Efficient, rate-base multiclass access control

Abstract

A fair and efficient admission scheme enables sharing of a common resource among N traffic classes, such that each class is guaranteed (on a suitable long-term basis) a contracted minimum use of the resource, and each class can go beyond the contract when extra resource capacity becomes temporarily available. The scheme operates in an open loop mode, and thus does not require information describing the current status of the resource. For the purposes of description, one form of the invention is best described in terms of "tokens" and "token banks" with finite sizes. Our scheme uses one token bank per class (bank `i`, i= 1, . . . ,N), plus one spare bank. Class `i` is preassigned a rate, rate(i), i=1, . . . ,N, that represents the "guaranteed throughput" or contracted admission rate for class `i`. Tokens are sent to bank `i` at rate(i). Tokens that find a full bank are sent to the spare bank. When the spare bank is also full, the token is lost. Every admitted arrival consumes a token. A class `i` arrival looks first for a token at bank `i`. If bank `i` is empty, it looks for a token at the spare bank. If the latter is also empty, the arrival is blocked.

We claim: 
     
       1. A method for allocating access to a shared limited resource by a plurality of requesters requesting access to said shared limited resource, said allocation being made such that each requester in said plurality of requesters is granted access to said shared limited resource at a minimum guaranteed rate associated with said each requester and such that said shared limited resource is available for use by any requester exceeding its minimum guaranteed rate only if said shared limited resource is available, said method comprising the steps of: assigning tokens to said each requester at a rate determined by the minimum guaranteed rate associated with said each requester;   storing tokens assigned to said each requester in a bank associated with said each requester, said bank having a finite capacity;   storing tokens assigned to said each requester in a common bank if said bank associated with said each requester is full; and   allowing said each requester to gain access to said shared limited resource by first using tokens in said each requester's bank or by then using tokens in said common bank, and otherwise denying access to said shared limited resource.   
     
     
       2. A method for fair and efficient allocation among competing classes of users of access to a common resource, comprising the steps of (a) establishing an incrementable counter for each class of users, said incrementable counter having a count:   (b) incrementing the count in the counter established for each class of users at a rate associated with said each class of users if said count is below a predefined maximum;   (c) permitting a class of users to access said common resource if the count in the counter established for said each class of users is non-zero;   (d) decrementing the count in the counter established for each class of users upon each use of said common resource by said each class of users;   (e) incrementing the count in a common counter if the count in any counter incremented in step (b) is at said predefined maximum;   (f) permitting a class of users to access said common resource even if the count in the counter established for said class of users is zero, provided that the count in said common counter is non-zero; and   (g) decrementing the count in said common counter if access is permitted in step (f).   
     
     
       3. 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, rate `i`, to each of said N users, said rate indicating the minimum desired access for the i th  user, where 1≦i≦N;   storing indicia of the eligibility of the i th  user to access said common resource in an associated token bank, bank `i`;   incrementing the indicia in bank `i` at the rate, rate `i` up to a predetermined limit, limit `i`;   establishing a common token bank, bank `N+1`, said common token bank having a predetermined limit `N+1`;   incrementing the indicia in bank `N+1` in the event that any token bank `i` is at its associated limit, limit `i`, and said common token bank is not at limit `N+1`;   allowing the i th  user to access said common resource if either bank `i` or bank `N+1` is not empty; and   decrementing the indicia in bank `i` or bank `N+1` upon granting of access to said common resource.   
     
     
       4. A method of sharing admission to a resource by a plurality of competing users on a fair and efficient basis, comprising the steps of: allocating a nominal allowable admission rate to each of said competing users;   storing indicia of actual admissions to said resource by each of said competing users;   admitting, in response to said stored indicia, any of said competing users that have been admitted to said resource at less than their nominal rate,   storing an indication representing a difference, over a selected time period, for all of said competing users, said difference being the difference between the nominal and actual admissions to said resource; and   admitting any of said competing users that have exceeded their nominal rate if said stored indication representing said difference is positive.   
     
     
       5. A method for admitting an integer number N of classes of users to a common resource on a fair and efficient basis, where N>1, comprising the steps of: establishing a plurality of token banks, including one token bank for each of said N classes of users, each of said banks designated as bank `i`, `i`=1. . . , N, plus one spare token bank, bank `N+1`, each of each of said token banks having a finite size;   assigning a rate, rate `i`, i=1, . . . , N to each class i, rate `i` representing the allocated admission rate for class i;   sending tokens to bank `i` at rate `i`;   sending tokens that find a full token bank to said spare token bank;   discarding tokens sent to said spare token bank when said spare token bank is also full;   for each class i arrival, first using a token from bank `i` in order to admit said class i arrival to access said common resource;   if bank `i` is empty, then using a token from said spare token bank in order to admit said class i arrival to access said common resource; and   blocking admission to said common resource if said spare token bank is also empty.   
     
     
       6. A method for allocating access to a shared limited resource by a plurality of N requesters requesting access to said shared limited resource, said allocation being made such that each requester is granted access to said shared limited resource at a minimum guaranteed rate associated with said each requester and such that said shared limited resource is available for use by other requesters exceeding their minimum guaranteed rate only if some requesters have not used their entire allocation in the recent past, said method comprising the steps of: assigning credit to said each requester at said minimum guaranteed rate associated with said each requester;   associating with said each requester, a first sequence of banks selected from a set of M banks for storing credit assigned to said each requester, each of said M banks having a finite capacity, where M and N are integers greater than 1;   storing credit assigned to said each requester in the first bank in that requester's said first sequence of banks that is below its said capacity, or discarding said credit if none of said banks in said each requester's said first sequence of banks is below said capacity;   associating with said cach requester, a second sequence of banks selected from said set of M banks for using credit stored in said plurality of M banks; and   allowing a requester to gain access to said shared limited resource by withdrawing credit available in the first non-empty bank in said each requester's said second sequence of banks, and otherwise denying access to said shared limited resource.   
     
     
       7. A method for allocating access to a common resource, among N competing classes of users, comprising the steps of: (a) establishing M incrementable counters each having a predefined maximum, M and N being integers greater than 1;   (b) for each of said classes of users, establishing a rate at which, and a first sequence in which, ones of said M incrementable counters are incremented;   (c) for each of said classes of users, incrementing the count in the first one of said counters in said first sequence that has a count that is below said predefined maximum;   (d) for each of said classes of users, establishing a second sequence in which ones of said M counters are decremented;   (e) allocating access to said resource to any of said classes of users if the count in any of the counters in said second sequence established for said any of said classes of users is non-zero;   (f) decrementing the count in the first one of said counters in said second sequence that has a non-zero count, upon each use of said common resource by said any of said classes of users; and   (g) denying access to said common resource to said any of said classes of users if the count in all of the counters in said second sequence is zero.   
     
     
       8. A method for sharing access to a common resource among N users, comprising the steps of assigning a rate, rate `i`, to each of said N users, said rate indicating the minimum desired access for the i th  user, where N is an integer greater than 1 and where 1≦i≦N;   storing indicia of the eligibility of any user to access said common resource in a series of M banks, each of said M banks having a predetermined limit, limit `j`, where M is an integer greater than 1 and where 1≦j≦M;   for the i th  user, incrementing the indicia in said M banks at rate `i`, up to respective limits, said M banks being incremented in a first sequence associated with said i th  user, the increment being discarded if all of said banks in said first sequence are at said limit;   allowing the i th  user to access said common resource if any bank in a second sequence of banks associated with said i th  user is not empty; and   decrementing the indicia in the first bank in said second sequence that contains any indicia, upon granting of access to said common resource.   
     
     
       9. A method for admitting users in N classes to a common resource on a fair and efficient basis, comprising the steps of: establishing M banks, where M and N are integers greater than 1;   establishing, for each of said N classes, a rate at which said class earns credit required to admit said class to said common resource;   establishing first and second sequences for each of said N classes, said first sequence indicating the order in which credit earned by said class is deposited in said M banks, and said second sequence indicating the order in which credit required by said class is withdrawn from said M banks;   for each of said N classes, depositing credit earned at said rate established for said class, in said M banks in accordance with said first sequence, and discarding credit when all banks in said first sequence are full;   admitting users in each of said N classes to said common resource by withdrawing credit from said M banks in accordance with said second sequence, and   blocking admission to said common resource to a user in a class if all banks in said second sequence are empty.   
     
     
       10. The method defined in claim 9 wherein M=N+1, and wherein said first and second sequences are the same. 
     
     
       11. A method of regulating access of multiclass arrivals to a common resource, comprising the steps of: (1) storing credit earned by each class in a plurality of M banks each having a finite credit limit, where M is an integer greater than 1, wherein said storing step includes:   (a) assigning a rate at which each class earns credit; (b) establishing a first sequence in which credit for each class is stored in said M banks; (c) depositing credit in the first bank in said first sequence that has not exceeded its credit limit; (d) discarding credit if all banks in said first sequence have exceeded their credit limit; and   (2) regulating access to said common resource by arrivals from each class, wherein said regulating step includes:   (a) establishing a second sequence in which arrivals from each class seek to use credit stored in said M banks; (b) allowing an arrival to access said common resource by withdrawing credit in the first bank in said second sequence that has credit available; (c) denying access to said common resource if no banks in said second sequence contain credit that can be withdrawn in step (2(b) above.   
     
     
       12. A method of controlling admission of arrivals from users in N classes seeking access to a common resource, each of said users having an associated rate at which access to said common resource is guaranteed, comprising the steps of: in response to an arrival from a user in any of said N classes, updating the credit in each of a plurality of M banks in accordance with the rate associated with each of said users, where M and N are integers greater than 1,   determining if said arrival is admitted to use said common resource or rejected; and   awaiting the next arrival,   wherein said updating step includes:   (a) for the first class, determining the amount of credit earned since the last update;   (b) adding the amount determined in (a) to the contents of the first bank in the sequence of banks associated with the first class;   (c) determining if the bank is above its limit;   (d) if so, setting the contents of the bank at its limit and adding the excess credit to the next bank in the sequence;   (e) repeating steps (a) to (d) for the remaining classes; and   wherein said determining step includes:   (f) in response to an arrival from a user in any of said N classes, determining if the first bank in the sequence associated with said user contains sufficient credit required to permit said arrival to access said common resource;   (g) if a positive result is determined in step (f), allowing access to said common resource by said arrival by withdrawing credit from said bank; and   (h) if a negative result is determined in step (f), repeating step (f) with respect to the next bank in the sequence associated with said user.   
     
     
       13. Apparatus for allocating access to a shared limited resource by a plurality of requesters requesting access to said shared limited resource, said allocation being made such that each requester is granted access to said shared limited resource at a minimum guaranteed rate associated with said each requester and such that said shared limited resource is available for use by any requester exceeding its minimum guaranteed rate only if said shared limited resource is available, said apparatus comprising: means for assigning tokens to said each requester at a rate determined by the minimum guaranteed rate associated with said each requester;   storing means for (a) storing tokens assigned to said each requester in a bank associated with said each requester, said bank having a finite capacity, and for (b) storing tokens assigned to any requester in a common bank if the bank associated with said each requester is full; and   means for allowing a requester to gain access to said shared limited resource by first using tokens in said each requester's bank or by then using tokens in said common bank, and otherwise denying access to said shared limited resource.   
     
     
       14. Apparatus for fair and efficient allocation among competing classes of users of access to a common resource, comprising (a) an incrementable counter associated with each class of users, and a common counter, each counter having a count;   (b) means for incrementing the count in the counter associated with each class of users at a rate associated with said each class of users if said count is below a predefined maximum and for incrementing the count in said common counter if the count in any of said associated counters is at or above said predefined maximum;   (c) means for permitting a class of users to access said common resource if the count in the associated counter for said each class of users is non-zero, or if the count in the associated counter for said class of users is zero, provided that the count in said common counter is non-zero;   (d) means responsive to said permitting means for decrementing the count in either the associated counter for each class of users, or in the common counter, upon each use of said common resource by said each class of users.   
     
     
       15. Apparatus for sharing admission to a resource by a plurality of competing users on a fair and efficient basis, comprising: means for allocating a nominal allowable admission rate to each of said competing users;   means for storing indicia of actual admissions to said resource by each of said competing users and an indication representing a difference, for all users, said difference being the difference between the nominal and actual admissions to said resource; and   means for admitting, in response to said stored indicia, any user that has been admitted to said resource at less than its nominal rate, and users that have exceeded their nominal rate, but only if said stored indication representing said difference is positive.   
     
     
       16. Apparatus for admitting N classes of users to a common resource on a fair and efficient basis, where N is an integer greater than 1, comprising: a plurality of token banks, including one token bank for each of said N classes, each of said token banks designated as, plus one spare token bank, bank `N+1`, each of said token banks having a finite size;   means for assigning a rate, rate `i`, i=1, . . . , N to each class i, rate `i` representing the allocated admission rate for class i;   means for sending tokens to bank `i` at rate `i`;   means for sending tokens that find a full token bank to said spare token bank;   means for discarding tokens sent to said spare token bank when said spare token bank is also full;   means for admitting a class i arrival to access said common resouce by first using a token from bank `i` and if bank `i` is empty, then using a token from said spare token bank and for blocking admission to said common resource if said spare token bank is also empty.   
     
     
       17. Apparatus for allocating access to a shared limited resource by a plurality of N requesters requesting access to said shared limited resource, said allocation being made such that each requester is granted access to said shared limited resource at a minimum guaranteed rate associated with said each requester and such that said shared limited resource is available for use by other requesters exceeding their minimum guaranteed rate only if some requesters have not used their entire allocation in the recent past, said apparatus comprising: means for assigning credit to said each requester at said minimum guaranteed rate associated with said each requester,   means for associating with said each requester, a first sequence of banks selected from a set of M banks for storing credit assigned to said each requester, each of said M banks having a finite capacity, where M and N are integers greater than 1;   means for storing credit assigned to said each requester in the first bank in that requester's said first sequence of banks that is below its said capacity, or discarding said credit if none of said banks in said requester's said first sequence of banks is below said capacity;   means for associating with each requester, a second sequence of banks selected from said set of M banks for using stored credit; and   means for allowing a requester to gain access to said shared limited resource by withdrawing credit available in the first non-empty bank in said each requester's said second sequence of banks, and otherwise denying access to said shared limited resource.   
     
     
       18. Apparatus for allocating access to a common resource among N competing classes of users, comprising: (a) M incrementable counters each having a predefined maximum, where M and N are integers greater than 1,   (b) means for incrementing said counters in a first sequence and at a rate established for each class of users, said means arranged to increment only ones of said M counters in said first sequence that have a count that is below said predefined maximum;   (c) means for decrementing said counters in a second sequence upon each use of said common resource by said class of users, and   (d) means for allowing access to said common resource to a class of users if the count in any of the counters in said second sequence established for said class of users is non-zero and for denying access to said common resource to a class of users if the count in all of the counters in said second sequence is zero.   
     
     
       19. Apparatus for sharing access to a common resource among N users, comprising means for assigning a rate, rate `i`, to each of said N users, said rate indicating the minimum desired access for the i th  user, where N is an integer greater than 1 and where 1≦i≦N;   means for storing indicia of the eligibility of any user to access said common resource in a series of M banks, each of said banks having a predetermined limit, limit `i` where M is an integer greater than 1 and where 1≦j≦M;   means for incrementing the indicia in said M banks at rate `i` up to respective limits for the i th  user, in accordance with a first sequence associated with said user, said increment being discarded if all of said M banks in said first sequence are at said limit;   means for allowing the i th  user to access said common resource if any banks in a second sequence of banks associated with said i th  user is not empty; and   means for decrementing the indicia in the first bank in said second sequence that contains any indicia, upon granting of access to said common resource.   
     
     
       20. Apparatus for admitting users in N classes to a common resource on a fair and efficient basis, comprising: M banks, where M and N are integers greater than 1;   means for establishing, for each of said N classes, a rate at which said class earns credit required to admit said class to said common resource;   means for establishing first and second sequences for each of said N classes, said first sequence indicating the order in which credit earned by said class is deposited in said M banks, and said second sequence indicating the order in which credit used by said class is withdrawn from said M banks;   means for depositing, for each of said N classes of users, credit earned at said rate established for said class, in said M banks in accordance with said first sequence, and discarding credit when all banks in said first sequence are full;   means for admitting users in each of N classes of users to said common resource by withdrawing credit from said M banks in accordance with said second sequence; and   means for blocking admission to said common resource to a user in a class if all banks in said second sequence are empty.   
     
     
       21. The invention defined in claim 20 wherein M=N+1, and wherein said first and second sequences are the same. 
     
     
       22. Apparatus for regulating access of multiclass arrivals to a common resource, comprising: (1) means for storing credit earned by each class in a plurality of M banks each having a finite credit limit, where M is an integer greater than 1, wherein said storing means is arranged to:   (a) assign a rate at which each class earns credit; (b) establish a first sequence in which credit for each class is stored in said M banks; (c) deposit credit in the first bank in said first sequence that has not exceeded its credit limit; (d) discard credit if all banks in said first sequence have exceeded their credit limit; and   (2) means for regulating access to said common resource by arrivals from each class, wherein said regulating means is arranged to   (a) establish a second sequence in which arrivals from each class seek to use credit stored in said M banks; (b) allow an arrival to access said common resource by withdrawing credit in the first bank in said second sequence that has credit available; and (c) deny access to said common resource if no banks in said second sequence contain credit that can be withdrawn in accordance with paragraph (2)(b) above.   
     
     
       23. Apparatus for controlling admission of arrivals from users in N classes seeking access to a common resource, each of said users having an associated rate at which access to said common resource is guaranteed, comprising: means for updating, in response to an arrival from a user in any of said classes, the credit in each of a plurality of M banks in accordance with the rate associated with each of said users, where M and N are integers greater than 1;   means for determining if said arrival is admitted to use said common resource or rejected; and   means for awaiting the next arrival,   wherein said updating means is arranged to:   (a) determine, for the first class, the amount of credit earned since the last update; (b) add the amount determined in (a) to the contents of the first bank in the sequence of banks associated with the first class; (c) determine if the bank is above its limit; (d) if so, set the contents of the bank at its limit and adding the excess credit to the next bank in the sequence; (e) repeat steps (a) to (d) for the remaining banks;   and wherein said determining means is arranged to:   (a) determine, in response to an arrival from a user in any of said classes, if the first bank in the sequence associated with said user contains sufficient credit required to permit said arrival to access said common resource; (b) if a positive result is determined in step (a), allow access to said common resource by said arrival by withdrawing credit from said bank; (c) if a negative result is determined in step (a), repeat step (a) with respect to the next bank in the sequence associated with said user.   
     
     
       24. A method for allocating access to a shared limited resource by a plurality of N requesters requesting access to said shared limited resource, said allocation being made such that each requester is granted access to said shared limited resource at a minimum guaranteed rate associated with said requester and such that said shared limited resource is available for use by other requesters exceeding their minimum guaranteed rate only if some requesters have not used their entire allocation in the recent past, said method comprising the steps of: storing credit assigned to each requester at said minimum guaranteed rate associated with said requester, in the first of M banks in a first sequence of banks that is below its capacity, or discarding said credit if none of said banks in said first sequence is below its capacity, where M and N are integers greater than 1; and   allowing a requester to gain access to said shared limited resource by withdrawing credit available in the first one of said M banks in a second sequence of banks that contains credit.   
     
     
       25. Apparatus for sharing access to a common resource among N users, each user having an identity represented by an index `i` where N is an integer greater than 1 and where 0≦i≦N; comprising means for assigning a rate, rate `i`, to each of said N users, said rate indicating the minimum desired access for the i th  user;   means for storing indicia of the eligibility of the i th  user to access said resource in an associated token bank, bank `i`;   means for incrementing the indicia in bank `i` at the rate rate `i` up to a predetermined limit, limit `i`;   means for establishing a common token bank, bank `N+1`, said common token bank having a predetermined limit `N+1`;   means for incrementing the indicia in bank `N+1` in the event that any of said other token banks is at its associated limit and said common token bank is not at limit `N+1`;   means for allowing the i th  user to access said common resource if either bank `i` or bank `N+1` is not empty; and   means for decrementing the indicia in bank `i` or bank `N+1` upon granting of access to said common resource.   
     
     
       26. A method for admitting users in N classes to a common resource on a fair and efficient basis, comprising the steps of: establishing M counters, where M and N are integers greater than 1, each of said counters having a count, said count in said counters ranging from 0 to a finite limit, in arbitrarily small increments, the difference between said count in a counter and its limit being designated as the space in said counter;   establishing, for each of said N classes, a rate at which said class earns credit, and a cost required to admit said class to said common resource;   establishing first and second sequences for each said classes, said first sequence indicating the order in which credit earned by said class is accounted for in said counters, and said second sequence indicating the order in which the debit incurred upon admittance of said class is accounted for in said counters;   for each of said classes, incrementing the count in said counters at said rate established for said class, said incrementing being performed in accordance with said first sequence, and discarding credit when all counters in said first sequence are at their limit;   admitting arrivals in each of said classes to said common resource by decrementing the counters by the cost associated with said class, said decrementing being performed in accordance with said second sequence; and   blocking admission to said common resource to an arrival in a class if the sum of the counts in said counters in said second sequence does not add up to the admittance cost for said class.   
     
     
       27. A method for allocating access to a shared limited resource by a plurality of requesters requesting access to said shared limited resource, said allocation being made such that each requester is granted access to said shared limited resource at least at a minimum guaranteed rate associated with said each requester, comprising the steps of: assigning credit to said each requester at said minimum guaranteed rate associated with said each requester;   storing each credit assigned to said each requester in one of a plurality of credit banks, each of said credit banks having a finite capacity, there being first and second sequences of said credit banks associated with said each requester, and each credit assigned to said each requester being (a) stored in the first one of the banks of said first sequence that is below said capacity or (b) discarded if none of the banks of said first sequence is below said capacity, and   if at least one of the banks of said second sequence is non-empty, allowing a requester to gain access to said shared limited resource and concomitantly withdraw credit stored in the first non-empty one of said second sequence banks.   
     
     
       28. A method for admitting users in N classes to a common resource on a fair and efficient basis, comprising the steps of: establishing M counters, where M and N are integers greater than 1, each of said counters having a count, said count in said counters ranging from 0 to a finite limit, in arbitrarily small increments, the difference between said count in a counter and its limit being designated as the space in said counter;   establishing, for each of said N classes, a rate at which said class earns credit, and a cost required to admit said class to said common resource;   establishing first and second sequences for each said classes, said first sequence indicating the order in which credit earned by said class is accounted for in said counters, and said second sequence indicating the order in which the debit incurred upon admittance of said class is accounted for in said counters;   for each of said classes, decrementing the count in said counters at said rate established for said class, said decrementing being performed in accordance with said first sequence, and discarding credit when all counters in said first sequence are empty;   admitting arrivals in each of said classes to said common resource by incrementing the counters by the cost associated with said class, said incrementing being performed in accordance with said second sequence; and   blocking admission to said common resource to an arrival in a class if the sum of the space in said counters in said second sequence does not add up to the admittance cost for said class.