[네트워크] 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

 

Go-Back-N

파란색은 전송되는 패킷, 초록색은 응답 패킷이다.

송신자는 확인응답을 기다리지 않고 최대 허용된 수 안에서 여러 패킷을 전송할 수 있다. 

송신자 관점에서 확인응답(ACK)이 안된 가장 오래된 패킷의 순서번호를 base라고 하고, 사용되지 않은 가장 작은 순서번호를 nextseqnum으로 정의한다면, 순서번호 공간을 4개로 나누어 볼 수 있다.

 

[0, base-1] : 전송되고 확인응답이 된 패킷
[base, nextseqnum-1] : 송신되었으나 응답이 아직 안온 패킷
[nextseqnum, base+N-1] : 앞의 데이터가 도착하면 바로 전송될 수 있는 패킷 (최대 N개 까지 전송)[base+N, end]: 앞 영역에서 패킷 확인응답이 올때까지 사용될 수 없는 패킷(윈도우 바깥)

 

N이 패킷 순서번호의 범위상 크기(윈도우)라고 하는데, 윈도우는 순서번호 공간에서 오른쪽으로 이동(슬라이드)한다.

그래서 GBN 프로토콜은 슬라이딩 윈도우 프로토콜이라고 부른다. 

패킷이 한 번에 하나씩 전송되기 때문에 패킷 k가 첫번째 영역[0, base-1]에 있다면, k-1을 비롯한 k 이전 패킷들은 모두 전송되었고 확인응답이 되었다는 것을 알 수 있다. 

수신자는 패킷이 정확하게 수신되었지만 순서가 틀릴 경우 해당 패킷을 버린다. 패킷이 k+1, k 순으로 도착했다면 둘 다 버려 송신자가 k부터 다시 보내게끔 한다.

아래에 GBN 프로토콜의 작동 방식을 (내가) 이해하기 쉽게 정리해보았다.

 

<송신자>
1. 송신자는 첫 패킷을 보내고 타임아웃 타이머를 킨다.
2. 첫 패킷에 대한 응답이 오지 않아도 윈도우 크기만큼의 패킷을 순서대로 보낸다.
3. 윈도우의 맨 앞에 있는 순서번호에 해당하는 ACK이 왔을 때, 윈도우를 오른쪽으로 민다.
4. 윈도우를 이동시킬때(ACK이 도착했을때) 타임아웃을 타이머를 재시작시킨다. 
5. 패킷에 대한 응답이 오지 않아 타임아웃이 되면, 윈도우 처음부터 패킷을 다시 순서대로 보낸다.

<수신자>
1. 패킷을 받으면 해당 패킷 순서번호와 함께 ACK을 송신자에게 보낸다.
2. 가장 마지막으로 k번 패킷을 받았는데, 다음에 k+2번 패킷을 받으면 이후로 오는 패킷은 모두 버린다.
3. 마침내 k+1번 패킷을 받게 되면 순서번호와 함께 ACK을 보낸다.

 

+ 확인응답이 안 된 패킷 수를 N으로 제한하는 이유

TCP는 송신자가 수신자의 버퍼를 오퍼플로우 시키는 것을 방지하기 위해 흐름제어(속도 일치시키기)를 한다. 송신되는 세그먼트의 양을 제한하여 혼잡제어를 할 수 있다. 수신 측은 사용가능한 버퍼 공간이 얼마나 되는지 송신자에게 알려주고, 송신자는 그에 맞게 수신 윈도우 범위(N)를 조절한다.

 

 

Selective Repeat

윈도우 안의 각 패킷마다 타임아웃 타이머를 설정한다.

GBN은 패킷 하나의 오류 때문에 많은 패킷을 불필요하게 재전송한다. 그래서 SR 프로토콜은 오류가 발생된 패킷만을 송신자가 다시 전송하게 한다. 윈도우 크기 N은 확인응답이 안 된 패킷 수를 제한하는 데 사용되지만, GBN과 달리 송신자는 윈도우에서 몇 패킷에 대한 ACK을 수신할 수 있다.

SR 프로토콜에서는 수신측과 송신측 모두 윈도우를 가지고 있다. 두 윈도우는 항상 같지는 않는데, 수신측이 패킷을 받았더라도 송신측이 윈도우의 맨 앞에 있는 패킷에 대한 응답(ACK)을 받지 못하면, 송신측의 윈도우는 절대 이동하지 않는다.

오류난 패킷만 재전송한다!

송신자의 윈도우가 [0, 1, 2, 3], 수신자의 윈도우가 [0, 1, 2, 3]일때, 수신측이 0에 해당하는 패킷을 받으면 윈도우를 움직여 [1, 2, 3, 4]가 된다. 각 상황별로 정리해보면 다음과 같다. 왼쪽은 송신측의 윈도우, 오른쪽은 수신측이다.

1) 0번 패킷을 수신측이 받았을 때

[0, 1, 2, 3] [1, 2, 3, 4]

2) 0번 패킷에 대한 ACK을 송신측이 받았고, 1번 패킷을 수신측이 받지 않았을 때

[1, 2, 3, 4] [1, 2, 3, 4]

3) 1번 패킷에 대한 ACK을 받지 않고, 2번을 받았을 경우. (송신측은 움직이지 않음)

[1, 2, 3, 4] [1, 2, 3, 4]

4) 1번패킷에 대한 ACK의 타이머가 타임아웃되었을 경우 1번패킷을 재전송함.

수신측에서는 2번을 이미 받았으므로 3번으로 슬라이드.

[1, 2, 3, 4] [3, 4, 5, 6]

 

SR의 송수신측에서는 윈도우 안의 패킷들에 대해 ACK 또는 수신 데이터를 받았는지 확인하는 과정이 필요하고, 송신부에서는 윈도우 안의 각 패킷에 대해 각각의 타이머를 설정해야 한다. 

그렇다면 SR에서 ACK이 손실되면 어떻게 될까? 수신측은 데이터를 받았으니 윈도우를 옮겼는데 송신측은 타임아웃이 되어 해당 패킷을 다시 보낼 것이다. 송신자와 수신자 윈도우 사이에 동기화가 부족하면 윈도우의 한정된 범위에 도달했을 때, 수신자가 재전송된 패킷을 새로운 패킷인지 재전송된 것인지 모르게 된다. 

예를 들어 송신자가 0번 패킷의 ACK만 받지 못해 재전송할때, 수신자가 1, 2, 3의 패킷은 다 받고 윈도우를 4, 0, 1로 옮긴다면 위와 같은 문제가 발생한다. 재전송된 패킷의 번호가 윈도우 안에 있기 때문이다.

이를 해결하려면 윈도우 크기는 SR 프로토콜에 대한 순서번호 공간 크기의 절반보다 작거나 같아야 한다. (예시에서는 윈도우 크기는 3, 전체 크기는 4이다.)

 

 

TCP는 SR 프로토콜과 유사한 방식으로 작동하지만, 수신자가 순서가 맞는 세그먼트에 대해 확인응답을 하는 것보다는 GBN처럼 순서가 틀린 세그먼트에 대해 선택적으로 확인응답을 한다. 그래서 TCP의 오류 복구 메커니즘은 GBN과 SR의 혼합이라고 할 수 있다.

 

 

(참고) James F. Kurose. Computer networking a top-down approach. 7th edition