3.5 Path Vector Routing Protocol
3.5.2 Path Vector with Path Caching
There are additional aspects that may impact the actual working of a path vector protocol. To see this, observe that an advantage of the path vector announcement is that a node may learn about multiple nonlooping paths to a destination from its different neighbors. It may choose to cache multiple path entries in its path table for each destination that it has learned from all or some of its neighboring nodes, instead of caching just the best one; this is an advantageous feature of a path vector protocol. Note, however, that while the path table may have multiple entries for each destination, the routing table points only to the next hop for the best or single preferred path for each destination unless there is a tie; in case of a tie, the routing table will enter the next hop for both paths.
Thus, we will now illustrate a generalization of the basic concept of a path vector proto- col where a node is allowed to cache multiple paths for every destination in the path table.
For simplicity, we assume that each node stores two best paths per destination that it has learned from different neighbors. Thus, for destination node 6, each source node will have the following path entries:
From Node To Destination Cost Path Table Entry
1 6 3 (1,4,3,6)
1 6 4 (1,2,3,6)
2 6 3 (2,3,6)
2 6 3 (2,4,3,6)
3 6 1 (3,6)
3 6 2 (3,5,6)
4 6 2 (4,3,6)
4 6 3 (4,5,6)
5 6 1 (5,6)
5 6 2 (5,3,6)
Consider again the failure of the link between node 3 and node 6. When node 3 recognizes this link failure, it will realize that it has a second path to node 6, i.e.,(3,5,6). Thus, it will delete path(5,6), make route(3,5,6)the preferred route in the path table, make appropriate adjustments in the routing table, and advertise path(3,5,6)with its cost to its neighbors 2, 4, and 5 as 6, 2, 3; 3, 5, 6.
We will first consider the situation at node 5. On receiving the above message, node 5 will immediately detect that this will create a loop, and thus it will ignore this message. Node 2,
on receiving the new path vector from node 3, will notice that it will need to update the first path. This will make the second path cheaper, although the second path has an unreachable path.
Node 4, on receiving the new path vector from node 3, will change its path via node 3 to (4,3,5,6)and the cost to 3. Now, both paths for destination node 6 will be of cost 3. It will then transmit a path vector message to nodes 2 and 1 about the new path vector to destination 6.
Node 1 will receive an updated path vector from node 2 in regard to destination node 6, and update both its paths via node 2. Node 2 will receive another one from node 4 and will update that path as well.
Eventually, different nodes will have new path entries to destination node 6 as follows (invalid paths are marked with a strikethrough):
From Node To Destination Cost Path Table Entry
1 6 4 (1,4,3,5,6)
1 6 5 (1,2,3,5,6)
2 6 4 (2,3,5,6)
2 6 4 (2,4,3,5,6)
3 6 1 (3,—–6)
3 6 2 (3,5,6)
4 6 3 (4,3,5,6)
4 6 3 (4,5,6)
5 6 1 (5,6)
5 6 2 (——–5,3,6)
It may be noted that path caching can be helpful as it provides a node with additional paths through its neighbors if the first one does not work because of a link failure. The basic idea behind a path vector protocol with path caching is outlined in Figure 3.15. It usually con- verges to a new solution quickly. Thus, it can give the impression that path caching is a good idea. However, path caching is not always helpful; in fact, it can result in poor convergence in case of a node failure, especially when the node is connected to multiple nodes. We will describe this next.
NODEFAILURECASE
To illustrate the node failure case, we consider a four-node fully connected network example [594] shown in Figure 3.16; we assume that the distance cost between any two nodes is 1.
Preferred direct path and alternate cached paths are shown in the following table (top of the next page) from nodes 1, 2, and 3 to destination node 0.
From Node To Destination Cost Path Table Entry
1 0 1 (1,0)
1 0 2 (1,2,0)
1 0 2 (1,3,0)
2 0 1 (2,0)
2 0 2 (2,1,0)
2 0 2 (2,3,0)
3 0 1 (3,0)
3 0 2 (3,1,0)
3 0 2 (3,2,0)
Initialization:
– Nodeiis activated and exchanges “hello” message with neighbors; table exchange updates are per- formed to find paths for all known destination nodesj
Nodeiin the receiving mode:
Announcement/Advertisement Message:
– Receive a path vectorPkji from neighborkregarding destination nodej – If ( destination nodejis not previously in routing and path table )
create a new entry and continue
– If ( for destination nodejthere is already an entry for the previously announced path from nodekin the path table )
Replace the old path by the new pathPkji in the path table – Update candidate path cost:Dij=dik+Dikj
If (Dij<Dij) then Mark best path asi→Pkji
Update the routing table entry for destinationj else
For destinationj, identify neighborkthat results in minimum cost over all neighbors, i.e.,Dij=dik+Dikj=mink∈Ni{dik+Dikj} Mark the best path through this new neighbor asi→Pi
kj Update the routing table entry for destinationj
Nodeiin sending mode: send the new best path to all its neighbors Endif
Withdrawal Message:
– If ( a withdrawal message is received from a neighbor for a particular destinationj) then Mark the corresponding entry as “unreachable”
If ( there is a next best path in the path table for this destination) Advertise this to the rest of the neighbors
Endif
Special Cases: (nodeilost communication with neighbork[“link failure”]):
– For those destinationsjfor which the best path was throughk, mark the path as “unreachable” in the path table (and also routing table )
– If ( another path is available in cache for the same destination through another neighbork) Advertise/announce this to all the remaining neighbors
– If ( there is no other path available in cache for destinationj) Send a message to all neighbors that path to nodejis “withdrawn”
F I G U R E 3.15 Path vector protocol with path caching (nodei’s view).
Consider now the failure of node 0. Immediately, all the other nodes lose their direct path to node 0. All of them switch to their second path in the path table entry. For example, node 1 will switch from (1,0)to (1,2,0); furthermore, node 1 will send the following path vector announcement to node 3 and node 2: 0, 2, 3; 1, 2, 0. This announcement will be understood by the receiving nodes as an implicit withdrawal, meaning its previous one does not work and it is replaced by a new one. This would lead to a cascading of path changes; for example, at node 2, first path(2,0)will be dropped and will be replaced by(2,1,0). On hearing from node 1 that(1,0)is not reachable, it will then switch to (2,3,0). It will go through another step to(2,1,3,0)before recognizing that no more paths are available, and noting then that a path to destination node0is unavailable.
In this illustration, we assume that node 2 finds out about the connectivity being down to node 0 before node 1 and node 3 have recognized that their connectivity to node 0 is down as well; in other words, node 2 does not receive the first path withdrawal messages from node 1 and node 3 before it sends out to them. The following sequence of steps will then take place:
– Node 2 sees that path(2,0)is no longer available and crosses it off. By inspecting paths cached in its routing table, it then switches to(2,1,0), which is least as the next preferred path.
Node 2 informs both node 1 and node 3 about withdrawal of path(2,0).
– Node 1 recognizes that path(1,0)is no longer available and crosses it off.
Node 1 switches to its next preferred path(1,2,0).
Node 1 receives withdrawal of path(2,0)from node 2, before it has time to inform others about (1,0).
Node 1 switches to(1,3,0)and advertises this path to node 2.
– Node 2 receives the advertisement(1,3,0)from node 1 and recognizes that the preferred path of node 1 to node 0 is no longer(1,0); thus, node 1 strikes off(2,1,0).
Node 2 compares the last path in its preferred list(2,3,0)to the newly advertised path(1,3,0) received from node 1, i.e., compare(2,3,0)with(2,1,3,0), and switches to(2,3,0)since this is preferred over(2,1,3,0).
– Node 3 recognizes that path(3,0)is no longer available and crosses it off.
Node 3 receives withdrawal of path(1,0)from node 1 and withdrawal of path(2,0)from node 2.
Node 3 thus realizes that(3,1,0)and(3,2,0)are no longer available and crosses them off.
Node 3 informs node 1 and node 2 that path(3,0)is no longer available.
– Upon receiving withdrawal of path(3,0)from node 3, node 2 realizes that path(2,3,0)is no longer available, thus, it switches to(2,1,3,0), since this is the only path remaining in its table.
– Upon receiving withdrawal of path(3,0)from node 3, node 1 realizes that(1,3,0)is no longer available and thus inform node 2 that path(1,3,0)is no longer available.
– Upon receiving withdrawal of path(1,3,0)from node 3, node 2 finally realizes that it no longer has any path to node 0.
The key point about this illustration is that due to path exploration, convergence can take quite a bit of time in case of a node failure when the failing node has multiple connectivity.
You may wonder why the node failure case is so important since the nodes are built to be robust to start with. There are two reasons for this:
F I G U R E 3.16 Four-node fully connected network.
• From a theoretical point of view, it is important to understand how the entire protocol works so that fail-safe mechanisms can be added, if needed.
• While the node failure case discussed above seems like an unlikely case, this is a fairly common case in BGP since a node such as node 0 is a specialized node. Actually, such a node is not a real node and in fact represents an address block (IP prefix) that is conceptually represented as a specialized node in the above illustration; we will discuss this in detail in Chapter 8. In this sense, the above illustration is really about how quickly the overall network may learn about losing connectivity to an address block or a route and helps us see the implication of a node failure.
Finally, an important comment here. A path vector protocol tries to avoid looping by not accepting a path from a neighboring node if this path already contains itself. However, in the presence of path caching, a node can switch to a secondary path, which can in fact lead to an unusual oscillatory problem during the transient period; thus, an important problem in the operation of a path vector protocol is the stable paths problem [265]. This says that instead of determining the shortest path, a solution that reaches an equilibrium point is desirable where each node has only a local minimum; note that it is possible to have multiple such solutions at equilibrium.
IMPLICITCOST ANDRELATION TOBGP
In our basic description of the path vector protocol with path caching, we have assumed that the cost to destination is included; this is helpful when the cost between two neighboring nodes is different. When the cost between two neighboring nodes is implicitly set to 1, it means that the link cost is hop-based. In this case, it is not necessary to include the cost to destination in the path vector message. Thus, a message format would be:
Destination Node, Number of Nodes in the Path; Node List of the Path | . . .
As for example, instead of using the protocol message given in (3.5.1), the following will be transmitted:
1, 2; 2, 1 | 2, 1; 2 | 3, 2; 2, 3 | 4, 2; 2, 4 | 5, 3; 2, 3, 5 | 6, 3; 2, 3, 6
Certainly, this implicitly assumes that all costs are hop-based instead of link costs shown in Figure 3.2. In fact, BGP uses the notion of implicit hop-based cost. BGP has another differ- ence; the node as described here is a model of a supernode this is called an autonomous system in the Internet. This also results in a difference, instead of the simplifying assumption we have made that the node ID is what is contained in a path vector message. Furthermore, two supernodes may be connected by multiple links where there may be a preference in regard to selecting one link over another. Thus, BGP is quite a bit more complicated than what we have described and illustrated here in regard to a path vector protocol; BGP will be discussed in detail in Chapter 8.