Internet Draft David Allan Document: draft-allan-fec-cv-overview-01.txt Nortel Networks Category: Informational October 2003 Overview of the FEC-CV proposed extension to the Y.1711 protocol Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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. Copyright Notice Copyright(C) The Internet Society (2003). All Rights Reserved. Abstract This Internet Draft provides an overview of the FEC-CV probe [Y17FEC-CV] proposed as an extension to the Y.1711 protocol. This is a private informational submission. Those interested in more detail are directed to the ITU-T recommendations and SG13/Q3 living lists. This has been updated from the previous version to include material incorporated at the July SG13/Q3 meeting. Sub-IP ID Summary [to be removed when published] WHERE DOES IT FIT IN THE PICTURE OF THE SUB-IP WORK Fits in the MPLS, PWE and PPVPN boxes. WHY IS IT TARGETED AT THESE WGs Allan Expires October 2003 Page 1 Overview of the FEC-CV proposed extension to the Y.1711 protocol This draft provides an overview of the Y.17FEC-CV PDU and suggests extensions whereby it can be applied to MPLS, PWs, PSNs and VPNs. 1. Introduction This draft provides an overview of the proposed FEC_CV extension to Y.1711. It is not normative and only represents a technical approach proposed to SG13/Q3 and currently documented as draft recommendation Y.17fec-cv [Y17FEC-CV]. The body of the document provides a functional overview, while the appendicies provide a short tutorial on bloom filters and the proposed PDU and coding rules for the FEC-CV probe message. 2. FEC-CV Overview Proposed and "provisionally agreed" for future enhancement to Y.1711 is the FEC-CV PDU. FEC-CV permits a combination of data plane misbranching defects and verification of the control plane against the data plane to be combined in a single lightweight PDU. FEC-CV employs a fixed length encoding to permit configuration information elements bound to an LSP, (or for that matter, any tunnel type) to be encoded as a 128 bit "Bloom filter" [BLOOM1][BLOOM2]. This functions as a verifiable "fingerprint" of LSP configuration and connectivity and typically allows a single transaction sent from the ingress to the egress to verify all configuration bound to an LSP is synchronized between the LSP end- points. This would include but is not limited to: - FECs bound to an LSP created via LDP - VPN RTs and RDs - PW-FECs - tunnel I.D.s and LSP I.D.s for TE trunks Multiple tokens can be encoded in the fixed length bloom filter so that a single FEC-CV PDU can verify the control plane aspects of an LSP that carries multiple FECs without any incremental 'per- message' processing. A practical limit is 10 FEC elements per LSP with the currently proposed encoding rules. Compliant LSRs would be expected to offer multiple labels when more than 10 FECs are required. Bloom Filters have significantly different properties when compared to a simple digest or checksum that makes it uniquely suited as a mechanism for conveying information for the purpose of verifying MPLS FECs. The principal property is that it allows comparisons to be performed between sets of information tokens. Interested readers are directed to appendix 'A' for a short tutorial. A high level view of the approach to using the bloom filters is that complexity in generating the bloom filters is traded for simplicity in subsequent repeated processing of the generated filters. When the LSP is established, nodes capable of performing filter processing compute bloom filters to associate with the LSP. Allan Expires October 2003 Page 2 Overview of the FEC-CV proposed extension to the Y.1711 protocol The LSP ingress(es) periodically will send a copy of the current FEC filter to the egress via the LSP in a FEC-CV PDU. The rate of FEC-CV insertion is unspecified, the proposed recommendation suggests this should be configurable over a broad range (1 sec to one minute intervals). Receipt of the FEC-CV probe permits the egress (and any intermediate systems capable of inspecting the probe) to perform a simple boolean test to simultaneously determine that: i) The configuration of tunnel at the ingress originating the probe corresponds to or is a reasonable subset of that offered by the egress for the tunnel. ii) The tunnel connectivity is correct (no misbranching). The output of the test is a simple pass/fail indication and the PDU carries sufficient information to facilitate subsequent fault diagnosis when a problem is detected. This is in the form of the TTSI which identifies the LSR originating the probe and access point ID. This can be used as a "stateless" test in which the egress (or intermediate nodes) simply verifies that any probes received are "reasonable" and flags any exceptions to management. This would complement normal link and node failure detection mechanisms by detecting faults not caught by other means. The egress may also choose to track availability per ingress by maintaining per ingress state (MP2P case) or via direct association of availability state with the LSP, PW or tunnel (P2P case) however this does lead to more complex implementation and alarm management issues. Some of which can be addressed by having the egress correlate failures with the routing system. The approach taken in specifying the FEC-CV PDU decouples the definition and implementation of probe handling from the definition of application specific configuration elements (typically FECs or VPN prefixes) that are verified. Future MPLS or other tunnel applications may be accommodated via filter coding rules that require no modifications to the FEC-CV PDU or handling. This permits ubiquitous deployment of misbranching detection to be deployed which addresses key carrier concerns [REQUIRE]. FEC-CV makes no special provisions for ECMP in the PDU design. It is recommended that LSRs implementing ECMP treat the set of downstream paths as LSP ingresses and periodically insert FEC-CV probes into each downstream path to extend misbranching detection to all ECMP path permutations. This avoids the redundant and overlapping testing that attempting to exercise all permutations from every probe origin would entail. Allan Expires October 2003 Page 3 Overview of the FEC-CV proposed extension to the Y.1711 protocol 3. Security Considerations Y.1711 and FEC-CV in particular is designed to be sufficiently simple that abuse for DOS attacks via volume of messaging should be difficult. However employment of Y.1711 in this application does generally assume trusted tunnel end points as otherwise spurious verification information may be inserted into the tunnel. This may causes false indication of mis-configuration or mis-direction of traffic. For VPN and PW applications, unintended security breaches caused by failure to synchronize configuration, control plane problems, or data plane mis-forwarding can be detected using FEC-CV in just about all instantiations of tunnel applications. 4. Summary FEC-CV provides a lightweight, application agnostic mechanism to simultaneously verify both correct configuration and connectivity for LSPs, PWs or VPN links. Support for future applications only requires the definition of filter coding rules. No actual protocol modifications or modifications to probe handling need be defined. This effectively makes implementations "future proof" and permits scalable verification to be incorporated into applications. FEC-CV complements existing link and node failure detection mechanisms by exclusively focusing on path misdirection problems. FEC-CV is easily adapted to ECMP implementations by treating the set of NHLFEs as LSP ingresses. 5. Intellectual Property Considerations Nortel Networks may pursue, or is pursuing, patent protection on technology described in this document. If this document becomes, in part or whole, an IETF Standard, and if such patented technology is essential for practice of an IETF Standard incorporating in whole or part this document, Nortel Networks would be willing to make available nonexclusive licenses on fair, reasonable, and non- discriminatory terms and conditions, to such patented technology to the extent it is essential to practice such IETF standard. 6. Acknowledgements My thanks to Jerome Chiabaut, Elwyn Davies, Greg Wright and Dean Frohwerk for their assistance and constructive input. 7. References [BLOOM1] Bloom, B., "Space/Time Trade Offs in Hash Coding with Allowable Errors", Communications of the ACM, Vol. 13, No. 7, July 1970 [BLOOM2] Ripeanu, M., Iamnitchi, A., "Bloom Filters - Short Allan Expires October 2003 Page 4 Overview of the FEC-CV proposed extension to the Y.1711 protocol Tutorial", www.cs.uchicago.edu/~matei/PAPERS/bf.doc [CR-LDP] Jamoussi et.al.,"Constraint Based LSP Setup using LDP", IETF RFC 3212, January 2002 [LDP] Andersson et.al., "LDP Specification", IETF RFC 3036, January 2001 [LSP-PING] Pan et.al. "Detecting MPLS Data Plane Failures", draft-ietf-mpls-lsp-ping-03, IETF work in progress, June 2003 [Y1711] ITU-T Recommendation Y.1711, "OAM mechanism for MPLS networks", November 2002 [Y17FEC-CV] ITU-T draft Recommendation Y.17fec-cv, "Misbranching Detection in MPLS Networks", July 2003 [RFC 2547] Rosen et.al. "BGP/MPLS VPNs", IETF Internet Draft, draft-ietf-ppvpn-rfc2547bis-02.txt, July 2002 [REQUIRE] Nadeau et.al., "OAM Requirements for MPLS Networks", IETF Internet Draft, draft-ietf-mpls-oam-requirements- 01.txt, June 2003 8. Author's Address David Allan Nortel Networks Phone: 1-613-763-6362 3500 Carling Ave. Email: dallan@nortelnetworks.com Ottawa, Ontario, CANADA 9. Full Copyright Statement "Copyright (C) The Internet Society (2003). Except as set forth below, authors retain all their rights. 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 rights in submissions defined in the IETF 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 Allan Expires October 2003 Page 5 Overview of the FEC-CV proposed extension to the Y.1711 protocol 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 CONTRIBUTOR, THE ORGANIZATION HE/S HE REPRESENTS (IF ANY), THE INTERNET SOCIETY 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." Allan Expires October 2003 Page 6 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'A': Short Tutorial on Bloom Filters A Bloom Filter is a form of knowledge digest. It is an unstructured bit array of fixed length. The actual length is fixed as a function of filter design. Typical applications for a Bloom Filter to date are as a digest of knowledge for information caches for communication to cache proxies, and dictionary search pre- processing in word processors. TO create a Bloom Filter, one uses hashing techniques to condense a representation of a token of information (e.g. prefix/mask) into some number of bits in the bit array where the relative bit positions are significant. There is a given probability that more than one token will hash to the same value for any one of the bits (bit collisions) but as more bits are used to represent a token, the probability that another token hashes to the exact same set of bits diminishes rapidly. When multiple tokens are encoded in a bit array (simply via logical OR of the individual filter representations), the probability of collision goes up (one token hashing to a subset of the bits set in the filter) but can still be bounded within a useful range via appropriate filter design for the application. Because the generation of the filter is lossy in the inclusive direction (due to the ORing of information as tokens are added to the filter), a test that shows a requisite bit for a token to not be in the filter is still an authoritative indication of non-membership. A simple example of bloom filter operation is: Filter engineering: 16 bit filter using two bits per FEC. "FEC A" hashes to bits 2 and 9 0000001000000100B "FEC B" hashes to bits 11 and 15 1000100000000000B "FEC C" hashes to bits 2 and 13 0010000000000100B "Set ABC" = A OR B OR C 1010101000000100B "FEC D" hashes to bits 11 and 14 0100100000000000B AND NOT "Set ABC" 0101010111111011B is non zero 0100000000000000B So "FEC D" is absolutely NOT in "Set ABC" "FECs AB" hash to bits 2,9,11 and 15 1000101000000100B AND NOT "Set ABC" 0101010111111011B is zero 0000000000000000B So "FECs AB" are in "set ABC" "FEC E" hashes to bits 9 and 13 0010001000000000B AND NOT "Set ABC" 0101010111111011B is zero, 0000000000000000B "FEC E" generates a "false positive" Allan Expires October 2003 Page 7 Overview of the FEC-CV proposed extension to the Y.1711 protocol This has application as a means of representing a set of FECs that permits a simple boolean operation on two filters to compare sets of information and produce a "pass/fail" result. The ingress LSRs will create a filter representing the set of FECs associated with the LSP and instantiated in the FTN. This will correspond to, or be a subset of, the set of FECs advertised by the egress for the termination of the LSP. All bits set in the ingress filter should also be present in the egress filter. Allan Expires October 2003 Page 8 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'B' The FEC-CV PDU 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Function (=7) | Reserved (=0) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | TTSI | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | FEC Filter | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved (=0) | BIP 16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Where: TTSI - Trail termination source identifier, combination of originating LSR ID and locally admininsted access point ID. FEC Filter - is a 16 byte bloom filter that encodes the functional description of the LSP (see appendix 'D' and 'E'). BIP16 - G(x)=x16+1 polynomial of the FEC-CV PDU (exact details specified in Y.1711) Allan Expires October 2003 Page 9 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'C' Filter Processing Rules Egress processing falls into one of two styles. 1) Reasonable subset The egress will AND the received ingress filter with the logical inverse of the egress filter. A non-zero result indicates a dFEC_Mismatch defect. If the egress has withdrawn a FEC element, it may tolerate a mismatch for an unspecified amount of time, and it MAY maintain a second filter containing the cumulative set of FEC elements offered for the LSP. If ANDing the received filter with the logical inverse of the cumulative filter yields a non-zero result, it indicates that the mismatch is not related to the withdrawl of the FEC element and dFEC_Mismerge defect state may be entered immediately. 2) Exact Match The egress will directly compare the received ingress filter with the egress filter. A not-equal result indicates either dFEC_Mismatch defect or a recent change has not propagated to the ingress. If the egress has changed the FEC filter, it may tolerate a mismatch for an unspecified amount of time. It MAY further perform filter testing to determine if the ingress filter is a subset of the current egress filter or cumulative egress filter in order to more quickly ascertain whether a genuine mismatch has occurred or is simply an artifact of hysteresis in the control plane. it indicates that the mismatch is not related to the withdrawl of the FEC element and dFEC_Mismatch defect state may be entered immediately. Allan Expires October 2003 Page 10 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'D': FEC-CV Encoding Procedure A filter entry is a filter representation of a single token of information. A filter entry is specified as an application specific number of filter offsets that correspond to specific bits in the FEC filter. Filter offsets are expressed as a single value in the range 0-127. Each filter offset represents a single bit in the 16 byte FEC filter. The upper 4 bits of the offset constitute an octet offset from the first byte of the filter, and the lower 3 bits of the offset constitute a bit offset in the octet, zero referring to the LS-Bit and 7 referring to the MS-Bit. A filter is initially zeroed, and the bit corresponding to each filter offset is ORed with the filter. Generalized coding: Coding rules are based primarily on the maximum number of filter entries that the filter is expected to carry for a given application. Filter offsets are generated from the CRC32 result. Generalized rules are provided for the generation of 2, 3, 4 and 5 filter offsets from CRC32. Coding rules are designed to (in general) preserve the hamming distance of the CRC via inclusion of the majority of information. Although not used in this Recommendation, specification of two offsets is included for applications that may require the ability to encode greater than 16 Filter Entries per LSP. Two offsets Two filter offsets are generated by: 1) Condensing each octet into a 7 bit value by XORing bit 8 into bit 7 and zeroing bit 8. 2) XORing together octets zero and one, and octets two and three to produce two 7 bit values. Three offsets Three filter offsets are generated by segmenting the CRC32 into 3 10 bit entities, then XORing the 7th,8th and 9th bits with the 4th, 5th and 6th respectively. The two most significant bits are unused. Four filter offsets Four filter offsets are generated via taking the lower 7 bits of each octet in the CRC32 and XORing the 8th bit of each octet with the 7th. Allan Expires October 2003 Page 11 Overview of the FEC-CV proposed extension to the Y.1711 protocol Five filter offsets Five filter offsets are generated by segmenting the CRC32 into four 7 bit offsets and the remaining lower 4 bits are used as the 4 LS- bits of the 5th offset. The CRC32 is then segmented on 9 bit boundaries parity performed on each to compute the upper 3 bits of the 5th offset. Allan Expires October 2003 Page 12 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'E': FEC-CV Application Specific Encoding E.1 Coding Rules for LDP [RFC3036] LSPs Coding Rules for ingress Each FEC element (as encoded per RFC 3036 [4] section 3.4.1) that is instantiated in the FTN table for the LSP is encoded as a filter entry consisting of three filter offsets. Coding Rules for the egress and intermediate nodes Each FEC element (as encoded per RFC 3036 section 3.4.1) that is offered to LDP peers for the LSP is encoded as a filter entry consisting of three (3) filter offsets. Filter processing The egress and intermediate nodes will perform "reasonable subset" filter processing. Limitations Using these coding rules, an upper limit of 10 FEC elements in a FEC filter is required to ensure > 99.9% probability of detecting all misbranching defects in a network supporting all of the applications outlined in this annex. E.2 Coding Rules for RFC 3209 (RSVP-TE) LSPs Coding Rules for ingress The ingress PE encodes the tunnel ID and extended tunnel ID extracted from the session object sect 4.6.1 RFC 3209) as a filter entry, and the LSP ID extracted from the sender template (sect 4.6.2 RFC 3209) as a filter entry. Both filter entries are composed of 4 filter offsets. If the extended tunnel ID is zero, then the tunnel sender address from the sender template object must be substituted. During reroute and bandwidth increase procedures (sect 4.3.4 of RFC 3209), the filter used contains the tunnel ID/extended tunnel ID filter entry and the old LSP ID filter entry until the RESV message confirming the path with the new LSP-ID is received. At this point the ingress revises the filter to contain the tunnel ID/extended tunnel ID filter entry and the new LSP ID filter entry. Allan Expires October 2003 Page 13 Overview of the FEC-CV proposed extension to the Y.1711 protocol Coding Rules for the egress and intermediate nodes The egress PE encodes the tunnel ID and extended tunnel ID extracted from the session object as a filter entry, and the LSP ID extracted from the sender template as a filter entry. If the extended tunnel ID is zero, then the tunnel sender address from the sender template object must be substituted. During reroute and bandwidth increase procedure (sect 4.3.4 of RFC 3209), upon receipt of a path message with a new LSP ID, both the old and new LSP IDs will be encoded as filter entries along with the tunnel ID and extended tunnel ID so that the change of LSP IDs at the probe origin does not result in an error. Upon receipt of the Pathtear message for the old LSP ID, the filter will be revised to only contain the current LSP ID as a filter entry. Filter Processing Processing nodes will perform "exact match" processing in normal operation, and "reasonable subset" processing during reroute and bandwidth increase procedures. Limitations Not applicable. The number of filter entries associated with an RFC3209 LSP is already bounded. Coding Rules for RFC 2547 (BGP/VPN) LSPs Coding Rules for ingress and egress The ingress PE encodes the BGP next hop information and each of the RDs associated with the LSP as filter entriers consisting of three filter offsets. Filter Processing Processing nodes will perform "exact match" filter processing. Coding Rules for RFC 3212 (CR-LDP) LSPs Coding rules for ingress intermediate, and egress LSRs The LSP-ID (sect 4.5 RFC 3213) and each CR_LSP FEC element (sect 4.10 RFC 3212) and/or LDP FEC element Sect 3.4.1 RFC 3036) is encoded as a filter entry consisting of 3 filter offsets. Limitations Using these coding rules, an upper limit of 10 FEC elements and the LSP-ID TLV in a FEC filter is required to ensure > 99.9% Allan Expires October 2003 Page 14 Overview of the FEC-CV proposed extension to the Y.1711 protocol probability of detecting all misbranching defects in a network supporting all of the applications outlined in this annex. Allan Expires October 2003 Page 15 Overview of the FEC-CV proposed extension to the Y.1711 protocol Appendix 'F' The CRC32 Polynomial Existing CRC32 polynomials (designed to operate on larger input lengths) do not offer randomization (measured via the Hamming distance) for shorter inputs comparable to polynomials selected specifically with the application characteristics in mind. This polynomial has been selected because the minimum Hamming distance is 10 for 64-bit inputs and then at least 8 for all input lengths up to 992 bits (124 octets). By comparison, the minimum Hamming distance of the standard Ethernet polynomial is only 8 for 64-bit inputs, drops to 7 at 92 bits (12 octets), then to 6 at 172 bits, and is only 5 above 268 bits. The 32-bit CRC used for the generation of FEC-CV filter entries is defined by the following generating polynomial: G(x) = x32+x30+x28+x21+x19+x15+x12+x9+x8+x4+x3+x2+x+1 Mathematically, the CRC is defined as the sum (modulo 2) of: 1) The remainder of (x31+x30+...+x+1)xk divided (modulo 2) by the generator polynomial, where k is the number of bits of the data over which the CRC is calculated; and 2) The remainder of the division (modulo 2) by the generator polynomial of the product of the data over which the CRC is calculated, interpreted as a polynomial, multiplied by x32. Algorithmically, the CRC is defined by the following procedure: a) The first 32 bits of the data are complemented. b) The k bits of the data are then considered to be the coefficients of a polynomial M(x) of degree k-1. c) M(x) is multiplied by x32 and divided by G(x), producing a remainder R(x) of degree at most 31 d) The coefficients of R(x) are considered to be a 32-bit, 4-octet sequence.