주제 : 라우팅 알고리즘
ICMP Internet Control Message Protocol
host에게 router가 어떤 report를 해주기 위한 메시지 프로토콜
어떤 라우터에서 ttl이 0이 되어서 drop을 했을 때, 이 사실을 호스트에게 알리면 host의 다음 동작이 쉬울 것이다.
그냥 이런게 있는 갑다 하면 된다 근데 여기 Ping Pong이 있었네 ㄷㄷ
Ipv6와 터널링
자세히 알 필요 없다. 아직 v4를 많이 쓰니까.
과도기에는 v4, v6이 혼재할텐데, 이러면 v4를 쓰는 라우터가 이해를 못할 수도 있지 않은가?
그래서 v6의 메시지를 v4 타입에 맞게 래핑해서 보내는 '터널링' 방식을 사용한다고 한다.
라우팅 알고리즘 : forwarding table을 어떻게 만들것인가?
포인트 : 최소 cost 경로 찾기
2가지 접근 방식이 있다.
- 전체 네트워크를 다 알고 있을 경우
- 내 이웃들로부터 정보로 유추를 하는 경우
둘 다 알아보자
1. Link State 알고리즘 : 전체를 다 알고 있을 경우
각 라우터가 알아서 각자 테이블을 설계해야 한다.
나는 U의 입장에서, 서로 브로드캐스팅을 해서 저런 그래프를 만들었다.
이제 테이블 만들기를 시작하자.
내가 최종적으로 원하는 테이블은
destination | next
v |
x |
y |
w |
z |
여기서 next를 찾는 과정일 것이다.
이 테이블 만들기는 Dijkstra 알고리즘을 사용해서 만든다.
- Init (라운드0)
N'은 내가 확실히 아는 구간이다. 내 자신은 안다. N'=u
내 이웃들에 가는 구간은 안다. 위 그림을 보자. x 가는데 5, w 가는데 3, v가는데 7, 나머진 몰라. 이를 표로 그리자.
- 라운드1
라운드 에서 가장 가까운 거리를 잡는다. w다. 나는 이제 u에서 w까지 가는 최소 경로는 확실히 안다. 동그라미 치고, 저건 이제 안 건드려도 된다.
N' = uw(u에서 w까지 커버 가능)
나머지 경로를 하나 하나 보자.
D(v) : u에서 가려면 7인데, w 거쳐서 가면 3 + 3= 6이다. => 6,w로 교체
D(x) : u에서 가려면 5, w 거쳐서 가면 3 + 4 = 7 => 5,u로 냅둬
D(y) : u에선 못갔는데, w에서 8이니까 3 + 8 = => 11,w
D(z) : w에서도 이웃 아니다. 그대로 무한대
가장 짧은 건? 5,u 동그라미 치고.
자 업데이트 하면
- 라운드 2
N' = xuw
D(v) : x거쳐서 가니까 더 길다. 5+4+3 = 12다. -> 그대로 6,w
D(y) : 5 + 7 = 12다. 냅둬 -> 11,w
D(z) : 5 + 9 =14 => 14,x
동그라미는 v에
업데이트하면
이런식으로 커버 범위를 늘리다보면
이런 그래프와 표가 나온다.
이를 바탕으로 테이블을 그리면
'목적지' : '다음 라우터'
정보가 나온다.
이 코스트가 고정이 아니니까 일정 주기마다 업데이트를 할것이고, 그 때마다 트래픽 등 고려되서 경로가 계속 바뀔 수 있단다.
Q. 그럼 모든 전세계 라우터에 브로드캐스팅하는게 현실적으로 가능?
그래서 관리주체가 명확한 하나의 네트워크 내의 라우터들은 이게 가능. ex) 네이버 회사 내 네트워크, 삼성 내 네트워크
이들을 연결하기 위한 라우터가 또 전세계에 있을 건데, 요건 커버가 안된다.
그렇다면?
2. Distance vector 알고리즘
내 이웃들의 정보만 가지고 알아내는 방법이다.
나는 U다. a,b,c랑 이웃인데, X한테 메시지를 보내려면,
무조건 이웃들을 거쳐서 갈 것이다.
그렇다면, 내가 아는건 나와 이웃 사이의 거리일 것이고,
이웃은 또 지 이웃의 거리를 포함해서 가는 것이다.
그렇게 재귀적으로 가면 알 수 있다고 한다.
직관적으로 이해가 됬다면, 자세한 건 다음시간에 계속...
