1. rtd2.1
- Sender adds sequence number to each packet
- Sender retransmits current packet with same sequence number
when receive garbled ACK/NAK- Receiver discards duplicate packet
시퀀스 넘버를 사용해서 패킷에 번호를 붙인다고 했는데 시퀀스 넘버를 붙이는 가장 직관적인 방법은 순서대로 0, 1, 2, 3, 4, 5, 6, 7, 8 붙이면 됩니다. 그러면 이 시퀀스 넘버는 부가적인 정보로써 헤더에 들어갑니다.
그러면 헤더에 어떤 하나의 시퀀스 넘버가 자리 잡는 어떤 필드로서 적힐 것 입니다. 만약에 0번부터 시작해서 쭉 번호를 붙여서 무한대로 나가면 계속 커지게 됩니다. 이 헤더는 실제 보내고자 하는 메시지에 부가적으로 보내는 엑스트라 파트입니다. 그래서 최소한의 필드들만 사용해야 될 뿐만 아니라, 각 필드들의 크기는 가능한 최소의 크기가 되야합니다. 즉, 헤더에 붙는 정보들은 최소화가 되야합니다.
이 프로토콜은 단순한 프로토콜이라서 한 번 보내고, 상대방이 받았는지 확인한 다음에 다음 것을 보내게 됩니다. 그러니까 0, 1 을 돌려쓰게 되서 한 비트로 가능합니다. 그러므로 아래의 예제의 프로토콜에서는 시퀀스 넘버 두 개를 가지고 중복된 패킷인지 아니면 새로운 패킷인지 표현 할 수 있습니다.
2. rtd2.1 Introducing Sequence Number
sender가 패킷 보내는데 시퀀스 넘버 0번으로 담아서 보냅니다. 이 상황에서는 receiver는 시퀀스 넘버 1번을 기다리면 됩니다. 그런데 이게 에러가 생기면 sender는 receiver가 잘 받았는지, 안 받았는지 모르니까 피드백을 받아도 피드백이 에러가 나면 ACK인지 NAK인지 확인할 길이 없습니다.
그래서 지금 receiver 상황을 몰라서 “그래 너를 위해서, 한 번 재전송 더 해준다” 해서 재전송을 하는데 그것이 같은 패킷이 됩니다. 그런데 receiver는 1번 패킷을 기다리고 있습니다. 그래서 중복인 걸 알기 때문에, 이 패킷을 받아들이지 않고 ACK를 보내줘야 됩니다. 그래야 sender가 새로운 것을 보내주게 됩니다. receiver는 무조건 제대로 받으면 ACK는 보내줘야 합니다.
3. rdt2.1: Summary For Packet Error
Mechanisms for channel with packet errors
- Error detection, Feedback, Retransmission, Sequence#
Sender:
- Seq # added to pkt
- Must check if received ACK/NAK corrupted
- Retransmit on NAK or corrupted feedback
Receiver:
- must check if received packet is duplicate-
- send NAK if received packet is corrupted-
• Send ACK otherwise
지금 에러 있는 상황에서 피드백 에러이든, 데이터 에러든, 패킷 에러든 간에 우리가 error detection이랑 feedback, retransmission, sequence number 사용해서 해결했습니다.
동작을 보면 sender는 보낼 때 시퀀스 붙여서 보내고, 그 다음에 피드백에 대해서 에러 체킹을 해서, 에러가 있을 경우에는 재전송하고, 피드백에 에러가 없을 경우에 그게 negative 피드백이면 재전송 입니다.
그리고 receiver는 시퀀스를 한 번 트래킹해서 내가 지금 받아야 할 번호가 뭔지 계속 알아내서 그 번호가 아니면 그냥 버리고 간다고 했습니다. 그리고 무조건 ACK 보내야 하는데, 만약에라도 에러가 있을 경우에 NAK 보내게 됩니다.
4. rdt2.2: a NAK-free Protocol
- Same functionality as rdt2.1, using ACKs only
Instead of NAK, receiver sends ACK for last correctly received packet
- Receiver must explicitly include seq # of pkt being ACKed
- Duplicate ACK at sender results in same action as NAK： retransmit current pkt
이렇게 하면 완벽하게 에러인 상황에서 신뢰성 있는 프로토콜이 가능하지만 ACK랑 NAK 둘이 있어서 복잡합니다. 그래서 실제 원리는 똑같지만 NAK를 없앤 ACK만을 사용한 프로토콜도 가능합니다.
sender랑 receiver랑 있으면 sender에서 보내면, receiver는 NAK 없이 무조건 받으면 ACK를 보냅니다. 이 ACK라는 피드백 안에 시퀀스 넘버를 적어 보내줘야 합니다. 여기 들어가는 시퀀스 넘버는 가장 마지막으로 제대로 내가 받은 시퀀스 넘버 0번을 함께 보냅니다. 그럼 0번 잘 받았다는 것 입니다.
이제 sender가 1번 보냅니다. 그런데 이게 오다가 에러가 났다고 가정합니다. 그럼 받아왔는데 에러입니다. 얘가 지금 뭘 받긴 받았으니까, ACK는 보내야 됩니다. ACK는 보내는데, 이 ACK의 번호가 뭐냐면, 지금까지 제일 마지막으로 잘 받은 게 0번 입니다 그래서 0번을 같이 보내는 겁니다.
지금 sender는 1번 보냈는데, 0번이 왔습니다 그러니까 지금 receiver 상황을 아는 것 입니다. 지금 방금 내가 1번 보냈는데, 이거 안 갔구나. 이게 지금 negative negative 피드백으로 처리되는 것 입니다. 무조건 ACK를 사용하되, 그 ACK 안에 들어가는 시퀀스 넘버는 가장 마지막으로 제대로 받은 시퀀스 정보를 집어넣으면 되는 것 입니다.
5. rdt3.0: Channel with Loss & Packet Errors
What mechanisms do we need for packet loss?
- Timer!
Sender waits "reasonable" amount of time for ACK (a Time-Out)
If packet (or ACK) is just delayed (not lost)：
- Retransmission will be duplicate, but use of seq. #'s already handles this
마지막 현실적인 상황으로 언더라인 채널에 에러뿐만 아니라, 메시지 유실도 가능한 경우를 보겠습니다. 저런 상황에서 reliable한 의사소통이 되면 이게 완전체 입니다. 에러가 있는 상황에 대해서 우리가 메커니즘을 다 구해놨기 때문에, 로스 있는 상황에 뭔가 처리될 수 있게 그런 메커니즘만 붙이면 됩니다.
만약에 보낸 메시지가 유실되면 Sender 입장에서는 아무것도 안 듣게 됩니다. Sender가 전화 통화로 “오늘 저녁 같이 먹을래?” 하는데, 이 메시지가 만약에 중간에 가서 유실되고 가정하겠습니다. 그러면 침묵이 흐르게 됩니다. Receiver는 아무것도 못 들었고, Sender도 기다리고 있고. 침묵이 흐르면서 누군가 답답해서 이야기를 꺼내게 됩니다. “야 내 말 못 들었어?”
그러니까 우리 마음속에는 시간이 흐르고 있습니다. ‘왜 지금 왜 말 안 하지?’ 이러면서 ‘못 들었나?’ 마찬가지로 Sender가 패킷을 보냈는데 '유실됐나?'라고 응용하는 것 입니다. Sender가 피드백을 못들으면 Sender 입장에서는 그냥 메시지 패킷 보내고 나서 아무 말도 안 들리게 됩니다. 이 때 이 상황을 해결할 수 있는 건 타이머뿐 입니다.
Sender는 패킷을 보낼 때마다 타이머를 실행시켜서, 패킷 보내고 타이머가 작동합니다. 만약 패킷이 유실되었으면 아무 피드백도 없을 겁니다. 그러면 타이머가 울리고 지금 유실된 것으로 판단하고, 재전송하면 되는 겁니다.
매번 패킷 보낼 때마다 타이머를 실행시켜서, 타이머가 터지면 재전송 합니다. 그러면 과연 이 타이머의 시간을 얼마나 맞춰야 하는지 문제가 생깁니다. 이건 정답이 없는 문제입니다. 실제로는 저 적당히가 얼마큼 되는지는 수치로 정해져 있습니다.
중요한 것은 왜 이게 수치로 나오기 어렵냐면 이게 트레이드 오프가 있기 때문입니다. 예를 들면 이 타이머의 시간이 굉장히 짧으면. 장점으로는 내가 패킷을 보내고, 이 타이머 시간 딱 금방 타이머가 금방 흘러서, 그때까지 피드백이 안 들리면 재전송을 하게 됩니다.
짧은 타이머를 쓰면 실제로 유실이 일어났을 경우에, 리커버리가 빠릅니다. 즉, 유실되면 바로 재전송해버리기 때문입니다. 그러나 단점도 있습니다. 혹시 이 패킷 좀 멀리 갔다 와서 오래 걸려서 돌아 온것인데, 성급하게 판단 한것이 됩니다. 그래서 네트워크에 중복된 패킷들이 나가게 되고, 그러면 네트워크에 오버헤드를 주게 됩니다. 반대로 이 타이머가 굉장히 길었다, 그럼 장점이 네트워크에 오버헤드는 적게 갑니다. 단점은 너무 신중해서 에러가 발생했을 때 반응이 늦어지게 됩니다.
짧게 잡으면 내가 리액션 리커버리는 빠른데 네트워크 오버헤드가 크고, 길게 잡으면 네트워크 오버헤드는 적게 나는데, 실제 로스가 발생했을 때 로스 극복이 느리게 되니다. 그렇기 때문에 이거 타이머를 어떻게 잡느냐 그것도 사실 중요한 이슈 입니다. 그럼 생각해 봅시다. 마지막으로. 타이머를 굉장히 짧게 잡았다고 쳐봐. 타이머를 짧게 잡아서, 패킷을 딱 보낼 때 타이머를 딱 틀고, 이게 가서 제대로 돌아오고 있는데, 내 타이머가 빨라서 터졌습니다.
그럼 나는 이거 재전송하는 거죠. 근데 그러면 지금 이거 사실 제대로 돌아가고 있는 거잖아. 그러면 중복된 패킷은 receiver에서 버려야 합니다. 지금 우리 메커니즘에 따르면 receiver가 제대로 버립니다. 그러니까 문제는 없습니다. Receiver가 처리를 해주니까 문제는 없는데, 어쨌든 이게 많이 나가게 되면 네트워크에 문제가 됩니다.
6. rdt3.0 in action
(a)는 네트워크가 평안할 때, 아무 일도 없을 때, sender 패킷 보내고, receiver는 무조건 ACK 보내지. 그 ACK의 시퀀스 넘버는 가장 최근에 잘 받은 거. 왔다 갔다 하게 됩니다.
(b)는 드디어 유실이 발생한 상황 입니다. 첫 번째 패킷 가고 잘 받아서 ACK 보내고, 두 번째 패킷 가다가 유실됬습니다. Sender는 이거 보낼 때 이미 타이머로 재고 있으니까, 타이머 빵 터지면서 재전송을 합니다. 그럼 별일 없이 가는 것 입니다. 어차피 receiver가 1번 기다리고 있습니다. 근데 1번 재전송 됬기 때문에 아무 일 없이 잘되게 됩니다.
(c)는 ACK가 유실된 상황입니다. 시퀀스 넘버 0번 패킷 잘 가고, ACK 오고, 시퀀스 넘버 1번 패킷 가고, 잘 받아서 ACK 1번 오는데, 그게 유실됐습니다. 어차피 sender 입장에서는 가는 패킷 유실되나 오는 피드백이 유실되나 똑같습니다. 둘 다 침묵이 흐르는 건 마찬가지 입니다. 마찬가지로 침묵이 흐르다가, 이게 타이머가 뻥 터지면 sender는 그냥 같은 거 시퀀스 넘버 1번 재전송 입니다. 근데 실제로는 receiver는 1번 잘 받았 습니다. 지금 0번 기대하고 있는데 1번이 왔으니까 버리고 ACK만 해주는 겁니다. ACK는 1번 잘 받았습니다 그래서 1번으로 계속 진행하게 됩니다.
(d)는 마지막 상황. 이번에는 timeout이 성급하게 먼저 뻥 터진 상황입니다. 똑같이 0번 시퀀스 갔다가 오고 1번 시퀀스 넘버 갔다가 이게 피드백이 오는데, 피드백이 좀 늦게 왔습니다. 늦게 온 상황에서 타임아웃이 터진 겁니다. 터졌으니까 역시 1번이 나가야 합니다. 똑같은 패킷 재전송하고, 그 사이에 피드백이 왔어. 왔으니까 sender는 잘 받았으니까 그 다음 시퀀스 넘버인 0번을 씁니다. 근데 그 사이에 1번 재전송한 게 갔을 것 입니다. 지금 receiver는 0번 기다리고 있는데, 1번이 온 거니까 이거 중복 패킷인 거 알고 버리고, 무조건 ACK는 해야합니다. ACK는 지금까지 잘 받은 거 1번이니까 1번으로 보냅니다.
핵심은 이 rdt 프로토콜 3.0 완벽하게 동작해. ‘완벽하게’라는 얘기는 뭐냐면 sender와 receiver 사이에 신뢰성 있는 통신 완벽하게 하는 것 입니다. 신뢰성 있게 가긴 가는데 어떤 상황이 이후에 펼쳐질지 한 번 생각해봅니다.
