End-to-end network access analysis

摘要

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.

主权项

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, andconstructing 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.