Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!uwvax!mcvoy
From: mcvoy@rsch.WISC.EDU (Flip Wilson II)
Newsgroups: net.mail
Subject: Re: Domains: Multiple names OK? (Really, are domains good)
Message-ID: <2743@rsch.WISC.EDU>
Date: Mon, 22-Sep-86 11:20:25 EDT
Article-I.D.: rsch.2743
Posted: Mon Sep 22 11:20:25 1986
Date-Received: Mon, 22-Sep-86 21:08:51 EDT
References: <566@mecc.UUCP> <2502@cbosgd.UUCP> <3920@ut-ngp.UUCP> <3437@umcp-cs.UUCP> <205@BMS-AT.UUCP>
Reply-To: mcvoy@rsch.WISC.EDU (Lawrence W. McVoy)
Organization: U of Wisconsin CS Dept
Lines: 40

In article <205@BMS-AT.UUCP> stuart@BMS-AT.UUCP (Stuart D. Gathman) writes:
>The pathalias database in conjunction with smail provides
>a convenient way to enter 'user@barf' instead.  Unfortunately, the
>network maps are passing 6 Megs in size.  That is a lot to broadcast
>monthly, and some machines can't handle a database that size.  On
>my AT, pathalias can grow to about 900K before getting canned by
>Xenix.  This will handle thousands of paths, but will not handle
>the entire network. :-(

Just a note to those who need to make the pathalias database managable on
very small machines (ie no disk space).   The current method of storing
the database is "time-optimal", ie you give it a key and it gives you a
full path to that key.  One database query.  This is great for speed, but 
it's space worst case.
	There is a way to get space-optimal by paying time penalty.  It's 
quite simple:  For each key store the hop which immediately preceeds the
key.  Then lookups are a loop in which you build the path backwards until
you reach the root (your host machine).  For example: to store the path 

	seismo	   foo!bar!glarch!seismo
Store
	seismo	   glarch
	glarch	   bar
	bar	   foo

And to build the path you would
	1) look up seismo:	path = [glarch!seismo]
	2) look up glarch:	path = [bar!glarch!seismo]
	3) look up bar:		path = [foo!bar!glarch!seismo]
	4) Recoginize that foo is one of the sites to which you have a link and
	   stop.

Notes: 1) this is space optimal, it takes 2N -1 units of storages where N 
	  is the space to store one key.  For 5000 nodes, each ~10 chars, 
	  this is 10,000 bytes.
       2) This is time worst case.  For a N hop path you have N lookups.  I
          assume that you are using the dbm routines, otherwise this is 
          prohibitive.
       3) I have implemeted a hacked version of this.  If someone wants to 
	  clean it up and post it, I'll send him/her what I've done.