Principle of Reliable Data Transfer

reliable data transfer

신뢰성이 있다는건
1. 오류 없이 목적지까지 전달
2. 손실없이 전달
3. 순서에 맞춰서 전달
을 의미한다.

안정적인 데이터 전송이란, 다음과 같은 요소를 포함해야한다.

1. reliable channel
2. sender, receiver

하지만 실제 채널은 안정적이지 못하다 .

응용계층 측면에서는 사실 transfer가 어떤지는 잘 모르고 그냥 reliable하다고 믿고 보낸다. 하지만 실제로는 프로토콜 없이는 unreliable하다. 즉, reliable하기 위해서는 보내는 쪽, 받는 쪽 둘 다 rdt 프로토콜이 필요하다. 결국 rdt 프로토콜이 application이 요구하는 신뢰성 있는 transfer에 대한 책임을 지어야만 한다.

상태 공유

sender, receiver는 각각 상대방이 어떤 상태에 있는지 알지 못한다. 그럼 이들은 어떤 방식으로 상태를 공유할까?

유한 상태 머신

유한상태기계는, 주어지는 모든 시간에서 처해 있을 수 있는 유한 개의 상태를 가지고 주어지는 입력에 따라 어떤 상태에서 다른 상태로 전환시키거나 출력이나 액션이 일어나게 하는 장치 또는 그런 장치를 나타낸 모델이다.

출처

이제 이 상태머신을 통해서 각 단계별로 rdt의 상태를 알아보겠다.

가장 단순한 경우

이 경우는 channel 이 reliable하다.

• 오류 없음
• 패킷손실 없음

FSM

Sender : Wait for call from above 상태 -> rdt.send()라는 요청(액션)

Receiver : Wait for call from below 상태 -> Rdt.receive를 통해 패킷, 데이터를 받고 deliver하면 된다.

매우 단순해서 따로 살펴볼게 없다.

Channel Bit Error

• 채널에서 비트플립이 발생할 수도 있다.
• 하나의 오류만 발생해도 이를 역추적할 수도 없고, 체크섬으로 에러가 나면 그냥 패킷을 통으로 버려야한다. 이러면 재전송 요청말고는 방법이 없다.
  -> 재전송을 위한 알고리즘이 필요함

이를 위해서는 받음 상태를 알려주기 우한 acknowledgement(ACK)를 내야한다. (오류있으면 NAK)

FSM

Sender의 경우 Wait for call from above 상태, 그리고 이를 send하고 나면 ACK/NAK를 기다리는 상태로 전환된다.

이 상태에서 NAK를 받으면 에러발생을 의미, 재전송을 해주낟.
ACK를 받으면 다시 대기상태로 넘겨준다.

---

Receiver의 경우 기존처럼 응답받는 state하나이다. 이때 액션은 corrupt의 경우 nak를 반환하고 ack면 그냥 ack 반환하고 deliver 해준다.

FATAL FLOW!!!

이 방식에는 가장 큰 문제가 하나 있다.

만약 ACK/NAK가 오류나면 어떨까?

피드백이 왔는데 오류라면 해당 피드백에 대한 추측을 하지 말고 그대로 버려야한다. 그리고 sender는 이러나 저러나 재전송을 한다.

만약 이러면 receiver에서는 이게 ack인데 또 보낸거라 다음 패킷인건지, 아니면 nak에서 재전송해준 건지 알 수가 없다. 따라서 패킷을 구분해줄 수 있는 sequence number를 보내줘야한다. 즉, receiver입장에서 패킷구분을 해주는게 필요하다.

FSM

Sender

Sender
4개의 state가 생긴다.
Wait for 0 from above

• Make pkt 해서 보내고, ACK0 대기상태로 감

Wait for ACK or NAK 0

• Ack 를 받아서 노커럽트면 1 대기 상태로 넘어간다
• 커럽트 상태인 경우, 다시 send 해준다.

Wait for 1 from above

• 위와 마찬가지로 ack1 대기상태로 넘긴다,

Wait for ACK, NAK 1

• No corrupt당시 0 대기상태로 돌린다.
• 커럽트인 경우 다시 보내준다.

이런 경우
1. ACK인데 NAK가 오더라도 다시 보내서 괜찮다
2. NAK인데 ACK가 오는경우는?

Receiver

Receiver는 State가 2개이다
Wait for 0 , Wait for 1

에러가 없는 경우 ack를 반환하고 1상태 혹은 0상태로 이동한다.

만약 깨져있다면, NAK를 보낸다.

이때
만약 Wait 1상태인데 0번이 온다면, 이는 ack가 깨져서 sender에서는 nak로 본 상태이다. 이미 멀쩡한 패킷이 올라갔으니깐 따로 deliver할 필요는 없고 seq를 보고 ack0를 만들어서 sender한테 보내줘야 sender가 정상처리 된 것을 알고 보낼 수 있는것이다.

이는 wait 0일떄도 마찬가지이다.

위에서 가정한대로 NAK를 보냈는데 ACK로 인식해서 리시버가 다음걸 보내주게 된다면, 리시버는 아직 상태가 변하지 않았기때문에 Sender가 잘못보낸것을 알 수 있고 다시금 NAK를 보내게 될 것이다.

지금은 stop and go 방식이라 2개만 보내고 seq가 0 1 만 있어도 되고, ack도 체크하니깐 이를 위한 state가 늘어난다.

NAK-Free

긍정이 오지 않으면 그건 즉 부정이다.

!true = false

즉, NAK를 없앨 수 있는 방법이 있다. Receiver가 가장 마지막으로 받은 정상 seq의 ACK를 보내주는 것이다. 즉, sender가 1번을 보냈는데 ACK가 0이 오면 에러가 난 것을 인지할 수 있는것이다.
TCP가 이를 사용한다.

FSM

Sender의 경우

Wait for 0 from above
Wait for ACK0

• 여기서 ACK1을 받아버리면, receiver가 오류난걸 알린다고 판단, 0을 다시 보내준다.

Receiver의 경우

Wait for 0 from below

• Seq가 다르거나, corrupt하게 오면, ACK1을 담은 pkt를 sender한테 보내준다.
• 즉 바로 전 단계 ACK를 보낸다.

이 경우에선 0을 보냈는데 1이 온 경우 : 아무일도 안한다 -> 왜?
만약 이 ACK가 오류가 아니라 지연된 에크라면?
이를 대비하는 타이머 기능이 추가된다.

Channel error and loss

error말고도 로스가 발생할 수 있는데, 이 경우는 어떻게 처리해야할까?
로스는 받는쪽에서는 이게 로스가 났는지 아닌지 알 길이 없기에 무조건 sender가 해결해줘야한다

Reasonable한 시간을 기다려보고, sender가 아무런 ack를 받지 못했으면 retransmission한다. 만약 패킷이 실종된게 아니라 그냥 지연된거라면

1. 재전송은 복사되지만, seq로 인해서 중복처리는 해결된다.
2. 리시버는 받고 나면 무조건 ack를 보내줘야한다. 그래야지 혹시라도 먼저 보낸 ack가 에러나더라도 sender가 받은걸 알 수 있다.

Timeout의 적당량은 알아서 조절해야한다.

FSM

Sender

Wait for 0 from above

• 보내는것과 동시에 timer를 돌린다.
  Wait for ACK 0
• 잘 받으면 타이머를 멈춘다
• 못받으면, 즉 timeout이 되면 재전송하고 타이머를 다시 구동한다.
• 혹은 피드백을 받았는데 깨졌거나, ACK1이 오거나 하면 아무일도 하지 않는다. 재전송은 timeout의 경우에만 재전송을 한다. 만약 진짜 오류여도 그냥 timeout을 믿고 재전송을 안해주는것이다.
  Wait for 1 from above
• 이 상태에서는 아무것도 오면 안되는데 뭔가가 올 수 있는 환경이다 따라서 이런 경우는 그냥 무시해야한다.
  Loss의 경우에는 Timer말고는 사실 별로 해준게 없다.

Receiver의 경우

loss는 보낸 쪽이 전적으로 이 감당을 해야하기 때문에, Receiver는 사실 2.2 NCK-free랑 다를게 없다.

문&답

Pkt 0을 보냈는데 ACK 1이 온 경우 : 아무일도 안한다 -> 왜?
만약 이 ACK가 오류가 아니라 지연된 에크라면 어떨까? 즉, 아까 보낸 1에 대한 답이 지금온거라면 이걸 보고 아 이거 틀렸네 하고 다시 0을 보내주는건 낭비가 된다. 그냥 타이머가 모든 오류를 처리하게 놔두는것이 좋다고 본다.

Performance Check

1기가비트의 링크, 15ms prop. delay, 8000bit 패킷이라고 하자.

Trans Delay = L/R = 8000 bits / 10&9 bits = 8mircosec

T = RTT + L/R -> 1패킷 전송시간 즉 낭비요소가 굉장히 크다.

Usender = L/R / (RTT + L/R) = 0.008 / 30.008 = 0.0027

링크는 좋은데 프로토콜 효율이 너무 떨어져서 별로인것이다. 이에 ACK를 허용량까지 전부 보내버기로 ACK가 오면 빈자리에 또 보내는 방식을 써보도록 하자.

ACK허용량을 3까지만 줘도
Usender = 3*L/R / (RTT + L/R) = 0.024 / 30.008 = 0.0081
즉, 성능이 훨씬 좋아진것을 볼 수 있다.

Go-Back-N Sender

Window 사이즈만큼(n) 허용 그 개수만큼 보내라 즉, unAck인데도 보낼 수 있는 개수이다. 물론 이 구분을 위해서 k-bit > n인 시퀀스 넘버를 준비해야한다.

이 방식은 cumulative ACK방식을 사용하는 프로토콜이다.
에크가 순서가 뒤바뀐채로 오는 경우 이 프로토콜에서는 그러면 가장 마지막 에크전에 모든 패킷은 정상전달 되었다고 인정해버리고 넘어간다. 즉 12345는 loss되고 6만 오더라도, 123456 전부 인정하는것이다.

예시

예시) 12 3(x) 45 로 온다고 가정하면
Receiver는 ack1, ack2 까지는 정상으로 보낸다. 그리고 3이 없는데 ack4를 보내 줄 수 없다. 이에 receiver는 ack2를 보내준다(가장 최근에 받은 정상ack) 5번에 대해서도 마찬가지로 ack2를 보낸다. 그러면 sender는 ack2만 받으니깐 1 2만 갔다고 판단 3 4 5 를 다시 보내버린다.
이와 반대로 Select Repeat방식은 각각의 에크를 보고 없는 것만 보내준다.

타이머

고백N 방식에서는 에크 하나를 받으면, 안받은 에크들 중 가장 오래된 패킷의 타이머를 돌리고 에크가 오면 종료하는 방식이다. 만약 2번에서 오류가 나서 ack1만 오면 T2은 해결될 수 없고 계속 돌다가 오류를 뱉어내고 다시 2부터 보내주는 방식이다.

Receiver Window

고백 N은 딱 하나만 기다린다. 따라서 제대로 받은 마지막 ACK에 대한 순서가 중요하다. 그래서 순서가 잘못오면 리시버쪽에선 전부 버려버린다.

Selective Repeat

리시버는 각 패킷별로 개별적으로 ACK를 전달한다. 즉, 다음 그림과 같은 그림이 가능한것이다.

이 방식ㅇ느 순서가 뒤바뀐채로 와도 별 문제가 없지만 이로 인해서 window위치랑 base위치가 어긋나는 경우가 생길 수 도 있다. (어긋나는 가장 큰 값은 N)

즉, sender는 window만큼 다 보냈고 receiver는 이를 다 보내서 ack를 보내고 window를 뒤로 미뤘지만, ack가 도착하지 않아서 어긋나는 경우이다.

타이머

이 경우, 각 Pkt별로 타이머를 따로 돌리면서 ack가 오면 타이머를 종료해줘야한다.

윈도우의 크기와 어긋남

윈도우의 크기는 가장 작은 unAcked 부터 window 크기만큼이다

SR 기능 정리

sender

data from above

윈도우안에 보낼 수 있는 seq가 있으면 보낸다

timeout

타임아웃이 나면 타이머를 다시 시작하고 다시보내준다

범위 안의 ACK

[sendbase, sendbase+N] 즉, 현 위치부터 윈도우 안에서 오는 ACK의 경우 패킷을 받은걸로 처리하고 만약 온 ack가 unACK중 가장 작은 값이면 윈도우를 다음 unACK로 이동한다.

Receiver

범위 안의 Packet

[rcvbase, rcvbase+N-1] (즉 현재 받아야하는 rcv 부터 window 하나전까지)

1. 정상도착시 ACK 발송
2. 순서가 안맞으면 buffer에 저장한다
3. 정상도착은 deliver한다.

범위안의 패킷 재전송시

[rcvbase-N,rcvbase-1], 즉 현재 rcvbase부터 윈도우 크기만큼 전, 즉 sender의 window와 어긋날 수 있는 최대범위내에서 뭔가 온다면 이는 받아서 acka만 다시 보내준다.

범위 밖의 패킷 재전송시

범위 밖에 있는건 좀비패킷이니깐 무시한다.

SR의 딜레마

다음과 같은 상황을 가정하자
seq num = 0 1 2 3
window size = 3

위와 같은 상황에서 두가지의 전송상황을 보도록 하겠다.

a의 경우 pkt 0 1 2가 다 정상적으로 갔고 받아졌지만 pkt2번에서 ack오류가 난 경우이다. 이때 sender와 receiver의 window를 보면 서로 겹쳐있지 않은것을 볼 수 있다.

하지만 b의 경우, 0 1 2 모든 ACK가 오류가 난다. 이러면 Receiver의 window는 옆으로 3칸 이동했지만 sender는 하나도 움직이지 못했다. 이 상황에서 sender가 pkt0을 다시보내면 이는 실제로는 첫번째의 0이 되겠지만, sender에서는 301즉 5번째로 오는 0으로 받아들이게 된다.

왜?

이런 문제들은 시퀀스넘버 중복 때문에 발생한다. 이를 해결하려면 스퀀스 넘버를 늘려야한다. 이때 중복되지 않으려면 Seq 넘버는 2*n보다 크거나 같아야한다. 최대한 둘이 어긋나는 경우가 N N 이기 때문이다.

이는 SR말고 GBN에서도 동일하게 적용된다. 정확하게는 2N이 아니라 Sender Window size + receiver Window Size이다.