Event-driven cell scheduler and method for supporting multiple service categories in a communication network

• US 5,793,747 A
• Filed: 03/14/1996
• Issued: 08/11/1998
• Est. Priority Date: 03/14/1996
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Kline, Richard
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/616,147
• Time in Patent Office: 880 Days
• Field of Search: 370/395, 370/412-413, 370/415, 370/414, 370/229, 370/230-235, 370/429, 370/428, 370/416, 370/418, 370/417
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling

Abstract

The event scheduler (100; 200) and method (300) of the present invention solve the problem of mixing multiple service categories on the same physical link or media by utilizing a calendar queue scheduling method (i.e., based on prior actual transmission times of previous packets). The event-driven cell scheduler is, for example used in an asynchronous transfer mode ATM network and may, for example, be embodied in software, hardware and firmware.

Claims

1. A method for scheduling transmission times for a plurality of packets on an outgoing link for a communication network, comprising the steps of:

A) enqueuing, by a memory controller, the packets in a plurality of per connection data queues in at least one packet memory, wherein each queue has a queue ID;

B) notifying, by the memory controller, at least one multiservice category scheduler, where a data queue is empty immediately prior to the memory controller enqueuing the packets, that a first arrival has occurred;

C) calculating, by a calculation unit of the multiservice category scheduler, using service category and present state information associated with a connection stored in a per connection context memory, an earliest transmission time, TIME EARLIEST and an updated PRIORITY INDEX and updating and storing present state information in a per connection context memory;

D) generating, by the calculation unit, a "task" wherein the task includes;

D1) the queue ID;

D2) the TIME EARLIEST; and

D3) the PRIORITY INDEX;

E) inserting the task into one of at least a first calendar queue;

F) storing, by the calendar queue, at the calculated TIME EARLIEST, the task in one of a plurality of priority task queues;

G) removing, by a priority task decoder, at a time equal to or greater than TIME EARLIEST in accordance with a time opportunity, the task from the priority task queue and generating a request to the memory controller;

H) dequeueing the packet by the memory controller and transmitting the packet;

I) notifying, by the memory controller, where more packets remain to be transmitted, the multiservice category scheduler that the per connection queue is unempty;

J) calculating, by the calculation unit, an updated TIME EARLIEST and an updated PRIORITY INDEX based on service category and present state information associated with the connection, and updating and storing present state information in the per connection context memory;

K) generating, where the per connection queue is unempty, a new task using the updated TIME EARLIEST, by the calculation unit, for the connection and returning to step E, and otherwise, where the per connection queue is empty, waiting for the notification by the memory controller and returning to step C.

2. The method of claim 1 wherein the step of enqueuing the packets includes determining whether to enqueue/discard a packet in accordance with a predetermined scheme for, where at least one source malfunctions, maintaining a predetermined quality of service for other sources.

3. The method of claim 2 wherein the predetermined scheme includes one of:

A) discarding a packet where a maximum queue length specified by a threshold is exceeded by storing the packet in a queue; and

B) discarding the packet in accordance with a predetermined selective scheme.

4. The method of claim 1 including, for constant bit rate, CBR, packet traffic in a packet switch, in step J, updating TIME EARLIEST using a predetermined function of the negotiated traffic parameters for the connection, the present value of the real time clock TIME NOW and state information associated with the connection that is stored in the per connection context memory.

5. The method of claim 1 wherein, for CBR packet traffic in a packet switch, including the steps of:

A) in step C, on first packet arrival, where a TIME NOW is greater than TIME EARLIEST, updating TIME EARLIEST equal to TIME NOW, where TIME NOW is an output of a real time clock, and storing updated TIME EARLIEST in a per connection context memory and

B) in step J, updating TIME EARLIEST to TIME EARLIEST plus packet period, where packet period is a reciprocal of a predetermined peak packet rate and storing updated TIME EARLIEST in the per connection context memory.

6. The method of claim 1 wherein, for UBR packet traffic in a packet switch, including the steps of:

A) in step C, on first packet arrival, where a TIME NOW is greater than TIME EARLIEST, updating TIME EARLIEST equal to TIME NOW, where TIME NOW is an output of a real time clock, and storing updated TIME EARLIEST in a per connection context memory and

B) in step J, updating TIME EARLIEST to TIME NOW plus packet period, where packet period is a reciprocal of a predetermined peak packet rate and storing updated TIME EARLIEST in the per connection context memory.

7. The method of claim 1 wherein, for available bit rate, ABR, packet traffic in a packet switch, the following steps are included:

A) in step J, updating TIME EARLIEST using a predetermined function of the negotiated traffic parameters for the connection, a present value of a real time clock TIME NOW and associated predetermined state information that is stored in the per connection context memory;

B) in step J, using a predetermined algorithm, such as a leaky bucket algorithm, to determine if the actual transmission packet rate at the output of the packet multiplexer is falling below the negotiated minimum packet rate, MCR, for the connection; and

C) in step J, setting the PRIORITY INDEX to one of at least two different priority levels as a predetermined function of the actual packet rate determined in step B.

8. The method of claim 1 wherein, for ABR packet traffic in a packet switch, including the steps of:

A) in step C, on first packet arrival, where a TIME NOW is greater than TIME EARLIEST,

A1) updating TIME EARLIEST equal to TIME NOW, where TIME NOW is an output of a real time clock, and storing updated TIME EARLIEST in a per connection context memory and

A2) setting a RESET FLAG to TRUE in a per connection context memory;

B) in step J,

B1) one of B1a-B1b;

B1a) where RESET FLAG is equal to TRUE, setting RESET FLAG to FALSE and setting THRESHOLD equal to TIME EARLIEST plus {a predetermined constant times a reciprocal of a predetermined minimum packet rate} in the per connection context memory; and

B1b) where RESET FLAG is equal to FALSE, setting THRESHOLD equal to THRESHOLD plus a reciprocal of a predetermined minimum packet rate;

B2) updating TIME EARLIEST to TIME NOW plus packet period, where packet period is a reciprocal of a peak packet rate and storing updated TIME EARLIEST in the per connection context memory; and

B3) where notified in step I that a per connection packet queue was unempty,

B3a) where TIME NOW is greater than THRESHOLD, setting the PRIORITY INDEX to a value indicating a high priority ABR task queue;

B3b) where TIME NOW is less than or equal to THRESHOLD,

B3b1) setting the PRIORITY INDEX to a value indicating a normal priority ABR task queue; and

B3b2) where THRESHOLD is greater than TIME NOW plus {a predetermined constant multiplied by a reciprocal of a predetermined minimum packet rate}, setting THRESHOLD equal to TIME NOW plus {the constant multiplied by the reciprocal of the predetermined minimum packet rate}.

9. The method of claim 1 wherein, for variable bit rate, VBR, packet traffic in a packet switch, the following steps are included:

A) in step J, using a predetermined algorithm to determine whether the actual transmission packet rate at the output of the packet multiplexer falls below a negotiated sustainable packet rate, SCR, for the connection,

B) in step J, using a predetermined algorithm to determine whether an actual transmission packet rate at an output of the packet multiplexer is exceeding a burst limit, MBS, for the connection;

C) in step J, updating TIME EARLIEST using a predetermined function of negotiated traffic parameters for the connection, a present value of a real time clock TIME NOW, outputs of steps A and B above, and predetermined associated state information for the connection that is stored in the per connection context memory;

D) in step J, setting the PRIORITY INDEX to one of at least two different priority levels as a predetermined function of the actual transmission packet rate at the output of the packet multiplexer determined in steps A and B.

10. The method of claim 1 wherein, for VBR packet traffic in a packet switch, including the steps of:

A) in step C, on first packet arrival, where a TIME NOW is greater than TIME EARLIEST,

A1) updating TIME EARLIEST equal to TIME NOW, where TIME NOW is an output of a real time clock, and storing updated TIME EARLIEST in a per connection context memory and

A2) setting a RESET FLAG to TRUE in a per connection context memory;

B) in step J,

B1) one of B1a-B1b;

B1a) where RESET FLAG is equal to TRUE,

B1a1) setting RESET FLAG to FALSE and

B1a2) setting THRESHOLD equal to TIME EARLIEST plus {a predetermined constant times a reciprocal of a predetermined sustainable packet rate} in the per connection context memory;

B1a3) and where a theoretical transmission time TTT is less than TIME NOW, setting TTT=TIME NOW; and

B1b) where RESET FLAG is equal to FALSE, setting THRESHOLD equal to THRESHOLD plus a predetermined reciprocal of the predetermined sustainable packet rate;

B2) updating TIME EARLIEST to TIME NOW plus packet period, where packet period is a reciprocal of a peak packet rate and storing updated TIME EARLIEST in the per connection context memory; and

B3) where notified in step I that a per connection packet queue was unempty,

B3a) updating TTT to a value of TTT plus the reciprocal of the sustainable packet rate and storing the updated TTT in the per connection context memory;

B3b) one of B3b1-B3b2;

B3b1) where TIME NOW is greater than THRESHOLD, setting the PRIORITY INDEX equal to a value indicating a high priority VBR task queue;

B3b2) where TIME NOW is less than or equal to THRESHOLD,

B3b2a) setting the PRIORITY INDEX equal to value indicating a normal priority VBR task queue;

B3b2b) where THRESHOLD is greater than TIME NOW plus a predetermined constant times a reciprocal of a predetermined sustainable packet rate, setting THRESHOLD equal to TIME NOW plus a predetermined constant times a reciprocal of a predetermined sustainable packet rate, and

B3b2c) where TIME EARLIEST is less than TTT minus a predetermined maximum burst size constant TMBS, setting TIME EARLIEST equal to TMBS.

11. The method of claim 1 wherein priority decoding includes one of:

A) utilizing a set of priority task queues and a head of line priority decoder/demultiplexer at the output of the task queues;

B) utilizing a set of priority task queues and a priority decoder/demultiplexer arranged to provide a combination of head of line priority and weighted round robin queuing disciplines.

12. A method for scheduling transmission of a packet, the method comprising the steps of:

determining, upon receipt of said packet, a corresponding per-connection queue for said packet;

determining, upon determination of the corresponding per-connection queue, whether said per-connection queue is empty;

generating, upon determination that said per-connection queue is empty, a request for scheduling said packet;

calculating at least a desired execution time and a priority for said request;

storing said request until at least the desired execution time; and

storing said request in one of a plurality of priority queues corresponding to the priority calculated for the request.

13. The method of claim 12 further comprising the step of:

selecting one request for each of a plurality of cell transmission times from among a number of requests stored in the plurality of priority queues.

14. The method of claim 13 further comprising the steps of:

retrieving, upon selecting a request, a corresponding packet from its corresponding per-connection queue;

determining, upon retrieving the corresponding packet from its corresponding per-connection queue, whether said per-connection queue is non-empty; and

generating, upon determination that said per-connection queue is non-empty, a request for scheduling a next packet from said per-connection queue.

15. An event scheduler for scheduling transmission times for a plurality of packets, the event scheduler receiving a request for each packet to be scheduled, the event scheduler comprising:

a priority queue for each of a plurality of priorities supported by the event scheduler;

logic for calculating at least a desired execution time and a priority for each request; and

a real time task scheduler, responsive to a real time clock, for determining when the real time clock is at least equal to the desired execution time of a request and, upon said determination, for storing said request in a corresponding priority queue.

16. The event scheduler of claim 15 further comprising:

a cell clock for signaling each successive cell transmission time; and

a decoder/MUX, responsive to the cell clock, for selecting one request for each cell transmission time from among the requests stored in the plurality of priority queues.

17. The event scheduler of claim 16 wherein the selected request corresponds to the request stored at the head of the highest priority non-empty priority queue.

18. An apparatus for scheduling transmission times for a plurality of packets, the apparatus comprising:

a per-connection queue for each of a plurality of connections supported by the apparatus;

logic for determining, upon receipt of each packet, a corresponding perconnection queue for said packet;

logic for determining, upon determination of the corresponding per-connection queue, whether said per-connection queue is empty;

logic for generating, upon determination that said per-connection queue is empty, a request for scheduling said packet;

logic for calculating at least a desired execution time and a priority for said request;

logic for storing said request until at least the desired execution time; and

logic for storing said request in one of a plurality of priority queues corresponding to the priority calculated for the request.

19. The apparatus of claim 18 further comprising:

logic for selecting, for each cell transmission time, one request from a number of requests stored in the plurality of priority queues.

20. The apparatus of claim 19 further comprising:

logic for retrieving, upon selecting a request, a corresponding packet from its corresponding per-connection queue;

logic for determining, upon retrieving the corresponding packet from its corresponding per-connection queue, whether said per-connection queue is non-empty; and

logic for generating, upon determination that said per-connection queue is non-empty, a request for scheduling a next packet from said per-connection queue.

21. An apparatus comprising a computer usable medium having computer readable program code means embodied therein for scheduling transmission times for a plurality of packets, the computer readable program code means comprising:

computer readable program code means for determining, upon receipt of each packet, a corresponding per-connection queue for said packet;

computer readable program code means for determining, upon determination of the corresponding per-connection queue, whether said per-connection queue is empty;

computer readable program code means for generating, upon determination that said per-connection queue is empty, a request for scheduling said packet;

computer readable program code means for calculating at least a desired execution time and a priority for said request;

computer readable program code means for storing said request until at least the desired execution time; and

computer readable program code means for storing said request in one of a plurality of priority queues corresponding to the priority calculated for the request.

22. The apparatus of claim 21 further comprising:

computer readable program code means for selecting one request for each of a plurality of cell transmission times from among a number of requests stored in the plurality of priority queues.

23. The apparatus of claim 22 further comprising:

computer readable program code means for retrieving, upon selecting a request, a corresponding packet from its corresponding per-connection queue;

computer readable program code means for determining, upon retrieving the corresponding packet from its corresponding per-connection queue, whether said per-connection queue is non-empty; and

computer readable program code means for generating, upon determination that said per-connection queue is non-empty, a request for scheduling a next packet from said per-connection queue.