1. IP(Internet Protocol)

  • 네트워크 계층의 핵심 프로토콜
  • 전송계층에서 TCP 혹은 UDP 헤더를 붙여 만들어진 패킷에 IP 헤더를 붙여 IP 패킷을 생성
  • 패킷은 헤더에 명시된 IP 주소를 기반으로 목적지로 전송된다.
  • IP 자체는 비연결형 프로토콜이며 신뢰성있는 전송을 보장하지 않는다.(이는 전송계층에서 담당)

 

 

2. IP 헤더(IPv6)

출처:https://en.wikipedia.org/wiki/IPv4

  • Version
    • 현재 사용하는 IP의 버전

 

  • IHL(IP Header Length)
    • IP 헤더의 길이(데이터 포함 X)

 

  • TOS(Type of Service)
    • 서비스의 우선순위를 표시하기 위한 영역

 

  • Total Length
    • 데이터를 포함한 IP패킷 전체의 길이

 

  • Identification / Flags / Fragment Offset
    • 라우터의 전송가능한 최대 패킷 크기(MTU)가 IP 패킷보다 작아 패킷이 쪼개질 경우
      쪼개진 패킷을 다시 재조립하기 위해 필요한 정보를 저장하기 위한 영역

    • Identification(16bit) : 어느 패킷의 프래그먼트인지 나타내기 위한 영역

    • Flags(3bit) : 패킷 분할 정보를 나타내기 위한 영역. 예를들어 마지막 비트는 뒤에 다른 프래그먼트가
                       더 있는지 표시되기 위해 사용된다.

    • Offset(15bit) : 각 프래그먼트의 원본 데이터에서의 인덱스를 나타내는 영역

 

  • TTL(Time To Live)
    • 초기 설정한 값에서 포워딩을 거칠 때마다 1씩 감소
    • 패킷에 수명을 주어 무한루프에 빠진 패킷 등이 일정 횟수의 포워딩을 거치면 사라지도록 함

 

  • Protocol(Upper Layer)
    • 상위 계층에서 사용될 프로토콜을 명시(TCP/UDP 등)

 

  • Header Checksum
    • ip 헤더의 체크섬을 저장 - 최소한의 에러검출

 

  • Source/Destination IP Address
    • 출발지, 목적지 IP주소

 

  • Options
    • 추가적인 처리 옵션을 정의하기 위한 영역
    • 없을 수도 있으며 최대 40바이트까지 사용 가능

 

 

3. IP 주소

  • 8비트로 표현되는 정수 4개(32비트)로 표현되는 주소체계
    => IPv6의 경우 총 128비트로 주소를 표현한다. 즉, 2 ^ 128 개의 독립적인 주소를 표현할 수 있다.

 

  • IP 주소는 엄밀히 말해 특정 호스트를 가리키는 주소가 아닌 네트워크 인터페이스를 가리키는 주소
    => 라우터와 같이 다수의 인터페이스를 가지는(다수의 IP주소를 가지는) 장비도 존재한다.

 

  • IP의 분배
    • 단순히 IP 하나하나를 호스트에게 배분하는 방식을 사용할 경우 포워딩 테이블의 크기가 너무 커지며
      포워딩에 걸리는 시간도 너무 길어진다.
    • IP 계층화
      • Network ID 부분과 Host ID 부분을 분리
      • ex) 12.34.158.0/24
        • 상위 24비트(12.34.158) 까지는 네트워크 ID
        • 나머지 8비트(0) 까지는 호스트 ID
        • 같은 네트워크에 속하는 호스트들을 동일한 IP prefix로 묶을 수 있게 된다
          => 포워딩 테이블을 보다 간단하게 표현하여 효율적인 포워딩을 가능하게 한다.
        • 새 호스트에 IP주소를 할당하는 작업도 간단해짐
      • 과거에는 네트워크 ID를 부여받는 기관의 규모에 따라 네트워크 ID 비트수를 조정
        • A클래스 - 상위 8비트를 네트워크 ID로 사용
        • B클래스 - 상위 16비트를 네트워크 ID로 사용
        • C클래스 - 상위 24비트를 네트워크 ID로 사용
      • 현재는 서브네팅을 사용하여 유동적으로 prefix를 조절

    • 서브넷 마스크(Subnet Mask)
      • 네트워크 ID가 어디까지인지 컴퓨터가 이해할 수 있도록 표현하는 방식

      • ex) 125.23.87.0 이라는 네트워크 ID를 부여받았을 때, 각각 30개의 호스트를 가지는
        8개의 서브넷으로 분리하려면 네트워크 ID인 24비트까지의 서브넷마스크는 모두 1,
        그 이하로는 8개의 서브넷을 사용하기 위해 3개의 비트를 1로, 나머지를 0으로 하면
        0인 부분이 5비트가 되어 32개의 주소를 나타낼 수 있게된다. 

      • 만약 125.23.87.0 에 서브넷마스크가 255.255.255.192라면
        • 서브넷의 갯수는 최대 4개이다.
        • 각 서브넷의 호스트 범위는 0~63, 64~127, 128~191, 192~255 가 된다.
        • 이 중 세 번째 서브넷인 128~191 에서 대표주소는 125.23.87.128이며
          브로드캐스트 주소는 125.23.87.191이 된다.

  • NAT(Network Address Translation)
    • 20년 전에도 이미 IPv4가 지원하는 2 ^ 32 개의 주소만으론 부족할 것으로 예상하여
      IPv6를 만들었지만 정작 현재까지도 사용중인것은 여전히 IPv4 이다

    • IPv6로의 이전을 위해서는 기존에 사용하던 모든 네트워크 장비를 교체해야하는데,
      이는 아직까지는 현실적으로 어려움이 따름 

    • 결과적으로 IPv4를 그대로 사용하면서도 표현 가능한 주소의 갯수를 늘리기 위해
      NAT(Network Address Translation)를 사용

    • NAT의 방식
      • 로컬 네트워크에서 그 네트워크 내부에서만 유일성을 가지는 IP 주소를 분배

      • 네트워크 내부 호스트가 외부 호스트에게 데이터를 전송할 경우 내부 호스트의 IP주소를
        전 세계적으로도 유일한 게이트웨이 주소로 변경해주고 외부에서 내부의 호스트에게
        데이터를 전송할 경우 내부 IP주소로 변환하여 내부 호스트에게 전달해준다.

      • 기본적으로는 출발지 IP주소(게이트웨이 주소)와 도착지 IP주소를 통해 내부 IP를 특정하지만
        이 방식으로는 다수의 내부 호스트가 같은 목적지와 통신할 경우 구분이 불가능해진다.
        이를 해결하기 위해 추가적으로 포트를 구성하여 패킷을 구분하는 PAT 혹은 NAPT 방식을 사용한다.
      • NAT 테이블에 기록되는 것은 내부에서 패킷을 전송할 때이기 때문에 클라이언트로써는
        문제가 없지만 상대의 요청을 기다려야하는 서버로서는 정상적으로 동작하기 어렵다.
        NAT 테이블에 직접 변환정보를 기재하여 서버로서 동작할 수 있게 하는 방법도 있지만
        일반 사용자가 할 수 있는 작업은 아니다.

      • NAT의 또다른 문제는 계층화된 네트워크 구조를 어기고있다는 점이다. 네트워크 계층에서 동작하는
        장비인 NAT 라우터가 IP 패킷의 데이터부분(TCP헤더의 포트)을 인지하고 수정까지 하는 규칙위반을
        하고있다. (대부분의 사용자는 서버 역할을 할 경우가 없기 때문에 문제를 크게 인지하지 못한다.)

  • DHCP(Dynamic Host Configuration Protocol)
    • DHCP 서버가 네트워크에 연결된 호스트에게 자동으로 IP주소를 대여해주는 방식
    • 절차
      • DHCP 클라이언트는 네트워크에 연결하기 위해 네트워크 내에서 브로드캐스트(255.255.255.255)로
        DHCP 서버에게 IP 주소를 요청하는 패킷을 전송(discover)

      • DHCP 서버는 요청에 대한 응답으로 대여해줄 IP 주소를 담은 패킷을 전송(offer)

      • DHCP 클라이언트는 요청에 응답해준 DHCP 서버중 하나를 선택하여 해당 서버를 선택했음을 알리는
        패킷을 브로드캐스트로 전송한다.(request) 이 때, 브로드캐스트를 사용하는 이유는 선택받지 못한
        DHCP 서버가 자신의 요청을 더이상 신경 쓸 필요가 없도록 해주기 위해서이다.

      • 선택받은 DHCP 서버는 request 패킷에 대해 ack 패킷을 보내고 프로토콜이 완료된다.
        이후부터 클라이언트측은 대여받은 IP를 통해 통신이 가능해진다.
    • 이 과정을 통해 네트워크에 연결된 호스트는 자신과 연결된 DNS 서버와
      게이트웨이 라우터의 IP주소를 알게되고 이를 기반으로 포워딩 테이블을 생성하게 된다.

 

 

3. 라우터(Router)

  • 네트워크 계층의 핵심 장비
  • IP 패킷들은 출발지와 목적지 사이를 연결하는 다수의 라우터를 거쳐 전송된다.
  • 포워딩(Forwarding)
    • 라우터의 가장 기본적인 기능
    • 라우터가 가진 포워딩 테이블에 따라 목적지 주소에 매칭되는 방향으로 패킷을 전송
    • 목적지 주소 하나하나에 매칭되는 방향을 따로 관리하는 것을 비효율적
      => 엔트리를 주소의 범위 형태로 구성하여 목적지 주소와 가장 많이 일치하는 엔트리와 매칭

 

  • 라우팅(Routing)
    • 포워딩을 위한 포워딩 테이블을 생성하는 작업
    • 목적지 주소까지의 모든 경로 중 최적의 경로를 탐색
    • 라우팅 결과 만들어진 포워딩 테이블은 라우터의 입력 포트에 각각 저장되며 라우터에
      도착한 패킷들의 포워딩은 이를 이용하여 각 포트에서 병렬적으로 수행된다.

 

 

4. 라우팅 알고리즘

  • 연결 상태(Link State) 알고리즘
    • 라우터간의 연결 상태정보를 모든 라우터에 전달하여 최단경로를 탐색하는 알고리즘
    • 데이크스트라(Dijkstra)의 최단경로 알고리즘 사용
    • 라우팅 정보 변경될 경우에만 변경정보를 브로드캐스팅으로 전달
    • 최단경로를 구하기 위해 전체 링크의 상태를 알고있어야하기 때문에 추가적인 메모리가 필요

    • OSPF, IS-IS 등의 프로토콜이 이 알고리즘을 사용

    • 대규모 네트워크에 적합

  • 거리 벡터(Distance Vector) 알고리즘
    • 최단경로 탐색을 재귀적으로 수행
      => 브로드캐스팅이 아닌 이웃한 라우터와의 통신만으로 네트워크의 상태를 파악

    • 벨만 포드(Bellman-Ford Algorithm)의 최단경로 알고리즘 사용
    • 라우팅 정보 변경의 전달이 주기적으로 이루어짐
      • 즉각적으로 발생하지 않기 때문에 잘못된 정보로 경로를 계산하게 될 수 있음
      • 변화가 없어도 주기적으로 통신이 발생하기에 트래픽을 낭비

    • count to infinity 문제
      • 인접한 노드의 목적지까지의 거리를 토대로 목적지까지의 최단경로를 계산
      • 그런데 인접한 노드의 최단경로에 자기자신이 포함될경우 문제가 발생(역류)
      • 인접한 노드 x에 의존하는 최단경로값을 노드 x에 넘겨줄 때는 무한값을
        넘겨주는 것으로 역류를 미연에 방지할 수 있음

    • RIP, IGRP 등의 프로토콜이 이 알고리즘을 사용

    • 소규모 네트워크에 적합

 

 

5. AS(Autonomous System) - 자율시스템

  • 통일된 라우팅 프로토콜을 사용하고 동일한 관리자에 의해 관리되는 독립된 네트워크 영역
  • 해당 네트워크에 속한 라우터와 서브 네트워크들의 집합
  • 넓게 보면 ISP(Internet Service Provider)를 말하기도 한다.

  • 필요성
    • 전 세계의 라우터를 대상으로 라우팅 알고리즘을 실행하기에는 그 수가 너무 많음
    • 계층화를 통해 라우팅의 규모를 분할 - 보다 효율적인 라우팅
    • 라우팅 알고리즘을 AS별로 독립적으로 적용
    • AS 단위의 보안 유지
    • 고장 및 오류를 AS단위로 관리 가능
  • AS 라우팅 프로토콜
    • IGP(Interior Gateway Protocol)
      • AS 내부의 라우터간의 라우팅
      • RIP, IGRP, EIGRP, OSPF, IS-IS 등 일반적으로 말하는 라우팅 알고리즘은 IGP를 의미

    • EGP(Exterior Gateway Protocol)
      • 서로 다른 AS 간의 라우팅 
      • BGP(Border Gateway Protocol)
        • 서로 다른 AS간에 라우팅 경로를 설정하기 위해 AS 외곽의 라우터끼리 IP주소 정보를 교환
        • AS 내부의 독립정 정책을 사용하는 IGP와 달리 조직간에 합의된 정책을 따른다.

'CS > 네트워크' 카테고리의 다른 글

#9 Wireless Network & Mobile Network  (0) 2021.11.30
#8 Link Layer(Data Link Layer + Physical Layer)  (0) 2021.11.25
#6 Transport Layer  (0) 2021.11.16
#5 Application Layer 2 - HTTP  (0) 2021.11.01
#4 Socket Programming  (0) 2021.10.29

1. TCP(Transmission Control Protocol)

  • 전송계층(Transport Layer)의 연결 지향형 프로토콜
  • 두 호스트간에 통신을 위한 논리적 연결(가상회선)을 수립하여 통신
  • 3-way handshaking 으로 연결을 수립, 4-way handshaking으로 연결을 해제
  • 신뢰성있는 데이터 전송(Reliable Data Transfer)을 지원
  • 데이터의 순서유지 보장 
  • 흐름제어(수신측의 처리속도에 맞춰 전송속도 조절) 지원
  • 혼잡제어(망의 혼잡도에 따라 전송 패킷량 조절) 지원
  • 양방향(Full Duplex), 1:1(Point to Poin) 통신

 

 

2. UDP(User Datagram Protocol)와의 비교

  TCP UDP
신뢰성 보장 O X
순서 유지 O X
에러 검출 O O
흐름 제어 O X
혼잡 제어 O X
연결 과정 O X
통신 형태 1:1(Point to Point), 양방향(Full Duplex) 1:1, 1:N(Broadcast), N:M, 단방향(Simplex)
통신 단위 바이트 스트림(데이터 유실이 없기 때문) 데이터그램

 

 

3. 헤더

 ① UDP

  • Port(32bit)  : source(송신측) 포트와 dest(수신측) 포트 두 종류가 있으며 각각 16비트씩 차지

  • Segment Length(16bit) : 헤더를 포함한 UDP 세그먼트의 길이 정보

  • Checksum(16bit) : 전송 도중에 에러가 발생했는지 판단하기 위한 값.  UDP는 에러가 발생한 segment를 drop

 

  • Port(32bit) : source(송신측) 포트와 dest(수신측) 포트 두 종류가 있으며 각각 16비트씩 차지
  • Sequence Number(32bit) : 전송되는 데이터의 순서. 데이터의 순서 유지를 보장하기 위한 값
  • Acknowledgement Number(32bit) : 수신자가 받을 것으로 기대하는 다음 데이터의 시퀀스번호
  • Data Offset(= Header Length)(4bit) : 헤더가 아닌 데이터(본문)가 시작되는 위치. 단위는 word(=32bit)
    => 맨 마지막 필드인 Option의 경우 길이가 정해져있지 않기 때문에 이 필드가 필요하다.

  • Reserved(3bit) : 나중을 위해 예약된 필드. 현재는 그냥 0으로만 채워지는 상태
  • Flags(9bit) : 세그먼트의 속성을 표현하는 플래그
    • URG : Urgent Pointer 필드에 값이 채워져있음을 표시
    • ACK : Acknowledgement 필드에 값이 채워져있음을 표시. 이 플래그가 0이라면 해당 필드를 무시
    • PSH(Push) : 수신측에게 이 데이터를 최대한 빠르게 애플리케이션에 전달할 것을 요청.  
                       이 플래그가 0이라면 수신측은 버퍼가 채워질 때 까지 대기
    • RST(Reset) : 이미 연결이 확립된 상대에게 연결을 강제로 리셋해달라고 요청
    • SYN(Synchronized) : 상대방과 연결을 확립할 때 시퀀스 번호의 동기화를 맞추기 위한 세그먼트임을 표시
    • FIN(Finish) : 연결 종료 요청을 위한 세그먼트임을 표시
    • NS, CWR, ECE : 명시적 혼잡 통보(ECN)를 위한 플래그.  혼잡 제어 기능의 향상을 위한 플래그
  • Window Size(16bit) : 한번에 전송 가능한 데이터의 양을 의미. 즉, 윈도우의 최대 크기는 (2^16 - 1) 바이트
  • Checksum(16bit) : 데이터 송신중 에러가 발생했는지 검출하기 위한 값. 에러 발생시 재전송을 요청하기 위함
  • Urgent Pointer(16bit) : 긴급 포인터. URG 플래그가 1이라면 해당 포인터가 가리키는 데이터를 우선처리
  • Option(~40 bytes) : TCP의 기능 확장을 위해 사용되는 필드. TCP 헤더의 최대 길이가 60 bytes 이고 고정 필드의
                               길이가 도합 20 bytes 이기 때문에 Option 필드의 최대 길이는 40bytes가 된다.

 

 

4. 신뢰성 있는 데이터 전송(Reliable Data Transfer) / 데이터의 순서유지 보장

  • 송신측은 데이터 패킷을 전송한 뒤 타이머를 설정
  • 수신측이 데이터를 받으면 응답으로 다음에 받아야할 패킷의 시퀀스 넘버를 명시한 ACK을 전송
  • 이때, ACK를 보낼 때 응답 데이터를 보낼 가능성을 생각하여 수신 후 ACK을 보낼 때 까지 딜레이를 둔다.
  • 송신측이 ACK를 받으면 데이터가 정상적으로 전달된 것을 확인, ACK에 명시된 다음 패킷을 전송
  • ACK를 받지 못하고 타임아웃이 발생하면 데이터가 전달되지 않은것으로 간주, 데이터 패킷을 재전송

 

 

5. 흐름 제어(Flow Control)

 ① Stop and Wait

  • 하나의 패킷을 보낸 뒤 해당 패킷에 대한 ACK가 돌아오기까지 대기
  • 패킷 전송마다 ACK를 기다리는 방식으로는 패킷 전송 이후 응답이 돌아오기 까지의
    RTT(Round Trip Time)만큼 시간을 낭비

 

 ② Sliding Window

  • 지정된 갯수(윈도우 크기)만큼의 패킷은 하나하나 ACK를 기다리지 않고 전송하는 Pipeline 방식을
    사용하는 것으로 성능향상 가능 

 

 

6. Pipeline 방식을 사용할 때의 신뢰성 보장

 Pipelined 방식을 실제로 구현하려면 한번에 얼마만큼의 패킷을 연속적으로 보낼 것인지

오류가 발생한 패킷을 어떻게 재전송할 것인지를 생각해야한다.  이에 대한 두 가지 접근법에 대해 알아보자.

 ① Go Back N (GBN)

  • 사전에 윈도우(Window)의 크기를 임의로 정하여 윈도우의 크기만큼의 패킷을 연속으로 전송

  • 수신측은 대기하고있던 순서에 해당하는 패킷이 아니면 discard, 마지막으로 받은 패킷에 대한 ack를 전송
    => 여기서 ACK은 마지막으로 전달받은 패킷의 시퀀스넘버이다. 
         실제 TCP에서의 ACK는 GBN과는 달리 다음에 받아야할 패킷의 시퀀스넘버를 명시한다.

  • 유실된 패킷에 대한 ack가 오지 않아 timeout이 발생하면 윈도우의 시작 위치를 timeout이 발생한
    패킷으로 옮겨 윈도우의 크기만큼 재전송
  • 수신은 정상적으로 됐지만 ACK만 유실된 경우 다음 ACK만으로도 이전 패킷이 정상적으로 전송됐음을
    유추가능하기에 문제가 발생하지 않음

  • 중간에 하나의 패킷만 유실되도 해당 패킷부터 다시 윈도우의 크기만큼 패킷들을 재송신하는
    방식이기 때문에 그다지 효율적이지 못함

 

 ② Selective Repeat

  • 수신측이 유실된 현재 기다리는중인 패킷이 아니어도 정상적으로 수신한 패킷을 버퍼에 저장하고
    해당 패킷에 대한 ack를 전송

  • 송신측은 timeout이 발생하면 해당 패킷을 재송신하고 이후 정상적으로 전송된 패킷에 대한 ack를
    받더라도 timeout이 발생한 패킷들에 대한 ack가 도착하기 전까지는 윈도우를 이동하지 않으며
    새로운 패킷을 보내지도 않음

  • 수신측은 유실되었던 패킷을 수신하면 그동안 버퍼에 저장해두었던 다른 패킷들과 함께 정상적으로 패킷을
    처리하고 유실되었던 패킷에 대한 ack를 전송

  • 송신측은 timeout이 발생한 패킷에 대한 ack를 수신하면 윈도우를 이동하고 새로운 패킷을 전송
    이때, 미리 ack를 받아두었던 패킷들도 모두 스킵하여 윈도우를 이동한다.
  • GBN에 비해 효율적이지만 구현이 복잡함, 수신측에도 버퍼 필요

  • Selective Repeat 프로토콜의 딜레마
    • Sequence Number 의 범위가 윈도우의 크기만큼일 경우 재전송한 데이터와 정상적으로 보낸
      데이터를 수신측이 구분할 수 없게 되는 경우가 발생할 수 있음

    • Sequence Number 의 범위를 더 넓혀야함 - 얼마만큼 넓혀야하는가
      => 윈도우 크기의 2배가량이 Sequence Number의 범위를 최소화하면서 문제를 해결할 수 있다.
  • 실제 TCP는 윈도우 크기가 매우 크기때문에 모든 패킷에 일일히 타이머를 설정하는 것은 비현실적
    => GBN을 기반으로 조금 더 개선된 방식을 사용

 

 

7. 혼잡 제어(Congestion Control)

  • 패킷이 전송되는 과정에서 네트워크가 혼잡상태에 빠질 경우 이를 감지, 패킷 전송량을 조절
  • TCP의 경우 패킷의 유실을 통해 혼잡을 감지하고 혼잡 제어에 들어간다.

 ① AIMD(Additive Increase Multicative Decrease)

  • 합증가/곱감소 알고리즘
  • 처음에는 패킷을 주기마다 하나씩 보내는 것으로 시작
  • 패킷이 정상적으로 보내질 경우 주기마다 1씩 전송량을 증가
  • 윈도우 크기 증가여부는 이전에 윈도우 크기를 증가시킨 뒤 처음으로 보내진 패킷의 ACK로 판단한다.
  • 패킷전송에 실패하거나 timeout이 발생할 경우 윈도우 크기를 절반으로 감소
    => 단순 패킷 유실의 경우 일부 패킷을 제외한 다른 패킷의 ACK이 도달하기에 구분 가능
  • 초반에 패킷 전송량이 늘어나는데 너무 많은 시간이 걸림
  • 네트워크의 혼잡을 미리 감지하지 못하고 혼잡이 발생하고나서 비로소
    윈도우 크기를 절반으로 줄이는 방식

 

 ② Slow Start(Multicative Increase)

  • AIMD와 마찬가지로 처음에는 패킷을 하나 보내는 것으로 시작
  • 패킷이 정상적으로 보내질 경우 "모든 ACK마다" 1씩 전송량을 증가. 즉, 주기마다 윈도우 크기는 2배씩 증가
  • 혼잡이 감지될 경우 해당 시점에서의 윈도우 크기를 기억하고 윈도우 크기를 1로 초기화
  • 이후 혼잡이 감지된 시점의 윈도우 크기의 절반까지는 기존의 방식대로 주기마다 2배씩 증가
  • 절반 이후부터는 선형적으로 주기마다 1씩 증가시키는 방식을 사용
  • 초기 패킷 전송량을 빠르게 높여갈 수 있으며 한번 혼잡을 감지하고나면 AIMD보다 효율적인 혼잡제어가 가능 

 ③ Fast Retransmit - 패킷유실에 대한 대처

  • 수신측이 순서에 맞지 않는 패킷을 받았을 때도 ACK를 전송
  • 이 때, ACK 값으로 마지막으로 순서를 지켜 들어온 패킷의 다음 패킷의 시퀀스 넘버를 담아
    전송하는 것으로 송신측이 빠진 패킷만을 재전송하도록 할 수 있음
  • 또한 재전송이 발생한 것으로 네트워크 혼잡을 감지하여 윈도우 사이즈를 조절할 수 있음

 

 ④ Fast Recovery - Slow Start의 윈도우 크기 복구에 걸리는 시간 개선

  • 혼잡을 감지할 경우 윈도우 사이즈를 1로 줄이지 않고 반으로 줄이는 방식
  • 이 방식에서는 혼잡이 발생하기 전까지는 Slow Start 방식을, 발생한 후에는 AIMD방식을 사용하게된다.

 

7. Nagle 알고리즘 

if there is new data to send then
    if the window size ≥ MSS and available data is ≥ MSS then
        send complete MSS segment now
    else
        if there is unconfirmed data still in the pipe then
            enqueue data in the buffer until an acknowledge is received
        else
            send data immediately
        end if
    end if
end if

 

  • Pipelined Protocol에서 패킷 하나로 전송되는 데이터의 크기가 너무 작을 경우 데이터크기 대비 패킷량이
    너무 많아지는 오버헤드가 발생
  • 지정한 사이즈의 버퍼를 사용하여 이전에 보낸 패킷의 ack가 돌아오기 전까지 전송해야할 데이터는 버퍼에 저장

  • ack가 돌아오면 버퍼에 넣어둔 데이터를 하나의 패킷으로 전송
  • 이 방식을 사용할 경우 전송 속도는 느려지지만 전송되는 패킷의 수가 줄어들어 효율적인 통신이 가능하다.

  • 빠른 응답속도가 요구되는 시스템에서는 nagle을 사용하지 않는 것이 좋을 수 있다.

  • WAN 과 같이 규모가 크고 느린 네트워크 통신에서는 nagle을 사용하는 것이 효과적이다.

 

'CS > 네트워크' 카테고리의 다른 글

#8 Link Layer(Data Link Layer + Physical Layer)  (0) 2021.11.25
#7 Network Layer  (0) 2021.11.18
#5 Application Layer 2 - HTTP  (0) 2021.11.01
#4 Socket Programming  (0) 2021.10.29
#3 Application Layer 1 - 소켓(Socket)  (0) 2021.10.28

1. HTTP(HyperText Transfer Protocol)

  • HTML 등의 하이퍼미디어 문서를 전송하기 위한 프로토콜

  • 일반적으로 웹 브라우저와 웹 서버간의 통신을 위해 설계되었지만 다른 용도로 사용할 수도 있음

  • 주로 TCP를 사용(HTTP/3 부터는 UDP를 사용한다고 한다.)

 

 

2. HTTP의 특성

 ① 비연결성(Connectionsless)

  • HTTP 프로토콜은 서버가 클라이언트의 요청을받아 처리하고나면 연결을 유지하지 않고 해제해버림
  • 더 많은 클라이언트로부터 요청을 받기 위해 연결 유지에 드는 리소스를 절약하기 위함
  • 클라이언트의 요청에 대해 매번 새로운 연결을 수립하고 해제하는 오버헤드가 발생

  • KeepAlive 속성을 부여하여 주기적으로 상대의 상태를 묻는 패킷을 보내 반응이 있는동안은 연결을
    유지하도록 할 수 있지만 연결을 유지하기 위해 리소스를 사용하므로 주의해야함

 

 ② 무상태(Stateless)

  • HTTP 프로토콜의 비연결성으로 인해 서버는 클라이언트를 식별할 수 없는 상태

  • 서버가 클라이언트를 식별하려면 어딘가에 클라이언트의 정보를 저장해둘 필요가 있음
    1. 쿠키(Cookie)
      • 클라이언트측에 클라이언트의 정보를 저장
      • 정보가 클라이언트측에 저장되기 때문에 서버에 부담이 가진 않지만 보안이 취약
    2. 세션(Session)
      • 서버측에 클라이언트의 정보를 저장
      • 정보가 서버측에 저장되기 때문에 서버의 리소스를 차지하게되지만 보안면에서 쿠키보다 나음
      • 동시 접속자 수가 많아지면 서버 과부하의 원인이 될 수 있음
      • 세션 정보 또한 중간에 탈취당할 수 있기 때문에 보안면에서 여전히 불안요소가 있음
    3. 토큰(token)을 사용한 인증
      • 보호할 데이터를 토큰으로 치환(암호화)하여 원본데이터대신 토큰을 사용하는 방식
      • OAuth, JWT 등이 대표적

 

 

3. HTTP 응답 상태코드

 클라이언트의 요청에 대한 서버의 응답에 포함되는 요청의 처리 상태를 나타내는 메시지

 

  • 1XX : 요청 접수중, 처리중 등 서버의 상태를 나타내는 코드. 특수한 경우를 제외하면 거의 사용되지 않음

  • 2XX : 성공 코드. 요청이 성공적으로 접수/처리된 경우

  • 3XX : 리다이렉션 코드. 요청한 페이지가 새 위치로 이동했거나 마지막 요청 이후 변경이 없는 경우

  • 4XX : 요청 오류 코드. 클라이언트측의 문제(잘못된 주소, 허용되지 않은 방식 등)로 처리에 문제가 생긴 경우

  • 5XX : 서버 오류 코드. 서버측의 문제(미구현 기능, 불량 게이트웨이 등)로 처리에 문제가 생긴 경우

 

 

4. HTTP Method

 HTTP 프로토콜상에 정의된 요청의 방식

 

  • GET : 서버에게 리소스를 요청(조회)하기 위해 사용

  • HEAD : GET과 유사하지만 본문 없이 헤더만을 통해 정보를 획득하기 위해 사용

  • PUT : 서버가 요청에 따라 리소스를 생성하거나 수정해야하는 경우 사용

  • POST : 입력 데이터를 요청 본문에 넣어 서버에 전송하기 위해 사용

  • DELETE : 서버에 리소스 삭제를 요청하기 위해 사용
  • TRACE : 요청 패킷이 서버에 도착하는 사이 변조되는 등의 문제가 발생하는지 여부를 확인하기 위해 사용
  • OPTIONS : 서버에게 특정 리소스가 지원하는 메소드를 알아보기 위해 사용

 

 

5. RESTful API

 ① REST(Representational State Transfer)

  • HTTP 프로토콜을 개선해나가는 과정에서 이전 버전의 HTTP로 구축된 웹과의 호환성문제가 대두
  • 로이 필딩(Roy Fielding)은 이를 해결하기 위해 웹과 같은 분산 하이퍼미디어 시스템을 위한
    아키텍쳐 스타일인 REST를 만들어냄
  • 여기서 말하는 아키텍쳐 스타일이란 제약 조건의 집합과도 같은 의미로, REST 가 내세우는 모든
    제약 조건을 만족하여 시스템을 설계했을 때 비로소 REST 하다고 말할 수 있음

 ② REST 아키텍쳐의 6가지 제약조건

  1. 클라이언트-서버 구조
    • 유저 인터페이스를 데이터 저장소와 분리하는 것으로 여러 플랫폼에 대해 인터페이스의 이식성을 높임
    • 서버측의 컴포넌트를 단순화하는 것으로 확장성을 높임
    • 서버, 클라이언트측의 컴포넌트가 독립적으로 발전 가능해짐

  2. 무상태(Stateless)
    • 클라이언트의 어떤 컨텍스트도 서버에 저장되지 않으며 세션 상태 등은 전적으로 클라이언트측에 저장
    • 시스템의 가시성, 신뢰성, 확장성을 증가시키기 위함

  3. 캐시(Cache)
    • 서버의 응답 데이터는 암시적으로든 명시적으로든 캐싱 가능 여부가 정해져있어야 함
    • 클라이언트측은 캐싱 가능하다고 정해진 응답에 대해서는 그 데이터를 재사용할 권리를 가짐
    • 네트워크 효율성을 증가시키기 위함
  4. 통일된 인터페이스(Uniform Interface)
    • 컴포넌트간의 인터페이스를 통일하여 시스템의 전반적인 구조를 단순화하고 상호작용의 가시성 향상
    • 데이터가 어플리케이션이 원하는 상태가 아닌 표준화된 형식으로 전달되기 때문에 효율성이 떨어질 수 있음
    • 웹과 같은 대규모 하이퍼 미디어 데이터 전송을 위한 시스템에 최적화

  5. 계층화된 시스템(Layered System)
    • 시스템을 계층화하여 시스템 전체의 복잡성을 낮추고 각 계층의 서비스를 독립적으로 관리할 수 있도록 함
    • 중개자(Intermediaries)는 로드 밸런싱을 통해 서버의 부담을 낮추고 서버의 확장성을 높여줄 수 있음
    • 데이터 처리에 오버헤드와 지연이 발생하여 사용자의 체감 성능이 떨어질 수 있지만 공유 캐싱을 통해
      이를 상쇄할 수 있음

  6. Code-On-Demand(Optional)
    • 클라이언트가 서버로부터 애플릿이나 스크립트 등의 코드를 제공받아 기능을 확장할 수 있도록 함
    • 클라이언트측에 기본적으로 구현되어있어야할 기능의 수가 줄어들어 클라이언트가 단순화됨
    • 서버측에서 새로운 기능을 추가적으로 지원하기 편해져 확장성이 증가
    • 시스템의 가시성을 감소시킬 수 있는 제약이기에 필수적인 제약은 아님
    • 현재 웹 기준 자바 스크립트가 이에 해당

 

 ③ REST API - REST 규칙을 완벽하게 지키는 API

  • HTTP의 규칙에만 따라도 클라이언트-서버 구조, 무상태, 캐시, 계층화된 시스템, Code-On-Demand 등
    대부분의 REST 규칙은 잘 지켜짐

  • 단일 인터페이스(Uniform Interface)의 네 가지 제약조건 중 두 가지가 문제가 됨
    • 리소스의 식별(identification of resources)
      • URI를 사용함으로서 만족

    • 메시지를 통한 리소스의 조작(manipulation of resources through representations)
      • 단순히 메시지를 통해 자원을 조작할 수 있다면 만족
    • 자기 서술적 메시지(self-descriptive messages)
      • 메시지만으로 해당 요청을 어떻게 처리해야할지에 대한 충분한 정보를 포함해야함
      • 오늘날 대부분의 API가 지키지 못하는 규칙
      • 웹에서는 기본적으로 만족

    • 하이퍼링크를 통한 상태전이(hypermedia as the engine of application state - HATEOAS)
      • 애플리케이션의 상태 전이가 하이퍼미디어를 통해 이뤄짐
      • 웹에서는 기본적으로 만족

 

 ④ RESTful API - REST 스러운 API

  • 완벽한 REST API를 만들기는 현실적으로 어려움이 따름
  • 완벽하진 않더라도 가능한 선에서는 REST 규칙을 지키는 RESTful API를 구현할 수는 있음
  • URI 매핑이 깔끔해지고 메시지가 의미하는 바가 명확해진다는 장점을 가짐

 

 

6. HTTP 헤더

 ① 요청 라인(Request Line)

  • {HTTP 메소드} {요청 uri} HTTP/{HTTP 버전}  의 형태로 구성

 

 ② 공통 헤더(General Headers)

  • Date : 메시지가 발행된 날짜와 시간

  • Connection : 현재 전송 이후 연결의 유지여부(Keep-Alive / close)
    => HTTP /1.1 에서 주로 사용 (HTTP /2 이후로는 사용불가)

  • Content-Length : 본문의 크기를 바이트단위로 표시

  • Content-Type : 컨텐츠 타입(MIME)과 인코딩을 명시할 수 있음

  • Content-Language : 사용자의 언어

  • Content-Encoding : 컨텐츠의 압축 인코딩(br, gzip, deflate, compress, identity 등).

  • Cache-Control : 요청과 응답 내의 캐싱 매커니즘을 위한 디렉티브를 정하는데 사용

 

 ③ 요청 헤더(Request Headers)

  • Host : 서버의 도메인 네임
  • User-Agent : 사용자가 요청을 보내는데 사용한 클라이언트(운영체제, 애플리케이션, 브라우저)
  • Accept : 클라이언트가 수용 가능한 미디어 타입(MIME)
  • Cookie : 웹 서버가 클라이언트에 저장해둔 쿠키 정보
  • Origin : 요청이 시작된 주소
  • If-Modified-since : 주어진 날짜 이후에 리소스가 변경되지 않았다면 요청을 제한
  • Authorization : 서버에게 인증 토큰을 보내기 위한 헤더. JWT 등을 사용한 인증에서 사용

 

 ④ 응답 헤더(Response Headers)

  • Server : 웹 서버의 정보

  • Access-Control-Allow-Origin : 서버가 허용하는 요청 시작 주소

  • Access-Control-Allow-Headers : 서버가 허용하는 헤더

  • Access-Control-Allow-Methods : 서버가 허용하는 메소드

  • Allow : 리소스가 지원하는 메소드 집합

  • Content-Diposition : 브라우저가 응답 본문을 표시할 방식(inline: 본문표시 / attachment : 다운로드)
    => attachment 의 경우 filename 옵션으로 파일명 지정도 가능

  • Location : 300번대 응답(리다이렉션)이나 201 Created 응답(리소스 생성)시 이동할 페이지 주소 명시

  • Content-Security-Policy : 컨텐츠 보안정책 명시(외부 컨텐츠를 가져올 경우)

 

 

'CS > 네트워크' 카테고리의 다른 글

#7 Network Layer  (0) 2021.11.18
#6 Transport Layer  (0) 2021.11.16
#4 Socket Programming  (0) 2021.10.29
#3 Application Layer 1 - 소켓(Socket)  (0) 2021.10.28
#2 OSI 7계층  (0) 2021.10.28

소켓 통신의 이해를 위해 Python으로 간단한 소켓 통신을 구현해본다.

 

1. 서버 측

from socket import socket, AF_INET, SOCK_STREAM
from threading import Thread

BUF_SIZ = 1024
user_list = dict()


# 수신 핸들러
def receive_handler(client_socket, user_name):
    # 클라이언트 소켓으로부터 메시지 수신대기
    while True:
        try:
            data = client_socket.recv(BUF_SIZ).decode()

        # 클라이언트와 연결이 끊어진 경우 반복 종료
        except:
            print(user_name, '와의 연결이 끊어졌습니다.')
            break

        # 클라이언트가 종료 명령어를 입력한 경우 반복 종료
        if data == '/종료':
            break

        # 유저명: 메시지 형태로 다이얼로그 생성
        dialog = f'{user_name}: {data}'

        # 자신과 연결된 다른 클라이언트들에게 메시지 출력
        print(dialog)
        for user in user_list:
            # 메시지를 보낸 유저에겐 출력하지 않음
            if user == user_name:
                continue
            user_list[user].sendall(dialog.encode())

    # 클라이언트 연결 종료
    # 유저 리스트에서 해당 유저 제거
    del user_list[user_name]

    # 자신과 연결된 다른 클라이언트들에게 해당 유저의 퇴장알림 메시지 출력
    msg = user_name+'님이 퇴장하셨습니다.'
    print(msg)
    for user in user_list:
        user_list[user].sendall(msg.encode())

    # 클라이언트 소켓 close
    client_socket.close()


if __name__ == '__main__':
    # 서버측 소켓 생성(socket)
    # 주소 체계와 소켓 타입을 입력하여 생성한다.
    # 인터넷 IPv4 주소체계를 사용하기 위해 AF_INET 을 사용
    # TCP 소켓을 사용하기 위해 SOCK_STREAM 을 사용
    server_socket = socket(AF_INET, SOCK_STREAM)

    # 바인딩에 성공할 때 까지 입력을 다시받음
    while True:
        try:
            print('HOST IP: ', end='')
            HOST = input()
            print('PORT: ', end='')
            PORT = int(input())

            # 연결할 서버의 주소, 포트를 입력하여 연결 요청
            server_socket.bind(('localhost', PORT))
            break
        except:
            continue

    # 수신 대기열 생성
    # 입력한 숫자만큼 대기열을 생성
    server_socket.listen(5)
    print('>> 채팅방 개설')

    # 무한루프
    while True:
        try:
            # 클라이언트로부터 로그인 요청을 대기
            connection_socket, addr = server_socket.accept()

            # 유저 등록
            user_name = connection_socket.recv(BUF_SIZ).decode()

            # 이미 존재하는 이름으로 로그인 시도시 재입력 요구
            while user_name in user_list:
                connection_socket.send('exist username'.encode())
                user_name = connection_socket.recv(BUF_SIZ).decode()

            # 로그인 성공시 성공메시지를 송신하고 유저리스트에 추가
            user_list[user_name] = connection_socket
            connection_socket.send('ok'.encode())

            # 클라이언트로부터 메시지를 수신하기 위한 스레드 실행
            receive_thread = Thread(target=receive_handler, args=(connection_socket, user_name))
            receive_thread.daemon = True
            receive_thread.start()

            # 해당 유저의 입장알림 메시지를 자신과 다른 연결된 클라이언트들에게 출력
            msg = user_name+'님이 입장하셨습니다.'
            print(msg)
            for user in user_list:
                user_list[user].sendall(msg.encode())

        # 서버 종료시 모든 클라이언트 소켓 close
        except KeyboardInterrupt:
            for user in user_list:
                user_list[user].close()

 

  • host 주소와 port 번호를 입력받아 채팅방 개설
     
  • 수신 대기열을 만들고 클라이언트로부터 연결요청을 대기

  • 연결요청이 들어오고 user_name이 전송되면 중복검사

  • 중복 user_name인 경우 재입력 요구

  • 중복되지 않는 user_name을 입력받을 경우 user_list에 user_name : connection_socket 의 형태로 저장

  • 해당 클라이언트로부터 메시지를 전송받기 위한 스레드를 daemon으로 생성
    => daemon 스레드는 메인 프로세스가 종료시 자신의 실행여부에 관계없이 종료된다.

  • 메시지 수신 핸들러는 클라이언트로부터 메시지를 전송받아 일반 메시지라면 유저명: 메시지 의 형태로
    포매팅하여 연결된 전 클라이언트에게 전송.  종료 명령어라면 해당 클라이언트의 소켓을 close 하고
    해당 클라이언트의 퇴장을 연결중인 전 클라이언트에게 알림

  • 해당 유저의 입장을 연결중인 전 클라이언트에게 알림

  • 서버 종료시 모든 클라이언트 소켓 close

 

 

2. 클라이언트 측

from socket import socket, AF_INET, SOCK_STREAM
from threading import Thread

BUF_SIZ = 1024


# 수신 핸들러
def receive_handler(client_socket):
    while True:
        try:
            data = client_socket.recv(BUF_SIZ)
            data = data.decode()
            print(data)
        except:
            print('연결 종료')
            break


# 송신 핸들러
def send_handler(client_socket):
    # 사용자가 '/종료' 를 입력하기 전까지 입력을 받아 서버에 전송
    while True:
        data = input()
        client_socket.sendall(data.encode())
        if data == '/종료':
            break
        
    # 소켓 close
    client_socket.close()


if __name__ == '__main__':
    # 클라이언트측 소켓 생성(socket)
    # 주소 체계와 소켓 타입을 입력하여 생성한다.
    # 인터넷 IPv4 주소체계를 사용하기 위해 AF_INET 을 사용
    # TCP 소켓을 사용하기 위해 SOCK_STREAM 을 사용
    client_socket = socket(AF_INET, SOCK_STREAM)

    # 연결에 성공할 때 까지 입력을 다시받음
    while True:
        try:
            print('HOST IP: ', end='')
            HOST = input()
            print('PORT: ', end='')
            PORT = int(input())

            # 연결할 서버의 주소, 포트를 입력하여 연결 요청
            client_socket.connect(('localhost', PORT))
            break
        except:
            continue

    # 로그인
    while True:
        print('USER_ID: ', end='')
        user = input()
        client_socket.send(user.encode())
        result = client_socket.recv(BUF_SIZ).decode()
        if result == 'ok':
            break
        else:
            print('이미 존재하는 유저명입니다.')

    # 로그인 성공시
    # 수신 대기 스레드
    receive_thread = Thread(target=receive_handler, args=(client_socket,))
    receive_thread.daemon = True
    receive_thread.start()

    # 송신 대기 스레드
    send_thread = Thread(target=send_handler, args=(client_socket,))
    send_thread.daemon = True
    send_thread.start()

    # 수신 대기 스레드의 종료를 대기
    # 송신 대기 스레드가 종료시 소켓이 닫혀 수신 대기 스레드도 자동종료
    # 수신 대기 스레드가 종료시 메인 프로세스가 종료되며 송신 대기 스레드도 자동종료
    receive_thread.join()
  • 서버의 host 주소와 port 번호를 입력받아 연결요청

  • 연결 성공시 유저명을 입력하여 채팅방 입장 시도

  • 중복되는 유저명일 경우 재입력

  • 입장 성공시 수신 대기 스레드와 송신 대기 스레드를 daemon으로 생성

  • 수신 대기 스레드는 서버와의 연결이 끊어지기 전까지 서버로부터 전송되는 메시지를 받아 출력

  • 송신 대기 스레드는 입력된 메시지를 서버에 전송 종료 명령어가 입력될 경우 반복문을 빠져나와 소켓을 close

 

'CS > 네트워크' 카테고리의 다른 글

#6 Transport Layer  (0) 2021.11.16
#5 Application Layer 2 - HTTP  (0) 2021.11.01
#3 Application Layer 1 - 소켓(Socket)  (0) 2021.10.28
#2 OSI 7계층  (0) 2021.10.28
#1 네트워크 구성 2 - Network Core  (0) 2021.10.28

1. 소켓(Socket)

 소켓은 응용 계층에서 프로세스간 통신을 쉽게 행하기 위한 창구의 역할을 한다. 사용자는 소켓이라는 형태로

통신할 대상과의 연결을 확립하고 소켓과의 송/수신으로 대상과의 송/수신을 하는 것과 마찬가지인 결과를

얻게된다. 즉, 소켓을 사용하는 법만 알면 하위 계층에 대한 지식이 없더라도 쉽게 통신이 가능해지는 것이다. 

서버와 클라이언트가 특정 port 를 통해 실시간 양방향 통신을 하는 방식이기에 실시간 통신이 필요한

스트리밍이나 채팅 등의 서비스에 사용된다.

 

2. 소켓의 종류

① 스트림(TCP 소켓)

출처: https://www.cs.dartmouth.edu/~campbell/cs60/socketprogramming.html

  • 서버측 흐름
    1. 소켓 생성(socket)
    2. 포트번호 설정(bind)
    3. 수신 대기열 생성(listen)
    4. 연결 대기(accept) - 연결 요청이 들어올 때 까지 block 상태
    5. 연결 요청이 들어오면 handshaking 과정을 거쳐 연결수립
    6. 이후 양방향 통신 가능
    7. 연결 종료 요청이 들어오면 종료과정을 거쳐 연결종료(close)

  • 클라이언트측 흐름
    1. 소켓 생성(socket)
    2. 연결 요청(connect) - handshaking 과정을 거쳐 연결수립
    3. 이후 양방향 통신 가능
    4. 통신 종료시 종료 요청(close) - 종료 과정을 거쳐 연결종료
                        
  • 연결 지향성 양방향 통신을 위한 소켓

  • 데이터를 스트림 형태로 전송하기에 데이터간의 경계가 없음

  • 데이터의 순서유지와 무결성 보장

  • 대량의 데이터를 안전하게 주고받기 위해 사용

 

② 데이터그램(UDP 소켓)

출처: https://www.cs.dartmouth.edu/~campbell/cs60/socketprogramming.html

  • 서버측 흐름
    1. 소켓 생성(socket)
    2. 포트번호 설정(bind)
    3. 요청 대기(recvfrom) - request 데이터그램을 수신할 때 까지 대기
    4. 요청이 들어오면 응답(sendto)

  • 클라이언트측 흐름
    1. 소켓 생성(socket)
    2. 요청(sendTo)
    3. 응답 대기(recvfrom)
    4. 통신 완료시 연결 종료(close)

  • 비연결형 통신을 위한 소켓

  • 한번의 전송으로 보낼 수 있는 데이터의 크기에 제한이 있다.

  • 데이터의 순서유지와 무결성을 보장하지 않음

  • 신뢰성보다는 속도가 중시되는 경우, 작은 데이터를 자주 보내야하는 경우 등에 사용(RTP 등)

 

'CS > 네트워크' 카테고리의 다른 글

#5 Application Layer 2 - HTTP  (0) 2021.11.01
#4 Socket Programming  (0) 2021.10.29
#2 OSI 7계층  (0) 2021.10.28
#1 네트워크 구성 2 - Network Core  (0) 2021.10.28
#0 네트워크의 구성 1 - Network Edge  (0) 2021.05.29

1. OSI 7계층(OSI 7 Layer)

OSI 7계층은 네트워크 프로토콜 디자인과 통신을 위와 같이 일곱 계층으로 나누어 표현하는 모델이다.

각 계층은 자신의 하위 계층이 제공하는 기능만을 사용하며 자신의 상위 계층에 기능을 제공한다.  

이러한 방식으로 네트워크를 구성함으로써 네트워크상에서 통신이 일어나는 흐름을 알아보기 쉽고

유지/보수 시에 문제가 발생한 기능에 해당하는 계층만을 수정하는 것으로 문제를 해결할 수 있게 된다.

 

 

2. 개요

 ① 물리 계층(Physical Layer)

  • 하드웨어 레벨에서의 데이터 전송이 발생하는 계층

  • 전기신호의 형태로 이진 데이터(Binary Data)가 전달된다.

  • 리피터, 허브, 케이블 등이 이 계층에 속하는 장비이다.

  • 데이터 단위는 bit 이다

 

 ② 데이터 링크 계층(Data Link Layer):

  • 직접 연결된 기기간에 물리 주소(MAC Address)를 통해 데이터를 전달하는 계층

  • 물리 계층에서의 전송중에 발생하는 오류를 검출하고 수정하는 기능과 흐름제어 기능 등을 제공한다

  • 스위치, 브릿지 등이 이 계층에 속하는 장비이다.

  • 데이터 단위는 frame 이다.

 

 ③ 네트워크 계층(Network Layer)

  • 데이터가 최종 목적지까지 최단경로로 도달할 수 있도록 패킷 포워딩(Packet Forwarding)을
    담당하는 계층

  • IP(Internet Protocol) 가 이 계층에 속하는 프로토콜이다. (IP 주소를 통해 데이터를 전달한다.)
  • 앞서 Network Core에 대한 설명을 했을 때 언급했던 라우터(Router)가 이 계층에 속하는 장비이다.

  • 라우터는 데이터가 목적지까지 도달하기 위한 최단경로를 계산하여 패킷을 전송한다. 이 때, 네트워크의
    상태를 파악하여 패킷 전송량을 조절하는 혼잡 제어(Congestion Control) 또한 수행한다.

  • 데이터 단위는 packet 이다.

 

 ④ 전송 계층(Tranport Layer)

  • 네트워크의 종단의 사용자간에 신뢰성있는 데이터 통신이 가능하도록 해주는 계층

  • Port 번호를 통해 데이터를 전달한다.
  • 프로토콜에 따라 오류 검출, 재전송, 흐름 제어, 중복 검사 등을 수행한다.
  • TCP / UDP 가 이 계층에 속하는 프로토콜이다.

  • 데이터 단위는 segment 이다.

 

 ⑤ 세션 계층(Session Layer)

  • 실제로 통신을 하기 위한 논리적인 연결 상태, 즉 세션(session)을 연결하는 계층

  • 세션을 연결, 관리, 종료하는 기능을 수행한다. 이러한 작업은 운영체제 레벨에서 수행된다.

 

 ⑥ 표현 계층(Presentation Layer)

  • 응용 계층에서 사용하는 표현 형식과 전송을 위한 공통적인 표현 형식 사이의 변환을 위한 계층

  • 전송받은 데이터를 응용 계층이 이해할 수 있는 형태로, 전송할 데이터를 전송을 위한 형태로 번역한다.
  • 파일의 확장자나 문서의 인코딩 등이 이에 속한다.

 

 ⑦ 응용 계층(Application Layer)

  • 전송할 데이터를 사용자에게 입력받거나 전송받은 데이터를 실제로 사용자에게 보여주는 계층
  • HTTP, FTP, SMTP 등이 이 계층에 속하는 프로토콜이다.
  • 위의 프로토콜을 처리하기 위한 응용 프로그램으로 브라우저 등이 있다.

 

 

실질적인 통신에는 OSI 7 계층 모델보다는 5, 6, 7 계층을 모두 묶어 응용 계층으로

분류하는 TCP/IP 5계층 모델을 사용하게된다.

'CS > 네트워크' 카테고리의 다른 글

#5 Application Layer 2 - HTTP  (0) 2021.11.01
#4 Socket Programming  (0) 2021.10.29
#3 Application Layer 1 - 소켓(Socket)  (0) 2021.10.28
#1 네트워크 구성 2 - Network Core  (0) 2021.10.28
#0 네트워크의 구성 1 - Network Edge  (0) 2021.05.29

네트워크의 종단 사이를 연결하는 부분. 라우터 등의 네트워크 종단 사이를 연결하는

중계기들이 여기에 속한다. 

1. Switching 

 ① 회선 교환 방식(Circuit Switching)

  • 송수신 단말 사이에 데이터를 전송할 때마다 전용 회선을 예약하여 데이터를 교환하는 방식

  • 회선 연결, 데이터 전송, 연결 해제의 3단계로 이루어진다

  • 대용량의 데이터, 연속적인 데이터를 빠르고 안정적으로 처리 가능 (팩스, 전화 등에 적합)

  • 회선 사용중에 다른 사용자는 해당 회선을 사용할 수 없음

 

 ② 패킷 교환 방식(Packet Switching)

  • 회선 교환 방식과 달리 두 단말 사이에 전용회선을 예약하지 않음

  • 전송할 데이터를 패킷(packet)의 형태로 묶어 전달한다.

  • 패킷에 들어있는 정보를 라우터(Router)가 처리하여 패킷이 전달되어야 할 목적 단말로
    최적의 경로를 계산하여 전송한다.  이 때 최적경로는 단순히 거리 뿐 아니라 망의 혼잡도,
    연결 상태 등 다양한 조건을 고려하여 계산된다.

  • 전용회선 예약이 없기에 망을 낭비하지 않음

  • 패킷에 에러 발생 시 패킷 내의 데이터를 통해 검출, 재송신 가능

  • 회선에 문제 발생 시 다른 경로를 즉각적으로 사용 가능

  • 최적경로 탐색을 위한 시간이 소요됨
  • 전송량이 증가할 경우 지연율이 급상승

  • 패킷에 추가되는 헤더로 인해 오버헤드 발생
  • 인터넷은 패킷 교환 방식을 사용

 

 

2. 패킷 교환 방식(Packet Switching)의 문제와 해결

 ① 패킷 지연(Packet Delay)

  • Node Processing Delay(노드 처리 지연) : 데이터 패킷 헤더의 처리, 비트 오류 검사 등에 걸리는 시간

  • Queing Delay(대기 지연) : 라우터의 처리속도보다 데이터 전송량이 클 경우 대기열에서 기다리는 시간

  • Transmission Delay(전송 지연) : 데이터의 첫 번째 비트가 전송된 후 마지막 비트가 전송되는 순간까지의 시간
    • R = 연결 대역폭(Link Bandwidth) - bps
    • L = 패킷 길이(Packet Length) - bits
    • Transmission Delay = L / R

  • Propagation Delay(전파 지연) : 데이터가 물리적인 회선을 통해 전달되는 데 걸리는 시간
    • d = 물리적인 회선의 길이(length of physical link)
    • s = 전파의 속도(~2*10^8 m/s)
    • Propagation Delay = d/s

 

  • 패킷 지연의 개선 방법
    • Node Processing Delay : 라우터의 성능 개선
    • Transmission Delay : 회선의 성능 개선(연결 대역폭 증가)
    • Queing Delay, Propagation Delay : 현재 시스템으로는 사실상 줄일 수 없음

 

 ② 패킷 유실(Packet Loss)

  • 대부분의 패킷 유실은 라우터의 대기열이 포화된 상태에서 새로운 패킷이 추가되어 발생

  • TCP를 사용한 통신의 경우 이러한 패킷 유실을 감지하여 송신 단말측에서 재전송하는 것으로 해결

  • 유실 직전의 라우터에서 재전송할 수 있다면 좋겠지만 라우터의 부하가 너무 커지기에 현실적으로 어려움

'CS > 네트워크' 카테고리의 다른 글

#5 Application Layer 2 - HTTP  (0) 2021.11.01
#4 Socket Programming  (0) 2021.10.29
#3 Application Layer 1 - 소켓(Socket)  (0) 2021.10.28
#2 OSI 7계층  (0) 2021.10.28
#0 네트워크의 구성 1 - Network Edge  (0) 2021.05.29

1. 해싱(Hashing)

해싱은 데이터를 키:값의 쌍으로 구성하여 배열에서 인덱스로 데이터를 참조하듯 키로 데이터에 바로 접근할 수 있도록 하기위해

고안된 방식이다.  해시 함수(Hash Function)를 사용하여 키 값을 특정한 길이의 해시값으로 변환하고 이 해시값에 해당하는

위치에 데이터를 저장하는 것으로 삽입, 삭제, 탐색에 O(1)에 가까운 성능을 보이도록 한다.  Python의 dictionary 나 Java의
HashMap, HashTable 과 같이 대부분의 언어에서 내장 라이브러리로 지원하며 굉장히 자주 사용되는 유용한 방식이다. 

 

 

2. 용어

  • 버킷(Bucket) : 해시 함수로 얻은 해시 값을 주소로 하는 저장 공간.  해시 방식은 미리 지정된 갯수만큼의 버킷을 만들어두고
                                  데이터를 저장해나간다. 

  • 슬롯(Slot) : 버킷이 데이터 하나를 저장하기 위해 사용하는 공간. 

  • 충돌(Collision) : 서로 다른 키 값에 대해 해시 함수로 얻은 해시 값이 서로 동일한 경우, 즉 같은 버킷에 다수의 데이터를
                                      저장해야하는 상황을 의미한다.
  • 클러스터링(Clustering) : 연속된 주소를 가진 버킷에 데이터가 밀집되는 현상을 의미한다.
  • 부하율(Load Factor) : 전체 버킷 중 사용중인 버킷의 비율을 의미한다. 

 

 

3. 해싱의 특징

  • 삽입, 삭제, 탐색에 평균적으로 O(1)의 성능을 보인다.

  • 해시 함수의 특성상 언젠가 충돌이 반드시 발생하며 그럴수록 성능이 저하되기 때문에 해시 함수가 얼마나
    충돌이 일어나지 않도록 해시 값을 생성하느냐에 따라 성능이 크게 좌우된다.

 

 

4. 충돌(Collision) 의 처리

 ① 체이닝(Chaining) 기법

  • 같은 해시 값을 가지는, 즉 같은 버킷에 저장해야할 데이터들을 연결 리스트의 형태로 이어붙이는 방식

  • 비교적 구현이 간단하고 연결리스트를 사용하기 때문에 슬롯 갯수의 제약이 없다.

  • 클러스터링에 영향을 거의 받지 않기 때문에 해시 함수를 선정할 때 충돌의 최소화만을 중점적으로 고려할 수 있다.

  • 충돌이 많이 발생할 경우 최악의 경우 O(N) 수준까지 성능이 저하될 수 있다.
     
  • 하나의 버킷의 슬롯 갯수가 일정 이상으로 늘어나면 연결 리스트 대신 이진 트리를 사용하여 검색효율을 높이기도 한다.

  • 부하율이 높아져도 성능 저하가 선형적으로 발생하기 때문에 높은 부하율이 예상될수록 개방주소기법에 비해 성능이 좋다.

  • 처음에 얻은 해시주소 내에서 문제를 해결하기 때문에 폐쇄 해싱(Closed Hashing)이라고도 한다.

 

 ② 개방주소(Open  Addressing) 기법

  • 충돌이 발생할 경우 다른 비어있는 버킷을 찾아 데이터를 삽입하는 방식

  • 체이닝 기법과 달리 추가적인 메모리나 외부 자료구조에서의 작업을 필요로하지 않는다.

  • 연결리스트나 트리 등 외부 자료구조를 사용하지 않기 때문에 삽입/삭제의 오버헤드가 적어 저장할 데이터가  적다면
    체이닝 기법보다 좋은 성능을 보인다.

  • 저장해야할 데이터가 많아져서 부하율이 일정 이상으로 증가하면 체이닝에 비해 성능이 급격히 저하된다.
  • 비어있는 버킷을 찾는 방식으로 선형 탐색, 제곱 탐색, 이중 해싱이 있다. 

  • 선형 탐색은 말그대로 선형적으로 다음 버킷을 참조해나가며 빈 버킷을 찾는 방식이다.

  • 제곱 탐색은 처음 얻은 해시 값에서 제곱수만큼씩 증가해나가며 빈 버킷을 찾는 방식이다.
  • 이중 해싱은 처음 얻은 해시 값이 충돌을 일으킬 경우 2차 해시 함수를 사용하여 다시한번 해시 값을 얻는 방식이다.
    가장 많은 연산을 필요로하지만 클러스터링의 영향을 거의 받지 않는다.

 ※ 클러스터링에 취약하다는 것은 반대로 참조 지역성(Locality of Reference)이 높다는 의미가 되기 때문에
      캐싱 성능이 좋아진다. 그렇기 때문에 선형탐색 -> 제곱 탐색 -> 이중 해싱 순으로 클러스터링 방지는 잘 되지만
      참조 지역성이 낮아져 캐싱 성능은 떨어진다. 체이닝 기법의 경우에도 클러스터링의 영향을 거의 받지 않기 때문에
      참조 지역성이 낮아 선형탐색을 통한 개방주소 기법에 비해 캐싱 성능이 떨어진다.

 

 

5. 리사이징(Resizing) & 재해싱(Rehashing)

  • 부하율이 높아져 성능이 저하되는 것을 방지하기 위해 기존보다 더 많은 버킷을 할당한 뒤 기존에 저장된 데이터들을
    새로운 공간간에 다시해싱하는 작업 

  • 개방주소법의 경우 삭제 시 발생하는 더미 데이터 등으로 인한 성능저하 문제도 있기 때문에 주기적인 재해싱을 해줘야
    성능을 유지할 수 있다.

 

1. ADT 작성

Trie:
    Datas:
        __root : 트리의 루트노드
        __size : 트리의 크기

    Operations:
        insert(string) : 문자열 string 을 트라이에 삽입
        find(string) : 문자열 string이 트라이에 들어있다면 True, 아니라면 False 반환
        
Trie.__Node:
    Datas:
    	is_term : 해당 노드가 문자열의 마지막 문자를 나타내는지 여부
        next : 연결된 다음 문자 노드 리스트.  next[ord(key) - ord('a')] 가 None 이 아니라면
               다음 문자가 key인 문자열이 Trie 내에 존재한다는 의미가 된다.

    Operations:
    	get(key) : 문자 key 에 해당하는 다음 문자 노드를 반환
        set(key) : 문자 key 에 해당하는 다음 문자 노드를 설정

 

 

2. 구현 

class Trie:
    # 트라이의 노드 클래스
    class __Node:
        def __init__(self, is_term=False):
            self.next = [None] * 26
            self.is_term = is_term

        # key 에 해당하는 다음 문자 노드를 반환
        def get(self, key):
            return self.next[ord(key) - ord('a')]

        # key 에 해당하는 다음 문자 노드를 설정
        def set(self, key, node):
            self.next[ord(key) - ord('a')] = node

    def __init__(self):
        # 루트 노드
        self.__root = self.__Node()
        
        # 트라이의 크기
        self.__size = 0

    def __len__(self):
        return self.__size

    # 문자열 삽입
    def insert(self, string: str):
        # 루트 노드에서 탐색 시작
        cur = self.__root

        # 삽입할 문자열의 모든 문자를 소문자로 변환
        for c in string.lower():
            nxt = cur.get(c)
            # 문자 c에 해당하는 노드가 없다면 생성
            if not nxt:
                nxt = self.__Node()
                cur.set(c, nxt)

            # 문자 c에 해당하는 노드로 이동
            cur = nxt

        # 기존에 없었던 문자열이라면
        if not cur.is_term:
            # 문자열의 마지막 문자에 해당하는 노드에 is_term 값을 True 로 설정
            cur.is_term = True
        
            # 트리의 크기 1 증가
            self.__size += 1

    # 문자열 탐색
    def find(self, string):
        return True if self.__search(string) else False

    # 문자열의 마지막 문자에 해당하는 노드를 찾아 반환
    def __search(self, string: str):
        cur = self.__root
        for c in string.lower():
            cur = cur.get(c)
            if not cur:
                return None
        if cur.is_term:
            return cur
        return None

 

1. 트라이(Trie)

 트라이(Trie)는 문자열의 빠른 탐색을 위해 고안된 트리이다. 하나의 노드가 하나의 문자를 나타내도록 하여

문자열을 저장해나가는 것으로 검색할 문자열의 길이가 N 일 때, O(N)의 복잡도로 탐색을 마칠 수 있다.

하나의 문자열의 끝임을 표시하기 위해 문자열의 마지막 문자인 노드를 식별할 수 있도록 한다.

위 그림의 트라이는 문자열의 마지막 문자인 노드를 주황색으로 표시한 것이다.  위 트라이에 저장된 문자열은

be, bee, bean, app, apple, apart 의 6개가 된다.

 

 

2. 특징

  • 길의 N의 문자열을 삽입할 경우 O(N)의 시간복잡도로 삽입 가능

  • 길이 N의 문자열을 탐색할 경우 O(N)의 시간복잡도로 탐색 가능

  • 저장된 문자열 중 지금까지 입력한 문자열로 시작하는 모든 문자열을 파악할 수 있기 때문에 
    자동완성 기능의 구현에 사용됨

트라이의 삽입/탐색 연산은 굉장히 간단하기 때문에 구현 파트에서 주석으로 간단히 설명하고 넘어가기로 한다.

'CS > 자료구조' 카테고리의 다른 글

#14 해싱(Hashing)  (0) 2021.10.26
#13 트라이(Trie) 구현  (0) 2021.10.25
#11 트리(Tree) 5 - B-Tree  (0) 2021.10.18
#10 레드블랙 트리(Red-Black Tree) 구현  (0) 2021.10.14
#9 트리(Tree) 4 - 레드블랙 트리(Red-Black Tree)  (0) 2021.10.08

+ Recent posts