파이프라인된 신뢰적 데이터 전송 프로토콜

앞서 배운 rdt3.0은 기능적으로 정확한 프로토콜이다. 하지만 핵심적인 성능 문제는 전송-후-대기(stop-and-wait) 포로토콜이라는 점이다. 

 

아래의 그림처럼 하나의 호스트는 미국의 서부에 위치하고 다른 하나는 동부에 위치한 두 종단 호스트의 가상의 경우를 고려하자. 두 종단 시스템 사이의 광속 왕복 전파 지연(RTT)은 대략 30msec이다. 

전송-후-대기와 파이프라인된 프로토콜의 비교

이들이 1Gbps(초당 10⁹비트) 전송률(R)을 가진 채널에 의해 연결되어 있다고 가정하자. 

 t_trans = L/R = (8,000bits/packet) /(10⁹bits/sec) = 8μsec 

8μsec에서 마지막 비트가 송신 측의 채널로 들어가고 패킷은 15msec 동안 대륙을 횡단하고 t = RTT/2 + L/R = 15.008msec에서 수신 측으로 마지막 비트가 도착한다. 송신자 측에서 ACK 패킷은 t = RTT +L/R = 30.008msec 후에 다시 받을 수 있다. 

이를 통해 이용률(utilization)을 계산할 수 있다.

U_sender = L/R / RTT + L/R = 0.008 / 30.008 = 0.00027

즉, 송신자는 단지 시간의 0.00027만큼만 바빴던 것이다. 이러한 비효율성을 관리하기 위해  송신자에게 확인응답을 기다리기 전에 송신자가 3개의 패킷을 전송하도록 허용한다면, 송신자의 이용률은 3배가 된다. 많은 전송 중인 송신자-수신자 패킷을 파이프라인에 채워 넣음으로써 나타낼 수 있다. 이 기술을 파이프라이닝(pipelining)이라고 부른다.

전송-후-대기와 파이프라인된 전송

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

 

N부터 반복(Go-Back-N, GBN)

 

GBN 프로토콜에서 송신자는 확인응답을 기다리지 않고 여러 패킷을 전송할 수 있다. 그러나 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크지 않아야 한다. 

Go-Back-N에서 송신자 관점의 순서번호

base: 확인응답이 안 된 가장 오래된 패킷의 순서번호

nextseqeuencenumber: 사용되지 않은 가장 작은 순서번호

[0, base-1]: 이미 전송되고 확인응답이 된 패킷

[base, nextseqnum-1]: 송신은 되었지만 아직 확인응답이 되지 않은 패킷

[nextseqnum, base+N-1]: 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷

base+N 이상의 순서번호: 파이프라인에서 확인응답이 안 된 패킷의 확인응답이 도착하기 전까지 사용할 수 없다.

 

전송되었지만 아직 확인응답 안 된 패킷을 위해 허용할 수 있는 순서번호의 범위는 순서번호의 범위상에서 크기가 N인 '윈도우'로 나타낸다. 프로토콜이 동작할 떄, 이 윈도우는 순서번호 공간에서 오른쪽으로 이동(slide)된다. 이러한 이유 때문에 N을 윈도우 크기(window size)라 부르며, GBN 프로토콜은 슬라이딩 윈도우 프로토콜(sliding window protocol)이라고 부른다. 

Go-Back-N에서의 동작

4개의 패킷 윈도우 크기의 경우, 패킷 0부터 3까지 송신한다. 송신을 계속하기 전에 하나 이상의 패킷이 긍정 확인응답되는 것을 기다리고 각각의 성공적인 ACK가 수신되었을 때 윈도우는 앞으로 이동하고 송신자는 다음의 새로운 패킷을 전송한다. 위의 예시에서는 패킷2가 손실되었으므로 패킷 3, 4, 5는 순서가 잘못된 패킷으로 발견되어 제거된다. 

 

선택적 반복

 

GBN은 패킷 하나의 오류로 인해 많은 패킷을 불필요하게 재전송하는 경우가 발생한다. 채널의 오류가 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워지게된다. 이를 해결하게 위해 나온 방법이 선택적 반복(Selective Repeat, SR)이다. 

순서번호 공간에 대한 SR 송신자와 수신자 관점

수신자에서 오류가 발생한 패킷을 수신했다고 의심되는 패킷만을 송신자가 다시 전송하므로 불필요한 재전송을 피한다. GBN과 달리 송신자는 윈도우에서 몇몇 패킷에 대한 ACK를 이미 수신했을 것이다. 

SR 동작

송신자와 수신자 윈도우 사이의 동기화의 부족은 순서번호의 한정된 범위에 직면했을 때 중대한 결과를 가져온다. 예를 들어, 한정된 범위의 네 패킷 순서번호 0, 1, 2, 3과 윈도우 크기 3에서 어떤 일이 일어날 수 있는가를 생각해보자. 0부터 2까지 패킷이 전송되어 올바로 수신되고 수신자에게서 확인이 되었다고 가정하자. 

너무 큰 윈도우를 가진 SR 수신자의 고민: 새 패킷인가 아니면 재전송된 것인가?

그 순간에 수신자의 윈도우는 각각의 순서번호가 3, 0, 1인 4, 5, 6번째 패킷에 있다. 첫 번째 그림에서 처음 3개의 패킷에 대한 ACK가 손실되고 송신자는 이 패킷을 재전송한다. 두 번째 그림에서 처음 3개의 패킷에 대한 ACK가 모두 올바르게 전달이 되었다. 그러면 송신자는 자신의 윈도우를 앞으로 이동시켜 각각의 순서번호가 3, 0, 1인 4, 5, 6번째 패킷을 보낸다. 순서번호 3을 가진 패킷이 손실되고, 순서번호 0을 가진 패킷은 도착한다.

 수신자는 송신자의 행동을 볼 수 없으므로 수신자의 관점에서 상황을 보자. 다섯 번째 패킷의 원래 전송과 첫 번째 패킷의 재전송을 구별할 수 있는 방법은 없다. 두 상황을 똑같이 해석한다는 것이다. 따라서 윈도우 크기는 SR 프로토콜에 대한 순서번호 공간 크기의 절반보다 작거나 같아야한다.