US 6,674,721 B1 · Method and apparatus for scheduling packets being sent from a component of a packet switching system

Abstract

Methods and apparatus are disclosed for determining the order to send information arriving at the inputs of a packet switching system. A line card maintains its own data structure indicating flow control information and a queue for each destination it is sending data with its memory. Control logic then controls the placing of the incoming data into these queues and for taking the data out of the queues and sending the data, typically in the form of packets, to the packet switch. As information arrives at a line card, priority outgoing packet time slots are allocated for that destination. In this manner, each destination is given the opportunity to send information at its arrival rate. In the remaining bandwidth or packet cycles available on the outgoing link, the destination queues containing information retained due to a congestion condition are serviced.

Claims38

Dependent claims

A method comprising:

maintaining a data structure indicating flow control information for a plurality of destinations;
receiving an item to be routed to a particular one of the plurality of destinations;
placing the item in a first queue corresponding to the particular destination;
placing an identifier of the particular destination or the first queue in a second queue only if the particular destination is determined to not be congested;
removing the identifier from the second queue;
determining whether or not the particular destination is indicated as congested in the data structure;
and
sending the item to the particular destination.

5 more elements

A method performed by a packet switching system including a plurality of destinations including at least a congested state and a non-congested state, the method comprising:

maintaining a flow control data structure;
maintaining a destination queue for each of the plurality of destinations;
maintaining a server queue;
receiving a plurality of items to be routed to the plurality of destinations;
placing each of the plurality of items in its respective destination queue of said destination queues;
and placing an indication corresponding to said respective destination or said respective destination queue in the server queue;
and
determining whether or not the server queue is empty;
in response to said determining that the server queue is not empty;
removing a first indication from the server queue, determining whether or not a particular destination corresponding to the first indication is not in the congested state as indicated in the flow control data structure, and if the particular destination is determined not to be in the congested state, removing a first item from a particular queue corresponding to the particular destination, and sending the first item to the particular destination;
and in response to determining that the server queue is empty, identifying a next destination queue of said destination queues with a corresponding destination indicated as not in the congested state in the flow control data structure, and sending a corresponding packet from the next destination queue to the corresponding destination.

8 more elements

A computer-readable medium containing computer-executable instructions for performing steps for use in a packet switching system including a plurality of destinations including at least a congested state and a non-congested state, said steps comprising:

maintaining a flow control data structure;
maintaining a destination queue for each of the plurality of destinations;
maintaining a server queue;
receiving a plurality of items to be routed to the plurality of destinations;
placing each of the plurality of items in its respective destination queue of said destination queues;
placing an indication corresponding to said respective destination or said respective destination queue in the server queue;
and
determining whether or not the server queue is empty;
in response to said determining that the server queue is not empty:
removing a first indication from the server queue, determining whether or not a particular destination corresponding to the first indication is not in the congested state as indicated in the flow control data structure, and if the particular destination is determined not to be in the congested state, removing a first item from a particular queue corresponding to the particular destination, and sending the first item to the particular destination;
and in response to determining that the server queue is empty, identifying a next destination queue of said destination queues with a corresponding destination indicated as not in the congested state in the flow control data structure, and sending a corresponding packet from the next destination queue to the corresponding destination.

8 more elements

A method comprising:

maintaining a data structure indicating flow control information for a plurality of destinations;
receiving a plurality of items, each of the plurality of items to be routed to a corresponding destination of the plurality of destinations, and for each received item of the plurality of items, performing operation (a) and (b) as follows:
(a) placing said received item in a particular destination queue of a plurality of destination queues, the particular destination queue associated with a particular destination of said received item;
and
(b) determining whether the particular destination of said received item is congested based on the data structure indicating flow control information, and, placing an identifier corresponding to the particular destination or the particular destination queue in a server queue;
and
repeatedly identifying whether or not said server queue is empty;
and in response to said each said identifying operation, performing either (c) or (d) as follows:
(c) in response to said server queue being identified as not empty:
removing a particular identifier from the server queue;
determining whether an identified destination of the plurality of destinations corresponding to the identifier is congested based on the data structure indicating flow control information, and if the identified destination is not indicated as congested, causing a corresponding identified item to be sent from one of the plurality of destination queues;
and
(d) in response to said server queue being identified as empty, identifying a stored item in one of the plurality of destination queues whose corresponding destination is identified in the data structure as not being congested, and causing the stored item to be sent.

10 more elements

A computer-readable medium containing computer-executable instructions for performing steps, said steps comprising:

maintaining a data structure indicating flow control information for a plurality of destinations;
receiving a plurality of items, each of the plurality of items to be routed to a corresponding destination of the plurality of destinations, and for each received item of the plurality of items, performing operation (a) and (b) as follows:
(a) placing said received item in a particular destination queue of a plurality of destination queues, the particular destination queue associated with a particular destination of said received item;
and
(b) determining whether the particular destination of said received item is congested based on the data structure indicating flow control information, and, placing an identifier corresponding to the particular destination or the particular destination queue in a server queue;
and
repeatedly identifying whether or not said server queue is empty;
and in response to said each said identifying operation, performing either (c) or (d) as follows:
(c) in response to said server queue being identified as not empty:
removing a particular identifier from the server queue;
determining whether an identified destination of the plurality of destinations corresponding to the identifier is congested based on the data structure indicating flow control information, and if the identified destination is not indicated as congested, causing a corresponding identified item to be sent from one of the plurality of destination queues;
and
(d) in response to said server queue being identified as empty, identifying a stored item in one of the plurality of destination queues whose corresponding destination is identified in the data structure as not being congested, and causing the stored item to be sent.

10 more elements

An apparatus comprising:

means for maintaining a data structure indicating flow control information for a plurality of destinations;
means for receiving a plurality of items, each of the plurality of items to be routed to a corresponding destination of the plurality of destinations;
means for performing operation (a) and (b) for each received item of the plurality of items as follows:
(a) placing said received item in a particular destination queue of a plurality of destination queues, the particular destination queue associated with a particular destination of said received item;
and
(b) determining whether the particular destination of said received item is congested based on the data structure indicating flow control information, and, placing an identifier corresponding to the particular destination or the particular destination queue in a server queue;
and
means for repeatedly identifying whether or not said server queue is empty;
and
means for performing either (c) or (d) in response to said each said identifying operation as follows:
(c) in response to said server queue being identified as not empty:
removing a particular identifier from the server queue;
determining whether an identified destination of the plurality of destinations corresponding to the identifier is congested based on the data structure indicating flow control information, and if the identified destination is not indicated as congested, causing a corresponding identified item to be sent from one of the plurality of destination queues;
and
(d) in response to said server queue being identified as empty, identifying a stored item in one of the plurality of destination queues whose corresponding destination is identified in the data structure as not being congested, and causing the stored item to be sent.

12 more elements

Dependencies are inferred from the claim text.

Method and apparatus for scheduling packets being sent from a component of a packet switching system

Life of this patent

Method and apparatus for scheduling packets being sent from a component of a packet switching system

Life of this patent

Abstract

Claims38