5.2 라우팅 알고리즘

5.2 라우팅 알고리즘

 

-라우팅 알고리즘의 목표 : 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로(루트)를 결정하는 것.

 

-좋은 경로 = 최소 비용 경로

그러나 현실적으로는 네트워크 정책과 같은 실제 문제가 고려됨을 보게 될 것이다.

 

 

라우팅 문제를 나타내는 데는 그래프가 사용된다.

그래프 표현 : G(N, E)

 

 

-N(node) :

 

라우터

 

 

-E(edge) :

 

라우터들 간의 물리 링크

 

엣지는 그 비용을 나타내는 값을 갖는다. 위 그림에서 선에 나타난 숫자값.

(비용은 일반적으로 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영한다.)

 

집합 E에 포함된 어떤 에지 (x, y)에 대해 c(x, y)는 노드 x와 y 간의 비용을 의미한다.

 

만약 노드 쌍 (x, y)가 E에 포함되어 있지 않으면 c(x, y) = 무한대 로 둔다.

ex) 위 그림에서 c(u, z) = 무한대이다. u에서 z로 한번에 바로 갈 수 없기 때문에.

 

에지 (x, y)가 집합 E에 속하면, 노드 y는 노드 x의 이웃(neighbor)이라고 한다.

 

경로(path) :  그래프 G(N, E)에서의 경로는 노드의 연속(x1, x2, x3, …, xp)이다.

 

노드 쌍 (x1, x2), (x2, x3), … , (xp-1, xp)는 집합 E에 속한 에지들이다.

 

경로 (x1, x2, x3, … , xp)의 비용은 경로상 모든 에지 비용의 단순 합이다.
c(x1, x2) + c(x2, x3) + … + c(xp-1, xp)

 

 

-라우팅 알고리즘 분류

 

1. 중앙 집중형 라우팅 알고리즘(centralized routing algorithm)

 

네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다.

 

계산 자체는 한 장소(논리적 중앙 집중형 제어)에서 수행되거나 모든 라우터 각각의 라우팅 모듈로 복사(라우터별 제어)될 수 있다.

 

전체 상태 정보를 갖는 알고리즘을 링크 상태(link-state, LS) 알고리즘이라고 하는데,
이는 이 알고리즘이 네트워크 내 각 링크의 비용을 알고 있어야 하기 때문이다.

 

 

2. 분산 라우팅 알고리즘(decentralized ~)

 

각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다.

 

최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.

 

반복된 계산과 이웃 노드와의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지의 최소 비용 경로를 계산한다.

 

분산 라우팅 알고리즘은 거리 벡터(distance-vector, DV) 알고리즘이라고도 하는데,
이는 각 노트가 네트워크 내 다른 모든 노드까지 비용(거리)의 추정값을 벡터 형태로 유지하기 때문이다.

 

 

 

1. 정적 라우팅 알고리즘(static ~)

 

사람이 직접 링크 비용을 수정하는 경우처럼 종종 사람이 개입하는 상황 때문에 정적 라우팅 알고리즘에서 경로는 아주 느리게 변한다.

 

 

2. 동적 라우팅 알고리즘(dynamic ~)

 

네트워크 트래픽 부하(load)나 토폴로지 변화에 따라 라우팅 경로를 바꾼다.

 

동적 알고리즘은 주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.

 

네트워크 변화에 빠르게 대응한다는 장점도 있지만, 경로의 루프나 경로 진동(oscillation) 같은 문제에 취약하기도 하다.

 

 

1. 부하에 민감한 알고리즘(load-sensitive ~)

 

링크 비용은 해당 링크의 현재 혼잡 수준을 나타내기 위해 동적으로 변한다.

 

현재 혼잡한 링크에 높은 비용을 부과한다면, 라우팅 알고리즘은 혼잡한 링크를 우회하는 경로를 택하는 경향을 보일 것이다.

 

 

2. 부하에 민감하지 않은 알고리즘(load-insensitive ~)

 

오늘날 인터넷 라우팅 알고리즘(RIP, OSPF, BGP 등)은 링크 비용이 현재(또는 가장 최근)의 혼잡을 반영하지 않기 때문에 부하에 민감하지 않다.

 

 

 

5.2.1 링크 상태(LS) 라우팅 알고리즘

 

링크 상태 알고리즘에서는 네트워크 토폴로지와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다.

 

이것은 각 노드가 자신과 직접 연결된 링크의 식별자와 비용 정보를 담은 링크 상태 패킷을 네트워크상의 다른 모든 노드로 브로드캐스트하게 함으로써 가능하며,

 

-다익스트라 알고리즘(Dijkstra's algorithm)

 

다익스트라 알고리즘은 하나의 노드(출발지, u라고 지칭)에서 네트워크 내 다른 모든 노드로의 최소 비용 경로를 계산한다.

 

알고리즘의 k번째 반복 이후에는 k개의 목적지 노드에 대해 최소 비용 경로가 알려지며,
이들은 모든 목적지 노드로의 최소 비용 경로 중에서 가장 낮은 비용을 갖는 k개의 경로다.

 

기호

D(v) : 알고리즘의 현재 반복 시점에서 출발지 노드부터 목적지 v까지의 최소 비용 경로의 비용

p(v) : 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드

N' : 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있는 노드의 집합

 

-출발지 노드 u를 위한 링크 상태(LS) 알고리즘

 

 

 

u와 직접 연결된 이웃 v, x, w까지의 현재 알려진 최소 비용 경로는 각각 2, 1, 5로 초기화된다.

y, z는 직접 연결되어 있지 않기 때문에 무한대.

 

첫 번째 반복에서는 N' 집합에 아직 포함되지 않은 노드 중에서 이전 반복이 끝난 시점의 최소 비용을 가진 노드를 찾는다. 위 그림에서는 최소 비용 노드는 비용 1을 갖는 x이므로 x를 N'에 추가한다.

다시 또 최소 비용 노드를 찾고 갱신을 반복 해주면 위와 같은 표를 만들 수 있다.

 

 

노드 u의 포워딩 테이블은 각 목적지에 대해 / 노드 u에서 그 목적지까지의 최소 비용 경로상의 다음 홉 노드 정보를 저장하여 구성한다.

 

위 그림은 최소 비용 경로의 결과와 노드 u의 포워딩 테이블을 보여준다.

 

 

계산 복잡도 :

 

링크 상태 알고리즘은 최악의 경우 O(n^2)의 복잡성을 갖는다.

 

 

진동(oscillation) 문제

 

링크 상태 알고리즘이 수행되면 노드 c는 a로 가는 시계 방향의 경로 비용이 1인 반면,
지금까지 사용해왔던 반시계 방향으로의 경로 비용은 1+e임을 알게 된다.

 

따라서 a로 가는 c의 최소 비용 경로는 시계 방향이며,
b도 마찬가지로 a로 가는 시계 방향 경로를 새로운 최소 비용 경로로 결정한다.

 

 

링크 상태 알고리즘이 다시 한번 수행되면
노드 b, c, d 모두 a로 가는 반시계 방향의 경로 비용이 0임을 알게 되어 모든 트래픽을 반시계 방향 경로로 보낸다.

 

 

다음번 링크 상태 알고리즘 수행 시에는 x, y, z 모두 시계 방향으로 트래픽을 전송한다.

 

 

5.2.2 거리 벡터(DV) 라우팅 알고리즘

 

벨만-포드(Bellman-Ford) 식

 

d가 소문자일 경우 실제 값, D가 대문자일 경우 추정치

 

 

-min.v는 x의 모든 이웃에 적용된다.

 

-x에서 v(x의 이웃)로 이동한 후, v에서 y까지의 최소 비용 경로를 택한다면, 경로 비용은 c(x, v) + d.v(y)일 것이다.

 

-반드시 하나의 이웃 v로 가는 것부터 시작해야 하므로,

 

x에서 y까지의 최소 비용은 모든 이웃 노드 v에 대해 계산된 c(x, v) + d.v(y) 중 최솟값이 된다.

 

 

 

-분산적이고 비동기적으로 동작하는 알고리즘에서는 때때로 각 노드가 자신의 거리 벡터를 이웃들에게 보낸다.

 

-노드 x가 이웃 w에게서 새로운 거리 벡터를 수신하면,
x는 w의 거리 벡터를 저장하고 벨만-포드 식을 사용하여 다음처럼 자신의 거리 벡터를 갱신한다.

 

 

-만약 이 갱신으로 인해 노드 x의 거리 벡터가 변경된다면

 

노드 x는 이 수정된 거리 벡터를 자신의 이웃들에게 보내고

 

그에 따라 이웃들도 자신의 거리 벡터를 갱신한다.

 

-모든 노드가 자신의 거리 벡터를 비동기적으로 교환하는 동작을 계속하다 보면,
비용 추정값 D.x(y)는 노드 x에서 노드 y까지의 실제 최소 비용 경로의 비용인 d.x(y)로 수렴하게 된다.

 

 

알고리즘 : 

 

 

각 노드는 이웃으로부터의 갱신을 기다리고 (10~11번째 줄)

-> 업데이터를 수신하면 새로 거리 벡터를 계산하고 (14번째 줄)

-> 이 새로운 거리 벡터를 이웃들에게 배포한다. (16~17번째 줄)

 

 

이 과정은 더 이상의 갱신 메시지가 없을 때까지 계속된다.

 

갱신 메시지가 더 이상 없으면 라우팅 테이블 계산도 더 이상 없고 알고리즘은 정지 상태가 된다. (10~11번째 줄 대기 명령을 수행)

 

이 알고리즘은 링크 비용이 변할 때까지 정지 상태로 있는다.

 

 

 

-거리 벡터(DV) 알고리즘: 링크 비용 변경과 링크 고장

 

거리 벡터 알고리즘을 수행하는 노드가

 

자신과 이웃 사이 링크의 비용이 변경된 것을 알게 되면

자신의 거리 벡터를 갱신한 후

최소 비용 경로의 비용에 변화가 있는 경우에는 이웃에게 새로운 거리 벡터를 보낸다.

 

 

a. 비용이 감소한 상황

 

 

-시각 t0 : y가 링크 비용의 변화를 감지하고, 자신의 거리 벡터를 갱신한 후 이 변경값을 이웃에게 알린다.

 

 

-시각 t1 : z는 y로부터 갱신 정보를 받고 자신의 테이블을 갱신한다.

z는 x까지의 새로운 최소 비용을 계산한다.

이웃에게 자신의 새로운 거리 벡터를 전송한다.

 

 

-시각 t2 : y는 z로부터 갱신 정보를 받고 자신의 테이블을 갱신한다.

y의 최소 비용은 변화가 없으므로 y는 z에게 아무런 메시지를 보내지 않는다.

이에 알고리즘은 정지 상태가 된다.

 

 

b. 비용이 증가한 상황

 

-시각 t0 : y가 링크 비용 변화를 감지하고 노드 x까지 다음의 비용을 갖는 새로운 최소 비용 경로를 계산한다.

 

이때 우리는 네트워크 전체를 한눈에 볼 수 있기 때문에 z를 경유하는 이 새로운 비용이 잘못되었다는 사실을 알 수 있지만, 노드 y의 입장에서는 아니다.

 

 

-시각 t1 :

x로 가기 위해 y는 z로 경로 설정을 하고, z는 y로 경로 설정을 하는 라우팅 루프(routing loop)가 발생한다.

 

t1에 x를 목적지로 하는 패킷이 y나 z에 도착하면 포워딩 테이블이 변할 때까지 이 두 노드 사이에서 왔다 갔다 순환할 것이다.

 

노드 y는 x까지의 새로운 최소 비용을 계산했으므로 z에게 새로운 거리 벡터를 알린다.

 

 

-시각 t2 : z는 y로부터 갱신 정보를 받고 새로운 최소 비용을 계산한다.

 

D.z(x) = min{50+0, 1+6} = 7

x까지의 z의 최소 비용이 증가했으므로, 새로운 거리 벡터를 y에 알린다.

 

 

-시각 t3 : y는 z로부터 새로운 거리 벡터를 수신하고 새로운 최소 비용을 계산한다.

Dy(x) = min{60+0, 1+7} = 8

x까지의 y의 최소 비용이 증가했으므로, 새로운 거리 벡터를 z에 알린다.

 

 

이렇게 계속 반복되는 문제를 무한 계수 문제(count-to-infinity)라고 한다.

 

 

-거리 벡터 알고리즘: 포이즌 리버스 추가

 

방금 설명한 특정한 라우팅 루프 시나리오는 포이즌 리버스(poisoned reverse)라는 방법을 통해 방지할 수 있다.

 

즉, 만약 z가 y를 통해 목적지 x로 가는 경로 설정을 했다면, z는 y에게 x까지의 거리가 무한대라고 알린다.

 

z는 y를 통과해서 x로 가는 동안은 이러한 거짓말을 계속한다.

 

이에 y는 z에서 x로 가는 경로가 없다고 믿으므로,
z가 계속해서 y를 통해 x로 가는 경로를 사용하는 동안은 y는 z를 통해 x로 가는 경로를 시도하지 않을 것이다.

 

하지만 포이즌 리버스는 모든 무한 계수 문제를 해결할 수는 없다.

 

단순히 직접 이웃한 2개의 노드가 아닌, 3개 이상의 노드를 포함한 루프는 포이즌 리버스로는 감지할 수 없다.

 

 

-링크 상태 알고리즘과 거리 벡터 라우팅 알고리즘의 비교

 

1) 경로 계산 방법

 

LS 알고리즘 : 

전체 정보를 필요로 한다.

각 노드는 다른 모든 노드와 (브로드캐스트를 통해) 통신한다.

오직 자신에게 직접 연결된 링크의 비용만 알린다.

 

DV 알고리즘 : 

각 노드는 오직 직접 연결된 이웃과만 메시지를 교환한다.

자신으로부터 네트워크 내 (자신이 알고 있는) 모든 노드로의 최소 비용 추정값을 이웃들에게 제공한다.

 

2) 메시지 복잡성

 

LS 알고리즘 : 

각 노드는 네트워크 내 각 링크 비용을 알아야 하며, 이를 위해서는 O(|N| |E|)개의 메시지가 전송되어야 한다.

링크 비용이 변할 때마다 새로운 링크 비용이 모든 노드에게 전달되어야 한다.

 

DV 알고리즘 : 

매번 반복마다 직접 연결된 이웃끼리 메시지를 교환한다.

알고리즘의 결과가 수렴하는 데 걸리는 시간은 많은 요소에 좌우된다.

링크 비용이 변하고, 이 새로운 링크 비용이 이 링크에 연결된 어떤 노드의 최소 비용 경로에 변화를 준 경우에만 DV 알고리즘은 수정된 링크 비용을 전파한다.

 

3) 견고성

 

LS 알고리즘 : 

라우터는 연결된 링크에 대해 잘못된 비용 정보를 브로드캐스트할 수 있다.

노드는 링크 상태 브로드캐스트를 통해 받은 패킷을 변질시키거나 폐기할 수 있다.

 

그러나 하나의 링크 상태 노드는 자신의 포워딩 테이블만 계산하기 때문에 링크 상태 알고리즘에서 경로 계산은 어느 정도 분산되어 수행된다.

따라서 링크 상태 알고리즘은 어느 정도의 견고성을 제공한다.

 

DV 알고리즘 : 

노드는 잘못된 최소 비용 경로를 일부 혹은 모든 목적지에 알릴 수 있다.

 

각 반복마다 한 노드의 거리 벡터 계산이 이웃에게 전달되고 다음 반복에서 이웃의 이웃에게 간접적으로 전달된다.

따라서 거리 벡터 알고리즘을 사용하는 네트워크에서 한 노드의 잘못된 계산은 전체로 확산될 수 있다.