ICMP (Internet control message protocol)

네트워크 상에서 증상을 알기 위한 컨트롤 메시지를 운반하는 프로토콜이다. IP 패킷을 처리할 때 발생하는 에러를 알려주며 보통 네트워크 진단을 위해 많이 사용된다.

목적지의 호스트가 없거나 목적지 port에 서버 프로그램이 없는 등의 에러 상황이 발생하면, IP header에 기록되어 있는 출발지 호스트에게 해당 에러를 알려주는 기능을 한다.

그림과 같은 종류가 있으며 네트워크 계층의 IP 데이터그램에 포함되어 전송된다.

IPv6

앞서 IPv4가 곧 고갈될 것으로 예상됨에 따라 IPv6가 등장했다고 했다.

IPv6 datagram format

IPv6는 고정된 40바이트의 헤더를 갖고 있으며 단편화 (fragmentation)를 허용하지 않는다.

• Priority : flow 안에서 데이터그램 간의 우선순위를 식별.
• flow label : 같은 flow 안에 있는 데이터그램들을 식별. (하지만 flow라는 개념은 아직 명확하게 규정되지 않았다.)
• next header : 상위 계층 프로토콜을 식별.

Transition from IPv4 to IPv6

IPv4를 사용하는 라우터는 한번에 IPv6로 업그레이드할 수 없다. 따라서 현재는 IPv4와 IPv6의 과도기이다.

하지만 언제까지 기다릴 수는 없으므로 IPv4와 IPv6를 혼용하는 방식이 등장했는데 이를 tunnerling 이라고 한다.

Tunnerling

IPv4 라우터를 거쳐갈 때 IPv6 데이터그램을 IPv4의 데이터 필드 (payload)에 포함해서 전송한다.

IPv4와 IPv6는 버전이 달라서 서로를 인식하지 못한다. 따라서 새로운 버전의 패킷을 이전 버전의 패킷 안에 넣어준 채 전달할 수 밖에 없다.

Routing Algorithm

Interplay between routing, forwarding

포워딩이라는 작업은 단순히 포워딩 테이블을 Look Up하는 것에 지나지 않는다. 또한 포워딩 테이블 Look Up은 Longest prefix match로 이루어진다.

이때 이 포워딩 테이블은 라우팅 알고리즘에 의해 채워진다고 했다.

Routing algorithm classification

라우팅 알고리즘은 다음과 같은 종류가 있다.

Global vs Decentralized information

Global

• 모든 라우터들은 완벽한 topology와 link cost 정보를 가진다.
• link state algorithm이 있다.
• link state : 모든 노드가 자신의 링크 정보 (Link State)를 브로드캐스트로 전체에게 알려준다.

Decentralized

• 라우터는 물리적으로 연결된 이웃을 알고있고, 그 이웃까지의 이동 비용을 알고 있다.
• 이웃과 정보를 교환하는 반복 계산 과정을 거친다.
• distance vector algorithm이 있다.

Static vs Dynamic

Static

• 관리자가 수동으로 경로를 입력한다.
• 시간이 지나면서 경로가 느리게 바뀐다.

Dynamic

• 라우터가 상황에 따라 경로를 동적으로 결정한다.
• 경로가 더 빨리 바뀐다.
  • 정기적으로 업데이트되며, 이동 비용에 따라 변경된다.

Link-State Algorithm

Link-State 알고리즘은 다익스트라 알고리즘을 사용한다.

다익스트라 알고리즘은

• 모든 노드의 topology와 경로 비용이 알려져있다.
  • 이 정보들은 link state 브로드캐스트를 통해 알려진다.
• 출발지부터 다른 노드까지의 경로 중 가장 짧은 경로를 계산하여 포워딩 테이블을 채워넣는다.

다익스트라 알고리즘에서 알아야 할 정보는 다음과 같다.

• c(x,y) : 노드 x부터 노드 y까지의 경로 비용. (이웃하는 노드끼리만 계산 가능. 이웃하지 않으면 무한대로 가정)
• D(v) : 출발지부터 노드v까지의 현재 경로 비용.
• p(v) : 출발지부터 노드v까지의 경로 중에서 v 직전의 노드.
• N' : 최소 비용의 경로가 확실하게 파악된 노드.

이를 기반으로 다음의 예시를 풀어보자.

출발지 u 부터 z까지 이동하는 최소한의 경로를 찾는다.

1. N'에 출발지인 u를 넣어 초기화한다.

u와 이웃한 노드는 그 경로 비용와 p(노드)를 기록한다.
표 상에서 D(v), D(w), D(x)는 u에서 시작했으므로 p에 각각 7,u / 3,u / 5,u로 적을 수 있다.
이웃하지 않은 노드는 무한대로 적는다.

이후 3개의 인접 노드 중에서 경로가 제일 짧은 노드는 w이므로 N'에 w를 넣는다.

2. w와 이웃한 노드를 토대로 표의 D를 업데이트한다.

업데이트는 D(v) = min(D(v), D(w) + c(w, v)) 의 공식을 따른다. 즉, 기존의 D(v) 값과 새로 구한 D(w) + c(w, v) 중에서 더 작은 값을 선택한다.

w와 이웃한 노드는 x, y, v 이다.

x ) 기존의 5와 공식에 따라 새로 구한 7 중에서 5를 선택한다.
y ) 기존의 무한대와 공식에 따라 새로 구한 11 중에서 11을 선택한다.
v ) 기존의 7과 공식에 따라 새로 구한 6 중에서 6을 선택한다.

값이 새로 바뀌었다는 것은 경로가 바뀌었다는 뜻이다. 즉, 원래 경로보다 w에서 오는 경로가 더 짧으니 이걸로 바꾸겠다는 뜻이므로 p 값은 w로 변경된다.

반복

이런 식으로 반복을 거쳐서 노드 u의 포워딩 테이블을 채울 수 있다.

Link-State 알고리즘은 이렇게 다익스트라 알고리즘에 기반하여 포워딩 테이블을 채우는 라우팅 알고리즘이다.