Computer Networking: A Top-Down Approach, 7th Edition의 번역 및 정리입니다.

1. Pipelined Reliable Data Transfer Protocols

rdt3.0은 제대로 동작은 하지만, 성능이 그리 좋다고 할 수는 없다. 매번 패킷을 제대로 받았다는 응답이 왔을 때에야 패킷을 보내기 때문에, 한 패킷을 전부 보내고 다음 패킷을 보낼 때까지 1 RTT가 걸리기 때문이다. 그렇다면 어떻게 해야할까? 방법은 간단하다. ACK을 받기 전에 여러 개의 패킷을 보낼 수 있으면 된다. 이러한 테크닉을 파이프라이닝(pipelining)이라 한다.

1. 한 번에 여러 패킷을 보내니 시퀀스 번호의 범위를 더 넓혀야 한다. 이제 1비트 시퀀스 비트로는 충분하지 않다.
2. 송수신자 모두 여러 개의 패킷을 버퍼링할 수 있어야 한다.
3. 시퀀스 번호 범위와 버퍼링 크기는 데이터 전송 프로토콜의 손실/손상/지연 패킷 대응 전략에 따라 달라진다. 기본적인 전략에는 Go-Back-N과 selective repeat이 있다.

2. Go-Back-N(GBN)

GBN 프로토콜에서는 송신자가 보낼 수 있는 최대 패킷의 개수를 N개로 제한한다. 즉 송신자는 한 번에 최대 N개의 패킷을 보낼 수 있고, 송신자의 입장에서는 시퀀스 번호를 다음과 같이 네 영역으로 나눠 볼 수 있다.

GBN은 아래와 슬라이딩 윈도우 방식으로 동작한다. 때문에 GBN을 그냥 슬라이드 윈도우 방식이라 하기도 하고, N을 윈도우 크기라고도 한다.

1. 송신자는 N개의 패킷을 순차적으로 보낸다
2. ACK을 받으면 base를 ACK + 1로 보낸다.
3. base를 옮겼을 때 윈도우 범위 내에 아직 보내지 않은 패킷이 있다면 추가로 전송한다.

Q. 왜 굳이 패킷 수를 N개로 제한하는 걸까?
A. 나중에 TCP 흐름 제어/혼잡 제어에서 다룹니다.

실제 구현에서 패킷 시퀀스 번호는 패킷 헤더의 고정 길이 필드에 담겨 있다. 시퀀스 번호 필드의 비트 수가 k일때, 시퀀스 번호의 범위는 $[0, 2^k-1]$이 되고, 오버플로우 방지를 위해 $modulo\ 2^k$를 해서 사용한다.

이제 시퀀스 번호가 1비트만으로는 충분하지 않으니, 송수신자가 이벤트에 반응하는 방식도 변해야 한다.

GBN Sender

GBN 송신자는 rdt3.0에 추가로 다음의 세 이벤트에 반응해야 한다.

1. 상위 계층에서의 호출
   상위 계층에서 rdt_send()가 호출되면, 송신자는 우선 윈도우가 가득 찼는지, 즉 아직 ACK를 받지 못한 패킷이 N개 있는지를 확인한다.

• 만약 윈도우가 가득 차지 않았다면 패킷을 만들어 전송하고, 관련된 변수를 갱신한다.
• 만약 윈도우가 가득 찼다면 송신자는 윈도우가 가득 찼다는 신호로, 상위 계층에 데이터를 그냥 반환한다.

실제 구현에서는 데이터를 버퍼에 저장만 해두고 바로 보내지는 않거나, 세마포어/플래그 등의 동기화 메커니즘을 통해 윈도우에 여유가 있을 때에만 상위 계층이rdt_send()를 호출하도록 제한하곤 한다.

2. ACK 수신
   GBN에서는 시퀀스 번호 n에 대한 ACK을 누적 ACK으로 본다. 즉 n번까지의 모든 패킷이 수신자에게 올바르게 도착했다는 뜻이다.

3. 타임아웃 이벤트
   사실 "Go-Back-N"이라는 이름 자체가, 패킷 손실/지연 시 N개의 패킷을 재전송하는 데에서 유래했다. Stop-and-Wait 방식 때와 마찬가지로 타이머를 데이터 손실 복구에 사용하는데, 타임아웃이 일어나면 송신자는 이전에 보냈지만 ACK을 받지는 못한 모든 패킷을 재전송한다.

ACK을 받았을 때 아직 전송/미확인 패킷이 있다면 타이머는 재시작되고, 더 이상 전송 중인 패킷이 없는 경우 타이머는 중지된다.

GBN Receiver

GBN 수신자가 하는 일은 더 간단하다. 데이터가 정상적으로, 순서에 맞게 도착하면 송신자에게는 ACK(n)을, 상위 계층으로는 데이터를 전달하면 된다. 그 외 패킷에 오류가 있거나 순서가 안 맞는 경우, 해당 패킷은 버리고 마지막으로 올바르게 받은 패킷에 대한 ACK을 재전송한다. 이 ACK를 받은 송신자는 ACK + 1번 패킷부터 다시 보내게 될 것이다.

---

GBN에서 한 가지 생각해 볼 것은, 왜 굳이 수신자가 순서에 맞지 않는 패킷을 모두 버리냐는 것이다. 그렇게 하는 가장 큰 이유는 일단 수신자가 복잡한 버퍼 처리를 할 필요가 없기 때문이다.

순서에 맞지 않는 패킷을 모두 버리는 방식에서 수신자는 그냥 expectedsqenum, 즉 다음으로 몇 번 패킷을 받으면 될지만 신경쓰면 된다. 기대하던 패킷 n이 아닌 n+1을 먼저 받았다면 ACK(n-1)을 보내 n번 이후의 모든 패킷을 재전송 받기만 하면 된다.

만약 위 방식이 아니라면, 순서에 맞지 않는 패킷이 오면 이를 가지고 있다가 나중에 상위 계층으로 올려보내기 위해 복잡한 버퍼 처리를 해줘야만 한다.

물론 모두 버리는 방식에 장점만 있는 건 아니다. 대표적으로는 정상적으로 수신됐지만 순서가 어긋나서 버린 패킷을 재전송 받는 과정에서 또 다시 패킷 유실이 발생할 수도 있다. 이 경우 재전송이 또 필요해지고, 이런 상황이 반복되면 네트워크 트래픽이 치솟게 될 수도 있다.

그럼에도 GBN 프로토콜에는 TCP에서 사용되는, 신뢰성 있는 데이터 전송을 위한 거의 모든 기술들이 포함되어 있다.

• 시퀀스 번호
• 누적 ACK
• 체크섬
• 타임아웃/재전송

이 기술들에 대해서는 나중에 TCP를 다룰 떄 다시 다루게 될 것이다.

3. Selective Repeat (SR)

앞서 봤듯 GBN에서도 성능 문제가 발생할 수 있는 상황이 있다.

파이프라인에 매우 많은 패킷이 존재할 수 있고, 이 중 단 하나의 패킷 오류만으로도 수많은 패킷을 (불필요하게) 재전송해야 할 수도 있다.

SR 프로토콜은 이러한 불필요한 재전송 방지를 위해 만들어진 프로토콜로, 오류가 의심되는 패킷만 골라서 재전송하는 방식이다. 이때 수신자는 올바르게 받은 각 패킷마다 개별적으로 ACK을 보내고, 여전히 슬라이딩 윈도우 방식으로 동작하기는 하지만, GBN과 달리 윈도우 안의 일부 패킷은 이미 ACK을 받았을 수도 있다.

SR 수신자의 동작 방식은 아래와 같다.

1. 패킷이 올바르게 수신되면 순서와 상관없이 ACK을 보낸다.
2. 순서가 맞지 않아도 버리지 않고 버퍼링하고 있다가
3. 이후 누락된 패킷이 도착하면, 버퍼에 저장해 둔 패킷들과 함께 순서대로 상위 계층에 전달한다.

이제 SR 송수신자의 이벤트 반응 방식을 보도록 하자.

SR Sender

1. 상위 계층에서 데이터를 받는다.
   • 상위 계층에서 데이터를 받으면 다음으로 사용할 수 있는 패킷 시퀀스 번호를 확인한다.
   • 윈도우 내에 있다면 패킷으로 만들고 전송하고, 그렇지 않으면 버퍼 처리하거나 곧바로 상위 계층으로 반환한다.
2. 타임아웃
   • 이번에도 유실된 패킷을 처리하기 위해 타이머를 사용한다.
   • 다만 이번에는 각 패킷이 각자의 논리적 타이머를 가진다. 전송에 실패한 각 패킷을 재전송해줘야 할 수 있기 때문이다.
3. ACK 수신
   • SR 송신자는 윈도우 내에 있는 패킷에 대한 ACK을 받으면 해당 패킷에 마크한다.
   • ACK이 send_base와 동일한 경우 윈도우를 옆으로 한 칸 옮기고, 윈도우 내에 아직 전송되지 않은 시퀀스 번호의 패킷이 있다면 전송한다.

SR Receiver

1. [rcv_base, rcb_base+N-1]의 시퀀스 번호를 가지는 패킷 정상 수신
   • 해당 패킷의 시퀀스 번호에 맞는 ACK을 보낸다.
   • 이전에 받았던 패킷이 아닌 경우 버퍼 처리한다.
   • 이 패킷이 rcv_base와 같은 시퀀스 번호를 가진다면 이 패킷을 포함해 이전에 버퍼처리된, 연속적인 시퀀스 번호의 패킷들을 모두 상위 계층으로 올려 보내고, 윈도우를 그만큼 옮긴다.
2. [rcv_base, rcv_base-1]의 시퀀스 번호를 가지는 패킷 정상 수신
   • 이미 수신자가 받은 ACK이기는 하지만, 다시 ACK을 보낸다.
3. 그 외의 패킷은 무시한다.

여기서 눈여겨 볼 곳은 2번이다. 왜 윈도우를 벗어난, 이미 받았던 패킷에 대한 ACK를 또 보내줘야 할까? 수신자가 어떤 경우에 그런 패킷을 받게 될지를 생각해보면 간단하다.

1. 송신자가 [0, 1, 2, 3] 패킷을 보내고, 수신자도 이를 잘 받아 각 패킷에 대한 ACK를 보냈다고 하자. 수신자의 윈도우는 이제 [4, 5, 6, 7]에 있다.
2. 그런데 ACK(2)가 도중에 유실됐다고 하자. 송신자는 ACK(0), ACK(1), ACK(3)을 받았으므로, 윈도우를 [2, 3, 4, 5]로 이동시킨다. 3번 패킷은 ACK를 받았음이 표시되어 있다.
3. 송신자는 ACK(2)를 받지 못했으므로 2번 패킷을 재전송한다.
4. 수신자의 입장에서 2번 패킷은 이미 예전에 받았던 패킷이다. 만약 수신자가 이 패킷을 그냥 무시한다면? 송신자는 ACK(2)를 영영 받지 못하고 윈도우를 옆으로 옮길 수 없게 된다.

SR에서의 윈도우 비동기 문제

송신자와 수신자의 윈도우가 항상 일치하지는 않을 수도 있다. 특히 시퀀스 번호 공간이 제한적일 때 문제가 발생할 수 있는데, 다음과 같은 경우를 생각해보자.

사용할 수 있는 시퀀스 번호에는 0, 1, 2, 3이 있고, 윈도우의 크기는 송/수신자 모두 3이다.

1. 송신자가 [0, 1, 2] 패킷을 전송하고, 수신자는 이를 정상적으로 수신해 ACK를 보낸다. 수신자의 윈도우는 [3, 0, 1]로 이동된다.
2. 이때 모든 ACK가 네트워크에서 사라졌다고 하자. 송신자는 다시 [0, 1, 2]를 보낸다.
3. 수신자는 이번에 받은 0번, 1번 패킷이 이전에 받았던 0번, 1번인지, 실제로는 4번, 5번이라 생각해도 좋을 패킷인지 알 수 없다.

이러한 혼동을 막으려면, 시퀀스 번호를 재사용하기 전에 수신자가 해당 번호를 기억하는 일이 발생하지 않도록 해야한다. 그러려면 윈도우의 크기를 아무리 커도 시퀀스 번호 공간 크기의 반을 넘지 않도록 설정해야 한다.

이번에는 윈도우의 크기가 2라 가정해보자.

1. 송신자가 [0, 1] 패킷을 전송하고, 수신자는 이를 정상적으로 수신해 ACK를 보낸다. 수신자의 윈도우는 [2, 3]으로 이동된다.
2. 이때 모든 ACK가 네트워크에서 사라졌다고 하자. 송신자는 다시 [0, 1]을 보낸다.
3. 수신자는 0번, 1번 패킷이 이전에 받았던 패킷들임을 알 수 있다. 앞서와 같은 혼동이 발생하지 않는다.