네트워크 정리 : Network Layer (Routing/Forwading)

Network Layer 기능

Packetizing

• 출발지에서 네트워크 계층의 패킷안에 payload를 Encapsulation 한다.
• 도착치에서 네트워크 계층의 패킷에서 payload를 Decapsulation 한다.
• payload를 출발지 -> 도착지로 전달할 때 해당 내용물을 사용하거나 변경하지 않는다. 이는 마치 우편물을 배송할 때 중간에 내용물을 확인하거나 바꾸지 않는것과 동일하다.

Routing/Forwarding

• Routing: 출발지로부터 도착지까지 패킷이 이동할 경로를 결정한다.
• Fowarding: 라우터의 input 적절한 라우터의 output으로 패킷을 이동시킨다.
• 서울에서 부산까지의 경로가 여러개 존재한다. 이때 특정 분기점에 위치했을때 경부고속도로로 보낼지, 다른 고속도로로 보낼지 라우팅을 통해 정해지고 포워딩을 통해 정해진 방향대로 보내주는 것이다.

Routing

위와같은 경로가 존재할 때, u에서 z까지의 최소 비용 경로는 무엇일까? 라우팅 알고리즘은 이 최소 비용 경로를 찾는 알고리즘이다.

Link State

• Global 방식으로 모든 topology에 대한 정보를 모든 라우터가 갖게 하는 방식이다.

Distance Vector

• Decentralized 방식으로 각 라우터에 대해서 인접한 topology에 대한 정보만 갖게하는 방식이다.
• 인접 노드들과 상호적으로 정보 교환 및 계산하는 처리가 발생한다.

1. Link State Routing Algorithm

다익스트라 알고리즘을 통해 u, v 노드 간 최소 경로 비용을 계산한다. 이때, 네트워크 topology와 링크의 비용들에 대해서 모든 노드들이 알고 있어야 한다. 또한 각 노드들이 갖고 있는 정보는 모두 동일해야한다.

 

다익스트라 알고리즘 예시

ArrayList<pair>[] adj = new ArrayList[N];
// pair는 다음 노드로 가기위한 비용과 다음 노드의 정보가 들어있다
int dp[N];
// dp는 해당 노드까지의 비용을 업데이트하기 위한 배열

// 시작점을 제외한 모든 노드들에 대해 비용을 최대로 잡아준다, 시작점은 0
for (int i = 0; i < N; i++)
	dp[i] = INF;

dp[S] = 0;

PriorityQueue<Object> pq = new PriorityQueue<>(Comparator.comparingInt(s -> s.비용);

pq.push(new Object(0, S));
while (!pq.isEmpty())
{
	Object obj = pq.poll();
	
	if (dp[obj.다음정점] < obj.비용) continue;

	for (Object next_obj : adj[obj.다음정점])
	{
		if (dp[obj.다음정점] + next_obj.비용 < dp[next_obj.다음정점])
		{
			dp[next_obj.다음정점] = dp[obj.다음정점] + next_obj.비용;
			pq.add(new Object(dp[next_obj.다음정점], next_obj.다음정점);
		}
	}
}

System.out.println(dp[END]);

2. Distance Verctor Algorithm

Bellman-ford equation (벨먼 포드 알고리즘)으로 해결한다. 인접 노드들에 대한 정보를 가지고 가장 짧은 경로를 계산해낸다.

u -> z까지의 최단 경로를 구한다고 할때, 인접 노드 v, w, x 에 대해서 경로 비용을 확인한다.

v -> z 비용, x -> z 비용, x -> z 비용을 확인하고 & u -> (v, w, x) 각 인접 노드까지의 비용을 확인해서 최종 선택을 하게 된다.

3. Path Vector Algorithm

간선에 대한 비용을 따지지 않는 알고리즘이다. 따라서 좀 오래걸리거나 패킷이 많다고 예상되는 경로여도 따지지 않고 갈 수 있는 경로인지만 찾을 때 사용하게 된다.

그림에서 보듯이 존재하는 경로에 대해서만 라우팅 테이블에 적시하게 된다. 후에 인접 노드들과 정보 교환 절차를 통해 더 나은 경로가 있다면 변경해주거나 추가해주게 된다.

예를들어 C노드와 B노드를 봐보자. C노드는 A노드까지 가는 경로에 대해 정보가 없다. 하지만 B노드와 정보교환을 하게 되면 B를 통해 A로 갈 수 있나는 정보를 알 수 있다. 그러면 C는 A 노드에 대해 경로를 C -> B -> A 로 수정할 수 있게 된다.

 

정리

위 그림과 같은 Network 망 구성도를 봐보자. 이때 전국은 Backbone이라는 망으로 연결되어 있고 이는 KT에서 제공한다. 그러면 IPS 사업자들은 그 위에서 (sk, lg, kt)는 네트워크를 제공하게 된다. 이때 ISP들은 여러 네트워크 망을 관리하게 된다. 이런 각 네트워크 망들은 라우팅 알고리즘으로 1. Link State, 2. Distance Vector 중에서 골라서 사용하게 된다. 보통 규모가 작으면 1번, 크면 2번을 사용한다. 이후 각 ISP들이 갖고있는 네트워크 망 간 라우팅 알고리즘을 위해서 3. Path Vector를 사용한다.