Internet Experiment Note # 19
Notebook Section 2.3.3.5
A note on
Inter-Network Naming, Addressing, and Routing
John F. Shoch
January 1978
Xerox Palo Alto Research Center
Palo Alto, California 94305
Introduction
Taxonomies and terminology will not, by themselves, solve some of the
difficult problems associated with the inter-connection of computer networks;
but carefully choosing our words can help us to avoid misunderstanding and
refine our perceptions of the task.
In 'Through the Looking Glass', the White Knight tries to elucidate (for an
imprecise Alice) the important differences between what a song *is*, what it
*is called*, what it *is named*, and what *the name is called*; perhaps we
need to be equally vigilant with our use of the words 'name', 'address', and
'route'.
Let me offer one scheme which has proven useful in analyzing this domain, and
begin by asserting that 'names', 'addresses', and 'routes' are different
entities. [Even one of my favorite papers introduces part of this topic by
merging two of these characteristics: "The question of addressing. or how to
name all the participants in an interconnected communication system...."]
The General Model
We can first construct an extremely general definition:
The 'name' of a resource indicates *what* we seek,
an 'address' indicates *where* it is, and
a 'route' tells us *how to get there*.
Some further detail to flesh this out:
I. A 'name' is a symbol -- usually a human-readable string -- identifying
some resource, or set of resources.
The string need not be meaningful to all users, and need not be drawn
from a uniform name space.
The strings can identitify processes, places, people, machines,
functions, or anything else the user chooses.
2
To be useful, however, there will probably be some mechanism available to
the user that will map names into addresses.
The name (what we seek) need not be bound to the address (where it is)
until this mapping takes place; the address (or addresses) associated
with a particular name may change over time.
II. An 'address', however, is the data structure whose format can be
recognized by all elements in the domain, and which defines the fundamental
addressable object.
Addresses must, therefore, be meaningful throughout the domain, and must
be drawn from some uniform address space.
This address space may be a "flat" one which spans the entire domain
(such as Social Security numbers), or it may be a hierarchical address
space (such as telephone numbers).
If a name has produced several different addresses for a particular
resource, some form of 'a priori' information may prove useful in
selecting a preferred address.
At the time one wishes to communicate with a particular address, there
will be some mechanism that will map an address into an appropriate
route.
The address (where something is) need not be bound to the route (how to
get there) until this mapping takes place; the choice of an "appropriate"
route may change over time.
III. A 'route' is the specific information needed to forward a piece of
information to its specified address.
The routing action may only require one step to reach a destination (a
direct route), or it may require a series of steps in order to forward
the information on its way.
Where there is merely one hop in a simple topology, the routing decision
is usually straightforward.
When the path to an address requires several steps (as in a store and
forward system), the route defines a path through intermediate switching
points.
In categorizing such routing mechanisms, one dimension is the *place* at
which each intermediate routing decision is specified:
a. The source may specificy all of the intermediate routing decisions,
and include this information along with the data being sent ('source
routing'). The source must have fairly comprehensive information about
the environment, but the switching points need not maintain routing
tables.
b. Alternatively, the source may only specify the destination
address, and the intermediate switching points choose the next
portion of the route ('hop-by-hop routing', sometimes called
'intermediate routing' or 'incremental routing'). In this case, the
source only needs enough information to reach the next switching
point, but each of these points must then have a routing table of
some sort.
c. There may be a hybrid routing mechanism combining these two, in
which the source specifies certain major intermediate points, but
allows the underlying system to choose routes between those points.
A second dimension of the routing mechanims [sic] is the 'time constant'
of the routing decisions -- when are they specified, and how frequently
they may be changed:
a. Routing tables may be set once, left unchanged for relatively long
periods
3
of time, and only changed to reflect major modifications to the
system ('fixed routing', or 'deterministic routing').
b. Alternatively, routing tables may be updated relatively
frequently, reflecting shorter term changes in the environment
('dynanamic routing', or 'adaptive routing').
[This measure is, in some sense, relative to the time constants of
the communication system itself.]
If there is a dynamic routing system providing periodic updates of
appropriate information, a third dimension of the routing process is the
'control' mechanism:
a. Individual switching points may try to update their information in
an 'isolated' manner, perhaps by trying various routes and observing
performance.
b. Changes in the environment or connectivity may all be reported
back to one 'centralized' point, which is then responsible for
promulgating this inforniation to the sources (if we use source
routing) or to the switches (if we use hop-by-hop routing).
c. Alternatively. control of the dynamic update process may be
'distributed' among all of the sources or switches, which individualy
[sic] obtain information about the state of the system.
It is meaningful to talk about possible combinations of these
dimensions: 'fixed source routing' may be quite simple to implement,
while 'dynamic source routing' may be beneficial if the source can learn
about changes occurring throughout the system. 'Fixed hop-by-hop routing'
requires setting the routing tab1es at the switching points, while
'dynamic hop-by-hop routing' then requires updates to these routing
tables. 'Distributed, dynamic, hop-by-hop routing' might obtain these
periodic updates from neighboring switches, while a 'centralized,
dynamic, hop-by-hop' system would depend on some form of network coutrol
center to provide new information.
Thus, a *name* may be used to derive an *address*, which may then be used to
derive a *route*.
[There is an interesting similarity between this structure and mechanisms
used in programming languages (where one must bind a value to a
variable), or in operating systems (where one must link a particular
piece of code into a module). In all these cases, there is a certain
amount of added flexibility gained by deferring the binding process as
long as possible: MULTICS defers the binding of pieces of code until
run-time so that new instantiations of code will be used automatically,
while the Arpanet tries to defer routing decisions as long as possible,
in order to make the most informed choice.]
If one fails to deliver a piece of information to the resource originally
specified, an error recovery procedure can systematically try to undo each of
these binding decisions: first try an *alternate route*, then an *alternate
address*, then an *alternate name*.
Example #1: Naming/Addressing/Routing in the Telephone System
Before attempting to apply this scheme to a connected set of computer
networks, let's see how well it serves to understand the workings of another
domain: placing a telephone call.
[The telephone system, of course, uses circuit switching, and dedicates
resources for the lifetime of a call. We are here discussing the naming,
addressing, and routing which take place during call set-up.]
I. We can look up a 'name' in the phone book.
The name may be a specific person ("D. B. Cooper"), an institution
("Stanford University"), the local representative of a nation-wide
service ("the nearest TWA
4
office"), or a generic function ("Get me the police!", or the time
server).
The names of different individuals may yield the same phone number.
One name may yield several phone numbers, if there are two telephones in
one home or if a business provides multiple incoming lines. In addition, a
considerate business might provide several incoming lines vith
different area codes.
Should a name yield more than one number, the caller may use some
additional information to aid in the choice of which to dial: is one
number less likely to be in use, or is one address in our own area code,
and thus cheaper.
There can be a two-level name-to-address mapping process: look up the
name "information" in the phone book, get that number (411), place a
call, and then present a new name to be looked-up by the information
operator.
II. The 'address' which we eventually find is just the telephone number.
The phone system did not have to understand the subscribers' names, but
it certainly must be able to understand their addresses (numbers).
Addressing in the phone network is based on a hierarchical structure --
the major contribution of area codes, as specified in the North American
Numbering Plan.
There are certain conventions for defaulting parts of the address when it
is found: if the area code is not listed, we generally assume it is the
same as our own.
Every resource (person) accessible through the phone system is actually
represented by a telephone instrument, which we can address. Actual
signals are intended for the person, but they are always sent via the
instrument.
III. Vhen we dial the number (in fact, each time we dial the number) the
phone network attempts to build an appropriate route to the destination,
reflecting current conditions.
Two successive calls to the same number need not be routed through the
same path, and the telephone plant provides alternate routes if a trunk
is busy. The distributed, adaptive nature of this routing is one of the
major factors which contributes to the reliability of the phone system.
Now consider the error recovery procedure if we are not able to reach the
person we seek: we move back through the hierarchy, trying alternate routes,
alternate addresses, and alternate names.
1. If we get a busy trunk indication, we know that the route chosen by the
network turned out to be inadequate. We can, in effect, ask the system to try
picking a route again, by re-dialing (re-transmitting). If we are
particularly concerned, we can ask an operator to override some of the
automatic routing decisions, and attempt an alternate route.
2. If all of the routes to this address are inadequate, or if the address is
unavailable (perhaps busy, or broken), we must fall back and find an
alternate address: perhaps there were two phone numbers listed, and we can
try the second. (How many of us have second phones for a terminal, which we
call in on when the regular line is busy?) This will lead to the selection of
a completely new route.
3. If the alternate address fails, we can fall back one more step, and try to
find an alternate name: perhaps the phone is listed in the name of one's
spouse, or maybe we should look up the name of the organization where one
works.
5
The Implications of Hierarchical vs. Flat Address Spaces
It should be apparent that the structure of the address space is of central
importance: it is the major element of commonality in such an environment,
and can have a profound influence on the naming mechanism "above" and the
routing mechanism "below".
An address space can be partitioned in a hierarchical manner, or left as a
single uniform space. Use of a flat address space implies that:
1. The address given to any resource must be unique over the whole
domain; and,
2. There is no structure to the address which might aid the routing
process; instead, the routing mechanism must be able to handle all
addresses, without segmenting them into parts (i.e., there is no area
code).
There are some advantages to this approach: it is logically simple, and has
the potential to optimize the particular route between any two resources. But
there are certain kinds of costs: upon adding a new set of resources to an
existing system, one must insure [sic] that none of the new addresses
conflict with those already used, and the routing process must now be able to
recognize all of the legal addresses (in the phone system, 10^10).
The alternative is to provide a hierarchical structure for addresses, as has
been done with area codes. Local addresses can then be changed within areas,
but need not be made known to all of the other parts.
Yet the choice of hierarchical addressing can have important ramifications
for the levels "below".
We would certainly not want to allow a strictly hierarchical address scheme
to serve as the justification for a strictly hierarchical physical topology:
that would allow only one path to each resource, and severely diminish
reliability. Thus, the underlying communications should provide alternate
paths to a destination.
Furthermore, the routing mechanism must now be flexible enough to take
advantage of the alternate paths available -- it would make litle sense to
lay a strictly hierarchical routing algorithm on top of a richly-connected
network. Given a hierarchical address, this form of area routing should be
able to pick out an appropriate field, and route the data towards that area,
through one of the available paths, but be able to identify an alternate path
when necessary.
Though the hierarchical address space is often viewed as preferable, there is
a cost here too: if the routing decision does in fact use the hierarchical
structure of the address and route to an area, then some information has been
lost: the ability to specify precise routes between two resources. This can
lead to several kinds of difficulties:
1. Two resources may be geographically close, but on distant branches of
the hierarchical tree, If the routing strictly parallels the addressing
hierarchy, it may require many hops to reach a nearby node.
The telephone system provides a routing hierarchy which matches the
addressing scheme, but then provides additional routes (high usage
trunks) across the tree, as warranted by the traffic; switching
centers then have the choice of routing through the specially
allocated trunk, or back up the regular hierarchy, which then becomes
the alternate route.
This means, however, that some central offices within an area code
are reachable through direct lines, while other less-heavily used
offices must be reached through the standard hierarchy. To make that
routing decision, the foreign switch must be provided with additional
information about the internal structure of the system within the
destination area code -- i.e., which central office prefixes are
reachable through a "short-cut". To take advantage of a direct
high-usage trunk from downtown New York to a
6
central office in downtown San Francisco, without going through the
California area code hierarchy, the switch in New York must be able
to perform what is called "6-digit translation" on the phone number,
examining both the area code and the central office prefix.
2. If a sub-area (netvork) is unintentionally partitioned so that half of
its internal addresses are now unreachable, a distant routing process
won't be able to recognize that, given only the sub-area number.
3. Should there be alternate paths into the partitioned sub-area, now
making those lost nodes reachable, the distant routing process will not
be able to make an informed choice about the proper route into the
sub-area.
4. Two resources may be in the same sub-area, but perhaps connected by an
inefficient route (many hops or poor quality). Provided there are two
paths in to the sub-area, it may make more sense for a resource to route
its traffic out of the area aud back in through the other path, but area
routing will indicate that the source is already in the area of the
destination, and may not allow a route going outside of that area.
In these unusual circumstances, we see that there are clear weaknesses at the
routing level which evolve from the choice of a hierarchical address space;
but in the most common cases this approach will work well.
This choice of hierarchical addresses may also impact the naming mechanism,
although that ought not be necessary. The name-to-address mapping can be
supplied by a process which is external to the system itself, and there is no
reason to enforce hierarchical names. A user may offer a name from which one
can directly derive the address, but it should also be acceptable to provide
a symbolic name, independent of the address format. An example may show the
different kinds of names which might be converted into adresses (telephone
numbers):
1. The syntax of the string "(415) 767-2676" explicitly indicates the
three fields of the address, and their values.
2. The string "(SanFrancisco) Pop-Corn" has the syntactic structure of a
proper hierarchical address, but will require a symbolic look-up of the
component parts.
3. Yet the string "GetMeTheTimeLady" -- when looked-up in the context of
my name dictionary -- should produce this same address.
The virtue of the third approach is that the names may remain the same, even
if the resource is moved to a different address, or if I should move to a
different area; only the name-lookup process must be made aware of the change.
Example #2: Inter-connected Computer Netvorks
It seems that this model of naming/addressing/routing provides a useful
framework for discussing the phone system, and that system provides a rich
set of examples for comparison with the domain of computer networks.
I. A name is merely a human-readable string meant to denote some resource:
"BBN-TenexA" (a host), "SAIL" and "SU-AI" (two names for the same host), "the
SRI mobile van", "a time server", "the Telnet server at ISI", "the Telnet
server on any Tenex", "the nearest FORTRAN compiler", "the error-logging
process in IMP32", "the inter-network routing process in Gateway2l" .... Note
that these names may identify resources outside of the communication system,
or processes within it.
Virtually any object can have a name. In practice, of course, any such
resource is usually represented by some sort of process which can act on its
behalf.
The Arpanet system for handling text messages describes a slightly
different kind of name, in the form "User@Host", but that would not
really resolve down to a proper internetwork address. Instead, the "host"
name is used to derive an address for the
7
mail server process, and the "user" name is sent along as data, to be
interpreted by a higher-level protocol (the mail server) at the
destination.
Some local process (either local or part of some distant resource) may offer
to convert names into appropriate addesses, although a single name may yield
many addresses. The name-lookup process may know about the precise address of
certain well-known severs [sic], and may provide certain default conventions
if some portions of the address are not fully specified.
I have not yet mentioned the notion of names and addresses for
multi-destination pieces of information. The name
"Internet-Working-Group" could produce a whole set of names, which in
turn could be transformed into individual addressess [sic], and
individual copies of the information could be sent to each place. Most
communications subsystems do not yet have protocols which would provide
more congenial support for multi-destination packets.
If a single name does yield many addresses, one of them may be chosen on the
basis of some other information: bandwidth and delay characteristics, cost,
etc.
II. An address, in this context, really means an internetwork address: a
collection of bits in a standard format, recognizable by any object cognizant
of the inter-network protocols.
In most inter-network efforts we have adopted a hierarchical address space,
usually partitioned into (net, host, socket) tuples.
Note that this model is not quite adequate to describe the dynamic naming
and addessing conventions planned for the Distributed Computing System
(DCS) at UC Irvine. They had proposed that processes not be bound to
particular machines, but would be free to migrate around the ring; 16-bit
process ID's on each packet would be dynamically checked in each host,
and the packet given to the appropriate process, if it happened to be in
that host. The actual address of a destination process would remain
hidden from the sending program,
I would argue that the 16-bit process ID (although not human-readable) is
most accurately called a process 'name', since it may be used to describe
a generic resource without specifying a particular address. Thus, this
mechanism pushes "down" and distributes the task of mapping from names to
addresses, thereby deferring the binding until even later.
The mechamsm depended heavily on two aspects of the DCS ring:
-- the ability of the communications subsystem to broadcast a packet to
all nodes on the ring, and,
-- the ability of each interface to quickly look up a process name in a
content addressable memory (associative memory) used to identify those
processes resident in the node. (In the original proposal, this memory
could hold the names of 16 resident processes) [sic]
In a different communications enviromment -- or if there were more than
16 processes in one host -- this mechanism would not function properly.
In those cases, however, one can provide the same effect (allowing users
to communicate with resources stirctly [sic] by name, without specifying
an address) merely by providing an extra layer of protocol. I would
conclude that the different naming/addressing conventions in DCS are more
of a difference in style, rather than a difference in substance.
We usually think of these three components as physical objects -- networks
and machines -- but they are really only logical groupings used to form the
address. In a particular environment, for example, the "host" might be a
front-end processor, and the "sockets" might be specialized processors,
perfoming the function which the user sought at that
8 address. If a machine has only one network interface, processes in that machine will all have the same <Net><Host> address, although from many other addresses there may be multiple paths to this address. If a machine has two network interfaces, to the same network or to two different networks, it will have two alternate internetwork addresses for each process resident there. Another process seeking to communicate might select either address. III. The underlying communications system provides the means for routing packets to their destination. Individual networks use different routing strategies for forwarding their internal traffic: the DCS ring has a simple topology with no alternate routes, while the Alohanet and the Etherent [sic] use a broadcast communications media, requiring no routing. The Arpanet uses dynamic hop-by-hop routing, while the Packet Radionet uses dynamic source routing. Internetwork packets, however, may travel through various networks, routed among internetwork gateways. The gateway routing processes make use of the information specified in the internetwork address, and can route to the areas specified. Upon arrival at a gateway entering the destination network, the network-specific routing mechanism can be used to route it to the specified "host". The gateway processes may implement a form of dynamic hop-by-hop routing, using complete networks as the communications channel to "adjacent" gateways. These gateways can exchange routing tables and perform dynamic hop-by-hop routing, or one could simplify the gateway by requiring users to perform source routing. In one sense, these two methods can be combined: while the gateways normally do hop-by-hop routing, there could be a special process resident in the gateway which would take incoming packets, examine the data field, extract the next address indicated there, and forward the packet to that destination. (Danny Cohen has called this process a "forwarder", and I believe Steve Crocker once called it an "oasis".) The effect is to provide source routing to the user, by simply incorporating the list of intermediate addresses in the data field of a packet, rather than in the header. We have spoken earlier on the manner in which area routing using hierarchical addresses cannot properly identify resources which may have been stuck in different parts of a partitioned network -- it requires some additional information to guide the selection of an appropriate route. If we are using some form of source routing, and if some information about the internal structure of the destination net can propogate back to the source, it may be possible to then choose an alternate route which will lead into one part of a partitioned network. In addition, a source routing or hybrid scheme which allows a user to specify certain intermediate addresses allows a process to force traffic over a particular network, perhaps in response to political, economic, or performance considerations: "take any reasonable path across the country, but I must use the Packet Satellite system across the Atlantic". More difficult, however, is selectively eliminating some paths from the routing decision: "take me to Europe, but don't ever go through Spain". Naming/Addressing/Routing and Internetwork Gateways The gateway function is. in general, performed in a machine which is connected to at least two networks, and which therefore has at least two addresses. Incoming packets which need to be forwarded may enter on any attached net, using any of the legal addresses.
9
Yet there is a single gateway process which handles all of this traffic, and
which is responsible for maintaining relevent [sic] routing tables.
It has been suggested that a gateway might be viewed as two completely
separate "halves" actually residing on different machines, connected by a
"thin wire" communications channel. We do not find this abstraction
particularly useful, since it does not easily account for the shared gateway
processes which actually perform the routing function.
In this model, the gateway processes maintain routing tables to reach network
areas through other gateways, but they do not attempt to maintain any other
state about networks, hosts, or connections. Thus, these intermediate
gateways -- using dynamic hop-by-hop routing -- will not be able to deal with
partitioned networks.
Material not covered in this note
Distribution lists, multi-destination packets, and broadcasting.
Ways we might modify area routing to more gracefully deal with partitioned
networks.
Internetwork fragmentation.
Internetwork flow control and congestion control.
Flow control between gateways.
Acknowledgements
The material in this note has evolved from many conversations with David
Boggs, Ed Taft, Bob Metcalfe, and Yogen Dalal; any clarity which has emerged
is due to their willingness to struggle with the semantic demons. Recent
conversations with Danny Cohen have been particularly useful in understanding
his proposal for hybrid routing schemes (where the source routing process
specifies only some of the intermediate stops), and the manner in which area
routing may obscure a preferred off-net route. Much of the commentary on
routing has evolved from [McQuillan 1974] and [Sunshine 1977]; the latter
paper is a partictilarly useful one, touching on many of the issues raised
here, although we tend to differ on some of the fine points.
Bibliography
[AT&T 1975]
AT&T, 'Notes on Distance Dialing', 1975.
[McQuillan 1974]
J. M. McQuillan, 'Adaptive routing algorithms for distributed
computer networks', BBN Report No. 2831, May 1974.
[Sunshine 1977]
Carl A. Sunshine, 'Interconnection of computer networks', Computer
Networks, 1977.
file: names.b
January 29, 1978 8:02 PM
mirror server hosted at Truenetwork, Russian Federation.