End-to-end network access analysis

• US 9,253,038 B2
• Filed: 08/04/2009
• Issued: 02/02/2016
• Est. Priority Date: 08/08/2008
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Bhatt, Sandeep N, Rao, Prasad V, Okita, Cat
• Primary Examiner(s): CATTUNGAL, AJAY P
• Application Number:
  US13/057,511
• Publication Number:
  US 20110142051A1
• Time in Patent Office: 2,373 Days
• Field of Search: 370/238, 370/241, 370/250, 370/252, 370/254, 370/351, 370/392, 370/401, 370/400, 709/238, 709/249
• US Class Current: 1/1
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• 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

Abstract

Instances of router models and filter models respectively are populated with configuration data from routers and filters in a network. A route advertising graph is derived from the router model instances. The route advertising graph indicates propagation of routes between the ones of the real-world devices serving as routers according to routing protocols implemented by the ones of the real-world devices serving as routers. Consolidated routing data is determined for the ones of the real-world devices serving as routers. In this process, the propagation of routes indicated by the route advertising graph is iterated to stability. For a destination node in the network, a respective route graph indicating available paths to the destination node from each source node in the network is constructed from the consolidated routing data. Services between each source node and the destination node are classified based on a full traversal of the route advertising graph.

Claims

1. A computer-implemented method, comprising:

populating instances of router models with configuration data from real-world devices that serve as routers in a network and populating instances of filter models with configuration data from real-world devices that serve as filters in the network;

deriving a route advertising graph from the router model instances, wherein the route advertising graph indicates propagation of routes between the ones of the real-world devices serving as routers according to routing protocols implemented by the ones of the real-world devices serving as routers;

determining consolidated routing data for the ones of the real-world devices serving as routers;

for a destination node in the network, constructing from the consolidated routing data a respective route graph indicating available paths to the destination node from each source node in the network; and

classifying services between each source node and the destination node based on a full traversal of the route graph,

wherein the constructing comprises

building for the destination node a destination graph that comprises a respective node for each of the real-world devices and a respective directed edge between each pair of the nodes in the destination graph that is traversable by a packet destined for the destination node,

removing from the destination graph all filter nodes corresponding to respective ones of the real-world devices serving as filters to produce a set of disconnected sub-graphs,

within each of the sub-graphs, replacing each strongly connected component with a respective supernode that has all external incoming and outgoing edges of the component, and

constructing the route graph by interconnecting the supernodes and non-replaced ones of the nodes in the sub-graphs with the filter nodes that were removed from the destination graph.

2. The method of claim 1, wherein the populating comprises, for each of the real-world devices serving as a router in the network, populating a respective one of the router model instances with a specification of one or more routing methods implemented by the real-world device in connection with respective interfaces of the real-world device.

3. The method of claim 1, wherein the populating comprises, for each of the real-world devices serving as a filter in the network, populating a respective one of the filter model instances with specifications of physical interface connections to the real-world device, network translations applied to the physical interface connections, and access policies applied to the physical interface connections.

4. The method of claim 1, wherein the deriving comprises building the route advertising graph that comprises a respective node for each routing process and static route set in the real-world devices that serve as routers in the network, and further comprises a respective edge between each pair of nodes in the route advertising graph in which one of the nodes of the pair advertises to the other node in the pair.

5. The method of claim 1, wherein the determining comprises:

for each node in the route advertising graph, ascertaining a consolidated route information base that specifies all destination nodes in the network that are reachable by the associated real-world devices serving as respective routers and that comprises a respective list of next-hop interfaces for each of the reachable destination nodes.

6. The method of claim 1, wherein the route graph comprises all paths that are traversable by a packet from any source node in the network to the destination node.

7. The method of claim 1, wherein the classifying comprises for each of the services:

classifying the service into a first class in response to a determination that every path in the route graph from the source node to the destination node is open for the service;

classifying the service into a second class in response to a determination that every path in the route graph from the source node to the destination node is blocked for the service; and

classifying the service into a third class in response to a determination that one or more paths in the route graph from the source node to the destination node are open for the service and one or more paths in the route graph from the source node to the destination node are blocked for the service.

8. The method of claim 7, wherein the classifying comprises:

traversing every path in the route graph from the source node to the destination node;

for each of the traversed paths, maintaining a respective list of the ones of the services that are blocked, wherein the maintaining comprises for each filter on the path, adding to the respective list all the services that are blocked for the destination node;

for each of the traversed paths, adding the ones of the services enumerated in the respective list to a blocked list and adding the ones of the services not enumerated in the respective list to an open list;

classifying into the first class each of the services that appears only in the open list;

classifying into the second class each of the services that appears only in the blocked list; and

classifying into the third class each of the services that appears in both the open list and the blocked list.

9. The method of claim 1, further comprising verifying that the classification of the services is compliant with one or more end-to-end requirements associated with the network.

10. The method of claim 1, wherein the network comprises a set of destination nodes, and further comprising performing the constructing and the classifying for all destination nodes in the network.

11. Apparatus, comprising:

a non-transitory computer-readable medium storing computer-readable instructions; and

a processor coupled to the computer-readable medium, operable to execute the instructions, and based at least in part on the execution of the instructions operable to perform operations comprising

populating instances of router models with configuration data from real-world devices that serve as routers in a network and populating instances of filter models with configuration data from real-world devices that serve as filters in the network;

deriving a route advertising graph from the router model instances, wherein the route advertising graph indicates propagation of routes between the ones of the real-world devices serving as routers according to routing protocols implemented by the ones of the real-world devices serving as routers;

determining consolidated routing data for the ones of the real-world devices serving as routers;

for a destination node in the network, constructing from the consolidated routing data a respective route graph indicating available paths to the destination node from at least one source node in the network; and

classifying services between the source node and the destination node based on a full traversal of the route graph,

wherein in the classifying, the processor is operable to perform operations comprising, for each of the services;

classifying the service into a first class in response to a determination that every path in the route graph from the source node to the destination node is open for the service;

classifying the service into a second class in response to a determination that every path in the route graph from the source node to the destination node is blocked for the service; and

classifying the service into a third class in response to a determination that one or more paths in the route graph from the source node to the destination node are open for the service and one or more paths in the route graph from the source node to the destination node are blocked for the service.

12. The apparatus of claim 11, wherein in the populating the processor is operable to perform operations comprising:

for each of the real-world devices serving as a router in the network, populating a respective one of the router model instances with a specification of one or more routing methods implemented by the real-world device in connection with respective interfaces of the real-world device; and

for each of the real-world devices serving as a filter in the network, populating a respective one of the filter model instances with specifications of physical interface connections to the real-world device, network translations applied to the physical interface connections, and access policies applied to the physical interface connections.

13. The apparatus of claim 11, wherein the network comprises a set of destination nodes, and the processor is operable to perform operations comprising performing the constructing and the classifying for all destination nodes in the network.

14. At least one non-transitory computer-readable medium having computer-readable program code embodied therein, the computer-readable program code adapted to be executed by a computer to implement a method comprising:

populating instances of router models with configuration data from real-world devices that serve as routers in a network and populating instances of filter models with configuration data from real-world devices that serve as filters in the network;

deriving a route advertising graph from the router model instances, wherein the route advertising graph indicates propagation of routes between the ones of the real-world devices serving as routers according to routing protocols implemented by the ones of the real-world devices serving as routers;

determining consolidated routing data for the ones of the real-world devices serving as routers;

for a destination node in the network, constructing from the consolidated routing data a respective route graph indicating available paths to the destination node from each source node in the network; and

classifying services between each source node and the destination node based on a full traversal of the route graph,

wherein the classifying comprises, for each of the services;

classifying the service into a first class in response to a determination that every path in the route graph from the source node to the destination node is open for the service;

classifying the service into a second class in response to a determination that every path in the route graph from the source node to the destination node is blocked for the service; and

classifying the service into a third class in response to a determination that one or more paths in the route graph from the source node to the destination node are open for the service and one or more paths in the route graph from the source node to the destination node are blocked for the service.

15. The at least one non-transitory computer-readable medium of claim 14, wherein the populating comprises:

for each of the real-world devices serving as a router in the network, populating a respective one of the router model instances with a specification of one or more routing methods implemented by the real-world device in connection with respective interfaces of the real-world device; and

for each of the real-world devices serving as a filter in the network, populating a respective one of the filter model instances with specifications of physical interface connections to the real-world device, network translations applied to the physical interface connections, and access policies applied to the physical interface connections.

16. The at least one non-transitory computer-readable medium of claim 14, wherein the network comprises a set of destination nodes, and the method comprises performing the constructing and the classifying for all destination nodes in the network.