🌐 ziinsun

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

19 min read

rdt3.0의 핵심적인 성능 문제 : 전송 후 대기(stop-and-wait) 프로토콜 이라는 점

비트를 전송하는 데만 걸린 시간을 송신자의 이용률(효율)수식으로 정의한다면 전송 후 대기 프로토콜이 형편없는 송신자 이용률을 갖는다

해결책 : 송신자에게 확인응답을 기다리지 않고 여러 패킷을 전송하도록 허용(파이프라이닝) 확인응답들을 기다리기 전에 송신자가 3개의 패킷을 전송하도록 허용한다면 송신자의 이용률은 3배가 된다

파이프라이닝 방식은 신뢰적인 데이터 전송 프로토콜에서 다음과 같은 중요성을 지닌다

  • 순서 번호의 범위가 커져야 한다
    • 각각의 전송중인 패킷은 유일한 순서 번호를 가져야하고 전송중인 확인응답이 안된 패킷이 여럿 있을지도 모르기 때문이다
  • 프로토콜의 송수신측은 패킷 하나 이상을 버퍼링 해야 한다
    • 최소한 송신자는 전송되었으나 확인응답되지 않은 패킷을 버퍼링 해아한다
    • 정확하게 수신된 패킷의 버퍼링은 수신자에게서도 필요하다
  • 필요한 순서 번호의 범위와 버퍼링 조건은 데이터 전송 프로토콜이 손실 패킷과 손상 패킷 그리고 상당히 지연된 패킷들에 대해 응답하는 방식에 달려있다
    • 파이프라인 오류회복 접근방법 : GBN, SR

3.4.3 GBN

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

  • 확인응답이 안 된 가장 오래된 패킷의 순서 번호를 base로 정의
  • 사용되지 않은 가장 작은 순서 번호를 nextseqnum으로 정의 ⇒ 4가지 간격 식별
  1. 간격 [0,base-1] : 순서 번호는 이미 전송되고 확인응답이 된 패킷
  2. 간격 [base, nextseqnum-1] : 송신되었지만 아직 확인응답되지 않은 패킷
  3. 간격[nextseqnm, base+N-1] : 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷
  4. base+N 이상 : 파이프라인에서 확인응답이 안된 패킷의 확인응답이 도착할 때 까지 사용할 수 없음

전송되었지만 아직 확인응답이 안 된 패킷을 위해 허용할 수 있는 순서 번호의 범위는 순서 범위상에서 크기가 N인 ‘윈도’로 나타냄 프로토콜이 동작할 때 이 윈도는 순서 번호 공간에서 오른쪽으로 이동함

  • N = 윈도 크기
  • GBN 프로토콜 = 슬라이딩 윈도 프로토콜 이라고 부름
패킷의 순서 번호
  • 실제 패킷의 순서 번호는 패킷 헤더 안의 고정된 길이 필드에 포함
  • 만약 k가 패킷 순서 번호 필드의 비트 수라면, 순서 번호의 범위는 [0, 2^k - 1]
  • 순서 번호의 제한된 범위에서 순서 번호를 포함하는 모든 계산은 모듈로(modulo) 2^k 연산 을 이용

ACK 기반의 NAK 없는 확장된 FSM

  • base 와 nextseqnum 변수 추가
  • 이러한 변수에서의 동작과 변수를 포함하는 조건부 동작 추가

송신자
  1. 상위로부터 호출
    1. rdt_send()가 상위로부터 호출되면, 송신자는 우선 윈도가 가득 찼는지 확인한다(확인응답되지않은 패킷이 있는지 확인)
    2. 윈도가 가득 차있지 않다면 = 패킷이 생성되고 송신되며 변수들이 적절하게 갱신
    3. 윈도가 가득 차 있다면 = 데이터를 상위 계층으로 반환
      1. 윈도가 가득 차 있음을 가리키는 함축적 의미
      2. 상위계층에서 나중에 rdt_send()를 다시 시도

실제 구현에서는

  • 이 데이터를 버퍼링하거나
  • 오직 윈도가 가득 차 있지 않을때만 rdt_send()를 호출하는 동기화 메커니즘(semapore, flag)사용
  1. ACK 수신
    1. 순서번호 n을 가진 패킷에 대한 확인 응답은 누적확인응답으로 인식
      1. 누적 확인 응답 : 올바르게 수신된 n을 포함하여 n까지의 순서 번호를 가진 모든 패킷에 대한 확인응답
  2. 타임아웃 이벤트
    1. 타이머 : 손실된 데이터 또는 확인응답 패킷으로부터 회복하는데 사용
    2. 타임아웃이 발생한다면 송신자는 이전에 전송되었지만 아직 확인응답되지않은 모든 패킷을 다시 송신

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

지금 패킷 n이 수신되어야 하지만 그 다음 패킷 n+1이 먼저 도착했다고 가정 데이터가 순서대로 전달되어야 하므로 n+1을 저장하고 나중에 n이 수신되고 전달된 후 상위계층에 이 패킷을 전달

그러나 만약 n이 손실된다면, 재전송 규칙에 따라 수신자에게 패킷 n과 n+1이 모두 재전송

이점 : 수신자 버퍼링이 간단하다 (수신자는 어떤 순서가 잘못된 패킷에 대해 버퍼링 할 필요가 없다)

  • 송신자
    • 윈도 상위와 하위 경계에 있는 윈도안의 nextseqnum 위치 유지
  • 수신자
    • 다음 순서 패킷의 순서 번호만 유지 단점 : 그 패킷의 재전송이 손실되거나 왜곡될 수 있으므로 많은 재전송이 필요할 수도 있다는 것이다

윈도 크기가 4 패킷인 경우에 대한 GBN 프로토콜 동작

  • 윈도 크기가 4 = 패킷 0부터 3까지 송신

  • 송신을 계속하기 전에 하나 이상의 패킷이 긍정 확인응답되는것을 기다려야 함

  • ACK0, ACK1처럼 각각의 성공적인 ACK가 수신되었을 때

    • 윈도우는 앞으로 이동
    • 송신자는 새로운 패킷을 전송

  • pkt2가 손실되었으므로 pkt3,4,5는 잘못된 패킷으로 발견되어 제거

이벤트 기반 프로그래밍(event-based programming)

이 구현은 발생할 수 있는 다양한 이벤트에 대해 대응으로 취할 수 있는 동작을 구현하는 다양한 절차들과 유사

이러한 이벤트 기반 프로그래밍에서의 다양한 프로시저들은 프로토콜 스택에서 다른 프로시저에의해 야기되거나 인터럽트의 결과로 요청됨

송신자에서 이벤트

  1. rdt_send()를 호출하기 위한 상위 계층 개체로부터의 호출
  2. 타이머 인터럽트
  3. 패킷이 도착했을 때 rdt_rcv()를 호출하기 위한 하위 계층으로부터의 호출

3.4.4 SR

SR(Selective Repeat, 선택적 반복 프로토콜은 수신자에서 오류가 발생한 패킷을 수신했다고 의심되는 패킷만 재전송

  • 불필요한 재전송을 피하고

  • 필요에 따라 개별적인 재전송은 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답을 요구

  • 윈도크기 N = 아직 확인응답 되지않은 패킷의 수를 제한하는데 사용

SR 수신자는 패킷의 순서와 무관하게 손상없이 수신된 패킷에 대한 확인응답을 함 빠진 패킷이 존재하는 경우

  1. 순서가 바뀐 패킷은 빠진 패킷이 수신될 때까지 버퍼에 저장
  2. 빠진 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위계층에 전달
SR 송신자 이벤트와 행동
  1. 상위로부터 데이터 수신 : 상위에서 데이터가 수신될 때 SR 송신자는 다음 순서번홀르 검사하고 순서 번호가 윈도 내에 있으면 데이터는 다음 패킷으로 송신된다. 그렇지 않으면 버퍼에 나중에 전송하기 위해 되돌려진다
  2. 타임아웃 : 패킷을 보호하기 위해 재사용된다. 타임아웃시 오직 한 패킷만이 전송되기 때문에 각 패킷은 자신의 논리 타이머가 있어야 한다
  3. ACK 수신 : ACK가 수신되었을 때 SR 송신자는 그 ACK가 윈도 내에 있다면 그 패킷을 수신된 것으로 표기한다
    • 만약 패킷 순서가 send_base와 같다면 윈도베이스는 가장 작은 순서 번호를 가진 확인응답되지않은 패킷으로 옮겨진다
    • 윈도가 이동하고 윈도 내의 순서번호를 가진 미전송 패킷이 있다면 이 패킷들은 전송된다
SR 수신자 이벤트와 행동

1️⃣ [rcv_base, rcv_base+N-1] 내의 순서 번호를 가진 패킷이 손상 없이 수신된다.

이 경우는 수신된 패킷이 수신자의 윈도에 속하는 것이며, 선택적인 ACK 패킷이 송신자에게 회신된다.

  • 만약 이 패킷이 이전에 수신되지 않았던 것이라면 버퍼에 저장된다.
  • 만약 이 패킷이 수신 윈도의 base와 같은 순서 번호를 가졌다면,
    이 패킷과 이전에 버퍼에 저장되어 연속적으로 번호를 가진(rcv_base로 시작하는) 패킷들은 상위 계층으로 전달된다.

2️⃣ [rcv_base-N, rcv_base-1] 내의 순서 번호를 가진 패킷이 수신된다.

이 경우에는 이 패킷이 수신자가 이전에 확인응답한 것이라도 ACK가 생성되어야 한다.

3️⃣ 그 외의 경우, 패킷을 무시한다

송신측에서 pck 0,1,2,3보내고 기다리고 받는 쪽에선 2가 로스 되어도 0,1,3에 대해 ack를 보낸다.

송신측에서 ack 0,1 을 받아 슬라이딩 되어 pck 4,5를 보낸다. 이다음 ack 3을 받지만 슬라이딩이 안되어 가만히 있는다. ack 4,5까지 다 받으면 2 빼고 3,4,5를 다 받은 상태에서 아까 보낸 2에 대한 타임아웃이 되어 pck2를 재전송 한다.

SR 프로토콜에서 송신자와 수신자의 윈도는 항상 같지 않다

SR 수신자 이벤트와 행동의 2단계 : [rcv_base-N, rcv_base-1] 내의 순서 번호를 가진 패킷이 수신된다.

현재의 윈도 base보다 작은 특정 순서 번호를 가진 ‘이미 수신된 패킷’을 무시하지 않고 재확인 응답을 하는 것이 중요하다!

만약 수신자가 이 패킷에 대한 확인응답을 하지 않는다면, 송신자의 윈도는 결코 앞으로 이동하지 않을 것이다.

💡 송신자와 수신자는 올바른 수신과 그렇지 않은 수신에 대해 항상 같은 관점을 갖지는 않을 것이다.

→ 이는 SR 프로토콜에서 송신자와 수신자의 윈도가 항상 같지 않다는 것을 뜻한다.

첫번째 시나리오
  1. 처음 3개의 패킷에 대한 ACK가 손실되고 송신자가 재전송
  2. 수신자는 순서 번호가 0인 패킷을 수신
두 번째 시나리오
  1. 처음 3개의 패킷에 대한 ACK가 모두 올바르게 전달
  2. 송신자는 윈도우를 이동시켜 순서번호가 3,0,1인 4,5,6번째 패킷 전달
  3. 순서번호 3을 가진 패킷이 손실되고 순서번호 0을 가진 패킷 도착

수신자 관점에서 수신자는 송신자의 행동을 볼 수 없다 모든 수신자는 채널을 통해 받고 채널을 통해 보내는 메시지의 순서를 관찰하는데 위의 두 가지 시나리오가 똑같다 즉, 다섯번째 패킷의 원래 전송과 첫번째 패킷의 재전송을 구별할 수 없다

받는 입장에서는 pck0이 재전송된건지 새로운건지 모른다

패킷 순서 바뀜 현상

  • 앞에서 패킷들은 송신자와 수신자 사이의 채널 안에서 순서가 바뀔 수 없다는 가정 하에 신뢰적인 데이터 전송 프로토콜에 대한 설명을 하였지만 이는 일반적으로 송신자와 수신자가 단일한 물리적 선으로 연결되어 있을 때 적합한 가정이다
  • 하지만 둘을 연결하는 채널이 네트워크 일때는 패킷 순서 바뀜이 일어날 수 있다

송신자와 수신자의 윈도가 x를 포함하지 않고 있더라도 순서 번호 또는 확인응답 번호 x를 가진 오래된 패킷의 복사본들이 생길 수 있다

패킷 순서가 채널이라는것 ?

  • 패킷들을 버퍼에 저장하고
  • 나중에 어느 때나 이 패킷들을 임의로 내보낸다고 간주

순서 번호가 재사용될 수 있으므로 중복 패킷들을 막을 수 있는 조치가 필요하다 실제 방식 : 송신자가 이전에 송신된 순서 번호 x를 가진 패킷들이 더는 네트워크 상에 없음을 어느정도 확신할 때까지 순서 번호가 재사용되지않음을 확실히 하는것 패킷이 어느 일정시간이상으로 네트워크에서 존재할 수 없다는 가정 하에 이루어짐

Graph View