컴퓨터네트워크[12]: Principles of reliable data transfer

Principles of reliable data transfer (신뢰성 있는 데이터 전송의 원칙)

신뢰성 있는 데이터 전송 = reliable data transfer = rdt

신뢰성 없는 채널의 특성(손실, 오염, 재정렬 등)에 따라 신뢰성 있는 transfer protocol의 복잡도가 영향을 받는다.

송신자와 수신자는 서로의 상태를 모르기에 메시지가 수신됐는지 알 수 없다.

 

rdt_send() : 애플리케이션 계층 등 상위 레이어에서 호출됨. 전송할 데이터를 수신 측 상위 레이어에 전달

udt_send() : rdt에서 호출되어 불안정한 채널을 통해 패킷을 수신측에 전송

rdt_rcv() : 수신측 채널에서 패킷이 도착했을 때 호출됨

deliver_data() : rdt에서 호출되어 상위 레이어에 데이터를 전달함

 

 

rdt1.0 - 신뢰성 있는 채널에서 신뢰성 있는 전송

기반이 되는 채널이 perfectly reliable

- 비트 에러 없음

- 패킷 손실 없음

 

송신자와 수신자 각각 별도의 FSMs가 있음.

FSMs: Finite State Machines : 입력을 받아서 다음 상태로 전이, 전이 과정에서 출력. 송신자와 수신자를 명시함

- 송신자는 데이터를 기반 채널(underlying channel)로 보냄

- 수신자는 기반 채널(underlying channel)에서 데이터를 읽음

 

 

rdt2.0 - 채널에 비트에러가 있을 수 있음

기반이 되는 채널이 패킷 내의 비트를 뒤집을 수 있음(flip bits in packet)

- checksum이 비트에러를 감지함.

 

확인응답(ACKs) : 수신자가 패킷을 올바르게 수신했다는 것을 명시적으로 송신자에게 알림

부정적인 확인 응답(NAKs) : 수신자가 패킷에 오류가 있음을 명시적으로 송신자에게 알림

송신자는 NAKs를 수신하면 패킷을 재전송

 

ACK/NAK가 손상됐을 수도 있다.

- 송신자는 수신자에게 어떤 일이 일어났는지 알 수 없음

- 단순히 재전송하면 중복이 발생할 가능성 있음

 

handling duplicates:

- ACK/NAK가 손상되면 송신자는 현재 패킷을 다시 전송함

- 송신자는 각 패킷에 일련 번호(sequence number)를 추가함

- 수신자는 중복 패킷을 제거(상위 레이어로 전달하지 않음)한다.

 

 

rdt2.1: discussion

sender:

- 패킷에 일련번호 seq # 추가

- 0,1 두가지 seqence로 충분하다.

- 수신한 ACK/NAK가 손상되었는지 확인

- states가 2배로 증가 - 예상 패킷이 0 or 1의 sequence number를 가져야하는지 기억해야함.

 => 상태 전이에 필요한 상태의 수가 두 배가 됨

 

receiver:

- 중복 패킷이 수신됐는지 확인 : states는 0 또는 1의 seq number를 예상하는 패킷을 나타냄

- receiver는 마지막 ACK/NAK이 sender에서 올바르게 수신됐는지 알 수 없음

 

 

rdt2.2: a NAK-free protocol

- ACK만 사용해서 rdt2.1과 동일한 기능을 제공함.

- NAK 대신에 receiver는 마지막으로 올바르게 수신된 패킷에 대한 ACK를 보낸다.

- receiver는 명시적으로 ACK된 패킷의 seq number를 포함해야한다.

- sender에게 중복된 ACK가 발생하면 NAK와 동일한 작업을 수행한다 (현재 패킷 재전송)

- TCP는 이런 방식을 사용해서 NAK가 필요하지 않도록 구현된다.

 

 

rdt3.0: 채널에 비트에러와 손실 모두 있을 수 있음

기반이 되는 채널은 손실 패킷도 있을 수 있다.

 

sender는 ACK를 받을 합리적인(reasonable) 시간을 기다린다.

일정 시간 내에 ACK가 수신되지 않으면 재전송한다.

 

패킷(또는 ACK)가 지연될 경우:

- 재전송은 중복될 수 있지만 seq number가 이를 처리한다.

- receiver는 ACK된 패킷의 seq number를 명시해야한다.

 

카운트다운 타이머를 사용해서 합리적인 시간 후에 interrupt한다.

 

 

U(sender) : sender의 이용률, sender가 패킷을 보내는 데 사용하는 시간의 일부분

예시 : 1Gbps link = R, 15ms prop. delay(전파지연), 8000bit packet = L

 

패킷을 채널에 전송하는 데 걸리는 시간 D(trans)는,

D(trans) = L/R = 8000bits / 1Gbps = 8us (마이크로초)

 

U(sender)는 패킷을 채널에 전송하는 데 걸린 시간 D(trans)에 총 시간을 나눈 값이다.

RTT는 패킷을 보내고나서, ACK가 돌아올 때까지의 시간으로 전파지연 값의 2배이다. 따라서,

U(sender) = (D(trans)) / (RTT + D(trans)) = 0.008 / 30.008 = 0.00027

 

 

rdt 3.0 프로토콜의 성능은 좋지 않다.

프로토콜은 기반이 되는 인프라의 성능을 제한한다.

 

 

rdt3.0: pipelined protocols operation

pipelining: sender는 여러 개의 패킷을 "in-flight"상태로 유지하면서 아직 ACK를 받지 못한 패킷을 허용한다.

- seq number의 범위를 증가시켜야한다.

- sender, receiver에서 버퍼링이 필요하다. (둘 모두에게 필요할 수도 있고, 한쪽만 필요할 수도 있다)

 

pipelining을 통해, 여러 개의 패킷을 한번에 전송한다.

1Gbps link = R, 15ms prop. delay(전파지연), 8000bit packet = L 라고 할 때,

같은 패킷을 3개 보낸다고 하면 U(sender) = (3*L/R) / (RTT + L/R) 으로 0.00081이 된다.

 

 

Go-Back-N: sender

sender:  window란, 연속적으로 전송되지만 ACK를 받지 못한 최대 N개의 패킷

- 패킷 헤더에 k비트의 seq number 포함

cumulative(누적) ACK : ACK(n)은 n번 이하의 모든 패킷을 ACK한다.

- ACK(n)을 받으면 윈도우를 n+1에서 시작하는 위치로 이동한다.

 

타이머 : 가장 오래된 전송중인(in-flight) 패킷의 타이머

timeout(n): 패킷 n과 윈도우 내에서 높은 seq number의 모든 패킷을 재전송

 

 

Go-Back-N: receiver

ACK-only: 지금까지 올바르게 수신한 패킷에 대해 항상 ACK를 보냄, 가장 높은 순서의 seq number를 함께 보낸다.

- 중복 ACK를 생성할 수 있다.

- rcv_base만 기억하면 된다.

 

순서가 바뀐(receipt) 패킷을 받았을 때:

- 버퍼링하지 않고 취소할 수 있음 (버퍼링 여부는 구현 결정 사항)

- 가장 높은 순서의 시퀀스 번호로 패킷을 다시 ACK한다.

 

Go-Back-N의 예시이다.

N=4일 때, ACK(0,1,2,3)로써 패킷 0,1,2,3을 보낸다.

receiver 입장에서 0,1이 왔지만 그 다음으로 3이 왔다. 따라서 2번이 손실됐음을 파악했으므로 3번을 discard한다.

 

sender는 0,1번은 ACK가 왔기에 다음번으로 늘려서 4,5번 패킷을 보낸다. 2번 패킷에 대해 타임아웃이 되면, 다시 보낸다. 3,4,5번 패킷에 대해서도 타임아웃으로 인해 재전송한다.

 

 

 

 

Selective repeat

receiver는 올바르게 receive한 모든 패킷에 대해 개별적으로 확인 응답한다.

- 필요한 경우, 상위 레이어로 순서대로 전달하기 위해 패킷을 버퍼링한다.

 

sender는 ACK 받지 못한 패킷을 개별적으로 타임아웃 및 재전송한다.

sender는 각각의 ACK 받지 못한 패킷에 대해 타이머를 유지한다.

 

sender window

- N개의 연속적인 seq number

- 전송된, ACK받지못한(unACKed) 패킷의 seq number를 제한한다.

 

sender:

window 내에서, 다음 사용 가능한 seq number일 경우 패킷을 전송한다.

timeout(n) : 패킷 n을 다시 전송하고 타이머를 재시작한다.

 

ACK(n)이 [sendbase, sendbase+N]에 있는 경우,

- 패킷 n을 수신한 것으로 표시한다.

- n이 가장 작은 ACK 받지 못한 패킷일 경우 window base를 다음 ACK 받지 못한 seq number로 이동한다.

 

 

receiver:

패킷 n이 [rcvbase, rcvbase+N-1]에 있는 경우,

- 순서가 바뀐 경우, 버퍼링한다.

- 순서대로인 경우, ACK(n)을 전달하고 버퍼링된 순서대로인 패킷도 전달하고, window를 다음으로 받지 못한 패킷으로 이동한다.

 

패킷 n이 [rcvbase-N, rcvbase-1]에 있는 경우,

- ACK(n)을 전송한다.

 

그 외는 무시한다.

 

selective repeat의 예시이다.

패킷 0,1,2,3을 보내고, 0,1에 대한 ACK가 돌아와 패킷 4,5도 보낸 상태이다.

 

receiver는 패킷 2를 받지 못해 패킷 3,4,5를 버퍼에 저장해두고, 타임아웃으로 인해 sender에서 다시 패킷2를 보낸다.

패킷 2를 받은 receiver는 패킷 2,3,4,5에 대한 ACK를 보낸다.

 

 

 

 

 

다만, 윈도우의 크기가 너무 크거나 시퀀스 번호의 크기가 너무 작은 경우, ACK 패킷이 손실됐을 때 문제가 생길 수 있다.

 

ACK 패킷이 손실되어 패킷이 재전송 됐을 때 이를 무시해야하는데, seq number의 크기가 너무 작으면 문제가 발생할 수 있다.