5.2 라우팅 알고리즘
라우팅 알고리즘의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것인데, 일반적으로 ‘좋은’ 경로란 최소 비용 경로를 말한다.
네트워크 제어 평면이 라우터별 제어 방식을 채택하든 논리적 중앙 집중형 방식을 채택하든 상관없이 패킷이 전송 호스트에서 수신 호스트로 이동하기 위한 잘 정의된 일련의 라우터가 항상 존재해야 한다.
라우팅 문제를 나타내는 데는 그래프가 사용되는데, 그래프는 G(N, E)로 나타낸다. N과 E는 각각 노드와 에지의 집합이고, 하나의 에지는 집합 N에 속하는 한 쌍의 노드로 표시된다.
그래프상의 노드는 패킷 전달 결정이 이루어지는 지점인 라우터를 나타내며, 이 노드들을 연결하는 에지는 라우터들 간의 물리 링크를 나타낸다.
에지는 그 비용을 나타내는 값을 갖는다. 이 비용은 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영한다.
집합 E에 포함된 어떤 에지 (x, y)에 대해 c(x, y)는 노드 x와 y간의 비용을 의미하는데, 만약 노드 쌍 (x, y)가 E에 포함되어 있지 않으면 c(x, y) = INF로 둔다. 모든 에지가 방향성을 갖지 않는 무방향성 그래프만을 고려한다. 에지(x, y)가 집합 E에 속하면, 노드 y는 노드 x의 이웃이라고 한다.
여러 에지들에 비용이 할당되고 나면 라우팅 알고리즘은 출발지와 목적지 간 최소 비용 경로를 찾는 것을 목표로 하게 된다. 만약 그래프의 모든 에지가 같은 비용을 갖는다면 최소 비용 경로가 바로 최단 경로가 된다.
라우팅 알고리즘을 분류하는 일반적인 방법 한 가지는 알고리즘이 중앙 집중형인지 분산형인지이다.
- 중앙 집중형 라우팅 알고리즘
- 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다.
- 모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 한다.
- 계산 자체는 한 장소에서 수행되거나 모든 라우터 각각의 라우팅 모듈로 복사될 수 있다.
- 해당 알고리즘이
연결과 링크 비용에 대한 완전한 정보를 갖는다는 점이 핵심적인 특징이다. - 전체 상태 정보를 갖는 알고리즘을
링크 상태(LS) 알고리즘이라고 하는데, 이는 이 알고리즘이 네트워크 내 각 링크의 비용을 알고 있어야 하기 때문이다.
- 분산 라우팅 알고리즘
- 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.
- 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지는 않다.
- 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다.
- 분산 라우팅 알고리즘은
거리 벡터(DV) 알고리즘이라고 부르는데, 각 노드가 네트워크 내 다른 모든 노드까지 비용의 추정값을 벡터 형태로 유지하기 때문이다.
라우팅 알고리즘을 분류하는 두 번째 방식은 정적 알고리즘과 동적 알고리즘으로 분류하는 것이다.
- 정적 라우팅 알고리즘
- 경로는 아주 느리게 변하는데, 종종 사람이 개입한 결과로 그렇게 된다.
- 동적 라우팅 알고리즘
- 네트워크 트래픽 부하나 토폴로지 변화에 따라 라우팅 경로를 바꾼다.
- 주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.
- 네트워크 변화에 빠르게 대응한다는 장점도 있지만, 경로의 루프나 경로 진동 같은 문제에 취약하기도 하다.
라우팅 알고리즘을 분류하는 세 번째 방식은 라우팅 알고리즘이 부하에 민감한지 아닌지에 따른다.
부하에 민감한 알고리즘 에서 링크 비용은 해당 링크의 현재 혼잡 수준을 나타내기 위해 동적으로 변한다. 현재 혼잡한 링크에 높은 비용을 부과한다면, 라우팅 알고리즘은 혼잡한 링크를 우회하는 경로를 택하는 경향을 보일 것이다.
오늘날 인터넷 라우팅 알고리즘은 링크 비용이 현재의 혼잡을 반영하지 않기 때문에 부하에 민감하지 않다.
5.2.1 링크 상태(LS) 라우팅 알고리즘
링크 상태 알고리즘에서는 네트워크 토폴로지와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다는 것을 기억해야한다. 각 노드가 자신과 직접 연결된 링크의 식별자와 비용 정보를 담은 링크 상태 패킷을 네트워크상의 다른 모든 노드로 브로드캐스트하게 함으로써 가능하다. 이는 링크 상태 브로드캐스트 알고리즘에 의해 수행된다.
다익스트라 알고리즘은 하나의 노드에서 네트워크 내 다른 모든 노드로의 최소 비용 경로를 계산한다. 해당 알고리즘은 반복적이고, 알고리즘의 k번째 반복 이후에는 k개의 목적지 노드에 대해 최소 비용 경로가 알려지며 이 k개의 경로는 모든 목적지 노드로의 최소 비용 경로 중에서 가장 낮은 비용을 갖는 k개의 경로다.
링크 상태 알고리즘이 종료된 후에 우리는 각 노드에 대해 출발지 노드로부터의 최소 비용 경로상의 직전 노드를 알게 된다. 각각의 직전 노드는 또 그 직전 노드를 가지며 이러한 방식으로 출발지에서 모든 목적지까지의 전체 경로를 구축할 수 있다.
진동문제를 방지하려면 링크 비용이 해당 링크가 전달하는 트래픽의 양에 의존하지 않도록 하는 방법이 있다. 하지만 라우팅의 한 가지 목적이 매우 혼잡한 링크를 회피하는 것이므로 받아들이기 어려운 해결책이다. 다른 해결책으로, 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 하면 된다.
하지만, 인터넷 라우터들이 스스로 자기들끼리 동기를 맞춘다는 사실을 발견했다. 즉, 라우터들이 알고리즘을 처음에는 각기 다른 시작 시간에, 그러나 같은 주기를 갖도록 해서 실행하더라도 점진적으로 결국엔 서로 동기화된다는 것이다.
5.2.2 거리 벡터(DV) 라우팅 알고리즘
링크 상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면에, 거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. 각 노드는 하나 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다는 점에서 분산적이다. 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다는 점에서는 반복적이다. 모든 노드가 서로 정확히 맞물려 동작할 필요가 없다는 점에서 비동기적이다.
DV 알고리즘을 설명하기 전에, 최소 비용 경로의 비용들 사이의 관계를 알면 좋은데, 최소 비용은 벨만-포드 식에 의해 아래와 같이 나타낼 수 있다.
벨만-포드 식의 해답은 각 노드 포워딩 테이블의 엔트리를 제공한다.
모든 노드가 자신의 거리 벡터를 비동기적으로 교환하는 동작을 계속하다 보면, 비용 추정값은 노드 x에서 노드 y까지의 실제 최소 비용 경로의 비용으로 수렴하게 된다.
거리 벡터(DV) 알고리즘
DV 알고리즘에서는 어떤 노드 x가 자신에게 직접 연결된 링크 중 하나의 비용이 변경된 사실을 알게 되거나 어떤 이웃으로부터 변경된 거리 벡터를 수신했을 때 자신의 거리 벡터 추정값을 갱신한다. 그러나 특정 목적지 y에 대한 자신의 포워딩 테이블을 갱신하기 위해 노드 x가 정말 알아야 하는 것은 y까지의 최단 경로 거리가 아니라 y로의 최단 경로상의 다음 홉 라우터인 이웃 노드다.
LS 알고리즘은 다익스트라 알고리즘을 수행하기 전에 각 노드가 네트워크에 대한 전체 지도를 먼저 얻어야 한다는 면에서 중앙 집중형 알고리즘임을 기억하자. DV 알고리즘은 분산적이고 전체 정보를 사용하지 않는다.
세 노드로 이루어진 단순한 네트워크에서의 거리 벡터 알고리즘의 동작을 보여주는데, 알고리즘의 동작은 동기적 방식이다. 즉, 모든 노드가 동시에 이웃에게서 거리 벡터를 받고, 새로운 거리 벡터를 계산해서 변화가 있다면 그들의 이웃에게 알린다.
그림의 가장 왼쪽 열은 세 노드 각각의 최초 라우팅 테이블 모습이다. 특정 라우팅 테이블에서 각 행은 거리 벡터다. 각 노드의 라우팅 테이블은 자신과 이웃들의 거리 벡터를 갖는다.
노드들이 거리 벡터를 재계산한 후에, 만약 변화가 있다면 갱신된 거리 벡터를 다시 이웃들에게 보낸다. 새로운 거리 벡터 정보를 수신하면 세 번째 열에 보인 대로 노드는 다시 자신의 거리 벡터를 재계산하고 라우팅 테이블을 갱신한다.
이웃으로부터 갱신된 거리 벡터를 받고, 라우팅 테이블 엔트리를 재계산하고, 목적지까지 최소 비용 경로의 비용 변경값을 알리는 과정은 더 이상의 갱신 메시지가 없을 때까지 계속된다.
거리 벡터(DV) 알고리즘: 링크 비용 변경과 링크 고장
거리 벡터 알고리즘을 수행하는 노드가 자신과 이웃 사이 링크의 비용이 변경된 것을 알게 되면, 자신의 거리 벡터를 갱신한 후, 최소 비용 경로의 비용에 변화가 있는 경우에는 이웃에게 새로운 거리 벡터를 보낸다.
거리 벡터 알고리즘은 정지 상태가 될 때까지 두 번만 반복하면 된다.
거리 벡터 알고리즘: 포이즌 리버스 추가
(생략)
링크 상태 알고리즘과 거리 벡터 라우팅 알고리즘의 비교
DV와 LS 알고리즘은 경로를 계산할 때 서로 대비되는 방법을 취한다. DV 알고리즘에서 각 노드는 오직 직접 연결된 이웃과만 메시지를 교환하지만, 자신으로부터 네트워크 내 모든 노드로의 최소 비용 추정값을 이웃들에게 제공한다. LS 알고리즘은 전체 정보를 필요로 한다.
각각의 모든 라우터에 LS 알고리즘이 구현된다면, 각 노드는 다른 모든 노드와(브로드캐스트를 통해) 통신하지만, 오직 자신에 직접 연결된 링크의 비용만 알린다. N은 노드(라우터)의 집합이고, E는 에지(링크)의 집합임을 기억하자.
- 메시지 복잡성
- 링크 상태 알고리즘에서 각 노드는 네트워크 내 각 링크 비용을 알아야 한다.
- 링크 비용이 변할 때마다 새로운 링크 비용이 모든 노드에게 전달되어야 한다.
- 거리 벡터 알고리즘에서는 매번 반복마다 직접 연결된 이웃끼리 메시지를 교환한다.
- 링크 비용이 변하고, 이 새로운 링크 비용이 이 링크에 연결된 어떤 노드의 최소 비용 경로에 변화를 준 경우에만 DV 알고리즘은 수정된 링크 비용을 전파한다.
- 수렴 속도
- 거리 벡터 알고리즘은 천천히 수렴하고 알고리즘이 수렴하는 동안 라우팅 루프가 발생할 수 있다.
- 무한 계수 문제가 일어날 수 있다.
- 견고성
링크 상태 알고리즘에서 라우터는 연결된 링크에 대해 잘못된 비용 정보를 브로드캐스트할 수 있다.- 노드는 링크 상태 브로드캐스트를 통해 받은 패킷을 변질시키거나 폐기할 수 있다.
- 하나의 링크 상태 노드는 자신의 포워딩 테이블만 계산하고, 다른 노드들 역시 자신의 테이블을 만들기 위한 유사한 계산을 수행하는데, 이는 링크 상태 알고리즘에서
경로 계산이 어느 정도 분산되어 수행됨을 의미하고, 따라서 어느 정도의견고성을 제공한다. 거리 벡터 알고리즘에서 노드는 잘못된 최소 비용 경로를 일부 혹은 모든 목적지에 알릴 수 있다.- 각 반복마다 한 노드의 거리 벡터 계산이 이웃에게 전달되고 다음 반복에서 이웃의 이웃에게 간접적으로 전달된다. → 거리 벡터 알고리즘을 사용하는 네트워크에서 한 노드의 잘못된 계산은 전체로 확산될 수 있다.
