[네트워크] RDT(reliable data transfer)의 개념과 진화, FSM 설명 - 신뢰할 수 있는 데이터 전송 프로토콜

코딩하는 동현 2025. 5. 5. 22:50

신뢰할 수 있는 데이터 전송 프로토콜(Reliable Data Transfer Protocol)

신뢰할 수 있는 데이터 전송 프로토콜(Reliable Data Transfer Protocol, RDT)은 신뢰할 수 없는 네트워크 환경에서 데이터를 안정적으로 전송하기 위한 메커니즘이다. 이는 전송 계층(Transport Layer)에서 중요한 역할을 하는 프로토콜이다.

신뢰할 수 있는 데이터 전송의 원칙(Principles of Reliable Data Transfer)

신뢰할 수 있는 데이터 전송 프로토콜의 복잡성은 신뢰할 수 없는 채널(unreliable channel)의 특성에 크게 의존한다.

채널이 데이터를 손실(lose)하거나, 손상(corrupt)시키거나, 순서를 바꾸는(reorder) 경우에 따라 프로토콜의 복잡성이 달라진다.

송신자(sender)와 수신자(receiver)는 서로의 "상태(state)"를 알지 못한다.

예를 들어, 송신자는 수신자가 메시지를 받았는지 알 수 없다. 이러한 정보는 메시지를 통해 명시적으로 전달되어야 한다.

신뢰할 수 있는 데이터 전송은 두 가지 관점에서 볼 수 있다:

1. 추상화(abstraction)

송신 프로세스(sending process)와 수신 프로세스(receiving process) 사이에 신뢰할 수 있는 채널(reliable channel)이 존재하는 것처럼 보이는 추상적 서비스 모델이다.

2. 구현(implementation)

실제로는 신뢰할 수 없는 채널(unreliable channel) 위에 신뢰할 수 있는 데이터 전송 프로토콜의 송신 측(sender-side)과 수신 측(receiver-side)이 구현되어 있다.

RDT 인터페이스(Interfaces)

RDT는 신뢰할 수 없는 채널 위에서 신뢰할 수 있는 서비스를 제공하기 위한 인터페이스를 정의한다:

rdt_send(): 상위 계층(예: 애플리케이션)에서 호출되는 함수로, 송신자에게 수신자의 상위 계층에 전달할 데이터를 전달한다.
udt_send(): RDT에 의해 호출되는 함수로, 신뢰할 수 없는 채널을 통해 수신자에게 패킷을 전송한다.
rdt_rcv(): 수신 측에서 패킷이 도착했을 때 호출되는 함수이다.
deliver_data(): RDT에 의해 호출되는 함수로, 수신 측의 상위 계층에 데이터를 전달한다.

이러한 인터페이스를 통해 양방향 통신(bi-directional communication)이 신뢰할 수 없는 채널 위에서 이루어진다. 패킷에는 헤더(header)와 데이터(data)가 포함되어 있다.

RDT 시작하기(Getting Started)

신뢰할 수 있는 데이터 전송 프로토콜을 개발하기 위해 다음과 같은 접근 방식을 취한다:

점진적으로(incrementally) 송신자와 수신자 측을 개발한다.
단방향 데이터 전송(unidirectional data transfer)만 고려하지만, 제어 정보(control info)는 양방향으로 흐른다.
유한 상태 머신(Finite State Machine, FSM)을 사용하여 송신자와 수신자를 명세한다.

유한 상태 머신에서 상태(state)는 특정 "상태"에 있음을 의미하며, 다음 상태는 다음 이벤트(event)에 의해 고유하게 결정된다.

상태 전이(state transition)는 이벤트에 의해 발생하며, 상태 전이 시 정의된 행동(actions)을 수행한다.

예를 들어, 상태 1에서 특정 이벤트가 발생하면 상태 2로 전이하면서 정의된 행동을 수행한다. 이러한 FSM 모델은 RDT 프로토콜의 송신자와 수신자의 동작을 명확하게 정의하는 데 도움이 된다.

정리

신뢰할 수 있는 데이터 전송 프로토콜(RDT)은 신뢰할 수 없는 채널 위에서 안정적인 데이터 전송을 보장하기 위한 중요한 메커니즘이다.

신뢰할 수 있는 데이터 전송의 원칙을 이해하고, RDT의 인터페이스를 명확히 정의하며, 유한 상태 머신을 통해 프로토콜의 동작을 명세함으로써 효과적인 RDT 프로토콜을 구현할 수 있다.

RDT는 인터넷의 전송 계층에서 중요한 역할을 하며, TCP와 같은 실제 프로토콜의 기반이 된다. 이러한 개념들을 이해하면 신뢰할 수 있는 데이터 전송 프로토콜의 설계와 구현을 더 깊이 이해할 수 있다.

신뢰할 수 있는 데이터 전송 프로토콜의 진화: RDT1.0과 RDT2.0

신뢰할 수 있는 데이터 전송 프로토콜(Reliable Data Transfer Protocol, RDT)은 네트워크 환경에서 데이터를 안전하게 전송하기 위한 메커니즘이다.

컴퓨터 네트워크의 전송 계층(Transport Layer)에서 중요한 역할을 하는 이 프로토콜은 여러 버전으로 발전해왔다.

RDT1.0: 신뢰할 수 있는 채널 위의 신뢰할 수 있는 전송

RDT1.0은 가장 단순한 형태의 신뢰할 수 있는 데이터 전송 프로토콜이다. 이 프로토콜은 기본적으로 다음과 같은 특성을 가진다:

기반 채널(underlying channel)이 완벽하게 신뢰할 수 있다(perfectly reliable)

비트 오류(bit errors)가 없다
패킷 손실(loss of packets)이 없다

송신자(sender)와 수신자(receiver)를 위한 별도의 유한 상태 머신(FSM)이 존재한다:

송신자는 데이터를 기반 채널로 보낸다
수신자는 기반 채널에서 데이터를 읽는다

송신자의 FSM

상위 계층(응용계층)으로부터 호출을 기다리는 상태에서 rdt_send(data) 호출이 발생하면, 패킷을 생성하고(packet = make_pkt(data)) 이를 전송한다(udt_send(packet)).

그 후 다시 호출을 기다리는 상태로 돌아간다.

수신자의 FSM

하위 계층(네트워크 계층)으로부터 호출을 기다리는 상태에서 rdt_rcv(packet) 호출이 발생하면, 패킷에서 데이터를 추출하고(extract(packet,data)) 상위 계층에 전달한다(deliver_data(data)).

RDT2.0: 비트 오류가 있는 채널

현실에서는 완벽한 채널이 존재하지 않는다. RDT2.0은 비트 오류가 발생할 수 있는 채널에서의 신뢰할 수 있는 데이터 전송을 위해 설계되었다. 이 프로토콜의 특징은 다음과 같다:

기반 채널에서 패킷의 비트가 뒤집힐 수 있다(may flip bits)
체크섬(checksum)을 사용하여 비트 오류를 감지한다

오류로부터 어떻게 복구할 것인가에 대한 해결책으로 다음과 같은 메커니즘을 사용한다:

확인응답(Acknowledgements, ACK): 수신자가 패킷을 올바르게 받았음을 송신자에게 명시적으로 알린다
부정 확인응답(Negative Acknowledgements, NAK): 수신자가 패킷에 오류가 있음을 송신자에게 명시적으로 알린다
송신자는 NAK를 받으면 패킷을 재전송(retransmits)한다

RDT2.0은 stop-and-wait 프로토콜이라고도 불린다. 송신자는 하나의 패킷을 보내고 수신자의 응답을 기다린다.

RDT2.0의 FSM 명세

RDT2.0의 송신자 FSM은 두 가지 상태로 구성된다:

1. "위로부터의 호출 대기(Wait for call from above)" 상태

상위 계층으로부터 데이터를 받기 위해 대기한다.

rdt_send(data) 호출이 발생하면, 체크섬을 포함한 패킷을 생성하고(snkpkt = make_pkt(data, checksum)) 이를 전송한 후(udt_send(sndpkt)), "ACK 또는 NAK 대기" 상태로 전환한다.

2. "ACK 또는 NAK 대기(Wait for ACK or NAK)" 상태

수신자로부터의 응답을 기다린다.

NAK를 받으면(rdt_rcv(rcvpkt) && isNAK(rcvpkt)), 같은 패킷을 다시 전송하고(udt_send(sndpkt)) 같은 상태에 머문다.
ACK를 받으면(rdt_rcv(rcvpkt) && isACK(rcvpkt)), "위로부터의 호출 대기" 상태로 돌아간다.

수신자의 "상태"(수신자가 내 메시지를 올바르게 받았는지 여부)는 송신자에게 알려지지 않는다. 이 정보는 반드시 수신자로부터 송신자에게 통신되어야 한다. 이것이 바로 프로토콜이 필요한 이유이다.

RDT2.0의 오류 없는 작동

오류가 없는 경우, RDT2.0의 작동 순서는 다음과 같다:

송신자는 rdt_send(data) 호출을 받으면, 체크섬이 포함된 패킷을 생성하고 전송한다.
수신자는 패킷이 도착하면 체크섬을 검사한다.
오류가 없는 경우(rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)), 패킷에서 데이터를 추출하고, 상위 계층에 전달한 후, ACK를 송신자에게 보낸다.
송신자는 ACK를 받으면 다음 데이터 전송을 위해 대기 상태로 돌아간다.

RDT2.0: 손상된 패킷 시나리오

패킷이 손상된 경우, RDT2.0의 작동 순서는 다음과 같다:

송신자는 rdt_send(data) 호출을 받으면, 체크섬이 포함된 패킷을 생성하고 전송한다.
수신자는 패킷이 도착하면 체크섬을 검사한다.
오류가 감지된 경우(rdt_rcv(rcvpkt) && corrupt(rcvpkt)), NAK를 송신자에게 보낸다.
송신자는 NAK를 받으면 같은 패킷을 재전송한다.

RDT2.0의 치명적 결함

RDT2.0은 치명적인 결함을 가지고 있다. ACK나 NAK가 손상되면 어떻게 될까?

송신자는 수신자에게 무슨 일이 일어났는지 알 수 없다!
단순히 재전송할 수 없다: 중복(duplicate) 패킷이 발생할 가능성이 있다

이 문제를 해결하기 위한 방법:

ACK/NAK가 손상되면 송신자는 현재 패킷을 재전송한다
각 패킷에 sequence number를 추가한다
수신자는 중복 패킷을 폐기한다(다시 전달하지 않음)

이 접근 방식은 stop-and-wait 방식이다: 송신자는 하나의 패킷을 보내고 수신자의 응답을 기다린다.

정리

신뢰할 수 있는 데이터 전송 프로토콜은 네트워크 통신의 기본이 되는 중요한 개념이다. RDT1.0에서 시작하여 RDT2.0으로 발전하면서, 우리는 비트 오류가 있는 채널에서 신뢰할 수 있는 통신을 구현하기 위한 메커니즘을 배웠다. 하지만 RDT2.0에는 ACK/NAK 손상 시 발생하는 문제와 같은 치명적인 결함이 있다. 이러한 문제를 해결하기 위해 시퀀스 번호와 같은 추가적인 메커니즘이 필요하며, 이는 더 발전된 RDT 버전에서 구현된다.

RDT2.1: 손상된 ACK/NAK 처리 메커니즘

RDT2.1은 RDT2.0의 치명적 결함을 해결하기 위해 개발된 프로토콜이다. RDT2.0에서는 ACK나 NAK가 손상되었을 때 발생할 수 있는 문제를 다루지 못했다. RDT2.1은 이 문제를 해결하기 위해 sequence number(시퀀스 번호)를 도입했다.

송신자(Sender)의 FSM 구현

RDT2.1의 송신자는 4개의 상태(state)로 구성된 유한 상태 머신(Finite State Machine)으로 구현된다:

1. "위로부터 호출 0 대기(Wait for call 0 from above)" 상태

이벤트: rdt_send(data) (상위 계층에서 데이터 전송 요청)
동작: sndpkt = make_pkt(0, data, checksum) (시퀀스 번호 0을 포함한 패킷 생성)
동작: udt_send(sndpkt) (패킷 전송)
전이: "ACK 또는 NAK 0 대기" 상태로 이동

2. "ACK 또는 NAK 0 대기(Wait for ACK or NAK 0)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) (올바른 ACK 수신)
전이: "위로부터 호출 1 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt)) (손상된 패킷 또는 NAK 수신)
동작: udt_send(sndpkt) (동일한 패킷 재전송)
전이: 같은 상태 유지

3. "위로부터 호출 1 대기(Wait for call 1 from above)" 상태

이벤트: rdt_send(data) (상위 계층에서 데이터 전송 요청)
동작: sndpkt = make_pkt(1, data, checksum) (시퀀스 번호 1을 포함한 패킷 생성)
동작: udt_send(sndpkt) (패킷 전송)
전이: "ACK 또는 NAK 1 대기" 상태로 이동

4. "ACK 또는 NAK 1 대기(Wait for ACK or NAK 1)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) (올바른 ACK 수신)
전이: "위로부터 호출 0 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt)) (손상된 패킷 또는 NAK 수신)
동작: udt_send(sndpkt) (동일한 패킷 재전송)
전이: 같은 상태 유지

수신자(Receiver)의 FSM 구현

RDT2.1의 수신자는 2개의 상태로 구성된 FSM으로 구현된다:

1. "아래로부터 0 대기(Wait for 0 from below)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) (올바른 시퀀스 0 패킷 수신)
동작: extract(rcvpkt,data) (데이터 추출)
동작: deliver_data(data) (상위 계층에 데이터 전달)
동작: sndpkt = make_pkt(ACK, chksum) (ACK 패킷 생성)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: "아래로부터 1 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && corrupt(rcvpkt) (손상된 패킷 수신)
동작: sndpkt = make_pkt(NAK, chksum) (NAK 패킷 생성)
동작: udt_send(sndpkt) (NAK 패킷 전송)
전이: 같은 상태 유지

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) (잘못된 시퀀스 번호 패킷 수신)
동작: sndpkt = make_pkt(ACK, chksum) (ACK 패킷 생성)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: 같은 상태 유지

2. "아래로부터 1 대기(Wait for 1 from below)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) (올바른 시퀀스 1 패킷 수신)
동작: extract(rcvpkt,data) (데이터 추출)
동작: deliver_data(data) (상위 계층에 데이터 전달)
동작: sndpkt = make_pkt(ACK, chksum) (ACK 패킷 생성)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: "아래로부터 0 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && corrupt(rcvpkt) (손상된 패킷 수신)
동작: sndpkt = make_pkt(NAK, chksum) (NAK 패킷 생성)
동작: udt_send(sndpkt) (NAK 패킷 전송)
전이: 같은 상태 유지

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) (잘못된 시퀀스 번호 패킷 수신)
동작: sndpkt = make_pkt(ACK, chksum) (ACK 패킷 생성)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: 같은 상태 유지

RDT2.1의 핵심 메커니즘

RDT2.1은 다음과 같은 핵심 메커니즘을 통해 손상된 ACK/NAK를 처리한다:

시퀀스 번호(Sequence Number) 사용:
- 각 패킷에 시퀀스 번호(0 또는 1)를 부여한다
- 이를 통해 수신자는 중복 패킷을 식별할 수 있다
패킷 손상 처리:
- 송신자: 손상된 ACK/NAK를 받으면 패킷을 재전송한다
- 수신자: 손상된 패킷을 받으면 NAK를 보낸다
잘못된 시퀀스 번호 처리:
- 수신자는 잘못된 시퀀스 번호의 패킷을 받으면 이를 중복으로 인식하고 해당 시퀀스에 대한 ACK를 보낸다
- 이를 통해 송신자는 수신자의 현재 상태를 알 수 있다

이러한 메커니즘을 통해 RDT2.1은 손상된 ACK/NAK 문제를 효과적으로 해결한다. 하지만 여전히 패킷 손실이 발생하는 채널에서는 문제가 발생할 수 있으며, 이는 후속 버전인 RDT3.0에서 해결된다.

RDT2.1: 논의(Discussion)

RDT2.1 프로토콜의 중요한 특징들을 송신자와 수신자 측면에서 살펴보겠다.

송신자(Sender) 측면

RDT2.1에서 송신자는 다음과 같은 특징을 가진다:

패킷에 sequence number(시퀀스 번호)가 추가된다
두 개의 시퀀스 번호(0, 1)만으로도 충분하다. -> stop-and-wait 방식으로 동작하기 때문이다
수신된 ACK/NAK가 손상(corrupted)되었는지 확인해야 한다
RDT2.0보다 두 배 많은 상태(states)가 필요하다
- 상태는 "예상되는" 패킷이 시퀀스 번호 0인지 1인지 "기억(remember)"해야 한다

RDT2.1에서는 패킷에 시퀀스 번호를 추가함으로써 중복 패킷을 식별할 수 있게 된다.

오직 두 개의 시퀀스 번호(0과 1)만으로도 충분한 이유는 stop-and-wait 방식으로 동작하기 때문이다.

한 번에 하나의 패킷만 전송하고 그 응답을 기다리기 때문에, 수신자는 현재 패킷과 직전 패킷만 구분할 수 있으면 된다.

수신자(Receiver) 측면

RDT2.1에서 수신자는 다음과 같은 특징을 가진다:

수신된 패킷이 중복(duplicate)인지 확인해야 한다
- 상태는 예상되는 패킷 시퀀스 번호가 0인지 1인지 나타낸다
중요한 점: 수신자는 자신이 마지막으로 보낸 ACK/NAK가 송신자에게 올바르게 수신되었는지 알 수 없다(not know)

수신자는 자신의 상태를 통해 어떤 시퀀스 번호(0 또는 1)의 패킷을 기대하고 있는지 기억한다. 만약 기대하는 번호와 다른 패킷이 도착하면, 이는 중복 패킷으로 간주하고 데이터를 상위 계층에 전달하지 않고 해당 패킷에 대한 ACK만 보낸다.

RDT2.2: NAK 없는 프로토콜(a NAK-free protocol)

RDT2.2는 RDT2.1과 동일한 기능을 수행하지만, NAK를 사용하지 않고 ACK만을 사용한다.

이 프로토콜의 주요 특징은 다음과 같다:

RDT2.1과 동일한 기능을 ACK만 사용해서 구현한다
NAK 대신, 수신자는 마지막으로 올바르게 받은 패킷에 대해 ACK를 보낸다
수신자는 ACK를 보낼 때 명시적으로(explicitly) ACK 대상 패킷의 sequence number를 포함해야 한다
송신자가 중복된 ACK를 받으면 NAK를 받은 것과 동일한 동작을 수행한다: 현재 패킷을 재전송(retransmit current pkt)한다

이러한 접근 방식은 TCP가 NAK 없이 동작하는 데 사용하는 방법이다.

RDT2.2 프로토콜의 송신자와 수신자 FSM 구현

RDT2.2 프로토콜은 NAK를 사용하지 않고 ACK만을 이용하여 신뢰할 수 있는 데이터 전송을 구현한 프로토콜이다. 이 프로토콜은 RDT2.1과 동일한 기능을 수행하지만, 구현 방식에 차이가 있다.

송신자 FSM 구현

송신자 FSM(Finite State Machine)은 두 가지 주요 상태로 구성되어 있다:

1. "위로부터 호출 0 대기(Wait for call 0 from above)" 상태

이벤트: rdt_send(data) (상위 계층에서 데이터 전송 요청)
동작: sndpkt = make_pkt(0, data, checksum) (시퀀스 번호 0을 포함한 패킷 생성)
동작: udt_send(sndpkt) (패킷 전송)
전이: "ACK 0 대기" 상태로 이동

2. "ACK 0 대기(Wait for ACK 0)" 상태

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt,1)) (손상된 패킷 또는 ACK 1을 수신)
동작: udt_send(sndpkt) (동일한 패킷 재전송)
전이: 같은 상태 유지

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) (올바른 ACK 0을 수신)
전이: "위로부터 호출 1 대기" 상태로 이동 (그림에는 표시되지 않음)

수신자 FSM 구현

수신자 FSM은 다음과 같이 구성된다:

1. "아래로부터 0 대기(Wait for 0 from below)" 상태

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) (손상된 패킷 또는 시퀀스 1 패킷 수신)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: 같은 상태 유지

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) (올바른 시퀀스 1 패킷 수신)
동작: extract(rcvpkt,data) (데이터 추출)
동작: deliver_data(data) (상위 계층에 데이터 전달)
동작: sndpkt = make_pkt(ACK1, chksum) (ACK 1 패킷 생성)
동작: udt_send(sndpkt) (ACK 패킷 전송)
전이: "아래로부터 0 대기" 상태로 이동 (그림에서는 원래 1을 기다리는 상태로 가야 하지만 생략됨)

RDT2.2의 작동 원리

RDT2.2에서 패킷 손상이 감지되면, 수신자는 NAK를 보내는 대신 마지막으로 성공적으로 받은 패킷의 시퀀스 번호를 포함한 ACK를 보낸다.

예를 들어, 송신자가 시퀀스 번호 1을 가진 패킷을 보냈는데 이 패킷이 손상되었다면:

RDT2.1에서는 수신자가 NAK를 보낸다
RDT2.2에서는 수신자가 이전에 성공적으로 받은 패킷(시퀀스 번호 0)에 대한 ACK를 다시 보낸다

송신자가 시퀀스 번호 1의 패킷을 보냈는데 ACK 0을 다시 받으면, 이것은 패킷 1이 손상되었다는 것을 의미하므로 패킷 1을 재전송한다.

이 방식은 NAK를 사용하지 않고도 손상된 패킷을 처리할 수 있게 하며, 프로토콜을 단순화한다. TCP를 포함한 많은 실제 프로토콜들이 이 접근 방식을 사용한다.

RDT3.0: 오류와 손실이 있는 채널에서의 신뢰할 수 있는 데이터 전송

RDT3.0의 새로운 가정

RDT3.0은 RDT2.2에서 더 나아가 패킷 손실(packet loss)까지 처리할 수 있는 프로토콜이다.

이전 버전들은 비트 오류(bit errors)만 처리했지만, 실제 네트워크에서는 패킷이 완전히 손실되는 경우도 발생한다. RDT3.0의 새로운 가정은 다음과 같다:

기반 채널(underlying channel)은 데이터나 ACK 패킷을 손실시킬 수 있다
체크섬(checksum), 시퀀스 번호(sequence #), ACK, 재전송(retransmissions) 메커니즘만으로는 이 문제를 해결하기에 충분하지 않다

타임아웃 메커니즘

RDT3.0에서 추가된 핵심 메커니즘은 타임아웃(timeout)이다. 송신자(sender)는 패킷을 전송한 후 "합리적인 시간" 동안 ACK를 기다린다.

해당 시간 내에 ACK가 오지 않으면 패킷이 손실되었다고 판단하고 재전송한다
타이머(timer)가 만료되면 타임아웃(timeout)이 발생한다
재전송 후 타이머를 다시 시작한다

이 타이머 시간 설정이 중요한데, 타이머 시간은:

RTT(Round Trip Time)보다 길어야 한다
너무 짧으면: 불필요한 재전송이 발생할 수 있다
너무 길면: 패킷 손실 시 반응이 느려진다

RDT3.0 송신자(Sender)의 FSM

RDT3.0 송신자의 FSM은 총 4개의 상태로 구성되며, 주요 특징은 타이머(timer) 관련 동작이 추가된 것이다:

1. "위로부터 호출 0 대기(Wait for call 0 from above)" 상태

이벤트: rdt_send(data) (상위 계층에서 데이터 전송 요청)
동작: sndpkt = make_pkt(0, data, checksum) (시퀀스 번호 0을 포함한 패킷 생성)
동작: udt_send(sndpkt) (패킷 전송)
동작: start_timer (타이머 시작)
전이: "ACK 0 대기" 상태로 이동

2. "ACK 0 대기(Wait for ACK 0)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) (올바른 ACK 0 수신)
동작: stop_timer (타이머 중지)
전이: "위로부터 호출 1 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt,1)) (손상된 패킷 또는 잘못된 ACK 수신)
동작: 무시
전이: 같은 상태 유지

이벤트: timeout (타임아웃 발생)
동작: udt_send(sndpkt) (동일한 패킷 재전송)
동작: start_timer (타이머 재시작)
전이: 같은 상태 유지

3. "위로부터 호출 1 대기(Wait for call 1 from above)" 상태

이벤트: rdt_send(data) (상위 계층에서 데이터 전송 요청)
동작: sndpkt = make_pkt(1, data, checksum) (시퀀스 번호 1을 포함한 패킷 생성)
동작: udt_send(sndpkt) (패킷 전송)
동작: start_timer (타이머 시작)
전이: "ACK 1 대기" 상태로 이동

4. "ACK 1 대기(Wait for ACK 1)" 상태

이벤트: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) (올바른 ACK 1 수신)
동작: stop_timer (타이머 중지)
전이: "위로부터 호출 0 대기" 상태로 이동

이벤트: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt,0)) (손상된 패킷 또는 잘못된 ACK 수신)
동작: 무시
전이: 같은 상태 유지

이벤트: timeout (타임아웃 발생)
동작: udt_send(sndpkt) (동일한 패킷 재전송)
동작: start_timer (타이머 재시작)
전이: 같은 상태 유지

RDT3.0 동작 시나리오

RDT3.0이 다양한 상황에서 어떻게 동작하는지 살펴보자:

손실 없는 경우(No Loss)

송신자: 패킷 전송 및 타이머 시작
수신자: 패킷 수신 및 ACK 전송
송신자: ACK 수신 및 타이머 중지
다음 패킷 전송 준비

패킷 손실(Packet Loss)

송신자: 패킷 전송 및 타이머 시작
패킷 손실 발생
수신자: 아무 동작 없음
송신자: 타임아웃 발생
송신자: 패킷 재전송 및 타이머 재시작
수신자: 패킷 수신 및 ACK 전송
송신자: ACK 수신 및 타이머 중지

ACK 손실(ACK Loss)

송신자: 패킷 전송 및 타이머 시작
수신자: 패킷 수신 및 ACK 전송
ACK 손실 발생
송신자: 타임아웃 발생
송신자: 패킷 재전송 및 타이머 재시작
수신자: 중복 패킷 수신 및 ACK 재전송
송신자: ACK 수신 및 타이머 중지

조기 타임아웃/지연된 ACK(Premature Timeout/Delayed ACK)

송신자: 패킷 전송 및 타이머 시작
ACK 지연 발생
송신자: 타임아웃 발생 (ACK가 도착하기 전)
송신자: 패킷 재전송 및 타이머 재시작
송신자: 지연된 ACK 수신 (첫 번째 패킷에 대한)
수신자: 중복 패킷 수신 및 ACK 재전송
송신자: 두 번째 ACK 수신 및 타이머 중지

RDT3.0은 stop-and-wait 프로토콜로, 하나의 패킷을 보내고 응답을 기다리는 방식이다. 이 방식은 채널 활용도가 낮다는 단점이 있으며, 이를 개선하기 위해 Go-Back-N이나 Selective Repeat과 같은 pipelined 프로토콜이 개발되었다.

RDT3.0의 성능과 Stop-and-Wait 동작 방식

RDT3.0 프로토콜의 성능은 송신자가 데이터를 전송하는 데 얼마나 시간을 효율적으로 사용하는지를 나타내는 지표인 활용률(utilization)로 측정할 수 있다. 활용률(Usender)은 송신자가 데이터 전송에 바쁘게 보내는 시간의 비율을 의미한다.

성능 계산 예시

예를 들어 1 Gbps 링크, 15 ms 전파 지연(propagation delay), 8000 비트 패킷의 경우를 살펴보자.

패킷을 채널에 전송하는 데 걸리는 시간(transmission delay)은 다음과 같이 계산된다:

Dtrans = L/R = 8000 bits / 10^9 bits/sec = 8 microsecs

여기서:

L: 패킷 크기 (8000 비트)
R: 링크 속도 (1 Gbps = 10^9 bits/sec)

Stop-and-Wait 동작

RDT3.0의 stop-and-wait 방식 동작은 다음과 같은 순서로 이루어진다:

송신자가 첫 번째 패킷 비트를 전송한다 (t = 0)
패킷은 네트워크를 통해 수신자에게 전달된다 (RTT 시간 소요)
수신자는 패킷의 마지막 비트를 받은 후 ACK를 보낸다
송신자는 ACK를 받은 후 다음 패킷을 전송한다 (t = RTT + L/R)

이 과정에서 송신자는 패킷을 전송한 후 ACK를 받을 때까지 기다려야 하므로, 대부분의 시간을 기다리는 데 소비한다.

활용률(U) 계산

송신자의 활용률(Usender)은 다음 공식으로 계산된다:

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

위의 예시에서:

L/R = 0.008 ms (8 microsecs)
RTT = 30 ms (왕복 시간)

따라서: Usender = 0.008 / 30.008 = 0.00027

이는 송신자가 실제로 패킷을 전송하는 데 사용하는 시간이 전체 사이클 시간의 약 0.027%에 불과하다는 것을 의미한다.

성능의 한계

RDT3.0 프로토콜의 성능은 매우 좋지 않다. 이는 프로토콜이 기반 인프라(underlying infrastructure)의 성능을 제한하기 때문이다.

Stop-and-wait 방식의 가장 큰 문제점은 송신자가 ACK를 기다리는 동안 채널이 유휴 상태로 남아있다는 것이다.

이는 특히 대역폭이 크고 지연 시간이 긴 네트워크(high bandwidth-delay product)에서 심각한 성능 저하를 가져온다.

이러한 문제를 해결하기 위해 파이프라이닝(pipelining) 같은 기법이 도입되었으며, 이를 통해 여러 패킷을 동시에 전송할 수 있게 되었다.

RDT3.0의 파이프라인 프로토콜 동작 방식

파이프라이닝(Pipelining)의 개념

파이프라이닝은 송신자(sender)가 여러 개의 "in-flight" 패킷, 즉 아직 확인응답(acknowledgment)을 받지 않은 상태의 패킷을 동시에 전송할 수 있게 하는 메커니즘이다. 이는 stop-and-wait 방식의 한계를 극복하기 위한 접근법이다.

파이프라이닝을 구현하기 위해서는 다음과 같은 요소들이 필요하다:

시퀀스 번호(sequence numbers)의 범위가 증가되어야 한다
송신자 및/또는 수신자(receiver)에서의 버퍼링(buffering)이 필요하다

활용률(Utilization) 향상

파이프라이닝은 네트워크 성능, 특히 송신자의 활용률을 크게 향상시킨다.

파이프라이닝 동작 과정

첫 번째 패킷 비트가 t = 0 시점에 전송된다
마지막 비트는 t = L/R 시점에 전송된다
첫 번째 패킷 비트가 수신자에게 도착한다
마지막 패킷 비트가 도착하면 수신자는 ACK를 보낸다
두 번째 패킷의 마지막 비트가 도착하면 다시 ACK를 보낸다
세 번째 패킷의 마지막 비트가 도착하면 또 다시 ACK를 보낸다
ACK가 도착하면 송신자는 다음 패킷을 전송한다 (t = RTT + L/R)

성능 향상 계산

3-패킷 파이프라이닝 방식은 활용률을 3배 향상시킨다.

송신자 활용률 계산식:

U(sender) = 3L/R / (RTT + L/R) = .0024 / 30.008 = 0.00081

파이프라이닝을 사용하지 않는 경우의 활용률이 0.00027인데 비해, 3-패킷 파이프라이닝을 사용하면 활용률이 0.00081로 정확히 3배 증가한다.

정리

파이프라이닝은 RDT3.0과 같은 프로토콜에서 네트워크 자원을 효율적으로 사용할 수 있게 해주는 중요한 기법이다. 여러 패킷을 동시에 전송함으로써 송신자가 ACK를 기다리는 시간을 효율적으로 활용할 수 있으며, 이는 전체 시스템의 처리량(throughput)을 향상시킨다. 이러한 파이프라이닝 개념은 TCP와 같은 실제 네트워크 프로토콜에서도 중요하게 활용된다.

Go-Back-N: 신뢰할 수 있는 데이터 전송을 위한 파이프라인 프로토콜

Go-Back-N은 신뢰할 수 있는 데이터 전송(Reliable Data Transfer)을 위한 파이프라인 프로토콜이다.

이 프로토콜은 송신자(sender)가 여러 패킷을 연속적으로 전송할 수 있게 해주면서도 오류 발생 시 효율적인 복구 메커니즘을 제공한다.

Go-Back-N: 송신자(Sender) 측면

Go-Back-N 송신자는 다음과 같은 특징을 가진다:

송신자는 "window"라는 개념을 사용하여 최대 N개의 연속적으로 전송된 패킷들이 ACK(확인응답)을 기다릴 수 있도록 한다.
패킷 헤더에는 k-bit의 시퀀스 번호(sequence number)가 포함된다.
송신자의 상태는 다음과 같은 영역으로 구분된다:
- 이미 ACK를 받은 패킷(already ACK'ed)
- 전송했지만 아직 ACK를 받지 않은 패킷(sent, not yet ACK'ed)
- 전송 가능하지만 아직 전송하지 않은 패킷(usable, not yet sent)
- 사용할 수 없는 패킷(not usable)

누적 ACK(Cumulative ACK) 메커니즘

ACK(n): n번까지의 모든 패킷을 확인했다는 의미이다.
송신자는 ACK(n)을 받으면 윈도우를 n+1부터 시작하도록 이동시킨다.
이는 n까지의 모든 패킷이 성공적으로 수신되었음을 의미한다.

타이머 및 재전송 메커니즘

송신자는 가장 오래된 in-flight 패킷(아직 확인되지 않은 패킷 중 가장 먼저 보낸 것)에 대한 타이머를 유지한다.
timeout(n): 타임아웃이 발생하면 패킷 n과 윈도우 내의 그 이후의 모든 패킷들을 재전송한다.

Go-Back-N: 수신자(Receiver) 측면

Go-Back-N 수신자는 다음과 같은 특징을 가진다:

ACK-only 방식: 지금까지 올바르게 수신한 패킷 중 가장 높은 in-order 시퀀스 번호에 대해 항상 ACK를 보낸다.
중복 ACK를 생성할 수 있다.
수신자는 rcv_base(다음에 기대하는 시퀀스 번호)만 기억하면 된다.

순서가 맞지 않는(out-of-order) 패킷 처리

버리거나(discard) 버퍼링할 수 있다 (구현에 따른 결정).
가장 높은 in-order 시퀀스 번호에 대한 ACK를 다시 보낸다(re-ACK).

수신자의 시퀀스 번호 공간

수신자의 시퀀스 번호 공간은 다음 세 가지로 구분된다:

받고 ACK한 패킷(received and ACKed)
순서가 맞지 않게 받았지만 ACK하지 않은 패킷(Out-of-order: received but not ACKed)
아직 받지 않은 패킷(Not received)

Go-Back-N 동작 예시

다음은 Go-Back-N이 실제로 어떻게 동작하는지 보여주는 예시이다:

송신자 윈도우 크기(N=4)인 경우:

송신자는 패킷 0, 1, 2, 3을 순차적으로 전송한다.
패킷 2가 손실되었다고 가정한다.
수신자는 패킷 0, 1을 받고 ACK0, ACK1을 보낸다.
수신자는 패킷 3을 받지만 이는 순서가 맞지 않으므로 버리고, ACK1을 다시 보낸다.
송신자는 ACK0, ACK1을 받고 윈도우를 이동시켜 패킷 4, 5를 전송한다.
수신자는 패킷 4, 5도 순서가 맞지 않으므로 버리고 계속 ACK1을 보낸다.
패킷 2의 타임아웃이 발생하면 송신자는 패킷 2부터 5까지 모두 재전송한다.
수신자는 이제 패킷 2, 3, 4, 5를 순서대로 받고 각각 ACK2, ACK3, ACK4, ACK5를 보낸다.

이 과정에서 Go-Back-N의 핵심 특징인 윈도우 기반 전송, 누적 ACK, 그리고 오류 발생 시 패킷 2부터 모든 후속 패킷의 재전송이 잘 드러난다.

이러한 방식으로 Go-Back-N은 파이프라이닝을 통해 전송 효율성을 높이면서도, 단순한 수신자 구현과 확실한 오류 복구 메커니즘을 제공한다.

Selective Repeat (선택적 재전송) 프로토콜: 원리와 구현

Selective Repeat(선택적 재전송) 프로토콜은 신뢰할 수 있는 데이터 전송을 위한 파이프라인 프로토콜이다. 이 프로토콜은 Go-Back-N과 함께 슬라이딩 윈도우 프로토콜의 한 종류이며, 오류가 발생한 패킷만을 선택적으로 재전송함으로써 네트워크 자원을 효율적으로 사용하는 방식이다.

Selective Repeat의 기본 접근 방식

Selective Repeat 프로토콜의 기본 원리는 다음과 같다:

파이프라이닝(pipelining): 여러 패킷을 동시에 전송한다(multiple packets in flight).
개별 ACK: 수신자는 모든 올바르게 수신한 패킷에 대해 개별적으로 ACK(acknowledgment)를 보낸다.
버퍼링: 수신자는 필요에 따라 패킷을 버퍼링하여 상위 계층에 순서대로 전달한다.

송신자 측면에서:

각 미확인(unACKed) 패킷에 대한 타이머를 (개념적으로) 유지한다.
타임아웃 발생 시 해당 타임아웃과 연관된 단일 미확인 패킷만 재전송한다.
N개의 연속적인 시퀀스 번호에 대한 "윈도우"를 유지한다.
윈도우 내에 있는 패킷만 파이프라인으로 전송한다.

송신자와 수신자의 윈도우

Selective Repeat(선택적 재전송) 프로토콜에서 송신자(sender)와 수신자(receiver)는 모두 시퀀스 번호(sequence number)의 윈도우(window)를 관리한다. 이 윈도우는 송수신 양쪽이 어떤 패킷을 전송하거나 수신할 수 있는지, 그리고 어떤 패킷이 이미 처리되었는지를 구분하는 데 핵심적인 역할을 한다.

송신자 관점(sender view)

send_base: 송신 윈도우의 시작점. 이보다 작은 시퀀스 번호는 이미 ACK를 받은 상태이다(초록색).
nextseqnum: 다음에 전송할 수 있는 시퀀스 번호의 위치.
윈도우 크기(window size, N): 송신자가 한 번에 전송할 수 있는 미확인 패킷의 최대 개수.

송신자 시퀀스 번호의 상태는 다음과 같이 나뉜다:

already ack’ed (초록색): 이미 ACK를 받은 패킷.
sent, not yet ack’ed (노란색): 전송했으나 아직 ACK를 받지 못한 패킷. 이 구간이 실제로 "in-flight" 패킷이다.
usable, not yet sent (파란색): 아직 전송하지 않았지만 윈도우 내에 있어 바로 전송할 수 있는 시퀀스 번호.
not usable (흰색): 윈도우 바깥에 있어 아직 전송할 수 없는 시퀀스 번호.

수신자 관점(receiver view)

rcv_base: 수신 윈도우의 시작점. 이 위치의 패킷을 가장 먼저 기대하고 있다.
윈도우 크기(window size, N): 수신자가 허용할 수 있는 시퀀스 번호의 범위.

수신자 시퀀스 번호의 상태는 다음과 같이 나뉜다:

already ack’ed (초록색): 이미 수신하고 ACK를 송신자에게 보낸 패킷.
out of order (buffered) but already ack’ed (분홍색): 순서가 맞지 않아 버퍼에 저장된 패킷이지만, 이미 ACK를 보낸 상태.
expected, not yet received (회색): 수신자가 현재 가장 기대하고 있는 시퀀스 번호. 이 패킷이 도착하면 상위 계층에 데이터를 전달하고, 윈도우를 한 칸 이동시킨다.
acceptable (within window) (파란색): 윈도우 내에 있어 수신이 가능한 시퀀스 번호. out-of-order로 도착하면 버퍼에 저장된다.
not usable (흰색): 윈도우 바깥에 있어 수신자가 아직 허용하지 않는 시퀀스 번호.

핵심 동작 원리

송신자는 send_base부터 nextseqnum-1까지의 패킷만 전송할 수 있고, 윈도우 크기 N을 넘지 않는다.
송신자는 ACK를 받으면 send_base를 앞으로 이동시키고, 그만큼 새로운 패킷을 전송할 수 있다.
수신자는 rcv_base부터 rcv_base+N-1까지의 시퀀스 번호만 허용하며, 순서가 맞지 않는 패킷도 윈도우 내라면 버퍼에 저장할 수 있다.
수신자는 rcv_base 위치의 패킷이 도착해야만 상위 계층에 데이터를 전달하고, 그 이후 버퍼에 저장된 순서 맞는 패킷도 연달아 전달한다.

Selective Repeat의 윈도우 관리가 중요한 이유

효율적인 대역폭 활용: 여러 패킷을 동시에 전송하고, 손실된 패킷만 재전송하여 네트워크 효율을 높인다.
순서 보장 및 신뢰성: out-of-order 패킷을 버퍼링하고, 순서가 맞는 데이터만 상위 계층에 전달함으로써 데이터의 순서를 보장한다.
중복 및 오류 처리: 이미 ACK를 보낸 패킷이 다시 도착하면 무시하거나 ACK만 재전송하여 중복 처리를 단순화한다.

이와 같은 윈도우 관리 방식은 Selective Repeat 프로토콜의 핵심이며, 고속 네트워크 환경에서 신뢰성과 효율성을 모두 달성할 수 있게 한다.

Selective Repeat 송신자와 수신자의 동작

송신자:

상위 계층으로부터 데이터 수신 시: 윈도우 내에 다음 사용 가능한 시퀀스 번호가 있으면 패킷을 전송한다.
타임아웃(timeout) 발생 시: 해당 패킷 n만 재전송하고 타이머를 재시작한다.
ACK(n) 수신 시: 패킷 n을 받았다고 표시하고, 만약 n이 가장 작은 미확인 패킷이라면 윈도우의 기준점(base)을 다음 미확인 시퀀스 번호로 이동시킨다.

수신자:

[rcvbase, rcvbase+N-1] 범위의 패킷 n을 수신 시:
- ACK(n)을 송신자에게 보낸다.
- 순서가 맞지 않은(out-of-order) 패킷은 버퍼링한다.
- 순서가 맞는(in-order) 패킷은 상위 계층에 전달하고, 버퍼링된 in-order 패킷도 함께 전달한 후 윈도우를 다음 아직 받지 않은 패킷으로 이동시킨다.
[rcvbase-N, rcvbase-1] 범위의 패킷 n을 수신 시: ACK(n)을 보낸다(중복 패킷을 처리하기 위함).
그 외 경우: 무시한다.

Selective Repeat의 딜레마

Selective Repeat 프로토콜에서는 시퀀스 번호 크기와 윈도우 크기 간의 관계에 대한 중요한 딜레마가 있다. 예를 들어:

시퀀스 번호: 0, 1, 2, 3 (base 4 counting)
윈도우 크기: 3

이런 상황에서 다음과 같은 두 가지 시나리오를 고려할 수 있다:

문제 없는 경우(no problem): 패킷 0, 1, 2, 3이 정상적으로 전송되고 윈도우가 이동한다.
문제가 발생하는 경우(oops!): 패킷 0, 1, 2가 전송되지만 모두 손실되고, 타임아웃으로 패킷 0이 재전송된다.

두 번째 경우, 수신자는 동일한 시퀀스 번호 0을 가진 패킷을 받게 되지만, 이것이 원래 패킷 0인지 새로운 패킷 0인지 구분할 수 없다. 이 문제를 해결하기 위해서는 시퀀스 번호 공간의 크기와 윈도우 크기 사이에 특정 관계가 필요하다.

해결책: 시퀀스 번호 공간 크기는 윈도우 크기의 2배 이상이어야 한다. 즉, 시퀀스 번호 크기가 n비트일 때, 최대 윈도우 크기는 2^(n-1)이 되어야 한다.

Go-Back-N과의 비교

Selective Repeat은 Go-Back-N과 비교하여 다음과 같은 특징이 있다:

재전송 효율성: Go-Back-N은 오류 발생 시 윈도우 내 모든 패킷을 재전송하는 반면, Selective Repeat은 오류가 발생한 패킷만 재전송한다.
버퍼 요구사항: Selective Repeat는 수신자 측에서 더 큰 버퍼가 필요하다(순서가 맞지 않는 패킷을 버퍼링하기 위함).
구현 복잡성: Selective Repeat이 Go-Back-N보다 구현이 더 복잡하다.
순서 보장: 두 프로토콜 모두 최종적으로 데이터의 순서를 보장한다.

결론

Selective Repeat 프로토콜은 효율적인 패킷 재전송 메커니즘을 통해 네트워크 자원을 최적화하는 신뢰할 수 있는 데이터 전송 프로토콜이다. 시퀀스 번호와 윈도우 크기 간의 관계에 주의해야 하지만, 적절히 구현되면 Go-Back-N보다 더 효율적인 성능을 제공할 수 있다. 이러한 원리는 TCP와 같은 현대의 네트워크 프로토콜 설계에도 중요한 영향을 미쳤다.