컴퓨터 네트워크 - Routing 알고리즘(Link State, Distance Vector)

K-MOOC에서 부산대학교 유영환 교수님의 “컴퓨터 네트워킹” 강의를 수강하며 적은 노트

Introduction to Routing

N: 라우터 집합, E: 링크 집합
라우팅 알고리즘: 그래프 상에서 최소의 링크 코스트를 갖는 경로 찾기

• 현재 네트워크에서 많이 쓰는 방식: 링크 코스트를 모두 1로 같다고 가정
  • 전체 지연 시간 중 transmission delay, propagation delay보다는 queueing delay가 큼
  • hop 수가 가장 작은 것이 좋은 경로
• 현재 남은 capacity의 역수를 비용으로 계산

알고리즘 분류 방법

• static과 dynamic
  • static: 관리자가 라우트를 결정해 줌, 네트워크 상황 변동이 있으면 관리자가 라우터들에 접속해 값을 수동으로 수정
  • dynamic: 라우터들이 알아서 정보를 주고받은 뒤 라우트 선정
• global과 decentralized
  • global: 모든 라우터들이 전체 네트워크 topology를 다 알고 판단
    • link state 알고리즘
  • decentralized: 자기 주변 정보만 알고 라우트 결정
    • distance vector 알고리즘

---

Link-State Routing

Link-state routing: 각 라우터가 전체 topology 정보를 알고 그 상황에서 길을 설정

LSA 메시지(Link-state advertisement message), LSP(Link-state packet): 자신이 알고 있는 정보들을 다른 라우터들에 보내는 교환 메시지

• neighbor node information: 나와 직접 연결되어 있는 node들에 대한 정보
• neighbor들과 연결된 링크의 상태: 끊어짐, 원활, capacity, 지연 시간 등
• 이웃이 바뀌었거나, 링크의 상태가 변했을 때, 또는 주기적으로 생성하여 모든 라우터들에게 전송

Dijkstra’s algorithm: 하나의 source로부터 네트워크에 있는 모든 node로의 최소 비용 경로 계산

1.	 N’ = {u}
2.	 for all nodes v
3.	   if v adjacent to u
4.	     then D(v) = c(u, v)
5.	   else D(v) = inf
6.	LOOP
7.	 find w not in N’ such that D(w) is a minimum
8.	 add w to N’
9.	 update D(v) for all v adjacent to w and not in N’:
10.	   D(v) = min(D(v), D(w) + c(w, v))
11.	Until All Nodes in N’

• c(x,y): x, y 사이의 link cost
• D(v): 현재 구한 소스부터 v까지의 최소 비용
• p(v): 직전에 지나온 노드
• N’: 현재 최소 비용 경로가 계산된 노드들의 집합
• Oscillation problem: 링크 코스트를 잘 설정하지 않아 생기는 문제

  • ex) Link cost를 그 링크가 전송하고 있는 트래픽 양으로 설정, C->A 찾기, 보낼 트래픽 양 e

    	A	B	C	D
    A	0	1	.	1
    B	1	0	0	.
    C	.	0	0	0
    D	1	.	0	0

  • 임의로 B를 선택해 전송

    	A	B	C	D
    A	0	1+e	.	1
    B	1+e	0	0	.
    C	.	e	0	0
    D	1	.	0	0

  • B가 보니 B->A는 1+e인데, B->C->D->A는 1로 비용이 더 쌈
  • 계속 트래픽이 왔다 갔다

---

Distance Vector Routing

distance vector routing: bellman-ford equation 사용. node들은 기본적으로 각각의 직접 연결이 있는 이웃으로의 경로 비용 c(x,v)를 알고, 각각의 node들은 네트워크 내에 있는 모든 다른 라우터들로의 비용 값을 유지 하는 테이블 가짐

distance vector table: 각 라우터들이 가진 포워딩 테이블, 이웃들과 교환하여 업데이트

• 주로 30초 주기로 주고받음

bellman-ford equation

• Dx(y) = min(c(x, v) + Dv(y))
• Count to infinity problem: bad news가 천천히 알려짐
  • ex) c(x, y) = 4, c(y, z) = 1, c(z, x) = 50
  • 따라서 z가 y로 보낼 때 z->y, z가 x로 보낼 때도 z->y->x
  • 그런데 갑자기 c(x, y)가 60으로 변화
    • y는 이를 감지하고 x로 갈 방법을 찾기 위해, z의 테이블을 봄
    • z의 테이블에는 5로 갈 수 있다고 기록되어 있음(기존의 z->y->x, 1+4)
    • 따라서 y는 x로 갈 때 z를 거쳐 가기로 함, 자신의 테이블 c(y, x)는 6으로 z에게 전달
    • z는 c(y, x)가 4에서 6이 되었으므로, 자신의 테이블에서 c(z, x)를 7로 갱신하여 전달
    • 따라서 c(z,x) = 50을 넘을 될 때까지 1씩 천천히 값이 바뀜
  • poisoned reverse: 해당 노드를 거쳐 가는 경우 inf로 알려 줌
    • ex) z가 x로 가는 길이 y를 거친다면, z는 y에게 자신의 c(z, x) = inf로 가르쳐 줌
    • 직접 연결된 두 node 사이의 Count to infinity는 해결되지만, loop를 이룰 경우에는 해결 X

---

Link state vs Distance Vector

• 포워딩 테이블들이 stable한 상태에 들어가는 시간은 link state가 더 빠름
  • distance vector: 전체 라우팅 테이블을 보내야 함. 교환할 때마다 네트워크 내에 있는 모든 다른 node로의 최소 비용 정보를 서로 제공
  • link state: 바뀐 정보만 전달
• overhead는 distance vector가 더 적음
  • link state: 업데이트 정보를 전체 네트워크에 전달
  • distance vector: 자신의 이웃들에게만 전달
• distance vector는 라우팅 loop 발생
  • link state: 전체 네트워크 토폴로지를 알고 다익스트라를 수행하므로 라우팅 loop x
  • distance vector: poisoned reverse를 하더라도 loop 문제 발생
• 큰 네트워크에 대해 configuration 설정은 link state가 더 복잡

---