🌐 Chapter 5: Network Layer - The Control Plane

참고 자료

📌 5.1 Introduction

**네트워크 계층(Network Layer)**은 데이터를 송신자에서 수신자까지 전달하는 역할을 담당하며, 크게 두 가지 핵심 기능이 있음:

• 📬 포워딩(Forwarding)

  • 라우터(Router)의 입력(input)에 도착한 패킷(packet)을 적절한 출력(output) 인터페이스로 전달하는 과정
  • 데이터 평면(Data Plane)의 관할

• 🗺️ 라우팅(Routing)

  • 패킷을 송신 측에서 수신 측으로 전달하는 최적 경로를 결정하는 과정
  • 제어 평면(Control Plane)의 관할

네트워크의 제어 평면(Control Plane)을 구성하는 방식은 크게 두 가지 접근법으로 나눌 수 있음:

• ⚙️ 라우터별 제어(Per-Router Control, 전통적 접근법)
• 🎛️ 논리적 중앙 집중형 제어(Logically Centralized Control, Software Defined Networking: SDN)

---

⚙️ 라우터별 제어 (Per-Router Control)

개별 라우터(Router) 각각에 탑재된 라우팅 알고리즘(Routing Algorithm)이 서로 상호작용하여 포워딩 테이블(Forwarding Table)을 독립적으로 계산하고 관리함. 라우터가 분산된 형태로 동작하므로 분산 제어(Distributed Control) 방식이라고도 부름.

📝 특징

• 각 라우터가 독립적으로 동작하여 장애 발생 시 국지적으로만 영향
• 복잡한 네트워크에서는 설정 및 유지보수가 어려울 수 있음

---

🎛️ 논리적 중앙 집중형 제어 (Software Defined Networking: SDN)

논리적 중앙 집중형 제어는 라우터에서 분리된 **논리적 중앙 컨트롤러(Logical Central Controller)**가 전체 네트워크 상태를 파악하고, 라우터에 존재하는 로컬 제어 에이전트(Control Agents, CAs)와 상호작용하여 포워딩 테이블을 계산하는 방식임.

일반적으로 SDN 컨트롤러는 네트워크 외부에 배치되어 원격으로 관리되며, 개방형 소프트웨어(Open Source Software)를 기반으로 구성됨.

📝 특징

• 중앙에서 네트워크를 통합적으로 관리 가능
• 네트워크의 운영 효율성을 높이고, 복잡한 정책을 쉽게 적용할 수 있음
• 컨트롤러 장애 시 전체 네트워크가 영향받을 가능성 있음

---

🚦 5.2 Routing Protocols

📌 라우팅 프로토콜(Routing Protocol)의 목표:

• 송신 측에서 수신 측으로 패킷을 전송하기 위한 "좋은(good)" 경로를 결정하는 것

📌 경로(Path)의 정의:)

• 패킷이 송신 측에서 최종 수신 측까지 이동하면서 거쳐가게 될 라우터의 일련의 순서

📌 "좋다(Good)"의 의미:

• 최소 비용(Minimum cost)
• 최고 속도(Highest speed)
• 최소 번잡도(Minimum congestion)

---

📊 네트워크의 그래프 모델(Graph Model of Networks)

• 그래프(Graph): G = (N, E)
• 노드(Node): N (라우터(Router)의 집합)
• 엣지(Edge): E (링크(Link)의 집합)

---

💰 그래프의 비용(Cost in Graphs)

📌 링크 비용(Link Cost):

• c(X, Y): 링크 (X, Y)의 비용
• 링크의 대역폭(Bandwidth)과 혼잡도(Congestion)에 영향을 받음

📌 경로 비용(Path Cost):

• 경로가 거쳐가는 모든 링크의 비용을 합산한 값
• 라우팅 알고리즘은 최소 비용의 경로를 찾아내는 것을 목표로 함

---

🧩 라우팅 알고리즘의 분류 (Classification of Routing Algorithms)

🌐 Global (Centralized)

• 모든 라우터가 네트워크의 완전한 토폴로지(Topology)를 알고 있음
• 링크 상태(Link State) 알고리즘을 채택

🌐 Decentralized

• 라우터는 물리적으로 직접 연결된 이웃 라우터의 링크 비용만을 알고 있음
• 정보 교환과 반복적인 비용 연산을 통해 최소 비용 경로를 결정
• 거리 벡터(Distance Vector) 알고리즘 채택

---

📈 정적(Static) vs 동적(Dynamic)

⚙️ 정적(Static):

• 라우터가 정보를 천천히 갱신 및 반영

⚡️ 동적(Dynamic):

• 경로 정보가 빠르게 변화
• 주기적인 업데이트 및 링크 비용 변화에 적극 대응

---

🔗 Link State Routing Algorithm

📌 다익스트라 알고리즘(Dijkstra's Algorithm)

📍 핵심 개념:

• 링크 상태 브로드캐스트(Link state broadcast)를 통해 모든 링크의 비용을 모든 노드가 공유
• 모든 노드가 동일한 정보를 가짐
• 한 노드에서 다른 모든 노드로 가는 최소 비용 경로를 계산하여 포워딩 테이블(Forwarding Table) 생성

📍 반복 수행:

• 다익스트라 알고리즘을 k번 반복하면 k개의 목적지에 대한 최소 비용 경로 계산 가능

📍 다익스트라 알고리즘 표기법(Notation):

• c(X, Y): 노드 X에서 노드 Y로 이동하기 위한 링크 비용 (직접 연결되지 않은 경우 ∞)
• D(v): 송신측으로부터 목적지 노드 v로 이동하는 데 필요한 현재 비용
• p(v): 송신측으로부터 노드 v까지의 경로에서 직전 방문 노드
• N': 최소 비용 경로를 계산 완료한 노드의 집합

📍 다익스트라 알고리즘의 의사 코드(Pseudo Code):

Initialization:
N' = {u}
for all nodes v
  if v is a neighbor of u
    then D(v) = c(u, v)
  else
    D(v) = ∞

Loop:
find w not in N' such that D(w) is a minimum
add w to N'

update D(v) for each neighbor v of w and not in N': 
  D(v) = min(D(v), D(w) + c(w, v))

until all nodes are in N'

📍 그래프 예시(Graph Example):

📍 다익스트라 알고리즘 수행 예시:

📍 다익스트라 알고리즘의 복잡도(Complexity):

• 노드가 총 n개일 때, 각 단계에서 남아있는 모든 노드를 검사
• 총 검사 횟수는 n(n+1)/2이므로 시간 복잡도는 O(n²)
• 힙(heap) 구조 등을 이용한 최적화를 통해 시간 복잡도를 O(nlogn)까지 개선 가능

📌 Oscillation 문제 🔄

• 링크 비용이 트래픽 양에 따라 계속 변화하여 발생하는 문제
• 비용과 경로가 반복적으로 바뀌며 네트워크 상태가 불안정해질 수 있음

---

📐 Distance Vector Routing Algorithm

📌 특징

구분	설명
🔄 반복적(iterative)	이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스를 지속.
⏰ 비동기적(asynchronous)	모든 노드가 서로 정확히 맞물려 동작할 필요가 없음.
🌐 분산적(distributed)	각 노드는 직접 연결된 이웃으로부터 정보를 받아 계산한 결과를 다시 이웃들에게 배포.

---

📌 벨만-포드 방정식(Bellman-Ford Equation)

📖 정의

$d_x(y) = \min_v \{ c(x, v) + d_v(y) \}$

여기서 $d_x(y)$는 노드 $x$에서 노드 $y$로 이동할 수 있는 경로의 최소 비용이고, $c(x,v)$는 노드 $x$와 이웃 노드 $v$ 사이의 링크 비용이다.

📌 예시

$d_u(z) = \min\{ c(u, v)+d_v(z),\; c(u, x)+d_x(z),\; c(u, w)+d_w(z) \}$
$= \min\{2+5, 1+3, 5+3\} = 4$

---

📌 Distance Vector Algorithm 핵심 아이디어

📖 각 노드는 자신의 거리 벡터 추정치를 이웃에게 전송. 새로운 거리 벡터를 받으면 Bellman-Ford 방정식을 이용해 갱신. 모든 노드가 지속적으로 거리 벡터를 교환하면 최소 비용 경로의 실제 비용으로 수렴.

---

📌 Distance Vector Algorithm 의사 코드

Initialization:
  for all destinations y in N:
    D(y) = c(x, y)  // 이웃이 아니면 비용은 무한대
  for each neighbor w:
    send distance vector D = [D(y): y in N] to w

Loop:
  wait (link cost change or distance vector received)
  for each y in N:
    D(y) = min {c(x, v) + D(v)}
  if D(y) changed for any destination y:
    send updated distance vector D to all neighbors
forever

---

📌 링크 비용 변화 시 동작

상황	설명
📉 링크 비용 감소 (Good News)	빠르게 전파됨
📈 링크 비용 증가 (Bad News)	느리게 전파됨. count-to-infinity 문제 발생

• 🔄 링크 비용 감소 예시

  • 빠른 전파와 업데이트로 효율적인 경로 갱신

• 🔄 링크 비용 증가 예시 (count-to-infinity)

  • routing loop 발생 가능, 안정화에 긴 시간 소요

📌 Poisoned Reverse

📖 정의

루프 방지를 위해, 특정 노드가 이웃 노드를 통해 목적지로 가는 경로를 설정했으면 해당 이웃에게 그 목적지로 가는 비용을 무한대라고 알리는 방법이다. 모든 형태의 루프를 해결할 수는 없다.

---

🔍 Link State vs. Distance Vector

비교 요소	Link State (LS)	Distance Vector (DV)
💬 메시지 복잡도	$O(n \times E)$, 전체 네트워크 정보 교환	근접 이웃 간 정보 교환, 수렴 시간 다양
⏱️ 수렴 속도	빠름 ($O(n^2)$), Oscillation 가능성 존재	상대적으로 느림, count-to-infinity 문제 가능
🛡️ 견고성	부정확한 정보가 국지적 오류로 한정	부정확한 정보가 네트워크 전체로 전파 가능

---

🏠 5.3 Intra-AS Routing in the Internet: OSPF

📌 문제의 배경

문제 상황	설명
🌐 규모(scale)	현실적으로 라우터의 수가 매우 많아, 모든 목적지 정보를 하나의 라우팅 테이블에 저장하는 것은 불가능
🛠️ 관리 자율성(administrative autonomy)	인터넷은 네트워크의 네트워크로 각 네트워크 관리자는 자체 네트워크의 라우팅을 제어하고자 함

---

📌 인터넷의 확장 가능한 라우팅 접근법(Internet Approach to Scalable Routing)

• 🌐 자율 시스템(Autonomous System, AS or domain): 특정 지역의 라우터 집합

---

📌 라우팅의 종류

라우팅 유형	설명
📍 intra-AS routing	동일한 AS 내부에서 호스트 및 라우터 간 라우팅. 모든 라우터는 동일 intra-domain 프로토콜 실행 필요.
🌐 inter-AS routing	서로 다른 AS 간의 라우팅. gateway-router는 AS 간 연결 관리 및 inter-domain 라우팅 수행

---

📌 라우팅 알고리즘의 역할

• 📍 intra-AS routing 알고리즘

  • AS 내부 목적지에 대한 포워딩 테이블 엔트리 결정

• 🌐 inter-AS routing 알고리즘

  • AS 외부 목적지에 도달하기 위해 거쳐야 하는 외부 AS 학습 및 내부 모든 라우터와 정보 공유

---

📌 대표적인 intra-AS 프로토콜(interior gateway protocols, IGP)

프로토콜 종류	알고리즘 유형	특징
🔄 RIP	DV	Routing Information Protocol
🔗 OSPF	LS	Open Shortest Path First
🔧 IGRP	DV	Interior Gateway Routing Protocol

---

📌 OSPF (Open Shortest Path First) Protocol

• 📖 개방성(open): 누구나 사용 가능

• 🔗 알고리즘: 링크 상태 알고리즘(Link State Algorithm) 사용

  • 링크 상태 패킷 flooding을 통해 모든 라우터가 전체 네트워크 토폴로지를 획득
  • 경로 계산은 다익스트라 알고리즘(Dijkstra’s algorithm)을 활용

• 📡 링크 상태 정보 전파

  • 모든 라우터가 OSPF link-state 정보를 AS 내 모든 라우터에 직접 전파 (IP 계층에서 직접 전송, TCP/UDP 불필요)

• 🛡️ 보안

  • 모든 OSPF 메시지는 인증을 통해 악의적인 접근 방지

• 🚦 동일 비용 다중 경로 지원

  • RIP는 하나의 경로만 허용하는 반면, OSPF는 동일 비용의 여러 경로를 허용하여 트래픽 분산 가능

• 🛣️ 서비스 유형(Type of Service, TOS)별 링크 비용 설정 가능

🛠️ TOS 유형	💰 링크 비용(metric)	📌 해석
📦 Best-effort	낮음 (예: 10)	일반 트래픽은 위성 링크 사용 가능
⏱️ Real-time	높음 (예: 100)	실시간 트래픽은 위성 링크 피함

• 📢 유니캐스트와 멀티캐스트 통합 지원

  • 기존 OSPF 링크 데이터베이스 활용
  • OSPF 링크 상태 브로드캐스트 메커니즘에 새로운 형태의 링크 상태 추가

• 🗂️ 계층적 구조 지원

  • 단일 AS 내에서 계층적(hierarchical) 라우팅 구조 지원으로 관리 효율성 증가

---

🌍 5.4 Routing Among The ISPs: BGP

📌 인터넷 Inter-AS Routing: BGP (Border Gateway Protocol)

• 🌐 인터넷의 de facto 표준 inter-domain routing protocol

---

📍 BGP의 역할

역할	설명
🌍 eBGP	이웃한 AS들로부터 서브넷 도달 가능성(reachability) 정보 획득
🏠 iBGP	AS 내부 모든 라우터에 획득한 reachability 정보 전파

📖 BGP의 목표: 다른 네트워크(domain)로 향하는 "좋은" 경로를 reachability 정보와 정책(policy)을 기반으로 결정

📢 서브넷이 자신의 존재를 인터넷에 광고(advertise)할 수 있도록 지원

---

📍 BGP Basics

• 🔗 BGP 세션: 두 BGP 라우터(peer)는 반영구적 TCP 연결을 통해 BGP 메시지를 교환

• 🗃️ BGP attribute를 포함한 prefix 광고:

  • Prefix + Attribute = "route"

Attribute	설명
🛣️ AS-PATH	prefix 광고가 지나온 AS의 목록
🔀 NEXT-HOP	다음 AS로 패킷을 전달할 내부 라우터 IP 주소, 즉 AS-PATH가 시작되는 라우터의 인터페이스 IP 주소

📌 정책 기반 라우팅

• 경로 광고를 받은 게이트웨이는 경로를 채택/거부하는 import policy 적용
• AS 정책은 이웃 AS에 경로를 광고할지 여부를 결정

• AS3 게이트웨이 라우터인 3a는 경로 AS3, X를 AS2 게이트웨이 라우터인 2c에 광고. AS3는 AS2에 데이터그램을 X로 포워딩해줄 것을 약속.
• AS2 라우터인 2c는 eBGP를 통해 경로 광고 AS3, X를 AS3 3a으로부터 수신.
• AS2의 정책에 기반해 AS2 라우터 2c는 경로 AS3, X를 채택, iBGP를 통해 AS2 내부의 모든 라우터에 해당 경로를 전파.
• AS2 정책에 의거, AS2 라우터 2a는 eBGP를 통해 경로 AS2, AS3, X를 AS1 라우터 1c에 전달.

---

📍 다양한 경로 학습 및 선택

• 게이트웨이는 다양한 경로를 학습할 수 있으며, 정책에 따라 최적 경로를 선택

• 선택한 경로는 iBGP를 통해 내부 라우터와 공유됨

• 위 그림과 같은 상황에서 AS1 게이트웨이 라우터 1c는 2a로부터 경로 AS2, AS3, X 학습. 3a로부터 경로 AS3, X 학습.

• AS1 정책에 기반해 1c는 경로를 선정. 결정된 경로를 iBGP 통해 AS1 내부의 모든 라우터에 공유.

---

📍 BGP 메시지

메시지 종류	역할
🚪 OPEN	원격 BGP peer와 TCP 연결 개방 및 인증
🔄 UPDATE	새로운 경로 광고 또는 기존 경로 철회
⏳ KEEPALIVE	연결 상태 유지 및 OPEN 메시지 ACK
⚠️ NOTIFICATION	오류 보고 및 연결 종료 요구

---

📍 BGP 경로 선택 기준

경로가 여러 개일 때 선택 기준:

1. 📝 AS 자체 정책
2. 📏 가장 짧은 AS-PATH
3. 🌶️ 가장 가까운 NEXT-HOP 라우터 (Hot Potato Routing)
4. 🔍 추가적 기준

🌶️ Hot Potato Routing 예시

• 2a를 거쳐가는 AS1, AS3, X. (2a까지 가는 최소비용 201)
• 2c를 거쳐가는 AS3, X. (2c까지 가는 최소비용 263)

Hot potato routing은 intra-domain 비용이 최소인 로컬 게이트웨이를 선택. 즉, 2d는 AS hop이 더 많더라도 2a를 선택함.

---

📍 라우팅 정책 예시

• ISP는 고객 네트워크의 트래픽만 라우팅하고 싶음
• ISP A는 경로 Aw를 ISP B와 ISP C에 광고.
• B는 경로 BAw를 C에 광고하지 않기로 선택. (C, A, w는 B의 고객이 아니라서 B는 경로 CBAw를 라우팅해서 얻는 이익이 없기 때문)
• C는 경로 CAw를 통해 w로 가는 트래픽을 라우팅.

---

📍 Inter-AS vs. Intra-AS 비교

구분	Inter-AS	Intra-AS
📜 정책	각 관리자가 자신의 네트워크를 통해 트래픽이 누가 어떻게 라우팅하는지 제어하고 싶어함.	관리자가 단일, 별도의 정책 결정 불필요
📈 스케일	계층적 라우팅으로 라우팅 테이블 크기 절약 및 트래픽 감소	계층적 구조로 효율적 관리 및 트래픽 관리 가능
🚀 성능	성능보다는 정책 우선	성능에 중점 맞춤

---

🧠 5.5 The SDN Control Plane

📌 과거의 인터넷 네트워크 계층 구조

구성 요소	설명
🧱 Monolithic Router	스위칭 하드웨어(HW)와 라우팅 소프트웨어(SW)를 통합한 장비. 벤더 종속 (예: Cisco)
📦 Middlebox	라우터/스위치를 제외한 특화 장비 (예: 방화벽, 로드 밸런서, NAT 등)

• 🧩 기존 per-router control plane: 각 라우터가 개별적으로 라우팅 알고리즘을 실행하며 상호작용
• 🧠 SDN의 logically centralized control plane: 중앙 컨트롤러가 각 로컬 라우터의 Control Agent(CA)와 상호작용하여 forwarding table 계산

📌 SDN 장점

• 🧰 네트워크 관리의 용이성:

  • count-to-infinity, oscillation 문제 회피 가능
  • 유연한 트래픽 흐름 관리 가능

• 💡 테이블 기반 포워딩 = 프로그래밍 가능한 라우터 실현

프로그래밍 방식	설명
🧷 중앙집중식(Centralized)	컨트롤러에서 계산한 포워딩 테이블을 각 스위치에 배포 → 구현 쉬움
🔄 분산식(Distributed)	각 라우터가 분산 알고리즘으로 테이블 계산 → 구현 복잡

---

📌 SDN Controller 구조

📡 OpenFlow Protocol

SDN 컨트롤러와 OpenFlow API를 구현한 스위치 간 통신을 담당하는 프로토콜

컨트롤러 → 스위치 메시지

메시지 유형	기능 설명
📋 features	스위치 기능 질의, 스위치는 자신이 지원하는 기능을 응답
⚙️ configure	스위치 설정 파라미터 조회/설정
🧾 modify-state	Flow Table 항목 추가(add), 삭제(delete), 수정(modify)
📤 packet-out	특정 패킷을 지정된 포트로 직접 전송하도록 지시

스위치 → 컨트롤러 메시지

메시지 유형	기능 설명
📥 packet-in	스위치가 처리 못한 패킷을 컨트롤러에 전달하여 제어 요청
❌ flow-removed	Flow Table에서 항목 삭제되었음을 컨트롤러에 통보
📶 port status	포트 상태 변화 (업/다운 등)를 컨트롤러에 알림

⚠️ 운영자가 OpenFlow 메시지를 직접 제어하지 않으며, 컨트롤러가 고수준 추상화 API를 통해 처리함

---

🔄 Control/Data Plane Interaction 예시

1️⃣ 스위치 s1에서 링크 장애 발생 → port status 메시지로 컨트롤러에 알림

2️⃣ SDN 컨트롤러가 메시지를 수신 → 내부 링크 상태 정보(link-state info) 갱신

3️⃣ 등록된 다익스트라(Dijkstra) 알고리즘 호출 → 새로운 경로 계산

4️⃣ 컨트롤러는 네트워크 그래프와 링크 상태 기반으로 최적 경로 계산

5️⃣ 계산 결과 기반으로 어떤 스위치에 어떤 룰이 필요한지 결정

6️⃣ OpenFlow 프로토콜로 스위치들의 flow table을 업데이트

---

⚠️ 5.6 ICMP: Internet Control Message Protocol

🎯 목적 및 개요

• ICMP는 호스트나 라우터가 네트워크 상태를 알리고 진단하는 데 사용됨
• IP 프로토콜 위에서 동작하며, IP 패킷 내부에 포함됨 (IP payload로 동작)

---

🛠️ 주요 용도

기능	설명
❗ 에러 리포팅	목적지 호스트/네트워크/포트/프로토콜 접근 불가 시 경고
🔁 에코 요청/응답	ping 명령어의 기반 기능, 연결 상태 확인용

---

🧾 ICMP 메시지 구성

• 필드: type, code
• 오류 유발한 IP 패킷의 앞 8바이트 포함됨

Type	Code	설명
0	0	Echo reply (ping 응답)
3	0~7	Destination unreachable (네트워크, 호스트, 포트 등 도달 불가)
4	0	Source quench (혼잡 제어 – 현재는 사용되지 않음)
8	0	Echo request (ping 요청)
9	0	Route advertisement
10	0	Router discovery
11	0	TTL expired (중간 라우터에서 TTL 소진됨)
12	0	Bad IP header (잘못된 IP 헤더)

---

✅ Traceroute and ICMP

📌 동작 개요

• 출발지에서 목적지까지 가는 라우팅 경로 추적에 사용
• 기본 원리: IP 패킷의 TTL(Time-To-Live) 값을 1부터 증가시키며 전송

⚙️ 동작 절차

1. UDP 패킷 전송 시작
2. 첫 번째 패킷: TTL=1 → 첫 번째 라우터에서 TTL=0 되어 폐기됨
3. 해당 라우터는 ICMP 메시지(type=11, code=0) 전송 → TTL 만료
4. 송신자는 이를 수신하여 중간 라우터의 IP와 RTT 기록
5. 이후 TTL을 증가시켜 반복

🎯 목적지에 도달 시

• 목적지 호스트는 해당 포트가 열려있지 않으므로:

📩 ICMP port unreachable 메시지(type=3, code=3)를 반환

• 이를 통해 목적지에 도달했음을 확인하고 Traceroute 종료

---