-- --

PATHALIAS

or

The Care and Feeding of Relative Addresses

Peter Honeyman

Computer Science Department
Princeton University
Princeton, New Jersey 08544
princeton!honey

Steven M. Bellovin*

AT&T Bell Laboratories
Murray Hill, New Jersey 07974
ulysses!smb

ABSTRACT

Pathalias computes electronic mail routes in environments that mix explicit and implicit routing, as well as syntax styles. We describe the history of pathalias, its algorithms and data structures, and our design decisions and compromises.

Pathalias is guided by a simple philosophy: get the mail through, reliably and efficiently. We discuss the principles of routing in heterogeneous environments necessary to make this philosophy a reality.

HISTORY AND OVERVIEW

UUCP,1 the basic networking component of UNIX,2 is the backbone of a widespread store-and-forward network. Because setting up new connections is easy, and does not require the intervention of a central administrator, the network has no regular topology. Mail routing is explicitly specified by users. That is, a user who wishes to send mail to hostb using hosta as a relay would write

mail hosta!hostb!user

When the UUCP network was small and the average connectivity was high, explicit routing was a minor annoyance at worst. Most paths were direct, and only a tiny fraction involved more than one or two hops, so remembering proper paths was easy.

Then came USENET.3 For several reasons, UUCP routes soon became a major headache. First, many of the universities on USENET had a low degree of connectivity to other UNIX sites, typically with only two or three long-distance links. Second, USENET readers tended to reply along the USENET paths; these were rarely optimal, and were sometimes unusable. Third, as other networks were used for USENET transport, hhhhhhhhhhhhhhhhhh
* Much of the work was performed at the Department of Computer Science, University of North Carolina at Chapel Hill. 1 D.A. Nowitz and M.E. Lesk, ``A Dial-Up Network of UNIX Systems,'' in UNIX Programmer's Manual, Seventh Ed., 1979.
2 UNIX is a trademark of AT&T Bell Laboratories.
3 S.M. Bellovin and M. Horton, ``USENET ? A Distributed, Decentralized News System,'' unpublished manuscript, 1986.