Pipelined protocols

---

Performance of RDT 3.0

RDT 3.0이 정확하게 작동하는 것은 확인이 되었다. 그러나 그 성능은 비현실적으로 너무 안좋다. 그 원인은 'stop-and-wait' 알고리즘에 있다. 지금까지의 Transport 알고리즘은 전부 sender가 packet을 보내고 receiver에게 답이 올때까지 기다려야하고 receiver도 마찬가지이다. 이게 얼마나 비효율적인지 살펴보자. 예를들어 1Gbps link가 있고 15ms propagation delay가 디폴트로 있다고 할때 8000bit packet을 보내는 과정을 보면 transmission delay는 L/R 즉 8000/1,000,000,000=8microsecs이다.

이때 sender의 utilization 즉 망 이용율을 보면 0.008/(RTT+0.008) = 0.008/30.008 = 0.00027 즉 link의 능력치의 0.27%만 이용하는 것이다.

---

Piplelined protocols

따라서 일단 여러개를 보내놓고 판단하는 pipelining 기술을 적용한다. 이때 sequence를 counting하는 숫자가 늘어나야할 것이다. 또한 packet들을 세트로 전송했을때 그중에 문제가 생겼을때 해결할 수 있어야한다.

위와 같이 stop-and-wait 보다는 확실히 우리가 생각하는 현실적인 networking이 진행되는 것을 볼 수 있다.

이제 얼마나 효율적인지 한번 계산해보자.

packet을 세개씩 보냈더니 이용률이 3배 늘었다. 이런 방식으로 networking을 하면 좀더 효율적일 것으로 보인다.

Pipelined protocol로는 크게 두가지 "Go-back-N" 방식과 "Selective Repeat"방식이 있다.

---

Go-back-N

송신자는 최대 N개의 확인되지 않은 패킷을 파이프라인에 보관할 수 있다. 수신자는 각 패킷에 대한 누적 확인 응답(ACK)만 보낸다. 송신자는 가장 오래된 확인되지 않은 패킷에 대한 타이머를 가지고 있는다. 타이머가 만료되면 모든 확인되지 않은 패킷을 재전송한다.

N사이즈의 window를 이용하여 일정 단위로 체크를 하면서 넘어간다.

 

sender extended FSM

우선 초기상태는 base와 nextseqnum을 초기화해둔다. base는 수신자가 확인한 마지막 패킷의 시퀀스 번호를 나타내고, nextseqnum은 다음으로 전송할 패킷의 시퀀스 번호를 나타낸다. 다음으로 데이터 전송 단계에서 sender는 데이터를 전송할 때 nextseqnum이 base + N보다 작으면, 해당 시퀀스 번호의 패킷을 생성하고 전송한다. 이때 window의 첫번째 sequence에서 timer를 시작해준다. 만약 답이 오지 않고 timeout이 된다면 데이터를 다시 전송한다. 만약 제대로 답이 돌아온다면 base를 하나 올려서 window로 다음 데이터를 비춰주는 식의 protocol을 반복한다.

receiver extended FSM

만약 corrupt되지 않고 expectedseqnum이 들어오면 데이터를 추출해서 app layer로 올려주고 expectedseqnum의 크기를 키운다. 이외의 상황에서는 이전에 만들어둔 ACK를 전송하여 제대로 전송이 안되었다는 점을 알려준다.

GBN in action

문제가 발생하면 그 시점부터는 아무것도 받아들이지 않고 문제지점부터 다시 window를 설정하고 덩어리로 보내는 것을 볼 수 있다.

---

Selective repeat

이름에서 알 수 있듯 선택적으로 오류가 난 패킷에 대해서만 데이터를 다시 주고 받는 방식이다.

위 그림에서 보면 ACK를 받은 초록색들 사이에 ACK를 받지 못한 노란색이 존재한다. GBN 방식이라면 해당지점부터 정보를 습득하지 않고 재전송을 요청하여 재전송이 올때 정보를 습득하겠지만 위 그림에서 볼 수 있듯 ACK를 받은 packet에 대해서는 저장을 해두고 다음 재전송에서 굳이 추가로 받지 않는다.

sequence number를 무한하게 늘릴 수는 없어서 어느정도의 기준을 갖고 정하는데 kbit라고 했을때 sequence number는 2^k까지 가능하고 이때 GBN에서는 window의 크기를 sequence number보다 1작은 2^k-1로 설정할 수 있다. 0,1,2,3일때 0,1,2,3전송이 잘 완수되고 그 다음에 바로 0이 와서 문제가 생긴것으로 인식하지 않도록 하는 것인데 selective repeat에서는 문제가 존재한다. 아래에서 살펴보자.

b case를 보면 ACK가 3개 모두 sender에게 가는중에 corrupt되어서 sender는 timeout이 되어 0번 sequence packet을 다시 보내주는데 receiver는 012가 잘 전달이 되었는데 3을 건너뛰고 0이 왔네? 이렇게 생각하고 0을 저장해두고 3에 대한 packet만 재요청을 할 것이다. 따라서 window size를 최소 sequence number 수의 절반으로 유지해야해서 2^(k-1)이하가 되어야한다.

---