[네트워크] Dijkstra's link state 알고리즘

오늘은 Dijkstra's link state 알고리즘에 대해 알아보겠습니다.

 

link state는 이웃의 정보를 모두에게 전달 즉, broadcast 해줍니다.

다시 말하자면 자신과 연결된 노드의 정보를 모두에게 알려주고, 각각의 라우터는 자신으로부터 다른 노드들까지 최소 길이를 각자 계산하게 됩니다.

 

아래 그림의 상황에서 Dijkstra알고리즘이 시행되는 과정을 표로 나타내보았습니다. 

출처: http://gaia.cs.umass.edu/kurose_ross/interactive/dij.php

 

step	start	D(v), p(v)	D(x), p(x)	D(w), p(w)	D(y), p(y)	D(z), p(z)
0	u	2,u	3,u	4,u	infinite	infinite
1	uv
2	uvx				12,x
3	uvxw				9,w	8,w
4	uvxwz
5	uvxwzy