[데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 8장 네트워크층: 패킷의 라우팅

8.1 개요

인터넷의 유니캐스트 라우팅은 수많은 라우터와 호스트를 효과적으로 연결하기 위해 계층적 라우팅을 사용

---

8.1.1 일반적인 아이디어

 

• 패킷 경로: 패킷은 출발지 호스트의 기본 라우터인 발신지 라우터(source router) 시작하여 목적지 호스트의 기본 라우터인 목적지 라우터(destination router)로 전달
• 라우터의 역할: 출발지 및 목적지 호스트는 포워딩 테이블이 필요 없으며, 인터넷 내 라우터만 포워딩 테이블을 유지하여 패킷 경로를 결정.
• 경로 선택 문제: 출발지와 목적지 사이의 여러 경로 중 가장 적합한 경로를 선택해야 합니다.

 

 

그래프로 표현한 인터넷

 

• 그래프(graph) 표현: 라우터는 노드(node)로, 라우터 간 네트워크는 선(edge)로 표현됩니다.
• 가중치 그래프(weighted graph): 선(edge)은 특정 비용(가중치)을 가지며, 이는 라우팅 프로토콜에 따라 다르게 해석됩니다(예: 거리, 대역폭 등).

 

---

8.1.2 최소-비용 라우팅

 

• 최소 비용(least cost) 경로: 출발지 라우터에서 목적지 라우터로 가는 경로 중 총 비용이 가장 낮은 경로를 선택

하나의 인터넷과 그래프로 표현한 인터넷

• 위 그림에서 A와 E 사이의 가장 최선의 경로는 비용 6을 가지는 A - B - E이다

 

최소-비용 트리

• 인터넷에 N개의 라우터가 있다면, 각 라우터에서 다른 라우터로 (N - 1)의 최소-비용 경로가 존재한다.
• 모든 인터넷에 대해 N * (N - 1) 최소-비용 경로가 필요하다는 의미이다.
  • 만약 인터넷에 10개의 라우터만이 존재한다면 90개의 최소-비용 경로가 존재한다.

---

 

8.2 라우팅 알고리즘

---

8.2.1 거리-벡터 라우팅

• 최선의 경로를 찾기 위해 일차원 배열을 이용해 거리-벡터를 생성

트리에 대응하는 거리-벡터

Bellman-Ford 방정식

• 라우터는 이 방정식을 통해 최소 비용 경로를 계산
• 새로운 최소 비용 경로를 생성하기 위해 기존 최소 비용 경로를 사용

• Dxy​: x에서 y로의 최소 비용

x - z - y 경로가 더 짧다면 위의 식처럼 방정식을 간소화

• Cxz: x에서 z까지의 비용
• Dzy​: z에서 y까지의 최소 비용

그래프로 표현한 벨만-포드 방정식

---

8.2.2 링크 - 상태  라우팅

• 인터넷에서 네트워크를 나타내는 링크(엣지)의 특성을 정의하기 위해 링크 상태를 사용한다.
• 더 낮은 비용을 가진 링크를 선호
• 링크의 비용이 무한대면 링크가 존재하지 않거나, 링크가 폐쇄되어 있음을 의미

링크-상태 데이터베이스

링크-상태 데이터베이스 예

• 모든 링크의 상태 집합을 링크-상태 데이터베이스(LSDB)라 부른다.

각 노드로부터 LSDB를 만들기 위해 만들고 전달되는 LSDB

• 플러딩(flooding)은 LSDB를 생성하기 위해 각 노드가 네트워크 전체의 링크 상태 정보를 공유하는 과정이다.
  1. LSP(Link-State Packet) 생성
     • 노드 정보와 링크의 비용 정보 조합을 LS패킷(LSP)라 한다.
  2. LSP 전파 (Flooding Mechanism)
  3. LSP 확산 종료
     • 새로 도착된 LSP가 기존의 것보다 오래되었다면 새로 받은 LSP를 차단
     • LSP가 더 새롭거나 처음 도착했다면, 노드는 기존 갖고 있던 오래된 LSP를 폐기
  4. LSDB 구축 및 최단 경로 계산
     • 최종적으로 위 그림처럼 작성한다.

거리-벡터 라우팅(Distance-Vector Routing)	링크-상태 라우팅(Link-State Routing)
각 라우터는 자신이 알고 있는 인터넷 전체의 정보를 이웃에게 전파함.	각 라우터는 자신이 알고 있는 이웃 정보를 네트워크 전체에 전파함.

 

 

---

8.2.3 경로 - 벡터 라우팅

• 경로-백터(PV, Path-Vector) 라우팅은 최소-비용 라우팅 기반 알고리즘이 아니기 때문에 LS나 DV 라우팅의 단점을 가지고 있지 않다.
  • 최소-비용 라우팅은 최소-비용 경로상에 특정 지역이 있을 때 패킷이 그 지역을 통과하지 못하도록 할 수 없다. 
• 최선의 경로는 발신자가 경로에 적용한 규칙을 사용하여 결정된다.
  ➡️ 발신자는 경로를 조절할 수 있다.

스패닝 트리

• 경로-벡터 라우팅에서 발신지에서 모든 목적지까지의 경로는 스패닝 트리(spanning tree)에 의해 결정된다.
• 목적지까지 하나 이상의 경로가 있다면, 발신자는 가장 최선의 규칙을 사용하는 경로를 선택할 수 있다.

경로-벡터 라우팅에서 스패닝 트리

 

스패닝 트리 생성

1. 초기 경로 벡터 생성
   • 네트워크에 노드가 부팅되면, 해당 노드는 자신의 이웃 노드에 대한 정보를 수집
     

     

     부팅 시간에 만들어지는 경로 벡터

2. 경로 벡터 교환 및 업데이트
   • 각 노드는 생성한 초기 경로 벡터를 자신의 모든 이웃 노드에게 전송
     
   • 이웃 노드는 받은 경로 벡터를 기반으로 자신의 경로 벡터를 업데이트
3. 루프 방지 조건 적용
   • 루프 방지를 위해 경로 내 자기 자신이 포함된 경우 해당 경로를 폐기한다.
     • 즉, Path(v, y)에 x가 포함되어 있으면, 해당 경로는 무시
     • 노드가 스스로를 다시 방문하지 않도록 하기 위함
4. 스패닝 트리의 점진적 구축

---

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

---

8.3.1 인터넷 구조

 

• 인터넷은 여러 개의 백본 네트워크가 상호 연결된 구조로 발전함.
• 백본 네트워크, 제공자 네트워크(ISP), 소비자 네트워크로 구성됨.

인터넷 구조

• 인터넷 라우팅은 자율 시스템(AS) 단위로 관리되며,
  • IGP (내부 게이트웨이 프로토콜): AS 내부 라우팅 (예: RIP, OSPF)
  • EGP (외부 게이트웨이 프로토콜): AS 간 라우팅 (예: BGP)

 

---

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

 

• 거리 벡터(distance-vector) 알고리즘 기반으로 동작하며, 작은 AS에서 사용됨.

 

홉 카운트

RIP에서 홉 카운트

• 홉 수(Hop Count) 기반 경로 비용 측정 (최대 15홉, 16은 무한대로 간주).

 

포워딩 테이블

포워딩 테이블

• 포워딩 테이블에는 목적지 네트워크, 다음 라우터, 비용 정보 저장
• 위 그림에서 R1은 N4로 가는 경로에서 다음 라우터를 R2로 정의
• R2는 N4로 가는 다음 라우터를 R3로 정의
• R3는 경로에 더 이상의 라우터가 없다고 정의

 

RIP 메시지 유형

• 요청(Request): 라우터가 부팅되거나 경로 정보가 만료될 때 전송.
• 응답(Response/Update):
  • 정기적(30초마다) 또는 변경 발생 시 전송하여 라우팅 테이블 업데이트.

 

RIP 알고리즘

• 전체 포워딩 테이블을 교환하며, 비용을 수정하고 최적의 경로 선택.
• 거리-벡터 라우팅 알고리즘과 동일한 알고리즘 사용

RIP를 사용하는 자율 시스템의 예

 

 

---

8.3.3 개방 최단 경로 우선(OSPF)

OSPF 메트릭(비용) 계산

• RIP과 달리, 홉 수뿐만 아니라 처리량, 지연시간, 신뢰성 등의 요소를 기반으로 비용(weight) 설정 가능.
• 서비스 유형(TOS) 에 따라 다른 비용을 적용할 수도 있음.

OSPF에서 메트릭

 

 

포워딩 테이블

OSPF에서 포워딩 테이블

• 다익스트라(Dijkstra) 알고리즘을 사용하여 최단 경로 트리를 생성한 후, 이를 바탕으로 포워딩 테이블 구성.
• RIP과의 차이점은 비용(metric) 계산 방식이며, 홉 수를 비용으로 설정하면 RIP과 동일한 결과가 나옴.

---

8.3.4 경계 게이트웨이 프로토콜 버전4 (BGP4)

• BGP는 외부 BGP(eBGP)와 내부 BGP(iBGP) 두 가지 변형이 존재.
  • eBGP(External BGP): 다른 자율 시스템(AS) 간 경로 정보를 교환하는 프로토콜
  • iBGP(Internal BGP): 동일한 AS 내의 라우터들 간 경로 정보를 공유하는 프로토콜
• 일반적인 네트워크에서는 경로 정보를 공유하기 위해 eBGP는 경계 라우터에서 실행되며, iBGP는 모든 라우터에서 실행된

 

eBGP의 동작

• BGP는 TCP 포트 179를 사용하여 라우터 간 세션(session)을 설정하고 경로 정보를 교환한다.
• eBGP는 직접 연결된 AS 간의 경로 정보를 교환하며, BGP 피어(BGP peers) 또는 BGP 스피커(BGP speakers)가 서로 정보를 교환한다.
• 업데이트 메시지를 통해 특정 네트워크 도달 가능성을 알리고, 이 정보를 기반으로 경로를 설정한다.

eBGP 동작

 

iBGP의 동작

• AS 내부의 모든 라우터가 iBGP를 실행하여 경로 정보를 공유해야 한다.
• 라우팅 루프 방지를 위해 풀 메쉬(Full Mesh) 구조를 가지며, n개의 라우터가 존재할 경우 n(n-1)/2개의 세션이 필요하다.
• iBGP는 직접적인 네트워크 연결 없이도 TCP 연결을 통한 논리적 경로 설정이 가능하다.

인터넷에서 eBGP와 iBGP의 조합

 

---

8.4 멀티캐스트 라우팅

---

8.4.1 유니캐스팅 (Unicasting)

• 하나의 송신자가 하나의 목적지로 데이터를 전송하는 방식.
• 각 라우터는 패킷을 특정 인터페이스를 통해 하나의 목적지로 전달.
• 네트워크 내부에서 패킷이 브로드캐스트될 수도 있지만, 최종적으로 지정된 단일 목적지에 도달.

유니캐스팅

 

---

8.4.2 멀티캐스팅 (Multicasting)

 

• 하나의 송신자가 다수의 목적지 그룹에 데이터를 전송.
• 수신자가 속한 그룹의 멀티캐스트 주소를 사용하여 데이터를 전송.
• 멀티캐스트 라우터는 패킷을 여러 인터페이스를 통해 복사 및 전송.

 

멀티캐스팅

 

---

8.5 IGMP

 

• 네트워크 계층에서 동작하는 프로토콜로, 그룹 멤버십 정보를 수집하는 역할 수행
• ICMP와 유사한 보조 프로토콜로, IGMP 메시지는 IP 데이터그램에 캡슐화됨

 

IGMP 동작