3.3 Distance Vector Routing Protocol
3.3.1 Conceptual Framework and Illustration
In Chapter 2, we presented the distance vector routing algorithm (see Algorithm 2.2). It tells us that a node, say nodei, needs to know the distance or cost from its neighbors to a desti- nation, say nodej, to determine the shortest path to nodej. Since nodeican have multiple neighbors, it is preferable to know the distance from all its neighbors to nodejso that nodei can compare and determine the shortest path. The basic information exchange aspect about a distance vector protocol is that a node needs the distance cost information from each of its neighbors for all destinations; this way, it can compare and determine the shortest paths to all destinations. This means that our discussion about a distance vector protocol is strongly
tied to the distance vector routing algorithm (Algorithm 2.2), but keep in mind that it is not necessary to do so in general.
The main operation of a distance vector protocol needs to address dissemination and reception of information. Thus, we start with the basic operation of a distance vector protocol from the point of view of a node as shown in Figure 3.1. We clarify a few aspects about the protocol description:
• The protocol does not need to know ahead of time how many nodes are in the network; in other words, through the information received periodically that may contain a new node information, the receiving node can update the list of destination nodes.
• Actual numbering of a node can be done through some addressing scheme outside the protocol (for example, IP addressing with RIP).
• For each destinationj(from nodei), the protocol maintains/updates the next hop, to be denoted asHij.
• With the arrival of a distance vector message from a neighbork, the protocol updates the cost to a destination if the currently stored next hop for this destination is alsok.
• Steps indicated are not necessarily in any specific order (except for initialization).
• There is possibly a time wait between steps and within substeps of a step.
We will now illustrate the basic working of a distance vector protocol through the six- node network discussed earlier in Chapter 2. We reproduce the topology (along with link cost information) in Figure 3.2 for ease of reference. Since we do not consider time-dependent distance cost, we will ignore time parametert, i.e., we will usedik andDij, instead ofdik(t) andDij(t), respectively. Recall thatdik refers to the link cost on the linki-kconnecting node i to node k, while Dij refers to the cost between node i and j. Consider that node 1 wants to compute the shortest paths to all its destinations. It needs to receive cost information from its neighbor nodes 2 and 4. Assuming for now that node 2 knows the best information (somehow), it is easy to see that node 2 needs to transmit the following protocol message to node 1:
D21=1 D22=0 D23=2 D24=1 D25=3 D26=3
Note that the first subscript with D is the node generating this distance vector infor- mation (2 in this case), while the second subscript indicates the destination for which this distance cost is provided. Since the first subscript is common, it can be ignored as long as the receiving node knows who it is coming from. The second subscript is the most relevant iden- tifier that indicates the destination. Obviously, a routing protocol exchange message cannot understand or indicate a subscript as we can do with a notation in describing the protocol!
Thus, the message format, shown above, looks more like the following where the destination jis identified first with a node number followed by the distance costD, which is repeated for everyj:
j=1,D=1 j=2,D=0 j=3,D=2 j=4,D=1 j=5,D=3 j=6,D=3
Initialize:
– Node is configured with a unique node ID, sayi – Nodei’s distance vector to itself is set to zero, i.e.,Dii=0
– Initialize module that determines the link cost to its directly connected neighbor (either manually or based on measurements), i.e.,dikfor all neighborsk, and set the routing table entry to indicate the next hop fork askitself, i.e.,Hik=k
Transmit mode:
– Transmit the most recently computed cost (distance) for all known destination nodes to all its neighborsk on a periodic basis
Receive mode:
– Nodeireceives a distance vector from its neighbork
a. If the distance vector contains a new destination nodej, then a new node entry in the routing table is created and setDij= ∞
b. The distance vectorDikjfor each destination nodejreceived from neighborkat nodeiis temporarily stored
c. If the currently stored next hop for a destinationjis the same askitself, then update the distance cost for this destination, i.e.,
If (Hij=k) then // if next hop isk Dij=dik+Dikj
Endif
– Route Computation
For each destinationj: // shortest path computation For all neighborsk(or, the last received neighbork)
Computetemp=dik+Dikj If (temp<Dij) then
Dij=temp // update the new cost
Hij=k // update next hop in the routing table Endif
Special Cases:
– If for any neighbork, linki-kgoes down, then Setdik= ∞
IfHij=k, thenDij= ∞
Broadcast a distance vector to each neighbor Endif
– If for any neighbork, linki-kis up again, then Updatedik(fixed or dynamic)
Broadcast a distance vector to each neighbor Endif
F I G U R E 3.1 Distance vector protocol (nodei’s view): basic framework.
Based on the above message information, we can also see that the term distance vector then refers to the vector of distance or direction. This is communicated through the above message to a neighbor so that the neighbor can determine its best distance to a destination.
While it looks odd to include information about cost to node 1 itself in such a message, this is indeed the case in the basic or nạve distance vector protocol since node 2 does not dif- ferentiate who its neighbors are when disseminating such information. Upon receiving this information, node 1 will add its cost to this neighbor (1 in this case) for each destination sep- arately to compare and determine the best cost to every destination. Assuming that until this instant, node 1 does not know the cost to any destination (except itself), it will then compare and update the cost (see Eq. (2.2.4b) in Chapter 2) really for itself resulting in no improve-
ment; it also computes cost to all other destinations based on the information received and creates entries in its routing table, and tracks the outgoing link identifier. Thus, the routing table at node 1 is as given in Table 3.1.
Now compare Table 3.1 and the topology given in Figure 3.2; it is clear that for node 4 as destination, the entry is not optimal. This means that at this point, to route to node 4, node 1 will send to node 2 hoping that node 2 knows how to get to node 4. In fact, the routing table will stay in the above form as long as node 1 does not hear updated distance vector information from node 4 directly (to which it is also connected). In other words, a node actually never knows if it has the optimal cost as well as the best outgoing link identified for each destination (i.e., it is only the network administrator who can do optimal route analysis based on measurements). A node assumes that its neighbor is giving the correct distance vector information all the time. Furthermore, a node may or may not know if it has the view of the entire list of active nodes.
Now suppose that sometime after the above update, node 1 receives a distance vector from node 4 as given below:
j=1,D=1 j=2,D=1 j=3,D=1 j=4,D=0 j=5,D=2 j=6,D=2
F I G U R E 3.2 Six-node, ten-link network example (the entry shown next to a link is the cost of the link).
TA B L E 3.1 Routing table information at node 1 (after receiving distance vector from node 2).
Destination Node Cost Outgoing Link
1 0 local
2 1 1-2
3 3 1-2
4 2 1-2
5 4 1-2
6 4 1-2
Upon receiving this information, node 1 performs an updated computation as shown in Ta- ble 3.2. You may note that this computation, marked as action-6 in Figure 3.1, is the same as Eq. (2.2.4b) in Algorithm 2.2; here,d14(t)=1, and node 1 receivesD4j(t),j=1,2, . . . ,6as the distance vector message described above. The basic difference in the computation is that while the Bellman–Ford algorithm does not explicitly state that the outgoing link should be tracked, a distance vector routing protocol usually tracks this information for the purpose of creating/updating the routing table.
While it may not be apparent from the discussion so far, we learn the following lessons in regard to how timing (and timers) influences a routing protocol (see also Figure 3.3):
• The order of information as received matters: In the example discussed so far, we started by assuming that node 1 receives a distance vector from node 2 first before receiving a distance vector from node 4. Had node 1 received a distance vector from node 4 first, the entire routing table in the first round would have been different.
• How often the distance vector information is disseminated matters: Assume for the sake of ar- gument that a distance vector is disseminated by node 2 every minute while node 4 does it every 10 min. Clearly, this would make a difference to node 1 in terms of how quickly it would be able to arrive at the best routing table.
• The instant when a node broadcasts the distance vector (after an event) matters: It is important to distinguish this item from the previous item. While the previous item discusses periodicity of the update interval, this one refers to whether a node should trigger an immediate update after a major event such as a failure of a link connected to it.
• The instant when a routing computation is performed matters: Suppose a node receives a dis- tance vector from a neighbor every 2 min while it performs the route computation every 3 min. Certainly, these update cycles have an impact on obtaining the best route in a timely manner.
TA B L E 3.2 Cost and routing able updating at node 1 (after receiving distance vector from node 4).
Destination Current New Possible Updated Cost Update Outgoing
Node Cost Cost (Update?) Link (If Any)
1 0 1 + 1 0 (No) local
2 1 1 + 1 1 (No) 1-2
3 3 1 + 1 2 (Yes) 1-4
4 2 1 + 0 1 (Yes) 1-4
5 4 1 + 2 3 (Yes) 1-4
6 4 1 + 2 3 (Yes) 1-4
F I G U R E 3.3 Time line of different activities at two different nodes.
• The instant when the routing table is updated matters: Suppose a node waits another 30 sec af- ter performing a route computation before updating the routing table. This would impact the flow of user data.
An important corollary of the above discussion is that time (and timers) matter when it comes to a routing protocol, and that a routing environment encounters a transient period during which different nodes may have different views of the network; this is the root cause of many undesirable problems, which are discussed next. While common sense indicates that extended gaps between events as highlighted in Figure 3.3 are probably not necessary, it is important to understand what can happen if they do exist. This is explored in the next section.