Some changes are necessary due to the need to accomodate multiple senders on a given stream, and due to the need to deal with the fact that the sending node may be restarted, or the sender may send from a different node. As long as they still have the key, they should still be able to send. Furthermore there were some opportunities to simplify matters. So:
Freenet 0.7 Publish/Subscribe Specification ------------------------------------------- Overall Architecture: Multiple nodes subscribe to a given key. Their requests are routed, and coalesced, forming a tree. The root of the tree is the only node which has no parent. A node connects to another node only if it gets it closer to the target key, within the HTL - so the root is the node which is the closest to the target key; the root is the node which cannot find a closer node to the key within HTL. When we want to send data packets to the tree, we first subscribe to the tree. Then we send a PublishData to our parent (not to our children, even if we have some). It will normally be forwarded up to the root, which will decide whether it is a collision. If not, it is broadcast to all nodes in the tree and thereby all subscribers. Handling of errors remains similar to the previous spec. In particular, if we lose our uplink we may need to route our resubscribe request through one of our children; this must be handled correctly. Messages: PublishData (data injection) - UID (for collision avoidance), key, packet#, best seen location, data, htl SubscribeData (data broadcast) - key, packet#, data SubscribeRequest (subscribe in the first place) - key, htl, last seen packet #, best seen location, UID ResubscribeRequest (resubscribe after something broke) - key, htl, last seen packet #, must-beat location, best seen location, UID SubscribeRestarted (something broke) - key, resub UID (to match against ResubReq.UID) SubscribeSucceededNewRoot - key, UID SubscribeSucceeded - key, UID When we get 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 elsewhere 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 something changes (we are already subscribed): When we lose our parent node (uplink node, the node through whom we are subscribed) for a given key, 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 get 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. When we get a PublishData: - If we do not have the key, we return an error message. - If we have the key, and already have the packet, we return an FNPPublishSucceeded. - If we have the key, and have a packet with the same number but different contents, we return an FNPPublishCollision with a suggested next packet number. - If we are the root, and we do not have a packet of the same number, we can accept it and send an FNPPublishSucceeded. We will then broadcast the packet to all of the nodes subscribed to it through us. The tree nodes which receive the FNPPublishSucceeded will propagate it to their subtrees. -- Matthew J Toseland - toad at amphibian.dyndns.org Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20050921/f0ca1d48/attachment.pgp>
