라우팅 알고리즘

  • 라우팅 알고리즘의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것이다.
  • 그래프 : G(N, E)로 나타내고, N과 E는 각각 노드와 엣지의 집합이고, 하나의 엣지는 집합 N에 속하는 한 쌍의 노드로 표시된다.
  • 라우팅 알고리즘의 분류
    • 중앙 집중형 라우팅 알고리즘 : 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 핵식점인 특징은 알고리즘이 연결과 링크 비용에 대한 완전한 정보를 갖는다는 점이다. 전체 상태 정보를 갖는 알고리즘을 링크 상태(link-state) 알고리즘이라고 한다.
    • 분산 라우팅 알고리즘 : 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지는 않다. 대신 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다. 이후 반복된 계산과 이웃 노드와의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지의 최소 비용 경로를 계산한다. (예) 거리 벡터 알고리즘)

링크 상태(LS) 라우팅 알고리즘

  • 다익스트라 알고리즘 : 하나의 노드에서 네트워크 내 다른 모든 노드로의 최소 비용 경로를 계산한다. 네트워크 전체 정보를 이용한다.
  • D(v) : 알고리즘이 현재 반복 시점에서 출발지 노드부터 목적지 v까지의 최소 비용 경로의 비용
  • p(v) : 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드
  • N’ : 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있다면, v는 N’에 포함된다.

  • 출발지 노드 u를 위한 링크 상태(LS) 알고리즘 image-20231008-130643

  • 링크 상태 알고리즘 수행 결과 예시 image-20231008-131015

  • 최소 비용 경로와 포워딩 테이블 image-20231008-131108

거리 벡터(DV) 라우팅 알고리즘

  • 특징
    • 분산적 : 각 노드는 하나 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다.
    • 반복적 : 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다.
    • 비동기적 : 톱니바퀴 돌듯이 모든 노드가 서로 정확히 맞물려 통작할 필요가 없다.

  • DV 알고리즘에서 노드x부터 y까지 최소 비용 경로의 비용 image-20231008-131515

  • 거리 벡터(DV) 알고리즘
    image-20231008-135845

  • DV 알고리즘에서는 어떤 노드 x가 자신에게 직접 연결된 링크 중 하나의 비용이 변경된 사실을 알게 되거나 어떤 이웃으로부터 변경된 거리 벡터를 수신했을 때 자신의 거리 벳터 추정값을 갱신한다.
  • 거리벡터 알고리즘 동작 image-20231008-140035

링크 상태 알고리즘과 거리 벡터 라우팅 알고리즘의 비교

  • DV 알고리즘에서 각 노드는 오직 직접 연결된 이웃과만 메시지를 교환하지만, 자신으로부터 네트워크 내 모든 노드로의 최소 비용 추정값을 이웃들에게 제공한다. 반면 LS 알고리즘은 전체 정보를 필요로 한다.

인터넷에서의 AS 내부 라우팅 : OSPF

  • 네트워크를 여러 개의 자율 시스템(Autonomous System)으로 나누고 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용하는데 이러한 라우팅 알고리즘을 AS 내부 라우팅 프로토콜이라고 한다.
  • 개방형 최단 경로 우선(OSPF) 프로토콜
    • 링크 상태 정보를 플러딩 하고, 다익스트라 최소 비용 경로 알고리즘을 사용하는 링크 상태 알고리즘이다.
    • OSPF를 이용하여 각 라우터는 전체 AS에 대한 완벽한 토폴로지 지도(그래프)를 얻는다.
    • OSPF를 사용하는 라우터는 인접한 라우터만이 아니라 자율 시스템 내의 다른 모든 라우터에게 라우팅 정보를 브로드캐스팅한다.

인터넷 서비스 제공업자(ISP)간의 라우팅 : BGP

  • 목적지가 AS 외부에 있는 경우 BGP를 이용하여 전달된다.
  • BGP의 임무
    • 이웃 AS를 통해 도달 가능한 서브넷 프리픽스 정보를 얻는다.
    • 서브넷 주소 프리픽스로의 가장 좋은 경로를 결정한다.
  • BGP 경로
    • eBGP : 2개의 AS를 연결하는 BGP 연결
    • iBGP : 같은 AS 내의 라우터 간 BGP 연결
    • 도달 가능성 정보를 전파하기 위해서는 iBGP와 eBGP 연결이 모두 사용된다.
    • 특정 목적지까지 다른 많은 경로가 존재할 수 있고 각기 다른 일련의 AS들을 통과하기도 한다.
  • 최고의 경로 결정
    • 수많은 경로 중 라우터는 최선의 경로를 선택해야한다.
    • AS-PATH : 프리픽스가 어떤 AS에 전달되었을 때 그 AS는 자신의 AN은 AS-PATH 내 현재 리스트에 추가한다.
    • NECT-HOP : AS-PATH가 시작되는 라우터 인터페이스의 IP 주소이다.
  • 뜨거운 감자 라우팅
    • 라우터가 목적지까지의 경로 중 자신의 AS 바깥에 있는 부분에 대한 비용은 신경쓰지 않고 최대한 신속하게 패킷을 자신의 AS 밖으로 내보내는 것이다.
    • 비용은 신경쓰지 않고 자신의 AS 내부 비용만 줄이기 위해 당장의 최선의 다음 라우터를 선택한다.
  • BGP 경로 선택 알고리즘
    • 속성중 하나로서 지역 선호도가 경로에 할당 된다. 지역 선호도의 값은 온전히 AS 네트워크 관리자에 의한 정책이다. 최고 지역 선호 값을 가진 경로가 선택된다.
    • 최고 지역 선호값을 가진 경로가 여러 개 있다면 이들 중에서 최단 AS-PATH를 가진 경로가 선택된다. 여기서 거릿값으로는 라우터 홉 수 보다는 AS 홉 수를 사용한다.
    • 남은 경로들에 대해 뜨거운 감자 라우팅을 수행한다. 즉, NEXT-HOP 라우터까지의 거리가 가장 가까운 경로가 선택된다.
    • 아직도 하나 이상의 경로가 남아있다면 라우터는 BGP 식별자를 사용하여 경로를 선택한다.