Apparatus and methods for co-location and offloading of web site traffic based on traffic pattern recognition

• US 20040111508A1
• Filed: 12/10/2002
• Published: 06/10/2004
• Est. Priority Date: 12/10/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, International Business Machines SA (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Liu, Zhen, Zhang, Li, King, Richard Pervin, Dias, Daniel Manuel, Squillante, Mark Steven, Yu, Shun-Zheng
• Granted Patent: US 7,386,611 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Apparatus and methods for identifying traffic patterns to web sites based on templates that characterize the arrival of traffic to the web sites are provided. Based on these templates, determinations are made as to which web sites should be co-located so as to optimize resource allocation. Specifically, web sites whose templates are complimentary, i.e. a first web site having a peak in arrival traffic at time t1 and a second web site that has a trough in arrival traffic at time t1, are designated as being candidates for co-location. In addition, the present invention uses the templates identified for the traffic patterns of web sites to determine thresholds for offloading traffic to other servers. These thresholds include a first threshold at which offloading should be performed, a second threshold that takes into consideration the lead time needed to begin offloading, and a third threshold that takes into consideration a lag time needed to stop all offloading of traffic to the other servers.

Claims

1. A computer program product in a computer readable medium for allocating resources to a plurality of web sites, comprising:

first instructions for identifying a traffic pattern for each web site in the plurality of web sites;

second instructions for identifying a template for each web site in the plurality of web sites based on the traffic pattern; and

third instructions for allocating resources to web sites in the plurality of web sites based on the identified templates for each web site in the plurality of web sites.

2. The computer program product of claim 1, wherein the third instructions for allocating resources to web sites include:

instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites; and

instructions for allocating resources to the two or more web sites based on the identification of the two or more web sites being candidates for co-location.

3. The computer program product of claim 1, wherein the third instructions for allocating resources to web sites include:

instructions for calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

instructions for calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

instructions for calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

4. The computer program product of claim 2, wherein the third instructions for allocating resources to web sites includes:

instructions for calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

instructions for calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

instructions for calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

5. The computer program product of claim 3, further comprising:

fourth instructions for monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic exceeds the second threshold; and

fifth instructions for offloading at least a portion of the traffic to another web server if the traffic of the web site exceeds the second threshold.

6. The computer program product of claim 5, further comprising:

sixth instructions for monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic falls below the third threshold; and

seventh instructions for disabling the offloading of traffic to the another web server if the traffic of the web site falls below the third threshold.

7. The computer program product of claim 2, wherein the instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites include:

instructions for identifying a first web site having peaks in traffic at a first set of time periods; and

instructions for identifying a second web site having peaks in traffic at a second set of time periods different from the first set of time periods.

8. The computer program product of claim 7, wherein the second web site has a trough in traffic at approximately a same time as the first web site has a peak in traffic.

9. The computer program product of claim 2, wherein the instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites include:

instructions for identifying the two or more web sites such that a capacity for traffic of a web server on which the two or more web sites are located remains constant.

10. The computer program product of claim 2, wherein the instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites include:

instructions for identifying the two or more web sites such that a the total cost of all web servers hosting the plurality of web sites is minimized.

11. The computer program product of claim 2, wherein the instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites include:

instructions for formulating an integer programming problem having decision variables that are an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is an increasing function of minimum distances between server capacity and peak load at different ones of the plurality of web servers.

12. The computer program product of claim 2, wherein the instructions for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites include:

instructions for formulating an integer programming problem having decision variables that are an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is a sum of costs of all web servers to which at least one web site is assigned.

13. A method of allocating resources to a plurality of web sites, comprising:

identifying a traffic pattern for each web site in the plurality of web sites;

identifying a template for each web site in the plurality of web sites based on the traffic pattern; and

allocating resources to web sites in the plurality of web sites based on the identified templates for each web site in the plurality of web sites.

14. The method of claim 13, wherein allocating resources to web sites includes:

identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites; and

allocating resources to the two or more web sites based on the identification of the two or more web sites being candidates for co-location.

15. The method of claim 13, wherein allocating resources to web sites includes:

calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

16. The method of claim 14, wherein allocating resources to web sites includes:

calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

17. The method of claim 15, further comprising:

monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic exceeds the second threshold; and

offloading at least a portion of the traffic to another web server if the traffic of the web site exceeds the second threshold.

18. The method of claim 17, further comprising:

monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic falls below the third threshold; and

disabling the offloading of traffic to the another web server if the traffic of the web site falls below the third threshold.

19. The method of claim 14, wherein identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

identifying a first web site having peaks in traffic at a first set of time periods; and

identifying a second web site having peaks in traffic at a second set of time periods different from the first set of time periods.

20. The method of claim 19, wherein the second web site has a trough in traffic at approximately a same time as the first web site has a peak in traffic.

21. The method of claim 14, wherein identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

identifying the two or more web sites such that a capacity for traffic of a web server on which the two or more web sites are located remains constant.

22. The method of claim 14, wherein identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

identifying the two or more web sites such that a the total cost of all web servers hosting the plurality of web sites is minimized.

23. The method of claim 14, wherein identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

formulating an integer programming problem having decision variables that arc an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is an increasing function of minimum distances between server capacity and peak load at different ones of the plurality of web servers.

24. The method of claim 14, wherein identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

formulating an integer programming problem having decision variables that are an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is a sum of costs of all web servers to which at least one web site is assigned.

25. An apparatus for allocating resources to a plurality of web sites, comprising:

means for identifying a traffic pattern for each web site in the plurality of web sites;

means for identifying a template for each web site in the plurality of web sites based on the traffic pattern; and

means for allocating resources to web sites in the plurality of web sites based on the identified templates for each web site in the plurality of web sites.

26. The apparatus of claim 25, wherein the means for allocating resources to web sites includes:

means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites; and

means for allocating resources to the two or more web sites based on the identification of the two or more web sites being candidates for co-location.

27. The apparatus of claim 25, wherein the means for allocating resources to web sites includes:

means for calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

means for calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

means for calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

28. The apparatus of claim 26, wherein the means for allocating resources to web sites includes:

means for calculating, for each web site in the plurality of web sites, a first threshold based on the template for the web site;

means for calculating a second threshold based on the first threshold, wherein offloading of traffic is enabled when a traffic intensity for the web site meets or exceeds the second threshold; and

means for calculating a third threshold based on the first threshold, wherein offloading of traffic is disabled when a traffic intensity of the web site meets or falls below the third threshold.

29. The apparatus of claim 27, further comprising:

means for monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic exceeds the second threshold; and

means for offloading at least a portion of the traffic to another web server if the traffic of the web site exceeds the second threshold.

30. The apparatus of claim 29, further comprising:

means for monitoring traffic of a web site of the plurality of web sites, on a web server to determine if the traffic falls below the third threshold; and

means for disabling the offloading of traffic to the another web server if the traffic of the web site falls below the third threshold.

31. The apparatus of claim 26, wherein the means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

means for identifying a first web site having peaks in traffic at a first set of time periods; and

means for identifying a second web site having peaks in traffic at a second set of time periods different from the first set of time periods.

32. The apparatus of claim 31, wherein the second web site has a trough in traffic at approximately a same time as the first web site has a peak in traffic.

33. The apparatus of claim 26, wherein the means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

means for identifying the two or more web sites such that a capacity for traffic of a web server on which the two or more web sites are located remains constant.

34. The apparatus of claim 26, wherein the means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

means for identifying the two or more web sites such that a the total cost of all web servers hosting the plurality of web sites is minimized.

35. The apparatus of claim 26, wherein the means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

means for formulating an integer programming problem having decision variables that are an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is an increasing function of minimum distances between server capacity and peak load at different ones of the plurality of web servers.

36. The apparatus of claim 26, wherein the means for identifying two or more web sites from the plurality of web sites that are candidates for co-location based on the templates for the two or more web sites includes:

means for formulating an integer programming problem having decision variables that are an assignment of the plurality of web sites to a plurality of web servers, a constraint that is a capacity limitation for any server at any time epoch, and an objective function that is a sum of costs of all web servers to which at least one web site is assigned.

37. A method for deploying computing infrastructure, comprising integrating computer readable code into a computing system, wherein the code in combination with the computing system is capable of performing the following:

identifying a traffic pattern for each web site in the plurality of web sites;

identifying a template for each web site in the plurality of web sites based on the traffic pattern; and

allocating resources to web sites in the plurality of web sites based on the identified templates for each web site in the plurality of web sites.