Routing Backus-Naur Form (RBNF): A Syntax Used to Form Encoding Rules in Various Routing Protocol Specifications
Extracted elements (22)
Precedence is identified as the main source of confusion in RBNF, particularly when alternatives are mixed with concatenations. The concrete example from RFC 2205 Section 3.1.4 illustrates how a line break could be misread as implying grouping; the precedence rules resolve it to formulation (a) where concatenation binds before the alternative.
RBNF was created rather than adopting ABNF (RFC 5234) because ABNF terminals are integers (characters/bytes), while routing protocol BNF terminals are 'objects' (protocol message elements) or entire 'messages'. Converting existing specifications to ABNF would require extensive document rework and extensions to ABNF itself.
The variant of BNF used across IETF Routing Area specifications (similar to a subset of Extended BNF) is internally consistent with only a small number of constructs. Providing a formal definition enables ease of interpretation of existing documents and facilitates automated verification of future protocol specifications.
RBNF is primarily applicable to RSVP (RFC 2205), RSVP-TE (RFC 3209), GMPLS (RFC 3473), LMP (RFC 4204), and PCEP (RFC 5440), and extensions thereto. Using RBNF for wholly new protocols unrelated to these is not recommended; ABNF (RFC 5234) should be considered instead. Using RBNF to specify extensions to protocols that already use a different BNF form is explicitly not recommended.
Authors are strongly RECOMMENDED to use explicit grouping wherever there is any scope for misinterpretation of precedence, even when the intended meaning is obvious to the authors. Implicit grouping via line breaks SHOULD be avoided in new definitions.
Automated readers (parsers) are REQUIRED to parse RBNF rules correctly with or without explicit grouping, including RBNF as used in pre-existing RFCs that predate this specification.
In new documents, any construct combining multiple concatenated elements as alternatives (e.g., <A> <B> | <C> <D>) MUST use explicit grouping or intermediary constructs. Existing ambiguous uses in legacy RFCs are not deprecated, and automated parsers must still handle them.
Rule names MUST NOT include tabs or line feeds/breaks; they MAY include any other printable characters.
The left-hand side of an assignment and the assignment operator MUST be present on the same line. Each new assignment (construct or message definition) MUST begin on a new line.
The ordering of objects and constructs in an assignment is explicit by default. Protocol specifications MAY opt to state that ordering is only RECOMMENDED, in which case elements MAY be received in any order.
Alternatives are encoded with the pipe symbol ("|") between mutually exclusive choices, meaning exactly one MUST be present. Explicit grouping is RECOMMENDED to avoid ambiguity when alternatives are mixed with concatenation.
Concatenation is expressed as a space-separated (or line-break-separated) sequence of objects and constructs, meaning all elements MUST be present in the specified left-to-right order.
Constructs are rules built from other rules using operators, conventionally named in lowercase with spaces or hyphens between words (e.g., <sender descriptor>). They serve as intermediate compositions between objects and messages.
Grouping uses round brackets ("(" and ")") to treat a set of objects, constructs, and operators as a single unit. Grouping is not syntactically mandatory but is RECOMMENDED for clarity and is REQUIRED when expressing multi-element alternatives in new documents.
Messages are the top-level rules constructed from objects and constructs using operators, conventionally named in title case (e.g., <Path Message>). The only syntactic difference from a construct is that no other rule is typically constructed from a message.
Objects are the most basic (indivisible) rule type, representing atomic protocol elements traditionally defined by bit diagrams. They are conventionally named in uppercase using underbars rather than spaces (e.g., <SENDER_TEMPLATE>).
Optional presence is encoded by enclosing objects or constructs in square brackets ("[" and "]"). Nested square brackets create hierarchical dependency: an inner optional is only valid when its enclosing outer optional is present.
RBNF operator precedence from highest (tightest binding) to lowest: objects/constructs, repetition, grouping/optional, concatenation, alternative. Concatenation therefore binds tighter than the alternative operator, which is the principal source of misinterpretation in existing RFCs.
Repetition is encoded using three dots ("...") following an object, intermediate construct, or construct, meaning it MAY be repeated. Combined with optional brackets (e.g., [ <OBJ> ... ]), this expresses zero-or-more occurrences.
Rule names are delimited by angle brackets ("<" and ">") and MAY include any printable characters. Rule names MUST NOT include tabs or line feeds/breaks. Example: <Path Message>.
The assignment operator '::=' defines a named construct or message. The left-hand side rule name and the assignment operator MUST appear on the same line; new assignments MUST begin on a new line.
RFC 5511 defines no network behavior and introduces no security issues. Clear and unambiguous protocol specifications, as enabled by RBNF, reduce the likelihood of incompatible or defective implementations that might be exploited in security attacks.