Link-state

Link-state routing protocols are one of the two main classes of used in packet switching networks for computer communications, the other being . 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 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. Each collection of best paths will then form each node's routing table.

This contrasts with 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 nodes is connectivity related. Link-state algorithms are sometimes characterized informally as each router, "telling the world about its neighbours."

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

...
Wikipedia