Computer Network[05] - principle of reliable data transfer(2)

Chapter 3.4 principles of reliable data transfer

Computer Networking : A Top Down Approach 7th Edition, Global Edition Jim Kurose, Keith Ross

---

Pipelined protocols

이전 포스트에서 rdt 방식은 stop-and-wait 으로 진행됨으로 굉장히 효율이 떨어진다는 것을 알았다.

효율을 높이기 위해서 파이프라이닝 방식을 사용한다. 

컴퓨터 구조를 공부한 적이 있는 사람이라면 이 그림이 익숙할 것이다.

 

파이프라이닝이란 무엇일까? 단순히 말해 여러 일을 동시에 처리하는 것이다.

4명의 사람이 자신의 옷을 세탁한다고 가정하자. 

 

세탁기에 옷을 넣고 세탁 -> 건조기에 옷을 말림 -> 옷을 갠다 -> 옷장에 보관

 

위 그림에서 이 하나의 과정은 한 번 하는데 2시간이 걸린다.

A, B, C, D 라는 사람이 이 일을 각각 하나씩 하는데 서로의 작업이 전부 끝날 때까지 기다렸다가

자신의 일을 한다고 가정하면 저녁 6시에 시작한 일이 무려 새벽 2시가 되어서 끝이 난다.

 

이와 반대로 앞 사람이 끝난 작업을 다음 사람이 바로 하게 되면 

모든 작업이 9시 30분에 끝나게 되니 얼마나 효율적인가?

 

이것이 바로 파이프라이닝이다. 

 

한번의 한 개씩 패킷이 목적지에 도착하면 목적지로부터 돌아오는 ACK를 기다리지 말고

여러 패킷을 전송할 수 있도록 하는 것이다.

 

파이프라이닝을 이용하여 이전보다 이용률이 무려 3배나 좋아진다.

 

하지만 파이프라이닝을 사용하려면 다음 사항을 고려해야 한다.

• 순서 번호(sequence number) 범위의 증가 : 여러 패킷을 보낼 수 있게 됨으로써 0과 1 만으로는 부족
• 버퍼(buffer)의 필요 : 송신측과 수신측은 여러 패킷을 담을 수 있는 버퍼가 필요
• 파이프라인의 대한 오류 : 파이프라인에서 발생하는 패킷 손실 , 지연 패킷에 대한 처리 방식이 필요

이 고려 사항들은 어떻게 해결해야 할까?

---

GBN(Go-Back-N) : N에서부터 다시

GBN 프로토콜은 수신자 측에서 지금까지 성공적으로 받은 패킷 순서 번호에 대한 ACK를 전송하며,

순서에 맞지 않는 패킷은 성공적으로 수신한 것으로 간주하지 않는다.

따라서 송신자는 ACK를 받지 못한 가장 오래된 패킷부터 다시 재전송하게 된다.

 

왼쪽에서 오른쪽으로 쌓이는데 가장 왼쪽에 있는(=가장 오래된) 노란색 패킷부터 재전송한다.

이때 이 패킷들은 최대 허용수(N=window size) 보다 크지 않아야 한다.

 

• 수신자는 누적된(cumulative) ACK만 전송 (수신된 패킷들의 순서번호 사이에 갭이 있으면 ACK는 응답하지 않음)
• 수신자는 비순차(out of order) 패킷으로 버퍼링하지 않는다.
• 송신자는 ACK받지 못한(문제가 생긴) 가장 오래된 패킷부터 모두 재전송 (타이머가 1개)

 

위 그림의 sender에게는 4개의 저장 공간이 있다.

처음에 sender는 패킷을 pkt0부터 pkt3 까지 총 4개를 보내고 ACK를 대기한다.

 

pkt2의 경우, 중간에 손실이 있어서 receiver는 이를 받지 못했기 때문에 ACK2를 보내지 않고

ACK1을 보내어 자신이 pkt2를 제대로 받지 못했음을 알린다. 

 

※이전까지 순서 번호가 0과 1만 있었는데 이제 2도 생겼음을 눈치챘는가?

앞에서 pkt0, pkt1의 긍정응답인 ACK0과 ACK1은 슬라이딩 되어 다음 패킷인 pkt4와 pkt5를 보낸다.

 

앞에서 pkt2를 받지 못했으니 이후의 패킷인 pkt3, pkt4, pkt5는 잘 도착하여도 이를 버리고(discard)

sender에게 ACK3 ACK4 ACK5 가 아니라 모두 ACK 1을 보낸다.

 

즉 pkt2가 다시 제대로 receiver에게 전달되어 ACK2가 sender에게 가야만 뒷 작업인

pkt3, pkt4, pkt5의 패킷을 받을 수 있는 것이다.

 

패킷 pkt3, pkt4, pkt5(후배님들)는 자신들보다 먼저 보내졌던 pkt2(선배님)을 받지 못하였다고

온전히 받아졌음에도 불구하고 버려졌다(discard).

 

굉장히 비효율적이지 않은가?

이것을 해결하기 위해 SR 이 등장했다.

---

SR(Selective Repeat) : 선택된 것만 다시

SR은 받는 쪽에도 저장 공간을 만드는 것이다.

따라서 불필요한 재전송 즉, 이미 온전히 받은 패킷의 재전송을 피할 수 있다.

 

(a)는 sender의 저장 공간, (b)는 receiver의 저장 공간이다.

receiver의 저장 공간을 보면 sender로부터 문제 없이 도착한 패킷은 자주색,

그렇지 못한 패킷은 회색으로 표시가 되어 있다.

 

동작이 어떻게 이루어지는지 살펴보자.

 

아까와 마찬가지로 sender는 패킷을 pkt0부터 pkt3 까지 총 4개를 보내고 ACK를 대기한다.

pkt2가 손실이 일어나 receiver는 이를 받지 못했지만 

pkt3를 받았을 때 순서 번호 3에 맞춰 ACK3를 보낸다. 

pkt4와 pkt5를 받은 receiver 또한 ACK4 ACK5를 보낸다.

pkt2의 긍정응답인 ACK2를 대기하고 있던 타이머가 초과(time out)되어 pkt2를 재전송한다.

 

이러한 SR에도 문제점이 있는데 아래를 살펴보자

---

이 그림에서 pkt0, pkt1,pkt2의 긍정응답인 ack0, ack1, ack2가 sender에게 가는 도중 손실이 되었다.

타임 아웃 이후에 pkt0을 재전송하게 된다면

이것이 순서번호가 0인 첫번째 패킷이 재전송된 것인지,

아니면 이동한 슬라이드 안의 순서번호가 0인 새로운 패킷이 온 것인지

알 방법이 없다.

 

이를 해결하기 위해선 위에서 나온 N(=window size)의 크기 조절이 중요하다.

N은 sender의 순서번호 공간 크기의 절반보다 작거나 같아야한다.

 

예를 들어 순서번호가 0,1,2,3 총 4개라면 N은 1~3의 크기를 가져야 한다.