Methods and apparatus for downloading and/or distributing information and/or software resources based on expected utility

• US 7,512,940 B2
• Filed: 03/29/2001
• Issued: 03/31/2009
• Est. Priority Date: 03/29/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J.
• Primary Examiner(s): VU, TUAN A
• Application Number:
  US09/820,519
• Publication Number:
  US 20030154282A1
• Time in Patent Office: 2,924 Days
• Field of Search: 717168-178, 709/219, 711/134
• US Class Current: 717/173
• 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/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/306 User profiles
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A resource download process is provided which includes accepting and/or determining evidence about user based factors, accepting and/or determining resource based factors, and maximizing the expected value of downloading resources. A resource distribution process is provided which includes accepting and/or determining user based factors, accepting and/or determining resource based factors, accepting and/or determining intermediate storage facility based factors, and minimizing the total expected latencies between requesting and receiving resources. A process for distributing resources is provided which includes determining a change in value and a change in cost of storing resources on a first storage facility versus storing resources on a second storage facility, determining a value density based on the change in value and the change in cost, and maximizing a total value density given a total size of resources being less than the finite available capacity of the first storage facility.

Claims

1. A computer implemented method for downloading resources, from a source to one or more intermediate storage facility(ies) having a finite storage capacity, the computer implemented method comprising the following computer executable acts:

determining a probability of using a resource, the probability in part determined by;

maximizing an expected value of downloaded resources via a computation that takes input parameters, wherein the input parameters include at least one user-based factor and at least one resource-based factor;

evaluating a cost of accessing resources in a source in a non-downloaded condition; and

comparing said cost with a cost of accessing resources for the at least one of the intermediate storage facilities in an downloaded condition; and

distributing resources downloaded from the source based on the determining step among a plurality of storage media associated with the intermediate storage facilities to minimize total request-to-receive time.

2. The computer implemented method of claim 1 further comprising determining probabilities that a user belongs to various user type classes.

3. The computer implemented method of claim 2 wherein the probabilities that a user belongs to various user type classes are determined based on evidence using a Bayesian network.

4. The computer implemented method of claim 2 wherein the at least one resource-based factor includes probabilities that users of the various user type classes will use the resource at least once.

5. The computer implemented method of claim 2, wherein the at least one resource-based factor is a probability that the resource will be used at least once and is based on a sum, over all user type classes, of a product of:

a probability that the resource is used at least once, given that an application to which the resource belongs is used at least once, by a user of the user type class;

a probability that the application to which the resource belongs is used at least once by a user of the user type class; and

a probability that the user belongs to the user type class.

6. The computer implemented method of claim 1 wherein the at least one resource-based factor includes probabilities that users of various user type classes will use the resource at least once.

7. The computer implemented method of claim 1 wherein the at least one resource-based factor includes an association of each of the resources to at least one application class.

8. The computer implemented method of claim 7 wherein the at least one resource-based factor includes an indication, for each of the resources, of whether the resource is a core component or an optional component of the application class with which it is associated.

9. The computer implemented method of claim 1 wherein the act of maximizing an expected value of downloaded resources includes maximizing an expected value density of downloaded resources.

10. The computer implemented method of claim 1 wherein the act of maximizing an expected value of downloaded resources includes minimizing an expected cost of not having a needed resource.

11. The computer implemented method of claim 10 wherein the expected cost of not having a needed resource is based on one of enhancement rates of the resources and value densities of the resources.

12. The computer implemented method of claim 11 wherein the enhancement rate of a resource is based on the size of the resource, a probability of that resource being used at least once, and a cost of later downloading the resource.

13. The computer implemented method of claim 11 wherein the value density of a resource is based on the size of the resource and the probability that the resource will be used at least once.

14. A computer implemented system for downloading resources from a source to a plurality of storage facilities, comprising a computer for executing the following computer executable components:

means for intelligently downloading a resource to at least one of the plurality of storage facilities based on a probability of use of resources,

means for determining the probability of use of resources by maximizing an expected value of downloaded resources to at least one of the plurality of storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor and at least one resource-based factor,

means for evaluating a cost to retrieve resources in the source in a non-downloaded condition, and for evaluating a cost to retrieve resources from the source to at least one of the storage facilities in a downloaded condition based on the probability of use;

means for comparing the cost to retrieve resources in the non-downloaded condition with cost to retrieve resources in the downloaded condition; and

means for optimizing distribution among the plurality of storage facilities to minimize total request-to-receive times based on the comparing act.

15. A computer implemented method of downloading a resource from a source to a plurality of storage facilities comprising the following computer executable acts:

determining a probability of use for a resource by a user in a user type class;

wherein the determining includes;

maximizing an expected value of downloaded resources to at least one of the plurality of storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor and at least one resource-based factor,

comparing a cost to retrieve resources in the source in a non-downloaded condition with a cost to retrieve resources from the source to at least one of the plurality of storage facilities in a downloaded condition;

changing a storage capacity of at least one of the plurality of storage facilities based on a change of the expected value and the comparing act.

16. A computer implemented method for installing software components, each having a size, from a source to a plurality of storage facilities, the method comprising, the following computer executable acts:

predicting an expected frequency of use for a software component, in part via;

maximizing an expected value of downloaded resources to at least one of the plurality of storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor and at least one resource-based factor,

comparing a cost to retrieve resources in the source in a non-downloaded condition with a cost to retrieve resources from the source to at least one of the plurality of storage facilities in a downloaded condition; and

changing a storage capacity of at least one of the plurality of storage facilities and downloading resources among the plurality of storage facilities based on the predicting act.

17. The computer implemented method of claim 16 wherein the at least one user-based factor includes probabilities that a user is member of various user type classes.

18. The computer implemented method of claim 16 wherein the at least one component-based factor includes an association of each of the software components to one of a plurality of application classes.

19. The computer implemented method of claim 18 wherein the at least one component-based factor further includes an indication, for each of the software components, of whether the software component is a core component or an optional component of the application class with which it is associated.

20. The computer implemented method of claim 19 wherein the at least one component-based factor further includes probabilities that each of the software components will be used at least once by users of various user type classes.

21. A computer implemented method for distributing resources, each having a size, among at least two storage facilities, the method comprising the following computer executable acts:

determining a probability of using resources by maximizing an expected value of downloaded resources from a source to the at least two storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor, at least one resource-based factor, and at least one storage facility-based factor;

comparing a cost to retrieve resources in the source in a non-downloaded condition with a cost to retrieve resources from the source to the at least two storage facilities in a downloaded condition;

minimizing total expected request-to-receive time based on the determining act and comparing act;

changing a storage space associated with the at least two storage facilities, based on the minimizing act,

and distributing the resources among the at least two storage facilities.

22. The computer implemented method of claim 21 wherein the at least one user-based factor includes probabilities that a user belongs to various user type classes.

23. The computer implemented method of claim 22 further comprising determining the probabilities that a user belongs to various user type classes.

24. The computer implemented method of claim 23 wherein the probabilities that a user belongs to various user type classes are determined based on evidence using a Bayesian network.

25. The computer implemented method of claim 22 wherein the at least one resource-based factor includes frequencies at which users of the various user type classes will use each of the resources.

26. The computer implemented method of claim 25 wherein the at least one storage facility-based factor includes an available capacity of each of the at least two storage facilities and a relative request-to-receive latency of each of the at least two storage facilities.

27. The computer implemented method of claim 26 wherein the total expected latencies is a function of the frequencies at which users of the various user type classes will use each of the resources, and a difference between the relative request-to-receive latencies of the at least two storage facilities.

28. The computer implemented method of claim 21 wherein the at least one storage facility-based factor includes an available capacity of each of the at least two storage facilities and a relative request-to-receive latency of each of the at least two storage facilities.

29. The computer implemented method of claim 21 wherein the total expected latencies to request and receive resources is minimized based on value densities of the resources.

30. The computer implemented method of claim 29 wherein the value densities of the resources are based on the frequency of use of the resources and a difference in request to receive latencies between the at least two storage facilities.

31. A computer implemented method of distributing resources, each having a size, among at least two storage facilities, each of the storage facilities having a finite available capacity, the computer implemented method comprising the following computer executable acts:

a first determining a probability of using a resource distributed among the at least two storage facilities by a composite user;

wherein the first determining includes;

a second determining, for each resource, a change in value of storing the resource on a first storage facility versus storing the resource on a second storage facility and

a third determining, for each resource, a change in cost of storing the resource on the first storage facility versus storing the resource on the second storage facility;

a fourth determining, for each resource, a value density in a knapsack approximation procedure based on the change in value and cost as a result of the first determining act;

wherein the fourth determining includes maximizing an expected value of downloaded resources to the at least two plurality of storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor and at least one resource-based factor,

distributing the resources among the at least two storage facilities based on the fourth determining act.

32. The computer implemented method of claim 31 wherein the value of storing a resource on the first storage facility is a function of a perceived utility of such storage, per request for the resource, and a frequency of requests for the resource.

33. The computer implemented method of claim 32 wherein the perceived utility of such storage, per request for the resource, is a function of a request-to-receive time delay.

34. The computer implemented method of claim 33 wherein the request-to-receive time delay is a function of at least one of:

a storage device read access time, a network speed, a network latency, and the size of the resource.

35. The computer implemented method of claim 34 wherein the network speed is a function of a user configuration.

36. The computer implemented method of claim 32 wherein the frequency of requests for the resource is a function of a user type class and a number of users belonging to the user type class.

37. The computer implemented method of claim 31 wherein the cost of storing a resource on the first storage facility is a function of the resource size.

38. A computer implemented method of downloading a resource(s) from a source to a plurality of storage facilities comprising the following computer executable acts:

minimizing total expected latencies to request and receive resources, by;

determining a probability of using resources by maximizing an expected value of downloaded resources from the source to at least one of the storage facilities via a computation that takes input parameters, wherein the input parameters include at least one user-based factor, at least one resource-based factor, and at least one storage facility-based factor;

determining a cost of returning resources to the source in a non-downloaded condition, and comparing said cost with cost of accessing resources from the source to at least one of the storage facilities in an downloaded condition; and

distributing resources among the plurality of storage facilities based on the probability of use and the comparing act.

39. The computer implemented method of claim 38 further comprising changing a storage capacity associated with the plurality of storage facilities based on at least one of a change in value and cost.

40. The computer implemented method of claim 39 farther comprising changing the storage capacity when a ratio of value to cost is greater than one.

41. The computer implemented method of claim 40 wherein the at least one user-based factor is a function of a time offline until the one of the plurality of storage facilities is reconnected with a source.

42. The computer implemented method of claim 41 wherein the time offline is a probability distribution considering at least one of:

a resource context, a user type class, and a recent usage pattern.