On Thu, Dec 16, 2010 at 9:43 AM, Matthias Leisi <matthias(_at_)leisi(_dot_)net>
(as
part of a length off-list discussion) wrote:
For the examples below, I constructed a "granularity response" as an A
record response with IPs in 254.0.0.0/8. The last nibble indicates the
"next granularity" which would need to be queried. A response in
127.0.0.0/8 is interpreted as a "data response". Note that this is
only illustrative at this point in time, maybe there are more
intelligent ways to construct responses.
A totally general way to represent the data at the current level as well as
the availability or nonavailablity of data in finer levels is as follows:
Queries are of the form
rangeprefix DASH length DOT listaddress
with no additional dots anywhere. A list is presumed to be under one
administrative domain. rangeprefix and length are both hexadecimal, length
is in bits, and is always two hexits. (if you serve responses for more than
256 bit queries, like if you're serving images from the Hubble or something,
you can make it longer.)
Responses are of the form
127.A.B.C, where A, B and C represent the three octets we have to work
with.
A indicates how many more bits finer we have to go to find out anything
more interesting. It is relative to the length specified inthe query. When
it is zero, any finer query may be NXDOMAIN. When it is non-zero, it
indicates how many more bits of rangeprefix are required to find out
anything interesting, that is, to flip a 0 confidence bit to a 1.
B is confidence, and is a mask over the bits of C which are data, so this
protocol can support 8 bits of data for each range.
How the confidence and data interact:
CONDIFENCE DATA MEANING
1 1 1 for this and all finer ranges
1 0 0 for this and all finer ranges
0 1 generally 1, 0 points may exist
0 0 generally 0, 1 points may exist
how to serve an image with this protocol:
given an image, such as this red-shift adjusted radio-telescope snapshot of
the Levine nebula:
0123456789abcdef
0++++++++++++++++
1++++++++++++++++
2++++++++++++++++
3+++252+++++252++
4+++5f5+++++5f5++
5+++252+++++252++
6++++++++++++++++
7++++++++++++++++
8++++++++22++++++
9+++++2555552++++
a++++35fffff53+++
b++++5f55555f5+++
c++++252+++252+++
d++++++++++++++++
e++++++++++++++++
f++++++++++++++++
where each pixel may an eight-bit brightness, but none of them are brighter
than 0x0f, and the zeroes are "+" to make it look better,
and a division of the field into two dimensions, with bits alternating from
each dimension -- odd bits vertical, even bits horizontal:
one bit:
0
1
two bits:
00 01
10 11
three bits:
000 010
001 001
100 110
101 111
four bits:
0000 0001 0100 0101
0010 0011 0110 0111
1000 1001 1100 1101
1010 1011 1110 1111
and so on, up to the eight bits of full resolution as available in the data;
the top level, or root, query for this range list server earns a response
indicating that there are no data points with brightness greater than 0x0f
anywhere, in general the majority of the remaining data are zeroes, and to
get a more definitive clue you'll have to use at least three bits:
-00.sampleimage.example => 127.3.240.0
(I initially thought it was four, but on closer inspection I found that at
the third bit of focus one finds that there are some regions without any
0x08 bits.)
below here, to avoid doing binary/decimal conversion, I'm going to mostly
talk about additional bits required, confidence, and data, without
converting them into a dotted quad.
here is the picture grouped at three bits of resolution:
0-03 2-03
01234567 89abcdef
0++++++++ ++++++++
1++++++++ ++++++++
2++++++++ ++++++++
3+++252++ +++252++
query 0-03 or 2-03 to get a response indicating:
one more bit of focus for new information
confidence: 0b11111000
data: 0b00000000
1-03 3-03
01234567 89abcdef
4+++5f5++ +++5f5++
5+++252++ +++252++
6++++++++ ++++++++
7++++++++ ++++++++
4-03 6-03
01234567 89abcdef
8++++++++ 22++++++
9+++++255 5552++++
a++++35ff fff53+++
b++++5f55 555f5+++
query 1-03, 3-03, 4-03 or 6-03 to get a response indicating:
one more bit of focus for new information
confidence: 0b11110000 (there are still f points)
data: 0b00000000
5-03 7-03
01234567 89abcdef
c++++252+ ++252+++
d++++++++ ++++++++
e++++++++ ++++++++
f++++++++ ++++++++
querying for either of these will give us confidence on a zero for the 0x8
bit in the data, and notification that we would find out something else with
one more bit of focus.
These are the blocks at four bits of resolution:
0123 4567 89ab cdef
0++++ ++++ ++++ ++++
1++++ ++++ ++++ ++++
2++++ ++++ ++++ ++++
3+++2 52++ +++2 52++
4+++5 f5++ +++5 f5++
5+++2 52++ +++2 52++
6++++ ++++ ++++ ++++
7++++ ++++ ++++ ++++
8++++ ++++ 22++ ++++
9++++ +255 5552 ++++
a++++ 35ff fff5 3+++
b++++ 5f55 555f 5+++
c++++ 252+ ++25 2+++
d++++ ++++ ++++ ++++
e++++ ++++ ++++ ++++
f++++ ++++ ++++ ++++
at a four-bit granularity, we can get several different responses.
A query for the lower left-hand corner at four bits would get a reponse
stating that every point is zero and no further info is available:
a-04.sampleimage.example => 127.0.255.0
Also for the one above that:
8-04.sampleimage.example => 127.0.255.0
The one to the right of the lower left hand corner will differentiate at the
fifth bit, but no point in it is greater than 7, so we can get another
confidence bit.
The bottom right hand corner has only one bit set in its data, so
f-04.sampleimage.example => 127.1.253.0
tells us that there is a 0x02 bit set somewhere in there, but mostly the
data in that range is zeroes.
And so on.
_______________________________________________
Asrg mailing list
Asrg(_at_)irtf(_dot_)org
http://www.irtf.org/mailman/listinfo/asrg