연습 문제 | Notion

[Q1] Dijkstra 알고리즘을 활용해서 아래의 그래프에서 출발지 노드인 u에서 다른 노드들로 가는 최단 경로 비용을 단계별로 계산하라. 또한, 출발지 노드 u의 각 목적지에 대한 포워딩 테이블도 나타내라.

step	N	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
0	u	7,u	3,u	5,u	무한대	무한대
1	u w	6, w		5,u	11,w	무한대
2	u w x	6, w			11, w	14, x
3	u w x v				10, v	14, x
4	u w x v y					12, y
5	u w x v y z

D(v) = min(D(v), D(w) + cw,v)

포워딩 테이블 u에서 어디로 가야지 해당 목적지로 갈 수 있는가
x만 u에서 x로 가야하고
나머지는 w로 가야지 목적지로 갈 수 있음

[1] ISP A는 ISP B에 A-W 및 A-V 경로를 알려주고, ISP C에 A-V 경로만 알린다

[2] ISP A의 정책은 V로 가는 트래픽을 ISP B 또는 C를 통해서 라우팅 되도록 했고, ISP B는A-W 및A-V 경로를 알고 있으며, ISP B와 C는 서로의 트래픽을 자신의 네트워크에 통과시키는 것을 합의했기 때문에, ISP C에 해당 경로를 알려 준다. 따라서 ISP A로부터 ‘A-V’ 경로를 받게 되며, ISP B로부터 ‘B-A-V’, ‘B-A-W’ 경로를 받게 된다.