Routing protocols and architectures/The Link State algorithm

The Link State (LS) algorithm is based on distribution of information about the neighborhood of the router over the whole network. Each node can create the map of the network (the same for all nodes), from which the routing table has to be obtained.

Components

• Neighbor Greetings
• Link States
• flooding algorithm
• Dijkstra's algorithm
• adjacency bring-up

Neighbor Greetings

Neighbor Greetings are messages periodically exchanged between adjacent nodes to collect information about adjacencies. Each node:

• sends Neighbor Greetings to report its existence to its neighbors;
• receives Neighbor Greetings to learn which are its neighbors and the costs to reach them.

Neighbor Greetings implement fault detection based on a maximum number of consecutive Neighbor Greetings not received:

• fast: Neighbor Greetings can be sent with a high frequency (e.g. every 2 seconds) to recognize variations on adjacencies in a very short time:
  • once they are received, they are not propagated but stop on the first hop → they do not saturate the network;
  • they are packets of small size because they do not include information about nodes other than the generating node;
  • they require a low overhead for routers, which are not forced to compute again their routing table whenever they receive one of them;
• reliable: it does not rely on the 'link-up' signal, unavailable in presence of hubs.

Link States

Each router generates a LS, which is a set of adjacency-cost pairs:

• adjacency: all the neighbors of the generating node;
• cost: the cost of the link between the generating router and its neighbor.

Each node stores all the LSs coming from all nodes in the network into the Link State Database, then it scans the list of all adjacencies and builds a graph by merging nodes (routers) with edges (links) in order to build the map of the network.

LS generation is mainly event-based: a LS is generated following a change in the local topology (= in the neighborhood of the router):

• the router has got a new neighbor;
• the cost to reach a neighbor has changed;
• the router has lost its connectivity to a neighbor previously reachable.

Event-based generation:

• allows a better utilization of the network: it does not consume bandwidth;
• it requires the 'hello' component, based on Neighbor Greetings, as the router can no longer use the periodic generation for detecting faults toward its neighbors.

In addition, routers implement also a periodic generation, with a very low frequency (in the order of tens of minutes):

• this increases reliability: if a LS for some reason goes lost, it can be sent again without having to wait for the next event;
• this allows to include an 'age' field: the entry related to a disappeared destination remains in the routing table and packets keep being sent to that destination until the piece of information, if not refreshed, ages enough that it can be deleted.

Flooding algorithm

Each LS must be sent in 'broadcast' to all the routers in the network, which must receive it unchanged → real protocols implement a sort of selective flooding, representing the only way to reach all routers with the same data and with minimum overhead. Broadcast is limited only to LSs, to avoid saturating the network.

LS propagation takes place at a high speed: unlike DVs, each router can immediately propagate the received LS and in a later time process it locally.

Real protocols implement a reliable mechanism for LS propagation: every LS must be confirmed 'hop by hop' by an acknowledgment, because the router must be sure that the LS sent to its neighbors has been received, also considering that LSs are generated with a low frequency.

Dijkstra's algorithm

After building the map of the network from its adjacency lists, each router is able to compute the spanning tree of the graph, that is the tree with least-cost paths having the node as a root, thanks to the Dijkstra algorithm: on every iteration all the links are considered connecting nodes already selected with nodes not yet selected, and the closest adjacent node is selected.

All nodes have the same Link State Database, but each node has a different routing tree to the destinations, because the obtained spanning tree changes as the chosen node as a root changes:

• better distribution of the traffic: reasonably there are no unused links (unlike Spanning Tree Protocol);
• obviously the routing tree must be consistent among the various nodes.

Adjacency bring-up

Bringing up adjacencies is required to synchronize Link State Databases of routers when a new adjacency is detected:

• a new node connects to the network: the adjacent node communicates to it all the LSs related to the network, to populate its Link State Database from which it will be able to compute its routing table;
• two partitioned subnetworks (e.g. due to a failure) are re-connected together: each of the two nodes at the link endpoints communicates to the other node all the LSs related to its subnetwork.

Procedure

1. a new adjacency is detected by the 'hello' protocol, which keeps adjacencies under control;
2. synchronization is a point-to-point process, that is it affects only the two routers at the endpoints of the new link;
3. the LSs which had previously been unknown are sent to other nodes in the network in flooding.

Behaviour over broadcast data-link-layer networks

The LS algorithms models the network as a set of point-to-point links → it suffers in presence of broadcast data-link-layer networks (such as Ethernet), where any entity has direct access to any other entity on the same data link (shared bus), hence creating a full-mesh set of adjacencies ($N$ nodes → ${\tfrac {N\left(N-1\right)}{2}}$ point-to-point links).

The high number of adjacencies has a severe impact on the LS algorithm:

• computation problems: the convergence of the Dijkstra's algorithm depends on the number of links ($L\cdot \log {N}$), but the number of links explodes on broadcast networks;
• unnecessary overhead when propagating LSs: whenever a router needs to send its LS on the broadcast network, it has to generate $N-1$ LSs, one for every neighbor, even if it would be enough to send it only once over the shared channel to reach all its neighbors, then each neighbor will in turn propagate multiple times the received LS ($\sim N^{2}$);
• unnecessary overhead when bringing up adjacencies: whenever a new router is added to the broadcast network, it has to start $N-1$ bring-up phases, one for every neighbor, even if it would be enough to re-align the database just with one of them.

The solution is to transform the broadcast topology in a star topology, by adding a pseudo-node (NET): the network is considered an active component that will start advertising its adjacencies, becoming the center of a virtual star topology:

• one of the routers is 'promoted' which will be in charge of sending also those additional LSs on behalf of the broadcast network;
• all the other routers advertise an adjacency to that node only.

The virtual star topology is valid only for LS propagation and adjacency bring-up, while normal data traffic still uses the real broadcast topology:

• LS propagation: the generating node sends a LS to the pseudo-node, which sends it to the other nodes ($\sim N$);
• adjacency bring-up: the new node activates a bring-up phase only with the pseudo-node.

Advantages

• fast convergence:
  • LSs are quickly propagated without any intermediate processing;
  • every node has certain information because coming directly from the source;
• short duration of routing loops: they may happen during transient for a limited amount of time;
• debug simplicity: each node has a map of the network, and all nodes have identical databases → it is enough to query a single router to have the full map of the network in case of need;
• good scalability, although it is better not to have large domains (e.g. OSPF suggests not to have more than 200 routers in a single area).