20180425 13 : 라우팅 알고리즘

ICMP 및 IPv6 

네트워크 레이어에서 가장 중요한 프로토콜이자, 유저 데이터를 운반하는 패킷. IP 패킷을 보면 헤더와 데이터부분이 존재하며 헤더는 목적정보와 주소정보 등의 데이터가 들어가며 데이터 부분에는 주고받고자 하는 데이터가 들어간다. (실제메세지). IP 패킷을 IP 데이터그램이라고 부르는 이유가 여기에 있다.

ICMP
패킷이 소스에서 시작에서 쭉 가다가 목적지에 도착한 경우 해당 목적지의 포트가 열려있지 않은 경우 드롭된다. 여기서 소스는 무슨 일이 일어난지 모른다.

하지만 문제가 발생하였기 때문에, 네트워크에 일어난 일을 소스에게 다시 알려주기 위한 메세지가 필요하다. 이 메세지는 사용자가 보낸 메세지가 아니며 네트워크 사건에 의해 발생하는 메세지이다. 네트워크에서 보낸 메세지 프로토콜이 ICMP 은 이며, Internet Control Message Protocol 의 준말이다.

TTL 이 라우터를 거치면서 1씩 감소하다가 0이 되어버린 경우, 어느어느 상황에서 드롭되었다는 것을 명시하는 것이 ICMP 이며 이를 통해 소스에게 네트워크 사건을 알린다. 네트워크 상황에 발생한 이벤트에 대해서 컨트롤 메세지를 전달하는 프로토콜이다.

사실 신뢰성이 없는 IP 프로토콜을 대신하여 네트워크 상의 연결 여부를 확인하는데 중점이 맞추어져 있고, 문제가 생긴 구간의 원인을 파악하기 위해 사용하기도 한다.

+) 네트워크를 진단하기 위한 유틸리티 : tracert

(1) 윈도우 키 + s 를 입력하자

(2) cmd 입력 후 엔터

(3) 입력 창에 tracert www.naver.com 입력 후 엔터

그렇게 하면 아래와 같은 화면처럼 진행된다. 현재 본인이 이용하고 있는 호스트가 가진 IP 에서 라우터를 거쳐서 www.naver.com 을 접속하기 위한 라우터까지 가는 경로를 보여주는 것이다.

어떻게 이런 일이 가능한가?

첫번째 패킷을 보내며 TTL 을 1보내며, 첫번째 라우터를 거치면서 0되고 드롭되고 ICMP 가 소스로 날라온다. 두번째 패킷을 보내며 TTL 을 2 보내며 이러한 과정을 반복하는 것이다.

IPv6 혹은 다른 프로토콜로 변경하는 경우, 무조건 과도기는 존재할 것이다. 어떠한 과도기를 거치면서 어떻게 해야하는 것인가에 대한 문제에 부딪힌다. 결국 IPv4 에 동작하는 프로토콜도 존재하면서 새로운 프로토콜에 동작하는 프로토콜도 존재할 것이다. 해당 패킷에 대한 해석(이해)를 하는지 안하는지에 대한 결정 문제가 따른다. 결국 새로운 버전의 패킷을 과거 형태의 패킷 포맷에 맞춰출 필요가 있으며 그러한 방식은 해당 패킷을 새로운 프로토콜로 캡슐하고 새로운 프로토콜을 벗어나는 경우 디캡슐화하여 준다. 그리고 이러한 작업을 터널링이라고 부른다.

목적지 주소와 포워딩 엔트리 매칭은 Logest prefix matching 방식을 이용한다. 가장 긴 prefix 매칭을 찾아서 연결시키는 것이다. 포워딩 테이블의 작업은 포워딩 테이블 룩업에 지나지 않는다. 그럼 포워딩 테이블은 어떻게 생성되었는가? 에 대해서 질문을 던질 수 있다. 라우팅 알고리즘이 포워딩 테이블을 채워넣었는데 그 알고리즘을 알아보아야 한다.

라우팅 알고리즘

라우팅 알고리즘의 목적은 최소 비용을 통해서 해당 목적지까지 가야하는 것이다. 접근 방식이 두가지가 존재한다. 

(1) 모든 라우터가 다른 라우터들의 목적지까지 가는 비용을 모두 알고 있는 경우

     >> link state 알고리즘

(2) 하나의 라우터가 자신의 이웃들에게 가는 비용만 알고 있는 경우

     >> distance vector 알고리즘

link state 알고리즘

모든 노드들이 자신의 링크 정보를 브로드캐스트하여서 다른 노드들이 모두 각 노드들의 링크 정보를 가질 수 있도록 한다. 그리고 여기서 사용되는 알고리즘이 바로 다익스트라 알고리즘이다. 특정 노드를 가기 위해 최단경로를 작성하는 것, 결과적으로 해당 포워딩 테이블을 작성하고 채워가는 과정이 다익스트라 알고리즘이다.

(1) u가 출발점이다. N= {u}

(2) v까지의 거리를 초기화시킨다. path[v] = 7

(3) w까지의 거리를 초기화 path[w] = 3

(4) x까지의 거리를 초기화 path[x] = 5

(5) 나머지 노드들은 무한대로 값을 초기화 path[y] = ???, path[z] = ???

(6) 이제 출발점을 제외하고 distance 값이 가장 작은 노드를 찾는다. >> path[w] = 3; N={u,w}

(7) 그리고 N={u, w}에 값에 대해서 distance 를 초기화한다.

(8) (6)과 (7) 과정을 반복하면서 N={} 에 모든 노드들이 가득 찰 때까지 반복한다.

결국 각각의 라우터들이 라우팅 알고리즘을 통해 포워딩 테이블을 구성한다. link state 는 다익스트라 알고리즘 그 자체이다. 다익스트라 알고리즘을 사용할 때 트래픽이 왔다갔다 하는 현상이 발생한다. 특정 라우터에서 경미한 데이터를 보내고 또 다른 라우터가 조금 더 큰 데이터를 보낸다고 가정하자. 이렇게 한 동안 트래픽이 이동할 것이다.

질문 )

여기서 브로드 캐스트의 범위가 어느정도까지인가? link state 알고리즘이 모든 라우터들에게 가는 비용을 계산한다면 전 세계의 라우터까지 비용을 따질 것인가? 작은 네트워크 망, 큰 네트워크 망이 존재하는데 그 범위는 관리 주체가 동일한 하나의 네트워크 집합내에서만 이루어진다. 관할하고있는 네트워크 망에서만 브로드 캐스트 범위를 정하는 것이다. 결과적으로 하나의 도메인에 속한 네트워크인 것이다. 각 네트워크 주체별로 각 라우팅 알고리즘을 이용해 쓰고 있지만, 네트워크끼리 연결하는 라우터들은 어떻게 브로드 캐스트 될 것인가? 거기에 따른 또다른 주체가 존재한다고 한다.

Distance vector algorithm

link state 알고리즘은 브로드캐스트를 통해서 하나의 네트워크 영역에 있는 라우터들의 비용을 알고 있다. Distance vector algorithm 은 주변의 정보를 통해서 최소 경로의 포워딩 테이블을 만든다. Distance vector algorithm 은 그렇기 때문에 사실은 직관적이지 않다. 

d_x(y) = min{c(x,v) + d_v(y)}

source x 에서부터 destination y 까지에 대한 최소 경로는

(x에서 v까지 가는 경로 + v에서 y로 가는 최소경로)의 최소값이다.

위의 식에서 c(x,v) 는 알고 있는 값이다.

그리고 d_v(y) 는 모르는 값이지만 똑같이 recursive 를 통해 구할 수 있다.

d_v(y) = min{c(v, w) + d_w(y)} 로 재귀가 이용된다.

정리 )

• ICMP 란 무엇인가

• 라우팅 알고리즘 종류 두 가지

• link state 알고리즘

• 다익스트라 알고리즘

• link state 알고리즘의 broad cast 의 범위

• distance vector 알고리즘 식과 식 내용 설명