Principles of reliable data transfer

Application layer 입장에서는 보내면 reliable이 보장 된다고 생각한다.
이 부분은 transport layer에서 구현해줘야 한다.(아래 layer들은 unreliable한 상황)

RDT라는 프로토콜을 통해 reliablility를 보장한다. (rdt_send(), udt_send(), rdt_rcv(), deliver_data())

RDT(Reliable Data Transfer)

RDT는, '신뢰성 있는 데이터 전송'의 줄임말로 전송된 데이터가 소실되거나 손상되지 않도록, 말 그대로 '신뢰성 있게' 데이터를 전송하는 개념이다.

아까 이야기했듯, transport layer에서는 신뢰성 있는 데이터를 주고 받고 싶지만, 그 아래 layer에서는 보장하지 못한다. 이를 해결하기 위한 프로토콜이다.

transport layer에서 신뢰성 있는 데이터 전송도 결국 network 계층의 신뢰성 없는 채널에 의존한다.
sender와 receiver는 서로의 상태를 알지 못하기에, 본인이 보낸 데이터를 반대편에서 잘 받았는지, 가는 과정에서 오류가 발생했는지 알 수가 없다.

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

rdt_send, udt_sedn는 sender에서, rdt_rcv(), deliver_data()는 receiver에서 호출된다.

FSM(Finite State Machine)을 통해 sender와 receiver가 어떻게 동작하는지 도식화한다.

RDT 1.0

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

그러면 sender와 receiver은 단순히 데이터를 송수신만 한다.

RDT 2.0

당연하게도, 전송 과정에서 오류가 발생하지 않을리는 없다. (발생하지 않으면 좋겠지만..)

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

비트가 달라졌는지에 대한 여부는 checksum 필드를 확인하면 된다.

receiver 입장에서 데이터에 대한 오류를 판별하고 난 뒤에는 당연히 데이터를 다시 보내달라고 얘기할 것이다.
그에 따라 두 가지 응답을 할 수 있다.

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

corrupt(rcvpkt) 함수에서 걸리면 데이터가 손상되었다는 뜻이고 NAK를 보내게 된다.
notcorrput 함수에 걸리면 데이터는 잘 받았다는 뜻이고, 추출하여 deliver_data(), udt_send()를 통해 sender에서 ACK를 보낸다.

이 때 sender는 응답을 받을 때까지 다른 패킷을 전송하지 않고 멈춰서 기다린다. 따라서 RDT 2.0 방식은 Stop and wait 방식이라고 한다.

(위는 에러가 없을 때 동작하는 방식을 빨간 줄로 표시했다.)

RDT 2.1

RDT 2.0에서는 보낸 패킷 데이터에 에러가 났을 때 처리하는 방법을 보여줬다.
그런데 만약 ACK/NAK에 오류가 난다면 어떻게 할 것인가?

데이터를 그냥 다시 보내주면 되지 않나라는 생각을 할 수 있지만, 만약 receiver 입장에서 데이터를 잘 처리하고 ACK를 보냈는데, sender가 데이터를 다시 보내면 (아까 받은 것) receiver 입장에서는 원한 데이터가 아니여서 문제가 발생할 수도 있다.

그래서 순서를 적기로 했다.

만약 receiver가 0번 패킷을 받고 ACK를 보내고 1번 패킷을 기다린다고 가정하자.
그리고 ACK에 오류가 생겨 sender에게 도달하지 않았고 이에 sender가 본인이 보낸 데이터가 제대로 전달되지 않을 줄 알고 다시 0번 패킷을 보낸다.
그러면 receiver 입장에서 1번 패킷을 기다리는데, 0번 패킷을 온 것을 보고 ACK 처리가 제대로 안된걸로 인지 후 다시 ACK를 보낸다.

sender 입장에서의 FSM이다.

receiver 입장에서의 FSM이다.

RDT 2.2

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

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

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

RDT 3.0

이제 만약 에러가 아니라 아예 패킷이 소실되었다면 어떻게 할 것인가?

그렇다면 보낸 sender도 '적당한' 시간만큼 ACK를 기다릴 것이다.
적당한 시간 안에 대답이 돌아오지 않으면 패킷이 소실되었다고 생각하고 패킷을 재전송할 것이다.

RDT action

Performance of RDT(3.0)

sender는 패킷을 전송하면 멈춰서 응답을 기다린다.
응답을 기다리는 동안 아무것도 하지 않아 전체 회선 사용량은 낮다.
패킷인 전송 완료되고, 패킷에 대한 응답이 도착할 때까지의 시간을 RTT라고 한다.

패킷이 끝까지 전송 시작될 때까지 기다리는 시간을 trasmission delay라고 하고, 패킷의 길이/R(L/R)로 표현된다.

그러면 패킷을 보내기 시작했을 시점부터 ACK를 받을 때까지는 L/R + RTT이다.

그러면 성능은 얼마일까?
sender는 trasmission delay만큼만 일을 한다. 그러면 (L/R) / (L/R + RTT)가 된다.
이것이 RDT 3.0의 protocol performance가 된다.

그러면 "아니, ACK를 기다리지 말고 그냥 바로 다음 패킷을 전송하면 되지 않을까?"라는 생각을 할 수 있다.
동시에 여러 개의 패킷을 보낼 수 있는 방식을 pipelining 방식이라고 한다.

Pipelining

송/수신자 간의 패킷 교환에서 송신자가 패킷을 보낸 후에 응답을 기다리는 것이 아닌, 바로 다음 패킷을 보내는 것을 말한다.

Go-Back-N

Go-Back-N 방식은 수신자가 어떤 패킷을 받지 못하면 그 패킷부터 모든 패킷을 다시 보내는 방법이다.
송신자는 ACK를 받지 않은 상태로 동시에 최대로 보낼 수 있는 패킷의 수를 정한다.
이를 window size라고 한다.
현재 window 위치를 설정하고, window size 만큼 범위를 지정한다.
수신자는 패킷들을 연속해서 받고, 각각의 패킷을 받을 때 마다 sequence number을 확인하고, ACK를 보낸다.
이 때, 송신자가 보낸 패킷들 중에 일부가 유실되면, 수신자가 받은 패킷들의 sequence number도 당연히 유실이 된다.
그러면, 빈틈이 생기기 전의 정상적으로 받은 패킷의 마지막 번호를 지속적으로 ACK에 실어서 보낸다.
송신자는 보낸 패킷의 ACK가 정상적으로 왔으면, 그 패킷을 처리했다고 기록한 후 window를 오른쪽으로 한 칸 밀어서 하나의 패킷을 더 보낼 수 있는 상태로 만든다.

위 그림에서 window size는 4이고, 0부터 3까지 일단 보낸다.
packet 2가 손실되었고, 수신자 입장에서는 순서대로 받아야하는데 2를 못 받고, 3을 받았기에, ack1을 송신자에게 보낸다.

한편, 송신자 측에서는 0과 1을 보냈기 떄문에 윈도우 사이즈 내에서 범위를 오른쪽으로 옮겨 4와 5를 보내지만, 수신자는 여전히 ack1을 보낸다.

그러면 송신자는 받지 못한 패킷 2에 대한 timeout이 발생하면 2번 패킷부터 지금까지 보냈던 모든 패킷을 다시 보낸다.

Selective repeat

Go-Back-N 방식은 수신자에게 보낸 패킷이어도 다시 보내야할 경우가 있어서 비효율적이다.
이를 개선한 것이 Selective Repeat이다.

Selective Repeat은 수신자가 받은 각각의 패킷에 대해 ACK를 보내는 방식이다.
다른 패킷의 수신 여부에 관계없이 모든 패킷이 따로 고려된다.

수신자는 window와 버퍼를 가지고 있는데, 어떤 패킷을 받앗을 때 패킷이 순서에 어긋나면 일단 버퍼에 저장한다.
그리고 순서에 맞는 패킷이 들어오면 버퍼에 있는 패킷들을 모두 ack을 보내고, ack를 보낸 패킷 수만큼 window를 이동한다.

위 그림 예시를 보면 송신자는 패킷 2에 대한 ack가 오지 않아 ack 3에 대해 window를 이동시키지 않는다. 대신 완료 처리 마킹은 한다.

Dilemma

window size는 반드시 사용하는 sequence number / 2 이하이어야 한다.

그렇지 않으면 많이 loss 됐을 때 문제가 발생할 수 있다.

위는 sequence number가 window size에 비해 충분히 크지 않아서 발생하는 문제의 예시이다.
위 그림과 같은 경우는 수신자는 0,1,2번 패킷을 받고 window를 3칸 이동시켜 3, 0, 1 패킷을 받을 준비를 하고 있다.

하지만 ack이 유실되어 송신자에게 도달하지 못했다. 그러면 송신자 측에서는 0번 패킷에 대한 timeout이 발생하고, 이를 재전송한다. 하지만 이 때 송신자가 보내는 0번 패킷과 수신자 window에 있는 window에 있는 0번 패킷은 서로 다르다. 하지만 0번이 window에 있기 때문에 정상적으로 간주하게 된다.

이러한 문제는 window size를 줄이면 된다. 사용하는 sequence nubmer(4)의 절반 이하인 2로 설정하면, 전체 ACK가 유실되더라도 한 바퀴 돌아서 다시 돌아오지 않도록 만들면 된다.