[네트워크이론] 3.4 Principles of Reliable Data Transfer

(Computer Networking a top-down Approach 책의 내용입니다)

3.4 Principles of Reliable Data Transfer

• 이번 절에서의 가정
  • 패킷 전달 순서가 바뀔 일은 없음
  • 단방향 데이터 전송(unidirectional data transfer) 만 고려
    • 양방향 데이터 전송(bidirectional data transfer) 은 개념적으로는 비슷하지만 more tedious to explain
    • 단방향 데이터 전송에서도 제어 패킷은 서로 주고 받음
• FSM으로 설명

3.4.1 Building a Reliable Data Transfer Protocol

완벽하게 신뢰 가능한 채널 상에서의 신뢰적 데이터 전송

• 비트 에러 x
• 패킷 손실 x
• 보내는 쪽이나 받는 쪽이나 특별한 체크가 필요 없음

송신자의 FSM

stateDiagram-v2
    S0: 상위의 호출을 대기
    [*] --> S0
    S0 --> S0: rdt_send(data)<br>--------------<br>packet = make_pkt(data)<br>udt_send(packet)

수신자의 FSM

stateDiagram-v2
    S0: 하위의 호출을 대기
    [*] --> S0
    S0 --> S0: rdt_rcv(data)<br>--------------<br>extract(packet, data)<br>deliver_data(data)

비트 에러가 있는 채널 상에서의 신뢰적 데이터 전송(수신자의 데이터 전송 오류 가능성 미고려)

• stop and wait 프로토콜
• 프로토콜 :
  • 송신자는 데이터를 보낸 후 대기
  • 수신자는 checksum을 통해 비트 에러를 확인
  • 확인 결과에 따라 송신자에게 제대로 데이터를 받았는지 전달(ACK, NAK)
  • 송신자는 ACK를 받으면 다음 데이터를 보내고 NAK를 받으면 같은 데이터를 재전송
• 한계 :
  • 송신자의 입장에서 수신자가 보낸 ACK, NAK 패킷이 손상되었다면 수신자가 제대로 데이터를 받았는지 확인할 방법이 없음

송신자의 FSM

stateDiagram-v2
    direction LR
    S0: 상위의 호출을 대기
    S1: ACK or NAK 응답을 대기
    [*] --> S0
    S0 --> S1: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(data, checksum)<br>udt_send(sndpkt)
    S1 --> S1: rdt_rcv(rcvpkt) && isNAK(rcvpkt)<br>----------------<br>udt_send(sndpkt)
    S1 --> S0: rdt_rcv(rcvpkt) && isACK(rcvpkt)<br>----------------<br>𝛬

• 데이터 전송 호출
  • rdt_send(data) : 상위의 데이터 전송 호출
  • sndpkt = make_pkt(data, checksum) : 데이터와 체크섬을 패킷으로 가공
  • udt_send(sndpkt) : 신뢰 불가능한 채널로 데이터 전송
• 대기 상태에서 패킷을 받았을 때
  • ACK이면
    • 𝛬 : 특별히 뭔가를 하지 않고 다음 데이터 전송 호출
  • NAK이면
    • 같은 패킷 재전송

수신자의 FSM

stateDiagram-v2
    direction LR
    S0: 하위의 호출을 대기
    [*] --> S0
    S0 --> S0: rdt_rcv(rcvpkt) && corrupt(rcvpkt)<br>----------------<br>udt_send(NAK)
    S0 --> S0: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)<br>----------------<br>extract(rcv-kt, data)<br>deliver_data(data)<br>udt_send(ACK)

• 받은 데이터가 손상된 경우(corrupt case)
  • NAK 전송
• 받은 데이터가 손상되지 않은 경우(notcorrupt case)
  • ACK 전송

비트 에러가 있는 채널 상에서의 신뢰적 데이터 전송(수신자의 데이터 전송 오류 가능성 고려)

• ACK/NAK가 손상된 경우 NAK로 간주하고 재전송
• 하지만 수신자 입장에서 자신이 보낸 ACK/NAK 패킷이 송신자에게 제대로 도착했는지 알 수 없기 때문에 수신자는 새로 온 데이터가 새 데이터인지 재전송된 것인지 알 방법이 없음
  • 송신자가 sequence number를 각 패킷에 포함시킴
  • 수신자는 이 숫자를 통해 중복 패킷 여부를 확인해서 처리

송신자의 FSM

stateDiagram-v2
    [*]
    S0WC: 패킷 0 전송 호출을 대기
    S0WR: 패킷 0에 대한 ACK/NAK 응답 대기
    S1WC: 패킷 1 전송 호출을 대기
    S1WR: 패킷 1에 대한 ACK/NAK 응답 대기

    [*] --> S0WC
    S0WC --> S0WR: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(0, data, checksum)<br>udt_send(sndpkt)
    S0WR --> S0WR: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt))<br>----------------<br>udt_send(sndpkt)
    S0WR --> S1WC: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt))<br>----------------<br>𝛬

    S1WC --> S1WR: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(1, data, checksum)<br>udt_send(sndpkt)
    S1WR --> S1WR: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt))<br>----------------<br>udt_send(sndpkt)
    S1WR --> S0WC: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt))<br>----------------<br>𝛬

• 패킷 0에 대한 다이어그램과 패킷 1에 대한 다이어그램은 동일한 구조 (번호의 차이만 존재)

수신자의 FSM

stateDiagram-v2
    [*]
    S0: 하위의 패킷 0 호출 대기
    S1: 하위의 패킷 1 호출 대기

    [*] --> S0
    S0 --> S1: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)<br>----------------<br>extract(rcvpkt, data)<br>deliver_data(data)<br>sndpkt = make_pkt(ACK, chksum)<br>udt_send(sndpkt)
    S1 --> S1: rdt_rcv(rcvpkt) && corrupt(rcvpkt)<br>----------------<br>sndpkt = make_pkt(NAK, chksum)<br>udt_send(sndpkt)
    S1 --> S1: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)<br>----------------<br>sndpkt = make_pkt(ACK, chksum)<br>udt_send(sndpkt)
    S1 --> S0: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)<br>----------------<br>extract(rcvpkt, data)<br>deliver_data(data)<br>sndpkt = make_pkt(ACK, chksum)<br>udt_send(sndpkt)
    S0 --> S0: rdt_rcv(rcvpkt) && corrupt(rcvpkt)<br>----------------<br>sndpkt = make_pkt(NAK, chksum)<br>udt_send(sndpkt)
    S0 --> S0: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)<br>----------------<br>sndpkt = make_pkt(ACK, chksum)<br>udt_send(sndpkt)

• 패킷이 손상되지 않고 순서에 맞는 경우 : ACK 응답
• 패킷이 손상된 경우 : NAK 응답
• 패킷이 손상되지 않고 순서에 맞지 않는 경우(송신 측에서 손상된 ACK 패킷을 받아서 재전송한 경우) : ACK 응답

비트 에러가 있는 채널 상에서의 신뢰적 데이터 전송(수신자의 데이터 전송 오류 가능성 고려) <-- NAK 없이 동일한 효과

• 수신자가 패킷을 받을 때맏 가장 최신에 성공적으로 받은 패킷 번호를 ACK와 함께 응답하면 굳이 케이스를 나눠서 응답하지 않아도 됨
• TCP가 사용하는 방식

송신자의 FSM

stateDiagram-v2
    [*]
    S0W: 상위의 패킷 0 호출 대기
    S0R: 패킷 0 ACK 응답 대기
    S1W: 상위의 패킷 1 호출 대기
    S1R: 패킷 1 ACK 응답 대기

    [*] --> S0W
    S0W --> S0R: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(0, data, checksum)<br>udt_send(sndpkt)
    S0R --> S0R: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 1))<br>----------------<br>udt_send(sndpkt)
    S0R --> S1W: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 0)<br>----------------<br>𝛬
    S1W --> S1R: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(1, data, checksum)<br>udt_send(sndpkt)
    S1R --> S1R: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 0))<br>----------------<br>udt_send(sndpkt)
    S1R --> S0W: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 1)<br>----------------<br>𝛬

• 손상된 응답을 받거나 올바르지 않은 순서의 응답 받은 경우 : 재전송
• 제대로 된 순서의 ACK 응답 받은 경우 : 다음 state로 이동

수신자의 FSM

stateDiagram-v2
    [*]
    S0: 하위의 패킷 0 호출 대기
    S1: 하위의 패킷 1 호출 대기

    [*] --> S0
    S0 --> S0: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt))<br>----------------<br>sndpkt = make_pkt(ACK, 1, checksum)<br>udt_send(sndpkt)
    S0 --> S1: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)<br>----------------<br>exract(rcvpkt, data)<br>deliver_data(data)<br>sndpkt = make_pkt(ACK, 0, checksum)<br>udt_send(sndpkt)
    S1 --> S1: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq0(rcvpkt))<br>----------------<br>sndpkt = make_pkt(ACK, 0, checksum)<br>udt_send(sndpkt)
    S1 --> S0: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)<br>----------------<br>exract(rcvpkt, data)<br>deliver_data(data)<br>sndpkt = make_pkt(ACK, 0, checksum)<br>udt_send(sndpkt)

• 모든 경우 : 가장 최근에 정확하게 수신된 패킷 번호에 대해 ACK 응답

비트 에러와 손실이 모두 가능한 채널 상에서의 신뢰적 데이터 전송

• 송신자는 일정 시간 내에 ACK 응답 없으면 재전송
  • ACK에 패킷 순서 번호를 달아줌으로써 중복 데이터 이슈는 자연스레 해결
• 송신자는 올바른 순서의 ACK 응답 받으면 다음 단계로 나아감

송신자의 FSM

stateDiagram-v2
    [*]
    S0W: 상위의 패킷 0 호출 대기
    S0R: 패킷 0 ACK 응답 대기
    S1W: 상위의 패킷 1 호출 대기
    S1R: 패킷 1 ACK 응답 대기

    [*] --> S0W

    S0W --> S0W: rdt_rcv(rcvpkt)<br>----------------<br>𝛬
    S0W --> S0R: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(0, data, checksum)<br>udt_send(sndpkt)<br>start_timer
    S0R --> S0R: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 1))<br>----------------<br>𝛬
    S0R --> S0R: timeout<br>----------------<br>udt_send(sndpkt)<br>start_timer
    S0R --> S1W: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 0)<br>----------------<br>stop_timer
    S1W --> S1W: rdt_rcv(rcvpkt)<br>----------------<br>𝛬
    S1W --> S1R: rdt_send(data)<br>----------------<br>sndpkt = make_pkt(1, data, checksum)<br>udt_send(sndpkt)<br>start_timer
    S1R --> S1R: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 0))<br>----------------<br>𝛬
    S1R --> S1R: timeout<br>----------------<br>udt_send(sndpkt)<br>start_timer
    S1R --> S0W: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 1)<br>----------------<br>stop_timer

cf) 지금까지 살펴본 프로토콜은 패킷 순서 번호가 0, 1 교대로 반복되므로 alternating-bit protocol이라고 부르기도 함

3.4.2 Pipelined Reliable Data Transfer Protocols

• stop-and-wait 방식으로 성능 문제가 있음
• ex)
  • 가정
    • 두 호스트 간에 30ms의 RTT
    • Transmission rate, $R$, of $1Gbps$ ($10^{9}$ bits per second)
    • Packet size, $L$, of $1,000$ bytes ($8,000$ bits) per packet
  • 패킷 하나 전송에 소요되는 시간
    • $$ d_{trans} = \frac{L}{R} = \frac{8000 \text{bits}}{10^{9} \text{bits/sec}} = 8 \text{ms} $$
  • $t = 0$ 에 전송을 시작하면 $t = RTT/2 + L/R$ 시점에 패킷이 수신 측에 도착
  • (ACK 패킷이 아주 작다고 가정하면) 패킷 전달 완료 시점은 $t = RTT + L/R$
  • 송신 채널의 utilization을 전체 시간 대비 송신자가 채널에 비트를 밀어넣는데 실제로 돌아가는 시간으로 정의하면,
    • $$ U_{sender} = \frac{L/R}{RTT + L/R} = \frac{.008}{30.008} = 0.00027$$
  • 1Gbps 링크에서 실질적인 처리량은 267kbps
• Solution?
  • 대기할 시간에 병렬적으로 패킷 전송 => pipelining
• 신뢰적 데이터 전송에서 파이프라이닝으로 인해 필요한 변화
  • sequence 넘버의 범위가 늘어나야 한다.
  • 수신/송신 측은 하나 이상의 패킷을 버퍼에 임시 보관해야할 수 있다.
  • 시퀀스 넘버의 범위와 버퍼링 요구 사항은 손실,손상,지연 패킷에 대해 데이터 전송 프로토콜이 대응하는 방식에 따라 달라진다. 가장 기본적인 두 가지 파이프라인 에러 복구 접근 방식은 Go-Back-N과 selective repeat이다.

3.4.3 Go-Back-N (GBN)

• N : window size
• GBN 프로토콜 - sliding-window protocol
• window size limit을 두는 이유?
  • flow control (3.5에서 확인)
  • congestion control (3.7에서 확인)
• 패킷의 시퀀스 넘버는 패킷 헤더에 설정
  • $k$를 패킷 시퀀스 넘버 필드의 비트라 하면 숫자의 범위는 $[0, 2^{k} - 1]$ 이다.
  • 따라서 시퀀스 넘버는 $2^{k}$의 modulo 연산으로 구한다. (오버플로우시 0으로 복귀)

Sender

• cumulative ACK:
  • ACK(n) -> n번째 패킷을 포함한 모든 이전의 패킷을 ACK 처리
    • ACK(n)을 받으면 window를 n+1부터 시작하도록 이동
• 전송한지 가장 오래된 패킷에 대해 타이머 작동
  • timeout(n) : 전송되었지만 ACK되지 않은 패킷 중 가장 오래된 패킷을 전송한 시간으로부터 일정 시간이 흐르면, 윈도우 내에 해당 패킷과 그 이후의 모든 패킷을 재전송.

Receiver

• ACK-only :
  • 순서에 맞게 들어온 패킷 중 가장 높은 시퀀스 번호로 ACK 응답
    • 동일 번호의 ACK가 여러 번 갈 수 있음
    • 송신자는 rcv_base만 기억하면 됨
• 순서에 맞지 않는 패킷을 받은 경우 :
  • 버리거나 버퍼에 넣거나 : 구현에 달림
  • 기존에 순서에 맞게 들어온 패킷 중 가장 높은 시퀀스 번호로 ACK 응답

3.4.4 Selective Repeat (SR)

GBN에서는 하나의 패킷 에러로 인해 최대 윈도우 사이즈만큼의 패킷을 다시 보내야 하는 상황이 생길 수 있음
=> 불필요한 재전송으로 성능 이슈 생길 수 있음

특징

• pipelining : 여러 패킷 동시에 보냄
• 수신자는 개별 패킷마다 따로 ACK 처리
  • 필요한만큼 패킷을 버퍼링하여 상위 계층에는 순서에 맞게 전달
• 송신자는,
  • ACK 확인되지 않은 개별 패킷마다 타이머를 작동시킴
    • 타임아웃된 패킷만 따로 재전송
  • N개의 연속적인 시퀀스 번호에 대해 윈도우를 유지
    • 전송중인 패킷은 윈도우 범위 안에 있어야 한다

구체적인 프로토콜

Sender

• 상위 계층에서 데이터 받으면 :
  • 패킷이 받을 수 있는 next available sequence number가 윈도우 범위 내에 있을 때만 재전송
• 패킷 n에 대해 타임아웃 :
  • 패킷 n 재전송하고 타이머 재시작
• 윈도우 범위([sendbase, sendbase + N - 1]) 내 패킷에 대해 ACK(n) 응답 받으면 :
  • 패킷 n을 받은 것으로 마킹 처리
  • n이 ACK 처리되지 않은 패킷 중 가장 작은 패킷이라면 window base 번호를 그 다음 ACK 처리되지 않은 패킷의 시퀀스 넘버로 수정한다.

Receiver

• [rcvbase, rcvbase + N - 1] 범위 내의 패킷 n을 받은 경우 :
  • ACK(n)으로 응답
  • 순서에 맞는 시퀀스 번호라면 :
    • (해당 번호 앞의 버퍼링된 순서에 맞는 패킷과 함께) 상위 계층으로 전달
    • window 범위가 그 다음 아직 전송받지 못한 패킷부터 시작하도록 window를 옮긴다
  • 순서에 맞지 않는 시퀀스 번호라면 :
    • 버퍼링
• [rcvbase - N, rcvbase - 1] 범위의 패킷 n을 받은 경우 :
  • ACK(n) 으로 응답
• 그 외 :
  • 무시

[rcvbase - N, rcvbase - 1] 범위에 대해서는 다시 ACK(n) 해주는 이유

rcvbase 번호 밑의 모든 패킷을 receiver가 받아서 ACK 응답을 했더라도 최악의 경우 sender는 ACK 응답을 하나도 받지 못했을 수도 있다.
이 경우 sender는 패킷을 재전송하게 된다.
이 때 receiver가 이미 받은 패킷이기 때문에 무시한다면 sender의 window는 앞으로 나아갈 수 없고, 새 패킷을 전달할 수 없게 된다.
receiver의 rcvbase 값이 주어진 상황에서 sender의 window 범위는 가장 진보하지 못한 상태여도 rcvbase - N 밑으로 내려갈 수는 없을 것이다.
따라서 receiver는 rcvbase - N 까지만 ACK 응답을 하면 된다.

window 사이즈의 제약

sender와 receiver가 공유하는 패킷 전달 상황 정보의 격차로 인해 window 사이즈에도 제약이 생길 수 있다.
예시를 통해 이유를 살펴보자.
sequnce number는 0, 1, 2, 3이 반복되고 window 사이즈는 4를 가정한다.

• 상황 1 :
  • sender가 패킷 0, 패킷 1, 패킷 2 전송
  • receiver가 이를 전부 받고 ACK 응답을 모두 보냈지만 sender는 하나도 받지 못 함
  • sender timeout으로 패킷 0(기존)을 재전송
• 상황 2 :
  • sender가 패킷 0, 패킷 1, 패킷 2 전송
  • receiver가 이를 전부 받고 ACK 응답 모두 보냄
  • sender가 패킷 3, 패킷 0(기존 패킷 0과 다른 새 패킷)을 보냄
  • 패킷 3은 유실되어 receiver는 패킷 0만 받음
    두 케이스 모두 receiver 입장에서는 패킷 0, 패킷 1, 패킷 2, 패킷 0의 sequence number를 받은 것으로 동일하다.
    따라서 이런 상황에서는 두번째로 받은 패킷 0이 window가 진전하여 받은 새로운 패킷인지 (sequence number가 한 차례 순환을 돌게된 상황), ACK 확인이 안 된 패킷을 재전송한 것인지 구분할 수 없게 된다.

=> 필요한 제약 : $\text{window size} <= (\text{sequence 범위 크기 절반})$
위의 예시에서 window size를 2로 줄여보자.

• sender가 패킷 0, 패킷 1 전송
• receiver가 전부 받아서 ACK 처리
• (ACK 응답 수신에 대한 모든 경우의 수를 고려했을 때)sender가 보낼 수 있는 패킷 중 sequence number가 겹치는 것 X