IP 단편화(fragmentation) network links는 MTU(Max Transfer Size)를 가진다. 링크 계층 프로토콜마다 다른 링크 타입과 MTU를 가지므로 네트워크는 큰 IP datagram을 분할할 필요성이 있다. 이러한 IP datagram을 여러 조각의 datagram으로 쪼개서 전송하고 최종 목적지에서 재결합(reassembly) 된다. IP 헤더를 통해 본래 하나의 datagram이었는지 구분하고 순서를 확인하게 된다. 4000byte datagram을 3개의 datagram으로 쪼개서 전송했다고 하자. 각 datagram은 헤더가 20byte씩을 차지한다. 즉 처음 datagram도 헤더가 20byte를 차지하므로 data field는 3980이다. 또한 MTU는 1500..
스케줄링 기법(Scheduling Mechanisms) 네트워크에서 스케줄링은 link 상으로 보낼 다음 패킷(packet)을 선택하는 것을 뜻한다. 스케줄링 기법에는 여러가지가 존재하는데, 그 중 몇 가지만 알아보자. FIFO(First In First Out) 스케줄링 FIFO 스케줄링은 간단하게 큐에 도착한 순서대로 전송하는 기법을 뜻한다. 이 때 만약 큐가 가득찼을 때 패킷을 버린다면 어떤 패킷을 버려야 할까? 이것도 다음과 같이 여러가지 방법이 있다. tail drop : 방금 도착한 패킷을 버린다. priority : 우선순위에 기반해 패킷을 버린다. random : 랜덤으로 패킷을 버린다. Priority 스케줄링 가장 높은 우선순위의 패킷을 먼저 전송하는 기법을 뜻한다. Round Robi..
TCP 혼잡 제어란? 혼잡(congetion)하다는 것은 너무 많은 source가 너무 많은 data를 너무 빨리 전송해 네트워크가 이를 처리하지 못하는 상태를 말한다. 조금 더 자세히 설명하자면 데이터의 양이 수신 측에서 처리할 수 있는 양을 초과하게 되면 송신 측에서는 수신 측에서 처리하지 못한 데이터를 손실 데이터로 간주하고 계속 재전송하게 되므로 네트워크가 더욱더 혼잡하게 된다. 이러한 혼잡 상태를 제어하는 것을 혼잡 제어라고 한다. TCP 혼잡 제어의 여러 가지 방법을 알아볼 것인데, 그전에 TCP에 대해 잘 모르겠다면 다음 포스팅을 참고하자. [네트워크] TCP란? | TCP의 특징 | TCP RDT | 3-way handshake TCP란? TCP(Transmission Control Pro..
다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능) 다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문) 2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다. 위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자. ..
TCP란? TCP(Transmission Control Protocol)는 애플리케이션에서 보낸 데이터를 신뢰성 있게 수신 측에 전송을 보장하는 프로토콜이다. 다음과 같은 특징들을 가진다. point-to-point : 하나의 송신 측과 하나의 수신 측이 통신하는 1:1 통신이다. reliable : 신뢰성 있는 데이터 전송을 보장한다. pipelined : TCP 흐름 제어와 혼잡 제어가 window size를 설정한다. full duplex(전이중 통신) : 쌍방향 통신이 가능하다. 즉 데이터를 주고받을 수 있다. connection-oriented : 연결 지향적이다. 송신 측과 수신 측이 데이터를 교환하기 전에 handshaking을 한다. flow control : 흐름 제어를 한다. conge..
pipelined protocols pipelined protocols에서 pipelining은 송신자가 다수의 패킷을 한 번에 보내는 것을 말한다. 즉 ACK신호를 받을 때까지 기다리다 ACK신호를 받고 나서 다음 데이터를 보내는 stop and wait 방식과 다르게 송신자가 ACKs 신호를 받지 않아도 패킷 여러 개를 보내는 방식이다. 송신자와 수신자가 버퍼를 가져야 하며, 대표적인 두 가지 프로토콜로 Go-Back-N과 Selective Repeat이 있다. 참고 : stop and wait 방식의 RDT [네트워크] Reliable Data Transfer - rdt 1.0/2.0/2.1/2.2/3.0 | RDT란? | FSM 이란? RDT(Reliable Data Transfer)란? RDT는..
RDT(Reliable Data Transfer)란? RDT는 신뢰성 있는 데이터 교환을 의미한다. 즉 송/수신하는 데이터가 오류 없이 온전히 전송되는 것을 뜻한다. Transport Layer(전송계층)에서는 신뢰성 있는 데이터 교환을 하고 싶어 하지만, 하위 레이어들에서는 신뢰성을 보장할 수 없기 때문에 문제가 발생할 수 있다. 이를 해결하기 위해 Transport Layer에서 RDT 프로토콜을 이용할 수 있다. 아래는 RDT 프로토콜을 이용해 데이터를 송/수신하는 예시이다. 송신 측 상위 레이어에서 보내려는 데이터가 있다면 rdt_send()를 호출해 데이터를 RDT 프로토콜로 전송한다. RDT 프로토콜에서 신뢰할 수 없는 채널인 하위 레이어로 보낼 때 udt_send()를 호출해 패킷을 전송한다..
UDP란? UDP(User Datagram Protocol)는 비연결형, 신뢰성이 없는 전송 프로토콜이다. IP데이터그램을 캡슐화하여 보내는 방법과 연결 설정을 하지 않고 보내는 방법을 제공한다. UDP는 TCP/IP 5계층에서 Transport Layer(전송계층)의 프로토콜이다. UDP의 특징 UDP는 흐름제어, 오류제어 또는 손상된 세그먼트의 수신에 대한 재전송을 하지 않는다. 따라서 내용이 전송 중에 손실 될 수 있고, 전송되는 세그먼트의 순서가 바뀔 수 있다. UDP는 TCP보다 간단하고 빠르다. 작은 header size를 가지고 있다. 흐름제어를 하지 않기 때문에 전송 속도를 최대한 빠르게 할 수 있다. 수신자와 송신자 간의 handshaking이 없는 connectionless 성질을 가진..
정렬 알고리즘이란? 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다. 아주 간단한 알고리즘부터 조금 복잡한 알고리즘까지, 여러가지 알고리즘을 알아보고 비교해보자. 우선 정렬 알고리즘을 비교하기 전에 stable 과 not stable의 차이, in-place와 not inplace 개념에 대해 알아보자. stable vs not stable stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다. 예를 들어, int arr[5] = { 7, 3, 6, 2, 3 } 과 같이 3값이 두 번 들어 있는 배열이 있다고 하자. 이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서대로 정렬 되었다면 stable s..
퀵 정렬(Quick Sort) 퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다. 1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. 3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 ..