GBN & Selective repeat

Pipelining

이전 Posting에서 정리한 RDT는 여러가지 일을 할 수 있지만, "너무 느리다"라는 문제 상황에 도달합니다.
그 이유는 바로 "stop-and-wait" 방식을 수행하기 때문입니다.

packet을 전송하고, 이에 대한 ACK가 올 때까지 그저 기다리는 형태의 RDT는 네트워크의 성능 저하에 큰 원인이 됩니다.
따라서, 우리는 마치 pipe를 따라 흐르는 물처럼 막힘 없이 데이터를 보내고자 하는 방법을 고안해야 했습니다.

이 과정에서 위에서 언급한 바와 같이, 연속해서 데이터를 보내는 방식을 pipelining이라고 하고,
이로 인해 발생할 수 있는 추가적인 문제를 해결하기 위한 방법으로 2가지의 방식을 대표적으로 이해합니다.

pipelining의 문제

• 가장 큰 문제는 데이터가 중간에 drop 되었을 때, 어떤 것이 실패하였는지 정확하게 인식해야 한다는 것입니다.
• 또한, 연속으로 보내게 될 경우 중간의 데이터의 순서가 바뀌는 Out of Order 문제가 발생할 수 있습니다. => 해당 상황은 설명의 편의를 위해서 존재하지 않는다고 가정을 합니다. 하지만, 이 또한 중요한 문제이고, 이를 극복하는 내용은 packet 자체의 timer를 이용해서 스스로 drop 하는 방식을 사용하기도 한다고 합니다.

물론, 중간에 데이터가 손실된 경우에도 Out of Order 문제가 발생하지만, 두 번째에서 얘기하고자 하는 바는 receiver에게 도착하는 것의 순서 자체가 바뀌었다는 점입니다.

Go Back N(GBN)

단어에서 명시적으로 표현하듯 "문제가 발생한다면, N의 크기만큼 다시 전송해라."라고 이해하면 쉽습니다.

이러한 방식을 수행하기 위해서 도입한 것이 window라는 새로운 기술이다. window는 보낼 수 있거나, 이미 보냈거나 한 packet 중에서 아직 ACK가 오지 않은 packet의 범위를 지정합니다.

이미지에서 설명하는 바와 같이 sender에서는 window라는 개념을 이용해서 자신이 보낼 수 있는 데이터의 한계를 정해두고, 이 범위에서 오는 데이터만을 취급합니다. 만약, window에 있는 packet 중에 ACK가 정상 도착한 경우에는 window가 한 칸씩 전진하게 되며, 전송을 수행하게 됩니다. 그리고 만약, ACK가 정상적이지 못하거나, timer가 out 된다면, 해당 지점부터 다시 처음부터 보냅니다.

receiver에서는 간단히 데이터를 받아서 저장을 하며, 매번 packet을 받으며 squence numer를 확인하고, 기대했던 데이터가 올 때까지 기다렸다가 이를 받으면 저장합니다. 이렇게 저장을 수행할 때에는 무조건 순서에 맞는 sequence number만을 받을 수 있도록 되어있고, 원하는 sequence number가 오지 않으면 모두 버립니다.

이렇게 sender와 receiver 양 쪽에서 sequence number를 통해서 소통을 한다. k를 packet의 bit 수라고 한다면, 이 때, sequence number의 범위는 [0, 2^k]을 갖게 된다. 이에 대한 설명은 후에 posting에서 자세히 다룬다.

이 방식의 문제점은, 이미 받았더라도 안 받은 지점부터 다시 보내야 한다는 성능적인 문제를 들 수 있다.

Selective Repeat (SR)

위에서 언급한 것처럼, 성능적인 문제를 일으키는 GBN을 좀 더 보완하기 위해서 나온 것이 Selective Repeat입니다. 이는 잘못된 데이터만을 재전송하도록 하는 방식이고, 이를 위해서 기존에는 sender 쪽에만 존재하던 window를 receiver 쪽에도 도입합니다.

sender에서는 기존의 역할과 비슷하지만, timeout이 발생하면, window의 처음 부분만을 재전송합니다. 이를 통해서 전체의 재전송이 아닌, 에러가 있었던 부분만 재전송하는 것이 가능합니다.

또한, receiver 역시 동일하지만, 먼저 도착한 packet들도 저장할 수 있습니다.
여기서, 특이한 점은 window의 범위 뿐만 아니라, 그 이전의 window 크기 만큼의 값에 대해서도 ACK를 전송한다는 점입니다. 해당 경우를 생각해보면, 이미 receiver에서는 데이터를 받았지만, Sender에서는 이를 알지못하고 재전송을 한 경우인데 이 또한, selective repeat에서는 ACK를 보내 잘 받았음을 명시해줍니다.