[네트워크] GBN(Go-back-N), SR(Selective Repeat) - Pipelined Protocols
Pipelined Protocols
앞서 서술하였듯이, RDT 2.1 모델부터는 송신자가 하나의 packet을 보내고나면 수신자의 응답을 기다리는 "Stop and Wait" 방식을 사용한다고 하였다.
https://oneonlee.tistory.com/m/111
[네트워크] Reliable Data Transfer의 원리와 RDT 모델 알고리즘
Principles of RDT(Reliable Data Transfer) Reliable Data Transfer 신뢰성 있는 데이터 교환(이하 RDT)은 한마디로 "송/수신하는 데이터가 오류없이 온전히 전송되는 것" 이다. Transport Layer 에서는 신뢰성 있는 데이
oneonlee.tistory.com
하지만 이 방법은 ACK가 올 때까지 송신자가 계속해서 놀고 있기 때문에 굉장히 비효율적인 방법이다.
따라서, 한번에 하나의 패킷만 보내는 것이 아니라 여러 패킷을 pipelining하여 처리하는 방식을 살펴볼 것이다.
대표적인 Pipelined Protocol으로는 GBN(Go-Back-N)과 SR(Selective Repeate) 방식이 있다.
GBN(Go-back-N)
Go-back-N 방식은 수신자 측에서 받지 못한 패킷이 있다면, 송신자가 해당 패킷부터 순서대로 다시 재전송 하는 방식이다.
- (1) 수신자 측은 정상적으로 받지 못한 패킷이 있을 경우, 해당 패킷이 올 때까지 다른 패킷들을 받더라도, 받지 못한 패킷의 직전 패킷에 대한 ACK를 보낸다.
- 수신자는 받은 ACK의 순서가 뒤섞이는 것을 허용하지 않는다.
- 이러한 성질 때문에 cumulative ACK(연속적인 ACK)이라고도 한다.
- 예를 들어 패킷 1,2,3,4,5를 전송했는데, 수신자 측에서 1,2,4,5를 받았다면, 수신자 측은 ACK 1,2,2,2를 보낸다.
- 송신자 입장에서 ACK 1,2,3이 안오고 ACK 4만 오더라도 수신자가 패킷 1,2,3,4를 정상적으로 받았다는 것을 알 수 있다. (ACK가 오다가 손실된 경우)
- 수신자는 받은 ACK의 순서가 뒤섞이는 것을 허용하지 않는다.
- (2) 송신자는 전송한 패킷 중, ACK 되지 않은 가장 최신의 패킷에 대해 하나의 타이머를 계산한다.
- 만약 해당 타이머가 만료될 때까지 ACK가 오지 않으면, window 내의 unack된 모든 패킷을 재전송한다.
- 만약 해당 타이머가 만료되기 전에 ACK가 온다면, 다음 ACK 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.
- (3) 구조가 간단하고 구현이 단순하며, 따로 패킷을 보관할 버퍼가 필요 없다.
- 올바른 패킷이 오면 삼키고, 틀린 패킷이 오면 뱉는 구조이기 때문이다.
- (4) 송신자의 Window Size는 사용되는 sequence number보다 무조건 커야한다.
- N = (2^k)-1
- 만약 Window size가 같거나 작으면, 수신자가 오해할 수 있는 상황이 생긴다. (ACK가 모두 소실된 경우)
SR(Selective Repeat)
Selective Repeat 방식은 송신자 측에서 받은 각각의 패킷들에 대해 ACK을 보내는 방식이다.
- (1) 송신자 측은 ACK가 순서대로 오든 말든, 그냥 받은 패킷에 대한 ACK을 보낸다.
- 예를 들어 패킷 1,2,3,4,5를 전송했는데 송신자 측에서 1,2,4,5가 왔다면, 송신자 측은 ACK 1,2,4,5를 보낸다.
- (2) 송신자는 ACK을 받지 못한 모든 패킷에 대해 타이머를 각각 계산한다.
- 만약 각각의 타이머가 만료될 때까지 ACK가 안오면, 각각 패킷을 재전송한다.
- (3) 따로 받은 패킷을 보관할 버퍼가 필요하다.
- 올바르지 않은 패킷이 와도 일단 저장해놓고, 나중에 부족한 부분이 채워지면 함께 삼키는 구조이기 때문이다.
- (4) 사용되는 sequence number는 송신자의 Window Size와 송신자의 Widow Size 크기의 합보다 무조건 크거나 같야한다.
- Max allowable window size N을 (2^k)-1이 아니라, (2^k)/2 = 2^(k-1)로 해야 한다. (half the seq# space)
- 만약 sequence number의 크기가 더 작다면, 송신자가 오해할 수 있는 상황이 생긴다.
시각화 자료
참고 자료
- Computer Networking: A Top Down Approach 6th edition - Jim Kurose, Keith Ross Addison-Wesley March 2012
- https://ddongwon.tistory.com/m/81
- https://m.blog.naver.com/mayooyos/220987008864