(컴퓨터 네트워크) 5. Pipeline protocol

해당 내용은 kocw 한양대학교 컴퓨터 네트워크 강의를 정리한 내용입니다.

강의 링크 - http://www.kocw.net/home/search/kemView.do?kemId=1169634&ar=relateCourse

 

1. Intro

지난시간에는 reliable data transfer를 하기 위한 기본 원리에 대해서 이야기 하였습니다.

unreliable한 channel에서는 packet error와 packet loss가 발생할 수 있는데, 아래 해결책으로 해결할 수 있습니다.

- packet error : error detection, feedback, retransmission, sequence number

- packet loss : timer

 

그래서 이렇게 보내는데 성능이 어느정도 될 것인가를 계산해 보면 설능이 좋지 않습니다.

 

성능 지표 (utilization) : [sender가 network를 사용하는 시간 / 전체 시간] 의 값으로 나타낼 수 있습니다.

해당 값은 클수록 좋습니다.

 

저희가 지난시간에 생각한 것은 한번에 하나의 패킷만 보내기 때문에 ACK가 돌아올 때 까지 sender는 하는 일 없이 계속 대기하게 됩니다. 그래서 utilization값은 작을 수 밖에 없습니다.

 

그래서 우리는 pipeline 방식으로 한 번에 많은 패킷을 쏟아붓고, 해당 패킷에 대해서 ACK를 받아야 utilization이 올라가게 됩니다.

 

그래서 오늘은 이러한 pipeline 방식의 구현을 위한 go-back-N 방식과, selective repeat 방식을 배워볼 것입니다.

 

2. Go Back N 방식

이제는 한 번에 많은 packet을 보낼 것입니다.

그런데 한 번에 얼마나 많은 packet을 보낼 것이가에 대해서 생각해 보아야 합니다.

무작정 보낼 packet을 다 보내는 것이 아니라, 일정 양 만큼만 보내야 합니다. 그래서 우리는 window 라는 개념을 도입할 것입니다.

window : 한 번에 얼만큼의 packet을 보낼 것인가의 값을 가지고 있다.

 

window size만큼 feedback을 받지 않고 한번에 packet을 보낼 것입니다.

 

만약에 보내야할 packet이 0 ~ 14번 까지 있을 때

window size가 4라면 0, 1, 2, 3번 packet은 한 번에 보냅니다.

 

응답 방식은 cumulative ACK를 사용하는데, ACK11이라고 받으면 11번 packet까지 완벽하게 잘 받았다 라는 뜻입니다.

그래서 이제 12번 packet을 보내면 된다는 뜻 입니다.

 

sender는 보내는 각각의 packet에 timer가 있고, 하나의 packet의 타이머가 켜지면 window에 있는 모든 packet을 다시 보냅니다.

(1번 packet의 timer가 켜지면, 0, 1, 2, 3번 packet모두 다시 보냅니다.)

 

receiver의 역할은 별달리 하는것이 없고, 버퍼도 없고, 그냥 자신이 받아야 할 sequence number의 packet만 계속해서 기다립니다.

receiver는 자신이 받아야 할 sequence number의 packet이 안온다면 무조건 버립니다.

receiver가 packet0번 받으면 ACK0을 주고 1을 기다린다.

만약에 packet2번이 먼저 오게 된다면 버리고 ACK0을 보낸다 (0번까지 제대로 받았다)
packet1을 받으면 1을 기다렸으니 ACK1을 보내고, packet2번이 아닌 다른 packet이 오면 모두 버리고 ACK1을 보낸다.

 

다시 보내야할 packet이 0 ~ 14까지 있고, window size가 4일 때

 

0, 1, 2, 3 packet을 보내고, receiver가 0번 packet을 받고, ACK0을 주면

sender는 ACK0이 왔으니 packet4번을 보냅니다.

receiver가 1번 packet을 받았으면 ACK1을 보내고

sender는 ACK1번을 받았으니 packet5번을 보냅니다.

......

이런식으로 진행하다가

6번 packet이 유실되어서 receiver가 받지 못했다면

window는 6, 7, 8, 9를 가리키고 있고, receiver가 7, 8, 9번 packet을 받아도 6번을 받지 못했기 때문에 ACK5를 보낼 것 입니다.

그리고 6번 packet에 대한 timeout이 일어나서 sender는 6, 7, 8, 9번 packet을 다시 보내고, receiver는 ACK5에서 6, 7, 8, 9를 잘 받았기 때문에 ACK6, 7, 8, 9를 순차적으로 보낼 것이다.

 

이렇게 packet의 유실이 없다면 window는 0, 1, 2, 3, 4....... 7, 8, 9...로 쭉 가다가 (GO)

pakcet이 유실되거나 에러가 일어나면 window size (N개) 만큼 돌아와서 (back) 다시 packet을 전송합니다.

이러한 방식이 GO-Back-N 방식 입니다.

 

또한 window 안에 있는 packet들은 receiver가 확실히 받았는지 모르는 packet들이라서 buffer에 저장하고 있어야 하지만,

window를 지나온 packet들은 receiver가 확실하게 받았기 때문에, buffer에 저장해 둘 필요가 없는 packet들 입니다.

 

3. Selective Repeat

Go-Back-N 방식에서 하나의 packet만 문제가 일어나도 window size만큼의 모든 packet을 다 전송하는것이 비효율 적이라서 이를 보완한 방식입니다.

유실된 packet만 Selective하게 재전송 하는 방식입니다.

또한 모든 packet에 timer가 달려있습니다.

 

이는 먼저 receiver가 ACK하는 방식부터 달라집니다.

- Go-Back-N방식은 ACK(N)은 N번 packet까지 잘 받았다 라는 뜻이지만,

- Selective Repeat 방식에서 ACK(N)은 N번 packet만 잘 받았다 라는 뜻입니다. (N - 1번은 잘 맏았는지 모릅니다.)

 

또한, 이제 순서에 맞게 들어온 packet이 아니더라도, receiver는 해당 packet을 버리는 것이 아니라, buffer에 저장해 두고 있어야 합니다.

2번 packet이 유실되고, 3번, 4번을 받은 경우 ACK3, ACK4를 해 주어야 합니다.

 

selective repeat은 유실된 packet만 재전송 합니다.
위의 예제와 같이 0 ~ 14번 packet까지 전송하는데, window size가 4일 때

0번부터 {0, 1, 2, 3}번 packet을 보내는데, packet2번이 유실된 경우
receiver는 0, 1, 3번을 받을꺼고 ACK0, ACK1, ACK3을 각각에 대해서 보냅니다.

그리고 2번 packet을 못받았기 때문에 3번 packet은 buffer에 저장해 둡니다.

sender측은 ACK0, ACK1을 받았기 때문에 window는 2, 3, 4, 5를 가리키고 있고, 4, 5번 packet을 전송합니다.
reciever는 4, 5번을 잘 받았기에 ACK4, ACK5를 전송하고,

아직 2번 packet이 없기 때문에 4, 5번 packet은 buffer에 저장해 둡니다.

sender측은 ACK3, ACK4, ACK5를 받아도 ACK2를 못받았기 때문에 window를 이동시키지 않습니다.
packet2번의 timeout이 일어나서 packet2번만 재전송 합니다.
receiver는 2번 packet을 받았기에 ACK2를 전송하고, buffer에 있던 3, 4, 5도 같이 Application layer에 전송해줍니다.
sender측은 ACK2를 받았고, ACK3, ACK4, ACK5도 기존에 받았었으니까 window를 6, 7, 8, 9까지 이동시킵니다.

 

여기까지가 selective repaet의 방식입니다.

 

---

4. 딜레마

이제 여기서 딜레마가 하나 발생합니다. (Sequence number와 window size에 대해서 생각해 보아야 합니다.)

만약에 통신할 때 Sequence number를 최소한으로 {0, 1, 2, 3} 이렇게 4개만 사용하고

window size가 3이라면

 

예제)

sender가 packet 0, 1, 2를 보냅니다.

receiver는 packet을 받고 나서 ACK0, 1, 2를 보냅니다. 그런데, 모든 ACK가 유실된 경우

sender는 timeout에 의해서 packet 0번을 다시 보냅니다.

 

그런데 receiver는 내가 받을 3번 packet의 다음 packet인 0번 packet이라고 생각해서 이를 buffer에 저장할 수가 있습니다. (실제로는 이미 받은 packet입니다.)

 

해당 문제의 해결 방법은 sequence number를 늘리면 됩니다.

하지만, 무작정 많이 늘릴수는 없고, window size와 어떤 관계로 문제를 일으키지 않는 선에서 최소한으로 늘릴수 있을까? 하는 문제가 있습니다.

그래서 window size와 sequence number는 밀접한 관련이 있습니다.

 

아마 window size * 2 + 1만큼의 sequence number를 사용하면 될 것 같습니다.