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.

Â