[Note: This file contains some old mail exchanged about the design and
implementation of Frisbee.  For a much better discussion, read our
Usenix 2003 paper, available on the Web or in the testbed source tree at
doc/papers/frisbee-usenix03.pdf ]

------------------------------------------------
From stoller Mon Mar 18 07:17:13 -0800 2002
Date: Mon, 18 Mar 2002 07:17:13 -0800
From: Leigh Stoller <stoller@fast.cs.utah.edu>
To: Jay Lepreau <lepreau@fast.cs.utah.edu>
Cc: barb@fast.cs.utah.edu
Subject: Re: Need a summary of the Frisbee algorithm
In-Reply-To: <200203181215.FAA11167@fast.cs.utah.edu>


> From: Jay Lepreau <lepreau@fast.cs.utah.edu>
> Subject: Need a summary of the Frisbee algorithm
> Date: Mon, 18 Mar 2002 05:15:47 -0700 (MST)
> 
> I need this today; tomorrow at the latest.
> Chad had written one once; where is it?
> It probably is mostly still true assuming Leigh
> left it pretty much the same, whuch I thought
> he said he did.

I changed the algorithm quite a bit actually, to make it less synchronous
with respect to the server. The toplevel view is still the same, which is
why we can still call it Frisbee; the server flings blocks out and clients
catch them. If its a block it needs, it saves it and adds to its list of
blocks to unzip to disk.

The big change is that clients connect to the server to get the number of
blocks in the image, but after that the server no longer cares much about
them, except to read in requests for blocks (or subblocks) that clients
need.

The server is multithreaded. One thread simply reads those requests and
adds them to a worklist. The other thread reads the worklist, reads the
stuff out of the image file, and sends the blocks (or subblocks) out. A
"block" is one of our 1meg chunks, and a subblock is a range within one of
the 1 meg chunks (a client can request a missing subblock). Thats all the
server does. Very simple.

The clients are also multithreaded. One thread takes in blocks and
subblocks and adds them to an internal cache. The other thread looks for
completed blocks in that cache, and unzips them to disk. By being
multithreaded, the receiver thread gets control (can take in more blocks)
when the disk writer thread blocks in the kernel on a disk write.

Okay, so the main algorithm is contained in the block reader thread in the
client. It maintains a bitmap of blocks (1 meg chunks) it needs. At startup
it randomizes the list (using noise), and then doles out those block
requests to the server. For each block it is working on, it maintains a
bitmap of 1K chunks it needs. Of course, since multiple clients are all
requesting blocks which are being multicast out, it could be working on
lots of different blocks at once; *whenever* a block arrives that it has
not seen before, it starts working on it, up to a limit of 32 (or perhaps
64) in progress at once.  To avoid meltdown, each individual client
requests no more than 2 blocks ahead; if the total number of blocks in
progress in less <= 2, it will send in a request for another one from its
randomized list. Now, for each block in progress, it maintains a bitmap of
1K chunks it needs. If no block or subblock (remember, a subblock is a
contig range of 1K buffers) arrives after 90ms (timeout on socket read), it
assumes that the something was lost; it looks at its bitmaps and requests
more data (either subblock ranges or blocks). Subranges are not lost very
often of course (all the UDP packets typically make it).

The goal of this algorithm is to keep the diskwriter thread busy *all* the
time; each time around the loop, there should be a completed block for it
to to unzip/write. Since the unzip/write operates at a fraction of the
speed that the server/network can get blocks to it, this turns out to be
pretty easy to do. The hard part is keeping the server from melting down
the network (or itself) by sending them too fast! Send too fast and UDP
packets get toasted and the server thrashes. 

As it turns out, I managed to accomplish this. Other than startup delay,
the writer thread is never idle, and the server can manage many concurrent
frisbee daemons doling out different images. Well, I've tested it out to
about 6. Each one takes about 4% CPU at steady state. 

Is this enough text for you?
Lbs

From stoller Mon Mar 18 10:43:31 -0800 2002
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <15510.13651.903626.13004@stoller.casco.net>
Date: Mon, 18 Mar 2002 10:43:31 -0800
From: Leigh Stoller <stoller@fast.cs.utah.edu>
To: Jay Lepreau <lepreau@cs.utah.edu>
Cc: barb@fast.cs.utah.edu
Subject: Re: Need a summary of the Frisbee algorithm 
In-Reply-To: <200203181827.LAA19142@fast.cs.utah.edu>
References: <200203181827.LAA19142@fast.cs.utah.edu>
X-Mailer: VM 6.92 under Emacs 20.7.1

> From: Jay Lepreau <lepreau@cs.utah.edu>
> Subject: Re: Need a summary of the Frisbee algorithm 
> Date: Mon, 18 Mar 2002 11:27:00 MST
> 
> Questions:
> -From what you say about randomizing requests, it doesn't
> sound like you do anything to keep requests more-or-less
> sequentially ordered.  Which seems like it would hurt the
> disk writer, as it would have to seek around.
> And randomizing the list means that the clients are
> all asking for different things, which means the
> server will seek around a lot, too.

True, but the server is sending the chunks out at a fairly relaxed rate,
and the chunks are large (1MB), so the seeking around on the server is not
so bad (2ms or so per seek, 300 of them in the full image, and the buffer
cache read ahead will help as well).

On the write side, the extra 2ms of seek time per chunk is hardly something
to worry about given it has nothing better to do. So, thats 2/3 of a second
in 180 seconds?

The point of randomization is to prevent all the clients from getting into
lockstep mode. Otherwise, they would all (and did) eventually sync with
each other, and they would all finish at the same time; the time at which
the slowest (last to start) finished. 

> -How do you pace the rate at which the server sends?
> > The hard part is keeping the server from melting down
> > the network (or itself) by sending them too fast!

On the server side its rather simple; a 10000us microsleep! To reiterate,
the bottleneck is on the client side, unzipping and writing, and so the
pace at which we send the data is not critical. Fast, but not too fast.

Oh, on the client side I employ a simple linear backoff function to keep
the clients from overloading the server with requests; Instead of sending
the same request every 90ms, back off slowly in case the server already has
a bunch of requests it is working on.

Lbs

From: "David G. Andersen" <danderse@cs.utah.edu>
To: Leigh Stoller <stoller@flux.utah.edu>
Subject: Re: Refs on Reliable bulk data distrib (relevant to Frisbee)
Date: Thu, 19 Sep 2002 16:32:57 -0600

Leigh Stoller just mooed:
> 
> 1. The "I need these blocks" request format is stupid. I naively thought
>    that packet loss would be rare, so nodes would not be requesting missing
>    blocks very often. Its a dumb start,length request which means that if I
>    am missing a bunch of scattered blocks in a 1MB chunk, I have to send a
>    request for each non contiguous range. Should be a simple bitmap
>    instead. Should be an easy change to client and server, and this would
>    reduce the amount of client to server traffic.
>
> 2. Slightly related is my point in the message below. The clients should be
>    listening for requests from the other clients so as not to flood the
>    server with dup requests. Note though that the server *does* coallesce
>    all the requests; if 10 clients request the same block it is sent just
>    once. Basically, if one client did not get a block, odds are none of the
>    clients got it! This change is a little more work cause it requires
>    some bookkeeping, but its not too big a deal. 

   yeah.  you're now encountering the standard multicast reliability
problem.  too bad kristin isn't still there. :-)  throw in a bit
of random backoff and snooping on requests and it should be OK.

> 3. Lastly, I have no decent rate controlling mechanism to prevent the
>    server from flooding the network. Its not so much that I am worried
>    about flooding the clients with blocks too fast, but that I can easily
>    flood the link to the cisco by blasting out udp packets. That causes
>    more packet drops and more requests and again I have a feedback loop. My
>    hacky solution was just to throttle back the sender with a constant
>    usleep until I came up with something. I'm not really sure what the
>    effect of this hack is though, but I am guessing that the strictly
>    constant (and conservative) output rate is not helping me any!

  hmm.  also researchby, but since the clients are mostly homogenous,
this shouldn't be too bad to solve.  could you keep a rate estimate of
the number of drops, and scale back the transmission rate by .9 or so
if it exceeds some thresshold, and then ramp it back up a bit over time?
(super aggressive tcp)

  -dave

From testbed-request  Fri May 10 12:34:34 2002
Message-ID: <15580.4790.185138.434691@stoller.casco.net>
Date: Fri, 10 May 2002 11:34:30 -0700
From: Leigh Stoller <stoller@fast.cs.utah.edu>
To: Testbed Project <testbed@fast.cs.utah.edu>
Cc: Jay Lepreau <lepreau@cs.utah.edu>
Subject: Frisbee and Multicast

Found this site: http://www.roads.lut.ac.uk/DS-Archive/MTP.html

Scanned a few papers, and found one that was interesting:

   http://www.cse.ucsc.edu/research/ccrg/publications/brian.icnp.ps.gz

Brian Neil Levine and J.J. Garcia-Luna-Aceves,``A Comparison of Known
Classes of Reliable Multicast Protocols,'' Master's Thesis, Computer
Engineering, University of California, Santa Cruz, CA 95064, June
1996. Or a shorter version to appear in Proc. International Conference
on Network Protocols (ICNP-96) October 1996.
http://www.cse.ucsc.edu/research/ccrg/publications/brian.icnp.ps.gz

I read the paper. Its an okay paper, but it hits the highpoints and is a
reasonable survey. I have no idea if ICNP-96 is a respectable conference.

Main points below. NOTE THE DIRECT QUOTATION! The thing to note about
it is that both versions of Frisbee (old/new) use a receiver-initiated
approach, although I think mine is more classically receiver-initiated
than Chad's. Mine is also less synchronous.

"There are two main classes of multicast protocols: sender-initiated
and receiver-initiated. In sender initiated, the sender maintains the
state of all receivers to whom it has sent data and from whom it is
expecting ACKs. Each sender's transmission or retransmission is
multicast to all receivers; for each packet that each receiver obtains
correctly, it sends a unicast ACK back to the sender. In contrast, in
the receiver initiated approach, each receiver informs the sender of
the information that is in error or missing; the sender multicasts all
packets, giving priority to retransmissions, and a reciever sends a
NACK when it detects an error or lost packet."

"The first comparative analysis of sender-initiated and
reciever-initiated reliable multicast protocols was presented in
[15,16]. This analysis showed that reciever-initiated protocols are
far more scalable than sender-initiated protocols because the maximum
throughput of sender-initiated protocols is dependent on the number of
recievers, while the maximum throughput of reciever-initiated
protocols is *independent* [my emphasis] of the number of recievers
(when the probability of lacket loss is low). However, as this paper
demonstrates, the reciever-initiated protocols to date cannot prevent
deadlock when they operate with finite memory."

It goes on to talk about ACK implosion of sender-initiated protocols
being a big problem. The issue of finite memory (at the sender) is not
really a problem for us since we are not doing general multicast bulk
transfer (say, delivering 100s of different files), but instead are
more constrained. We also do not buffer much data at the sender, but
instead read directly from the disk since the time to decompress and
write to the raw device at the receiver, is ultimately the bottleneck.
Besides, we depend on the buffer cache to do the caching at the
sender, although since we are reading randomly, we may not get much
benefit there. May not matter though.

They also talk about NACK implosion in receiver-based protocols, where a
lost packet results in a NACK from every receiver. One solution to this
problem is to multicast NACKs so that other receivers see them, and refrain
from sending their own NACK for a time (random amount). We might benefit
from this if we get to very large scale experiments (100s of nodes that
need disk reloading). My solution to this problem was a little different.
Receivers backoff when NACKS go unanswered (new data not received within a
set period of time). At the sender, I keep a time ordered list of packets
that need to be sent, and if a NACK arrives requesting data already on the
queue, I do not do anything cause the data is going to get sent soon.
However in the presence of lost NACKS (unlikely in the local area case),
the other solution they talk about is probably better. 

Then there are several pages of formulas which I prudently skipped
right over without looking at. Table 1 might be interesting though.

The ultimate conclusion is that tree based multicast is best ...

Lbs
-----------------------------------------------------------------
