tsuchiya@GATEWAY.MITRE.ORG (Paul Tsuchiya) (09/25/87)
To whom it may concern (and a plea for help)...................... I am working on a set of new techniques for dynamic routing in very large networks, called Landmark Routing. Anybody at the July IETF meeting saw a presentation of some of this work. I have just finished a rough draft of a major piece of work that describes, mostly at medium to high level, how all of Landmark Routing works. (The previous document, which a lot of people have seen, is full of fairly nitty-gritty details about one small aspect of Landmark Routing--the Landmark Hierarchy). I am looking for people to read the paper and give me feedback. I hope that there is a varied collection of people out there that would be interested in this work--partly because it contains a lot of new ideas, and partly because there is a reasonably good chance that implementations of it will find their way into the internet in the near future (one year at best). Landmark Routing basically is a set of protocols and algorithms that allow for fully automated routing in arbitrarily large networks and internets. Its main feature is that it automatically configures its own hierarchy for dealing with large numbers of nodes--no preassigned addresses are necessary! To deal with changing addresses, it offers a general, fully distributed name-to-address binding scheme, which we have dubbed Assured Destination Binding. As a fallout of this, Landmark Routing can handle any number of mobile hosts. We have also incorporated the concept of administrative boundaries into the scheme. This allows messages to stay within a pre-defined boundary, prevents other messages from going through the boundary (if desired), and allows a fair amount of autonomy between different groups. The paper itself, called "Landmark Routing: Architecture, Algorithms, and Issues," is long; over 140 pages. However, don't let this lower your expectations about the quality of the work. Unlike many long papers, I don't think any of this thing is content-free. (Believe me, if I could fit all of it into one double spaced page, I would). Because of the length, I would only expect people to give substantive review individual sections. There are 5 major sections (not including the section that overviews the main idea behind Landmark Routng). Although a general understanding of Landmark Routing is needed to help understand any section, they all pretty much stand alone. Therefore, one could realistically give substantive review to any one section without reading the whole thing in gory detail. Let me outline each section, so that people can get an idea of whether they want to read it. I am only interested in hearing from people who will give it a real critical review. Section 2 describes the basic idea behind Landmark Routing. I don't need any review of this section. Section 3 describes the routing protocol I intend to use with Landmark Routing (the way it is architected, multiple and/or different routing protocols can be used, as long as they are of the distance-vector (i.e., Bellman-Ford, Old ARPANET, etc.) variety). Don't worry about the count-to-infinity business. This section contains a simple and efficient fix to count-to-infinity that has INSTANT convergence to new routes given bad news. (Even good-ole SPF doesn't have instant convergence.) This is because the alternate route is pre-primed even before bad news comes along. We call this scheme Alternate-path Distance-vector Routing. The alternate route also provides some nice path splitting to boot. Section 4 describes how the hierarchy is maintained and adjusted in the face of topology changes, including merging networks together. Section 5 describes the administrative autonomy and trust scheme that we employ, called Administrative Zones. It provides some of what Autonomous Systems provide. Section 6 describes the name-to-address binding technique mentioned above. This technique works with a completely flat name space (as long as names are unique), and can be distributed among as many or as few nodes as desired. Finally, section 7 provides a lot of miscellaneous, include implementation ideas, transition issues, address structures, how to configure across large, non-broadcast subnetworks, and the like. I should note that this implementation will be for ISO only (the DoD IP address is just too small), but will be able to handle DoD IP packets. As such, it will be useful during transition. Also, most of the implementation will run at the application layer. I GREATLY appreciate any help people wish to offer. Thanks in advance.................. Paul Tsuchiya tsuchiya@gateway.mitre.org The MITRE Corp. tsuchiya@mitre-gateway.arpa P.S. (Sorry for those of you who received this over several lists)