\documentstyle{article}
%\input{/home/wahab/papers/psfig-dvips}
\newcommand{\hs}{\hspace*{.5cm}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\benq}{\begin{eqnarray}}
\newcommand{\eenq}{\end{eqnarray}}
\newtheorem{defin}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{theor}{Theorem}
\newtheorem{col}{Corollary}
\def\ged{\hbox{${\vcenter{\vbox{
        \hrule height 0.4pt\hbox{\vrule width 0.4pt height 6pt
        \kern5pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}}
% Macros 

\newcommand{\comment}[1]{}

\newcommand{\attention}[1]{\marginpar{\sl\raggedright #1}}
%\newcommand{\attention}[1]{}

\newcommand{\topicskip}{\vskip .5cm}

\newcommand{\topnote}[1]{\vspace{-1cm}\begin{verbatim} #1 \end{verbatim}}

% how can I do this?
%\newenvironment{comm}{\comment\{ }{\}}

\newcommand{\polish}{\attention{{\bf Polish}}}

%% For ``editorial'' comments

%\draftheader[A Proportional Share Allocation Algorithm]

\title{\bf Mechanisms to provide QoS guarantees}
\author{
}

\date{} 
%\renewcommand{\baselinestretch}{1.3}
\setcounter{secnumdepth}{4} 

\setlength{\oddsidemargin}{-0.5in} 
\setlength{\textwidth}{7.5in}
\setlength{\topmargin}{-1.25in}
\setlength{\textheight}{10.0in}

\begin{document}
\maketitle

\begin{abstract}
We give a brief introduction to scheduling, link sharing,
admission control and resource reservation mechanisms, used to provide QoS
guarantees to applications in integrated-services networks.  We give an overview of some of the latest research results and point out some open problems which we believe are valuable starting points for future research.
\end{abstract}

\section{Scheduling}

Scheduling algorithms operate at the smallest timescale (packet transmission time) of the overall traffic management framework.  The basic function of a scheduling algorithm is to pick the next packet to transmit from a set of queued packets in accordance with some pre-determined policy.  A ``good'' scheduling algorithm should exhibit the following features:

\begin{itemize}

\item isolation - The algorithm should provide QoS guarantees for  a session
in the presence of traffic fluctuations and (possibly) misbehaving
sessions.

\item utilization - The algorithm should utilize the bandwidth
efficiently.

\item fairness - The available bandwidth should be divided among the
active sessions in a fair manner.

\item low complexity - The algorithm must have a simple
implementation. This is critical in high-speed network switches, such
as ATM, where the transmission time for a cell is in the order of
$\mu s$.

\end{itemize}

There are a large number of scheduling algorithms proposed in literature, each of which offers some combination of the above desired properties.  Broadly, scheduling algorithms can be classified as 1) work-conserving---the scheduler is never idle when there is a packet to transmit and 2) non work-conserving---the scheduler transmits only those packets that are considered {\em eligible} in some sense.  Delay Earliest Due Date (Delay-EDD), Weighted Fair Queueing (WFQ) and Virtual Clock (VC) are examples of work-conserving algorithms, while Stop-and-Go, Jitter-EDD and Rate Controlled Static Priority are examples of non work-conserving algorithms.
 
Since in the IETF specifications of both guaranteed
QoS~\cite{Bib-She96} and committed rate QoS~\cite{Bib-Bak96}, the
proposed scheduling policy at switches is based on the class of
fair-queueing algorithms, in the
remainder of this section we concentrate mainly on discussing the
algorithms in this class.  However the above mentioned service disciplines could be implemented using other scheduling algorithms as well.


\subsection{The Fluid Flow Model}

We assume that each session is characterized by a {\it weight} which
determines the {\it relative} share of the bandwidth that the session
should receive. In the idealized model (known as fluid-flow system)
sessions are assumed to be serviced in arbitrarily {\it small}
increments. In this way, a session is guaranteed to receive its share
over any interval of time $d t$.

Since in practice this is not possible (one of the reasons is that the
packet transmission is usually assumed to be non-preemptive), a large
number of approximation algorithms have been developed. Demers,
Keshav, and Shenker were the first to propose the Packet Fair Queueing
(PFQ) discipline, according to which {\it the packets are transmitted
in the order in which they would finish in the corresponding
fluid-flow system~\cite{Bib-Dem89}}. By using the concept of {\it
virtual time}, Parekh
and Gallager have analyzed the PFQ\footnote{In their work PFQ is known
as Packet-by-Packet Generalized Processor Sharing (PGPS for short).}
algorithm when the input traffic stream conforms to the {\em
leaky-bucket} constraints~\cite{Bib-Par92,Bib-Par92a}. In particular,
they have shown that no packet is serviced ${\theta}_{max}$ latter
than it would have been serviced in the fluid-flow system, where
${\theta}_{max}$ represents the time to transmit a packet of maximum
size.

\vskip 0.2in

\noindent
{\bf Note:} In many papers the session weight (denoted $\rho$) also
represents the {\it minimum} amount of bandwidth that a session is
{\it guaranteed} to receive. Thus, for a switch with capacity $C$ we
have:

\benq
\sum_{i = 1}^{n} {\rho}_i \leq C
\eenq

\noindent
In this model the ``excess bandwidth'' (i.e., $C - \sum_{i = 1}^{n}
{\rho}_i$) is allocated among the competing sessions in proportion
their weights. This introduces a coupling between the guaranteed
bandwidth and the allocation of the ``excess'' bandwidth, which may be
undesirable.

\subsection{Implementation Issues}
The complexity in implementing fair-queueing algorithms arises basically from the need to sort packets (at high-speed) according to their virtual finish times and from the need to keep track of the ideal fluid-flow system.  It is possible that in a short interval of time as much as $O(n)$ events could occur in the fluid-flow system.  Various solutions have been proposed to reduce the implementation complexity of fair queueing systems~\cite{Bib-Gol94,Bib-Ben96b,Bib-Goy96,Bib-Sti95}.

\subsection{CPU Allocation} 

In the context of networks with value added services, scheduling algorithms need to be applied to allocate the processing resources inside the network (similar to link bandwidth).  However, we note two main differences that makes the
problem harder in this case:

\begin{itemize}

\item Unlike packet scheduling where the length of the packet and
therefore the service time is assumed to be known in advance at the
packet arrival, in the processor case it is hard (sometimes
impossible) to predict {\it exactly} how much service time a process
will actually use. This makes the computation of the virtual time
difficult, which has direct impact on the accuracy of the previous
algorithms.


\item A general solution should take into account the synchronization
(i.e., due to I/O operations). So far, we are not aware of any
fair-queueing based algorithm to address this problem.

\end{itemize}

Recently, numerous algorithms have been developed for processor
scheduling~\cite{Bib-Wal94,Bib-Wal95,Bib-Sto96,Bib-Goy96}. 

\subsection{Delay-Bandwidth Coupling}

The main drawback of fair-queueing algorithms is that the introduction
of a coupling between the bandwidth allocation and delay. Thus, a
session requesting a small delay must allocate a large bandwidth
irrespective of its throughput. This makes itdifficult to support
low-latency/low-throughput sessions efficiently.

A promising approach to address this problem is to use the concepts of
{\it arrival} and {\it service} curves~\cite{Bib-Cru95}. The arrival
curve provides an upper bound for the incoming traffic over any
interval of time, while the service curve provides a lower bound for
the the service time that a session is guaranteed to receive over any
interval of time. By using the arrival curve to characterize the
session incoming traffic and the service curve to characterize the
service time, the delay is bounded by the maximum horizontal distance
between the arrival and the service curves, while the session backlog
is bounded by the maximum vertical distance between these two
curves. By using an EDF algorithm in which the deadlines are assigned
as if the the session receives {\it exactly} its guaranteed service
time, it can be shown that both the bounds for delay and session's
backlog are guaranteed as long as, for any time interval $\Delta t$ the
sum of the guaranteed service time over all sessions is smaller than
$\Delta t$ (i.e., the CPU is not over-committed). An open question
here is how the concept of fairness can be integrated in this
model. Another open issue is how the arrival curve can be efficiently
computed in practice.


\section{Link Sharing}
The main purpose of link-sharing is to share the bandwidth on a link
between different ``entities''. An entity can be anything from a
single session to a set of sessions that request similar QoS, or the
set of sessions belonging to a certain
organizations. ~\cite{Bib-Flo95} proposes an hierarchical link-sharing
model, where at the higher level the bandwidth is distributed between
multiple organizations, and at the lower level(s) the share of each
organization is distributed between different QoS classes, such as
real-time and best-effort. At each level an entity is guaranteed to
receive its share during congestion. Moreover, if one or more entities
are passive (i.e., do not have any packet to send) their share is
redistributed between the active entities at the same level.

Since link-sharing requires isolation among different entities and
flexibility in redistributing the ``excess'' bandwidth, fair-queueing
based algorithms were the natural choice for implementing these
mechanisms. In a hierarchical fair queueing system, the delay bounds are strongly influenced by the accuracy with which the fluid system is approximated, which is not the case for a single-level fair queueing system~\cite{Bib-Ben96b}.
Finally, we note that it is possible for the
lower levels(s) to use other scheduling disciplines. For example in
the best-effort class, the sessions may be simply scheduled according
to the FCFS or SP disciplines.


\section{Admission Control}

The main objective of an admission control test is to admit as many
sessions as possible, while guaranteeing their QoS requirements. In
general, the number of admitted sessions is determined by:

\begin{itemize}

\item traffic characterization - As shown in~\cite{Bib-Kni95},
increasing the accuracy of characterizing sessions' incoming traffic,
also increases the number of accepted sessions and the link
utilization. However, a more accurate characterization requires a
larger number of parameters. This dictates a trade-off between the
characterization accuracy and the computation complexity of the
admission test. Another potential problem is that it is hard to
provide an accurate characterization when the traffic profile is not
known in advance (e.g., the traffic of a video-conferencing
application). Finally, we note that although it is possible to predict
the future traffic based on previous data, this will not ensure
strict guarantees.

\item scheduling algorithm - Usually, there is a trade-off between the
algorithm complexity and the number of admitted sessions. While more
sophisticated algorithms, such as Delay-EDD, are able to admit a larger
number of sessions, other more simple algorithms, such as FCFS and
Static Priorities (SP), involve a lower computation complexity. 

\end{itemize}

\begin{table}
\caption{Comparison of resource reservation setup protocols}
\begin{center}
\begin{tabular}{||c||c|c|c|c|c|c||} \hline \hline
& \multicolumn{1}{c|}{\bf Scalability} & \multicolumn{1}{|c|}{\bf Resource} & \multicolumn{1}{|c|}{\bf Multicast} & \multicolumn{1}{|c|}{\bf QoS} & \multicolumn{1}{|c|}{\bf State} & \multicolumn{1}{|c||}{\bf Setup} \\ 
& & \multicolumn{1}{|c|}{\bf sharing} & \multicolumn{1}{|c|}{\bf model} & \multicolumn{1}{|c|}{\bf routing} & \multicolumn{1}{|c|}{\bf management} & \\ \hline \hline
{\bf RSVP} & Yes & Yes & \begin{minipage}{1in}{\small Receiver-init} \end{minipage} & No & soft-state & one-pass \\ \hline
{\bf ST-II} & Yes & Yes & \parbox{1.3in}{\small Receiver/Sender-init}& No & hard-state & two-pass \\ \hline
{\bf Tenet-2} & Yes & Yes & \parbox{1.3in}{\small Receiver/Sender-init} & Yes & hard-state & two-pass \\ \hline
{\bf PNNI/UNI} & Yes & No & \parbox{1.3in}{\small Receiver/Sender-init} & Yes & hard-state & two-pass \\ \hline \hline
\end{tabular}
\end{center}
\end{table}

\section{Resource Reservation}

In order to provide a contracted, quantitative QoS to a particular flow, the
network usually needs to reserve resources such as bandwidth/buffers for that
flow.  An important component in the integrated services network architecture
is the reservation setup protocol that is responsible for setting up and 
maintaining reservations on each link along the end-to-end path through the 
network.  Some of the desirable properties of a reservation setup protocol are:

\begin{itemize}

\item Low connection setup time.

\item Scalability (should deal with large multicast groups).

\item Support for Sender and Receiver-initiated multicast.

\item Resource sharing between senders in the same multicast group.

\item Dynamic re-negotiation of QoS.

\item Transparent support for re-routing.

\item Consistent multipoint-to-multipoint state management (MxN).

\end{itemize}

RSVP~\cite{Bib-RSVP} is a reservation setup protocol for the integrated services Internet, 
which has some of the above properties.  It uses receiver initiated reservations to 
deal with heterogeneous receivers and provides different reservation styles to 
support shared/distinct reservations for a multicast group.  By using ``soft
state'' which is periodically refreshed by senders/receivers in a multicast 
group, RSVP is able to adapt dynamically to group membership and route changes.

RSVP is not a routing protocol, but relies on existing unicast/multicast 
routing algorithms.  Since the multicast distribution tree is already assumed to exist when the receiver initiates reservation requests, RSVP could potentially try to establish reservations along sub-optimal
routes.  Another drawback of RSVP is the use of periodically refreshed ``soft-state''.  This does not guarantee consistency of reservation state and could lead to trashing~\cite{Bib-Mitz}.  Moreover the soft-state protocol allows occasional disruptions in service (when the reservations are not refreshed in a timely manner) which makes it difficult to provide guaranteed services.

Other examples of reservation setup protocols are the ATM Forum PNNI/UNI specifications~\cite{Bib-PNNI,Bib-UNI}, the Tenet-1/2 schemes~\cite{Bib-Tenet1,Bib-Tenet2} and the Internet Stream Protocol (ST-II)~\cite{Bib-STII}.  Table 1 compares some of the interesting characteristics of these protocols.

In an application aware network framework, it should be noted that reservation protocols (signalling in general) would need to allocate and manage more resources such as compute servers and invoke appropriate value added services, than the traditional network resources such as bandwidth and buffers.  The signalling protocol should also be able to deal with multiple connections of different QoS within the context of a single multiparty call.  New interfaces are needed between applications and the signalling protocols and between signalling protocols and service providers to allocate and manage services and resources in the network. 

{\small
\begin{thebibliography}{99}

\bibitem{Bib-Bak96} F. Baker, R. Guerin, and D. Kandlur,
``Specification of Committed Rate Quality of Service,'', {\it IETF Draft},
August 1996.

\bibitem{Bib-Ben96} J. C. R. Bennett and H. Zhang, ``WF$^{2}$Q :
Worst-case Fair Queueing'', {\it Proc. of IEEE INFOCOM'96},
San-Francisco, March 1996.

\bibitem{Bib-Ben96b} J. C. R. Bennett and H. Zhang, ``Hierarchical
Packet Fair Queueing Algorithms'', {\it Proc. of ACM SIGCOMM'96},
Stanford University, August 1996, pp. 143--156.

\bibitem{Bib-Cru95} R. L. Cruz, ``Quality of service guarantees in
virtual circuit switched networks," {\em IEEE Journal of Selected
Areas in Communication}, vol. 13, no. 6, Aug. 1995.

\bibitem{Bib-Dem89} A. Demers, S. Keshav, and S. Shenkar, ``Analysis and
Simulation of a Fair Queueing Algorithm'', {\em Journal of
Internetworking Research \& Experience}, October 1990, pp. 3--12.


\bibitem{Bib-Flo95} S. Floyd, and V. Jacobson, ``Link-Sharing and
Resource Management Models for Packet Networks'', {\it IEEE ACM
Transactions on Networking}, vol. 3, no. 4, August 1995, pp. 365--386.

\bibitem{Bib-Gol94} S. J. Golestani, ``A Self-Clocked Fair Queueing
Scheme for Broadband Applications'', {\em
Proc. of IEEE INFOCOM'94}, April 1994, pp. 636--646.

\bibitem{Bib-Goy96} P. Goyal, X. Guo and H. M. Vin, ``A Hierarchical
CPU Scheduler for Multimedia Operating Systems'', to appear in {\em
Proc. of the 2nd OSDI Symposium}, October 1996.

\bibitem{Bib-Kni95} E. W. Knightly, D. E. Wrege, J. Liebeherr, and
H. Zhang, ``Fundamental Limits and Tradeoffs of Providing
Deterministic Guarantees to VBR Video Traffic'', {\it Proc. of ACM
SIGMETRICS'95}, Ottawa, Canada, May, 1995. 

\bibitem{Bib-Par92} A. K. Parekh and R. G. Gallager, ``A Generalized
Processor Sharing Approach To Flow Control in Integrated Services
Networks-The Single Node Case'', {\em ACM/IEEE Trans. on
Networking}, Vol. 1, No. 3, 1992, pp. 344--357.

\bibitem{Bib-Par92a} A. K. Parekh, ``A Generalized
Processor Sharing Approach To Flow Control in Integrated Services
Networks'', {\em Ph.D Thesis}, Department of EE and CS, MIT, 1992.

\bibitem{Bib-She96} S. Shenker, C. Partridge, and R. Guerin,
``Specification of Guaranteed Quality of Service,'', {\it IETF Draft},
August 1996.

\bibitem{Bib-Sti95} D. Stiliadis and A. Varma, ``Frame-based Fair
Queueing: A New Traffic Scheduling Algorithm for Packet-Switched
Networks,'' Technical Report UCSC-CRL-95-39, July 1995.

\bibitem{Bib-Sto96} I. Stoica, H. Abdel-Wahab, and K. Jeffay, ``A
Proportional Share Resource Allocation for Real-Time, Time-Shared
Systems'', to appear in {\it Proc of RTSS'96}, December 1996.

\bibitem{Bib-Sur96} S. Suri, G. Varhese, and G. Chandranmenon, ``Leap
Forward Virtual Clock'', accepted to {\it INFOCOMM'97}.

\bibitem{Bib-Wal94} C. A. Waldspurger and W. E. Weihl. ``Lottery
Scheduling: Flexible Proportional-Share Resource Management,'' {\em
Proc. of the 1st OSDI Symposium}, November 1994, pp. 1--12.

\bibitem{Bib-Wal95} C. A. Waldspurger. ``Lottery
and Stride Scheduling: Flexible Proportional-Share Resource
Management,'' {\it PhD Thesis}, Technical Report, MIT/LCS/TR-667,
Laboratory for CS, MIT, Sept. 1995.

\bibitem{Bib-Zha91} L. Zhang, ``VirtualClock: A New Traffic Control
Algorithm for Packet-Switched Networks'', {\em ACM Trans. on
Comp. Systems}, vol. 9, no. 2, May 1991, pp. 101--124.

\bibitem{Bib-RSVP} R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin. ``Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification,'' {\em Internet Draft, draft-ietf-rsvp-spec-13.ps}, August 1996.

\bibitem{Bib-Mitz} Danny J. Mitzel, Deborah Estrin, Scott Shenker and Lixia Zhang. ``A Study of Reservation Dynamics in Integrated Services Packet Networks,'' {\em Proc. of INFOCOM `96}, March 1996, San Fransisco, USA.

\bibitem{Bib-PNNI} The ATM Forum. {\em Private Network-Network Interface Specification Version 1.0}, March 1996.

\bibitem{Bib-UNI} The ATM Forum. {\em ATM User-Network Interface Specification Version 3.1}, September 1994.

\bibitem{Bib-Tenet1} A. Banerjea, D. Ferrari, B. A. Mah, M. Moran, D. C. Verma and H. Zhang.  ``The Tenet Real-Time Protocol Suite: Design, Implementation, and Experiences,'' {\em IEEE/ACM Transactions on Networking}, vol. 4, no. 1, pp. 1-11, February 1996.

\bibitem{Bib-Tenet2} R. Bettati, D. Ferrari, A. Gupta, W. Heffner, W. Howe, M. Moran, Q. Nguyen and R. Yavatkar. ``Connection Establishment for Multi-Party Real-Time Communication,'' {\em Proc. of NOSSDAV `95} New Hampshire, April 1995, pp. 255-266.

\bibitem{Bib-STII} L. Delgrossi and L. Berger. ``Internet Stream Protocol Version 2 (ST2) Protocol Specification --- Version ST2+,'' {\em Request for Comments 1819}, August 1995.

\end{thebibliography}

}
\end{document}