Multipath Extension for QUIC

4.1. Path Identifier and Connection ID

Endpoints need a Path Identifier for each different path which is used to track states of packets. Endpoints use Connection IDs in 1-RTT packet header as Path Identifier in each directions, and use the sequence number of Connection IDs in MP frames to identify the path referred.¶

Following [QUIC-TRANSPORT], Each endpoint uses NEW_CONNECTION_ID frames to claim usable connections IDs for itself. Before an endpoint add a new path, it SHOULD check whether there is at least one unused available Connection ID for each side.¶

Endpoints can find which path a received packet belongs to according to the Destination Connection ID of the 1-RTT packet. Endpoints can find the context of a path by its' Connection ID or the Sequence number of Connection ID.¶

4.2. Path Packet Number Spaces

For the convenience of packet loss detection and recovery, endpoints use a different packet number space for each Path Identifier (Connection ID). MP_ACK frame includes the sequence number of the Destination Connection ID of the acknowledged packets as the Path Identifier.¶

4.3. Path Initiation

Figure 1 illustrates an example of new path establishment.¶

   Client                                                  Server

   (Exchanges start on default path)
   1-RTT[]: NEW_CONNECTION_ID[C1, Seq=1] -->
                         <-- 1-RTT[]: NEW_CONNECTION_ID[S1, Seq=1]
                         <-- 1-RTT[]: NEW_CONNECTION_ID[S2, Seq=2]
   ...
   (starts new path)
   1-RTT[0]: DCID=S2, PATH_CHALLENGE[X] -->
                     Checks AEAD using nonce(CID sequence 2, PN 0)
       <-- 1-RTT[0]: DCID=C1, PATH_RESPONSE[X], PATH_CHALLENGE[Y],
                                                MP_ACK[Seq=1,PN=0]
   Checks AEAD using nonce(CID sequence 1, PN 0)
   1-RTT[1]: DCID=S2, PATH_RESPONSE[Y],
             MP_ACK[Seq=1, PN=0], ... -->

As shown in Figure 1, client provides one unused available Connection ID (C1 with sequence number 1), and server provides two available Connection IDs (S1 with sequence number 1, and S2 with sequence number 2). When client wants to start a new path, it checks whether there is unused available Connection IDs for each side, and choose an available Connection ID S2 as the Destination Connection ID in the new path.¶

Endpoints need to exchange unused available Connection IDs with the NEW_CONNECTION_ID frame before an endpoint starts a new path. For example, if the goal is to maintain 2 paths, each endpoint should provide at least 3 CID to its peer: 2 in use, and one spare. If the client has used all the allocated CID, it is supposed to retire those that are not used anymore, and the server is supposed to provide replacements, as specified in [QUIC-TRANSPORT].¶

If the transport parameter "active_connection_id_limit" is negotiated as N, and the server has provided N Connection IDs and the client has started N paths, the limit is reached. If the client wants to start a new path, it has to retire one of the established paths.¶

Path validation uses the PATH_CHALLENGE and PATH_RESPONSE frame defined in QUIC-Transport [QUIC-TRANSPORT].¶

4.4. Path State Management

An endpoint uses PATH_STATUS frames to inform that the peer should send packets in the preference expressed by these frames. An endpoint uses the sequence number of the CID used by the peer for PATH_STATUS frames (describing the sender's path identifier).¶

In the example Figure 1, if the client wants to send a PATH_STATUS frame to tell the server that it prefers the path with CID sequence number 1 (of the server's side), the client should use the identifier of the server (sequence 1) in PATH_STATUS frame.¶

PATH_STATUS frame describes 4 kinds of path states:¶

• Abandon a path, and release the corresponding resource.¶
• Mark a path as "available", i.e., allow the peer to use its own logic to split traffic among available paths.¶
• Mark a path as "standby", i.e., suggest that no traffic should be sent on that path if another path is available.¶
• Mark the priority of a path, i.e, path 1 is weight 8, path 2 is weight 2, suggest that path 1 has higher priority than path 2, and peer should try to send more data in path 1.¶

PATH_STATUS frame can be sent via a different path, instead of the path identified by the Path Identifier field.¶

4.5. Path Close

An endpoint that want to delete a path SHOULD NOT rely on implicit signals like idle time or packet losses, but instead SHOULD use explicit signals like retiring Connection ID or asking to abandon path.¶

   Client                                                    Server

   (client tells server to abandon a path)
   1-RTT[X]: PATH_STATUS[id=1, PSSN1, status=abandon, pri.=0] ->
                            (server tells client to abandon a path)
      <- 1-RTT[Y]: PATH_STATUS[id=2, PSSN2, status=abandon, pri.=0],
                                                 MP_ACK[Seq=1, PN=X]
   (client abandons the path that it is using)
   1-RTT[X+1]: RETIRE_CONNECTION_ID[2], MP_ACK[Seq=2, PN=Y] ->
                         (server abandons the path that it is using)
       <- 1-RTT[Y+1]: RETIRE_CONNECTION_ID[1], MP_ACK[Seq=1, PN=X+1]

5.1. Packet protection for QUIC Multipath

Packet protection for QUIC V1 is specified is section 5 of [QUIC-TLS]. The general principles of packet protection are not changed for QUIC Multipath. No changes are needed for setting packet protection keys, initial secrets, header protection, use of 0-RTT keys, receiving out-of-order protected packets, receiving protected packets, or retry packet integrity. However, the use of multiple number spaces for 1-RTT packets requires changes in AEAD usage.¶

Section 5.3 of [QUIC-TLS] specifies AEAD usage, and in particular the use of a nonce, N, formed by combining the packet protection IV with the packet number. QUIC multipath uses multiple packet number spaces, and thus the packet number alone would not guarantee the uniqueness of the nonce. In order to guarantee this uniqueness, we construct the nonce N by combining the packet protection IV with the packet number and with the identifier of the path, which for 1-RTT packets is the Sequence Number of the Destination Connection ID present in the packet header, as defined in Section 5.1.1 of [QUIC-TRANSPORT], or zero if the Connection ID is zero-length. Section 19 of [QUIC-TRANSPORT] encode this Connection ID Sequence Number as a A variable-length integer, allowing values up to 2^62-1; for QUIC multipath, we require that these values be no larger than 2^32 -1.¶

For QUIC multipath, the construction of the nonce starts with the construction of a 96 bit path-and-packet-number, composed of the 32 bit Connection ID Sequence Number in byte order, two zero bits, and the 62 bits of the reconstructed QUIC packet number in network byte order. If the IV is larger than 96 bits, path-and-packet-number is left-padded with zeros to the size of the IV. The exclusive OR of the padded packet number and the IV forms the AEAD nonce.¶

For example, assuming the IV value is 6b26114b9cba2b63a9e8dd4f, the connection ID sequence number is 3, and the packet number is aead, the nonce will be set to 6b2611489cba2b63a9a873e2.¶

5.2. Key Update for QUIC Multipath

The Key Phase bit update process for QUIC V1 is specified in Section 6 of [QUIC-TLS]. The general principles of key update are not changed for Multipath QUIC. Following QUIC V1, the Key Phase bit is used to indicate which packet protection keys are used to protect the packet. The Key Phase bit is toggled to signal each subsequent key update. Because of network delays, packets protected with the older key might arrive later than the packets protected with the new key. Therefore, the endpoint needs to retain old packet keys to allow these delayed packets to be processed and it must distinguish between the new key and the old key. In QUIC V1, this is done using packet numbers so that the rule is made simple: Use the older key if packet number is lower than any packet number frome the current key phase.¶

In QUIC multipath, some care is needed in the initiating Key Update process. Because different paths use different packet number spaces but share a single key, when a key update is initiated on one path, packets sent to the other path needs to know when transition is complete. Otherwise, it is possible that the other paths send packets with the old keys, but skip sending any packets in the current key phase and directly jump to sending packet in the next key phase. When that happens, as the endpoint can only retain two sets of packet protection keys with the 1-bit Key Phase bit, the other paths cannot distinguish which key should be used to decode received packets, which results in a key rotation synchronization problem.¶

To address such a synchronization issue, in QUIC multipath, if key update is initilized on one path, the sender should send at least one packet with the new key on all active paths. Regarding the responding to Key Update process, the endpoint MUST NOT initiate a subsequent key update until a packet with the current key has been acknowledged on each path.¶

Following the Section 5.4. of [QUIC-TLS], the Key Phase bit is protected, so sending multiple packets with Key Phase bit flipping at the same time should not cause linkability issue.¶

7.1. Basic Scheduling

For an outgoing packet, the packet scheduler decides which path the packet shall be transmitted. A basic static scheduling strategy consists of four major components:¶

1. Path state: A scheduler may want to decide which path shall be activated to transmit data. For instance, a scheduler can choose to use only one of the two paths and completely ignore the other one. A scheduler marks the selected paths to be in the "available" state and the un-selected ones in the "standby" state.¶
2. Path priority: Due to the fact that costs of transmitting data over different paths are not always equal. For example, the energy (battery) cost over a 5G path and a wifi path are very different. In another example, transmissions over a wifi path and a cellular path may incur different charges per packet. Note that a user's preference may change over time. For instance, certain mobile carriers offer unlimited free data for a particular streaming app. Therefore, the path priority should be made available in the scheduler.¶
3. Path selection algorithm: A selection algorithm splits packets across different paths and determines the order of paths to be selected. The selection algorithm takes congestion controller states as inputs, such as smoothed RTTs (sRTTs), estimated bandwidths (eBWs) and congestion window sizes (CWNDs) as well as application-defined information such as path priorities and path states. The outputs of the algorithm is an ordered list of paths to put a packet on. To name a few, some of the commonly used algorithms are: - Round-Robin: There is no priority. it selects paths one by one in order to transmit data. - Lowest-RTT: It first chooses the path with the lowest RTT and feeds packets to it until that path's congestion window is full. Then it chooses the path with the second lowest RTT. - Highest-Sending-Rate: It first chooses the path with the highest bandwidth and feeds packets to it until that path's congestion window is full. Then it chooses path with the second largest bandwidth.¶
4. Packet redundancy: One major challenge in multi-path transmission is that a packet loss on the slow path might block the overall transmission when packets are split across fast-changing paths. As the path selection algorithm takes inputs from congestion controllers on predictions of the network which may not be accurate enough for fast-changing wireless channels, such an imprecise estimation could lead to network overuse/underuse. A solution to this problem is to implement packet redundancy strategy. A redundancy strategy can be applied to only ACK packets(partial redundancy) or all data packets (full redundancy). It is up to the application to determine whether, when, and on which packets to activate redundancy.¶

The path state and path priority are managed by PATH_STATUS frame. The path selection algorithm and packet redundancy are application related and should be controlled by the applicaiton.¶

7.2. Scheduling with QoE Feedback

Applications may have completely different QoE requirements---the interactive applications are delay sensitive, while the video streaming applications are more throughput sensitive. There is thus a trend of cross-layer design that takes applications' demands into account when managing paths or scheduling packets. The QoE feedback is used to fully support application-awareness in multipath scheduling and is carried in the QOE_CONTROL_SIGNALS frames Figure 6. The QOE_CONTROL_SIGNALS frames can include general application-level information that is needed by the schedulers. The frequency of such feedback should be controlled to limit the amount of extra packets. The QoE control signal allows a synchronization of viewpoints between two endhosts. It is up to the application to determine the interpretation of QoE control signals.¶

7.3. Per-stream Policy

As QUIC supports stream multiplexing, streams are allowed to associate stream priorities to express applications intent. For instance, objects in a web page may be dependent on others and thus have different priorities multipath quic scheduler. A stream priority-aware packet scheduling algorithm will improve the performance notably.¶

    High priority  /\  +---------+
                   ||  |         |
                   ||  +---------+
                   ||  +---------+
                   ||  |         |
                   ||  +---------+
                   ||     ...          User-defined stream priority
                   ||  +---------+
    Low priority   ||  |         |
                   ||  +---------+
    -----------------------------------------------------------
    High priority  /\  +---------+
                   ||  |         |
                   ||  +---------+
                   ||  +---------+
                   ||  |         |
                   ||  +---------+
                   ||     ...          Default stream priority
                   ||  +---------+
    Low priority   ||  |         |
                   ||  +---------+

The priority management scheme composes two separated priority ranges. The user-defined priority range includes those streams that the applications explicitly designate priorities, while the default priority range includes the streams with no priorities set by the applications. Only when the streams in the user-defined ranges have no data to send, the streams in the default priority range can send. In the same range, one can use the weighted-round robin for scheduling---the higher-priority streams get more quota for data to send in each round. One can also dynamically set/change the priorities of the streams in the default priority ranges to enable short stream first if needed.¶

8.1. Congestion control

Implementations MAY support coupled congestion controllers such as LIA [MPTCP-LIA], OLIA [MPTCP-OLIA], and etc., or support decoupled congestion controllers in environments using disjoint network paths.¶

In decoupled congestion control, each path runs its own congestion controller without interacting with the congestion controllers of other paths. That is to say, in the aspect of congestion control, a path behaves exactly the same as a normal QUIC connection over the same network path.¶

Each path MAY choose congestion control algorithm independently.¶

8.2. Packet number space and acknowledgements

Each path has it's own packet number space for transmitting 1-RTT packets.¶

ACK frame [QUIC-TRANSPORT] MUST be returned via the same path on which the corresponding packets were sent.¶

MP_ACK frame can be returned via either a different path, or the same path identified by the Path Identifier, based on different strategies of sending MP_ACK frames.¶

Note: Only MP_ACK frame returned via the same path can be used to calculate RTT(round trip time).¶

8.3. Flow control

TBD.¶

9.1. PATH_STATUS frame

PATH_STATUS Frame are used by endpoints to inform the peer of the current status of one path, and the peer should send packets according to the preference expressed in these frames. Endpoint use the sequence number of the CID used by the peer for PATH_STATUS frames (describing the sender's path identifier). PATH_STATUS frames are formatted as shown in Figure 4.¶

  PATH_STATUS Frame {
    Type (i) = 0x2a,
    Path Identifier (i),
    Path Status sequence number (i),
    Path Status (i),
    Path Priority (i),
  }

PATH_STATUS Frames contain the following fields:¶

Path Identifier: A variable-length integer specifying the path identifier.¶

Path Status sequence number: A variable-length integer specifying the sequence number assigned for this PATH_STATUS frame. There is a different path status sequence number space for each path.¶

Available values of Path Status field are:¶

• 0: Abandon¶
• 1: Standby¶
• 2: Available¶

If the value of Path Status field is 2-available, the receiver side can use the Path Priority field to express the priority weight of a path for the peer.¶

Frames may be received out of order. A peer MUST ignore an incoming PATH_STATUS frame if it previously received another PATH_STATUS frame for the same Path Identifier with a sequence number equal to or higher than the sequence number of the incoming frame.¶

PATH_STATUS frames SHOULD be acknowledged. If a packet containing a PATH_STATUS frame is considered lost, the peer should only repeat it if it was the last status sent for that path -- as indicated by the sequence number.¶

9.2. MP_ACK frame

MP_ACK frame allows for acknowledgements on different paths. MP_ACK frame is formatted by adding a Path Identifier field to [QUIC-TRANSPORT] ACK frame. MP_ACK frame is formatted as shown in Figure 5.¶

  MP_ACK Frame {
    Type (i) = 0x22..0x23,
    Path Identifier (i),
    Largest Acknowledged (i),
    ACK Delay (i),
    ACK Range Count (i),
    First ACK Range (i),
    ACK Range (..) ...,
    [ECN Counts (..)],
  }

Type(i) = 0x22 , with no ECN Counts Type(i) = 0x23 , with ECN Counts¶

9.3. QOE_CONTROL_SIGNALS frame

QOE_CONTROL_SIGNALS frame is used to carry quality of experience (QoE) information. A typical use of such information is to provide feedback to help application-aware scheduling. Note that different applications may have very different needs, the interpretation of the QoE control signal can be up to the users. QOE_CONTROL_SIGNALS frames are formatted as shown in Figure 6.¶

  QOE_CONTROL_SIGNALS Frame {
    Type (i) = 0x24,
    Path Identifier (i),
    QoE Control Signals Length(8),
    QoE Control Signals (..)
  }

QOE_CONTROL_SIGNALS frames may be received out of order, peers SHOULD pass them to the application as they arrive. Although QOE_CONTROL_SIGNALS frames are not retransmitted upon loss detection, they are ack-eliciting [QUIC-RECOVERY].¶

9.4. MP_ADD_ADDRESS frame

TBD.¶

9.5. MP_REMOVE_ADDRESS frame

TBD.¶