⚠️ 들어가기 앞서
경북대학교 컴퓨터학부 COMP0414-001 컴퓨터망 과목을 공부하며 정리한 글입니다.
1. Pipelining이란
앞서, 송/수신자 간의 패킷 교환에서 송신자는 패킷을 보낸 후 응답이 올 때까지 기다리는 stop and wait 방식을 소개하였다. 그리고 글의 말미에 패킷을 보내고 기다리지 않고 바로 다음 패킷을 보냄으로써 utilization을 늘릴 수 있는 방법인 pipeline을 잠깐 소개했었다.
이 글에서는 pipeline을 수행하는 두 가지 대표적 방법인 Go-Back-N 프로토콜과 Selective Repeat 방식을 소개한다.
2. Go-Back-N
Go-Back-N 방식은 수신자가 어떤 패킷을 받지 못하면 그 패킷부터 모든 패킷을 다시 보내는 방법이다.
-
Go-Back-N(이하 GBN)에서, 송신자는
ACK를 받지 않은 상태로 동시에 최대로 보낼 수 있는 패킷의 수를 정하고, 이를window size라고 하며, 현재 window 위치를 설정해 window size만큼의 범위를 구축한다. -
송신자는 보낼 패킷들이 들어있는 버퍼의 시작부터 window의 범위를 설정하고, sequence number가 그 window의 범위 안에 들어 있는 패킷을 모조리 보낸다.
-
수신자는 패킷들을 연속해서 받고, 각각의 패킷을 받을 때마다 sequence number를 확인하고,
ACK를 보낸다. -
이 때, 송신자가 보낸 패킷들 중에서 일부가 유실될 수 있다. 그러면 수신자가 받은 패킷들의 sequence number에
빈틈이 생기게 된다. 이 때, 빈틈이 생기기 전에 정상적으로(연속적으로) 받은 패킷의 마지막 번호를 지속적으로ACK에 실어서 보낸다. -
송신자는 내가 보낸 패킷의
ACK가 정상적으로 왔다면, 그 패킷을 처리됐다고 기록한 후, window를 오른쪽으로 한 칸 밀어서 하나의 패킷을 더 보낼 수 있는 상태로 만든다.
즉 수신자는 패킷 사이에 빈 번호가 발생하면 그 번호 직전의 번호를 계속 ACK에 담아 보낸다. 이런 식으로 "내가 이 번호까지는 잘 받았음" 하고 송신자가 잘 받은 패킷들을 점점 누적시켜 가기 때문에 Cumulative(누적하는) ACK 이라고도 한다. 그리고 연속된 패킷의 마지막 번호를 rcv_base 에 기록해 둔다.
복잡하니 그림과 함께 순서대로 천천히 짚어 보자..!!
window size는 4로 설정해 주었다. 즉 송신자는 ACK가 어떻게 오건 간에 한 번에 4개까지는 보낼 수 있다. 그리고 보낼 패킷은 9개이다.
- 송신자는 0, 1, 2, 3번 패킷을 우다다 보낸다. (이 중 2번 패킷이 유실되었다.) 그리고
ACK를 기다린다. - 수신자는 패킷들을 받는다. 0, 1번 패킷에 대해서는 잘 받았으므로, 연속 수신 패킷의 마지막 번호가 계속해서 이어질 수 있다. 각각
ACK(0),ACK(1)를 보낸다.rcv_base도 1이 되었다. - 그러나 다음번에 2번 패킷이 아닌 3번 패킷을 수신했다.
rcv_base+1에 해당하는 패킷이 아니므로, packet loss가 생겼다고 감지했다. 3번 패킷을 받았으나 연속되지 않으므로rcv_base인ACK(1)을 다시 보낸다. 4번 패킷에 대한ACK도 마찬가지. - 송신자는
ACK(0)과ACK(1)을 받으면, 먼저중복된 ACK인지 확인한다. 중복되지 않고 처음 들어온 번호라면 그 번호의 패킷을 완료처리하고 window를 한 칸 이동시킨다. 즉 4번 패킷을 보낼 수 있게 된다. - 따라서 4번 패킷을 준비되는 대로 바로 보낸다.
ACK(1)과 5번 패킷의 전송도 마찬가지. - 그 다음에는 다시
ACK(1)이 들어오는데 이는 중복된ACK이므로 바로 무시한다. ACK를 받지 못한 2번 패킷에 대해 timeout이 발생하면 2번 패킷부터 지금까지 보냈던 모든 패킷들 (2~5번)을 다시 보낸다.
3. Selective repeat
위에서 알아본 Go Back N 방식은 loss된 패킷을 발견하면 그 뒤의 모든 패킷을 다 다시 보내는 방식인데, 정상적으로 도착한 패킷이라고 하더라도 재전송해야 하기 때문에 비효율적이다.
이 문제점을 효율적으로 개선한 방식이 Selective Repeat(이하 SR) 이다.
Selective Repeat (SR) 방식은 수신자가 받은 각각의 패킷에 대해
ACK를 보내는 방식이다.
다른 패킷이 전달이 잘 되었건 말건, 모든 패킷은 각각 따로 고려된다. 이제 송신자와 수신자가 하는 역할을 알아보자.
송신자는 GBN 방식과 마찬가지로 window를 가지고 있다. window 범위 안에 들어오는 패킷들을 다 보내고 나면, 각각의 패킷에 대해 ACK을 기다린다. 그리고 각각의 패킷에 대해 타이머를 가지고 있고, 일정 시간이 지나도 ACK 가 도착하지 않으면 timeout을 발생시켜 해당 패킷만을 다시 보낸다. 특정 패킷에 대해 ACK가 들어오면 그 패킷을 완료되었다고 기록한다. 송신자가 보낸 패킷들 중 아직 ACK되지 않은 패킷들 중 가장 번호가 작은 패킷이 ACK되면 window를 한 칸 이동시킨다.
수신자는 window와 버퍼를 가지고 있다. 어떤 패킷을 받았을 때 이 패킷이 순서(rcv_base)에 어긋난다면 일단 버퍼에 저장해 둔다. 그리고 순서에 맞는 패킷이 들어오면 버퍼에 있는 패킷들까지 모조리 ACK을 한꺼번에 보낸다. 그리고 ACK를 보낸 패킷 수만큼 window를 이동한다. 그리고 window의 범위보다 이전에 속하는 패킷이 도달한다면, ACK에 오류가 생겨 재전송된 패킷이라 간주하고 ACK만 보내고 별다른 처리는 하지 않는다.
위와 같은 예시를 보면, 송신자는 아직 2번 패킷에 대해 ACK가 오지 않았기 때문에 ACK3에 대해 window를 이동시키지 않는다. 대신 완료 처리 마킹은 해 둔다.
수신자의 경우 3, 4, 5번 패킷에 대해서 받는 족족 ACK를 보내긴 하지만 상위 레이어에 deliver 하지는 않는다. 순서를 지키면서 보낼 수 있을 때, 즉 2번 패킷이 들어올 때까지 버퍼에 저장해두고 있다가 한 번에 보낸다.
ACK2가 송신자에게 도착하면 2번 패킷이 완료처리됨과 동시에 window가 한 칸 이동할 것이고, 곧이어 6번 패킷을 보낼 것이다.
여기서 주의해야 하는 점이 있다.
window size는 반드시 (사용하는 sequence number / 2) 이하여야 한다.
그렇지 않으면 많이 loss 되었을 때 문제가 발생할 수 있다.
sequence number가 window size에 비해 충분히 크지 않아서 발생하는 문제의 예시이다. 수신자는 0, 1, 2번 패킷을 정상적으로 받고 자기의 window를 3칸 이동시켜 3, 0, 1번 패킷을 받을 준비를 하고 있다. (이 때 0, 1번 패킷은 sequence number만 0, 1번일 뿐 실질적으로는 5, 6번째 패킷이다)
그런데 ACK이 유실되어 송신자에게 도달하지 못했다. 따라서 송신자는 0번 패킷에 대해 timeout이 발생하고, 이를 retransmit 한다. 그런데 이 때 송신자가 보내는 0번 패킷과 수신자의 window에 있는 0번 패킷은 서로 다르다. 그러나 0번이 window에 있으므로 정상적으로 간주하게 된다.
이러한 문제는 window size를 줄임으로써 해결할 수 있다. 사용하는 sequence number(4)의 절반 이하인 2로 설정해 주면 전체 ACK가 유실되더라도 한 바퀴 돌아서 다시 0번으로 돌아오지 않으므로 이러한 문제를 해결할 수 있다.
