TCP Sliding Window

• the purpose of the Sliding Window is not flow control; it is to keep track of bytes/packets sent, received, ACKd, written, read, expected,…on the sender and the receiver
• uses the concept of pipelining: sending a bunch of segments without waiting for ACKs → improved performance
• the Sliding window protocol improves on the Stop-and-Wait protocol
• Window size is the number of bytes (or packets) that can be sent or received
• Window size is advertised with the SYN segment
• a sender maintains three variables:
  • SWS: number of segments the sender can send without waiting for ACK → the allowed number of unacknowledged segments to be sent
  • LAR
  • LSS

• the receiver maintains these variables
  • RWS: number of out-of-order segments that it can receive before sending an ACK
  • LAS: the sequence number of the Last Acceptable Segment
  • LSR: the sequence number of the Last Segment Received

• The sender makes sure this invariant is true: LSS – LAR <= SWS
• the receiver makes sure this invariant is true: LAS – LSR <= RWS
• Any time a host sends packets, it holds a SWS. Any time it has to receive data, it holds a RWS → since TCP is a full duplex protocol, each host maintains both SWS and RWS.
• in terms of bytes:
  • the receiver can not buffer data that is more than ACK Seq Num + RWS
  • the sender must not send data more than ACK Seq Num + RWS
• principle:
  • Sender side:
    • when a higher ACK is received:
      • the LAR pointer advances one slot
      • the window advances one slot, which means we can send one more segment
      • when the sender keeps receiving the same ACK, it means that one segment is lost. It must retransmit it and get an ACK for it before sliding the window.

• Receiver side:
  • when a segment is received:
    • if seqnum <= LSR or seqnum > LAS, then the segment is discarded
    • otherwise it is accepted
    • if ACK is lost and ACK+1 is sent, then there is no need to send ACK, because ACK+1 acknowledges data up to ACK→ concept of TCP Cumulative ACKs
• if a RTT = x ms, then the number of possible RTTs per one second is (1000/x)
• SWS <= SendBuffer
• RWS <= RcvBuffer
• Advertized Window = the amount of bytes that the sender can send. This value is advertized by the receiver in the TCP header (Window field). This is also called RecvWindow.

Figure: The place of the Window field, in the TCP header

• maxRcvBuffer – (LastByteRcvd – LastByteRead)    = Advertized Window
•  Effective Window: how many bytes the sender can still send to a particular receiver. This value is relative to the Advertized Window.
• • Effective Window = Advertized Window – (LastByteSent – LastByteAckd)
•  LastByteWritten – LastByteAcked <= maxSendBuffer
• Bytes to know:
  • at the sender side: LastByteAckd < LastByteSent < LastByteWritten
  • at the receiver side: LastByteRead < NextExpectedByte < LastByteRecvd

Figure: Important bytes to know, from the sender side and the receiver side, in a TCP connection

• the number of segments a sender can send is limited by two factors:
  • SWS
  • MSS
• The window size is variable in time
• The Sequence Number Space is the group of all the possible sequence numbers of bytes sent to a receiver. The sequence number space must be at least equal to SWS+RWS sequence numbers
• if RWS == 1, then we talk about “Go-back-N” protocol. To illustrate the process of the Go back N protocol, let’s assume:
  • SWS = 3
  • Host A sends segments 1, 2, 3
  • segment 2 is lost
  • Since RWS ==1, then only one segment is allowed in the RecvBuffer, and host B can not buffer segment 3. So host B sends ACK2, ACK2, ACK2. At that time, host A times out segment 2 and resends it. Once received, host B sends ACK3 and host A resends segment 3.

References

TCP Congestion Control, Vern Paxon.