[네트워크] 9. Principles of Reliable data transfer

이번 챕터는 Data transfer에서 어떻게 Reliable하게 보낼 것인지에 대해 다루게 됩니다.

 

1. Principles of Reliable data transfer

Application layer의 데이터 무결성은, Transport layer가 해주게 됩니다.

무선 등의 환경에서 어떻게 reliable한 데이터 전송을 가능하게 할 지 알아보도록 하겠습니다.

---

1.1 Reliable data transfer : Error & Solutions

데이터 전송 시 발생할 수 있는 문제는 크게 2가지가 있습니다.

1. Corruption (Bit-error) : 비트가 틀려서 데이터가 잘못 된 경우입니다. Checksum과 ACK로 해결할 수 있습니다.
2. Packet Loss : 도중에 패킷이 유실되는 경우입니다. Time-out이 걸렸을 때, Retransmission(재전송)을 하거나,
   Sequence Number을 활용하여 순서대로 전송하거나 중복을 방지할 수 있습니다.

 

 

Callback 함수가 불리는 식으로 layer간 통신이 일어납니다.

Transport Layer는 Application과의 rdt_send(), deliver_data()는 데이터 무결성을 보장합니다.

network layer과의 udt_send(), rdt_rcv()는 unreliable channel입니다.

어떻게 transport layer에서 reliable data transfer가 가능하게 하는지 살펴보도록 하겠습니다.

 

FSM (Finite state machine) 유한상태머신

앞으로 알고리즘으로 이론적으로 가능하다는 것을 보이기 위해, 유한상태머신을 사용합니다.

state(상태)와 event(actions)로 나뉘어 상태 전이를 통해 증명하는 방법입니다.

---

1.2 RDT 1.0

rdt 1.0은 모두 reliable한 채널입니다. 

bit error나 packet loss가 일어나지 않았을 때 상황입니다.

왼쪽위 점선은 state의 시작을 나타냅니다. 

1. sender는 application이 rdt_send(data)콜백 함수를 부르게 될 때, 패킷을 만들고 udt_send(packet)콜백 함수를 부릅니다.
2. network 계층을 통해 receiver에서 rdt_rcv(packet)콜백 함수가 불려지게 되면, 패킷을 unboxing하여(헤더를 벗겨) 데이터를 application layer로 보내주게 됩니다.

---

1.3 RDT 2.0

위에는 에러가 발생하지 않은 경우지만, 에러가 발생한다면 어떤 일이 일어날 지 보도록 하겠습니다.

Bit error가 발생하였을 때, 어떻게 에러로부터 복구를 할 수 있을까요?

(사람이라면 말을 잘 못 들었을 때, "뭐라고"라고 다시 말해달라는 요청을 할 것입니다.)

 

네트워크 통신에서도 비슷한 방식으로 잘 받았는지, 잘 못 받았는지에 대한 확인을 합니다.

이를 ACK(acknoledgements)와 NAK(negative acknowledgement)를 통해 합니다.

sender로부터 받은 데이터를 제대로 받지 못 했을때, receiver는 sender에게 NAK를 날리고, 제대로 받는다면 ACK를 보내줍니다.

sender는 receiver로부터 NAK를 받으면, 제대로 전송이 안 된 것이기 때문에, retransmit(재전송)을 해줍니다.

 

원리를 알았으니 FSM을 보도록 하겠습니다.

 

그림을 천천히 따라가보도록 하겠습니다.

1. sender의 rdt_send 콜백이 불리고, 패킷을 만들어 보내게 됩니다.
2. sender의 state가 Wait for ACK or NAK으로 전이합니다.
3. receiver는 아래 계층에서 rdt_rcv 콜백이 불리고, bit error가 발생한 것을 확인하고(corrupt), sender에게 NAK을 보냅니다.
4. sender는 NAK를 받고, 패킷을 재전송 합니다.
5. 이번에는 receiver가 정상적으로 받아, 데이터를 추출하고 application layer로 전송한 후, sender에게 ACK를 보냅니다.
6. sender는 ACK를 받고, 아무것도 하지 않고(거꾸로 된 V) 상태를 다시 Wait for call from above로 변경합니다.

 

1회 전송에 대해, NAK과 ACK로 bit error가 발생한 것을 확인할 수 있었습니다.

하지만, 이 방식에는 문제점이 있습니다.

ACK, NAK에도 bit error가 있을 수 있습니다. 이런 경우, sender는 패킷을 중복으로 전송하게 될 수 있습니다.

 

이러한 문제를 해결하기 위해, sender는 sequence number를 더해 패킷을 전송합니다. 이렇게, 현재 패킷과 이전 패킷을 구분하여, 중복된 패킷을 receiver가 제거할 수 있게 합니다. 이것이 가능하게 하기 위해, stop and wait 방식을 사용합니다.

 

stop and wait

sender가 하나의 패킷을 전송하고, receiver의 응답이 올 때 까지 패킷을 전송하지 않고 기다리는 방법입니다.

 

---

1.4 RDT 2.1

이제, sender가 sequence number를 더해 패킷을 전송하는 상황에서 FSM를 보도록 하겠습니다.

 

sender

 

 

receiver

 

 

다양한 상황을 만들어서, FSM이 잘 작동하는지 직접 천천히 따라가봅시다. 아래는 상황 예시입니다

1. No Error : 에러 안 생김
2. Pkt0 corrupt, (NAK 0 ok, corrupt) : 패킷0번이 깨지고, NAK은 깨지지 않고 옴
3. Pkt0 ok, ACK0 corrupt, Pkt0 duplicated : 패킷0이 잘 갔는데, ACK가 깨져서, 패킷0이 중복되어 전송됨
4. Pkt0 ok, ACK0 corrupt, Pkt0 corrupt : 패킷 0이 잘 갔는데, ACK가 깨져서, 패킷0이 중복되어 전송되는데, 이 와중에 깨져서 전송됨.

 

RDT 2.1 정리

sender

• 패킷에 시퀀스 숫자가 더해지는데, 0 또는 1이면 충분할 것 입니다. (왜? : stop and wait)
• ACK, NAK이 제대로 왔는지 확인해야 합니다.
• 상태가 두 배가 요구됩니다. 현재 받아야 하는 패킷이 0인지 1인지를 기억하고 있어야 합니다.

receiver

• 패킷이 중복되는지 검사해야 합니다.
• receiver는 sender가 ACK, NAK을 잘 받았는지 알 수 없습니다.

---

1.5 RDT 2.2

NAK를 사용하지 않는 방법에 대해 알아보도록 하겠습니다.

아이디어는, NAK대신 ACK에 시퀀스를 더해 ACK만 사용하는 것입니다.

 

상태 머신은 절반은 똑같기 때문에 절반씩만 살펴보도록 하겠습니다.

(그림이 헷갈릴 수 있는데, receiver FSM에서 왼쪽 action은 state0에 해당하고, 아래 action은 state 1에 해당합니다)

 

sender가 패킷을 보낼 때, 깨지거나 seq이 1로 간 상황을 가정하겠습니다.

 

• receiver는 ACK0을 기다리는 state에서, 패킷이 깨지거나 다른 seq가 오면, 기존에 만들어 둔 ACK number를 가진 패킷을 보내서, sender에게 다시 보내달라고 요청합니다.
• sender는 ACK0을 기다리는 state에서, ACK1이 오거나 패킷이 깨지는 경우 재전송을 합니다.

receiver state가 1번을 기다리고 있다가, 정상적으로 받게 되면, ACK1을 보냅니다.

---

1.6 RDT 3.0

지금까지는 bit error가 발생했을 때, 해결하는 법을 살펴보았습니다.

하지만 만약 패킷 자체가 유실이 된다면 어떻게 될까요? receiver 입장에서는, 패킷이 유실 됐는지 알 방법이 없습니다.

따라서 sender에서 time-out을 사용합니다.

 

sender

 

 

receiver

 

receiver는 RDT2.2와 동일합니다. (receiver는 패킷 유실을 알 수 없기 때문에)

 

sender action 중 특이한 점들이 있는데, 패킷 corrupt가 일어나거나 ACK를 잘못 받았을 때, 가만히 있는 action을 취합니다.

또한, application의 rdt_send 콜백을 기다리고 있는 상황일 때, rdt_rcv를 무시합니다.

이렇게 처리하는 이유를 아래에서 설명드리도록 하겠습니다.

 

기본적으로 패킷이 유실되었을 때, timer에서 시간을 측정하다가, timeout이 발생하면 패킷을 재전송합니다.

 

 

 

 

 

 

 

 

하지만 아래와 같은 복잡한 상황이 생길 수도 있습니다.

 

 

 

위 상황은 패킷 1을 전송한 후에, ACK1이 도달하는데 시간이 많이 걸려 timeout이 발생한 경우입니다.

timeout이 걸려서 패킷1을 재전송 했지만, 늦게 도착한 ACK1이 sender에게 도달하게 되어 상황이 꼬였습니다.

 

이러한 상황은, ACK0을 기다리는 state에서, ACK1이 도착했을 때 아무것도 안 하는 것으로 해결할 수 있습니다.

잘 생각해보면, 패킷 1을 재전송 한 후, 늦게 도착한 ACK1이 도달하게 됩니다. 이 때 sender는 패킷 0을 보내고 state는 ACK0을 기다리는 state가 됩니다.

이 때 패킷1을 재전송한 것에 대한 ACK1가 도착하는데, 이를 무시하게 되므로, 상황이 더이상 꼬이지 않게 됩니다.

 

 

 

 

 

또 다른 복잡한 상황으로, application이 데이터를 늦게 줘서, state가 wait for call 0 from above에 머물 때입니다.

 

 

아까의 상황은 늦게 도착한 ACK1을 받을 때, sender의 state가 wait for ACK0였습니다. 하지만 application이 콜백을 하지 않아 state가 이전에 머물러 있는 경우입니다.

이럴 때 ACK1과 같은 패킷이 올 수 있는데, 어떤 패킷인지 상관 없이 무시를 합니다. 이렇게 상황은 꼬이지 않고 application의 콜백이 이루어지면 다음부터 정상적으로 흘러가게 됩니다.

 

---

1.7 RDT 3.0 성능

RDT 3.0은 정확하지만, 성능이 좋지 않습니다.

stop and wait 방식을 사용하기 때문에, ACK를 받아야 하나의 데이터 전송이 끝났다고 할 수 있습니다.

 

예를 들어, 1 Gbps link, 15ms prop delay, 8000 bit packet을 전송한다고 했을 때,

하나의 데이터를 보내는 데 걸리는 시간은 아래와 같습니다.

 

 

sender 입장에서 네트워크 사용량은 아래와 같습니다.

 

이렇게 좋지 않은 성능을 개선할 방법, Pipelined protocols에 대해 다음 시간에 알아보도록 하겠습니다.

 

 

 

 

본 글은 Computer networking : a top-down approach 라는 책을 통해 작성되었습니다.