Method of allocating resources in a telecommunications network

• US 6,498,786 B1
• Filed: 08/03/1999
• Issued: 12/24/2002
• Est. Priority Date: 08/07/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Kirkby, Paul Anthony, Sabesan, Subramanian, Biddiscombe, Martin
• Primary Examiner(s): Vincent, David
• Assistant Examiner(s): Wilson, Robert W.
• Application Number:
  US09/368,280
• Time in Patent Office: 1,239 Days
• Field of Search: 370/95.1, 370/110.1, 370/230, 370/232, 370/233, 370/234, 370/322, 370/395.2, 370/468, 379/114-1-1, 455/13.1
• US Class Current: 370/322
• CPC Class Codes: H04L 2012/5612 Ring
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 2213/1313 Metering, billing
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/13349 Network management
• CPC Class Codes: H04Q 3/0066 Bandwidth allocation or management

Abstract

The invention provides a resource allocation method which is based on the concept of proportional fairness. In this method, users express their willingnesses to pay for network resources. A controller determines how the users'"'"' willingnesses to pay are to be divided between the resources in order to determine the relative demands for the resources. Each resource is then divided between those users using it in proportion to how much they are willing to pay for the use of their share of it. The allocation takes into account the relative demands on all the resources in the network. A user may increase his share of the network resources allocated to him by increasing the value of his willingness to pay. The method may be applied either by a central controller (network manager), or it may be delegated to controllers (network element managers/customer premises equipment managers) distributed across the network.

Claims

1. A method of allocating shared resources in a telecommunications network, comprises the step of:

allocating a share in a resource to a user that will utilise said resource in satisfying a request for resources, said share being allocated as a proportion of the resource equal to that user'"'"'s indicated willingness to pay (WtP) value divided by the sum of the demands by all users for the resources of the network that said user will utilise in satisfying said request for resources.

2. A method as claimed in claim 1, wherein it includes the step of allocating the user'"'"'s indicated WtP value between the resources needed to satisfy the user'"'"'s request in proportion to the sums of the demands by all users for those resources in order to update the resources demands information.

3. A method as claimed in claim 1, wherein it includes the step of calculating the demand for each of the resources needed to satisfy the user'"'"'s request by, for each resource, summing the proportions of the WtP values of all users allocated respectively to said resources.

4. A method as claimed in claim 3, wherein it includes the step of calculating the proportions of users'"'"' indicated WtP values allocated to the resources needed to satisfy the user'"'"'s request by setting for each combination of user and resource the proportion of that user'"'"'s WtP value to be allocated to that resource equal to the demand by all users for that resource divided by the sum of the demands by all users for all resources needed to satisfy the user'"'"'s request.

5. A method as claimed in claim 1, wherein it includes as an initial step allocating each user'"'"'s WtP value proportionally between the resources that the user will utilise to satisfy a request for resources in order to establish initial demands for resources.

6. A method as claimed in claim 5, wherein the initial proportions of users'"'"' WtP values allocated to resources are set to the equal.

7. A method as claimed in claim 5, wherein the initial proportions of users'"'"' WtP values allocated to resources are selected randomly.

8. A method as claimed in claim 3, wherein, if the calculated proportions of users'"'"' indicated WtP values allocated to the resources needed to satisfy the user'"'"'s request differ by more than a predetermined amount over previously allocated proportions, the method includes the step of recalculating the demands on each of the resources and using the recalculated demands to determine new proportions of users'"'"' WtP values to be allocated to the resources.

9. A method as claimed in claim 1, wherein a centralised controller allocates network resources to users.

10. A method as claimed in claim 9, wherein the centralised controller forms part of or comprises a network manager.

11. A method as claimed in claim 1, wherein the controller maintains a register of those network resources which are allocatable in proportion to users'"'"' indicated WtP values.

12. A method as claimed in claim 1, wherein the controller determines which of the network resources are required to satisfy a user request for resources.

13. A method as claimed in claim 12, wherein, where the allocatable resources comprise transmission links, the controller determines which transmission link resources are required to satisfy a user request by reference to a look-up routing table which stores a listing of fixed transmission routes across the network.

14. A method as claimed in claim 1, wherein the allocatable resources of the network includes transmission link bandwidth, buffer occupancy and data retrieval from content providers.

15. A method as claimed in claim 1, wherein it includes polling each user for a WtP value for each user request.

16. A method as claimed in claim 1, wherein a user'"'"'s indication of WtP value is related to a value amount remaining in an account of the user.

17. A method as claimed in claim 16, wherein the user maintains its account with the controller.

18. A method as claimed in claim 16, wherein the user subscribes periodically to said account in order to increase the value amount remaining in said account.

19. A method as claimed in claim 1, wherein a user provides a separate WtP value for each of a plurality of requests by the user.

20. A method as claimed in claim 1, wherein a user comprising an entity through which a plurality of second level users are connected to the network expresses a single WtP value comprising an aggregate of the WtP values of said plurality of second level users.

21. A method as claimed in claim 20, wherein said entity allocates the share of network resources allocated to it by the controller in response to the single WtP value indicated by it between the secondary level users in proportion to said secondary level users indicated WtP values divided by the aggregate of the values of the plurality of secondary level users.

22. A method as claimed in claim 1, wherein a user'"'"'s WtP value can be capped to prevent the user from indicating a WtP value above a predetermined limit.

23. A method as claimed in claim 22, wherein a user can set the predetermined capping limit on its WtP value.

24. A method as claimed in claim 22, wherein a user can change its indicated WtP value.

25. A method as claimed in claim 24, wherein a user can periodically change its indicated WtP value by communicating the changed value to the network controller.

26. A telecommunications network comprising:

a plurality of network resources;

a plurality of users;

a controller for receiving user requests for resources, wherein said controller allocates a share in a network resource to a user that will utilise said resource in satisfying a request for resources, said share being allocated as a proportion of the resource equal to that user'"'"'s indicated willingness to pay (WtP) value divided by the sum of the demands by all users for the resources of the network that said user will utilise in satisfying its request for resources.

27. A network as claimed in claim 26, wherein the controller comprises a network manager and said resources comprises a plurality of interconnected transmission links.

28. A network as claimed in claim 26, wherein the transmission links are interconnected by nodes, each node having at least one user associated therewith.

29. A network as claimed in claim 28, wherein each user comprises one of a customer premises network, a private branch exchange (PBX), a service provider (SP), a content provider (CP) and a local area network (LAN).

30. A network as claimed in claim 27, wherein the users are connected across one of a metropolitan area network (MAN) and a wide area network (WAN).

51. A network controller for a telecommunications network as claimed in claim 26.

31. A method of allocating shared resources in a telecommunication network, comprising the steps of:

allocating a share in a resource to an entity that requests use of resources, said share being allocated as a proportion equal to the entity'"'"'s indicated willingness to pay (WtP) value divided by the sum of the demands by all entities for resources of the network that said entity will utilise in satisfying said request for resources; and

said entity allocates its share of the resource between a plurality of users connected to the entity.

32. A method as claimed in claim 31, wherein it includes the step of allocating the entity'"'"'s indicated WtP value between the resources needed to satisfy the entity'"'"'s request in proportion to the sums of the demands by all entities for those resources.

33. A method as claimed in claim 31, wherein it includes the step of calculating the demand for each of the resources needed to satisfy the entity'"'"'s request by, for each resource, summing the proportions of the WtP values of all entities allocated respectively to said resources.

34. A method as claimed in claim 33, wherein it includes the step of calculating the proportions of entities'"'"' indicated WtP values allocated to the resources needed to satisfy the entities'"'"' request by setting for each combination of entity and resource the proportion of that entities'"'"' WtP value to be allocated to that resource equal to the demand by all entities for that resource divided by the sum of the demands by all entities for all resources needed to satisfy the entity'"'"'s request.

35. A method as claimed in claims 31, wherein it includes as an initial step allocating each entity'"'"'s WtP value proportionally between the resources that the entity will utilise to satisfy a request for resources in order to establish initial demands for resources.

36. A method as claimed in claim 35, wherein the initial proportions of entities'"'"' WtP values allocated to resources are set to the equal.

37. A method as claimed in claim 35, wherein the initial proportions of entities'"'"' WtP values allocated to resources are selected randomly.

38. A method as claimed in claim 33, wherein, if the calculated proportions of entities'"'"' indicated WtP values allocated to the resources needed to satisfy the entity'"'"'s request differ by more than a predetermined amount over previously allocated proportions, the method includes the step of recalculating the demands on each of the resources and using the recalculated demands to determine new proportions of entities'"'"' WtP values to be allocated to the resources.

39. A method as claimed in claim 31, wherein the WtP value of the entity is the aggregate of the WtP values of the plurality of users connected to said entity.

40. A method as claimed in claim 39, wherein said entity allocates its share of the resource to its connected users in proportion to each user'"'"'s WtP value divided by the aggregate of the users'"'"' WtP values.

41. A method as claimed in claim 31, wherein the entity'"'"'s WtP value is communicated to a network controller by a local controller associated with the entity.

42. A method as claimed in claim 41, wherein, where the allocatable resources comprise transmission links, the local controller determines the network resources required to satisfy a demand of the entity associated with said controller.

43. A method as claimed in claim 41, wherein the network controller communicates to the local controller the demands made on resources by other entities.

44. A method as claimed in claim 31, wherein a resource is allocated between entities which will utilise it by a local controller associated with that resource.

45. A telecommunication network comprising:

a plurality of network resources;

a plurality of entities;

a network controller for controlling the allocation of resources between the entities; and

at least one local controller associated with one of said entities;

wherein

said network controller controls the allocation of shares in a network resource to each of a set of entities that will utilise said resource, said shares being allocated in proportion to each entity'"'"'s indicated willingness to pay (WtP) value divided by the sum of the demands by all entities for all network resources that said entity will utilise, and

the entity associated with the at least one local controller allocates its share of the network resource to a plurality of users connected to the network via said entity.

46. A method as claimed in claim 45, wherein the local controller allocates shares in a resource associated with said controller.

47. A network as claimed in claim 45, wherein the local controller comprises a network element manager of a node of which the controller forms part.

48. A network as claimed in claim 45, wherein the local controller communicates a single WtP value on behalf of its associated entity to the network controller, said single WtP value being an aggregate of the WtP values of the plurality of users connected by the entity to the network.

49. A network as claimed in claim 45, wherein it comprises a SDH/SONET ring.

50. A network as claimed in claim 45, wherein the entities comprise any combination of customer premises networks, local area networks (LAN), service providers (SPs) and content providers (CPs).

52. A local controller for a telecommunications network as claimed in claim 45.