IEN-183
Logical Addressing
Bolt Beranek and Newman Inc.
Eric C. Rosen
May 1981
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
Table of Contents
1 Introduction.......................................... 1
2 Translating Logical to Physical Addresses............. 7
2.1 Translation Locus................................... 7
2.2 Translation Methodology............................ 10
3 Organizing the Translation Tables.................... 17
4 Initializing the Translation Tables.................. 23
5 Updating the Translation Tables...................... 30
6 Operational and Implementation Considerations........ 49
7 Network Access Protocol Implications................. 53
-i-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
1 Introduction
This paper is a slightly modified extract from BBN Report
No. 4473, "ARPANET Routing Algorithm Improvement, Volume 1," by
Rosen, et al. It proposes a scheme for implementing logical
addressing in the ARPANET. However, the issues dealt with are
quite similar to the issues raised by the problem of implementing
logical addressing in the Catenet (several IENs are currently in
preparation in which we argued for this assertion at great
length.) It is hoped, therefore, that the discussion will be of
interest to internet workers as well.
In the current ARPANET, in order for a user to transmit
data to a particular host, he must know the PHYSICAL ADDRESS of
the host. That is, he must know which node the host is connected
to, and he must know which port on that node is used to connect
that host. Furthermore, this is the ONLY means a user has of
identifying a host. In many respects, the physical address of a
host computer can be compared to a person's telephone number.
The problems inherent to physical addressing in a computer
network are similar to those we would experience in ordinary
interpersonal communication if a person's telephone number were
the only means we had of identifying him. Dialing a particular
telephone number allows us to establish a communications channel
to a particular location. This works well as long as the person
-1-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
with whom we wish to communicate remains at that particular
location. When the person changes his location, though, the
phone number becomes virtually useless, and the physical address
of a host computer becomes equally useless if the computer's
location within the network changes. In the context of
interpersonal communication, this gives rise to the calling of a
"wrong number". In the context of computer networking, this can
give rise to the more serious phenomenon of mis-delivery of data.
Furthermore, when a computer changes location within a network,
it is quite difficult to carry out a procedure which reliably
informs all users of its new physical address. There are
difficulties in identifying all users, difficulties in contacting
them once they are identified, difficulties in making sure that
the information receives the proper level of attention once
contact is made, and if all these difficulties are resolved, it
is still difficult to make the necessary changes to computer
software so that the new physical address is actually put into
use.
There is another sort of problem would occur in
interpersonal communication if our only means of identifying a
person were by his phone number. It is very common for several
people to share a phone number. If we identified people only by
phone numbers, we could not distinguish among several people at
-2-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
the same location. This problem arises in computer networking if
several computers share the same port. There are, in fact,
several reasons why it may be desirable to allow several
computers to share the same port. One reson is simply the need
to get by with a less than optimal amount of equipment, either
due to economics or to shortage. If some administration has two
computers, each of which needs to be on the network only part of
the day, but which do not need to be on the network at the same
time, sharing a single port may be the best solution. The
increasing cost-effectiveness of such devices as port expanders
and local networks may also make it more and more desirable to
have several computers sharing the same port. A related problem
arises if one thinks of a network of computers as consisting of
"logical hosts," rather than physical hosts. Whereas a physical
host would be a particular piece of hardware, a logical host
would be the instantiation of a particular function. Thus a
physical host which supported (for example) time-sharing during
the day and batch processing at night could be regarded as two
logical hosts which share the port on a time-division basis. A
related application is the situation in which the functionality
of two (small) physical hosts is combined into one (larger)
physical host, which then can be thought of as consisting of two
logical hosts. It could be very useful to have the flexibility
to move logical hosts freely around the network, perhaps changing
-3-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
the correspondence between particular logical and physical hosts,
without having to inform all users of the new physical addresses.
Of course, the reasons these problems in computer
networking are more serious than the analogous problems in
interpersonal communication is that telephone numbers are not the
only, or even the primary, means we have of identifying other
people. We can identify other people by NAME, and this greatly
facilitates our ability to get in touch with people even as they
change location. It also enables us to specify the individual we
wish to talk to, in the situation where several people share a
telephone. Similar advantages would accrue if we could identify
computers by name rather than by physical address. In order to
get our data to the appropriate computer, its physical address
would still have to be determined. But the user should be able
to tell the network the name of the appropriate computer (perhaps
a logical rather than a physical host), and let the network
itself map the name to its physical address. For speed and
reliability, the mapping function should be accomplished
automatically (i.e., by software) with minimal need for human
intervention. Schemes to accomplish this are known as LOGICAL
ADDRESSING schemes, and the name of a computer is usually
referred to as its "logical address" (though in fact, logical
addresses are not addresses at all, since they, like names, are
-4-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
independent of location).
A good logical addressing scheme should allow more
flexibility than may be already apparent. We have spoken of the
need to be able to identify a computer in a way which is
independent of location, and of the need to be able to map
several distinct names onto a single physical address. There is
also a need to be able to map a single name onto several physical
addresses. To carry out the analogy with interpersonal
communication, this would correspond to the case where a single
person has several telephones, with different phone numbers,
possibly at different locations. This adds reliability to the
communications process, since if the person cannot be reached at
one phone number, perhaps he can be reached at another. If he
can be reached at each of the numbers, he now can handle several
conversations simultaneously, i.e., he has increased throughput.
In computer networking, this sort of application is known as
"multi-homing." In multi-homing, a single computer connects to
the network through several ports, usually (though not
necessarily) at several different network nodes. This allows the
computer to remain on the network even though one of its access
lines, ports, or home nodes fails, thereby increasing
reliability. In the case where it is more economical (or
otherwise more practical) to obtain several low-speed access
-5-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
lines than to obtain a single high speed line, multi-homing can
also allow a given host computer to obtain higher throughput at
less cost.
Another sort of application which requires a single name
to map into several physical addresses can be compared to a
business which has several branch offices, each with a different
phone number, but whose customers do not care which branch office
they reach. This can be useful in certain sorts of internetting
applications. Suppose, for example, that an ARPANET user wants
to send a packet to SATNET, but that there are several equally
good gateways between the two networks. It may be convenient for
the user to simply specify a name like "Gateway-to-SATNET" and
let the network choose which of the several gateways (i.e.,
physical addresses) to use. A related sort of possible
application has to do with distributed processing and resource
sharing. If some particular resource is available at any of
several locations around the network, it may be desirable to
allow the user to specify the resource by name, and allow the
network to map that name onto some particular physical address
according to criteria that the user need not be aware of. (Such
a service was formerly offered by the ARPANET TIPs. By typing
@N, a user would be connected to a "Resource-Sharing Executive"
on one of several network TENEX systems. The user, however,
-6-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
would have no way of knowing which system he was actually on.)
2 Translating Logical to Physical Addresses
2.1 Translation Locus
It should be obvious that any implementation of logical
addressing would require the network to maintain a translation
table. The user would specify a logical address, and the network
would use this logical address as an index into the translation
table in order to obtain the physical address (or list of
physical addresses) to which it corresponds. The network would
use the physical address internally to determine the routing of
user messages. The need to maintain a translation table gives
rise to a multitude of design issues. The first question that
needs to be answered is, where should the translation table be
located? Should every node maintain a copy of the whole
translation table, or should there be just a few copies of the
table scattered around the network in strategic locations? If
there are only a few copies scattered around the network, then
nodes which do not contain the tables would have to query the
nodes that do in order to perform the translation function. This
is less efficient (both in terms of overhead and response time)
than placing the table in every node. Considerations of
-7-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
reliability and survivability also favor placing the table in
every node. This eliminates the possibility of finding that, due
to network partition, all copies of the translation table are
inaccessible. It eliminates the need to have some nodes serving
as hot or cold standby for the nodes which do have the tables.
This is an important advantage, since the protocols needed to
implement "standby" tend to be slow and cumbersome, or else
unreliable. Furthermore, if all nodes maintain identical copies
of the translation table, there is no need to go through any
special initialization procedure for creating the table when a
node first comes up. Typically, a node which is just coming up
has been reloaded from a neighboring node. If all nodes have an
identical copy of the table, a node coming up can simply have its
table reloaded from its neighbor, i.e., can copy its neighbor's
table. (Under certain unusual conditions this may give rise to a
race condition, but as we shall see later, it is a race that can
be easily remedied and one that will not have any bad effect
other than to slow the reload process.)
There is, however, a possible disadvantage to having the
tables in every node. That is simply the need to have enough
memory in every node to hold the table. In certain networks,
particularly commercial ones, the network nodes may be of widely
varying sizes and capabilities, and the smaller nodes just may
-8-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
not be able to hold the complete translation table. Such
networks would necessarily have a hierarchical structure
(probably with some form of hierarchical routing), and a node
would not be able to hold a translation table unless it were at
or above a certain level in the hierarchy.
Strictly speaking, only those nodes which will ever need to
translate a logical address to a physical address will need to
have a copy of the translation table. Whether that is all nodes
or only a subset of the nodes depends on the translation
methodology that we adopt. We have a choice between requiring
translation to be done only at the source node, or requiring it
to be done also at tandem nodes. In the former case, when the
user presents some data to the network and specifies its
destination with a logical address, the source node looks in the
translation table, gets the physical address, places the physical
address in the packet header, and sends the packet on its way.
Tandem nodes do not look at the destination logical address at
all, but only at the physical address. In the other case, each
tandem node looks at the logical address, does its own
translation to physical address, and routes the packet on that
basis. The packet header would not even have to contain the
physical address. If we do source translation only, the only
nodes which need to contain translation tables are those that
-9-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
connect to hosts which use logical addressing. If these nodes
are only a subset of all the nodes, then it may be feasible to
configure these nodes with more memory than the others.
Therefore, we must look at the advantages of source node vs.
tandem node translation.
2.2 Translation Methodology
Clearly, in the case where a logical address maps to a
unique physical address, source node translation is superior to
tandem node translation. As long as there is only one possible
physical address for that logical address, all nodes will produce
exactly the same mapping. There is thus no advantage to
performing the mapping several times, and the scheme which does
it only once is more efficient. There is, however, one exception
to this. When the translation tables need to be updated, we
cannot expect all copies to be updated simultaneously. There
will necessarily be some short interval of time when not all of
the copies of the table around the network are identical, and
during this interval, tandem node translation may yield different
results than source node translation. It will certainly be
necessary to design some mechanism to deal with this problem, and
we shall propose one shortly for the ARPANET environment. Tandem
node translation, however, is not the right solution to this
-10-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
problem. During the transient period, some copies of the table
will be right (up to date) and some wrong (out of date). But the
copies at the tandem nodes will be no more likely to be right
than the copy at the source node, so tandem node translation
would be as likely to amplify the problem as to reduce it. The
solution to this problem lies elsewhere.
In the case where a logical address maps to several
physical addresses (multi-homing), tandem node translation might
well give different results than source node translation.
However, we must now distinguish between virtual circuit and
datagram traffic. If virtual circuit traffic is logically
addressed, all translation must be performed at the source node.
In fact, the translation must be performed only once, at
connection set-up time. This is the only way to ensure that all
traffic on a given circuit is sent to the same physical address,
which in turn is the only way to provide the sequencing and
duplicate detection that is the RAISON D'ETRE of virtual circuit
traffic. (Additional issues having to do with logically
addressed virtual circuit traffic will be discussed later.) Thus
the only possible advantage of tandem node translation would have
to do with datagram traffic which is destined to a multi-homed
logical address. To understand the differences, though, between
source node and tandem node translation, we must first discuss
-11-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
the criteria which a node uses to pick one physical address out
of the several that are available. Even though a host is multi-
homed, any particular packet for it can go to only one of its
physical addresses; some criterion for choosing the proper one in
each particular case must therefore be available. Several
possible criteria come readily to mind:
a) When there are several physical addresses
corresponding to a given logical address, it may be desirable to
send packets to the physical address which is closest to the
source node, according to some metric of distance. For example,
if we are interested in minimizing delay, we may want to choose
the physical address to which the delay from the source is least.
If SPF routing is used, this information is readily available.
If we are interested in minimizing the use of network resources
by a particular packet (i.e., in maximizing throughput while
still using only a single path), we may want to choose the
physical address which is the least number of hops from the
source. (For these purposes, ties can be broken arbitrarily.)
Again, this information can be made readily available by the SPF
routing algorithm (although it is not readily available from the
ARPANET's particular implementation of that algorithm, since a
table of hop-counts is not saved). If either of these criteria
is used, tandem node translation can result in better route
-12-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
selection for the logically addressed datagram. If delay changes
or topology changes take place while a packet is in transit, it
may happen that the "closest" physical address to some tandem
node is different from the physical address that was closest to
the source node when the packet first entered the network. It is
easy to prove that, if SPF routing is used, this cannot result in
looping, except as a transient phenomenon while a routing update
is traversing the network. That is no particular disadvantage,
since a packet may be subject to that sort of transient looping
even when its destination physical address does not change.
However, it is not clear that tandem node translation provides
much of an advantage either, especially when one takes into
account the additional overhead of doing the re-translation at
each tandem node. Doing translation at tandem nodes will
necessarily increase the nodal delay and decrease the nodal
throughput. These negative effects may outweigh the positive
effects of improved route selection for those relatively rare
cases in which delay or topology changes significantly while a
packet is in transit. We must remember that although real
improvements in route selection would only occur rarely (since
delay and topology changes are very infrequent when compared with
average network transit times), re-translation would have to be
done for EVERY logically addressed datagram. Unfortunately, all
these effects are extremely difficult to quantify with any degree
-13-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
of confidence. Our (somewhat intuitive) conclusion is that,
under the selection criterion of choosing the closest physical
address, tandem node translation offers at best a small
improvement over source node translation, and at worst a severe
degradation.
b) It is possible that some multi-homed hosts will want
to establish an inherent ordering to their ports. That is, they
may prefer to receive all their traffic on port A, unless that
port is inaccessible to the source of the traffic, in which case
they prefer to receive all traffic on port B, unless that port is
inaccessible to the source of the traffic, in which case they
prefer to receive all traffic on port C, etc. This sort of
strategy may be appropriate if certain of the host access lines
are charged according to a volume-based tariff, while others are
not. It may also be appropriate if certain of the access lines
can be used more efficiently (i.e., can be serviced with less
host CPU bandwidth) than others. (An example might be a host
which can access the ARPANET through an 1822 line and a VDH line.
It might be desirable to avoid the VDH line, unless absolutely
necessary, since VDH lines tend to be used less efficiently.) In
either case, the idea would be to reduce cost by favoring certain
ports over others, using the more expensive ports only when
needed for purposes of reliability or availability. Thus we may
-14-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
want the logical addressing scheme to support an inherent
ordering among the several physical addresses which correspond to
a given logical address. With this scheme, there is no advantage
to doing tandem node translation. There will be only one
ordering for the set of physical addresses corresponding to a
logical address, so tandem nodes should always pick the same
physical address as the source node picked, and re-translation
would simply be a waste of resources. There are only two
exceptions to this. The first exception would arise in the
situation where a particular physical address becomes
inaccessible as a packet routed to that address is traversing the
network. However, since this can happen no matter what criteria
are used for choosing among the physical addresses, we put it off
for later consideration. The second exception would arise if the
translation tables were being updated while a packet is in
transit. Clearly, some procedure to deal with this case must be
devised, since the update which is taking place may invalidate
the translation which was done at the source. Tandem node
translation is not the proper solution, however, since there is
in general no reason to believe that the tandem node is more up-
to-date than the source node. We will return to this issue when
we discuss the table updating procedures.
c) Certain multi-homed hosts may have a preference for
-15-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
receiving certain kinds of traffic over particular ports. Thus a
dual-homed host may consider one of its ports more suitable for
receiving batch traffic, and another more suitable for receiving
interactive traffic (perhaps the first port offers a higher speed
but a longer delay than the second). However, if one of the
ports is inaccessible from a particular source node, that node
would send all its traffic (both kinds) to the port which remains
accessible. With this criterion, we see once again that tandem
node translation offers no benefits, since, barring the case of a
port becoming inaccessible while a packet is in transit, all
tandem nodes would select the same physical address as the source
node.
d) Some multi-homed hosts may wish to try to keep their
several access lines as equally loaded as possible. One possible
way to do this would be to establish an inherent ordering to the
ports (as in b, above), but to make the ordering different for
different source nodes (or hosts). Clearly, this scheme requires
source node translation; tandem node translation would only serve
to defeat it. Another possible way to achieve some sort of load
leveling would be for each source node to send traffic to the
various physical addresses on a round-robin basis. This would be
a very crude form of control, but might work reasonably well for
particular traffic patterns. This scheme also requires source
-16-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
node translation. In fact, tandem node translation could
actually cause packets to loop endlessly.
We see then that none of the suggested selection criteria
give any very large advantage to tandem node translation, and
some of the criteria are actually in conflict with re-translation
at tandem nodes. Thus it is not necessary for all notes to hold
the translation tables; only those nodes connected to hosts which
use logical addressing need hold the tables. Of course, it is
still possible that the tables will be too large to be held in
any one node, in which case we would have to use distributed
database techniques to split the tables among several nodes. We
will not consider that further here, but we will consider it in a
future IEN.
3 Organizing the Translation Tables
Another issue having to do with the translation tables is
the way in which the tables should be organized. Clearly we do
not want the entries in the table to be in random order,
necessitating a lengthy linear search each time a translation
must be done. Basically, there are two possible ways to order
the table. We can sort the table by logical address, and do a
binary search of the table whenever we need to do a logical-to-
-17-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
physical address translation. This is a rather efficient form of
searching, but it causes inefficiencies when table entries have
to be inserted or deleted, since that would require a potentially
time-consuming expansion or compression of the table. There are,
however, ways of reducing the overhead involved in
insertions/deletions. Deletions could be made "logically", i.e.,
by marking an entry deleted, rather than physically compressing
the table. New entries could be inserted into an overflow area,
which itself would be searched linearly whenever a particular
logical address could not be found in the main table. Actual
compression/expansion of the main table would be done only when
the overflow area filled. Note, however, that this sort of
strategy would necessarily complicate the search algorithm, and
this might actually do more harm than good, especially if
insertions and deletions are rare events. We shall see later,
when we discuss the conditions under which insertions and
deletions are required, that these are indeed rare events. We
conclude tentatively that, if a sorted table with binary
searching is used, the use of an overflow area is probably not
necessary.
The other possibility for organizing the table is to use
hashing. A good hashing algorithm (i.e., one which minimizes
collisions) provides very efficient insertions and very efficient
-18-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
searches. Deletions are not quite so efficient, but are still
more efficient, in general, than the table compression required
if binary searching is used. However, hashing has certain
inherent problems which may make it less suitable. Choosing a
hashing algorithm which both minimizes collisions and is
computationally efficient is not a simple matter. One must be
sure that the time needed to perform the hashing is really less
than the average time needed to find an entry in a sorted table
by means of binary searching; otherwise, the efficiency is lost.
Furthermore, the number of collisions generated by a particular
hashing algorithm will depend on exactly which set of logical
addresses are in use. The set of logical addresses in use during
a network's lifetime will be a slowly changing set, and a hashing
algorithm which is excellent at one time may give poor
performance at another. Hashing algorithms are also subject to
undetected programming bugs in a way in which binary search
algorithms are not. A bug which is inserted into a hashing
algorithm, which, for example, causes all entries to hash into
the same bucket, might go undetected for years, although it would
cause a significant performance degradation by reducing the
efficiency of the hashing technique to that of linear searching.
A bug in the binary search algorithm, however, would be more
likely to come to someone's attention. Its probable result would
not be performance degradation, but rather, failure to find
-19-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
certain entries. This would cause inability to deliver traffic
to certain logical addresses, and this would certainly come to
the users' attention very quickly. These qualitative reasons
would seem to indicate that binary searching is preferable to
hashing. It would also be useful to do some quantitative
analysis; that may be done at a later stage of our research.
Someone may wonder why we have not considered a much
simpler method of organizing the tables. Logical addresses,
after all, are just numbers (or at least are representable as
numbers). If the set of logical addresses in use at any given
time is a contiguous set of numbers, then the addresses can be
used as indexes directly into a translation table, with no need
either for hashing or for sorting. The problem, of course, lies
in the requirement that the set of logical addresses form a
contiguous set of numbers. Assigning numbers to hosts
contiguously may not be a problem in itself, but it does cause a
problem as soon as some host is removed from the network. Its
number (or numbers, if it has several logical addresses) cannot
be left unused, or the size of the translation table would be
determined not by the number of logical addresses currently in
use in the network, but rather by the number of logical addresses
that have ever been in use in the network, a number which may be
much larger, and which in fact has no bound. Yet it is not
-20-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
acceptable simply to reassign the same logical addresses as hosts
enter or leave the network. We all have some experience with
moving to a new location, getting a new telephone number, and
finding ourselves frequently getting calls intended for the
person who previously had that number. Such calls may persist
for years, especially if the number previously belonged to a
business. Receiving phone calls or mail intended for someone
else who happens to have the same name as we do is also a
familiar occurrence. We would expect analogous problems if
logical addresses are reassigned (at least, if they are
reassigned without some very long waiting period), especially if
the logical address previously belonged to a large service host.
When a user tries to address a host which is no longer on the
network, he should receive some indication of that fact; he
should NOT have his data mis-delivered to some other host which
has been assigned the same name. Thus it is preferable to have a
logical addressing scheme which does not depend on the logical
addresses forming a contiguous set of numbers.
Whatever means of organizing the table is chosen, it may
still be useful to maintain a smaller table for use as a "cache."
The cache would contain the n most recently used logical
addresses (where n is some small number), together with a pointer
to the absolute location of that logical address entry in the
-21-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
main translation table. When it is necessary to do translation,
the cache would be searched before the main table. The
assumption is that once one packet for a particular logical
address is received from a source host, many more will follow.
Thus it pays to optimize the search for that particular logical
address. Choosing the optimum size for the cache, and the means
of searching it (linear or binary) are issues left for later
resolution. These issues must be dealt with carefully, however;
one would not want to find that searching the cache takes as long
or longer than searching the main table. It is worth emphasizing
that the cache should contain a pointer into the main translation
table, rather than a copy of the list of physical addresses
associated with a particular logical address. For multi-homed
logical addresses, this is more efficient, since it involves less
copying. Also, if there are variables associated with the
physical addresses, this enables unique copies of the variables
to be kept in the main table. (Suppose, for example, that
packets are to be sent on a round-robin basis to the several
physical addresses corresponding to a multi-homed logical
address. This requires a variable to be associated with each
physical address, indicating whether that physical address was
the last one to be sent data. This variable must be kept in the
main table, not the cache, since one cannot rely on a particular
logical address always being present in the cache.) This means,
-22-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
of course, that the cache must be cleared whenever there are
insertions or deletions into the main translation table, but that
should not be very expensive as long as such insertions and
deletions are relatively rare.
4 Initializing the Translation Tables
We turn now to the issue of how the translation table
entries are to be set up in the first place. That is, what
procedure is to be used for establishing that a particular
logical address is to map to a particular set of physical
addresses. One possibility for the ARPANET, of course, is to
have all the mappings set up by the Network Control Center (NCC).
This is quite reasonable in certain cases. If some user wants
his computer to be addressable by some new logical address (i.e.,
by a logical address not previously in use), it makes sense to
have him contact the NCC directly. If the user has proper
authorization, the NCC can then take action to set up the new
entry in all the translation tables. A similar procedure would
also be appropriate if some logical address is to be totally
removed from the translation tables (i.e., that logical address
will no longer be in use in that network). This procedure would
also be appropriate when a particular computer is moved from one
location to another, necessitating a change in its logical-to-
-23-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
physical mapping, or if the functionality of two computers is
combined into one, so that two logical addresses which formerly
mapped to distinct physical addresses now map to the same
physical address. What all these cases have in common is that
they are relatively infrequent (i.e., occurring on the order of
days, rather than on the order of minutes), and they require
considerable advance planning. The first of these
characteristics ensures that NCC personnel will not be swamped
with translation table changes. The second of these
characteristics makes it feasible to coordinate such changes in
advance with the NCC. Unfortunately, not all translation table
changes have these characteristics. For example, we have
suggested that a good logical addressing scheme should facilitate
port-sharing. That is, some user might want to unplug one of his
computers from the network and use that port for another
computer. He should be able to do this without much advance
planning, and without having to explicitly coordinate with the
NCC. As soon as the change is made, users who are logically
addressing the first computer should be told that it is no longer
on the network; only the logical address of the second computer
should map to this port. If this change in the mapping does not
take place immediately, the result can be mis-delivery of data,
as packets which are logically addressed to the first computer
get mis-delivered to the second. A similar situation arises if
-24-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
some computer consists of several "logical hosts." Logical hosts
may come and go quite frequently, with no advance planning at
all. The logical addressing system should be able to adapt
immediately to such changes, without any need for human
intervention. A related situation arises in the case of logical
addresses which are multi-homed. We have already discussed
various possible criteria for choosing among the several physical
addresses associated with a single multi-homed logical address.
But before applying these criteria, any physical addresses which
are "inaccessible" from the source node must be excluded. If
some host has two access lines into the network, and one of them
is inaccessible from a particular source node, then all traffic
from that source node should be directed to the other access
line. Indeed, this is one of the most important purposes of
multi-homing. This implies that a source node must have some way
of knowing that a certain physical address is not currently
accessible. There are basically two classes of reasons why a
given physical address might be inaccessible from a source node.
The first is that there is no path from the source node to the
destination node (either because the network is partitioned, or
because the destination node is down). This information is
readily available from the routing tables, and need not be kept
in the translation tables. It is simple enough to check the
routing tables when choosing one from a set of physical
-25-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
addresses. The other reason why a physical address might be
inaccessible is that the port itself, or the access line from the
port to the host, has failed. Functionally, this is the
equivalent of unplugging the host from the port. It may happen
quite frequently, however, and certainly with no advance
planning. As long as the node itself is up, the routing
algorithm will give no indication that the port is inaccessible;
this information must somehow get into the translation tables.
Clearly, we do not want to depend on human intervention to ensure
that this sort of change gets made in the translation tables.
What is needed here is a quick and reliable means of making
changes in the translation tables, not the cumbersome and
unreliable method of contacting the NCC. The same problem arises
when the inaccessible port becomes accessible again. One wants
to be able to begin using this port again as soon as possible,
without having to wait until NCC personnel have time to make the
appropriate changes in the translation tables. So although
certain sorts of changes to the translation tables can be made by
the NCC, many sorts of changes will occur suddenly and
unexpectedly, and need to become effective immediately. So the
procedure of having all translation table changes made by the NCC
is not satisfactory.
There is another sort of problem with having translation
-26-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
table changes made by the NCC. The problem is that carelessness,
either by the NCC or by host site personnel, can result in mis-
delivery of data if changes are made by the NCC. Suppose, for
example, that a network controller makes a typographical error,
associating a logical address with an incorrect physical address.
If there is no further check on the validity of that mapping, one
computer may receive data intended for another. A good logical
addressing scheme should prevent this sort of simple
typographical error from resulting in mis-delivery. The same
situation can occur if one computer is carelessly plugged into
the wrong port. In this case, networks which use only physical
addressing might also mis-deliver data. However, with physical
addressing, one must expect mis-delivery if some computer is
plugged into the wrong port (i.e., given the wrong physical
address) due to carelessness. With logical addressing, this is
not inevitable, and a good scheme should give better protection
against carelessness.
Another possibility for setting up the translation table
entries is to have each host, as it comes up on the network, tell
the network which logical addresses it wants to be addressed by
over each of its (physical) ports. This would require
augmentation of the host access protocol to include a "Logical
Address Declaration" (LAD) message. A given host could put as
-27-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
many logical addresses as it wanted in each LAD message. Multi-
homed hosts would send the same LAD message over each of their
ports. The logical addresses specified in the LAD message
received over a given port would all be mapped to that particular
physical address. Hosts would be allowed to change their logical
addresses at any time by sending a LAD message to the network.
Since a host may wish to add or delete logical addresses for
itself at any time, there would have to be two options for the
LAD message -- "add" and "delete." Whenever a particular port
goes down (either because the port itself fails to function
properly, or because the access line between the network and the
host fails, or because the host itself crashes), all mappings of
logical addresses to that port would be cancelled. When the host
can once again communicate with the network through that port, it
would have to redeclare its logical addresses with a LAD message
before it could receive any logically addressed traffic.
Allowing each host to set up its own logical-to-physical
address mappings in this manner has several advantages over
having all the mappings set up by the NCC. This procedure allows
sudden and unplanned mapping changes to take effect immediately,
with no need for advance planning and coordination with the NCC.
Since the mappings are cancelled immediately when a port goes
down, this procedure helps to ensure that, if one of a multi-
-28-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
homed host's ports is down, all data which is logically addressed
to that host will go to the other ports. If one host is
unplugged from a given port, and another plugged in its place,
the procedure ensures that the mapping for the first host is
cancelled, while the mapping for the second host becomes
effective. When a host goes down, there is no assumption that
the same host will return in the same location. Hence
carelessness on the part of site personnel or NCC personnel
cannot result in mis-delivery of data; data which is logically
addressed to a certain host could only be delivered to a host
which has declared itself to have that logical address.
There are, however, two quite serious problems with this
procedure. The first problem is that of spoofing. That is, this
procedure offers no protection against the situation where one
host declares itself to be addressable by a logical address which
is supposed to be the logical address of a different host. Thus
the procedure allows one host to "steal" traffic intended for
another, simply by declaring itself to have the same logical
address as the other. This sort of spoofing might be done by a
malicious user, who is really trying to steal someone else's
data, or it might happen accidentally, as a result of programmer
or operator error. In either case, we would like to have some
procedure which is less prone to spoofing. The other serious
-29-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
problem with this procedure is that it can easily cause the
translation tables to overflow in size. If every host can
specify an uncontrolled and unlimited number of logical addresses
for itself, there is no bound on the size of the translation
tables. Since only a finite amount of memory will be available
for the translation tables, it is clearly not acceptable to allow
each host to specify an arbitray number of logical addresses for
itself.
5 Updating the Translation Tables
We have examined two different procedures for setting up
the logical-to-physical address mappings, and have found that
they both have problems. Many of these problems can be resolved,
however, by a combination of the two procedures. Let us define
two characteristics of a logical-to-physical address mapping,
which we will call "authorized" and "effective." A mapping from a
particular logical address to a particular physical address is
"authorized" if a host which connects to the network at that
physical address is allowed to use that logical address.
Authorizations would change very infrequently, and only after
considerable advance planning. Hence it is appropriate for
authorizations to be determined (i.e., added and deleted) by the
NCC. A mapping from a particular logical address to a particular
-30-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
physical address would be said to be "effective" from the
perspective of a given source node if (1) that mapping is
authorized, (2) that physical address is accessible from that
source node, and (3) the host at that physical address has, by
means of a LAD message, declared itself to have that logical
address. When a port goes down, all mappings to it will become
ineffective, until they are made effective again by means of a
LAD message. Logically addressed traffic will not be delivered
to a particular physical address unless the mapping between that
logical address and that physical address is effective. Changes
in the effectiveness of a mapping will occur automatically, in
real-time, with no need for intervention by NCC personnel. This
facilitates multi-homing, since if there are two authorized
mappings of a logical address to a physical address, and only one
is effective, that one can be chosen all the time until the
second becomes effective also. It facilitates sharing of ports
(either by physical or by logical hosts), since each host has
control over the effectiveness (though not the authorization) of
the mappings that affect it. Carelessness by NCC personnel can
cause the wrong mappings to become authorized, but it is rather
unlikely that an incorrectly authorized mapping could become
effective -- that would require carefully planned malicious
intent. Therefore, such carelessness might prevent delivery of
data to some host, but would not cause mis-delivery of data.
-31-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
Carelessness by site personnel, such as plugging a host into the
wrong port, would not cause mis-delivery of data, since the
mapping of that host's logical address to that particular port
would not be authorized. The possibility of spoofing is greatly
reduced; since host A cannot pretend to be host B unless it is at
a port which is already authorized for host B. The size of the
translation table cannot increase without bound, since that is
determined by the number of authorized mappings, and cannot be
increased by LAD messages. This means, of course, that the
network access protocol must be further modified so that it can
provide positive and negative acknowledgments for the LAD
messages. For each logical address that a host specifies for
itself in a LAD message, the network must return either a
positive or a negative acknowledgment. The positive
acknowledgment would indicate that the mapping is authorized and
has become effective. The negative acknowledgment would indicate
that the mapping is not authorized.
It must be emphasized that the suggested procedures are
not intended to provide security in any very strict sense. For
networks in which security is a very important issue (e.g.,
AUTODIN II), further study of these issues should be carried out
by security experts.
It should also be emphasized that these procedures will
-32-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
allow the logical addressing scheme to continue to function
normally even if the NCC facilities are down. It does require
centralized intervention to add or delete authorizations, and
this could not be done if the NCC were down. For a fixed set of
authorized mappings, however, no centralized intervention is
required to determine the effectiveness of the mappings. That
is, the real-time functionality and responsiveness of the logical
addressing scheme does not depend in any way on the proper
functioning of the NCC.
We have argued that the authorization of a mapping should
be determined by the NCC, and the effectiveness of a mapping
should be determined by the network node which contains the
physical address (port) to which the mapping is made, in
cooperation with the host that is connected to that port. We
have also argued that a full translation table (i.e., a table
containing all the effective mappings) should be stored at each
network node (or more precisely, at each network node which
serves as an access point for a host which can be either a source
or a destination of logically addressed traffic). However, we
have not yet discussed the algorithm by which the effectiveness
or ineffectiveness of a particular logical-to-physical address
mapping is communicated to all network nodes. We turn now to
this issue. We will discuss two very different methods for
-33-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
building up the translation tables at all nodes.
The first method is based upon an extension of the SPF
routing algorithm, wherein each logical address is treated like a
stub node. In this method, each node is initialized with a
partial translation table. This table contains a list of all the
logical addresses which are AUTHORIZED to map TO that node,
(i.e., all the logical addresses which correspond to ports at
that node). Each of these logical addresses is associated with a
particular port or ports at that node. At initialization time,
each of these logical addresses is treated just as if it is a
neighboring node which is down, and the node sends an update
(similar to a routing update) to all other nodes, indicating that
all authorized mappings to itself are ineffective. When a host
comes up over a particular port, it declares its logical
address(es) by means of one or more LAD messages. The node then
checks its table of authorized mappings, and acknowledges to the
host (either positively or negatively) each logical address
mentioned in the LAD message. Whenever a logical address is
positively acknowledged, it becomes effective, and the node must
broadcast an update to all other nodes declaring that mapping to
be effective. Whenever a host declares (via a LAD message) that
it no longer wants to be addressable by a particular logical
address, an update must be generated declaring that mapping to be
-34-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
ineffective. Whenever a port goes down, all logical addresses
mapping to it become ineffective, and an update indicating this
must be broadcast. If the protocol used to disseminate these
updates is the same as the protocol used in the ARPANET to
disseminate the updates of the SPF routing algorithm, then all
nodes will be able to build dynamically an up-to-date table of
effective mappings, just as the routing updates enable them to
build an up-to-date topology table. (The procedure used to build
the topology tables is described in [1]. The updating protocol
is described in [2] and [3].) In effect, this procedure extends
the routing algorithm to treat the hosts (or more precisely, the
mappings of logical addresses to physical addresses) as stub
nodes, and the ports as lines, except that there is no delay
associated with a port, but only an up/down status.
This procedure is attractive from a conceptual point of
view, but it is not really cost-effective. That is, it seems to
be too expensive to be practical. One reason is that it is hard
to place a bound on the size of the updates. The updating
protocol of the ARPANET routing algorithm is quite efficient,
because the updates are so small. The maximum update size is
only 216 bits (from a node with 5 neighbors). The logical
addressing updates might be much longer, since there is no limit
on the number of logical addresses that may map to a given node.
-35-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
The updates would also have to be sent periodically, even when
there in no change in state. These features are necessary to
ensure reliability in the face of such events as partitions, node
crashes, updates received out of order, etc. With no restriction
on the number of logical addresses which can map to a given node
(and it seems unwise to build in such a restriction), there is no
restriction on update size, and hence no bound on the bandwidth
needed for updating, or on the extra delay which may be imposed
on data packets due to the need to transmit the updates.
The updating protocol which was designed for the SPF
routing algorithm was designed to get the updates to all nodes
very quickly, and with 100% reliability, even in the face of
various types of network failures. This extreme speed and
reliability is necessary for routing updates, since rapid and
reliable updating of the routing tables is necessary to ensure
the integrity of the network. Routing failures, after all, can
make the network completely unusable, and can be very difficult
to recover from, since most recovery techniques depend on the
NCC's ability to communicate with the nodes, which in turn
depends upon the integrity of the routing algorithm.
Fortunately, the protocol used for disseminating the logical
addressing updates does not need all the functionality of the
updating protocol used for routing, since the integrity of the
-36-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
logical addressing scheme is not quite as critical as the
integrity of the routing algorithm. This enables us to use a
simpler and less expensive method of maintaining the translation
tables, which we will now discuss.
In this second method, each node is initialized with a
translation table containing ALL the authorized mappings. This
table would have an entry for every logical address that can be
used in the network. Each logical address would be associated in
the table with all the physical addresses to which it has an
authorized mapping. Associated with each of these physical
addresses would be a Boolean variable indicating whether that
particular logical-to-physical address mapping is effective or
ineffective. At initialization time a node would mark all
mappings to itself as INEFFECTIVE, and all mappings to other
nodes as EFFECTIVE. Whenever a host declares itself, via a LAD
message, to have a certain logical address, the node looks in the
translation table to see if that mapping is authorized. (This is
just an ordinary table look-up, indexed off the logical address.)
If not, a negative acknowledgment is sent to the host. If the
mapping is authorized, a positive acknowledgement is sent, and
the entry in the translation table is marked EFFECTIVE. Whenever
a port goes down, the node marks all mappings to that port as
INEFFECTIVE. Of course, this also requires a "reverse" search of
-37-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
the table (i.e., a search based on a physical, rather than
logical address). To make this more efficient, when the initial
reverse search is done at initialization time, the node can save
a list of pointers into the translation table. Each pointer
would correspond to a physical address entry for that node. If a
separate table of pointers is kept for each port, the node will
be able to find in a very efficient manner entries which map to a
particular port. Using this methodology, each node's translation
table will correctly indicate, for each of the logical addresses
that map to IT, whether or not that mapping is effective. (Of
course, these pointers would have to be adjusted whenever table
insertions or deletions are made.)
When a source host sends a logically addressed datagram
packet into the network, the source node will search the
translation table for the correct mapping. If that logical
address cannot be found, i.e., its use is not authorized, an
error message indicating this fact should be returned to the
host, and the packet discarded. If that logical address is
found, but all the corresponding physical addresses are either
marked INEFFECTIVE, or else are unreachable (according to the
routing algorithm), then the packet should be discarded, and the
host informed of that fact. If some of the physical addresses
are both reachable (according to routing) and marked EFFECTIVE,
-38-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
then one should be chosen, according to some set of criteria
(perhaps one of those which we discussed above). The chosen
physical address should be placed in the packet header, along
with the logical address. The packet should then be forwarded to
its destination; in doing the forwarding, tandem nodes will look
only at the physical address. According to the procedure
described in the previous paragraph, all mappings to REMOTE ports
will be initially marked EFFECTIVE. To see how such mappings can
get marked INEFFECTIVE, we must see what happens when a logically
addressed packet reaches its destination node.
When a logically addressed datagram packet reaches its
destination node, the node looks up that logical address in its
translation table. It is possible, of course, that that logical
address will not be found at all, or that it will be found, but
that there will be no authorized mapping to this particular
destination node. This would indicate some sort of disagreement
between the translation tables at the source and destination
nodes. There are three possible causes of this disagreement:
(1) NCC error in setting up the translation tables, (2) deletion
of the authorization for that particular logical address while
the packet was in transit, or (3) a race condition, whereby a
translation table update authorizing the new logical address is
taking place, but the update has not reached that destination
-39-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
node yet. In any case, the data packet should be discarded
without delivery, and an error message should be sent to the NCC
indicating receipt of a packet with an unauthorized logical
address. This will alert NCC personnel to a possible error. If
the authorization for that logical address was deleted while the
packet was in transit, however, then the NCC need not take any
action; having the destination node simply discard the packet is
the correct procedure. If, on the other hand, that logical-to-
physical mapping is really authorized, but the update making the
authorization has not yet reached the destination node, then we
want to take the same action as we would take for a packet
delivered according to an authorized but ineffective mapping.
This action shall be described in the next paragraph.
Suppose that, upon looking up the logical address in the
translation table, the destination node does find an authorized
mapping to itself, but that mapping is marked ineffective. Then
there are two actions to take. The first action is to try to
re-address and then re-send the message. Of course, this can
only be done if the destination logical address is multi-homed,
and at least one of the corresponding physical addresses is
effective. If this is not the case, the packet must be
discarded. The second action is to send a special message back
to the source node of that datagram packet. We will call this
-40-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
message a "DNA message" (for "Destination Not Accessible"). The
DNA message will specify that the particular logical-to-physical
address mapping used for that packet is not an EFFECTIVE mapping.
The DNA message should also be sent in response to datagrams
which appear to have unauthorized mappings (see previous
paragraph). For reliability, each logically addressed datagram
must carry the physical address of its source node (though not of
its source host), so that the DNA message can be physically
addressed to the source node. It is not enough for the packet
simply to carry the logical address of its source host, for two
reasons. The first reason is that if the source host is multi-
homed, the destination node will not know which source node the
packet came from, and hence will not know where to send the DNA
message. The second reason has to do with the fact that one
situation in which DNA messages may have to be sent is the
situation in which the translation table at the destination node
has been set up erroneously. In this case, we do not want to
have to rely on the integrity of the translation table to ensure
proper delivery of the DNA message.
When a source node receives a DNA message indicating that
a certain logical-to-physical address mapping is ineffective, it
must find the proper entry in its translation table, and mark
that mapping as ineffective. Henceforth, incoming packets with
-41-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
that particular logical address will not be sent to that
particular physical address. If the logical address is multi-
homed, packets will be sent to one or more of the other physical
addresses, unless all the mappings for that logical address are
ineffective. If this is the case, packets for that logical
address will be discarded by the source node, which should also
return some sort of negative acknowledgment to the source host.
We see then that the DNA messages provide a feedback mechanism
which enables a source node to tell when a mapping to a remote
port is ineffective. The source node has no way to tell whether
this is the case, until it sends a packet to that port. After
sending the packet, it will be explicitly told by the DNA message
if the mapping is ineffective. If it receives no DNA message, it
assumes that the mapping is effective. This may mean, of course,
that some logically addressed packets are sent to a wrong
physical address. However, if there are other possible physical
addresses corresponding to that logical address, and the original
destination node has one of those other mappings marked as
effective, the packet will be re-addressed and re-delivered, so
there is no data loss. Note that there are two possible reasons
why a given logical-to-physical address mapping might be
ineffective: (1) the physical port might not be operational, or
(2) the host at that physical address might not have declared
itself addressable with that logical address. If desired, the
-42-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
DNA message can indicate which of these two reasons is applicable
in the particular case in hand. This information can be stored
in the source node's translation table, and passed on to source
hosts which try to use a logical address for which all the
mappings are ineffective.
This procedure enables all nodes to find out when a
particular authorized mapping is ineffective. We also need a
procedure to enable the nodes to find out when an ineffective
mapping becomes effective again (i.e., a port comes back up, or a
new LAD message is received at some remote site). A simple but
effective method is the following. At periodic intervals (say,
every 5 or 10 minutes) each node will go through its translation
table and mark ALL the entries which map to REMOTE ports to be
effective. (Entries which map to local ports will be marked
effective or ineffective according to procedures already
discussed. The current procedure will not apply to such
entries.) This enables mappings to be used again shortly after
they become effective. Of course, this scheme will result in
some packets being sent to the wrong physical address. When that
happens, however, a DNA message will be elicited, causing that
mapping to be marked ineffective again in that source node.
Furthermore, this scheme does not cause any unnecessary data
loss, since packets sent to the wrong physical address will be
-43-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
re-addressed and re-delivered, if possible.
Although this method requires all nodes to periodically
mark all mappings to remote ports effective, it is important to
understand that it does not require any time-synchronization
among the various nodes. Also, there is no reason why all the
mappings have to be marked effective at the same time. For
example, if the translation table contains 600 mappings, rather
than marking all of them effective every 10 minutes, it may be
more efficient to mark one mapping effective each second, thereby
cycling through the table every ten minutes (though if this
method is used, it must take account of table compressions and
expansions which may occur as the NCC adds or deletes
authorizations).
There is also an issue as to the exact methodology to be
used to send the DNA messages. The simplest method is for a
destination node to send a DNA message to the source node of each
packet which arrives as the result of an ineffective mapping. If
this method is used, there is no need to use a reliable transport
protocol in sending the DNA messages. If, for some reason, a DNA
message fails to get through to the source node, more packets
will arrive at the wrong destination node, causing more DNA
messages to be sent, until one of them finally gets through.
This method, however, might generate a virtually unbounded number
-44-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
of DNA messages, particularly in pure datagram networks with no
flow or congestion control. This in turn might contribute to
network congestion. In order to gain better control of the
throughput due to DNA messages, one could implement a scheme
which ensures that only one DNA per ineffective mapping per
source node can be sent within a certain time interval. This
scheme would have a significant cost in table space, however.
Also, it would require some sort of reliable transport protocol
(e.g., positive acknowledgments from the source node when it
receives the DNA message) to protect against the case where a DNA
message is lost in transit. This issue would have to be
carefully considered before any implementation is done.
The procedure to follow with virtual circuit traffic is
very similar. In the ARPANET, a single virtual circuit or
"connection" is individuated by the source and destination
physical addresses. The user takes no part in setting up a
connection; whenever a user sends a packet to the network which
is not a datagram, the network checks to see if a connection from
the user's physical address to the destination physical address
that he specified is already in existence. If not, the IMPs
automatically run a protocol to set up such a connection. With
logical addressing, we would want to redefine the notion of a
connection so that connections are individuated by source and
-45-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
destination LOGICAL address, rather than physical address.
However, translation would be done only at connection setup time.
Thereafter, all virtual circuit packets received by a given
source node with the same source logical address and destination
logical address would be sent on the same connection. If a
destination node receives a connection setup message for a
logical address whose mapping is ineffective, it will refuse the
connection, just as it would refuse a setup message for a
physical connection to a dead port. When the source node
receives the refusal message, it will mark that particular
logical-to-physical mapping as ineffective. If the destination
logical address is multi-homed, the source node can attempt to
set up the connection again, but with a different physical
destination address. If a mapping becomes ineffective after a
connection has already been set up, the destination node will
take action to reset the connection, also informing the source
node that the mapping is now ineffective.
Note that logically addressed virtual circuit packets
need not carry in their headers the logical addresses of either
the source or destination hosts, since that information can be
stored in the connections tables at the source and destination
nodes. Of course, all packets sent on a particular logical
connection will go to the same physical destination port.
-46-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
However, if the destination node or port goes down, and the
destination host is multi-homed, the above procedure
automatically ensures that a new connection will be opened to one
of the ports which is not down. Since the ARPANET connection
protocol is transparent to the user, the user need never know
that this has happened.
It is interesting to compare this procedure (based on DNA
messages) with the previously discussed procedures (based on an
updating protocol similar to that used for the SPF routing
algorithm). The latter procedure would ensure that all nodes
always agree (except during some very short transient period) on
precisely which mappings are effective and which are not.
Mappings would be marked effective (or ineffective) almost as
soon as they become so. There would be no need for the source
nodes to probe the destination nodes by sending data packets to
possibly incorrect physical addresses. The procedure we are
recommending does not have these features. In the recommended
procedure, different nodes' translation tables would not
necessarily be in agreement all the time as to which mappings are
or are not effective, and probing is necessary. This is an
acceptable situation though, since the sort of universal and
immediate agreement which is necessary to ensure the proper
functioning of a routing algorithm just is not needed to ensure
-47-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
the proper functioning of the logical addressing scheme.
However, THE LACK OF UNIVERSAL AGREEMENT DOES REQUIRE THAT
TRANSLATION BE DONE AT SOURCE NODES RATHER THAN TANDEM NODES,
since the DNA-based procedure, while designed to keep the tables
at source nodes up-to-date, will not necessarily have the same
effect at tandem nodes. (That is, DNA messages are sent to the
source nodes, NOT to tandem nodes.)
There is only one situation in which re-translation
should be done at the tandem nodes. Suppose a logically
addressed packet arrives at a tandem node, and that node, after
checking its routing table, sees that the physical destination
address of that packet is unreachable. If the packet is a
virtual circuit packet, or the tandem node does not implement
logical addressing (i.e., does not contain a translation table),
the packet must simply be discarded. But if the packet is a
datagram, and the tandem node does have a translation table, it
should re-translate the destination logical address, and re-
address the packet. This procedure can help to prevent
unnecessary data loss. Note that this tandem node translation
would happen only rarely, and only in situations in which it
could not serve to defeat the criteria according to which the
source node translation was done.
It should be noted that, with the recommended procedure
-48-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
(unlike the alternative), the size of the translation table at
each node is a function only of the number of authorizations.
That is, only changes in the authorizations require insertions or
deletions to the table. This justifies our previous claim that
insertions and deletions are relatively rare events.
It should also be pointed out that nothing in this
procedure prevents a computer from being multi-homed to a single
node.
6 Operational and Implementation Considerations
This procedure requires each network node to maintain a
full table of authorized mappings. There are operational
advantages to requiring all nodes to have precisely the same
translation table; this simplifies the process whereby one node
can be reloaded from another in case of failure, and reduces the
amount of site-dependent information that must be maintained in
the nodes. (In general, the more site-dependent information
there is, the larger the Mean Time to Repair will be.) We have
not spoken explicitly of the way in which NCC personnel add or
delete authorizations. This will require some protocol between
the nodes and the NCC. This protocol would be similar in some
ways to the protocol used to broadcast software patches or
-49-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
packages to the nodes. However, since we want to be able to make
incremental changes to the tables (rather than broadcasting an
entire new table each time a change must be made), the node will
have to contain routines to add to or delete from the tables.
The node may have to inhibit interrupts while modifying its
table, so that no translations are done while the table is in a
state of flux. Also, no reloads may be done from a node whose
table is in a state of flux. These last two restrictions are
needed to prevent race conditions; these restrictions are easily
implemented.
When the NCC makes a change to the table of
authorizations, it will want to receive some sort of positive
feedback, indicating that the change has indeed been made. One
method of doing this is to associate a sequence number with every
"add" or "delete" command. Each node could periodically report
to the NCC the sequence number of the last command that it fully
executed, and an entry could appear in the log whenever the
sequence number is other than expected. If the nodes refuse to
execute commands which are received out of sequence, this would
enable the NCC to determine whether each node has received the
correct sequence of commands.
If memory considerations make it impossible for each node
to contain a table of ALL authorized mappings, it is possible to
-50-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
get by with a shorter table. Strictly speaking, each node's
table need contain only the logical addresses which map to that
node itself, PLUS those logical addresses which the node's own
local hosts are allowed to use. While this smaller table may
take less memory, it would, however, increase the operational
difficulties of table maintenance. We have not yet said anything
explicit about the format of a logical address. We recommend use
of a 16-bit field for coding the logical addresses. This should
be enough to prevent bit-coding limitations from placing any
restriction on network growth. The only other information needed
in the translation table is (1) destination node physical address
(8 bits should suffice), (2) one bit for the
effective/ineffective variable, (3) enough bits to code the port
numbers, and (4) enough bits to code any variables needed to
implement the selection criteria used for multi-homed hosts.
This should not take more than two or three 16-bit words per
entry. If space is a problem, it is possible to shorten the
tables somewhat by deleting the port numbers. Strictly speaking,
port numbers are only needed by the destination nodes, and hence
need not appear in each node's copy of the translation table.
However, eliminating the port numbers from the common table
increases the amount of site-specific information in the tables,
which is a disadvantage in itself.
-51-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
It goes without saying that the use of logical addressing
has implications for the network access protocol. We have
already discussed one aspect of the network access protocol,
viz., the need for the host to send LAD messages to the source
node, and the need for positive and negative acknowledgments to
be returned to the host. A LAD message from a particular port
contains a list of logical addresses, with an indication for each
one as to whether the host wants the mapping of that logical
address to that port to be effective or not. When a host
declares a mapping to be ineffective, the source node must always
return a positive acknowledgment, and must mark the mapping
ineffective in its translation table. However, if the mapping is
not authorized (i.e., not in the translation table), the source
node should also return a warning to the source host, since host
error is likely. When a host declares a mapping to be effective,
the node will return either a positive or negative
acknowledgment, depending upon whether the mapping is authorized
or not. When a host declares an authorized mapping to be
effective, the node must mark it so. The host should be allowed
to send LAD messages to the node at any time, and they should
take effect immediately.
-52-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
7 Network Access Protocol Implications
The use of a logical addressing scheme also has
implications on the part of the network access protocol that is
used for ordinary data transport. When a source host passes a
message to its source node, the message leader must indicate
whether logical or physical addressing is desired (assuming the
network allows both). If logical addressing is desired, the
destination logical address must be indicated. The source node
must be able to discard that message (with an appropriate
negative acknowledgment) if there is no effective mapping for
that logical address. The source host must also be able to
indicate its own logical address, if it wants to make this known
to the destination host. (Since the source host may have several
logical addresses, it must explicitly choose one to be carried to
the destination host.) Again, the source node must be able to
negatively acknowledge and then discard the message if the
mapping from that logical address to the source host's physical
address is not effective. Alternatively, one may want to return
this sort of negative acknowledgment only if the source logical
address mapping is unauthorized, and allow the message to be sent
if the mapping is authorized but ineffective. If this is done, a
particular "logical host" may be allowed to send data, but not to
receive it.
-53-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
When a logically addressed message is passed from the
destination node to the destination host, the message header must
contain the destination logical address (since the destination
host may have more than one logical address), and the source
logical address, if any. This implies, of course, that the
source and destination logical addresses of datagram packets must
be carried across the network in the packet header. (For virtual
circuit packets, the logical addresses can be kept in the
connection blocks in the source and destination nodes.) The
internal packet header must also carry the physical destination
node number (for addressing at tandem nodes), and the physical
source node number (so that DNA messages can be returned without
having to rely on the integrity of the translation tables).
However, these physical node numbers need not be passed to the
destination host. Note that there is no need for the internal
packet header to carry source or destination port numbers, since
these are usually determined by the combination of physical node
number and logical address. In the case where a host is multi-
homed to a single node, the port numbers are not so determined,
but the destination node can make a choice of ports "at the last
minute," either by choosing according to one of the criteria
already discussed, or by choosing the port with the shortest
queue.
-54-
IEN-183 Bolt Beranek and Newman Inc.
Eric C. Rosen
[1] E.C. Rosen, J.G. Herman, I. Richer, J.M. McQuillan, ARPANET
Routing Algorithm Improvements -- Third Semiannual Technical
Report, BBN Report No. 4088, April 1979, chapter 2.
[2] J.M. McQuillan, I. Richer, E.C. Rosen, D.P. Bertsekas,
ARPANET Routing Algorithm Improvements -- Second Semiannual
Report, BBN Report No. 3940, October 1978, chapter 4.
[3] E.C. Rosen, "The Updating Protocol of ARPANET's New Routing
Algorithm," Computer Networks, February 1980, Volume 4, p. 11.
-55-