[Computer Networking] Network Layer : Routing Protocols

Per-router control plane

- 라우터 별 제어 : 라우팅 알고리즘들이 모든 라우터 각각에서 동작하는 경우

 

Software-Defined Networking (SDN) control plane

- 논리적 중앙 집중형 제어 : 논리적 중앙 집중형 컨트롤러가 포워딩 테이블을 작성하고 이를 모든 개별 라우터가 사용할 수 있도록 배포한 경우 (EX. SDN)

 

Routing Protocols

- 라우팅 프로토콜 : 송신자부터 수신자까지 라우터의 네트워크를 통과하는 최적(일반적으로 최소비용 경로)의 경로를 결정하는 것

 

Link-State Routing Algorithm

- 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산하는 중앙 집중형 라우팅 알고리즘이다.

- 데이크스트라의 알고리즘을 사용하여 구현한다.

데이크스트라의 알고리즘 : https://junstory314.tistory.com/entry/Computer-Algorithms-Dijkstras-Shortest-Path-Algorithm

 

- 문제점

  위는 극단적인 예시이지만 트래픽 상황에 따라서 경로가 반복적으로 바뀌는 route oscillations (경로 진동) 문제가 발생할 수 있다. 이는 모든 라우터가 동시에 LS 알고리즘을 실행하지 못하게 하여 해결할 수 있다.

  다른 하나의 문제점은 라우터가 고장/오동작 또는 파손된다면 연결된 링크에 대해 잘못된 정보를 브로드캐스트 할 수 있다. 또한 노드는 LS 브로드캐스트를 통해 받은 패킷을 변질시키거나 폐기할 수 있다. 그러나 하나의 LS 노드는 자신의 포워딩 테이블만 계산하고, 다른 노드들 역시 그렇게 한다. 이는 LS 알고리즘에서 경로 계산이 어느 정도 분산되어 수행됨을 의미하고, 따라서 어느 정도의 견고성을 제공한다.

 

Distance Vector Algorithm

- 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행되는 분산 라우팅 알고리즘이다.

- 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지는 않다. 대신 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다.

1. 인접 노드의 DV 테이블이 바뀔때 까지 대기한다.

2. 바뀌었다면 자신의 DV 테이블도 갱신한다.

3. 인접노드에게 알린다.

이 세 가지 과정을 모든 노드의 DV 테이블이 변경되지 않을 때 까지 반복한다.

- 문제점

  링크 비용이 중간에 갑자기 높게 바뀌어 버리면 계산 횟수가 급격히 많아질 수 있다. 이는 poisoned reverse 라는 방법으로 방지할 수 있다. 위 그림을 예로 들면 같은 구간을 반복적으로 계산한다면 z->y->x의 경로의 비용을 무한대로 취급해버리는 것이다. 하지만 이 방식은 3개 이상의 노드를 포함한 루프에서는 적용되지 않는다.

  다른 하나의 문제점은 노드는 잘못된 최소 비용 경로를 일부 혹은 모든 목적지에 알릴 수 있다는 것이다. 각 반복마다 한 노드의 DV 계산이 이웃에게 전달되고 다음 반복에서 확산된다. 이런 측면에서 DV 알고리즘을 사용하는 네트워크에서 한 노드의 잘못된 계산은 전체로 확산될 수 있다.