[컴퓨터네트워크] 기말고사 정리본 (3)

forwarding : 들어오는 패킷을 만들어진 routing table을 보고 해당 interface로 내보내는 것

routing : router에서 routing table을 만드는 것

router는 routing packet을 주고받으면서 path를 찾는데 이 routing packet 자체가 굉장히 오버헤드이다.

routing의 challenge

(1) routing은 distributed manner에서 진행되어야 한다.

(2) Quality and availability of routes change with time.

routing metric : cost

ex) delay, number of hops, throughput

문제점 : 어떤 source, destination에서든 sum of cost를 최소화하는 길을 찾아야 한다.

=Shortest Path Routing Problem (SPRP)

s(a, b) : shortest between

w(a, b) : a와 b를 연결하는 edge의 cost

d(a, b) : a와 b를 연결하는 shortest path의 minimum cost

즉, d(a,b) = w(s(a, b))

SPRP의 특징

(1) 주어진 source vertex에서 SPRP의 solution들의 합은 tree를 구성한다. 

= source node에서 모든 node에 대한 shortest path들의 union은 tree를 구성한다.

tree : 두 노드 사이에 오직 하나의 길 밖에 없는 그래프 (사이클 존재 X)

(2) s(a, c) = (a,.., b.., c) 일 때 s(b, c)는 s(a, c)의 subtree이다. "optimal substructure" -> 작은 tree를 먼저 구해서 combine 하면 large tree를 쉽게 구할 수 있다.

Optimal substructure of SPRP = divide and conquer : Bellman Ford Algorithm. DVR (distance vector routing)

solution propagates from the destination to the source

d(a, x) = min( w(a, v) + d(v, x) } -> 모든 v에 대해서.

v를 정보를 계속 받으면서 shortest path가 바뀐다. = initial belief 가 wrong 일 수 있고, 계속 update가 필요하다.

오직 neighbor에게만 distance vector를 보내준다. (내 distance vector 바뀔 때마다.) -> routing packet의 수가 적음.

다만, global minima가 아닌 local minima를 찾게 되고, algorithm이 converge slow!

neighbor의 distance vector를 받으면 나의 distance vector도 수정한다.

Distance Vector Routing의 특징

(1) routing packet을 주고받는 총 수는 상대적으로 적다.

(2) algorithm이 converges slow

(3) node의 수가 많을 때엔 not useful 하며 잘 scale 되지 않는다. (size ~15 hop 까진 괜찮다.)

small and fast network엔 잘 동작한다.

Link State Routing (LSR) : DVR과 달리 start with the global map of the network

uses Dijkstra's algorithm (also relies on optimal substructure of the problem)

build solution from the source 'pick and merge'

(1) 모든 노드가 자신과 연결된 link의 정보를 모든 노드에게 퍼뜨린다.

= reliable flooding (link state packets) (대신, 필요 없는 LSP의 전송은 최소화해야 한다.)

(2) shortest path를 다익스트라의 알고리즘을 이용하여 계산한다.

Link State Routing의 특징

(1) LSR is based on DA

solution propagates from source to destination

(2) LSR always works with complete map of the network

stabilize quickly, responds well to changes, reasonable amount of generated messages

(3) 단점 : need to store all the link states of all the nodes in the network (big network에선 생각보다 클 수도 있다.)

 

RIP : routing information protocol (DVR)

OSPF : open shortest path first (LSR) -> authentication, load balancing, hierarchical routing (scalability)