RFC 3247

Supplemental Information for the New Definition of the EF PHB (Expedited Forwarding Per-Hop Behavior)

📅 published March 2002, from ietf

RFC 3247: Supplemental Information for the New Definition of the EF PHB (Expedited Forwarding Per-Hop Behavior) 💖

okay bestie, this one is a Network Working Group doc, and it's Informational 🦋, so it's extra context, not a strict standard. A whole squad wrote it: A. Charny (Cisco Systems, Inc.), J.C.R. Bennett (Motorola), K. Benson (Tellabs), J.Y. Le Boudec (EPFL), A. Chiu (Celion Networks), W. Courtney (TRW), S. Davari (PMC-Sierra), V. Firoiu (Nortel Networks), C. Kalmanek (AT&T Research), and K.K. Ramakrishnan (TeraOptic Networks) 🫶. It's dated March 2002, and the title block doesn't list anything it obsoletes or updates ✨

Status of This Memo 📜

This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.

Copyright (C) The Internet Society (2001). All Rights Reserved.

Abstract 🧠

okay so this doc was written while people were clarifying RFC2598 "An Expedited Forwarding PHB", which then led to the revised spec "An Expedited Forwarding PHB" 🔥. Its main goal is explaining the revised EF definition and its properties. It also brings extra implementation examples and guidance on computing the numerical parameters of the new definition for several well-known schedulers and router architectures 💅

Table of Contents 📚

1      Introduction  ...........................................   2
2      Definition of EF PHB  ...................................   3
2.1    The formal definition  ..................................   3
2.2    Relation to Packet Scale Rate Guarantee  ................   6
2.3    The need for dual characterization of EF PHB  ...........   7
3      Per Packet delay  .......................................   9
3.1    Single hop delay bound  .................................   9
3.2    Multi-hop worst case delay  .............................  10
4      Packet loss  ............................................  10
5      Implementation considerations  ..........................  11
5.1    The output buffered model with EF FIFO at the output.  ..  12
5.1.1  Strict Non-preemptive Priority Queue  ...................  12
5.1.2  WF2Q  ...................................................  13
5.1.3  Deficit Round Robin (DRR)  ..............................  13
5.1.4  Start-Time Fair Queuing and Self-Clocked Fair Queuing  ..  13
5.2    Router with Internal Delay and EF FIFO at the output  ...  13
6      Security Considerations  ................................  14
7      References  .............................................  14
Appendix A. Difficulties with the RFC 2598 EF PHB Definition  ..  16
Appendix B. Alternative Characterization of Packet Scale Rate
            Guarantee  .........................................  20
Acknowledgements  ..............................................  22
Authors' Addresses  ............................................  22
Full Copyright Statement  ......................................  24

1. Introduction 🌸

The Expedited Forwarding (EF) Per-Hop Behavior (PHB) was built for a low-loss, low-latency, low-jitter, assured bandwidth service 🦋. The potential benefits are honestly enormous, which is why the EF PHB is such a big deal. Because this PHB is so valuable, it's critical that the forwarding behavior an EF-compliant node is required to deliver be specific, quantifiable, and unambiguous 💜

Unfortunately, the definition of EF PHB in the original RFC2598 [10] wasn't precise enough (see Appendix A and [4]) 😭. A more precise definition is given in [6]. This document is here to help people understand the properties of that new definition, and it adds supplemental info that wasn't included in the text of [6] for the sake of brevity 🎀

Here's the outline, bestie 🗺️ In section 2, we briefly restate the definition for EF PHB from [6], then add some extra discussion and describe some of its properties. We talk about per-packet delay and loss in sections 3 and 4. In section 5, we look at how known scheduling architectures affect the critical parameters of the new definition. We also cover how real devices that deviate from the ideal output-buffered model change the magnitude of those critical parameters 🧚

2. Definition of EF PHB 💅

2.1. The formal definition ✨

An intuitive explanation of the new EF definition is described in [6]. Here we restate the formal definition from [6] word for word 📖

A node that supports EF on an interface I at some configured rate R MUST satisfy the following equations:

d_j <= f_j + E_a for all j>0                                (eq_1)

where f_j is defined iteratively by

f_0 = 0, d_0 = 0

f_j = max(a_j, min(d_j-1, f_j-1)) + l_j/R,  for all j > 0   (eq_2)

In this definition:

  • d_j is the time that the last bit of the j-th EF packet to depart actually leaves the node from the interface I.
  • f_j is the target departure time for the j-th EF packet to depart from I, the "ideal" time at or before which the last bit of that packet should leave the node.
  • a_j is the time that the last bit of the j-th EF packet destined to the output I actually arrives at the node.
  • l_j is the size (bits) of the j-th EF packet to depart from I. l_j is measured on the IP datagram (IP header plus payload) and does not include any lower layer (e.g. MAC layer) overhead.
  • R is the EF configured rate at output I (in bits/second).
  • E_a is the error term for the treatment of the EF aggregate. Note that E_a represents the worst case deviation between actual departure time of an EF packet and ideal departure time of the same packet, i.e. E_a provides an upper bound on (d_j - f_j) for all j.
  • d_0 and f_0 do not refer to a real packet departure but are used purely for the purposes of the recursion. The time origin should be chosen such that no EF packets are in the system at time 0.
  • For the definitions of a_j and d_j, the "last bit" of the packet includes the layer 2 trailer if present, because a packet cannot generally be considered available for forwarding until such a trailer has been received.

An EF-compliant node MUST be able to be characterized by the range of possible R values that it can support on each of its interfaces while conforming to these equations, and the value of E_a that can be met on each interface. R may be line rate or less. E_a MAY be specified as a worst-case value for all possible R values or MAY be expressed as a function of R.

Note also that, since a node may have multiple inputs and complex internal scheduling, the j-th EF packet to arrive at the node destined for a certain interface may not be the j-th EF packet to depart from that interface. It is in this sense that eq_1 and eq_2 are unaware of packet identity 🤔

In addition, a node that supports EF on an interface I at some configured rate R MUST satisfy the following equations:

D_j <= F_j + E_p for all j>0                                (eq_3)

where F_j is defined iteratively by

F_0 = 0, D_0 = 0

F_j = max(A_j, min(D_j-1, F_j-1)) + L_j/R,  for all j > 0   (eq_4)

In this definition:

  • D_j is the actual departure time of the individual EF packet that arrived at the node destined for interface I at time A_j, i.e., given a packet which was the j-th EF packet destined for I to arrive at the node via any input, D_j is the time at which the last bit of that individual packet actually leaves the node from the interface I.
  • F_j is the target departure time for the individual EF packet that arrived at the node destined for interface I at time A_j.
  • A_j is the time that the last bit of the j-th EF packet destined to the output I to arrive actually arrives at the node.
  • L_j is the size (bits) of the j-th EF packet to arrive at the node that is destined to output I. L_j is measured on the IP datagram (IP header plus payload) and does not include any lower layer (e.g. MAC layer) overhead.
  • R is the EF configured rate at output I (in bits/second).
  • E_p is the error term for the treatment of individual EF packets. Note that E_p represents the worst case deviation between the actual departure time of an EF packet and the ideal departure time of the same packet, i.e. E_p provides an upper bound on (D_j - F_j) for all j.
  • D_0 and F_0 do not refer to a real packet departure but are used purely for the purposes of the recursion. The time origin should be chosen such that no EF packets are in the system at time 0.
  • For the definitions of A_j and D_j, the "last bit" of the packet includes the layer 2 trailer if present, because a packet cannot generally be considered available for forwarding until such a trailer has been received.

It is the fact that D_j and F_j refer to departure times for the j-th packet to arrive that makes eq_3 and eq_4 aware of packet identity. This is the critical distinction between the last two equations and the first two 💖

An EF-compliant node SHOULD be able to be characterized by the range of possible R values that it can support on each of its interfaces while conforming to these equations, and the value of E_p that can be met on each interface. E_p MAY be specified as a worst-case value for all possible R values or MAY be expressed as a function of R. An E_p value of "undefined" MAY be specified.

Finally, there's an additional recommendation in [6] that an EF compliant node SHOULD NOT reorder packets within a microflow 🙈

The definitions described in this section are referred to as aggregate and packet-identity-aware packet scale rate guarantee [4],[2]. An alternative mathematical characterization of packet scale rate guarantee is given in Appendix B 🌈

2.2. Relation to Packet Scale Rate Guarantee 🎀

okay so picture an ideal output-buffered device with an EF FIFO at the output 💅. For a device like that, the i-th packet to arrive is also the i-th packet to depart. So in this ideal model the aggregate behavior and the packet-identity-aware stuff are identical, and E_a = E_p 🫶. That means this section just drops the subscript and calls the latency term plain E.

It could be shown that for such an ideal device, the section 2.1 definition is stronger than the well-known rate-latency curve [2]. If a scheduler satisfies the EF definition, it also satisfies the rate-latency curve, so every property known for the rate-latency curve also applies to the modified EF definition ✨. BUT (and this is the lowkey important part 👀) we argue below that the section 2.1 definition is a better match for what the EF PHB is actually trying to do than the rate-latency curve is 🌸.

It is shown in [2] that the rate-latency curve is equivalent to the following definition:

Definition of Rate Latency Curve (RLC):

   D(j) <= F'(j) + E                                           (eq_5)

where

   F'(0)=0, F'(j)=max(a(j), F'(j-1))+ L(j)/R for all j>0       (eq_6)

It's easy to verify that the EF definition of section 2.1 is stronger than RLC, because for all j, F'(j) >= F(j) 💖.

F'(j) in the RLC definition is basically the time the j-th departure should have happened if the EF aggregate were constantly served at exactly its configured rate R 🧚. Following the usual convention, we call F'(j) the "fluid finish time" of the j-th packet to depart 🦋.

The vibe of the rate-latency curve is that any packet gets served at most time E later than it would have finished in the fluid model 💅.

For RLC (and therefore for the stronger EF definition), in any interval (0,t) the EF aggregate gets close to the desired service rate R, as long as there's enough traffic to sustain that rate 🔥. How far off the ideal and actual service are in that interval depends on the latency term E, and E depends on how the scheduler is actually implemented 🍓. The smaller E is, the smaller the gap between the configured rate and the rate the scheduler actually delivers ✨.

Here's the catch though 😭. RLC guarantees the desired rate to the EF aggregate in every interval (0,t), within a specified error, but it can still leave big gaps in service. Say a large number (N) of identical EF packets of length L arrive from different interfaces to the EF queue, with no non-EF traffic around. Then any work-conserving scheduler will serve all N packets at link speed. When the last packet goes out at time NL/C, where C is the capacity of the output link, F'(N) will equal NL/R. So the scheduler is running ahead of ideal, since NL/C < NL/R for R < C 🏃‍♀️.

Now suppose that at time NL/C a bunch of non-EF packets arrive, followed by a single EF packet. The scheduler can legitimately wait to start sending that EF packet until time F'(N+1)=(N+1)L/R + E - L/C. That means the EF aggregate gets no service at all during the interval (NL/C, (N+1)L/R + E - L/C) 💀. That interval can be pretty huge if R is much smaller than C. Basically, the EF aggregate gets "punished" with a service gap for having been served faster than its configured rate at the start 🙈.

The new EF definition fixes this by adding the term min(D(j-1), F(j-1)) into the recursion 👑. In plain English, the fluid finishing time gets "reset" whenever a packet is sent before its "ideal" departure time 🌈. Because of that, when the EF aggregate is served in FIFO order, suppose a packet arrives at time t to a server that satisfies the EF definition. That packet will be transmitted no later than time t + Q(t)/R + E, where Q(t) is the EF queue size at time t (including the packet we're talking about) [4] 🫶.

2.3. The need for dual characterization of EF PHB 🦋

In a more general case, things get messier 😵‍💫. Either the output scheduler doesn't serve EF packets in FIFO order, or the variable internal delay in the device reorders packets on their way to the output (or both). In that case, the i-th packet destined for a given output interface to arrive at the device may no longer be the i-th packet to depart from that interface. So the packet-identity-aware definition and the aggregate definition are no longer the same thing 🙃.

The aggregate behavior definition is a truly aggregate view of the service EF packets get 🎀. Think of a dark reservoir where every arriving packet gets dumped in 🌊. The scheduler can grab packets out of the reservoir in any random order, with zero knowledge of the arrival order 🎲. The aggregate part of the definition measures how accurately the EF aggregate, as a whole, gets the output rate. The smaller E_a is, the more confident we can be that the reservoir drains at least at the configured rate ✨.

In this reservoir analogy, packets in the EF aggregate can be reordered arbitrarily 😳. However, the definition of EF PHB given in [6] explicitly says that no packet reordering may occur within a microflow 💜. That rule limits how scheduling can be implemented. In the reservoir analogy, it means the order you pull packets out has to make sure packets in a microflow don't get swapped, but reordering at the aggregate level is still allowed 🧚.

Reordering within the aggregate, as long as there's no flow-level reordering, doesn't automatically mean the service is bad 🙌. Take a scheduler arbitrating among 10 different EF "flows" with different rates. A scheduler that knows the rate requirements might send a packet from the faster flow before a packet from the slower flow, to keep jitter low at the flow level 🏎️. Actually, an ideal "flow"-aware WFQ scheduler will cause reordering within the aggregate while keeping packet order and small jitter at the flow level ✨. Iconic, honestly 👑.

It's intuitively clear that for a scheduler like that, and for a simpler FIFO scheduler too, the "accuracy" of the service rate is crucial for keeping flow-level jitter down 💖. The packet-identity-aware definition is what quantifies that accuracy 📏.

BUT, a small E_a doesn't promise anything about the absolute per-packet delay 😬. In fact, if the input rate exceeds the configured rate, the aggregate behavior definition can allow arbitrarily large delay for a subset of packets 💀. That's the main reason the packet-identity-aware definition exists 🫶.

The primary goal of the packet-aware characterization of an EF implementation is that, unlike the aggregate behavior characterization, it gives you a way to find a per-packet delay bound as a function of the input traffic parameters 🎯.

So the aggregate behavior definition measures the accuracy of the service rate for the whole EF aggregate, and the packet-identity-aware part measures how far the device is from an ideal server that serves the EF aggregate in FIFO order at least at the configured rate 🔍.

The value of E_p in the packet-identity-aware definition is affected by two things: how accurate the aggregate rate service is, and how much packets within the EF aggregate get reordered (as long as packets in the same microflow aren't reordered) 🌀. So a sub-aggregate aware device that gives an ideal service rate to the aggregate, AND an ideal rate service to each of the sub-aggregates, can still have a really large E_p. In that case E_p has to be at least the ratio of the maximum packet size to the smallest rate of any sub-aggregate 🤯. So a large E_p doesn't necessarily mean the service for the EF aggregate is bad. It might just mean the service is good but non-FIFO 🙂. On the other hand, a large E_p could also mean the aggregate service is very inaccurate (bursty), in which case the large E_p reflects poor implementation quality 😤.

So a large number of E_p doesn't necessarily tell you anything about the quality of the EF implementation 🤷‍♀️. A small value of E_p, though, does indicate a high-quality FIFO implementation ✨.

Since E_p and E_a relate to different aspects of the EF implementation, they should be considered together when you're judging the quality of the implementation 💅🫶.

3. Per Packet delay 🧁

The main reason the packet-identity-aware definition exists is that it lets you quantify a per-packet delay bound 🎀. This section talks about the issues involved in computing per-packet delay 🧐.

3.1. Single hop delay bound 🦋

Say the total traffic arriving at an output port I from all inputs is constrained by a leaky bucket with parameters (R, B). Here R is the configured rate at I, and B is the bucket depth (burst). Then the delay of any packet departing from I is bounded by D_p, given by:

   D_p = B/R + E_p                                             (eq_7)

(see appendix B) 📖.

The delay bound depends on the configured rate R and the input burstiness B, so it's really useful for both of these parameters to be visible to a user of the device 👀. A PDB (Per-Domain Behavior) that wants a particular delay bound might need to limit the range of configured rates and allowed burstiness it can support in order to actually deliver that bound 🎯. Equation (eq_7) gives you a way to figure out an acceptable operating region for the device with a given E_p 🗺️. It can also be useful to limit the total offered load to some output to a rate R_1 < R (for example, to get end-to-end delay bounds [5]) 🔗. Important detail: even though R_1 might be a configurable parameter of the device too, the delay bound in (eq_7) does NOT depend on it 🙅‍♀️. It may be possible to get tighter bounds by explicitly using the bound on the input rate, but the bound in (eq_7) doesn't take advantage of that information 🥲.

3.2. Multi-hop worst case delay 🧶

okay so, even though the PHB is inherently local (it only cares about what happens at one hop), we're gonna talk about per-packet delay as a packet hops through several routers running EF PHB 🦋 Like, if you have a delay bound (eq_7) at a single hop, it's SO tempting to think the bound across h hops is just h times (eq_7). ngl, that's not necessarily true 🙈 It only works if B is the worst case input burstiness across ALL the nodes in the network.

and getting that worst case B value is not trivial at all 😭 If EF PHB is done with aggregate class-based scheduling, where every EF packet shares a single FIFO, jitter accumulation can make burstiness grow from hop to hop. It can be shown that, unless you put severe restrictions on EF utilization, even if every EF flow is ideally shaped at the ingress, then for any delay D you can build a network where EF utilization on any link is bounded to not exceed a given factor, no flow crosses more than a specified number of hops, and yet there's still a packet that gets delayed more than D [5]. main character energy of a problem 💀

this means that limiting worst case burstiness and the end-to-end delay across several hops might need more than just limiting EF utilization on every link. you might also have to constrain the global network topology 🗺️ and those topology constraints would need to be specified in the definition of any PDB built on top of EF PHB, but only if that PDB needs a strict worst case delay bound ✨

4. Packet loss 🍓

any device with finite buffering may need to drop packets if the input burstiness gets high enough 📦 To meet the low loss objective of EF, a node can be characterized by its operating region, the region where EF loss due to congestion will not happen. This can be specified as a token bucket with rate r <= R and burst size B that can be offered from all inputs to a given output interface without loss.

BUT, as we talked about in the previous section, jitter accumulation makes it really hard to guarantee the input burstiness never goes beyond the specified operating region for nodes inside the DiffServ domain 😩 A no-loss guarantee across multiple hops might need constraints on network topology, and those are outside the scope of the inherently local definition of a PHB. so, it must be possible to figure out whether a device conforms to the EF definition even when some packets are lost 🫶

this can be done with an "off-line" conformance test against equations (eq_1)- (eq_4). after observing a sequence of packets entering and leaving the node, the packets that did not leave are assumed lost and are notionally removed from the input stream. the remaining packets become the arrival stream, and the packets that left the node become the departure stream. so conformance to the equations can be verified by only looking at the packets that successfully made it through the node 🌸

also, what packets get lost when loss does happen is beyond the scope of the EF PHB definition 🙅‍♀️ but the packets that weren't lost must conform to the equations definition of EF PHB in section 2.1 💖

5. Implementation considerations 🔧

a packet going through a router is gonna experience delay for a bunch of reasons ⏱️ two familiar pieces are the time it sits in a buffer at an outgoing link waiting for the scheduler to pick it, and the time it takes to actually transmit the packet onto the outgoing line.

there can be other parts of a packet's delay through a router too ✨ for example, a router might have to do some header processing before the packet can be handed to the correct output scheduler. in another case, a router might have a FIFO buffer (called a transmission queue in [7]) where the packet waits after being picked by the output scheduler but before it's transmitted. in cases like these, the extra delay can be absorbed into the latency terms E_a and E_p 🧚

implementing EF on a router with a multi-stage switch fabric needs special attention 👀 a packet might get extra delays because it has to compete with other traffic for forwarding resources at multiple contention points in the switch core. the delay an EF packet experiences before it even reaches the output-link scheduler should be included in the latency term. input-buffered and input/output-buffered routers based on crossbar design may also need their latency terms modified. factors like the speedup factor and the choice of crossbar arbitration algorithm can affect the latency terms a lot 🔥

delay in the switch core comes from two sources, and both have to be considered 💅 the first part is the fixed delay a packet experiences no matter what other traffic is around. this includes things like packet segmentation and reassembly in cell based cores, enqueueing and dequeuing at each stage, and transmission between stages. the second part is variable and depends on the type and amount of other traffic going through the core. this delay shows up when the stages in the core mix traffic flowing between different input/output port pairs. so EF packets have to compete against other traffic for forwarding resources in the core, and some of that competing traffic might even come from other, non-EF aggregates 😭 this adds extra delay, which can also be absorbed by the latency term in the definition.

to capture all of this, in this section we'll look at two simplified implementation examples 🎀

the first is an ideal output buffered node, where packets entering from an input interface are immediately delivered to the output scheduler. in this model, the properties of the output scheduler fully define the values of the parameters E_a and E_p. we'll look at the case where the output scheduler does aggregate class-based queuing, so all EF packets share a single queue. we'll also talk about the values of E_a and E_p for a bunch of class-based schedulers that are widely considered 🌈

the second example is a router modeled as a black box, with a known bound on the variable delay a packet can experience from the time it arrives at an input to the time it's delivered to its destination output. the output scheduler on its own is assumed to be an aggregate scheduler where all EF packets share a single FIFO queue, with a known value of E_a(S)=E_p(S)=E(S). this model is a reasonable abstraction for a large class of router implementations 🦋

5.1. The output buffered model with EF FIFO at the output. 💜

like we mentioned earlier, in this model E_a = E_p, so we'll drop the subscript and just call both terms the latency E. the rest of this subsection goes over E for a number of scheduling implementations ✨

5.1.1. Strict Non-preemptive Priority Queue 👑

a Strict Priority scheduler, where all EF packets share a single FIFO queue that is served at strict non-preemptive priority over other queues, satisfies the EF definition with the latency term E = MTU/C, where MTU is the maximum packet size and C is the speed of the output link 🔥

5.1.2. WF2Q 🌸

another scheduler that satisfies the EF definition with a small latency term is WF2Q, described in [1]. a class-based WF2Q scheduler, where all EF traffic shares a single queue with the weight matching the configured rate of the EF aggregate, satisfies the EF definition with the latency term E = MTU/C+MTU/R 💅

5.1.3. Deficit Round Robin (DRR) 🍓

for DRR [12], E can be shown to grow linearly with N*(r_max/r_min)*MTU, where r_min and r_max are the smallest and the largest rate among the rate assignments of all queues in the scheduler, and N is the number of queues in the scheduler 🧮

5.1.4. Start-Time Fair Queuing and Self-Clocked Fair Queuing 🫧

for Start-Time Fair Queuing (SFQ) [9] and Self-Clocked Fair Queuing (SCFQ) [8], E can be shown to grow linearly with the number of queues in the scheduler 🎀

5.2. Router with Internal Delay and EF FIFO at the output 🧚

in this section we're looking at a router modeled like this 🖤 a packet entering the router may experience a variable delay D_v with a known upper bound D. that means 0<=D_v<=D. at the output, all EF packets share a single class queue. class queues get scheduled by a scheduler with a known value E_p(S)=E(S), where E(S) corresponds to the model where this scheduler is implemented in an ideal output buffered device 🌟

the computation of E_p is more complicated in this case 😵‍💫 for this kind of device, it can be shown that E_p = E(S)+2D+2B/R (see [13]).

remember from section 3 that bounding input burstiness B might not be easy in a general topology 🙃 without knowing a bound on B, you can bound E_p as E_p = E(S) + D*C_inp/R (see [13]).

also note that the bounds in this section are derived using only the bound on the variable portion of the interval delay and the error bound of the output scheduler. if more details about a device's architecture are available, it may be possible to compute better bounds 🫶

6. Security Considerations 🔐

this informational document provides additional information to help with understanding the EF PHB described in [6] 📖 it adds no new functions to it. as a result, it adds no security issues beyond those already described in that specification.

7. References ✨

[1] J.C.R. Bennett and H. Zhang, "WF2Q: Worst-case Fair Weighted Fair Queuing", INFOCOM'96, March 1996. 🎀

[2] J.-Y. Le Boudec, P. Thiran, "Network Calculus", Springer Verlag Lecture Notes in Computer Science volume 2050, June 2001 (available online at http://lcawww.epfl.ch). 📚

[3] Bradner, S., "Key Words for Use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 💅

[4] J.C.R. Bennett, K. Benson, A. Charny, W. Courtney, J.Y. Le Boudec, "Delay Jitter Bounds and Packet Scale Rate Guarantee for Expedited Forwarding", Proc. Infocom 2001, April 2001. ✨

[5] A. Charny, J.-Y. Le Boudec "Delay Bounds in a Network with Aggregate Scheduling". Proc. of QoFIS'2000, September 25-26, 2000, Berlin, Germany. 🌸

[6] Davie, B., Charny, A., Baker, F., Bennett, J.C.R., Benson, K., Boudec, J., Chiu, A., Courtney, W., Davari, S., Firoiu, V., Kalmanek, C., Ramakrishnan, K.K. and D. Stiliadis, "An Expedited Forwarding PHB (Per-Hop Behavior)", RFC 3246, March 2002. 🦋

[7] T. Ferrari and P. F. Chimento, "A Measurement-Based Analysis of Expedited Forwarding PHB Mechanisms," Eighth International Workshop on Quality of Service, Pittsburgh, PA, June 2000. 🧚

[8] S.J. Golestani. "A Self-clocked Fair Queuing Scheme for Broadband Applications". In Proceedings of IEEE INFOCOM'94, pages 636-646, Toronto, CA, April 1994. 💜

[9] P. Goyal, H.M. Vin, and H. Chen. "Start-time Fair Queuing: A Scheduling Algorithm for Integrated Services". In Proceedings of the ACM-SIGCOMM 96, pages 157-168, Palo Alto, CA, August 1996. 🔥

[10] Jacobson, V., Nichols, K. and K. Poduri, "An Expedited Forwarding PHB", RFC 2598, June 1999. 👑

[11] Jacobson, V., Nichols, K. and K. Poduri, "The 'Virtual Wire' Behavior Aggregate", Work in Progress. 🌈

[12] M. Shreedhar and G. Varghese. "Efficient Fair Queuing Using Deficit Round Robin". In Proceedings of SIGCOMM'95, pages 231-243, Boston, MA, September 1995. 🍓

[13] Le Boudec, J.-Y., Charny, A. "Packet Scale Rate Guarantee for non-FIFO Nodes", Infocom 2002, New York, June 2002. 🫶

Appendix A. Difficulties with the RFC 2598 EF PHB Definition ✨

Okay so this appendix is where we dig into why the RFC 2598 EF PHB definition is a little bit messy. 🙈 Here's what [10] says the EF PHB is:

"The EF PHB is defined as a forwarding treatment for a particular diffserv aggregate where the departure rate of the aggregate's packets from any diffserv node must equal or exceed a configurable rate. The EF traffic SHOULD receive this rate independent of the intensity of any other traffic attempting to transit the node. It [the EF PHB departure rate] SHOULD average at least the configured rate when measured over any time interval equal to or longer than the time it takes to send an output link MTU sized packet at the configured rate."

Read literally, that definition would call the behaviours in the next two subsections non-compliant. 😭 It also needlessly caps how high the configured rate of an EF aggregate can go. 💀

A.1 Perfectly-Clocked Forwarding

Let's picture a router with EF configured rate R=C/2, where C is the output line rate. 🎀 In the diagram, E is an MTU-sized EF packet, and x is either a non-EF packet or unused capacity, also MTU-sized.

E x E x E x E x E x E x...
 |-----|

The gap between the vertical bars is 3*MTU/C, which is bigger than MTU/(C/2), so the EF PHB definition applies to that window. ✨ During that window, 3*MTU/2 bits of the EF aggregate should be forwarded, but only MTU bits actually go out. So even though this pattern should be considered compliant under any sensible reading of the EF PHB, it technically doesn't match the definition in RFC 2598. 🤯

Note that this forwarding pattern can occur in any work-conserving scheduler in an ideal output-buffered architecture where EF packets arrive in a perfectly clocked manner according to the above pattern and are forwarded according to exactly the same pattern in the absence of any non-EF traffic. 🧚

Trivial as this example may be, it reveals the lack of mathematical precision in the formal definition. 🙃 The fact that no work-conserving scheduler can formally comply with the definition is unfortunate, and it appears to warrant some changes to the definition that would correct this problem. 🔥

The underlying reason for the problem is quite simple: you can only expect the EF aggregate to be served at its configured rate in some interval where there is enough backlog of EF packets to sustain that rate. 💅 In the example above, the packets come in at exactly the rate at which they're served, so there's no persistent backlog. Certainly, if the input rate is even smaller than the configured rate of the EF aggregate, there will be no backlog either, and a similar formal difficulty will show up. 🌸

A seemingly simple fix might be to require that the EF aggregate is served at its configured rate only when the queue is backlogged. 🫶 However, as we show in the rest of this section, that fix does not suffice. 💔

A.2 Router Internal Delay

We're about to show that this example is not as trivial as it looks at first glance. 👀

Consider a router with EF configured rate R = C/2, like in the previous example, but with an internal delay of 3T (where T = MTU/C) between the time a packet arrives at the router and the time it is first eligible for forwarding at the output link. 🍓 Things like header processing, route look-up, and delay in switching through a multi-layer fabric could cause this delay. Now suppose EF traffic arrives regularly at a rate of (2/3)R = C/3. The router performs as shown below.

EF Packet Number 1 2 3 4 5 6 ...

Arrival (at router) 0 3T 6T 9T 12T 15T ...

Arrival (at scheduler) 3T 6T 9T 12T 15T 18T ...

Departure 4T 7T 10T 13T 16T 19T ...

Again, the output does not satisfy the RFC 2598 definition of EF PHB. 😤 As in the previous example, the root cause is that the scheduler cannot forward EF traffic faster than it arrives. But here's the twist: internal delay means one packet is always sitting inside the router. 🙈 An external observer will rightfully conclude that the number of EF packets that arrived at the router is always at least one greater than the number that left, so the EF aggregate is constantly backlogged. 🧠 Even so, while the EF aggregate is continuously backlogged, the observed output rate is still strictly less than the configured rate. 😭

This example shows that simply adding the condition that the EF aggregate must receive its configured rate only when the EF aggregate is backlogged does not suffice in this case. 💀

Still, this problem matters a lot in practice. Most routers have some amount of internal delay. A vendor declaring EF compliance is not expected to also disclose the internals of the router. 🌈 So the existence of internal delay may cause a perfectly reasonable EF implementation to look non-conformant, which is clearly undesirable. 🙅‍♀️

A.3 Maximum Configurable Rate and Provisioning Efficiency

It is well understood that with any non-preemptive scheduler, the RFC-2598-compliant configurable rate for an EF aggregate cannot exceed C/2 [11]. 👑 This is because an MTU-sized EF packet may arrive to an empty queue at time t just as an MTU-sized non-EF packet begins service. The maximum number of EF bits that could be forwarded during the interval [t, t + 2*MTU/C] is MTU. But if the configured rate R > C/2, that interval is longer than MTU/R, and more than MTU EF bits would have to be served during it for the router to be compliant. So R must be no greater than C/2. 🧮

It can be shown that for schedulers other than PQ, such as various implementations of WFQ, the maximum compliant configured rate may be much smaller than 50%. 📉 For example, for SCFQ [8], the maximum configured rate cannot exceed C/N, where N is the number of queues in the scheduler. For WRR, which is mentioned as compliant in section 2.2 of RFC 2598, this limitation is even more severe. 😬 In these schedulers, a packet arriving to an empty EF queue may be forced to wait until one packet from each other queue (in the case of SCFQ), or until several packets from each other queue (in the case of WRR), are served before it is finally forwarded. 🐢

It's often assumed that the configured rate of EF traffic will be a lot smaller than the link bandwidth, but the requirement that this rate should never exceed 50% of the link bandwidth seems unnecessarily limiting. 🤷‍♀️ For example, in a fully connected mesh network, where any flow traverses a single link on its way from source to destination, there's no compelling reason to cap EF traffic at 50% (or an even smaller percentage for some schedulers) of the link bandwidth. 🌟

An even more striking example is that even a TDM circuit with dedicated slots cannot be configured to forward EF packets at more than 50% of the link speed without violating RFC 2598 (unless the entire link is configured for EF). 😱 If the configured rate of EF traffic is greater than 50% (but less than the link speed), there will always be an interval longer than MTU/R in which less than the configured rate is achieved. For example, suppose the configured rate of the EF aggregate is 2C/3. Then the forwarding pattern of the TDM circuit might be:

E E x E E x E E x ...
   |---|

Only one packet is served in the marked interval of length 2T = 2MTU/C. But at least 4/3 MTU would have to be served during this interval by a router in compliance with the definition in RFC 2598. 🥲 The fact that even a TDM line can't be booked over 50% by EF traffic shows that the restriction is artificial and unnecessary. 💖

A.4 The Non-trivial Nature of the Difficulties

okay so the first idea people usually have is to just clarify which intervals the definition applies to, or average over several intervals 🫶. bestie, that gets messy fast 😭. lining up interval start times with the epochs of the forwarded stream seems to need a real amount of global clock synchronization, and that's a whole risk for misinterpretation and mistakes in practice 💀.

another idea is to let the rates average over a larger time scale. ngl, it's unclear what finite time scale would even be enough in all reasonable cases 🤔. and it would kinda wreck the vibe of very short-term guarantees, which is literally the essence of the EF PHB 💜.

we also tried combining two simple fixes 🎀. fix one: only count the intervals that fall inside a period where the EF aggregate is continuously backlogged in the router (aka when an EF packet is in the router). fix two: add an error (latency) term that could work as a figure-of-merit when advertising EF services ✨.

with both changes, the candidate definition becomes:

In any interval of time (t1, t2) in which EF traffic is continuously backlogged, at least R(t2 - t1 - E) bits of EF traffic must be served, where R is the configured rate for the EF aggregate and E is an implementation-specific latency term.

the "continuously backlogged" condition gets rid of the insufficient-packets-to-forward difficulty 🙌. adding a latency term of size MTU/C fixes the perfectly-clocked forwarding example from section A.1 🦋, and it also removes the limitation on the EF configured rate 👑.

but here's the tea 🙈: neither fix (nor both together) resolves the example in section A.2. recall that in that example the EF aggregate is continuously backlogged, but the service rate of the EF aggregate is consistently smaller than the configured rate. so no finite latency term will be enough to bring the example into conformance 💀.

Appendix B. Alternative Characterization of Packet Scale Rate Guarantee

the proofs of several bounds in this document can be found in [13] 📚. those proofs use an algebraic characterization of the aggregate definition given by (eq_1), (eq_2), and the packet identity aware definition given by (eq_3), (eq_4). since this characterization is of interest on its own, we present it right here in this section 🧚.

Theorem B1. Characterization of the aggregate definition without f_n.

consider a system where packets are numbered 1, 2, ... in order of arrival. as in the aggregate definition, call a_n the n-th arrival time, d_n - the n-th departure time, and l_n the size of the n-th packet to depart. define by convention d_0=0. the aggregate definition with rate R and latency E_a is equivalent to saying that for all n and all 0<=j<= n-1:

d_n <= E_a + d_j + (l_(j+1) + ... + l_n)/R                 (eq_b1)

or

there exists some j+1 <= k <= n such that

d_n  <= E_a + a_k + (l_k + ... + l_n)/R                    (eq_b2)

Theorem B2. Characterization of packet-identity-aware definition without F_n.

consider a system where packets are numbered 1, 2, ... in order of arrival. as in the packet-identity-aware definition, call A_n, D_n the arrival and departure times for the n-th packet, and L_n the size of this packet. define by convention D_0=0. the packet identity aware definition with rate R and latency E_p is equivalent to saying that for all n and all 0<=j<= n-1:

D_n <= E_p + D_j + (L_{j+1} + ... + L_n)/R                 (eq_b3)

or

there exists some j+1 <= k <= n such that

D_n  <= E_p + A_k + (L_k + ... + L_n)/R                    (eq_b4)

for the proofs of both Theorems, see [13] 🔍.

Acknowledgements

this document could not have been written without Fred Baker, Bruce Davie and Dimitrios Stiliadis 🫶. their time, support and insightful comments were invaluable 🌸.

Authors' Addresses

Anna Charny
Cisco Systems
300 Apollo Drive
Chelmsford, MA 01824

EMail: acharny@cisco.com

Jon Bennett
Motorola
3 Highwood Drive East
Tewksbury, MA 01876

EMail: jcrb@motorola.com

Kent Benson
Tellabs Research Center
3740 Edison Lake Parkway #101
Mishawaka, IN  46545

EMail: Kent.Benson@tellabs.com

Jean-Yves Le Boudec
ICA-EPFL, INN
Ecublens, CH-1015
Lausanne-EPFL, Switzerland

EMail: jean-yves.leboudec@epfl.ch

Angela Chiu
Celion Networks
1 Sheila Drive, Suite 2
Tinton Falls, NJ 07724

EMail: angela.chiu@celion.com
Bill Courtney
TRW
Bldg. 201/3702
One Space Park
Redondo Beach, CA 90278

EMail: bill.courtney@trw.com

Shahram Davari
PMC-Sierra Inc
411 Legget Drive
Ottawa, ON K2K 3C9, Canada

EMail: shahram_davari@pmc-sierra.com

Victor Firoiu
Nortel Networks
600 Tech Park
Billerica, MA 01821

EMail: vfiroiu@nortelnetworks.com

Charles Kalmanek
AT&T Labs-Research
180 Park Avenue, Room A113,
Florham Park NJ

EMail: crk@research.att.com

K.K. Ramakrishnan
TeraOptic Networks, Inc.
686 W. Maude Ave
Sunnyvale, CA 94086

EMail: kk@teraoptic.com

Copyright (C) The Internet Society (2001). All Rights Reserved. 💖

you're allowed to copy this document and share it with others, and to make derivative works that comment on or explain it, or help with implementing it 🎀. you can publish and distribute those copies and works, in whole or in part, without restriction of any kind. the one catch is that the copyright notice and this paragraph must be included on all such copies and derivative works ✨. the document itself may not be modified in any way (no removing the copyright notice or the references to the Internet Society or other Internet organizations), except as needed for developing Internet standards, in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English 🌈.

the permissions above are perpetual and will not be revoked by the Internet Society or its successors or assigns 🦋.

this document and the information in it are 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. 💀

Acknowledgement

funding for the RFC Editor function is currently provided by the Internet Society 💜👑

📦 where this page comes from