This write-up is a top level overview of “Link State Protocols”, and why they are preferred, compared to “Distance Vector Protocols”. I have been wondering about this over the last ten years, and the recent surge in articles on IS-IS allowed some thoughts …
Link State Protocols
- Each node (router) keeps track of all (physical) links that it owns
- This state is advertised to the other routers (switches) periodically through a Link State Advertisement (LSA) message.
- The Link State message is flooded to every other router in the network
- Every router therefore has data for every link in the network.
- This data is stored in a database called Link State Database
- From this data, every router computes the shortest path to every network.
- This computation is computationally expensive.Based on this, for every network, the next hop is computed
- The next-hops are stored in a Forwarding Information Base (FIB)
- In the data layer, when a router receives a packet,
- it looks up the next hop, and forwards the packet there.
Comparison to Distance Vector Protocols
Bandwidth to exchange Routing Information
While at an initial glance, it looks like “Link State Protocols” consume excessive bandwidth, because of “Link State Flooding”, a careful analysis shows that
- Distance vector information, also in its steady state, exchanges the route to all the networks from the current node, with all its neighbors
- The link state protocol, also does the same thing. Every network is owned by a router, and that data is passed onto every other router by flooding.
So, the byte quantity of data exchanged is the same.
Type of Information Exchanged
Distance Vector Protocols exchange the immediate “Next Hop” information for each of the networks. The paths to each network are computed and hashed at each hop. Hence, there is not too much computation at each node, but all state is not available at a single node.
Link State protocol carries information of the originating source to all the nodes. Hence all the nodes share the same state of the network. But the results of the “path computation”, to each of the network are not transferred. So, each router needs to compute the paths to each of the network.
Points of differences
|Distance Vector||Link State|
|Neighbor state of network only||Complete network state replicated|
|Routing paths computed and next-hops exchanged||Next hops not computed prior to exchange.|
Faster flooding and Convergence
Since the local state of every router is available to all other routers, certain functions can be done better
Under steady state, it can be mathematically proved that there will be convergence, and no loops. This means that we need not be paranoid about disallowing loops in the short term. This allows us to optimize on other characteristics. We may reduce the overall convergence time by focusing on flooding the network with the state change, rather than defensively putting synchronizing conditions
Better Steady-state rerouting
Also, we would be able to use more sophisticated algorithms, while recomputing paths. We may be able to take into account the RSVP reservations on the paths, and build the next hop table, so that the entire network can satisfy the RSVP request.
Controlled Message Sizes
A message in “Distance Vector Protocols” is proportional to the total number of networks in the system. This may require some kind of “Session Based” data exchange between the adjacent routers, as the number of connected networks grows.
A message in “Link State Protocol” is proportional only to the number of links that a router is connected to. Hence, it fits better into a datagram, and can be transferred by the more efficient transport service.