[컴퓨터 네트워크] 거리 벡터(Distance Vector) 라우팅 알고리즘

인터넷: 가중치 그래프(Weighted Graph)

• 라우터들을 비용이 매겨진 링크로 연결한 그래프
• 링크의 유형에 따라 링크 사용 비용에 차이
• 라우터가 선호하는 링크의 비용이 낮다.
• 최소경로비용: 출발지 라우터와 목적지 라우터를 연결하는 경로 중에 링크 비용의 합이 가장 작은 경로
• 링크 비용: c(u, x) = 1, 최소경로비용 D_uz = 4

인터넷 라우팅: Hob-by-Hop

• 라우터들을 비용이 매겨진 링크로 연결한 그래프에서 출발지 라우터에서 목적지 네트워크의 라우터까지 최소 비용 경로를 찾는다.
• 최소 비용 경로 상의 다음 라우터의 주소를 라우팅 테이블에 저장한다.

거리 벡터(Distance Vector)

• 특정 라우터에서 다른 모든 라우터까지의 최소 경로 비용을 갖는 1열 벡터
• u[ ]: 라우터 u의 전체 거리 벡터
• u[x]: 라우터 u에서 라우터 x까지 거리(최소 경로 비용), 네트워크의 각 라우터가 거리 벡터의 인덱스

초기 거리 벡터: 라우터 연결 시점의 거리 벡터

• 직접 연결 라우터(이웃) 거리: 링크 비용, 간접 연결 라우터 거리: ∞

거리 벡터 공유를 통한 거리 벡터 갱신: x → u로 거리 벡터 전달

• u[ ] = min(u[ ], c(u, x) + x[ ])

벨먼-포드 방정식(Bellman-Ford Equation)

• D_xy: 라우터 x에서 라우터 y까지의 최소 경로 비용
• c(x, v): 라우터 x에서 이웃 라우터 v까지 링크 비용
• D_xy = min_v{c(x, v) + D_vy}, v는 x의 모든 이웃 라우터

개념: 분산 라우팅(Distributed Routing)

1. 이웃 라우터와 자신의 초기 거리 벡터 공유
2. 이웃 라우터의 거리 벡터와 벨먼-포드 방정식으로 자신의 거리 벡터 갱신
3. 갱신된 거리 벡터를 이웃 라우터에 전달

거리 벡터 갱신

• u의 거리벡터의 z항: Duz
• D_uz 갱신: 이웃 (v, w, x)의 거리 벡터 공유 정보로 갱신
• D_uz = min_k{D_uz, c(u, k) + D_kz}, k는 u의 모든 이웃 라우터
• D_uz = min{∞, 2+5, 5+3, 1+3) = 4

무한 계산 문제

• 이웃 라우터를 경유하는 경로로 최소 경로 비용을 갱신하고, 해당 이웃 라우터에게 다시 전송하는 과정이 반복되는 문제

문제 발생 이유

• 링크가 고장나거나 비용이 증가할 때 발생
• 이웃 라우터가 자신을 경유하는 최소 경로 비용 전송
• 2개의 이웃 라우터 간에 순환 경로(loop path) 발생

포이즌 리버스(Poison Reverse)

• 상대방 이웃 라우터를 경유하는 최소 경로 비용을 ∞로 변경하여 통보

3개 노드 불완전성 문제

• 3개 이상의 라우터 간 순환 경로 발생 시 포이즌 리버스가 무한 계산 문제 완전 해결 불가하다.