Network Working Group                                          A. Charny
Request for Comments: 3247                           Cisco Systems, Inc.
Category: Informational                                   J.C.R. Bennett
                                                               K. Benson
                                                          J.Y. Le Boudec
                                                                 A. Chiu
                                                         Celion Networks
                                                             W. Courtney
                                                               S. Davari
                                                               V. Firoiu
                                                         Nortel Networks
                                                             C. Kalmanek
                                                           AT&T Research
                                                       K.K. Ramakrishnan
                                                      TeraOptic Networks
                                                              March 2002
            Supplemental Information for the New Definition
         of the EF PHB (Expedited Forwarding Per-Hop Behavior)

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 Notice


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




This document was written during the process of clarification of RFC2598 "An Expedited Forwarding PHB" that led to the publication of revised specification of EF "An Expedited Forwarding PHB". Its primary motivation is providing additional explanation to the revised EF definition and its properties. The document also provides additional implementation examples and gives some guidance for computation of 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
1. はじめに

The Expedited Forwarding (EF) Per-Hop Behavior (PHB) was designed to be used to build a low-loss, low-latency, low-jitter, assured bandwidth service. The potential benefits of this service, and therefore the EF PHB, are enormous. Because of the great value of this PHB, it is critical that the forwarding behavior required of and delivered by an EF-compliant node be specific, quantifiable, and unambiguous.

緊急転送(EF)ホップ単位動作(PHB)は、低損失、低遅延、低ジッタ、保証帯域幅サービスを構築するために使用されるように設計されました。このサービスの潜在的な利点、したがってEF PHBは、莫大です。このため、PHBの大きな価値、転送動作を必要とEF準拠のノードによって提供さは、特定の定量化、および明確なことが重要です。

Unfortunately, the definition of EF PHB in the original RFC2598 [10] was not sufficiently precise (see Appendix A and [4]). A more precise definition is given in [6]. This document is intended to aid in the understanding of the properties of the new definition and provide supplemental information not included in the text of [6] for sake of brevity.

残念ながら、元のRFC2598 [10]におけるEF PHBの定義は十分に正確ではなかった(付録Aを参照し、[4])。より正確な定義は、[6]に記載されています。この文書は、新しい定義の性質の理解を助けると簡潔さのために[6]のテキストに含まれていない補足情報を提供することを意図しています。

This document is outlined as follows. In section 2, we briefly restate the definition for EF PHB of [6]. We then provide some additional discussion of this definition and describe some of its properties. We discuss the issues associated with per-packet delay and loss in sections 3 and 4. In section 5 we discuss the impact of known scheduling architectures on the critical parameters of the new definition. We also discuss the impact of deviation of real devices from the ideal output-buffered model on the magnitude of the critical parameters in the definition.


2. Definition of EF PHB
2.1. The formal definition
2.1. 正式な定義

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


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)

d_j 0(eq_1)<= F_J + E_Aすべてのjについて>

where f_j is defined iteratively by


f_0 = 0, d_0 = 0

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)

全てのj> 0(eq_2)用F_J = MAX(a_j、分(d_j-1、F_J-1))+ l_j / R、

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.

- d_jはj番目のEFパケットの最後のビットが出発すること時間は、実際にはインターフェース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.

- F_JはI、そのパケットの最後のビットは、ノードを離れなければならないのか、前に「理想的な」時間から逸脱するj番目のEFパケットのターゲット出発時刻です。

- 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.

- a_jは、j番目のEFパケットの最後のビットは、私が実際にノードに到着出力に宛てている時間です。

- 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.

- l_j I.のl_j逸脱するj番目のEFパケットのサイズ(ビット)は、IPデータグラム(IPヘッダーとペイロード)で測定され、任意の下位層(例えばMAC層)オーバーヘッドを含みません。

- R is the EF configured rate at output I (in bits/second).

- Rは、I(ビット/秒)出力でEF設定されたレートです。

- 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.

- E_Aは、EF集合体の治療のための誤差項です。すべてのjについて - E_AがEFパケットの実際の出発時間と同じパケットの理想的な出発時刻との間の最悪の場合の偏差を表している、すなわちE_Aは(F_J d_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.

- D_0とF_0は、実際のパケット出発を参照しませんが、再帰の目的のために純粋に使用されています。時間原点にはEFパケットが時間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.

- 存在する場合、パケットは、一般に、トレーラが受信されるまで転送するために使用可能と考えることができないのでa_jとd_jの定義については、パケットの「最後のビットが」レイヤ2トレーラを含みます。

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.

EF準拠のノードは、これらの式に準拠しながら、そのインターフェースのそれぞれにサポートすることができる可能なR値の範囲、及び各インタフェース上で満たすことができるE_Aの値によって特徴付けることができなければなりません。 Rは、回線速度以下であってもよいです。 E_Aは、すべての可能なR値に対する最悪の場合の値として指定してもよく、または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)

D_j 0(eq_3)<= F_J + E_pすべてのjについて>

where F_j is defined iteratively by


F_0 = 0, D_0 = 0

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)

F_J = MAX(A_j、分(D_j-1、F_J-1))+ L_j / R、全ての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.

- D_jは、私は、任意の入力を介してノードに到着する宛j番目のEFパケットたパケット与えられ、すなわちA_j時インターフェイスIを宛先ノードに到着した個々のEFパケットの実際の出発時間でありますD_jは、個々のパケットの最後のビットが実際に界面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.

- F_Jは時間A_jでインタフェースI宛てのノードに到着した個々のEFパケットのターゲット出発時刻です。

- 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.

- A_jは私が到着する出力宛てのj番目のEFパケットの最後のビットが実際にノードに到着する時間です。

- 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.

- L_j出力I. L_jを宛先とするノードに到達するj番目のEFパケットのサイズ(ビット)は、IPデータグラム(IPヘッダーとペイロード)で測定され、任意の下位層(例えばMACが含まれていません層)のオーバーヘッド。

- R is the EF configured rate at output I (in bits/second).

- Rは、I(ビット/秒)出力でEF設定されたレートです。

- 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.

- E_pは、個々のEFパケットの処理のための誤差項です。すべてのjについて - E_p、すなわちE_p、EFパケットの実際の出発時間と同じパケットの理想的な出発時刻との間の最悪の場合の偏差を表す(F_J D_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.

- D_0とF_0は、実際のパケット出発を参照しませんが、再帰の目的のために純粋に使用されています。時間原点にはEFパケットが時間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.

- 存在する場合、パケットは、一般に、トレーラが受信されるまで転送するために使用可能と考えることができないのでA_jとD_jの定義については、パケットの「最後のビットが」レイヤ2トレーラを含みます。

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.

EF準拠のノードは、これらの式に準拠しながら、そのインターフェースのそれぞれにサポートすることができる可能なR値の範囲、及び各インタフェース上で満たすことができるE_pの値によって特徴付け可能であるべきです。 E_pは、すべての可能なR値に対する最悪の場合の値として指定してもよく、または「未定義」のR.アンE_p値の関数を指定することができるように表すことができます。

Finally, there is an additional recommendation in [6] that an EF compliant node SHOULD NOT reorder packets within a micorflow.


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
2.2. パケットスケールレートギャランティーとの関係

Consider the case of an ideal output-buffered device with an EF FIFO at the output. For such a device, the i-th packet to arrive to the device is also the i-th packet to depart from the device. Therefore, in this ideal model the aggregate behavior and packet-identity-aware characteristics are identical, and E_a = E_p. In this section we therefore omit the subscript and refer to the latency term simply as E.

出力におけるEF FIFO理想的な出力緩衝装置の場合を考えます。そのようなデバイスのために、デバイスに到達するi番目のパケットは、デバイスから逸脱するi番目のパケットです。したがって、この理想的なモデルに凝集挙動及びパケット識別認識特性は同一であり、E_A = E_p。このセクションでは、我々は、したがって、添字を省略し、Eと待ち時​​間という用語は、単に参照します

It could be shown that for such an ideal device the definition of section 2.1 is stronger than the well-known rate-latency curve [2] in the sense that if a scheduler satisfies the EF definition it also satisfies the rate-latency curve. As a result, all the properties known for the rate-latency curve also apply to the modified EF definition. However, we argue below that the definition of section 2.1 is more suitable to reflect the intent of EF PHB than the rate-latency curve.


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)

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



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

F '(0)= 0、F'(J)= MAX((J)、F '(J-1))のために+ L(J)/ R全てのj> 0(eq_6)

It can be easily verified that the EF definition of section 2.1 is stronger than RLC by noticing that for all j, F'(j) >= F(j).

容易セクション2.1のEF定義は、すべてのjについて、F '(J)> = F(J)ことを通知することによりRLCよりも強力であることを検証することができます。

It is easy to see that F'(j) in the definition of RLC corresponds to the time the j-th departure should have occurred should the EF aggregate be constantly served exactly at its configured rate R. Following the common convention, we refer to F'(j) as the "fluid finish time" of the j-th packet to depart.

EFの集計が常に共通の慣習に従ってその設定されたレートR.で正確に提供しなければならないことは、j番目の出発が発生しているはずRLCの定義におけるF '(j)は、時間に対応することを確認するために簡単ですが、我々はを参照してください。出発するj番目のパケットの 『流体終了時刻』としてF '(J)。

The intuitive meaning of the rate-latency curve of RLC is that any packet is served at most time E later than this packet would finish service in the fluid model.


For RLC (and hence for the stronger EF definition) it holds that in any interval (0,t) the EF aggregate gets close to the desired service rate R (as long as there is enough traffic to sustain this rate). The discrepancy between the ideal and the actual service in this interval depends on the latency term E, which in turn depends on the scheduling implementation. The smaller E, the smaller the difference between the configured rate and the actual rate achieved by the scheduler.


While RLC guarantees the desired rate to the EF aggregate in all intervals (0,t) to within a specified error, it may nevertheless result in large gaps in service. For example, suppose that (a large number) N of identical EF packets of length L arrived from different interfaces to the EF queue in the absence of any non-EF traffic. Then any work-conserving scheduler will serve all N packets at link speed. When the last packet is sent at time NL/C, where C is the capacity of output link, F'(N) will be equal to NL/R. That is, the scheduler is running ahead of ideal, since NL/C < NL/R for R < C. Suppose now that at time NL/C a large number of non-EF packets arrive, followed by a single EF packet. Then the scheduler can legitimately delay starting to send the EF packet until time F'(N+1)=(N+1)L/R + E - L/C. This means that the EF aggregate will have no service at all in the interval (NL/C, (N+1)L/R + E - L/C). This interval can be quite large if R is substantially smaller than C. In essence, the EF aggregate can be "punished" by a gap in service for receiving faster service than its configured rate at the beginning.

RLCは、指定された誤差範囲内にすべての間隔(0、T)はEF集合体に所望の速度を保証しながら、それにもかかわらず、サービスに大きなギャップを生じ得ます。例えば、と仮定長さLの同一のEFパケットの(多数)Nは、任意の非EFトラフィックの不在下でEFキューに異なるインタフェースから到着しました。そして、いずれの作業保存スケジューラは、リンク速度で、すべてのN個のパケットにサービスを提供します。最後のパケットがCは、出力リンクの容量である時NL / C、で送信される場合、F '(N)は、NL / Rに等しくなります。すなわち、スケジューラが先理想の実行されて、R用のNL / C <NL / Rので<C.は時間NL / Cで今それを仮定し、非EFパケットの多数は、単一のEFパケットが続く、到着しています。 L / C - スケジューラは合法時間F '(N + 1)=(N + 1)L / R + EまでEFパケットを送信する起動遅延させることができます。これは、EF集合体が間隔( - L / C NL / C、(N + 1)L / R + E)に全くサービスを持たないであろうことを意味します。この間隔は、Rは、本質的にCよりも実質的に小さい場合、EF集合が初めにその設定されたレートよりも速いサービスを受信するためのサービスのギャップによって「罰する」ことができる非常に大きくすることができます。

The new EF definition alleviates this problem by introducing the term min(D(j-1), F(j-1)) in the recursion. Essentially, this means that the fluid finishing time is "reset" if that packet is sent before its "ideal" departure time. As a consequence of that, for the case where the EF aggregate is served in the FIFO order, suppose a packet arrives at time t to a server satisfying the EF definition. The 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 under discussion)[4].

新しいEF定義は再帰で(F(J-1)、D(J-1))という用語は、minを導入することによって、この問題を軽減します。基本的に、これは、そのパケットは、その「理想的」出発時刻前に送信された場合に流体終了時刻が「リセット」されることを意味します。その結果として、EFの集合体はFIFO順で提供しています場合のために、パケットがEFの定義を満たすサーバに時刻tに到着すると仮定します。パケットは、Q(t)は(議論下パケットを含む)は、時間tにおけるEFキューサイズである時刻t + Q(T)/ R + E、遅くとも送信されません[4]。

2.3. The need for dual characterization of EF PHB
2.3. EFのPHBのデュアル特徴づけのための必要性

In a more general case, where either the output scheduler does not serve the EF packets in a FIFO order, or the variable internal delay in the device reorders packets while delivering them to the output (or both), the i-th packet destined to a given output interface to arrive to the device may no longer be the i-th packet to depart from that interface. In that case the packet-identity-aware and the aggregate definitions are no longer identical.


The aggregate behavior definition can be viewed as a truly aggregate characteristic of the service provided to EF packets. For an analogy, consider a dark reservoir to which all arriving packets are placed. A scheduler is allowed to pick a packet from the reservoir in a random order, without any knowledge of the order of packet arrivals. The aggregate part of the definition measures the accuracy of the output rate provided to the EF aggregate as a whole. The smaller E_a, the more accurate is the assurance that the reservoir is drained at least at the configured rate.


Note that in this reservoir analogy packets of EF aggregate may be arbitrarily reordered. However, the definition of EF PHB given in [6] explicitly requires that no packet reordering occur within a microflow. This requirement restricts the scheduling implementations, or, in the reservoir analogy, the order of pulling packets out of the reservoir to make sure that packets within a microflow are not reordered, but it still allows reordering at the aggregate level.

このリザーバ内EF集合の類似パケットが任意に並べ替えてもよいことに留意されたいです。しかしながら、所与のEF PHBの定義は、[6]明示ないパケットの並べ替えは、マイクロフロー内で発生しないことを必要とします。この要件は、スケジューリングの実装を制限、または、リザーバー同様に、マイクロフロー内のパケットの順序が変更されていないことを確認するために、容器からのパケットを引き上げるため、それはまだ集計レベルで並べ替えができます。

Note that reordering within the aggregate, as long as there is no flow-level reordering, does not necessarily reflect a "bad" service. Consider for example a scheduler that arbitrates among 10 different EF "flows" with diverse rates. A scheduler that is aware of the rate requirements may choose to send a packet of the faster flow before a packet of the slower flow to maintain lower jitter at the flow level. In particular, an ideal "flow"-aware WFQ scheduler will cause reordering within the aggregate, while maintaining packet ordering and small jitter at the flow level.

限り何のフローレベルの並べ替えがないので、必然的に「悪い」のサービスを反映していない、集約内のその並べ替えに注意してください。例えば、多様な速度を持つ10種類のEF「流れ」の中で調停スケジューラを考えてみましょう。レート要件を認識しているスケジューラは、フローレベルでの低ジッタを維持するために、より遅い流れのパケットの前に速い流れのパケットを送信することもできます。具体的には、理想的な「流れ」-aware WFQスケジューラは、フローレベルでのパケットの順序や小さなジッタを維持しながら、集約内の並べ替えが発生します。

It is intuitively clear that for such a scheduler, as well as for a simpler FIFO scheduler, the "accuracy" of the service rate is crucial for minimizing "flow"-level jitter. The packet-identity-aware definition quantifies this accuracy of the service rate.


However, the small value of E_a does not give any assurances about the absolute value of per-packet delay. In fact, if the input rate exceeds the configured rate, the aggregate behavior definition may result in arbitrarily large delay of a subset of packets. This is the primary motivation for the packet-identity-aware definition.


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


While the aggregate behavior definition characterizes the accuracy of the service rate of the entire EF aggregate, the packet-identity-aware part of the definition characterizes the deviation of the device 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 therefore affected by two factors: the accuracy of the aggregate rate service and the degree of packet reordering within the EF aggregate (under the constraint that packets within the same microflow are not reordered). Therefore, a sub-aggregate aware device that provides an ideal service rate to the aggregate, and also provides an ideal rate service for each of the sub-aggregates, may nevertheless have a very large value of E_p (in this case E_p must be at least equal to the ratio of the maximum packet size divided by the smallest rate of any sub aggregate). As a result, a large value of E_p does not necessarily mean that the service provided to EF aggregate is bad - rather it may be an indication that the service is good, but non-FIFO. On the other hand, a large value of E_p may also mean that the aggregate service is very inaccurate (bursty), and hence in this case the large value of E_p reflects a poor quality of implementation.

パケット識別認識定義におけるE_pの値は、したがって、二つの要因によって影響される:集約レートサービスの精度と(同じマイクロフロー内のパケットを再順序付けされていない制約の下で)EF集合内のパケット並べ替えの度。したがって、凝集に理想的なサービスレートを提供し、また、サブ凝集体の各々のための理想的な速度のサービスを提供するサブ集計認識装置は、それにもかかわらずE_pの非常に大きな値を有していてもよい(この場合E_pはでなければなりません任意のサブ集合の最小速度で割った最大パケットサイズ)の比率に少なくとも等しいです。むしろサービスが良好であることを示すが、非FIFOとすることができる - その結果、E_pの大きな値は、必ずしもEF集合体に提供されるサービスが悪いことを意味するものではありません。一方、E_pの大きな値はまた、集約サービスは、非常に不正確な(バースト)であることを意味する、従ってこの場合にはE_pの大きな値は、実装の低品質を反映しています。

As a result, a large number of E_p does not necessarily provide any guidance on the quality of the EF implementation. However, a small value of E_p 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 to determine the quality of the implementation.


3. Per Packet delay

The primary motivation for the packet-identity-aware definition is that it allows quantification of the per-packet delay bound. This section discusses the issues with computing per-packet delay.


3.1. Single hop delay bound
3.1. バインドされたシングルホップ遅延

If the total traffic arriving to an output port I from all inputs is constrained by a leaky bucket with parameters (R, B), where 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)

D_P = B / R + E_p(eq_7)

(see appendix B).


Because the delay bound depends on the configured rate R and the input burstiness B, it is desirable for both of these parameters to be visible to a user of the device. A PDB desiring a particular delay bound may need to limit the range of configured rates and allowed burstiness that it can support in order to deliver such bound. Equation (eq_7) provides a means for determining an acceptable operating region for the device with a given E_p. It may also be useful to limit the total offered load to a given output to some rate R_1 < R (e.g. to obtain end-to-end delay bounds [5]). It

遅延限度が設定速度R及び入力バーストBに依存するため、これらのパラメータの両方は、デバイスのユーザに見えるようにするために、それが望ましいです。結合した特定の遅延を希望PDBが設定速度と、それは、このようなバウンドを提供するためにサポートすることができることを許容バーストの範囲を制限する必要があるかもしれません。式(eq_7)指定E_p有する装置のための許容可能な動作領域を決定するための手段を提供します。また、いくつかの速度R_1 <R(例えば、エンドツーエンド遅延限界を得た[5])に指定された出力に負荷を提供合計を制限するのに有用であり得ます。それ

is important to realize that, while R_1 may also be a configurable parameter of the device, the delay bound in (eq_7) does not depend on it. It may be possible to get better bounds explicitly using the bound on the input rate, but the bound (eq_7) does not take advantage of this information.


3.2. Multi-hop worst case delay
3.2. マルチホップ最悪の遅延

Although the PHB defines inherently local behavior, in this section we briefly discuss the issue of per-packet delay as the packet traverses several hops implementing EF PHB. Given a delay bound (eq_7) at a single hop, it is tempting to conclude that per-packet bound across h hops is simply h times the bound (eq_7). However, this is not necessarily the case, unless B represents the worst case input burstiness across all nodes in the network.

PHBは、本質的に地元の動作を定義しますが、パケットがEF PHBを実装するいくつかのホップを横断する際に、このセクションでは、我々は簡単に、パケットごとの遅延の問題を議論します。遅延限界所与(eq_7)単一ホップで、それは毎パケット時間を横切って結合することを締結したくれるホップ(eq_7)H回バウンド単純です。 Bは、ネットワーク内のすべてのノード間で最悪の場合の入力バーストを示していない限りしかし、これは、必ずしもそうではありません。

Unfortunately, obtaining such a worst case value of B is not trivial. If EF PHB is implemented using aggregate class-based scheduling where all EF packets share a single FIFO, the effect of jitter accumulation may result in an increase in burstiness from hop to hop. In particular, it can be shown that unless severe restrictions on EF utilization are imposed, even if all EF flows are ideally shaped at the ingress, then for any value of delay D it is possible to construct a network where EF utilization on any link is bounded not to exceed a given factor, no flow traverses more than a specified number of hops, but there exists a packet that experiences a delay more than D [5]. This result implies that the ability to limit the worst case burstiness and the resulting end-to-end delay across several hops may require not only limiting EF utilization on all links, but also constraining the global network topology. Such topology constraints would need to be specified in the definition of any PDB built on top of EF PHB, if such PDB requires a strict worst case delay bound.

残念ながら、Bのように最悪の場合の値を取得することは簡単ではありません。 EF PHBは、すべてのEFパケットが単一FIFOを共有する集約クラスベースのスケジューリングを使用して実装されている場合、ジッタ蓄積の効果は、ホップするホップからバースト性の増加をもたらすことができます。特に、EF利用に厳しい制限が課されていない限り、すべてのEFフローは、理想的には入口で成形されても、その後、遅延Dの任意の値に対して、任意のリンク上のEF利用があるネットワークを構築することが可能であることを示すことができます所定の係数を超えない境界、全く流れはホップの指定された数を超えて横断しないが、[5] Dよりも遅延を経験するパケットが存在します。この結果は、能力は、いくつかのホップを横断バースト性、そして得られたエンド・ツー・エンドの遅延はすべてのリンク上のEFの利用を制限するだけでなく、グローバルなネットワークトポロジを制約するだけでなく、必要になることがあり、最悪の場合を制限することを意味します。このようなトポロジーの制約は、PDBがバインドされ、厳格な最悪の場合の遅延を必要とする場合には、EF PHBの上に構築された任意のPDBの定義に指定する必要があります。

4. Packet loss

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

有限バッファを有する任意のデバイスは、入力されたバーストが十分に高くなった場合にパケットをドロップする必要があるかもしれません。 EFの低損失の目的を満たすために、ノードは、輻輳のEFの損失が発生しないれる運転領域によって特徴づけることができます。これは、損失なしに所定の出力インタフェースへのすべての入力から提供することができるレートr <= RとバーストサイズBのトークンバケットとして指定することができます。

However, as discussed in the previous section, the phenomenon of jitter accumulation makes it generally difficult to guarantee that the input burstiness never exceeds the specified operating region for nodes internal to the DiffServ domain. A no-loss guarantee across multiple hops may require specification of constraints on network topology which are outside the scope of inherently local definition of a PHB. Thus, it must be possible to establish whether a device conforms to the EF definition even when some packets are lost.


This can be done by performing an "off-line" test of conformance to equations (eq_1)- (eq_4). After observing a sequence of packets entering and leaving the node, the packets which did not leave are assumed lost and are notionally removed from the input stream. The remaining packets now constitute the arrival stream and the packets which left the node constitute the departure stream. Conformance to the equations can thus be verified by considering only those packets that successfully passed through the node.

これは、式への適合の「オフライン」テストを実行することによって行うことができる(eq_1) - (eq_4)。ノードに入って出るパケットのシーケンスを観察した後、残さなかったパケットが失われたと仮定され、概念的に入力ストリームから除去されます。残りのパケットは、現在到着ストリームを構成し、ノードを左パケットが出発ストリームを構成します。式への適合は、このように正常にノードを通過したパケットのみを考慮することによって確認することができます。

Note that specification of which packets are lost in the case when loss does occur is beyond the scope of the definition of EF PHB. However, those packets that were not lost must conform to the equations definition of EF PHB in section 2.1.

損失が発生したときにパケットが場合に失われたの仕様は、EF PHBの定義の範囲外であることに注意。しかし、失われていなかったこれらのパケットは、セクション2.1でEF PHBの方程式の定義に準拠する必要があります。

5. Implementation considerations

A packet passing through a router will experience delay for a number of reasons. Two familiar components of this delay are the time the packet spends in a buffer at an outgoing link waiting for the scheduler to select it and the time it takes to actually transmit the packet on the outgoing line.


There may be other components of a packet's delay through a router, however. A router might have to do some amount of header processing before the packet can be given to the correct output scheduler, for example. In another case a router may have a FIFO buffer (called a transmission queue in [7]) where the packet sits after being selected by the output scheduler but before it is transmitted. In cases such as these, the extra delay a packet may experience can be accounted for by absorbing it into the latency terms E_a and E_p.


Implementing EF on a router with a multi-stage switch fabric requires special attention. A packet may experience additional delays due to the fact that it must compete with other traffic for forwarding resources at multiple contention points in the switch core. The delay an EF packet may experience 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 require modification of their latency terms. The factors such as the speedup factor and the choice of crossbar arbitration algorithms may affect the latency terms substantially.


Delay in the switch core comes from two sources, both of which must be considered. The first part of this delay is the fixed delay a packet experiences regardless of the other traffic. This component of the delay includes the time it takes for things such as packet segmentation and reassembly in cell based cores, enqueueing and dequeuing at each stage, and transmission between stages. The second part of the switch core delay is variable and depends on the type and amount of other traffic traversing the core. This delay comes about if the stages in the core mix traffic flowing between different input/output port pairs. Thus, EF packets must compete against other traffic for forwarding resources in the core. Some of this competing traffic may even be traffic from other, non-EF aggregates. This introduces extra delay, that can also be absorbed by the latency term in the definition.


To capture these considerations, in this section we will consider two simplified implementation examples. The first is an ideal output buffered node where packets entering the device 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 will consider the case where the output scheduler implements aggregate class-based queuing, so that all EF packets share a single queue. We will discuss the values of E_a and E_p for a variety of class-based schedulers widely considered.


The second example will consider a router modeled as a black box with a known bound on the variable delay a packet can experience from the time it arrives to an input to the time it is delivered to its destination output. The output scheduler in isolation 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 provides a reasonable abstraction to a large class of router implementations.

第二の例では、パケットは、それが入力に到着した時から、それは、その先の出力に供給される時に体験することができ、可変遅延上の既知のバウンドとブラックボックスとしてモデル化ルータを検討します。単独で出力スケジューラは、すべてのEFパケットがE_A(S)= E_p(S)= E(S)の既知の値を用いて、単一のFIFOキューを共有集約スケジューラであると仮定されます。このモデルは、ルータの実装の大きなクラスに合理的な抽象化を提供します。

5.1. The output buffered model with EF FIFO at the output.
5.1. 出力でのEF FIFOと出力バッファリングモデル。

As has been mentioned earlier, in this model E_a = E_p, so we shall omit the subscript and refer to both terms as latency E. The remainder of this subsection discusses E for a number of scheduling implementations.

このモデルE_A = E_pに、前述したように、私たちは添え字を省略してレイテンシE.として両方の用語を指すものとする。このサブセクションの残りの部分は、スケジューリングの実装数のEを論じています。

5.1.1. Strict Non-preemptive Priority Queue
5.1.1. 厳密ノンプリエンプティブ優先度キュー

A Strict Priority scheduler in which all EF packets share a single FIFO queue which 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.

すべてのEFパケットが他のキュー上に厳密ノンプリエンプティブ優先で提供される単一のFIFOキューを共有する完全優先スケジューラは、MTUは、最大パケットサイズである待ち時間用語E = MTU / CとEFの定義を満たし、Cであります出力リンクの速度。

5.1.2. WF2Q
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, in which all EF traffic shares a single queue with the weight corresponding to the configured rate of the EF aggregate satisfies the EF definition with the latency term E = MTU/C+MTU/R.

小さなレイテンシ用語とEFの定義を満たす別のスケジューラはWF2Q [1]に記載されています。クラスベースWF2Qスケジューラ内のすべてのEFトラフィック共有EF凝集満足の構成率レイテンシ用語E = MTU / C + MTU / RとEFの定義に相当する量の単一のキュー。

5.1.3. Deficit Round Robin (DRR)
5.1.3. 赤字ラウンドロビン(DRR)

For DRR [12], E can be shown to grow linearly with N*(r_max/r_min)*MTU, where r_min and r_max denote 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.

DRR [12]のために、Eは、N *(R_MAX / r_min)* MTU、r_minとともに直線的に成長すると、スケジューラ内のすべてのキューのレートの割り当てのうち最小および最大レートを示しR_MAX示すことができ、Nはスケジューラのキューの数。

5.1.4. Start-Time Fair Queuing and Self-Clocked Fair Queuing
5.1.4. 開始時刻フェアキューイングおよびセルフクロックフェアキューイングを

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.

スタートタイム・フェア・キューイング(SFQ)[9]とセルフクロックフェアキューイング(SCFQ)[8] Eは、スケジューラのキューの数に比例し成長を示すことができます。

5.2. Router with Internal Delay and EF FIFO at the output
5.2. 出力での内部遅延およびEF FIFO付きルーター

In this section we consider a router which is modeled as follows. A packet entering the router may experience a variable delay D_v with a known upper bound D. That is, 0<=D_v<=D. At the output all EF packets share a single class queue. Class queues are 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).

このセクションでは、次のようにモデル化されたルータを考えます。ルータに入るパケットは、0 <= D_v <= Dで知ら上限D.可変遅延D_vを経験し得ます。出力では、すべてのEFパケットは、単一のクラスキューを共有しています。クラスキューは(E(S)は、このスケジューラは、理想的な出力緩衝装置に実装されているモデルに対応する)既知の値E_p(S)= E(S)とスケジューラによってスケジュールされます。

The computation of E_p is more complicated in this case. For such device, it can be shown that E_p = E(S)+2D+2B/R (see [13]).

E_pの計算は、この場合は、より複雑です。このような装置のために、E_p = E(S)+ 2D + 2B / Rは、([13]参照)ことを示すことができます。

Recall from the discussion of section 3 that bounding input burstiness B may not be easy in a general topology. In the absence of the knowledge of a bound on B one can bound E_p as E_p = E(S) + D*C_inp/R (see [13]).

セクション3の議論からリコールは、入力されたバーストBの境界は一般的なトポロジーが容易ではないかもしれないこと。 B上の結合についての知識の欠如の一方はE_p = E(S)+ D * C_inp / R([13]参照)としてE_pを結合することができます。

Note also 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 the architecture of a device are available, it may be possible to compute better bounds.


6. Security Considerations

This informational document provides additional information to aid in understanding of the EF PHB described in [6]. It adds no new functions to it. As a result, it adds no security issues to those described in that specification.

この情報は、ドキュメントに記載EF PHBの理解を助けるために追加情報を提供する[6]。それはそれに全く新しい機能が追加されていません。その結果、その仕様書に記載されたものにはセキュリティ上の問題を追加しません。

7. References

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

[1] J.C.R.ベネットとH.チャン、「WF2Q:ワーストケースフェア均等化キューイング」、INFOCOM'96、1996年3月。

[2] J.-Y. Le Boudec, P. Thiran, "Network Calculus", Springer Verlag Lecture Notes in Computer Science volume 2050, June 2001 (available online at

[2] J.-Y.ルBoudec、P. Thiran、「ネットワーク微積分」、シュプリンガーフェアラーク講義ノートコンピュータサイエンスのボリューム2050年、2001年6月(http://lcawww.epfl.chからオンラインで入手できます)。

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

[3]ブラドナーのは、S.は、BCP 14、RFC 2119、1997年3月の "RFCsにおける使用のためのレベルを示すために"。

[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.

[4] J.C.R.ベネット、K.ベンソン、A. Charny、W.コートニー、J.Y.ルBoudec、「遅延ジッタ境界および緊急転送のためのパケットスケールレートギャランティ」、PROC。インフォコム2001年、2001年4月。

[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.

[5] A. Charny、J.-Y.ルBoudec「集計のスケジュールとネットワークの遅延境界」。 PROC。 QoFIS'2000、9月25-26日、2000年、ベルリン、ドイツの。

[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.

[6]デイビー、B.、Charny、A.、ベイカー、F.、ベネット、JCR、ベンソン、K.、Boudec、J.、チウ、A.、コートニー、W.、Davari、S.、Firoiu、V 。、Kalmanek、C.、ラマクリシュナン、KKそして、D. Stiliadis、 "緊急転送PHB(ホップ単位動作)"、RFC 3246、2002年3月。

[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.

[7] T.フェラーリとP. F. Chimento、サービス、ピッツバーグ、PA、2000年6月の品質上の第八回国際ワークショップ「緊急転送PHBメカニズム、測定ベースの分析」。

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

[8] S.J.ゴールスタニ。 「広帯域アプリケーション用のセルフクロックフェアキューイングスキーム」。 IEEE INFOCOM'94、ページ636から646、トロント、CA、1994年4月の議事録。

[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.

[9] P. Goyal氏、H.M.ヴィン、およびH.チェン。 「スタート・タイム・フェア・キューイング:統合サービスのためのスケジューリングアルゴリズム」。 ACM-SIGCOMM 96、ページ157-168、パロアルト、CA、1996年8月の議事録。

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

[10]ジェーコブソン、V.、ニコルズ、K.及びK. Poduri、 "緊急転送PHB"、RFC 2598、1999年6月。

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

[11]ジェーコブソン、V.、ニコルズ、K.とK. Poduri、 "「仮想ワイヤの行動の集約" が進行中で働いています。

[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.

[12] M. Shreedhar及びG. Varghese。 「赤字ラウンドロビンを使用して効率的なフェア・キューイング」。 SIGCOMM'95の議事録、ページで231-243、ボストン、MA、1995年9月。

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

[13]ルBoudec、J.-Y.、Charny、A. "非FIFOノードのパケットスケールレートギャランティ"、インフォコム2002年、ニューヨーク、2002年6月。

Appendix A. Difficulties with the EF PHB Definition

EF PHBの定義との付録A.の難しさ

The definition of the EF PHB as given in [10] states:

EF PHBの定義は、[10]の状態で与えられます。

"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."

「EF PHBは、任意のDiffServノードから集約のパケットの出発速度が設定速度に等しいかまたは超えなければならない特定のdiffserv集合の転送処理として定義される。EFトラフィックが他のトラフィックの強度の独立このレートを受信しますそれが設定されたレートで出力リンクMTUサイズのパケットを送信するのに要する時間以上の間隔任意の時間をかけて測定した場合に遷移するノードを試みる。これ[EF PHB逸脱レート]は、少なくとも設定されたレートを平均すべきです。」

A literal interpretation of the definition would consider the behaviors given in the next two subsections as non-compliant. The definition also unnecessarily constrains the maximum configurable rate of an EF aggregate.


A.1 Perfectly-Clocked Forwarding


Consider the following stream forwarded from a router with EF-configured rate R=C/2, where C is the output line rate. In the illustration, E is an MTU-sized EF packet while x is a non-EF packet or unused capacity, also of size MTU.

Cが出力ラインレートであるEF-構成率R = C / 2とルータから転送次ストリームを考えます。 Xはまた、サイズMTUの、非EFパケットまたは未使用容量であるが図では、Eは、MTUサイズのEFパケットです。

      E x E x E x E x E x E x...

The interval between the vertical bars is 3*MTU/C, which is greater than MTU/(C/2), and so is subject to the EF PHB definition. During this interval, 3*MTU/2 bits of the EF aggregate should be forwarded, but only MTU bits are forwarded. Therefore, while this forwarding pattern should be considered compliant under any reasonable interpretation of the EF PHB, it actually does not formally comply with the definition of RFC 2598.

縦線の間隔は、MTU /(C / 2)よりも大きく、したがってEFのPHBの定義の対象となる3 * MTU / Cです。この間、EF集合体の3 * MTU / 2ビットが転送されるべきであるが、唯一のMTUビットが転送されます。この転送パターンはEF PHBのいずれかの合理的な解釈の下に準拠したとみなされるべきつつ、それが実際に正式に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 appears to warrant some changes to the definition that would correct this problem.


The underlying reason for the problem described here is quite simple - one can only expect that the EF aggregate is served at 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 exactly at the rate at which they are served, and so there is no persistent backlog. Certainly, if the input rate is even smaller than the configured rate of the EF aggregate, there will be no backlog as well, and a similar formal difficulty will occur.

ここで説明する問題の根本的な理由は非常に簡単です - 1は、EFの集計がそのレートを維持するためにEFパケットの十分なバックログがあり、いくつかの区間に設定されたレートで提供されていることだけを期待することができます。パケット上の例では、彼らが提供される速度で正確で来て、その永続的なバックログがありません。入力レートがEF集合体の構成割合よりも小さい場合には確かに、そこにもないバックログないであろう、と同様の形式的な困難が生じます。

A seemingly simple solution to this difficulty 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 remainder of this section, this solution does not suffice.


A.2 Router Internal Delay


We now argue that the example considered in the previous section is not as trivial as it may seem at first glance.


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

前の例のように構成されたEF率R = C / 2とルータを検討するが、3Tの内部遅延とパケットがルータに到着する時間との時間差(T = MTU / Cである)それが最初のものであること出力リンクに転送するための資格。ヘッダ処理、ルートルックアップ、および多層ファブリックを介してスイッチングにおける遅延は、この遅延を引き起こす可能性があるようなもの。今、EFトラフィックが(2/3)R = C / 3の割合で定期的に到着すると仮定します。以下に示すようにルータが実行されます。

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

EFパケット番号1 2 3 4 5 6 ...

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

(ルータで)到着0 3T、6T、9T 12T 15T ...

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

(スケジューラで)到着3T、6T、9T 12T 15T 18T ...

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

出発4T 7T 13T 16T 19T 10トン...

Again, the output does not satisfy the RFC 2598 definition of EF PHB. As in the previous example, the underlying reason for this problem is that the scheduler cannot forward EF traffic faster than it arrives. However, it can be easily seen that the existence of internal delay causes one packet to be inside the router at all times. An external observer will rightfully conclude that the number of EF packets that arrived to the router is always at least one greater than the number of EF packets that left the router, and therefore the EF aggregate is constantly backlogged. However, while the EF aggregate is continuously backlogged, the observed output rate is nevertheless strictly less that the configured rate.

ここでも、出力はEF PHBのRFC 2598の定義を満たしていません。前の例と同様に、この問題の根本的な理由は、スケジューラは、より速く、それが到着するよりも、EFトラフィックを転送することができないということです。しかし、簡単に内部遅延の存在は、すべての回でルータの内側にあることを一つのパケットが発生していることが分かります。外部の観察者は合法的にルータに到着したEFパケットの数は、常にルータを残し、したがって、EFの集計が常にバックログであるEFパケットの数よりも少なくとも1大きいと結論します。 EF集合が連続バックログであるがしかし、観察された出力レートにもかかわらず、構成割合その厳密に小さいです。

This example indicates that the simple addition of the condition that EF aggregate must receive its configured rate only when the EF aggregate is backlogged does not suffice in this case.


Yet, the problem described here is of fundamental importance in practice. Most routers have a certain amount of internal delay. A vendor declaring EF compliance is not expected to simultaneously declare the details of the internals of the router. Therefore, the existence of internal delay may cause a perfectly reasonable EF implementation to display seemingly non-conformant behavior, which is clearly undesirable.

しかし、ここで説明する問題は、実際には基本的に重要です。ほとんどのルータは、内部遅延の一定量を持っています。 EFコンプライアンスを宣言するベンダーは、同時にルータの内部の詳細を宣言することが期待されていません。したがって、内部遅延の存在は完全に合理的EFの実装は明らかに望ましくない一見非準拠の動作を、表示されることがあります。

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 configured rate R > C/2, then this interval would be of length greater than MTU/R, and more than MTU EF bits would have to be served during this interval for the router to be compliant. Thus, R must be no greater than C/2.

よく、任意の非プリエンプティブスケジューラと、EF集合体のためのRFC-2598準拠の設定速度を超えてはならないことが理解されるC / 2 [11]。 MTUサイズのEFパケットがMTUサイズの非EFパケットがサービスを開始しますと同じように、時刻tで空のキューに到着する可能性があるためです。インターバル中に転送することができたEFビットの最大数[T、T + 2 * MTU / C]はMTUです。設定されたレートR> C / 2の場合には、この間隔は長さのMTU / Rよりも大きく、及びMTU EFビットが準拠するルータは、この間隔の間に配信されなければならないよりもあろう。したがって、Rは、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, mentioned as compliant in section 2.2 of RFC 2598, this limitation is even more severe. This is because 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 will finally be forwarded.

そのようなWFQの様々な実装としてPQ以外のスケジューラのために、最大対応構成率が50%よりもはるかに小さくてもよいことを示すことができます。例えば、SCFQ [8]最大設定されたレートは、Nは、スケジューラのキューの数であり、C / Nを超えることはできません。 RFC 2598のセクション2.2に準拠するように言及さWRR、のために、この制限はさらに深刻です。これらのスケジューラに空のEFキューに到着したパケットは、(WRRの場合)(SCFQの場合)または各他のキューからの複数のパケットまで、それぞれ他のキューから1つのパケットまで待つことを余儀なくされる可能性があるためで提供していますです前にそれが最終的に転送されます。

While it is frequently assumed that the configured rate of EF traffic will be substantially smaller than the link bandwidth, the requirement that this rate should never exceed 50% of the link bandwidth appears unnecessarily limiting. For example, in a fully connected mesh network, where any flow traverses a single link on its way from source to its destination there seems no compelling reason to limit the amount of EF traffic to 50% (or an even smaller percentage for some schedulers) of the link bandwidth.


Another, perhaps even more striking example is the fact 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

別の、おそらくより多くの顕著な例は、専用スロットにもTDM回路は、RFC 2598に違反することなく、リンク速度の50%以上でEFパケットを転送するように構成することができないという事実であります

(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 exist 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

(全体のリンクがEFのために構成されていない限り)。 EFトラフィックの構成比率が50%を超える(しかし、リンク速度未満)であれば、常に設定されたレート未満が達成されるMTU / Rよりも長い間隔が存在します。例えば、EF集合体の構成割合は、2C / 3であると仮定する。そして、TDM回路の転送パターンがあるかもしれません

   E E x E E x E E x ...

where 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 cannot be booked over 50% by EF traffic indicates that the restriction is artificial and unnecessary.

唯一の1つのパケットが長さ2T = 2MTU / Cのマークされた間隔で提供している場合。しかし、少なくとも4/3 MTUはRFC 2598で定義に準拠したルータによって、この期間中に提供されなければならないとしてもTDMラインは、EFトラフィックによって50%以上予約することができないという事実は、制限が人工的であることを示し、不要。

A.4 The Non-trivial Nature of the Difficulties


One possibility to correct the problems discussed in the previous sections might be to attempt to clarify the definition of the intervals to which the definition applied or by averaging over multiple intervals. However, an attempt to do so meets with considerable analytical and implementation difficulties. For example, attempting to align interval start times with some epochs of the forwarded stream appears to require a certain degree of global clock synchronization and is fraught with the risk of misinterpretation and mistake in practice.


Another approach might be to allow averaging of the rates over some larger time scale. However, it is unclear exactly what finite time scale would suffice in all reasonable cases. Furthermore, this approach would compromise the notion of very short-term time scale guarantees that are the essence of EF PHB.

別のアプローチは、いくつかの大きな時間スケールにわたる率の平均化を可能にしている可能性があります。しかし、有限の時間スケールは、すべての合理的な例で十分であろう、まさに不明です。さらに、このアプローチは、EF PHBのエッセンスです非常に短期的な時間スケールの保証の概念を危うくします。

We also explored a combination of two simple fixes. The first is the addition of the condition that the only intervals subject to the definition are those that fall inside a period during which the EF aggregate is continuously backlogged in the router (i.e., when an EF packet is in the router). The second is the addition of an error (latency) term that could serve as a figure-of-merit in the advertising of EF services.


With the addition of these two changes the candidate definition becomes as follows:


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.

EFトラフィックが連続的にバックログされた時間の任意の期間(T1、T2)において、少なくともR(T2 - T1 - E)Rは、EF集合体のために設定されたレートであり、EがどこにあるEFトラフィックのビットは、配信されなければなりません実装固有の待ち時間の用語。

The "continuously backlogged" condition eliminates the insufficient-packets-to-forward difficulty while the addition of the latency term of size MTU/C resolves the perfectly-clocked forwarding example (section A.1), and also removes the limitation on EF configured rate.

サイズMTU / Cの待ち時間用語の添加は完全に、クロックド転送の例(セクションA.1)を解決し、また構成EF上の制限を除去しながら、「連続未処理」状態が不十分・パケット・ツー・フォワード困難を排除します割合。

However, neither fix (nor the two of them together) resolves the example of section A.2. To see this, recall that in the example of section A.2 the EF aggregate is continuously backlogged, but the service rate of the EF aggregate is consistently smaller than the configured rate, and therefore no finite latency term will suffice 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]. These proofs use an algebraic characterization of the aggregate definition given by (eq_1), (eq_2), and packet identity aware definition given by (eq_3), (eq_4). Since this characterization is of interest on its own, we present it in this section.


Theorem B1. Characterization of the aggregate definition without f_n.

定理B1。 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:

パケットは、1、2の番号が付けられてい...到着のためにシステムを考えてみましょう。 n番目の出発時刻、および出発するn番目のパケットのサイズをl_n - 集計定義のように、d_n、n番目の到着時間A_N呼び出します。コンベンションD_0 = 0で定義します。レートR及び待ち時間E_A有する集約定義は、全てのn及び全て0 <= jの<= N-1のためと言うのと等価です。

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

d_n <= E_A + d_j +(L_(J + 1)+ ... + l_n)/ R(eq_b1)



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

いくつかのJ + 1 <= K <= Nとなるように存在します

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

d_n <= E_A + a_k +(L_K + ... + l_n)/ R(eq_b2)

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

定理B2。 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:

パケットは、1、2の番号が付けられてい...到着のためにシステムを考えてみましょう。パケットのアイデンティティを意識した定義のように、このパケットのサイズA_N、D_n n番目のパケットの到着と出発時刻、およびL_nを呼び出します。大会D_0 = 0で定義します。レートRとレイテンシE_pのパケットアイデンティティを意識定義は、すべてのnのためにそれを言うと同等であり、すべての0 <= J <= N-1:

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

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



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

いくつかのJ + 1 <= K <= Nとなるように存在します

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

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

For the proofs of both Theorems, see [13].




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

アンナCharnyシスコシステムズ300アポロドライブチェルムズフォード、MA 01824



Jon Bennett Motorola 3 Highwood Drive East Tewksbury, MA 01876

ジョン・ベネットモトローラ3ハイウッドドライブ東テュークスベリー、MA 01876



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




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

ジャン=イヴ・ルICA-EPFL Boudec、INN Ecublens、CH-1015ローザンヌ、ローザンヌ連邦工科大学、スイス



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

アンジェラ・チウCelionネットワーク1シーラ・ドライブ、スイート2ティントンフォールズ、NJ 07724



Bill Courtney TRW Bldg. 201/3702 One Space Park Redondo Beach, CA 90278

ビル・コートニーTRWビル。 201/3702一つのスペースパークレドンドビーチ、CA 90278



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

K2K 3C9、カナダON Shahram Davari PMC-Sierraの社411 Leggetドライブオタワ、



Victor Firoiu Nortel Networks 600 Tech Park Billerica, MA 01821

ビクターFiroiu Nortel Networksの600ハイテクパークビレリカ、MA 01821



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

チャールズKalmanek AT&T Labsのリサーチ180パークアベニュー、ルームA113、フローハムパークNJ



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

K.K.ラマクリシュナンTeraOpticネットワークス株式会社686 W.モーデスアベニューサニーベール、CA 94086



Full Copyright Statement


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


This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of 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 limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.






Funding for the RFC Editor function is currently provided by the Internet Society.

RFC Editor機能のための基金は現在、インターネット協会によって提供されます。