On Wednesday, January 17, 2007 Serguei Osokine wrote:
> ...it looks like the response path area becomes a circle built
> on the line connecting requestor and responder - this line actually
> becomes its diameter. So the area involved in the single-response
> broadcasts is 1/4 of the area covered by the request at the moment
> when it reaches the responder.
I don't know what I was thinking. It is an ellipse, not a
circle - with the requestor and the responder at its foci:
http://mathworld.wolfram.com/Ellipse.html
- so at its widest point the trace width is about d*sqrt(2N+1),
where d is the hop distance, and N - the number of hops between
the requestor and the responder. This is about sqrt(N/2) less
than what I was saying about the circle. At 10 hops the response
trace width is about 4.5 hop lengths, at 50 hops - about 10 hop
lengths, and at 100 hops - about 14 hop lengths, forming a nice
elongated trail that does grow with the number of hops, but as
sqrt(N).
So the area of the single-response trace (and the corresponding
cumulative network traffic) is smaller, too: at 10 hops it is about
11% of the request coverage area, at 50 hops - about 5%, and at 100
hops (assuming that this is a realistic scenario in the first place)
- only 3.5% of the area covered by the request. So the more hops
there are, the more targeted does the response become, wasting less
bandwidth relative to the request traffic. I'm not sure if the
sqrt(N) trace width growth is really what is needed to compensate
for the loss probability growth at large hop counts, but there is
a fine-tuning parameter:
These numbers are all for case when the response is to be
retransmitted back by the 'layer' of hosts that were broadcasting
the corresponding-hop request. If the rebroadcast tolerance is
increased by allowing, say, "-+1 hop" response transmissions, then
the ellipse width will be increased, also increasing both the needed
cumulative network bandwidth and the response transmission redundancy.
Of course, this is all for a very simplified scenario of an infinite
plane with the uniformly distributed constant-bandwidth transmitters
(i.e. 100% bandwidth within the hop distance d, and 0% outside it).
So the estimates achieved with this method should be treated as
the order of magnitude estimates in the best case - but this might
still be useful.
Sorry for the confusion. I hope at least this time I got it
all right...
Best wishes -
S.Osokine.
17 Jan 2007.
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Serguei Osokine
Sent: Wednesday, January 17, 2007 1:30 PM
To: theory and practice of decentralized computer networks
Subject: RE: [p2p-hackers] Penumbra Wifi Network
On Wednesday, January 17, 2007 Serguei Osokine wrote:
> The response path trace covers the lense-shaped area that is widest
> midway between the requestor and the responder...
I just did some calculations, and as the number of hops keeps
growing, it looks like the response path area becomes a circle built
on the line connecting requestor and responder - this line actually
becomes its diameter. So the area involved in the single-response
broadcasts is 1/4 of the area covered by the request at the moment
when it reaches the responder.
This means two things: first, that the order of magnitude of
the cumulative network-wide request traffic and of the cumulative
network-wide single-response traffic is the same (though of course
if the request keeps going further, the ratio will be less than 1/4),
but second, that the response traffic in the proposed algorithm is
at least somewhat localized and does not have to reach every corner
of the universe.
Like I said - I'd prefer the response path to be narrower and
have a width that would be on the same order of magnitude as the
hop length, not as the hop length multiplied by the number of hops.
But these calculations can at least give us the upper bound for the
cumulative network traffic analysis. For example, if the response
happens to be the whole requested file, now we know which parts of
the network approximately will it reach, what will be the cumulative
bandwidth needed for its transmission, and how many nodes will have
a chance to cache the file in the process.
As a matter of fact, it might even be a good thing that the
path width grows with a number of hops - it might offset the growth
of the loss probability as the number of hops increases. Basically,
the more is the number of hops that have to be traversed by the
response, and the higher is the resulting probability of loss, the
higher is also the number of nodes doing the redundant transmission
on every hop. Maybe wishing for a constant-width path was not such
a good idea, after all...
Best wishes -
S.Osokine.
17 Jan 2007.
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Serguei Osokine
Sent: Wednesday, January 17, 2007 10:57 AM
To: theory and practice of decentralized computer networks
Subject: RE: [p2p-hackers] Penumbra Wifi Network
On Wednesday, January 17, 2007 Andy Green wrote:
> This idea that you might be able to hear a station but not talk
> back to it is behind the total lack of acknowledges, that and the
> fact an acknowledge from one station has little meaning when you
> broadcast to many. But the requests from the guy that is unable
> to talk back directly can find their way back to the transmitter
> via other stations.
Right. So it sounds like the basic request-response mechanism
has to be developed first, and then we have to decide how the more
complicated things might be built on top of it.
The request sounds relatively simple. Gnutella might be a good
guide. Every request has a unique ID. You hear it for the first time
- you decrease its TTL, increase hop number, and rebroadcast it. You
hear it again - you ignore it.
Responses are trickier. My first guess is also a Gnutella
derivative: responses have the same ID as the request, and are to
be rebroadcast only by the the nodes that potentially could be the
originators of the appropriate-hop request. This is easier to draw
than to explain, but here is an example: let's say that the response
is coming from the node that is two hops away from the requestor.
The response node broadcasts it to everyone around it, but the
only nodes that should rebroadcast it are the nodes that have sent
the second-hop request broadcast. Okay, let's draw this, after all:
Say, the nodes are in the square grid and the transmission distance
is 2.9 - this way, every transmission reaches 5x5 node square. So
here is the covered area after the first request hop:
. . . . .
. . . . .
. . x . .
. . . . .
. . . . . ('x' is the requestor).
After the second hop (24 transmissions), the coverage area will
look like this and include 'r' (the responder):
, , , , , , , , ,
, , , r , , , , ,
, , . . . . . , ,
, , . . . . . , ,
, , . . x . . , ,
, , . . . . . , ,
, , . . . . . , ,
, , , , , , , , ,
, , , , , , , , ,
So the respoder sends the response that reaches 24 nodes around
it, but this response basically says: "this is sent in response to the
request A with hop count of two. Rebroadcast it only if you are the
node who has sent this request with this hop count". These would be
only the nodes marked with dot '.' in the picture, so the first hop
of the response will be forwarded by 'dotted' nodes within the one-
hop broadcast distance from 'r':
, , , , , , , , ,
, , , r , , , , ,
, , o o o o . , ,
, , o o o o . , ,
, , . . x . . , ,
, , . . . . . , ,
, , . . . . . , ,
, , , , , , , , ,
, , , , , , , , ,
- these eight nodes (marked as 'o') rebroadcast the response, and
this time, it reaches the original requestor 'x'.
This is the basic idea. In a multi-hop case the same thing
happens, except that the response hop count gets decreased further
and further as it gets rebroadcast, and the nodes from the previous
request hop circles rebroadcast it one hop closer to the requestor.
Of course, just as it is the case with the requests, every node
should rebroadcast a particular response only once - so in case there
are multiple responder nodes, their responses should be unique, and
the responder should include a unique response ID into the response
in addition to the request ID. Request ID is used to backtrace the
request path, and the response ID - to make sure that multiple
responses are correctly rebroadcast back and not ignored.
The response path trace covers the lense-shaped area that is
widest midway between the requestor and the responder, and narrows
down closer to them. This is not ideal, because I'd prefer the
response path with a constant width (determined by the need to have
redundant transmitters due to the lossiness) - but I could not come
up with a simple way to do so. Maybe someone can think of something.
A variation of this could include -+1 hop tolerance on the
response rebroadcasts - if you've broadcast the hop 4 request, maybe
you should rebroadcast the responses that are coming with hops 3 and
5 recorded in them, too. This might increase traffic, but also
increase the response delivery reliability. Let's say the responder
is on the very edge of the hop N coverage area, and only one node
reaches it on hop N (though multiple nodes - on the hop N+1). So
if the response rebroiadcast is done by this single node, there is
a high probability of loss; but if the nodes that have just broadcast
hop N+1 request are allowed to rebroadcast the 'hop N' response (the
response that was generated for the hop N request), the chances of
the successful response delivery can dramatically increase.
Intuitevely, this -+1 variation is especially important near
the path end, where the response path trace is at its narrowest -
and it is essentially an attempt to make the response path width
more uniform. Hopefully there are also other, better and more
reliable ways to achieve that goal, but I haven't thought much
about it yet - even in its simplest form, this network should be
capable of doing of at least some routing.
Now the question is, what is the cumulative traffic capacity
of such a network, and can it realistically send the content, too,
and not just requests and responses?
Best wishes -
S.Osokine.
17 Jan 2007.
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Andy Green
Sent: Wednesday, January 17, 2007 1:31 AM
To: theory and practice of decentralized computer networks
Subject: Re: [p2p-hackers] Penumbra Wifi Network
coderman wrote:
Hi Coderman -
Thanks for your big set of ideas!
> a quick overview, since i don't have time (yet) for a more detailed reply:
> there are a plethora of ad-hoc routing protocols [0] and some are well
> suited towards this kind of wireless mesh. my particular favorite is
> Link Quality Source Routing [1] which supports multiple radios nicely.
> this is what you'll need to do your "rebroadcast" efficiently.
"Link Quality Source Routing" does sound pretty cool, but in a system
where there is zero identity in the nodes, I don't know how traditional
concepts of routing can apply. Instead of an active transmission-led
routing system, where the transmitter makes decisions to direct packets
at particular receivers, in this concept the only active decision is if
a receiver will rebroadcast. It can't target its broadcast.
> some comments about the broadcasts: you'll want to consider encoding
> rate and transmit power in the xmit stack, one size fits all (that is,
> no differentiation between packet types and encoding) will be
> inefficient, and you'll get better behavior if you can tune this
> accordingly. rate control is actually pretty complicated in practice,
> while it may seem seductively easy in theory. [2]
Yes it is a good point, but again the situation is unusual for that.
One might reduce the transmit power or decrease the transmission rate to
optimize a link to a particular node, but there are no particular nodes,
they are all "spartacus". I guess it can keep stats on re-requested
packets, or look at the tx signal strength used to make the request, and
figure out that there is a distant client it could service by dropping
the rate temporarily, but that has ramifications too.
> along similar lines, packet size (including fragmentation, if needed)
> will greatly affect the receive-ability of your broadcasts by multiple
> clients, since longer payloads are more likely to experience
> collision, thus forcing back-off and retransmission. in short, it
> might work best to have the signalling/control/discovery traffic in
> small packets, sent at the lowest bitrate and max power, while the
> data traffic uses a different (more flexible) rate and fragmentation
> layer. (you might be doing this already, but i did not see details on
> the wiki) antenna selection may also be useful now that wireless
> devices are including MIMO and multiple antennas more frequently.
Yes my current idea is this kind of granularity
- frame-sized packets 256..512 bytes that actually get transmitted
- 4K blocks of packets (individually signed)
- 1MByte "chunks" of 4K blocks (which form the "files" in the caching
system)
Each packet is marked up with the hash of the upload to which it belongs
> [just to emphasize this point, the broadcast nature of wireless makes
> it ideal for resource discovery requests, since it is a true
> broadcast, and not an emulated one implemented via iterative unicast
> or forwarding, etc. in particular i've tested small periodic payloads
> (<128 bytes) at 1M rate and 1W xmit to great effect, literally many
> tens of miles diameter. you shouldn't need such a high degree source,
> but this does show just how wide a unidirectional path can be when the
> wireless layer is tuned for distance]
Sounds like you have been there :-) This idea that you might be able to
hear a station but not talk back to it is behind the total lack of
acknowledges, that and the fact an acknowledge from one station has
little meaning when you broadcast to many. But the requests from the
guy that is unable to talk back directly can find their way back to the
transmitter via other stations.
>> The state at the moment is I am working on two Linux wifi drivers, for
>> zd1211rw and ipw3945 to add the Penumbra packet transfer stuff as a
>> proof of concept, and that the usermode daemon SSL and upload stuff is
>> done and under GPL. So it is quite early days but there is progress.
>
> i'd highly recommend looking at the madwifi [3] driver as well, and
> fortunately it makes this kind of extension very easy. there is also
> a reverse engineering ath-driver HAL [4] for even more non-standard
> tweaking of radio parameters if you want to _really_ avoid contention
> in the usual 2.4Ghz bands by giving a finger to the FCC :P
I don't want to make any regulatory trouble. It should be fine just
using the ISM bands at normal powers using standard gear. I chose my
two POC drivers because I have the hardware :-) Assuming it can be made
to work I will document what needs to be done and hopefully someone who
works on the driver can consider to add it.
> there is even an existing program that uses control frames in 802.11
> for covert channel transmissions [5] that may be useful.
That is really cool, but it needs the packet injection capability in the
driver. Which admittedly is currently more available than my protocol
support in drivers. I will have a closer look at it.
> last but not least, the latest madwifi drivers support virtual devices
> [6], so you can have a client association, a master mode AP device,
> and a raw monitor device all sharing the same physical radio hardware,
> which may eliminate the need for driver tweaks when using Atheros
> devices.
Yes I heard also that the Devicescape stack will support this, and I saw
in the ipw3945 driver there is hardware support but not yet software
support in the driver.
> that way, although if you need to use persistent identities for secure
> routing, an opportunistically shared RSA identity key (for
> routing/control) could be used while keeping the single use RSA keys
> (perhaps in a mode like ephemeral diffie hellman, with the transient
> keys signed by the long lived identity key).
The problem here is that any kind of long-lived identity can be used to
destroy the privacy of what the node is doing. What might not violate
this privacy aspect is to have random "session keys" that are changed
every minute or so by every router, and use that for the purposes of
trying to work out what rate and tx power to use to service requests
that came with that router as the last hop.
-Andy
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
