US 6,807,187 B1Granted

Method and apparatus for determining a next round robin element using a cascaded approach

AssigneeCisco Technology, Inc.

InventorDalit Sagi

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and apparatus are disclosed for determining a next round robin element requesting service using a cascaded approach. The cascaded approach could be implemented in numerous ways, including, inter alia, a circuit or in software, and be used, inter alia, in a network or computer system. In one implementation, a first stage of the cascaded implementation is divided into multiple groups, each of the multiple groups receives an indication of elements requesting service. Based on a last round robin result and its address, each of the multiple groups determines a candidate for the next result. In the situation where the last result was in a group and the group has a requesting element subsequent in the round robin sequence, that next requesting element is selected and forced to be the selected next result. Otherwise, this processing is repeated by subsequent stages to determine the round robin result. One implementation selects a next result from 4096 requesting inputs within a single clock period using three sixteen input cascaded stages.

Claims7

Dependent claims

A cascaded circuit to identify a next element in a round robin sequence, the cascaded circuit comprising:

a plurality of first stage components configured to receive an indication of a starting position and to receive a plurality of indication signals of elements requesting selection, the elements requesting selection being a subset of a plurality of elements which may request selection, each of the plurality of first stage components including an identification circuit to identify one of the plurality of requesting elements to a second stage component;
the second stage component, coupled to the plurality of first stage components, configured to receive an indication of the starting position and to receive servicing request indications from the plurality of first stage components, the second stage component including a selection circuit to select the next element from among the elements requesting selection identified as identified by said servicing request indications;
wherein the identification circuit includes a find first one sub-circuit, a round robin sub-circuit, and a selection device to select between the find first one sub-circuit and the round robin sub-circuit;
wherein the round robin sub-circuit includes masking circuitry and a second find first one sub-circuit.

1 more element

Dependencies are inferred from the claim text.