19 Sep 2021
Multipath transmission is interesting, and I have been working quite a bit on implementing multipath support in QUIC. There are multiple ways to do that some simple and some more systematic, but all designs have the issue of timers. In single-path QUIC, the situation is simple: data is always sent on the same path, acknowledgements are always received on the same path. In multipath QUIC, data is sent on multiple paths, and acknowledgements for that data can be received on any available path. Those paths can well have different latency, and queues could build up at various places. There is no single “round trip time”, but different values depending on the combination of send path and receive path.
I think that the multipath implementations need to estimate one-way delays for each of the paths, and use combinations of one way delays to predict the “end to end” delay expected on a specific combination of send path and acknowledgement path. But then, we have to compute those one way delays.
When computing one-way delays, for each path there is not one estimate of delay but two: the delay from the local node to the peer, and the delay from the peer to the node – we could note them a Dxu and Dxd, where x is the path index and the suffix “u” or “d” indicates a delay for sending “up” on a path “u”, or “down” for receiving on that path for “d”. The delay for “sending to path1 and receiving the ack on path 2” will thus be:
If we have N paths, there will be N^2 possible combinations of upload and download, and N^2 different types of measurements. That looks like as many equations as there are variables, but these equations are not linearly independent. See for example the example of two paths:
The equation system only has a solution if
In which case it has an infinity of solutions for the form (D1u+x, D1d-x, D2u+x, D2d-x). We can only assess one-way delays if we fix this variable “x” to an arbitrary value. This is not an issue in practice, because we do not directly use the one-way delays. In transport protocols, we use end-to-end delays to assess whether a packet may be lost, and to assess the bandwidth-delay product. Some congestion control protocols operate by monitoring the variation of transmission delays. In both cases, the arbitrary variable “x” does not matter. When computing sums such as “D1u + D1d”, it cancels out. When computing variations such as “D1u(t) – D1u(t-x)”, it also cancels out. So, in practice, it suffices to set the variable x to a constant arbitrary value.
Let’s assume that acknowledgement packets contain a timestamp, as specified for example in the QUIC timestamps draft. With that, the nodes can assess the time at which a packet was sent, the time at which it was received and the acknowledgment sent, and the time at which the acknowledgement was received. Each time a new acknowledgement is received, the sender can measure the one-way delays on the up and down path. The nodes can compute statistics on the one way delays, such as average value and average deviation, much like they compute those statistics today for round trip times. They can use these statistics for predicting round trip times on arbitrary combinations of “up” and “down” paths.
Of course, the uncertainty that we just discussed still applies. The time at which a packet was sent or the acknowledgement received is measured in “local” time, using the clock of the sender. The time at which the packet was received or the acknowledgement sent is measured in “remote” time, using the clock of the receiver. There may be an arbitrary difference between these two clocks, but this does not matter if we are only using the one-way delays to predict round trip time or to track variations over time.
It is still possible to assess one-way delays in the absence of timestamps, but it gets more complicated. Suppose for example that at time “t”, a node receives on path 2 an acknowledgement of a packet sent on path 1. It obtains a measurement of R12, but it would like to assess the “hidden variables” D1u and D2d. We can write that as a problem of estimating the values from noisy measurements. These variables cannot be directly computed from a single measurement, but they can be estimated from a series of measurement.
When we receive a measurement M for a variable like R12, we already have some knowledge of the value probability for D1u and D2d, such as average and variance. That means that we can compute the most likely value of the measurement, the one that has the maximum combined probability of (D1u=d, D2d=M-d). The measurement can also be used to refine the estimate of these probabilities.
The general solution requires interesting statistical processing, but we could make some simplifying hypotheses. For example, if we made a Gaussian hypothesis, we could estimate the one-way delays and their covariance using a Kalman filter. But even that might be too complicated for transport protocol implementations that typically avoid floating point computation, let alone the resolution of linear systems such as Kalman filters. TCP implementations model round trip times using exponential filters to compute an average RTT and an average deviation. It is a big jump from that to a full fledged Kalman filter.
In the picoquic implementation, I programmed a very simplified model that just uses TCP level math. Basically:
I will leave initial conditions as an exercise for the reader. And I will leave to another blog the details on how exactly to use these delays for loss recovery and congestion control.