Internet-Draft M. Takefman R. Broberg Cisco Systems P. Lothberg Sprint July 31st, 1998 Enabling Byte Stuffing Transparency for RFC-1619 <draft-takefman-pppext-transper-00.txt Status of this Memo 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 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet- Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited. 1. Abstract Recent Internet Draft submissions and discussion on the PPP Extensions Working Group email list have highlighted transparency issues with the PPP over SONET/SDH mapping described in IETF RFC1619 and RFC1549. The HDLC byte stuffing described by RFC1549 can result in a worst case expansion of the actual payload data by a factor of 2. An algorithm suggested below limits the expansion factor to be a maximum of 6% the actual data to be transported. 2. Introduction Byte synchronous PPP (as described in RFC1549) is technique for link layer encoding of data streams on byte boundaries to maintain data transparency. The transparency processing used in PPP causes expansion of the data stream that is dependant on the contents of the data stream. On average the expansion factor is small enough to be ignored. However, a worst case expansion would result in the reduction of the available bandwidth by a factor of 2. Transparency processing is required in order to allow frame deliniation and the passage of control characters. Transparency processing ensures that control characters (0x7E, 0x7D) do not appear within the encoded data stream that is mapped into the payload. When a control character is encountered during the encoding phase the link layer inserts an escape character (0x7D) into the output stream and then XORs the control character with the value 0x20. This operation is referred to as stuffing as it results in one byte being represented by two. The receiver operation is quite simple, anytime an escape character is encountered it is deleted and the following character is XORed with 0x20. The following example shows part of a data stream before and after stuffing: pre-stuff 0x01 0x02 0x7E 0x7D 0x05 0x7D 0x06 0x7E 0x08 post-stuff 0x01 0x02 0x7D 0x5e 0x7D 0x5D 0x05 0x7D 0x5D 0x06 0x7D 0x5E 0x08 Assuming a random data stream there is a 2 in 256 chance that a stuffing operation will occur. Therefore, the average expansion factor (due to stuffing) of a PPP encoded stream will be less than 1%. The worst case expansion will occur if the frame to be transmitted consists of control characters. In this case, the expansion factor will be 100%, as every byte is transformed into 2 output bytes. 3. An option to PPP syncronous byte stuffing While the worst case expansion scenario is highly unlikely, it is always prudent to avoid problems, however unlikely, when possible. The following stuffing compression scheme provides a method for bounding the expansion factor. The key concept in this compression scheme is to recognize when stuff operations will occur within 32 bytes of each other. In this case, a new encoding can allow a single stuff operation to replace 2 stuff operations. An escape character is inserted into the data stream followed by a character encoded as follows: Bit Value / Description 7 1 to differentiate from the standard encoding. 6 1 if the first stuff operation is a 0x7E. 0 if the first stuff operation is a 0x7D. 5 1 if the second stuff operation is a 0x7E. 0 if the second stuff operation is a 0x7D. 4:0 the number of bytes between the stuff operations 0 indicates adjacent bytes. 31 indicates that 31 bytes are between the control characters. The second byte requiring stuffing is deleted from the stream as it has already been sent within the encoded byte. For the example stream shown above no expansion occurs and the post-stuff encoding is given by: 0x01 0x02 0x7D 0xC0 0x05 0x7D 0xA1 0x08 At the receiver, when a 0x7D is encounter the MSB of the next byte is checked to determine if the compressed stuffing operation occured. If so the escape character is deleted and the first compressed character is output and a counter is loaded with the distance value. If the counter is zero, the next byte to be output is the second compressed control character. Otherwise, the bytes following the encoded stuff byte are output, and the counter is decremented for each byte. Once the counter reaches zero the second compressed character is output. Compression does not extend across frame boundaries. Therefore the transmitter/receiver resets the compression/decompression state whenever the end of frame is found. Assume a large packet that starts with a control character and then has another control character every 33 characters. The first 33 characters will be transmitted as 34 characters. This repeats until the end of packet. The efficiency is therefore 34/33 or 1.030303. The degenerate case is when all packets are 34 bytes long with a control character at the begining and end. In this case the transmitted packet is 36 bytes long and the efficiency is therefore 36/34 or 1.058824. 4. Recommendations It is recommended that this be considered an optional feature for Packet Over Sonet links as defined by RFC1619. An implementation done by one of the authors at 622mbits/second leads us to believe that this can be scaled to 10gigabits/second. An RFC1619 implementation with the modification described above limits the maximum payload expansion to less than 6% thereby removing any concerns regarding the actual contents of the data. 5. Security Considerations RFC1619 as currently proposed does have what may be considered a weakness in that the available bandwidth of a given link is a function the data to be transported across that link. Given that POS links currently are aggregated from many smaller links it is considered highly unlikely that a malicous user could effect any serious harm on a link. Although the likelyhood of a steady stream of control characters passing across the link is extremely small the above algorithm is offered as way to bound the expansion to less than 6%. 6. References [1] W. Simpson, "PPP over SONET/SDH," RFC 1619, May 1994. [2] W. Simpson, "PPP in HDLC-like Framing," RFC 1549, December 1993. 7. Author Addresses M. Takefman Cisco Systems 146 Colonnade Road Suite 201 Nepean, Ontario Canada K2E7Y1 Email: tak@cisco.com R. Broberg Cisco Systems 170 West Tasman Drive San Jose, CA 94513 USA Email: rbroberg@cisco.com Peter Lothberg Sprint VARESA0104 12502 Sunrise Valley Drive Reston VA, 20196 Email: roll@stupi.se