[컴퓨터 네트워크] 9장 - 네트워크층 패킷의 라우팅

성원·2026년 5월 31일

컴퓨터네트워크

목록 보기

7/9

[컴퓨터 네트워크] 9장 - 네트워크층 패킷의 라우팅

9.1 라우팅 개요 및 알고리즘 분류

라우팅(Routing)은 송신지 네트워크 호스트에서 수신지 호스트까지 패킷이 이동할 최적의 경로를 결정하는 분산 알고리즘 매커니즘이다. 라우팅 알고리즘의 연산 결과물이 포워딩의 기준이 되는 자료구조인 라우팅 테이블(Routing Table)이 된다. 네트워크 토폴로지는 노드(라우터)와 엣지(링크 및 비용)를 가진 그래프 $G = (V, E)$ 로 표현된다.

9.1.1 정보 관리 범위에 따른 분류

글로벌 라우팅 알고리즘 (링크 상태 알고리즘): 모든 라우터가 네트워크의 완전한 토폴로지와 각 링크의 비용(Cost) 정보를 동시에 확보한 상태에서 연산을 수행한다. 전체 노드가 동일한 전체 맵을 기반으로 경로를 계산하며, 대표적으로 다익스트라(Dijkstra) 알고리즘이 이에 속한다.
분산 라우팅 알고리즘 (거리 벡터 알고리즘): 각 라우터가 자신과 물리적으로 직접 연결된 이웃 라우터의 정보만을 교환하며, 반복적인 연산을 통해 점진적으로 최적 경로를 수렴해 나간다. 독립적으로 계산을 수행하며, 대표적으로 벨만-포드(Bellman-Ford) 알고리즘이 이에 속한다.

9.2 라우팅 알고리즘 상세 (Dijkstra vs Bellman-Ford)

9.2.1 링크 상태(Link State) 라우팅: 다익스트라 알고리즘

중앙 집중식 구조로, 모든 노드가 전체 토폴로지 맵을 공유하기 위해 링크 상태 패킷(LSP: Link State Packet)을 전체 네트워크에 플러딩(Flooding)한다. 이를 통해 모든 라우터는 완벽하게 일치하는 네트워크 지도(맵)를 동기화하여 보유하게 된다.

동작 원리: 특정 시작 노드로부터 다른 모든 노드까지의 최단 경로를 반복적으로 탐색하여 최단 경로가 완벽히 확정된 노드들의 집합인 확정 집합( $N'$ )을 한 단계씩 넓혀간다.
연산 매커니즘:
- $D(v)$ : 시작 노드로부터 목적지 노드 $v$ 까지의 현재 최단 경로 비용
- $p(v)$ : 최단 경로 상에서 노드 $v$ 의 바로 직전 노드(부모 노드)
- $c(u,v)$ : 노드 $u$ 와 $v$ 간의 직접적인 링크 비용 (연결되지 않은 이종 노드 간의 경우는 $\infty$ )
반복 수식: 확정 집합 $N'$ 에 속하지 않은 노드 중 $D(v)$ 가 최소인 노드 $w$ 를 선택하여 집합에 추가하고, $w$ 와 인접한 모든 이웃 노드들의 비용을 아래 수식으로 비교 및 갱신(Relaxation)한다.
$D(v) = \min(D(v), D(w) + c(w,v))$

9.2.2 거리 벡터(Distance Vector) 라우팅: 벨만-포드 알고리즘

분산형 및 반복형 구조로, 각 노드는 네트워크 전체 지도를 그리지 않는 대신 자신의 이웃 노드들과만 거리 벡터(Distance Vector) 정보를 주기적으로 비동기 교환한다.

동작 원리: 목적지까지 가는 최단 경로를 구하기 위해 벨만-포드 방정식(Bellman-Ford Equation)을 기반으로 자신의 테이블을 지속적으로 갱신한다. 이웃 라우터가 보낸 거리 벡터 값이 변경되거나 링크 비용이 변할 때만 국소적 갱신 연산이 트리거된다.
수식 구조: 노드 $x$ 에서 목적지 $y$ 까지 가는 최단 경로 비용 $d_x(y)$ 는 다음과 같이 정의된다.
$d_x(y) = \min_{v} \{ c(x,v) + d_v(y) \}$
(여기서 $v$ 는 노드 $x$ 와 물리적으로 직접 연결된 모든 이웃 라우터들을 의미한다.)

거리 벡터의 한계점과 해결책

Count-to-Infinity (무한대 수렴 문제): 네트워크 상에서 특정 링크의 비용이 감소하는 좋은 소식(Good News)은 전 네트워크에 즉시 반영되지만, 링크가 완전히 단절되거나 비용이 대폭 증가하는 나쁜 소식(Bad News)은 라우터 간의 잘못된 경로 정보가 서로 메아리처럼 순환 참조되면서 비용이 무한대로 커질 때까지 수렴하지 않고 패킷 루프를 유발하는 현상이 발생한다.
포이즌 리버스 (Poison Reverse / Split Horizon): 무한 루프 문제를 완화하기 위한 경로 광고 제어 기술이다. 만약 노드 $Z$ 가 노드 $Y$ 를 거쳐서 목적지 $X$ 로 가고 있다면, $Z$ 는 $Y$ 에게 목적지 $X$ 까지의 거리 정보를 보낼 때 의도적으로 값을 무한대( $\infty$ )로 속여서 전달한다 ( $d_Z(X) = \infty$ ). 이를 통해 $Y$ 가 $Z$ 의 정보를 신뢰하여 $Z$ 를 거쳐 다시 $X$ 로 가는 잘못된 경로 루프(양방향 경로 루프)를 형성하는 것을 사전에 완전히 차단한다.

9.3 자율 시스템(AS)과 라우팅 프로토콜

인터넷은 전 세계 모든 라우터를 단 하나의 알고리즘과 거대 테이블로 제어할 수 없기 때문에, 단일 관리 도메인 및 동일한 라우팅 정책 체제 하에 묶인 라우터 집합인 자율 시스템(AS: Autonomous System) 단위로 계층화하여 운영한다.

내부 라우팅 프로토콜 (IGP: Interior Gateway Protocol): 동일한 자율 시스템(AS) 내부의 라우터들끼리 경로 정보를 교환하기 위해 사용하는 프로토콜이다. 단일 관리 도메인 내부이므로 메트릭 최적화에 중점을 둔다. (예: RIP, OSPF)
외부 라우팅 프로토콜 (EGP: Exterior Gateway Protocol): 서로 다른 독립된 AS 간의 도메인 연결 및 패킷 중계를 위해 사용하는 프로토콜이다. (예: BGP)

9.3.1 RIP (Routing Information Protocol)

기반 알고리즘: 거리 벡터(Distance Vector) 알고리즘 기반
경로 결정 메트릭: 홉 카운트(Hop Count)만을 유일한 경로 비용 기준으로 삼는다. 패킷이 통과하는 라우터의 개수만 단순 계산하기 때문에 링크의 실제 대역폭이나 속도, 전송 지연을 전혀 반영하지 못하는 한계가 있다.
네트워크 크기 제한: 최대 홉 카운트는 15로 제한된다. 홉 카운트 16은 도달 불가능(Unreachable)한 유효하지 않은 경로를 의미하므로 대규모 백본 네트워크에는 적용이 전면 불가능하다.
주기적 업데이트: 라우터들은 매 30초마다 자신의 전체 라우팅 테이블 내용을 이웃 라우터에게 UDP 포트 520번을 통해 브로드캐스트 또는 멀티캐스트 방식으로 전송한다. 만약 180초 동안 특정 경로에 대한 업데이트가 없으면 해당 경로는 무효화되며, 추가로 120초(Garbage Collection)가 지나면 테이블에서 완전히 삭제된다.

9.3.2 OSPF (Open Shortest Path First)

기반 알고리즘: 링크 상태(Link State) 알고리즘 기반 (Dijkstra 알고리즘 사용)
경로 결정 메트릭: 링크의 표준 대역폭을 기반으로 계산되는 비용(Cost)을 메트릭으로 사용한다. 수식은 다음과 같으며 속도가 빠른 고대역폭 링크일수록 메트릭 값이 작아져 최적 경로로 선택된다.
$\text{Cost} = \frac{10^8}{\text{Bandwidth (bps)}}$
계층적 라우팅 지원: 자율 시스템을 내부적으로 다시 여러 개의 Backbone Area (Area 0)와 이와 직접 연결되는 일반 Area로 쪼개어 관리할 수 있다. 이 구조는 링크 상태 패킷(LSP)의 플러딩 범위를 특정 영역 내부로 국한시켜 대규모 네트워크 환경에서도 전체 토폴로지 변경에 따른 트래픽 과부하 없이 안정적으로 동작하도록 돕는다.
보안 및 전송 특성: 라우팅 정보 교환 시 해시 기반 인증(Authentication) 매커니즘을 지원하며, TCP/UDP 상위 프로토콜을 거치지 않고 IP 페이로드 상에 프로토콜 번호 89번을 달고 직접 인캡슐화되어 전송된다. 멀티캐스트 주소(224.0.0.5, 224.0.0.6)를 사용하여 효율적으로 동기화한다.

9.3.3 BGP (Border Router Protocol)

기반 알고리즘: 경로 벡터(Path Vector) 알고리즘 기반
핵심 특성: 단순한 링크 비용이나 홉 카운트 계산을 넘어, 각 AS 관리자가 독립적으로 설정한 국가 간 조약, 비용 정책, 특정 국가 및 기관 장비 경유 금지 등의 정치적/경제적 정책(Policy-based Routing)을 기준으로 최적의 도메인 간 경로를 결정한다. 라우팅 정보 교환의 신뢰성을 위해 L4 TCP 프로토콜의 179번 포트를 사용하여 피어 간 반영구적인 세션을 유지한다.
루프 방지 매커니즘: BGP 라우팅 정보 전송 시, 해당 경로 패킷이 거쳐온 자율 시스템 번호의 진행 리스트인 AS-PATH 속성을 헤더 명세에 담아 보낸다. 만약 수신한 AS-PATH 목록에 자신의 AS 번호가 이미 포함되어 있다면 루프가 발생한 것으로 판단하고 해당 라우팅 경로 정보를 즉시 폐기한다.
세부 연결 구조:
- eBGP (External BGP): 서로 물리적으로 직접 연결된 다른 AS의 경계 라우터(Border Router) 간에 BGP 경로 정보를 교환하는 세션이다.
- iBGP (Internal BGP): 동일한 AS 내부의 라우터들끼리 AS 외부에 대한 라우팅 주소 정보를 공유하고 동기화하기 위해 내부에서 맺는 BGP 세션이다.

9.4 멀티캐스트 라우팅 (Multicast Routing)

단일 송신자가 네트워크 상의 지정된 특정 그룹 수신자들(1-to-Many)에게 동시에 패킷을 한 번만 전송하여 대역폭 효율을 극대화하는 기술이다. 수신 호스트들은 멀티캐스트 IP 주소 클래스 D 대역( $224.0.0.0 \sim 239.255.255.255$ )을 목적지 주소로 활용한다.

9.4.1 최적 트리 구축 매커니즘

멀티캐스트 패킷이 중복 복제되어 루프를 도는 것을 막고 모든 그룹 멤버에게 최소 경로로 도달하기 위해 그래프 상에 가상 트리를 형성한다.

RPF (Reverse Path Forwarding): 멀티캐스트 패킷의 무한 루프를 방지하는 근본 검증 기술이다. 라우터가 멀티캐스트 패킷을 수신하면 패킷의 목적지가 아닌 출발지 IP 주소를 역으로 확인한다. 만약 패킷이 들어온 입력 인터페이스가 유니캐스트 라우팅 테이블 상에서 해당 출발지 소스까지 가기 위해 사용하는 출력 인터페이스와 정확히 일치할 경우에만 정상 패킷으로 인정하여 포워딩(복제 및 전송)하고, 인터페이스가 일치하지 않으면 소스가 조작되었거나 루프된 패킷으로 판단하여 즉시 폐기(Drop)한다.

송신자 기반 트리 (Source-Based Tree): 각 멀티캐스트 송신자(Source) 노드를 트리의 루트(Root)로 삼아 개별적으로 최단 경로 트리(SPT: Shortest Path Tree)를 형성하는 방식이다. 대표적인 프로토콜로 DVMRP, MOSPF가 있으며, 밀집 모드인 PIM-DM에서 활용된다. 라우터는 그룹당 소스별로 정보를 따로 관리해야 하므로 각 소스마다 독립적인 $(S, G)$ 상태 정보를 유지한다.
공유 트리 (Shared Tree): 네트워크 내부에 랑데부 포인트(RP: Rendezvous Point) 혹은 코어(Core)라고 불리는 공용 중심 라우터를 하나 지정해 두고, 모든 송신자와 수신자가 이 RP를 중심으로 하나의 거대한 트리를 공유하여 통신하는 구조이다. 소스 개수와 관계없이 그룹별로 단 하나의 트리만 관리하면 되므로 라우터의 메모리 부담이 적다. 수신 단말이 적고 넓은 영역에 분산된 환경(Sparse Mode)에 적합하며 PIM-SM에서 이 방식을 채택한다. 상태 정보는 소스에 관계없이 $(*, G)$ 로 표기한다.

9.5 그룹 멤버십 관리 프로토콜: IGMP

IGMP(Internet Group Management Protocol)는 호스트와 로컬 라우터 간에 동작하며, 호스트가 어떤 멀티캐스트 그룹에 가입(Join)하거나 탈퇴(Leave)하려는지 서브넷 내부의 로컬 라우터에게 알려 브로드캐스트 도메인 내부의 그룹 멤버십 리스트를 동적으로 관리하는 프로토콜이다.

9.5.1 IGMP 버전별 특징 및 개선점

IGMPv1: 가장 기본적인 구조로, 라우터가 그룹 가입 여부를 주기적으로 묻는 General Query를 전송하면 호스트가 가입 보고서(Membership Report)를 전송한다. 명시적인 탈퇴 메시지가 헤더 구조에 없기 때문에 호스트가 말없이 세션을 종료하면 라우터는 타임아웃이 발생할 때까지 불필요한 멀티캐스트 트래픽을 세그먼트에 계속 전송하는 대역폭 낭비가 생긴다.
IGMPv2: 명시적 그룹 탈퇴(Leave Group) 메시지가 신설되었다. 호스트가 그룹을 나갈 때 탈퇴 메시지를 보내면 라우터는 해당 링크에 그룹의 다른 수신자가 남아 있는지 최종 확인하기 위해 특정 그룹 전용 질의인 Group-Specific Query를 전송한다. 호스트는 Max Response Time 필드값 이내에 응답해야 하며, 이를 통해 자원 회수 대기 시간을 대폭 단축한다. 또한, 동일 서브넷 내에 여러 라우터가 존재할 때 쿼리를 총괄할 하나의 라우터만 남기는 Querier 선출 매커니즘이 추가되었다.
IGMPv3 (송신자 필터링 지원): 멀티캐스트 소스 기반 필터링 기능이 도입되어, 호스트가 특정 그룹 가입 시 "특정 송신자 $S$ 가 보내는 멀티캐스트 트래픽만 받겠다(INCLUDE)" 혹은 "특정 송신자 $S$ 가 보내는 트래픽만 제외하고 다 받겠다(EXCLUDE)"를 리포트에 명시할 수 있다. 이를 통해 원치 않는 트래픽 유입을 물리적으로 사전 차단하여 대역폭 보안 및 라우터 자원 절약을 달성하고 SSM(Source-Specific Multicast) 환경을 완벽하게 지원한다.

스스로 확인해보기

[ 라우팅 알고리즘 및 프로토콜 ]

Q1. 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford) 알고리즘의 최적 경로 연산 범위 및 정보 교환 대상의 차이점을 기술하시오.

모범 답안: 다익스트라는 글로벌 링크 상태 알고리즘으로 모든 라우터가 플러딩을 통해 네트워크 전체 토폴로지 정보를 공유한 상태에서 최단 경로를 연산한다. 반면 벨만-포드는 분산형 거리 벡터 알고리즘으로 전체 토폴로지 맵 없이 물리적으로 인접한 이웃 라우터들과만 주기적으로 거리 벡터 정보를 교환하며 점진적으로 수렴한다.

Q2. 거리 벡터 라우팅에서 발생하는 'Count-to-Infinity' 장애 현상의 원인과 이를 완화하기 위한 '포이즌 리버스(Poison Reverse)'의 동작 원리를 서술하시오.

모범 답안: 나쁜 경로 비용 정보가 라우터 간에 순환 참조되면서 무한대로 커지는 현상이다. 포이즌 리버스는 노드 $Z$ 가 목적지 $X$ 로 가기 위해 이웃 노드 $Y$ 를 경유 경로로 선택한 경우, $Z$ 가 $Y$ 에게 경로 정보를 광고할 때 의도적으로 최단 거리 비용을 무한대( $\infty$ )로 선언하여 $Y$ 가 자신을 역참조하는 루프를 차단한다.

Q3. OSPF 프로토콜이 대규모 엔터프라이즈 네트워크 환경에서 라우팅 트래픽 폭증 문제를 해결하기 위해 지원하는 계층 구조의 명칭과 동작 상의 이점을 서술하시오.

모범 답안: 자율 시스템을 계층적 영역인 Area 단위로 분할하여 운영한다. 최상위 백본 영역(Area 0)과 일반 영역을 분리함으로써, 링크 상태 패킷(LSP)의 플러딩 범위를 전체 망이 아닌 개별 Area 내부로만 국한시켜 전체 네트워크의 트래픽 오버헤드를 획기적으로 줄여준다.

Q4. BGP 프로토콜에서 인터넷 라우팅 루프를 감지하고 원천 차단하기 위해 패킷 헤더 내에 삽입하여 전파하는 핵심 속성(Attribute)의 명칭과 판정 기준을 쓰시오.

모범 답안: AS-PATH 속성이다. 경로 정보가 통과해 온 자율 시스템 번호(ASN)의 리스트를 기록하여 전송하며, 라우터가 수신한 AS-PATH 목록 내에 자신의 AS 번호가 이미 포함되어 있으면 루프 경로로 판단하고 해당 경로 정보를 즉시 폐기한다.

[ 멀티캐스트 및 IGMP ]

Q5. 멀티캐스트 라우팅에서 패킷의 네트워크 루프 및 중복 복제를 방지하기 위해 입력 인터페이스의 정당성을 검증하는 RPF(Reverse Path Forwarding)의 동작 매커니즘을 출발지 주소 관점에서 설명하시오.

모범 답안: 멀티캐스트 패킷이 유입되었을 때, 패킷의 '출발지 IP 주소'를 확인한다. 유니캐스트 라우팅 테이블 상에서 해당 출발지 주소까지 도달하기 위해 사용하는 출력 인터페이스와 현재 패킷이 유입된 입력 인터페이스가 정확히 일치할 때만 패킷을 정상 수용하여 포워딩하고, 일치하지 않으면 폐기한다.

Q6. IGMPv2에서 호스트가 가상 그룹을 나갈 때 전송하는 메시지와, 이에 대응하여 로컬 라우터가 해당 링크에 그룹 수신 단말이 최종적으로 잔존하는지 파악하기 위해 전송하는 특수 제어 쿼리의 명칭을 쓰시오.

모범 답안: 호스트는 Leave Group(그룹 탈퇴) 메시지를 전송하고, 라우터는 이에 대응하여 Group-Specific Query(특정 그룹 전용 질의)를 전송하여 멤버십 잔존 여부를 확인한다.

Q7. IGMPv3가 이전 버전들과 차별화되는 가장 핵심적인 기능적 발전 요소를 필터 모드 키워드를 포함하여 서술하시오.

모범 답안: 송신자 필터링(Source Filtering) 기능이 도입되었다. 호스트가 멀티캐스트 그룹 가입 보고서를 보낼 때 특정 송신자 소스 주소 목록을 지정하여, 원하는 소스만 수신하는 INCLUDE 모드와 특정 소스를 차단하는 EXCLUDE 모드를 명시할 수 있어 대역폭 효율과 보안성이 비약적으로 향상되었다.

핵심 요약

다익스트라(Dijkstra): 링크 상태 알고리즘, LSP 플러딩을 통한 전체 토폴로지 공유, 글로벌 최단 경로 수립.
벨만-포드(Bellman-Ford): 거리 벡터 알고리즘, 이웃 간 국소적 정보 교환. 나쁜 소식의 느린 전파로 인한 Count-to-Infinity 루프 문제는 Split Horizon 및 Poison Reverse 기술로 차단.
RIP: 거리 벡터 기반 IGP, 홉 카운트(최대 15홉 제한) 메트릭 사용, 대규모 망 적용 불가, 30초 주기 업데이트.
OSPF: 링크 상태 기반 IGP, 대역폭 비용 메트릭 사용, 계층적 Area 분할 구조 지원을 통한 확장성 확보.
BGP: 경로 벡터 기반 EGP, AS-PATH 속성을 통한 인터넷 인터-도메인 루프 완벽 방지, 정책/규약 기반 최적 경로 라우팅 수행.
멀티캐스트 트리: RPF(역경로 검증) 매커니즘을 통과한 패킷만 전송. 소스 기반 트리(SPT, PIM-DM)와 공용 트리(RP 중심 공유 트리, PIM-SM) 구조로 세분화.
IGMP 진화: v1(기본 가입) → v2(Leave 메시지와 Group-Specific Query 신설로 자원 고갈 최소화) → v3(INCLUDE/EXCLUDE 송신자 필터링 제어를 통한 SSM 아키텍처 완성).

참고문헌

Forouzan, B. A. (2013). Data Communications and Networking (6th ed.). McGraw-Hill.
번역: 이재광, 김중규, 이경현, 홍충선. 데이터 통신과 네트워킹 TCP/IP 프로토콜 기반 (개정 6 수정판). 퍼스트북.

성원

버그와 싸우며 성장 중인 IT 공대생

이전 포스트

# [컴퓨터 네트워크] 7장 - 네트워크층: 데이터 전송

다음 포스트

[컴퓨터 네트워크] 9장 - 네트워크층 패킷의 라우팅