summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc8382.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc8382.txt')
-rw-r--r--doc/rfc/rfc8382.txt1403
1 files changed, 1403 insertions, 0 deletions
diff --git a/doc/rfc/rfc8382.txt b/doc/rfc/rfc8382.txt
new file mode 100644
index 0000000..ee501b1
--- /dev/null
+++ b/doc/rfc/rfc8382.txt
@@ -0,0 +1,1403 @@
+
+
+
+
+
+
+Internet Engineering Task Force (IETF) D. Hayes, Ed.
+Request for Comments: 8382 S. Ferlin
+Category: Experimental Simula Research Laboratory
+ISSN: 2070-1721 M. Welzl
+ K. Hiorth
+ University of Oslo
+ June 2018
+
+
+Shared Bottleneck Detection for Coupled Congestion Control for RTP Media
+
+Abstract
+
+ This document describes a mechanism to detect whether end-to-end data
+ flows share a common bottleneck. This mechanism relies on summary
+ statistics that are calculated based on continuous measurements and
+ used as input to a grouping algorithm that runs wherever the
+ knowledge is needed.
+
+Status of This Memo
+
+ This document is not an Internet Standards Track specification; it is
+ published for examination, experimental implementation, and
+ evaluation.
+
+ This document defines an Experimental Protocol for the Internet
+ community. This document is a product of the Internet Engineering
+ Task Force (IETF). It represents the consensus of the IETF
+ community. It has received public review and has been approved for
+ publication by the Internet Engineering Steering Group (IESG). Not
+ all documents approved by the IESG are candidates for any level of
+ Internet Standard; see Section 2 of RFC 7841.
+
+ Information about the current status of this document, any errata,
+ and how to provide feedback on it may be obtained at
+ https://www.rfc-editor.org/info/rfc8382.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 1]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+Copyright Notice
+
+ Copyright (c) 2018 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
+ (https://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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 2]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+Table of Contents
+
+ 1. Introduction ....................................................4
+ 1.1. The Basic Mechanism ........................................4
+ 1.2. The Signals ................................................4
+ 1.2.1. Packet Loss .........................................4
+ 1.2.2. Packet Delay ........................................5
+ 1.2.3. Path Lag ............................................5
+ 2. Definitions .....................................................6
+ 2.1. Parameters and Their Effects ...............................7
+ 2.2. Recommended Parameter Values ...............................8
+ 3. Mechanism .......................................................9
+ 3.1. SBD Feedback Requirements .................................10
+ 3.1.1. Feedback When All the Logic Is Placed at
+ the Sender .........................................10
+ 3.1.2. Feedback When the Statistics Are Calculated at the
+ Receiver and SBD Is Performed at the Sender ........11
+ 3.1.3. Feedback When Bottlenecks Can Be Determined
+ at Both Senders and Receivers ......................11
+ 3.2. Key Metrics and Their Calculation .........................12
+ 3.2.1. Mean Delay .........................................12
+ 3.2.2. Skewness Estimate ..................................12
+ 3.2.3. Variability Estimate ...............................13
+ 3.2.4. Oscillation Estimate ...............................13
+ 3.2.5. Packet Loss ........................................14
+ 3.3. Flow Grouping .............................................14
+ 3.3.1. Flow-Grouping Algorithm ............................14
+ 3.3.2. Using the Flow Group Signal ........................18
+ 4. Enhancements to the Basic SBD Algorithm ........................18
+ 4.1. Reducing Lag and Improving Responsiveness .................18
+ 4.1.1. Improving the Response of the Skewness Estimate ....19
+ 4.1.2. Improving the Response of the Variability
+ Estimate ...........................................20
+ 4.2. Removing Oscillation Noise ................................21
+ 5. Measuring OWD ..................................................21
+ 5.1. Timestamp Resolution ......................................21
+ 5.2. Clock Skew ................................................22
+ 6. Expected Feedback from Experiments .............................22
+ 7. IANA Considerations ............................................22
+ 8. Security Considerations ........................................22
+ 9. References .....................................................23
+ 9.1. Normative References ......................................23
+ 9.2. Informative References ....................................23
+ Acknowledgments ...................................................25
+ Authors' Addresses ................................................25
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 3]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+1. Introduction
+
+ In the Internet, it is not normally known whether flows (e.g., TCP
+ connections or UDP data streams) traverse the same bottlenecks. Even
+ flows that have the same sender and receiver may take different paths
+ and may or may not share a bottleneck. Flows that share a bottleneck
+ link usually compete with one another for their share of the
+ capacity. This competition has the potential to increase packet loss
+ and delays. This is especially relevant for interactive applications
+ that communicate simultaneously with multiple peers (such as
+ multi-party video). For RTP media applications such as RTCWEB,
+ [RTP-COUPLED-CC] describes a scheme that combines the congestion
+ controllers of flows in order to honor their priorities and avoid
+ unnecessary packet loss as well as delay. This mechanism relies on
+ some form of Shared Bottleneck Detection (SBD); here, a measurement-
+ based SBD approach is described.
+
+1.1. The Basic Mechanism
+
+ The mechanism groups flows that have similar statistical
+ characteristics together. Section 3.3.1 describes a simple method
+ for achieving this; however, a major part of this document is
+ concerned with collecting suitable statistics for this purpose.
+
+1.2. The Signals
+
+ The current Internet is unable to explicitly inform endpoints as to
+ which flows share bottlenecks, so endpoints need to infer this from
+ whatever information is available to them. The mechanism described
+ here currently utilizes packet loss and packet delay but is not
+ restricted to these. As Explicit Congestion Notification (ECN)
+ becomes more prevalent, it too will become a valuable base signal
+ that can be correlated to detect shared bottlenecks.
+
+1.2.1. Packet Loss
+
+ Packet loss is often a relatively infrequent indication that a flow
+ traverses a bottleneck. Therefore, on its own it is of limited use
+ for SBD; however, it is a valuable supplementary measure when it is
+ more prevalent (refer to [RFC7680], Section 2.5 for measuring packet
+ loss).
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 4]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+1.2.2. Packet Delay
+
+ End-to-end delay measurements include noise from every device along
+ the path, in addition to the delay perturbation at the bottleneck
+ device. The noise is often significantly increased if the round-trip
+ time is used. The cleanest signal is obtained by using One-Way Delay
+ (OWD) (refer to [RFC7679], Section 3 for a definition of OWD).
+
+ Measuring absolute OWD is difficult, since it requires both the
+ sender and receiver clocks to be synchronized. However, since the
+ statistics being collected are relative to the mean OWD, a relative
+ OWD measurement is sufficient. Clock skew is not usually significant
+ over the time intervals used by this SBD mechanism (see [RFC6817],
+ Appendix A.2 for a discussion on clock skew and OWD measurements).
+ However, in circumstances where it is significant, Section 5.2
+ outlines a way of adjusting the calculations to cater to it.
+
+ Each packet arriving at the bottleneck buffer may experience very
+ different queue lengths and, therefore, different waiting times. A
+ single OWD sample does not, therefore, characterize the path well.
+ However, multiple OWD measurements do reflect the distribution of
+ delays experienced at the bottleneck.
+
+1.2.3. Path Lag
+
+ Flows that share a common bottleneck may traverse different paths,
+ and these paths will often have different base delays. This makes it
+ difficult to correlate changes in delay or loss. This technique uses
+ the long-term shape of the delay distribution as a base for
+ comparison to counter this.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 5]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+2. Definitions
+
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
+ "OPTIONAL" in this document are to be interpreted as described in
+ BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
+ capitals, as shown here.
+
+ Acronyms used in this document:
+
+ OWD - One-Way Delay
+
+ MAD - Mean Absolute Deviation
+
+ SBD - Shared Bottleneck Detection
+
+ Conventions used in this document:
+
+ T the base time interval over which measurements
+ are made
+
+ N the number of base time, T, intervals used in some
+ calculations
+
+ M the number of base time, T, intervals used in some
+ calculations, where M <= N
+
+ sum(...) summation of terms of the variable in parentheses
+
+ sum_T(...) summation of all the measurements of the variable in
+ parentheses taken over the interval T
+
+ sum_NT(...) summation of all measurements taken over the
+ interval N*T
+
+ sum_MT(...) summation of all measurements taken over the
+ interval M*T
+
+ E_T(...) the expectation or mean of the measurements of the
+ variable in parentheses over T
+
+ E_N(...) the expectation or mean of the last N values of the
+ variable in parentheses
+
+ E_M(...) the expectation or mean of the last M values of the
+ variable in parentheses
+
+
+
+
+
+Hayes, et al. Experimental [Page 6]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ num_T(...) the count of measurements of the variable in
+ parentheses taken in the interval T
+
+ num_MT(...) the count of measurements of the variable in
+ parentheses taken in the interval M*T
+
+ PB a boolean variable indicating that the particular
+ flow was identified transiting a bottleneck in the
+ previous interval T (i.e., "Previously Bottleneck")
+
+ skew_est a measure of skewness in an OWD distribution
+
+ skew_base_T a variable used as an intermediate step in
+ calculating skew_est
+
+ var_est a measure of variability in OWD measurements
+
+ var_base_T a variable used as an intermediate step in
+ calculating var_est
+
+ freq_est a measure of low-frequency oscillation in the OWD
+ measurements
+
+ pkt_loss a measure of the proportion of packets lost
+
+ p_l, p_f, p_mad, c_s, c_h, p_s, p_d, p_v
+ various thresholds used in the mechanism
+
+ M and F number of values related to N
+
+2.1. Parameters and Their Effects
+
+ T T should be long enough so that there are enough packets
+ received during T for a useful estimate of the short-term
+ mean OWD and variation statistics. Making T too large can
+ limit the efficacy of freq_est. It will also increase the
+ response time of the mechanism. Making T too small will
+ make the metrics noisier.
+
+ N and M N should be large enough to provide a stable estimate of
+ oscillations in OWD. Often, M=N is just fine, though
+ having M<N may be beneficial in certain circumstances. M*T
+ needs to be long enough to provide stable estimates of
+ skewness and MAD.
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 7]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ F F determines the number of intervals over which statistics
+ are considered to be equally weighted. When F=M, recent
+ and older measurements are considered equal. Making F<M
+ can increase the responsiveness of the SBD mechanism. If F
+ is too small, statistics will be too noisy.
+
+ c_s c_s is the threshold in skew_est used for determining
+ whether a flow is transiting a bottleneck or not. Lower
+ values of c_s require bottlenecks to be more congested to
+ be considered for grouping by the mechanism. c_s should be
+ set within the range of +0.2 to -0.1 -- low enough so that
+ lightly loaded paths do not give a false indication.
+
+ p_l p_l is the threshold in pkt_loss used for determining
+ whether a flow is transiting a bottleneck or not. When
+ pkt_loss is high, it becomes a better indicator of
+ congestion than skew_est.
+
+ c_h c_h adds hysteresis to the bottleneck determination. It
+ should be large enough to avoid constant switching in the
+ determination but low enough to ensure that grouping is not
+ attempted when there is no bottleneck and the delay and
+ loss signals cannot be relied upon.
+
+ p_v p_v determines the sensitivity of freq_est to noise.
+ Making it smaller will yield higher but noisier values for
+ freq_est. Making it too large will render it ineffective
+ for determining groups.
+
+ p_* Flows are separated when the
+ skew_est|var_est|freq_est|pkt_loss measure is greater than
+ p_s|p_mad|p_f|p_d. Adjusting these is a compromise between
+ false grouping of flows that do not share a bottleneck and
+ false splitting of flows that do. Making them larger can
+ help if the measures are very noisy, but reducing the noise
+ in the statistical measures by adjusting T and N|M may be a
+ better solution.
+
+2.2. Recommended Parameter Values
+
+ [Hayes-LCN14] uses T=350ms and N=50. The other parameters have been
+ tightened to reflect minor enhancements to the algorithm outlined in
+ Section 4: c_s=0.1, p_f=p_d=0.1, p_s=0.15, p_mad=0.1, p_v=0.7. M=30,
+ F=20, and c_h=0.3 are additional parameters defined in that document.
+ These are values that seem to work well over a wide range of
+ practical Internet conditions.
+
+
+
+
+
+Hayes, et al. Experimental [Page 8]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+3. Mechanism
+
+ The mechanism described in this document is based on the observation
+ that when flows traverse a common bottleneck, each flow's
+ distribution of packet delay measurements has similar shape
+ characteristics. These shape characteristics are described using
+ three key summary statistics --
+
+ 1. variability estimate (var_est; see Section 3.2.3)
+
+ 2. skewness estimate (skew_est; see Section 3.2.2)
+
+ 3. oscillation estimate (freq_est; see Section 3.2.4)
+
+ -- with packet loss (pkt_loss; see Section 3.2.5) used as a
+ supplementary statistic.
+
+ Summary statistics help to address both the noise and the path lag
+ problems by describing the general shape over a relatively long
+ period of time. Each summary statistic portrays a "view" of the
+ bottleneck link characteristics, and when used together, they provide
+ a robust discrimination for grouping flows. An RTP media device may
+ be both a sender and a receiver. SBD can be performed at either a
+ sender or a receiver, or both.
+
+ In Figure 1, there are two possible locations for shared bottleneck
+ detection: the sender side and the receiver side.
+
+ +----+
+ | H2 |
+ +----+
+ |
+ | L2
+ |
+ +----+ L1 | L3 +----+
+ | H1 |------|------| H3 |
+ +----+ +----+
+
+ A network with three hosts (H1, H2, H3) and three links (L1, L2, L3)
+
+ Figure 1
+
+ 1. Sender side: Consider a situation where host H1 sends media
+ streams to hosts H2 and H3, and L1 is a shared bottleneck. H2
+ and H3 measure the OWD and packet loss and periodically send
+ either this raw data or the calculated summary statistics to H1
+ every T. H1, having this knowledge, can determine the shared
+ bottleneck and accordingly control the send rates.
+
+
+
+Hayes, et al. Experimental [Page 9]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ 2. Receiver side: Consider that H2 is also sending media to H3, and
+ L3 is a shared bottleneck. If H3 sends summary statistics to H1
+ and H2, neither H1 nor H2 alone obtains enough knowledge to
+ detect this shared bottleneck; H3 can, however, determine it by
+ combining the summary statistics related to H1 and H2,
+ respectively.
+
+3.1. SBD Feedback Requirements
+
+ There are three possible scenarios, each with different feedback
+ requirements:
+
+ 1. Both summary statistic calculations and SBD are performed at
+ senders only. When sender-based congestion control is
+ implemented, this method is RECOMMENDED.
+
+ 2. Summary statistics are calculated on the receivers, and SBD is
+ performed at the senders.
+
+ 3. Summary statistic calculations are performed on receivers, and
+ SBD is performed at both senders and receivers (beyond the scope
+ of this document, but allows cooperative detection of
+ bottlenecks).
+
+ All three possibilities are discussed for completeness in this
+ document; however, it is expected that feedback will take the form of
+ scenario 1 and operate in conjunction with sender-based congestion
+ control mechanisms.
+
+3.1.1. Feedback When All the Logic Is Placed at the Sender
+
+ Having the sender calculate the summary statistics and determine the
+ shared bottlenecks based on them has the advantage of placing most of
+ the functionality in one place -- the sender.
+
+ For every packet, the sender requires accurate relative OWD
+ measurements of adequate precision, along with an indication of lost
+ packets (or the proportion of packets lost over an interval). A
+ method to provide such measurement data with the RTP Control Protocol
+ (RTCP) is described in [RTCP-CC-FEEDBACK].
+
+ Sums, var_base_T, and skew_base_T are calculated incrementally as
+ relative OWD measurements are determined from the feedback messages.
+ When the mechanism has received sufficient measurements to cover the
+ base time interval T for all flows, the summary statistics (see
+ Section 3.2) are calculated for that T interval and flows are grouped
+ (see Section 3.3.1). The exact timing of these calculations will
+ depend on the frequency of the feedback message.
+
+
+
+Hayes, et al. Experimental [Page 10]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+3.1.2. Feedback When the Statistics Are Calculated at the Receiver and
+ SBD Is Performed at the Sender
+
+ This scenario minimizes feedback but requires receivers to send
+ selected summary statistics at an agreed-upon regular interval. We
+ envisage the following exchange of information to initialize the
+ system:
+
+ o An initialization message from the sender to the receiver will
+ contain the following information:
+
+ * A list of which key metrics should be collected and relayed
+ back to the sender out of a possibly extensible set (pkt_loss,
+ var_est, skew_est, and freq_est). The grouping algorithm
+ described in this document requires all four of these metrics,
+ and receivers MUST be able to provide them, but future
+ algorithms may be able to exploit other metrics (e.g., metrics
+ based on explicit network signals).
+
+ * The values of T, N, and M, and the necessary resolution and
+ precision of the relayed statistics.
+
+ o A response message from the receiver acknowledges this message
+ with a list of key metrics it supports (subset of the sender's
+ list) and is able to relay back to the sender.
+
+ This initialization exchange may be repeated to finalize the set of
+ metrics that will be used. All agreed-upon metrics need to be
+ supported by all receivers. It is also recommended that an
+ identifier for the SBD algorithm version be included in the
+ initialization message from the sender, so that potential advances in
+ SBD technology can be easily deployed. For reference, the mechanism
+ outlined in this document has the identifier "SBD=01".
+
+ After initialization, the agreed-upon summary statistics are fed back
+ to the sender (nominally every T).
+
+3.1.3. Feedback When Bottlenecks Can Be Determined at Both Senders and
+ Receivers
+
+ This type of mechanism is currently beyond the scope of the SBD
+ algorithm described in this document. It is mentioned here to ensure
+ that sender/receiver cooperative shared bottleneck determination
+ mechanisms that are more advanced remain possible in the future.
+
+ It is envisaged that such a mechanism would be initialized in a
+ manner similar to that described in Section 3.1.2.
+
+
+
+
+Hayes, et al. Experimental [Page 11]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ After initialization, both summary statistics and shared bottleneck
+ determinations should be exchanged, nominally every T.
+
+3.2. Key Metrics and Their Calculation
+
+ Measurements are calculated over a base interval (T) and summarized
+ over N or M such intervals. All summary statistics can be calculated
+ incrementally.
+
+3.2.1. Mean Delay
+
+ The mean delay is not a useful signal for comparisons between flows,
+ since flows may traverse quite different paths and clocks will not
+ necessarily be synchronized. However, it is a base measure for the
+ three summary statistics. The mean delay, E_T(OWD), is the average
+ OWD measured over T.
+
+ To facilitate the other calculations, the last N E_T(OWD) values will
+ need to be stored in a cyclic buffer along with the moving average of
+ E_T(OWD):
+
+ mean_delay = E_M(E_T(OWD)) = sum_M(E_T(OWD)) / M
+
+ where M <= N. Setting M to be less than N allows the mechanism to be
+ more responsive to changes, but potentially at the expense of a
+ higher error rate (see Section 4.1 for a discussion on improving the
+ responsiveness of the mechanism).
+
+3.2.2. Skewness Estimate
+
+ Skewness is difficult to calculate efficiently and accurately.
+ Ideally, it should be calculated over the entire period (M*T) from
+ the mean OWD over that period. However, this would require storing
+ every delay measurement over the period. Instead, an estimate is
+ made over M*T based on a calculation every T using the previous T's
+ calculation of mean_delay.
+
+ The base for the skewness calculation is estimated using a counter
+ initialized every T. It increments for OWD samples below the mean
+ and decrements for OWD above the mean. So, for each OWD sample:
+
+ if (OWD < mean_delay) skew_base_T++
+
+ if (OWD > mean_delay) skew_base_T--
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 12]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ mean_delay does not include the mean of the current T interval to
+ enable it to be calculated iteratively.
+
+ skew_est = sum_MT(skew_base_T) / num_MT(OWD)
+
+ where skew_est is a number between -1 and 1.
+
+ Note: Care must be taken when implementing the comparisons to ensure
+ that rounding does not bias skew_est. It is important that the mean
+ is calculated with a higher precision than the samples.
+
+3.2.3. Variability Estimate
+
+ Mean Absolute Deviation (MAD) is a robust variability measure that
+ copes well with different send rates. It can be implemented in an
+ online manner as follows:
+
+ var_base_T = sum_T(|OWD - E_T(OWD)|)
+
+ where
+
+ |x| is the absolute value of x
+
+ E_T(OWD) is the mean OWD calculated in the previous T
+
+ var_est = MAD_MT = sum_MT(var_base_T) / num_MT(OWD)
+
+3.2.4. Oscillation Estimate
+
+ An estimate of the low-frequency oscillation of the delay signal is
+ calculated by counting and normalizing the significant mean,
+ E_T(OWD), crossings of mean_delay:
+
+ freq_est = number_of_crossings / N
+
+ where we define a significant mean crossing as a crossing that
+ extends p_v * var_est from mean_delay. In our experiments, we
+ have found that p_v = 0.7 is a good value.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 13]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ freq_est is a number between 0 and 1. freq_est can be approximated
+ incrementally as follows:
+
+ o With each new calculation of E_T(OWD), a decision is made as to
+ whether this value of E_T(OWD) significantly crosses the current
+ long-term mean, mean_delay, with respect to the previous
+ significant mean crossing.
+
+ o A cyclic buffer, last_N_crossings, records a 1 if there is a
+ significant mean crossing; otherwise, it records a 0.
+
+ o The counter, number_of_crossings, is incremented when there is a
+ significant mean crossing and decremented when a non-zero value is
+ removed from the last_N_crossings.
+
+ This approximation of freq_est was not used in [Hayes-LCN14], which
+ calculated freq_est every T using the current E_N(E_T(OWD)). Our
+ tests show that this approximation of freq_est yields results that
+ are almost identical to when the full calculation is performed
+ every T.
+
+3.2.5. Packet Loss
+
+ The proportion of packets lost over the period NT is used as a
+ supplementary measure:
+
+ pkt_loss = sum_NT(lost packets) / sum_NT(total packets)
+
+ Note: When pkt_loss is low, it is very variable; however, when
+ pkt_loss is high, it becomes a stable measure for making grouping
+ decisions.
+
+3.3. Flow Grouping
+
+3.3.1. Flow-Grouping Algorithm
+
+ The following grouping algorithm is RECOMMENDED for the use of SBD
+ with coupled congestion control for RTP media [RTP-COUPLED-CC] and is
+ sufficient and efficient for small to moderate numbers of flows. For
+ very large numbers of flows (e.g., hundreds), a more complex
+ clustering algorithm may be substituted.
+
+ Since no single metric is precise enough to group flows (due to
+ noise), the algorithm uses multiple metrics. Each metric offers a
+ different "view" of the bottleneck link characteristics, and used
+ together they enable a more precise grouping of flows than would
+ otherwise be possible.
+
+
+
+
+Hayes, et al. Experimental [Page 14]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ Flows determined to be transiting a bottleneck are successively
+ divided into groups based on freq_est, var_est, skew_est, and
+ pkt_loss.
+
+ The first step is to determine which flows are transiting a
+ bottleneck. This is important, since if a flow is not transiting a
+ bottleneck its delay-based metrics will not describe the bottleneck
+ but will instead describe the "noise" from the rest of the path.
+ Skewness, with the proportion of packet loss as a supplementary
+ measure, is used to do this:
+
+ 1. Grouping will be performed on flows that are inferred to be
+ traversing a bottleneck by:
+
+ skew_est < c_s
+
+ || ( skew_est < c_h & PB ) || pkt_loss > p_l
+
+ The parameter c_s controls how sensitive the mechanism is in
+ detecting a bottleneck. c_s = 0.0 was used in [Hayes-LCN14]. A
+ value of c_s = 0.1 is a little more sensitive, and c_s = -0.1 is
+ a little less sensitive. c_h controls the hysteresis on flows
+ that were grouped as transiting a bottleneck the previous time.
+ If the test result is TRUE, PB=TRUE; otherwise, PB=FALSE.
+
+ These flows (i.e., flows transiting a bottleneck) are then
+ progressively divided into groups based on the freq_est, var_est, and
+ skew_est summary statistics. The process proceeds according to the
+ following steps:
+
+ 2. Group flows whose difference in sorted freq_est is less than a
+ threshold:
+
+ diff(freq_est) < p_f
+
+ 3. Subdivide the groups obtained in step 2 by grouping flows whose
+ difference in sorted E_M(var_est) (highest to lowest) is less
+ than a threshold:
+
+ diff(var_est) < (p_mad * var_est)
+
+ The threshold, (p_mad * var_est), is with respect to the highest
+ value in the difference.
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 15]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ 4. Subdivide the groups obtained in step 3 by grouping flows whose
+ difference in sorted skew_est is less than a threshold:
+
+ diff(skew_est) < p_s
+
+ 5. When packet loss is high enough to be reliable (pkt_loss > p_l),
+ subdivide the groups obtained in step 4 by grouping flows whose
+ difference is less than a threshold:
+
+ diff(pkt_loss) < (p_d * pkt_loss)
+
+ The threshold, (p_d * pkt_loss), is with respect to the highest
+ value in the difference.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 16]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ This procedure involves sorting estimates from highest to lowest. It
+ is simple to implement and is efficient for small numbers of flows
+ (up to 10-20). Figure 2 illustrates this algorithm.
+
+ *********
+ * Flows *
+ ***.**.**
+ / '
+ / '--.
+ / \
+ .---v--. .----v---.
+ 1. Flows traversing | Cong | | UnCong |
+ a bottleneck '-.--.-' '--------'
+ / \
+ / \
+ / \
+ .--v--. v-----.
+ 2. Divide by | g_1 | ... | g_n |
+ freq_est '---.-. '----..
+ / \ / \
+ / '--. v '------.
+ / \ \
+ .----v-. .-v----. .---v--.
+ 3. Divide by | g_1a | ... | g_1z | ... | g_nz |
+ var_est '---.-.' '-----.. '-.-.--'
+ / \ / \ / |
+ / '-----. v v v |
+ / \ |
+ .-v-----. .-v-----. .---v---.
+ 4. Divide by | g_1ai | ... | g_1ax | ... | g_nzx |
+ skew_est '----.-.' '------.. '-.-.---'
+ / \ / \ / |
+ / '--. v v v |
+ / \ |
+ .-----v--. .-v------. .----v---.
+ 5. Divide by | g_1aiA | ... | g_1aiZ | ... | g_nzxZ |
+ pkt_loss '--------' '--------' '--------'
+ (when applicable)
+
+ Simple grouping algorithm
+
+ Figure 2
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 17]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+3.3.2. Using the Flow Group Signal
+
+ Grouping decisions can be made every T from the second T; however,
+ they will not attain their full design accuracy until after the
+ 2*Nth T interval. We recommend that grouping decisions not be made
+ until 2*M T intervals.
+
+ Network conditions, and even the congestion controllers, can cause
+ bottlenecks to fluctuate. A coupled congestion controller MAY decide
+ only to couple groups that remain stable, say grouped together 90% of
+ the time, depending on its objectives. Recommendations concerning
+ this are beyond the scope of this document and will be specific to
+ the coupled congestion controller's objectives.
+
+4. Enhancements to the Basic SBD Algorithm
+
+ The SBD algorithm as specified in Section 3 was found to work well
+ for a broad variety of conditions. The following enhancements to the
+ basic mechanisms have been found to significantly improve the
+ algorithm's performance under some circumstances and SHOULD be
+ implemented. These "tweaks" are described separately to keep the
+ main description succinct.
+
+4.1. Reducing Lag and Improving Responsiveness
+
+ This section describes how to improve the responsiveness of the basic
+ algorithm.
+
+ Measurement-based shared bottleneck detection makes decisions in the
+ present based on what has been measured in the past. This means that
+ there is always a lag in responding to changing conditions. This
+ mechanism is based on summary statistics taken over (N*T) seconds.
+ This mechanism can be made more responsive to changing conditions by:
+
+ 1. Reducing N and/or M, but at the expense of having metrics that
+ are less accurate, and/or
+
+ 2. Exploiting the fact that measurements that are more recent are
+ more valuable than older measurements and weighting them
+ accordingly.
+
+ Although measurements that are more recent are more valuable, older
+ measurements are still needed to gain an accurate estimate of the
+ distribution descriptor we are measuring. Unfortunately, the simple
+ exponentially weighted moving average weights drop off too quickly
+ for our requirements and have an infinite tail. A simple linearly
+ declining weighted moving average also does not provide enough weight
+ to the measurements that are most recent. We propose a piecewise
+
+
+
+Hayes, et al. Experimental [Page 18]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ linear distribution of weights, such that the first section (samples
+ 1:F) is flat as in a simple moving average, and the second section
+ (samples F+1:M) is linearly declining weights to the end of the
+ averaging window. We choose integer weights; this allows incremental
+ calculation without introducing rounding errors.
+
+4.1.1. Improving the Response of the Skewness Estimate
+
+ The weighted moving average for skew_est, based on skew_est as
+ defined in Section 3.2.2, can be calculated as follows:
+
+ skew_est = ((M-F+1)*sum(skew_base_T(1:F))
+
+ + sum([(M-F):1].*skew_base_T(F+1:M)))
+
+ / ((M-F+1)*sum(numsampT(1:F))
+
+ + sum([(M-F):1].*numsampT(F+1:M)))
+
+ where numsampT is an array of the number of OWD samples in each T
+ (i.e., num_T(OWD)), and numsampT(1) is the most recent;
+ skew_base_T(1) is the most recent calculation of skew_base_T; 1:F
+ refers to the integer values 1 through to F, and [(M-F):1] refers to
+ an array of the integer values (M-F) declining through to 1; and ".*"
+ is the array scalar dot product operator.
+
+ To calculate this weighted skew_est incrementally:
+
+ Notation: F_ = flat portion, D_ = declining portion,
+ W_ = weighted component
+
+ Initialize: sum_skewbase = 0, F_skewbase = 0, W_D_skewbase = 0
+
+ skewbase_hist = buffer of length M, initialized to 0
+
+ numsampT = buffer of length M, initialized to 0
+
+ Steps per iteration:
+
+ 1. old_skewbase = skewbase_hist(M)
+
+ 2. old_numsampT = numsampT(M)
+
+ 3. cycle(skewbase_hist)
+
+ 4. cycle(numsampT)
+
+ 5. numsampT(1) = num_T(OWD)
+
+
+
+Hayes, et al. Experimental [Page 19]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ 6. skewbase_hist(1) = skew_base_T
+
+ 7. F_skewbase = F_skewbase + skew_base_T - skewbase_hist(F+1)
+
+ 8. W_D_skewbase = W_D_skewbase + (M-F)*skewbase_hist(F+1)
+ - sum_skewbase
+
+ 9. W_D_numsamp = W_D_numsamp + (M-F)*numsampT(F+1) - sum_numsamp
+ + F_numsamp
+
+ 10. F_numsamp = F_numsamp + numsampT(1) - numsampT(F+1)
+
+ 11. sum_skewbase = sum_skewbase + skewbase_hist(F+1) - old_skewbase
+
+ 12. sum_numsamp = sum_numsamp + numsampT(1) - old_numsampT
+
+ 13. skew_est = ((M-F+1)*F_skewbase + W_D_skewbase) /
+ ((M-F+1)*F_numsamp+W_D_numsamp)
+
+ where cycle(...) refers to the operation on a cyclic buffer where the
+ start of the buffer is now the next element in the buffer.
+
+4.1.2. Improving the Response of the Variability Estimate
+
+ Similarly, the weighted moving average for var_est can be calculated
+ as follows:
+
+ var_est = ((M-F+1)*sum(var_base_T(1:F))
+
+ + sum([(M-F):1].*var_base_T(F+1:M)))
+
+ / ((M-F+1)*sum(numsampT(1:F))
+
+ + sum([(M-F):1].*numsampT(F+1:M)))
+
+ where numsampT is an array of the number of OWD samples in each T
+ (i.e., num_T(OWD)), and numsampT(1) is the most recent;
+ skew_base_T(1) is the most recent calculation of skew_base_T; 1:F
+ refers to the integer values 1 through to F, and [(M-F):1] refers to
+ an array of the integer values (M-F) declining through to 1; and ".*"
+ is the array scalar dot product operator. When removing oscillation
+ noise (see Section 4.2), this calculation must be adjusted to allow
+ for invalid var_base_T records.
+
+ var_est can be calculated incrementally in the same way as skew_est
+ as shown in Section 4.1.1. However, note that the buffer numsampT is
+ used for both calculations, so the operations on it should not be
+ repeated.
+
+
+
+Hayes, et al. Experimental [Page 20]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+4.2. Removing Oscillation Noise
+
+ When a path has no bottleneck, var_est will be very small and the
+ recorded significant mean crossings will be the result of path noise.
+ Thus, up to N-1 meaningless mean crossings can be a source of error
+ at the point where a link becomes a bottleneck and flows traversing
+ it begin to be grouped.
+
+ To remove this source of noise from freq_est:
+
+ 1. Set the current var_base_T = NaN (a value representing an invalid
+ record, i.e., Not a Number) for flows that are deemed to not be
+ transiting a bottleneck by the first grouping test that is based
+ on skew_est (see Section 3.3.1).
+
+ 2. Then, var_est = sum_MT(var_base_T != NaN) / num_MT(OWD).
+
+ 3. For freq_est, only record a significant mean crossing if a given
+ flow is deemed to be transiting a bottleneck.
+
+ These three changes can help to remove the non-bottleneck noise from
+ freq_est.
+
+5. Measuring OWD
+
+ This section discusses the OWD measurements required for this
+ algorithm to detect shared bottlenecks.
+
+ The SBD mechanism described in this document relies on differences
+ between OWD measurements to avoid the practical problems with
+ measuring absolute OWD (see [Hayes-LCN14], Section III.C). Since all
+ summary statistics are relative to the mean OWD and sender/receiver
+ clock offsets should be approximately constant over the measurement
+ periods, the offset is subtracted out in the calculation.
+
+5.1. Timestamp Resolution
+
+ The SBD mechanism requires timing information precise enough to be
+ able to make comparisons. As a rule of thumb, the time resolution
+ should be less than one hundredth of a typical path's range of
+ delays. In general, the coarser the time resolution, the more care
+ that needs to be taken to ensure that rounding errors do not bias the
+ skewness calculation. Frequent timing information in millisecond
+ resolution as described by [RTCP-CC-FEEDBACK] should be sufficient
+ for the sender to calculate relative OWD.
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 21]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+5.2. Clock Skew
+
+ Generally, sender and receiver clock skew will be too small to cause
+ significant errors in the estimators. skew_est and freq_est are the
+ most sensitive to this type of noise due to their use of a mean OWD
+ calculated over a longer interval. In circumstances where clock skew
+ is high, basing skew_est only on the previous T's mean and ignoring
+ freq_est provide a noisier but reliable signal.
+
+ A more sophisticated method is to estimate the effect the clock skew
+ is having on the summary statistics and then adjust statistics
+ accordingly. There are a number of techniques in the literature,
+ including [Zhang-Infocom02].
+
+6. Expected Feedback from Experiments
+
+ The algorithm described in this memo has so far been evaluated using
+ simulations and small-scale experiments. Real network tests using
+ RTP Media Congestion Avoidance Techniques (RMCAT) congestion control
+ algorithms will help confirm the default parameter choice. For
+ example, the time interval T may need to be made longer if the packet
+ rate is very low. Implementers and testers are invited to document
+ their findings in an Internet-Draft.
+
+7. IANA Considerations
+
+ This document has no IANA actions.
+
+8. Security Considerations
+
+ The security considerations of RFC 3550 [RFC3550], RFC 4585
+ [RFC4585], and RFC 5124 [RFC5124] are expected to apply.
+
+ Non-authenticated RTCP packets carrying OWD measurements, shared
+ bottleneck indications, and/or summary statistics could allow
+ attackers to alter the bottleneck-sharing characteristics for private
+ gain or disruption of other parties' communication. When using SBD
+ for coupled congestion control as described in [RTP-COUPLED-CC], the
+ security considerations of [RTP-COUPLED-CC] apply.
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 22]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+9. References
+
+9.1. Normative References
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119,
+ DOI 10.17487/RFC2119, March 1997,
+ <https://www.rfc-editor.org/info/rfc2119>.
+
+ [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in
+ RFC 2119 Key Words", BCP 14, RFC 8174,
+ DOI 10.17487/RFC8174, May 2017,
+ <https://www.rfc-editor.org/info/rfc8174>.
+
+9.2. Informative References
+
+ [Hayes-LCN14]
+ Hayes, D., Ferlin, S., and M. Welzl, "Practical Passive
+ Shared Bottleneck Detection using Shape Summary
+ Statistics", Proc. IEEE Local Computer Networks (LCN),
+ pp. 150-158, DOI 10.1109/LCN.2014.6925767, September 2014,
+ <http://heim.ifi.uio.no/davihay/
+ hayes14__pract_passiv_shared_bottl_detec-abstract.html>.
+
+ [RFC3550] Schulzrinne, H., Casner, S., Frederick, R., and V.
+ Jacobson, "RTP: A Transport Protocol for Real-Time
+ Applications", STD 64, RFC 3550, DOI 10.17487/RFC3550,
+ July 2003, <https://www.rfc-editor.org/info/rfc3550>.
+
+ [RFC4585] Ott, J., Wenger, S., Sato, N., Burmeister, C., and J. Rey,
+ "Extended RTP Profile for Real-time Transport Control
+ Protocol (RTCP)-Based Feedback (RTP/AVPF)", RFC 4585,
+ DOI 10.17487/RFC4585, July 2006,
+ <https://www.rfc-editor.org/info/rfc4585>.
+
+ [RFC5124] Ott, J. and E. Carrara, "Extended Secure RTP Profile for
+ Real-time Transport Control Protocol (RTCP)-Based Feedback
+ (RTP/SAVPF)", RFC 5124, DOI 10.17487/RFC5124,
+ February 2008, <https://www.rfc-editor.org/info/rfc5124>.
+
+ [RFC6817] Shalunov, S., Hazel, G., Iyengar, J., and M. Kuehlewind,
+ "Low Extra Delay Background Transport (LEDBAT)", RFC 6817,
+ DOI 10.17487/RFC6817, December 2012,
+ <https://www.rfc-editor.org/info/rfc6817>.
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 23]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+ [RFC7679] Almes, G., Kalidindi, S., Zekauskas, M., and A. Morton,
+ Ed., "A One-Way Delay Metric for IP Performance Metrics
+ (IPPM)", STD 81, RFC 7679, DOI 10.17487/RFC7679,
+ January 2016, <https://www.rfc-editor.org/info/rfc7679>.
+
+ [RFC7680] Almes, G., Kalidindi, S., Zekauskas, M., and A. Morton,
+ Ed., "A One-Way Loss Metric for IP Performance Metrics
+ (IPPM)", STD 82, RFC 7680, DOI 10.17487/RFC7680,
+ January 2016, <https://www.rfc-editor.org/info/rfc7680>.
+
+ [RTCP-CC-FEEDBACK]
+ Sarker, Z., Perkins, C., Singh, V., and M. Ramalho,
+ "RTP Control Protocol (RTCP) Feedback for Congestion
+ Control", Work in Progress, draft-ietf-avtcore-cc-
+ feedback-message-01, March 2018.
+
+ [RTP-COUPLED-CC]
+ Islam, S., Welzl, M., and S. Gjessing, "Coupled congestion
+ control for RTP media", Work in Progress, draft-ietf-
+ rmcat-coupled-cc-07, September 2017.
+
+ [Zhang-Infocom02]
+ Zhang, L., Liu, Z., and H. Xia, "Clock synchronization
+ algorithms for network measurements", Proc. IEEE
+ International Conference on Computer Communications
+ (INFOCOM), pp. 160-169, DOI 10.1109/INFCOM.2002.1019257,
+ September 2002.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 24]
+
+RFC 8382 SBD for CCC for RTP Media June 2018
+
+
+Acknowledgments
+
+ This work was partially funded by the European Community under its
+ Seventh Framework Programme through the Reducing Internet Transport
+ Latency (RITE) project (ICT-317700). The views expressed are solely
+ those of the authors.
+
+Authors' Addresses
+
+ David Hayes (editor)
+ Simula Research Laboratory
+ P.O. Box 134
+ Lysaker 1325
+ Norway
+
+ Email: davidh@simula.no
+
+
+ Simone Ferlin
+ Simula Research Laboratory
+ P.O. Box 134
+ Lysaker 1325
+ Norway
+
+ Email: simone@ferlin.io
+
+
+ Michael Welzl
+ University of Oslo
+ P.O. Box 1080 Blindern
+ Oslo N-0316
+ Norway
+
+ Email: michawe@ifi.uio.no
+
+
+ Kristian Hiorth
+ University of Oslo
+ P.O. Box 1080 Blindern
+ Oslo N-0316
+ Norway
+
+ Email: kristahi@ifi.uio.no
+
+
+
+
+
+
+
+
+Hayes, et al. Experimental [Page 25]
+