Method of resolving conflicts in access control lists in router by comparing elements in the lists based on subsumption relations

• US 6,883,034 B1
• Filed: 02/12/2002
• Issued: 04/19/2005
• Est. Priority Date: 06/23/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McGuire, James G., Madan, Herbert S., Pelavin, Richard N.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US10/074,805
• Time in Patent Office: 1,162 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241, 709/242, 709/243, 709/244, 713/201, 370/471, 370/451
• US Class Current: 709/242
• 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/54 Organization of routing tables

Abstract

Methods are described for analyzing access list subsumption in routing devices of a computer network and for identifying computer network integrity violations, by producing structured data that includes stored router names and access lists that include elements with address/mask pairs, or patterns used to filter data into and out of a routing device, respectively; determining whether access lists in the structured data include elements in which a first element in the access list has a more general or equal address/mask pair, or pattern, respectively, than a second or subsequent element, or pattern; and storing in electronic memory a report of elements or a list of patterns, respectively, in which a first element or pattern is more general than or equal to a second or subsequent element or pattern.

Claims

1. A method of analysis of access list subsumption in routing devices of an actual or planned routed computer network, comprising:

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include elements with address/mask pairs, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include two or more elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list, wherein the respective access lists are structured such that the first element is encountered prior to the second element during typical processing of the respective access lists; and

storing in electronic memory a report of access list elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list.

2. The method of claim 1 wherein one or more of the respective stored access lists are respectively related to input packets and one or more of the respective stored access lists are respectively related to output packets and wherein the step of producing structured data is based at least in part on the respective stored access lists.

3. The method of claim 1 wherein each of the respective stored access lists is related to a respective level three protocol and wherein the step of producing structured data is based at least in part on the respective stored access lists.

4. The method of claim 3 wherein the respective level three protocol is one from a group consisting of IP, IPX, and AppleTalk and wherein the step of producing structured data is based at least in part on the respective stored access lists.

5. A method of identifying network integrity violations in a computer network, comprising:

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include patterns used to filter data into and out of a routing device, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include a subsumption relation in which a first pattern is more general than or equal to a second pattern, wherein the respective access lists are structured such that the first pattern is encountered prior to the second pattern during typical processing of the respective access lists; and

storing in electronic memory a list of subsumption relations identifying respective pairs of first and second patterns.

6. The method of claim 5 wherein one or more of the respective stored access lists are respectively related to input packets and one or more of the respective stored access lists are respectively related to output packets and wherein the step of producing structured data is based at least in part on the respective stored access lists.

7. The method of claim 5 wherein each of the respective stored access lists is related to a respective level three protocol and wherein the step of producing structured data is based at least in part on the respective stored access lists.

8. The method of claim 7 wherein the respective level three protocol is one from a group consisting of IP, IPX, and AppleTalk and wherein the step of producing structured data is based at least in part on the respective stored access lists.

9. A computer-readable medium carrying one or more sequences of instructions for analyzing access list subsumption in routing devices of an actual or planned routed computer network, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include elements with address/mask pairs, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include two or more elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list, wherein the respective access lists are structured such that the first element is encountered prior to the second element during typical processing of the respective access lists; and

storing in electronic memory a report of access list elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list.

10. The computer-readable medium of claim 9 wherein one or more of the respective stored access lists are respectively related to input packets and one or more of the respective stored access lists are respectively related to output packets and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

11. The computer-readable medium of claim 9 wherein each of the respective stored access lists is related to a respective level three protocol and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

12. The computer-readable medium of claim 11 wherein the respective level three protocol is one from a group consisting of IP, IPX, and AppleTalk and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

13. A computer-readable medium carrying one or more sequences of instructions for identifying network integrity violations in a computer network, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include patterns used to filter data into and out of a routing device, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include a subsumption relation in which a first pattern is more general than or equal to a second pattern, wherein the respective access lists are structured such that the first pattern is encountered prior to the second pattern during typical processing of the respective access lists; and

storing in electronic memory a list of subsumption relations identifying respective pairs of first and second patterns.

14. The computer-readable medium of claim 13 wherein one or more of the respective stored access lists are respectively related to input packets and one or more of the respective stored access lists are respectively related to output packets and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

15. The computer-readable medium of claim 13 wherein each of the respective stored access lists is related to a respective level three protocol and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

16. The computer-readable medium of claim 15 wherein the respective level three protocol is one from a group consisting of IP, IPX, and AppleTalk and wherein the instructions cause the one or more processors to carry out the step of producing structured data based at least in part on the respective stored access lists.

17. An apparatus for analyzing access list subsumption in routing devices of an actual or planned routed computer network, comprising:

means for producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include elements with address/mask pairs, and wherein said structured data associates respective access lists with respective router names;

means for determining whether respective access lists in the structured data include two or more elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list, wherein the respective access lists are structured such that the first element is encountered prior to the second element during typical processing of the respective access lists; and

means for storing in electronic memory a report of access list elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list.

18. An apparatus for identifying network integrity violations in a computer network, comprising:

means for producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include patterns used to filter data into and out of a routing device, and wherein said structured data associates respective access lists with respective router names;

means for determining whether respective access lists in the structured data include a subsumption relation in which a first pattern is more general than or equal to a second pattern, wherein the respective access lists are structured such that the first pattern is encountered prior to the second pattern during typical processing of the respective access lists; and

means for storing in electronic memory a list of subsumption relations identifying respective pairs of first and second patterns.

19. An apparatus for analyzing access list subsumption in routing devices of an actual or planned routed computer network, comprising:

a network interface coupled to the routed computer network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include elements with address/mask pairs, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include two or more elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list, wherein the respective access lists are structured such that the first element is encountered prior to the second element during typical processing of the respective access lists; and

storing in electronic memory a report of access list elements in which a first element in the access list has a more general or equal address/mask pair than a second element in the access list.

20. An apparatus for identifying network integrity violations in a computer network, comprising:

a network interface coupled to the routed computer network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

producing structured data in electronic memory which includes respective stored router names and respective stored access lists which respectively include patterns used to filter data into and out of a routing device, and wherein said structured data associates respective access lists with respective router names;

determining whether respective access lists in the structured data include a subsumption relation in which a first pattern is more general than or equal to a second pattern, wherein the respective access lists are structured such that the first pattern is encountered prior to the second pattern during typical processing of the respective access lists; and

storing in electronic memory a list of subsumption relations identifying respective pairs of first and second patterns.