Looks good to me, but we need to be careful about weird cases (parents reconnecting through their own children etc).
Ian. On 5 Sep 2005, at 20:40, Matthew Toseland wrote: > So, a little more concrete: > > The subscribe tree persists on the network. > The insert chain does not. > > Messages: > PublishData > SubscribeData > SubscribeRequest > ResubscribeRequest > SubscribeRestarted > SubscribeSucceededNewRoot > SubscribeSucceeded > > So, we push a PublishData, it is routed. Until it reaches the tree, at > which point it is broadcast (as a SubscribeData). If it reaches the > root, > it is only routed down the tree; if it reaches a branch node, it > forwards > it up the tree as well. > > When we receive a SubscribeRequest: > - If we have the stream, we send a SubscribeSucceeded, and add the > subscriber node to the list of nodes subscribing to the stream. > - If we have less than 32 streams, we route the request. Otherwise we > send a RejectOverload error back to the source. > - We use the backtracking algorithm described earlier to determine > whether we are the root. Each SubscribeRequest includes the location > of the last nearest node. If we are closer to the key than the last > nearest node, we reset this field to our location. If not, we > decrement HTL. This may mean we have to revisit the probabilistic > decrement probabilities; certainly max HTL should be low, say 10. If > we run out of HTL, and we are the closest node, we become the > root. We > send back a SubscribeSucceededNewRoot. If not we send back a > DataNotFound to indicate that we can't find the stream. Similarly if > we get a DataNotFound, and we are the closest node to the key, we > become the root. SubscribeSucceededNewRoot is forwarded back to the > originator just as SubscribeSucceeded is. > > > When we lose our parent node (uplink node, the node through whom we > are > subscribed), or when a new node is added, or when a swap completes > successfully, or when our parent node is restarted (new boot ID), we > restart the subscription. This means: > - Send out a SubscribeRestarted. > - Send out a ResubscribeRequest. This is routed as a SubscribeRequest, > but has an ID on it equal to that on the SubscribeRestarted. Also it > includes our location, which is no longer the best location so far, > but the must-beat location. We also include the best location so > far, > (which also initially is set to our location), so that HTL works > normally. > > When we receive a ResubscribeRequest: > - If we have the key, and our location is closer to the target key > than > the must-beat location, we send a SubscribeSucceeded and add the > node > to the list of subscribers for that key. > - If we don't have the stream, we route it normally as a > SubscribeRequest. Even if we are closer to the key than the must- > beat > location. If we become the root, we check whether we are closer > to the > key than the must-beat location, and if so, succeed; if not, fail. > - If we have the key, and have recently had a SubscribeRestarted with > the same ID, we route it as a SubscribeRequest, except that we > pretend > the stream doesn't exist. > > When a node reconnects, and has a new boot ID, we remove it from any > streams to which it was subscribed. It can then send SubscribeRequests > and ResubscribeRequests as necessary. > > > > On Mon, Sep 05, 2005 at 08:13:03PM +0100, Matthew Toseland wrote: > >> Ian and I have reached the following principle conclusions: >> >> 1. We will use the backtracking mechanism outlined in a previous >> email. >> This will not result in a reduction of anonymity, as if we recieve a >> request with location equal to that of the sender, we know that a) >> the >> node was closer to the target than the previous node, or b) the >> node was >> the originator. This is an acceptable level of plausible deniability >> although it is not enough against correlation attacks (but not >> much is). >> >> 2. A subscribe request will succeed when it reaches any node, even if >> that node is further away from the target location than the start >> node, >> if the node has the stream we are searching for. >> >> 3. A resubscribe request carries the location of the node which is >> resubscribing, and an ID. We will ONLY subscribe through a node if >> that >> chain gets us, directly or indirectly, closer to the target key >> than the >> originator was. >> >> 4. When we lose our parent link, when a node is added, when a swap >> completes successfully etc, we reroute. First we send out a >> SwapRestarted message to all our dependants, who forward it to all >> their >> dependants etc. This message contains an ID. >> >> 5. If we are on a given stream, and we get a resubscribe request >> with ID >> equal to the ID on a SwapRestarted recently forwarded to us, we >> forward >> the request. This can of course happen out of order. If we can't >> forward >> it any further, we become the root. >> >> Notes: >> Resubscribe request != Subscribe request. Because a subscribe request >> will stop when it reaches ANY node with the stream, whereas a >> resubscribe request only stops when it reaches one closer to the >> stream >> key than the sender. >> -- >> Matthew J Toseland - toad at amphibian.dyndns.org >> Freenet Project Official Codemonkey - http://freenetproject.org/ >> ICTHUS - Nothing is impossible. Our Boss says so. >> > > > > >> _______________________________________________ >> Tech mailing list >> Tech at freenetproject.org >> http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/tech >> > > -- > Matthew J Toseland - toad at amphibian.dyndns.org > Freenet Project Official Codemonkey - http://freenetproject.org/ > ICTHUS - Nothing is impossible. Our Boss says so. >
