Link-state routing protocol: Difference between revisions

Revision as of 21:03, 4 August 2022

Revision as of 16:31, 5 August 2022

Line 2:

{{More footnotes|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).

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]].

This contrasts with [[distance-vector routing protocol]]sprotocols, 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."

==Overview==

Line 15:

Examples of link-state routing protocols:

* [[Open Shortest Path First]] (OSPF)

* [[Intermediate systemSystem to intermediateIntermediate systemSystem]] (IS-IS)

==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-771977 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.{{cn|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>

Line 24:

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}}

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,{{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.

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)|transparentTransparent 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}}</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]]s that use radio frequency transmission.

Line 68:

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 [[Greedygreedy Algorithmalgorithm]] 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===