Scalable network route analysis

• US 9,660,886 B1
• Filed: 07/28/2014
• Issued: 05/23/2017
• Est. Priority Date: 03/07/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ye, Fei, Zhang, Shidong, Vahdat, Amin, Ju, Mickey, Zeng, Hongyi, Ong, Joon
• Primary Examiner(s): Nawaz, Asad
• Assistant Examiner(s): Chang, Kai
• Application Number:
  US14/444,156
• Time in Patent Office: 1,030 Days
• CPC Class Codes: H04L 41/065 involving logical or physical relationship, e.g. grouping and hierarchies
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 49/55 Prevention, detection or correction of errors
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting

Abstract

This disclosure provides systems, methods and apparatus for providing a network verification system (NVS) to analyze and detect anomalies and errors within a network. The NVS requests forwarding tables from each of the switches within the network being analyzed, and generates directed forwarding graphs for each subnet within the network. Certain graph properties of the directed forwarding graphs are analyzed to detect anomalies or errors in the subnets represented by the directed forwarding graphs. In some implementations, the NVS can execute the generation of the directed forwarding graphs in parallel. In some implementations, the NVS can be implemented on a MapReduce system.

Claims

1. A method for analyzing a network for abnormalities, comprising:

receiving routing information from a plurality of switches within a network, the routing information including forwarding tables that list forwarding rules for forwarding packets within the network;

splitting the received routing information into N portions;

processing each of the N portions by identifying forwarding rules that pertain to each of M subnets belonging to the network, wherein a forwarding rule pertains to an Mth subnet if a prefix representing the Mth subnet can be fully included within a prefix associated with the forwarding rule;

forming M groups of forwarding rules such that each group only includes forwarding rules that pertain to the same Mth subnet;

generating M forwarding graphs for the M subnets, each of the M forwarding graphs being generated using the corresponding Mth group of forwarding rules;

identifying graph properties representative of network abnormalities in any of the M forwarding graphs; and

indicating network abnormalities identified in any of the M forwarding graphs, wherein M and N are integers greater than 1.

2. The method of claim 1, wherein processing each of the N portions of the routing information includes processing the N portions of the routing information in parallel.

3. The method of claim 1, wherein generating the M forwarding graphs for the M subnets includes generating the M forwarding graphs in parallel.

4. The method of claim 1, further comprising:

determining the M subnets from the routing information.

5. The method of claim 4, further comprising:

storing the M subnets in the form of a trie data structure, and

identifying forwarding rules that pertain to each of the M subnets by traversing the trie to identify that the prefix representing the Mth subnet is fully included within the prefix associated with the forwarding rule.

6. The method of claim 1, wherein the forwarding rules include a network address and at least one of a next hop switch identifier, a local switch identifier, and a priority.

7. The method of claim 2, wherein processing the N portions of the routing information in parallel includes utilizing one of N mapping functions of a MapReduce system for processing one of the N portions of the routing information.

8. The method of claim 3, wherein generating the M forwarding graphs in parallel includes utilizing one of M reducing functions of a MapReduce system for generating one of the M forwarding graphs.

9. The method of claim 1, wherein identifying the graph properties representative of network abnormalities in any of the M forwarding graphs includes identifying at least one of strongly connected components and zero-out degree within any of the M forwarding graphs.

10. A system for detecting network anomalies within a network comprising one or more processors executing:

a route dumper module configured to receive routing information from a plurality of switches within a network, the routing information including forwarding tables that list forwarding rules for forwarding packets within the network;

a forwarding rules splitting module configured to split the received routing information into N portions;

N match modules, each of the N match modules configured to process one of the N portions by identifying forwarding rules that pertain to each of M subnets belonging to the network, wherein a forwarding rule pertains to an Mth subnet if a prefix representing the Mth subnet can be fully included within a prefix associated with the forwarding rule;

a grouping module configured to form M groups of forwarding rules such that each group only includes forwarding rules that pertain to the same Mth subnet; and

M graphing modules, each of the M graphing modules configured to generate M forwarding graphs for the M subnets, each of the M forwarding graphs being generated using the corresponding Mth group of forwarding rules, wherein M and N are integers greater than 1.

11. The system of claim 10, wherein each of the M graphing modules is further configured to identify graph properties representative of network anomalies within the corresponding forwarding graph.

12. The system of claim 10, wherein the N match modules are implemented in parallel over N separate servers.

13. The system of claim 10, wherein the M graphing modules are implemented in parallel over M separate servers.

14. The system of claim 10, wherein the M subnets are determined from the routing information.

15. The system of claim 14, wherein the M subnets are stored in the form of a trie data structure, and wherein each of the N match modules is configured to identify all the subnets within the trie that have their prefix fully included within a prefix associated with the forwarding rule.

16. The system of claim 10, wherein the forwarding rules include a network address and at least one of a next hop switch identifier, a local switch identifier, and a priority.

17. The system of claim 12, wherein the N match modules are implemented in parallel utilizing N mapping functions of a MapReduce system.

18. The system of claim 13, wherein the M graphing modules are implemented in parallel utilizing M reduce functions of a MapReduce system.

19. The system of claim 11, wherein the graph properties representative of network anomalies can include at least one of strongly connected components and zero-out degree within the corresponding forwarding graph.