3.1 principles of reliable data transfer

어떻게 data를 reliable 하게 보내는가

• 어플리케이션 레이어 입장에서는 보내면 reliable이 보장 된다고 생각한다.
  -> 트랜스포트 레이어에서 이 부분을 구현해 줘야함. (아래 레이어들(링크 레이어)은 unreliable한 상황)
  -> 그림의 네가지 함수들을 통해 reliablility 보장(rdt_send(), udt_send(), rdt_rcv(), deliver_data())
• Unreliable channel의 특징이 reliable data trnasfer protocol(rdt)의 복잡성을 결정한다.
  -> 많이 unreliable 하다면 복잡해지겠고, 어느정도 커버 해준다면 덜 복잡해 지고.

동작하는 함수들

-> 샌더와 리시버가 동작하는 방법을 fsm형태로 설계(fsm : 시스템 동작 설명하는 방법)

rdt 1.0: reliable transfer over a reliable channel

• reliable한 채널 위에 만든 경우(아래 래이어가 reliable한 경우)
• underlying channel이 완벽하게 reliable한 경우
  -> bit error가 없다.
  -> 패킷의 loss가 없다.
  -> 할게 딱히 없다.

rdt 1.0: FSM specification

• sender : 어플리케이션 레이어가 데이터를 보내주면 패킷을 만들고(데이터에 헤더를 붙임) 패킷을 아래 레이어로 전송한다.
• receiver : 아래 레이어로부터 패킷을 받으면 패킷에서 헤더 떼서 데이터 추출하고 데이터 전달

rdt 2.0: channel with bit errors

• 비트 에러가 발생하는 경우
  -> 아래 채널이 패킷의 비트를 바꾼 경우
  -> checksum을 통해 bit error를 detect한다.(오류있다는 사실만 알지 어디서 틀린지는 모름)
• 에러를 복구하는 방법
  -> 에러가 있는 패킷을 버리고 송신자에게 알려서 재전송 받아야 한다.
  -> 이것을 위해 feedback을 해 줘야 한다.(control message를 receiver가 sender로 보내줌)
  -> acknowledgements(ACKs) : sender가 receiver쪽으로 패킷을 보내면 receiver가 잘 받았다는 내용이 답긴 작은 패킷을 sender쪽으로 보냄.
  -> negative acknowledgements(NAKs) : 패킷이 왔는데 checksum을 보니 에러가 있어서 에러가 있다는 내용을 sender쪽으로 보냄.
  -> sender 입장에서 NAK이 오면 에러가 있다는 의미이므로 재전송하고 ACK이 오면 잘 받았다는 의미이므로 그냥 넘어감.

rdt 2.0: FSM specification

• sender
  ->데이터를 받으면 패킷을 만들고 보내준 후 ACK이나 NAK을 기다리는 상태로 변경(receiver의 응답 대기)
  -> receiver로부터 패킷을 받고 만약 받은 패킷이 NAK이면 재전송
  -> 패킷 받고 만약 ACK이라면 아무런 action 취하지 않고 상태만 변경
• receiver
  -> 패킷을 받고 받은 패킷이 corrupt라면(checksum을 확인해서 에러 있는 경우) NAK을 보냄
  -> 받은 패킷이 notcorrupt라면 데이터를 추출하여 전송해 주고(어플리케이션 레이어로), sender에게 ACK을 보냄

문제점

• ACK이나 NAK이 제대로 올 것이란 보장이 없다(얘네마저 비트에러가 있을 수 있음).
  -> ack이던 nak이던 다시 전송하면됨
  -> 근데 리시버에서 이미 왔던건지, 새건지 모름
  -> 그저 다시 전송하면 duplicate 가능성 있음
• duplicate 해결 방법
  -> sender는 ACK,NAK에서 corrupt가 일어면 패킷을 재전송 한다.
  -> sender는 각각의 패킷에 sequence number를 붙임
  -> duplicate인지 아닌지 알 수 있음
  -> receiver는 받은 패킷이 왔던것이면 버리고 새것이면 처리해줌

예를들어 sender가 receier에 패킷을 보내서 receiver가 ACK을 보내줬는데 sender에서 못받았다고 하자.
-> 그냥 다시 패킷을 재전송하면 receiver 입장에서 새 패킷인지 왔던 패킷인지 모른다.
-> 그래서 sender가 숫자를 붙여서 0번 패킷을 보낸다.
-> receiver가 받아서 ACK을 보내줬는데 만약 sender가 못받으면
-> sender는 다시 0번 패킷을 보낸다.
-> receiver 입장에서 0번은 왔던거니까 그냥 버리고 ACK만 보내준다.

rdt 2.1: handles garbled ACK/NAKs

• 왜곡된 ACK/NAK 처리하기 -> 위에서 발생한 문제점 해결을 위해 sequence number를 이용
  -> sequence number를 나타내기 위해 1비트만 사용한다(0,1만 구별 가능)
  -> 이것을 통해 ACK/NAK 손실을 해결한다.

rdt 2.1: FSM specification

• sender
  
  -> 첫 상태 : 데이터 받으면 헤더에 0 붙여서 패킷 만들고 보내고 상태 변경
  -> 뭔가 받았고, corrupt이거나 NAK이면 재전송하고 상태 유지(상태 : ACK이나 NAK 0를 기다림) / 뭔가 받았고, notcorrupt이고, ACK이면 상태 변경
  -> 데이터 받으면 헤더에 1 붙여서 패킷 만들고 보내고 상태 변경
  -> 위 내용 반복

• receiver
  
  -> 0번 기다리는 상태 : 뭔가 받았는데 문제없고(notcorrupt), 0번이면 데이터 손질해서 애플리케이션 레이어로 보내주고, ACK 만들어서 샌더로 보내주고 상태 변경
  -> 문제있으면 NAK 만들어서 보냄 / 문제 없는데 1번이면 ACK은 만들어서 보내줌
  -> 둘 다 애플리케이션쪽으로 보내는거 없음, 상태도 변경 아님.(문제가 있거나 이미 받은 패킷이니까)
  -> 1번 기다리는 상태 : 위 내용 반복

논의점

• sender
  -> 패킷에 sequence number를 붙인다.
  -> 0,1 만 써도 충분하다. -> stop and wait을 하기 때문
  -> 받은 ACK/NAK 이 corrupte인지 확인 해야 한다.
  -> ACK이 와야 다음 패킷을 보낸다.
  -> 상태가 두배 많다(전에 온 넘버 기억, 어떤 넘버가 올지 대기)
• sender
  -> 받은 패킷이 중복된것인지 확인해야한다.

rdt 2.2: a NAK-free protocol

• 일반적으로 NAK을 안쓰고 ACK만 쓰는 경우가 많음 -> NAK을 안쓰도록 한거
• 기능은 2.1과 같지만 NAK을 사용하지 않는다.
• NAK 대신에 ACK 활용 : receiver는 제대로 받은 마지막 패킷에 대한 ACK을 보내준다.
  -> 이것을 위해 ACK에 sequence number 넣어서 보내줌
• sender에서 받은 중복된 ACK이 NAK의 기능을 한다.
  -> 중복된 ACK 받으면 현재 패킷 재전송함

rdt 2.2: FSM specification

-> 2.1에서 바뀐 부분만 표현함

• sender
  -> ACK 0를 기다리는 상태에서 corrupt이거나 받은 ACK이 1번이면 재전송 하고 상태 유지
  -> corrupt아니고 0번 ACK이면 다음 상태로 변경
• receiver
  -> 1번 패킷을 받으면
  -> 상태 변경하면서(1->0을 기다리는 상태) sndpkt(ACK1을 가진 패킷) 만들고 상태 변경
  -> 0 기다리는 상태에서 오류가 있거나 받은 패킷이(샌더로부터) 1번이면 sndpkt를 보내고 상태 유지
  -> sndpkt에는 ACK1이 저장되어 있으니까 샌더 입장에서 재전송 해 줘야 하는거

rdt 3.0: channels with errors and loss

• 2번대는 비트에러에 관한 내용
• 3.0 : 패킷로스도 발생할 수 있는 경우(라우터에서 오버플로우가 발생해서(들어오는게 나가는거보다 빨라서) 버퍼가 꽉차서 drop되는 경우)
  -> 샌더는 보냈는데 리시버가 못받은 경우
  -> checksum, seq num, ACK, 재전송은 도움이 될 순 있지만 충분하지 않다.
• 접근
  -> receiver는 아무것도 안받았으니까(패킷이 안온거니까) 동작 안함.
  -> sender는 패킷을 보낸 후 ACK이 올때까지 적절한 시간동안 기다린다.
  -> 이 시간동안 ACK이 안오면 재전송한다.
  -> 어떤 이유로 손실이 아니라 느리게 간 것이라면 그냥 재전송 했을 경우 duplication이 발생한다.(seq num으로 방지할 수 있음)
  -> 타이머를 구현해야 한다.

rdt 3.0: sender FSM specification

-> 초기상태 : 패킷 만들고 전송 한 후 타이머 시작해서 다음 상태로 넘어감
-> 오긴 왔는데 시퀀스 넘버가 다르거나 문제가 있으면 타이머는 그냥 흘러가도록 놔두고 상태 유지
-> 타임아웃이 걸리면 재전송하고 타이머 다시 시작 하고 상태 유지
-> ACK이 제대로 오면 타이머 스탑하고 다음 상태로 넘어감

동작과정

• (d) 이미지
  -> 타이머를 너무 짧게 하면 제대로 보내지긴 하는데 불필요한 재전송이 많아진다
  -> performance 측면에서 안좋다.
  -> 반면 너무 길게 하면 loss 발생 했을때 복구까지 너무 오래 걸림
  -> 적당한 타이머를 구현하는게 중요

performance of rdt 3.0

• rdt 3.0은 동작은 잘하지만 성능이 안좋다(stop and wait 때문)

(예시)

• 전송속도 1 Gbps / 전파속도 15ms / 8000bit의 패킷 보냄 가정
• sender와 receiver 사이가 회선으로 연결되있다고 가정(중간에 라우터 없이)
  -> 전송시간 : 패킷 내보내는데 걸리는 시간 : 8 microsec
  -> 전파시간 : 한 패킷이 끝까지 가는데 걸리는 시간 : 15ms
  -> 보내는데 총 시간 = 전송시간 + 전파시간 = 15.008ms
  -> ACK은 비트수가 작기 때문에 전송시간 매우 작다고 판단해서 무시하고 전파시간만 고려
  -> 따라서 패킷이 가는데 걸리는 시간 + ACK이 오는데 걸리는 시간 = 15.008 + 15 = 30.008ms
  -> 8000비트 보내고 ACK 받는데 30.008ms 걸리는거
  -> 효율성이 매우 떨어진다. (효율성이 1이 제일 좋음)
  -> 즉 하나 보내고 하나 돌려 받는 동안 기다리는 시간이 매우 아깝다

stop-and-wait operation

• 하나 보내고 하나 받고 하는 방식
• 전체 시간(RTT + L/R)에 비해 파일 전송에 걸리는 시간 L/R이 너무 짧다.

Pipelined protocols

• 파이프라인 프로토콜(<-> stop and wait)
  -> 한꺼번에 여러개의 패킷을 보내서 여러개의 ACK을 받자.
  -> 보내지는 여러 패킷들을 구별하기 위해 sequence 넘버가 늘어나야 한다.
  -> 버퍼링이 필요하다.
  -> go-Back-N, selective repeat 이 많이 사용된다.

정해진 개수의 여러개의 패킷을 보내고, ACK이 오는대로(하나씩 올 때 마다) 다음 패킷을 보낸다.
-> 효율성 정해진 개수배 만큼 늘어난다.
-> performance 측면에서 좋아진다.
-> 단점 : 프로토콜이 복잡해진다.

Pipelined protocols: overview

• Go-Back-N
  -> 파이프 라인에 N개까지 ACK을 받지 않은 패킷을 보낼 수 있음.
  -> Cumulative ack 사용(리시버는 중간에 비는 번호 없이 다 받았을 때만 ack을 보낼 수 있음. 순서대로 받다가 하나라도 안오면 그 이후로는 패킷 오더라도 ack 안보냄).
  -> 타이머 하나 사용(ack 못받은 패킷중 가장 오래된 패킷이 가지고 있음. Expire(time out) 되면 모든 패킷 재전송)
  -> 같이 보내진 패킷들을 한번에 관리해서 하나라도 안오면 ack 안보내니까 샌더에서 타임아웃 돼서 안온 패킷부터 재전송 하게 된다.
• selective repeat
  -> 안보내진 패킷만 재전송하자.
  -> Individual ack 사용(따로 관리해서 받은 패킷만 ack 보내고 못받은 패킷은 ack 안보내줘서 못받은 패킷만 재전송 할 수 있게).
  -> 각각의 패킷에 대한 타이머 사용.(ACK이 오면 타이머 끄고 expire 되면 그 패킷만 재전송 하면 됨)
  -> 타임아웃 된 패킷에 대해서만(ack 못받은 패킷) 재전송

Go-Back-N

Sender

• k-bit를 써서 패킷들을 seq num을 통해 구별한다.
• 필요한 parameter : send_base, window size, nextseqnum
  
  -> window size : n개까지 한번에 보낼수 있다라는 파라메터
  -> send_base : 전송할 수 있는 윈도우의 가장 앞의 패킷
  -> nextseqnum : 다음으로 보내질 패킷의 시퀀스 넘버
  -> 그림에서 앞에 노란색은 보냈지만 송신자로부터 아직 ack안온 것들
  -> 뒤에 파란색은 데이터가 없어서 보낼 수 있지만 아직 안보낸거.
  -> 맨 앞 초록색은 보내고 ack 받은거.
  -> 슬라이딩 윈도우 사용(사이즈는 유지하고 한칸씩 옆으로 이동)
• ACK(n) : n번까지 ACK을 다 받았다는 의미 -> cumulative ACK
  -> ack이 날아가서 못받더라도 패킷만 잘 전달 됐으면 그 다음 ack이 오면서 앞에꺼 까지 acknowledge 해 줄 수 있다. 이런식으로 누적ack 사용
  -> 예를들어 패킷 1,2,3,4 를 보내고 다 잘 전달 됐는데 2,3번 ACK이 날라간 경우 ACK(4)를 통해 앞에것들이 잘 왔다는 것을 알 수 있다.
  -> duplicate ack을 받을 수 있음
• oldes in-flight packet 에 대한 타이머
  -> in-flight = outstanding = set but not acked
  -> 아직 ack 못받은 애중 시퀀스 넘버가 가장 앞에 있는거
  -> 얘에 대해서 타이머를 가지고 있다 = 타이머를 하나만 가지고 있다.
• timeout(n) : n이라는 시퀀스 넘버에서 타임아웃이 걸렸으면 n부터 전부 다시 보냄

GBN: sender extended FSM

• 하나의 스테이트
  -> 이벤트에 따른 반응만 있다.
• 애플리케이션에서 데이터를 보내줬을 때
  -> 만약 nextseqnum이 base + N 보다 작으면(윈도우 안에 존재하는 경우) 패킷에 헤더 붙이고 네트워크 레이어로 보낸다.
  -> 이 과정을 진행 한 후 만약 base == nextseqnum 이면(in-flight packet이면) 타이머 시작
  -> nextseqnum++
  -> 만약 윈도우 안에 있는 애들이 다 보내진 경우라면 refuse(버퍼링)
• timeout 일 때
  -> 타이머를 다시 시작하고 베이스 부터 nextseqnum-1 까지 데이터를 다시 전부 재전송한다.
• 데이터를 받고 notcorrupt 일 때
  -> 베이스에 ack 넘버 + 1을 해준다.
  -> 예를 들어 현재 베이스가 5인데 ACK(6)이 오면 베이스를 7로 해준다.
  -> 만약 베이스가 nextseqnum이면 타이머 스탑, 아니면 타이머 0부터 재시작
• ack을 받았는데 corrupt일 때
  -> 아무 동작 안함

GBN: sender extended FSM

• 타임아웃이 걸리면 어차피 sender가 다 보내주기 때문에 기억할 필요가 없다
  -> 단순함
• Ack-only : 어떤 데이터가 오면 항상 ACK을 보내주는데 cumulative ack이기 때문에 in order(중간에 빵구 없이 순서대로 온것)중 시퀀스 넘버가 가장 큰거 보내준다.
  -> 예를들어서 3번 빵구면 expectedseqnum인 A2만 ack으로 보냄. 4번이 와도 2번 보냄. 그리고 2번 이후에 오는 패킷들은 걍 다 버림(discard)
  -> 샌더 입장에서 똑같은 번호를 가진 ack을 중복하여 받을 수 있다.
  -> expectedseqnum만 기억하면 된다.
• out-of-order packet
  -> 빵구 이후에 오는 패킷들(순서에 안맞게 온 애들 예를들어 123와야 하는데 132오는 패킷도 포함)은 버리고 버퍼링하는것도 없음.
  -> ack을 보내주긴 함.

• 초기 상태 : expectseqnum=1로 해 주고 그 번호로 ACK 만든다.
  -> 올것들이 제대로 온 상황 : 처리 잘 해주고 보내주고 expectseqnum++
  -> default(에러가 있다거나 패킷이 깨졌거나 원하는 번호가 아니거나 등) : 이전에 만들었던 패킷 보내줌
  -> 예를들어 현재 ACK(3)까지 만들어진 상황에 5번 패킷이 오면 ACK(3)을 보내줌. 만약 패킷이 깨져서 와도 ACK(3) 보내줌.

동작 과정

출처 및 참고
Computer Networking A Top-Down Approach 7-th Edition / Kurose, Ross / Pearson
서강대학교 기초컴퓨터네트워크 강의자료