0:00
In the previous lesson,
we learned the shortest distance to routing based on distance vector.
Today, we discuss its problems in a study,
The Shortest Distance Routing Based on Link State.
In distance vector approach,
the changes in routing table should trigger a router to broadcast
the minimum cost to its neighbors to speed up its convergence.
However, the problem is that the approach is very slow for values.
Consider the topology shown in the figure,
with the router four be the destination.
Suppose after the distance vector approach stabilize,
link three four breaks.
There is need to recompute the minimal cost from each node to the destination node.
The table shows the computation process of minimal cost.
And it shows each node keeps updating its cost in increment of two units.
At each update, node two thinks that
its the shortest path to the destination is through node three.
Likewise, node three thinks that
its the shortest path to the destination is through node two.
As a result, a packet in either of
these two nodes bounce back and forth until the process stop updating.
The process keeps iterating until the minimal cost is infinite at
which point the process realize that the destination node is unreachable.
This is often called count-to-infinity Problem.
To avoid it, several changes to the distance vector algorithm have
been proposed but none of them work well in all situations.
One method that was widely implemented is called
the Split Horizon in which the minimum cost to
a given destination is not sent to
the neighbor if the neighbor is the next node along the shortest path.
Another variation is called a Split Horizon with
Poisoned Reverse which allows a node to send the minimal costs to all its neighbor.
But the minimal cost to a given destination is set to infinity,
if the neighbor is the next node along the shortest path.
Let's have an example on how Split Horizon with Poisoned Reverse works.
We consider same topology with a destination node four.
After link three to four breaks,
node two advertise its route to four to node three as having distance infinity.
Node three finds there is no router to node four.
And therefore its distance vector becomes an active one, infinity.
In the second update,
node one advertise its route to four to node two as having distant infinity.
Node two finds there is no route to four.
In the set update,
node one finds there is no route to node four.
In total three updates.
All three nodes find the destination node is unreachable.
So this reverse approach can break [inaudible] direct loops immediately.
The essential problem of distance vector routing is that
the information is only exchanged with local neighbors.
The link-state algorithm seeks global optimization.
The basic idea involves three steps.
First, each source node creates a link state packet of local to neighbor link metrics.
Then, each source node broadcasts the link-state packet,
so that each source node gets a map of all nodes and link metrics of the entire network.
Finally, apply an algorithm to find the shortest path
on the map from the source node to all destination nodes.
The Link state packet contains the identifier of
its neighbors as well as the distance to its links.
The broadcast of link-state packets can be done by flooding.
Recall the disadvantage of flooding.
To limit scale of flooding,
one can add source node identifier,
sequence number and time to leave so as to remove duplicates.
Here is an example of link-state packet.
Consider a network topology with six nodes as shown in the figure.
Each node contains its own identifier,
the sequence number, the time to leave,
neighbors' identifiers and distance.
One question you may have is when to build links data packets.
A quick answer is,
periodically or when significant events occur such as system reboot.
Once the global view of the network is constructed each node,
the last step is to apply an algorithm to find
the shortest path from the source node to all destination nodes.
The algorithm often used is called Digester
algorithm which we will discuss in details in the next class.
Xiaobo ZhouProfessor, Interim Dean
