System and method for integrated load distribution and resource management on internet environment

• US 6,463,454 B1
• Filed: 06/17/1999
• Issued: 10/08/2002
• Est. Priority Date: 06/17/1999
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lumelsky, Leon L., Manohar, Nelson R.
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/335,272
• Time in Patent Office: 1,209 Days
• Field of Search: 709/105, 709/104, 709/102, 709/226, 709/221, 709/224, 709/223
• US Class Current: 718/105
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/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/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system providing access to web objects that matches predicted demand for web objects to available capacity on web servers. The system implements methods to dynamically shape both demand and capacity based on certain criteria. The system provides methods to dynamically shape demand for an object based on criteria such as arrival time, incoming geography, and costs requirements. In particular, the present invention characterizes future demand for an object based on aggregation and forecasting of past demand for such object. The system effectively permits control and customization of capacity across one or more media servers based on characteristics associated with the demand across one or more of them, and particularly, based on the dominating geographical traits of past demand. Moreover, the system dynamically shapes capacity by: (a) controlling the number of replicas associated with an object; and, (b) controlling the placement of these replicas across servers in a distributed network. In particular, the system drives capacity shaping measures over a particular object based on its predicted demand. Consequently, the number and location of replicas associated with an object is made to be variable over time and driven by predicted demand for a web object.

Claims

1. A request management system for placing requests for multi-media objects from independent clients onto servers distributed throughout a network having said objects, each server having a capacity for storing multi-media objects and, a streaming resource for delivering requested multi-media objects to clients, the system comprising:

intermediary control means for receiving placement inquires for said multi-media objects from said clients, a requested object having a unique identifier associated therewith;

first directory service means comprising a mapping of object identifiers to locations of associated object replicas at said servers, said first directory means for locating object replicas associated with the given object identifier;

second directory service means for mapping available distributed servers with an indicator indicating degree of willingness of a respective server to receive placement inquiries and, determining a willingness of any such server to consider said placement inquiries for said object replicas; and

,

means for generating one or more placement inquiries to a willing server according to a predetermined policy, said intermediary control means forwarding a placement inquiry to said willing server.

2. The system according to claim 1, wherein said willingness indicator of said directory service represents a degree of server aggressiveness for functioning in said distributed network, said indicator being used to drive aggressiveness of said servers.

3. The system according to claim 1, wherein a server in said distributed network includes a server cluster comprising one or more server devices addressable as a single entity.

4. The system according to claim 1, wherein said second directory service enables mapping of distributed servers with an available capacity rating indicator for indicating amount of resources available at said server.

5. The system according to claim 4, wherein said control means implements a placement policy for generating one or more tentative placements of requests to servers, said control means accessing said first and second directory services for determining said tentative placements.

6. The system according to claim 5, wherein said predetermined policy includes a negotiation policy, said control means further choosing one or more tentative placements and negotiating with each associated server to enable placement of a particular request to that server based upon a predetermined criteria.

7. The system according to claim 6, wherein said predetermined criteria includes one or more selected from a group comprising:

resolution of a streaming object, cost, quality of a streaming object, distance between a client and server, and maximum delay for receiving a streaming object.

8. The system according to claim 7, wherein each said server applies its own admission control for admitting or denying placement requests, and communicating an admission or denial of a placement request to said intermediary controller.

9. The system according to claim 6, wherein said control means further implements an exploration policy for iteratively determining multiple placement opportunities across one or more servers.

10. The system according to claim 6, wherein said control means further includes means for monitoring a number of received requests and aggregating said requests into groups of requests based on one or more predetermined characteristics.

11. The system according to claim 10, wherein demand requests for objects received during a bounded time interval are aggregated.

12. The system according to claim 11, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes geographic proximity of clients requesting the same object identifier.

13. The system according to claim 11, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes commonality of requested streaming constraints including resolution and quality for the same object identifier.

14. The system according to claim 12, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes temporal proximity in arrival time of requests for the same object identifier.

15. The system according to claim 14, wherein said controller means further includes means for batching a group of similar requests to a server with multicast capability, said server providing multicast services for clients.

16. The system according to claim 14, wherein said control means further includes means for autonomously upgrading or downgrading a particular request in order to achieve aggregation.

17. The system according to claim 16, wherein said means for upgrading or downgrading a particular object request includes decreasing or increasing, respectively, said sensitivity of geographical proximity grouping criteria.

18. The system according to claim 16, wherein said means for upgrading or downgrading a particular object request includes increasing or decreasing, respectively, quality of the requested object.

19. The system according to claim 16, wherein said means for upgrading or downgrading a particular object request includes changing sensitivity of temporal proximity grouping criteria.

20. The system according to claim 10, wherein each said server reports its available system capacity to said controller means.

21. The system according to claim 10, wherein said control means further includes means for generating object replicas and dynamically controlling placement of object replicas on servers according to current demand requests for said objects.

22. The system according to claim 21, further including means for forecasting future demand for object requests based on past demand for said object, said placement of object replicas being based on forecasted demand.

23. A method for shaping demand for multi-media objects stored at one or more servers distributed throughout a network, each server device having a capacity for storing multi-media objects and, a streaming resource for delivering requested multi-media objects to clients, the method comprising:

receiving requests for said multi-media objects from independent clients, each requested object having a unique identifier associated therewith;

maintaining a mapping of object identifiers to locations of associated object replicas at said servers and utilizing said mapping to locate object replicas associated with the requested object identifier;

maintaining a mapping of available distributed servers with an indicator indicating degree of willingness of a respective server to receive placement inquiries, and utilizing said mapping to determine a willingness of any such server to consider a placement inquiry associated with said request for said object replicas; and

,

generating one or more placement inquiries for said object to a willing server according to a predetermined policy, and forwarding a placement inquiry to said willing server.

24. The method according to claim 23, wherein the step of determining the willingness of servers includes implementing a directory service for mapping distributed servers with an available capacity rating indicator for indicating amount of resources available at said server.

25. The method as claimed in claim 23, further comprising the step of maintaining demand statistics associated with each distributed object, said demand statistic including a characterization of demand density, demand volume and including a geographic indicator for indicating dominating area of demand.

26. The method according to claim 25, further including the step of generating one or more tentative placements of requests to servers based on locations of said object identifiers and a capacity rating for said servers.

27. The method according to claim 26, wherein said predetermined policy includes a negotiation policy, said generating step including choosing one or more tentative placements and negotiating with each associated server to enable placement of a particular request to that server based upon a predetermined criteria.

28. The method according to claim 27, wherein said predetermined criteria includes one or more selected from a group comprising:

resolution of a streaming object, cost, quality of a streaming object, distance between a client and server, and maximum delay for receiving a streaming object.

29. The method according to claim 27, wherein each said server applies its own admission control for admitting or denying placement requests, and communicating an admission or denial of a placement request to said intermediary controller.

30. The method according to claim 27, further implementing an exploration policy for iteratively determining multiple placement opportunities across one or more servers.

31. The method according to claim 27, further including the step of monitoring a number of received requests and aggregating said requests into groups of requests based on one or more predetermined characteristics.

32. The method according to claim 31, wherein demand requests for objects received during a bounded time interval are aggregated.

33. The method according to claim 31, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes geographic proximity of clients requesting the same object identifier.

34. The method according to claim 31, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes commonality of requested streaming constraints including resolution and quality for the same object identifier.

35. The method according to claim 31, wherein a predetermined criteria for aggregating demand requests during a bounded time interval includes temporal proximity in the arrival time of requests for the same object identifier.

36. The method according to claim 31, further including the step of autonomously upgrading or downgrading a particular request in order to achieve aggregation.

37. Integrated system for real-time management of multimedia object resources in an Internet environment having servers for storing and providing streaming of multimedia objects to clients, the system comprising:

means for monitoring demand for object resources and for predicting future demand for objects based on demand statistics and geographical location of said demand;

means for ascertaining current willingness of server devices to store and allocate resources for streaming object resources in said Internet environment;

means for shaping capacity of object resources in said Internet environment based on said demand statistics, said current available capacity and said geographical proximity of servers to demand locations, said capacity shaping means including means for replicating objects associated with said objects resources and temporarily placing said object replicas at one or more server devices having available capacity at predicted geographical demand locations;

means for placing received request inputs for an object resource from a client and, generating and forwarding placement inquiries related to one or more received requests to a server device having said requested object resource at said geographical location; and

,

means for negotiating with a server device to enable placement of a particular request to that server device based upon predetermined criteria associated with streaming of said object resource from said server device to said client.

38. The integrated system as claimed in claim 37, wherein said means for shaping capacity includes means for evaluating a number and geographical placement of object replicas based on characteristics associated with said demand.

39. The integrated system as claimed in claim 37, wherein said means for placing received request inputs includes means for querying, according to some policy, willing and capable servers for admission of one or more requests.

40. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a demand for multi-media objects stored at one or more servers distributed throughout a network, each server device having a capacity for storing multi-media objects and a streaming resource for delivering requested multi-media objects to clients, said method steps comprising:

receiving requests for said multi-media objects from independent clients, each requested object having a unique identifier associated therewith;

maintaining a mapping of object identifiers to locations of associated object replicas at said servers and utilizing said mapping to locate object replicas associated with the requested object identifier;

maintaining a mapping of available distributed servers with an indicator indicating degree of willingness of a respective server to receive placement inquiries, and utilizing said mapping to determine a willingness of any such server to consider a placement inquiry associated with said request for said object replicas; and

,

generating one or more placement inquiries for said object to a willing server according to a predetermined policy, and forwarding a placement inquiry to said willing server.

41. The program storage device readable by a machine according to claim 40, wherein said step of determining the willingness of servers further includes implementing a directory service for mapping distributed servers with an available capacity rating indicator for indicating amount of resources available at said server.

42. The program storage device readable by a machine according to claim 40, further comprising the step of maintaining demand statistics associated with each distributed object, said demand statistic including a characterization of demand density, demand volume and including a geographic indicator for indicating dominating area of demand.

43. The program storage device readable by a machine according to claim 40, further including the step of generating one or more tentative placements of requests to servers based on locations of said object identifiers and a capacity rating for said servers.

44. The program storage device readable by a machine according to claim 43, wherein said predetermined policy includes a negotiation policy, said generating step including choosing one or more tentative placements and negotiating with each associated server to enable placement of a particular request to that server based upon a predetermined criteria.