거리 벡터 라우팅 프로토콜
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
거리 벡터 라우팅 프로토콜은 벨만-포드 알고리즘을 사용하여 각 라우터가 이웃 라우터와의 거리 정보를 교환하며 최적의 경로를 찾아가는 방식의 라우팅 프로토콜이다. 라우터는 네트워크 전체의 토폴로지를 알지 못하고, 홉 수나 지연 시간과 같은 메트릭을 사용하여 최단 경로를 결정한다. 라우팅 테이블을 주기적으로 업데이트하며, 다른 라우터의 정보에 의존하기 때문에 '소문을 통한 라우팅'이라고도 불린다. 주요 거리 벡터 프로토콜로는 RIP, BGP, EIGRP 등이 있으며, '무한대로의 카운트' 문제와 같은 단점을 해결하기 위해 수평 분할, 포이즌 리버스 등의 기법을 사용한다.
더 읽어볼만한 페이지
- 라우팅 알고리즘 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다. - 라우팅 알고리즘 - 플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 동적 계획법의 일종으로, 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾아 시간 복잡도 O(N^3)으로 계산하며, 유향 그래프의 최단 경로 탐색 등 다양한 문제에 적용된다. - 라우팅 프로토콜 - 라우팅 정보 프로토콜
라우팅 정보 프로토콜(RIP)은 벨만-포드 알고리즘 기반의 거리 벡터 라우팅 프로토콜로, 홉 카운트를 사용하여 최적 경로를 설정하며 라우팅 루프 방지를 위해 최대 홉 수를 15로 제한하고, RIPv1, RIPv2, RIPng 등의 버전이 있다. - 라우팅 프로토콜 - IS-IS
IS-IS는 대규모 네트워크에서 효율적인 라우팅을 제공하는 링크 상태 라우팅 프로토콜로, 빠른 컨버전스 속도와 확장성이 뛰어나 통신 사업자 및 데이터 센터에서 주로 사용되며 OSPF와 유사하지만 주소 체계 등에서 차이가 있다.
| 거리 벡터 라우팅 프로토콜 | |
|---|---|
| 개요 | |
| 종류 | 라우팅 프로토콜 |
| 기능 | 네트워크 내에서 목적지까지의 최적 경로를 결정 |
| 특징 | 주기적으로 전체 라우팅 테이블을 이웃 라우터에 전송 |
| 작동 원리 | |
| 정보 교환 | 각 라우터는 주기적으로 인접 라우터에 자신의 라우팅 테이블 복사본을 보냄 |
| 거리 정보 | 각 라우터는 네트워크 내 다른 모든 노드까지의 거리를 기록 (홉 수 또는 다른 메트릭 사용) |
| 벡터 정보 | 각 라우터는 특정 목적지에 도달하기 위한 최적의 경로(방향)를 기록 |
| 업데이트 | 라우터는 이웃으로부터 라우팅 업데이트를 수신하면 자신의 테이블을 업데이트하여 최적 경로를 반영 |
| 주요 알고리즘 | |
| 벨-포드 알고리즘 (Bellman-Ford algorithm) | 최단 경로를 찾는데 사용 |
| 라우팅 정보 프로토콜 (Routing Information Protocol, RIP) | 거리 벡터 라우팅 프로토콜의 한 예 |
| 장단점 | |
| 장점 | 구현 및 구성이 비교적 간단 소규모 네트워크에 적합 |
| 단점 | 라우팅 루프 문제 발생 가능성 네트워크 크기가 커질수록 확장성 떨어짐 컨버전스 속도가 느림 (네트워크 변경 사항이 전체 네트워크에 반영되는 데 시간이 오래 걸림) Count-to-infinity 문제 발생 가능성 |
| 문제점 및 해결책 | |
| Count-to-infinity 문제 | 잘못된 라우팅 정보가 네트워크 전체에 무한히 순환하는 문제 |
| 해결책 | 최대 홉 수 제한 (일반적으로 15홉) Split horizon Poison reverse Triggered update |
| 프로토콜 종류 | |
| 라우팅 정보 프로토콜 (RIP) | 가장 일반적인 거리 벡터 라우팅 프로토콜 |
| IGRP (Interior Gateway Routing Protocol) | 시스코에서 개발한 거리 벡터 라우팅 프로토콜 (현재는 EIGRP로 대체) |
| EIGRP (Enhanced Interior Gateway Routing Protocol) | 시스코에서 개발한 고급 거리 벡터 라우팅 프로토콜 (하이브리드 프로토콜로 분류되기도 함) |
| 기타 | |
| 용도 | 소규모 네트워크 또는 대규모 네트워크의 특정 영역 내에서 사용 |
| 대체 기술 | 링크 상태 라우팅 프로토콜 (OSPF, IS-IS) |
2. 거리 벡터 라우팅 프로토콜의 동작 방식
거리 벡터 라우팅 프로토콜은 벨만-포드 알고리즘을 기반으로 동작한다. 각 라우터는 전체 네트워크 토폴로지에 대한 정보를 소유하지 않고, 자신에게 연결된 이웃 라우터까지의 거리(가중치)를 계산하여 더한 뒤, 이를 다른 라우터에 알리는 동작을 반복한다.[1] 이 과정은 각 라우터의 라우팅 테이블이 안정적인 값으로 수렴될 때까지 계속된다.
거리 벡터 라우팅을 구현한 프로토콜의 예는 다음과 같다:
- 라우팅 정보 프로토콜 (RIP)
- RIPv2
- RIPng (IPv6 지원)
- 내부 게이트웨이 라우팅 프로토콜 (IGRP)
- 향상된 내부 게이트웨이 라우팅 프로토콜 (EIGRP)
이러한 프로토콜 중 일부는 수렴 속도가 느리다는 단점이 있다.
2. 1. 벨만-포드 알고리즘
거리 벡터 라우팅 프로토콜은 벨만-포드 알고리즘을 사용한다. 각 라우터는 전체 네트워크 토폴로지에 대한 정보를 소유하지 않고, 자신에게 연결된 이웃 라우터까지의 거리(가중치)를 계산하여 다른 라우터에 알리는 동작을 반복한다. 이 과정은 각 라우터의 라우팅 테이블이 안정적인 값으로 수렴될 때까지 계속된다.[1]거리 벡터 프로토콜에서 라우터는 자신과 목적지 간의 거리를 홉 수로 측정한다. 데이터 데이터 네트워크를 통한 최적의 경로는 패킷이 대상 네트워크에 도달하기 위해 거쳐야 하는 라우터의 수로 결정된다. 일부 거리 벡터 프로토콜은 네트워크 지연 시간과 같은 다른 트래픽 정보도 고려한다. 라우터는 라우팅 테이블의 홉 수 및 기타 정보를 사용하여 인접 라우터와 정기적으로 정보를 교환하며, 다른 라우터에서 제공하는 정보에만 의존하고 네트워크 토폴로지를 직접 평가하지 않는다.[1]
거리 벡터 프로토콜은 라우터의 라우팅 테이블을 업데이트하여 패킷이 전송될 경로(라우터의 출구 인터페이스와 수신 라우터의 인터페이스 IP 주소, 즉 '다음 홉')를 결정한다. 거리는 특정 노드에 도달하는 데 드는 비용의 척도이며, 임의의 두 노드 간의 최소 비용 경로는 최소 거리를 갖는 경로이다.[1]
업데이트는 주기적으로 수행되며, 라우터의 라우팅 테이블 전부 또는 일부가 인접 라우터로 전송된다. 정보를 받은 라우터는 자체 라우팅 테이블을 수정하여 변경 사항을 반영하고, 이를 다시 인접 라우터에 알린다. 이 과정은 '소문을 통한 라우팅'으로 설명되기도 하는데, 이는 라우터가 다른 라우터에서 받은 정보에 의존하며 정보의 유효성과 정확성을 확인할 수 없기 때문이다.[1]
2. 2. 주요 특징
거리 벡터 라우팅 프로토콜은 벨먼-포드 알고리즘을 사용한다. 각 라우터는 전체 네트워크 토폴로지에 대한 정보를 가지지 않고, 이웃 라우터까지의 거리 정보만을 가지고 동작한다. 라우팅 정보 교환은 주기적으로 또는 변경 이벤트가 발생할 때 이루어진다.[1]라우터는 다른 라우터에서 받은 정보를 바탕으로 자신의 라우팅 테이블을 업데이트하고, 이를 다시 이웃 라우터에게 알린다. 이 과정에서 라우터는 다른 라우터로부터 받은 정보의 정확성을 검증하지 않기 때문에 '소문을 통한 라우팅'이라고도 불린다.[1]
일부 거리 벡터 프로토콜은 네트워크 지연 시간과 같은 다른 트래픽 정보도 고려한다.[1]
3. 주요 거리 벡터 라우팅 프로토콜
거리 벡터 라우팅 프로토콜의 예시는 다음과 같다.
| 프로토콜 | 설명 |
|---|---|
| RIP | 1988년에 표준화된 가장 오래된 거리 벡터 프로토콜 중 하나이다.[5] 홉 수를 기준으로 최단 경로를 설정하며, 홉 수 제한이 15이므로 대규모 네트워크에는 적합하지 않다. |
| RIPv2 | RIP의 개선 버전이다. |
| RIPng | IPv6를 지원하는 RIP 버전 2의 확장이다. |
| IGRP | 시스코에서 개발한 독점 프로토콜이다. |
| EIGRP | 시스코에서 개발한 독점 프로토콜로, IGRP를 개선하였다. |
| BGP | WAN(광역 통신망)에서 사용하도록 설계된 프로토콜이다. 외부 게이트웨이 프로토콜이며, 인터넷의 경계 및 외부 라우터에서 구현된다.[6] |
| 바벨 | 또 다른 거리 벡터 라우팅 프로토콜이다. |
이 외에도 다양한 거리 벡터 라우팅 프로토콜이 존재하며, 각각 다른 특징과 용도를 가진다.
3. 1. RIP (Routing Information Protocol)
라우팅 정보 프로토콜(RIP)은 가장 오래된 라우팅 프로토콜 중 하나이자 가장 오래된 거리 벡터 프로토콜로, 1988년에 표준화되었다.[5] RIP는 홉 카운트(대상 네트워크에 도달하기 위해 통과해야 하는 라우터 수)를 기준으로 최단 경로를 결정한다. 내부 게이트웨이 프로토콜이므로 근거리 통신망(LAN) 내부 또는 경계 라우터에서 사용할 수 있다.RIPv1 프로토콜을 사용하는 라우터는 연결된 모든 네트워크에 30초마다 RIPv1 패킷을 브로드캐스트하여 인접 라우터와 라우팅 테이블을 교환한다. RIP는 라우팅 루프를 방지하기 위해 홉 수를 15로 제한하므로, 대규모 네트워크에는 적합하지 않다.[5] 15개 이상의 라우터를 통해 연결된 네트워크는 도달할 수 없다.[2]
RIP에는 RIPv1, RIPv2, 그리고 IPv6를 지원하는 RIPng (Routing Information Protocol Next Generation) 등의 버전이 있다.
3. 2. IGRP (Interior Gateway Routing Protocol)
내부 게이트웨이 라우팅 프로토콜(IGRP)은 시스코에서 개발한 독점 프로토콜이다. 홉 카운트 외에 대역폭, 지연 시간 등 다양한 요소를 고려하여 최단 경로를 결정하며, 라우팅 정보 프로토콜(RIP)보다 더 큰 규모의 네트워크에서 사용될 수 있다.3. 3. EIGRP (Enhanced Interior Gateway Routing Protocol)
EIGRP(향상된 내부 게이트웨이 라우팅 프로토콜)는 시스코에서 1980년대에 개발한 독점 프로토콜이다.[4] IGRP를 개선한 프로토콜로, 최단 경로 우선 열기(OSPF)보다 더 나은 수렴성을 제공하고 라우터 간의 네트워크 트래픽을 줄이도록 설계되었다.[4]EIGRP는 거리 벡터 프로토콜의 특징과 링크 상태 라우팅 프로토콜의 특징을 결합하여 하이브리드 프로토콜로 분류되기도 한다. DUAL(Diffusing Update Algorithm) 알고리즘을 사용하여 빠른 수렴 속도와 루프 없는 라우팅을 제공한다.
대한민국에서는 시스코 장비를 사용하는 네트워크 환경에서 EIGRP를 널리 사용한다.
3. 4. BGP (Border Gateway Protocol)
BGP(Border Gateway Protocol)은 WAN(광역 네트워크)에서 사용하도록 설계된 거리 벡터 프로토콜이다. BGP는 외부 게이트웨이 프로토콜이므로 인터넷의 경계 및 외부 라우터에서 구현된다.[6] TCP(Transmission Control Protocol) 세션을 통해 라우터 간에 정보를 교환한다. BGP가 구현된 라우터는 홉 이외의 다양한 요소를 기반으로 네트워크 전체에서 최단 경로를 결정한다. 관리자는 특정 경로를 선호하거나 피하도록 설정할 수도 있다. BGP는 인터넷 서비스 공급자(ISP)와 통신 회사에서 사용된다.[6]4. 무한대로의 카운트 문제
벨먼-포드 알고리즘은 라우팅 루프 발생을 막지 못하기 때문에 '''무한대로의 카운트 문제(Count to Infinity)'''가 발생할 수 있다.
이 문제를 간단히 설명하기 위해 A-B-C-D-E-F와 같이 연결된 네트워크를 생각해 보자. 각 라우터 간의 거리는 "점프 수"라고 가정한다. A가 오프라인 상태가 되면, B는 A로 가는 경로가 끊어졌음을 알게 된다. 그러나 C는 이 사실을 바로 알지 못하고, B에게 A까지 거리가 2라고 알려준다(C→B→A). B는 이 경로에 자신(B)이 포함된 것을 모르고, A까지의 거리를 3으로 갱신한다. 이후 B는 C에게 이 정보를 전달하고, C는 다시 A까지의 거리를 4로 갱신한다. 이 과정이 반복되면서 A까지의 거리는 무한대로 증가한다.
4. 1. 문제 발생 원인
벨먼-포드 알고리즘은 라우팅 루프 발생을 막지 못하여 무한대로의 카운트 문제(Count to Infinity) 가 발생할 수 있다. 이 문제는 라우터들이 서로에게 부정확한 거리 정보를 전달하면서 발생한다.A-B-C와 같이 연결된 네트워크에서 A가 오프라인 상태가 되는 경우를 예로 들어 설명하면 다음과 같다.
# B는 A와의 연결이 끊겼음을 감지한다.
# C는 A가 다운되었다는 사실을 즉시 알지 못하고, B에게 A까지의 거리가 2라고 알린다. (C → B → A)
# B는 C가 알려준 경로에 자신(B)이 포함되어 있다는 사실을 모르고, A까지의 거리를 3으로 갱신한다. (B → C → B → A)
# 이후 B는 C에게 업데이트된 정보를 전달하고, C는 A까지의 거리를 4로 갱신한다. (C → B → C → B → A)
# 이 과정이 반복되면서 A까지의 거리가 무한대로 증가한다.
이러한 무한대까지 세는 문제의 핵심은, 어떤 라우터가 다른 라우터에게 특정 경로가 있다고 알려줄 때, 그 경로에 자신이 포함되어 있는지 알 수 없다는 것이다.
4. 2. 해결 방안
이 문제를 해결하기 위해 다양한 기법들이 개발되었다. 대표적인 방법으로는 수평 분할과 포이즌 리버스가 있다.RIP는 라우팅 루프를 줄이기 위해 분할 지평선 경로 광고 기술과 최대 홉 수 제한을 사용한다. 홀드 타임(경로 철회 후 몇 분 동안 경로 업데이트 거부)을 추가하면 거의 모든 경우에서 루프 형성을 방지하지만, 컨버전스 시간이 상당히 증가한다.
최근에는 루프 문제를 해결한 거리 벡터 프로토콜이 다수 개발되었다. EIGRP, DSDV, Babel 등이 그 예시이다. 이러한 프로토콜은 루프 형성을 방지하지만 복잡성이 증가한다는 단점이 있다.
4. 2. 1. 수평 분할 (Split Horizon)
경로 정보를 받아온 노드에는 다시 정보를 보내지 않도록 하는 방식이다.하지만 수평 분할에는 한 가지 단점이 있다. 보통 거리 벡터 알고리즘 프로토콜은 타이머를 사용하고, 경로상에 새로운 소식이 없으면 테이블에서 경로를 제거한다. 이 때문에 C가 B로 보내는 광고에 A로의 경로를 제거해버리면 B는 이것이 수평 분할 정책 때문인지, 아니면 C가 최근에 A에 관한 소식을 받지 못해서인지 예측할 수 없다.
RIP는 루프 형성 가능성을 줄이기 위해 분할 지평선 경로 광고 기술을 사용하며, '무한대까지 세기' 문제를 해결하기 위해 최대 홉 수를 사용한다. 이러한 조치들은 일부 경우, 특히 모든 경우에서 라우팅 루프 형성을 방지한다.[1]
4. 2. 2. 포이즌 리버스 (Poison Reverse)
포이즌 리버스는 수평 분할에서 일어나는 문제를 해결할 수 있는 방법이다. C가 A에 대한 정보를 광고할 때, 만약 송신자가 노드 A인 경우 거리값을 무한대로 설정해서 해당 경로 정보가 사용되지 않도록 한다.4. 2. 3. 최대 홉 카운트 제한
RIP는 라우팅 루프 형성 가능성을 줄이기 위해 분할 지평선 경로 광고 기술을 사용하고, '무한대까지 세기' 문제를 해결하기 위해 최대 홉 수 제한을 사용한다. 이러한 조치들은 일부 경우에 라우팅 루프 형성을 방지한다.4. 2. 4. Hold-down Timer
RIP는 루프 형성 가능성을 줄이기 위해 분할 지평선 경로 광고 기술을 사용하며, '무한대까지 세기' 문제를 해결하기 위해 최대 홉 수를 사용한다. 이러한 조치들은 일부 경우에서 라우팅 루프 형성을 방지한다.[1] 홀드 타임(경로 철회 후 몇 분 동안 경로 업데이트 거부)을 추가하면 거의 모든 경우에서 루프 형성을 방지하지만, 컨버전스 시간이 상당히 증가한다.5. 예제
거리 벡터 라우팅 프로토콜은 4개의 라우터 A, B, C, D로 구성된 네트워크에서 동작한다.
알고리즘의 현재 시간(또는 반복)을 T로 표시한다. T=0일 때, 각 라우터는 직접 연결된 이웃 라우터까지의 거리를 나타내는 행렬을 초기화한다.
아래 표에서 최단 경로는 녹색, 새로운 최단 경로는 노란색으로 표시된다. 회색 열은 현재 노드의 이웃이 아닌 노드를 나타내므로 무시한다. 빨간색 칸은 노드 자신으로의 경로를 나타내므로 사용하지 않는다.
{| class="wikitable"
|-
| T=0
|
| A로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to B | bgcolor="#DD5555"| | 3 | bgcolor="#C0C0C0"| | |
| to C | bgcolor="#DD5555"| | 23 | bgcolor="#C0C0C0"| | |
| to D | bgcolor="#DD5555"| | bgcolor="#C0C0C0"| |
|
| B로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 3 | bgcolor="#DD5555"| | bgcolor="#C0C0C0"| | |
| to B | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to C | bgcolor="#DD5555"| | 2 | bgcolor="#C0C0C0"| | |
| to D | bgcolor="#DD5555"| | bgcolor="#C0C0C0"| |
|
| C로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 23 | bgcolor="#DD5555"| | ||
| to B | 2 | bgcolor="#DD5555"| | ||
| to C | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to D | bgcolor="#DD5555"| | 5 |
|
| D로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | bgcolor="#DD5555"| | |
| to B | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | bgcolor="#DD5555"| | |
| to C | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 5 | bgcolor="#DD5555"| |
| to D | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
|-
|colspan=5| T=0에서 각 라우터는 자신의 거리 벡터(DV)를 이웃에게 알린다. 예를 들어, A는 C에게 "C에서 D까지의 거리는 5"라는 정보를 전달하고, A에서 D까지의 최단 경로는 5+23=28로 계산되어 갱신된다.
|
|-
| T=1
|
| A로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to B | bgcolor="#DD5555"| | 3 | 25 | bgcolor="#C0C0C0"| |
| to C | bgcolor="#DD5555"| | 5 | 23 | bgcolor="#C0C0C0"| |
| to D | bgcolor="#DD5555"| | 28 | bgcolor="#C0C0C0"| |
|
| B로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 3 | bgcolor="#DD5555"| | 25 | bgcolor="#C0C0C0"| |
| to B | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to C | 26 | bgcolor="#DD5555"| | 2 | bgcolor="#C0C0C0"| |
| to D | bgcolor="#DD5555"| | 7 | bgcolor="#C0C0C0"| |
|
| C로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 23 | 5 | bgcolor="#DD5555"| | |
| to B | 26 | 2 | bgcolor="#DD5555"| | |
| to C | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to D | bgcolor="#DD5555"| | 5 |
|
| D로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 28 | bgcolor="#DD5555"| |
| to B | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 7 | bgcolor="#DD5555"| |
| to C | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 5 | bgcolor="#DD5555"| |
| to D | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
|-
|colspan=5| T=1에서 각 라우터는 이전 단계에서 얻은 정보를 바탕으로 다시 DV를 이웃에게 알린다. A는 B로부터 "B에서 D까지의 거리는 7"이라는 정보를 받고, A에서 D까지의 최단 경로를 7+3=10으로 갱신한다.
|
|-
| T=2
|
| A로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to B | bgcolor="#DD5555"| | 3 | 25 | bgcolor="#C0C0C0"| |
| to C | bgcolor="#DD5555"| | 5 | 23 | bgcolor="#C0C0C0"| |
| to D | bgcolor="#DD5555"| | 10 | 28 | bgcolor="#C0C0C0"| |
|
| B로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 3 | bgcolor="#DD5555"| | 7 | bgcolor="#C0C0C0"| |
| to B | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to C | 8 | bgcolor="#DD5555"| | 2 | bgcolor="#C0C0C0"| |
| to D | 31 | bgcolor="#DD5555"| | 7 | bgcolor="#C0C0C0"| |
|
| C로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 23 | 5 | bgcolor="#DD5555"| | 33 |
| to B | 26 | 2 | bgcolor="#DD5555"| | 12 |
| to C | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to D | 51 | 9 | bgcolor="#DD5555"| | 5 |
|
| D로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 10 | bgcolor="#DD5555"| |
| to B | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 7 | bgcolor="#DD5555"| |
| to C | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 5 | bgcolor="#DD5555"| |
| to D | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
|-
|colspan=5| T=2에서는 A와 D만 새로운 최단 경로 정보를 갖게 되어 DV를 이웃에게 알린다. 하지만 이 정보는 이미 라우팅 테이블에 반영되어 있거나 더 짧은 경로가 아니므로, 라우팅 테이블은 변경되지 않는다.
|
|-
| T=3
|
| A로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to B | bgcolor="#DD5555"| | 3 | 25 | bgcolor="#C0C0C0"| |
| to C | bgcolor="#DD5555"| | 5 | 23 | bgcolor="#C0C0C0"| |
| to D | bgcolor="#DD5555"| | 10 | 28 | bgcolor="#C0C0C0"| |
|
| B로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 3 | bgcolor="#DD5555"| | 7 | bgcolor="#C0C0C0"| |
| to B | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to C | 8 | bgcolor="#DD5555"| | 2 | bgcolor="#C0C0C0"| |
| to D | 13 | bgcolor="#DD5555"| | 7 | bgcolor="#C0C0C0"| |
|
| C로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | 23 | 5 | bgcolor="#DD5555"| | 15 |
| to B | 26 | 2 | bgcolor="#DD5555"| | 12 |
| to C | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
| to D | 33 | 9 | bgcolor="#DD5555"| | 5 |
|
| D로부터 | via A | via B | via C | via D |
|---|---|---|---|---|
| to A | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 10 | bgcolor="#DD5555"| |
| to B | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 7 | bgcolor="#DD5555"| |
| to C | bgcolor="#C0C0C0"| | bgcolor="#C0C0C0"| | 5 | bgcolor="#DD5555"| |
| to D | bgcolor="#EE5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| | bgcolor="#DD5555"| |
|-
|colspan=5| T=3에서는 더 이상 새로운 최단 경로 정보가 없으므로, 알고리즘은 종료된다.
|}
참조
[1]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
[2]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
[3]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
[4]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
[5]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
[6]
서적
Network+ Guide to Networks
https://archive.org/[...]
Cengage Learning
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com