라우팅 알고리즘

라우팅 알고리즘의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것이다. 일반적으로 좋은 경로란 최소 비용 경로를 말한다. 그러나 현실적으로는 네트워크 정책(예를 들면, "y기관에 속해 있는 라우터 x는 Z기관이 소유한 네트워크가 보낸 패킷을 전달해서는 안된다." 와같은 규칙)과 같은 실제 문제가 고려된다. 네트워크 제어 평면이 라우터별 제어 방식을 채택하든 논리적 중앙 집중된 방식을 채택하든 상관없이 패킷이 전송 호스트에서 수신 호스트로 이동하기 위한 잘 정의된 일련의 라우터가 항상 존재해야 한다. 따라서 이러한 경로를 계산하는 라우팅 알고리즘은 근본적으로 중요하다. 

라우팅 알고리즘을 분류하는 일반적인 첫번째 방법은 알고리즘이 중앙 집중형인지 분산형인지를 잘 알아야 한다.

중앙 집중형 라우팅 알고리즘 : 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 즉, 이 알고리즘은 모드 노드 사이의 연결상태와 링크 비용을 입력값으로 한다. 이 알고리즘의 핵심적인 특징은 연결과 링크 비용에 대한 완전한 정보를 가진다는 것이다. 전체 상태 정보를 가지는 알고리즘을 링크상태 알고리즘이라고 한다.

분산 라우팅 알고리즘 : 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지 않으며, 대신 각 노드는 자신에 직접 연결된 인접노드에 대한 링크 비용 정보만을 가지고 시작한다. 이후 반복된 계산과 인접노드와의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지의 최소 비용 경로를 계산한다. 분산 라우팅 알고리즘을 종류로는 거리 벡터 알고리즘이 있다.

라우팅 알고리즘을 분류하는 일반적인 두 번째 방식은 정적 알고리즘과 동적 알고리즘으로 분류하는 것이다. 

정적 라우팅 알고리즘 : 정적 라우팅 알고리즘에서는 경로의 변경이 느리고 사람이 직접 링크에 대한 비용을 수정해야 한다. 이는 규모가 큰 네트워크에서 일일이 수정하기 불가능하며 사람이 하기엔 역부족이다.

동적 라우팅 알고리즘 : 네트워크 트래픽 부하나 노폴로지 변화에 따라 라우터가 자체적으로 경로를 바꾼다. 동적 알고리즘은 주기적으로 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다. 동적 알고리즘은 네트워크 변화에 더 빠르게 대응할 수 있다는 장점이 있지만 경로의 루프나 경로 진동과 같은 문제에는 취약하다는 단점이 있다.

링크 상태 라우팅 알고리즘

링크 상태 알고리즘에서는 네트워크 토폴로지와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다는 점을 기억해야 한다. 이는 각 노드가 자신과 연결된 링크의 식별자와 비용을 포함하는 링크 상태 패킷을 네트워크 상의 모든 다른 노드로 브로드캐스팅 하게 함으로써 가능하다. 링크 상태 라우팅 알고리즘은 다익스트라 알고리즘이라고 부른다.

다익스트라 알고리즘을 계산할때 만약 한 단계에서 동일한 비용의 링크가 나오면 그냥 아무거나 선택하면 된다.

거리벡터 라우팅 알고리즘

링크상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면에, 거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. 각 노드는 하나나 그 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다는 점에서 분산적이다. 이웃끼리 더 이상 정보를교환하지 않을 때까지 프로세스가 지속된다는 점에서는 반복적이다. 또한 모든 노드가 서로 정확히 맞물려 동작할 필요가 없다는 점에서 비동적이라고 할수있다. 

맨 왼쪽 열을 보면 맨처음에는 x y z 노드 모두 자신의 인접 노드의 정보밖에 모르기 때문에 인접노드 제외하고는 모두 무한대로 세팅한다.

두번째 열을 보면 인접노드들에게 자신의 정보를 다 알린다. 예를 들어 y와 z 노드 테이블(첫번째 열에서) 정보를 x에게 알려준다면 x 노드는 y의 정보를 얻게 되며 따라서 y에서 z로 가는 비용이 x에서 z로 가는 현재 7 비용보다 싸다느 것을 알게 된다 . 

따라서 두번 째 열의 x노드의 테이블에서 x->y->z 로 가면3 비용이 들게 된다는 것을 확인가능하기 때문에 테이블이 변경된다. 

이처럼 다른 노드들도 똑같이 수행하게 되면 결국 3번째 열의 각 노드의 테이블은 하나의 동일한 값으로 수렴하게 된다.