TOKEN PASSING LOAD LIMITING --------------------------- Each node has a maximum limit N on the number of running requests.
Each node has a bucket for each of its peers, containing tokens. A token is simply a UID; a counter which is incremented each time we create a new token. The token is effectively a permit to send a request. A request will include a token. If the token isn't recognized by the node it sends back a specialized message indicating no such token. Otherwise the node is required to accept it unless there is a serious problem (such as looped requests). It then removes the token in question from that node's allocation. Using UIDs for tokens prevents any race issues that might otherwise happen. When nodes are first added, they are given some tokens. Tit-for-tat can be implemented later on by scaling the maximum size of the token bucket and biasing the decision on whom to give tokens to. When a request completes, a new token is created an allocated to a node. There are two obvious strategies for adding tokens: - Reward requestors by adding to the least full bucket. - Reward non-requestors by adding to the most full non-full bucket. I prefer the latter option (it does impose some limits though; there need to be enough tokens initially that a node not using its tokens doesn't prevent everyone from requesting). Obviously we would use a random tiebreaker in the case that two nodes have the same number of tokens. What else remains? How do we integrate this with routing, that is the remaining question. All we have to do here is keep requests in some sort of pending state, and when we get a token from a node, send the request most specialized for that node. This means we will have some misrouting, but not much, and nodes which send us few tokens will get only the requests closest to their specializations. We can perhaps improve on this by "simulated queueing", but I don't see why the basic mechanism shouldn't work, albeit at a slight latency cost. I'm rather inclined to implement this without waiting for simulations. Any objections? -------------- 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/devl/attachments/20060927/bddeea2e/attachment.pgp>
