[네트워크] 네트워크 계층 (3) 라우팅 알고리즘 (RIP, OSPF, BGP)

라우팅

출발지에서 목적지까지의 최적 경로를 찾는 것

 

총 경로 비용 = 중간 단계에서 경유하는 링크(한 노드에서 근접한 노드까지의 연결)의 비용 합

 

$cost(x_1,x_2,...,x_p) = c(x_1,x_2) + c(x_2,x_3) + ... + c(x_{p-1},x_p)$

 

분류

Static vs Dynamic 방식

- Static

• 경로가 관리자 정책에 의해 고정되거나 수정됨

- Dynamic

• 실시간으로 최적 경로를 업데이트

Global vs Decentralized

- Global

• 모든 라우터는 완전한 네트워크 토폴리지를 알고 있으며 모든 링크 비용을 알고 있음
• ex) Link State Algorithm

- Decentralized

• 라우터는 자신과 근접한 라우터들의 정보만 알고 있음
• 최적 비용을 점근적으로 계산, 근접 라우터로 부터 비용관련 정보를 주고 받음.
• ex) Distance Vector Algorithm

Link State Algortihm	Distance Vector Algorithm
근접 라우터 정보가 변하거나 링크가 업/다운 되었을 때 혹은 주기를 가지고 LSA(Link State Advertisement) 메세지를 만든다. LSA는 네트워크 상의 모든 라우터에 브로드 캐스트 된다. 모든 라우터에서 수신된 LSA를 기반으로, 각 라우터는 완전한 네트워크 토폴로지를 만든다. 각 라우터는 다른 모든 라우터까지의 최적 경로를 다익스트라 알고리즘으로 계산한다. 이에 따른 목적지에 해당하는 포워딩 테이블을 구성한다.	각 라우터는 distance vector(다른 라우터로부터 얼마나 걸리는 지) 정보를 보유하고 있다. distance vector 정보를 근접 라우터와 지속적으로 교환한다. 라우터는 자신과 근접 라우터의 링크 비용과 근접 라우터의 distance vector를 가지고 최적 경로를 계산한다(벨만 포드).

Link State

• 네트워크 토폴로지와 모든 링크 비용을 알고 있음
• 라우터 자신으로부터 모든 다른 라우터까지의 최적경로를 계산

- 다익스트라 알고리즘

• 모든 경로 비용 무한대로 초기화
• 자신에 대한 경로 비용 0
• 큐는 모든 노드

--- 반복 시작 

1. 큐에서 최소 경로 비용을 가지는 노드 u를 꺼냄 (dist[u] < dist[others]) 

2. 주변 노드 v까지 가는 비용 dist[v]보다 노드 u를 거쳐갔을 때 비용 dist[u] + cost(u,v)가 더 작을 시 dist[v]를 업데이트

3. 노드 u까지의 최적 경로가 계산됨

4. 모든 노드에 대한 최적 경로가 계산될 때까지 반복

출처: https://www.researchgate.net/figure/The-pseudo-code-of-Dijkstras-algorithm-adapted-from-Wikipedia-2011_fig2_233025836

Distance Vector

• $d_x(y)$는 x에서 y까지의 경로의 최적 비용이라고 할 때,
• $d_x(y) =  min_v{c(x,v)+d_v(y)}, v \in neighbor(x)$로 계산된다.
• 따라서 노드 x에서 모든 노드 y에 대한 경로를 계산하기 위해서는 주변 노드에 대한 링크 비용 $c(x,v)$와 주변 노드에서 distance vector $d_v(y)$를 얻어야 최적 비용을 계산할 수 있다.

특징

• Bellman-Ford equation를 통한 최적경로 계산
• 지역적으로 한 노드에서 link cost$c(x,v)$가 변하거나 DV message를 수신하였을 때 최적 경로를 계산하고 
• 각 노드는 DV가 바뀔때마다 주변 노드에 DV 메세지를 전달한다.
• 전송 지연에 따른 시간 차이로 주변 노드로 부터 수신된 DV 메세지와 실제 주변 노드에서 DV 정보가 다를 경우 최적 경로를 계산하는데 시간이 오래걸리거나 주변 노드에서 수신된 DV 메세지간 충돌이 있을 수 있다.

계층적 라우팅 방법

네트워크를 자율성이 있는 시스템(AS) 단위로 나누고 효율적인 통신을 위해 AS 내부를 위한 intra-AS 라우팅 프로토콜과 AS 간 통신을 위한 inter-AS 라우팅 프로토콜을 사용한다.

• 같은 AS에 속한 라우터는 같은 라우팅 프로토콜(intra-AS)을 사용
• Gateway 라우터: 다른 AS로의 연결이 있는 라우터, inter-AS 프로토콜을 사용
• Intra-AS와 Inter-AS 라우팅 프로토콜에 의해 포워딩 테이블을 구성

Intra-AS 라우팅

- Routing Information Protocol (RIP)

• distance vector algorithm을 사용
• distance metric: 링크 cost를 1이라 할 때, 경유해야하는 홉(라우터)의 수
• 주기적으로 UDP 전송 프로토콜을 사용하여 주변 노드로 DV message를 advertise한다.

RIP 예시

RIP에 의해 라우터 D에서 포워딩 테이블이 업데이트된 예시

  1) 기존 z 목적지는 B 라우터를 거쳐 7의 비용이 듦

  2) A로부터 DV message를 수신, A는 C를 거쳐 4의 비용이 듦

  3) 기존 7보다 거리가 1인 A를 거쳤을 때 총 5(1+4)의 비용으로 갈 수 있음

  4) D의 포워딩 테이블에서 z에 대한 다음 홉과 최종 비용이 업데이트

 

- Open Shortest Path First (OSPF)

• link state algortihm을 사용
• 모든 라우터는 네트워크 토폴로지와 모든 라우터에 대한 최적 비용 정보를 가지고 있음
• 브로드 캐스트 advertisement를 통해 AS 내 모든 라우터에 LS 정보를 전송한다.
• 가장 흔한 intra-AS 라우팅 프로토콜

Inter-AS 라우팅

Border Gateway Protocol

- Border Gateway Protocol (BGP)

• 네트워크 AS들을 연결하는 역할
• eBGP: 목적지 서브넷 도달 정보를 주변 AS들로부터 얻음
• iBGP: AS 내부 라우터들에게 도달 정보를 전파

- BGP 기능: Distributing Path Information

• 경로 정보를 주변 AS에 전파하는 역할
• TCP 전송 프로토콜을 사용

경로 정보 전파 예시

  1) 3a와 1c 게이트웨이 라우터 사이에 eBGP를 이용하여 AS3는 서브넷 도달 정보를 AS1에 전송함

  2) 1c는 iBGP를 사용하여 도달 정보를 모든 AS1내부 라우터에 전파

  3) 1b는 다시 2a간 eBGP를 통해 새로운 도달 정보를 AS2에 전송할 수 있음 

 

- 경로 정보

• 경로 정보는 경로 출발지 네트워크 정보(Network Prefix)와 BGP 속성 정보를 포함

     "Routes" = Network Prefix + Attributes 

 

- BGP 속성 정보 (Attributes)

• AS-PATH: 어떤 AS를 경유해서 도착했는지, 기록 (ex, AS 1, AS 3:  3과 1을 경유함)
• NEXT-HOP:  네트워크 Prefix에서 출발한 경로가 거쳐야하는 첫번째 외부 AS와 연결된 Gateway 라우터
• 135.120.0.0/16 에서 출발하여 12.10.0.1 Gateway 라우터를 거친 경로 정보가 e-BGP로 주변 AS에 전파되고 각 AS에서 경로 정보를 수신한 라우터는 내부로 iBGP를 통해 경로 정보를 전파

출처: https://slideplayer.com/slide/10780892/

- BGP route selection

  1) Internet Sevice Provider마다 정해져 있는 경로 정책에 의해 결정

  2) 가장 짧은 AS-PATH

  3) 가장 가까운 NEXT-HOP

  4) 기타 다른 기준

 

- Intra-AS vs Inter-AS 라우팅의 차이

• 최적 경로 계산에 따른 라우터가 결정 / 관리자(IS)가 라우터 간 경로를 제어하는가
• 성능 우선순위 / 정의된 정책 우선순위

- 이미지 출처 및 참고자료 : wiki.ucalgary.ca/page/Courses/Computer_Science/CPSC_441.W2014/Chapter_4:_Network_Layer.html