What goes around comes around

[Paul Francis--formerly Tsuchiya <[e-mail]>]

or:  There is nothing new under the Sun(shine)
or:  How to quote history to further your aims
or:  A blast from the past
or:  If we do not learn from history, we are bound to
     repeat its mistakes


Gang,

As some of you may know, Pip is the topic of my PhD thesis.
Naturally in the course of writing a thesis, one must cite
relavent work, so I went digging....

What I found is that, 1) Pip had already largely been invented,
by Jon Postel in RFC730 (Extensible Field Addressing), and 2)
that all the current "discoveries" about addressing and routing
had already been made, in a flurry of creative activity, in
1977 and 1978, by Postel, Sunshine, Cohen, Clark, Cerf, and
perhaps others who didn't bother putting out IENs (or whose
IENs or other publications I haven't bothered to read).

So, for those of you who don't mind taking a few minutes to
stroll down memory lane (though most of your memories, and
mine, don't go back this far), and listening to platitudes
about Pip, I offer the following....

The opening paragraph in Postel's May 1977 RFC730, "Extensible
Field Addressing", says:

   This memo discusses the need for and advantages of the expression of
   addresses in a network environment as a set of fields.  The suggestion
   is that as the network grows the address can be extended by three
   techniques: adding fields on the left, adding fields on the right, and
   increasing the size of individual fields.  Carl Sunshine has described
   this type of addressing in a paper on source routing [1].

Well, right here in a nutshell is Pip.  Postel's fields are nothing
more than my FTIFs (forwarding table index fields), which allow adding
fields on the left, the right, making them bigger, and adding in the
middle (which Jon's can do too, but he doesn't mention it above).

So, now you know.  Pip stands for Postel's internet protocol--though
I should be careful, as Jon credits Carl Sunshine as having described
that type of addressing first.  To give credit where it is due, I'm
thinking of changing the name of Pip to Sip--Sunshine's internet 
protocol--or maybe SipV0, since it predates that other SIP....

Later in the RFC, Jon says:

   The prospect of interconnections of networks to form a complex
   multinetwork system poses additional addressing problems.  The new
   Host-IMP interface specification has reserved fields in the leader to
   carry network addresses  [2].  There is experimental work in progress on
   interconnecting networks [4, 5, 6]. We should be prepared for these
   extensions to the address space.

Talk about understatement!

And later still......

   A problem with simple field addressing is the desire to specify only the
   fields that are necessary given the local context.  A program
   interpreting the address is then unsure what the first field represents.
   Some clues are needed in the address specification for correct parsing
   to be possible.  Dave Crocker has described a syntax for a similar
   problem in network access of data [8].
   
Pip does this too (puts only the necessary fields in the address).
Pip uses the Routing Context field as the "clue" for correct parsing
of the fields.  And, now it is known that Dave Crocker is one of the
original Pip contributors.  Come out of the closet Dave!!!

Jon gets to the meat of the thing in the following excerpt:

   Specific Sugestion
   
   Specifically i suggest that we adopt a field based extensible address
   scheme where each field is separated from its neighbors by a delimiter
   character and each field has a name.  When an address is specified the
   name of the most general field must also be indicated.
   
     Definitions:
   
       <address> ::= <field-name> ":" <fields>
   
       <field-name> ::= "NET" | "IMP" | "HOST" | "MESSAGE-ID"
   
       <fields> ::= <field> | <field> "/" <fields>
   
       <field> ::= a decimal number


Well, (my) Pip has a few differences from this, but the basic
idea is there.  Something to give the context of the field
to be parsed (my Routing Context = Jon's field-name), and
a series of fields (mine are binary not decimal, but had Jon's
found their way into a packet, I'm sure they would have been
binary).

Perhaps the major difference between my Pip and Jon's Pip is
that my Pip uses a source route mechanism for parsing the
fields, whereas Jon's (though he really didn't get down to that
level of specificity) presumably always parses the fields
starting at the left-most one.
   
In April of 1978, Danny Cohen shed more light on the nature of
addresses in his IEN31, "On Names, Addresses and Routings (II)".
After a long rambling introduction, Danny gets to the point, which
is:

   I HATE TO ADMIT IT, BUT ...
   
   At the beginning of this note, and in an earlier note, I  used  a  great
   line telling that "names tell what the processes are, and addresses tell
   where they are." It continues by "routings tell how to get there."
   
   I hate to admit  that  by  now  I  have  some  reservations  about  this
   definition.   My  name  is  "Danny."  My address is "ISI." When I was at
   Tech, my name was  the  same,  but  the  address  was  different.   This
   supports  the  definition.   How  about  the addresses in a broadcasting
   media network? When a host changes its position (location) on  the  same
   Ethernet,  its address does not change.  Well, maybe these addresses are
   not real addresses, according to the definition.  Admittedly, this is an
   uncomfortable thought.
   
   I believe that there is a better explanation.  I suggest that an address
   is "the canonic routing from the root of the addressing-tree." It sounds
   recursive, doesn't it?
   
   To be more precise, an addressing scheme is a hierarchical  organization
   of  elements,  with  code assignment such that each element has a unique
   set of codes, corresponding to its position in the hierarchy.
   
   The notion that the address tells how-to-get-there from the root of  the
   tree  is very similar to the notion that absolute coordinates are really
   relative, with respect to the origin.
   
   Since we know (by default) how to get from the source to  the  UA  root,
   and since the address tells how to get to the destination from the root,
   the address tells how to get from the source to the destination.
   
   Hence, by definition, addresses are routings.

Yes!  Addresses are routes!  Well, perhaps the fact that Danny said
this 15 years ago still won't help convince those doubters that still 
believe that addresses are addresses.  Sigh....
   
Later on in the IEN Danny makes a proposal:
   
   Our proposal for addressing and routing is as follows:
   
        *    Establish a UA scheme, of variable level structure.

(UA is Universal-Address, such as the Pip Address......)
   
        *    Disseminate as much knowledge to each participating  node
             as deemed practical.
   
        *    Allow the option of routing to be included in the headers
             of the messages.
   
        *    Refuse delivery of messages to a destination with unknown
             routing
   
        *    Establish internet-directory-assistance service.


This last bit is crucial.  Internet-directory-assistance (now known
as DNS) must advertise the "route" from the root of the hierarchy
to the leaves.  In particular, if the packet format is a variable
length string of fields, then DNS should advertise that string, ala
Pip.

So, at this point in the discourse (April 1978), Postel has provided 
the address format, and Cohen the architectural underpinning from 
which to understand that address.  So, what happened?  Why did we
end up with IP and not Pip?

We find a clue to the answer from IEN46, written by Clark and Cohen
in June of 1978 called "A Proposal for Addressing and Routing in 
the Internet".  After discussing several problems with routing and
addressing, they make the following statement:

   The solution which has been proposed in the past to cope with this is to
   replace the address in the packet whith a route, called a source route since
   it is provided by the source of the packet.  The disadvantage of having a
   route in a packet instead of an address is that the concept of an address is
   very useful one.  For example, for accounting purposes it may be necessary to
   note the source and destination of a packet as it passes through a transit
   net.  Clearly, it is desirable that the source and destination be uniquely
   identified for this purpose, something not easily done if the source and
   destination are specified only by a route.  Thus, we propose that the address
   continue to be the primary piece of information in the packet, but that it be
   possible to include, in addition, an optional source route.  

So, here they recognize the need for a compact, simple, fixed length
*something* to identify the source and destination of a packet.  Sounds
like the EID to me!  So, the need for both an identifier and an
"address" (still at that time arguable to be a route.....) was clearly
recognized.  However, they added the source route to handle the routing
bit, and kept the address as the primary piece of information.

I think this would have been fine except for the crucial thing mentioned
by Cohen in IEN31:

        *    Establish internet-directory-assistance service.

Well, this was established, but it didn't contain the source route,
just the address.  So, the "routing" information in the packet was
effectively limited to 32 bits.

I was interested to find the following in the Clark/Cohen paper:

   5.  Migration
   
   What is the relationship between the scheme proposed here and the current
   internet header with a fixed size address field?  Happily, adoption of the

Huh?  In 1978 they were worried about migration?  Scheeese!

   addressing strategy involving regions together with the optional internet
   source route implies no immediate upheaval to packet formats or gateway code.
   Currently, every network is a region, and every gateway thus contains code for
   doing inter-region routing.  Eventually, gateways will want to be modified as
   follows.  When a region finally is defined which contains more than one
   network, then gateways inside that region will need to understand an
   additional component of the internet address.  Thus, unless gateway code is
   rewritten for different regions, it will be necessary to write code which can
   deal, eventually, with a variable size component of the address.  The address
   itself, however, can reasonably be a fixed size, since it is merely an address
   and not a route.  In fact, it seems that the field as specified for the
   current internet header is sufficient in size, although perhaps marginally so.

Well, something happened here.  An argument was put forth that 32 bits
is enough because the address doesn't have to do routing--the source
route can handle the rest.  Clearly it was recognized that a variable
length *something* was needed, but the source route was deemed sufficient
for that, and the 32-bit address won out in the end.  So, perhaps what
killed IP is not that the address is too short (though probably it is),
but that the ability for DNS to hand a host a source route (which it could
then put in the header so that the right thing could happen in the
network) was not created.

So, in fact Pip is a combination of Postel's Extensible Field Addressing
(EFA) and Clark and Cohen's "address", though the "routing" part of the 
"address" has been largely moved over to the EFA (FTIF Chain), and the 
"address" (ID) is left with minimal routing role (the last hop) and 
identification.

As an aside, if we go with SIP, I would strongly encourge the ability
to advertise source routes by DNS, which can be handed to hosts, which
will obediantly put them in the header.  This, for all practical
purposes, makes the SIP "address" variable length, thus allowing for
more flexibility in routing and addressing, for instance policy
routing.  Such a scheme, I think, would be much closer to what IP
was intended to be (at least by some).

An IEN from Cerf the following month (July 1978) seems to meld
with Clark/Cohen (IEN48, "The Catenet Model for Internetworking").  
It generally confirms the Clark/Cohen proposal.  It, however,
has some interesting statements of its own:

   In order to limit the overhead of address fields in the header,
   it was decided to restrict the maximum length of the host portion
   of the internet address to 24 bits.  The possibility of true,
   variable-length addressing was seriously considered.  At one
   point, it appeared that addresses might be as long as 120 bits
   each for source and destination.  The overhead in the higher
   level protocols for maintaining tables capable of dealing with
   the maximum possible address sizes was considered excessive.

Not only is it interesting that a longer address (120 bits, almost
as long as an NSAP), was seriously considered, but the reason for
not going with it (memory overhead to "upper layer protocols") really 
shows how times have changed.

Finally, Cerf's IEN seems to delegate source routing to its
current, and very limited, role:

   One of the major arguments in favor of variable length
   "addressing" is to support what is called "source-routing."  The
   structure of the information in the "address" really identifies a
   route (e.g., through a particular sequence of networks and
   gateways).  Such a capability could support ad hoc network
   interconnections in which a host on two nets could serve as a
   private gateway.  Though it would not participate in catenet
   routing or flow control procedures, any host which knows of this
   private gateway could send "source-routed" internet datagrams to
   that host.

I find it interesting that the original ideas of Postel and Cohen
(very Pip-like) evolved into the source route, which was then
limited to a "special service" role (i.e., routing a packet through
a private host on two nets).  I guess I would characterize Pip has
trying to get back to some of the earliest ideas on internet
addressing and routing.

PX

ps.....

By the way, I hope this little diatribe is in no way interpreted as
a criticism of the work of Cerf, Postel, Clark, Cohen, Sunshine
and others (Boggs, Shoch, Metcalfe, and many others).  They're work
is nothing short of brilliant, and the fact that we are doing nothing
but rehash 15-year-old arguments is testimony to that.  In particular,
one could conjecture that, had the Extendable Field Addressing idea
won the day, the resulting complexity might have prevented the
internet from growing the way it did.  (I certainly don't conjecture
this, but one *could*  :-).

I hope somebody out there enjoyed reading this as much as I enjoyed
discovering and writing it.  I would love to get war stories from
the participants on what *really* happened.....