거리 벡터 라우팅 프로토콜

위키백과, 우리 모두의 백과사전.

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

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


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

개요[편집]

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

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


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


거리-벡터 라우팅 구현[편집]

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

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

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


무한대로의 카운트[편집]

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

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

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

해결 방법 및 솔루션[편집]

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

수평 분할

각 인터페이스를 통해 테이블을 플러딩(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).

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

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
(T=0) A,B,C,D 모두에 최단 경로 정보가 갱신되었다. 각 라우터는 갱신된 자신의 정보를 다른 라우터에 브로드캐스트한다.

예를 들어 A는 C에게 'C에서 D로 가는 최단경로'가 5라는 정보(Distanve Vector)를 받는다. 그렇기 때문에 A에서 D로 가는 최단 경로는 5+23=28로 계산된다. 이것이 A가 D로 가는 알고있는 경로중에 가장 짧은 거리이므로 테이블을 갱신한다.

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
(T=1) 모든 라우터가 새로운 최단 경로를 이전에 얻었으므로, 모든 라우터는 자신의 DV를 이웃에게 브로드캐스트한다. 그러면 각 이웃은 자신의 최단 거리를 다시 계산해야한다.

예를 들어, A는 B에게 'B에서 D로 가는 최단경로'가 7이라는 DV를 받는다. B로 가는 현재의 최단경로가 3이므로, A는 D로 가는 비용 10(7+3)의�경로가 있음을 알 수 있다. 길이 10은 C를 거쳐가는 기존의 최단경로보다 짧으므로, 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
이번에는 라우터 A와 D만이 자신의 DV에 대한 새로운 최단 경로를 가지고 있다. 그래서 두 라우터는 자신들의 이웃들에게 새로운 DV를 브로드캐스트한다. A는 B와 C로 브로드캐스트하고, D는 C로 브로드캐스트한다.

새로운 DV를 수신하는 이웃들은 각각 자신들의 최단 경로를 다시 계산하게 하지만, 이미 가지고 있는 경로보다 더 짧은 결과가 없기 때문에 라우팅 테이블에는 아무런 변화가 없다.

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
모든 라우터가 브로드캐스트할 새로운 최단 경로를 가지고 있지 않기에 알고리즘 작동이 종료된다.

참고자료[편집]

  1. ↑ 가 나 Tamara Dean (2009). 《Network+ Guide to Networks》. Cengage Learning. 274쪽. ISBN 9781423902454. 
  2. ↑ Tamara Dean (2009). 《Network+ Guide to Networks》. Cengage Learning. 274–275쪽. ISBN 9781423902454. 
  • "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

추가 읽기[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=거리_벡터_라우팅_프로토콜&oldid=36538034"