comnet-07

Chapter 03. Transport layer(2)

 

Principles of reliable data transfer

reliable channel이 있다고 가정해 보자

reliable service abstraction

신뢰가능한 서비스란? 손실, 오류, 중복, 순서 뒤바뀜이 전혀 없는 채널이다. 

reliable channel을 통해 손실 없이 전송한다. 

 

(application layer는 오직 어떤 데이터를 주고받을지만 처리하기 때문에 데이터 전송의 신뢰성을 신경 쓸 필요가 없다. 신뢰성 있는 전송은 transport layer가 고려한다.)

 

하지만 현실의 transport/network layer는 loss, bit-error, 중복, out-of-order 등의 특성을 가지므로 신뢰성이 없다. 

reliable service implementation

unreliable channel 위에 reliable data transfer protocol을 이용해 신뢰성을 구현해야 한다. 

어떤 unreliable channel 위에서 신뢰 전송 서비스를 구현하냐에 따라 그 protocol의 복잡도가 크게 달라진다. 

 

reliable data transfer protocol(신뢰 전송 프로토콜)의 핵심

sender와 receiver는 서로의 상태를 알 수 없다.(네트워크의 비동기성) 오직 메시지(ACK/NAK 등) 교환을 통해서만 상태가 동기화된다. 

 

 

 

애플리케이션이 보낼 메시지를 준비한다. rdt_send() 호출하여 rdt 송신모듈로 데이터를 전달한다. 

송신 측 rdt에서 메시지에 시퀀스 번호(seq#), checksum 등 헤더를 붙여 하나의 패킷(packet)을 생성하여 udt_send()를 호출하여 네트워크로 패킷을 전송한다.

unreliable channel을 통해 전송된다.

수신 측에서 채널을 통과한 packet을 수신한다. rdt_rcv() 호출로 rdt 수신 모듈에 전달한다. 수신 측 rdt에서 checksum 검사, 시퀀스 번호 확인을 하여 정상 패킷이면 원본 메시지를 복원한다. deliver_data()를 호출하여 rdt 수신 모듈이 정상 복원된 데이터를 애플리케이션에 전달한다.

 

 

FSM으로 살펴보는 rdt 전송 프로토콜

FSM 형식

event / actions : 상태 전이를 유발하는 사건 / 동작 

state: 현재의 상태를 나타냄

--> : transition, 상태의 전이를 나타냄 

 

rdt1.0: reliable transfer over a reliable channel

(신뢰성 있는 채널, 비트 오류 및 패킷 손실 없음)

 

sender 측

초기 상태: 애플리케이션으로부터 rdt_send 호출을 기다리는 상태 

 

event: rdt_send(data)

packet=make_pkt(data): 데이터를 담은 패킷 생성

udt_send(packet): 하위 (불안정한) 채널로 패킷 전송 

 

receiver 측

초기 상태: 하위 채널로부터 rdt_rcv 호출을 기다리는 상태 

 

event: rdt_rcv(packet)

extract(packet, data): 패킷에서 순수 데이터 부분만 추출

deliver_data(data): 애플리케이션에 데이터 전달

 

rdt2.0: channel with bit errors

(채널에 비트 오류가 있는 경우)

물리 매체 전송 과정에서 비트가 뒤집힐 수 있다. checksum을 이용해 bit errors를 탐지할 수 있지만 제한적이다. 

오류 복구 전략: ACK, NAK

ACK: 수신자가 송신자에게 제대로 받았다고 알려주는 메시지 

NAK: 수신자가 오류가 난 패킷을 받았다고 송신자에게 재전송을 요청하는 메시지 

수신자와 송신자는 서로 메시지를 제대로 받았는지 자체적으로 알 수 없으므로 상태를 알리기 위한 메시지 교환이 필요한 것이다. 

 

stop-and-wait 방식

한 번에 하나의 패킷만 보내고, 수신자로부터의 응답(ACK/NAK)을 받은 뒤에야 다음 패킷을 보낸다. 

 

sender 측 

상태 1: 애플리케이션이 rdt_send 호출을 기다리는 상태

 

event: rdt_send(data)

sndpkt=make_pkt(data, checksum): 데이터와 checksum으로 패킷 생성

udt_send(sndpkt): 하위 채널로 전송

 

상태 2: ACK/NAK이 올 때까지 대기

 

event: rdt_rcv(rcvpkt)&&isNAK(rcvpkt): 수신자로부터 도착한 NAK인 경우 

udt_send(sndpkt): 동일한 패킷 재전송 

상태 전이 없음

 

evenr: rdt_rcv(rcvpkt)&&isACK(rcvpkt): 수신자로부터 ACK이 도착한 경우 

actions 없이 초기 상태로 돌아가 다음 애플리케이션 데이터 전송 준비 

 

receiver 측

event: rdt_rcv(rcvpkt)&&corrupt(rcvpkt): 패킷이 도착했는데 체크섬 검사 결과 오류 발생

udt_send(NAK): 이 패킷에 오류가 있으니 재전송해 달라는 의미로 전송 

 

event: rdt_rcv(rcvpkt)&&notcorrupt(rcvpkt): 패킷이 도착했고 체크섬 검사 결과 정상

extract(rcvpkt, data): 패킷에서 원본 데이터만 추출

deliver_data(data): 애플리케이션에게 전달 

udt_send(ACK): 송신자에게 정상 수신했다는 의미로 ACK 전송

 

rdt2.0에서 ACK/NAK 패킷 전송 중 비트 오류가 발생할 수 있다는 문제점이 있다.

ACK을 NAK으로 받으면 불필요하게 재전송하고, NAK을 ACK으로 받으면 오류가 난 패킷을 무시하고 넘어가게 된다. 중복(duplicate) 처리가 불가능하다.
해결책으로는 시퀀스 번호(sequence number)를 도입하는 것이다.

 

rdt2.1: handling garbled ACK/NAKs

(bit errors와 ACK/NAK 오류까지 고려)

시퀀스 번호를 도입하고, 중복(duplicate) 패킷을 검출한다. ACK/NAK에도 시퀀스 번호를 포함하여 정확히 어느 패킷에 대한 응답인지 식별한다.

 

기본 아이디어: 각 데이터 패킷에 0 또는 1의 시퀀스 번호를 부여한다. 수신자는 마지막으로 정상 처리한 seq을 기억해, 동일 seq가 오면 중복으로 간주하고 버린다. ACK/NAK에도 시퀀스를 담아 송신자는 어떤 패킷에 대한 응답인지를 확실히 알 수 있다. 

 

sender 측

상태 1: Wait for call 0 from above(다음에 보낼 패킷의 시퀀스 번호가 0)

event: rdt_send(data)

sndpkt = make_pkt(seq=0, data, checksum)  
udt_send(sndpkt)  

상태 2로 전이

 

상태 2: Wait for ACK or NAK 0 

event: rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && isACK(rcvpkt) 

상태 3으로 전이 

event: rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt))
udt_send(sndpkt): 동일한 seq=0 패킷 재전송 

상태 3: Wait for call 1 from above

event: rdt_send(data)

sndpkt = make_pkt(seq=1, data, checksum)  
udt_send(sndpkt)  

상태 4로 전이 

 

상태 4: Wait for ACK or NAK 1

event: rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && isACK(rcvpkt)

상태 1로 전이 

event: rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt))
udt_send(sndpkt): 동일한 seq=1 패킷 재전송 

 

 

receiver 측

각 상태에서 패킷이 도착(rdt_rcv(rcvpkt))했을 때, 세 가지 경우로 나눠서 처리한다. 

1. 패킷 오류(corrupt)
2. 올바른 패킷 & 기대 seq
3. 올바른 패킷 & 중복 seq

상태 1: Wait for 0 from below(seq=0인 패킷을 받을 준비가 된 상태)

event: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)

extract(rcvpkt, data): 원본 데이터 추출

deliver_data(data): 애플리케이션 층에 전달 

sndpkt=make_pkt(ACK, chksum): ACK 패킷 생성

udt_send(sndpkt): 생성한 ACK 패킷을 하위 채널로 전송

상태 2로 전이

 

상태 2: Wait for 1 from below(seq=1인 패킷을 받을 준비가 된 상태)

event: rdt_rcv(rcvpkt) && corrupt(rcvpkt): 패킷이 손상됨

sndpkt=make_pkt(NAK, chksum)

udt_send(sndpkt): NAK 패킷 만들어서 재전송해 달라는 신호 보냄

 

event: rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt): 이미 처리한 패킷이 중복으로 들어왔을 때 

sndpkt=make_pkt(ACK, chksum): ACK 만 다시 전송하여 수신했다는 신호를 보내줌

udt_send(sndpkt)

 

event: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt): 기대하던 정상 패킷이 도착했을 때 

extract(rcvpkt, data)

deliver_data(data)

sndpkt=make_pkt(ACK, chksum): seq1 패킷의 ACK을 전송하여 정상 수신하였음을 알려줌

udt_send(sndpkt)

상태 1로 전이 

 

event: rdt_rcv(rcvpkt) && corrupt(rcvpkt)

sndpkt=make_pkt(NAK, chksum)

udt_send(sndpkt)

 

event: rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq1(rcvpkt)

sndpkt=make_pkt(ACK, chksum)

udt_send(sndpkt)

 

sender 측에서 다음에 보내야 할 패킷의 번호가 0인지 1인지 확인해야 하므로 상태의 개수가 두 배로 증가한다.

receiver 측에서는 자신이 보낸 ACK/NAK이 송신자에게 제대로 도달했는지 알 수 없다.

 

rdt2.2: a NAK-free protocol

오류 발생 시, 이전에는 NAK을 보냈다면 이제는 마지막으로 수신한 패킷의 ACK을 반복해서 보낸다.

송신자는 같은 ACK(seq)이 연속으로 도착하면, 재전송을 수행한다. 

 

 

sender 측

 

event: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 1) ): 패킷 손상 또는 잘못된 seq=1 ACK 수신(NAK을 의미)

udt_send(sndpkt): 동일한 seq=0 패킷 재전송

 

event: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt, 0): 올바른 ACK 도착 

 

receiver 측

 

event: rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)): 패킷 손상 또는 이미 처리한 seq=1인 중복 패킷 수신(NAK을 의미)

udt_send(sndpkt): 이전에 보냈던 ACK0 패킷 재전송

 

event: rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt): 올바른 패킷이 도착한 경우

extract(rcvpkt, data)

deliver_data(data)

sndpkt=make_pkt(ACK1, chksum)

udt_send(sndpkt)

 

rdt3.0: channels with errors and loss

bit errors와 패킷 손실까지 고려한 프로토콜 

 

핵심 아이디어: 송신자 측에서 데이터 패킷 전송 후에 일정한 시간 내에 ACK이 도착하지 않으면 재전송한다. 

만약 ACK이 늦게 도착했다면 수신자는 중복 패킷을 받게 되는데, 시퀀스 번호가 있기 때문에 중복 여부를 판별 가능하다.

 

sender 측 

데이터 전송 시 start_timer

1. 정상적으로 ACK 수신 시 stop_timer, 다음 상태로 전이

2. 패킷 손실, ACK 손실, 오류, 잘못된 ACK일 경우에 무시하고 상태 유지

3. ACK이 정해진 시간 안에 도착하지 않으면 udt_send(sndpkt) 재전송 후에 start_timer

 

ACK이 손실되었는지, 단순히 늦었는지 송신자는 알 수 없기 때문에 합리적인 시간을 정하고 그 시간 안에 ACK이 도착하지 않으면 재전송한다. 

 

1. 정상적인 경우

 

 

2. 패킷 손실(Packet loss)

pkt1이 손실되면 수신자는 아무런 응답을 안 한다. 송신자는 timeout(타이머 만료)을 통해 이상을 감지하고 pkt1을 재전송한다. 

 

3. ACK 손실

ACK이 송신자에게 도착하지 않으면 송신자는 timeout이 발생하고 송신자는 ACK을 못 받았으므로 pkt1을 재전송한다. 수신자는 중복인 줄 알고 데이터는 재전달하지 않고, ACK만 재전송한다. 

 

4. ACK 지연으로 인한 조기 재전송(premature timeout, delayed ACK)

ack1이 네트워크 지연으로 송신자 타이머보다 늦게 도착하는 경우, 송신자는 timeout으로 pkt1을 재전송한다. 수신자는 중복을 감지하고 데이터는 전달 안 하고 ACK만 재전송한다. 이후에 송신자가 ack1을 받게 되면 무시한다. 

 

rdt3.0의 성능

utilization(송신자 이용률): 송신자가 실제로 채널에 데이터를 보내는 데 소요한 시간의 비율

 

rdt3.0: pipelined protocols operation

 

핵심 개념: 송신자가 여러 개의 패킷을 한 번에 보내고, 각각의 ACK을 나중에 받는 pipelining 방식 

ACK을 기다리지 않고 연속적으로 패킷을 전송하는 in-flight 패킷을 허용한다. 

이용률(utilization) 증가!

 

Go-Back-N

sender 측

송신자는 최대 N개의 연속된 패킷을 ACK 없이 전송할 수 있다. 이를 sliding window라고 부른다. 

각 패킷에 시퀀스 번호를 부여한다. 

send_base: 아직 ACK을 받지 못한 가장 앞쪽 패킷의 시퀀스 번호

nextseqnum: 다음에 보낼 시퀀스 번호 

nextseqnum < send_base + N 이면 패킷 전송이 가능하고 보낼 때마다 nextseqnum += 1을 해줘야 한다. 

ACK 수신 시 cumulative ACK 기법을 이용한다. ACK#이 n이면, n번까지 모두 수신 완료로 간주한다. send_base=n+1

단 하나의 타이머만 사용하고, send_base에 해당하는 패킷이 지정된 시간 내에 ACK을 받지 못하면, 송신자는 그 이후 모든 패킷도 받지 못했을 거라고 가정하고 아직 ACK을 받지 않은 모든 in-flight 패킷들을 전부 재전송한다. (send_base ~ nextseqnum-1)

 

receiver 측

수신자는 오직 in-order 패킷만 ACK 처리한다. out-of-order 패킷을 그냥 버린다.

rcv_base: 다음으로 기대하는 시퀀스 번호

-패킷이 도착했을 때, 정상적인 경우(seq==rcv_base)

데이터를 상위 계층에 전달하고 ACK을 전송한다. rcv_base+=1

-순서가 어긋난 경우(seq > rcv_base)

패킷을 폐기하고 마지막으로 성공적으로 받은 in-order 패킷에 대한 ACK을 재전송한다. 

-중복된 패킷인 경우(seq < rcv_base)

데이터는 다시 전달하지 않고 ACK만 재전송한다. 

 

Go-Back-N: extended FSM

sender 측

전체 상태: Wait

 

1. rdt_send(data) (애플리케이션에서 송신 요청)

if (nextseqnum < base + N) { #전송 윈도우 안이므로 전송 가능
    sndpkt[nextseqnum] = make_pkt(nextseqnum, data, checksum) #전송할 새 패킷 생성 후 udt_send로 전송
    udt_send(sndpkt[nextseqnum])
    if (base == nextseqnum) #현재 윈도우에 아무것도 없는 경우
        start_timer #가장 오래된 미확인 패킷에 대해 타이머 설정
    nextseqnum++ 
} else {
    refuse_data(data) #윈도우가 가득 찬 경우, 데이터 송신 거부
}

 

2. rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) (정상 ACK 수신)

base = getacknum(rcvpkt) + 1 #수신된 ACK에서 인정된 시퀀스 번호(n)를 확인하고 base=n+1로 업데이트, 이는 cumulative ACK
if (base == nextseqnum) #모든 패킷이 ACK 되었다면, 타이머 종료
    stop_timer
else
    start_timer #아직 미확인 패킷이 남아있는 경우, 타이머 재시작

 

3. rdt_rcv(rcvpkt) && corrupt(rcvpkt) (손상된 ACK 수신)

아무것도 하지 않고 상태 유지, 수신된 패킷이 손상되었으므로 무시한다. 

 

4. timeout (base에 해당하는 패킷에 대한 타임아웃 발생) 

start_timer
udt_send(sndpkt[base]) #base부터 nextseqnum-1까지의 모든 미확인 패킷을 재전송

udt_send(sndpkt[base+1])
...
udt_send(sndpkt[nextseqnum - 1])

 

receiver 측

1. 초기화 상태 

expectedseqnum = 1 #수신자는 처음에 seq=1 패킷을 기대 
sndpkt = make_pkt(expectedseqnum, ACK, chksum) #이 경우에 expectedseqnum이 1이므로 ACK1을 전송하여 pkt1이 도착한 것으로 간주된다. 그러므로 sndpkt = make_pkt(0, ACK, chksum)으로 작성해야 0번 패킷을 기다림. 즉, 아무것도 못 받았음을 알릴 수 있다. 

 

2. rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum) (정상적인 순서의 패킷 수신)

extract(rcvpkt, data)
deliver_data(data)
sndpkt = make_pkt(expectedseqnum, ACK, chksum)
udt_send(sndpkt)
expectedseqnum++ #기대하는 시퀀스 번호를 1 증가

 

3. any other event (기타 모든 경우, out-of-order, 손상된 패킷 등) 

udt_send(sndpkt) #수신자는 데이터를 무시하고 마지막으로 수신된 in-order 패킷에 대한 ACK만 재전송

 

Go-Back-N: in action 

pkt2 손실 발생

pkt3은 도착했지만 out-of-order 패킷이기 때문에 수신자는 버리고 ack1을 재전송 

송신자는 pkt0과 pkt1에 대한 ACK을 받고 pkt4와 pkt5를 전송

그러나 pkt2는 ACK이 오지 않아 timeout 발생

송신자는 pkt2, pkt3, pkt4, pkt5 전부 재전송(GBN의 핵심 특성! 패킷 하나라도 ACK을 못 받으면 그 이후 모든 패킷 재전송) 

 

 

<시퀀스 번호가 순환되는 경우>

pkt2 손실 

송신자는 ack0, ack1 수신하여 pkt3, pkt0(두 번째 순환된) 전송 

수신자는 pkt3, pkt0은 out-of-order 패킷이므로 버리고 ack1 반복 전송

pkt2 timeout 발생

손실된 pkt2부터 다음 패킷들을 재전송

pkt0이 재사용되므로 주의해야 한다. 

 

Selective repeat

GBN 방식에서는 문제없이 받은 패킷들을 전부 폐기하고 재전송해야 하므로 낭비가 발생한다. 이를 해결하기 위한 방법으로 고안된 selective repeat 방식은 손실되거나 오류 난 패킷만 개별적으로 재전송하는 방식의 신뢰성 있는 전송 프로토콜이다. 

 

GBN과 다르게 N번 ACK을 수신하면 N번 패킷에 대한 것으로 N-1번 패킷 수신 여부에 대해서는 알 수 없다. (cumulative ACK 방식이 아님), 개별 패킷에 대해 개별로 수신을 확인해야 한다. 따라서 각 패킷마다 타이머가 필요하다. 

 

 

sender 측

애플리케이션 계층에서 데이터가 내려왔을 때, send_baes ≤ 시퀀스 번호 < send_base + N 범위만 전송 가능

특정 시퀀스 번호 n의 타이머가 만료된 경우에 해당 패킷 n을 재전송하고 타이머 재시작 

ACK 수신 시, n번 패킷을 수신 완료 표시한다. 만약 n이 가장 오래된 미수신 패킷(n==send_base)이라면, 그다음 연속적으로 받은 ACK들을 확인하여 send_base를 가능한 만큼 앞으로 이동시켜 윈도우를 갱신한다. 

 

receiver 측

rcv_base ≤ 시퀀스 번호 < rcv_base + N 만 수신 및 버퍼링 가능

ACK(n)을 전송하고 버퍼링 한다. 만약 n==rcv_base라면 순서 맞는 패킷 및 그 이후 버퍼에 있는 순서가 맞는 패킷들까지 모두 상위 계층으로 전달한다.

이미 윈도우를 지나간 오래된 패킷을 수신한 경우(rcv_base ≤ 시퀀스 번호 ≤  rcv_base - 1)에 ACK(n)을 재전송한다. 

나머지는 무시한다. 

 

Selective Repeat: in action 

수신자는 out-of-order 패킷을 수신하면, receiver window buffer에 저장한다. 

pkt loss 된 pkt이 timeout이 발생하면 해당 패킷만 재전송한다. in-order 패킷 수신 시, 버퍼에 저장되어 있던 연속된 pkt들 모두 상위 layer로 전송한다. 

 

out-of-order 패킷을 재활용 가능하다는 장점이 있지만, 타이머의 개수가 증가하고 복잡도가 증가한다는 단점이 있다. 

Selective Repeat 방식은 out-of-order 수신을 허용하므로 receiver가 buffering을 한다. 시퀀스 번호는 순환하므로 과거 패킷과 현재 패킷이 구분되지 않는 문제가 발생할 수 있다. 이 문제는 window size가 너무 작기 때문에 발생한다. 

 

k bit 시퀀스 번호를 사용하는 경우에 총 2^k의 번호를 표현 가능하므로, 시퀀스 번호가 반복되기 전에 명확하게 구분이 가능해야 한다. 따라서 시퀀스 번호 공간을 절반으로 나눠서 sender와 receiver window가 겹치지 않게 제한해야 합니다.

 

GBN에서도 비슷한 문제가 발생한다.

receiver가 이미 한번 받았던 seq 번호가 다시 도착했을 때, 이게 이전 패킷의 재전송인지 아니면 진짜 다음 window의 패킷인지 판단 불가능하다는 것이다. 

GBN에서는 수신자가 한 번에 딱 하나의 expected sequence number만 기억하므로, window size는 전체 시퀀스 공간보다 작아야 한다.