Chapter3 - GoBackN과 Selective Repeat

Go-Back-N과 Selective Repeat의 차이

- time out이 발생했을 때 어떻게 처리하냐가 이 둘의 큰 차이점

 

▪︎ Go-back-N - N개를 실행하다 문제 발생 시 다시 뒤로 간다.

- sender는 ACK를 받지 않고 최대 N개까지 파이프라인 형식으로 보낼 수 O

- receiver는 오직 cumulative ack를 보냄.

  - 항상 자신이 정상적으로 받았던 마지막 seq #의 packet에 대해서만 ACK를 보냄.

   ex) 3번을 보냄. -> seq # 0,1,2,3에 대한 패킷은 모두 정상적으로 받았음을 의미

  - 순서에 맞지 않게 온 packet은 모두 무시 -> gap은 허용 X

- sender는 ack를 아직 받지 않은 가장 오래된 패킷에 대해 timer를 실행 (N개 단위로 timer 시행)

   - timeout(n) : 윈도우 안에서 time out이 걸린 seq #보다 높은 seq #을 가지는 패킷들(ack를 받지 않은 패킷들)을 모두 재전송

 

cumulative ack : 하나의 ack를 가지고, 그 seq # 이전의 모든 패킷은 받았다고 표시해줌.

   - 누적해서 ACK를 받음.

   - ACK(n) : receiver가 n번 packet까지 모두 받았을 때를 의미

   ex) 6번 못받음 7번 8번 받음 -> Ack(5)를 보내줘야 함.

 

▪︎ Selective Repeat - 선택적으로 다시 보냄.

- N개의 ack를 받지 않은 패킷을 파이프라인에서 가질 수 O

- receiver은 각 패킷에 대해 individual ack를 사용하여 전송

   - ex) 3번을 보냄. -> seq #3에 대한 패킷을 받았음을 의미(0~3번 패킷을 모두 받은게 X)

- sender는 각각의 ack를 받지 않은 패킷에 대해 timer를 가지고 O

   - 패킷 하나 보내면 timer 시행 

   - 각각의 패킷에 연결된 timer 존재

   - time out이 발생하면 어떤 패킷에 대한 time out인지를 판단 후 해당 패킷만 재전송

 

Go-Back-N (sender)

▪︎ sender는 3가지 변수에 대한 정보를 기억하고 있어야함.

   - send_base : 아직 ACK를 받지 않은 첫번째 seq #

   - nextseqnum : 아직 보내지 않은 패킷들의 첫번째 seq # 

   - N : sender는 N개까지 ACK를 받지 않고, 패킷 연이어 전송 가능

▪︎ sender가 항상 N개의 packet을 다 보내고 있는건 아님.

   - application-layer에서 N개만큼의 data를 줘야 보낼 수 O

▪︎ k-bit의 seq # field가 packet 헤더에 존재 --> 2의 k승개의 seq # <= N을 만족해야함.

▪︎  sender는 ACK(n)을 받으면 window의 시작을 앞으로 한칸 이동해줘야함.(n+1번째로)

   ex) ACK(10) -> send_base = 11로  변경

▪︎ if ) send_base == nextseqnum -> 윈도우 상에서 아직 보낸게 아무것도 없음. / 내가 보낸 패킷에 대한 ACK를 모두 받음. 

▪︎ sender쪽에서 duplicate ACK를 구분할 필요 X (정상적으로 ACK를 받은 경우처럼 처리하면 됨)

 

Go-Back-N (receiver)

▪︎ receiver는 1가지 변수에 대한 정보를 기억하면 됨.

   - rcv_base : 내가 받고 싶은 packet의 seq #

▪︎ receiver는 항상 자신이 정상적으로 받았던 마지막 seq #의 packet에 대해서만 ACK를 보냄.

▪︎ 제멋대로 순서의 패킷을 받았을 땐 

   - 버퍼가 없으면 버리거나 버퍼에 저장

   - 정상 순서의 가장 높은 seq #의 패킷에 대한 ACK를 재전송

 

Go-Back-N in action

 

Go-Back-N 요약

▪︎ 장점

- ACK loss 시 효율적 (ACK를 못받으면 window 및 send_base가 이동을 하지 못하기 때문에 대기)

▪︎ 단점

- packedt loss 시 비효율적 (loss가 난 이후로 보냈던 packet들은 모두 무시되므로)

 

Selective repeat

- receiver가 받은 패킷에 대해 올바르게 받았다는 사실을 개별적으로 알려줌.

- 버퍼 꼭 필요

   - 순서가 틀리게 왔어도 버퍼에 저장 후 in-order하게 application-layer로 보냄.

- sender는 각각의 패킷에 대해 타이머 실행/재전송

- sender window는 N개의 sequence #를 가질 수 O

- sender window는 ACK 안받고 N개까지만 패킷 보낼 수 O

 

ex) ACK 10

   - go-back-N : packet을 10번까지 다 받았다.

   - selective repeat : packet 10번을 받았다.

 

Selective repeat : sender, receiver windows

- 항상 send_base는 노란색 (ACK를 받았다면 윈도우가 이동할 것이므로)

- go-back-N과 다르게 sender의 window 안에는 이미 ACK를 받은 패킷들이 섞여 있을 수 있다.

-  sender의 window와 receiver의 window가 다를 수 있다.

- window : 아직 ACK를 받지 못한 가장 작은 #부터 시작

 

Selective repeat: sender and receiver

▪︎ sender

- data가 application layer로부터 도착하면 nextseqnum가 윈도우 안에 있다면 패킷 전송 후 start timer, nextseqnum은 ++;

- timeout(n) : n번 패킷만 다시 보내면 됨, restart timer

- ACK(n) in [sendbase, sendbase+N-1] <window 안의 범위의 ACK가 옴>

   - 패킷 받았다고 표시

   - 아직 ACK을 안받은 패킷중 가장 작은 seq #로 send_base 이동 (ACK를 안받은 그다음으로)

 

▪︎ receiver

- receiver는 2가지 변수에 대한 정보를 기억하면 됨.

   - rcv_base : 내가 받고 싶은 packet의 seq #

   - N (receiver도 윈도우 가지므로 저장 필요)

 

- n번 패킷은 [rcvbase, rcvbase+N-1] 안에 존재 -> Ack(n) 전송

   - 정상적인 경우(rcv_base에 해당하는 패킷이옴): 전달 (버퍼에 저장된 패킷과 함께 in-order로 정리해서 전달),                     recv_base 이동

   - out-of-order : 버퍼에 저장

- n번 패킷이 [rcvbase-N,rcvbase-1] 안에 존재 -> Ack(n) 전송

   - Ack loss가 나서 sender가 패킷 재전송한 경우임.

- 그 이외의 경우 -> 무시

 

Selective repeat in action

 

 

Selective repeat : 딜레마

(a) 아무 문제 없는 경우

(b) window size=3 && 3번 Ack loss가 발생한 경우 -> seq # size && window size가 문제 발생시킴!

   - 0번 패킷에 대한 time out 가장 먼저 발생 -> sender : 패킷 0번 재전송한 경우

   

-> receiver는 (a),(b) 두 동일한 상황을 seq # 가지고 구분 필요

 

Selective repeat : 딜레마 해결

- sender의 window와 receiver의 window가 안겹쳐서 문제 발생

- seq # size >= window size * 2

   - 위의 상황에서 seq # size >= 6  → 적어도 seq # (0,1,2,3,4,5)를 가져야함.  → seq # 3bit 필요