1. Recap: Principles of Reliable Data Transfer
What can happen over unreliable channel?
- Packet error, packet loss
What mechanisms for packet error?
- Error detection, feedback, retransmission, sequence#
What mechanisms for packet loss?
- Timeout!
We built simple reliable data transfer protocol
- Real-world protocol (e.g.t TCP) is more complex, but with same principles!
unreliable한 네트워크에서 일어나는 일은 패킷 에러랑 패킷 로스가 일어납니다. 이를 극복하기 위해서 메커니즘을 하나씩 집어넣었는데, 패킷 에러를 위한 메커니즘이 error detection, feedback, retransmission, sequence number. 그리고 로스를 위한 것이 타이머 입니다.
이런 게 unreliable한 상황을 극복하기 위해서 필요한 메커니즘 입니다. 그런데 TCP라는 거는 이런 reliable한 기능을 제공하는 서비스 입니다. 그러니까 이런 메커니즘이 구현되어 있습니다. 그러면 이런 메커니즘들이 당연히 TCP 어떤 동작, 실제 워킹 코드 안에 구현되어 있습니다. 이런 정보들이 어디에 또 담겨갈까 패킷 이 헤더 부분에 어떤 정보, 필드로서 담겨 가야 될 것 입니다.
그래서 저런 피드백이니 error detection이니 뭐 저런 것들이 다 TCP 헤더에 필드들로 다 구성되어 있습니다. 그런데 TCP가 또 제공하는 기능이 reliable한 transfer 기능뿐만 아니라 많습니다. 그렇기 때문에 TCP 헤더 안에 들어가는 이 필드들이 더 많을 수밖에 없고, 각각 의미가 다 있게 됩니다.
2. Pipelined Reliable Data Transfer Protocol
unreliable한 상황에서 reliable한 기능을 제공하는 메커니즘을 원리를 이해해도 지금 이거 가지고 현실 세계에 나갈 수 없습니다. 이 rdt라는 프로토콜은 너무나 단순하기 때문입니다. 어떤 면에서 단순하냐면 한 번에 하나의 패킷밖에 못 보냅니다. 즉, 패킷 하나 보내고 도착한 거 확인했으면, 하나 보내고, 확인하고, 하나 보내고, 확인합니다.
utilization이라는 건 어떤 의미냐면, 전체 시간 중에서 sender가 네트워크를 사용하는 순간의 비율입니다. 그래서 전체 시간 중에 sender가 네트워크를 사용하는 비율이 크면 클수록 좋은 겁니다.
왜냐하면, 고속도로 16차 딱 깔아놓고선 차가 같이 달려야지 이게 효율이 높은 거지, 깔아놨는데 그냥 차 한 대만 달리고 있으면 이렇게 해 놓을 이유가 없기 때문입니다. 그래서 이 효율이 얼마큼 좋으냐가 중요한 척도입니다.
실제로 우리가 지난 번에 얘기한 reliable data transfer protocol은, sender가 receiver한테 데이터, 패킷을 보냈는데, 한 번에 하나씩 보냈습니다. 한 번에 패킷 하나 보내고, 받은 거 확인하고, 다음 패킷 보내고, 그런 식으로 했습니다.
이제 패킷 하나를 보내는데 걸리는 기본적인 시간이 있습니다. 그것이 트랜스미션 타임 입니다. 그리고 데이터 패킷이 갔다가 피드백이 돌아올 때까지 걸리는 그 시간, 즉 라운드 트립 타임(Round trip time)동안 sender는 아무것 안 받아들입니다. 라운드 트립 타임만 기다리고 그래서 그만큼 아무것도 안 합니다. 그럼 결국에는 utilization을 구해보면 0.1%도 안 되게 되고 너무나 비효율적 이게 됩니다.
그림을 보면, sender가 데이터 패킷 보내고 갔다 올 때 동안 아무것도 안 합니다. 즉, 네트워크 사용을 안 합니다. 갔다 오고 나서 피드백 돌아온 거 확인하고 보내고 지금 한 16차선 고속도로가 뚫려 있는데 차 한 대 뿅뿅 이렇게 가는 것 입니다. 물론 신뢰성은 있는 통신입니다.
3. Pipelined protocols
실제로는 TCP는 이런 방식으로 동작합니다. 지금 우리가 본 게 (a) 입니다. 데이터 가고 피드백 오고 다시 보내고. 실제로는 (b)처럼 패킷을 쏟아붇습니다 피드백 안 받고 쫙 쏟아붓고 한꺼번에 피드백 받는 식 입니다.
우리가 지향해야 될 것은, Pipelining을 통해서 한 번에 쏟아붓고 한꺼번에 받고 이렇게 해야합니다. 그래야 효율이 높을 것 입니다. 방금 봤던 그래프로 그리면, 아까는 이제 한 번에 하나씩 보냈는데, 아래의 그림처럼 한 번에 3개씩 보낸다고 칩시다. 그럼 utilization이 벌써 세 배만큼 늘어납니다. 한꺼번에 많이 보내면 보낼수록 utilization이 높아지는 것을 확인할 수 있습니다.
그림을 보면 한꺼번에 데이터를 막 마구잡이로 보내고 걔네들에 대해서 각각을 피드백을 받고 이런 식으로 해야합니다. 그래야 네트워크를 잘 활용하는 것이 됩니다. 이렇게 하려면 피드백, 시퀀스 넘버 관리, 이런 게 복잡해집니다. 그래서 이렇게 단순한 원리를 바탕으로 작동을 하긴 하지만, TCP가 복잡하게 됩니다.
4. Go-Back-N
-
Sender:
- K-bit seq # in pkt header
- "Window" of up to N, consecutive unack’ed pkts allowed
go back n은 현실 세계에서 존재하는 프로토콜이 아닙니다. 이러한 Pipelining 방식의 신뢰성 있는 통신을 구현하기 위해 준비한 하나의 어프로치를 나타내는 것 입니다. 가장 중요한 건 무슨 어프로치든 간에 이제는 한꺼번에 많은 패킷을 쏟아 부을 것 입니다.
그렇기 때문에 그러면 한꺼번에 얼마큼 많이 보낼 거냐는 또 기준이 있어야 합니다. 그게 바로 윈도우 사이즈입니다. 그래서 윈도우 사이즈가 딱 정해지면, 윈도우 사이즈만큼은 그냥 피드백 받지 않고, 그냥 한꺼번에 보낼 수 있습니다.
예를 들면, 보내야 할 패킷의 시퀀스 넘버가 있는데, 윈도우 사이즈가 4 입니다. 그러면 우선 0, 1, 2, 3번 패킷은 한꺼번에 쭉 가는 겁니다. 그리고 이 go back n이라는 스타일에서 ACK는 어떤 성격을 가진 ACK냐면 cumulative 입니다. 이게 뭐냐면, 쌓는다는 의미 입니다. 예를 들어 ACK 11번이다. 이러면 go back n에서는 무슨 뜻이냐면, 11번까지 하나도 빼놓지 않고 다 잘 받았고 12번 기다리고 있다라는 의미 입니다.
5. GBN in action
윈도우 사이즈가 4라서 한꺼번에 피드백 없이 보낼 수 있는 게 4개 입니다. 그래서 sender가 0, 1, 2, 3번은 한 번에 보냈습니다. 그리고 타이머를 다 켜주었습니다.
receiver가 0번 받아서 ACK 0번 날리고, 그 다음에 1번 기다리고 있는데, 1번 들어와서, ACK 1번 날리고. 그 다음에 2번 기다리고 있는데 없어졌고 그런 상황에서 3번이 왔습니다. 이 receiver가 지금 2번 기다리고 있는데 3번이 왔습니다 그래서 3번을 버리게 됩니다. 2번 아니면 안 받게 됩니다. 3번 버리고 ACK 1번 입니다. 1번까지 잘 받았으니까.
이 상황에서 sender의 모습을 보면, receiver가 ACK 몇 번 보냈었죠? 제일 처음에 0번 보냈고 0번이 도착하면 타이머 제거하고, 0번은 이제 여기 윈도우 안에 있을 필요가 없습니다. 윈도우를 전진시킵니다.
이제 다음 보내주는 거지. 다음 보내면서, 역시 타이머 설치 그 다음에 ACK 1번 보냈지. ACK 1번 받았으니까 이제 더 이상 있을 필요 없습니다. 또 윈도우 전진을 시켜줍니다.
이제 5번도 보낼 수 있게 됩니다. 해서 4번 5번 이렇게 쭉 나가는 상황입니다. 그런데 4번 5번 보내는데, 역시 receiver는 이 패킷들 안 받습니다.
receiver는 2번 기다리고 있습니다. 그래서 다 버리고, 4번 5번 보낸 거 다 버리고, ACK 몇 번 보내줘? 1번 보내줍니다. ACK 1번 보내주는 게 sender한테 의미가 없습니다. 그래서 시간이 조금 지나서 제일 앞에 있는 2번 타이머가 뻥 터질 것 입니다.
뻥 터지면 2번의 행동은 재전송. 얘 터지는 순간 윈도우 안에 패킷은 다 재전송이 됩니다. 2, 3, 4, 5가 가게 되면, receiver는 2번 기대하고 있고, 순서대로 다 받아들이게 됩니다. ACK 계속 보겠지. 이게 go back n의 동작입니다.
만약에 sender와 receiver 사이에 로스도 없고, 에러도 없고 그냥 아주 편한 상태면, 이게 윈도우가 지금 쭉 진행되게 됩니다. 이렇게 끝까지 쭉 간다. 근데 만약에 중간에 유실이 있었다. 예를 들면 6번이 없어졌다. 그러면 어떻게 되는지 생각을 해보면, ACK는 계속 5번만 가고, ACK가 진행이 안되니까 윈도우는 멈추게 됩니다. 그러다 타임아웃되면 다시 6, 7, 8, 9 보내는 거고. 그러니까 유실돼서 타이머가 터지면 결국에는 돌아오되 N개만큼 돌아옵니다. 윈도우 사이즈만큼. 그러니까 go back n이라고 합니다.
윈도우 안에 들어있는 이 패킷은 sender인 내가 버퍼에 저장하고 있어야 합니다. 윈도우 안에 들어있는 애들은 sender인 내가 receiver가 아직 받았는지, 안 받았는지 확인하지 못한 애들 입니다.
윈도우 밖에 있는 패킷은 받았다고 확신하는 패킷이기 때문에 더 이상 저장하고 있을 필요가 없어서 저장할 필요가 없고, 윈도우 안에 있는 애들은 아직 확신하지 못했기 때문에, 혹시라도 재전송이 있을 수도 있으니까 버퍼에서 들고 있어야 합니다. 그래서 윈도우는 일종의 버퍼입니다. 그래서 한 번 윈도우 밖으로 빠져나가게 되면 걔네들은 100% 갔기 때문에 가지고 있을 필요가 없고, 윈도우 안에 있는 애들은 아직 확신할 수 없기 때문에 가지고 있어야 합니다.
Go back n 동작은 이해되는데, 좀 개선의 여지가 많습니다. 지금 이슈 된 거는 예를 들면 6번 하나인데, 얘 때문에 지금 다른 패킷들까지 다 재전송을 해야합니다. 쉽게 이해하려고 윈도우 사이즈 4라고 잡았는데, 실제 시스템에서 패킷 4개씩이 아니라 실제 윈도우 사이즈는 훨씬 큽니다. 한꺼번에 막 몇 백 개씩 보냅니다. 윈도우 사이즈가 100인데, 이게 하나 유실됐다고 다 안보내면, 동작은 하지만 역시 뭔가 개선이 필요합니다. receiver가 지금 아무런 기능을 안 주니까. 그래서 “receiver님 좀 도와줘요”라고 하는 버전이 바로 selective repeat이라는 하나의 또 다른 어프로치 입니다.
6. Selective Repeat
selective repeat은 뭔가 문제가 있을 때 재전송 즉 리핏 재전송을 해주되, selective 하게 없어진 애들만 repeat해 주겠다는 그런 의미 입니다. 그래서 좀 더 개선이 있습니다. 이렇게 selective 하게 재전송을 해주기 위해서는 ACK가 cumulative ACK는 안 됩니다. ACK 11이면 이제는 11번 패킷을 잘 받았다는 의미로 받아들여야지 이제 동작할 것 입니다. 왜냐면 selective하게 재전송할 것 이기 때문입니다.
동일하게 패킷은 각자의 타이머를 유지하고, 타이머가 터지기 전에 ACK를 받으면 타이머를 해제합니다. 예를 들어 ACK 7번 받았다. 그러면 7번까지 다 잘 받았다는 게 아니라 7번만 잘 받았다는 의미입니다.
이제는 receiver가 순서에 맞지 않게 들어온 패킷이라도, 에러가 없으면 버퍼에 저장을 합니다. 예를 들면 receiver가 2번 패킷을 기다리고 있지만 3번이 들어갔다. 그럼 3번은 버퍼에 저장해야 합니다. 2번 자리 채울 때까지. 그 대신 ACK를 다 해줘야 합니다. 이렇게 해주면 좀 더 sender가 편해집니다.
sender가 한꺼번에 4개의 패킷을 보낼 수 있기 때문에 0, 1, 2, 3을 한꺼번에 보냈습니다. receiver는 0번 잘 받았기 때문에 0번 받은 거를 애플리케이션 레이어에 올려주고 ACK 0번. 이제 1번 기다리고 있죠. 1번 잘 와서 ACK 1번. 그런데 2번이 없어졌습니다. 2번 기다리고 있는데 3번이 왔잖아. 3번 버리지 않고 저장하고 ACK 3번. Go back n이었으면, receiver는 3번 버리고 ACK 1번을 보냈습니다.
이 상황에서 sender는 처음에 ACK 0번 받았지. 그럼 윈도우 전진을 합니다. 이제 4번도 보낼 수 있지. 그 다음 ACK 1번 받으면 또 윈도우 전진을 합니다. 그래서 5번도 보낼 수 있습니다.
그리고 ACK 3번을 받습니다. 3번에 있는 타이머는 없어지게 됩니다. 2, 4, 5번 타이머는 그대로 있습니다. 이렇게 있다가 이제 더 이상 2번 ACK가 안 오고, 2번 타이머가 빵 터지게 됩니다. 그러면 2번만 재전송. 2번이 재전송되면, receiver 버퍼에 2번이 들어가고 이제 순서가 딱 맞게 됩니다. 그럼 이거를 애플리케이션 레이어에 올려주고 receiver는 ACK 2번을 보냅니다. sender는 ACK 2번 받으면 전진이 가능해집니다.
그래서 selective repeat을 보면, 유실된 패킷은 2번, 재전송된 패킷도 2번 입니다. 유실된 패킷만 재전송하게 됩니다. Go back n에서는 유실된 패킷 포함해서 윈도우에 있는 거 다 재전송인데, 여기는 receiver가 다 온 패킷 버퍼링 해주고, ACK를 다 따로 주기 때문에 누가 유실됐는지 확실하게 판단해줍니다. 얘는 0, 1, 2, 3, 4, 5, 2, 6, 7, 8 이런 식으로 전송이 됩니다. 유실된 패킷만 전송하기 때문에 네트워크에 부담이 덜 되는데 그 대신 receiver가 좀 일을 해야합니다.
7. Selective repeat: dilemma
