5.2 Routing Algorithms

라우팅 알고리즘의 목표는 **발신지에서 수신지까지 데이터를 전달하는 최적의 경로(즉, 루트)**를 결정하는 것이다.

여기서 “최적의 경로”란 비용이 가장 적은 경로를 뜻한다. 책에서는 이를 다양한 조건에서 다룬다.

 

라우팅 문제를 그래프(Graph)로 추상화하기

 

라우팅 문제를 설명하기 위해 그래프를 사용한다. 그래프란 다음과 같이 정의된다:

• 노드(Node): 네트워크에서 라우터를 나타낸다.

• 엣지(Edge): 라우터 간의 실제 물리적 링크를 나타낸다.

예를 들어, 책의 Figure 5.3에 나타난 그래프는 네트워크의 추상적 모델이다.

그림에서는 노드들이 라우터를 나타내고, 라우터를 연결하는 선은 물리적 연결(링크)을 나타낸다.

 

엣지의 비용(Cost)

 

엣지는 비용 값을 가진다. 이 비용은 다음과 같은 것을 나타낼 수 있다:

• 링크의 물리적 길이: 긴 링크일수록 비용이 크다.

• 링크의 속도: 느린 링크일수록 비용이 크다.

• 금전적 비용: 네트워크를 유지하는데 드는 실제 비용.

 

최소 비용 경로 (Least-Cost Path)

 

라우팅 알고리즘은 보통 최소 비용 경로를 찾는 문제로 변환된다.

예를 들어, 그래프 상의 두 노드 간 최소 비용 경로는 다음과 같이 계산한다:

1. 노드 간 여러 경로 중, 비용의 합이 가장 작은 경로를 선택한다.

2. 각 엣지의 비용을 합산하여 경로의 총 비용을 계산한다.

 

Figure 5.3 예시

 

• 노드 u에서 z까지의 최소 비용 경로를 찾는 문제를 살펴보자.

• 그림에서 비용은 엣지에 표시되어 있다.

• 가장 비용이 적은 경로는 u->x->y->z로, 총 비용은 5이다.

 

라우팅 알고리즘의 분류

 

라우팅 알고리즘은 크게 두 가지 방식으로 분류된다:

1. 중앙집중식 라우팅(Centralized Routing):

• 네트워크에 대한 전체 정보를 단일 위치에서 수집하고 처리한다.

• 예를 들어, 특정 컴퓨터나 라우터가 모든 정보를 가지고 경로를 계산한다.

• Link-State (LS) 알고리즘이 대표적이다.

 

2. 분산형 라우팅(Decentralized Routing):

• 라우터가 각자 인접한 라우터와 정보만 교환하며 경로를 계산한다.

• 네트워크 전체 정보를 알 필요가 없다.

• Distance-Vector (DV) 알고리즘이 대표적이다.

 

다음으로 **Link-State 알고리즘(LS 알고리즘)**의 동작 방식을 설명하겠다. 이는 책에서 5.2.1 섹션에 다루어진다. LS 알고리즘은 Dijkstra 알고리즘을 기반으로 최소 비용 경로를 계산한다.

 

5.2.1 링크 상태(Link-State, LS) 알고리즘

 

Link-State 알고리즘은 네트워크의 전체 토폴로지(네트워크 구성도)와 링크의 비용 정보를 알고리즘에 입력하여 최소 비용 경로를 계산한다. 네트워크의 모든 노드가 동일한 정보를 공유하기 때문에, 각 노드는 동일한 결과를 계산하여 동일한 라우팅 테이블을 구성한다.

 

링크 상태 알고리즘의 주요 과정

 

LS 알고리즘은 네 단계로 이루어진다:

1. 링크 상태 정보 수집:

• 각 노드는 자신과 연결된 링크의 비용을 계산하여 “링크 상태 패킷”을 생성한다.

• 이 패킷은 네트워크 상의 모든 노드에 브로드캐스트 된다.

• 결과적으로 모든 노드가 네트워크의 전체 토폴로지 정보를 갖게 된다.

2. 네트워크 전체 정보를 기반으로 경로 계산:

• LS 알고리즘은 Dijkstra 알고리즘을 사용하여 한 노드에서 모든 목적지 노드까지의 최소 비용 경로를 계산한다.

 

Dijkstra 알고리즘

 

Dijkstra 알고리즘은 하나의 소스 노드에서 네트워크의 모든 다른 노드로 가는 최소 비용 경로를 계산하는데 사용된다. 이 알고리즘은 반복적이고, 매 단계에서 가장 적은 비용으로 갈 수 있는 새로운 노드를 선택한다.

 

Dijkstra 알고리즘의 주요 변수

 

• D(v): 소스 노드에서 노드 까지의 현재까지 계산된 최소 비용 경로.

• p(v): 노드 까지의 경로에서 바로 이전 노드.

• N': 이미 최소 비용 경로가 확정된 노드의 집합.

 

알고리즘 단계

 

1. 초기화:

• 소스 노드 의 비용을 0으로 설정 (D(u) = 0).

• 다른 모든 노드의 비용을 무한대로 설정.

• 소스 노드 u를 N'에 추가.

2. 반복:

•  N{\prime} 에 포함되지 않은 노드 중에서  D(v) 가 최소인 노드  w 를 선택.

•  w 를  N' 에 추가.

•  w 의 모든 이웃 노드  v 에 대해:

•  D(v) = min(D(v), D(w) + c(w, v)) 로 업데이트.

• 여기서  c(w, v) 는  w 와  v  사이의 링크 비용.

3.  N' 에 모든 노드가 포함될 때까지 반복.

 

예제: Figure 5.3의 그래프

 

책에 나와 있는 Figure 5.3의 그래프를 사용하여 Dijkstra 알고리즘을 실행해 보자. 노드 를 소스로 설정한다.

 

초기화 단계:

 

•  D(u) = 0 ,  D(v) = 2 ,  D(w) = 5 ,  D(x) = 1 ,  D(y) = ∞,  D(z) = ∞ .

•  N'= {u} .

 

반복 과정:

 

1. 비용이 가장 낮은 x를 선택하고, N' = {u,x}로 업데이트.

2.  x 를 통해 갈 수 있는 경로를 계산하여  D(y) = 3 ,  D(w) = 4 로 업데이트.

3. 비용이 가장 낮은  y 를 선택하고,  N' = {u, x, y} 로 업데이트.

4.  y 를 통해  z 의 비용을 계산하여  D(z) = 4 로 업데이트.

 

최종 라우팅 테이블

 

최종적으로 각 노드로 가는 최소 비용 경로가 결정되고, 이를 기반으로 포워딩 테이블을 생성한다. 예를 들어:

• 목적지  v :  u -> v .

• 목적지  z :  u -> x -> y -> z .

책의 Figure 5.4는 이 포워딩 테이블을 시각적으로 보여준다.

 

계산 복잡도

 

Dijkstra 알고리즘의 복잡도는 O(n^2) $이다. 즉, 네트워크에 있는 노드 수가 많아질수록 계산량이 제곱으로 증가한다. 이 복잡도는 힙(Heap) 자료구조를 사용하여 개선할 수 있다.

 

문제점: 네트워크 진동(Oscillation)

 

Figure 5.5에서는 LS 알고리즘에서 발생할 수 있는 문제를 보여준다.

링크 비용이 트래픽에 따라 변동하면, 라우터들이 서로 다른 경로를 반복적으로 선택하며 진동이 발생할 수 있다.

 

해결책:

 

• 링크 비용을 트래픽과 독립적으로 설정한다.

• 라우터가 서로 다른 시간에 링크 상태 정보를 업데이트하도록 설정한다.

 

 

Distance-Vector (DV) 알고리즘

 

DV 알고리즘은 분산형 라우팅 알고리즘의 대표적인 예이다. 이 알고리즘은 라우터들이 자신의 인접 라우터들과만 정보를 교환하며 점진적으로 최적 경로를 계산한다.

 

DV 알고리즘의 기본 원리

 

1. 각 라우터는 자신의 **거리 벡터(Distance Vector)**를 유지한다.

• 거리 벡터는 네트워크 상의 다른 모든 노드로 가는 경로의 최소 비용을 나타낸다.

• 예: 노드  A 의 거리 벡터가  [0, 1, 3, ∞] 라면 이는  A 에서 다른 노드  A, B, C, D 로의 최소 비용 경로가 각각  0, 1, 3, ∞임을 나타낸다.

2. 각 라우터는 주기적으로 자신의 거리 벡터를 인접 라우터에 전달한다.

• 이웃 라우터들은 받은 거리 벡터를 사용해 자신의 거리 벡터를 갱신한다.

3. 반복적으로 거리 벡터를 업데이트한 뒤, 네트워크 전체가 **수렴(Convergence)**하면 최적 경로가 결정된다.

 

DV 알고리즘의 주요 과정

 

DV 알고리즘의 문제점

 

1. Count-to-Infinity 문제:

• 네트워크의 일부 링크가 실패했을 때, 라우터들이 무한히 큰 거리 값을 계산하며 잘못된 정보가 전파될 수 있다.

• 예를 들어, 라우터  A 와  B 가 서로  Z 로 가는 경로를 가지고 있다고 잘못 계산하며, 무한히 큰 거리 값을 주고받을 수 있다.

2. 수렴 속도:

• LS 알고리즘에 비해 수렴 속도가 느리다. 특히, 네트워크 장애 상황에서 복구 시간이 오래 걸릴 수 있다.

 

해결책: Split Horizon

 

Split Horizon은 Count-to-Infinity 문제를 완화하기 위한 기법이다:

• 라우터는 자신에게서 온 경로 정보를 다시 되돌려 보내지 않는다.

• 예를 들어,  A -> B 를 통해  C 로 가는 경로를 계산한 경우,  B 는  A 에게  C  경로 정보를 보내지 않는다.

DV 알고리즘의 응용

 

DV 알고리즘은 단순성과 효율성 때문에 다음과 같은 네트워크 프로토콜에서 널리 사용된다:

• RIP (Routing Information Protocol): 소규모 네트워크에서 DV 알고리즘을 사용.

• EIGRP (Enhanced Interior Gateway Routing Protocol): DV 알고리즘을 개선한 하이브리드 방식.