Method and apparatus for the assessment and optimization of network traffic

• US 7,773,536 B2
• Filed: 11/30/2007
• Issued: 08/10/2010
• Est. Priority Date: 10/17/2000
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: McGuire, James G., Finn, Sean P., Lloyd, Michael A., Karam, Mansour J., Madan, Herbert S., Baldonado, Omar C.
• Primary Examiner(s): Sheikh, Ayaz R
• Assistant Examiner(s): Ho, Chuong T
• Application Number:
  US11/998,678
• Publication Number:
  US 20080089241A1
• Time in Patent Office: 984 Days
• Field of Search: 370/252, 370/248, 370/241, 370/241.1, 370/242, 370/253, 370/237, 370/232, 370/233, 370/235, 370/238, 709/223, 709/224
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/5045 Making service definitions prior to deployment
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/0841 Round trip packet loss
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/283 : in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

A system for the assessment of network performance criteria, and applying this criteria to the classification of network addresses into appropriate ranges, using these ranges to consolidate performance measurements for the associated addresses, and applying these metrics toward the optimization of the network towards performance or policy objectives.

Claims

1. A method of optimizing traffic in an internetwork, the method comprising:

selecting, by one or more network devices, a subset of flows in the internetwork for monitoring, wherein the subset of flows includes one of one flow, some flows, and all flows;

measuring performance characteristics of the subset of flows in at least a portion of the internetwork, the performance characteristics including a plurality of one or more round trip measurements for each of the subset of flows and a plurality of one or more one-way measurements for each of the subset of flows, the measuring performance characteristics including;

encoding material within a first plurality of one or more flows, causing a second plurality of one or more flows to be generated, wherein the first plurality of one or more flows traverses a first path of the internetwork, and the second plurality of one or more flows traverses a second path of the internetwork, wherein at least a portion of the first path of the internetwork and at least a portion of the second path of the internetwork are equal, and measuring a subset of the second plurality of one or more flows;

calculating at least one performance metric for the subset of flows in the at least a portion of the internetwork, the at least one performance metric at least partly determined from the measured performance characteristics, the at least one performance metric computed according to an exponentially moving average; and

in response to calculating the at least one performance metric, rearchitecting the internetwork to optimize one or more of the least one performance metric wherein the at least one performance metric is at least one of;

an average delay d computed according to;

d=u*d+(1−

u)*m

where d is the exponentially moving average of delay, m is tile last delay sample, and, u is the weight of the moving average;

an average jitter v computed according to;

v=u*v+(1−

u)*ld−

m l

where v is the exponentially moving average of jitter, ld−

m] is the last sample of jitter, and, u is the weight of the average;

an average jitter v computed according to;

v=u*v+(1−

u)*lm−

m ′

l

where v is the exponentially moving average of jiuer, lm−

m ′

l is the last sample of jitter, m is the last delay sample, m ′

is the previous delay sample, and /1 is the weight of the average;

an average loss p-hat computed according to;

p-hat=u*p-hat+(1−

u)*p

where p-hat is the moving average of the loss, p={0 if packet is received, l is the packet is declared lost}, and, u is the weight of the exponentially moving average.

2. The method of claim 1, wherein rearchitecting the internetwork comprises altering one or more routing tables in the internetwork wherein the plurality of one or more routing tables includes network-layer routing tables, layer 3 routing tables IP routing tables, layer 2 routing tables, or MPLS forwarding tables.

3. The method of claim 1, wherein the performance characteristics include the plurality of one or more round trip measurements.

4. The method of claim 1, wherein the performance characteristics include the plurality of one or more one-way measurements.

5. The method of claim 1, wherein the at least one performance metric to be optimized quantifies path performance of the subset of flows.

6. The method of claim 5, wherein the at least one performance metric characterizes a quality of a network application.

7. The method of claim 6, wherein the application includes http, ftp, telnet, voice, or video.

8. The method of claim 1, wherein one or more of the at least one performance metric quantifies one or more of:

overall usage of the at least the portion of the internetwork, absolute individual network link usage in the at least the portion of the internetwork, relative individual network link usage in the at least the portion of the internetwork, and link usage cost in the at least the portion of the internetwork.

9. The method of claim 1, wherein the subset of flows include at least a first sub-plurality of one or more flows and a second sub-plurality of one or more flows, and the first sub-plurality of one or more flows uses at least a first measured performance characteristic, and the second sub-plurality of one or more flows uses at least a second measured performance characteristic.

10. The method of claim 1, wherein the one or more of the at least one performance metric quantifies geographic distance covered by the subset of flows in the internetwork.

11. The method of claim 1, wherein the selection of the subset of flows is user-based in the at least the portion of the internetwork.

12. The method of claim 1, wherein the internetwork comprises an autonomous sub-system of a larger network.

13. The method of claim 12, wherein the larger network is the Internet.

14. The method of claim 12, wherein the internetwork is a Border Gateway Protocol autonomous system.

15. The method of claim 1, wherein the internetwork comprises an autonomous system of a larger network.

16. The method of claim 15, wherein the larger network is the Internet.

17. The method of claim 15, wherein the internetwork is a Border Gateway Protocol autonomous system.

18. The method of claim 1, wherein the internetwork comprises an overlay network.

19. The method of claim 1, wherein measuring performance characteristics includes launching a first plurality of one or more packets, and measuring the first plurality of one or more packets.

20. The method of claim 19, wherein the measuring performance characteristics includes launching a first plurality of one or more round-trip packets, and measuring the first plurality of one or more round-trip packets, such that the plurality of one or more round trip measurements include round trip measurements for the launched packets.

21. The method of claim 20, wherein the first plurality of one or more round-trip packets include traceroute ICMP packets, ICMP packets, telnet packets, TCP packets from an empty TCP transaction or http packets.

22. The method of claim 19, wherein the measuring performance characteristics includes launching a first plurality of one or more one-way packets, and measuring the first plurality of one or more one-way packets, such that the plurality of one or more one-way measurements include one-way measurements for the launched packets.

24. The method of claim 1, wherein round-trip measurements include one or more of round-trip delay, round-trip jitter, round-trip loss, round-trip available bandwidth, and round-trip total bandwidth.

25. The method of claim 1, wherein one-way measurements include one or more of one-way delay, one-way jitter, one-way loss, one-way available bandwidth, and one-way total bandwidth.

26. The method of claim 1, wherein rearchitecting the internetwork includes altering a plurality of one or more routing tables in the internetwork.

27. The method of claim 26, wherein the altering of the plurality of one or more routing tables is applied automatically.

28. The method of claim 26, wherein the altering of the plurality of one or more routing tables includes configuring a plurality of one or more routers, wherein the configuring the plurality of one or more routers statically alter the routing of flows.

29. The method of claim 28, wherein the configuring a plurality of one or more routers includes route maps or static route statements.

30. The method of claim 26, wherein the altering of the plurality of one or more routing tables includes configuring a plurality of one or more routers, wherein the configuring the plurality of one or more routers adjust the processing of dynamic routing updates.

31. The method of claim 26, wherein the altering of the plurality of one or more routing tables is performed at least partly by a plurality of one or more dynamic routing protocols.

32. The method of claim 31, wherein the plurality of one or more dynamic routing protocols includes Border Gateway Protocol, a plurality of one or more Interior Gateway Protocol routing protocols, or OSPF.

33. The method of claim 26, wherein the altering of the plurality of one or more routing tables are applied manually by a user.

34. The method of claim 1, wherein the rearchitecting of the internetwork includes redirecting the subset of flows to a second internetwork coupled to the internetwork at one or more Points of Presence.

35. The method of claim 34, wherein the redirecting of the subset of flows is at least partly across an exit point traversed by at least a portion of the subset of flows from the internetwork, wherein the at least one performance metric is optimized.

36. The method of claim 1, wherein the optimizing of the at least one performance metric includes:

calculating at least one performance metric for a plurality of one of more paths in the at least the portion of the internetwork; and

at least partly responsive to the calculating of the at least one performance metric, selecting a path in the at least the portion of the internetwork from the plurality of one or more paths.

37. The method of claim 36, wherein the selected path is a direct path.

38. The method of claim 36, wherein the selected path is an indirect path.

39. The method of claim 1, wherein the measuring performance characteristics includes monitoring a first plurality of one or more flows in the internetwork, duplicating one or more packets from the plurality of one or more flows, and measuring the one or more duplicated packets.

40. The method of claim 1, wherein the measuring performance characteristics includes serving as a proxy hop for a second plurality of one or more flows, and measuring the second plurality of one or more flows.

46. The method of claim 1, wherein the subset of flows is selected based on a rate of incoming requests.

47. The method of claim 1, wherein the subset of flows is selected based on applying thresholds to statistics related to the flows.

23. The method of 1, wherein the measuring performance characteristics includes measuring a second plurality of one or more packets in the internetwork, wherein the second plurality of one or more packets were already launched.

41. A method of optimizing traffic in an internetwork, the method comprising:

Selecting, by one or more network devices, a subset of flows in the internetwork for monitoring, wherein the subset of flows includes one of one flow, some flows, and all flows;

measuring performance characteristics of the subset of flows in at least a portion of the internetwork, the performance characteristics including a plurality of one or more round trip measurements for each of the subset of flows and a plurality of one or more one-way measurements for each of the subsets of flows, the measuring performance characteristics including;

encoding material within a first plurality of one or more flows, causing a second plurality of one or more flows to be generated, wherein the first plurality of one or more flows traverses a first path of the internetwork, and the second plurality of one or more flows traverses a second path of the internetwork, wherein at least a portion of the first path of the internetwork and at least a portion of the second path of the internetwork are equal, and measuring a subset of the second plurality of one or more flows;

calculating at least one performance metric for the subset of flows in the at least a portion of the internetwork, the at least one performance metric at least partly determined from the measured performance characteristics, wherein the at least one performance metric is at least one of;

an average delay d computed according to;

d=u*d+(1−

u)*m

where d is the exponentially moving average of delay, m is tile last delay sample, and, u is the weight of the moving average;

an average jitter v computed according to;

v=u*v+(1−

u)*ld−

m I

where v is the exponentially moving average of jiuer, ld−

m] is the last sample of jitter, and, u is the weight of the average;

an average jitter v computed according to;

v=u*v+(1−

u)*lm−

m ′

l

where v is the exponentially moving average of jiuer, lm−

m ′

l is the last sample of jitter, m is the last delay sample, m ′

is the previous delay sample, and /1 is the weight of the average;

an average loss p-hat computed according to;

p-hat=u*p-hat+(1−

u)*p

where p-hat is the moving average of the loss, p={0 if packet is received, l is the packet is declared lost}, and, u is the weight of the exponentially moving average; and

in response to calculating the at least one performance metric, affecting the routing of the subset of flows by altering a plurality of one or more Domain Name System entries in the internetwork.

42. A network systems, comprising:

a plurality of one or more network devices configured such that, when the plurality of one or more network devices is deployed in an internetwork, the plurality of one or more network devices performs;

selecting a subset of flows in the networks for monitoring, wherein the subset of flows includes one of one flow, some flows, and all flows;

measuring performance characteristics of the subset of flows in at least a portion of the internetwork, the performance characteristics including;

a plurality of one or more round trip measurements for each of the subset of flows and a plurality of one or more one-way measurements for each of the subset of flows, the measuring performance characteristics including;

encoding material within a third first plurality of one or more flows, causing a second plurality of one or more flows to be generated, wherein the first plurality of one or more flows traverses a first path of the internetwork, and the second plurality of one or more flows traverses a second path of the internetwork, wherein at least a portion of the first path of the internetwork and at least a portion of the second path of the internetwork are equal, and measuring a subset of the second plurality of one or more flows;

calculating at least one performance metric for the subset of flows in the at least a portion of the internetwork, the at least one performance metric at least partly determined from the measured performance characteristics, wherein the at least one performance metric is at least one of;

an average delay d computed according to;

d=u*d+(1−

u)*m

where d is the exponentially moving average of delay, m is tile last delay sample, and, u is the weight of the moving average;

an average jitter v computed according to;

v=u*v+(1−

u)*ld−

m l

where v is the exponentially moving average of jitter, ld−

m] is the last sample of jitter, and, u is the weight of the average;

an average jitter v computed according to;

v=u*v+(1−

u)*lm−

m ′

l

where v is the exponentially moving average of jiuer, lm−

m ′

l is the last sample of jitter, m is the last delay sample, m ′

is the previous delay sample, and /1 is the weight of the average;

an average loss p-hat computed according to;

p=hat=u*p-hat+(1−

u)*p

where p-hat is the moving average of the loss, p={0 if packet is received, l is the packet is declared lost}, and, u is the weight of the exponentially moving average;

and in response to calculating the at least one performance metric, rearchitecting the internetwork to optimize one or more of the at least one performance metric.

43. The network system of claim 42, where the rearchitecting of the internetwork is performed within the plurality of one or more network devices.

44. A network systems, comprising:

a plurality of one or more network devices configured such that, when the plurality of one more network devices is deployed in an internetwork, the plurality of one or more network devices performs;

selecting a subset of flows in the internetwork for monitoring, wherein the subset of flows includes one or one flow, some flows, and all flows;

measuring performance characteristics of the subset of flows in at least a portion of the internetwork, the performance characteristics including;

a plurality of one or more round trip measurements for each of the subset of flows and a plurality of one or more one-way measurements for each of the subset of flows, the measuring performance characteristics including;

encoding material within a first plurality of one or more flows, causing a second plurality of one or more flows to be generated, wherein the first plurality of one or more flows traverses a first path of the internetwork, and the second plurality of one or more flows traverses a second path of the internetwork, wherein at least a portion of the second path of the internetwork and at least a portion of the second path of the internetwork are equal, and measuring a subset of the second plurality of one or more flows;

calculating at least one performance metric for the subset of flows in the at least a portion of the internetwork, the at least one performance metric at least partly determined from the measured performance characteristics, wherein the at least one performance metric is at least one of;

an average delay d computed according to;

d=u*d+(1−

u)*m

where d is the exponentially moving average of delay, m is tile last delay sample, and, u is the weight of the moving average;

an average jitter v computed according to;

v=u*v+(1−

u)*ld−

m l

where v is the exponentially moving average of jitter, ld−

m] is the last sample of jitter, and, u is the weight of the average;

an average jitter v computed according to;

v=u*v+(1−

u)*lm−

m ′

l

where v is the exponentially moving average of jiuer, lm−

m ′

l is the last sample of utter, m is the last delay sample, m ′

is the previous delay sample, and /1 is the weight of the average;

an average loss p-hat computed according to;

p-hat=u*p-hat+(1−

u)*p where p-hat is the moving average of the loss, p={0 if packet is received, l is the packet is declared lost}, and, u is the weight of the exponentially moving average and in response to calculating the at least one performance metric, affecting the routing of the subset of flows by altering a plurality of one or more Domain Name System entries in the internetwork

45. The network system of claim 44, where the affecting the routing of the subset of flows is performed within the one or more network devices.