Network Working Group A. Farrel
Request for Comments: 5511 Old Dog Consulting
Category: Standards Track April 2009
Routing Backus-Naur Form (RBNF): A Syntax Used to Form
Encoding Rules in Various Routing Protocol Specifications
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) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Farrel Standards Track [Page 1]
RFC 5511 Routing BNF April 2009
Abstract
Several protocols have been specified in the Routing Area of the IETF
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 existing 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 definition of the variant of BNF that
has been used (that we call Routing BNF) and makes it available for
use by new protocols.
Table of Contents
1. Introduction ....................................................3
1.1. Terminology ................................................3
1.2. Existing Uses ..............................................3
1.3. Applicability Statement ....................................4
2. Formal Definitions ..............................................4
2.1. Rule Definitions ...........................................5
2.1.1. Rule Name Delimitation ..............................5
2.1.2. Objects .............................................5
2.1.3. Constructs ..........................................6
2.1.4. Messages ............................................6
2.2. Operators ..................................................6
2.2.1. Assignment ..........................................6
2.2.2. Concatenation .......................................7
2.2.3. Optional Presence ...................................7
2.2.4. Alternatives ........................................8
2.2.5. Repetition ..........................................9
2.2.6. Grouping ...........................................10
2.3. Editorial Conventions .....................................11
2.3.1. White Space ........................................11
2.3.2. Line Breaks ........................................11
2.3.3. Ordering ...........................................11
2.4. Precedence ................................................11
3. Automated Validation ...........................................13
4. Security Considerations ........................................13
5. Acknowledgments ................................................13
6. References .....................................................13
6.1. Normative References ......................................13
6.2. Informative References ....................................13
Farrel Standards Track [Page 2]
RFC 5511 Routing BNF April 2009
1. Introduction
Backus-Naur Form (BNF) has been used to specify the message formats
of several protocols within the Routing Area of the IETF.
Unfortunately, these specifications are not based on any specific
formal definition of BNF, and they 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, Augmented BNF or ABNF [RFC5234]); however, this would
require a lot of work. It should be noted that in ABNF the terminals
are integers (characters/bytes), while in the BNF form used to define
message formats, the terminals are "objects" (some kind of message
elements, but not individual bytes or characters) or entire
"messages". This means that converting existing specifications to
use an established BNF specification would also require extensions to
that BNF specification.
On the other hand, the variant of BNF used by the specifications in
question (which is similar to a subset of Extended BNF [EBNF]) 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. A specification will also facilitate automated verification
of the formal definitions used in future documents.
This document provides such a specification and names the BNF variant
Routing BNF (RBNF).
1.1. Terminology
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 [RFC2119].
1.2. 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 been extended for use 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].
Farrel Standards Track [Page 3]
RFC 5511 Routing BNF April 2009
Each of these three uses of RSVP has given rise to a large 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 variant of BNF.
New protocols have also been specified using the same variant of BNF.
This has arisen 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) [RFC5440]. In both cases, further documents that specify
protocol extensions also use the same variant of BNF.
1.3. Applicability Statement
RBNF as defined in this document is primarily applicable for the
protocols listed in the previous section. The specification may be
used to facilitate the interpretation of the pre-existing RFCs that
are referenced. It should also be used in the specification of
extensions to those protocols.
RBNF could also be used for the specification of new protocols. This
is most appropriate for the development of new protocols that are
closely related to those that already use RBNF. For example, PCEP is
closely related to RSVP-TE, and when it was developed, the PCE
working group chose to use the same form of BNF as was already used
in the RSVP-TE specifications.
If a wholly new protocol is being developed and is not related to a
protocol that already uses RBNF, the working group should consider
carefully whether to use RBNF or to use a more formally specified and
broader form of BNF such as ABNF [RFC5234].
The use of RBNF to specify extensions to protocols that do not
already use RBNF (i.e., that use some other form of BNF) is not
recommended.
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
Farrel Standards Track [Page 4]
RFC 5511 Routing BNF April 2009
combining other rules using operators. The most complex rule is the
message that is constructed from an organization of protocol objects
as specified by the operators.
An RBNF specification consists of a sequence of rule definitions
using the operators defined in Section 2.2. One rule may be
constructed from a set of other rules using operators. The order of
definition of rules does not matter. That is, the subordinate rules
MAY be defined first and then used in subsequent definitions of
further rules, or the top-level rules MAY be defined first followed
by a set of definitions of the subordinate rules.
Rule definitions are read left-to-right on any line, and the lines
are read top-to-bottom on the page. This becomes particularly
important when considering sequences of rules and 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
easier.
2.1.1. Rule Name Delimitation
All rule names are enclosed by angle brackets ("<" and ">"). Rule
names MAY include any printable characters, but MUST NOT include tabs
or line feeds/breaks.
Example:
2.1.2. Objects
The most basic (indivisible) rule is termed an object. The
definition of an object is derived from its context.
Objects are typically named in uppercase. They do not usually use
spaces within the name, favoring underbars ("_").
Example:
Farrel Standards Track [Page 5]
RFC 5511 Routing BNF April 2009
2.1.3. Constructs
Rules that are constructed from other rules using operators are
termed constructs.
Constructs are named in lowercase, although capitals are commonly
used to indicate acronyms. Spaces and hyphens are used between words
within names.
Example:
2.1.4. Messages
The final objective is the definition of messages. These are rules
that are constructed from objects and constructs using operators.
The only syntactic difference between a message and a construct is
that no other rule is typically constructed from a message.
Messages are typically named in title case.
Example:
2.2. Operators
Operators are used to build constructs and messages from objects and
constructs.
2.2.1. Assignment
Assignment is used to form constructs and messages.
Meaning:
The named construct or message on the left-hand side is defined to
be set equal to the right-hand side of the assignment.
Encoding:
colon, colon, equal sign ("::=")
Example:
::=
Note:
The left-hand side of the assignment and the assignment operator
MUST be present on the same line.
Farrel Standards Track [Page 6]
RFC 5511 Routing BNF April 2009
2.2.2. Concatenation
Objects and constructs can be combined as a sequence to form a new
construct or a message.
Meaning:
The objects or constructs MUST be present in the order specified.
The order of reading RBNF is stated in Section 2.
Encoding:
A sequence of objects and constructs usually separated by spaces.
The objects in a sequence MAY be separated by line breaks.
Example:
::=
Note:
See Section 2.3.3 for further comments on the ordering of objects
and constructs.
2.2.3. Optional Presence
Objects and constructs can be marked as optionally present.
Meaning:
The optional objects or constructs MAY be present or absent within
the assignment. Unless indicated as optional, objects and
constructs are mandatory and MUST be present. The optional
operator can also be nested to give a hierarchical dependency of
presence as shown in the example below.
Encoding:
Contained in square brackets ("[" and "]").
Example:
::= [ ]
[ ]
Example of nesting:
The optional operator can be nested. For example,
::= [ [ ] ]
In this construction, the object OPT_2 can only be present if OPT_1
is also present.
Farrel Standards Track [Page 7]
RFC 5511 Routing BNF April 2009
Note:
The set of objects and constructs within the same pair of square
brackets is treated as a unit (an unnamed construct). This means
that when multiple objects and constructs are included within the
same pair of square brackets, all MUST be included when one is
included, unless nested square brackets are used as in the previous
example.
2.2.4. Alternatives
Choices can be indicated within assignments.
Meaning:
Either one rule or the other MUST be present.
Encoding:
The pipe symbol ("|") is used between the objects or constructs
that are alternatives.
Example:
::=
|
Notes:
1. Use of explicit grouping (Section 2.2.6) is RECOMMENDED to avoid
confusion. Implicit grouping using line breaks (Section 2.3.2)
is often used, but gives rise to potential misinterpretation and
SHOULD be avoided in new definitions.
2. Multiple members of alternate sets can give rise to confusion.
For example:
::= |
could be read to mean that an instance of must
be present or that it is optional.
To avoid this type of issue, explicit grouping (see Section
2.2.6), or an intermediary MUST be used in all new documents
(existing uses are not deprecated, and automatic parsers need to
handle existing RFCs). See also Section 2.4 for a description
of precedence rules.
Thus:
::= |
Farrel Standards Track [Page 8]
RFC 5511 Routing BNF April 2009
is not allowed in new documents and MUST be presented using
grouping or using an intermediary construct. For example, and
depending on intended meaning:
::= ( ) | ( )
or
::= ( | )
or
::=
::=
::= |
or
::= |
::=
2.2.5. Repetition
It could be the case that a sequence of identical objects or
constructs is required within an assignment.
Meaning:
MAY repeat the preceding object, intermediate construct, or
construct.
Encoding:
Three dots ("...").
Example:
::= [ ]
[ ... ]
[ ]
Notes:
1. A set of zero or more objects or constructs can be achieved by
combining with the Optional concept as shown in the example
above.
2. Sequences can also be encoded by building a recursive construct
using the Alternative operator. For example:
Farrel Standards Track [Page 9]
RFC 5511 Routing BNF April 2009
::=
RFC, FYI, BCP