I have given some thought to the next generation routing algorithm, and how to implement it efficiently.
the idea is to efficiently store information about each node's
response times for specific keys. The challenge is to store this
information efficiently, while allowing efficient response time
estimation for a given key with a given node.
My proposal is that we encapsulate this functionality in an
object called ResponseTimeEstimator. Each node in the routing
table would have its own ResponseTimeEstimator object.
The RTE's interface would look something like:
public class ResponseTimeEstimator {
public ResponseTimeEstimator(Key bias, int accuracy) {...}
public ResponseTimeEstimator(byte[] serialized) {...}
public void report(Key k, float time) {...}
public float guess(Key k) {...}
public byte[] serialize() {...}
}
as can be seen here, the accuracy of the RTE can be specified on
construction - along with an initial key that we think this node
specializes in (ie. this is set to the key of the request in
which this node was discovered and returned in the DataSource).
We also anticipate that we might want to pass these objects
between nodes so we provide serialization methods (assuming we
don't want to use Java's built-in serialization stuff).
internally, we represent the information with a set of
two-dimensional vectors, the more accuracy we want, the more
vectors we use. Clearly, the will be a trade-off between
accuracy, and cpu/memory use.
the two dimensions of each vector represent a key and a time.
initially the vectors will be set up with a bias towards the key
passed in the constructor. When a response time is reported for
a particular key, all of the vectors are moved closer to it
(assuming a two-dimensional plane in the key and the response
time), vectors which are further away, will move less (something
akin to a gravity-attraction equation can be used here). We
could also have a object-wide "sensitivity" setting which starts
high - and then gets lower as more data is collected.
when the object is asked for an estimate for particular key, it
looks at the two vectors closest to that key, draws a line
between them, and wherever that line crosses the key, that is the
estimated response time we return.
clearly this is a simple approach, and it's still needs to be
fleshed out more, for example, we may want to maintain two
vectors locked at the edge-keys (ie. key 1, and key 2^160) to
ensure that even if most of the vectors get bunched up, we will
still be able to provide estimates for all keys.
Now we should think about efficient ways, given a large set of
these RTE objects, to determine which object has the lowest
estimated response time for particular key. one approach would be
to maintain a global data structure which keeps track of which
node has the best estimated response time for every key. imagine
taking all of the vectors stored within the RTEs, and placing
them all on a two-dimensional graph with the key being the X
axis, and the estimated routing time being the Y axis. Now
imagine drawing a line along the bottom of this mess of lines,
and taking note of which node has the best routing time at each
vector along this line. We would then need a way to update this
data structure efficiently when vector's move as a result of new
reports.
comments?
Ian.
--
Ian Clarke [EMAIL PROTECTED]
Coordinator, The Freenet Project http://freenetproject.org/
Founder, Locutus http://locut.us/
Personal Homepage http://locut.us/ian/
pgp00000.pgp
Description: PGP signature
