\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 Scheduling, Link Sharing, Admission Control, Resource Reservation}  
\author{
}

\date{} 
\renewcommand{\baselinestretch}{1.3}
\setcounter{secnumdepth}{4} \oddsidemargin 0.3in \textwidth 6.3in
\topmargin -0.7in \textheight 9.4in
\begin{document}
\maketitle

\begin{abstract}
We summarize the latest research results in scheduling, link sharing,
admission control and resource reservation in communication
networks. We also present similar results obtained recently in the
context of CPU scheduling. Finally, we briefly point out some open
problems which we believe are valuable starting points for future
research.
\end{abstract}

\section{Scheduling}


First we discuss scheduling in the context of packet switched
networks. Next, we show how these algorithms can be applied to the domain
of processor scheduling, and discuss the new problems that arise in
this case. 

A ``good'' scheduling algorithm should exhibit the following features:

\begin{itemize}

\item isolation - The algorithm should guarantee the traffic of 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}

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 compatible to the class of
fair-queueing algorithms which were extensively analyzed, in the
remaining of this section we concentrate mainly on discussing the
algorithms in this class.


\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}, previously introduced by Zhang~\cite{Bib-Zha91}, 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.

\subsubsection{Implementation Issues}

Since for computing the finishing time of each packet, PFQ requires to
keep track of the events that occur in the fluid-flow system (and not
in the real one) the resulting implementation might be quite
expensive.  Moreover, it is possible that during an arbitrary small
interval of time, as much as $O(n)$ events to occurs in the
corresponding fluid-flow system.  In practice, when $n$ is large, the
overhead to treat this events is unacceptable (e.g., in a high-speed
ATM switches).

As a solution to this problem, Golestani has proposed an algorithm,
called Self-Clocked Fair Queueing (SCFQ), based on a the virtual time
approximation~\cite{Bib-Gol94}. In SCFQ there is no need to keep trace
of the events in the fluid-flow system.\footnote{The virtual time is
updated when an event (eg., a session becomes backlog-ed) occurs in
the real system and not in the fluid-flow one.} However, this is done
to the expense of the algorithm accuracy: the delay bounds for a
packet transmission increases proportionally with the number of active
sessions.


A second problem with both PFQ and SCFQ is that the difference between
the service time that a session should receive (in the fluid-flow
system) and the service time it receives in the real system can be as
large as $O(n)$. This creates serious problems for a hierarchical
organization (see~\cite{Bib-Ben96b}).

Recently, Bennett and Zhang have addressed this problem by developing
a new algorithm, called W$F^2$Q~\cite{Bib-Ben96}. Besides the finishing
time, W$F^2$Q introduces the concept of {\it eligible} time, i.e., the
time when a packet should start transmission in the corresponding
fluid-flow system. Unlike PFQ which considers for transmission all
outstanding packets, W$F^2$Q chooses the next packet to be send only among
the {\it eligible} packets.

Unfortunately, similarly to PFQ, W$F^2$Q requires to keep track of the
events in the-fluid flow system. To solve this problem, Bennett and
Zhang have proposed a new approximation of the virtual time. The new
scheme is called W$F^2$Q+~\cite{Bib-Ben96b}. It is worth to mention
that unlike SCFQ, W$F^2$Q+ ensures the same delays bounds as W$F^2$Q
(and PFQ).

Finally, we note that recently several other fair-queueing algorithms
trying to address these problems have been developed. Among these we
mention: Leap Forward Virtual Clock~\cite{Bib-Sur96}, Start Time Fair
Queueing~\cite{Bib-Goy96} and Frame-Based Fair
Queueing~\cite{Bib-Sti95}.


\subsection{CPU Allocation} 

In general the algorithms used for bandwidth allocation can be easily
applied for processor allocation (by simply taking the time to
transmit a packet to be the time allocated to a corresponding
process). However, we note two main differences that makes the
problem harder in this case:

\begin{enumerate}

\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{enumerate}

Recently, numerous algorithms have been developed for processor
scheduling. Among these we note:

\begin{itemize}

\item Lottery scheduling - this algorithms allocates time slices
randomly (by using a binomial distribution) in proportion to the
processes' weights~\cite{Bib-Wal94,Bib-Wal95}. Although simply to
implement, its probabilistic nature makes it inappropriate for
supporting guaranteed services.

\item Hierarchical stride scheduling - this algorithm is similar to PFQ
but uses an approximation of the virtual
time~\cite{Bib-Wal95}. Although, in a static system (i.e., when the
number of active processes does not change) it is more accurate than
PFQ it is not clear how this algorithm performs in a dynamic system.

\item Earliest Eligible Virtual Deadline First - similarly to W$F^2$Q,
this algorithm makes use of the eligibility concept to improve the
allocation accuracy~\cite{Bib-Sto96}. In addition, this algorithm
decouples the size of the request issued by a process from the size of
a time slice. Thus, an application may issue a request that makes
sense for it, e.g., processing an MPEG frame. Finally, the algorithm
guarantees optimal bounds for the difference between the service time
that a client actually receives and the service time it is supposed to
receive in the corresponding fluid-flow system.

\item Start-time Fair Queueing - this algorithm is used for
hierarchically partitioning of a CPU among various application
classes~\cite{Bib-Goy96}. While this algorithm supports both uniform
and non-uniform quanta, the delay bounds increase linearly with the
number of clients. However, when the number of clients is small, in
terms of delay, this algorithm can be superior to classical fair
queueing algorithms, such as PFQ.

\end{itemize}

\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 difficult to support
low-latency/low-throughput sessions efficiently.

\vskip 0.2in

{\bf Note:} As shown in ~\cite{Bib-Ben96b} it is possible to use
fair-queueing algorithms for decoupling the delay/bandwidth
allocation. However, this is done at the expense of the session
isolation; in this case, the traffic of every session should be
explicitly regulated.

\vskip 0.2in

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 organization, 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. It is interesting to note that although for a single level
PFQ and W$F^2$Q guarantees the same delay bounds, in the case of an
hierarchical scheme W$F^2$Q achieves much better delay bounds than
PFQ~\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 the 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 EDF, 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. 

\item service characterizations - An accurate service characterization
may increase the number of accepted sessions as well. However, this
implies that the scheduling discipline should be able to deliver the
requested service. For example, the fair-queueing algorithms will be
able to deliver service only based on the allocated bandwidth. If the
service is characterized by both bandwidth and delay then other
disciplines which decouples these parameters, such as EDF, should be
used.

\end{itemize}

\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 Ability to deal with large dynamic multicast groups.

\item Support heterogeneous receivers.

\item Support aggregation/merging of reservation requests within the same 
   multicast group.

\item Adapt dynamically to route changes.

\end{itemize}

RSVP is a reservation setup protocol for the integrated services Internet, 
which has 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 existing multicast algorithms do no consider QoS
metrics, RSVP could potentially try to establish reservations along sub-optimal
routes.  Also the use of "soft-state" poses a problem for supporting 
guaranteed service in the Internet.




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


\end{thebibliography}
\end{document}