draft-ietf-aqm-docsis-pie-00.txt   draft-ietf-aqm-docsis-pie-01.txt 
Active Queue Management and Packet Scheduling (aqm) G. White Active Queue Management and Packet Scheduling (aqm) G. White
Internet-Draft CableLabs Internet-Draft CableLabs
Intended status: Informational R. Pan Intended status: Informational R. Pan
Expires: September 28, 2015 Cisco Systems Expires: April 1, 2016 Cisco Systems
March 27, 2015 September 29, 2015
A PIE-Based AQM for DOCSIS Cable Modems A PIE-Based AQM for DOCSIS Cable Modems
draft-ietf-aqm-docsis-pie-00 draft-ietf-aqm-docsis-pie-01
Abstract Abstract
DOCSIS cable modems provide broadband Internet access to over one Cable modems based on the DOCSIS(R) specification provide broadband
hundred million users worldwide. They are commonly positioned at the Internet access to over one hundred million users worldwide. In some
head of the bottleneck link for traffic in the upstream direction cases, the cable modem connection is the bottleneck (lowest speed)
(from the customer), and as a result, the impact of buffering and link between the customer and the Internet. As a result, the impact
bufferbloat in the cable modem can have a significant effect on user of buffering and bufferbloat in the cable modem can have a
experience. The CableLabs DOCSIS 3.1 specification includes significant effect on user experience. The CableLabs DOCSIS 3.1
requirements for cable modems to support an Active Queue Management specification introduces requirements for cable modems to support an
(AQM) algorithm that is intended to alleviate the impact that Active Queue Management (AQM) algorithm that is intended to alleviate
buffering has on latency sensitive traffic, while preserving bulk the impact that buffering has on latency sensitive traffic, while
throughput performance. In addition, the CableLabs DOCSIS 3.0 preserving bulk throughput performance. In addition, the CableLabs
specifications have also been amended to contain similar DOCSIS 3.0 specifications have also been amended to contain similar
requirements. requirements. This document describes the requirements on Active
Queue Management that apply to DOCSIS equipment, including a
description of the "DOCSIS-PIE" algorithm that is required on DOCSIS
3.1 cable modems.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 28, 2015. This Internet-Draft will expire on April 1, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Overview of DOCSIS AQM Requirements . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. The DOCSIS MAC Layer and Service Flows . . . . . . . . . . . 3 2. Overview of DOCSIS AQM Requirements . . . . . . . . . . . . . 3
3. DOCSIS-PIE vs. PIE . . . . . . . . . . . . . . . . . . . . . 4 3. The DOCSIS MAC Layer and Service Flows . . . . . . . . . . . 3
3.1. Latency Target . . . . . . . . . . . . . . . . . . . . . 4 4. DOCSIS-PIE vs. PIE . . . . . . . . . . . . . . . . . . . . . 5
3.2. Departure rate estimation . . . . . . . . . . . . . . . . 5 4.1. Latency Target . . . . . . . . . . . . . . . . . . . . . 5
3.3. Expanded auto-tuning range . . . . . . . . . . . . . . . 6 4.2. Departure rate estimation . . . . . . . . . . . . . . . . 5
3.4. Trigger for exponential decay . . . . . . . . . . . . . . 6 4.3. Enhanced burst protection . . . . . . . . . . . . . . . . 6
4. Implementation Guidance . . . . . . . . . . . . . . . . . . . 6 4.4. Expanded auto-tuning range . . . . . . . . . . . . . . . 7
5. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.5. Trigger for exponential decay . . . . . . . . . . . . . . 7
Appendix A. DOCSIS-PIE Algorithm definition . . . . . . . . . . 7 4.6. Drop probability scaling . . . . . . . . . . . . . . . . 7
A.1. DOCSIS-PIE AQM Constants and Variables . . . . . . . . . 7 4.7. Support for explicit congestion notification . . . . . . 8
A.1.1. Configuration parameters . . . . . . . . . . . . . . 7 5. Implementation Guidance . . . . . . . . . . . . . . . . . . . 8
A.1.2. Constant values . . . . . . . . . . . . . . . . . . . 8 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
A.1.3. Variables . . . . . . . . . . . . . . . . . . . . . . 8 Appendix A. DOCSIS-PIE Algorithm definition . . . . . . . . . . 9
A.1.4. Public/system functions: . . . . . . . . . . . . . . 9 A.1. DOCSIS-PIE AQM Constants and Variables . . . . . . . . . 9
A.2. DOCSIS-PIE AQM Control Path . . . . . . . . . . . . . . . 9 A.1.1. Configuration parameters . . . . . . . . . . . . . . 10
A.3. DOCSIS-PIE AQM Data Path . . . . . . . . . . . . . . . . 11 A.1.2. Constant values . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 A.1.3. Variables . . . . . . . . . . . . . . . . . . . . . . 10
A.1.4. Public/system functions: . . . . . . . . . . . . . . 11
A.2. DOCSIS-PIE AQM Control Path . . . . . . . . . . . . . . . 11
A.3. DOCSIS-PIE AQM Data Path . . . . . . . . . . . . . . . . 13
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15
1. Overview of DOCSIS AQM Requirements 1. Introduction
A recent resurgence of interest in Active Queue Management, arising
from a recognition of the inadequacies of drop tail queuing in the
presence of loss-based congestion control algorithms, has resulted in
the development of new algorithms that appear to provide very good
congestion feedback to current TCP algorithms, while also having
operational simplicity and low complexity. One of these algorithms
has been selected as a requirement for cable modems built according
to the DOCSIS 3.1 specification [DOCSIS_3.1]. The Data Over Cable
Service Interface Specifications (DOCSIS) define the broadband
technology deployed worldwide for Ethernet and IP service over hybrid
fiber-coaxial cable systems. The most recent revision of the DOCSIS
technology, version 3.1, was published in October 2013 and provides
support for up to 10 Gbps downstream (toward the customer) and 1 Gbps
upstream (from the customer) capacity over existing cable networks.
Previous versions of the DOCSIS technology did not contain
requirements for AQM. This document outlines the high-level AQM
requirements for DOCSIS systems, discusses some of the salient
features of the DOCSIS MAC layer, and describes the DOCSIS-PIE
algorithm - largely by comparing it to its progenitor, the
[I-D.ietf-aqm-pie] algorithm.
2. Overview of DOCSIS AQM Requirements
CableLabs' DOCSIS 3.1 specification [DOCSIS_3.1] mandates that cable CableLabs' DOCSIS 3.1 specification [DOCSIS_3.1] mandates that cable
modems implement a specific variant of the Proportional Integral modems implement a specific variant of the Proportional Integral
controller Enhanced (PIE) [I-D.ietf-aqm-pie] active queue management controller Enhanced (PIE) [I-D.ietf-aqm-pie] active queue management
algorithm. This specific variant is provided for reference in algorithm. This specific variant is provided for reference in
Appendix A. CableLabs' DOCSIS 3.0 specification [DOCSIS_3.0] has Appendix A, and simulation results comparing it to drop tail queuing
been amended to recommend that cable modems implement the same and other AQM options are given in [CommMag] and [DOCSIS-AQM]. In
algorithm. Both specifications allow that cable modems can addition, CableLabs' DOCSIS 3.0 specification [DOCSIS_3.0] has been
optionally implement additional algorithms, that can then be selected amended to recommend that cable modems implement the same algorithm.
for use by the operator via the modem's configuration file. Both specifications allow that cable modems can optionally implement
additional algorithms, that can then be selected for use by the
operator via the modem's configuration file.
These requirements on the cable modem apply to upstream These requirements on the cable modem apply to upstream transmissions
transmissions. (i.e. from the customer to the Internet).
Both specifications also include requirements (mandatory in DOCSIS Both specifications also include requirements (mandatory in DOCSIS
3.1 and recommended in DOCSIS 3.0) that the Cable Modem Termination 3.1 and recommended in DOCSIS 3.0) that the Cable Modem Termination
System (CMTS) implement active queue management for downstream System (CMTS) implement active queue management for downstream
traffic, however no specific algorithm is defined for downstream use. traffic, however no specific algorithm is defined for downstream use.
2. The DOCSIS MAC Layer and Service Flows 3. The DOCSIS MAC Layer and Service Flows
The DOCSIS Media Access Control (sub-)layer provides tools for The DOCSIS Media Access Control (sub-)layer provides tools for
configuring differentiated Quality of Service for different configuring differentiated Quality of Service for different
applications by the use of Packet Classifiers and Service Flows. applications by the use of Packet Classifiers and Service Flows.
Each cable modem can be configured with multiple Packet Classifiers
and Service Flows. The maximum number of such entities that a cable
modem supports is an implementation decision for the manufacturer,
but modems typically support 16 or 32 Service Flows and at least that
many Packet Classifiers.
Each Service Flow has an associated Quality of Service (QoS) Each Service Flow has an associated Quality of Service (QoS)
parameter set that defines the treatment of the packets that traverse parameter set that defines the treatment of the packets that traverse
the Service Flow. These parameters include (for example) Minimum the Service Flow. These parameters include (for example) Minimum
Reserved Traffic Rate, Maximum Sustained Traffic Rate, Peak Traffic Reserved Traffic Rate, Maximum Sustained Traffic Rate, Peak Traffic
Rate, Maximum Traffic Burst, Traffic Priority. Each upstream Service Rate, Maximum Traffic Burst, and Traffic Priority. Each upstream
Flow corresponds to a queue in the cable modem, and each downstream Service Flow corresponds to a queue in the cable modem, and each
Service Flow corresponds to a queue in the CMTS. The DOCSIS AQM downstream Service Flow corresponds to a queue in the CMTS. The
requirements mandate that the CM and CMTS implement the AQM algorithm DOCSIS AQM requirements mandate that the CM and CMTS implement the
(and allow it to be disabled if need be) on each Service Flow queue AQM algorithm (and allow it to be disabled if need be) on each
independently. Service Flow queue independently.
Packet Classifiers can match packets based upon several fields in the Packet Classifiers can match packets based upon several fields in the
packet/frame headers including the Ethernet header, IP header, and packet/frame headers including the Ethernet header, IP header, and
TCP/UDP header. Matched packets are then queued in the associated TCP/UDP header. Matched packets are then queued in the associated
Service Flow queue. Service Flow queue.
Each cable modem can be configured with multiple Packet Classifiers
and Service Flows. The maximum number of such entities that a cable
modem supports is an implementation decision for the manufacturer,
but modems typically support 16 or 32 upstream Service Flows and at
least that many Packet Classifiers. Similarly the CMTS supports
multiple downstream Service Flows and multiple Packet Classifiers per
cable modem.
It is typical that upstream and downstream Service Flows used for It is typical that upstream and downstream Service Flows used for
broadband Internet access are configured with a Maximum Sustained broadband Internet access are configured with a Maximum Sustained
Traffic Rate. This QoS parameter rate-shapes the traffic onto the Traffic Rate. This QoS parameter rate-shapes the traffic onto the
DOCSIS link, and is the main parameter that defines the service DOCSIS link, and is the main parameter that defines the service
offering. Additionally, it is common that upstream and downstream offering. Additionally, it is common that upstream and downstream
Service Flows are configured with a Maximum Traffic Burst and a Peak Service Flows are configured with a Maximum Traffic Burst and a Peak
Traffic Rate. These parameters allow the service to burst at a Traffic Rate. These parameters allow the service to burst at a
higher (sometimes significantly higher) rate than is defined in the higher (sometimes significantly higher) rate than is defined in the
Maximum Sustained Traffic Rate for the amount of bytes configured in Maximum Sustained Traffic Rate for the amount of bytes configured in
Maximum Traffic Burst, as long as the long-term average data rate Maximum Traffic Burst, as long as the long-term average data rate
skipping to change at page 4, line 23 skipping to change at page 5, line 14
The result of this configuration is that the link rate available to The result of this configuration is that the link rate available to
the Service Flow varies based on the pattern of load. If the load the Service Flow varies based on the pattern of load. If the load
that the Service Flow places on the link is less than the Maximum that the Service Flow places on the link is less than the Maximum
Sustained Traffic Rate, the Service Flow "earns" credit that it can Sustained Traffic Rate, the Service Flow "earns" credit that it can
then use (should the load increase) to burst at the Peak Traffic then use (should the load increase) to burst at the Peak Traffic
Rate. This dynamic is important since these rate changes Rate. This dynamic is important since these rate changes
(particularly the decrease in data rate once the traffic burst credit (particularly the decrease in data rate once the traffic burst credit
is exhausted) can induce a step increase in buffering latency. is exhausted) can induce a step increase in buffering latency.
3. DOCSIS-PIE vs. PIE 4. DOCSIS-PIE vs. PIE
There are a number of differences between the version of the PIE There are a number of differences between the version of the PIE
algorithm that is mandated for cable modems in the DOCSIS algorithm that is mandated for cable modems in the DOCSIS
specifications and the version described in [I-D.ietf-aqm-pie]. specifications and the version described in [I-D.ietf-aqm-pie].
These differences are described in the following subsections.
o 10 ms default latency target, configurable per service flow 4.1. Latency Target
o departure rate estimation
o expanded auto-tuning range
o trigger for exponential decay
3.1. Latency Target
The latency target (aka delay reference) is a key parameter that The latency target (aka delay reference) is a key parameter that
affects, among other things, the tradeoff in performance between affects, among other things, the tradeoff in performance between
latency-sensitive applications and bulk TCP applications. Via latency-sensitive applications and bulk TCP applications. Via
simulation studies, a value of 10ms was identified as providing a simulation studies, a value of 10ms was identified as providing a
good balance of performance. However, it is recognized that there good balance of performance. However, it is recognized that there
may be service offerings for which this value doesn't provide the may be service offerings for which this value doesn't provide the
best performance balance. As a result, this is provided as a best performance balance. As a result, this is provided as a
configuration parameter that the operator can set independently on configuration parameter that the operator can set independently on
each upstream service flow. If not explicitly set by the operator, each upstream service flow. If not explicitly set by the operator,
the modem will use 10 ms as the default value. the modem will use 10 ms as the default value.
3.2. Departure rate estimation 4.2. Departure rate estimation
The PIE algorithm utilizes a departure rate estimator to track The PIE algorithm utilizes a departure rate estimator to track
fluctuations in the egress rate for the queue and to generate a fluctuations in the egress rate for the queue and to generate a
smoothed estimate of this rate for use in the drop probability smoothed estimate of this rate for use in the drop probability
calculation. This estimator may be well suited to many link calculation. This estimator may be well suited to many link
technologies, but is not ideal for DOCSIS upstream links for a number technologies, but is not ideal for DOCSIS upstream links for a number
of reasons. of reasons.
First, the bursty nature of the upstream transmissions, in which the First, the bursty nature of the upstream transmissions, in which the
queue drains at line rate (up to ~100 Mbps for DOCSIS 3.0 and ~1 Gbps queue drains at line rate (up to ~100 Mbps for DOCSIS 3.0 and ~1 Gbps
skipping to change at page 5, line 36 skipping to change at page 6, line 16
can result in some further inaccuracy. In typical conditions, the can result in some further inaccuracy. In typical conditions, the
request-grant mechanism can add between ~4 ms and ~8 ms of latency to request-grant mechanism can add between ~4 ms and ~8 ms of latency to
the forwarding of upstream traffic. Within that range, the amount of the forwarding of upstream traffic. Within that range, the amount of
additional latency that affects any individual data burst is additional latency that affects any individual data burst is
effectively random, being influenced by the arrival time of the burst effectively random, being influenced by the arrival time of the burst
relative to the next request transmit opportunity, among other relative to the next request transmit opportunity, among other
factors. factors.
Third, in the significant majority of cases, the departure rate, Third, in the significant majority of cases, the departure rate,
while variable, is controlled by the modem itself via the pair of while variable, is controlled by the modem itself via the pair of
token bucket rate shaping equations described in Section 2. token bucket rate shaping equations described in Section 3.
Together, these two equations enforce a maximum sustained traffic Together, these two equations enforce a maximum sustained traffic
rate, a peak traffic rate, and a maximum traffic burst size for the rate, a peak traffic rate, and a maximum traffic burst size for the
modem's requested bandwidth. The implication of this is that the modem's requested bandwidth. The implication of this is that the
modem, in the significant majority of cases, will know precisely what modem, in the significant majority of cases, will know precisely what
the departure rate will be, and can predict exactly when transitions the departure rate will be, and can predict exactly when transitions
between peak rate and maximum sustained traffic rate will occur. between peak rate and maximum sustained traffic rate will occur.
Compare this to the PIE estimator, which would be simply reacting to Compare this to the PIE estimator, which would be simply reacting to
(and smoothing its estimate of) those rate transitions after the (and smoothing its estimate of) those rate transitions after the
fact. fact.
skipping to change at page 6, line 10 skipping to change at page 6, line 39
predicted queuing delay with a minimum of computations. Furthermore, predicted queuing delay with a minimum of computations. Furthermore,
these computations only need to be run every drop probability update these computations only need to be run every drop probability update
interval, as opposed to the PIE estimator, which runs a similar interval, as opposed to the PIE estimator, which runs a similar
number of computations on each packet dequeue event. number of computations on each packet dequeue event.
For these reasons, the DOCSIS-PIE algorithm utilizes the For these reasons, the DOCSIS-PIE algorithm utilizes the
configuration and state of the dual token bucket traffic shaper to configuration and state of the dual token bucket traffic shaper to
translate queue depth into predicted queuing delay, rather than translate queue depth into predicted queuing delay, rather than
implementing the departure rate estimator defined in PIE. implementing the departure rate estimator defined in PIE.
3.3. Expanded auto-tuning range 4.3. Enhanced burst protection
The PIE [I-D.ietf-aqm-pie] algorithm has two states, INACTIVE and
ACTIVE. During the INACTIVE state, AQM packet drops are suppressed.
The algorithm transitions to the ACTIVE state when the queue exceeds
1/3 of the buffer size. Upon transition to the ACTIVE state, PIE
includes a burst protection feature in which the AQM packet drops are
suppressed for the first 150ms. Since DOCSIS-PIE is predominantly
deployed on consumer broadband connections, a more sophisticated
burst protection was developed in order to provide better performance
in the presence of a single TCP session.
Where the PIE algorithm has two states, DOCSIS-PIE has three. The
INACTIVE and ACTIVE states in DOCSIS-PIE are identical to those
states in PIE. The QUIESCENT state is a transitional state between
INACTIVE and ACTIVE. The DOCSIS-PIE algorithm transitions from
INACTIVE to QUIESCENT when the queue exceeds 1/3 of the buffer size.
In the QUIESCENT state, packet drops are immediately enabled, and
upon the first packet drop, the algorithm transitions to the ACTIVE
state (where drop probability is reset to zero for the 150ms duration
of the burst protection as in PIE). From the ACTIVE state, the
algorithm transitions to QUIESCENT if the drop_probability has
decayed to zero and the queuing latency has been less than half of
the LATENCY_TARGET for two update intervals. The algorithm then
fully resets to the INACTIVE state if this "quiet" condition exists
for the duration of the BURST_RESET_TIMEOUT (1 second). One end
result of the addition of the QUIESCENT state is that a single packet
drop can occur relatively early on during an initial burst, whereas
all drops would be suppressed for at least 150ms of the burst
duration in PIE. The other end result is that if traffic stops and
then resumes within 1 second, DOCSIS_PIE can directly drop a single
packet and then re-enter burst protection, whereas PIE would require
that the buffer exceed 1/3 full.
4.4. Expanded auto-tuning range
The PIE algorithm scales the PI coefficients based on the current The PIE algorithm scales the PI coefficients based on the current
drop probability. The DOCSIS-PIE algorithm extends this scaling to drop probability. The DOCSIS-PIE algorithm extends this scaling to
drop probabilities below 1e-4. drop probabilities below 1e-4.
3.4. Trigger for exponential decay 4.5. Trigger for exponential decay
The PIE algorithm includes a mechanism by which the drop probability The PIE algorithm includes a mechanism by which the drop probability
is allowed to decay exponentially (rather than linearly) when it is is allowed to decay exponentially (rather than linearly) when it is
detected that the buffer is empty. In the DOCSIS case, recently detected that the buffer is empty. In the DOCSIS case, recently
arrived packets may reside in buffer due to the request-grant latency arrived packets may reside in buffer due to the request-grant latency
even if the link is effectively idle. As a result, the buffer may even if the link is effectively idle. As a result, the buffer may
not be identically empty in the situations for which the exponential not be identically empty in the situations for which the exponential
decay is intended. To compensate for this, we trigger exponential decay is intended. To compensate for this, we trigger exponential
decay when the buffer occupancy is less than 5ms * Peak Traffic Rate. decay when the buffer occupancy is less than 5ms * Peak Traffic Rate.
4. Implementation Guidance 4.6. Drop probability scaling
The DOCSIS-PIE algorithm scales the calculated drop probability based
on the ratio of the packet size to a constant value of 1024 bytes
(representing approximate average packet size). While [RFC7567] in
general recommends against this type of scaling, we note that DOCSIS-
PIE is expected to predominantly be used to manage upstream queues in
residential broadband deployments, where we believe the benefits
outweigh the disadvantages. As a safeguard to prevent a flood of
small packets from starving flows that use larger packets, DOCSIS-PIE
limits the scaled probability to a defined maximum value of 0.85.
4.7. Support for explicit congestion notification
DOCSIS-PIE does not include support for explicit congestion
notification. Cable modems are essentially IEEE 802.1d Ethernet
bridges and so are not designed to modify IP header fields.
Additionally, the packet processing pipeline in a cable modem is
commonly implemented in hardware. As a result, introducing support
for ECN would have engendered a more significant redesign of cable
modem data paths, and implementations would have been difficult or
impossible to modify in the future. At the time of the development
of DOCSIS-PIE, which coincided with the development of modem chip
designs, the benefits of ECN marking relative to packet drop were
considered to be relatively minor, there was considerable discussion
about differential treatment of ECN capable packets in the AQM drop/
mark decision, and there were some initial suggestions that a new ECN
approach was needed. Due to this uncertainty, we chose to not
include support for ECN.
5. Implementation Guidance
The AQM space is an evolving one, and it is expected that continued The AQM space is an evolving one, and it is expected that continued
research in this field may in the future result in improved research in this field may in the future result in improved
algorithms. algorithms.
As part of defining the DOCSIS-PIE algorithm, we split the pseudocode As part of defining the DOCSIS-PIE algorithm, we split the pseudocode
definition into two components, a "data path" component and a definition into two components, a "data path" component and a
"control path" component. The control path component contains the "control path" component. The control path component contains the
packet drop probability update functionality, whereas the data path packet drop probability update functionality, whereas the data path
component contains the per-packet operations, including the drop component contains the per-packet operations, including the drop
skipping to change at page 7, line 5 skipping to change at page 8, line 47
may be done in hardware, particularly functions that handle packet- may be done in hardware, particularly functions that handle packet-
processing. processing.
While the DOCSIS specifications don't mandate the internal While the DOCSIS specifications don't mandate the internal
implementation details of the cable modem, modem implementers are implementation details of the cable modem, modem implementers are
strongly advised against implementing the control path functionality strongly advised against implementing the control path functionality
in hardware. The intent of this advice is to retain the possibility in hardware. The intent of this advice is to retain the possibility
that future improvements in AQM algorithms can be accommodated via that future improvements in AQM algorithms can be accommodated via
software updates to deployed devices. software updates to deployed devices.
5. References 6. References
[CommMag] White, G., "Active queue management in DOCSIS 3.1
networks", IEEE Communications Magazine vol.53, no.3,
pp.126-132, March 2015.
[DOCSIS-AQM]
White, G., "Active Queue Management in DOCSIS 3.x Cable
Modems", May 2014, <http://www.cablelabs.com/wp-
content/uploads/2014/06/DOCSIS-AQM_May2014.pdf>.
[DOCSIS_3.0] [DOCSIS_3.0]
CableLabs, "DOCSIS 3.0 MAC and Upper Layer Protocols CableLabs, "DOCSIS 3.0 MAC and Upper Layer Protocols
Specification", November 2013, <http://www.cablelabs.com/ Specification", November 2013, <http://www.cablelabs.com/
wp-content/uploads/specdocs/ wp-content/uploads/specdocs/
CM-SP-MULPIv3.0-I23-131120.pdf>. CM-SP-MULPIv3.0-I23-131120.pdf>.
[DOCSIS_3.1] [DOCSIS_3.1]
CableLabs, "DOCSIS 3.1 MAC and Upper Layer Protocols CableLabs, "DOCSIS 3.1 MAC and Upper Layer Protocols
Specification", October 2013, <http://www.cablelabs.com/ Specification", October 2013, <http://www.cablelabs.com/
wp-content/uploads/specdocs/ wp-content/uploads/specdocs/
CM-SP-MULPIv3.1-I01-131029.pdf>. CM-SP-MULPIv3.1-I01-131029.pdf>.
[I-D.ietf-aqm-pie] [I-D.ietf-aqm-pie]
Pan, R., Natarajan, P., Baker, F., and G. White, "PIE: A Pan, R., Natarajan, P., Baker, F., and G. White, "PIE: A
Lightweight Control Scheme To Address the Bufferbloat Lightweight Control Scheme To Address the Bufferbloat
Problem", draft-ietf-aqm-pie-00 (work in progress), Problem", draft-ietf-aqm-pie-01 (work in progress), March
October 2014. 2015.
[RFC7567] Baker, F., Ed. and G. Fairhurst, Ed., "IETF
Recommendations Regarding Active Queue Management", BCP
197, RFC 7567, DOI 10.17487/RFC7567, July 2015,
<http://www.rfc-editor.org/info/rfc7567>.
Appendix A. DOCSIS-PIE Algorithm definition Appendix A. DOCSIS-PIE Algorithm definition
PIE defines two functions organized here into two design blocks: PIE defines two functions organized here into two design blocks:
1. Control path block, a periodically running algorithm that 1. Control path block, a periodically running algorithm that
calculates a drop probability based on the estimated queuing calculates a drop probability based on the estimated queuing
latency and queuing latency trend. latency and queuing latency trend.
2. Data path block, a function that occurs on each packet enqueue: 2. Data path block, a function that occurs on each packet enqueue:
skipping to change at page 8, line 11 skipping to change at page 10, line 23
o BUFFER_SIZE. The size (in bytes) of the buffer for this Service o BUFFER_SIZE. The size (in bytes) of the buffer for this Service
Flow. Flow.
A.1.2. Constant values A.1.2. Constant values
o A=0.25, B=2.5. Weights in the drop probability calculation o A=0.25, B=2.5. Weights in the drop probability calculation
o INTERVAL=16 ms. Update interval for drop probability. o INTERVAL=16 ms. Update interval for drop probability.
o DELAY_HIGH=200 ms.
o BURST_RESET_TIMEOUT = 1 s. o BURST_RESET_TIMEOUT = 1 s.
o MAX_BURST = 142 ms (150 ms-8 ms(update error)) o MAX_BURST = 142 ms (150 ms-8 ms(update error))
o MEAN_PKTSIZE = 1024 bytes o MEAN_PKTSIZE = 1024 bytes
o MIN_PKTSIZE = 64 bytes o MIN_PKTSIZE = 64 bytes
o PROB_LOW = 0.85 o PROB_LOW = 0.85
o PROB_HIGH = 8.5 o PROB_HIGH = 8.5
o LATENCY_LOW = 5 ms o LATENCY_LOW = 5 ms
o LATENCY_HIGH=200 ms.
A.1.3. Variables A.1.3. Variables
o drop_prob_. The current packet drop probability. o drop_prob_. The current packet drop probability.
o accu_prob_. accumulated drop prob. since last drop o accu_prob_. accumulated drop prob. since last drop
o qdelay_old_. The previous queue delay estimate. o qdelay_old_. The previous queue delay estimate.
o burst_allowance_. Countdown for burst protection, initialize to 0 o burst_allowance_. Countdown for burst protection, initialize to 0
o burst_reset_. counter to reset burst o burst_reset_. counter to reset burst
o burst_state_. Burst protection state encoding 3 states: o aqm_state_. AQM activity state encoding 3 states:
NOBURST - no burst yet INACTIVE - queue staying below 1/3 full, suppress AQM drops
FIRST_BURST - first burst detected, no protection yet QUIESCENT - transition state
PROTECT_BURST - first burst detected, protecting burst if ACTIVE - normal AQM drops (after burst protection period)
burst_allowance_ > 0
o queue_. Holds the pending packets. o queue_. Holds the pending packets.
A.1.4. Public/system functions: A.1.4. Public/system functions:
o drop(packet). Drops/discards a packet o drop(packet). Drops/discards a packet
o random(). Returns a uniform r.v. in the range 0 ~ 1 o random(). Returns a uniform r.v. in the range 0 ~ 1
o queue_.is_full(). Returns true if queue_ is full o queue_.is_full(). Returns true if queue_ is full
o queue_.byte_length(). Returns current queue_ length in bytes, o queue_.byte_length(). Returns current queue_ length in bytes,
skipping to change at page 9, line 37 skipping to change at page 11, line 45
o Calls control_path_init() at service flow creation o Calls control_path_init() at service flow creation
o Calls calculate_drop_prob() at a regular INTERVAL (16ms) o Calls calculate_drop_prob() at a regular INTERVAL (16ms)
================ ================
// Initialization function // Initialization function
control_path_init() { control_path_init() {
drop_prob_ = 0; drop_prob_ = 0;
qdelay_old_ = 0; qdelay_old_ = 0;
burst_reset_ = 0; burst_reset_ = 0;
burst_state_ = NOBURST; aqm_state_ = INACTIVE;
} }
// Background update, occurs every INTERVAL // Background update, occurs every INTERVAL
calculate_drop_prob() { calculate_drop_prob() {
if (queue_.byte_length() <= msrtokens()) { if (queue_.byte_length() <= msrtokens()) {
qdelay = queue_.byte_length() / PEAK_RATE; qdelay = queue_.byte_length() / PEAK_RATE;
} else { } else {
qdelay = ((queue_.byte_length() - msrtokens()) / MSR \ qdelay = ((queue_.byte_length() - msrtokens()) / MSR \
+ msrtokens() / PEAK_RATE); + msrtokens() / PEAK_RATE);
} }
if (burst_allowance_ > 0) { if (burst_allowance_ > 0) {
drop_prob_ = 0; drop_prob_ = 0;
burst_allowance_ = max(0, burst_allowance_ - INTERVAL);
} else { } else {
p = A * (qdelay - LATENCY_TARGET) + \ p = A * (qdelay - LATENCY_TARGET) + \
B * (qdelay - qdelay_old_); B * (qdelay - qdelay_old_);
// Since A=0.25 & B=2.5, can be implemented // Since A=0.25 & B=2.5, can be implemented
// with shift and add // with shift and add
if (drop_prob_ < 0.000001) { if (drop_prob_ < 0.000001) {
p /= 2048; p /= 2048;
} else if (drop_prob_ < 0.00001) { } else if (drop_prob_ < 0.00001) {
p /= 512; p /= 512;
skipping to change at page 10, line 34 skipping to change at page 12, line 44
p /= 0.125; p /= 0.125;
} else { } else {
p /= 0.03125; p /= 0.03125;
} }
if ((drop_prob_ >= 0.1) && (p > 0.02)) { if ((drop_prob_ >= 0.1) && (p > 0.02)) {
p = 0.02; p = 0.02;
} }
drop_prob_ += p; drop_prob_ += p;
/* for non-linear drop in prob */ /* some special cases */
if (qdelay < LATENCY_LOW && qdelay_old_ < LATENCY_LOW) { if (qdelay < LATENCY_LOW && qdelay_old_ < LATENCY_LOW) {
drop_prob_ *= 0.98; // (1-1/64) is sufficient drop_prob_ *= 0.98; // exponential decay
} else if (qdelay > DELAY_HIGH) { } else if (qdelay > LATENCY_HIGH) {
drop_prob_ += 0.02; drop_prob_ += 0.02; // ramp up quickly
} }
drop_prob_ = max(0, drop_prob_); drop_prob_ = max(0, drop_prob_);
drop_prob_ = min(drop_prob_, \ drop_prob_ = min(drop_prob_, \
PROB_LOW * MEAN_PKTSIZE/MIN_PKTSIZE); PROB_LOW * MEAN_PKTSIZE/MIN_PKTSIZE);
} }
if (burst_allowance_ < INTERVAL) // check if all is quiet
burst_allowance_ = 0; quiet = (qdelay < 0.5 * LATENCY_TARGET)
else && (qdelay_old_ < 0.5 * LATENCY_TARGET)
burst_allowance_ = burst_allowance_ - INTERVAL; && (drop_prob_ == 0)
&& (burst_allowance_ == 0);
// both old and new qdelay is well better than the
// target and drop_prob_ == 0, time to clear burst tolerance
if ((qdelay < 0.5 * LATENCY_TARGET)
&& (qdelay_old_ < 0.5 * LATENCY_TARGET)
&& (drop_prob_ == 0)
&& (burst_allowance_ == 0)){
if (burst_state_ == PROTECT_BURST) {
burst_state_ = FIRST_BURST;
burst_reset_ = 0;
} else if (burst_state_ == FIRST_BURST) { // Update AQM state based on quiet or !quiet
if ((aqm_state_ == ACTIVE) && quiet) {
aqm_state_ = QUIESCENT;
burst_reset_ = 0;
} else if (aqm_state_ == QUIESCENT) {
if (quiet) {
burst_reset_ += INTERVAL ; burst_reset_ += INTERVAL ;
if (burst_reset_ > BURST_RESET_TIMEOUT) { if (burst_reset_ > BURST_RESET_TIMEOUT) {
burst_reset_ = 0; burst_reset_ = 0;
burst_state_ = NOBURST; aqm_state_ = INACTIVE;
} }
} } else {
} else if (burst_state_ == FIRST_BURST) {
burst_reset_ = 0; burst_reset_ = 0;
}
} }
qdelay_old_ = qdelay; qdelay_old_ = qdelay;
} }
A.3. DOCSIS-PIE AQM Data Path A.3. DOCSIS-PIE AQM Data Path
The DOCSIS-PIE data path performs the following: The DOCSIS-PIE data path performs the following:
skipping to change at page 11, line 49 skipping to change at page 14, line 5
accu_prob_ = 0; accu_prob_ = 0;
} else if (drop_early(packet, queue_.byte_length())) { } else if (drop_early(packet, queue_.byte_length())) {
drop(packet); drop(packet);
} else { } else {
queue_.enque(packet); queue_.enque(packet);
} }
} }
//////////////// ////////////////
drop_early(packet, queue_length) { drop_early(packet, queue_length) {
// if still in burst protection, suppress AQM drops
if (burst_allowance_ > 0) { if (burst_allowance_ > 0) {
return FALSE; return FALSE;
} }
// if drop_prob_ goes to zero, clear accu_prob_
if (drop_prob_ == 0) { if (drop_prob_ == 0) {
accu_prob_ = 0; accu_prob_ = 0;
} }
if (burst_state_ == NOBURST) { //first burst? if (aqm_state_ == INACTIVE) {
if (queue_.byte_length() < BUFFER_SIZE/3) { if (queue_.byte_length() < BUFFER_SIZE/3) {
// if queue is still small, stay in
// INACTIVE state and suppress AQM drops
return FALSE; return FALSE;
} else { } else {
burst_state_ = FIRST_BURST; //burst detected // otherwise transition to QUIESCENT state
aqm_state_ = QUIESCENT;
} }
} }
//The CM can quantize packet.size to 64, 128, 256, 512, 768, //The CM can quantize packet.size to 64, 128, 256, 512, 768,
// 1024, 1280, 1536, 2048 in the calculation below // 1024, 1280, 1536, 2048 in the calculation below
p1 = drop_prob_ * packet.size() / MEAN_PKTSIZE; p1 = drop_prob_ * packet.size() / MEAN_PKTSIZE;
p1 = min(p1, PROB_LOW); p1 = min(p1, PROB_LOW);
accu_prob_ += p1; accu_prob_ += p1;
// If latency is low, don't drop packets // Suppress AQM drops in certain situations
if ( (qdelay_old_ < 0.5 * LATENCY_TARGET && drop_prob_ < 0.2) if ( (qdelay_old_ < 0.5 * LATENCY_TARGET && drop_prob_ < 0.2)
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) { || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
return FALSE; return FALSE;
} }
drop = TRUE;
if (accu_prob_ < PROB_LOW) { // avoid dropping too fast due if (accu_prob_ < PROB_LOW) { // avoid dropping too fast due
drop = FALSE; // to bad luck of coin tosses... return FALSE; // to bad luck of coin tosses...
} else if (accu_prob_ >= PROB_HIGH) { // ...and avoid droppping } else if (accu_prob_ >= PROB_HIGH) { // ...and avoid droppping
drop = TRUE; // too slowly drop = TRUE; // too slowly
} else { //Random drop } else { //Random drop
double u = random(); // 0 ~ 1 double u = random(); // 0 ~ 1
if (u > p1) { if (u > p1)
drop = FALSE; return FALSE;
} else
drop = TRUE;
} }
// at this point, drop == TRUE, so packet will be dropped.
if (drop == FALSE) return FALSE; // reset accu_prob_
// In case of packet drop:
accu_prob_ = 0; accu_prob_ = 0;
// Not protecting burst yet? Start protecting burst. // If in QUIESCENT state, packet drop triggers
// This will set the burst_allowance_ value, and // ACTIVE state and start of burst protection
// calculate_drop_prob() will decrement it. if (aqm_state_ == QUIESCENT) {
// Could implement this as a 150ms timer instead. aqm_state_ = ACTIVE;
if (burst_state_ == FIRST_BURST) {
burst_state_ = PROTECT_BURST;
burst_allowance_ = MAX_BURST; burst_allowance_ = MAX_BURST;
} }
return TRUE; return TRUE;
} }
Authors' Addresses Authors' Addresses
Greg White Greg White
CableLabs CableLabs
858 Coal Creek Circle 858 Coal Creek Circle
 End of changes. 54 change blocks. 
126 lines changed or deleted 231 lines changed or added

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/