[컴퓨터 네트워크] 19. Transport Layer (5) : Go-Back-N (GBN), Selective Repeat (SR)

Pipelined Protocol

rdt 3.0 프로토콜은 stop and wait 방식의 프로토콜이라 performance 가 매우 좋지 않았다.

이를 해결하기 위해 pipeline 기법을 이용하여 한번에 여러개 패킷을 전송하는 아이디어가 제시되었다.

이와 관련된 아이디어는 크게 Go-Back-N (GBN) 과 Selective Repeat (SR) 프로토콜이 있다.

이 프로토콜들은 pipelined protocol 로 분류한다.

먼저 Go-Back-N 프로토콜에 대해 정리하자.

 

Go-Back-N

sender

먼저 Go-Back-N 프로토콜을 사용하는 sender 입장을 살펴보자.

sender는 다수의 pipelined packet을 보내야 하기 때문에 '윈도우' 를 사용한다.

'윈도우'라는 이름은 슬라이딩 윈도우 기법을 사용하기 때문에 이런 이름을 사용한다.

 

윈도우는 ack를 받지 않은 상태에서 한번에 n개의 패킷을 보낼 수 있도록 만든 버퍼이다.

따라서 센더가 윈도우를 갖고 있는 것처럼, 리시버도 한번에 여러개의 패킷을 저장할 수 있는 윈도우를 갖고 있어야 한다.

그리고 n개의 패킷을 구분하기 위해 시퀀스 넘버도 k개가 필요하다. (k = log₂ n)

 

윈도우의 크기는 N으로 일정하고, 윈도우 내에는 전송했으나 ack를 받지 못한 패킷들이 들어있고(노란색),

남은 공간은 전송을 대기중인 패킷으로 채운다. 또는 보낼 데이터가 없는 경우엔 그냥 빈 공간이 될 수 있다.(파란색)

 

원래는 녹색과 노란색 범위의 윈도우를 갖고 있었고, 이 패킷을 한번에 send 했을 것이다.

그런데 녹색 6는 전송되었다는 ack를 받아서 윈도우를 6칸 오른쪽으로 옮기고, 노란색은 ack를 기다리고 파란색은 전송을 기다리는 상황이다.

만약 노란색에 대해서 timeout 이 발생하거나, 적절한 ack가 오지 않는다면 이들은 재전송될 것이다.

그리고 노란색에 대해 ack 신호가 온다면 (잘 전송되었다면 8개에 대해 ack가 올 것이다) 그 만큼 한번에 슬라이딩한다.

노란색 친 데이터 중 앞에 3개만 ack가 온다면 3칸을 슬라이딩할 것이다.

 

Go-Back-N 은 cumulative ACK를 사용한다.

말 그대로 누적 ACK라는 의미로, 위 예시에서 노란색 패킷을 왼쪽부터 1번 ~ 8번 이라고 했을 때, 각각에 대해서 ACK를 보내는게 아니라 누적 ACK 하나를 보낸다.

수신자 입장에서는 내가 '연속해서' 받은 패킷의 가장 큰 마지막 번호를 누적 ACK 하나로 보낸다.

만약 그 값이 N 이었다면 센더는 N이하의 값은 잘 받았다고 인지하고, 윈도우의 send_base는 n+1 위치로 바뀌도록 슬라이딩한다.

TCP 프로토콜도 이 방식을 따라서 누적ACK를 받고 있다.

 

또한 Go-Back-N 도 타이머를 유지한다.

이때 타이머는 내가 보낸지 가장 오래된 패킷을 기준으로 타이머를 설정한다.

극단적으로 가면 내가 보낸 모든 패킷 각가에 대해서 타이머를 둘 수도 있다.

하지만 이렇게 하면 굉장히 번거롭고 오버헤드가 크기 때문에, 타이머를 하나를 둔다.

 

만약 녹색과 노란색에 대해 데이터를 전송하고, 공통의 타이머를 두었을 때,

녹색을 받아서 슬라이딩했다면, 여전히 타이머의 기준시간은 노란색을 기준으로 두고 있고, 이 시간이 지나면 이때는 노란색과 파란색까지 모아서 한번에 전송할 것이다.

 

노란색의 번호가 N이고 파란색이 N+14 라고 할 때, N을 기준으로 타이머를 잡아서 N에 대해 타임아웃이 발생하면 N뿐만 아니라 버퍼에 들어있는 N ~ N+14에 대해 모두 다시 전송하기 때문에 Go-Back-N 이라는 이름을 가진다.

 

receiver

 

리시버는 데이터를 수신하고, 이에 대해 ACK를 보낸다.

이때 리시버도 똑같이 윈도우를 유지한다.

그리고 어플리케이션이 도착한 패킷의 데이터를 읽어가면, 그 패킷들에 대해 ACK를 보내고 그 만큼 윈도우를 슬라이딩한다. (만약 어플리케이션이 바빠서 데이터를 읽어가지 않으면 슬라이딩 하지 않는다. 따라서 버퍼에 계속해서 수신 데이터가 쌓일 수 있는데, 이때는 receiver가 sender에게 데이터를 잠깐 보내지 말도록 신호를 보낼 수 있다.

이를 flow control 이라고 한다.)

 

이때, 수신한 패킷의 번호들을 보고 리시버는 순서를 따지는데, 리시버도 윈도우 내에서 연속한 데이터들에 대해 한번에 ACK를 전송하므로, 순서에 맞게 들어온 패킷들 중 제일 큰 시퀀스 번호를 ACK로 보낸다.

순서에 맞지 않는 패킷 (위 그림에서 분홍색) 이 있다면 이 뒤에 있는 패킷에 대해서는 수신했더라도 ACK를 보내지 않는다.

 

receiver는 sender와 달리 rcv_base 만 기억했다가, 자신이 처리한 데이터 패킷 번호 + 1 위치로 rcv_base 만 옮기면 된다.

또한 구현에 따라 순서에 맞지 않게 들어온 패킷을 버퍼에 저장해둘 수도, 그냥 버릴 수도 있다.

 

Go-Back-N action

실제 sender와 receiver가 데이터를 주고 받는 과정을 살펴보자.

 

 

먼저 sender window는 N=4 로 설정되어 있다.

(참고로 전체 action 동작 방식만 보고도 윈도우 크기를 역으로 추론할 수도 있다.)

 

sender가 보낼 패킷은 0부터 8까지 9개가 존재하는 상황이다.

윈도우 크기가 4이므로 패킷 0~3 은 이미 윈도우에 들어있고, 이렇게 4개를 한번에 전송한다.

 

이때 pkt2가 전송 중간 유실되었다고 하자.

receiver 입장에서는 pkt0, 1 은 올바르게 수신했으니 ack0, ack1 을 보내고, rcv window를 2칸 옮긴다.

receiver window를 그리면 아래와 같다.

 

패킷 0, 1 은 수신했으므로, 그 번호에 맞는 ACK를 보내고, application 계층에 데이터를 전달한다.

2는 수신하지 않았으므로 별도 ACK를 보내지 않고

3에 대해서는 수신했으나, Go-Back-N 방식은 연속적으로 받은 가장 높은 패킷 번호를 ACK로 보내므로, ACK1을 보낸다.

 

따라서 슬라이딩 윈도우는 아래와 같이 변화한다.

 

---

 

ack0, ack1 이 sender에게 도착하면, sender는 슬라이딩 윈도우를 한칸씩 밀면서 pkt4, pkt5를 보낸다.

하지만 receiver는 아직 pkt2를 기다리고 있어서 4, 5패킷을 수신해도 ack1을 반환한다.

sender는 ack1 을 이미 수신했으므로, 무시한다.

 

이때 pkt2 가 ack0 패킷을 받지 못해서 timeout 이벤트가 발생했다고 하자.

 

그러면 sender는 (이미 pkt 3, 4, 5를 보냈음에도) pkt2 로 다시 돌아가서 (Go-Back-N) 2,3,4,5 패킷을 모두 다시 보낸다.

receiver는 4개 패킷에 대한 ack를 각각 번호별로 다시 보내줄 것이다.

 

---

Selective Repeat

Selective Repeat 은 Go - Back - N 과 달리 중간에 패킷이 유실되었을 때, 이후 잘 도착한 패킷을 버리지 않고 가지고 있다가 유실된 패킷만 선택해서 다시 전송하는 프로토콜이다.

(참고로 TCP에서는 Go-Back-N 과 Selective Repeat이 적절히 혼합되어서 사용된다.)

 

Select Repeat 방식도 Go-Back-N과 마찬가지로 Sender 와 Receiver 모두 버퍼(윈도우)를 갖고 있다.

Go-Back-N과 동일하게 윈도우는 앞에 있는 패킷을 보낼 때마다 슬라이딩된다.

 

Sender는 사진과 같은 윈도우를 갖는다. receiver 는 제대로 받은 패킷에 대해서 선택적으로 ACK를 보내기 때문에, sender도 버퍼에서 선택적으로 받은 ACK에 대해서 관리한다.

따라서 Go-Back-N 과 달리 버퍼 윈도우 중간에 녹색 패킷이 존재할 수 있다.

 

사진과 같이 send_base 부터 연속적으로 ACK 를 받지 못했다면 sender의 윈도우는 이동하지 않고, 타이머를 재면서 기다린다. 따라서 sender는 타이머를 전송한 모든 패킷에 대해 각각 갖고 있는다. 당연히 sender 입장에서는 부담이다.

위 사진에서는 노란색 패킷이 된다.

 

파란색 패킷은 2가지 의미를 갖는다.

첫번째는 어플리케이션에서 아직 메세지를 보내주지 않아서 생긴 빈 공간일 수 있고,

두번째는 상위 어플리케이션에서 데이터를 계속 보내주고 있어서 보낼 준비는 되었지만 아직 보내지 않은 상태일 수 있다.

 

 

receiver 윈도우도 Go-Back-N과 마찬가지로 rcv_base 가 존재한다.

리시버 윈도우의 크기는 sender 윈도우의 크기와 같다.

다만 그 싱크가 항상 일치하지는 않을 수 있다. (send_base와 rcv_base 가 일치하지 않을 수 있다.)

 

위 이미지에서 녹색은 이미 수신해서 ACK를 보내고 상위 어플리케이션에 데이터를 전달한 패킷이다.

리시버 입장에서는 녹색인데, 센더 입장에서는 노란색이라면, 리시버가 보낸 ACK가 센더에게 가고 있거나, 가다가 중간에 유실되었다는 뜻이다.

 

만약 유실되었거나 느리게 가서 timeout이 발생하면, 센더는 리시버에게 다시 패킷을 전송할 것이고, 리시버는 이미 ACK를 보냈으니 다시 ACK를 보낼 것이다.

 

회색 패킷은 아직 받지 않아서 데이터를 기다리고 있는 패킷이다.

빨간색 패킷은 일단 순서에는 맞지만 잘 도착한 패킷이다.

selective repeat 방식에서는 이 패킷도 버퍼에 저장하고, ACK를 보낸다.

하지만 온전히 데이터가 순서에 맞게 도착하지는 않았으므로 윈도우를 슬라이딩 하지 않고, 어플리케이션에 데이터를 올려보내지도 않는다.

 

파란색 패킷은 sender와 유사하게 윈도우의 빈 공간을 의미한다.

 

Sender

상위 어플리케이션에서 데이터를 전달받았을 때, sender window에 가용 공간이 있다면 그 데이터를 바로 패킷으로 만든 뒤 전송한다.

데이터를 전송한 뒤에는 각 패킷마다 따로 타이머를 두며, 만약 타이머에 설정된 시간이 지나면 해당하는 패킷 하나를 다시 보낸다. 따라서 timeout(n) 과 같이 타임아웃의 동작을 표시할 때, 패킷 번호도 같이 표시한다.

 

Sender가 n번 패킷에 대한 ACK(n) 를 받을 때 (n의 범위는 [ sendbase, sendbase + n -1 ] )

이 범위 내에 존재하는 패킷을 받으면 패킷 n에 대해 ACK를 수신했다고 마킹하고, 아직 ACK를 받지 못한 패킷 중에 제일 작은 n 을 갖는다면, 윈도우를 다음으로 ACK를 받지 못한 패킷으로 슬라이딩 한다.

 

Receiver

만약 수신한 패킷의 번호 n이 [ rcv_base, rcv_base + N - 1 ] 범위, 즉 현재 리시버 윈도우 범위 내에 존재한다면, ACK(n)을 전송한다.

이때 이 번호가 순서를 벗어난 번호라고 하더라도 버퍼에 저장하고, ACK(n)을 보내준다.

(Go-Back-N 에서는 순서에 벗어난 번호를 받으면 순서에 맞게 받은 가장 큰 패킷 번호를 보내주었었다.)

 

만약 순서에 맞는 번호를 받았다면 ACK(n)을 보내고, 데이터를 상위 어플리케이션에 보내준 뒤, 윈도우를 슬라이딩하면 된다.

 

그런데 Selective Repeat 에서는 센더와 리시버의 윈도우 싱크가 서로 맞지 않을 수 있기 때문에,

[ rcv_base - N, recv_base - 1 ]  범위에 있는 패킷을 수신할 수도 있다.

싱크가 맞지 않는 상황은 리시버가 ACK를 제대로 보냈는데, 센더가 ACK를 받지 못했을 때 (또는 늦게 받았을 때) 발생한다.

 

그림으로 보면 위와 같은 상황이다.

send_base 번호의 패킷이 아직 ACK를 수신대기하는 상태에서 리시버는 센더 윈도우에 있는 모든 패킷에 대해 ACK를 전송한 상황인 것이다.

이 상황에서는 이미 잘 처리한 패킷을 받은 것이므로 그냥 ACK(n)을 보내면 된다.

 

만약 그 이외 범위의 패킷을 수신한다면, 그때는 아무 행동도 하지 않고 무시한다.

 

Selective Repeat Action

 

그림과 같이 sender window에 4개 패킷이 들어있고, 4개 패킷을 한번에 전송한 뒤 기다리는 상황이라고 하자.

이때 만약 packet 2 를 전송하는 과정에서 loss 가 발생했다면 어떻게 될까?

 

receiver 입장에서는 수신한 패킷에 대해서는 모두 각각의 번호에 맞는 ACK를 보내줄 것이다.

(Go-Back-N 이었다면 pkt3 에 대해서는 ACK 1 을 전송했을 것이다!)

 

 

ACK 0, ACK1 이 sender에게 도착하면,sender의 윈도우가 각각 1칸씩 밀리면서 ACK4, ACK5를 전송한다.

 

 

ACK3 이 도착했을 때는 아직 pkt2 에 대한 ACK를 받지 않았으므로 윈도우는 그대로 두고, ACK3을 받았다는 것만 기록해둔다.

(Go-Back-N 이었다면 ACK1 이 왔을 것이므로 윈도우가 이동하지 않는다.)

 

이때 pkt2 에 걸어둔 타이머의 시간이 지나서 timeout 이 발생하면, pkt2 를 재전송한다.

단, Go-Back-N 과 달리 pkt3, pkt4, pkt5 는 재전송하지 않는다!!

 

pkt2 가 도착하면, receiver 윈도우에서 순서가 맞춰졌으므로, pkt2 ,3, 4, 5를 순서대로 모두 어플리케이션 계층에 전달하고, ACK2 를 보내면서 윈도우는 pkt6을 수신하도록 이동한다.

 

이후에 ACK2가 도착하면 sender 의 윈도우도 6을 send_base로 하도록 이동할 것이다. (ACK 4, ACK5 가 도착했다면)

 

---

Selective Repeat 방식의 Dilemma

 

아래와 같은 예시를 생각해보자.

 

window의 크기는 3 이고, 패킷 번호는 4를 기반으로 카운팅하여 0, 1, 2, 3  이렇게 4개 번호로 구분한다고 해보자.

(3 이후에는 다시 0부터 번호를 센다! 번호의 경우 최소한 윈도우 크기 만큼의 번호는 필요하다.)

 

 

sender가 보낸 pkt 0, pkt 1, pkt2 모두 잘 도착해서 ACK 0, ACK 1 을 보낸 상황이다.

receiver의 윈도우도 3칸이 이동해서 rcv_base 가 3이 되어있는 상황이다.

 

이때 pkt3 을 보내다가 중간에 loss가 발생했고, ACK1 에 의해 윈도우가 밀리면서 pkt 0 을 보낸다.

이때는 pkt 0 을 문제 없이 받을 수 있다.

 

 

그런데 위 이미지처럼 pkt0, pkt1, pkt2 모두 다 잘 받아서 윈도우를 3칸 밀었는데, ACK는 하나도 전송이 안되었다고 해보자.

 

이때 sender 입장에서는 ACK가 오지 않았으니 timeout 이 발생하여 다시 pkt0 을 보낼 것이다.

그런데 이 패킷은 사실 receiver 가 받으면 안된다.

 

지금은 window 에 0번 패킷에 대한 공간이 있으므로 수신할 수 있는데, 이 0번 패킷은 2번째 0번 패킷이고, sender 가 보내는 0번 패킷은 첫번째 0번 패킷이라 엄연히 서로 다른 패킷이기 때문이다.

하지만 receiver 입장에서는 내가 받은 0번 패킷이 첫번째 0번 패킷인지, 두번째 0번 패킷인지 구분하지 못한다. 

 

따라서 이런 문제를 방지하려면 sender window 와 receiver 윈도우가 극단적으로 차이가 나더라도 패킷 번호를 구분할 수 있도록 윈도우 크기의 2배 이상의 번호를 사용하면 된다.