Path: utzoo!utgpu!water!watmath!clyde!att!ucbvax!amdcad!rpw3 From: rpw3@amdcad.AMD.COM (Rob Warnock) Newsgroups: comp.mail.uucp Subject: Re: Dynamic vs. passive routing: site rights Message-ID: <22788@amdcad.AMD.COM> Date: 31 Aug 88 03:06:41 GMT References: <4902@netnews.upenn.edu> <965@vsi1.UUCP> <6392@chinet.UUCP> Reply-To: rpw3@amdcad.UUCP (Rob Warnock) Organization: [Consultant] San Mateo, CA Lines: 64 tron@amdahl.uts.amdahl.com (Ronald S. Karr) writes: +--------------- | In article <6392@chinet.UUCP> les@chinet.UUCP (Leslie Mikesell) writes: | >But if you have a map entry for b showing that it talks to your site | >and c, and you have a map entry for c showing that it talks to b, do | >you not then know that the c in your map entry is the same c that | >b is going to forward to? | In this specific case, you probably know that the two c's are the same. Now | if you can get this information into your mailer then you are doing something | that is a substantial improvement over the current state-of-the-art... | A reasonable implementation of your strategy would require the mailer | to step through the map data and find an optimal solution for each path. | This is very expensive (in CPU and disk)... +--------------- There is an intermediate strategy that does not cost very much, is completely correct, *and* which would trim paths a lot if we all did it. (Peter Honeyman and I discussed this in the halls way back at the SLC USENIX and agreed that it would work, but neither of us ever implemented it.) What you do is a bounded-depth tree walk starting at your site, and going out for some small path length "x" (say, 3 to 6), computing *left-prefix* paths using the map data. Whenever two completely known (in the sense of the connectivity being in the maps) left-prefixes go to the same site, you store a rule which says that it's o.k. to rewrite the poorer into the better (by whatever criteria -- usually path cost -- you prefer). You stop when you exceed depth "x" or when your rewrite table gets "too big". (The rewrite table can be searched with the same binary search smail uses for the "paths" file.) For example, if you talk to "a" and the map for "a" says he talks to "b" and the map for "b" says she talks to "c" and that's the *same* "c" you talk directly to, you can rewrite "a!b!c!..." to "c!..." (as suggested above). This is completely correct and safe, since you you are exploring a path anchored at yourself. You are *not* "reaching into" a UUCP path (e.g., starting at the right -- *UGH*) and pulling out a name without indeed knowing that that's the same host you talk to. For example, if your depth limit is 4, and you see the path "a!b!c!d!e!c!x!..." you may safely rewrite as "c!d!e!c!x!..." (assuming the maps as above), but you *MUST NOT* rewrite it as "c!x!..." since you did not actually prove that the two c's were the same. (Yes, I have seen cases where they were different.) Nor may you rerwrite "a!b!q!j!c!x!..." to "c!x!...", for the same reason: You didn't search out far enough to prove that that "c" is the one you talk to. So if you're so limited in what you can do, why bother? Because if everyone rewrote 2-3 hops out of an outrageous path (and the truly outrageous ones seem to wander 'round and 'round), it would become merely long. Yet no unregistered host need ever be "cut off", nor would any unregistered host ever become a black hole for a registered host's mail (nor vice-versa). The preprocessing should be much less than a full pathalias run, since you are basically just exploring "your neighborhood", and not the whole net. (You still need the pathalias output for routing domain names, or if you want to be somebody's "smart-host", that is, routing left-most non-direct- connect names.) Rob Warnock Systems Architecture Consultant UUCP: {amdcad,fortune,sun}!redwood!rpw3 ATTmail: !rpw3 DDD: (415)572-2607 USPS: 627 26th Ave, San Mateo, CA 94403