수업 들을 때도 제법 헷갈리던 부분인데, 생각보다 정리하는데 오래 걸렸다.

나중에 다시 봐야지

목차
1. Performance of rdt 3.0
2. Pipelining
3. Go-Back-N
4. Selective Repeat

1.  Performance of rdt 3.0

 

📌 As-is : stop-and-wait (non-pipelining)

기존의 stop-and-wait은 상당히 비효율적이다.

RTT(Round Trip Time) 내에서 하나의 packet을 보내고 기다리는 동안 sender가 아무 것도 할 수가 없다.

이렇게 한 RTT 내에서 하나의 packet만 주고 받는 것을 non-pipelining 방식이라고 한다.

 

예를 들어, 1Gbps link, 30ms RTT 환경에서 8000bit packet을 전송한다고 치자.

 

  • packet을 channel로 전송하는 시간

$$ D_{trans} = \frac{L}{R} = \frac{8000bits}{10^{9}bits/sec} = 8 microsecs $$

 

  • 수신자가 데이터를 전송하는데 사용하는 시간의 비율

$$ U_{sender} = \frac{L/R}{RTT + L/R} = \frac{.008}{30.008} = 0.00027 $$

 

위의 계산대로 효율이 굉장이 좋지 않다는 것을 수치로 볼 수 있다.

RTT는 사람이 어떻게 예측하고 제어할 수 있는 값이 아니라서 어떻게 할 수 없다.

 

하지만 RTT는 엄연히 sender 입장이지, receiver 입장에서는 RTT라는 게 존재하지 않는다.

즉, "한 RTT 내에서 여러 개의 packet을 보내도 되지 않을까?"가 Pipelining 방식의 아이디어가 된다.

2.  Pipelining

 

📌 Pipelined Protocols Operation

✅ Pipelining : Sender에게 ACK을 기다리지 않고, 여러 개의 packet을 전송하도록 허용하는 것

  • "in-flight" : ACK이 도착하지 않아도 보낼 수 있는 packet
  • seq #의 범위는 증가될 필요가 있다.
  • packet의 양을 최대로 늘리면 네트워크 혼잡도가 심해져서 Queueing Delay가 발생해서 좋지 않다.
  • sender와 receiver는 하나 이상의 packet을 buffering 해야 한다.

 

in-flight가 3이면 U_sender가 0.00027이었던 수치가 아래처럼 바뀐다.

 

 ✒️ pipelining protocol → go-back-N, selective repeat

3.  Go-Back-N

 

sliding window

📨 Sender
  • packet header에 k-bit seq #를 갖는다.
  • window : 전송했지만 확인이 안 된 packet을 위해 허용할 수 있는 seq # 범위
    • ACK을 받으면 window가 이동한다. (sliding window)
    • window 범위를 벗어나면 송수신이 잘 이루어졌다고 판단한다.
  • Cumulative ACK : ACK(n) : seq# n을 가진 ACK을 cumulative(누적) ACK으로 인식한다.
    • "~까지 잘 받았다"라는 정보라고 이해하면 된다.
    • 수신측에서 보면 n을 포함한 n까지의 모든 packet에 대한 ACK이다.
    • Timer는 window의 가장 오래된 seq#를 기준으로 체크한다.
    • Timeout(n): timeout이 발생하면 window내의 n부터 그 이상의 seq# packet들을 모두 재전송한다. 
      • 5번 pkt가 수신 안 된 채 6,7,8번 pkt가 도착하더라도, 5번에 대한 ACK이 도착하지 않아 time-out이 되면 순서가 뒤바뀌어서 온 packet은 모두 버린다. 그리고 5번부터 다시 재전송한다.

 

📮 Receiver
💡 Window sliding을 하다가 packet loss가 발생하면 N만큼 다시 돌아간다.

  • ACK만 사용
    • packet이 수신될 때마다, 항상 현재까지 수신된 가장 높은 in-order seq# pkt에 대한 ACK을 보낸다.
    • duplicate ACKs이 발생할 수 있다.
    • rcv_base만 기억하고 있으면 된다.
  • out-of-order packet의 처리
    • 버리거나 버퍼에 적재하거나, 구현한 개발자 마음이다.
    • 현재까지 수신된 가장 큰 seq#에 대한 ACK을 재전송한다.

 

실제 action

4.  Selective Repeat

 

📌 What's difference with Go-Back-N?

Go-back-N 단점을 보완하기 위한 protocol이다.

  • Receiver가 수신한 packet에 대한 개별적인 ACK이 요구된다.
    • 순서가 틀린 packet들은 하위 seq #를 가진 packet이 수신될 때까지 buffering되었다가 seq# 순서대로 상위 Layer에 전달된다.
  • Sender는 ACK이 없는 packet에 대해서만 재전송한다.
    • sender의 timer는 ACK이 없는 각각의 packet에 대해서 유지된다.

 

📌 Sender & Receiver

Sender

  • 상위 Layer에서 Data가 수신된다. (rdt_send)
    • window 내에 이용가능한 다음 seq# packet이 있으면 전송한다.
  • timeout(n) : 선택적 타이머 운영
    • Packet n을 재전송하고 timer을 restart한다.
  • ACK(n) in [sendbase, sendbase + N]
    • n이 window에 있다면 packet이 수신된 것을 확인한다.
    • 만약 n이 smallest unACKed packet과 같다면, window를 다음으로 가장 작은 seq#로 옮긴다.

Receiver

  • Packet n in [rcvbase, rcvbase + N - 1] : rcv_base보다 클 때
    • 무조건 개별적으로 ACK(n) 송신 (cumlative ACK이 아니다!)
    • Out-of-order의 경우 buffer에 적재한다.
    • in-order인 경우 (필요하다면 buffer의 in-order pakets들을 상위 layer에 올리고) rcv_base를 가장 낮은 seq#를 가진 미수신 packet으로 옮긴다.
  • Packet n in [rcvbase - N, rcvbase - 1] : rcv_base보다 작을 때
    • ACK(n) : 이미 packet들을 정상적으로 받아서 처리가 끝난 상태다.
  • otherwise : 무시한다.

특징

  • receiver는 정상적인 특정 packet을 받으면 필요하든, 필요하지 않던 무조건 해당 packet에 대한 ACK을 sender에게 보낸다.
  • send_base가 있긴 하지만 receiver는 각 패킷마다 모두 ACK을 보낸다.
  • sender 측으로부터 out-of-order packet이 들어와도, in-order가 될 때까지 buffer에 가지고 있어야 한다.
  • 누적 ACK을 사용하지 않고, 개별적인 ACK을 사용한다.
  • Receiver sliding window가 Sender sliding window보다 빠르게 이동한다. ()

 

 

 

📌 Dilemma

예를 들어보자.

  • seq #s: 0,1,2,3 이 반복
  • window size=3

이 경우 모두 ACK loss가 발생하더라도 receiver는 정상적으로 packet을 받았으므로 window sliding을 해버린다.

문제는 Sender 입장에서는 ACK이 오지 않았으므로 time-out이 되어 처음부터 보냈는데, Receiver는 이를 새로운 패킷으로 인지하게 될 수도 있다.

 

💡 Seq# 범위가 window size의 2배 이상이면 무조건 문제가 해결된다!

 

저작자표시 비영리

티스토리툴바