Routing validation

• US 8,699,493 B2
• Filed: 03/05/2012
• Issued: 04/15/2014
• Est. Priority Date: 07/29/2005
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Cohen, Alain J., Singh, Pradeep K., Jeyachandran, Vinod, Gupta, Nitin
• Primary Examiner(s): Zhao, Wei
• Application Number:
  US13/412,604
• Publication Number:
  US 20120163197A1
• Time in Patent Office: 771 Days
• Field of Search: 370/392, 370/250, 709/238
• US Class Current: 370/392
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 41/0866 Checking the configuration
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A simulator simulates routing system protocols to build routing tables corresponding to a modeled network, and a comparator compares the routing tables in the actual network to these simulator-created routing tables. Because the modeled system represents a fault-free version of the actual system, and assuming that the modeled routing system protocols are representative of the algorithms used in the actual routers, these simulator-produced routing tables can represent steady-state routing tables that should be present in the routers of the actual network at steady state. By querying each router in the actual network for its routing table and comparing each routing table to the corresponding simulator-produced routing table, any differences from the steady state can be identified.

Claims

1. A method of identifying a cause of performance degradation in a network, said method comprising:

receiving, from the network, a first set of routing tables, wherein the first set of routing tables represent a current state of the network based on entries that indicate a next hop and a metric for a destination;

determining a second set of routing tables based on simulating changes to the first set of routing tables to a steady-state condition;

identifying a cause of performance degradation in the network based on differences between the entries in the first and second set of routing tables; and

outputting information indicating the cause of performance degradation;

wherein identifying the cause of performance degradation in the network comprises identifying at least one of;

at least one difference between at least one next hop in the first set of routing tables and a corresponding next hop in the second set of routing tables; and

at least one difference between the metric for a destination in the first set of routing tables and a corresponding metric in the second set of routing tables.

2. The method of claim 1, wherein receiving the first set of routing tables comprises querying a plurality of routers in the network.

3. The method of claim 1, wherein determining the second set of routing tables comprises generating a simulated model of the network by a computer processor and simulating a plurality of routers in the network.

4. The method of claim 3, wherein the simulated model of the network comprises parameters indicating one or more routing protocols employed in the network.

5. The method of claim 4, wherein the simulated model of the network comprises parameters indicating at least one routing table update algorithm corresponding to each of the one or more routing protocols.

6. A network monitoring system coupled to a network and configured to provide information indicating a suspected cause of degradation in performance of the network, said system comprising:

at least one interface, coupled to the network, configured to receive a plurality of routing tables from routers in the network, wherein the routing tables indicate a current state of the network and comprise entries for a next hop and a metric to a destination; and

a processor configured to model the network based on the received plurality of routing tables, simulate convergence of the network to a steady-state condition, determine a simulated set of routing tables based on the simulated steady-state condition, identify a suspected cause of degradation based on differences between entries in a set of routing tables received from the network and the simulated set of routing tables, and providing information indicating the suspected cause of degradation;

wherein the processor is configured to identify the suspected cause of the degradation by at least one of;

identifying at least one difference between at least one next hop in the received set of routing tables and a corresponding next hop in the simulated set of routing tables; and

identifying at least one difference between the metric for a destination in the received set of routing tables and a corresponding metric in the simulated set of routing tables.

7. The system of claim 6, wherein the processor is configured to query, via the at least one interface, a plurality of routers in the network for their respective routing tables.

8. The system of claim 6, wherein the processor is configured to simulate convergence of the network to a steady-state condition based on one or more routing protocols employed in the network.

9. The system of claim 8, wherein the processor is configured to simulate convergence of the network to a steady-state condition based on at least one routing table update algorithm corresponding to each of the one or more routing protocols.

10. A network monitoring system for monitoring performance of a network, said system comprising:

a query system configured to query routers in the network and receive routing tables from the routers having entries indicating next hops and metrics to destinations;

a simulator configured to model the network based on the received routing tables and determine a simulated set of routing tables representative for the simulated network at a steady-state condition; and

a comparator configured to compare the simulated set of routing tables representative of a steady-state condition of the simulated network with a set of routing tables from the network representative of a current state of the network and provide an output indicating differences between the simulated set of routing tables and the received set of routing tables;

wherein the comparator the determines the differences between the simulated set of routing tables and the received set of routing tables by at least one of;

identifying at least one difference between at least one next hop in the simulated set of routing tables and a corresponding next hop in the received set of routing tables; and

identifying at least one difference between the metric for a destination in the simulated set of routing tables and a corresponding metric in the received set of routing tables.

11. The system of claim 10, wherein the simulator is configured to determine the simulated set of routing tables at the steady-state condition based on one or more associated routing protocols.

12. The system of claim 10, wherein the simulator is configured to determine the simulated set of routing tables at the steady-state condition based on at least one routing table update algorithm corresponding to each of the one or more associated routing protocols.