IEN-122                                                     Danny Cohen
                                                                I  S  I
                                                        31 October 1979
                                                              Halloween


                   On Addressing and Related Issues.
                      (or: Fuel for a Discussion)
                   ---------------------------------


This note is about addressing of hosts on local nets.


THE AXIOM-A1

According to our current model a local net  (LN)  is  an  InterNetworkly
(like  "internationally")  known  network,  having an 8-bit Net-ID (NID)
assigned by the czar, registered in the official registry, etc., etc.

Furthermore, we have Axiom-A1 which states that:

          (A1): All Gateways know how to get to ALL Networks.

Here,  both "Gateway" and "Network" are spelled with capital letters  to
indicate  that  they  are part of the global InterNetwork Environment as
opposed to some trivial network or gateway, like the  hidden  ones,  for
example.

An interesting question is: "Is every local network a Network?".

Now the answer seems to be "yes".   I beg to differ.

I cannot escape the feeling that if we hold to  this  practice  we  will
soon  find that slow nets, like the ARPANET, cannot keep up with all the
inter-Gateways traffic needed for all Gateways to  know  all  about  all
Networks,  or  at  least about their existence and how to get there.  In
addition the storage capacity to keep this information and the cycles to
process  it  may  also exceed any reasonable estimate.  In addition, the
8-bit field may turn out to be too small for the NID.

This fear is based on the experience with  the  ARPANET  routing  update
which was frequent when the net was lightly loaded,  hence least needed,
and less frequent when it was needed the most,  when the net was heavily
loaded.

Also,  so far we have 31 NID's assigned (according to page 2 of IEN-117,
August 79) and this does not even include the 10 telephone lines each of
which has to be treated as a Network, according to Dave Clark; the 3 (at
least)  LN's  at  ISI,  at Lincoln, SRI, LLL, LBL, CMU and more.  In the
very near future every installation will have an  LN  (DECNETS  and  the
like) and probably so will any medium and big computer system.

                                                                  Page 2

If every PDP-10 (and bigger) computer has a  local  net  to  communicate
with its devices, file systems and the like, and if local nets have NIDs
then we may need LOTS of bits in LOTS of tables, and lots of  cycles  to
process  them,  if we ever manage to get enough bandwidth to communicate
them.

I propose the following:

    *  Let NID='377 be an escape-code, and NID=0 mean "this-Net".

    *  Let networks which have only one connection to the IN-environment
       (e.g., one Gateway only) be defined as Ln's.  Note, net, not Net.

    *  Let Ln-addresses be 24 bit wide.  The value 24 is used  here  for
       convenience only.  Obviously it may assume any other value, as is
       needed for any particular network.

    *  Let Ln's not have  NID's!!!  and  their  gateways  considered  as
       gateways (not Gateways); and

    *  Use source-routing to get to the hosts on these Ln's.

Hence, if there is a local net at site-X,  which  is  connected  to  the
IN-environment via IMP-Y on the ARPANET, then the addresses of processes
on this net should be:

         <NID=ARPANET> <IMP=Y> <HOST/LINK=Local-gateway>
         <NID='377> <the 24-bit address of that process>

Note that this is a 64-bit address !!

In comparison, now we have only 32-bit addresses, such as:

         <NID=X> <the 24-bit address of that process>

However,  for sites on Networks with only  16-bit addressing  (e.g., the
ARPANet and WBnet) it is  most advantegous to have local nets with 8-bit
addressing  only,  since  this allows packing of the entire address in a
single IP-address without the need for source-routing.

For example,  the IP-address of host-123   on  the  local-net  which  is
connected  to  the INE via the gateway which is on interface-3 of IMP-22
could be:

          <NID=ARPANet> <IMP=22> <HOST=3> <Ln=123>

The main idea is that if all the communication to X has to pass  through
"g"  then  there  is  absolutely  no point in propagating to the outside
world any information about the  structure  of  the  environment  inside
(i.e., "inwards" or "beyond") of "g".

                                                                  Page 3

If CMU, for example, has 5 local nets, all of which are connected to the
world  via  the  same IMP, then there is absolutely no point in treating
them as Networks with NID's, and polluting the  world  with  information
about  them, how to get to them etc., since the only way to get there is
to get first to the ARPANET and then to the CMU-IMP.

Proliferation of information which is not needed may be very costly,  in
storage, in cycles, and in bandwidth.

I don't believe that the fact that  someone  adds  a  local  network  in
Timbaktoo has to be propagated to all the Gateways.

In summary: Let's adopt the policy of  non-proliferation  of  NID's  and
let's use source routing.

THE THEOREMS T1, T2 and T3

The following three theorems have been proven experimentally and require
no more discussion:

         (T1): Any fixed size field will be found to be too small.

         (T2): Any fixed number of fields will be found to be too small.

         (T3): You can fool T1, or T2, but not both.

It is important to understand that T1 is not the only  reason  to  avoid
Networks  proliferation.   By having a very-very long NID field (say 100
bits) T1 may be fooled for some time.


THE POSTULATE-P1

Addressing hosts and processes which have several  physical  connections
with the INE (the InterNetwork Environment, or "Catenet") is a messy and
nasty problem.

This problem may be stated as:  "What is the  address  of  X  if  it  is
connected with the INE both as HOST-m on NET-i and as HOST-n on NET-j?".

If X is a network,  say NET-k,  then there are Gateways in between,  and
according  to  Axiom-A1 there  is  no problem in addressing it as NET-k,
since all the Gateways anywhere know how to get to it.

But if X is a host,  or any other  non-network  type  of  process,  then
there is a problem with its dual-homing (or better: multiple-homing).

If the choice between the multiple  addresses  is left  to  any  process
which  tries  to  communicate  with  X  then  we  have to admit that our
communication system is  not  capable  of  solving  ALL  the  addressing
issues,  and  push this problem "up" into hosts.  It goes without saying
that this does not mean that people (like senders of text messages) have
to remember these multiple addresses, and that programs and tables could
be used for it.

                                                                  Page 4

Here is where Postulate-P1 is defined.

          (P1): Every process should have only one IN-address.

This  is  possible  to  achieve  by  simply  defining  any  process,  or
collection of processes, as a Network.  For example, if hosts (which are
not Gateways) and local networks which have more than one connection  to
the  INE,  are  defined as Networks, with their own NID's, then Axiom-A1
guarantees that Postulate-P1 is always true.

Note how  nicely  this  alleviates  the  problem  of  handling  multiple
addressing,  source routing, the mess required to handle variable length
addresses, and more.

THE INNER STRUCTURE OF GATEWAYS

After establishing both Axiom-A1 and Postulate-P1 the  addressing  issue
is  totally  under  control.   There  may  be  a  slight difficulty with
handling the number of Networks which are required, but T1 can always be
fooled by assigning a very long field for the NID and by  assuming  that
the bandwidth, the storage and  the  cycles  are  avilable  at  all  the
Gateways to handle all the information about ALL these Networks.

Next, consider a process P which is  inside  the  Gateway  G(i,j)  which
connects NET-i with NET-j.  Such a process may deal with access control,
checks and balance, routing, or any of many other possible issues.

What is the address of this process?

G(i,j) is both HOST-m on NET-i and HOST-n on NET-j, just like X above.

Since our Postulate-P1 does not allow multiple homing, we cannot let the
address of this process be

            either  <NET=i><HOST=m><P>  or  <NET=j><HOST=m><P>

Hence, we must define the inside the Gateway to be another Network.

The new Network is obviously connected both to NET-i and to NET-j.   But
how?  Simply, as shown in <**> below:

          <**> Via  two  Gateways,  each  of  which is itself
               a Network with an InterNetworkly known NID.

               How is each of  these  Networks  connected  to
               its own neighboring Networks? Simply, as shown
               in <**> above.

Well, this does not seem to jibe perfectly with  the  notion  of  finite
length NID-fields...   By the way,  I suspect that you did not trace the
above explanation to its logical termination.  Did you?

There are several tacks one may take here to  mend  this  situation.   I
dare say that un-adopting Postulate-P1 is one of the better ones.

                                                                  Page 5

Let's do it, hence we accept  that  the  multiple-homing  issue  is  not
necessarily always solved completely by the Gateways.

There is a lot to be said about multiple-addressing but this is left for
yet another note.

Once this heresy is introduced -- even Local Networks with more than one
connection to INE may be treated as Ln's without NID's !!


CONCLUSION

Local networks, regardless of the number of connections which they  have
to the INE, should NOT be treated as Networks with NID's.

AFTERTHOUGHTS

The network forefathers demonstrated remarkable foresight by  allocating
an  8-bit  field  for  HOSTs  on  the ARPANet.  The notions of that many
hosts, that many IMPs and several computers connected to a single IMP at
one location were ahead of their time.

Since then the scenario developed in several directions.  First,  it  is
not  THE network any more.  Many networks, of different technologies are
in existence.  Second, on many occasions there is more than one computer
at the same location.

The concept of HOST is gradually and  implicitly  replaced  by  the  new
concept of SITE.  Here "site" is some combination of an organization and
a certain location, like "ISI", "MIT" or "BBN", but not  like  "DoD"  or
"Cambridge".

The association of processes, people, files, devices is not per-host, as
it  used to be, but more and more per-site.  This is especially apparent
when text messages ("mail") are discussed.  It is typically expressed by
statements  like:  "I  know that he is at MIT, but have no idea on which
machine there, and don't even care to know!".

I suspect  (but  am  not  quite  sure)  that  the  similarities  between
local-networking  and  Networking  (a  la ARPANet, WBCNet and PRNet) are
deeper than just a lucky coincidence, but less than a  deep  fundamental
phenomena.

Treating local networks with all the "glory" which  is  associated  with
"real"  (or  "global")  networks -- may be misleading and may cause more
artifacts than what we bargain for.

                                        Let's think about it......

                                                                  Page 6

A COMMENT ABOUT MULTIPLE-ADDRESSING.

Without suggesting anything to the INE,  following are some examples  of
the handling of multiple-addressing in Telephonia.

My addresses, at ISI,  are 1-213-822-1511 thru 1-213-822-1519 (plus some
non-contigious numbers).   However,  no one  outside  of ISI has to know
these numbers, since all the communication which is addressed to the one
of them is automatically re-routed to the rest, if so needed.

I have one address at ISI, and another at home.   The re-routing between
them  takes  place  outside the "pure" communication system,  unless its
definition is augmented to include the human operators, secretaries, and
the like.

If I am not around  someone probably can provide the sought information.
This multi-address (of the information!) is the choice  of  whom-to-ask.
It is very difficult to stretch the definition of  communication  sytems
to include that.

These examples show that in Telephonia  the multiple-addressing issue is
handled at several levels. Maybe the same is true for internetting, too.