Unified network cell scheduler and flow controller

• US 6,058,114 A
• Filed: 05/20/1996
• Issued: 05/02/2000
• Est. Priority Date: 05/20/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Snesrud, Mark, Maffit, Rob, Sethuram, Jay
• Primary Examiner(s): Treat, William M.
• Application Number:
  US08/652,626
• Time in Patent Office: 1,443 Days
• Field of Search: 370/94.2, 370/395, 370/229, 370/230, 370/231, 370/235, 370/236, 370/253, 370/389, 370/391, 370/396, 370/398, 370/399, 370/412, 370/465, 395/880, 709/233, 709/234, 709/235
• US Class Current: 370/397
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention includes a method and apparatus for prioritizing and scheduling ATM cells that are competing for a given time slot for transmission onto a network. A segmentation and reassembly controller establishes a data structure within a memory. The preferable data structure includes a virtual connection time table and a virtual connection parameter table that use linked lists to index to one another. The segmentation and reassembly (SAR) controller includes a sorter for determining the priority of the ATM cells and selecting one for a given time slot and a microcode engine to compute next scheduled time slot and adjust the virtual connection parameter table for a given virtual connection. Coupled to the microcode engine is a random access memory for storing microcode programs so that the SAR may be programmed to prioritize and schedule in a different manner.

Claims

1. A unified scheduler for prioritizing and scheduling a plurality of fixed length communication cells for multiple virtual communication channels of a communication network, the unified scheduler comprising:

a rewritable storage unit for storing schedule times of fixed length communication cells of the multiple virtual communication channels and for storing virtual communication channel parameters used to compute a next scheduled time for a fixed length communication cell, said parameters including a cell delay variation tolerance and an allowed cell period;

a sorter, coupled to the rewritable storage unit, for sorting schedule times and determining the priority of the transmission of the plurality of fixed length communication cells on their respective virtual communication channels and selecting a prioritized fixed length communication cell for transmission;

a programmable microcontroller, coupled to the rewritable storage unit, for computing the next scheduled time from a current time and a virtual communication channel'"'"'s parameters, said programmable microcontroller having a second rewritable storage unit for storing a scheduling and rate adjustment program, said microcontroller computes the next scheduled time by adding the current transmission time with a modified parameter of the allowed cell period to generate an ideal next scheduled time, said modified parameter being generated by said rate adjustment program.

2. The unified scheduler of claim 1 wherein said sorter sorts on the schedule time stored in the rewritable storage unit for determining the priority of transmission of the plurality of fixed length communication cells.

3. The unified scheduler of claim 1 wherein the computation of the next scheduled time is initiated at a time of transmission of the prioritized fixed length communication cell.

4. The unified scheduler of claim 1 wherein said programmable microcontroller modifies, while computing the next scheduled time, the virtual communication channel parameters stored in the rewritable storage unit to reflect the available capacity of the communication network.

5. The unified scheduler of claim 1 wherein said sorter comprises a plurality of stages serially coupled to one another and wherein a stage of said sorter comprises:

a rewritable storage unit for storing a stored value;

a comparitor for comparing an input value with a stored value and generating a comparison output; and

a multiplexor, coupled to the comparitor and the rewritable storage unit, for selecting between the input value and the stored value as storage into said rewritable storage unit and as an output from the stage.

6. The unified scheduler of claim 5 wherein said stage of said sorter further comprises a second rewritable storage unit for storing a stored communication identification;

a second multiplexor, coupled to the second rewritable storage unit, for selecting between an input communication identification and the stored communication identification as storage into said second rewritable storage unit and as a second output from the stage.

7. The unified scheduler of claim 1 wherein said programmable microcontroller adds the ideal next scheduled time with the cell delay variation tolerance to generate an expiration time, said expiration time being used to prioritize cell scheduling.

8. The unified scheduler of claim 1 wherein said programmable microcontroller subtracts the cell delay variation tolerance from the ideal next scheduled time to generate a maturation time, said maturation time being used to determine cell transmission eligibility.

9. The unified scheduler of claim 1 wherein

said means of computing the next scheduled time has a counter for maintaining the current time.

10. A network interface communication controller for controlling the flow of fixed length communication cells over a communication channel, comprising;

a rewritable storage for sorting parameters, a priority and an identity of the communication channel;

a segmentation and reassembly (SAR) controller, coupled to a system bus, a network transmission link, a network receiving link and the rewritable storage, for prioritizing and scheduling the flow of fixed length communication cells by analyzing the parameters and the priority of the communication channel and selecting a channel with the highest priority for scheduling, said parameters including a cell delay variation delay tolerance (CDVT) and an allowed cell period (ACP), said priority being an expiration time computed by adding the cell delay variation tolerance to an ideal next scheduled time, said ideal next scheduled time being computed by adding a modified parameter, allowed cell period, to a current transmission time, said modified parameter being generated by a rate adjustment program.

11. The network interface communication controller of claim 10 wherein

said rewritable storage uses linked lists to store the priority and identity of the communication channel.

12. The network interface communication controller of claim 10 wherein said segmentation and reassembly (SAR) controller analyzes a communication channel having a first priority with a first sorter.

13. The network interface communication controller of claim 10 wherein said segmentation and reassembly (SAR) controller analyzes a communication channel having a second priority with a second sorter.

14. The network interface communication controller of claim 10 wherein

said rewritable storage has a first partition for storing a list of communication channels having the first priority and a second partition for storing a list of communication channels having the second priority.

15. A segmentation and reassembly (SAR) controller for controlling the flow of fixed length communication cell over a communication path and channel of a communication network, the SAR controller comprising:

a system bus interface for coupling to a system bus and communicating to a host system;

a storage controller, for coupling to a rewritable storage having scheduled times and virtual communication channel parameters data stored therein, addressing the rewritable storage, and reading the data from and writing the data into the rewritable storage;

a network output interface for coupling to a transmission cabling of the network;

a network input interface for coupling to receiving cabling of the network;

a segmenter, coupled to the system bus interface, the memory controller, and the network output interface, for segmenting data into prioritized fixed length communication cells;

a scheduler coupled to the segmenter and the memory controller, having a sorter and a microcode engine for sorting and scheduling the prioritized fixed length communication cells for transmission out to the network based on the scheduled times and virtual communication channel parameters, said microcode engine computes the next scheduled time by adding the current transmission time with the modified parameter of the allowed cell period to generate an ideal next scheduled time, said modified parameter being generated by a rate adjustment program, said ideal next scheduled time being used to compute an expiration time and a maturation time;

a reassembler, coupled to the system bus interface, the memory controller, and the network input interface, for removing the header from the prioritized fixed length communication cells and reassembling them into usable data, the reassembler further comprising;

a DMA controller coupled to the system bus interface for communicating user data onto the system bus, and

a network feedback logic coupled to the network input interface for reading the prioritized fixed length communication cells received from the network and adjusting the sorting and scheduling of the prioritized fixed length communication cells by the scheduler.

16. The segmentation and reassembly (SAR) controller of claim 15 wherein

said scheduler utilizes linked list data structures to store scheduling information.

17. The segmentation and reassembly (SAR) controller of claim 16 wherein

said scheduler includes a second sorter for sorting and scheduling the prioritized fixed length communication cells having a second priority and generating linked lists addresses for the storage controller.

18. A method of prioritizing and scheduling the flow of fixed length communication cells over a communication channel of a communication network, the steps comprising:

a) computing a priority value for a fixed length communication cell based on communication channel parameters, said priority value being an expiration time computed by adding a cell delay variation tolerance to an ideal next scheduled time, said ideal next scheduled time being computed by adding a modified allowed cell period to a current transmission time, said modified allowed cell period being computed by a rate adjustment program;

b) storing the priority value and an identifier of the fixed length communication cell into a rewritable storage unit;

c) sorting on the priority value of the fixed length communication cell to determine the cell having the highest priority;

d) selecting the fixed length communication cell having the highest priority for transmission over the communication channel of the communication network; and

e) repeating steps (a) through (d).

19. The method of prioritizing and scheduling the flow of fixed length communication cells of claim 18, further comprising the step of:

rescheduling when steps (a) through (d) should be repeated utilizing virtual communication channel parameters.

20. A scheduler for sorting and scheduling the flow of fixed length communication cell over a communication path and channel of a communication network, the scheduler comprising:

a) a microcode engine which includes a scheduling and rate adjustment program and which computes the next scheduled time by adding the current transmission time with a modified parameter of the allowed cell period to generate an ideal next scheduled time, said modified parameter being generated by said rate adjustment program;

b) a sorter for determining the priority of a fixed length cell for transmission onto a communication network and for selecting said cell for transmission as a function of its priority.

21. The scheduler of claim 20 wherein said priority is a function of an expiration time, said expiration time computed by adding a cell delay variation tolerance to said ideal next scheduled time, and wherein said microcode engine also computes a maturation time equal to the sum of said ideal next scheduled time and the cell delay variation tolerance, said maturation time being used by said scheduler to determine eligibility of transmission of the plurality of fixed length communication cells onto the network.