강의 회고

RDT Protocol

RDT (Reliable Data Transpose) 는 sender 와 reciever 의 feedback , retransmission 으로 이뤄진다.

feedback 에 맞춰 sender 는 retransmission 하고, 중복된 데이터에 대해서는 packet에 부여된 sequence number 를 가지고 reciever 가 알아서 처리한다.

만약 loss 가 일어나 feedback 없을 경우엔 feedback 이 오기 까지의 timer 를 설정하여 feedback이 없으면 retransmission

RDT 프로토콜은 많은 시간을 소모한다.

• L : 데이터의 길이 (비트 또는 바이트 단위)
• R : 데이터 전송 속도 또는 비트 전송률 (bps 또는 b/s 단위)
• L/R : 데이터 길이 / 데이터 전송 속도 ==> 데이터 전송 시간
• RTT : Round Trupe Time ==> sender 가 마지막 비트를 전송하고 receiver 가 마지막 비트 까지 수신, 피드백을 sender 가 받을 때 까지 걸리는 시간
• (L/R)/(RTT+L/R) : 전체 지연 시간 으로 데이터를 전송하는데 걸리는 시간을 전체 왕복 시간으로 나눈 값으로, 네트워크에서의 전체 지연 시간을 나타낸다.

==> 그러니 RDT 는 유실 없이 신뢰도 높은 데이터 전송 프로토콜이지만 feedback 을 받기 까지의 RTT 라는 시간을 소모하기 때문에 많은 시간이 소모 된다.

하지만 packet 을 하나씩 보내고 feedback 을 받기 보다 우루루 보낸 후 feedback 을 받으면 ?

어차피 RTT 는 데이터를 몇 개씩 연속으로 보내든과 상관 없이 일정하다.

똑같이 3개의 packet 을 보낼 때 하나씩 수신하고 확인 할 필요 없이 우루루 보내는게 시간이 훨씬 빠르다.

그래서 실제 생활에서는 하나씩 보내고 피드백을 수신하는 방식이 아닌

우루루루루 보낸다.

그럼 우루루루 보내는데도 어떻게 신뢰성 있는 데이터 전송을 만들게 할까 ?

Go-Back-N

• window size : 윈도우 사이즈만큼은 피드백을 받지 않아도 packet 을 우수수수 보내자.
• Ack(n) : cumulative ACK 로 n 까지의 ACK 를 누적 (n 번째 ACK 가 아님)

Reciever 는 순정파

만약 내가 0번 ~ 3번 까지의 packet 을 리시버한테 보낸다고 해보자

만약 유실이 없으면

1. packet 1 전송 -> ACK 1 feedback
2. ACK1 받아서 packet 2 전송 -> ACK 2 feedback
   ..
3. ACK3 받아서 packet 4 전송 -> ACK4 feedback

된다.

그러니까 리시버는 packet1 을 받았으면 ACK1 을 피드백 하고 다음 패킷인 packet2 만을 기다린다.

만약 내가 ACK1 인 상태에서 packet2 를 제외한 다른 packet을 받으면 그냥 안받고 여전히 packet2 내놓으라고 ACK1 을 유지한다.

만약 유실이 있거나 packet 의 전송 속도가 달랐다고 해보자

sender 는 0 , 1, 2 , 3 , 4 , 5 , 6 , 7 packet 을 갖고 있고 window size : 4 라고 해보자

그니까 sender 는 피드백을 받건 말건 4개의 packet 을 우루루루 보내겠다는 거다.

GBN in ACTION

1. 0 , 1 , 2 ,3 우루루 방출
   • receiver 의 ACK 상태 변화
   • 0 받고 ACK0 => 1 받고 ACK1 => 2 못받아서 여전히 ACK1 => 3 받아도 여전히 ACK1
2. sender 는 0,1,2,3 을 보냈지만 사실상 receiver 는 0,1 만 받은 상태
3. sender 는 window 에 맞춰서 4,5,6,7 우루루 방출
   • sender : "어 ~ 너가 ACK 몇 번을 보내든 난 윈도우대로 보낼거야 ~"
4. 우루루 방출해도 리시버는 안받는다.
   • receiver : "나는 ACK1 이고 packet 2 내놔, 너가 뭘 보내도 나는 안받고 ACK1만 대답할거임 "
5. packet2 에 대한 피드백이 올 때 까지 너무 시간이 오래 걸리니 sender 측의 타이머가 터진다. (timeout)
6. sender 정신 차림
   • sender : "아 윈도우 다시 구성해서 보내야겠다. 어차피 2번 안받았으면 여태 보낸 것들도 못받았을거 아냐 "
   • 2,3,4,5 로 윈도우 다시 구성하고 재전송

왜 이름이 Go Back N 인가욜

윈도우 사이즈가 N 일 때 , 뭔가 타이머가 터지면 문제가 터진 부위로 되돌아가서 N 개 만큼의 윈도우로 다시 보내셈요 ㅋㅋ

sender 는 윈도우 전에 있던 놈들은 가지고 있을 필요가 없음

sender 가 0 , 1 , 2 , 3 , 4 , 5 ,6 , 7 ,8 ,9 를 가지고 있고 window : 4 인 상태에서

현재 우루루 쏟아붓고 ACK5 를 받았다고 해보자

그럼 sender 는 6 , 7 , 8 ,9 의 윈도우를 구성해서 우루루 쏟으면 된다.

ACK5 라는 뜻은 receiver 는 ACK1 , 2 , 3 ,4 , 5 까지 했다는 거니까

packet 0 ,1 , 2 , 3 , 4 , 5 는 잘 전송이 된거다.

그러니까 sender 는 packet 0 ~ 5 는 가지고 있을 필요 없다.어차피 보냈으니까

단점

내가 윈도우 사이즈에 맞게 우루루루 packet 을 보냈는데 그 중 하나라도 유실되면 다시 그 사이즈부터 윈도우를 구성하고 우루루루 packet 을 보내야 한다.

만약 window 사이즈가 100이라고 해보자

내가 우루루루루 쏟아부었는데 그 중 packet 1 이 유실되었다고 가정해보자

sender 는 0 ~ 99 쏟아붓고 100 ~ 199 쏟아 붓던 도중 packet1 유실 타이머가 터지면 다시 1 ~100 으로 윈도우를 구성하고 또 쏟아부어야 한다.

이미 난 1~99 까지 보냈는데 또 보내야 한다. 나는 보냈지만 sender 가 안받아버려서 중복된 패킷을 또 보낸다.

Selective Repeat

Selective Repeat : GBN 너 가능성 있어 , 열심히 해

리시버는 정확하게 받은 packet 에 대해서는 정보를 담고, 올바른 packet 에 대해선 ACK 를 보낸다.

예 : 0 , 1 , 2 ,3 을 보냈고 그 중 0 만 유실된 상황
receiver : [empty , 1 , 2 , 3] 으로 패킷을 받고 ACK 1 ~ 3 은 보낸다.

센더는 받지 않은 ACK 에 맞는 packet 만을 재전송 한다.

sender : ACK 1 ~3 은 받았고 .. ACK0 이 없네 ==> packet 0 재전송

Selective Repeat 에서는 receiver 도 packet 을 저장할 buffer 가 존재한다.

sender 의 window size 에 맞춰 receiver 도 buffer를 준비해준다.

Selective repeat 과정

위 과정을 이해해보자

초기 전송

window size : 4
sender 0 , 1 , 2 , 3 순차적으로 보내고 receiver 의 buffer 는 [0의 공간, 1의 공간 , 2의 공간 , 3의 공간] 를 기다리고 있음
0 도착 완료 => ACK 0 보내고 receiver 의 buffer 이동 [1의 공간, 2의 공간 , 3의 공간 , 4의 공간]
1 도착 완료 => ACK 1 보내고 receiver 의 buffer 이동 [2의 공간, 3의 공간 , 4의 공간 , 5의 공간]
2 유실되고 3 도착 완료 => ACK3 보내고 receiver 의 buffer [2의 공간, 3 채워짐 , 4의 공간 , 5의 공간]
sender 4,5,6,7 순차적으로 보냄
4 도착 완료 => ACK4 보내고 receiver 의 buffer [2의 공간, 3 채워짐 , 4 채워짐 , 5의 공간]
5 도착 완료 => ACK5 보내고receiver 의 buffer [2의 공간, 3 채워짐 , 4 채워짐 , 5 채워잠]
2 유실 된 것에 대한 time out 터져서 sender는 2 다시 보냄 => 2도착 완료 => ACK2 보내고receiver 의 buffer [2채워짐, 3 채워짐 , 4 채워짐 , 5 채워잠]

다시 재 전송된 후의 움직임

receiver 는 2 받았으니까 buffer [6 공간 , 7공간 , 8공간 , 9공간] 으로 buffer 형성하고 기다림
sender 는 ACK2 받았으니까 윈도우 [3,4,5,6] 으로 만들어둠
근데 이미 ACK3 , 4 , 5 는 받았으니 [3,4,5,6] 로 윈도우 구성했다가
- sender : 어 ? ACK3 있네 ? ==> 윈도우 재구성 [4,5,6,7]
- sender : 어 ? ACK4 있네 ? ==> 윈도우 재구성 [5,6,7,8]
- sender : 어 ? ACK5 있네 ? ==> 윈도우 재구성 [6,7,8,9]
마지막 ACK가 ACK5 니까 [6,7,8,9] 우루루 전송

딜레마

seqeumce number 는 작을 수록 좋다 . header 에 들어가는데 보내야 할 packet 이 1억개라고 header 에 0 ~ 1억 -1 까지의 번호를 하나하나 세겨놓으면 자원 낭비가 심하니까

딜레마 가정

그럼 내가 윈도우 사이즈를 3으로 지정해두고 sequence number 는 0 , 1 , 2 , 3 으로 구성해뒀다고 해보자

내가 데이터가 몇 개가 있든
0 , 1 , 2 , 3 , 0 , 1 , 2 , 3 .... 이런식으로 번호를 지정하겠다는 거임

만약 sender 가 첫 번째 윈도우인 0,1,2 보냈고 receiver 는 모두 잘 받아서 receiver 의 버퍼는 다음 윈도우의 [3 , 0 , 1] 을 기다리고 있을거다.

첫 번째 전송 후 sender 는 다음 윈도우인 [3 , 0 , 1] 을 보내겠지

그러면 [3 , 0 , 1] 에서 3 은 잘 받았어

그리고 timer 가 터져서 sender 는 ACK0 , 1 , 2 가 없으니 첫 번째 윈도우인 [0 , 1 ,2 ] 를 다시 보낼 것앋.

이 때 발생하는 문제는 recevier 버퍼 안에 다음 윈도우인 [3 , 0 , 1] 을 기다리는데 0 , 1 이 들어왔으니 recevier는 다음 윈도우의 0 , 1 인줄 알고 냅다 받아버린다. (2 는 자리가 없으니까 그냥 안받아버림)

다 차면 윈도우 이동하고 2 에 대한 ACK 없으니 재전송하고 ..

그럼 리시버는 전 윈도우의 2 지만 현재의 2 인줄 알고 받아버리고 ..

그러면서 악의 순환 고리 ...

그럼 어떻게 해결할까 ?

해결방법

시퀀스 넘버를 윈도우 사이즈의 2배로 해보자

요렇게 ==> 0 , 1 , 2 , 3 , 4 , 5, 0 , 1 , 2 , 3 , 4 , 5 , 0 , 1 , 2 , 3 , 4 , 5 ..

1. sender : [0 , 1 ,2 ] 전송 => recevier 전부 잘 받고 buffer : [3 , 4 ,5] 주세요 , 현재 ACK는 2
2. ACK 0 , 1 ,2 유실됐으니 sender 는 [0 , 1 ,2 ] 재전송
3. receiver : 어 ~ 버퍼에 자리 없으니까 안받아 3내놔 ~
4. sender 는 다음 윈도우인 [3,4,5] 보냄
5. recevier 는 ACK5 보내고 [0,1,2] 기다림
6. sender : 엥 왜 아직도 ACK 0 , 1 ,2 가 안오징 .. 재전송 해야하나 .. 고민함
7. recevier 가 ACK5 보냈으니 [0,1,2] 내놓으라고 닥달함
8. sender 는 ACK5 받았으니 이전에 윈도우인 0,1,2,3,4,5 애들은 무시하고 다음 윈도우를 구성 [0,1,2] 하고 보냄
9. sender 는 ACK 0 , 1 ,2 받았으니 만족
   해피엔딩

그럼 도대체 시퀀스 넘버는 윈도우 사이즈의 몇배로 해야할까 ?

그건 다음 강의에 ..