ATM switching element and method having independently accessible cell memories

• US 5,583,861 A
• Filed: 04/28/1994
• Issued: 12/10/1996
• Est. Priority Date: 04/28/1994
• Status: Expired due to Term

• Current Assignee: PMC-Seirra, Inc.
• Original Assignee: Integrated Telecom Technology, Inc. (Microchip Technology Incorporated)
• Inventors: Holden, Brian D.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/235,006
• Time in Patent Office: 957 Days
• Field of Search: 370/60, 370/60.1, 370/61, 370/85.6, 370/94.1
• US Class Current: 370/395.42
• CPC Class Codes: H04J 2203/0071 Monitoring
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

An ATM switching system architecture of a switch fabric-type is built of, a plurality of ATM switch element circuits and routing table circuits for each physical connection to/from the switch fabric. A shared pool of memory is employed to eliminate the need to provide memory at every crosspoint. Each routing table maintains a marked interrupt linked list for storing information about which ones of its virtual channels are experiencing congestion. This linked list is available to a processor in the external workstation to alert the processor when a congestion condition exists in one of the virtual channels. The switch element circuit typically has up to eight 4-bit-wide nibble inputs and eight 4-bit-wide nibble outputs and is capable of connecting cells received at any of its inputs to any of its outputs, based on the information in a routing tag uniquely associated with each cell.

Claims

1. A switch element comprising:

a plurality of input interfaces for receiving cells of data;

a plurality of output interfaces for transmitting cells of data;

a shared pool memory comprised of a plurality of cell memories, wherein each cell memory can be connected to any available input interface and to any available output interface and wherein a cell memory can always be connected to an available output interface without being blocked by other cell memories being output to other output interfaces;

an input crosspoint circuit capable of connecting each of said plurality of input interfaces to any one of said plurality of cell memories, without being blocked by cells from other input interfaces being simultaneously stored in any other cell memory location;

an output crosspoint circuit for connecting each of said plurality of cell memories to any available one of said output interfaces, without being blocked by cells stored in other cell memory locations being output to other output interfaces, and;

controller means for controlling which of said inputs is connected to which of said cell memories and for controlling which of said outputs is connected to which of said cell memories.

2. The device according to claim 1 wherein said controller means further comprises:

a linked-list random access memory;

a set of multipriority queues for each of said output interfaces each one of said queues in said set residing in said random access memory and comprising;

a connection address;

a queue priority identifier; and

a first-in/first-out linked list of identifiers to said cell memories in said shared pool memory.

3. The device according to claim 1 wherein there are eight input interfaces each capable of receiving four-bit wide nibbles and eight output interfaces each capable of transmitting four-bit wide nibbles and wherein the shared pool memory is comprised of 32 cell memories.

4. The device according to claim 3 wherein there are five multipriority queues for each of said eight output interfaces making a total of 40 multipriority queues.

5. The device according to claim 2 wherein each of said multipriority queues when active represents one connection through a switch fabric, said connection defined as connecting one data transmitter to one data receiver at a specified priority over a determined and fixed path in said switch fabric.

6. In a switch element comprising a plurality of input interfaces, a plurality of output interfaces, a shared pool memory having a plurality of cell memories wherein each cell memory can be connected to an available input interface and an available output interface without being blocked by other cells in the shared pool accessing other input or output interfaces, a controller, and means responsive to the controller for connecting any of said input interfaces and any of said output interfaces to any one of said cell memories, a method for switching a cell of data from any input interface to any output interface comprising the steps of:

receiving the cell of data over one input interface and storing the cell in a cell memory designated by said controller for that input interface;

using the controller to examine a tag portion of said cell, said tag portion identifying the output interface to which the cell must be directed;

using the controller to enqueue the cell by adding an identifier for the cell memory in which the cell has been stored to a linked list;

using the controller to dequeue the cell when its desired output is available by connecting the cell memory in which the cell is stored to the cell'"'"'s desired output interface wherein said cell is available without regard for the location of said cell in said shared pool cell memory; and

transmitting the cell over its desired output interface.

7. The method according to claim 6 further capable of sending to one output interface cells of data having different priorities further comprising the steps of:

using the controller to examine said tag portion of said cell, said tag portion additionally identifying the priority at which the cell is being transmitted;

using the controller to enqueue the cell at its appropriate priority by adding an identifier for the cell memory in which the cell has been stored to a linked list having a specified priority; and

using the controller to dequeue the cell when its desired output interface is available to receive a cell of that cell'"'"'s priority by connecting the cell memory in which the cell is stored to the cell'"'"'s desired output interface.

8. A switch element comprising:

a plurality of input interfaces for receiving cells of data;

a plurality of output interfaces for transmitting cells of data;

a shared pool memory comprised of a plurality of cell memories;

an input crosspoint circuit capable of connecting any of said plurality of input interfaces to any one of said plurality of cell memories;

an output crosspoint circuit for connecting any one of said plurality of cell memories to any one of said output interfaces and;

controller means for controlling which of said inputs is connected to which of said cell memories and for controlling which of said outputs is connected to which of said cell memories;

wherein said controller means further comprises;

a linked-list random access memory;

a set of multipriority queues for each of said output interfaces each one of said queues in said set residing in said random access memory and comprising;

a connection address;

a queue priority identifier; and

a first-in/first-out linked list of identifiers to said cell memories in said shared pool memory wherein said multipriority queues further comprise a means for designating a bandwidth assignment associated with each of a subset of said plurality of queues.

9. The device according to claim 8 wherein said controller further comprises a queue service order table for determining, during a cell cycle, the service order for said plurality of bandwidth queues.

10. In a switch element comprising a plurality of input interfaces, a plurality of output interfaces, a shared pool memory having a plurality of cell memories, a controller, and means responsive to the controller for connecting any of said input lines and any of said output interfaces to any one of said cell memories and capable of sending to one output interface cells of data having different priorities and cells having different assigned proportional bandwidths at the same priority, a method for switching a cell of data from any input interface to any output interface comprising the steps of:

receiving the cell of data over one input interface and storing the cell in a cell memory designated by said controller for that input interface;

using the controller to examine a tag portion of said cell, said tag portion identifying the output interface to which the cell must be directed;

using the controller to enqueue the cell by adding an identifier for the cell memory in which the cell has been stored to a linked list;

using the controller to dequeue the cell when its desired output is available by connecting the cell memory in which the cell is stored to the cell'"'"'s desired output interface;

transmitting the cell over its desired output interface;

using the controller to examine said tag portion of said cell, said tag portion additionally identifying the assigned proportional bandwidth at which the cell is being transmitted;

using the controller to enqueue the cell at its appropriate assigned proportional bandwidth by adding an identifier for the cell memory in which the cell has been stored to a linked list defining a queue having a specified proportional bandwidth;

using the controller to determine by reference to a service order table the service order for the proportional bandwidth queues; and

using the controller to dequeue the cell when its desired output is available to receive a cell of that cells priority and when that cell is in the highest service order during a cell cycle according to the service order table by connecting the cell memory in which the cell is stored to the cell'"'"'s desired output interface.

11. A switch element comprising:

a plurality input interfaces for receiving cells of data;

a plurality of output interfaces for transmitting cells of data;

a shared pool memory comprises of a plurality of cell memories;

an input crosspoint circuit capable of connecting any or said plurality of input interfaces to anyone of said plurality of cell memories;

an output crosspoint circuit for connecting any one of said plurality of cell memories to any one of said output interfaces;

controller means for controlling which of said inputs is connected to which of said cell memories and for controlling which of said outputs is connected to which of said cell memories;

a plurality of storage elements for storing aggregate input control bits;

a plurality of storage elements for storing aggregate output control bits;

and wherein said controller is responsive to an active state of one of said aggregate bits by treating cells received on a subset of said plurality of input interfaces as though the cells were received on one input interface such that cell order is preserved without resequencing the cells after transmission in the switch.

12. The switch element of claim 11 wherein said controller means further comprises:

a linked-list random access memory;

a set of multipriority queues for each of said output interfaces each one of said queues in said set residing in said random access memory and comprising;

a connection address;

a queue priority identifier; and

a first-in/first-out linked list of identifiers to said cell memories in said shared pool memory; and

further comprising;

a plurality of storage elements for storing aggregate input control bits;

a plurality of storage elements for storing aggregate output control bits;

and wherein said controller is responsive to an active state of one of said aggregate bits by treating cells received on a subset of said plurality of input interfaces as though the cells were received on one input interface by establishing in said linked-list random access memory a set of aggregated multipriority queues for receiving cells from all of the subset of input interfaces.

13. The switch element of claim 12 wherein said control means is operative to respond to one of said aggregate input bits by preserving FIFO order on cells received over said subset of said input interfaces.

14. In a switch element comprising a plurality of input interfaces, a plurality of output interfaces, a shared pool memory comprised of a plurality of cell memories, a controller, aggregate bits, and means responsive to the controller for connecting any of said input interfaces and any of said output interfaces to any one of said cell memories, a method for switching cells of data from a designated aggregate subset of input interfaces to any available interfaces of a designated aggregate subset of output interfaces comprising the steps of:

receiving cells of data over said aggregate subset of input interfaces and storing the cells in cell memories designated by said controller for each of said subset of input interfaces;

using the controller to examine a tag portion of said cells, said tag portion identifying the output interface to which the cell must be directed;

using the controller to enqueue the cells from the aggregate input interfaces by adding in FIFO order an identifier for each of the cell memories in which aggregate input interface cells have been stored to a single linked list for the aggregate output;

using the controller to dequeue the cells when any of the desired aggregate output interfaces are available by connecting the cell memories in which the cells are stored to the available output interfaces; and

transmitting the cells over the desired aggregated output interfaces.

15. The method according to claim 14 further capable of receiving, via aggregated input interfaces, cells of data having different priorities, said method further comprising the steps of:

using the controller to examine said tag portions of said cells, said tag portions additionally identifying the priority at which the aggregated cells are being transmitted;

using the controller to enqueue the cells at their appropriate priority by adding an the identifies for the cell memories in which the cells have been stored to a aggregate linked list having a specified priority; and

using the controller to dequeue the cells when any of the desired aggregate output interfaces are available to receive cells at the aggregated queue'"'"'s priority by connecting the cell memories in which the cells are stored to the available aggregate output interfaces.