3.3 Distance Vector Routing Protocol
3.3.5 Distance Vector Protocol Based on Diffusing Computation with Coordinated Update
The most well-known scheme that accomplishes loop-free routing in a distance vector proto- col framework is the diffusing computation with coordinated update approach [244], [245],
that incorporates the concept of diffusing computation [179] and the coordinated update ap- proach [336]; this approach has been implemented in Enhanced Interior Gateway Routing Protocol (EIGRP) (see Section 5.6) and is known as the Diffusing Update Algorithm (DUAL).
To identify that this approach is still built on the notion of a distance vector protocol frame- work, we will refer to this approach simply as the loop-free distance vector protocol, while we will refer to the original distance vector protocol discussed earlier as the basic distance vector protocol.
We start with three important assumptions for the loop-free approach: (1) within a finite time, a node must be able to determine the existence of a new neighbor or if the connectivity to a neighbor is lost, (2) distance vector updates are performed reliably, and (3) message events are processed one at a time, be it an update or a link failure message or a message about new neighbors being discovered.
It may be noted that the basic distance vector protocol does not explicitly address the first assumption. This assumption helps to build adjacency with neighbors in a finite time and is now a common feature in other, more recent routing protocols as well. The second as- sumption was also not addressed in the basic distance vector protocol—we have noted earlier that the lack of this functionality heavily affects convergence time and in the determination of whether a link has gone down. The third assumption is specifically about workings of diffusing computation with coordinated update.
The basic distance vector protocol has only a single message type, which is the dis- tance vector update. However, the loop-free approach has multiple different message types:
(1) hello—used in neighbor discovery, (2) ack—acknowledgment of a hello message, (3) up- date—for distance vector update, (4) query—for querying a neighbor for specific information, and (5) reply—for response to a query. Given the first assumption, you can clearly see the need for hello/ack messages. In the case of the loop-free distance vector (DV) protocol, up- date messages are not periodic, unlike the basic distance vector protocol, and can contain partial information. Query reply messages help in accomplishing loop-free routing and are used for coordination. This is also a good time to bring up information push and informa- tion pull in regard to protocol exchanges, as discussed earlier in Section 3.1. While the basic distance vector protocol operates in an information push mode, the loop-free distance vector protocol employs both the push mode for updates and the pull mode when hello or query are generated.
To execute the loop-free distance vector protocol, each nodei maintains the following information:
• A list of neighboring/adjacent nodes, represented byNi.
• A network node table that includes every nodejin the network along with the following information:
– Lowest feasible distance to nodej(represented asDij).
– A list of feasible next hopsk—this means that a sublist (Nij) of neighbors,Ni, for which the distance from such a neighbor (as known toi) is smaller than its own distance toj;
this means thatDikj<Dij.
– Feasible next hop’s advertised distance (i.e.,Dikjfork∈Nij).
F I G U R E 3.5 Six-node, nine-link network example.
– Distance through all feasible neighbors (“working distance”) determined asDij=dik+ Dikjfork∈Nij.
– Active or passive states (more discussion later).
• A routing table that contains the next hop,Hij, for whichihas the lowest feasible distance for nodej. If there are multiple next hops that have the same lowest feasible distance, then they are all entered in the routing table. There are two benefits to having suchentries in the routing table: (1) user traffic can be distributed among equal cost paths, and (2) if one link goes down, then there is a second one readily available to carry user traffic.
Given the information maintained by nodei, it can generate a distance vector message that has the following components:
Destination Node, Message Type, Next Hop, Distance
It is important to note that in loop-free distance vector protocol, distance vector updates are not periodic and also need not contain the distance for all destinations; furthermore, through message type, it can be indicated whether a message is an update message or other- wise.
Example 3.1 Illustration of a network node table and message type.
Consider the six-node network that we have discussed earlier; this time with link 4-6 deleted; the new topology is shown in Figure 3.5.
Here, we will consider node 5’s view; thus, i=5. It has three neighboring nodes 3, 4, and 6. Thus,N5= {3,4,6}. We will illustrate the node table and routing table for destination node 6. The shortest distance for node 5 to reach node 6 is the direct link 5-6 with cost 1. Thus, the lowest feasible distance isD56=1. Consider the distance cost of its other neighbors to node 6; we see thatD536=1andD546=2, and that none is lower than its distance (D56=1) to node 6, except node 6 itself. Thus, the only feasible next hop is node 6 itself; thus,N56= {6}.
It also stores feasible next hop’s advertised distance, i.e.,D566=0, and its current distance through them, i.e.,D˜56=d56+D566=1. Certainly, there is no difference here between this and the lowest feasible distance since there is only one feasible next hop for destination node 6.
The next hop in the routing table for destination node 6 has one entry:H56=6.
The node table and routing table for all destinations are summarized below:
Network node table at nodei=5
Destination Distance Feasible Next Hop Advertised Working Distance State:
j D5j k∈N5j Distance,D5kj D5j=d5k+D5kj Active (1)/Passive (0)
1 3 4 1 3 0
2 3 3, 4 2, 1 3, 3 0
3 1 3 0 1 0
4 2 4, 3 0, 1 2, 2 0
5 0 5 0 0 0
6 1 6 0 1 0
Routing table at Nodei=5:
Destination,j Next Hop,Hij
1 3
2 3, 4
3 3
4 4, 3
5 0
6 6
A distance vector update message generated at node 5 in regard to destination node 6 will be in the following form j=6, Update, 6, 1 . For brevity, we will write this as 6, U, 6, 1 , where U stands for update (similarly, Q stands for query, R for reply, and so on).
Now consider the operation of the loop-free distance vector protocol. Recall that in the case of the basic distance vector protocol, a node does route computation using distributed Bellman–Ford and then updates the routing table. In the case of the loop-free distance vec- tor protocol, route computation is a bit different depending on the situation; furthermore, there are three additional aspects that need to be addressed: building of the neighbor table, node discovery and creating entry in the network node table, and coordination activity when link cost changes or link fails. Building of the neighbor table typically occurs when a node is first activated; this is where hello messages are sent to neighbor—once an ack message is re- ceived in response, the neighbor relationship is set up. It is important to note that hello is also periodically transmitted to determine/maintain availability and connectivity to a neighbor- ing node. Typically, node discovery occurs immediately after the initial hello message when the neighboring node sends a distance vector update to the newly activated node. Since the newly activated node may be connected to multiple nodes, it will do such an exchange with each of the neighbors; furthermore, it will do its own route computation and send an update message to its neighbors. For message exchange once a node is activated, there is a series of exchanges involved (see Figure 3.6).
F I G U R E 3.6 Protocol message exchanges when a node is activated.
A node performs various tasks depending on an event; primarily, a node provides up- dates under normal situations and coordinates activities when an event such as a link going down occurs. To do that, a node is required to maintain two states: passive (0) and active (1).
When it is passive, it can receive or send normal distance vector updates. A node moves to an active state for a specific destination when, for example, a link failure occurs. When it is in an active state, node table entries are frozen. Note that when it is in an active state, a node gen- erates the request message instead of the update message and keeps track of which requests are outstanding; it moves to the passive state when responses to all outstanding requests are received. It may be noted that a request may be forwarded if the receiving node does not have an answer (in this case, a feasible next hop). In Figure 3.7, we show two different instances of how request response messages are handled. Finally, in Figure 3.8, we present the loop-free distance vector protocol in a compact manner.
It is possible that one or more events occur before the completion of exchanges during an active state. For example, a link goes down; before the coordination phase is completely done, the link comes back up again. While it is possible to handle multiple events and computations through diffusing computation (for example, see [245]), it can be essentially restricted to just one event handling at a time by enforcing a holddown timer; we have discussed the notion of a holddown timer earlier in this chapter. That is, when a link cost changes or link failure event occurs, a holddown timer is started; another link status change event for the same link is not permitted to be communicated through the network until the first holddown timer expires. If the duration of the holddown timer is chosen properly, the coordination phase for a single event can be completed. In general, the holddown timer makes the state maintenance
F I G U R E 3.7 Request/response handling in a loop-free distance vector protocol.
mechanism much simpler compared to when multiple events are needed to be taken care of simultaneously.
In the following, we illustrate how a link failure is handled by the loop-free distance vector protocol.
Initialization:
– Nodeiinitializes itself in a passive state with an infinite distance for all its known neighbors and zero distance to itself
– Initiate hello protocol with neighborkand update valuedik
– Receive update message from all neighborsk, and update node and routing table Nodeiin passive mode:
– Nodeidetects change in a link cost/status to neighborkthat changesDijfor somej If (this is due to link failure) thendik= ∞,Dikj= ∞
– Check for a feasible next hop already in the node table (i.e., a neighborkin the node table that satisfied Dkj<Dijprior to the link status change)
– If ( Nodeifinds one or more feasible next hops,k∈Nij) then // initiate local computation (much like D-BF)
If ( there is a feasibleksuch thatdik+Dkj<di,H
ij+DiH
i,j,j, that is, cost through thiskis better than the current next hopHij) then
Setkas the new next hop, i.e.,Hij=k If (DiHi,j,j<Dij) thenDij=DiH
i,j,j Send update,Dij, to all its neighbors Endif
– If ( Nodeicannot find a feasible next hop ) then
SetDij=Dij=dih+Dihjwherehis the current next hop for nodej Set feasible distance toDihj
// initiate diffusing computation
Change state to nodejto active state, freeze any change for destinationj, and set action flag to 1 Send query to all neighborsk∈Ni
Endif
Nodeiin receiving mode:
Nodeiin passive mode:
Receive update message:
Update node table, determine new next hop, routing table, and update message Receive Query:
If ( feasible next hop exists ) respond withDij If (Dijchanges ) send update to neighbors If ( no feasible next hop exists )
change to active mode,R=1and send query to other neighbors Nodeiin active mode:
If ( response received from neighborskto all queries ) then Change to passive mode (R=0)
ResetDij
Update node table, determine new next hop, update routing table Endif
F I G U R E 3.8 Loop-free distance vector protocol based on diffusing computation with coordinated update (nodei’s view).
Example 3.2 Link failure handling in the loop-free distance vector protocol.
We continue with Example 3.1 to illustrate the link failure case. Consider that the net- work has converged as illustrated earlier in Example 3.1 and all nodes are in passive states.
We will consider only part of the information from the node table just for destination node 6:
specifically(D,D,passive/active status), i.e., distance, working distance, and state. This in-
F I G U R E 3.9 Coordination activities in the loop-free distance vector protocol.
formation is shown in Figure 3.9 at each node for destination node 6. For example, at node 5, for destination node 6, we have(D,D,passive/active status)=(1,1,0).
Now suppose that link 5-6 goes down; it will be marked as the active state and node 5 will change the entry in the node table for node 6 from (1, 1, 0) to(∞,∞,1). It will then generate the query message 6, Q, –,∞ to be sent to the other two outgoing links, 5-3 and 5-4. To keep track of outstanding requests, the following will be set for requested tracking parameters:
R536=1(i.e., node 5 querying node 3 in regard to node 6) andR546=1(i.e., node 5 querying node 4 in regard to node 6). On receiving the query message from node 5 at node 3, it will check to see if it has a feasible next hop to node 6. In this case, it does. Thus, it will generate the following response message 6, R, 6, 1 to node 5. Similarly, node 4 will generate a response message to node 5 as follows: 6, R, 3, 2. Note that node 5 has to receive response messages to both its outstanding requests to move from the active state to the passive state. Once it does, it performs a computation for the node table and generates a new shortest path to destination
node 6.
As you can see, the loop-free distance vector protocol resolves the looping problem faced due to a link-failure in the basic distance vector protocol. A general question (with any proto- col): are there any limitations? Below, we discuss two possible problematic scenarios for the loop-free distance vector approach:
• In some situations, the loop-free distance vector protocol requires quite a bit of coordi- nation between neighboring nodes, thus creating a chatty mode. A general problem with
such a chatty protocol is that it can consume a significant percentage of the bandwidth if the link between two neighboring nodes is a low-speed link, thus affecting performance for user traffic.
• Recall that a holddown timer is started in this protocol once a node moves to the active state; before the holddown timer expires, the node is supposed to hear responses back about a query. However, under an unrelated multi-event situation, it is possible that the time expires before the situation is resolved; this is known as the stuck in active (SIA) con- dition. For example, a node, say A, loses a link to a neighboring node B that happens to isolate the network into two networks. Node A would not realize the isolation of the overall network; it will query its other neighbors, say C and D, about determining a path to node B. In turn, nodes C and D will inquire of its neighbors about any path to node B and change to the active state. Now, assume that there is a congestion problem between node D and its neighboring node E that delays getting a response back. In the meantime, the timer at node A expires, thus resulting in the SIA condition at node A. In general, this is a difficult problem to resolve.
To summarize, it is possible to use a distance vector protocol framework and extend it for loop-free routing by using diffusing computation with coordinated update. Like any proto- cols, it has limitations under certain conditions.