Internet DRAFT - draft-allan-fec-cv-overview
draft-allan-fec-cv-overview
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.
