diff options
Diffstat (limited to 'doc/rfc/rfc2212.txt')
| -rw-r--r-- | doc/rfc/rfc2212.txt | 1123 |
1 files changed, 1123 insertions, 0 deletions
diff --git a/doc/rfc/rfc2212.txt b/doc/rfc/rfc2212.txt new file mode 100644 index 0000000..4207fcc --- /dev/null +++ b/doc/rfc/rfc2212.txt @@ -0,0 +1,1123 @@ + + + + + + +Network Working Group S. Shenker +Request for Comments: 2212 Xerox +Category: Standards Track C. Partridge + BBN + R. Guerin + IBM + September 1997 + + + Specification of Guaranteed Quality of Service + + +Status of this Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + +Abstract + + This memo describes the network element behavior required to deliver + a guaranteed service (guaranteed delay and bandwidth) in the + Internet. Guaranteed service provides firm (mathematically provable) + bounds on end-to-end datagram queueing delays. This service makes it + possible to provide a service that guarantees both delay and + bandwidth. This specification follows the service specification + template described in [1]. + +Introduction + + This document defines the requirements for network elements that + support guaranteed service. This memo is one of a series of + documents that specify the network element behavior required to + support various qualities of service in IP internetworks. Services + described in these documents are useful both in the global Internet + and private IP networks. + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this + document are to be interpreted as described in RFC 2119. + + This document is based on the service specification template given in + [1]. Please refer to that document for definitions and additional + information about the specification of qualities of service within + the IP protocol family. + + + + +Shenker, et. al. Standards Track [Page 1] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + In brief, the concept behind this memo is that a flow is described + using a token bucket and given this description of a flow, a service + element (a router, a subnet, etc) computes various parameters + describing how the service element will handle the flow's data. By + combining the parameters from the various service elements in a path, + it is possible to compute the maximum delay a piece of data will + experience when transmitted via that path. + + It is important to note three characteristics of this memo and the + service it specifies: + + 1. While the requirements a setup mechanism must follow to achieve + a guaranteed reservation are carefully specified, neither the + setup mechanism itself nor the method for identifying flows is + specified. One can create a guaranteed reservation using a + protocol like RSVP, manual configuration of relevant routers or a + network management protocol like SNMP. This specification is + intentionally independent of setup mechanism. + + 2. To achieve a bounded delay requires that every service element + in the path supports guaranteed service or adequately mimics + guaranteed service. However this requirement does not imply that + guaranteed service must be deployed throughout the Internet to be + useful. Guaranteed service can have clear benefits even when + partially deployed. If fully deployed in an intranet, that + intranet can support guaranteed service internally. And an ISP + can put guaranteed service in its backbone and provide guaranteed + service between customers (or between POPs). + + 3. Because service elements produce a delay bound as a result + rather than take a delay bound as an input to be achieved, it is + sometimes assumed that applications cannot control the delay. In + reality, guaranteed service gives applications considerable + control over their delay. + + In brief, delay has two parts: a fixed delay (transmission delays, + etc) and a queueing delay. The fixed delay is a property of the + chosen path, which is determined not by guaranteed service but by + the setup mechanism. Only queueing delay is determined by + guaranteed service. And (as the equations later in this memo + show) the queueing delay is primarily a function of two + parameters: the token bucket (in particular, the bucket size b) + + + + + + + + + +Shenker, et. al. Standards Track [Page 2] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + and the data rate (R) the application requests. These two values + are completely under the application's control. In other words, + an application can usually accurately estimate, a priori, what + queueing delay guaranteed service will likely promise. + Furthermore, if the delay is larger than expected, the application + can modify its token bucket and data rate in predictable ways to + achieve a lower delay. + +End-to-End Behavior + + The end-to-end behavior provided by a series of network elements that + conform to this document is an assured level of bandwidth that, when + used by a policed flow, produces a delay-bounded service with no + queueing loss for all conforming datagrams (assuming no failure of + network components or changes in routing during the life of the + flow). + + The end-to-end behavior conforms to the fluid model (described under + Network Element Data Handling below) in that the delivered queueing + delays do not exceed the fluid delays by more than the specified + error bounds. More precisely, the end-to-end delay bound is [(b- + M)/R*(p-R)/(p-r)]+(M+Ctot)/R+Dtot for p>R>=r, and (M+Ctot)/R+Dtot for + r<=p<=R, (where b, r, p, M, R, Ctot, and Dtot are defined later in + this document). + + NOTE: While the per-hop error terms needed to compute the end-to- + end delays are exported by the service module (see Exported + Information below), the mechanisms needed to collect per-hop + bounds and make the end-to-end quantities Ctot and Dtot known to + the applications are not described in this specification. These + functions are provided by reservation setup protocols, routing + protocols or other network management functions and are outside + the scope of this document. + + The maximum end-to-end queueing delay (as characterized by Ctot and + Dtot) and bandwidth (characterized by R) provided along a path will + be stable. That is, they will not change as long as the end-to-end + path does not change. + + Guaranteed service does not control the minimal or average delay of + datagrams, merely the maximal queueing delay. Furthermore, to + compute the maximum delay a datagram will experience, the latency of + the path MUST be determined and added to the guaranteed queueing + delay. (However, as noted below, a conservative bound of the latency + can be computed by observing the delay experienced by any one + packet). + + This service is subject to admission control. + + + +Shenker, et. al. Standards Track [Page 3] + +RFC 2212 Guaranteed Quality of Service September 1997 + + +Motivation + + Guaranteed service guarantees that datagrams will arrive within the + guaranteed delivery time and will not be discarded due to queue + overflows, provided the flow's traffic stays within its specified + traffic parameters. This service is intended for applications which + need a firm guarantee that a datagram will arrive no later than a + certain time after it was transmitted by its source. For example, + some audio and video "play-back" applications are intolerant of any + datagram arriving after their play-back time. Applications that have + hard real-time requirements will also require guaranteed service. + + This service does not attempt to minimize the jitter (the difference + between the minimal and maximal datagram delays); it merely controls + the maximal queueing delay. Because the guaranteed delay bound is a + firm one, the delay has to be set large enough to cover extremely + rare cases of long queueing delays. Several studies have shown that + the actual delay for the vast majority of datagrams can be far lower + than the guaranteed delay. Therefore, authors of playback + applications should note that datagrams will often arrive far earlier + than the delivery deadline and will have to be buffered at the + receiving system until it is time for the application to process + them. + + This service represents one extreme end of delay control for + networks. Most other services providing delay control provide much + weaker assurances about the resulting delays. In order to provide + this high level of assurance, guaranteed service is typically only + useful if provided by every network element along the path (i.e. by + both routers and the links that interconnect the routers). Moreover, + as described in the Exported Information section, effective provision + and use of the service requires that the set-up protocol or other + mechanism used to request service provides service characterizations + to intermediate routers and to the endpoints. + +Network Element Data Handling Requirements + + The network element MUST ensure that the service approximates the + "fluid model" of service. The fluid model at service rate R is + essentially the service that would be provided by a dedicated wire of + bandwidth R between the source and receiver. Thus, in the fluid + model of service at a fixed rate R, the flow's service is completely + independent of that of any other flow. + + + + + + + + +Shenker, et. al. Standards Track [Page 4] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + The flow's level of service is characterized at each network element + by a bandwidth (or service rate) R and a buffer size B. R represents + the share of the link's bandwidth the flow is entitled to and B + represents the buffer space in the network element that the flow may + consume. The network element MUST ensure that its service matches + the fluid model at that same rate to within a sharp error bound. + + The definition of guaranteed service relies on the result that the + fluid delay of a flow obeying a token bucket (r,b) and being served + by a line with bandwidth R is bounded by b/R as long as R is no less + than r. Guaranteed service with a service rate R, where now R is a + share of bandwidth rather than the bandwidth of a dedicated line, + approximates this behavior. + + Consequently, the network element MUST ensure that the queueing delay + of any datagram be less than b/R+C/R+D, where C and D describe the + maximal local deviation away from the fluid model. It is important + to emphasize that C and D are maximums. So, for instance, if an + implementation has occasional gaps in service (perhaps due to + processing routing updates), D needs to be large enough to account + for the time a datagram may lose during the gap in service. (C and D + are described in more detail in the section on Exported Information). + + NOTE: Strictly speaking, this memo requires only that the service + a flow receives is never worse than it would receive under this + approximation of the fluid model. It is perfectly acceptable to + give better service. For instance, if a flow is currently not + using its share, R, algorithms such as Weighted Fair Queueing that + temporarily give other flows the unused bandwidth, are perfectly + acceptable (indeed, are encouraged). + + Links are not permitted to fragment datagrams as part of guaranteed + service. Datagrams larger than the MTU of the link MUST be policed + as nonconformant which means that they will be policed according to + the rules described in the Policing section below. + +Invocation Information + + Guaranteed service is invoked by specifying the traffic (TSpec) and + the desired service (RSpec) to the network element. A service + request for an existing flow that has a new TSpec and/or RSpec SHOULD + be treated as a new invocation, in the sense that admission control + SHOULD be reapplied to the flow. Flows that reduce their TSpec + and/or their RSpec (i.e., their new TSpec/RSpec is strictly smaller + than the old TSpec/RSpec according to the ordering rules described in + the section on Ordering below) SHOULD never be denied service. + + + + + +Shenker, et. al. Standards Track [Page 5] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + The TSpec takes the form of a token bucket plus a peak rate (p), a + minimum policed unit (m), and a maximum datagram size (M). + + The token bucket has a bucket depth, b, and a bucket rate, r. Both b + and r MUST be positive. The rate, r, is measured in bytes of IP + datagrams per second, and can range from 1 byte per second to as + large as 40 terabytes per second (or close to what is believed to be + the maximum theoretical bandwidth of a single strand of fiber). + Clearly, particularly for large bandwidths, only the first few digits + are significant and so the use of floating point representations, + accurate to at least 0.1% is encouraged. + + The bucket depth, b, is also measured in bytes and can range from 1 + byte to 250 gigabytes. Again, floating point representations + accurate to at least 0.1% are encouraged. + + The range of values is intentionally large to allow for the future + bandwidths. The range is not intended to imply that a network + element has to support the entire range. + + The peak rate, p, is measured in bytes of IP datagrams per second and + has the same range and suggested representation as the bucket rate. + The peak rate is the maximum rate at which the source and any + reshaping points (reshaping points are defined below) may inject + bursts of traffic into the network. More precisely, it is a + requirement that for all time periods the amount of data sent cannot + exceed M+pT where M is the maximum datagram size and T is the length + of the time period. Furthermore, p MUST be greater than or equal to + the token bucket rate, r. If the peak rate is unknown or + unspecified, then p MUST be set to infinity. + + The minimum policed unit, m, is an integer measured in bytes. All IP + datagrams less than size m will be counted, when policed and tested + for conformance to the TSpec, as being of size m. The maximum + datagram size, M, is the biggest datagram that will conform to the + traffic specification; it is also measured in bytes. The flow MUST + be rejected if the requested maximum datagram size is larger than the + MTU of the link. Both m and M MUST be positive, and m MUST be less + than or equal to M. + + The guaranteed service uses the general TOKEN_BUCKET_TSPEC + parameter defined in Reference [8] to describe a data flow's + traffic characteristics. The description above is of that + parameter. The TOKEN_BUCKET_TSPEC is general parameter number + 127. Use of this parameter for the guaranteed service TSpec + simplifies the use of guaranteed Service in a multi-service + environment. + + + + +Shenker, et. al. Standards Track [Page 6] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + The RSpec is a rate R and a slack term S, where R MUST be greater + than or equal to r and S MUST be nonnegative. The rate R is again + measured in bytes of IP datagrams per second and has the same range + and suggested representation as the bucket and the peak rates. The + slack term S is in microseconds. The RSpec rate can be bigger than + the TSpec rate because higher rates will reduce queueing delay. The + slack term signifies the difference between the desired delay and the + delay obtained by using a reservation level R. This slack term can + be utilized by the network element to reduce its resource reservation + for this flow. When a network element chooses to utilize some of the + slack in the RSpec, it MUST follow specific rules in updating the R + and S fields of the RSpec; these rules are specified in the Ordering + and Merging section. If at the time of service invocation no slack + is specified, the slack term, S, is set to zero. No buffer + specification is included in the RSpec because the network element is + expected to derive the required buffer space to ensure no queueing + loss from the token bucket and peak rate in the TSpec, the reserved + rate and slack in the RSpec, the exported information received at the + network element, i.e., Ctot and Dtot or Csum and Dsum, combined with + internal information about how the element manages its traffic. + + The TSpec can be represented by three floating point numbers in + single-precision IEEE floating point format followed by two 32-bit + integers in network byte order. The first floating point value is + the rate (r), the second floating point value is the bucket size (b), + the third floating point is the peak rate (p), the first integer is + the minimum policed unit (m), and the second integer is the maximum + datagram size (M). + + The RSpec rate term, R, can also be represented using single- + precision IEEE floating point. + + The Slack term, S, can be represented as a 32-bit integer. Its value + can range from 0 to (2**32)-1 microseconds. + + When r, b, p, and R terms are represented as IEEE floating point + values, the sign bit MUST be zero (all values MUST be non-negative). + Exponents less than 127 (i.e., 0) are prohibited. Exponents greater + than 162 (i.e., positive 35) are discouraged, except for specifying a + peak rate of infinity. Infinity is represented with an exponent of + all ones (255) and a sign bit and mantissa of all zeroes. + +Exported Information + + Each guaranteed service module MUST export at least the following + information. All of the parameters described below are + characterization parameters. + + + + +Shenker, et. al. Standards Track [Page 7] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + A network element's implementation of guaranteed service is + characterized by two error terms, C and D, which represent how the + element's implementation of the guaranteed service deviates from the + fluid model. These two parameters have an additive composition rule. + + The error term C is the rate-dependent error term. It represents the + delay a datagram in the flow might experience due to the rate + parameters of the flow. An example of such an error term is the need + to account for the time taken serializing a datagram broken up into + ATM cells, with the cells sent at a frequency of 1/r. + + NOTE: It is important to observe that when computing the delay + bound, parameter C is divided by the reservation rate R. This + division is done because, as with the example of serializing the + datagram, the effect of the C term is a function of the + transmission rate. Implementors should take care to confirm that + their C values, when divided by various rates, give appropriate + results. Delay values that are not dependent on the rate SHOULD + be incorporated into the value for the D parameter. + + The error term D is the rate-independent, per-element error term and + represents the worst case non-rate-based transit time variation + through the service element. It is generally determined or set at + boot or configuration time. An example of D is a slotted network, in + which guaranteed flows are assigned particular slots in a cycle of + slots. Some part of the per-flow delay may be determined by which + slots in the cycle are allocated to the flow. In this case, D would + measure the maximum amount of time a flow's data, once ready to be + sent, might have to wait for a slot. (Observe that this value can be + computed before slots are assigned and thus can be advertised. For + instance, imagine there are 100 slots. In the worst case, a flow + might get all of its N slots clustered together, such that if a + packet was made ready to send just after the cluster ended, the + packet might have to wait 100-N slot times before transmitting. In + this case one can easily approximate this delay by setting D to 100 + slot times). + + If the composition function is applied along the entire path to + compute the end-to-end sums of C and D (Ctot and Dtot) and the + resulting values are then provided to the end nodes (by presumably + the setup protocol), the end nodes can compute the maximal datagram + queueing delays. Moreover, if the partial sums (Csum and Dsum) from + the most recent reshaping point (reshaping points are defined below) + downstream towards receivers are handed to each network element then + these network elements can compute the buffer allocations necessary + + + + + + +Shenker, et. al. Standards Track [Page 8] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + to achieve no datagram loss, as detailed in the section Guidelines + for Implementors. The proper use and provision of this service + requires that the quantities Ctot and Dtot, and the quantities Csum + and Dsum be computed. Therefore, we assume that usage of guaranteed + service will be primarily in contexts where these quantities are made + available to end nodes and network elements. + + The error term C is measured in units of bytes. An individual + element can advertise a C value between 1 and 2**28 (a little over + 250 megabytes) and the total added over all elements can range as + high as (2**32)-1. Should the sum of the different elements delay + exceed (2**32)-1, the end-to-end error term MUST be set to (2**32)-1. + + The error term D is measured in units of one microsecond. An + individual element can advertise a delay value between 1 and 2**28 + (somewhat over two minutes) and the total delay added over all + elements can range as high as (2**32)-1. Should the sum of the + different elements delay exceed (2**32)-1, the end-to-end delay MUST + be set to (2**32)-1. + + The guaranteed service is service_name 2. + + The RSpec parameter is numbered 130. + + Error characterization parameters C and D are numbered 131 and 132. + The end-to-end composed values for C and D (Ctot and Dtot) are + numbered 133 and 134. The since-last-reshaping point composed values + for C and D (Csum and Dsum) are numbered 135 and 136. + +Policing + + There are two forms of policing in guaranteed service. One form is + simple policing (hereafter just called policing to be consistent with + other documents), in which arriving traffic is compared against a + TSpec. The other form is reshaping, where an attempt is made to + restore (possibly distorted) traffic's shape to conform to the TSpec, + and the fact that traffic is in violation of the TSpec is discovered + because the reshaping fails (the reshaping buffer overflows). + + Policing is done at the edge of the network. Reshaping is done at + all heterogeneous source branch points and at all source merge + points. A heterogeneous source branch point is a spot where the + multicast distribution tree from a source branches to multiple + distinct paths, and the TSpec's of the reservations on the various + outgoing links are not all the same. Reshaping need only be done if + the TSpec on the outgoing link is "less than" (in the sense described + in the Ordering section) the TSpec reserved on the immediately + upstream link. A source merge point is where the distribution paths + + + +Shenker, et. al. Standards Track [Page 9] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + or trees from two different sources (sharing the same reservation) + merge. It is the responsibility of the invoker of the service (a + setup protocol, local configuration tool, or similar mechanism) to + identify points where policing is required. Reshaping may be done at + other points as well as those described above. Policing MUST not be + done except at the edge of the network. + + The token bucket and peak rate parameters require that traffic MUST + obey the rule that over all time periods, the amount of data sent + cannot exceed M+min[pT, rT+b-M], where r and b are the token bucket + parameters, M is the maximum datagram size, and T is the length of + the time period (note that when p is infinite this reduces to the + standard token bucket requirement). For the purposes of this + accounting, links MUST count datagrams which are smaller than the + minimum policing unit to be of size m. Datagrams which arrive at an + element and cause a violation of the the M+min[pT, rT+b-M] bound are + considered non-conformant. + + At the edge of the network, traffic is policed to ensure it conforms + to the token bucket. Non-conforming datagrams SHOULD be treated as + best-effort datagrams. [If and when a marking ability becomes + available, these non-conformant datagrams SHOULD be ''marked'' as + being non-compliant and then treated as best effort datagrams at all + subsequent routers.] + + Best effort service is defined as the default service a network + element would give to a datagram that is not part of a flow and was + sent between the flow's source and destination. Among other + implications, this definition means that if a flow's datagram is + changed to a best effort datagram, all flow control (e.g., RED [2]) + that is normally applied to best effort datagrams is applied to that + datagram too. + + NOTE: There may be situations outside the scope of this document, + such as when a service module's implementation of guaranteed + service is being used to implement traffic sharing rather than a + quality of service, where the desired action is to discard non- + conforming datagrams. To allow for such uses, implementors SHOULD + ensure that the action to be taken for non-conforming datagrams is + configurable. + + Inside the network, policing does not produce the desired results, + because queueing effects will occasionally cause a flow's traffic + that entered the network as conformant to be no longer conformant at + some downstream network element. Therefore, inside the network, + network elements that wish to police traffic MUST do so by reshaping + traffic to the token bucket. Reshaping entails delaying datagrams + until they are within conformance of the TSpec. + + + +Shenker, et. al. Standards Track [Page 10] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + Reshaping is done by combining a buffer with a token bucket and peak + rate regulator and buffering data until it can be sent in conformance + with the token bucket and peak rate parameters. (The token bucket + regulator MUST start with its token bucket full of tokens). Under + guaranteed service, the amount of buffering required to reshape any + conforming traffic back to its original token bucket shape is + b+Csum+(Dsum*r), where Csum and Dsum are the sums of the parameters C + and D between the last reshaping point and the current reshaping + point. Note that the knowledge of the peak rate at the reshapers can + be used to reduce these buffer requirements (see the section on + "Guidelines for Implementors" below). A network element MUST provide + the necessary buffers to ensure that conforming traffic is not lost + at the reshaper. + + NOTE: Observe that a router that is not reshaping can still + identify non-conforming datagrams (and discard them or schedule + them at lower priority) by observing when queued traffic for the + flow exceeds b+Csum+(Dsum*r). + + If a datagram arrives to discover the reshaping buffer is full, then + the datagram is non-conforming. Observe this means that a reshaper + is effectively policing too. As with a policer, the reshaper SHOULD + relegate non-conforming datagrams to best effort. [If marking is + available, the non-conforming datagrams SHOULD be marked] + + NOTE: As with policers, it SHOULD be possible to configure how + reshapers handle non-conforming datagrams. + + Note that while the large buffer makes it appear that reshapers add + considerable delay, this is not the case. Given a valid TSpec that + accurately describes the traffic, reshaping will cause little extra + actual delay at the reshaping point (and will not affect the delay + bound at all). Furthermore, in the normal case, reshaping will not + cause the loss of any data. + + However, (typically at merge or branch points), it may happen that + the TSpec is smaller than the actual traffic. If this happens, + reshaping will cause a large queue to develop at the reshaping point, + which both causes substantial additional delays and forces some + datagrams to be treated as non-conforming. This scenario makes an + unpleasant denial of service attack possible, in which a receiver who + is successfully receiving a flow's traffic via best effort service is + pre-empted by a new receiver who requests a reservation for the flow, + but with an inadequate TSpec and RSpec. The flow's traffic will now + be policed and possibly reshaped. If the policing function was + chosen to discard datagrams, the best-effort receiver would stop + receiving traffic. For this reason, in the normal case, policers are + simply to treat non-conforming datagrams as best effort (and marking + + + +Shenker, et. al. Standards Track [Page 11] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + them if marking is implemented). While this protects against denial + of service, it is still true that the bad TSpec may cause queueing + delays to increase. + + NOTE: To minimize problems of reordering datagrams, reshaping + points may wish to forward a best-effort datagram from the front + of the reshaping queue when a new datagram arrives and the + reshaping buffer is full. + + Readers should also observe that reclassifying datagrams as best + effort (as opposed to dropping the datagrams) also makes support + for elastic flows easier. They can reserve a modest token bucket + and when their traffic exceeds the token bucket, the excess + traffic will be sent best effort. + + A related issue is that at all network elements, datagrams bigger + than the MTU of the network element MUST be considered non-conformant + and SHOULD be classified as best effort (and will then either be + fragmented or dropped according to the element's handling of best + effort traffic). [Again, if marking is available, these reclassified + datagrams SHOULD be marked.] + +Ordering and Merging + + TSpec's are ordered according to the following rules. + + TSpec A is a substitute ("as good or better than") for TSpec B if (1) + both the token rate r and bucket depth b for TSpec A are greater than + or equal to those of TSpec B; (2) the peak rate p is at least as + large in TSpec A as it is in TSpec B; (3) the minimum policed unit m + is at least as small for TSpec A as it is for TSpec B; and (4) the + maximum datagram size M is at least as large for TSpec A as it is for + TSpec B. + + TSpec A is "less than or equal" to TSpec B if (1) both the token rate + r and bucket depth b for TSpec A are less than or equal to those of + TSpec B; (2) the peak rate p in TSpec A is at least as small as the + peak rate in TSpec B; (3) the minimum policed unit m is at least as + large for TSpec A as it is for TSpec B; and (4) the maximum datagram + size M is at least as small for TSpec A as it is for TSpec B. + + A merged TSpec may be calculated over a set of TSpecs by taking (1) + the largest token bucket rate, (2) the largest bucket size, (3) the + largest peak rate, (4) the smallest minimum policed unit, and (5) the + smallest maximum datagram size across all members of the set. This + use of the word "merging" is similar to that in the RSVP protocol + [10]; a merged TSpec is one which is adequate to describe the traffic + from any one of constituent TSpecs. + + + +Shenker, et. al. Standards Track [Page 12] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + A summed TSpec may be calculated over a set of TSpecs by computing + (1) the sum of the token bucket rates, (2) the sum of the bucket + sizes, (3) the sum of the peak rates, (4) the smallest minimum + policed unit, and (5) the maximum datagram size parameter. + + A least common TSpec is one that is sufficient to describe the + traffic of any one in a set of traffic flows. A least common TSpec + may be calculated over a set of TSpecs by computing: (1) the largest + token bucket rate, (2) the largest bucket size, (3) the largest peak + rate, (4) the smallest minimum policed unit, and (5) the largest + maximum datagram size across all members of the set. + + The minimum of two TSpecs differs according to whether the TSpecs can + be ordered. If one TSpec is less than the other TSpec, the smaller + TSpec is the minimum. Otherwise, the minimum TSpec of two TSpecs is + determined by comparing the respective values in the two TSpecs and + choosing (1) the smaller token bucket rate, (2) the larger token + bucket size (3) the smaller peak rate, (4) the smaller minimum + policed unit, and (5) the smaller maximum datagram size. + + The RSpec's are merged in a similar manner as the TSpecs, i.e. a set + of RSpecs is merged onto a single RSpec by taking the largest rate R, + and the smallest slack S. More precisely, RSpec A is a substitute + for RSpec B if the value of reserved service rate, R, in RSpec A is + greater than or equal to the value in RSpec B, and the value of the + slack, S, in RSpec A is smaller than or equal to that in RSpec B. + + Each network element receives a service request of the form (TSpec, + RSpec), where the RSpec is of the form (Rin, Sin). The network + element processes this request and performs one of two actions: + + a. it accepts the request and returns a new Rspec of the form + (Rout, Sout); + b. it rejects the request. + + The processing rules for generating the new RSpec are governed by the + delay constraint: + + Sout + b/Rout + Ctoti/Rout <= Sin + b/Rin + Ctoti/Rin, + + where Ctoti is the cumulative sum of the error terms, C, for all the + network elements that are upstream of and including the current + element, i. In other words, this element consumes (Sin - Sout) of + slack and can use it to reduce its reservation level, provided that + the above inequality is satisfied. Rin and Rout MUST also satisfy + the constraint: + + r <= Rout <= Rin. + + + +Shenker, et. al. Standards Track [Page 13] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + When several RSpec's, each with rate Rj, j=1,2..., are to be merged + at a split point, the value of Rout is the maximum over all the rates + Rj, and the value of Sout is the minimum over all the slack terms Sj. + + NOTE: The various TSpec functions described above are used by + applications which desire to combine TSpecs. It is important to + observe, however, that the properties of the actual reservation + are determined by combining the TSpec with the RSpec rate (R). + + Because the guaranteed reservation requires both the TSpec and the + RSpec rate, there exist some difficult problems for shared + reservations in RSVP, particularly where two or more source + streams meet. Upstream of the meeting point, it would be + desirable to reduce the TSpec and RSpec to use only as much + bandwidth and buffering as is required by the individual source's + traffic. (Indeed, it may be necessary if the sender is + transmitting over a low bandwidth link). + + However, the RSpec's rate is set to achieve a particular delay + bound (and is notjust a function of the TSpec), so changing the + RSpec may cause the reservation to fail to meet the receiver's + delay requirements. At the same time, not adjusting the RSpec + rate means that "shared" RSVP reservations using guaranteed + service will fail whenever the bandwidth available at a particular + link is less than the receiver's requested rate R, even if the + bandwidth is adequate to support the number of senders actually + using the link. At this time, this limitation is an open problem + in using the guaranteed service with RSVP. + +Guidelines for Implementors + + This section discusses a number of important implementation issues in + no particular order. + + It is important to note that individual subnetworks are network + elements and both routers and subnetworks MUST support the guaranteed + service model to achieve guaranteed service. Since subnetworks + typically are not capable of negotiating service using IP-based + protocols, as part of providing guaranteed service, routers will have + to act as proxies for the subnetworks they are attached to. + + In some cases, this proxy service will be easy. For instance, on + leased line managed by a WFQ scheduler on the upstream node, the + proxy need simply ensure that the sum of all the flows' RSpec rates + does not exceed the bandwidth of the line, and needs to advertise the + rate-based and non-rate-based delays of the link as the values of C + and D. + + + + +Shenker, et. al. Standards Track [Page 14] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + In other cases, this proxy service will be complex. In an ATM + network, for example, it may require establishing an ATM VC for the + flow and computing the C and D terms for that VC. Readers may + observe that the token bucket and peak rate used by guaranteed + service map directly to the Sustained Cell Rate, Burst Size, and Peak + Cell Rate of ATM's Q.2931 QoS parameters for Variable Bit Rate + traffic. + + The assurance that datagrams will not be lost is obtained by setting + the router buffer space B to be equal to the token bucket b plus some + error term (described below). + + Another issue related to subnetworks is that the TSpec's token bucket + rates measure IP traffic and do not (and cannot) account for link + level headers. So the subnetwork network elements MUST adjust the + rate and possibly the bucket size to account for adding link level + headers. Tunnels MUST also account for the additional IP headers + that they add. + + For datagram networks, a maximum header rate can usually be computed + by dividing the rate and bucket sizes by the minimum policed unit. + For networks that do internal fragmentation, such as ATM, the + computation may be more complex, since one MUST account for both + per-fragment overhead and any wastage (padding bytes transmitted) due + to mismatches between datagram sizes and fragment sizes. For + instance, a conservative estimate of the additional data rate imposed + by ATM AAL5 plus ATM segmentation and reassembly is + + ((r/48)*5)+((r/m)*(8+52)) + + which represents the rate divided into 48-byte cells multiplied by + the 5-byte ATM header, plus the maximum datagram rate (r/m) + multiplied by the cost of the 8-byte AAL5 header plus the maximum + space that can be wasted by ATM segmentation of a datagram (which is + the 52 bytes wasted in a cell that contains one byte). But this + estimate is likely to be wildly high, especially if m is small, since + ATM wastage is usually much less than 52 bytes. (ATM implementors + should be warned that the token bucket may also have to be scaled + when setting the VC parameters for call setup and that this example + does not account for overhead incurred by encapsulations such as + those specified in RFC 1483). + + To ensure no loss, network elements will have to allocate some + buffering for bursts. If every hop implemented the fluid model + perfectly, this buffering would simply be b (the token bucket size). + However, as noted in the discussion of reshaping earlier, + implementations are approximations and we expect that traffic will + become more bursty as it goes through the network. However, as with + + + +Shenker, et. al. Standards Track [Page 15] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + shaping the amount of buffering required to handle the burstiness is + bounded by b+Csum+Dsum*R. If one accounts for the peak rate, this + can be further reduced to + + M + (b-M)(p-X)/(p-r) + (Csum/R + Dsum)X + + where X is set to r if (b-M)/(p-r) is less than Csum/R+Dsum and X is + R if (b-M)/(p-r) is greater than or equal to Csum/R+Dsum and p>R; + otherwise, X is set to p. This reduction comes from the fact that + the peak rate limits the rate at which the burst, b, can be placed in + the network. Conversely, if a non-zero slack term, Sout, is returned + by the network element, the buffer requirements are increased by + adding Sout to Dsum. + + While sending applications are encouraged to set the peak rate + parameter and reshaping points are required to conform to it, it is + always acceptable to ignore the peak rate for the purposes of + computing buffer requirements and end-to-end delays. The result is + simply an overestimate of the buffering and delay. As noted above, + if the peak rate is unknown (and thus potentially infinite), the + buffering required is b+Csum+Dsum*R. The end-to-end delay without + the peak rate is b/R+Ctot/R+Dtot. + + The parameter D for each network element SHOULD be set to the maximum + datagram transfer delay variation (independent of rate and bucket + size) through the network element. For instance, in a simple router, + one might compute the difference between the worst case and best case + times it takes for a datagram to get through the input interface to + the processor, and add it to any variation that may occur in how long + it would take to get from the processor to the outbound link + scheduler (assuming the queueing schemes work correctly). + + For weighted fair queueing in a datagram environment, D is set to the + link MTU divided by the link bandwidth, to account for the + possibility that a packet arrives just as a maximum-sized packet + begins to be transmitted, and that the arriving packet should have + departed before the maximum-sized packet. For a frame-based, slotted + system such as Stop and Go queueing, D is the maximum number of slots + a datagram may have to wait before getting a chance to be + transmitted. + + Note that multicasting may make determining D more difficult. In + many subnets, ATM being one example, the properties of the subnet may + depend on the path taken from the multicast sender to the receiver. + There are a number of possible approaches to this problem. One is to + + + + + + +Shenker, et. al. Standards Track [Page 16] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + choose a representative latency for the overall subnet and set D to + the (non-negative) difference from that latency. Another is to + estimate subnet properties at exit points from the subnet, since the + exit point presumably is best placed to compute the properties of its + path from the source. + + NOTE: It is important to note that there is no fixed set of rules + about how a subnet determines its properties, and each subnet + technology will have to develop its own set of procedures to + accurately compute C and D and slack values. + + D is intended to be distinct from the latency through the network + element. Latency is the minimum time through the device (the speed + of light delay in a fiber or the absolute minimum time it would take + to move a packet through a router), while parameter D is intended to + bound the variability in non-rate-based delay. In practice, this + distinction is sometimes arbitrary (the latency may be minimal) -- in + such cases it is perfectly reasonable to combine the latency with D + and to advertise any latency as zero. + + NOTE: It is implicit in this scheme that to get a complete + guarantee of the maximum delay a packet might experience, a user + of this service will need to know both the queueing delay + (provided by C and D) and the latency. The latency is not + advertised by this service but is a general characterization + parameter (advertised as specified in [8]). + + However, even if latency is not advertised, this service can still + be used. The simplest approach is to measure the delay + experienced by the first packet (or the minimum delay of the first + few packets) received and treat this delay value as an upper bound + on the latency. + + The parameter C is the data backlog resulting from the vagaries of + how a specific implementation deviates from a strict bit-by-bit + service. So, for instance, for datagramized weighted fair queueing, C + is set to M to account for packetization effects. + + If a network element uses a certain amount of slack, Si, to reduce + the amount of resources that it has reserved for a particular flow, + i, the value Si SHOULD be stored at the network element. + Subsequently, if reservation refreshes are received for flow i, the + network element MUST use the same slack Si without any further + computation. This guarantees consistency in the reservation process. + + + + + + + +Shenker, et. al. Standards Track [Page 17] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + As an example for the use of the slack term, consider the case where + the required end-to-end delay, Dreq, is larger than the maximum delay + of the fluid flow system. The latter is obtained by setting R=r in + the fluid delay formula (for stability, R>=r must be true), and is + given by + + b/r + Ctot/r + Dtot. + + + In this case the slack term is + + S = Dreq - (b/r + Ctot/r + Dtot). + + + The slack term may be used by the network elements to adjust their + local reservations, so that they can admit flows that would otherwise + have been rejected. A network element at an intermediate network + element that can internally differentiate between delay and rate + guarantees can now take advantage of this information to lower the + amount of resources allocated to this flow. For example, by taking an + amount of slack s <= S, an RCSD scheduler [5] can increase the local + delay bound, d, assigned to the flow, to d+s. Given an RSpec, (Rin, + Sin), it would do so by setting Rout = Rin and Sout = Sin - s. + + Similarly, a network element using a WFQ scheduler can decrease its + local reservation from Rin to Rout by using some of the slack in the + RSpec. This can be accomplished by using the transformation rules + given in the previous section, that ensure that the reduced + reservation level will not increase the overall end-to-end delay. + +Evaluation Criteria + + The scheduling algorithm and admission control algorithm of the + element MUST ensure that the delay bounds are never violated and + datagrams are not lost, when a source's traffic conforms to the + TSpec. Furthermore, the element MUST ensure that misbehaving flows + do not affect the service given to other flows. Vendors are + encouraged to formally prove that their implementation is an + approximation of the fluid model. + +Examples of Implementation + + Several algorithms and implementations exist that approximate the + fluid model. They include Weighted Fair Queueing (WFQ) [2], Jitter- + EDD [3], Virtual Clock [4] and a scheme proposed by IBM [5]. A nice + theoretical presentation that shows these schemes are part of a large + class of algorithms can be found in [6]. + + + + +Shenker, et. al. Standards Track [Page 18] + +RFC 2212 Guaranteed Quality of Service September 1997 + + +Examples of Use + + Consider an application that is intolerant of any lost or late + datagrams. It uses the advertised values Ctot and Dtot and the TSpec + of the flow, to compute the resulting delay bound from a service + request with rate R. Assuming R < p, it then sets its playback point + to [(b-M)/R*(p-R)/(p-r)]+(M+Ctot)/R+Dtot. + +Security Considerations + + This memo discusses how this service could be abused to permit denial + of service attacks. The service, as defined, does not allow denial + of service (although service may degrade under certain + circumstances). + +Appendix 1: Use of the Guaranteed service with RSVP + + The use of guaranteed service in conjunction with the RSVP resource + reservation setup protocol is specified in reference [9]. This + document gives the format of RSVP FLOWSPEC, SENDER_TSPEC, and ADSPEC + objects needed to support applications desiring guaranteed service + and gives information about how RSVP processes those objects. The + RSVP protocol itself is specified in Reference [10]. + +References + + [1] Shenker, S., and J. Wroclawski, "Network Element Service + Specification Template", RFC 2216, September 1997. + + [2] A. Demers, S. Keshav and S. Shenker, "Analysis and Simulation of + a Fair Queueing Algorithm," in Internetworking: Research and + Experience, Vol 1, No. 1., pp. 3-26. + + [3] L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for + Packet Switching Networks," in Proc. ACM SIGCOMM '90, pp. 19-29. + + [4] D. Verma, H. Zhang, and D. Ferrari, "Guaranteeing Delay Jitter + Bounds in Packet Switching Networks," in Proc. Tricomm '91. + + [5] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan, + "Efficient Network QoS Provisioning Based on per Node Traffic + Shaping," IBM Research Report No. RC-20064. + + [6] P. Goyal, S.S. Lam and H.M. Vin, "Determining End-to-End Delay + Bounds in Heterogeneous Networks," in Proc. 5th Intl. Workshop on + Network and Operating System Support for Digital Audio and Video, + April 1995. + + + + +Shenker, et. al. Standards Track [Page 19] + +RFC 2212 Guaranteed Quality of Service September 1997 + + + [7] A.K.J. Parekh, A Generalized Processor Sharing Approach to Flow + Control in Integrated Services Networks, MIT Laboratory for + Information and Decision Systems, Report LIDS-TH-2089, February 1992. + + [8] Shenker, S., and J. Wroclawski, "General Characterization + Parameters for Integrated Service Network Elements", RFC 2215, + September 1997. + + [9] Wroclawski, J., "Use of RSVP with IETF Integrated Services", RFC + 2210, September 1997. + + [10] Braden, R., Ed., et. al., "Resource Reservation Protocol (RSVP) + - Version 1 Functional Specification", RFC 2205, September 1997. + +Authors' Addresses + + Scott Shenker + Xerox PARC + 3333 Coyote Hill Road + Palo Alto, CA 94304-1314 + + Phone: 415-812-4840 + Fax: 415-812-4471 + EMail: shenker@parc.xerox.com + + + Craig Partridge + BBN + 2370 Amherst St + Palo Alto CA 94306 + + EMail: craig@bbn.com + + + Roch Guerin + IBM T.J. Watson Research Center + Yorktown Heights, NY 10598 + + Phone: 914-784-7038 + Fax: 914-784-6318 + EMail: guerin@watson.ibm.com + + + + + + + + + + +Shenker, et. al. Standards Track [Page 20] + |