Non-consecutive data readout scheduler

• US 6,343,066 B2
• Filed: 03/09/2001
• Issued: 01/29/2002
• Est. Priority Date: 03/10/2000
• Status: Expired due to Term

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Benson, Kent Daniel, Magill, Robert Bradford, Hrabik, Terry Jon
• Primary Examiner(s): Jung, Min
• Application Number:
  US09/802,389
• Publication Number:
  US 20010048690A1
• Time in Patent Office: 326 Days
• Field of Search: 370/229, 370/230, 370/232, 370/235, 370/412, 370/415, 370/416, 370/418, 709/232, 709/235
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Data switching systems for use in ATM and other packet and cell switching networks can more smoothly switch data if incoming data packets to be switched are re-ordered to avoid overwhelming an output port with too many consecutive packets to a particular destination. An apparatus and method for simply re-ordering data samples in a non-consecutive manner is computationally efficient and effective.

Claims

1. In a switching system having a plurality of input ports and a plurality of contention points in a switch fabric, a method of ordering input data packets into a switching system fabric comprised of the steps of:

a. receiving at an input port a number of input data packets, each requiring transfer through at least one of said switch fabric contention points;

b. queuing each input data packet into one or more data queues where each data queue contains packets destined for a particular switch fabric contention point through which each said data packet is to be transferred by said switch fabric;

c. forming a T-member list of vectors, where each vector is chosen from a set of vector values, each vector value save one corresponding to one of the said one or more data queues;

the remaining vector value is a null-vector indicating that no-packet is sent into the switch fabric during the corresponding slot;

d. assigning to each of said T members of said list, a k-bit binary ordinal number between 0 and T−

1, where k=log₂(T);

e. for each member of said list, assigning thereto a k-bit reverse binary number valued between zero and T−

1 corresponding to the vectors in the list;

f. beginning with the vector assigned the reverse binary value zero and ending with the vector assigned reverse binary number T−

1, transferring a data packet into said switch fabric from the data queue corresponding to said vector.

2. The method of claim 1 wherein said step of queuing data packets includes the step of first segmenting data packets into fixed length internal packets.

3. The method of claim 1 wherein said step of queuing data packets includes the step of storing data packets in random access memory.

4. The method of claim 1 wherein said step of forming a T-member list of vectors comprises the formation of a data structure, where each vector is chosen from a set of different-valued vectors, each vector save one corresponding to one of the said data queues;

the remaining vector is a null-vector indicating that no packet is sent into the switch fabric during the corresponding slot.

5. The method of claim 1 wherein said step of assigning reverse binary numbers is comprised of reversing the binary digits of said k-bit binary-valued ordinal numbers assigned to said members of said list.

6. The method of claim 1 wherein the contention points are the links from the switch fabric to the output ports.

7. The method of claim 1 wherein all vectors in the T-member list are grouped so that vectors pointing to the same contention point are assigned consecutive binary ordinal numbers.

8. The method of claim 1 wherein the step of transferring the data packets into the switch fabric comprises the steps of:

i. forming a plurality of parallel processing blocks, wherein each of said blocks corresponds to a said vector and contains the ordinal numbers occupied by the vector in the said assignment list;

ii. determining a reverse binary number correspond ing to a time slot, said time slot one of a plurality of time slots numbered consecutively from 0 to T−

1;

iii. sending said reverse binary number to each of said processing blocks;

iv. determining, for each processing block, if said reverse binary number corresponds to said ordinal number assigned to said vector of said processing block from said assignment list;

v. transferring a data packet into said switch fabric from said data queue corresponding to the said vector indicated by said processing block.

9. A switching system having a plurality of input ports, each of which receives data packets, and one or more contention points through which data packets are transferred via a switching fabric, comprised of:

a. an input port at which data packets from a plurality of sources are received, each data packet requiring transfer through at least one of said one or more contention points via said switching fabric;

b. a data buffer comprised of at least T storage locations into which data packets from said plurality of sources are stored and queued into at least one or more data queues where each queue contains packets destined for a particular switch fabric contention point through which each of said data packets are to be transferred;

c. a memory device storing an assignment list of T elements, each element in the list consisting of a vector pointing to one of said one or more data queues, each element of said list being enumerated by an ordinal k-bit binary number, where k=log₂(T), ranging in value from zero to T−

1 and further being enumerated by a k-bit reverse binary number ranging in value from zero to T−

1, said reverse binary number being determined by reversing the binary digits of said ordinal k-bit binary number;

d. beginning with the element assigned the reverse binary value zero and ending with the element assigned reverse binary number T−

1, reading the vector in the element location and transferring a data packet into said switch fabric from the data queue corresponding to said vector.

10. The switching system of claim 9 wherein said memory device is comprised of random access memory.

11. The switching system of claim 9 wherein said data buffer first segments data packets into fixed length internal packets.

12. The switching system of claim 9 wherein said data buffer is a storage device comprised of random access memory.

13. The switching system of claim 9 wherein the contention points are the links from the switch fabric to the output ports.

14. The switching system of claim 9 wherein all vectors in the T-member list are grouped so that vectors pointing to the same contention point reside as elements assigned consecutive binary ordinal numbers.

15. The switching system of claim 9 wherein said data packets are asynchronous transfer mode data packets.

16. The switching system of claim 9 wherein the step of transferring the data packet into the switch fabric comprises the steps of:

i. forming a plurality of parallel processing blocks, wherein each of said blocks corresponds to a said vector and contains the ordinal numbers occupied by the vector in the said assignment list;

ii. determining a reverse binary number corresponding to a time slot;

iii. sending said reverse binary number to each of said processing blocks;

iv. determining, for each processing block, if said reverse binary number corresponds to said ordinal number assigned to said vector of said processing block from said assignment list;

v. transferring a data packet into said switch fabric from said data queue corresponding to the said vector indicated by said processing block.

17. A switching system having input ports and a plurality of one or more contention points in the switch fabric, a method of ordering input data packets into a switching system fabric comprised of the steps of:

a. receiving at an input port a number of input data packets, each requiring transfer through said switch fabric contention points;

b. queuing each input data packet into one of at least one or more data queues where each data queue contains packets destined for a particular switch fabric contention point through which each said data packet is to be transferred by said switch fabric;

c. forming a T-member list of elements, where each element in the list consists of a queue of vectors chosen from a set of different vector values, each vector value save one corresponding to each of said data queues;

the remaining vector value is a null-vector indicating that no internal packet is sent into the switch fabric during the corresponding slot;

d. assigning to each of said T elements of said list, a k-bit binary ordinal number between 0 and T−

1, where k=log₂(T);

e. for each element of said list, assigning thereto a k-bit reverse binary number valued between zero and T−

1 corresponding to the vectors in the list;

f. beginning with the element assigned the reverse binary value zero and ending with the element assigned reverse binary number T−

1, transferring the vectors queued in the list element to an output vector queue for the switch fabric input link;

g. choosing one vector for the output vector queue and transferring a data packet into said switch fabric from the data queue corresponding to said vector.

18. The method of claim 17 wherein said step of queuing data packets includes the step of first segmenting data packets into fixed length internal packets.

19. The method of claim 17 wherein said step of queuing data packets includes the step of storing data packets in random access memory.

20. The method of claim 17 wherein said step of forming a T-member list of elements comprises the formation of a data structure, where each element in the list consists of a queue of vectors chosen from a set of different-valued vectors, each vector save one corresponding to one of the said data queues;

the remaining vector is a null-vector indicating that no packet is sent into the switch fabric during the corresponding slot.

21. The method of claim 17 wherein said step of queuing vectors in an output vector queue includes the step of storing vectors in random access memory.

22. The method of claim 17 wherein the contention points are the links between the switch fabric and the output ports.

23. The method of claim 17 wherein all vectors in the T-member list are grouped so that vectors pointing to the same contention point reside in elements assigned consecutive binary ordinal numbers.

24. The switching system of claim 17 wherein said data packets are asynchronous transfer mode data packets.

25. The switching system of claim 17 wherein the step of transferring the data packet into the switch fabric comprises the steps of:

i. forming a plurality of parallel processing blocks, wherein each of said blocks corresponds to a said vector and contains the ordinal numbers occupied by the vector in the said assignment list;

ii. determining a reverse binary number corresponding to a time slot;

iii. sending said reverse binary number to each of said processing blocks;

iv. determining, for each processing block, if said reverse binary number corresponds to said ordinal number assigned to said vector of said processing block from said assignment list;

v. queing said vectors from said processing blocks into said output vector queue.