기초컴퓨터네트워크 11 (pipelined protocols continue, Go-Back-N)

TonyHan·2021년 4월 15일

21) 기초컴퓨터네트워크

목록 보기

12/30

Pipelined protocols overview

ACK을 받지 못한 상태에서도 여러개의 패킷을 보내고 수신자측에서 ACK가 오는데로 더 데이터를 보내는 것이 성능을 향상시킬 수 있는 방법이다. 이런것을 Pipelined protocol이라고 부른다.

두개다 N개의 패킷을 보내고 수신자로부터 ACK를 받으면 더 많은 패킷을 보낸다.
차이점은 Go-Back-N은 중간에 문제가 생기면 문제가 생긴시점부터 다시 보내는다. Selective Repeat는 문제가 생긴 패킷들만 재전송을 받아서 빈칸을 채워서 application쪽으로 올려주는 방식이다.

Go-back-N
- sender can have up to N unacked packets in pipeline
- receiver only sends cumulative ack
  - doesn't ack packet if there's a gap
- sender has timer for oldest unacked packet
  - when timer expires, retransmit all unacked packets
Selective Repeat
- sender can have up to N unacked packets in pipeline
- receiver sends individual ack for each packet
- sender maintains timer for each unacked packet
  - when timer expires, retransmit only that unacked packet

2. Go-Back-N: sender

k-bit sequence number in packet header : 패킷은 k-bit의 sequence-number가 존재한다.
"window" of up to N, consecutive unacked packets allowed

N개의 어떤 패킷들을 보내야 할 것인가. sender가 가지고 있어야 하는 변수나 parameter는 총 3가지가 존재한다.

send_base : sender가 전송을 할 수 있는 window의 가장 앞의 패킷.
netxseqnum : 앞의 노란색은 ack을 아직 못받은것이고 파란색은 아직 안 보낸 패킷자리들을 이야기 한다.
window_size(N): 내가 N개까지 한꺼번에 보낼 수 있다.
앞의 초록색은 이미 ACK를 받은 것들이다.
흰색은 패킷을 보낼 수 없는 상태이다.
이제 패킷을 받게되면 sliding window 효과가 일어나게 된다. window size는 바뀌지 않고 send_base 위치만 바뀌게 된다.

ACK(n): ACKs all packets up to, including sequence number n - "cumulative ACK" : 누적 ACK이라고 부른다. 만약에 ACK가 몇칸 뛰어서 보내졌다고 하면 이전에 있던 패킷은 정상적으로 보내졌다고 판단한다.
- may receive duplicate ACKs
timer for oldest in-flight packet : window에서 sequence number가 앞에 있는 것에 timer가 존재한다.
timeout(n): retransmit packet n and all higher sequence number packets in window : n번째 패킷의 시간이 다 되었다면 n번째 패킷부터해서 다 다시보내야 한다.

(요약 - 중요)
패킷 헤더에 k-bit seq가 존재, n size의 window가 존재한다.

not yet ack는 ACK을 받는 순간 window가 한칸 움직이게 된다. 하지만 가장 오래된 패킷이 받지 못하면 여전히 window를 움지이지 못한다.

ACK(n) : n번 까지의 패킷이 제대로 받아졌다.(각각이 보내진것이 아니다) 만약에 ACK가 몇칸 뛰어서 보내졌다고 하면 이전에 있던 패킷은 정상적으로 보내졌다고 판단한다.

timer for oldest in-flight packet : window에서 sequence number가 앞에 있는 것에 timer가 존재한다.

timeout(n) : n번째 패킷의 시간이 다 되었다면 n번째 패킷부터해서 다 다시보내야 한다.

GBN: sender extended FSM

A : 초기상태
rdt_send : 보내야하는 패킷의 크기(window)보다 nextseqnum이 작으면 패킷을 보낸다. 만약 base가 nextseqnum이면 start_timer 이다. 그 이외의 바깥에 데이터가 있다면 데이터전송을 멈춘다.
rdt_rcv(rcvpkt) : receiver 쪽에서 데이터가 오고, 패킷이 깨지었다면 작동을 안한다.
notcorrupt(rckpkt) : ACK 번호 + 1을 해서 base 번호를 만드는 것이다. 만약 base와 nextseqnum이 같다면 timer을 정지하고 그게 아니면 timer을 시작한다.
timeout : timer 시작, udt_send(base 부터 nextseqnum - 1 까지) 데이터를 다시보낸다.

(요약)
1. 처음에는 base=1, nextseqnum=1
2. nextseqnum이 윈도우 안에 있으면 nextseqnum의 번호를 적어 패킷을 보낸다. base가 nextseqnum과 같은 경우 timer를 시작한다. 그외의 경우는 무시
3. timeout이 되면 timer를 돌리고 노란패킷들을 다 다시보낸다.
4. 패킷을 받았는데 에러가 없으면 base를 이동, base가 nextseqnum인 경우 타이머 중지

default : rdt_rcv를 제외한 모든 경우는 가장 마지막 seq num을 가진 패킷을 보낸다.
rdt_rcv : 고장안나고 seqnum이 정상인 경우 expectedseqnum을 기준으로 패킷을 보내고 sender쪽으로 전송한다.

ACK-only: always send ACK for correctly-received packet with highest in-order sequence number : 데이터가 오면 항상 ACK를 보내주는데 cumulate ACK이기 때문에 순서대로 가장 높은 sequence number을 보낸다. (즉 중간에 뛰어서 왔다면 이전에 가장 높은 번호를 보낸다.)
- may generate duplicates ACKs : sender은 중복된 ACK을 받을 수 있따.
- need only to remember expectedseqnum
Out-of-order packet : 순서에 맞지 않는 패킷들
- discard (don't buffer): no receiver buffering : 패킷을 받지 않는다.
- re-ACK packet with highest in-order sequence number : 가장 최근에 순서에 맞는 가장 높은 seq number을 보낸다.

(요약)
1. expectseqnum =1인 상태로 시작한다.
2. 받은 데이터가 expect이면 정상이다. expect에 대한 ACK을 보내준다. expect만 보내주는 이유는 base 가 되는 비트만을 가지고 error control이 가능해서이다.
3. 만약 중간에 못받은 것이 있다면 그 다음것부터 다 보내지 않는다. 그래서 가장 최근에 잘 받아진 패킷만 보낸다는 의미이다.
4. out-of-order면 그냥 버린다.

https://www.youtube.com/watch?v=gaocB7unrqs