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