Scheduler design for ATM switches, and its implementation in a distributed shared memory architecture

• US 5,959,993 A
• Filed: 09/13/1996
• Issued: 09/28/1999
• Est. Priority Date: 09/13/1996
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Varma, Subir, Daniel, Thomas
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/714,005
• Time in Patent Office: 1,110 Days
• Field of Search: 370/389, 370/397, 370/412, 370/428, 370/413-418, 370/445, 370/229, 370/230, 370/235, 370/351, 370/352, 370/395, 370/396, 370/399, 370/400, 370/411, 370/409, 370/419 , 370/444, 370/455, 370/468, 340/825.5, 340/825.51, 340/825.52
• US Class Current: 370/397
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/107 using shared medium
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

A cell scheduler for a distributed shared memory switch architecture including a controller for scheduling transmissions of cells from output queues of the switch structure pursuant to one of several different scheduling modes. The controller receives a mode selection input, segregates the output queues into groups, assigns priority rankings to the groups, and applies one of scheduling disciplines at each group of output queues as determined by the mode selection input and the priority rankings. The groups of output queues include a group of per-Virtual Channel (VC) queues and at least one group of First In-First Out (FIFO) queues. The scheduling disciplines include a Weighted Fair Queuing (WFQ) scheduling discipline applied by the controller at the group of per-VC queues and a Round Robin (RR) scheduling discipline applied by the controller at the at least one group of FIFO queues. The priority rankings comprising a highest priority ranking which is assigned to the group of per-VC queues.

Claims

1. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the group of output queues comprising a group of per-virtual-channel queues and at least one group of first-in-first-out queues;

the plurality of scheduling disciplines comprising a weighted-fair-queuing scheduling discipline applied by the controller at the group of per-virtual-channel queues and a round-robin scheduling discipline applied by the controller at the at least one group of first-in-first-out queues;

the priority rankings comprising a highest priority ranking; and

the group of per-virtual-channel queues being assigned the highest priority ranking.

2. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the plurality of scheduling disciplines including a weighted-fair-queuing scheduling discipline applied by the controller at the group of per-virtual-channel queues.

3. The cell scheduler of claim 2 wherein the priority rankings comprise a highest priority ranking, and the group of per-virtual-channel queues are assigned the highest priority ranking.

4. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the plurality of scheduling disciplines including a round-robin scheduling discipline applied by the controller at the group of first-in-first-out queues.

5. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the controller scheduling transmissions of cells from the per-virtual-channel queues such that a virtual channel associated with a particular cell does not share a sub-queue with another virtual channel.

6. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the controller scheduling transmissions of cells from the per-virtual-channel queues such that a virtual channel associated with a particular cell shares a sub-queue with another virtual channel.

7. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to each groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the controller scheduling transmissions of cells from the first-in-first-out queues such that a virtual channel associated with a particular cell does not share a sub-queue with another virtual channel.

8. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the controller scheduling transmissions of cells from the first-in-first-out queues such that a virtual channel associated with a particular cell shares a sub-queue with another virtual channel.

9. A cell scheduler for a distributed shared memory switch architecture, the cell scheduler comprising:

a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues and three groups of first-in-first-out queues; and

the plurality of scheduling disciplines including a weighted-fair-queuing scheduling discipline applied by the controller at the group of per-virtual-channel queues and a round-robin scheduling discipline applied by the controller at the groups of first-in-first-out queues.

10. The cell scheduler of claim 9 wherein the priority rankings comprise a highest priority ranking, and the group of per-virtual-channel queues are assigned the highest priority ranking.

11. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the plurality of scheduling disciplines including a weighted-fair-queuing scheduling discipline applied by the controller at the group of per-virtual-channel queues.

12. The chip set of claim 11 wherein the priority rankings including a highest priority ranking, and the group of per-virtual-channel queues are assigned the highest priority ranking.

13. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the plurality of scheduling disciplines including a round-robin scheduling discipline applied by the controller at the group of first-in-first-out queues.

14. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the controller scheduling transmissions of cells from the per-virtual-channel queues such that a virtual channel associated with a particular cell does not share a sub-queue with another virtual channel.

15. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues; and

the controller scheduling transmissions of cells from the per-virtual-channel queues such that a virtual channel associated with a particular cell shares a sub-queue with another virtual channel.

16. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the controller scheduling transmissions of cells from the first-in-first-out queues such that a virtual channel associated with a particular cell does not share a sub-queue with another virtual channel.

17. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of first-in-first-out queues; and

the controller scheduling transmissions of cells from the first-in-first-out queues such that a virtual channel associated with a particular cell shares a sub-queue with another virtual channel.

18. A chip set including a cell scheduler for a distributed shared memory switch architecture, the chip set comprising:

a plurality of output queues;

a controller for scheduling transmissions of cells from the output queues pursuant to one of a plurality of scheduling modes, receiving a mode selection input, segregating the output queues into groups of output queues, assigning priority rankings to the groups, and applying one of a plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings;

the groups of output queues including a group of per-virtual-channel queues and three groups of first-in-first-out queues; and

the plurality of scheduling disciplines including a weighted-fair-queuing scheduling discipline applied by the controller at the group of per-virtual-channel queues and a round-robin scheduling discipline applied by the controller at the groups of first-in-first-out queues.

19. The chip set of claim 18 wherein the priority rankings comprise a highest priority ranking, and the group of per-virtual-channel queues are assigned the highest priority ranking.

20. A method of manufacturing a cell scheduler for a distributed shared memory switch architecture, the method comprising the steps of:

(a) providing a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes, including a weighted-fair-queuing scheduling discipline and a round-robin scheduling discipline;

(b) providing the controller with a mode selection input; and

(c) employing the controller to segregate the output queues into groups, assign priority rankings to the groups, and apply one of the plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings.

21. A method of manufacturing a cell scheduler for a distributed shared memory switch architecture, the method comprising the steps of:

(a) providing a controller for scheduling transmissions of cells from output queues of the switch architecture pursuant to one of a plurality of scheduling modes;

(b) providing the controller with a mode selection input; and

(c) employing the controller to segregate the output queues into groups including a group of per-virtual-channel queues and a group of first-in-first-out queues, assign priority rankings to the groups, and apply one of the plurality of scheduling disciplines at each of the groups as determined by the mode selection input and the priority rankings.