Multipath TCP in the datacenter

In the scientific literature, one of the first important use case for Multipath TCP was to distribute the load datacenters. Several architectures have been proposed for datacenters. They differ in how links are organised, but all offer multiple paths between the servers. Measurement studies:cite:benson2010network have shown that datacenter traffic is composed of a lot of short flows called mice that are delay-sensitive, but most of the data is transported in long flows, called elephants that consume most of the bandwidth and can compete with the mice. One of the problems in a datacenter is that congestion can happen on some of the network links while others are unused. This is illustrated in the figure below that shows two TCP connections competing for the same link.

../../../_images/dc-1.png

This problem was studied by Raiciu et al. by simulations [RBP+11]. They demonstrate that these collisions between competing flows significantly impact the performance of TCP.

../../../_images/dc-2.png

Different techniques have been explored in the literature to solve this problem. Many of the proposed approaches used a centralised controller with Openflow or other similar techniques to reroute flows to avoid congestion.

../../../_images/dc-3.png

With Multipath TCP, a completely distributed solution is possible. It leverages the utilisation of Equal Cost Multipath (ECMP) on datacenter switches. When a router/switch has several paths having the same cost towards a given destination, it can send packets over any of these paths. To maximise load-balancing, routers install all the available paths in their forwarding tables and balance the arriving packets over all of them. To ensure that all the packets that correspond to the same layer-4 flow follow the same path and thus have roughly the same delay, routers usually select the outgoing equal cost path by computing : H(IP_{src}||IP_{dst}||Port_{src}||Port_{dst})~mod~n when n is the number of equal cost paths towards the packet’s destination and H a hash function.

A consequence of this utilisation of ECMP is that TCP connections with different source ports between two hosts will sometimes follow different paths. This motivated the design of the ndiffports path manager in the Linux kernel. This path manager opens different subflows using the same source and destination IP addresses, the same destination port but different source addresses. The benefit of this approach is that the different subflows of a Multipath TCP connection will likely follow different paths inside the datacenter. With this path manager, Multipath TCP improves the utilisation of the datacenter as illustrated by the simulation results below.

../../../_images/dc-4.png

One of the limiting factors of ECMP is that flows with different source ports may still use the same paths. This problem can be fixed by using a reversible hash function [DPVDL+13].

From an operation viewpoint, the most convincing argument of [RBP+11] was that similar results were obtained with the Linux implementation of Multipath TCP [PBD+14] in real datacenters by using Amazon EC2 servers.

../../../_images/dc-5.png

The SIGCOMM‘11 article [RBP+11] attracted a lot of interest in the scientific community and is one of the most widely cited Multipath TCP articles. However, as of 2018, no real deployment of Multipath TCP in the datacenter has been publicly documented.

References

[DPVDL+13]Gregory Detal, Christoph Paasch, Simon Van Der Linden, Pascal Merindol, Gildas Avoine, and Olivier Bonaventure. Revisiting flow-based load balancing: stateless path selection in data center networks. Computer Networks, 57(5):1204–1216, 2013. URL: https://inl.info.ucl.ac.be/publications/revisiting-flow-based-load-balancing-stateless-path-selection-data-center-networks.html.
[PBD+14]C. Paasch, S. Barré, G. Detal, F. Duchene, and others. Linux kernel implementation of Multipath TCP. https://www.multipath-tcp.org, 2014.
[RBP+11](1, 2, 3) C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving Datacenter Performance and Robustness with Multipath TCP. ACM SIGCOMM Computer Communication Review (CCR), 41(4):266–277, 2011. URL: https://inl.info.ucl.ac.be/publications/improving-datacenter-performance-and-robustness-multipath-tcp.html.

The first Multipath TCP enabled smartphones

Smartphones are a very important use case for Multipath TCP with two very large scale deployments :

  • Apple uses Multipath TCP on iPhones and iPads. In 2013, the initial motivation was to support fast handovers for the Siri voice recognition application. Since iOS12, any iOS application can use Multipath TCP
  • High-end Samsung and LG samrtphones in South Korea use Multipath TCP to bond their Wi-Fi and cellular interface for the GigaLTE service to reach a bandwidth of up to 1 Gbps.

Although the designers of Multipath TCP were aware of the importance of the smartphones, the initial focus of the design was to enable ressource pooling. A first analysis of the benefits that Multipath TCP appeared in [RNBH11] with experiments carried out with a userspace implementation running on laptops.

The initial support for Multipath TCP on smartphones started with interactions with the engineers of a young Irish company called Multipath Networks. They had developed a first prototype that bonds several access networks together by using Multipath TCP. To cover new use cases, such as in-vehicle data transfers, they were testing the ability of Multipath TCP to quickly recover from the failure of any network interface. At that time, Multipath TCP was mainly used on servers and laptops and this part of the code was not heavily tested. Thanks to their detailed tests, we could improve the Multipath TCP implementation in the Linux kernel to better react to link failures.

When a smartphone moves, it may switch frequently from one access network to another. We explore these failures in more details in [PDD+12] by leveraging the recent updates to the Linux implementation. A key result of this paper was to demonstrate that Multipath TCP can provide fast handovers as shown in the figure below.

../../../_images/handover.png

Our measurements indicated that the application could take up to 3 seconds to recover from a network failure with TCP. For Multipath TCP, we proposed two different modes of operation: Full MPTCP and the Backup Mode. With Full MPTCP, the two subflows are used simultaneously while the Backup Mode use the MP_PRIO option to indicate that a subflow should only be used once the other subflow fails.

This paper was also the first to describe measurements with Multipath TCP on a real smartphone: the Nokia N950.

../../../_images/n950.png

It was mainly used to study the energy consumption of the cellular and Wi-Fi interfaces when using Multipath TCP.

../../../_images/n950-energy.png

Unfortunately, this developper phone never became widely used. We then performed some experiments with Samsung Galaxy S2 smartphones and we obtained later a dozen of Nexus5. The Samsung Galaxy S2 was used to record a nice video that demonstrates how Multipath TCP enables smooth handovers.

The video shows two live video streamings. The smartphone uses a Wi-Fi hotspot provided by a laptop that captures packets on its Wi-Fi interface and displays them on the right part of the screen. With regular TCP, the video stream stops when the smartphone leaves the area covered by the Wi-Fi access point. With Multipath TCP, the video stream switches automatically to the cellular interface and then later comes back to the Wi-Fi when the user returns.

Several researchers have explored the performance of the Linux Multipath TCP on smartphones. De Coninck et al. have configured a set of Nexus devices to use a SOCKS proxy [CBHB16a]. This is similar to the Giga LTE deployment mentioned earlier, but at a much smaller scale. This analysis captured 71 millions packets over more than 7 weeks. Using the same devices, the same team of researchers analysed the behavior of the most popular smartphone applications over Multipath TCP [CBHB16b]. A similar study was published in [NGQ+16]. Later, De Coninck proposed several improvements to the Multipath TCP implementation to tune it for interactive applications running on smartphones [CB18].

As of December 2018, there is no published detailed analysis of the performance of Multipath TCP on iPhones, despite the large user base. We’d be very interesting in collecting packet traces on servers that are used by iPhone applications that have enabled Multipath TCP. Feel free to contact me if you have deployed such an application.

References

[CBHB16a]Quentin De Coninck, Matthieu Baerts, Benjamin Hesmans, and Olivier Bonaventure. A first analysis of multipath tcp on smartphones. In 17th International Passive and Active Measurements Conference, volume 17. Springer, March-April 2016. URL: https://inl.info.ucl.ac.be/publications/first-analysis-multipath-tcp-smartphones.html.
[CBHB16b]Quentin De Coninck, Matthieu Baerts, Benjamin Hesmans, and Olivier Bonaventure. Observing real smartphone applications over multipath tcp. IEEE Communications Magazine, Network Testing Series, March 2016. URL: https://inl.info.ucl.ac.be/publications/observing-real-smartphone-applications-over-multipath-tcp.html.
[CB18]Quentin De Coninck and Olivier Bonaventure. Tuning multipath tcp for interactive applications on smartphones. In IFIP Networking 2018. 2018. URL: https://inl.info.ucl.ac.be/publications/tuning-multipath-tcp-interactive-applications-smartphones.html.
[NGQ+16]Ashkan Nikravesh, Yihua Guo, Feng Qian, Z Morley Mao, and Subhabrata Sen. An in-depth understanding of multipath tcp on mobile devices: measurement and system design. In Proceedings of the 22nd Annual International Conference on Mobile Computing and Networking, 189–201. ACM, 2016.
[PDD+12]C. Paasch, G. Detal, F. Duchene, C. Raiciu, and O. Bonaventure. Exploring Mobile/WiFi Handover with Multipath TCP. In Proceedings of the 2012 ACM SIGCOMM workshop on Cellular Networks: Operations, Challenges, and Future Design (CellNet). 2012. URL: https://inl.info.ucl.ac.be/publications/exploring-mobilewifi-handover-multipath-tcp.html.
[RNBH11]Costin Raiciu, Dragos Niculescu, Marcelo Bagnulo, and Mark James Handley. Opportunistic mobility with multipath tcp. In Proceedings of the sixth international workshop on MobiArch, 7–12. ACM, 2011.

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 [1] 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 [PBD+14]. A detailed analysis of the performance of the current packet schedulers has been published in [PFAB14].

../../../_images/mptcp-scheduler.png

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], [FErbshauerB+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. [FrommgenRErbshauer+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 [FrommgenRErbshauer+17].

[1]A first version of this post was published in 2014

References

[CB18]Quentin De Coninck and Olivier Bonaventure. Tuning multipath tcp for interactive applications on smartphones. In IFIP Networking 2018. 2018. URL: https://inl.info.ucl.ac.be/publications/tuning-multipath-tcp-interactive-applications-smartphones.html.
[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.
[FErbshauerB+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.
[FrommgenRErbshauer+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.
[PBD+14]C. Paasch, S. Barré, G. Detal, F. Duchene, and others. Linux kernel implementation of Multipath TCP. https://www.multipath-tcp.org, 2014.
[PFAB14](1, 2) Christoph Paasch, Simone Ferlin, Ozgu Alay, and Olivier Bonaventure. Experimental evaluation of multipath tcp schedulers. In ACM SIGCOMM Capacity Sharing Workshop (CSWS). ACM, 2014. URL: https://inl.info.ucl.ac.be/publications/experimental-evaluation-multipath-tcp-schedulers.html.
[PKB13](1, 2) Christoph Paasch, Ramin Khalili, and Olivier Bonaventure. On the benefits of applying experimental design to improve multipath tcp. In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, 393–398. ACM, 2013. URL: https://inl.info.ucl.ac.be/publications/benefits-applying-experimental-design-improve-multipath-tcp.
[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.
[RPB+12](1, 2) C. Raiciu, C. Paasch, S. Barre, A. Ford, M. Honda, F. Duchene, O. Bonaventure, and M. Handley. How Hard Can It Be? Designing and Implementing a Deployable Multipath TCP. In Proceedings of the 9th Symposium on Networked Systems Design and Implementation (NSDI). 2012. URL: https://inl.info.ucl.ac.be/publications/how-hard-can-it-be-designing-and-implementing-deployable-multipath-tcp.html.
[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.

The evolution of the MP_CAPABLE option

A TCP connection always starts with a three-way handshake. The client sends a SYN packet that contains the TCP options that it wants to negotiate with the server. The server replies with the TCP options that it supports. Like most TCP extensions (the only known exception is the support for Explicit Congestion Notification defined in RFC 3168 that uses bits of the TCP header for its negotiation), Multipath TCP defines the MP_CAPABLE option that needs to be used in the SYN.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE\n\n"];
|||;
c=>s [label="ACK\n\n"];
}

This option first appeared in draft-ford-mptcp-multiaddressed-00. Its evolution since 2009 reflects the evolution of the protocol and some of the lessons learned during its design and based on experiments.

../../../_images/draft-1.png

This firs draft proposed the following format for this MP_CAPABLE option.

../../../_images/mpc-1.png

This initial format contains several interesting fields. Like most TCP options, the MP_CAPABLE option is encoded using a type length value format. draft-ford-mptcp-multiaddressed-00 decided to use a different option type for different Multipath TCP options. At that time, this was considered to be a normal practice. The Selective Acknowledgement option RFC 2018 also defined two TCP options: one to negotiate its utilization in the SYN packet and one to carry the selective acknowledgements. Besides the Kind and Length field, this first MP_CAPABLE option contained a Version number (the protocol designers already anticipated the possibility of having different versions of Multipath TCP) and a 32 bits Sender Token.

TCP uses IP addresses and port numbers to identify connections. Each packet belonging to a connection carries the source and destination addresses and ports that uniquely identify it. Multipath TCP cannot rely on this to identify connections since each Multipath TCP connection is composed of a set of TCP connections, called subflows, which can vary over time. As indicated in RFC 6182, Multipath TCP uses unique identifiers that are called tokens to identify connections. Each host generates a token that identifies each connection locally. The MP_CAPABLE option carries the token chosen by the client in the SYN and the token chosen by the server in the SYN+ACK.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE(Client Token)\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE(Server Token)\n\n"];
|||;
c=>s [label="ACK\n\n"];
}

The first change to this important option appeared in draft-ford-mptcp-multiaddressed-03.txt which was published in March 2010.

../../../_images/mpc-2.png

When a TCP connection starts, the client selects its initial sequence number and places it inside the SYN. The server does the same with its SYN+ACK. In addition to the TCP sequence numbers that are included in the TCP header, Multipath TCP uses Data Sequence Numbers (DSN) that are placed in the DSN option. These DSNs are used to number the data that is sent over the different TCP subflows. The first drafts assumed that the DSN would start at 0 in both directions when a Multipath TCP connection is created. However, this choice raised security concerns since an attacker could easily predict the content of the DSN option that he should use to inject data inside a Multipath TCP connection. The normal way to solve such a problem is to use a random value for the initial DSN in each direction. The second version of the MP_CAPABLE option carries this value.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE(Client Token+IDSN)\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE(Server Token+IDSN)\n\n"];
|||;
c=>s [label="ACK\n\n"];
}

This draft was adopted by the working group as `draft-ietf-mptcp-multiaddressed-00<https://tools.ietf.org/html/draft-ietf-mptcp-multiaddressed-00>`_. The MP_CAPABLE option was modified again in draft-ietf-mptcp-multiaddressed-02. The new format is shown below.

../../../_images/mpc-3.png

The new format still contains a version number but it adds two keys. The client sends an MP_CAPABLE option that contains the sender key in the SYN, while the server replies with a SYN+ACK that contains an MP_CAPABLE option with both the Sender and the Receiver keys. These keys were introduced to improve the security of the addition of new subflows with the MP_JOIN option. The client and the server exchange their keys during the three-way handshake and later used them to prove their ownership of the connection when they add a new subflow. A simple solution to carry these keys would have been to extend the MP_CAPABLE option that was shown earlier. Unfortunately, it would have become difficult to open a Multipath TCP connection given the limited length of the TCP extended header.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE(Client Key)\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE(Server Key)\n\n"];
|||;
c=>s [label="ACK\n\n"];
}

These two keys help to authenticate the establishment of subflows, but we saw earlier that Multipath TCP hosts need to exchange tokens and agree on initial sequence numbers and that this information was included in the MP_CAPABLE option. With the new format, we had to find a way to compute these tokens and initial data sequence numbers from the keys. draft-ietf-mptcp-multiaddressed-02 computes them with a hash function and uses the high (resp. low) order bits of this hash as the token (resp. initial data sequence number).

Thanks to these hashes, we could reduce the length of the MP_CAPABLE option. However, this created a small risk of collision. When a host generates a random 64 bits key, it must verify that the hash of this key does collide with the token of an existing Multipath TCP connection. The figure below, extracted from [RPB+12], shows that the performance impact of this verification is not too high.

../../../_images/collision.png

Two modifications appeared in draft-ietf-mptcp-multiaddressed-03. The first one is that this document requests a single TCP Option Kind for all Multipath TCP options. This was mainly because we feared that a middlebox could drop one type of Multipath TCP option and not the other. Dealing with such corner cases would have made the protocol much more complex. We hoped that if a middlebox decided to drop unknown TCP options, it would do so based on their TCP Option Kind. Such a middlebox would thus either remove the MP_CAPABLE option from the SYN packet or discard such a SYN packet. Multipath TCP clients already coped with the latter by removing the MP_CAPABLE option after 3 unsuccessful attempts to transmit a SYN that carries this option.

../../../_images/mpc-4.png

The second modification introduced in draft-ietf-mptcp-multiaddressed-03 is the definition of two flags : S and C. S was intended to negotiate the hash function used to compute the tokens and the initial sequence numbers from the keys. C allows to negotiate the utilization of the DSN checksum that will be explained in a subsequent blog post.

The format of this option changed again in draft-ietf-mptcp-multiaddressed-10 to clarify the different flags.

../../../_images/mpc-5.png

Besides the changes to the format of the MP_CAPABLE option, there were also changes to the processing of this option. As middleboxes such as firewalls could block SYN that contain an unknown option, the Multipath TCP draft, draft-ford-mptcp-multiaddressed-00 already suggested that a client should only set the MP_CAPABLE options in the first few transmissions of a SYN and fallback to TCP if it does not receive any SYN+ACK in response. This is illustrated in the figure below.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
fw [label="Firewall", linecolour=red],
s [label="Server", linecolour=black];
|||;
c=>fw [ label = "SYN MP_CAPABLE"];
|||;
c=>fw [ label = "SYN MP_CAPABLE"];
|||;
c=>fw [ label = "SYN MP_CAPABLE"];
|||;
c=>s [ label = "SYN \n\n"];
|||;
s=>c [label = "SYN+ACK \n\n"];
|||;
c=>s [label="ACK\n\n"];
}

Another issue with Multipath TCP is that exchanging keys in the SYN and SYN+ACK forces the server to maintain state for each connection attempt upon reception of the client SYN. This could lead to denial of service attacks that have affected TCP implementations in the past RFC 4987. Since draft-ietf-mptcp-multiaddressed-02, Multipath TCP copes with this problem by allowing the server to be stateless. For this, the client needs to retransmit its key and the server key inside an MP_CAPABLE option that is carried in the third ACK.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE(Client Key)\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE(Server Key)\n\n"];
|||;
c=>s [label="ACK MP_CAPABLE(Client and Server Keys)\n\n"];
}

The presence of the MP_CAPABLE option in the third packet also confirms the utilization of Multipath TCP to the server.

At this point, RFC 6824 was published in January 2013. In September 2013, Apple deployed Multipath TCP on all iPhones to support the Siri application. This deployment will be discussed in a specific blog post.

Based on the feedback received from implementors and given the successful deployments, the MPTCP working group started in late 2013 to work on a revision of RFC 6824 : draft-ietf-mptcp-rfc6824bis-00. A first change was proposed in draft-ietf-mptcp-rfc6824bis-05. This was an attempt to reduce the length of the options in the SYN packet.

../../../_images/mpc-6.png

The client sends a small MP_CAPABLE option that only contains the first four bytes. The server replies with its key and then the client echoes the client and server keys in the third ACK. The MP_CAPABLE option is also placed in the first packet that carries data. This choice was motivated by the fact that the third ACK is not transmitted reliably. If this packet does not reach the server, then it will not be aware of the client key. By placing the MP_CAPABLE option inside a packet that carries data, we ensure that it will eventually reach the server.

msc {
width=800, arcgradient = 4;

c [label="Client", linecolour=black],
s [label="Server", linecolour=black];
|||;
c=>s [ label = "SYN MP_CAPABLE(4 bytes only)\n\n"];
|||;
s=>c [label = "SYN+ACK MP_CAPABLE(Server Key)\n\n"];
|||;
c=>s [label="ACK MP_CAPABLE(Client and Server Keys)\n\n"];
|||;
c=>s [label="ACK MP_CAPABLE(Client and Server Keys, length of data and checksum)\n[First data]\n"];
}

Another important modification appeared in draft-ietf-mptcp-rfc6824bis-07. Although this modification only specifies the value of one bit in the MP_CAPABLE option, it is important to efficiently support load-balancers. This has been described in details in [DB17].

../../../_images/mpc-7.png

References

[DB17]Fabien Duchene and Olivier Bonaventure. Making multipath tcp friendlier to load balancers and anycast. In Network Protocols (ICNP), 2017 IEEE 25th International Conference on, 1–10. IEEE, 2017. URL: https://inl.info.ucl.ac.be/publications/making-multipath-tcp-friendlier-load-balancers-and-anycast.html.
[RPB+12]C. Raiciu, C. Paasch, S. Barre, A. Ford, M. Honda, F. Duchene, O. Bonaventure, and M. Handley. How Hard Can It Be? Designing and Implementing a Deployable Multipath TCP. In Proceedings of the 9th Symposium on Networked Systems Design and Implementation (NSDI). 2012. URL: https://inl.info.ucl.ac.be/publications/how-hard-can-it-be-designing-and-implementing-deployable-multipath-tcp.html.