[CS/네트워크] 4. Network layer

1. Forwarding vs Routing

Forwarding	Routing
Data plane에서 앞으로 보내기	Control plane에서 길 찾기

Control plane을 바탕으로 Data plane에 routing 정보 기록

Data plane에서는 이것으로 보고 Forwarding

 

 

2. Per-Router Control Plane

router마다 routing algorithm이 존재

Distributed control

 

 

3. Locally Centralized Control Plane

local control agent가 remote controller에 정보 제공

Centralized control

 

 

4. Data plane

4.1. Forwarding

Destination based	dest IP 기반
Generalized	header 값 기반

Logest prefix matching으로 forwarding

 

4.2. Scheduling

FIFO	들어온 순서대로 나감
Priority scheduling	Priority가 높은 것부터 수행, starvation 가능
Round Robin	time slice마다 하나씩 공평하게 수행
Weighted-Fair queuing	weighted queue에 따라 RR 수행 (weight = 비율)

 

 

4.3. IP

IP datagram

 

IP fragmentation, reassembly

network 상황에 따라 MTU가 다르기에 fragmentation을 통해 크기를 줄임

Destination에서 reassemble

flag와 offset을 통해 fragmented packet의 순서를 확인할 수 있음

 

Subnet

IP 자원을 구역별로 관리

Subnet mask/24  =  10.1.1.0/24

24 bit까지 subnet mask로 사용, 32 bit(IPv4)면 나머지 8 bit로 host에게 IP 할당

 

DHCP

IP를 임시로 빌려주는 protocol

Broadcast 기반으로 돌아감 (IP 충돌을 막기 위해서)

0.0.0.0 == my host IP

255.255.255.255 === broadcast IP

 

NAT

network address translation on router

source의 IP, port 정보와 outgoing 정보를 mapping

*Issue: port # 마음대로 변경, router의 cross layer 역할, NAT 뒤에 있을 서버

 

IPv4 vs IPv6

IPv4	IPv6
32 bit NAT 사용	128 bit NAT 사용 x Qos(quality of service) 제공

 

 

5. Control Plane

5.0. Shortest Path Routing problem

hop 수가 아닌 cost가 최소가 되어야 함

 

5.1. Centralized vs Decentralized

Centralized	Decentralized
Link-state algorithm	Distance-vector algorithm
single point of failure complexity	optimality 부족

 

5.2. Dijkstra

일반적으로 O(n^2), 최소 O(nlogn)도 가능 on network

d[v] = min{ d[v], d[u] + cost[u][v] }

선택된 node를 기준으로 주변 node의 d[v] update & min 선택

 

5.3. Bellman-Ford

O(VE) 소모, Dijkstra보다 조금 느림

음수간선 처리 가능

모든 node에 대해서 매번 update & min 선택

d[v] = min{ d[v], d[u] + cost[u][v] for all neighbor of v }

 

5.4. Distance-Vector

dx[y] = min{ cost[x][y], cost[x][z] + dz[y] }

(1) 연결된 node로부터 d 정보를 받아오기

(2) 자기꺼 update

(3) 더 이상 update가 이루어지지 않으면 종료

 

* Link cost changed issue

Link cost가 감소하는 것은 Good

Link cost가 증가하는 것은 Bad -> 반영이 느림, 서서히 cost가 증가

*Poisoned reverse

Link cost가 증가하면 해당 link cost = INF 처리

 

5.5. LS vs DS

	Link state algorithm	Distributed state algorithm
Message complexity	nE msg 전송, 상대적으로 작음	node끼리 교환
Speed of convergence	O(n^2)으로 비슷
Robustness	error 걱정 x	error propagated

 

 

6. Intra-AS

같은 AS 내부 routing, performance가 중요

Gateway router 다른 AS와 연결해주는 router

OSPF(LS), RIP(DV), IGRP(DV)

 

6.1. OSPF (open shortest path first)

내부 AS 하위 체계를 Dijkstra나 SPF로 살펴봄

cost만 저렴하면 어떤 path든 사용

계층적 area 단위로 관리됨

convergence time이 빠른 편

목적에 따라 multiple cost metric 구현 가능

security 측면에서 좋음

uni- multi- cast 지원

 

 

7. Inter-AS

서로 다른 AS간 routing, policy가 더 중요

Gateway router는 Intra, Inter domain routing모두 수행

 

7.1. BGP (border gateway protocol)

AS-PATH	지나온 path
NEXT-HOP	다음으로 선택할 Hop
eBGP	AS-AS protocol
iBGP	Intra protocol

(1) local preference에 따른 path 결정

(2) shortest AS-PATH를 가지도록 path 탐색

(3) closest NEXT-HOP router를 가지도록 path 탐색

     - HOT-POTATO

       intra-AS cost가 적도록 gateway router를 설정해서 그쪽으로 보내달라고 만듦

       이 과정에서, 다른 AS 측면에서는 손해를 볼 수 있지만, 알 바는 아님

 

 

8. Intra-AS vs Inter-As

Policy
Intra-AS	AS admin 마음대로
Inter-AS	AS간의 약속

Performance
Intra-AS	Performance 우선
Inter-AS	Policy 우선

Scale

Hierarchical routing