• 유니캐스트 라우팅은 계층적 라우팅 방식을 사용한다.
• 패킷은 포워딩 테이블을 참조하여 근원지에서 목적지까지 홉 단위로 전달된다.
• 근원지 호스트는 포워딩 테이블이 필요없다.(자신의 패킷을 로컬 네트워크의 기본 라우터에 전달) 라우터들만 알면 된다.
• 근원지 호스트의 기본라우터를 근원지 라우터(source router)라 한다.
• 목적지 호스트의 기본라우터를 목적지 라우터(destination router)라 한다.

그래프 표현

인터넷에서 최적 경로를 찾기 위해 그래프를 이용해 모델링했다. 라우터는 노드로, 라우터 사이의 네트워그를 선으로 표현한다. 각 선 사이에 비용을 연관지어 가중치 그래프를 이용해 모델링할 수 있다.

최소 비용 라우팅

가중치 그래프로 인터넷을 모델링할 때, 근원지 라우터부터 목적지 라우터까지의 최적 경로를 표현하는 방법 중 하나이다.

두 라우터 사이의 최소 비용(least cost)를 찾는 것이다.

위의 그림에서 A와 E의 최선의 경로는 A-B-E라는 것을 알 수 있다. 각 라우터는 최소 비용 경로를 찾아 라우팅해야한다.

최소 비용 트리

루트로부터 다른 모든 노드들을 최소 비용으로 방문하는 트리

N개의 라우터가 있다면 각 라우터는 자신만의 최소비용 트리를 가진다.

루트와 다른 노드 사이의 가장 짧은 경로를 구하기 위해 모든 다른 노드들을 방문하는 트리이다.

아래 그림은 위에 가중치 그래프에서 갖는 7개의 최소 비용 트리를 보여준다.

라우팅 알고리즘

과거에 여러 라우팅 알고리즘들이 설계되었다. 이 방법들의 차이점은 최소비용과 각 노드에서 최소 비용 트리를 만드는 방법을 표현하는 방식이다.

거리-벡터 라우팅(DV, distance-vector)

1. 각 노드의 인접한 노드들의 정보를 이용하여 최소 비용 트리를 구한다.
2. 불완전한 트리는 계속 완전한 트리가 되기위해 수정한다.
3. 각 라우터들은 자신이 가지고 있는 인터넷 정보가 불완전해도 정보들을 주위 라우터들에게 끊임없이 알려준다.

불완전한 트리를 완전한 트리로 바꾸기 위해 내부적으로 사용하는 개념들이 있다.

벨만-포드 방정식

거리 벡터 라우팅의 내부적으로 완전한 트리를 만들기 위해 사용되는 알고리즘이다.

간단하게 모든 경로 거리를 구해 최소값을 구하는 간단한 알고리즘이다.

거리 벡터

최소 비용 트리는 트리의 루트에서부터 모든 목적지까지의 최소 비용 경로 정보를 가지고 있다. 이 정보들을 일차원 배열로 저장한 것을 거리 벡터라고 한다.

각 라우터는 주변 노드와의 비용정보를 활용하여 거리 벡터를 생성한다.

• 처음 값을 모를 때는 무한대로 표시한다.

거리 벡터 갱신

불완전한 트리를 완전한 트리로 바꾸기 위해 거리 벡터를 계속 최저 비용으로 갱신해야한다.

1. 모든 노드가 벡터를 만든 후 인접한 노드와 벡터 정보를 교환
2. 이웃으로부터 벡터 정보를 수신한 노드는 벨만-포드 방정식을 이용하여 자신의 거리 벡터를 갱신 (최저 비용정보를 갱신)
3. 백터가 갱신되면 자신의 모든 이웃에게 전달
4. 전역적인 최소 비용을 찾을 수 있음

거리 벡터 라우팅의 단점

• 비용 감소와 같은 소식은 빨리 퍼지나 비용 증가와 같은 안좋은 소식은 갱신이 느리다.

   Route poisoning : 특정 네트워크가 사용불가일 경우 인접 라우터에게 무한대와 같은 높은 비용 값을 전달하여 다운 상태를 알린다.

• 링크가 고장 난 경우에 다른 모든 라우터가 이를 인식해야 하는데, 거리 벡터 라우팅에서는 시간이 많이 소요된다.

   무한대로의 카운트(count to infinity)라 불림.

무한대로의 카운트

이 문제가 발생하는 여러 예시가 있다.

• 두 노드의 불안정성(two-node instability)
  • 해결 방안 1 : 수평 분할(split horizon)
  • 해결 방안 2 : 포이즌 리버스(poison reverse)

• 세 노드의 불안정성

  • 세 노드 간에 불안정성이 발생하면 이 문제의 해결이 보장되지 않는다.

링크-상태 라우팅

인터넷에서 네트워크를 나타내는 링크의 특성을 결정하기 위해 링크 상태를 사용한다. 만약 도메인 내의 각 라우터가 도메인의 전체 상태를 알고 있다면 최소 비용의 라우팅 테이블을 만들 수 있다.

1. 각 노드에 의해 링크 상태 패킷(LSP: Link State Packet) 생성

   • 도메인의 토폴로지에 변화가 있는 경우

   • 주기적으로 생성 (1 – 2 시간)

2. 다른 모든 라우터에 LSP 전송: 플러딩(flooding)
   • 한 노드가 인접 노드로 부터 LSP를 받았을 때 이 LSP가 새것이면 이를 갱신하고 송신 노드를 제외한 각 인터페이스의 외부로 전송
3. 각 노드에서 최소 비용 트리 생성(Dijkstra 알고리즘 적용)
4. 최소 비용 트리를 기반으로 한 테이블 계산

링크-상태 데이터베이스

링크-상태 라우팅을 사용하여 최소 비용 트리를 작성하기 위해 각 노드는 각 링크의 상태를 알아야 하기 때문에 네트워크의 완전한 맵(map)이 필요하다. 그런 모든 인터넷에 대해 딱 하나만 존재하는 링크의 상태 집합을 링크-상태 데이터베이스(LSDB, Link-State DataBase)라 부른다.

다이크스트라(Dijkstra) 알고리즘

각 노드에서 최소 비용 트리를 생성하기 위한 알고리즘이다.

1. 자기 자신을 루트로 선택하고 각 노드의 전체 비용을 계산
2. 트리에 속하지 않은 모든 노드 중 루트와 가장 근접한 하나의 노드를 선택, 모든 트리 비용 계산
3. 트리에 모든 노드가 추가될 때 까지 2단계 반복

경로-벡터(PV, Path-Vector) 라우팅

링크-상태나 거리-벡터와는 다르게 최소 비용을 목표로 하는 것보다 발신자가 라우터에게 특정한 규칙을 적용시킬 수 있다.

배경

• 거리 벡터와 링크 상태 라우팅은 도메인 내부 라우팅에만 사용됨.
  • 확장성으로 인해 도메인 간 라우팅에는 대부분 부적합
• 거리 벡터 라우팅은 동작하는 도메인에 수 홉 이상이 존재하게 되면 불안정해질 수 있다.
• 링크 상태 라우팅은 라우팅 테이블을 계산하기 위해 아주 많은 양의 자원을 필요로 한다. 이는 또한 플러딩으로 인해 많은 트래픽을 유발할 수도 있다.
  • 거리와 링크 상태 뿐 아니라 특정 서비스를 위한 정책적인 제어가 필요함.

스패닝 트리

• 최소 비용 트리가 아니다.
• 스패닝 트리 고유 규칙을 적용해 발신지로부터 작성되는 트리
• 벨만-포드 방정식과 비슷하나 최소 비용이 아닌 고유 규칙을 이용한다.

Path(x, y) = best {Path(x, y), [(x + Path(v, y)]} for all v’s in the internet

유니캐스트 라우팅 프로토콜

자율 시스템(AS, Autonomous System)

하나의 단일 기관하에 있는 라우터와 네트워크 그룹

인터 도메인과 인트라 도메인 라우팅

현재 인터넷은 전세계적으로 매우 많이 확장되어 한 가지 라우팅 프로토콜로 모든 라우터의 라우팅 테이블을 갱신할 수 없다.

• 인터넷을 자율 시스템으로 나누어 관리함.
  • 도메인 내(intra-domain) 라우팅: 자율 시스템 내에서의 라우팅
  • 도메인 간(inter-domain) 라우팅: 자율 시스템 간의 라우팅

라우팅 정보 프로토콜(RIP)

라우팅 정보 프로토콜(RIP, Routing Information Protocol)은 AS 내에서 사용되는 내부 라우팅 프로토콜로서 거리-벡터 라우팅에 기초를 둔 단순한 프로토콜이다.

라우팅 테이블

• 목적지 네트워크 주소, Next router (주소), hop 수(거리 등으로 구성된다.
• 목적지는 네트워크
• 메트릭(비용)은 Hop counter (발신지 host는 계산하지 않음)
• 16 이 무한대, 15 hop을 넘을 수 없다.

RIP 메시지 포맷

OSPF(Open Shortest Path First)

• RIP와 같은 인트라 도메인 라우팅 프로토콜
• 링크-상태 라우팅 프로토콜 기반

메트릭(비용)

• RIP 처럼 호스트로부터 목적지까지 도달하는 비용은 근원지 라우터에서부터 목적지 네트워크까지로 계산된다.
• 관리자에 따라 각 링크는 처리량, 왕복시간, 신뢰성 등을 기반으로 가중치를 할당받을 수 있다.
• 라우터는 각각 다른 서비스 유형에 따라 다중의 라우팅 테이블을 가질 수 있다.

라우팅 테이블

• 이웃에 대한 정보 공유 : 지역(Area : AS를 나눈 단위) 안에서
• 모든 라우터와의 공유 : flooding
• 변경이 있을 때의 정보 공유 : 오직 변경이 발생할 때만

Area(지역)

• 모든 라우터에게 LSDB를 유지하기 위해 모든 AS에게 flooding

  큰 규모의 AS에서 많은 트래픽을 유발.

  AS를 area(지역)라고 불리는 작은 부분으로 나누게됨.

• Area border router : 지역에 관한 정보를 요약하고 그것들을 다른 지역으로 송신
• AS boundary router : 다른 자율 시스템에 관한 정보를 현재 시스템으로 분산

OSPF 라우팅

1. 지역(Area) : 하나의 자율 시스템을 여러 개의 지역으로 나눈다
2. 각 노드에 의해 링크 상태 패킷(LSP: Link State Packet) 생성
   1. 도메인의 토폴로지에 변화가 있는 경우
   2. 주기적으로 생성
3. 다른 모든 라우터에 LSP 전송: 플러딩(flooding)
4. 각 노드에서 최소 비용 트리 생성(Dijkstra 알고리즘 적용)
5. 최소 비용 트리를 기반으로 한 테이블 계산

BGP

BGP4(Border Gateway Protocol Version 4)는 현재 인터넷에서 사용하고 있는 유일한 인터도메인 라우팅 프로토콜이다.

• 경로-벡터 알고리즘 기반
  • 도메인 간 라우팅, 거리 벡터 라우팅의 원리와 비슷
  • 각 자율 시스템 (AS) 은 하나의 노드 (Speaker node)로 대표되며 이 speaker node만이 서로 통신이 가능
  • Speaker node는 AS의 메트릭을 통지하는 것이 아니라 경로(path)를 통지

BGP 세션

두 라우터간 라우팅 정보를 교환하는 것. 2가지 종류가 있다.

 - EBGP (External BGP) Session : 다른 AS 상호 간에 변방 라우터들끼리 접속  
 - IBGP (Internal BGP) Session : 동일 AS 내부의 변방 라우터들 간 내부접속 

eBGP(external BGP)

1. 경로 벡터 라우팅에 참여하는 AS 경계 라우터들은 이웃한 AS의 라우터들에게 자체 AS 내부의 네트워크 도달 여부(reach ability)를 광고(advertise) 한다.
2. 경로 벡터 메시지를 수신하는 각 라우터는 advertised 된 경로가 정책(경로들을 제어하는 관리자에 의해 부여되는 일련의 규칙)에 맞는지를 검사한 후 자신의 라우팅 테이블을 갱신하고 메시지를 수정하여 다음 이웃에게 전송한다.
3. 메시지의 수정은 경로에 자신의 AS 번호를 추가하고 자체의 식별자로 다음 라우터의 항목을 바꾼다.

문제점

• 이웃하지 않는 AS에게 전달될 패킷을 어떻게 전달할지 모른다.
• 경계 라우터가 아닌 라우터는 다른 AS의 네트워크로 전달될 패킷을 어떻게 전송해야 하는지 모른다.

iBGP(internal BGP)

• 동일 AS 내에 있는 2개 이상의 변방 라우터가 외부 AS와 연결된 상태에서 서로 간에는 Full-mesh 형태로 연결

BGP 메시지

BPG는 AS의 BGP speaker(node)와 AS 내부 사이의 통신을 위한 네 가지 종류의 메시지를 사용한다.

• Open : 동작 중인 라우터가 이웃관계를 생성하기 위해 보내는 메시지
• Update : 라우터가 전에 광고된 목적지를 취소하거나 새로운 목적지를 알리는데 사용
• Keepalive : 상대방에게 자신이 살아있음을 알리기위해 유지 시간이 만료되기 전에 정기적으로 메시지 교환
• Notification : 오류 상황이 감지되거나 연결을 닫기 원할 때 라우터에 의해 전송

김땡땡's blog

김땡땡