📌 Routing Algorithm?

들어온 패킷을 어느 인터페이스로 보낼 지를 결정하는 네트워크의 소프트웨어 일부분이다. 라우터는 CPU가 라우팅 테이블 엔트리를 보고 어느 인터페이스로 보낼 지를 결정한다. 그렇다면 이 라우팅 테이블 엔트리는 어떻게 만들어지는 지에 대해 알아보자.

우선 Datagram Packet Switching 방식에서 라우터의 CPU가 패킷을 받으면 이 패킷을 어느 인터페이스로 보낼 지를 결정하는 시점은 바로 패킷이 들어올 때이다.
그리고, Virtual Circuit Packet Switching 방식에서는 Signaling Message를 보낼 때, 즉 처음 Virtual Circuit을 setup할 때 결정한다.

물론 IP는 Datagram Packet Switching 방식을 사용한다. 그렇기 때문에 패킷들이 서로 다른 길을 갈 수도 있고, 도착하는 순서가 어긋날 수도 있다.

한편, Routing Algorithm이 갖춰야 될 성질들이 존재한다.

• Correctness : Destination까지 패킷이 잘 도착함을 보장해줌.
• Simplicity : 짧은 시간 안에 최대의 길을 찾아서 가장 단순한 경로를 선택해야 함.
• Robustness : 전체 인터넷 중 일부에서 문제가 생기더라도 Source에서 Destination까지의 경로를 찾을 수 있어야 한다. 즉, 장애 대응력이라고 할 수 있다.
• Fairness : 자원을 공정하게 사용해야 한다는 것이다.
• Optimality : 자원을 효율적으로 사용해야 한다는 것이다.

이때, Fairness와 Optimality는 동시에 만족시킬 수가 없다.

예를 들어, 다음과 같은 네트워크가 있다고 해보자. 여기서 A, B, C가 통신하면서 X가 통신할 수는 없다. 충돌이 발생하기 때문이다. 여기서 효율이 가장 좋으려면 A, B, C만 통신이 가능하게 하고 X는 아예 통신을 하지 못하게 한다면 가장 효율적이다. 그러나, 자원을 공정하게 사용하려면 일정 시간 동안 A, B, C가 통신하고, 그 시간 이후에는 X가 사용하고 이렇게 번갈아가면서 사용해야 한다. 이처럼 Fairness와 Optimality는 동시에 만족시킬 수 없다.

대신 이 차이를 최소화하여 라우팅 하도록 해주는 노력들을 알아보자.

• Source에서 Destination까지 거치는 hop(=네트워크)의 수를 최소화
• Delay가 최소가 되는 길을 선택
• 소비되는 Bandwidth의 양을 줄이는 길을 선택
• throughput이 제일 높은 길을 선택

하는 방법들로 Fairness와 Optimality 사이의 간극을 좁히려고 한다. 이런 경로를 찾기 위한 것이 Routing Algorithm이 하는 일이다.

🆚 Static VS Dynamic

Routing Algorithm은 크게 Static한 방식과 Dynamic한 방식으로 나뉜다. Static은 말 그대로 Routing Table Entry를 사람이 직접 입력하는 방식이다. 반면, Dynamic한 방식은 라우터들끼리 서로 정보를 주고 받아서 네트워크 상황에 따라 Routing Table Entry가 변할 수 있도록 하는 방법이다.

✅ Dynamic Routing Algorithms

그렇다면 이런 Dynamic한 방식에서는 어떤 기준으로 경로를 선택할까?

예를 들어, Source에서 Destination까지 가는 길이 2개가 있다고 해보자. 한쪽은 사이에 네트워크가 1개만 있지만, 다른 경로는 사이에 네트워크가 20개가 있다고 해보자. 이렇게만 본다면 전자를 선택하는 편이 좋은 경로인 것 같다.
하지만, 네트워크의 속도를 봤을 때 전자는 100Mbps의 속도를 지원하지만, 후자는 10Gbps의 속도를 지원한다고 해보자. 이렇게 되면 어떤 경로를 선택해야 할까?

단순하게 생각해본다면 Delay = Propagation Delay + Transmission Delay였다.

Propagatoin Delay = Distance / 200,000km/s
Transmission Delay = Size / Transmission Velocity

여기서 Delay를 최소화하는 것을 기준으로 생각해본다면, 보내는 트래픽의 크기가 커지면 Transmission Delay가 더 Delay에 영향을 많이 끼치므로 전송 속도가 빠른 후자를 선택해야 Transmission Delay가 줄어들어 더 Delay를 줄일 수 있고, 트래픽의 크기가 작은 편이라면 Propagation Delay가 더 도미넌트하므로 거리가 짧은 쪽인 전자를 선택하는 게 더 좋다고 할 수 있겠다.

이렇게 Routing 경로를 정하는 요소들은 여러 가지가 있다.

• 어디서 알려주는가? - 인접한 라우터, 다른 먼 라우터, 스스로 깨닫기 등(여기로 보내면 트래픽이 느려지는구나)
• 언제 경로를 바꾸어야 할까? - 매 초마다, 트래픽이 변할 때마다, Topology가 변할 때마다 등
• 무엇을 기준으로 길을 바꾸어야 할까? - 거리, hop의 개수, Delay 등

Optimality principle

여기부터는 조금 이론적인 내용이다.

If router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route
-> 만약 라우터J가 라우터I에서 라우터K까지 가는 최적의 경로상에 존재한다
면 라우터J에서 라우터K까지 가는 최적의 경로 또한 같은 루트이다.

어찌보면 당연한 말이다. 여기서 모든 Source에서 주어진 Destination까지의 최적의 길을 설정해둔 것을 Sink Tree라고 한다. 더 간단히 말하면 주어진 노드를 목적지로 하고 다른 모든 노드를 소스로 하여 형성된 최소 비용 트리 라고 할 수 있다.
이 Sink Tree는 loop를 포함하지 않는다. Loop가 존재하면 패킷이 반복해서 경로를 돌아 제대로 도착을 못할 수도 있기 때문이다.

그래서 모든 라우팅 알고리즘들은 모든 라우터에서의 Sink tree를 찾고 사용하고자 하지만, 각 라우터마다 서로 인지하고 있는 Sink tree가 다를 수 있어서 결코 쉬운 작업이 아니다.

🛜 Network Algorithms

역시 개념적인 이야기이다.

• Undirected Graphs
  Graph G = (N,A)로 표현하고, N은 노드, A는 Arc로 edges와 동의어이다.

다른 개념들도 알아보자.

• Walk : 갈 수 있는 길이라는 것으로 loop를 포함한 모든 길을 말한다. 그렇기 때문에 이 Walk의 개수는 셀 수 없다.(loop를 포함하기 때문)
• Path : loop를 포함하지 않는, 즉 같은 노드를 더 포함하지 않는 Walk로 유한개이다.
• Cycle : Source와 Destination이 같은 Walk를 말한다.
• Connected : 어떤 노드 i와 다른 노드 j간에 path가 존재한다면 이는 연결된 것이다.

G가 Connected graph이고 S가 이 G의 N으로 이루어져있는 비어있지 않은 부분집합이라고 해보자. 이때, i와 j 간에는 적어도 하나의 arc가 존재한다.

이 역시도 당연한 말이다. G라는 그래프에서 한 부분을 선택한 부분집합과 다른 선택되지 않은 부분은 당연히 연결되는 arc가 존재할 수 밖에 없다. 이 그래프는 애초부터 Connected Graph였기 때문이다.

• Tree : Connected Graph 중에서 Cycle이 없는 그래프이다.
• Spanning Tree : G의 모든 노드를 포함하는 tree이다.
  

예를 들어, a라는 G에서의 Spanning Tree는 b와 c가 된다. 이 Spanning Tree는 Bridge 부분에서 Loop Bridge라는 내용으로도 이미 한번 다루었다.

Algorithm to construct spanning tree

Spanning tree를 만드는 알고리즘을 알아보자.

1. Root node를 설정해야 한다.
2. 모든 노드가 아직 선택되지 않았다면, 선택되지 않은 노드와 이미 선택된 노드 혹은 그래프를 연결시킨다.
3. 2번 과정을 반복하다가 모든 노드가 선택되면 종료한다.

여기서 Root Node를 설정하는 것은 각 노드마다 자신을 설정했다면 Spanning tree가 서로 맞물려 loop가 발생할 수 있다. 그래서 이 Root node는 모든 노드가 동일한 트리를 선택할 수 있게 유도하는 것이 중요하다.

MST(Minimum weight spanning tree)

• Minimum weight spanning tree (MST) : arc의 가중치의 합이 최소가 되는 spanning tree이다.
• Fragment : MST의 부분 트리이다.
• Outgoing arc : Fragment에 속한 노드와 속하지 못한 노드를 연결하는 Arc.
• Tree에서는 fragment와 연결된 가장 작은 Weight의 arc를 고르면 그 arc를 통해 MST fragment가 계속 연결될 수 있다.

Algorithm to construct MST

MST를 구성하는 알고리즘은 2가지가 있다.

Prim-Dijkstra

임의로 아무 노드를 고르고, 이 노드를 시작으로 가장 작은 arc들을 골라간다. 이때 고려하는 arc는 항상 outgoing arc를 의미한다.

Kruskal's algorithm

같은 예시에 대해 Kruskal 알고리즘은 가장 Weight가 작은 Arc를 먼저 고른다. 그 후에 계속 가장 작은 Weight를 가지는 arc들을 골라 최종적으로는 하나의 spanning tree로 만드는 것이 목적이다. 이때 주의해야 할 점은 arc를 고를 때 , weight가 작아도 cycle이 생기지 않도록 해야 한다.

Shortest path algorithm

여기서는 Directed graph를 다룬다. 역시 G=(N,A)로 표현하지만, A 집합에서는 순서가 존재하게 된다.

이 그래프는 네트워크 상에서 다음과 같은 상황에서 사용될 수 있다. 예를 들어, 클라이언트와 서버 단이 있을 때 전달되는 트래픽 양은 서버 -> 클라이언트 방향이 훨씬 많을 것이다. 이렇게 되면 클라이언트 -> 서버와 서버 -> 클라이언트 간에는 서로 다른 가중치를 가지게 되는 것이므로 방향이 존재한다고 할 수 있는 것이다.

여기서도 마찬가지로 arc라고 부르고, 가중치는 length나 distance로 표현한다. 이를 방향에 따라 d_ij로 표현한다.(i에서 j로 향하는 방향에 대한 가중치)

Shortest path algorithm은 Source에서 Destination까지의 길들이 arc의 집합으로 이루어져있는데, 여기서 distance의 합이 최소가 되는 경로를 찾기 위한 알고리즘이다.