05 Network Layer - Control Plane

1. Routing Algorithm 개요

Routing algorithm의 목표는 sender에서 receiver까지의 네트워크를 통한 “좋은” 경로(최소 비용, 최단, 최소 혼잡 등)를 결정하는 것이다. 네트워크를 graph로 모델링하여 분석한다.

Node: Router
Edge: Router 간 link
Edge cost: Bandwidth, congestion, distance 등을 반영하는 가중치

1.1 Routing Algorithm 분류

분류 기준	유형	설명
정보 범위	Global (Link State)	모든 router가 전체 토폴로지와 link cost를 알고 있음
	Decentralized (Distance Vector)	각 router가 이웃까지의 link cost만 알고, 이웃과 정보를 교환하여 반복적으로 계산
동적성	Static	경로가 느리게 변함 (수동 관리)
	Dynamic	경로가 빠르게 변함 (주기적 업데이트 또는 link cost 변화 시)

2. Link State Routing: Dijkstra’s Algorithm

2.1 개요

Link state algorithm에서는 전체 네트워크 토폴로지와 모든 link cost가 모든 node에 알려져 있다. 이를 위해 각 node가 자신의 link state(인접 link의 cost)를 네트워크 전체에 broadcast한다 (“link state broadcast”). 모든 node가 동일한 정보를 갖게 되면, 각 node가 독립적으로 Dijkstra’s algorithm을 실행하여 자신에서 다른 모든 node까지의 최단 경로를 계산한다.

2.2 Dijkstra’s Algorithm

표기법:

$c (x, y)$ : Node $x$ 에서 $y$ 까지의 direct link cost. 인접하지 않으면 $\infty$
$D (v)$ : Source에서 $v$ 까지의 현재까지 알려진 최소 비용 경로의 cost
$p (v)$ : Source에서 $v$ 까지의 최소 비용 경로에서 $v$ 의 직전(predecessor) node
$N^{'}$ : 최소 비용 경로가 확정된 node의 집합

알고리즘 동작:

초기화: Source node $u$ 를 $N^{'}$ 에 추가. $u$ 의 인접 node는 $D (v) = c (u, v)$ , 나머지는 $D (v) = \infty$
반복:
- $N^{'}$ 에 속하지 않은 node 중 $D (a)$ 가 최소인 node $a$ 를 찾아 $N^{'}$ 에 추가
- $a$ 의 인접 node $b$ ( $N^{'}$ 에 미포함)에 대해: $D (b) = min (D (b), D (a) + c (a, b))$ 로 갱신
모든 node가 $N^{'}$ 에 포함되면 종료

2.3 예시

Source $u$ 에서 시작하여, 각 step에서 최소 비용 node를 선택하고 인접 node의 비용을 갱신한다.

결과:

$u \to v$ : cost 2, outgoing link (u,v)
$u \to x$ : cost 1, outgoing link (u,x)
$u \to y$ : cost 2, outgoing link (u,x) → x → y
$u \to w$ : cost 3, outgoing link (u,x) → x → y → w
$u \to z$ : cost 4, outgoing link (u,x) → x → y → z

모든 destination에 대한 forwarding table이 구성된다. v를 제외한 모든 목적지의 next hop이 x임을 주목하자.

2.4 복잡도와 문제점

Algorithm complexity ( $n$ 개 node):

매 iteration마다 $N^{'}$ 에 없는 모든 node를 검사: $n (n + 1) /2$ 비교 → $O (n^{2})$
Heap 기반 구현으로 $O (n lo g n)$ 까지 개선 가능

Message complexity:

각 router가 link state 정보를 $n$ 개 router에 broadcast: $O (n)$ link crossing per broadcast
$n$ 개 router가 각각 broadcast: 전체 $O (n^{2})$ messages

Oscillation 문제:

Link cost가 traffic volume에 의존하면, routing이 변할 때 traffic pattern도 바뀌고, 이것이 다시 link cost를 바꾸어 routing을 변경시키는 oscillation(진동)이 발생할 수 있다.

3. Distance Vector Routing: Bellman-Ford Algorithm

3.1 Bellman-Ford Equation

$D_{x} (y)$ : Node $x$ 에서 $y$ 까지의 least-cost path cost

D_{x} (y) = v min {c (x, v) + D_{v} (y)}

$v$ : $x$ 의 모든 neighbor
$c (x, v)$ : $x$ 에서 $v$ 까지의 direct link cost
$D_{v} (y)$ : $v$ 에서 $y$ 까지의 least-cost path cost (neighbor $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$

최소값을 달성하는 neighbor $x$ 가 $u$ 에서 $z$ 로 가는 최단 경로의 next hop이 된다.

3.2 Distance Vector Algorithm

핵심 아이디어: 각 node가 자신의 distance vector(DV) - 모든 destination까지의 추정 cost 벡터 - 를 이웃에게 주기적으로 전송한다.

각 node의 동작:

Wait: Local link cost 변화 또는 neighbor로부터 DV update 수신 대기
Recompute: 수신한 DV를 이용하여 B-F equation으로 자신의 DV를 재계산
Notify: DV가 변경되면 neighbor에게 알림. 변경이 없으면 아무것도 보내지 않음

특성:

Iterative: 각 local iteration이 local link cost 변화 또는 neighbor의 DV 업데이트에 의해 trigger
Asynchronous: Node 간 동기화 불필요
Distributed, self-stopping: 각 node가 독립적으로 동작하며, DV가 수렴하면 자연스럽게 멈춤

3.3 Link Cost 변화와 Count-to-Infinity

Good news travels fast

Link cost가 감소하면 좋은 소식은 빠르게 전파된다:

$t_{0}$ : $y$ 가 link cost 변화를 감지하고 DV를 갱신, neighbor에 알림
$t_{1}$ : $z$ 가 $y$ 의 update를 받고 새 least cost를 계산, DV를 전송
$t_{2}$ : $y$ 가 $z$ 의 update를 받고 DV 확인 - 변경 없으므로 전파 중단

Bad news travels slow (Count-to-Infinity)

Link cost가 크게 증가하면 문제가 발생한다:

$y$ 가 $x$ 로의 direct link cost가 60으로 증가한 것을 감지
하지만 $z$ 는 “나는 $x$ 까지 cost 5로 갈 수 있다” ( $y$ 를 경유하는 경로인데!)고 알려줌
$y$ 는 $z$ 를 경유하면 6으로 갈 수 있다고 생각 → $z$ 에 알림
$z$ 는 다시 7, $y$ 는 8… 이렇게 50까지 점진적으로 증가 (count-to-infinity 문제)

해결책으로 Poisoned reverse 등의 기법이 있지만, 3개 이상의 node가 관여하는 loop에서는 여전히 문제가 될 수 있다.

4. LS vs DV 비교

비교 항목	Link State	Distance Vector
Message complexity	$n$ 개 router, $O (n^{2})$ messages	Neighbor 간에만 교환, 수렴 시간 가변
Speed of convergence	$O (n^{2})$ algorithm. Oscillation 가능	수렴 시간 가변. Routing loop, count-to-infinity 가능
Robustness	Router가 잘못된 link cost를 광고할 수 있지만, 각 router가 자신의 table만 계산	Router가 잘못된 path cost를 광고할 수 있고 (black-holing), 각 router의 DV가 다른 router에 의해 사용되므로 error가 전파됨

5. Scalable Routing: AS와 Intra/Inter-AS Routing

5.1 문제: 확장성과 관리 자율성

지금까지의 routing 연구는 이상적 가정(모든 router가 동일, network가 “flat”)에 기반했다. 현실에서는:

Scale: 수십억 개의 destination을 하나의 routing table에 넣을 수 없다
Administrative autonomy: 각 네트워크 관리자가 자체 네트워크 내의 routing을 자율적으로 제어하고 싶어한다

5.2 Autonomous System (AS)

해결: Router를 Autonomous System (AS) 또는 “domain”이라는 단위로 묶는다.

Intra-AS routing (intra-domain): 같은 AS 내의 router 간 routing. 같은 AS의 모든 router는 동일한 intra-domain protocol을 실행. 다른 AS는 다른 프로토콜을 사용할 수 있다
Inter-AS routing (inter-domain): AS 간의 routing. Gateway router가 AS의 “edge”에 위치하여 다른 AS의 router와 연결

Forwarding table은 intra-AS와 inter-AS routing algorithm 모두에 의해 구성된다:

AS 내부 destination → intra-AS routing이 결정
AS 외부 destination → inter-AS routing이 어느 gateway를 통해 나갈지 결정, intra-AS routing이 그 gateway까지의 경로를 결정

6. OSPF (Open Shortest Path First)

OSPF [RFC 2328]는 가장 널리 사용되는 intra-AS routing protocol이다.

특성:

Open: 공개 표준
Classic link-state algorithm: 각 router가 OSPF link-state advertisement를 AS 내 모든 router에 flood
IP 위에서 직접 동작 (TCP/UDP를 사용하지 않음)
각 router가 전체 AS topology를 가지고 Dijkstra’s algorithm으로 forwarding table을 계산
Link cost metric으로 bandwidth, delay 등을 사용할 수 있음
Security: 모든 OSPF message가 authenticated (악의적 침입 방지)

6.1 Hierarchical OSPF

대규모 AS에서는 OSPF를 2-level hierarchy로 구성한다:

Local area: Link-state advertisement는 area 내부에서만 flood
Backbone: Area를 연결하는 backbone area
Area border router: 자기 area 내 destination까지의 거리를 “요약(summarize)“하여 backbone에 광고
Backbone router: Backbone 내에서만 OSPF를 실행
Boundary router: 다른 AS와 연결

7. BGP (Border Gateway Protocol)

BGP [RFC 4271]는 Internet의 inter-AS routing protocol이다. “Internet을 하나로 묶는 접착제(glue)“라고도 불린다.

BGP가 각 AS에 제공하는 기능:

eBGP (external BGP): 인접 AS로부터 subnet reachability 정보를 획득
iBGP (internal BGP): AS 내부 모든 router에 reachability 정보를 전파
Reachability 정보와 policy에 기반하여 다른 네트워크로의 “좋은” 경로를 결정
인접 AS에 자신의 reachability 정보를 advertise

7.1 eBGP와 iBGP

eBGP session: 서로 다른 AS의 gateway router 간에 설정되는 semi-permanent TCP 연결
iBGP session: 같은 AS 내의 router 간에 설정되는 TCP 연결 (모든 router 쌍 사이)
Gateway router는 eBGP와 iBGP를 모두 실행한다

7.2 BGP 기본 동작

BGP session을 통해 교환되는 정보: destination network prefix에 대한 path (“path vector” protocol)

예시: AS3의 gateway 3a가 eBGP로 “AS3, X” path를 AS2의 gateway 2c에 광고한다. AS2의 2c는 이를 수락하고 iBGP로 AS2 내부에 전파한다. AS2의 gateway 2a가 다시 eBGP로 “AS2, AS3, X” path를 AS1의 1c에 광고한다.

7.3 Path Attributes와 BGP Route

BGP advertised route = prefix + attributes

두 가지 중요한 attribute:

AS-PATH: 이 prefix 광고가 경유한 AS들의 목록. Loop detection에도 사용 (자신의 AS가 이미 path에 있으면 거부)
NEXT-HOP: Next-hop AS로 가는 internal-AS router의 구체적인 IP 주소

Policy-based routing: Gateway router가 import policy로 경로를 수락/거부하고, export policy로 어떤 경로를 어떤 neighbor에 광고할지 결정

7.4 BGP Route Selection

Router가 같은 destination prefix로의 여러 경로를 학습했을 때, 다음 순서로 선택:

Local preference 값 (policy decision) - 최우선
Shortest AS-PATH - AS hop 수가 가장 적은 경로
Closest NEXT-HOP (hot potato routing) - intra-domain cost가 가장 낮은 gateway
Additional criteria (BGP identifier 등)

Hot Potato Routing

Hot potato routing은 “뜨거운 감자를 빨리 넘기듯” packet을 자기 네트워크에서 가장 빠르게 내보내는 전략이다. Inter-domain cost는 고려하지 않고, intra-domain cost만으로 가장 가까운 gateway를 선택한다.

7.5 BGP Policy 예시

ISP는 일반적으로 자신의 customer network와의 트래픽만 routing하고, 다른 ISP 간의 transit traffic은 routing하지 않으려 한다:

Provider B가 customer network w로의 path “Aw”를 A에게서 학습했더라도, 이를 peer C에게 광고하지 않는다 - C, A, w 중 어느 것도 B의 customer가 아니므로 revenue가 없기 때문
Dual-homed customer x는 B에서 C로의 transit traffic을 원하지 않으므로, B에게 C로의 경로를 광고하지 않는다

7.6 왜 Intra-AS와 Inter-AS Routing을 구분하는가?

기준	Intra-AS	Inter-AS
Policy	단일 관리자 → policy가 덜 중요	관리자가 트래픽 routing 방식을 제어하고 싶어함 → policy가 성능보다 중요
Scale	-	계층적 routing으로 table 크기와 update traffic 감소
Performance	성능에 집중 가능	Policy가 성능을 override

8. SDN Control Plane

8.1 전통적 접근 vs SDN

전통적 network layer: 분산된 per-router control approach

Monolithic router가 proprietary OS에서 standard protocol(IP, OSPF, BGP)을 실행
다른 기능(firewall, load balancer, NAT)은 별도 middlebox

SDN(~2005): Control plane을 재정의

Data plane과 control plane의 분리: Data plane switch는 단순한 forwarding만 수행
Control plane은 remote controller(network OS)에서 실행
Generalized flow-based forwarding (OpenFlow)
Programmable control application: Routing, access control, load balancing 등

8.2 SDN Architecture

SDN의 4가지 핵심 특성:

Flow-based forwarding: OpenFlow 등으로 generalized forwarding
Control/data plane separation: Data plane switch + remote controller
Control plane functions external to switches: Controller + control application이 별도 서버에서 실행
Programmable control applications: Routing, access control, load balance를 software application으로 구현

8.3 SDN Controller 구성

SDN controller (network OS)는 세 계층으로 구성된다:

Communication layer (southbound API): OpenFlow, SNMP 등을 통해 controlled switch와 통신
Network-wide state management: Network link, switch, host 정보를 distributed database로 관리
Interface to network control apps (northbound API): Network graph, RESTful API, intent 등의 추상화를 control application에 제공

8.4 SDN 동작 예시

Link failure 시 SDN의 동작:

Switch S1이 link failure를 감지하고 OpenFlow port status message를 controller에 전송
SDN controller가 link state 정보를 갱신
Dijkstra’s routing algorithm application이 link state 변화에 따라 호출됨
Routing app이 network graph와 link state 정보를 이용하여 새 경로를 계산
Routing app이 flow-table-computation component와 상호작용하여 새 flow table을 생성
Controller가 OpenFlow를 사용하여 영향 받는 switch에 새 flow table을 설치

대표적 SDN controller: OpenDaylight (ODL), ONOS (Open Network Operating System)

9. ICMP (Internet Control Message Protocol)

ICMP는 host와 router가 network-level 정보를 교환하는 데 사용하는 프로토콜이다.

Error reporting: Unreachable host/network/port/protocol
Echo request/reply: ping 명령이 사용
Network layer “위에” 위치하지만 IP datagram에 담겨 전송

ICMP message 구성: Type, Code, 그리고 오류를 유발한 IP datagram의 첫 8 bytes

주요 ICMP message type:

Type	Code	설명
0	0	Echo reply (ping)
3	0-7	Destination unreachable (network/host/protocol/port 등)
8	0	Echo request (ping)
11	0	TTL expired (traceroute가 사용)
12	0	Bad IP header

Traceroute와 ICMP: Source가 TTL=1, 2, 3… 인 UDP segment를 전송하면, 각 router에서 TTL이 만료되어 ICMP “TTL expired” (type 11, code 0) 메시지가 반환된다. Destination에 도달하면 “port unreachable” (type 3, code 3) 메시지가 반환되어 traceroute가 종료된다.

10. Network Management

10.1 개요

수천 개의 hardware/software component로 구성된 네트워크를 관리하려면 체계적인 접근이 필요하다.

네트워크 관리의 구성 요소:

Managing server/controller: Network manager(사람)가 사용하는 application
Managed device: Router, switch 등 관리 대상 장비. 내부에 agent가 동작하며 data(MIB)를 관리
Network management protocol: Managing server가 device를 조회/설정하고, device가 server에 이벤트를 알리는 데 사용

10.2 관리 접근법

접근법	설명
CLI	SSH 등으로 개별 device에 직접 명령 (가장 원시적)
SNMP/MIB	SNMP protocol로 device의 MIB data를 조회/설정
NETCONF/YANG	더 추상적이고 network-wide한 접근. Multi-device configuration 관리

10.3 SNMP (Simple Network Management Protocol)

SNMP는 두 가지 방식으로 MIB 정보를 전달한다:

Request/Response mode: Managing server가 agent에게 MIB data를 요청하고 응답을 받음
Trap mode: Agent가 예외적 이벤트 발생 시 managing server에 자발적으로 알림

주요 SNMP message type:

Message	방향	설명
GetRequest	Manager → Agent	MIB data 요청
GetNextRequest	Manager → Agent	다음 MIB data 요청 (순회)
GetBulkRequest	Manager → Agent	대량 MIB data 요청
SetRequest	Manager → Agent	MIB 값 설정
Response	Agent → Manager	요청에 대한 응답
Trap	Agent → Manager	예외적 이벤트 알림

MIB (Management Information Base): Managed device의 operational/configuration data를 저장하는 구조. SMI(Structure of Management Information)로 data type을 정의. 400+ MIB module이 RFC로 정의됨.

10.4 NETCONF/YANG

NETCONF [RFC 6241]는 SNMP보다 현대적인 network management protocol이다.

목표: 여러 device의 configuration을 network-wide로 관리
Atomic-commit: 여러 device에 대한 설정 변경을 원자적으로 수행
Configuration retrieve/set/modify, operational data 조회, notification 구독
RPC(Remote Procedure Call) 패러다임. XML 기반 message. TLS 위에서 동작

YANG: NETCONF network management data의 structure, syntax, semantics를 정의하는 data modeling language. SMI와 유사한 역할이지만 더 현대적이다. YANG description으로부터 XML document를 생성하여 NETCONF message에 포함할 수 있다.

11. Chapter 5 정리

주제	핵심 내용
Routing Algorithm	Graph model. Global(LS) vs Decentralized(DV), Static vs Dynamic
Link State (Dijkstra)	전체 토폴로지 broadcast. $O (n^{2})$ 또는 $O (n lo g n)$ . Oscillation 가능
Distance Vector (B-F)	Neighbor와 DV 교환. Iterative, asynchronous, self-stopping. Count-to-infinity 문제
AS	Router를 domain으로 묶어 확장성과 관리 자율성 확보. Intra-AS vs Inter-AS
OSPF	Intra-AS, link-state. IP 위에서 직접 동작. Hierarchical(area+backbone). Authenticated
BGP	Inter-AS, path vector. eBGP(AS 간) + iBGP(AS 내). Policy > Performance. Hot potato routing
SDN	Control/data plane 분리. Remote controller. OpenFlow. Traffic engineering 용이
ICMP	Error reporting, echo request/reply. Traceroute(TTL expired + port unreachable)
Network Management	SNMP(request/response + trap, MIB), NETCONF/YANG(XML, RPC, atomic-commit)

탐색기

회고

일상

정원