[11월5일]GBN과 SR

Performance of rdt3.0

• 지금까지 우리가 배운 stop and wait방식은 패킷 하나하나에 집중하여 확인하고 전송하는 방식이었는데(1번 pk -> 2번 -> 3 ->...)
• ex) 1Gbps의 link, 8000 bit의 packet이 전송 된다면

• 만약 두 종단 시스템 사이의 광속 왕복 전파 지연(RTT)이 30msec정도라면 모든 packet이 전송된 후 ACK를 받는데 까지 걸리는 시간이 30.008msec
• 따라서 30.008msec동안 송신자는 단지 0.008msec 동안만 데이터를 전송한 셈
• 이용률을 따져보면

• 0.027%만 이용했고 나머지는 대기 했다는 것을 알 수 있음
• 30.008msec동안 8000bit를 전송할 수 있지만 1Gbps의 링크를 사용하는 것에 비해 비효율 적인것을 느낄 수 있음

---

Pipelined protocols

• 한꺼번에 data packet들을 연속적으로 보내고 ACK또한 연속으로 받는 방식
• 순서번호의 범위가 증가 - 각각의 전송중인 패킷은 유일한 순서번호를 가져야 함
• Go-Back-N(N부터 반복)과 Selective Repeat, SR) 등이 있음

 

---

N부터 반복(Go-Back-N)

• 송신자는 확인응답을 기다리지 않고 여러 패킷을 전송할 수 있음
• 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크지 않아야 함
• sender는 타이머를 하나만 사용하고 buf를 가직 있어서 연속으로 보낼 수 있음
• 수신측은 buf가 필요 없음

• 초록색의 패킷들은 이미 ACK를 받아 수신 완료되었음을 확인한 패킷
• 노란색의 패킷들은 전송은 했지만 아직 ACK를 받지 못한 패킷
• 파란색의 패킷들은 상위 계층으로부터 데이터를 받는 즉시 전송을 할 수 있는 패킷
• 나머지 패킷들은 파이프라인에서 확인응답이 안 된 패킷

• GBN: sender FSM

1. 상위로부터의 호출 : rdt_send()가 상위 계층으로부터 호출되면, 송신자는 첫째로 윈도우가 가득 찼는지, 즉 N개의 아직 확인응답되지 않은 패킷이 있는지를 확인 -> 만약 윈도우가 가득 차 있지 않다면 패킷이 생성되고 송신됨 / 만약 윈도우가 가득 차 있다면, 윈도우가 가득 차 있다는 것을 가리키는 함축적인 의미로 단지 데이터를 상위 계층으로 반환
2. ACK의 수신 : GBN 프로토콜에서 순서번호 n을 가진 패킷에 대한 확인응답은 누적 확인응답으로 인식됨(패킷순서에 따라 번호를 줌)
3. 타임아웃 이벤트 : 'GBN(Go-Back-N)'이라는 프로토콜의 이름은 손실이 있거나 아주 긴 지연된 패킷이 있을 때 -> timeout이 발생하고 타임아웃이 발생한 패킷부터 다시 송신 -> 확인응답이 안 된 패킷이 있는 한 timer는 항상 실행중

• GBN: receiver FSM

1. 순서번호 n을 가진 패킷이 오류 없이, 순서대로 수신 된다면 수신자는 패킷 n에 대한 ACK를 송신하고 상위 계층에 데이터를 넘김
2. 그 외의 경우에는 받은 데이터를 버리고 가장 최근에 제대로 수신된 순서의 패킷에 대한 ACK를 재전송

• GBN 동작

1. 파이프라인을 이용하여 4개의 [0, 1, 2, 3] 패킷을 전송 후 기다림
2. 전송중 pkt2의 loss가 발생, 나머지는 모두 수신
3. 수신자는 sequence number의 순서에 맞지않는 pkt3을 받았으므로 가장 최근에 정확하게 수신한 1번의 ACK를 재전송 한 후 pkt3을 버림
4. 그 동안 sender는 ACK0번과 1번을 받았으므로 그 다음 2개의 패킷인 pkt4, pkt5를 전송
5. 재전송 된 ACK1번이 sender에 도착해도 이미 받은 ACK와 중복되는 응답은 무시
6. pk2의 타임아웃이 발생하며 sender는 타임아웃이 발생한 패킷부터 순서대로 전송을 시작 [2, 3, 4, 5]

• 여전히 남아있는 문제점들

• GBN에서 stop and wait 프로토콜의 채널 이용률 문제를 해결하였지만 여전히 성능 문제가 존재
• 윈도우 크기와 '밴드폭-지연(bandwidth-delay)' 곱의 결과가 모두 클 때, 많은 패킷들이 파이프라인에 있을 수 있는데 GBN은 패킷 하나의 오류 때문에 많은 패킷을 재전송하므로, 많은 패킷을 불필요하게 재전송하는 경우가 발생
• 채널 오류의 확률이 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워짐

---

Selective repeat(선택적 반복)

• 말 그대로 수신자에서 오류가 발생한 패킷을 수신했다고 의심되는 패킷만을 재전송하므로 불필요한 재전송을 피함
• sender뿐만 아니라 receiver에도 버퍼를 적용

• sender의 노란색 pecket은 전송 후 아직 ACK를 받지 못한 것
• sender의 초록색 packet은 ACK를 완벽하게 받은 것
• sender의 파란색 packet은 사용은 가능하나 아직 전송하지 못한 것
• sender의 나머지 packet은 사용 불가한 것

 

• receiver의 회색 packet은 예상은 가능하나 수신이 안 된 것
• receiver의 분홍색 packet은 순서가 틀린 패킷이지만 확인 응답을 전송한 것
• receiver의 파란색 packet은 윈도우 내에서 받을 수 있는 것
• receiver의 나머지 packet은 사용 불가한 것

• SR 송신자 이벤트와 행동

• 상위로부터 데이터 받음 : 상위에서 데이터가 수신될 때, SR 송신자는 패킷의 다음 순서번호를 검사 -> 순서번호가 송신자 윈도우 내에 있으면, 데이터는 패킷으로 송신 / 그렇지 않으면 GBN처럼 버퍼에 저장되거나 나중에 전송하기 위해 상위계층으로 되돌려짐
• 타임아웃 : 타이머는 손실된 패킷을 보호하기 위해 다시 사용하지만 오직 한 패킷만이 타임아웃에 전송되기 때문에, 각 패킷은 자신의 논리 타이머를 가져야 함
• ACK 수신 : ACK가 수신되었을 때, SR 송신자는 그 ACK가 윈도우에 있다면 그 패킷을 수신된 것으로 표기, 만약 패킷 순서번호가 send_based와 같다면 윈도우 베이스는 가장 작은 순서번호를 가진 아직 확인응답되지 않은 패킷으로 옮겨짐

• Selective repeat의 동작

1. pkt0~3을 전송중 pk2번에 loss가 발생
2. 나머지 pkt0, 1, 3은 수신 측에서 잘 받아 ACK를 전송 -> 순서대로 저장해야 하므로 우선 0번과 1번을 app으로 보냄 3번은 버퍼에 저장
3. ACK 0, 1, 3을 송신 측에서 받음 -> pkt4, 5 전송 -> pkt4, 5도 버퍼에 저장
4. pkt2에 타임아웃 발생
5. pkt2만 재전송
6. 송신 측 ACK 4, 5 받음,수신 측 ACK2받고 대기하고 있던 패킷 3, 4, 5 모두 app에 보냄
7. ACK 2를 뒤늦게 받아도 전송에는 영향을 주지 않음

•  Selective repeat의 dilemma

• ACK가 깨진경우 타임아웃이 걸리고 재전송을 하지만 이미 receiver는 그 패킷을 받았으므로 무시
• 결국 윈도우 base가 이동 할 수 없게 됨
• 또 0 1 2 3 0 1 2 같이 한정된 패킷 순서번호를 사용하는 상황에서는 0 1 2를 보낸 후 receiver가 보낸 ACK의 손실이 왔을 때 문제가 발생

 

• 여기서 receiver의 window는 옮겨졌으나 sender는 아직 ACK를 받지 못해 옮겨지지 않았음을 알 수 있음
• 타임아웃이 발생한 sender는 다시 0 1 2 번의 패킷을 보냄
• 그러나 receiver는 첫 번째 0 1 2번 패킷을 모두 받은 상태고 3번과 두 번째 0 1번을 기다리는 중이지만 그 내용은 확인 할 수 없으므로 이미 받은 0번 패킷을 현재 받아야하는 패킷으로 인식하여 저장 할 수 있음

-> receiver의 window는 옮겨졌지만, sender는 ACK를 받지 못한 상태이다.

ACK에 대한 time out이 발생하여 sender에서 0,1,2번의 패킷이 재전송된다.

sender에서 보낸 0,1번의 패킷은 receiver에서 기다리고 있는 0,1번 패킷과는 다른 패킷이다.

sender는 제대로 받았어야할 0,1번 패킷이 아닌 이전 0,1번 패킷을 받게 된다.