Stream

Introduction

This document defines a streaming protocol built on top of UDP that provides reliable in-order packet delivery semantics.

Concepts

Connection ID

An identifier that is used to identify a connection. Each endpoint supplies a connection id that is to be used by the other end for sending packets.

Connection

A connection is identified by a pair of connection ids supplied by both ends. Connections ids are exchanged as part of the 3-way handshake while establishing the connection.

Stream

A bidirectional channel of ordered (potentially infinite) bytes within a connection. A single connection can carry multiple simultaneous streams which can be created by either end of the connection.

Operation

Connection establishment

A connection is established by performing a 3-way handshake that exchanges connection ids.

The usual handshake proceeds as follows with one endpoint as a dialer and other as a listener:

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
DIALER                                               LISTENER
-------------------------------------------------------------
STATE: LISTEN                                   STATE: LISTEN
-------------------------------------------------------------
DIAL
src_conn_id: x ---------------------------->
-------------------------------------------------------------
State: DIAL_SENT                             State: DIAL_RECV
-------------------------------------------------------------
                                                    DIAL_CONF
                                               src_conn_id: y
                <---------------------------   dst_conn_id: x
-------------------------------------------------------------
State: ESTABLISHED                           State: DIAL_RECV
-------------------------------------------------------------
CONF
src_conn_id: x
dst_conn_id: y --------------------------->
-------------------------------------------------------------
State: ESTABLISHED                         State: ESTABLISHED
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

On rare occasions, it is possible that both ends of the connection initiate the handshake at the same time. In this case, the handshake proceeds as follows with both endpoints as dialers:

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
DIALER                                                 DIALER
-------------------------------------------------------------
STATE: LISTEN                                   STATE: LISTEN
-------------------------------------------------------------
DIAL
src_conn_id: x ---------------------------->
                                                         DIAL
                <---------------------------   src_conn_id: y
-------------------------------------------------------------
State: DIAL_RECV                             State: DIAL_RECV
-------------------------------------------------------------
DIALCONF
src_conn_id: x
dst_conn_id: y --------------------------->
                                                     DIALCONF
                                               src_conn_id: y
                <---------------------------   dst_conn_id: x
-------------------------------------------------------------
State: ESTABLISHED                         State: ESTABLISHED
-------------------------------------------------------------
CONF
src_conn_id: x
dst_conn_id: y --------------------------->
                                                         CONF
                                               src_conn_id: y
                <---------------------------   dst_conn_id: x
-------------------------------------------------------------
State: ESTABLISHED                         State: ESTABLISHED
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Sending data

Data is broken up into fragments and is sent in a DATA packet on a particular stream. Apart from the actual data, each packet contains a unique monotonically increasing packet number, the offset of the first byte in the stream and the length of the data. Data previously marked as lost is given priority and is sent before new data.

The sender keeps track of sent packets. Once the sender is done sending packets, he can indicate the end of a stream by sending a DATA+FIN packet as the final data packet.

Congestion control

The sender limits the total bytes in flight by defining a congestion window that increases slowly as more and more packets get acked.

Initially the connection starts off in the slow start stage where the congestion window increases exponentially. On the first congestion event, the connection switches to congestion avoidance with a sublinear growth in congestion window.

Packet pacing

The sender also limits the sending rate even if the congestion window is not full. This helps to smooth out the traffic and prevent packet loss due to burst traffic from affecting overall connection throughput (goodput).

Handling ACKs

On receiving ACK packets, the sender marks the packet numbers contained within as acked. The connection then performs loss detection where packets that were sent at least 50ms before the largest packet acked are marked as lost. In case of a lost packet, the connection emits a congestion event and halves the congestion window.

Tail loss detection

The sender sets a tail loss detection timer that is reset every time an ACK is received. If the timer ever fires, it means that an ACK has not been received in a long time indicating that the receiver is waiting for us to send new data. All packets in flight are marked as lost, a new congestion event is triggered and the lost data is sent again.

Receiving data

Buffering

The Stream protocol provides in-order packet delivery semantics. In order to fulfil this, the receiver maintains a application read offset. The receiver checks if the received data packet can be read immediately by the application. If not, he puts the packet in a buffer in order of their packet number to be read later.

Sending ACKs

The receiver periodically sends ACK packets containing all received packets to notify the sender about the packets he has received. The ACK packet supports TCP SACK style acknowledgement ranges to efficiently ACK a large number of packets at once.

Wire format

Every message is prefixed with a version byte and a message type byte. The message type identifies the message and the version field enables protocol upgrades in the future. Following this are the two connection ids followed by the payload.

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|     Version    |      Type     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
-----------------------------------------------------------------
|                             Payload                         ...
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

DATA (0x00)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x00     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
-----------------------------------------------------------------
|            Stream ID           |
-----------------------------------------------------------------
|                                                               |
---                        Packet Number                      ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                            Offset                         ---
|                                                               |
-----------------------------------------------------------------
|              Length            |
-----------------------------------------------------------------
|                               Data                         ...
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

DATA+FIN (0x01)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x01     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
-----------------------------------------------------------------
|            Stream ID           |
-----------------------------------------------------------------
|                                                               |
---                        Packet Number                      ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                            Offset                         ---
|                                                               |
-----------------------------------------------------------------
|              Length            |
-----------------------------------------------------------------
|                               Data                         ...
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

ACK (0x02)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x02     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
-----------------------------------------------------------------
|          Num Ranges (N)        |
-----------------------------------------------------------------
|                                                               |
---                        Largest Acked                      ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                        Ack Range (1)                      ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                           Gap (2)                         ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                        Ack Range (3)                      ---
|                                                               |
-----------------------------------------------------------------
|                                                               |
---                           Gap (4)                         ---
|                                                               |
-----------------------------------------------------------------
|                              ...                              |
-----------------------------------------------------------------
|                                                               |
---                        Ack Range (N)                      ---
|                                                               |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

DIAL (0x03)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x03     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                            0x00000000                         |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

DIALCONF (0x04)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x04     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

CONF (0x05)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x05     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

RST (0x06)

 0               1               2               3
 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|       0x00     |      0x06     |
-----------------------------------------------------------------
|                        Src Connection ID                      |
-----------------------------------------------------------------
|                        Dst Connection ID                      |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++