computer network - control plane(3)

routing protocol - oscilation problem

저번 글에선 다익스트라 알고리즘을 사용해서 라우팅을 하면 생기는 문제에 대해 알아보았습니다. 이번 글에선, 새로운 라우팅 프로토콜에 대해 다뤄보도록 하겠습니다.

해결책에 앞서

어떻게 하면 이러한 진동 문제를 해결할 수 있을까요? link state algorithm은 현재 상태를 한 번에 공유하기에 생기는 문제입니다. 그러면 한 번에 공유하지 않고 동적으로 만들면 어떻게 안될까? 라는 생각을 가져보는 것이 가능하지 않을까요?

Distance vector

distance vector algorithm은 bellman-ford equation에 뿌리를 둡니다. 이 분의 이름을 딴 유명한 알고리즘이 있습니다. 바로 벨만-포드 알고리즘이죠. 간략하게 설명해보자면, 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 또한 그래프의 link 가중치가 음수여도 성립하는 알고리즙입니다.

그렇다면 BF equation은 뭘까요? x에서 y로 가는 cost는 [x의 인접한 정점들 v + v에서 y까지의 거리의 최소]의 최솟값입니다.

하나의 정점 기준으로, 하나를 찍고, 그 주변 모든 정점들을 보면서 테이블을 키우고, 그 커진 테이블을 기준으로 또 확장하는 그러한 형태인 알고리즘입니다. “아니 그렇다면 v에서 y까지의 거리의 최소는 어떻게 구할래?”라는 의문점이 들 법도 합니다. 그건 나중에 설명하겠습니다.

벨만 포드 알고리즘와 다익스트라 알고리즘의 차이

벨만 포드 알고리즘은 시작 노드 s로부터, 모든 s의 인접한 정점들을 다 방문합니다. 하지만 다익스트라 알고리즘은 기준 노드를 정한 후, 그 노드에 대해 제일 거리가 짧은 주변 인접 정점으로 확장되어 가는 알고리즘인 것이죠. 즉, 벨만 포드 알고리즘은 모든 정점과 그 인접한 정점들을 다 방문하지만, 다익스트라 알고리즘은 모든 정점은 방문하되, 제일 좋은 정점만 확장해 나가는 것이 차이점입니다.

의문점?

v에서 y까지의 거리의 최소는 확실하게 알 길이 없습니다. 왜냐하면 distance vector 알고리즘은 모든