Distance vector protocols

A routing protocol belong to one of two classes (Distance-Vector or Link-state), every class of both has some of characteristics of operation.

– Distance Vector class
One of the main aspects of Distance-Vector that every route is treated like a Vector being defined the Distance by the Metric and defined the Direction by the Next-hop for example RIP (Routing Information Protocol) calculates the Metric by count how many Hop-AWAY this prefix exist.

List of the Routing Protocols:
1 -Routing Information Protocol (RIP) for IP
2- Xerox Networking System’s XNS RIP
2-Novell’s IPX RIP
3-The Cisco Systems Internet Gateway Routing Protocol (IGRP) and Enhanced Internet Gateway
4 -Routing Protocol (EIGRP)
5- DEC’s DNA Phase IV
6- AppleTalk’s Routing Table Maintenance Protocol (RTMP)

BGP could be considered as a Distance-Vector protocol but mostly Books call it PATH-Vector protocol

EIGRP has some exceptions of the big rule of the Distance-Vector suck as it’s not slow in convergence, no periodic updates, No full routing table update so some books are calling it hyper.

‘’Convergence

Most of Distance-Vector protocols periodically advertise updates by broadcast message to neighbors by sending the entire Routing-Table, after the neighbor has received the update then it is responsible to deliver this update to the Next Router , this periodic frequently updates sometimes are causing in congestion and load to the Router CPU, also if these updates being sent infrequently the convergence in the network would be unacceptable.
When any Router becomes active , it will send a broadcast message (255.255.255.255) to declare itself and the other routers that speaking the same language (Protocol) will understand the message and take appropriate action in order to perform the Convergence.

Routing by rumor

Because in the Distance-Vector protocols every update received is coming from the neighbor perspective and after this neighbor router ran its calculation Algorithm , not independently calculated , the receiver router does not care what the network look like but all what it can imagine is that this Prefix (X) is Received from Next hop (Y) with Metric (one hop Away) if we are talking from RIP operation perspective as an example of Distance-Vector protocols.

Note: When a Router Receives update contain one or more prefix it already has in its routing table with the same Next-hop router and hop counts it will discard this prefixes from the update.

‘’Distance Vector defects and solutions

Route Validation Time:

What if a prefix or a subnet goes down in a network runs a Distance-Vector Protocol , it’s so simple the router which this subnet being attached will send in the upcoming periodic update that this subnet is down and So on… ) BUT if the Router itself which this subnet attached to it became down  , Other Routers still do not know because there is no update received informing that this subnet is Down or the Router is self so this is considered as a  black hole in the network because neighbors are still seeing that this subnet is reachable, So there is a mechanism used in this case called (Route Invalidation timer).

When a router receives a prefix for the first time it sets a time of this route validation and after the timeout of this prefix it will remove this subnet or this prefix as it is considered unreachable and send this update in the upcoming periodic update to other neighbors routers.

Periods for route timeouts range from three to six update periods. A router would not want to invalidate a route after a single update has been missed, because this event might be the result of a corrupted or lost packet or some sort of network delay.

Routing loops:

One of another problems is the Routing loops , Let’s imagine there are two routers (A and B) are running with RIP , A-Router has attached subnet (N) sent it in an update to B-Router , B-Router received and stored the subnet in it’s routing table , In the next periodic update what is the mechanism that prevents B-Router to send the subnet (N) update back to A-Router? If B-Router sends the (N) subnet update back to A-Router anyway A-Router is going to discard the update that because it has the same Subnet with lowest Metric but this Ping-Pong Operation wastes the resources of the network , So (Split Horizon mechanism) Takes a place , simply Split-Horizon is preventing B-Router to send back the (N) subnet update to A-Router on the same interface which B-Router received  the update From.

Split-Horizon concept is when sending updates out a particular interface, does not include networks that were learned from updates received on that interface.

Regardless of wasting the resources of the network , imagine that A-Router which has (N) Subnet and B-Router , Let’s say that the (N) Subnet went down and before the periodic update which A-Router will send it to B-Router contains update of the failure of (N) subnet, The B-Router which also sending a periodic update unfortunately B-Router sent the Update to A-Router Says “hey A-Router, I have (N) is one hop away”. A-Router will receive this update and adds the (N) subnet router in the routing table because in Dynamic Routing Protocols one of it’s powerful features is to find a backup of the path when the main went down , now imagine what happens with a Transit-Packet from B-Router destined to (N) subnet  , B-Router have Next Hop is A-Router , so will pass the packet to A-Router , A-Router see this (N) subnet with two Hop away and the Next-HOP is B-Router and the loop occurs (Ping – Pong operation again) but the SPLIT-Horizon will solve this problem from the beginning because it will prevent B-Router to send the UPDATE about (N) subnet back to A-Router on the Interface which it is received from.

There is another rule now a days comes with Split-Horizon rule The (Route Poisoning)
supposed somehow A-Router suddenly recognized by wrong that (N) is reachable via B-Router so simply Split-Horizon will not prevent the loop from occurring so then B-Router in the Periodic update will send (N) subnet update as this route is (Poisoned- Route) with Infinity hop counts so A-Router will know then that the Next-hop of this Subnet is not B-Router.

Counting to Infinity:

images

Split horizon will break loops between neighbors, but it will not stop loops in a network such as the one in again, 10.1.5.0 has failed. Router D sends the appropriate updates to its neighbors, Router C (the dashed arrows), and Router B (the solid arrows). Router B marks the route via D as unreachable, but Router A is advertising a next-best path to 10.1.5.0, which is three hops away. B posts that route in its route table.

B now informs D that it has an alternative route to 10.1.5.0. D posts this information and updates C, saying that it has a four-hop route to the network. C tells A that 10.1.5.0 is five hops away. A tells B that the network is now six hops away.

“Ahmm” Router B thinks, “Router A’s path to 10.1.5.0 has increased in length. Nonetheless, it’s the only route I’ve got, so I’ll use it!”

B changes the hop count to seven, updates D, and around it goes again. This situation is the counting-to-infinity problem because the hop count to 10.1.5.0 will continue to increase to infinity. All routers are implementing split horizon, but it doesn’t help.

The way to alleviate the effects of counting to infinity is to define infinity. Most distance vector protocols define infinity to be 16 hops. As the updates continue to loop among the routers in the hop count to 10.1.5.0 in all routers will eventually increment to 16. At that time, the network will be considered unreachable.

There is another technique to reduce the looping beside the Counting to Infinity , (Triggered Updates) also known as flash updates, are very simple: If a metric changes for better or for worse, a router will immediately send out an update without waiting for its update timer to expire. Re-convergence will occur far more quickly than if every router had to wait for regularly scheduled updates, and the problem of counting to infinity is greatly reduced, although not completely eliminated. Regular updates might still occur along with triggered updates. Thus a router might receive bad information about a route from a not-yet-re-converged router after having received correct information from a triggered update. Such a situation shows that confusion and routing errors might still occur while a network is re-converging, but triggered updates will help to iron things out more quickly.

Hold-down Timers:

Triggered updates add responsiveness to a re-converging network. Hold-down timers introduce a certain amount of skepticism to reduce the acceptance of bad routing information.

If the distance to a destination increases (for example, the hop count increases from two to four), the router sets a hold-down timer for that route. Until the timer expires, the router will not accept any new updates for the route.

Obviously, a trade-off is involved here. The likelihood of bad routing information getting into a table is reduced but at the expense of the re-convergence time. Like other timers, hold-down timers must be set with care. If the hold-down period is too short, it will be ineffective, and if it is too long, normal routing will be adversely affected.

Thanks,
Mohamed Wagdy