----MESSAGE-BEGIN---- <1983051714480000> Return-path: 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 To: don.provan@CMU-CS-A, tcp-ip@SRI-NIC In-Reply-To: <17May83.223549.DP0N@CMU-CS-A> 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 ------- ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051718350000> Return-path: Received: from CMU-CS-A by SRI-NIC via DDN; 17 May 83 19:43:30-PDT Date: 17 May 1983 2235-EDT (Tuesday) From: don.provan@CMU-CS-A To: tcp-ip@SRI-NIC Subject: zero checksums? Message-Id: <17May83.223549.DP0N@CMU-CS-A> 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? ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051720490000> Return-path: Received: from CMU-CS-A by SRI-NIC via DDN; 17 May 83 22:05:44-PDT Date: 18 May 1983 0049-EDT From: Rudy.Nedved@CMU-CS-A To: don.provan@CMU-CS-A Subject: Re: zero checksums? CC: tcp-ip@SRI-NIC In-Reply-To: <17May83.223549.DP0N@CMU-CS-A> Message-Id: <18May83.004956.IM2P@CMU-CS-A> 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 computed. 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). -Rudy ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051722050000> Return-path: Received: from MIT-MULTICS by SRI-NIC via DDN; 17 May 83 23:15:01-PDT Date: 18 May 1983 02:05 edt From: JSLove at MIT-MULTICS (J. Spencer Love) Subject: Re: zero checksums? To: Craig Milo Rogers cc: don.provan at CMU-CS-A, tcp-ip at SRI-NIC, JSLove.PDO at MIT-MULTICS In-Reply-To: Message of 18 May 1983 00:48 edt from Craig Milo Rogers 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 result. 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. ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051805214800> Return-path: Received: from PURDUE by SRI-NIC via DDN; 18 May 83 08:27:27-PDT Date: 18 May 1983 10:21:48-EST From: Christopher A Kent Reply-to: cak@purdue.ARPA To: don.provan@CMU-CS-A Cc: tcp-ip@SRI-NIC Subject: Re: zero checksums? In-reply-to: Your message of 17 May 1983 2211-EST (Tuesday) 17 May 1983 2235-EDT (Tuesday). <17May83.223549.DP0N@CMU-CS-A> Message-ID: I believe that the zero checksum convention exists only in the Xerox NS protocols. TCP and IP consider it expressly illegal to omit checksums. Cheers, chris ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051806280000> Return-path: Received: from USC-ISIB by SRI-NIC via DDN; 18 May 83 13:29:40-PDT Date: 18 May 1983 1328-PDT Subject: Re: zero checksums? From: Craig Milo Rogers To: JSLove@MIT-MULTICS (J. Spencer Love), Craig Milo Rogers cc: don.provan@CMU-CS-A, tcp-ip@SRI-NIC, JSLove.PDO@MIT-MULTICS In-Reply-To: Your message of 18 May 1983 02:05 edt 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, though. 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 ------- ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051810064300> Return-path: Received: from 1000400007 by SRI-NIC via DDN; 18 May 83 12:07:58-PDT Date: 18 May 1983 14:06:43 EDT (Wednesday) From: Mike Brescia Subject: Re: zero checksums? In-Reply-to: Your message of 17 May 1983 2235-EDT (Tuesday) To: don.provan@CMU-CS-A Cc: tcp-ip@SRI-NIC 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  ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983051908120000> Return-path: Received: from MIT-MC by SRI-NIC via DDN; 19 May 83 09:14:12-PDT Date: 19 May 1983 12:12 EDT From: David C. Plummer Subject: Re: zero checksums? To: ROGERS @ USC-ISIB cc: JSLove @ MIT-MULTICS, tcp-ip @ SRI-NIC, don.provan @ CMU-CS-A 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. ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983052015000000> Return-path: Received: from USC-ISIB by SRI-NIC via DDN; 22 May 83 16:51:18-PDT Return-path: Mail-From: SMTP created at 20-May-83 22:01:18 Received: FROM SRI-NIC BY USC-ISIB.ARPA WITH TCP ; 20 May 83 22:01:23 PDT Date: 20 May 1983 2200-PDT From: The Mailer Daemon To: Subject: Message of 17-May-83 21:50:40 Remailed-Date: 22 May 1983 1645-PDT Remailed-From: Craig Milo Rogers Remailed-To: Postmaster@SRI-NIC Remailed-date: 23 May 1983 0914-PDT Remailed-from: ROODE at SRI-NIC (David Roode) Remailed-to: tcp-ip Message undeliverable and dequeued after 3 days: Chavez@HARV-10: Cannot connect to host. Mealy@HARV-10: Cannot connect to host. Steckel@HARV-10: Cannot connect to host. TCP-IP@LLL-TIS: Cannot connect to host. CStacy@MIT-AI: Cannot connect to host. Migues@MIT-AI: Cannot connect to host. BNSW@MITRE-BEDFORD: Cannot connect to host. LCG@MITRE-BEDFORD: Cannot connect to host. Colella@NBS-PL: Cannot connect to host. JDB@NCSC: Cannot connect to host. Ammons@NOSC-TECR: Cannot connect to host. DQuigley@NUSC-NPT: Cannot connect to host. Steve@NUSC-NPT: Cannot connect to host. Don@OKC-UNIX: Cannot connect to host. RDS@OKC-UNIX: Cannot connect to host. DeBoer@UCLA-CCN: Cannot connect to host. Eszurkow.DARCOM-HQ@UDEL-TCP: Cannot connect to host. Dreifu@WHARTON-10: Cannot connect to host. Hagan@WHARTON-10: Cannot connect to host. Morgan@WHARTON-10: Cannot connect to host. McClendon@WPAFB-AFWAL: 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 To: don.provan@CMU-CS-A, tcp-ip@SRI-NIC In-Reply-To: <17May83.223549.DP0N@CMU-CS-A> 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 ------- ------- ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983052319000000> Return-path: Mail-From: SMTP created at 24-May-83 03:56:39 Received: FROM BRL-VGR BY USC-ISIF.ARPA WITH TCP ; 24 May 83 03:56:47 PDT Received: From Brl-Vgr.ARPA by BRL-VGR via smtp; 24 May 83 4:44 EDT Sender: Mike Muuss From: TCP-IP@brl To: TCP-IP@brl Date: 24 May 1983 00:00 EST 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: POSTEL@Usc-Isif.ARPA Subject: TELNET RFCs To: TCP-IP@Brl.ARPA Hi! 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. --jon. ------------------------------ Date: 10 May 1983 1323-PDT From: POSTEL@Usc-Isif.ARPA Subject: "Little Servers" RFCs To: TCP-IP@Brl.ARPA Hi! 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. --jon. ------------------------------ Date: 3 May 83 22:51:46-EDT (Tue) From: Robert Morris Subject: communication with strange hosts To: unix-wizards@Sri-Unix.ARPA, tcp-ip@Brl.ARPA 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. thanks bob morris ram.umass-boston@udel-relay 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 Date: Wed, 27 Apr 83 22:49:38 EDT To: tcp-ip@Brl.ARPA 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: CMP.HAMBERGER@Utexas-20.ARPA Subject: TCP/IP FIRST LET ME IDENTIFY MYSELF. HUGH HAMBERGER HARRIS CORP. GDCD PO BOX 37 MELBOURNE FL 32901 tel 305 727 6673 NET CMP.HAMBERGER @ UTEXAS MY PRIMARY FUNCTION IS RESEARCH ON COMPUTER NETWORK SECURITY. PRESENTLY, I AM INVESTIGATING TCP/IP FOR INCORPORATION OF ADDITIONAL SECURITY PROTOCOLS. I AM IN NEED OF A SOURCE LISTING OF TCP/IP IN A HIGH ORDER LANGUAGE SUCH AS C PASCAL ETC. FOR INVESTIGATION. ALSO, I WOULD LIKE TO KNOW OF ANY STUDIES OR RESEARCH BEING PERFORMED ON THE OVERHEAD AND THROUGHPUT DEGRADATION IMPOSED BY TCP/IP. THANKS FOR YOUR HELP. 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 Reply-to: cak@purdue.arpa To: mike@Brl.ARPA Subject: an interesting dialogue Cc: Thomas.Rodeheffer@Cmu-Cs-A.ARPA Mike, 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. Cheers, chris [ 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 Rodeheffer@CMU-CS-A To: cak@PURDUE 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 well. 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: Thomas.Rodeheffer@CMU-CS-A Cc: cak@purdue 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. Cheers, chris ------------------------------ 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 network. 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 . -Mike] ------------------------------ END OF TCP-IP DIGEST ******************** ----MESSAGE-END---- ----MESSAGE-BEGIN---- <1983052419000000> Return-path: Mail-From: SMTP created at 25-May-83 01:13:34 Received: FROM BRL-VGR BY USC-ISIF.ARPA WITH TCP ; 25 May 83 01:13:55 PDT Received: From Brl-Vgr.ARPA by BRL-VGR via smtp; 25 May 83 1:42 EDT Sender: Mike Muuss From: TCP-IP@brl To: TCP-IP@brl Date: 25 May 1983 00:00 EST 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: POSTEL@Usc-Isif.ARPA Subject: "local internets" To: cak@Purdue.ARPA, Thomas.Rodeheffer@Cmu-Cs-A.ARPA cc: postel@Usc-Isif.ARPA, TCP-IP@Brl.ARPA 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. --jon. ------------------------------ Date: 24 May 1983 1746-EDT (Tuesday) From: lwa@mit-csr Subject: On subnet routing To: tcp-ip@brl 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 use. 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 area. 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]" Subject: thoughts on large multi-wire local networks To: tcp-ip@Brl.ARPA 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 ------------------------------ END OF TCP-IP DIGEST ******************** ----MESSAGE-END----