Routing algorithms that constructs a Forwarding Table by having every Router discovering the topology of the network (the network graph) and then computing the Single Source Shortest Path from a source to each router, where “shortest” comes from the edge cost often being a distance measure.
Since it is necessary to have a complete map of the complete network before running the Single Source Shortest Path algorithm the LS algorithm is a Centralised Routing Algorithms.
Discovery
To compute the Single Source Shortest Path we need all link costs as input. These are obtained by having every router broadcasts link-state Packets to all other nodes in the network which contain the identities and costs of its attached links.
Computation
After discovery any node has the same complete information of the network and can run any Single Source Shortest Path algorithm, like Dijkstra’s algorithm, to compute the single source shortest path to any other router, which is the path to use when sending traffic to that router.
Oscillation Problem
The oscillation problem is the problem of routers oscillating between routes indefinitely.
This problem can arise when LS routing algorithms are run on networks where link costs change depending on load carried on the link.
This is because the Single Source Shortest Path computed by each router can become favourable for other router which change their traffic to that route, thus increasing the cost of the route. This in turn makes the routers send traffic along another route, and if they take the same route, then the cost of that route increases. If they keep choosing the same new router, they will keep oscillating between these routes indefinitely.
The solution can be that not all routers compute the LS algorithm at the same time. Researchers have however found that router can self-synchronise through Floyd Synchronisation, so a better solution might be to have each router randomise the time it sends out a link advertisement.
Complexity
Since we require each node to know the cost of each link in the network by having each node broadcast their node costs, we need to send messages.
Afterwards the algorithm needs to compute the Single Source Shortest Path for each node, whose runtime will depend on the algorithm used.
Example
The router take turns sending clockwise and counter-clockwise to avoid the links with large load.
