2020년 12월 15일 화요일

Computer Network - Network Layer

개요

    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 가 성능보다 중요함

                         

List