Link-state routing protocol: Difference between revisions

Revision as of 10:15, 10 August 2022

Revision as of 15:31, 3 October 2022

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 [[Intermediate System to Intermediate System]] (IS-IS).

Line 9:

==Overview==

In [[link-state routing protocol]]sprotocols, 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 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.

Line 18:

==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-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.{{cncitation 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>

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 [[Enhanced Interior Gateway Routing Protocol]] (EIGRP) as a "hybrid" protocol,{{cncitation needed|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]]s or Rbridges. The [[Internet Engineering Task Force]] has standardized the [[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|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>

Line 41:

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

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

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

Line 87:

===Topology reduction===

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_ProtocolOptimized Link State Routing Protocol#Multipoint_relaysMultipoint 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 }}</ref>

# [[Connected dominating set]]s that again have been 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 }}</ref>

Line 109:

* 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==