=== principles of reliable data transfe ===

1. Principles of reliable data transfer

application layer 입장에서는 reliable 하게 보내줄거라고 생각한다.

하지만 실재로 Transport layer에서 unreliable한 것을 reliable하게 만들어야 한다.

transport layer의 input, output 측면에서 바라보자
rdt_send() 함수를 호출하여서 데이터를 전달하게 된다. sending side에서 조치를 취하고 udt_send() 가 network layer로 데이터를 전달하게 된다.

데이터가 오면 rdt_rcv() 가 처리하고 receiving side에서 데이터를 처리하고 deliver data는 reliable하게 데이터를 application layer 쪽으로 보내주면 된다.

unreliable channel이 어떤 characteristic을 가지고 있는지를 알고 있어서 프로토콜을(rdt = reliable data transfer protocol) 설계할 수 있다.

Reliable data transfer: getting started

• incrementally develop sender, receiver sides of reliable data
  transport protocol (rdt)
• consider only unidirectional data transfer
  • but control info will flow on both directions
• use finite state machines (FSM) to specify sender, receiver : sender과 receiver가 동작하는 방법을 FSM으로 설계할 것이다. FSM은 시스템의 동작을 설명하는 방식중에 하나이다. state와 event, action으로 설명하는 것이다.

state : 예를들어 sender의 FSM이라면 sender가 가질 수 있는 여러가지 state중 하나에 있게 되고 어떤 상황이 발생함에 따라서 다른 상태로 넘어갈 수 있는 state를 정의한다.

event causing state transition : event 발생
actions taken on state transition : action을 수행하고 state2로 이동

rdt 1.0: reliable transfer over a reliable channel

• underlying channel perfectly reliable : reliable한 channel위에 rdt를 만든다.

  • no bit errors
  • no loss of packets

• separate FSMs for sender, receiver

  • sender sends data into underlying channel
  • receiver reads data from underlying channel

• sender
  rdt_send(data)에 반응 -> 패킷을 만들고 아래 layer로 데이터 전송 : reliable하지 않음

• receiver
  rdt_rcv(packet)에 반응 -> extract 헤더를 떼어줌, application쪽으로 데이터 전송

가장 간단하게 reliable하지 않은 rdt

rdt 2.0: channel with bit errors

• underlying channel may flip bits in packets : 패킷에 에러가 있을 수 있는 경우
  • checksum to detect bit errors : checksum으로 bit에러를 검사
• how to recover from errors
  • acknowledgments (ACKs): receiver explicitly tells sender that
    packet received OK : ACK feedback은 sender가 receiver쪽으로 보내면 그것에 대한 응답을 sender로 보낸다.
  • negative acknowledgments (NAKs): receiver explicitly tells sender that packet had errors : 패킷에 에러가 있을때 응답하는 것
  • sender retransmits packet on receipt of NAK : NAK이 오면 재전송해줌
• new mechanisms in rdt 2.0 (beyond rdt 1.0) : error을 찾으면 버리고 재전송
  • error detection
  • feedback: control messages (ACK, NAK) from receiver to sender : feedback은 ACK, NAK이 존재한다.

rdt 2.0: FSM specification

• sender
  sender의 state가 2개가 되었다.
  ACK가 오면 원래의 state로 가고 NAK이 오면 state에 머물면서 계속 재전송한다.

• receiver
  receiver은 corrupt는 문제가 생기었기에 NAK을 보내준다. 그때는 state는 자기자신으로 돌아간다.
  제대로된 패킷이 왔다면 sender 쪽으로 ACK를 보낸다.
  

rdt 2.0: problem

• what happens if ACK/NAK is corrupted? : ACK, NAK에도 에러가 있을 수 있다는 문제점이 있다.
  • sender doesn't know what happened at receiver
  • can't just retransmit: possible duplicate
• handling duplicates
  • sender retransmits current packet if ACK/NAK corrupted : ACK/NAK이 깨졌으면 재전송해야 한다.
    
  • sender adds sequence number to each packet : 예를 들어서 ACK가 깨졌고 sender가 재전송하면 이게 그 다음 패킷인지 재전송 패킷인지 알 수 없다. 그래서 sequence number을 패킷에 붙인다.
    
  • receiver discards (doesn't deliver up) duplicate packets

rdt 2.1: sender, handles garbled ACK/NAKs

sequence number을 쓰면 4개의 state가 된다. 이떄 sequene number은 1bit만 써서 0 또는 1이 반복되도록 제작하자

왼쪽 위에서 패킷을 보낼떄 0번 sequence number을 붙이고 다음 state에서 대기한다. 그러면 ACK나 NAK가 왔을 것이다. 만약 패킷에 문제가 있거나 NAK이면 재전송해준다.

corrupt 하지도 않고 ACK 이면 sequence number 1을 붙인다.

그리고 이번에는 sequence number 1을 붙여 보내고 계속 반복한다.

rdt 2.1: receiver, handles garbled ACK/NAKs

왼쪽 state 에서 0번 state가 왔는지 확인하고 오른쪽 state에서 1번 state가 왔는지 확인한다.

rdt 2.1: discussion

• sender

  • sequence number added to packet
  • two sequence numbers (0, 1) will suffice : 우리가 sequence number을 2개만 쓰는게 가능한 이유가 stop-and-wait를 하기 때문이다.
  • must check if received ACK/NAK corrupted
  • twice as many states
    - state must "remember" whether "expected" packet should have seq 0 or 1
    

• receiver

  • must check if received packet is duplicate
    • state indicates whether 0 or 1 is expected packet sequence number

rdt 2.2: a NAK-free protocol

• same functionality as rdt 2.1, using ACKs only
• instead of NAK, receiver sends ACK for last packet received successfully : ACK만 쓰는 형태로 protocol을 바꾸어 보자. NAK을 보낼 상황에도 ACK를 보내는 것이다.
  • receiver must explicitly include sequence number of packet being ACKed : 구분을 하기 위해서 ACK에 sequence number을 추가해 준다.(ACK(0), ACK(1)과 같이)
• duplicate ACK at sender results in same action as NAK: retransmit
  current packet : 똑같은 sequence number에 대한 ACK이 duplicate ACK이라고 한다.
  

rdt 2.2: sender, receiver fragments

sender는 state가 원래 4개 였던것이 2개로 줄어들었다. 0을 보냈는데 1번이 들어오면 반복하고 0이 돌아오면 그 다음 패킷을 보낸다.

0번을 기다리고 있는데 1번이 온 경우 ACK1을 재전송한다.

rdt 3.0: channels with errors and loss

channel with error and lose는 패킷에 loss가 난 경우

라우터 버퍼에서 패킷을 버린 경우, sender가 패킷을 보냈는데 receiver가 오지 않은 경우

• new assumption
  • underlying channel can also lose packets (data, ACKs) : 패킷 lose가 있을 수 있다.
  • checksum, seq num, ACKs, retransmissions can help, but are not enough
• approach
  • sender waits "reasonable" amount of time for ACK : sender가 어느정도 ACK를 기다린다.
  • retransmits if no ACK received in this time : 시간이 지나도 ACK가 안오면 패킷을 재전송한다.
  • if packet (or ACK) just delayed (not lost) : 그냥 패킷이 느리게 간 경우
    • retransmission will be duplicate, but sequence numbers can handle this : 재전송이 duplicate가 발생할 수 있지만 sequence number 덕분에 중복되지 않는다.
    • receiver must specify sequence numbers of packets being ACKed
  • requires countdown timer

rdt 3.0: sender

0번을 붙여서 패킷을 보내고 타이머를 시작한다.

이때 receiver에 timeout이 되면 재전송하고 start_timer한다. 혹은 그냥 패킷에 어라가 있거나 ACK(1)이 왔다면 그냥 계속 time을 남기어 놓는다.

ACK이 제대로 왔으면 stop_numer하고 그 다음 상태로 넘어가고 이를 반복한다.

rdt 3.0: action

패킷 1번을 보내다가 loss가 발생한 경우 timeout이 걸리게 된다. 이떄는 패킷 1번을 다시 보낸다.

첫번째 경우는 ACK가 loss된 것이다. sender 쪽에서 timeout되면 패킷을 재전송한다.

두번쨰 경우는 보내기는 보냈는데 도착하기 전에 timeout이 걸린상황이다. sender 입장에서는 재전송을 했는데 재전송한거치고는 굉장히 빠르게 ACK가 온거다. 이 경우에는 수많은 duplicate가 생길 가능성이 크다.

그래서 이떄는 timeout을 얼마로 잡을지가 굉장히 중요한 이슈이다.

Performance of rdt 3.0

• rdt 3.0 is correct, but performance is bad : 3.0이 reliable하지만 속도가 느리다.

• e.g.: 1Gbps link, 15ms propagation delay, 8000 bit packet
  
  그러면 사실상 보내는데에는 15.008ms가 걸린다고 볼 수 있다. 왔다갔다하는데 30.008ms이다.

  • Usender: utilization – fraction of time sender busy sending : 효율성

    

  • if RTT = 30msec, 1KB packet every 30msec: 33kB/sec throughput over
    1Gbps link

• network protocol limits use of physical resource

이렇게 되는 이유는 결국 sender는 패킷을 받기까지 놀고 있기 때문이다.

rdt 3.0: stop-and-wait operation