[Transport Layer] Go-Back-N & Selective Repeat

둘 다 Sliding Window를 이용해 패킷을 전송하는 방식으로, 쪼개진 데이터가 다시 합쳐졌을 때 보낸 그대로(in order) 해석 될 수 있도록 보장한다.

또한 두 ARQ 모두 Pipelining을 통해 N개(Window Size만큼)의 패킷이 ACK 없이 receiver로 전달될 수 있다. (오해의 소지가 있으므로 아래에서 다시 풀어서 설명하도록 하겠다.)

두 프로토콜의 속성을 간단하게 살펴보면 다음과 같다.

Go-Back-N (GBN)

• Sender는 크기가 N인 Window, Window의 시작점인 Window Base, 다음에 보낼 프레임 번호인 Sequence number(이하 보낼 Seq#), 세 가지로 구성된다.
• Receiver는 이번에 받을 프레임 번호를 나타내는 Next Sequence#(이하 받을 Seq#)을 지닌다.
• Receiver 에서 누적 ACK (Cumulative ACK)를 사용한다.
• Timeout은 각 프레임이 전송될 때 Ack를 받지 못한 가장 오래된 패킷을 기준으로 한다.
• Timeout 발생 시 window에 있는 모든 패킷을 다시 전송한다.

다음으로

Selective Repeat (SR)

• Sender는 크기가 N인 Window, Window의 시작점인 send_base, Seq#, 세 가지로 구성된다.
• GBN과 다르게 Receiver도 window를 가진다. 따라서 Receiver Window의 시작점인 rcv_base를 가진다.
• Receiver 에서 누적 ACK (Cumulative ACK)를 사용한다.
• 각 패킷이 전송될 때를 기준으로 각 패킷당 경과시간을 기준으로 Timeout을 판단한다.

Go-Back-N

GBN의 Receiver Side를 우선 설명하면, Receiver는 NextSeq#에서 in-order로 (1,2,3,..와 같이) 중간에 끊김 없이 전달된 Seq# 중 최대+1을 받을 Seq#로 관리한다.

 

아래 그림을 예로 들자.

Transport Layer 3-50, All material copyright 1996-2016, J.F Kurose and K.W. Ross, All Rights Reserved

만약 보낼 Seq# = 2인데, 2번 패킷이 손실등이 일어나, 2번 패킷 이전에, Seq# = 3인 패킷이 도착한다면, 예외가 발생한 경우이다.

이 때, GBN은 out of order Seq# 패킷은 버리고, in-order로(정상적으로) 받은 패킷 중 Seq#가 가장 큰 번호를 ACK로 보낸다. (따라서 중복 ACK가 발생할 수 있다.)

 

GBN속성에서 Timeout 관련 동작은 다음과 같다.

Timeout은 각 프레임이 전송될 때 Ack를 받지 못한 가장 오래된 패킷을 기준으로 한다.
Timeout 발생 시 window에 있는 모든 패킷을 다시 전송한다.

위 경우에서 Receiver의 ACK를 받지 못한 (보낸지) 가장 오래된 패킷은 2번 패킷이다. 따라서 Receiver로 전달되지 않아 ACK를 받지 못한 2번 패킷에서 Timeout이 발생했고, GBN은 Window에 있는 모든 패킷을 다시 전송한다.

(Receiver에서 잘 받았든 못받았든, 모두 다시 재전송한다.)

 

* Window 이동에 관하여 서술하지 않았는데,  Sender Side의 동작을 설명하며 서술하겠다.

 

Sender Side는 단순히 Window에 포함된 패킷을 보내는 일 이외에도, Window의 위치(send_base) 조정을 한다.

GBN은 보낼 Seq#를 통해 in-order로 패킷을 전송한다. Receiver Side에서도 받을 Seq#에 잘 맞게 정상적으로 패킷이 도착한다면, 알맞은 ACK(정상적으로 받은 ACK중 최대)를 보내게 된다. 

 

일이 잘 진행된다면, Sender Side의 Window에는 ACK를 받은 패킷들이 놓이게 되는데, 

Transport Layer 3-47

다음과 같은 경우, nextseqnum-1을 새로운 send_base로 둘 수 있다. 

(이미 보내서 ACK를 받은 패킷들을 재전송할 필요는 없으므로)

 

 

SR

 

Selective Repeat의 딜레마