mark@cbosgd.UUCP (Mark Horton) (01/14/85)
There have been some questions about what the valid codes in the pathalias information are. I am including a list of those that are understood. When updating your maps, please use these codes, or arithmetic based on them. (For example, DAILY/2 means one-half the value of DAILY, or 2500; i.e. that connections are made twice per day.) These numbers represent the "cost" of the connection, and are used by the pathalias program to find the "least cost" route to send mail. The enclosed information is excerpted from the pathalias manual page. LOCAL 10 (local-area network connection) DEDICATED 95 (high speed dedicated link) DIRECT 200 (local call) DEMAND 300 (normal call) HOURLY 500 (hourly poll) EVENING 1800 (time restricted call) DAILY 5000 (daily poll) WEEKLY 30000 (irregular poll) In addition, ARPA is either a very large number or a very small one, depending on whether the local site is on the \s-2ARPANET\s0, DEAD is a very large number, and HIGH and LOW are \-5 and +5 respectively, for baud-rate or quality bonuses/penalties. The numbers are intended to represent frequency of connection, which seems to be far more important than baud rates for this type of traffic. There is an assumed high overhead for each hop; thus, e.g., HOURLY is far more than DAILY / 24. Mark
andrew@garfield.UUCP (Andrew Draskoy) (01/14/85)
I have found the definitions to be a bit incomplete.
For example what do you use if you will call someone on demand, but
also poll them daily? I have seen people using DAILY for this, but
some value less than DEMAND would perhaps be more appropriate.
Another example: We call most of our connections after midnight,
but only if we have something for them - and we will call them on
demand up until 8am. We have been using EVENING to express this,
but I am not sure this is right. I think the definitions could
stand to be made clearer.
Since Mark's reason for posting the official definitions is presumably
to get us all using the same values to describe similar situations, I
think some discussion on the relation of these definitions to reality
would be appropriate.
--
Andrew Draskoy
{akgua,allegra,cbosgd,ihnp4,mcvax,utcsrgv}!garfield!andrew
The opinions expressed above may not represent those of the author
after he has had some sleep.honey@down.FUN (code 101) (01/17/85)
let me respond to some of andrew droskoy's queries. i gather this is a confusing point, since so many people seem confused by it. mea culpa. in simplest terms, pathalias solves the single-source shortest paths problem in a weighted, directed graph. see aho, hopcroft and ullman for details. all pathalias wants out of life is a list of weighted edges so that it can do its thing. it yaccs a high-level language to make life a little easier (for you! for me and steve it's like pulling teeth, or scratching fingernails on a blackboard). LOCAL, DEMAND, etc. act like macros for integers (cat lex.l), not "classes of service" or whatever the common misinterpretation is. on to the misinterpretations. (but first, please glance at the man page. thank you.) I have found the definitions to be a bit incomplete. For example what do you use if you will call someone on demand, but also poll them daily? I have seen people using DAILY for this, but some value less than DEMAND would perhaps be more appropriate. if you call someone on demand, the appropriate weight is DEMAND. if someone polls you every day, use DAILY. if you call on demand *and* once a day, that's no better than calling on demand, is it? so use DEMAND. DAILY+DEMAND definitely doesn't make it, since this indicates a link that is more costly (i.e., less useful/reliable/worthwhile) than DEMAND or even DAILY. as a rule of thumb, do not mix the basic costs (see man page again) -- use HIGH and LOW for minor adjustments. Another example: We call most of our connections after midnight, but only if we have something for them - and we will call them on demand up until 8am. We have been using EVENING to express this, but I am not sure this is right. EVENING is the appropriate cost. I think the definitions could stand to be made clearer. you're probably right -- help? Since Mark's reason for posting the official definitions is presumably to get us all using the same values to describe similar situations, I think some discussion on the relation of these definitions to reality would be appropriate. the values were pulled out of thin air, played with, adjusted, adjusted, etc. until the routes started looking reasonable. i don't know a better way to describe this. perhaps the mistake was to allow arithmetic expressions in the weights, which has led to confusion (as well as providing flexibility). i abase myself for having anything to do with this and am open to suggestion. coming soon in a net.sources near you: the third iteration of pathalias. i have sworn my honor that i'll post it before dallas. peter
spaf@gatech.UUCP (Gene Spafford) (01/20/85)
Let me attempt a little more explanation, and maybe it will help.
Imagine drawing a directed graph (digraph) where every edge represents
a uucp (or other) connection. If you weight each edge with a cost, you
have a network. Pathalias is a program which applies an algorithm to
figure least-cost routes to other sites (I dunno which algorithm -- I've
never bothered to look. I hope it's one of the more efficient ones,
perhaps even using a heuristic lookahead, but it really doesn't matter.)
Now the problems come in when a site has a link with basically two (or
more) possible classifications. Suppose site A calls site B on demand
whenever there is news to transfer, and after midnight otherwise.
Well, in our network, we have two (2) directed edges from node A to
node B -- one with a weight of DEMAND and one with a weight of
EVENING. Now, if you look at the values behind DEMAND and EVENING,
you'll see that DEMAND is a smaller value than EVENING. Since
pathalias tries to find the least cost (weight) path, it should never
traverse the EVENING path since there is a cheaper route from A to B --
namely, the DEMAND link. Thus, there is no use in specifying the
EVENING route at all. I believe, in fact, that if you actually include
both in your listing, as in:
a b(DEMAND), b(EVENING)
then pathalias will complain about a redundant link and use the DEMAND
link since it is cheaper.
The underlying point is, if two specifications could be used to describe
the way your site connects to another, use the one with lowest cost
(weight).
--
Gene "7 months and counting" Spafford
The Clouds Project, School of ICS, Georgia Tech, Atlanta GA 30332
CSNet: Spaf @ GATech ARPA: Spaf%GATech.CSNet @ CSNet-Relay.ARPA
uucp: ...!{akgua,allegra,hplabs,ihnp4,linus,seismo,ulysses}!gatech!spafhoney@down.FUN (code 101) (01/21/85)
The algorithm used by pathalias doesn't seem to have a name. Sometime last summer, it struck me that since the graph is sparse (4000 nodes, 20,000 edges), Dijkstra's algorithm, which always takes time O(v squared) must lose to one that uses a priority queue. (Think of breadth-first search, with a priority queue instead of a regular queue. 120 sophomores implemented this algorithm in my data structures course this past term, so it can't be too hard, right?) Because the graph is sparse, i.e., e is O(v), this takes time O(v log v). In practice, changing the original algorithm, which was Dijkstra's, better than halved the running time of pathalias. I seem to have discovered this algorithm, notwithstanding the fact that it's mentioned in Aho, Hopcroft and Ullman's Data Structures text as a variation on Dijkstra's (without a reference). Or the fact that Sedgewick tells me that he also discovered it, years ago. People in the know tell me it's probably in Don Johnson's bible, er, thesis. (Can someone at Penn State ask for me?) I don't know anything about a "heuristic lookahead" method -- what did you have in mind? Not that it really matters, since the big bottleneck in pathalias is parsing, not mapping. Peter