Subject: Proposal for the inclusion of slack term

From: [email-masked] (Roch Guerin)
Date: Wed, 23 Aug 1995 16:49:06 -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 A SLACK TERM IN THE RSPEC
                ======================================

OVERVIEW
--------

This note proposes that an excess delay term i.e. "slack" be added to
the Service Specification currently defined in the drafts related to
"Integrated Services".  The focus is on the guaranteed delay service
class [GSdraft].  The note first motivates the need for such a slack
term by identifying a number of limitations in the current
specifications, and illustrating their implications. The major
limitations are as follows:

- Restriction on the maximum end-to-end delay bound which can be
  requested.
- Inability to allow different guarantees (except for the "error"
  terms) at different network elements.

The second part of the note describes how the use of a slack term can
eliminate these limitations.  It also points to the fact that the
impact of introducing a slack term is minimal in that it can simply be
ignored or even omitted, and does not require consistent operation
among network elements.  As a result, the potential benefits of
introducing such a term appears to far outweigh the associated cost.

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

LIMITATIONS OF THE CURRENT SPECS
--------------------------------

Based on the current draft, the service rate R requested by a flow
must satisfy r <= R.  This in turn imposes a limit on the maximum
value of the end-to-end delay bound D_max which a flow can request.
From equation (1), we have:

            D_max = b/r + C_tot/r + D_tot,               (1)

D_max should in general, be larger than the desired end-to-end delay
bound, especially for flows with large b and small r, i.e., bursty
flows.  However, there are cases, e.g., flows with small b, for which
D_max can be smaller than the desired end-to-end delay bound.  For
example, take a voice connection that can tolerate delays of 100msec,
with r=4kBytes/sec, b=L=96 bytes, where L is the maximum packet
length.  If the call is local, e.g., goes through two routers,
specifying R=r=4kBytes yields an end-to-end delay of 3*96/4,000=72msec,
i.e., there is a budget of 28msec left over.  Here, it was assumed
that the error term in each network element is L, and that the D terms
are essentially 0, e.g., 0 propagation delay and OC-12 links.  What
this means, is that the current service specifications forces this
connection to be provided with a better service than it really needs.
This will in turn lower the number of such flows that the routers can
support.  There is, therefore, an incentive for providing mechanisms
which can remedy this problem.

Another limitation, although less significant, of the current
specifications, is that they require all network elements over which a
flow is routed, to provide essentially the same guarantees.  For
example, assuming that all the network elements are identical, i.e.,
have the same C and D terms,  a service request with rate, R,
means that all network elements have to be able to allocate this rate.
This also means that they all provide the same delay guarantees. If
one of them is not able to do so, the request will then be rejected.
It may, however, have been possible to accommodate the request, if
different network elements had been asked to provide different
guarantees.  For example, the bottleneck network element which caused
the request to be rejected, might have been able to accommodate a
looser delay bound that would have been compensated for by asking for
tighter delay guarantees at less loaded network elements.  Support for
asymmetric guarantees may not be feasible with all scheduling policies
as it requires that the scheduler be able to INTERNALLY separate delay
from rate guarantees.  However, it is certainly possible with many
different types of schedulers, e.g., [Zhang94,RCSD95].  It is,
therefore, desirable to provide mechanisms that will allow such
improvements in efficiency.

BENEFITS OF INTRODUCING A SLACK TERM
------------------------------------

The rest of this note illustrates how the specification of a slack
term in the service request, eliminates the above limitations.  It
also points to the fact that the presence of a slack term only has a
minimal impact on the current specifications, as it can simply be
ignored or omitted without any consequence on the delivery of the
service guarantees.

It was pointed out in the previous section that an application may
desire an end-to-end delay guarantee, D_req, larger than the maximum
value D_max it can request.  In such cases, the difference

        S = D_req - D_max = D_req - (b/r + C_tot/r + D_tot)

is denoted as the slack.  Note that it is also possible for a service
request to ask for a rate, R, such that D = b/R + C_tot/R + D_tot be
less than D_req, so that a non-zero slack, S = D_req - D can be
specified even in cases where D_req < D_max.  Motivations for when
and why this may be useful are provided below.

Assuming that a slack term, S, is present in the service request, a
service element at an intermediate node which can internally
differentiate between delay and rate guarantees can now take advantage
of this information to lower the amount of resources it allocates to
the flow.  For example, an RCSD scheduler could increase the local
delay bound, d, assigned to the flow, up to a value d'= d + S.  In
general, if network element i consumes an amount s_i of the slack, it
can increase the delay bound of the flow from d to d + s_i.  It will
then also modify the slack term to reflect the amount used, and
therefore update the slack field by setting S := S - s_i.  The
relaxation of the local delay guarantee which the network element has
to provide to the flow, will later allow it to accept other flows that
it would otherwise have had to reject.

It should be pointed out that there is no requirement for different
network elements to use a consistent rule to determine how much of the
slack they should take.  For example, the entire slack could be
consumed by a single network element, or alternatively the slack could
be left untouched if none of the network elements on the path were
capable of taking advantage of it.  Irrespective of how and whether
the slack is being consumed at different network elements, the
end-to-end delay bound will be guaranteed.

Introducing a slack term can also allow acceptance of a request which
would otherwise have been rejected.  Assume, for example, an RCSD
network element which advertised quantities C and D so that the local
delay bound it needs to provide an incoming request with rate R, is equal
to C/R + D. Assume further, that because of its current load, the best
delay bound the network element can provide to the flow given its
traffic parameters is of the form d = C/R + D + e.  If no slack term is
present (or the slack is 0), then the network element has to reject
the call.  On the other hand, if a slack term is present with S >= e,
then the network element can decrease the slack by an amount e and
increase the local deadline for the flow to d = C/R + D + e so that it
accepts the request.  In general, the availability of a slack term
will improve the chance of success of service requests, when the load
on network elements is unbalanced.  As a result, it may be worthwhile
for a service request to specify a slightly larger service rate R than
needed, so that it can also specify a non-zero slack term. However,
note that this is useful only if the network elements can internally
distinguish between delay and rate guarantees.

One environment in which this may indeed be a very useful
capability, is when service requests need to extend across switched
ATM clouds.  In this context, ATM clouds have to somehow figure out
which values to advertise for their C and D error terms.  Even if
all the switches in a cloud are capable of essentially providing
"rate-based" delay guarantees, i.e., ensure the form of the
bound used in the service specifications remains the same, the
advertised cloud level quantities will at best be approximations.
The presence of a slack term can go a long way towards ensuring
insensitivity to these approximations.  Note that being
conservative in picking the D (and C) values which the ATM cloud
advertises, will not really help overall.  It may help the ATM
cloud increase its likelihood of success for a given reservation,
but this will be at the cost of increasing the burden on the other
routers on the path (a bigger D will trigger a request for a larger
R).  This may in turn increase the overall rejection probability.

HANDLING OF SLACK TERM AT SPLIT POINTS
--------------------------------------

Consider a split point at which two R specs with rates R1 and R2,
R1 > R2 are received.  With the current draft, the greater of the
two rates, R1, will be reserved upstream of the split point.  For
the receiver which requested the lower rate R2, this will result
in a lower end-to-end delay bound than required.  Specifically,
the bound will be lowered by an amount equal to:

                   Ctot_i * (1/R2 - 1/R1),

where Ctot_i is the accumulated value of the C error terms up to the
split point.  This, in essence, creates slack even though none was
initially present.  The presence of a slack term provides a mechanism
for network elements to take advantage of such instances.  This is
achieved by applying the following rules at split points:

1. At split point i, the RSpec sent upstream has a rate Rmax which is

                          Rmax = max { Rj },
                                  j

where j spans all RSpecs downstream of split point i.

2. At split point i, the RSpec sent upstream has a slack term S given by

             S = min { Ctot_i * (1/Rj - 1/Rmax) + Sj },
                  j

where Sj is the slack term received in downstream RSpec j after
reducing it by the amount of slack that is consumed locally.

PROPERTIES OF SLACK ALLOCATION
------------------------------

At a given network element, the slack allocation algorithm is defined
by a function f(.) that for a given flow takes as one of its inputs t
he slack S received with the reservation for the flow, and provides as
output a new slack f(S) <= S.  The value S - f(S) corresponds to the
portion of slack consumed locally by the network element.
There are several desirable properties for a slack allocation algorithm
at network elements.  Below we give a short list of some of the more
significant ones, and briefly describe their implications.

 - Monotonicity: If for a given flow, S1 <= S2, then f(S1) <= f(S2)

 - Idempotence of call admission:  The slack allocation algorithm
 should be such that it does not affect the idempotence of call
 admission, that is if there exists slack allocation values for
 which a set of flows is admissible, then this set must be admissible
 irrespective of the order in which the reservations for these flows
 are received.

 - Locality:  The function f1(.) used at network element 1 need not be
 the same as the function f2(.) used at network element 2.

CONCLUSION
----------

In this note, we have provided arguments in support of the introduction
of a slack term as part of a service request.  We have motivated the
need for such a term by pointing out some limitations/constraints
imposed by the current specifications.  In particular, it was pointed
out that the maximum value of the end-to-end delay bound which can
currently be requested, may in some cases be insufficient and, therefore,
result in inefficient operation.  Similarly, while the approach of
providing delay bounds by requiring that each network element guarantee
a given service (clearing) rate has the advantage of simplicity, it
also implies that requests will be rejected whenever any network
element on the path cannot guarantee this desired service rate.  This
can be improved when using delay-based scheduling policies by allowing
different delay guarantees at different network elements.  The use of a
slack term in the service requests provides a simple solution to these
two problems.  Furthermore, it is also useful in dealing with potential
inaccuracies in advertised C and D values, which may be common with
non-rate-based schedulers. A similar problem is also present
when attempting to extend service requests across ATM clouds.
Finally, a slack term can allow network elements to take advantage
of the creation of slack which naturally occurs at split points.

In addition, to providing a simple and common solution to these problems,
a key property of the slack term is that it has only minimal impact
on the current specifications.  Specifically, it can be ignored or
even omitted without impacting the service guarantees, and when used
does not require additional interactions or even consistent operation
among network elements.  In short, a slack term solves several
important problems with minimal impact on the current specifications,
and can be taken advantage of at the cost of little additional
complexity.

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

[Zhang94] H. Zhang and D. Ferrari. "Rate-controlled service disciplines."
  Journal of High Speed Networks, 3(4):389--412, 1994.