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

• US 20110013525A1
• Filed: 07/14/2009
• Published: 01/20/2011
• 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: Ee, Cheng, Breslau, Lee, Dhamdhere, Amogh, Duffield, Nicholas, Gerber, Alexandre, Sen, Subhabrata, Lund, Carsten
• Granted Patent: US 8,165,019 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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 the steps of:

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; and

based on a determination that the frequency of packet flows traversing the particular interface of the router has changed, reporting a routing change in the packet-switched network.

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

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

4. The method of claim 1, wherein the step of 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 the step of monitoring packet flows traversing the router further comprises recording an interface traversed by each monitored packet flow.

6. The method of claim 1, wherein the step of 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 the step of 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 the steps of:

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

determining an impact of the routing change on the packet-switched network.

11. A 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 the steps of:

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; and

based on a determination that the frequency of packet flows traversing the particular interface of the router has changed, reporting a routing change in the packet-switched network.

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

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

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

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

16. The computer-usable medium of claim 11, wherein the step of 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 computer-usable medium of claim 11, wherein the step of monitoring packet flows traversing the router further comprises recording flow inter-arrival times between sequential packet flows traversing the router.

18. The 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 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 computer-usable medium of claim 11, wherein the method further comprises the steps of:

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

determining an impact of the routing change on the packet-switched network.