Re: Other Efforts

andrew meggs (
Tue, 10 Jun 1997 23:31:33 -0400

At 8:50 PM -0400 6/10/97, wrote:
>I think he meant something along the lines of the method to the madness of
>handing out the keys.. is it purely random? is it sequential from 0 to
>(large number here)? sequential wouldn't be very good, and totally
>random probably wouldn't be terribly good either.. i'd guess it was
>splitting the keyspace into n chunks and working away from those points
>in either direction.. but i could be wrong.

First a disclaimer: Although I did some deschall development work, I have
no experience with or knowledge of the server's operation other than the
fact that it assigns keys to the clients I've worked on, so all of this is
my speculation only and is neither an official statement or a violation of
any NDA's. But here's how I'd set it up...

Set up an array of buckets, numbered from 55 (for 2^55 key pairs, or 2^56
keys -- the entire key space) down to 22 (the lowest block that gets handed
out is 2^22 pairs). They all start out initially empty except for slot 55,
which conatins a single block representing the entire keyspace.

function get_block( N: integer )
// returns a block of 2^N key pairs, 22 <= N <= 56
if bucket N has a block in it, then:
take a block out of bucket N
return the block
else if N < 55 then:
let b = get_block( N+1 ); // a recursive call
split b into two blocks of size 2^N
randomly choose one of the halves of b,
and put it into bucket N, which is empty
return the other half of b
while (N > 22) do
N := N - 1
if bucket N has a block in it, remove one and return it
end while loop
Uh oh! Go page Rocke, because if we get here we've run out
of blocks to assign but haven't found the key yet!

A system like this would let the server manage the entire handing out of
key blocks, and, aside from any expired blocks that got stuck back into
buckets for reassignment, it would only have to keep track of a maximum of
34 blocks (one of each size) at a time.

Andrew Meggs, content provider Antennahead Industries, Inc.
<> <>