From owner-ppp-comp Thu Oct 7 12:04:30 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ol0bk-00004Ta; Thu, 7 Oct 93 12:02 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 at CCP before release Date: Thu, 7 Oct 93 12:01:08 PDT Message-ID: <9310071901.AA14098@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 The PPP Compression Control Protocol (CCP) draft-ieft-pppext-compression-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 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 expires in six months [Page i] DRAFT PPP Compression October 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 expires in six months [Page 1] DRAFT PPP Compression October 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 expires in six months [Page 2] DRAFT PPP Compression October 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 some cases) may be sent uncompressed, using its standard form, or may be sent in multiple datagrams, if the compression algorithm supports it. Dave Rand expires in six months [Page 3] DRAFT PPP Compression October 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 expires in six months [Page 4] DRAFT PPP Compression October 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 expires in six months [Page 5] DRAFT PPP Compression October 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 expires in six months [Page 6] DRAFT PPP Compression October 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 expires in six months [Page 7] DRAFT PPP Compression October 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 expires in six months [Page 8] DRAFT PPP Compression October 1993 A. Standard compression algorithm definitions A compression algorithm that is available without license fees is the predictor algorithm, defined below. Note that although care has been taken to ensure that the following code does not infringe any patents, there is no assurance that it is not covered by a patent. Use the following code at your own risk. 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. Dave Rand expires in six months [Page 9] DRAFT PPP Compression October 1993 Reconstructed data is: 0 1 2 3 4 5 6 7 File: A 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 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; Dave Rand expires in six months [Page 10] DRAFT PPP Compression October 1993 { 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) { Dave Rand expires in six months [Page 11] DRAFT PPP Compression October 1993 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; { Dave Rand expires in six months [Page 12] DRAFT PPP Compression October 1993 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); } } } A.2. Encapsultation for Predictor type 1 The correct encapsulation for type 1 compression is the protocol type, 1 bit indicating if the data is compressed or not, 15 bits of the uncompressed data length in octets, 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC - 16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ It is not required that any of the fields 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 Dave Rand expires in six months [Page 13] DRAFT PPP Compression October 1993 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 (uncompressed), compressed data, and uncompressed CRC-16. The data stream may be broken at any convenient place for encapsulation purposes. With type 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC-16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... It is not required that any field 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. Dave Rand expires in six months [Page 14] DRAFT PPP Compression October 1993 Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W. A., "The Point-to-Point Protocol", RFC in progress. [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 1340, 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. The predictor algorithm was originally implemented by Timo Raita, at the ACM SIG Conference, New Orleans, 1987. Bill Simpson helped with the document formatting. Chair's Address The working group can be contacted via the current chair: Dave Rand expires in six months [Page 15] DRAFT PPP Compression October 1993 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 expires in six months [Page 16] DRAFT PPP Compression October 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 ....... 14 B. CCP Recommended Options ......................... 14 SECURITY CONSIDERATIONS ................................ 14 REFERENCES ................................................ 15 ACKNOWLEDGEMENTS ............................................. 15 CHAIR'S ADDRESS .............................................. 15 AUTHOR'S ADDRESS ............................................. 16 From owner-ppp-comp Thu Oct 7 21:11:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ol9AD-00009ba; Thu, 7 Oct 93 21:10 PDT Sender: owner-ppp-comp X-Path: netcom.com!jad From: jad@netcom.com (James A. DeFrank) To: ppp-comp@bungi.com Subject: Re: FYI Date: Thu, 7 Oct 93 21:10:52 PDT Message-ID: <9310080410.AA21782@netcom.netcom.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk First, I would like to re-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. Back in early September, a lot of things were said and elaborated upon in this list in reaction to a marketing brochure from my company. The situation really got out of hand. Here in Cleveland, I do not have local full service access to the Internet and for some reason, those postings did not show up in my mail. I did not discover the postings until late September, and consequently, did not respond immediately. In view of the fact that we intend to obtain a CCP negotiation number, not to mention the fact that many of our prospective customers may be monitoring this list, I have no choice but to respond. I have chosen to cite each reference and respond accordingly. -From: Dave_Rand@Novell.COM (Dave Rand) -Subject: Re: FYI -Date: Thu, 2 Sep 93 09:40:54 PDT >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. **** Yes, yes I know. Development is taking a little longer than expected, but just because we haven't delivered anything yet, does not mean that we don't have anything, quite the contrary. Please read on. -From: art@acc.com (Art Berggreen) -Subject: Re: FYI -Date: Thu, 2 Sep 93 10:07:27 PDT >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. It's not all marketing hype. Yes, we did obtain throughput measurements from customers. >I don't see how information theory will let you get any net >compression on truly random data. I don't either Art. But hopefully, we're not talking about truly random data. If we were, then no compression algorithm(ASH included) that works by finding redundancy in a data stream and removing it would work because there would be no redundancy to remove. Hopefully, we're talking about good ole home grown network traffic, the raw, unprocessed stuff (-: Despite the smileys, there is a clever analogy at work here :-) Please read on. >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. > **** Perhaps the best way to explain the references to small packets and T1/E1 rates is to share a piece of e-mail that I sent to Dave Rand in late July containing information for obtaining a CCP negotiation number. He subsequently asked that I post it for everyone to have a look at anyway. I'll just encapsulate the whole thing with a {} block a la 'C' and take up on the other side of the }. PS: Yes, I know that the framing info is incomplete, I'll need to supply that in another posting. { From jad Wed Jul 21 12:21:11 1993 Return-Path: Received: by netcom4.netcom.com (5.65/SMI-4.1/Netcom) id AA05818; Wed, 21 Jul 93 12:18:10 -0700 From: jad (James A. DeFrank) Message-Id: <9307211918.AA05818@netcom4.netcom.com> Subject: Data for CCPN# for ASH To: dlr@daver.bungi.com Date: Wed, 21 Jul 93 12:18:10 PDT Cc: jad@netcom.com Reply-To: jad@netcom.com X-Mailer: ELM [version 2.3 PL11] Status: OR >[In the message entitled "Compression negotiation number for >ASH" on Jul 20, 16:04, James A. DeFrank writes:] >> >>Could you send me a list on private e-mail of the information >>you need from us in order to assign ASH a compression >>negotiation number. Thanks > >You will need to disclose the method of compression, the >framing type, whether a reliable protocol is required or not, >and the method for recovery and discovery of >compressor/decompressor desyncronization. METHOD OF COMPRESSION: ASH (Proprietary) FRAMING TYPE: Algorithm expedites latent codes on user frame end; however, available bandwidth of the composite(reliable link) may encapsulate multiple user frames of compressed data. RELIABLE PROTOCOL: Yes (LAP-M) DETECTION OF DESYNCHRONIZATION: Overlong user frame, scrambler signal(stuffing convention) without preceding expedite, or diagnostic(internal) CRC error which follows expedite. RECOVERY FROM DESYNCHRONIZATION: Scrambler signal sent to remote coder of desynchronized history followed by error report; decoder resets desynchronized compression history and enters a hunt mode for scrambler signal. Coder receives scrambler signal and error report, and resets history; coder issues scrambler signal followed by resynchronize connect, decoder receives scrambler signal, resynchronizes connect, and begins decoding. Please contact me with CCP negotiation number(CCPN#), or any further questions by private e-mail or at Transcend at (216) 835-4882. If calling after business hours(Eastern Time), dial my voice mail at Ext. 21. Thanks Dave. Jim DeFrank -- } The brochure means higher throughput on shorter packets and on T1/E1. Since the algorithm expedites latent codes on user frame ends, shorter packets would clear the compression engine faster than longer ones. Also, if the frames come in faster, it stands to reason that they will move through faster. -From: dcarr@gandalf.ca (Dave Carr) -Subject: Re: FYI -Date: Thu, 2 Sep 1993 13:07:22 -0400 (EDT) >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. **** I'm not sure what you mean by your first statement, Dave. In a theoretical sense, no algorithm consumes power, it's just an algorithm. If you mean the hardware that the algorithm is implemented on, then the above statement is not correct, ASH does not run without power. As for the second statement, this seems to be the first instance of many which associate us(Transcend) with WEB. This is unfortunate for all concerned. In ASH, Transcend has some really neat concepts and technology to offer the network compression industry as a whole, none of which depart from principles of information theory. Now for the next statements, the ones involving the word "guarantee". I'm afraid that this was taken too literally by many folks on this alias. More on this later. Please read on. -From: Thomas Dimitri -Subject: RE: FYI -Date: Thu, 2 Sep 93 10:22:39 TZ >Be careful! Do not slander this company in public. Do not >claim that guaranteed 4:1 compression is impossible otherwise >you may be sued. > Some folks may already be guilty of that, not because they claim that guaranteed 4:1 compression is impossible, but because they attributed certain things to us and made associations which were simply not true. Relax guys, we're not out to sue anyone, we just want to set the record straight. >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). We are not making similar claims and we are not doing "tricky things" like that. >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? **** We are aware of Shannon's work. As for the ZIP file, if the compression ratio of the ZIPped file were 4:1, then it would go across at 4:1, if it were 16:1, then it would go across at 16:1, and if it were 2:1, then it would go across at 2:1. You see, we never claimed to be able to compress pre-compressed or encrypted data, or any of that "processed stuff" (-: so much for the clever analogy :-) but, we do say that we will not expand it. This is what I meant by the word 'guarantee' being taken too literally. -From: Jim Petty -Subject: Re: FYI -Date: Thu, 2 Sep 93 10:51:52 PDT >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 > **** As previously mentioned, the 4:1 was based on results from the field. The results of the chopped up Calgary stuff were not available at Interop, they will be reported as soon as they are available. -From: dcarr@gandalf.ca (Dave Carr) -Subject: Re: FYI -Date: Thu, 2 Sep 1993 14:19:14 -0400 (EDT) >> 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". > And what's going on here is definitely what I term debating in a vacuum. >Now granted, if they are claiming 4:1 on the "Rand" corpus, >that's another story. **** -From: Thomas Dimitri -Subject: Transcend -Date: Thu, 2 Sep 93 11:44:04 TZ >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. > I don't know exactly what everyone on this alias knows, but I do agree with you on one point - a lot of time was wasted unnecessarily. >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 :-) **** Can I come too? -From: rms@titan.acc.com (Ron Stoughton) -Subject: Re: FYI -Date: Thu, 2 Sep 93 15:15:23 EDT >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. > That's it! That's the idea. I couldn't have stated it better myself. >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. If we're talking about straight-up compression ratio this may not always be the case, but certainly ASH would be no worse than other string-based compressors on a single session. Keep in mind that even without the data diversity of multiple sessions, in the network environment where the specter of latency looms dark and ominous, high compression ratio does not necessarily mean high throughput. It could actually mean just the opposite. If it takes longer to receive a frame, compress it, and send it across the link than it does to send the same information across uncompressed, a high compression ratio won't do much good. >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". > **** If 'any data' includes pre-compressed or encrypted data, I don't see how we can either, and we don't. Yes, we freely admit that all data is not compressible. Needless to say, we are quite proud of our mechanisms for detection and prevention of expansion. -From: dcarr@gandalf.ca (Dave Carr) -Subject: Re: Transcend -Date: Thu, 2 Sep 1993 15:29:11 -0400 (EDT) >> >> 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. Hearsay, you say(dramatic pause)... I'll say! > >I think the onus would be on them publish data backing up their >claim. > We will do so. >> 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. > What if the claim does have substance? >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.* > Hmmm, yeah, somehow I think I know where you're coming from on the "if I don't speak up" part, Dave. >> 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 :-) > **** Do you guys like peanuts with your beer? :-) Seriously though, what should it be recognized as? Shouldn't it be checked out before passing judgment? -From: fbaker@acc.com (Fred Baker) -Subject: Re: FYI -Date: Thu, 2 Sep 1993 13:37:07 -0800 >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. **** Save the time, effort, and diskettes Fred. First, ASH in its present form is not a file compressor, it is a network compression system, designed from that environment, for that environment. Second, AT NO TIME DID ANYONE FROM TRANSCEND EVER SAY THAT WE COULD COMPRESS RECURSIVELY, i.e., COMPRESS OUR OWN OUTPUT. NOT EVEN OUR MARKETING DEPARTMENT CAN BE ACCUSED OF THIS. EVEN IF WE COULD, DO YOU THINK WE WOULD TRY TO USE SUCH A THING IN A NETWORK ENVIRONMENT? THE LATENCY GREMLINS WOULD BE LAUGHING THEIR BUTTS OFF! C'MON GUYS. -From: dcarr@gandalf.ca (Dave Carr) -Subject: Re: FYI -Date: Thu, 2 Sep 1993 16:47:58 -0400 (EDT) >#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! :-) > That's tellin' em, Dave :-) By the way, I've adopted that last line as the banner for my Windows screen saver, smiley included. :-) All smileys aside though, Dave, I would like to know more about your FZA. Not secrets of course, just a general description. If you have the chance, could you send it private e-mail? Well, I've said my piece. In closing I would just like to say that we at Transcend are not much different from all of you in the following respect: We are for real, we are experienced, we believe in our technology, and we believe we have something exciting to contribute to the network compression industry. Just because development is taking somewhat longer than expected(we are in the closing phases), we shouldn't be counted out. Let's bury the hatchet folks, please. Finally, if anyone has any questions or comments regarding Transcend, ASH, this posting, life in general, etc., please contact me by posting, private e-mail, or at Transcend at (216) 835-4882 between 9 a.m. and 5 p.m. Eastern Time, or leave a voice mail message anytime at Ext. 21. Regards, Jim DeFrank -- From owner-ppp-comp Fri Oct 8 07:55:09 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olJCi-0000NXa; Fri, 8 Oct 93 07:54 PDT Sender: owner-ppp-comp X-Path: netcs.com!okorf From: Oliver Korfmacher To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Fri, 8 Oct 93 15:53:33 MET Message-ID: <9310081453.AA08381@keks.netcs.com> References: <<9310071901.AA14098@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk you write: 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 some cases) may be sent uncompressed, using its standard form, or may be sent in multiple datagrams, if the compression algorithm supports it. How can I differentiate between an datagram which is not compressed at all meaning it dont go through any compressor and a datagram which is sent uncompressed because the compressed datagram is larger than the original? This is needed with some algorithms because they have to eat the uncompressed data as well to update their dictionaries. Oliver Oliver Korfmacher (okorf@netcs.com, whois OK11) From owner-ppp-comp Fri Oct 8 08:20:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olJbJ-0000DEa; Fri, 8 Oct 93 08:19 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: Fri, 8 Oct 1993 11:16:52 -0400 (EDT) Message-ID: <9310081516.AA09816@donut.gandalf.ca> References: <<9310080410.AA21782@netcom.netcom.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Hi Jim, welcome aboard. > >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. > **** > > I'm not sure what you mean by your first statement, Dave. In a > theoretical sense, no algorithm consumes power, it's just an > algorithm. If you mean the hardware that the algorithm is > implemented on, then the above statement is not correct, ASH does > not run without power. Perpetual motion machine. Very abstract analogy to an outrageous claim. The (heresay) claims reminded me of outrageous claims made by WEB. That's as far as I meant the statement to be taken. > What if the claim does have substance? I would first want to read an actual data sheet. Wording is most important. What they intend to claim, what they actually claim, what a naive reader reads into it, what a person knowledgable in the field reads, and so on. >From what Jim has mentioned, the "claim" is not outrageous. Many customers report higher ratings for our compression in real life. My marketting department would like to make higher claims too, but I try to force them back to reality. What happens in real life should be stated as typical, not garaunteed. Since I have yet to see the claims, I'll stick by my original statement. Per session compression, is definitely a win. No doubt about it. Mixing data streams reduces the efficiency of any algorithm. To claim this would not be outrageous, but realistic. > >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 > > Hmmm, yeah, somehow I think I know where you're coming from on > the "if I don't speak up" part, Dave. See marketting (above). > > Seriously though, what should it be recognized as? Shouldn't it > be checked out before passing judgment? Definitely. Any chance of seeing the claims first hand? Could you FAX a data sheet? > > Save the time, effort, and diskettes Fred. First, ASH in its > present form is not a file compressor, it is a network > compression system, designed from that environment, for that > environment. Yes. FZA has the same problem. That's why it we need a better benchmark system. The file approach (Rand test) is good, but it would be better if it had a packet interface to the test file(s). > That's tellin' em, Dave :-) By the way, I've adopted that last > line as the banner for my Windows screen saver, smiley included. Oh, darn. Forgot the Copyright 1993 again! I hereby grant you unrestricted use, with zero indemnity on it's originality. > All smileys aside though, Dave, I would like to know more about > your FZA. Not secrets of course, just a general description. If > you have the chance, could you send it private e-mail? Sure. I'll show you mine, if you show me yours! -- 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 Oct 8 08:37:53 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olJre-0000Nba; Fri, 8 Oct 93 08:36 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: Fri, 8 Oct 93 08:35:22 PDT Message-ID: <9310081535.AA02798@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > >First, I would like to re-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. > >Back in early September, a lot of things were said and elaborated >upon in this list in reaction to a marketing brochure from my >company. The situation really got out of hand. Here in Cleveland, >I do not have local full service access to the Internet and for >some reason, those postings did not show up in my mail. I did not >discover the postings until late September, and consequently, did >not respond immediately. In view of the fact that we intend >to obtain a CCP negotiation number, not to mention the fact that >many of our prospective customers may be monitoring this list, I >have no choice but to respond. I have chosen to cite each >reference and respond accordingly. Jim, Thanks for the rational response and welcome to the minefield that is known as the Internet. I think that many of us have gotten overly sensitive to the habit most of our marketing folks have of taking specific engineering information and using it publically, totally out of context. Don't take the discussion as a flame of Transcend's technology, but rather of how information gets released. Art From owner-ppp-comp Fri Oct 8 09:19:33 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olKWL-00004za; Fri, 8 Oct 93 09:18 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Fri, 8 Oct 1993 09:18:11 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Last chance at CCP before release" on Oct 8, 15:53, Oliver Korfmacher writes:] > How can I differentiate between an datagram which is not compressed at > all meaning it dont go through any compressor and a datagram which is > sent uncompressed because the compressed datagram is larger than the > original? This is needed with some algorithms because they have to eat > the uncompressed data as well to update their dictionaries. You can't. If you want in-band expansion protection, you must do it in some fashion within your compressor's data stream. That's what is done in predictor - a single bit indicates if the next block is compressed, or not. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Oct 8 10:23:48 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olLWY-0000PMa; Fri, 8 Oct 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: FYI Date: Fri, 8 Oct 1993 10:21:43 -0800 Message-ID: <9310081722.AB05154@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >>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. >**** > >Save the time, effort, and diskettes Fred. First, ASH in its >present form is not a file compressor, it is a network >compression system, designed from that environment, for that >environment. > >Second, AT NO TIME DID ANYONE FROM TRANSCEND EVER SAY THAT WE >COULD COMPRESS RECURSIVELY, i.e., COMPRESS OUR OWN OUTPUT. NOT >EVEN OUR MARKETING DEPARTMENT CAN BE ACCUSED OF THIS. > >EVEN IF WE COULD, DO YOU THINK WE WOULD TRY TO USE SUCH A THING >IN A NETWORK ENVIRONMENT? THE LATENCY GREMLINS WOULD BE LAUGHING >THEIR BUTTS OFF! C'MON GUYS. Which was, of course, my point. I was responding to something direct mailed to me which "guaranteed" 4:1 compression on "any data". "Any data", to me, includes recursive compression. And "guarantee" is a term that my lawyers advise me has legal and financial implications. Your sales person, when I called your office, assured me with a very straight face that all that is required to make this guarantee good is enough CPU MIPS and memory. >Well, I've said my piece. In closing I would just like to say >that we at Transcend are not much different from all of you in >the following respect: We are for real, we are experienced, we >believe in our technology, and we believe we have something >exciting to contribute to the network compression industry. >Just because development is taking somewhat longer than >expected(we are in the closing phases), we shouldn't be counted >out. Let's bury the hatchet folks, please. Having said which, I absolutely agree. Carr Brown (one of our hardware people) and I have spoken with your marketing person under non-disclosure, and I have contacted your reference customer. The technology as described seems like it should be capable of acheiving excellent compression ratios on compressible data, and may be better at finding patterns in the data than standard Lempel-Ziv approaches. Consider any "hatchets" buried. Please also understand that the compression field is frought with hype and hyperbole; in a results-oriented realm, where "rough consensus and running code" speaks, what we have heard from Transcend so far really isn't very impressive. At the last (Amsterdam) IETF meeting, HP made a presentation to the working group on their compression approach. Maybe you would like to do the same at the coming IETF meeting in Houston? If so, contact me directly (fbaker@acc.com, 805.685.4455) and we'll make arrangements for that. ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Sat Oct 9 13:13:27 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olkeK-0000BNa; Sat, 9 Oct 93 13:12 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 at CCP before release Date: Sat, 9 Oct 93 15:03:28 EDT Message-ID: <1503.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > 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. > I suggest that the second sentence here could be removed. Try: 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 data compression over > PPP links, and describes the use of several such data compression > protocols. > Good. > 1. Introduction > The language you used here is fine if this were introducing a Network Control Protocol, but you are _really_ introducing a link modification. This is the first of such "special" control protocols. I suggest some introductory language about the need for and use of compression on a link, like that which is found in your other draft, "PPP Reliable Transmission". > The Compression Control Protocol is exactly the same as the Link > Control Protocol [1] with the following exceptions: > Frame Modifications The packet may utilize any modifications to the basic frame format which have been negotiated during the Link Establishment phase. > 2.1. Sending Compressed Datagrams > One or more compressed packets are encapsulated in the Information > 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. > I really disagree with this paragraph! Let's standardize on one (1) method of handling multiple packets (not frames!) within one compressed frame. I suggest that Compound-Frames be used. > 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. > Please split this overly long paragraph, perhaps at "There is the possibility". Change the references to LAPB to "Reliable" and reference [#]. > 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. > I thought we were allowing multiple algorithms! We certainly discussed this at length a year ago. How does this work with multiple OUIs? (It doesn't.) I think that you have confused Reject with Nak. (In view of the later section, it is clear you don't understamd it at all.) > 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 > This doesn't match the Types you have below. I suggest putting OUI first (#1). There were a lot of vendors out there. Assign them some numbers. > 3.1. Defined Compression Algorithms > This is not right! This doesn't match the Configuration Options description above, won't work with either Reject or Nak, and simply isn't what we discussed. If you send back a Reject, it means you don't understand the option TYPE, not the option _contents_. Back to the drawing board.... Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Sat Oct 9 19:24:12 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0olqQx-0000Roa; Sat, 9 Oct 93 19:22 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Sat, 9 Oct 1993 19:22:37 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Last chance at CCP before release" on Oct 9, 15:03, "William Allen Simpson" writes:] > > 2.1. Sending Compressed Datagrams > > > One or more compressed packets are encapsulated in the Information > > 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. > > > I really disagree with this paragraph! Sigh. That is unfortunate. > Let's standardize on one (1) method of handling multiple packets (not > frames!) within one compressed frame. No. Each algorithm needs the ability to decide for itself when and if to concatenate "packets" into multiple "frames". Above the compressor is not the right place, at all. > I thought we were allowing multiple algorithms! We certainly discussed > this at length a year ago. We are allowing ONLY ONE compression algorithm at a time to be used on a link. This was a direct result of the late-night session that we had in Amsterdam. People were way concerned with the amount of memory that even one of the algorithms were using, and had no desire to have multiple algorithms running concurrently. > > There were a lot of vendors out there. Assign them some numbers. I'm *QUITE* happy to assign numbers. I have requested that those who wish numbers send me: 1) The algorithm used (full disclosure desireable, but just the name is OK) 2) The framing method used, with any required error check mechanism. This includes such things as min/max size, multiple "packets" per "frame" used, etc, etc. Enough so that someone can implement the method, if they have rights to the compressor. 3) The reliable link requirements (yes/no) 4) The error recovery mechanism and signalling required. No one has yet - the only one to try has been Transcend. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Tue Oct 12 04:04:29 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0omhVE-0000O7a; Tue, 12 Oct 93 04:02 PDT Sender: owner-ppp-comp X-Path: spider.co.uk!gerry From: Gerry Meyer To: dcarr@gandalf.ca, ppp-comp@bungi.com Subject: Re: FYI Date: Tue, 12 Oct 93 12:02:03 +0100 Message-ID: <24542.9310121102@orbweb.spider.co.uk> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Yes. FZA has the same problem. That's why it we need a better >benchmark system. The file approach (Rand test) is good, but it >would be better if it had a packet interface to the test file(s). Yes. I would certainly be happier if the Rand test at least included a liberal sprinkling of small ACKS to the constant 512 byte chunks - which would impact some algorithms (like PPC) more than others. [Were any results of the Rand test for PPC mailed to the list?] Gerry From owner-ppp-comp Tue Oct 12 06:49:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0omk61-0000A7a; Tue, 12 Oct 93 06:49 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: FYI Date: Tue, 12 Oct 1993 06:48:42 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: FYI" on Oct 12, 12:02, Gerry Meyer writes:] > > [Were any results of the Rand test for PPC mailed to the list?] > No. They will be at some point. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Tue Oct 12 10:34:47 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0omncF-00007aa; Tue, 12 Oct 93 10:34 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Tue, 12 Oct 93 10:07:42 TZ Message-ID: <9310121733.AB24293@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Dave Rand | > | > There were a lot of vendors out there. Assign them some numbers. | | I'm *QUITE* happy to assign numbers. I have requested that those who wish | numbers send me: | | 1) The algorithm used (full disclosure desireable, but just the name is OK) | 2) The framing method used, with any required error check mechanism. | This includes such things as min/max size, multiple "packets" per "frame" | used, etc, etc. Enough so that someone can implement the method, if they | have rights to the compressor. | 3) The reliable link requirements (yes/no) | 4) The error recovery mechanism and signalling required. | | No one has yet - the only one to try has been Transcend. Could we hold off on submitting this for a release because I am *very* close (a week or so) to releasing/licensing a good PPP LZ compression scheme (probably for FREE). I would like this scheme to make it into the CCP document. I will be glad to provide a write-up on the algorithm and source code (assuming all goes well). I will also be glad to give a talk on it at the upcoming IETF. The scheme has a negoitable history buffer size, doesn't need a reliable link (but does use a simple recovery mechanism), and won't expand uncompressable frames much. It also has some other nice properties. I just need a week or so to finalize stuff over here. --Thomas From owner-ppp-comp Tue Oct 12 13:03:31 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ompwH-0000Wba; Tue, 12 Oct 93 13:03 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: working the wood Date: Tue, 12 Oct 1993 13:02:49 PDT Message-ID: <9310122002.AA02956@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Hmm... it seems that everyone is coming out of the woodwork now that the draft is close to finished. I am now modifying my request for those that wish a defined compression type. I would now like you to include the text AS YOU WISH IT TO APPEAR in the document. This should include contact information (email/postal addresses) for licensing information, approximate cost, plus all the details required previously. If you can and wish to negotiate options, please include a section on negotiation and defaults. If there is confusion on this, please contact me ASAP, and I'll help you with the details. Basically, it should provide enough information for someone to pick up the document, order the compression sources, integrate it into their PPP, and have it work. -- From owner-ppp-comp Tue Oct 12 13:18:26 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0omqAc-0000Fva; Tue, 12 Oct 93 13:18 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: tommyd@microsoft.com Subject: Re: Last chance at CCP before release Date: Tue, 12 Oct 1993 13:17:03 -0800 Message-ID: <9310122017.AB20459@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Could we hold off on submitting this for a release because By "release", Dave meant submission as an Internet Draft. We won;t be sending it off to the IESG until after the IETF, at the earliest. BTW, could I impose on you to make a presentation at the IETF re: your draft? ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Tue Oct 12 13:22:17 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0omqES-0000V9a; Tue, 12 Oct 93 13:22 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Tue, 12 Oct 1993 13:22:02 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Last chance at CCP before release" on Oct 12, 13:17, Fred Baker writes:] > >Could we hold off on submitting this for a release because > > By "release", Dave meant submission as an Internet Draft. We won;t be > sending it off to the IESG until after the IETF, at the earliest. > > BTW, could I impose on you to make a presentation at the IETF re: your draft? > I assume you mean me? Of course. I'll be there. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Oct 13 06:23:12 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on69K-0000Uqa; Wed, 13 Oct 93 06:21 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 at CCP before release Date: Tue, 12 Oct 93 18:58:42 EDT Message-ID: <1518.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Could we hold off on submitting this for a release because > I am *very* close (a week or so) to releasing/licensing a > good PPP LZ compression scheme (probably for FREE). I would > like this scheme to make it into the CCP document. I will Actually, I have been saying for some time that the CCP should be one document, and then each compression scheme should be in a separate document, with its own history and configuration sections. That way, we get the CCP done so that we can test the various algorithms, with automatic negotiation. Particularly since we haven't been able to come up with a single "perfect" scheme. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Oct 13 08:00:25 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on7fW-00005La; Wed, 13 Oct 93 07:59 PDT Sender: owner-ppp-comp X-Path: vnet.IBM.COM!jo'donnell From: jo'donnell@vnet.IBM.COM To: ppp-comp@bungi.com Subject: Compression For other protocols. Date: Wed, 13 Oct 93 10:48:36 EDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Is anyone else interested in developing a standard for data compression for Frame Relay (RFC1490 (1294)) ? Jim O'Donnell (919) 254-0015 From owner-ppp-comp Wed Oct 13 08:19:33 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on7yY-0000Nya; Wed, 13 Oct 93 08:18 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 at CCP before release Date: Wed, 13 Oct 1993 11:16:15 -0400 (EDT) Message-ID: <9310131516.AA10934@donut.gandalf.ca> References: <<1518.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Actually, I have been saying for some time that the CCP should be one > document, and then each compression scheme should be in a separate > document, with its own history and configuration sections. I'll second that motion, and also suggest that all negotitaion is through the OUI method. -- 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 Oct 13 08:33:13 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on8Bg-00002Ka; Wed, 13 Oct 93 08:32 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Last chance at CCP before release Date: Wed, 13 Oct 1993 08:32:09 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Last chance at CCP before release" on Oct 13, 11:16, Dave Carr writes:] > > Actually, I have been saying for some time that the CCP should be one > > document, and then each compression scheme should be in a separate > > document, with its own history and configuration sections. > > I'll second that motion, and also suggest that all negotitaion is > through the OUI method. > This is a draft standard. It can change easily. Definition of compression protocols will occur in this document. Definition of as many "standard" compression types as possible will occur in this document. This was the concensus at both meetings I have attended. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Oct 13 09:13:16 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on8oG-0000ABa; Wed, 13 Oct 93 09:12 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr (Dave Rand) To: ppp-comp@bungi.com Subject: Multi-link methods Date: Wed, 13 Oct 93 09:11 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk How, exactly, is this all going to work together? Today, we have: ------- -------------- | PPP | ----> | Comm. Link | ------- -------------- With compression, we have: ------- -------- -------------- | PPP | ----> | Comp | ----> | Comm. Link | ------- -------- -------------- or ------- -------- -------- -------------- | PPP | ----> | Comp | ----> | LAPB | ----> | Comm. Link | ------- -------- -------- -------------- Depending on the compressor. This diagram is not quite correct, because we can bypass the compressor for some packets. We also kind of loop back into PPP for address, control and protocol type compression (after/during data compression). Now, with multi-link (Keith's proposal), we have: ------- ------- -------------- | PPP | ----> | MLP | ----> | Comm. Link | ------- ------- | -------------- | -------------- +---> | Comm. Link | | -------------- (...) Adding compression, we get: (1). ------- ------- ------- -------------- | PPP | ----> | Comp | ----> | MLP | ----> | Comm. Link | ------- ------- ------- | -------------- | -------------- +---> | Comm. Link | | -------------- (...) or (1A). ------- ------- ------- -------- -------------- | PPP | ----> | Comp | ----> | MLP | ----> | LAPB | ----> | Comm. Link | ------- ------- ------- | -------- -------------- | ________ -------------- +---> | LAPB | ----> | Comm. Link | | -------- -------------- (...) or (2). ------- ------- -------- -------------- | PPP | ----> | MLP | ----> | Comp | ----> | Comm. Link | ------- ------- | -------- -------------- | -------- -------------- +---> | Comp | ----> | Comm. Link | | -------- -------------- (...) or (2A). ------- ------- -------- -------- -------------- | PPP | ----> | MLP | ----> | Comp | ----> | LAPB | ----> | Comm. Link | ------- ------- | -------- -------- -------------- | -------- -------- -------------- +---> | Comp | ----> | LAPB | ----> | Comm. Link | | -------- -------- -------------- (...) If you have read this far, you can see that the A versions of 1 and 2 add the reliable datalink layer, for those compression protocols that require it. Method 1 Advantages: Offers the best compression ratio, by giving the compressor the most coherent data stream to work with. Load balancing the lines occurs with compressed data, which is actually the data that will be carried on the link. Dissimilar link speeds can be accommodated properly. Good use of the MLP by fragmenting data over multiple links, reducing latency. Disadvantages: Requires a host-based compression algorithm. Method 2 Advantages: Allows off-loading the compression to front-end communications boards. Disadvantages: For "reasonable" compression ratios, round-robin (ie B and E bits both set on packets coming down for compression) should be used, increasing latency. Hmm. It appears that I am biased. I'm having trouble thinking up advantages to method 2 (sorry, Greg!). I am trying some experiments to see exactly what effect MLP has on my "test data". I'll post those results when they are ready. In the mean time, what (else) have I missed? Should this information be in the CCP document, or should there be a separate "Life, the Universe, and PPP" document that ties everything together? From owner-ppp-comp Wed Oct 13 09:31:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on95h-00003ma; Wed, 13 Oct 93 09:30 PDT Sender: owner-ppp-comp X-Path: acc.com!fbaker From: fbaker@acc.com (Fred Baker) To: ppp-comp@bungi.com Subject: Re: Compression For other protocols. Date: Wed, 13 Oct 1993 09:29:07 -0800 Message-ID: <9310131629.AB00487@fennel.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >Is anyone else interested in developing a standard for >data compression for Frame Relay (RFC1490 (1294)) ? in the context of PPP/FR, I believe that we already have... ============================================================================= Don't blame ACC; they think I'm nuts too! From owner-ppp-comp Wed Oct 13 10:10:12 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0on9ht-000050a; Wed, 13 Oct 93 10:09 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: Last chance at CCP before release Date: Wed, 13 Oct 93 11:08:48 -0600 Message-ID: <9310131708.AA07397@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk "William Allen Simpson" writes: > > Could we hold off on submitting this for a release because > > I am *very* close (a week or so) to releasing/licensing a > > good PPP LZ compression scheme (probably for FREE). I would > > like this scheme to make it into the CCP document. I will > > Actually, I have been saying for some time that the CCP should be one > document, and then each compression scheme should be in a separate > document, with its own history and configuration sections. > > That way, we get the CCP done so that we can test the various > algorithms, with automatic negotiation. Particularly since > we haven't been able to come up with a single "perfect" scheme. We all agree that most compression algorithms should be listed by little more than name and number in the CCP RFC and that most compression algorithms should be fully documented elsewhere. However, I strongly disagree that no algorithms at all should be documented in the CCP RFC. The purpose of an RFC is to ensure interoprability. A compression RFC that did not define at least one lingua franca would be useless, since there would be no likelihood that two implementations would have a common compression mode. The compression RFC must fully document one (or perhaps 2 or 3) minimal compression algorithm(s). The defined algorithm must be as close to public domain as possible. The common mode need not be very good, but it must exist and be documented. The vast majority of all compressing PPP installations will be on PC's and other DOS, Windows-NT, and UNIX machines, and will be based on the existing, freely redistributable source. Those installations will obviously not involve any algorithms or anything else that require paying anyone anything. Those installations will use one of no more than 2 or 3 different compression algorithms. It would be silly to document these minimal, free compression algorithms in a separate RFC, since no one who reads about the minimal algorithms would fail to also read the CCP RFC, and no one who reads the CCP RFC would fail to read the RFC defining the minimal, common compression algorithm(s). The only reason to separate topics into different RFC's is if you expect one to be revised much more frequently than the other, if you think that the audiences for the RFC's are not the same, or if each topic individual would require a large document. Predictor and CCP meet none of those criteria for separating them, and so they must be documented in the same RFC. Predictor Type 1 seems to meet the requirements for a minimal, free, common algorithm, and so must be documented in the CCP RFC. Predictor Type 2 is very similar, might turn out to be common and so could be fully documented in the CCP RFC. I don't know. An LZ algorithm that is free for software implementations (even if it required royaties for hardware products) might also meet those requirements for the minimal algorithm and might have been a replacement for Predictor Type 1. However, at this late date, it can only be the second or third fully documented in the CCP RFC. After 2 or 3 years of trying, we have two (2) documented algorithms, with at most hopes or rumors of 3 others (splay trees, Digiboard's LZ, and Gandalf's). If anyone has an algorithm that can be put in the draft, then do it soon. Let's publish the draft and get on with it! Vernon Schryver, vjs@sgi.com From owner-ppp-comp Wed Oct 13 10:44:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onAEv-00005aa; Wed, 13 Oct 93 10:43 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 at CCP before release Date: Wed, 13 Oct 1993 13:41:29 -0400 (EDT) Message-ID: <9310131741.AA00311@donut.gandalf.ca> References: <<9310131708.AA07397@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > with at most hopes or rumors of 3 others (splay trees, Digiboard's LZ, > and Gandalf's). Thanks Vernon. I'll inform the 1000's of customers running FZA that it is only a virtual algorithm :-) Serious inquiries are welcome as aways. -- 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 Oct 13 11:14:13 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onAh9-0000Eka; Wed, 13 Oct 93 11:13 PDT Sender: owner-ppp-comp X-Path: mcimail.com!STAC/STAC/BobL%Stac_Electronics From: BobL To: ppp-comp Subject: CCP Comments Date: Wed, 13 Oct 93 17:35 GMT Message-ID: <21931013173512/0005015674ND3EM@mcimail.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I am in the middle of trying to write a Compression Negotiation Definition (CND) for the Stacker LZS compression format that corresponds to Dave Rand's CCP. I have a few of suggestions based on this experience. 1) I believe there are a certain set of negotiable parameters that will be common to most, if not all compression formats. These parameters should probably be included in the CCP document. Otherwise, they will simply be repeated in each separate CND. The parameters that I am planning to negotiate for the LZS algorithm are a) number of simultaneous compression histories, b) reset mode, c) option to append a CRC. These parameters are largely algorithm independent. I suspect that many CNDs will want to include these same options. Note: Reset Mode is simply whether the compression history must be reset at the end of each packet, or if the compression history can be maintained between packets. 2) Due to the fact I want to negotiate these options for LZS, I need to include a protocol for negotiation in my CND. This is a lot of overhead which is essentially an encapsulation of the LCP negotiation protocol embedded in the data field of the Type 3 CCP packet. Since many CNDs will probably need to negotiate options, I believe that we should include the negotiation protocol at the CCP level as additional Types to include the Configure-Request, Configure-Ack, Configure-Nak, and Configure-Reject types. 3) I do not believe the Predictor compression algorithm should be included in the CCP. All compression algorithms should be defined in a separate Compression Negotiation Definition (CND) document. If you include specific compression algorithms in the CCP, then it will never become stable as new algorithms will be added, and new options will be added to old algorithms. I have been directly involved in data compression standards for ANSI(X3.241-199X), IEEE, and QIC (QIC-122). In these organizations individual data compression algorithms have always been defined in separate documents (written by the sponsor of each algorithm), unless only a single compression algorithm has been chosen as THE standard. Robert Lutz Stac Electronics Phone (619) 431-7474, FAX (619) 431-0947 Email:Stac/Stac/BobL%Stac_Electronics@mcimail.com From owner-ppp-comp Wed Oct 13 12:20:47 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onBiQ-0000EPa; Wed, 13 Oct 93 12:18 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Multi-link methods Date: Wed, 13 Oct 1993 15:15:01 -0400 (EDT) Message-ID: <9310131915.AA00355@donut.gandalf.ca> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > I am trying some experiments to see exactly what effect MLP > has on my "test data". I'll post those results when they are > ready. In the mean time, what (else) have I missed? Should > this information be in the CCP document, or should there > be a separate "Life, the Universe, and PPP" document that > ties everything together? The second method would allow you to multilink a T1 link and a basic rate for example, but only compression the basic rate. Alternately, you may chose to use a more powerful algorithm on the slower link. Reasons can vary, but CPU and memory could be determining factors. And while this mode isn't my cup of tea, I'm sure someone out there wants it. The interactions of the CCP, Internet Multilink, and LAPB NCPs is getting quite complicated. I would say that it should NOT be part of your document, or at least be isolated into an "Interaction with Other Protocols" section. Otherwise, you should rename the spec to "Milli-daves, the RFC at the end-of-the-universe". So long, and thanks for the CCP Options. -- 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 Oct 13 15:11:24 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onEPB-0000Rja; Wed, 13 Oct 93 15:10 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: Last chance at CCP before release Date: Wed, 13 Oct 93 15:47:06 -0600 Message-ID: <9310132147.AA09403@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > with at most hopes or rumors of 3 others (splay trees, Digiboard's LZ, > > and Gandalf's). > > Thanks Vernon. I'll inform the 1000's of customers running FZA that > it is only a virtual algorithm :-) Serious inquiries are welcome as > aways. What? How can you possibly be offended by that? Unless Dave lost some mail or misspoke, he does not have the necessary words from you to put into the CCP draft. That makes your algorithm at best a rumor as far as PPP is concerned. No, FZA is completely a rumor since the only way anyone might find out about it is by asking around. About CCP algorithm negotiating...it might be cleaner to only use the OUI scheme for negoticating the compression algorithm, but only if we use something like an OUI of 00-00-00 for Predictor or whatever we pick for the lingua franca. I have no great enthusiasm for Predictor, despite now having an implementation of it. It is absolutely clear that PPP compression requires at least one completely open, free, documented compression algorithm for the majority of PPP installations, host installations. So far, the only candidate is Predictor, and it is almost too late for any new nominees. If CCP is only to be used to allow a pair of dedicated router boxes to discover they have the same OUI and use a proprietary compression algorithm, then the whole PPP compression protocol effort has no business being assoicated with the IETF, and this group should be disbanded (perhaps to be re-formed as a router-box vendor consortium). If you have an algorithm that you want listed, send it to Dave. Let's get on with things and publish a draft! vjs From owner-ppp-comp Wed Oct 13 17:10:48 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onGGQ-0000YBa; Wed, 13 Oct 93 17: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: Re: Last chance at CCP before release Date: Wed, 13 Oct 1993 16:09:45 PDT Message-ID: <9310132309.AA01259@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Oct 13, 15:47, Vernon Schryver wrote: } Unless Dave lost some mail or misspoke, he does not have the necessary } words from you to put into the CCP draft. That makes your algorithm at } best a rumor as far as PPP is concerned. No, FZA is completely a rumor } since the only way anyone might find out about it is by asking around. Agreed. I do not have a proposal at this time from Gandalf, and Dave has thus far been reluctant to even send me a NDA. -- From owner-ppp-comp Thu Oct 14 08:16:59 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onUMw-00001Va; Thu, 14 Oct 93 08:13 PDT Sender: owner-ppp-comp X-Path: wellfleet.com!cbrown From: cbrown@wellfleet.com (Caralyn Brown) To: ppp-comp@bungi.com Subject: Re: Compression For other protocols. Date: Thu, 14 Oct 93 11:10:22 EDT Message-ID: <9310141510.AA15399@pobox.wellfleet> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > >Is anyone else interested in developing a standard for > >data compression for Frame Relay (RFC1490 (1294)) ? > > in the context of PPP/FR, I believe that we already have... > > ============================================================================= > Don't blame ACC; they think I'm nuts too! > > > Perhaps this would an example of an application that would have benefitted from the parameter negotiations over frame relay document. That way, if you were running in a way that was not strictly point-to-point, you could still negotiate compression on individual VCs. c From owner-ppp-comp Thu Oct 14 09:17:38 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onVJe-0000B6a; Thu, 14 Oct 93 09:14 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 at CCP before release Date: Thu, 14 Oct 1993 12:11:42 -0400 (EDT) Message-ID: <9310141611.AA01051@donut.gandalf.ca> References: <<9310132147.AA09403@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > What? How can you possibly be offended by that? I'm offended in that we have offered to sell the FZA algorithm for months. Just because we didn't give the code away, it becomes a rumour? All serious inquiries have been directed to our marketting director and dealt with. At least one other company is in the process of porting the code. If you want information, and are willing to pay, call! I have provided Rand test results, memory sizes, benchmarking on the Corpus, and loads of other information to the net on FZA. If I gave out any more, you could go away and implement your own. I have even offered to loan a pair of our bridges out for evaluation, just to prove the algorithm works as advertised. How much further can I go without giving the code away. On the other hand, we've had at best rumours of PPC. I have tried contacting the parties mentioned on the list to no avail. Then there's other LZ based algorithms "coming". Call them rumours if you want. > Unless Dave lost some mail or misspoke, he does not have the necessary > words from you to put into the CCP draft. Funny, I did have mailer problems this week. Are you psychic? And since when was it manditory to respond to e-mail immediately. The information Dave has asked for will be prepared in good time and sent. The information he has asked for, or at least the relevant parts, has been on the list for months. There's a big difference in putting some public domain code in the spec. It's certainly a lot easier to describe the licensing isn't it. > That makes your algorithm at > best a rumor as far as PPP is concerned. No, FZA is completely a rumor > since the only way anyone might find out about it is by asking around. Try asking me. And no, I'm not about to give away what we consider trade secrets over the net. And don't bother to call if you expect to get it for free. I made that clear many times. It's quite clear from your postings that if we're charging for FZA you're not buying. Fine. There's no point in even signing an NDA in your case. Any other serious inquiries are welcome. -- 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 Oct 14 09:42:16 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onVj2-00009ta; Thu, 14 Oct 93 09:40 PDT Sender: owner-ppp-comp X-Path: vnet.IBM.COM!jo'donnell From: jo'donnell@vnet.IBM.COM To: ppp-comp@bungi.com Subject: A concern about PPP/FR for compression Date: Thu, 14 Oct 93 12:13:55 EDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk One thing that is different about PPP and FR is that in a leased line context, line speed is a constant. So presumably for slower CPU/faster lines, one would test the throughput for a given combination of line speed and CPU on both ends of the link. Once done, one knows whether compression will help. With VCs instead of leased lines I would think that one would not always know in advance either the line speed or the CPU speed on the other end. So, what I'm trying to get at is, if the consensus is that PPP/FR is how we're going to standardise compression, I'd like to see the protocol make some determination that the latency introduced by compressing will not exceed the latency removed by sending compressed data. Something Like timing the period between a request and an ack to determine line speed, from that calculate the line-latency removed by the compression algorithm. From the cpu speed and an avg. instructions per byte compressed determine the compression-introduced latency. And compare the two before ack or reject. From owner-ppp-comp Thu Oct 14 10:00:14 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onW0q-0000RBa; Thu, 14 Oct 93 09:58 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: A concern about PPP/FR for compression Date: Thu, 14 Oct 1993 09:58:34 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "A concern about PPP/FR for compression" on Oct 14, 12:13, jo'donnell@vnet.IBM.COM writes:] > So, what I'm trying to get at is, if the consensus is that > PPP/FR is how we're going to standardise compression, I'd like to > see the protocol make some determination that the latency introduced > by compressing will not exceed the latency removed by sending compressed > data. Compression will not "remove latency". Latency is fixed at the RTT of the entire path (not just this hop), and compression will not really help with this. What compression can do is offer to increase the amount of data sent over a link. To figure the best algorithm requires you to know how fast you can emit data from the compression engine, how much compression you get, how fast your link is, and how much data your source can provide. To say nothing of variables like pre-compressed data, encryption, etc, etc. > Something Like timing the period between a request and an ack to determine > line speed, from that calculate the line-latency removed by the compression > algorithm. From the cpu speed and an avg. instructions per byte > compressed determine the compression-introduced latency. > And compare the two before ack or reject. You can't determine the line speed this way. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 14 10:13:38 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onWDt-0000Dha; Thu, 14 Oct 93 10:12 PDT Sender: owner-ppp-comp X-Path: fcr.com!brad From: Brad Parker To: ppp-comp@bungi.com Subject: Enough! Date: Thu, 14 Oct 1993 13:03:50 -0400 Message-ID: <9310141703.AA23346@stemwinder.fcr.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [ warning: potentially inflamitory material enclosed. contends sold by... ] At the risk of being flamed, this is all ridiculous. IM-not-so-HO, no one is going to make any real money selling compression algorithms for *PPP*. Ignore your marketing people and lawyers. They are wrong. (I would wager good money that the folks at IBM, Unisys and BT have not made nearly enough money on licensing v.42bis - a standard no less - to justify all the time their lawyers and sales people spend on licensing it. There simply is not a enough enough volume of potential customers.) Let's stop wasting everyone's time and get this spec done. In the end the compression method we use will become irrelivant anyway, as the market will force us all to use one and everyone will have it. it's the way of the world. waaahhhh! ;-) -brad From owner-ppp-comp Thu Oct 14 10:17:28 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onWHf-0000bFa; Thu, 14 Oct 93 10:16 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 at CCP before release Date: Thu, 14 Oct 1993 13:13:59 -0400 (EDT) Message-ID: <9310141714.AA01080@donut.gandalf.ca> References: <<9310132309.AA01259@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Agreed. I do not have a proposal at this time from Gandalf, and Dave > has thus far been reluctant to even send me a NDA. Considering the information you have asked for has been available on this list for many months, I find the above statement offensive. Perhaps, in retrospect, I should have written the actual text months ago, and avoided all misrepresentation of FZA (patent issues, indemnity) by yourself. The fact that no NDA has been signed is another matter. What information do think could be covered in an NDA that hasn't been publicly discussed? Everything in our algorithm has been discussed in various books, archivers, and magazines. We've just put them together, carefully avoiding all the patents. I doubt these would be discussed even under an NDA, because they would be "obvious to one skilled in the art". An NDA would not prevent you from developing your own clone. I am preparing the information in question. Either wait for it or publish the draft, no matter. It's only a draft isn't it? -- 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 Oct 14 11:54:30 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onXnq-0000EQa; Thu, 14 Oct 93 11:53 PDT Sender: owner-ppp-comp X-Path: vnet.IBM.COM!jo'donnell From: jo'donnell@vnet.IBM.COM To: ppp-comp@bungi.com Subject: compression for ppp/fr Date: Thu, 14 Oct 93 14:02:30 EDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > So, what I'm trying to get at is, if the consensus is that > > PPP/FR is how we're going to standardise compression, I'd like to > > see the protocol make some determination that the latency introduced > > by compressing will not exceed the latency removed by sending compressed > > data. > Compression will not "remove latency". Latency is fixed at the RTT of the > entire path (not just this hop), and compression will not really help > with this. What compression can do is offer to increase the amount of data > sent over a link. Lets agree on terms. time for a hop = time on box A + time on link + time on box B Increasing the amount of data the link can send by compressing depends on decreasing the total time for a hop. If you increase the time for a hop because the time on the boxes increases more than the time on the link decreases, you decrease the amount of data the link can send. > To figure the best algorithm requires you to know how > fast you can emit data from the compression engine, how much compression > you get, how fast your link is, and how much data your source can provide > To say nothing of variables like pre-compressed data, encryption, etc, etc. I mean that whether an algorithm should be used at all should be determined at link initiation by your protocol. What you need to know and don't can be determined. Compression engine emit rate is going to be a function of instructions to compress and MIPS for your CPU. Average compression ratio is a constant for your algorithm You determined it in your testing. Line speed is the only problem. > > Something Like timing the period between a request and an ack to determine > > line speed, from that calculate the line-latency removed by the compression > > algorithm. From the cpu speed and an avg. instructions per byte > > compressed determine the compression-introduced latency. > > And compare the two before ack or reject. > > You can't determine the line speed this way. > How can you determine line speed? Jim O'Donnell From owner-ppp-comp Thu Oct 14 12:33:42 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onYPZ-000099a; Thu, 14 Oct 93 12:32 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: compression for ppp/fr Date: Thu, 14 Oct 1993 12:32:27 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "compression for ppp/fr" on Oct 14, 14:02, jo'donnell@vnet.IBM.COM writes:] > Lets agree on terms. > > time for a hop = time on box A + time on link + time on box B > > Increasing the amount of data the link can send > by compressing depends on decreasing the total time for a hop. > If you increase the time for a hop because the time on the boxes > increases more than the time on the link decreases, you decrease > the amount of data the link can send. Nope. Increasing the amount of data the link can send depends only on the signalling rate. For example, let's say that we have a dial-up modem link. I call another phone line in the same building - we get 14,400 bps, with a latency of 400ms due to the modem scramblers, V.42/V.42bis engines and prop. delay of the link. Now, I call a phone accross the country and (for some reason) it gets routed via satellite. We still get 14,400 bps, 400ms due to the scramblers etc, but now we have added another 473 ms RT latency (22,000/186,000 up, down, up and down) for a total of 873ms of latency. But we still have 14,400 bps. We have not reduced the amount of data the link can carry by increasing the latency. > What you need to know and don't can be determined. > Compression engine emit rate is going to be a function of instructions > to compress and MIPS for your CPU. Nope. It is dependant on the data stream, too. > Average compression ratio is a constant for your algorithm > You determined it in your testing. Nope. I determined it for ONE DATA SET ONLY. Real life is different, and always will be. > Line speed is the only problem. Line speed is ONE problem. > > > > You can't determine the line speed this way. > > > How can you determine line speed? You must see how much data the link can accept. I do this in a real-time fashion currently by observing the incoming (uncompressed) data rate, and the outgoing (compressed) data rate. I see how many bytes flowed into the compression engine in one second (sampled every second, averaged over the last 8), and how many bytes flowed out the physical link (sampled every second, averaged every 8). If your hardware link speed is (for example) 128Kbps, you can't stuff any more than 128Kbits worth of data down this link every second. Doesn't matter if it is compressed or uncompressed. It is the link speed. If you get 8:1 compression, and your compression engine is good, you can get 1Mbps effective data flow across this link. If the source data is uncompressable (and you are using predictor pre-CCP), you will get 113Kbps effective data flow across this link. Note that this assumes that you really can transmit 128Kbps on the link. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 14 13:14:06 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onZ2f-0000NBa; Thu, 14 Oct 93 13:12 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: A concern about PPP/FR for compression Date: Thu, 14 Oct 93 15:46:19 EDT Message-ID: <1527.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk There is already a PPP/FR draft, which will be issued as an RFC "Real Soon Now". As it says: Applicability This specification is intended for those implementations which desire to use facilities which are defined for PPP, such as the Link Control Protocol, Network-layer Control Protocols, authentication, and compression. These capabilities require a point-to-point relationship between peers, and are not designed for multi-point or multi-access environments. You could certainly use the LCP Echo function for determining line speed and latency. This has been suggested for IPX as well. However, I expect that it is more of an implementation design problem than a "testing" problem. Any algorithm that introduces more latency than can be regained from the compression is unlikely to be very popular. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Fri Oct 15 06:46:50 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onpT0-00009Ca; Fri, 15 Oct 93 06:45 PDT Sender: owner-ppp-comp X-Path: vnet.IBM.COM!jo'donnell From: jo'donnell@vnet.IBM.COM To: ppp-comp@bungi.com Subject: Effective data flow Date: Fri, 15 Oct 93 09:42:06 EDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk compression engine = algorithm and CPU compression engine emission = CPU mips / avg. number of algorithms assembler instructions per 1000 bytes I think it's kilobytes/second. the avg number of inst to compress 1000 bytes is determined by compressing "representative" data. Yes I know the world doesn't look like a bell-shaped curve, but sometimes we choose to treat it as if it were. (and over-engineer by subtracting a percentage) Given a poor enough CPU, (or a fast enough line), any compression engine's throughput can become the throttling factor for the line. I think it's been called "starving the line." I still think there's a problem that isn't being addressed. I still think that you should compare the line speed kbs to the compression engine's througput before accepting compression. Given that my product is software only and not a software/hardware combination, I don't have control over what kind of MIPs customers might give my code to run with. I would like to see it behave well no matter what they do. Imagine someone running a bridge on a 286. Or imagine 10 MEG lines connected to a 486. I'd rather not have the user figure out whether to turn compression on/off for each connection. I'd rather configure the product to use compression whenever it will help and for higher line speeds I think that it will not. Otherwise, why is compression WAN only, Why not for LANs also? From owner-ppp-comp Fri Oct 15 08:29:52 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onr4u-0000UQa; Fri, 15 Oct 93 08:28 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Effective data flow Date: Fri, 15 Oct 1993 08:28:08 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Effective data flow" on Oct 15, 9:42, jo'donnell@vnet.IBM.COM writes:] > I think it's been called "starving the line." > > I still think there's a problem that isn't being addressed. > I still think that you should compare the line speed kbs to the > compression engine's througput before accepting compression. Please review my compression document (comp.doc/comp.ps, available on sgi.com:other/ppp-comp). I cover this In Exquisite Detail. In particular, observe what RGF stands for :-) > Imagine someone running a bridge on a 286. Or imagine 10 MEG lines > connected to a 486. I'd rather not have the > user figure out whether to turn compression on/off for each connection. > I'd rather configure the product to use compression whenever it will > help and for higher line speeds I think that it will not. Otherwise, > why is compression WAN only, Why not for LANs also? Novell offers a software-only compression (at the moment). We run on a wide variety of platforms, with an even wider range of speeds. While you *can* figure out which is good/bad for a given link speed, sometimes it is better never to run compression. If you are sending pre-compressed data, or running encryption, compression generally does not help - and there is no point turning it on for that link. You would just waste CPU cycles trying to compress data that couldn't be compressed. You must run the algorithm with some data, on the platform, to figure out what it can do. I would suggest that you do it during initialization of your product (compress a fixed-size block with each algorithm that you run - best would be a number of blocks, comprising the best, worst and "average" cases). Once you know how fast you can produce data, you can figure out which algorithm to use on each link. Obviously, if you want to do this, you need to know the speed of the link prior to bringing up compression. On Async lines, you know the speed. On Ethernet, you have a good idea of the speed (although the adapter can make a big difference). On internally-clocked Sync lines, you know the speed. On externally-clocked Sync lines, you have to figure out the speed. We do this by measuring the interval between character transmissions upon link open - perhaps not the best approach, but it works in the vast majority of cases. With algorithms that are fast enough, you can also use them on LANS, although the benefit can be smaller. LANs typically don't run at 100% link utilization, whereas WANs *should* run at 100% link utilization. If you have a LAN running at 100% utilization, and have a good compression engine, then compression can help. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Fri Oct 15 11:36:05 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ontzB-00009ha; Fri, 15 Oct 93 11:34 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: Last chance at CCP before release Date: Fri, 15 Oct 93 12:33:28 -0600 Message-ID: <9310151833.AA23960@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > What? How can you possibly be offended by that? > > I'm offended in that we have offered to sell the FZA algorithm for months. > > Just because we didn't give the code away, it becomes a rumour? All > serious inquiries have been directed to our marketting director and > dealt with. At least one other company is in the process of porting the > code. If you want information, and are willing to pay, call! > ... Yes, it is a rumor. What "V.Schryver, Intrepid IETF pain in the ass" knows is only that various outfits want to sell, PPP compression code, including HP, Gandalf, and Stac. He knows nothing more except those rumors. Someone else, "V.Schryver, aging hack", knows somewhat more than rumors. His silence can be taken as an expression of the official disinterest of his employer in paying money for PPP compression code. We are talking about IETF standards. Anything not written down in IETF standards or drafts is a "rumor." Publishing advertizements in the trade press would not change the rumor character of the the Gandalf compression product as far as the IETF is concerned. > On the other hand, we've had at best rumours of PPC. I have tried contacting > the parties mentioned on the list to no avail. Then there's other LZ based > algorithms "coming". Call them rumours if you want. Yes, everything not in the draft is a "rumor." > And since when was it manditory to respond to e-mail immediately. The > information Dave has asked for will be prepared in good time and sent. > The information he has asked for, or at least the relevant parts, has > been on the list for months. My reading of this list contradicts that statement. It has been months since Dave asked for the necessary info. I certainly could not write what Dave has wanted from what you have written in this list or to me (I.e. neither V.Schryver has the answers.) I think Dave has been asking too much until his most request, when I understood him to relax it to little more than contact info, bet even then I could not answer on your behalf. I have finally learned something about some people here. Some of you are very different from the "editors" of documents I encounter at work. Many "editors" are really authors and do not take kindly to having text proposed for their documents. The best way to get changes in is to communicate the ideas and let them suppy their own words. Here, at least with some people, things are different, and progress is made only by propose explict words for the document. Simply send Dave what you want the CCP draft to say about FZA; I bet that will work. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Oct 15 13:49:32 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0onw4I-0000T8a; Fri, 15 Oct 93 13:48 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Gandalf FZA draft Date: Fri, 15 Oct 93 16:12:59 EDT Message-ID: <1544.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I have assisted Dave Carr in getting the Gandalf FZA draft ready. Here's version 1. It will be posted in internet-drafts on Monday, updated with any comments received by then. Network Working Group Dave Carr Internet Draft Gandalf expires in six months October 1993 PPP Gandalf FZA Compression Protocol draft-ietf-pppext-gandalf-nn.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. The PPP Compression Control Protocol [2] provides a method to negotiate and utilize compression protocols over PPP encapsulated links. This document describes the use of the Gandalf FZA data compression algorithm for compressing PPP encapsulated packets. Carr expires in six months [Page i] DRAFT Gandalf FZA October 1993 1. Introduction FZA is a high performance LZA derivative which maximizes compression at the expense of memory and CPU. Compression performance can be adjusted based on CPU and memory available. Multiple PPP packets can be combined in a single compressed frame, or a single PPP packet can be spread across multiple frames. 1.1. Licensing Source and object licenses are available on a non-discriminatory basis for either a royalty or fixed price arrangement. Patent indemnity is included with the license. Carr expires in six months [Page 1] DRAFT Gandalf FZA October 1993 2. Sending FZA Datagrams Before any FZA packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the CCP Control Protocol must reach the Opened state. Exactly one FZA datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 00FD (compressed datagram). The maximum length of the FZA datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated packet. Padding The FZA packets require the negotiation of the Self-Describing- Padding Configuration Option [3] at LCP Link Establishment. Reliability and Sequencing The FZA algorithm expects a reliable link, as described in "PPP Reliable Transmission" [4]. The FZA algorithm expects the packets to remain in sequence. Data Expansion The maximum expansion of Gandalf FZA is 2:1. However, typical expansion on pre-compressed data is 1.01:1. Expanded data is sent to maintain the integrity of the compression history. When the expansion exceeds the size of the PPP Maximum Receive Unit for the link, the expanded packet is sent in multiple PPP frames. The compressed data contains an indication of the end of the original packet. 2.1. Packet Format A summary of the Gandalf FZA packet 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Carr expires in six months [Page 2] DRAFT Gandalf FZA October 1993 PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the Gandalf FZA compression protocol is successfully negotiated by the PPP Compression Control Protocol [2], the value is 00FD hex. This value MAY be compressed when Protocol-Field- Compression is negotiated. Compressed Data The compressed PPP encapsulated packet. Carr expires in six months [Page 3] DRAFT Gandalf FZA October 1993 3. Configuration Option Format Description The CCP Gandalf-FZA Configuration Option negotiates the use of Gandalf FZA on the link. By default or ultimate disagreement, no compression is used. A summary of the Gandalf-FZA 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 | History Buffer | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type (6) Length 4 History Count The History Buffer field is two octets, and specifies the maximum size of the Compression History. Valid values are 4096, 8192, 16384, and 32768. Carr expires in six months [Page 4] DRAFT Gandalf FZA 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] Rand, D., "The PPP Compression Control Protocol (CCP)", work in progress. [3] Simpson, W.A., "PPP LCP Extensions", work in progress. [4] Rand, D., "PPP Reliable Transmission", work in progress. Acknowledgments Editting and formatting by Bill Simpson. Carr expires in six months [Page 5] DRAFT Gandalf FZA 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 Carr Gandalf Data Limited 130 Colonnade Road South Napean, Ontario, Canada K2E 7M4 (613) 723-6500 (613) 226-1717 Fax Email: dcarr@gandalf.ca Carr expires in six months [Page 6] DRAFT Gandalf FZA October 1993 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. Sending FZA Datagrams ................................. 2 2.1 Packet Format ................................... 2 3. Configuration Option Format ........................... 4 SECURITY CONSIDERATIONS ...................................... 5 REFERENCES ................................................... 5 ACKNOWLEDGEMENTS ............................................. 5 CHAIR'S ADDRESS .............................................. 6 AUTHOR'S ADDRESS ............................................. 6 Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Fri Oct 15 19:52:56 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oo1kZ-0000Uua; Fri, 15 Oct 93 19:52 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: Gandalf FZA draft Date: Fri, 15 Oct 93 20:51:52 -0600 Message-ID: <9310160251.AA26924@rhyolite.wpd.sgi.com> References: <> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > I have assisted Dave Carr in getting the Gandalf FZA draft ready. > Here's version 1. It will be posted in internet-drafts on Monday, > updated with any comments received by then. > .... Shouldn't something somewhere mention the CCP compression protocol number involved? Whether OUI-based or one fo the 255 special cases? I'm sorry if it's here, and I missed it, or it has already been added to the CCP draft. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Fri Oct 15 22:24:59 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oo46e-0000ZSa; Fri, 15 Oct 93 22:23 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Gandalf FZA draft Date: Fri, 15 Oct 1993 22:22:24 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Gandalf FZA draft" on Oct 15, 20:51, Vernon Schryver writes:] > Shouldn't something somewhere mention the CCP compression protocol > number involved? Whether OUI-based or one fo the 255 special > cases? I'm ASSuming that Dave wants one of the Standard compression numbers, and have assigned it. It will appear in the next draft, assuming Tommy gets me his info. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Sat Oct 16 05:23:27 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ooAel-0000CZa; Sat, 16 Oct 93 05:22 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Gandalf FZA draft Date: Fri, 15 Oct 93 23:20:52 EDT Message-ID: <1548.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Shouldn't something somewhere mention the CCP compression protocol > number involved? Whether OUI-based or one fo the 255 special > cases? > It's there: A summary of the Gandalf-FZA Configuration Option format is shown below. The fields are transmitted from left to right. Type (6) > I'm sorry if it's here, and I missed it, or it has already > been added to the CCP draft. > The number also has to be added to the CCP draft. I have another draft coming out tomorrow, Stacker LZS, which I assigned 5, assuming: 1 OUI 2 Predictor 1 3 Predictor 2 4 unassigned (just in case Dave's already assigned it) 5 Stacker 6 Gandalf 7 MicroSoft 8 HP? Just getting the ball rolling. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Sat Oct 16 06:40:00 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ooBqK-00004La; Sat, 16 Oct 93 06:38 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Stacker FZS draft Date: Sat, 16 Oct 93 08:25:07 EDT Message-ID: <1551.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Here's the Stacker draft. There will be more comments and licensing info on Monday, I hope. Network Working Group Robert Lutz Internet Draft Stac Electronics expires in six months October 1993 PPP Stacker LZS Compression Protocol draft-ietf-pppext-stacker-nn.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. The PPP Compression Control Protocol [2] provides a method to negotiate and utilize compression protocols over PPP encapsulated links. This document describes the use of the Stacker LZS data compression algorithm, with single or multiple compression histories, for compressing PPP encapsulated packets. Lutz expires in six months [Page i] DRAFT Stacker LZS October 1993 1. Introduction Starting with a sliding window compression history, similar to LZ1 [3], Stac Electronics developed a new, enhanced compression algorithm identified as Stacker LZS. The LZS algorithm is optimized to compress all file types as efficiently as possible. Even string matches as short as two bytes are effectively compressed. The Stacker LZS compression algorithm supports both single compression history communication and multiple compression history communication. A single compression history will require the minimum amount of memory to implement, but may not provide as much compression as a multiple history implementation. Using multiple compression histories can improve the compression ratio of a communication link by associating separate compression histories with separate virtual links of communication. In general, each virtual link will transmit data that is independent of other virtual links. 1.1. Licensing Source and object licenses are available on a non-discriminatory basis for either a royalty or fixed price arrangement. Hardware implementations are also available. Patent indemnity is included with the license. Lutz expires in six months [Page 1] DRAFT Stacker LZS October 1993 2. Sending LZS Datagrams Before any LZS packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the CCP Control Protocol must reach the Opened state. Exactly one LZS datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 00FD (compressed datagram). The maximum length of the LZS datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated packet. Padding The LZS Information field contains an integral length field, which is used to disambiguate padding. When expansion has resulted in the number of octets specified in the length, the remainder of the packet is considered padding. This allows trailing bits as well as octets to be considered padding. Reliability and Sequencing By default, the Compression History will be reset for each LZS packet. In this case, the algorithm does not depend on a reliable link and does not require that packets be delivered in sequence. Optionally, each Compression History may be reset at the discretion of the transmitter. Use of this feature requires a reliable link, as described in "PPP Reliable Transmission" [4], and expects the packets to be delivered in sequence. When a transmitter resets a Compression History, no other indication needs to be sent to the receiver, other than that provided within the compressed information. Data Expansion The maximum expansion of Stacker LZS is 12.5%. When the expansion exceeds the size of the peer's Maximum Receive Unit for the link, the expanded packet is sent in multiple PPP frames. When such frames are delivered out of sequence, the parity check in each frame will detect the failure. When expansion is detected, the PPP packet MAY be sent without compression. Any following LZS packet will indicate a reset of Lutz expires in six months [Page 2] DRAFT Stacker LZS October 1993 its Compression History. Lutz expires in six months [Page 3] DRAFT Stacker LZS October 1993 2.1. Packet Format The encapsulation differs based on the negotiated History Count. If the History Count is one, then the following format is used. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | Uncompressed Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LCB or CRC | +-+-+-+-+-+-+-+-+ If the History Count is greater than one, then the following format is used. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | History Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Uncompressed Length | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LCB or CRC | +-+-+-+-+-+-+-+-+ PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the Stacker LZS compression protocol is successfully negotiated by the PPP Compression Control Protocol [2], the value is 00fd hex. This value MAY be compressed when Protocol-Field- Compression is negotiated. History Number The number of the compression history which should be used. Lutz expires in six months [Page 4] DRAFT Stacker LZS October 1993 Uncompressed Length The number of octets which were in the original PPP encapsulated packet, prior to compression. Compressed Data The compressed PPP encapsulated packet. LCB or CRC By default, a simple Longitudinal Check Byte (LCB) will be appended to each packet. The LCB MUST be initialized to FF(hex) at the beginning of each packet. The LCB is one octet, and is the Exclusive-OR of each byte of the original, uncompressed data. If the CRC option is successfully negotiated, a CRC will be appended to each packet instead of the LCB. The CRC MUST be initialized to FFFF(hex) at the beginning of each packet. The CRC is two octets, and is based on the following polynomial: x^16 + x^12 + x^5 + 1 Lutz expires in six months [Page 5] DRAFT Stacker LZS October 1993 3. Configuration Option Format Description The CCP Stacker-LZS Configuration Option negotiates the use of Stacker LZS on the link. By default or ultimate disagreement, no compression is used. A summary of the Stacker-LZS 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 | History Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Mode | Reset Mode | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type (5) Length 6 History Count The History Count field is two octets, and specifies the maximum number of Compression Histories. Valid values range from 1 to 65768. Check Mode The Check Mode MAY be set to indicate support of CRC parity. 1 LCB 2 CRC Reset Mode The Reset Mode MAY be set to indicate support for maintaining a Compression History for more than a single packet. Lutz expires in six months [Page 6] DRAFT Stacker LZS October 1993 1 Single Packet 2 Multiple Packets Lutz expires in six months [Page 7] DRAFT Stacker LZS 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] Rand, D., "The PPP Compression Control Protocol (CCP)", work in progress. [3] Lempel, A. and Ziv, J., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions On Information Theory, Vol. IT-23, No. 3, May 1977. [4] Rand, D., "PPP Reliable Transmission", work in progress. Acknowledgments Editting and formatting by Bill Simpson. Lutz expires in six months [Page 8] DRAFT Stacker LZS 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: Robert Lutz Stac Electronics 5993 Avenida Encinas Carlsbad, CA 92008 (619)431-7474 Email: stac/stac/bobl%stac_electronics@mcimail.com Lutz expires in six months [Page 9] DRAFT Stacker LZS October 1993 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. Sending LZS Datagrams ................................. 2 2.1 Packet Format ................................... 4 3. Configuration Option Format ........................... 6 SECURITY CONSIDERATIONS ...................................... 8 REFERENCES ................................................... 8 ACKNOWLEDGEMENTS ............................................. 8 CHAIR'S ADDRESS .............................................. 9 AUTHOR'S ADDRESS ............................................. 9 Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Sun Oct 17 10:32:23 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oobx9-00005Ea; Sun, 17 Oct 93 10:31 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Puddle Jumper draft Date: Sun, 17 Oct 93 13:21:24 EDT Message-ID: <1554.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Here's the first draft of _my_ Predictor negotiation, since Dave refused to add parameters for negotiate. I called it Puddle Jumper for variety. Network Working Group W A Simpson Internet Draft Daydreamer expires in six months October 1993 PPP Puddle Jumper Compression Protocol draft-ietf-pppext-puddlejumper-nn.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. The PPP Compression Control Protocol [2] provides a method to negotiate and utilize compression protocols over PPP encapsulated links. This document describes the use of the Puddle Jumper compression protocol for compressing PPP encapsulated packets. Simpson expires in six months [Page i] DRAFT PPP Puddle Jumper October 1993 1. Introduction The Puddle Jumper compression algorithm is entirely based on the Predictor algorithm [2]. Puddle Jumper merely adds the ability to negotiate some parameters for greater flexibility, and is renamed to avoid tradename conflicts. The nature of the hash function is highly dependent on the least significant bits of the original data. Puddle Jumper provides superior compression for short packets through negotiable dictionary initialization of likely successive values. Puddle Jumper is optimized for packetization. The hash function is re-initialized on every frame, although the compression history is retained across multiple frames. This serves to separate different types of datagram headers within the compression history. 1.1. Licensing Puddle Jumper is available without license fees. The included source code has been placed in the public domain. Although care has been taken to ensure that the included source code does not infringe any patents, there is no assurance that it is not covered by a patent. Use the code at your own risk. Simpson expires in six months [Page 1] DRAFT PPP Puddle Jumper October 1993 2. Puddle Jumper Packets Before any Puddle Jumper packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the CCP Control Protocol must reach the Opened state. Exactly one Puddle Jumper datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 00FD (compressed datagram). The maximum length of the Puddle Jumper datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated packet. Only packets with PPP Protocol numbers in the range 0021 to 00FA hex are compressed. Other PPP packets are always sent uncompressed. Rationale: Most PPP Protocols are sent infrequently. Changes to the compression history would not persist, which would result in a net expansion. Also, LCP packets MUST NOT be compressed, to ensure recognition in a partially Opened state. Padding The Puddle Jumper packets require the negotiation of the Self- Describing-Padding Configuration Option [3] at LCP Link Establishment. Rationale: Every octet counts. A length field would add two octets all of the time. Self-Describing-Padding adds one extra octet less than half the time. Reliability and Sequencing The Puddle Jumper algorithm does not require a reliable link. Instead, it relies on renegotiation of the Compression Control Protocol [2] to indicate loss of sequence. Puddle Jumper expects the packets to be delivered in sequence. Rationale: Modern serial links are very reliable, with a transmission error rate on the order of less than 1/1000. Restart of the transmission history at this rate should be considerably more efficient then adding overhead to every frame. Simpson expires in six months [Page 2] DRAFT PPP Puddle Jumper October 1993 Data Expansion When data expansion is detected, the PPP packet MUST be sent without compression. When a packet is received with PPP Protocol numbers in the range 0021 to 00FA hex, it is assumed that the packet would have caused expansion. The packet is locally compressed to update the compression history. Rationale: By using the PPP Protocol field for compression detection, a field with a bit for compression is eliminated. 2.1. Packet Format A summary of the Puddle Jumper packet 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | Initial | Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the Puddle Jumper compression protocol is successfully negotiated by the PPP Compression Control Protocol [2], the value is 00FD hex. This value MAY be compressed when Protocol-Field- Compression is negotiated. Initial The first octet of uncompressed data. This is usually the PPP Protocol number for the compressed packet. This octet is also used as the initial value of the hash function for compressing the remainder of the packet. Simpson expires in six months [Page 3] DRAFT PPP Puddle Jumper October 1993 Data The compressed PPP encapsulated packet, excluding the Initial octet. The format is described in the "Compressed Data" appendix. CRC The CRC of the original, uncompressed data, including the Initial octet. This is used to detect that a packet has been lost which resulted in an invalid compression history. For convenience in implementation, the same algorithm is used which is already described for the HDLC FCS [4]. Simpson expires in six months [Page 4] DRAFT PPP Puddle Jumper October 1993 3. Configuration Option Format Description The CCP Puddle Jumper Configuration Option negotiates the use of Puddle Jumper on the link. By default or ultimate disagreement, no compression is used. A summary of the Puddle Jumper 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 | History | Preset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mask | Shift | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type (4) Length 6 History The History field specifies the size of the compression history in powers of 2. Valid values range from 12 to 16. Preset The Preset field indicates the method used for initialization of the compression history. Because newer methods will always be assigned larger numbers only a smaller number is allowed in a Configure-Nak. 0 The value zero is used throughout. Mask The Mask indicates the mask used in the hash function. Simpson expires in six months [Page 5] DRAFT PPP Puddle Jumper October 1993 Shift The Shift indicates the shift used in the hash function. Valid values range from 4 to 8. Simpson expires in six months [Page 6] DRAFT PPP Puddle Jumper 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] Rand, D., "The PPP Compression Control Protocol (CCP)", work in progress. [3] Simpson, W.A., "PPP LCP Extensions", work in progress. [4] Simpson, W.A., "PPP in HDLC Framing", work in progress. Acknowledgments Simpson expires in six months [Page 7] DRAFT PPP Puddle Jumper 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: William Allen Simpson Daydreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 EMail: Bill.Simpson@um.cc.umich.edu Simpson expires in six months [Page 8] DRAFT PPP Puddle Jumper October 1993 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. Puddle Jumper Packets ................................. 2 2.1 Packet Format ................................... 3 3. Configuration Option Format ........................... 5 SECURITY CONSIDERATIONS ...................................... 7 REFERENCES ................................................... 7 ACKNOWLEDGEMENTS ............................................. 7 CHAIR'S ADDRESS .............................................. 8 AUTHOR'S ADDRESS ............................................. 8 Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Sun Oct 17 16:31:04 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oohYO-00008va; Sun, 17 Oct 93 16:30 PDT Sender: owner-ppp-comp X-Path: cs.tu-berlin.de!cabo From: Carsten Bormann To: ppp-comp@bungi.com Subject: Re: Lapb draft RFC: N2 should not be changed to 3 Date: Mon, 18 Oct 1993 00:28:53 +0100 Message-ID: <199310172328.AA21671@mail.cs.tu-berlin.de> References: <<9310052323.AA06772@va.SJF.Novell.COM>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Sorry for not waking up earlier (I can only offer my relocation to Bremen and the resulting mailer woes as a weak apology): N2 should be 10 (or sometimes 8, depending on how old the version of X.25 you read is), not 3. 3 is a decent default window size, but not a decent default maximum retry counter. Gruesse, Carsten ;-) Jeez, setting N2 to 3 would really break our aging Deutsche ;-) Bundespost Telekom X.25 lines whenever the snow starts to melt... From owner-ppp-comp Mon Oct 18 10:23:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ooyIM-00007na; Mon, 18 Oct 93 10:22 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: Puddle Jumper draft Date: Sun, 17 Oct 93 13:01:03 -0600 Message-ID: <9310171901.AA10859@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Here's the first draft of _my_ Predictor negotiation, since Dave refused > to add parameters for negotiate. I called it Puddle Jumper for variety. > .... > Data Expansion > When data expansion is detected, the PPP packet MUST be sent > without compression. > > When a packet is received with PPP Protocol numbers in the range > 0021 to 00FA hex, it is assumed that the packet would have caused > expansion. The packet is locally compressed to update the > compression history. > > Rationale: By using the PPP Protocol field for compression > detection, a field with a bit for compression is eliminated. Consier what happens when the receiver detects a bad CRC on a compressed packet, and drops out of CCP by sending a config-request. How does the receiver distinguish incompressible puddle-jumper packets packets transmitted by the peer before the peer noticed the configure request and ordinary packets from after? In other words, how does the peer know when to stop trying to de-compress packets with protocols 0x21 to 0xfa? The same problem happens at start-up. How does the receiver know when to start decompressing? How does the receiver know whether a packet transmitted with protocol ID 21 was transmitted before the peer processed the final config-request and sent its ACK or after? The receiver cannot tell by watching for the config-ack, because that ACK might be lost. Worse, if the peer separates the processing of CCP from IP, the link may be permanently broken. For example, my code handles PPP overhead packets in a daemon, but IP packets in the kernel. The daemon sets switches that control what the kernel does, but the kernel and daemon are otherwise independent, automomous, and asynchronous. I'd have to stop all IP traffic for the duration of CCP chit-chat to ensure that no uncompressed IP packets got out just after the config-ACK and so seem to the confused the receiver like incompressable IP packets, which would cause the receiver to drop out of CCP and start the problem all over again. (Note that transitions in and out of CCP will happen at times of high load.) > 2.1. Packet Format > > A summary of the Puddle Jumper packet 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 > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > | PPP Protocol | Initial | Data ... > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > | CRC | > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > > > PPP Protocol > > The PPP Protocol field is described in the Point-to-Point Protocol > Encapsulation [1]. > > When the Puddle Jumper compression protocol is successfully > negotiated by the PPP Compression Control Protocol [2], the value > is 00FD hex. This value MAY be compressed when Protocol-Field- > Compression is negotiated. > > Initial > > The first octet of uncompressed data. This is usually the PPP > Protocol number for the compressed packet. > > This octet is also used as the initial value of the hash function > for compressing the remainder of the packet. This is good information, and should be in the Predictor 1 & 2 description. However, it is still incomplete. Is the protocol ID 1 byte or 2 bytes long? In other words, is it "compressed"? Does the protocol-ID compression option apply to these encapsulated protocol-ID's? OR all all encapsulated protocol-ID's compressed? What does "<> the PPP Protocol number" mean? When is it anything other than a protocol number? What is the other choice? Standards must completely define at least packet formats. ---- By the way, I'm unconvinced of the utility of making the mask and shift negotiatable. As is often said, "our job is to make choices." It is not fair (or profitable) to hand customers a sack of sand to tell them to buid their own computers. You only make things optional or variable when you honestly think customers will want and need and be able to vary them. Varying the mask and shift are expensive in many instruction sets. It is much faster to have a constant shift count and mask, so it is necessary to have some compelling reasons for expecting customers to want to vary them. I find it very unlikely that customers will ever configure even one installation's shift count. Restarting the hash fuction at each packet is an interesting idea. Have you done any tests that show it helps? Instead of varying the shift, and perhaps instead of restarting the hash at each packet, has anyone considered making the hash function have more than 16-bits of "history"? It seems to me that main reason to reduce the shift from 4 is to get more "history" into the hash table probes. Using a 32-bit hash value that is folded into a 16-bit index (e.g. ((x>>16)^x)&0xffff) seems to me likely to be effective and as cheap as configurable shifting. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Mon Oct 18 11:04:38 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0ooyvE-0000Eka; Mon, 18 Oct 93 11:03 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Mon, 18 Oct 1993 14:00:28 -0400 (EDT) Message-ID: <9310181800.AA01237@donut.gandalf.ca> References: <<9310171901.AA10859@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > By the way, I'm unconvinced of the utility of making the mask and > shift negotiatable. As is often said, "our job is to make choices." Maybe, it should have several *fixed* modes, depending on the available memory. Something like a shift of 3 and a mask of 13 for an 8K (per end) implementation. The default could be <4,17> bits, and a maximum mode of who knows what. The actual compression loop is so short that I would not have a problem duplicating the code within a case, and hardwwiring the shifts and masks with the case. I viewed the "shift" and "mask" as a way of reducing/increasing the memory required. > Restarting the hash fuction at each packet is an interesting idea. > Have you done any tests that show it helps? And doing a memset of 64K per packet? > > Instead of varying the shift, and perhaps instead of restarting the > hash at each packet, has anyone considered making the hash function > have more than 16-bits of "history"? It seems to me that main reason > to reduce the shift from 4 is to get more "history" into the hash table > probes. Using a 32-bit hash value that is folded into a 16-bit index > (e.g. ((x>>16)^x)&0xffff) seems to me likely to be effective and as > cheap as configurable shifting. A higher Markov model won't necessarily improve the compression and may make it worse. -- 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 Oct 18 15:59:17 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0op3Vb-0000Bia; Mon, 18 Oct 93 15:56 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Microsoft PPC Draft Date: Mon, 18 Oct 93 15:46:06 TZ Message-ID: <9310182255.AA25883@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Well, here is the fourth one of these drafts. Obviously, I stole from the other three drafts :-). NOTE: The licensing is still up in the air. I *think* it will be free. Better yet, no license at all! I'll see what I can do. Also, I use a coherency byte to keep the history buffers in synch. It appears to me that ALL three submitted algorithms will want to do the same thing instead of working over a "reliable link". I would be glad to present exactly how this coherency byte works and why it is better (easier to implement, lower overhead, etc.) than the current HDLC draft. The coherency byte I use does NOT substitute for a reliable delivery mechanism - it simply keeps the history buffers in check, and when they go out of synch, it flushes them. This is ALL that these compression schemes need. A reliable link is overkill in my opinion. Network Working Group Thomas J. Dimitri Internet Draft Microsoft expires in six months October 1993 PPP Microsoft PPC Compression Protocol draft-ietf-pppext-microsoftppc-nn.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. The PPP Compression Control Protocol [2] provides a method to negotiate and utilize compression protocols over PPP encapsulated links. This document describes the use of the Microsoft Point to Point Compression protocol for compressing PPP encapsulated packets. Dimitri expires in six months [Page i] =0CDRAFT Microsoft PPC October 1993 1. Introduction The Microsoft Point to Point Compression(MPPC)algorithm is a means of representing arbitrary Point to Point Protocol (PPP) packets in a compressed form. MPPC is lossless, because translating into and out of MPPC causes no loss of information. MPPC is real-time because it favors speed of compression and decompression over achieving maximum compression as well as having the ability to compress on-the-fly. MPPC is based on MS-DOS 6 DoubleSpace integrated disk compression and the Microsoft Real-time Compression Interface (MRCI). It has been modified to take advantage of continuous data streams, sections of uncompressable data, and unreliable point to point links. The MPPC algorithm is an LZ based algorithm which uses a sliding window history buffer. The MPPC algorithm will compress all file types efficiently. Even two byte copy items can be compressed. The MPPC algorithm supports both single and multiple history buffers. A single history buffer will require less memory, but may not provide as much compression as a multiple history buffer implementation. Using multiple history buffers can improve the compression ratio of a PPP link by associating a separate history buffer for each virtual link. 1.1. Licensing The MPPC general algorithm and encoding scheme is available without license fees. The included source code is available only with a license. The licensing fee for the source code is free. Although great care has been taken to ensure that the algorithm and the source code does not infringe any patents, there is no assurance that it is not covered by a patent. Use the code at your own risk. Dimitri expires in six months [Page 1] =0CDRAFT Microsoft PPC October 1993 2. MPPC Packets Before any MPPC packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the CCP Control Protocol must reach the Opened state. Exactly one MPPC datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 00FD (compressed datagram). The maximum length of the MPPC datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated packet. Only packets with PPP Protocol numbers in the range 0021 to 00FA hex are compressed. Other PPP packets are always sent uncompressed. Rationale: Most PPP Protocols are sent infrequently. Changes to the compression history would not persist, which would result in a net expansion. Also, LCP packets MUST NOT be compressed, to ensure recognition in a partially Opened state. Padding The MPPC packets require the negotiation of the Self-Describing- Padding Configuration Option [3] at LCP Link Establishment. Rationale: Every octet counts. A length field would add two octets all of the time. Self-Describing-Padding adds one extra octet less than half the time. Reliability and Sequencing The MPPC algorithm does not require a reliable link. Instead, it relies on a coherency octet in each packet to keep the history buffers in synchronization. If the history buffers fall out of synchronization, the coherency octet will be used to resynchronize the history buffer. MPPC expects the packets to be delivered in sequence, otherwise hisory buffer resynchronization will occur. MPPC MAY be used over a reliable link, as described in "PPP Reliable Transmision" [4], but this typically just adds unnecessary overhead since the coherency octet is all that is needed. Dimitri expires in six months [Page 2] =0CDRAFT Microsoft PPC October 1993 Rationale: Modern serial links are very reliable, with a transmission error rate on the order of less than 1/1000. Restart of the transmission history at this rate should be considerably more efficient then adding overhead to every frame. Data Expansion The maximum theoretical expansion of MPPC is 1.1875:1. On completely uncompressable data (no matches found), data expansion is only 1.06:1. However, typical expansion on pre-compressed data transmitted in 1500 octet packets is 0.99:1. When the data expansion exceeds the size of the PPP MRU for the link, the expanded packet MUST be sent without compression. When a packet is received with PPP Protocol numbers in the range 0021 to 00FA hex, it is assumed that the packet would have caused expansion. The packet is locally compressed to update the compression history. Rationale: By using the PPP Protocol field for compression detection, a field with a bit for compression is eliminated. 2.1. Packet Format The encapsulation differs based on the negotiated History Count. If the History Count is greater than one, the the following format is used. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | Coherency |Compressed Data... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ If the History Count is greater than one, the the following format is used. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | History Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Coherency | Compressed Data... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Dimitri expires in six months [Page 3] =0CDRAFT Microsoft PPC October 1993 PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the MPPC compression protocol is successfully negotiated by the PPP Compression Control Protocol [2], the value is 00FD hex. This value MAY be compressed when Protocol-Field-Compression is negotiated. History Number The number of the compression history which should be used. Coherency The coherency octet is used to assure that the packets are sent in proper order and that no packet has been dropped. It is also used to indicate the start of a packet from a flushed history buffer as well as to request that the other end flush its history buffer. Compressed Data The compressed PPP encapsulated packet. Note that the compressed data may also be in Check Mode form. Check Mode includes a history buffer position index as well as a CRC. Dimitri expires in six months [Page 4] =0CDRAFT Microsoft PPC October 1993 3. Configuration Option Format Description The CCP Configuration Option negotiates the use of MCCP on the link. By default or ultimate disagreement, no compression is used. A summary of the MCCP 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 | History Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | History Buffer | Check Mode | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type (4) Length 7 History Count The History Count field is two octets, and specifies the maximum number of Compression Histories. Valid values range from 1 to 65768. History Buffer The History Buffer field is two octets, and specifies the maximum size of the History Buffer. Valid values are 4096, 8192, and 16384. Check Mode The Check Mode MAY be set to indicate support for checking the history buffer's current index and for CRC parity. Dimitri expires in six months [Page 5] =0CDRAFT Microsoft PPC 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] Rand, D., "The PPP Compression Control Protocol (CCP)", work in progress. [3] Simpson, W.A., "PPP LCP Extensions", work in progress. [4] Simpson, W.A., "PPP in HDLC Framing", work in progress. Acknowledgments Dimitri expires in six months [Page 6] =0CDRAFT Microsoft PPC 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: Thomas J. Dimitri Microsoft Corporation 1 Microsoft Way Redmond, WA 98052 EMail: tommyd@microsoft.com Dimitri expires in six months [Page 7] =0CDRAFT Microsoft PPC October 1993 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. MPPC Packets .......................................... 2 2.1 Packet Format.................................... 3 3. Configuration Option Format ........................... 5 SECURITY CONSIDERATIONS ...................................... 6 REFERENCES ................................................... 6 ACKNOWLEDGEMENTS ............................................. 6 CHAIR'S ADDRESS .............................................. 7 AUTHOR'S ADDRESS ............................................. 7 Dimitri expires in six months [Page 7] =0CDRAFT Microsoft PPC October 1993 =1A From owner-ppp-comp Mon Oct 18 16:18:36 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0op3oR-0000bAa; Mon, 18 Oct 93 16:16 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Mon, 18 Oct 1993 16:16:22 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Microsoft PPC Draft" on Oct 18, 15:46, Thomas Dimitri writes:] > current HDLC draft. The coherency byte I use does NOT substitute > for a reliable delivery mechanism - it simply keeps the history > buffers in check, and when they go out of synch, it flushes them. > This is ALL that these compression schemes need. A reliable link > is overkill in my opinion. In certain situations, such as a temporary loss of receive resources, a reliable link is far preferable to flushing the dictionary. Also, how do you deal with out-of-order packets? -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Mon Oct 18 17:01:31 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0op4U2-0000cZa; Mon, 18 Oct 93 16:59 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Mon, 18 Oct 93 16:51:16 TZ Message-ID: <9310182358.AA02160@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Dave Rand | [In the message entitled "Microsoft PPC Draft" on Oct 18, | 15:46, Thomas Dimitri writes:] | > current HDLC draft. The coherency byte I use does NOT substitute | > for a reliable delivery mechanism - it simply keeps the history | > buffers in check, and when they go out of synch, it flushes them. | > This is ALL that these compression schemes need. A reliable link | > is overkill in my opinion. | | In certain situations, such as a temporary loss of receive resources, | a reliable link is far preferable to flushing the dictionary. Also, how | do you deal with out-of-order packets? out-of-order packets are dealt with by the coherency byte. You note that in certain situations a reliable link is preferable. Fine. But I say that in MOST situations just one coherency byte and no reliable delivery is preferable. The public phone system is only getting better. Almost all modems today do error-control. The chance of a dropped is getting real slim (especially with V.42). Other mediums are even better. Plus, if a packet is dropped, within a couple packets, the history buffer is built back up. And those packets which could not benefit from a history buffer only lose 5% or so. So I still say, it's really not worth it. PLUS, some network layers will RETRANSMIT the dropped packets for you if the reliable mechanism takes too long. So in effect, the effect of a reliable delivery mechanism at the PPP level may hamper the reliable delivery mechanism at the network layer. Time for another beer bet? I bet my coherency byte will take up less code, less memory and 99% of the time (using modems with V.42) get a better throughput then the same algorithm over HDLC. --Thomas From owner-ppp-comp Mon Oct 18 19:07:55 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0op6SC-00008Wa; Mon, 18 Oct 93 19:05 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Mon, 18 Oct 1993 19:05:33 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Microsoft PPC Draft" on Oct 18, 16:51, Thomas Dimitri writes:] > better. Almost all modems today do error-control. > The chance of a dropped is getting real slim (especially > with V.42). Other mediums are even better. V.42 only helps Modem <-> Modem. The Computer <-> Modem link is not reliable. I agree that in a properly designed router environment, with true hardware flow control (implemented in hardware, like the SCN2692), async links are very reliable. Typical async hardware (NS16550/NS16450/8250) is not very reliable, WRT overrun/dropped bytes. > Plus, if a packet is dropped, within a couple packets, > the history buffer is built back up. And those packets > which could not benefit from a history buffer only > lose 5% or so. So I still say, it's really not worth it. In a well designed router, I agree. Unfortunately, not everyone is running on a well designed hardware platform :-( > Time for another beer bet? I bet my coherency byte > will take up less code, less memory and 99% of the > time (using modems with V.42) get a better throughput > then the same algorithm over HDLC. --Thomas If you confine yourself to good hardware and great software, I agree. If you allow that algorithms are going to run on poor hardware platforms, with strange buffering requirements - you are on! -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Tue Oct 19 04:52:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opFcD-0000EZa; Tue, 19 Oct 93 04:52 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Tue, 19 Oct 93 05:52:46 EDT Message-ID: <1555.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) > In other words, how does the peer know when to stop trying to > de-compress packets with protocols 0x21 to 0xfa? > Good point. The CCP draft will need text saying "once the CCP has started negotiation, all network layer packets are silently discarded." > I'd have to stop all > IP traffic for the duration of CCP chit-chat to ensure that no > uncompressed IP packets got out just after the config-ACK and > so seem to the confused the receiver like incompressable IP packets, > which would cause the receiver to drop out of CCP and start the problem > all over again. (Note that transitions in and out of CCP will > happen at times of high load.) > Yes, that's what I expected. All IP traffic would have to stop for the duration of CCP negotiation, just like it will have to stop for the duration of MLP negotiation. This would _have_ to be true anyway, since any compressed packets would have to be discarded during CCP negotiation, and one would expect that most network layer traffic would be compressed, yes? > This is good information, and should be in the Predictor 1 & 2 > description. However, it is still incomplete. Is the protocol ID > 1 byte or 2 bytes long? In other words, is it "compressed"? > Does the protocol-ID compression option apply to these encapsulated > protocol-ID's? OR all all encapsulated protocol-ID's compressed? > Yes, this information should be in the CCP draft, for all protocols. I'd say always compress the PPP Protocol "inside". > customers to want to vary them. I find it very unlikely that customers > will ever configure even one installation's shift count. > The mask and shift is primarily there so that I could test changing them. Yes, I agree, and will take them out. See my answer to Dave for results. > Restarting the hash fuction at each packet is an interesting idea. > Have you done any tests that show it helps? > Yes, about 3% on packets of 512 bytes (6M test set). It avoids the IP header being re-inserted into the table at the hash of every random ending of the previous packet. But I only restart the _hash_ function, not re-initialize the history. The IP header ends up in the same hash location every time, and so is not re-sent. That won't help as much when sending to more than one machine. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Oct 19 04:53:00 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opFcH-0000B1a; Tue, 19 Oct 93 04:52 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Tue, 19 Oct 93 06:14:10 EDT Message-ID: <1556.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) > > By the way, I'm unconvinced of the utility of making the mask and > > shift negotiatable. As is often said, "our job is to make choices." > > Maybe, it should have several *fixed* modes, depending on the available > memory. Something like a shift of 3 and a mask of 13 for an 8K (per end) > implementation. The default could be <4,17> bits, and a maximum mode > of who knows what. > Well, the real reason I added them is so that I could _test_ them. The results of this weekend's test were for history sizes ranging from 4K to 32K, changing the shift _always_ resulted in worse compression. The 4 bit shift appears to be a local minimum. Here's some of the tests I wrote down: Size Shift Mask 16384 3 ff 6,170,097 3,261,286 16384 4 ff 6,170,097 3,195,197 .5179 16384 5 ff 6,170,097 3,282,594 16384 6 ff 6,170,097 3,589,906 4096 3 ff 6,170,097 3,720,493 4096 4 ff 6,170,097 3,617,575 .5863 4096 5 ff 6,170,097 3,754,951 4096 6 ff 6,170,097 4,048,129 Also, changing the mask _always_ resulted in worse compression on a large data set. I had hoped for some table folding, but it didn't pan out. I didn't try changing the shift and the mask at the same time (there is only so much time). If anyone else wants to try and see if there is some synergy, go ahead. > I viewed the "shift" and "mask" as a way of reducing/increasing the > memory required. > Yes, that was my hope. Unfortunately, it doesn't seem to help, and degrades at about the same rate independent of hash table size. > > Restarting the hash fuction at each packet is an interesting idea. > > Have you done any tests that show it helps? > > And doing a memset of 64K per packet? No, I only reset the _hash_ function, not the history. One of the problems with the Predictor algorithm is it takes so long to fill in the table. The first time you see a pair of bytes, it goes in one place. The next time, there are 3 bytes in the hash, the first byte of the three is relatively random, and so the table needs to be filled in 256 spots. My experiments show that the table is about 80% filled after 4M of data, and 95% after 40M. This is a really long startup cycle. So, restarting the hash on our relatively short packets allows us to do the lookups in the same starting place in the table for each packet, rather than one of 4K random starting places based on the last few bytes of the previous packet. Of course, the leap from the TCP sequence to the data is also relatively random, and so there is always 5 bytes to restart the data part. This is also true when doing VJ IP header compression. ---- BTW, Dave Rand considered presetting the history buffer to be too expensive. So, I included a Preset option for testing. My tests show that the basic in-band initialization (preset zero, fill during compression) with relatively homogenous data takes about 4K. After that it slows down. This 4K applies whether I send 400 bytes, 40 KiloBytes, or 40 MegaBytes. Using a preset of a mere memcpy of a small 256 byte block gave me a 5% increase in throughput for transfers of a single 112K email message, and a 20% increase for a 732 byte message. Using preset, suddenly a 4K history gives better performance than a 32K history without preset! I've decided that using a preset is well worth the effort! Also, over 20% of the table gets filled with Blank, not Zero. So, even starting with a memset of Blank would be better than a simple calloc. There is a _lot_ of pattern in the history. I will devote my next efforts to find a good 1K preset. Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Oct 19 05:44:05 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opGPb-0000SXa; Tue, 19 Oct 93 05:43 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Tue, 19 Oct 1993 08:41:07 -0400 (EDT) Message-ID: <9310191241.AA01491@donut.gandalf.ca> References: <<9310182358.AA02160@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Time for another beer bet? I bet my coherency byte > will take up less code, less memory and 99% of the > time (using modems with V.42) get a better throughput > then the same algorithm over HDLC. --Thomas Beer bet taken! I'm not so sure about the throughput statement. You may be right if and only if us LAPB bigots have to use V.42 also. If you are running V.42, you must factor in the packet size and the LAPM protocol the modem uses, both which reduce throughput. After all, how else would they error correct? LAPM might save a header byte (I don't have the specs handy) but you aren't saving a great deal over LAP/B on a packet basis. I would also believe that most V.42 modems would send multiple packets for each input packet, otherwise a 1500 byte frame would encounter more than 1 second of latency while the modem buffers the packet. So your V.42 error-correction is going to cost more in throughput. I would turn V.42 off in the modem, and replace it LAPB in the router, thereby garaunteeing the error-correction between routers. You are right on the "less code", "less memory", and "tastes great" :-) Too bad you used V.42 in your bet. But then again, if you used ISDN nobody would have taken the bet! And none of that American beer please. If I wanted water, I'd order water. -- 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 19 06:14:23 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opGt6-0000W3a; Tue, 19 Oct 93 06:14 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Tue, 19 Oct 1993 09:11:51 -0400 (EDT) Message-ID: <9310191311.AA01539@donut.gandalf.ca> References: <<1556.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > The results of this weekend's test were for history sizes ranging from > 4K to 32K, changing the shift _always_ resulted in worse compression. > The 4 bit shift appears to be a local minimum. > > Here's some of the tests I wrote down: > > Size Shift Mask > 16384 3 ff 6,170,097 3,261,286 > 16384 4 ff 6,170,097 3,195,197 .5179 > 16384 5 ff 6,170,097 3,282,594 > 16384 6 ff 6,170,097 3,589,906 Which seems to confer with my statement on the Markov order. Order 3, or in the case of predictor 3.5, seems optimal. > 4096 3 ff 6,170,097 3,720,493 > 4096 4 ff 6,170,097 3,617,575 .5863 > 4096 5 ff 6,170,097 3,754,951 > 4096 6 ff 6,170,097 4,048,129 > > Also, changing the mask _always_ resulted in worse compression on a > large data set. I had hoped for some table folding, but it didn't pan > out. This is a given. But getting 1.7:1 (4K history) versus 1.9:1 (16K history) is a valid tradeoff. This opens the door to saving 8 separate histories in the same amount of memory. > I didn't try changing the shift and the mask at the same time (there is > only so much time). If anyone else wants to try and see if there is > some synergy, go ahead. And while their at it, how about replacing the XOR with an ADD, which generally produces a more even hash, in the same algorithmic time. The gain is somewhat less than 1%, but still it's free. I've done very little testing on this change, so it's a pretty loose claim. -- 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 19 09:20:46 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opJnH-0000X6a; Tue, 19 Oct 93 09:20 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: Puddle Jumper draft Date: Tue, 19 Oct 93 10:19:45 -0600 Message-ID: <9310191619.AA26778@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Dave Carr writes: > ... > > > Restarting the hash fuction at each packet is an interesting idea. > > Have you done any tests that show it helps? > > And doing a memset of 64K per packet? How so? It's only the hash function that is cleared, not the hash table. Puddle Jumper must define the algorithm it uses. It is very polite to say it is "based entirely on Predictor", but that is not sufficent for a standard. The Puddle jumper standard must either stand alone or be added to the document that defines Predictor, which I think should be the CCP document. Notice that at least one of the parameters that Puddle Jumper makes variable is not explicitly mentioned in the Predictor document. What exactly is the "mask" that Puddle Jumper varies? I've been assuming that it is the implicit 0xffff in the declaration of the hash value as an unsigned short, but it occurred to me that it might be either of at least two other things. I think that C code is the best description for such algorithms. Puddle Jumper must have some code defining its algorthm. English is simply too imprecise. (I pressume Algol 60 and Pascal are not choices.) The Predictor code is unsuitable for building a PPP implementation, but it does define the compression algorithm. Without that code, the English in the CCP document that attempts to descripe Predictor would be useless. Of course, Puddle Jumper must not be forwarded until the objections I raised about its encapsulation ambiguities are resolved, either by changes in how it works or by words answering my questions. Even if my objections are irrelevant or wrong, if I can think of them, so will many others. (Please let me know if I failed to convey the ambiguities I perceive.) By the way, have there been behind the scenes disagreements about Puddle Jumper? I would hate to think that Puddle Jumper is separate from CCP and Predictor or that there have been proposals to separate Predictor from the CCP document reflects a disagreement on letting Puddle Jumper be part of the document describing Predictor. I really think that Puddle Jumper should be merged with Predictor. Of course, in the long run, not only the compression algorithm used in more than 90% of all PPP installations will be free and unlisensed, but it will be a single algorithm with a single, common, effectively fixed set of parameters. For example, of the zillions of netnews links (far more than there are PPP links), how many compression schemes are in use to the 99th percentile? Three (3), none, 12-bit `compress`, and 16-bit `compress`. Given the switch in the C News source switch to 16-bit `compress`, how many are still running 12-bit? I really think that we need only one of Predictor 1, Predictor 2, and Puddle Jumper, and I like Predictor 1. "Our job is to make choices." > > Instead of varying the shift, and perhaps instead of restarting the > > hash at each packet, has anyone considered making the hash function > > have more than 16-bits of "history"? It seems to me that main reason > > to reduce the shift from 4 is to get more "history" into the hash table > > probes. Using a 32-bit hash value that is folded into a 16-bit index > > (e.g. ((x>>16)^x)&0xffff) seems to me likely to be effective and as > > cheap as configurable shifting. > > A higher Markov model won't necessarily improve the compression and may > make it worse. Good point, but without a test (and a "standard" test set), how can one know? The current Predictor with its 4 bytes of history and no influence at all from the 5th and older bytes strikes me as too short. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Tue Oct 19 09:34:06 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opK0F-00005pa; Tue, 19 Oct 93 09:33 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: Microsoft PPC Draft Date: Tue, 19 Oct 93 10:32:28 -0600 Message-ID: <9310191632.AA26983@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Well, here is the fourth one of these drafts. Obviously, I stole > from the other three drafts :-). NOTE: The licensing is still up > in the air. I *think* it will be free. Better yet, no license at > all! I'll see what I can do. > > Also, I use a coherency byte to keep the history buffers in synch. > It appears to me that ALL three submitted algorithms will want to do > the same thing instead of working over a "reliable link". I would > be glad to present exactly how this coherency byte works and why it > is better (easier to implement, lower overhead, etc.) than the > current HDLC draft. The coherency byte I use does NOT substitute > for a reliable delivery mechanism - it simply keeps the history > buffers in check, and when they go out of synch, it flushes them. > This is ALL that these compression schemes need. A reliable link > is overkill in my opinion. > > > Network Working Group Thomas J. Dimitri I agree that LAPB is gross overkill for these purposes, but Puddle Jumper, Predictor 2, and Predictor 1 all have "coherency bytes", their two-byte checksum. They would not work otherwise. Recall that a PPP packet of any one of those three has two (2) 16-bit checksums. One is the familiar HDLC checksum on all packets, and the other is inside the PPP HDLC INFO field. If it turns out to be unlicensed and if it is to be a real contender for the solitary de facto standard PPP compression, the document must include a complete description of the algorithm. That solitary de facto PPP compression standard will be whatever a pair of machines running the code from uunet.uu.net or agate.berkeley.edu negotiate. As soon as someone publishes modifications to the DP source that work well enough, all arguments here will be moot. Of course, dedicated boxes from router vendors will continue to negotiate their own private or semi-private protocols, but they will be an insignificant minority, irrelevant to everyone except their owners. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Tue Oct 19 10:14:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opKdq-0000P7a; Tue, 19 Oct 93 10:14 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: Puddle Jumper draft Date: Tue, 19 Oct 93 11:13:27 -0600 Message-ID: <9310191713.AA27162@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk >From: Bill.Simpson@um.cc.umich.edu > > From: vjs@rhyolite.wpd.sgi.com (Vernon Schryver) > > In other words, how does the peer know when to stop trying to > > de-compress packets with protocols 0x21 to 0xfa? > > > Good point. The CCP draft will need text saying "once the CCP has > started negotiation, all network layer packets are silently discarded." Are you saying that as soon as the (future) receiver of compressed packets sends a CCP config request, it would have to drop all network packets? That obviously cannot work. What if the other side refuses to compress? Or are you saying that as soon as the receiver gets a CCP config-ACK from the transmitter, the receiver must discard all non-compressed packets forever? -That would mean you could never stop using compression without completely killing the PPP link. -what about compression algorithms that expand the data a lot and compenstate by sending uncompressable data using natural encapsulation? >... > Yes, that's what I expected. All IP traffic would have to stop for the > duration of CCP negotiation, just like it will have to stop for the > duration of MLP negotiation. > > This would _have_ to be true anyway, since any compressed packets would > have to be discarded during CCP negotiation, and one would expect that > most network layer traffic would be compressed, yes? Instead of my other guesses, are you saying only that all network traffic received from the transmission of the CCP config request by the (prospective) receiver until the receiver either gets CCP "OPENED" or gives up and moves the CCP FSM to CLOSED or similar? I guess you might do that, but only Puddle Jumper needs it I would also object to this since it breaks the link for a relatively long time (perhaps many exchanges to pick a common compression protocol and options). The only reason to have a PPP link is to pass network packets, and anything that interferes with passing network packets is by definition Very Bad, and permissible only if it somehow helps network packets overall. > ... > I'd say always compress the PPP Protocol "inside". I'd probably say that too, but whatever it is, something must be written in the RFC. > > > Restarting the hash fuction at each packet is an interesting idea. > > Have you done any tests that show it helps? > > > Yes, about 3% on packets of 512 bytes (6M test set). It avoids the IP > header being re-inserted into the table at the hash of every random > ending of the previous packet. Interesting. > But I only restart the _hash_ function, not re-initialize the history. > The IP header ends up in the same hash location every time, and so is > not re-sent. That won't help as much when sending to more than one > machine. Have you measured something like the 32-bit history? The deal of folding a 32-bit hash value into a 16-bit index? vjs From owner-ppp-comp Tue Oct 19 10:37:32 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opKzX-0000Xia; Tue, 19 Oct 93 10:37 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Tue, 19 Oct 93 10:25:25 TZ Message-ID: <9310191735.AA21967@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Dave Carr | | If you are running V.42, you must factor in the packet size and the | LAPM protocol the modem uses, both which reduce throughput. After all, | how else would they error correct? LAPM might save a header byte | (I don't have the specs handy) but you aren't saving a great deal over | LAP/B on a packet basis. | | I would also believe that most V.42 modems would send multiple | packets for each input packet, otherwise a 1500 byte frame would encounter | more than 1 second of latency while the modem buffers the packet. So | your V.42 error-correction is going to cost more in throughput. | | I would turn V.42 off in the modem, and replace it LAPB in the router, | thereby garaunteeing the error-correction between routers. | Ok, one thing we are forgetting here is that V.42 increases throughput by about 10% if the data stream is mostly continuous. That is, the network layer opens up the window to about 3 1500 byte packets before wanting an ACK. This is because V.42 does not send start and stop bits. Thus, instead of sending 10bits per byte, it sends 8 bits per byte with framing and a CRC overhead. The overhead hurts, but it does NOT hurt so much that it kills the ~20% gain from removing the start and stop bits. Also, the max frame size V.42 uses is 256 - this is good for noisy links because it may be harder to get 1 1500 byte packet through then 6 256 byte packets, so on noisy links, V.42 is a win as well. This 10% stuff is not coming out of my butt either. File copy throughput has been tested with error control off and on for several different modems on several different machines. Furthermore, it is shipping (Microsoft uses LZ compression and the coherency byte in NT RAS and now Window for Workgroups RAS) which means the algorithm has been tested with TERABYTES of data. | You are right on the "less code", "less memory", and "tastes great" :-) | | Too bad you used V.42 in your bet. But then again, if you used ISDN | nobody would have taken the bet! In most cases the V.42 part of the bet still works. For little packets and small windows ACKS flying back and forth, it doesn't. So it still appears to me that all four of the algorithms I've seen so far run better (in most cases) with this coherency byte instead of over HDLC. So does anybody intend to do anything about it besides me? | And none of that American beer please. If I wanted water, I'd order water. What do you want, Moosehead? --Thomas From owner-ppp-comp Tue Oct 19 10:53:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opLEe-0000Rua; Tue, 19 Oct 93 10:52 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Tue, 19 Oct 93 10:40:44 TZ Message-ID: <9310191751.AA23259@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Vernon Schryver | | I agree that LAPB is gross overkill for these purposes, but Puddle | Jumper, Predictor 2, and Predictor 1 all have "coherency bytes", their | two-byte checksum. They would not work otherwise. Recall that a PPP | packet of any one of those three has two (2) 16-bit checksums. One is | the familiar HDLC checksum on all packets, and the other is inside the | PPP HDLC INFO field. >From testing terabytes of data, I've found that if the algorithm is properly coded, all you need is one byte to do all that. That one byte checks for sequencing, can make a flush request, and states whether or not the current packet came from a flushed history buffer or not. It's definitely faster than running yet another checksum. This is getting ridiculous -- two checksums, two reliable delivery mechanisms? Really, aren't there any end to end proponents on this alias? However, I have also included a configuration option "check mode" in which 4 extra bytes are added. Two bytes for the history buffer index ptr, and two bytes for a CRC. The reason for the history buffer index ptr is that without it, if the packet is out of sequence you may make lots of EXTRA matches making for one very big packet. The way to counter that is to check for this problem in your decompressor but that just slows down the decompressor with extra checks (and doesn't clue in the developer to the problem that the history buffers are out of sycnhronization). Whereas, if the history buffer index ptr checks and the CRC fails, there is most likely a bug in the way the compressor compresses and the decompressor decompresses. So I still say, get rid of the deadweight, get rid of the unnecessary code, don't duplicate work done in other layers unless needed. But perhaps I'll be the one picking up the bar tab in Houston. --Thomas From owner-ppp-comp Tue Oct 19 15:01:29 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opP6g-0000ela; Tue, 19 Oct 93 15:00 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: Microsoft PPC Draft Date: Tue, 19 Oct 93 15:57:43 -0600 Message-ID: <9310192157.AA29475@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: tommyd@microsoft.com > | From: Vernon Schryver > | > | I agree that LAPB is gross overkill for these purposes, but Puddle > | Jumper, Predictor 2, and Predictor 1 all have "coherency bytes", their > | two-byte checksum. They would not work otherwise. Recall that a PPP > | packet of any one of those three has two (2) 16-bit checksums. One is > | the familiar HDLC checksum on all packets, and the other is inside the > | PPP HDLC INFO field. > > >From testing terabytes of data, I've found that if the algorithm is > properly coded, all you need is one byte to do all that. That one > byte checks for sequencing, can make a flush request, and > states whether or not the current packet came from a flushed > history buffer or not. It's definitely faster than running yet another > checksum. This is getting ridiculous -- two checksums, two > reliable delivery mechanisms? Really, aren't there any end to > end proponents on this alias? All of us who are even willing to consider compression with unreliable links easily qualify as "end-to-end proponents." The CPU cycle cost/byte of computing an extra CRC is a little less than the raw cost/byte of Predictor 1, 2, or Puddle Jumper. The CRC seems to me an extremely reliable mechanism for detecting situations which would otherwise require a reliable link. The cost in space for the extra CRC is insignificant. Is your 1-byte "coherency byte" other than a packet sequence number? If so, how does your 1-byte detector cope with a transmit queue of length greater than 256 and a long block of simply and cleanly lost data as might happen with buffer overflows during a long modem retraining? As far as I can see, it is impossible to detect all such problems with a 1-byte packet sequence number. > However, I have also included a configuration option "check mode" > in which 4 extra bytes are added. Two bytes for the history buffer > index ptr, and two bytes for a CRC. The reason for the history buffer > index ptr is that without it, if the packet is out of sequence you may > make lots of EXTRA matches making for one very big packet. > The way to counter that is to check for this problem in your > decompressor but that just slows down the decompressor with > extra checks (and doesn't clue in the developer to the problem > that the history buffers are out of sycnhronization). Whereas, if > the history buffer index ptr checks and the CRC fails, there is > most likely a bug in the way the compressor compresses and > the decompressor decompresses. I do not understand this text. It seems to be talking about an option for the Microsoft algorithm. I have never signed an non-disclosure agreement for Microsoft's Doublespace, and the Microsoft compression draft does not describe the algorithm (at least in I don't see a description). So I do not understand the relevance or significance of this option. I just assume it's a good idea for what is currently a secret, proprietary algorithm. > So I still say, get rid of the deadweight, get rid of the unnecessary > code, don't duplicate work done in other layers unless needed. > But perhaps I'll be the one picking up the bar tab in Houston. --Thomas I understand this text even less. Is there some deadweight in the Microsoft code that you think should be removed? Are you proposing changes to any of Predictor 1, 2, or Puddle Jumper? If so, what are they? None of those three has a "history buffer index pointer", although I guess you might ship a recent value of the hash function, but I think that would be a bad idea, since the CRC is both a sufficient and more powerful detector of loss of synchronization. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Tue Oct 19 15:05:58 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opPAy-0000Tna; Tue, 19 Oct 93 15:05 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Tue, 19 Oct 1993 18:01:59 -0400 (EDT) Message-ID: <9310192202.AA01675@donut.gandalf.ca> References: <<9310191619.AA26778@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > How so? It's only the hash function that is cleared, not the hash table. Sorry, I was thinking about resetting the table on an error. My mistake. > I think that C code is the best description for such algorithms. Perhaps not best, but certainly concise. But then again, I've seen some V.42bis code which was more cryptic than the specification. > Of course, in the long run, not only the compression algorithm used in > more than 90% of all PPP installations will be free and unlisensed, but > it will be a single algorithm with a single, common, effectively fixed > set of parameters. We may as well standardize the vendor and products. No need for marketting hype called differentiation. I'll take the market, you can watch. Get real. One of the reasons of LZ77 popularity is that different versions can interoperate. Same can be said for LZW. Yes, it slows down the inner loops. That is the price of interoperability. A $2000 router will probably have less RAM than a $10,000 router. Rightly so. But they can interoperate. > I really think that we need only one of Predictor 1, Predictor 2, and > Puddle Jumper, and I like Predictor 1. "Our job is to make choices." I agree here (signal exception event). > Good point, but without a test (and a "standard" test set), how can one > know? The current Predictor with its 4 bytes of history and no > influence at all from the 5th and older bytes strikes me as too short. Read existing papers and books maybe? But in some cases it's faster to write and test the code. After all, who actually can understand all those information theory equations and symbols. I'll take a picture anytime. If I recall, higher order models are good for text, bad for anything else. The best Markov compressors blend models, usually maintaining orders of 0,1, and 3. I'd have to dig out the papers/books to quote references. There is a local minimum somewhere between orders 2 and 4, depending on the data. -- 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 19 17:04:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opR1o-0000i5a; Tue, 19 Oct 93 17:03 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Tue, 19 Oct 93 16:55:19 TZ Message-ID: <9310200002.AA00905@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk | From: Vernon Schryver | > From: tommyd@microsoft.com | > | From: Vernon Schryver | > | | > | I agree that LAPB is gross overkill for these purposes, but Puddle | > | Jumper, Predictor 2, and Predictor 1 all have "coherency bytes", their | > | two-byte checksum. They would not work otherwise. Recall that a PPP | > | packet of any one of those three has two (2) 16-bit checksums. One is | > | the familiar HDLC checksum on all packets, and the other is inside the | > | PPP HDLC INFO field. | > | > >From testing terabytes of data, I've found that if the algorithm is | > properly coded, all you need is one byte to do all that. That one | > byte checks for sequencing, can make a flush request, and | > states whether or not the current packet came from a flushed | > history buffer or not. It's definitely faster than running yet another | > checksum. This is getting ridiculous -- two checksums, two | > reliable delivery mechanisms? Really, aren't there any end to | > end proponents on this alias? | | All of us who are even willing to consider compression with unreliable | links easily qualify as "end-to-end proponents." | | The CPU cycle cost/byte of computing an extra CRC is a little less than | the raw cost/byte of Predictor 1, 2, or Puddle Jumper. The CRC seems | to me an extremely reliable mechanism for detecting situations which | would otherwise require a reliable link. The cost in space for the | extra CRC is insignificant. If it is NOT needed, why bother? My argument is that it is not needed. I make this argument, because as I have alluded to before, I have put in debug checks(in my code) to account for anytime when the coherency byte didn't the detect situation but the extra CRC and that "history buffer pointer" did. After terabytes of modem transmissions (inter state & intercontinental), it did not fail. Can you claim the same? I'm not theorizing here, I worked on this stuff for almost two years. | Is your 1-byte "coherency byte" other than a packet sequence number? | If so, how does your 1-byte detector cope with a transmit queue of | length greater than 256 and a long block of simply and cleanly lost | data as might happen with buffer overflows during a long modem | retraining? As far as I can see, it is impossible to detect all such | problems with a 1-byte packet sequence number. | Doesn't work when an exact multiple of 15 packets in a row are droppped (and totally undetected). That is, if 15, 30, 45, etc. compressed packets in a row are dropped, you're screwed. For this case, an extra measure is needed. This was never the case in my implementation. | > However, I have also included a configuration option "check mode" | > in which 4 extra bytes are added. Two bytes for the history buffer | > index ptr, and two bytes for a CRC. The reason for the history buffer | > index ptr is that without it, if the packet is out of sequence you may | > make lots of EXTRA matches making for one very big packet. | > The way to counter that is to check for this problem in your | > decompressor but that just slows down the decompressor with | > extra checks (and doesn't clue in the developer to the problem | > that the history buffers are out of sycnhronization). Whereas, if | > the history buffer index ptr checks and the CRC fails, there is | > most likely a bug in the way the compressor compresses and | > the decompressor decompresses. | | I do not understand this text. It seems to be talking about an option | for the Microsoft algorithm. I have never signed an non-disclosure | agreement for Microsoft's Doublespace, and the Microsoft compression | draft does not describe the algorithm (at least in I don't see a | description). So I do not understand the relevance or significance of | this option. I just assume it's a good idea for what is currently a | secret, proprietary algorithm. | You'll understand it soon. Gimme a break. I'll try to briefly explain why below. | > So I still say, get rid of the deadweight, get rid of the unnecessary | > code, don't duplicate work done in other layers unless needed. | > But perhaps I'll be the one picking up the bar tab in Houston. --Thomas | | I understand this text even less. Is there some deadweight in the | Microsoft code that you think should be removed? Are you proposing | changes to any of Predictor 1, 2, or Puddle Jumper? If so, what are | they? No, there is no deadweight that I know of in the Microsoft code. There is deadweight when you have two CRC algorithms and two reliable delivery mechanisms. By default, the MPPC algorithm does not do this. I am proposing changes to all three other algorithms. A "history buffer index pointer" would be, for those algorithms, the number of uncompressed bytes passed to the compressor. It may be the exact same thing as MPPC depending on how the Gandalf and STAC implementations slide the history buffer. I admit I have not licensed the code from Gandalf or STAC either, so I cannot say. I'm sure I will find out soon enough. Either way, such a "pointer" or perhaps I should say "counter" for the other algorithms, is helpful because it can detect out of order packets which the CRC cannot. Believe me this helps when you are working on multiple processor, multi-threaded kernel platforms. This is a "debug" mode, or "extra super duper safe" mode for the Microsoft PPC algorithm. It is not the suggested mode. | None of those three has a "history buffer index pointer", | although I guess you might ship a recent value of the hash function, | but I think that would be a bad idea, since the CRC is both a | sufficient and more powerful detector of loss of synchronization. The CRC cannot detect when packets 1 and 2 got swapped and sent in order 2 and 1. It is sufficient to detect loss of synchronization though. What do you mean by "more powerful". Even CRC's can fail. Have you tested and proved that it is more powerful or are you just theorizing? -Thomas From owner-ppp-comp Tue Oct 19 20:52:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opUaj-0000fDa; Tue, 19 Oct 93 20:52 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: Microsoft PPC Draft Date: Tue, 19 Oct 93 21:23:23 -0600 Message-ID: <9310200323.AA01887@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: From: tommyd@microsoft.com > | The CPU cycle cost/byte of computing an extra CRC is a little less than > | the raw cost/byte of Predictor 1, 2, or Puddle Jumper. The CRC seems > | to me an extremely reliable mechanism for detecting situations which > | would otherwise require a reliable link. The cost in space for the > | extra CRC is insignificant. > > If it is NOT needed, why bother? My argument is that it is not needed. > I make this argument, because as I have alluded to before, I have > put in debug checks(in my code) to account for anytime when the coherency > byte didn't the detect situation but the extra CRC and that "history > buffer pointer" did. I do not understand your point. No one has suggested that you should do anything than whatever you've proposed for the Microsoft compression algorithm. Are you instead proposing a varient of Predictor? If so, could you be specific? > After terabytes of modem transmissions (inter state & > intercontinental), it did not fail. How did you move "terabytes" of data in only two years? Isn't a TB 10*12 bytes? By "modem," I infer you mean something that runs no faster than 28kbit/sec, and so moves about about 12MByte/hour, and I assume you compress by 2X, and so do 25MB/hour. That means that you can do 25*24*366 MB/year or about 220GB/year. A reasonable derating from 24 hours/day, 365 days/year makes a TB a very large number. Perhaps you had very large number of phone lines active at the same time. At $0.10/minute of interstate long distance time, and more for intercontinental links, you must have spent at least $3,000,000 for telephone time for your tests. That is an impressive investment in PPP compression algorithm testing. > Can you claim the same? I'm not theorizing here, I worked on this > stuff for almost > two years. What is your point? It's possible that paying customers have used my SLIP code, or even only my screwball varient of header-compressing SLIP with its link-layer, error-detecting checksum to move a total of a TB of data. (10's of 1000's of people have the stuff, and it's been out for a lot longer than 2 years). I don't know, and I don't think anyone should care. I would not want to make claims about my expertise or the reliability of any protocol of the form "I (or it) moved X bytes." Not so minor details like what kind of errors and problems were observed, not to mention at least some kind of description of the protocol itself, would be required before I would presume to make such claims. For example, I have run tests that have moved a TB of data over FDDI links (12MB/sec=300hr/TB), but I would make few claims based on them because I don't have the supporting data to make them interesting. > | Is your 1-byte "coherency byte" other than a packet sequence number? > .... > Doesn't work when an exact multiple of 15 packets in a row are droppped > (and totally undetected). That is, if 15, 30, 45, etc. compressed packets > in a row are dropped, you're screwed. For this case, an extra measure is > needed. This was never the case in my implementation. I still do not know what your "coherency byte" is. I still do not know if I should care. > There is deadweight when you have two CRC algorithms and > two reliable delivery mechanisms. By default, the MPPC > algorithm does not do this. Predictor 1 and 2 and P.J. involve 2 CRC's, but where is the second or even the first "reliable delivery mechanism" in any of them? > I am proposing changes to all three other algorithms. Ok, what would the new versions of Preditor 1, 2 and P.J. look like? You must be sufficiently specific to allow me to change my code. > A "history buffer index pointer" would be, for those algorithms, > the number of uncompressed bytes passed to the compressor. >... Wouldn't that be the same as the length prepended to the data in Predictor 1 and 2? That Bill Simpson proposes to eliminate in Puddle Jumper as deadweight? > Either way, such a "pointer" or perhaps I should say "counter" for > the other algorithms, is helpful because it can detect out of order > packets which the CRC cannot. Believe me this helps when you are > working on multiple processor, multi-threaded kernel platforms. > This is a "debug" mode, or "extra super duper safe" mode for the > Microsoft PPC algorithm. It is not the suggested mode. I do not understand any of this, although I've been involved with symmetric multiprocessors since the late 1970's. My PPP and SLIP code is sold on symmetric multiprocessors as well as uniprocessors. (Well, PPP didn't quite make the IRIX 5.1 CDROM's) I certainly do not understand how this "pointer," which seems to already be present in Predictor 1 and 2, is particularly useful for MP implementations. Anyone who cannot keep packets well ordered in their protocol stacks on their MP systems is likely to have far worse problems than might ever be affected by an "extra super duper safe mode." I say that as one who has had (i.e. created and/or fixed) more than one or two such "far worse" MP problems. > | the CRC is both a > | sufficient and more powerful detector of loss of synchronization. > > The CRC cannot detect when packets 1 and 2 got > swapped and sent in order 2 and 1. It is sufficient to detect > loss of synchronization though. What do you mean by > "more powerful". Even CRC's can fail. Have you tested > and proved that it is more powerful or are you just theorizing? On the contrary, the Predictor 1, 2, and P.J. CRC do detect packet reorderings. If you swap the order of a pair of packets, you have an excellent chance of having the the CRC for both of them be wrong because the decompressor's dictionary will be wrong. The CRC is more powerful than a simple packet sequence number (which is apparently not what the "coherency byte" is; I don't know), because you have a very good chance of the CRC being wrong after any loss of consecutive packets, including any multiple of 15 that you say are not detected by the "coherency byte." Vernon Schryver, vjs@sgi.com From owner-ppp-comp Tue Oct 19 21:10:23 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opUrM-0000dBa; Tue, 19 Oct 93 21:09 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Re: Puddle Jumper draft Date: Tue, 19 Oct 93 23:44:58 EDT Message-ID: <1565.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > And while their at it, how about replacing the XOR with an ADD, which > generally produces a more even hash, in the same algorithmic time. The > gain is somewhat less than 1%, but still it's free. I've done very > little testing on this change, so it's a pretty loose claim. > I tried it this evening. Always gives an improvement (less than 1%) for text email, and always is worse for exe binary (less than 0.1%). ppp92.all 16384 4 ^ 6,170,097 3,195,197 .5179 ppp92.all 16384 4 + 6,170,097 3,186,024 .5163 imr-9307.txt 16384 4 ^ 112,635 66,739 .592 imr-9307.txt 16384 4 + 112,635 66,335 .588 shorter.txt 16384 4 ^ 732 677 .9249 shorter.txt 16384 4 + 732 680 .9289 tar.exe 16384 4 ^ 35,231 38,886 1.103 tar.exe 16384 4 + 35,231 38,890 1.103 gs386.exe 16384 4 ^ 456,597 356,500 .780 gs386.exe 16384 4 + 456,597 356,599 .780 Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Tue Oct 19 22:08:19 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opVlS-0000bba; Tue, 19 Oct 93 22:07 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: Puddle Jumper draft Date: Tue, 19 Oct 93 23:05:40 -0600 Message-ID: <9310200505.AA02560@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: dcarr@gandalf.ca > ... > > Good point, but without a test (and a "standard" test set), how can one > > know? The current Predictor with its 4 bytes of history and no > > influence at all from the 5th and older bytes strikes me as too short. > > Read existing papers and books maybe? But in some cases it's faster to > write and test the code. After all, who actually can understand all those > information theory equations and symbols. I'll take a picture anytime. > > If I recall, higher order models are good for text, bad for anything else. > The best Markov compressors blend models, usually maintaining orders of > 0,1, and 3. I'd have to dig out the papers/books to quote references. > There is a local minimum somewhere between orders 2 and 4, depending on the > data. I don't see what "information theory equations" have to do with what is essentally a matter of picking a pragmatic minimum over a favorite set of test data. Beware of using big math words as a rhetorical technique. Some of us have at one time or another had a little academic math training, and not just the sterilized stuff engineers think is math. In olden days, people ended up fiddling with computers after starting out studying or working in other fields, instead of starting out studying computers and only computers as C.S. students now seem to. It sounds entirely plausible that English text (including computer program source) is well modeled by chains longer than 4. It sounds equally plausible that 80*86 binaries would not want longer chains (my best guess for "non-text" that has fairly low entropy). I wonder about 32-bit RISC binaries, with their uniformly 32-bit instructions, but with more and larger embedded constants. There are a lot of long rote sequences in the MIPS code I see, but mostly when ignoring the addresses in the load-immediates. But no matter. What matters is only is something good enough. Give that you say "the best" compressors maintain orders 0,1, and 3, what about a shift of 8 into a 32-bit accumulator, h, and compute the table index with (((h>>24) ^ h) & 0xffff) ? Is anyone likely today to build anything with a CPU that would be inconvenienced by a 32-bit accumulator? Eg. something like an 80186? I intend that as a serious question, but without wanting to know anyone's product development plans. 8086's are awfully cheap, but they are very slow. Of course, if the gain would be only marginal, then the current 4-bit shift, and simple 16-bit mask is simplest and so best. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Wed Oct 20 07:35:44 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opedB-00009Ta; Wed, 20 Oct 93 07:35 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 93 10:02:24 EDT Message-ID: <1567.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I have come to the conclusion that Predictor/Puddle Jumper isn't worth more effort, unless this group can't decide on anything else. In experimenting with short (< 40K) exe files, I have found that they don't compress very well. Even if all the exe files in one of my bin directories are copied together, PJ will give only 20% compression. For comparison, the email test file gives 48% compression. exe.all 16384 4 + ff 2,142,639 1,716,021 .800 ppp92.all 16384 4 + ff 6,170,097 3,186,024 .5163 Then, last night, I changed the test bed to "packetize" two files interleaved -- 512 bytes of one, then 512 bytes of the other -- like a pair of FTP sessions going through a router. When using short email for one and short exe for the other, compression dropped to about 7%! I figured out why this is: the MOV instructions in the exe occupy the same space as the ASCII letters. The table thrashes. When the big exe.all and (the first part of) ppp92.all are interleaved, overall compression does improve. This means that PJ is only good on very long lived connections. exe|ppp92 16384 4 + ff 4,285,871 2,956,551 .689 For comparison, here are the numbers for PKZIP: ppp92.all pkzip 1.1 6,170,097 1,490,761 .2416 76% exe.all pkzip 1.1 2,142,639 1,178,798 .5502 45% Why waste our time with Predictor? An LZ based technique beats the pants off of it! Even on short individual files! Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Oct 20 08:11:49 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opedB-00009Ta; Wed, 20 Oct 93 07:35 PDT Sender: owner-ppp-comp X-Path: um.cc.umich.edu!bill.simpson From: "William Allen Simpson" To: ppp-comp@bungi.com Subject: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 93 10:02:24 EDT Message-ID: <1567.bill.simpson@um.cc.umich.edu> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I have come to the conclusion that Predictor/Puddle Jumper isn't worth more effort, unless this group can't decide on anything else. In experimenting with short (< 40K) exe files, I have found that they don't compress very well. Even if all the exe files in one of my bin directories are copied together, PJ will give only 20% compression. For comparison, the email test file gives 48% compression. exe.all 16384 4 + ff 2,142,639 1,716,021 .800 ppp92.all 16384 4 + ff 6,170,097 3,186,024 .5163 Then, last night, I changed the test bed to "packetize" two files interleaved -- 512 bytes of one, then 512 bytes of the other -- like a pair of FTP sessions going through a router. When using short email for one and short exe for the other, compression dropped to about 7%! I figured out why this is: the MOV instructions in the exe occupy the same space as the ASCII letters. The table thrashes. When the big exe.all and (the first part of) ppp92.all are interleaved, overall compression does improve. This means that PJ is only good on very long lived connections. exe|ppp92 16384 4 + ff 4,285,871 2,956,551 .689 For comparison, here are the numbers for PKZIP: ppp92.all pkzip 1.1 6,170,097 1,490,761 .2416 76% exe.all pkzip 1.1 2,142,639 1,178,798 .5502 45% Why waste our time with Predictor? An LZ based technique beats the pants off of it! Even on short individual files! Bill.Simpson@um.cc.umich.edu From owner-ppp-comp Wed Oct 20 08:45:18 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opfiR-0000ABa; Wed, 20 Oct 93 08:44 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 1993 08:44:09 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Predictor/Puddle Jumper a dog" on Oct 20, 10:02, "William Allen Simpson" writes:] > Why waste our time with Predictor? An LZ based technique beats the > pants off of it! Even on short individual files! > *some* LZ techniques beat it. Not all. Predictor helps on long sessions, or lots of data in short sessions over high speed links. Predictor is patent free (even Novell pays the V.42bis patent royalty, and we don't make any hardware). If you read my WAN compression document (sgi.com:other/ppp-comp/comp.{doc|ps}) you will see that many compression techniques, even on multiple session data, will beat Predictor. None of them are faster, however. If you don't want to implement it, license a different technique, and use it! I will be using multiple compression techniques in our PPP implementation, and so should you. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Oct 20 09:18:17 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opgEY-00005La; Wed, 20 Oct 93 09:17 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: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 93 12:16:37 EDT Message-ID: <9310201616.AA28950@eng.xyplex.com> References: <<1567.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Has anybody benchmarked predictor/derivative for its compression time, rather than compression ratio? If predictor can keep up with T1 speeds with a reasonable uCPU running at reasonable MIPS, even "lousy 7%" compression is much better than no compression at all: LZ-based algorithms -definitely- can't keep up. +=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+ | 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 Oct 20 09:22:39 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opgIn-0000C1a; Wed, 20 Oct 93 09:22 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 1993 09:22:12 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: Predictor/Puddle Jumper a dog" on Oct 20, 12:16, Scott Wasson writes:] > Has anybody benchmarked predictor/derivative for its compression time, > rather than compression ratio? > > If predictor can keep up with T1 speeds with a reasonable uCPU running > at reasonable MIPS, even "lousy 7%" compression is much better than no > compression at all: LZ-based algorithms -definitely- can't keep up. > Yes. We have it running on E1 (2 Mbps) on a 386 box. Works fine, and doesn't use 100% of the CPU (we can still route!). -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Wed Oct 20 09:52:03 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opgke-0000QPa; Wed, 20 Oct 93 09:51 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: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 93 10:50:07 -0600 Message-ID: <9310201650.AA06611@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Bill.Simpson@um.cc.umich.edu > > I have come to the conclusion that Predictor/Puddle Jumper isn't worth > more effort, unless this group can't decide on anything else. Given licensing and patent worries, is anything else possible? >... > When using short email for one and short exe for the other, compression > dropped to about 7%! I figured out why this is: the MOV instructions in > the exe occupy the same space as the ASCII letters. The table thrashes. I think 512 byte packets are too small. 1500 sounds more plausible for today's Internet, but your point remains. Suggestion 1: What about hashing the first 5 bytes of each packet to a 2-4 bit number, and using that number to select one of 4-16 Predictor tables, each 4-16KBytes long, and then use Predictor for the rest of the packet? Whether the traffic is VJ-compressed TCP/IP or plain vanilla IP, the first 5 bytes (usually starting with 0x21, 0x2d, or 0x2f) should vary mostly on the connection, and so should train a dictionary to a connection. Suggestion 2: Associate a small Preditor table with each VJ-compression slot, and compress only protocols 0x2d or 0x2f. Suggestion 3: Obvious combinations of (1) and (2). > ... > Why waste our time with Predictor? An LZ based technique beats the > pants off of it! Even on short individual files! That sounds good. Can we agree on one for pure software products? And let the hardware product people worry about royalties to Unisys et al or agree on a different protocol? Vernon Schryver, vjs@sgi.com From owner-ppp-comp Wed Oct 20 14:48:24 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oplNU-0000Q4a; Wed, 20 Oct 93 14:47 PDT Sender: owner-ppp-comp X-Path: microsoft.com!tommyd From: Thomas Dimitri To: ppp-comp@bungi.com Subject: Puddle Jumper, STAC, Gandalf, and MPPC Date: Wed, 20 Oct 93 14:40:59 TZ Message-ID: <9310202146.AA18589@netmail.microsoft.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I have renamed the discussion Vernon and I were having because the discussion really applies to all compression algorithms. Also, the discussion we were having had digressed to the point (my fault entirely) where I was failing to communicate effectively. If I have failed to do it yet again, I'm sure Vernon will let me know. I think that all four algorithms should, by default, NOT use an extra CRC check and NOT run over the HDLC draft. Instead, they should default to using ONE byte. A byte which I refer to as the "coherency byte". However, they should also be able to neogtiate a "super safe mode" were they add the extra CRC check (or whatever else is needed). Reasons: 1. The coherency byte is sufficient to detect out of sequence packets. 2. The coherency byte is sufficient to request a FLUSH of the history buffer. 3. The coherency byte takes less code, less memory, and is easier to implement than HDLC. 3. The coherency byte takes less space (just one byte) and is faster to compute (on average) than the 16-bit CRC. 4. Thus, the coherency byte will, for most cases, provide better throughput than CRC or HDLC + CRC. How can I make say this? Well, I am confident that the coherency byte is sufficient because about a terabyte of data has been pumped through it (really, I am not trying to brag here, I am simply giving empirical data). The Micrsoft dial-in server has 80 modem ports and about 20 ISDN ports all running the MPPC algorithm, almost 100 ports busy every night. Then take all the other Microsoft sites in England, France, Australia, and in the U.S (probably another 50 or more). Plus, we stress test the stuff 24 hours around the clock in our labs (that's 64 modem ports and 4 ISDN ports - althouugh not running all the time). All these machines would hit an assertion of mine if the coherency byte failed to be sufficient. Granted, probably only 10% are non-local calls. But, yes Vernon, I am talking in terms of terabytes (from above that's 250 lines, each pumping at least 10 megs a day). So the next question is exactly how does this "coherency byte" work. Well, for that you'll have to wait until the license for MPPC gets finalized (*should* be less than a week). But before that, I'm 100% certain that some people have an excellent idea on how it works and could probably implement it better than I did. I'm also confident persons can come up with reasons why in some cases a CRC is better or why HDLC provides better throughput but I could counter those arguments with other situations. All considered, I truly believe that for most cases, the coherency byte is sufficient and provides better throughput and that is why it should be the default. --Thomas From owner-ppp-comp Wed Oct 20 14:49:51 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oplPJ-0000Mua; Wed, 20 Oct 93 14: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: Puddle Jumper draft Date: Wed, 20 Oct 1993 17:46:40 -0400 (EDT) Message-ID: <9310202146.AA01979@donut.gandalf.ca> References: <<9310200505.AA02560@rhyolite.wpd.sgi.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > I don't see what "information theory equations" have to do with what is > essentally a matter of picking a pragmatic minimum over a favorite set > of test data. The danger is optimizing for the "test data", and getting worse results in the field. > Some of us have at one time or another had a little academic math > training, and not just the sterilized stuff engineers think is math. I'm an engineer, with no formal information theory training. What I have learned is from the books and papers, skipping over the math. When I need theory, I ask an expert. Ask three, take a vote. One may think he's an expert :-) > It sounds entirely plausible that English text (including computer > program source) is well modeled by chains longer than 4. Sure. There have been studies (in the 1960's I think), that verify that. Some guy named Shannon I think. Lined up a number of people and asked them what the next letter in a word was, given the first few. It gets better at the *word* level though, and so does text compression, if you take the *syntax* of the data into the model. (There goes the old code complexity meter, right off the scale). Compression algorithms such as "Word", that try to find a Markov relationship between words. All that's nice, but perhaps we don't have 6 MB+ to store the word dictionary, so Predictor will have to do! However, Predictor* is not a full Markov compressor, only an approximation. So the gains made by keeping state information from more characters, is offset by the fact that your wiping out state information from the lower models, without compensating. If you were to have a blended model, keeping order 1 and order 0, then maybe order 4 or 5 makes sense for english. For example, to add order 1 information to Predictors model would require 256 bytes of memory (no hashing either, but you could cut it down to 64 bytes with a hash table :-)). The trick becomes how to encode it efficiently, since you need an "escape" to drop from order 3 encoding down to order 1. Now here's a deep thought. Suppose we forget the encoding for a minute. How many bytes does it take to implement order 0 model for Predictor? Ah, it's quitting time. Time for a beer. > It sounds > equally plausible that 80*86 binaries would not want longer chains (my > best guess for "non-text" that has fairly low entropy). I wonder about > 32-bit RISC binaries, with their uniformly 32-bit instructions, but > with more and larger embedded constants. There are a lot of long rote > sequences in the MIPS code I see, but mostly when ignoring the > addresses in the load-immediates. It's possible to determine the nature of the data, and adjust your compression (see archiver HPACK source code). This could be added to Predictor. It's also a good place to study up on the Markov technique used to boost it's compression. Of course, I'm only speculating that Markov is used in HPACK because the code is obfuscated. At a risk of stating the obvious, binaries are different than text, RISC code is different than CISC, etc. A 80x86 compressor wouldn't work well for SPARC. "Experts" I've talked with speculated the best compressor would be a Markov compressor, tuned for the *Assembler* code not the object. It's important to recognize the natural widths of fields, such as opcodes, which are never on a byte boundary, and therefore don't get compressed well with a character oriented compressor. You'd also want to know this is an instruction, that is a jump table, ... > Give that you say "the best" compressors maintain orders 0,1, and 3, > what about a shift of 8 into a 32-bit accumulator, h, and compute the > table index with (((h>>24) ^ h) & 0xffff) ? Not exactly the same. A real "0,1,3" compressor, would have one model indexed with the hash of the last 3 character, another model with the last character, etc. I would expect the above to perform much worse than just a plain order 3. Try it and see. It may work better on the data set you chose, or worse. Try it on the "corpus". It has different types of data. But after all the testing, how it works as a *packet* compressor is what counts here. And a packet compressor is not a file compressor. Perhaps that's why resetting the hash works better. The chain is reset to point at "control" (packet headers) instead of "data". It would probably work better if you split the model into 2 halves, and compressed the header separate from the data. > Is anyone likely today to build anything with a CPU that would be > inconvenienced by a 32-bit accumulator? Eg. something like an 80186? Good point. What are people on the list using? This certainly affects some compression algorithms, say for example an arithmetic encoder :-) -- 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 Oct 20 14:53:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oplSb-0000Sea; Wed, 20 Oct 93 14:52 PDT Sender: owner-ppp-comp X-Path: Novell.COM!Dave_Rand From: Dave_Rand@Novell.COM (Dave Rand) To: ppp-comp@bungi.com Subject: New CCP - have at it! Date: Wed, 20 Oct 93 14:51:08 PDT Message-ID: <9310202151.AA02432@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 The PPP Compression Control Protocol (CCP) draft-ieft-pppext-compression-00.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 of encapsulating multiple protocol datagrams 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 expires in six months [Page i] DRAFT PPP Compression October 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 expires in six months [Page 1] DRAFT PPP Compression October 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 (0xFD) (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 expires in six months [Page 2] DRAFT PPP Compression October 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 some cases) may be sent uncompressed, using its standard form, or may be sent in multiple datagrams, if the compression algorithm supports it. Dave Rand expires in six months [Page 3] DRAFT PPP Compression October 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. If any of the protocols are not recognized, a Configure-Reject must be sent for all protocols that are not recognized. If any of the protocols are recognized, but not acceptable due to local options in the request, a Configure-Nak should be sent with the local options modified appropriately. A new Configure-Request may then be sent with the options adjusted as specified in the Configure-Nak. 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. 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: CCP Option Meaning 1 Compression type negotiation (common) 2 Compression type negotiation (OUI/proprietary) Dave Rand expires in six months [Page 4] DRAFT PPP Compression October 1993 3.1. Compression Type Negotiation Option (common) Description This Configuration Option provides a way to negotiate the use of a standard compression algorithm. As of this writing, several compression algorithms are specified (see appendix). By default, compression is not enabled. 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 | Compression | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | options... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 1 Length >= 3 Compression Types The compression types field lists the common compression algorithms that the are available. They must be listed in the order of desirability for this particular link. Each compression type is followed with a length, which may be 0. The length indicates the number of octets of compression-specific negotiation information, which may include items such as dictionary size, maximum string length and number of dictionaries. 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 Configure-ACKed. If a protocol is understood, but some (or all) of the compression negotiation options are not acceptable, these may be modified and sent back in a Configure-Nak. If any of the protocols are not understood, a Configure-Reject must be sent back including all protocols not understood. Implementation of any particular compression algorithm IS NOT guaranteed. If all protocols the sender implements are Configure-Rejected by the receiver, then no compression is Dave Rand expires in six months [Page 5] DRAFT PPP Compression October 1993 enabled. Default No compression protocol enabled. Dave Rand expires in six months [Page 6] DRAFT PPP Compression October 1993 3.2. Compression Type Negotiation Option (OUI/Proprietary) Description This Configuration Option provides a way to negotiate the use of a proprietary compression protocol. By default, such compression is not enabled. Since the first matching compression will be used, it is recommended that any known OUI compression options be transmitted first, before the common options are used. Before accepting this option, the implementation must verify that the Organizationally Unique Identifier identifies a proprietary algorithm that the implementation can decompress, and that any vendor specific negotiation options are fully understood. If no OUIs are supported by an implementation, a Configure-Reject may be sent back for any type 2 Compression Type Negotiation Option. 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 | OUI MS octet | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OUI remaining octects | Length | options... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 2 Length >= 3 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 any previous OUI has been received by the sender. Multiple vendor-specific proprietary compression types may be Dave Rand expires in six months [Page 7] DRAFT PPP Compression October 1993 implemented by the option field, which may contain algorithm selection information, negotiated options such as dictionary size, or any other information required. Any unrecognized proprietary compression configure requests MUST have a Configure-Reject sent back. Length The Length field specifies the number of octects of OUI-specific negotiation information, in free format. It may be followed by 0 to 255 octets of negotiation information. options The options 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 expires in six months [Page 8] DRAFT PPP Compression October 1993 A. Common compression number identification The following numbers for common compression option use have been defined. Compression ID Algorithm specified 1 Predictor type 1 2 Predictor type 2 3 Puddle Jumper 16 Hewlett-Packard PPC 17 Stac Electronics LZS 18 Microsoft PPC 19 Gandalf FZA IDs 4-15 are reserved for other freely-available implementations of compression algorithms. Dave Rand expires in six months [Page 9] DRAFT PPP Compression October 1993 B. Common compression algorithm definitions A compression algorithm that is available without license fees is the predictor algorithm, defined below. Note that although care has been taken to ensure that the following code does not infringe any patents, there is no assurance that it is not covered by a patent. Use the following code at your own risk. B.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 Dave Rand expires in six months [Page 10] DRAFT PPP Compression October 1993 File: A 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 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 #ifdef __STDC__ #include #endif #include /* * pred.c -- Test program for Dave Rand's rendition of the * predictor algorithm * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) * 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) static unsigned short int Hash; static unsigned char GuessTable[65536]; Dave Rand expires in six months [Page 11] DRAFT PPP Compression October 1993 static int 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); } static int 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--; Dave Rand expires in six months [Page 12] DRAFT PPP Compression October 1993 } 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); } #define SIZ1 8192 static void compress_file(f) FILE *f; { char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; int len1, len2; while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) { len2 = compress((unsigned char *)bufp, (unsigned char *)bufc, len1); (void) fwrite(bufc, 1, len2, stdout); } } static void decompress_file(f) FILE *f; { char bufp[SIZ1+9]; char bufc[SIZ1*9+9]; int len1, len2, len3; len1 = 0; while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) { len1 += len3; len3 = len1; len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 0); (void) fwrite(bufc, 1, len2, stdout); (void) memcpy(bufp, bufp+len3-len1, len1); } Dave Rand expires in six months [Page 13] DRAFT PPP Compression October 1993 len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 1); (void) fwrite(bufc, 1, len2, stdout); } int main(ac, av) int ac; 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); (void) fclose(f); } } return(0); } B.2. Encapsultation for Predictor type 1 The correct encapsulation for type 1 compression is the protocol type, 1 bit indicating if the data is compressed or not, 15 bits of the uncompressed data length in octets, compressed data, and uncompressed CRC-16 of the two octets of unsigned length in network byte order, followed by 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC - 16 | Dave Rand expires in six months [Page 14] DRAFT PPP Compression October 1993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ It is not required that any of the fields 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.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 (uncompressed), compressed data, and uncompressed CRC-16 of the two octets of unsigned length in network byte order, followed by the original, uncompressed data. The data stream may be broken at any convenient place for encapsulation purposes. With type 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC-16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... It is not required that any field 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. Dave Rand expires in six months [Page 15] DRAFT PPP Compression October 1993 C. 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. [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] Reynolds, J., Postel,J., "Assigned Numbers", RFC 1340, USC/Information Sciences Institute, March 1990. [6] Perkins, D., Hobby, R., "Point-to-Point Protocol (PPP) initial configuration options", RFC 1172, August 1990. [7] Carr, D., "PPP Gandalf FZA Compression Protocol", Work in progress. [8] Lutz, R., "PPP Stacker LZS Compression Protocol", Work in progress. [9] Simpson, W.A., "PPP Puddle Jumper Compression Protocol", Work in progress. [10] Dimitri, T.J., "PPP Microsoft LZ Compression Protocol", Work in progress. Dave Rand expires in six months [Page 16] DRAFT PPP Compression October 1993 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. The predictor algorithm was originally implemented by Timo Raita, at the ACM SIG Conference, New Orleans, 1987. 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 Author's Address Questions about this memo can also be directed to: Dave Rand Novell, Inc. 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand expires in six months [Page 17] DRAFT PPP Compression October 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 Compression Type Negotiation Option (common) .... 5 3.2 Compression Type Negotiation Option (OUI/Proprietary) ................................................. 7 APPENDICES ................................................... 9 A. Common compression number identification .............. 9 B. Common compression algorithm definitions .............. 10 B.1 Predictor algorithm .......................... 10 B.2 Encapsultation for Predictor type 1 .......... 14 B.3 Encapsultation for Predictor type 2 .......... 15 C. CCP Recommended Options ............................ 16 SECURITY CONSIDERATIONS ................................... 16 REFERENCES ................................................... 16 ACKNOWLEDGEMENTS ............................................. 17 CHAIR'S ADDRESS .............................................. 17 AUTHOR'S ADDRESS ............................................. 17 From owner-ppp-comp Wed Oct 20 15:05:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opldh-0000PAa; Wed, 20 Oct 93 15:04 PDT Sender: owner-ppp-comp X-Path: accessworks.com!popaccess From: chen@accessworks.com (Cheng T. Chen) To: ppp-comp@bungi.com Subject: Re: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 93 18:02:12 -0400 Message-ID: <9310202202.AA00430@uu2.psi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Dave Rand wrote: > > Has anybody benchmarked predictor/derivative for its compression time, > > rather than compression ratio? > > > > If predictor can keep up with T1 speeds with a reasonable uCPU running > > at reasonable MIPS, even "lousy 7%" compression is much better than no > > compression at all: LZ-based algorithms -definitely- can't keep up. > > > > Yes. We have it running on E1 (2 Mbps) on a 386 box. Works fine, and doesn't > use 100% of the CPU (we can still route!). But, what is the E1 line utilization? At 100% full-duplex E1 line utilization, there are 250,000 bytes transmitted and received, for a total of 500,000 bytes, per second. That gives only 2 micro-seconds per byte for compression or decompression. A 386/33 box definitely cannot do this. -- Cheng T. Chen chen@accessworks.com From owner-ppp-comp Wed Oct 20 15:41:45 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opmDI-0000Yaa; Wed, 20 Oct 93 15:41 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: Predictor/Puddle Jumper a dog Date: Wed, 20 Oct 1993 15:39:28 PDT Message-ID: <9310202239.AA07725@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Oct 20, 18:02, Cheng T. Chen wrote: } But, what is the E1 line utilization? Depends on the data, and on the adapter card. With a Syncplus card, we get pretty poor line utilization due to the overhead of the card - lots of flags between frames. We still get up to 6-7 Mbps throughput, however, on our test data - better than < 2Mbps we get without compression. Another network card we have seems to do much better, but I don't know the line utilization. Diane? Do you have some numbers? } At 100% full-duplex E1 line utilization, there are 250,000 bytes transmitted } and received, for a total of 500,000 bytes, per second. That gives only } 2 micro-seconds per byte for compression or decompression. A 386/33 box } definitely cannot do this. That works out to about 64 clocks per byte, (33Mhz/256K)/2. Predictor core code in my implementation takes... 8-11 instructions per byte, only two of which reference memory. If the adapter does DMA, or you can assemble the outgoing data directly on the adapter's memory space, it is possible. Looking at some older code results that I have show a throughput of 122 FPS at 1518 byte frames, coming from a dumb ethernet card with a W&G protocol analyzer saturating the ehternet. This was on a T1 link. When compression is turned on, in the same environment, we get 286 FPS. This, due to the ethernet traffic, involves 100% of the CPU. -- From owner-ppp-comp Thu Oct 21 03:07:32 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0opwti-0000Yya; Thu, 21 Oct 93 03:05 PDT Sender: owner-ppp-comp X-Path: netcs.com!okorf From: Oliver Korfmacher To: ppp-comp@bungi.com Subject: Re: Puddle Jumper, STAC, Gandalf, and MPPC Date: Thu, 21 Oct 93 11:04:42 MET Message-ID: <9310211004.AA13175@keks.netcs.com> References: <<9310202146.AA18589@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > I have renamed the discussion Vernon and I were having because > the discussion really applies to all compression algorithms. Also, > the discussion we were having had digressed to the point (my fault > entirely) where I was failing to communicate effectively. If > I have failed to do it yet again, I'm sure Vernon will let me > know. > > I think that all four algorithms should, by default, NOT use > an extra CRC check and NOT run over the HDLC draft. Instead, > they should default to using ONE byte. A byte which I refer to > as the "coherency byte". However, they should also be able > to neogtiate a "super safe mode" were they add the extra > CRC check (or whatever else is needed). > > Reasons: > 1. The coherency byte is sufficient to detect out of sequence > packets. > 2. The coherency byte is sufficient to request a FLUSH of > the history buffer. > 3. The coherency byte takes less code, less memory, and > is easier to implement than HDLC. > 3. The coherency byte takes less space (just one byte) > and is faster to compute (on average) than the 16-bit > CRC. > 4. Thus, the coherency byte will, for most cases, provide > better throughput than CRC or HDLC + CRC. > > How can I make say this? Well, I am confident that the > coherency byte is sufficient because about a terabyte of data > has been pumped through it (really, I am not trying to brag here, > I am simply giving empirical data). The Micrsoft dial-in > server has 80 modem ports and about 20 ISDN ports all running > the MPPC algorithm, almost 100 ports busy every night. Then > take all the other Microsoft sites in England, France, Australia, > and in the U.S (probably another 50 or more). Plus, we stress test > the stuff 24 hours around the clock in our labs (that's 64 modem > ports and 4 ISDN ports - althouugh not running all the time). All > these machines would hit an assertion of mine if the coherency byte > failed to be sufficient. Granted, probably only 10% are non-local > calls. But, yes Vernon, I am talking in terms of terabytes (from > above that's 250 lines, each pumping at least 10 megs a day). > > So the next question is exactly how does this "coherency > byte" work. Well, for that you'll have to wait until the license > for MPPC gets finalized (*should* be less than a week). But > before that, I'm 100% certain that some people have > an excellent idea on how it works and could probably implement > it better than I did. > > I'm also confident persons can come up with reasons why in some > cases a CRC is better or why HDLC provides better throughput > but I could counter those arguments with other situations. > All considered, I truly believe that for most cases, the > coherency byte is sufficient and provides better throughput > and that is why it should be the default. > > --Thomas > Sure. But we need at least the option to have HDLC/CRC. And, since most ISDN (and other serial synch. lines as well) will need some bit-framing anyhow, the overhead isn't that big, additionally, most ISDN adaptions support LAPB/X.75/.. in hardware. Some of them, (not ours, of course:-), but I know many many manufacturers) ONLY support LAPB. It is the default configuration with our european API, and don't forget: germany is the worlds largest ISDN market, today. Don't ignore their needs and their today realities. So lets have at least the option for LAPB. Oliver From owner-ppp-comp Thu Oct 21 06:28:05 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq035-00009Aa; Thu, 21 Oct 93 06:27 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/Puddle Jumper a dog Date: Thu, 21 Oct 1993 09:25:02 -0400 (EDT) Message-ID: <9310211325.AA02161@donut.gandalf.ca> References: <<1567.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Why waste our time with Predictor? An LZ based technique beats the > pants off of it! Even on short individual files! Sure. But in all fairness, Predictor/Puddle Jumper was optimised for speed not compression. If you compare the times taken by an LZ method, you'll see why it's an acceptable method. Now try to get INFO-ZIP to run dynamically over a link. The Huffman trees it stores with the file will need to go with every packet! Not to say it can't be done :-) -- 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 Oct 21 08:58:14 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2O9-0000Aea; Thu, 21 Oct 93 08:57 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: IETF Houston Date: Thu, 21 Oct 1993 10:55:49 -0400 (EDT) Message-ID: <9310211455.AA02362@donut.gandalf.ca> References: <<1551.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Bill, could you forward me info about the IETF meeting in Houston. My manager finally approved some travel, but I don't have the schedule and the hotel stuff. Thanks. -- 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 Oct 21 09:06:46 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2Wi-0000C2a; Thu, 21 Oct 93 09:06 PDT Sender: owner-ppp-comp X-Path: vx4.interlan.com!KRISHNAN From: KRISHNAN@vx4.interlan.com To: ppp-comp@bungi.com Subject: Hello Date: Thu, 21 Oct 1993 12:06:18 -0400 (EDT) Message-ID: <931021120618.25e15242@vx4.interlan.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I like to introduce myself. My name is Veda Krishnan and I work in the access division at Racal Datacom ( engineering work) I have a comment and a few questions. To: Dave_Rand@novell.com (Dave Rand) Subj: Lapb draft RFC > T1 timer > 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. The timer value should be set to twice the maximum number of bits per frame, divided by the bit rate of the link, plus 100 ms. processing time. ( higher the link speed, lower the time) For your ex. it is 2* 8000/14400 + .1 = 1.21 secs. > References > [1] Simpson, W. A., "The Point-to-Point Protocol (PPP)", work in > progress. > [3] Simpson, W. A., "PPP in HDLC Framing", work in progress. > [4] Sklower, K., "PPP MultiLink Procedure", work in progress. Are there preliminary copies of these documents available ? Is there a way to get the "corpus" , so I can do some testing? Subj: New CCP - have at it! > 1 Predictor type 1 > 2 Predictor type 2 > 3 Puddle Jumper Considering all are the same prediction compression algorithm, why dont we combine them into one. It is not clear to me, where this difference in parameter negotiation will be useful. To : "William Allen Simpson" Subject: Re: Puddle Jumper draft > Size Shift Mask > 16384 3 ff 6,170,097 3,261,286 Where and how a mask of ff is applied in this test? Veda From owner-ppp-comp Thu Oct 21 09:11:46 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2bO-0000DRa; Thu, 21 Oct 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: Puddle Jumper, STAC, Gandalf, and MPPC Date: Thu, 21 Oct 1993 09:49:26 -0400 (EDT) Message-ID: <9310211349.AA02227@donut.gandalf.ca> References: <<9310202146.AA18589@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Your reasons for the coherency byte seem valid for *some* types of compression, and some types of lines. I don't think it is a universal solution. In my case, I do not want to reset my tables. For one, it's time consuming, and secondly, I've got a lot more model to lose. Losing a 2K byte history is no big deal. One packet and your history is back full. Not in my case. Of course, this coherency byte is based on some low error-rate on the lines. At 10E-5, you'll be resetting pretty often. > Reasons: > 1. The coherency byte is sufficient to detect out of sequence > packets. Good, only on low error rate lines. > 2. The coherency byte is sufficient to request a FLUSH of > the history buffer. Another protocol to run when an error happens. How is this better? And, start pitching all the frames while this reset takes place? Or is each packet encoded separately? > 3. The coherency byte takes less code, less memory, and > is easier to implement than HDLC. True. > 3. The coherency byte takes less space (just one byte) > and is faster to compute (on average) than the 16-bit > CRC. If one byte is critical, use a better compression 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 Oct 21 09:12:21 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2bp-0000Cua; Thu, 21 Oct 93 09:11 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: Oliver Korfmacher Subject: Re: New CCP - have at it! Date: Thu, 21 Oct 1993 09:11:00 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: New CCP - have at it!" on Oct 21, 10:56, Oliver Korfmacher writes:] > Hmm. Why did you remove our V.42bis proposal from the draft? > Do you see problems with a vendor-specific assignment? > I understand our discussion as successful and expected to get an > code point for our compression technique? Sigh. Sorry - I went over all the documents, but I guess I missed the V.42bis. I just checked my "mods" mail, and you are in fact in there. It was an oversight, and will be added in the next release. I will assign type 20 to it. Type Use 20 V.42bis with CodeWordSize and MaxLength negotiable -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 21 09:13:38 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2d3-0000CEa; Thu, 21 Oct 93 09:12 PDT Sender: owner-ppp-comp X-Path: donut.gandalf.ca!dcarr From: dcarr@gandalf.ca (Dave Carr) To: ppp-comp@bungi.com Subject: Re: Microsoft PPC Draft Date: Thu, 21 Oct 1993 10:37:43 -0400 (EDT) Message-ID: <9310211437.AA02305@donut.gandalf.ca> References: <<9310191735.AA21967@netmail.microsoft.com>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Ok, one thing we are forgetting here is that V.42 increases > throughput by about 10% if the data stream is mostly continuous. > That is, the network layer opens up the window to about > 3 1500 byte packets before wanting an ACK. This is because > V.42 does not send start and stop bits. Thus, instead of > sending 10bits per byte, it sends 8 bits per byte with framing > and a CRC overhead. > This 10% stuff is not coming out of my butt either. File copy > throughput has been tested with error control off and on for > several different modems on several different machines. First, you need to compare apples to apples. Start with error-correction turned off in the modem for both tests. Now, compare your protocol throughput to LAPB, in the presence of line errors. State your performance gains at error rate of 10E-12 up to 10E-5. With this test setup, the LAPB code will not be "corrected" and delayed by the V.42 error-correction. Talk about redundancy! Your throughput can at best be one byte more per packet than LAPB. It can however be a lot worse. -- 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 Oct 21 09:14:53 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2ea-0000Wba; Thu, 21 Oct 93 09:14 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: New CCP - have at it! Date: Thu, 21 Oct 93 09:15:40 -0600 Message-ID: <9310211515.AA14241@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk The following two segments are not consistent with themselves and each other, and they are wrong and ambiguous. > If any of the protocols are not recognized, a Configure-Reject must be > sent for all protocols that are not recognized. If any of the protocols > are recognized, but not acceptable due to local options in the request, > a Configure-Nak should be sent with the local options modified > appropriately. A new Configure-Request may then be sent with the > options adjusted as specified in the Configure-Nak. > Compression Types > > The compression types field lists the common compression > algorithms that the are available. They must be listed in the > order of desirability for this particular link. Each compression > type is followed with a length, which may be 0. The length > indicates the number of octets of compression-specific negotiation > information, which may include items such as dictionary size, > maximum string length and number of dictionaries. > > 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 Configure-ACKed. If a protocol > is understood, but some (or all) of the compression negotiation > options are not acceptable, these may be modified and sent back in > a Configure-Nak. If any of the protocols are not understood, a > Configure-Reject must be sent back including all protocols not > understood. The inconsistency is whether to ACK or REJect a single config-request option containing several proposaled protocols. The last paragraph in the second chunk is self-contradictory. It requires that a request listing both unrecognized protocols and a completely acceptible protocol be both rejected and ACK'ed. It also requires that almost ok configure-requests be both rejected and NAK'ed. As several of us have said, the first text that says an option containing unacceptible protocols should be rejected is inconsistent with how most (perhaps all) other PPP protocols work as well as explicitly inconsisently with how PPP says Rejects should work. The main PPP RFC says that rejected stuff must be completely unmodified. There is no reason to reject unrecognized protocols in the option if any of the others might be ok. The first chunk should be changed to something like: If none of the protocols are not recognized, a Configure-Reject MAY be sent with the entire, unmodified Configure-Request. The original transmitter of the Configure-Request, which was hoping to negotiate a compression of future network data packets sent to it, SHOULD interpret such a Configure-Reject as indicating that none of the proposed compression protocols are possible. If any of the protocols are recognized but not acceptable due to local options in the request (or optional parameters not in the request), a Configure-NAK MUST be sent with the local options modified appropriately. The Configure-NAK SHOULD contain only those protocols that might be acceptible. Other protocols which are unacceptible, whether because unrecognized or for other reasons, MUST NOT be listed in the option in the Configure-NAK. A new Configure-Request MAY then be sent with the options adjusted as specified in the Configure-Nak. The last paragraph of the second chunk should be changed to something like: The receiver will process the compression types field from left to right, selecting the first protocol that matches the receiver's capability. If an acceptible compression protocol with acceptible options is encountered, the Configure-Request MUST be ACK'ed. The ACK MUST list only this acceptible protocol If no completely acceptible protocol is found, but one or more protocols are understood, but some or all of the compression negotiation options are not acceptable, these may be modified and sent back in a Configure-Nak. If none of the protocols are understood or no acceptible alternate compression negotiation options are possible, a Configure-Reject MUST be transmitted. This Configure-Reject MUST be identical to the original Configure-Request as required by PPP protocols. Note that I've also thrown in some SHOULD's and MUST's. By the way, the title, "Compression Types", of the second chunk is inconsistent with the packet format, which contains "Compression". Vernon Schryver, vjs@sgi.com From owner-ppp-comp Thu Oct 21 09:15:10 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2ex-00007ga; Thu, 21 Oct 93 09:14 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: New CCP - have at it! Date: Thu, 21 Oct 93 09:33:49 -0600 Message-ID: <9310211533.AA14368@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk The Predictor description does not say enough about what is in each packet. > B.2. Encapsultation for Predictor type 1 > The correct encapsulation for type 1 compression is the protocol > type, 1 bit indicating if the data is compressed or not, 15 bits > of the uncompressed data length in octets, compressed data, and > uncompressed CRC-16 of the two octets of unsigned length in > network byte order, followed by 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 | > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > |*| Uncompressed length (octets)| * is compressed flag > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed > | Compressed data... | 0 means data is not compressed > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > | CRC - 16 | > +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ > > It is not required that any of the fields 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. What is in "Compressed data..."? It is not fair to expect people to guess. Until just now, I've been assuming (in code!) that that "CCP Protocol Identifier" in that diagram would also be 0xfd. I just realized that maybe the original packet's protocol ID is intended. Since that would exempt the protocol ID from compression, I've assumed my previous guess was right. Something like the following text should be added: The CCP Protocol Identifier that starts the packet is always 0xfd. If PPP Protocol field compression has not be negotiated, it MUST be a 16-bit field. The Compressed data is the Protocol Identifiewr and the Info fields of the original PPP packet described in RFC-1331 [should be new RFC number], but not the Address, Control, FCS, or Flag The CCP Protocol field MAY be compressed as described in RFC-1331, regardless of whether the Protocol field of the CCP Protocol Identifier is compressed or whether PPP Protocol field compression has been negotiated. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Thu Oct 21 09:18:55 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2io-00008Wa; Thu, 21 Oct 93 09:18 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: Hello Date: Thu, 21 Oct 1993 09:18:22 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Hello" on Oct 21, 12:06, KRISHNAN@vx4.interlan.com writes:] > Is there a way to get the "corpus" , so I can do some testing? You can get it from sgi.com:other/ppp-comp > Considering all are the same prediction compression algorithm, why dont > we combine them into one. It is not clear to me, where this difference in > parameter negotiation will be useful. Because they do different things, and we wanted the ability to have at least one really simple, no option, no way to get it wrong compression technique. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 21 09:30:50 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq035-00009Aa; Thu, 21 Oct 93 06:27 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/Puddle Jumper a dog Date: Thu, 21 Oct 1993 09:25:02 -0400 (EDT) Message-ID: <9310211325.AA02161@donut.gandalf.ca> References: <<1567.bill.simpson@um.cc.umich.edu>> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > Why waste our time with Predictor? An LZ based technique beats the > pants off of it! Even on short individual files! Sure. But in all fairness, Predictor/Puddle Jumper was optimised for speed not compression. If you compare the times taken by an LZ method, you'll see why it's an acceptable method. Now try to get INFO-ZIP to run dynamically over a link. The Huffman trees it stores with the file will need to go with every packet! Not to say it can't be done :-) -- 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 Oct 21 09:35:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq2ya-00008Na; Thu, 21 Oct 93 09:35 PDT Sender: owner-ppp-comp X-Path: netcs.com!okorf From: Oliver Korfmacher To: ppp-comp@bungi.com Subject: Comination Date: Thu, 21 Oct 93 17:34:10 MET Message-ID: <9310211634.AA14217@keks.netcs.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk Has anybody experience with TCP header compression over V.42bis or other compression techniques? We offer it as an unsupported feature, and it seems that V.42bis tends to become not very effective if many telnets with very small packets confuse its dictionary. Any comments? Oliver From owner-ppp-comp Thu Oct 21 09:39:06 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq31h-00005Sa; Thu, 21 Oct 93 09:38 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: New CCP - have at it! Date: Thu, 21 Oct 1993 09:37:47 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "Re: New CCP - have at it!" on Oct 21, 9:15, Vernon Schryver writes:] > > There is no reason to reject unrecognized protocols in the option if > any of the others might be ok. Ok - the intent here was that as you were processing, you encountered an option that you didn't recognize, you should REJ that which you didn't understand. I like your wording better, and will incorporate it. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 21 10:39:50 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq3yF-00008Ta; Thu, 21 Oct 93 10:38 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: Comination Date: Thu, 21 Oct 93 11:37:16 -0600 Message-ID: <9310211737.AA15185@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > From: okorf@netcs.com, Oliver Korfmacher > Has anybody experience with TCP header compression over V.42bis or other > compression techniques? > > We offer it as an unsupported feature, and it seems that V.42bis > tends to become not very effective if many telnets with very small > packets confuse its dictionary. > > Any comments? > > Oliver What do you mean? Do you mean IP over PPP over v.42bis modems with VJ header compression? If so, a lot of us (including me) have been sending a lot of bytes for telnet and other things in that and similar way for a long time. Given that v.42bis is most commonly used with completely simple, absolutely raw interactive stuff (i.e. PC's), in what way is the v.42bis dictionary badly confused by the telnet protocol? Vernon Schryver, vjs@sgi.com From owner-ppp-comp Thu Oct 21 11:42:41 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq4vx-0000GPa; Thu, 21 Oct 93 11: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: New CCP - have at it! Date: Thu, 21 Oct 93 12:38:46 -0600 Message-ID: <9310211838.AA15667@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > There is no reason to reject unrecognized protocols in the option if > > any of the others might be ok. > > Ok - the intent here was that as you were processing, you encountered an > option that you didn't recognize, you should REJ that which you didn't > understand. I like your wording better, and will incorporate it. > > Dave Rand > Internet: dlr@daver.bungi.com Do we agree that if you get 2 protocols, you like one, but do not understand the other, regardless of in which order they appear, that you should ACK or NAK the good one and ignore the wierdo? That a REJ should be reserved for when everything looks like nonsense? While reviewing my message as it came back from the mailing list, I saw I had at least one extra "not": If none of the protocols are not recognized, a Configure-Reject MAY ... ^^^ vjs From owner-ppp-comp Thu Oct 21 12:05:57 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq5Js-00006Ha; Thu, 21 Oct 93 12:05 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: New CCP - have at it! Date: Thu, 21 Oct 1993 12:04:10 PDT Message-ID: <9310211904.AA23405@va.SJF.Novell.COM> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk On Oct 21, 12:38, Vernon Schryver wrote: } Subject: Re: New CCP - have at it! } } > > There is no reason to reject unrecognized protocols in the option if } > > any of the others might be ok. } > } > Ok - the intent here was that as you were processing, you encountered an } > option that you didn't recognize, you should REJ that which you didn't } > understand. I like your wording better, and will incorporate it. } > } > Dave Rand } > Internet: dlr@daver.bungi.com } } Do we agree that if you get 2 protocols, you like one, but do not } understand the other, regardless of in which order they appear, that } you should ACK or NAK the good one and ignore the wierdo? That a REJ } should be reserved for when everything looks like nonsense? Yes. If you don't understand ANY of the protocols offered (even if there is only one offered), you MUST Configure-Reject. If, while processing left to right, you encounter one you like, you MAY ACK it. If you encounter something you don't like, you MAY NAK it, and hope for a better offer next time. -- From owner-ppp-comp Thu Oct 21 14:19:17 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq7OR-0000EIa; Thu, 21 Oct 93 14:17 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: LZW compression Date: Thu, 21 Oct 93 15:17:29 -0600 Message-ID: <9310212117.AA16612@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk I've been reviewing the mailing list archives, looking for mentions of "LZW". One claim that stands out is that LZW requires ~500KByte of memory. I do not understand this, given that for many years netnews was transfered to and from PDP-11's, using 12-bit compression. Predictor's 64KB table is not small when viewed on a PDP-11. A statement in the archives is that LZW seemed to compress better than Predictor but that gross file transfer times were higher. I could not tell enough about the implementation in which this was observed to know if it might not have been caused by packets being so compressed that they were delayed, causing the unspecified file transfer algorithm to timeout and then ask for a retransmission. Or if the delays were caused by the increased CPU load of LZW on the machines involved. The phrased in the archives "not all implementations are equal" is true in many different way. Since the compression ID's are up to 20, we ought to add one for straight BSD-UNIX `compress`, with negotiatable 12 or 16-bit. I don't know which strategy for handling expansion. Described as "UNIX compress" to frighten off the patent leeches and allow pure software implemtations like Morningstar, Novell, Silicon Graphics, BSDI, Sun, IBM, and HP to use it without fear. (several of those are fearlessly shipping BSD (!NOT USL!) derived compress commands.) With sample code grabbed from your favorite BSD archive site. Vernon Schryver, vjs@sgi.com From owner-ppp-comp Thu Oct 21 14:25:08 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq7UD-00008ta; Thu, 21 Oct 93 14:23 PDT Sender: owner-ppp-comp X-Path: dlr From: dlr@daver.bungi.com (Dave Rand) To: ppp-comp@bungi.com Subject: Re: LZW compression Date: Thu, 21 Oct 1993 14:23:51 PDT Message-ID: Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk [In the message entitled "LZW compression" on Oct 21, 15:17, Vernon Schryver writes:] > > One claim that stands out is that LZW requires ~500KByte of memory. > I do not understand this, given that for many years netnews was > transfered to and from PDP-11's, using 12-bit compression. > Predictor's 64KB table is not small when viewed on a PDP-11. 16-bit unix compress requires about 500K for tables, per direction. 12 bit requires less (but I'm not sure how much). I ran the tests using TCP/IP (ftp) as I recall. -- Dave Rand Internet: dlr@daver.bungi.com From owner-ppp-comp Thu Oct 21 15:48:38 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq8nG-00003Ba; Thu, 21 Oct 93 15:47 PDT Sender: owner-ppp-comp X-Path: zircon.acc.com!rms From: rms@zircon.acc.com (Ron Stoughton) To: ppp-comp@bungi.com Subject: Re: LZW compression Date: Thu, 21 Oct 93 18:46:58 EDT Message-ID: <9310212246.AA00245@zircon.acc.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk > > One claim that stands out is that LZW requires ~500KByte of memory. > > I do not understand this, given that for many years netnews was > > transfered to and from PDP-11's, using 12-bit compression. > > Predictor's 64KB table is not small when viewed on a PDP-11. > > 16-bit unix compress requires about 500K for tables, per direction. > 12 bit requires less (but I'm not sure how much). I once tested a modified version of Unix compress (modified for packet-at-a-time application) and determined the following memory requirements for various codeword sizes. I have also included the CPU time and average compression ratio for a diverse stream of packetized data (about 5M bytes of data) to give a sense of the trade-off between memory, compression ratio and CPU time (in seconds on a Sun 3/80). Size Memory CPU Ratio 12-bit 31230 7.03 2.39 14-bit 109292 6.30 2.78 16-bit 415222 6.28 3.01 Ron Stoughton ACC From owner-ppp-comp Thu Oct 21 16:34:20 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq9W2-0000NJa; Thu, 21 Oct 93 16:33 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: New CCP draft (rev 01) Date: Thu, 21 Oct 93 16:32:40 PDT Message-ID: <9310212332.AA29435@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 The PPP Compression Control Protocol (CCP) draft-ieft-pppext-compression-01.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 of encapsulating multiple protocol datagrams 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 expires in six months [Page i] DRAFT PPP Compression October 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 expires in six months [Page 1] DRAFT PPP Compression October 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 mechanism 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 (0xFD) (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 expires in six months [Page 2] DRAFT PPP Compression October 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 some cases) may be sent uncompressed, using its standard form, or may be sent in multiple datagrams, if the compression algorithm supports it. Dave Rand expires in six months [Page 3] DRAFT PPP Compression October 1993 3. CCP Configuration Options CCP Configuration Options allow negotiation 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. If none of the protocols are not recognized, a Configure-Reject MAY be sent with the entire, unmodified Configure-Request. The original transmitter of the Configure-Request, which was hoping to negotiate a compression of future network data packets sent to it, SHOULD interpret such a Configure-Reject as indicating that none of the proposed compression protocols are possible. If any of the protocols are recognized but not acceptable due to local options in the request (or optional parameters not in the request), a Configure-NAK MUST be sent with the local options modified appropriately. The Configure-NAK SHOULD contain only those protocols that might be acceptable. Other protocols which are unacceptable, whether because unrecognized or for other reasons, MUST NOT be listed in the option in the Configure-NAK. A new Configure-Request MAY then be sent with the options adjusted as specified in the Configure-Nak. 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: CCP Option Meaning 1 Compression type negotiation (common) 2 Compression type negotiation (OUI/proprietary) Dave Rand expires in six months [Page 4] DRAFT PPP Compression October 1993 3.1. Compression Type Negotiation Option (common) Description This Configuration Option provides a way to negotiate the use of a standard compression algorithm. As of this writing, several compression algorithms are specified (see appendix). By default, compression is not enabled. 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 | Comp. Types | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | options... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 1 Length >= 3 Comp. Types (Compression Types) The compression types field lists the common compression algorithms that the are available. They must be listed in the order of desirability for this particular link. Each compression type is followed with a length, which may be 0. The length indicates the number of octets of compression-specific negotiation information, which may include items such as dictionary size, maximum string length and number of dictionaries. The receiver will process the compression types field from left to right, selecting the first protocol that matches the receiver's capability. If an acceptable compression protocol with acceptable options is encountered, the Configure-Request MUST be ACK'ed. The ACK MUST list only this acceptable protocol If no completely acceptable protocol is found, but one or more protocols are understood, but some or all of the compression negotiation options are not acceptable, these may be modified and sent back in a Configure-Nak. If none of the protocols are understood or no acceptable alternate Dave Rand expires in six months [Page 5] DRAFT PPP Compression October 1993 compression negotiation options are possible, a Configure-Reject MUST be transmitted. This Configure-Reject MUST be identical to the original Configure-Request as required by PPP protocols. Implementation of any particular compression algorithm IS NOT guaranteed. If all protocols the sender implements are Configure-Rejected by the receiver, then no compression is enabled. Default No compression protocol enabled. Dave Rand expires in six months [Page 6] DRAFT PPP Compression October 1993 3.2. Compression Type Negotiation Option (OUI/Proprietary) Description This Configuration Option provides a way to negotiate the use of a proprietary compression protocol. By default, such compression is not enabled. Since the first matching compression will be used, it is recommended that any known OUI compression options be transmitted first, before the common options are used. Before accepting this option, the implementation must verify that the Organizationally Unique Identifier identifies a proprietary algorithm that the implementation can decompress, and that any vendor specific negotiation options are fully understood. If no OUIs are supported by an implementation, a Configure-Reject may be sent back for any type 2 Compression Type Negotiation Option. 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 | OUI MS octet | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OUI remaining octects | Length | options... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 2 Length >= 3 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 any previous OUI has been received by the sender. When a supported vendor- specific proprietary compression is seen, and the option field is valid, a Configure-Ack may be sent to indicate acceptance of this Dave Rand expires in six months [Page 7] DRAFT PPP Compression October 1993 compression type. Multiple vendor-specific proprietary compression types may be implemented by the option field, which may contain algorithm selection information, negotiated options such as dictionary size, or any other information required. If the information in the option field is unrecognized, a Configure-Reject MUST be sent. If the information in the option field is recognized, but certain value(s) are unavailable, a Configure-Nak MAY be sent with the appropriate values modified. Any unrecognized proprietary compression configure request MUST have a Configure-Reject sent back. Length The Length field specifies the number of octects of OUI-specific negotiation information, in free format. It may be followed by 0 to 255 octets of negotiation information. options The options 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 expires in six months [Page 8] DRAFT PPP Compression October 1993 A. Common compression number identification The following numbers for common compression option use have been defined. Compression ID Algorithm specified 1 Predictor type 1 2 Predictor type 2 3 Puddle Jumper 16 Hewlett-Packard PPC 17 Stac Electronics LZS 18 Microsoft PPC 19 Gandalf FZA 20 V.42bis compression 21 UNIX LZW Compress IDs 4-15 are reserved for other freely-available implementations of compression algorithms. Dave Rand expires in six months [Page 9] DRAFT PPP Compression October 1993 B. Common compression algorithm definitions A compression algorithm that is available without license fees is the predictor algorithm, defined below. Note that although care has been taken to ensure that the following code does not infringe any patents, there is no assurance that it is not covered by a patent. Use the following code at your own risk. B.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 Dave Rand expires in six months [Page 10] DRAFT PPP Compression October 1993 File: A 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 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 #ifdef __STDC__ #include #endif #include /* * pred.c -- Test program for Dave Rand's rendition of the * predictor algorithm * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) * 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) static unsigned short int Hash; static unsigned char GuessTable[65536]; Dave Rand expires in six months [Page 11] DRAFT PPP Compression October 1993 static int 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); } static int 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--; Dave Rand expires in six months [Page 12] DRAFT PPP Compression October 1993 } 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); } #define SIZ1 8192 static void compress_file(f) FILE *f; { char bufp[SIZ1]; char bufc[SIZ1/8*9+9]; int len1, len2; while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) { len2 = compress((unsigned char *)bufp, (unsigned char *)bufc, len1); (void) fwrite(bufc, 1, len2, stdout); } } static void decompress_file(f) FILE *f; { char bufp[SIZ1+9]; char bufc[SIZ1*9+9]; int len1, len2, len3; len1 = 0; while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) { len1 += len3; len3 = len1; len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 0); (void) fwrite(bufc, 1, len2, stdout); (void) memcpy(bufp, bufp+len3-len1, len1); } Dave Rand expires in six months [Page 13] DRAFT PPP Compression October 1993 len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 1); (void) fwrite(bufc, 1, len2, stdout); } int main(ac, av) int ac; 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); (void) fclose(f); } } return(0); } B.2. Encapsulation for Predictor type 1 The correct encapsulation for type 1 compression is the protocol type, 1 bit indicating if the data is compressed or not, 15 bits of the uncompressed data length in octets, compressed data, and uncompressed CRC-16 of the two octets of unsigned length in network byte order, followed by 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC - 16 | Dave Rand expires in six months [Page 14] DRAFT PPP Compression October 1993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The CCP Protocol Identifier that starts the packet is always 0xfd. If PPP Protocol field compression has not be negotiated, it MUST be a 16-bit field. The Compressed data is the Protocol Identifier and the Info fields of the original PPP packet described in [1], but not the Address, Control, FCS, or Flag. The CCP Protocol field MAY be compressed as described in [1], regardless of whether the Protocol field of the CCP Protocol Identifier is compressed or whether PPP Protocol field compression has been negotiated. It is not required that any of the fields 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.3. Encapsulation 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 (uncompressed), compressed data, and uncompressed CRC-16 of the two octets of unsigned length in network byte order, followed by the original, uncompressed data. The data stream may be broken at any convenient place for encapsulation purposes. With type 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed | Compressed data... | 0 means data is not compressed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRC-16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| Uncompressed length (octets)| * is compressed flag +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Dave Rand expires in six months [Page 15] DRAFT PPP Compression October 1993 The CCP Protocol Identifier that starts the packet is always 0xfd. If PPP Protocol field compression has not be negotiated, it MUST be a 16-bit field. The Compressed data is the Protocol Identifier and the Info fields of the original PPP packet described in [1], but not the Address, Control, FCS, or Flag. The CCP Protocol field MAY be compressed as described in [1], regardless of whether the Protocol field of the CCP Protocol Identifier is compressed or whether PPP Protocol field compression It is not required that any field 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. C. 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. [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 Dave Rand expires in six months [Page 16] DRAFT PPP Compression October 1993 1983. [5] Reynolds, J., Postel,J., "Assigned Numbers", RFC 1340, USC/Information Sciences Institute, March 1990. [6] Perkins, D., Hobby, R., "Point-to-Point Protocol (PPP) initial configuration options", RFC 1172, August 1990. [7] Carr, D., "PPP Gandalf FZA Compression Protocol", Work in progress. [8] Lutz, R., "PPP Stacker LZS Compression Protocol", Work in progress. [9] Simpson, W.A., "PPP Puddle Jumper Compression Protocol", Work in progress. [10] Dimitri, T.J., "PPP Microsoft LZ Compression Protocol", Work in progress. 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. The predictor algorithm was originally implemented by Timo Raita, at the ACM SIG Conference, New Orleans, 1987. 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 Dave Rand expires in six months [Page 17] DRAFT PPP Compression October 1993 EMail: fbaker@acc.com Author's Address Questions about this memo can also be directed to: Dave Rand Novell, Inc. 2180 Fortune Drive San Jose, CA 95131 +1 408 321-1259 EMail: dave_rand@novell.com Dave Rand expires in six months [Page 18] DRAFT PPP Compression October 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 Compression Type Negotiation Option (common) .... 5 3.2 Compression Type Negotiation Option (OUI/Proprietary) ................................................. 7 APPENDICES ................................................... 9 A. Common compression number identification .............. 9 B. Common compression algorithm definitions .............. 10 B.1 Predictor algorithm .......................... 10 B.2 Encapsulation for Predictor type 1 ........... 14 B.3 Encapsulation for Predictor type 2 ........... 15 C. CCP Recommended Options ............................ 16 SECURITY CONSIDERATIONS ................................... 16 REFERENCES ................................................... 16 ACKNOWLEDGEMENTS ............................................. 17 CHAIR'S ADDRESS .............................................. 17 AUTHOR'S ADDRESS ............................................. 18 From owner-ppp-comp Thu Oct 21 16:40:13 1993 Return-Path: Received: by daver.bungi.com (Smail3.1.28.1 #1) id m0oq9bj-0000Wja; Thu, 21 Oct 93 16:39 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: LZW compression Date: Thu, 21 Oct 93 17:38:41 -0600 Message-ID: <9310212338.AA17563@rhyolite.wpd.sgi.com> Sender: owner-ppp-comp@daver Reply-To: ppp-comp@bungi.com Precedence: bulk From: dlr@daver.bungi.com > > One claim that stands out is that LZW requires ~500KByte of memory. > > I do not understand this, given that for many years netnews was > > transfered to and from PDP-11's, using 12-bit compression. > > Predictor's 64KB table is not small when viewed on a PDP-11. > > 16-bit unix compress requires about 500K for tables, per direction. > 12 bit requires less (but I'm not sure how much). Looks like the common source wants 450K for 16-bit, 230K for 15, 128K for 14, 74K for 13, and it's not obvious yet to me how much for 12-bit. For historical reasons (80*86's and PDP-11's), I bet 12-bit needs no more than 64K. Maybe it is 6*5003 or about 30K. Of course, while Predictor 1&2 want 64K, they need fewer CPU cycles. Vernon Schryver, vjs@sgi.com