reliable data transfer (rdt 1.0, 2.0, 2.1, 2.2, 3.0) | Notes

신뢰성 있는 데이터 전송 문제는 네트워킹에서 중요한 주제이다. 이 문제가 전송 계층 뿐만 아니라 링크 계층, 애플리케이션 계층에서도 발생할 수 있는 문제이기 때문이다. 네트워킹에서 가장 중요한 문제들 중 Top 10을 만든다면, 이 문제가 최상위에 위치할 후보일 것이다.

이후 TCP를 살펴볼 때, TCP가 이 섹션에서 설명하는 원칙들을 어떻게 활용하는지 확인할 수 있을 것이다. TCP를 위한 빌드업이라고 보면 될 것 같다.

애플리케이션과 같은 상위 계층이 원하는 것은 간단하다. "내 데이터를 정확하게, 손실 없이, 순서대로 상대방에게 전달해 달라"는 것이다. 이것이 바로 '신뢰성 있는 채널'이 제공하는 서비스다.

하지만 실제 네트워크 환경은 완벽하지 않다. 데이터 전송 중에 비트가 손상되거나, 패킷이 완전히 사라지거나, 순서가 뒤바뀔 수 있다. 이런 불완전한 환경에서도 마치 완벽한 채널처럼 동작하도록 만드는 것이 '신뢰성 있는 데이터 전송 프로토콜'의 역할이다.

당연하게도 이 다음 절에서 다룰 것이 신뢰적인 데이터 전송 원리가 적용된 TCP다. TCP는 패킷 손실이나 오류가 발생할 수 있는 IP 네트워크 위에서 동작하면서도, 웹 브라우저나 이메일 앱에게는 안정적인 데이터 전송을 보장한다.

이 원리들을 이야기하면서 가지고 있을 한 가지 가정은 패킷이 보낸 순서대로 전달되고(일부 패킷은 손실될 수 있음), 기본 채널이 패킷 순서를 재정렬하지 않는다는 것이다.

이 섹션에서는 '단방향 데이터 전송'만 다룬다. 즉, 실제 정보(파일, 메시지 등)는 송신자에서 수신자 방향으로만 흐른다고 가정한다. 하지만 '데이터'는 한 방향으로만 전송되더라도, '제어 메시지'는 양방향으로 오간다는 것이다. 데이터 패킷이 제대로 도착했는지 확인하는 응답(ACK), 손상된 패킷을 알리는 부정 응답(NAK) 등의 제어 메시지는 수신자에서 송신자로 전송되어야 하기 때문이다. 따라서 rdt 프로토콜은 실제로는 양쪽 모두 패킷을 보내고 받을 수 있어야 한다.

📡 rdt 1.0

rdt 1.0은 가장 단순한 상황을 가정한다. 기본 채널이 완벽하게 신뢰할 수 있는 경우다. 다시 말해, 비트 오류, 패킷 손실, 순서 변경이 전혀 발생하지 않는 이상적인 상황이다.

송신자와 수신자 모두 단 하나의 상태만 가진 매우 단순한 FSM으로 표현된다. 왜냐하면 아무런 문제가 발생하지 않는다고 가정하기 때문이다.

송신자의 동작

상위 계층에서 데이터 전송 요청이 오면(rdt_send(data))
데이터를 포함한 패킷을 생성하고(make_pkt(data)),
그 패킷을 채널로 보낸다(udt_send(packet)).

수신자의 동작

하위 채널에서 패킷을 받으면(rdt_rcv(packet))
패킷에서 데이터를 추출하고(extract(packet, data)),
그 데이터를 상위 계층에 전달한다(deliver_data(data)).

이 때 완벽한 채널을 가정하므로 수신자가 송신자에게 어떤 피드백도 보낼 필요가 없다. 데이터와 패킷 사이에 차이가 없고, 모든 패킷은 송신자에서 수신자로만 흐른다. 이 때, 수신자는 송신자가 보내는 속도를 따라갈 수 있다고 가정한다.

rdt 1.0은 실제로는 사용할 수 없는 이상적인 모델이지만 더 복잡한 프로토콜을 이해하기 위한 기본 출발점으로서 의의가 있다. 이후 rdt 버전들은 실제 네트워크에서 발생하는 다양한 문제(비트 오류, 패킷 손실)를 다루기 위해 점진적으로 더 복잡해진다.

📡 rdt 2.0

1.0보다 더 현실적인 채널 모델은 어떤 형태가 있을까? 바로 패킷의 비트가 손상되는 경우다. 이런 비트 오류는 패킷이 전송, 전파 또는 버퍼링될 때 네트워크의 물리적 구성 요소에서 주로 발생한다. 여전히 모든 패킷은 보낸 순서대로 수신된다고 가정하지만 비트는 손상될 수 있다.

예를 들어 전화로 메시지를 받아쓰는 상황을 생각해보자. 일반적으로 받아쓰는 사람은 문장을 듣고 이해한 후 "OK"라고 응답한다. 만약 잘 안들리면 "다시 말해주세요"라고 요청할 것이다. 이 과정은 긍정 응답과 부정 응답을 모두 사용한다. 이렇게 해서 수신자는 무엇이 올바르게 수신되었는지, 아니면 오류로 수신되어 반복이 필요한지 송신자에게 알릴 수 있다.

컴퓨터 네트워크에서 이러한 재전송 기반 프로토콜을 ARQ $_{Automatic \space Repeat \space reQuest}$ (자동 재전송 요구) 프로토콜이라고 한다.

비트 오류를 처리하기 위해 ARQ 프로토콜에는 세 가지 추가 기능이 필요하다.

오류 검출 수신자가 비트 오류를 감지할 수 있는 메커니즘이 필요하다. 체크섬 필드가 이 목적으로 사용된다.
수신자 피드백 송신자와 수신자는 일반적으로 서로 다른 시스템에서 실행되므로 수신자의 상황(패킷이 올바르게 수신되었는지 여부)을 송신자가 알 수 있는 유일한 방법은 수신자가 명시적인 피드백을 제공하는 것이다. 예시로 ACK(긍정 응답)과 NAK(부정 응답) 메시지가 있다.
재전송 수신자가 오류로 수신한 패킷은 송신자가 재전송한다.

그래서 rdt 2.0는 오류 감지, 긍정 응답(ACK), 부정 응답(NAK) 세 가지를 채택해 사용한다.

송신자 측 동작

송신자는 두 가지 상태를 가진다.
- 첫 번째 상태에서는 상위 계층으로부터 데이터를 기다린다.
  - 데이터가 도착하면 체크섬과 함께 패킷을 만들어(make_pkt(data, checksum)) 전송(udt_send(sndpkt))한다.
- 두 번째 상태에서는 수신자로부터 ACK 또는 NAK을 기다린다.
  - ACK를 받으면 다시 첫 번째 상태로 돌아가 새 데이터를 기다린다.
  - NAK을 받으면 마지막 패킷을 재전송(udt_send(sndpkt))하고 ACK/NAK을 기다린다.

수신자 측 동작

수신자는 하나의 상태만 가진다.
- 패킷이 도착(rdt_rcv(rcvpkt))하면 손상 여부를 확인(corrupt(rcvpkt))한다.
- 패킷이 올바르면(notcurrupt(rcvpkt)) ACK을 보낸다.
- 패킷이 손상되었으면 NAK을 보낸다(udt_send(NAK)).

(수신자 측 동작) 패킷이 손상되었으면 NAK을 보낸다. 그림에서 receiver 위에 udt_send(NAK) 참고하면 된다.

하지만 rdt 2.0에는 심각한 문제가 있다. rdt 2.0에서는 ACK나 NAK 패킷 자체가 손상될 수 있다는 가능성을 고려하지 않았다. 이 경우 송신자는 수신자가 마지막 데이터를 올바르게 받았는지 여부를 알 수 없게 된다.

📡 rdt 2.1, 2.2

이 문제를 해결하기 위해 rdt 2.1에서는 sequence number(시퀀스 번호)라는 새로운 필드를 도입한다. 송신자는 데이터 패킷에 번호를 부여하고, 수신자는 이 번호를 확인해 패킷이 재전송인지 새 패킷인지 판단할 수 있다. 전송 후 대기(stop-and-wait) 프로토콜에서는 1비트 시퀀스 번호(0 또는 1)로 충분하다.

rdt 2.2는 NAK을 사용하지 않고 ACK만 사용하는 방식으로 더 발전했다. 손상된 패킷을 받으면 수신자는 NAK을 보내는 대신, 마지막으로 올바르게 수신한 패킷에 대한 ACK를 보낸다. 송신자가 동일한 패킷에 대해 ACK를 두 번 받으면(중복 ACK), 그 이후 패킷이 올바르게 수신되지 않았다고 판단할 수 있다.

이러한 방식으로 RDT 프로토콜은 비트 오류가 있는 채널에서도 신뢰성 있는 데이터 전송을 제공할 수 있게 된다.

📡 rdt 3.0

지금까지 살펴본 채널은 비트를 손상시킬 수 있었지만, 패킷 자체가 손실되는 경우는 고려하지 않았다. 그러나 현실에서의 컴퓨터 네트워크에서는 당연하게도 패킷 손실이 흔하게 발생한다. 따라서 프로토콜은 패킷 손실을 어떻게 감지하고, 패킷 손실이 발생했을 때 어떻게 대처할 지에 대한 두 가지 문제를 추가적으로 해결해야 한다.

패킷 손실 감지 및 복구 방법

패킷 손실 문제를 해결하기 위한 여러 접근법이 있지만, rdt 3.0에서는 송신자에게 패킷 손실 감지와 복구의 책임을 부여한다.

송신자가 데이터 패킷을 전송한다.
해당 패킷이나 수신자의 ACK가 손실되면, 송신자는 수신자로부터 아무런 응답을 받지 못한다.
일정 시간 기다린 후에도 응답이 없으면, 송신자는 패킷이 손실되었다고 판단하고 패킷을 재전송한다.

타이머의 도입

핵심 질문은 "송신자가 얼마나 오래 기다려야 하는가?"다. 이론적으로는 송신자와 수신자 간의 왕복 지연 시간(RTT) 이상을 기다려야 한다. 하지만 많은 네트워크에서 최악의 경우 지연 시간을 정확히 예측하기 어렵다.

실제로는 적절한 타임아웃 값을 선택해 그 시간 내에 ACK가 도착하지 않으면 패킷 손실이 발생했다고 가정하고 재전송한다. 이 접근법의 단점은 패킷이 단순 지연되었을 경우에도 재전송될 수 있어 중복 패킷이 발생할 수 있다는 점이다. 다행히 rdt 2.2에서 도입한 sequence number가 중복 패킷 문제를 처리할 수 있다.

타이머 기반 재전송 메커니즘을 구현하려면 송신자는 아래와 같은 기능이 필요하다.

패킷을 보낼 때마다 타이머 시작
타이머 인터럽트에 대응(적절한 조치 수행)
타이머 중지

rdt 3.0은 비트 오류와 패킷 손실이 모두 발생할 수 있는 채널에서 데이터를 안정적으로 전송하는 프로토콜이다.

송신자 측 동작

송신자는 4가지 상태를 가진다.
- Wait for call 0 from above (상위 계층으로부터 호출 0 대기)
  - 데이터가 도착하면(rdt_send(data)) 시퀀스 번호 0, 데이터, 체크섬을 포함한 패킷을 만들어(make_pkt(0, data, checksum)) 전송하고(udt_send(sndpkt)) 타이머를 시작(start_timer)한다.
  - ‘ACK 0 대기 상태’로 전환한다.
- Wait for ACK 0 (ACK 0 대기)
  - 올바른 ACK 0을 받으면(rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 0)) 타이머를 중지(stop_timer)하고 ‘상위 계층으로부터 호출 1 대기’ 상태로 전환한다.
  - 손상된 ACK나 ACK 1을 받으면(rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 1))) 무시하고 계속 기다린다.
  - 타임아웃이 발생하면(timeout) 마지막 패킷을 재전송하고 타이머를 다시 시작한다.
- Wait for call 1 from above (상위 계층으로부터 호출 1 대기)
  - 데이터가 도착하면(rdt_send(data)) 시퀀스 번호 1, 데이터, 체크섬을 포함한 패킷을 만들어(make_pkt(1, data, checksum)) 전송하고(udt_send(sndpkt)) 타이머를 시작한다.
  - ‘ACK 1 대기’ 상태로 전환한다.
- Wait for ACK 1 (ACK 1 대기)
  - 올바른 ACK 1을 받으면(rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 1)) 타이머를 중지하고 ‘상위 계층으로부터 호출 0 대기’ 상태로 전환한다.
  - 손상된 ACK나 ACK 0을 받으면(rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 0))) 무시하고 계속 기다린다.
  - 타임아웃이 발생하면(timeout) 마지막 패킷을 재전송하고 타이머를 다시 시작한다.

수신자 측 동작

수신자는 이전 버전과 마찬가지로 올바른 패킷에 ACK를 보내고, 손상된 패킷은 무시한다.

패킷 시퀀스 번호가 0과 1 사이에서 번갈아 가기 때문에 rdt 3.0은 alternating-bit protocol이라고도 한다.

RDT 3.0 프로토콜의 동작 예시

[정상 작동]

송신자가 packet 0을 보냄
- 수신자가 packet 0을 받고 ACK 0으로 응답
송신자가 ACK 0을 받고 packet 1을 전송
- 수신자가 packet 1을 받고 ACK 1으로 응답
송신자가 ACK 1을 받고 다시 packet 0을 전송
- 수신자가 packet 0을 받고 ACK 0으로 응답
- … 이후 과정 반복

[packet loss 시나리오]

송신자가 packet 1을 보냈으나 전송 중 손실됨
timeout 발생 후 송신자가 packet 1을 재전송
- 수신자가 packet 1을 받고 ACK 1으로 응답
송신자가 ACK 1을 받고 다음 packet으로 진행

[ACK loss 시나리오]

송신자가 packet 1을 보내고 수신자가 ACK 1으로 응답했으나 ACK가 손실됨
timeout 발생 후 송신자가 packet 1을 재전송
- 수신자가 중복 packet을 감지하고 다시 ACK 1을 전송
송신자가 ACK 1을 받고 다음 packet으로 진행

[조기 timeout 시나리오]

송신자가 packet 1을 보내고 조기에 timeout 발생
송신자가 packet 1을 재전송했으나 원래의 packet 1도 수신자에게 도착
- 수신자는 첫 번째 packet 1에 ACK 1로 응답
- 수신자는 중복된 두 번째 packet 1을 감지하고 다시 ACK 1을 전송
결국 송신자는 ACK 1을 받고 다음 패킷으로 진행

이제 데이터 전송 프로토콜의 핵심 요소를 모두 갖추게 되었다.

checksum 데이터 손상 감지
sequence number 중복 패킷 식별
timer 패킷 손실 감지
ACK/NAK 수신 상태 피드백

이 메커니즘들이 모두 함께 작동해 신뢰성 있는 데이터 전송 프로토콜이 완성되었다.

결국에는 데이터를 연속으로 보내야 한다. 근데 stop-and-wait은 이름에서도 볼 수 있듯 기다리는 단계가 있다. 그래서 속도를 올리기 위해서는 이러한 단계를 줄이는 것이 중요하다고 볼 수 있다.

📡 파이프라인된 reliable data transfer 프로토콜

rdt 3.0은 기능적으로는 정확한 프로토콜이지만, 요즘의 네트워크 환경에서는 성능이 제한될 수 있다.

stop-and wait 프로토콜의 성능 한계를 이해하기 위해 미국 서부와 동부에 위치한 두 호스트를 예로 들어보자. 이 두 시스템 간의 빛의 속도에 따른 왕복 전파 지연은 약 30밀리초이다. 1Gbps의 전송 속도를 가진 채널로 연결되어 있고, 패킷 크기나 헤더와 데이터를 포함해 1,000 bytes라고 가정하면 패킷을 전송하는 데 필요한 시간은

d_{trans} = \frac{L}{R} = \frac{8000 \space bit}{10^9 \space bits/sec} = 8 \space microseconds

이다.

즉, 30.008ms 중 송신자는 단 0.008ms 동안만 전송하고 있다. 송신자(또는 채널)의 활용률을 채널에 비트를 실제로 전송하는 시간의 비율로 정의하면 stop-and-wait 프로토콜의 송신자 활용률은

U_{sender} = \frac{L/R}{RTT+L/R} = \frac{.008}{30.008} = 0.00027

이다. 즉 송신자는 전체 시간의 단 0.027%만 활성화되어 있다. 송신자는 30.008밀리초동안 단 1,000 바이트만 보낼 수 있다. 만약 통신사에서 1Gbps 요금제를 내면서 원활한 환경 속에서 사용할 수 있음에도 실질적으로 처리량이 267kbps밖에 되지 않는다. 결국에는 네트워크 프로토콜이 기본 네트워크 하드웨어 성능을 제한하게 된다.

파이프라이닝

해결책은 의외로 간단하다. stop-and-wait 방식으로 작동하는 대신, 송신자가 확인 응답을 기다리지 않고 여러 패킷을 전송할 수 있도록 허용하는 것이다.

만약 위 그림처럼 송신자가 확인 응답을 기다리기 전에 세 개의 패킷을 전송할 수 있다면, 송신자의 활용률은 세 배가 된다.

여러 송-수신자 간 전송 중인 패킷이 파이프라인을 채우는 것처럼 시각화할 수 있어서, 파이프라이닝 $_{pipelining}$ 이라 알려져 있다. 파이프라이닝은 아래와 같은 영향을 미친다.

각 전송 중인 패킷(재전송 제외)은 고유한 시퀀스 번호를 가져야 하고, 여러 전송 중인 확인되지 않은 패킷이 있을 수 있다.
프로토콜의 송신자와 수신자 측은 하나 이상의 패킷을 버퍼링해야 할 수 있다.
- 송신자가 여러 패킷을 연속해서 보냈을 때, 아직 ACK를 받지 못 한 패킷들은 메모리에 저장해두어야 한다. 왜냐하면 이 패킷들이 네트워크에서 유실될 경우 다시 보내야 하기 때문이다.
- 수신자도 받은 패킷들을 임시로 저장해야 할 수 있다. 특히 패킷이 순서대로 도착하지 않았을 때, 순서대로 상위 계층에 전달하기 위해 버퍼링이 필요하다.
필요한 시퀀스 번호 범위와 버퍼링 요구 사항은 데이터 전송 프로토콜이 손실, 손상, 과도하게 지연된 패킷에 대응하는 방식에 따라 달라진다. 파이프라인 오류 복구에 대해 Go-Back-N과 Selective Repeat이라는 두 가지 접근법이 있다.

이렇듯 파이프라이닝 기법은 네트워크 링크의 활용도를 향상시키지만, 오류 제어를 위해 복잡한 메커니즘이 필요하다.

마무리

여기까지 살펴본 rdt 프로토콜은 TCP를 어떻게 구성할지 완성하기 위한 조각들을 맞춰가는 과정이었다. 완벽한 채널을 가정한 rdt 1.0, 비트 오류를 다룬 2.x, 패킷 손실까지 고려한 rdt 3.0까지 각 단계는 실제 상황에서의 네트워크가 얼마나 복잡하고 예측 불가능한지를 보여주면서도 그 안에서도 어떻게 신뢰성을 만들어낼 수 있는지를 설명해줬다.

결국 rdt를 통해 하고 싶었던 것은 상대방에게 데이터를 정확하게, 빠짐없이, 순서대로 보내고 싶은 하나만의 목표를 가지고 발전했다. 당연하지만 절대로 당연하지 않은 요구를 만족시키기 위해 수많은 고민과 기법들이 쌓여왔다. rdt는 그 첫걸음이고 다음에 살펴보게 될 TCP는 그 고민이 쌓여서 만들어낸 결과물이다.

rdt를 이해했다면, TCP도 분명 덜 낯설게 느껴질 것이다. 왜 ACK를 쓰는지, 타이머가 필요한지, sequence number가 중요한지에 대한 답이 이미 다 있었다.