IEN-179 March 11th, 1981 Danny Cohen USC / ISI Addressing and Routing ---------------------- There are several approaches to addressing such as hierarchical and flat, but there is only one approach to routing: Take the best (usually the shortest) path. The choice of addressing scheme which is both manageable and may support an efficient routing is the subject of this note. Hierarchical addressing is probably the easiest to manage. The universe is divided into some small number of units, and each of which is assigned an address which is some kind of a string, typically numeric but not necessarily so. If any of these units contains more than one member then the same process is repeated (iterated). The address of the subunit is appended somehow, typically to the end (but sometimes to the front) of the address of the parent unit. This hierarchy is easy to manage such that addresses are uniquely assigned. Typically in an hierarchy each unit is capable of communicating both with its ancestor and with all of its immediate descendants. A default routing can always be easily derived from an hierarchical address. This route consists of going up to a common ancestor (parent) and then down to the destination. Hence, an hierarchical address is always a route from the root (sorry about that). This default routing requires only N-1 communication links which is the minimal connectivity for N nodes. In this situation the default route is also the only existing route, up to trivial changes. In reality, for efficiency reasons, the connectivity is richer than that. Typically, brothers are in direct communication, and a "top" (root) may not exist at all.
IEN-179 [Page 2]
Because of the connectivity richness the routing process is non-trivial and requires that decisions be made. Routing is the process of chosing a possible communication link, where there is more than one. The other extreme of addressing is the flat space approach where locations have totally random dependency on their addresses, meaning that a fully instantiated table lookup must be used in order to locate an address. The important feature of flat and random addressing is that it can conveniently support mobile users. A simple, however expensive, way for implementing routing when flat addressing is used is by providing all the switches (where routing decisions have to be made) with tables containing all the required information about all the addresses. In the case of flat addressing it is required that all addresses be globally unique. It is not required however that all addresses be known to all the switching nodes, provided that nodes can ask for, and get, information about addresses which were not known to them. In the hierarchical case it is possible either that all addresses be specified in an absolute (complete) mode or in a relative (partial) mode. The former requires that all addresses be fully expanded, and have the same format regardless of where they are specified (e.g., 1-213-822-1511x104), and the latter supports short forms for local addresses, at the possible expense of additional control information for remote addresses. The same address shown before may be specified as 104 from inside ISI as 822-1511x104 from the STN at LA, as 9-822-1511x104 from UCLA, as 213-822-1511x104 from Palo Alto or as 010-1-213-822-1511x104 from London. Similarly, intra-office memos do not require long addresses, and intra-country mail does not require the country name to be specified in the address. Any system which can handle perfectly flat addresses can take advantage of rich communication connectivity and can also handle multi-homing (destination with more than one address). An hierarchical addressing scheme which uses only the default hierarchical routing may have difficulties in handling efficiently rich connectivity and multi-homing. However, between these two extremes there is a wide spectrum of other possibilities. The claim of the rest of this paper is that (i) hierarchical addresses are easier to manage, and (ii) if you can handle flat addresses - you can handle hierarchical addresses even better.
IEN-179 [Page 3]
Hierarchical addressing is at least as good (in any respect) as flat one because flat addressing is a special case of hierarchical addressing, but not the other way round. Suppose that there is a system which can handle very well flat addressing. Since the only requirement for the flat addressing is that addresses are unique, one can assign unique addresses in any way, for example in a very structured way, like hierarchical. The introduction of hierarchical addresses to the flat addressing scheme should not degrade its performance since the uniqueness was not disturbed. Suppose further that all the addresses are examined at every switch. All addresses which result in the same routing decisions by both the flat addressing scheme and by the hierarchical addressing are marked, and the entries corresponding to them are removed from the flat addressing tables. This causes no degradation of the flat addressing scheme (which was assumed to be a good one to start with) since the hierarchical addressing yields the same routing decision for these addresses. This process repeats at all levels, and only the "GCD" addresses are stored. Hence, after removing these addresses the size of the tables decreases in all switches which probably may yield some performance improvement and increased capacities. In fact, the resulting scheme is now an hierarchical scheme with tables of exceptions which are handled in the best known way. The format of the exception table is discussed later. Note that this results in uneven distribution of knowledge. At different switches different set of destinations are known. For example, all the traffic to the East coast may be treated in the same way when being far away from there, but as the message approaches its destination, it is likely that the granularity of the address examination changes such that more details are used. When leaving Tokyo the only part of the address which was used for the routing was the fact that the message is addressed to the States. After arriving at California, the Boston traffic may be treated separately from the Washington traffic, later the Boston traffic is examined even closer to distinguish the Cambridge from the Lexington traffic, and later the MIT traffic is isolated from the Harvard and the BBN traffic. Upon entering MIT the traffic is sorted further to the appropriate local MIT net, and later to its terminal destination. This scheme allows the switches in Tokyo NOT to know about the internal structure of the addressing in the USA in general and at MIT in particular. It also helps the switches in California to take advantage of special HU (high utilization) trunks to the Boston area, if any. Since this hybrid contains both the flat and the hierarchical addressing, multi homing can be handled as well as by flat addressing.
IEN-179 [Page 4]
Another variant of this scheme is not to start with full tables of flat addresses (which are impossible to manage) but to treat the system as if it was a pure hierarchical one, but in addition to maintain a table of exception which is dynamically updated. The entries in these exception tables should include both addresses, their granularity level and the associated routing decision. If, for example, addresses always consist of a sequence of bytes (of any size) the granularity level may be measured by the number of bytes which are used. For example, a telephone exchange in Marina del Rey may know that the traffic for 1-213-828X and 1-213-821X is local, all the traffic for addresses 2X and 4X (Europe) should be routed to a certain cable which goes directly to Europe, the traffic to 1-212X be routed to a some cable which goes directly to NY, the traffic to either 1-617-49X or 1-617-253X should be routed to the HU trunk which goes to Cambridge, and similarly the traffic to 1-202-694-3049 should be given to a certain line which is connected to a certain destination, somewhere. All the rest of the traffic should be routed to downtown LA where smarter computers can solve the routing. In the above example the various entries have different levels of granularity, varying from 1 (in the case of Europe) to 11 (in the last example). Such a scheme yields tables of reasonable size, can benefit from any structure and logic/regularity (as opposed to randomness) of the communication subsystem, can handle multihoming, and has the capability to utilize special irregular HU lines and shortcuts. Note that in this scheme the addressing may be highly structured (e.g., in a hierarchical way) but the routing is not necessarily so. The routing is hierarchical only when this is known to be the right thing, or when nothing else is known and the hierarchical routing is used as a default. In summary, this is a way to benefit from the simplicity of hierarchical routing whenever possible, while being able to use the flat-addressing features when needed, on a case-by-case basis, without the need to maintain tables of unreasonable size.