Multiplex communications – Channel assignment techniques – Arbitration for access to a channel
Reexamination Certificate
1999-02-23
2002-08-06
Marcelo, Melvin (Department: 2663)
Multiplex communications
Channel assignment techniques
Arbitration for access to a channel
Reexamination Certificate
active
06430194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of digital data processing systems, and more particularly, to the field of networks wherein units of the network are connected to a high speed bus requiring arbitration for access and data transfer.
2. Discussion of the Related Art
As is well known in the art, as computer networks have grown in size and complexity, the need for high speed data transfer has increased. Among the types of data transfer devices which provide high speed transport between shared resources, such as bridges or switches, is the use of a high speed shared channel or bus. With such an arrangement, network efficiency and utilization is strongly affected by the procedure for controlling access to the high speed bus or channel.
As is also known, in general a transmission of data between two units over a high speed bus or channel requires two steps, since more than one unit has the capability of originating a transmission. The first step is for the transmitting unit to obtain control of the bus for some more or less defined interval. Once the selection step is completed, a second (or transfer) step is used to complete the transfer that is controlled by the selected transmitting unit.
Obtaining control of the bus requires contending with other units desiring bus access, to arbitrate and determine which one will be selected. As is known in the art, there are two principal generic approaches to arbitration. These are central arbitration and distributed arbitration. In the central arbitration approach, a single, central priority circuit or device receives all the requests for bus access and determines which requesting unit at any given time should be accorded the greatest priority and allowed to use the bus. Once the unit is selected, it is allowed to control the bus and effect the transfer. By contrast, in distributed arbitration, each unit connected to a bus is assigned a specific priority and each unit individually determines whether it has sufficient priority to obtain control of the bus when it desires to do so. If a unit of higher priority simultaneously seeks bus access, a device of lower priority must wait until some later time when it is the highest priority requester.
As is also known, in choosing a method of arbitration, fairness is assured when each unit connected to the bus has substantially equal average priority for obtaining bus access. One such approach to guaranteeing fairness is a primitive round robin method. With such a method, for each unit, two delay interval possibilities exist; the delay selection for each unit is switched from time to time, on a round-robin basis, such that all units are given equal average priority.
In today's networks, data of more than one protocol may also coexist and be transferred from unit to unit in the network via the high speed bus. Examples of different protocols are Ethernet, FDDI, and Asynchronous Transfer Mode (ATM). Therefore, a method of arbitration is required that will not only guarantee fairness, but one that can handle data of both similar and different protocols.
SUMMARY OF THE INVENTION
In accordance with one embodiment of the present invention, a method of granting bus access to one of first and second modules seeking control of a common bus, includes assigning a first module priority level to the first module; assigning a second module priority level to the second module; assigning a first arbitration number to the first module and assigning a second arbitration number to the second module. When the first and second module priority levels are not the same, bus access is granted to the module having a higher priority module priority level. When the first and second module priority levels are the same, it is determined whether one of the first and second modules has been previously granted bus access and is asserting a new request and the other has been waiting its turn bus access is granted to the module that has been waiting its turn. Finally, when the first and second priority levels are the same and each of the first and second modules has been waiting its turn, the first and second arbitration numbers are compared and access is granted to the module with a higher arbitration priority arbitration number.
Additionally, the present invention provides a method of granting bus access to one of first and second modules seeking control of a common bus, including assigning a first module priority level to the first module; assigning a second module priority level to the second module; assigning a first arbitration number to the first module and assigning a second arbitration number to the second module.
When the first and second module priority levels are not the same, bus access is granted to the module having a higher priority module priority level. When the first and second module priority levels are the same, it is determined whether one of the first and second modules has been previously granted bus access and is asserting a new request and the other has been waiting its turn bus access is granted to the module that has been waiting its turn. Additionally, when the first and second module priority levels are the same and each of the first and second modules has been waiting its turn, comparing the first and second arbitration numbers are compared and access is granted to the module with a higher arbitration priority arbitration number.
Additionally, the present invention provides an apparatus for granting bus access to one of first and second modules seeking control of a common bus, the first module having a first module priority level and a first arbitration number assigned to it and the second module having a second module priority level and a second arbitration number assigned to it. The apparatus includes a first circuit that grants bus access to the module having a higher priority module priority level when the first and second module priority levels are not the same; a second circuit that determines, when the first and second module priority levels are the same, whether one of the first and second modules has been previously granted bus access and is asserting a new request and the other has been waiting its turn and then grants bus access to the module that has been waiting its turn; and a third circuit that compares, when the first and second module priority levels are the same and each of the first and second modules has been waiting its turn, the first and second arbitration numbers and then grants access to the module with a higher arbitration priority arbitration number.
REFERENCES:
patent: 3611305 (1971-10-01), Greenspan et al.
patent: 4463445 (1984-07-01), Grimes
patent: 5072363 (1991-12-01), Gallagher
patent: 5109379 (1992-04-01), Kume et al.
patent: 5119292 (1992-06-01), Baker et al.
patent: 5282272 (1994-01-01), Guv et al.
patent: 5301333 (1994-04-01), Lee
patent: 5487170 (1996-01-01), Bass et al.
patent: 5594733 (1997-01-01), Katoen et al.
patent: 5689657 (1997-11-01), Desor et al.
patent: 5796732 (1998-08-01), Mazzola et al.
patent: 0159592 (1985-10-01), None
patent: 2287621 (1995-09-01), None
Ilyadis Nicholas
Tiffany William J.
Enterasys Networks Inc.
Kwoh Jasper
Marcelo Melvin
Wolf Greenfield & Sacks P.C.
LandOfFree
Method and apparatus for arbitrating bus access amongst... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for arbitrating bus access amongst..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for arbitrating bus access amongst... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905264