% $Id: %
\input{iap-scdefs.tex} 
\documentclass[a4paper]{slides}
\usepackage{
  iap-commentstar,
  color,
  graphicx,
  amsfonts,
  amsmath,
  epsfig,
  url
  }
\input{pstricks}

\definecolor{dgreen}{rgb}{0,.5,0}
\def\dgreen#1{{\color{dgreen} #1}}
\definecolor{dblue}{rgb}{0,0,.6}
\def\dblue#1{{\color{dblue} #1}}

\newcommand{\psdm}[1]{{\psfig{figure=#1}}}

\pagestyle{empty}

\includecomment*{mynotes}{\cbstart}{\cbend}
\includecomment{mynotes}

\includecomment*{xnotes}{\cbstart}{\cbend}
\includecomment{xnotes}


\excludecomment{xnotes}
\excludecomment{mynotes}
\renewcommand{\topmargin}{-0.5in} % without notes
\renewcommand{\textheight}{9in}  % 

%\renewcommand{\topmargin}{-1.25in} % with notes
%\renewcommand{\textheight}{11in}    

\DeclareRobustCommand\itemL{\item}

\newenvironment{mymode} {
    \tiny \em \topsep 0pt 
    \begin{enumerate}\itemsep 0pt \parsep 0pt}{\itemsep 0pt \parsep 0pt \end{enumerate}
}




\begin{document}

\vfill
\vspace{0.5in}
\rule{\linewidth}{2mm}
\begin{center}
\vspace{-13mm}
{\huge \bf GRID Resource Scheduling - Subsidiarity and Networking}
\end{center}
\rule{\linewidth}{2mm}

\ \\

\center{\Large {Jon Crowcroft}}
\center{{\it Jon.Crowcroft@cl.cam.ac.uk}}
\center{{\tt http://www.cl.cam.ac.uk/homes/jac22}}

\center{June 5, 2002}
\center{Terena Networking Conference 2002}

\vspace{0.5in}
\vfill


\raggedright \sloppy \renewcommand{\hyphenpenalty}{1000000000}
\itemsep 0pt
\setlength{\itemindent}{0pt}
\parsep 0pt

\small


\center{\Large{GRID Resource Scheduling}}
\raggedright \sloppy \renewcommand{\hyphenpenalty}{1000000000}
\itemsep 0pt
\setlength{\itemindent}{0pt}
\parsep 0pt

\small

This is a two part talk. 

Part I is about:

{\tt http://www.cs.ucl.ac.uk/staff/S.Bhatti/grs/}

Part II is about:

{\tt http://www.cs.ucl.ac.uk/staff/jon/mbng/}

Acknowledgements:

The two parts are based on work funded by the PPARC (the Managed Bandwith ng project,
and EPSRC (the GRID Resource Scheduling project) as part of the UK
E-Science program, at UCL and the Computer Laboratory at the
University of Cambridge, run by the speaker, together
with Prof Pete Clark in UCL Department of Physics, and Dr Saleem Bhatti and Soren Sorenson in UCL
Department of Computer Science.


\begin{slide}
\slidetitle{Abstract, Part I}

\begin{verbatim}

There was a young man from Madrid
Who was trying to program the GRID.
When looking for cycles.
And storage and bandwidth,
Without Euros, he was mostly undid.

\end{verbatim}
\end{slide}

\begin{slide}
\slidetitle{Abstract, continued}

Grid Applications make use of significant quantities of resources,
whether it be CPU cycles, number of CPUs (whether clustered or
distributed over a wide area), storage (whether local, remote,
structured or flat, central or distributed), and network capacity.

Historically, there has been research into scheduling in distributed
systems, but often the assumption has been that a network is largely
in the local area, and is dedicated to the task in hand. Even in that
constrained environment, scheudling is an NP-hard problem.

In the GRID, the resources are almost all shared, including the
network.

This talk is about the work in the GRS project which is trying to
provide an "application cradle" into which the range of different GRID
middleware can sit, that gives a simple API to requesting, and being
granted, or denied access to a set of distributed resources, including
networking resources.

Think {\em Supply Chain} Economics.
\end{slide}


\begin{slide}
\slidetitle{History}
\slidesubtitle{What is the GRID?}

``The Grid : Blueprint for a New Computing Infrastructure'',
by Ian Foster (Editor), Carl Kesselman (Editor)
Morgan Kaufmann Publishers; (November 1998) 
ISBN: 1558604758

It's a metaphor - you plug in a toaster or a matter transmitter to a 
13Amp socket on the wall. You don't care how the electricity is generated or
distributed.
\end{slide}

\begin{slide}
\slidetitle{What's a GRID For?}

The idea is you have some scientific problem to solve e.g. :
\begin{itemize}
\item
Where is the Dark Matter?
\item
How does this protein fold?
\item
Is there a likely causal link between MMR and Autism?
\item
Is the average temperature of the sea or atmosphere increasing?
\item
Will this shape wing lift this much mass?
\item 
When does turbulence break bits off this turbine blade?
\end{itemize}

\end{slide}

\begin{slide}
\slidetitle{What's hard about these GRID Problems?}

These are all computationally expensive, and may even require large amounts of storage
for intermediate stages (or rely on large amounts of telemmetry data). They may benefit
from enlisting computers and people from many places in many organisations (distributed
virtual information societies, formed on an ad hoc basis to solve urgent, or important
problems).

The GRID is to this what the Web is to sharing documents (in fact, the web is just a
component of the GRID).
\end{slide}


\begin{slide}
\slidetitle{So you want to use {\em MY} computer?}

So there are lots of peer2peer systems out there

(Yes, LOTS)
napster, gnutella, kazaa, morpheus, fastraqck, directconnect, edonkey, freenet

But these all hjust do file sharing.

Then there's: SETI@home....versus real work:-)

What do we have in the Open Source world?

Well, right now, we have {\tt ssh}. While this is ok for closed communities
it is just that: it relies on a flat user id space, and a single accountign domain.

What about sharing CPU cycles across multiple administrative domains?

It's a hard problem, entailing, authorisation, access control, authentication, accounting, 
and so far we've only got as far as the letter 'A' :-)

\end{slide}

\begin{slide}

\slidetitle{Problem definition}

One size doesn't fit all
e.g. PPARC problems different from NERC, BBSRC etc

10 Teraflop machines versus 1 million Megaflop SETI@HOme PCs

Brittle, High Cost, High Availability v.  Highly Organised Tolerance

Monopoly, verus broker/bourse/market organisation

Guiding principal: KISS
\end{slide}

\begin{slide}
\slidetitle{Desired Properties}

Protection of existing resources

Incentive to offer resources to other organisations

``Guarantees'' that if I pay for resources, I get them
\end{slide}

\begin{slide}

\slidetitle{System Components}

Pace: OGSA - define these in terms of WSDL/Grid Services! TBD!
(Think: Schedule factories etc)

\begin{tabbing}
API \=  \\
\>	job description \\
\>	user interfaces \= \\
\>	\>	Push versus Pull \\
\>	\>	exceptions \\
\>	\>	re-negotiation \\
Co-allocation \\
\>	group naming \\
\>	membership management \\
\>	application layer multicast \\
\>	VPNs/MBNG \\
Accounting \\
\end{tabbing}

\end{slide}

\begin{slide}

\slidetitle{More System Components}

\begin{tabbing}
Schedulers \= \\
\>	Turing's Halting Problem reminder! \\
\>	CPU schedulers \= \\
\> \>		pre-emption \\
\>\>		constraints\\
\>\>		priority\\
\>\>		elastic\\
\>\>		heuristics \\
etc (see pp 291 on in \\
{\tt ftp://cs.ucl.ac.uk/darpa/ods.ps.Z} \\
\end{tabbing}
\end{slide}
\begin{slide}

\slidetitle{Yet More System Components - IDEA!!}

Maybe system schedulers could be like network schedulers? 

\begin{tabbing}
Network Schedulers \= \\
	\> FCFS \\
	\> Int-serv - WFQ \\
	\> Diff-serv - CBQ \= \\
		\> \>	Priority \\
		\> \>DRR \\
		\>\>Pragmatic: CAR etc \\
\end{tabbing}

Has nice property that we think of process as
throughput and latency - other properties (locality to data or
I/O, also natural).

Has undesirable property that one can schedule for other
resources (memory) - perhaps these really should be 
constraints only though, rather than parameters

\end{slide}

\begin{slide}
\slidetitle{Policy/Mechanism}

\begin{itemize}
\item
Economics - maybe a market is a way to do distributed management?

\begin{enumerate}
\item
List resourecs on a bourse. Users "bid"- run an online auctioning system (maybe blind
vickrey auction to avoid nasty games).

\item
Users choose which parameter (cpu, storage, i/o, network) - could be like different
commodity markets -

\item
Users are allocated tokens by funding agencies, or their institution.
\end{enumerate}
\end{itemize}

\end{slide}

\begin{slide}
\slidetitle{Policy/Mechanism continued}

\begin{itemize}
\item
Service Level agreements (SLAs):
\begin{enumerate}
\item
SLA's need to be announced (might include availability, including MTBF (e.g. windows is
typically 6.5 hours, linux 65 days etc)
\item
Need refund mechanism (like railtrack:-)
\item
Long term statistics published (like internet weather service, need GRID weather
service).
\end{enumerate}

\end{itemize}

\end{slide}

\begin{slide}
\slidetitle{Policy/Mechanism continued}

User can choose to pay spot or futures, or brokered price.

Need to worry about stability, of course. But scale of system can
help!

Markets in bundled services might emerge.

Need tarrif distribution mechanism (c.f. Grid event 
notification service is part of OGSA).

Need to think about CPU and memory and I/O Congestion
(and signaling - a bit like ECN in Networking!).

\end{slide}
\begin{slide}
\slidetitle{Conclusions to Part 1}

In a complex heteroegeneous system with many organisations, the only current model we
have for organisation is a market

It works for the Internet (a thoudand ISPs per country!)

It is highly optimised and robust, but built out of sloppy components (see work by John
Doyle at Caltech on control theoretic analysis of such systems, often biologivcally
inspired)

\end{slide}

\begin{slide}

\slidetitle{References on GRS}

EU DataGRID Refs:
see
{\tt http://web.datagrid.cnr.it/pls/portal30/GRID.RPT\_DATAGRID\_PAPERS.show}

especially
Integrating GRID tools to build a computing resource broker:
activities of DataGrid WP1, Authors M. Ruda et al

GGF Refs
see
{\tt http://www.cs.nwu.edu/~jms/sched-wg/}

\end{slide}

\begin{slide}
\slidetitle{Abstract for part II - MBNG}

Herding Cats, Mice and Elephants - Network resource implications for the Grid.

The GRID promises several novel traffic patterns, such as data from the large hadron
collider (elephants), distributed computation from genomics (mice) and general acess
grid traffic (mice). In this talk, we try to characterise these from 20,000 feet, and
discuss some of the resource management consequences for this compelx ecosystem.

\end{slide}

\begin{slide}
\slidetitle{Part II:- MBNG }
\slidesubtitle{History}

The Internet does not offer protection of one user from another.
(hence term ``best effort'').

If the net is overloaded, and there are some legitimate reasosn to give some users 
decent performance rather than othes, we would like to haev some mechanisms for this.

On a road system, this is like haeving the California "Car Pool Lane" or the London Bus
Lane.

In some cases, we need to - e.g. tele-surgery, etc, this is clear. In others (e.g. voice
over IP, video conference) it may be necessary too. In others, more "elastic" behaviour
(i.e. adaption and tolerance) may suffice.

In the past, we had a network based on ATM (Asynchronous Transfer Mode switches) which
could dynamcialyl be programmed (managed/configured) to  partition the network capacity
into such seperate chunks. 

Now we do not have this capaibility in the underlying transmission system, we have to
re-implement it in the Internet Protocol Layer.

MBNG is looking at how to do this using a technology called Differentiated Services and
MPLS, with help from a small company called Cisco...


\end{slide}

\begin{slide}
\slidetitle{Realities }
\slidesubtitle{Measurements}

But what we realyl want to know is "what are the real traffic patterns"
and what are the real requirements?

Right now, net traffic is mainly made up out of two types of traffic, known colloquially
as mice and elephants.

Mice are your typical web browser - small (<<14 ackets total excanged) and interactive,
but faitrly delay tolerant (most userd can stand about 1 second web download delay)

Elephants are your large downloads - FTP of a new Redhat release....many megabytes
(therefore thousands of packets) - these are very delay tolerant - we don't really care
if the rate or delay vary even by orders of magnitude during the download so long as the
FTP completes withi nsome broadly reasoanble timeframe.

Mice and Elephants co-exist quite nicely, as typically there are millions of mice, and
onyl a handful of elephants, and the collective behaviour of many mice looks pretty much
like an elephant (central limit theorem, or even statistical thermodynamics math can be
used to show this). The behaviour of many humans drivign the mice, and a few FTP servers
have well behaved long term stability due to a mix of luck, economics, network
structures and the design of the TCP congestion avoidance algorithms.

\end{slide}

\begin{slide}
\slidetitle{Win Win }
\slidesubtitle{Controls}
The GRID may be introducing  a third type which is a tad trickier to comprehend, which I
have termed ``cats'', after the faous quote about the difficulty of herding cats:-)

Cat's eat mice. They are not scared of elephants (note elephants are famously scared of
mice, which leads to some rather lame jokes ... ... ...)

Cat's are medium term, do need care and feeding (i.e. live on the edge, need low
latency) and come and go as they please.

Cat's are a luxury.

IMHO, the only way to accomodate cats is through {\em economics}. We have a mechanism
due to Kelly et all, called Congestion Pricing.

A Cat must pay its way. (finally)
\end{slide}

\begin{slide}
\slidetitle{Justice for Mice }

If the presence of a cat means that a mouse dies, or an elephant forgets, then the cat
must learn guilt. This is done thruugh
\begin{enumerate}
\item
Explicit Congestion Notification (a.k.a packet shadow pricing)
\item
ECN counting is doen by the edge devices.
\item
A Cat accrues an ECN Bill. It is sent to their project or their institute (or their
tutor:-)
\item
non payment of bills leads to being blocked for prowling, but ALSO for mice and elephant
like mimicry.
\end{enumerate}
\end{slide}

\begin{slide}
\slidetitle{Practicalities }
\slidesubtitle{To Do}
ECN needs deployment

ECN billing needs a AAA environment.

GRS is deploying such an environment.

Thus we have the pieces.
\end{slide}

\begin{slide}
\slidetitle{References on Network Traffic}

 "Herding Cats: Modelling the Internet Jon Crowcroft, Royal Society talk, Dec 1999. pub
in August 2000 issue of the Philosophical Transactions of the Royal Society, vol 358, number 1773 

See also
{\tt http://www.nlanr.net}

\end{slide}

\end{document}
