파이프라이닝된 신뢰적인 데이터 전송 프로토콜

• rdt 3.0 프로토콜은 기능적으로는 정확하지만, 전송 후 대기 프로토콜이라는 점에서 형편없는 송신자 이용률을 갖는다.
• 이에 대한 해결책으로 송신자에게 확인응답(ACK)을 기다리기 전에 송신을 전송하도록 허용하는 파이프라이닝을 수행한다.
• 위와 같이 확인응답들을 기다리기 전에 송신자가 3개의 패킷을 전송하도록 허용하면, 송신자 이용률은 3배가 되는 것을 볼 수 있다. 즉, window size만큼 효율이 증가하게 된다.

전송 후 대기 동작

 

파이프라이닝된 동작

 

파이프라이닝 방식은 신뢰적인 데이터 전송 프로토콜에서 다음 중요 사항을 지켜야 한다.

• 순서번호의 범위가 커져야 한다.
  • 전송 중인 각각의 패킷은 유일한 순서번호를 가져야 한다. 확인응답(ACK)이 안된 패킷이 여러개 있을 수 있기 때문이다.
• 프로토콜의 송신자와 수신자는 패킷 하나 이상을 버퍼링해야 한다.
  • 송신자는 전송되었으나 확인응답이 안된 패킷을 최소한 하나 이상 버퍼링해야 한다.
• 필요한 순서번호의 범위와 버퍼링 조건은, 데이터 전송 프로토콜이 손실 패킷, 손상 패킷, 상당히 지연된 패킷들에 대해 응답하는 방식에 달려있다.
• 파이프라이닝 오류 회복의 2가지 기본적인 방법
  • GBN(Go-Back-N): N부터 반복
  • SR(Selective Repeat): 선택적 반복

---

GBN (Go-Back-N)

• GBN 프로토콜에서 송신자는 확인응답을 기다리지 않고 여러 패킷을 전송할 수 있다.
• 그러나 파이프라인에서 확인응답이 안된 패킷의 최대 허용수 N보다 크지 말아야 한다.

• 위 그림은 GBN 프로토콜에서 송신자 관점의 순서번호 범위를 보여준다.
• 확인응답이 안된 가장 오래된 패킷의 순서번호를 base로 정의하고, 사용되지 않은 가장 작은 순서번호를 nextseqnum(전송될 다음 패킷의 순서번호)로 정의한다.
• [0, base-1]: 순서번호는 이미 전송되고 확인응답이 된 패킷
• [base, nextseqnum-1]: 전송되었지만 아직 확인응답이 안된 패킷
• [nextseqnum, base+N-1]: 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷
• [base+N ~]: 파이프라인에서 확인응답이 안된 패킷(특히 순서번호 base를 가진 패킷)의 확인응답이 도착할 때까지 사용될 수 없다.

 

슬라이딩 윈도우 프로토콜

• 전송되었지만 아직 확인응답이 안된 패킷(하늘색)을 위해 허용할 수 있는 순서번호의 범위는 순서번호 범위상에서 크기가 N인 윈도우로 나타낸다.
• 프로토콜이 동작할 때 이 윈도우는 순서번호 공간에서 오른쪽으로 이동된다.
• 확인응답이 안된 패킷의 수를 N으로 제한하는 이유는 뒤에서 흐름제어와 TCP 혼잡 제어를 다룰 때 알게 될 것이다.
• 실제로 패킷의 순서번호는 패킷 헤더 안의 고정된 길이 필드에 포함된다.
• 만약 k가 패킷 순서번호 필드의 비트 수라면, 순서번호의 범위는 [0, 2^k-1]이 된다. 순서번호의 제한된 범위에서, 순서번호를 포함하는 모든 계산은 모듈로 2^k 연산을 이용한다. (순서번호 공간은 크기 2^k의 링처럼 생각될 수 있음)
• rdt 3.0이 1비트의 순서번호 필드를 가지므로 [0, 1]의 순서번호 범위를 갖는다.

 

GBN 송신자는 다음의 3가지 타입의 이벤트에 반응해야 한다.

• 상위로부터의 호출
  • rdt_send()가 위로부터 호출되면, 송신자는 우선 윈도우가 가득 찼는지, 즉 N개의 아직 확인응답이 안된 패킷이 있는지를 확인한다.
  • 만약 윈도우가 가득 차있지 않으면 패킷이 생성되고 송신되고, 변수들이 적절하게 갱신된다.
  • 만약 윈도우가 가득 차있다면, 송신자는 윈도우가 가득 차있음을 가리키는 함축적인 의미로 단지 데이터를 상위 계층으로 반환한다. 따라서 상위 계층은 나중에 다시 시도할 것이다.
• ACK의 수신
  • 순서번호 n을 가진 패킷에 대한 확인응답은 누적 확인응답으로 인식된다.
  • 누적 확인응답은 수신측에서 올바르게 수신된 n을 포함하여, n까지의 순서번호를 가진 모든 패킷에 대한 확인응답이다.
• 타임아웃 이벤트
  • 타이머는 손실된 데이터 또는 손실된 확인응답 패킷으로부터 회복하는 데 사용된다.
  • 만약 타임아웃이 발생한다면, 송신자는 이전에 전송되었지만 아직 확인응답이 안된 모든 패킷을 다시 송신한다.
    
    

GBN 수신자의 행동도 단순하다.

• 만약 순서번호 n을 가진 패킷이 오류 없이, 순서대로 수신된다면 수신자는 패킷 n에 대한 ACK를 송신하고 상위 계층에 패킷의 데이터 부분을 전달한다.
• 그 외의 경우에 수신자는 그 패킷을 버리고, 가장 최근에 제대로 수신된 순서의 패킷에 대한 ACK를 재전송한다.
• GBN 프로토콜에서 수신자는 순서가 잘못된 패킷들을 버린다. 이는 수신자 버퍼링이 간단하다는 이점이 있다.
  • 수신자가 유지해야 하는 것은 단지 다음 순서의 패킷 순서번호이다.

 

• 위 그림은 윈도우 크기가 4 패킷인 경우에 대한 GBN 프로토콜 동작이다.
• 윈도우 크기가 4이므로 송신자는 패킷 0~패킷 3까지 송신한다.
• 송신을 계속하기 전에 하나 이상의 패킷이 긍정 확인응답되는 것을 기다려야 한다.
• 각각의 성공적인 ACK(ACK0, ACK1)가 수신되었을 때,
  • 윈도우는 앞으로 이동한다.
  • 송신자는 새로운 패킷(pkt4, pkt5)을 각각 전송한다.
• 수신측에서 pkt2가 손실되었으므로 패킷 3,4,5는 순서가 잘못된 패킷으로 발견되어 discard 된다.
• GBN은 윈도우 크기와 대역폭 지연곱의 결과가 모두 클 때, 많은 패킷이 파이프라인에 있을 수 있다.
• GBN은 패킷 하나의 오류만으로 많은 패킷을 재전송하므로, 많은 패킷을 불필요하게 재전송하는 경우가 발생한다.

---

SR (Selective Repeat)

• 수신측에서 오류(손실 or 변조)가 발생한 패킷을 수신했다고 의심되는 패킷만을 재전송한다.
• 불필요한 재전송을 피할 수 있고, 필요에 따라 재전송 각각은 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답을 요구할 것이다.
• 윈도우 크기 N은 파이프라인에서 아직 확인응답이 안된 패킷의 수를 제한하는 데 사용된다.
• 그러나 GBN과는 달리 송신자는 윈도우에 있는 몇몇 패킷에 대한 ACK를 이미 수신했을 것이다.

• SR의 수신자는 패킷 순서와는 무관하게 손상 없이 수신된 패킷에 대한 확인응답을 할 것이다.
• 빠진 패킷(아직 도착하지 않은 더 작은 순서번호를 가진 패킷)이 있는 경우:
  • 순서가 바뀐 패킷은 빠진 패킷이 수신될 때까지 버퍼에 저장한다.
  • 빠진 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위 계층에 전달한다.

 

SR 송신자 이벤트와 행동

• 상위로부터 데이터 수신
  • 상위에서 데이터가 수신될 때, 송신자는 패킷의 다음 순서번호를 검사한다. 순서번호가 송신자 윈도우 내에 있으면 데이터는 패킷으로 송신된다.
• 타임아웃
  • 타이머는 손실된 패킷을 보호하기 위해 재사용된다. 그러나 타임아웃 시 오직 한 패킷만이 전송되기 때문에 각 패킷은 자신의 논리 타이머가 있어야 한다.
• ACK 수신
  • ACK가 수신되었을 때, 송신자는 그 ACK가 윈도우 내에 있다면 그 패킷을 수신된 것으로 표기한다. 만약 패킷 순서번호가 send_base와 같다면 윈도우 베이스는 가장 작은 순서번호를 가진 아직 확인응답이 안된 패킷으로 옮겨진다.

 

SR 수신자 이벤트와 행동

• [rcv_base, rcv_base+N-1] 내의 순서번호를 가진 패킷이 손상 없이 수신되는 경우
  • 수신된 패킷이 수신자의 윈도우에 속하며, 선택적인 ACK 패킷이 송신자에게 회신된다.
  • 이 패킷이 이전에 수신되지 않은 것이라면 버퍼에 저장된다.
  • 이 패킷이 수신 윈도우의 base와 같은 순서번호를 가졌다면, 이 패킷과 이전에 버퍼에 저장된 연속적으로 번호를 가진 (rcv_base로 시작하는) 패킷들은 상위 계층으로 전달된다.
• [rcv_base-N, rcv_base-1] 내의 순서번호를 가진 패킷이 수신되는 경우
  • 이 패킷이 이전에 수신자가 확인응답한 것이라도 ACK가 생성되어야 한다.
• 그 외의 경우, 패킷을 무시한다.