RDT

RDT

• Reliable Data Trasfer Protocol
• Sender는 receiver의, receiver는 sender의 fsm state를 모른다.

Interfaces of RDT

rdt_send()

• called from above
• Passed data deleiver to receiver upper layer

udt_sent()

• called by rdt to transfer packet over unreliable channel to receiver

rdt_rcv()

• called when packet arrives on receiver

deliver_data()

• called by rdt to deliver data to upper layer

RDT 1.0

• 매우 단순
• unreiliable channel 이 perfect 하다 가정
  • NO LOSS
  • No bit error
• sender, receiver를 위한 각각 한개의 FSM 존재

Sender

• rdt_send(data) → udt_send(packet)

Receiver

• rdt_rcv → deliver_data

RDT 2.0

• Bit error 가 발생한다면?
  • Use checksum to detect
  • ACK, NAK to tell sender packet is OK or NOT
  • Sender retransmit on receiept of NAK
• Stop And Wait
  • 패킷 보내고, 수신자의 반응을 기다림

Sender

• FSM 에 두개의 state 존재
  • 보내기를 기다리는 상태
    • 데이터에 checksum을 합해 패킷을 만들고
    • 이를 보낸다
  • Receiver 의 response를 기다리는 상태
    • ACK 를 받은 경우 위 상태로 전이
    • NAK를 받은 경우 패킷을 다시 보내고 상태 유지

Receiver

• 하나의 state
• checksum과 데이터를 보고 corrupt 여부 판단
  • Not Corrupt
    • deliver_data
    • udt_send(ACK)
  • Corrupt
    • udt_send(NAK)

RDT 2.1

• RDT 2.0은 ACK / NAK corrupt 되는 경우 receiver에 무슨일이 일어났는지 알 수 없다.
  • 이때 단순 retransmit 하는 경우 duplicate가 발생
• Duplicate handling위해
  • Sender는 Sequence number를 packet에 추가
    • Seq # 는 2개 (0, 1 )이면 충분하다.
  • Receiver는 duplicate packet 무시
    • Receiver는 sender에게 본인이 보낸 ACK / NAK가 sender에게 제대로 도착하였는지 모름

Sender

• 4개의 state 존재
  • seq 0 packet의 전송을 기다리는 상태
  • seq 0 packet 전송 후에 ACK나 NAK 를 기다리는 상태
    • 응답이 Corrupted 되거나 Nak면 다시 보냄
    • 응답이 ACK 인 경우 seq 1 패킷의 전송을 기다리는 상태로 전이
  • 1번 packet 에도 동일

Receiver

• 2개의 상태 존재
  • seq 0번을 기다리는 중
    • 받았는데 not corrupt이고 seq 0번을 받은 경우
      • deliver_data
      • udt_send(ACK, checksum)
    • 받았는데, corrupt인 경우
      • NAK 보냄
    • 받았고, not corrupt인데 seq1을 받은 경우
      • ACK를 보냄
        • sender의 state가 변하고, seq0을 보내도록 하기 위함
  • seq 1번을 기다리는 중
    • 위와 유사

RDT 2.2

• RDT 2.1과 같은데 NAK없이 ACK만 사용해서 구현해보자.
• Receiver는 ACK에 SEQ Number를 붙혀서 보낸다.
  • 동일 seq ACK의 반복전송은 이전 2.1 version의 NAK 과 동일하게 동작하게 하자.

Sender

• 4개의 state
  • seq 0 ACK 을 기다리는 상태에서
    • corrupt되거나 ACK 1을 받은 경우
      • 재전송
    • corrupt되지 않고, ACK 0 을 받은 경우
      • Seq 1 packet 전송을 기다리는 상태로 전이
  • seq 1 ACK을 기다리는 상태에서
    • 위와 유사
  • seq 0 packet 전송을 기다리는 상태
    • 2.1과 동일
  • seq 1 packet 전송을 기다리는 상태
    • 2.1과 동일

Receiver

• seq 0 packet 기다리는데
  • corrupt거나 seq 1 도착할 때
    • ACK 1 전송
  • 잘 왔을 때
    • ACK 0 전송, deliver data

RDT 3.0

• Sender는 ACK를 무한정 기다려줄 수는 없다.
  • 제 시간에 ACK가 안오면 재전송
  • 만약 ACK가 그냥 늦은거였다면?
    • duplicated, but seq # handles it
    • receiver specify seq # of packet ACKed
  • Use countdown timer

Sender

• ACK대기시에 잘못된 response가 오면 하던 일을 timeout때 수행한다.
• 잘못된 response가 오는 경우에는 아무것도 안한다.
• 4개의 state
  • seq 0 전송 대기
    • packet을 보내며 timer를 시작한다.
  • seq 0 ACK 대기
    • ACK가 제대로 온 경우
      • Stop timer
    • 뭐가 왔는데 corrupt거나 seq 1의 ACK인 경우
      • 아무것도 안함
    • timout
      • udt_send(sndpkt)
      • starttimer

Receiver

RDT 2.2와 동일

RDT 3.0 in action

 

Performance of RDT 3.0

• U_sender : utilization - fraction of time sender busy sending
• 1Gbps link, 15 ms prop. delay , 8000 bit 가정

When not using RDT 3.0

• time to transmit = L/R = 8000 / (10^9/sec) = 8 microsec

when using RDT 3.0 : stop & wait operation

• U_sender = (L / R) / ( RTT + (L / R)) = 0.008 / (30.008) = 0.00027
• 성능이 너무 안좋다.
  • RTT가 너무 길어 utilization이 낮음
  •  

    

RDT 3.0 with Pipelining

• 3 packet pipelining 수행 시 utilization이 3배가 됨

• 

Go-Back-N (GBN)

Sender

• window : 연속적으로 unACKed인 packet들의 모임
• Cumulative ACK : seq # 까지 모두 ACK 처리
  • ACK(n) 받으면 window 시작은 n+1 되도록
• timer 존재
  • oldest in flight packet에 대한 timer
  • timeout(n) 이면 window 안에 n 이상의 seq # packet 전부 재전송

 

Receiver

• ACK 만 전송, 지금까지 제대로 받았고, 순서가 맞게 이어진 패킷들 중 가장 높은 seq #로 ACK
  • 중복 ACK 발생 가능
  • rcv_base만 기억하면 됨
• Out of order packet이면?
  • 버리거나, buffer에 넣거나 구현에 따라 선택
  • 순서 맞게 잘 이어진 패킷들 중 가장 높은 seq# reACK

GBN In Action

Selective Repeat (SR)

• Receiver individually ack all correctly received packets
• Senders timeout, retransmit individualy for unACKed packet
  • maintain timer for each unACKed packet
• Sender window
  • N consecutive seq #s
  • limit seq #s of sent, unACKed packets
• Window size constraint
  • window size ≤ (# seq number) / 2

Sender

• data from above
  • if next available seq # in window
    • send packet
• timeout(n)
  • resend packet n
  • restart timer
• ACK(n) in [sendbase, sendbase+N]
  • mark packet n as received
  • if n is smallest unACKed packet
    • window base to next unACKed seq #

Receiver

• packet n in [rcvbase, rcvbase + N-1]
  • send ACK(n)
  • out of order
    • buffer
  • in order
    • deliver
    • window base to next not-yet-received packet
• packet in [rcvbase-N,rcvbase-1]
  • ACK(n)
• else
  • ignore

SR in Action

SR dilema

• when seq # are 0,1,2,3
• window size = 3
• ACK 몇개가 날라가면 순서가 꼬이는 문제가 발생할 수 있다.

• ⇒ win size ≤ (# seq num) / 2 will fix this

 

Ref

• Computer Networking: A Top-Down Approach (6th Edition)