3. Transport Layer

Must do in transport layer

1. Multiplexing/demultiplexing

2. Error checking

Multiplexing/demultiplexing

socket을 통해 message가 transport layer로 내려올 것이다.

Transport layer는 이를 segment로 만들어서 하위 layer로 보내게 된다.

💡

강의안 기준으로는 multiplexing은 encapsulation, demultiplexing은 decapsulation에 대응됨을 주의해서 정리하도록 하자.

How demultiplexing works

segment는 다음 2개의 파트로 나눌 수 있다.

1. data 부분

2. header부분

이때, header부분에 source port와 destination port에 대한 정보가 있는 것이다.

→ 이러한 정보를 가지고 demultiplexing을 진행할 수 있다.

💡

정확히는 Network layer가 datagram을 수신하는데, datagram의 header부분에는 source IP address와 destination address가 존재한다. host 입장서는 IP주소와 port number를 활용하여 알맞은 port에다가 연결해주는 작업을 수행하게 된다.

💡

좀 더 정확하게는 UDP의 경우는 destination IP와 destination port number를 기준으로 socket를 판단하고, TCP의 경우는 source/destination IP, source/destination port 전부를 판단하고 하나라도 다르면 다른 socket으로 판단한다. (그래서 connection oriented이다.)

💡

OS 관점에서 바라보자면, 웹 서버 프로세스가 있고 각 사용자별로 thread를 만들어준다. 그리고 각 thread별로 서로 다른 socket이 할당되는 것이다. (즉 유저 별로 다른 socket이 할당되고 이 과정에서 overhead가 발생한다.)

추가적으로 1개의 datagram에는 1개의 transport layer segment가 들어있다.

UDP : User Datagram Protocol

• often used for streaming multimedia apps
  • loss tolerant
  • rate sensitive

• other UDP uses
  • DNS
  • SNMP

• reliable transfer over UDP : add reliability at application layer

Header

• source port number: 16bit ($0$ ~ $2^{16}-1$)

• destination port number : 16bit ($0$ ~ $2^{16}-1$)

💡

위 2개의 정보를 가지고 demultiplexing (decapsulation)을 진행하게 된다.

• length

• checksum : 전송 도중 error가 있는지 없는지 판단하는데 사용

💡

만약 checksum을 활용해서 검사한 결과 오류로 판명되면 버림

Principles of Reliable Data Transfer

💡

실제로는 physical layer만 하더라도 unreliable하다.

일단은 단순한 모델부터 생각해보도록 하자.

이후에는 별다른 언급이 없으면, 하나의 패킷이 receiver에게 다 도착했다는 것을 확인한 이후 그다음 packet을 보낸다고 가정하겠다.

Rdt1.0 : Data Transfer over a Perfect Channel

• The underlying channel is perfectly reliable
  • no packet errors
  • no packet loss

• What mechanism do we need for reliable transfer?

  → Nothing!

Rdt2.0 : channel with packet errors (no loss)

• What mechanisms do we need to deal with error?
  • Error detection
    • Add checksum bits
  • Feedback
    • Acknowledgement (ACKs) : receiver explicitly tells sender that packet received correctly
    • Negative acknowledgment (NAKs) : receiver explicitly tells sender that packet had errors
  • Retransmission
    • sender retransmits packet an receipt of NAK

따라서 우리는 다음 3가지의 mechanism이 필요하게 된다.

1. Error detection

2. Feedback

3. Retransmission

Rdt2.1

하지만, 만약 ACK나 NAK에 error가 있는 경우에는 문제가 발생하게 된다.

💡

즉, ACK와 NEK에도 checksum이 있어야 한다는 의미이다.

하지만, receiver 입장에서는 중복된 패킷인지 새로운 패킷인지 알 길이 없다.

→ 그래서 packet에 번호를 붙이는 것이다.

즉 rdt 2.0과 거의 유사하지만 sequence number를 추가했다는 점에서 차이를 보인다. Mechanism을 정리하면 다음과 같다.

1. Error detection

2. Feedback

3. Retransmission

4. Sequence

💡

즉, receiver 입장에서 sequence number를 활용하여 중복 여부를 체크한다.

💡

만약 receiver가 받은 packet이 corrupted되었다면 NAK를 보내고, 아니면 ACK를 보낸다.

Handling Duplicate Packets

• Sender adds sequence number to each packet

• Sender retransmits current packet if ACK/NAK unclear

  💡

  어차피 sequence number를 통해 receiver도 확인하고 있기 때문에 크게 문제는 없다.

• Receiver discards duplicate packet

Example

Rdt2.2 : a NAK-free protocol

Functionality는 rdt2.1과 동일하지만 ACK만 사용하겠다는 것

→ Instead of NAK, receiver sends ACK for the last correctly received packet

💡

ACK에 가장 마지막으로 잘 받은 packet의 번호를 보내주면 된다. 그걸 기반으로 sender는 다음 packet를 보내야하는지, 재전송 해야하는지 판단할 수 있게 된다.

Rdt3.0 : channel with loss & packet errors

• What mechanisms do we need for packet loss?
  • Timer!

  💡

  즉 일정 시간동안 답장을 기다리고 안오면 loss 되었다고 간주하는 것이다.

• Sender waits “reasonable” amount of time for ACK (a Time-out)

• If packet (or ACK) is just delayed (not lost):
  • Retransmission will be duplicate, but use of sequence number already handles this

Timer의 간격에 따라 장단점이 존재한다

• 짧게 한 경우
  • 장점 : loss 되었을 때 recovery가 빠름
  • 단점 : retransmission이 너무 빈번하게 발생해서 overhead가 발생한다.

• 길게 한 경우
  • 장점 : network의 overhead가 적음
  • 단점 : loss가 발생했을 때 recovery가 느리다

Example

Recap : Principles of Reliable Data Transfer

• What can happen over unreliable channel?
  • packet error, packet loss

• What mechanisms for packet error?
  • Error detection (by using checksum), feedback, retransmission, sequence number

• What mechanisms for packet loss?
  • Timeout

💡

이러한 정보들은 packet의 header부분에 담겨서 간다

Performance of rdt3.0

하지만 여태까지 언급한 방식은 한번에 하나의 패킷만 보낼 수 있다는 점에서 unrealistic하다. (신뢰성은 있지만 느려터졌다.)

→ 이러한 방식을 stop-and-wait 이라고 부른다.

$$U_\text{sender} = \frac{L/R}{L/R + RTT}$$

$U_\text{sender}$ : utilization - fraction of time sender busy sending

💡

즉 얼마나 많이 utilization을 했는지에 대한 계산이다. 근본적으로 한번에 1개의 packet만을 보낼 수 있기 때문에 utilization이 낮게 나오는 것이 문제이다.

Pipelined protocols

sender allows multiple, yet to be acknowledged packets

💡

즉, stop and wait 방식과 달리 pipelined 방식에서는 한꺼번에 많은 패킷을 보낸다는 점에서 차이를 보인다. 얼마만큼의 packet을 보내느냐는 window size에 의해 결정된다.

• range of sequence numbers must be increased

  💡

  기존의 stop and wait에서는 0과 1이면 충분했기에 1bit만 요구되었다. 하지만, pipelined방식을 사용하는 경우에는 이보다는 더 증가하게 된다.

• buffering at sender and/or receiver

pipelined protocol을 구현하기 위한 방법은 2가지가 존재한다

1. go-Back-N

2. selective repeat

아래 사이트에서 직접 구동을 확인해보도록 하자.

Selective Repeat / Go Back N

coded by Johannes Kessler 2012

https://www2.tkn.tu-berlin.de/teaching/rn/animations/gbn_sr/

Example

Go-Back-N

• ACK(n) : ACKs all packets up to, including sequence number of n - cumulative ACK

  → 예를 들어 ACK 11이라는 것은 11번 packet까지 잘 받았다는 것을 의미한다.

  → 따라서 여러 번의 중복된 ACK를 수신할 수 있다.

receiver와 sender의 입장에서의 procedure는 다음과 같다.

Sender

1. 첫 packet을 보내고 timeout timer를 킨다.

2. 첫 packet에 대한 응답이 오지 않아도 윈도우 크기 만큼의 packet을 순서대로 보낸다.

3. 윈도우의 맨 앞에 있는 순서번호에 해당하는 ACK가 왔을 때, 윈도우를 오른쪽으로 민다.

4. 윈도우를 이동시킬 때 (ACK가 도착했을 때) timeout timer를 재시작시킨다.

5. packet에 대한 응답이 오지 않아 타임아웃이 되면, 윈도우 처음부터 packet을 다시 순서대로 보낸다.

Receiver

1. 패킷을 수신하면 ACK(n)을 sender에게 보낸다.

   💡

   즉, 어느 packet까지 정상적으로 수신했는지에 대한 정보를 sender에게 보낸다.

2. 만약, k번 packet까지 정상적으로 받았는데, 다음에 k + 2번 packet을 수신하면 해당 패킷은 버린다.

3. 이후 k + 1번 패킷을 받게 되면 ACK(k + 1)를 sender에게 보낸다.

💡

추가적으로 receiver입장에서는 수신했지만 ACK signal이 sender에게 돌아가는 도중에 없어질 수 있는 경우도 고려하기는 해야 한다. 예를 들어 ACK(0)은 수신하지 못했지만, ACK(1)을 수신했다면, sender입장에서는 base를 2로 바로 바꿔주면 된다. 애초에 ACK가 cumulative하기 때문에 가능한 접근이다.

Example

→ 오른쪽에서 packet 2를 기다리는데 packet 3이 도착했기 때문에 버리는 것이다. 그리고 1번까지는 잘 받았으므로 ACK1를 보낸 것이다.

→ TimeOut된 것 기준으로 window size만큼 다시 보낸다.

💡

그래서 유실되면 window size만큼 다시 돌아와서 반복하게 된다.

💡

window안에 들어가 있는 packet들은 buffer에 있어야 한다.

[네트워크] Go-Back-N, Selective Repeat

데이터 전송 프로토콜은 손실된 패킷과 손상된 패킷 등에 대해 응답하는 방법을 정해두는데, 이 방법에 따라 버퍼링 조건이 달라진다. 파이프라인 오류 회복의 기본적인 접근법으로 Go-Back-N(N부터 반복, GBN)과 Selective Repeat(선택적 반복, SR)가 있다. GBN과 SR을 시각적으로 나타낸 웹사이트가 있다. 전송되고 있는 블록을 클릭하면 사라진다! www2.tkn.tu-berlin.de/teaching/rn/animations/gbn_sr/ Selective Repeat / Go Back N www2.tkn.tu-berlin.de Go-Back-N 송신자는 확인응답을 기다리지 않고 최대 허용된 수 안에서 여러 패킷을 전송할 수 있다. 송신자 관점에서 확인응답(ACK)이 안된 가장 오래..

https://snoop-study.tistory.com/65

Sequence number bit

The sequence number in each packet is used to identify and distinguish between different packets. To accommodate a window size of n, you need enough bits for n + 1 distinct sequence numbers. This allows for n unacknowledged but sent packets at the sender side, and one additional sequence number for the next expected packet at the receiver side.

Therefore, you would need $log_2(n+1)$ bits for the sequence number in each packet with Go-Back-N protocol.

→ 예를 들어 window size가 4이고 packet의 number는 절대적으로 가정하겠다. 만약에 0 ~ 3에 해당하는 packet을 receiver가 수신했지만, 이에 대한 ACK가 sender에게 가다가 유실되었다고 가정해보자. 그러면 sender 입장에서는 timeout때문에 packet 0부터 다시 보내게 될 것이다. 반면 receiver입장에서는 3번까지 받은 상황이기 때문에 ACK(3)을 전송할 것이다. 이 상황에서 만약 sequence number의 크기를 4로 한정한다면 receiver입장에서는 packet 4에 해당하는 정보가 온 것인지 아니면 ACK(3)이 또다시 sender에게 도착하지 않아서 packet 0을 재전송한 것인지를 구분할 수 없다. 이러한 문제때문에 +1만큼 조금 더 여유를 줬다고 생각해주면 된다.

Selective repeat

Go-Back-N의 경우에는 window size만큼 다시 재전송을 한다는 측면때문에 비효율성이 발생한다.

💡

그리고 애초에 receiver입장에서도 자기가 원하는 packet이 오지 않는이상 해당 packet을 버린다.

이에 개선을 하고자 ACK를 cumulative하는게 아니라 각각의 packet이 수신이 되었는지를 확인하는 용도로 사용하게 된다. 즉 ACK(n)의 의미가 해당 n번 packet이 잘 수신되었다는 것을 의미하는 것으로 변하게 된다.

추가적으로 Go-Back-N과 달리 순서에 맞지 않게 들어온 packet이라도 받아줘야 한다는 점에서 차이를 보인다. 또한 각 packet에 대해서 timer를 설정해야한다는 점에서 단점이 발생한다.

주의해야할 점은 receiver와 sender 모두 window를 가진다는 점이다. 이때 receiver가 packet을 받았더라도 sender 입장에서 윈도우의 맨 앞에 있는 packet에 대한 ACK를 받지 않으면 sender측의 윈도우는 이동하지 않는다.

💡

receiver쪽의 buffer는 out-of-order인 packet들의 수신여부를 저장하는데 사용한다. 그래서 Go-Back-N과 달리 receiver쪽에도 buffer가 존재하는 것이다.

💡

window size는 ACK 수신이 안된 packet의 수를 제한하는데 사용된다.

직접 구현해보는게 이해가 가장 빠르다.

Selective Repeat / Go Back N

coded by Johannes Kessler 2012

https://www2.tkn.tu-berlin.de/teaching/rn/animations/gbn_sr/

Example

Sequence number bit

In the selective repeat protocol, the sender maintains a window of up to n unacknowledged packets that have been sent. Similarly, the receiver also maintains a window of up to n packets that it is willing to receive.

The sequence number in each packet is used to identify and distinguish between different packets. To accommodate a window size of $n$, you need enough bits for $2n$ distinct sequence numbers. This allows for $n$ unacknowledged but sent packets at the sender side, and another $n$ unsent but receivable packets at the receiver side.

Therefore, you would need $log_2(2n)$ bits for the sequence number in each packet with selective repeat protocol.

Dilemma

sequence number를 줄이는 것이 header의 크기를 줄이기 위해서는 중요하다.

그렇다면, window size와 sequence number 사이의 관계에 대해서 알아보고 싶다. 예를 들어 window size가 3이고, sequence의 개수를 4로 설정했다고 가정하자. 그러면 다음과 같은 상황을 구분할 수 없는 문제가 발생한다.

💡

즉 재전송인지 다음 packet인지 구분할 수 없는 문제가 발생한다.

TCP

• point-to-point

  → 소켓 1쌍 끼리의 통신을 책임지는 것

  💡

  정확하게는 process 1개에 여러 개의 socket이 존재할 수 있다는 점을 주의해야 한다.

• reliable, in-order byte stream

• pipelined

• send & receive buffers

• full duplex data

  → bi-directional data flow in same connection

  💡

  따라서 각각 sender buffer/receiver buffer가 존재한다.

• connection-oriented

• flow controlled

  → sender will not overwhelm receiver

  💡

  window 크기만큼 전송을 하긴 하되, 만약 receiver buffer에 공간이 없으면 의미가 없다. 그래서 receiver의 능력에 맞게 조정한다는 것

• congestion controlled

  → 내부 네트워크가 받아들일 수 있는 양만큼 조절한다는 것

TCP segment structure

• 각각 port 주소는 16bit이다.

  💡

  포트 번호의 사용범위는 $0$ ~ $2^{16} - 1$

• checksum : 해당 segment가 network를 거쳐오면서 error가 있었는지 확인하는 목적

  → 이것을 활용해서 error detection을 수행하게 된다.

• Receive window : receiver buffer에 얼마나 많은 공간이 있는지에 대한 정보가 담겨있는 field

  💡

  해당 정보를 바탕으로 sender에게 정보를 보낸다.