From owner-ppp-comp Tue Jun 8 20:18:48 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Tue, 8 Jun 93 20:18 PDT X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Traffic (or lack thereof) Date: Tue, 8 Jun 1993 20:18:37 PDT Message-ID: Reply-To: ppp-comp@bungi.com Precedence: bulk No, you have not been dropped from the ppp-comp mailing list. Yes, there has been no messages since 05/25 or so. The Daves are all busy trying to ship code, and as you all know, no one but Dave is permitted to work on compression-related code :-) -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Tue Jul 6 20:05:41 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Tue, 6 Jul 93 20:05 PDT X-Path: hprnls6.rose.hp.com!davel From: Dave Langley To: ppp-comp@bungi.com Subject: HP PPC compression proposal introduction Date: Tue, 6 Jul 93 15:27:12 PDT Message-ID: <9307062227.AA03105@hprnls6.rose.hp.com> Reply-To: ppp-comp@bungi.com Precedence: bulk To the IETF PPP compression group, I will be presenting a compression technology at the upcoming IETF meeting on behalf of Hewlett Packard and wanted to give an introduction to this presentation on this notes group. The intent is to give everyone some time to think about the HP compression proposal and gather preliminary feedback and areas of particular interest. Dave Rand has mentioned a compression method he was including in his overall testing. This is the compression technology he was alluding to. HP has developed a compression technology that is tailored for WAN applications. It contains 2 key ingredients 1) a WAN compression architecture and 2) a compression algorithm to support this architecture. The architecture is based on a packet by packet compression approach. As we looked at a running dictionary approach to implementing compression on a WAN link, many issues arose that made this implementation very difficult. Among them are 1) Requirement of a reliable link to maintain dictionary syncroniztion 2) Large memory for the large running packet 3) Large memory to implement context stream switching 4) Large system overhead to maintain a running dictionary system. The HP PPC tecnhology (PPC stands for Packety by Packet Compression) is based on compressing each packet to be sent over the WAN independently of all the others. This approach alleviates all of the issues mentioned above. To make this approach feasable required the development of our PPC algorithm that compresses effectively with small data packets. The PPC algorithm is an LZ based algorithm with several new additions. In our testing, we have achieved compression performance that is comperable to the mainstream compression algorithms available. This is using the other algorithms in a running dictionary mode and the HP PPC running in a packet by packet mode. This algorithm also has the advantages of small dictionary memory and overall system simplicity. Another benefit of PPC is that it combines very well with header compression or other "known data structure" compression. Since every packet is compressed independently, any sort of compression segmentation (i.e. compress any portion of the packet you wish) combined with very efficient header compression yields excellent overall compression This PPC approach makes for a very simple compression implementation without the need for a reliable link or high system overhead. Patents & Licensing: Since this is an LZ based system, patent licensing must be discussed. Also, HP has applied for patents on the additional technology we've developed. I want to make it clear that HP is *NOT* interested in profit from the additions to LZ that we've made for PPC. However, existing patents are out there that we must work with. In addition to the PPC algorithm, HP is in the process of working with holders of patents in the relevant technology areas to obatain "pass through" licensing agreements. This will provide a "one-stop shopping" point for full licensing to use PPC legally and easily. Summary: * PPC offers implementation simplicity with good compression performance * PPC does NOT require a reliable link * PPC combined with header compression provides even better compression on small packets * HP is in the process of resolving patent/licensing issues to offer easy license execution. Please respond with comments and I'll see you (with more details) at the Amsterdam IETF Dave Langley Hewlett Packard Roseville Networks Division 8000 Foothills Blvd. MS R3NF3 Roseville, CA 95747 (916) 785-4973 -- Dave Langley x4973 From owner-ppp-comp Wed Jul 7 04:54:54 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Wed, 7 Jul 93 04:54 PDT X-Path: wellfleet.com!cbrown From: cbrown@wellfleet.com (Caralyn Brown) To: ppp-comp@bungi.com Subject: Re: HP PPC compression proposal introduction Date: Wed, 7 Jul 93 07:39:11 EDT Message-ID: <9307071139.AA25080@pobox.wellfleet> Reply-To: ppp-comp@bungi.com Precedence: bulk I'm glad you'll be in Amsterdam. I'll look forward to your compression talk. Wellfleet is still making a decision about which compression path to take. The fact that you are bringing yours to IETF will, I hope, lead us in the right direction. Caralyn Brown From owner-ppp-comp Wed Jul 7 13:11:58 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Wed, 7 Jul 93 13:11 PDT X-Path: wellfleet.com!cbrown From: cbrown@wellfleet.com (Caralyn Brown) To: ppp-comp@bungi.com Subject: Re: HP PPC compression proposal introduction Date: Wed, 7 Jul 93 10:25:12 EDT Message-ID: <9307071425.AA25829@pobox.wellfleet> Reply-To: ppp-comp@bungi.com Precedence: bulk egads! That message wasn't supposed to go to everyone. My mind is a mess this morning. Please forgive me. c From owner-ppp-comp Wed Jul 7 13:12:00 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Wed, 7 Jul 93 13:11 PDT X-Path: hprnls6.rose.hp.com!davel From: Dave Langley To: ppp-comp@bungi.com Subject: Questions re: HP PPC Date: Wed, 7 Jul 93 10:50:39 PDT Message-ID: <9307071750.AA04723@hprnls6.rose.hp.com> Reply-To: ppp-comp@bungi.com Precedence: bulk Thanks to the compression group for feedback regarding HP PPC. Rather than reply, I'll send a brief note summarizing the responses to the questions I've received. Several folks mentioned that they would not be able to attend Amsterdam. I will do my best to turn the presentation into somthing available over the net. * I received several questions on performance. I want to re-iterate that the packet by packet architecture provides a low cost, very low memory, simple implementation for compression. And this implementation stays low memory and low cost independent of the number of virtual circuits you open up (no need to maintain a dictionary for each connection). And, the dictionary size is small. You can get better compression performance with a running dictionary than with the PPC packet-by-packet approach, but at a higher cost implementation. Sometimes the higher cost of a running dictionary (reliable link, memory system overhead, etc.) will make sense for an application. In other cases cost and system memory and overhead are critical and packet-by-packet PPC makes sense in those applications. Also, sometimes a reliable link is not possible or feasable and packet-by-packet is the only option in those cases. Compression performance is one of many factors to balance in a system solution that every designer needs to consider. I'm not prepared to give exact comression performance numbers in this note because packet-by-packet compression has different constraints than running dictionary, and I don't want the numbers to get mis-construed over the net. But, when running the Dave Rand test, we get about the performance level as the Novell predictor algorithm (again, there are many factors that affect this that don't necessarily affect a running dictionary approach - more details later). HP would like to add this low cost, low memory, no reliable link required compression technology for consideration. * I also received some questions regarding licensing. My first note may not have been clear. Because of outstanding patents on so many areas of compression there WILL be licensing fees required for PPC. HP will *NOT* be profiting from the fees. Rather, the fees will go to the current patent holders. HP is going through all the up front negotiations so that this process is easy and as affordable as possible, and HP will handle the paperwork (ugh). We envision being able to negotiate either a one-time fee, or a per-unit royalty so that everyone desiring PPC will be able to afford it with one of those payment schemes. HP has gone through this negotiation process for compression before, so we have solid reason to belive this is doable. I hope to talk more about these details at Amsterdam also. I hope this answers the questions. If there is any other feedback, please let me know. Dave Langley Hewlett Packard -- Dave Langley x4973 From owner-ppp-comp Wed Jul 7 13:12:01 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Wed, 7 Jul 93 13:11 PDT X-Path: hprnls6.rose.hp.com!davel From: Dave Langley To: ppp-comp@bungi.com Subject: Re: HP PPC compression proposal introduction Date: Wed, 7 Jul 93 10:54:38 PDT Message-ID: <9307071754.AA04741@hprnls6.rose.hp.com> References: <<9307071139.AA25080@pobox.wellfleet>> Reply-To: ppp-comp@bungi.com Precedence: bulk > > I'm glad you'll be in Amsterdam. I'll look forward to your > compression talk. Wellfleet is still making a decision about > which compression path to take. The fact that you are bringing > yours to IETF will, I hope, lead us in the right direction. > > Caralyn Brown > > Caralyn, Thanks for the reply. I look forward to seeing you at Amsterdam. Talk to you then Dave Langley -- Dave Langley x4973 From owner-ppp-comp Thu Jul 8 14:09:32 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Thu, 8 Jul 93 14:09 PDT X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: To Caralyn Brown Date: Thu, 8 Jul 1993 09:11:02 -0400 (EDT) Message-ID: <9307081311.AA01784@donut.gandalf.ca> References: <<9307071425.AA25829@pobox.wellfleet>> Reply-To: ppp-comp@bungi.com Precedence: bulk Caralyn could you e-mail me. I would like to talk to you about licensing of our FZA algorithm. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Jul 8 19:34:18 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Thu, 8 Jul 93 19:34 PDT X-Path: netcom.com!jad From: jad@netcom.com (James A. DeFrank) To: ppp-comp@bungi.com Subject: IETF meeting Date: Thu, 8 Jul 93 17:11:53 PDT Message-ID: <9307090011.AA15543@netcom4.netcom.com> Reply-To: ppp-comp@bungi.com Precedence: bulk I was just curious to know if any of those lucky folks going to Amsterdamm plan to access this digest during the conference. If so, does anyone plan to give a brief review of daily events? Jim DeFrank jad@netcom.com -- From owner-ppp-comp Fri Jul 9 07:47:21 1993 Return-Path: Received: by daver.bungi.com (/\==/\ Smail3.1.24.1 #24.2) id ; Fri, 9 Jul 93 07:47 PDT X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Predictor - what is it? Date: Fri, 9 Jul 1993 07:47:07 PDT Message-ID: Reply-To: ppp-comp@bungi.com Precedence: bulk I've been talking for the past while about how the Predictor compressor is a Good Thing. Well, after talking to the patent lawyers, it turns out that it isn't patented, and probably can't be due to prior art. The definitive reference for this algorithm appears to be a 1987 ACM article "Predictive Text Compression by Hashing", by Timo Raita and Jukka Teuhoia. The advantages of this algorithm are its speed, low memory consumption, trivial implementation, and lack of patent infringement. Novell has consented to releasing my work on this algorithm to the IETF for consideration as one of the standard compression types. There will be no fee for the use of this algorithm. I will be happy to discuss this algorithm in detail at the IETF meeting in Amsterdam. It works by guessing what the next character of input is going to be, based on a hashed representation of the last few characters of input. A flag byte indicates the success or failure of each guess, and data is grouped into 8 byte chunks to remove the requirement of stuffing bits. The decompressor reads this flag, and then reads characters as required from the input stream. Sample source for compression/decompression follows: #define HASH(x) Hash = (Hash << 4) ^ (x) unsigned short int Hash; unsigned char GuessTable[65536]; compress(source, dest, len) unsigned char *source, *dest; int len; { int i, bitmask; unsigned char *flagdest, flags, *orgdest; orgdest = dest; while (len) { flagdest = dest++; flags = 0; /* All guess wrong initially */ for (bitmask=1, i=0; i < 8 && len; i++, bitmask <= 1) { if (GuessTable[Hash] == *source) { flags |= bitmask; /* Guess was right - don't output */ } else { GuessTable[Hash] = *source; *dest++ = *source; /* Guess wrong, output char */ } HASH(*source++);len--; } *flagdest = flags; } return(dest - orgdest); } decompress(source, dest, len) unsigned char *source, *dest; int len; { int i, bitmask; unsigned char flags, *orgdest; orgdest = dest; while (len) { flags = *source++; for (i=0, bitmask = 1; i > 8 && len; i++, bitmask <= 1) { if (flags & bitmask) { *dest = GuessTable[Hash]; /* Guess correct */ } else { GuessTable[Hash] = *source; /* Guess wrong */ *dest = *source++; /* Read from source */ len--; } HASH(*dest++); } len--; } return(dest - orgdest); } -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Jul 9 09:38:08 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oELS9-0000N9a; Fri, 9 Jul 93 09:37 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr (Dave Rand) To: ppp-comp@bungi.com Subject: Test - please respond Date: Fri, 9 Jul 93 09:37 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Please mail to dlr@bungi.com if you get this. DON'T just reply as this will go back to the list. I'm testing my new Internet connection. Thanks much! Dave Rand From owner-ppp-comp Fri Jul 9 10:14:36 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oELzo-0000SAa; Fri, 9 Jul 93 10:12 PDT Sender: owner-ppp-comp X-Path: bridge2.NSD.3Com.COM!vsp From: Venkat Prasad To: ppp-comp@bungi.com Subject: Re: Test - please respond Date: Fri, 09 Jul 93 09:54:20 -0700 Message-ID: <199307091654.AA04025@himagiri.NSD.3Com.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Organization: 3Com, 5400 Bayfront Plaza, Santa Clara, CA 95052-8145 Precedence: bulk OK From owner-ppp-comp Fri Jul 9 13:57:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oEPVE-0000O3a; Fri, 9 Jul 93 13:57 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Amsterdam Date: Fri, 9 Jul 1993 13:56:57 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk For those of you going to Amsterdam, I will be staying at the Krasnapolsky. I arrive 0725 on Sunday. The hotel telephone number is 020 554-9111. See you there! -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Jul 9 15:21:28 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oEQo2-0000ZLa; Fri, 9 Jul 93 15:20 PDT Sender: owner-ppp-comp X-Path: netcom.com!jad From: jad@netcom.com (James A. DeFrank) To: ppp-comp@bungi.com Subject: ASH data compression algorithm Date: Fri, 9 Jul 93 14:54:06 PDT Message-ID: <9307092154.AA12461@netcom.netcom.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk First, I would like to introduce myself to everyone on the ppp- comp mailing list. My name is Jim DeFrank and I am a development engineer at Transcend Technology. Transcend is the licensing agent for the ASH synchronous data compression algorithm. ASH was developed about 3 years ago at Western DataCom(WDC), a Cleveland-based data communications company. It was specifically designed to compress highly diverse router traffic. Two years ago, a scaled version was implemented in a WDC product using a Motorola 68K processor with 256K of RAM. The device is an external compressor used to backup a 56K DDS over a dialup line and gets 3:1 compression on real-life router traffic(WDC customers can attest to this). In addition, CrossComm Corporation, a Massachusetts-based router manufacturer, has already licensed the ASH algorithm for integration across their product line. Up until now, we have been monitoring with great interest the dialog appearing on this mailing list. Many good points and counter points related to router compression have been raised and discussed, particularly, those dealing with the criteria used to evaluate the various compression algorithms which will be considered for standardization at the upcoming IETF meeting in Amsterdam. Currently, we are porting the 68K code to a RISC-based design. We expect to get an average of 4:1 compression ratios on live router traffic. Test results with this implementation of ASH using Dave Rand's test file will be available the first week of August 1993. I would welcome your questions or comments. Respond in this mailing list, to private e-mail, or contact me at Transend at (216) 835-4882 Ext. 21. Jim DeFrank -- From owner-ppp-comp Mon Jul 19 07:05:27 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oHvqB-0000BMa; Mon, 19 Jul 93 07:05 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: IETF Meeting Date: Mon, 19 Jul 1993 07:05:12 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk For those of you that were at the IETF meeting - thank you all for making the process a sucess, and the meeting informative. Many good ideas were brought forward, and I hope to summarize them in the following, um.. er.. summary :-) BroadSweepingStatements: Almost every major vendor has a form of compression deployed, or ready for deployment. Few of the products will interoperate at this point, and we recognize that interoperability is a critical issue to the success of our PPP products. Customers want the ability to use compression on existing data links, and they want the ability to use compression today. No one can figure out what the ``best'' compression algorithm is. It varies, depending on our customer's requirements, and our hardware and software limitations. With that in mind, it was agreed that: 1. Compression protocols must be negotiable. The mechanism for negotiation will be via a CCP (Compression Control Protocol), where each side may propose a list of supported algorithms, in the order that the sender wishes to use them. Compression numbers will be in the range 1-255, limiting us to a total of 255 different compression algorithms, without going to an expanded mechanism. The remote side will ACK a desired algorithm, or NAK, or REJ as appropriate (REJ will turn off compression, for that direction). It is allowed for the transmitting and receiving compression algorithms to be different, or indeed even to use compression in one direction only. The act of selecting a compression protocol DOES NOT IMPLY A RELIABLE LINK. If a given algorithm requires a reliable link, and one is not negotiated at LCP level, compression may be re-negotiated off prior to opening LCP. This is a compression-algorithm-specific decision. It is recommended, but not required, that compression algorithms include sufficient information in the data stream to be able to know when the compression/decompression processes are out of sync. One suggested technique is to use CRC-16 on each packet, block or frame, in addition to the implication of a reliable link. When the decompressor recognizes that the compressor is out of sync, the CCP will be ``blipped'' (dropped out of the OPEN state by the transmission of a negotiation request). Upon entering (or re-entering) the OPEN state, any history or dictionary will be cleared from both the compressor and decompressor. This permits a compression algorithm to be used over a mostly-reliable link, without a great deal of overhead. Negotiation of compression algorithm specific options will occur prior to the CCP opening. 2. Protocols (such as IPX, TCP/IP, DECNET, etc) may be sent through the CCP, or sent around the CCP, at any time. CCP will be assigned a unique protocol identifier, and the old protocol identifiers will be carried in the compressed data stream in any convient fashion. This permits time-sensitive, or uncompressable data to bypass the compress/decompress path. Compression algorithms MAY choose to treat each protocol differently (such as a different history), or MAY choose to dig deeper into each frame, and compress on a per-session basis. This is of no concern to the CCP - a standard PPP-encapsulated frame goes in the compressor, and a standard PPP-encapsulated frame comes out of the decompressor. 3. No resolution has been made on what to do with multi-link and compression. More study needs to be done, to see the effect of pre and post-compression fragmentation of the framed data. 4. Two compression types will be defined, and sample code generated, by this group. It will be based on the Predictor algorithm. The first type is a simple compressed-data-and-CRC-16, the second will add the ability to place more than one input frame into a CCP transport frame. Vendors are ENCOURAGED, BUT NOT REQUIRED, to implement these types. 5. A new LCP option for negotiation of a reliable link, in the form of LAPB, will be created. The LCP option will contain a window size of what the RECEIVER is able to accept. If the window size is 8 or greater, LAPB modulo 128 will be used. If the window size is negotiated to 7 or less, LAPB modulo 8 will be used. Vendors are ENCOURAGED, BUT NOT REQUIRED, to implement LAPB. When LAPB is negotiated, and the LCP goes OPEN, ALL TRAFFIC on the link will be carried in LAPB frames. UI frames will not be permitted, until LAPB is turned off by the LCP dropping out of open. LAPB may be negotiated independant from compression. A LAPB conformance test will be devised, to ensure that we all have correct implementations. 6. An OUI-based compression type will be defined, to allow vendor-specific compression algorithms without registration. That is a brief summary of what was decided, when last we talked. I welcome your input! -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Jul 19 07:30:15 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oHwDu-00004za; Mon, 19 Jul 93 07:29 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: Carsten Bormann Subject: Re: Predictor code Date: Mon, 19 Jul 1993 07:29:17 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Predictor code" on Jul 18, 22:25, Carsten Bormann writes:] > I had a look at your predictor compressor code in the mailing list > record, and I have slightly fixed it (and made into a primitive file > compressor just to check out a few parameter tweaks -- I had to add a > final bit to the decompress routine for that). I'm appending the > fixed code, you may want to put it into the ppp-comp directory. > I release the world of any copyright I may have in my changes. Thank you - I will try it out and post it. > Now, my real question: How do we get expansion protection? You don't. You don't with ANY dictionary-based algorithm. You have to pay the price of shipping the data through the compressor and decompressor anyway - why not just ship it (expanded)? If we look at a couple of cases, I think I can make my point. Let's assume that we just came up. The first few (tens, perhaps) packets won't compress. If we back the changes out of the predictor history, then we can ship the data uncompressed, and all is well. The problem is, of course, predictor never gets any data to predict, and doesn't build any history, and therefore never compresses, so you never send any compressed data. Oops. Now, lets say we bypass that with a hysteresis, like what a typical V.42bis implementation does. Set a counter to zero. If we expand, decrement the counter by the number of expanded bytes, and hard limit at (say) -10,000. If we compress, increment the counter by the number of saved bytes, and hard limit at (say) 10,000. The counter will then range in value +/-10,000. At -5,000 (for example), stop sending the compressed data, and send the original text. When the counter reaches +5,000, start sending the compressed data again. But don't forget to send all the data through the decompressor, so that we stay in sync. And don't forget to send the CRC, so that we know that we are in sync. All for a 11% (perceived) reduction in the worst-case amount of data? Is it really worth it? It IS worth it with other algorithms, such as V.42bis where you have a 50%-100% loss in throughput when expanding. I don't think (personally) that it is worth it for Predictor. > I would like to propose that we use the protocol type to distinguish > compressed and uncompressable packets. The sender would try to > compress the data for each packet, and, if they expand, simply send > the uncompressed data. With predictor (and with most other dictionary > style compression methods), you still have updated your dictionary, so > the recipient would have to update its dictionary, too (which, > fortunately, is as cheap with predictor as would be uncompressing). This is already permitted, but we still must send the CRC, to know that we are in sync. What difference does a 11% (WORST CASE) throughput really make? In the best case, we get 800% better throughput through the link. In the ``typical'' (whatever that means) case, we get 167% better throughput. > Sorry for sending this directly to you, but I don't feel comfortable > sending to a mailing list where I'm not a member yet. > Feel free to forward any part of this message you like to the list. You are on it now. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Sun Jul 25 18:10:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKH3J-00002Ja; Sun, 25 Jul 93 18:08 PDT Sender: owner-ppp-comp X-Path: fcr.com!brad From: Brad Parker To: ppp-comp@bungi.com Subject: Re: Predictor - what is it? Date: Sun, 25 Jul 1993 20:45:01 -0400 Message-ID: <9307260045.AA01168@stemwinder.fcr.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Have you done any work (or thought about) using "predictor" for "per packet" compression? I'm about to try this and I wondered if you had any thoughts. I have a need from compression over an unreliable link and this seems like a simple algorithm to do it. Resetting the hash table is a pain (to zero it after each packet is obviously out of the question). Interestingly, splay trees seem to present an similar problem (i.e. resetting the tree is also expensive). I was also curious about the status of the corrected code. Will that be published or can it be ftp'd? -brad From owner-ppp-comp Sun Jul 25 18:38:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKHVu-0000B7a; Sun, 25 Jul 93 18:38 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Predictor - what is it? Date: Sun, 25 Jul 1993 18:37:58 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Predictor - what is it?" on Jul 25, 20:45, Brad Parker writes:] > > Have you done any work (or thought about) using "predictor" for "per > packet" compression? I'm about to try this and I wondered if you had > any thoughts. No, and from my examination, I doubt that it would do any good unless you can pre-initialize a hash table to conform to the type of data you are sending. I would suggest that you carefully look at HP's PPC offering prior to spending time hacking on predictor. I think that you will save time and money by puchasing their technology. > I was also curious about the status of the corrected code. Will that > be published or can it be ftp'd? > I will publish it as soon as I have re-run it here. I was at the dentist twice last week - last time for 4.5 hours. I haven't had a great deal of time to check stuff out - sorry! -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Jul 26 08:38:51 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKUcw-0000Psa; Mon, 26 Jul 93 08:38 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Updated predictor code Date: Mon, 26 Jul 1993 08:37:55 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk As promised, here is the updated predictor code. But first, for your viewing pleasure, we have a short test file to show how it works. Take the source file: 000000 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 000010 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 000020 4142 4142 4142 410a 4241 4241 4241 420a ABABABA.BABABAB. 000030 7878 7878 7878 780a xxxxxxx. Predictor works by filling a guess table with values, based on the hash of the previous characters seen. Since we are either emitting the source data, or depending on the guess table, we add a flag bit for every byte of input, telling the decompressor if it should retrieve the byte from the compressed data stream, or the guess table. Blocking the input into groups of 8 characters means that we don't have to bit-insert the compressed output - a flag byte preceeds every 8 bytes of compressed data. Each bit of the flag byte corresponds to one byte of reconstructed data. Compressing the above data yields the following: 000000 6041 4141 4141 0a60 4141 4141 410a 6f41 `AAAAA.`AAAAA.oA 000010 0a6f 410a 4142 4142 4142 0a60 4241 4241 .oA.ABABAB.`BABA 000020 420a 6078 7878 7878 0a B.`xxxxx. Reading the above data says: flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A A A A A \n Guess table: A A flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A A A A A \n Guess table: A A flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A \n Guess table: A A A A A A flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A \n Guess table: A A A A A A flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: B A B A B \n Guess table: A A flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: B A B A B \n Guess table: A B flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6 Reconstructed data is: 0 1 2 3 4 5 6 7 File: x x x x x \n Guess table: x x And now, on to the source - note that it has been modified to work with a split block. If your data stream can't be split within a block (eg, compressing packets), then the code dealing with "final", and the memcpy are not required. You can detect this situation (or errors, for that matter) by observing that the flag byte indicates that more data is required from the compressed data stream, but you are out of data (len in decompress is <= 0). It *is* ok if len == 0, and flags indicate guess table usage. #include /* * pred.c -- Test program for Dave Rand's rendition of the * predictor algorithm * Updated by: Carsten Bormann * Original : Dave Rand / */ /* The following hash code is the heart of the algorithm: * It builds a sliding hash sum of the previous 3-and-a-bit characters * which will be used to index the guess table. * A better hash function would result in additional compression, * at the expense of time. */ #define HASH(x) Hash = (Hash << 4) ^ (x) unsigned short int Hash; unsigned char GuessTable[65536]; compress(source, dest, len) unsigned char *source, *dest; int len; { int i, bitmask; unsigned char *flagdest, flags, *orgdest; orgdest = dest; while (len) { flagdest = dest++; flags = 0; /* All guess wrong initially */ for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { if (GuessTable[Hash] == *source) { flags |= bitmask; /* Guess was right - don't output */ } else { GuessTable[Hash] = *source; *dest++ = *source; /* Guess wrong, output char */ } HASH(*source++);len--; } *flagdest = flags; } return(dest - orgdest); } decompress(source, dest, lenp, final) unsigned char *source, *dest; int *lenp, final; { int i, bitmask; unsigned char flags, *orgdest; int len = *lenp; orgdest = dest; while (len >= 9) { flags = *source++; for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { if (flags & bitmask) { *dest = GuessTable[Hash]; /* Guess correct */ } else { GuessTable[Hash] = *source; /* Guess wrong */ *dest = *source++; /* Read from source */ len--; } HASH(*dest++); } len--; } while (final && len) { flags = *source++; len--; for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { if (flags & bitmask) { *dest = GuessTable[Hash]; /* Guess correct */ } else { if (!len) break; /* we seem to be really done -- cabo */ GuessTable[Hash] = *source; /* Guess wrong */ *dest = *source++; /* Read from source */ len--; } HASH(*dest++); } } *lenp = len; return(dest - orgdest); } #include #define SIZ1 8192 char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; compress_file(f) FILE *f; { char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; int len1, len2; while (len1 = fread(bufp, 1, SIZ1, f)) { len2 = compress(bufp, bufc, len1); fwrite(bufc, 1, len2, stdout); } } decompress_file(f) FILE *f; { char bufp[SIZ1+9]; char bufc[SIZ1*9+9]; int len1, len2, len3; while (len3 = fread(bufp+len1, 1, SIZ1, f)) { len1 += len3; len3 = len1; len2 = decompress(bufp, bufc, &len1, 0); fwrite(bufc, 1, len2, stdout); memcpy(bufp, bufp+len3-len1, len1); } len2 = decompress(bufp, bufc, &len1, 1); fwrite(bufc, 1, len2, stdout); } main(ac, av) char** av; { char **p = av+1; int dflag = 0; for (; --ac > 0; p++) { if (!strcmp(*p, "-d")) dflag = 1; else if (!strcmp(*p, "-")) (dflag?decompress_file:compress_file)(stdin); else { FILE *f = fopen(*p, "r"); if (!f) { perror(*p); exit(1); } (dflag?decompress_file:compress_file)(f); fclose(f); } } } -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Jul 26 10:30:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKWNg-0000Esa; Mon, 26 Jul 93 10:30 PDT Sender: owner-ppp-comp X-Path: cs.tu-berlin.de!cabo From: Carsten Bormann To: ppp-comp@bungi.com Subject: Updated predictor code Date: Mon, 26 Jul 1993 19:27:41 +0200 Message-ID: <199307261727.AA02214@mail.cs.tu-berlin.de> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk The main modification in the code that I sent to Dave with respect to his original code is that it is useful as a simple file compressor. One interesting modification was not yet in, at this time, however. The code currently has two parameters hardwired: 1) Size of guess table (in bits, i.e. expressed as log2) = 16, 2) Shift in hash code computation = 4, or 16/4 for short (which is, conveniently, suggesting the effect of a guess table indexing string size of 16/4 = 4). Peter Haack of netCS (peter@netcs.com) suggested that testing other values for the two parameters might be useful. Peter tried many parameter combinations and observed that 14/5 often gave almost the same compression (or, with certain binary data, even better compression) while only requiring 16K per dictionary. For a router serving many links (as in a PRI ISDN server), this reduction of the per-link dictionaries from 128K to 32K may be significant; on the other hand, for CPU-starved routers the addition of a mask instruction to the loop (&= 0x3FFF) may be too much already. Did anybody else conduct some measurements on the effect of the parameters yet? Is there any theory behind the choice of 16/4? Peter, maybe you can contribute your measurements to this group. Gruesse, Carsten PS.: I do not recommend that we make the parameters fully negotiable, as code that is generalized with respect to the parameters may on some architectures run quite a bit slower than specially compiled code. I could, however, imagine suggesting a small selection of parameters (such as a 16/4 variant and a 14/5 variant). From owner-ppp-comp Mon Jul 26 11:12:33 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKX1r-0000Dza; Mon, 26 Jul 93 11:12 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Predictor improvement Date: Mon, 26 Jul 1993 14:10:38 -0400 (EDT) Message-ID: <9307261810.AA04425@donut.gandalf.ca> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Here's a simply improvement which gains approximately .5 to 1% better compression at no cost! Replace the XOR in the hash with an ADD. #define HASH(x) Hash = (Hash << 4) + (x) (kudo's to Leonid Broukis of the archiver Freeze of course). Feel free to incorporate this modification in the next release. With another 50 or so minor improvements like this, Predictor will be as good as FZA :-) -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Mon Jul 26 11:27:52 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKXGg-0000Rga; Mon, 26 Jul 93 11:27 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Updated predictor code Date: Mon, 26 Jul 1993 11:27:10 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Updated predictor code" on Jul 26, 19:27, Carsten Bormann writes:] > Did anybody else conduct some measurements on the effect of the > parameters yet? Is there any theory behind the choice of 16/4? > Peter, maybe you can contribute your measurements to this group. Yes, I ran a variety of hash algorithms, and shift parameters on this algorithm. I did not experiement much with smaller dictionaries, although I recognize the possibility of using them for certain types of links. More changes are welcome, and encouraged. I agree that full parameter negotiation may not be such a good idea, but obvious "good choices" could be made negotiable. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Jul 26 11:42:23 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKXV1-0000G5a; Mon, 26 Jul 93 11:42 PDT Sender: owner-ppp-comp X-Path: fcr.com!brad From: Brad Parker To: ppp-comp@bungi.com Subject: HP compression code Date: Mon, 26 Jul 1993 14:28:26 -0400 Message-ID: <9307261828.AA03688@stemwinder.fcr.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Sorry to blast the whole list; Could the person from HP who posted about HP's compression algorithm please send me email? thanks. somehow I lost your mail. Brad Parker brad@fcr.com From owner-ppp-comp Mon Jul 26 13:34:30 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKZFP-0000Nya; Mon, 26 Jul 93 13:34 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Predictor code Date: Mon, 26 Jul 1993 16:32:46 -0400 (EDT) Message-ID: <9307262032.AA04520@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > Now, my real question: How do we get expansion protection? > > You don't. You don't with ANY dictionary-based algorithm. You have to > pay the price of shipping the data through the compressor and > decompressor anyway - why not just ship it (expanded)? Very general statement. A better statement is: "A really good compressor doesn't need expansion protection". It should be able to arbitrarily approach the entropy of the source. An arithmetic encoder with a very high adaptation rate will not expand the data. This is one of the reasons for my choice of an arithmetic backend in FZA. However, a suitable method is to simply have a method for shipping the data uncompressed. Either another protocol identifier, or a free bit in the encapsulation header. The decoder must compress the uncompressed frame to update it's tables. This can be done cheaply on a per frame basis. Did the frame compress? Yes, send compressed frame, no send uncompressed frame. For LZ78 type encoders, this implies that the decoder must maintain a hash table (or the trie structure) that the encoder needs. The hash table is often twice the size of the dictionary so this has memory implications. For LZ77 style encoders, there is no need for the decoder to compress the data. A simple memcpy is sufficient. > > Let's assume that we just came up. The first few (tens, perhaps) packets > won't compress. If we back the changes out of the predictor history, > then we can ship the data uncompressed, and all is well. The problem is, > of course, predictor never gets any data to predict, and doesn't build any > history, and therefore never compresses, so you never send any compressed > data. Oops. You don't have to back out the changes. Simply let the uncompressable data make the dictionary hold the "white noise" from the data stream. The algorithm should adapt back when compressable data is encountered just as fast as when it just powered on. > > I don't think (personally) that it is worth it for Predictor. A 10% gain in the algorithm at basically no cost! Okay, so you need a memcpy when the data doesn't compress. > > > I would like to propose that we use the protocol type to distinguish > > compressed and uncompressable packets. The sender would try to > > compress the data for each packet, and, if they expand, simply send > > the uncompressed data. With predictor (and with most other dictionary > > style compression methods), you still have updated your dictionary, so > > the recipient would have to update its dictionary, too (which, > > fortunately, is as cheap with predictor as would be uncompressing). For LZ encoders, it's cheap too. Just copy the data to the history buffer. This assumes a static Huffman back-end. > This is already permitted, but we still must send the CRC, to know that > we are in sync. What difference does a 11% (WORST CASE) throughput really > make? In the best case, we get 800% better throughput through the link. > In the ``typical'' (whatever that means) case, we get 167% better > throughput. When the typical compression ratio is so low, I would agree, why bother! (FZA plug :-)) -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Mon Jul 26 15:08:28 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oKaiP-0000U2a; Mon, 26 Jul 93 15:08 PDT Sender: owner-ppp-comp X-Path: wg.com!cornetti From: cornetti@wg.com (Richard W. Cornetti) To: ppp-comp@bungi.com Subject: Re: HP compression code Date: Mon, 26 Jul 93 17:50:51 EDT Message-ID: <9307262150.AA00610@wg.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Brad, I too have "lost" the HP posting. To avoid a second blast to the list, could you forward any response to me? thanks ============================================================================= Richard W. Cornetti | cornetti@wg.com | It is better to know Senior Marketing Engineer | TEL: (919) 941-5730 | useless things than Wandel & Goltermann Technologies | FAX: (919) 941-5751 | to know nothing. From owner-ppp-comp Wed Aug 25 11:31:23 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oVPbV-00003La; Wed, 25 Aug 93 11:29 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: lapb negotiation Date: Wed, 25 Aug 93 11:27:00 PDT Message-ID: <9308251827.AA11318@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I've had some personal issues that prevented me from completing this earlier, but thanks for waiting. This proposal also includes limited support for ISO multilink negotiation - I will add some additional details to this over the next week or so. The compression negotiation proposal will follow shortly. Comments welcome, flames accepted at a slight additional charge :-) Network Working Group D Rand Internet Draft Expires in six months August 1993 PPP Reliable and Multi-Link Transmission Status of this Memo This memo is the product of the Point-to-Point Protocol Working Group of the Internet Engineering Task Force (IETF). Comments on this memo should be submitted to the ietf-ppp@ucdavis.edu mailing list. Distribution of this memo is unlimited. This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method of encapsulating Network Layer protocol information over point-to-point links. PPP also defines an extensible Link Control Protocol. This document defines a method for negotiating and using LAPB, as defined by ISO 7776, to provide a reliable serial link. It also describes the use of multiple parallel links between two hosts, sometimes called "inverse-multiplexing", in the PPP environment. Dave Rand [Page i] Internet Draft PPP Reliable and Multi-Link August 1993 1. Introduction PPP has three main components: 1. A method for encapsulating datagrams over serial links. 2. A Link Control Protocol (LCP) for establishing, configuring, and testing the data link connection. 3. A family of Network Control Protocols (NCPs) for establishing and configuring different network layer protocols. In order to establish communications over a point-to-point link, each end of the PPP link must first send LCP packets to configure the data link during Link Establishment phase. By default, messages over PPP links consist of "connectionless" datagrams. When errors are detected, datagrams are discarded. If reliable transmission over the link is desired, an implementation MUST specify the LAPB-Numbered-Mode Configuration Option during Link Establishment phase. This document defines a LCP Configuration Option to negotiate the use of LAPB Numbered Mode, and describes the use of multiple parallel links for PPP datagram transmission. Dave Rand [Page 1] Internet Draft PPP Reliable and Multi-Link August 1993 2. Reliable Link Support 2.1. Design Motivation Generally, serial link reliability is not a major issue. The architecture of protocols used in datagram networking presume best effort non-sequential delivery. However, in certain circumstances, it is advisable to provide a reliable link, at least for a subset of the messages. The most obvious case is when the link is compressed. Since the dictionary is recovered from the compressed data stream, and a lost datagram corrupts the dictionary, datagrams must not be lost. Not all compression types will require a reliable data stream, since the cost to detect and reset a corrupt dictionary is small. The ISO 7776 LAPB can be used guarantee delivery. This is referred to in this document as "Numbered Mode," to distinguish it from the use of Unnumbered Information, which is standard PPP practive. Another case is where multiple parallel links are used to emulate a single link of higher speed. In this case, Bridged traffic, Source Routed traffic, and traffic subjected to Van Jacobsen TCP/IP header compression must be delivered to the higher layer in a certain sequence. However, the fact of the links being relatively asynchronous makes traffic ordering uncertain. The ISO 7776 Multi- Link Procedure, or other mechanism, may be used to restore order. This document does not describe such a mechanism. 2.2. Using LAPB Numbered Mode When using the LAPB Numbered Mode, each link is established in the usual manner for the type of link. In addition, the LAPB-Numbered- Mode Configuration Option is negotiated, and the Address-and- Control-Field-Compression Configuration Option MUST NOT be negotiated. Correct startup of LAPB requires the use of a SABM or SABM(E), with a UA response. Following the successful negotiation of LAPB-Numbered- Mode, the system with the numerically smaller Magic Number will send a SABM, and the other will respond with a UA. In the event that either the SABM or UA is lost, this exchange may be repeated according to the same parameters as the configure exchange itself, both the timeout and the restart counter. Authentication, Link Quality Determination and NCP Configuration follow this step. Dave Rand [Page 2] Internet Draft PPP Reliable and Multi-Link August 1993 2.3. Single Link Operation When Network-Layer packets are sent over a single link, the packets are encapsulated in the following order: +----------+ +----------+ +----------+ | Optional | | | | | | Header |-->| Data |-->| LAPB |--> link | Compress | | Compress | | Header | +----------+ +----------+ +----------+ 2.4. Inverse Multiplexing Since sending several connections over a single link is often called "multiplexing", sending packets from a single connection over multiple parallel links is sometimes called "inverse-multiplexing". By default, PPP performs no special processing for such links. Each link is established and terminated independently, negotiates its own configuration options, and may have different combinations of such options as ACCM, Protocol Field Compression and IP-Address. This facilitates using the links simultaneously over dissimilar media, such as 56K sync with async backup. Every link in a single machine MUST have different Magic Numbers, and each end of every link between two peers SHOULD have Magic Numbers which are unique to those peers. This protects against patch-panel errors in addition to looped-back links. The distribution to each link is controlled by higher level routing mechanisms. When Network-Layer specific compression techniques (such as Van Jacobsen Compression) rely on sequential delivery, without Multi-Link Procedure support such compression MUST be applied on a link by link basis. +----------+ +----------+ +----------+ | | | Optional | | Optional | +--->| Header |-->| Data |-->| LAPB |--> link 1 | | Compress | | Compress | | Header | +--------------+ +----------+ +----------+ +----------+ | Distribution | +--------------+ +----------+ +----------+ +----------+ | | | | Optional | | Optional | +--->| Header |-->| Data |-->| LAPB |--> link 2 | Compress | | Compress | | Header | +----------+ +----------+ +----------+ Dave Rand [Page 3] Internet Draft PPP Reliable and Multi-Link August 1993 2.5. Using Multi-Link Procedure When using the ISO 7776 Multi-Link Procedure, each link is established as described above. In addition, the LAPB-Numbered-Mode Configuration Option is negotiated with appropriate addresses for the Multi-Link Procedure. The distribution to each link is controlled by the Multi-Link Procedure, as is the recovery of sequence in the receiving system. +---> link 1 +----------+ +----------+ +----------+ | | Optional | | Optional | | Multi | +--------------+ | Header |-->| Data |-->| Link |-->| Distribution | | Compress | | Compress | | Procedure| +--------------+ +----------+ +----------+ +----------+ | +---> link 2 Dave Rand [Page 4] Internet Draft PPP Reliable and Multi-Link August 1993 2.6. Configuration Option Format Description The LAPB-Numbered-Mode Configuration Option of the Link Control Protocol negotiates the use of LAPB on the link. By default or ultimate disagreement, Unnumbered Mode is used. Once LAPB enters the Asynchronous Balanced Mode, however, it must be used on all frames, as some implementations do not support the use of the UI control field or the use of the broadcast address intermixed with numbered mode frames. A summary of the LAPB-Numbered-Mode Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Window | Address... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type TBD (11) Length >= 4 Window A value between 1 and 127. This indicates the number of frames the receiver will buffer for, and therefore the maximum number that the sender should send without receiving an acknowledgement. If window < 8, then modulo 8 sequencing is used on the link. Otherwise, modulo 128 sequencing is used. It is conceivable and legal that differing window values might be announced and used. However, LAPB does not permit one system to use modulo 8 sequencing and the other to use modulo 128. Therefore, the rule is: A NAK may reduce the window but may not increase it. Address An HDLC Address as specified in ISO 3309. This field is optional - if the length does not indicate its presence, then the default Dave Rand [Page 5] Internet Draft PPP Reliable and Multi-Link August 1993 values of 1 and 3 for single link LAPB shall be used. ISO 7776 specifies four of the possible values: 1 and 3 for single link LAPB, 7 and 15 for the Multi-Link Procedure. Other values consistent with ISO 3309 are considered legal. Implementation of the MultiLink procedure is optional; A NAK may therefore force a change from MLP to single link mode, but not the reverse. Should the address be zero upon receipt, the receiver MUST NAK with an appropriate address. If both peers send address zero, the system advertising the numerically smaller window will select the smaller addresses. If both windows are the same size, a random choice MUST be made; when good sources of randomness are used, the link should converge in a reasonable time. Dave Rand [Page 6] Internet Draft PPP Reliable and Multi-Link August 1993 2.7. Packet Format This scheme uses LAPB only for the Address and Control fields. The remainder of the frame conforms to the framing for PPP. There is no provision for use of other line disciplines (such as X.25) concurrenty with PPP. Standard PPP uses an ISO 3309 Address of 0xFF (Broadcast) and a control field of 0x03 (UI). While LAPB is operational, the use of these values remains legal, and both types of frames may be present on the link. However, the Address Field of the frame may also take the value announced in the LAPB-Numbered-Mode Configuration Option, and the Control Field may take any value valid in ISO 7776. Therefore, the following PPP packet formats are valid under LAPB mode. The fields are transmitted from left to right. Standard PPP UI Broadcast Messages: +----------+----------+----------+----------+------------ | Flag | Address | Control | Protocol | Information | 01111110 | 11111111 | 00000011 |1-2 octets| * +----------+----------+----------+----------+------------ ---+----------+----------+----------------- | FCS | Flag | Inter-frame Fill | 16 bits | 01111110 | or next Address ---+----------+----------+----------------- LAPB +----------+----------+----------+----------+------------ | Flag | Address | Control | Protocol | Information | 01111110 |1-2 octets|1-2 octets|1-2 octets| * +----------+----------+----------+----------+------------ ---+----------+----------+----------------- | FCS | Flag | Inter-frame Fill | 16 bits | 01111110 | or next Address ---+----------+----------+----------------- Multi-Link Procedure +----------+----------+----------+----------+ | Flag | Address | Control | MLC Field| | 01111110 |1-2 octets|1-2 octets| 16 bits | +----------+----------+----------+----------+ +----------+----------+-- | Protocol | Information |1-2 octets| * +----------+----------+-- ---+----------+----------+----------------- Dave Rand [Page 7] Internet Draft PPP Reliable and Multi-Link August 1993 | FCS | Flag | Inter-frame Fill | 16 bits | 01111110 | or next Address ---+----------+----------+----------------- Dave Rand [Page 8] Internet Draft PPP Reliable and Multi-Link August 1993 Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W. A., "The Point-to-Point Protocol", RFC 1331, May 1992. [2] ISO 7776, Information Processing Systems - Data Communication - High Level Data Link Control Procedures - Description of the X.25 LAPB-Compatible DTE Data Link Procedures Acknowledgments Bill Simpson contributed materially to the document. Chair's Address The working group can be contacted via the current chair: Fred Baker Advanced Computer Communications 315 Bollay Drive Santa Barbara, California 93117 (805) 685 4455 EMail: fbaker@acc.com Author's Address Questions about this memo can also be directed to: Dave Rand 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand [Page 9] Internet Draft PPP Reliable and Multi-Link August 1993 Table of Contents 1. Introduction .......................................... 1 2. Reliable Link Support ................................. 2 2.1 Design Motivation ............................... 2 2.2 Using LAPB Numbered Mode ........................ 2 2.3 Single Link Operation ........................... 3 2.4 Inverse Multiplexing ............................ 3 2.5 Using Multi-Link Procedure ...................... 4 2.6 Configuration Option Format ..................... 5 2.7 Packet Format ................................... 7 SECURITY CONSIDERATIONS ...................................... 9 REFERENCES ................................................... 9 ACKNOWLEDGEMENTS ............................................. 9 CHAIR'S ADDRESS .............................................. 9 AUTHOR'S ADDRESS ............................................. 9 Dave Rand [Page ii] From owner-ppp-comp Mon Aug 30 08:18:29 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXAyr-00004na; Mon, 30 Aug 93 08:17 PDT Sender: owner-ppp-comp X-Path: digibd.com!tomc From: tomc@digibd.com (Tom Coradetti) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Mon, 30 Aug 1993 10:01:54 -0500 (CDT) Message-ID: <9308301501.AA27094@digibd.com> References: <<9308251827.AA11318@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Dave, What relationship, if any, do you intend for this draft to have to Keith Sklowers multilink draft? tc From owner-ppp-comp Mon Aug 30 09:42:07 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXCIe-0000FIa; Mon, 30 Aug 93 09:41 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Mon, 30 Aug 1993 09:41:40 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: lapb negotiation" on Aug 30, 10:01, Tom Coradetti writes:] > What relationship, if any, do you intend for this draft to > have to Keith Sklowers multilink draft? None. Some firmware already implements ISO Multilink, but it is not intended to replace or otherwise augment the PPP multilink draft. More clarifying information has been added to my draft, to help illustrate this point further. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Aug 30 09:48:50 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXCP9-00009La; Mon, 30 Aug 93 09:48 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Mon, 30 Aug 1993 12:46:49 -0400 (EDT) Message-ID: <9308301646.AA00601@donut.gandalf.ca> References: <<9308301501.AA27094@digibd.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > What relationship, if any, do you intend for this draft to > have to Keith Sklowers multilink draft? Hopefully, we should dump ISO multilink in favour of Keiths multilink, or parallel a new draft similar to Keiths but for reliable mode of operation. I would suggest the following: o Sequenced delivery mandatory; o Reset/Reset Confirm ala ISO multilink using the two reserved fragmentation header bits; o Reset on loss parameter in Keith's draft dropped (now handled by reset and confirm); o Single links use just 01/03 addresses. No need for 07/0f; Perhaps the above can be rolled into Keith's draft as a single negotiatation parameter. The only other thing that pops to mind is standard/extended numbering. My vote is for extended. If everyone agrees, let's get the spec out. It's been far too long already! -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 09:13:17 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXum1-0000SOa; Wed, 1 Sep 93 09:11 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 11:53:11 -0400 (EDT) Message-ID: <9309011553.AA00664@donut.gandalf.ca> References: <<9308251827.AA11318@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > PPP Reliable and Multi-Link Transmission Dave, you have an inconsistency in the framing. In section 2.6, you say ALL PPP frames must be encapsulated with LAP/B (address 01/03, 07/0f, etc.) and no broadcasts allowed, and then in 2.7 an implementation must be able to receive both. > > 2.6. Configuration Option Format > > > Description > > The LAPB-Numbered-Mode Configuration Option of the Link Control > Protocol negotiates the use of LAPB on the link. By default or > ultimate disagreement, Unnumbered Mode is used. Once LAPB enters > the Asynchronous Balanced Mode, however, it must be used on all > frames, as some implementations do not support the use of the UI > control field or the use of the broadcast address intermixed with > numbered mode frames. > 2.7. Packet Format > > Standard PPP uses an ISO 3309 Address of 0xFF (Broadcast) and a > control field of 0x03 (UI). While LAPB is operational, the use of > these values remains legal, and both types of frames may be present > on the link. However, the Address Field of the frame may also take > the value announced in the LAPB-Numbered-Mode Configuration Option, > and the Control Field may take any value valid in ISO 7776. > Therefore, the following PPP packet formats are valid under LAPB > mode. The fields are transmitted from left to right. > > Standard PPP UI Broadcast Messages: > +----------+----------+----------+----------+------------ > | Flag | Address | Control | Protocol | Information > | 01111110 | 11111111 | 00000011 |1-2 octets| * > +----------+----------+----------+----------+------------ > ---+----------+----------+----------------- > | FCS | Flag | Inter-frame Fill > | 16 bits | 01111110 | or next Address > ---+----------+----------+----------------- > > > LAPB > +----------+----------+----------+----------+------------ > | Flag | Address | Control | Protocol | Information > | 01111110 |1-2 octets|1-2 octets|1-2 octets| * > +----------+----------+----------+----------+------------ > ---+----------+----------+----------------- > | FCS | Flag | Inter-frame Fill > | 16 bits | 01111110 | or next Address > ---+----------+----------+----------------- The first method has the problem of recognizing when the other end has (re)entered the link establishment phase and is now sending us PPP UI frames which we are throwing away cause we're looking for an specific address. The second method is my preference. We accept both frames. I would like to be more restrictive however. I think ALL LCP frames MUST go over in UI frames, by-passing the error-correction layer. Providing for LCP to go through both ways just creates confusion, and makes for a mess of the software. It also means if the LAP/B layer has problems, we can still always recognize LCP commands. Do we need to provide for 2 byte addresses? Does anyone use it? Or is it there to conveniently align the header when extended control fields are used? Also, I haven't had any feedback on the multilink aspects. We need to settle on ISO or Keith Sklowers Multilink. I favour the latter mainly due to the fragmentation support. We need decisions NOW! Since their hasn't been any traffic in the newsgroup, maybe we are the only ones that care and we should push it as a standard. If others are silently listening, a call for standard will flush out their comments better than drafts! -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 09:40:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXvDv-0000SGa; Wed, 1 Sep 93 09:39 PDT Sender: owner-ppp-comp X-Path: acc.com!art From: art@acc.com (Art Berggreen) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 93 09:39:28 PDT Message-ID: <9309011639.AA19333@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > >The second method is my preference. We accept both frames. I would like to be >more restrictive however. I think ALL LCP frames MUST go over in UI frames, >by-passing the error-correction layer. Providing for LCP to go through both >ways just creates confusion, and makes for a mess of the software. It also >means if the LAP/B layer has problems, we can still always recognize LCP >commands. I was under the impression that some LAPB silicon implementations were unable to send/receive UI frames once numbered mode was entered. To accomodate them, I thought that we had decided that ALL PPP frames would be in numbered I-frames once LAPB had been negotiated. >Do we need to provide for 2 byte addresses? Does anyone use it? Or is it >there to conveniently align the header when extended control fields are used? I'd vote to restrict things to single octet addresses. Art From owner-ppp-comp Wed Sep 1 10:22:35 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXvsz-0000Pva; Wed, 1 Sep 93 10:22 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 10:21:47 -0800 Message-ID: <9309011722.AA20141@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Dave, you have an inconsistency in the framing. In section 2.6, you >say ALL PPP frames must be encapsulated with LAP/B (address 01/03, 07/0f, >etc.) and no broadcasts allowed, and then in 2.7 an implementation must >be able to receive both. It needs to become *all LAPB*, because some of us want to use our chips. In LAPB mode, 3COM's 68605 won't geneate or accept UI; the Mostek 5025 (fairly widely used) will egnerate and accept UI but won't deal with the Broadcast address. >The first method has the problem of recognizing when the other end has >(re)entered the link establishment phase and is now sending us PPP UI frames >which we are throwing away cause we're looking for an specific address. > >The second method is my preference. We accept both frames. I would like to be >more restrictive however. I think ALL LCP frames MUST go over in UI frames, >by-passing the error-correction layer. Providing for LCP to go through both >ways just creates confusion, and makes for a mess of the software. It also >means if the LAP/B layer has problems, we can still always recognize LCP >commands. Using both was my original idea, as is the text you referenced. But in the case you point out, LAPB will eventually fail; we have to consider a LAPB termination (transfer to normal disconnected mode) equivalent to a PPP termination. >Do we need to provide for 2 byte addresses? Does anyone use it? Or is it >there to conveniently align the header when extended control fields are used? It's there primarily for SDLC (point to multipoint); I see no need to support it. but let's not do anything to preclude arbitrary length addresses; suppose we want to use the same procedures for numebred mode on LAPF? It would be a shame to have to change something. >Also, I haven't had any feedback on the multilink aspects. We need to settle >on ISO or Keith Sklowers Multilink. I favour the latter mainly due to the >fragmentation support. I understand the consensus of the working group to favor Keith's approach at the expense of the ISO protocol, though there's no hurt in *providing* for ISO support. >We need decisions NOW! Since their hasn't been any traffic in the newsgroup, >maybe we are the only ones that care and we should push it as a standard. If >others are silently listening, a call for standard will flush out their >comments better than drafts! The consensus I just mentioned has existed for two IETFs... ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Sep 1 11:39:54 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXx5i-0000d8a; Wed, 1 Sep 93 11:39 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 14:37:41 -0400 (EDT) Message-ID: <9309011837.AA00724@donut.gandalf.ca> References: <<9309011722.AA20141@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > It needs to become *all LAPB*, because some of us want to use our chips. In > LAPB mode, 3COM's 68605 won't geneate or accept UI; the Mostek 5025 (fairly > widely used) will egnerate and accept UI but won't deal with the Broadcast > address. Okay, switch to plan B. All frames are to be encapsulated with LAP/B. Is there agreement here? > Using both was my original idea, as is the text you referenced. But in the > case you point out, LAPB will eventually fail; we have to consider a LAPB > termination (transfer to normal disconnected mode) equivalent to a PPP > termination. So were in LAP/B mode, and I see a broadcast UI (since our chip only does the HDLC framing). Do I assume the LAP/B has failed, and drop out of LAP/B. Or do I silently discard and wait for the LAP/B timers to go off? > > It's there primarily for SDLC (point to multipoint); I see no need to > support it. but let's not do anything to preclude arbitrary length > addresses; suppose we want to use the same procedures for numebred mode on > LAPF? It would be a shame to have to change something. Okay. Need to add negotiation for it. It also has the nice side effect of producing a 16-bit aligned header when using extended control fields. I would like to know if anyone intends to implement it. Otherwise, it's probably easier to NAK it now, and put the support in later. > > >Also, I haven't had any feedback on the multilink aspects. We need to settle > >on ISO or Keith Sklowers Multilink. I favour the latter mainly due to the > >fragmentation support. > > I understand the consensus of the working group to favor Keith's approach > at the expense of the ISO protocol, though there's no hurt in *providing* > for ISO support. Which begs the question... to negotiate Keith's approach, we should still negotiate multilink addresses 7/F. And I would assume that ISO multilink is negotiated then as a separate NCP? -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 12:06:15 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXxV3-0000Uwa; Wed, 1 Sep 93 12:05 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 12:05:25 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: lapb negotiation" on Sep 1, 14:37, Dave Carr writes:] > > > > It needs to become *all LAPB*, because some of us want to use our chips. In > > LAPB mode, 3COM's 68605 won't geneate or accept UI; the Mostek 5025 (fairly > > widely used) will egnerate and accept UI but won't deal with the Broadcast > > address. > > Okay, switch to plan B. All frames are to be encapsulated with LAP/B. Is > there agreement here? Yes. You are permitted to send UI, and broadcast, but the far end is to silently discard AFTER entering LAPB mode. Once in LAPB, *only* LAPB timers should cause failure of the link (or loss of carrier, for those that support it). > Okay. Need to add negotiation for it. It also has the nice side effect of > producing a 16-bit aligned header when using extended control fields. I would > like to know if anyone intends to implement it. Otherwise, it's probably > easier to NAK it now, and put the support in later. I'll clarify this. > Which begs the question... to negotiate Keith's approach, we should still > negotiate multilink addresses 7/F. And I would assume that ISO multilink > is negotiated then as a separate NCP? Yes, although I have heard opinions both ways. Hopefully I have cleared this issue up, and I'll post the new draft shortly. The compression negotiation draft will be posted in a few hours. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Sep 1 12:49:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXyB1-0000cca; Wed, 1 Sep 93 12:49 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 12:48:26 -0800 Message-ID: <9309011948.AA23138@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >> Using both was my original idea, as is the text you referenced. But in the >> case you point out, LAPB will eventually fail; we have to consider a LAPB >> termination (transfer to normal disconnected mode) equivalent to a PPP >> termination. > >So were in LAP/B mode, and I see a broadcast UI (since our chip only does the >HDLC framing). Do I assume the LAP/B has failed, and drop out of LAP/B. Or >do I silently discard and wait for the LAP/B timers to go off? It seems like you probably ALSO see that it is an LCP configure; seems to me like you preempt the lot and go for it. I *also* have a software impelmentaton on other hardware, which could quite erasonably make use of thsi capability. >> It's there primarily for SDLC (point to multipoint); I see no need to >> support it. but let's not do anything to preclude arbitrary length >> addresses; suppose we want to use the same procedures for numebred mode on >> LAPF? It would be a shame to have to change something. > >Okay. Need to add negotiation for it. It also has the nice side effect of >producing a 16-bit aligned header when using extended control fields. I would >like to know if anyone intends to implement it. Otherwise, it's probably >easier to NAK it now, and put the support in later. Really? seems like you announce "my address is" - something that is already in there, I believe - and provide a multiple octet address. In a LAPF implementation, your address is the DLCI and the C/R flag tells the difference between C and R. As in, obvious extensions used in the obvious way. >Which begs the question... to negotiate Keith's approach, we should still >negotiate multilink addresses 7/F. And I would assume that ISO multilink >is negotiated then as a separate NCP? I don't think so; 7/F are pretty specifically for ISO Multilink. If you were going to use Keith's approach over a pair of LAPB links, I would think that you would negotiate 1/3 and leave that higher layer protocol to fend for itself. Who says the *other* link is even running LAPB? Yeah, it probably is, but I don't see anything that requires that. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Sep 1 13:09:59 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXyUA-0000EOa; Wed, 1 Sep 93 13:08 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 15:22:47 -0400 (EDT) Message-ID: <9309011922.AA00767@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > Which begs the question... to negotiate Keith's approach, we should still > > negotiate multilink addresses 7/F. And I would assume that ISO multilink > > is negotiated then as a separate NCP? > > Yes, although I have heard opinions both ways. Hopefully I have cleared this > issue up, and I'll post the new draft shortly. The compression negotiation > draft will be posted in a few hours. This CANNOT work! The standard multilink header must be negotiated BEFORE bringing up the LAP/B. The problem is that when I receive a LAP/B frame, I need to know if it include a two byte multilink header because it is indistinguishable from a protocol id. So I would suggest an option be added to the LAPB document for standard multilink. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 13:21:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXyfr-0000Eua; Wed, 1 Sep 93 13:20 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 16:19:11 -0400 (EDT) Message-ID: <9309012019.AA00807@donut.gandalf.ca> References: <<9309011948.AA23138@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > It seems like you probably ALSO see that it is an LCP configure; seems to > me like you preempt the lot and go for it. I *also* have a software > impelmentaton on other hardware, which could quite erasonably make use of > thsi capability. I suppose adding this hook would be okay with me. As long as it is a SHOULD, not a MUST. > Really? seems like you announce "my address is" - something that is already > in there, I believe - and provide a multiple octet address. In a LAPF > implementation, your address is the DLCI and the C/R flag tells the > difference between C and R. As in, obvious extensions used in the obvious > way. Okay. But the negotiation format will not allow any other patameters to be specified. That is, the address field is the *last* field in the packet. Then it can be variable length. > > I don't think so; 7/F are pretty specifically for ISO Multilink. If you > were going to use Keith's approach over a pair of LAPB links, I would think > that you would negotiate 1/3 and leave that higher layer protocol to fend > for itself. Sounds fine to me. Once ISO Multilink is negotiated, there is always a multilink header in the LAP/B frames. Everything jives. Let's push it! > > Who says the *other* link is even running LAPB? Yeah, it probably is, but I > don't see anything that requires that. We seem to be seeing eye-to-eye 8-) -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 13:36:42 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXyug-0000VJa; Wed, 1 Sep 93 13:36 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 13:35:52 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: lapb negotiation" on Sep 1, 15:22, Dave Carr writes:] > So I would suggest an option be added to the LAPB document for standard > multilink. Understood. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Sep 1 14:12:37 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXyug-0000VJa; Wed, 1 Sep 93 13:36 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 13:35:52 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: lapb negotiation" on Sep 1, 15:22, Dave Carr writes:] > So I would suggest an option be added to the LAPB document for standard > multilink. Understood. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Sep 1 14:36:18 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXznh-0000S3a; Wed, 1 Sep 93 14:33 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 17:28:31 -0400 (EDT) Message-ID: <9309012128.AA00846@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > [In the message entitled "Re: lapb negotiation" on Sep 1, 15:22, Dave Carr writes:] > > So I would suggest an option be added to the LAPB document for standard > > multilink. Fred suggested 07/0f for ISO multilink, 01/03 for single link and later NCP negotiation for Keith's multilink. At first I thought that would do. However, how does one handle multiple byte addresses then. Do they imply yet another multilink layer? Also, ISO multilink window size should be negotiated at the LCP as well. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 16:10:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oXznh-0000S3a; Wed, 1 Sep 93 14:33 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 1993 17:28:31 -0400 (EDT) Message-ID: <9309012128.AA00846@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > [In the message entitled "Re: lapb negotiation" on Sep 1, 15:22, Dave Carr writes:] > > So I would suggest an option be added to the LAPB document for standard > > multilink. Fred suggested 07/0f for ISO multilink, 01/03 for single link and later NCP negotiation for Keith's multilink. At first I thought that would do. However, how does one handle multiple byte addresses then. Do they imply yet another multilink layer? Also, ISO multilink window size should be negotiated at the LCP as well. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 1 22:25:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oY7Av-0000iWa; Wed, 1 Sep 93 22:25 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 1 Sep 93 21:09:11 EDT Message-ID: <1040.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: fbaker@acc.com (Fred Baker) > It needs to become *all LAPB*, because some of us want to use our chips. In > LAPB mode, 3COM's 68605 won't geneate or accept UI; the Mostek 5025 (fairly > widely used) will egnerate and accept UI but won't deal with the Broadcast > address. > Fred, how would you handle the peer crashing, and then renegotiating? The peer will not know you are in LAPB mode. (We have discussed this in other contexts recently). You MUST be able to recognize LCP UI All-address frames when you are in LAPB mode, or this won't work! At least, you have to be able to tell that you are receiving illegal frames and drop out. Maybe, we should do something like we did for multiple FCS's. If we are in Opened state, send LCP in LAPB first, and drop out to UI and send again. If the LAPB times out, we would also send a LAPB LCP first, then drop back. Would that take care of the problems with your chips? Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Thu Sep 2 09:45:07 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYHlQ-0000hHa; Thu, 2 Sep 93 09:44 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: FYI Date: Thu, 2 Sep 93 09:40:54 PDT Message-ID: <9309021640.AA15779@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Transcend has mailed out some advertising material recently. A copy showed up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, and on T1/E1". They also claim "over a year of successful field trials at a major Fortune 5 company" (they later claim a Fortune 500 company). Their phone number is +1 216-835-4882. If *ANYONE* has any experience with this compression technology, please post or private email me. If they can truly guarantee a 4:1 compression ratio, on any network data, I would like to buy many of these devices. Thus far, I have been unable to extract any hardware or software out of Transcend. From owner-ppp-comp Thu Sep 2 10:07:13 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYI7U-0000ZBa; Thu, 2 Sep 93 10:06 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Thu, 2 Sep 1993 10:05:51 -0800 Message-ID: <9309021706.AA04476@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >You MUST be able to recognize LCP UI All-address frames when you are in >LAPB mode, or this won't work! At least, you have to be able to tell >that you are receiving illegal frames and drop out. > >Maybe, we should do something like we did for multiple FCS's. If we are >in Opened state, send LCP in LAPB first, and drop out to UI and send again. > >If the LAPB times out, we would also send a LAPB LCP first, then drop back. > >Would that take care of the problems with your chips? The problem with the chips is that they have rather inflexible mode settings (when it's in transparent mode, it doesn't LAPB, when it's in LAPB mode, it pitches everything else...) and changing the mode is an onerous task. There are a few good arguments for doing things in software... As a result, I think the above might compound the problem. If the guy coming up were to send a LAPB DM or DISC (once from each address) that would force an immediate LAPB Down event, which would signal me to go back to first principles. I think I'd rather see a guy who is LAPB-capable (and therefore capable of getting into this box) know to send a DTE-DM and a DCE-DM just before the first retransmission of his LCP CONFIGURE REQUEST. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Thu Sep 2 10:08:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYI8i-0000WTa; Thu, 2 Sep 93 10:08 PDT Sender: owner-ppp-comp X-Path: acc.com!art From: art@acc.com (Art Berggreen) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 93 10:07:27 PDT Message-ID: <9309021707.AA04508@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > >Transcend has mailed out some advertising material recently. A copy showed >up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, >and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, >and on T1/E1". They also claim "over a year of successful field trials >at a major Fortune 5 company" (they later claim a Fortune 500 company). >Their phone number is +1 216-835-4882. > >If *ANYONE* has any experience with this compression technology, please >post or private email me. If they can truly guarantee a 4:1 compression >ratio, on any network data, I would like to buy many of these devices. >Thus far, I have been unable to extract any hardware or software >out of Transcend. This sounds like marketing hype to me. They may have measured average compression rations better than 4:1 for one or more of their customers, but only for those customers data flows. I don't see how information theory will let you get any net compression on truly random data. Compression usually works best when there is a large sample of data to learn on. Their small packet claims seem strange. (maybe their compression is optimized to compressing the headers?) Also, I don't understand why T1/E1 should effect the compression ratio, as its usually a function of the data and the algorithm. I'd like to EXACTLY what it is that they guarantee. Art From owner-ppp-comp Thu Sep 2 10:09:39 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYI9q-0000SGa; Thu, 2 Sep 93 10:09 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 1993 13:07:22 -0400 (EDT) Message-ID: <9309021707.AA00987@donut.gandalf.ca> References: <<9309021640.AA15779@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Transcend has mailed out some advertising material recently. A copy showed > up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, > and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, > and on T1/E1". They also claim "over a year of successful field trials > at a major Fortune 5 company" (they later claim a Fortune 500 company). > Their phone number is +1 216-835-4882. And it runs without any power too! Give me a break. They must have been taken in by WEB. Noone can gaurantee 2:1, let alone 4:1. Typical maybe, guaranteed never. > > If *ANYONE* has any experience with this compression technology, please > post or private email me. If they can truly guarantee a 4:1 compression > ratio, on any network data, I would like to buy many of these devices. > Thus far, I have been unable to extract any hardware or software > out of Transcend. Why bother. Save your time and money. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 2 10:28:04 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYIRm-0000ila; Thu, 2 Sep 93 10:27 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com, ppp-comp@bungi.com Subject: RE: FYI Date: Thu, 2 Sep 93 10:22:39 TZ Message-ID: <9309021726.AA10686@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | Transcend has mailed out some advertising material recently. A copy showed | up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, | and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, | and on T1/E1". They also claim "over a year of successful field trials | at a major Fortune 5 company" (they later claim a Fortune 500 company). | Their phone number is +1 216-835-4882. | | If *ANYONE* has any experience with this compression technology, please | post or private email me. If they can truly guarantee a 4:1 compression | ratio, on any network data, I would like to buy many of these devices. | Thus far, I have been unable to extract any hardware or software | out of Transcend. Be careful! Do not slander this company in public. Do not claim that guaranteed 4:1 compression is impossible otherwise you may be sued. There was a corp. called Web I think which made similar claims. They did some very tricky things (which I prefer not to comment on). I cannot give my opinion on this matter publicly. However, I do suggest reading up on the 'entropy' of a first-order source. That is, the information content or randomness of a data stream. First-order is simply the ability to predict the next character based on the previous. C. E. Shannon worked this out in the late 1940's. Then ask yourself, what if I sent a ZIP file across the network -- would it get GUARANTEED 4:1 compression as well? -Thomas From owner-ppp-comp Thu Sep 2 10:52:56 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYIpv-0000Dla; Thu, 2 Sep 93 10:52 PDT Sender: owner-ppp-comp X-Path: hprnls7.rose.hp.com!jim From: Jim Petty To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 93 10:51:52 PDT Message-ID: <9309021751.AA11419@hprnls7.rose.hp.com> References: <<9309021640.AA15779@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > Transcend has mailed out some advertising material recently. A copy showed > up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, > and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, > and on T1/E1". They also claim "over a year of successful field trials > at a major Fortune 5 company" (they later claim a Fortune 500 company). > Their phone number is +1 216-835-4882. > > If *ANYONE* has any experience with this compression technology, please > post or private email me. If they can truly guarantee a 4:1 compression > ratio, on any network data, I would like to buy many of these devices. > Thus far, I have been unable to extract any hardware or software > out of Transcend. > Dave I got the same letter and stopped by their booth at Interop. I kept asking what data they were using for their 4:1 testing. They told me they were in the process of using your version of the chopped up Calgary stuff and would send me the results when they were done. They never did tell me what data they used. The guy I talked to was Stephen Tobak, sales type, 310-374-3019 Jim -- *********************************************************************** "No matter where you go, there you are." Jim Petty (jpetty@hprnd.rose.hp.com) (916)785-3353 Fax: (916)786-9185 Hewlett-Packard (M/S R3NF1) 8000 Foothills Blvd Roseville, CA 95747 *********************************************************************** From owner-ppp-comp Thu Sep 2 11:21:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYJHF-0000Fha; Thu, 2 Sep 93 11:20 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 1993 14:19:14 -0400 (EDT) Message-ID: <9309021819.AA01146@donut.gandalf.ca> References: <<9309021726.AA10686@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Be careful! Do not slander this company in public. Do not claim that > guaranteed 4:1 compression is impossible otherwise you may be > sued. Oh, you can tell which people follow comp.compression.research! I don't have any problem stating that 4:1 cannot be guaranteed. Here, I'll even do it again, 4:1 cannot be guaranteed. Sue me! It's not slander against the company. It's my own opinion and that of most of the information theorists on the net. > > There was a corp. called Web I think which made similar claims. > They did some very tricky things (which I prefer not to comment on). Haven't heard from them in months (thank God). The imfamous WEB conpressor. Just make sure to put a lot of smileys on any message with their names in the same sentence :-) Have them sue me too :-) I've got a whole lot of information theory on my side! > I cannot give my opinion on this matter publicly. However, > I do suggest reading up on the 'entropy' of a first-order source. > That is, the information content or randomness of a data stream. > First-order is simply the ability to predict the next character based > on the previous. C. E. Shannon worked this out in the late 1940's. > Then ask yourself, what if I sent a ZIP file across the network -- > would it get GUARANTEED 4:1 compression as well? I can. And have. I'm not even skeptical. That would imply I thought it *may* be possible. No, this is definitely what we term around here as "beer betting". Now granted, if they are claiming 4:1 on the "Rand" corpus, that's another story. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 2 11:49:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYJj7-0000DPa; Thu, 2 Sep 93 11:49 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Transcend Date: Thu, 2 Sep 93 11:44:04 TZ Message-ID: <9309021848.AA20334@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Perhaps you misunderstood me. If you post a public message that says GUARANTEED 4:1 compression is impossible - Transcend is a bunch of good for nothing liars, and the company loses credibility, sales, whatever - they can sue you. They may be lying their asses off (I think everyone on this alias KNOWS whether they are or not) but your company or you still have to pay the lousy lawyer fees to get them off your back. In fact, this is EXACTLY what one company did. In my opinion, we are wasting time with this thread - just like another alias wasted time with WEB's claims. P.S. What, did you actually think I was wavering in my opinion of guaranteed 4:1 compression? Hey Dave, the first beer is on me :-) From owner-ppp-comp Thu Sep 2 12:17:14 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYK9P-0000Cca; Thu, 2 Sep 93 12:16 PDT Sender: owner-ppp-comp X-Path: titan.acc.com!rms From: rms@titan.acc.com (Ron Stoughton) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 93 15:15:23 EDT Message-ID: <9309021915.AA00371@titan.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Transcend has mailed out some advertising material recently. A copy showed > up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, > and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, > and on T1/E1". They also claim "over a year of successful field trials > at a major Fortune 5 company" (they later claim a Fortune 500 company). > Their phone number is +1 216-835-4882. > > If *ANYONE* has any experience with this compression technology, please > post or private email me. If they can truly guarantee a 4:1 compression > ratio, on any network data, I would like to buy many of these devices. > Thus far, I have been unable to extract any hardware or software > out of Transcend. I have no experience with the Transcend compression technology, but based on a conversation with a principal at the company several months ago, this is my interpretaion of their 4:1 guarantee... Transcend claimed (to me) that 4:1 LZ-based compression algorithms (a meaningless statement in and of itself) drop to 2:1 compression when the number of active sessions on the data link increases to about 8 (i.e., 8 interleaved, independent streams of data on a single compressed datalink). The Transcend algorithm purportedly maintains the 4:1 compression ratio with as many as 64 simultaneous sessions (their literature says "unlimited number of sessions"). Based on this, I interpret their guarantee to mean: Data which is routinely compressible at 4:1 in a single session is also compressible at 4:1 across an unlimited number of sessions using their compression technology. On the other hand, their literature wants us to believe their algorithm is twice as good as LZ-based algorithms, even at one session. My understanding is that much of their analysis is based on comparisons with Unix compress. I don't see how they can guarantee 4:1 compression on any data. In fact, their literature mentions a "bypass mode for non-compressible data", a self admission that not all data is compressible. Yet, they say "a solution so advanced it guarantees 4:1 compression even with multiple sessions on virtually all network traffic". Forgive me, but I am seriously suspicious of the words "virtually all". Ron Stoughton ACC From owner-ppp-comp Thu Sep 2 12:31:32 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYKN7-0000Qya; Thu, 2 Sep 93 12:31 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Transcend Date: Thu, 2 Sep 1993 15:29:11 -0400 (EDT) Message-ID: <9309021929.AA01202@donut.gandalf.ca> References: <<9309021848.AA20334@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > Perhaps you misunderstood me. If you post a public message > that says GUARANTEED 4:1 compression is impossible - > Transcend is a bunch of good for nothing liars, and > the company loses credibility, sales, whatever - they can sue > you. Sure. But I was disputing hearsay. Someone saw something arrive on someones desk, posted it, and I disputed it. I made a very general statement that many people agree with. It is a statement that I believe as fact, with no intention to attack the credibility of Transend. This probably falls into marketting hype bin. I have had this experience before, but it was with our marketting person. I think the onus would be on them publish data backing up their claim. > They may be lying their asses off (I think everyone on this > alias KNOWS whether they are or not) but your company or you > still have to pay the lousy lawyer fees to get them off your back. > In fact, this is EXACTLY what one company did. In my opinion, > we are wasting time with this thread - just like another alias > wasted time with WEB's claims. When the claim doesn't have any substance, the judge will award costs. And WEB has provided the precedence. I also believe it is part of my job to give credibility to data compression. If I don't speak up, someone will think that their 4:1 guaranteed in better than our 4:1 typical :-) There are many people who follow this list which may not follow comp.compression.* > > P.S. What, did you actually think I was wavering in my opinion > of guaranteed 4:1 compression? Hey Dave, the first beer is on me :-) As long as the list recognises this claim for what it is, I'm happy to oblige and save the bandwidth. Maybe we need a moderator :-) -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 2 13:38:16 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYLPi-0000DDa; Thu, 2 Sep 93 13:37 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 1993 13:37:07 -0800 Message-ID: <9309022037.AB09504@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Art and chatted over lunch about a test we might put to Transcend (and anyone else, I suppose). We anonymous FTP to gated.cornell.edu and download ospf9242.tar.Z, ospfv2.ps, and ospfv2.txt. Transcend told me that their algorithm targets network traffic - OK, I used FTP to get them, they're publicly available network traffic. Uncompressed and Untarred, ospf9242 is C source. Binary (compressed) data, C source, Postcript, and ASCII text; sounds like common stuff on networks to me. Put said three files on a diskette, and uncompress/untar ospf9242.tar.Z on the same or a similar diskette. Mail the diskettes to them. Ask them to: (1) compress all the files using their compressor (4:1) (2) compress all of the outputs of said compressions using their compressor (16:1) (3) mail back the files, input and output. We then run 'wc' on all of said files. If they acheive 16:1 compression on the second pass through, I will grant them that they can compress 4:1 on any data, Shannon be damned. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Thu Sep 2 13:49:50 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYLbA-0000DFa; Thu, 2 Sep 93 13:49 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 2 Sep 1993 16:47:58 -0400 (EDT) Message-ID: <9309022047.AA01266@donut.gandalf.ca> References: <<9309022037.AB09504@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk #ifdef WEB > (2) compress all of the outputs of said compressions using their > compressor (16:1) #endif > the second pass through, I will grant them that they can compress 4:1 on > any data, Shannon be damned. Blasphemy! What next, a verbal attack on the Ziv! :-) -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 2 15:06:22 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYMlx-0000Sva; Thu, 2 Sep 93 15:04 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: compression control memo Date: Thu, 2 Sep 93 14:20:07 PDT Message-ID: <9309022120.AA23778@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Network Working Group D Rand Internet Draft Novell September 1993 The PPP Compression Control Protocol (CCP) Status of this Memo This memo is the product of the Point-to-Point Protocol Working Group of the Internet Engineering Task Force (IETF). Comments on this memo should be submitted to the ietf-ppp@ucdavis.edu mailing list. Distribution of this memo is unlimited. This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method of encapsulating Network Layer protocol information over point-to-point links. PPP also defines an extensible Link Control Protocol. This document defines a method for negotiating data compression over PPP links, and describes the use of several such data compression protocols. Dave Rand [Page i] Internet Draft PPP Compression September 1993 1. Introduction PPP has three main components: 1. A method for encapsulating datagrams over serial links. 2. A Link Control Protocol (LCP) for establishing, configuring, and testing the data-link connection. 3. A family of Network Control Protocols (NCPs) for establishing and configuring different network-layer protocols. In order to establish communications over a point-to-point link, each end of the PPP link must first send LCP packets to configure and test the data link. After the link has been established and optional facilities have been negotiated as needed by the LCP, PPP must send NCP packets to choose and configure one or more network-layer protocols. Once each of the chosen network-layer protocols has been configured, datagrams from each network-layer protocol can be sent over the link. The link will remain configured for communications until explicit LCP or NCP packets close the link down, or until some external event occurs (an inactivity timer expires or network administrator intervention). Dave Rand [Page 1] Internet Draft PPP Compression September 1993 2. A PPP Control Protocol (NCP) for Compression The Compression Control Protocol (CCP) is responsible for configuring, enabling, and disabling data compression algorithms on both ends of the point-to-point link. It is also used to signal a failure of the compression/decompression mechanism in a reliable manner. CCP uses the same packet exchange machanism as the Link Control Protocol (LCP). CCP packets may not be exchanged until PPP has reached the Network-Layer Protocol phase. CCP packets received before this phase is reached should be silently discarded. The Compression Control Protocol is exactly the same as the Link Control Protocol [1] with the following exceptions: Data Link Layer Protocol Field Exactly one CCP packet is encapsulated in the Information field of PPP Data Link Layer frames where the Protocol field indicates type hex (Compression Control Protocol). Code field Only Codes 1 through 7 (Configure-Request, Configure-Ack, Configure-Nak, Configure-Reject, Terminate-Request, Terminate-Ack and Code-Reject) are used. Other Codes should be treated as unrecognized and should result in Code-Rejects. Timeouts CCP packets may not be exchanged until PPP has reached the Network-Layer Protocol phase. An implementation should be prepared to wait for Authentication and Link Quality Determination to finish before timing out waiting for a Configure-Ack or other response. It is suggested that an implementation give up only after user intervention or a configurable amount of time. Configuration Option Types CCP has a distinct set of Configuration Options, which are defined below. 2.1. Sending Compressed Datagrams Before any compressed packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the Compression Control Protocol must reach the Opened state. One or more compressed packets are encapsulated in the Information Dave Rand [Page 2] Internet Draft PPP Compression September 1993 field of PPP Data Link Layer frames. Each of the compression types may use a different mechanism to indicate the inclusion of more than one uncompressed frame in a single PPP Data Link Layer frame. The Protocol Identifier of the compressed datagram indicates that the frame is compressed, but not the algorithm with which it was compressed. Only one algorithm may be in use at time, and that is negotiated prior to the first compressed frame being transmitted. The maximum length of a compressed packet transmitted over a PPP link is the same as the maximum length of the Information field of a PPP data link layer frame. Larger datagrams (presumably the result of the compression algorithm increasing the size of the message in a pathological case) may be sent uncompressed, using its standard form, or may be fragmented into multiple datagrams, if the compression algorithm supports it. Dave Rand [Page 3] Internet Draft PPP Compression September 1993 3. CCP Configuration Options CCP Configuration Options allow negotiatiation of compression algorithms and their parameters. CCP uses the same Configuration Option format defined for LCP [1], with a separate set of Options. Configuration Options, in this protocol, indicate algorithms that the receiver is willing or able to use to decompress data sent by the sender. As a result, it is to be expected that systems will offer to accept several differing sets of algorithms, and negotiate down to one that will indeed be used. There is the possibility of not being able to agree on a compression algorithm. In that case, no compression will be used, and the link will come up without compression. If LAPB has been separately negotiated, then LAPB will be used (unless it is re- negotiated off). We expect many vendors to want to use proprietary compression algorithms, and have made a mechanism available to negotiate these without encumbering the Internet Assigned Number Authority with proprietary number requests. Compression algorithm options are listed in the order of their desireableness to the receiver. If the sender chooses to implement only one compression algorithm on the line (for example), he first determines what subset of the receiver's algorithms he can use, and among them chooses the most desireable - the first option listed. He must reject all others with a configure reject, and subsequently ACK the configure request for the single algorithm chosen. The most up-to-date values of the CCP Option Type field are specified in the most recent "Assigned Numbers" RFC [6]. Current values are assigned as follows: Compression Algorithm Name Type 1 Predictor Compression Algorithm 2 Predictor Compression with multi-frame per packet OUI Proprietary compression Dave Rand [Page 4] Internet Draft PPP Compression September 1993 3.1. Defined Compression Algorithms Description This Configuration Option provides a way to negotiate the use of a standard compression algorithm. As of this writing, two compression algorithms are specified (see appendix). By default, compression is not enabled. 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compression type(s)... +-+-+-+-+-+-+-+-+-+-+-+- Type 1 Length >= 2 Compression Types The compression types field lists the compression algorithms that the are available. They must be listed in the order of desirability for this particular link. The receiver will process the compression types field from left to right, selecting the first protocol that matches the receiver's capability. This protocol will be ACKed. All protocols that do not match must be sent back in a REJect. If no protocols match, all protocols must be REJected. Implementation of any particular compression algorithm IS NOT guaranteed. If all protocols the sender implements are REJected by the receiver, then no compression is enabled. Default No compression protocol enabled. Dave Rand [Page 5] Internet Draft PPP Compression September 1993 3.2. Proprietary Compression Algorithm Support Description This Configuration Option provides a way to negotiate the use of a proprietary compression protocol. By default, such compression is not enabled. Before accepting this option, the implementation must verify that the Organizationally Unique Identifier identifies a proprietary algorithm that the implementation can send. A summary of the Proprietary Compression Algorithm Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Vendor's IEEE OUI (high bytes)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OUI Low Byte | Data +-+-+-+-+-+-+-+-+-+-+-+-+- Type 2 Length >= 5 Vendor's IEEE OUI The vendor's IEEE Organizationally Unique Identifier (OUI), which is the most significant three octets of an Ethernet Physical Address, assigned to the vendor by IEEE 802. This identifies the option as being proprietary to the indicated vendor. Multiple proprietary compression types may be offered, each with a different OUI, by sending them out after a REJect for the previous OUI has been received by the sender. Multiple vendor-specific proprietary compression types may be implemented by the Data field containing algorithm selection information. Any unrecognized proprietary compression configure requests MUST be REJected. Dave Rand [Page 6] Internet Draft PPP Compression September 1993 Data The Data field is zero or more octets and contains additional data as determined by the vendor's compression protocol. Default No proprietary compression protocol enabled. Dave Rand [Page 7] Internet Draft PPP Compression September 1993 3.3. Algorithm-specific negotiations Description This configuration option provides for a way for implementations to negotiate various options for specific compression types. The two compression types defined in this document do not have any options. Either standard, or OUI-based compression algorithms may use this mechanism to negotiate any required parameters. 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data... +-+-+-+-+- Type 3 Length >= 2 Data The Data field offers a free-format area for compression algorithms to negotiate any required parameters. The contents of this field is specific to each compression algorithm. The reciever MUST REJect any unknown compression negotiation configure requests. Default Specific to the compression algorithm negotiated. Dave Rand [Page 8] Internet Draft PPP Compression September 1993 A. Standard compression algorithm definitions The only compression algorithm that is available without license currently is the predictor algorithm, defined below. A.1. Predictor algorithm Predictor works by filling a guess table with values, based on the hash of the previous characters seen. Since we are either emitting the source data, or depending on the guess table, we add a flag bit for every byte of input, telling the decompressor if it should retrieve the byte from the compressed data stream, or the guess table. Blocking the input into groups of 8 characters means that we don't have to bit-insert the compressed output - a flag byte preceeds every 8 bytes of compressed data. Each bit of the flag byte corresponds to one byte of reconstructed data. Take the source file: 000000 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 000010 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 000020 4142 4142 4142 410a 4241 4241 4241 420a ABABABA.BABABAB. 000030 7878 7878 7878 780a xxxxxxx. Compressing the above data yields the following: 000000 6041 4141 4141 0a60 4141 4141 410a 6f41 `AAAAA.`AAAAA.oA 000010 0a6f 410a 4142 4142 4142 0a60 4241 4241 .oA.ABABAB.`BABA 000020 420a 6078 7878 7878 0a B.`xxxxx. Reading the above data says: flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A A A A A Guess table: A A flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A A A A A Guess table: A A flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A Guess table: A A A A A A flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: A Guess table: A A A A A A Dave Rand [Page 9] Internet Draft PPP Compression September 1993 flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: B A B A B Guess table: A A flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. Reconstructed data is: 0 1 2 3 4 5 6 7 File: B A B A B Guess table: A B flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6 Reconstructed data is: 0 1 2 3 4 5 6 7 File: x x x x x Guess table: x x And now, on to the source - note that it has been modified to work with a split block. If your data stream can't be split within a block (eg, compressing packets), then the code dealing with "final", and the memcpy are not required. You can detect this situation (or errors, for that matter) by observing that the flag byte indicates that more data is required from the compressed data stream, but you are out of data (len in decompress is <= 0). It *is* ok if len == 0, and flags indicate guess table usage. #include /* * pred.c -- Test program for Dave Rand's rendition of the * predictor algorithm * Updated by: Carsten Bormann * Original : Dave Rand / */ /* The following hash code is the heart of the algorithm: * It builds a sliding hash sum of the previous 3-and-a-bit characters * which will be used to index the guess table. * A better hash function would result in additional compression, * at the expense of time. */ #define HASH(x) Hash = (Hash << 4) ^ (x) unsigned short int Hash; unsigned char GuessTable[65536]; compress(source, dest, len) unsigned char *source, *dest; int len; { int i, bitmask; unsigned char *flagdest, flags, *orgdest; Dave Rand [Page 10] Internet Draft PPP Compression September 1993 orgdest = dest; while (len) { flagdest = dest++; flags = 0; /* All guess wrong initially */ for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { if (GuessTable[Hash] == *source) { flags |= bitmask; /* Guess was right - don't output */ } else { GuessTable[Hash] = *source; *dest++ = *source; /* Guess wrong, output char */ } HASH(*source++);len--; } *flagdest = flags; } return(dest - orgdest); } decompress(source, dest, lenp, final) unsigned char *source, *dest; int *lenp, final; { int i, bitmask; unsigned char flags, *orgdest; int len = *lenp; orgdest = dest; while (len >= 9) { flags = *source++; for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { if (flags & bitmask) { *dest = GuessTable[Hash]; /* Guess correct */ } else { GuessTable[Hash] = *source; /* Guess wrong */ *dest = *source++; /* Read from source */ len--; } HASH(*dest++); } len--; } while (final && len) { flags = *source++; len--; for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { if (flags & bitmask) { *dest = GuessTable[Hash]; /* Guess correct */ } else { if (!len) Dave Rand [Page 11] Internet Draft PPP Compression September 1993 break; /* we seem to be really done -- cabo */ GuessTable[Hash] = *source; /* Guess wrong */ *dest = *source++; /* Read from source */ len--; } HASH(*dest++); } } *lenp = len; return(dest - orgdest); } #include #define SIZ1 8192 char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; compress_file(f) FILE *f; { char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; int len1, len2; while (len1 = fread(bufp, 1, SIZ1, f)) { len2 = compress(bufp, bufc, len1); fwrite(bufc, 1, len2, stdout); } } decompress_file(f) FILE *f; { char bufp[SIZ1+9]; char bufc[SIZ1*9+9]; int len1, len2, len3; while (len3 = fread(bufp+len1, 1, SIZ1, f)) { len1 += len3; len3 = len1; len2 = decompress(bufp, bufc, &len1, 0); fwrite(bufc, 1, len2, stdout); memcpy(bufp, bufp+len3-len1, len1); } len2 = decompress(bufp, bufc, &len1, 1); fwrite(bufc, 1, len2, stdout); } main(ac, av) char** av; { char **p = av+1; int dflag = 0; for (; --ac > 0; p++) { Dave Rand [Page 12] Internet Draft PPP Compression September 1993 if (!strcmp(*p, "-d")) dflag = 1; else if (!strcmp(*p, "-")) (dflag?decompress_file:compress_file)(stdin); else { FILE *f = fopen(*p, "r"); if (!f) { perror(*p); exit(1); } (dflag?decompress_file:compress_file)(f); fclose(f); } } } A.2. Encapsultation for Predictor type 1 The correct encapsulation for type 1 compression is the protocol type, compressed data, and uncompressed CRC-16 of the original, uncompressed data packet. 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CCP Protocol Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed data... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC - 16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ It is not required that the CRC-16 land on an even word boundary - the compressed data may be of any length. If during the decode procedure, the CRC-16 does not match the decoded frame, it means that the compress or decompress process has become desyncronized. This will happen as a result of a frame being lost in transit if LAPB is not used. In this case, a new configure-request must be sent, and the CCP will drop out of the open state. Upon receipt of the configure-ack, the predictor tables are cleared to zero, and compression can be resumed without data loss. A.3. Encapsultation for Predictor type 2 The correct encapsulation for type 2 compression is the protocol type, followed by the data stream. Within the data stream is the current frame length (compressed), compressed data, and uncompressed CRC-16. The data stream may be broken at any convenient place for encapsulation purposes. With type Dave Rand [Page 13] Internet Draft PPP Compression September 1993 2 encapsulation, LAPB is almost essential for correct delivery. 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CCP Protocol Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed length (2 octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed data (variable) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC-16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed length (2 octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... It is not required that the CRC-16 land on an even word boundary - the compressed data may be of any length. If during the decode procedure, the CRC-16 does not match the decoded frame, it means that the compress or decompress process has become desyncronized. This will happen as a result of a frame being lost in transit if LAPB is not used. In this case, a new configure-request must be sent, and the CCP will drop out of the open state. Upon receipt of the configure-ack, the predictor tables are cleared to zero, and compression can be resumed without data loss. B. CCP Recommended Options The following Configurations Options are recommended: IP-Compression-Protocol -- with at least 4 slots, usually 16 slots. IP-Address -- only on dial-up lines. Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W. A., "The Point-to-Point Protocol", RFC in progress. Dave Rand [Page 14] Internet Draft PPP Compression September 1993 [2] Postel, J., "Internet Protocol", RFC 791, USC/Information Sciences Institute, September 1981. [3] Jacobson, V., "Compressing TCP/IP Headers", RFC 1144, January 1990. [4] Postel, J., "The TCP Maximum Segment Size Option and Related Topics", RFC 879, USC/Information Sciences Institute, November 1983. [5] Mogul, J.C., Deering, S.E., "Path MTU Discovery", RFC 1191, November 1990. [6] Reynolds, J., Postel,J., "Assigned Numbers", RFC 1060, USC/Information Sciences Institute, March 1990. [7] Perkins, D., Hobby, R., "Point-to-Point Protocol (PPP) initial configuration options", RFC 1172, August 1990. Acknowledgments Some of the text in this document is taken from RFCs 1171 & 1172, by Drew Perkins of Carnegie Mellon University, and by Russ Hobby of the University of California at Davis. Information leading to the expanded IP-Compression option provided by Van Jacobson at SIGCOMM '90. Bill Simpson helped with the document formatting. Chair's Address The working group can be contacted via the current chair: Fred Baker Advanced Computer Communications 315 Bollay Drive Santa Barbara, California 93117 (805) 685 4455 EMail: fbaker@acc.com Dave Rand [Page 15] Internet Draft PPP Compression September 1993 Author's Address Questions about this memo can also be directed to: Dave Rand 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand [Page 16] Internet Draft PPP Compression September 1993 Table of Contents 1. Introduction .......................................... 1 2. A PPP Control Protocol (NCP) for Compression .......... 2 2.1 Sending Compressed Datagrams .................... 2 3. CCP Configuration Options ............................. 4 3.1 Defined Compression Algorithms .................. 5 3.2 Proprietary Compression Algorithm Support ....... 6 3.3 Algorithm-specific negotiations ................. 8 APPENDICES ................................................ 9 A. Standard compression algorithm definitions ......... 9 A.1 Predictor algorithm ....................... 9 A.2 Encapsultation for Predictor type 1 ....... 13 A.3 Encapsultation for Predictor type 2 ....... 13 B. CCP Recommended Options ......................... 14 SECURITY CONSIDERATIONS ................................ 14 REFERENCES ................................................ 14 ACKNOWLEDGEMENTS ............................................. 15 CHAIR'S ADDRESS .............................................. 15 AUTHOR'S ADDRESS ............................................. 15 Dave Rand [Page ii] From owner-ppp-comp Fri Sep 3 06:57:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYbda-0000GGa; Fri, 3 Sep 93 06:57 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 09:54:28 -0400 (EDT) Message-ID: <9309031354.AA01426@donut.gandalf.ca> References: <<9309022120.AA23778@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > 2. A PPP Control Protocol (NCP) for Compression > > The Compression Control Protocol (CCP) is responsible for > configuring, enabling, and disabling data compression algorithms on > both ends of the point-to-point link. It is also used to signal a > failure of the compression/decompression mechanism in a reliable > manner. CCP uses the same packet exchange machanism as the Link > Control Protocol (LCP). CCP packets may not be exchanged until PPP > has reached the Network-Layer Protocol phase. CCP packets received > before this phase is reached should be silently discarded. The CCP packets SHOULD NOT be sent prior to negotiation of multilink negotiation. > > One or more compressed packets are encapsulated in the Information > > The maximum length of a compressed packet transmitted over a PPP link > is the same as the maximum length of the Information field of a PPP > data link layer frame. Larger datagrams (presumably the result of > the compression algorithm increasing the size of the message in a > pathological case) may be sent uncompressed, using its standard form, ^^^^^^^^^^^^ Hardly! First, it's not a pathological case. It happens any time pre-compressed data or when a change in source entropy is encountered. Second, any packet that was compressed MUST be sent with the compression header, and it is the responsibility of the compression algorithm to provide the transparent data feature. Note, this feature entails having a hash table or trie structure in the decoder for LZW or LZ77 style encoders. > or may be fragmented into multiple datagrams, if the compression > algorithm supports it. Fragmentation should be left to the Sklowers multilink. No sense having it in more places! > > The most up-to-date values of the CCP Option Type field are specified in > the most recent "Assigned Numbers" RFC [6]. Current values are assigned > as follows: > > Compression Algorithm Name > Type > > 1 Predictor Compression Algorithm > 2 Predictor Compression with multi-frame per packet > OUI Proprietary compression Why is Novell Predictor negotiation different than vendor specific? We have 2 algorithms. Why 2 OUI's required? Might I suggest everyone uses OUI + Algorithm type to specify the method. > #define HASH(x) Hash = (Hash << 4) ^ (x) Didn't like the 0.5% to 1% improvement by using an add instruction? Finally, if your algorithm is to be standardized, there should be a clause from Novell indemnifying users of Predictor. I personally will not include it into a product until such a notice is included. I have problems seeing the difference between this algorithm and U.S. patent number 4,612,532 (Telebyte, 1986) with a fixed followset of 1. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Fri Sep 3 07:23:34 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYc2q-0000N3a; Fri, 3 Sep 93 07:23 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 07:23:13 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: compression control memo" on Sep 3, 9:54, Dave Carr writes:] > > the compression algorithm increasing the size of the message in a > > pathological case) may be sent uncompressed, using its standard form, > ^^^^^^^^^^^^ > > Hardly! First, it's not a pathological case. It happens any time > pre-compressed data or when a change in source entropy is encountered. Whatever. I'll remove the word pathological. > Second, any packet that was compressed MUST be sent with the compression > header, and it is the responsibility of the compression algorithm to > provide the transparent data feature. Note, this feature entails having > a hash table or trie structure in the decoder for LZW or LZ77 style > encoders. This is not the case. If an algorithm such as (for example) RLE is used, you can back out of the compression at no cost, in which case you can send it with the regular protocol ID. Specifically, you may get compressed and uncompressed packets on the wire, at any time. > > > or may be fragmented into multiple datagrams, if the compression > > algorithm supports it. > > Fragmentation should be left to the Sklowers multilink. No sense having > it in more places! I'll change the word fragmentation. What I really meant was the compression algorithm is free to split packets up on the wire how it wants/needs to. If that means that one packet spans several frames on the wire, or several packets are contained in one frame, that is OK. > > Why is Novell Predictor negotiation different than vendor specific? > We have 2 algorithms. Why 2 OUI's required? There exist two classes of compression algorithms - Standard, and Proprietary. Standard algorithms are those that are fully specified (even if that means paying a license fee to someone), and anyone can implement them and get a compatible version. It is intended that implementing other common compression algorithms (such as STAC and HP PPC) will have fully disclosed framing formats, and numbers assigned. Proprietary algorithms can do exactly what they want, when they want. For as long as they want. > Didn't like the 0.5% to 1% improvement by using an add instruction? I like it, but it doesn't happen in all cases. I still need to qualify it more. I have a couple of other changes to the algorithm as well, and these will show up as new ID numbers in the future. > Finally, if your algorithm is to be standardized, there should be a clause > from Novell indemnifying users of Predictor. I personally will not include > it into a product until such a notice is included. Feel free not to include it. Novell will indemnify users of the predictor algorithm, up to the full value paid to Novell for the use of the algorithm - in this case, up to a total liability of $0.00. What I will add in the document as a brief history of the algorithm, and a statement that (as with all software) the implementor must research and develop their own patent infringment policy. In my opinion, software patents should be made invalid. > I have problems seeing > the difference between this algorithm and U.S. patent number 4,612,532 > (Telebyte, 1986) with a fixed followset of 1. I don't think it conflicts, and neither do our lawyers. I will ask specifically for their reasoning on this patent, as my opinion doesn't count at all. -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Sep 3 08:01:34 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYcdD-0000Z8a; Fri, 3 Sep 93 08:00 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr (Dave Rand) To: ppp-comp@bungi.com Subject: mailing list Date: Fri, 3 Sep 93 08:00 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Many people have asked me for a list of those people currently on this mailing list (including some at Novell). There are two reasons that no one except for me and daver.bungi.com know who is on this list: 1. I respect the privacy of the individuals on this list. 2. Some companies may not want general knowledge of their work in compression, at this time. If you disagree with this policy, and want your name and email address to be known to everyone on this list, you need only send a simple message to ppp-comp@bungi.com. All comments made to the list are archived, and available on sgi.com:other/ppp-comp. grep From: * | uniq will give you a complete mailing list of those people that wish to be known. Thanks for your understanding. From owner-ppp-comp Fri Sep 3 10:28:55 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYewB-0000epa; Fri, 3 Sep 93 10:28 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 13:26:55 -0400 (EDT) Message-ID: <9309031726.AA01528@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > This is not the case. If an algorithm such as (for example) RLE is used, > you can back out of the compression at no cost, in which case you can > send it with the regular protocol ID. Specifically, you may get compressed > and uncompressed packets on the wire, at any time. Just so long as the wording is to this effect. > > > from Novell indemnifying users of Predictor. I personally will not include > > it into a product until such a notice is included. > > Feel free not to include it. Novell will indemnify users of the predictor > algorithm, up to the full value paid to Novell for the use of the algorithm - > in this case, up to a total liability of $0.00. What I will add in the You have maintained the patent free-ness of the algorithm as one of the principal features (along with speed) of Predictor. There also has been some speculation as to other algorithms proposed for standardization are *not* patent free. If Novell is so sure of the patent issues, they should not have any problem indemnifying Predictor. Otherwise, classify it along with my FZA as "algorithms that the authors are pretty confident are patent free". Without indemnification, you're algorithm cannot be considered as patent-free to any implementor! --- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Fri Sep 3 11:45:44 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYg8S-0000XUa; Fri, 3 Sep 93 11:45 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 11:45:09 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk (why are we re-hashing this?) [In the message entitled "Re: compression control memo" on Sep 3, 13:26, Dave Carr writes:] > You have maintained the patent free-ness of the algorithm as one of the > principal features (along with speed) of Predictor. There also has been > some speculation as to other algorithms proposed for standardization are > *not* patent free. If Novell is so sure of the patent issues, they should > not have any problem indemnifying Predictor. Otherwise, classify it > along with my FZA as "algorithms that the authors are pretty confident are > patent free". Without indemnification, you're algorithm cannot be considered > as patent-free to any implementor! I have maintained that it is patent free, and unpatentable due to prior art. The lawyers agree with me, even though my opinion doesn't count. Each company must decide for themselves what is patentable, and what is not - recall the XOR-cursor patent. The advantages of predictor, as discussed in Amsterdam, are: 1. It appears to be patent free. 2. It is very fast. 3. It is simple to implement. 4. It is free. The "free", "simple" and "fast", not "patent-free" were the critical issues for consideration as a standard. "patent-free" was a bonus. I recall Mr. Simpson saying words to the effect of "...if there is a license fee for its use, then it cannot be considered for a standard. People like me just can't afford to be paying royalties for use in a PPP product." (Please correct me if I'm wrong, Bill.) (I'm going to shout now) I'M NOT ASKING *ANYONE* TO IMPLEMENT PREDICTOR. If you don't like it, don't implement it. I'll 'standardize' ANY algorithm in the memo, so long as it is available to everyone at the same price(s), and you fully disclose the framing technique. I'm not forcing ANYONE to use OUI-based negotiation. I have 255 different 'standard' compressor ID's - I'm quite happy to use them all. It doesn't have to be free to be a 'standard', and it doesn't have to be patent free to be a 'standard'. It just has to be documented. Bonus points for disclosing the compression mechanism. The memo SPECIFICALLY allows compression-capable PPP's to negotiate to no compression - in case both ends don't support any types in common. Not everyone WILL (or CAN) implement predictor, due to memory consumption. (I'm done shouting now) Sigh. Now, I just went through all of the back issues, and I think I found what you are talking about (setting the WayBack machine to May 26, 1993, we see Dave Rand and Dave Carr deep in discussion) ------------------------------------------------------------------------ > From Dave Carr: > > Dave, I'd wish you'd tell me the patents that I don't know about. You seem > to imply that FZA has patent problems, and I don't agree. I don't want the > rest of the list to become biased away from LZ77. It appears to have the > best chance of any algorithm to be free of patent issues. I'm not implying anything. I'm researching it, and my best current information tells me that all LZ-related algorithms are covered by one or more patents. The validity of the patents is questionable, of course. I'm not a lawyer, and I don't pretend to understand which algorithms are or are not covered. Besides, the issue is not going to depend on you and I agreeing FZA isn't covered by patents, it is going to depend on the lawyers agreeing that it isn't covered. Arithmetic compression also appears to be covered by IBM patents. I know that you said that you have worked around at least the STAC patent. Personally, I *LIKE* LZ77. It gets GREAT compression. I'm not biasing anything. I've tried to present all algorithms that I know about, so that everyone has the opportunity to review the data and come to their own conclusions. Part of that data involves patents. Even though I have received assurance from the Info-ZIP authors that I can use the algorithm, I would still run it through our lawyers before putting it in a product. I'm also still waiting for your non-disclosure so that I can try your algorithm. Even if it doesn't make it into the standard, I'm still interested in it as a potential product. I'm also not limiting my search to the algorithms that I know about. I'm *ACTIVELY* looking at different algorithms, and different ways of doing compression. I've even talked to the WEB^H^H^HTranSCend folks, who claim "amazing, simply amazing" compression rates. Yes, these are commercial products. No, it isn't a factor in the evaluation. We must look at all alternatives. We can decide to eliminate candidates after looking at them, but I don't think that we should ignore anyone. The LZW algorithm in the compress algorithm is patented, but no one is sure if IBM/Unisys will come after you if you use it. USL has apparently paid a license fee to Unisys for the right to include compress in the USL UNIX release. I'm checking on that now. Predictor, to the best of my knowledge, is not patented, and cannot be patented due to prior art. I'll know more when the patent search is complete. This will be in 5 weeks or less. I submitted the request about 2 weeks ago to the Novell patent lawyer, who of course is named (in the tradition of all people involved in compression) Dave Black. To which you later reply: > Let's stop beating around the bush. Quote patent numbers or refrain from > bashing LZ77. I think you're wrong. Plain and simple. I am not alone. > I would hardly think that all the archivers are wrong. Great! I have quoted patent numbers in my document. I have a stack of them on my desk. I think that it is covered - but it doesn't matter *AT ALL* what I think. Period. It *ONLY* matters what the lawyers think is covered. AND I AM NOT BASHING ANYTHING. Dave - if you want to take this any further, take it to private email. ------------------------------------------------------------------------- (returning to the present...) Novell as a company is very sure of the patent status of predictor. Novell as a company gets sued a *LOT* over stupid patent issues, because it is a high profile company (read: easy target). Novell as a company spends a *LOT* of money every year defending itself from stupid patent issues - even ones that OBVIOUSLY have no basis in reality. Now you want Novell to indemnify everyone that uses an algorithm that we published, and charged no money for? Why? If you used a binary of Novell's, there is perhaps a basis for this. But let's say (for example) that someone has a patent pending for the idea of a base-plus-offset lookup in a table, using a fixed offset. Depending on your compiler, you might infringe this patent on a RISC processor, and not on a CISC. Is Novell supposed to cover you here, too? What are the limits? Do you expect the ITU (nee CCITT) to indemnify you because you built a V.42bis-compatible compressor from their documents, and didn't pay Unisys? If Novell charges you money for a product, you have a reasonable expectation to be indemnified. Just as when Novell purchases a license from STAC, we have some assurance that STAC owns the technology - and part of that license fee will go toward covering the legal fees that will be incurred by STAC defending itself against patent claims. Summary: Gandalf wants to charge money for FZA, but is unwilling to indemnify the users of that product (as of your last statement). HP wants to charge money for PPC, and is willing to indemnify the users of that product (as of the Amsterdam meeting). STAC wants to charge money for its compressor, and is willing to indemnify the users of that product. Transcend wants to charge money for its compressor. I don't know if they are willing to indemnify the users of that product. Novell doesn't want to charge any money for predictor, and is not willing indemnify the users of predictor (it isn't a product). Put it in your PPP, or not. Negotiate it, or not. You won't hurt my feelings either way. I'm just happy to have been able to contribute an algorithm and implementation, for consideration. I hope that the rest of the mailing list has enjoyed the work that Novell has put in to getting compression standardized (or standardizing, as the case may be). -- Dave Rand {pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Sep 3 13:26:40 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYhi7-0000CWa; Fri, 3 Sep 93 13:26 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Fri, 3 Sep 93 16:02:10 EDT Message-ID: <1045.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: fbaker@acc.com (Fred Baker) > The problem with the chips is that they have rather inflexible mode > settings (when it's in transparent mode, it doesn't LAPB, when it's in LAPB > mode, it pitches everything else...) and changing the mode is an onerous > task. > Fred, does this mean that the chip CANNOT indicate that an illegal LAPB but properly checksummed frame has arrived? > As a result, I think the above might compound the problem. If the guy > coming up were to send a LAPB DM or DISC (once from each address) that > would force an immediate LAPB Down event, which would signal me to go back > to first principles. I think I'd rather see a guy who is LAPB-capable (and > therefore capable of getting into this box) know to send a DTE-DM and a > DCE-DM just before the first retransmission of his LCP CONFIGURE REQUEST. > That could solve the RE-negotiate problem, but won't help the "system crashes and restarts with no prior knowlege" problem. Based on your answer, I would like to abandon the LAPB negotiation for going from UI to LAPB. Instead, we should adopt the technique used in PPP/ISDN, by detecting that the LCP ConfigReq is _framed_ in either LAPB or UI, and conduct all negotiations using whichever framing is detected. Eliminate mode-switching except after the first frame detected. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Fri Sep 3 14:14:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYiS0-0000i2a; Fri, 3 Sep 93 14:13 PDT Sender: owner-ppp-comp X-Path: lassen.wpd.sgi.com!ian From: ian@lassen.wpd.sgi.com (Ian Clements) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 93 14:13:32 -0700 Message-ID: <9309032113.AA14032@lassen.wpd.sgi.com> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk In mail.ietf.ppp.comp you write: >{pyramid|mips|bct|vsi1}!daver!dlr Internet: dlr@daver.bungi.com You should take the mips out of your path. You could replace it w/sgi. -- -- Ian Clements, | ian@sgi.com, 415/390-3410 | "It's more excitement than decent people need" From owner-ppp-comp Fri Sep 3 14:55:44 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYj6S-0000hMa; Fri, 3 Sep 93 14:55 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 17:53:43 -0400 (EDT) Message-ID: <9309032153.AA01610@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Gandalf wants to charge money for FZA, but is unwilling to indemnify the > users of that product (as of your last statement). Wrong! I never said that we would not indemnify the buyer. Quite the contrary in fact. > HP wants to charge money for PPC, and is willing to indemnify the > users of that product (as of the Amsterdam meeting). Yes, and I'm still waiting for info. Am I the only one who Dave Langley hasn't responded to? (Yes, I have phoned and e-mailed). > STAC wants to charge money for its compressor, and is willing to > indemnify the users of that product. Obvious. > > Transcend wants to charge money for its compressor. I don't know > if they are willing to indemnify the users of that product. Seems to be a trend here. People are buying indemnification with the algorithm. Given the costs of fighting trivial patent infringement claims, the license costs of these algorithms are peanuts. Personally, I'd rather have protection from these fights as the PRIMARY goal of the algorithm, with speed, memory, and compression ratio following close behind. > > Put it in your PPP, or not. Negotiate it, or not. You won't hurt my > feelings either way. I'm just happy to have been able to contribute > an algorithm and implementation, for consideration. I hope that the > rest of the mailing list has enjoyed the work that Novell has put > in to getting compression standardized (or standardizing, as the > case may be). Don't get me wrong. We all appreciate your effort Dave. And Novell's. Myself included! But understand this. If I have to pay $20K to some patent holder, or spend $20K fighting it, it's no different than paying $20K for the algorithm from STAC, Gandalf, Transend, or HP, if the seller is providing the indemnification. So much for *free* algorithms. I believe the proper term for this is *false economy*. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Fri Sep 3 15:25:11 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oYjYb-0000DNa; Fri, 3 Sep 93 15:24 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Fri, 3 Sep 1993 15:21:33 PDT Message-ID: <9309032221.AA14586@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Sep 3, 17:53, Dave Carr wrote: } Subject: Re: compression control memo } > Gandalf wants to charge money for FZA, but is unwilling to indemnify the } > users of that product (as of your last statement). } } Wrong! I never said that we would not indemnify the buyer. Quite the } contrary in fact. I stand corrected. I looked in the back issues, and could not find a statement either way. I believe it may have been my faulty memory. } Personally, I'd rather have protection from these fights as the } PRIMARY goal of the algorithm, with speed, memory, and compression } ratio following close behind. Dave, one algorithm has been proposed. It has been accepted by the majority of people that were in Amsterdam, as one algorithm. I have specified it. I have released code for it. It is *NOT* required to implement ANY algorithm. The one thing we figured out in Amsterdam was that one size does not fit all, unless we could get the WonderAlgorithm(tm) that does 16:1, takes no memory, no cpu, and is free. We can have up to 255 different ones. Each one will have its own advantages and disadvantages. If you want FZA to be one of the choices, release pricing information on FZA (you have said as low as $5,000, and as high as $40,000). Specify the framing, and I'll include it. If you don't want to do that, leave it as an OUI, do private licensing, and you are still set. But please stop arguing! -- From owner-ppp-comp Sun Sep 5 22:10:46 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oZYop-00006ya; Sun, 5 Sep 93 22:08 PDT Sender: owner-ppp-comp X-Path: cisco.com!misko From: Bill Miskovetz To: ppp-comp@bungi.com Subject: Re: FYI Date: Sun, 5 Sep 93 22:08:25 PDT Message-ID: <199309060508.AA16958@regal.cisco.com> References: <<9309021640.AA15779@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I talked to them at interop and got their card, that's about it for me. > > Transcend has mailed out some advertising material recently. A copy showed > up in my mailbox today. They claim a GUARANTEED 4:1 compression ratio, > and 56K/64K or T1/E1 data rates, with "higher compression on shorter packets, > and on T1/E1". They also claim "over a year of successful field trials > at a major Fortune 5 company" (they later claim a Fortune 500 company). > Their phone number is +1 216-835-4882. > > If *ANYONE* has any experience with this compression technology, please > post or private email me. If they can truly guarantee a 4:1 compression > ratio, on any network data, I would like to buy many of these devices. > Thus far, I have been unable to extract any hardware or software > out of Transcend. > From owner-ppp-comp Mon Sep 6 21:16:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oZuSz-0000DLa; Mon, 6 Sep 93 21:15 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: compression control memo Date: Mon, 6 Sep 93 19:47:04 EDT Message-ID: <1053.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I have a number of concerns about the memo. 1) I thought that we were going to use 0xfd for the PPP Protocol number. I can't find that anywhere. 2) I thought that we were going to assign PPP Protocol high numbers to each compression scheme, so that even when not the first choice, a second compression protocol could be used. 3) I would prefer that the Predictor algorithm be specified in a separate document (informational). It should have more configuration information of its own, such as table size. It needs a lot more explanatory text on why it works, its freedom from patent problems, etc. 4) There are a lot of left over pieces from the documents you grabbed the skeleton from. And a number of indentation and formatting problems. And some inconsistencies in the sections on negotiation. (I would be happy to fix that up for you.) 5) The renegotiation when out of sync should be a MUST not a may. 6) We already have a compound frame technique, let's use that (not the multiples used in the #2). Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Sep 7 11:56:25 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oa8DA-0000Bka; Tue, 7 Sep 93 11:56 PDT Sender: owner-ppp-comp X-Path: opal.acc.com!art From: art@opal.acc.com (Art Berggreen) To: ppp-comp@bungi.com Subject: Comments on CCP Date: Tue, 7 Sep 93 09:55:55 PDT Message-ID: <9309071655.AA22438@opal.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Here are my initial comments regarding the Compression Contro Protocol (CCP). Should the CCP state become opened before "normal" NCPs are allowed to start? If a compression algorithm requires LAPB, must the LAPB negotiation complete before "normal" NCPs can start? Why are "standard" and "proprietary" compression algorithms encoded differently in the Config-req? Why are multiple algorithms listed for "standard" but only a single "proprietary" algorithm (one OUI at a time) supported? I'd much rather use a common encoding format and have a single list. Say, maybe an OUI followed by one octet under that OUI. We could pick a distinquished OUI (maybe 00-00-00) for the "standard" algorithms and allow vendors to support multiple "proprietary" ones. This allows all of the parsing of the option to be more uniform, and allows the vendor to list a mix of preferences using both "standard" and "proprietary" in his desired preference order. It's not unlikely that a vendor will try his list of "proprietary" algorithms before accepting one of the "standard" algorithms. I'd like to see a defined way to tag the algorithm specific negotiation option to a specific algorithm. This is because more than one listed algorithm may carry algorithm specific negotiation. Either this, or state that the algorithm specific information negoatiation cannot be initiated until a single algorithm has been selected. But this would draw out negotation and make it more complex. Also which algorithm you select may be influenced by what algorithm specific negotiation parameters the peers is willing to use. Art From owner-ppp-comp Tue Sep 7 12:01:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oa8IB-00008Na; Tue, 7 Sep 93 12:01 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Tue, 7 Sep 1993 10:06:55 -0800 Message-ID: <9309071707.AB23149@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >> The problem with the chips is that they have rather inflexible mode >> settings (when it's in transparent mode, it doesn't LAPB, when it's in LAPB >> mode, it pitches everything else...) and changing the mode is an onerous >> task. >> >Fred, does this mean that the chip CANNOT indicate that an illegal LAPB >but properly checksummed frame has arrived? Yes and no. If it's to my address or my peer's address, LAPB requires that this result in a FRMR and a transition to NDM. If it's to another address, HDLC assumes that it is to some other station. Yes, LAPB is for point to point procedures, but HDLC has a wider view. The chips, I believe, would not fail the link on receipt of that data. >> As a result, I think the above might compound the problem. If the guy >> coming up were to send a LAPB DM or DISC (once from each address) that >> would force an immediate LAPB Down event, which would signal me to go back >> to first principles. I think I'd rather see a guy who is LAPB-capable (and >> therefore capable of getting into this box) know to send a DTE-DM and a >> DCE-DM just before the first retransmission of his LCP CONFIGURE REQUEST. >> >That could solve the RE-negotiate problem, but won't help the "system >crashes and restarts with no prior knowlege" problem. Not sure of that; sending the DM is an optimization; the magic timers resolve it if nothing else does. >Based on your answer, I would like to abandon the LAPB negotiation for >going from UI to LAPB. > >Instead, we should adopt the technique used in PPP/ISDN, by detecting >that the LCP ConfigReq is _framed_ in either LAPB or UI, and conduct all >negotiations using whichever framing is detected. Eliminate >mode-switching except after the first frame detected. Let me see if I understand what you're saying. It *sounds* like you're saying "send the LCP configure as a numbered I frame", which is illegal in NDM, LAPB's "down" state. I trust that's not your proposal. If I want to run UI mode, I start out in the chip's transparent mode. If another system wants to run LAPB mode, it will hear my UI and switch to UI. If I want to run LAPB mode, I start out in the chip's transparent mode. Approach (1), I send SABM(E) looking for a UA response. When I get the UA, we are in ABM and I can send the LCP configure - except that if I'm using a chip, I must now configure IT, which will result in an extra SABM(E)/UA. Approach (2), I send an XID (negotiating use of LAPB, address, window, etc) looking for an XID response. When I get it, I now need to send SABM(E), which may be done by chip initialization or software process initialization. In either case, if I receive a broadcast UI LCP Configure, I must abandon LAPB and either refuse or go into UI mode. In either case, once the mode is selected, you would suggest that we just stay in that mode for the lifetime of the connection. There is a race in this (not an argument against, but a fact to keep in mind), using either approach. Since LAPB requires the use of opposing addresses (unlike Q.921 or Q.922, which have a C/R flag), there is some possibility that you and I both tried for the same address simultaneously and wound up accepting the other guy's negotiation. The only way out that *I* know of is to not respond to the other guy's negotiation while my own is outstanding, and have a random interfval between attempts. Am I correct in my interpretation? ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Tue Sep 7 13:38:26 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oa9nv-0000Dba; Tue, 7 Sep 93 13:38 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Tue, 7 Sep 1993 16:36:31 -0400 (EDT) Message-ID: <9309072036.AA02263@donut.gandalf.ca> References: <<9309071707.AB23149@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > If I want to run LAPB mode, I start out in the chip's transparent mode. > Approach (1), I send SABM(E) looking for a UA response. When I get the UA, > we are in ABM and I can send the LCP configure - except that if I'm using a > chip, I must now configure IT, which will result in an extra SABM(E)/UA. Not a big deal. Resequence and go. > Approach (2), I send an XID (negotiating use of LAPB, address, window, etc) > looking for an XID response. When I get it, I now need to send SABM(E), > which may be done by chip initialization or software process > initialization. In either case, if I receive a broadcast UI LCP Configure, > I must abandon LAPB and either refuse or go into UI mode. In either case, > once the mode is selected, you would suggest that we just stay in that mode > for the lifetime of the connection. I like this better! More or less what we do today. > > There is a race in this (not an argument against, but a fact to keep in > mind), using either approach. Since LAPB requires the use of opposing > addresses (unlike Q.921 or Q.922, which have a C/R flag), there is some > possibility that you and I both tried for the same address simultaneously > and wound up accepting the other guy's negotiation. The only way out that > *I* know of is to not respond to the other guy's negotiation while my own > is outstanding, and have a random interfval between attempts. Will your controller accept an XID (command or response) while in the information transfer state? Does it pass both through? Or will you simply let the LAPB timers go off and return to transparent mode? The XID is nice because it can include the remote ends ID, magic number, etc. Magic number can be used to resolve 01/03/07/0f address assignments. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Tue Sep 7 13:47:37 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oa9wn-0000Toa; Tue, 7 Sep 93 13:47 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Comments on CCP Date: Tue, 7 Sep 1993 13:44:44 PDT Message-ID: <9309072044.AA13184@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Sep 7, 9:55, Art Berggreen wrote: } } If a compression algorithm requires LAPB, must the LAPB negotiation complete } before "normal" NCPs can start? No, but the LAPB negotiation should be complete before the CCP comes up. Depending on the algorithm, the should could be a must. If the algorithm doesn't do error checking (a mistake, IMHO), LAPB must be UP prior to bringing up the CCP. } Why are "standard" and "proprietary" compression algorithms encoded differently } in the Config-req? } Because the standard ones are fully specified. The intent is for the standard types be easy to implement, and easy to get right. } Why are multiple algorithms listed for "standard" but } only a single "proprietary" algorithm (one OUI at a time) supported? Unlimited numbers of proprietary algorithms are supported. Each OUI may be followed with a list, just like the standard list, of 'supported' algorithms. Whatever. That's why it is proprietary. You can think of the 'standard' list as having a compressed OUI of 00-00-00 in front of it - compressed to 0 bytes in this case :-) (more implied than compressed, come to think of it). I don't want to limit any manufacturer of a compression algorithm to a single byte algorithm specification though - if he was clever, he could encode the parameter negotiation set in the space he has after the OUI, or something. I specifically DON'T want to specify the OUI-space, other than to say it is there. } Either this, or } state that the algorithm specific information negoatiation cannot be } initiated until a single algorithm has been selected. But this would } draw out negotation and make it more complex. Also which algorithm } you select may be influenced by what algorithm specific negotiation } parameters the peers is willing to use. While I agree with the last sentence, you can always re-negotiate the compression type if the compression options suggest that the algorithm chosen is a bad one. I do state that the algorithm specific information negotiation cannot proceed until an algorithm is specified (if I don't, be sure that it will be in the next rev). I looked at making a common set of parameters that all compression algorithms could use (dictionary size, maximum code size, maximum run size, etc, etc), but got totally bogged down in the details. With this in mind, unless you are willing to offer the defaults for your implementation in the negotiation packets, prior to chosing an algorithm (which would involve the transmission of N packets, where N is the number of supported compression algorithms), I suggest that negotiation AFTER, and re-select the algorithm in the event of a failure in negotiation, is the appropriate mechanism. In our implementation, we offer up to 3 different compression algorithms. Since one of them takes a LOT of memory, we may find that there is not room to allocate the 1.2 meg of memory required, once the negotiation is complete (even if there WAS memory available at the start of the negotiation). In this case, we close down the CCP, and try again, this time without the space-hungry algorithm in our list. Works, and without a significant penalty. -- From owner-ppp-comp Tue Sep 7 14:39:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaAlT-0000Tqa; Tue, 7 Sep 93 14:39 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Tue, 7 Sep 93 16:51:23 EDT Message-ID: <1065.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > >Fred, does this mean that the chip CANNOT indicate that an illegal LAPB > >but properly checksummed frame has arrived? > > Yes and no. If it's to my address or my peer's address, LAPB requires that > this result in a FRMR and a transition to NDM. If it's to another address, > HDLC assumes that it is to some other station. Yes, LAPB is for point to > point procedures, but HDLC has a wider view. The chips, I believe, would > not fail the link on receipt of that data. > OK. Then this means that for your chip 0xff is not the "all-stations" address? (I think I'll call you, since this one exchange a day is wearing.) Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Sep 7 14:45:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaAqb-0000UAa; Tue, 7 Sep 93 14:45 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: More CCP comments Date: Tue, 7 Sep 93 14:38:44 TZ Message-ID: <9309072143.AA17419@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Why is the maximum length of a compressed packet transmitted over the PPP link the same as the max length of the Information field? Compression, as noted, can expand the frame. For some compression schemes, it is diffifcult to "back-out" once compression on a packet is attempted so sending the packet uncompressed is not a viable option. Thus, the only other option is to fragment the packet. This seems like an unnecessary waste of time to me. It seems to me like the max length of a compressed packet should be based on the compression algorithm being used. If an algorithm is used that has a worst case expansion of 50% then any frame over 150% of the max length of the information field is invalid. Why can't this be done instead? --Thomas From owner-ppp-comp Tue Sep 7 15:08:46 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaBDB-0000Tfa; Tue, 7 Sep 93 15:08 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Tue, 7 Sep 1993 15:05:39 PDT Message-ID: <9309072205.AA14969@va.SJF.Novell.COM> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Sep 7, 14:38, Thomas Dimitri wrote: } Subject: More CCP comments } Why is the maximum length of a compressed packet transmitted over } the PPP link the same as the max length of the Information field? Because it is the negotiated paramter of the maximum transmission size. It is what the other end is prepared to receive. If, for example, you blow a 1.5K packet up to 2K, and the far size only has a 1.5K buffer... If you want larger frames on the wire, negotiate for it. Don't assume. -- From owner-ppp-comp Wed Sep 8 06:56:35 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaQ09-0000Oaa; Wed, 8 Sep 93 06:56 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Wed, 8 Sep 1993 09:54:12 -0400 (EDT) Message-ID: <9309081354.AA02643@donut.gandalf.ca> References: <<9309072205.AA14969@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > On Sep 7, 14:38, Thomas Dimitri wrote: > } Subject: More CCP comments > } Why is the maximum length of a compressed packet transmitted over > } the PPP link the same as the max length of the Information field? > > Because it is the negotiated paramter of the maximum transmission size. > It is what the other end is prepared to receive. If, for example, you > blow a 1.5K packet up to 2K, and the far size only has a 1.5K buffer... > > If you want larger frames on the wire, negotiate for it. Don't assume. I agree with your logic, but I feel that the splitting of the frame down to the MTU should NOT be buried in the compression layer. We have the fragmentation protocol defined (Sklower multilink) which can take care of fragmenting down to the MTU (or beyond). If the compression is building packets to the MTU, which one does it use since there may be several links below the compression running in a multilink, each with a different MTU. There is an MRRU defined by Sklower, which can easily handle larger frames. If this means that compression requires Sklower multilink to run, so be it. Not every compression protocol will need it. Some algorithms require LAP/B to run. This additional requirement is consistent with the LAPB requirement. I see where you are coming from. Your moving the fragmentation and what I call frame multiplexing into the compression layer. I'd rather have a separate layer which I can apply to many compression algorithms. You have a great advantage here Dave. With predictor, you can send the uncompressed data through with virtually no penalty. Most compression schemes do not have this capability. You don't need multilink. If you don't need error correction because you handle it internally, you don't need LAPB. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 8 13:09:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaVoy-0000T7a; Wed, 8 Sep 93 13:08 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 8 Sep 1993 09:31:09 -0800 Message-ID: <9309081631.AC21115@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Will your controller accept an XID (command or response) while in the >information transfer state? Does it pass both through? Or will you >simply let the LAPB timers go off and return to transparent mode? > >The XID is nice because it can include the remote ends ID, magic number, >etc. Magic number can be used to resolve 01/03/07/0f address assignments. XID does you one better; it resolves (negotiates) the address assignments, windows, and several otehr parameters. Yes, the Mostek 5025 handles an XID command in the information transfer state. I'd have to check on how it handles responses, but I believe that's not an issue, as I shouldn't be getting a response if I haven't sent a request. Not sure on the 68605 (3COM's chip). ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Sep 8 13:09:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaVp0-0000bga; Wed, 8 Sep 93 13:08 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Wed, 8 Sep 1993 10:40:44 -0800 Message-ID: <9309081741.AA22783@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >> >Fred, does this mean that the chip CANNOT indicate that an illegal LAPB >> >but properly checksummed frame has arrived? >> >> Yes and no. If it's to my address or my peer's address, LAPB requires that >> this result in a FRMR and a transition to NDM. If it's to another address, >> HDLC assumes that it is to some other station. Yes, LAPB is for point to >> point procedures, but HDLC has a wider view. The chips, I believe, would >> not fail the link on receipt of that data. >> >OK. Then this means that for your chip 0xff is not the "all-stations" >address? Right. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Sep 8 15:04:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaXci-0000Qva; Wed, 8 Sep 93 15:04 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Wed, 8 Sep 93 16:25:46 EDT Message-ID: <1072.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: dcarr@gandalf.ca (Dave Carr) > I see where you are coming from. Your moving the fragmentation and > what I call frame multiplexing into the compression layer. I'd rather > have a separate layer which I can apply to many compression algorithms. > I concur. Could we remove the fragmentation and compound frames from the compression spec, and put in references to multi-link (both LAPB and Sklower) and the "compound-frames" LCP option? Thanks. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Thu Sep 9 07:40:02 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oan9X-0000dka; Thu, 9 Sep 93 07:39 PDT Sender: owner-ppp-comp X-Path: MorningStar.Com!karl From: Karl Fox To: Dave_Rand@Novell.COM (Dave Rand) Subject: compression control memo Date: Thu, 9 Sep 93 10:38:38 -0400 Message-ID: <9309091438.AA07825@remora.MorningStar.Com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Organization: Morning Star Technologies, Inc. Precedence: bulk > Compression Types > > The compression types field lists the compression algorithms that > the are available. They must be listed in the order of > desirability for this particular link. > > The receiver will process the compression types field from left to > right, selecting the first protocol that matches the receiver's > capability. This protocol will be ACKed. All protocols that do > not match must be sent back in a REJect. If no protocols match, > all protocols must be REJected. But a Configure-Reject will prevent the peer from including the `1' option in any future Configure-Requests. I recommend you use Configure-Nak instead. From owner-ppp-comp Thu Sep 9 11:09:13 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaqPN-0000fUa; Thu, 9 Sep 93 11:07 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Thu, 9 Sep 1993 11:07:30 PDT Message-ID: <9309091807.AA06770@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Sep 8, 9:54, Dave Carr wrote: } } I agree with your logic, but I feel that the splitting of the frame } down to the MTU should NOT be buried in the compression layer. We have } the fragmentation protocol defined (Sklower multilink) which can take } care of fragmenting down to the MTU (or beyond). There is a good reason (or two) for doing this. The compressor is the only one that knows when it is running out of input data, and when to forward. Perhaps I better explain that further... "frame" means input frame destined for compression. "packet" means compressed data on the wire. In any link, there may be times that the link is idle. It is not acceptable for the compression algorithm to hold up a frame, waiting for enough data. Some compression algorithms may also peform better on a block-by-block basis, where a block is much larger than a frame. The compressor is the best judge of when to forward the frame. If you are just compressing frames into packets, for example, and only deal with 1 frame at a time (like type 1 predictor), then there is not a problem. Except, of course, for the issue of expansion. I have received a large number of comments WRT this issue. Some block-based algorithms will have an absolute worst case expansion ratio of 10:1 (although the typical worst case :-) will be more like 1.05:1). In that case, some method of splitting one frame into multiple packets is required. It has been suggested that a literal-next indication is one way of doing this - but block-based algorithms need to send out-of-band information to the decompressor. It has been suggested that multilink is a good way of doing this. I think the choice should be left up to the algorithm. It *knows* when it needs to span packets, and can take appropriate measures to ensure that this happens. There is no overhead at all when it doesn't need to span them. Predictor is bound to a 1.125:1 maximum expansion ratio, plus two bytes (for CRC). This can be handled in two ways: negotiate MTU to (real MTU * 1.125) + 2; or span packets with some mechanism. Other algorithms may need other features. One of the features that I really like was included in the type 2 predictor algorithm. That is the ability for more than one frame to be included in a packet. This is *very* useful on sync links with old chips - they usually insert a large number of flags between packets. This reduces the throughput for small packets on the wire - which is exactly what you are trying to do with compression. When you decouple the compression from the transport - just jam frames into the compressor - the compressor is free to forward packets when they are full (MTU), or when it runs out of input data - whichever comes first. This means full packets on the wire - which means better thoughput. It also is a clean implementation, since the compressor can just use a fputc type of macro, with a fflush when it runs out of input data. I think it makes a cleaner implementation the way it is defined. Type 1 predictor needs work to deal with the expansion case, however. As always, comments are welcome. -- From owner-ppp-comp Thu Sep 9 11:11:02 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oaqRq-000076a; Thu, 9 Sep 93 11:10 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Thu, 9 Sep 1993 13:16:14 -0400 (EDT) Message-ID: <9309091716.AA04327@donut.gandalf.ca> References: <<9309081631.AC21115@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > XID does you one better; it resolves (negotiates) the address assignments, > windows, and several otehr parameters. Fred, I'm whipping together a PPP LAPB Numbered Mode draft for the XID negotiation method. Could you give me a list of parameters for the XID. Also, how do the addresses get resolved? -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 9 12:39:18 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oarpO-0000Fga; Thu, 9 Sep 93 12:38 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Thu, 9 Sep 1993 15:36:27 -0400 (EDT) Message-ID: <9309091936.AA04390@donut.gandalf.ca> References: <<9309091807.AA06770@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > In any link, there may be times that the link is idle. It is not acceptable > for the compression algorithm to hold up a frame, waiting for enough > data. Some compression algorithms may also peform better on a block-by-block > basis, where a block is much larger than a frame. The compressor is the best > judge of when to forward the frame. Yes. You should forward to the link whatever data you have compressed so far and continue on compressing. This can be done by forwarding a fragment to the multilink layer. You can even start decompressing as soon as you get the fragment. But this can be accomplished with Sklower multilink. But if the link has been idle, how much extra data are you going to get through. Let's see. 64K link, 1 msec to compress 1500 bytes, wow, you save 8 whole bytes. Not a big win. I believe we went into this discussing latency in the compressor before. > If you are just compressing frames into packets, for example, and only > deal with 1 frame at a time (like type 1 predictor), then there is not > a problem. Except, of course, for the issue of expansion. I have received > a large number of comments WRT this issue. Some block-based algorithms > will have an absolute worst case expansion ratio of 10:1 (although the > typical worst case :-) will be more like 1.05:1). In that case, some > method of splitting one frame into multiple packets is required. Argh! 10:1. Are you sure they're not decompressors! Sklower.... Can handle MRRU up to 8K. It should not be too hard to limit the worst case to this :-) > It has been suggested that a literal-next indication is one way of doing > this - but block-based algorithms need to send out-of-band information to > the decompressor. It has been suggested that multilink is a good way of > doing this. I think the choice should be left up to the algorithm. I think the algorithm *is* free to send whatever it likes. So put me down as pro-choice! > It *knows* when it needs to span packets, and can take appropriate measures > to ensure that this happens. It does in the single link case. But often, it doesn't have control over what link the data is transmitted on in a multilink scenario. Both links could have different MTU's, be different speeds, encounter retransmissions etc. The compression layer should NOT be looking at the lower layers MTU. This said, your compressor can still choose to: (1) Forward data on a block by block basis; (2) Sub-frame multiplex; Just don't assume an MTU, or that your block size is the size of the frame going over the link. > There is no overhead at all when it doesn't > need to span them. Predictor is bound to a 1.125:1 maximum expansion ratio, > plus two bytes (for CRC). This can be handled in two ways: negotiate MTU > to (real MTU * 1.125) + 2; or span packets with some mechanism. Other > algorithms may need other features. Yes. But replace MTU with MRTU (maximum Re-assembled Transmit Unit). > > One of the features that I really like was included in the type 2 predictor > algorithm. That is the ability for more than one frame to be included in > a packet. This is *very* useful on sync links with old chips - they usually > insert a large number of flags between packets. Jees. And I thought that PPP disallowing shared 0's was a waste of bandwidth! Optimizing throughput of archaic hardware should not be one of our goals. Yes, making it work is a goal. Making it work well isn't. If you're that concerned with extra throughput, you should modify your predictor code. You'll get higher throughput by inverting your guess flags. A correct prediction should be encoded as a *zero* not a *one*. This way, you won't be stuffing as many zeroes into the HDLC data. Of course, your worst case might go to 1.3:1 :-) Freebie. I've used this in all my compressors (formerly a trade secret, now you caqn obtain a royalty free license through this special TV offer by calling the number on your screen today). I was berated for just this option mere months ago. Seems that everyone else was thinking only in terms of compressing 1500 byte packets, so who cared about a few extra bytes. I decided to drop the argument. If you persist, I'll be forced to bring up residuals. No sense wasting all those bits padding out to a byte boundary :-) > This reduces the throughput > for small packets on the wire - which is exactly what you are trying to > do with compression. No. We are concerned with *overall* performance. And, not all protocols send 576 byte packets or rely on 64 bytes acks coming back to send another (rub,rub)! And if your only getting 1.6:1 (:-)), you don't have to worry about the link overhead. All said, just how much do you gain from this percentage wise? > When you decouple the compression from the > transport - just jam frames into the compressor - the compressor is > free to forward packets when they are full (MTU), or when it runs > out of input data - whichever comes first. This means full packets > on the wire - which means better thoughput. It also is a clean implementation, > since the compressor can just use a fputc type of macro, with a fflush when > it runs out of input data. Sure. Just forward the fragments using Sklower multilink, and we are in agreement. > > I think it makes a cleaner implementation the way it is defined. Type 1 > predictor needs work to deal with the expansion case, however. Type 1 predictor should have a 1.01:1 expansion factor. Prefix the frame with a byte (bit) to indicate whether expansion occurred and send through the uncompressed frame AS IF IT WERE COMPRESSED. The decompressor simply updates it's tables the way the encoder did while attempting to compress (decompressor calls compressor with decompressor table pointer). Forive me if I'm stating the obvious, but you have the ideal algorithm for this method. Other methods require substantial memory to do the same. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 9 13:26:56 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oasZl-0000bCa; Thu, 9 Sep 93 13:26 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: pred type 2 Date: Thu, 9 Sep 93 14:25:49 -0600 Message-ID: <9309092025.AA12236@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk The problem with Type 2 is in having the upper layer packets span the boundaries of lower layer packets. That makes it hard to run without LAPB. Type 1 solves that problem, but also limits you to a single upper layer packet per link packet, which hurts its performance for small upper layer packets. What if you use type 2, but only never put more upper layer packets into a link layer packets than will fit in the peer's MRU or your upper layer MTU*1.25+4 ? In other words, negotiate type 2, procede to stuff packets into buffers, and if you ever run out of MTU, do not break the packet, but instead back up and send the prevous complete bundle of packets. In other words, I think the current Predictor Type 1 should be forgotten, and replaced a restricted version of Type 2, the restriction being that lower layer packet boundaries are respected. This would make Predictor Type 1 more effective, since it would allow several small upper layer packets to share the PPP framing overhead and the bit stuffing costs. This would also give Type 1 a packet length, which some of us (e.g. I) would find comforting. vjs From owner-ppp-comp Thu Sep 9 14:28:05 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oatWw-0000Pba; Thu, 9 Sep 93 14:27 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Thu, 9 Sep 93 15:26:52 -0600 Message-ID: <9309092126.AA12730@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Dave Carr, dcarr@gandalf.ca writes: > ... > Type 1 predictor should have a 1.01:1 expansion factor. Prefix the frame > with a byte (bit) to indicate whether expansion occurred and send through > the uncompressed frame AS IF IT WERE COMPRESSED. The decompressor simply > updates it's tables the way the encoder did while attempting to compress > (decompressor calls compressor with decompressor table pointer). > Forive me if I'm stating the obvious, but you have the ideal algorithm for > this method. Other methods require substantial memory to do the same. I wondered about this, but figured the intention must have been to keep it simple, and to not worry since the worst case of 1.125 is not bad. Also, the worst case expansion caused by adding a single byte to a PPP packet is far more than 1.01. You can't get down to 1.01 unless the original packet is at least 100 bytes long. Think about VJ-compressed TCP/IP ACKs. There is another bad case. Consider a PPP packet of MTU size that cannot be compressed. The best way to send that packet is to send it as a normal packet. It would never make sense to take a single packet, bloat it with "compression" stuff, and then fragment it into two packets. Still, how about this: 1. add a leading length to Type 1 for the reasons I just described. 2. reserve the length value 0 to mean "the following packet was not compressed, but by the way, the real length follows this" In other words, uncompressed packets would expand by 6 bytes, and would consist of a leading 0x0000, 2 bytes of length, the original packet and finally the extra CRC-16. Or use the sign bit of the length. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Thu Sep 9 16:10:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oav7U-0000RDa; Thu, 9 Sep 93 16:09 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Thu, 9 Sep 1993 18:51:09 -0400 (EDT) Message-ID: <9309092251.AA04533@donut.gandalf.ca> References: <<9309092126.AA12730@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > I wondered about this, but figured the intention must have been to keep > it simple, and to not worry since the worst case of 1.125 is not bad. Right. Two or three lines of code. Great simplification. I guess you don't want to look at FZA code then :-) One needs to look at the overall performance improvement. If this mod gets 12.5% more throughput on 20% of the packets (the ones that expanded but were shipped through expanded), that's a 3.125% compression improvement with NO CPU cycles and NO memory. I've already given simple improvements to the algorithm that will amount to 1-2% (Dave Rand to verify). Is this another few percent? I for one plan to test it tomorrow. I'll let you know. If someone can squeeze some more great. I'll switch :-) > Also, the worst case expansion caused by adding a single byte to a PPP > packet is far more than 1.01. You can't get down to 1.01 unless the > original packet is at least 100 bytes long. Think about VJ-compressed > TCP/IP ACKs. My assumption was based on the fact that you need one BIT to indicate expansion, and the damn PPP framing is about 10 bytes. So yes, on minimum length packets it's more than 1.01. But one bit on 1500 bytes is .00008, or .01%. Note also Vernon, we were talking about exceeding the MTU of the link. I assume your MTU is longer than 100 bytes. If it takes only one byte to indicate expansion, the MTU can surely be adjusted by 1. > > There is another bad case. Consider a PPP packet of MTU size that > cannot be compressed. The best way to send that packet is to send it > as a normal packet. It would never make sense to take a single packet, > bloat it with "compression" stuff, and then fragment it into two packets. O contrare mon ami. (My french isn't that good even though I can see Quebec as I'm typing). On the contrary my friend... One does not have the luxury of sending it through uncompressed without going through the compression layer. The problem is Vernon, that to determine that a packet doesn't compress requires compressing the packet. The encoder tables have been modified. So you can either reset the compression tables, or have the decoder update its table by "compressing" the frame also. Predictor 1 simply bloats the frame. Predictor 2 send the compressed data mixed with uncompressable stuff, bloated, as one stream. These bloated frames are chopped into more than one MTU. What's the diff? Yes, I can see that by filling the packets to the MTU and treating the transfer as one byte stream will be more efficient on the link. But the same is true if you use a more efficient framing. In reality, a fragmented, LAPB error corrected frame has 5 bytes of overhead (flag,Address,Control,FCS). Sequence number is inside address field! It's only PPP that adds the bloat! And in the end, how much (in percent) does it improve the throughput?? > > Or use the sign bit of the length. Use the sign, unless you're planning on a real large MTU! -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Thu Sep 9 18:16:32 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oax5v-0000Vpa; Thu, 9 Sep 93 18:16 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Thu, 9 Sep 93 19:14:51 -0600 Message-ID: <9309100114.AA14076@rhyolite.wpd.sgi.com> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Dave Carr, dcarr@gandalf.ca writes: > ... > > Also, the worst case expansion caused by adding a single byte to a PPP > > packet is far more than 1.01. You can't get down to 1.01 unless the > > original packet is at least 100 bytes long. Think about VJ-compressed > > TCP/IP ACKs. > > My assumption was based on the fact that you need one BIT to indicate > expansion, and the damn PPP framing is about 10 bytes. So yes, on minimum > length packets it's more than 1.01. But one bit on 1500 bytes is .00008, > or .01%. How do you "add one bit" to a packet? I thought about arguing for an additional CCP protocol ID that would say "this packet did not compress", but figured 1 bit would not be enough for all cases, and compression protocols that really need to do such things (e.g. the 10:1 bloater) would be better off adding their own headers in their own encapsulation. > Note also Vernon, we were talking about exceeding the MTU of the link. > I assume your MTU is longer than 100 bytes. If it takes only one byte > to indicate expansion, the MTU can surely be adjusted by 1. That was not evident. You appeared to be talking about passing packets that failed to compress, one particularly important case of which are packets that bloat past the MTU. Even if the bloated packet does not excede the MTU, it would still be far better to do the old standard thing, send the uncompressed version and let the peer recompute the dictionary delta. Consider the fabled 10:1 algorithm. > > There is another bad case. Consider a PPP packet of MTU size that > > cannot be compressed. The best way to send that packet is to send it > > as a normal packet. It would never make sense to take a single packet, > > bloat it with "compression" stuff, and then fragment it into two packets. > > O contrare mon ami. (My french isn't that good even though I can see Quebec > as I'm typing). On the contrary my friend... One does not have the > luxury of sending it through uncompressed without going through the > compression layer. > > The problem is Vernon, that to determine that a packet doesn't compress > requires compressing the packet. The encoder tables have been modified. > .... That's a good point. With Predictor, it takes only about 3 MIPS CPU cycles/byte (in the packet) to keep enough info restore the table, and only another 5 cycles/byte to actually restore the table should you need to. > Yes, I can see that by filling the packets to the MTU and treating the > transfer as one byte stream will be more efficient on the link. But > the same is true if you use a more efficient framing. In reality, > a fragmented, LAPB error corrected frame has 5 bytes of overhead > (flag,Address,Control,FCS). Sequence number is inside address field! > It's only PPP that adds the bloat! I'm allergic to LAPB. It offends me to have to have retransmission queues in a link layer driver. It bugs me no end to couple the input and output streams of a link layer driver. I might not be so unalterably opposed to the silliness of LAPB under TCP if I had to use chips that forced LAPB on me. LAPB under TCP strikes me as classic standards committee stuff. (E.g. the LLC DLIP XID test for duplicate address detection that does absolutely no good on media like Ethernet were duplicate addresses are not an issue, is absolutely useless on media like FDDI where duplicate addresses cause messy problems, and blithely assumes that on no media does a sender ever receive its own transmissions.) Oh, well. The router box people seem to require LAPB, so they should have it. > And in the end, how much (in percent) does it improve the throughput?? Ok, here's a "Predictor 3" that seems like it should do significantly better... 1. tell the upper layers the MTU is 1/2.5 of the MRU requested by the peer, and hope the peer asks for at least 3750. (Maybe help out with a config NAK) 2. concatenate up to 3000 bytes of whole PPP frames. No fragments. 3. compress the whole thing as if with Predictor 1 4. don't worry and hope no one complains about the latency effects of 3K packets.. Given the assumption that you're passing a lot of VJ-compressed TCP small packets (telnet or ACKS) where the repetative PPP framing is significant part of the total bandwidth, Predictor should be quite effective on concatenated PPP frames.. A PPP channel completely saturated with TCP ACKs is not so unlikely Consider a Hybrid Systems LAN-over-cable-TV scheme. I don't know what they're using on the back-channel, but their claimed ratio of back/forward channel bandwidth is within 1% of what I figure it would be if they are using PPP and VJ-compression. > > Or use the sign bit of the length. > > Use the sign, unless you're planning on a real large MTU! What? A standards committee that would let compression reduce the standardized maximum PPP MTU by 50%? Even if a 60K MTU is wrong, a little big for a v.32 modem link and too small for a HIPPI link? Amazing. Of course, you could simply revert to vanilla PPP for all upper layer packets larger than 32K. Or refuse to do Predictor on all links with an MTU > 32K. vjs From owner-ppp-comp Fri Sep 10 07:07:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ob96o-0000A7a; Fri, 10 Sep 93 07:05 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr (Dave Rand) To: ppp-comp@Bungi.com Subject: ISO Multi link Date: Fri, 10 Sep 93 07:05 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Could I have a call for votes on whether to specify ISO Multilink in the LAPB document, or not? Please mail your votes to dlr@bungi.com Thanks! Dave From owner-ppp-comp Fri Sep 10 08:35:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0obAVB-0000aaa; Fri, 10 Sep 93 08:35 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Fri, 10 Sep 93 11:10:45 EDT Message-ID: <1093.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > "frame" means input frame destined for compression. "packet" means compressed > data on the wire. > This is exactly backward from the usual usage. The frame is on the wire, the packet is inside the frame, and the datagram is inside the packet. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Fri Sep 10 08:49:19 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0obAie-0000S5a; Fri, 10 Sep 93 08:49 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Fri, 10 Sep 1993 11:47:06 -0400 (EDT) Message-ID: <9309101547.AA04713@donut.gandalf.ca> References: <<9309100114.AA14076@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > How do you "add one bit" to a packet? I think you actually had the solution. The count field you recommended was 2 bytes long. Are you going to use all the bits? But serially, I can add a *fraction* of a bit with an arithmetic encoder! > > I thought about arguing for an additional CCP protocol ID that would > say "this packet did not compress", but figured 1 bit would not be > enough for all cases, and compression protocols that really need to do > such things (e.g. the 10:1 bloater) would be better off adding their own > headers in their own encapsulation. No. Just the same compression ID that was used to compress the packet, and an indication that expansion occured carried with the uncompressed data. > > That was not evident. > You appeared to be talking about passing packets that failed to compress, > one particularly important case of which are packets that bloat past the MTU. Here's that MTU again. Can we digress for a moment? We've been doing WANs for years around here, and when I think MTU, it means to me what size packets are appropriate to send over this link. This size has more factors in the WAN sense, than would normally be applicable to LANs. If I were configuring the MTU of a WAN, I'd consider the media (digital, analog, satellite, ...) which gives an error rate. Higher the error rate, the shorter the MTU. Second, I'd factor in whether the link is running in a multilink, such as would be normal on an ISDN basic rate interface. Third, if it were a multilink, are the line speeds equal. All of the above seemed to indicate to me that the upper layers really don't and should care about the MTU of the link because they won't know which link the packet is going over. All they are concerned with is the MAXIMUM MTU of the multilink. Therefore, I'm more concerned with the MRRU (and corresponding MRTU) for the multilink. So, where am I going with this? Well, I think the compression layer should be free to generate a continuos stream of characters for transmission, and it's up to the lower layers to pass the data according to their MTUs. Only now, I'd suggest the cleanest way to implement this is through Sklower multilink. > > Even if the bloated packet does not excede the MTU, it would still be > far better to do the old standard thing, send the uncompressed version > and let the peer recompute the dictionary delta. Consider the fabled > 10:1 algorithm. Exactly! But you can't send it through without passing it in anything but the same CCP ID. I thought you were implying that the packet could be sent as a regular IP frame or the like. I think were on the same wavelength here. > > With Predictor, it takes only about 3 MIPS CPU cycles/byte (in the packet) > to keep enough info restore the table, and only another 5 cycles/byte > to actually restore the table should you need to. Restore the table? Are you thinking about restoring the compressors table? Why not just update the decoders table. It takes *no* time. Here's another thing to factor in. When the packet doesn't compress, the data on the line will "last" longer. So you actually have more time when the data doesn't compress to compress the original uncompressed frame in the decoder. You're worst CPU usage case is when the data compresses a lot. That's why I like to view the compressor from the line side, ie. output line rate, not the input bytes/sec. The same method is valid for static encoded LZ77 (sliding window). Here, to update the decoders table only involves a memcpy. The tricky part comes when anything other than a static encoding is used. But there are ways around this too. > > I'm allergic to LAPB. It offends me to have to have retransmission > queues in a link layer driver. It bugs me no end to couple the input > and output streams of a link layer driver. I might not be so unalterably > opposed to the silliness of LAPB under TCP if I had to use chips that > forced LAPB on me. > > LAPB under TCP strikes me as classic standards committee stuff. What about LAPB under IPX? Vernon, you seem to be have a LAN bias. I seem to have a WAN bias. I doubt the twain shall meet :-( I think one of the factors here is again the MTU. What we happen to do on our our LAPB links is send packets far shorter than the typical 1500 byte MTU. We just slapped in Sklower multilink into our compression bridge. All frames on the link go out 256 bytes of payload (MTU varies with link speed). Why? First, on error prone links (dialup), we can retransmit the frame far faster than TCP can, mainly cause typically only one fragment of 256 gets hit. If we were sending 1500 MTUs, then you have a valid point. With data compression, assuming a modest 2:1 compression, we can retransmit a hit fragment multiple times, and still get it there before a non-error-corrected link using 1500 byte MTUs. Of course, I'm assuming that selective reject is used, so you don't have to retransmit all fragments, just the one that went missing. Sure would be nice if IP did that too! This fragmentation and LAPB allows operation on lines with 10E-5 error rate, where TCP would probably time out. And don't say that error rates too high, you don't live up here in Canada. On error-free links, the PPP overhead on 256 byte packets is only around 2-3%. The data compression layer more than adeqately makes up for this. Now, for the real win. It's a lot easy to load balance across multiple links, links with different speeds, etc. The fragmentation layer supplies multiple fragments of a reasonable size, and the multilink simple operates using the bank-tellers algorithm. Another advantage is when running non-windowed protocols (dare we mention names?). I am free to split the 1500 byte packet down into 6 pieces and fire each over one of 6 64K links. Seems to work out nicely. BTW, we use the Zilog 16C30. (Boy, could I digress here!). We could do just about anything on the line we chose. The LAPB is totally software. It's not forced on me, we chose it. > (E.g. the LLC DLIP XID test for duplicate address detection that Oh, and I thought I digress to much! > Ok, here's a "Predictor 3" that seems like it should do significantly > better... > 1. tell the upper layers the MTU is 1/2.5 of the MRU requested > by the peer, and hope the peer asks for at least 3750. > (Maybe help out with a config NAK) > 2. concatenate up to 3000 bytes of whole PPP frames. No fragments. > 3. compress the whole thing as if with Predictor 1 > 4. don't worry and hope no one complains about the latency effects > of 3K packets.. > > Given the assumption that you're passing a lot of VJ-compressed TCP > small packets (telnet or ACKS) where the repetative PPP framing is > significant part of the total bandwidth, Predictor should be quite > effective on concatenated PPP frames.. Why not just add another layer, the "statistic mux" layer. Really! I just happen to have written multiple statmuxes in my time, and that's exactly what you're asking for! Geez, I've even got compression stat-mux experience :-) It's what really made me think hard about the PPP framing overhead in the first place. > > A PPP channel completely saturated with TCP ACKs is not so unlikely > Consider a Hybrid Systems LAN-over-cable-TV scheme. I don't know what > they're using on the back-channel, but their claimed ratio of > back/forward channel bandwidth is within 1% of what I figure it > would be if they are using PPP and VJ-compression. Yes, a mux layer may help. An alternate scheme is to reduce the number of acks required by using the right protocol. Modems and file transfer protocols such as X,Y,Z,MODEM all try to get around the acks and using ping-pong turnaraound on a half-duplex line. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Fri Sep 10 14:13:03 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0obFlC-0000S2a; Fri, 10 Sep 93 14:12 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Fri, 10 Sep 93 14:18:47 -0600 Message-ID: <9309102018.AA20860@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Dave Carr writes: > > How do you "add one bit" to a packet? > > I think you actually had the solution. The count field you recommended > was 2 bytes long. Are you going to use all the bits? What's this "you" kemo sabe? The way I see it, the guy who wrote the spec gets most of the votes on at least Predictor 2, and he's not me. I'm just an alien here; I can't even think of a single relative of mine who is named Dave or David. I'd like to see at least Predictor 2 have a "didn't compress" bit, and just say all 32K packets are passed in their native encapsulation. Since no one in their right mind would use PPP on a medium where a 32K MTU makes sense, and since it is likely that no PPP implementation will ever support a 32K MRU, that is no problem. > Here's that MTU again. Can we digress for a moment? > > We've been doing WANs > for years around here, and when I think MTU, it means to me what size packets > are appropriate to send over this link. This size has more factors in the > WAN sense, than would normally be applicable to LANs. If I were configuring > the MTU of a WAN, I'd consider the media (digital, analog, satellite, ...) > which gives an error rate. Higher the error rate, the shorter the MTU. > > Second, I'd factor in whether the link is running in a multilink, such > as would be normal on an ISDN basic rate interface. > > Third, if it were a multilink, are the line speeds equal. > > All of the above seemed to indicate to me that the upper layers really don't > and should care about the MTU of the link because they won't know which link > the packet is going over. All they are concerned with is the MAXIMUM MTU > of the multilink. Therefore, I'm more concerned with the MRRU (and > corresponding MRTU) for the multilink. > > So, where am I going with this? Well, I think the compression layer should > be free to generate a continuos stream of characters for transmission, and > it's up to the lower layers to pass the data according to their MTUs. > Only now, I'd suggest the cleanest way to implement this is through > Sklower multilink. Hmmph. I thought of something last night. It explains the enthusiasm for LAPB. Since router guys don't otherwise get to play with retransmission queues, RTT's, selective vs. go-back-N retransmission, slow start, fast retransmission, retransmission timers, and all of the other fun stuff in TCP, they want or don't mind LAPB and a few of those fun games. Those of us who already have one or more albatrosses with all of those feathers don't want another. What you say about the link layer MTU makes some sense, but you are wrong when you say that in general the real MTU does not matter to the higher layers. If you want a case study, go look at the ATM tests and 48/53 bytes. Don't listen to the public words or even privately to the ATM switch or host (adapter) vendors. Talk to some of the third parties with real hardware, not just white boards, overhead projectors, and smooth tongues. From what I've heard (names withheld by request), the fabled TCP-ATM congestion collapse is a real problem with no currently implemented solutions. (Never mind the other TCP/IP-over-ATM problems.) I agree that the compression stuff should be free to re-packetize to its own taste. Some flavors of multilink might be good for compression above multilink, but I don't have an opinion on which flavors. My personal perference is for "brutally simple multilink," where each link is a complete and independent PPP stack, with complete IP packets sent to each PPP stack, to be independently compressed. As we've agreed before: Yes, that works only for IP. Yes, that requires robust (i.e. H.R. RFC conformant) IP hosts. No, VJ-compression works just fine. Yes, the code is simple. No, there is no chance any standards committee would ever agree to this so it will remain a "proprietary" hack. > > Even if the bloated packet does not excede the MTU, it would still be > > far better to do the old standard thing, send the uncompressed version > > and let the peer recompute the dictionary delta. Consider the fabled > > 10:1 algorithm. > > Exactly! But you can't send it through without passing it in anything > but the same CCP ID. I thought you were implying that the packet could > be sent as a regular IP frame or the like. I think were on the same > wavelength here. Yes and no. Yes, if you want to train the other end's dictonary, you must send it through the same CCP ID. Yes, if you want to train the local dictionary so that the next packet doesn't bloat, you must train the other end's dictionary. No, you can decide that this 10:1 bloater of a packet is unusual and send it through as a regular IP frame or the like. Yes, that means you must roll back changes to the local dictionary (not a fatal problem for predictor). Yes, I too bet that anything that suffers 10:1 on one packet will do the same on the next, unless you let the dictionaries learn. If you really have 10:1, you're going to have to send it bloated and fragmented, and just hope for the best. With Predictor #1 without LAPB, you have little choice but to either 1. negotiate an MTU of 1.125N+2 2. send bloaters as regular IP frames, hope the hash table doesn't care, and either recognize bloaters before compressing (e.g. look for all ASCII bytes) or roll back hash table changes. Feel free to not comment about compression and no LAPB if you are always going to use LAPB. There's a reason I have nothing to say about the details of LAPB, and very little about the details of Multilink; I don't intend to have anything to do with either. > > With Predictor, it takes only about 3 MIPS CPU cycles/byte (in the packet) > > to keep enough info restore the table, and only another 5 cycles/byte > > to actually restore the table should you need to. > > Restore the table? Are you thinking about restoring the compressors > table? Why not just update the decoders table. It takes *no* time. Only if you can send the packet to the decoder, and have the decoder recognize that it is a "compressed" packet that should update the table. If you're forced to send the packet uncompressed and lack a "didn't compress" indication, you must do as you wrote last time, and restore the table. > Here's another thing to factor in. When the packet doesn't compress, the > data on the line will "last" longer. So you actually have more time when > the data doesn't compress to compress the original uncompressed frame in > the decoder. You're worst CPU usage case is when the data compresses a lot. That's true for the receiver, but can be false for the sender, if the sender is forced to restore the table. > > I'm allergic to LAPB.... > What about LAPB under IPX? I have no opinion about IPX, with or without LAPB, multilink, or even PPP. I have no current expectations of doing anything with it. I have heard that some implementaitons of IPX want LAPB. > Vernon, you seem to be have a LAN bias. I seem to have a WAN bias. > I doubt the twain shall meet :-( Yes. More important is that you're interested in routers and forwarders, while I care about hosts. > I think one of the factors here is again the MTU.... > First, on error prone links (dialup), we can retransmit the frame far > faster than TCP can, mainly cause typically only one fragment of 256 > gets hit. If we were sending 1500 MTUs, then you have a valid point. > With data compression, assuming a modest 2:1 compression, we can > retransmit a hit fragment multiple times, and still get it there before > a non-error-corrected link using 1500 byte MTUs. As others have often observed, the main point there is "error prone links". When the link error rate gets high enough (or perhaps bandwidth*delay), then per-link error recover makes sense. While the link error rate is low enough, link error detection and purely end-to-end recovery wins. > Of course, I'm assuming that selective reject is used, so you don't have > to retransmit all fragments, just the one that went missing. Sure would > be nice if IP did that too! IP is a datagram protocol with absolutely no error recovery at all, and no data error detection, so it would make no more sense for IP selectively retransmit. TCP, on the other hand, does have a well established experimental selective ACK scheme. More important, common TCP implementations with "fast retransmission" have (in effect) selective retransmission. I hope you're not making too many decisions about PPP and compression based on such information about TCP/IP. > This fragmentation and LAPB allows operation on lines with 10E-5 error > rate, where TCP would probably time out. Yes, the old rule about link error recover on bad links. > On error-free links, the PPP overhead on 256 byte packets is only around > 2-3%. The data compression layer more than adeqately makes up for this. No. The data compression layer cannot make up for the wasted bandwidth. Once you waste it, you can never get all of it back. At best, compression recovers most of the waste. > Now, for the real win. It's a lot easy to load balance across multiple > links, links with different speeds, etc. The fragmentation layer > supplies multiple fragments of a reasonable size, and the multilink > simple operates using the bank-tellers algorithm. I'll believe good TCP performance over such bundles of mixed media when I see it running. > Another advantage is when running non-windowed protocols (dare we mention > names?). I am free to split the 1500 byte packet down into 6 pieces > and fire each over one of 6 64K links. Seems to work out nicely. That sounds like it would work well. The latency for 1500 Byte IP packets would be 5 or 6 times better than my prefered "brutally simple" scheme, but no different for 8K NFS UDP/IP packets. All that matters is the application. How fast an XID can be turned around, or even a TCP ACK, is a secondary detail. > > A PPP channel completely saturated with TCP ACKs is not so unlikely > > Consider a Hybrid Systems LAN-over-cable-TV scheme. I don't know what > > they're using on the back-channel, but their claimed ratio of > > back/forward channel bandwidth is within 1% of what I figure it > > would be if they are using PPP and VJ-compression. > > Yes, a mux layer may help. An alternate scheme is to reduce the number > of acks required by using the right protocol. Modems and file transfer > protocols such as X,Y,Z,MODEM all try to get around the acks and > using ping-pong turnaraound on a half-duplex line. Wrong. It's possible to reduce the number of TCP ACK's. First and easiest is to use a larger TCP MSS, and probably but not necessarily, as Cray and NCS showed years ago, a larger MTU. Second, if your back channel is saturated and by nothing except TCP ACK's the obvious thing that works fine is to send only the ACK's you need to send. The 4.3BSD code will in fact almost do that by accident of the way IP is hooked to the link layer. The "2 segments/ACK" rule in TCP is no more than a good rule of thumb that helps compute the RTT used by the most common implementation. The TCP protocol itself makes no such demand. The protocol allows one ACK per window of data; the current TCP window (TCP-LW) is plenty big enough. Somewhat seriously, I've frequently bothered by the lack of knowledge about TCP in the PPP working groups. For better or worse, TCP/IP and UDP/IP are the main clients of PPP. It would be wise to know how they work and what they need. vjs From owner-ppp-comp Sun Sep 12 17:10:22 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oc1UD-0000E2a; Sun, 12 Sep 93 17:09 PDT Sender: owner-ppp-comp X-Path: lloyd.com!brian From: brian@lloyd.com (Brian Lloyd) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Sun, 12 Sep 93 16:51:30 -0700 Message-ID: <9309122351.AA24700@spider.lloyd.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk At 11:10 9/10/93 -0400, William Allen Simpson wrote: >The frame is on the wire, the packet is inside the frame, and the >datagram is inside the packet. I agree with Bill re the description of the word "frame." In my experience the word "datagram" has been used to describes the the information unit from the internet layer of a connectionless network protocol stack. I have never heard an unambiguous description for the work "packet." I would have to say that it was very clearly defined by Tweedledum (Tweedledee?) to Alice (with very slight paraphrasing on my part), "the word 'packet' means precisely what I mean it to say; nothing more and nothing less." Therefore, I would avoid using the word "packet" anywhere where you do not clearly define it within the context of the specific document within which it appears. Brian Lloyd, President BP Lloyd & Associates, Inc. brian@lloyd.com 3420 Sudbury Road (916) 676-1147 - voice Cameron Park, CA 95682 (916) 676-3442 - fax From owner-ppp-comp Mon Sep 13 08:37:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ocFy7-0000Asa; Mon, 13 Sep 93 08:37 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Mon, 13 Sep 1993 11:35:33 -0400 (EDT) Message-ID: <9309131535.AA06434@donut.gandalf.ca> References: <<9309102018.AA20860@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > What's this "you" kemo sabe? The way I see it, the guy who wrote Sorry. After writing this response, I only had to take out four you's and 3 your's. Bad habits are hard to break. But most of the you's were general, and not directed at you! :%s/you/one/g > > I'd like to see at least Predictor 2 have a "didn't compress" bit, and > just say all 32K packets are passed in their native encapsulation. Yes. This will work if the encoder backs out. In the algorithms I've played with, this is more difficult than updating the decompressors dictionary. The expansion happens for various reasons. One is a change in data stream entropy. Backing out the compression may mean that the algorithm never again adapts. Once data expands, one may not be able to compress again. Of course, it might be just a blip in which case one can pick up where one left off. Predictor is just so flexible! It's also "exceptional" in terms of being able to back out or at no cost compress using the same structures as decompress. > I thought of something last night. It explains the enthusiasm for > LAPB. Since router guys don't otherwise get to play with retransmission > queues, RTT's, selective vs. go-back-N retransmission, slow start, fast > retransmission, retransmission timers, and all of the other fun stuff > in TCP, they want or don't mind LAPB and a few of those fun games. Are you (This you is for you) kidding. That's why we love COMPRESSION. Hashing, Sigma buffers, tries, multiply threaded lists, suffix trees, LRU and MTF queues, ... It's our chance to use all those exotic data structures. > Those of us who already have one or more albatrosses with all of those > feathers don't want another. Basic ring buffers and link lists are passe'. Have some real fun Vern! Dig out Knuth. Blow off the dust and join the fun. > What you say about the link layer MTU makes some sense, but you are > wrong when you say that in general the real MTU does not matter to the > higher layers. If you want a case study, go look at the ATM tests and > 48/53 bytes. Don't listen to the public words or even privately to the > ATM switch or host (adapter) vendors. Talk to some of the third > parties with real hardware, not just white boards, overhead projectors, > and smooth tongues. From what I've heard (names withheld by request), > the fabled TCP-ATM congestion collapse is a real problem with no > currently implemented solutions. (Never mind the other TCP/IP-over-ATM > problems.) I haven't followed this at all, so I can't comment. We have had an ATM-like switch for a couple of years. It happens to use *smaller* cells however. There's fragmentation is the IP sense where you create a new packet complete with a new IP header from a large packet. The WAN type fragmentation I'm talking about doesn't do that. The packet gets re-assembled into its pre-fragmentation form by the other end. This is transparent to TCP/IP. Does this still have a problem over ATM? > Feel free to not comment about compression and no LAPB if you are > always going to use LAPB. There's a reason I have nothing to say about > the details of LAPB, and very little about the details of Multilink; I > don't intend to have anything to do with either. It's not that I haven't played with non-error-corrected links with compression. It can work either way. But what would help is if someone would publish some comparison between compression ratios over both types of links. And, I should add, this this NOT a new idea. One company I know of have been shipping a compression statmux for 5 years using this idea. They also use a maximum frames size of 32 bytes to reduce latency. > As others have often observed, the main point there is "error prone links". > When the link error rate gets high enough (or perhaps bandwidth*delay), > then per-link error recover makes sense. While the link error rate is > low enough, link error detection and purely end-to-end recovery wins. I've heard that before. I'd like to know the *implementation* used in this comparison. Can you quote some papers on the matter? Please define "low enough". The overhead on maximum length packets for LAPB is 2-3 bytes on 1518, or 99.8% efficient. This assumes address and control field compression for the straight PPP. Some big drop in performance. The PPP implementations I've seen, don't bother to do ACF compression on synchronous links. In this case, LAPB is *never* a loss. On 10E-10 links, LAPB is no worse than straight PPP. Somewhere between 10E-5 and 10E-10 there are some tradeoffs to be made. With non-error corrected links, you get what you get. With LAPB, the implementation is free to adapt. In my idea of a perfect LAPB implementation, the MTU is adjusted to the link error rate. The MTU adjustment permits OPTIMUM throughput in all conditions. Tell me how your ideal TCP over non-error-corrected links work. > IP is a datagram protocol with absolutely no error recovery at all, > and no data error detection, so it would make no more sense for IP > selectively retransmit. I agree with this. I meant TCP. > I hope you're not making too many decisions about PPP and compression > based on such information about TCP/IP. No. I realize how TCP/IP basics. The inner details of fast-start etc. I'll leave to you experts. > > > Now, for the real win. It's a lot easy to load balance across multiple > > links, links with different speeds, etc. The fragmentation layer > > supplies multiple fragments of a reasonable size, and the multilink > > simple operates using the bank-tellers algorithm. > > I'll believe good TCP performance over such bundles of mixed media when > I see it running. Well, perhaps you should try our product. It does run, and runs well. Of course it's only a bridge (number one in the market), and that may bother you. And if you'd like to try out the Sklower type fragmentation, I can arrange some demo units for you. > > > Another advantage is when running non-windowed protocols (dare we mention > > names?). I am free to split the 1500 byte packet down into 6 pieces > > and fire each over one of 6 64K links. Seems to work out nicely. > > That sounds like it would work well. The latency for 1500 Byte IP > packets would be 5 or 6 times better than my prefered "brutally simple" > scheme, but no different for 8K NFS UDP/IP packets. Exactly. The bank tellers algorithm even works for NFS. But running Novell, even with burst mode, the bank tellers algorithm can never load balance properly. > Somewhat seriously, I've frequently bothered by the lack of knowledge > about TCP in the PPP working groups. For better or worse, TCP/IP and > UDP/IP are the main clients of PPP. It would be wise to know how they > work and what they need. Admittedly, my knowledge of TCP is far below yours. To assume that it is as low as you state is a mistake. I do not spend all day writing up these replies, and sometimes my fingers get ahead of my brain. I on the other hand am not bothered at all by anyones lack of WAN experience in the PPP working groups. I wish only to share my experience with them. I do believe that router people are more knowledgable about WANs than workstation vendors, probably from experience. I feel that LAPB hasn't been given a fair shake, possibly because of some simplistic implementation. I'm not saying ours is better than everyones. But the same would be true for TCP if all the TCP implementations were done by some PeeCee software (no names) house. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Mon Sep 13 13:00:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ocK3z-00007ua; Mon, 13 Sep 93 12:59 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: More CCP comments Date: Mon, 13 Sep 93 13:59:02 -0600 Message-ID: <9309131959.AA01017@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > I'd like to see at least Predictor 2 have a "didn't compress" bit, and > > just say all 32K packets are passed in their native encapsulation. > > Yes. This will work if the encoder backs out.... That's not what I meant. No "encoder back out" is needed, desirable, nor appropriate. Instead, on the sender 1. if packet size > 32767 (or maybe 32765), then send with native encapsulation 2. else, if packet size < 32767, then (a) compress the packet (b) if compressed packet > uncompressed packet, then send uncompressed packet with appropriate length but with 0x8000 OR'ed with that length (c) else send packet as with normal Predictor 2. On the receiver, I. deal with IP, IPCP, VJ-COMP, VJ-UNCOMP, and all other non-CCP packets as usual, including those sent by (1) above. II. if the Predictor 2, and if packet length = 0x8000 | length, then run uncompressed packet through local, receiver's dictionary. III. else, do familiar Predictor 2. In other words, just what one would expect. There are other ways to convey the same "didn't compress" bit that seem about as good to me, and there is hope that Dave Rand might like one of them. Anyone who feels strongly should send a message to Dave. > There's fragmentation is the IP sense where you create a new packet complete > with a new IP header from a large packet. The WAN type fragmentation I'm > talking about doesn't do that. The packet gets re-assembled into its > pre-fragmentation form by the other end. This is transparent to TCP/IP. > Does this still have a problem over ATM? TCP/IP packets are chopped up into AAL-5 ATM cells of 48 bytes payload invisibly to IP at either end or any intermediate or TCP at either end. The problem is that should switch congestion (or anything else) cause the loss of a single cell, the entire IP datagram, containing the entire TCP segment, will eventually have to be retransmitted, and, worse, the other ATM 48-byte payloads that did not get lost will also be delivered, so that the switch is relieved of very little congestion by dropping the one cell, but causes the end points to offer a lot more load. ATM switches are supposed to be for fast networks; talk starts at 155Mbit/sec and goes up fast (yes, I know of the "low speed" ATM proposals. They may work for low cost, wide areas, but they seem unlikely to be competative elsewhere.) High speed and long distances (e.g. Gigabit/sec and 1000 kilometers) means a large bandwidth*delay product, which requires large amounts of data in flight at any instant. Some application protocols, such as NFS, use UDP datagrams, which must have at least 8K and should have 800KBytes in flight to get reasonable performance. Consider the consequences of losing 1 cell per 1000 due to congestion. > ... > I feel that LAPB hasn't been given a fair shake, possibly because of some > simplistic implementation. I'm not saying ours is better than everyones. > But the same would be true for TCP if all the TCP implementations were > done by some PeeCee software (no names) house. As long as we continue to have compression with and without LAPB, LAPB will be given a fair shake. vjs From owner-ppp-comp Tue Sep 14 11:15:24 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ocetW-0000Ofa; Tue, 14 Sep 93 11:14 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: lapb negotiation Date: Tue, 14 Sep 1993 11:13:37 -0800 Message-ID: <9309141814.AA29606@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >> XID does you one better; it resolves (negotiates) the address assignments, >> windows, and several otehr parameters. > >Fred, I'm whipping together a PPP LAPB Numbered Mode draft for the XID >negotiation method. Could you give me a list of parameters for the XID. >Also, how do the addresses get resolved? You need ISO 8885 (definition of XID fields) and 8471 (how to negotiate). I've been looking for my copy of the former (the latter is in the McGraw Hill Black books, volume 3) and haven't found it. probably relates to my filing system. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Sep 15 20:26:37 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0od9yZ-0000Tqa; Wed, 15 Sep 93 20:25 PDT Sender: owner-ppp-comp X-Path: vangogh.CS.Berkeley.EDU!sklower From: Keith Sklower To: ietf-ppp@ucdavis.edu, ppp-comp@bungi.com Subject: Disclaimer: silence does not mean credit-taking Date: Wed, 15 Sep 1993 20:24:36 -0700 Message-ID: <199309160324.UAA05175@vangogh.CS.Berkeley.EDU> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I'm a little nervous seeing numerous references to ``Sklower Multilink'', and feel if I don't speak up, then I'm implicitly taking credit for intellectual property mostly contributed by other people. I would prefer the term ``PPP Multilink'', or even ``Internet Multilink''. This document is supposed to reflect committee consensus rather than necesarily my own taste or invention. Of course, I do have some opinions on the subject! (and will continue to voice them as vocifierously as anybody else). We now return you to your regularly scheduled harrangues ;-) From owner-ppp-comp Mon Sep 20 22:21:35 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0of08n-0000tta; Mon, 20 Sep 93 22:19 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr (Dave Rand) To: ppp-comp@bungi.com Subject: Closure items? Date: Mon, 20 Sep 93 22:19 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Based on the response, I would like to delete the ISO MultiLink from the LAPB negotiation document. In addition, we need to reach closure on the compression RFC. Is there any objection to adding a length field to Predictor 1, with the most significant bit indicating no compression? On type 2, I propose that the same mechanism be used. Any other pending comments? Dave From owner-ppp-comp Tue Sep 21 11:01:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofC1w-0000Zza; Tue, 21 Sep 93 11:01 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: RE: Closure items? Date: Tue, 21 Sep 93 10:56:09 TZ Message-ID: <9309211800.AB28066@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Dave Rand | | In addition, we need to reach closure on the compression RFC. Is there | any objection to adding a length field to Predictor 1, with the most | significant bit indicating no compression? On type 2, I propose that | the same mechanism be used. Do you mean it looks like this.. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CCP Protocol Indentifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |x| Length of Compressed Data | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed Data.... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC - 16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Where x is the bit which determines whether the data is compressed or not? And the length field is a 15 bit unsigned field? Ok with me. | Any other pending comments? Shouldn't your "Assigned Number" Reference refer to RFC 1340 instead of RFC 1060? Also, didn't Timo Raita come up with the Predictor Algorithm at the ACM SIG Conference, New Orleans, 1987 ? Perhaps you should reference or acknowledge that. -Thomas From owner-ppp-comp Tue Sep 21 15:04:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofFoU-0000Afa; Tue, 21 Sep 93 15:03 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Tue, 21 Sep 93 12:13:52 EDT Message-ID: <1397.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Any other pending comments? > Yeah, I asked that you split out the Predictor from the CCP draft. That gets us away from having actual algorithms included with the negotiation mechanism. And allows those fights to be separated. Also, if Predictor is supposed to be our default, we only want one. Pick one, forget the other. The last time I looked, you hadn't assigned numbers to other algorithms. Each algorithm needs a number. We shouldn't rely on OUIs except in exceptional circumstances. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Sep 22 12:11:29 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofZY6-0000iGa; Wed, 22 Sep 93 12:08 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 12:02:59 TZ Message-ID: <9309221907.AB00626@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Any other pending comments? > Has anyone thought about encryption? If compression is negotiated, encryption will have to occur AFTER compression otherwise compression won't work worth beans. Futhermore, encryption is largely independent of the compression technique used, although not necessarily. That is, if compression uses LAPB and the data gets resent, you probably won't want to re-encrypt the data. Also, some frames may not be compressed, but they should still be encrypted. Anyway, compression and encryption still go hand in hand. What's worse, encryption is also tied to CHAP authentication because that's how both ends SHOULD determine what key to use to encrypt the data. So I ask, should we start a draft for encryption? Or perhaps, we should include a section about encryption in the Compression CP draft? -Thomas From owner-ppp-comp Wed Sep 22 13:11:30 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofaWy-0000h4a; Wed, 22 Sep 93 13:11 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 1993 16:09:08 -0400 (EDT) Message-ID: <9309222009.AA01836@donut.gandalf.ca> References: <<9309221907.AB00626@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Has anyone thought about encryption? If compression is negotiated, > encryption will have to occur AFTER compression otherwise compression > won't work worth beans. Good point. There seems to be an increasing demand for ORDERING of NCP layers. Compression Type A needs LAPB, Multilink this can work with LAPB this way, and that way without LAPB, ... The list could be endless. Up until now, NCPs could theoretically be negotiated in parallel. > Futhermore, encryption is largely independent > of the compression technique used, although not necessarily. That is, > if compression uses LAPB and the data gets resent, you probably won't > want to re-encrypt the data. It's really independent of the compression, but possibly from your example dependent on LAPB. The encryption method would be dependent on whether reliable delivery is present. > Anyway, compression and encryption still go hand in hand. What's worse, > encryption is also tied to CHAP authentication because that's how both > ends SHOULD determine what key to use to encrypt the data. No. IMHO Authentication and encryption are two separate techniques. But then again, I'm no encryption expert. > So I ask, should we start a draft for encryption? Or perhaps, we should > include a section about encryption in the Compression CP draft? Yes separate draft. Yes a section in CCP, but not specific to encryption. The CCP draft should (does?) specify any NCPs which must be negotiated prior to compression working. Encryption can be negotiated later, but may depend on LAPB. Then again, does encryption belong at the link layer or multilink layer? -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Wed Sep 22 13:23:33 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofaih-0000jda; Wed, 22 Sep 93 13:23 PDT Sender: owner-ppp-comp X-Path: MorningStar.Com!kim From: Kim Toms To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 16:23:10 -0400 Message-ID: <9309222023.AA15787@volitans.MorningStar.Com> References: <<9309221907.AB00626@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > So I ask, should we start a draft for encryption? Or perhaps, we should > include a section about encryption in the Compression CP draft? Several people have been thinking about encryption. One of the problems with encryption is that currently there is no standard for PPP over TCP. This would be helpfull because then you could run end-to-end encryption over the Internet instead of just over your local phone connection. One of the other reasons for PPP over TCP is so that traffic like Bridging or OSI can be carried over IP internets without the IP network needing to know anything about the traffic it's carrying. Our product currently implements PPP over TCP by treating the TCP as though it were a normal async connection. From owner-ppp-comp Wed Sep 22 13:28:16 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofanH-0000fxa; Wed, 22 Sep 93 13:28 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 1993 13:27:46 PDT Message-ID: <9309222027.AA20667@va.SJF.Novell.COM> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Sep 22, 12:02, Thomas Dimitri wrote: } } So I ask, should we start a draft for encryption? Or perhaps, we should } include a section about encryption in the Compression CP draft? } A separate draft for encryption would be required, IMHO. -- From owner-ppp-comp Wed Sep 22 14:14:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofbUz-00008Va; Wed, 22 Sep 93 14:13 PDT Sender: owner-ppp-comp X-Path: sgw.xyplex.com!sgw From: sgw@sgw.xyplex.com (Scott Wasson) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 15:47:46 EDT Message-ID: <9309221947.AA24218@eng.xyplex.com> References: <<9309221907.AB00626@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk According to Thomas Dimitri: > > > Any other pending comments? > > > > Has anyone thought about encryption? If compression is negotiated, > encryption will have to occur AFTER compression otherwise compression > won't work worth beans. Futhermore, encryption is largely independent > of the compression technique used, although not necessarily. That is, > if compression uses LAPB and the data gets resent, you probably won't > want to re-encrypt the data. Also, some frames may not be compressed, > but they should still be encrypted. > > Anyway, compression and encryption still go hand in hand. What's worse, > encryption is also tied to CHAP authentication because that's how both > ends SHOULD determine what key to use to encrypt the data. > Your last conjecture may be flawed: Some encryption algorithms are easier to crack than others. Unless your encryption algorithm is AT LEAST as good as the MD5 algorithm, then it will be relatively easy to crack the encryption key, and thus the CHAP key. +=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+ | Scott G. Wasson sgwasson@eng.xyplex.com | | Xyplex, Internetworking & Media Voice: (508) 952-4746 | | 295 Foster St. Littleton, MA 01460 Fax: (508) 952-4702 | +=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+ From owner-ppp-comp Wed Sep 22 15:12:43 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofcQ5-0000oFa; Wed, 22 Sep 93 15:12 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 15:05:56 TZ Message-ID: <9309222210.AA17569@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Scott Wasson | | According to Thomas Dimitri: | > | > | > Anyway, compression and encryption still go hand in hand. What's worse, | > encryption is also tied to CHAP authentication because that's how both | > ends SHOULD determine what key to use to encrypt the data. | > | | Your last conjecture may be flawed: Some encryption algorithms are | easier to crack than others. Unless your encryption algorithm | is AT LEAST as good as the MD5 algorithm, then it will be relatively | easy to crack the encryption key, and thus the CHAP key. | Good point. That's why you should take the CHAP key (the one which is NOT passed on the wire) and run it through a one-way algorithm and then use that key for encryption. That's what should be used. CHAP is the only mechanism in PPP today which has a "key" that both ends know which never gets sent on the wire. That is why in my mind, encryption is tied to CHAP. BTW, if your encryption is stronger than MD5, you ain't gonna ship your product anywhere because I doubt the NSA will clear it. I agree with Kim that end-end encryption is mucho better, but is there a multi-network layer standard for doing this? Until then, we are probably restricted to only encrypting from PPP peer to PPP peer, once it gets routed on to the LAN all bets are off. Boy, this is beginning to turn into one of those encryption discussions. -Thomas From owner-ppp-comp Wed Sep 22 17:09:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofeFD-00002Ja; Wed, 22 Sep 93 17:09 PDT Sender: owner-ppp-comp X-Path: MorningStar.Com!kim From: Kim Toms To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 19:57:48 -0400 Message-ID: <9309222357.AA13557@remora.MorningStar.Com> References: <<9309222210.AA17569@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Good point. That's why you should take the CHAP key (the one which is > NOT passed on the wire) and run it through a one-way algorithm and then > use that key for encryption. That's what should be used. No, what should be used is the MD5 of the (CHAP challenge concatenated with 2 copies of the CHAP key). That way it will 1) change with each connection, 2) not be related solely to the CHAP key. > I agree with Kim that end-end encryption is mucho better, but is > there a multi-network layer standard for doing this? Currently PPP is defined to work on many different network layers. By running it over TCP, it'll go over even something as primitive as SLIP! > Until then, we are probably restricted to only encrypting from PPP > peer to PPP peer, once it gets routed on to the LAN all bets are off. By doing it over TCP, you have the advantage that it can be routed over an existing internet. > Boy, this is beginning to turn into one of those encryption discussions. Yes. We put together a mailing list after Interop, called "private-ip@morningstar.com". Perhaps we should move there? Send requests to private-ip-request@morningstar.com if you'd like to be added. I've taken the liberty of adding the following folks, since they've contributed to this discussion already: tommyd@microsoft.com (Thomas Dimitri) dcarr@gandalf.ca (Dave Carr) Dave_Rand@Novell.COM (Dave Rand) sgw@sgw.xyplex.com (Scott Wasson) I note that this list (except for me) does not intersect with the existing membership... There is an archive of previous discussions available for anonymous ftp from ftp.morningstar.com:/pub/private-ip/private-ip-archive. From owner-ppp-comp Wed Sep 22 18:04:31 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0off6H-0000mta; Wed, 22 Sep 93 18:04 PDT Sender: owner-ppp-comp X-Path: lloyd.com!brian From: brian@lloyd.com (Brian Lloyd) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 18:03:23 -0700 Message-ID: <9309230103.AA27717@spider.lloyd.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Our product currently implements PPP over TCP by treating the TCP as >though it were a normal async connection. Somehow the thought of PPP over TCP bothers me. Ah well, YAOP (Yet Another Overloaded Protocol). Brian Lloyd, President BP Lloyd & Associates, Inc. brian@lloyd.com 3420 Sudbury Road (916) 676-1147 - voice Cameron Park, CA 95682 (916) 676-3442 - fax From owner-ppp-comp Wed Sep 22 18:29:35 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0offUg-0000p3a; Wed, 22 Sep 93 18:29 PDT Sender: owner-ppp-comp X-Path: MorningStar.Com!kim From: Kim Toms To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 21:28:44 -0400 Message-ID: <9309230128.AA13716@remora.MorningStar.Com> References: <<9309230103.AA27717@spider.lloyd.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > >Our product currently implements PPP over TCP by treating the TCP as > >though it were a normal async connection. > > Somehow the thought of PPP over TCP bothers me. Ah well, YAOP (Yet Another > Overloaded Protocol). I guess you don't know anybody who would like to do bridging across the internet. From owner-ppp-comp Wed Sep 22 19:21:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofgIj-00007Ya; Wed, 22 Sep 93 19:20 PDT Sender: owner-ppp-comp X-Path: lloyd.com!brian From: brian@lloyd.com (Brian Lloyd) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Wed, 22 Sep 93 19:20:32 -0700 Message-ID: <9309230220.AA28222@spider.lloyd.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >> Somehow the thought of PPP over TCP bothers me. Ah well, YAOP (Yet Another >> Overloaded Protocol). > >I guess you don't know anybody who would like to do bridging across the >internet. I don't know anyone who would like to do bridging, period. And those who profess to want to do bridging, I simply refuse to know. ;^) Brian Lloyd, President BP Lloyd & Associates, Inc. brian@lloyd.com 3420 Sudbury Road (916) 676-1147 - voice Cameron Park, CA 95682 (916) 676-3442 - fax From owner-ppp-comp Thu Sep 23 08:13:08 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ofsKb-0000gJa; Thu, 23 Sep 93 08:11 PDT Sender: owner-ppp-comp X-Path: sgw.xyplex.com!sgw From: sgw@sgw.xyplex.com (Scott Wasson) To: ppp-comp@bungi.com Subject: Re: Closure items? (fwd) Date: Thu, 23 Sep 93 10:18:55 EDT Message-ID: <9309231418.AA00142@eng.xyplex.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk According to Kim Toms: > > > I agree with Kim that end-end encryption is mucho better, but is > > there a multi-network layer standard for doing this? > > Currently PPP is defined to work on many different network layers. By > running it over TCP, it'll go over even something as primitive as SLIP! > > > Until then, we are probably restricted to only encrypting from PPP > > peer to PPP peer, once it gets routed on to the LAN all bets are off. > > By doing it over TCP, you have the advantage that it can be routed over > an existing internet. > This is all true, but we were addressing the issues of encryption on a multiprotocol point-to-point link. I believe that although the virtues of end-to-end encryption are certainly valuable, they reside at a higher layer beyond the scope of the PPP WG. I'd like to keep the problem generic to PPP, rather than have the PPP WG trying to solve the problems of [insert every network protocol here] end-to-end encryption in the future. +=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+ | Scott G. Wasson sgwasson@eng.xyplex.com | | Xyplex, Internetworking & Media Voice: (508) 952-4746 | | 295 Foster St. Littleton, MA 01460 Fax: (508) 952-4702 | +=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+ From owner-ppp-comp Thu Sep 23 17:55:08 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0og1R0-0000r0a; Thu, 23 Sep 93 17:54 PDT Sender: owner-ppp-comp X-Path: lloyd.com!brian From: brian@lloyd.com (Brian Lloyd) To: ppp-comp@bungi.com, ppp-comp@bungi.com Subject: Re: Closure items? Date: Thu, 23 Sep 93 17:54:42 -0700 Message-ID: <9309240054.AA07799@spider.lloyd.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I just realized what this discussion on compression/encryption over PPP over TCP reminds me of; the old addage: When all you have is a hammer, everything looks like a nail. Brian Lloyd, President BP Lloyd & Associates, Inc. brian@lloyd.com 3420 Sudbury Road (916) 676-1147 - voice Cameron Park, CA 95682 (916) 676-3442 - fax From owner-ppp-comp Fri Sep 24 07:42:07 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogEJx-0000j3a; Fri, 24 Sep 93 07:40 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 08:39:52 -0600 Message-ID: <9309241439.AA00997@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > "William Allen Simpson" writes: > > Any other pending comments? > > > Yeah, I asked that you split out the Predictor from the CCP draft. > That gets us away from having actual algorithms included with > the negotiation mechanism. And allows those fights to be separated. > > Also, if Predictor is supposed to be our default, we only want one. > Pick one, forget the other. > > The last time I looked, you hadn't assigned numbers to other algorithms. > Each algorithm needs a number. We shouldn't rely on OUIs except in > exceptional circumstances. > > Bill.Simpson@um.cc.umich.edu I think that the Predictor code belongs in the PPP compression RFC for the same compelling reasons that the ASYNC CRC code belongs in one of the other PPP RFC's and not in its own. No one who reads the compression RFC will fail to also read the Predictor RFC, and conversely. There is no justification for separating them, beyond making one an appendix in the other. The new scheme of 27 different PPP RFC's is a mistake. I am continually arguing with people about which of 1331-1334 concerns what, and continually having to point people at titles. (So far, I've won all of those arguments, but that won't last.) No one seems able to keep straight which of 1331-1334 concerns what. In the near future, when we will have 1134,1171,1331,1332,1333,1334,1331Abis,1331Bbis,1331Cbis, 1332bis,1333bis,1334bis,compress, and many others I don't pay attention to, we'll start to look worse than ITU/CCITT. It wouldn't be so bad if they were all bound together as separate chapters in the same book, but they are not. Do not object that the RFC number does not matter. Customers site RFC's by number instead of title in request's for quotes, request's for proposals, and contracts. What do you do when they refer to "RFC 1333" when you know they mean "RFC 1334," but include no text that would let you respond in a way that would help them? So that by rights you have to give the wrong answer, no matter what answer you give? This happened to me this morning. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Sep 24 07:48:49 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogEQv-0000wua; Fri, 24 Sep 93 07:47 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 08:46:55 -0600 Message-ID: <9309241446.AA01165@rhyolite.wpd.sgi.com> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Thomas Dimitri writes: > | From: Scott Wasson > | > | According to Thomas Dimitri: > | > > | > > | > Anyway, compression and encryption still go hand in hand. What's worse, > | > encryption is also tied to CHAP authentication because that's how both > | > ends SHOULD determine what key to use to encrypt the data. > | > > | > | Your last conjecture may be flawed: Some encryption algorithms are > | easier to crack than others. Unless your encryption algorithm > | is AT LEAST as good as the MD5 algorithm, then it will be relatively > | easy to crack the encryption key, and thus the CHAP key. > | > > Good point. That's why you should take the CHAP key (the one which is > NOT passed on the wire) and run it through a one-way algorithm and then > use that key for encryption. That's what should be used. CHAP is the > only mechanism in PPP today which has a "key" that both ends know > which never gets sent on the wire. That is why in my mind, encryption > is tied to CHAP. > > BTW, if your encryption is stronger than MD5, you ain't gonna ship > your product anywhere because I doubt the NSA will clear it. > > I agree with Kim that end-end encryption is mucho better, but is > there a multi-network layer standard for doing this? Until then, > we are probably restricted to only encrypting from PPP peer to > PPP peer, once it gets routed on to the LAN all bets are off. > > Boy, this is beginning to turn into one of those encryption discussions. > > -Thomas Encryption and authentication are entirely different and separate ideas. Encryption tries to keep things secret while auththenication tries to ensure that you know who you are talking to. There is no universally good reason to tie encryption and authentication together and some reasons to separate them. There is no universally good reason to tie either PAP or CHAP to link-level stream encryption or packet encryption. There are good reasons to separate them. MD5 is not an "encryption algorithm". It is a hard-to-reverse checksummer commonly used for signing, a form of authentication, but like most such, can also be used for encryption. There is no simple way to compare the relative strengths of encryption algorithms. Talk of "rounds" only lets you compare schemes with similar computations for each round. Talk of "years on a Cray" is interesting but imprecise. The condition "stronger than MD5" is at best technically imprecise. Encyprtion and compression are in practice connected because useful encryption necessarily raises the entropy of a stream, foiling the efforts of your compression algorithm. There are plenty of end-to-end encryption standards, efforts, and works-in-progress. There are also plenty of end-to-end authentication standards, efforts, and works-in-progress. The PPP working group(s) is (are) not the place for end-to-end encryption or authentication discussions. It might make sense to talk about link-level PPP encryption, but in most systems, the time and effort that would be spent implementing link-level encryption would be better spent on end-to-end encryption, to fix things like telnet and ftp passwords. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Sep 24 07:57:44 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogEZK-0000uNa; Fri, 24 Sep 93 07:56 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 08:55:10 -0600 Message-ID: <9309241455.AA01373@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Kim Toms writes: > > So I ask, should we start a draft for encryption? Or perhaps, we should > > include a section about encryption in the Compression CP draft? > > Several people have been thinking about encryption. One of the problems > with encryption is that currently there is no standard for PPP over TCP. > This would be helpfull because then you could run end-to-end encryption > over the Internet instead of just over your local phone connection. > > One of the other reasons for PPP over TCP is so that traffic like > Bridging or OSI can be carried over IP internets without the IP network > needing to know anything about the traffic it's carrying. > > Our product currently implements PPP over TCP by treating the TCP as > though it were a normal async connection. URGHHHHHHHHHHHHHHH! NO! PLEAESE! Not in the PPP set of standards. PPP is technically the wrong way to encapsulate other packets over TCP. Why in the world would you have all of the PPP headers when running over TCP? Why in in the world would you do all of the ASYNC escaping and CRC mechanisms that is intended and required for links that lose or corrupt bytes? Does your TCP drop or corrupt bytes? Instead, simply put a length and a type in front of your packets and send them down your TCP pipe. Or take raw Ethernet packets, strip preamble and perhaps FCS, prepend a length and send them over TCP. Or best, when your halves of bridges are only connected via IP, simply jam raw packets into UDP/IP packets. The next thing you know, someone will want to run IP, Appletalk, or IPX over bridged ethernets packets over PPP with LABP and TCP over PPP with compression and LAPB over v.42! There is no more need for a TCP over PPP IETF standard than there is for a UUCP over TCP standard. Just do it. (After typing "TCP over PPP" several times I feel a need to go wash my hands with lye.) Which "product" and vendor is this? Something from Microsoft or from Morningstar? We all need to know to avoid buying it or its brethern. Try not to take this flame too personally. I know that salescritters and managers who do refuse to realize they do not understand can have incredibly stupid ideas and make implausibly bad decisions. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Sep 24 11:23:16 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogHmM-00018ia; Fri, 24 Sep 93 11:22 PDT Sender: owner-ppp-comp X-Path: fcr.com!brad From: Brad Parker To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 1993 11:38:49 -0400 Message-ID: <9309241539.AA10051@stemwinder.fcr.com> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk In message <9309241455.AA01373@rhyolite.wpd.sgi.com>, Vernon Schryver writes: >The next thing you know, someone will want to run IP, Appletalk, or IPX >over bridged ethernets packets over PPP with LABP and TCP over PPP with >compression and LAPB over v.42! too late. ;-) (I run Appletalk Remote Access over tcp with v.42 compression all the time ;-) works great. it's not hard on the internet (due to tcp's slow start and back off characteristics). nice flow control. easy to set up. ;-) -brad [ sorry for the noise. i could not resist. ] From owner-ppp-comp Fri Sep 24 12:36:24 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogIuk-0001Cga; Fri, 24 Sep 93 12:34 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 1993 12:32:45 -0800 Message-ID: <9309241933.AA03547@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >So I ask, should we start a draft for encryption? Or perhaps, we should >include a section about encryption in the Compression CP draft? If you want to start a draft for encryption, go ahead. I have three principal comments: First, I noted a while back that the difference between compression and encryption was a bit murky in my mind; both are re-encoding a data stream in a form that only the sender and the receiver are expected to understand at any given time - the big differences being the re-encoding algorithm and "code book" used. Second, making that observation in the presence of a COCOM lawyer, making that comment in an RFC that such a lawyer might reference, could have disastrous consequences for the compression industry (small as it is :^) Third, I mentioned to a DCA official once that it would be rather straightforward for me to build a card that put a DMA driven DES chip between the memory and the serial chip, but that it would be harder for me to put the DES chip between the serial chip and the line drivers due to the timing behaviors of low level signalling protocols. The big difference would be that there would be flags in the data stream, and that CRCs would be on the encrypted data, not the decrupted data. He indicated that - flag streams could be detected (and therefore activity measured, which is of military value even without the decoding of the messages), and - there is a clear demarcation between clear and encrypted data, the start of which is fairly predictable and therefore a clue to a code breaker The upshot was that DCA did not consider that a viable encryption product. That probably doesn't affect the commercial market (people are encrypting on LANs inside an IP header, which suffers from the above), but it's something to consider. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Fri Sep 24 12:51:01 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogJ93-00015Za; Fri, 24 Sep 93 12:49 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 11:01:09 TZ Message-ID: <9309241948.AA04281@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Vernon Schryver | > Thomas Dimitri writes: | > | From: Scott Wasson | > | | > | According to Thomas Dimitri: | > | > | > | > | > | > Anyway, compression and encryption still go hand in hand. What's worse, | > | > encryption is also tied to CHAP authentication because that's how both | > | > ends SHOULD determine what key to use to encrypt the data. | > | > | > | | > | Your last conjecture may be flawed: Some encryption algorithms are | > | easier to crack than others. Unless your encryption algorithm | > | is AT LEAST as good as the MD5 algorithm, then it will be relatively | > | easy to crack the encryption key, and thus the CHAP key. | > | | > | > Good point. That's why you should take the CHAP key (the one which is | > NOT passed on the wire) and run it through a one-way algorithm and then | > use that key for encryption. That's what should be used. CHAP is the read this part... | > only mechanism in PPP today which has a "key" that both ends know | > which never gets sent on the wire. That is why in my mind, encryption | > is tied to CHAP. ok, stop reading. | > | > -Thomas | | Encryption and authentication are entirely different and separate | ideas. Encryption tries to keep things secret while auththenication | tries to ensure that you know who you are talking to. There is no | universally good reason to tie encryption and authentication together | and some reasons to separate them. Of course they are different. They only reason they are tied is the "key". You need a way to agree on a "key" that was NOT sent over the wire and can NOT be derived easily from what went over the wire. It's the "key" I tell you. | There is no universally good reason to tie either PAP or CHAP to | link-level stream encryption or packet encryption. There are good | reasons to separate them. There is no universally good reason to do anything. | MD5 is not an "encryption algorithm". It is a hard-to-reverse | checksummer commonly used for signing, a form of authentication, but | like most such, can also be used for encryption. When did I say use MD5? Bleck, I was thinking of using RC4. | There is no simple way to compare the relative strengths of encryption | algorithms. Talk of "rounds" only lets you compare schemes with | similar computations for each round. Talk of "years on a Cray" is | interesting but imprecise. The condition "stronger than MD5" is at | best technically imprecise. The way it is done is by encyption experts (I am not at all one) is by reviewing and attacking the algorithm. Peer review. How long it takes to crack it. Stuff like that. Sure it's imprecise, but it's a good notion. RC4, by the way, is weak compared to MD5. If you want to argue that point with an encryption guru, I can set you up. | Encyprtion and compression are in practice connected because useful | encryption necessarily raises the entropy of a stream, foiling the | efforts of your compression algorithm. Agreed. | There are plenty of end-to-end encryption standards, efforts, and | works-in-progress. There are also plenty of end-to-end authentication | standards, efforts, and works-in-progress. The PPP working group(s) is | (are) not the place for end-to-end encryption or authentication | discussions. It might make sense to talk about link-level PPP | encryption, but in most systems, the time and effort that would be | spent implementing link-level encryption would be better spent on | end-to-end encryption, to fix things like telnet and ftp passwords. The only reason I bring it up is because you need to do encryption after compression and if you do encryption, there should be a way to determine the "key" to use to encrypt the data. Since PPP already has a way of doing this (CHAP) I thought it would be fitting to use that same scheme and not invent another one. That's all. RC4 encryption is really easy to implement - it is a no brainer. The effort put into it would be far less then fixing telnet and ftp. But I absolutely agree that end to end encryption is better. The problem is, end to end encryption is typically tied to network layers and I'm thinking more along the lines of an easy way to do it in PPP which encompasses everything that's get sent out -- like compression does. Nothing revolutionary, but probably worth it I'm not trying to reinvent the wheel, just trying to come up with a simple way to encrypt PPP data because it's easy for me to lock up my PPP server in a room and put it on a secure net, but it's hard for me to secure my phone line from my house or hotel. --Thomas | Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Sep 24 13:39:04 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogJtW-0000t9a; Fri, 24 Sep 93 13:37 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 1993 15:58:33 -0400 (EDT) Message-ID: <9309241958.AA02557@donut.gandalf.ca> References: <<9309241933.AA03547@fennel.acc.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > - flag streams could be detected (and therefore activity measured, > which is of military value even without the decoding of the messages), > and > > - there is a clear demarcation between clear and encrypted data, the > start of which is fairly predictable and therefore a clue to a code > breaker There are companies (at least one that I know of) that make encrypted Ethernets. On the LAN, all stations send the same LENGTH packets, and at least one station generates a constant load so that you cannot ditinguish an active LAN from an inactive LAN. On a WAN, this would be fairly trivial to implement, and if the, say for example, PPP Multilink fragment were small enough, would only add a small latency to a real transfer. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Fri Sep 24 13:39:37 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogJtW-00019Oa; Fri, 24 Sep 93 13:37 PDT Sender: owner-ppp-comp X-Path: MorningStar.Com!kim From: Kim Toms To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 16:36:20 -0400 Message-ID: <9309242036.AA07594@volitans.MorningStar.Com> References: <<9309241446.AA01165@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I think I just read an argument that said that encryption shouldn't be put into PPP because it's being put into the upper layers. Now, encryption increases the entropy of the data stream, so that compression can't be done. So, either compression has to be done above encryption or compression is useless. The people wanting to put encryption into PPP are wanting to do that because it's below compression (at least partially). Now, if the correct place to put encryption is into the upper layers, why is that an inappropriate place to put compression, such that we're putting it into PPP? Just think, the upper layers would have more knowledge of the data stream, and therefore be able to do a better job... From owner-ppp-comp Fri Sep 24 15:12:42 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogLMM-0001Gua; Fri, 24 Sep 93 15:11 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: More questions Date: Fri, 24 Sep 1993 15:10:55 PDT Message-ID: <9309242210.AA14391@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On the LAPB document, we don't really say much about T1-T3/N1-N5. Should we? Defer to V.42? As well, we need a companion document, or a preface, that describes the relationship of LAPB, Compression and Multilink. Ideas? I want to release these documents (after one more round here), next week for general consumption, so time is running out. Thanks! -- From owner-ppp-comp Fri Sep 24 16:24:35 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogMU4-0000pda; Fri, 24 Sep 93 16:23 PDT Sender: owner-ppp-comp X-Path: rhyolite.wpd.sgi.com!vjs From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 93 17:22:43 -0600 Message-ID: <9309242322.AA04942@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk kim@MorningStar.Com wrote: > I think I just read an argument that said that encryption shouldn't be > put into PPP because it's being put into the upper layers. Now, > encryption increases the entropy of the data stream, so that compression > can't be done. So, either compression has to be done above encryption > or compression is useless. > > The people wanting to put encryption into PPP are wanting to do that > because it's below compression (at least partially). > > Now, if the correct place to put encryption is into the upper layers, > why is that an inappropriate place to put compression, such that we're > putting it into PPP? Just think, the upper layers would have more > knowledge of the data stream, and therefore be able to do a better job... Let's not get distracted from CCP.... There is no single "correct place to put encryption" any more than the authentication mechanism should necessarily related to the session encryption key (at whatever layer(s)). For example, it makes sense to compress and then encrypt inside the FTP client and server programs. People have been talking about doing compression inside FTP for at least 6 years in my hearing, and in more recent years defacto standards have evolved around freely distributable implementations (in other words, the *.Z hack). It makes sense to run such compressed-FTP or compressed-encrypted-FTP bytes over a PPP link that itself compresses. That the PPP link compression will be not effective on those bytes is no more interesting or surprising that what will happen to a significant number of TCP/IP/PPP bytes. (Think of pre-compressed netnews.) That some PPP packets will have high entropy and not be friendly to any particular CCP compression algotithm is no more than a design constraint on the compression mechanism. That's why Predictor now has the "didn't compress" bit. For example, even if the data of an NFS/RPC-XDR/UDP/IP packet is encrypted, there are about 100 bytes/packet of headers that could be easily compressed. As I understand some common encryption practices, the initial chit-chat to pick the session key (which might be viewed as authentication and sometimes really is authentication) uses different keys than the subsequent session key, if only because the initial chit-chat uses methods that are too slow for a significant number of data bits. Consider CLIPPER and RSA. It might be that the CHAP shared secrets might support a useful, perhaps slow, link encryption scheme, but it seems clear that a real PPP encryption standard would have to allow as much or more flexibility in picking encryption algorithms as CCP allows for compression. Besides the obvious choices such as the algorithm from a list starting with obvious choices like one-time-pads, DES, strong random number generators, triple-DES, and even CLIPPER, you would need options for defending against traffic analysis (if you pay per packet, you might not care enough to send much chaff). Then there are the hard issues, such as key distribution. Would you wnat to sign packets? CCP compression is not all that similar to useful encryption. One difference is that the "key" is usually only about 3 bytes long, and rarely more than 4 bytes. The "shared codebook" aspect of compression applies just as much to layers below PPP. Consider the "cyphers" and "symbols" in high speed link stuff that ensures the right number of transitions per second. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Sep 24 17:29:59 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ogNVL-0001FNa; Fri, 24 Sep 93 17:28 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: Closure items? Date: Fri, 24 Sep 1993 17:28:00 -0800 Message-ID: <9309250028.AB10062@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Now, if the correct place to put encryption is into the upper layers, >why is that an inappropriate place to put compression, such that we're >putting it into PPP? Just think, the upper layers would have more >knowledge of the data stream, and therefore be able to do a better job... I don't know that anyone is arguing against putting it in the upper layers. The argument is (this statistic quoted from an unrelated note on another mailing list this morning or yesterday) that over 2/3 of traffic on a typical internet is NOT compressed, and therefore an effective bit rate improvement can be gained by compressing data at the link. NSFnet once commented that 1/4 of their traffic was DNS queries and replies. They also said that another 1/4 was telnet/rlogin traffic, and anoter 1/4 was mail. This mailgram is going in the clear, ... ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Mon Oct 4 18:10:47 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ok0uM-0000YWa; Mon, 4 Oct 93 18:09 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: Last chance for LAPB document Date: Mon, 4 Oct 93 16:38:04 PDT Message-ID: <9310042338.AA15292@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Network Working Group D Rand Internet Draft Novell Expires in six months October 1993 PPP Reliable Transmission draft-ietf-pppext-reliable-xx.txt Status of this Memo This document is the product of the Point-to-Point Protocol Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the ietf-ppp@ucdavis.edu mailing list. Distribution of this memo is unlimited. This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method for transporting multi-protocol datagrams over point-to-point links. This document defines a method for negotiating and using Numbered- Mode, as defined by ISO 7776 [2], to provide a reliable serial link. Dave Rand expires in six months FORMFEED[Page i] RFC DRAFT PPP Reliable Transmission October 1993 1. Introduction By default, PPP packets over HDLC framed links consist of "connectionless" datagrams. If reliable transmission over the HDLC link is desired, the implementation MUST specify the Numbered-Mode Configuration Option during Link Establishment phase. Generally, serial link reliability is not a major issue. The architecture of protocols used in datagram networking presume best- effort non-sequential delivery. When errors are detected, datagrams are discarded. However, in certain circumstances, it is advisable to provide a reliable link, at least for a subset of the messages. The most obvious case is when the link is compressed. Since the dictionary is recovered from the compressed data stream, and a lost datagram corrupts the dictionary, datagrams must not be lost. Not all compression types will require a reliable data stream, since the cost to detect and reset a corrupt dictionary is small. The ISO 7776 LAPB can be used guarantee delivery. This is referred to in this document as "Numbered Mode" to distinguish it from the use of "Unnumbered Information", which is standard PPP framing practice. Where multiple parallel links are used to emulate a single link of higher speed, Bridged traffic, Source Routed traffic, and traffic subjected to Van Jacobsen TCP/IP header compression must be delivered to the higher layer in a certain sequence. However, the fact of the links being relatively asynchronous makes traffic ordering uncertain. The ISO 7776 Multi-Link Procedure MAY be used to restore order. Implementation of the ISO Multi-Link Procedure is deprecated. It is recommended that the PPP multilink procedure [4] be used instead. Dave Rand expires in six months FORMFEED[Page 1] RFC DRAFT PPP Reliable Transmission October 1993 2. Physical Layer Requirements PPP Reliable Transmission imposes the same requirements that are described in "PPP in HDLC Framing" [3], with the following exceptions. Control Signals While PPP does not normally require the use of control signals, implementation of Numbered-Mode LAPB or LAPD requires the provision of control signals, which indicate when the link has become connected or disconnected. These in turn provide the Up and Down events to the LCP state machine. 3. The Data Link Layer Numbered-Mode affects only the Address and Control fields. The remainder of the frame conforms to the framing in use for PPP. The Address Field of the frame MUST take the value announced in the Numbered-Mode Configuration Option, and the Control Field MAY take any value valid in ISO 7776. Once the link enters Numbered-Mode, Numbered-Mode MUST be used on all frames, as some implementations do not support the use of the Unnumbered-Information control field or the use of the All-Stations address intermixed with Numbered-Mode frames. 3.1. Frame Format The following frame format is valid under Numbered-Mode. The fields are transmitted from left to right. Numbered Mode +----------+----------+----------+ | Flag | Address | Control | | 01111110 |1-2 octets|1-2 octets| +----------+----------+----------+ +----------+-------------+---------+ | Protocol | Information | Padding | |1-2 octets| * | * | +----------+-------------+---------+ +----------+----------+----------------- | FCS | Flag | Inter-frame Fill | 16 bits | 01111110 | or next Address +----------+----------+----------------- Dave Rand expires in six months FORMFEED[Page 2] RFC DRAFT PPP Reliable Transmission October 1993 The Protocol, Information and Padding fields are described in the Point-to-Point Protocol Encapsulation [1]. The FCS and Flag Sequence fields are described in "PPP in HDLC Framing" [3]. Dave Rand expires in six months FORMFEED[Page 3] RFC DRAFT PPP Reliable Transmission October 1993 4. Configuration Option Format Description The LCP Numbered-Mode Configuration Option negotiates the use of Numbered-Mode on the link. By default or ultimate disagreement, Unnumbered-Mode is used. A summary of the Numbered-Mode Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Window | Address... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type TBD (11) Length >= 4 Window A value between 1 and 127. This indicates the number of frames the receiver will buffer, which is the maximum number that the sender should send without receiving an acknowledgement. If window < 8, then modulo 8 sequencing is used on the link. Otherwise, modulo 128 sequencing is used. It is conceivable and legal that differing window values might be announced. However, it is not permitted for one system to use modulo 8 sequencing and the other to use modulo 128. Therefore, the rule is: a Configure-Nak may reduce the window but may not increase it. Address An HDLC Address as specified in ISO 3309. ISO 7776 specifies four of the possible values: 1 and 3 for single link operation, 7 and 15 for the Multi-Link Procedure. Other values consistent with ISO 3309 are considered legal. Implementation of the Multi-Link Procedure is optional; A Dave Rand expires in six months FORMFEED[Page 4] RFC DRAFT PPP Reliable Transmission October 1993 Configure-Nak may therefore force a change from MLP to single link mode, but not the reverse. Should the address be zero upon receipt, the receiver MUST Configure-Nak with an appropriate address. If both peers send address zero, the system advertising the numerically smaller window will select the smaller address. If both windows are the same size, a random choice MUST be made; when good sources of randomness are used, the link will converge in a reasonable time. 5. Numbered-Mode Operation When using the Numbered-Mode, each link is established in the usual manner for the type of link. The Numbered-Mode Configuration Option is negotiated, the Magic-Number Configuration Option MUST also be negotiated, and the Address-and-Control-Field-Compression Configuration Option MUST NOT be negotiated. Following the successful negotiation of the Numbered-Mode Configuration Option during LCP Link Establishment phase, the system with the numerically smaller Magic-Number will send a SABM or SABM(E), and the other will respond with a UA. In the event that either the SABM or UA is lost, this exchange may be repeated according to the same parameters as the configuration exchange itself, using the Restart Timer and counter values. Authentication, Link Quality Determination, and NCP Configuration follow this step. Once the link has been established with Numbered-Mode, when re- negotiation of link configuration occurs, the entire re-negotiation MUST be conducted in Numbered-Mode. If the Numbered-Mode Configuration Option is not successfully re-negotiated, the link reverts to Unnumbered-Information operation prior to Authentication, Link Quality Determination, and NCP Configuration. When an implementation which is capable of Numbered-Mode, and is not currently configured for Numbered-Mode operation, detects a frame which has a correct FCS but does not have a UI Control octet, the implementation MUST send a DM message, immediately followed by a LCP Configure-Request. When an implementation which is currently configured for Numbered- Mode operation receives a DM message, it MUST revert to Unnumbered- Information operation, and immediately send a LCP Configure-Request. Dave Rand expires in six months FORMFEED[Page 5] RFC DRAFT PPP Reliable Transmission October 1993 5.1. Single Link When Network-Layer packets are sent over a single link, the packets are encapsulated in the following order: +----------+ +----------+ +----------+ | | | | | Numbered | | Header |-->| Data |-->| Mode |--> link | Compress | | Compress | | Header | +----------+ +----------+ +----------+ 5.2. Inverse Multiplexing Since sending several connections over a single link is often called "multiplexing", sending packets from a single connection over multiple parallel links is sometimes called "inverse-multiplexing". By default, PPP performs no special processing for such links. Each link is established and terminated independently, negotiates its own configuration options, and may have different combinations of such options as ACCM, Protocol Field Compression and IP-Address. This facilitates using the links simultaneously over dissimilar media, such as 56K sync with async backup. Every link in a single machine MUST have different Magic Numbers, and each end of every link between two peers SHOULD have Magic Numbers which are unique to those peers. This protects against patch-panel errors in addition to looped-back links. The distribution to each link is controlled by higher level routing mechanisms. When Network-Layer specific compression techniques (such as Van Jacobsen Compression) rely on sequential delivery, without Multi-Link Procedure support such compression MUST be applied on a link by link basis. +----------+ +----------+ +----------+ | | | | | Numbered | +--->| Header |-->| Data |-->| Mode |--> link 1 | | Compress | | Compress | | Header | +--------------+ +----------+ +----------+ +----------+ | Distribution | +--------------+ +----------+ +----------+ +----------+ | | | | | | Numbered | +--->| Header |-->| Data |-->| Mode |--> link 2 | Compress | | Compress | | Header | +----------+ +----------+ +----------+ Dave Rand expires in six months FORMFEED[Page 6] RFC DRAFT PPP Reliable Transmission October 1993 5.3. Using Multi-Link Procedure This document does not offer a standard for ISO Multi-Link, but does offer a method for agreeing on the addressing scheme usable with Multi-Link. A sample implementation is shown below. Implementation of Multi-Link is not required. When using the ISO 7776 Multi-Link Procedure, each link is established as described above. In addition, the Numbered-Mode Configuration Option is negotiated with appropriate addresses for the Multi-Link Procedure. The distribution to each link is controlled by the Multi-Link Procedure, as is the recovery of sequence in the receiving system. +---> link 1 +----------+ +----------+ +----------+ | | | | | | Multi | +--------------+ | Header |-->| Data |-->| Link |-->| Distribution | | Compress | | Compress | | Procedure| +--------------+ +----------+ +----------+ +----------+ | +---> link 2 Dave Rand expires in six months FORMFEED[Page 7] RFC DRAFT PPP Reliable Transmission October 1993 5.4. LAPB Parameter defaults The following guidelines specify the default values of LAPB configurable parameters. Timer T1 Timer T1 is the maximum time permitted before a retransmission is started, as a result of no response to a transmitted I frame. This value must be greater than time required for a maximum sized frame to be sent and received by the other side of the link, and for a response to be generated for the frame. This can and should be adapted to in a dynamic fashion, in response to the measured round trip time delay of the link at the LAPB level. In the event that the system cannot determine the round trip time of the link, this value should be set to twice the bit rate of the link, divided by the maximum number of bits per frame. For example, on a 14,400 BPS link, with a maximum frame size of 8000 bits (1000 octects), the T1 value should be set to 3.6 seconds. Timer T3 Timer T3 gives an indication of the idle state of the link. Its value must be greater than the T1 value. Maximum number of attempts to complete a transmission, N2 Parameter N2 gives the maximum number of retransmission attempts for a given frame. If this value is exceeded, the link should be taken down. The default value for parameter N2 should be 10. Dave Rand expires in six months FORMFEED[Page 8] RFC DRAFT PPP Reliable Transmission October 1993 Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W. A., "The Point-to-Point Protocol (PPP)", work in progress. [2] ISO 7776, Information Processing Systems - Data Communication - High Level Data Link Control Procedures - Description of the X.25 LAPB-Compatible DTE Data Link Procedures [3] Simpson, W. A., "PPP in HDLC Framing", work in progress. [4] Sklower, K., "PPP MultiLink Procedure", work in progress. Acknowledgments Fred Baker was the original author of this document. Bill Simpson contributed materially to the document. Dave Rand expires in six months FORMFEED[Page 9] RFC DRAFT PPP Reliable Transmission October 1993 Chair's Address The working group can be contacted via the current chair: Fred Baker Advanced Computer Communications 315 Bollay Drive Santa Barbara, California 93117 EMail: fbaker@acc.com Author's Address Questions about this memo can also be directed to: Dave Rand 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand expires in six months FORMFEED[Page 10] RFC DRAFT PPP Reliable Transmission October 1993 Table of Contents 1. Introduction .......................................... 1 2. Physical Layer Requirements ........................... 2 3. The Data Link Layer ................................... 2 3.1 Frame Format .................................... 2 4. Configuration Option Format ........................... 4 5. Numbered-Mode Operation ............................... 5 5.1 Single Link ..................................... 6 5.2 Inverse Multiplexing ............................ 6 5.3 Using Multi-Link Procedure ...................... 7 5.4 LAPB Parameter defaults ......................... 8 SECURITY CONSIDERATIONS ...................................... 9 REFERENCES ................................................... 9 ACKNOWLEDGEMENTS ............................................. 9 CHAIR'S ADDRESS .............................................. 10 AUTHOR'S ADDRESS ............................................. 10 Dave Rand expires in six months FORMFEED[Page ii] From owner-ppp-comp Tue Oct 5 12:34:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0okI8A-0000Bsa; Tue, 5 Oct 93 12:33 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Last chance for LAPB document Date: Tue, 5 Oct 93 14:44:24 EDT Message-ID: <1465.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk You need to run the sed script (as specified in the header of the nroff) to get the page breaks. You can get a copy of the script from ftp.morningstar.com:pub/ppp-wg-drafts/fixdraft.sed Copy of minor nits: Sometimes you only have one space between sentences. If you always start every sentence on a new line, nroff will take care of this for you. And I would indent the Timer T1, etc sections with .RS .RE pairs. I would say: Timer T1 Timer T1 specifies the time to send a retransmission when there has been no response to a transmitted I frame. This value must ^^ be greater than the time required for a maximum sized frame to ^^^ be received by the other side of the link, and for a response to ^ be generated for the frame. This time SHOULD be determined ^^^^^^^^^^^^^^^^^^^^ dynamically, based on the measured round trip time delay of the ^^^^^^^^^^^ ^^^^^^^^ link. In the event that the system cannot determine the round ^^^ trip time of the link, this value SHOULD be set to twice the bit ^^^^^^ rate of the link, divided by the maximum number of bits per frame, plus 100 milliseconds for processing. For example, on a ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 14,400 bps link, with a maximum frame size of 8000 bits (1000 ^^^ octets), the T1 value would be set to 3.7 seconds. ^ Maximum number of attempts to complete a transmission, N2 Parameter N2 gives the maximum number of retransmission attempts for a given frame. If this value is exceeded, the link SHOULD be ^^^^^^ terminated. The default value for parameter N2 SHOULD be 10. ^^^^^^^^^^ ^^^^^^ Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Oct 5 12:46:40 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0okIKG-0000CZa; Tue, 5 Oct 93 12:45 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Last chance for LAPB document Date: Tue, 5 Oct 1993 15:43:24 -0400 (EDT) Message-ID: <9310051943.AA08774@donut.gandalf.ca> References: <<9310042338.AA15292@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Dave, looks pretty good. Just a few comments to reflect the current multilink discussions. > Address > > An HDLC Address as specified in ISO 3309. ISO 7776 specifies four > of the possible values: 1 and 3 for single link operation, 7 and > 15 for the Multi-Link Procedure. Other values consistent with ISO > 3309 are considered legal. I'm wondering if ISO multilink being frowned upon is enough. Should we go that extra step and not allow it. It seems having 2 ways to do the same thing should be avoided. I would also like to find out the route that other manufacturers are taking for error-correction. There seems to be a split occuring, those doing it with LAPB and those with multilink. I would like this issue *settled* before giving LAPB my blessing. I haven't had much feedback in the main newsgroup. > Configure-Nak may therefore force a change from MLP to single link > mode, but not the reverse. Same as above. > > 5.4. LAPB Parameter defaults > > The following guidelines specify the default values of LAPB > configurable parameters. > > Parameter N2 gives the maximum number of retransmission attempts > for a given frame. If this value is exceeded, the link should be > taken down. The default value for parameter N2 should be 10. Typically, N2 is set to 3. I propose that as the default. -- Dave Carr | dcarr@gandalf.ca | It's what you learn, Principal Designer | TEL (613) 723-6500 | after you know it all, Gandalf Data Limited | FAX (613) 226-1717 | that counts. From owner-ppp-comp Tue Oct 5 16:25:44 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0okLk3-0000Wma; Tue, 5 Oct 93 16:24 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: internet-drafts@cnri.reston.va.us, ppp-comp@bungi.com Subject: Lapb draft RFC Date: Tue, 5 Oct 93 16:23:28 PDT Message-ID: <9310052323.AA06772@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Network Working Group D Rand Internet Draft Novell Expires in six months October 1993 PPP Reliable Transmission draft-ietf-pppext-reliable-xx.txt Status of this Memo This document is the product of the Point-to-Point Protocol Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the ietf-ppp@ucdavis.edu mailing list. Distribution of this memo is unlimited. This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method for transporting multi-protocol datagrams over point-to-point links. This document defines a method for negotiating and using Numbered- Mode, as defined by ISO 7776 [2], to provide a reliable serial link. Dave Rand expires in six months [Page i] DRAFT PPP Reliable Transmission October 1993 1. Introduction By default, PPP packets over HDLC framed links consist of "connectionless" datagrams. If reliable transmission over the HDLC link is desired, the implementation MUST specify the Numbered-Mode Configuration Option during Link Establishment phase. Generally, serial link reliability is not a major issue. The architecture of protocols used in datagram networking presume best- effort non-sequential delivery. When errors are detected, datagrams are discarded. However, in certain circumstances, it is advisable to provide a reliable link, at least for a subset of the messages. The most obvious case is when the link is compressed. Since the dictionary is recovered from the compressed data stream, and a lost datagram corrupts the dictionary, datagrams must not be lost. Not all compression types will require a reliable data stream, since the cost to detect and reset a corrupt dictionary is small. The ISO 7776 LAPB can be used guarantee delivery. This is referred to in this document as "Numbered Mode" to distinguish it from the use of "Unnumbered Information", which is standard PPP framing practice. Where multiple parallel links are used to emulate a single link of higher speed, Bridged traffic, Source Routed traffic, and traffic subjected to Van Jacobsen TCP/IP header compression must be delivered to the higher layer in a certain sequence. However, the fact of the links being relatively asynchronous makes traffic ordering uncertain. The ISO 7776 Multi-Link Procedure MAY be used to restore order. Implementation of the ISO Multi-Link Procedure is deprecated. It is recommended that the PPP multilink procedure [4] be used instead. Dave Rand expires in six months [Page 1] DRAFT PPP Reliable Transmission October 1993 2. Physical Layer Requirements PPP Reliable Transmission imposes the same requirements that are described in "PPP in HDLC Framing" [3], with the following exceptions. Control Signals While PPP does not normally require the use of control signals, implementation of Numbered-Mode LAPB or LAPD requires the provision of control signals, which indicate when the link has become connected or disconnected. These in turn provide the Up and Down events to the LCP state machine. 3. The Data Link Layer Numbered-Mode affects only the Address and Control fields. The remainder of the frame conforms to the framing in use for PPP. The Address Field of the frame MUST take the value announced in the Numbered-Mode Configuration Option, and the Control Field MAY take any value valid in ISO 7776. Once the link enters Numbered-Mode, Numbered-Mode MUST be used on all frames, as some implementations do not support the use of the Unnumbered-Information control field or the use of the All-Stations address intermixed with Numbered-Mode frames. 3.1. Frame Format The following frame format is valid under Numbered-Mode. The fields are transmitted from left to right. Numbered Mode +----------+----------+----------+ | Flag | Address | Control | | 01111110 |1-2 octets|1-2 octets| +----------+----------+----------+ +----------+-------------+---------+ | Protocol | Information | Padding | |1-2 octets| * | * | +----------+-------------+---------+ +----------+----------+----------------- | FCS | Flag | Inter-frame Fill | 16 bits | 01111110 | or next Address +----------+----------+----------------- Dave Rand expires in six months [Page 2] DRAFT PPP Reliable Transmission October 1993 The Protocol, Information and Padding fields are described in the Point-to-Point Protocol Encapsulation [1]. The FCS and Flag Sequence fields are described in "PPP in HDLC Framing" [3]. Dave Rand expires in six months [Page 3] DRAFT PPP Reliable Transmission October 1993 4. Configuration Option Format Description The LCP Numbered-Mode Configuration Option negotiates the use of Numbered-Mode on the link. By default or ultimate disagreement, Unnumbered-Mode is used. A summary of the Numbered-Mode Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Window | Address... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type TBD (11) Length >= 4 Window A value between 1 and 127. This indicates the number of frames the receiver will buffer, which is the maximum number that the sender should send without receiving an acknowledgement. If window < 8, then modulo 8 sequencing is used on the link. Otherwise, modulo 128 sequencing is used. It is conceivable and legal that differing window values might be announced. However, it is not permitted for one system to use modulo 8 sequencing and the other to use modulo 128. Therefore, the rule is: a Configure-Nak may reduce the window but may not increase it. Address An HDLC Address as specified in ISO 3309. ISO 7776 specifies four of the possible values: 1 and 3 for single link operation, 7 and 15 for the Multi-Link Procedure. Other values consistent with ISO 3309 are considered legal. Implementation of the Multi-Link Procedure is optional; A Dave Rand expires in six months [Page 4] DRAFT PPP Reliable Transmission October 1993 Configure-Nak may therefore force a change from MLP to single link mode, but not the reverse. Should the address be zero upon receipt, the receiver MUST Configure-Nak with an appropriate address. If both peers send address zero, the system advertising the numerically smaller window will select the smaller address. If both windows are the same size, a random choice MUST be made; when good sources of randomness are used, the link will converge in a reasonable time. If magic numbers have been negotiated on the link, the system with the numerically smaller magic number SHOULD specify the smaller address. 5. Numbered-Mode Operation When using the Numbered-Mode, each link is established in the usual manner for the type of link. The Numbered-Mode Configuration Option is negotiated, the Magic-Number Configuration Option MUST also be negotiated, and the Address-and-Control-Field-Compression Configuration Option MUST NOT be negotiated. Following the successful negotiation of the Numbered-Mode Configuration Option during LCP Link Establishment phase, the system with the numerically smaller Magic-Number will send a SABM or SABM(E), and the other will respond with a UA. In the event that either the SABM or UA is lost, this exchange may be repeated according to the same parameters as the configuration exchange itself, using the Restart Timer and counter values. Authentication, Link Quality Determination, and NCP Configuration follow this step. Once the link has been established with Numbered-Mode, when re- negotiation of link configuration occurs, the entire re-negotiation MUST be conducted in Numbered-Mode. If the Numbered-Mode Configuration Option is not successfully re-negotiated, the link reverts to Unnumbered-Information operation prior to Authentication, Link Quality Determination, and NCP Configuration. When an implementation which is capable of Numbered-Mode, and is not currently configured for Numbered-Mode operation, detects a frame which has a correct FCS but does not have a UI Control octet, the implementation MUST send a DM message, immediately followed by a LCP Configure-Request. When an implementation which is currently configured for Numbered- Mode operation receives a DM message, it MUST revert to Unnumbered- Information operation, and immediately send a LCP Configure-Request. Dave Rand expires in six months [Page 5] DRAFT PPP Reliable Transmission October 1993 5.1. Single Link When Network-Layer packets are sent over a single link, the packets are encapsulated in the following order: +----------+ +----------+ +----------+ | | | | | Numbered | | Header |-->| Data |-->| Mode |--> link | Compress | | Compress | | Header | +----------+ +----------+ +----------+ 5.2. Inverse Multiplexing Since sending several connections over a single link is often called "multiplexing", sending packets from a single connection over multiple parallel links is sometimes called "inverse-multiplexing". By default, PPP performs no special processing for such links. Each link is established and terminated independently, negotiates its own configuration options, and may have different combinations of such options as ACCM, Protocol Field Compression and IP-Address. This facilitates using the links simultaneously over dissimilar media, such as 56K sync with async backup. Every link in a single machine MUST have different Magic Numbers, and each end of every link between two peers SHOULD have Magic Numbers which are unique to those peers. This protects against patch-panel errors in addition to looped-back links. The distribution to each link is controlled by higher level routing mechanisms. When Network-Layer specific compression techniques (such as Van Jacobsen Compression) rely on sequential delivery, without Multi-Link Procedure support such compression MUST be applied on a link by link basis. +----------+ +----------+ +----------+ | | | | | Numbered | +--->| Header |-->| Data |-->| Mode |--> link 1 | | Compress | | Compress | | Header | +--------------+ +----------+ +----------+ +----------+ | Distribution | +--------------+ +----------+ +----------+ +----------+ | | | | | | Numbered | +--->| Header |-->| Data |-->| Mode |--> link 2 | Compress | | Compress | | Header | +----------+ +----------+ +----------+ Dave Rand expires in six months [Page 6] DRAFT PPP Reliable Transmission October 1993 5.3. Using Multi-Link Procedure This document does not offer a standard for ISO Multi-Link, but does offer a method for agreeing on the addressing scheme usable with Multi-Link. A sample implementation is shown below. Implementation of Multi-Link is not required. When using the ISO 7776 Multi-Link Procedure, each link is established as described above. In addition, the Numbered-Mode Configuration Option is negotiated with appropriate addresses for the Multi-Link Procedure. The distribution to each link is controlled by the Multi-Link Procedure, as is the recovery of sequence in the receiving system. +---> link 1 +----------+ +----------+ +----------+ | | | | | | Multi | +--------------+ | Header |-->| Data |-->| Link |-->| Distribution | | Compress | | Compress | | Procedure| +--------------+ +----------+ +----------+ +----------+ | +---> link 2 Dave Rand expires in six months [Page 7] DRAFT PPP Reliable Transmission October 1993 5.4. LAPB Parameter defaults The following guidelines specify the default values of LAPB configurable parameters. Timer T1 Timer T1 is the maximum time permitted before a retransmission is started, as a result of no response to a transmitted I frame. This value must be greater than the time required for a maximum sized frame to be received by the other side of the link, and for a response to be generated for the frame. This SHOULD be determined dynamically, based on the measured round trip time delay of the link at the LAPB level. In the event that the system cannot determine the round trip time of the link, this value SHOULD be set to twice the bit rate of the link, divided by the maximum number of bits per frame, plus 100 milliseconds processing time. For example, on a 14,400 bps link, with a maximum frame size of 8000 bits (1000 octects), the T1 value would be set to 3.7 seconds. Timer T3 Timer T3 gives an indication of the idle state of the link. Its value must be greater than the T1 value. Maximum number of attempts to complete a transmission, N2 Parameter N2 gives the maximum number of retransmission attempts for a given frame. If this value is exceeded, the link SHOULD be terminated. The default value for parameter N2 SHOULD be 3. Dave Rand expires in six months [Page 8] DRAFT PPP Reliable Transmission October 1993 Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W. A., "The Point-to-Point Protocol (PPP)", work in progress. [2] ISO 7776, Information Processing Systems - Data Communication - High Level Data Link Control Procedures - Description of the X.25 LAPB-Compatible DTE Data Link Procedures [3] Simpson, W. A., "PPP in HDLC Framing", work in progress. [4] Sklower, K., "PPP MultiLink Procedure", work in progress. Acknowledgments Fred Baker was the original author of this document. Bill Simpson contributed materially to the document. Dave Rand expires in six months [Page 9] DRAFT PPP Reliable Transmission October 1993 Chair's Address The working group can be contacted via the current chair: Fred Baker Advanced Computer Communications 315 Bollay Drive Santa Barbara, California 93117 EMail: fbaker@acc.com Author's Address Questions about this memo can also be directed to: Dave Rand 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand expires in six months [Page 10] DRAFT PPP Reliable Transmission October 1993 Table of Contents 1. Introduction .......................................... 1 2. Physical Layer Requirements ........................... 2 3. The Data Link Layer ................................... 2 3.1 Frame Format .................................... 2 4. Configuration Option Format ........................... 4 5. Numbered-Mode Operation ............................... 5 5.1 Single Link ..................................... 6 5.2 Inverse Multiplexing ............................ 6 5.3 Using Multi-Link Procedure ...................... 7 5.4 LAPB Parameter defaults ......................... 8 SECURITY CONSIDERATIONS ...................................... 9 REFERENCES ................................................... 9 ACKNOWLEDGEMENTS ............................................. 9 CHAIR'S ADDRESS .............................................. 10 AUTHOR'S ADDRESS ............................................. 10 Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Oct 6 16:02:12 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0okhqM-00001Ua; Wed, 6 Oct 93 16:00 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Last chance for LAPB document Date: Wed, 6 Oct 93 16:14:06 EDT Message-ID: <1475.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: dcarr@gandalf.ca (Dave Carr) > > An HDLC Address as specified in ISO 3309. ISO 7776 specifies four > > of the possible values: 1 and 3 for single link operation, 7 and > > 15 for the Multi-Link Procedure. Other values consistent with ISO > > 3309 are considered legal. > > I'm wondering if ISO multilink being frowned upon is enough. Should we > go that extra step and not allow it. It seems having 2 ways to do the > same thing should be avoided. > > > Configure-Nak may therefore force a change from MLP to single link > > mode, but not the reverse. > I'm in favor of keeping it. There are already people out there who are using it, and the negotiation allows graceful fallback to LAPB w/o MLP (which is what negotiation is all about!) It is one thing to recommend/deprecate something, and another to require/disallow it. We don't have any police powers. > I would also like to find out the route that other manufacturers are taking > for error-correction. There seems to be a split occuring, those doing it > with LAPB and those with multilink. I would like this issue *settled* before > giving LAPB my blessing. I haven't had much feedback in the main newsgroup. > Once we get this posted in internet-drafts, I expect some more feedback from the main list. > Typically, N2 is set to 3. I propose that as the default. I see that he took care of that. Nice work everyone. Too bad all of our stuff isn't this easy. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Oct 6 16:02:15 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0okhqM-0000W0a; Wed, 6 Oct 93 16:00 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Lapb draft RFC Date: Wed, 6 Oct 93 16:08:36 EDT Message-ID: <1474.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Looks OK to me. Did find a couple more nits: > Implementation of the Multi-Link Procedure is optional; A should be lower case ^ > link, with a maximum frame size of 8000 bits (1000 octects), extra c ^ > Bill.Simpson@um.cc.umich.edu My name seems to be stuck in the end of your draft. Don't bother resending to internet-drafts until we get some feedback from the main list. Bill.Simpson@um.cc.umich.edu