 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(September 2010) (Learn how and when to remove this message) |
Link-state routing protocols are one of the two main classes ofrouting protocols used inpacket switching networks forcomputer communications, the others beingdistance-vector routing protocols.[1] Examples of link-state routing protocols includeOpen Shortest Path First (OSPF) andIntermediate System to Intermediate System (IS-IS).[2]
The link-state protocol is performed by everyswitching node in the network (i.e., nodes which are prepared to forward packets; in theInternet, these are calledrouters).[3] The basic concept of link-state routing is that every node constructs amap of the connectivity to the network in the form of agraph, showing which nodes are connected to which other nodes.[4] Each node then independently calculates the next best logicalpath from it to every possible destination in the network.[5] Each collection of best paths will then form each node'srouting table.[6]
This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors, in a link-state protocol, the only information passed between nodes isconnectivity related.[7] Link-state algorithms are sometimes characterized informally as each router "telling the world about its neighbors."[8]
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 withdistance-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.
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 fromPlessey Radar led by Bernard J Harris; the project was for "Wavell" – a system of computer command and control for theBritish Army.[citation needed] The first link-state routing concept was published in 1979 byJohn M. McQuillan (then atBolt, Beranek and Newman) as a mechanism that would calculate routes more quickly when network conditions changed and thus lead to more stable routing.[9][10]
The technique was later adapted for use in the contemporary link-state routing protocols IS-IS and OSPF.Cisco literature refers toEnhanced Interior Gateway Routing Protocol (EIGRP) as a "hybrid" protocol,[11] 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 forlayer 2 frame forwarding with devices calledrouting bridges, or Rbridges. TheInternet Engineering Task Force has standardized theTransparent Interconnection of Lots of Links (TRILL) protocol to accomplish this.[12]
More recently, this hierarchical technique was applied towireless mesh networks using theOptimized 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 somead hoc routing protocols that use radio frequency transmission.[citation needed]
 | This section'stone or style may not reflect theencyclopedic tone used on Wikipedia. See Wikipedia'sguide to writing better articles for suggestions.(October 2023) (Learn how and when to remove this message) |
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 usingreachability protocol that it runs periodically and separately with each of its directly connected neighbours.
Each node periodically (and in case of connectivity changes) sends a short message, thelink-state advertisement, which:
This message is sent to all the nodes on a network. As a necessary precursor, each node in the network remembers, for every one ofits 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.
The second main stage in the link-state algorithm is to produce routing tables by inspecting the maps. Each node independently runs analgorithm over the map to determine theshortest path from itself to every other node in the network; generally, some variant ofDijkstra's algorithm is used. A node maintains two data structures: atree containing nodes which are "done", and a list ofcandidates. The algorithm starts with both structures empty; it then adds to the first one the node itself. The variant of agreedy algorithm then repetitively does the following:
The 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. 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.
Whenever a change in the connectivity map happens, it is necessary to recompute the shortest-path tree and then recreate the routing table. BBN Technologies discovered how to compute only that part of the tree which could have been affected by a given change in the map.[citation needed]
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 aremultipoint relays that are at the base of theOptimized Link State Routing Protocol (OLSR) but have also been proposed for OSPF[13] andconnected dominating sets that were again proposed for OSPF.[14]
WithFisheye State Routing (FSR), the LSA are sent with different time-to-live values to restrict their diffusion and limit the overhead due to control messages. The same concept is used also in theHazy Sighted Link State Routing Protocol.
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.[15]
TheOptimized Link State Routing Protocol (OLSR) is a link-state routing protocol optimized formobile ad hoc networks (which can also be used on otherwireless ad hoc networks).[16] OLSR is proactive and uses hello andtopology control messages to disseminate link-state information into the mobile ad hoc network. Using hello messages, each node discovers two-hop neighbor information and elects a set ofmultipoint relays (MPRs). MPRs make OLSR distinct from other link-state routing protocols. Individual nodes use the topology information to compute next-hop paths regarding all nodes in the network using shortest-hop forwarding paths.
{{citation}}: CS1 maint: numeric names: authors list (link){{cite journal}}:Cite journal requires|journal= (help){{cite journal}}:Cite journal requires|journal= (help)