10. 라우팅 알고리즘

본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다.

 

Index

• 1. 그래프의 기본
• 2. link state
• 3. distance vector

 

1. 그래프 기본

 

자료구조나 알고리즘 시간에 우리는 그래프에 대해 배운 적이 있을 것이다.

그래프는 여러 개의 노드와 그들을 잇는 에지들로 구성되어있고, 각 에지는 가중치가 존재한다.

 

이를 바탕으로 여러 코딩 테스트에서는 어떤 경로에 대한 최단 거리, 사이클의 존재 유무 등 최근 그래프 기반 문제들을 자주 출제 중이라 꼭 알아햐 하는 부분 중 하나이다.

 

이번에는 네트워크적 관점에서의 그래프에 대해 아~주 간단하게만 알아볼 시간이다.

 

네트워크 그래프 용어

• 노드 -> 라우터
• 에지 -> 링크
• 가중치 -> 연결 비용 or 시간 or 혼잡도

우리가 그래프를 이용해 어떠한 노드들(라우터들)을 거쳐가면 가장 좋은 경로(최단 or 최저 비용 등)로 갈 수 있는지 

라우팅 알고리즘을 통해 알아보겠다.

 

 

1.1 라우팅 알고리즘 분류

 

1) global : 모든 라우터들은 전부 연결되어있는 상태이다. ex)link state 알고리즘

2) decentralized : 라우터들은 그들의 이웃끼리만 비용과 연결상태를 공유한다. ex) distance vector 알고리즘

 

3) static : 루트들이 시간이 지남에따라 천천히 변화한다.

4) dynamic : 루트들이 상당히 빠르게 변화한다. (업데이트)

 

 

2. link-state routing algorithm

링크 상태 알고리즘은 일반적으로 "다익스트라 알고리즘"을 사용한다.

 

간단하게 말해서, 다익스트라 알고리즘의 과정은 다음과 같다.

• (가정) link state broadcast를 해서, 모든 링크의 가격을 알고 있는 상태이다.
• 시작점을 정한 후, 그 점에 연결된 에지들 중 가장 적은 가격을 갖는 에지를 고른다.
• 위 과정을 노드의 개수만큼 반복하면 최단 거리가 만들어진다.

다익스트라가 메인이 아닌지라 더 자세히는 필요하지 않을 것 같다.

 

간단히 이 알고리즘에 정당성에 대해 이야기해보자면, 

만약 시작점에 연결되어있는 노드들가운데 가장 작은 에지를 고르지 않는다면 가장 작은 에지와 연결된 노드로 가는 경로는 반드시 가장 작은 에지의 비용보다 크거나 같게 된다. 왜냐하면 다익스트라는 양의 가중치에 대한 그래프만을 고려하고, 최소의 에지를 고르지 않는다면 그곳까지 가는 경로는 반드시 늘어날 수밖에 없기 때문이다. 

이런 식으로 "항상 최선의 선택을 하는" 알고리즘을 "그리디 알고리즘"이라고도 말한다.

 

이 알고리즘은 한 노드부터 시작해 계속 연결된 에지들만 찾기 때문에 집중적(global)이고 정적(static)인 특성을 지니고 있다.

 

 

3. distance vector routing algorithm

distance vector 알고리즘은 일반적으로 벨만 포드 알고리즘을 사용한다.

벨만 포드 알고리즘도 똑같이 한 정점으로부터의 최단 거리를 구하는 알고리즘인데,

다익스트라와 다르게, dynamic programming 의 성질을 띠고 있다. 즉, 이미 구한 것을 바탕으로 다음 것을 구할 수 있다는 이야기다.

 

만약 a, b, c, d, e 노드가 존재하고 각자 모두 연결되어있다고 해보자.

a->e 간의 최단 경로를 구하기 위해서 벨만 포드 알고리즘은

a->b->e, a->c->e, a->d->e와 a->e 중 최솟값을 찾는다. 이미 a->b, a->c, a->d 등 몇 개는 구해져 있으므로 (loop가 알파벳 순으로 돈다고 하면) dynamic programming이 성립된다고 볼 수 있을 것이다.

 

특히 중요한 것은 이 알고리즘이 구하는 최단 거리는 계속 바뀔 수 있는데

예를 들어 a->e 에지가 5이고, a->b가 1, b->e가 3이라고 하면, 이후에 a->e에 대해 구하는 과정에서 4로 바뀌게된다.

(이런 변화를 "good news"라고 한다)

 

따라서 알고리즘은 각자 따로따로 계산하고 합쳐지기 때문에 분산적(decentralized)이고 동적(dynamic)인 특성을 지니고 있다.