Pipelining: increased utilization

파이프라인 프로토콜을 통해 많은 양의 패킷을 주고 받을 수 있고 패킷 낭비를 줄일 수 있지만, 수신자 입장에서 어떤 패킷을 먼저 처리하고 피드백을 줘야할지 혼란스러울 수 있다.

이를 위해 등장한 프로토콜로 go-Back-N, Selective Repeat 프로토콜이 있다.

Go-Back-N

일정 크기 (Window Size)만큼의 패킷을 한번에 보낸다.
이때 각각의 패킷은 타이머를 갖고 있다.
Window Size 안의 패킷 중 하나가 Time-out 된다면
그 패킷부터 마지막 패킷까지를 전부 재전송한다.

Window Size : 한번에 얼마 만큼의 패킷을 보낼지 판단하는 기준이다.

한 뭉치의 패킷을 보내면 그 다음부터 또 한 뭉치를 보내는 동작이 마치 창문을 좌우로 움직이는 행위와 비슷해서 Window 라는 이름이 붙었다. (Sliding Window 알고리즘과 유래가 비슷하다.)

한번에 많은 양의 패킷을 보내므로 ACK 피드백의 의미 역시 달라진다.

Go-Back-N에서 사용하는 ACK은 CUmulative ACK 즉, 누적된 만큼의 ACK이다.
만약 ACK11이라면 11번까지의 패킷을 모두 잘 받았다는 의미가 된다.

Go-Back-N in action

Go-Back-N 프토토콜은 다음과 같이 동작한다.

1. 수신자는 정상적으로 받지 못한 패킷이 있으면 그 패킷이 올 때까지 그 직전 패킷의 ACK을 보낸다. (다른 패킷이 아무리 많이 들어와도 상관없이)
   즉, ACK 사이에 갭이 발생하는 것을 용납하지 않는다.
   이러한 성질 덕분에 Cumulative ACK (누적된 ACK) 이라고 한다.
   예를 들어 패킷 1,2,3,4,5를 전송했는데 수신자가 1,2,4,5를 받았다면, 3이 들어올 때 까지 수신자는 ACK 1,2,2,2를 보낸다. (이때 패킷 4,5는 버린다.)
   전송자는 ACK2가 중복으로 들어오는 것을 보고 패킷 3을 재전송한다.

   만약 ACK이 유실되었을 경우에도 대응이 가능하다. 전송자 입장에서 ACK 1,2,3이 유실되어 오지 않고 ACK4만 오더라도, 수신자가 패킷 1,2,3,4를 정상적으로 받았다고 판단할 수 있다.

2. 전송자는 전송한 패킷 중에서 ACK 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.
   만약 해당 타이머가 만료될 때 까지 ACK이 오지 않으면 Window 내의 unAck된 모든 패킷을 재전송한다.
   만약 해당 타이머가 만료되기 전에 ACK이 오면, 그 다음 패킷 중 ACK 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.

문제점

Go-Back-N은 문제가 된 패킷 이후의 패킷을 전부 재전송한다. 즉, 정상적으로 전송되었음에도 불구하고 자기 앞에 있는 패킷이 유실되었다는 이유만으로 전부 재전송된다는 것이다.

당연히 문제가 되는 패킷만 재전송하면 성능 낭비를 줄일 수 있을 것이다.

이렇게 해서 등장한 방식이 Selective Repeat이다.

Selective Repeat

• 수신자는 정상적으로 도착한 패킷 각각에 대해 ACK을 보낸다.
  • 이때 상위 계층으로 패킷을 순서대로 올려줘야하므로 패킷이 유실되었다면 그 패킷이 도착할 때까지 그 다음 순서의 패킷들을 임시로 버퍼에 저장한다.
• 전송자는 ACK을 받지 못한 패킷 즉, 유실된 패킷만 재전송한다.

Selective Repeat in action

Selective Repeat은 다음과 같이 동작한다.

Window size가 4이고, 2번 패킷이 유실된 상황이다.

1. 전송자가 0번 패킷을 보내고, 정상적으로 받아서 위로 올려준 후 ACK0을 반환한다.
2. 전송자가 1번 패킷을 보내고, 정상적으로 받아서 위로 올려준 후 ACK1을 반환한다.
3. 전송자가 2번 패킷을 보냈지만 유실되었다.
4. 전송자가 3번 패킷을 보내고, 정상적으로 받아서 ACK3을 반환한다. 다만 2번 패킷이 오지 않았으므로 버퍼에 저장한다. 버퍼 : 3
5. 전송자는 ACK0을 받아서 Window를 한칸 이동시키고 4번 패킷을 보낸다. 수신자는 정상적으로 받아서 ACK4를 반환한다. 다만 2번 패킷이 오지 않았으므로 버퍼에 저장한다. 버퍼 : 3,4
6. 전송자는 ACK1을 받아서 Window를 한칸 이동시키고 5번 패킷을 보낸다. 수신자는 정상적으로 받아서 ACK5를 반환한다. 다만 2번 패킷이 오지 않았으므로 버퍼에 저장한다. 버퍼 : 3,4,5
7. 2번 패킷의 타이머가 Time-out 되었으므로 전송자는 2번 패킷을 재전송한다. 수신자는 정상적으로 받아서 ACK2를 반환한다. 또한 2번 패킷을 받았으므로 버퍼에 저장되어어있던 패킷들과 함께 2,3,4,5 패킷을 위로 올려보낸다.

Selective Repeat Dilemma

하지만 Selective Repeat는 앞서 언급한 시퀀스 넘버의 한정된 크기로 인해 딜레마가 발생한다.

Window size는 3이고, 시퀀스 넘버로 0,1,2,3 만을 사용한다고 가정해보자.

한정된 시퀀스 넘버 + ACK 손실

0번, 1번, 2번 패킷을 모두 정상적으로 받고 ACK 0, 1, 2를 반환했는데 이 ACK들이 모두 유실되었다면?

전송자는 아무런 ACK을 받지 못했으므로 다시 0번 패킷부터 재전송한다. 하지만 수신자는 이미 0번, 1번, 2번 패킷을 모두 받아 위로 올리고 자신의 Window를 옮겨놓은 상태이다.

이렇게되면 수신자 입장에서 0번으로 들어온 패킷이 기존에 들어온 패킷을 재전송한 것인지, 완전 새로운 패킷을 전송한 것인지를 알 수가 없다.

한정된 시퀀스 넘버 + 패킷 유실

0번, 1번, 2번 패킷이 모두 정상적으로 전송되었고 ACK 0, 1, 2 역시 정상적으로 반환되었다.

전송자는 먼저 ACK 0을 받고 Window를 한칸 이동시켜서 3번 패킷을 보낸다. 그런데 이 3번 패킷이 유실되었다. 하지만 전송자는 이 사실을 모른채 ACK1에 맞춰 Window를 이동시키고 다시 0번 패킷을 보낸다.

수신자 입장에서는 자신의 0번 패킷에 대한 ACK이 제대로 전송되었는지 알지 못한다. 따라서 그 상태에서 다시 0번 패킷을 수신하게 되면 이 0번 패킷이 완전 새로운 패킷인지 아니면 재전송된 패킷인지 알 수 없어 문제가 발생한다.

해결책

단순히 시퀀스 넘버를 늘리면 되는 문제 아닌가? 싶을 수 있지만, 용량을 최소화해야하므로 무작정 늘려서는 안된다.

다양한 경우의 수를 계산해봤을 때

시퀀스 넘버의 가장 최적 크기는 Window size * 2 이다.

따라서 Window size의 2배 만큼 시퀀스 넘버를 설정하면 Selective Repeat의 딜레마에 대응할 수 있다.