개요
Data Plane
각 라우터에서 forwarding datagrams from input link to output link
Control Plane
Data Plane 이 end-to-end 로 전달 되도록 Control, including Routing
SDN(Software Defined Networking)
옛날에는 위 두개가 라우터에 같이 구현되어 있었음.
Router 는 Forwarding 만 하고, 물리적으로 떨어진 Controller 가 후자를 챙김
Network Service Model
Guaranteed Delivery, Bounded Delay, In-order Packet,
Minimal Bandwidth(이거보다 적은 데이터면 한방에 감),
Security( Src->암호화->Network->복호화->Dest ) 등
Internet is Best-Effort-Service
No Guaranteed Delivery, Bounded Delay, In-order Packet, Minimal Bandwidth.
Packet Switch in Network Layer is Route, in Link Layer is Switch
Forwarding
Packets at a Router's Input Port => the Appropriate Output Link Port
매우 빠르며 Hardware 단위에서 처리됨
구성
Input Ports
Line Termination Function - Terminate Incoming Physical Links
Link Layer Processing Function - needed to interoperate with the Link Layer
Lookup Function
Forwarding Table 에 Header Filed Value 를 Indexing, Output Port 얻음
Copy 본을 쓰므로 Centralized Processing Bottleneck 을 없앰. 지역적.
Longest Prefix Matching Rule
IP 의 Prefix 가 여러 Index 에 곂칠 때 가장 긴걸 사용
하드웨어적으로 Lookup 알고리즘이 구현된 TCAMs 를 사용( 1 clock )
Forwarding to Switching Fabric
Destination Based Forwarding
오로지 도착 IP 주소만 가지고
Generalized Forwarding
Dest IP Address 이외의 정보도 활용
Queueing
if arrive faster than Forwarding rate into Switching Fabric
Input Buffer Overflow 로 데이터가 사라질 수 있음.
HOL Blocking (Head-of-the-line Blocking)
목표 Output Port 는 비워져 있는데 Queue 에서 대기타는 현상
Other Functions
Packet's version number, checksum, time-to-alive-field Checking Function
Counters Update Function ( count IP Datagrams for Network Management)
Switching Fabric
Input Ports, Output Ports 연결용
Switching Via Memory
CPU 를 사용해 Input Port -> Memory -> Lookup -> Output Port 로
최신으론 Input Card 에서 Lookup, storing dest 까지 하고 Memory 로
Memory Bandwidth / 2 의 속도로 제한이 됨
Switching Via Bus
shared bus 를 사용해 직접 복사함 = 1번 복사.
switch-internal label 을 붙여서 모든 output ports 에 보냄.
label 이 맞는거만 남고 나머진 제거. 후 label 삭제.
얘도 한번에 하나만 보낼 수 있고 bus speed 속도에 제한됨.
Switching Via CrossBar
Input 수만큼 Bus 를 평행하게 만들고 Output 수만큼 그것과 교차되게 배치.
2*2 면 우물정자의 Bus 모양이 됨.
요청된 Input, Output Port 의 교차점만 On 시켜서 직접 복사.
사용중이 아닌 Bus 가 있으므로 그걸 요청할 땐 Non-Blocking
Switching Via Multiple Stage Fabric
Cross Bar 에서 각 교차점이 Stage 가 여러개면 동시에 여러개도 가능
Switching Via Parallel Switching Fabric
Packet 을 K 개로 나눠서 N 개의 병렬 Fabric 에 넣으면 더 빠름.
순서 등은 Output Port 의 Queuing Buffer 가 처리함.
Output Ports
Input Ports 에서 하는거 정 반대 순서로 함.
Queueing
Switching Fabric 이 여러 input 에서 온 것을 하나의 output 에 뿌릴 때 생김
Buffering ( 버퍼가 꽉 차면 )
Packet Discarding Policy
Drop-Tail, Priority, Random
Congestion Signal 을 주기위해 buffer 가 차기 이전의 것을 보내기
Active Queue Management(AQM) 의 대표 Random Early Detection(RED)
Packet Scheduling ( Queue 중 어떤거 선택 )
FIFO
Priority - FIFO highest queue of Multiple Class
Round Robin - queue of multiple class 를 돌려가면서 하나씩 if queued
WFQ(Weight Fair Queueing)
RR 처럼 돌아가면서 하는데 자기차례의 수행 비중이 다름
Transmission Rate * w_i/sum(w) Bandwidth 보장
버퍼크기 = RTT * Link_Capacity / root(number of TCP flow)
Packet's Header 의 일부 값을 이용해 Forwarding Table 에 Indexing
그러면 Output Line Interface 값나옴.
Block if malicious sending host, duplicated or multiple outgoing link.
Forwarding Table
Forwarding, Routing 의 사이임.
Routing Algorithms Function 이 Forwarding Table 의 내용물을 정하게 됨
IP
Version(4bit) 가 먼저 있고 다음들이 들어옴.
IPv4 Header = 20 bytes, TCP Header = 20bytes, UDP Header = 8 bytes
IPv4(32bits 단위)
첫번째 줄
Version(4bit)
Header Length(4bit) => Data 시작 주소
TOS(Type of Service)(8bit) => data 의 사용용도로 Router 의 Policy 결정 등
Datagram Length(16bit)
Header 포함 총 패킷 길이. 16bit 라 최대 65.535 bytes
Ethernet Frame 의 payload field 크기로 보동은 1500bytes 이하라 충분함
두번째 줄
Fragmentation 용. IPv6 엔 없음
MTU(Maximum Transmission Unit) of Link Layer 는 제각각임
Ethernet(1500bytes), WIFI(2304bytes) 등 보다 작은경우 쪼개는거
Router 는 쪼개기만 하고, 재조립은 End System 의 몫임
Payload 가 쪼개지는 거고 헤더길이도 고려해서 길이를 나눔.
Identifier (16bit)
Src IP Address 가 다르면 Identifier 로 구분함 ( Host 에서 같이 찍어줌 )
Flags (3bit) => 마지막이면 Flag = 0, 아니면 Flag 1,
Fragment Offset (3bit)
정렬 및 손실된 조각 판별용.
Payload 를 8bytes 단위로 표기함.
payload 1480 bytes => offset 185
세번째 줄
TTL(Time to Live)(8bit)
Router 거칠 때마다 1씩 줄어서 0 되면 Drop 함.
Network 에서 계속 순환하는 것 막음
Upper Layer Protocol (8bit)
6 이면 TCP, 17 이면 UDP.
Transport Layer 와 Network Layer 을 잇는 역할
Header Checksum (16bit)
Header 를 16bits 씩 묶어서 더한 후 보수처리함.
TTL 때문에 계속 업데이트 되어야 함.
TCP/UDP 는 패킷 전체를 체크한다는 점이 차이.
Source IP Address (32bit)
Interface
Router 에 연결된 각각의 Link 마다 다른 주소가 필요함.
Host 도 연결된 Link(Ethernet, WIFI, ..) 마다 다른 주소가 필요함
=> Host/Link, Router/Link 의 Interface 마다 IP 가 부여됨
Subnet
Router 를 거치지 않고 연결된 Interface 의 그룹
CIDR(Classless Interdomain Routing)
a.b.c.d/x 로 앞의 x bit 는 Subnet Part(Prefix), 나머지는 Host Part
ISP 마다 Subnet Mask 인 x 는 ICANN 의 관리하에 임의적으로 부여됨
ICANN => Allocate IP Address, Manage DNS, Resolve DNS
내부에서는 Host Part 도 고려되지만 외부에서는 Subnet Part 만 보고 길찾.
Host Part 가 다시 Subnet/Host Part 로 쪼개질 수도 있음
x 가 점점 커지는 거임 => Longest Prefix Matching 하면 ISP 내부가 됨
Class Based Addressing
x 가 8(Class A), 16(Class B), 24(Class C) 로 고정됨.
회사마다 특정 Prefix 를 사는데 Class B 이상부터는 너무 많음(2^16개-2)
DHCP (Dynamic Host Configuration Protocol)
Host 가 Subnet 에서 IP 를 가지는 방법으로 Plug and Play 방식이다.
사용할 때만 IP 가 부여되며, 유한한 IP 주소로 여러 사람들을 서포트 가능
이를 위해서 Subnet 마다 DHCP Server 가 있음
Client and Server Protocol 로 UDP Port 67(Client), 68(Server)
단계
Client's DHCP Discover Message ( 옵션 )
Dest 255.255.255.255, Src 0,0,0,0 으로 Broadcast
Transaction ID 를 정해서 줌.
Server's DHCP Offer Message ( 옵션 )
Dest 255.255.255.255, Src myip 로ftBroadcast ( 옵션임)
받은 Transaction ID + DHCP Server ID + LifeTime
+ yiaddrr(Your Internet Address) + DNS Name/Address
+ Address of first hop router (Gateway)
Client's DHCP Request Message
여러 DHCP Offer Message 중에 원하는 걸 선택.
거기에서 Src 를 0.0.0.0, 메시지 종류 바꾸고, Transaction ID 바꿈
Server's DHCP ACK Message
Offer Message 와 똑같은데 메시지 종류랑, Transaction ID 만 다름.
이후엔 주어진 IP Address 사용 가능
NAT(Network Address Translation)
NAT-Enable Router 가 하나의 Host 로서 Subnet 밖에선 보임.
안에선 정해진 IP Address (10.0.0.0/8, 172.16.0.0/20, 192.168.0.0/16) 사용
Subnet 안에서 밖으로 갈 땐 NAT-Translation Table 을 사용
Subnet 내의 주소+Port # <-> NAT-Enable Router 주소 + 특정 Port #
Port Number 는 16bits 라 60000 개 이상 가능
장점
Public Address 와 Private Address 가 독립적이라 보안, 유지 등에 도움
단점
하지만 Router 가 IP 를 건드므로 OSI 의 철학이 깨지고 복잡해짐.
특히 서버를 Private Address 로 하면 더 그럼.
Subnet 마다 FFFFF(Subnet Broadcast), 00000 은 IP 는 특정용도로 사용됨
Destination IP Address (32bit) => DNS Lookup 으로 찾은 결과도 여기에
Options (32bit * 15)
혹시 옵션이 Header 에 가변적으로 추가되면 검색시간이 늘어나니 추가.
IPv6 엔 없음
Time Stamp, Record Route Taken, Record Router to visit.
Payloads
TCP/UDP Segment, ICMP Message
IPv6(32bit 이나 IP 는 128bit)
특징
40 bytes 의 간단한 Header
Anycast 가능 ( Subnet 중 하나에게 보냄), Broadcast 없어짐.
No Fragmentation => ICMP error 를 보내고 drop 하는 걸로 바꿈
No CheckSum => Link, Transport Layer 에서도 하고, 계속 업뎃도 해야함(TTL)
첫번째 줄
Version(4bit) => 6 쓰면 됨
Traffic Class(8bit) => Priority
Flow Label(20bit) => Same Flow 로 Datagram 묶어 Priority 조정, 아직 미정임.
두번째 줄
Payload Length (16bit) => Header 제외 패킷 길이
Next Header => Upper Layer Protocol Indentifier + 구 Option
Hop Limit => TTL 과 같음
Source/Destination Address ( 16byte 각각 )
Routing ( Algorithms )
Network-Wide Process 로 end-to-end paths 를 결정함
비교적 느리며 Software 단위에서 처리함
하는일
Routing Tables, Link State Information 유지
Forwarding Table 계산, Routing Protocol 수행
Remote Controller 와 연결 ( SDN 의 경우)
종류
전통적 방법
각 Router 가 Routing Functionality 를 가짐
각 Routing Functionality 는 다른 Router 의 것들과 소통함
SDN
물리적으로 떨어져 있는 Remote Controller 가 있음
여러 Router 의 Flow Table 의 값을 Routing Algorithms 으로 계산함.
그 값을 메시지에 넣어서 CA(Local Agents) 에 전달함
Generalized Forwarding
Forwarding Table 은 이제 Flow Table 로 부름.
Pattern => IP 외의 다양한 헤더들 +
Actions => 보낼 Link Port# 외의 행동 패턴들. Drop/Forward/Modify ...
Priority => 혹시 Action 의 Pattern 이 겹칠 때 사용
Counter => Match 된 수, 최근에 Match 된 기간
주어진 Pattern 에 따라서 가능한 Action 이 다양해짐
NAT Boxes, Firewall, DPI(Redirect), Load-balancers 등의
Proliferation of MiddleBoxes 를 따로 할 필요가 없어짐.
방법
Shortest Path Routing Problem
Cost of Path 가 있어서 Min Hop Route 가 최적이 아닐 수도 있음.
Cost
Fixed => Link Length, Hop Count, Bandwidth, Propagation Delay ...
UnFixed => Traffic Expected, Queueing, DPI(Processing, Redirect), Error...
Preference
Bandwidth, Delay, Security
Graph Abstraction
용어
G = (N, A) = (Node, Arc or Edge)
Walk(n1, n2 ... n_n) = (n1, n2), (n2, n3) ... (n_n-1, n_n), 공집합 가능
Path = Walk without repeated node
Cycle = Walk Length >= 4, 처음과 끝이 같고 나머진 달라야함
Tree = Connected Graph without Cycle
Spanning Tree of G = Tree and Subgraph of G containing all the node in G
전제
모든 Connected Graph(N,A) 는 Spanning Tree 를 가진다.
|A| >= |N| - 1
G is tree iff |A| = |N| - 1
Cost of Path(x1, x2 .. x_n) = c(x1, x2) + c(x2, x3) ... + c(x_n-1, x_n)
Link State Algorithms (Dijkstra's Algorithms)
Global, Centralized, Static
All Router 의 정보를 가지고 행동
Link State Broadcast 로 All Node 가 같은 정보를 가짐
특징
N 개의 Node 와 E 개의 Edge 가 있으면 O(N*E) 의 메시지전송
O(n^2) 의 계산복잡도
single point failure 에 약함.
하지만 각 Node 가 보내는건 link cost 므로 전체에 영향이 가진 않음
Oscillations 의 가능성이 있음. 이건 안좋은거.
Distance Vector Algorithms (Bellman-Ford)
Decentralized, Dynamic
Router 들은 인접한것들의 정보가 계속 업데이트해서. 이걸 가지고 지역적 행동
특징
직접 연결된 노드들을 인식 및 Cost 계산
=> LS 에 비해 필요한 메시지량이 작음
직접 연결된 노드와 모든 도착지에 대한 Distance Vector 들을 받음
=> Distance Table. 여기에 기반해서 Routing Table 을 만듦
=> 위 결과를 다시 이웃노드에 전달
모든 노드가 같은 정보를 가지지 않으므로 Asynchronous Algorithms
Distance Vector 가 잘못 전달되면 Error Propagates 라고 전체에 영향이감.
Converge Time 이 다양함
Count to Infinity Problem
급격히 cost 가 늘어날 때 Converge 까지 시간이 매우 오래걸림
Routing Loop 가 일부 원인
Poisoned Reverse 로 해결
내가 정보를 주는 노드를 경유시 그 경로는 Cost 를 무한으로 처리함
실제 구현
단순한 알고지름과 실제의 차이
Scale
다 처리하면 용량, 복잡도가 너무 큼. DV 는 Converge 못할거임.
Administrative Autonomy
각 ISP 마다 자기가 원하는 Routing 가능해야함
근데 위는 모든 라우터가 같은 알고리즘 쓴다는 가정임
Autonomous System(AS)
같은 Administrative Control 아래의 라우터들
AS 끼리는 각 AS 안의 Gateway Router 가 소통함
Intra-AS Routing Protocol (Interior Gateway Protocol, IGP)
같은 AS 끼리는 Routing Algorithms 이 같음.
같은 AS 내의 모든 정보가 사용됨
RIP(Routing Information Control) - DV
OSPF(Open Shortest Path First) - LS
AS 전체의 Topology Map 을 각 라우터가 가짐.
각 라우터는 All Subnet + AS 내부의 목적지에 대해 Table 작성
AS의 모든 라우터에 Link State Advertisement 를 수정시/주기적으로 실시
IP 에서 Direct 로 진행됨.
그래서 OSPF 는 Reliable message transfer 등의 기능이 붙어있음
Security
승인된 Router 만 사용해서 정보탈취의 걱정이 작음
단순한 비번을 걸거나 MD5 Authentication 을 하거나 2개의 옵션
Multiple Same Cost Paths (RIP 는 아님)
Multiple Cost Metric Support ( Multiple Type of Service, ToS)
Multicast Extension ( 여러 Destination 가능)
Support Hierarchy within a Single AS
ISO 의 IS-IS Routing Protocol 과 거의 같음
IGRP(Interior Gateway Routing Protocol) - DV
Inter-AS Routing
AS -> Gateway1 -> AS -> Gateway2 ... 이렇게 안밖을 오가는 것.
AS 내부의 라우터마다 Outer AS 들로 가기위한 정보를 처리해야함
BGP (Border Gateway Protocol) 뿐임
Decentralized and Asynchronous Protocol => DV Algorithms
Advertises the Reachability Information for prefix x
new AS 내부의 모든 라우터에 자신의 AS 와 x 를 보냄.
iBGP session - semi-permanent TCP
Gateway Router 다른 AS Gateway Router 로 보냄.
eBGP session - semi-permanant TCP
이때 자신의 AS 도 같이 보내서 보내는게 Path 가 되게함.
그리고 보낼 때 쓴 Gateway IP 도 같이 보냄.
그럼 모든 AS 는 new AS 의 Prefix, 갈 수 있는 경로를 알게됨
NEXT-HOP(IP), AS-PATH, prefix => 이런형태
Policy-Based-Routing
Route Advertisement 를 받을 때 받을지/거부할지
Route Advertisement 를 보낼지/말지
Determine Good Route
Hot Potato Routing => Least Intra Domain Cost, Ignore Inter
Policy 가 성능보다 중요함