(Transient loops under Dijkstra’s algorithm) In Dijkstra’s algorithm, nodes need to have consistent knowledge of link costs. Otherwise, packets may not be correctly routed to their destinations. For example, when the cost of a link changes, but the change is not known by all the nodes in the network, transient loops may occur. Consider the network in Figure 7.10, where nodes a and b know the failure of link ab, but nodes c, d, and e do not. Use Dijkstra’s algorithm to construct routing tables at each node, and then show that packets from e to a will loop between nodes b and e.

 

b          1          c

1

 

 

a                       10

15

e

 

15        2

1          d

 

 

Figure 7.10 Nodes a and b know the failures of link ab, but nodes c, d, and e do not.