Distance-vector routing protocol: Difference between revisions

Revision as of 16:05, 28 July 2022

Latest revision as of 01:28, 5 August 2025

(7 intermediate revisions by 7 users not shown)

Line 1:

{{short description|Class of routing protocols}}

{{Multiple issues|

{{More footnotes needed|date=September 2010}}

{{technical|date=November 2013}}

}}

Line 10:

The term ''distance vector'' refers to the fact that the protocol manipulates ''vectors'' ([[Array data structure|arrays]]) of distances to other nodes in the network. The distance vector algorithm was the original [[ARPANET]] routing algorithm and was implemented more widely in [[local area networks]] with the [[Routing Information Protocol]] (RIP).

==Overview==

Distance-vector routing protocols use the [[Bellman–Ford algorithm]]. In these protocols, each router does not possess information about the full [[network topology]]. It advertises its distance value (DV) calculated to other routers and receives similar advertisements from other routers unless changes are done in the local network or by neighbours (routers). Using these routing advertisements each router populates its routing table. In the next advertisement cycle, a router advertises updated information from its routing table. This process continues until the routing tables of each router [[Convergence (routing)|converge]] to stable values.

Some of these protocols have the disadvantage of slow convergence.

Examples of distance-vector routing protocols:

* [[Routing Information Protocol]] (RIP)

* [[Routing Information Protocol#RIP version 2|Routing Information Protocol Version 2]] (RIPv2)

* [[Routing Information Protocol#RIPng|Routing Information Protocol Next Generation]] (RIPng), an extension of RIP version 2 with support for [[IPv6]]

* [[Interior Gateway Routing Protocol]] (IGRP)

* [[Enhanced Interior Gateway Routing Protocol]] (EIGRP)

==Methodology==

Routers that use distance-vector protocol determine the distance between themselves and a destination. The best route for [[Internet Protocol]] [[Network packet|packets]] that carry [[data]] acrossthrough a [[data network]] is measured in terms of the numbers of [[Router (computing)|routers]] (hops) a packet has to pass through to reach its destination network. Additionally, some distance-vector protocols take into account other traffic information, such as [[network latency]]. To establish the best route, routers regularly exchange information with neighbouring routers, usually their [[routing table]], hop count for a destination network and possibly other traffic related information. Routers that implement distance-vector protocol rely purely on the information provided to them by other routers, and do not assess the [[network topology]].<ref>{{Cite book|title= Network+ Guide to Networks|url= https://archive.org/details/networkguidetone00dean_142|url-access= limited|author =Tamara Dean |publisher= Cengage Learning|year=2009 |isbn= 9781423902454|pages=[https://archive.org/details/networkguidetone00dean_142/page/n294 274]}}</ref>

Distance-vector protocols update the routing tables of routers and determine the route on which a packet will be sent by the ''next hop'' which is the exit interface of the router and the IP address of the interface of the receiving router. Distance is a measure of the cost to reach a certain node. The least cost route between any two nodes is the route with minimum distance.

Line 29 ⟶ 41:

==Count to infinity problem==

The [[Bellman–Ford algorithm]] does not prevent [[routing loop]]s 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, 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). 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's point of view), C decides to update its table to "C to A = 3 + 1". This slowly propagates through the network until it becomes infinity (in which case the algorithm corrects itself, due to the relaxation property of Bellman-Ford).

===Workarounds and solutions===

Line 175 ⟶ 187:

|}

|-

|colspan=5| 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.

Line 589 ⟶ 601:

==Further reading==

* [http://docwiki.cisco.com/wiki/Routing_Basics#Link-State_Versus_Distance_Vector Section "Link-State Versus Distance Vector"] {{Webarchive|url=https://web.archive.org/web/20101214043441/http://docwiki.cisco.com/wiki/Routing_Basics#Link-State_Versus_Distance_Vector |date=2010-12-14 }} in the Chapter "Routing Basics" in the [[Cisco Systems|Cisco]] "Internetworking Technology Handbook"

* [httphttps://authorscsc-knu.phptrgithub.comio/tanenbaumcn4sys-prog/books/Andrew%20S.%20Tanenbaum%20-%20Computer%20Networks.pdf Section 5.2 "Routing Algorithms"] in Chapter "5 THE NETWORK LAYER" from "Computer Networks" 4th.5th Edition by Andrew S. Tanenbaum and David J. Wetherall

{{DEFAULTSORT:Distance-Vector Routing Protocol}}