Granted Patent B2

US 7,680,124 · App. 10/903,954 · Granted Mar 16, 2010

Abstract

Claims (75)

1. A processing device for use in a communication system, the device comprising:

scheduling circuitry configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing at least a weight table and a mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

the scheduling circuitry being further configured to determine a particular transmission element to be scheduled in a given timeslot by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table; and

memory circuitry associated with the scheduling circuitry and configurable to store at least a portion of at least one of the weight table and the mapping table;

wherein the scheduling circuitry utilizes the resultant value, determined by accessing a corresponding mapping table entry, to identify a first entry of the weight table that is larger than or equal to the resultant value, said entry of the weight table identifying a particular one of the transmission elements.

2. The processing device of claim 1 wherein the weight table associates each of the transmission elements with one or more of the timeslots of the frame.

3. The processing device of claim 1 wherein the weight table includes a total number of entries equivalent to a total number of the timeslots in the frame.

4. The processing device of claim 1 wherein each of the transmission elements has a weight associated therewith.

5. The processing device of claim 4 wherein a sum of the weights for the plurality of transmission elements is equal to a size of the frame.

6. The processing device of claim 1 wherein the weight table is stored in a compressed format.

7. The processing device of claim 6 wherein the weight table in the compressed format includes a total number of entries equivalent to a total number of the plurality of transmission elements.

8. A processing device for use in a communication system, the device comprising:

scheduling circuitry configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing at least a weight table and a mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

the scheduling circuitry being further configured to determine a particular transmission element to be scheduled in a given timeslot by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table; and

memory circuitry associated with the scheduling circuitry and configurable to store at least a portion of at least one of the weight table and the mapping table;

wherein the weight table is stored in a compressed format; and

wherein the weight table in the compressed format includes a total number of entries equivalent to one less than a total number of the plurality of transmission elements.

9. A processing device for use in a communication system, the device comprising:

scheduling circuitry configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing at least a weight table and a mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

the scheduling circuitry being further configured to determine a particular transmission element to be scheduled in a given timeslot by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table; and

memory circuitry associated with the scheduling circuitry and configurable to store at least a portion of at least one of the weight table and the mapping table;

wherein the weight table is stored in a compressed format; and

wherein an i-th entry of the weight table stores a value given by

∑

j

=

1

i

⁢

W

j

-

1

,

where W 1 denotes a weight of a transmission element identified by the j-th entry of the weight table and where i>1.

10. The processing device of claim 9 wherein the scheduling circuitry utilizes the resultant value, determined by accessing a corresponding mapping table entry, to identify a first entry of the compressed weight table that is larger than or equal to the resultant value, said entry of the compressed weight table identifying a particular one of the transmission elements.

11. The processing device of claim 1 wherein entries of the mapping table are predetermined in accordance with a golden ratio policy.

12. A processing device for use in a communication system, the device comprising:

scheduling circuitry configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing at least a weight table and a mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

the scheduling circuitry being further configured to determine a particular transmission element to be scheduled in a given timeslot by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table; and

memory circuitry associated with the scheduling circuitry and configurable to store at least a portion of at least one of the weight table and the mapping table;

wherein entries of the mapping table are predetermined in accordance with a golden ratio policy; and

wherein the entries of the mapping table are determined by:

utilizing a golden ratio φ to compute

G i =( i*φ −1 ),

for a given range of index values i;

sorting the computed values in a specified order; and

taking the entries as a sequence of subscript indices.

13. The processing device of claim 1 wherein the scheduling circuitry generates entries of the mapping table as needed in accordance with a bit-reverse policy.

14. The processing device of claim 13 wherein a given entry of the mapping table is determined by computing a bit-reverse value of a corresponding timeslot number.

15. The processing device of claim 1 wherein each of the weight table entries comprises an identifier of one of the transmission elements.

16. The processing device of claim 1 wherein the memory circuitry comprises at least one of internal memory and external memory of the processing device.

17. The processing device of claim 1 wherein one or more of the data blocks comprise data packets.

18. The processing device of claim 1 wherein the processing device comprises a network processor integrated circuit configured to provide an interface for data block transfer between a network and a switch fabric.

19. A method for use in a processing device of a communication system, the method comprising:

storing at least a portion of at least one of a weight table and a mapping table in a memory coupled to a processor; and

scheduling by the processor data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing the weight table and the mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

wherein a particular transmission element to be scheduled in a given timeslot is determined by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table;

wherein the resultant value, determined by accessing a corresponding mapping table entry, is utilized to identify a first entry of the weight table that is larger than or equal to the resultant value, said entry of the weight table identifying a particular one of the transmission elements.

20. An integrated circuit comprising:

a processing device having scheduling circuitry configured to schedule data blocks for transmission from a plurality of transmission elements in timeslots of a frame, utilizing at least a weight table and a mapping table;

the weight table comprising a plurality of entries, each of the entries identifying a particular one of the transmission elements;

the mapping table comprising at least one entry specifying a mapping between a particular timeslot of the frame and an entry of the weight table;

the scheduling circuitry being further configured to determine a particular transmission element to be scheduled in a given timeslot by accessing a corresponding mapping table entry and utilizing a resultant value to access the weight table;

wherein the scheduling circuitry utilizes the resultant value, determined by accessing a corresponding mapping table entry, to identify a first entry of the weight table that is larger than or equal to the resultant value, said entry of the weight table identifying a particular one of the transmission elements.

Assignments (8)