3.4 신뢰적인 데이터 전송의 원리

신뢰적인 데이터 전송을 구현하는 문제는 트랜스포트 계층뿐만 아니라 링크 계층과 애플리케이션 계층에서도 발생할 수 있는 문제이다.

따라서 이 절에서는 일반적인 상황에서의 신뢰적인 데이터 전송 문제를 다룬다.

신뢰적인 데이터 전송 연구의 프레임워크는 다음과 같다.

a. 서비스 모델

b. 서비스 구현

상위 계층 객체에게 제공되는 서비스 추상화는 / 데이터가 전송될 수 있는 신뢰적인 채널의 서비스 추상화다.

신뢰적인 채널에서는 전송된 데이터가 손상되거나 손실되지 않으며,

모든 데이터는 전송된 순서 그대로 전달된다.

= TCP가 인터넷 애플리케이션에게 제공하는 서비스 모델

신뢰적인 데이터 전송 프로토콜(reliable data transfer protocol)의 의무는 신뢰적인 채널의 서비스 추상화를 구현하는 것이다.

이 절에서는 점점 복잡해지는 하위 채널 모델을 고려하여 신뢰적인 데이터 전송 프로토콜의 송신자 측면과 수신자 측면을 점진적으로 개발해나간다.

논의 과정 중 채택할 한 가지 가정 : 패킷은 순서대로 전달된다. (하부 채널은 패킷의 순서를 바꾸지 않음)

위 두 가지 그림 중 b는 데이터 전송 프로토콜의 인터페이스를 나타낸다.

데이터 전송 프로토콜의 송신 측은 rdt_send() 호출로 위쪽으로부터 호출될 것이며, 수신 측에서는 상위 계층으로 전달될 데이터를 넘길 것이다.

rdt : 신뢰적인 데이터 전송(reliable data transfer) 프로토콜을 나타낸다.
_send : rdt의 송신 측이 호출되고 있음을 나타낸다.

수신 측에서 rdt_rcv()는 패킷이 채널의 수신 측으로부터 도착했을 때 호출된다.

rdt 프로토콜이 상위 계층에 데이터를 전달하려고 할 때 deliver_data()를 호출한다.

이 절에서는 단방향 데이터 전송(unidirectional data tranfer)의 경우인 송신 측으로부터 수신 측까지의 데이터 전송만을 고려한다.

양방향(전이중) 데이터 전송(bidirectional data transfer)의 설명은 상당히 복잡하다.

단방향 데이터 전송만 생각하더라도 프로토콜의 송신 측과 수신 측이 양방향으로 패킷을 전달할 필요가 있다.

즉, rdt의 송신 측과 수신 측은 전송 데이터를 포함하는 패킷을 교환하는 것 외에 제어 패킷을 양쪽으로 전송해야 한다.

rdt의 송신 측과 수신 측 모두 udt_send()를 호출함으로써 다른 쪽에 패킷을 전송한다.

udt : 비신뢰적인 데이터 전송(unreliable data transfer)을 나타냄

3.4.1 신뢰적인 데이터 전송 프로토콜의 구축

유한상태 머신(finite-state machine, FSM)에 대한 정의

화살표는 한 상태로부터 다른 상태로의 전이를 나타낸다.

FSM의 초기 상태는 점선 화살표로 표시된다.

전이를 일으키는 이벤트(event)는 변화를 표기하는 가로선 위에 나타낸다.

이벤트가 발생했을 때 취해지는 행동, 액션(action)은 가로선 아래에 나타낸다.

이벤트 발생 시 어떠한 행동도 취해지지 않거나, 어떠한 이벤트 발생 없이 행동이 취해질 때동작이나 이벤트가 없음을 표시하기 위해 각각 가로선 아래나 위에 기호 𝚲를 사용한다.

완벽하게 신뢰적인 채널상에서의 신뢰적인 데이터 전송: rdt1.0

하위 채널이 완전히 신뢰적인 가장 간단한 경우를 고려해보자.

rdt1.0에 대한 FSM

rdt1.0 송신자와 수신자에 대한 유한상태 머신(FSM) 정리는 아래 그림과 같다.

💡 송신자에 대해 그리고 수신자에 대해 분리된 FSM이 있다

a는 송신자(sender)의 동작에 대한 정의

b는 수신자(receiver)의 동작에 대한 정의

rdt1.0에서 각각의 FSM은 하나의 상태만을 가지므로, 전이는 필연적으로 그 상태로부터 자신으로 되돌아온다.

송신자

rdt_send(data) 이벤트에 의해

(이 이벤트는 상위 계층 애플리케이션의 프로시저 호출(e.g., rdt_send())에 의해 발생)

상위 계층으로부터 데이터를 받아들이고
데이터를 포함한 패킷을 생성한다. (make_pkt(data))

그러고 난 후 패킷을 채널로 송신한다.

수신자

rdt는 rdt_rcv(packet) 이벤트에 의해 하위의 채널로부터 패킷을 수신한다. : 이 이벤트는 하위 계층 프로토콜로부터의 프로시저 호출(e.g., rdt_rcv())에 의해 발생한다.

패킷으로부터 데이터를 추출하고 (extract(packet, data))

데이터를 상위 계층으로 전달한다. (deliver_data(data))

여기서는 데이터 단위와 패킷의 차이점이 없으며, 모든 패킷 흐름은 송신자로부터 수신자까지다.

💡 완전히 신뢰적인 채널에서는 오류가 생길 수 없으므로 수신 측이 송신 측에게 어떤 피드백(feedback)도 제공할 필요가 없다.

또한, 수신자는 송신자가 데이터를 송신하자마자 데이터를 수신할 수 있다고 가정하였다.

따라서 수신자가 송신자에게 천천히 보내라는 것을 요청할 필요가 없다.

비트 오류가 있는 채널상에서의 신뢰적인 데이터 전송: rdt2.0

패킷 안의 비트들이 하위 채널에서 손상되는 모델이다.

일반적으로 이러한 비트 오류는 패킷이 전송 도는 전파되거나 버퍼링될 때 네트워크의 물리적인 구성요소에서 발생한다.

자동 재전송 요구(Automatic Repeat reQuest, ARQ) 프로토콜

긍정 확인응답(positive acknowledgment, “OK”)

부정 확인응답(negative acknowledgment, “그것을 반복해주세요”)

이러한 제어 메시지는 정확하게 수신되었는지 또는 잘못 수신되어 반복이 필요한지를 수신자가 송신자에게 알려줄 수 있게 한다.

비트 오류를 처리하기 위해 기본적으로 다음과 같은 세 가지 부가 프로토콜 기능이 ARQ 프로토콜에 요구된다.

오류 검출

비트 오류가 발생했을 때 수신자가 검출할 수 있는 기능이 필요하다. → checksum

이러한 기술은 수신자가 패킷 비트 오류를 검출하고 복구할 수 있게 해준다.

수신자 피드백

송신자가 수신자의 상태를 알기 위한 유일한 방법은 수신자가 송신자에게 피드백을 제공하는 것이다.

수신자의 상태 : 패킷이 정확하게 수신되었는지 아닌지 등

e.g., rdt2.0 프로토콜에서은 수신자로부터 송신자 쪽으로 ACK와 NAK 패킷들을 전송할 것이다.

긍정 확인 응답(ACK)

부정 확인 응답(NAK)

→ 이러한 패킷은 단지 한 비트 길이면 된다. (0 또는 1)

재전송

수신자에서 오류를 가지고 수신된 패킷은 송신자에 의해 재전송(retransmit)된다.

rdt2.0에 대한 FSM

송신자

2개의 상태가 존재한다.

왼쪽 상태에서 송신 측 프로토콜은 상위 계층으로부터 데이터가 전달되기를 기다린다.

rdt_sent(data) 이벤트가 발생하면,

송신자는 패킷 체크섬과 함께 전송될 데이터를 포함하는 패킷(sndpkt)을 생성하고,
그 패킷을 udt_send(sndpkt) 동작을 통해 전송한다.

오른쪽 상태에서 송신자 프로토콜은 수신자로부터의 ACK 또는 NAK 패킷을 기다린다.

만약 ACK 패킷이 수신된다면 (rdt_rcv(rcvpkt) && isACK(rcvpkt))

가장 최근에 전송된 패킷이 정확하게 수신되었음을 의미한다.

따라서 프로토콜은 상위 계층으로부터 데이터를 기다리는 상태로 돌아간다.

만약 NAK가 수신된다면

프로토콜은 마지막 패킷을 재전송한다.
재전송된 데이터 패킷에 대한 응답으로 수신자에 의해 응답하는 ACK 또는 NAK를 기다린다.

rdt2.0과 같은 프로토콜은 전송 후 대기(stop-and-wait) 프로토콜이다.

💡 송신자가 ACK 또는 NAK를 기다리는 상태에 있을 때, 상위 계층으로부터 더 이상의 데이터를 전달받을 수 없다.

즉, rdt_send() 이벤트는 발생할 수 없으며, 이는 오직 송신자가 ACK를 수신하고 이 상태를 떠난 후에 발생할 것이다.

따라서 송신자는 수신자가 현재의 패킷을 정확하게 수신했음을 확신하기 전까지 새로운 데이터를 전달하지 않는다.

수신자

단일 상태를 갖는다.

패킷이 도착했을 때, 수신자는 수신된 패킷이 손상되었는지 아닌지에 따라 ACK 또는 NAK로 응답한다.

rdt2.0의 결함

여기서는 ACK 또는 NAK 패킷이 손상될 수 있다는 가능성을 고려하지 않았다.

만약 ACK 또는 NAK가 손상되었다면, 송신자는 수신자가 전송된 데이터의 마지막 부분을 올바르게 수신했는지를 알 방법이 없다.

대안 1 : 송신자가 검출뿐만 아니라 비트 오류로부터 회복할 수 있도록 충분한 체크섬 비트들을 추가한다.

이 방식은 패킷이 손상될 수 있으나 손실되지는 않는 채널의 경우에는 즉각적으로 문제를 해결할 수 있다.

대안 2 : 송신자가 왜곡된 ACK 또는 NAK 패킷을 수신할 때 현재 데이터 패킷을 단순히 다시 송신한다.

그러나 이 방식은 송신자에게 수신자 간의 채널로 중복 패킷(duplicate packet)을 전송한다.

송신자 입장에서는 마지막으로 전송된 ACK 또는 NAK가 송신자에게 정확하게 수신됐는지를 알 수 없다.

수신자 입장에서는 도착하는 패킷이 새로운 데이터를 포함하고 있는 것인지 아니면 재전송인지를 사전에 알 수 없다.

해결책

💡 데이터 패킷에 새로운 필드를 추가하고 이 필드 안에 순서 번호(sequence number)를 삽입하는 방식으로 데이터 패킷에 송신자가 번호를 붙인다.

이는 현존하는 데이터 전송 프로토콜에 채택된 방법이다.

수신자는 수신된 패킷이 재전송인지를 결정할 때는 이 순서 번호만 확인하면 된다.

rdt2.0의 수정 버전: rdt2.1

rdt2.1은 rdt2.0보다 두 배 많은 상태를 가지고 있다.

이는 아래의 2가지를 반영해야 하기 때문이다.

프로토콜 상태가 현재 (송신자에 의해) 전송되고 있는지에 대한 반영

(수신자가) 기다리고 있는 패킷이 순서 번호 0 또는 1을 가져야 하는지에 대한 반영

프로토콜 rdt2.1은 수신자로부터 송신자까지의 긍정 확인응답과 부정 확인응답을 모두 포함한다.

순서가 바뀐 패킷이 수신되면, 수신자는 이미 전에 수신한 패킷에 대한 긍정 확인응답을 전송한다.

손상된 패킷이 수신되면, 수신자는 부정 확인응답을 전송한다.

NAK를 송신하는 것 대신에,

가장 최근에 정확하게 수신된 패킷에 대해 ACK를 송신함으로써 NAK를 송신한 것과 같은 효과를 얻을 수 있다.

즉, 같은 패킷에 대해 2개의 ACK를 수신(즉, 중복(duplicate) ACK를 수신)한 송신자는

수신자가 두 번 ACK 한 패킷의 다음 패킷을 정확하게 수신하지 못했다는 것을 알게 된다. (NAK의 의미와 동일)

rdt2.1에 대한 FSM

송신자

수신자

비트 오류를 갖는 채널을 위한 NAK 없는 신뢰적인 데이터 전송 프로토콜 : rdt2.2

rtd2.2는 rdt2.1과 다르게,

수신자가 반드시 ACK 메시지에 의해 확인 응답되는 패킷의 순서 번호를 포함해야 한다.

이는 수신자 FSM의 make_pkt()에 ACK, 0 또는 ACK, 1인 인수를 넣어서 수행한다.

송신자는 수신된 ACK 메시지에 의해 확인응답된 패킷의 순서 번호를 반드시 검사해야만 한다.

이는송신자 FSM의 isACK()에 0 또는 1인 인수를 넣어서 수행한다.

rdt2.2에 대한 FSM

송신자

수신자

#비트 오류와 손실 있는 채널상에서의 신뢰적인 데이터 전송: rdt3.0

하위 채널이 패킷을 손실하는 경우도 생각해보자.

다음과 같은 두 가지 부가 내용을 프로토콜이 다루어야 한다.

어떻게 패킷 손실을 검출할 것인가?

패킷 손실이 발생했을 때 어떤 행동을 할 것인가?

💡 송신자에게 손실된 패킷의 검출과 회복 책임을 부여한다.

송신자가 데이터 패킷을 전송하고, 패킷 또는 수신자의 패킷에 대한 ACK를 손실했다고 가정하자.

어느 경우에서나 송신자에게는 수신자로부터 어떠한 응답도 없다.

즉, 송신자는 데이터 패킷이 손실되었는지, ACK가 손실되었는지, 패킷 또는 ACK가 단순히 지나치게 지연된 것인지를 알지 못한다.

만약 송신자가 패킷을 잃어버렸다고 확신할 정도로 충분한 시간을 기다릴 수만 있다면, 데이터 패킷은 간단하게 재전송될 수 있다.

그러나 송신자가 어떤 패킷을 손실했다는 것을 확신하기 위해 얼마나 오랫동안 기다려야 할까?

송신자는 적어도 다음의 시간만큼을 기다려야 한다.

송신자와 수신자 사이의 왕복 시간 지연(중간 라우터에서의 버퍼링을 포함) + 수신 측에서 패킷을 처리하는 데 필요한 시간

실제 상황에서 채택한 접근 방식은 이와 같다.

💡 패킷 손실이 일어났을 만한 그런 시간을 선택하여, 만일 ACK가 이 시간 안에 수신되지 않는다면 패킷은 재전송된다.

이것은 송신자 대 수신자 채널에서 중복 데이터 패킷(duplicate data packet)의 가능성을 포함하나,

프로토콜 rdt2.2에서처럼 패킷의 순서 번호를 통하여 처리가 가능하다.

시간 기반의 재전송 메커니즘을 구현하기 위해서는
주어진 시간이 지난 후에 송신자를 인터럽트(중단)할 수 있는 카운트다운 타이머(countdown timer)가 필요하다.

그러므로 송신자는 다음처럼 동작해야 한다.

매 패킷(첫 번째 또는 재전송 패킷)이 송신된 시간에 타이머를 시작한다.

타이머 인터럽트에 반응한다. (즉, 적당한 행동을 취함)

타이머를 멈춘다.

rdt3.0에 대한 FSM

송신자

동작과 처리 과정

아래의 4가지 다이어그램은 프로토콜이 패킷 손실 또는 지연 없이 어떻게 동작하는지와 손실된 데이터 패킷을 어떻게 처리하는지를 나타낸 것이다.

시간은 다이어그램의 위로부터 아래로 흐른다.

패킷에 대한 수신 시간은 전송 지연과 전파 지연 때문에 패킷 전송 시간보다 더 늦다.

패킷의 순서 번호가 0과 1이 번갈아 일어나기 때문에 프로토콜 rdt3.0은 얼터네이팅 비트 프로토콜(alternating-bit protocol)이라고 부른다.

무손실 동작

패킷 손실

ACK 손실

조급한 타임아웃

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

프로토콜 rdt3.0은 기능적으로는 정확한 프로토콜이나, 오늘날의 고속 네트워크에서 누구나 이것의 성능에 만족하는 것은 아니다.

💡 rdt3.0의 핵심적인 성능 문제는 전송 후 대기(stop-and-wait) 프로토콜이라는 점 때문에 발생한다.

전송 후 대기 프로토콜은 형편없는 송신자 이용률(utilization, 또는 효율)을 갖는다.

이에 대한 해결책은 다음과 같다.

송신자에게 확인응답을 기다리기 전에 송신을 전송하도록 허용하는 것이다. = 파이프라이닝(pipelining)

즉, 많은 전송 중인 송신자-수신자 패킷을 파이프라인에 채워 넣는 것이다.

아래의 그림들을 통해 만약 확인응답들을 기다리기 전에 송신자가 3개의 패킷을 전송하도록 허용한다면

송신자의 이용률은 3배가 되리라는 것을 볼 수 있다.

즉, window size 만큼 효율이 증가한다는 것이다.

전송 후 대기 동작

파이프라이닝된 동작

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

순서 번호의 범위가 커져야 한다.

각각의 전송 중인 패킷은 유일한 순서 번호를 가져야 한다.

전송 중인 확인응답(ACK)이 안 된 패킷이 여럿 있을지도 모르기 때문이다.

프토로콜의 송신 측과 수신 측은 패킷 하나 이상을 버퍼링해야 한다.

최소한 ‘송신자는 전송되었으나 확인응답되지 않은 패킷’을 버퍼링해야 한다.

정확하게 수신된 패킷의 버퍼링은 수신자에게서도 필요하다.

필요한 순서 번호의 범위와 버퍼링 조건은 데이터 전송 프로토콜이 손실 패킷과 손상 패킷 그리고 상당히 지연된 패킷들에 대해 응답하는 방식에 달려 있다.

파이프라인 오류 회복의 두 가지 기본적인 접근 방법

GBN(Go-Back-N) : N부터 반복

SR(Selective Repeat) : 선택적 반복

3.4.3 GBN

💡 GBN(Go-Back-N, N부터 반복) 프로토콜에서 송신자는 확인 응답을 기다리지 않고 여러 패킷을 전송(가능할 때)할 수 있다.

그러나 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크지 말아야 한다.

아래 그림은 GBN 프로토콜에서 송신자 관점의 순서 번호 범위를 보여준다.

확인응답이 안 된 가장 오래된 패킷의 순서 번호를 base로 정의한다.

가장 작은 순서 번호를 nextseqnum(전송될 다음 패킷의 순서 번호)으로 정의한다.

이를 통해서 순서 번호의 범위에서 4개의 간격을 식별할 수 있다.

간격 [0, base-1] : 순서 번호는 이미 전송되고 확인응답이 된 패킷

간격 [base, nextseqnum-1] : 송신은 되었지만 아직 확인응답되지 않은 패킷

간격 [nextseqnum, base+N-1] : 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷

base+N 이상

→ 파이프라인에서 확인응답이 안 된 패킷(특히, 순서 번호 base를 가진 패킷)의 확인응답이 도착할 때까지 사용될 수 없다.

슬라이딩 윈도 프로토콜(sliding-window protocol)

전송되었지만 아직 확인응답이 안 된 패킷을 위해,
허용할 수 있는 순서 번호의 범위는 순서 번호의 범위상에서 크기가 N인 ‘윈도(window)’로 나타낸다.

프로토콜이 동작할 때, 이 윈도는 순서 번호 공간에서 오른쪽으로 이동(slide)된다.

N = 윈도 크기(window size)

따라서 GBN 프로토콜은 슬라이딩 윈도 프로토콜(sliding-window protocol)이라고 부른다.

패킷의 순서 번호

실제로 패킷의 순서 번호는 패킷 헤더 안의 고정된 길이 필드에 포함된다.

만약 k가 패킷 순서 번호 필드의 비트 수라면, 순서 번호의 범위는 [0, 2^k - 1]

순서 번호의 제한된 범위에서, 순서 번호를 포함하는 모든 계산은 모듈로(modulo) 2^k 연산을 이용한다.

ACK 기반의 NAK 없는 확장된(extended) FSM

base와 nextseqnum 변수를 추가한다.

이러한 변수에서의 동작과 이러한 변수를 포함하는 조건부 동작을 추가한다.

송신자

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

1️⃣ 상위로부터의 호출

rdt_send()가 위로부터 호출되면, 송신자는 우선 윈도가 가득 찼는지 확인한다.

(즉, N개의 아직 확인응답되지 않은 패킷이 있는지를 확인)

만약 윈도가 가득 차 있지 않다면 패킷이 생성되고 송신되며, 변수들이 적절하게 갱신된다.

만약 윈도가 가득 차 있다면, 단지 데이터를 상위 계층으로 반환한다.

이는 윈도가 가득 차 있음을 가리키는 함축적인 의미이다.

따라서 상위 계층은 나중에 rdt_send()를 다시 시도할 것이다.

실제적인 구현에서 송신자는 아래와 같은 방법을 사용할 것이다.

이 데이터를 버퍼링한다. (그러나 즉시 송신하진 않음)

오직 윈도가 가득 차 있지 않을 때만 rdt_send()를 호출하는 동기화 메커니즘을 사용한다.(e.g., semaphore 또는 flag)

2️⃣ ACK의 수신

GBN 프로토콜에서

순서 번호 n을 가진 패킷에 대한 확인응답은 누적 확인응답(cumulative acknowledgment)으로 인식된다.

이 누적 확인 응답은 수신 측에서 올바르게 수신된 n을 포함하여, n까지의 순서 번호를 가진 모든 패킷에 대한 확인 응답이다.

3️⃣ 타임아웃 이벤트

타이머는 손실된 데이터 또는 손실된 확인응답 패킷으로부터 회복하는 데 사용된다.

만약 타임아웃이 발생한다면, 송신자는 이전에 전송되었지만 아직 확인응답되지 않은 !!모든!! 패킷을 다시 송신한다.

위의 그림에서 송신자는

가장 오래된 ‘전송했지만, 아직 확인응답 안 된 패킷’에 대한 타이머로 생각될 수 있는 단일 타이머를 사용한다.

만일 한 ACK가 수신되었지만, 추가로 ‘전송했지만, 아직 확인응답 안 된 패킷’이 아직 존재한다면, 타이머를 다시 시작한다.

만약 아직 확인응답 안 된 패킷이 없다면, 타이머를 멈춘다.

수신자

만약 순서 번호 n을 가진 패킷이 오류 없이, 그리고 순서대로 수신된다면

(= 상위 계층에 마지막으로 전달된 데이터가 순서 번호 n-1을 가진 패킷에서 온 것이라면)

수신자는 패킷 n에 대한 ACK를 송신하고 상위 계층에 패킷의 데이터 부분을 전달한다.

그 외의 경우에는 수신자는 그 패킷을 버리고 가장 최근에 제대로 수신된 순서의 패킷에 대한 ACK를 재전송한다.

GBM 프로토콜에서 수신자는 순서가 잘못된 패킷들을 버린다.

지금 패킷 n이 수신되어야 하지만, 그 사람 다음의 패킷 n+1이 먼저 도착했다고 가정하자.

수신자는 상위 계층에 데이터를 전달해야 한다.

데이터가 순서대로 전달되어야 하므로, 수신자는 패킷 n+1을 저장하고

나중에 패킷 n이 수신되고 전달된 후에 상위 계층에 이 패킷을 전달한다.

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

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

송신자가 유지해야 하는 것

윈도 상위와 하위 경계

이 윈도 안에 있는 nextseqnum 위치

수신자가 유지해야 하는 것 : 다음 순서 패킷의 순서 번호

물론, 올바르게 수신된 패킷을 버리는 것의 단점은 그 패킷의 재전송이 손실되거나 왜곡될 수 있으므로 많은 재전송이 필요할 수도 있다는 것이다.

아래 그림은 윈도 크기가 4 패킷인 경우에 대한 GBN 프로토콜의 동작을 보여준다.

윈도 크기가 4 → 송신자는 패킷 0부터 3까지 송신한다.

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

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

윈도는 앞으로 이동한다.

송신자는 하나의 새로운 패킷(pkt4와 pkt5, 각각)을 전송한다.

수신 측에서는 pkt2가 손실되었으므로 pkt3, 4, 5는 순서가 잘못된 패킷으로 발견되어 제거된다.

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

앞에서 본, 확장된(extended) FSM을 다시 떠올려보자.

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

이러한 이벤트 기반 프로그래밍(event-based programming)에서의 다양한 프로시저들은
프로토콜 스택에서 다른 프로세저에 의해 야기되거나 인터럽트의 결과로 요청될 것이다.

송신자에서 이러한 이벤트들에 대한 예시로는 다음과 같다.

rdt_send()를 호출하기 위한 상위 계층 개체로부터의 호출

타이머 인터럽트

패킷이 도착했을 때 rdt_rcv()를 호출하기 위한 하위 계층으로부터의 호출

GBN 프로토콜의 성능 문제

GBN 프로토콜은 송신자가 패킷으로 파이프라인을 채우는 것을 통해 전송 후 대기 프로토콜에서의 채널 이용률 문제를 피하도록 하였다.

그러나 GBN 자체에는 성능 문제를 겪는 시나리오들이 존재한다.

윈도 크기와 대역폭 지연(bandwidth-delay) 곱의 결과가 모두 클 때, 많은 패킷이 파이프라인에 있을 수 있다.

GBN은 패킷 하나의 오류 때문에 많은 패킷을 재전송하므로, 많은 패킷을 불필요하게 재전송하는 경우가 발생한다.

채널 오류의 확률이 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워진다.

3.4.4 SR

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

이를 통해서 SR는 불필요한 재전송을 피한다.

필요에 따라 각각의 개별적인 재전송은 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답을 요구할 것이다.

윈도 크기 N은 파이프라인에서 아직 확인응답이 안 된 패킷 수를 제한하는 데 사용된다.

그러나 GBN과는 달리, 송신자는 윈도에 있는 몇몇 패킷에 대한 ACK를 이미 수신했을 것이다.

순서 번호 공간에 대한 SR 송신자의 관점

SR 수신자는 패킷의 순서와는 무관하게 손상 없이 수신된 패킷에 대한 확인응답을 할 것이다.

빠진 패킷이 존재하는 경우

순서가 바뀐 패킷은 빠진 패킷이 수신될 때까지 버퍼에 저장하고,(빠진 패킷 = 아직 도착하지 않은 더 낮은 순서 번호를 가진 패킷)

빠진 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위 계층에 전달할 수 있다.(re-order & reassemble the packets → in-order delivery to upper layer)

SR 송신자 이벤트와 행동

1️⃣ 상위로부터 데이터 수신

상위에서 데이터가 수신될 때, SR 송신자는 패킷의 다음 순서 번호를 검사한다.

순서 번호가 송신자 윈도 내에 있으면 데이터는 패킷으로 송신된다.

그렇지 않으면 GBN처럼 버퍼에 나중에 전송하기 위해 되돌려진다.

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️⃣ 그 외의 경우, 패킷을 무시한다.

SR 동작

처음에 pkt3, 4, 5를 버퍼에 저장한다.

마지막으로 pkt2가 수신되었을 때 pkt2와 함께 상위 계층에 전달한다.

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

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

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

e.g.,

송신자와 수신자의 순서 번호 공간을 줬을 때, 수신자가 송신자에게 보내는 send_base 패킷에 대한 ACK가 없다면

(우리에게는 수신자가 그 패킷을 이미 수신했음이 분명하더라도) 결국 송신자는 send_base 패킷을 재전송할 것이다.

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

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

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

송신자와 수신자 윈도 사이의 동기화 부족은 순서 번호의 한정된 범위에 직면했을 때 중대한 결과를 가져온다.

e.g.,

한정된 범위의 네 패킷 순서 번호 0, 1, 2, 3

윈도 크기 : 3

0부터 2까지의 패킷이 전송되어 올바로 수신되고, 수신자에게서 확인이 되었다고 가정하자.

그 순간에 수신자의 윈도는 각각의 순서 번호가 3, 0, 1인 4, 5, 6번째 패킷에 있다.

첫 번째 시나리오

처음 3개의 패킷에 대한 ACK가 손실되고, 송신자는 이 패킷을 재전송한다.

수신자는 순서 번호가 0인 패킷(처음 보낸 패킷의 복사본)을 수신한다.

두 번째 시나리오

처음 3개의 패킷에 대한 ACK가 모두 올바르게 전달되었다.

송신자는 자신의 윈도를 앞으로 이동시켜, 각각의 순서 번호가 3, 0, 1인 4, 5, 6번째 패킷을 보낸다.

순서 번호 3을 가진 패킷이 손실되고, 순서 번호 0을 가진 패킷(새로운 데이터를 포함한 패킷)은 도착한다.

수신자 관점을 고려해보자

수신자는 송신자의 행동을 볼 수 없다.

모든 수신자는 채널을 통해 받고, 채널을 통해 보내는 메시지의 순서를 관찰하는데, 이는 위의 두 가지 시나리오가 똑같다.

즉, 다섯 번째 패킷의 원래 전송과 첫 번째 패킷의 재전송을 구별할 방법은 없다.

최소한의 윈도 크기는 얼마인가?

윈도 크기는 SR 프로토콜에 대한 순서 번호 공간 크기의 절반보다 작거나 같아야 한다.

패킷 순서 바뀜 현상

맨 앞에서 패킷들은 송신자와 수신자 사이의 채널 안에서 순서가 바뀔 수 없다는 가정 하에 신뢰적인 데이터 전송 프로토콜에 대한 설명을 진행하였다.

이는 일반적으로 송신자와 수신자가 단일한 물리적 선으로 연결되어 있을 때 적합한 가정이다.
하지만 둘을 연결하는 ‘채널’이 네트워크일 때는 패킷 순서 바뀜이 일어날 수 있다.

패킷 순서 바뀜 현상으로, 송신자와 수신자의 윈도가 x를 포함하지 않고 있더라도

순서 번호 또는 확인응답 번호 x를 가진 오래된 패킷의 복사본들이 생길 수 있다.

패킷 순서가 바뀌는 채널이라는 것은 본질적으로 패킷들을 버퍼에 저장하고, 나중에 어느 때나 이 패킷들을 임의로 내보낸다고 간주할 수 있다.

순서 번호가 재사용될 수 있으므로 그런 중복된 패킷들을 막을 수 있는 조치가 필요하다.

실제 방식은 송신자가 이전에 송신된 순서 번호 x를 가진 패킷들이

더는 네트워크 상에 없음을 어느 정도 ‘확신’할 때까지 순서 번호가 재사용되지 않음을 확실히 하는 것이다.

이는 패킷이 어느 일정 시간 이상으로 네트워크에서 존재할 수 없다는 가정에 의해 이루어진다.

신뢰적인 데이터 전송 메커니즘과 그 사용에 대한 요약

체크섬

전송된 패킷 안의 비트 오류를 발견하는 데 사용된다.

타이머

채널 안에서 패킷이 손실되었기 때문에 발생되는 패킷(또는 이것의 ACK)의 타임아웃/재전송에 사용된다.

타임아웃

발생 이유

패킷이 지연되었지만 손실되지는 않았을 경우 (조기 타임 아웃)

패킷이 수신자에 의해 수신되었으나 수신자에서 송신자로의 ACK가 손실되었을 경우

→ 수신자에 의해 수신되는 패킷은 중복으로 복사(수신)된 패킷일 수 있다.

순서 번호

송신자에서 수신자로 가는 데이터 패킷의 순서 번호를 붙이기 위해 사용된다.

수신자 패킷의 순서 번호의 간격 : 수신자가 손실된 패킷을 검사하게 한다.

중복된 순서 번호를 갖는 패킷 : 수신자가 패킷의 중복 복사를 검사하게 한다.

확인응답

수신자가 한 패킷 또는 패킷 집합이 정확히 수신되었다는 응답을 송신자에게 하기 위해 사용된다.

일반적으로 패킷 또는 이미 확인응답된 패킷들의 순서 번호를 전달한다.

프로토콜에 따라 개별적이거나 누적된 것일 수 있다.

부정 확인응답

수신자가 패킷이 정확히 수신되지 않았다는 응답을 송신자에게 하기 위해 사용된다.

일반적으로 정확히 수신되지 않은 패킷의 순서 번호를 전달한다.

윈도, 파이프라이닝

송신자는 주어진 범위에 있는 순서 번호를 가진 패킷만 전송하도록 제한될 수 있다.

확인응답은 없지만 허가된 패킷이 전송될 수 있으므로, 송신자의 이용률은 전송 후 대기 모드의 동작보다 증가할 수 있다.

윈도 크기는 수신자의 메시지를 수신하고 버퍼링하는 능력, 네트워크의 혼잡 정도, 또는 두 가지 모두에 근거하여 설정된다.

3.4 신뢰적인 데이터 전송의 원리 - Computer Network