신뢰성 있는 데이터 전송 : ARQ

reference: Computer Networking 3판. James F. Kurose, Keith W.Ross
Automatic repeat-request. Wikipedia

신뢰성 있는 데이터 전송
    - ARQ(Automatic Repeat reQuest) :
        - 신뢰성 있는 데이터 전송을 위해 수신 확인과 timeout을 이용하여 데이터를 전송하는 오류 제어 기법
        - 주요 구성요소 : checksum, 순서번호, 타이머, ACK, NAK, window, pipelining
        - 종류: Stop & Wait ARQ, GBN(Go-Back-N) ARQ, SR(Selective Repeat) ARQ, Hybrid ARQ(HARQ : HSDPA에서 사용)

Stop & Wait ARQ
    - 한번에 하나의 프레임을 보내고 ACK를 수신하면 그 다음 프레임을 보내는 방식. 해당 프레임에 대한 ACK를 받기전 timeout이 일어나면, 해당 프레임에 오류 및 변형이 일어난 것으로 간주하고 재전송을 한다.

파이프라이닝
    - (Stop & Wait 방식으로 동작하는 대신) 송신자가 ACK을 기다리지 않고 여러 패킷을 전송하는 방식
    - 전송 중인 각 패킷은 유일한 순서 번호를 가져야 하고 순서 번호의 범위는 증가되어야 한다.
    - 프로토콜의 송신측과 수신측은 한 패킷 이상을 버퍼링해야 한다.
    - 본 전송방식에는 GBN ARQ와 SR ARQ가 사용된다.

GBN(Go-Back-N) ARQ
    - 슬라이딩 윈도우 프로토콜(sliding-window protocol)이라고도 부른다.
    - 윈도우(window) :  파이프라이닝을 위한  일정 개수의  패킷묶음.

- send_base : 확인 응답이 안 된 가장 오래된 패킷의 순서번호
- nextseqnum : 전송될 다음 패킷의 순서 번호
- N : 윈도우 크기(window size)

    - 확인 응답을 기다리지 않고 여러 패킷을 전송할 수 있다(최대 허용 수 : N). N이 무한대이면 아니되는가? 안된다. 흐름제어를 위해서.
    - GBN 송신자측의 행동 : 세 가지 타입의 이벤트에 반응
       - 상위 계층으로부터 하달된 data send() : 1. 윈도우가 가득 찼는지(N개의 ACK가 안 된 패킷이 있는지) 확인. 2. 차 있지 않다면 패킷 생성 및 송신, 변수 수정. 3. 차있을 경우 상위 계층으로 반려.
       - ACK의 수신 : 순서 번호 n인 패킷에 대한 확인 응답은 n까지의 모든 패킷에 대한 확인 응답이란 뜻의 누적확인응답(cumulative acknowlegement)으로 인식.
       - timeout : GBN이란 이름은 여기서 유래. 송신되었지만 확인응답이 안된 모든 패킷을 재전송.
    - GBN 수신자 측의 행동 :
       - 순서번호 n을 가진 패킷까지 정확히 수신된 경우 : n 패킷에 대한 ACK 전송 및 상위 계층에 payload 전송.
       - 그 외의 경우(중간에 빠진 패킷이 있는 경우 포함) : 가장 최근에 정확히 수신된 패킷에 대한 ACK 전송.

   - GBN의 예

- 송신자는 패킷 5까지 보냈음에도 불구하고, 패킷 2가 timeout되어 패킷 2부터 재전송한다.
- 수신자는 패킷 3, 4, 5를 정상적으로 수신했음에도 불구하고, 패킷 2부터 다시 받는다(3, 4, 5 폐기).

SR(Selective Repeat) ARQ
    - GBN은 패킷 하나의 오류 때문에 많은 패킷을 재전송하므로, 불필요한 전송이 많다.
    - 수신자에게 오류가 발생한 수신 패킷만을 송신자에게 다시 전송하는 기법
    - 수신자는 순서가 틀린 패킷들은 분실된 패킷들(즉, 더 낮은 순서번호를 갖는 패킷)이 수신될 때까지 버퍼에 저장, (순서가 틀린 패킷보다 낮은) 분실된 패킷을 수신하면 순서대로 상위계층에 전달.

- rcv_base에 앞선 ACK를 받지 못한 두 패킷이 재전송되었을 경우, 수신측에서는 이미 받았더라도 ACK를 생성한다.

    - 송신측
        - 상위 계층에서 데이터를 받을 경우 : 패킷의 다음 순서번호를 검사, 송신자 윈도우 내에 있으면 패킷으로 송신, 없으면 버퍼에 저장되거나 상위로 반려.
        - timeout 시 : 손실된 패킷을 보호하기 위해 다시 사용. 각 패킷마다 자신의논리 타이머를 가짐
        - ACK 수신 시 : window 내에 있을 경우 해당 패킷을 수신된 것으로 표시. 수신된 ACK의 순서번호가 send_base와 같으면 가장 작은 순서번호의 미확인 패킷으로 send_base가 옮겨짐(window 이동). 이동 후 순서번호를 가진 미전송 패킷이 있으면 해당 패킷 전송.

    - 수신측
        - [rcv_base, rcv_base + N -1]의 패킷이 수신될 경우, 해당 패킷의 ACK 전송. 새로운 패킷이면 버퍼에 저장. rcv_base와 동일 순서번호이면 이 패킷과 연속한 버퍼된 패킷을 상위 계층으로 전달(아래 그림의 패킷 2가 수신되었을 경우 참조).
        - [rcv_base - N, rcv_base -1]의 패킷이 수신될 경우, 이전에 ACK한 것이라도 해당 ACK가 생성되어야 한다.
        - 나머지 패킷은 무시.

- 패킷 2가 수신된 순간 수신측 base가 5로 변경된다(윈도우가 옮겨간다).

    - SR ARQ 적용시 주의 사항
         - 윈도우의 크기는 순서번호 공간 크기의 반 보다 작거나 같아야 한다(재전송된 순서번호 n의 패킷과 다음 cycle의 순서번호 n 패킷을 구분 못하는 경우가 생기기 때문에).