Link-state routing protocol: Difference between revisions

Revision as of 16:00, 2 January 2022

Revision as of 14:36, 2 May 2022

Line 70:

The algorithm described above was made as simple as possible, to aid in ease of understanding. In practice, there are a number of optimizations which are used.

===Partial Recomputationrecomputation===

Whenever a change in the connectivity map happens, it is necessary to recompute the shortest-path tree, and then recreate the routing table. Work by [[BBN Technologies]]{{Citation needed|date=March 2013}} discovered how to recompute only that part of the tree which could have been affected by a given change in the map.

Also, the routing table would normally be filled in as the shortest-path tree is computed, instead of making it a separate operation.

===Topology Reductionreduction===

In some cases it is reasonable to reduce the number of nodes that generate LSA messages. For instance, a node that has only one connection to the network graph does not need to send LSA messages, as the information on its existence could be already included in the LSA message of its only neighbor. For this reason a topology reduction strategy can be applied, in which only a subset of the network nodes generate LSA messages. Two widely studied approaches for topology reduction are:

# [[Optimized_Link_State_Routing_Protocol#Multipoint_relays|MultiPointMultipoint Relaysrelays]] that are at the base of the [[Optimized_Link_State_Routing_Protocol|OLSROptimized Link State Routing Protocol]] protocol(OLSR) but have also been proposed for OSPF<ref>{{Cite document|url=https://tools.ietf.org/html/rfc5449|title = OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks|date = February 2009|last1 = Nguyen|first1 = Dang-Quan|last2 = Clausen|first2 = Thomas H.|last3 = Jacquet|first3 = Philippe|last4 = Baccelli|first4 = Emmanuel}}</ref>

# [[Connected_dominating_set|Connected Dominatingdominating Setsset]]s that again have been proposed for OSPF<ref>{{Cite document|url=https://tools.ietf.org/html/rfc5614|title = Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding|date = August 2009|last1 = Ogier|first1 = Richard|last2 = Spagnolo|first2 = Phil}}</ref>

===Fisheye State Routing===

With [[Fisheye_State_Routing|FSRFisheye State Routing]] (FSR) the LSA are sent with different TTLtime-to-live values in order to restrict their diffusion and limit the overhead due to control messages. The same concept is used also in the [[Hazy Sighted Link State Routing Protocol]].

==Failure modes==