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 http://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 [NSDI12] 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 [NSDI12] 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 [Conext13] by considering a large number of scenarios. This analysis has resulted in various improvements to the Linux Multipath TCP implementation.
During the last years, 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.
A few articles have tried to solve the scheduling problem by using a different approach than the one currently implemented in the Linux kernel.
The Delay-Aware Packet Scheduling For Multipath Transport proposed in [DAPS] is a recent example of such schedulers. [DAPS] 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 [DAPS], 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. [DAPS] implements the proposed scheduler in the ns-2 CMT simulator dans evaluates its performance in small networks.
Another scheduler is proposed in [YAE2013]. 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 [YAE2013]. 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.
It can be expected that other researchers will propose new Multipath TCP schedulers. This is room for improvement in the part of the Multipath TCP code. 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 [Conext13] and demonstrate that it can be efficiently implemented in the Linux kernel.
References
| [NSDI12] | (1, 2) Costin Raiciu, C. Paasch, S. Barre, A. Ford, and M. Honda and O. Bonaventure and M. Handley, How hard can it be? designing and implementing a deployable Multipath TCP USENIX NSDI, 2012. |
| [Conext13] | (1, 2) Christoph Paasch, R. Khalili, and O. Bonaventure, On the benefits of applying experimental design to improve Multipath TCP, presented at the CoNEXT ‘13: Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, 2013. |
| [DAPS] | (1, 2, 3, 4) Nicolas Kuhn, E. Lochin, A. Mifdaoui, G. Sarwar, O. Mehani, and R. Boreli, DAPS: Intelligent Delay-Aware Packet Scheduling For Multipath Transport presented at the ICCC, 2014 |
| [YAE2013] | (1, 2) Fan Yang, P. Amer, and N. Ekiz, A Scheduler for Multipath TCP, presented at the Computer Communications and Networks (ICCCN), 2013 22nd International Conference on, 2013, pp. 1-7. |