Pipelined RDT Protocol.

• we have two hosts connected with a channel with transmission rate R = 1 Gbps (10⁹ bits per second)
• the RTT (round trip time) between the hosts is 30 milliseconds
• we are sending a packet of size L = 1000 byte (8000 bits)
• ACK packet is so small that we can neglect its transmission time

1. we start transmitting our packet at time t₀ = 0
2. transmission time of the packet is t_trans = L/R = 8 microseconds = 0.008 milliseconds
3. last bit of the packet is sent at time t_trans = 8 microseconds
4. since the packet trip time to the other host is 15 milliseconds, then the last bit of the packet is received at time t_rcv = RTT/2 + t_trans = 15.008
5. assume the receiving host immediately sends ACK. Since we decided to neglect the ACK transmission time the last bit of ACK will be received by the sender at time t_end = RTT/2 + t_rcv = 30.008

What can be done?

Solution: rather than operate in stop-and-wait mode, the sender is allowed to send multiple packets without waiting for ACK. This method is called pipelining.

Consequences:

• The range of sequence numbers must be increased.
• Both the sender and receiver sides may have to buffer more than one packet.
• Protocol needs a new strategy to deal with lost, corrupted, and overly delayed packets.

Go-back-N

• base -- the sequence number for the oldest unacknowledged packet
• nextseqnum -- the smallest unused sequence number
• window size N -- the max allowed amount of unacknowledged packets

Go-back-N sender has to respond to the following events:

• Invocation from above. When the protocol is called by the upper level (upper level is trying to send more data).
• Receipt an ACK. In our GBN protocol, an acknowledgment for a packet with sequence number n will be taken as a cumulative acknowledgment, indicating that all packets with sequence numbers less and equal to n have been successfully received.
• A timeout event. Yes, we again need to use timers to indicate loss of packets.

if( nextseqnum < base + N ){
  make packet[nextseqnum] (data, checksum, seq#=nextseqnum)
  send packet[nextseqnum]
  if( base == nextseqnum ){
    start timer
  }
  nextseqnum++
}
else{
  /* buffer is filled out with unACK'd packets */
  refuse the data
}

/* re-send all packets starting with the first unACK'd */
start timer
send packet[base]
send packet[base+1]
...
send packet[nextseqnum-1]

base = ACK_number + 1;
if( base == nextseqnum ){
  /* we have no ACK's to wait for */
  stop timer
}
else{
  start timer
}

Receiver. RDT v4.0 Go-back-N.

Initial conditions: expectedseqnum = 1 make ack packet (ACK, checksum, seq#=0) /* to ACK nothing */
Event	Action
received packet is not corrupted has seq# == expectedseqnum	extract data from the packet pass data to the upper level make ack packet (ACK, checksum, seq#=expectedseqnum) send ack packet expectedseqnum++
received a corrupted packet or packet seq# != expectedseqnum	send ack packet

See applet for Kurose-Ross book that illustrates how Go-back-N works.

Selective Repeat

• send_base -- the sequence number for the oldest unacknowledged packet
• nextseqnum -- the smallest unused sequence number
• window size N -- the max allowed amount of unacknowledged packets

1. Data received from above. When data received from above, then SR sender checks the next available sequence number for the packet. If the sequence number is within the sender's window, the data is packetized and sent; otherwise it's either buffered or returned to the upper layer for later transmission, as in GBN.
2. Timeout. Timers are again used to protect against lost packets. However, each packet must now have its own logical timer, since only a single packet will be transmitted on timeout.
3. ACK received. If an ACK is received, the SR sender marks that packet as having been ACK'd, provided it's in the window. If packet's sequence number is equal to send_base, the window base is moved forward to the unacknowledged packet with the smallest sequence number. If the window moves and there are untransmitted packets with sequence numbers that now fall within the window, these packets are transmitted.

Receiver Algorithm:

1. Packet with sequence number in [rcv_base, rcv_base+N-1] is correctly received. In this case, the received packet falls within the receiver window and a selective ACK packet is returned to the sender. If the packet was not previously received, it's buffered. If this packet has a sequence number equal to the base of the receiver window (rcv_base), then this packet and any previously buffered and consecutively numbered packets are delivered to the upper layer. The receiver window is then moved forward by the number of delivered packets.
2. Packet with sequence number in [rcv_base-N, rcv_base-1] is received. In this case, an ACK must be generated, even though this packet is a packet that the receiver has previously ACK'd.
3. Otherwise. Ignore the packet.