Why is the Multipath TCP scheduler so important ?
Multipath TCP can pool several links together. An important use case for Multipath TCP are the smartphones and tablets equipped with both 3G and WiFi interfaces. On such devices, Multipath TCP would establish two subflows, one over the WiFi interface and one over the 3G interface. Once the two subflows have been established, one the main decisions taken by Multipath TCP is the scheduling of the packets over the different subflows.
This scheduling decision is very important because it can impact performance and quality of experience. In the current implementation of Multipath TCP in the Linux kernel, the scheduler always prefers the subflow with the smallest round-trip-time to send data. A typical example of the operation of this scheduler is shown in the demo below from the https://www.multipath-tcp.org web site :
On this demo, the Multipath TCP client uses SSH over Multipath TCP to connect to a server that exports a screensaver over the SSH session. The client has three interfaces : WiFi, 3G and Ethernet. Multipath continuously measures the round-trip-time every time it sends data over any of these subflows. The Ethernet subflow has the lowest routing time. WiFi has a slightly higher round-trip-time and 3G has the worst round-trip-time. The SSH session is usually not limited by the network throughput and all subflows are available every time data needs to be transmitted. When Ethernet is available, it is preferred over the other interfaces. WiFi is preferred over 3G and 3G is only used when the two other interfaces are unavailable.
Sending data over the subflow with the smallest round-trip-time is not sufficient to achieve good performance on memory constrained devices that use a small receive window. This problem was first explored in [RPB+12] where reinjection and penalizations where proposed to mitigate the head-of-line blocking than can occur when the receiver advertises a limited receive window. The typical scenario is a smartphone using 3G and WiFi where 3G is slower than WiFi. If the receiver is window-limited, then it might happen that a packet is sent on the 3G subflow and then the WiFi subflow becomes blocked due to the limited receive window. In this case, the algorithm proposed in [RPB+12] will reinject the unacknowledged data from the 3G subflow on the WiFi subflow and reduce the congestion window on the 3G subflow. This problem has been analyzed in more details in [PKB13] by considering a large number of scenarios. This analysis has resulted in various improvements to the Linux Multipath TCP implementation [PBarreD+14]. A detailed analysis of the performance of the current packet schedulers has been published in [PFAB14].
Several researchers have proposed other types of schedulers for Multipath TCP or other transport protocols. In theory, if a scheduler has perfect knowledge of the network characteristics (bandwidth, delay), it could optimally schedule the packets that are transmitted to prevent head-of-line blocking problems and minimize the buffer occupancy. In practice, and in a real implementation, this is slightly more difficult because the delay varies and the bandwidth is unknown and varies in function of the other TCP connections.
The Delay-Aware Packet Scheduling For Multipath Transport proposed in [KLM+14] is a recent example of such schedulers. [KLM+14] considers two paths with different delays and generates a schedule, i.e. a list of sequence numbers to be transmitted over the different paths. Some limitations of the proposed scheduler are listed in [KLM+14], notably : the DAPS scheduler assumes that there is a lage difference in delays between the different paths and it assumes that the congestion windows are stable. In practice, these conditions are not always true and a scheduler should operate in all situations. [KLM+14] implements the proposed scheduler in the ns-2 CMT simulator dans evaluates its performance in small networks.
Another scheduler is proposed in [YAE13]. This scheduler tries to estimate the available capacity on each subflow and measures the number of bytes transmitted over each subflow. This enables the scheduler to detect when the subflow is sending too much data and select the other subflow at that time. The proposed scheduler is implemented in the Linux kernel, but unfortunately the source code does not seem to have been released by the authors of [YAE13]. The performance of the scheduler is evaluated by considering a simulation scenario with very long file transfers in a network with a very small amount of buffering. It is unclear whether this represents a real use case for Multipath TCP.
Since the publication of [PFAB14], various schedulers have been proposed and evaluated based on simulations and measurements. A detailed review of these schedulers would be much longer than a a blog post. Here are a few pointers for recent and interesting papers.
- Corbillon et al. propose a cross-layer scheduler that is optimised for video content [CAPK+16]
- Kimura et al. propose three alternate Multipath TCP schedulers [KLL17]
- Several researchers have proposed Multipath TCP schedulers that transmit the same packet over different subflows [WZS16], [FErbshausserB+16], [HKV16], [FSS+18]
- De Coninck proposes and implements a scheduler that is tuned for Multipath TCP applications running on smartphones [CB18]. In a nutshell, this scheduler tries to send packet over the last subflow from which data was received. This enables it to better support handovers from cellular to Wi-Fi compared to classical schedulers.
The most interesting approach to solve the Multipath TCP scheduling problem was proposed by Frommgen et al. [FrommgenRErbshausser+17]. This paper proposes a high-level API that enables application developpers to inject eBPF code containing their scheduling decision directly in the Linux kernel. Such a programming model provides a lot of flexibility and enables to solve this problem in a generic manner. Unfortunately, the code developed for this paper has not been submitted for inclusion in the Linux kernel implementation.
It can be expected that researchers will continue to propose scheduler for Multipath TCP and other multipath transport protocols (a new scheduler [RHB18] has already been proposed for the recent Multipath QUIC [DCB17]). There is still room for improvement in the Multipath TCP scheduler. However, to be convincing, the evaluation of a new scheduler should not be limited to small scale simulations. It should consider a wide range of scenarios like [PKB13] and demonstrate that it can be efficiently implemented in the Linux kernel. Ideally, it should provide a flexible API that leverages the eBPF VM in the Linux kernel such as proposed in [FrommgenRErbshausser+17].
References
| [CAPK+16] | Xavier Corbillon, Ramon Aparicio-Pardo, Nicolas Kuhn, Géraldine Texier, and Gwendal Simon. Cross-layer scheduler for video streaming over mptcp. In Proceedings of the 7th International Conference on Multimedia Systems, 7. ACM, 2016. |
| [DCB17] | Quentin De Coninck and Olivier Bonaventure. Multipath quic: design and evaluation. In Proceedings of the 13th International Conference on emerging Networking EXperiments and Technologies, 160–166. ACM, 2017. URL: https://www.multipath-quic.org. |
| [FSS+18] | Benevid Felix, Igor Steuck, Aldri Santos, Stefano Secci, and Michele Nogueira. Redundant packet scheduling by uncorrelated paths in heterogeneous wireless networks. In 2018 IEEE Symposium on Computers and Communications (ISCC), 00498–00503. IEEE, 2018. |
| [FErbshausserB+16] | Alexander Frommgen, Tobias Erbshäußer, Alejandro Buchmann, Torsten Zimmermann, and Klaus Wehrle. Remp tcp: low latency multipath tcp. In Communications (ICC), 2016 IEEE International Conference on, 1–7. IEEE, 2016. |
| [FrommgenRErbshausser+17] | (1, 2) Alexander Frömmgen, Amr Rizk, Tobias Erbshäußer, Max Weller, Boris Koldehofe, Alejandro Buchmann, and Ralf Steinmetz. A programming model for application-defined multipath tcp scheduling. In Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference, 134–146. ACM, 2017. |
| [HKV16] | Axel Hunger, Pascal A Klein, and Martin H Verbunt. Evaluation of the redundancy-bandwidth trade-off and jitter compensation in rmptcp. In New Technologies, Mobility and Security (NTMS), 2016 8th IFIP International Conference on, 1–5. IEEE, 2016. |
| [KLL17] | Bruno YL Kimura, Demetrius CSF Lima, and Antonio AF Loureiro. Alternative scheduling decisions for multipath tcp. IEEE Communications Letters, 21(11):2412–2415, 2017. |
| [KLM+14] | (1, 2, 3, 4) Nicolas Kuhn, Emmanuel Lochin, Ahlem Mifdaoui, Golam Sarwar, Olivier Mehani, and Roksana Boreli. Daps: intelligent delay-aware packet scheduling for multipath transport. In Communications (ICC), 2014 IEEE International Conference on, 1222–1227. IEEE, 2014. |
| [PBarreD+14] | C. Paasch, S. Barré, G. Detal, F. Duchene, and others. Linux kernel implementation of Multipath TCP. https://www.multipath-tcp.org, 2014. |
| [RHB18] | Alexander Rabitsch, Per Hurtig, and Anna Brunstrom. A stream-aware multipath quic scheduler for heterogeneous paths. In Proceedings of the Workshop on the Evolution, Performance, and Interoperability of QUIC, 29–35. ACM, 2018. |
| [WZS16] | Wei Wang, Liang Zhou, and Yi Sun. Improving multipath tcp for latency sensitive flows in the cloud. In Cloud Networking (Cloudnet), 2016 5th IEEE International Conference on, 45–50. IEEE, 2016. |
| [YAE13] | (1, 2) Fan Yang, Paul Amer, and Nasif Ekiz. A scheduler for multipath tcp. In Computer Communications and Networks (ICCCN), 2013 22nd International Conference on, 1–7. IEEE, 2013. |