Jan 23, 1978 Danny Cohen IEN: 23 Notebook Section 18.104.22.168 On Names, Addresses and Routings -------------------------------- DESTINATIONs and SOURCEs of communication have names. These destinations and sources are processes which exist outside the communication subnet (e.g., in HOSTs) or inside it (e.g., in GATEWAYs, NET-NODEs, etc). Names are not necessarily unique to destinations. Certain processes may have more than a single name. There are two kinds of names, names which specify a unique process and names which specify a set of processes (e.g., by capability). A name tells WHO (or WHAT) the process is. It is conceivable the names are arbitrary alphanumeric string suited for human readability. In addition to names, processes have addresses which indicate WHERE they are. Again, it is possible that several different names share the same address, and also that the same name has several addresses. In order to move messages from sources to destinations, not only the address of the destination (i.e., where it is) has to be known, but also HOW-TO-GET-THERE. This knowledge is the ROUTING. It is, obviously, possible that the same address can be reached by more than one route. These beautiful definitions of NAMEs (what), ADDRESSes (where) and ROUTING (how-to-get-there) are borrowed from John Shoch. To summarize: destinations and sources have names. Names are "converted" into addresses, and addresses into routings. However, none of the above mappings is a one-to-one correspondence. Names have to be unambiguous within a certain environment. From outside of this environment, the environment, too, has to be specified in order to complete the name specification i.e., to disambiguate it completely. This is the essence of hierarchical naming. A very similar argument holds for addresses. Within a certain environment addresses are unique, outside of it, the environment has to
Page 2 be specified ("addressed") too. Obviously, environments have names/addresses which are unique within some bigger super-environment, out of which, the super-environment has to be specified, too. And so on. Note that in general address (and names) are hierarchical. The non-hierarchical case (or the "flat" situation) is a special case of hierarchy, with depth equal to one, and width equal to the total number of addresses. The mapping of names to addresses cannot be computed, and can be resolved only by reference to directories. Hence names from which addresses can be computed are not names in the true sense, but addresses in disguise. These directories may be implemented in various ways, ranging from off-line distributed directories (like paper based telephone directories) to online centralized services (like 411) even by or utilizing some broadcasting techniques. The sole purpose of addressing is to support routing. The address which tells where the destination is, is only important for determining the routing (i.e., how to get there). The key question is who performs the mapping of addresses into routing. Several avenues can be pursued. (1) Sources supplying the entire routing from source to destination (source-routing), or (2) source supplying only the name (or address) of the destination, and the communication subsystem performing the routing (communication-routing), and (3) a hybrid of the above, by the source supplying some intermediate destinations along the route, such that the communication subsystem can perform the routing between these given destinations. Note that (3) is a generalization of both (1) and (2). If done right, it should have the advantages of both, else it may have their combined disadvantages. There are too many (obvious) problems associated with a complete source-routing, (1), which are amplified in dynamically changed networks. Basically, the user is faced with the need to specify completely the routing whenever a message is sent. Since most of the information needed for finding the routing is originated in the communication subsystem, this is an undue burden which should be minimized. On the other hand the other extreme, the communication-routing, (2) , is not problem-free either. In the case of flat address-spaces too much knowledge has to be maintained, with all the problems associated with this requirement. Therefore, it is preferred to implement hierarchical addressing and hierarchical routing, which matches it in a unique way. As a matter of
Page 3 fact, it seems that the most "natural" avenue is to follow the well-debugged paradigm of the telephone system, and have both hierarchical names, which are uniquely mapped into hierarchical addresses. One of the bigger drawbacks of this scheme is that it will not support an application of INTERnet fast facilities in order to expedite INTRAnet traffic, like using satellite links (which belong to SATnet) in order to expedite internal coast-to-coast ARPAnet traffic. Since the flat address space is a special case of the hierarchical one, we would like to treat all address spaces as hierarchical ones, and consider the argument of flat vs. hierarchical as optimizing the depth/width combination. The disadvantage of a big flat name/address subspace (as opposed to a hierarchical one) is that it requires that large table of addresses be maintained, that names/addresses be cleared before being put into use and that everyone knows about everyone, a requirement which is not feasible to fulfill when the dimension of this space keeps increasing. An example for a very flat name space is the social security number, as opposed to telephone numbers and mailing addresses. Note that this space is a subspace of a bigger space which includes also SSNs (or other unique IDs) of people in other countries. Note that both telephone numbers and mailing addresses are a kind of routing of the 3rd flavor. It is supplied by the source, and may have as much (or as little) information to get to the environment where the next piece of routing is nonambiguous. An example of source-routing, (1), is calling from a centrex system to a centrex system in another area code. An example of communication-routing, (2), is the interHOST traffic within the ARPAnet. An example of user-assisted-routing, (3), is an operator-assisted person to person call without knowing the number. For example, one has to tell the communication subsystem (here, a sequence of operators) that the other person is (a) in Massachusetts, (b) in Cambridge, (c) at MIT, and finally (d) the final destinations name. In this case the source supplied the sub-destination "Masachusetts" (or 617) but the communication system was free to choose the optimal route there. Another example is a call which is placed from a military base to another. Normally the AUTOVON system is used, but many times at the discretion of the individuals, they use the AUTOVON system to get outside to the commercial network, and back to the destination base, where the AUTOVON system is used again for the terminal contact. This is a example of an INTRAnet (AUTOVON) call which for quality, convenience and similar reasons, uses INTERnet facilities.
Page 4 Another interesting observation about the telephone systems. Telephone addresses are of variable length. This does not mean only that different addresses may have different lenghts, but that the same address may have several lenghts, depending from where it is refered to. For example inside most organizations extensions may be reached by dialing about 4 digits only. from outside the organization, but still in the neighborhood 7 digits are usually needed, from a larger neighborhood it is 8, then 10, and so on. This is to be expected since telephone numbers are the basis for the hybrid routing used. Telephone numbers are parsed sequentially, and can traverse hierarchies up and down because of the prefixes used to indicate the "up" direction (like the 9 for outside, and the 1 for area code). It seems to me that we might like to implement a very similar structure for addressing. One way to implement such a user assisted routing is to implement a special FORWARDER process (on a well-known PORT), whose function is to receive messages, retrieve the "next-address" from its data and resubmit it for transportation to the next sub-destination, while doing the right things to acknowledgments, duplicates and the like. These processes do not have to be implemented on all systems, but only on a certain subset, where this capability is needed. This would eliminate the need for making all processes able to handle variable length multilevel addressing. SUMMARY The address space should be hierarchical, because it is more general than the flat space, and mainly because it may be not practical to have everyone knowing about all the other participants in this space. The format of the ADDRESS should be made more general (extensible). Routing which follows the hierarchy of the address space has difficulties in utilizing internet resources for intranet traffic. The distribution of all the knowledge needed to support routing which is entirely performed by the communication subsystem may also turn out to be impractical. Relying always on the source to supply the entire routing has its obvbious problems. Therefore we highly recommend that the hybrid approach will be used. ACKNOWLEDGMENT Recent discussions with John Shoch and David Boggs were a very educational experience for me, and helped me to understand these issues better. This note and John Shoch's note on the same subject (both are prepared for the same January 1978 TCP meeting) cover similar issues, and are basically in agreement about most issues. However, minor differences between the them seem to justify their existance separately.