Methods and systems for monitoring network routing

• US 20040221296A1
• Filed: 03/18/2004
• Published: 11/04/2004
• Est. Priority Date: 03/18/2003
• Status: Active Grant

• Current Assignee: Dynamic Network Services, Inc. (Oracle Corporation)
• Original Assignee: Renesys Corporation (Oracle Corporation)
• Inventors: Ogielski, Andrew T., Cowie, James H.
• Granted Patent: US 8,161,152 B2
• Time in Patent Office: Days
• US Class Current: 719/313
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• 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 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/16 Threshold monitoring
• 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

Abstract

The disclosed methods and systems include collecting routing data from a plurality of network routers, and correlating the routing data across routers and across time to obtain network data. The network data can be streamed to a user in real-time and the user can interactively query the data. In one embodiment, interactive routing analyses, drill-down, and forensics can be performed using a repository of Border Gateway Protocol (BGP) update traffic. Alarms can be set to detect selected routing problems. In setting the alarms, the message data for each router can be processed in timestamp order. Current message data from each router can be compared with previous message data to determine a condition status. An alarm can be provided when the condition status meets a temporal correlation criterion and/or a spatial correlation criterion.

Claims

1. A computer program tangibly stored on a computer-readable medium, the computer program comprising processor instructions to:

collect routing message data from a plurality of network routers, and,

correlate the routing message data across multiple routers and across time to obtain correlated data.

2. The computer program of claim 1, further comprising instructions to obtain routing patterns based on the correlated data.

3. The computer program of claim 1, where the instructions to collect routing message data comprise instructions to collect Border Gateway Protocol message data.

4. The computer program of claim 1, further comprising instructions to collect structural information regarding the network.

5. The computer program of claim 4, where the instructions to collect structural information comprise instructions to collect at least one of routing registry data and Domain Name Service data.

6. The computer program of claim 5, where the instructions to correlate comprise instructions to correlate the structural information with the routing message data.

7. The computer program of claim 1, further comprising instructions to stream the routing patterns in real-time over the network.

8. The computer program of claim 1, where the instructions to collect further comprise instructions to establish sessions between routers located in geographically diverse locations.

9. The computer program of claim 1, further comprising instructions to provide at least one alarm based on the routing patterns.

10. The computer program of claim 9, where the instructions to provide at least one alarm comprise instructions to:

process the message data for network prefixes in timestamp order,

compare current message data for each prefix with previous message data for the prefix to determine a condition status for alarm conditions of the prefix, and,

provide at least one alarm for the prefix based on a comparison of the condition status and at least one of a temporal correlation criterion and a spatial correlation criterion.

11. The computer program of claim 10, further comprising instructions to:

determine that the condition status meets the temporal correlation criteria when the condition status indicates at least one of the alarm conditions is high for a predetermined time duration, and

determine that the condition status meets the spatial correlation criteria when the condition status for a predetermined number of prefixes indicate a same alarm condition is high.

12. The computer program of claim 11, further comprising instructions to determine that the condition status satisfies the spatial correlation criteria when the condition status for a predetermined number of prefixes having a specified geographical distribution indicates a same alarm condition is high.

13. The computer program of claim 10, where the instructions to provide at least one alarm comprise instructions to:

assign a value to each of the at least one alarms,

apply a processing scheme to the values based on time, and

remove an identified of the at least one alarm based on a comparison of the value of the identified alarm to a predetermined value.

14. The computer program of claim 10, further comprising instructions to summarize a set of the at least one alarm to obtain a composite alarm.

15. The computer program of claim 14, where the instructions to summarize comprise instructions to combine the at least one alarm based on at least one of network prefixes, Autonomous Systems on the network, and sub-networks on the network.

16. The computer program of claim 15, where the instructions to combine the at least one alarm based on network prefixes comprise instructions to:

generate at least one of;

a list of more-specific prefixes and a list of origin Autonomous System prefixes based on the routing message data for the network prefixes, and

combine the at least one alarm for the more-specific prefixes and for the origin Autonomous System prefixes chosen from the respective lists.

17. The computer program of claim 10, further comprising instructions to present graphical representations of the at least one alarm provided to a user.

18. The computer program of claim 2, where the instructions to obtain routing patterns include instructions to process at least one time series of the correlated data.

19. The computer program of claim 18, where the instructions to process at least one time series comprise instructions to detect features in the correlated data corresponding to the routers having similar patterns of message data over selected portions of the at least one time series.

20. The computer program of claim 19, where the instructions to detect features comprise instructions to determine when the correlated data for each of the routers indicates the routing message data exceeds a threshold number of prefixes.

21. The computer program of claim 20, further comprising instructions to identify at least one of sub-networks and Autonomous Systems on the network corresponding to the correlated data of the features.

22. The computer program of claim 19, further comprising instructions to vary the timescales of the selected portions of the at least one time series.

23. The computer program of claim 18, where the instructions to process comprise instructions to apply a processing technique taken from a listing of signal processing techniques including feature detection, correlation, and clustering.

24. The computer program of claim 1, further comprising instructions to present graphical representations of at least one of the routing message data and the correlated data to a user.

25. The computer program of claim 24, where the instructions to present comprise instructions to:

interactively process user queries based on the graphical representations, and

present to the user those data of the routing message data and the correlated data that match the queries.

26. The computer program of claim 24, where the instructions to present include instructions to generate a record corresponding to the graphical representation and its associated routing data, whereby recalling the record generates the graphical representation according to the associated routing data.

27. The computer program of claim 26, where the record is an extensible Markup Language (XML) record.

28. A method, comprising:

collecting routing data from a plurality of network routers, and,

correlating the routing data across routers and across time to obtain network data.

29. The method of claim 28, further comprising:

streaming the network data to users over the network.

30. The method of claim 28, where correlating the routing data comprises determining at least one network metric, where the at least one network metric includes at least one of:

a globally reachable network prefix metric, an intensity metric indicative of total routing message traffic on the network, an unreachable network metric, a route instability metric, and route instability score distribution metrics.

31. The method of claim 30, where determining the globally reachable network prefix metric comprises determining default-free routing table sizes-over a predetermined timeframe.

32. The method of claim 30, where the globally reachable network prefix represents connectivity losses and degradation events and variations in a size of the network.

33. The method of claim 30, where determining the intensity metric comprises determining total route announcement message traffic and total withdrawal message traffic.

34. The method of claim 30, where determining the unreachable network metric comprises tracking a number of sub-networks estimated to be temporarily unreachable, optionally conditioned on prior reachability to correct for expected levels of sub-network arrivals and departures.

35. The method of claim 30, where determining the route instability metric comprises:

applying an instability score to each prefix,

cumulatively computing the instability score to routes to each prefix over time, and

suppressing the instability score following route stabilization.

36. The method of claim 30, where determining the route instability score distribution metrics comprises determining a set of vectorial metrics representing a breakdown of route instabilities according to severity and prefix size.

37. The method of claim 30, further comprising detecting features in the network data corresponding to the routers having similar patterns of network metrics over varying timescales.

38. The method of claim 37, where detecting features comprises determining when the network data for each of the routers indicates that a number of prefixes exceeds a threshold number of prefixes for at least one metric.

39. The method of claim 38, further comprising identifying at least one of sub-networks and Autonomous Systems corresponding to prefixes associated with the network data of the features.

40. A method, comprising:

processing, for a plurality of routers in a network, Border Gateway Protocol (BGP) UPDATE messages in timestamp order for each network prefix identified in the BGP UPDATE messages,

setting at least one alarm condition for each network prefix based on a comparison of current messages received and previous messages received,

correlating the at least one alarm condition over time and across routers, and

providing at least one alarm for a network prefix based on a comparison of the at least one alarm condition and at least one of a temporal correlation criterion and a spatial correlation criterion.

41. The method of claim 40, where providing at least one alarm comprises:

determining that the at least one alarm condition satisfies the temporal correlation criterion when the at least one alarm condition is set for a predetermined time duration, and,

determining that the at least one alarm condition satisfies the spatial correlation criteria when the at least one alarm condition is set for a predetermined number of routers.

42. The method of claim 41, where providing at least one alarm comprises determining that the at least one alarm condition meets the spatial correlation criteria when the at least one alarm condition is set for a predetermined number of routers having a specified geographical distribution.

43. The method of claim 40, where providing at least one alarm comprises:

assigning a value to each of the at least one alarm,

applying a processing scheme to the values to vary the values over time, and

removing an identified of the at least one alarm when the value of the identified alarm attains a predetermined value.

44. The method of claim 43, where applying a processing scheme comprises at least one of:

decreasing the values based on time, maintaining the values based on time, and increasing the values based on time.

45. The method of claim 40, further comprising summarizing a set of the at least one alarm to obtain a composite alarm.

46. The method of claim 40, where summarizing comprises combining the at least one alarm based on at least one of network prefixes, Autonomous Systems on the network, and sub-networks on the network.

47. The method of claim 46, where combining the at least one alarm based on network prefixes comprises:

generating at least one of;

a list of more-specific prefixes and a list of origin Autonomous System prefixes based on the routing message data for the network prefixes, and

combining the at least one alarm for the more-specific prefixes and for the origin Autonomous System prefixes chosen from the respective lists.

48. The method of claim 40, where setting at least one alarm condition comprises at least one of:

setting an ADVERTISED condition for a prefix to high when the prefix is advertised,

setting a CHANGED condition for a prefix to high when the prefix is advertised with at least one different attribute,

setting the CHANGED condition for a prefix to high when the prefix is withdrawn,

setting a DEGRADED condition for a prefix to high when the prefix is advertised with a longer ASPATH,

setting the DEGRADED condition for a prefix to high when the prefix is withdrawn,

setting a WITHDRAWN condition for a prefix to high when the prefix is withdrawn,

setting an UNREACHABLE condition for a prefix to high when the prefix is withdrawn and there is no route to a less specific prefix,

setting a DEAGGREGATION condition to high for a prefix when an unauthorized, more specific prefix is advertised,

setting an ORIGIN condition for a prefix to high when the prefix was advertised by an unauthorized Autonomous System on the network, and

setting the ORIGIN condition for a prefix to high when an Autonomous System on the network advertises an unauthorized prefix.