Transport layer에서의 신뢰적인 데이터 전송을 다룬다.

• 신뢰적인 채널에서는 데이터가 손상되거나 (bit가 바뀜) 전송 순서가 바뀌지 않는다.
• Transport layer에서 신뢰적인 데이터 전송을 보장하더라도, 하위 계층에서 데이터가 손실될 수 있기 때문에 다루기가 어렵다.
• rdt: reliable data transfer protocol
  • rdt_send(): rdt의 송신 측이 호출될 때
  • rdt_rcv(): 패킷이 수신 측에 도착했을 때
  • deliver_data(): rdt가 상위 계층에 데이터를 전달할 때

이 챕터에서는 송신 측에서 수신 측으로의 데이터 전송(Unidirectional data transfer)만을 고려하고 패킷이 일부 손실될 수는 있으나, 순서대로 보내지긴 한다고 가정한다.

신뢰적인 데이터 전송 프로토콜의 구축

Finite-state machine (FSM) 정리

컴퓨터 과학에서 유한한 상태들과 그들 간의 전이(transition)를 정의한 수학적 모델

• 시스템의 동작을 모델링하고, 입력에 따라 시스템이 어떻게 반응하는지를 나타낸다.
  

• 점선 화살표: 초기 상태를 나타낸다.

• 실선 화살표: Transition을 나타낸다.

• 가로선 위: Transition을 일으키는 event를 나타낸다.

• 가로선 아래: Event가 발생하였을 때 취할 행동 (Action)

완벽하게 신뢰적인 채널에서 신뢰적인 데이터 전송: rdt 1.0

• 하나의 상태만을 가지고 있기 때문에 Transition (화살표)는 자신으로 되돌아온다.

• 송신 (a)

  • rdt_send(data) event에 의해 상위 계층으로부터 데이터를 받아들인다.
  • make_pkt(data): 데이터를 포함한 패킷을 생성한다.
  • udt_send(packet): 패킷을 채널로 전송한다.'

• 수신 (b)

  • rdt_rcv(packet) event에 의해 하위 채널으로부터 패킷을 수신한다.
  • extract(packet, data): 데이터를 추출한다.
  • deliver_data(data): 데이터를 상위 계층으로 전달한다.

• 완전히 신뢰적인 채널에서는 오류가 생길 수 없으므로 수신 측이 송신 측에게 어떠한 피드백도 제공할 필요가 없다.

비트 오류가 있는 채널에서 신뢰적인 데이터 전송: rdt 2.0

패킷 안의 비트들이 하위 채널에서 손상되는 모델을 고려해보자.

자동 재전송 요구(Automatic Repeat reQuest, ARQ) 프로토콜

• 긍정 확인응답(positive acknowledgment, “OK”)
• 부정 확인응답(negative acknowledgment, “그것을 반복해주세요”)

비트 오류를 처리하기 위해 ARQ Protocol에 필요한 세 가지 부가 프로토콜 기능

1. 오류 검출: checksum과 같이 비트 오류가 발생했을 때 수신자가 검출할 수 있는 기능

2. 수신자 피드백: ACK, NAK와 같은 피드백을 전송한다.

   • 보통 피드백은 한 비트 길이로, NAK: 0 / ACK: 1으로 나타낼 수도 있다.

3. 재전송: 오류가 발생한 패킷은 송신자에 의해 재전송된다.

송신 (a)

• 두 가지 상태가 존재한다.

  • 상위 계층으로부터 데이터 전달 대기 / ACK, NAK 응답 대기

• Event에 따라 행동이 다르다.

  • rdt_send(data): 패킷 checksum과 함께 전송될 데이터를 포함하는 packet (sndpkt)를 생성하고, 그 패킷을 udt_send(sndpkt)를 통해 전송한다. 이후, ACK 또는 NAK 패킷을 기다린다.
  • rdt_rcv(rcvpkt) && isACK(rcvpkt): 가장 최근에 전송된 패킷이 정확하게 수신되었으니 프로토콜은 데이터 전송 대기 상태로 돌아간다.
  • rdt_rcv(rcvpkt) && isNAK(rcvpkt): 프로토콜은 마지막 패킷을 재전송하고 다시 ACK, NAK 응답 대기

• ACK, NAK 응답 대기 중에는 상위 계층으로부터 데이터를 받을 수 없다 (rdt_send() 이벤트는 발생할 수 없다).

• Stop-and-wait protocol

  • 송신자는 수신자가 현재 패킷을 정확하게 수신했음을 확신하기 전까지 새로운 데이터를 전송하지 않는다.

수신 (b)

• 하위 계층으로부터 호출을 기다리는 하나의 상태만을 가진다.

• Event에 따라 행동이 다르다.

  • rdt_rcv(rcvpkt) && corrupt(rcvpkt): NAK 패킷을 생성하고 전송한다.
  • rdt_rcv(rcvpkt) && notcorrupt(rcvpkt): 데이터를 추출하고 상위 계층으로 전송하고 수신자한테는 ACK 패킷을 전송한다.

문제점
ACK / NAK 패킷이 손실될 수도 있다.

rtd 2.1 & rdt 2.2

ACK / NAK가 손실될 경우를 대비한 rdt 2.0

손상된 ACK, NAK를 처리할 수 있는 세 가지 가능성

1. 수신 측의 ACK, NAK 재요청에 대해 재전송

   • 재전송하는 ACK, NAK 패킷이 또 손실될 수도 있다.

2. 송신자가 검출뿐만 아니라, 비트 오류로부터 회복할 수 있도록 충분한 checksum bit를 추가하는 것

3. 송신자가 ACK, NAK 패킷을 수신하면 데이터 패킷을 재전송하는 것

   • Duplicate packet이 전송된다.
   • 수신자가 도착하는 패킷이 새로운 데이터인지 재전송인지 사전에 알 수 없다는 단점이 있다.

해결책

송신자가 데이터 패킷에 sequence number 라는 새로운 field를 추가하고, 수신자는 수신된 패킷이 재전송인지 여부를 sequence number만 확인하여 결정한다.

• sequece number field의 bit 수가 k라면, sequence number의 범위는 [0, 2^k - 1]이 된다.
• sequence number 연산에는 mod k 가 이용된다.

rtd 2.1

송신자

• Sequence number가 0인지 1인지를 결정하는 부분을 추가해야되기 때문에 상태가 rtd 2.0에 비해 두 배 많다.
• 여기서의 Sequence number는 이전과 같은지 여부만 판단하여 재전송인지 여부를 판단한다.
  • Duplicate packet인지 판단한다.
• Corrupt (): ACK / NAK packet이 손실된 경우를 뜻한다.

수신자

• 손상된 패킷이 수신되면, 수신자는 NAK를 전송한다.
• Sequence number가 다른 패킷을 받았다면
  a. 이미 처리한 패킷이 재전송 됨 (Duplicate packet)
  b. 순서가 어긋난 패킷
• 시퀀스 번호가 맞지 않거나 중복 패킷(예: 재전송된 패킷)을 받으면 데이터는 무시되고, 이전 상태를 유지합니다.
  

rtd 2.2

rtd 2.1과의 차이점

• 수신자가 반드시 ACK 메세지에 의해 확인 응답되는 패킷의 sequence number를 포함해야한다.
  • make_pkt() 에 ACK, 0 또는 ACK, 1인 인수를 추가한다.
• 송신자는 수신된 ACK 메세지에 의해 확인 응답된 패킷의 sequence number를 반드시 검사해야한다.
  • isACK() 에 0 또는 1인 인수를 추가한다.
• sequence number를 추가하여 duplicate data packet을 처리한다.
  

비트 오류와 손실 있는 채널상에서의 신뢰적인 데이터 전송: rdt 3.0

만약 하위 계층에서 packet loss가 발생했다면, 송신자가 패킷을 잃어버렸다고 확신할 정도로 충분한 시간을 기다린다면 간단하게 재전송될 수 있다.

• 하지만 수신자가 굉장히 오랜시간 대기하게 된다.
• 때문에 실제로는 ACK가 특정 시간 안에 수신되지 않는다면 패킷을 재전송하는 방법을 선택한다.
• 이 경우, duplicate data packet의 가능성이 있지만 rtd 2.2에서 중복 데이터를 처리하는 기능을 제공한다.

송신자는 실제로 packet loss가 발생했는지, ACK packet이 손실된 것인지, 둘 중 하나가 단순히 지나치게 지연된 것인지 알지 못하지만 우선 재전송한다.

• 이를 위해 Countdown timer를 사용한다.
• Countdown timer: 주어진 시간 후, 송신자를 interrupt 할 수 있게 해준다.

송신자의 동작은 다음과 같다.

1. 각 packet이 송신된 시간에 Countdown timer를 시작한다.
2. Timer interrupt가 발생하면 적당한 action을 취한다.
3. Timer를 멈춘다.

rdt 3.0

• Packet sequence number가 0과 1이 번갈아 일어나기 때문에 alternating-bit protocol 이라고도 부른다.
• 패킷에 대한 수신 시간은 transmission delay와 propagation delay 때문에 패킷 전송 시간보다 더 늦다.
• stop-and-wait protocol이라는 성능 문제가 존재한다.

protocol의 동작

파이프라이닝된 신뢰적인 데이터 전송 프로토콜

rdt 3.0의 문제점인 stop-and-wait protocol을 해결하자

• stop-and-wait protocol은 형편없는 송신자 utilization을 갖는다.

RTT = 30ms, Transmission rate: 1 Gbps, 패킷 크기: 1000 byte일 때

Stop-and-wait의 경우

RTT = 30ms, $d_{trans}$ = 0.008ms이므로 송신자가 packet을 전송하고, ACK packet을 다시 받을 때까지는 30.008ms가 걸린다.

이때 Utilization을 구해볼 수 있다.

• 30.008ms 시간 중 실제로 송신자가 데이터를 전송한 시간은 0.008ms 밖에 되지 않는다.
• Effective throughput: 초당 1 Gbps의 링크가 가용하더라도 267 kbps만이 Effective throughput 이다.

Pipelining 이용

Stop-and-wait 방식에서 낮은 Utilization의 문제를 해결하기 위해 확인 응답을 기다리지않고 여러 패킷을 전송하도록 허용하는 것이다.

• Pipelining: Pipeline에 전송 중인 송신자 - 수신자 패킷을 채워 넣는 기술

Pipeline 사용 조건

1. Seqeunce number의 범위가 커져야 한다.

   • 전송 중인 packet은 유일한 sequence number를 가져야 하고 전송 중인 ACK이 확인이 되지 않은 packet이 여렷 존재할 수도 있기 때문이다.

2. 프로토콜의 송신 측과 수신 측은 패킷 하나 이상을 버퍼링해야 한다.

   • 송신자는 반드시 전송되었으나 확인 응답되지 않은 패킷을 버퍼링해야 한다.

Pipeline 오류 회복 방법

GBN (Go-Back-N) protocol

Pipeline에서 확인 응답이 되지 않은 packet의 수가 최대 허용 수 N보다 크지 말아야 한다.

base: 확인 응답이 되지 않은 가장 오래된 패킷의 순서 번호
nextseqnum: 전송될 다음 패킷의 순서 번호

• [0, base-1]: 이미 전송되고 확인 응답까지 완료된 패킷의 sequence number
• [base, nextseqnum - 1]: 송신 되었지만 아직 확인 응답 되지 않은 패킷의 sequence number
• [nextseqnum, base + N - 1]: 상위 계층으로부터 데이터가 도착하면 사용할 sequence number
• [base + N 이상]: base에 해당하는 packet이 확인 응답되기 전까지 사용될 수 없는 sequence number

window: 전송되었지만 아직 확인 응답되지 않은 패킷을 위해 허용할 수 있는 sequence number 범위

• Protocol이 동작할 때, window는 sequence number space에서 오른쪽으로 slide 된다.
• 이러한 관점에서 GBN Protocol을 sliding-window protocol이라고도 부른다.
  -window size: N

ACK 기반, NAK 없는 GBN protocol

송신자

GBN 송신자는 다음 세 가지 타입의 이벤트에 반응한다.

1. 상위로부터의 호출

   • 호출되면 송신자는 window가 가득 찼는지 확인한다.
   • 가득 차지 않았다면, 패킷이 생성되고 송신된다.
   • 가득 차 있다면, 송신자는 window가 가득 차 있음을 가리키는 함축적인 의미로 데이터를 상위 계층으로 반환한다.

2. ACK의 수신

   • sequence number n을 가진 packet에 대한 확인 응답은 cummulative acknowledgment로 인식된다.
   • cummulative acknowledgment: 0 ~ n까지의 sequence number를 가진 모든 패킷에 대한 확인 응답

3. Timeout event

   • Timeout이 발생하면, 송신자는 이전에 전송되었지만 아직 확인 응답되지 않은 모든 패킷을 재송신한다.

수신자

• 수신자는 packet이 오류 없이 순서대로 수신된다면 packet n에 대해 ACK를 송신하고 상위 계층에 데이터를 전달한다.

• 그 외의 경우에는 해당 packet을 버리고 가장 최근에 제대로 수신된 순서의 패킷에 대한 ACK를 재전송한다.

• 순서가 잘못된 패킷은 버린다.

GBN의 동작

• window size = 4
• event-based programming: 다양한 event에 대한 대응으로 취할 수 있는 동작을 구현하는 programming

GBN의 문제점

1. (window size) * (bandwidth-delay) 의 결과가 너무 클 때, 많은 패킷이 pipeline에 존재하게 될 수 있다.

2. 하나의 패킷 오류에 대해 많은 패킷을 재전송하므로 불필요한 재전송이 많아진다.

SR (Selective Repeat)

GBN의 문제점을 보완하기 위해 불필요한 재전송을 줄이고 오류가 발생했다고 의심되는 패킷만을 재전송한다.

• SR 수신자는 손상 없이 수신된 패킷에 대한 확인 응답을 보낸다.
• 순서가 바뀐 패킷의 경우, 빠진 패킷이 전송될 때까지 Buffer에 저장하고, 빠진 패킷이 수신되는 시점에 상위 계층에 전달한다.

SR 송신자

SR 수신자

• 2단계가 중요하다.
  • 재확인응답을 해야 다음 sequence number로 넘어갈 수 있기 때문이다.

SR 동작

• 처음에 pkt3, 4, 5를 버퍼에 저장한다.
• 마지막으로 pkt2가 수신되었을 때 pkt2와 함께 상위 계층에 전달한다.

SR protocol에서 송신자와 수신자의 window가 항상 동일하지는 않다.

송신자와 수신자 윈도 사이의 동기화 부족: 순서 번호의 한정된 범위에 직면했을 때 중대한 결과를 가져온다.

가정)

• 한정된 범위의 네 패킷 순서 번호 0, 1, 2, 3
• window size : 3
• 0부터 2까지의 패킷이 전송되어 올바로 수신되고, 수신자에게서 확인이 되었다.
• 그 순간에 수신자의 윈도는 각각의 순서 번호가 3, 0, 1인 4, 5, 6번째 패킷에 있다

첫 번째 시나리오

1. 처음 3개의 패킷에 대한 ACK가 손실되고, 송신자는 이 패킷을 재전송한다.
2. 수신자는 순서 번호가 0인 패킷(처음 보낸 패킷의 복사본)을 수신한다.

두 번째 시나리오

1. 처음 3개의 패킷에 대한 ACK가 모두 올바르게 전달되었다.

2. 송신자는 자신의 window를 앞으로 이동시켜, 각각의 순서 번호가 3, 0, 1인 4, 5, 6번째 패킷을 보낸다.

3. Sequence number 3을 가진 패킷이 손실되고, 순서 번호 0을 가진 패킷(새로운 데이터를 포함한 패킷)은 도착한다.

수신자 관점을 고려해보자

수신자는 송신자의 행동을 볼 수 없다.

모든 수신자는 채널을 통해 받고, 채널을 통해 보내는 메시지의 순서를 관찰하는데, 이는 위의 두 가지 시나리오가 똑같다.

즉, 다섯 번째 패킷의 원래 전송과 첫 번째 패킷의 재전송을 구별할 방법은 없다.

Q) 최소한의 윈도 크기는 얼마인가?

Window size: SR 프로토콜에 대한 순서 번호 공간 크기의 절반보다 작거나 같아야 한다.

신뢰적인 데이터 전송 메커니즘과 그 사용에 대한 요약