[네트워크] 4. Network layer (3) - Routing Protocols

Reference - Computer Networking: a Top Down Approach

 

 

Network layer는 end to end로 패킷을 전송할 때, 경로를 설정하고 라우터 관점에서 어떻게 효율적으로 전달할지를 결정하는 역할을 한다.

 

Routing Protocol

Routing Protocol의 목적은 good path를 찾는 것이다.

여기서 good path라 함은 cost / fastest / least congested 등을 최적화하는 path가 될 수 있다.

 

Shortest Path Routing problem의 경우 모든 경로 상에서 destination까지의 sum of cost가 가장 작은 값을 찾는다.

이때의 cost는 정의하기 나름인데, link length, speed, propagation delay 등등의 조합일 것이다.

 

라우팅 알고리즘은 global / decentralized, 그리고 static / dynamic으로 분류할 수 있다.

global(centralized)은 모든 라우터가 연결되어있는 상태로, link-state algorithm이 있다.

이 방법은 single point of failure의 문제가 있다.

decentralized는 라우터가 이웃끼리면 비용과 연결을 공유하는 상태로, distance vector algorithm이 있다.

이 방법은 convergence(라우터가 변화를 공유하기까지 오래걸림), sub-optimality(최적이 아닐 수 있음) 문제가 있다.

static은 path가 아주 천천히 변화하는 것이고,

dynamic은 path가 동적으로 업데이트되며 빠르게 변화하는 것이다. 

 

Graph

 

그래프 G는 (N, A) (N = non-empty set of nodes, A = Each pair of nodes, called Arc)로 정의한다.

이때 A는 없을 수 있다.(=공집합)

모든 pair를 walk, 반복된 nodes가 없는 walk를 path, 시작 node와 마지막 node가 반복없는 walk로 이어지고 동시에 walk의 node가 4개 이상일 때(최소 node 3개가 cycle이 될 때) cycle이라 정의한다.

graph는 각 node i가 다른 node j로 향하는 path가 연결되어 있을 때 graph라고 한다.

tree는 graph가 cycle이 없을 때, spanning tree는 connected graph의 subgraph일 때를 말한다.

 

위 내용을 상기하며, 본격적으로 라우팅 알고리즘을 알아보겠다.

 

- link-state routing algorithm

 

link-state 알고리즘은 다익스트라 알고리즘을 사용한다.

다익스트라 알고리즘은 모든 link의 cost를 알고있다는 가정 하에 사용한다. (global and static)

시작점을 정한 후, 그 점에 연결된 edge 중 가장 cost가 적은 edge를 선택하고, 이 과정을 노드 수만큼 반복하면 최단 거리를 찾을 수 있다. 시간 복잡도는 O(n^2)가 나온다. 이 방법은 cost가 바뀌는 dynamic 환경에서 문제가 발생할 수 있다.

 

- Distance vector algorithm

 

distance vecctor 알고리즘은 Dynamic Programming의 일종인 벨만 포드 알고리즘을 사용한다.

벨만 포드 알고리즘은 시간에 따라 각 노드가 이웃에게 distance vector를 보내 update다. (decentralized and dynamic)

pseudo code를 보면, least cost path from x to y를 dx(y)라 할 때,

dx(y) = min{ cost to neighbor v + dv(y) }의 꼴로 DP를 통해 동적으로 비용이 최소인 path를 구할 수 있다.

이때 각 node는 network topology에 대한 정보를 알 필요가 없다.

outgoing link의 cost, identity of every node, cost of immediate neighbors to destination 3가지 정보만 알면 된다.

 

두 routing algorithm을 비교하면 다음과 같다.