RDT Protocol

Reliable Data Transfer Protocol(신뢰할 수 있는 데이터 전송 규칙)을 수립하기 위한 고민의 과정을 다음과 같이 정리합니다.

각 단계를 거치면서, 가정을 조금씩 걷어내며 신뢰도를 계속해서 높입니다.

FSM

모든 예제를 FSM을 이용하여 표기하기 때문에, FSM에 대해서 이해하고 가는 것이 편합니다.
FSM(Finite State Machine)이란, 유한한 관계에서 각 상태와 각 상태로 가기 위한 조건과 행동을 명시하는 도표를 말합니다.
기본적으로 다음과 같은 형태로 이루어지는 것이 일반적이다. 시작 지점을 화살표를 통해 명시하고, 어떤 상태에서 각 조건과 이에 따른 행동을 했을 때, 변하게 될 상태를 명시하는 것이다.

RDT v1.0

가정 : 하위 통신 channel은 완벽하게 신뢰할 수 있다.

- sending side : 송신단에서는 상위 계층(0SI 기준)에서 송신 요청이 들어오면, packet을 만들어서 이를 udt를 통해서 전송하는 것을 보여주고 있다. 이때, 상태는 변하지 않고 계속해서 유지된다.
- receive side : 수신단에서는 하위 계층에서 수신 요청이 들어오면, packet을 추출하고, 이를 상위 계층에게 전달하는 역할을 수행한다.

가정에 따라, 해당 과정은 절대 실패하지 않는다. 따라서, 서로 feedback을 주는 것은 무의미하다.

RDT v2.0

가정 :

    - 하위 통신 channel의 하나의 packet의 bit가 일부 손상될 수 있다고 가정하자. 
    - 전송된 packet은 순서대로 모두 받을 수 있다고 가정한다.

해당 과정에서는 ARQ(Automatic Repeat reQuest) protocol을 사용한다. 해당 방식은 수신단에서 자신이 제대로 받았는지를 송신단에게 다시 reaction을 통해서 알려주는 수단이다.

이를 수행하기 위해서는 기본적으로 다음과 같은 3단계의 과정이 필요하다.

1. Error detection : bit error가 발생했을 때, 이를 감지하는 것이다. checksum과 같은 기법을 사용한다. 이는 해당 주제에서는 다소 멀어질 수 있는 별도로 다룹니다.
2. Receiver feedback : 수신단에서 송신단에게 자신이 받은 데이터가 정상적으로 전달되었는지를 알립니다. 이때, 정상적으로 전달되었다면, ACK를 전송하고, 그렇지 않다면, NAK를 전송합니다. 대게, 1bit로 표현되며, 0 = NAK, 1 = ACK입니다.
3. Retransmission : packet을 receiver에게 재전송하는 것을 말합니다.

- sending side : RDT v1.0과 동일하게 전송을 수행하지만, 그 후에 응답을 기다리는 상태로 이어집니다. 해당 응답이 NAK이면 재전송 후에 다시 대기하며, 그렇지 않다면, 송신 대기 상태로 되돌아갑니다. 여기서 상대방이 응답을 하기 전까지는 다음 전송을 수행하지 않습니다. 이를 stop-and-wait protocol이라고 합니다.
- receiver side : 받은 데이터가 손상되었다면, NAK을 전송하고, 그렇지 않다면 ACK를 전송합니다.

=> 해당 과정은 문제를 가진다. 왜냐하면, NAK 또는 ACK 응답 또한, corrupt 될 수 있다는 것이다. 이 경우에는 receiver가 제대로 데이터를 받았는지 sender는 알 수가 없다.

RDT v2.1

가정 :

    - 하위 통신 channel의 하나의 packet의 bit가 일부 손상될 수 있다고 가정하자. 
    - 전송된 packet은 순서대로 모두 받을 수 있다고 가정한다.

생각할 수 있는 해결책
1. Response에서 에러가 발생하였다면, 다시 전송해달라고 sender에서 요청하는 것이다. 하지만, 이 다시 전송해달라는 말이 에러가 나면, receiver는 정말 무엇을 잘못 알아들었다는 것인지 알 방법이 없다.
2. 더 많은 checksum bits를 추가하여, receiver가 스스로 error를 복구할 수 있도록 하는 방법이다.
3. sender에서 NAK 뿐만 아니라 error가 있는 response를 받았을 때에도 재전송을 하는 것이다. 그러나, 이 방법을 사용하면, 도착한 데이터가 새로운 데이터인지 또는 재전송된 데이터인지를 receiver는 알 수 없다.

이 중에서 2번이 아닌 우리는 3번 방식을 이용해볼 것이다. 여기서 위에서 제시한 문제를 해결할려면, 우리는 sequence number를 data packet에 추가함으로서 해결할 수 있다. 이를 이용해서 receiver는 수신한 데이터가 retransmission 된 것인지 확인할 수 있다. 여기서는 1bit의 sequence number면 충분히 이를 수행할 수 있다.

- sending side : sender는 sequence number가 0일 경우와 1일 경우 두 가지로 분리되게 된다. sequence number는 하나의 요청당 하나로 고정되며, 요청이 완벽하게 종료되어야 그 수가 바뀐다. 이를 이해 한다면, 단지 2배로 state가 늘어난 것 정도로 해당 그림을 이해할 수 있다.
- receiver side : receiver 역시 sequence number가 0일 경우와 1일 경우 두 가지로 분리되게 된다.

=> 해당 과정에서 만약에, receiver 단에서 out of order(잘못된 sequence number)가 발생하면 동일한 data에 대해서 두 번 ACK를 두 번 보내는 것을 알 수 있다.

RDT v2.2

가정 :

    - 하위 통신 channel의 하나의 packet의 bit가 일부 손상될 수 있다고 가정하자. 
    - 전송된 packet은 순서대로 모두 받을 수 있다고 가정한다.

기존에 2.1 방식에서 NAK를 ACK + 반대 sequence number로 대체하여 더 유연하게 대응할 수 있도록 변경한 것이다.

 

RDT v3.0

가정 :

     - 하위 통신 channel의 하나의 packet의 bit가 일부 손상되거나 아예 사라질 수 있다고 가정하자.
    - 전송된 packet은 순서대로 받을 수 있다고 가정하자.

지금부터는 packet의 데이터가 일부 손상당할 뿐만 아니라 아예 사리질 수 있다고 가정해보자. 아예 손상되었을 경우 이에 대해서 어떻게 알고 이를 어떻게 대처할지를 추가해서 다루어야 한다. 이를 위한 구현 방법은 다양하지만, 여기서는 countdown timer를 이용할 것이다. 만약, timer가 interupt를 발생시켰음에도 데이터가 도착하지 않았다면, 데이터의 손실이 발생했다고 생각하는 방식이다.