Indirect measurement methodology to infer routing changes using statistics of flow arrival processes

• US 8,165,019 B2
• Filed: 07/14/2009
• Issued: 04/24/2012
• Est. Priority Date: 07/14/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Breslau, Lee, Dhamdhere, Amogh, Duffield, Nicholas, Ee, Cheng, Gerber, Alexandre, Lund, Carsten, Sen, Subhabrata
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US12/460,113
• Publication Number:
  US 20110013525A1
• Time in Patent Office: 1,015 Days
• Field of Search: None
• US Class Current: 370/229
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

Statistical methods are used to observe packet flow arrival processes and to infer routing changes from those observations. Packet flow arrivals are monitored using NetFlow or another packet flow monitoring arrangement. Packet flow arrivals are quantified by counting arrivals per unit time, or by measuring an inter-arrival time between flows. When a change in packet flow arrivals is determined to be statistically significant, a change in network routing protocol is reported.

Claims

1. A method for detecting routing changes in a packet-switched network, the method comprising:

in a packet flow analyzer connected to a router, monitoring packet flows traversing the router, wherein all packets of a packet flow are destined for the same destination;

in a computer connected for receiving data generated by the monitoring of the packet flows, statistically determining that a frequency of packet flows traversing a particular interface of the router has changed, including statistically detecting a decrease of flows to a particular destination; and

based on a determination that the frequency of packet flows traversing the particular interface of the router has changed, reporting a removal of the router from a route to the particular destination.

2. The method of claim 1, wherein monitoring packet flows traversing the router comprises monitoring packets arriving at a particular incoming interface.

3. The method of claim 1, wherein monitoring packet flows traversing the router comprises monitoring packets departing over a particular outgoing interface.

4. The method of claim 1, wherein monitoring packet flows traversing the router comprises recording an observation time of a first packet of each monitored packet flow.

5. The method of claim 4, wherein monitoring packet flows traversing the router further comprises recording an interface traversed by each monitored packet flow.

6. The method of claim 1, wherein monitoring packet flows traversing the router further comprises recording a number of packet flows traversing the router during each of a plurality of time bins.

7. The method of claim 1, wherein monitoring packet flows traversing the router further comprises recording flow inter-arrival times between sequential packet flows traversing the router.

8. The method of claim 1, wherein the destination to which all packets of a packet flow are destined comprises a destination selected from the group consisting of an IP destination address, an IP subnet and a network aggregate.

9. The method of claim 1, wherein all packets of a packet flow have in common a source address and a destination address.

10. The method of claim 1, further comprising:

repeating the monitoring and determining in association with a packet flow analyzer connected to a second router; and

determining an impact on the packet-switched network of the removal of the router from the route.

11. A non-transitory computer-usable medium having computer readable instructions stored thereon for execution by a processor to perform a method for detecting routing changes in a packet-switched network, the method comprising:

in a packet flow analyzer connected to a router, monitoring packet flows traversing the router, wherein all packets of a packet flow are destined for the same destination;

in a computer connected for receiving data generated by the monitoring of the packet flows, statistically determining that a frequency of packet flows traversing a particular interface of the router has changed, including statistically detecting a decrease of flows to a particular destination; and

based on a determination that the frequency of packet flows traversing the particular interface of the router has changed, reporting a removal of the router from a route to the particular destination.

12. The non-transitory computer-usable medium of claim 11, wherein monitoring packet flows traversing the router comprises monitoring packets arriving at a particular incoming interface.

13. The non-transitory computer-usable medium of claim 11, wherein monitoring packet flows traversing the router comprises monitoring packets departing over a particular outgoing interface.

14. The non-transitory computer-usable medium of claim 11, wherein monitoring packet flows traversing the router comprises recording an observation time of a first packet of each monitored packet flow.

15. The non-transitory computer-usable medium of claim 14, wherein monitoring packet flows traversing the router further comprises recording an interface traversed by each monitored packet flow.

16. The non-transitory computer-usable medium of claim 11, wherein monitoring packet flows traversing the router further comprises recording a number of packet flows traversing the router during each of a plurality of time bins.

17. The non-transitory computer-usable medium of claim 11, wherein monitoring packet flows traversing the router further comprises recording flow inter-arrival times between sequential packet flows traversing the router.

18. The non-transitory computer-usable medium of claim 11, wherein the destination to which all packets of a packet flow are destined comprises a destination selected from the group consisting of an IP destination address, an IP subnet and a network aggregate.

19. The non-transitory computer-usable medium of claim 11, wherein all packets of a packet flow have in common a source address and a destination address.

20. The non-transitory computer-usable medium of claim 11, wherein the method further comprises:

repeating the monitoring and determining in association with a packet flow analyzer connected to a second router; and

determining an impact on the packet-switched network of the removal of the router from the route.