Granted Patent B1

US 7,620,712 · App. 10/385,995 · Granted Nov 17, 2009

Abstract

Claims (53)

1. Apparatus comprising:

a first network element for forwarding a set of packets associated with a first set of forwarding policy indicators along a label switched path to a second network element, wherein the first and second network elements are multi protocol label switching (MPLS) label switch routers (LSRs), and wherein the first set of forwarding policy indicators is a first set of forwarding equivalence classes (FECs) associated with the label switched path;

logic in the first network element for producing a first knowledge digest encoding the first set of forwarding policy indicators into a fixed length bit array, wherein the fixed length bit array is a bloom filter;

logic in the first network element for periodically sending probe messages containing the first knowledge digest to the second network element;

logic in the second network element for producing a second knowledge digest encoding a second set of forwarding policy indicators into a fixed length bit array, wherein the fixed length bit array is a bloom filter, and wherein the second set of forwarding policy indicators is a second set of forwarding equivalence classes (FECs) associated with the label switched path;

logic in the second network element for comparing the first knowledge digest to the second knowledge digest to determine whether the first set of forwarding policy indicators is a subset of the second set of forwarding policy indicators and for sending a misbranch indication to a central processor responsive to determining that the first set of forwarding policy indicators is not a subset of the second set of forwarding policy indicators; and

logic in the second network element for indicating availability of the label switched path as long as probe messages are received from the first network element in which the first set of forwarding policy indicators is determined to be a subset of the second set of forwarding policy indicators, and for indicating unavailability of the label switched path if probe messages are not received from the first network element after an interval of time.

2. The apparatus of claim 1 wherein the first set of FECs contains a single FEC and wherein the second set of FECs contains a single FEC.

3. Apparatus comprising:

a first interface on a network element for receiving periodically issued probe messages containing a first knowledge digest encoding a first set of forwarding policy indicators associated with a label switched network path as a fixed length bit array that is a bloom filter, wherein the network element is a multi-protocol label switched router (MPLS LSR), and wherein the first set of forwarding policy indicators is a first set of forwarding equivalence classes (FECs) associated with the label switched network path;

logic on the network element for producing a second knowledge digest encoding a second set of forwarding policy indicators and for causing the second knowledge digest to be stored on the first interface and on a second interface as a fixed length bit array that is a bloom filter, wherein the second set of forwarding policy indicators is a second set of forwarding equivalence classes (FECs) associated with the label switched network path;

logic on the first interface and on the second interface for comparing the first knowledge digest to the second knowledge digest to determine whether the first set of forwarding policy indicators is a subset of the second set of forwarding policy indicators and for sending a misbranch indication to a central processor responsive to determining that the first set of forwarding policy indicators is not a subset of the second set of forwarding policy indicators;

logic on the first interface for producing a first indication indicating unavailability of the label switched network path if the probe messages are not being received for a predetermined interval;

logic on the second interface for producing a second indication indicating availability of the label switched network path if the probe messages are received at the second interface in which the first set of forwarding policy indicators is determined to be a subset of the second set of forwarding policy indicators; and

logic on the network element for correlating the first indication with the second indication to determine whether the label switched network path was unavailable.

4. The apparatus of claim 3 wherein the first set of FECs contains a single FEC, and wherein the second set of FECs contains a single FEC.

5. Apparatus comprising:

a first interface on an MPLS LSR for receiving periodically issued probe messages containing a fixed length bit array that is a first bloom filter encoding a first set of forwarding policy indicators made up of a first set of forwarding equivalence classes (FECs) associated with a label switched path (LSP);

logic on the MPLS LSR for producing a fixed length bit array that is a second bloom filter encoding a second set of forwarding policy indicators made up of a second set of forwarding equivalence classes (FECs) associated with the label switched path and for causing the second bloom filter to be stored on the first interface and on a second interface;

logic on the first interface and on the second interface for comparing the first bloom filter to the second bloom filter to determine whether the first set of FECs is a subset of the second set of FECs and for sending a misbranch indication to a central processor responsive to determining that the first set of FECs is not a subset of the second set of FECs;

logic on the first interface for producing a first indication indicating unavailability of the label switched path if the probe messages are not being received for a predetermined interval;

logic on the second interface for producing a second indication indicating availability of the label switched path if the probe messages are received at the second interface in which the first set of FECs is determined to be a subset of the second set of FECs;

logic on the network element for correlating the first indication with the second indication to determine whether the label switched path was unavailable.

6. The apparatus of claim 5 wherein the first set of FECs contains a single FEC and wherein the second set of FECs includes a single FEC.

7. A method comprising the steps of:

forwarding by a first network element a set of packets associated with a first set of forwarding policy indicators along a label switched path to a second network element;

producing by the first network element a first knowledge digest encoding the first set of forwarding policy indicators into a fixed length bit array that is a bloom filter;

periodically sending probe messages containing the first knowledge digest from the first network element to the second network element;

producing by the second network element a second knowledge digest encoding a second set of forwarding policy indicators into a fixed length bit array that is a bloom filter;

comparing by the second network element the first knowledge digest to the second knowledge digest to determine whether the first set of forwarding policy indicators is a subset of the second set of forwarding policy indicators and sending a misbranch indication to a central processor responsive to determining that the first set of forwarding policy indicators is not a subset of the second set of forwarding policy indicators;

indicating, by the second network element, availability of the label switched path as long as probe messages are received from the first network element in which the first set of forwarding policy indicators is determined to be a subset of the second set of forwarding policy indicators, and for indicating unavailability of the label switched path if probe messages are not received from the first network element after an interval of time;

wherein the first and second network elements are MPLS LSRs;

wherein the first set of forwarding policy indicators is a first set of forwarding equivalence classes (FECs) associated with the label switched path; and

wherein the second set of forwarding policy indicators is a second set of FECs associated with the label switched path.

8. The method of claim 7 wherein the first set of forwarding equivalence classes contains a single forwarding equivalence class and wherein the second set of forwarding equivalence classes contains a single forwarding equivalence class.

9. A method comprising the steps of:

receiving at a first interface on a network element periodically issued probe messages containing a first knowledge digest encoding a first set of forwarding policy indicators associated with a label switched network path, wherein the first knowledge digest is a bloom filter, wherein the network element is a multi-protocol label switched router (MPLS LSR), and wherein the first set of forwarding policy indicators is a first set of forwarding equivalence classes (FECs) associated with the label switched network path;

producing by the network element a second knowledge digest encoding a second set of forwarding policy indicators, wherein the second knowledge digest is encoded as fixed length bit array that is a bloom filter, and wherein the second set of forwarding policy indicators is a second set of forwarding equivalence classes (FECs) associated with the label switched network path;

causing by the network element the second knowledge digest to be stored on the first interface and on a second interface;

comparing by the first interface and by the second interface the first knowledge digest to the second knowledge digest to determine whether the first set of forwarding policy indicators is a subset of the second set of forwarding policy indicators and sending a misbranch indication to a central processor responsive to determining that the first set of forwarding policy indicators is not a subset of the second set of forwarding policy indicators;

producing by the first interface a first indication indicating unavailability of the label switched network path if the probe messages are not being received for a predetermined interval;

producing by the second interface a second indication indicating availability of the label switched network path if the probe messages are received at the second interface in which the first set of forwarding policy indicators is determined to be a subset of the second set of forwarding policy indicators; and

correlating by the network element the first indication with the second indication to determine whether the label switched network path was unavailable.

10. The method of claim 9 wherein the first set of FECs contains a single FEC, and wherein the second set of FECs contains a single FEC.

11. A method comprising the steps of:

receiving at a first interface on an MPLS LSR periodically issued probe messages containing a fixed length bit array that is a first bloom filter encoding a first set of forwarding policy indicators made up of a first set of forwarding equivalence classes (FECs) associated with a label switched path (LSP);

producing by the MPLS LSR a fixed length bit array that is a second bloom filter encoding a second set of forwarding policy indicators made up of a second set of forwarding equivalence classes (FECs) associated with the label switched path;

causing by MPLS LSR the second bloom filter to be stored on the first interface and on a second interface;

comparing by the first interface and the second interface the first bloom filter to the second bloom filter to determine whether the first set of FECs is a subset of the second set of FECs and sending a misbranch indication to a central processor responsive to determining that the first set of FECs is not a subset of the second set of FECs;

producing, by the first interface, a first indication indicating unavailability of the path if the probe messages are not being received for a predetermined interval;

producing, by the second interface, a second indication indicating availability of the path if the probe messages are received at the second interface in which the first set of FECs is determined to be a subset of the second set of FECs; and

correlating by the MPLS LSR the first indication with the second indication to determine whether the label switched path was unavailable.

12. The method of claim 11 wherein the first set of FECs contains a single FEC and wherein the second set of FECs includes a single FEC.

Assignments (11)