| RTP Media Congestion Avoidance Techniques (rmcat) | M. Welzl |
| Internet-Draft | S. Islam |
| Intended status: Experimental | S. Gjessing |
| Expires: April 27, 2015 | University of Oslo |
| October 24, 2014 |
Coupled congestion control for RTP media
draft-welzl-rmcat-coupled-cc-04
When multiple congestion controlled RTP sessions traverse the same network bottleneck, it can be beneficial to combine their controls such that the total on-the-wire behavior is improved. This document describes such a method for flows that have the same sender, in a way that is as flexible and simple as possible while minimizing the amount of changes needed to existing RTP applications.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 27, 2015.
Copyright (c) 2014 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) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
When there is enough data to send, a congestion controller must increase its sending rate until the path's capacity has been reached; depending on the controller, sometimes the rate is increased further, until packets are ECN-marked or dropped. This process inevitably creates undesirable queuing delay -- an effect that is amplified when multiple congestion controlled connections traverse the same network bottleneck. When such connections originate from the same host, it would therefore be ideal to use only one single sender-side congestion controller which determines the overall allowed sending rate, and then use a local scheduler to assign a proportion of this rate to each RTP session. This way, priorities could also be implemented quite easily, as a function of the scheduler; honoring user-specified priorities is, for example, required by rtcweb [rtcweb-usecases].
The Congestion Manager (CM) [RFC3124] provides a single congestion controller with a scheduling function just as described above. It is hard to implement because it requires an additional congestion controller and removes all per-connection congestion control functionality, which is quite a significant change to existing RTP based applications. This document presents a method that is easier to implement than the CM and also requires less significant changes to existing RTP based applications. It attempts to roughly approximate the CM behavior by sharing information between existing congestion controllers, akin to "Ensemble Sharing" in [RFC2140].
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].
Figure 1 shows the elements of the architecture for coupled congestion control: the Flow State Exchange (FSE), Shared Bottleneck Detection (SBD) and Flows. The FSE is a storage element that can be implemented in two ways: active and passive. In the active version, it initiates communication with flows and SBD. However, in the passive version, it does not actively initiate communication with flows and SBD; its only active role is internal state maintenance (e.g., an implementation could use soft state to remove a flow's data after long periods of inactivity). Every time a flow's congestion control mechanism would normally update its sending rate, the flow instead updates information in the FSE and performs a query on the FSE, leading to a sending rate that can be different from what the congestion controller originally determined. Using information about/from the currently active flows, SBD updates the FSE with the correct Flow State Identifiers (FSIs).
------- <--- Flow 1 | FSE | <--- Flow 2 .. ------- <--- .. Flow N ^ | | ------- | | SBD | <-------| -------
Figure 1: Coupled congestion control architecture
Since everything shown in Figure 1 is assumed to operate on a single host (the sender) only, this document only describes aspects that have an influence on the resulting on-the-wire behavior. It does, for instance, not define how many bits must be used to represent FSIs, or in which way the entities communicate. Implementations can take various forms: for instance, all the elements in the figure could be implemented within a single application, thereby operating on flows generated by that application only. Another alternative could be to implement both the FSE and SBD together in a separate process which different applications communicate with via some form of Inter-Process Communication (IPC). Such an implementation would extend the scope to flows generated by multiple applications. The FSE and SBD could also be included in the Operating System kernel.
This section gives an overview of the roles of the elements of coupled congestion control, and provides an example of how coupled congestion control can operate.
SBD uses knowledge about the flows to determine which flows belong in the same Flow Group (FG), and assigns FGIs accordingly. This knowledge can be derived in three basic ways:
The methods above have some essential trade-offs: e.g., multiplexing is a completely reliable measure, however it is limited in scope to two end points (i.e., it cannot be applied to couple congestion controllers of one sender talking to multiple receivers). A measurement-based SBD mechanism is described in [sbd]. Measurements can never be 100% reliable, in particular because they are based on the past but applying coupled congestion control means to make an assumption about the future; it is therefore recommended to implement cautionary measures, e.g. by disabling coupled congestion control if enabling it causes a significant increase in delay and/or packet loss. Measurements also take time, which entails a certain delay for turning on coupling (refer to [sbd] for details).
The FSE contains a list of all flows that have registered with it. For each flow, it stores the following:
The FSE can operate on window-based as well as rate-based congestion controllers (TEMPORARY NOTE: and probably -- not yet tested -- combinations thereof, with calculations to convert from one to the other). In case of a window-based controller, FSE_R is a window, and all the text below should be considered to refer to window, not rates.
In the FSE, each FG contains one static variable S_CR which is meant to be the sum of the calculated rates of all flows in the same FG (including the flow itself). This value is used to calculate the sending rate.
The information listed here is enough to implement the sample flow algorithm given below. FSE implementations could easily be extended to store, e.g., a flow's current sending rate for statistics gathering or future potential optimizations.
Flows register themselves with SBD and FSE when they start, deregister from the FSE when they stop, and carry out an UPDATE function call every time their congestion controller calculates a new sending rate. Via UPDATE, they provide the newly calculated rate and the desired rate (less than the calculated rate in case of application-limited flows, the same otherwise).
Below, two example algorithms are described. While other algorithms could be used instead, the same algorithm must be applied to all flows.
This algorithm was designed to be the simplest possible method to assign rates according to the priorities of flows. Simulations results in [fse] indicate that it does however not significantly reduce queuing delay and packet loss.
S_CR = S_CR + CC_R - FSE_R(f)
S_P = 0
for all flows i in FG do
S_P = S_P + P(i)
end for
for all flows i in FG do
FSE_R(i) = (P(i)*S_CR)/S_P
send FSE_R(i) to the flow i
end for
This algorithm extends algorithm 1 to conservatively emulate the behavior of a single flow by proportionally reducing the aggregate rate on congestion. Simulations results in [fse] indicate that it can significantly reduce queuing delay and packet loss.
if Timer has expired or not set then
DELTA = CC_R - FSE_R(f)
if DELTA < 0 then // Reduce S_CR proportionally
S_CR = S_CR * CC_R / FSE_R(f)
Set Timer for 2 RTTs
else
S_CR = S_CR + DELTA
end if
end if
S_P = 0
for all flows i in FG do
S_P = S_P + P(i)
end for
for all flows i in FG do
FSE_R(i) = (P(i)*S_CR)/S_P
send FSE_R(i) to the flow i
end for
This document has benefitted from discussions with and feedback from David Hayes, Andreas Petlund, and David Ros (who also gave the FSE its name).
This work was partially funded by the European Community under its Seventh Framework Programme through the Reducing Internet Transport Latency (RITE) project (ICT-317700).
This memo includes no request to IANA.
In scenarios where the architecture described in this document is applied across applications, various cheating possibilities arise: e.g., supporting wrong values for the calculated rate, the desired rate, or the priority of a flow. In the worst case, such cheating could either prevent other flows from sending or make them send at a rate that is unreasonably large. The end result would be unfair behavior at the network bottleneck, akin to what could be achieved with any UDP based application. Hence, since this is no worse than UDP in general, there seems to be no significant harm in using this in the absence of UDP rate limiters.
In the case of a single-user system, it should also be in the interest of any application programmer to give the user the best possible experience by using reasonable flow priorities or even letting the user choose them. In a multi-user system, this interest may not be given, and one could imagine the worst case of an "arms race" situation, where applications end up setting their priorities to the maximum value. If all applications do this, the end result is a fair allocation in which the priority mechanism is implicitly eliminated, and no major harm is done.
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |
| [RFC2140] | Touch, J., "TCP Control Block Interdependence", RFC 2140, April 1997. |
| [RFC3124] | Balakrishnan, H. and S. Seshan, "The Congestion Manager", RFC 3124, June 2001. |
| [RFC5348] | Floyd, S., Handley, M., Padhye, J. and J. Widmer, "TCP Friendly Rate Control (TFRC): Protocol Specification", RFC 5348, September 2008. |
| [fse] | Islam, S., Welzl, M., Gjessing, S. and N. Khademi, "Coupled Congestion Control for RTP Media", ACM SIGCOMM Capacity Sharing Workshop (CSWS 2014); extended version available as a technical report from http://safiquli.at.ifi.uio.no/paper/fse-tech-report.pdf , 2014. |
| [rtcweb-rtp-usage] | Perkins, C., Westerlund, M. and J. Ott, "Web Real-Time Communication (WebRTC): Media Transport and Use of RTP", Internet-draft draft-ietf-rtcweb-rtp-usage-18.txt, October 2014. |
| [rtcweb-usecases] | Holmberg, C., Hakansson, S. and G. Eriksson, "Web Real-Time Communication Use-cases and Requirements", Internet-draft draft-ietf-rtcweb-use-cases-and-requirements-14.txt, February 2014. |
| [sbd] | Hayes, D., Ferlin, S. and M. Welzl, "Shared Bottleneck Detection for Coupled Congestion Control for RTP Media", Internet-draft draft-hayes-rmcat-sbd-00.txt, October 2014. |
| [transport-multiplex] | Westerlund, M. and C. Perkins, "Multiple RTP Sessions on a Single Lower-Layer Transport", Internet-draft draft-westerlund-avtcore-transport-multiplexing-07.txt, October 2013. |
Active algorithms calculate the rates for all the flows in the FG and actively distribute them. In a passive algorithm, UPDATE returns a rate that should be used instead of the rate that the congestion controller has determined. This can make a passive algorithm easier to implement; however, the resulting dynamics are not fully understood. The algorithm described below is to be considered as highly experimental and did not perform as well as the active variants in simulations.
This passive version of the FSE stores the following information in addition to the variables described in Section 5.2:
The passive version of the FSE contains one static variable per FG called TLO (Total Leftover Rate -- used to let a flow 'take' bandwidth from application-limited or terminated flows) which is initialized to 0. For the passive version, S_CR is limited to increase or decrease as conservatively as a flow's congestion controller decides in order to prohibit sudden rate jumps.
for all flows i in FG do
new_S_CR = new_S_CR + FSE_R(i)
end for
DELTA = CC_R - FSE_R(f)
FSE_R(f) = CC_R
if DELTA > 0 then // the flow's rate has increased
S_CR = S_CR + DELTA
else if DELTA < 0 then
S_CR = new_S_CR + DELTA
end if
DR(f) = min(new_DR,FSE_R(f))
for all flows i in FG do
if P(i)<0 then
delete flow
else
S_P = S_P + P(i)
end if
end for
if DR(f) < FSE_R(f) then
TLO = TLO + (P(f)/S_P) * S_CR - DR(f))
end if
Rate = min(new_DR, (P(f)*S_CR)/S_P + TLO)
if Rate != new_DR and TLO > 0 then
TLO = 0 // f has 'taken' TLO
end if
if Rate > DR(f) then
DR(f) = Rate
end if
FSE_R(f) = Rate
The goals of the flow algorithm are to achieve prioritization, improve network utilization in the face of application-limited flows, and impose limits on the increase behavior such that the negative impact of multiple flows trying to increase their rate together is minimized. It does that by assigning a flow a sending rate that may not be what the flow's congestion controller expected. It therefore builds on the assumption that no significant inefficiencies arise from temporary application-limited behavior or from quickly jumping to a rate that is higher than the congestion controller intended. How problematic these issues really are depends on the controllers in use and requires careful per-controller experimentation. The coupled congestion control mechanism described here also does not require all controllers to be equal; effects of heterogeneous controllers, or homogeneous controllers being in different states, are also subject to experimentation.
This algorithm gives all the leftover rate of application-limited flows to the first flow that updates its sending rate, provided that this flow needs it all (otherwise, its own leftover rate can be taken by the next flow that updates its rate). Other policies could be applied, e.g. to divide the leftover rate of a flow equally among all other flows in the FGI.
In order to illustrate the operation of the passive coupled congestion control algorithm, this section presents a toy example of two flows that use it. Let us assume that both flows traverse a common 10 Mbit/s bottleneck and use a simplistic congestion controller that starts out with 1 Mbit/s, increases its rate by 1 Mbit/s in the absence of congestion and decreases it by 2 Mbit/s in the presence of congestion. For simplicity, flows are assumed to always operate in a round-robin fashion. Rate numbers below without units are assumed to be in Mbit/s. For illustration purposes, the actual sending rate is also shown for every flow in FSE diagrams even though it is not really stored in the FSE.
Flow #1 begins. It is a bulk data transfer and considers itself to have top priority. This is the FSE after the flow algorithm's step 1:
----------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 1 | 1 | 1 |
----------------------------------------
S_CR = 1, TLO = 0
Its congestion controller gradually increases its rate. Eventually, at some point, the FSE should look like this:
--------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 10 | 10 | 10 |
-----------------------------------------
S_CR = 10, TLO = 0
Now another flow joins. It is also a bulk data transfer, and has a lower priority (0.5):
----------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 10 | 10 | 10 |
| 2 | 1 | 0.5 | 1 | 1 | 1 |
------------------------------------------
S_CR = 11, TLO = 0
Now assume that the first flow updates its rate to 8, because the total sending rate of 11 exceeds the total capacity. Let us take a closer look at what happens in step 3 of the flow algorithm.
CC_R = 8. new_DR = infinity.
3 a) new_S_CR = 11; DELTA = 8 - 10 = -2.
3 b) FSE_Rf) = 8. DELTA is negative, hence S_CR = 9;
DR(f) = 8.
3 c) S_P = 1.5.
3 d) new sending rate = min(infinity, 1/1.5 * 9 + 0) = 6.
3 e) FSE_R(f) = 6.
The resulting FSE looks as follows:
----------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 6 | 8 | 6 |
| 2 | 1 | 0.5 | 1 | 1 | 1 |
-------------------------------------------
S_CR = 9, TLO = 0
The effect is that flow #1 is sending with 6 Mbit/s instead of the 8 Mbit/s that the congestion controller derived. Let us now assume that flow #2 updates its rate. Its congestion controller detects that the network is not fully saturated (the actual total sending rate is 6+1=7) and increases its rate.
CC_R=2. new_DR = infinity.
3 a) new_S_CR = 7; DELTA = 2 - 1 = 1.
3 b) FSE_R(f) = 2. DELTA is positive, hence S_CR = 9 + 1 = 10;
DR(f) = 2.
3 c) S_P = 1.5.
3 d) new sending rate = min(infinity, 0.5/1.5 * 10 + 0) = 3.33.
3 e) DR(f) = FSE_R(f) = 3.33.
The resulting FSE looks as follows:
-------------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 6 | 8 | 6 |
| 2 | 1 | 0.5 | 3.33 | 3.33 | 3.33 |
-------------------------------------------
S_CR = 10, TLO = 0
The effect is that flow #2 is now sending with 3.33 Mbit/s, which is close to half of the rate of flow #1 and leads to a total utilization of 6(#1) + 3.33(#2) = 9.33 Mbit/s. Flow #2's congestion controller has increased its rate faster than the controller actually expected. Now, flow #1 updates its rate. Its congestion controller detects that the network is not fully saturated and increases its rate. Additionally, the application feeding into flow #1 limits the flow's sending rate to at most 2 Mbit/s.
CC_R=7. new_DR=2.
3 a) new_S_CR = 9.33; DELTA = 1.
3 b) FSE_R(f) = 7, DELTA is positive, hence S_CR = 10 + 1 = 11;
DR = min(2, 7) = 2.
3 c) S_P = 1.5; DR(f) < FSE_R(f), hence TLO = 1/1.5 * 11 - 2 = 5.33.
3 d) new sending rate = min(2, 1/1.5 * 11 + 5.33) = 2.
3 e) FSE_R(f) = 2.
The resulting FSE looks as follows:
-------------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 2 | 2 | 2 |
| 2 | 1 | 0.5 | 3.33 | 3.33 | 3.33 |
-------------------------------------------
S_CR = 11, TLO = 5.33
Now, the total rate of the two flows is 2 + 3.33 = 5.33 Mbit/s, i.e. the network is significantly underutilized due to the limitation of flow #1. Flow #2 updates its rate. Its congestion controller detects that the network is not fully saturated and increases its rate.
CC_R=4.33. new_DR = infinity.
3 a) new_S_CR = 5.33; DELTA = 1.
3 b) FSE_R(f) = 4.33. DELTA is positive, hence S_CR = 12;
DR(f) = 4.33.
3 c) S_P = 1.5.
3 d) new sending rate: min(infinity, 0.5/1.5 * 12 + 5.33 ) = 9.33.
3 e) FSE_R(f) = 9.33, DR(f) = 9.33.
The resulting FSE looks as follows:
-------------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 1 | 1 | 1 | 2 | 2 | 2 |
| 2 | 1 | 0.5 | 9.33 | 9.33 | 9.33 |
-------------------------------------------
S_CR = 12, TLO = 0
Now, the total rate of the two flows is 2 + 9.33 = 11.33 Mbit/s. Finally, flow #1 terminates. It sets P to -1 and DR to 0. Let us assume that it terminated late enough for flow #2 to still experience the network in a congested state, i.e. flow #2 decreases its rate in the next iteration.
CC_R = 7.33. new_DR = infinity.
3 a) new_S_CR = 11.33; DELTA = -2.
3 b) FSE_R(f) = 7.33. DELTA is negative, hence S_CR = 9.33;
DR(f) = 7.33.
3 c) Flow 1 has P = -1, hence it is deleted from the FSE.
S_P = 0.5.
3 d) new sending rate: min(infinity, 0.5/0.5*9.33 + 0) = 9.33.
3 e) FSE_R(f) = DR(f) = 9.33.
The resulting FSE looks as follows:
-------------------------------------------
| # | FGI | P | FSE_R | DR | Rate |
| | | | | | |
| 2 | 1 | 0.5 | 9.33 | 9.33 | 9.33 |
-------------------------------------------
S_CR = 9.33, TLO = 0