P3 Sliding Window

P3 implements a sliding window, which is used to control the flow of packets. This page documents how the P3 sliding window is implemented in the America Online clients.

Note

I would like to personally thank Randell Jesup, the person who invented the P3 protocol for his guidance, and explanations about some of the finer points of P3 internals.

Sliding Window Overview

Technically, a sliding window is a strategy used to control the flow of packets between two P3 endpoints. The basic idea behind sliding windows is to use a range of sequence numbers that determine when packets can be transmitted. The sliding part of a sliding window, is the idea that the range itself shifts as packets are acknowledged and new ones are sent.

Example

Before looking at how sliding windows are implemented in P3, let's take a look at a generic example. Assume we have a 3-bit sequence number with a maximum window size of 4. This means that (for this example) the valid sequence numbers are 0 through 8 inclusive.

Initially there are no packets in the window.

┌─┬─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
└─┴─┴─┴─┴─┴─┴─┴─┘

After the first DATA packet is transmitted using seqence number 0 the window has one packet.

Client: DATA (tx_seq = 0)

┌─┐              
├─┼─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
├─┼─┴─┴─┴─┴─┴─┴─┘
└─┘              

The next DATA packet transmitted has the sequence number 1 and the window now has two packets.

Client: DATA (tx_seq = 1)
┌───┐            
├─┬─┼─┬─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
├─┴─┼─┴─┴─┴─┴─┴─┘
└───┘            

Assume the client continues transmitting, and sends two more DATA packets with the sequence numbers 2 and 3.

Client: DATA (tx_seq = 2)
┌─────┐          
├─┬─┬─┼─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
├─┴─┴─┼─┴─┴─┴─┴─┘
└─────┘          

Client: DATA (tx_seq = 3)
┌───────┐        
├─┬─┬─┬─┼─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
├─┴─┴─┴─┼─┴─┴─┴─┘
└───────┘        

At this point, the sliding window has reached it's maximum size (4 in our example). That is, the window is full. At this point the client can no longer transmit any DATA packets until the host acknowledges the sent packets. This is how a sliding window controls the flow of packets.

At some later point the host acknowledges the first packet sent by the client (the one with sequence number 0).

Host: ACK (rx_seq = 0)
  ┌─────┐        
┌─┼─┬─┬─┼─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
└─┼─┴─┴─┼─┴─┴─┴─┘
  └─────┘        

The window has shrunk slightly, and now contains three unacknowledged packets. Technically the client could send another DATA packet, but we will assume instead the host sends another acknowledgement of sequence number 1.

Host: ACK (rx_seq = 1)
    ┌───┐        
┌─┬─┼─┬─┼─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│
└─┴─┼─┴─┼─┴─┴─┴─┘
    └───┘        

The window size is now 2 since the client transmitted four DATA packets, and the host acknowledged two packets.

Since the window is available, the client can now transmit additional DATA packets. For example if the client transmitted a single DATA packet with the sequence number 4, the window would look like:

Client: DATA (tx_seq = 4)
    ┌─────┐      
┌─┬─┼─┬─┬─┼─┬─┬─┐
│0│1│2│3│4│5│6│7│
└─┴─┼─┴─┴─┼─┴─┴─┘
    └─────┘      

Notice how the window moves along from left to right? That's the "sliding" part of a sliding window.

Boundary Crossing

A point worth considering is what happens when sequence numbers run out? To continue the example, assume that the window currently has two packets, for sequence numbers 6 and 7. Since the maximum size of the window in this example is 4, the client is allowed to transmit DATA packets. However, what should the sequence numbers be, and what will the window look like?

Client: DATA (tx_seq = ???)
            ┌───┐                
┌─┬─┬─┬─┬─┬─┼─┬─┤                
│0│1│2│3│4│5│6│7│  ???           
└─┴─┴─┴─┴─┴─┼─┴─┤                
            └───┘                

The answer is actually simple. Just wrap around and start the sequence numbers over again. Thus the sequence number of the next transmitted packet will be 0.

Client: DATA (tx_seq = 0)
            ┌─────┐              
┌─┬─┬─┬─┬─┬─┼─┬─┬─┼─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│0│1│2│3│4│5│6│7│ ...
└─┴─┴─┴─┴─┴─┼─┴─┴─┼─┴─┴─┴─┴─┴─┴─┘
            └─────┘              

Sliding Window Implementation

This section discusses details of how a sliding window is implemented by the P3 handler portion of the client.

Sender Window

The P3 handler implements a sliding window for sending packets. That is, the window controls the packets being sent, not the packets being received. While it is generally possible to have one sliding window for sending, and another one for receiving, P3 does not do this.

The tx_seq Field

The tx_seq field refers to a packet's sequence number. It is incremented by 1 for each DATA packet that is transmitted. The other packet types (called control or "unnumbered" packets) do not increment the tx_seq value. Instead they reuse the value of the last tx_seq that was sent.

The rx_seq Field

The rx_seq field contains the acknowledgement information. It is used to acknowledge all correctly received packets up to and including the one described by the rx_seq field. This is called an implicit acknowledgement.

For example, assume the client transmits four DATA packets to the host starting with 0x11 as the first tx_seq value. For each transmitted packet the window size grows by one.

sequenceDiagram
    participant Client
    participant Host

    Client ->> Host: DATA, tx_seq = 0x11, rx_seq = 0x20
    Note over Client: Window = {0x11}

    Client ->> Host: DATA, tx_seq = 0x12, rx_seq = 0x20
    Note over Client: Window = {0x11, 0x12}

    Client ->> Host: DATA, tx_seq = 0x13, rx_seq = 0x20
    Note over Client: Window = {0x11, 0x12, 0x13}

    Client ->> Host: DATA, tx_seq = 0x14, rx_seq = 0x20
    Note over Client: Window = {0x11, 0x12, 0x13, 0x14}

At this point assume the host sends an ACK packet with the rx_seq field set to 0x13. This acknowledges the correct receipt of packets 0x11, 0x12, and 0x13. The client's window has now shrunk to only containing the reference to the packet with tx_seq value 0x14.

sequenceDiagram
    participant Client
    participant Host

    Host ->> Client: ACK, tx_seq = 0x20, rx_seq = 0x13
    Note over Client: Window = {0x14}

Window Parameters

Since the tx_seq and rx_seq fields are one byte each, the theoretical range of values is 0 to 0xFF (0 - 255). However in practice the range of values used is 0x10 to 0x7F. The client uses the value 0x7F as the initial value for both the tx_seq and rx_seq fields.

The maximum size of client's window is 0x10 (16 decimal). In practice the window rarely gets this full due to preemptive acknowledgments.

Transmitting Acknowledgements

The ACK packet type is one way to convey acknowledgement information. However since every P3 packet contains an rx_seq field, any packet type excluding INIT can be used to transmit acknowledgement information. In effect rather than wasting bandwidth by sending separate ACK packets, the acknowledgement information can be sent in the next outbound packet. This is called piggybacking.

In practice, because of the high volume of data transmitted back and forth, you typically see acknowledgement information in DATA packets (though for example it could also come in the form of a NAK packet.)

Timeouts

P3 uses a mechanism called heartbeats to handle packet timeouts. Despite the name, it is not a mechanism to keep the connection alive. Instead heartbeats are used for eliciting acknowledgement information from the other side after a timeout period. This timeout period has been observed to be 12 seconds.

If an INIT packet has been unacknowledged, the client retransmits the packet INIT packet. Graphically it looks like:

sequenceDiagram
    participant Client
    participant Host

    Client ->> Host: INIT, tx_seq = 0x7F, rx_seq = 0x7F
    Note over Client,Host: 12 seconds later

    Client ->> Host: INIT, tx_seq = 0x7F, rx_seq = 0x7F

However if a DATA packet has been unknowledged, the sender transmits a HEARTBEAT packet. The receiver of the HEARTBEAT then transmits an ACK packet in response.

sequenceDiagram
    participant Client
    participant Host

    Client ->> Host: DATA, tx_seq = 0x10, rx_seq = 0x7F
    Note over Client,Host: 12 seconds later

    Client ->> Host: HEARTBEAT, tx_seq = 0x10, rx_seq = 0x7F
    Host ->> Client: ACK, tx_seq = 0x7F, rx_seq = 0x10

The client will attempt to transmit timed-out packets (INIT or DATA) up to 10 times. After that it disconnects and presents the user with an error message.

Preemptive Acknowledgement

Sliding windows can run into a delay-related problem when transmitting enough data to fill up the sliding window. For example, assume the client needs to transmit 20 packets worth of data, and all of the packets must be received before the host can process the incoming data.

Graphically, the situation looks like:

sequenceDiagram
    participant Client
    participant Host

    Client ->> Host: DATA, tx_seq = 0x20, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x21, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x22, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x23, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x24, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x25, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x26, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x27, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x28, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x29, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2A, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2B, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2C, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2D, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2E, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2F, rx_seq = 0x55

    Note over Client,Host: Sender window full
    Note over Client: Data still pending
    Note over Host: Needs pending data to continue

At this point, unless there is traffic from the host, P3 will pause sending until a timeout occurs (12 seconds in practice) and then send a HEARTBEAT, which will elicit an ACK and close the window.

To avoid this delay, P3 implements a preemptive acknowledgement. A preemptive acknowledgement is when a receiver sends an ACK packet after it has received a specific number of unacknowledged DATA packets. In practice, the preemptive acknowledgement threshold has been observed to be 8.

This means if the receiving side of a P3 connection receives 8 DATA packets, and has not yet acknowledged them it sends an ACK packet. This looks like:

sequenceDiagram
    participant Client
    participant Host

    Client ->> Host: DATA, tx_seq = 0x20, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x21, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x22, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x23, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x24, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x25, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x26, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x27, rx_seq = 0x55
    Host ->> Client: ACK, tx_seq = 0x55, rx_seq = 0x27
    Note over Client: Window is now empty
    Client ->> Host: DATA, tx_seq = 0x28, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x29, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2A, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2B, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2C, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2D, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2E, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x2F, rx_seq = 0x55
    Host ->> Client: ACK, tx_seq = 0x55, rx_seq = 0x2F
    Note over Client: Window is now empty
    Client ->> Host: DATA, tx_seq = 0x30, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x31, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x32, rx_seq = 0x55
    Client ->> Host: DATA, tx_seq = 0x33, rx_seq = 0x55