Networking Working Group                                       A. Farrel
Internet-Draft                                        Old Dog Consulting
Intended Status: Standards Track
Created: September 7, 2008
Expires: March 7, 2009


                  Reduced Backus-Naur Form (RBNF)
          A Syntax Used in Various Protocol Specifications

                 draft-farrel-rtg-common-bnf-02.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   Several protocols have been specified using a common variant of the
   Backus-Naur Form (BNF) of representing message syntax. However, there
   is no formal definition of this version of BNF.

   There is value in using the same variant of BNF for the set of
   protocols that are commonly used together. This reduces confusion and
   simplifies implementation.

   Updating exsting documents to use some other variant of BNF that is
   already formally documented would be a substantial piece of work.

   This document provides a formal deinition of the variant of BNF that
   has been used (called Reduced BNF), and makes it available for use by
   new protocols.

Farrel                    Expires March 7, 2009                 [Page 1]


Internet-Draft                 Reduced BNF                September 2008

1. Introduction

   Backus-Naur Form (BNF) has been used to specify the message formats
   of several protocols within the IETF. Unfortunately these
   specifications are not based on any specific formal definition of BNF
   and differ slightly from the definitions provided in other places.

   It is clearly valuable to have a formal definition of the syntax-
   defining language that is used. It would be possible to convert all
   existing specifications to use an established specification of BNF
   (for example, [RFC5234]), however this would require a lot of work.

   On the other hand, the variant of BNF used by the specifications in
   quesiton is consistent and has only a small number of constructs. It
   makes sense, therefore, to provide a definition of this variant of
   BNF to allow ease of interpretation of existing documents and to
   facilitate the development of new protocol specifications using the
   same variant of BNF.

   This document provides such a specification and names the BNF variant
   Reduced BNF (RBNF).

1.1. Existing Uses

   The first notable use of the variant of BNF that concerns us is in
   the specification of the Resource Reservation Protocol (RSVP)
   [RFC2205]. RSVP has gone on to be used in Multiprotocol Label
   Switching (MPLS) networks to provide signaling for Traffic
   Engineering (TE) [RFC3209], and this has been developed for use as
   the signaling protocol in Generalized MPLS (GMPLS) networks
   [RFC3473].

   Each of these three uses of RSVP has given rise to a considerable
   number of specifications of protocol extensions to provide additional
   features over and above those in the base documents. Each new feature
   is defined in its own document using the common form of BNF.

   New protocols have also been specificed using the same variant of
   BNF. This has arrisen partly because the developers were familiar
   with the BNF used in [RFC2205], etc., but also because of the overlap
   between the protocols especially with respect to the network objects
   controlled and operated.

   Notable among these additional protocols are the Link Management
   Protocol (LMP) [RFC4204] and the Path Computation Element Protocol
   (PCEP) [PCEP]. Both of these protocols have also given rise to a
   number of protocol extensions that also use the same variant of BNF.




Farrel                    Expires March 7, 2009                 [Page 2]


Internet-Draft                 Reduced BNF                September 2008

2. Formal Definitions

   The basic building blocks of BNF are rules and operators. At its
   simplest form, a rule in the context we are defining is a protocol
   object that is traditionally defined by a bit diagram in the
   protocol specification. Further and more complex rules are
   constructed by combining other rules using operators. The most
   complex rule is the protocol message that is constructed from an
   organization of protocol objects as specified by the operators.

2.1. Rule Definitions

   No semantics should be assumed from special characters used in rule
   names. For example, it would be wrong to assume that a rule carries a
   decimal number because the rule name begins or ends with the letter
   "d". However, individual specifications may choose to assign rule
   names in any way that makes the human interpretation of the rule more
   easy.

2.1.1. Rule Name Delimitation.

   All rule names are enclosed by angle brackets ("<" and ">").

   Example:
     <Path Message>

2.1.2. Data Objects

   The most basic (indivisible) rule is termed a data object.

   Data objects are named in upper case. They do not usually use spaces
   within the name, favoring hyphens ("-") or underbars ("_").

   Example:
     <SENDER_TEMPLATE>

2.1.3. Data Constructs

   Rules that are constructed from other rules using operators are
   termed data constructs.

   Data constructs are named in lower case, although captials may be
   used to indicate acronyms.

   Example:
     <sender descriptor>





Farrel                    Expires March 7, 2009                 [Page 3]


Internet-Draft                 Reduced BNF                September 2008

2.1.4. Protocol Messages

   The final objective is the definition of protocol messages. These are
   constructed from data objects and data constructs using operators.

   Data constructs are named in title case.

   Example:
     <Path Message>

2.2. Operators

2.2.1. Assignment

   Assignment is used to form data constructs and protocol messages.

   Meaning:
     The lefthand side is equivalent to the righthand side.

   Encoding:
     colon, colon, equal sign

   Example:
     <WF flow descriptor> ::= <FLOWSPEC>

   Note:
     The lefthand side of the assignment and the assignment operator
     must be present on the same line.

2.2.2. Sequential Combination

   Data objects and data constructs may be combined as a sequence to
   form a new data construct of protocol message.

   Meaning:
     The data objects of data constructs must be present in the order
     specified.

   Encoding:
     A sequence of data objects and data constructs ususally separated
     by spaces. May also be separated by line feeds.

   Example:
     <SE flow descriptor> ::= <FLOWSPEC> <filter spec list>







Farrel                    Expires March 7, 2009                 [Page 4]


Internet-Draft                 Reduced BNF                September 2008

2.2.3. Optional Presence

  Data objects and data constructs may be marked as optionally present.

  Meaning:
    The optional data objects or data consructs may be present or absent
    within the assignment. Unless indicated as optional, data objects
    and data constructs are mandatory.

  Encoding:
    Contained in square brackets ("[" and "]").

  Example:
    <PathTear Message> ::= <Common Header> [ <INTEGRITY> ]
                           <SESSION> <RSVP_HOP>
                           [ <sender descriptor> ]

  Note:
    The optional operator can be nested. For example,

      <construct> ::= <MAND> [ <OPT_1> [ <OPT_2> ] ]

    In this construction, the data object OPT_2 can only be
    present if OPT_1 is also present.

2.2.4. Alternatives

  Choices (exclusive or) may be indicated within assignments.

  Meaning:
    Either one thing or the other must be present.

  Encoding:
    The pipe symbol ("|")

  Example:
    <flow descriptor list> ::= <FF flow descriptor list>
                               | <SE flow descriptor>

  Note:
    Multi-way alternates are not currently common. To avoid
    confusion, grouping should be used (see Section 2.2.6), or
    an intermediary data construct may be created. Thus:

      <construct> ::= <ALT_ONE> | <ALT_TWO> | <ALT_THREE>

    is better presented as

      <construct> ::= ( <ALT_ONE> | <ALT_TWO> ) | <ALT_THREE>


Farrel                    Expires March 7, 2009                 [Page 5]


Internet-Draft                 Reduced BNF                September 2008

    or as

      <intermediaty construct> ::= <ALT_TWO> | <ALT_THREE>
      <construct> ::= <ALT_ONE> | <intermediaty construct>

2.2.5. Repetition

  It may be the case that a sequence of identical data objects or data
  constructs is required within an assignment.

  Meaning:
    One or more objects or constructs may be present.

  Encoding:
    Three dots ("...").

  Example:
    <Path Message> ::= <Common Header> [ <INTEGRITY> ]
                       <SESSION> <RSVP_HOP>
                       <TIME_VALUES>
                       [ <POLICY_DATA> ... ]
                       [ <sender descriptor> ]

  Notes:
    1. A set of zero or more objects or constructs may be achieved by
       combining with the Optional concept as shown in the example
       above.
    2. Sequences may also be encoded by buidling a recursive data
       construct using the Alternative operator. For example:

         <sequence> ::= <OBJECT> |
                        <OBJECT> <sequence>

2.2.6. Grouping

  Meaning:
    A group of objects or constructs to be treated together.
    This notation is not mandatory and is used only for clarity.
    See Section 2.2.10 on Precedence.

  Encoding:
    Round brackets ("(" and ")").

  Example:
    <group> ::= ( <this> <that> )






Farrel                    Expires March 7, 2009                 [Page 6]


Internet-Draft                 Reduced BNF                September 2008

  Note:
    The precedence rule in Section 2.2.10 means that the use of grouping
    is not necessary for the formal interpretation of the BNF
    representation. However, grouping may make the BNF easier to parse
    unambiguously. Line breaks are ofen used to clarify grouping as can
    be seen in the definition of <sequence> in Section 2.2.5.

2.2.7. White Space

   White space is ignored, but should be used for readability.

2.2.8. Line Feeds

   Line feeds are ignored, but should be used for readability. They can
   be used to enahnce readability when the precedence rules imply
   grouping as described in Section 2.2.6.

   A linefeed must not be present between the lefthand side of an
   assignment and the assignment operator (see Section 2.2.1).

2.2.9. Ordering

   The ordering of data objects and data constructs in an assigment is
   explicit.

   Protocol specifications may opt to state that ordering is only
   recommended. In this case, elements of a list of data objects and
   data constructs may be received in any order.

2.2.10. Precendence

   Precendence may be deduced from a "proper" reading of the BNF using
   these rules. Grouping and ordering are recommended for clarity.

   The various mechanisms described above have the following precedence,
   from highest (binding tightest) at the top, to lowest and loosest at
   the bottom:

      data objects, data constructs
      repetition
      grouping, optional
      concatenation
      alternative

   Note:
     Precedence is the main oportunity for confusion in the use of BNF.
     Authors are strongly recommended to use grouping (Section 2.2.6) in
     all places where there is any scope for misinterpretation even when
     the meaning is obvious to the authors.


Farrel                    Expires March 7, 2009                 [Page 7]


Internet-Draft                 Reduced BNF                September 2008

   Example:
     An example of the confusion in precedence can be found in Section
     3.1.4 of [RFC2205].

           <flow descriptor list> ::=  <empty> |
                            <flow descriptor list> <flow descriptor>

     The implementer must decide which of the following is intended.

     a.  <flow descriptor list> ::= <empty> |
                            ( <flow descriptor list> <flow descriptor> )

     b.  <flow descriptor list> ::= ( <empty> | <flow descriptor list> )
                                    | <flow descriptor>

     The linefeed may be interpreted as implying grouping, but that is
     not an explicit rule. However, the concatenation precedence says
     that concatenation has higher precedence than alternates. Thus, we
     should interpret (correctly) the text in [RFC2205] as shown in
     alternative a.

     Similarly (from the same section of [RFC2205]) we should interpret

           <flow descriptor list> ::=
                            <FLOWSPEC>  <FILTER_SPEC>  |
                            <flow descriptor list> <FF flow descriptor>

     as

           <flow descriptor list> ::=
                         ( <FLOWSPEC> <FILTER_SPEC> ) |
                         ( <flow descriptor list> <FF flow descriptor> )

3. Automated Validation

   RBNF would be appropriate for verification using automated validaiton
   tools. No tools are known at this time.

4. IANA Considerations

   This document makes no requests for IANA action.

5. Security Considerations

   This document does not define any network behavior and does not
   introduce or seek to solve any security issues.

   It may be noted that clear and unabmiguous protocol specifications
   reduce the likelihood of defective or incompatible implementations
   that might be exploited in security attacks.

Farrel                    Expires March 7, 2009                 [Page 8]


Internet-Draft                 Reduced BNF                September 2008

6. Acknowledgments

   Thanks to Magnus Westerlund, Nic Neate, and Chris Newman for review
   and useful comments.

7.  References

7.1.  Normative References

   None

7.2.  Informative References

   [RFC2205] Braden, R. (Ed.), Zhang, L., Berson, S., Herzog, S., and S.
             Jamin, "Resource ReserVation Protocol -- Version 1
             Functional Specification", RFC 2205, September 1997.

   [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
             and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
             Tunnels", RFC 3209, December 2001.

   [RFC3473] Berger, L., "Generalized Multi-Protocol Label Switching
             (GMPLS) Signaling Resource ReserVation Protocol-Traffic
             Engineering (RSVP-TE) Extensions", RFC 3473, January 2003.

   [RFC4204] Lang, J., Ed., "The Link Management Protocol (LMP)", RFC
             4204, September 2005.

   [RFC5234] Crocker, D. (Ed.) and Overell, P., "Augmented BNF for
             Syntax Specifications: ABNF", STD 68, RFC 5234, January
             2008.

   [PCEP]    Vasseur, J.P., and Le Roux, J.-L., "Path Computation
             Element (PCE) Communication Protocol (PCEP) - Version 1",
             draft-ietf-pce-pcep, work in progress.

Author's Address

   Adrian Farrel
   Old Dog Consulting

   Email: adrian@olddog.co.uk

Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

Farrel                    Expires March 7, 2009                 [Page 9]


Internet-Draft                 Reduced BNF                September 2008

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.




















Farrel                    Expires March 7, 2009                [Page 10]