Sec.5.1 Introduction 371 E Figure 5.9 Illustration of sclective broadcasting using a spanning tree.We assume that each node knows which of the incident spanning tree links lead to any given destination.In this example.node A G wishes to broadcast a packet to nodes C. D.E.and F.Node A sends a copy of the CF packet to each of its incident finks that lead to intended destinations.and each copy carries in its header the ID numbers of its F intended destinations.Upon reception of a copy,a node strips the ID number from the header (if it is an intended destination)and repeats the process.This climinates some unnecessary transmissions.for example the transmission on link EG in the figure. path should contain relatively few and uncongested links,and therefore be desirable for routing. A more sophisticated alternative is to allow the length of each link to change over time and to depend on the prevailing congestion level of the link.Then a shortest path may adapt to temporary overloads and route packets around points of congestion.This idea is simple but also contains some hidden pitfalls,because by making link lengths de- pendent on congestion,we introduce a feedback effect between the routing algorithm and the traffic pattern within the network.It will be seen in Section 5.2.5 that this can result in undesirable oscillations.However,we will ignore this possibility for the time being. An important distributed algorithm for calculating shortest paths to a given desti- nation,known as the Bellman-Ford method,has the form Di:=minldi;+D.l where D:is the estimated shortest distance of node i to the destination and d,,is the length of link (j).Each node i executes periodically this iteration with the minimum taken over all of its neighbors j.Thus dij+D,may be viewed as the estimate of shortest distance from node i to the destination subject to the constraint of going through j,and minjdij+Di]may be viewed as the estimate of shortest distance from i to the destination going through the "best"neighbor. We discuss the Bellman-Ford algorithm in great detail in the next section.where we show that it terminates in a finite number of steps with the correct shortest distances under reasonable assumptions.In practice,the Bellman-Ford iteration can be implemented as an iterative process,that is,as a sequence of communications of the current value of D of nodes j to all their neighbors,followed by execution of the shortest distance estimate updates Di:=min,[d+Di].A remarkable fact is that this process is very flexible with respect to the choice of initial estimates D;and the ordering of communications and updates;it works correctly,finding the shortest distances in a finite number of steps,for an essentially arbitrary choice of initial conditions and for an arbitrary order of communications and updates.This allows an asynchronous,real-time distributed implementation of the Bellman-Ford method,which can tolerate changes of the link lengths as the algorithm executes (see Section 5.2.4).Sec. 5.1 Introduction 371 8 CD--- E / / / / / A G /D " / / " / / " / / " / / " / C CD--- F Figure 5.9 Illustration of selective broadcasting using a spanning tree. We assume that each node knows which of the incident spanning tree links lead to any given destination. In this example. node A. wishes to broadcast a packet to nodes C. D, E, and F. Node A. sends a copy of the packet to each of its incident links that lead to intended destinations, and each copy carries in its header the ID numbers of its intended destinations. Upon reception of a copy, a node strips the lD number from the header (if it is an intended destination) and repeats the process. This eliminates some unnecessary transmissions. for example the transmission on link EO in the figure. path should contain relatively few and uncongested links, and therefore be desirable for routing. A more sophisticated alternative is to allow the length of each link to change over time and to depend on the prevailing congestion level of the link. Then a shortest path may adapt to temporary overloads and route packets around points of congestion. This idea is simple but also contains some hidden pitfalls, because by making link lengths de￾pendent on congestion, we introduce a feedback effect between the routing algorithm and the traffic pattern within the network. It will be seen in Section 5.2.5 that this can result in undesirable oscillations. However, we will ignore this possibility for the time being. An important distributed algorithm for calculating shortest paths to a given desti￾nation, known as the Bellman-Ford method, has the form D i := min[di ] + D]1 ] where Di is the estimated shortest distance of node i to the destination and rilj is the length of link (i, j). Each node i executes periodically this iteration with the minimum taken over all of its neighbors j. Thus di ] + D j may be viewed as the estimate of shortest distance from node i to the destination subject to the constraint of going through j, and minjfdij + D j ] may be viewed as the estimate of shortest distance from i to the destination going through the "best" neighbor. We discuss the Bellman-Ford algorithm in great detail in the next section. where we show that it terminates in a finite number of steps with the correct shortest distances under reasonable assumptions. In practice, the Bellman-Ford iteration can be implemented as an iterative process, that is, as a sequence of communications of the current value of D j of nodes j to all their neighbors, followed by execution of the shortest distance estimate updates D i := minjfdij + D j ]. A remarkable fact is that this process is very flexible with respect to the choice of initial estimates Dj and the ordering of communications and updates; it works correctly, finding the shortest distances in a finite number of steps, for an essentially arbitrary choice of initial conditions and for an arbitrary order of communications and updates. This allows an asynchronous, real-time distributed implementation of the Bellman-Ford method, which can tolerate changes of the link lengths as the algorithm executes (see Section 5.2.4)