diff options
Diffstat (limited to 'doc/rfc/rfc5511.txt')
| -rw-r--r-- | doc/rfc/rfc5511.txt | 787 |
1 files changed, 787 insertions, 0 deletions
diff --git a/doc/rfc/rfc5511.txt b/doc/rfc/rfc5511.txt new file mode 100644 index 0000000..723e54f --- /dev/null +++ b/doc/rfc/rfc5511.txt @@ -0,0 +1,787 @@ + + + + + + +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: + <Path Message> + +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: + <SENDER_TEMPLATE> + + + + + + + +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: + <sender descriptor> + +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: + <Path Message> + +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: + <WF flow descriptor> ::= <FLOWSPEC> + + 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: + <SE flow descriptor> ::= <FLOWSPEC> <filter spec list> + + 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: + <PathTear Message> ::= <Common Header> [ <INTEGRITY> ] + <SESSION> <RSVP_HOP> + [ <sender descriptor> ] + + Example of nesting: + The optional operator can be nested. For example, + + <construct> ::= <MAND> [ <OPT_1> [ <OPT_2> ] ] + + 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: + <flow descriptor list> ::= <FF flow descriptor list> + | <SE flow descriptor> + + 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: + + <flow descriptor list> ::= <empty> | + <flow descriptor list> <flow descriptor> + + could be read to mean that an instance of <flow descriptor> 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: + + <construct> ::= <ALT_A> <ALT_B> | <ALT_C> <ALT_D> + + + + +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: + + <construct> ::= ( <ALT_A> <ALT_B> ) | ( <ALT_C> <ALT_D> ) + + or + + <construct> ::= <ALT_A> ( <ALT_B> | <ALT_C> ) <ALT_D> + + or + + <intermediary X> ::= <ALT_A> <ALT_B> + <intermediary Y> ::= <ALT_C> <ALT_D> + <construct> ::= <intermediary X> | <intermediary Y> + + or + + <intermediary Z> ::= <ALT_B> | <ALT_C> + <construct> ::= <ALT_A> <intermediary Z> <ALT_D> + +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: + <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 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 + + + <sequence> ::= <OBJECT> | + ( <OBJECT> <sequence> ) + + 3. Repetition can also be applied to a component of an assignment + to indicate the optional repetition of that component. For + example, the Notify message in [RFC3473] is defined as follows: + + <Notify message> ::= + <Common Header> [<INTEGRITY>] + [ [<MESSAGE_ID_ACK> | <MESSAGE_ID_NACK>] ... ] + [ <MESSAGE_ID> ] + <ERROR_SPEC> <notify session list> + + In this example, there is a sequence of zero or more instances + of [<MESSAGE_ID_ACK> | <MESSAGE_ID_NACK>]. One could argue that + the use of grouping (see Section 2.2.6) or a recursive construct + (see Note 2, above) would be more clear. + +2.2.6. Grouping + + Meaning: + A group of objects or constructs to be treated together. This + notation is not mandatory but is RECOMMENDED for clarity. See + Section 2.4 on Precedence. + + Encoding: + Round brackets ("(" and ")") enclosing a set of objects, + constructs, and operators. + + Example: + <group> ::= ( <this> <that> ) + + Notes: + 1. The precedence rule in Section 2.4 means that the use of + grouping is not necessary for the formal interpretation of the + BNF representation. However, grouping can make the BNF easier + to parse unambiguously. Either grouping or an intermediate + construct MUST be used for multi-alternates (Section 2.2.4). + + 2. Line breaks (Section 2.3.2) are often used to clarify grouping + as can be seen in the definition of <sequence> in Section 2.2.5, + but these are open to misinterpretation, and explicit grouping + is RECOMMENDED. + + 3. A practical alternative to grouping is the definition of + intermediate constructs as illustrated in Note 2 of Section + 2.2.4. + + + + +Farrel Standards Track [Page 10] + +RFC 5511 Routing BNF April 2009 + + +2.3. Editorial Conventions + +2.3.1. White Space + + White space (that is space characters) between operators, objects, + and constructs is ignored but SHOULD be used for readability. + +2.3.2. Line Breaks + + Line breaks within an assignment are ignored but SHOULD be used for + readability. + + Line breaks are often used to imply grouping within the precedence + rules set out in Section 2.4, but explicit grouping (Section 2.2.6) + or intermediary constructs (Section 2.2.4) SHOULD be used in new + definitions. + + A line break MUST NOT be present between the left-hand side of an + assignment and the assignment operator (see Section 2.2.1). + + New assignments (i.e., new construct or message definitions) MUST + begin on a new line. + +2.3.3. Ordering + + The ordering of objects and constructs in an assignment is explicit. + + Protocol specifications MAY opt to state that ordering is only + RECOMMENDED. In this case, elements of a list of objects and + constructs MAY be received in any order. + +2.4. Precedence + + Precedence is the main opportunity for confusion in the use of this + BNF. In particular, the use of alternatives mixed with + concatenations can give rise to different interpretations of the BNF. + Although precedence can be deduced from a "proper" reading of the BNF + using the rules defined above and the precedence ordering shown + below, authors are strongly RECOMMENDED to use grouping (Section + 2.2.6) and ordering (Section 2.3.3) to avoid cases where the reader + would otherwise be required to understand the precedence rules. + + Automated readers are REQUIRED to parse rules correctly with or + without this use of grouping. + + The various mechanisms described in the previous sections have the + following precedence, from highest (binding tightest) at the top, to + lowest (and loosest) at the bottom: + + + +Farrel Standards Track [Page 11] + +RFC 5511 Routing BNF April 2009 + + + objects, constructs + repetition + grouping, optional + concatenation + alternative + + Note: + Precedence is the main opportunity 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. + + Example: + + An example of the confusion in precedence can be found in Section + 3.1.4 of [RFC2205] and is mentioned in Section 2.2.4. + + <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 line break MAY be interpreted as implying grouping, but that is + not an explicit rule. However, the precedence rules say that + concatenation has higher precedence than the Alternative operator. + Thus, the text in [RFC2205] SHOULD be interpreted as shown in + formulation a. + + Similarly (from the same section of [RFC2205]): + + <flow descriptor list> ::= + <FLOWSPEC> <FILTER_SPEC> | + <flow descriptor list> <FF flow descriptor> + + SHALL be interpreted as: + + <flow descriptor list> ::= + ( <FLOWSPEC> <FILTER_SPEC> ) | + ( <flow descriptor list> <FF flow descriptor> ) + + The use of explicit grouping or intermediary constructs is strongly + RECOMMENDED in new text to avoid confusion. + + + +Farrel Standards Track [Page 12] + +RFC 5511 Routing BNF April 2009 + + +3. Automated Validation + + RBNF would be appropriate for verification using automated validation + tools. Validation tools need to be able to check for close + conformance to the rules expressed in this document to be useful for + verifying new documents, but should also be able to parse RBNF as + used in existing RFCs. No tools are known at this time. + +4. 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 unambiguous protocol specifications + reduce the likelihood of incompatible or defective implementations + that might be exploited in security attacks. + +5. Acknowledgments + + Thanks to Magnus Westerlund, Nic Neate, Chris Newman, Alfred Hoenes, + Lou Berger, Julien Meuric, Stuart Venters, Tom Petch, Sam Hartman, + and Pasi Eronen for review and useful comments. + +6. References + +6.1. Normative References + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + +6.2. Informative References + + [RFC2205] Braden, R., Ed., Zhang, L., Berson, S., Herzog, S., and S. + Jamin, "Resource ReSerVation Protocol (RSVP) -- 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., Ed., "Generalized Multi-Protocol Label + Switching (GMPLS) Signaling Resource ReserVation Protocol- + Traffic Engineering (RSVP-TE) Extensions", RFC 3473, + January 2003. + + + + + + + +Farrel Standards Track [Page 13] + +RFC 5511 Routing BNF April 2009 + + + [RFC4204] Lang, J., Ed., "Link Management Protocol (LMP)", RFC 4204, + October 2005. + + [RFC5234] Crocker, D., Ed., and P. Overell, "Augmented BNF for Syntax + Specifications: ABNF", STD 68, RFC 5234, January 2008. + + [RFC5440] Vasseur, JP., Ed., and JL. Le Roux, Ed., "Path Computation + Element (PCE) Communication Protocol (PCEP)", RFC 5440, + March 2009. + + [EBNF] ISO/IEC 14977, "Information technology -- Syntactic + metalanguage -- Extended BNF", 1996. + +Author's Address + + Adrian Farrel + Old Dog Consulting + + EMail: adrian@olddog.co.uk + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Farrel Standards Track [Page 14] + |