Priority-based arbitrator on a token-based communication medium

• US 5,566,177 A
• Filed: 10/09/1994
• Issued: 10/15/1996
• Est. Priority Date: 10/09/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bhandari, Inderpal S., Rajkumar, Ragunathan, MacInnis, Alexander G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/320,462
• Time in Patent Office: 737 Days
• Field of Search: 370/85.1, 370/85.2, 370/85.4, 370/85.5, 370/85.6, 370/85.11, 370/85.12, 370/85.7, 370/85.8, 340/825.05, 340/825.5, 340/825.51, 395/200.21
• US Class Current: 370/452
• CPC Class Codes: H04L 12/40143 involving priority mechanisms hybrid switching fabrics H04L12/6402; intermediate storage or scheduling H04L49/90; time-division multiplex systems H04J3/00
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 2012/6435 Bus
• CPC Class Codes: H04L 2012/6437 Ring
• CPC Class Codes: H04L 2012/6451 Deterministic, e.g. Token, DQDB
• CPC Class Codes: H04L 2012/6464 Priority

Abstract

This invention is an arbitration scheme for a token-based communications medium which is intended for use when there are timing deadlines for transactions on the medium. Initially knowledge of the expected workload is used to determine for each module its priority as well as the limit on the duration of time lower priority modules can be permitted to use the medium between request and completion of a transaction for this module. A count is maintained for each module of the number of data units that has been transferred on the medium by lower priority modules since the time this module last requested the medium. A module can transmit a selected number of data units if it has the token and the count of none of its higher priority modules has reached a corresponding limit.

Claims

1. A method of arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said method comprising:

a. maintaining a count for each of said modules of a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and

b. transferring at least a unit of data by one of said modules if at least first conditions are satisfied, said first conditions being;

said one module has a request to transfer data on said medium said one module has said token, and each count, of said counts, of all of said modules having priority higher than said one module, has not reached latter said corresponding limit.

2. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:

a. a count register for each of said modules for indicating a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and

b. a logic device for indicating the satisfaction of at least first conditions, said first conditions being;

one module has a request to transfer data on said medium, said one module has said token and each count, of said counts, of all of said modules having priority higher than said one module, has not reached latter said corresponding limit.

3. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:

a. means for maintaining a count for each of said modules of a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where said corresponding latter limit is an integer; and

b. means for indicating that first conditions are satisfied, said first conditions being;

one module has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reached latter said corresponding limit.

4. A method of arbitrating access to a token-based communication medium among a plurality of modules M₁,M₂, . . . , M_n, wherein a token is circulated among said modules on said medium, wherein each of said modules M_i has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said method comprising:

a. maintaining a count c_i for each of said modules M_i of the number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts c₁,c₂, . . . , c_n, where each count c_i is initialized to a value k_i and is changed when a module of lower priority, of said priorities, than module M_i transmits a unit of data each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and

b. transferring at least a unit of data by one of said modules if at least first conditions are satisfied, said first conditions being;

said one module has said token, and each count of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reached its said assigned corresponding limit.

5. A method of arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities,

a. maintaining a count for each of said modules of a number of uses of said medium by lower priority modules, thereby generating a plurality of counts, each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer;

and

b. using said medium by one of said modules by transferring at least a unit of data by any one of said modules if at least first condition are satisfied, said first conditions being;

said one module has a request to transfer data on said medium, said one module has a request to transfer data on said medium, said one module has said token and each count, of all of said modules having priority, of said priorities, higher than said one module, has not reached latter said corresponding limit.

6. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i where i is an integer, thus having a plurality of priorities, said apparatus comprising:

a. a count register for each of said modules for indicating a number of uses of said medium by lower priority modules, thereby generating a plurality of counts, each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer;

b. a logic device for indicating the satisfaction of at least first conditions, said first conditions being;

one of said modules has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reach latter said corresponding limit; and

c. using said medium by said one module when said first conditions are satisfied for said one module.

7. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:

a. means for maintaining a count for each of said modules of a number of uses of said medium by lower priority modules of said modules, thereby generating a plurality of counts;

b. means for indicating that first conditions are satisfied for one of said modules, said first conditions being;

said one module has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority higher than said one module, has not reached a corresponding limit, where each latter said corresponding limit is an integer; and

c. means for using said medium by said one module when said first conditions are satisfied for said one module.

8. A method of arbitrating access to a token-based communication medium among a plurality of modules M₁,M₂, . . . , M_n, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules M_i being assigned a priority i, where i is an integer and i is a higher priority than i+1, said method comprising:

a. maintaining a count c_i for each of said modules M_i of a number of uses of said medium, by lower priority modules of said modules, thereby generating a plurality of counts c_i,c₂, . . . , c_n, where each count c_i is initialized to a value k_i and is changed when a module of lower priority than module M_i transmits a unit of data; and

b. using said medium by one of said modules by transferring at least a unit of data by said one of said modules if at least first conditions are satisfied, said first conditions being;

said one module has said token, and each count of said counts, of all of said modules having priority higher than said one module, has not reached a corresponding limit, where each latter said corresponding limit is an integer.