Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). 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 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. Each collection of best paths will then form each node's routing table. 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 is connectivity related. Link-state algorithms are sometimes characterized informally as each router "telling the world about its neighbors."
Overview 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 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.
History 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" – 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 (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. 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, 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 has standardized the Transparent Interconnection of Lots of Links (TRILL) protocol to accomplish this. More recently, this hierarchical technique was applied to wireless mesh networks 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 protocols that use radio frequency transmission.
Distributing maps
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. Each node periodically (and in case of connectivity changes) sends a short message, the link-state advertisement, which:
Identifies the node that 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.
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 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 greedy algorithm then repetitively does the following:
… excerpt ends here. Continue reading the full article.
