패킷을 제대로 도착하지 않으면, 수신 측에서 NAK를 보내야 하지만, NAK 대신에 마지막 패킷에 대한 ACK를 송신한다. 예를 들어, 내가 0번 패킷을 잘 수신했고, 그 다음 패킷인 1번 패킷을 수신했는데 패킷이 깨졌으면 NAK를 보내야 하지만, NAK 대신에 시퀀스 번호 0번에 대한 ACK를 송신 측에 전송한다. → 그렇다면 송신 입장에서는 이전 패킷에 대한 ACK를 수신한 것이므로 duplicate ACK를 수신한 셈이 된다. 여기서 주의해야 할 점은 rdt2.1에서 ACK, NAK를 보낼 때는 ACK, NAK에는 시퀀스 번호가 없었다. 즉, rdt2.1 ACK 전송 방식으로는 sender가 duplicate ACK를 구분할 수 없다. 하지만 Nak-free protocol을 운영하려면 ACK 되는 패킷에 시퀀스 번호를 명시적으로 포함시켜야만 sender 측에서 duplicate ACK를 구분할 수 있다. 그래서 rdt2.2는 ACK가 담긴 패킷에다가 시퀀스 번호(까지 포함시켜서 전송한다. (여기서 말하는 시퀀스 번호는 0 ~ 123132132 이런 시퀀스 번호가 아닌 rdt2.1과 마찬가지로 0과 1이 반복되는 시퀀스 번호이다)
rdt2.2 실행 흐름도
sender
0번 패킷을 만들기 위한 상위 층으로부터 콜을 기다린다(상위층으로부터 데이터를 기다린다)
상위층에서 데이터가 오면, 데이터, checksum, sequence num을 붙여서 패킷을 만든 뒤 패킷 전송
데이터 패킷을 보냈으니, 시퀀스 번호 0번에 대한 ACK를 기다리는 상태로 전환
수신 받은 ACK에 오류가 발생했거나, ACK를 받았는데, sender가 기다리던 0번 시퀀스에 대한 ACK가 아닌 1번 시퀀스에 대한 ACK를 수신(0과 1 시퀀스 번호를 바꿔서 사용하므로 1번 시퀀스 번호를 가진 ACK가 도착하면 내가 이전에 받았던 ACK가 다신 온 것 → NAK)하면 방금 전송한 패킷 재전송. || 받은 패킷에 대한 오류가 없고 내가 원한 시퀀스 번호를 가진 ACK이면 상태 변환
receiver(생략된 상태) 1번 데이터 패킷을 기다리는 상태 → 0번 데이터 패킷을 기다리는 상태로 변경: 데이터 패킷을 수신했고, 오류가 없으며, 내가 기다리던 1번 시퀀스 번호인 데이터 패킷이면, 데이터를 추출해서 상위 층에게 데이터를 전송한 후, sender에게 데이터 전송에 대한 ACK를 보내야 하므로, 시퀀스 번호 1번에 대한 ACK와 ACK에 대한 checksum을 만들어서 sender에게 전송 → sender에게 시퀀스 번호 1번에 대한 ACK를 전송했으므로, 시퀀스 번호 0번에 대한 패킷 받을 준비를 위해 상태 변환
시퀀스 번호 0번에 대한 데이터 패킷 대기
데이터에 오류가 발생(NAK 역할을 하는 ACK를 보내야 함)
시퀀스 번호 1번(그 이전 패킷 시퀀스 번호)에 대한 ACK sender에게 전송(재전송 요청)
rdt 3.0
rdt3.0 등장 배경: 패킷 오류뿐만 아니라 데이터 패킷에 대한 손실 상황에 대해서도 대처하자. rdt2.2에서는 checksum과 시퀀스 번호, ACKs 등으로 데이터 손실에 대한 어느 정도는 도움이 될 테지만 충분하지 않다. 가령,데이터 패킷이 전송되다가 중간에 손실이 되면 receive 측에서는 sender 측에서 패킷을 전송한 사실조차도 인식할 수 없기 때문에 아무런 대처도 할 수가 없다. 즉, sender 측에서 데이터 패킷을 보내고 그에 대한 ACK 를 기다리고 있기 때문에 receiver보다는 sender 측에서 데이터 손실에 대한 인식하기가 쉽다(ACK를 기다리는데 receiver로부터 아무런 액션이 없으면 '아 데이터 손실이 발생했구나' 라고 생각할 수 있음)
즉, 패킷 loss를 대처하기 위해서는 sender 측에서 데이터 패킷을 전송한 후, 일정 시간 동안 ACK를 기다린다. 그럼에도 불구하고 receiver로부터 ACK가 오지 않는다면 두 가지 상황을 가정할 수 있다.
데이터 패킷을 잊어버렸거나
ACK가 오다가 손실됐거나
일정 시간 동안 ACK를 받지 못하면 sender 측은 이전에 보냈던 데이터 패킷을 재전송한다. 하지만 ACK가 담긴 패킷이 위에서 가정한 두 가지 상황이 아닌, 단순히 늦게 도착하는 거라면? sender 측은 그 사실을 모르고 이전 패킷을 다시 보낼 테고, receive 측은 결과적으로 duplicate packet을 수신한 셈이 되지만 receiver 측은 이미 duplicate packet에 대한, 시퀀스 번호를 통한 예외 처리 매커니즘을 가지고 있기 때문에 이 상황은 문제가 되지 않는다. (sender가 일정 시간동안 ACK를 기다리기 위해서는 타이머가 필요하다)
sender 단에서 rdt3.0 finite state machine 동작 과정
0번 패킷에 대한 데이터를 상위 계층에서 대기
상위 계층으로부터 데이터를 받으면 데이터, checksum, 시퀀스 번호를 조합해 패킷을 만들고 전송한다.
패킷 전송과 동시에 timer를 시작하고 state machine을 ACK 0번을 기다리는 상태로 바꾼다.
receiver로부터 패킷이 도착했는데, 패킷에 오류가 발생했거나, 기다리던 ACK 0번이 아니라 ACK 1번이 온다면(rdt2.0에서는 재전송 같은 액션을 취했고, rdt3.0에서도 같은 행동을 취해도 되지만 위 템플릿에서는 timeout과 동시에 액션을 취하기 위해서 패킷 오류나 ACK 번호 불일치에 대한 액션을 별도로 취하지 않음) time out과 한꺼번에 액션을 취하기 위해 일단은 아무런 행동을 취하지 않는다
일정 시간을 기다렸는데도 패킷이 도착하지 않으면(time out) 이전에 보냈던 패킷을 재전송하고 타이머도 리셋한다.
패킷을 기다리다가, 기다리던 패킷(오류 X, ACK 0번)이 도착하면 타이머를 중지시키고 그 다음 데이터 패킷(1번) 상위층으로부터 1번에 해당하는 데이터 기다리는 상태로 state machine의 상태를 바꾼다. (이 때 0번 패킷을 여러 번 재전송 했었다면, ACK 0에 대한 패킷이 뒤늦게 도착할 수도 있다. 하지만 ACK 0번에 대한 처리는 이미 끝냈고 상태도 바뀌었기 때문에 ACK 0에 대한 패킷이 뒤늦게 도착하더라도 무시하고 상위 층으로부터 1번 데이터를 기다리기만 하면 된다)
상위 층으로부터 1번 데이터를 수신하면 그 이후의 상황은 1~6번과 동일하다.
(a) no loss: 에서 시퀀스 번호를 ack에 붙일 때, 본인이 올바르게 수신한 패킷에 대한 시퀀스 번호(0번)를 ack에 붙이는 프로토콜이 있는 반면, 해당 시퀀스 번호(0번)를 가진 패킷은 잘 받았고, 그 다음 패킷인 1번 패킷을 receiver가 기다리고 있다는 의미에서 ack 1번(next expected packet)을 붙여서 sender에게 전송하는 프로토콜이 있으니 알아둘 것!!
(b) packet loss: sender가 패킷을 1번을 보냈는데 중간에 패킷이 손실되면 receiver 측에서는 해당 패킷이 loss된 사실을 알 수가 없다. sender는 패킷 1번을 전송함과 동시에 타이머가 가동되고 있고, 타임 아웃이 되면 패킷 1번을 receiver에게 재전송한다.
(c) ACK loss: 이번에 수신 측에서 패킷 1번에 대한 ack 1을 sender에게 송신하던 중, 중간에 ack 1에 대한 패킷이 손실되면, sender 입장에서는 ack 1번을 받지 못하게 되지만, 패킷 1을 전송함과 동시에 타이머를 시작했으므로, 중간에 ack 1 패킷이 손실됐더라도 타임 아웃이 되면 이전에 보냈던 패킷 1을 재전송한다. receiver 입장에서 패킷 1은 이미 수신했으므로 duplicate pakcet이 된다. receiver는 duplicate 패킷은 버리고 ack 1에 대한 패킷을 재전송한다.
(d) premature timeout / delated ACK: sender가 패킷 1번을 송신했고 receiver 측에서도 ack1을 송신했지만 ACK 수신이 지연돼서 타임아웃이 된 상황에서는 sender는 다시 패킷 1번을 재전송한다. receiver 입장에서는 패킷 1번은 duplicate pakcet이므로 해당 패킷은 폐기하고 ack 1을 sender에게 재전송한다. 하지만 sender는 ack 1을 수신하고 패킷 0번을 전송한다. 위 템플릿에서는 타이밍이 엇갈려서 패킷을 두 번씩 전송하고 있지만, sender와 receiver 모두 duplicate packet에 대한 에러 처리 매커니즘을 포함하고 있기 때문에 중복된 패킷이 오더라도 데이터 송수신에는 문제가 없다.
rdt 3.0이 사용하는 stop&wait 방식(패킷 하나를 보내고, 응답 ACK 패킷이 올 때까지 대기)은 신뢰성은 좋지만 성능은 매우 구리다. 가령, 1gbps 데이터 처리를 할 수 있는 링크가 있고, 전파하는 딜레이가 15ms, 패킷 한 개의 길이가 8000bit이면 링크에 8000bit 1개 패킷을 올리는 데 소요되는 시간은 8 microsecs 이 걸린다.
sender가 바쁜 시간: 0.00027 ← utilization이 굉장히 낮다(링크 효율성이 떨어진다)
if RTT(Round Trip Time, 링크를 타고 receiver에 가는 시간. 여기서는 ack도 받아야 하므로 갔다가 와야한다) = 30 msec, 1KB pkt every 30 msec: 33KB/sec thruput over 1 Gbps link: 1 Gbps 처리할 수 있는 링크에서 1초 33KB밖에 처리를 못한다 → 즉, rdt3.0 프로토콜은 물리적 자원의 활용을 효율적으로 하지 못한다. 그래서 신뢰성이 중요한 데이터 송수신 환경에서는 적합한 프로토콜일지 몰라도, 송수신 효율성이 극대화 돼야 하는 대부분의 환경에서는 사용하기에 제한이 많다.
rdt3.0은 신뢰성은 좋지만, utilization이 나쁜 환경도 존재하므로 이것을 극복하기 위해 등장한 것이 Pipelined Protocol이다. 파이프라인 프로토콜은 stop&wait 방식처럼 하나의 패킷을 전송하고 ack가 담긴 패킷을 수신할 때까지 대기하는 게 아닌 패킷들이 전송 중일 때, 다른 패킷도 계속 전송시키는 것이다. 즉, ack를 아직 받지 않았음에도 여러 개의 패킷을 계속 파이프 속으로 보내는 것이다. 이러면 파이프라이닝 방식을 적용하려면 어떻게 해야할까?
우선 시퀀스 번호가 0과 1만 있으면 안 될 거 같다. 여러 패킷이 한꺼번에 가고 있는 시퀀스 번호를 0과 1을 쓰면 이동중인 패킷 간에 시퀀스 번호가 중복될 것이다. 그래서 최소한 이동 중인 패킷에 대해서는 전부 다른 시퀀스 번호를 갖도록 시퀀스 번호 범위가 넓어져야 할 것이다.
sender와 receiver 중 하나에 buffering을 할 수 있는 버퍼가 필요하다. 즉, 이동 중인 패킷들이 전부 처리가 완료될 때까지 sender나 receiver 측에서 임시로 저장해야 할 것이다. stop&wait 방식에서는 패킷을 1개씩 보내기 때문에 패킷을 저장할 버퍼가 필요없었지만, 파이프라이닝 방식은 여러 개의 패킷을 동시에 보내기 때문에, 송수신이 실패했을 경우 재전송을 해줘야 하므로, 패킷을 저장할 수 있는 버퍼가 필요하다. 파이프라이닝 방식을 사용한 프로토콜 중에는 go-Back-N과 selective repeat 방식이 있다.
두 번째 파이프라이닝 utilization 템플릿에서 3개의 패킷을 파이프라이닝 하면 utilization을 3배로 올릴 수 있는 것을 알 수 있다. 즉, 많은 패킷을 연속으로 보낼수록 utilization을 향상시킬 수 있다!!!
Go-back-N
가정: sender가 ack를 받지 않은 상태에서 n개까지 패킷을 전송할 수 있다.
receiver는 ack를 보내야 할 때, cumulative ack(만약 sender가 패킷1, 패킷2, 패킷3을 보내면 receiver 측에서 ack를 보낼 때 패킷1, 2, 3을 전부 잘 받았다라는 메시지를 보냄 → cumulative, 쌓아서 보낸다)를 보낸다. 하지만 내가 수신한 패킷 사이에 gap이 생기면 gap이 생긴 패킷에 대해서는 ack를 날릴 수 없다(e.g. 1번 패킷, 2번 패킷을 잘 받고 3번을 못 받고 4번 5번을 받았으면 receiver는 4번을 잘 받았지만 4번에 대한 ack를 날릴 수가 없다. 이게 무슨 말이냐면 내가 1, 2 패킷을 받고 ack 2를 보내면 2번 패킷까지 잘 받았다는 의미이다. sender가 1, 2, 3, 4 패킷을 보냈는데 receiver 측에서 3번까지만 제대로 수신했다면 ack4가 아닌 ack3을 보내야 한다)
sender는 ack를 아직 못 받은 패킷들 중 전송한 지 가장 오래된 패킷에 대한 타이머만 가지면 된다(go-back-n에서는 타이머를 하나만 가진다). 타이머의 타임 아웃이 되면 전송한 지 가장 오래된 패킷을 기준으로 그 때까지 ack를 못 받은 패킷을 전부 재전송한다.
Selective Repeat
가정: sender가 N개의 ack를 받지 않은 채로 파이프라인에 올릴 수 있다.
receiver는 각 패킷에 대해서 cumulative가 아닌 individual ack를 보낸다. (e.g. ack1을 받으면 패킷 1번을 잘 받은 거고, ack 2를 받으면 패킷0, 1번은 모르겠고, 패킷 2번만 잘 받은 게 된다)
selective repeat 방식에서는 individual ack를 보내기 때문에 sender측에서 ack를 못 받은 패킷에 대해서 timer를 하나씩 유지해야 한다. 만약 타이머의 타임이 타임 아웃되면 시간이 만료가 된 패킷 1개에 대해서만 재전송한다.
시퀀스 번호를 k-bit를 사용하면 2^k 개의 시퀀스 번호를 사용 가능하다. 2^k 만큼의 시퀀스 번호를 붙인 ack를 전부 전송이 가능하지는 않다. 그 중의 일부로 window size(ack를 받지 않은 상태로 연속으로 전송이 가능한 패킷의 개수)를 정하게 된다. 위 템플릿에서 ack를 받으면 window가 왼쪽으로 밀리면서 일정 사이즈를 유지하게 된다.
ACK(n): 시퀀스 번호 n을 포함한 지금까지 전송한 패킷들 전부에 대한 ack → cumulative ack
timer는 ack를 못 받은 전송한 지 가장 오래된 패킷을 기준으로 운영.
timeout(n): 타임 아웃이 되면 위 템플릿 기준으로 현재 윈도우 내에 있는(전송은 했지만 ack를 못 받은 패킷에 한해서) 패킷들을 전부 재전송한다.
base(윈도우의 맨 처음 시퀀스 넘버)의 시퀀스 넘버를 1로, 다음 시퀀스 넘버(윈도우에서 아직 전송을 하지 않는 시퀀스 번호)를 2로 세팅
wait 상태로 있다가, 상위 계층에서 데이터를 받았으면, 해당하는 nextseqnum이 base+N보다 작은지, 즉 윈도우 사이즈 내에 있는지 체크하고 윈도우 사이즈 내에 nextseqnum이 있으면 데이터, checksum, nextseqnum으로 패킷을 만들고 패킷 전송. 또한, 전송한 패킷이 윈도우에서 전송한 최초의 패킷이면 타이머 시작! 만약 else이면 데이터를 아직 전송할 수 없는 상태이므로 윈도우 내로 nextseqnum이 들어오면 전송.
receive로부터 컨트롤 패킷(ack 패킷)을 수신하고, 해당 패킷이 문제가 없다면, ack 넘버를 추출해서 base = ack + 1을 셋팅(윈도우를 왼쪽으로 한 칸 밀기). → 만약에 base == nextseqnum의 값이 같다는 의미는 전진된 윈도우 내에서 전송된 패킷이 아무것도 없음을 의미하므로 timer를 stop하게 된다.
오류가 났든지(컨트롤 패킷이 오류가 나면 아무 행동도 하지 않고 타임 아웃이 날 때까지 대기), 아직 ack 패킷이 도착 안 한 건지는 모르겠으나, time out이 발생하면 base부터 시작해서 nextseqnum - 1 패킷까지 전부 재전송한다.
Go-Back-N에서 receive는 1번, 2번 패킷 다음에 3번 패킷을 받으면 제대로 수신이 된 것이므로 ack3을 보내겠지만, 1, 2번 다음에 4번 패킷을 수신한다면 3번 패킷이 (아직 도착 안 한 건지, 오류가 난 건지 모르겠으나) 중간에 빠졌으므로 이 때는 ack를 2번을 보낸다. 이럴 경우 duplicate ACKs가 발생할 수 있다. receiver 측에서는 내가 다음에 받아야 할 시퀀스 번호가 뭔지 기억해야 할 필요가 있다.
만약에 receiver가 ack 2번까지 보낸 다음 4번 패킷이 오면 순서가 맞지 않으므로 4번 패킷은 버퍼링을 하지 않고 그냥 폐기해 버리고, 현재까지 올바르게 수신한 최고 시퀀스 번호인 ack 2번을 다시 재전송한다.
receiver도 sender와 마찬가지로 시퀀스 넘버 윈도우를 가지고 있는데 receiver에서 윈도우는 sender 측으로 ack를 날려줬을 때 전진하게 된다.
<receiver extended FSM>
expectedseqnum = 1 ⇒ 받을 예정인 시퀀스 번호 설정하고 wait
데이터 패킷을 수신하고, 오류가 없고 내가 받고자 하는 시퀀스 번호를 가진 패킷이면 패킷으로부터 데이터를 추출하고 상위 계층으로 데이터를 전송한 후, expectedseqnum, ack 1, checksum으로 패킷을 만들어서 sender 측으로 전송 후, expectedseqnum에 1를 더하고 다시 wait 상태로 돌아감
만약 패킷이 오류가 난 채로 온다면, 시퀀스 번호가 1인 패킷을 다시 수신해야 하므로 ack 0을 가진 패킷을 만들어서 sender 측으로 전송한다. sender 측은 0번 다음 패킷인 1번 패킷을 전송해줄 것이다.
Selective Repeat
receiver는 수신한 패킷에 한해서 하나씩(cumulative ack가 아님) 개별적으로 ack를 보낸다.
개별적으로 ack를 보내기 때문에, 패킷들을 bffer에 receiver에서 저장해야 한다. 몇몇 패킷들은 재전송이 될 수도 있고 다른 이유로 인해서 패킷들의 순서가 맞지 않을 수 있다. 상위 층에다가 데이터를 올려줄 때는 패킷들의 순서를 맞춘 채로 올려야 하기 때문에 buffer에 패킷들을 저장했다가 순서에 맞게 상위 층으로 전송한다.
sender는 ack를 받지 않은 패킷들에 한해서만 재전송한다( unACKed 패킷에 대해서 타이머를 각각 유지하고 있다)
위 템플릿에서 sender 측 윈도우를 보자. 윈도우 내에서 몇 몇 패킷은 ack를 받았지만 몇몇 패킷은 아직 ack를 수신받지 못했다. 위 템플릿에서 보여주는 예처럼 ack를 순서적으로 받지 못한다면 윈도우는 앞으로 절대 전진할 수 없다.
sender 역시 마찬가지이다. sender에서는 ack를 보낸 이후에 윈도우를 전진할 수 있지만, sender 측 윈도우에서 분홍색 패킷은 (이미 ack를 날려준 패킷이나, 패킷의 순서가 맞지 않아서 buffer에서 재조합을 해야한다) 이미 수신이 됐으나 ack를 날린 패킷보다 그 이전 패킷이 아직 ack를 못 날렸기 때문에 윈도우를 전진시킬 수가 없다.
sender
상위 계층으로부터 데이터가 내려오면, 윈도우의 사용 가능한 다음번의 시퀀스 번호를 체크하고 있으면 패킷을 만들어서 전송하고 불가하면 보류.
특정 패킷에 대해서 타임 아웃이 발생하면 그 패킷만 재전송하고 타이머를 재시작한다.
만약에 sender가 ack를 받았는데, 그 ack num이 sender sendbase ~ sendbase -1 범위에 있다면(시퀀스 번호의 윈도우 내에 있는 ack이므로 수신한 패킷 n에 대해서 기록(mark)만 해놓고, 윈도우는 전진시키지 못한다. ack를 받았는데 받은 ack보다 작은 윈도우 내의 패킷이 전부 ack를 받았으면 받은 ack 개수만큼 윈도우를 전진시킬 수 있다.
receiver
receiver가 기대하고 있던 윈도우 base 범위에 있는 패킷 n이 도착하면 해당하는 패킷 n에 대해서 ack(n)을 sender에게 전송한다.
만약 패킷 n이 순서가 맞지 않은, 이전에 도착하지 않은 패킷이 있으면 버퍼링(버퍼에 저장)을 한다.
패킷들의 순서가 맞으면 버퍼에 저장되어 있는 패킷들을 포함해서 상위 계층으로 전송하고 윈도우를 그 개수만큼 전진시킨다.
Selective repeat 방식의 딜레마
위 템플릿에서 (b) 상황을 보자. sender가 보낸 0, 1, 2번 패킷을 receiver에서 수신하고 receiver는 ack 0, 1, 2를 송신함과 동시에 receiver의 윈도우를 증가시킨다. receiver에서 ack0, 1, 2를 sender 측으로 전송했는데 중간에 ack가 손실이 되면 어떻게 될까? 그러면 sender에서 ack 0, 1, 2번을 기다리는 타이머가 타임 아웃이 돼서 자동으로 패킷 0, 1, 2을 receiver 측으로 재전송할 것이다. receiver 측에서 받을 다음 패킷들은 3, 0, 1인데 sender 측에서 보낸 재전송 패킷들은 0, 1, 2 패킷이다. 3번 패킷은 안 왔지만 0, 1 패킷이 왔으므로 receiver는 0, 1 패킷들을 받아들인다. 하지만 이번에 받은 0,1 패킷은 duplicate 패킷이므로 받으면 안 되지만 패킷 번호의 일치로 인해서 duplicate packet이 새로운 packet인 것처럼 받아들여진다. 어떻게 하면 이 문제를 해결할 수 있을까? → Maximum Window Size를 지키자!!!!
Selective Repeat 방식에서는 위 문제를 방지하려면 maximum 윈도우 사이즈가 2^k-1 개수를 넘으면 안 된다!!
Go-Back-N 방식도 위 문제를 발생할 수 있으므로 맥시멈 윈도우 사이즈가 2^k - 1 개를 넘으면 안 된다!!
