RFC 3290
An Informal Management Model for Diffserv Routers
RFC 3290: An Informal Management Model for Diffserv Routers 🎀
okay bestie, this is RFC 3290 💅 (part 1 of 13). It's from the Network Working Group and dated May 2002. The authors are Y. Bernet (Microsoft), S. Blake (Ericsson), D. Grossman (Motorola), and A. Smith (Harbour Networks). It's Informational, so it's sharing info with the internet community, not setting a standard. Its header doesn't list anything it obsoletes or updates 🦋
Status of This Memo 🌸
Quick legal-ish vibe check: this memo gives info to the internet community. It does not specify an Internet standard of any kind. Distribution is unlimited 💜
Copyright Notice 🔥
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract ✨
So the big idea is an informal management model for Diffserv routers, aka Differentiated Services routers 🧚 It's meant to help with managing and configuring them. The model names the functional datapath elements (classifiers, meters, actions, marking, absolute dropping, counting, and multiplexing), plus algorithmic droppers, queues, and schedulers. It also describes possible configuration parameters for these elements and how they might be wired together to get the whole range of traffic conditioning and per-hop behavior (PHB) stuff from the Diffserv Architecture. It's giving architecture realness 🙈
Table of Contents 💖
1 Introduction ................................................. 3
2 Glossary ..................................................... 4
3 Conceptual Model ............................................. 7
3.1 Components of a Diffserv Router ............................ 7
3.1.1 Datapath ................................................. 7
3.1.2 Configuration and Management Interface ................... 9
3.1.3 Optional QoS Agent Module ................................ 10
3.2 Diffserv Functions at Ingress and Egress ................... 10
3.3 Shaping and Policing ....................................... 12
3.4 Hierarchical View of the Model ............................. 12
4 Classifiers .................................................. 13
4.1 Definition ................................................. 13
4.1.1 Filters .................................................. 15
4.1.2 Overlapping Filters ...................................... 15
4.2 Examples ................................................... 16
4.2.1 Behavior Aggregate (BA) Classifier ....................... 16
4.2.2 Multi-Field (MF) Classifier .............................. 17
4.2.3 Free-form Classifier ..................................... 17
4.2.4 Other Possible Classifiers ............................... 18
5 Meters ....................................................... 19
5.1 Examples ................................................... 20
5.1.1 Average Rate Meter ....................................... 20
5.1.2 Exponential Weighted Moving Average (EWMA) Meter ......... 21
5.1.3 Two-Parameter Token Bucket Meter ......................... 21
5.1.4 Multi-Stage Token Bucket Meter ........................... 22
5.1.5 Null Meter ............................................... 23
6 Action Elements .............................................. 23
6.1 DSCP Marker ................................................ 24
6.2 Absolute Dropper ........................................... 24
6.3 Multiplexor ................................................ 25
6.4 Counter .................................................... 25
6.5 Null Action ................................................ 25
7 Queuing Elements ............................................. 25
7.1 Queuing Model .............................................. 26
7.1.1 FIFO Queue ............................................... 27
7.1.2 Scheduler ................................................ 28
7.1.3 Algorithmic Dropper ...................................... 30
7.2 Sharing load among traffic streams using queuing ........... 33
7.2.1 Load Sharing ............................................. 34
7.2.2 Traffic Priority ......................................... 35
8 Traffic Conditioning Blocks (TCBs) ........................... 35
8.1 TCB ........................................................ 36
8.1.1 Building blocks for Queuing .............................. 37
8.2 An Example TCB ............................................. 37
8.3 An Example TCB to Support Multiple Customers ............... 42
8.4 TCBs Supporting Microflow-based Services ................... 44
8.5 Cascaded TCBs .............................................. 47
9 Security Considerations ...................................... 47
10 Acknowledgments ............................................. 47
11 References .................................................. 47
Appendix A. Discussion of Token Buckets and Leaky Buckets ...... 50
Authors' Addresses ............................................. 55
Full Copyright Statement........................................ 561. Introduction ✨
Okay so Differentiated Services (Diffserv) [DSARCH] is a set of technologies that lets network service providers offer services with different kinds of network quality-of-service (QoS) objectives to different customers and their traffic streams. This doc uses terminology defined in [DSARCH] and [NEWTERMS]. Some of those definitions are repeated in Section 2 for completeness 🫶
The whole premise is that routers in the core of the network handle packets from different traffic streams by forwarding them with different per-hop behaviors (PHBs). The PHB to use is indicated by a Diffserv codepoint (DSCP) in the IP header of each packet [DSFIELD]. The DSCP markings get applied either by a trusted upstream node (like a customer), or by the edge routers when traffic enters the Diffserv network 🌈
Here's why this is so smart: lots of traffic streams can be aggregated into a small number of behavior aggregates (BAs). Each BA gets forwarded with the same PHB at the router, which keeps processing and storage simple. There's also no signaling beyond what's carried in each packet's DSCP, and no other related processing is required in the core of the Diffserv network, because QoS is invoked on a packet-by-packet basis. Main character energy 👑
The Diffserv architecture makes a bunch of possible services doable on a network. Customers at the edges of the Diffserv network see these services in the form of a Service Level Specification (SLS, see [NEWTERMS]). Further talk about these services is out of scope for this doc (see [PDBDEF]). Still, providing them depends on having cohesive management and configuration tools that can provision and monitor a set of Diffserv routers in a coordinated way 🍓
So to make those tools easier to build, it helps to have a conceptual model of a Diffserv router. The model hides the implementation details of particular routers and keeps only the parameters you actually care about for configuration and management. That's the whole point of this document: defining that model 🦋
The basic forwarding functionality of a Diffserv router is defined in other specs, e.g., [DSARCH, DSFIELD, AF-PHB, EF-PHB] 💅
This doc is not meant to constrain or dictate how Diffserv routers get implemented in any way. Implementers are expected to show a lot of variety in what they build. The more implementers can model their stuff using the abstractions in this doc, the more easily configuration and management tools can configure and manage networks with Diffserv routers from all kinds of origins 🧚
This model is meant to be abstract. It should be able to represent the configuration parameters that matter for Diffserv functionality across a variety of specific router implementations. It's not a guide to building a system, and it's not a formal modeling description either 🙈 It serves as the rationale for the design of an SNMP MIB [DSMIB] and for other configuration interfaces (e.g., other policy-management protocols), and possibly for more detailed formal models (e.g., [QOSDEVMOD]). All of these should be consistent with this model 💖
Here's the roadmap:
- Section 3 starts with the basic high-level blocks of a Diffserv router. It explains the concepts used in the model, including the hierarchical management model for these blocks, which uses low-level functional datapath elements such as Classifiers, Actions, and Queues.
- Section 4 describes Classifier elements.
- Section 5 discusses Meter elements.
- Section 6 discusses Action elements.
- Section 7 discusses the basic queuing elements of Algorithmic Droppers, Queues, and Schedulers, and their functional behaviors (e.g., traffic shaping).
- Section 8 shows how the low-level elements can be combined into modules called Traffic Conditioning Blocks (TCBs), which are useful for management purposes.
- Section 9 discusses security concerns.
- Appendix A has a brief discussion of the token bucket and leaky bucket algorithms used in this model, and some of the practical effects of using token buckets within the Diffserv architecture 🎀
2. Glossary 📖✨
Okay bestie, this doc uses terms that are defined in [DSARCH] 🤓. There's also ongoing work-in-progress on this terminology in the IETF, and some of the definitions here come from that work. A few terms from those other references get defined again here for extra detail, and there are some new terms that are specific to this document 💅
- Absolute Dropper: a functional datapath element that just discards all packets arriving at its input 🗑️
- Algorithmic Dropper: a functional datapath element that selectively discards packets arriving at its input, based on a discarding algorithm. It has one data input and one output 🎯
- Classifier: a functional datapath element made of filters that select matching and non-matching packets. Based on that selection, packets get forwarded along the appropriate datapath within the router. So a Classifier splits one incoming traffic stream into multiple outgoing streams 🧚
- Counter: a functional datapath element that updates a packet counter and an octet counter for every packet that passes through it 🔢
- Datapath: a conceptual path that packets with particular characteristics take through a Diffserv router. The decisions about which path a packet takes are made by functional datapath elements like Classifiers and Meters 🛣️
- Filter: a set of wildcard, prefix, masked, range and/or exact match conditions on the content of a packet's headers or other data, and/or on implicit or derived attributes associated with the packet. A filter only matches if every condition is satisfied 🫶
- Functional Datapath Element: a basic building block of the conceptual router. Typical elements are Classifiers, Meters, Actions, Algorithmic Droppers, Queues and Schedulers 🧩
- Multiplexer (Mux): A multiplexor.
- Multiplexor (Mux): a functional datapath element that merges multiple traffic streams (datapaths) into a single traffic stream (datapath) 🌸
- Non-work-conserving: a property of a scheduling algorithm such that it services packets no sooner than a scheduled departure time, even if this means leaving packets queued while the output (e.g., a network link or connection to the next element) is idle. Iykyk, it's a whole vibe of patience 🐢
- Policing: the process of comparing the arrival of data packets against a temporal profile and forwarding, delaying or dropping them so that the output stream becomes conformant to the profile 👮♀️
- Queuing Block: a combination of functional datapath elements that modulates the transmission of packets belonging to a traffic stream and determines their ordering, possibly storing them temporarily or discarding them 📚
- Scheduling Algorithm: an algorithm that determines which queue, out of a set of queues, gets serviced next. This may be based on the relative priority of the queues, on a weighted fair bandwidth sharing policy, or on some other policy. Such an algorithm may be either work-conserving or non-work-conserving 🗓️
- Service-Level Specification (SLS): a set of parameters and their values which together define the treatment offered to a traffic stream by a Diffserv domain 💜
- Shaping: the process of delaying packets within a traffic stream to cause it to conform to some defined temporal profile. Shaping can be implemented using a queue serviced by a non-work-conserving scheduling algorithm 🌊
- Traffic Conditioning Block (TCB): a logical datapath entity made of a number of functional datapath elements, interconnected in such a way as to perform a specific set of traffic conditioning functions on an incoming traffic stream. You can think of a TCB as an entity with one input and one or more outputs, plus a set of control parameters 🎀
- Traffic Conditioning Specification (TCS): a set of parameters and their values which together specify a set of classifier rules and a traffic profile. A TCS is an integral element of an SLS 🍓
- Work-conserving: a property of a scheduling algorithm such that it services a packet, if one is available, at every transmission opportunity. No wasted turns, periodt 👑
3. Conceptual Model 🧠🩷
Okay so this section introduces a block diagram of a Diffserv router and walks through the components shown in Figure 1 🦋. Heads up: a Diffserv core router is probably only going to need a subset of these components. The model here is meant to cover both Diffserv edge and core routers, so it's giving full coverage 🫧
3.1. Components of a Diffserv Router 🔧
The conceptual model includes abstract definitions for the following:
- Traffic Classification elements. 🏷️
- Metering functions. 📏
- Actions of Marking, Absolute Dropping, Counting, and Multiplexing. ✨
- Queuing elements, including capabilities of algorithmic dropping and scheduling. 🚦
- Certain combinations of the above functional datapath elements into higher-level blocks known as Traffic Conditioning Blocks (TCBs). 🧱
The components, and combinations of components, described in this document form building blocks that need to be manageable by Diffserv configuration and management tools 🛠️ One of the goals of this document is to show how a model of a Diffserv device can be built out of these component blocks. The model is a connected directed acyclic graph (DAG) of functional datapath elements, and it describes the traffic conditioning and queuing behaviors that any particular packet will experience when forwarded to the Diffserv router 🕸️ Figure 1 illustrates the major functional blocks of a Diffserv router 👀
3.1.1. Datapath 🛤️
An ingress interface, routing core, and egress interface are illustrated at the center of the diagram. In real router implementations there can be an arbitrary number of ingress and egress interfaces, all interconnected by the routing core 🔌 The routing core element is an abstraction of a router's normal routing and switching functionality. It moves packets between interfaces according to policies that are outside the scope of Diffserv (note: it's possible that such policies for output-interface selection might involve packet fields such as the DSCP, but that's outside the scope of this model). The actual queuing delay and packet loss behavior of a specific router's switching fabric/backplane is not modeled by the routing core; those should be modeled using the functional datapath elements described later 🙅♀️
The routing core of this model can be thought of as an infinite bandwidth, zero-delay interconnect between interfaces. Properties like the behavior of the core when it's overloaded need to be reflected back into the queuing elements modeled around it. For example, when too much traffic is directed across the core at an egress interface, the excess must either be dropped or queued somewhere, and the elements performing those functions must be modeled on one of the interfaces involved 😭💅
The components of interest at the ingress to and egress from interfaces are the functional datapath elements (e.g., Classifiers, Queuing elements) that support Diffserv traffic conditioning and per-hop behaviors [DSARCH]. These are the fundamental components that make up a Diffserv router, and they're the focal point of this model 💖
+---------------+
| Diffserv |
Mgmt | configuration |
<----+-->| & management |------------------+
SNMP,| | interface | |
COPS | +---------------+ |
etc. | | |
| | |
| v v
| +-------------+ +-------------+
| | ingress i/f | +---------+ | egress i/f |
-------->| classify, |-->| routing |-->| classify, |---->
data | | meter, | | core | | meter |data out
in | | action, | +---------+ | action, |
| | queuing | | queuing |
| +-------------+ +-------------+
| ^ ^
| | |
| | |
| +------------+ |
+-->| QOS agent | |
-------->| (optional) |---------------------+
QOS |(e.g., RSVP)|
cntl +------------+
msgs
Figure 1: Diffserv Router Major Functional Blocks3.1.2. Configuration and Management Interface 🎛️
Diffserv operating parameters get monitored and provisioned through this interface 📊 The monitored parameters include statistics about traffic carried at the various Diffserv service levels. These stats may be important for accounting purposes and/or for tracking compliance with Traffic Conditioning Specifications (TCSs) negotiated with customers 💸 The provisioned parameters are mainly the TCS parameters for Classifiers and Meters, plus the associated PHB configuration parameters for Actions and Queuing elements 🧁 The network administrator interacts with the Diffserv configuration and management interface through one or more management protocols, such as SNMP or COPS, or through other router configuration tools such as serial terminal or telnet consoles 🖥️
Specific policy rules and goals governing the Diffserv behavior of a router are presumed to be installed by policy management mechanisms 📜 That said, Diffserv routers are always subject to implementation limits, and those limits scope the kinds of policies the router can successfully implement 🚧 External reporting of such implementation capabilities is considered out of scope for this document 🙈
Okay so this part picks up right where section 3.1.2 left off, bestie 🎀 Let's get into the QoS agent, the sneaky-but-spicy bit where routers can peek at reservation signalling 👀
3.1.3. Optional QoS Agent Module ✨
Okay so Diffserv routers are allowed to snoop on, or actually take part in, QoS requirement signalling, whether that's per-microflow or per-flow-aggregate 🦋 [E2E]. RSVP is the classic example 💅 Snooping on RSVP messages is a super useful move, because a router can learn how to classify traffic without ever being a full RSVP protocol peer. Lowkey genius 🧚
Diffserv routers can also reject or admit RSVP reservation requests, which gives them a way to do admission control for Diffserv-based services 🔥 Or they can use those requests as a trigger to change provisioning for a flow-aggregation in the Diffserv network. A flow-aggregation here might be basically the same thing as a Diffserv BA, or it might be more fine-grained and rely on a multi-field (MF) classifier [DSARCH]. Main character energy, no cap 👑
Also, the conceptual model of a router like this implements the Integrated Services Model from [INTSERV]. It applies the control plane controls to data that's been classified and conditioned in the data plane, as described in [E2E] 💜 Iykyk.
Now, a QoS Agent component might, if it's there at all, be active only in the control plane and not in the data plane 🌸 In that case RSVP can be used just to signal reservation state, without installing any actual reservations in the data plane. The data plane can still act purely on Diffserv DSCPs and provide PHBs for handling data traffic, without the normal per-microflow handling that some Intserv services are expected to need. It's giving minimalist but still gets the job done ✨
3.2. Diffserv Functions at Ingress and Egress 🎀
Okay so this document is focused on the Diffserv-specific parts of the router 💖 Figure 2 gives a high-level view of a router's ingress and egress interfaces. The diagram shows two Diffserv router interfaces, and each one has a set of ingress elements and a set of egress elements. It shows the classification, metering, action and queuing functions that might be set up at each interface's ingress and egress 🦋
Interface A Interface B
+-------------+ +---------+ +-------------+
| ingress: | | | | egress: |
| classify, | | | | classify, |
--->| meter, |---->| |---->| meter, |--->
| action, | | | | action, |
| queuing | | routing | | queuing |
+-------------+ | core | +-------------+
| egress: | | | | ingress: |
| classify, | | | | classify, |
<---| meter, |<----| |<----| meter, |<---
| action, | | | | action, |
| queuing | +---------+ | queuing |
+-------------+ +-------------+
Figure 2. Traffic Conditioning and Queuing ElementsThe simple diagram of Figure 2 assumes that the Diffserv functions applied to traffic on one interface are independent of the functions on every other interface 🌈 Some architectures let Diffserv functions be shared across multiple interfaces, though. For example, processor and buffering resources might handle several interfaces on the same line card before forwarding across a routing core 🍓 The model in this document can be easily extended to handle that, but this document doesn't dig into it, because it would make the explanation of the concepts way too complicated 🙈
Here's the big idea: if you built a network entirely out of two-port routers (connected by LANs or similar media), each router might need four QoS control functions in the datapath, for traffic in each direction:
- Classify each message according to some set of rules, which could possibly just be a "match everything" rule 🫶
- If necessary, work out whether the data stream the message belongs to is within or outside its rate, by metering the stream 📏
- Carry out a set of resulting actions. These can include applying a drop policy that fits the classification and queue in question, and maybe also marking the traffic with a Differentiated Services Code Point (DSCP) [DSFIELD] 💅
- Enqueue the traffic for output in the right queue. Scheduling output from that queue might lead to shaping of the traffic, or it might just forward it with some minimum rate or maximum latency assurance ✨
If the network is built out of N-port routers instead, the network should behave the same way. So this model has to provide basically the same set of functions at a router's ingress as at its egress 💖 The one difference is that all traffic at an interface's egress gets queued, while traffic at its ingress is only likely to be queued for shaping purposes, if at all 🦋 That means equivalent functional datapath elements can be modeled at both the ingress and the egress of an interface.
Note that each of these functional datapath elements doesn't have to be implemented at both ingress and egress 💜 The model also allows multiple sets of these elements to be placed in series and/or in parallel at ingress or egress. Which arrangement you pick depends on the service requirements for a particular interface on a particular router 🎀 Modeling these elements at both ingress and egress doesn't mean a specific router has to implement them that way. For example, a router might do all shaping and PHB queuing at the interface egress, or it might do it only at the ingress 🌸 Also, the classification needed to map a packet to an egress queue (if there is one) doesn't have to happen at the egress. It could happen at the ingress instead, with the packet passed through the routing core along with in-band control information so the egress queue can be selected ✨
Some interfaces will be at the outer "edge" of the Diffserv domain, and some will be toward the "core". Given the general principles behind Diffserv's motivation, you'd expect "edge" interfaces, or at least the routers that contain them, to have more complexity and need more configuration than core ones 👑 Obviously this isn't a hard requirement, though 🙈
3.3. Shaping and Policing 💅
Diffserv nodes may apply shaping, policing and/or marking to traffic streams that go over the bounds of their TCS 🔥 The goal is to stop one traffic stream from grabbing more than its fair share of resources in a Diffserv network. In this model, shaping (sometimes thought of as a TC action) is treated as a function of queuing elements; see section 7 🦋 Algorithmic Dropping techniques (e.g., RED) get the same treatment, since they're often closely tied to queues 💖 Policing is modeled either as a Meter concatenated with an Absolute Dropper, or as an Algorithmic Dropper concatenated with a Scheduler 🫶 These elements will discard packets that exceed the TCS 🌈
3.4. Hierarchical View of the Model 🧚
From a device-level configuration management perspective, there's this hierarchy 🎀
At the lowest level considered here, there are individual functional datapath elements, each with their own configuration parameters and management counters and flags.
At the next level, the network administrator manages groupings of these functional datapath elements interconnected in a DAG. These functional datapath elements are organized in self-contained TCBs, which are used to implement some desired network policy (see Section 8). One or more TCBs may be instantiated at each interface's ingress or egress. They may be connected in series and/or in parallel configurations on the multiple outputs of a preceding TCB. A TCB can be thought of as a "black box" with one input and one or more outputs (in the data path). Each interface may have a different TCB configuration, and each direction (ingress or egress) may too 💜
At the topmost level considered here, the network administrator manages interfaces. Each interface has ingress and egress functionality, with each of these expressed as one or more TCBs. This level of the hierarchy is what was illustrated in Figure 2 ✨
Further levels may be built on top of this hierarchy, especially ones that help with the repetitive configuration tasks likely for routers with many interfaces 🌸 Some such "template" tools for Diffserv routers are outside the scope of this model, but other IETF working groups are studying them 👀
4. Classifiers ⭐
4.1. Definition 🦋
Classification is performed by a classifier element 💖 Classifiers are 1:N (fan-out) devices: they take a single traffic stream as input and generate N logically separate traffic streams as output 🫶 Classifiers are parameterized by filters and output streams. Packets from the input stream are sorted into various output streams by filters that match the contents of the packet, or possibly match other attributes associated with the packet 🎀 Different types of classifiers using different filters are described in the following sections. Figure 3 shows a classifier, where the outputs connect to the succeeding functional datapath elements 🌈
The simplest possible Classifier element matches all packets applied at its input. In that case the Classifier element is just a no-op and may be omitted 🙈
Note that we allow a Multiplexor (see Section 6.5) before the Classifier, so it can take input from multiple traffic streams 🍓 For example, if traffic streams from multiple ingress interfaces feed through a single Classifier, then the interface number could be one of the packet classification keys that Classifier uses. This optimization may be important for scalability in the management plane 💅 Classifiers may also be cascaded in sequence to perform more complex lookup operations while still keeping that scalability ✨
Another example of a packet attribute could be an integer representing the BGP community string associated with the packet's best-matching route 🦋 Other contextual information can also be used by a Classifier. For example, knowing that a particular interface faces a Diffserv domain, or a legacy IP TOS domain [DSARCH], could help when deciding whether a DSCP is present 💜
unclassified classified
traffic traffic
+------------+
| |--> match Filter1 --> OutputA
------->| classifier |--> match Filter2 --> OutputB
| |--> no match --> OutputC
+------------+
Figure 3. An Example ClassifierThe following BA classifier separates traffic into one of three output streams, based on matching filters 🌸
Filter Matched Output Stream
-------------- ---------------
Filter1 A
Filter2 B
no match CWhere the filters are defined to be the following BA filters ([DSARCH], Section 4.2.1) 🎀
Filter DSCP
------ ------
Filter1 101010
Filter2 111111
Filter3 ****** (wildcard)4.1.1. Filters ✨
A filter is basically a bouncer's checklist 💅. It's a set of conditions on the component values of a packet's classification key (the header values, contents, and attributes relevant for classification). In the BA classifier example above, the classification key is just one header field, the DSCP, and both Filter1 and Filter2 do exact-match checks on the DSCP value. Filter3 is a wildcard default filter that matches every packet, but it only gets picked if no other, more specific filter matches 🫶.
In general, the possible component conditions include exact, prefix, range, masked and wildcard matches. Ranges can be written as a set of prefixes (less efficient, though 💀), and prefix matches are really just a special case of both masked and range matches. It's giving matryoshka doll energy 🪆.
For an MF classifier, the classification key is made of several packet header fields, and the filter can set a different condition for each key component. Here's Filter4 for an IPv4/TCP classifier:
Filter IPv4 Src Addr IPv4 Dest Addr TCP SrcPort TCP DestPort
------ ------------- -------------- ----------- ------------
Filter4 172.31.8.1/32 172.31.3.X/24 X 5003In this example, the fourth octet of the destination IPv4 address and the source TCP port are wildcard or "don't care" 🦋.
⚠️ MF classification of IP-fragmented packets is impossible if the filter uses transport-layer port numbers (e.g., TCP port numbers). MTU-discovery is therefore a prerequisite for proper operation of a Diffserv network that uses such classifiers. No skipping this step, bestie 🙈.
4.1.2. Overlapping Filters
It is super easy to define sets of overlapping filters in a classifier, so watch out 👀. For example:
Filter IPv4 Src Addr IPv4 Dest Addr
------ ------------- --------------
Filter5 172.31.8.X/24 X/0
Filter6 X/0 172.30.10.1/32A packet containing {IP Dest Addr 172.31.8.1, IP Src Addr 172.30.10.1} cannot be uniquely classified by this pair of filters, so a precedence must be established between Filter5 and Filter6 to break the tie 💜. This precedence must be established either (a) by a manager which knows that the router can accomplish this particular ordering (e.g., by means of reported capabilities), or (b) by the router along with a mechanism to report to a manager which precedence is being used. Such precedence mechanisms must be supported in any translation of this model into specific syntax for configuration and management protocols.
Another example: one might want to first disallow certain applications from using the network at all, or to classify some individual traffic streams that are not Diffserv-marked. Traffic that is not classified by those tests might then be inspected for a DSCP. The word "then" implies sequence, and this must be specified by means of precedence ⏳.
An unambiguous classifier requires that every possible classification key match at least one filter (possibly the wildcard default) and that any ambiguity between overlapping filters be resolved by precedence. So the classifiers on any given interface must be "complete," and they will often include an "everything else" filter as the lowest precedence element so the result of classification is deterministic 🎯. Note that this completeness is only required of the first classifier that incoming traffic will meet as it enters an interface. Subsequent classifiers on an interface only need to handle the traffic that it is known they will receive 🌸.
This model of classifier operation assumes that all filters of the same precedence are applied simultaneously. This is super convenient from a modeling point of view, but it may or may not be how the classifier is actually implemented. This assumption is not meant to dictate how the implementation handles it, only to clearly define the required end result 🧚.
4.2. Examples
4.2.1. Behavior Aggregate (BA) Classifier
The simplest Diffserv classifier is a behavior aggregate (BA) classifier [DSARCH]. A BA classifier uses only the Diffserv codepoint (DSCP) in a packet's IP header to determine the logical output stream the packet should be directed to. We allow only an exact-match condition on this field, because the assigned DSCP values have no structure, so no subset of DSCP bits is significant 💅.
The following defines a possible BA filter:
Filter8:
Type: BA
Value: 1110004.2.2. Multi-Field (MF) Classifier
Another type of classifier is a multi-field (MF) classifier [DSARCH]. This classifies packets based on one or more fields in the packet (possibly including the DSCP). A common type of MF classifier is a 6-tuple classifier that classifies based on six fields from the IP and TCP or UDP headers (destination address, source address, IP protocol, source port, destination port, and DSCP). MF classifiers may classify on other fields such as MAC addresses, VLAN tags, link-layer traffic class fields, or other higher-layer protocol fields 🌈.
The following defines a possible MF filter:
Filter9:
Type: IPv4-6-tuple
IPv4DestAddrValue: 0.0.0.0
IPv4DestAddrMask: 0.0.0.0
IPv4SrcAddrValue: 172.31.8.0
IPv4SrcAddrMask: 255.255.255.0
IPv4DSCP: 28
IPv4Protocol: 6
IPv4DestL4PortMin: 0
IPv4DestL4PortMax: 65535
IPv4SrcL4PortMin: 20
IPv4SrcL4PortMax: 20A similar type of classifier can be defined for IPv6 ✨.
4.2.3. Free-form Classifier
A Free-form classifier is made up of a set of user-definable arbitrary filters, each made up of {bit-field size, offset (from head of packet), mask} 🎀:
Classifier2:
Filter12: OutputA
Filter13: OutputB
Default: OutputC
Filter12:
Type: FreeForm
SizeBits: 3 (bits)
Offset: 16 (bytes)
Value: 100 (binary)
Mask: 101 (binary)
Filter13:
Type: FreeForm
SizeBits: 12 (bits)
Offset: 16 (bytes)
Value: 100100000000 (binary)
Mask: 111111111111 (binary)Free-form filters can be combined into filter groups to form very powerful filters 👑.
4.2.4. Other Possible Classifiers
Classification may also be performed based on information at the datalink layer below IP (e.g., VLAN or datalink-layer priority), or perhaps on the ingress or egress IP, logical or physical interface identifier (e.g., the incoming channel number on a channelized interface). A classifier that filters based on IEEE 802.1p Priority and on 802.1Q VLAN-ID might be represented as:
Classifier3:
Filter14 AND Filter15: OutputA
Default: OutputB
Filter14: -- priority 4 or 5
Type: Ieee8021pPriority
Value: 100 (binary)
Mask: 110 (binary)
Filter15: -- VLAN 2304
Type: Ieee8021QVlan
Value: 100100000000 (binary)
Mask: 111111111111 (binary)Such classifiers may be the subject of other standards or may be proprietary to a router vendor, but they are not discussed further here 🫶.
5. Meters
Metering is defined in [DSARCH]. Diffserv network providers may choose to offer services to customers based on a temporal (i.e., rate) profile within which the customer submits traffic for the service. In this event, a meter might be used to trigger real-time traffic conditioning actions (e.g., marking) by routing a non-conforming packet through an appropriate next-stage action element. Alternatively, by counting conforming and/or non-conforming traffic using a Counter element downstream of the Meter, it might also be used to help collect data for out-of-band management functions such as billing applications 💰.
Meters are logically 1:N (fan-out) devices (although a multiplexor can be used in front of a meter). Meters are parameterized by a temporal profile and by conformance levels, each of which is associated with a meter's output. Each output can be connected to another functional element 🦋.
Note that this model of a meter differs slightly from the one described in [DSARCH]. In that description, the meter is not a datapath element. Instead, it is used to monitor the traffic stream and send control signals to action elements to dynamically modulate their behavior based on the conformance of the packet. This difference in description does not change the function of a meter 🙃. Figure 4 illustrates a meter with 3 levels of conformance.
In some Diffserv examples (e.g., [AF-PHB]), three levels of conformance are discussed in terms of colors: green representing conforming, yellow representing partially conforming, and red representing non-conforming. These conformance levels may be used to trigger different queuing, marking or dropping treatment later on in the processing 🚦. Other example meters use a binary notion of conformance, but in the general case N levels of conformance can be supported. In general there is no constraint on the type of functional datapath element following a meter output, but care must be taken not to inadvertently configure a datapath that results in packet reordering that is not consistent with the requirements of the relevant PHB specification ⚠️.
unmetered metered
traffic traffic
+---------+
| |--------> conformance A
--------->| meter |--------> conformance B
| |--------> conformance C
+---------+Figure 4. A Generic Meter
A meter, according to this model, measures the rate at which packets making up a stream of traffic pass it, compares the rate to some set of thresholds, and produces some number of potential results (two or more). A given packet is said to be "conformant" to a level of the meter if, at the time the packet is being examined, the stream appears to be within the rate limit for the profile associated with that level. A fuller discussion of conformance to meter profiles (and the associated requirements this places on the schedulers upstream) is provided in Appendix A 📚.
5.1. Examples
The following are some examples of possible meters 🌟.
5.1.1. Average Rate Meter
An example of a very simple meter is an average rate meter. This type of meter measures the average rate at which packets are submitted to it over a specified averaging time ⏱️.
An average rate profile may take the following form:
Meter1:
Type: AverageRate
Profile: Profile1
ConformingOutput: Queue1
NonConformingOutput: Counter1
Profile1:
Type: AverageRate
AverageRate: 120 kbps
Delta: 100 msecA Meter measuring against this profile would continually maintain a count that indicates the total number and/or cumulative byte-count of packets arriving between time T (now) and time T - 100 msecs. So long as an arriving packet does not push the count over 12 kbits in the last 100 msec, the packet would be deemed conforming. Any packet that pushes the count over 12 kbits would be deemed non-conforming. Thus, this Meter deems packets to correspond to one of two conformance levels, conforming or non-conforming, and sends them on for the appropriate subsequent treatment 💖.
5.1.2. Exponential Weighted Moving Average (EWMA) Meter
okay so the EWMA meter is literally so easy to build in hardware, no cap 🔥 and it's parameterized like this:
avg_rate(t) = (1 - Gain) * avg_rate(t') + Gain * rate(t)
t = t' + DeltaFor a packet arriving at time t:
if (avg_rate(t) > AverageRate)
non-conforming
else
conforming"Gain" controls the time constant (e.g., frequency response) of what is basically a simple IIR low-pass filter 💅. "Rate(t)" counts the incoming bytes in a small fixed sampling interval, Delta. Any packet that arrives and pushes the average rate over the predefined rate AverageRate gets marked non-conforming 🙈. An EWMA Meter profile might look something like this:
Meter2:
Type: ExpWeightedMovingAvg
Profile: Profile2
ConformingOutput: Queue1
NonConformingOutput: AbsoluteDropper1
Profile2:
Type: ExpWeightedMovingAvg
AverageRate: 25 kbps
Delta: 10 usec
Gain: 1/165.1.3. Two-Parameter Token Bucket Meter
a more sophisticated Meter can check conformance against a token bucket (TB) profile 🪣✨. A TB profile usually has two parameters: an average token rate, R, and a burst size, B. TB Meters compare the arrival rate of packets to the average rate in the TB profile. Logically, tokens pile up in a bucket at the average rate, R, up to a maximum credit, which is the burst size, B. When a packet of length L arrives, a conformance test runs. There are at least two such tests in widespread use:
Strict conformance : Packets of length L bytes are conforming only if there are enough tokens in the bucket at the moment the packet arrives to cover the whole packet (so the current depth is greater than or equal to L). No tokens may be borrowed from future token allocations. For examples of this approach, see [SRTCM] and [TRTCM].
Loose conformance : Packets of length L bytes are conforming if any tokens are available in the bucket when the packet arrives. Up to L bytes may then be borrowed from future token allocations.
Packets can go over the average rate in bursts, up to the burst size 🌊. For more on loose and strict conformance to token bucket profiles, plus system and implementation issues, see Appendix A.
A two-parameter TB meter has exactly two possible conformance levels: conforming and non-conforming. It might look like this:
Meter3:
Type: SimpleTokenBucket
Profile: Profile3
ConformanceType: loose
ConformingOutput: Queue1
NonConformingOutput: AbsoluteDropper1
Profile3:
Type: SimpleTokenBucket
AverageRate: 200 kbps
BurstSize: 100 kbytes5.1.4. Multi-Stage Token Bucket Meter
fancier TB meters can define multiple burst sizes and more conformance levels 🎀. Packets that exceed the larger burst size are non-conforming. Packets that exceed the smaller burst size are partially-conforming. Packets that exceed neither are conforming. Some token bucket meters built for Diffserv networks are covered in more detail in [SRTCM, TRTCM]. In some of those references, the three conformance levels are described as colors: green for conforming, yellow for partially conforming, and red for non-conforming 🚦. Also, these multiple-conformance-level meters can sometimes be built from a suitable sequence of several two-parameter TB meters.
a profile for a multi-stage TB meter with three conformance levels might look like this:
Meter4:
Type: TwoRateTokenBucket
ProfileA: Profile4
ConformanceTypeA: strict
ConformingOutputA: Queue1
ProfileB: Profile5
ConformanceTypeB: strict
ConformingOutputB: Marker1
NonConformingOutput: AbsoluteDropper1
Profile4:
Type: SimpleTokenBucket
AverageRate: 100 kbps
BurstSize: 20 kbytes
Profile5:
Type: SimpleTokenBucket
AverageRate: 100 kbps
BurstSize: 100 kbytes5.1.5. Null Meter
the Null Meter is the chill one 🧘♀️. It has only one output, it's always conforming, and it has no temporal profile attached. It's handy to define in case your configuration or management interface isn't flexible enough to leave a meter out of a datapath segment.
Meter5:
Type: NullMeter
Output: Queue16. Action Elements
okay, so the classifiers and meters we've covered so far are fan-out elements. They're mostly used to figure out which action to apply to a packet 🎯. The actions that can then be applied include:
- Marking
- Absolute Dropping
- Multiplexing
- Counting
- Null action - do nothing
the corresponding action elements get their own sections below 💖.
6.1. DSCP Marker
DSCP Markers are 1:1 elements that set a codepoint (like the DSCP in an IP header) 🏷️. They can act on unmarked packets too (for example, ones sent with a DSCP of zero), or they can re-mark packets that were already marked. The model supports applying a mark based on a preceding classifier match, which is so iconic 👑. The mark on a packet decides its later PHB treatment at downstream nodes in the network, and maybe also in later processing stages inside this router.
DSCP Markers for Diffserv usually take just one parameter: the 6-bit DSCP to mark in the packet header.
Marker1:
Type: DSCPMarker
Mark: 0100106.2. Absolute Dropper
Absolute Droppers just throw packets away 🗑️. They have no parameters. Since an Absolute Dropper is a terminating point of the datapath and has no outputs, it's probably a good idea to send the packet through a Counter Action first for instrumentation purposes 📊.
AbsoluteDropper1:
Type: AbsoluteDropperAbsolute Droppers aren't the only elements that can make a packet get discarded. Another one is the Algorithmic Dropper element (see Section 7.1.3). But because this element's behavior is closely tied to the state of one or more queues, we chose to treat it as its own separate functional datapath element 🧠.
6.3. Multiplexor
sometimes you need to squeeze several traffic streams into one functional datapath element that has a single input 🧵. An M:1 (fan-in) multiplexor is a simple logical device for merging traffic streams. It's parameterized by its number of incoming ports.
Mux1:
Type: Multiplexor
Output: Queue26.4. Counter
one passive action is just accounting for the fact that a data packet got processed 🔢. The resulting statistics might later be used for customer billing, service verification, or network engineering purposes 💸. Counters are 1:1 functional datapath elements. Every time a L-byte sized packet passes through, they update a counter by L and a packet counter by 1. Counters can count packets that are about to be dropped by an Absolute Dropper, or count packets arriving at or leaving some other functional element 📈.
Counter1:
Type: Counter
Output: Queue16.5. Null Action
a null action has one input and one output, and it does absolutely nothing to the packet 😌. It's useful to define in case your configuration or management interface doesn't have the flexibility to leave out an action element in a datapath segment.
Null1:
Type: Null
Output: Queue17. Queuing Elements
queuing elements are the ones that control the pace of packets from the different traffic streams, decide their order, and maybe store them for a bit or throw them away 🚦. Packets usually get stored either because a resource constraint (like available bandwidth) stops them from going out immediately, or because the queuing block is used to change the timing of a traffic stream (that's shaping) ⏳. Packets get discarded for one of these reasons:
- because of buffering limitations.
- because a buffer threshold is exceeded (including when shaping is performed).
- as a feedback control signal to reactive control protocols such as TCP.
- because a meter exceeds a configured profile (i.e., policing).
the queuing elements in this model are a logical abstraction of a queuing system, used to configure PHB-related parameters 🎀. The model can represent a huge variety of implementations. But it doesn't have to map one-to-one onto the physical queuing systems in a particular router. Implementors should map the configurable parameters of their implementation's queuing systems onto these queuing element parameters, as appropriate, to get equivalent behaviors 🫶.
7.1. Queuing Model
queuing is a function that invites innovation 🧪. It needs to be modeled so that a broad range of possible implementations can be represented with common structures and parameters. This model uses functional decomposition as a tool to give the needed latitude.
queuing systems do three distinct but related jobs: they store packets, they modulate the departure of packets from various traffic streams, and they selectively discard packets 💅. This model breaks queuing down into the component elements that do each of those jobs: Queues, Schedulers, and Algorithmic Droppers, respectively. These elements can be connected together as part of a TCB, as described in section 8 🧩.
The rest of this section talks about FIFO Queues. Typically, the Queue element in this model will be implemented as a FIFO data structure. But that doesn't rule out implementations that aren't strictly FIFO, as long as they also support operations that remove or examine packets (for example, for use by discarders) somewhere other than the head or tail. However, those operations must not have the effect of reordering packets that belong to the same microflow ⚠️.
the term FIFO has a bunch of different common meanings. Sometimes it means a data structure where items can only be removed in the order they were inserted, and sometimes it means a service discipline that doesn't reorder things. It's giving confusing, so keep that in mind 🙈.
7.1.1. FIFO Queue ✨
Okay bestie, a FIFO Queue element is a data structure 🫶 that can hold zero or more packets at any moment. It can have one or more thresholds attached to it. A FIFO has one or more inputs but exactly one output 💅. It must support an enqueue operation to add a packet to the tail of the queue, and a dequeue operation to remove a packet from the head of the queue. Packets must be dequeued in the order in which they were enqueued. First in, first out, that's literally the whole name 😭. A FIFO has a current depth, which is the number of packets and/or bytes it's holding at any given time 🧚.
FIFOs in this model have no built-in depth limits. Obviously real implementations do have them, so size limits are modeled by an algorithmic dropper attached to the FIFO, typically at its input 🌸. It is quite likely that every FIFO will be preceded by an algorithmic dropper. One exception might be where the packet stream has already been policed to a profile that can never exceed the scheduler bandwidth available at the FIFO's output. In that case, the FIFO doesn't need an algorithmic dropper at its input 🦋.
This representation allows for one common type of depth limit: the kind that comes from a FIFO being supplied by a limited pool of buffers, shared between multiple FIFOs 💜.
In an implementation, packets are presumably stored in one or more buffers. Those buffers are allocated from one or more free buffer pools. If there are multiple instances of a FIFO, their packet buffers may or may not come out of the same free buffer pool. Free buffer pools may also have one or more thresholds associated with them, which can affect discarding and/or scheduling. Other than this, buffering mechanisms are implementation specific and not part of this model 🍓.
A FIFO might be represented using the following parameters:
Queue1:
Type: FIFO
Output: Scheduler1Note that a FIFO must provide triggers and/or current state information to other elements upstream and downstream from it. In particular, it is likely that the current depth will need to be used by Algorithmic Dropper elements placed before or after the FIFO. It will also likely need to provide an implicit "I have packets for you" signal to downstream Scheduler elements 📣.
7.1.2. Scheduler 👑
A scheduler is an element that gates the departure of each packet arriving at one of its inputs, based on a service discipline. It has one or more inputs and exactly one output. Each input has an upstream element it's connected to, plus a set of parameters that affects how packets received at that input get scheduled 🎀.
The service discipline (also known as a scheduling algorithm) is an algorithm that might take any of the following as its input(s):
- a) static parameters, such as the relative priority associated with each of the scheduler's inputs.
- b) absolute token bucket parameters for maximum or minimum rates associated with each of the scheduler's inputs.
- c) parameters, such as packet length or DSCP, associated with the packet currently present at its input.
- d) absolute time and/or local state.
Possible service disciplines fall into a bunch of categories, including (but not limited to) first come, first served (FCFS), strict priority, weighted fair bandwidth sharing (e.g., WFQ), rate-limited strict priority, and rate-based. Service disciplines can also be split by whether they are work-conserving or non-work-conserving (see Glossary) 🌈. Non-work-conserving schedulers can be used to shape traffic streams so they match some profile, by delaying packets that might be deemed non-conforming by some downstream node. A packet is delayed until such time as it would conform to a downstream meter using the same profile ⭐.
[DSARCH] defines PHBs without specifying required scheduling algorithms. However, PHBs such as the class selectors [DSFIELD], EF [EF-PHB] and AF [AF-PHB] have descriptions or configuration parameters that strongly suggest the sort of scheduling discipline needed to implement them. This document discusses a minimal set of queue parameters to enable realization of these PHBs. It does not attempt to specify an all-embracing set of parameters to cover every possible implementation model. A minimal set includes:
- a) a minimum service rate profile, which allows rate guarantees for each traffic stream as required by EF and AF, without specifying the details of how excess bandwidth between these traffic streams is shared. Additional parameters to control this behavior should be made available, but they depend on the particular scheduling algorithm implemented.
- b) a service priority, used only after the minimum rate profiles of all inputs have been satisfied, to decide how to allocate any remaining bandwidth.
- c) a maximum service rate profile, for use only with a non-work-conserving service discipline.
For the purposes of this model, any one of these profiles is composed of both a rate (in suitable units of bits, bytes or larger chunks in some unit of time) and a burst size, as discussed further in Appendix A 🧁.
By way of example, take an implementation of the EF PHB using a strict priority scheduling algorithm that assumes the aggregate EF rate has been appropriately bounded by upstream policing, so it doesn't starve other BAs. Here the service rate profiles aren't used at all: the minimum service rate profile would default to zero, and the maximum service rate profile would effectively be the "line rate". Such an implementation, with multiple priority classes, could also be used for the Diffserv class selectors [DSFIELD] 💖.
Alternatively, setting the service priority values for each input to the scheduler to the same value lets the scheduler satisfy the minimum service rates for each input, so long as the sum of all minimum service rates is less than or equal to the line rate 🔥.
For example, a non-work-conserving scheduler allocating spare bandwidth equally between all its inputs might be represented using the following parameters:
Scheduler1:
Type: Scheduler2Input
Input1:
MaxRateProfile: Profile1
MinRateProfile: Profile2
Priority: none
Input2:
MaxRateProfile: Profile3
MinRateProfile: Profile4
Priority: noneA work-conserving scheduler might be represented using the following parameters:
Scheduler2:
Type: Scheduler3Input
Input1:
MaxRateProfile: WorkConserving
MinRateProfile: Profile5
Priority: 1
Input2:
MaxRateProfile: WorkConserving
MinRateProfile: Profile6
Priority: 2
Input3:
MaxRateProfile: WorkConserving
MinRateProfile: none
Priority: 37.1.3. Algorithmic Dropper ✨
okay so an Algorithmic Dropper is the element that selectively throws packets away based on a discarding algorithm 🗑️💅 it has one data input and one output. In this model (not necessarily in a real implementation, fr), a packet hits the dropper at its input, and then either its buffer goes back to a free buffer pool or the packet comes out the output 🦋
Another way to picture it: the dropper is basically doing operations on a FIFO Queue, picking out a packet and returning its buffer to the free buffer pool based on the discarding algorithm. Here the operation could be modeled as a side-effect on the FIFO it's acting on, instead of having a discrete input and output. Both treatments are equivalent, but we're going with the one from the paragraph above for this model 🫶
The big question for an Algorithmic Dropper is which packet gets dropped (if any) 👀 For this model, we only allow one of two selection choices, and you can tell which one is in play by where the Algorithmic Dropper and the FIFO Queue sit relative to each other:
a) Tail Dropper: the dropper picks a packet that's about to join the tail of a queue. The output of the Algorithmic Dropper connects to the input of the relevant FIFO Queue.
b) Head Dropper: the dropper picks a packet that's already sitting at the head of a queue. The output of the FIFO Queue connects to the input of the Algorithmic Dropper.
Other packet selection methods could be added to this model later, as a different type of datapath element 🌈
The Algorithmic Dropper is modeled with a single input. Packets that were classified differently by a Classifier in this TCB can still end up going through the same dropper 🧚 The dropper's algorithm might need to do different math depending on stuff about the incoming packet (like its DSCP). So implementations of this model need a way to connect which classifier element a packet matched to the Algorithmic Dropper. For the rare times that's needed, the chosen approach is to drop in another Classifier element at this point in the flow, feeding into multiple Algorithmic Droppers. Each of those droppers runs a drop calculation that doesn't depend on any classification keys of the packet. This will likely mean creating a new TCB to hold the Classifier and the Algorithmic Dropper elements 🎀
NOTE: there are lots of other ways to model this linkage, honestly. One option would be a pointer from one of the drop probability calculation algorithms inside the dropper back to the original Classifier element that picked that algorithm. Another would be multiple "inputs" to the Algorithmic Dropper, fed from the preceding elements and eventually leading back to the Classifier elements that matched the packet. Yet another would be for the Classifier to (logically) attach some sort of "classification identifier" to the packet as it travels its path, for any later element to use. And one more would be putting a classifier inside the dropper so it can pick out the drop algorithm to apply. Implementations could use these other approaches, but they were judged less clear than the one we picked 🤓
An Algorithmic Dropper, with an example shown in Figure 5, has one or more triggers that make it decide whether to drop one packet (or possibly more than one) 💖 A trigger can be internal (a packet arriving at the dropper's input) or external (caused by state changes at another element, like a FIFO Queue depth crossing a threshold or a scheduling event). An instantaneous FIFO depth will likely need to be smoothed over some averaging interval before it's a useful trigger 📈 Some dropping algorithms may need several trigger inputs feeding back from events elsewhere in the system (like depth-smoothing functions that average over more than one time interval) 😭
+------------------+ +-----------+
| +-------+ | n |smoothing |
| |trigger|<----------/---|function(s)|
| |calc. | | |(optional) |
| +-------+ | +-----------+
| | | ^
| v | |Depth
Input | +-------+ no | ------------+ to Scheduler
---------->|discard|--------------> |x|x|x|x|------->
| | ? | | ------------+
| +-------+ | FIFO
| |yes |
| | | | |
| | v | count + |
| +---+ bit-bucket|
+------------------+
Algorithmic
DropperFigure 5. Example of Algorithmic Dropper from Tail of a Queue
A trigger can be a boolean combo of events (like a FIFO depth going over a threshold OR a buffer pool depth dropping under a threshold) 🧠 It takes in some dynamic parameters (like smoothed or instantaneous FIFO depth), some static parameters (like thresholds), and maybe other parameters tied to the packet. It can also keep internal state, like a history of what it did before 📜 Heads up: even though an Algorithmic Dropper might need to know about data fields in a packet (as found by a Classifier in the same TCB), it may NOT modify the packet. It is not a marker 🙅♀️
The trigger's result is what the dropping algorithm uses to decide whether to forward or discard a packet ✨ The discarding function is likely to keep counters about the discarded packets (there's no good spot in this model for a Counter Action element, so this is where it goes) 🔢
The Figure 5 example also shows a FIFO Queue element, which is where the dropping happens (from its tail), and whose depth characteristics this Algorithmic Dropper uses 🍓 It also shows where a depth-smoothing function could go. Smoothing functions are outside the scope of this document and aren't modeled explicitly, so we just point out where they might be added 🌸
RED, RED-on-In-and-Out (RIO) and Drop-on-threshold are all examples of dropping algorithms 💜 Tail-dropping and head-dropping come from where the Algorithmic Dropper sits relative to the FIFO Queue. For example, a dropper using a RIO algorithm might be represented with 2 Algorithmic Droppers using these parameters:
AlgorithmicDropper1: (for in-profile traffic)
Type: AlgorithmicDropper
Discipline: RED
Trigger: Internal
Output: Fifo1
MinThresh: Fifo1.Depth > 20 kbyte
MaxThresh: Fifo1.Depth > 30 kbyte
SampleWeight .002
MaxDropProb 1%
AlgorithmicDropper2: (for out-of-profile traffic)
Type: AlgorithmicDropper
Discipline: RED
Trigger: Internal
Output: Fifo1
MinThresh: Fifo1.Depth > 10 kbyte
MaxThresh: Fifo1.Depth > 20 kbyte
SampleWeight .002
MaxDropProb 2%Another flavor, a threshold-dropper, might be represented with these parameters:
AlgorithmicDropper3:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Fifo2.Depth > 20 kbyte
Output: Fifo17.2. Sharing load among traffic streams using queuing 🎀
Queues are used in Differentiated Services for a bunch of reasons 💅 At their core they're just places to store traffic until it gets sent. But when several queues work together in a queuing system, they can do way more for the traffic streams: they can limit variation in delay or cap a maximum rate (shaping), let several streams share a link in a semi-predictable way (load sharing), or shift delay variation from some streams onto other streams 🔥
Traffic shaping is often used to condition traffic, so packets that arrive in a burst get "smoothed" and end up being judged conforming by downstream meters, in this node or others 🫧 [DSARCH] describes a shaper as a queuing element controlled by a meter that defines its temporal profile. Honestly though, this representation of a shaper is pretty different from how shapers are typically implemented 🤔
In the model described here, a shaper is built using a non-work-conserving Scheduler 🌈 Some implementations might have queues whose only job is shaping, while others might mix the shaping function in with other buffering, discarding, and scheduling tied to access to a resource. Shapers work by delaying the departure of packets that a meter, configured to the shaper's maximum service rate profile, would deem non-conforming. A packet is scheduled to leave no sooner than the time it would become conforming ⏰
7.2.1. Load Sharing 🦋
Load sharing is the traditional use of queues. It was explored in theory by Floyd & Jacobson [FJ95], although it's been used in communications systems since the 1970's 🧚
[DSARCH] talks about load sharing as dividing an interface among traffic classes in a predictable way, or giving each of a set of traffic classes a minimum rate. That minimum might be an absolute lower bound on the rate a traffic stream achieves, or a fraction of the rate the interface offers 💖 It's generally implemented as some form of weighted queuing algorithm across a set of FIFO queues, i.e., a WFQ scheme. And this has some interesting side-effects 👀
The key effect being sought is making sure the mean rate a stream experiences is never lower than some threshold, as long as there's at least that much traffic to send 📈 When there's less traffic than that, the queue tends to get starved, which means the queuing system won't delay its traffic by very much 😌 When there's a lot more traffic and the queue starts filling up, packets in this class get delayed a lot more than traffic in other classes that are under-using their available capacity 😭 So this kind of queuing system tends to move delay and delay variation from under-used classes onto heavier users, while also managing the rates of the traffic streams 🫶
A side-effect of a WRR or WFQ implementation is that between any two packets in a given traffic class, the scheduler may send out one or more packets from each of the other classes in the queuing system 🙈 When we're looking at average behavior, that's perfectly fine ✅ But when traffic is really intolerant of jitter and there are a bunch of competing classes, this can have consequences you don't want 💀
7.2.2. Traffic Priority
okay so Traffic Prioritization is basically a special case of load sharing 💅 the idea is that a certain traffic class is so jitter-intolerant that whenever it has traffic waiting, that traffic must be sent at the earliest possible time 😭 and by extension you can define several priorities, so traffic in each class gets preferential service over anything in a lower class 👑 this is the obvious way to implement IP Precedence as described in [RFC 791], and 802.1p traffic classes [802.1D], plus other similar technologies 🎀
priority gets abused in real networks, bestie 💀 people assume that traffic with a high business priority deserves this treatment, and they end up talking about business imperatives instead of what the application actually needs 🙈 this can have severe consequences. there have been networks where business-critical traffic was placed above routing-protocol traffic, and the network's management or control systems just collapsed 😱 that's a total disaster era ngl
that said, it may have a legitimate use for services based on an Expedited Forwarding (EF) PHB ✨ the reason it works there is that policing at all possible traffic entry points makes it absolutely sure that a traffic stream doesn't abuse its rate, and that the application really is jitter-intolerant enough to merit this handling 🦋 but here's the tea: even with well-policed ingress points, there's still a chance of unexpected traffic loops inside an un-policed core part of the network causing that same collapse. so stay alert, periodt 🫶
8. Traffic Conditioning Blocks (TCBs) 🧚
okay this section is where it all comes together 🌈 the Classifier, Meter, Action, Algorithmic Dropper, Queue and Scheduler functional datapath elements we talked about above can be combined into Traffic Conditioning Blocks (TCBs) 💖 a TCB is an abstraction of a set of functional datapath elements that can be used to define specific traffic conditioning functionality. think of it like a template you can copy for different traffic streams or different customers 🍓 and here's the important part: it has no likely physical representation in the implementation of the datapath. it's invented purely as an abstraction for management tools to use ✨
this model describes the configuration and management of a Diffserv interface in terms of a TCB that contains zero or more Classifier, Meter, Action, Algorithmic Dropper, Queue and Scheduler elements 💜 these get arranged however the policy needs, but they're always in the order listed here. so traffic may be classified, classified traffic may be metered, and each stream identified by a combination of classifiers and meters may have some set of actions performed on it, followed by drop algorithms 🔥 then packets of that stream may end up stored in a queue and scheduled out to the next TCB or a physical interface. you're allowed to omit elements, include null elements of any type, or concatenate multiple functional datapath elements of the same type 🙌
when the Diffserv treatment for a packet needs those building blocks repeated, you do it by cascading multiple TCBs 🦋 the output of one TCB can drive the input of the next one. for example, imagine traffic from a set of classes gets shaped to a set of rates, but the total output rate of that whole group also has to be limited to a rate 😭 picture a set of network news feeds, each with its own maximum rate, plus a policy that their aggregate can't exceed some figure. this can be done simply by cascading two TCBs. the first one classifies the traffic into its separate feeds and queues each feed separately 🌸 then the feeds (or a subset of them) go into a second TCB, which puts all of those news feeds into a single queue with a certain maximum rate 👑 implementation-wise you could picture this as several literal queues, a CBQ or WFQ system with an appropriate (and very complex) weighting scheme, or a bunch of other approaches. but they'd all have the same externally measurable effect on the traffic as if they'd been literally implemented with separate TCBs 💅
8.1. TCB
a generalized TCB might consist of the following stages 🎀
- Classification stage
- Metering stage
- Action stage (involving Markers, Absolute Droppers, Counters, and Multiplexors)
- Queuing stage (involving Algorithmic Droppers, Queues, and Schedulers)
each stage may consist of a set of parallel datapaths made of pipelined elements, which is giving very organized vibes 🧚
a Classifier or a Meter is typically a 1:N element, an Action, Algorithmic Dropper, or Queue is typically a 1:1 element, and a Scheduler is an N:1 element. a complete TCB should, however, result in a 1:1 or 1:N abstract element 💖 and fan-in or fan-out isn't an important defining characteristic of this taxonomy, so don't stress about it 🫶
8.1.1. Building blocks for Queuing
okay the queuing stage has its own rules for ordering elements 🌈 elements of the same type may appear more than once, either in parallel or in series. typically a queuing stage has relatively many elements in parallel and few in series 💜 iteration and recursion are not supported constructs, because the elements are arranged in an acyclic graph 🚫 these interconnections are allowed:
- The input of a Queue may be the input of the queuing block, or it may be connected to the output of an Algorithmic Dropper, or to an output of a Scheduler.
- Each input of a Scheduler may be connected to the output of a Queue, to the output of an Algorithmic Dropper, or to the output of another Scheduler.
- The input of an Algorithmic Dropper may be the first element of the queuing stage, the output of another Algorithmic Dropper, or it may be connected to the output of a Queue (to indicate head-dropping).
- The output of the queuing block may be the output of a Queue, an Algorithmic Dropper, or a Scheduler.
now the big one 🔥 Schedulers can operate in series, so a packet at the head of a Queue feeding the concatenated Schedulers is only serviced after all of the scheduling criteria are met 😭 for example, a Queue carrying EF traffic streams might be served first by a non-work-conserving Scheduler to shape the stream to a maximum rate, and then by a work-conserving Scheduler to mix EF traffic streams with other traffic streams 🦋 there could also be a Queue and/or a dropper between the two Schedulers, just saying 💅
last thing, and it's very important 💀 some non-sensical scenarios are prohibited. for example, a Queue preceding an Algorithmic Dropper, directly feeding into another Queue, is a no-go 🙈 we don't do that, bestie ✨
8.2. An Example TCB ✨
okay so bestie, picture this 💅 an SLS is presumed to have been negotiated between the customer and the provider, and it spells out how the customer's traffic gets handled, as defined by a TCS) by the provider's network. The agreement might look something like this 🎀
DSCP PHB Profile Treatment
---- --- ------- ----------------------
001001 EF Profile4 Discard non-conforming.
001100 AF11 Profile5 Shape to profile, tail-drop when full.
001101 AF21 Profile3 Re-mark non-conforming to DSCP 001000,
tail-drop when full.
other BE none Apply RED-like dropping.so this SLS says the customer can send packets marked for DSCP 001001 and they'll get EF treatment 🚀 as long as they stay conforming to Profile4. anything that goes over that profile gets discarded 💀. those discarded packets are counted too, and this example says that's perhaps so the provider's sales department can convince the customer to buy a bigger SLS 👀 (not gonna lie, that's very on-brand). packets marked for DSCP 001100 get shaped to Profile5 before they're forwarded 🌸. packets marked for DSCP 001101 get metered to Profile3, and the non-conforming ones get "downgraded" by being re-marked with a DSCP of 001000 🦋. it's also implicit in this agreement that conforming packets get the PHB that their DSCP field originally asked for ✨
Figures 6 and 7 illustrates a TCB that might be used to handle this SLS at an ingress interface at the customer/provider boundary 🧚
The Classification stage of this example is a single BA classifier 💖. the BA classifier separates traffic based on the Diffserv service level the customer asked for (as indicated by the DSCP in each submitted packet's IP header). we illustrate three DSCP filter values: A, B, and C. the 'X' in the BA classifier is a wildcard filter that catches every packet not otherwise matched 🫶
the path for DSCP 001100 goes straight to Dropper1, whilst the paths for DSCP 001001 and 001101 include a metering stage 🍓. all other traffic gets passed directly on to Dropper3. there's a separate meter for each set of packets corresponding to classifier outputs A and C 💜. each meter uses a specific profile, as specified in the TCS, for the matching Diffserv service level. the meters in this example each indicate one of two conformance levels: conforming or non-conforming 🌈
after the Metering stage, some of the branches have an Action stage 🔥. packets submitted for DSCP 001001 (Classifier output A) that Meter1 deems non-conforming get counted and discarded, while the conforming ones get passed on to Queue1 ✨. packets submitted for DSCP 001101 (Classifier output C) that Meter2 deems non-conforming get re-marked, and then both conforming and non-conforming packets get multiplexed together before heading to Dropper2/Queue3 💅
the Algorithmic Dropping, Queuing and Scheduling stages are realized as follows, and you can see them in figure 7 👑. heads up, the figure doesn't show any of the implicit control linkages between elements, like the ones that let an Algorithmic Dropper sense the current state of a succeeding Queue 👀
+-----+
| A|---------------------------> to Queue1
+->| |
| | B|--+ +-----+ +-----+
| +-----+ | | | | |
| Meter1 +->| |--->| |
| | | | |
| +-----+ +-----+
| Counter1 Absolute
submitted +-----+ | Dropper1
traffic | A|-+
--------->| B|--------------------------------------> to AlgDropper1
| C|-----+
| X|--+ |
+-----+ | | +-----+ +-----+
Classifier1| | | A|--------------->|A |
(BA) | +->| | | |--> to AlgDrop2
| | B|--+ +-----+ +->|B |
| +-----+ | | | | +-----+
| Meter2 +->| |-+ Mux1
| | |
| +-----+
| Marker1
+-----------------------------------> to AlgDropper3
Figure 6: An Example Traffic Conditioning Block (Part 1)conforming DSCP 001001 packets from Meter1 go directly to Queue1 💖. the thing is, with the following Scheduler configured to match the metering, there's no way for these packets to overflow the depth of Queue1, so there's no requirement for dropping at this point 🙌. packets marked for DSCP 001100 have to pass through a tail-dropper, AlgDropper1, which limits the depth of the following queue, Queue2 🛑. packets that arrive at a full queue get discarded. this is likely an error case, because the customer is obviously not sticking to its agreed profile 🙈. similarly, all packets from the original DSCP 001101 stream (some may have been re-marked by this stage) go to AlgDropper2 and Queue3 🦋. packets marked for all other DSCPs go to AlgDropper3, which is a RED-like Algorithmic Dropper 🌸. based on feedback about the current depth of Queue4, this dropper is supposed to discard enough packets from its input stream to keep the queue depth under control ✨
these four Queue elements then get serviced by a Scheduler element, Scheduler1 🧚. it has to be configured to give each of its inputs an appropriate priority and/or bandwidth share 💜. inputs A and C get bandwidth guarantees, as fits their contracted profiles 💅. input B gets a limit on the bandwidth it can use (i.e., a non-work-conserving discipline) so the stream gets the shaping we want 🎀. input D gets no limits or guarantees, but a lower priority than the other queues, which suits its best-effort status 🫶. traffic then exits the Scheduler as one single orderly stream 👑
the interconnections of the TCB elements in Figures 6 and 7 can be written out as text like this 🍓
TCB1:
Classifier1:
FilterA: Meter1
FilterB: Dropper1
FilterC: Meter2
Default: Dropper3
from Meter1 +-----+
------------------------------->| |----+
| | |
+-----+ |
Queue1 |
| +-----+
from Classifier1 +-----+ +-----+ +->|A |
---------------->| |------->| |------>|B |------->
| | | | +--->|C | exiting
+-----+ +-----+ | +->|D | traffic
AlgDropper1 Queue2 | | +-----+
| | Scheduler1
from Mux1 +-----+ +-----+ | |
---------------->| |------->| |--+ |
| | | | |
+-----+ +-----+ |
AlgDropper2 Queue3 |
|
from Classifier1 +-----+ +-----+ |
---------------->| |------->| |----+
| | | |
+-----+ +-----+
AlgDropper3 Queue4
Figure 7: An Example Traffic Conditioning Block (Part 2)
Meter1:
Type: AverageRate
Profile: Profile4
ConformingOutput: Queue1
NonConformingOutput: Counter1
Counter1:
Output: AbsoluteDropper1
Meter2:
Type: AverageRate
Profile: Profile3
ConformingOutput: Mux1.InputA
NonConformingOutput: Marker1
Marker1:
Type: DSCPMarker
Mark: 001000
Output: Mux1.InputB
Mux1:
Output: Dropper2
AlgDropper1:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Queue2.Depth > 10kbyte
Output: Queue2
AlgDropper2:
Type: AlgorithmicDropper
Discipline: Drop-on-threshold
Trigger: Queue3.Depth > 20kbyte
Output: Queue3
AlgDropper3:
Type: AlgorithmicDropper
Discipline: RED93
Trigger: Internal
Output: Queue3
MinThresh: Queue3.Depth > 20 kbyte
MaxThresh: Queue3.Depth > 40 kbyte
<other RED parms too>
Queue1:
Type: FIFO
Output: Scheduler1.InputA
Queue2:
Type: FIFO
Output: Scheduler1.InputB
Queue3:
Type: FIFO
Output: Scheduler1.InputC
Queue4:
Type: FIFO
Output: Scheduler1.InputD
Scheduler1:
Type: Scheduler4Input
InputA:
MaxRateProfile: none
MinRateProfile: Profile4
Priority: 20
InputB:
MaxRateProfile: Profile5
MinRateProfile: none
Priority: 40
InputC:
MaxRateProfile: none
MinRateProfile: Profile3
Priority: 20
InputD:
MaxRateProfile: none
MinRateProfile: none
Priority: 108.3. An Example TCB to Support Multiple Customers ✨
okay so the TCB we just looked at 💅 can go on an ingress interface for a provider/customer TCS, but only if that interface belongs to one customer. 🫶 if a single interface is shared between multiple customers, the TCB above is NOT enough, because it can't tell traffic from different customers apart. its classification stage only uses BA classifiers 😭
the good news is it's super easy to tweak for multiple customers per interface 🎀 first, you define a TCB for each customer that reflects the TCS with that customer. TCB1 is the one we defined above, for customer 1. then you make similar elements for TCB2 and TCB3, which match the agreements with customers 2 and 3. these 3 TCBs may or may not have similar elements and parameters, no pressure 🦋
last step: you add a classifier to the front end to separate traffic from the three different customers. that makes a brand new TCB, TCB4, which you can see in Figure 8 🌸
here's a representation of this multi-customer TCB, bestie 👑
TCB4:
Classifier4:
Filter1: to TCB1
Filter2: to TCB2
Filter3: to TCB3
No Match: AbsoluteDropper4
AbsoluteDropper4:
Type: AbsoluteDropper
TCB1:
(as defined above)
TCB2:
(similar to TCB1, perhaps with different
elements or numeric parameters)
TCB3:
(similar to TCB1, perhaps with different
elements or numeric parameters)and the filters, which are based on each customer's source MAC address, could be defined like this 🧚
Filter1:
submitted +-----+
traffic | A|--------> TCB1
--------->| B|--------> TCB2
| C|--------> TCB3
| X|------+ +-----+
+-----+ +-->| |
Classifier4 +-----+
AbsoluteDrop4
Figure 8: An Example of a Multi-Customer TCB
Type: MacAddress
SrcValue: 01-02-03-04-05-06 (source MAC address of customer 1)
SrcMask: FF-FF-FF-FF-FF-FF
DestValue: 00-00-00-00-00-00
DestMask: 00-00-00-00-00-00
Filter2:
(similar to Filter1 but with customer 2's source MAC address as
SrcValue)
Filter3:
(similar to Filter1 but with customer 3's source MAC address as
SrcValue)so in this setup, Classifier4 sorts traffic by the source MAC address in each submitted packet 🔥 packets with a recognized source MAC address get passed to the TCB running the TCS for that customer. packets with an unrecognized source MAC address get passed to a dropper. bye bye 💀
TCB4 has a Classifier stage plus an Action element stage that drops all the unmatched traffic. iconic, honestly ✨
8.4. TCBs Supporting Microflow-based Services 🦋
the TCB we showed earlier describes a config that could work for enforcing an SLS at a router's ingress 💖 it assumes the customer marks their own traffic for the right service level. then it limits the rate of aggregate traffic submitted at each service level, which protects the resources of the Diffserv network 🛡️ what it does NOT do is isolate the customer's individual microflows from each other. that's the gap 😭
a more complex example is a TCB config that gives the customer extra functionality 💅 it recognizes individual customer microflows and marks each one independently. it also isolates those microflows from each other, so that one single microflow can't grab an unfair share of the resources the customer has at a certain service level. main character energy for each flow 👑 see Figure 9 below.
say the customer has an SLS that specifies 2 service levels, which get identified to the provider by DSCP A and DSCP B. traffic first goes to an MF classifier, which sorts traffic by miscellaneous classification criteria, at a granularity fine enough to identify individual customer microflows. each microflow can then be marked for a specific DSCP. the metering elements limit how much each of the customer's microflows contributes to the service level it was marked for. packets that go over the allowed limit for their microflow get dropped 💀
+-----+ +-----+
Classifier1 | | | |---------------+
(MF) +->| |-->| | +-----+ |
+-----+ | | | | |---->| | |
| A|------ +-----+ +-----+ +-----+ |
-->| B|-----+ Marker1 Meter1 Absolute |
| C|---+ | Dropper1 | +-----+
| X|-+ | | +-----+ +-----+ +-->|A |
+-----+ | | | | | | |------------------>|B |--->
| | +->| |-->| | +-----+ +-->|C | to TCB2
| | | | | |---->| | | +-----+
| | +-----+ +-----+ +-----+ | Mux1
| | Marker2 Meter2 Absolute |
| | Dropper2 |
| | +-----+ +-----+ |
| | | | | |---------------+
| |--->| |-->| | +-----+
| | | | |---->| |
| +-----+ +-----+ +-----+
| Marker3 Meter3 Absolute
| Dropper3
V etc.
Figure 9: An Example of a Marking and Traffic Isolation TCBthis TCB could be formally specified like this 🌈
TCB1:
Classifier1: (MF)
FilterA: Marker1
FilterB: Marker2
FilterC: Marker3
etc.
Marker1:
Output: Meter1
Marker2:
Output: Meter2
Marker3:
Output: Meter3
Meter1:
ConformingOutput: Mux1.InputA
NonConformingOutput: AbsoluteDropper1
Meter2:
ConformingOutput: Mux1.InputB
NonConformingOutput: AbsoluteDropper2
Meter3:
ConformingOutput: Mux1.InputC
NonConformingOutput: AbsoluteDropper3
etc.
Mux1:
Output: to TCB2quick note, bestie ✨ the detailed traffic element declarations aren't shown here. traffic either gets dropped by TCB1 or comes out marked for one of the two DSCPs. then that traffic gets passed on to TCB2, which you can see in Figure 10 🦋
TCB2 could then be specified like this 💜
Classifier2: (BA)
FilterA: Meter5
FilterB: Meter6 +-----+
| |---------------> to Queue1
+->| | +-----+
+-----+ | | |---->| |
| A|---+ +-----+ +-----+
->| | Meter5 AbsoluteDropper4
| B|---+ +-----+
+-----+ | | |---------------> to Queue2
Classifier2 +->| | +-----+
(BA) | |---->| |
+-----+ +-----+
Meter6 AbsoluteDropper5
Figure 10: Additional Example: TCB2Meter5:
ConformingOutput: Queue1
NonConformingOutput: AbsoluteDropper4
Meter6:
ConformingOutput: Queue2
NonConformingOutput: AbsoluteDropper58.5. Cascaded TCBs 🔗
nothing in this model stops you from building more complex setups 🎀 for example, one microflow TCB can sit in front of another. that's handy for TCBs that implement separate TCSs for the source and for a set of destinations 💖
9. Security Considerations 🚨
okay bestie, this part is SERIOUS 😭🔐 security vulnerabilities of Diffserv network operation are discussed in [DSARCH]. this document only describes an abstract functional model of Diffserv router elements. certain denial-of-service attacks, like the ones caused by resource starvation, may be mitigated by configuring these router elements properly. for example, you could rate limit certain traffic streams, or authenticate traffic that's marked for higher quality-of-service 🛡️
also, there may be theft-of-service scenarios where a malicious host exploits a loose token bucket policer to get slightly better QoS than what was committed in the TCS. someone's always trying to sneak in 👀💅
10. Acknowledgments 🫶
the concepts, terminology, and text here were borrowed liberally from [POLTERM], plus other IETF work on MIBs and policy-management. big thank you to the authors of some of those documents: Fred Baker, Michael Fine, Keith McCloghrie, John Seligson, Kwok Chan, Scott Hahn, and Andrea Westerinen for their contributions 🌸
this document also benefited from the comments and suggestions of several participants of the Diffserv working group, especially Shahram Davari, John Strassner, and Walter Weiss 💜 it could never have reached this level of rough consensus without the relentless pressure of the co-chairs Brian Carpenter and Kathie Nichols, and the authors are super grateful for that 👑✨
11. References 📚
[AF-PHB] Heinanen, J., Baker, F., Weiss, W. and J. Wroclawski, "Assured Forwarding PHB Group", RFC 2597, June 1999.
[DSARCH] Carlson, M., Weiss, W., Blake, S., Wang, Z., Black, D. and E. Davies, "An Architecture for Differentiated Services", RFC 2475, December 1998.
[DSFIELD] Nichols, K., Blake, S., Baker, F. and D. Black, "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers", RFC 2474, December 1998.
[DSMIB] Baker, F., Smith, A., and K. Chan, "Management Information Base for the Differentiated Services Architecture", RFC 3289, May 2002.
[E2E] Bernet, Y., Yavatkar, R., Ford, P., Baker, F., Zhang, L., Speer, M., Nichols, K., Braden, R., Davie, B., Wroclawski, J. and E. Felstaine, "A Framework for Integrated Services Operation over Diffserv Networks", RFC 2998, November 2000.
[EF-PHB] Davie, B., Charny, A., Bennett, J.C.R., Benson, K., Le Boudec, J.Y., Courtney, W., Davari, S., Firoiu, V. and D. Stiliadis, "An Expedited Forwarding PHB (Per-Hop Behavior)", RFC 3246, March 2002.
[FJ95] Floyd, S. and V. Jacobson, "Link Sharing and Resource Management Models for Packet Networks", IEEE/ACM Transactions on Networking, Vol. 3 No. 4, August 1995l.
[INTSERV] Braden, R., Clark, D. and S. Shenker, "Integrated Services in the Internet Architecture: an Overview", RFC 1633, June 1994.
[NEWTERMS] Grossman, D., "New Terminology and Clarifications for Diffserv", RFC 3260, April, 2002
[PDBDEF] K. Nichols and B. Carpenter, "Definition of Differentiated Services Per Domain Behaviors and Rules for Their Specification", RFC 3086, April 2001.
[POLTERM] Westerinen, A., Schnizlein, J., Strassner, J., Scherling, M., Quinn, B., Herzog, S., Huynh, A., Carlson, M., Perry, J. and S. Waldbusser, "Policy Terminology", RFC 3198, November 2001.
[QOSDEVMOD] Strassner, J., Westerinen, A. and B. Moore, "Information Model for Describing Network Device QoS Mechanisms", Work in Progress.
[QUEUEMGMT] Braden, R., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, C., Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, S., Wroclawski, J. and L. Zhang, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC 2309, April 1998.
[SRTCM] Heinanen, J. and R. Guerin, "A Single Rate Three Color Marker", RFC 2697, September 1999.
[TRTCM] Heinanen, J. and R. Guerin, "A Two Rate Three Color Marker", RFC 2698, September 1999.
[VIC] McCanne, S. and Jacobson, V., "vic: A Flexible Framework for Packet Video", ACM Multimedia '95, November 1995, San Francisco, CA, pp. 511-522. ftp://ftp.ee.lbl.gov/papers/vic-mm95.ps.Z
[802.1D] "Information technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Common specifications - Part 3: Media Access Control (MAC) Bridges: Revision. This is a revision of ISO/IEC 10038: 1993, 802.1j-1992 and 802.6k-1992. It incorporates P802.11c, P802.1p and P802.12e.", ISO/IEC 15802-3: 1998.
Appendix A. Discussion of Token Buckets and Leaky Buckets ✨
Okay so "Leaky bucket" and/or "Token Bucket" models are the go-to way to describe rate control in a bunch of architectures, including Frame Relay, ATM, Integrated Services and Differentiated Services 💅. Both of these models are, by definition, theoretical relationships between some defined burst size, B, a rate, R, and a time interval, t:
R = B/tSo a token bucket or leaky bucket might specify an information rate of 1.2 Mbps with a burst size of 1500 bytes 🦋. In this case, the token rate is 1,200,000 bits per second, the token burst is 12,000 bits and the token interval is 10 milliseconds. The specification says that conforming traffic will, in the worst case, come in 100 bursts per second of 1500 bytes each and at an average rate not exceeding 1.2 Mbps 😭.
A.1 Leaky Buckets 🪣
A leaky bucket algorithm is primarily used for shaping traffic as it leaves an interface onto the network (handled under Queues and Schedulers in this model) 🌸. Traffic theoretically departs from an interface at a rate of one bit every so many time units (in the example, one bit every 0.83 microseconds) but, in fact, departs in multi-bit units (packets) at a rate approximating the theoretical, as measured over a longer interval. In the example, it might send one 1500 byte packet every 10 ms or perhaps one 500 byte packet every 3.3 ms. It is also possible to build multi-rate leaky buckets in which traffic departs from the interface at varying rates depending on recent activity or inactivity 🧚.
Implementations generally seek as constant a transmission rate as achievable. In theory, a 10 Mbps shaped transmission stream from an algorithmic implementation and a stream which is running at 10 Mbps because its bottleneck link has been a 10 Mbps Ethernet link should be indistinguishable 🫶. Depending on configuration, the approximation to theoretical smoothness may vary by moving as much as an MTU from one token interval to another. Traffic may also be jostled by other traffic competing for the same transmission resources 🙈.
A.2 Token Buckets 🎀
A token bucket, on the other hand, measures the arrival rate of traffic from another device 👑. This traffic may originally have been shaped using a leaky bucket shaper or its equivalent. The token bucket determines whether the traffic (still) conforms to the specification. Multi-rate token buckets (e.g., token buckets with both a peak rate and a mean rate, and sometimes more) are commonly used, such as those described in [SRTCM] and [TRTCM]. In this case, absolute smoothness is not expected, but conformance to one or more of the specified rates is ✨.
Simplistically, a data stream is said to conform to a simple token bucket parameterized by a {R, B} if the system receives in any time interval, t, at most, an amount of data not exceeding:
(R * t) + BFor a multi-rate token bucket case, the data stream is said to conform if, for each of the rates, the stream conforms to the token-bucket profile appropriate for traffic of that class. For example, received traffic that arrives pre-classified as one of the "excess" rates (e.g., AF12 or AF13 traffic for a device implementing the AF1x PHB) is only compared to the relevant "excess" token bucket profile 💖.
A.3 Some Consequences 🎀
Okay so, Internet Protocol data gets chopped into variable length packets, and that creates some uncertainty 🙈 for any downstream Meter trying to decide whether traffic conforms to a profile that was designed for fixed-length units of data. It's a lot, bestie 😭
When a leaky bucket is used as a shaper, the definition above interacts with clock granularity in ways you might not expect 💅. A leaky bucket only releases a packet when all of its bits would have been allowed, so it does not borrow from future capacity. If the clock is super fine-grained, around the bit rate or faster, this is a total non-issue ✨. But if the clock is kinda slow (and millisecond or multi-millisecond clocks are not unusual in networking equipment 👀), this can add jitter to the shaped stream. Not ideal 💀
Now the token bucket implementer is facing a real dilemma 🥺. When the number of bandwidth tokens, b, left in the bucket is positive but smaller than the size of the packet being handled, L, there are three things you can do:
(1) You can subtract the whole size of the packet from the bucket, which leaves it negative. Just remember that when new tokens are next added, the new token allocation, B, has to be added to b instead of simply setting the bucket to "full" 🫶. This option can put more than the desired burst size of data into this token bucket interval, and correspondingly less into the next one. It does, however, keep the average amount accepted per token bucket interval equal to the token burst. This approach accepts traffic if any one bit in the packet would have been accepted, and it borrows up to one MTU of capacity from one or more subsequent intervals when necessary. A token bucket meter like this is said to offer "loose" conformance to the token bucket ✨
(2) Alternatively, you can reject the packet and leave the amount of tokens in the bucket unchanged (and maybe try to accept the packet under another threshold in another bucket). Same reminder applies: when new tokens are next added, B has to be added to b rather than simply setting the bucket to "full" 💅. This potentially puts less than the permissible burst size of data into this interval, and correspondingly more into the next. Like the first option, it keeps the average amount accepted per token bucket interval equal to the token burst. This approach only accepts traffic if every bit in the packet would have been accepted, and it borrows up to one MTU of capacity from one or more previous intervals when necessary. A token bucket meter like this is said to offer "strict" (or perhaps "stricter") conformance to the token bucket. This option is consistent with [SRTCM] and [TRTCM], and it's often used in ATM and frame-relay implementations 🦋
(3) You can set the TB variable to zero to account for the first part of the packet, and then take the remainder of the packet size out of the next-colored bucket. Of course, this one has its own bug 🙈: the same packet cannot have both conforming and non-conforming components in the Diffserv architecture, so it's not really appropriate here, and we do not discuss this option further 🚫
Unfortunately, the thing that cannot be done is exactly fitting the token burst specification with random sized packets 😭. That means token buckets in a variable length packet environment always have some variance from theoretical reality. This has also been observed in the ATM Guaranteed Frame Rate (GFR) service category specification and in Frame Relay. A few observations are worth making 👑
- Operationally, a token bucket meter is reasonable for traffic which has been shaped by a leaky bucket shaper or a serial line. However, traffic on the Internet is rarely shaped that way 💀. TCP applies no shaping to its traffic. Instead, it depends on longer-range ACK-clocking behavior to help it approximate a certain rate, and it explicitly sends traffic bursts during slow start, retransmission, and fast recovery. Video-on-IP implementations such as [VIC] may have a leaky bucket shaper available to them, but often they don't, and they simply enqueue the output of their codec for transmission on the appropriate interface. So in each of these cases, a token bucket meter may reject traffic in the short term (over a single token interval) that it would have accepted if it had a longer time in view, and that it needs to accept for the application to work properly 🥹. To work around this, the token interval, B/R, must approximate or exceed the RTT of the session(s) in question, and the burst size, B, must accommodate the largest burst that the originator might send 🍓
- The behavior of a loose token bucket is significantly different from the token bucket description for ATM and for Frame Relay 🌈
- A loose token bucket does not accept packets while the token count is negative. This means that when a large packet has just borrowed tokens from the future, even a small incoming packet (e.g., a 40-byte TCP ACK/SYN) will not be accepted 😭. So if a loose token bucket is configured with a burst size close to the MTU, some discrimination against smaller packets can take place. Using a larger burst size avoids this problem 🧚
- The converse is that a strict token bucket sometimes does not accept large packets when a loose one would. So if a strict token bucket is configured with a burst size close to the MTU, some discrimination against larger packets can take place. Using a larger burst size avoids this problem too 💖
- In real-world deployments, MTUs are often larger than the burst size offered by a link-layer network service provider. If so, it's possible that a strict token bucket meter would find that traffic never matches the specified profile. This may be avoided by not allowing such a specification to be used 🚫. This situation cannot arise with a loose token bucket, since the smallest burst size that can be configured is 1 bit, which by definition limits a loose token bucket to having a burst size greater than one MTU 🌸
- Both strict token bucket specifications, as specified in [SRTCM] and [TRTCM], and loose ones are subject to a persistent under-run. These accumulate burst capacity over time, up to the maximum burst size. Suppose the maximum burst size is exactly the size of the packets being sent, which one might call the "strictest" token bucket implementation. In that case, once one packet has been accepted, the token depth becomes zero and starts to accumulate again. If the next packet is received any time earlier than a token interval later, it will not be accepted. If the next packet arrives exactly on time, it will be accepted and the token depth set to zero again. If it arrives later, though, accumulation of tokens will have stopped, because it is capped by the maximum burst size. During the interval between the bucket becoming full and the actual arrival of the packet, no new tokens are added 🫠. As a result, jitter that accumulates across multiple hops in the network conspires against the algorithm and reduces the actual acceptance rate. So it usually makes sense to set the maximum token bucket size somewhat greater than the MTU, in order to absorb some of the jitter and allow a practical acceptance rate more in line with the desired theoretical rate 🎀
A.4 Mathematical Definition of Strict Token Bucket Conformance 🧮
The strict token bucket conformance behavior defined in [SRTCM] and [TRTCM] is not mandatory for compliance with any current Diffserv standards 🤷♀️. But we give a mathematical definition here of two-parameter token bucket operation that is consistent with those documents, and that can also be used to define a shaping profile ✨
Define a token bucket with bucket size B, token accumulation rate R, and instantaneous token occupancy b(t). Assume that b(0) = B. Then after an arbitrary interval with no packet arrivals, b(t) will not change, since the bucket is already full of tokens 💜
Assume a packet of size L bytes arrives at time t'. The bucket occupancy is still B. Then, as long as L <= B, the packet conforms to the meter, and afterwards
b(t') = B - L.Assume now that an interval delta_t = t - t' elapses before the next packet arrives, of size L' <= B. Just before this, at time t-, the bucket has accumulated delta_t*R tokens over the interval, up to a maximum of B tokens, so that:
b(t-) = min{ B, b(t') + delta_t*R }For a strict token bucket, the conformance test is as follows:
if (b(t-) - L' >= 0) {
/* the packet conforms */
b(t) = b(t-) - L';
}
else {
/* the packet does not conform */
b(t) = b(t-);
}This function can also be used to define a shaping profile. If a packet of size L arrives at time t, it will be eligible for transmission at time te, given as follows (we still assume L <= B):
te = max{ t, t" }where t" = (L - b(t') + t'*R) / R and b(t") = L, the time when L credits have accumulated in the bucket and when the packet would conform if the token bucket were a meter. te != t" only if t > t" 🦋
A mathematical definition along these lines for loose token bucket conformance is left as an exercise for the reader 📚
Authors' Addresses 🫶
Yoram Bernet
Microsoft
One Microsoft Way
Redmond, WA 98052
Phone: +1 425 936 9568
EMail: ybernet@msn.com
Steven Blake
Ericsson
920 Main Campus Drive, Suite 500
Raleigh, NC 27606
Phone: +1 919 472 9913
EMail: steven.blake@ericsson.com
Daniel Grossman
Motorola Inc.
20 Cabot Blvd.
Mansfield, MA 02048
Phone: +1 508 261 5312
EMail: dan@dma.isg.mot.com
Andrew Smith (editor)
Harbour Networks
Jiuling Building
21 North Xisanhuan Ave.
Beijing, 100089
PRC
Fax: +1 415 345 1827
EMail: ah_smith@acm.orgFull Copyright Statement ✨
Okay bestie, here's the copyright part 💅 The Internet Society owns the copyright (2002), and all rights are reserved, but you can still do a lot with it. You can copy this document and share it with others, and you can translate it. You can also make derivative works that comment on or explain it, or help people implement it, and you can prepare, copy, publish, and distribute those, in whole or in part, without any restriction of any kind. The one condition is that the above copyright notice and this paragraph must be included on all such copies and derivative works 🎀
The document itself, though, may not be modified in any way. That means no removing the copyright notice or the references to the Internet Society or other Internet organizations. There are two exceptions: you can do it when it's needed for developing Internet standards (in which case the copyright procedures in the Internet Standards process must be followed), or when you need to translate it into languages other than English 🌸
The limited permissions above are perpetual, meaning they will never be revoked by the Internet Society or its successors or assigns. Forever and ever 🦋
Now the legal disclaimer, which I have to say in its own words so nobody gets confused 😭 This document and the information in it is provided on an "AS IS" basis, and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Not a vibe, but very important 💀
Acknowledgement 🫶
The RFC Editor function is currently funded by the Internet Society. Iconic of them, honestly 👑
📦 where this page comes from
- ietf: rfc3290 2002-06
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms