본 포스팅은 James Kurose, Keith Ross의 Computer Networking: A Top-Down Approach (6th Edition) 교재를 기반으로 정리한 내용입니다.

1. 신뢰적 데이터 전송이란

하위 채널(네트워크 계층)이 **비신뢰적**이더라도, 상위 계층에는 **신뢰적 전송**을 제공하는 것이 목표다.

애플리케이션 계층: "데이터가 확실히 도착할 거야"

↕ 신뢰적 채널 (추상화)

전송 계층(rdt): 신뢰성을 보장하는 프로토콜 구현

↕ 비신뢰적 채널 (현실)

네트워크 계층: 패킷 손실, 비트 오류 발생 가능

1.1 인터페이스

송신 측:

rdt_send(data) ← 상위 계층이 데이터 전달

udt_send(packet) ← 비신뢰적 채널로 패킷 전송

수신 측:

rdt_rcv(packet) ← 비신뢰적 채널에서 패킷 수신

deliver_data(data) ← 상위 계층에 데이터 전달

2. 단계별 프로토콜 구축

2.1 rdt 1.0: 완벽한 채널 위의 신뢰적 전송

가정: 하위 채널이 완벽하다 (비트 오류 없음, 패킷 손실 없음)

송신 측 FSM:

[대기] --rdt_send(data)-->

packet = make_pkt(data)

udt_send(packet)

-->[대기]

수신 측 FSM:

[대기] --rdt_rcv(packet)-->

data = extract(packet)

deliver_data(data)

-->[대기]

아무런 추가 메커니즘이 필요 없다. 현실에서는 이런 채널이 존재하지 않는다.

2.2 rdt 2.0: 비트 오류가 있는 채널

가정: 비트 오류 발생 가능, 패킷 손실은 없음

필요한 메커니즘

1. 오류 검출: 체크섬으로 비트 오류 발견

2. 피드백: 수신자가 송신자에게 결과 알림

- ACK (Acknowledgment): "잘 받았음"

- NAK (Negative Acknowledgment): "오류 발생"

3. 재전송: NAK를 받으면 패킷 재전송

이러한 프로토콜을 **ARQ (Automatic Repeat reQuest)** 프로토콜이라 한다.

rdt 2.0 동작

송신 측:

[데이터 대기] --rdt_send(data)-->

pkt = make_pkt(data, checksum)

udt_send(pkt)

-->[ACK/NAK 대기]

[ACK/NAK 대기] --rdt_rcv(pkt) && isACK(pkt)-->

-->[데이터 대기] (성공, 다음 데이터 대기)

[ACK/NAK 대기] --rdt_rcv(pkt) && isNAK(pkt)-->

udt_send(pkt) (재전송)

-->[ACK/NAK 대기]

수신 측:

[대기] --rdt_rcv(pkt) && !corrupt(pkt)-->

deliver_data(extract(pkt))

udt_send(ACK)

-->[대기]

[대기] --rdt_rcv(pkt) && corrupt(pkt)-->

udt_send(NAK)

-->[대기]

rdt 2.0의 치명적 결함

> **ACK/NAK 자체에 비트 오류가 발생하면?**

송신자가 ACK를 받았는지 NAK를 받았는지 알 수 없다!

2.3 rdt 2.1: 순서 번호 도입

해결책: **순서 번호(sequence number)** 를 추가한다.

해결 전략:

1. 손상된 ACK/NAK를 받으면 현재 패킷을 재전송

2. 수신자는 순서 번호로 중복 패킷을 구분

3. 정지-대기(stop-and-wait) 프로토콜이므로

순서 번호 0과 1이면 충분 (1비트)

rdt 2.1 송신 측 (간략):

[seq=0 대기] --rdt_send(data)-->

pkt = make_pkt(0, data, checksum)

udt_send(pkt)

-->[ACK 대기 for 0]

[ACK 대기 for 0]

--ACK 수신, 정상--> [seq=1 대기] (다음 데이터)

--NAK 수신 또는 손상--> 재전송 pkt [ACK 대기 for 0]

[seq=1 대기] ... (seq=0과 대칭)

rdt 2.1 수신 측 (간략):

[seq=0 기대]

--pkt 정상, seq=0--> deliver, ACK 전송 → [seq=1 기대]

--pkt 정상, seq=1--> 중복! ACK 전송 → [seq=0 기대] (데이터 무시)

--pkt 손상--> NAK 전송 → [seq=0 기대]

2.4 rdt 2.2: NAK 없는 프로토콜

NAK를 사용하지 않고, **이전 패킷에 대한 ACK**를 보내는 방식이다.

rdt 2.2의 핵심:

ACK에 순서 번호를 포함: ACK(0), ACK(1)

수신자가 seq=1 패킷을 기대하는데 seq=0 패킷이 도착:

→ ACK(0) 전송 (= "seq=0까지는 잘 받았는데, seq=1은 아직")

→ 송신자 입장에서 이것은 NAK와 같은 효과

송신자가 seq=1 패킷에 대해 ACK(0)을 받으면:

→ "seq=1이 제대로 안 갔구나" → 재전송

2.5 rdt 3.0: 비트 오류 + 패킷 손실

가정: 비트 오류 발생 가능, **패킷 손실도 발생** 가능

타이머 메커니즘

새로운 문제: 패킷이 완전히 사라지면 어떻게 하나?

- ACK가 영원히 오지 않음

- 송신자가 무한히 대기

해결: 타이머(Timer)!

- 패킷 전송 후 타이머 시작

- 합리적인 시간 내에 ACK가 오지 않으면 재전송

- 패킷이 손실된 게 아니라 지연된 경우?

→ 중복 패킷 발생 → 순서 번호로 처리 (이미 해결됨)

rdt 3.0 시나리오

시나리오 1: 패킷 손실 없음 (정상)

송신 수신

|--pkt(0)-->|

|<--ACK(0)--|

|--pkt(1)-->|

|<--ACK(1)--|

시나리오 2: 패킷 손실

송신 수신

|--pkt(0)--> X (손실)

| 타이머 만료

|--pkt(0)-->| (재전송)

|<--ACK(0)--|

시나리오 3: ACK 손실

송신 수신

|--pkt(0)-->|

| ACK(0) X (ACK 손실)

| 타이머 만료

|--pkt(0)-->| (재전송, 중복)

|<--ACK(0)--| (수신자는 중복 무시)

시나리오 4: 타이머 조기 만료

송신 수신

|--pkt(0)-->|

| 타이머 만료 (ACK가 아직 오는 중)

|--pkt(0)-->| (불필요한 재전송)

|<--ACK(0)--| (원래 ACK 도착)

|--pkt(1)-->|

|<--ACK(0)--| (중복 pkt(0)에 대한 ACK, 무시)

|<--ACK(1)--|

3. 정지-대기 프로토콜의 성능

rdt 3.0은 올바르게 동작하지만 성능이 매우 나쁘다.

예시: 1 Gbps 링크, RTT = 30ms, 패킷 크기 = 8000 bits

전송 지연: L/R = 8000 / 10^9 = 0.008ms = 8us

이용률(Utilization):

U = (L/R) / (RTT + L/R)

= 0.008 / (30 + 0.008)

= 0.00027

= 0.027%

1 Gbps 링크에서 실제 처리량:

0.00027 * 1 Gbps = 267 kbps ← 극도로 비효율적!

정지-대기의 시간 다이어그램:

송신 수신

|─pkt─> |

| |

| (대기) |

| |

| <─ACK──|

|─pkt─> |

| |

...

대부분의 시간을 ACK 기다리며 낭비!

4. 파이프라인 프로토콜

4.1 파이프라이닝 개념

ACK를 기다리지 않고 **여러 패킷을 연속으로 전송**한다.

정지-대기: 파이프라이닝 (윈도우=3):

|─pkt0─>| |─pkt0─>|

| 대기 | |─pkt1─>|

|<─ACK──| |─pkt2─>|

|─pkt1─>| |<─ACK0─|

| 대기 | |─pkt3─>|

|<─ACK──| |<─ACK1─|

|─pkt2─>| |<─ACK2─|

...

이용률 3배 향상!

파이프라이닝의 결과

파이프라이닝이 가져오는 변화:

1. 순서 번호 범위 증가 (1비트로는 부족)

2. 송수신 버퍼 필요 (여러 패킷 관리)

3. 오류 처리 방식 결정 필요:

├── Go-Back-N (GBN)

└── Selective Repeat (SR)

이용률 계산 (윈도우 크기 = W):

U = W * (L/R) / (RTT + L/R)

W=3 예시:

U = 3 * 0.008 / 30.008 = 0.0008 = 0.08%

(3배 향상, 하지만 여전히 낮음)

W=1000 예시:

U = 1000 * 0.008 / 30.008 = 0.267 = 26.7%

(훨씬 나아짐!)

4.2 Go-Back-N (GBN)

윈도우 개념

송신자의 순서 번호 공간:

[이미 ACK받음][전송했으나 ACK 미수신][사용 가능][사용 불가]

─────────────|──────────────────|──────────|────────

base nextseqnum base+N

윈도우 크기 = N

base: 가장 오래된 미확인 패킷

nextseqnum: 다음 전송할 패킷

GBN 송신자 규칙

GBN 송신자:

1. 상위 계층에서 데이터 요청 시:

- 윈도우가 가득 차지 않았으면 패킷 전송

- 가득 찼으면 거부 (또는 버퍼링)

2. 타이머 관리:

- 가장 오래된 미확인 패킷에 대해 하나의 타이머 사용

- 타이머 만료 시 윈도우 내 모든 미확인 패킷 재전송

3. ACK(n) 수신:

- n번까지의 모든 패킷 확인 (누적 확인: cumulative ACK)

- base = n + 1로 업데이트

GBN 수신자 규칙

GBN 수신자 (매우 단순):

- 기대하는 순서 번호의 패킷만 수용

- 순서가 맞지 않는 패킷은 모두 버림

- 마지막으로 정상 수신한 패킷의 ACK를 전송

GBN 동작 예시

윈도우 크기 N=4, 패킷 2가 손실:

송신자 수신자

|──pkt0──>| ← 수신, ACK(0) 전송

|──pkt1──>| ← 수신, ACK(1) 전송

|──pkt2──> X (손실)

|──pkt3──>| ← 순서 틀림! 버림, ACK(1) 재전송

|──pkt4──>| ← 순서 틀림! 버림, ACK(1) 재전송

|──pkt5──>| ← 순서 틀림! 버림, ACK(1) 재전송

| |

| (타이머 만료: pkt2부터 재전송)

|──pkt2──>| ← 수신, ACK(2) 전송

|──pkt3──>| ← 수신, ACK(3) 전송

|──pkt4──>| ← 수신, ACK(4) 전송

|──pkt5──>| ← 수신, ACK(5) 전송

GBN의 단점

- 하나의 패킷 오류로 **윈도우 전체를 재전송** (낭비)

- 오류율이 높으면 파이프라인이 불필요한 패킷으로 채워짐

4.3 Selective Repeat (SR)

GBN과의 차이

GBN: 오류 발생 시 윈도우 전체 재전송

SR: 오류가 발생한 패킷만 선택적으로 재전송

SR의 윈도우

송신자 윈도우:

[ACK][ACK][미확인][ACK][미확인][사용 가능]

─────────|────────────────────|─────────

base base+N

각 패킷에 대해 개별 타이머 유지!

수신자 윈도우:

[수신][미수신][수신][미수신]

─────|───────────────────|

base base+N

순서가 안 맞는 패킷도 버퍼에 보관!

SR 동작 예시

윈도우 크기 N=4, 패킷 2가 손실:

송신자 수신자

|──pkt0──>| ← 수신, ACK(0) 전송, 전달

|──pkt1──>| ← 수신, ACK(1) 전송, 전달

|──pkt2──> X (손실)

|──pkt3──>| ← 수신, ACK(3) 전송, 버퍼에 보관

|──pkt4──>| ← 수신, ACK(4) 전송, 버퍼에 보관

| |

| (pkt2 타이머 만료, pkt2만 재전송)

|──pkt2──>| ← 수신, ACK(2) 전송

| | pkt2, pkt3, pkt4 순서대로 상위에 전달

SR의 딜레마: 순서 번호 범위

윈도우 크기와 순서 번호 범위의 관계:

순서 번호 범위가 너무 작으면 새 패킷과 재전송 패킷을 구분 불가!

규칙: 순서 번호 범위 >= 2 * 윈도우 크기

(윈도우 크기 N이면, 순서 번호는 최소 2N개 필요)

5. GBN vs Selective Repeat 비교

| 기준 | Go-Back-N | Selective Repeat |

| ---------------- | ----------------------- | ------------------------ |

| 재전송 범위 | 윈도우 전체 | 손실 패킷만 |

| 수신자 버퍼 | 필요 없음 | 필요 (순서 외 패킷 보관) |

| 타이머 | 하나 (가장 오래된 패킷) | 패킷별 개별 타이머 |

| ACK 방식 | 누적 ACK | 개별 ACK |

| 구현 복잡도 | 단순 | 복잡 |

| 효율성 (오류 시) | 낮음 | 높음 |

6. 정리

신뢰적 데이터 전송 메커니즘 발전:

rdt 1.0: 완벽한 채널 → 아무것도 필요 없음

rdt 2.0: + 비트 오류 → 체크섬 + ACK/NAK

rdt 2.1: + ACK/NAK 오류 → 순서 번호

rdt 2.2: NAK 제거 → 중복 ACK 활용

rdt 3.0: + 패킷 손실 → 타이머

성능 개선:

정지-대기 → 파이프라이닝 (GBN 또는 SR)

핵심 메커니즘 요약:

├── 체크섬: 비트 오류 검출

├── ACK: 정상 수신 확인

├── 순서 번호: 중복 패킷 식별

├── 타이머: 패킷 손실 대응

└── 파이프라이닝: 이용률 향상

7. 확인 문제

패킷이 완전히 손실되면 수신자는 아무것도 받지 못하므로 ACK도 보내지 않는다. 타이머가 없으면 송신자는 ACK를 영원히 기다리게 된다. 타이머를 사용하면, 합리적인 시간이 지나도 ACK가 오지 않을 때 패킷을 **재전송**할 수 있다. 타이머가 너무 일찍 만료되면 불필요한 재전송이 발생하지만, 순서 번호 덕분에 수신자가 중복을 처리할 수 있다.

GBN 수신자는 **기대하는 순서 번호의 패킷만 수용**하고, 순서가 맞지 않는 패킷은 모두 버린다 (버퍼링 없음). 따라서 중간 패킷이 손실되면 그 뒤의 모든 패킷도 버려진다. 송신자의 타이머가 만료되면 가장 오래된 미확인 패킷부터 윈도우 내 모든 패킷을 재전송해야 한다.

순서 번호 범위가 충분히 크지 않으면, 수신자가 새로운 패킷과 재전송된 패킷을 구분할 수 없다. 예를 들어, 윈도우 크기가 3이고 순서 번호가 0, 1, 2만 있다면, ACK가 모두 손실된 상황에서 송신자가 재전송한 패킷 0을 수신자가 새로운 패킷 0으로 오인할 수 있다. 순서 번호가 최소 `2N`이면 이 혼동을 방지할 수 있다.