RDT(reliable data transfer)

  • Capabilities
    • Error detection
    • Receive feedback(ACK)
    • Retransmission(RDT based on retransmission is also called ARQ(automatically repeat request))

Stop-and-wait

Let’s build a reliable data transfer protocol! 🌟

  • RDT2.0 🌟

    • Sending process
      • Receive data from upper layer
      • Make a packet
      • Send the packet
      • Waiting
        • Receive ACK
          • Exit waiting
        • Receive NAK
          • Resend
          • Keep waiting
      • Next
    • Receiving process
      • Receive the packet
      • Checking
        • Corrupt
          • Send NAK
          • Exit checking
        • Not corrupt
          • Extract data
          • Deliver data to next layer
          • Send ACK
          • Exit checking
      • Next
    • Problems
      • Corrupt ACK/NAK
        • Error
        • Lost
    • 3 ways to solve the problems
      • Sender asking
        • Receiver have no idea whether it is a new packet or request for repeating
      • checksum
        • Not solving “lost” problem
      • Resending when NAK/corrupt ACK
        • Receiver have no idea sender have received ACK or not. Then it’s hard for receiver to find out the new packet is the previous one or the new one.
    • final method
      • Resending (3rd method)
      • SN(sequence number) for packets
      • 1-bit number(SN mod 2 can achieve)
      • Introduce RDT2.1

  • RDT2.1 🌟

    • Sender
      • Receive data from upper layer
      • Make a packet(+ SN mod 2)
      • Send the packet
      • Waiting
        • Receive ACK
          • Exit waiting
        • Receive NAK/corrupt packet
          • Resend
          • Keep waiting
      • Next (SN+1)
    • Receiver
      • Receive the packet
      • Checking
        • Waiting for 1(SN mod 2=1)
          • Corrupt
            • Send NAK
            • Keep waiting
          • Receive 0(duplicate one)
            • Send ACK
            • Keep waiting
          • Receive 1
            • Extract and deliver
            • Send ACK
            • Exit waiting
        • Waiting for 0(SN mod 2=0)
          • Corrupt
            • Send NAK
            • Keep waiting
          • Receive 1(duplicate one)
            • Send ACK
            • Keep waiting
          • Receive 0
            • Extract and deliver
            • Send ACK
            • Exit waiting
      • Next(waiting +1)

  • RDT2.2 🌟

    • What’s new
      • No more NAK
      • SN in ACK
    • Sender
      • Receive data from upper layer
      • Make a packet(+ SN mod 2)
      • Send the packet
      • Waiting
        • Waiting for ACK 0(having sent the packet(SN mod 2=0))
          • Receive ACK 0
            • Exit waiting
          • Receive ACK 1/corrupt ACK
            • Resend
            • Keep waiting
        • Waiting for ACK 1(having sent the packet(SN mod 2=1))
          • Receive ACK 1
            • Exit waiting
          • Receive ACK 0/corrupt ACK
            • Resend
            • Keep waiting
      • Next (SN+1)
    • Receiver
      • Receive the packet
      • Checking
        • Waiting for 1(SN mod 2=1)
          • Corrupt /Receive 0(duplicate one)
            • Send ACK 0
            • Keep waiting
          • Receive 1
            • Extract and deliver
            • Send ACK 1
            • Exit waiting
        • Waiting for 0(SN mod 2=0)
          • Corrupt /Receive 1(duplicate one)
            • Send ACK 1
            • Keep waiting
          • Receive 0
            • Extract and deliver
            • Send ACK 0
            • Exit waiting
      • Next(waiting +1)

  • RDT3.0(alternating-bit protocol) 🌟

    • What’s new
      • Deal with the lossy channel, which is common
      • Introduce cutdown timer
        • Start the timer for each packet
        • Timer interrupt
        • Stop the timer
    • Sender
      • Receive data from upper layer
      • Make a packet(+ SN mod 2)
      • Send the packet
      • Start the timer
      • Waiting
        • Waiting for ACK 0(having sent the packet(SN mod 2=0))
          • Receive ACK 0
            • Stop the timer
            • Exit waiting
          • Receive ACK 1/corrupt ACK
            • None
          • Timeout
            • Resend
            • Restart the timer
            • Keep waiting
        • Waiting for ACK 1(having sent the packet(SN mod 2=1))
          • Receive ACK 1
            • Stop the timer
            • Exit waiting
          • Receive ACK 0/corrupt ACK
            • None
          • Timeout
            • Resend
            • Restart the timer
            • Keep waiting
      • Next (SN+1)
    • Receiver
      • The same as RDT2.2
Screenshot 2023-10-31 at 21.58.58.png

A reliable data transfer protocol(3.0) has been created! 🌟

  • New problems
    • How to achieve high efficiency?
      • Pipelining
  • Consequences for RDT
    • Unique SN
    • Both sides have buffer
    • Error control
      • GBN
      • Selective repeat

GBN(Go-Back-N)

  • Base: The oldest unacknowledged packet
  • Nextseqnum: The next packet to be sent
  • Window size(N): used for flow control
  • SN issues: As the number of bits in header is fixed(eg. k, (32 bits)TCP), SN need do modular arithmetic(mod  2kmod\ \ 2^k)
  • w<2kw<2^k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//sender
base=1;
nextseqnum=1;
while(1){
  getData(data);//from upper layer
  if(nextseqnum<base+N){
    sndpkt[nextseqnum]=make_pkt(nextseqnum,data,checksum);
    send(sndpkt[nextseqnum]);
    if(base==nextseqnum)
    	start_timer;
    nextseqnum++;
  }
  else
    refuse_data(data);
  if(timeout){
    start_timer;
    send(sndpkt[base]);
    send(sndpkt[base+1]);
    ...
    send(sndpkt[nextseqnum-1]);
  }
  if(receive(rcvpkt)){
    if(notcorrupt(rcvpkt)){
      base=getacknum(rcvpkt)+1;
      if(base==nextseqnum)
     	stop_timer;
      else
     	start_timer;
    }
  }
}

//receiver
expectedseqnum=1;
sndpkt=make_pkt(0,ACK,checksum);
while(1){
  if(receive(rcvpkt)){
    if(notcorrupt(rcvpkt)&&hasseqnum(rcvpkt,expectedseqnum)){
      extract(rcvpkt,data);
      deliver_data(data);//deliver to next layer
      sndpkt=make_pkt(expectedseqnum,ACK,checksum);
      send(sndpkt);
      expectedseqnum++;
    }else{
      send(sndpkt);
    }
  }
}
  • Why discard all packets after the unacknowledged one?
    • Sender will resend, so they will not be lost
    • Simplify the receiver buffer
  • Why w<2k=mw<2^k=m

    • w>2k=mw>2^k=m

      • It’s obvious that there must be mixing the previous one with the new one

    • w=2k=mw=2^k=m

SR(selective repeat)

  • What’s new
    • Compare to GBN
      • Solving the problem that when a large number of packets are in the channel, GBN becomes time-consuming
    • Avoid unnecessary retransmissions
Screenshot 2023-11-01 at 10.18.10.png
  • Sender
    • Receive data from upper layer
      • The same as GBN
    • Timeout
      • Now each packet has its own logical timer
      • Only send the one packet when its timer expires
    • ACK received
      • The same as GBN
  • Receiver
    • Packets with SN in rcv window(rcv_base ~ rcd_base+N-1) is correctly received
      • Not received previously
        • buffered
      • SN == rcv_base
        • Rcv_base one and all previously buffered & consecutively numbered packets are all passed to the next layer
        • Window moves forward by the number of packets delivered
        • Send ACK
    • Packets with SN in [rcv_base-N, rcv_base-1] –ensure the window of send slides
      • Send ACK
      • Not buffered
    • Other packets
      • Ignore them
  • SR delima with too-large window size
Screenshot 2023-11-01 at 11.19.10.png

🌟 How to solve

  • 2k−1⩾w2^{k-1}\geqslant w
    • equivalent to m⩾2wm\geqslant 2w
    • w is the window size
    • Why?
      • We must make sure the sum of w of both sides less than or equal to 2k2^k, then all previous ones with SN can be distinguished. We cannot recognize a previous one as a new one

We have built amazing RDT protocols! Now, let’s see what’s new in RDT of TCP.

RDT in TCP

  • Point 1: Practically, timer requires considerable overhead
    • Try to follow one-timer retransmission
  • Point 2: Use cumulative acknowledgements
    • The acknowledgment number that receiver puts in its segment is the sequence number of the next byte receiver is expecting from sender.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*Not C just pseudocode*/
/* Assume sender is not constrained by TCP flow or congestion control, that data from above is less
than MSS in size, and that data transfer is in one direction only. */
NextSeqNum=InitialSeqNumber
SendBase=InitialSeqNumber
loop (forever) {
  switch(event)
    event: data received from application above
      create TCP segment with sequence number NextSeqNum
      if (timer currently not running)
        start timer
      pass segment to IP
      NextSeqNum=NextSeqNum+length(data)
      break;
    event: timer timeout
      retransmit not-yet-acknowledged segment with smallest sequence number
      start timer
      break;
    event: ACK received, with ACK field value of y
      if (y > SendBase) {
        SendBase=y
        if (there are currently any not-yet-acknowledged segments)
          start timer
      }
    break;
} /* end of loop forever */
  • 3 scenarios to learn RDT in TCP visually

​ Screenshot 2023-11-01 at 19.33.09.png

Screenshot 2023-11-01 at 19.33.20.png

​ Screenshot 2023-11-01 at 19.33.36.png

  • Fast retransmission
    • If the TCP sender receives three duplicate ACKs for the same data, it takes this as an indication that the segment following the segment that has been ACKed three times has been lost
    • Retransmitting the missing segment before that segment’s timer expires
  • How to classify RDT in TCP
    • A hybrid of GBN and SR protocols

Here is a Leaning Note.

Most of the content references “Computer Network A Top-Down Approach(James Kurose, Keith Ross)”