Method for using a knowledge digest to verify configuration information in a network

• US 7,839,891 B1
• Filed: 03/11/2003
• Issued: 11/23/2010
• Est. Priority Date: 03/11/2003
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Allan, David
• Primary Examiner(s): Wilson, Robert W
• Application Number:
  US10/385,942
• Time in Patent Office: 2,814 Days
• Field of Search: None
• US Class Current: 370/469
• CPC Class Codes: H04L 41/0869 Validating the configuration within one network element
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A first network element forwards a set of packets associated with first configuration information along a path to a second network element. Logic in the first network element generates a first knowledge digest encoding the first configuration information into a fixed length bit array. Logic in the second network element generates a second knowledge digest encoding second configuration information into a fixed length bit array. Logic in the second network element compares the first knowledge digest to the second knowledge digest, and generates an indication if the comparison indicates that the first configuration information is not a subset of the second configuration information.

Claims

1. A method comprising the steps of:

forwarding a set of packets associated with first configuration information along a path from a first network element to a second network element;

producing by the first network element a first knowledge digest encoding the first configuration information into a first fixed length bit array;

producing by the second network element a second knowledge digest encoding second configuration information into a second fixed length bit array; and

comparing by the second network element the first knowledge digest to the second knowledge digest, and producing by the second network element a configuration error only if the comparison indicates that the first configuration information is not a subset of the second configuration information, the configuration error indicating that at least a portion of the first configuration information was never sent from the second network element to the first network element.

2. The method of claim 1 wherein the first configuration information includes a first single forwarding policy indicator.

3. The method of claim 2 wherein the second configuration information includes a second single forwarding policy indicator.

4. The method of claim 1 wherein the first and second knowledge digests are bloom filters.

5. The method of claim 4 wherein the first and second network elements are MPLS (Multi-Protocol Label Switched) link state routers, and wherein the first configuration information is a first set of at least one FECs (Forwarding Equivalence Classes), and wherein the second configuration information is a second set of at least one FECs.

6. The method of claim 5 wherein the first set of at least one FECs contains a first single FEC, and wherein the second set of at least one FECs contains a second single FEC.

7. A method comprising the steps of:

forwarding by a first network element a set of packets associated with first configuration information along a path to a second network element;

producing by the first network element a first knowledge digest encoding the first configuration information into a first fixed length bit array; and

forwarding by the first network element the first knowledge digest to the second network element, the second network element including logic for producing a second knowledge digest encoding second configuration information into a second fixed length bit array, the second network element also including logic for comparing the first knowledge digest to the second knowledge digest, and for producing a configuration error if the comparing indicates that the first configuration information is not a subset of the second configuration information, the configuration error indicating that at least a portion of the first configuration information was never sent from the second network element to the first network element.

8. The method of claim 7 wherein the first configuration information includes a first single forwarding policy indicator.

9. The method of claim 8 wherein the second configuration information includes a second single forwarding policy indicator.

10. The method of claim 7 wherein the first and second knowledge digests are bloom filters.

11. The method of claim 10 wherein the first and second network elements are MPLS (Multi-Protocol Label Switched) link state routers, and wherein the first configuration information is a first set of at least one FECs (Forwarding Equivalence Classes), and wherein the second configuration information is a second set of at least one FECs.

12. The method of claim 11 wherein the first set of at least one FECs contains a first single FEC, and wherein the second set of at least one FECs contains a second single FEC.

13. A method comprising the steps of:

receiving by a second network element a set of packets associated with second configuration information from a first network element;

producing by the second network element a second knowledge digest encoding the second configuration information into a second fixed length bit array;

comparing by the second network element the second knowledge digest to a first knowledge digest received from the first network element, the first knowledge digest encoding the first configuration information into a first fixed length bit array; and

producing by the second network element a configuration error if the comparing indicates that the first configuration information is not a subset of the second configuration information, said configuration error indicating that at least a portion of the first configuration information was never sent from the second network element to the first network element.

14. The method of claim 13 wherein the first configuration information includes a first single forwarding policy indicator.

15. The method of claim 14 wherein the second configuration information includes a second single forwarding policy indicator.

16. The method of claim 13 wherein the first and second knowledge digests are bloom filters.

17. The method of claim 16 wherein the first and second network elements are MPLS (Multi-Protocol Label Switched) link state routers, and wherein the first configuration information is a first set of at least one FECs (Forwarding Equivalence Classes), and wherein the second configuration information is a second set of at least one FECs.

18. The method of claim 17 wherein the first set of at least one FECs contains a first single FEC, and wherein the second set of at least one FECs contains a second single FEC.