Link-state routing protocol: Difference between revisions

Revision as of 06:27, 25 May 2021

Latest revision as of 02:51, 3 June 2025

(42 intermediate revisions by 24 users not shown)

Line 1:

{{short description|Class of routing protocols}}

{{More footnotes needed|date=September 2010}}

'''Link-state routing protocols''' are one of the two main classes of [[routing protocol]]s used in [[packet switching]] networks for [[computer communication]]s, the other being [[distance-vector routing protocol]]s. Examples of link-state routing protocols include [[Open Shortest Path First]] (OSPF) and [[IS-IS|Intermediate System to Intermediate System]] (IS-IS).

'''Link-state routing protocols''' are one of the two main classes of [[routing protocol]]s used in [[packet switching]] networks for [[computer communication]]s, the otherothers being [[distance-vector routing protocol]]s.<ref>{{Cite web |date=2018-05-18 |title=Unicast Routing - Link State Routing |url=https://www.geeksforgeeks.org/unicast-routing-link-state-routing/ |access-date=2024-05-09 |website=GeeksforGeeks |language=en-US}}</ref> Examples of link-state routing protocols include [[Open Shortest Path First]] (OSPF) and [[IS-IS|Intermediate System to Intermediate System]] (IS-IS).<ref>lec10-lsrouting.pdf (princeton.edu)

The link-state protocol is performed by every ''switching node'' in the network (i.e., nodes that are prepared to forward packets; in the [[Internet]], these are called [[Router (computing)|router]]s). The basic concept of link-state routing is that every node constructs a ''map'' of the connectivity to the network, in the form of a [[graph theory|graph]], showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical ''path'' from it to every possible destination in the network. Each collection of best paths will then form each node's [[routing table]].

<nowiki>https://www.cs.princeton.edu/courses/archive/spring23/cos461/lectures/lec10-lsrouting.pdf</nowiki></ref>

This contrasts with [[distance-vector routing protocol]]s, which work by having each node share its routing table with its neighbours, in a link-state protocol the only information passed between nodes is ''connectivity related''. Link-state algorithms are sometimes characterized informally as each router, "telling the world about its neighbors."

The link-state protocol is performed by every ''switching node'' in the network (i.e., nodes which are prepared to forward packets; in the [[Internet]], these are called [[Router (computing)|router]]s).<ref>lecture6.pptx (umich.edu)

==History==

What is believed to be the first adaptive routing network of computers, using link-state routing as its heart, was designed and implemented during 1976-77 by a team from [[Plessey Radar]] led by Bernard J Harris; the project was for "Wavell" - a system of computer command and control for the British Army.{{cn|date=September 2016}}

<nowiki>https://www.eecs.umich.edu/courses/eecs489/w10/winter10/lectures/lecture6_2.pdf</nowiki></ref> The basic concept of link-state routing is that every node constructs a ''map'' of the connectivity to the network in the form of a [[graph theory|graph]], showing which nodes are connected to which other nodes.<ref>123sp15-lec14.pdf (ucsd.edu)

The first link-state routing concept was published in 1979 by [[John M. McQuillan]] (then at [[Bolt, Beranek and Newman]]) as a mechanism that would calculate routes more quickly when network conditions changed, and thus lead to more stable routing.<ref>[[John M. McQuillan]], Isaac Richer and Eric C. Rosen, ''ARPANet Routing Algorithm Improvements'', BBN Report No. 3803, Cambridge, April 1978</ref><ref>[[John M. McQuillan]], Isaac Richer and Eric C. Rosen, ''The New Routing Algorithm for the ARPANet'', [[IEEE]] Trans. on Comm., 28(5), pp.&nbsp;711–719, 1980</ref>

<nowiki>https://cseweb.ucsd.edu/classes/sp15/cse123-a/lectures/123sp15-lec14.pdf</nowiki></ref> Each node then independently calculates the next best logical ''path'' from it to every possible destination in the network.<ref>link state protocol.pdf (fauser.edu)

Later work at [[BBN Technologies]] showed how to use the link-state technique in a hierarchical system (i.e., one in which the network was divided into areas) so that each switching node does not need a map of the entire network, only the area(s) in which it is included.{{Citation needed|reason=where can we read more about this work?|date=February 2013}}

<nowiki>http://nuovolabs.fauser.edu/~valeria/materiale-didattico/sistemi-quinta/link%20state%20protocol.pdf</nowiki></ref> Each collection of best paths will then form each node's [[routing table]].<ref>{{Cite web |date=2019-08-12 |title=9.6: Link-State Routing-Update Algorithm |url=https://eng.libretexts.org/Bookshelves/Computer_Science/Networks/Book%3A_An_Introduction_to_Computer_Networks_(Dordal)/09%3A_Routing-Update_Algorithms/9.06%3A_Link-State_Routing-Update_Algorithm |access-date=2024-05-09 |website=Engineering LibreTexts |language=en}}</ref>

The technique was later adapted for use in the contemporary link-state routing protocols IS-IS and OSPF. Cisco literature refers to [[enhanced interior gateway routing protocol]] (EIGRP) as a "hybrid" protocol,{{cn|date=September 2016}} despite the fact it distributes routing tables instead of topology maps. However, it does synchronize routing tables at start up as OSPF does, and sends specific updates only when topology changes occur.

This contrasts with [[distance-vector routing protocol]]sprotocols, which work by having each node share its routing table with its neighboursneighbors, in a link-state protocol, the only information passed between nodes is ''connectivity related''. Link<ref>5-staterouting-part2.pdf algorithms are sometimes characterized informally as each router, "telling the world about its neighbors(washington."edu)

In 2004, [[Radia Perlman]] proposed using link-state routing for [[layer 2]] frame forwarding with devices called [[Routing Bridge|routing bridge]]s or Rbridges. The [[Internet Engineering Task Force]] has standardized the [[TRILL (Computer Networking)|transparent interconnection of lots of links]] (TRILL) protocol to accomplish this.<ref>{{citation |rfc=7176 |title=Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS}}</ref>

<nowiki>https://courses.cs.washington.edu/courses/cse461/22sp/slides/5-routing-part2.pdf</nowiki></ref> Link-state algorithms are sometimes characterized informally as each router "telling the world about its neighbors."<ref>{{Cite web |last=Library |first=Broadband |date=2018-08-31 |title=A Closer Look at Routing {{!}} |url=https://broadbandlibrary.com/a-closer-look-at-routing/ |access-date=2024-05-09 |language=en-US}}</ref>

More recently, this hierarchical technique was applied to [[wireless mesh network]]s using the [[optimized link state routing protocol]] (OLSR). Where a connection can have varying quality, the quality of a connection can be used to select better connections. This is used in some [[Ad hoc routing protocol list|routing protocols]] that use radio frequency transmission.

==Overview==

In 2012, the [[IEEE]] completed and approved the standardization of the use of IS-IS to control [[Ethernet]] forwarding with [[IEEE 802.1aq]] shortest path bridging (SPB).

In link-state routing protocols, each router possesses information about the complete network topology. Each router then independently calculates the best next hop from it for every possible destination in the network using local information of the topology. The collection of best next hops forms the routing table.

This contrasts with [[Distance-vector routing protocol|distance-vector routing protocols]], which work by having each node share its routing table with its neighbours. In a link-state protocol, the only information passed between the nodes is the information used to construct the connectivity maps.

==Distributing maps==

This description covers only the simplest configuration; i.e., one with no areas, so that all nodes have a map of the entire network. The hierarchical case is somewhat more complex; see the various protocol specifications.

==History==

As previously mentioned, the first main stage in the link-state algorithm is to give a map of the network to every node. This is done with several subsidiary steps.

What is believed to be the first adaptive routing network of computers, using link-state routing, was designed and implemented during 1976–1977 by a team from [[Plessey Radar]] led by Bernard J Harris; the project was for "Wavell"{{snd}} a system of computer command and control for the [[British Army]].{{citation needed|date=September 2016}} The first link-state routing concept was published in 1979 by [[John M. McQuillan]] (then at [[Bolt, Beranek and Newman]]) as a mechanism that would calculate routes more quickly when network conditions changed, and thus lead to more stable routing.<ref>[[John M. McQuillan]], Isaac Richer and Eric C. Rosen, ''ARPANet Routing Algorithm Improvements'', BBN Report No. 3803, Cambridge, April 1978</ref><ref>[[John M. McQuillan]], Isaac Richer and Eric C. Rosen, ''The New Routing Algorithm for the ARPANet'', [[IEEE]] Trans. on Comm., 28(5), pp.&nbsp;711–719, 1980</ref>

The technique was later adapted for use in the contemporary link-state routing protocols IS-IS and OSPF. [[Cisco]] literature refers to [[enhancedEnhanced interiorInterior gatewayGateway routingRouting protocolProtocol]] (EIGRP) as a "hybrid" protocol,<ref>{{cnCite web |title=Cisco Firepower Threat Defense Configuration Guide for Firepower Device Manager, Version 7.1 - Enhanced Interior Gateway Routing Protocol (EIGRP) [Cisco Secure Firewall Threat Defense] |url=https://www.cisco.com/c/en/us/td/docs/security/firepower/710/fdm/fptd-fdm-config-guide-710/fptd-fdm-eigrp.html |access-date=September2024-01-18 2016|website=Cisco |language=en}}</ref> despite the fact it distributes routing tables instead of topology maps. However, it does synchronize routing tables at start -up as OSPF does, and sends specific updates only when topology changes occur.

===Determining the neighbours of each node===

First, each node needs to determine what other ports it is connected to, over fully working links; it does this using ''reachability protocol'' it runs periodically and separately with each of its directly connected neighbours.

In 2004, [[Radia Perlman]] proposed using link-state routing for [[layer 2]] frame forwarding with devices called [[Routing Bridge|routing bridge]]s, or Rbridges. The [[Internet Engineering Task Force]] has standardized the [[TRILLTransparent (Computer Networking)|transparent interconnectionInterconnection of lotsLots of linksLinks]] (TRILL) protocol to accomplish this.<ref>{{citation |rfc=7176 |title=Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS|date=May 2014|last1=Eastlake 3Rd|first1=Donald E.|last2=Senevirathne|first2=Tissa|last3=Ghanwani|first3=Anoop|last4=Dutt|first4=Dinesh|last5=Banerjee|first5=Ayan|doi=10.17487/RFC7176 }}</ref>

===Distributing the information for the map===

{{unclear|date=November 2020|reason=from the given description, it is not clear how sequence numbers work: 1) how are they generated, 2) how are they "updated" when a node receives a message, 3) how exactly do they prevent sending a message in a cycle}}

More recently, this hierarchical technique was applied to [[wireless mesh network]]s using the [[optimizedOptimized linkLink stateState routingRouting protocolProtocol]] (OLSR). Where a connection can have varying quality, the quality of a connection can be used to select better connections. This is used in some [[Adad hoc routing protocol list|routing protocols]]s that use radio frequency transmission.{{citation needed|date=July 2024}}

Next, each node periodically (and in case of connectivity changes) sends a short message, the [[link-state advertisement]], which:

==Distributing maps==

* Identifies the node which is producing it.

{{Tone|date=October 2023|section}}

The first main stage in the link-state algorithm is to give a map of the network to every node. This is done with several subsidiary steps. First, each node needs to determine what other ports it is connected to, over fully working links; it does this using ''reachability protocol'' that it runs periodically and separately with each of its directly connected neighbours.

Next, eachEach node periodically (and in case of connectivity changes) sends a short message, the [[link-state advertisement]], which:

* Identifies the node whichthat is producing it.

* Identifies all the other nodes (either routers or networks) to which it is directly connected.

* Includes a 'sequence number', which increases every time the source node makes up a new version of the message''.''

This message is sent to all the nodes on a network. As a necessary precursor, each node in the network remembers, for every one of ''its'' neighbors, the sequence number of the last link-state message which it received from that node. When a link-state advertisement is received at a node, the node looks up the sequence number it has stored for the source of that link-state message:; if this message is newer (i.e., has a higher sequence number), it is saved, the sequence number is updated, and a copy is sent in turn to each of that node's neighbors. This procedure rapidly gets a copy of the latest version of each node's link-state advertisement to every node in the network.

The complete set produces the graph for the map of the network. The link-state message giving information about the neighbors is recomputed, and then flooded throughout the network, whenever there is a change in the connectivity between the node and its neighbors;, e.g., when a link fails. Any such change will be detected by the reachability protocol which each node runs with its neighbors.

Networks running link state algorithms can also be segmented into hierarchies which limit the scope of route changes. These features mean that link state algorithms scale better to larger networks.

===Creating the map===

Finally, with the complete set of link-state advertisements (one from each node in the network) in hand, each node produces the graph for the map of the network.

The algorithm iterates over the collection of link-state advertisements; for each one, it makes links on the map of the network, from the node which sent that message, to all the nodes which that message indicates are neighbors of the sending node.

No link is considered to have been correctly reported unless the two ends agree; i.e., if one node reports that it is connected to another, but the other node does not report that it is connected to the first, there is a problem, and the link is not included on the map.

===Notes about this stage===

The link-state message giving information about the neighbors is recomputed, and then flooded throughout the network, whenever there is a change in the connectivity between the node and its neighbors; e.g., when a link fails. Any such change will be detected by the reachability protocol which each node runs with its neighbors.

==Calculating the routing table==

The second main stage in the link-state algorithm is to produce routing tables by inspecting the maps. Each node independently runs an [[algorithm]] over the map to determine the [[Shortest path problem|shortest path]] from itself to every other node in the network; generally, some variant of [[Dijkstra's algorithm]] is used. A node maintains two data structures: a [[Tree data structure|tree]] containing nodes which are "done", and a list of ''candidates''. The algorithm starts with both structures empty; it then adds to the first one the node itself. The variant of a [[Greedygreedy Algorithmalgorithm]] then repetitively does the following:

As initially mentioned, the second main stage in the link-state algorithm is to produce routing tables, by inspecting the maps. This is again done with several steps.

===Calculating the shortest paths===

Each node independently runs an [[algorithm]] over the map to determine the [[Shortest path problem|shortest path]] from itself to every other node in the network; generally some variant of [[Dijkstra's algorithm]] is used. This is based around a link cost across each path which includes available bandwidth among other things.

A node maintains two data structures: a [[Tree data structure|tree]] containing nodes which are "done", and a list of ''candidates''. The algorithm starts with both structures empty; it then adds to the first one the node itself. The variant of a [[Greedy Algorithm]] then repetitively does the following:

* All neighbour nodes which are directly connected to the node are just added to the tree (excepting any nodes which are already in either the tree or the candidate list). The rest are added to the second (candidate) list.

* Each node in the candidate list is compared to each of the nodes already in the tree. The candidate node which is closest to any of the nodes already in the tree is itself moved into the tree and attached to the appropriate neighbor node. When a node is moved from the candidate list into the tree, it is removed from the candidate list and is not considered in subsequent iterations of the algorithm.

The above two steps are repeated as long as there are any nodes left in the candidate list. (When there are none, all the nodes in the network will have been added to the tree.) This procedure ends with the tree containing all the nodes in the network, with the node on which the algorithm is running as the ''root'' of the tree. The shortest path from that node to any other node is indicated by the list of nodes one traverses to get from the root of the tree, to the desired node in the tree..!

===Filling the routing table===

With the shortest paths in hand, the next step is to fill in the routing table. For any given destination node, the best path for that destination is the node which is the first step from the root node, down the branch in the shortest-path tree which leads toward the desired destination node. To create the routing table, it is only necessary to walk the tree, remembering the identity of the node at the head of each branch, and filling in the routing table entry for each node one comes across with that identity.

* All neighbour nodes which are directly connected to the node are just added to the tree (excepting any nodes which are already in either the tree or the ''candidate'' list). The rest are added to the second (''candidate'') list.

==Optimizations to the algorithm==

* Each node in the ''candidate'' list is compared to each of the nodes already in the tree. The candidate node which is closest to any of the nodes already in the tree is itself moved into the tree and attached to the appropriate neighbor node. When a node is moved from the candidate list into the tree, it is removed from the candidate list and is not considered in subsequent iterations of the algorithm.

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.

The above two steps are repeated as long as there are any nodes left in the candidate list. (When there are none, all the nodes in the network will have been added to the tree.) This procedure ends with the tree containing all the nodes in the network,. withFor theany nodegiven ondestination whichnode, the algorithmbest ispath runningfor asthat thedestination ''root'' ofis the tree. The shortest path from that node to any other nodewhich is indicated by the listfirst ofstep nodesfrom onethe traversesroot tonode, get fromdown the rootbranch ofin the shortest-path tree, towhich leads toward the desired destination node in the tree..!

===Partial Recomputation===

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.

== Algorithm optimizations ==

===Topology Reduction===

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 recomputecompute only that part of the tree which could have been affected by a given change in the map.{{Citation needed|date=March 2013}}

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|MultiPoint Relays]] that are at the base of the [[Optimized_Link_State_Routing_Protocol|OLSR]] protocol but have also been proposed for OSPF<ref>https://tools.ietf.org/html/rfc5449</ref>

# [[Connected_dominating_set|Connected Dominating Sets]] that again have been proposed for OSPF<ref>https://tools.ietf.org/html/rfc5614</ref>

===Topology Reductionreduction===

In some cases, it is reasonable to reduce the number of nodes that generate LSA messages. 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|multipoint relays]] that are at the base of the [[Optimized Link State Routing Protocol]] (OLSR) but have also been proposed for OSPF<ref>{{Cite journal|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| doi=10.17487/RFC5449 |doi-access = free|url-access = subscription}}</ref> and [[connected dominating set]]s that were again proposed for OSPF.<ref>{{Cite journal|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| doi=10.17487/RFC5614 |url-access = subscription}}</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==

If all the nodes are not working from '''exactly''' the same map, ''routing loops'' can form. These are situations in which, in the simplest form, two neighboring nodes each think the other is the best path to a given destination. Any packet headed to that destination arriving at either node will loop between the two, hence the name. Routing loops involving more than two nodes are also possible.

This can occur since each node computes its shortest-path tree and its routing table without interacting in any way with any other nodes. If two nodes start with different maps, it is possible to have scenarios in which routing loops are created. In certain circumstances, differential loops may be enabled within a multi -cloud environment. Variable access nodes across the interface protocol may also bypass the simultaneous access node problem.<ref>{{cite journal |last1=Wójcik |first1=R |title=A survey on methods to provide interdomain multipath transmissions |journal=Computer Networks |date=2016 |volume=108|pages=233–259 |doi=10.1016/j.comnet.2016.08.028 }}</ref>

==The Optimized Link State Routing Protocol for mobile ad hoc networks==

The ''[[Optimized Link State Routing Protocol]]'' (OLSR) is a link-state routing protocol optimized for [[mobile ad hoc network]]s (which can also be used on other [[wireless ad hoc network]]s).<ref>RFC 3626</ref> OLSR is proactive, itand uses Hellohello and Topology[[topology Control (TC)control]] messages to discover and disseminate link -state information into the [[mobile ad hoc network]]. Using Hellohello messages, each node discovers 2two-hop neighbor information and elects a set of ''[[multipoint relay]]s'' (MPRs). MPRs makesmake OLSR uniquedistinct from other link -state routing protocols. Individual nodes use the topology information to compute next -hop paths regard toregarding all nodes in the network using shortest -hop forwarding paths.

==See also==

Line 95 ⟶ 75:

==References==

<references />

{{refbegin}}

{{More footnotes|date=September 2010}}

* Josh Seeger and Atul Khanna, ''Reducing Routing Overhead in a Growing DDN'', MILCOMM '86, IEEE, 1986

* [[Radia Perlman]] [http://www.ieee-infocom.org/2004/Papers/26_1.PDF “Rbridges: Transparent Routing”], Infocom 2004.

{{refend}}

==Further reading==