World Library  
Flag as Inappropriate
Email this Article

Vector Routing Protocol

Article Id: WHEBN0000159228
Reproduction Date:

Title: Vector Routing Protocol  
Author: World Heritage Encyclopedia
Language: English
Subject: Enhanced Interior Gateway Routing Protocol, Vector, Interior Gateway Routing Protocol, Border Gateway Protocol, Index of Internet-related articles
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Vector Routing Protocol

In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of intra domain routing protocols, the other major class being the link-state protocol. Distance-vector routing protocols use the Bellman–Ford algorithm, Ford–Fulkerson algorithm, or DUAL FSM (in the case of Cisco Systems's protocols) to calculate paths.

A distance-vector routing protocol requires that a router inform its neighbors of topology changes periodically. Compared to link-state protocols, which require a router to inform all the nodes in a network of topology changes, distance-vector routing protocols have less computational complexity and message overhead.

The term distance vector refers to the fact that the protocol manipulates vectors (arrays) of distances to other nodes in the network. The vector distance algorithm was the original ARPANET routing algorithm and was also used in the internet under the name of RIP (Routing Information Protocol).

Examples of distance-vector routing protocols include RIPv1 and RIPv2 and IGRP.

Count-to-infinity problem

The Bellman–Ford algorithm does not prevent routing loops from happening and suffers from the count-to-infinity problem. The core of the count-to-infinity problem is that if A tells B that it has a path somewhere, there is no way for B to know if the path has B as a part of it. To see the problem clearly, imagine a subnet connected like A–B–C–D–E–F, and let the metric between the routers be "number of jumps". Now suppose that A is taken offline. In the vector-update-process B notices that the route to A, which was distance 1, is down – B does not receive the vector update from A. The problem is, B also gets an update from C, and C is still not aware of the fact that A is down – so it tells B that A is only two jumps from C (C to B to A), which is false. Since B doesn't know that the path from C to A is through itself (B), it updates its table with the new value "B to A = 2 + 1". Later on, B forwards the update to C and due to the fact that A is reachable through B (From C point of view), C decides to update its table to "C to A = 3 + 1". This slowly propagates through the network until it reaches infinity (in which case the algorithm corrects itself, due to the relaxation property of Bellman–Ford).

Workarounds and solutions

RIP uses the split horizon with poison reverse technique to reduce the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases. The addition of a hold time (refusing route updates for a few minutes after a route retraction) avoids loop formation in virtually all cases, but causes a significant increase in convergence times.

More recently, a number of loop-free distance vector protocols have been developed — notable examples are EIGRP, DSDV and Babel. These avoid loop formation in all cases, but suffer from increased complexity, and their deployment has been slowed down by the success of link-state routing protocols such as OSPF.

Example

In this network we have 4 routers A, B, C, and D:

We shall mark the current time (or iteration) in the algorithm with T, and shall begin (at time 0, or T=0) by creating distance matrices for each router to its immediate neighbors. As we build the routing tables below, the shortest path is highlighted with the color green, a new shortest path is highlighted with the color yellow. Grey columns indicate nodes that are not neighbors of the current node, and are therefore not considered as a valid direction in its table. Red indicates invalid entries in the table since they refer to distances from a node to itself, or via itself.

T=0
from A via A via B via C via D
to A
to B 3
to C 23
to D
from B via A via B via C via D
to A 3
to B
to C 2
to D
from C via A via B via C via D
to A 23
to B 2
to C
to D 5
from D via A via B via C via D
to A
to B
to C 5
to D
At this point, all the routers (A,B,C,D) have new "shortest-paths" for their DV (the list of distances that are from them to another router via a neighbor). They each broadcast this new DV to all their neighbors: A to B and C, B to C and A, C to A, B, and D, and D to C. As each of these neighbors receives this information, they now recalculate the shortest path using it.

For example: A receives a DV from C that tells A there is a path via C to D, with a distance (or cost) of 5. Since the current "shortest-path" to C is 23, then A knows it has a path to D that costs 23+5=28. As there are no other shorter paths that A knows about, it puts this as its current estimate for the shortest-path from itself (A) to D, via C.

T=1
from A via A via B via C via D
to A
to B 3 25
to C 5 23
to D 28
from B via A via B via C via D
to A 3 25
to B
to C 26 2
to D 7
from C via A via B via C via D
to A 23 5
to B 26 2
to C
to D 5
from D via A via B via C via D
to A 28
to B 7
to C 5
to D
Again, all the routers have gained in the last iteration (at T=1) new "shortest-paths", so they all broadcast their DVs to their neighbors; This prompts each neighbor to re-calculate their shortest distances again.

For instance: A receives a DV from B that tells A there is a path via B to D, with a distance (or cost) of 7. Since the current "shortest-path" to B is 3, then A knows it has a path to D that costs 7+3=10. This path to D of length 10 (via B) is shorter than the existing "shortest-path" to D of length 28 (via C), so it becomes the new "shortest-path" to D.

T=2
from A via A via B via C via D
to A
to B 3 25
to C 5 23
to D 10 28
from B via A via B via C via D
to A 3 7
to B
to C 8 2
to D 31 7
from C via A via B via C via D
to A 23 5 33
to B 26 2 12
to C
to D 51 9 5
from D via A via B via C via D
to A 10
to B 7
to C 5
to D
This time, only routers A and D have new shortest-paths for their DVs. So they broadcast their new DVs to their neighbors: A broadcasts to B and C, and D broadcasts to C. This causes each of the neighbors receiving the new DVs to re-calculate their shortest paths. However, since the information from the DVs doesn't yield any shorter paths than they already have in their routing tables, then there are no changes to the routing tables.
T=3
from A via A via B via C via D
to A
to B 3 25
to C 5 23
to D 10 28
from B via A via B via C via D
to A 3 7
to B
to C 8 2
to D 13 7
from C via A via B via C via D
to A 23 5 15
to B 26 2 12
to C
to D 33 9 5
from D via A via B via C via D
to A 10
to B 7
to C 5
to D
None of the routers have any new shortest-paths to broadcast. Therefore, none of the routers receive any new information that might change their routing tables. The algorithm comes to a stop.

References

  • "RFC1058 - Routing Information Protocol", C. Hedrick, Internet Engineering Task Force, June 1988
  • "RFC1723 - RIP Version 2 Carrying Additional Information", G. Malkin, Internet Engineering Task Force, November, 1994
  • "RFC2453 - RIP Version 2", G. Malkin, Internet Engineering Task Force, November, 1998
  • "A Path-Finding Algorithm for Loop-Free Routing, J.J. Garcia-Luna-Aceves and S. Murthy, IEEE/ACM Transactions on Networking, February 1997
  • "Detection of Invalid Routing Announcements in the RIP Protocol", D. Pei, D. Massey, and L. Zhang, IEEE Global Communications Conference (Globecom), December, 2003

Further reading

  • Section "Link-State Versus Distance Vector" in the Chapter "Routing Basics" in the Cisco "Internetworking Technology Handbook"
  • Section 5.2 "Routing Algorithms" in Chapter "5 THE NETWORK LAYER" from "Computer Networks" 4th. Edition by Andrew S. Tanenbaum
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.