Subject: proposal for slack term

From: [email-masked] (Dilip Kandlur)
Date: Wed, 22 Nov 95 15:39:30 -0500

Hi Folks,

this is a proposal for introduction of a slack term to the guaranteed
service specifications.  It is a revision of a draft that we had
posted some time back on the mailing list.  We plan to present this
for consideration at the Dallas meeting.

-- Dilip.

----------------------------------------------------------------------

A case for extension of the Guaranteed Delay service specifications

ABSTRACT

The guaranteed delay service class defines a service that provides an
upper bound on the end-to-end delay for packets from a source node to
a receiver node.  This draft proposes the introduction of an excess
delay term, termed "slack", to the service specifications of this
service class.

BACKGROUND AND MOTIVATION

The guaranteed delay service class [GSdraft] defines a service that
provides an upper bound on the end-to-end delay for packets from a
source node to a receiver node.  The service request is
specified in the form of a traffic specification (TSpec) and a
level of service specification (RSpec) to the network element.
The Tspec includes a token bucket size, b, and a token accumulation
rate, r.
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 values
respectively along all network elements on the path of the flow.

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,               (2)

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

To summarize, the major limitations of the current mechanisms for
level of service specification are:
  - they restrict the maximum end-to-end delay bound which can be
    requested.
  - they do not permit different levels of service guarantees (except
    for the "error" terms) at different network elements.

PROPOSED EXTENSION

We propose to introduce an element representing excess delay into the
specification for the level of service (RSpec).  This element, termed
slack, represents the difference between the desired delay and the
delay obtained using a reservation level R in a fluid flow system:

        S = D_req - (b/R + C_tot/R + D_tot)		(3).

The enhanced RSpec is a tuple (R_i, S_i) that must be presented to
different network elements along the path of the flow.  The network
elements may in turn modify the RSpec using some simple operation
rules described below.

OPERATIONAL RULES

Each network element receives a service request of the form (TSpec,
RSpec), where the RSpec is of the form (R_in, S_in).  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 (R_out, S_out);
b. it rejects the request.

The processing rules for this transformation are governed by the
delay constraint:

   S_out + b/R_out + C_i/R_out <= S_in + b/R_in + C_i/R_in	(4),

where C_i is the contribution that was advertised by this network
element.  In other words, this element consumes (S_in - S_out) of
slack and it can use it to reduce its reservation level.  R_in and
R_out must also satisfy the constraint:

	r <= R_out <= R_in

At split points, it is necessary to to merge the Rspecs for different
links.  In the current specification this is accomplished by obtaining

                         R_out = max { R_j },
                                  j

where j spans all RSpecs downstream of the split point.  In the
extended specification this rule is supplemented by a rule to merge
the slack terms in the Rspec.  This merging may be achieved
conservatively by choosing the smallest slack:

			S_out = min { S_j }.
				 j

When the cumulative error term, C_tot_i, for all links upstream of i is
available, S_out may be further enhanced to

		S_out = min { C_tot_i * (1/R_j - 1/R_out) + s_j }
			 j

The network element must reserve buffer space for the flow.
This required buffer space must now include a provision for S_out as
an additional delay term.

BENEFITS OF PROPOSED EXTENSION

It is now possible for an application to specify a desired end-to-end
delay guarantee, D_req, that is larger than the maximum
value, D_max, of the fluid flow system:

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

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.

The slack term may be used by the network elements to adjust their
local reservations.  This local adjustment provides additional
flexibility in handling flow requests which can be used to admit
flows that would otherwise have been rejected.

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) by
using the slack in the RSpec.  Given an RSpec (R_in, S_in), it would
do so by setting R_out = R_in and S_out = S_in - s.

Similarly, a network element using a WFQ scheduler could decrease its
local reservation from R_in to R_out by using some of the slack in the
RSpec.  This would be accomplished by using the RSpec transformation in
equation 4 which ensures that the reduced reservation level will not
increase the overall end-to-end delay.  The WFQ scheduler would,
however, be constrained in that it can not reduce the reservation
level R_out below the traffic rate, r.

CONCLUSIONS

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.