Link State algorithm

각 Router들은 자신과 연결된 Interface(=Link)의 상태를 LSA(Link State Advertisement)라는 정보로 생성하여 다른 Router들과 교환하게 되며, 다른 Router들을 통해 받은 LSA를 LSDB(Link State DataBase)에 저장하게 된다. 그 후 SPF 알고리즘을 사용하여 Best Path를 결정하고 이를 Routing table에 등록하게 된다. 최소 비용 기준 알고리즘이다.

📌 Link State Algorithm 과정

① Link-State Advertisements -> ② Topological Database -> ③ SPF Algorithm-> ④ Shortest Path First Tree -> ⑤ Routing Table

1. 이웃을 알기위해 hello 패킷을 보낸다. 응답이 오면 이웃이 있는 것이고 없으면 존재하지 않는 것이다.

2. 각 라우터마다의 cost를 측정하기 위해서 ping 메세지를 보낸다. ping을 보내면 다시 올때까지 delay가 있다.(round-trip-time) ping은 갖다가 오는 시간이기 때문에 cost로 사용하기 위해서 2로 나눠준다. 또한 ping을 보낼때마다 delay가 달라질수도 있기 때문에 cost는 이 값들의 평균값을 사용한다.

3. link state 패킷을 만든다. 주기적으로 만들때도 있고 어떤 이벤트가 발생했을때 만드는 경우도 있다.
   

4. 만든 패킷을 AS 도메인 내의 다른 라우터들에게 브로드캐스트 한다.(Flooding)

5. 다른 노드들도 모두 브로드캐스트하므로 받은 정보를 통해 다익스트라 알고리즘을 이용해 shortest path를 구성한다.

-> OSPF 방식이다.

📌 Link state 특징

• 전체 네트워크에 대한 토폴로지와 관련된 모든 정보로써 LSD(Link State Database) 를 각 라우터가 완벽히 갖고 있게된다. 이 LSD를 통해 SPF 트리를 만들고 이를 토대로 최적 경로에 대한 라우팅 테이블을 구축한다.

• 네트워크 토폴로지 및 모든 링크 비용이 알려져 있고, 이들 값이 입력으로 사용되기에 이에 참여하는 모든 라우터는 항상 전체 네트워크에 대한 맵(지도,그림 등)을 그리고 이를 토대로 최적의 경로를 계산하는 방식을 취한다.

• 각 노드는 맵에서 독립적으로 알고리즘을 실행하여 자체에서 네트워크의 다른 모든 노드까지의 최단 경로를 결정한다.

• Periodic Update(주기적 업데이트)를 수행하지 않는다.

• Hop-count 제한이 없고 Loop 발생의 위험이 없다