[Transport Layer] 신뢰적인 데이터 전송의 원리

신뢰적인 데이터 전송을 구현하는 문제는 전송 계층 뿐만 아니라, 링크 계층과 애플리케이션 계층에서도 발생하는 문제이다. 

Some limitations of the channel

채널이 불안정한 상황들

• drop msgs
• reorder msgs 
• deliver duplicate copies of a given msg
  ACK가 와야 도착했다고 생각 → 늦어지면 재전송 (delay가 길었을 경우)
• limit msgs to finite size
• deliver msgs often an arbitary long delay

 

신뢰적 데이터 전송

Frame Format

전체 패킷 format

Reciver pkt number

▷ piggy-backing : for reverse direction of data flow

 

ARQ Protocol

Automatic Repeat reQuest 자동 재전송 요구

retransmission algorithms

 

idea : to detect frame with errors at the receiver and then request the sender to retransmit

 

Stop and Wait Protocol

가장 기본이 되는 프로토콜이다.

• send a pkt from A to B
• B sends  ACK if the pkt is received correctly 
                  NCK if the pkt is corrupted
• if ACK → send next pkt
• if NACK or timeout → retransmit

 

pkt 번호 & ACK 번호

pkt, ACK 번호의 유무 차이

* timeout : pkt을 보내고 송신단에서 일정 시간 안에 신호를 받지 못하면, timeout이 일어난다. →  retransmit

문제점  : pkt이 0인지 1인지 모른다. 

∴ packet에 Number을 달아야한다.

 

두번째 그림을 보면, 지금 ACK가 두번이 왔는데, 두번째 ACK가 pkt1 뒤에 왔기에 pkt1을 받지 못했음에도 pkt1을 받았다고 인식할 수 있다.

문제점 : ACK가 어떤 pkt을 받아 보내는 ACK인지 모른다.

∴ ACK에 Number을 달아야한다.

 

세번째 그림을 보자

이를 통해 몇번째 패킷을 보내고 몇번째 패킷에 대해 ACK , NACK 을 받았는지 확인할 수 있다.

 

ACK 0의 의미

• ACK0 : 수신자가 pkt0을 성공적으로 받았다는 것을확인해주는 의미
• RN1 : pkt0을 받았기 때문에, 다음에 오는 Receiver Next 1, 즉 다음에 받을 pkt 번호가 1이라는 의미이다.

*RN과 SN의 경우, 인접한 것만 구분하면 되므로 1bit, 즉 0과 1만 사용한다.

만약, 3번째 그림에서 다음 패킷까지 보내야하는경우, pkt0(3번째 패킷)을 보내고, ACK 0을 재전송하게 된다.

 

Q) B가 Ack 0을 재전송하는 이유?

A ) B입장에서 A가 Ack를 잘 받았다는 보장이 없기 때문에 반복해서 ACK를 전송

 

---

무손실 동작

이때 ACK0은 RN1과 의미가 같고, ACK1은 RN0과 의미가 같다.

 

Lost Pkt

Lost ACK

Premature timeout

조급한 타임아웃

do nothing 부분 

pck1을 두번 보냈고, ACK1(RN0)을 두번 받았다. 

두번째 ACK1(RN0)을 받기 전에 pkt0을 전송했고, 이에 대한 응답은 ACK0(RN1)이므로 아무것도 하지 않는다.

---

Sender Side의 State Transition Diagram

SN and RN can be 0 or 1 (1bit)

 

Fineate-state machine, FSM to specify sender, receiver

event

------

action

으로 나타냄

• event causing state transmitikon
• actions taken on state transmition

 

 

처리 과정을 한번 자세히 살펴보겠다.

 

패킷을 받는건 언제나 상위 layer에서 받아서 오는 것이다. 

Wait for pkt0 

• pkt0이 상위 Layer에서부터 오기를 기다리는 것이다. 
• pkt이 오지 않는다면 계속 wait한다.
• pkt recived시, send pkt SN=0 (SN0을 받았다)를 보내고 타이머를 시작한다.
• 상위 Layer에서 패킷을 받으면 다음 state로 넘어간다.

Wait for ACK0 / RN=1

•  sender가 receiver로부터 보낸 pkt에 대한 응답을 기다린다.
• 기다리고 있는건 RN=1인데 (다음 패킷이 1을 보내달라)인데, 이미 보낸 RN=0이 오면 아무것도 하지 않는다.
• 설정한 timer에서 timeout이 생긴다면, sender은 패킷을 다시 보내고 타이머를 재시작한다.
• 기다리고 있던 RN=1을 받는다면, 다음 state로 넘어간다.

Wait for pkt1

• pkt1에 대한 요청을 받았으므로 (RN=1) 상위 layer에서 pkt이 전달되기를 기다린다.
• 기다리고 있는 pkt이 오지 않는다면, 계속 wait한다.
• pkt recived(data ready)시, send pkt SN=1(SN1을 받았다)를 보내고 타이머를 시작한다.
• 상위 layer에서 pkt을 받으면 다음 state로 넘어간다

Wait for ACK1 / RN=0

• sender가 receiver로부터 보낸 pkt에 대한 응답을 기다린다
• 기다리고 있는건 RN=0인데, RN=1이 오면 아무것도 하지 않는다
• 설정한 timer에서 timeout이 생긴다면, sender은 패킷을 다시 보내고 타이머를 재시작한다.
• 기다리고 있던 RN=0을 받는다면, 다음 state로 넘어간다.

∴ stop-and-wait is not efficient 이러한 stop-and-wait 프로토콜은 효율이 매우 좋지 않다.

 

Stop-and-wait 예시

1Gbps link, 15msec end-to-end delay
each pkt has length 1KB
RTT = 30msec

Transmission delay

\(L = 8000bit\) = pkt length in bits

\(R = 10^9 bps \) = transmission rate

\(T_{tx} = \frac{L}{R} = 8 \times 10^{-6}sec = 8\mu\text{s}\)

 

Utilization 

fraction of time, sender is busy sending

\(U_{sender} = \frac{L/R}{RTT+L/R} = \frac{0.008}{30.008} = 0.00027 = 0.027%\)

 

따라서 1KB의 패킷을 30ms마다 전송(RTT)할 수 있고, 이는 33.3KB/sec = 264kbps이다. (bps는 bit단위이므로 *8)

 

∴1Gps link를 264kbps로만 활용하므로 비효율적이다. 

 

---

Pipelining

Two ways to handle multiple transmissions

• Go back n (GBN) : N부터 반복
• Selective repeat (SR) : 선택적 반복

 

 

GBN (Go Back N)

ACK를 기다리지 않고, n개의 pkt를 동시에 보낸다. (n = window size)

GBN

첫번째 그림처럼 진행이 된다고 생각하자.

현재 그림은 window sizer가 4라는 전제이다.

즉, pkt2에 대한 응답이 오지 않았으므로, pkt2부터 window size만큼의 패킷을 다시 동시에 전송한다.

 

두번째 그림처럼 진행이 된다고 생각하자.

pkt0에 대한 timeout이 일어나기 전에 RN3이 도착하면,

Cummlative acknowledge에 의해 pkt0, pk1에 대한 것도 받았다는 것을 알려준다.

 

Cumulative acknowledgment

GBN의 특징이다.

ACK3 (RN4) 라는 의미는 window size가 4일때, pkt 0,1,2,3을 받았다는 뜻이다.

이처럼 누적 확인 응답이란, 맨 마지막에 온 응답이 그 전의 모든 패킷이 전송되었다는 것을 보장해준다.

 

window size

• Window size (N) : 해당 그림에서는 14
• base : ACK를 못 받은 가장 오래된 pkt number
• next seq num : 전송될 pkt number (상위 Layer 에서 pkt가 아직 안 내려옴)

 

• [0, base-1] : ACK 받은 pkt
• [base, next seq num -1] : 전송했으나 확인되지 않은 pkt
• [next seq number, base+N-1] : 상위 계층에서 pkt 오면 바로 보낼 수 있는 pkt
• [base+1, ] 파이프라인에서 확인 응답이 되지 않은 패킷 (base의 응답이 도착할 때까지 사용 불가)

 

∴ GBN은 stop-and-wait 보다 효율적이지만, 여전히 효율성이 떨어진다.

 

SN / RN

stop-and-wait 프로토콜의 경우, 1개 단위로 pkt을 전송하고 받기 때문에 인접한 곳과의 pkt에 대해 꼬이지 않도록 mod2로 즉, 0과 1의 SN과 RN이 필요했다.

하지만, GBN의 경우 한번에 여러개의 패킷을 보내야하기 때문에 0과 1 (mod2)로 구분할 수 없다.

 

∴ SN and RN can be sent mod m ≥ n+1 (window size보다 1큰 값으로 구분)

---

Selective Repeat

Selecive Repeats는 GBN과 달리, 전송되지 않은 것이 있다면, 그 뒤는 모두 buffer에 넣고 한번에 전송한다.

 

buffer

이때, 최대 buffer size = window size이다.

또한 Selective Repeat도 윈도우를 가지고 있기 때문에 이를 위해 pkt3이 전송되었을 때 바로 전송하지 않고 buffer에 저장하는 것이다. 

만약, pkt3,4,5를 pkt2가 도착하기 전에 전송하려면 윈도우의 base를 이동해야하는데, 아직 ACK2를 수신하지 못했기 움직이지 않는다.

∴ 수신자가 pkt 3,4,5를 저장할 공간이 필요하다

 

Q) 왜 상위 layer로 전달하지 않는다 (deliver의 의미)

A) Application layer에 혼돈이일어난다.

 

do nothing

현재 window는 n=4일 때, 2,3,4,5에 위치한다.

ACK 3 이 도착했을 때 do nothing 인데, (window를 이동하지 않음) 그 이유는 pkt2를 잘 받았다는 확신이 없기 때문이다.

* GBN의 경우 cumulative acknowledgment를 사용하기 때문에, 만약 ACK3이 되작하면 pkt2도 보장한다.(안 받았으면 다음 ACK 자체를 보내지 않음)

 

따라서, 가장 오래된 pkt에 대한 ACK가 와야 windowd를 이동한다. 

 

SN / RN

mod m ≥ 2n