[네트워크] 10. Pipelined protocol (Go-back-N, selective repeat)

1. Pipelined protocol

지난 시간에 reliable transfer 에 대해 알아보았습니다. 이 방식은 unreliable한 네트워크 계층에서도 reliable할 수 있게 보장합니다.

기존에 살펴본 방법은 stop and wait 방식으로, 하나의 패킷을 보내고 정상적으로 ACK가 올 때 까지 기다렸습니다.

때문에 시간이 오래 걸리는 문제가 있었습니다.

 

하지만 만약 여러 패킷을 한번에 보내고 ACK도 한번에 받으면 어떻게 될까요?

컴퓨터 구조에서 말하는 파이프라이닝을 네트워크에도 적용시킬 수 있습니다.

Pipelined protocol에는 크게 두 가지 종류가 있습니다.

1. go-Back-N
2. selective repeat

 

파이프라이닝을 적용시키면 아래와 같은 효과를 볼 수 있습니다.

 

 

 

 

 

 

1.1 Go back N / Selective Repeat

자세히 들어가기 앞서 두 가지 protocol의 특징을 살펴보겠습니다.

 

Go-back-N

• sender는 N개의 패킷을 보냅니다.
• receiver는 패킷을 받고 ACK를 보냅니다. (누적 ACK로 하나만 보내기도 합니다.)
• sender는 가장 오래된 패킷에 대한 timer를 하나만 갖고 있고, 시간이 초과되면 ACK를 받지 못한 모든 패킷을 다시 전송합니다.

Selective Repeat

• Sender는 N개의 패킷을 보냅니다.
• receiver는 각각의 ACK를 보냅니다.
• Sender는 receiver가 못 받은 패킷만 전송합니다. 각각 패킷에 대한 timer를 갖고 있어, 시간이 초과되면 해당 패킷만 다시 보냅니다.

 

 

이제 두 프로토콜에 대해 자세히 알아보도록 하겠습니다.

 

 

1.2 Go-Back-N

 

• 초록색 : 이미 ACK 받음
• 노란색 : 보냈지만 ACK가 도착하지 않음 (inflight)
• 파란색 : 아직 안 보냄(보낼 수 있음)
• 흰색 : 아직 이용 불가

window size는 총 보낼수 있는 패킷 수 입니다.

노란색 중 가장 오래된 패킷 기준으로 timer가 세팅됩니다. 타이머가 만료되면, 해당 패킷부터 모든 상위의 seq 패킷을 재전송합니다.

 

패킷에 대한 Ack가 오면, 노란색이 초록색으로 되며 window가 이동합니다.

 

 

Sender의 FSM을 보도록 하겠습니다.

 

시작할 때 base와 nextseqnum은 1로 시작합니다.

1. window에 버퍼가 남아 있을 때 까지 패킷을 전송합니다. (만약 window의 처음이라면 timer를 설정합니다)
2. ACK를 받았을 때, 한번에 window를 이동하게 됩니다.(누적 ACK)
3. 만약 다 받았다면 timer를 멈추고, 다 받지 않았다면 timer를 세팅합니다.(여기서 구현에 따라 기존 타이머를 멈추고 재설정하거나, 기존 타이머에 이어서 설정할 수 있습니다.)
4.  잘못된 패킷이 들어오거나, 다 받았는데도 추가적으로 ACK가 들어온다면, timeout을 유도합니다.

 

 

다음은 Receiver의 FSM을 보도록 하겠습니다.

수신 쪽에는 버퍼가 없습니다. 따라서 패킷을 하나씩 받고 처리하게 됩니다.

 

처음 시작은 받아야 하는 expectedseqnum = 1로 설정하고 시작합니다.

미리 보낼 패킷을 만들고 시작합니다.

1. 패킷을 정상적으로 받았을 땐, 해당 패킷의 seqnum으로 ACK를 담은 패킷을 만들어 보냅니다. 또한 받아야 하는 seqnum을 증가시킵니다.
2. 받은 패킷이 깨지거나 받아야 하는 seq num이 아닌 경우, 기존에 만들어 놓은 패킷을 다시 보냅니다. ( 이렇게 어느 seqnum까지 받았는지 알려줍니다.)

 

receiver는 버퍼가 없기 때문에 반드시 패킷을 순서대로 받아야 합니다. 중간에 빠지게 될 경우, expected seq num이 아니면 계속 똑같은 ACK를 보내기 때문에 ACK가 중복된다는 점이 있습니다.

 

 

패킷 0,1,2,3을 보내고 2가 유실되는 상황을 가정해보겠습니다.

sender는 ACK1을 중복으로 보내게 될 것입니다.

그러다가 어느 순간 패킷2의 timer가 만료하게 되면, sender는 패킷2 부터 다시 보내게 됩니다.

이후에 receiver는 다시 순차적으로 ACK 2, 3, 4, 5를 보내게 됩니다.

 

결론

파이프라이닝이 되어서 효율은 높아졌지만, 아직도 더 좋은 방법이 있을 것 같습니다.

ACK가 중복이 된다는 점이 마음에 걸립니다. 더 좋은 방법이 없을까요?

 

 

 

 

1.3 Selective Repeat

이 방법은 resend를 하는 패킷을, 선택적으로 한다는 것입니다.

받은 패킷에 대해서는 기억을 해야 하기 때문에 버퍼가 필요합니다.

receiver는 안 받은 패킷에 대한 ACK만 보내게 됩니다. (이는 가장 오래된 것부터 보내게 됩니다.)

 

 

 

senderd의 입장에서 패킷 1, 2는 노란색으로 아직 ACK를 받지 못했습니다.

ACK를 받지 못한 패킷이 있으면, window는 진행하지 못합니다.

 

receiver는 패킷을 받고 ACK를 보내면 window를 진행합니다.

하지만 데이터를 못 받은 패킷이 있으면 window를 진행하지 못합니다.

 

Selective repeat의 프로세스는 아래와 같습니다.

Sender

1. 만약 버퍼가 남아 있으면, 패킷을 전송합니다.
2. 패킷에 대한 timeout이 발생하면, 다시 패킷을 보내고 timer를 설정합니다.
3. ACK를 받은 것에 대해 표시를 합니다.
4. 만약 가장 오래된 패킷의 ACK가 도착하면, window를 진행할 수 있을 때까지 진행합니다.

Receiver

1. 패킷을 받은 것에 대해 ACK를 보냅니다.
2. seqnum이 가장 작은 패킷을 받으면, 데이터를 아직 받지 않은 곳 까지 window를 이동합니다.(window 확보)
3. [base - N, base - 1] 범위의 패킷에 대해 ACK를 보내줍니다. 이로써 sender가 진도를 나갈 수 있게 window를 확보해줍니다.
4. 나머지 경우에 대해 무시합니다.

 

위 상황이 발생할 수 있는 상황 중 최악의 상황입니다.

sender는 첫 번째 패킷에 대한 ACK를 받지 못해서 진도를 나가지 못합니다.

반면 receiver는 모든 ACK를 보냈지만, sender가 진도를 나가지 못한 것 때문에 데이터를 못 받고 있는 상황입니다.

따라서 recevier는 구간 [base - N, base - 1] 의 패킷에 대한 ACK를 보내줘야 합니다.

 

 

앞선 예제와 똑같이 패킷 0,1,2,3을 보내는데 패킷 2가 유실될 경우, receiver는 패킷 0,1,3에 대한 ACK를 보냅니다.

이후 패킷 4, 5를 추가로 전송하고, ACK 4, 5또한 전달받습니다.

sender는 패킷2에 대한 ACK를 받지 못해 진도를 나가지 못하고 있다가, timeout이 걸려서 패킷 2를 재전송합니다.

receiver는 ACK2를 보내주고, 데이터를 전달하게 됩니다.

sender는 ACK2를 받았을 때, 이미 ACK 3, 4, 5도 받아놓은 상황이기 때문에 한번에 패킷 6까지 진도를 나갈 수 있습니다.

 

 

이렇게 좋아보이는 SR도 치명적인 문제가 있습니다.

 

 

1.4 Selective repeat dilemma

위와 같이, sequence number의 숫자가 충분히 크지 않은 상황이라면 어떻게 될까요?

 

(a)상황처럼 패킷 3이 유실되는 상황이라면 큰 문제가 발생하지 않습니다.

패킷 0이 도달할 때는 예전의 패킷 0과는 다르기 때문에 문제가 되지 않습니다.

 

하지만 (b)의 경우는 어떻게 될까요?

패킷 0, 1, 2를 보냈는데 receiver는 전부 다 받고 ACK를 보냅니다. 이 ACK들이 모두 유실이 되었습니다.

이후 sender는 timeout으로 기존에 보낸 패킷을 다시 보낼 것입니다.

이 때 다시 보내는 패킷 0은, receiver가 받아야 하는 패킷 0과는 다릅니다. receiver는 이미 받은 패킷이고, 새로운 패킷 0을 받아야 하는데, 이를 구분할 방법이 없는 것이죠.

 

이 문제를 해결하기 위해서는 seq num이 window size의 2배 이상이어야 합니다.

 

비슷하게 GBN의 경우, seq num이 window size보다 1 이상 크면 됩니다.

 

이 이유에 대해서는 잘 생각해 보시기 바랍니다. ^^7

 

 

 

본 글은 Computer networking : a top-down approach 라는 책을 통해 작성되었습니다.