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

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

신뢰적인 데이터 전송 프로토콜을 구축하기 위해서 가장 간단한 상황부터 시작해서 조금씩 더 복잡해지는 상황으로 이어지는 다음의 4가지 경우에 대해 알아봅시다.

• 완벽하게 신뢰적인 채널 상에서의 신뢰적인 데이터 전송 : rdt1.0
• 비트 오류가 있는 채널 상에서의 신뢰적인 데이터 전송 : rdt2.0
• rdt2.0의 수정된 버전 : rdt2.1, rdt2.2
• 비트 오류와 손실 있는 채널 상에서의 신뢰적인 데이터 전송 : rdt3.0

시작에 앞서 몇 가지 가정해야 할 사항들이 있는데,

일단 송신자로부터 수신자로의 데이터 전송은 단방향의 경우만 고려합니다. 그리고 송신자와 수신자를 정의하기 위해 유한 상태 머신 FSM(Finite State Machine)을 사용합니다.

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

먼저, 하위 채널이 완전히 신뢰적인 가장 간단한 경우를 고려해 봅시다. 이 경우 패킷의 비트오류와 패킷손실은 없습니다. 이 프로토콜은 단순하며 rdt1.0이라 부르겠습니다. 다음의 FSM을 봅시다.

송신 측

• rdt_send(data) 이벤트에 의해 상위 계층으로부터 데이터를 받습니다.

• paket=make_pkt(data) 이벤트에 의해 데이터를 포함하는 패킷을 생성합니다.

• udt_send(packet) 이벤트에 의해 패킷을 채널로 내려보내며 송신합니다.

수신 측

• rdt_rcv(packet) 이벤트에 의해 하위 채널로부터 패킷을 수신합니다.

• extract(packet,data) 이벤트에 의해 패킷으로부터 데이터를 추출합니다.

• deliver_data(data) 이벤트에 의해 데이터를 상위 계층으로 전달합니다.

rdt1.0의 경우에는 하위 채널이 완전히 신뢰할 수 있는 경우이므로 중간에 데이터 변형이 없고(비트에러가 없음), 패킷의 손실도 없습니다. 이렇게 오류가 생길 수 없으므로 수신 측이 송신 측에게 어떠한 피드백도 제공할 필요가 없습니다.

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

두번째로, 패킷 안의 비트들이 하위 채널에서 손상되는 모델을 고려봅시다. rdt1.0보다 조금 복잡한 rdt2.0이라고 부르며, 모든 패킷들이 순서대로 수신되고 패킷손실은 없다고 가정합니다.

여러분은 전화통화를 할 때, 상대방의 말이 잘 들리면 계속 대화를 이어가지만 상대방의 말이 잘 안들리거나 하면 "뭐라고? 잘 안들려"라고 상대방에게 피드백을 줄 것입니다. 통신에서도 마찬가지입니다. 상대방의 말이 잘 들리면(데이터가 잘 도착하면) ACKs(acknowledgements)라는 긍정확인응답을 보내고, 상대방의 말이 잘 안들리면(데이터가 잘 도착하지 못하면) NAKs(negative acknowledgements)라는 부정 확인응답을 보내서 재전송을 요청합니다. 이렇게 재전송을 기반으로 하는 신뢰적인 프로토콜을 자동재전송요구 프로토콜인 ARQ(Automatic Repeat reQuest) 프로토콜이라고 합니다.

ARQ의 기능은 크게 3가지 입니다.

1. 오류검출 : 체크섬 필드를 사용하여 비트오류 발생 시 수신자가 검출할 수 있게 합니다.
2. 수신자 피드백 : 패킷이 정확하게 수신되었는지 아닌지를 수신자가 송신자에게 ACK 또는 NAK로 피드백 합니다.
3. 재전송 : NAK의 피드백일 경우 송신자는 재전송합니다.

이러한 ARQ의 기능들이 rdt2.0에 포함되었는데, 이는 rdt1.0과의 구별되는 점입니다. 다음의 FSM을 봅시다.

송신 측(2가지의 상태를 가집니다)

• 송신 측은 상위 계층으로부터 데이터가 전달되기를 기다립니다.

• rdt_send(data) 이벤트에 의해 상위 계층으로부터 데이터를 받으면, sndpkt=make_pkt(data,checksum) 이벤트에 의해 데이터와 체크섬을 포함하는 패킷을 생성하고, udt_send(sandpit) 이벤트에 의해 패킷을 채널로 내려보내며 송신합니다.

• 송신 후에는 오른쪽 상태로 넘어와 ACK 또는 NAK로 피드백 받기를 기다립니다.

• 만약, 수신 측이 잘 받고(receive) ACK의 피드백이 돌아온다면 왼쪽의 상태로 넘어가 상위계층으로부터 데이터가 전달되기를 기다리며 위의 과정을 반복합니다.

• 그러나, 수신 측이 잘 받았지만 NAK의 피드백이 돌아온다면 ACK의 피드백이 돌아올 때까지 udt_send(sandpit)의 과정을 반복합니다.

이 때 송신 측이 ACK 또는 NAK를 기다리는 오른쪽 상태에 있는 중에는 상위 계층으로부터 더 이상의 데이터를 전달받을 수 없습니다. rdt2.0은 전송-후-대기(Stop-and-Wait) 프로토콜이라고도 합니다.

수신 측

• rdt_rcv(rcvpkt) 이벤트에 의해 하위 채널로부터 패킷을 수신합니다.
• corrupt(rcvpkt) 이벤트에 의해 수신한 패킷에 오류가 있는 경우 udt_send(NAK)로 NAK 피드백을 합니다.
• 수신한 패킷에 오류가 없는 경우 extract(rcvpkt, data) 이벤트에 의해 패킷으로부터 데이터를 추출합니다.
• deliver_data(data) 이벤트에 의해 데이터를 상위 계층으로 전달합니다.
• udt_send(ACK) 이벤트에 의해 ACK 피드백을 합니다.

rdt2.0은 위와 같이 잘 동작되는 것처럼 보이지만 실제로는 치명적인 결합이 있는데 바로 ACK/NAK 패킷의 손상 가능성을 무시했다는 것입니다.

송신 측으로부터 수신 측으로 data가 잘 왔고, ACK 피드백을 보냈는데 중간에 ACK 패킷이 손상되어서 송신 측이 ACK를 못 알아듣는다면 어떻게 해야할까요? 가장 간단하면서 단순한 방법으로 송신 측은 그저 data를 수신 측으로 다시 한 번 보냅니다. 그러면 ACK/NAK가 다시 올테니깐요. 

그런데 수신 측은 혼란스러울 겁니다. 자신은 아까 받은 data에 대해 ACK를 보내주었는데, 동일한 data가 한 번 더 왔으니... 이게 다음 data인지 똑같은 data를 두번 중복(duplicate)으로 보낸건지.... 헷갈립니다.

이러한 중복 패킷에 대한 문제에 대한 간단한 해결책은 패킷에 순서번호(sequence number)를 붙이는 것입니다. 그래서 수신 측은 수신된 패킷이 재전송으로 인한 중복패킷인지 새로운 패킷인지를 결정할 때 sequence number만 확인하면 됩니다. 동일한 sequence number의 패킷이 수신된다면 이는 중복패킷으로 인식하는 것입니다.

rdt2.0의 수정된 버전 : rdt2.1, rdt2.2

세번째로, 바로 위에서 언급한 sequence number를 추가한 모델이 rdt2.1입니다. 송신 측은 0과 1을 sequence number로 사용합니다. 그리고 수신측은 0과 1로 중복패킷인지 여부를 결정합니다. 아래의 FSM을 봅시다

• 왼쪽 송신 측이 sequence number 0의 패킷을 보내면 0번에 대한 ACK/NAK를 기다립니다.
• 오른쪽 수신 측은 문제없이 잘 수신한 경우 ACK를 보내며 sequence number 1의 패킷이 수신되기를 기다립니다.
• 왼쪽 송신 측은 ACK를 받으면 sequence number 1의 패킷을 보내고, NAK를 받거나 피드백 패킷에 오류가 있을 경우에 sequence number 0의 패킷을 재전송합니다.
• 오른쪽 수신 측은 sequence number 1의 패킷을 기다리고 있는데, sequence number 1의 패킷이 수신되면 순조롭게 ACK를 보내면 되고, sequence number 0의 패킷이 도착한다면 sequence number 0의 패킷이 중복도착했으므로 무언가 중간에 문제가 생겼음을 알고 sequence number 0에 대한 ACK를 보냅니다.

기능은 rdt2.1과 동일하지만 NAK를 사용하지 않고(NAK-free) ACK만 사용하는 모델이 rdt2.2입니다.

NAK를 보내는 대신에, 가장 최근에 잘 받은 패킷에 대한 ACK를 보냄으로써 NAK를 보내는 것과 동일한 효과를 얻을 수 있습니다. 다음 그림을 보면 쉽게 이해할 수 있습니다.

송신 측이 pkt1을 보냈지만 수신측이 ACK1이 아닌 ACK0만 계속 보낸다면 송신 측은 pkt1의 전송에 문제가 생겼음을 인식하고 재전송할 수 있다라는 의미입니다.

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

마지막으로, 비트 손상과 함께 패킷을 손실하는 모델을 고려봅시다. 이를 rdt3.0이라고 부르며, 어떻게 패킷 손실을 검출하며 패킷손실이 발생했을 때 어떤 행동을 해야하는지가 중요한 사항이 됩니다. 다행히 패킷손실이 발생했을 경우 rdt2.2까지 설명하면서 사용되어 왔던 체크섬,sequence number, ACK, 재전송 등은 패킷손실이 발생했을 때 해야하는 행동에 대한 답이 될 수 있습니다. 패킷 손실의 검출은 바로 Timer로 할 수 있습니다.

타이머는 패킷 손실이 일어났다는 100% 보장은 아니지만, 손실이 일어났을 만한 그런시간을 현명하게 선택하는 방식입니다. 만일 ACK가 이 시간안에 수신되지 않는다면 패킷은 재전송될 것(그림 b,c)입니다. 심지어 패킷이 유별나게 큰 delay를 가져서 타이머 시간보다 늦게 도착하는 경우 비록 ACK가 손실되지 않았다 하더라도 패킷은 재전송할 수 있습니다. 이는 중복 데이터 패킷(duplicate data packet)의 가능성을 포함한다는 이야기입니다.(그림d) 다행히 rdt2.2는 이미 패킷이 중복되었을 경우를 처리하기 위한 sequence number의 기능을 가지고 있습니다.

재밌는 점은 프로토콜 rdt3.0은 기능적으로 매우 정확한 프로토콜임에도 불구하고 오늘날의 고속 네트워크에서 만족스러운 성능을 보여주지 못한다는 점입니다. 이유는 '전송-후-대기(Stop-and-Wait)'방식이기 때문입니다.

예를 들어 봅시다. 미국 서부에서 동부로 통신하는 경우를 고려합시다. 

• 두 종단 사이의 RTT =  30msec
• 1Gbps(초당 10의 9승 bit) 전송률(R)을 가진 채널에 의해서 연결
• 헤더와 데이터를 포함하여 패킷당 1000byte(8000bit)의 패킷크기(L)의 패킷을 전송

RTT : Round Trip Time; 패킷이 송신측에서 수신측으로 전송되고,ACK가 수신측에서 송신측으로 돌아오는데 걸리는 시간

위와 같은 가정된 상황에서 8000비트를 실제로 보내는데 필요한 시간은 다음과 같습니다.

즉, 8usec동안 송신측은 8000비트의 첫 비트부터 마지막 비트까지 수신측으로 보냈습니다. 보낸 패킷들은 15msec동안 서부에서 동부로 이동하며 수신측에게 도착할 것이며, 수신 측이 ACK를 바로 보낸다는 가정하에 또 다른 15msec후에 ACK가 송신측으로 도착할 것입니다.  결국 송신 측은 30.008msec 후에 ACK를 받았습니다. 

그러므로 30.008msec 동안 송신 측은 단지 0.008msec동안만 데이터를 전송한 셈입니다. 이용률로 따져보자면 다음과 같이 아주 형편없음을 알 수 있습니다.

즉, 송신자는 전체 시간의 0.00027만큼만 바빴던 것입니다. 어이가 없죠. 이것이 바로 stop-and-wait 프로토콜의 문제점이라는 것입니다. 그런데 아주 간단한 해결책이 있습니다. ACK를 기다리지 말고, 여러 패킷을 전송하도록 허용하는 것입니다.

패킷을 파이프라인에 채워넣음으로써 이용률은 3배가 될 수 있습니다. 이 기술을 파이프라이닝(pipelining)이라고 하며, 다음과 같은 사항들을 고려해야 합니다.

• sequence number 범위의 증가 : 여러 패킷을 보낼 수 있게 됨으로써 0과 1로만은 부족해집니다.
• 버퍼의 필요 : 송신 측과 수신 측은 여러 패킷 이상을 담을 수 있는 버퍼가 필요해졌습니다.
• 파이프라인 오류 회복 방법 : 파이프라인에서 패킷 손실과 지연 패킷에 대한 처리방식이 필요해졌습니다.

이렇게 최종적으로 파이프라이닝 기술까지 오면서 위의 3가지 고려사항이 중요해졌습니다. 그래서 2가지 기본적인 접근방법인 GBN(Go-Back-N, N부터 반복)과 SR(Selective Repeat,선택적 반복) 프로토콜이 나타나게 되었습니다.