System and method for network service path analysis

• US 20090097418A1
• Filed: 10/11/2007
• Published: 04/16/2009
• Est. Priority Date: 10/11/2007
• Status: Abandoned Application

• Current Assignee: Alterpoint Incorporated
• Original Assignee: Alterpoint Incorporated
• Inventors: Bayer, Stephen, Castillo, Roger
• Application Number:
  US11/974,107
• Publication Number:
  US 20090097418A1
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level

Abstract

Systems and methods for network service path analysis analyze and manage the delivery of applications over a network. A program running on a computer utilizes a Layer 3 topology of a computer network to create a directed graph representing deliverability of packets across the network. By analyzing access control lists and firewall rule sets from the network, along with modeling routing protocol behavior and policy as packet filters, the program performs a series of matrix multiplications, using an optimized decomposition of the IP packet space. The resulting matrix contains all of the path information for all deliverable packets. The matrix populates a network path database that captures the set of packets deliverable between any pair of Internet Protocol addresses in the network.

Claims

1. A method of creating a directed graph comprising nodes and edges of an IP network topology so that each edge may be queried for the transmissibility of a selected subset of the IP packet space, comprising:

creating a rule mask for each edge of a directed graph encoding a Boolean value for each partition of a decomposition of the IP packet space indicating the transmissibility across that edge of all packets contained in the partition; and

annotating the edges of the directed graph with said rule mask.

2. The method of claim 1 further comprising:

parsing a network device configuration for each network device in an IP network;

identifying inbound and outbound interfaces of said network devices;

analyzing network routing protocol configuration and interface packet filter configuration;

representing said network as a directed graph; and

decomposing the IP packet space into partitions.

3. The method of claim 1 further comprising:

selecting a set of packets;

locating said packet set within an IP space partition;

using said Boolean values to determine the transmissibility of said packet set across an edge of the directed graph.

4. A method of identifying the paths through an IP network over which selected packet sets may be delivered from a specified subnet to a specified subnet, comprising the steps of:

(a) creating a directed graph of the network topology comprising vertices, in which each directed graph vertex is selected from the set comprising a network device, an endpoint subnet, and a range of endpoint IP addresses, and in which each directed graph edge represents a nearest neighbor relation between a first device and a neighbor selected from the set comprising a second device, a subnet, and a range of endpoint IP addresses;

(b) annotating each directed graph edge with a description of subsets of the IP address space that are configured to be transmissible across the edge;

(c) creating a reachability matrix identifying for each vertex pair the subsets of the IP address space that are deliverable from one vertex to the other;

(d) identifying edges of the graph that will permit the transmission of the packet set;

(e) defining a head vertex and a tail vertex for a user-selected packet set transmission from a user-selected source device to a user-selected destination device; and

(f) determining a path for the user-selected packet set transmission from the user-selected source device to the user-selected destination device.

5. The method of claim 4 further comprising analyzing packet filter configurations of network device interfaces to determine elements in a configuration of devices in an IP network that cause a selected path through the network to be permitted.

6. The method of claim:

4 further comprising analyzing packet filter configurations of network device interfaces to determine elements in a configuration of devices in an IP network that cause a selected path through the network to be denied.

7. A method for creating a reachability matrix from the annotated directed graph in claim 4, comprising the steps of:

(a) decomposing the network into partitions of an IP packet space;

(b) generating a rule mask encoding a Boolean value for each partition in the decomposition, the state of said Boolean value indicating whether the packet set is deliverable from the source to the destination; and

(c) computing the transitive closure of said annotated directed graph.

8. The method of claim 7 in which the decomposition of IP space further comprises subsets of IP space wherein multiple packets will be delivered from any specified source to any specified destination across identical transmission paths, wherein said decomposition subsets comprises:

(a) a first set of rule boxes comprising packet filter rules configured on network device interfaces and routing configuration rules;

(b) a second set of rule boxes representing all possible intersections of subsets of packet filter rules and routing configuration rules; and

(c) a directed acyclic graph representing the superset-subset relations between said first set of rule boxes and said second set of rule boxes.

9. The method of claim 8 wherein said first and said second set of rule boxes is used to compute rule masks associated with packet filters configured on the inbound and outbound interfaces of a network device.

10. The method of claim 9 wherein a subset mask for said first and second sets of rule boxes in the :

decomposition of the space is computed as a by-product of a topological sort of the directed acyclic graph of decomposition subset relations.

11. The method of claim 5 wherein the step of annotating further comprises:

(a) defining a leading vertex and a trailing vertex for a selected path to an edge;

(b) computing a first rule mask for packet filters on an inbound interface associated with said leading vertex of said edge, a second rule mask for packet filters configured on an outbound interface associated with said trailing vertex of said edge, and a third rule mask for routing configuration configured on an outbound interface; and

(c) performing Boolean operations on said rule masks to determine a set of transmission rules.

12. A method of annotating edges of a directed graph of an IP network topology for the transmission of packets and sets of packets via routing rules and packet filters, wherein the network comprises network devices and interfaces between the network devices, so that each edge of the directed graph may be queried for the transmissibility of a selected subset of the IP packet space, comprising the steps of:

(a) decomposing the IP packet space into partitions, each partition having the property that the intersection of any collection of packet sets defined by packet filters and routing rules in configurations of the network devices will be expressible as the union of partitions in the decomposition;

(b) defining a rule mask for each edge; and

(c) encoding a Boolean value for each said partition indicating the transmissibility across the edge of all packets contained in the partition.

13. A method of network service path analysis comprising the steps of:

(a) obtaining a list of device interface-to-interface relationships for a computer network;

(b) obtaining a set of access control lists and rule sets from devices for the computer network;

(c) creating a Layer 3 topology model from the device interface-to-interface relationships and association of packet filters on interfaces that defines each interface'"'"'s packet filter configuration, each interface having an inbound and an outbound direction;

(d) defining a set of vertices for each Layer 3 device;

(e) defining a set of vertices for each endpoint subnet in the computer network;

(f) defining a vertex representing the public Internet;

(g) creating a directed graph comprising nodes for each device that routes traffic and/or performs packet filtering and for each subnet that contains host computers that are either providers or consumers of services where deliverability is to be analyzed, wherein the directed graph also comprises edges for each Layer 3 link between each device that routes traffic and the subnets that contain host computers that are either providers or consumers of services where deliverability is to be analyzed;

(h) defining two set of hyper-rectangles for each interface, one for the inbound and one for the outbound direction, representing sets of packets the interface'"'"'s packet filter configuration will either permit or deny across the interface;

(i) defining a set of hyper-rectangles for each interface representing sets of packets for which the routing configuration of the network permits outbound delivery;

(j) intersecting the hyper-rectangles defined for all interfaces by steps (h) and (i) to decompose the IP packet space into all hyper-rectangles that may result from the intersection of the hyper-rectangles defined for all interfaces by (h) and (i);

(k) representing the decomposition of a d-dimensional space as a set of hyper-rectangles and a directed acyclic graph describing their subset relations;

(l) representing all subsets of a hyper-rectangle in the decomposition of step (k) by means of a subset mask;

(m) representing the disposition, permit or deny, of sets of packets across an interface as rule masks encoding permit or deny values for each hyper-rectangle in the decomposition of step (k);

(n) calculating rules masks from hyper-rectangles defined in steps (h) and (i) and their associated subset masks;

(o) computing a rule mask for each edge of the directed graph of step (g) by performing Boolean operations on the rule masks defined by (m) by matching the inbound set for the leading vertex of the edge with the outbound sets computed for the trailing vertex of the edge;

(p) annotating each edge of the directed graph of step (g) with rule masks representing the deliverability of packets across the edge;

(q) determining the deliverability of packets by computing the transitive closure of the directed graph of step (p) where the Boolean operators of Warshall'"'"'s algorithm are applied to the arrays of Boolean values annotated at each edge;

(r) retrieving reachability for specific packet flows by means of a matrix of rule masks referencing the primary decomposition of the IP packet space;

(s) retrieving path information for specific packet flows by means of a directed graph annotated with rule masks and a reachability matrix of rule masks referencing the primary decomposition of the IP packet space; and

(t) retrieving the specific network device configuration elements that determined the deliverability or non-deliverability of specific packet flows by means of a directed graph annotated with rule masks and a reachability matrix of rule masks referencing the primary decomposition of the IP packet space.