IGP(RIP, OSPF), EGP(BGP)

1. Routing scalable

• AS (Autonomous System): 인터넷에서 라우팅을 관리하기 위해 하나 이상의 IP 네트워크들을 하나의 관리 영역으로 묶어 정의한 네트워크 그룹

  • 계층화된 구조를 사용하여 네트워크의 확장성을 유지하고 관리 가능한 규모로 유지
  • 각 AS는 자체적으로 라우팅과 관리를 수행하고, 이러한 계층화된 구조를 통해 네트워크를 효과적으로 구성할 수 있다.
    

• Intra-AS: 동일한 Autonomous System (AS) 내의 라우터 간의 라우팅을 관리

• Inter-AS: 서로 다른 AS 간의 라우팅을 관리
  → Gateway: 다른 AS의 gateway 라우터와 Inter-AS 라우팅을 수행하는 장치

• 라우팅 테이블: Infra-AS & Inter-AS를 모두 참고하여 만든다.
  

---

2. Intra-AS (IGP ,Internal Gateway Routing Protocol)

1. RIP (Routing Information Protocol)

• Distance vector 알고리즘 기반: 각 노드가 자신에게 직접 연결된 이웃의 링크 비용만을 알고 있으며, 이웃 라우터 간에 주기적으로 정보를 교환하여 (목적지까지의 홉 수 등) 최적의 경로를 업데이트
  → 벨만-포드 알고리즘을 사용하여 경로를 계산
  

• 과정

  1. 주기적으로 각 노드는 이웃 노드에게 자신의 라우팅 테이블 정보를 전달하고 이웃 노드로부터 정보를 수신 (30초)
     • 각 노드는 자신과 직접 연결된 이웃 노드의 링크 비용 정보를 알고 있음
     • 120초 동안 정보를 받지 못하면 경로 단절로 판단
  2. 노드는 받은 정보를 기반으로 벨만-포드 알고리즘을 사용하여 자신의 라우팅 테이블로 갱신
  3. 갱신된 라우팅 테이블을 사용하여 데이터 패킷을 최적 경로로 전달

• 장점

  • 간단한 구현
  • 분산된 환경에서 동작할 수 있으며, 이웃 노드 간의 정보 교환을 통해 라우팅 테이블을 갱신
    → 소규모 네트워크에 효과적

• 단점

  • Slow convergence: 정보 교환과 라우팅 테이블의 업데이트를 반복해야 하므로 라우팅 테이블이 최적의 상태로 수렴하는 데 시간이 오래 걸릴 수 있다.
  • Bad news travels slow - Count-to-Infinity: 링크 비용이 증가하거나 경로가 끊긴 경우, 해당 정보가 라우터 간에 느리게 전파되는 현상으로 Route loop이 발생할 수 있다.
    • 무한대 홉 수로 16을 사용
    • split horizon: 자신이 얻은 경로 정보를 그 경로로 다시 전송하지 않는 기법
    • poison-reverse: 끊어진 경로 정보를 인접 라우터에게 알리는 메시지를 보내어 라우팅 테이블의 업데이트를 촉진하는 방법
    • triggered update: 네트워크 변경이 발생하면 즉시 인접 라우터에게 업데이트를 전송하여 정보를 빠르게 퍼뜨리는 방법

2. OSPF (Open Shortest Path First)

• Link-state 라우팅 알고리즘 기반: 라우터 간에 OSPF 메시지를 교환하여 네트워크의 링크 상태 정보를 업데이트하고 유지함으로써 네트워크의 완전한 토폴로지 맵을 구축

  • 각 라우터는 AS 내부의 다른 모든 라우터에게 link state 정보를 전달
  • 각 라우터는 받은 link state 정보를 사용하여 전체 네트워크의 topology를 구축
  • Hierarchical OSPF: OSPF 네트워크를 더 작은 영역으로 나누어 관리하기 위해서 local area, backbone 개념을 도입했다.
    
    • Area border router: 로컬 영역과 백본 영역 사이에 위치한 라우터로 로컬 영역과 백본 영역 사이의 중계 역할을 하며, 자신이 속한 로컬 영역의 정보를 백본 영역의 다른 라우터에게 알린다.
    • Backbone router: backbone 영역에 있는 라우터로, Area border router와 연결되어 있다.
    • Boundary router: 다른 AS와 라우팅 정보를 교환

• 과정

  1. Hello 프로토콜: 라우터는 Hello 패킷을 사용하여 이웃 관계를 설정
  2. Database Description 정보 전달: 이웃 라우터 간에 Database Description 정보를 전송
     → 링크 상태 요약 정보를 포함
  3. Link State Request (LSR): 링크 상태 요청
     → 더 자세한 정보를 위해 이웃 라우터로부터 특정 링크 상태 정보를 요청
  4. Link State Update (LSU): 링크 상태 변경된 경로 정보를 전송
     → LSA(Link State Advertisement): 링크 상태 광고 기법
  5. LSU 응답 ACK: LSU에 대한 응답으로 ACK를 전송하여 확인

• 장점

  • OSPF는 RIP와 달리 링크 비용의 개념을 도입하며, 다양한 변수를 고려하여 최적 경로를 계산
  • OSPF는 대규모 네트워크에서 효과적으로 동작하며, link-state 알고리즘을 사용하므로 네트워크의 정확한 topology 정보를 유지하고 최적 경로를 계산한다.
    → 높은 확장성과 성능
  • 다익스트라 알고리즘을 기반으로 최단 경로를 계산하고 패킷을 전달

---

3. Inter-AS (EGP, Exterior Gateway Routing Protocol)

1. BGP (Border Gateway Protocol)

• 대규모 네트워크에서 AS 간의 경로 선택과 라우팅 정보 교환을 관리하는 데 사용되는 프로토콜
  

• BGP 라우터 간에는 특정 목적지로 가는 경로 정보를 공유하기 위해 BGP 메시지를 교환

  • 목적지 네트워크 프리픽스(destination network prefix): 목적지의 IP 주소 범위
  • AS-PATH: 목적지까지 도달하기 위해 거쳐야 하는 Autonomous System (AS)의 경로
  • NEXT-HOP: 목적지로 향하는 다음 라우터의 IP 주소

• Policy-based routing: Gateway 라우터들은 내부 정책을 통해 해당 경로를 Accept or Decline 여부를 선택한다.
  → AS 1은 AS 3, AS 2로부터 받은 정보 중 내부 정책에 따라 한 가지 경로를 선택한다.

---

4. Hot potato routing

• 데이터를 가능한 빨리 네트워크에서 나가도록 하는 전략

  • 2d 라우터는 intra-AS 비용이 가장 작은 2a로 경로를 선택한다.
    → 2c 경로를 선택하면 더 효율적일 수 있지만, 내부 비용이 가장작은 (가장 빨리 내보내야 하므로) 경로를 선택하므로 2a가 선택된다.