Data packet scheduler

• US 7,061,865 B2
• Filed: 12/12/2001
• Issued: 06/13/2006
• Est. Priority Date: 03/10/2000
• Status: Active Grant

• 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:
  US10/021,612
• Publication Number:
  US 20020044563A1
• Time in Patent Office: 1,644 Days
• Field of Search: 370/235, 370/229, 370/398, 370/399, 370/395.21, 370/412, 370/230.1, 370/395.4
• US Class Current: 370/235
• 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 system for switching a plurality of data packets, a method comprising:

(a) queuing the plurality of data packets into a plurality of data queues, wherein each of the plurality of data queues corresponds to a value of at least one attribute and wherein each of the plurality of data packets is associated with the at least one attribute;

(b) forming a vector list, wherein each vector is chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queues, the remaining vector value in a null-vector indicating that none of the plurality of data packets is sent into a switching fabric during a corresponding time slot;

(c) assigning different assignment numbers to each member of the vector list;

(d) shuffling the different assignment numbers among members of the vector list;

(e) selecting a vector from the vector list in accordance with a numerical ordering of the different assignment numbers; and

(f) transferring into the switching fabric one of the plurality of data packets from a data queue corresponding to the vector.

2. The method of claim 1, further comprising:

(g) receiving the plurality of data packets at an input port before step (a).

3. The method of claim 1, further comprising:

(g) receiving a serial data stream before step (a); and

(h) converting the serial data stream into the plurality of data packets in response to step (g).

4. The method of claim 1, further comprising:

(g) generating the plurality of data packets before step (a).

5. The method of claim 1, wherein the at least one attribute is chosen from the group consisting of a contention point, a quality of service (QoS), a network that receives a data packet from the system, a higher layer protocol that is being utilized, an address of a destination of the data packet, a port of the destination of the data packet, an address of a source of the data packer, a port of the source of the data packet, a conversion mechanism applied to the data packet, a formation mechanism applied to the data packet, an adaptation mechanism applied to the data packet, and a routing of the data packet.

6. The method of claim 5, wherein the address of the destination and the address of the source comply with an Internet Protocol (IP).

7. The method of claim 5, wherein the adaptation mechanism supports an Asynchronous Transfer Mode (ATM) adaptation layer (AAL).

8. The method of claim 5, wherein a feature of the routing is chosen from the group consisting of a MultiProtocol Label Switching (MPLS) label, a MPLS experimental (EXP) field, an ATM virtual circuit, and an ATM virtual path.

9. The method of claim 5, wherein a mechanism of supporting the QoS is selected from the group consisting of a differentiated service (DiffServ) codepoint and an integrated service (IntServ) class.

10. The method of claim 1, further comprising:

(g) receiving a serial data stream before step (a); and

(h) converting the serial data stream into the plurality of data packets in response to step (g).

11. The method of claim 1, further comprising:

(g) generating the plurality of data packets before step (a).

12. In a system for switching a plurality of packets, a method comprising:

(a) queuing the plurality of data packets into a plurality of data queses, wherein each of the plurality of data queues corresponds to a value of at least one attribute and wherein each of the plurality of data packets is associated with the at least one attribute,

(b) forming a vector list, wherein each vector is chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queries, the remaining vector value is a null-vector indicating that none of the plurality of packets is sent into a switching fabric during a corresponding time slot;

(c) assigning different assignment numbers to each member of the vector list;

(d) assigning different assignment numbers to each member of a timeslot list, wherein each member of the timeslot list corresponds to an assigned timeslot for transporting one of the plurality of data packets;

(e) defining a one-to-one correspondence between the different assignment numbers in the vector list and the different assignment numbers in the timeslot list;

(f) selecting a vector from the vector list comprising;

(i) accessing a member of the timeslot list in accordance with a next timeslot for transport to the switching fabric;

(ii) determining an assignment number associated with the member of the timeslot list; and

(iii) obtaining a vector from a member of the vector list, wherein the assignment number associated with the member of the timeslot list maps to an assignment number associated with the member of the vector list in accordance with the one-to-one correspondence; and

(g) transferring into the switching fabric the one of the plurality of packets from a data queue corresponding to the vector.

13. The method of claim 12, further comprising:

(g) receiving the plurality of data packets at an input port before step (a).

14. In a system for switching a plurality of data packets, a method comprising:

(a) queuing the plurality of data packets into a plurality of data queues, wherein each of the plurality of data queues corresponds to a value of at least one attribute and wherein each of the plurality of data packets is associated with the at least one attribute;

(b) forming a vector list, wherein each vector is chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queues, the remaining vector value is a null-vector indicating that none of the plurality of data packets is sent into a switching fabric during a corresponding time slot;

(c) assigning different assignment numbers to each member of the vector list;

(d) associating second assignment numbers to the different assignment numbers, wherein an ordering of the second assignment numbers is a shuffling of an ordering of the different assignment numbers;

(e) selecting a vector from the vector list in accordance with the ordering of the second assignment numbers; and

(f) transferring into the switching fabric one of the plurality of data packets from a data queue corresponding to the vector.

15. A switching system for switching a plurality of data packets, comprising:

a data buffer that queues the plurality of data packets into a plurality of data queues, each of the plurality of data queues corresponding to a value of at least one attribute and each of the plurality of data packets being associated with the at least one attribute;

a switching fabric;

a memory device that stores a vector list, each vector being chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queries, the remaining vector value being a null-vector indicating that none of the plurality of data packets is sent into the switching fabric during a corresponding time slot; and

a scheduler that;

assigns different assignment numbers to each member of the vector list;

shuffles the different assignment numbers among members of the vector list;

selects a vector from the vector list in accordance with a numerical ordering of the different assignment numbers; and

transfers into the switching fabric one of the plurality of data packets from a data queue corresponding to the vector.

16. A switching system for switching a plurality of data packets, comprising:

a data buffer that queues the plurality of data packets into a plurality of data queues, each of the plurality of data queues corresponding to a value of at least one attribute and each of the plurality of data packets being associated with the at least one attribute;

a switching fabric;

a memory device that stores a vector list, each vector being chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queries, the remaining vector value being a null-vector indicating that none of the plurality of packets is sent into the switching fabric during a corresponding time slot; and

a scheduler that;

assigns different assignment numbers to each member of the vector list;

assigns different assignment numbers to each member of a timeslot list, each member of the timeslot list corresponding to an assigned timeslot for transporting one of the plurality of data packets;

defines a one-to-one correspondence between the different assignment numbers in the vector list and the different assignment numbers in the timeslot list;

selects a vector from the vector list by;

(i) accessing a member of the timeslot list in accordance with a next timeslot for transport to the switching fabric;

(ii) determining an assignment number associated with the member of the timeslot list; and

(iii) obtaining a vector from a member of the vector list the assignment number being associated with the member of the timeslot list mapping to an assignment number associated with the member of the vector list in accordance with the one-to-one correspondence; and

transfers into the switching fabric the one of the plurality of packets from a data queue corresponding to the vector.

17. A switching system for switching a plurality of data packets, comprising:

a data buffer that queues the plurality of data packets into a plurality of data queues, each of the plurality of data queues corresponding to a value of at least one attribute and each of the plurality of data packets being associated with the at least one attribute;

a switching fabric;

a memory device that stores a vector list, each vector being chosen from a set of vectors, each vector save one corresponding to one of the plurality of data queries, the remaining vector value being a null-vector indicating that none of the plurality of data packets is sent into a switching fabric during a corresponding timeslot; and

a scheduler that;

assigns different assignment numbers to each member of the vector list;

associates second assignment numbers to the different assignment numbers, wherein an ordering of the second assignment numbers is a shuffling of an ordering of the different assignment numbers;

selects a vector from the vector list in accordance with the ordering of the second assignment numbers; and

transfers into the switching fabric one of the plurality of data packets from a data queue corresponding to the vector.