[Computer Network] 3.4장(2) Pipelined Reliable Data Transfer Protocol

rdt3.0으로 network 상에서의 Corruption(오류)와 Loss(손실)에 대한 문제점들을 해결한 것을 이전 장에서 살펴봤다. 네트워크 상에서 아직 해결 못한 부분들도 많겠지만, 일단 Transport Layer에서 가장 중요한 문제인 오류와 손실에 관한 문제를 해결했다. 하지만 성능은?

이번 장에서는 이전 장에서 최종적으로 마무리 했었던 rdt3.0 방법의 성능상 한계를 설명하고, 새로운 pipelined 프로토콜을 살펴보도록 해보자.

Pipelined Reliable Data Transfer Protocol

Pipelined - Performance of rdt3.0

rdt3.0의 성능을 파악하기 위해 네트워크 상황을 가정해보면

조건

• 1Gbps 대역폭의 링크
• 15ms의 전파지연(propagation delay : link를 타고 전달되는 시간)
• 30ms의 RTT(Round Trip Time) (단순히 전파지연의 두배로 상정한다. 즉 receiver 측에서 처리 후 ACK 패킷을 만들어 보내는 시간은 무시한다)
• 8000 bit의 패킷 사이즈

전파지연과 전송지연이란? 전파지연(propagation delay)은 하나의 링크를 타고 도착하기까지의 시간을 말한다. 즉 물리적으로 하나의 지점에서 다른 지점으로 이동하는데 걸리는 시간(delay)이라고 할 수 있다. 전송지연(transmission delay)과 전파지연이 동일하다고 생각할 수 있겠지만, 전송에 얽매이지 않는 것이 편하다. 전송지연이란 하나의 중간노드(라우터 등)에서 패킷을 가고자 하는 링크로 내보내는데에 걸리는 시간을 말한다.

TODO: 원서 1장 전파지연 전송지연 정리글 링크 걸어두기

성능 계산

현재 계산하려고 하는 것은 우리가 봤었던 rdt3.0의 성능이다. 이 성능이라는 것을 여기선 Utilization(이용률)으로 살펴보려고 한다. 여기서 이용률이라는 것은 sender의 관점에서 "작업을 수행하는 시간의 비율"로 살펴보고 있다. 식을 보며 이해해보자.
 

1) 먼저 전송지연(transmission delay)부터 계산해보자. 전송지연 시간은 데이터의 사이즈를 링크의 대역폭으로 나눈 것을 말한다. 데이터의 사이즈를 L, 링크의 대역폭을 R이라고 했을 때, 전송지연 시간은 L / R로 나타낼 수 있다. 주어진 값을 대입해보면,
 

• 링크의 대역폭 : \(1Gbps\) = \(10^9bps\) (bps : bits per second)
• 데이터 사이즈 : 8000bits

이에 따라 sender의 전송지연 시간은 다음과 같이 계산된다.
$$
d_{trans} = \frac{L}{R} = \frac{8000}{10^9} = 8[usec]
$$  
2) 두번째로는 다음 sender가 패킷을 보내기까지의 시간이다. 이 시간은 RTT + 전송지연 시간으로 계산할 수 있다.
 

• RTT : 30ms
• 전송지연시간 : 8usec

$$
RTT + d_{trans} = 30ms + 8usec = 30.008ms
$$  

이 두개의 결과를 이용하면 sender의 이용률을 구할 수 있다.
$$
U_{sender} = \frac{d_{trans}}{RTT + d_{trans}} = \frac{0.008[ms]}{30.008[ms]} = 0.00027 = 0.027\%
$$  

위 식을 통해 sender의 이용률을 구하는 방법을 알 수 있었다. 그렇다면 위에서 이해가 가지 않았던 이용률이란 무엇을 뜻하는 걸까? 식을 보고 유추해볼 수 있는 바는 sender가 하나의 패킷을 보내는데에 참여한 시간을 말한다. 즉, 나머지 99.973% 시간동안 놀고 있었다는 것을 뜻한다.
 
그럼 throughput(처리율) 관점에서 보면 어떨까? 처리율은 단위시간당 처리할 수 있는 데이터의 크기를 뜻하며, 단위는 똑같이 [bps]를 사용한다. 처리율은 다음과 같이 구할 수 있다.
 

• 단위 시간 : s
• 데이터 크기 : 8000bits
• 처리 시간 : 30.008ms

$$
T = \frac{size}{time} = \frac{8000[bits]}{30.008[ms]} = \frac{\frac{8000}{30.008} \times 1000[bits]}{1[s]} = 267[kbits/s]
$$

결론

1Gbps라는 매우 큰 대역폭을 가지고 있음에도 불구하고, 1초에 267kbits의 데이터만 보낼 수 있다. 즉, 대역폭의 심각한 낭비를 초래하고 있다. 그렇다면 이 문제는 rdt3.0의 방식 중 무엇이 근본적인 문제였을까? 바로 하나의 패킷을 보내고 기다리고 다음 패킷을 보내는 매커니즘인 stop-and-wait 프로토콜이 근본적인 문제이다. 이에 기다리지 않고 연달아서 보내는 pipelined reliable data trasnfer 프로토콜이 등장하게 되었다.

Pipelined - 변화점

sender 의 이용률

만약 1개의 패킷이 아닌, 3개의 패킷을 보내고 기다리는 방식을 사용한다면?

기존 stop and wait 프로토콜 : 0.027%
3개의 패킷을 연달아 보내는 pipelined 프로토콜 : 0.081%

즉, 기다리지 않고 더 보낸 만큼 이용률이 상승한다는 것이다. 하지만 기존 rdt3.0까지의 매커니즘으로는 연달아서 보내는 방식을 수용할 수 없다. 그 원인은 rdt3.0까지의 시퀀스 넘버와 ACK 번호를 예로 들 수 있다.

rdt3.0의 시퀀스 넘버와 ACK

1. 시퀀스 넘버는 0과 1 둘 중의 하나로, 이는 우리가 stop-and-wait 프로토콜임을 가정하고 설계한 것이다.
2. ACK 번호도 시퀀스 넘버와 마찬가지로 stop-and-wait 프로토콜을 가정하고 0과 1 두개의 번호로 구현하였다.

이러한 매커니즘을 구현하기 위해 rdt3.0에서 몇가지를 변경해야 한다.
 

1. 시퀀스 넘버의 범위 : 여러개의 패킷들이 동시에 네트워크 상에 존재하게 되므로, 이들을 구별하기 위해 시퀀스 넘버가 여러개 필요해진다.
2. ACK 번호의 범위 : 위 시퀀스 넘버에 대한 ACK를 보내기 위해 여러개가 필요해진다.

구현

window(윈도우) : 한꺼번에 보내는 패킷들의 집합 또는 데이터의 집합을 윈도우라고 한다.

 
sender는 윈도우 크기에 해당하는 데이터를 보내고, receiver는 윈도우 크기에 해당하는 데이터를 기다리며 ACK를 보내는 방식으로 수행된다. 여기서 구현 방식은 크게 두가지로 나뉜다.

1. receiver측에서 버퍼를 두고 윈도우 크기의 패킷들을 저장해둔 후 오류 또는 손실(loss)이 발생한 패킷들만 다시 재전송을 요청할 것
2. receiver측에서 버퍼를 두지 않고 오류나 손실이 발생할 경우 윈도우 크기 전체에 대한 패킷들에 대해 재전송을 요청할 것.

각각의 장단점이 존재하는데, 특징과 함께 아래에서 보다 자세히 살펴보자.

Pipelined - GBN(Go-Back-N) Protocol

GBN ➡ checksum && ACK && sequence number && one timer && window && pipelining && cumulative ACK

 

그림 설명

• [0 ~ base-1] : 이미 패킷을 송신하고 ACK까지 정상적으로 받은 패킷들이다.
• [base ~ base + N-1] : 현재 한꺼번에 보낼 수 있는 패킷들이다. (슬라이딩 윈도우에 해당하는 패킷들이다. 슬라이딩 윈도우에 대해선 아래에서 살펴볼 것이다)
• [base ~ nextseqnum-1] : 이미 송신되었지만 아직 ACK는 받지 못한 패킷들이다.
• [nextseqnum ~ N-1] : 상위계층에서 데이터가 오는대로 바로 송신할 수 있는 패킷들이다.

위 그림에서 색상별로 구분되어져 있다.

GBN 특징1 : 슬라이딩 윈도우 (Sliding Window)

pipelined 프로토콜의 특징이 한번에 다수의 패킷을 보낼 수 있는 것이라고 했다. 여기서 한번에 보낼 수 있는 개수 N을 정해야 한다. 이 N을 sliding window(슬라이딩 윈도우)라고도 한다. 만약 슬라이딩 윈도우가 4라면, 패킷들은 0, 1, 2, 3, 0, 1, 2, 3, 0, 1,…과 같이 시퀀스 넘버가 설정된다. 이에 따라 GBN을 sliding window 프로토콜이라고도 한다.

GBN 특징2 : 하나의 타이머

타이머는 슬라이딩 윈도우에서 전송되었지만 아직 ACK를 받지 못한 가장 오래된 패킷에 설정된다. 그림에서는 base에 타이머가 설정될 것이다.

GBN 특징3 : Cummulative ACK

GBN 프로토콜은 Cummulative ACK방식으로 처리한다(이것은 딱히 한국어로 부르는 말이 없는 것 같으니 계속 영어로 쓰려고 한다). receiver측에서 보낸ACK k를 sender가 받았을 경우, 0 ~ k까지의 패킷들은 전부 잘 도착했다고 이해하는 매커니즘이다. GBN 프로토콜의 receiver는 순서대로 오는 패킷들에 대해서만 받고 나머지는 버리는 방식으로 동작한다. 또한 동시에 순서대로 상위 계층에 올려보내기 때문에 ACK 5번을 보냈다는 의미는 패킷이 0~5번까지 전부 정상적으로 왔다는 뜻이 된다. 이러한 receiver측의 동작으로 인해 Cummulative ACK가 정상적으로 동작하게 된다.

GBN 동작

sender 동작

1. 전송 : 슬라이딩 윈도우 크기만큼 패킷들을 차례대로 전송해준다.
2. 슬라이딩 윈도우 관리 : 슬라이딩 윈도우의 맨 첫번째 패킷이 ACK를 받을 때마다 슬라이딩 윈도우를 한칸 옆으로 미뤄준다. 이에 따라 슬라이딩 윈도우에 새로 포함된 패킷을 바로 전송시켜준다. 즉, 슬라이딩 윈도우에서 ACK된 것들은 전부 슬라이딩 윈도우에서 제외된다.
3. 손실(loss) 처리 : timeout이 발생하면 ACK를 받지 못한 패킷들 중 가장 오래된 패킷부터 슬라이딩 윈도우 전부를 다시 재전송한다. 어차피 슬라이딩 윈도우에는 아직 ACK되지 않은 것들만 있도록 관리되기 때문에 슬라이딩 윈도우 전체를 다시 재전송하는 것과 동일하다. GBN 자체는 이런 방식으로 loss에 대해 처리를 수행한다.
4. Cumulative ACK : ACK 3을 받지 못했지만 ACK 4를 받았다면 ACK 0부터 4까지 전부 정상적으로 전송된 것으로 이해한다. 이에 따라 ACK 3을 받지 못했다고 해서 3번 패킷을 다시 재전송하지 않는다.

receiver 동작

1. 정상 패킷 수신 : 오류가 없고 순서대로 온 패킷에 대해서만 수신한다. 수신한 패킷은 해당 시퀀스 넘버로 sender측으로 ACK를 보낸다. 이와 동시에 상위 계층으로 데이터를 전달해준다.
2. 비정상적인 패킷 수신 : 기다리고 있는 패킷이 아니거나 패킷의 오류가 있을 경우엔 그냥 단순히 버린다. 그리고 정상적으로 받은 패킷 중 가장 최근 시퀀스 넘버를 ACK로 보낸다.

sender가 유지해야 할 정보들

• 슬라이딩 윈도우의 base(시작)와 끝을 유지해야 한다. (그림 참고)
• 또한, 슬라이딩 윈도우에 포함되면서 아직 보내지지 않은 시퀀스 넘버(=nextseqnum)의 위치 또한 유지해야 한다.

receiver가 유지해야 할 정보들

• 다음 순서의 패킷의 시퀀스 넘버(=expectedseqnum)만 유지해주면 된다.

Pipelined - SR(Selective Repeat) Protocol

SR protocol ➡ checksum && ACK && sequence number && individual timer && window && pipelining && individual ACK && buffer

 

그림 설명

• GBN 프로토콜처럼 Cummulative ACK 방식을 사용하지 않아 ACK를 수신한 시퀀스 넘버와 아닌 시퀀스 넘버가 섞여 있다.
• GBN 프로토콜은 버퍼를 유지하지 않는 반면, SR프로토콜에선 Receiver측에서 버퍼를 유지해주고 있다. 위에서 rcv_base를 통해 윈도우의 첫 시작을 유지해주고 있다.

SR 특징1 : 수신자 측에서의 버퍼

GBN 프로토콜과는 다르게 수신자 측에서 버퍼를 유지해준다. 이 버퍼를 통해 out-of-order, 즉 순서가 뒤바껴 오는 패킷들도 잘 저장해줄 수 있다. 만약 rcv_base에 해당하는 패킷이 도착했다면 rcv_base부터 연속적으로 버퍼링된 패킷들 전부를 상위 계층으로 전달한다. 이후 수신자 측의 윈도우는 전달된 패킷 수만큼 오른쪽으로 민다. 이에 따라 다음 새로운 패킷들을 기다릴 수 있게 된다.

SR 특징2 : re-ACK

위 버퍼링에 따라 ACK를 보내는 방식도 달라진다. 송신자 측에서 ACK를 받지 못했거나 뒤늦게 받았을 경우(=premature timeout) 송신자는 재전송을 수행하게 되는데, 이 재전송하는 패킷이 수신자 측에서는 이미 받았던 패킷일 수도 있다. 수신자 측에서는 윈도우에서 제외된, 이미 받은 패킷을 또 수신했다고 해도 이에 대한 ACK를 반드시 재전송해줘야 한다.

SR 특징3 : Own Timer

송신자 측에서는 각 패킷에 대해 타이머를 각각 유지해준다. 수신자 측에서는 패킷을 받은 것에 한해 ACK를 보내주기 때문에 수신자가 잘 수신했는지를 알 방법은 ACK가 왔는지 안왔는지로 알 수 있다. 만약 ACK가 오지 않아 timeout이 발생했다면 해당 패킷은 전달이 잘 되지 않거나 오류가 발생한 것이 된다. 혹은 premature timeout으로 재전송을 수행하는 것일 수도 있지만, 이 경우에도 위 SR 특징2로 인해 중복 패킷을 처리할 수 있는 매커니즘이 있어 괜찮다.

SR 동작

sender 동작

1. 전송 : 상위 계층(application-layer)으로부터 패킷을 받는다.
2. 타이머 : 각 패킷 별로 timeout이 관리된다. ➡ 각 패킷 별로 타이머의 start, reset, stop이 수행된다. 위 SR 특징3으로 알 수 있듯이 이 타이머의 timeout으로 패킷의 오류와 손실 전부를 확인할 수 있다. 오류나 손실이 났다면 수신자 측에서는 ACK를 보내지 않기 때문에 timeout이 발생하기 때문이다.
3. 슬라이딩 윈도우 관리 : ACK 패킷을 받았을 때 이 ACK의 번호가 send_base번호와 동일하다면 슬라이딩 윈도우를 오른쪽으로 한칸 옮긴다. 슬라이딩 윈도우를 옮긴 후 새로 슬라이딩 윈도우에 포함된 패킷을 전송한다.

receiver 동작

1. 윈도우 범위에 있는 패킷을 수신 : [rcv_base ~ rcv_base + N - 1] 범위에 있는 패킷을 받았을 경우 수신자 측 윈도우에 이 패킷들을 저장한다. 저장한 패킷 번호로 ACK를 보내서 정상적으로 수신했다는 것을 알린다. 만약 rcv_base번호와 동일한 패킷을 수신했다면 이 패킷으로부터 연속적으로 저장되어 있는 패킷들을 한꺼번애 상위계층으로 전달한다.
2. 윈도우 범위 이전의 패킷을 수신 : [rcv_base-N ~ rcv_base-1] 범위에 있는 패킷을 수신했을 경우 수신자는 ACK를 다시 보내준다. 수신자 측은 잘 받았었다고 할지라도 송신자 측에서는 이를 모르고 있다는 뜻이므로 ACK를 꼭 다시 보내준다.
3. 이 외의 경우 : 받은 패킷들을 무시한다.

Pipelined - SR Dilemma

 
이 SR 딜레마라는 것은 송신자와 수신자가 각각 유지하고 있는 윈도우가 달라서 생긴 문제이다. 위의 그림을 보며 이해해보자.

Dilemma

1. receiver 측에서 rcv_base에 해당하는 패킷을 수신하면, 연이어서 버퍼에 저장된 패킷들을 전부 상위계층으로 전달하고, 이렇게 상위계층에 올려보낸 만큼 receiver의 윈도우를 옆으로 밀게 된다.
2. 하지만 위 그림에서 가정하듯이 sender는 아직 send_base에 해당하는 패킷에 대한 ACK를 받지 못했다고 해보자. 이에 따라 ACK를 받지 못해 timeout이 발생하고 이 패킷을 재전송한다. 위 그림 (a)에선 0번 패킷을 재전송하고 있다. 이에 따라 receiver가 SR 프로토콜의 receiver 동작에서 언급했던 두번째 방식으로 동작하기를 기대한다.
3. 하지만 sender가 재전송한 패킷의 시퀀스 넘버가 receiver가 기다리는 윈도우 내의 번호 중 하나와 같다면, receiver는 이를 재전송한 패킷이라고 생각하지 않고 새롭게 버퍼에 저장할 것이다. (그림 3.27-(a)번이 그러하다). 즉 두번째 경우로 동작하기를 바랬던 것이 첫번째 경우로 동작하게 된 것이다.

이렇게 SR 매커니즘에서 오류가 날 수 있는데, 이 때문에 시퀀스 넘버와 윈도우 크기(N)간의 관계를 다시 생각해봐야 한다.

시퀀스 넘버와 윈도우 크기의 관계

위에서 봤듯이, 서로 다른 window를 가지고 있어서 나타나는 딜레마를 봤다. 이제는 시퀀스 넘버와 윈도우 크기(N)간의 관계를 다시 정의해서 위와 같은 딜레마를 없도록 할 것이다.

Problem

위 딜레마는 송신자의 윈도우에 있는 시퀀스 넘버와 수신자의 윈도우에 있는 시퀀스 넘버가 하나라도 겹치게 되면서 발생하는 문제이다. 지금은 이해가 가지 않더라도 아래 해결 방법을 보면서 보면 이해가 충분히 갈거라 믿는다.

Solve

가장 최악의 경우는 send_base와 rcv_base가 N(윈도우 크기)만큼 차이나게 될 경우이다. 송신자 측의 윈도우 범위가 [0 ~ N-1]까지라면 수신자 측 윈도우의 범위는 [N ~ 2N-1]까지가 되는 경우이다. 즉 두 윈도우 사이에 겹치는 패킷들이 없는 경우이다. 이 경우 시퀀스 넘버를 어떻게 설정해주냐에 따라 위와 같은 딜레마가 생길수도 있고 안생길 수도 있게 된다. 여기서 윈도우 크기는 N으로 고정하고 시퀀스 넘버와의 관계를 알아보도록 하자.
 

우리의 목표는 서로 다른 윈도우를 가지는 송신자와 수신자가 있을 때, 송신 모든 경우에 대해 각 윈도우에 포함되는 시퀀스 넘버가 단 한개도 겹치지 않아야 하는 시퀀스 넘버와 윈도우 크기와의 관계를 찾는 것이다.

 

1) 만약 시퀀스 넘버가 0부터 N-1까지 가능하다면? 수신자측의 [N ~ 2N-1] 범위의 윈도우의 시퀀스 넘버들은 [0 ~ N-1]이 되고, 이 경우 송신자 측과 모든 번호들이 겹치게 된다. 즉, 수신자 측은 재전송되는 패킷들 전부 새로운 패킷으로 인식하게 될 것이다. 왜냐하면 이 경우는 위 SR 프로토콜의 receiver 동작 설명 중 첫번째 경우에 해당하기 때문이다. 이 경우를 간략히 다시 설명하자면, 현재 받은 패킷의 시퀀스 넘버가 수신자가 유지하고 있는 윈도우에 해당하는 번호인 경우이다.
 
2) 만약 시퀀스 넘버가 0부터 N까지 가능하다면? receiver의 윈도우는 [N, 0, 1, ..., N-2]와 같이 시퀀스 넘버를 가질 것이다. 송신자 측의 윈도우는 계속해서 [0 ~ N-1] 로 생각하고 있으므로 이 경우에선 0부터 N-2까지 총 N-1개가 겹치게 된다. 즉 시퀀스 넘버가 N-1인 패킷에 한해서만 재전송 패킷인지 새로 보낸 패킷인지를 구분할 수 있다는 것이다.
 
3) 만약 시퀀스 넘버가 0부터 N+k-1까지 가능하다면? receiver의 윈도우는 [N, N+1, …, N+k-1, 0, .., N-1-k]와 같이 시퀀스 넘버를 가질 것이다. 여기까지 봤으면 눈치를 챘을 수도 있다. 이 딜레마를 없애는 방법은 바로 receiver의 윈도우에 시퀀스 넘버 0을 없애면 되는 것이다. 이 0을 없앰으로써 최악의 경우 또한 서로의 윈도우가 가지는 시퀀스 넘버가 겹치는 일은 발생하지 않게 된다. 따라서 딜레마를 없애는 k는 N이 된다.
 
4) 만약 시퀀스 넘거자 0부터 2N-1까지 가능하다면? receiver의 윈도우는 [N, N+1, ..., 2N-1]와 같이 시퀀스 넘버를 가질 것이다. 현재 sender의 윈도우는 [0, 1, ..., N-1]이기 때문에 단 하나도 번호가 겹치지 않게 된다. 이에 따라 sender가 N이하의 시퀀스 넘버를 전송한다면 receiver는 이 패킷이 재전송된 패킷이라고 혼란 없이 이해할 수 있게 된다.

결론

위 딜레마를 해결하기 위해선 윈도우 크기가 N일 때, 시퀀스 번호는 0부터 2N-1까지 가능해야 한다.

요약

1. rdt3.0에서의 성능적 한계를 이용률과 처리율 관점에서 살펴봤다. 이를 통해 더 개선된 pipelined rdt를 살펴볼 동기를 얻게 되었다.
2. pipelined rdt의 구현 방식에 따라 GBN 프로토콜과 SR 프로토콜을 살펴봤다. 각각은 receiver 측에서 버퍼를 두느냐, cummulative ACK를 사용하느냐, 타이머는 각 시퀀스 번호마다 관리를 해주냐에 대한 차이가 있었다.
3. SR의 경우 시퀀스 넘버에 따른 오류가 생길 수 있음을 살펴봤다. 이 경우 시퀀스 번호와 윈도우 크기의 관계를 살펴보며 딜레마가 일어나지 않는 조건을 찾아보았다.

더 알아볼 점

출처

Computer Networking: a Top Down Approach 中 3.4.2 ~ 3.4.4