RFC 6356

Coupled Congestion Control for Multipath Transport Protocols

📅 published October 2011, from ietf

🎀 RFC 6356: Coupled Congestion Control for Multipath Transport Protocols 🦋

  • Series: Internet Engineering Task Force (IETF) 🌸
  • RFC number: 6356 ✨
  • Authors: C. Raiciu (Univ. Politehnica of Bucharest), M. Handly, D. Wischik (Univ. College London) 🧚
  • Category: Experimental 🧪
  • ISSN: 2070-1721 💜
  • Date: October 2011 📅
  • Obsoletes / Updates: the title block doesn't list any, so this one stands on its own 🍓

Abstract 🌈

okay so endpoints are often connected by multiple paths, but they usually only use one path per connection 🙃 which is kinda wasteful, because the network would be way more efficient if all those paths could be used at the same time 💅 Multipath TCP is a proposal for doing exactly that with TCP 🦋

bestie, multipath needs its own congestion control algorithms, because single-path algorithms run into a bunch of issues in the multipath world 😭 the big one is that running regular TCP independently on each path would give the multipath flow more than its fair share at a bottleneck link that more than one of its subflows goes through. not fair!! 💀

it's also really desirable that a source with multiple paths available sends more of its traffic over the least congested path. this is called "resource pooling", where a bundle of links basically acts like one shared link with bigger capacity ✨ it makes the whole network more efficient and more robust when stuff fails 🫶

this document presents a congestion control algorithm that couples the congestion control on the different subflows by linking their increase functions, and it dynamically controls the overall aggressiveness of the multipath flow 🔥 the result is a practical algorithm that is fair to TCP at bottlenecks while moving traffic away from congested links. iconic behavior 👑

Status of This Memo 🎀

this document is not an Internet Standards Track specification 🙈 it's published for examination, experimental implementation, and evaluation 🧪

it defines an Experimental Protocol for the Internet community. it's a product of the Internet Engineering Task Force (IETF) and it represents the consensus of the IETF community 🤝 it has had public review and was approved for publication by the Internet Engineering Steering Group (IESG). not every IESG-approved document is a candidate for any level of Internet Standard, so see Section 2 of RFC 5741 for that 💅

for info about the current status, any errata, and how to give feedback, check http://www.rfc-editor.org/info/rfc6356 🦋

Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. 🌸

this document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication. please actually read those, because they spell out your rights and restrictions for this document 📜 also, any Code Components pulled out of this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Simplified BSD License 🫶

Table of Contents 🧚

1. Introduction ....................................................3
2. Requirements Language ...........................................5
3. Coupled Congestion Control Algorithm ............................5
4. Implementation Considerations ...................................7
   4.1. Computing "alpha" in Practice ..............................7
   4.2. Implementation Considerations when CWND is
        Expressed in Packets .......................................8
5. Discussion ......................................................9
6. Security Considerations ........................................10
7. Acknowledgements ...............................................11
8. References .....................................................11
   8.1. Normative References ......................................11
   8.2. Informative References ....................................11

1. Introduction ✨

okay so Multipath TCP (MPTCP, [MPTCP-MULTIADDRESSED]) is a set of extensions to regular TCP [RFC0793] that lets one TCP connection spread across multiple paths 🦋 it spreads load by creating separate "subflows" across potentially disjoint paths 🌈

so how should congestion control work for multipath TCP? 🤔 first, each subflow needs its own congestion control state (i.e., cwnd) so the capacity on that path gets matched by the offered load. the simplest way to do that is to just run standard TCP congestion control on each subflow. however, that's kinda unsatisfying, because it gives the multipath flow an unfair share when its different subflows share a common bottleneck 😭

bottleneck fairness is only one of the things multipath congestion control should do. these three goals capture the desirable properties of a practical multipath congestion control algorithm 💅

  • Goal 1 (Improve Throughput): a multipath flow should perform at least as well as a single path flow would on the best of the paths available to it 🚀
  • Goal 2 (Do no harm): a multipath flow should not take up more capacity from any of the resources shared by its different paths than it would if it were a single flow using only one of those paths. this guarantees it won't unduly harm other flows 🫶
  • Goal 3 (Balance congestion): a multipath flow should move as much traffic as possible off its most congested paths, subject to meeting the first two goals 🌸
goals 1 and 2 together make sure there's fairness at the bottleneck 🎀

goal 3 is the vibe of resource pooling [WISCHIK] 💜 if each multipath flow sends more data through its least congested path, the traffic in the network moves away from congested areas. this improves robustness and overall throughput, among other things ✨ the way to get resource pooling is to effectively "couple" the congestion control loops for the different subflows 🧚

we propose an algorithm that couples the additive increase function of the subflows, and uses unmodified TCP behavior when there's a drop 🦋 it leans on the traditional TCP mechanisms to detect drops, retransmit data, and so on 🔥

detecting shared bottlenecks reliably is hard 😩 but it's only one part of a bigger question: how much bandwidth should a multipath user use in total, even when there's no shared bottleneck? 🤔

the congestion controller aims to make the multipath flow's aggregate bandwidth the same as what a regular TCP flow would get on the best path available to it. to estimate the bandwidth of a regular TCP flow, the multipath flow estimates loss rates and round-trip times (RTTs) and computes the target rate. then it adjusts the overall aggressiveness (parameter alpha) to hit the desired rate 🍓

the mechanism applies all the time, but its effect depends on whether the multipath TCP flow influences the link loss rates or doesn't (low versus high statistical multiplexing) 👀 if MPTCP doesn't influence link loss rates, MPTCP gets the same throughput as TCP on the best path ✨ in cases with low statistical multiplexing, where the multipath flow does influence the loss rates on the path, the multipath throughput is strictly higher than what a single TCP would get on any of the paths 🚀 in particular, if it's using two idle paths, the multipath throughput is the sum of the two paths' throughput 💖

this algorithm ensures bottleneck fairness and fairness in the broader, network sense 🌈 we know current TCP fairness criteria are far from ideal, but a multipath TCP needs to be deployable in the current Internet 😤 if needed, new fairness criteria can be implemented by the same algorithm we propose, by appropriately scaling the overall aggressiveness 💅

the algorithm here is also meant to apply to other multipath transport protocols, like alternative multipath extensions to TCP, or really any other congestion-aware transport protocol 🦋 but for the sake of examples, this document will refer to MPTCP where appropriate 🧚

the design decisions and evaluation of the congestion control algorithm are published in [NSDI] 📚

the algorithm presented here only extends standard TCP congestion control for multipath operation 🎀 it's foreseeable that other congestion controllers will be implemented for multipath transport to get the bandwidth-scaling properties of the newer congestion control algorithms for regular TCP (such as Compound TCP and Cubic) 👑

2. Requirements Language 🎀

the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] . 💜

3. Coupled Congestion Control Algorithm ✨

okay bestie, this part is where the actual magic happens 🪄 The algorithm only changes the increase phase of congestion avoidance, which is the bit about how the window grows when an ACK comes in 🌸 Slow start, fast retransmit, fast recovery, and the multiplicative decrease in congestion avoidance all stay exactly the same as standard TCP [RFC5681]. So you don't have to relearn everything, just this one piece 💅

Let cwnd_i be the congestion window on subflow i, and cwnd_total be the sum of the congestion windows of all the subflows in the connection. Then p_i, rtt_i, and MSS_i are the loss rate, round-trip time (the smoothed round-trip time estimate that TCP uses), and maximum segment size on subflow i. Lots of letters, but they're just the stats for each path 🦋

We assume throughout this document that the congestion window is maintained in bytes, unless otherwise specified. We'll give a quick rundown of the packet-based version of cwnd in Section 4.2, so stay tuned 🧚

Okay, the big one. Our proposed "Linked Increases" algorithm MUST:

  • For each ACK received on subflow i, increase cwnd_i by
                alpha * bytes_acked * MSS_i   bytes_acked * MSS_i
          min ( --------------------------- , ------------------- )  (1)
                         cwnd_total                   cwnd_i

The increase formula (1) takes the minimum of two things 👀 The first argument to min is the increase for the multipath subflow, and the second is what regular TCP would get in the same scenario. So no multipath subflow can ever be more aggressive than a TCP flow in the same circumstances. That's how we hit Goal 2 (do no harm) 💜

"alpha" is the parameter that controls how aggressive the multipath flow is 🔥 To hit Goal 1 (improve throughput), alpha gets picked so the total throughput of the multipath flow equals what a TCP flow would get if it ran on the best path. Main character energy for the best path, honestly 👑

Let's see what this is actually doing. Say all the subflows have the same round-trip time and Maximum Segment Size (MSS). Then the algorithm grows the total window by roughly alpha*MSS per RTT. That growth gets split across the subflows based on how big each one's window is right now. So subflow i grows by alpha*cwnd_i/cwnd_total segments per RTT 🌈

Also, just like standard TCP, when cwnd_total is large the increase can come out as 0. When that happens, the increase MUST be set to 1 🫶 We'll get into how to actually implement this formula in the next section.

We assume implementations work similarly to appropriate byte counting (ABC, [RFC3465]), where the bytes_acked variable tracks how many bytes were newly acknowledged. If that isn't the case, bytes_acked SHOULD be set to MSS_i 🍓

Now, here's a sneaky trap 🙈 When you compute cwnd_total, it's super easy to just add up cwnd_i across all the subflows. But when a flow is in fast retransmit, its cwnd is usually inflated and doesn't actually reflect the real congestion window anymore. So the right move is to use the ssthresh (slow start threshold) value for flows in fast retransmit when you're computing cwnd_total. For connections that are app limited, the computation should look at the minimum of flight_size_i and cwnd_i, and also the minimum of flight_size_i and ssthresh_i, wherever that applies 💀

The total throughput of a multipath flow depends on alpha and on the loss rates, MSS values, and round-trip times of its paths. We need the total throughput to be no worse than what a single TCP would get on the best path. Because of that, you can't just pick one alpha up front that works in every situation. So alpha has to be computed from the properties of the paths we actually observe ✨

The formula for alpha is:

                        MAX (cwnd_i/rtt_i^2)
   alpha = cwnd_total * -------------------------           (2)
                        (SUM (cwnd_i/rtt_i))^2

Note:

MAX (x_i) means the maximum value for any possible value of i.

SUM (x_i) means the summation for all possible values of i.

Formula (2) comes from making the rate of the multipath flow equal to the rate of a TCP running on the best path, and then solving for alpha 🧠 Iconic math moment.

4. Implementation Considerations 💖

Equation (2) means alpha is a floating point value. That's a problem, because floating point operations would be pretty costly every time an ACK arrives 😭 And in lots of kernels, floating point operations are just disabled. Luckily, there's an easy way to approximate all of this with integer arithmetic 🎀

4.1. Computing "alpha" in Practice

Let alpha_scale be an integer. When you compute alpha, use alpha_scale * cwnd_total instead of cwnd_total, and do every operation in integer arithmetic 🔢

Then you scale the per-ACK increase down by alpha_scale. The end result is a simple tweak to Equation (1):

  • For each ACK received on subflow i, increase cwnd_i by:
                alpha * bytes_acked * MSS_i   bytes_acked * MSS_i
          min ( --------------------------- , ------------------- )  (3)
                 alpha_scale * cwnd_total              cwnd_i

The alpha_scale parameter sets how precise the alpha computation is. The errors you get when computing the numerator or denominator in the formula for alpha are pretty tiny, because cwnd in bytes is usually way bigger than the RTT measured in ms 🌸

With those changes, everything can run on integer arithmetic. We propose that alpha_scale be a small power of two, so you can use quick shift operations instead of multiplication and division ⚡ Our experiments show that alpha_scale=512 works well across a wide range of scenarios 🦋 Raising alpha_scale gives you more precision, but it also raises the risk of overflow when computing alpha. Using 64-bit operations would fix that. Another option is to adjust alpha_scale dynamically when you compute alpha, which avoids overflow and still gives you maximum precision 🫧

It's possible to calculate cwnd_total on every ACK, but that gets costly, especially when there are lots of subflows. To dodge that overhead, the implementation MAY keep a new per-connection state variable called "cwnd_total". If it does, the implementation updates the cwnd_total value whenever the individual subflow windows get updated. That only takes one extra addition or subtraction compared to the regular per-subflow congestion control code, so the performance hit should be minimal 💅

Computing alpha on every ACK is also expensive. We propose that alpha be a per-connection variable, computed whenever there's a drop and once per RTT otherwise. More precisely, let cwnd_new be the new value of the congestion window after it's inflated or after a drop. Only update alpha if the quotient of cwnd_i/MSS_i differs from the quotient of cwnd_new_i/MSS_i 🧚

In certain cases with small RTTs, computing alpha can still be a lot of work. Here's the observation: if RTTs were constant, you'd only need to compute alpha once per drop, since alpha doesn't change between drops. (The insight is that cwnd_i/cwnd_j stays constant as long as both windows increase.) Experimental results show that even when round-trip times aren't constant, using the average round-trip time per sawtooth, instead of the instantaneous RTT (that is, TCP's smoothed RTT estimator), gives good precision for computing alpha. So it's possible to compute alpha only once per drop, using a modified version of equation (2) where rtt_i is replaced with rtt_avg_i 🌈

If you use average round-trip time, rtt_avg_i is computed by sampling rtt_i whenever the window can fit one more packet, that is, when cwnd / MSS < (cwnd+increase)/MSS. The samples get averaged once per sawtooth into rtt_avg_i. This sampling makes sure there's no sampling bias for larger windows 🎀

Once you have cwnd_total and alpha, the congestion control algorithm runs for each subflow independently, with about the same complexity as the standard TCP increase code [RFC5681] ✨

4.2. Implementation Considerations when CWND is Expressed in Packets

When the congestion control algorithm keeps cwnd in packets instead of bytes, the algorithms above need to change so they account for the path MSS 🍓

To compute the increase when an ACK arrives, the multipath congestion control is a simple extension of the standard TCP code. In standard TCP, cwnd_cnt is an extra state variable that tracks how many segments have been acked since the last cwnd increment. cwnd gets incremented only when cwnd_cnt > cwnd, and then cwnd_cnt is set to 0 🦋

In the multipath case, cwnd_cnt_i is maintained for each subflow the same way as above, and cwnd_i is increased by 1 when cwnd_cnt_i > max(alpha_scale * cwnd_total / alpha, cwnd_i) 💜

When you compute alpha for packet-based stacks, the errors in the denominator terms are bigger. (That's because cwnd is much smaller, and rtt may be comparatively large.) Let max be the index of the subflow used in the numerator. To cut down the errors, it's easiest to move rtt_max (once it's calculated) from the numerator to the denominator, which changes equation (2) into the equivalent formula below 🧠

                                                                  (4)

                                               cwnd_max
 alpha = alpha_scale * cwnd_total * ------------------------------------
                                    (SUM ((rtt_max * cwnd_i) / rtt_i))^2

Note that the calculation of alpha doesn't take path MSS into account, and it's the same for stacks that keep cwnd in bytes or in packets. With this formula, the alpha calculation matches the rate of TCP on the best path in B/s for byte-oriented stacks, and in packets/s for packet-based stacks. In practice, MSS rarely changes between paths, so this shouldn't be a problem 🌸

Still, it's simple to derive formulae that let packet-based stacks reach byte rate fairness (and the other way around) if you need it 🔥 Specifically, for packet-based stacks that want byte-rate fairness, equation (4) changes like this: cwnd_max is replaced by cwnd_max * MSS_max * MSS_max, while cwnd_i is replaced with cwnd_i * MSS_i 💅

5. Discussion ✨

Okay so the algorithm we just built totally achieves Goals 1 and 2 🎀, but it does not get full resource pooling (Goal 3) 😭. Resource pooling means that no traffic should be sent over links with higher loss rates. To get perfect resource pooling, you'd have to couple both the increase and the decrease of congestion windows across subflows, like in [KELLY] 💅.

There are a few problems with a fully coupled controller, bestie 🙈. First, it won't probe paths with high loss rates enough, so it fails to notice free capacity when it shows up 💀. Second, these controllers tend to get "flappy" 🦋. When the paths are all about equally congested, the controller tends to dump the whole window onto one random subflow and give zero window to the others. Then it keeps flipping randomly between these stable points 🌀. That's not great in general, and it's especially bad when the rates depend on the RTT (which is how the current Internet works) 😤. In that case the resulting rate would fluctuate unpredictably depending on which state the controller happens to be in, and that breaks Goal 1.

Our proposal only couples the increases 👑. That means it probes high loss paths and picks up free capacity faster ⚡. It doesn't suffer from flappiness, but it also gets less resource pooling. The algorithm allocates window to the subflows so that p_i * cwnd_i = constant, for all i 📊. So when all the subflows have equal loss rates, each one gets an equal window, and the flappiness is gone 🌸. When the loss rates differ, more window gets allocated to the flow with the lower loss rate, progressively. Perfect resource pooling, on the other hand, would put all the window on the path with the lowest loss rate 🤏. You can find more details in [NSDI] 🧚.

6. Security Considerations 🔐

Okay, this part is super serious, so pay attention 🫶. One security concern is what we call the traffic-shifting attack 😱. Here's the deal: an on-path attacker can drop packets that belong to a multipath subflow. That makes the path look congested, which forces the sender's congestion controller to avoid that path and shove more data over the alternate subflows 🚨.

The attacker's goal is to create congestion on those alternative paths 🕵️‍♀️. This is totally doable, but it only has minor effects 🙄. By design, the coupled congestion controller is less (or about as) aggressive on any of its paths as a single TCP flow would be. So the biggest effect this attack can have is making a multipath subflow as aggressive as a single TCP flow. Not the end of the world, lowkey 💅.

Another effect of the traffic-shifting attack is that the new path can monitor all the traffic, when before it could only see a subset of it 👀. We believe that if privacy is needed, splitting traffic across multiple paths with MPTCP is not the right solution in the first place 🙅‍♀️. End-to-end encryption should be used instead 🔒✨.

Besides the traffic-shifting attack, the coupled congestion control algorithm defined in this document adds no other security considerations beyond the ones found in [MPTCP-MULTIADDRESSED] and [RFC6181] 🫠. The detailed security analysis for the Multipath TCP protocol itself is in [MPTCP-MULTIADDRESSED] and [RFC6181], so go check those out too 📚💜.

7. Acknowledgements 🌷

We thank Christoph Paasch for his suggestions on computing alpha in packet-based stacks 🙌. The authors are supported by Trilogy (http://www.trilogy-project.org), a research project (ICT-216372) partially funded by the European Community under its Seventh Framework Program 🇪🇺. The views expressed here are those of the author(s) only. The European Commission is not liable for any use that may be made of the information in this document 🫡.

8. References 📖

8.1. Normative References

  • [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.
  • [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
  • [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion Control", RFC 5681, September 2009.

8.2. Informative References

  • [KELLY] Kelly, F. and T. Voice, "Stability of end-to-end algorithms for joint routing and rate control", ACM SIGCOMM CCR vol. 35 num. 2, pp. 5-12, 2005, http://portal.acm.org/citation.cfm?id=1064415.
  • [MPTCP-MULTIADDRESSED] Ford, A., Raiciu, C., Handley, M., and O. Bonaventure, "TCP Extensions for Multipath Operation with Multiple Addresses", Work in Progress, July 2011.
  • [NSDI] Wischik, D., Raiciu, C., Greenhalgh, A., and M. Handley, "Design, Implementation and Evaluation of Congestion Control for Multipath TCP", Usenix NSDI, March 2011, http://www.cs.ucl.ac.uk/staff/c.raiciu/files/mptcp-nsdi.pdf.
  • [RFC3465] Allman, M., "TCP Congestion Control with Appropriate Byte Counting (ABC)", RFC 3465, February 2003.
  • [RFC6181] Bagnulo, M., "Threat Analysis for TCP Extensions for Multipath Operation with Multiple Addresses", RFC 6181, March 2011.
  • [WISCHIK] Wischik, D., Handley, M., and M. Bagnulo Braun, "The Resource Pooling Principle", ACM SIGCOMM CCR vol. 38 num. 5, pp. 47-52, October 2008, http://ccr.sigcomm.org/online/files/p47-handleyA4.pdf.

Authors' Addresses 🏡

Costin Raiciu
University Politehnica of Bucharest
Splaiul Independentei 313
Bucharest
Romania

EMail: costin.raiciu@cs.pub.ro


Mark Handley
University College London
Gower Street
London  WC1E 6BT
UK

EMail: m.handley@cs.ucl.ac.uk


Damon Wischik
University College London
Gower Street
London  WC1E 6BT
UK

EMail: d.wischik@cs.ucl.ac.uk

That's the whole thing, bestie 🌈💖 You made it!!

📦 where this page comes from