Principles of reliable data transfer

상위 문서: Transport Layer

개요

Reliable data transfer

신뢰성있는 데이터 전송(Reliable data transfer)을 구현하는 문제는 네트워크 학문에서 굉장히 중요한 문제이다. 신뢰성있는 데이터 전송의 개념적인 틀은 오른쪽 이미지가 잘 보여주고 있다.
상위 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가 손상된 것을 확인하더라도, 송신자는 수신자가 마지막 패킷을 제대로 받았는지 알 수 없다는 것이다. 이 경우 송신측이 수신측에게 동일한 데이터를 보낸다면 수신자는 동일한 데이터를 두 번 받을 수 있고, 어떤 것이 새로운 데이터인지 구분할 수 없어 데이터 오류가 발생할 수도 있다.

이를 해결하기 위한 간단한 방법은 데이터 패킷에 새로운 필드를 추가하여 해당 필드에 패킷 번호를 부여하는 것이다. 이때 수신자가 패킷 번호만 확인하면, 수신된 패킷이 재전송된 것인지 아닌지를 판별할 수 있다. 즉, 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

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 프로토콜이기 때문에, 송신측과 수신측의 링크 사이에 단 하나의 패킷만 존재할 수 있기 때문이다.