[컴퓨터 네트워크]-Transport layer_Principles of reliable data transfer(2): Go-Back-N, Selective repeat

 지난 글까지는, TCP를 위한 사전지식을 위해서, stop and wait 프로토콜인 rdt(reliable data transmission)에 대해서 정리해봤다. 이번 글에서는 추가적으로 Go-Back-N 방식과 Selective repeat에 대해 정리해보려고 한다.

---

1. Go-Back-N

 먼저, Go-Back-N 방식은, rdt 3.0에서 적용한 pipelining을 구현한 첫 번째 접근이다. 이를 sender 측면과 receiver 측면에서 알아보자.

se

-Sender

 Go-Back-N 방법에서는, multiple packet을 보내야되기 때문에, window라는 개념이 처음 등장했다. window는 다음 그림과 같이 생겼다.

Go-Back-N window

 패킷의 상태창이라고 생각하면 편하다. 위 그림에 대해서 설명해보면,

• 초록색: 이미 전송되고 ACK 까지 받은 패킷들
• 노란색: 패킷은 전송된 상태지만, ACK를 보내지 않은 상태
• 파란색: 전송가능한 패킷이지만, 아직 전송하지 않은 상태
• 하얀색: 쓸 수 없는 부분

 즉, sender의 window는 sender가 보낼 수 있는 패킷의 용량이라고 생각하면 된다. 이 때, window 크기는 N으로 일정하고, 옆으로(그림 상에서는 오른쪽으로) 이동하면서 상태를 변화시키는 것이다.

 

 이 때, 저 패킷들을 저번에 정리했던 sequence 번호인 0번과 1번으로 충분할까? 아니다. 이 때는 sequence 번호가 더 많이 필요하다. 정확히는 필요한 sequence 번호 수를 k라고 하면, k=log2(N)개가 필요하다.

 

 초록색 부분은 이미 전송과 ACK도 잘 받은 상태이다. 즉, ACK를 받았기 때문에 window가 오른쪽으로 slide한 것이라고 보면 된다. 

 

 그 다음 노란색 부분은 ACK를 기다리고 있는 상태이다. 노란색 앞에서부터 차례대로 1~8이라고 하겠다. 1~8 순서대로 한 번에 ACK가 왔다면 window도 한 번에 8칸을 오른쪽으로 slide할 수 있다. 그렇지만, 2,3,4번 ACK가 도착했는데, 1번의 ACK가 도착하지 않았다면, window는 slide할 수 없다. 그리고 나서, 1번이 도착하면 한 번의 4개 slide를 할 수 있다.

 

 파란색 부분은, 이제 원할 때 전송을 할 수 있는 상태의 패킷을 나타낸 것이다. window 안에 포함돼 있기 때문에, 원할 때, 데이터를 전송하고 노란색으로, 즉 ACK 대기상태로 변경할 수 있다.

 

 흰 색 부분은, 노란색의 ACK가 들어오고 slide한 수 만큼 파란색으로 바뀐다. 즉, window size안에 포함되고 전송 대기 상태로 바뀔 수 있다는 것이다.

 

 위와 같은 방식으로 sender에서 작동한다. sender에서는 cumulative ACK 방식을 사용한다. 이 cumulative ACK는 누적 ACK 방식인데, 말 그대로, 수신자는 연속해서 1234번을 받았다면 가장 마지막에 받은 패킷 번호 4번에 대한 ACK만 보내는 것이다. 그럼 그 4번 이전 것은 잘 받았다고 인지하는 것이다. 만약 2번을 못받았다면 ACK 1번만 보내게 될 것이다.

 

 Go-Back-N은 pipelining 방식이기 때문에 in-flight상태이고, timer도 작동한다. 이 타이머는 각 패킷마다 한 개씩 있는 것이 아니라, 전송하고 ACK를 받지 못한 가장 오래된 패킷에 대한 타이머다. 즉, 위 그림에서는 노란색 1번에 대한 timer만 작동하는 것이다. 만약, timeout이 일어나게 된다면, sender는 1번부터 8번까지 다시 재전송을 한다.

 

-Receiver

그렇다면 receiver 측면에서는 어떨까? receiver도 sender와 동일하게 window가 필요하다. receiver의 window를 살펴보자.

 

 sender보다는 window가 간단하다. 그림에 대해서 설명해보자면,

• 초록색: 패킷을 받고 ACK까지 전송이 된 상태
• 분홍색: 받았지만 ACK를 전송하지 않은 상태
• 회색: 못 받은 상태

 위에서 설명했듯이 cumulative ACK 방식을 이용하기 때문에, receiver는 잘 도착한 마지막 패킷에 대한 ACK를 전송하고 그 다음 순서를 가리키는 rcv_base만 존재하면 된다. 

 

 만약, 위 상황처럼 도착했지만 ACK전송을 안 한 패킷(분홍색)과 ACK를 보낸 패킷(초록색) 사이에 도착하지 않은 패킷이 있다면, 분홍색에 대한 ACK를 보내지 않고, 기다리게 된다. 그리고 분홍색은 buffer에 저장되거나, 버리게 할 수 있게 둘 중 하나의 방식으로 구현할 수 있다.

 

 이제, 실제로 어떻게 적용되는지 살펴보자.

 

 위 그림과 같이 작동하게 되는데, 먼저 조건은 다음과 같다.

• sender의 window 크기는 4
• 패킷 번호는 순서대로 0~8

 그리고 다음과 같은 순서로 진행된다.

1. sender는 4개 만큼의 패킷을 보내고, ACK를 기다린다.
2. 그렇지만 중간에 모종의 이유로 pkt2번이 손실됐고, receiver는 0,1,3번을 받았지만 연속된 패킷을 받지 못했기 때문에 ACK 1번을 보낸다.
3. sender는 1번까지 ACK를 받았기 때문에 0번에 대한 timer를 끝내고 2번에 대한 timer를 시작한다. 그리고 윈도우를 2칸 오른쪽으로 slide한다.
4. sender는 그 후, 4-5번의 연속된 패킷을 보낸다.
5. receiver는 2번을 받지 못한 상태이기 때문에 4,5,번에 대한 패킷은 폐기하거나 buffer에 저장한다.
6. 2번에 대한 timer가 timeout되고, sender는 2번부터 5번까지 패킷을 재전송한다.

---

2. Selective repeat

 이제는 selective repeat 방식에 대해서 알아보자. Selective repeat 방식에 대해서 간단히 설명하면, 개별 패킷에 대한 ACK를 전송하는 것이다. Go-Back-N의 방식은 cumluative ACK 방식을 사용해 마지막으로 잘 도착한 패킷 번호에 대한 ACK를 보냈다면, Selective repeat 방식은 개별 ACK를 보내는 방식인 것이다.

 

 동일하게 Sender 측면과 receiver 측면에서 살펴보자.

 

-Sender

 

 Go-Back-N 방식과 동일하게 sender는 window를 가지고 있다. 그렇지만, 차이점은  다음과 같다.

• window 사이즈 내에, 초록색, 노란색, 파란색이 같이 존재한다는 것이다. 이 이유는 개별 ACK를 사용하기 때문에, 먼저 전송됐더라도, 중간에 손실되거나 ACK가 느리게 전송됐다면, 노란색이고, 그 다음 것이 초록색이 될 수도 있다는 것이다.
• 위 그림과 같이 send_base부터 연속적으로 ACK가 도착하지 못했다면, window를 slide하지 못하고, 각각의 패킷에 대한 타이머를 가지고 있는다.

그렇다면 Receiver는 어떨까?

 

-Receiver

 

 

 Receiver는 Go-Back-N 방식의 window와 다르다는 것을 한 눈에 볼 수 있다. 차이점은 다음과 같다.

• window size가 존재한다(receiver window size=sender window size)
• 파란색: window size가 존재해 패킷을 받아들일 수 있는 추가 공간이 존재한다
• 분홍색: 이전에 받지 못한 패킷이 있는데, ACK까지 전송된 상태

 위 그림을 토대로 설명하면, rcv_base가 가리키고 있는 패킷을 받지 못했지만 그 다음 패킷은 받아서 ack가 전송된 상태이다. 이를 분홍색으로 표현했고, 파란색은 추가적으로 받아들일 수 있는 패킷 수이다.

 

  ACK를 개별적으로 보내다 보니, 순서가 지켜지지 않을 수도 있다. 따라서, 위 그림과 같이 분홍색의 상태로 두고, 만약 그 전 패킷을 받고, ACK를 전송했다면, 그 뒤에 순서대로 데이터를 합치고, 상위 application 계층으로 전달한 뒤, 그 수만큼 window를 slide할 수 있게 된다.

+)이 때, 파란색이 window size 내에 없다면, receiver는 sender에게 데이터 전송을 잠깐 멈춰 달라고 요청할 수 있다.

 

 여기서 발생한 궁금한 점은, Go-Back-N 방식도 상황에 따라 buffer 방식으로 구현할 수 있다했는데, Selective repeat과의 차이점은 무엇일까? 가장 중요한 점은 cumulative ACK와 개별 ACK의 차이라는 것이다. 즉, Selective repeat는 개별 ACK를 통해 순서를 나타내는데, cumulative ACK는 순서를 나타내지 않고 단순 임시 저장용으로 buffer를 사용한다는 것이다.

+) Go-Back-N의 기본 방식은 discard이다. buffer 방식은 구현도 복잡하다..

 

2.1 Sender와 Receiver가 하는 일

-Sender

• window 내에 패킷을 추가로 만들 수 있는 공간(=파란색)이 존재하면, data를 application으로부터 전달받아 패킷을 만들어 바로 전송한다
• 개별 패킷마다 timer를 만들어 timeout된다면 재전송한다
• sendbase~sendbase+windowsize-1 사이의 ACK이 도착하면 잘 도착했다고 표시(=초록색)하고 그 전까지 연속적으로 잘 받았다면 그 크기만큼 window를 오른쪽으로 slide한다.

-Receiver

• rcvbase~rcvbase+windowsize-1 사이의 packet이 도착하면 해당하는 ACK를 보내고
  • 순서가 맞지 않는다면, buffer에 저장해놨다가 나중에 순서가 맞으면 재조립해서 application에 보낸다
• 만약, sender와 receiver의 싱크가 맞지 않아(sender가 ACK를 아직 못받은 상태, ACK가 손실됐거나 느리게 가고 있는 상태), rcvbase-windowsize~rcvbase-1 사이의 패킷을 받는다면, 이미 처리된 패킷을 받은 것으로 동일하게 ACK를 보낸다.

 

 이제 실제로 어떻게 적용되는지 알아보자.

 

 위 그림의 조건을 먼저 살펴보면 다음과 같다.

• sender의 window 크기는 N
• packet은 0번부터 전송된다고 가정

위 그림의 순서를 설명해보면, 다음과 같이 진행된다.

1. sender가 0~3까지의 패킷을 보내고 각 패킷에 대한 timer를 작동시킨다.
2. sedner가 보낸 pkt2번이 중간에 유실되어 receiver에게는 0,1,3의 패킷만 보낸다.
3. receiver window 범위 내 패킷이므로, ack0,1,3을 보내고, 3은 연속된 패킷이 아니기 때문에 버퍼에 저장해 놓는다.(이 때, rcv_base는 2를 가리키고 있다.)
4. receiver는 01에 대한 ACK를 받았기 때문에 window를 오른쪽으로 2칸 slide한 뒤 4,5번을 보낸다.
5. ack3은 받았다고 기억해 두고, pkt2의 timer가 timeout이 된다.
6. pkt2만 재전송한다.
7. receiver window는 2에서 멈춘 상태로, pkt2가 온전히 도착하면, 2에 대한 ACK를 보내고, 2,3,만큼 application 계층에 전달하고, window를 오른쪽으로 slide 해준다.

2.2 Selective repeat: Dilemma

 이러한 selective repeat 방법에도 딜레마가 존재한다. 다음 그림을 살펴보자.

정상적으로 Selective repeat이 진행되는 그림

위 그림을 살펴보면, 다음과 같은 순서로 Selective repeat이 정상적으로 진행된다.

1. sender가 패킷 0,1,2의 number를 가진 패킷을 동시에 보낸다.
2. receiver는 차례대로 0,1을 받았지만, 2번의 패킷을 받지 못해 sender에게 ACK를 보내지 못한다.
3. sender는 패킷3번을 보낼 차례지만 2에 대한 ACK가 도착하지 않았기 때문에
4. 선택적으로 패킷 2번을 재전송한다. 
5. 그 뒤 다시 패킷을 순서대로 전송한다.

 

그런데 이제 다음 그림을 살펴보자.

Selective Repeat의 딜레마

위 그림을 살펴보면,

1. sender가 정상적인 Selective repeat 방식과 동일하게 0,1,2의 패킷을 동시에 보낸다.
2. 이때 앞선 상황과는 다르게, receiver는 0,1,2 패킷을 모두 받았지만, 해당하는 모든 ACK를 손실한다.
3. ACK를 받지 못한 sender는 timeout된 후, 맨 처음의 0번 패킷을 재전송하게 된다.
4. receiver는 이미 0,1,2에 대한 ACK를 전송하고 window를 slide한 상태인데, 엉뚱한 0번 패킷을 받게 된다.

이런 딜레마를 해결하기 위한 방법은 뭐가 있을까? 다음과 같은 상황을 가정해보자.

• sequence # : 0,1,2,3(4개)
• window size = 3

위 그림들과 같은 상황이고, 이렇게 되면 딜레마가 발생하게 된다.

 

이 때, sequence number, 즉 서로 다른 sequence number가 window size보다 크게 되면, window size의 2배가 되게 된다면, 딜레마가 해결될 것이다.

 

예를 들어, sequence number가 0,1,2,3,4,5 까지 존재하게 된다면, sender 측 window가 slide되더라도 딜레마가 4번에 대한 패킷이 전송되어야 될 차례이기 때문에, 딜레마가 발생하지 않게 된다.

---