[12] CH4 네트워크 계층 < 라우팅 알고리즘 >

그럼 네트워크 계층의 중요한 라우팅 기능에 대해서 알아보겠습니다. 패킷을 송신호스트에서 목적지 호스트로 전송하기 위해서 네트워크 계층은 패킷의 라우팅 경로를 정해야 합니다. 즉, 네트워크 계층은 송신자로부터 수신자로의 패킷 경로를 결정해야 합니다. 여기서는 라우터의 네트워크를 통해 송신자로부터 수신자 까지 좋은 경로를 결정하는 것이 라우팅의 역할로 볼 것 입니다. 

 

대체로 호스트는 하나의 라우터에 직접 연결되어 있는데, 이 라우터를 호스트에 대한 디폴트 라우터라고 부릅니다. 호스트는 모든 패킷을 디폴트 라우터로 전송합니다. 출발지 호스트의 디폴트 라우터를 출발지 라우터라고 하며, 목적지 호스트에 연결된 디폴트 라우터를 목적지 라우터라고 합니다. 

 

라우팅 알고리즘의 목적은 간단합니다. 주어진 라우터와 라우터를 연결하는 링크들의 집합에서 라우팅 알고리즘은 출발지 라우터에서 목적지 라우터까지 '좋은' 경로를 찾는 것입니다. 여기서 '좋은'경로란 최소비용의 경로를 뜻합니다. 

 

그래프가 라우팅 문제를 나타내는데 사용됩니다. 그래프 G=(N,E)는 노드의 세트 N과 가장 자리 노드의 모음 E이고 각 가장자리는 N에서 노드들의 쌍인 것을 기억합시다.

E에서의 어떤 가장자리(x,y)에 대해서, c(x,y)는 노드x와y간의 비용을 나타낸다. 만약 쌍(x,y)가 E에 속하지 않는다면 c(x,y)=∞ 로 나타낸다. 그러므로 c(x,y) = c(y,x)가 성립하고 만약 (x,y)가 E에 속한다면, 노드y는 노드x의 이웃(neighbor)이라고 한다. 

 

라우팅 알고리즘은 넓은 의미로 글로벌화인지 혹은 분산화인지에 따라 분류할 수 있습니다. 

 

글로벌 라우팅 알고리즘

 네트워크에 대한 완벽한 글로벌 정보 즉,모든 router는 topology와 link cost정보를 가지고 출발지와 목적지 사이의 최소비용경로를 계산한다. 즉, 알고리즘은 입력값으로 모든 노드와 모든 링크비용의 연결을 취한다. 글로벌 상태 정보를 가진 알고리즘은 네트워크의 각 링크에 대한 비용을 알고 있어야 하므로 링크 상태(link state)알고리즘이라 부르기도 합니다. 

 

분산 라우팅 알고리즘 

 최소비용경로의 계산은 반복적이고 분산된 방식으로 수행됩니다. 노드가 모든 네트워크 링크의 비용에 대한 완벽한 정보를 갖고 있지 않습니다. 대신에 각 노드는 링크에 직접 연결된 링크의 비용에 대한 정보만 가지고 있습니다. 반복 계산 과정과 이웃 노드와의 정보교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지 최소비용경로를 계산합니다. 각 노드가 네투워크의 다른 노드까지 비용의 추정치들을 벡터형으로 유지하므로 거리 벡터 알고리즘이라 합니다. 

 

 

라우팅 알고리즘을 분류하는 두 번째 방식은 라우팅 알고리즘을 정적과 동적으로 분류하는 것입니다. 

 

정적 라우팅 알고리즘 

 이 알고리즘에서 경로는 아주 느리게 변합니다. 결과적으로 사람이 개입합니다.( 라우터의 포워딩 테이블은 수작업으로 수정한다.) 

 

동적 라우팅 알고리즘 

 네트워크 트래픽 부하나 토폴로지 변화에 따라 라우팅 경로를 바꿉니다. 동적 알고리즘은 주기적 혹은 토폴로지의 직접적인 응답, 링크 비용 변화로 수행됩니다. 동적인 알고리즘은 네트워크 변화뿐 아니라 라우팅 루프와 라우터의 진동과 같은 문제에 민감합니다. 

 

라우팅 알고리즘을 분류하는 세 번째 방식은 라우팅 알고리즘이 부하에 민감한지 또는 둔감한지에 의해 분류하는 것입니다. 

 

부하에 민감한 알고리즘 

 링크 비용은 하부 링크의 혼잡 수준이 바로 반영되므로 매우 동적이다. 높은 비용이 현재 혼잡한 링크와 관련되어 있다면, 라우팅 알고리즘은 혼잡한 링크를 우회하는 경로를 선택하게 됩니다. 대부분 예전 알고리즘 

 

부하에 둔감한 알고리즘 

 현재 인터넷 라우팅 알고리즘은 링크 비용이 현재의 혼잡을 반영하지 않는, 부하에 둔감한 알고리즘 입니다. 

 

 

 

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

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

 한 노드(출발지u)에서 네트워크의 다른 모든 노드에 이르는 최소비용을 계산한다. 이 알고맂므은 반복적이고 알고리즘의 k번째 반복 이후에 k개의 목적지 노드에 대해 최소비용경로가 알려지며,모든 목적지 노드까지 최소비용경로 중에서 이 k개의 경로는 k개의 최소비용을 가질 것이다. 다음은 이것을 기호로 나타낸 것이다. 

다익스트라 알고리즘 예제

1. 초기화 단계에서 u로부터 직접 연결된 이웃 v,x,w까지의 최소비용경로는 각각 2,1,5로 초기화 된다. y,z는 u에 직접 연결되어 있지 않기에 ∞로 표시한다. 

 

2. 첫 번째 반복에서 N'집합에 아직 포함되지 않은 노드 중에서 앞의 반복의 끝에서 얻은 최소 비용을 가진 노드를 찾는다. 그 노드는 비용 1을 갖는 x이며 집합N'에 넣는다. 다음에 링크 상태 알고리즘의 D(v) = min(D(v) , D(w)+c(w,v)) 이 줄이 모든 노드 v에 대한 D(v)를 갱신하도록 수행되고 1단계 표에 결과를 산출한다. 이때 노드x를 통한 w로의 경로비용(원래 5)은 4라는 것을 발견한다. 마찬가지로 y로의(x를 통한)비용은 2이므로 테이블을 갱신한다. 

 

3. 두 번째 반복에서 노드 v,y가 최소경로비용(2)을 가진다는 것을 발견하고 임의로 끊고 y를 N'에 넣는다. 따라서 N'에는 u,x,y가 있다. N'에 없는 남은 노드들의 비용, 즉 v,w,z는 링크 상태 알고리즘의 D(v) = min(D(v) , D(w)+c(w,v))을 ㅗㅇ해서 갱신되어 표의 세번째 줄에 보이는 결과를 가져옵니다. 

 

4. 위 과정을 계속 반복합니다. 

 

최소비용경로와 u를 위한 전달 테이블

링크 상태 알고리즘이 종료다.된 후 각 노드는 출발지 노드로부터 형성된 최소비용경로를 따라 이전 노드를 갖게 된다. 각 이전 노드는 이전 노드를 가지며 이러한 방식으로 출발지에서 모든 목적지까지 전체 경로를 구축할 수 있다. 

 

다익스트라 알고리즘 예제2

 

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

 링크 상태 알고리즘이 글로벌 정보를 이용하는 알고리즘인 반면에, 거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. 각 노드는 하나 이상의 직접 연결된 이웃이 주는 정보로 계산하고, 이웃에게 계산 결과를 알린다는 점에서 분산적이다. 이웃끼리 정보를 교환하지 않을때 까지 프로세스가 지속된다는 점에서 반복적이며, 모든 노드가 서로 톱니바퀴 모드로 동작할 필요가 없다는 점에서 비동기적이라고 말할 수 있다. 

 

 DV알고리즘을 설명하기 전, 최소비용경로들의 비용값에 존재하는 중요한 관계를 생각해보자. dx(y)를 노드x로부터 노드y로까지의 최소비용경로의 비용이라고 하자. 그러면 최소비용은 벨만-포드식에 의해서 다음처럼 나타낼 수 있다. 

Bellman-Ford 예제 

최소의 비용을 얻는 node(위의 예:x)가 두node(위의 예:u와z)사이의 가장 짧은 경로(path)상에 출발지 node(위의 예:u) 바로 다음 홉이다. >> forwarding table에 사용됨.

 

 

Distance Vector 알고리즘 

 

DV알고리즘은 노드x가 자신의 직접 연결된 링크 중의 하나가 비용이 변경된 것을 알거나 또는 그 이웃으로부터 거리 벡터 갱신을 수신했을 때, 어떻게 그 거리 벡터 예측치를 수정하는지 보여준다. 즉, 주어진 목적지 y에 대한 자신의 포워딩 테이블을 갱신하기 위해, 노드x가 정말 알아야 하는것은 y까지의 최단 경로 거리가 아니라 y로의 최단 경로상의 다음 홉 라우터인 이웃노드 v*(y)이다. 

 

- Node x는 바로 이웃 node v로 연결되는 link의 비용을 알고 있다.  c(x,v) 

- Node x는 distance vector Dx = [Dx(y): y є N]를 지닌다. Dx(y): x로부터 y에 이르는 최소 비용의 추정값

- Node x는 또한 이웃 node들의 distance vector들도 지님. 즉, 이웃 node v에 대해 x는 다음을 지닌다.

  Dv = [Dv(y): y є N ]

 

기본 아이디어 :

- 때때로 각 node는 자신의 distance vector 추정값을 이웃 node들에게 전송 

- 비동기적 

- Node x가 이웃으로부터 새로운 DV 추정값을 받으면(혹은 이웃 node와의 cost가 바뀌면), 그는 B-F방정식을 이용해 자신의 DV를 갱신한다.

 

Dx(y) ← minv{c(x,v) + Dv(y)}    for each node y ∊ N

- 시간이 흐름에 따라 Dx(y) 추정값은 실제 최소 비용값 dx(y)에 수렴하게 된다. 

 

특징 

반복적 & 비동기적 : 매 지역적 반복은 다음에 의해 발생됨 - 지역적 link비용의 변동 , DV 갱신 message가 이웃으로부터 전달 되었을때 

분산적 : 각 node는 자신의 DV가 변했을 때만 이웃들에게 알림 

 

Distance Vector : link cost 변동 

Link cost 변동

 - Node는 지역적인 link cost 변동을 감지 

 - Routing 정보 갱신, distance vector 다시 계산 

 - DV에 변동이 있으면, 이웃에게 알림 

 

" 좋은 소식은 빨리 전달됨 "

 

- 시간 t0에 y는 link-cost 변동을 감지, 자신의 DV갱신, 자신의 이웃에게 알림 

- 시간 t1에 z는y로부터 갱신정보 수신, 자신 table갱신. x로 가는 최소 경비 갱신, 자신의 DV를 이웃에게 알림 

- 시간t2에 y가 z의 갱신정보를 수신, 자신의 table을 갱신. y의 최소 비용은 변함이 없음 그러므로 y는 더이상 z에게 어떠한 message도 전송하지 않는다.