[Computer Network] Link State Routing

distance vector routing을 알아 보았고 이번엔 link state routing을 알아본다.

distance vector routing은 각 노드를 기준으로부터 모든 노드까지의 최단거리를 서로에게 전달하며 이를 기준으로 업데이트 했다.

link state routing은 각각의 노드의 incident한 link를 건너는데에 필요한 cost를 list에 저장해둔다. 그리고 브로드캐스트처럼 다른 노드들에게 이 정보를 전달한다.

그럼 하나의 노드는 다른 모든 AS에 존재하는 노드들에게 받은 리스트 정보를 통해 최단거리를 구할 수 있게 된다.(하나의 노드는 다른 노드들과의 모든 최단 거리를 구할 수 있다.)

각각의 노드는 모두 global topology를 가지고 있는 것을 확인할 수 있다.
이를 통해 각각의 노드로부터 다른 노드까지의 모든 최단거리를 구할 수 있다.

Pseudo Code

수도코드는 다음과 같다. 하나의 노드에 대해 다른 모든 노드와의 최단거리를 구한다. root 노드라 칭한다.

• s는 자기 자신이다. 자기로 가는 cost는 0이다.
• s의 adjacent한 node들은 cost를 가지고 있으므로 모두 cost로 초기화 해준다.

iteration

• 가장 cost가 작은 cost를 가진 경로를 path에 추가한다.
• 이후 각각의 node에 대해 incident한 edge(link)의 cost를 가지고 있으므로 최단 거리를 구한다.

path에 M개의 node가 찰 때까지 이를 반복한다.(M==0까지) 처음에 s를 넣고 시작하니 M의 초기값은 N-1이다.

구하는 과정

A를 root node로 설정했을 때 모습


iteration이 끝났을 때의 모습이다.