A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers using a distance-vector protocol exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router inform its neighbours of network topology changes periodically.

Distance-vector routing protocols use the Bellman–Ford algorithm to calculate the best route. Another way of calculating the best route across a network is based on link cost, and is implemented through link-state routing protocols.

The term distance vector refers to the fact that the protocol manipulates vectors (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 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 Version 2 (RIPv2)
 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 packets that carry data across a data network is measured in terms of the numbers of routers (hops) a packet has to pass 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.

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.

Updates are performed periodically in a distance-vector protocol where all or part of a router's routing table is sent to all its neighbours that are configured to use the same distance-vector routing protocol. Once a router has this information it is able to amend its own routing table to reflect the changes and then inform its neighbours of the changes. This process has been described as ‘routing by rumour’ because routers are relying on the information they receive from other routers and cannot determine if the information is actually valid and true. There are a number of features which can be used to help with instability and inaccurate routing information.

Development of distance-vector routing 
The oldest routing protocol, and the oldest distance-vector protocol, is version 1 of the Routing Information Protocol (RIPv1). RIPv1 was formally standardised in 1988. It establishes the shortest path across a network purely on the basis of the hops, that is numbers of routers that need to be passed to reach the destination network. RIP is an interior gateway protocol, so it can be used in local area networks (LANs) on interior or border routers. Routers with RIPv1 implementation exchange their routing tables with neighbouring routers by broadcasting a RIPv1 packet every 30 second into all connected networks. RIPv1 is not suitable for large networks as it limits the number of hops to 15. This hop limit was introduced to avoid routing loops, but also means that networks that are connected through more than 15 routers are unreachable.

The distance-vector protocol designed for use in wide area networks (WANs) is the Border Gateway Protocol (BGP). BGP is an exterior gateway protocol and therefore implemented on border and exterior routers on the Internet. It exchanges information between routers through a Transmission Control Protocol (TCP) session. Routers with BGP implementation determine the shortest path across a network based on a range of factors other than hops. BGP can also be configured by administrators so that certain routes are preferred or avoided. BGP is used by internet service providers (ISPs) and telecommunication companies.

Among the distance-vector protocols that have been described as a hybrid, because it uses routing methods associated with link-state routing protocols, is the proprietary Enhanced Interior Gateway Routing Protocol (EIGRP). It was developed by Cisco in the 1980s and was designed to offer better convergence and cause less network traffic between routers than the link-state routing protocol Open Shortest Path First (OSPF).

Another example of a distance-vector routing protocol is Babel.

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, 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
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 mark the current time (or iteration) in the algorithm with T, and begin (at time 0, or T=0) by creating distance matrices for each router to its immediate neighbours. As we build the routing tables below, the shortest path is highlighted in green, and a new shortest path is highlighted in 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.

References

 
 "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

Routing protocols
Routing algorithms
데이터 네트워크에서 거리 벡터 라우팅 프로토콜(Distance-vector routing protocol)은 패킷이 통과하는 라우터 수, 혹은 레이턴시와 같이 트래픽에 영향을 미치는 기타 요소로 거리를 측정하여 이를 기반으로 데이터 패킷의 최적 경로를 결정한다. 거리 벡터 프로토콜을 사용하는 라우터는 일반적으로 라우팅 테이블과 대상 네트워크의 홉 수 등의 정보를 주변 라우터와 서로 교환하고, 네트워크 토폴로지 변경 사항을 주기적으로 전파한다.

거리 벡터라는 용어는 프로토콜이 네트워크의 다른 노드까지의 거리 벡터 (배열)을 사용한다는 뜻이다. 거리 벡터 알고리즘은 원래 ARPANET 라우팅 알고리즘이었으며 RIP( Routing Information Protocol )를 사용하여 근거리 통신망 에서 더욱 광범위하게 구현되었다.

경로를 계산하는 또 다른 알고리즘으로는 링크 상태 라우팅 알고리즘, 경로 벡터 알고리즘 등이 있다.

개요 
거리 벡터 라우팅 프로토콜은 Bellman-Ford 알고리즘을 사용한다. 그러므로 각 라우터는 전체 네트워크 토폴로지에 대한 정보를 소유하지 않고, 자신에 대한 거리 계산값이 들어오면 자신에게 연결된 이웃 라우터 가중치를 더해 계산하여 다른 라우터에 알리는 동작을 반복한다.

이 프로세스는 각 라우터의 라우팅 테이블이 안정적인 값으로 수렴할 때까지 계속된다.

거리 벡터 라우팅을 구현한 프로토콜의 예시는 다음과 같다:

 라우팅 정보 프로토콜 (RIP)
 RIPv2( 라우팅 정보 프로토콜 버전 2 )
 IPv6를 지원하는 RIP 버전 2의 확장인 RIPng( Routing Information Protocol Next Generation )
 IGRP( 내부 게이트웨이 라우팅 프로토콜 )
 향상된 내부 게이트웨이 라우팅 프로토콜 (EIGRP)

거리-벡터 라우팅 구현 
가장 오래된 라우팅 프로토콜이자 가장 오래된 거리 벡터 프로토콜은  1988년에 표준화된 RIPv1( Routing Information Protocol )이다.   RIPv1는 홉, 즉 대상 네트워크에 도달하기 위해 통과해야 하는 라우터 수를 기준으로 네트워크 전체에서 최단 경로를 설정한다. RIP는 내부 게이트웨이 프로토콜 이므로 내부 또는 경계 라우터의 근거리 통신망 (LAN)에서 사용할 수 있다.

RIPv1 프로토콜을 사용하는 라우터는 연결된 모든 네트워크에 30초마다 RIPv1 패킷을 브로드캐스트 하여 인접 라우터와 라우팅 테이블을 교환한다. RIPv1은 라우팅 루프를 방지하기 위해 홉 수를 15로 제한하므로, 대규모 네트워크에는 적합하지 않다.

WAN( 광역 네트워크 )에서 사용하도록 설계된 거리 벡터 프로토콜은 BGP( Border Gateway Protocol )이다. BGP는 외부 게이트웨이 프로토콜 이므로 인터넷 의 경계 및 외부 라우터에서 구현된다.  BGP는 TCP( Transmission Control Protocol ) 세션을 통해 라우터 간에 정보를 교환한다. BGP가 구현된 라우터는 홉 이외의 다양한 요소를 기반으로 네트워크 전체에서 최단 경로를 결정한다. 관리자는 특정 경로를 선호하거나 피하도록 설정할 수도 있다. BGP는 인터넷 서비스 공급자 (ISP)와 통신 회사에서 사용된다.

무한대로의 카운트 
Bellman-Ford 알고리즘에서는 라우팅 루프가 발생하는 것을 방지하지 않기 때문에 무한대로의 카운트 문제(Count to Infinity)가 발생할 수 있다.

A–B–C와 같이 연결된 네트워크를 상상해보자.

 만약 A가 오프라인 상태라면, B는 거리 1인 A에 대한 경로가 다운되었음을 확인한다.
 하지만 C는 A가 다운되었다는 정보를 바로 받지 못한다. C는 A가 다운되었다는 사실을 인식하여 C에서 A로 가기 위해 2번의 점프(C->B->A)가 필요하다는 것을 B에게 알려준다.
 B는 C에서 A로 가는 경로가 자신(B)을 통과한다는 사실을 모르기 때문에 A로 가는 경로에 대한 테이블을 새로운 값 3((A->B)->A)으로 갱신한다.
 나중에 B가 업데이트를 C에 전달하면 C는 A로 가는 경로에 대한 테이블을 "C에서 A = 3 + 1"로 갱신한다.
 이 과정이 무한대로 반복된다.

해결 방법 및 솔루션 
이 문제를 해결하기 위한 대표적인 방법으로는 수평 분할과 포이즌 리버스가 있다.

수평 분할

각 인터페이스를 통해 테이블을 플러딩(flooding)하는 대신에 각 인터페이스를 통해 자신 테이블의 일부만을 전송한다. 위의 예시에서 C가 A에 도달하는 최소 경로에서 B를 거쳤다는 것을 안다면, 이 정보를 다시 B에게 광고할 필요가 없다. 경로 정보를 받아온 노드에는 다시 정보를 보내지 않도록 하는 것이 수평 분할 방식이다.

하지만 수평 분할에는 하나의 단점이 있다. 보통 거리 벡터 알고리즘 프로토콜은 타이머를 사용하고, 경로상에 새로운 소식이 없으면 테이블에서 경로를 제거한다. 이 때문에 C가 B로 보내는 광고에 A로의 경로를 제거해버리면 B는 이것이 수평 분할 정책 때문에 그런 것인지 아니면 C가 최근에 A에 관한 소식을 받지 못해서인지 예측할 수 없다.

포이즌 리버스

포이즌 리버스는 수평분할에서 일어나는 문제를 해결할 수 있다. C가 A에 대한 정보를 광고하되, 만약 송신자가 노드 A인 경우 거리값을 무한대로 설정해서 값이 사용되지 않도록 한다.

최근에는 루프 문제를 해결한 거리 벡터 프로토콜이 다수 개발되었다. 대표적인 예로는 EIGRP, DSDV 및 Babel이 있다. 이러한 프로토콜은 루프 형성을 방지하지만 복잡성이 증가한다는 단점이 있다.

예제 
4개의 라우터 A, B, C, D가 있다고 해보자.

알고리즘의 현재 시간(또는 반복)을 T로 표시하고, 각 라우터에 대해 바로 이웃까지의 거리 행렬을 나타내보자(시간 0 또는 T=0).

아래 라우팅 테이블에서 최단 경로는 녹색으로 강조 표시되고, 새로운 최단 경로는 노란색으로 강조 표시된다. 회색 열은 현재 노드의 이웃이 아닌 노드를 나타내므로 유효하지 않은 칸이고, 빨간색은 노드 자신이 연관된 경로이기 때문에 사용하지 않는다.

참고자료 

 "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

추가 읽기 

 Cisco "인터네트워킹 기술 핸드북"의 "라우팅 기본 사항" 장에 있는 "링크 상태 대 거리 벡터" 섹션 
 "컴퓨터 네트워크" 4번째 장 "5 네트워크 계층"의 섹션 5.2 "라우팅 알고리즘" . Andrew S. Tanenbaum의 에디션
라우팅 알고리즘
라우팅 프로토콜