Reliable data transfer design

---

Principle of Reliable data transfer

Reliable한 데이터 전송 method 분야는 application, transport, link layer에서 전부 주요한 내용으로 networking 분야에서는 언제나 top-10 list에 들어갈 정도로 중요한 내용이다.

이전에 다뤘듯 transport layer는 unreliable한 하위 network channel에서 전송된 데이터를 reliable한 데이터를 요구하는 application layer에게 정리해서 전달해주어야한다. 간단하게 함수를 정리한다면 아래와 같을 수 있겠다.

이제 FSM을 이용하여 step 별로 transfer protocol을 업그레이드 해볼 텐데 FSM은 Fine State Machine 즉, 유한 상태 기계의 줄임말이다. 아래와 같이 sender와 receiver의 논리 전개 과정을 한눈에 볼 수 있도록 표현하는 것이다.

---

RDT 1.0

우선은 channel이 완벽하게 reliable하다고 가정을 하고 초기 모델을 설계해보자. 여기서 완벽하게 reliable하다는 것은 bit error도 없고 packet loss도 없다는 것이다.

완벽한 데이터만 오가기 때문에 할 역할이 크게 없다. 단지 데이터를 던져주고 다시 받는 상태로 대기하고 데이터가 오면 다시 답을 주고 답을 기다리는 것을 반복하는 간단한 구조이다.

---

RDT 2.0

이번에는 channel에 bit error는 존재할 수 있다고 가정해보자. 일상에서 상대방이 말을 못들으면 가장 많이 하는 소통방식은 했던말을 다시 해주는 것이다. 여기서도 해당 방식을 차용해보겠다. 이때 오류가 있는지 없는지는 checksum을 이용하여 확인한다. Checksum이 일치하면 acknowledgements(ACKs)라고 메세지를 첨부해서 보내주고 check sum이 일치하지 않으면 receiver는 negative acknowledgements(NAKs)라고 메세지를 보내준다.

보면 조금 복잡해졌지만 단순한 조건문이라는 것을 잊지 않고 하나씩 보면된다. Sender는 데이터를 보내주고 ACK든 NAK든 receiver가 보내주는 신호를 기다린다. 데이터를 받은 receiver는 문제가 있다면 NAK를 보내고 문제가 없으면 데이터를 챙기고 ACK를 보내준다. 이제 sender는 ACK를 받으면 다음 데이터를 보내줄 준비를 하고 NAK를 받으면 보냈던 데이터를 다시 보내준다. 간단한 논리로 문제를 해결한 것 처럼 보인다.

그러나 치명적인 문제가 있다. 만약 ACK나 NAK 메세지가 망가지면 해결할 방법이 없는 것이다. ACK나 NAK에 문제가 있다고 무조건 다시보내주면 receiver측에서 duplicate문제가 발생하기 때문에 해결책이 될 수 없다. 따라서 업그레이드가 필요하다.

---

RDT 2.1

ACK나 NAK에 문제가 있다고 무조건 다시 보내주면 duplicate문제가 생기기 때문에 이를 해결하기 위해 아래와 같이 설계하였다.

보면 packet에 0 또는 1이 생긴 것을 볼 수 있다. 메세지는 sequential하게 들어오므로 그 순서가 맞지 않으면 뭔가 문제가 있는 것이므로 원하는 순서의 데이터가 아니면 재요청하는 방식을 이용한다. 이때 순서를 0,1,2,3,4 이런식으로 지정해주는 것이 아니라 0,1,0,1을 반복하여 receiver가 받은 packet이 0이후에 0이 다시 오거나 1이후에 1이 다시 오면 뭔가 문제가 발생했음을 인지하고 NAK을 전송해주어 원하는 packet에 대한 재전송을 요청한다.

---

RDT 2.2

RDT 2.2는 RDT 2.1과 동일한 기능을 가지지만 ACK만을 사용하는 방식으로 업그레이드가 되다. NAK 대신에 receiver는 정상적으로 받은 마지막 패킷에 대한 ACK를 보낸다.  다시 말해 이전에 0번에 해당하는 정보를 제대로 전달받으면 ACK0을 답으로 보냈을 텐데 이후에 문제가 생기면 NAK 대신 또다시 ACK0를 보내는 것이다. Sender에게 중복된 ACK가 도착하면 NAK의 경우와 동일한 조치를 취한다.

FSM으로 표현하면 위와 같이 그려볼 수 있다. RDT 2.1과 거의 똑같지만 조건부 파트에만 조금의 변화가 생긴 모습이다.

---

RDT 3.0

이제 최종적으로 channel에서 packet loss가 발생할 수 있는 실제 network에서도 이용할 수 있는 RDT 3.0을 설계해보자. 우선 packet loss가 발생하면 오류가 낫다는 사실 자체를 알 수 없다는 점에 집중해야한다. 따라서 timer를 세팅을 해서 일정한 시간이 지나도 답이 오지 않으면 packet loss가 발생했다고 판단하고 재전송하는 알고리즘을 넣어주었다.

위의 FSM의 특징을 살펴보기 위해 wait for call 0 from above에서 start_timer로 타이머를 설정한 이후 작동되는 wait for ACK0 부분을 보자. corrupt가 발생하거나 ACK1이오면 timeout을 기다린다. timeout이 발생하면 이전에 만들어둔 packet을 재전송하고 다시 timer를 setting하는 논리 구조를 볼 수 있다. 이러한 논리 구조를 바탕으로 실제 네트워크가 어떻게 진행되는지 보면 아래와 같이 크게 4가지 정도의 케이스가 있을 수 있다.

---