3. 전송 계층 3

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

• 이용률Utilization: 전체 시간 중 sender가 사용하는 시간
• stop-and-wait 프로토콜은 이용률이 낮다는 문제가 있음 
  • 예시
    • stop-and-wait 프로토콜을 쓰는 두 종단 시스템이 있음.
    • 두 종단 시스템 사이의 광속 왕복 전파 시간(RTT)는 30msec이라고 가정.
    • 1Gbps(초당 10^9비트) 전송률(R)을 가진 채널에 의해 연결되어 있다고 가정.
    • 헤더 필드와 데이터를 모두 포함하여 패킷당 크기는 1000바이트(8000bit)라고 가정.
    • 이때 1Gbps 링크로 패킷을 실제 전송하는데 걸리는 시간은 L/R이므로 8000bits/packet / 10^9bits/sec = 8microseconds임.
    • 그러면 송신자는 ACK패킷을 t = RTT + L/R = 30.008sec 후에 받을 수 있음.
    • 그러므로 이용률은 0.008 / 30.008 msec = 0.00027 퍼센트로 매우 효율이 낮음.
• 따라서 확인응답을 기다리지 않고 여러 패킷을 전송하도록 허용하는 방식인 파이프라이닝Pipelining 기술을 사용
  • 파이프라이닝의 두가지 접근 방법
    1. N부터 반복Go-Back-N, GBN
    2. 선택적 반복Selective Repeat, SR

 

N부터 반복

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

• GBN 프로토콜의 키
  • 초록: 이미 응답된 패킷
  • 노랑: 전송 후 응답 안 된 패킷
  • 파랑: 사용 가능하나 전송 안된 패킷
  • 하양: 사용 불가
• 전송되었지만 아직 확인응답 안된 패킷을 위해 허용할 수 있는 순서번호의 범위는 순서번호 범위 상에서 크기가 N인 "윈도우"로 나타냄.
• 프로토콜이 동작할 때 이 윈도우는 순서번호 공간에서 오른쪽으로 이동함.
• N을 윈도우 사이즈로 부르며, GBN 프로토콜을 슬라이딩 윈도우 프로토콜로 부름. 
• GBN 송신자가 반응하는 3가지 이벤트
  • 상위 계층으로부터 호출
    • 송신자는 윈도우가 가득 찼는지 확인 (N개의 확인응답 되지 않은 패킷이 있는지 확인)
    • 만약 윈도우가 가득 차 있지 않다면 패킷 생성 후 송신
    • 만약 윈도우가 가득 차 있다면 데이터 상위 계층으로 반환
  • ACK 수신
    • 순서번호 n을 가진 패킷에 대한 확인응답은 누적확인응답(cumulative acknowledgement)로 인식.
    • 누적확인응답: 수신측에서 올바르게 수신된 n을 포함하여 n까지의 순서번호를 가진 모든 패킷에 대한 확인응답.
  • 타임아웃 이벤트
    • 타임아웃 발생시 송신자는 이전에 전송되었지만 아직 확인응답 되지 않은 모든 패킷을 다시 송신함
• GBN 수신자가 반응하는 2가지 이벤트
  • 순서번호 n을 가진 패킷에 오류 없이 전달
    • 패킷 n에 대한 ACK 송신 후 상위 계층에 데이터 부분 전달.
  • 순서번호 n이 아닌 순서가 잘못된 패킷 전달 혹은 오류가 있는 패킷 전달
    • 패킷을 버리고 가장 최근에 제대로 수신된 패킷에 대한 ACK 재전송
• 동작 예시

 

선택적 반복Selective Reat, SR

• GBN 프로토콜은 패킷 하나의 오류 때문에 많은 패킷을 재전송하므로 많은 패킷을 불필요하게 재전송하는 경우가 발생.
• 선택적 반복 프로토콜은 수신자에게 오류(손실되거나 변조된)가 발생한 패킷을 수신했다고 의심되는 패킷만을 송신자가 다시 전송하므로써 불필요한 재전송을 피함.
• 필요에 따라 각각의 개별적인 재전송은 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답 요구.

• SR 프로토콜의 키
  • 송신자
    • 초록: 이미 응답된 패킷
    • 노랑: 전송 후 응답 안된 패킷
    • 파랑: 사용 가능하나 전송 안된 패킷
    • 하양: 사용 불가
  • 수신자
    • 초록: 버퍼에 저장된 순서 틀린 패킷이나 확인 응답 된 패킷
    • 노랑: 수신 안된 패킷
    • 파랑: 윈도우 내에서 받을 수 있는 패킷
    • 하양: 사용 불가 패킷
• SR 송신자가 반응하는 3가지 이벤트
  • 상위 계층으로부터 데이터 받음
    • 송신자는 패킷의 다음 순서번호 검사
    • 만약 순서번호가 송신자 윈도우 내에 있으면 데이터는 패킷으로 송신
    • 만약 순서번호가 송신자 윈도우 내에 있지 않으면 버퍼에 저장되거나 상위 계층으로 되돌려짐
  • 타임아웃
    • 각 패킷은 자신의 논리 타이머를 가짐
  • ACK 수신 
    • 만약 그 ACK가 윈도우에 있다면 그 패킷을 수신된 것으로 표시.
    • 만약 패킷 순서번호가 send_base와 같다면 윈도우 베이스를 아직 확인응답 되지 않은 패킷들 중 가장 작은 순서번호를 가진 것으로 이동.
      
      • 만약 윈도우가 이동하고 윈도우 내의 순서번호를 가진 미전송 패킷이 있다면 패킷 전송.
• SR 수신자가 반응하는 이벤트
  • [rcv_base ~ rcv_base+N+1] 내의 순서번호를 가진 손상 없는 패킷 수신
    • 선택적인 ACK 수신
    • 만약 이 패킷이 이전에 수신되지 않았던 것이라면 버퍼에 저장 후 선택적 ACK 수신
  • [rcv_base-N ~ rcv_base-1] 내의 순서번호를 가진 손상 없는 패킷 수신
    • 패킷이 수신자가 이전에 확인응답 한 것이라도 ACK수신
  • 그 외
    • 패킷 무시
• 동작 예시

• SR 프로토콜에서 송신자와 수신자의 윈도우가 항상 같지는 않음.
• 따라서 송신자와 수신자의 윈도우는 잘 동기화 되어야 하며, 동기화 부족은 순서번호의 한정된 범위에 직면 했을 때 문제를 일으킴.
  • 예시
  
• 그림 a의 경우
  • 0부터 2까지의 패킷이 전송되어 올바르게 수신되어 수신자가 확인
  • 수신자의 윈도우는 각각의 순서번호가 3,0,1인 4,5,6번째 패킷에 있음
  • 처음 3개의 패킷에 대한 ACK 손실
  • 송신자는 이 패킷 재전송
  • 수신자는 순서번호가 0인 패킷(처음 보낸 패킷의 복사본)을 수신 => 하지만 수신자는 이것이 중복된 패킷인지 알수 없음
• 그림 b의 경우
  • 0부터 2까지의 패킷이 전송되어 올바르게 수신되어 수신자가 확인
  • 수신자의 윈도우는 각각의 순서번호가 3,0,1인 4,5,6번째 패킷에 있음
  • 처음 3개의 패킷에 대한 ACK 올바르게 전달.
  • 송신자는 윈도우를 이동시켜 각각의 순서번호 3,0,1인 4,5,6번째 패킷 전송.
  • 순서번호 3을 가진 패킷 손실, 순서번호 0인 패킷 정상 전달.
  • 수신자는 순서번호가 0인 패킷(새로운 데이터를 포함한 패킷)을 수신 => 하지만 수신자는 이것이 새로운 패킷인지 알수 없음.
• 따라서 윈도우 사이즈는 최소한 SR 프로토콜에 대한 순서번호 공간 크기의 절반보다 작아야 함.