Jan 23, 1978
                                                            Danny  Cohen
IEN: 23
Notebook Section 2.3.3.7




                   On Names, Addresses and Routings
                   --------------------------------



DESTINATIONs  and  SOURCEs   of   communication   have   names.    These
destinations   and   sources  are  processes  which  exist  outside  the
communication subnet (e.g., in HOSTs) or inside it (e.g.,  in  GATEWAYs,
NET-NODEs, etc).

Names are not necessarily unique to destinations.  Certain processes may
have more than a single name.  There are two kinds of names, names which
specify a unique process and names which  specify  a  set  of  processes
(e.g., by capability).

A name tells WHO (or WHAT) the process is.

It is conceivable the names are arbitrary alphanumeric string suited for
human readability.

In addition to names, processes have addresses which indicate WHERE they
are.   Again, it is possible that several different names share the same
address, and also that the same name has several addresses.

In order to move messages from sources to  destinations,  not  only  the
address of the destination (i.e., where it is) has to be known, but also
HOW-TO-GET-THERE.  This knowledge is the ROUTING.

It is, obviously, possible that the same address can be reached by  more
than one route.

These beautiful definitions  of  NAMEs  (what),  ADDRESSes  (where)  and
ROUTING (how-to-get-there) are borrowed from John Shoch.

To  summarize:  destinations  and  sources  have   names.    Names   are
"converted"  into addresses, and addresses into routings.  However, none
of the above mappings is a one-to-one correspondence.

Names have to be unambiguous within a certain environment.

From outside of this  environment,  the  environment,  too,  has  to  be
specified   in  order  to  complete  the  name  specification  i.e.,  to
disambiguate it completely.  This is the essence of hierarchical naming.
A   very  similar  argument  holds  for  addresses.   Within  a  certain
environment addresses are unique, outside of it, the environment has  to

                                                    Page   2



be   specified   ("addressed")   too.    Obviously,   environments  have
names/addresses which are unique within some  bigger  super-environment,
out  of  which,  the super-environment has to be specified, too.  And so
on.

Note  that  in  general  address  (and  names)  are  hierarchical.   The
non-hierarchical  case  (or  the  "flat" situation) is a special case of
hierarchy, with depth equal to one, and width equal to the total  number
of addresses.

The mapping of names  to  addresses  cannot  be  computed,  and  can  be
resolved  only  by  reference  to  directories.   Hence names from which
addresses can be computed are not names in the true sense, but addresses
in disguise.

These directories may be  implemented  in  various  ways,  ranging  from
off-line   distributed   directories   (like   paper   based   telephone
directories) to online  centralized  services  (like  411)  even  by  or
utilizing some broadcasting techniques.

The sole purpose of addressing is to support routing.  The address which
tells  where  the  destination is, is only important for determining the
routing (i.e., how to get there).

The key question is who performs the mapping of addresses into routing.

Several avenues can  be  pursued.   (1)  Sources  supplying  the  entire
routing  from  source  to  destination  (source-routing),  or (2) source
supplying only the  name  (or  address)  of  the  destination,  and  the
communication  subsystem performing the routing (communication-routing),
and (3) a hybrid of the above, by the source supplying some intermediate
destinations  along the route, such that the communication subsystem can
perform the routing between these given destinations.

Note that (3) is a generalization of both (1) and (2).  If  done  right,
it  should  have the advantages of both, else it may have their combined
disadvantages.

There are  too  many  (obvious)  problems  associated  with  a  complete
source-routing,   (1),   which  are  amplified  in  dynamically  changed
networks.  Basically, the  user  is  faced  with  the  need  to  specify
completely  the  routing  whenever a message is sent.  Since most of the
information  needed  for  finding  the  routing  is  originated  in  the
communication  subsystem,  this  is  an  undue  burden  which  should be
minimized.

On the other hand the other extreme, the communication-routing, (2) , is
not problem-free either.

In the case  of  flat  address-spaces  too  much  knowledge  has  to  be
maintained,  with  all  the  problems  associated with this requirement.
Therefore, it is preferred  to  implement  hierarchical  addressing  and
hierarchical  routing, which matches it in a unique way.  As a matter of

                                                    Page   3



fact, it  seems  that  the  most  "natural"  avenue  is  to  follow  the
well-debugged   paradigm   of   the  telephone  system,  and  have  both
hierarchical  names,  which  are  uniquely  mapped   into   hierarchical
addresses.

One of the bigger drawbacks of this scheme is that it will  not  support
an application of INTERnet fast facilities in order to expedite INTRAnet
traffic, like using satellite links (which belong to SATnet) in order to
expedite internal coast-to-coast ARPAnet traffic.

Since the flat address space is a special case of the hierarchical  one,
we  would  like  to  treat  all address spaces as hierarchical ones, and
consider the argument  of  flat  vs.   hierarchical  as  optimizing  the
depth/width combination.

The disadvantage of a big flat name/address subspace (as  opposed  to  a
hierarchical  one)  is that it requires that large table of addresses be
maintained, that names/addresses be cleared before being  put  into  use
and  that  everyone  knows  about  everyone,  a requirement which is not
feasible to fulfill when the dimension of this space keeps increasing.

An example for a very flat name space is the social security number,  as
opposed  to  telephone  numbers  and  mailing addresses.  Note that this
space is a subspace of a bigger space which includes also SSNs (or other
unique IDs) of people in other countries.

Note that both telephone numbers and mailing addresses  are  a  kind  of
routing  of  the 3rd flavor.  It is supplied by the source, and may have
as much (or as little) information to get to the environment  where  the
next piece of routing is nonambiguous.

An example of source-routing, (1), is calling from a centrex system to a
centrex system in another area code.

An example of  communication-routing,  (2),  is  the  interHOST  traffic
within the ARPAnet.

An example of user-assisted-routing, (3), is an operator-assisted person
to person call without knowing the number.  For example, one has to tell
the communication subsystem (here, a sequence  of  operators)  that  the
other  person is (a) in Massachusetts, (b) in Cambridge, (c) at MIT, and
finally (d) the final  destinations  name.   In  this  case  the  source
supplied   the   sub-destination   "Masachusetts"   (or   617)  but  the
communication system was free to choose the optimal route there.

Another example is a call which  is  placed  from  a  military  base  to
another.   Normally  the  AUTOVON  system is used, but many times at the
discretion of the individuals,  they  use  the  AUTOVON  system  to  get
outside  to  the  commercial  network, and back to the destination base,
where the AUTOVON system is used again for the terminal  contact.   This
is   a  example  of  an  INTRAnet  (AUTOVON)  call  which  for  quality,
convenience and similar reasons, uses INTERnet facilities.

                                                    Page   4


Another interesting observation about the telephone systems.   Telephone
addresses  are  of  variable  length.   This  does  not  mean  only that
different addresses may  have  different  lenghts,  but  that  the  same
address may have several lenghts, depending from where it is refered to.
For example inside most  organizations  extensions  may  be  reached  by
dialing  about  4 digits only.  from outside the organization, but still
in  the  neighborhood  7  digits  are  usually  needed,  from  a  larger
neighborhood  it is 8, then 10, and so on.  This is to be expected since
telephone numbers are the basis for the hybrid routing used.   Telephone
numbers  are  parsed  sequentially,  and can traverse hierarchies up and
down because of the prefixes used to indicate the "up"  direction  (like
the 9 for outside, and the 1 for area code).

It seems to me that we might like to implement a very similar  structure
for addressing.

One way to implement such a user assisted  routing  is  to  implement  a
special  FORWARDER  process (on a well-known PORT), whose function is to
receive messages, retrieve the "next-address" from its data and resubmit
it for transportation to the next sub-destination, while doing the right
things to acknowledgments, duplicates and the like.  These processes  do
not have to be implemented on all systems, but only on a certain subset,
where this capability is needed.  This  would  eliminate  the  need  for
making   all   processes  able  to  handle  variable  length  multilevel
addressing.

SUMMARY

The address space should be hierarchical, because  it  is  more  general
than  the flat space, and mainly because it may be not practical to have
everyone knowing about all the other participants in this space.

The format of the ADDRESS should be made more general (extensible).

Routing  which  follows  the  hierarchy  of  the   address   space   has
difficulties in utilizing internet resources for intranet traffic.

The distribution of all the knowledge needed to support routing which is
entirely  performed  by the communication subsystem may also turn out to
be impractical.  Relying always on  the  source  to  supply  the  entire
routing has its obvbious problems.

Therefore we highly recommend that the hybrid approach will be used.

ACKNOWLEDGMENT

Recent  discussions  with  John  Shoch  and  David  Boggs  were  a  very
educational  experience for me, and helped me to understand these issues
better.  This note and John Shoch's note on the same subject  (both  are
prepared  for  the  same January 1978 TCP meeting) cover similar issues,
and are basically  in  agreement  about  most  issues.   However,  minor
differences between the them seem to justify their existance separately.