Principles of reliable data transfer

상위 문서: Transport Layer

개요

Figure 1. Reliable data transfer

신뢰성있는 데이터 전송(Reliable data transfer)을 구현하는 문제는 네트워크 학문에서 굉장히 중요한 문제이다. 신뢰성있는 데이터 전송의 개념적인 틀은 figure 1이 잘 보여주고 있다.
상위 layer에게 제공되는 서비스 abstraction은 데이터를 전송할 수 있는 신뢰성있는 데이터 전송 채널의 형태이다. 이러한 채널에서는 전송되는 데이터 bit들이 손상되지 않고, 누락되지 않으며, 전송한 순서대로 수신된다. 신뢰성있는 데이터 전송 프로토콜은 이러한 서비스를 제공해야 한다. 하지만 해당 작업은 어려운데, 해당 프로토콜이 수행되는 layer는 신뢰할 수 없는 network layer 위에서 구현되기 때문이다.

위 그림은 해당 문서에 다룰 데이터 전송 프로토콜의 인터페이스이다. 이때 그림에 나타난 함수들은 다음과 같다:

• 송신 측
  • rdt_send(): 상위 layer에서 호출되어, 수신측 상위 layer에 전달할 데이터를 넘겨준다.
  • udt_send(): 송신측이 채널에 패킷을 전송하고자 할 때 호출된다.
• 수신측
  • rdt_rcv(): 채널에서 패킷이 도착했을 때 호출된다.
  • deliver_data(): rdt 프로토콜이 상위 계층에 데이터를 넘기고자 할 경우 호출된다.

해당 문서에서는 신뢰성있는 데이터 전송 프로토콜을 만들고자 한다. 이때 "패킷은 전송된 순서대로 도착하지만, 일부는 손실될 수 있다."는 가정을 전제로 할 것이다. 또한 송신측과 수신측이 고정되어 있지만 control 패킷은 양방향으로 전달되어야 하므로, 송신측과 수신측은 모두 udt_send()를 통해 상대방에게 패킷을 전송한다. 그리고 transport layer에서 사용되는 용어인 segment 대신 패킷(packet)을 사용한다. 왜냐하면 해당 문서의 내용은 인터넷의 transport layer뿐 아니라 컴퓨터 네트워크 전반에 적용되기 때문이다. 또한 FSM(Finite State Machine)을 통해서 해당 프로토콜을 표현한다.

rdt1.0: reliable transfer over a reliable channel

먼저 기저를 이루는 채널(underlying channel)이 완전히 신뢰할 수 있다고 가정하자. 이는 아래와 같이 매우 단순하게 FSM이 정의된다.

위에서 중요한 점은 송신자와 수신자 각각에 대해 별도의 FSM이 존재한다는 것이다. 이는 rdt 프로토콜이 송신측과 수신측에서 독립적으로 실행되기 때문이다. 또한 FSM에서 화살표는 어떤 상태에서 다른 상태로의 전이(transition)를 나타낸다. 또한 화살표 옆에 있는 구분선을 기준으로 위쪽에는 어떤 event가 발생하였는지가 적혀있고, 아래쪽에는 해당 event가 발생했을 때 수행되는 action이 적혀있다.

rdt의 송신 측은 단순히 상위 계층으로부터 rdt_send(data) 이벤트를 통해 데이터를 받아들이고, make_pkt(data) 동작을 통해 데이터를 포함한 패킷을 생성한 후, 그 패킷을 채널에 전송한다.
수신 측에서는, rdt가 기저 채널로부터 rdt_rcv(packet) 이벤트를 통해 패킷을 수신하고, extract(packet, data) 동작을 통해 패킷에서 데이터를 추출한 뒤, deliver_data(data) 동작을 통해 상위 계층에 데이터를 전달한다.

위의 흐름에서는 완전히 신뢰할 수 있는 채널이 사용되기 때문에 송신자게 수신자가 피드백을 보낼 필요가 없다. 왜냐하면 잘못될 수 있는 일이 없기 때문이다.

rdt2.0: channel with bit errors

이번에는 패킷내의 bit들이 기저 채널에서 손상될 수 있다고 가정하자. Error bit가 발생하였다면 이를 해결하는 방법은 두가지가 있다. 하나는 수신측에서 복잡한 과정을 통해 복구하는 원래의 bit를 복구하는 것이다. 다른 방법은 error bit를 감지하고, 메시지를 다시 전송할 것을 요청하는 것이다. 일반적으로 후자가 훨씬 간단하기 때문에 후자의 방법이 주로 사용된다.
이처럼 수신측의 재전송을 기반으로 하는 rdt 프로토콜을 ARQ라고 하며, 이를 구현하기 위해서는 다음 세가지의 기능이 구현되어야 한다:

• Error detection: 수신자가 비트 오류가 발생했는지를 감지할 수 있는 메커니즘이 필요하다.
  • rdt2.0 데이터 패킷의 checksum feild는 해당 메커니즘을 구현하기 위해서 사용된다.
• Receiver feedback: 수신자는 송신자에게 응답을 보내서 error bit가 전송되었는지의 여부를 알 수 있다.
  • acknowledgement(ACKs)/negative acknowledgement(NAKs): 긍정/부정 응답
• Retransmission: 수신측에서 오류가 발생한 패킷은 송신자가 해당 패킷을 재전송한다.

송신측 FSM에는 두개의 상태가 있다.
왼쪽 상태에서는, 송신 측은 상위 계층으로부터 데이터가 도착하기를 기다린다. rdt_send(data) 이벤트가 발생하면, 송신자는 데이터를 포함하는 패킷(sndpkt)을 만들고, 여기에 체크섬(checksum)을 추가한 뒤, udt_send(sndpkt) 동작을 통해 채널로 전송한다.
이후 오른쪽 상태로 이동하고, 송신자는 수신자로부터 ACK 또는 NAK 패킷을 기다린다. ACK를 수신하면 송신자는 가장 최근에 보낸 패킷이 올바르게 도착했음을 확인하고, 다시 상위 계층 데이터 대기 상태로 돌아간다. NAK를 수신하면 마지막으로 보낸 패킷을 재전송하고 ACK 또는 NAK 응답을 다시 기다린다.

수신측 FSM은 여전히 하나의 상태만 가지고 있다.
패킷이 도착하면 패킷이 손상됐는지 확인하고 그에 따라 ACK 또는 NAK을 송신자에게 보낸다.

이때 송신자가 ACK 또는 NAK을 기다리는 상태에 있을 때는, 상위 계층으로부터 더 이상 데이터를 받을 수 없다. 즉, 이 상태에서는 rdt_send() 이벤트가 발생하지 않는다.(ACK를 받고 이 상태를 벗어난 뒤에야 가능하다.) 이런 동작 때문에 rdt2.0과 같은 프로토콜은 “Stop-and-Wait(정지-대기)” 프로토콜이라고 불린다.

rdt2.1: Consider the case of corrupted ACK/NAK

rdt2.0은 치명적인 결함을 가지고 있다. 그 이유는 rdt2.0은 ACK 또는 NAK 정보가 손상될 가능성(수신측이 송신측에 응답하는 패킷이 손상되었을 가능성)을 고려하지 않았기 때문이다. ACK이나 NAK가 손상되었을 경우는 checksum 기법을 통해서 감지할 수 있다. 하지만 근본적인 문제는 ACK이나 NAK가 손상된 것을 확인하더라도, 송신자는 수신자가 마지막 패킷을 제대로 받았는지 알 수 없다는 것이다. 이 경우 송신측이 수신측에게 동일한 데이터를 보낸다면 수신자는 동일한 데이터를 두 번 받을 수 있고, 어떤 것이 새로운 데이터인지 구분할 수 없어 데이터 오류가 발생할 수도 있다.

이를 해결하기 위한 간단한 방법은 데이터 패킷에 새로운 필드를 추가하여 해당 필드에 시퀸스 번호(sequence number)를 부여하는 것이다. 이때 수신자가 시퀸스 번호만 확인하면, 수신된 패킷이 재전송된 것인지 아닌지를 판별할 수 있다. 즉, ACK 또는 NAK 정보가 손상되거나 NAK 신호를 수신했을 경우, 송신측은 동일한 패킷을 다시 보낸다. 이때 수신측은 해당 패킷의 시퀸스 번호를 통해 중복된 패킷인지 아닌지를 구분하여 중복된 패킷은 폐기하여 패킷 중복 문제를 해결할 수 있다. 해당 rdt2.1 프로토콜의 경우, stop-and-wait 프로토콜이므로, 1bit의 시퀸스 번호만으로도 충분하다. 이는 수신자가 송신자가 이전에 보낸 패킷을 다시 보낸 건지, 아니면 새로운 패킷을 보낸 건지을 판별할 수 있도록 해주기 때문이다.

rdt2.2: a NAK-free protocol

rdt2.2는 rdt2.1과 기능 동일하지만, 효율성의 증대를 위해서 NAK을 사용하지 않고 ACK만 사용한다. NAK 대신, 수신자는 마지막으로 정상 수신한 패킷에 대한 ACK를 전송하며, 이를 위해 ACK에 시퀸스 번호를 명시적으로 포함한다. 이때, 송신자가 수신측으로부터 같은 시퀸스 번호에 대한 ACK를 두 번 받는 경우, NAK과 동일하게 처리하여 현재 패킷을 재전송한다. 예를 들어, 시퀸스 번호가 0과 1만 있다고 가정하자. 송신측이 수신측에게 정상적으로 0번 패킷을 전송하고 1번 패킷을 전송한 후 수신측이 ACK(1)을 답신한다면, 이는 1번 패킷이 정상적으로 전달되었음을 의미한다. 반대로 수신측이 ACK(0)을 전송하였을 때에는 송신측은 1번 패킷을 재전송한다.

rdt3.0: channels with errors and loss

rdt3.0에서는 패킷이 손상되는 경우 외에도 패킷 손실(loss)이 일어나는 상황을 해결한다. rdt2.2 프로토콜은 패킷 손실에 매우 취약하다. 그 이유는 rdt2.2 프로토콜이 stop-and-wait 프로토콜이기 때문에 패킷 손실이 생길 경우 송신측과 수신측 모두 패킷을 들어오기를 영원히 기다리기 때문이다. 패킷 손실을 처리하는 가장 간단한 해결책은 countdown timer을 활용하는 것이다. 송신자는 패킷을 보낸 후 ACK가 돌아오기를 "합리적인" 시간 동안 기다린다. 송신자는 1)데이터 패킷이 손실되었는지, 2)ACK이 손실되었는지, 3)혹은 데이터 패킷이나 ACK이 단지 지연되었는지 모르지만, 모든 경우에 재전송한다. 만약 해당 시간 동안 ACK 응답을 받지 못한다면 다시 해당 패킷을 수신측에 보낸다. 만약 단순히 수신측이 패킷을 정상적으로 수신하였으나 ACK이 손실된 경우에 수신측은 중복된 패킷을 받고, 시퀸스 번호로 이를 판별하여 폐기한다.

위는 rdt3.0이 각각의 경우에 어떠한 방식으로 작동하는지 보여준다. 1~3 번째 이미지는 타이머를 이용하여 큰 문제없이 각 문제 상황을 해결하는 것을 알 수 있다. 4번째 이미지는 ACK가 손실되는 것이 아니라, traffic congestion 등으로 인해 ACK 전송이 지나치게 늦어질 경우 발생하는데, 이와 같은 경우를 premature timeout이라고 한다.

Performance of rdt3.0

Figure 2. rdt3.0 Stop-and-Wait protocol Example

rdt3.0은 정확하고 reliable하지만 그 퍼포먼스는 매우 끔찍하다. 예를 들어, 다음과 같은 상황을 가정하자.

• 초당 10⁹비트(1Gbps)의 전송 속도 R을 가진 link(채널)로 연결되어 있다.
• 송신측과 수신측은 각각 미국 동/서부에 있어 propagation delay가 15ms이고, RTT는 간단히 30ms이라고 하자.
• 전송할 패킷의 크기(L)는 8000bit이다.

이때 transmission delay, 송신자가 실제로 비트를 채널에 전송하고 있는 시간의 비율인 utilization(U_sender)은 아래와 같이 나타낼 수 있다.

$D_{trans}=\frac{L}{R}=\frac{8000bits}{10^{9}bits/sec}=8microsecs$
$U_{sender}=\frac{L\mathbb{ℝ}}{RTT+L/R}=\frac{0.008}{30.008}\approx 0.00027$
$throughput=\frac{L}{RTT+D_{trans}}=\frac{1KB}{30.008msec}\approx 33KB/sec$

즉, 송신자는 전체 시간 중 단지 0.027%만 바쁘게 일하고 있었던 것이다. 또한 1Gbps 링크를 사용했음에도 불구하고 실질적으로는 30.008밀리초 동안 1,000byte만 전송할 수 있었다. 이런 끔찍한 퍼포먼스가 나온 이유는 rdt3.0이 stop-and-wait 프로토콜이기 때문에, 송신측과 수신측의 링크 사이에 단 하나의 패킷만 존재할 수 있기 때문이다.

Pipelined protocols

Figure 3. A pipelined protocol

rdt3.0은 reliable한 데이터 전송을 보장하지만 끔찍하게 느리다. 이를 해결하기 위한 방법은 stop-and-wait 프로토콜을 사용하는 대신, 송신자가 확인 ACK를 기다리지 않고 여러 개의 패킷을 전송할 수 있도록 허용하는 것이다. 위의 이미지는 이 원리를 잘 표여준다. 송신자가 확인 응답을 기다리기 전에 3개의 패킷을 전송할 수 있게 된다면, 송신자의 U_sender가 사실상 3배로 증가한다. 이러한 기법을 pipelining이라고 하는데, figure 3과 같이 송신자에서 수신자로 향하는 다수의 전송 중인 패킷들이 파이프라인을 채우는 것처럼 시각화될 수 있기 때문이다. 이때, pipelining을 구현하는 방식은 두가지가 존재하며, 이는 Go-Back-N과 Selective Repeat이다.

Packet 번호 구간

다음에 전송할 패킷의 시퀸스 번호를 nextseqnum, 가장 오래된 확인되지 않은 패킷의 시퀸스 번호를 base라고 하자. 그러면 시퀸스 번호의 범위는 아래와 같이 4개의 구간으로 나눌 수 있다:

• [0, base-1]: 이미 전송되었고 확인 응답을 받은 패킷들
• [base, nextseqnum-1]: 전송되었지만 아직 확인되지 않은 패킷들
• [nextseqnum, base+N-1]: 즉시 전송 가능한 시퀸스 번호 범위 (상위 계층에서 데이터가 도착하면)
• [base+N 이상]: base에 해당하는 패킷의 ACK이 도착하기 전까지는 전송할 수 없는 시퀸스 번호

Window

아직 ACK을 받지 않은 전송된 패킷들에 대해 허용된 시퀸스 번호 범위는 크기 N의 window라고 불린다. 위 문단의 표현법을 빌리면, [base, base+N-1]에 해당한다. 즉, window 내에 속하는 시퀸스 번호에 해당하는 패킷만 전송될 수 있으며, nextseqnum이 base+N에 도달하면, window가 가득찬 상태이며, 패킷을 더 이상 전송할 수 없다. 이때, 전송한 패킷의 ACK 신호를 수신함에 따라 이 window는 시퀸스 번호 공간 위를 앞으로 슬라이딩하며 움직인다. 이 때문에 N은 window 크기라고 불린다.

그렇다면 왜 window의 크기를 N으로 제한하는 건지에 대한 의문이 들 수 있다. 이에 대한 한 가지 이유는 flow control 때문이며, 또다른 이유는 TCP의 congestion control 때문이다.

Go-Back-N

Figure 4. Sender’s view of sequence numbers in Go-Back-N

Figure 5. GBN in action

Go-Back-N(GBN) 프로토콜에서 송신측은 pipeline 내에 최대 N개의 unack된(unacknowledged) 패킷을 보낸다. 또한 수신측으로부터 전송한 패킷에 대한 ACK을 수신하는데, 만약 패킷 번호가 n인 패킷에 대한 ACK은 cumulative ack으로 간주된다. 이는 n 이하의 모든 패킷들이 모두 올바르게 수신되었음을 의미한다. 또한 송신자는 가장 오래된, unack된 패킷에 대해 하나의 타이머를 가지고 time-out을 측정한다. 이때 n에 대한 time-out이 발생하면 송신자는 패킷 번호가 n 이상인 모든 패킷들을 다시 수신측에 보낸다. 만약, 패킷이 수신측에 전송되는 도중 손상되었다면, 해당 패킷은 수신측에서 폐기되고 ACK(base)를 다시 전송한다. 이후로도 손상된 패킷 이후의 ACK이 계속 base로 유지되기 때문에 타이머가 만료되고 base부터 시작해서 그 이후 모든 패킷을 다시 전송한다.

수신측의 동작은 더욱 간단하다. 만약 패킷 번호 n의 패킷이 정상적으로 수신되고 순서대로 도착했다면 ACK(n)을 전송하고, 해당 패킷의 데이터를 상위 계층에 전달한다. 그 외의 모든 경우에는 패킷을 폐기하고 ACK(base)를 재전송한다. 이때 상위 layer에는 패킷이 하나씩 순차적으로 전달되기 때문에, 만약 패킷 n이 전달되었다면, n보다 작은 모든 패킷들도 이미 전달된 것이 보장된다. 즉, 순서가 어긋난 패킷은 폐기되어 수신측의 상위 layer에는 패킷이 순서대로 도착한다. 이때, 수신측의 구현은 간단한데, 오직 다음에 도착할 것이 예상되는 패킷 번호, 즉 base+1만 저장하면 된다.

하지만 GBN은 문제를 가지고 있다. 만약 window의 크기와 대역폭-지연곱(Bandwidth-Delay Product)이 모두 큰 경우, 많은 패킷들이 파이프라인 안에 존재한다. 이때 만약 단 하나의 패킷 오류만 존재하더라도, GBN은 많은 수의 패킷들을 재전송할 수 있다. 또한 패킷이 손실되거나 손상될 확률이 커질수록 이러한 비효율성은 급속도로 커진다.

Selective repeat

Figure 6. Selective repeat: sender, receiver windows

Figure 7. Selective repeat in action

Selective repeat 프로토콜은 송신자가 수신측에서 손실되거나 손상된 패킷만 재전송하도록 하여 GBN에서 볼 수 있었던 불필요한 재전송을 피한다. 이러한 개별적이고 필요에 따른 재전송을 위해서는, 수신자가 각 패킷마다 별도로 ACK을 보내야 한다.

SR에서 송신측은 GBN과 마찬가지로 최대 N개의 unack된(unacknowledged) 패킷을 보낸다. 또한 수신측으로부터 전송한 패킷에 대한 ACK을 수신하며, 이는 cumulative ack로 간수되지 않는다. ACK(n)이 수신되었다면, 패킷 번호 n이 window 안에 존재할 경우에만 해당 패킷을 수신 완료한 것으로 표시한다. 만약 ACK(send_base)가 수신되었다면, send_base를 다음으로 unack된 패킷의 번호로 갱신하며 window를 슬라이딩한다. 또한 window의 사이즈가 N이면, 타이머의 개수도 N개 필요하다. N개의 타이머는 각각의 패킷에 대한 time-out을 측정하여 time-out이 발생한 패킷을 다시 수신측에 보낸다. SR에서 수신측은 패킷이 순서대로 도착했는지는 상관없이, 정상적으로 수신된 패킷 이라면 ACK(n)를 전송한다. 순서가 어긋난 패킷들은 버퍼에 저장해두었다가, 순서에서 빠진 패킷들이 도착하면 상위 layer에 일괄적으로 순서대로 전달된다. 이때, 수신측은 현재의 rcv_base보다 작은 패킷 번호를 가진 패킷에 대해서도 무시하지 않고 ACK(n)를 보낸다. 이는 다음과 같은 문제 상황을 막기 위해서이다.
만약 송신측이 패킷 0, 1, 2를 보내고, 수신자이 이를 정상적으로 수신하고 ACK도 전송했지만, ACK(0)만 손실되고 ACK(1), ACK(2)만 송신측에 도착했다고 하자. 이때 송신측은 ACK(0)가 도착하지 않았으므로 send_base = 0인 상태를 유지하며, 패킷 0에 대한 ACK(0)를 받지 못했으므로 타이머 만료시 패킷 0를 재전송한다. 하지만 수신측은 모든 패킷을 정상적으로 수신하였으므로, rcv_base = 3인 상태이다. 이 경우 만약 재전송된 패킷 0를 수신측이 무시한다면, 송신자는 계속 패킷 0를 재전송하므로 송신측의 window는 절대 앞으로 슬라이딩할 수 없다. 이는 수신측과 송신측이 서로 비동기화된 window를 사용하고 있기 때문에 발생하는 문제이다. SR은 이를 해결하기 위해서, 수신측이 이미 수신한 패킷에 대해서도 ACK를 전송하도록 한다.

그 이외의 경우에는 패킷 수신을 무시한다.

Figure 8. Selective repeat: dilemma

송신자와 수신자의 window가 동기화되어있지 않다는 점은 특수한 경우 매우 치명적인 결과를 초래한다.

예를 들어 패킷번호가 0~3까지 4개만 존재한다고 하고, window의 크기는 3이라고 하자. 이때 다음과 같은 시나리오 두가지가 존재한다:
첫 번째 시나리오에서는 송신측이 패킷 0~2를 전송하고, 수신자가 이들을 정상적으로 수신하고 ACK가 모두 송신측에 잘 전달된다. 그리고 송신자는 윈도우를 앞으로 이동시키고, 패킷 3, 0, 1을 전송한다. 이때 패킷 3이 손실되고 나머지가 도착한다. 이 경우 나중에 도착한 패킷 0은 완전히 새로운 패킷이다.
두 번째 시나리오에서는 송신측이 패킷 0~2를 전송하고, 수신자가 이들을 정상적으로 수신하고 ACK도 보내지만 ACK가 모두 손실된다. 타이머가 만료되어 송신자는 0~2번 패킷을 재전송한다. 이 경우에는 수신측의 window는 첫번째 시나리오와 동일하고, 동일하게 패킷 0을 수신하지만, 이는 단지 첫번째 전송분의 복사본일 뿐이다.
수신자 입장에서는 두 상황이 구분되지 않는다. 즉 이 경우에 수신자는 패킷 0이 이미 수신한 옛날 패킷의 복사본인지, 아니면 새로운 윈도우에서 새로 전송된 패킷인지 구분이 안 되는 상황에 빠진다. 이러한 상황을 막기 위해서는 SR 프로토콜에서 window의 크기를 패킷 번호 공간 크기의 절반 이하로 설정하여야 한다.