Methods and apparatus for fairly arbitrating contention for an output port

A hierarchical arbitration system comprising:

• a) at least two leaf layer arbiters, each of the at least two leaf layer arbiters including
• i) at least two inputs for accepting local request signals,
• ii) at least two outputs for providing local grant signals,
• iii) a further output for providing a group request signal, and
• iv) a further input for receiving a group grant signal;
• and
• b) a root arbiter including
• i) inputs for accepting the group request signal from each of the at least two leaf layer arbiters, and
• ii) outputs for providing the group grant signals to each of the at least two leaf layer arbiters.

In a system defining a number N, where N is an integer greater than 1, of hierarchical arbitration layers, where a first layer is the lowest layer of the hierarchy, a method for arbitrating requests, the method comprising steps of:

• a) initializing a layer index to the first layer;
• b) at the first layer, accepting request signals;
• c) incrementing the layer index;
• d) determining whether or not the layer index equals the number N;
• e(1) if the layer index does not equal the number N,
• i) grouping the accepted request signals and defining a group request signal for each group;
• and
• e(2) if the layer index is equal to the number N,
• i) determining grant signals,
• ii) decrementing the layer index,
• iii) determining internal grant signals,
• iv) determining grant signals by combining an associated one of the grant signals from the next higher layer with each of the internal grant signals, and
• v) determining whether the layer index is 1,
• vi(a) if the layer index is 1, terminating the process, and
• vi(b) if the layer index is not 1, repeating steps e(2)(ii) through e(2)(vi).

In a system defining a number N, where N is an integer greater than 1, of hierarchical arbitration layers, where a first layer is the lowest layer of the hierarchy, a method for arbitrating requests, the method comprising steps of:

• a) initializing a layer index to the first layer;
• b) at the first layer, accepting request signals;
• c) incrementing the layer index;
• d) determining whether or not the layer index equals the number N;
• e(1) if the layer index does not equal the number N,
• i) grouping the accepted request signals and defining a group request signal for each group;
• and
• e(2) if the layer index is equal to the number N,
• i) determining grant signals,
• ii) decrementing the layer index,
• iii) determining internal grant signals,
• iv) determining whether the layer index is 1, and
• v(a) if the layer index is 1, updating the internal grant signals by combining each of them with associated grant signals from the N−1 higher layer(s) of the hierarchy, and
• v(b) if the layer index is not 1, repeating steps e(2) (ii) through e(2) (v).

An arbitration system for handling up to four requests, the arbitration system comprising:

• a) four inputs for accepting request signals;
• b) a fifth input for accepting a group grant signal;
• c) four outputs for providing grant signals;
• d) a fifth output for providing a group request signal;
• e) a first arbiter having
• i) two inputs for accepting request signals from a first two of the four inputs for accepting request signals,
• ii) two outputs for providing grant signals to a first two of the four outputs for providing grant signals,
• iii) an third input coupled with the fifth input for accepting the group grant signal, and
• iv) a fourth input for accepting a second group grant signal;
• f) a second arbiter having
• i) two inputs for accepting request signals from a second two of the four inputs for accepting request signals,
• ii) two outputs for providing grant signals to a second two of the four outputs for providing grant signals,
• iii) an third input coupled with the fifth input for accepting the group grant signal, and
• iv) a fourth input for accepting a third group grant signal;
• g) a third arbiter having
• i) two inputs, each for accepting a grouped request signal,
• ii) a third input coupled with the fifth input for accepting the group grant signal,
• iii) a first output coupled with the fourth input of the first arbiter, and
• iv) a second output coupled with the fourth input of the second arbiter;
• h) a first logical OR element having
• i) four inputs, each coupled with a respective one of the four inputs for accepting request signals, and
• ii) an output coupled with the fifth output for providing a group request signal;
• i) a second logical OR element having
• i) two inputs, each coupled with a respective one of the first two of the four inputs for accepting request signals, and
• ii) an output coupled with a first one of the two inputs of the third arbiter;
• and
• j) a third logical OR element having
• i) two inputs, each coupled with a respective one of the second two of the four inputs for accepting request signals, and
• ii) an output coupled with a second one of the two inputs of the third arbiter.

An M-by-N switch, where N is an integer greater than one and M is another integer greater than one, the M-by-N switch comprising:

• a) M input port controllers for receiving incoming cells;
• b) N output port controllers for receiving outgoing cells;
• c) N hierarchical arbitration systems, each the N hierarchical arbitration systems being associated with one of the N output ports and having
• i) at least two leaf layer arbiters, each of the at least two leaf layer arbiters including
• A) at least two inputs for accepting local request signals,
• B) at least two outputs for providing local grant signals,
• C) a further output for providing a group request signal, and
• D) a further input for receiving a group grant signal;
• and
• ii) a root arbiter including
• A) inputs for accepting the group request signal from each of the at least two leaf layer arbiters, and
• B) outputs for providing the group grant signals to each of the at least two leaf layer arbiters;
• and
• d) switching fabric including M rows and N columns of crosspoints, wherein each of the M rows is associated with one of the M input port controllers, wherein each of the N columns is associated with one of the N output port controllers and one of the N hierarchical arbitration systems.

An xM-by-N switch, where N is an integer greater than one, x is another integer greater than one, and M is yet another integer greater than one, the xM-by-N switch comprising:

• a) xM input port controllers for receiving incoming cells;
• b) N output port controllers for receiving outgoing cells;
• c) xN hierarchical arbitration systems, each x the xN hierarchical arbitration systems being associated with one of the N output ports, and each of the xN hierarchical arbitration systems having
• i) at least two leaf layer arbiters, each of the at least two leaf layer arbiters including
• A) at least two inputs for accepting local request signals,
• B) at least two outputs for providing local grant signals,
• C) a further output for providing a group request signal, and
• D) a further input for receiving a group grant signal;
• and
• ii) a root arbiter including
• A) inputs for accepting the group request signal from each of the at least two leaf layer arbiters, and
• B) outputs for providing the group grant signals to each of the at least two leaf layer arbiters;
• d) N row arbiters, each of the N row arbiters receiving request signals from x associated hierarchical arbitration systems and providing grant signals to the x associated hierarchical arbitration systems;
• and
• e) switching fabric including xM rows and N columns of crosspoints, wherein each of the xM rows is associated with one of the xM input port controllers, wherein each of the N columns is associated with one of the N output port controllers and one of the N row arbiters.

An N-request arbitration system for handling cells which may have one of P priority levels, the arbitration system comprising:

• a) P hierarchical arbitration systems, each of the P hierarchical arbitration systems being associated with a priority level and having
• i) at least two leaf layer arbiters, each of the at least two leaf layer arbiters including
• A) at least two inputs for accepting local request signals,
• B) at least two outputs for providing local grant signals,
• C) a further output for providing a group request signal, and
• D) a further input for receiving a group grant signal;
• and
• ii) a root arbiter including
• A) inputs for accepting the group request signals from each of the at least two leaf layer arbiters,
• B) outputs for providing the group grant signals to each of the at least two leaf layer arbiters, and
• C) means for combining the group request signals to generate a priority group request;
• b) a priority selection device having inputs for receiving P priority group request from the P hierarchical arbitration systems and having P outputs for providing a priority grant signal to each of the P hierarchical arbitration systems;
• and
• c) N, P-input OR gates, each of the N, P-input OR gates having an associated one of its P inputs coupled with an associated one of N grant signals from an associated one of the P hierarchical arbitration systems.