GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


rfc:rfc7806

Internet Engineering Task Force (IETF) F. Baker Request for Comments: 7806 R. Pan Category: Informational Cisco Systems ISSN: 2070-1721 April 2016

                 On Queuing, Marking, and Dropping

Abstract

 This note discusses queuing and marking/dropping algorithms.  While
 these algorithms may be implemented in a coupled manner, this note
 argues that specifications, measurements, and comparisons should
 decouple the different algorithms and their contributions to system
 behavior.

Status of This Memo

 This document is not an Internet Standards Track specification; it is
 published for informational purposes.
 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 a candidate for any level of Internet
 Standard; see Section 2 of RFC 5741.
 Information about the current status of this document, any errata,
 and how to provide feedback on it may be obtained at
 http://www.rfc-editor.org/info/rfc7806.

Copyright Notice

 Copyright (c) 2016 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.

Baker & Pan Informational [Page 1] RFC 7806 On Queuing, Marking, and Dropping April 2016

Table of Contents

 1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
 2.  Fair Queuing: Algorithms and History  . . . . . . . . . . . .   3
   2.1.  Generalized Processor Sharing . . . . . . . . . . . . . .   3
     2.1.1.  GPS Comparisons: Transmission Quanta  . . . . . . . .   4
     2.1.2.  GPS Comparisons: Flow Definition  . . . . . . . . . .   4
     2.1.3.  GPS Comparisons: Unit of Measurement  . . . . . . . .   5
   2.2.  GPS Approximations  . . . . . . . . . . . . . . . . . . .   5
     2.2.1.  Definition of a Queuing Algorithm . . . . . . . . . .   5
     2.2.2.  Round-Robin Models  . . . . . . . . . . . . . . . . .   6
     2.2.3.  Calendar Queue Models . . . . . . . . . . . . . . . .   7
     2.2.4.  Work-Conserving Models and Stochastic Fairness
             Queuing . . . . . . . . . . . . . . . . . . . . . . .   9
     2.2.5.  Non-Work-Conserving Models and Virtual Clock  . . . .   9
 3.  Queuing, Marking, and Dropping  . . . . . . . . . . . . . . .  10
   3.1.  Queuing with Tail Mark/Drop . . . . . . . . . . . . . . .  11
   3.2.  Queuing with CoDel Mark/Drop  . . . . . . . . . . . . . .  11
   3.3.  Queuing with RED or PIE Mark/Drop . . . . . . . . . . . .  11
 4.  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . .  12
 5.  Security Considerations . . . . . . . . . . . . . . . . . . .  13
 6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  13
   6.1.  Normative References  . . . . . . . . . . . . . . . . . .  13
   6.2.  Informative References  . . . . . . . . . . . . . . . . .  13
 Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  15
 Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  16

1. Introduction

 In the discussion of Active Queue Management (AQM), there has been
 discussion of the coupling of queue management algorithms such as
 Stochastic Fairness Queuing [SFQ], Virtual Clock [VirtualClock], or
 Deficit Round Robin [DRR] with mark/drop algorithms such as
 Controlled Delay (CoDel) [DELAY-AQM] or Proportional Integral
 controller Enhanced (PIE) [AQM-PIE].  In the interest of clarifying
 the discussion, we document possible implementation approaches to
 that and analyze the possible effects and side effects.  The language
 and model derive from the Architecture for Differentiated Services
 [RFC2475].
 This note is informational and is intended to describe reasonable
 possibilities without constraining outcomes.  This is not so much
 about "right" or "wrong" as it is "what might be reasonable" and
 discusses several possible implementation strategies.  Also, while
 queuing might be implemented in almost any layer, the note
 specifically addresses queues that might be used in the
 Differentiated Services Architecture and are therefore at or below
 the IP layer.

Baker & Pan Informational [Page 2] RFC 7806 On Queuing, Marking, and Dropping April 2016

2. Fair Queuing: Algorithms and History

 There is extensive history in the set of algorithms collectively
 referred to as "fair queuing".  The model was initially discussed in
 [RFC970], which proposed it hypothetically as a solution to the TCP
 Silly Window Syndrome issue in BSD 4.1.  The problem was that, due to
 a TCP implementation bug, some senders would settle into sending a
 long stream of very short segments, which unnecessarily consumed
 bandwidth on TCP and IP headers and occupied short packet buffers,
 thereby disrupting competing sessions.  Nagle suggested that if
 packet streams were sorted by their source address and the sources
 treated in a round-robin fashion, a sender's effect on end-to-end
 latency and increased loss rate would primarily affect only itself.
 This touched off perhaps a decade of work by various researchers on
 what was and is termed "fair queuing", philosophical discussions of
 the meaning of the word "fair", operational reasons that one might
 want a "weighted" or "predictably unfair" queuing algorithm, and so
 on.

2.1. Generalized Processor Sharing

 Conceptually, any fair queuing algorithm attempts to implement some
 approximation to the Generalized Processor Sharing [GPS] model.
 The GPS model, in its essence, presumes that a set of identified data
 streams, called "flows", pass through an interface.  Each flow has a
 rate when measured over a period of time; a voice session might, for
 example, require 64 kbit/s plus whatever overhead is necessary to
 deliver it, and a TCP session might have variable throughput
 depending on where it is in its evolution.  The premise of
 Generalized Processor Sharing is that on all time scales, the flow
 occupies a predictable bit rate so that if there is enough bandwidth
 for the flow in the long term, it also lacks nothing in the short
 term.  "All time scales" is obviously untenable in a packet network
 -- and even in a traditional Time-Division Multiplexer (TDM) circuit
 switch network -- because a timescale shorter than the duration of a
 packet will only see one packet at a time.  However, it provides an
 ideal for other models to be compared against.
 There are a number of attributes of approximations to the GPS model
 that bear operational consideration, including at least the
 transmission quanta, the definition of a "flow", and the unit of
 measurement.  Implementation approaches have different practical
 impacts as well.

Baker & Pan Informational [Page 3] RFC 7806 On Queuing, Marking, and Dropping April 2016

2.1.1. GPS Comparisons: Transmission Quanta

 The most obvious comparison between the GPS model and common
 approximations to it is that real world data is not delivered
 uniformly, but in some quantum.  The smallest quantum in a packet
 network is a packet.  But quanta can be larger; for example, in video
 applications, it is common to describe data flow in frames per
 second, where a frame describes a picture on a screen or the changes
 made from a previous one.  A single video frame is commonly on the
 order of tens of packets.  If a codec is delivering thirty frames per
 second, it is conceivable that the packets comprising a frame might
 be sent as thirty bursts per second, with each burst sent at the
 interface rate of the camera or other sender.  Similarly, TCP
 exchanges have an initial window (common values of which include 1,
 2, 3, 4 [RFC3390], and 10 [RFC6928]), and there are also reports of
 bursts of 64 KB at the relevant Maximum Segment Size (MSS), which is
 to say about 45 packets in one burst, presumably coming from TCP
 Segment Offload ((TSO) also called TCP Offload Engine (TOE)) engines
 (at least one implementation is known to be able to send a burst of
 256 KB).  After that initial burst, TCP senders commonly send pairs
 of packets but may send either smaller or larger bursts [RFC5690].

2.1.2. GPS Comparisons: Flow Definition

 An important engineering trade-off relevant to GPS is the definition
 of a "flow".  A flow is, by definition, a defined data stream.
 Common definitions include:
 o  packets in a single transport layer session ("microflow"),
    identified by a five-tuple [RFC2990];
 o  packets between a single pair of addresses, identified by a source
    and destination address or prefix;
 o  packets from a single source address or prefix [RFC970];
 o  packets to a single destination address or prefix; and
 o  packets to or from a single subscriber, customer, or peer
    [RFC6057].  In Service Provider operations, this might be a
    neighboring Autonomous System; in broadband, this might be a
    residential customer.
 The difference should be apparent.  Consider a comparison between
 sorting by source address or destination address, to pick two
 examples, in the case that a given router interface has N application
 sessions going through it between N/2 local destinations and N remote
 sources.  Sorting by source, or in this case by source/destination

Baker & Pan Informational [Page 4] RFC 7806 On Queuing, Marking, and Dropping April 2016

 pair, would give each remote peer an upper-bound guarantee of 1/N of
 the available capacity, which might be distributed very unevenly
 among the local destinations.  Sorting by destination would give each
 local destination an upper-bound guarantee of 2/N of the available
 capacity, which might be distributed very unevenly among the remote
 systems and correlated sessions.  Who is one fair to?  In both cases,
 they deliver equal service by their definition, but that might not be
 someone else's definition.
 Flow fairness, and the implications of TCP's congestion avoidance
 algorithms, is discussed extensively in [NoFair].

2.1.3. GPS Comparisons: Unit of Measurement

 And finally, there is the question of what is measured for rate.  If
 the only objective is to force packet streams to not dominate each
 other, it is sufficient to count packets.  However, if the issue is
 the bit rate of a Service Level Agreement (SLA), one must consider
 the sizes of the packets (the aggregate throughput of a flow measured
 in bits or bytes).  If predictable unfairness is a consideration, the
 value must be weighted accordingly.
 [RFC7141] discusses measurement.

2.2. GPS Approximations

 Carrying the matter further, a queuing algorithm may also be termed
 "work conserving" or "non work conserving".  A queue in a work-
 conserving algorithm, by definition, is either empty, in which case
 no attempt is being made to dequeue data from it, or contains
 something, in which case the algorithm continuously tries to empty
 the queue.  A work-conserving queue that contains queued data at an
 interface with a given rate will deliver data at that rate until it
 empties.  A non-work-conserving queue might stop delivering even
 though it still contains data.  A common reason for doing this is to
 impose an artificial upper bound on a class of traffic that is lower
 than the rate of the underlying physical interface.

2.2.1. Definition of a Queuing Algorithm

 In the discussion following, we assume a basic definition of a
 queuing algorithm.  A queuing algorithm has, at minimum:
 o  some form of internal storage for the elements kept in the queue;

Baker & Pan Informational [Page 5] RFC 7806 On Queuing, Marking, and Dropping April 2016

 o  if it has multiple internal classifications, then it has
  • a method for classifying elements and
  • additional storage for the classifier and implied classes;
 o  potentially, a method for creating the queue;
 o  potentially, a method for destroying the queue;
 o  an enqueuing method for placing packets into the queue or queuing
    system; and
 o  a dequeuing method for removing packets from the queue or queuing
    system.
 There may also be other information or methods, such as the ability
 to inspect the queue.  It also often has inspectable external
 attributes, such as the total volume of packets or bytes in queue,
 and may have limit thresholds, such as a maximum number of packets or
 bytes the queue might hold.
 For example, a simple FIFO queue has a linear data structure,
 enqueues packets at the tail, and dequeues packets from the head.  It
 might have a maximum queue depth and a current queue depth maintained
 in packets or bytes.

2.2.2. Round-Robin Models

 One class of implementation approaches, generically referred to as
 "Weighted Round Robin" (WRR), implements the structure of the queue
 as an array or ring of subqueues associated with flows for whatever
 definition of a flow is important.
 The arriving packet must, of course, first be classified.  If a hash
 is used as a classifier, the hash result might be used as an array
 index, selecting the subqueue that the packet will go into.  One can
 imagine other classifiers, such as using a Differentiated Services
 Code Point (DSCP) value as an index into an array containing the
 queue number for a flow, or more complex access list implementations.
 In any event, a subqueue contains the traffic for a flow, and data is
 sent from each subqueue in succession.
 Upon entering the queue, the enqueue method places a classified
 packet into a simple FIFO subqueue.

Baker & Pan Informational [Page 6] RFC 7806 On Queuing, Marking, and Dropping April 2016

 On dequeue, the subqueues are searched in round-robin order, and when
 a subqueue is identified that contains data, the dequeue method
 removes a specified quantum of data from it.  That quantum is at
 minimum a packet, but it may be more.  If the system is intended to
 maintain a byte rate, there will be memory between searches of the
 excess previously dequeued.
                          +-+
                        +>|1|
                        | +-+
                        |  |
                        | +-+               +-+
                        | |1|             +>|3|
                        | +-+             | +-+
                        |  |              |  |
                        | +-+      +-+    | +-+
                        | |1|    +>|2|    | |3|
                        | +-+    | +-+    | +-+
                        |  A     |  A     |  A
                        |  |     |  |     |  |
                       ++--++   ++--++   ++--++
                    +->| Q  |-->| Q  |-->| Q  |--+
                    |  +----+   +----+   +----+  |
                    +----------------------------+
                     Figure 1: Round-Robin Queues

2.2.3. Calendar Queue Models

 Another class of implementation approaches, generically referred to
 as Calendar Queue Implementations [CalendarQueue], implements the
 structure of the queue as an array or ring of subqueues (often called
 "buckets") associated with time or sequence; each bucket contains the
 set of packets, which may be null, intended to be sent at a certain
 time or following the emptying of the previous bucket.  The queue
 structure includes a look-aside table that indicates the current
 depth (which is to say, the next bucket) of any given class of
 traffic, which might similarly be identified using a hash, a DSCP, an
 access list, or any other classifier.  Conceptually, the queues each
 contain zero or more packets from each class of traffic.  One is the
 queue being emptied "now"; the rest are associated with some time or
 sequence in the future.  The characteristics under "load" have been
 investigated in [Deadline].
 Upon entering the queue, the enqueue method, considering a classified
 packet, determines the current depth of that class with a view to
 scheduling it for transmission at some time or sequence in the
 future.  If the unit of scheduling is a packet and the queuing

Baker & Pan Informational [Page 7] RFC 7806 On Queuing, Marking, and Dropping April 2016

 quantum is one packet per subqueue, a burst of packets arrives in a
 given flow, and if at the start the flow has no queued data, the
 first packet goes into the "next" queue, the second into its
 successor, and so on.  If there was some data in the class, the first
 packet in the burst would go into the bucket pointed to by the look-
 aside table.  If the unit of scheduling is time, the explanation in
 Section 2.2.5 might be simplest to follow, but the bucket selected
 will be the bucket corresponding to a given transmission time in the
 future.  A necessary side effect, memory being finite, is that there
 exist a finite number of "future" buckets.  If enough traffic arrives
 to cause a class to wrap, one is forced to drop something (tail
 drop).
 On dequeue, the buckets are searched at their stated times or in
 their stated sequence, and when a bucket is identified that contains
 data, the dequeue method removes a specified quantum of data from it
 and, by extension, from the associated traffic classes.  A single
 bucket might contain data from a number of classes simultaneously.
                           +-+
                         +>|1|
                         | +-+
                         |  |
                         | +-+      +-+
                         | |2|    +>|2|
                         | +-+    | +-+
                         |  |     |  |
                         | +-+    | +-+      +-+
                         | |3|    | |1|    +>|1|
                         | +-+    | +-+    | +-+
                         |  A     |  A     |  A
                         |  |     |  |     |  |
                        ++--++   ++--++   ++--++
                "now"+->| Q  |-->| Q  |-->| Q  |-->...
                        +----+   +----+   +----+
                           A       A         A
                           |3      |2        |1
                        +++++++++++++++++++++++
                        ||||     Flow      ||||
                        +++++++++++++++++++++++
                       Figure 2: Calendar Queue
 In any event, a subqueue contains the traffic for a point in time or
 a point in sequence, and data is sent from each subqueue in
 succession.  If subqueues are associated with time, an interesting
 end case develops: if the system is draining a given subqueue and the
 time of the next subqueue arrives, what should the system do?  One

Baker & Pan Informational [Page 8] RFC 7806 On Queuing, Marking, and Dropping April 2016

 potentially valid line of reasoning would have it continue delivering
 the data in the present queue on the assumption that it will likely
 trade off for time in the next.  Another potentially valid line of
 reasoning would have it discard any waiting data in the present queue
 and move to the next.

2.2.4. Work-Conserving Models and Stochastic Fairness Queuing

 Stochastic Fairness Queuing [SFQ] is an example of a work-conserving
 algorithm.  This algorithm measures packets and considers a "flow" to
 be an equivalence class of traffic defined by a hashing algorithm
 over the source and destination IPv4 addresses.  As packets arrive,
 the enqueue method performs the indicated hash and places the packet
 into the indicated subqueue.  The dequeue method operates as
 described in Section 2.2.2; subqueues are inspected in round-robin
 sequence and a packet is removed if they contain one or more packets.
 The Deficit Round Robin [DRR] model modifies the quanta to bytes and
 deals with variable length packets.  A subqueue descriptor contains a
 waiting quantum (the amount intended to be dequeued on the previous
 dequeue attempt that was not satisfied), a per-round quantum (the
 subqueue is intended to dequeue a certain number of bytes each
 round), and a maximum to permit (some multiple of the MTU).  In each
 dequeue attempt, the dequeue method sets the waiting quantum to the
 smaller of the maximum quantum and the sum of the waiting and
 incremental quantum.  It then dequeues up to the waiting quantum (in
 bytes) of packets in the queue and reduces the waiting quantum by the
 number of bytes dequeued.  Since packets will not normally be exactly
 the size of the quantum, some dequeue attempts will dequeue more than
 others, but they will over time average the incremental quantum per
 round if there is data present.
 [SFQ] and [DRR] could be implemented as described in Section 2.2.3.
 The weakness of a classical WRR approach is the search time expended
 inspecting and not choosing sub-queues that contain no data or not
 enough to trigger a transmission from them.

2.2.5. Non-Work-Conserving Models and Virtual Clock

 Virtual Clock [VirtualClock] is an example of a non-work-conserving
 algorithm.  It is trivially implemented as described in
 Section 2.2.3.  It associates buckets with intervals in time that
 have durations on the order of microseconds to tens of milliseconds.
 Each flow is assigned a rate in bytes per interval.  The flow entry
 maintains a point in time the "next" packet in the flow should be
 scheduled.

Baker & Pan Informational [Page 9] RFC 7806 On Queuing, Marking, and Dropping April 2016

 On enqueue, the method determines whether the "next schedule" time is
 "in the past"; if so, the packet is scheduled "now", and if not, the
 packet is scheduled at that time.  It then calculates the new "next
 schedule" time as the current "next schedule" time plus the length of
 the packet divided by the rate.  If the resulting time is also in the
 past, the "next schedule" time is set to "now"; otherwise, it is set
 to the calculated time.  As noted in Section 2.2.3, there is an
 interesting point regarding "too much time in the future"; if a
 packet is scheduled too far into the future, it may be marked or
 dropped in the AQM procedure, and if it runs beyond the end of the
 queuing system, may be defensively tail dropped.
 On dequeue, the bucket associated with the time "now" is inspected.
 If it contains a packet, the packet is dequeued and transmitted.  If
 the bucket is empty and the time for the next bucket has not arrived,
 the system waits, even if there is a packet in the next bucket.  As
 noted in Section 2.2.3, there is an interesting point regarding the
 queue associated with "now".  If a subsequent bucket, even if it is
 actually empty, would be delayed by the transmission of a packet, one
 could imagine marking the packet Explicit Congestion Notification -
 Congestion Experienced (ECN-CE) [RFC3168] [RFC6679] or dropping the
 packet.

3. Queuing, Marking, and Dropping

 Queuing, marking, and dropping are integrated in any system that has
 a queue.  If nothing else, as memory is finite, a system has to drop
 as discussed in Sections 2.2.3 and 2.2.5 in order to protect itself.
 However, host transports interpret drops as signals, so AQM
 algorithms use that as a mechanism to signal.
 It is useful to think of the effects of queuing as a signal as well.
 The receiver sends acknowledgements as data is received, so the
 arrival of acknowledgements at the sender paces the sender at
 approximately the average rate it is able to achieve through the
 network.  This is true even if the sender keeps an arbitrarily large
 amount of data stored in network queues and is the basis for delay-
 based congestion control algorithms.  So, delaying a packet
 momentarily in order to permit another session to improve its
 operation has the effect of signaling a slightly lower capacity to
 the sender.

Baker & Pan Informational [Page 10] RFC 7806 On Queuing, Marking, and Dropping April 2016

3.1. Queuing with Tail Mark/Drop

 In the default case in which a FIFO queue is used with defensive tail
 drop only, the effect is to signal to the sender in two ways:
 o  Ack clocking, which involves pacing the sender to send at
    approximately the rate it can deliver data to the receiver; and
 o  Defensive loss, which is when a sender sends faster than available
    capacity (such as by probing network capacity when fully utilizing
    that capacity) and overburdens a queue.

3.2. Queuing with CoDel Mark/Drop

 In any case wherein a queuing algorithm is used along with CoDel
 [DELAY-AQM], the sequence of events is that a packet is time stamped,
 enqueued, dequeued, compared to a subsequent reading of the clock,
 and then acted on, whether by dropping it, marking and forwarding it,
 or simply forwarding it.  This is to say that the only drop algorithm
 inherent in queuing is the defensive drop when the queue's resources
 are overrun.  However, the intention of marking or dropping is to
 signal to the sender much earlier when a certain amount of delay has
 been observed.  In a FIFO+CoDel, Virtual Clock+CoDel, or FlowQueue-
 Codel [FQ-CODEL] implementation, the queuing algorithm is completely
 separate from the AQM algorithm.  Using them in series results in
 four signals to the sender:
 o  Ack clocking, which involves pacing the sender to send at
    approximately the rate it can deliver data to the receiver through
    a queue;
 o  Lossless signaling that a certain delay threshold has been
    reached, if ECN [RFC3168] [RFC6679] is in use;
 o  Intentional signaling via loss that a certain delay threshold has
    been reached, if ECN is not in use; and
 o  Defensive loss, which is when a sender sends faster than available
    capacity (such as by probing network capacity when fully utilizing
    that capacity) and overburdens a queue.

3.3. Queuing with RED or PIE Mark/Drop

 In any case wherein a queuing algorithm is used along with PIE
 [AQM-PIE], Random Early Detection (RED) [RFC7567], or other such
 algorithms, the sequence of events is that a queue is inspected, a
 packet is dropped, marked, or left unchanged, enqueued, dequeued,
 compared to a subsequent reading of the clock, and then forwarded on.

Baker & Pan Informational [Page 11] RFC 7806 On Queuing, Marking, and Dropping April 2016

 This is to say that the AQM Mark/Drop Algorithm precedes enqueue; if
 it has not been effective and as a result the queue is out of
 resources anyway, the defensive drop algorithm steps in, and failing
 that, the queue operates in whatever way it does.  Hence, in a
 FIFO+PIE, SFQ+PIE, or Virtual Clock+PIE implementation, the queuing
 algorithm is again completely separate from the AQM algorithm.  Using
 them in series results in four signals to the sender:
 o  Ack clocking, which involves pacing the sender to send at
    approximately the rate it can deliver data to the receiver through
    a queue;
 o  Lossless signaling that a queue depth that corresponds to a
    certain delay threshold has been reached, if ECN is in use;
 o  Intentional signaling via loss that a queue depth that corresponds
    to a certain delay threshold has been reached, if ECN is not in
    use; and
 o  Defensive loss, which is when a sender sends faster than available
    capacity (such as by probing network capacity when fully utilizing
    that capacity) and overburdens a queue.

4. Conclusion

 To summarize, in Section 2, implementation approaches for several
 classes of queuing algorithms were explored.  Queuing algorithms such
 as SFQ, Virtual Clock, and FlowQueue-Codel [FQ-CODEL] have value in
 the network in that they delay packets to enforce a rate upper bound
 or to permit competing flows to compete more effectively.  ECN
 marking and loss are also useful signals if used in a manner that
 enhances TCP / Steam Control Transmission Protocol (SCTP) operation
 or restrains unmanaged UDP data flows.
 Conceptually, queuing algorithms and mark/drop algorithms operate in
 series (as discussed in Section 3), not as a single algorithm.  The
 observed effects differ: defensive loss protects the intermediate
 system and provides a signal, AQM mark/drop works to reduce mean
 latency, and the scheduling of flows works to modify flow interleave
 and acknowledgement pacing.  Certain features like flow isolation are
 provided by fair-queuing-related designs but are not the effect of
 the mark/drop algorithm.
 There is value in implementing and coupling the operation of both
 queuing algorithms and queue management algorithms, and there is
 definitely interesting research in this area, but specifications,
 measurements, and comparisons should decouple the different
 algorithms and their contributions to system behavior.

Baker & Pan Informational [Page 12] RFC 7806 On Queuing, Marking, and Dropping April 2016

5. Security Considerations

 This memo adds no new security issues; it observes implementation
 strategies for Diffserv implementation.

6. References

6.1. Normative References

 [RFC2475]   Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z.,
             and W. Weiss, "An Architecture for Differentiated
             Services", RFC 2475, DOI 10.17487/RFC2475, December 1998,
             <http://www.rfc-editor.org/info/rfc2475>.

6.2. Informative References

 [AQM-PIE]   Pan, R., Natarajan, P., and F. Baker, "PIE: A Lightweight
             Control Scheme To Address the Bufferbloat Problem", Work
             in Progress, draft-ietf-aqm-pie-06, April 2016.
 [CalendarQueue]
             Brown, R., "Calendar queues: a fast 0(1) priority queue
             implementation for the simulation event set problem",
             Communications of the ACM Volume 21, Issue 10, pp.
             1220-1227, DOI 10.1145/63039.63045, October 1988,
             <http://dl.acm.org/citation.cfm?id=63045>.
 [Deadline]  Kruk, L., Lohoczky, J., Ramanan, K., and S. Shreve,
             "Heavy Traffic Analysis For EDF Queues With Reneging",
             The Annals of Applied Probability Volume 21, Issue No. 2,
             pp. 484-545, DOI 10.1214/10-AAP681, 2011,
             <http://www.math.cmu.edu/users/shreve/Reneging.pdf>.
 [DELAY-AQM] Nichols, K., Jacobson, V., McGregor, A., and J. Iyengar,
             "Controlled Delay Active Queue Management", Work in
             Progress, draft-ietf-aqm-codel-03, March 2016.
 [DRR]       Shreedhar, M. and G. Varghese, "Efficient fair queuing
             using deficit round-robin", IEEE/ACM Transactions on
             Networking Volume 4, Issue 3, pp. 375-385,
             DOI 10.1109/90.502236, June 1996,
             <http://ieeexplore.ieee.org/stamp/
             stamp.jsp?tp=&arnumber=502236>.
 [FQ-CODEL]  Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys,
             J., and E. Dumazet, "The FlowQueue-CoDel Packet Scheduler
             and Active Queue Management Algorithm", Work in Progress,
             draft-ietf-aqm-fq-codel-06, March 2016.

Baker & Pan Informational [Page 13] RFC 7806 On Queuing, Marking, and Dropping April 2016

 [GPS]       Demers, A., University of California, Berkeley, and Xerox
             PARC, "Analysis and Simulation of a Fair Queueing
             Algorithm", ACM SIGCOMM Computer Communication
             Review, Volume 19, Issue 4, pp. 1-12,
             DOI 10.1145/75247.75248, September 1989,
             <http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/
             data/89/fq.pdf>.
 [NoFair]    Briscoe, B., "Flow rate fairness: dismantling a
             religion", ACM SIGCOMM Computer Communication
             Review, Volume 37, Issue 2, pp. 63-74,
             DOI 10.1145/1232919.1232926, April 2007,
             <http://dl.acm.org/citation.cfm?id=1232926>.
 [RFC970]    Nagle, J., "On Packet Switches With Infinite Storage",
             RFC 970, DOI 10.17487/RFC0970, December 1985,
             <http://www.rfc-editor.org/info/rfc970>.
 [RFC2990]   Huston, G., "Next Steps for the IP QoS Architecture",
             RFC 2990, DOI 10.17487/RFC2990, November 2000,
             <http://www.rfc-editor.org/info/rfc2990>.
 [RFC3168]   Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
             of Explicit Congestion Notification (ECN) to IP",
             RFC 3168, DOI 10.17487/RFC3168, September 2001,
             <http://www.rfc-editor.org/info/rfc3168>.
 [RFC3390]   Allman, M., Floyd, S., and C. Partridge, "Increasing
             TCP's Initial Window", RFC 3390, DOI 10.17487/RFC3390,
             October 2002, <http://www.rfc-editor.org/info/rfc3390>.
 [RFC5690]   Floyd, S., Arcia, A., Ros, D., and J. Iyengar, "Adding
             Acknowledgement Congestion Control to TCP", RFC 5690,
             DOI 10.17487/RFC5690, February 2010,
             <http://www.rfc-editor.org/info/rfc5690>.
 [RFC6057]   Bastian, C., Klieber, T., Livingood, J., Mills, J., and
             R.  Woundy, "Comcast's Protocol-Agnostic Congestion
             Management System", RFC 6057, DOI 10.17487/RFC6057,
             December 2010, <http://www.rfc-editor.org/info/rfc6057>.
 [RFC6679]   Westerlund, M., Johansson, I., Perkins, C., O'Hanlon, P.,
             and K. Carlberg, "Explicit Congestion Notification (ECN)
             for RTP over UDP", RFC 6679, DOI 10.17487/RFC6679, August
             2012, <http://www.rfc-editor.org/info/rfc6679>.

Baker & Pan Informational [Page 14] RFC 7806 On Queuing, Marking, and Dropping April 2016

 [RFC6928]   Chu, J., Dukkipati, N., Cheng, Y., and M. Mathis,
             "Increasing TCP's Initial Window", RFC 6928,
             DOI 10.17487/RFC6928, April 2013,
             <http://www.rfc-editor.org/info/rfc6928>.
 [RFC7141]   Briscoe, B. and J. Manner, "Byte and Packet Congestion
             Notification", BCP 41, RFC 7141, DOI 10.17487/RFC7141,
             February 2014, <http://www.rfc-editor.org/info/rfc7141>.
 [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>.
 [SFQ]       Mckenney, P., "Stochastic Fairness Queuing", Proceedings
             of IEEE INFOCOM '90, Volume 2, pp. 733-740,
             DOI 10.1109/INFCOM.1990.91316, June 1990,
             <http://www2.rdrop.com/~paulmck/scalability/paper/
             sfq.2002.06.04.pdf>.
 [VirtualClock]
             Zhang, L., "VirtualClock: A New Traffic Control Algorithm
             for Packet Switching Networks", Proceedings of the ACM
             Symposium on Communications Architectures and
             Protocols, Volume 20, DOI 10.1145/99508.99525, September
             1990, <http://dl.acm.org/citation.cfm?id=99508.99525>.

Acknowledgements

 This note grew out of, and is in response to, mailing list
 discussions in AQM, in which some have pushed an algorithm to compare
 to AQM marking and dropping algorithms, but which includes flow
 queuing.

Baker & Pan Informational [Page 15] RFC 7806 On Queuing, Marking, and Dropping April 2016

Authors' Addresses

 Fred Baker
 Cisco Systems
 Santa Barbara, California  93117
 United States
 Email: fred@cisco.com
 Rong Pan
 Cisco Systems
 Milpitas, California  95035
 United States
 Email: ropan@cisco.com

Baker & Pan Informational [Page 16]

/data/webs/external/dokuwiki/data/pages/rfc/rfc7806.txt · Last modified: 2016/04/14 00:45 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki