[Lecture 6] RDT : Pipelined Protocols

신뢰적인 데이터 전송 (이어짐)

이전 강의에서는 송신자와 수신자 간 하나의 세그먼트만 주고 받는 상황에서의 신뢰적인 데이터 전달을 논의했었다. 하지만 실제 전송계층에서는 전송-후-대기 프로토콜을 사용하지 않고 파이프라인된 프로토콜을 사용한다. 데이터를 한꺼번에 많이 보내고, 보낸 것들에 대한 응답 또한 한꺼번에 받는 방식이다. 파이프라이닝을 이용해 세그먼트를 전달하면 송신자의 이용률이 증가하여 성능향상에 도움이 된다.

파이프라이닝을 사용해 한꺼번에 전송한다

성능이 향상된다는 것을 증명할 수 있다

 

파이프라이닝 방식을 사용하면 다음과 같은 사항들이 요구된다. 

* 순서번호의 범위가 커져야 한다. 각각의 전송중인 패킷은 유일한 순서번호를 가져야 하고, 거기에 전송 중이고 확인응답이 안된 여러 패킷이 있을지도 모른다. 

* 프로토콜의 송신측과 수신측은 한 패킷 이상을 버퍼링 해야한다. 송신자는 전송되었으나 확인응답되지 않은 패킷을 버퍼링해야한다. 수신자는 정확하게 수신된 패킷들을 버퍼링한다. 

 

파이프라인 오류 회복의 두 가지 접근방법으로 N부터반복(GBN, Go-Back-N) 과 선택적 반복(SR, Selective Repeat)이 있다. 

 

N부터 반복

수업시간에 다룬 방식이다

이 프로토콜에서 송신자 관점의 순서번호 범위는 위의 그림과 같다. 확인 응답이 안된 가장 오래된 패킷의 순서번호를 base 로 정의하고, 사용되지 않은 (전송될 다음 패킷의) 가장 작은 순서번호를 nextseqnum 으로 정의한다. 윈도우 사이즈는 송신자가 한 번에 보낼 수 있는 패킷의 범위를 정의한다. 확인응답이 오지 않은 패킷을 몇 개 까지 허용할 것인가에 대한 범위이다. 

위의  그림에서 알 수 있듯이 순서번호의 범위를 4개의 섹션으로 구분할 수 있다. 0 ~ base-1 까지는 이미 전송되고, 확인 응답이 온 패킷들이다. base ~ nextseqnum-1 까지는 전송되었으나 아직 확인응답이 오지 않은 패킷이다. nextseqnum ~ base + N -1 은 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷을 위하여 사용될 수 있다. 마지막으로 base + N 이상의 순서번호는 파이프라인에서 확인응답이 아직 오지 않은 패킷들에 대한 응답이 도착하지 않는 이상 사용될 수 없다. 즉, 전송후 확인응답을 확인하고 윈도우 슬라이딩을 하는 방식으로 사용 가능한 순서번호들을 지정하는 것이다. GBN을 다른 이름으로 Sliding-Window Protocol 이라 부르기도 한다. 

 

윈도우사이즈를 N으로 제한하는 이유? 

송신자 측에서 혼잡제어를 할 때 필요하다. 송신자는 수신자가 받아들일 수 있는 만큼의 데이터를 전달해야 하는데, 이를 지키지 않으면 수신자측 버퍼가 꽉 차서 데이터가 제대로 전달되지 않을 수 있다. 

 

위로부터 send 가 호출되면, 송신자는 첫째로 윈도우가 가득 찼는지, 즉 N개의 확인응답되지 않은 패킷이 있는지 확인한다. 만약 윈도우가 가득 차 있지 않다면 패킷이 생성되고 송신된다. 

만약 윈도우가 가득 파있다면 이를 상위 계층에 알려주기 위해 특정 신호를 보낸다. 실제적인 구현에서 송신자는 이 데이터를 버퍼링하거나, 오직 윈도우가 가득하지 않을 때만 send 를 호출하는 동기화 메커니즘(ex. 세마포어 혹은 플래그)를 사용할 것이다. 

 

누적확인응답 (Cumulative Acknowledgement)

GBN에서 순서번호 n을 가진 패킷에 대한 확인응답은 누적확인응답으로 인식된다. 수신측에서 패킷을 올바로 전달받으면 그 다음에 받아야 하는 순서번호와 함께 ACK를 보낸다. 예를들어 순서번호 100까지의 데이터를 받았으면 ACK 100 을 응답으로 보낸다. 

 

타임아웃 이벤트

데이터 손실이 일어나면 수신자는 그 다음에 받는 데이터들을 버리고, 송신자측에 반복적으로 ACK + 직전의 순서번호를 전달한다. 송신자 측에서는 중복되는 ACK들을 무시하고 타임아웃이 발생하기 전까지는 계속해서 다음 패킷들을 송신하다가, 타임아웃이 발생하면 손실된 패킷의 순서부터 차례대로 다시 보낸다. 수신자 측에서 데이터의 순서를 보장해주고, 송신자 측에서는 재전송을 보장해주는 식이다. 

 

 

선택적 재전송 (SR) 프로토콜

 

GBN 프로토콜은 파이프라이닝 방식을 이용함으로써 전송-후-대기 프로토콜에서의 채널 이용률 문제를 극복한다. 하지만 하나의 패킷 오류로 인해서 많은 패킷들을 불필요하게 전송해야 하는 문제가 있다. 채널 오류의 확률이 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워진다. 

 

선택적 반복은 수신자에서 오류가 발생한 패킷을 수신했다고 의심되는 패킷만을 송신자가 다시 전송하므로 불필요한 재전송을 피한다. 필요에 따라서 개별적인 재전송은 수신자가 올바르게 수신한 패킷에 대한 개별적인 확인응답을 요구할 것이다. 윈도우 크기 N은 파이프라인에서 아직 확인응답이 안 된 패킷 수를 제한하는 데 사용된다(확인응답이 안 된 것이 너무 많으면 그 중에서 재전송 해야 하는 데이터가 수신측에서 재전송인지 구분을 못 할 수 도 있으므로). GBN과는 달리 송신자는 윈도우에서 몇몇 패킷에 대한 ACK를 미리 수신할 수 있다. 

 

SR수신자는 패킷의 순서와는 무관하게 손상 없이 수신된 패킷에 대한 확인응답을 보낸다. 순서가 틀린 패킷은 분실된 패킷이 수신될 때까지 버퍼에 저장하고, 손실된 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위계층에 전달한다 (순서 채워지기를 기다렸다가, 송신측에서 ACK를 받지 못해 Timeout 이 온 패킷에 대한 재전송들이 다 이루어 졌을 때 전달). 

 

Selective Repeat

 위의 예시를 순서대로 설명하면 다음과 같다. 

 

1. 송신측 윈도우 사이즈는 4이므로 0 1 2 3 을 순서대로 수신측에 전달한다. 처음엔 0을 전달한다.  

2. 수신측에서는 0을 받으면 recv_base 를 1로 옮기고 1을 기송다린다. 수신측 윈도우 [1, 2, 3, 4]

3. 송신측에서 1을 전달한다. 

4. 수신측에서 1을 받는다. recv_base 를 2로 옮기고 2를 기다린다. 수신측 윈도우 [2, 3, 4, 5]

5. 송신측에서 2를 전달한다. 

6. 수신측에서는 2를 받지 못했다. (Loss 발생) recv_base 를 3으로 옮기지 않고 그대로 유지한다. 수신측 윈도우 [2, 3, 4, 5]

7. 송신측에서는 3을 전달한다. 

8. 수신측에서는 2를 받지 못했으므로 순서 유지가 필요하다. 따라서 3을 버퍼에 저장해둔다. 윈도우의 크기는 여전히 그대로이다. 수신측 윈도우 [2, 3, 4, 5]

9. 송신측에서 0번에 대한 ACK를 받았으므로, send_base 를 한 칸 옮겨서 3 다음의 4를 전달한다. 

10. 수신측에서는 여전히 2를 받지 못했으므로 4를 버퍼에 저장한다. 윈도우 크기는 그대로이다. 수신측 윈도우 [2, 3, 4, 5]

11. 송신측에서 1번에 대한 ACK를 받았으므로 send_base 를 한 칸 옮겨서 5를 전달한다. 

12. 수신측에서는 여전히 2를 받지 못했으므로 5를 버퍼에 저장한다. 수신측 윈도우 [2, 3, 4, 5]

13. 송신측에서 2번에 대한 ACK를 받지 못하고 Timeout 이 발생한다. 2를 재전송한다. 그 이전에 3번에 대한 ACK는 도착하였다.  

14. 수신측에서 2를 받아 순서를 끼워 맞추었으므로 2, 3, 4, 5 를 상위 계층에 전달한다. 받은 2에 대한 ACK도 송신측에 전송한다. recv_base 는 [6, 7, 8, 9] 로 옮긴다. 

15. 송신측에서 수신측이 좀 전에 보낸 ACK4 와 ACK5를 받는다. send_base 를 [6, 7, 8, 9] 로 옮긴다. 

 

Selective Repeat Dilemma

선택적 전송에서의 어려운 점은 수신측이 송신측에 대한 행동을 전혀 엿볼 수 없다는 사실에서 발생한다. 위 그림의 커튼이 서로 볼 수 없는 상황을 표현하고 있다. 

(a) 시나리오의 경우, 송신측에서 0, 1, 2 를 올바르게 전달했으므로 수신측은 3, 0, 1을 기다리는 상태가 된다. 송신측에서는 ACK0 를 받고 윈도우를 [1, 2, 3]으로 옮긴 후 3을 전달하였으나 loss 가 발생하였다. (어쨌건) 송신측에서는 또 1에 대한 ACK를 받았으므로 [1, 2, 3] 에서 [2, 3, 0] 으로 윈도우를 슬라이딩 한다. 이 때 수신측에서는 0이 전달이 되더라도 이 0이 가장 처음의 0이 아니라는 것을 인지할 수 있다. 처음 보낸 0에 대한 ACK를 수신측에 이미 보냈고, 이것을 송신측이 올바르게 수신했기 때문이다. 

하지만 (b) 시나리오는 약간의 문제가 있다. 만약 ACK가 손실이 된다면 어떻게 될까? (b)의 과정을 순서대로 살펴보자. 송신측은 [0, 1, 2]를 윈도우로 잡고 0, 1, 2 를 순차적으로 전달했다. 그러나 수신측에서 잘 받았다는 ACK메시지가 중간에 유실된다. 수신측은 이 사실을 전혀 인지하지 못하므로 이미 윈도우를 [3, 0, 1]로 옮긴 상태이다. 즉, 3, 0, 1을 기다리고 있는 상황인 것이다. 문제는 송신측의 send_base가 (ACK가 전혀 오지 않았으므로) 처음과 같은 [0, 1, 2] 상태라는 것에서 발생한다. 이 때 송신측에서 0을 전달하면 수신측에서는 "어, 내가 기다리던 0이네?"하며 순서가 틀린 처음의 0을 받아버릴 것이다. 

커튼으로 인해서 처음의 패킷과 다섯번째 패킷을 구분 할 방법이 없는 것이다. 만약 윈도우의 크기가 더 크다면 이와 같은 오류는 더 치명적일 것이라 예상할 수 있다. 

교과서에서는 이런 상황을 설명하고, '윈도우 크기는 SR프로토콜에 대한 순서번호 공간 크기의 절반보다 작거나 같아야 한다' 라고 말한다.