[네트워크] Pipelined Protocol

[네트워크] RDT(Reliable Data Transfer)

 

지난 포스팅에서 RDT에 대한 내용을 다루었습니다. 이번 포스팅에서는 Pipelined Protocol을 다루겠습니다.

 

 

1. Pipelined Protocol

 Pipelined Protocol은 신뢰성 있는 데이터 전송 프로토콜인 RDT의 성능 한계를 개선한 프로토콜 입니다. 여기서 신뢰성이란, 애플리케이션 계층에서 내려온 메시지가 유실되지 않고 에러 없이 상대 애플리케이션 프로세스에 전달되는 것을 의미합니다.

 

출처 : Computer Networking _ A Top Down Approach

 RDT3.0 으로 데이터의 손실은 보장할 수 있게 되었지만, 하나의 패킷이 도착하고 ACK가 돌아올 때까지, 해당 소켓은 아무런 메시지를 보낼 수가 없다는 큰 단점이 있었습니다.  반면 Pipeline Protocol 방식은 한번에 많은 패킷을 보내서 각각의 패킷에 대한 ACK를 받는 방식입니다. 

 

신뢰성 있는  Pipeline Protocol을 구축하기 위한 방법에는 대표적으로 GBN(Go-Back-N) 방식과 Selective repeat 방식이 있습니다.

실제 TCP에서는 이 두 가지 방식을 적절히 섞은 방법을 사용합니다. 두 가지 방식에 대해 알아보겠습니다.

 

2. Go-Back-N

Go-Back-N 방식에서는 한번에 전송할 범위가 윈도우(Window)라는 개념으로 지정됩니다. 

출처 : Computer Networking _ A Top Down Approach

 

 윈도우 크기(window size)는 한 번에 보낼 수 있는 패킷의 양을 의미하고 N으로 나타냅니다. 만약 윈도우 크기가 3이면 ACK가 돌아올 때까지 3개까지의 메시지를 동시에 보낼 수 있습니다. 그래서 Go-Back-N 이름의 의미는 N부터 반복이라는 뜻을 가집니다.

 

GBN의 패킷은 그림에서 보이듯 네 가지로 분류할 수 있습니다.

 

(1) 이미 응답된 패킷 (Already ACK'd)

(2) 전송 후 응답을 아직 받지못한 패킷 (Sent, not yet ACK'd)

(3) 사용이 가능하지만 전송이 안된 패킷 (Usable, not yet sent)

(4) 사용이 불가능한 패킷 (Not usable)

 

 

 그리고 GBN 방식에서는 동시에 여러 패킷을 전송하므로 피드백 메시지 방식도 달라지게 됩니다. 

 

 우선 GBN은 window size 만큼 Feedback을 받지 않은채로 패킷을 전송합니다. 그리고 ACK n는 receiver가 n번 패킷까지 제대로 받았음을 알리는 피드백이 됩니다. ACK 5은 5번 패킷을 받았다는 뜻이 아니라, 이전 패킷부터 시퀀스 넘버(sequence number)가 5번인 패킷까지 모두 정상적으로 받았다는 것을 의미합니다. 지금까지 누적(cumulative)된 패킷 모두에 대해 피드백을 보내는 것입니다. 그러면 sender는 ACK를 확인하고 6번 패킷부터 데이터를 보내게 됩니다.

 

 

이렇게 ACK를 변경하는 고려해야할 문제가 한 가지 있습니다.

 

 만약 0, 1, 2, 3, 4, 5번 패킷을 보내는데 3번 패킷이 유실된 상황이 생겼습니다. 그러면  ACK 0, ACK 1, ACK 2까지 전송되고 나서 3번 패킷이 유실되었으므로 다음 피드백 메시지는 ACK 2, ACK 2, ACK 2이 돌아오게 됩니다. 메시지를 보면, 3번 패킷이 유실된 것이 확실합니다. 하지만, 4번, 5번 패킷도 유실된 것인지 아닌지 알 수가 없습니다.

 

 그래서 만약 3번 패킷이 유실되어 timeout이 발생하면, 4, 5번 패킷도 모두 재전송하게 됩니다. 

 

이를  timeout(n)이라고 하며, n번 패킷이 유실되었을 경우, N번 패킷부터 윈도우 내에서 그 다음에 있는 패킷을 모두 재전송하는 것입니다.

출처 : Computer Networking _ A Top Down Approach

 

위 그림은 윈도우 사이즈가 4인 GBN 프로토콜을 나타냅니다.

 

 위 상황은 2번 패킷이 유실된 상태로 3번 패킷을 받았기 때문에 3번 패킷을 버리고 ACK 1을 통해 1번패킷 까지 정상적으로 수신하였다고 Feedback 하는 상태입니다. 3, 4, 5번 패킷은 정상 전송되었으므로, 재전송된 복제(duplicate) 패킷은 버려지게 됩니다.

 

ACK 0, ACK 1을 통해 정상적으로 수신했다는 Feedback을 받아 순서대로 4, 5 패킷을 전송하지만, 패킷 2에 timeout이 발생하여 sender는 다시 2번 패킷부터 window size인 4만큼 전송해야합니다. 

 

이렇듯 Go-Back-N 방식은 패킷이 유실되거나 에러가 발생하면 window size(N) 만큼 돌아와서 다시 패킷을 전송하는 것입니다.

 

그리고 윈도우에 들어있는 데이터는 버퍼에 저장을 해야합니다. 위 그림에서는 윈도우 밖(0, 1)의 패킷은 ACK가 왔으므로 전송이 완료되었다는 것임으로 버퍼에 저장하지 않습니다. 하지만 윈도우 내(2, 3, 4,5 )의 패킷은 ACK가 오지 않아 제대로 전송되었는지 알 수 없기 때문에 버퍼에 저장해야 합니다.

 

 

 

 Go-Back-N의 문제점은 하나의 패킷만 에러나 유실이 발생해도 window size 만큼의 패킷을 재전송된다는 점입니다. 실제 window size는 4보다는 훨씬 크기 때문에, 실패할 경우 윈도우 내에 있는 모든 패킷을 재전송해야만 하는 오버헤드가 큽니다. 이런 문제를 해결한 것이 Selective Repeat입니다. 

 

 

 

 

3. Selective Repeat

 Selective Repeat 유실된 패킷만 재전송하는 것을 말합니다.

 

 GBN처럼 누적 방식으로 보내는 것이 아니라, Selective Repeat에서는 패킷을 받을 때마다 각각 ACK를 전송시켜줍니다. 

 

 그래서 GBN 의 ACK n 은 n번까지 패킷을 받았다는 의미를 가졌지만, Selective Repeat에서는 ACK n이 n번 패킷만 받았다는 것을 의미합니다. 예를 들어 3번 패킷을 받으면 ACK 3을 보내는데, ACK 3은 3번까지 모두 받았다는 것이 아니라 3번 패킷을 받았다는 것을 의미합니다.

 

 

위 그림처럼 SR방식에서는 도착한 패킷의 순서와 상관없이 확인 응답을 하게 됩니다. 여기서 패킷을 순서대로 상위 계층에 전달해주어야하는데,  만약 패킷이 유실되었을 때, 그 패킷이 도착할 때까지 다음 순서의 패킷을 버퍼에 임시로 저장하게 됩니다. 

 

 위의 그림에서는 ACK 0과 ACK 1을 받았고 2번 패킷을 아직 받지 못했습니다. 그래서 3, 4, 5번 패킷을 버퍼에 저장하고, 2번 패킷을 기다리게 됩니다. 그러다 2번 패킷에 timeout이 일어나서 Sender가 2번 패킷을 재전송하게 되면 2, 3, 4, 5 패킷을 한번에 상위 계층으로 보낼 수 있게 됩니다. 그리고 ACK 3, 4, 5는 이미 받았기 때문에 window는 6, 7, 8, 9로 이동합니다.

 

 

 

GBN과 SR 방식에서의 딜레마

 Go-Back-N, Selective repeat과 같은 파이프라인 프로토콜에는 시퀀스 번호(Seq #)가 무한하지 않다는 문제점이 있습니다.

 시퀀스 번호를 전달하기 위해서 세그먼트 헤더에 시퀀스 정보를 넣어야 하는데, 보다 큰 수를 지원하려면 많은 비트가 필요해져 헤더 또한 길이가 길어지게 됩니다. 그래서 window size가 N이라면 시퀀스 번호는 N*2 정도의 적당한 값으로 설정합니다.

 

 

 

 

지금까지 Pipelined Protocol의 GBN과 SR 기법에 대해 알아보았습니다. 다음 포스팅에서는 TCP에 대해서 알아보겠습니다.

 

 

 

 

참고자료

[컴퓨터 네트워크 - 한양대학교 이석복 교수님]
http://www.kocw.net/home/cview.do?cid=6166c077e545b736

https://the-square-of-y.tistory.com/215

https://the-brain-of-sic2.tistory.com/52

https://dev-nicitis.tistory.com/26

Computer Networking _ A Top Down Approach, 7th