Link state

Link-state routing [LS] is a packet switching protocol for computer communications.

In LS every router constructs a map over which nodes they are directly connected to. Each router independently calculates the best path from it to all other possible nodes. A routing table is then built from the collection of best paths.

The large difference between LS and distance-vector routing is that distance-vector protocols shares its entire routing table while each node in LS only shares which neighbors it has. [WIKI]

In a LS network each router knows the entire network topology and independently calculates the best next hop to any other destination.

Distributing maps

1. Determining neighbors of nodes - Each nodes checks which ports it is connected to and if the links work it does it using reachability protocols which runs separately on each node.
2. Information distributing - Each node later periodically sends a link-state advertisement which includes:
   1. The current node
   2. All the current nodes direct neighbors
   3. A sequence number which denominates which version of this nodes advertisement this is.
3. Message transmission - When the message is constructed it is sent to all other nodes on the network trough broadcast. Each node which receives a message remembers the latest sequence number from each one of its neighbors, the sequence number - neighbor relations are important.
4. Receiving messages - When a message is gotten its sequence number is checked against the previously gotten sequence numbers from that specific neighbor. If the message has a higher number (newer) , it is saved and a copy of that message with an updated sequence number is sent to all neighbor.

This combination of operations quickly gets each node a new version of the network.

Creating the map

When each node has a complete set of link-state advertisements (one per node in the network) all nodes create an individual version of the whole network.

The list of advertisements is iterated over and for each one new links are created (to the current advertisements sender to any of its neighbors not present in the map)

To avoid errors no link is trusted if only one advertisement reports it (each node shall have two reports as each end sends a report).

Calculating a routing table

The calculation is done in several steps described below.

Calculating shortest paths

Each node independently use an algorithm to find the shortest path from itself to every other node, a modified version Dijkstra's algorithm is often used to build these tables. The paths are weighted by link costs which include bandwidth and additional variables.

The algorithm (Dijkstra)

Each node maintains two different data structures:

• A tree containing nodes which are "done".
• A list containing candidates.

At the start both structures are empty and then starts with adding itself to the tree. Some variant of a greedy algorithm then repeatedly does the following:

1. All neighboring nodes (not present in the candidate list) to the current node are added to the tree. All others are added to the candidate list (Is This Done First?).
2. Each candidate node is compared to the nodes in the tree. The closest candidate to any node in the tree is moved into the tree attached to its neighbors already in the tree. (Each moved candidate is removed from the candidate list)

The greedy algorithm continues until no candidates are left as all will be added to the tree.

Filling the routing table

For any given destination node, the best path for said destination is the first step (step on shortest path) from the root to the destination. To create the routing table one walks the tree and fills the routing table with each node - next hop - destination entry it finds. In the end each node holds the next hop for each node to any other node in the network.

Optimizing the algorithm

In real world examples more optimized versions of link-state are used, some of the optimizations used are:

Partial re-computation

When a change in the network is detected a recomputation of the shortest path tree and then also the table is needed. To optimize this process a solution has been found to only recalculate the changed portion of the tree and the routing table is also built as the tree is built to improve efficiency.

Topology reduction

Some systems only send one advertisement per edge where it is possible, a example is a node-(another node with only past node as neighbor). This slightly decreases the safety of the system but increases performance.