\documentstyle[psfig,fancybox]{seminar}
\def\printlandscape{\special{landscape}}
\slideframe{Oval}
\newtheorem{property}{Property}
\newcommand{\benq}{\begin{eqnarray}}
\newcommand{\eenq}{\end{eqnarray}}
\newcommand{\heading}[1]{%
  \begin{center}
    \large\bf
%%    \shadowbox
{#1}%
  \end{center}}
\begin{document}



\begin{slide}

\center{\Large {Scheduling, Link Sharing, Admission Control,
Resource Reservation}}

\vskip 0.2in

\center{\bf Ion Stoica, Prashant Chandra, Rex Xi Xu}

\center{Carnegie Mellon University \\
 {\tt e-mails: {istoica, prashant,rexx}$@$cs.cmu.edu}}

\newslide
\heading{\underline {\Large Overview}}

\vskip 0.2in
\begin{itemize}
\item Scheduling
\item Link Sharing
\item Admission Control
\item Resource Reservation 
\item Open Problems
\end{itemize}
\vskip 0.5in


\newslide
\heading{\underline {\Large Scheduling}}
\vskip 0.2in
\begin{figure}
\centerline{\psfig{figure=sch.ps}}
\end{figure}
\begin{itemize}
\item Network multiplexing point: scheduling algorithm
\item Network \& application negotiate policy: setting scheduler 
parameters
\end{itemize}
\vskip 0.2in

\newslide
\heading{\underline {\Large Scheduling (cont.)}}
\vskip 0.2in
\begin{itemize}
\item[] Desired features:
\begin{itemize}
\item session isolation
\item efficient bandwidth utilization
\item fair bandwidth allocation among active sessions
\item low implementation complexity
\end{itemize}
\end{itemize}
\vskip 0.4in

\newslide 
\heading{\underline {\Large Scheduling (cont.)}}
\vskip 0.2in
\begin{itemize}
\item Work-conserving - the scheduler is never idle when there is a
packet to be transmitted
\begin{itemize}
\item Examples: Weighted Fair Queueing (WFQ), Delay Earliest Due
(Delay-EDD), Hierarchical Round-Robin (HRR)
\end{itemize}
\item Non work-conserving - the scheduler transmits {\it only} the 
{\it eligible} packets 
\begin{itemize}
\item Examples: Stop-and-Go, Jitter-EDD, Rate Controlled Static
Priority
\end{itemize}
\end{itemize}
\vskip 0.4in

\newslide
\heading{\underline {\Large The Fluid-Flow Model}}
\vskip 0.2in
\begin{itemize} 
\item Each session is characterized by a {\it weight} which determines 
the {\it relative} share of the bandwidth that the session should receive.
\item Active sessions are assumed to be serviced in arbitrarily {\it small}
increments.
\end{itemize}
\vskip 2cm

\newslide
\heading{\underline {\Large The Fluid-Flow Model (cont.)}}
\begin{figure}
\centerline{\psfig{figure=ideal.ps}}
\end{figure}

\newslide
\heading{\underline {\Large Packet Fair Qeueuing (PFQ)}}
\vskip 0.5cm
\begin{itemize}
\item[]{\bf Algorithm} The packets are transmitted in the order in which they
{\it would} finish in the corresponding fluid-flow system.
\item[]
{\bf Delay bound} No packet is serviced ${\theta}_{max}$ latter
than it would have been serviced in the fluid-flow system,
where ${\theta}_{max} = $ time to transmit a packet of max. size.
\item[]
{\bf Allocation Accuracy} Difference between the service time a
session should receive in fluid-flow system and the one it actually
receives increases proportionally with the number of active sessions.
\end{itemize}
\vskip 0.1in

\newslide
\heading{\underline {\Large PFQ (cont.)}}
\vskip 0.2in
\begin{itemize}
\item Disadvantages:
\begin{itemize} 
\item High implementation complexity
\item Not good for hierarchical schemes
\item Coupling the delay and bandwidth
\end{itemize}
\end{itemize}
\vskip 0.6in

%\newslide
%\heading{\underline {\Large Self-Clocked Fair Queueing (SCFQ)}}
%\vskip 0.2in
%\begin{itemize}
%\item[]{\bf Idea} - Approximates virtual time
%\begin{itemize}
%\item Advantage: Lower complexity
%\item Disadvantage: Delay bounds increase (with the
%{\it number} of active sessions)
%\end{itemize}
%\end{itemize}
%\vskip 0.4in

\newslide
\heading{\underline {\Large Worst-case Fair Weighted Fair Queueing (WF$^2$Q)}}
\vskip 0.2in
\begin{itemize}
\item[] {\bf Idea} - Besides finishing time use the {\it eligible} time for
selecting the next packet to be transmitted
\item[] {\bf Advantage} - Allocation accuracy is optimal
\item[] {\bf Disadvantages} - High implementation complexity ({\bf
Note:} This is addressed by WF$^2$Q+)
\end{itemize}
\vskip 0.5in

\newslide
\heading{\underline {\Large CPU allocation}}
\vskip 0.1in
\begin{itemize}
\item[] New problems:
\begin{itemize}
\item The length of the request is not known in advance
\item Accommodate synchronization (i.e., due to I/O operations)
\end{itemize}
\item[] Example of Algorithms:
\begin{itemize}
\item Lottery Scheduling
\item Hierarchical Stride Scheduling
\item Earliest Eligible Virtual Deadline First
\item Start-time Fair Queueing
\end{itemize}
\end{itemize}

\newslide
\heading{\underline {\Large Decoupling Delay and Bandwidth}}
\vskip 0.2in
\begin{itemize}
\item[] {\bf Problem:} Fair Queueing algorithms introduce coupling
between {\it delay} and {\it bandwidth}:
\benq
Delay = \frac{Burstiness}{Bandwidth}
\eenq
\item[] {\bf Solutions:}
\begin{enumerate}
\item Use algorithms, such as EDF and Static Priority (SP)
\begin{itemize}
\item Disadvantage: 
\begin{itemize}
\item do not ensure fairness 
\item requires shapers to regulate the traffic
\end{itemize}
\end{itemize}
\item Use EDF in conjunction with {\it arrival} and {\it service} curves
\end{enumerate}
\end{itemize}
\vskip 0.2cm

\newslide
\heading{\underline {\Large Arrival/Service Curves}}
\vskip 0.2cm
\begin{figure}
\centerline{\psfig{figure=asCurves.ps}}
\end{figure}

\newslide
\heading{\underline {\Large Link Sharing}}
\vskip 0.2in
\begin{itemize}
\item Share link bandwidth between different ``entities'' (e.g., session,
set of sessions with the same QoS, organization)
\item Hierarchical link-sharing ``rules'':
\begin{enumerate}
\item At each level each entity is guaranteed to receive its share
\item The share of any {\it inactive} entity is redistributed between
the {\it active} entities at the same level
\end{enumerate}
\item Should ensure QoS for aggregate entities
\end{itemize}
\vskip 0.4in

\newslide
\heading{\underline {\Large Link Sharing (Example)}}
\vskip 0.2cm
\begin{figure}
\centerline{\psfig{figure=LinkSharing.ps}}
\end{figure}

\newslide
\heading{\underline {\Large Admission Control}}
\vskip 0.2in
\noindent
\begin{itemize}
\item {\bf Goal:} Admit as many sessions as possible, while guaranteeing
their requirements
\item Main factors:
\begin{itemize}
\item traffic characterization
\item scheduling algorithm
\item service characterization
\end{itemize}
\end{itemize}
\vskip 0.2in

\newslide
\heading{\underline {\Large Resource Reservation}}
\vskip 0.2in
\begin{itemize}
\item Reserve bandwidth/buffers to provide the contracted QoS per flow
\item Desirable Properties:
\begin{itemize}
\item Ability to deal with large multicast groups
\item Support sender and receiver initiated multicast models
\item Support resource sharing between senders within a group
\item Adapt dynamically to route changes
\end{itemize}
\end{itemize}
\vskip 0.2in

\newslide
\heading{\underline {\Large Examples}}
\vskip 0.2in 
\noindent
\begin{itemize}
\item RSVP
\item ST II/II+
\item Tenet Suite 1/2
\item ATM Forum PNNI/UNI
\end{itemize}
\vskip 1.2in

\newslide
\heading{\underline {\Large RSVP Message Flow}}
\vskip 0.2cm
\centerline{\psfig{figure=rsvp1.ps,height=4.0in}}

\newslide
\heading{\underline {\Large RSVP Reservation Styles}}
\vskip 0.2cm
\centerline{\psfig{figure=rsvp2.ps,height=4.0in}}

\newslide
\heading{\underline {\Large Research Issues}}
\vskip 0.2in 
\begin{itemize}
\item Study the implications of using service curve in integrating {\it
fairness} and {\it reservation} 

\item Develop hierarchical algorithms for link-sharing when the
guaranteed service is specified by service curve

\item Address the synchronization problem for the CPU case

\item Generalize the notion of {\it fairness} to distributed systems

\item Develop new interfaces for signalling/resource reservation protocols to invoke, co-ordinate and manage various services and resources in application aware networks

%\item Develop efficient and stable distributed algorithms for
%resource allocations
\end{itemize}
\vskip 0.4cm

\end{slide}
\end{document}