[Network] 3-4. Principles of Reliable Data Transfer (1)

Park Yeongseo·2024년 12월 2일

Network

목록 보기

17/17

Computer Networking: A Top-Down Approach, 7th Edition의 번역 및 정리입니다.

여기서는 보다 일반적인 맥락에서 신뢰성 있는 데이터 전송 문제에 대해 알아본다. 신뢰성 있는 데이터 전송의 구현은 전송 계층 뿐만 아니라, 링크 계층과 애플리케이션 계층에서도 일어난다.

위는 신뢰성 있는 데이터 전송의 프레임워크다. 상위 계층 엔티티에게 서비스는 데이터가 전송될 수 있는, 신뢰할 수 있는 채널 같이 보인다(a). 신뢰할 수 있는 채널을 이용하면, 전송되는 데이터 비트들은 손상되거나 손실되지 않으며, 전송한 모든 것은 보내진 순서대로 전달된다.

신뢰할 수 있는 데이터 전송은 이러한 서비스 추상화를 제공할 수 있어야 한다(b). 이 작업은, 신뢰성 있는 데이터 전송 프로토콜의 하위 계층들을 신뢰할 수 없기에 어려운 일이다. 예를 들어 TCP는 신뢰성 있는 데이터 전송 프로토콜로, 신뢰할 수 없는 IP 네트워크 계층 위에 있다.

이 섹션에서는 기저 채널이 비트를 손상/손실시킬 수 있을 때 어떻게 신뢰할 수 있는 데이터 전송을 구현할 수 있는지에 대해 알아본다. 단 여기서는 패킷이 보내진 순서대로 도착한다고(손실 및 손상은 일어날 수 있음), 즉 기저의 채널이 패킷의 순서를 바꾸는 경우는 없다고 가정한다.

(b)에서는 데이터 전송 프로토콜의 인터페이스를 볼 수 있다. 데이터 전송 프로토콜의 송신측은 rdt_send()를 통해 호출된다. 이는 수신 측의 상위 계층으로 전달할 데이터를 전달한다. 패킷이 채널의 수신측에 도착했을 때, 수신측은 rdt_rcv()를 호출한다. rdt 프로토콜이 데이터를 상위 계층으로 전달하고 싶을 때에는 deliver_data()를 이용한다. 이후 논의에서는 전송 계층 "세그먼트"라는 용어 대신 "패킷"이라는 용어를 쓰도록 한다. 이 섹션에서 논의할 이론은 인터넷 전송 계층에만 적용되는 게 아니라, 일반 컴퓨터 네트워크에도 적용될 수 있기 때문에 보다 일반적인 용어를 사용한다.

이 섹션에서는 오직 단방향(unidirectional) 데이터 전송만을 고려한다. 양방향(bidirectional. 즉 전이중, full-duplex) 데이터 전송도 단방향 데이터 전송과는 크게 다를 것이 없다. 다만 그렇다 하더라도, 실제 네트워크에서는 송수신 측이 양방향으로 패킷을 전송한다는 것을 염두에 두자.

1. Building a Reliable Data Transfer Protocol

Reliable Data Transfer over a Perfectly Reliable Channel: rdt1.0

우선은 기저 채널을 완전히 신뢰할 수 있는 경우를 고려해보자(rdt1.0이라 부르도록 한다).

위 그림은 rdt1.0 송수신측의 FSM으로, (a)는 송신측, (b)는 수신측의 FSM이다. 각 FSM은 단 하나의 상태만을 가지고 있다. 상태 전이를 일으키는 이벤트는 수평선의 위, 그리고 해당 이벤트가 일어났을 때 취할 액션들은 수평선의 아래에 적혀있다.

rdt 송신측은 rdt_send(data) 이벤트를 통해 상위 계층으로부터 데이터를 받아, make_pkt(data) 액션을 통해 해당 데이터를 포함하는 패킷을 만들어 채널로 내보낸다. 실제로 rdt_send(data) 이벤트는 상위 계층 애플리케이션에서 호출하는 프로시저 콜을 통해 일어난다.

rdt 수신측에서, rdt는 기저 채널로부터 rdt_rcv(packet)을 통해 패킷을 받아, extract(packet, data)를 통해 패킷으로부터 데이터를 제거한 후, 데이터를 deliver_data(data)를 통해 상위 계층으로 올려보낸다. 실제로 rdt_rcv(packet) 이벤트는 하위 계층 프로토콜의 프로시저 콜 호출을 통해 이루어진다.

이 간단한 프로토콜에서 완전히 신뢰할 수 있는 채널을 사용하기 때문에, 수신측은 송신측에 데이터 전송에 대한 어떠한 피드백을 제공할 필요가 없다(송신측에서 보내는 모든 데이터가 정확히 수신측에 도착할 것이기 때문에).

Reliable Data Transfer over a Channel with Bit Errors: `rdt2.0`

이번에는 패킷에 비트 손상이 일어날 수 있는 채널을 사용한다고 하자. 이러한 비트 오류는 보통 패킷이 전송, 전파, 버퍼링될 때 쓰이는 네트워크의 물리적 구성 요소에서 일어나곤 한다. 단 여기서도 패킷은 (손상은 일어날 수 있지만) 보내진 순서대로 받아진다고 가정한다.

여기서 잠깐 예시를 들어보자. 전화를 통해 긴 문장을 듣고 받아 쓰려한다고 해보자. 듣는 이는 자신이 들은 문장이 제대로 된 것이라면 제대로 들었다고 말하고(긍정 응답, positive acknowledgment), 제대로 듣지 못했다면 다시 한 번 말해달라고 말할 수 있다(부정 응답, negative acknowledgment). 말하는 이는 듣는 이의 피드백을 듣고, 자신이 말한 메시지가 제대로 전달됐는지의 여부를 알 수 있고, 이를 통해 다음 자신이 취할 행동을 선택한다. 컴퓨터 네트워크의 신뢰성 있는 데이터 전송 프로토콜도 이러한 재전송 방식에 기반해 있으며, 이를 ARQ(Automatic Repeat reQuest) 프로토콜이라 부른다

ARQ 프로토콜에서는 비트 오류를 처리하기 위해 추가로 다음의 세 프로토콜 기능들이 필요하다.

에러 검출: 수신자는 비트 에러의 발생 여부를 확인할 수 있어야 한다. 이전 섹션의 UDP가 체크섬 필드를 사용했던 것이 이러한 목적에서다. 에러 검출/수정 테크닉에 대해서는 이후 챕터에서 더 자세히 보게 될 것이고, 여기서는 송신측에서 이러한 기능을 제공하기 위한 추가적인 비트들을 더해 수신측으로 보낸다는 것 정도만 알아두도록 하자.
수신자 피드백: 송신자와 수신자는 보통 서로 다른 종단 시스템에서 실행되고 있다.
재전송: 송신자는 수신자가 에러 패킷을 받았을 때 데이터를 재전송할 수 있어야 한다.

위는 에러 검출, 긍정 응답(ACK), 부정 응답(NAK)을 사용하는 rdt2.0의 FSM이다.

rdt2.0의 송신측에는 두 상태가 있다. 왼쪽 상태에서 송신측 프로토콜은 상위 계층으로부터 자신에게 데이터가 전달되기를 기다린다. rdt_send(data) 이벤트가 발생할 때, 송신자는 데이터를 포함하는 sndpkt 패킷을 만드는데, 이 패킷에는 패킷 체크섬도 포함되어 있다. 이 패킷은 udt_send(sndpkt)을 통해 채널로 보내진다. 오른쪽 상태에서 송신 프로토콜은 수신측으로부터 ACK 또는 NAK 패킷이 보내지기를 기다린다.

만약 ACK 패킷을 받았다면(rdt_rcv(rcvpkt) && isACK(rcvpkt)) 송신측은 자신이 최근에 전송한 패킷을 수신측이 제대로 받았음을 알게 되고, 왼쪽 상태로 전이된다.

NAK를 받은 경우, 프로토콜은 최근 보낸 패킷을 재전송하고 상태를 유지한다. 여기서 중요한 점으로, 송신측은 ACK나 NAK를 기다리고 있는 동안 상위 계층으로부터 데이터를 받을 수 없다. 이 작업은 왼쪽 상태에서만 가능하며, 따라서 송신측은 최근에 보낸 패킷에 대한 ACK이 오기 전까지는 새로운 데이터를 보낼 수 없게 된다. 때문에 rdt2.0은 stop-and-wait 프로토콜이라 부른다.

수신측 FSM에는 여전히 하나의 상태 밖에 없다. 패킷이 도달했을 때 수신자는 자신이 받은 패킷에 손상이 있는지 여부에 따라 ACK, 또는 NAK로 응답을 한다.

rdt2.0 프로토콜은 잘 작동할 것 같아 보이지만 한 가지 큰 결함이 있는데, 바로 ACK, NAK 패킷에도 손상이 일어날 수 있다는 점이다. ACK/NAK 패킷에도 에러 검출을 위한 체크섬 비트를 추가하면 모든 문제가 해결될 것 같지만, 더 어려운 문제는 ACK/NAK 패킷 에러를 복구하는 일이다.

ACK/NAK 손상을 처리하는 세 경우를 생각해보자.

송신자는 수신자로부터 받은 응답 메시지에 에러가 있을 경우, 수신자에게 응답을 다시 보내달라는 메시지를 보낼 수 있다. 이 경우 해당 메시지를 받은 수신자는 다시 응답 메시지를 보내면 된다. 문제는 송신자가 보낸 메시지에도 에러가 발생하는 경우다. 수신자는 해당 메시지가 자신이 원래 받아야 할 메시지인지, 혹은 응답을 다시 보내달라는 메시지인지를 판단할 수 없다.
수신자는 응답 메시지에 에러 검출 뿐만 아니라 에러 복구까지도 할 수 있을 만큼의 충분한 체크섬 비트를 추가할 수도 있다. 이 경우 패킷 손상(손실이 아니라) 문제는 해결된다.
송신자는 수신자로부터 받은 응답 메시지에 에러가 있는 경우, 그냥 현재 데이터 패킷을 재전송할 수도 있다. 하지만 이 방식에는 중복 패킷(duplicate packet) 문제가 발생할 수 있다. 수신자는 자신이 보낸 응답을 송신자가 제대로 받았는지 확인할 수 없고, 송신자가 보낸 패킷이 새로운 데이터인지, 재전송된 것인지를 알 수도 없다.

이 문제를 해결하기 위해서는 데이터 패킷에 새로운 필드(시퀀스 번호, sequence number)를 추가하고, 이를 통해 송신자가 데이터 패킷에 번호를 매기게 하면 된다. 수신자는 시퀀스 번호 필드를 가지고 데이터가 재전송된 것인지, 혹은 그냥 새로 보내진 것인지를 확인할 수 있을 것이다.

우리가 사용하고 있는 간단한 stop-and-wait 프로토콜에서는 1비트 시퀀스 번호 필드를 추가해, 해당 패킷이 재전송된 것인지 혹은 새로운 패킷인지를 나타내는 것으로 충분하다. 현재 우리 채널에서 패킷 손실은 일어나지 않는 것으로 가정하기에, ACK/NAK 패킷에 해당 패킷이 어떤 데이터 패킷에 대한 응답인지를 표시할 필요도 없다. 송신자는 ACK/NAK 패킷을 받으면, 해당 패킷이 자신이 가장 최근에 보낸 데이터 패킷에 대한 응답임을 알 수 있기 때문이다.

아래의 두 다이어그램은 rdt2.0의 수정 버전인 rdt2.1의 FSM이다. 여기서 송신자와 수신자는 모두 이전의 두 배가 되는 상태를 가진다. 1비트 시퀀스 패킷을 추가했기 때문에 각 비트에 해당하는 상태들로 분화됐기 때문이다.

rdt2.1 프로토콜에서는 긍정 및 부정 응답을 모두 사용하며, 수신자는 순서가 잘못된 패킷을 받았을 때에는 긍정 응답을, 손상된 패킷을 받았을 때에는 부정 응답을 보낸다.

가장 최근에 제대로 받은 패킷에 ACK를 보내는 방법을 사용하면, 꼭 NAK를 보내지 않고서도 같은 효과를 낼 수도 있다. 송신자는 동일한 패킷에 두 개의 ACK를 받는 경우, 수신자가 제대로 패킷을 받지 못했음을 알 수 있게 된다.

아래의 두 다이어그램은 NAK을 사용하지 않는 프로토콜 rdt2.2의 FSM이다. rdt2.1과 차이가 있다면, 수신자는 ACK 메시지를 보낼 때 패킷의 시퀀스 번호도 함께 보내줘야 한다는 것, 그리고 송신자는 ACK 메시지를 받을 때 해당 메시지의 패킷 시퀀스 번호를 확인해야 한다는 것 밖에 없다.

Reliable Data Transfer over a Lossy Channel with Bit Errors: `rdt3.0`

이제는 패킷 손상 뿐만 아니라, 패킷 손실도 일어날 수 있다고 해보자. 이제 프로토콜은 패킷 손실이 일어났는지를 감지할 수도 있어야 하고, 그에 대한 대응도 할 수 있어야 한다.

패킷 손실이 일어났을 때의 대응은 rdt2에서 사용했던 것과 같은 방법으로 처리할 수 있다. 그렇다면 패킷 손실은 어떻게 감지할 수 있을까?

송신자가 데이터 패킷을 전송했을 때, 해당 데이터 패킷, 혹은 해당 패킷에 대한 수신자의 ACK 메시지가 손실되었다고 해보자. 만약 송신자가 패킷을 보낸 후 어느 정도의 시간이 지날 때까지 해당 패킷에 대한 ACK 메시지를 받지 못했다면, 송신자는 자신이 보낸 패킷이 손실되었음을 확신할 수 있다.

그런데 도대체 얼마나 오래 기다려야 할까? 수신자는 적어도 1 RTT + 수신자가 해당 패킷을 처리하는 데에 걸리는 시간만큼은 기다려야 한다. 하지만 그 시간을 정확히 측정하기는 어렵다.

그 시간을 제대로 알 수 있다고 하더라도 문제가 생길 수 있다. 어떤 지연으로 인해 시간이 너무 오래 걸릴 수도 있기 때문이다. 프로토콜에서 패킷 손실에 대한 복구는 최대한 신속하게 일어나야 하는데, 대기 시간이 너무 길어지면 에러 복구가 시작되는 데까지 걸리는 시간도 지체되는 결과로 이어진다.

때문에 송신자는 패킷 손실이 일어날 수도 있을 만한, 어느 정도의 시간을 정해두고, 해당 시간 동안 ACK을 받지 못하면 패킷을 재전송하는 방법을 사용한다. 단 이 경우, 실제로는 패킷 손실이 일어나지 않고 전송 지연만 일어나더라도 패킷을 재전송하게 될 수도 있다. 다행히 rdt2.2 프로토콜을 이용하면 이러한 중복 패킷 문제를 해결할 수 있다.