Subject: Proposal for the inclusion of peak rate

From: [email-masked] (Roch Guerin)
Date: Wed, 23 Aug 1995 16:48:49 -0400

We would like to submit the following proposal for consideration by the
INT-SERV working group.  This material is the result of numerous
discussions involving:

Leo Georgiadis, Roch Guerin, Vinod Peris, Raju Rajan
IBM T.J. Watson Research Center

and

Scott Shenker
Xerox PARC

             INCLUSION OF PEAK RATE IN THE TRAFFIC SPECS
             ===========================================

OVERVIEW
--------

This note outlines some of the benefits of including a peak rate
descriptor in the traffic specifications that are used in the drafts
related to "Integrated Services".  We illustrate these benefits in the
context of the guaranteed delay service class.  They are as follows:

1. A given end-to-end delay guarantee D_req can be satisfied with a lower
   rate R.
2. The buffer requirements at intermediate nodes can be lowered.
3. More calls can be accepted at intermediate nodes.
4. The peak rate can be used as an option without requiring end-to-end
   consistency.
5. Peak rate is needed when crossing switched ATM cloud.

[GSdraft] describes the guaranteed service specification; we describe
only the parts that are relevant to this note.  The traffic
characteristics of a flow are specified in terms of a TSpec, which
currently includes a token bucket size, b, and a token accumulation
rate, r.  The guaranteed delay service is invoked by specifying the
TSpec as well as the requested service (RSpec) to the network element.
The RSpec in this case is a rate, R.  Network element, i, specifies the
values C_i and D_i such that the end-to-end delay bound for any packet
of a flow with TSpec (r, b) and an RSpec of R (>= r), is given by

                   b/R + C_tot/R + D_tot,               (1)

where C_tot and D_tot are the sum of the C_i and D_i along all
network elements on the path of the flow.

BENEFITS OF INCLUDING A PEAK RATE
---------------------------------

In practice, a burst of size b can never enter the network
instantaneously.  Rather, the arrival of packets is constrained to
a peak rate which is bounded, for example by the access link speed
or by a network access policer.  If this peak rate is included in
the TSpec, then it is possible to account for the finite speed at
which packets enter the network to provide a tighter expression for
the end-to-end delay bound than the one given in equation (1).  More
specifically, if the peak rate, P, is included in the TSpec, the
end-to-end delay bound is given by

           b/R * (P-R)/(P-r) + C_tot/R + D_tot          (2)

For simplicity, we have assumed in equation (2) that R <= P.
A proof of the above result can be obtained from Lemma 2 of [RCSD95]
or Theorem 1 of [Cruz95].

Assuming that a receiver needs an end-to-end delay guarantee of D_req,
the use of equation (2) instead of equation (1) to determine the
necessary service rate, results in a lower value of R.  As seen from
equation (2), the savings in the requested rate R can be quite
significant when R is close to P.

An important aspect of this extension is that it is possible for
receivers to determine the rate they will request using EITHER
equation (1) OR equation (2).  In other words, receivers whose
implementations do not let them recognize P, can still determine their
rate from equation (1) and be guaranteed D_req as before.  It is
important to note that the provision of the peak rate only facilitates
a more accurate calculation of the end-to-end delay bound, and does
not alter the delay experienced by the packets.

The previous paragraphs described the benefit of specifying a peak
rate to the receivers.  Further advantages can be obtained by making
the peak rate available to intermediate nodes as well.  These nodes
benefit from this knowledge in two respects.

First, knowledge of the peak rate lets an intermediate node compute a
lower value for the maximum buffer requirements of the flow.
Specifically, if an intermediate node only knows the traffic
parameters b and r of a flow together with the values Csum and Dsum
since the last reshaping (merge/split) point, then it must allocate a
buffer of size

           b + (Csum/R + Dsum)r                         (3)

However, if the peak rate P is known, the amount of buffer that needs
to be allocated is given by

           (P-X)b/(P-r) + (Csum/R + Dsum)X              (4)

where             / r   if b/(P-r) <= Csum/R + Dsum
        X       = | R   if b/(P-r) > Csum/R + Dsum & P > R
                  \ P   otherwise

Note that the above expression can be greatly simplified by restricting
the range of R, i.e., R <= P, which is the region of practical significance.
As can be seen from comparing equations (3) and (4), knowledge of the
peak rate P can provide buffer savings at intermediate nodes.  Note
that intermediate nodes which do not recognize the term P, can again
ignore it and use equation (3) as before to determine their buffer
requirements.

A second benefit of making the peak rate, P, known to intermediate
nodes, is that it can allow them to accept more flows.  This is above
and beyond the increase due to the reduction in the requested rate R
that is obtained from making P known to the receiver. Specifically,
providing P to intermediate nodes (service elements) allows them to
determine a smaller traffic envelope for a given flow, i.e., the
traffic envelope of a flow characterized by traffic parameters P, b,
and r is below that of a flow for which only b and r are given (in the
latter case P is assumed to be infinite).  Knowledge of this smaller
traffic envelope can be used by some schedulers, e.g, EDF, when
checking the schedulability of a new flow (call admission), and will
allow them to accept more flows [RCSD95].

Finally, as is pointed out in RFC 1821, providing the peak rate, P,
together with b and r as part of a service request, can greatly
facilitate the extension of service requests across ATM clouds.  In
particular, if a flow is to be extended across an ATM cloud using an
ATM VC, then the cloud will require that a peak rate be specified as
part of the traffic and QoS parameters needed to establish the VC.  If
no peak rate is provided, some conservative estimate, e.g., speed of
the access link, will have to be used.  This can adversely affect the
likelihood of the request being admitted.

HANDLING OF PEAK RATE AT MERGE POINTS
-------------------------------------

TSpecs which include a peak rate are ordered according to the following
rules:  TSpec A is said to be greater than or equal to TSpec B if all its
parameters are greater than or equal to those of B, i.e., P_A >= P_B,
b_A >= b_B, and r_A >= r_B.  At a merge point, a substitute TSpec is
created by selecting any TSpec which is greater than or equal to any of
the merged TSpec.  For example, a TSpec with the maximum values of P, b,
and r over all merged TSpec is such a substitute.

CONCLUSION
----------

In this note, we have provided arguments in support of the optional
specification of a maximum (peak) transmission rate P as part of the
traffic parameters of a flow.  We showed how knowledge of the peak
rate P resulted in requests for a lower guaranteed service rate R
given a desired end-to-end delay bound.  In addition, we also showed
that knowledge of P at intermediate nodes translates into lower buffer
requirements for each flow, and can also be used by some schedulers to
accept more flows. The usefulness of including a peak rate was also
mentioned in the context of extending flows across ATM clouds.
Finally, it is important to emphasize that the ability to take
advantage of the peak rate information is not mandatory.  In other
words, the peak rate field can be omitted or ignored without any
impact to the service guarantees.  Similarly, use of the peak rate
information by service elements and/or service requesters need not be
consistent in order for any of them to individually realize the
associated benefits.

REFERENCES
----------

[GSdraft] S. Shenker and C. Partridge.  "Specification of Guaranteed
  Quality of Service (draft-ietf-intserv-guaranteed-svc-01.txt)."
  INTERNET-DRAFT, Internet Engineering Task Force - Integrated
  Services WG, July 1995.

[RCSD95] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan.
  "Efficient network QoS provisioning based on per node traffic
  shaping." Research Report RC 20064, IBM, T. J. Watson Research Center,
  May 1995.  The paper can be obtained via the URL
  http://www.watson.ibm.com:8080/main-cgi-bin/gunzip_paper.pl?/PS/5371.ps.gz

[Cruz95] R. L. Cruz. "Quality of service guarantees in virtual circuit
  switched networks."  IEEE J. Select. Areas Commun., 13(6):1048--1056,
  August 1995.