Routing Protocol

Purpose

Source부터 Destination까지의 빠르고 혼잡이 적은 경로를 찾는 것

Algorithms

Link-State

Topology를 완벽하게 아는 상태에서 사용
Router의 forwarding table이 필요

Dijkstra Algorithm

1. 현재 node에서 갈 수 있는 node와 cost를 기록
2. 가장 낮은 cost를 기록한 node를 다음 node로 선정
3. 모든 node를 파악할 때까지, 1~2를 반복
4. 위의 과정을 통해 최소 비용 경로 table<destincation , outgoing link>을 생성

Distance-Vector

물리적으로 연결된 Router만 아는 상태에서 사용
각 Router까지의 거리를 계속해서 업데이트 (bfs와 유사)

Bellman-Ford Equation

1. 시작 node에서 가까운 노드 순서대로 거리를 계산
2. 만약 계산한 거리가 이전 거리보다 가까우면 최신화

Count-to-infinity Problem

어떤 한 node에서 다른 node로 가는 경로의 비용이 증가했을 때 발생한다.
다른 node에서는 이미 계산되어 있는 결과가 있기 때문에, 정상적인 계산치에 도달할 때까지 시간이 걸린다.

Poisoned Reverse

비용이 증가한 경로를 Infinity 값으로 주변 node에 알린다. 이후에 Routing Algorithm을 수행한다.

Hierarchical Routing

Autonomous System (AS)

어떤 한 지역을 만드는 router들의 집합체를 의미

Intra-AS

같은 Autonomous System에 속해있는 Router간의 protocol

Inter-AS

Gateway Router를 통한 다른 Autonomous System의 Router간의 Protocol

Gateway Router

속한 Autonomous System의 edge에 위치한 Router로 다른 Autonomous System과 연결된 link를 가지고 있다.