Transport Layer - 3. Reliable data transfer Design (2)

1. Reliable data transfer design

이제 reliable data transfer에 대한 기본적인 내용은 다 배웠다.
이번장에서는 reliable data transfer 설계를 수행한다.

구체적으로 우리가 할 일은 하위 계층이 제공하는 udt_send(), rdt_rcv()(비신뢰성 패킷 전달 채널을 사용하는 api)를 사용해서 신뢰성 있는 전달 기능을 구현한 다음 상위 계층에게 rdt_send(), deliver_data() 라는 api를 제공하는 것이다.

설계 복잡도를 살짝 낮추기위해 아래 두가지를 가정한다.
1. checksum으로 bit error를 탐지할 수 있다.
2. packet loss는 없다고 가정한다.

2. case1 : no error

패킷을 전송하고 ack를 수신 할 동안 에러가 발생하지 않은 경우이다. (&&notcorrupt)

1. sender : app이 rdt_send api를 호출하면 데이터, checksum이 담긴 패킷을 만든다.
2. sender : udt_send api를 사용해서 하위 계층에게 패킷 전송을 부탁한다. (이제 ack를 기다리는 상태가 된다.)
3. receiver : rdt_rcv api로 하위계층으로부터 패킷을 받고 상위 계층에게 deliver_data로 데이터를 전달한다.
4. recevier : 그 다음 ack를 sender에게 보내준다.
5. sender : rdt_rcv로 리스폰스를 받고 ack인지 확인

이렇게 패킷을 보내고 응답(ack,nack)을 기다리는 모습을 따서 stop&wait protocol이라고 한다.
참고로 stop&wait protocol을 사용하면 패킷을 "하나" 보낼 때마다 receiver가 잘 받았는지 응답을 기다려야 한다.

3. case2: with error

receiver에서 에러를 탐지한 경우 (rdt_rcv&&corrupt, 받은 메시지에 에러가 있는 경우)

1. sender : app이 rdt_send api를 호출하면 데이터, checksum이 담긴 패킷을 만든다.
2. sender : udt_send api를 사용해서 하위 계층에게 패킷 전송을 부탁한다. (이제 ack를 기다리는 상태가 된다.)
3. receiver : rdt_rcv api로 하위계층으로부터 패킷을 받았다. 그런데 에러가 발견되었다. (corrupt(rcvpkt))
4. recevier : nack를 sender에게 보내준다.
5. sender : rdt_rcv로 리스폰스를 받고 nack임을 확인
6. sender : udt_send로 패킷을 다시 전송 (이제 ack를 기다리는 상태가 된다.)
......
n. sender : rdt_rcv로 리스폰스를 받고 ack인지 확인

이렇게 패킷을 보내고 응답(ack,nack)을 기다리는 모습을 따서 stop&wait protocol이라고 한다.

4. case3 : Ack, Nack 수신이 실패한 경우

ack, nack가 유실된 경우 sender는 receiver가 어떤 상황인지 알 수 없음.
그냥 재전송해버리면 receiver가 중복 패킷을 수신할 수 있음.
따라서 sender가 보내는 패킷에 sequence number를 붙여서 보내주자. 그럼 receiver는 번호를 보고 내가 이미 받은 패킷인지 확인하고 버릴 수 있다.

참고로 stop&wait프로토콜의 경우 패킷을 하나씩 보내고 응답을 확인하기 때문에 sequence number를 0,1 한비트만 사용하면 된다.
아래 세가지 상황을 가정해보자.
1) 1번 A패킷을 보냄 -> 0번 B패킷을 보냄 -> 1번 C패킷을 보냄 : 문제없음
2) 1번 A패킷을 보냄 -> 1번 A패킷을 보냄 중복!! : sequence number가 중복되므로 두번째로 받은 패킷 버림
3) 1번 A패킷을 보냄 -> 0번 B패킷을 보냄 -> 1번 C패킷을 보냄 -> 0번 D패킷을 보냄 -> 0번 D패킷을 보냄 중복!! : sequence number가 중복되므로 다섯번째로 받은 패킷 버림
0,1 만 sequence number로 사용해도 전혀 문제가 없다.

sender 입장에서의 finite state machine

1. wait for call 0 from above : sender가 패킷을 보낼때, sndpkt = make_pkt(0, data, checksum)을 보면 패킷의 sequence number, 보낼 데이터, checksum으로 패킷을 만든다. 그 다음 만든 패킷을 보낸다.
2. wait for ack or nack 0 : 0번 패킷을 보낸 직후 상태,
- 송신자가 수신한 메시지가 notcorrupt(ack 메시지가 checksum통과)이고 ack라면 다음 state로 이동한다.
- 반면 받은 응답이 corrupt(ack/nack메시지의 checksum이 틀림)되거나 nack(수신자가 받았던 패킷이 bit error가 있음을 알림)라면 패킷을 다시 보내고 기다린다.
3. wait for call 1 from above : 0번 패킷은 전송이 잘 되었으니 동일하게 다음 패킷에 1번을 붙여서 전송을 한다.
4. wait for ack or nack 1 : 1번 패킷을 보낸 직후 상태, 응답으로 받은 메시지의 상태, 내용에 따라서 다음 state로 이동

receiver 입장에서의 finite state machine

1. waiting for 0 from below : 0번 패킷이 전송되길 기다리는 상태
- 패킷을 수신했는데 패킷의 checksum에 문제가 없고 sequence 넘버도 0번으로 맞다면 데이터를 상위 계층에게 추출해서 보내준다. -> ACK0 응답을 보내준다. -> 다음 state로 이동
- 그러나 패킷을 수신했는데 corrupt(bit error)되었다면 nack0를 응답으로 보내준다. -> 아직 동일한 state에 머무름
- 그러나 패킷을 수신했는데 sequence number가 1인 경우(중복된 패킷을 받았음) -> 받은 패킷을 버림 -> 송신자가 이전 ack를 못 받은 것일 수도 있으니 ack를 또 보내준다. -> 아직 동일한 state에 머무름
2. waiting for 1 from below : 0번 패킷을 잘 수신한 다음이므로 1번 패킷이 전송되길 기다리는 상태이다. 위에 설명한 동일한 경우의 수를 따른다.

참고로 stop&wait 프로토콜이기 때문에 0,1두 비트만 사용하고 있고 ack에는 sequence number가 붙지 않는다.

4. Nack를 안 쓰고 싶은 경우

직전까지 설계한 sender, receiver간의 신뢰성 있는 전달 모델에서 nack를 안쓰고 ack만 사용하는 모델로 수정을 해보자.
그리고 지난 모델의 경우 ack에 sequence number가 따로 붙지 않았는데 이번에는 붙여서 모델을 설계해 볼 것이다. ack에 잘못된 seq no.가 붙은 경우 nack의 의미를 갖도록 할 것이다.

sender 입장에서의 finite state machine

1. wait for call 0 from above : sender가 패킷을 보낼때, sndpkt = make_pkt(0, data, checksum)을 보면 패킷의 sequence number, 보낼 데이터, checksum으로 패킷을 만든다. 그 다음 만든 패킷을 보낸다.
2. wait for ack or nack 0 : 0번 패킷을 보낸 직후 상태,
- 송신자가 수신한 메시지가 notcorrupt(ack 메시지가 checksum통과)이고 ack0라면 다음 state로 이동한다.
- 반면 받은 응답이 corrupt(ack메시지의 checksum이 틀림)되거나 ack1(수신자가 받았던 패킷이 중복이거나 bit error가 있음을 알림)이라면 0번 패킷을 다시 보내고 기다린다.
3. wait for call 1 from above, 4. wait for ack or nack 1 : 위에서 설명한 동일한 경우를 따른다 (그림에서는 생략)

receiver 입장에서의 finite state machine

1. waiting for 1 from below : 0번 패킷이 전송되길 기다리는 상태
- 패킷을 수신했는데 패킷의 checksum에 문제가 없고 sequence 넘버도 1번으로 맞다면 데이터를 상위 계층에게 추출해서 보내준다. -> ACK1 응답을 보내준다. -> 다음 state로 이동(waiting for 0 from below)
- 그러나 패킷을 수신했는데 corrupt(bit error)되었다면 ack0를 응답으로 보내준다. -> 아직 동일한 state에 머무름
- 그러나 패킷을 수신했는데 sequence number가 0인 경우(중복된 패킷을 받았음) -> 받은 패킷을 버림 -> 송신자가 이전 ack0를 못 받은 것일 수도 있으니 ack0를 또 보내준다. -> 아직 동일한 state에 머무름
2. waiting for 0 from below : 0번 패킷을 잘 수신한 다음이므로 1번 패킷이 전송되길 기다리는 상태이다. 위에 설명한 동일한 경우의 수를 따른다.

5. bit error 뿐만아니라 loss도 고려할 경우

crc나 checksum으로 bit error는 감지하는 모델을 만들어보았다. 하지만 이번에는 패킷 loss도 고려한 모델을 만들어보자.
data packet 뿐만 아니라 ack도 중간에 소실될 수 있다.

총 5가지 경우가 발생할 수 있다.
이번에는 checksum, ack, sequence number, 재전송 외에도 다른 장치가 필요하다. 바로 Timer이다.
sender는 합당한 시간동안 ack를 기다린다. 그 시간 내에 ack가 도달하지 않으면 timeout이 발생한 것으로 인지하고 패킷을 다시 전송한다.
ack가 소실된게 아니라 조금 늦는 것 일 수도 있다. 뒤늦게 도착한 ack는 seq#를 보면 sender가 상황을 인지할 수 있기 때문에 전혀 문제가 없다. (받은 ack를 그냥 버린다)

- (c)에서 receiver의 경우 duplicate 패킷을 감지했다. ack1을 sender가 받지 못 했다는 사실을 알았기 때문에 ack1을 다시 보내준다.
- (d) 같은 상황은 timeout이 짧거나 pkt1이 도착을 늦게 했거나 ack1이 늦게 도착했거나 하면 발생한다. 뒤늦게 도달한 ack1을 보고 sender는 다음 보낼 0번 패킷을 송신한다. ack1이 옛날 것이라는 것을 모르지만 전혀 문제가 없다. 하지만 한 번 순서가 엇갈리는 바람에 sender는 ack1을 두 번 수신해서 pkt0을 두 번 보냈고 receiver도 두번 중복 패킷을 수신하여 ack1 두번 ack0 두번 보내게 된다. 즉 loss가 없었음에도 불구하고 네트워크 혼잡도가 가중된다. 따라서 아주 적절한 timeout을 설정하는 것이 중요하다.

그렇다면 합당한 timeout 시간은 어느정도 여야 할까?
설정한 timeout이 너무 길면 시간 낭비이다. loss를 오래 기다린다. loss의 발생을 최대한 빨리 알아채는 것이 이득이다.
반면 timeout이 너무 짧으면 반면 너무 조금 기다리면 수신자는 너무 많은 duplicated packet을 수신하게될 수 있다. 뿐만 아니라 time, bandwidth, energy의 낭비, 네트워크 혼잡도를 가중하는 일이기도 하다.

게다가 네트워크를 구성하는 여러 router, queueing delay, cogestion을 고려해서 timeout을 추정하기는 쉽지 않다.

(좌상단) application layer로부터 데이터 전송 메시지를 받으면 하위 계층에게 0번 패킷 전송을 부탁하고 나서 timer를 세팅한다.
->
(우상단) 그 다음 ack0를 기다리는 상태가 된다.
i) 수신한 ack 패킷이 corrupt, 혹은 ack가 왔는데 1번이면 ack 버리고 다시 대기 상태
ii) timeout 발생시 다시 패킷을 재전송하고 timer 재설정하고 다시 대기 상태
0번 ack가 문제 없이 수신되면 다음 상태로 이동
->
(우하단) (좌하단) 위에 설명한 동일한 경우를 따른다. sequence number만 1번이다.

지금 우리가 설계한 신뢰성 있는 전송 방식은 stop&wait protocol이다. 아무리 대역폭이 커지더라도 한 패킷씩 보내고 기다리기 때문에 성능이 좋지 않다.

한번 보내는 패킷의 크기는 L비트이다. 이 한개의 패킷을 보내는데 RTT + L/R 시간이 걸린다.
1Gbps의 link를 사용하는데 1KB(1000byte) 패킷을 stop&wait 방식으로 보내면 33bit/sec throughput이 나오고 link untilization은 매우매우 낮다.