⚠️ 들어가기 앞서
경북대학교 컴퓨터학부 COMP0414-001 컴퓨터망 과목을 공부하며 정리한 글입니다.

---

1. RDT란

RDT(Reliable Data Transfer), 즉'신뢰성 있는 데이터 전송' 은 전송된 데이터가 소실되거나 손상되지 않도록, 말 그대로 '신뢰성 있게' 데이터를 전송하는 개념이다.

전송 계층에서는 신뢰성 있는 데이터를 주고받으려고 하나, 실제로 그 아래 계층에서는 신뢰성이 보장되지 않는다. 이러한 문제 상황에서 해결 방안으로 제시된 것이 RDT 프로토콜이다.

전송 계층에서 신뢰성 있는 데이터 전송도 결국 네트워크 계층의 신뢰성 없는 채널에 의존한다.
그리고 sender와 receiver는 서로의 상태를 알지 못하며, 따라서 본인이 보낸 데이터를 반대편에서 잘 받았는지, 가는 과정에서 오류가 발생했는지 서로 메시지를 주고받지 않는 한 알 수가 없다.

먼저 데이터를 전송하는 프로토콜의 인터페이스를 살펴보면 다음과 같다.

복잡해보이지만 딱 4가지의 기능만 알면 된다.

• rdt_send() : 상위 계층에서 보내고자 하는 데이터가 있을 경우rdt_send를 호출하여 rdt 프로토콜로 전송한다.
• udt_send() : 신뢰할 수 없는 하위 계층으로 데이터를 전송할 때 udt_send를 호출하여 패킷을 보낸다.
• rdt_rcv() : 하위 계층에서 보내고자 하는 데이터가 있는 경우 rdt_rcv를 호출하여 받아온다.
• deliver_data() : rdt 프로토콜에서 상위 계층으로 데이터를 보낼 때 호출한다.

위 2가지 시스템콜은 sender에서, 아래 2가지 시스템콜은 receiver에서 호출된다.

이제, Finite State Machine (FSM, 유한 상태 모델) 을 통해 sender와 receiver가 어떻게 동작하는지를 도식화하여 나타낼 것이다.

FSM(Finite state machine) : 어떤 상태가 어떤 사건에 의해 다른 상태로 변하는 것을 도식화 한 모델

---

2. RDT 1.0

RDT 1.0에서는 채널이 완벽하게 신뢰할 수 있다고 가정하며, 무조건 신뢰할 수 있기 때문에 오류 검증 및 재전송 과정을 거치지 않고 단순 패킷 송수신만이 이루어진다.

데이터의 송수신이 모두 완벽하게 신뢰할 수 있다고 가정한 모델이기 때문에, sender와 receiver는 단순히 데이터를 보내기만 하고, 받기만 한다. 때문에 모델이 단순하게 구현된다.

※ 화살표는 상태의 변화를 나타내는 것이고, 가로선 위의 이벤트가 발생하면 가로선 아래의 동작을 수행한다고 생각하면 된다.

먼저 sender를 보면, rdt_send 를 통해 전송할 데이터를 받으면, 바로 이를 패킷으로 만들어서 udt_send 로 보낸다. 어떠한 오류 검증 과정이나 재전송 과정도 포함되어 있지 않은 단순한 구조이다.

이번에는 receiver를 보면, rdt_rcv 를 통해 전송할 데이터가 들어오면 이를 추출(extract) 하여 상위 계층 프로토콜 형식에 맞게 변환하는 작업을 거쳐 바로 deliver_data 해 준다. 마찬가지로 오류 검증 과정 등이 포함되어 있지 않다.

---

3. RDT 2.0

하지만, 전송 과정에서 오류가 발생하지 않을 수는 없다. 따라서 현실을 부정할 것이 아니라 어떻게 하면 오류를 감지할 것인지, 감지했으면 어떤 작업을 거칠 것인지를 생각해야 한다.
그래서 고안된 것이 RDT 2.0 이다.

RDT 2.0에서는, 패킷이 전송되는 과정에서 bit error가 발생할 가능성을 인지한다.

bit error란 0과 1로 들어오는 비트가 뒤바뀐다거나 하여 원본 데이터에서 달라지는 것을 의미한다. 비트가 달라졌는지의 여부는 각 데이터의 비트 합을 나타내는 checksum 필드를 확인함으로써 판별 가능하다.

그렇다면, receiver가 받은 데이터에 오류가 있다는 것을 판별하고 나면, 어떤 작업을 할까? 사람의 대화로 예시를 들어보자..

A : 너 어제 #$#%@# 했어?
B : 뭐라고? 잘 못 들었어.

제대로 못 들었다면 당연히 다시 말해달라고 할 것이다. receiver 역시 마찬가지이다.

receiver는 데이터의 상태에 따라 두 가지 응답을 한다.
acknowledgement(ACK)과 negative acknowledgement(NAK)이 그것이다.

ACK는 데이터에 이상이 없고 문제없이 받았다는 뜻이다.
NAK는 데이터에 에러가 검출되었다는 뜻이다.

receiver는 두 가지 응답 중 하나를 sender에게 전송한다.
한편, sender는 자기가 데이터를 보낸 후 receiver에게 응답이 올 때까지 대기한다. 그러다 NAK이 도착하면 데이터를 재전송(retransmit)해 준다.

receiver의 위쪽 화살표를 보면 corrupt(rcvpkt) 라는 부분이 있는데 이 부분에서 걸리게 된다면 데이터가 손상되었다는 뜻이고 NAK 을 send 한다.

아래쪽은 notcorrupt 이므로 데이터를 정상적으로 받았다는 뜻이고, 데이터를 처리하여 deliver_data와 함께 udt_send로 sender에게 ACK를 보내준다.

이 때 sender는 응답을 받을 때까지 다른 패킷을 전송하지 않고 멈춰서 기다린다. 이러한 행동 때문에 rdt 2.0은 stop and wait 방식이라고 한다.

---

3-1. RDT 2.1

하지만 RDT 2.0 역시 문제가 없는 것은 아니다!

만약 ACK/NAK 메시지가 오류가 난다면?

sender는 receiver가 어떤 상태인지, 데이터를 잘 받았는지 알 수 없다고 하였다. 즉 ACK/NAK 말고는 receiver의 상태를 알 수가 없는데, 이 ACK/NAK이 오류가 발생했다면 어떨까?

데이터를 그냥 다시 보내주면 되지 않을까...?

마냥 데이터를 다시 보내줄 수는 없다. 만약 receiver가 데이터를 잘 처리한 후 ACK을 보내고 다음 데이터를 기다리고 있는데, sender가 데이터를 다시 보내주면 receiver 입장에서는 원한 데이터가 아니므로 문제가 발생할 수 있다.

여기서, 포인트는 다음과 같이 넘어간다.

수신자가 오류가 발생해서 재전송해준 데이터와, 다음에 받을 데이터를 구분할 수 있으면 좋겠다!

그래서 sender는 패킷에 sequence number, 일련 번호를 붙여서 보낸다.

• 만약 receiver가 0번 패킷에 대해서 잘 받고 ACK을 보내고 다음 1번 패킷을 기다리고 있다고 가정하자.
• 이 때 ACK가 오류가 발생해서 정상적으로 전달되지 않았고, 이에 sender가 본인이 보낸 데이터가 제대로 전달되지 않은 줄 알고 다시 0번 패킷을 보낸다.
• 그러면 receiver 입장에서는 1번 패킷을 기다리고 있는데, 0번 패킷이 다시 도착한 것이라면 "아, 내가 보낸 ACK가 제대로 도착하지 않아서 재전송 해준 거구나" 생각하고 별다른 처리를 하지 않고 ACK만 다시 보낸다.

위 그림은 sender의 동작 방식을 나타낸 FSM이다. 복잡해 보이지만 빨간 선을 기준으로 위 아래는 0번 패킷, 1번 패킷에 대한 처리 과정이므로 대칭이다. 즉 한쪽 부분의 화살표 3개만 보면 된다. 생각보다 단순하다.

• 먼저 0번 데이터를 받아서 패킷화 시켜 0번 패킷을 보내고, 응답을 기다린다.
• 만약 응답이 손상되었거나 NAK이 돌아온다면 다시 0번 패킷을 보낸다.
• 만약 응답으로 ACK이 돌아온다면, 잘 전해졌구나 하고 다음 1번 패킷을 만들 데이터를 기다린다.

위 그림은 receiver의 동작 방식의 FSM이다. 마찬가지로 복잡해 보이지만 빨간 선 기준으로 한 쪽의 3개 화살표만 보면 된다.

• 0번 패킷을 기다리고 있을 때, 손상되지 않은 0번 패킷이 잘 도착했으면 deliver_data로 상위 계층에 보내주고 ACK를 돌려준다. 그리고 1번 패킷을 기다린다.
• 만약 1번 패킷을 기다리고 있는데, 들어온 데이터가 손상되었다면 NAK을 보낸다.
• 만약 1번 패킷을 기다리고 있을 때 0번 패킷이 들어왔다면, 위에서 언급한 대로 "아, 내가 보낸 ACK가 제대로 도착하지 않아서 재전송 해준 거구나" 생각하고 별다른 처리를 하지 않고 ACK만 다시 보낸다.

FSM이 복잡해서 기선제압을 당할 수는 있지만, 사실 잘 뜯어보면 직관적으로 이해하기 쉬운 구조이다.

RDT 2.1에서 일련번호는 패킷의 중복 여부를 판별하고자 사용되므로 0, 1 두 숫자면 충분하다.

---

3-2. RDT 2.2

RDT 2.1과 기능적으로는 동일하나, receiver는 NAK/ACK 말고 ACK 만 사용한다. ACK에다 마지막으로 수신 성공한 번호를 담아서 보낸다.

sender가 0번 패킷을 보낸다고 가정했을 때, receiver가 정상적으로 0번 패킷을 처리하여 0이 담긴 ACK를 보내면, sender는 마지막으로 보낸 패킷과 일치하므로 잘 처리되었다고 생각한다.

그러나 receiver가 0번 패킷을 정상적으로 처리하지 못해 1이 담긴 ACK를 보내면, sender는 마지막으로 보낸 패킷과 일치하지 않으므로 NAK 으로 간주한다.

그림의 위쪽에서 sender의 동작 구조를 보면 0번 ACK 를 기다리고 있을 때 1번 ACK가 날아오거나 응답이 손상되면 다시 0번 패킷을 보내는 것을 볼 수 있다.
만약 0번 ACK가 잘 돌아왔다면, 잘 받았다고 간주하고 pass한다.

한편, 아래쪽의 receiver 동작을 보면 1번 패킷을 받았을 때 문제가 없으면 1번 ACK를 보낸다. 만약 문제가 있었다면 이전에 0번 패킷에 대한 응답을 보낼 때 민들었었던 sndpkt, 즉 0번 ACK 를 보낸다.

---

4. RDT 3.0

이제 오류가 발생한 패킷을 식별 및 재전송 요청할 수 있게 되었다. 하지만 아직 문제가 남아있다...!

보낸 패킷이 에러가 아니라 아예 소실(loss) 되었다면? receiver가 아예 데이터를 받지 못한다면?

만약 sender가 패킷을 보냈는데, 전송 중에 소실되었다고 가정하자. 그렇다면 sender는 이 패킷이 제대로 전달됐는지 여부를 알 수 없기 때문에 제대로 전송됐다고 가정하고 응답을 기다리고 있을 것이고, receiver는 아예 데이터가 도착하지 않았기 때문에 아무 일도 하지 않을 것이다. 즉 문제가 발생한다.

이러한 상황 역시 사람의 대화로 비유를 들 수 있다.

A : 밥 먹었어?
B : (다른 일을 하느라 듣지 못함)...
A : ...
A : (잠시 후) 밥 먹었냐고!

A는 본인의 물음에 대한 대답을 하염없이 기다릴 것이 아니라, 일정 시간이 지나도 돌아오지 않으면, 얘가 제대로 듣지 못했나 생각하고 다시 같은 물음을 던질 것이다.

이와 마찬가지의 과정을 패킷 통신에서도 적용할 수 있다.

sender는 '적당한' 시간만큼만 ACK를 기다린다.

여기서 '적당한' 시간이란 무엇일까? 뭐... 말하자면 정상적이었으면 응답이 돌아오고도 남을 시간 정도일 것이고, 이 글에서는 정상적인 통신에 걸리는 시간 등을 고려하여 합리적으로 결정한 시간이라고 가정한다.

만약 적당한 시간 안에 대답이 돌아오지 않으면 '내가 보낸 패킷이 소실되었구나' 생각하고 패킷을 재전송한다.

음... 그런데 단순히 대답이 느린 것이었다면? ACK가 전송되는 사이에 데이터가 재전송된다면?

이 질문에서는 RDT 2.1에서 이미 답을 찾았다. receiver가 일련번호를 확인하여 재전송된 패킷인지를 걸러낼 수 있다.

sender는 패킷을 보낸 이후에 timer 를 시작하여, 응답이 오기까지의 시간을 측정하고 있는다. 만약 사전에 정한 시간이 지나도 응답이 오지 않으면 패킷을 재전송한다.

위에 나온 설명대로 sender의 FSM을 그려보면 다음과 같다.

마찬가지로 빨간색 선 기준으로 대칭이므로 위쪽 부분만 확인하면 된다.

• sender는 0번 패킷을 보내고 응답을 기다리기 시작함과 동시에 타이머를 시작 start_timer한다.
• 만약 1번 ACK가 돌아왔다면 무시한다. (rdt 2.2와는 다르게, 어차피 무시하면 timeout 되므로 재전송 한다.)
• 만약 timeout (일정 시간이 지나도 응답이 오지 않음) 되면, 다시 패킷을 전송한다.
• 0번 ACK가 시간 안에 정상적으로 들어온다면 stop_timer 한다.

receiver는 rdt 2.2와 동일하다.

---

RDT 3.0에는 총 4가지 형식이 있을 수 있다.

1. 손실 없이 정상적으로 통신하는 경우
   

2. packet loss가 발생한 경우
   

3. ACK loss가 발생한 경우
   

4. timeout이 ACK보다 먼저 실행됐을 경우
   

정리하자면 receiver는 중복 패킷(일련번호로 판단)이 아닌 경우 항상 ACK를 보낸다.
그리고 receiver는 이 ACK에 대해 또 ACK를 보내지는 않고, 정상적인 ACK이 아닌 경우 재전송 한다.

---

5. Performance of RDT

sender는 패킷을 전송한 후 멈춰서 응답을 기다린다. 이 방식을 stop and wait 방식이라고 하는데, 당연히 응답을 기다리는 동안 아무 일도 하지 않으므로 전체 회선 사용량은 낮을 수밖에 없다.

패킷이 전송 완료됐을 시점부터 패킷에 대한 응답이 도착할 때까지의 시간을 round trip time, RTT 라고 한다.

그리고 패킷이 끝까지 전송 시작될 때까지 걸리는 시간을 transmission delay 라고 하며, 패킷의 길이 / Transmission rate L/R 로 표현한다.

그러면, 패킷을 보내기 시작했을 시점에서 ACK를 받을 때까지의 시간은 L/R + RTT 이다.

그럼, 이동안의 성능, utilization은 어떨지 생각해보자. 다르게 말하면 패킷이 가는 시간 동안 몇 개를 내보낼 수 있는가 에 대한 답변이다.

sender는 transmission delay만큼만 일을 한다. 나머지는 기다린다. 즉 (L/R) / (L/R + RTT) 가 바로 rdt 3.0의 protocol performance 라고 할 수 있다.

여기서 흔하게 드는 생각은, 'ACK를 기다리지 말고 바로 다음 패킷을 전송하면 되지 않나' 하는 생각이다. 이렇듯 동시에 여러 개의 패킷을 보낼 수 있는 방식을 pipelining 방식이라고 한다.

동시에 3개의 패킷을 보냈을 때, utilization이 3배 증가한 것을 볼 수 있다.

다음 글에서는 pipelined transport를 수행하는 두 가지 방법을 알아보자.

---

요약

• RDT 1.0 : 모든 데이터 송수신이 완전 신뢰 가능하다고 가정하며 어떠한 오류 검증 및 재전송 과정도 이루어지지 않음
• RDT 2.0 : sender가 전송한 메시지에 bit error가 발생할 때를 대비하여 잘 받았는지 여부를 receiver가 ACK/NAK 으로 sender에게 전달
• RDT 2.1 : ACK/NAK 메시지에 오류가 생길 때를 대비하여 재전송한 패킷과 다음 패킷을 구분하기 위해 일련번호 sequence number 를 도입
• RDT 2.2 : RDT 2.1과 동일하나 ACK/NAK 말고 ACK 만 사용. 가장 최근에 정상적으로 수신한 패킷의 일련번호를 ACK에 담아서 보냄.
• RDT 3.0 : 패킷이 손상이 아닌 완전 유실되었을 때를 대비하여 timer 를 도입, timeout 발생 시 재전송