Systems and methods for sharing of resources

• US 5,596,576 A
• Filed: 11/03/1995
• Issued: 01/21/1997
• Est. Priority Date: 11/03/1995
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Milito, Rodolfo A.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US08/552,899
• Time in Patent Office: 445 Days
• Field of Search: 370/17, 370/60, 370/60.1, 370/61, 370/85.6, 370/94.1, 370/85.4, 370/95.1, 370/58.1, 370/58.2, 370/85.7, 370/77, 370/79, 370/84
• US Class Current: 370/450
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket

Abstract

A method for allocating access to a shared limited resource among a plurality of users who require access to the resource, the allocation being made such that each user is granted access to the resource at a minimum guaranteed rate associated with each user and such that the resource is available for use by any user exceeding its minimum guaranteed rate only if the resource is available, the method comprising the steps of: assigning tokens to each user at a rate determined by the minimum guaranteed rate associated with each user; storing tokens assigned to each user in a bank associated with each user, each bank having a finite capacity associated with each user; storing tokens assigned to a user whose associated bank has reached its capacity in a bank assigned to another user whose bank is below its capacity; and allowing a user requesting access to the resource to have access to the resource if the user has a predetermined number of tokens in its associated bank and otherwise denying access to the resource.

Claims

1. A method for allocating access to a shared limited resource among a plurality of users who require access to said resource, said allocation being made such that each user is granted access to said resource at a minimum guaranteed rate associated with each user and such that said resource is available for use by any user exceeding its minimum guaranteed rate only if said resource is available, said method comprising the steps of:

assigning tokens to each user at a rate determined by the minimum guaranteed rate associated with each user;

storing tokens assigned to each user in a bank associated with each user, each said bank having a finite capacity associated with each user;

storing tokens assigned to a user whose associated bank has reached its capacity in a bank assigned to another user whose bank is below its capacity; and

allowing a user requesting access to said resource to have access to said resource if said user has a predetermined number of tokens in its associated bank and otherwise denying access to said resource.

2. The method of claim 1 wherein said users are assigned different priorities and wherein said another user is selected based on said assigned priorities.

3. The method of claim 1 further comprising the step of deleting a predetermined number of tokens from a bank associated with a user that is granted access to said resource.

4. The method of claim 1 wherein said predetermined number of tokens is one token.

5. The method of claim 1 wherein each said bank has the same predetermined finite capacity.

6. The method of claim 1 wherein at least two of said banks have a different predetermined finite capacity.

7. A method for allocating access to a shared resource, comprising the steps of:

(a) establishing an incrementable counter for each of a plurality of users of said resource, said incrementable counter having a count;

(b) incrementing the count in each counter established for each user at a rate associated with each user if said count is below a predefined maximum count associated with each user;

(c) permitting a user requesting access to said resource to have access if the count in the counter established for said user requesting access is non-zero;

(d) incrementing the count in a counter associated with a user whose counter is below said predefined maximum count at a rate higher than its associated rate if the count in any other counter incremented in step (b) is at its predefined maximum count.

8. The method of claim 7 wherein said users are assigned different priorities and wherein said user selected in step (d) is selected based on said assigned priorities.

9. The method of claim 7 further comprising the step of decrementing the count in the counter established for a user requesting access if said user requesting access is granted access to said resource.

10. The method of claim 7 wherein each said user has the same associated predefined maximum count.

11. The method of claim 7 wherein at least two of said users have a different predefined maximum count.

12. A method for sharing access to a common resource among N users, where N is an integer greater than 1, comprising the steps of:

assigning a rate "R_i " to each of said N users, said rate indicating the minimum desired access rate for the i^th user, where 1≦

i≦

N;

storing an indicia "B_i " of the eligibility of the i^th user to access said common resource for each of said N users;

incrementing each B_i at its associated rate R_i up to a predetermined limit L_i assigned to each of said N users;

incrementing a selected B_i at a rate greater than its associated R_i in the event that any other B_i is at its associated limit L_i, and said selected B_i is not at its limit L_i ; and

allowing the i^th user to access said common resource if its associated B_i is not zero.

13. The method of claim 12 further comprising the step of decrementing B_i upon the granting of access to the ith user of said resource.

14. The method of claim 12 wherein said users are assigned different priorities and wherein said selected B_i is selected based on said assigned priorities.

15. The method of claim 12 wherein each said user'"'"'s associated limit L_i has the same value.

16. The method of claim 12 wherein at least two of said user'"'"'s associated limits L_i have different values.