The 'Security Digest' Archives (TM)

Archive: About | Browse | Search | Contributions | Feedback
Site: Help | Index | Search | Contact | Notices | Changes

ARCHIVE: TCP-IP Distribution List - Archives (1983)
DOCUMENT: TCP-IP Distribution List for May 1983 (11 messages, 20626 bytes)
NOTICE: recognises the rights of all third-party works.


Date:      17 May 1983 2148-PDT
From:      Craig Milo Rogers  <[email protected]>
To:        [email protected], [email protected]
Subject:   Re: zero checksums?
	Nope, the zero checksum "rule" applies to UDP, but not to
IP, ICMP, TCP, EGP, HMP, XNET, etc... at least, as these protocols
are documented.

	The "ones complement" discription of the IP family checksum
algorithm is somewhat of a misnomer, anyway.  The bit manipulation
involved is the ones complement addition algorithm, but the underlying
semantics are different.  A "real-world" ones complement computer
might, for instance, include logic to coerce -0 to +0 during normal
addition (reserving -0 for an error indicator).  Such a ones complement
computer would have trouble calculating the IP family "ones complement"
checksum.  The moral is that the IP family checksum does not use (nor
result in) a ones complement number.

	As a final trivia note, the TOPS20 IP/TCP implementation (at
least, the sources at USC/ISI, module TCPCRC.MAC, as of change date
25 Sep 82) generates IP checksum (and TCP checksum, and ICMP checksum)
differently from any other IP implementation I can recall.  It will
never, ever generate an all-ones bit pattern for the transmitted
checksum... it coerces to all-zeros, instead.  Thus, any given
TCP connection to TOPS20 from another system will break after an
average of (2**-16)/2 packets, assuming that retransmissions are
duplicates of the original.  In fact, it's twice as bad as that, since
either the IP or the TCP checksums could get wedged.  On the other
hand, I haven't actually *tested* this situation, merely inspected
the code, so perhaps I'm wrong.

					Craig Milo Rogers
Date:      17 May 1983 2235-EDT (Tuesday)
From:      [email protected]
To:        [email protected]
Subject:   zero checksums?
i could have sworn that a zero checksum in any protocol indicated
that there was no checksum (a checksum coming out as zero being
represented with all ones).  i can even visualize the paragraph that
said that.  but when asked for a reference recently, i couldn't find
it anywhere.  does anyone know where i got this idea, or am i just
losing it?
Date:      18 May 1983 0049-EDT
From:      [email protected]
To:        [email protected]
Cc:        [email protected]
Subject:   Re: zero checksums?
3MB Experimental PUP protocol uses the value of all ones in the
checksum field at the end of the packet to mean no checksum was

I have never come across a "no checksum" concept in the current TCP
or current IP specs.

As experience has shown (one of the graduate students didn't check
checksums -- why waste the CPU time computing a checksum?), not
checking or generating a checksum will eventually burn you since (in
our case people reported their "teriinal lines are generating
occasionally garbage"...drove the lines people crazy) you can
occasionally get packets that are truncated (nulls where a checksum
should be) and munged data (bits dropped in the packet).

Date:      18 May 1983 02:05 edt
From:      JSLove at MIT-MULTICS (J. Spencer Love)
To:        Craig Milo Rogers <ROGERS at USC-ISIB>
Cc:        don.provan at CMU-CS-A, tcp-ip at SRI-NIC, JSLove.PDO at MIT-MULTICS
Subject:   Re: zero checksums?
The Multics implementations of UDP, TCP, ICMP and IP use the convention
that a checksum of "zero" is hexadecimal FFFF, and no checksum is 0000.
This is what is actually IN the packet.  We compute the checksum by
taking the ones complement sum of all the octet pairs in the packet,
padding with a zero octet if the length is odd, and complementing the

In ones complement, there is no difference computationally between the
positive and negative zero.  This is because of the end-around-carry.
The person who stated that the checksum is not "really" ones complement
arithmetic is confused, or perhaps their implementation is bogus.  I
*know* the code I wrote for Multics is good, because otherwise you
wouldn't be reading this message.

For communication via ARPAnet, we always calculate and transmit a valid
checksum, so we are not sensitive to whether or not other
implementations support this convention.  We implemented it across all
the protocols (as opposed to just UDP) so that we could save the expense
of computing a checksum when communicating via local networks where the
transport layer does its own (hardware CRC) checking.

It is true that we might occasionally fail to checksum an incoming
packet where the transmitting implementation calculated a zero checksum,
but this is a minor incompatibility when you look at the numbers.  In
general, when a packet is so severly damaged (such as by truncation)
that the checksum is lost, the transport layer probably won't deliver
it. That is, the transport layer will probably be aware of the error,
and the correct action for the transport layer is to discard a damaged
packet, not deliver it and hope that the damage was insignificant. A
ones complement checksum gives only so much protection, and even a CRC
gives at least a chance in 65,536 of an error.
Date:      18 May 1983 10:21:48-EST
From:      Christopher A Kent <[email protected]>
To:        [email protected]
Cc:        [email protected]
Subject:   Re: zero checksums?
I believe that the zero checksum convention exists only in the Xerox NS
protocols. TCP and IP consider it expressly illegal to omit checksums.

Date:      18 May 1983 1328-PDT
From:      Craig Milo Rogers  <[email protected]>
To:        [email protected] (J. Spencer Love), Craig Milo Rogers <[email protected]>
Cc:        [email protected], [email protected], [email protected]
Subject:   Re: zero checksums?
	Thank you for your description of the Multics method of calculating
the IP family checksum.  It is most gratifying to see these implementation
details revealed.  It is most amusing to see that TOPS20 and Multics,
in making unajudicated extensions to the protocol standards, selected
conflicting values.

	I did not state that, under these circumstances of variation
from the common standards, no communication was possible.  My claim is
that, assuming the use of one of the simpler approaches to IP/TCP
packetization and retransmission, the probability of some long data
transfers (FTPs, perhaps) becoming irrecoverably wedged approaches
unity.  You aren't likely to start noticing this effect until your
transfer approaches (2**16)/2 packets * 512 octets/packet = 16M octets.
To add to its intractability, the effect is data-dependent.

	It is quite likely that during early Internet development when
IP/TCP bakeoffs were common, few people had the patience and/or system
reliability to attempt transfers of this length between differing
implementations.  Now that our systems are more reliable, why would we
question such stable modules as our checksum algorithms?  Thus a subtle
evil enters our sacred halls, our bane and doom till time ends (I gotta
stop reading so much cheap F/SF).

	Once again, I reiterate, I exhort, playing around with the
common standards is fine research, as long as you *publish* your
experiment and results.  It's a lousy way to do production engineering,

	I conceed that I was somewhat confused on the ones complement
addition problem.  The point I wanted to make was that a real "ones
complement" computer might just coerce -0 to +0 at the end of an
addition, since that would simplify arithmetic comparisons (only one
value of zero to worry about).  On our everyday twos complement
conputers, we ought to make sure that we treat -0 and +0 as equal
when we compare the checksum of an incoming packet to the checksum
that we computed, if the phrase "ones complement sum" in the standard
implies that the checksum is really a ones complement number.

	I just realized that in the light of the preceeding paragraph
the TOPS20 method is viewed as "correct".  TOPS20 will treat incoming -0
and +0 checksums as identical.  It chooses to generate only +0 on outgoing
checksums.  My apologies to the TOPS20 IP/TCP implementors, they may
be the only ones who have it right.

					Craig Milo Rogers
Date:      18 May 1983 14:06:43 EDT (Wednesday)
From:      Mike Brescia <[email protected]>
To:        [email protected]
Cc:        [email protected]
Subject:   Re: zero checksums?
BBN gateways check the IP checksum, and will not pass packets with (+0) sum.

The 1's complement arithmetic is supposed to coerce any occurence of (-0)
to (+0) so that you could have a checksum of the 'impossible value' flag
to bypass checksum checking.  That's been around since the days of manual
patches to binary card decks.

I must agree with all who say ALWAYS include checksums.  While they often
find only that the other end has a bad (different) interpretation of the
checksum routine, once that gets ioned out, you then can have some assurance
that the checksum failures really indicate something.  Found a bad IMP interface
one time.  Your 'interface which does its own checking' could have a bad dma
interface which corrupts the packet on its way in or out of memory too.

(Note above I switched the +0 and -0; that's because the checksum field is
the complement of the sum).

Mike Brescia

Date:      19 May 1983 12:12 EDT
From:      David C. Plummer <DCP @ MIT-MC>
To:        ROGERS @ USC-ISIB
Cc:        JSLove @ MIT-MULTICS, tcp-ip @ SRI-NIC, don.provan @ CMU-CS-A
Subject:   Re: zero checksums?
Well, this is losing.  Here we are nearly 6 months into enforced
IP and we have a major disagreement.  My copy of the TCP document
is Septmber 1981.  I will implement whatever it says.  If there
is a more recent version of the protocol specification, I suggest
you let the WORLD know about it.  

I will interpret "one's complement of" as meaning "logical
negation of."  "One's complement sum" can result in both +0 and
-0, -0 coming about by adding -0 and -0 (i.e., all bits on in the
packet) in the "add then add-carry" method of computing it of
two's complement computers, or by adding -0 and +0.  Therfore,
both +0 and -0 are possible (seemingly valid) checksum values.

There is a major loss in saying "this value for the checksum
means no checksum."  Suppose the computed checksum is this magic
value but one bit is different.  If this one bit were damaged by
the network (as well as some other parts of the packet) and
therfore converted to the magic number you will lose horribly.

Date:      20 May 1983 2200-PDT
From:      The Mailer Daemon <[email protected]>
To:        <[email protected]>
Subject:   Message of 17-May-83 21:50:40
Message undeliverable and dequeued after 3 days:
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
[email protected]: Cannot connect to host.
Received:  from USC-ISIB by SRI-NIC via DDN;  17 May 83 21:50:10-PDT
Date: 17 May 1983 2148-PDT
Subject: Re: zero checksums?
From: Craig Milo Rogers  <[email protected]>
To: [email protected], [email protected]
In-Reply-To: <[email protected]>

	Nope, the zero checksum "rule" applies to UDP, but not to
IP, ICMP, TCP, EGP, HMP, XNET, etc... at least, as these protocols
are documented.

	The "ones complement" discription of the IP family checksum
algorithm is somewhat of a misnomer, anyway.  The bit manipulation
involved is the ones complement addition algorithm, but the underlying
semantics are different.  A "real-world" ones complement computer
might, for instance, include logic to coerce -0 to +0 during normal
addition (reserving -0 for an error indicator).  Such a ones complement
computer would have trouble calculating the IP family "ones complement"
checksum.  The moral is that the IP family checksum does not use (nor
result in) a ones complement number.

	As a final trivia note, the TOPS20 IP/TCP implementation (at
least, the sources at USC/ISI, module TCPCRC.MAC, as of change date
25 Sep 82) generates IP checksum (and TCP checksum, and ICMP checksum)
differently from any other IP implementation I can recall.  It will
never, ever generate an all-ones bit pattern for the transmitted
checksum... it coerces to all-zeros, instead.  Thus, any given
TCP connection to TOPS20 from another system will break after an
average of (2**-16)/2 packets, assuming that retransmissions are
duplicates of the original.  In fact, it's twice as bad as that, since
either the IP or the TCP checksums could get wedged.  On the other
hand, I haven't actually *tested* this situation, merely inspected
the code, so perhaps I'm wrong.

					Craig Milo Rogers
Date:      24 May 1983 00:00 EST
From:      [email protected]
To:        [email protected]
Subject:   TCP-IP Digest, Vol 2 #6
TCP/IP Digest            Tuesday, 24 May 1983      Volume 2 : Issue 6

Today's Topics:
        Intent of TELNET RFCs && Intent of "Little Servers" RFCs
                    Communication with Strange Hosts?
                    Using gateways on BBN 4.1 TCP/IP?
                Developing Security Protocols for TCP/IP?
    DIALOG on Subnet Routing -vs- IP Routing for "Campus Area Networks"
                  TCP/IP Digest --- The InterNet Digest
                         LIMITED DISTRIBUTION
          For Research Use Only --- Not for Public Distribution

Date: 10 May 1983 1320-PDT
From: [email protected]
Subject: TELNET RFCs
To:   [email protected]


The intent of the new RFCs on Telnet (854-861) is to clean up the 
documents on the basic Telnet protocol and to make available current
specifications of the most used Telnet Options.  There is no intent to
change the Telnet protocol at this time.



Date: 10 May 1983 1323-PDT
From: [email protected]
Subject: "Little Servers" RFCs
To:   [email protected]


The intent of the new RFCs 862 - 868 is to document a set of little
service protocols that have existed for many years.  Each of the
protocols is a very simple service, and most are used only for debugging.
In these RFCs, each protocol is defined for use with either TCP or UDP.



Date:     3 May 83 22:51:46-EDT (Tue)
From: Robert Morris <[email protected]>
Subject:  communication with strange hosts
To: [email protected], [email protected]

In order to evaluate proposals for a central computing facility,
I need to gather information about the ability of competing vendors
to communicate with our departmental UNIX systems running 4.2bsd.  Many
vendors support HASP and I gather with work one can  do something with this.
I also have the impression that TCP/IP is avaialable for VAX VMS

For the following systems I solicit information about 
known versions of TCP/IP. I would also welcom comments
about the suitabilty of a HASP interface, especially for non-IBM
systems.  Our needs are principally remote login and file transfer
with the alien (non unix) host , secondarily  mail transfer.

Please reply directly to me, not the list. I will summarize unless someone
tells me that such summaries have already appeared.

bob morris
[email protected]

vendor		system		os
~~~~~~		~~~~~~		~~
dec		vax 11/780	VMS
prime (2)	prime 850	PRIMOS
cdc		cyber 170-81	NOS
ibm		4341		VM/SP, supporting CMS, MUSIC
harris(2)	H800/2C		VOS (Vulcan)
honeywell 	DPS 8/49C	CP6 (?)
burroughs  (2) 	B-6925		MCP
sperry		1100/62		?


From: Alan Parker <[email protected]>
Date: Wed, 27 Apr 83 22:49:38 EDT
To: [email protected]
Subject: bbn 4.1 tcp/ip and Gateways

We are running the bbn tcp/ip on a 4.1bsd vax unix.   What is the
trick to get the user programs (telnet, ftp, and smtp) to recognize
hosts that are reached through a gateway.   For example host uw-beaver
is on net 192.   If I attempt to connect to them I get 'unknown host'
from the user programs.  I can in fact reach them by giving the full
internet address on the telnet command.   I have checked my host, net,
and gateway tables.   mkgate runs without any errors.   Thanks.


Date: 19 May 1983 1242-CDT
From: [email protected]
Subject: TCP/IP

            HUGH HAMBERGER
            HARRIS CORP.
            PO BOX 37
            MELBOURNE FL 32901
     tel    305 727 6673


                                HUGH HAMBERGER

[ Anybody with information for Hugh should reply directly to him, and CC
  the list.  -Mike ]


Date: 4 May 1983 03:33:34-EST
From: Christopher A Kent <[email protected]>
Reply-to: [email protected]
To: [email protected]
Subject: an interesting dialogue
Cc: [email protected]


Tom and I have been having an interesting discussion about the
expansion of the internet and how it is going to impact gateways and
protocols. Tom suggested we open up the discussion to a larger forum
and I agree with him; perhaps TCP-IP Digest is the right place. I'll
forward the transcript so far (in a separate note) and you can decide.


[ The remainder of this issue is devoted to the discussion between Tom
  and Chris.  Each message is broken out separately.  -Mike ]


Date:	26 April 1983 0208-EDT (Tuesday)
From:	Thomas [email protected]
To:	[email protected]
Subject: Re: grabbing a bunch of class C numbers

From your recent message to Header-People:

    Along the same lines, there seems to be a recent trend for groups that
    are bringing up private internets to grab a bunch of class C numbers,
    rather than one class B number that they manage privately. I think this
    is wrong. The Internet is cluttered enough with routing packets between
    gateways; why should the rest of the world know that you have, say, an
    10Mb Ethernet, 3Mb Ethernet, Proteon ring, serial line IP, fiber
    optics, and back-to-back parallel interfaces? I certainly don't care.
    It should all be invisible to the outside world. 

It is interesting to me that you think this is happening.  I'd like to
examine what it would mean to manage a class B number privately.  There
are two points of view from which the allocation of Internet network
numbers can be approached:  the point of view of the site that is
bringing up a private internet, and the point of view of the
administrators of the Internet as a whole.

First, the point of view of the site that is bringing up a private
internet.  The site probably already has more than one
local-area-network (LAN) technology:  I would suspect generally you
would find 10mb Ethernet plus some other technology.  The site is
looking for internet as the solution to their local networking problem.
They can get Internet support for lots of their local machines.  Now
part of the Internet support they will get extends down into what
Internet calls the local network interface (LNI).  The local network
interface plugs down into the physical characteristics of the
local-area-network and determines how things such as address resolution
work.  It determines how what Internet calls a local network maps onto
the physical local-area-network technology.  The local network interface
may or may not be modifiable.

Now in all cases I have seen, the local network interface maps the
Internet concept of local network onto the obvious addressing structure
supported by the local-area-network technology.  For example, IPs
running on top of the 10mb Ethernet see an Internet local network which
consists of those stations connected to the 10mb Ethernet cable.  This
is really a reasonable thing to do.  It lets the local network interface
use the hardware directly to fulfill its contract to deliver packets on
the Internet local network, and it lets the IP module worry about
inter-network routing.

So we can expect that a site with several local-area-networks will want
to set up each LAN as an Internet network, with Internet gateways
between them.  This is the most straightforward application of existing
IP implementations.

Second, the point of view of the administrators of the Internet as a
whole.  These people have got to be concerned with the growth in the
number of Internet networks.  If things keep on as they are going at
present, soon we will see the day of 10000 networks.  Jolly-Roger
Flea-Net gateway is going to be displeased when it EGP dials up its
friendly BBN neighbor gateway and gets the list of best-next-step
gateways.  I don't see anything being done about this problem.

So much for the points of view.  What ought to be happening?  As you
point out in your note, the local network structure of a site ought to
be invisible to the rest of the Internet world.  Certainly, the internal
structure of any site that is connected to the rest of the world via
one gateway is irrelevant to the rest of the world.  The trouble is that
the only way to express this irrelevance in IP is to make the entire
site one Internet network; for example, a class B network, as you
suggest.  But then, internal to the site, IP becomes useless as a tool
for tying together all of their different local-area-networks.  The site
will have to implement its own inter-local-area-network routing so that
the Internet local network interfaces can preserve the appearance of
one connected class B network.  This might be difficult keep up as new
machines are introduced.  (Our SUN terminal supports IP on the 10mb
Ethernet!--its version of a local network interface with a certain
encapsulation onto the 10mb Ethernet, of course.)

If an IP/LNI implementation for a local-area-network is designed under
the assumption that the local-area-network directly implements the
Internet local network (as far as I know, this is the case for all
existing implementations), then it will not work if you want the LAN to
be only one component in the Internet local network.  The only
possibility, other than modifying the IP/LNI implementation, is to
attach "leeches" to each LAN.  These leeches suck up raw packets,
encapsulate them up into an inter-LAN protocol, route them around
though some backbone network to the destination LAN, then spit them
back out as raw packets again.  Even this possibility only works where
the LANs have enough addressing space individually to cover the entire
Internet local network and where the leeches can arrange to receive
packets that are addressed to many different destinations.  There are
lots of subtleties involved in the implementation of the leeches, as

I say, this is complicated.  It may, however, be the only way to go.  For
hosts that come ready to plug into a LAN, there may be no possibility
of dividing an IP/LNI implementation--a site will have to take what
comes out on the LAN as a given.  There is nothing in Internet between
the concept of a connected Internet local network and the concatenation
of all Internet networks--either you are at the level of implementing
an Internet local network or you are implementing the entire Internet.

If I were in charge of bringing Internet to Carnegie-Mellon, the use of
many class C network numbers would be one definite alternative.  It
seems more in the "spirit" of IP to map the existing mechanisms in
Internet onto the structure of the problem.  Lots of people are working
on Internet gateways; I'd have natural encapsulations on all of my
LANs; there'd be lots of software to help me out.  I'd also be
contributing to the Internet network number explosion.  The second real
alternative would be to use the "leech" scheme I've outlined.  Even it
wouldn't work in all places--our 3mb Ethernet, for example--so I'd still
have to have either multiple Internet network numbers or modified LNIs
for these cases.  And of course now I'm all alone implementing leeches
with their own routing and updating algorithms to get right.  It would
be lots of fun, to be sure, but one wonders how many times the same
problem has to be solved.

		-Tom Rodeheffer


Date: 28 Apr 1983 1640-EST (Thursday)
From: cak
To: [email protected]
Cc: [email protected]
Subject: Re: grabbing a bunch of class C numbers

I agree with your interpretations of the two points of view; but I
think that your choices of solutions are shortsighted.

Organizations (I use this here to mean groupings of private networks
that wish to communicate with the Internet via core gateways) will have
to perform some form of internal routing, no matter whether each of
their wires has a distinct class C network or not. They will have to do
this because of the way EGP is structured; the simplest solution is, of
course, to have one EGP gateway which touches the Arpanet and all the
local wires. This will clearly have severe performance penalties, so
there will be a move to multiple internal gateways and some
gateway-to-gateway protocol, including the EGP gateway.

Yes, most LNIs perform some mapping of Internet addresses to local
network addresses (viz David Plummer's Ethernet address resolution
protocol). That has nothing to do with the way subnets are managed; it
merely describes a mechanism for mapping 32-bit Internet addresses onto
(in this case) 48-bit addresses. How those 32-bit addresses are
organized is strictly arbitrary, as far as the protocol is concerned.

Indeed, the *current* specification of IP does not indicate how one
should manage a subnet. There are clearly several straightforward
extensions to the addressing structure that make this possible; I have
outline and implemented one of them locally; others exist at CMU and
LBL and Linkabit and ... and yes, they all require the ability to
modify the IP implementation(s) at hand.. So far, this has not been a
problem. As the IP catches on and begins appearing in binary form
inside products, there will be problems. That is why I am making a lot
of noise NOW to have extensions made to the IP specifications to cover
these cases.

Specifically, what I propose is that there be added to the
implementation another level of hierarchy, which fits completely within
the 16-bit local portion of a class B address. Sites that wished to use
another mechanism internally could do so; but there should be a default
that appears within the specification, so that different vendors of IP
software could have common ground. My particular implementation of
subaddressing is fairly convoluted because I can't modify my Arpanet gateway.

I don't think that IP need be "useless as a tool for tying together all
of their different local-area-networks", IF A STANDARD IS PROPOSED AND
ACCEPTED. That's the point of all these lists that flood my mailbox and
yours; to discuss and modify and improve our networking environment. I
believe that my proposal is a straightforward, logical, and upward
compatible extension of the current standard.

You will notice that I have ignored your idea of leech machines. To be
honest, I find the idea rather distasteful. I don't like the idea of
promiscuous receivers on my networks. It sounds like it is very subtle,
tricky, and error-prone. 

These are probably religious issues; I hope that I have presented my
views in a scientific and logical, rather than fanatical, manner. Your
comments are welcome, as always.



Date: 28 April 1983 2011-EDT (Thursday)
From: Thomas Rodeheffer at CMU-CS-A (C410TR30)
To: cak at PURDUE
Subject: Re: grabbing a bunch of class C numbers

Currently, a site either has to set up each of its local-area-networks
as a separate IP network, or it has to cobble together a single IP
network through some conspiracy of local network interfaces and
inter-LAN bridges.  The first alternative contributes to the IP network
number explosion and consequently is distasteful from the point of view
of the IP administrators.  The second alternative requires
implementation at a second level of routing algorithms essentially
identical to those of IP and consequently is distasteful from the point
of view of the site administrators.  In sum, IP as currently defined is
not really a useful tool in solving a multi-LAN site's fundamental
problem of intermachine datagram transport.

I fully agree with your statement that IP could become a useful tool
for solving this problem if a new standard were proposed and adopted.  I
guess that I am less optimistic than you are about the chances of this
coming to pass.  (Although I will admit that the Apranet conversion went
fantastically better than I had expected.)

In order for IP to assist in the solution of a multi-LAN site's machine
interconnection problem without contributing to the IP network number
explosion, the concepts of IP network and local delivery area must be
separated.  Currently it is the case that an IP implementation assumes
that all IP addresses on the same IP network are in the local delivery
area, which is to say that the local network interface takes the
responsibility of delivering datagrams to and from hosts at these
addresses without the need of any further concern from the IP level.
The problem is that information about every IP network has to appear at
every IP gateway.  This would not be necessary if there were some kind
of hierarchy of networks--similar to what has been proposed for name
server domains.  In this case a site could subdivide its campus-wide IP
network into subnetworks corresponding to the physical implementation,
and get local inter-subnetwork IP routing without having to burden the
outside world with knowledge of the subnetwork structure.  This sounds
like a general statement of what you are proposing ought to be done.

I should state that it is possible to conceive of IP implementations
managing the IP network number explosion by deducing clusters of class
C network numbers that had similar routing parameters.  Tricks like this
would have to appear at least in every IP gateway, if not in every
host, and consequently seem very unlikely to come to pass.  Also, as far
as I can tell, it seems that the Internet administration is passing out
IP network numbers in sequence, which means geographically at random,
so eventually I would expect entrophy to catch up with any kind of
smart clustering heuristic.

Now it seems that currently sites are taking one of two approaches to
solving their multi-LAN networking problem.  Some sites are getting a
separate IP network number for each of their local-area-networks.  We
all agree that this in not a desirable solution from the point of view
of the Internet as a whole.  Other sites are locally amending the IP
specification to provide some sort of local subnetwork structure
understood by their local IP implementations.  This approach runs the
risk of setting up all kinds of incompatibilities.

The opinion I have from Postel is that he thinks that all of the
problems of subnetwork structure should be hid inside the local network
interface.  Besides the potential problem this presents to a site of
reimplementing routing in the LNI, there is also the difficulty that no
specification exists for how the local network interface should perform
its duties on popular local-area-networks such as the Ethernet.
Consequently, there is no guarantee that products from two vendors both
claiming to support IP on the Ethernet will even talk to one another.
So far we've been getting by because there exists a pretty obvious
encapsulation for the case that the Ethernet LAN implements one IP

As you point out, any irregularities in local implementations of IP on
a given kind of physical link will increasingly become problems as IP
catches on and real vendor products start to appear.  The question is
whether or not it is too late to amend the IP specification to allow a
subnetwork level in the hierarchy.  My impression is that it is too late
even to amend the implicit agreement on how the LNI uses the Ethernet,
but I have been wrong before.  Anyway, I'm really worried about the
short term problems that will start to come to roost in the next year
or so.

It occurs to me that perhaps the general interest would be better
served if our exchange were published in, say TCP-Digest.  I generally
don't dive into hot debate on the net, but as I have seen virtually no
discussion of this topic, perhaps some interest needs to be kindled.
Your responces are welcome.

		-Tom Rodeheffer

[ As this topic is of vital importance to us all, I have published these
  letters in full.  Please direct discussion to <[email protected]>.  -Mike]



Date:      25 May 1983 00:00 EST
From:      [email protected]
To:        [email protected]
Subject:   TCP-IP Digest, Vol 2 #7
TCP/IP Digest           Wednesday, 25 May 1983     Volume 2 : Issue 7

Today's Topics:
           Local InterNets -- Searching for a General Solution
                       Discourse on Subnet Routing
               Thoughts on Large Multi-Wire Local Networks
                  TCP/IP Digest --- The InterNet Digest
                         LIMITED DISTRIBUTION
          For Research Use Only --- Not for Public Distribution

Date: 24 May 1983 1312-PDT
From: [email protected]
Subject: "local internets"
To:   [email protected], [email protected]
cc:   [email protected], [email protected]

Chris & Tom:

I am very interested in the development of a procedure for treating
multiple lans as one IP network.  I think a promising approach is to
investigate the possible extension of the Plummer address resolution
scheme (RFC 826) to cover a multi-lan situation, or an extension
of the CRONUS scheme to cover multiple local networks.  I would be
very interested in a solution to the problem in terms of a procedure
like one of these.  If a procedure can be found and documented that
solves this problem in a general way (e.g., not dependent on a
particular type of network hardware), i would support making that a
standard interface between IP and lans -- i would encourge the procedure
to be incorporated in "IP products" to be used on lans.



Date: 24 May 1983 1746-EDT (Tuesday)
From: [email protected]
Subject: On subnet routing
To: [email protected]

I've been following the discussions of subnet routing in the digest with
interest.  I believe that there is some confusion evident, so this note
is an attempt to clarify some of the issues.  We started running up against
this problem about a year ago at MIT; this note is an attempt to summarize
what we think we've learned.   I'm afraid this is going to be a long note;
I'll attempt to keep things interesting.

For those of you who don't want to read the entire note, here's a
summary of what I'm going to say.  I'm going to argue that the introduction
of EGP reflects a leaning towards a particular structure for the Internet:
namely, a collection of "core" networks comprising the trusted long-haul
networks and interconnected by trusted gateways; and a large number of
external networks each connected to the core by an EGP-speaking gateway.
I'll argue that many of these external networks will in fact be a cluster
of physical nets, and that EGP in and of itself does not solve the problems
of routing within these clusters ("subnets" in our terminology).  I'll argue
that the major technical issues are: designing a subnet routing algorithm
which miminizes changes to existing host software; and propogating external
routing information within the subnet.  I'll argue that the subnet routing
algorithm is at least partially a political issue as well.  And finally I'll
point out some major routing problems which remain to be solved in the Arpa
Internet.  The note will start out by describing the current Internet
routing structure and its problems; then talk about EGP and subnets;
finally mention future problems.

1) Discussion of original Internet routing

	Routing in the Internet was originally designed with an eye towards
isolating hosts from changes in the routing algorithms employed.  This section
gives some background in how the original Internet routing scheme worked.

 a) Routing from the host's point of view

	In the Internet, it is assumed that each host is attached to a
network which is capable of delivering packets to any other host attached to
the same network.  The network may have an internal routing algorithm of its
own; this is of no concern to Internet.  The Internet-level routing algorithm
employed by the hosts is quite simple.  When a host wants to transmit a
packet, it performs the following steps:

	Look at the destination Internet address.  Is it on the same network
	I'm on?
	-- If so, I can send the packet directly, so pass the packet down to
	   the local network level for transmission directly to the
	   destination host.  (The local network may have to translate
	   the destination Internet address into a local net address, and
	   may have to perform local-net-specific routing.  This is of no
	   concern to Internet).
	-- If not, look up the destination Internet address in a cache of
	   recently-used addresses, to see if we know of a first-hop gateway
	   to which to send the packet.  (The first-hop gateway must (by
	   definition) be attached to the same net I'm on).
		-- If so, pass the packet down to the local network level
		   for transmission to the specified first-hop gateway.
		-- If not, find a "smart" gateway from a locally-maintained
		   table of gateways on the network I'm attached to.  A
		   smart gateway is one which participates in the Internet
		   routing algorithm (GGP), and hence which knows how to get
		   to any network (see below).  Pass the packet down to the
		   local network level for transmission to the smart gateway.
		   The smart gateway must know how to forward the packet to
		   its destination.

		   Now in the process of forwarding the packet, the gateway
		   may discover that it needs to forward the packet to another
		   gateway attached to the same network as the originating
		   host.  If so, it sends a redirect message back to the
		   originator, telling it that the other gateway is the
		   appropriate first-hop gateway for the specified destination.
		   This information is entered in the host's cache for later

Notice that the host doesn't need to know how the smart gateway arrived at the
correct routing decision; thus it is isolated from the details of the gateway-
to-gateway routing algorithm.

 b) Routing from the gateway's point of view

	The preceding section brought up a fundamental requirement on gateways:
each gateway must know how to route a packet to all networks.  The gateways
maintain this information by exchanging routing packets containing information
on the distance from each gateway to each network.  (The metric used in GGP
is hop count, where the "hops" are gateways).  Other details of the GGP
protocol aren't important here.

2) Problems - increasing numbers of nets, and user-supplied gateways

	A couple of problems began to show up as the Internet increased in
size.  The first was the limitation on the number of networks which could
be supported.  This limitation actually arose from two circumstances.  The
first was the structure of an Internet address: the field reserved for
holding the network number was only 8 bits in length.  This problem was
solved by redefining the structure of Internet addresses to create class
A, B, and C network numbers.  This only exacerbated the second circumstance,
though, which was a result of the fundamental limitation of GGP that all
gateways had to know how to reach all networks.  This limitation was not
a problem as long as there were only 256 possible networks; each gateway
could easily maintain routing tables listing all networks and simply
index into the table to find a route.  Now, however, Internet addresses could
address thousands of networks; but gateways could not hope to maintain routing
tables that large.  Nor were table sizes the only problem; the number and
size of routing updates needed to keep these huge tables up to date would
have been prohibitive.

	A second problem arose as a result of the desire of certain users
of the Internet to connect their own, locally-written gateways to the
Internet.  The problem was that GGP was designed to be used only in an
environment of mutually trusting gateways.  Any single malfunctioning
gateway could, by simply advertising that it had the shortest route to
any network, effectively halt all communication in the Internet.  Other
malfunctions (for example, sending bogus redirects) could isolate
individual hosts.  This was clearly unacceptable.

3) EGP - solving the user-supplied gateway problem

	In an attempt to solve the second problem, the set of all Internet
gateways was divided into two classes.  There would be a trusted set of
"core" gateways, all running DoD-approved gateway code, using GGP; and
a set of locally-written and maintained "external" gateways.  The external
gateways would communicate with each other and with the core gateways by
using a new routing protocol called EGP ("External Gateway Protocol").

	The basis of the design was that external gateways would be used
to connect autonomous external networks (eg. a university campus), to the core
Internet (the Arpanet, Satnet, and other long-haul Arpa-maintained networks).
The failure of an external gateway could only affect communications with
the isolated network it serviced, and could not disrupt communications within
the core Internet.

	Experimental implementations of EGP are currently being tested, but
the protocol is not yet in wide use.

4) Routing inside subnets

	These autonomous external networks, which are themselves connected to
the core Internet by EGP-speaking gateways, will often in fact consist of more
than one physical network interconnected by gateways.  Such "subnets" already
exist at several sites around the Internet (for example, MIT and CMU); and the
number is growing rapidly.  As the subnets themselves increase in size and
complexity, both the hosts attached to the subnets and the gateways inside
the subnets need to make routing decisions.  At the same time, more and more
hosts are running vendor-supplied Internet implementations which were not
written with this subnet organization in mind.

 a) Routing from the host's point of view

	Ideally, it should be possible to run a vendor-supplied Internet
implementation in a host attached only to a subnet without modification.
If, for example, each of the physical nets within a subnet were assigned
a separate Internet network number, existing host Internet implementations
would not have to change.  It has already been noted, though, that the
size of the routing tables needed and the size and frequency of the routing
updates required make this approach impractical.

	The alternative we have adopted inside MIT is instead to assign
a single Internet network number to the entire MIT subnet.  Thus to hosts
outside MIT, the MIT subnet appears to be a single network.  But there is
information "hidden" in the "rest" field of the Internet address which
is used by hosts and gateways inside MIT to perform intra-subnet routing.
The structure of "MIT-subnet" Internet addresses is: one byte of net,
identifying MIT; one byte of "subnet number", identifying a physical
net inside MIT; and two bytes of host number.

	Unfortunately, this alternative requires changes to vendor-supplied
Internet implementations.  The routing algorithm performed by hosts inside
MIT is identical to that specified in section 1.a) above, except that the
first test ("Is the destination host on my local net?") is changed to
	Is the destination host on my local net/subnet pair?
If so the packet is sent directly, if not it is sent to a gateway for
forwarding with the expectation that a redirect may come back.

	Of course, vendor-supplied software knows nothing about subnets and
thus needs to be modified to work.  Ideally for MIT, a standard structure
for subnet addresses would be specified; and in particular it would be very
useful to be able to look at an Internet address and tell whether the net
in question in fact supported subnet routing.  If these features were
standardized as a part of all vendor's offerings, MIT and others in the
same situation would once again be able to use standard software.

 b) Routing inside subnet-only gateways

	In the MIT subnet routing scheme, as in the original Internet routing,
hosts are isolated from the details of the particular gateway-to-gateway
routing algorithm in use.  The intra-subnet routing algorithm can be relatively
simple; a GGP-like or Chaosnet-like routing algorithm, in which each gateway
knows the entire structure of the subnet, would be quite adequate.  A problem
arises, though, in the case of a subnet with more than one external gateway.

	The problem here is that evidently some amount of external routing
information needs to propogate into the subnet, otherwise packets destined
for hosts outside the subnet may well be sent to the "wrong" external
gateway.  Similarly, hosts outside the subnet have no way of seeing the
internal subnet structure and hence may end up using the wrong gateway
for incoming packets.

	It is possible that this problem is not a large one.  It may well
be that most such subnets will have only one or two connections to the
outside world anyway; and it may be that the inefficiencies associated
with using the wrong gateway are small.  More study is needed in this

5) Future problems

	There are several problems related to routing which have not yet
been addressed in the Internet.  To begin with, the form of subnet routing
we have been discussing in this note is an interim solution at best.  It's
a step on the road to a more complete routing mechanism (sometimes called
"area routing", which has the characteristic that the distance to which
routing information is propogated is directly proportional to the granularity
of that information.  Thus the very fine-grained routing information (say
about the interconnectivity of Ethernets inside a single building) doesn't
get very far outside that building, while information about which
continents have satellite connections is disseminated to everyone.

	Notice that the metric for measuring "distance" in this sort of
scheme doesn't necessarily have to mean physical distance; it can be
any combination of physical distance, hop count, bandwidth, delay, etc.
This points up another serious weakness in the current Internet routing
algorithm: the use of hop count as the only metric for comparing routes.
A more sophisticated algorithm would include the requested type of
service (eg. delay over bandwidth preference) and the characteristics
of the networks being considered - their bandwidths, delays, and
possibly congestion characteristics.

	Finally, there is presently a problem with multi-homed hosts
in the Internet - that is, hosts which are attached to more than one
network.  This problem arises becauses an Internet address in fact
refers not to a specific host, but rather to a specific network
attachment point.  Thus once a packet has been transmitted, the
routing algorithm cannot take into account the fact that a better
route to the destination host might exist, if that route requires
sending the packet to a different network interface on the
destination host.  It's hard to imagine solutions to this problem
which retain compatibility with existing Internet implementations.

I hope this message has cleared up more points than it has raised.
I expect to get a lot of flak back; feel free to reply directly
to me rather than to the list if you want to include personal
comments about my ancestry, personal habits, or whatever.

					-Larry Allen


Date: 24 May 83 09:33:42 PDT (Tue)
From: "Mike O'Dell [system]" <[email protected]>
Subject: thoughts on large multi-wire local networks
To: [email protected]

With LBL thinking very hard about wiring its entire campus,
I have been working on an architecture which warrants exposure
to this august group.  Some of the ideas of this scheme are
variants of things proposed in the Cronus Network architecture
(Pogren, et al, at BBN).

The network environment at the Lab has several important characteristics:
we have a harsh electrical environment, it is VERY expensive to run
cables between buildings (we are on top of the Berkeley hills -
beautiful view, rock for soil), and some of the hosts eventually
connected to our net will be rehomed with some frequency.  This latter
part is one of the difficulties - using name servers is fine,
but not everything will use them because of size limitations, etc.

The scheme is to take 1 class B network number and use IP addresses as 
logical addresses.  This turns out to be quite reasonable because
the Address Resolution Protocol developed at MIT and already in
wide use provides the required mapping functions.  In the proposed
network architecture, intra-building trunks would be Ethernets,
with one or more to the building, while inter-building trunks
would likely be a fibre-optic Pronet ring.  Connecting the Ethers
to the Ring would be Gateway processors.  

The basic requirement for hosts is that they implement the
Address Resolution Protocol (ARP).  I believe vendors supporting IP/TCP
on Ethernets will either (1) only be able to talk to their own
family of hardware (2) implement some other random protocol with
the functionality of ARP, or (3) provide ARP implementations.
This is one place where market pressure might well cause
people to do the "right" thing and do number 3 above.  Even if they
don't, ARP can be slipped into the device driver for the network
interface more easily than hacking the IP implementation.
So, one of the important axioms of the design is that ARP is
something vendors are likely to do (if we, the Internet community
hound them about it), and if they don't, it isn't the worst
thing that could happen.  The Gateway processors can provide
bridge services for hosts which can't use them transparently.

By now, you have probably figured it out for yourself.  In the case
of talking to a host on a directly-connected wire, ARP works
just like normal.  In the case of a host on an indirectly-connected
wire, the Gateways processors respond to the ARP packets showing
their Ethernet as the mapping for the IP address.  As was mentioned
before, the Gateway processors need some kind of G-G protocol 
which can let each Gateway keep abreast of which host is on
which wire.  The general approach for this level is to use 
the Xerox NS Routing Information Protocol, modified to carry 
additional information about each host (its Internet address!).
This makes the Gateways each contain the entire host list
for the network, but that is ok.  Think of them as a distributed
name server.

Back to machines with no ARP implementation.  One cheap hack,
but a quite workable hack, is to simply hardwire the outgoing
Ethernet address for every packet to point to a Gateway.
The Gateway's normal routing function examines the IP address
and reencapsulates going on to the correct host.  This creates
a star-shaped network on each wire for such machines with no
ARP implementation, but if the IBM PC's and such really start
generating that much traffic, then doing ARP for them would
be worthwhile.

As for the Gateway processors, very fast 68K's are now available
with LARGE amounts of memory, so requiring large tables in the
Gateways is not the onerous requirement it is in IMP's.  They
will eventually need quite high packet bandwidths, but we are
looking at ways to do that cheaply.

So, the result of this scheme allows a large collection of wires
to be treated as one Internet network, with one class B
network number.  64K hosts is more than we see having before
the turn of the century.  By then, everything will be ISOOSI
and all out problems will be solved for us!  (That's a joke, son.)
Moreover, the ability of ARP to bind addresses very late in
interpretation allows hosts to be rehomed quite easily.  The
only tricky part is how Gateways know when a host has rehomed.
ARP includes a "here I am" packet which lets any interested
party take note of the IP/Ethernet address binding of some
newly-arrived host, so the Gateway processors simply use
that information.  They also can routinely send ARP request
packets to keep their view of a wire from getting stale.

One other point worth mentioning - this scheme 
has the advantage of providing both IP and Xerox NS capability.
As described above, the Gateway did its routing based on an IP address.
Since the tables contain everything needed to do NS routing, this
same backbone can route traffic for NS by simply demultiplexing
on the Ethernet "type" field and having additional code which
knows how to extract stuff from NS headers, as well as IP headers.
This is important in our enviroment because in spite of our
best efforts to promote IP/TCP as a basis for compatability,
NS-bases systems are already here, and will continue to be purchased,
and this would allow the Ethernet cables to be usefully shared.

None of this is particularly amazing, but we think it is a fairly
clean way to handle the problem without having to hack IP
implementations.  We do get to build and maintain the Gateway
system, and maybe do a few ARP implementaitons,  but if that
is the worst cost, we would be very pleased.

	I hope this is of value to the readers.  Comments and
	discussions are quite welcome.

	-Mike O'Dell