Link-state routing protocols are one of the two main classes of

routing protocol A routing protocol specifies how routers communicate with each other to distribute information that enables them to select paths between nodes on a computer network. Routers perform the traffic directing functions on the Internet; data packet ...

s used in

packet switching In telecommunications, packet switching is a method of grouping Data (computing), data into short messages in fixed format, i.e. ''network packet, packets,'' that are transmitted over a digital Telecommunications network, network. Packets consi ...

networks for computer communications, the others being

distance-vector routing protocol A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop ...

s. Examples of link-state routing protocols include

Open Shortest Path First Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single Autonomous syste ...

(OSPF) and

Intermediate System to Intermediate System Intermediate System to Intermediate System (IS-IS, also written ISIS) is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes thi ...

(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 The Internet (or internet) is the Global network, global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a internetworking, network of networks ...

, 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 may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

, 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 In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated wi ...

. 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 British Army is the principal Army, land warfare force of the United Kingdom. the British Army comprises 73,847 regular full-time personnel, 4,127 Brigade of Gurkhas, Gurkhas, 25,742 Army Reserve (United Kingdom), volunteer reserve perso ...

. The first link-state routing concept was published in 1979 by John M. McQuillan (then at

Bolt, Beranek and Newman Raytheon BBN (originally Bolt, Beranek and Newman, Inc.) is an American research and development company based in Cambridge, Massachusetts. In 1966, the Franklin Institute awarded the firm the Frank P. Brown Medal, in 1999 BBN received the ...

) 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 Cisco Systems, Inc. (using the trademark Cisco) is an American multinational digital communications technology conglomerate corporation headquartered in San Jose, California. Cisco develops, manufactures, and sells networking hardware, s ...

literature refers to

Enhanced Interior Gateway Routing Protocol Enhanced Interior Gateway Routing Protocol (EIGRP) is an advanced distance-vector routing protocol that is used on a computer network for automating routing decisions and configuration. The protocol was designed by Cisco Systems as a proprietary p ...

(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 Joy Perlman (; born December 18, 1951) is an American computer programmer and network engineer. She is a major figure in assembling the networks and technology to enable what we now know as the Internet. She is most famous for her inventi ...

proposed using link-state routing for

layer 2 The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer pr ...

frame forwarding with devices called

routing bridge A routing bridge or RBridge, also known as a TRILL switch, is a network device that implements the TRILL protocol and should not be confused with BRouters (Bridging Routers). RBridges are compatible with previous IEEE 802.1 customer bridges as well ...

s, or Rbridges. The

Internet Engineering Task Force The Internet Engineering Task Force (IETF) is a standards organization for the Internet standard, Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster ...

has standardized the

Transparent Interconnection of Lots of Links TRILL (Transparent Interconnection of Lots of Links) is a networking protocol for optimizing bandwidth and resilience in Ethernet networks, implemented by devices called TRILL switches. TRILL combines techniques from bridging and routing, and ...

(TRILL) protocol to accomplish this. More recently, this hierarchical technique was applied to

wireless mesh network A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network. Chai Keong Toh Ad Hoc Mobile Wireless Networks, Prentice Hall Publishers, 2002. ...

s using the

Optimized Link State Routing Protocol The Optimized Link State Routing Protocol (OLSR) is an Internet Protocol, 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, whic ...

(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 The link-state advertisement (LSA) is a basic communication means of the OSPF routing protocol for the Internet Protocol (IP). It communicates the router's local routing topology to all other local routers in the same OSPF area. OSPF is designed fo ...

, 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 In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

over the map to determine the

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

from itself to every other node in the network; generally, some variant of

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...

is used. A node maintains two data structures: a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

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 A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

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

Algorithm optimizations

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.

Topology reduction

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 are multipoint relays that are at the base of the

(OLSR) but have also been proposed for OSPF and connected dominating sets that were again proposed for OSPF.

Fisheye State Routing

With Fisheye 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 the

Hazy Sighted Link State Routing Protocol The Hazy-Sighted Link State Routing Protocol (HSLS) is a wireless mesh network routing protocol being developed by the CUWiN Foundation. This is an algorithm allowing computers communicating via digital radio in a mesh network to forward messages ...

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

Optimized Link State Routing Protocol

The

(OLSR) is a link-state routing protocol optimized for

mobile ad hoc network A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as router (computing), routers or wireless acces ...

s (which can also be used on other

wireless ad hoc network A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, ...

s).RFC 3626 OLSR is proactive and uses hello and topology 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 of '' multipoint 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.

References

* Josh Seeger and Atul Khanna, ''Reducing Routing Overhead in a Growing DDN'', MILCOMM '86, IEEE, 1986 *

br>“Rbridges: Transparent Routing”
Infocom 2004.