[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gnu-arch-users] Re: situations where cached revisions are not so go

From: Robert Collins
Subject: Re: [Gnu-arch-users] Re: situations where cached revisions are not so good
Date: Sun, 28 Sep 2003 18:07:40 +1000

On Sun, 2003-09-28 at 15:56, Jason McCarty wrote:

> More complicated algorithms could certainly put forth lots more effort
> to follow the graph in the most efficient way, yes. I've chosen a simple
> algorithm to avoid doing complicated graph searches.

Huh? I don't follow. SPF is trivial: you need
a) a priority queue
b) a 'visited' test for each node
c) a path recording structure
d) a cost for traversing a link.


Add the nodes adjacent to TARGET to the queue. If a node is already in
the queue with a lower cost, throw away the adjacency being added.
Once you've finished those adjacencies, start popping the front of the
queue off, and adding it's adjacent nodes.

Rinse and repeat until, after finishing a nodes adjacencies you have one
or more successful paths.

The cheapest of those paths is the one to take.

And: it handles:
normal changesets
  - all by virtue of the cost metric.

For a cost metric I suggest something like:
number of links * RTT *(MAGIC1) + total KB * observed|configured
bandwidth *(MAGIC2) + projected local tree copies *(MAGIC3)

where magic 1 2 and 3 are to normalise the metrics.

GPG key available at: <>.

Attachment: signature.asc
Description: This is a digitally signed message part

reply via email to

[Prev in Thread] Current Thread [Next in Thread]