Stop-and-Wait, Go-Back-N, Selective Repeat

TCP/IP 4계층의 전송 계층 프로토콜인 TCP의 기능중 하나는 신뢰적인 데이터 전송이다.

 

신뢰적인 데이터 전송이란 데이터가 손상되지 않고, 순서대로 도착함을 보장하는 것을 말한다.

 

신뢰적인 데이터 전송을 위한 TCP의 동작 방식으로 Stop-and-Wait, Go-Back-N, Selcetive-Repeat가 있다.

 

 

Stop - and - Wait

Sender가 패킷을 하나 보내고 대기한 뒤, 응답(ACK)을 수신하면 다음 패킷을 전송하는 방식이다.

 

지난 포스트의 rdt 3.0이 정확히 Stop-and-Wait 방식으로 분류된다.

https://debuggingworld.tistory.com/43

FSM으로 표현한 rdt

stop-and-wait

 

 

 

Pipelined Protocol

stop-and-wait 방식은 패킷을 하나씩 보내므로 매우 비효율적이다.

따라서 실제 TCP는 RTT 내에 여러 패킷을 전송하는 pipelined protocol을 이용한다.

 

sender와 receiver는 각각 패킷을 처리하기 위한 버퍼를 가진다.

 

pipelined protocol의 종류로는 Go-Back-N, Selective Repeat 두 가지가 있다.

pipelining

 

 

 

Go-Back-N

sender는 sendbase를 두고, sendbase와 window size에 따라 여러 패킷을 보낸다.

receiver는 수신한 패킷에 대한 누적 ACK(cumulative ACK)를 전송한다.

 

* window size

- Sender가 한번에 보낼 패킷의 양. 단위는 mss.

- window size가 3mss -> Sender는 한 번에 패킷을 3개씩 연속해서 보낸다.

 

* sendbase

- Sender는 sendbase부터 window size만큼 패킷을 연속해서 전송한다.

- sendbase가 p3이고, window size가 4라면

   -> window는 [p3, p4, p5, p6]이고, Sender는 p3, p4, p5, p6 패킷을 한 번에 전송한다.

       만일 sendbase가 p4로 변경됐다면, window가 [p4, p5, p6, p7]로 변경되므로 Sender는 p7을 마저 전송한다.

- sendbase가 변함에 따라 window가 변하고, window에 따라 전송하는 패킷이 달라지는 이러한 방식을 sliding window라 한다.

 

* 누적 ACK (cumulative ACK)

- Receiver가 가장 최근에 정상 수신한 패킷에 대한 ACK.

- 누적 ACK를 전송하는 Receiver로부터 ACK10이 도착했다.

   -> Receiver는 .... 8, 9,10번 패킷까지 정상 수신하였다는 의미.

 

 

GO-Back-N에서 sender와 receiver의 동작을 상세히 정리하면 다음과 같다.

 

Sender(GBN)

• timer : sendbase에 단일 timer를 갖는다.
• 상위 layer로부터 data를 수신했을 때
  • 보내야 할 다음 seq num를 붙여 패킷을 만들고, 생성한 패킷이 window 내에 있으면 전송
•  timeout
  • timer는 sendbase가 갱신되면 다시 시작된다. 지정한 interval 내에 전송한 패킷에 대한 ACK가 수신되지 않으면 timeout이 발생한다.
  • timeout이 발생하면 sendbase를 기준으로 패킷을 재전송한다.
• ACKn을 수신했을 때
  • n이 sendbase보다 작을 경우 : 무시
  • n이 sendbase와 같거나 클 경우 : sendbase를 window 내에 ACK를 수신하지 못한 패킷 중 가장 오래된 패킷으로 변경. window 내 미전송 패킷이 있다면 전송.

 

 

Receiver(GBN)

n번 패킷을 받으면 누적 ACK를 전송한다.

• 패킷이 in-order일 경우 (받아야 할 seq num의 패킷인 경우) : 패킷을 정상 처리하고 누적 ACK를 전송한다.
• 패킷이 out-order일 경우 (받아야 할 seq num이 아닌 패킷인 경우) : 누적 ACK를 전송. 받은 패킷은 버린다. 
  • ex) p4까지 정상 수신했는데, p5를 건너뛰고 p6이 도착했다면, ACK4를 전송하고 p6은 버린다.

• 그 외의 경우 : 무시

 

 

Go-Back-N 시나리오

 

- 정상 통신 시

정상 통신 시 GBN의 동작

 

 

- 패킷이 손실된 경우

패킷이 손실된 경우 GBN의 동작

패킷이 손실되어 Sender는 Receiver로부터 ACK1밖에 수신하지 못한다.

결국 send base가 갱신되지 않아 timeout이 발생하고, Sender는 send base인 p2부터 차례대로 모든 패킷을 재전송한다.

 

Receiver는 패킷을 정상 수신하여 누적 ACK를 전송한다.

p4를 수신해도 p2를 수신하지 못했으므로 누적 ACK로 a1을 전송하고 p4는 버린다.

 

 

 

 

- 응답이 손실된 경우

응답이 손실된 경우 GBN의 동작

ACK2가 손실되었지만, Sender는 누적 ACK인 ACK3을 수신하였으므로 send base를 p4로 옮겨 패킷을 계속 전송해

통신이 정상적으로 이루어진다.

 

 

 

Go-Back-N의 장단점

장점

- 누적 ACK를 사용하므로 응답이 손상 및 손실되어도 통신에 문제가 없다.

- Receiver측에서 받은 패킷을 버퍼링할 필요가 없으므로 Receiver 측에 추가적인 버퍼가 필요없다.

 

단점

- 정상 수신한 패킷도 순서가 맞지 않으면 버리고, 누적 ACK에 따라 모든 패킷을 재전송하므로 비효율적이다.

 

즉, 누적 ACK를 사용한다는 점이 장점이자 단점으로 작용한다.

 

 

 

 

 

Selective Repeat

Sender는 window size에 맞추어 패킷을 전송하고, 전송한 패킷별로 timer를 시작한다.

그리고 timeout이 발생한 패킷만 재전송한다.

send base에 해당하는 패킷을 수신해야만 send base를 이동한다.

 

Receiver는 누적ACK가 아닌 수신한 패킷에 대한 개별적인 ACK를 전송한다.

또한 순서에 맞지 않는 패킷을 버리지 않고 버퍼링한다.

 

 

Sender와 Receiver의 동작을 상세히 정리하면 다음과 같다.

 

Sender

• 상위 계층에서 전송할 데이터가 도착했을 때
  • seq num을 붙여 패킷을 생성하고 sendbase와 window에 따라 패킷을 전송한다.
• timout이 발생할때
  • timeout이 발생한 패킷을 재전송하고, timer를 재시작한다.
• ACK를 수신했을 때
  • 해당 패킷의 timer를 제거한다.
  • send_base의 패킷에 대한 ACK를 수신한 경우 send_base를 ACK를 수신하지 못한 가장 최근의 패킷으로 이동시킨다. 만약 send_base를 이동한 패킷이 window 내에 있다면 패킷을 전송한다.

 

Receiver

• 기본적으로 수신한 패킷에 대한 개별 ACK를 전송한다.
• 수신한 패킷이 out-order인 경우 (다음 차례로 수신해야하는 패킷이 아닌 경우) 정상수신한 뒤 버퍼링한다.
• 수신한 패킷이 in-order인 경우 정상 수신한다.
  • 수신한 패킷들의 순서가 맞을 경우 즉시 상위 계층으로 데이터를 전달한다.

 

 

Selective Repeat 시나리오

 

- 정상 통신 시

정상 통신 시 SR의 동작

 

 

- 패킷이 손실된 경우

패킷이 손실된 경우 SR의 동작

p2 패킷이 손실되어 Receiver로부터 ACK2가 도착하지 않는다.

Sender에 결국 timeout이 발생하여 p2를 재전송한다.

Receiver는 그제야 ACK2를 전송하고 버퍼링했던 다른 패킷들과 순서를 맞추어 상위 계층으로 전송한다.

 

 

 

- 응답이 손실된 경우

응답이 손실된 경우 SR의 동작

 

Sender는 send_base인 p2에 대한 ACK가 오지 않아 timeout이 발생하였고, p2를 재전송한 뒤 ACK2를 다시 수신한다.

ACK2를 수신한 뒤 그제서야 send base가 이동해 다음 패킷들을 순서대로 전송한다.

 

Receiver는 ACK2를 전송하고, p2는 이전에 이미 수신했으므로 버린다.

 

 

 

Selective Repeat의 장단점

장점

- 손실된 패킷에 대해서만 패킷을 재전송하므로 효율적이다.

 

단점

- Sender 측에서 전송한 패킷별로 timer를 유지하기 때문에 오버헤드가 크다.

- Receiver 측에서 받은 패킷을 버퍼링하므로 추가적인 공간을 필요로 한다.

 

GBN과 마찬가지로 누적ACK를 사용하지 않는 것이 장점이자 단점으로 작용한다.

 

 

 

+)

GBN, Selective Repeat의 시나리오를 보면 send base에 따라 window가 변하는 것을 알 수 있다.

이렇게 window를 실시간으로 변화시키며 패킷을 전송하는 방식을 sliding window 기법이라 한다.

 

 

 

 

 

 

 

 

real TCP

실제 TCP는 Go-Back-N과 Selective Repeat를 혼합한 방식으로 동작한다.

 

Sender는 단일 timer를, Receiver는 누적 ACK를 사용한다.

 

또한 Sender가 전송하는 패킷의 sequence number는 전송하는 바이트 스트림의 첫 번째 문자의 순서다.

그리고 Receiver의 ACK 번호는 Receiver가 다음번에 받아야 할 바이트 스트림의 sequence number다.

 

TCP는 기본적으로 보내는 데이터의 단위가 byte이기 때문에 보내는 데이터는 byte stream이며, sequence numer는 byte stream의 순서 번호다.

 

이를테면, TCP가 "abcdef"라는 데이터를 3byte(3글자)씩 두 개의 패킷에 나눠서 보낸다고 가정하자.

 

Sender가 보내는 첫 번째 패킷의 seq number는 1이고, 두 번째 패킷의 seq number는 4다.

첫 번째 패킷 : 데이터 = "abc", seq num = 1

두 번째 패킷 : 데이터 = "def", seq num = 4

 

Receiver가 첫 번째 패킷을 정상수신하면 총 3byte를 수신하였고, 다음에 받을 데이터의 순서는 4 이므로, 첫 번째 응답은 ACK4이다.

같은 원리로 두 번째 응답은 ACK7이 될 것이다.

 

 

Sender와 Receiver의 동작을 상세히 정리하면 다음과 같다.

 

Sender

• sequence number는 전송하는 byte stream의 첫 번째 순서다.
• Sender는 timeout이 발생하거나 중복 ACK를 여러 번(통상 3번) 수신하면 패킷을 재전송한다.
  • 중복 ACK를 여러번 수신하면 timeout 발생 전이라도 패킷을 재전송한다. 이를 빠른 재전송이라 한다.
  • timeout, 중복 ACK 수신 등의 이유로 패킷을 재전송하는 경우를 loss event라 한다.
• 단일 타이머를 사용하며 send base가 변경될때마다 갱신된다.

 

Receiver

• 기본적으로 누적 ACK를 사용한다.
• ACK 번호는 Receiver가 받아야 하는 byte stream의 다음 시작 순서다.
• 수신한 모든 패킷에 대해 ACK를 전송하지는 않는다.
  • 기다리는 seq num의 패킷을 수신하였고, 이전에 수신한 패킷에 대해 모두 ACK를 전송했으면,
    해당 패킷에 대한 ACK를 즉시 보내지 않고 기다린다.(500ms 정도)
    기다려도 다음 패킷이 오지 않으면 ACK를 전송한다.
  •  
  • 기다리는 seq num의 패킷을 수신했고, 바로 전에 수신한 패킷에 대해 ACK를 보내지 않았으면,
    (즉, ACK를 보내지 않은 패킷이 2개 쌓였으면) 즉시 ACK를 전송한다.
  •  
  • 기다리는 seq num보다 큰 seq num의 패킷이 도착하면(gap이 발견되면), 즉시 중복된 ACK를 전송한다.
  •  
  • gap에 해당하는 패킷을 수신하면 즉시 ACK를 전송한다.
• 복잡해 보이지만, 이전에 보았듯 누적 ACK는 일일이 다 보낼 필요가 없다는 점에 기인한 동작이다.
  2개의 패킷에 대해 하나의 누적 ACK로 묶어서 보낸다고 이해하면 쉽다.

 

 

real TCP 시나리오

real tcp 시나리오

①

Receiver가 기다리는 seq num의 패킷이 도착했고,

바로 이전에 ACK를 보내지 않은 패킷이 있으므로 즉시 ACK를 전송한다.

 

②

Receiver가 기다리는 seq num의 패킷이 도착했지만 이전에 모든 패킷에 대해 누적 ACK를 보냈으므로

즉시 ACK를 전송하지 않고 기다린다. 500ms가 지나도 다음 패킷이 오지 않으므로 ACK를 전송한다.

 

③

p50을 수신하기 전에 p60이 도착했으므로 즉시 누적 ACK를 전송한다.

Sender 측에서는 일단 a50이 도착했으므로 send base를 변경해 패킷을 전송한다.

하지만 Receiver측은 여전히 p50을 수신하지 못했으므로 중복 ACK를 전송한다.

 

④

Sender측에서 timeout이 발생하여 패킷을 재전송한다.

Receiver 측은 수신하지 못했던 p50을 수신했으므로 즉시 ACK를 전송한다.

 

 

 

+)

포스트에서는 GBN, Selective Repeat와의 구분을 위해 real TCP라 표현했지만, 진짜 이름은 아니다.

그저 실제 TCP의 동작일 뿐이므로 TCP가 맞는 표현이다.