    Network Working Group                                         C. Bormann
    Request for Comments: 2687                       Universitaet Bremen TZI
    Category: Standards Track                                 September 1999

                 PPP in a Real-time Oriented HDLC-like Framing

    Status of this Memo

       This document specifies an Internet standards track protocol for the
       Internet community, and requests discussion and suggestions for
       improvements.  Please refer to the current edition of the "Internet
       Official Protocol Standards" (STD 1) for the standardization state
       and status of this protocol.  Distribution of this memo is unlimited.

    Copyright Notice

       Copyright (C) The Internet Society (1999).  All Rights Reserved.

    Abstract

       A companion document describes an architecture for providing
       integrated services over low-bitrate links, such as modem lines, ISDN
       B-channels, and sub-T1 links [1].  The main components of the
       architecture are: a real-time encapsulation format for asynchronous
       and synchronous low-bitrate links, a header compression architecture
       optimized for real-time flows, elements of negotiation protocols used
       between routers (or between hosts and routers), and announcement
       protocols used by applications to allow this negotiation to take
       place.

       This document proposes the suspend/resume-oriented solution for the
       real-time encapsulation format part of the architecture.  The general
       approach is to start from the PPP Multilink fragmentation protocol
       [2] and its multi-class extension [5] and add suspend/resume in a way
       that is as compatible to existing hard- and firmware as possible.

    1.  Introduction

       As an extension to the "best-effort" services the Internet is well-
       known for, additional types of services ("integrated services") that
       support the transport of real-time multimedia information are being
       developed for, and deployed in the Internet.

       The present document defines the suspend/resume-oriented solution for
       the real-time encapsulation format part of the architecture.  As
       described in more detail in the architecture document, a real-time
       encapsulation format is required as, e.g., a 1500 byte packet on a

    Bormann                     Standards Track                     [Page 1]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       28.8 kbit/s modem link makes this link unavailable for the
       transmission of real-time information for about 400 ms.  This adds a
       worst-case delay that causes real-time applications to operate with
       round-trip delays on the order of at least a second -- unacceptable
       for real-time conversation.

       A true suspend/resume-oriented approach can only be implemented on a
       type-1 sender [1], but provides the best possible delay performance
       to this type of senders.  The format defined in this document may
       also be of interest to certain type-2-senders that want to exploit
       the better bit-efficiency of this format as compared to [5].  The
       format was designed so that it can be implemented by both type-1 and
       type-2 receivers.

    1.1.  Specification Language

       The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
       "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
       document are to be interpreted as described in RFC 2119 [8].

    2.  Requirements

       The requirements for this document are similar to those listed in
       [5].

       A suspend/resume-oriented solution can provide better worst-case
       latency than the pre-fragmenting-oriented solution defined in [5].
       Also, as this solution requires a new encapsulation scheme, there is
       an opportunity to provide a slightly more efficient format.

       Predictability, robustness, and cooperation with PPP and existing
       hard- and firmware installations are as important with suspend/resume
       as with pre-fragmenting.  A good suspend/resume solution achieves
       good performance even with type-2 receivers [1] and is able to work
       with PPP hardware such as async-to-sync converters.

       Finally, a partial non-requirement: While the format defined in this
       draft is based on the PPP multilink protocol ([2], also abbreviated
       as MP), operation over multiple links is in many cases not required.

    3.  General Approach

       As in [5], the general approach is to start out from PPP multilink
       and add multiple classes to obtain multiple levels of suspension.
       However, in contrast to [5], more significant changes are required to
       be able to suspend the transmission of a packet at any point and
       inject a higher priority packet.

    Bormann                     Standards Track                     [Page 2]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       The applicability of the multilink header for suspend/resume type
       implementations is limited, as the "end" bit is in the multilink
       header, which is the wrong place for suspend/resume operation.  To
       make a big packet suspendable, it must be sent with the "end" bit
       off, and (unless the packet was suspended a small number of bytes
       before its end) an empty fragment has to be sent afterwards to
       "close" the packet.  The minimum overhead for sending a suspendable
       packet thus is twice the multilink header size (six bytes, including
       a compressed multilink protocol field) plus one PPP framing (three
       bytes).  Each suspension costs another six bytes (not counting the
       overhead of the framing for the intervening packet).

       Also, the existing multi-link header is relatively large; as the
       frequency of small high-priority packets increases, the overhead
       becomes significant.

       The general approach of this document is to start from PPP Multilink
       with classes and provide a number of extensions to add functionality
       and reduce the overhead of using PPP Multilink for real-time
       transmission.

       This document introduces two new features:

       1)   A compact fragment format and header, and

       2)   a real-time frame format.

    4.  The Compact Fragment Format

       This section describes an optional multilink fragment format that is
       more optimized towards single-link operation and frequent suspension
       (type 1 senders)/a small fragment size (type 2 senders), with
       optional support for multiple links.

       When operating over a single link, the Multilink sequence number is
       used only for loss detection.  Even a 12-bit sequence number clearly
       is larger than required for this application on most kinds of links.
       We therefore define the following compact multilink header format
       option with a three-bit sequence number.

       As, with a compact header, there is little need for sending packets
       outside the multilink, we can provide an additional compression
       mechanism for this format: the MP protocol identifier is not sent
       with the compact fragment header.  This obviously requires prior
       negotiation (similar to the way address and control field compression
       are negotiated), as well as a method for avoiding the bit combination

    Bormann                     Standards Track                     [Page 3]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       0xFF (the first octet in an LCP frame before any LCP options have
       been negotiated), as the start of a new LCP negotiation could
       otherwise not be reliably detected.

                      Figure 1:  Compact Fragment Format

                        0   1   2   3   4   5   6   7
                      +---+---+---+---+---+---+---+---+
                      | R |  sequence |   class   | 1 |
                      +---+---+---+---+---+---+---+---+
                      |            data               |
                      :                               :
                      +---+---+---+---+---+---+---+---+

       Having the least significant bit always be 1 helps with HDLC chips
       that operate specially on least significant bits in HDLC addresses.
       (Initial bytes with the least significant bit set to zero are used
       for the extended compact fragment format, see next section.)

       The R bit is the inverted equivalent of the B bit in the other
       multilink fragment formats, i.e. R = 1 means that this fragment
       resumes a packet previous fragments of which have been sent already.

       The following trick avoids the case of a header byte of 0xFF (which
       would mean R=1, sequence=7, and class=7): If the class field is set
       to 7, the R bit MUST never be set to one.  I.e., class 7 frames by
       design cannot be suspended/resumed.  (This is also the reason the
       sense of the B bit is inverted to an R bit in the compact fragment
       format -- class 7 would be useless otherwise, as a new packet could
       never be begun.)

       As the sequence number is not particularly useful with the class
       field set to 7, it is used to distinguish eight more classes -- for
       some minor additional complexity, the applicability of prefix elision
       is significantly increased by providing more classes with possibly
       different elided prefixes.

       For purposes of prefix elision, the actual class number of a fragment
       is computed as follows:

       -  If the class field is 0 to 6, the class number is 0 to 6,

       -  if the class field is 7 and the sequence field is 0 to 7, the
          class number is 7 to 14.

    Bormann                     Standards Track                     [Page 4]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       As a result of this scheme, the classes 0 to 6 can be used for
       suspendable packets, and classes 7 to 14 (where the class field is 7
       and the R bit must always be off) can be used for non-suspendable
       high-priority classes, e.g., eight highly compressed voice streams.

    5.  The Extended Compact Fragment Format

       For operation over multiple links, a three-bit sequence number will
       rarely be sufficient.  Therefore, we define an optional extended
       compact fragment format.  The option, when negotiated, allows both
       the basic compact fragment format and the extended compact fragment
       format to be used; each fragment indicates which format it is in.

                   Figure 1:  Extended Compact Fragment Format

                         0   1   2   3   4   5   6   7
                       +---+---+---+---+---+---+---+---+
                       | R |  seq LSB  |   class   | 0 |
                       +---+---+---+---+---+---+---+---+
                       |      sequence -- MSB      | 1 |
                       +---+---+---+---+---+---+---+---+
                       |            data               |
                       :                               :
                       +---+---+---+---+---+---+---+---+

       In the extended compact fragment format, the sequence number is
       composed of three least significant bits from the first octet of the
       fragment header and seven most significant bits from the second
       octet.  (Again, the least significant bit of the second octet is
       always set to one for compatibility with certain HDLC chips.)

       For prefix elision purposes, fragments with a class field of 7 can
       use the basic format to indicate classes 7 to 14 and the extended
       format to indicate classes 7 to 1030.  Different classes may use
       different formats concurrently without problems.  (This allows some
       classes to be spread over a multi-link and other classes to be
       confined to a single link with greater efficiency.)  For class fields
       0 to 6, i.e. suspendable classes, one of the two compact fragment
       formats SHOULD be used consistently within each class.

       If the use of the extended compact fragment format has been
       negotiated, receivers MAY keep 10-bit sequence numbers for all
       classes to facilitate senders switching formats in a class.  When a
       sender starts sending basic format fragments in a class that was
       using extended format fragments, the 3-bit sequence number can be
       taken as a modulo-8 version of the 10-bit sequence number, and no
       discontinuity need result.  In the inverse case, if a 10-bit sequence
       number has been kept throughout by the receiver (and no major slips

    Bormann                     Standards Track                     [Page 5]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       of the sequence number have occurred), no discontinuity will result,
       although this cannot be guaranteed in the presence of errors.
       (Discontinuity, in this context, means that a receiver has to
       resynchronize sequence numbers by discarding fragments until a
       fragment with R=0 has been seen.)

    6.  Real-Time Frame Format

       This section defines how fragments with compact fragment headers are
       mapped into real-time frames.  This format has been designed to
       retain the overall HDLC based format of frames, so that existing
       synchronous HDLC chips and async to sync converters can be used on
       the link.  Note that if the design could be optimized for async only
       operation, more design alternatives would be available [4]; with the
       advent of V.80 style modems, asynchronous communications is likely to
       decrease in importance, though.

       The compact fragment format provides a compact rendition of the PPP
       multilink header with classes and a reduced sequence number space.
       However, it does not encode the E-bit of the PPP multilink header,
       which indicates whether the fragment at hand is the last fragment of
       a packet.

       For a solution where packets can be suspended at any point in time,
       the E-bit needs to be encoded near the end of each fragment.  The
       real-time frame format, to ensure maximum compatibility with type 2
       receivers, encodes the E-bit in the following way: Any normal frame
       ending also ends the current fragment with E implicitly set to one.
       This ensures that packets that are ready for delivery to the upper
       layers immediately trigger a receive interrupt even at type-2
       receivers.

       Fragments of packets that are to be suspended are terminated within
       the HDLC frame by a special "fragment suspend escape" byte (FSE).
       The overall structure of the HDLC frame does not change; the
       detection and handling of FSE bytes is done at a layer above HDLC
       framing.

       The suspend/resume format with FSE detection is an alternative to
       address/control field compression (ACFC, LCP option 8).  It does not
       apply to frames that start with 0xFF, the standard PPP-in-HDLC
       address field; these frames are handled as defined in [6] and [7].
       (This provision ensures that attempts to renegotiate LCP do not cause
       ambiguities.)

    Bormann                     Standards Track                     [Page 6]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       For frames that do not start with 0xFF, suspend/resume processing
       performs a scan of every HDLC frame received.  The FCS of the HDLC
       frame is checked and stripped.  Compact fragment format headers (both
       basic and extended) are handled without further FSE processing.
       (Note that, as the FSE byte was chosen such that it never occurs in
       compact fragment format headers, this does not require any specific
       code.)

       Within the remaining bytes of the HDLC frame ("data part"), an FSE
       byte is used to indicate the end of the current fragment, with an E
       bit implicitly cleared.  All fragments up to the last FSE are
       considered suspended (E = 0); the final fragment is terminated (E =
       1), or, if it is empty, ignored (i.e., the data part of an HDLC frame
       can end in an FSE to indicate that the last fragment has E = 0).

       Each fragment begins with a normal header, so the structure of a
       frame could be:

                    Figure 2:  Example frame with FSE delimiter

         0   1   2   3   4   5   6   7
       +---+---+---+---+---+---+---+---+
       | R |  sequence |   class   | 1 |
       +---+---+---+---+---+---+---+---+
       |            data               |
       :                               :
       +---+---+---+---+---+---+---+---+
       +              FSE              + previous fragment implicitly E = 0
       +---+---+---+---+---+---+---+---+
       | R |  sequence |   class   | 1 |
       +---+---+---+---+---+---+---+---+
       |            data               |
       :                               :
       +---+---+---+---+---+---+---+---+
       |             Frame             | previous fragment implicitly E = 1
       |              CRC              |
       +---+---+---+---+---+---+---+---+

       The value chosen for FSE is 0xDE (this is a relatively unlikely byte
       to occur in today's data streams, it does not trigger octet stuffing
       and triggers bit stuffing only for 1/8 of the possible preceding
       bytes).

       The remaining problem is that of data transparency.  In the scheme
       described so far, an FSE is always followed by a compact fragment
       header.  In these headers, the combination of a class field set to 7

    Bormann                     Standards Track                     [Page 7]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       with R=1 is reserved.  Data transparency is achieved by making the
       occurrence of an FSE byte followed by one of 0x8F, 0x9F, ... to 0xFF
       special.

                Figure 3:  Data transparency with FSE bytes present

               0   1   2   3   4   5   6   7
              +---+---+---+---+---+---+---+---+
              | R |  sequence |   class   | 1 |
              +---+---+---+---+---+---+---+---+
              |            data               |
              :                               :
              +---+---+---+---+---+---+---+---+
              +              FSE              + fragment NOT terminated
              +---+---+---+---+---+---+---+---+
              | R | S | T | U | 1 | 1 | 1 | 1 | R always is 1
              +---+---+---+---+---+---+---+---+
              |            data               | fragment continues
              :                               :

       In a combination of FSE/0xnF (where n is the first four-bit field in
       the second byte, RSTU in Figure 3), the n field gives a sequence of
       four bits indicating where in the received data stream FSE bytes,
       which cannot simply be transmitted in the data stream, are to be
       added by the receiver:

    0x8F: insert one FSE, back to data
    0x9F: insert one FSE, copy two data bytes, insert one FSE, back to data
    0xAF: insert one FSE, copy one data byte, insert one FSE, back to data
    0xBF: insert one FSE, copy one data byte, insert two FSE bytes, back
          to data
    0xCF: insert two FSE bytes, back to data
    0xDF: insert two FSE bytes, copy one data byte, insert one FSE, back
          to data
    0xEF: insert three FSE bytes, back to data
    0xFF: insert four FSE bytes, back to data

       The data bytes following the FSE/0xnF combinations and corresponding
       to the zero bits in the N field may not be FSE bytes.

       This scheme limits the worst case expansion factor by FSE processing
       to about 25 %.  Also, it is designed such that a single data stream
       can either trigger worst-case expansion by octet stuffing (or by bit
       stuffing) or worst-case FSE processing, but never both.  Figure 4
       illustrates the scheme in a few examples; FSE/0xnF pairs are written
       in lower case.

    Bormann                     Standards Track                     [Page 8]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

                     Figure 4:  Data transparency examples

                Data stream                     FSE-stuffed stream

                DD DE DF E0                     DD de 8f DF E0
                01 DE 02 DE 03                  01 de af 02 03
                DE DA DE DE DB                  de bf DA DB
                DE DE DE DE DE DA               de ff de 8f DA

       In summary, the real-time frame format is a HDLC-like frame delimited
       by flags and containing a final FCS as defined in [7], but without
       address and control fields, containing as data a sequence of FSE-
       stuffed fragments in compact fragment format, delimited by FSE bytes.
       As a special case, the final FSE may occur as the last byte of the
       data content (i.e. immediately before the FCS bytes) of the HDLC-like
       frame, to indicate that the last fragment in the frame is suspended
       and no final fragment is in the frame (e.g., because the desirable
       maximum size of the frame has been reached).

    7.  Implementation notes

    7.1.  MRU Issues

       The LCP parameter MRU defines the maximum size of the packets sent on
       the link.  Async-to-sync converters that are monitoring the LCP
       negotiations on the link may interpret the MRU value as the maximum
       HDLC frame size to be expected.

       Implementations of this specification should preferably negotiate a
       sufficiently large MRU to cover the worst-case 25 % increase in frame
       size plus the increase caused by suspended fragments.  If that is not
       possible, the HDLC frame size should be limited by monitoring the
       HDLC frame sizes and possibly suspending the current fragment by
       sending an FSE with an empty final fragment (FSE immediately followed
       by the end of the information field, i.e. by CRC bytes and a flag) to
       be able to continue in a new HDLC frame.  This strategy also helps
       minimizing the impact of lengthening the HDLC frame on the safety of
       the 16-bit FCS at the end of the HDLC frame.

    7.2.  Implementing octet-stuffing and FSE processing in one automaton

       The simplest way to add real-time framing to an implementation may be
       to perform HDLC processing as usual and then, on the result, to
       perform FSE processing.  A more advanced implementation may want to
       combine the two levels of escape character processing.  Note,
       however, that FSE processing needs to wait until two bytes from the
       HDLC frame are available and followed by a third to ensure that the
       bytes are not the final HDLC FCS bytes, which are not subject to FSE

    Bormann                     Standards Track                     [Page 9]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       processing.  I.e., on the reception of normal data byte, look for an
       FSE in the second-to-previous byte, and, on the reception of a
       frame-end, look for an FSE as the last data byte.

    8.  Negotiable options

       The following options are already defined by MP [2]:

       o    Multilink Maximum Received Reconstructed Unit

       o    Multilink Short Sequence Number Header Format

       o    Endpoint Discriminator

       The following options are already defined by MCML [5]:

       o    Multilink Header Format

       o    Prefix Elision

       This document defines two new code points for the Multilink Header
       Format option.

    8.1.  Multilink header format option

       The multilink header format option is defined in [5].  A summary of
       the Multilink Header Format Option format is shown below.  The fields
       are transmitted from left to right.

               Figure 5:  Multilink header format option

         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 = 27   |  Length = 4   |     Code      | # Susp Clses  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        As defined in [5], this LCP option advises the peer that the
        implementation wishes to receive fragments with a format given by
        the code number, with the maximum number of suspendable classes (see
        below) given.  This specification defines two additional values for
        Code, in addition to those defined in [5]:

       -  Code = 11: basic and extended compact real-time fragment format
          with classes, in FSE-encoded HDLC frame

       -  Code = 15: basic compact real-time fragment format with classes,
          in FSE-encoded HDLC frame

    Bormann                     Standards Track                    [Page 10]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       An implementation MUST NOT request a combination of both LCP
       Address-and-Control-Field-Compression (ACFC) and the code values 11
       or 15 for this option.

       The number of suspendable classes negotiated for the compact real-
       time fragment format only limits the use of class numbers that allow
       suspending.  As class numbers of 7 and higher do not require
       additional reassembly space, they are not subject to the class number
       limit negotiated.

    9.  Security Considerations

       Operation of this protocol is believed to be no more and no less
       secure than operation of the PPP multilink protocol [2].  Operation
       with a small sequence number range increases the likelihood that
       fragments from different packets could be incorrectly reassembled
       into one packet.  While most such packets will be discarded by the
       receiver because of higher-layer checksum failures or other
       inconsistencies, there is an increase in likelihood that contents of
       packets destined for one host could be delivered to another host.
       Links that carry packets where this raises security considerations
       SHOULD use the extended sequence number range for multi-fragment
       packets.

    10.  References

       [1]  Bormann, C., "Providing Integrated Services over Low-bitrate
            Links", RFC 2689, September 1999.

       [2]  Sklower, K., Lloyd, B., McGregor, G., Carr, D. and  T.
            Coradetti, "The PPP Multilink Protocol (MP)", RFC 1990, August
            1996.

       [3]  Simpson, W., "PPP in Frame Relay", RFC 1973, June 1996.

       [4]  Andrades, R. and F. Burg, "QOSPPP Framing Extensions to PPP",
            Work in Progress.

       [5]  Bormann, C., "The Multi-Class Extension to Multi-Link PPP", RFC
            2686, September 1999.

       [6]  Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD
            51, RFC 1661, July 1994.

       [7]  Simpson, W., Editor, "PPP in HDLC-like Framing", STD 51, RFC
            1662, July 1994.

    Bormann                     Standards Track                    [Page 11]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

       [8]  Bradner, S., "Key words for use in RFCs to Indicate Requirement
            Levels", BCP 14, RFC 2119, March 1997.

    11.  Author's Address

       Carsten Bormann
       Universitaet Bremen FB3 TZI
       Postfach 330440
       D-28334 Bremen, GERMANY

       Phone: +49.421.218-7024
       Fax:   +49.421.218-7000
       EMail: cabo@tzi.org

    Acknowledgements

       The participants in a lunch BOF at the Montreal IETF 1996 gave useful
       input on the design tradeoffs in various environments.  Richard
       Andrades, Fred Burg, and Murali Aravamudan insisted that there should
       be a suspend/resume solution in addition to the pre-fragmenting one
       defined in [5].  The members of the ISSLL subgroup on low bitrate
       links (ISSLOW) have helped in coming up with a set of requirements
       that shaped this solution.

    Bormann                     Standards Track                    [Page 12]

    RFC 2687      PPP in Real-time Oriented HDLC-like Framing September 1999

    Full Copyright Statement

       Copyright (C) The Internet Society (1999).  All Rights Reserved.

       This document and translations of it may be copied and furnished to
       others, and derivative works that comment on or otherwise explain it
       or assist in its implementation may be prepared, copied, published
       and distributed, in whole or in part, without restriction of any
       kind, provided that the above copyright notice and this paragraph are
       included on all such copies and derivative works.  However, this
       document itself may not be modified in any way, such as by removing
       the copyright notice or references to the Internet Society or other
       Internet organizations, except as needed for the purpose of
       developing Internet standards in which case the procedures for
       copyrights defined in the Internet Standards process must be
       followed, or as required to translate it into languages other than
       English.

       The limited permissions granted above are perpetual and will not be
       revoked by the Internet Society or its successors or assigns.

       This document and the information contained herein is provided on an
       "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
       TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
       BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
       HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
       MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

    Acknowledgement

       Funding for the RFC Editor function is currently provided by the
       Internet Society.

    Bormann                     Standards Track                    [Page 13]