go-back-N과 selective repeat

rdt 3.0은 정확했지만 느렸습니다. 패킷 하나를 보내고 ACK가 올 때까지 손 놓고 기다리기 때문입니다. RTT가 100ms인 회선에서 이렇게 하면 링크 용량이 아무리 커도 대부분의 시간을 대기에 씁니다. 이번에는 그 낭비를 없애면서도 신뢰성을 유지하는 두 가지 방식을 알아보겠습니다.

1. 아직 확인받지 못한 채로 여러 개 보내기

해법은 단순합니다. ACK를 기다리지 않고 여러 패킷을 연달아 보내는 것입니다. 다만 무한정 보낼 수는 없습니다. 재전송에 대비해 보낸 것을 들고 있어야 하고, 받는 쪽도 감당할 수 있어야 하기 때문입니다.

그래서 "확인받지 못한 채 떠 있어도 되는 패킷 수"에 상한을 둡니다. 이것이 window size(윈도우 크기)이고, 보통 N으로 씁니다. 윈도우는 ACK가 도착할 때마다 앞으로 미끄러집니다.

sequence number의 범위도 1비트로는 부족해집니다. 떠 있는 패킷이 여러 개이므로 그들을 전부 구분할 수 있어야 합니다.

윈도우를 쓰는 방식은 크게 둘로 갈립니다. 잃어버린 패킷 하나 때문에 뒤엣것까지 모두 다시 보내느냐, 잃어버린 것만 골라 보내느냐입니다.

2. go-back-N: 틀린 지점부터 전부 다시

GBN(go-back-N)의 규칙은 세 가지입니다.

• 수신 측은 순서대로 도착한 것만 받습니다. 중간이 비면 그 뒤에 온 것은 버퍼링하지 않고 버립니다.
• ACK는 cumulative ACK(누적 확인응답)입니다. "n번까지는 다 잘 받았다"는 의미이므로, ACK 하나가 잃어버려도 뒤의 ACK가 대신 덮어줍니다.
• 타이머는 가장 오래된 미확인 패킷 하나에만 겁니다. timeout이 나면 그 패킷부터 윈도우 안의 전부를 다시 보냅니다.

수신 측이 버퍼를 갖지 않아 구현이 단순합니다. 대신 하나 잃었을 뿐인데 멀쩡히 도착했던 pkt2와 pkt3까지 버려지고 다시 전송됩니다. 윈도우가 크고 오류가 잦을수록 손해가 커집니다.

3. selective repeat: 잃어버린 것만 다시

SR(selective repeat)은 그 낭비를 없앱니다.

• 수신 측이 윈도우 범위 안의 패킷이면 순서가 어긋나도 버퍼에 저장합니다.
• ACK는 누적이 아니라 개별입니다. 받은 패킷 각각에 대해 ACK를 보냅니다.
• 타이머를 패킷마다 따로 겁니다. timeout이 난 그 패킷만 재전송합니다.
• 빠진 자리가 채워지면 버퍼에 쌓아둔 것들을 한꺼번에 상위 계층으로 올립니다.

4. 두 방식의 비교

5. selective repeat dilemma

SR에는 함정이 하나 있습니다. sequence number는 유한해서 결국 돌아옵니다. 그런데 송신 측 윈도우와 수신 측 윈도우가 같은 시점에 서로 다른 구간을 보고 있을 수 있습니다.

번호 공간이 0~3이고 윈도우 크기가 3인 경우를 보겠습니다.

1. 송신 측이 pkt0, pkt1, pkt2를 보냅니다.
2. 수신 측이 셋 다 잘 받고 ACK를 보냅니다. 수신 윈도우는 3, 0, 1로 이동합니다.
3. 그런데 ACK 세 개가 전부 유실됩니다.
4. 송신 측은 timeout으로 pkt0을 재전송합니다.
5. 수신 측의 윈도우에는 이미 새로운 0의 자리가 열려 있습니다. 재전송된 옛날 pkt0을 새 데이터로 착각해 받아들입니다.

수신 측은 두 경우를 구분할 방법이 없습니다. 패킷에는 번호만 적혀 있고 그 번호는 재사용되기 때문입니다. 이를 막으려면 윈도우 크기가 번호 공간의 절반 이하여야 합니다. 위 예에서 번호가 4개이므로 윈도우는 2 이하여야 안전합니다.

일반화하면 k비트 sequence number를 쓸 때 윈도우 크기는 2^k / 2 이하입니다. 송신 윈도우와 수신 윈도우가 절대 겹치지 않도록 번호 공간을 넉넉히 두는 것입니다.