- 다익스트라 알고리즘의 단계별 수행예시다. 숫자 옆의 알파벳은 최단경로로 해당 노드에 도달하기 이전 노드를 의미한다.
- 이전 노드를 추적해가다 보면 최단 경로를 나타내는 트리가 그려진다.
- 다익스트라 알고리즘은 n 번의 루트를 돈다. 최악의 경우 n개가 N 프라임에 전혀 들어있지 않아 n번의 비교를 해야 하는 경우이므로, n(n-1)/2 번의 비교를 수행하여 O(N^2)의 시간복잡도가 걸린다.
- 벨만 포드 알고리즘을 설명하겠다. 위 식은 x로부터 y까지 최단 경로의 길이를 의미한다. 이 최단경로는 x의 이웃 노드를 통해 y로 갈때 다양한 경로들이 있는데, 모든 경로 중 최단 거리가 있다. 아래의 빨간 글씨로 써놓은 식이 그 최단 거리를 찾는 식이다. x로부터 y로 가는 최단 경로 길이는, x에서 이웃인 v로 가는 비용에서 v에서 y로 가는 비용을 더한 것중 최솟값이다.
- 벨만 포드 알고리즘의 예시다. u에서 z로 가는 최단 경로를 찾는다. u에서 이웃한 경로길이 v,x,w로 가는 최단 경로를 구하고 그 경로에서 z로 가는 길이를 더한 것중 미니멈 값이 du(Z)가 된다.
- Distance Vector algorithm은 벨만 포드 알고리즘을 이용하는 것이다. 네트워크강 모든 목적지의 집합은 N일때 Y는 네트워크의 모든 목적지를 뜻한다. Dx(y)는 노드x 로부터 y로 가는 최단 경로인데, 노드 x는 디스턴스 벡터 Dx를 유지 및 관리해야 한다. 모든 목적지 Y에 대해서 x로부터의 Dx(y)가 디스턴스 벡터이다.
- x는 x로부터 인접한 이웃으로의 링크 코스트를 알고 있으며, 이웃의 디스턴스 벡터 와 자신의 디스턴스 벡터를 교환하여 이웃의 정보까지도 알고 있다.
- 디스턴스 벡터 알고리즘은 이웃의 디스턴스 벡터와 자신의 것을 교환해나가며 디스턴스 벡터 정보를 업데이트해 나간다.
- Dx(y)는 x가 경로 v로 가는 비용에서 Dv(y) 정보를 더해서 업데이트해 나가는데, Dv(Y)로 가는 정보를 계속해서 업데이트 하는것이 핵심이다.
- 각 라우터는 자신과 인접한 로컬 링크 코스트를 알고 있고, 이웃과 디스턴스 벡터를 교환한다. 이 교환 정보로 계속해서 자신의 디스턴스 벡터를 업데이트 할 수 있다. 만약 디스턴스 벡터의 변화가 생기면 이웃에게 자신의 변화된 정보를 알려야 한다.
- 각 노드들은 서로의 디스턴스 벡터를 교환하며 무한대였던 경로 길이 정보를 재계산한다.
- 링크 코스트의 변화는 어떻게 디스턴스 벡터에 반영될까. 먼저 좋은 소식(디스턴스 벡터가 줄어든 경우)의 경우, 만약 y에서 x로 가는 링크 코스트가 1로 줄어들면 y는 자신의 벡터를 재계산한다. 이 변경 정보를 이웃에게 알려준다. 따라서 정보를 받은 z는 위의 z에서 x로 가는 비용을 5에서 2로 재계산하여 다시 이 변경 정보를 이웃에게 알린다. 그러나 y는 z의 재계산 소식을 들었지만 그로 인해 본인의 벡터 정보의 변화는 없으므로 어떠한 메세지를 z에 보내지 않는다.
- 그러나 링크 코스트가 들어난 "나쁜 소식"의 경우, 만약 y에서 x가 4에서 60으로 늘어나면 y는 이웃 노드를 쳐다본다. 이때 z는 변경 전 x로 가는 거리를 5로 인식 했으므로, y는 z로 가는 비용 1에 z에서 x로 가는 비용 5를 더해 총 6만에 x로 갈수 있다고 생각한다. 해당 정보로 디스턴스 벡터를 업데이트하면 z는 y로 가는 비용 1에 y에서 x로 가는 비용 5를 더해 6만에 x로 갈 수 있다고 생각하고 벡터를 수정한다. 위와 같은 과정을 44번씩 계속해야 51까지 비용이 늘어나고 z에서 x로 가는 50짜리 길로 경로를 바꿔 정확한 최단경로를 얻어낸다. 따라서 count to infinity라 하여 계산이 과도하게 수행되는 문제가 일어난다.
- 이 문제를 해결하기 위한 방법이 poisoned reverse인데, y가 x의 경로를 찾을 때 z를 통해 가는 길을 고려하지 않고, 먼저 본인이 다이렉트로 x로 가는 길(비용 60)을 파악 후 z에 전달하는 것이다. 그럼 z는 y에서 x로 가는 비용이 60임을 먼저 인지하고 다이렉트로 50짜리 길을 선택할 수 있다. 그럼 y는 그 소식을 듣고 x까지의 경로를 51로 고칠 수 있다.
- 그러나 이마저도 완전히 count to infinity 문제를 해결할 수 없다. 위와 같이 루트에 세 개 이상으로 여러가지 노드가 연관된 경우 z에서 X로 가는 경로가 끊어져 무한대가 되면 사이클이 생겨 무한대까지 각자의 경로가 디스턴스 벡터의 무한한 업데이트로 무한히 늘어난다.
- 다음은 Link state 와 디스턴스 벡터의 비교다
- 먼저 메세지의 복잡성이다. 한 노드가 감당해야 하는 메세지의 양을 의미한다. 링크 스테이트는 네트웤의 모든 노드로부터 링크 스테이트 정보를 받아야 하므로 노드와 링크 수가 늘어나면 처리할 양이 늘어난다. 하지만 DV는 이웃의 링크와만 디스턴스 벡터를 주고받으므로 네트워크 복잡도가 커져도 교환하는 디스턴스 벡터가 늘어나지만 LS만큼 크지는 않다.
- 다음은 speed of convergence의 경우다. LS나 DV나 라우터가 생각하는 목적지 경로가 모두 일관되어야 한다. LS의 경우 알고리즘의 경우 모든 라우터가 똑같은 경로를 갖지만 DV의 경우 경우에 따라 라우팅 루프가 발생하면 count to infinity 문제가 일어날 수 있다. 따라서 convergence time이 경우에 따라 상당히 가변적이다.
- 마지막으로 robustness 측면이다. 어떤 라우터가 맛이 가서 제 기능을 못하면 LS의 경우 문제가 일어난 라우터의 근방에 대해서는 목적지가 잘못 설정될 것이지만 그 라우터 근방을 제외하고는 정상적인 목적지 설정이 된다. 그런데 DV는 한 라우터가 맛이 가면 교환 정보 하나가 전체로 전달 되므로 모든 목적지의 경로가 잘못 될 수 있다. 따라서 DV가 robustness측면에서 좋지 않다.
- 링크 코스트를 고정적 혹을 가변적으로 사용할 수 있다. 링크 코스트가 링크를 지나는 트래픽의 양과 같으면(다이내믹), 마치 진동하듯이 루트가 계속 변경되는 route oscillations이 발생할 수 있다. 짧은 시간안에 루트 정보가 계속 변경하여, 한 목적지로 내보내는 스트림에 속하는 데이터그램이 경로가 전부 변경되어 순서대로 도착하지 못하고 out of order하게 될 수 있는 문제가 발생한다. 또 링크 코스트가 계속 변경되어 라우팅 루프가 발생할 수 있다.
- 네트워크의 규모가 커지면 링크 스테이트는 처리할 양이 너무 커지게 된다. DV의 입장에서도 루프 발생 문제 등이 더욱 심해지게 된다. 따라서 실제로는 네트워크를 autonomous systems(AS) 즉 지역적으로 제한된, 한 기관에 집한 라우터의 집합으로 묶는다. 이 AS내에서 한 가지의 라우팅 프로토콜을 돌려서 이곳에 속한 서브넷의 목적지에 대한 포워딩 테이블을 만든다. 이 안에서 실행되는 라우팅 프로토콜을 intra-AS 라고 부른다. 각 AS끼리도 연결되어야 하므로 이를 gateway router를 통해 연결한다.
- 포워딩 테이블의 서브넷 목적지는 intra as subnet(as 안)와 inter as subnet(as 바깥)으로 나뉜다. intra에서는 인트라 라우팅 프로토콜을 통해 포워딩 테이블을 작성하지만 inter에 대해서는 이 뿐 아니라 이에 더불어 inter as 프로토콜을 사용해서 포워딩 테이블을 작성한다
- inter as와 intra as는 어떻게 협력할까. 위 그림에서 as1의 입장에서는 as 2와 as 3을 통해 도달할 수 있는 목적지가 무엇이 있는지 인지해야 한다. 이를 inter as 라우팅 프로토콜을 통해서 인지할 수 있다. 게이트웨이를 통해 각 as에 어떤 서브넷 목적지가 있는지 전달하는 것이 inter as의 역할이다. 또한 타 as와 연결되어 있는, 예를 들면 as1의 1c와 1b는 외부 세계로부터 어떤 서브넷이 있는지 내부 as에 소문을 내준다.
- 위에서 as3에서 x에 갈 수 있다면 1c는 본인을 거쳐 as3에서 x에 갈 수 있다는 정보를 본인 as 내부에 전달한다. 이것이 inter as의 역할이고, 1d의 입장에서는 x에 보낼 것이 생긴다면 이 정보를 듣고 1c로 가는 길을 내부 테이블에서 파악한 후 내보낸다. 결국 1d는 다른 as에 속한 x로 가기 위한 인터페이스가 무엇인지 포워딩 테이블을 세팅할 수 있다.
하마드