Link-state routing protocol
Encyclopedia
A link-state routing protocol is one of the two main classes of routing protocol
s used in packet switching
networks for computer communications (the other is the distance-vector routing protocol
). Examples of link-state routing protocols include OSPF and 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 routers). 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
, 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. The collection of best paths will then form the node's routing table
.
This contrasts with distance-vector routing protocol
s, which work by having each node share its routing table with its neighbors. 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 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.
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.
The technique was later adapted for use in the contemporary link-state routing protocols IS-IS
and OSPF. Cisco literature refers to EIGRP as a "hybrid" protocol, 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 Bridges or RBridges. The Internet Engineering Task Force
is standardizing the TRILL protocol to accomplish this.
In the 2007 the IEEE started standardization of the use of IS-IS
to control Ethernet
forwarding with the IEEE 802.1aq
Shortest Path Bridging project based on earlier proprietary work Provider Link-State Bridging PLSB.
More recently, this hierarchical technique was applied to wireless mesh network
s using the optimized link state routing protocol
. Where a connection can have varying quality, the quality of a connection can be used to select better connections. This is used in some routing protocols
that use radio frequency transmission.
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 simple subsidiary steps.
, which:
This message is then flooded throughout the network. As a necessary precursor, each node in the network remembers, for every other node in the network, the sequence number of the last link-state message which it received from that node. With that in hand, the method used is simple.
Starting with the node which originally produced the message, it sends a copy to all of its neighbors. 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, 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.
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.
The algorithm simply 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.
over the map to determine the 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.
Basically, a node maintains two data structures: a 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:
The above two steps are repeated as long as there aren't 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.
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.
Most importantly, 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
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.
The reason is fairly simple: since each node computes its shortest-path tree and its routing table without interacting in any way with any other nodes, then if two nodes start with different maps, it is easy to have scenarios in which routing loops are created.
s - is the Optimized Link State Routing Protocol
(OLSR). OLSR is proactive, it uses Hello and Topology Control (TC) messages to discover and disseminate link state information into the mobile ad-hoc network. Using Hello messages each node discovers 2-hop neighbor information and elects a set of multipoint relay
s (MPRs). MPRs makes OLSR unique from other link state routing protocols. Individual nodes use the topology information to compute next hop paths regard to all nodes in the network utilising shortest hop forwarding paths.
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
s used in packet switching
Packet switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
networks for computer communications (the other is the distance-vector routing protocol
Distance-vector routing protocol
In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of routing protocols, the other major class being the link-state protocol...
). Examples of link-state routing protocols include OSPF and IS-IS
IS-IS
Intermediate System To Intermediate System , is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices....
.
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
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, these are called routers). 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
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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. The collection of best paths will then form the node's routing table
Routing table
In computer networking a routing table, or Routing Information Base , is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics associated with those routes. The routing table contains information about the...
.
This contrasts with distance-vector routing protocol
Distance-vector routing protocol
In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of routing protocols, the other major class being the link-state protocol...
s, which work by having each node share its routing table with its neighbors. 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'.
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.The first link-state routing concept was published in 1979 by John M. McQuillan
John M. McQuillan
John M. McQuillan is an American computer scientist, known for studies of adaptive routing in the early ARPANET.He received his A.B. , M.S. and Ph.D. in applied mathematics from Harvard University...
(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.
Later work at BBN Technologies
BBN Technologies
BBN Technologies is a high-technology company which provides research and development services. BBN is based next to Fresh Pond in Cambridge, Massachusetts, USA...
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.
The technique was later adapted for use in the contemporary link-state routing protocols IS-IS
IS-IS
Intermediate System To Intermediate System , is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices....
and OSPF. Cisco literature refers to EIGRP as a "hybrid" protocol, 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
Radia Perlman
Radia Joy Perlman is a software designer and network engineer sometimes referred to as the "Mother of the Internet." She is most famous for her invention of the spanning-tree protocol , which is fundamental to the operation of network bridges, while working for Digital Equipment Corporation...
proposed using link-state routing for Layer 2 frame forwarding with devices called Routing Bridges or RBridges. The Internet Engineering Task Force
Internet Engineering Task Force
The Internet Engineering Task Force develops and promotes Internet standards, cooperating closely with the W3C and ISO/IEC standards bodies and dealing in particular with standards of the TCP/IP and Internet protocol suite...
is standardizing the TRILL protocol to accomplish this.
In the 2007 the IEEE started standardization of the use of IS-IS
IS-IS
Intermediate System To Intermediate System , is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices....
to control Ethernet
Ethernet
Ethernet is a family of computer networking technologies for local area networks commercially introduced in 1980. Standardized in IEEE 802.3, Ethernet has largely replaced competing wired LAN technologies....
forwarding with the IEEE 802.1aq
IEEE 802.1aq
802.1aq Shortest Path Bridging or SPB in computer networking is a technology that greatly simplifies the creation and configuration of carrier, enterprise, and cloud networks which virtually eliminates human error, while enabling multipath routing...
Shortest Path Bridging project based on earlier proprietary work Provider Link-State Bridging PLSB.
More recently, this hierarchical technique was applied to wireless mesh network
Wireless mesh network
A wireless mesh network is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways.The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic...
s using the optimized link state routing protocol
Optimized link state routing protocol
The Optimized Link State Routing Protocol is an IP routing protocol optimized for mobile ad-hoc networks, which can also be used on other wireless ad-hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control messages to discover and then disseminate...
. Where a connection can have varying quality, the quality of a connection can be used to select better connections. This is used in some routing protocols
Ad hoc routing protocol list
An ad-hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network ....
that use radio frequency transmission.
Distributing maps
This description covers only the simplest configuration; i.e. one with no areas, so that all nodes do have a map of the entire network. The hierarchical case is somewhat more complex; see the various protocol specifications.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 simple subsidiary steps.
Determining the neighbors of each node
First, each node needs to determine what other ports it is connected to, over fully working links; it does this using a simple reachability protocol which it runs separately with each of its directly connected neighbors.Distributing the information for the map
Next, each node periodically and in case of connectivity changes makes up a short message, the link-state advertisementLink-state advertisement
The link-state advertisement is a basic communication means of the OSPF routing protocol for the Internet Protocol . It communicates the router's local routing topology to all other local routers in the same OSPF area. OSPF is designed for scalability, so some LSAs are not flooded out on all...
, which:
- Identifies the node which 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 then flooded throughout the network. As a necessary precursor, each node in the network remembers, for every other node in the network, the sequence number of the last link-state message which it received from that node. With that in hand, the method used is simple.
Starting with the node which originally produced the message, it sends a copy to all of its neighbors. 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, 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.
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, it is obviously easy to produce the graph for the map of the network.The algorithm simply 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.
Calculating the routing table
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 algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
over the map to determine the shortest path
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
from itself to every other node in the network; generally some variant of Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
is used. This is based around a link cost across each path which includes available bandwidth among other things.
Basically, a node maintains two data structures: a 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
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
then repetitively does the following:
- All nodes which are connected to the node just added to the tree (excepting any nodes which are already in either the tree or the candidate list) 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 aren't 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, filling in the routing table is trivial.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.
Optimizations to 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.Most importantly, 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
BBN Technologies
BBN Technologies is a high-technology company which provides research and development services. BBN is based next to Fresh Pond in Cambridge, Massachusetts, USA...
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.
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.)The reason is fairly simple: since each node computes its shortest-path tree and its routing table without interacting in any way with any other nodes, then if two nodes start with different maps, it is easy to have scenarios in which routing loops are created.
The Optimized Link State Routing Protocol for Mobile ad-hoc Networks
A link-state routing protocol - optimized for mobile ad-hoc networks, which can also be used on other wireless ad-hoc networkWireless ad-hoc network
A wireless ad-hoc network is a decentralized type of wireless network. The network is ad hoc because it does not rely on a preexisting infrastructure, such as routers in wired networks or access points in managed wireless networks...
s - is the Optimized Link State Routing Protocol
Optimized link state routing protocol
The Optimized Link State Routing Protocol is an IP routing protocol optimized for mobile ad-hoc networks, which can also be used on other wireless ad-hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control messages to discover and then disseminate...
(OLSR). OLSR is proactive, it uses Hello and Topology Control (TC) messages to discover and disseminate link state information into the mobile ad-hoc network. Using Hello messages each node discovers 2-hop neighbor information and elects a set of multipoint relay
Multipoint relay
Multi Point Relays are nodes in wireless Ad-Hoc networks that do the job of relaying messages between nodes, they also have the main role in routing and selecting the proper route from any source to any desired destination node - Arash Modaresi....
s (MPRs). MPRs makes OLSR unique from other link state routing protocols. Individual nodes use the topology information to compute next hop paths regard to all nodes in the network utilising shortest hop forwarding paths.
Further reading
- Section "Link-State Versus Distance Vector" in the Chapter "Routing Basics" in the CiscoCisco SystemsCisco Systems, Inc. is an American multinational corporation headquartered in San Jose, California, United States, that designs and sells consumer electronics, networking, voice, and communications technology and services. Cisco has more than 70,000 employees and annual revenue of US$...
"Internetworking Technology Handbook"