Resource allocation

• US 20040010592A1
• Filed: 02/19/2003
• Published: 01/15/2004
• Est. Priority Date: 01/14/2000
• Status: Abandoned Application

• Current Assignee: Qariba Limited
• Original Assignee: Qariba Limited
• Inventors: Ferguson, David Sinclair, Kelly, Peter, Piercy, Neil Philip, Hoyle, Rebecca Bryony, Haggar, Russell Jon, Carver, Andrew Richard
• Application Number:
  US10/181,209
• Publication Number:
  US 20040010592A1
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/788 Autonomous allocation of resources
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/808 User-type aware
• CPC Class Codes: H04L 47/828 Allocation of resources per group of connections, e.g. per group of users

Abstract

A shared resource allocation system for allocating a shared resource amongst a plurality of devices operable to access or use the resource. The system includes controlling means for controlling access to or use of the resource by each of the devices and means for receiving bids from one or more of the devices. Each bid indicates a requested amount of the resource and a price offered for the requested amount. The system also includes allocation means for processing the received bids to determine an appropriate allocation of the resource, and instructing means for instructing the controlling means to control access to or use of the shared resource in accordance with the determined allocation.

Claims

1. A shared resource access or utilisation system comprising:

a shared resource;

a plurality of devices operable to access or use an amount of the shared resource;

means for obtaining from one or more of the devices an indication of one or more desired amounts of the shared resource which the device wishes to use and of how much the device is prepared to pay for the or each desired amount of the shared resource;

means for accessing or determining a current cost for accessing or using a unit amount of the shared resource;

means for determining the amount of the shared resource which the or each device may access or use in accordance with its indication and the current cost; and

means for informing the or each device of the amount of the shared resource which it may access or use.

2. A system according to claim 1, wherein the shared resource is split into a plurality of different types of sub-resource, which have different properties and/or costs per unit amount.

3. A system according to claim 1 or 2, wherein the shared resource is a resource required during the transmission of a signal over a communications network.

4. A system according to claim 1, 2 or 3, wherein the shared resource is one of:

bandwidth over a communications network between two or more users of the network;

processing power of a shared processing device connected to a communications network;

or data storage capacity within a data storage device connected to a communications network, or any combination of these three resources.

5. A system according to any preceding claim wherein each indication further includes an indication as to a quality measure of the resource associated with the or each desired amount of the resource and the amount which the device is prepared to pay for that amount.

6. A system according to claim 5 wherein the quality measure is one of:

a minimum acceptable latency or round-trip packet delay;

a minimum level of packet jitter;

a minimum assured continuous bandwidth throughput;

or another measure of network performance.

7. A system according to any preceding claim wherein each indication comprises a preference table setting out a plurality of bid options each of which includes a requested amount of the resource and an associated ceiling price.

8. A system according to claim 7 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a type of content, whereby different groups of bid options may be used for different types of content to be transmitted.

9. A system according to claim 7 or 8 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a class of user, whereby different groups of bid options may be used for different classes of user to whom or from whom data is to be transmitted or received.

10. A system according to claim 7, 8 or 9 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a type of application, whereby different groups of bid options may be used for different types of application controlling data to be transmitted over a network to which the device is attached.

11. A system according to any of claims 7 to 10 wherein the preference table includes an explicit preference order for the bid options.

12. A system according to any of claims 7 to 11 wherein the preference table comprises one or more groups of bid options, each group containing a plurality of bid options setting out a requested amount of the resource and a price offered for that amount, wherein the price offered per unit of the resource in each bid option is set to equal the difference in benefit to the device divided by the difference in the amount of the resource in going to the respective bid option from the next lowest bid option.

13. A system according to any of claims 7 to 12 wherein the preference table includes a marker for indicating that the bidding table reflects the benefit to the device of each amount of the resource included in the bid options.

14. A system according to any of claims 7 to 13 wherein the preference table includes an indication that one or more different requests for an amount of the resource are related in some way such that the benefit associated with one request being successful is dependent on the success of the or each other related request.

15. A system according to any preceding claim including a first network and a second network connected to said first network, said first network including purchasing means for purchasing an amount of a second network shared resource from the second network for onward sale to one or more of the devices as part of the shared resource requested by the or each device, the purchasing means including means for estimating the aggregated amount of demand for the shared resource at a plurality of different costs of the shared resource desired by the or each device on the basis of the indications from the or each device.

16. A system according to claim 15 wherein the purchasing means is operable to determine the desired amount of the second network shared resource to purchase on behalf of the first network on the basis of the estimated level of demand for said shared resource from the or each of said devices.

17. A system as claimed in claim 15 or 16 wherein the purchasing means is operable to review the desired amount of the second network shared resource to purchase with a frequency which is greater than once every hour but less than once every minute.

18. A system according to any preceding claim wherein the indication obtaining means comprises a bid generation means for generating and transmitting a bid to a resource allocation means, the bid including at least one requested amount of the resource and an associated price.

19. A system according to claim 18 wherein the current cost accessing or determining means comprises a resource allocation means for receiving one or more bids from one or more of the devices, for determining a current price per unit of the resource available in dependence on the received bids and for determining the amount of the resource which can be used or accessed by each device in dependence on the received bids and the current price per unit of the resource available.

20. A system according to claim 19 wherein the resource allocation means includes the informing means for informing the or each device of the amount of the resource which it can use or access.

21. A system according to any preceding claim further comprising controlling means for controlling access to or use of the resource by the or each device, and wherein the resource allocation means further comprises means for instructing the controlling means to restrict the amount of the resource which the or each device may access or use to the amount determined by the resource allocation means.

22. A system according to any of claims 19, 20 or 21, wherein the allocation means includes means for determining a first price per unit of the shared resource and means for allocating the requested amount of the shared resource in response to bids whose price offered per unit of the resource is equal to or greater than said first price.

23. A system according to claim 22, wherein the allocation means further includes means for varying the first price according to the level of demand for the shared resource as determined by the received bids so as to maintain the utilization of the resource approximately equal to a predetermined percentage of the maximum utilization of the resource possible.

24. A system according to claim 22 or 23, wherein the allocation means further includes means for determining a second price per unit of the resource and means for allocating a requested amount of the shared resource in response to a new bid if the price offered per unit of the resource is equal to or greater than said second price.

25. A system as claimed in claims 23 and 24 wherein the allocation means further includes means for varying the second price according to the level of demand as determined by the received bids, at a rate which is greater than the rate at which the first price is varied.

26. A system as claimed in claim 25 wherein the allocation means further comprises means for setting the second price to a value higher than said first price in response to the level of demand as determined by the received bids being greater than a predetermined threshold.

27. A system as claimed in claim 25 wherein the allocation means further comprises means for setting the second price to a value higher than said first price in response to a measure of the quality of the resource falling below a predetermined threshold.

28. A system as claimed in any of claims 1 to 17 wherein the indication obtaining means is formed as part of a resource management agent which also includes the current cost accessing or determining means and the informing means, each device having an associated resource management agent.

29. A system as claimed in claims 2, 5 and 28 wherein the resource management agent of an associated device is adapted to receive a notification from a current price storing means of the current price per unit amount of resource for each of said sub-resources, and to determine how much resource, and of which sub-resource or sub-resources, the device should access or use in accordance with a measurement of the quality of service associated with each sub-resource and the respective indication from the device as to the amount of the shared resource desired, at what quality and at what price.

30. A resource allocation device for allocating access to or use of a shared resource amongst a number of devices which are operable to use the resource, said resource allocation device comprising:

receiving means for receiving a plurality of bids from one or more devices adapted to access or use the shared resource, which bids indicate a requested amount of the shared resource and a price offered for the requested amount;

allocation means for determining an allocation of access to or use of the resource by the devices, which are operable to use the resource, in dependence on the bids received; and

instruction means for instructing a controlling device to control access to the shared resource in accordance with the determined allocation.

31. A resource management agent for controlling the use, by a device connected to a data network, of a resource or sub-resources required by the device to transmit or receive data over the data network, the resource management agent comprising:

means for interfacing with a set of preferences associated with the device, said set of preferences including at least one set of indications as to what amounts of the resource or sub-resources are desired by the device for given levels of quality of service associated with the resource or sub-resources and for given ceiling prices under a given set of properties of an associated flow of data to or from the device over the network;

means for interfacing with the network to determine properties of the resource or sub-resources including the associated level or levels of quality of service, and the associated cost or costs; and

processing means for determining an appropriate amount or amounts of the resource or sub-resources for the device to use for an associated flow of data in dependence upon said set of preferences and said properties of said resource or sub-resources.

32. A resource management agent as claimed in claim 31 wherein the processing means includes conversion means for generating estimated indications, on the basis of said set of preferences associated with the device, as to what amounts of the resource or sub-resources are actually desired by the device for levels of quality of service associated with the resource or sub-resources and for the cost or costs of the resource or sub-resources actually available from the network for a given flow of data to or from the device over the network, where the actually available levels of quality of service and cost differ from those included in the set of preferences.

33. A bid router device comprising:

means for receiving bids from users of a shared resource which bids indicate a requested amount of the shared resource and a price offered for the requested amount;

data storage means for storing address data of one or more allocating devices operable to allocate portions of the shared resource to bidding users together with data indicating the nature of the shared resource which is able to be allocated by the or each allocation device;

means for processing each bid using said stored data to determine whether the bid should be forwarded to an allocation device and if so to which allocation device it should be forwarded; and

forwarding means for forwarding bids to allocation devices.

34. A bidding device operable to communicate with a correspondent device over a communications network, said communications network including at least one shared resource, access to which is required by both the bidding device and the correspondent device in order for a communication between the bidding and correspondent devices to occur, said device including:

detection means for detecting the initiation of a communication between the bidding device and the correspondent device; and

bid generation means for generating a bid indicating a requested allocation of the shared resource and a price offered for the requested allocation in response to detection by the detection means of the initiation of a communication.

35. A device according to claim 34, further comprising termination detection means for detecting the termination of the communication;

and

termination request generation means for generating a termination request requesting that the allocation of the shared resource in connection with the communication be terminated.

36. A device according to claim 34 or 35, further comprising quality of service determination means for determining a desired quality of service for the communication and wherein the bid generation means is operable to generate a bid which requests sufficient allocation of the shared resource to achieve the desired quality of service.

37. A device according to any of claims 34 to 36, wherein the bid generation means is adapted to generate bids having a plurality of different bid options, each bid option including a requested allocation of the shared resource and a price offered for the requested allocation.

38. A controlling device for controlling access to, or use of, a shared resource by one or more devices operable to access or use the shared resource, the controlling means including:

instruction receiving means for receiving instructions about how much of the shared resource should be allocated to the or each device;

storage means for storing data indicating how much of the shared resource should be allocated to the or each device; and

controlling means for controlling access to or use of the shared resource by the or each device operable to access or use the shared resource in accordance with said stored data.

39. A method of controlling access to or utilisation of a shared resource amongst a plurality of devices operable to access or use the shared resource, said method comprising the steps of:

obtaining from one or more of the devices an indication of one or more desired amounts of the shared resource which the device wishes to use and of how much the device is prepared to pay for the or each desired amount of the shared resource;

obtaining or determining a current cost for accessing or using a unit amount of the shared resource;

determining the amount of the shared resource which the or each device may access or use in accordance with its indication and the current cost; and

informing the or each device of the amount of the shared resource which it may access or use.

40. A method according to claim 39, wherein the shared resource is split into a plurality of different types of sub-resource, which have different properties and/or costs per unit amount.

41. A method according to claim 39 or 40, wherein the shared resource is a resource required during the transmission of a signal over a communications network.

42. A method according to claim 39, 40 or 41, wherein the shared resource is one of:

bandwidth over a communications network between two or more users of the network;

processing power of a shared processing device connected to a communications network;

or data storage capacity within a data storage device connected to a communications network, or any combination of these three resources.

43. A method according to any of claims 39 to 42 wherein each indication further includes an indication as to a quality measure of the resource associated with the or each desired amount of the resource and the amount which the device is prepared to pay for that amount.

44. A method according to claim 43 wherein the quality measure is one of:

a minimum acceptable latency or round-trip packet delay;

a minimum level of packet jitter;

a minimum assured continuous bandwidth throughput;

or another measure of network performance.

45. A method according to any of claims 39 to 44 wherein each indication comprises a preference table setting out a plurality of bid options each of which includes a requested amount of the resource and an associated ceiling price.

46. A method according to claim 45 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a type of content, whereby different groups of bid options may be used for different types of content to be transmitted.

47. A method according to claim 45 or 46 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a class of user, whereby different groups of bid options may be used for different classes of user to whom or from whom data is to be transmitted or received.

48. A method according to claim 45, 46 or 47 wherein the preference table comprises a plurality of groups of bid options, each group being associated with a type of application, whereby different groups of bid options may be used for different types of application controlling data to be transmitted over a network to which the device is attached.

49. A method according to any of claims 45 to 48 wherein the preference table includes an explicit preference order for the bid options.

50. A method according to any of claims 45 to 49 wherein the preference table comprises one or more groups of bid options, each group containing a plurality of bid options setting out a requested amount of the resource and a price offered for that amount, wherein the price offered per unit of the resource in each bid option is set to equal the difference in benefit to the device divided by the difference in the amount of the resource in going to the respective bid option from the next lowest bid option.

51. A method according to any of claims 45 to 50 wherein the preference table includes a marker for indicating that the bidding table reflects the benefit to the device of each amount of the resource included in the bid options.

52. A method according to any of claims 45 to 51 wherein the preference table includes an indication that one or more different requests for an amount of the resource are related in some way such that the benefit associated with one request being successful is dependent on the success of the or each other related request.

53. A method according to any of claims 39 to 52 wherein the devices are connected to a first network which in turn is connected to a second network, said method further including the steps of said first network purchasing an amount of a second network shared resource from the second network for onward sale to one or more of the devices as part of the shared resource requested by the or each device, the purchasing step including estimating the aggregated amount of demand for the shared resource at a plurality of different costs of the shared resource desired by the or each device on the basis of the indications from the or each device.

54. A method according to claim 53 wherein the purchasing step includes determining the desired amount of the second network shared resource to purchase on behalf of the first network on the basis of the estimated level of demand for said shared resource from the or each of said devices.

55. A method according to claim 53 or 54 wherein the purchasing step includes reviewing the desired amount of the second network shared resource to purchase with a frequency which is greater than once every hour but less than once every minute.

56. A method according to any of claims 39 to 55 wherein the indication obtaining step comprises generating and transmitting a bid to a resource allocation means, the bid including at least one requested amount of the resource and an associated price.

57. A method according to claim 56 wherein the current cost accessing or determining step comprises said resource allocation means receiving one or more bids from one or more of the devices, determining a current price per unit of the resource available in dependence on the received bids and determining the amount of the resource which can be used or accessed by each device in dependence on the received bids and the current price per unit of the resource available.

58. A method according to claim 57 wherein the resource allocation means performs the informing step of informing the or each device of the amount of the resource which it can use or access.

59. A method according to any of claims 39 to 58 further comprising the steps of:

causing a controlling means to control access to or use of the resource by the or each device, and

instructing the controlling means to restrict the amount of the resource which the or each device may access or use to the amount determined by the resource allocation means.

60. A method according to any of claims 57, 58 or 59, wherein the allocating step includes determining a first price per unit of the shared resource and allocating the requested amount of the shared resource in response to bids whose price offered per unit of the resource is equal to or greater than said first price.

61. A method according to claim 60, wherein the allocating step further includes varying the first price according to the level of demand for the shared resource as determined by the received bids so as to maintain the utilization of the resource approximately equal to a predetermined percentage of the maximum utilization of the resource possible.

62. A method according to claim 60 or 61, wherein the allocating step further includes determining a second price per unit of the resource and allocating a requested amount of the shared resource in response to a new bid if the price offered per unit of the resource is equal to or greater than said second price.

63. A method as claimed in claims 61 and 62 wherein the allocating step further includes varying the second price according to the level of demand as determined by the received bids, at a rate which is greater than the rate at which the first price is varied.

64. A method as claimed in claim 63 wherein the allocating step further comprises setting the second price to a value higher than said first price in response to the level of demand as determined by the received bids being greater than a predetermined threshold.

65. A method as claimed in claim 63 wherein the allocating step further comprises setting the second price to a value higher than said first price in response to a measure of the quality of the resource falling below a predetermined threshold.

66. A method as claimed in any of claims 39 to 55 wherein the indication obtaining step is performed by a resource management agent which also performs the current cost accessing or determining step and the informing step.

67. A method as claimed in claims 40, 44 and 66 wherein the resource management agent of an associated device receives a notification from a current price storing means of the current price per unit amount of resource for each of said sub-resources, and determines how much resource, and of which sub-resource or sub-resources, the device should access or use in accordance with a measurement of the quality of service associated with each sub-resource and the respective indication from the device as to the amount of the shared resource desired, at what quality and at what price.

77. A computer program for carrying out a method according to any of claims 39 to 76.

78. A carrier medium for carrying the computer program according to claim 77.

68. A resource allocation method for allocating access to or use of a shared resource amongst a number of devices which are operable to use the resource, said resource allocation method comprising:

receiving a plurality of bids from one or more of the devices adapted to access or use the shared resource, which bids indicate a requested amount of the shared resource and a price offered for the requested amount;

determining an allocation of access to or use of the resource by the devices in dependence on the bids received; and

instructing a controlling device to control access to the shared resource in accordance with the determined allocation.

69. A resource management method for controlling the use, by a device connected to a data network, of a resource or sub-resources required by the device to transmit or receive data over the data network, the resource management method comprising:

interfacing with a set of preferences associated with the device, said set of preferences including at least one set of indications as to what amounts of the resource or sub-resources are desired by the device for given levels of quality of service associated with the resource or sub-resources and for given ceiling prices under a given set of properties of an associated flow of data to or from the device over the network;

interfacing with the network to determine properties of the resource or sub-resources including the associated level or levels of quality of service, and the associated cost or costs; and

determining an appropriate amount or amounts of the resource or sub-resources for the device to use for an associated flow of data in dependence upon said set of preferences and said properties of said resource or sub-resources.

70. A resource management method as claimed in claim 69 wherein the determining step includes generating estimated indications, on the basis of said set of preferences associated with the device, as to what amounts of the resource or sub-resources are actually desired by the device for levels of quality of service associated with the resource or sub-resources and for the cost or costs of the resource or sub-resources actually available from the network for a given flow of data to or from the device over the network, where the actually available levels of quality of service and cost differ from those included in the set of preferences.

71. A method of routing bids comprising:

receiving bids from users of a shared resource which bids indicate a requested amount of the shared resource and a price offered for the requested amount;

storing address data of one or more allocating devices operable to allocate portions of the shared resource to bidding users together with data indicating the nature of the shared resource which is able to be allocated by the or each allocation device;

processing each bid using said stored data to determine whether the bid should be forwarded to an allocation device and if so to which allocation device it should be forwarded; and

forwarding bids to allocation devices.

72. A bidding method for use by a bidding device operable to communicate with a correspondent device over a communications network, said communications network including at least one shared resource, access to which is required by both the bidding device and the correspondent device in order for a communication between the bidding and correspondent devices to occur, said method including:

detecting the initiation of a communication between the bidding device and the correspondent device; and

generating a bid indicating a requested allocation of the shared resource and a price offered for the requested allocation in response to detection by the detection means of the initiation of a communication.

73. A method according to claim 72, further comprising detecting the termination of the communication;

and

generating a termination request requesting that the allocation of the shared resource in connection with the communication be terminated.

74. A method according to claim 72 or 73, further comprising quality of service determination means for determining a desired quality of service for the communication and wherein the bid generation means is operable to generate a bid which requests sufficient allocation of the shared resource to achieve the desired quality of service.

75. A method according to any of claims 72 to 74, wherein the bid generation step includes generating bids having a plurality of different bid options, each bid option including a requested allocation of the shared resource and a price offered for the requested allocation.

76. A method of controlling access to, or use of, a shared resource by one or more devices operable to access or use the shared resource, the method including:

receiving instructions about how much of the shared resource should be allocated to the or each device;

storing data indicating how much of the shared resource should be allocated to the or each device; and

controlling access to or use of the shared resource by the or each device operable to access or use the shared resource in accordance with said stored data.

79. A method of generating a bid for use by a bidding device operable to communicate with a correspondent device over a communications network, said communications network including at least one shared resource, access to which is required by both the bidding device and the correspondent device in order for a communication between the bidding and the correspondent devices to occur, said method including:

forming a plurality of bid options each of which indicates a desired amount of the resource together with a price offered for that amount of resource;

generating information identifying one or more properties of the flow for which the shared resource is required; and

bundling the bid option and flow information together to form a bid.

80. A method of generating data for transmission by a sending device to a receiving device over a communications network, said communications network including at least one shared resource, access to which is required by both the sending device and the receiving device, said method including:

receiving an indication as to how much of the shared resource may be used by the transmitting and receiving devices to enable transmission of the generated data;

generating data for transmission over the network which data includes address information of both the sending and receiving devices; and

transmitting the data onto the network at a rate such that the indicated amount of the shared resource is not exceeded.