Large capacity, multiclass core ATM switch architecture

• US 6,324,165 B1
• Filed: 09/05/1997
• Issued: 11/27/2001
• Est. Priority Date: 09/05/1997
• Status: Expired due to Term

• Current Assignee: Ciena Corporation
• Original Assignee: NEC USA (NEC Corporation)
• Inventors: Mark, Brian L., Ramamurthy, Gopalakrishnan, Fan, Ruixue
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): YAO, KWANG BIN
• Application Number:
  US08/923,978
• Time in Patent Office: 1,544 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/238, 370/252, 370/253, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/465, 710/52, 710/57
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A large capacity ATM core switch architecture is disclosed, which supports multiple traffic classes and quality-of-service (QoS) guarantees. The switch supports both real-time traffic classes with strict QoS requirements, e.g., CBR and VBR, and non-real-time traffic classes with less stringent requirements, e.g., ABR and UBR. The architecture also accommodates real-time and non-real-time multicast flows in an efficient manner. The switch consists of a high-speed core module that interconnects input/output modules with large buffers and intelligent scheduling/buffer management mechanisms. The scheduling can be implemented using a novel dynamic rate control, which controls internal congestion and achieves fair throughput performance among competing flows at switch bottlenecks. In the dynamic rate control scheme, flows are rate-controlled according to congestion information observed at bottleneck points within the switch. Each switch flow is guaranteed a minimum service rate plus a dynamic rate component which distributes any unused bandwidth in a fair manner.

Claims

1. An ATM switch capable of supporting streams of different classes having various quality of service requirements, comprising:

a core switch comprising;

a TDM bus;

a plurality of input ports connected to said TDM bus;

a plurality of output buffers connected to said TDM bus;

a plurality of output ports connected to respective output buffers; and

a multicast output buffer connected to each of said output ports;

a plurality of input modules connected to input side of said core switch, each of said input modules comprising;

a plurality of output port planes corresponding to the number of said output ports, each of said output port planes having a plurality of input buffers;

an input module scheduler for scheduling cells in said input buffers;

a plurality of output modules connected to output side of said core switch, each of said output modules comprising;

a plurality of output line planes, each having a plurality of output line buffers coupled to an output line;

an output module scheduler for scheduling cells in said output buffers.

2. The ATM switch of claim 1, wherein each of said output buffers of said core switch comprises overflow control for generating a shape signal when level of cells in a respective output buffer reaches a first threshold, and generating a stop signal when the level of cells in the respective output buffer reaches a second threshold.

3. The ATM switch of claim 1, further comprising:

connection admission control for issuing queue timestamps for each cell in said plurality of input buffers;

a timer issuing a current time; and

,

wherein said input module scheduler further comprises a comparator for comparing said queue timestamps to said current time, and scheduling eligibility for service each of said cells having queue timestamp equal to current time.

4. The ATM switch of claim 3, wherein each of said input module scheduler and output module scheduler further comprises:

a timestamp storage unit for storing the queue timestamps and providing said queue timestamps to said comparator;

a virtual rate shaping unit connected to said comparator for shaping transmission rate of cells eligible for service;

a plurality of virtual queue counters for counting the number of cells eligible for service;

a service scheduling unit for scheduling cells eligible for service;

a compute engine for dynamically updating the timestamps.

5. The ATM switch of claim 4, further comprising a rate feedback from said output modules to said input modules.

6. The ATM switch of claim 1, wherein said plurality of output buffers of said core switch are designated real-time output buffers and wherein said core switch further comprises:

a plurality of non-real-time output buffers corresponding to the number of real-time output buffers and each connected to one of said output ports;

a non-real-time multicast buffer connected to each of said output ports.

7. An ATM switch capable of supporting cell streams of different classes having various quality of service requirements, comprising:

a core switch comprising;

a TDM bus;

a plurality of input ports connected to said TDM bus;

a plurality of output buffers connected to said TDM bus;

a plurality of output ports connected to respective output buffers; and

a multicast output buffer connected to each of said output ports;

a plurality of output modules connected to output side of said core switch, each of said output modules having a plurality of output lines and comprising;

a plurality of output line planes, each having a plurality of output line buffers coupled to said output lines;

an output module scheduler for scheduling cells in said output buffers;

a plurality of input modules connected to input side of said core switch, each of said input modules comprising;

a plurality of output port planes corresponding to the number of said output ports, each of said output port planes having a plurality of output line planes corresponding to the number of said output lines, each of said output line planes having a plurality of input buffers;

an input module scheduler for scheduling cells in said input buffers.

8. The ATM switch of claim 7, wherein each of said output buffers of said core switch comprises overflow control for generating a shape signal when level of cells in a respective output buffer reaches a first threshold, and generating a stop signal when the level of cells in the respective output buffer reaches a second threshold.

9. The ATM switch of claim 7, further comprising:

connection admission control for issuing queue timestamps for each cell in said plurality of input buffers;

a timer issuing a current time; and

,

wherein said input module scheduler further comprises a comparator for comparing said queue timestamps to said current time, and scheduling eligibility for service each of said cells having queue timestamp equal to current time.

10. The ATM switch of claim 9, wherein each of said input module scheduler and output module scheduler further comprises:

a timestamp storage unit for storing the queue timestamps and providing said queue timestamps to said comparator;

a virtual rate shaping unit connected to said comparator for shaping transmission rate of cells eligible for service;

a plurality of virtual queue counters for counting the number of cells eligible for service;

a service scheduling unit for scheduling cells eligible for service;

a compute engine for dynamically updating the timestamps.

11. The ATM switch of claim 10, further comprising a rate feedback from said output modules to said input modules.

12. The ATM switch of claim 7, wherein said plurality of output buffers of said core switch are designated real-time output buffers and wherein said core switch further comprises:

a plurality of non-real-time output buffers corresponding to the number of real-time output buffers and each connected to one of said output ports;

a non-real-time multicast buffer connected to each of said output ports.

13. An ATM switch capable of supporting streams of different classes having various quality of service requirements, comprising:

a core switch comprising;

a TDM bus;

a plurality of input ports connected to said TDM bus;

a plurality of output buffers connected to said TDM bus;

a plurality of output ports connected to respective output buffers;

a plurality of input modules connected to input side of said core switch, each of said input modules comprising;

a plurality of input buffers;

a connection admission control assigning a minimum guaranteed rate and an excess share weight for each of said input buffers;

an input module scheduler for scheduling cells in said input buffers according to a rate composed of said minimum guaranteed rate and a share of the available unused bandwidth, said share being proportional to the excess share weight.

14. The ATM switch of claim 13, further comprising a closed-loop controller for adjusting the available unused bandwidth according to cell occupancy of said output buffers.

15. The ATM switch of claim 14, further comprising an overload control for transmitting a shape rate signal from any of said output buffers whenever cell occupancy of a respective one of said output buffers reaches a predetermined shape threshold, and wherein said scheduler is responsive to said shape signal to schedule said input buffers according to the guaranteed minimum rate only.

16. A tripled buffered ATM switch capable of supporting streams of different classes having various quality of service requirements, comprising:

a plurality of input buffers for queuing incoming cell streams;

a plurality of core buffers receiving queued cells of said cell streams from said input buffers and providing said queued cell to respective output ports;

a plurality of output buffers receiving said queued cells from said output ports and providing said queued cell to respective output lines;

a scheduler for scheduling transmission of said queued cells from said input buffers;

a first feedback loop from said core buffers to said scheduler, for transmission of load information of said core buffers to said scheduler;

a second feedback loop from said output buffers to said scheduler, for transmission of load information of said output buffers to said scheduler;

wherein said scheduler schedules transmission of said queued cells from said input module according to information received from said first and second feedback loops.

17. The tripled buffered ATM switch according to claim 16, further comprising a connection admission control for assigning a minimum guaranteed rate to said cell streams, and wherein said scheduler schedules said queued cells at the input buffers at a rate not less than said minimum guaranteed rate.

18. The tripled buffered ATM switch according to claim 17, wherein said scheduler schedules said queueds at the input buffers according to a dynamic rate which comprises the minimum guaranteed rate plus a distribution of an unused bandwidth determined from the information of said first and second feedback loops.

19. The tripled buffered ATM switch according to claim 18, wherein said connection admission control further assigns queue timestamps to each of said queues, and wherein said scheduler further comprises a comparator for comparing the queue timestamps to current time and defining each queue having a queue timestamp equal to or less than the current time as eligible for service.

20. A scheduler for an ATM switch, comprising:

a first memory for storing cells timestamps assigned to cells in queues to be scheduled;

a second memory for storing actual queue load;

a third memory for storing cells in virtual queues;

a current time generator generating current time;

a plurality of comparators for comparing the cells timestamps to current time and designating cells having cell timestamps≧

current time as eligible for service;

a virtual rate selector for assigning cells from said eligible cells to said virtual queues;

a service scheduling selector which selects queues for service from said virtual queues;

a compute engine for scheduling and rescheduling cells in said first memory.

21. A buffer, comprising:

a first monitoring circuit for monitoring a load level in said buffer and for generating a shape signal when said load level reaches a first threshold, so as to cause input to said buffer to be reduced to a minimum level, and further for generating a stop signal when said load level reaches a second threshold, so as to halt any input to said buffer.

22. The buffer of claim 21, further comprising an estimation circuit for estimating an unused bandwidth available on said buffer and generating a signal indicating said estimated bandwidth.

23. A scheduler for an ATM switch, comprising:

a first memory for storing queue timestamps assigned to queues to be scheduled;

a second memory for storing actual queue load;

a third memory for storing cells in virtual queues;

a current time generator generating current time;

a plurality of comparators for comparing the queue timestamps to current time and designating queues having cell timestamps≦

current timestamp as eligible for service;

a virtual rate selector for assigning cells from said eligible cells to said virtual queues;

a service scheduling selector which selects queues for service from said virtual queues;

a compute engine for scheduling and rescheduling cells in said first memory.