1. ICMP: 안 됐다고 말해주는 수단
라우터는 패킷을 버려도 알려주지 않습니다. 보낸 쪽은 응답이 없다는 것만 알 뿐, 어디서 왜 막혔는지 짚을 수 없습니다. 이 틈을 ICMP(Internet Control Message Protocol, 인터넷 제어 메시지 프로토콜)가 메웁니다.
ICMP 메시지는 IP 데이터그램에 실려 다닙니다. 그래도 계층은 네트워크 계층으로 칩니다. 상위 계층을 위해 일하지 않고, 네트워크 계층이 제 사정을 알리는 데만 쓰기 때문입니다. 헤더는 type과 code 각 1바이트로 시작합니다. type으로 크게 나누고 code로 사유를 좁힙니다.
| type | code | 이름 | 언제 발생 |
|---|---|---|---|
| 8 | 0 | Echo Request | ping이 보내는 쪽 |
| 0 | 0 | Echo Reply | ping에 답하는 쪽 |
| 3 | 0 / 1 / 3 | Destination Unreachable | 네트워크·호스트·포트에 닿지 못함 |
| 11 | 0 | Time Exceeded | TTL이 0이 되어 버려짐 |
type 3의 code 3은 자주 만나게 됩니다. 호스트는 살아 있는데 그 포트에서 아무도 듣지 않을 때 돌아옵니다. demultiplexing이 갈 곳을 못 찾았다는 뜻입니다.
traceroute는 이 중 type 11을 써먹습니다. TTL을 1부터 하나씩 올려가며 패킷을 던지면, 라우터들이 차례로 TTL을 0으로 만들면서 자기 주소로 "시간 초과"를 돌려보냅니다. 그 주소를 순서대로 적으면 경로가 나옵니다.
2. 라우팅을 그래프로 바꾸기
라우터를 점으로, 링크를 선으로, 링크 비용을 선의 가중치로 놓습니다. 그러면 라우팅은 최소 비용 경로를 찾는 문제가 됩니다.
푸는 길은 둘입니다. 모두가 지도 한 장을 똑같이 나눠 갖고 각자 계산하거나, 지도 없이 옆 노드와 숫자만 주고받거나.
3. link state: 지도를 나눠 갖고 Dijkstra
link state(링크 상태) 방식에서는 라우터마다 자기에게 붙은 링크 사정을 네트워크 전체에 뿌립니다. 그래서 모두가 같은 지도를 갖게 되고, 각자 Dijkstra 알고리즘을 돌려 자기 기준 최단 경로를 구합니다.
절차는 이렇습니다. 아직 확정하지 않은 노드 가운데 비용이 가장 작은 것을 하나 집어 확정합니다. 그 노드를 거치면 더 싸지는 이웃이 있는지 보고, 있으면 값을 고칩니다. 전부 확정할 때까지 이 두 가지를 반복합니다.
위 그래프에서 u를 출발점으로 돌려보겠습니다.
| 단계 | 확정 | D(v) | D(w) | D(x) | D(y) | D(z) |
|---|---|---|---|---|---|---|
| 0 | u | 2, u | 5, u | 1, u | ∞ | ∞ |
| 1 | u, x | 2, u | 4, x | 2, x | ∞ | |
| 2 | u, x, v | 4, x | 2, x | ∞ | ||
| 3 | u, x, v, y | 3, y | 4, y | |||
| 4 | u, x, v, y, w | 4, y | ||||
| 5 | 전부 |
칸마다 비용과 직전 노드를 적었습니다. x를 확정하자 w까지 가는 값이 5에서 4로 내려갔고, y를 확정하자 다시 3으로 내려갔습니다. 마지막에 경로를 거꾸로 따라가 "처음에 넘길 이웃"만 남기면 forwarding table이 됩니다. u에서는 w로 가는 것도 z로 가는 것도 전부 x로 내보내면 됩니다.
4. distance vector: 옆 노드와 숫자만 주고받기
distance vector(거리 벡터) 방식에서는 아무도 지도를 갖지 않습니다. 노드는 목적지마다 최소 비용을 적은 표 하나만 들고 있습니다. 그 표를 옆 노드에게 보냅니다. 받은 쪽은 자기 표를 고쳐보고, 값이 바뀌었으면 다시 자기 옆으로 보냅니다.
고칠 때 쓰는 식이 Bellman-Ford 방정식입니다.
dx(y) = min over v { c(x, v) + dv(y) }x에서 y까지 얼마나 드는지 알고 싶으면, 이웃 v마다 "x에서 v까지 드는 값 + v가 알려준 y까지의 값"을 더해보고 제일 작은 것을 고릅니다. 전체 경로를 몰라도 이웃까지의 비용과 이웃이 불러준 숫자만 있으면 계산이 끝납니다.
x-y가 2, y-z가 1, x-z가 7인 세 노드로 따라가 보겠습니다.
처음 : x는 z까지 7이라고 알고 있다
y 알림: "나는 z까지 1"
x 계산: min(7, 2 + 1) = 3
결과 : x는 z로 갈 때 y를 거치기로 한다값이 더 안 바뀔 때까지 이 주고받기를 반복하면 전체가 최단 경로에 수렴합니다.
5. 두 방식 비교
| link state | distance vector | |
|---|---|---|
| 역할 | 지도를 공유하고 각자 계산 | 이웃과 요약된 거리만 교환 |
| 아는 범위 | 네트워크 전체 구조 | 이웃까지의 비용과 이웃의 표 |
| 계산 | Dijkstra, 한 번에 끝남 | Bellman-Ford, 반복해서 수렴 |
| 메시지 | 전체에 뿌림 | 이웃에게만 보냄 |
| 오버헤드 | 메시지는 많지만 빨리 수렴 | 메시지는 적지만 느릴 수 있음 |
| 약한 점 | 지도를 통째로 들고 있어야 함 | 나쁜 소식이 더디게 퍼짐 |
마지막 줄을 조금 풀면 이렇습니다. 링크가 싸졌다는 소식은 금방 퍼집니다. 반면 비싸졌다는 소식은 이웃끼리 서로의 옛날 값을 보며 조금씩만 올리기 때문에, 제값에 닿기까지 여러 번 주고받아야 합니다.
