Routing Algorithms

상위 문서: Network Layer

개요

라우팅 알고리즘(Routing algorithm)이란 송신 호스트에서 수신 호스트까지의 "좋은(good)" 경로(path)들을 결정하는 알고리즘을 의미한다. 경로란 패킷이 출발지 호스트에서 목적지 호스트까지 이동할 때 거치는 라우터들의 순서를 의미한다. 이때 "좋은" 경로의 기준은 가장 비용이 적거나(least "cost"), 가장 빠르거나("fastest"), 가장 혼잡하지 않은("least congested") 경로를 의미한다.

Network graph notation

Figure 1. Abstract graph model of a computer network

이때 라우팅 알고리즘은 figure 1과 같이 그래프를 사용하여 형식화된다. 그래프 G = (N, E)는 노드들의 집합 N과 간선(edge)들의 모음 E로 구성되며, 각 간선은 N에 속한 두 노드의 쌍이다. 이는 아래와 같이 나타내어 진다.

N = set of routers = {u, v, w, x, y, z}
E = set of links ={(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)}

이때 그래프의 각 노드는 라우터를 의미하며, 간선은 해당 라우터들 간의 물리적인 링크(link)를 의미한다. 간선은 해당 링크의 비용을 나타내는 값을 가진다. 일반적으로 간선의 비용은 해당 링크의 물리적인 길이와 링크의 혼잡도 등에 의해 결정된다. 이때 각 간선과 경로의 비용은 다음과 같이 표기한다.

(x, y) $\in$ E, c(x,y) = cost of link (x,y) 
(x, y) $\notin$ E, c(x,y) = $\mathrm{\infty }$ //해당 간선은 존재하지 않음
cost of path (x2, x2, x3, ⋯, xp) = c(x1,x2) + c(x2,x3) + ⋯ + c(xp-1,xp)  

Routing algorithm classification

라우팅 알고리즘을 분류하는 한가지 방식은 중앙 집중형 라우팅 알고리즘(centralized routing algorithm)과 분산형 라우팅 알고리즘(decentralized routing algorithm)으로 구분하는 것이다. 라우팅 알고리즘을 분류하는 두 번째 방식은 그것이 정적(static)이냐 동적(dynamic)이냐에 따른 것이다.

Centralized vs. Decentralized

중앙 집중형 라우팅 알고리즘은 네트워크에 대한 전체적이고 전역적인 정보(topology)를 이용하여 출발지와 목적지 간의 최소 비용 경로를 계산한다. 따라서 해당 알고리즘은 모든 노드 간의 연결 정보와 각각의 링크의 비용을 필요로 한다. 해당 알고리즘은 흔히 LS(link-state) 알고리즘이라고 불린다.

분산형 라우팅 알고리즘은 각각의 라우터 들에 의해서 반복적이고 분산된 방식으로 수행된다. 이때 어떠한 노드도 전체 네트워크의 LS에 대한 완전한 정보를 가지고 있지 않다. 대신 각 노드는 자신에게 직접 연결된 링크들의 비용만 알고 있으므로, 각 노드는 이웃 노드들과의 정보 교환과 계산을 반복하여 최소 비용 경로를 점진적으로 계산한다. 해당 알고리즘은 흔히 DV(distance-vector) 알고리즘이라고 불린다. 왜냐하면 각 노드는 네트워크 내의 다른 모든 노드에 대한 비용의 추정치를 벡터 형태로 유지하기 때문이다.

Static vs. Dynamic

정적 라우팅 알고리즘에서는 패킷의 경로가 시간에 따라 매우 느리게 변화하며, 보통 사람의 개입을 통해서 변경된다. 반면 동적 라우팅 알고리즘은 네트워크 트래픽 부하나 topology가 변할 때 라우팅 경로를 변경한다. 동적 알고리즘은 주기적으로 실행되거나 해당 변화에 직접적으로 반응하여 구현된다. 동적 알고리즘은 네트워크 변화에 더 잘 반응할 수 있지만, 라우팅 루프(routing loop)나 경로 진동(route oscillation) 같은 문제에 더 취약할 수 있다.

LS routing algorithm

LS 라우팅 알고리즘 중 가장 일반적인 알고리즘은 Dijkstra 알고리즘이다. 다익스트라 알고리즘은 네트워크 topology와 모든 링크 비용을 바탕으로 출발 노드(u)에서 다른 모든 노드들까지의 최소 비용 경로를 계산한다. 이때 각 노드는 자신과 연결된 링크들의 식별자와 비용을 담은 링크 상태 패킷(link-state packet)을 네트워크 내의 모든 다른 노드들에게 브로드캐스트(LS broadcast)하여 이를 구현할 수 있다. 다익스트라 알고리즘은 반복적이며, 알고리즘의 k번째 반복이 끝난 후에는, 목적지 노드 k개에 대한 최소 비용 경로가 계산된다는 특징이 있다. 이때 다익스트라 알고리즘을 설명하기 위한 표기는 다음과 같다:

D(v): 알고리즘의 현재 단계에서 출발 노드에서 목적지 노드 v까지의 최소 비용 경로의 비용
p(v): 출발 노드에서 목적지 노드 v까지의 현재 단계의 최소 비용 경로에서 v 직전 노드
N': 최소 비용 경로가 확정된 노드들의 부분집합이다. 즉, v $\in$ N'는 출발 노드에서 v까지의 최소 비용 경로가 확정되었음을 의미한다.

다익스트라 알고리즘은 다음과 같다.

Initialization:
N' = {u}
//출발 노드 u와 인접한 노드들에서의 경로 비용을 계산한다.
for all nodes v
    if v is a neighbor of u
        then D(v) = c(u,v)
    else D(v) = ∞

Loop
find w not in N' such that D(w) is a minimum
add w to N'
//N'에 포함되지 않은 모든 노드들에 대해서 D(v)를 계산한다.
update D(v) for each neighbor v of w and not in N':
    //노드 v에 대한 새로 계산된 비용은 이전 단계에서의 비용, 혹은 u ~ w의 경로 비용에 c(w,v)를 더한 값이다.
    D(v) = min(D(v), D(w) + c(w,v))
until N' = N

다익스트라 알고리즘은 초기화 단계와 반복 루프로 구성되며, 해당 알고리즘은 네트워크에 있는 노드 수 만큼 반복된다. 알고리즘이 종료되면 출발 노드 u에서 네트워크 내의 다른 모든 노드들까지의 최단 경로가 계산된다. Figure 2를 기준으로 최단 경로를 계산하면, 그 결과는 아래 표와 같다.

Figure 2. Dijkstra’s algorithm Example

Step	N'	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
0	u	2, u	5, u	1, u	∞	∞
1	ux	2, u	4, x		2, x	∞
2	uxy	2, u	3, y			4, y
3	uxyv		3, y			4, y
4	uxyvw					4, y
5	uxyvwz