라우팅 프로토콜

포워딩: 라우터의 입력으로 들어온 패킷을 어느 출력으로 보내는가 (=데이터 플래인)

라우팅: 출발지부터 목적지까지의 패킷의 루트 결정 (=컨트롤 플래인)

 

라우팅이란

라우터에 저장될 라우팅 테이블(포워딩 테이블)을 만드는 과정

 

기존 방식

각각의 라우터에서 알고리즘이 적용되어 경로가 정해짐

=> 논리적으로는 데이터 플래인과 컨트롤 플래인이 분리되어 있으나, 물리적으로는 같은 곳

 

최근 방식

상위 컨트롤러에서 정보를 받아서 경로를 결정하고 보내줌

=> 논리적으로도 물리적으로도 데이터 플래인과 컨트롤 플래인이 분리됨

---

기존 방식

Routing Protocol의 목적 - 보내는 쪽에서 받는 쪽으로 "좋은 경로"를 설정해야 함

여기서 좋다는 건 비용일 수도 있고, 혼잡도일수도 있고..

 

G = (N, E)

N = {u, v, w, x, y, z}

E = {(u, v), (u, x) ... }

그래프, 노드(라우터), 엣지(링크)

 

c(x, x*)라 하면 x->x*의 비용을 의미

여기서 비용을 뭐라 정하는지는 네트워크마다 다름

비용을 동일하게 하면 최단 홉을 찾으려 할 것

혹은 혼잡도나 거리일 수 있음

 

Static / Dynamic

Static Routing - 수동 라우팅

- 관리자가 경로 설정함 -- 느림

- 복잡한 소프트웨어 구현 불필요

- 소규모, 변화가 거의 없는 네트워크 환경

- 라우팅 트래픽에 의한 대역폭 소모 불필요

- 인터넷에서는 불가능

 

Dynamic Routing- 동적, 자동 라우팅

- 특정 조건 하에서 업데이트 (이웃 정보 변경, 혹은 주기적 ..)

 

Dynamic Routing의 종류

Global 방식

- 라우터는 전체 네트워크 구조(토폴로지)와 연결 비용을 앎

- 라우터는 자신이 속한 네트워크의 전체 라우터의 정보를 공유하게 됨

- Link State 알고리즘

 

Decentralized 방식

- 자신과 직접 연결된 라우터의 정보, 최종 목적지를 가기 위한 경로 비용, 다음 라우터 정보만 앎

- Distance Vector 알고리즘

 

링크 스테이트 라우팅 알고리즘

각 라우터는 전체 네트워크의 구성(토폴로지)과 링크 상태 정보를 유지

전체 네트워크 상태 정보를 이용하여 '모든' 목적지 최적 경로 계산, 라우팅 테이블 구성

 

LSA (Link State Advertisement) message

- 나와 직접 연결된 이웃 라우터의 정보

- 링크 상태 변화 시 라우팅 정보 교환

 

라우터는 LSA를 같은 네트워크(AS) 내의 모든 라우터에게 전함

각 라우터는 받은 LSA를 기초로 전체 네트워크 토폴로지 설정

최소 경로 계산 알고리즘: Dijkstra's algorithm (그리디 알고리즘)

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

하나의 노드에서 다른 모든 노드로의 최단 비용 계산

 

다익스트라 알고리즘을 썼을 때의 문제

- 링크 코스트를 트래픽의 양으로 설정한 경우

기본적으로 같은 타이밍에 알고리즘이 실행된다고 하고 네트워크 트래픽이 0에서 시작한다고 하자.

 

b->a로 가는데 e만큼의 코스트가 든다고 하면, 다음엔 다른 경로를 통해서 보내려고 할 것임

그런데 다른 경로에 보내면 해당 경로는 코스트가 늘고, 이전 b->a는 다시 코스트가 감소함

그럼 다시 b->a 경로로 보냄 --.... 계속해서 보내는 경로가 바뀌는 현상 발생

=> 모든 라우터들이 동시에 link state 알고리즘을 수행하지 못하도록 함

 

디스턴스 벡터 알고리즘

Bellman-Ford 알고리즘 (다이나믹 프로그래밍)

Dx(y) = min(c(x, v) + Dv(y))

비용을 이웃 라우터와의 거리 비용을 더해서 구함

각 라우터는 DV를 이웃에만 공유

각 라우터는 이웃한테 받은 DV를 근거로 자신의 DV 갱신

 

기본 상태	x	y	z
x	0	2	7
y	2	0	1
z	7	1	0

Dx(z) = min( c(x, y) + Dy(z), c(x, z) + Dz(z) )

           = min( 2 + 1, 7 + 0 ) = 3

 

디스턴스 벡터 알고리즘의 문제. count to infinity

링크의 코스트가 바뀐 경우 ..

각 노드는 이웃에 대한 정보만을 알고 있음

 

이웃이 아닌 노드의 연결 정보가 바뀐 건 알 수 없기 때문에

링크 코스트 증가 시 일방적인 정보 교환만 계속 일어날 수 있음

해결법: z가 y를 통해 x에 가려고 한다면, z는 x로 가는 코스트가 무한하다고 말하면 됨

---

자율 시스템(AS .. Autonomous System)

- 한 기관의 내부 네트워크

 

링크스테이트 라우팅

- AS내 모든 라우터는 각각 네트워크 구성도를 만듦

- 내 정보를 다른 라우터와 공유

- 각 라우터는 AS내의 다른 모든 라우터와의 최단 경로를 구함

- 네트워크에 상태 변화가 생기면 토폴로지 다시 구성

 

Flooding

변화가 생기면 새로운 토폴로지 구성을 위해 전체 네트워크에 자신의 상태 변화 통보

 

현재 OSPF(Open Shortest Path First) 가장 많이 사용 중

 

디스턴스 벡터 라우팅

- 두 이웃 노드 사이의 최소 비용 경로는 최소 거리로 간주

- RIP v1, v2, IGRP, EIGRP

- BGP는 비슷한 방법을 사용

- 각 라우터는 자신의 정보를 이웃하고 공유

- 주기적으로 정보를 업데이트

 

RIP 초기 버전은 cost를 라우터의 개수로 최적 경로로 설정

RIP는 30초, IGRP는 90초마다 DV 교환