[Computer network] Chapter 4 - Network layer : Routing

1. Routing Algorithm

• Least-Cost Routing (최소 비용 라우팅) : 네트워크를 가중 그래프(Weighted graph)로 모델링하여 출발지 라우터에서 목적지 라우터까지의 최소 비용 경로를 찾는 방법. 이를 구현하기 위한 여러 알고리즘이 존재한다.

  • 네트워크의 그래프 표현

  • 최소 비용 찾기

• Least-Cost Routing Algorithms : 최소 비용을 달성하기 위한 라우팅 알고리즘은 크게 두 가지 종류로 나누어진다.

  • Distance Vector algorithm : 네트워크 전체 토폴로지 파악이 필요 없음

  • Link State Routing algorithm : 네트워크 전체 토폴로지 파악이 필요함

1-1. Distance-Vector Routing

• Distance-Vector Routing (DV) : 네트워크를 가중 그래프로 표현한 뒤, 이웃 노드와 정보 교환을 통해 최소 비용 경로를 찾는 알고리즘이다. 이 방식은 네트워크 전체 구조를 알지 못하더라도 동작한다.

  • The Key Idea : 각 노드는 주기적으로 자신의 DV 정보를 이웃 노드에 전달하고, DV를 받은 이웃 노드는 Bellman-Ford 방정식을 이용하여 자신의 DV를 업데이트한다.

    • Bellman-Ford 방정식 : 노드 $x$에서 노드 $y$까지 이동하는 데 필요한 최소 경로를 찾기 위해 사용되는 수식이다.

      $D_x(y) = min(c(x,v) + D_v(y))$

    • $c(x,v)$ : 노드 $x$에서 노드 $v$까지의 비용

    • $D_v(y)$ : 노드 $v$에서 노드 $y$까지의 비용

    • 출발지 노드(자기 자신)에서 목적지 노드까지 이동하는 데 발생하는 최소 비용을 계산하여 자신의 DV를 Update한다.

• 동작 예시

  1). 각 노드의 초기 DV

  • 각 노드는 자신과 이웃 노드까지의 초기 거리(경로 비용)만을 알고 있다.

  • 이웃하지 않은 노드와의 경로는 무한대로 설정되어 있다.

  2). Update DV : 노드 B가 이웃한 노드(A)와 DV를 교환하여 경로 비용을 Update한다.

  • B[D] = min(B[D], B[A] + A[D])

  • B[F] = min(B[F], B[E] + E[F])

• DV 알고리즘의 특징

  • 각 노드는 다음 프로세스를 따른다.

    • 로컬 링크 비용이 변경 또는 DV 업데이트 메시지 수신

    • DV 재계산

    • 자신의 DV가 업데이트 될 경우, 이웃 노드에게 메시지 전달

  • 반복적, 비동기적 : 링크의 비용이 변경되거나 이웃으로부터 DV 업데이트 메시지를 수신할 경우 알고리즘이 시작되므로, 반복적이며 비동기적이다.

  • 분산 방식 : 각 노드는 독립적으로 자신의 DV가 변경될 때 이웃에게 업데이트 메시지를 전달하는 방식이므로, 분산 방식이다.

• Two-Node Instability(불안정성) : DV 알고리즘의 불안정성을 살펴보자.

  • a : 두 노드 A, B가 존재하는 상황에서, A가 B에게 업데이트 메시지를 전송한다.

  • b : A와 X사이의 경로가 손실되었고, B는 A에게 Update 메시지를 전달한다.

  • c : 실제 A와 X사이의 경로 비용은 16이지만, 3으로 잘못 업데이트 된다. (A는 B를 통해 X로 갈 수 있다고 인식한다.)

  • d : A가 다시 B에게 업데이트 메시지를 전송한다.

  • 위 과정이 반복되며 결국 A,B 모두 X로의 경로 비용이 무한대로 발산한다.

X 노드로의 경로가 손실되었지만, A와 B는 서로를 통해 X에 도달할 수 있다고 판단하며 DV를 반복적으로 업데이트한다.

• Split Horizon Rule : 라우터는 업데이트 메시지를 받아온 인터페이스 방향으로 다시 업데이트 메시지를 보내지 않는다는 규칙이다. 이는 위와 같은 루프 문제를 방지하기 위한 규칙이다.

1-2. Link State Routing

• Link State Routing : 네트워크를 가중 그래프로 표현한 뒤, 링크의 상태를 고려하여 최소 비용 경로를 찾기 위한 알고리즘이다. 이 알고리즘은 네트워크 전체 구조를 알아야 정상적으로 동작할 수 있다.

  • 비용이 무한대로 표현되는 링크는 존재하지 않거나 비활성화된 상태이다.

• 동작 방식

  1). 각 노드는 자신과 연결된 이웃 노드와 링크 비용 정보를 교환하여 Link State Packet(LSP, 링크 상태 패킷)을 생성한다.

  2). 모든 노드가 자신이 생성한 LSP를 네트워크 내 모든 노드로 전파한다.

  3). 위 과정의 결과로 LSDB(Link State Data Base)가 생성된다.

• Dijkstra's Algorithm : 네트워크 토폴로지와 링크 비용 정보를 기반으로 최소 비용 경로를 계산하는 알고리즘이다.

  • 한 노드에서 모든 다른 노드까지의 최소 비용 경로를 계산한다.

  • 계산 결과로 포워딩 테이블을 생성한다.

  • Pseudo code

  
  c(x,v) : 노드 x에서 y까지의 링크 비용
  D(v) : 출발지에서 목적지 v까지의 경로 비용
  p(v) : 목적지 v까지의 경로에서 바로 이전 노드
  N : 최소 비용 경로가 확정된 노드 집합
  
  /* 초기화 단계 */
  Initialization :
    N = {u} // 출발지 노드가 u
    for all nodes v : // 모든 노드에 대해
      if v adjacent to u : // v가 u의 이웃이면
        then D(v) = c(u,v) // 경로 비용 설정
      else D(v) = infinite // v가 u의 이웃이 아니면 무한대로 초기화
   
   /* N 집합에 모든 노드가 포함될 때까지 loop */
   Loop :
     find w not in N such that D(w) is a minimum // N에 포함되지 않으면서 D(w)가 가장 작은 노드 w를 찾아서
       add w to N // N에 w를 추가
        /* w에 인접한 모든 노드 v에 대해 v가 아직 N에 포함되지 않은 경우 */
       update D(v) for all v adjacent to w and not in N :
         D(v) = min(D(v), D(w) + c(w,v)) // v로 가는 비용을 업데이트
   until all nodes in N

• Dijkstra's algorithm 동작 예시

  1). Step 0

  • N' 초기화 : 출발 노드 u가 포함된 집합 N' 초기화

  • D(v), D(w), D(x), D(y), D(z) : 노드 u에서 각 노드로의 초기 비용

  2). Step 1 ~ 5

  • 각 단계의 계산 결과에서 가장 낮은 비용을 가진 노드를 N'에 추가

  • 새로 추가된 노드와 이웃한 노드들의 비용을 업데이트

  • 최종적으로 N' = {u, w, x, y, z}가 되며, u에서 z까지의 최단 경로를 찾아냄.

• Dijkstra's algorithm 동작 예시 2

  • 다익스트라 알고리즘의 결과로 위와 같은 포워딩 테이블이 u에 형성되었다면, x를 default 라우터로 설정하여 forwarding table의 크기를 줄일 수 있다.

장점 : link state 변화에 따른 경로 update가 즉각적으로 이루어짐

단점 : Forwarding table size가 매우 커질 수 있음

1-3. Path-Vector Routing

• Path-Vector Routing (PV) : DV, LS는 모두 최소 비용 경로를 찾는 알고리즘이다. 네트워크 환경에 따라 여러가지 고려해야 할 사항이 있으므로, 최소 경로 비용이 항상 최적의 경로인 것은 아니다. 즉, PV는 정책 기반 라우팅을 지원하기 위한 알고리즘이다.

  • 통신 경로 상 외부 네트워크를 거쳐야할 때, 해당 네트워크를 사용하기 위해 적용되는 또다른 정책이 존재할 수 있다.

    • 외부 네트워크와 통신 : Policy least Path 찾기

    • 내부 네트워크의 통신 : Least cost Path 찾기

• 동작 방식

  • 각 노드는 자신과 이웃한 노드의 정보를 기반으로 초기 경로 벡터를 생성한다.

    • 경로 벡터는 도달할 수 있는 목적지와 해당 경로를 정의한다.

  • 경로 벡터 테이블을 구성

    • 각 노드는 자신의 경로 벡터를 다른 노드로 전달한다.

전체적으로 DV와 동작 과정이 비슷하지만, DV는 최소 비용 경로를 찾는 반면 PV는 최적 정책 경로를 찾는다.

2. Unicast Routing Protocols

위에서 소개된 라우팅 알고리즘을 사용하여 설계된 세 가지 라우팅 프로토콜에 대해서 배워보도록 하자.

2-1. Routing Information Protocol (RIP)

• Routing Information Protocol (RIP) : DV 알고리즘을 기반으로 동작하며, 오직 Hop count만을 사용하여 경로의 거리를 측정한다.

  • Hop count : 출발지에서 목적지까지 도달하기 위해 거쳐야하는 라우터의 수이다.

    • RIP는 Hop count가 가장 작은 경로를 선택한다.

  • Forwarding Table : RIP에서 사용하는 포워딩 테이블 구조는 다음과 같다.

  • Message Format

• 작동 예시

  • 초기 상태의 각 라우터는 포워딩 테이블에 자신과 연결된 네트워크에 대한 정보만 담고 있다.

  • 각 라우터는 인접 라우터로부터 메시지를 수신하고, 포워딩 테이블을 업데이트한다.

  • 위 과정이 반복되며, 최종적으로 각 라우터의 포워딩 테이블은 네트워크 전체에 대한 정보를 포함하게 된다.

2-2. Open Shortest Path First Protocol (OSFP)

• Open Shortest Path First (OSPF) : LS 알고리즘 기반으로 동작하는 프로토콜로, Link cost를 고려하여 경로를 선택한다. Open 프로토콜이기 때문에 모든 네트워크 장비 제조업체가 해당 프로토콜을 사용할 수 있다.

  • Link cost : 링크의 비용은 일반적으로 링크 대역폭에 반비례한다. 즉, 대역폭이 큰 링크가 비용이 적은 링크이다.

    • 출발지부터 목적지까지의 총 비용을 계산하여 라우팅을 결정한다.

  • Forwarding Table : 각 라우터는 다음과 같은 포워딩 테이블 구조를 갖는다.

    • 각 라우터는 다익스트라 알고리즘을 사용해 최단 경로를 계산한 후, 이를 포워딩 테이블에 저장한다.

  • Message Format

2-3. Border Gateway Protocol (BGP)

• Border Gateway Protocol (BGP) : 현재 인터넷에서 사용되는 유일한 도메인 간 라우팅 프로토콜이다. 즉, 외부 네트워크간 통신에 사용되는 프로토콜이며 PV 알고리즘을 기반으로 동작한다.

  • 각 네트워크는 AS로 구분되며, 고유한 AS 번호를 갖는다.

    • AS는 내부 라우팅 프로토콜(RIP, OSFP)와 외부 라우팅 프로토콜(BGP)를 사용하여 동작한다.

  • eBGP (External BGP) : 외부 AS 사이의 경로 정보를 교환하는 것을 eBGP라고 한다.

  • iBGP (Internal BGP) : 내부 AS 사이의 경로 정보를 교환하는 것을 iBGP라고 한다.

  • iBGP + eBGP

• 동작 예시

3. Quiz

• Question : 포워딩 테이블을 구성하는 방법은 무엇일까?

  • Answre

    • Intra Domain : Least Cost tree (OSPF, RIP)

    • Inter Domain : Policy based (BGP)