[강의정리] 데이터통신과네트워크 Network Layer
Network-layer function
Forwarding: 여러개의 패킷을 매칭되는 output 포트로 연결시켜주는 역할
Routing: 포워딩한 패킷들이 정해진 목적지까지 가는것
예시: 여행
- 포워딩: 교차로에서 어디로갈지 결정
- 라우팅: 출발점에서 도착점까지 어떤 경로로 갈지 정하는것
Data plane
- router input port로 어떠한 데이터가 왔을 때 output port로 포워딩을 해주는것을 결정하는 역할
control plane
datagram이 왔을때 어떤경로로 routing 해줄지 결정
2가지 control-plane approaches:
- traditional routing algorithm: 패킷에서 최선의 결정으로 라우팅
- software-defined networking(SDN): 중앙에서 소프트웨어적으로 라우팅을 변경해줌
Tanditional Approch
- Routing Alogrithm: forwarding table을 만들어줌 (control plane)
- table로 forwarding 시켜줌(data plane)
SDN
- 중앙서버에 RemoteController 존재.
- 각Router에 Control agents로 컨트롤
Router architecture
Input port functions
- line termination: 아날로그신호 -> 디지털
- link layer protocol: link layer에서 작업
decentralized switching
- lookup: 어느 output port로갈지 결정
- forwarding: output 출력 port 설정
- queueing: 나가는 속도보다 들어오는 속도가 빠르면 queueing
destination-based forwarding:
- 패킷에서 destination 해더 정보를 보고 어디로 보낼지 결정
generalized forwarding:
- 헤더의 여러 정보들을 보고 결정
- 특수한 경우에만 사용
Switch fabric
- 경로들이 엉킬수도 있음 (fabric: 직물)
destination-based forwarding
- destination IP Address 주소를 기반으로 어떤 Output Port로 데이터를 보낼 것인지를 결정하는 forwarding algorithm
longest prefix matching
- 원하는 부분만 정하고 나머지부분은 와일드카드로 설정하는 방법
Switching
- Switching fabric: 라우터의 핵심
- memory: 과거방식, 패킷을 받고 메모리에 보관후 포워딩 테이블을 보고 보냄, 인터럽트 기반.
- bus: 레이블을 붙여서 버스에 보냄, 자신의 레이블이면 받아서 처리, 아니면 드롭
- crossbar: interseption마다 on off 스위치 있음
Input port queueing
- Head-of-the-Line(HOL) blocking: 앞선 패킷(head)이 나가지 않았을 때 뒤에있는 패킷들도 계속 기다리는 현상
Output port queueing
- line termination에서 보내는 속도가 switch fabric에서 들어오는 속도보다 느릴 때 datagram buffer에서 queueing 발생
- scheduling discipline: 우선순위 기발 패킷 스케쥴링
Schedule mechanisms (스케쥴링 매커니즘)
- FIFO 스케쥴링: 먼저 들어온 패킷을 먼저 보냄(FCFS)
priority scheduling (우선순위 스케쥴링)
- 여러개 큐중 우선순위가 높은 큐의 패킷부터 전송
- 우선순위가 낮은 큐는 끝없이 밀릴 수 있음: 가중치를 줘서 우선순위를 가변적으로 만듬
Round Robin (RR)
- 각 클래스마다 한번씩 보냄
Weighted Fair Queueing (WFQ)
- Round Robin 방식에서 사용
- 각 클래스에 사이클의 weight를 줌
Internet network layer
- routing protocols -> forwarding table
- IP protocol
IP fragmentation, reassembly
- network links have MTU(max transfer size)
- fragmentation: 큰 패킷이 MTU때문에 작게 쪼개지는것
- reassembly: 쪼개진 패킷들을 합치는것 (final destination에서만 이루어짐)
example
- 4000byte datagram
- MTU = 1500bytes
- length: 1500(1480 data field) / ID = x / fragflag = 1 / offset = 0
- length: 1500(1480 data field) / ID = x / fragflag = 1 / offset = 185(1480/8)
- length: 1040(1020 data field) / ID = x / fragflag = 0 / offset = 370
IP addressing
ip address: 32-bit
interface: host/router와 physical link 사이의 connection
router: multiple interface
Subnets
높은 주소 비트: subnet part
낮은 주소 비트: host part
ex: 233.1.1.0/24 (subnet mask: /24): 총 24비트(233.1.1)이 서브넷
IP addressing: classful addressing
- IP주소는 8, 16, 24비트 단위로 쪼개짐
classful addressing 문제
- class C(/24)를 보면 2^8 - 2 = 254개의 호스트만 사용가능 (기업에선 매우 작은 숫자)
- 그렇다고 class B(/16)을 사용하면 65,634개로 너무 많음
IP addressing: CIDR
CIDR: Classless Inter Domain Routing
서브넷 임의의 길이
address format: a.b.c.d/x, x는 서브넷을 의미하는 비트의 길이
Broadcasting address: 255.255.255.255
IP addresses: how to get one?
- hard-coded by system admin in a file
- DHCP(Dynamic Host Configuration Protocol): 동적으로 서버에서 주소를 가져옴
- plug and play
DHCP client-server scenario
- DHCP discover: client broadcast로 DHCP 서버가 있는지 물어봄
- DHCP offer: DHCP 서버가 broadcast해줌
- yiaddrr: your Internet address (너가 쓸 인터넷 주소)
- DHCP request: yiaddrr 사용하겠다고 broadcast 해줌
- DHCP ACK: 사용해도된다 허락해줌
ISP: Internet Service Provide
- ISP’s block: 200.23.16.0/20
- Organization 0: 200.23.16.0/23
- Organization 1: 200.23.18.0/23
- …
- Organization 7: 200.23.30.0/23
Q: ISP는 어떻게 address를 가져오나?
A: ICANN: Internet Corportaion for Assigned Names and Numbers
NAT: network address translation
- local network에서 내부 서브넷으로 통신(10.0.0/24)
- 외부로 나갈때는 외부에서 쓸 수 있는 주소로 바꿔줌 (138.76.29.7)
- 반대도 수행
용어 정리:
공인 IP 주소 (public IP address)
- 전 세계적으로 고유한 주소 (예: 서울시 동작구 상도동 정보과학관 102호)
사설 IP 주소 (private IP address)
- 주소가 고유하지 않음 (예: 624호)
- 사용 예:
- 공유기에 공인 IP 할당 후, 공유기에 연결된 다수의 컴퓨터에 사설 IP 할당
공인 IP와 사설 IP를 변환해주는것: NAT
NAT: network address translation
- 사설 네트워크를 구축하면 특정 IP range를 ISP로부터 사올 필요 없음
- 모든 device에 하나의 IP
- 내부 사설 IP가 바뀌어도 외부에 통보필요x
- 내부 IP를 바꾸지 않고 ISP 변경 가능
- 외부에는 고정IP주소만 공개되기 때문에 보안적으로도 좋음
NAT implementation(구현)
- source: 자신의 사설IP와 임의의 PORT NUMBER
- NAT tranlation table 에 기록후 source change
- destination에서 도착하면 table을 보고 맞는 destination으로 보내줌
IPv6
motivation (동기)
- 32비트 공간은 결국 부족해질것이다.
- IPv4의 format header에서 쓸모없는게 너무 많음 speed 증가시키기 위해
- QoS(Quality of Service)를 증가시키기 위해
IPv6 datagram format
- Traffic class: datagram의 priority(우선순위)를 주기위한 field
- Flow Label: datagram의 flow가 같은 flow 인지 identify(식별)
- flow 개념이 정확하게 정의되지 않았음
- Next header: upper layer protocol의 정보를 기입할때 사용(tcp/udp)
IPv4 비교
- Checksum: 속도를 올리기 위해 빠짐
- Options: 필요하면 “Next header” 활용
- ICMPv6: new version of ICMP
- 새로운 메시지 타입, e.g. “Packet Too Big”
- MTU가 지원하지 않는 패킷이 도착하면, 버리고 다시 작게 보내라함
Transition from IPv4 to IPv6
모든 라우터가 동시에 업그레이드 할 수 없음
- “flag days”가 없음
tunneling: IPv4 dataram payload에 IPv6 datagram을 담는다.
Network-layer functions
two network layer functions:
- Forwarding: 라우터의 input에서 패킷을 라우터의 output으로 옮기는 역할
Data Plane
- Routing: 전체 경로 결정 source to destination
Control Plane
two approaches to structuring network control plane:
라우터마다 컨트롤(traditional)
중앙기관에서 컨트롤(Software defined networking)
Routing protocol
- Routing protocol goal: “good” paths 결정
Graph abstraction of the network
Graph: G = (N,E)
N = set of routers = {u,v,w,x,y,z}
E = set of links = {(u,v), (u,x), (v,x) …}
c(x, x’) = cost of link(x, x’)
- cost는 bandwidth와 역관계
- congestion와 역관계
cost of path(x1, x2, x3, …, xp)
- c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Key question: u에서 z까지 얼마나 적은 코스트를 사용하여 이동할 수 있는가?
Routing alogrithm: source에서 destination까지 얼마나 효율적으로 보낼 수 있는가
Routing algorithm classification
Global or Decentralized information
Global:
- 모든 라우터들이 완벽한 topology에 대한 정보, link cost info 가짐
- “link state” algorithm
Decentralized:
- router는 물리적으로 연결된 이웃의 link cost만 알고 routing 진행
- “distance vector” 알고리즘
static or dynamic
- static: 라우팅 알고리즘의 경로가 거의 변하지 않음
- dynamic: 라우팅 알고리즘의 경로가 자주 바뀜, 빠르게 변경
link-state routing algorithm
- 다익스트라 알고리즘
- 모든 네트워크 노드들의 edge에 대해서 cost를 다 알고있음
- 각 라우터들이 자신과 관련된 “link state broadcast”를함
- 모든 노드가 같은 정보를 가짐
- source에서부터 모든 경로에대한 최소 path을 구할 수 있음
- forwarding table에 반영
- 모든 네트워크 노드들의 edge에 대해서 cost를 다 알고있음
Dijkstra’s algorithm discussion
Algorithm complexity: n nodes
- 최대 O(n^2), 최적화해도 O(n log n)
Oscillations possible:
- 최적화된 경로가 계속 바뀌면서 무한루프 될 수 있음.
Distance vector algorithm
- Bellman-Ford equation
dx(y) := cost of least-cost path from x to y
then dx(y) = minv{c(x,v) + dv(y)}
- v: x의 모든 이웃 노드
- c(x,v): 이웃노드 v로 가는 코스트
- dv(y): v에서 y까지 최소 거리
결국 이웃노드를 계속 탐색하면서 최소 경로를 찾아감
Dx(y) = x에서 y까지 가는 최소 코스트로 추정되는 값
- x는 distance vector값을 유지 Dx = [Dx(y): y in N]
node x:
- 이웃노드의 코스트를 알고있음 v: c(x, v)
- v로부터 받은 추정값도 알고있음 Dv
key idea: 이웃노드들의 도움을 받아서 계산
- Dx(y) = minv{c(x,v) + Dv(y)} for each node y in N
Distance vector algorithm 사용될때:
- link cost 변경
- 주변 노드 Dv값 변경
Distributed(분배):
- 자신의 Dv가 변할 때 각 이웃노드들에게 알려줌
동작구조 - 각각의 노드들:
loop
- wait for (이웃노드들이나 local link cost값이 변경되었을때)
- recompute (다시계산)
- 이웃들에게 Dv가 변경되면 알려줌
Distance vector algorithm: link cost changes
- 노드에서 local link cost가 바뀐걸 알아챔
- routing info를 updates, distance vector 다시 계산
- 만약 Dv 가 바뀌면, 이웃에게 알림
“good news travels fast”
t0: y가 link-cost 변경된걸 확인, Dv 업데이트, 이웃에게 알림
t1: z는 그값을 y로부터 받음, 테비을 업데이트, z to x로 가는 최소값을 변경, 이웃에게 Dv 전달
t2: y는 z의 업데이트값 전달받음, distance table 수정, 변경되는점은 없음
bad news travels slow - “무한반복” 문제
link cost가 업데이트된걸 다른 노드들은 모르고 있기 때문에 생김
결국 -> 많이 반복해야함 -> inf problem
Distance vector algorithm: poisoned reverse
- If Z가 Y를 통해 X로 패킷을 라우팅할 때: Z로부터 X까지의 경로는 INF로 설정
- 하지만 단편적인 해결책
- INF problem 해결 못함
Link State vs Distance Vector
Message complexity
- LS: N nodes, E links, O(N*E) msg sent
- DV: 이웃노드끼리만 교환
- Convergence time varies
Speed of convergence(수렴 속도)
- LS: O(N^2) 알고리즘 O(N * E) 메시지
- 진동이 있을 수 있음
- DV: 제각각
- routing loops
- count-to-infinity problem
- LS: O(N^2) 알고리즘 O(N * E) 메시지
Roubustness(견고성)
- LS: 각자 계산하기 때문에 실수하면 자신의 포워딩 테이블만 에러
- DS: 이웃노드에게 잘못 계산된 Dv를 알려주면 에러가 번식함
Intea-AS routing in the Internet: OSPF
Making routing scalable (라우팅을 확장가능하게 만듬)
- 지금까지 배운 라우팅 - 이상적임
- 모든 라우터가 동일
- 네트워크가 “flat”
Scale: 많은 destinations
지구상의 모든 destination을 가지고 routing table을 만들 수 없음
communication cost도 무한 함
Administrative autonomy (관리 자동화)
- 각각의 노드들의 routing을 자동화
- 자신의 네트워크를 컨트롤할 수 있어야함
scalable routing에대한 Internet approach
- Autonomous systems(AS): 라우터를 하나의 지역으로 모은것 (a.k.a. “domains”)
Intra-AS routing - 하나의 도메인 내에서 라우팅
- 같은 지역의 호스트, 라우터 간의 라우팅 지원
- 모든 한 지역에 있는 라우터들은 같은 intra-domain protocol 구동
- 다른 AS에 있는 ㄹ라우터들은 다른 intra-doamin routing protocol 돌릴 수 있음
- Gateway router: AS의 edge, 인프라들이 다른곳과 통신할 때 거쳐가는 라우터
Inter-AS routing
- 도매인간의 통신을 지원
- Gateway가 inter-domain routing 지원
Interconnected ASes
- Forwarding table = Intra-AS Routing algorithm + Inter-AS Routing algorithm
- intra-AS: 하나의 AS 안에서 destinations 결정
- inter-AS & intra-AS: AS 밖에 있는 destinatons 결정
Inter-AS tasks
gateway router에서 Inter-AS 업무 수행
AS2와 AS3를 어떤 데스크로 연결할 수 있는지
어디로 가야하는지 AS1의 모든 라우터에 전달
Inter-AS Routing
interior gateway protocols (IGP)
주로 사용되는 intea-AS routing protocols:
- RIP: Routing Information Protocol
- OSPF: Open Shortest Path First
- IS-IS (Intermediate System to Intermediate System) protocol: OSPF랑 유사
- IGRP: Interior Gateway Routing Protocols (Cisco에서 2016까지 사적으로 사용)
OSPF (Open Shortest Path First)
표준: publicly available
- link-state algorithm 기반
- link state packet을 뿌려야함
- 각 노드에 topology map을 만들 수 있어야함
- 라우터에서 다익스트라 알고리즘 구현
OSPF를 돌리는 라우터들은 항상 AS의 모든 라우터들에게 link-state를 광고해야함
IS-IS routing protocol: 다익스트라기반, OSPF랑 유사
Large domains 에서는 Hierarchical(계층적) OSPF
two-level hierarchy: local area, backbone
- area 내에서만 link-state advertisement를 해줌
- 각각의 노드들은 detailed한 area topology를 알고있음; 다른 도메인으로 이동하는 경로를 알고있음
Area border routers: 자신의 area에 있는 네트워크들의 정보를 취합해서 다른 area border routers에게 advertise해줌
Backbone routers: Backbone router들 끼리 OSPF 라우팅을 할 수 있음
Boundary routers: 다른 AS 시스템이랑 연결
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): inter-domain routing에서 사용하는 표준과 같은 형태
- 이것을 통해 인터넷의 모든 노드들이 데이터를 주고 받음
BGT는 AS에게 2가지 규격 제안:
- eBGP (External BGP): AS간의 메시지 교환
- iBGP (Internal BGP): 하나의 AS안에 있는 routers끼리 메시지 교환
BGP는 특정 subnet에 자신의 존재를 알려주는 protocol
BGP basics
- BGP session: TCP connection을 통해서 BGP messages 교환
- 다른 지역에 있는 network 들에게 자신의 존재를 알리는 역할 (path vector)
Path attributes & BGP routes
어떤식으로 BGP가 자신을 홍보할까
prefix + attributes = “route”
prefix: CIDRized prefixes(subnet)- E.g. 138.16.68/22
two important attributes:
- AS-PATH: 전체 경로를 나타냄
- NEXT-HOP: 옆에 어떤 AS가 있는지 나타냄
Policy-based routing:
- Policy에 의하여 경로 결정
BGP messages
- TCP connection을 통해서 데이터를 주고받음
- BGP messages:
- OPEN: BGP peer을 remote하는 TCP connection 오픈
- UPDATE: 새로운 path를 광고
- KEEPALIVE: 업데이트가 없을때 연결 유지
- NOTIFICATION: 이전 msg에 오류 보고, connection을 닫을때도 사용
BGP route selection
- 라우터들은 destination AS에 대한 하나 이상의 경로를 학습
- 선택 기준:
- local 기본 설정 값 속성: 정책 결정
- shortest AS-PATH
- closest NEXT-HOP router: hot potato routing
- 추가 기준
Hot Potato Routing
- intra-domain에서 비용이 가장 적은 local gateway 선택
Why different Intra-, Inter-AS routing?
Policy:
- inter-AS: admin은 traffic을 cotrol하고 싶고, 누가 들어오는지 조절하기 때문에 중요
- intra-AS: single admin이므로 별로 중요하지 않음
Scale:
- hierarchical routing을 사용, traffic을 줄임
Performance:
- intra-AS: performance에 focus 할 수 있음
- inter-AS: 성능보단 policy가 더 중요