Source Coding and Fountain Codes meet Multipath TCP
Multipath TCP continues to attract the interest of networking researchers. In less than one week, two preprints of papers that apply networking coding techniques to improve the performance Multipath TCP have been published.
In the first paper [FMTCP] , Yong Cui and his colleagues propose to apply Fountain Codes, as defined in RFC 6380 to Multipath TCP. This is an interesting approach that encodes the data and adds redundancy to the data before transmission. Thanks to this coding scheme, FMTCP does not need to retransmit all segments when losses occur. Of course, the tradeoff is that FMTCP generates more data than Multipath TCP. The paper evaluates the performance of FMTCP by comparing it with Multipath TCP by relying on ns-2 simulations. The simulations show that on lossy links FMTCP performs better than Multipath TCP. This is not surprising given that Multipath TCP’s congestion control scheme tries to move traffic away from lossy paths by reducing its transmission rate on those paths. FMTCP on the other hand can easily recover from a limited number of losses by relying on its coding scheme. It would be interesting to complement these simulations by :
- evaluating the performance of several competing FMTCP flows. This would show the impact of the losses on the congestion control scheme that is used by FMTCP (the paper is not very clear about the congestion control scheme that it used and unfortunately, the source code of the simulator used is not referenced in the paper)
- evaluating the support of interactive applications. Such applications are more likely to benefit from FMTCP than bulk transfer, but this might have an impact on the coding scheme that will not have to deal anymore with fixed size segments
Another related paper is SC-MPTCP [SCMPTCP] . SC-MPTCP relies on source coding to encode the segments before being transmitted. It also compares SC-MPTCP with regular Multipath TCP, but explicitly mentions the utilisation of the coupled congestion control scheme and relies on ns-3 simulations. The simulations analyze the impact of losses on the performance of both SC-MPTCP and regular Multipath TCP. In addition, it also proposes a scheduling technique to select on which subflows segments have to be sent to minimize reordering on the receiver and thus prevent head-of-line blocking when the receive buffer is limited. This technique is applicable to both regular Multipath TCP and SC-MPTCP. The paper then evaluates two interesting multihoming scenarios and shows the benefits of SC-MPTCP compared to Multipath TCP.
These two papers show that by adding redundancy to the data segments, it is possible to improve the performance of Multipath TCP in lossy environments. These results were based on simulations and there are two remaining questions that need to be answered :
- How can these techniques be efficiently implemented in TCP stacks, either kernel-based on by modifying user-level TCP stacks that start to (re)appear ? How do applications interact with such modified stacks ?
- What happens when several sources using source coding or fountain codes compete for the same bottleneck link where packets are discarded due to congestion ? Is the loss pattern as favorable for the source coding and fountain codes are random losses that mainly correspond to wireless links ?
Bibliography
| [FMTCP] | Yong Cui, Lian Wang, Xin Wang,Hongyi Wang, and Yining Wang, FMTCP: A Fountain Code-Based Multipath Transmission Control Protocol, to appear in IEEE/ACM Transactions on Networking, http://dx.doi.org/10.1109/TNET.2014.2300140 |
| [SCMPTCP] | Ming Li, Andrey Lukyanenko, Sasu Tarkoma, Yong Cui, Antti Yla-Jaaski, Tolerating path heterogeneity in multipath TCP with bounded receive buffers, Computer Networks, Available online 6 February 2014, ISSN 1389-1286, http://dx.doi.org/10.1016/j.comnet.2014.01.011. |
Computing MPTCP’s initial Data Sequence Number (IDSN)
On a regular TCP subflow, the sequence number used in the SYN segment serves as the initial sequence number. All subsequent segments are numbered starting at this initial sequence number.
![msc { width=800, arcgradient = 4; c [label="Client", linecolour=black], s [label="Server", linecolour=black]; |||; c=>s [ label = "SYN(seq=x)\n\n"]; |||; s=>c [label = "SYN+ACK(seq=y,ack=x+1)\n\n"]; |||; c=>s [label="ACK(ack=y+1)\n\n"]; |||; c=>s [label="First data(seq=x+1,ack=y+1)\n\n"]; |||; }](_images/mscgen-2d63b19605bdb327b313485ff1d93b9764c81291.png)
Multipath TCP uses two levels of sequence numbers : the regular sequence numbers that appear inside the header of each TCP segment and the Multipath-level Data Sequence Numbers that are used inside Multipath TCP options. The DSNs enable the receiver to reorder the data received over the different subflows. The Data Sequence Number is incremented every time data is sent and an initial Data Sequence Number is negotiated during the three way handshake on the first subflow. Due to the limited TCP option space, the initial DSN is computed from the information exchanged during the three-way handshake.
![msc { width=800,arcgradient = 4; c [label="Client", linecolour=black], s [label="Server", linecolour=black]; |||; c=>s [ label = "SYN(seq=x, MP_CAPABLE(ClientKey))\n\n" ]; |||; s=>c [label = "SYN+ACK(seq=y,ack=x+1, MP_CAPABLE(ServerKey))\n\n" ]; |||; c=>s [label="ACK(ack=y+1), MP_CAPABLE(ClientKey,ServerKey)\n\n"]; |||; }](_images/mscgen-e509aec4067bfbf247bf8c759cbe8c37f19e852a.png)
At the end of the three-way handshake, the initial DSN can be computed as the low order 64 bits of the hash of the sender’s key. At this point, one could wonder why we need an initial DSN for each Multipath TCP connection. There are two reasons for that. The first one is that using an initial DSN can improve the resilience to segment injection attacks by using an initial DSN that cannot be easily predicted by attackers. The second reason is to prevent data losses in case of failure of the initial subflow. Consider the scenario depicted below. The client creates the first subflow,
![msc { width=800,arcgradient = 4; c1 [label="Client1", linecolour=black], c2 [label="Client2", linecolour=black], s [label="Server", linecolour=black]; |||; c1=>s [ label = "SYN(seq=x, MP_CAPABLE(ClientKey))\n\n" ]; |||; s=>c1 [label = "SYN+ACK(seq=y,ack=x+1, MP_CAPABLE(ServerKey))\n\n" ]; |||; c1=>s [label="ACK(ack=y+1), MP_CAPABLE(ClientKey,ServerKey)\n\n"]; |||; c1-x s [label="First Data(seq=x+1,DSS(seq=idsn),data=a)\n\n"]; |||; c2=>s [ label = "SYN(seq=w, MP_JOIN)\n\n" ]; |||; s=>c2 [label = "SYN+ACK(seq=z,ack=w+1, MP_JOIN)\n\n"]; |||; c2=>s [label="ACK(ack=z+1))\n\n"]; |||; c2=> s [label="Second Data(seq=w+1,DSS(seq=idsn+1),data=b)\n\n"]; |||; }](_images/mscgen-0616a6419ef3ed53b910c13896d9bf7e4f9ec87b.png)
Without an agreement on the initial DSN, the server would not know whether the first data that it receives on the second subflow is the initial data at the Multipath TCP level or not.
Measuring with Multipath TCP
We often receive questions from students or engineers who start to use Multipath TCP about the measurement software that they can use to assess the performance of protocol. The best approach is often to use real traffic with real applications because this will correspond to the real use case for Multipath TCP. However, it is not always possible to deploy Multipath TCP on a large number of clients and servers to perform such experiments. During the last years, we’ve used several software tools to measure the performance of Multipath TCP :
There are other, more generic measurement tools that could also be useful for some types of measurements, but we do not have direct experience with them :
- mgen from NRL is capable of generating various types of traffic patterns over UDP and TCP
- D-ITG [Botta2012] allows to generate traffic according to some statistical properties. Also works above TCP.
If you’ve used other open-source software to measure Multipath TCP performance, feel free to add comments below so that we can update this page.
References
| [Botta2012] |
|
Multipath TCP algorithms : theory and design
The congestion control schemes used by Multipath TCP have been designed based on earlier theoretical work. The current implementation in the Linux kernel supports two congestion control schemes : Coupled RFC 6356 and OLIA [Khalili2012] . Several other multipath congestion control schemes have been proposed and it is likely that the quest for the best multipath congestion control scheme will continue in the coming years.
In [Peng2013] , Qiuyu Peng and his colleagues propose a theoretical analysis of several multipath TCP congestion schemes and compares them based on ns-2 simulations. The theoretical analysis considers three criteria :
- TCP Friendliness or is the congestion control scheme fair compared with regular TCP (NewReno in this case RFC 5681)
- Responsiveness or how quickly can the congestion control scheme can adapt to changing network conditions
- Window Fluctuations
The second criteria is very interesting because real traffic is more bursty than the large file transfers that are used to evaluate congestion control schemes by simulations.
Four existing congestion control schemes are compared with a newly proposed one in [Peng2013] . Unfortunately, the paper only considers early multipath congestion control schemes that predate RFC 6356 and does not compare the proposed algorithm with OLIA [Khalili2012] . Considering OLIA and perhaps other congestion control schemes and analyzing more complex simulations would be a useful extension to this work.
References
| [Khalili2012] | (1, 2) Ramin Khalili, Nicolas Gast, Miroslav Popovic, Utkarsh Upadhyay, and Jean-Yves Le Boudec. 2012. MPTCP is not pareto-optimal: performance issues and a possible solution. In Proceedings of the 8th international conference on Emerging networking experiments and technologies (CoNEXT ‘12). ACM, New York, NY, USA, 1-12. http://doi.acm.org/10.1145/2413176.2413178 |
| [Peng2013] | (1, 2) Qiuyu Peng, Anwar Walid, and Steven H. Low. 2013. Multipath TCP algorithms: theory and design. In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems (SIGMETRICS ‘13). ACM, New York, NY, USA, 305-316. http://doi.acm.org/10.1145/2465529.2466585 |