The Bellman–Ford algorithm uses a simple idea to compute the shortest path between two nodes in a centralized fashion. In a distributed environment, a distance vector approach is taken to compute shortest paths. In this section, we will discuss both the centralized and the distributed approaches.
2.2.1 Centralized View: Bellman–Ford Algorithm
To discuss the centralized version of the Bellman–Ford algorithm, we will use two generic nodes, labeled as nodeiand nodej, in a network ofNnodes. They may be directly connected as a link such as link 4-6 with end nodes 4 and 6 (see Figure 2.1). As can be seen from Fig- ure 2.1, many nodes are not directly connected, for example, nodes 1 and 6; in this case, to find the distance between these two nodes, we need to resort to using other nodes and links.
This brings us to an important point; we may have the notion of cost between two nodes, irrespective of whether they are directly connected or not. Thus, we introduce two important notations:
dij=Link cost between nodesiandj
Dij=Cost of the computed minimum cost path from nodeito nodej.
Since we are dealing with different algorithms, we will use overbars, underscores, and hats in our notations to help distinguish the computation for different classes of algorithms.
For example, overbars are used for all distance computation related to the Bellman–Ford algorithm and its variants. Note that these and other notations used throughout this chapter are summarized later in Table 2.5.
If two nodes are directly connected, then the link costdij takes a finite value. Consider again Figure 2.1. Here, nodes 4 and 6 are directly connected with link cost 15; thus, we can writed46=15. On the other hand, nodes 1 and 6 are not directly connected; thus,d16= ∞.
What then is the difference betweendijand the minimum costDij? From nodes 4 to 6, we see that the minimum cost is actually 2, which takes path 4-3-6; that is,D46=2whiled46=15.
For nodes 1 and 6, we find that D16=3 while d16= ∞. As can be seen, a minimum cost path can be obtained between two nodes in a network regardless of whether they are directly
F I G U R E 2.2 Centralized Bellman–Ford Algorithm (solid line denotes a direct link;
dashed line denotes distance).
connected or not, as long as one of the end nodes is not completely isolated from the rest of the network.
The question now is how to compute the minimum cost between two nodes in a network.
This is where shortest path algorithms come in. To discuss such an algorithm, it is clear from the six-node example that we also need to rely on intermediate nodes. For that, consider a generic node k in the network that is directly connected to either of the end nodes; we assume thatkis directly connected to the destination nodej, meaningdkj has a finite value.
The following equations, known as Bellman’s equations, must be satisfied by the shortest path from nodeito nodej:
Dii=0, for alli, (2.2.1a)
Dij=min
k=j
Dik+dkj
, fori=j. (2.2.1b)
Simply put, Eq. (2.2.1b) states that for a pair of nodesiandj, the minimum cost is de- pendent on knowing the minimum cost fromi tokand the direct link costdkj for linkk-j.
A visual is shown in Figure 2.2. Note that there can be multiple nodeskthat can be directly connected to the end nodej(say they are markedk,k2, and so on; note thatk=iis not ruled out either); thus, we need to consider all suchks to ensure that we can compute the minimum cost. It is important to note that technically, a nodekthat is not directly connected tojis also considered; since for suchk, we have dkj = ∞, the resulting minimum computation is not impacted. On close examination, note that Eq. (2.2.1b) assumes that we know the minimum cost,Dik, from nodeitokfirst somehow! Thus, in an actual algorithmic operation, a slight variation of Eq. (2.2.1b) is used where the minimum cost is accounted for by iterating through the number of hops. Specifically, we define the term for the minimum cost in terms of number
of hopshas follows:
D(h)ij = cost of the minimum cost path from nodeito nodejwhen up toh number of hops are considered.
The Bellman–Ford algorithm that iterates in terms of number of hops is given in Algo- rithm 2.1. Note the use of(h)in the superscript in Eq. (2.2.2c); while the expression on the right side is up tohhops, with the consideration of one more hop, the expression on the left hand side is now given inh+1hops.
A L G O R I T H M 2.1 Bellman–Ford centralized algorithm.
Initialize for nodesiandjin the network:
D(0)ii =0, for alli; D(0)ij = ∞, fori=j. (2.2.2a) Forh=0toN−1do
D(hii+1)=0, for alli (2.2.2b)
D(hij+1)=min
k=j
D(h)ik +dkj
, fori=j. (2.2.2c)
For the six-node network (Figure 2.1), the Bellman–Ford algorithm is illustrated in Ta- ble 2.1. A nice way to understand the hop-iterated Bellman–Ford approach is to visualize through an example. Consider finding the shortest path from node 1 to node 6 as the num- ber of hops increases. Whenh=1, it means considering a direct link path between 1 and 6;
since there is none,D(1)16 = ∞. Withh=2, the path 1-4-6 is the only one possible since this is a two-link path, i.e., it uses two hops, consisting of the links 1-4 and 4-6; in this case, the hop-iterated minimum cost is 16 (=D(2)16). Ath=3, we can write the Bellman–Ford step as follows (shown only forkfor whichdk6<∞) since there are three possible paths that need to be considered:
k=3: D(2)13 +d36=2+1=3 k=5: D(2)15 +d56=3+1=4 k=4: D(2)14 +d46=1+15=16.
In this case, we pick the first one since the minimum cost is 3, i.e.,D(3)16 =3with the short- est path 1-4-3-6. It is important to note that the Bellman–Ford algorithm computes only the minimum cost; it does not track the actual shortest path. We have included the shortest path in Table 2.1 for ease of understanding how the algorithm works. For many networking en- vironments, it is not necessary to know the entire path; just knowing the next node k for which the cost is minimum is sufficient—this can be easily tracked with theminoperation in Eq. (2.2.2c).
TA B L E 2.1 Minimum cost from node1to other nodes using Algorithm 2.1.
h D(h)12 Path D(h)13 Path D(h)14 Path D(h)15 Path D(h)16 Path
0 ∞ – ∞ – ∞ – ∞ – ∞ –
1 1 1-2 ∞ – 1 1-4 ∞ – ∞ –
2 1 1-2 2 1-4-3 1 1-4 3 1-4-5 16 1-4-6
3 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
4 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
5 1 1-2 2 1-4-3 1 1-4 3 1-4-5 3 1-4-3-6
2.2.2 Distributed View: A Distance Vector Approach
In a computer network, nodes need to work in a distributed fashion in determining the short- est paths to a destination. If we look closely at the centralized version discussed above, we note that a source node needs to know the cost of the shortest path to all nodes immediately prior to the destination, i.e.,D(h)ik , so that the minimum cost to the destination can be com- puted; this is the essence of Eq. (2.2.2c), communicated through Figure 2.2. This view of the centralized Bellman–Ford algorithm is not directly suitable for a distributed environment. On the other hand, we can consider an important rearrangement in the minimum cost computa- tion to change the view. That is, what if we change the order of consideration in Eq. (2.2.1b) and instead use the minimum cost computation step as follows:
Dij=min
k=i
dik+Dkj
, fori=j. (2.2.3)
Note the subtle, yet distinctive difference between Eq. (2.2.1b) and Eq. (2.2.3); here, we first look at the outgoing link out of nodeito a directly connected nodekwith link costdik, and then consider the minimum costDkj from k toj without knowing how kdetermined this value. The list of directly connected nodes ofi, i.e., neighbors of i, will be denoted by Ni. In essence, what we are saying is that if nodei finds out from its neighbor the cost of the minimum cost path to a destination, it can then use this information to determine cost to the destination by adding the outgoing link costdik; this notion is known as the distance vector ap- proach, first applied to the original ARPANET routing. With this approach, the computational step Eq. (2.2.3) has a nice advantage in that it helps in building a computational model for a distributed environment.
We illustrate the change of order and its advantage for the distributed environment using Figure 2.3. Suppose that nodeiperiodically receives the minimum cost informationDkjfrom its neighboring nodekfor nodek’s minimum cost to nodej; this variation can be addressed by introducing the dependency on the time domain,t, usingDkj(t)for nodek’s cost toj—this will then be available to nodei(compare this expression to hop-basedD(h)kj ). Now, imagine for whatever reason that nodek recomputes its cost tojand makes it available to another source node, sayi2, but not to nodeias shown in Figure 2.3. In other words, from the view of the source nodei, the best we can say is that the minimum cost value from nodekto node jthat is available to nodeiis as nodeihas been able to receive; that is, it is more appropriate to use the termDikj(t)thanDkj(t)to indicate that the minimum cost from nodekto nodej, as
F I G U R E 2.3 Distance vector view for computing the shortest path.
available to source nodeiat timet; to distinguish, the cost availability toi2can be written as Dikj2(t)sincei2may receive at a different time instantt. Furthermore, in a dynamic network, the direct link costdik from nodei tokcan also change with timet, for example, to reflect change in network load/traffic. Thus, we can generalize the direct link cost to write asdik(t) to indicate dependency on timet. With these changes, we present the distributed distance vector approach in Algorithm 2.2.
A L G O R I T H M 2.2 Distance vector algorithm (computed at nodei).
Initialize
Dii(t)=0; Dij(t)= ∞, (for nodejthat nodeiis aware of). (2.2.4a) For (nodesjthat nodeiis aware of) do
Dij(t)= min
kdirectly connected toi
dik(t)+Dikj(t)
, forj=i. (2.2.4b)
We will now illustrate the distributed variation. For simplicity, we will assume that node k, which is directly connected to nodei, is sendingDikj(t)at the same instant to other directly connected nodes likei. Furthermore, we will assume that the direct link cost does not change with time, i.e.,dik(t)does not change with time.
Our illustration will consider the same six-node example by considering computing the shortest path cost from node 1 to node 6 (see Table 2.2). This time, we will interpret the hop-based cost computation in terms of discrete time windows; for example,t=0 means what node4sees about cost to node6when zero hops away,t=1means what node4sees about cost to node6when information from one hop away is received, and so on. Note that node 1 is directly connected to node 2 and node 4. Thus, node 1 will have D126(t), the cost between node 2 and node 6 from node 2, and D146(t), the cost between node 4 and node 6 from node 4.
To summarize, in the distance vector approach, a node relies on its neighboring nodes’
known cost to a destination to determine its best path. To do so, it does periodic computa- tion as and when it receives information from its neighbor. For this entire process to work,
TA B L E 2.2 Distance vector based distributed computation at timetfrom node 1 to node 6.
Time,t D146(t) D126(t) Computation at node1 D16(t) min{d14(t)+D146(t),d12(t)+D126(t)}
0 ∞ ∞ min{1+ ∞,1+ ∞} ∞
1 15 ∞ min{1+15,1+ ∞} 16
2 2 3 min{1+2,1+3} 3
the key idea is that a node k needs to distribute its cost to j given by Dkj(t)to all its di- rectly connected neighbor i—the dependency on i and t means that each node i may get such information potentially at a different time instant t. The difference between this idea and the centralized Bellman–Ford algorithm is subtle in that the order of computation along with the link considered in computation leads to different views to computing the shortest path.