[컴퓨터네트워크] 04. 유니캐스트 라우팅(1) - Unicast Routing

유니캐스트 라우팅(Unicast Routing)(1)

---

Introduciton Routing

• 수없이 많은 호스트와 엄청 많은 라우터가 있는 인터넷에서의 라우팅은 계층적 라우팅으로만 가능
• 다양한 라우팅 알고리즘과 여러 단계의 라우팅 필요
• 인터넷의 라우팅 개념과 알고리즘을 이해하고, 어떻게 인터넷에 적용하는지를 고찰

일반적 개념

• 유니캐스트 라우팅에서, 출발지에서 도착지까지 포워딩 테이블을 참조하여 홉 단위로 라우팅 됨
• 출발지 호스트는 자신이 속한 네트워크의 디폴트 라우터에게 패킷을 전달하면 되므로 포워딩 테이블이 불필요
  • 호스트가, 여러 네트워크에 동시에 연결된 경우에는 필요
• 목적지 호스트도 자신이 속한 라우터로부터 패킷을 수신하므로 포워딩 테이블 불필요
  • 여러 네트워크에 동시에 연결된 경우에는, 응답 데이터를 보낼 때 필요
• 인터넷에 연결된 라우터에서 포워딩 테이블이 필요함

---

GPT

• 유니캐스트 라우팅이란 단일 송신자(sender)로부터 단일 수신자(receiver)로 데이터 패킷을 전달하는 방법입니다.
• 인터넷과 같은 대부분의 네트워크는 유니캐스트 라우팅을 기본으로 사용하며, 이것은 일반적으로 우리가 웹사이트에 접속하거나 이메일을 보낼 때 사용하는 라우팅 방식이다
• 각 패킷의 헤더에 있는 목적지 주소가 해당 패킷의 최종 목적지를 나타냅니다
• 대표적인 유니캐스트 라우팅 프로토콜
  • Static Routing: 수동으로 정의된 라우팅 경로를 사용하며, 네트워크 관리자가 라우터에 직접 라우팅 정보를 입력합니다.
  • Dynamic Routing: 라우터가 자동으로 네트워크의 상태를 감지하고 최적의 경로를 결정합니다. 라우팅 프로토콜은 네트워크 변화에 맞춰 동적으로 라우팅 테이블을 갱신합니다.
  • Distance Vector Routing Protocol (예: RIP): 각 라우터가 자신의 라우팅 테이블을 주기적으로 인접 라우터와 공유하여, 네트워크의 모든 경로에 대한 정보를 축적합니다.
  • Link State Routing Protocol (예: OSPF): 각 라우터가 네트워크의 상태를 정확히 파악하여 자신의 라우팅 테이블을 구축하고, 전체 네트워크의 맵을 유지합니다.
  • Path Vector Protocol (예: BGP): 인터넷에서 AS(자율 시스템) 간 라우팅에 사용되며, 경로 정보와 함께 목적지에 대한 경로를 전파합니다.

---

최소비용(Least-Cost) 라우팅

• 인터넷을 weighted graph로 표시하면, 출발 라우터로부터 도착 라우터로의 가장 좋은 경로는, 둘 사이의 최소 비용 경로
• 즉, 출발 라우터는 목적지로 향하는 여러 가능 경로 중에서 총 비용이 최소가 되는 경로를 선택

라우팅 알고리즘

• 과거 여러 라우팅 알고리즘이 고안됨
• 라우팅 알고리즘들의 차이점
  • 최소비용의 해석
  • 최소 비용 트리를 만드는 방법
• 이 섹션에서는 공통 알고리즘을 논의하고, 인터넷의 라우팅 프로토콜이 이들 중의 한 알고리즘을 어떻게 구현했는지 고찰

거리-벡터(Distance-Vector) 라우팅

• 거리-벡터 (DV)
  • 방향과 거리 값
• 최적의 경로 탐색
  • 각 노드는 자신의 이웃 정보를 통해 최소 비용 트리 생성 (단순, 불완전한 정보)
    • 루트(라우터)를 기준으로 트리 생성
  • 이 정보를 이웃 노드들과 교환하여 업데이트
• 거리-벡터 라우팅에서, 각 라우터는 계속 이웃 노드들에게 자신이 알고 있는 (미완) 정보를 끊임없이 교환

벨만-포드(Bellman-Ford) 공식

• 소스와 목적지 사이의 최소비용경로 찾는 식
• 소스 x, 목적지 y 사이의 최소비용
  • 중간 노드 a, b, c, ...
    • x->a->y, x->b->y, x->c->y .... 중 최소
• 업데이트
  • 새로운 경로의 중간 노드 z
    • x->z->y

두 노드의 불안정성

• Before failure
  • A 라우터 : A->X | 비용 : 1
  • B 라우터 : B->X | A를 거침 | 비용 : 2
• After link failure
  • A 라우터 : A->X | 비용 : 16(보통 16은 도달할 수 없음을 의미함)
  • B 라우터 : B->X | A를 거침 | 비용 : 2
  • 아직 라우터 B가 link failure를 모르는 상태
• After A is updated by B
  • A 라우터 : A->X | 비용 : 3
    • B 라우팅 테이블을 보고 B->X가 2니까, A->X : 3이라고 착각
• After B is updated by A
  • B 라우터 : A->X | 비용 ㅣ 4
    • A 라우팅 테이블을 보고 A->X가 3니까, A->X : 4이라고 착각
• Finally
  • 비용이 무한대가 됨
  • 비용이 16(무한대)가 될 때 까지 불완전한 긴 시간이 존재

링크-상태(Link-State) 라우팅

• Link-state
  • 링크 (에지, 라우터 간의 연결) 특성
• 저비용의 링크 선호
  • 무한대의 링크 비용 : 없거나 고장
• 최소비용트리를 만들려면 전체 네트워크의 지도가 필요
  • 모든 라우터의 링크 비용을 알아야 함
    • cf) 거리 벡터 : 주변 노드 정보
• Link-state database (LSDB)
  • 모든 링크 상태 집합

다익스트라 알고리즘

• LSDB로 부터 최소비용트리 생성
• 3가지 단계
  • 루트 노드 선정(라우터 자신). 루트 노드만 있는 트리로 시작
  • 아직 트리에 없고 연결된 노드를 선택하여 트리에 추가하고, 트리 내의 모든 노드까지의 비용을 업데이트
    • D[x] : 목적지 x 까지의 비용, W : 추가노드
    • D[x] = min {D[x], D[w] + c[w][x](전달받은 linkstate를 계산한 비용)}
  • 모든 노드가 포함될 때 까지 위 단계를 수행
• 최종적으로, 루트노드에서 모든 노드로의 최소비용트리가 생성됨

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

• 최소비용이 아닌 다른 정책(policy)를 적용하는 라우팅
  • ex) 특정 노드 제외 경로
• Best Spanning Tree 선정(policy 적용)
• ISP간의 패킷 경로를 위해 고안
• 거리 벡터 방식의 Bellman-fod 알고리즘과 비슷하지만, 최소비용이 아닌 정책을 반영
• 라우팅 테이블 내용은 경로벡터 [x, a, b, .... c, d, y]
  • Tx : x, Rx : y
  • 이웃 노드와 교환