8.1 네트워크층의 개요

1. 일반적인 아이디어

유니캐스트 라우팅에서 패킷은 포워딩 테이블을 참조하여, 발신지에서 목적지까지 홉 단위로 전달된다. 발신지 호스트는 포워딩 테이블이 필요 없다. 목적지 호스트 역시 로컬 네트워크에서 목적지 호스트의 기본 라우터로부터 패킷을 전송받으면 되기 때문에 포워딩 테이블이 필요하지 않다. 이것은 인터넷에서 네트워크에 있는 라우터만 포워딩 테이블이 필요하다는 것을 의미한다.

- 그래프로 표현한 인터넷

최적의 경로를 찾기 위해 인터넷은 그래프(graph)를 이용하여 모델링하였다. 컴퓨터 과학에서 그래프는 노드(node)와 노드를 연결한 선(edge)의 집합으로 표현된다. 인터넷은 각 선 사이에 비용을 연관지어 가중치 그래프(weighted graph)를 이용하여 모델링되었다.

2. 최소 비용 라우팅

가중치 그래프로 인터넷이 모델링될 때 발신지 라우터부터 목적지 라우터까지 최적의 경로를 표현하는 방법 중 하나는 두라우터 사이의 최소 비용(least cost)을 찾는 것이다. 다시 말해, 발신지 라우터는 목적지 라우터까지 모든 가능한 경로 중에 비용의 합이 가장 적은 비용을 가진 경로를 선택한다.

가중치로 표현된 그래프

- 최소 비용 트리

만약 인터넷에 N개의 라우터들이 있다면, 각 라우터에서 다른 라우터로 N-1의 최소 비용 경로가 존재한다. 이것은 모든 인터넷에 대해 N X (N-1) 최소 비용 경로가 필요하다는 의미이다. 최소 비용 트리는 루트로써 발신지 라우터를 사용하여 루트와 다른 노드 사이의 가장 짧은 경로를 구하기 위해 모든 다른 노드들을 방문하는 트리이다.

각 노드들의 최소 비용 트리