Method for computing aggregate traffic between adjacent points of presence in an internet protocol backbone network

• US 7,519,705 B1
• Filed: 07/10/2003
• Issued: 04/14/2009
• Est. Priority Date: 07/10/2003
• Status: Active Grant

• Current Assignee: T-Mobile Innovations LLC (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Diot, Christophe, Papagiannaki, Konstantina, Taft, Nina
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): SALL, EL HADJI MALICK
• Application Number:
  US10/616,795
• Time in Patent Office: 2,105 Days
• Field of Search: 703/223, 703/224, 709/200, 709/223, 709/224, 709/232, 709/241
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity

Abstract

The present invention provides a method for computing traffic between a pair of Points of Presence in an IP network by summing link utilization values measured for each link connecting a pair of Points of Presence and dividing the sum by the number of link utilization values included in the sum. The resulting average link utilization is the average link utilization of any link in the aggregate and may be multiplied by the number of active links connecting a pair of Points of Presence to reflect the total amount of traffic between the two Points of Presence. Future link utilization may be forecast by modeling the observed traffic between a pair of Points of Presence using wavelet multiresolution analysis to create an approximation curve that captures the long-term trend of link utilization and at least one detail curve that captures the short term deviation of link utilization around the long-term trend. A time series model of the approximation curve may then be constructed and used for forecasting. In a similar fashion, deviation of link utilization may be forecast.

Claims

1. A method for determining link utilization in an IP network, the method comprising:

collecting utilization values for links in the IP network over a predetermined polling period;

collecting topological information for links in the IP network, the topological information identifying each link connecting each adjacent Point of Presence;

correlating the link utilization values with the topological information;

summing the link utilization values for all links connecting a pair of Points of Presence over a predetermined measurement period;

dividing the sum by the number of link utilization values included in the sum to give an average link utilization; and

multiplying the average link utilization by the number of links connecting the pair of Points of Presence to calculate a measure of total traffic flowing between the pair of Points of Presence that is insignificantly effected by one or more missing utilization values.

2. The method for determining link utilization of claim 1, further comprising:

calculating aggregate link demand.

3. The method for determining link utilization of claim 2, wherein calculating aggregate link demand comprises:

identifying the Point of Presence pairs connected by each link using the topological information;

summing the utilization values collected for each of the links connecting a Point of Presence pair over a predetermined time period; and

dividing the sum of link utilization values for each Point of Presence pair by the number of utilization values included in the sum.

4. The method for determining link utilization of claim 3, wherein the predetermined time period is at least twice as long as the predetermined polling period.

5. A method for determining link utilization in an IP network, the method comprising:

collecting link utilization values from routers in the IP network over a predetermined polling period;

collecting topological information from routers in the IP network;

correlating link utilization values with the topological information by identifying the Points of Presence pairs connected by each link for which a link utilization value was collected;

summing the link utilization values for each link connecting a pair of Points of Presence;

dividing the sum of link utilization values for the pair of Points of Presence by the number of link utilization values included in the sum to give an average link utilization; and

multiplying the average link utilization by the number of links connecting the two Points of Presence to calculate a measure of total traffic flowing between the two Points of Presence that is insignificantly effected by one or more missing utilization values.

6. The method for determining link utilization of claim 5, wherein collecting incoming and outgoing link utilization values from routers in the IP network further comprises each router transmitting SNMP messages using UDP transport protocol.

7. The method for determining link utilization of claim 6, wherein collecting link utilization values from routers in the IP network comprises:

receiving an exponentially weighted moving average of link utilization measurements for a first short time frame; and

averaging the received moving average link utilization measurements over a second longer time frame.

8. The method for determining link utilization of claim 6, wherein collecting link utilization values from routers in the IP network comprises:

receiving the total number of bytes transmitted over a link for a first short time frame; and

averaging the received total number of bytes over a second longer time frame.

9. The method for determining link utilization of claim 6, wherein collecting link utilization values from routers in the IP network comprises:

receiving the total number of bytes received over a link for a first short time frame; and

averaging the received total number of bytes over a second longer time frame.

10. The method for determining link utilization of claim 6, wherein collecting link utilization values from routers in the IP network comprises:

receiving the total number of bytes transmitted and received for a link over a first short time frame; and

averaging the received total number of bytes for a second longer time frame.

11. The method for determining link utilization of claim 6, wherein downloading configuration information comprises downloading the name of each router, the Point of Presence containing each router, all active links connected to each router, and the destination of each active link connected to each router.

12. The method for determining link utilization of claim 11, wherein collecting topological information from routers comprises downloading configuration information at predetermined time intervals.

13. The method for determining link utilization of claim 12, wherein the predetermined time intervals at which configuration information is downloaded comprises one week.

14. The method for determining link utilization of claim 13, wherein collecting incoming and outgoing link utilization values from the routers in the IP network comprises collecting incoming and outgoing link utilization values from all routers in the IP network.

15. The method for determining link utilization of claim 14, wherein collecting topological information from routers in the IP network comprises collecting topological information from all routers in the IP network.

16. A method for determining aggregate link utilization between two Points of Presence, wherein a plurality of links connects the two Points of Presence, the method comprising:

collecting link utilization values for one or more links connecting the two Points of Presence over a predetermined polling period, wherein at least one link connecting the two Points of Presence corresponds with one or more missing utilization values over the predetermined polling period;

summing the link utilization values for all links connecting the two Points of Presence over a predetermined measurement period;

dividing the sum by the number of link utilization values included in the sum to give an average link utilization; and

multiplying the average link utilization by the number of links connecting the two Points of Presence to calculate a measure of total traffic flowing between the two Points of Presence that is insignificantly effected by the one or more missing utilization values.

17. The method for determining aggregate link utilization between two Points of Presence of claim 16, wherein collecting link utilization data for each link connecting the two Points of Presence comprises:

each router in the two Points of Presence providing incoming and outgoing link utilization information, the incoming and outgoing link utilization information being an average over a short period of time; and

averaging the incoming and outgoing link utilization information over a longer period of time.

18. The method of determining aggregate link utilization between two Points of Presence of claim 17, wherein the incoming and outgoing link utilization information further comprises an exponentially weighted moving average.

19. The method for determining aggregate link utilization between two Points of Presence of claim 18, wherein the longer period of time over which the incoming and outgoing link utilization information is averaged comprises ninety minutes.

20. At least one machine readable media for causing at least one network management station in an IP network to perform a method for determining link utilization in an IP network, the method comprising:

collecting incoming and outgoing link utilization values from routers over a predetermined polling period;

correlating the link utilization values with the topological information;

summing the link utilization values collected over a first predetermined time period for links connecting a pair of Points of Presence, wherein at least one link connecting the pair of Points of Presence has one or more missing utilization values;

dividing the sum by the number of link utilization values included in the sum to give an average link utilization;

calculating a measure of total traffic flowing between the pair of Points of Presence by multiplying the average link utilization by the number of links connecting the pair of Points of Presence to compensate for the one or more missing utilization values of the at least one link connecting the pair of Points of Presence; and

collecting topological information from the routers at one or more second predetermined time intervals, the topological information identifying each link connecting the pair of Points of Presence.

21. The at least one machine readable media of claim 20, wherein the first predetermined time period is at least twice as long as the polling period.

22. The at least one machine readable media of claim 21, wherein the polling period comprises five minutes.

23. The at least one machine readable media of claim 22, wherein the first predetermined time period comprises ninety minutes.

24. The at least one machine readable media of claim 23, wherein the second predetermined time intervals comprise one week.