Key Characteristics of DVRP

1. Neighbor Discovery and Updates

Routers (usually) sharing a common data link are called “neighbors”. A router sends it update to the neighbor and expects them to pass the information to their neighbors. For this reason, distance vector routing updates are hop-by-hop.

When a router first becomes active it must announce itself and find other routers. The simplest method is to send an update to broadcast address (for example: 255.255.255.255). The broadcast method was used by previous generation DVRP such as RIP version 1, Novel’s IPX RIP and Cisco IGRP. The later releases such as RIP version 2 and RIPng (RIP Next Generation for IPv6) use multicast addresses.

Update means how often the routing information is refreshed. Updates can be either:

  •  Periodic: an update must be send at the end of certain time period
  •  Triggered: also known as “flash updates”. An update is sent as soon as a change in routing information is detected. The key advantage is faster convergence

Updates (usually) include full routing table. Therefore, these timers must be adjusted carefully.

2. Routing-by-Rumor

Distance Vector algorithm only provide direction and distance. They don’t provide the details of the path taken to a specific destination. Consider Figure-1.

FIGURE 1: Routing by Rumor

 

In the simplest case, R1 will always take the path through R3 to reach R5 since it is one hope away, although path via R2 is much better. There is no proactive approach to find the best path to a given destination. R1 blindly trust the information received from R2 and R3 and in this case R3 is considered the best path. For this reason, DVRPs are pruned to routing loops.

3. Metric

Metric is value used to determine the best path to a specific destination when multiple paths exits. For example: RIP version 1 and 2 uses hop count where as IGRP can use bandwidth, delay, load and reliability.

4. Routing Loop Avoidance Techniques

Routing loops occurs due to old (bad) routing information. The major cause is the slow periodic update. For rest of this section Figure-2 will be our reference point.

FIGURE-2: Distance Vector Loop Avoidance

For example: in figure-2, R3 just sent out an update to R1 and R4, and suddenly the link between R3 and R5 goes down. R3 must wait, till the periodic update timer expires, to notify R1. During this time R1, R2 and R4 will continue to use the old route to R5 and routing black-hole is already created. In a larger network this routing information inconsistency could lead to a routing loop.

4.1. Route Invalidation Timer

In the previous example, what if R3 fails? There must be some mechanism to tackle this situation to avoid routing black-hole. When a route is learned from a neighbor, an invalidation timer is associated with it. If invalidation timer expires and no periodic update has been received, the route will be marked unreachable and pass down to neighbors along next update. In this case, R1 and R4 will mark R3 as unreachable and provide associate update to R2.

4.2. Split Horizon

Split Horizon rules dictate that routing information should never be sent out an interface it was learnt from. In figure-2, R3 is providing update about 192.168.35.0 to R1 and R4. Up to this point, R1 and R4 should advertise this information to R2 and back to R3. This process of advertising back the route to originator is called “reverse route”.

Common sense dictates that R1 and R4 should not advertise back to R3 since it already knows about 192.168.35.0 and off-course it waste resources. Split horizon prevents this reverse route phenomenon to evade routing loops. For example: let us assume that split horizon is not in effect and network 192.168.35.0 is unreachable. Even if the route invalidation timer is in effect, R3 must wait for next periodic update. But unexpectedly, R4 update arrives early. Now R3 has 192.168.35.0 reachable via R4 in two hops and a routing loop has occurred.

4.3. Count to Infinity

The primary purpose of split horizon is to avoid loop between neighbors. But split horizon alone can not avoid loop in a network such as in figure-2. Let us take a closer look how routing information is propagated. The network 192.168.35.0 has failed. R3 sends an update to R1 and R4 that 192.168.35.0 is unreachable. But at the same time, R2 is advertising 192.168.35.0 three hops away. R1 now informs R3 that it has 192.168.35.0 reachable via R2 in 4-hops. R3 installs this route and advertise to R4. R4 now think that the metric toward 192.168.35.0 from R3 has increased; nonetheless, it is the only route and must be installed. R4 advertises to R2, R2 to R1 to R3 and goes on. This loop goes in reverse direction also. For each update, the hop count keeps on increasing. This phenomenon is called to count to infinity. To elevate this problem distance vector protocols define “infinity”. Most distance vector protocols define infinity as hop count reaches 16 and such routing information is discarded immediately. Although routing loop will be eliminated, but the convergence will be slow as each router must wait for hop count to reach infinity.

4.4. Split Horizon with Poison Reverse

Uses the “infinity” value and advertise the route back to originator on the interface through which it was learned from as “unreachable”. The analogy is simple: “bad information is better than no information”. The count to infinity problem can be avoided since each neighbor is advertising routes leaned on same interface as unreachable. There is no need to wait for hop count to reach infinity.

4.5. Triggered Updates

Send partial (not full) update when a metric change occurs. Re-convergence is faster and reduces the chances of count-to-infinity problem.

4.6. Hold Down Timer

Flash updates allowed fast convergence but hold down timers introduces uncertainty to reduce the acceptance of bad routing information. If an advertisement is received increased metric (hop count), the router set a hold down timer before accepting the new routing information. Until the hold down timer expires, router will not accept any route for the specified destination. The trade off is the convergence time vs. bad routing information. In figure-2, R3 must set a hold down timer before accepting any update from R1 and R4.

Today we covered in detail the workings of Distance Vector Routing Protocols. In the next lessons we will learn in depth various issues faced by Distance Vector Routing Protocols and their remedies.