[Lecture] Pipelined protocol (Go-Back-N과 Selective Repeat)

지난시간

packet error : error detection, feedback, retransmission, sequence# (4가지 매커니즘으로 해결)

packet loss : timer의 timeout (로 해결)

=> reliable data transfer protocol이지만, 현실세계에선 사용하지 않는다

 

 

(transmition(패킷하나를 link에다 올려 보내는 시간) 공식 : 이전글 참조)

Usender의 분자는 sender가 보내는 시간, 분모는 sender가 보내는 시간 + 그 다음 보내기 전까지의 시간

결과를 보면 sender가 보내는 시간의 비율이 0.00027이기 때문에 효율적이지 않다는 것을 알 수 있다

전체시간에서 sender가 네트워크를 사용하는 비율이 클수록 좋다 (효율성이 높다)

 

그래서 pipelined protocol (한번에 패킷을 다 쏟아붓고, ACK를 각각 확인하는)를 사용한다

pipelined protocol의 두개의 일반적인 접근법(go-Back-N, selective repeat)을 확인할 것이다

---

Go-Back-N

Window size : 간단히, feedback을 받지 않고 내가 한번에 보낼 수 있는 것 (자기가 한번에 보낼 수 있는 양)

• 윈도우 크기는 송신자가 연속적으로 보낼 수 있는 패킷의 개수를 나타낸다.
• TCP와 같은 프로토콜에서 윈도우 크기는 플로우 제어와 관련이 있다. 수신자는 송신자에게 자신의 버퍼에 얼마나 많은 데이터를 저장할 수 있는지 알려주는 역할을 한다.

ACK(n) : cumulative ACK (쌓이는 ACK)

e.g. ACK 11이면 11번까지 완벽히 잘 받았으니 이제 12번 줘! 라는 의미이다

 

보내는 패킷(window)에 timer가 설정된다. timeout시 해당 seq#부터 재전송한다

예를들어, window size = 4

0	1	2	3	4	5	6	7	8
timer	timer	timer	timer

 

receiver는 받아야하는 seq#를 주구장창 기다린다. 1번을 받아야하는데, 2번을 받을 경우 2번을 버린다. 따라서,

pct1이 늦게 도착해서 pct2가 먼저가고 그다음 pct1이 receiver에 도착할 경우, receiver는 ACK 0을 보내고(잘 받은 seq#) 2를 drop할 것이다

2를 drop하게 되면, pct1도착 후 pct2은 오지 않고(drop했기 때문에) pct3이 오는데, 2번이 오지 않았으므로 3번을 drop할 것이다. 그럼

 

0	1	2	3	4	5	6	7	8
		timer	timer	timer	timer

 

이렇게 다시 재전송이 된다. (어떤 패킷이 유실된지 모르기 때문에 다시 보내야한다)

 

2번을 기다리는 중에 3번이 왔기 때문에 drop한다. 2번을 기다리고 있기 때문에 4,5번이 와도 drop한다. pct2가 timeout이 돼서 터지면 그 뒤에 다시보낸다

Window 안에 있는 PCT는 receiver가 제대로 받았는지 안받았는지 sender가 확인하지 못한 애들이다

 

문제가 발생했을때, 그 시점으로 돌아오는데, N개만큼 돌아와서 다시 반복한다. 그래서, Go-back-N

But ! 유실된건 하나인데 N만큼(N이 몇이 될지 모른다) 다시보내면 매우 비효율적이다

 

Selective Repeat

문제가 있을 시, 문제있는 것만 다시 보내주는 것이다

 

ACK(n) : 각 패킷에 대한 것

e.g . ACK(7)은 7번 패킷을 잘 받았다 라는 뜻이다. 7번 패킷까지 잘 받았다 (X)

 

손실되거나 유실된 PCT은 timeout시 재전송이된다

유실된 것만 다시 보낸다. receiver가 일을 더 해야한다

2번 패킷이 유실되면, 수신자는 3,4,5번 패킷을 버퍼에 저장해뒀다가 재전송된 2번 패킷을 받게됐을 때 저장한다 (올려보낸다)

이미 전송되어 ACK가 돌아온 패킷은 sender가 윈도우에서 해제한다

 

 

마지막 : 2345가 다 잘 도착했으므로 application layer에 올려주고, 6789로 넘어간다

 

단점 : 윈도우 내의 모든 패킷마다 타이머를 설정해야한다

 

# 꼭 여러 상황을 생각해봐야한다

 

Selective repeat : dilemma

 

앞서 말했던 것처럼, header의 필드 크기는 작을수록 좋다. 여기서 seq#는 몇개 정도가 적당할까?

window size = 3일때, seq# = 4개(0,1,2,3)이라고 가정해보자

 

012를 모두 유실했을때, 마침 0이 timeout이 되어 패킷이 보내졌다고 가정하면, receiver는 0이 3번 다음의 패킷인줄 알고 0을 저장한다 => 이건 seq#의 범위를 늘리면 해결된다

Q. 어느정도 늘려야할까?

A. 약 N(window size) x 2

 

+window가 패킷에 따라 timer를 하나씩 다 다는 건 말이 안된다.(N의 크기도 그렇고, 여러 process를 돌릴 경우에) TCP에선 window를 대표하는 timer를 하나 주고 사용한다. 자세한 이야기는 다음 수업에서 다룰 예정