[RC5] d.net

Jason Untulis untulis at netgate.net
Fri Jul 17 15:45:53 EDT 1998

Joe Zbiciak <j-zbiciak1 at ti.com> wrote:

: 'GMH13 at aol.com' said previously:
: | 4)  During the past week someone on this list pointed out that when you
: | request a 2^31 block there are several different combinations you might
: | receive, making choosing a buffering size difficult. Would it be possible to
: | setup the proxies such that they have four buffers (2^28, 2^29, 2^30, and
: | 2^31)? 
: On its face, this seems like a good idea, and it might be made to work.
: There are a couple problems though.
: First, there are 8 valid block sizes currently, if I understand things
: correctly:
:  Block Size     Number of 2^28 blocks
:  ----------     ---------------------
:      2^28                1
:      2^29                2
:    3*2^28                3
:      2^30                4
:    5*2^28                5
:    3*2^29                6
:    7*2^28                7
:      2^31                8
: So, you'd actually need 8 lists.  You'd also still need the clients to
: accept odd-sized blocks in larger blocks are simply unavailable.  (See
: explanation below.)

You still only need four because the four odd sizes are only created
because the proxy wants to hand out the "partial" block created when a
<2^31 block is created. With four queues for the four different
requestable sizes, none of these funky sized "partials" ever need to be

: A stagnation problem occurs in this scheme, though, when the vast
: majority of clients request 2^31 blocks, since these will move quickly
: through the proxies, whereas the smaller-sized blocks will tend to
: collect.  This works against the FIFO buffering the proxies provide.
: In the limit, stagnation could cause the smaller sized block lists
: to grow without bound.

Not the way I interpreted this. When the proxy broke up a 2^31 into
smaller blocks, those would be added to the appropriate size queue, making
them available to later clients who request those size blocks. Thus, the
2nd 2^28 request would get some of the 2^28 subblocks from the original
2^31 block. At most there would be 7*2^28, 3*2^29 and a 2^30 block
stagnant and even that is highly unlikely. Since practice is to grab
multiple blocks at a time (I'm not likely to grab just one 2^28 block,
I'll want a few), it's unlikely that any part of any queue would
sit for very long. 

If you were exceptionally paranoid, you could have the breaking operation
cascade. If a client wanted a 2^28 block and all that was available was
2^31 blocks, a 2^31 block could be broken into 2 2^30 blocks. One of those
2^30 could br broken into blocks 2 2^29 blocks, etc. down to the size
requested. That would leave only one block per queue in the maximum.

: I believe the real fix is to express buffer sizes in equivalent numbers
: of 2^28 blocks, so that the total workload for a buffer of size N is
: constant, regardless of whether the blocks are 2^31 or 2^28 or
: something inbetween.  That way, if I say "buffer 200 blocks, preferring
: 2^31 blocks", I could either get 200 2^28 blocks or 25 2^31 blocks or
: some combination in between.  You will still keep the block-size
: preference setting so that you could place an upper bound on the
: granularity of work attempted at any given time.

I agree with your suggestion, with the substitution of smallest
granularity of work defined for the project rather than fixing on the 2^28
size. This would allow whatever size is useful for other projects. (Not
that they'll be any other projects at the rate v3 is being
developed... 8-) )
Jason Untulis, Ravenous Media Consumer    /\    /        untulis at netgate.net
<http://www.netgate.net/~untulis/>    \  /==\  /          untulis at netcom.com
protected by spamgard[tm]              \/v2.4\/  untulis at leland.stanford.edu
PGP key soon            (C) <http://www.netgate.net/~untulis/copyright.html>

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list