System and method for switching asynchronous transfer mode cells

• US 7,203,198 B2
• Filed: 04/17/2002
• Issued: 04/10/2007
• Est. Priority Date: 04/17/2001
• Status: Active Grant

• Current Assignee: Ikanos Communications Incorporated (Qualcomm, Inc.)
• Original Assignee: Conexant Incorporated (Synaptics Incorporated)
• Inventors: Knight, Brian James, Chick, Timothy John
• Primary Examiner(s): Qureshi; Afsar
• Application Number:
  US10/063,384
• Publication Number:
  US 20020176424A1
• Time in Patent Office: 1,819 Days
• Field of Search: 370/474, 370/472, 370/535, 370/537, 370/389, 370/471, 370/395, 370/310, 370/347, 370/341, 370/342, 370/335, 370/320, 370/503, 370/349, 370/338, 370/397, 370/399, 370/401, 370/522, 370/465, 370/466, 370/467, 370/469, 370/475, 370/476, 370/479, 370/442, 370/395.54, 370/395.1, 370/395.2, 370/395.3, 370/395.5, 370/395.4, 370/412, 370/413, 370/415, 370/416, 370/417, 370/418, 370/419, 370/429, 370/235, 370/392, 370/230, 370/252, 370/400, 370/402, 370/406, 370/407, 370/408, 370/414, 370/430, 370/242, 370/354, 370/356, 370/395.7
• US Class Current: 370/395.54
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5648 Packet discarding, e.g. EPD, PTD
• CPC Class Codes: H04L 2012/5658 using the AAL5
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

One embodiment of a method for switching ATM cells using Early Packet Discard and Partial Packet Discard is provided. Initially, a first cell of an AAL5 packet is received at an input port. Next, it is determined whether there is likely to be enough buffering available to handle the whole packet (i.e., up to 64 Kbytes). If it is determined that sufficient buffering is unlikely to be available, the entire packet is discarded. If it is determined that sufficient buffering exists, the cell is received and buffered for subsequent transmission. Next it is determined whether the flow'"'"'s buffer is filled at any time after initial transmission of a AAL5 cell but before reception of the final cell. If such a state is determined, the current cell is discarded and a flag is set in the flow structure so that subsequent cells of the same packet, except the last, will also be discarded.

Claims

1. An asynchronous transfer mode switch, comprising:

a plurality of input/output ports for receiving and transmitting ATM cells;

a cell header filter for decoding ATM cell headers to determine each cell'"'"'s ATM channel;

at least one processor for manipulating each ATM cell in response to the ATM channel identified by the cell header filter and outputting each of the manipulated ATM cells on one of the input/output ports; and

at least one memory structure associated with the at least one processor for storing ATM cell data prior to transmission on one of the input/output ports,

wherein each available ATM channel is represented by a flow data structure in the at least one memory structure, the flow data structure including a plurality of state variables associated with the ATM channel and further including memory addresses for a cell reception handler routine and a cell transmission handler routine, wherein the plurality of state variables include at least one variable selected from the group consisting of the following information;

static parameters such as the ATM channel'"'"'s output port, priority and cell header rewriting rules, a memory address to a queue of buffered cells awaiting transmission;

the ATM channel'"'"'s early packet discard/partial packet discard state, and channel statistics such as a count of cells passing through the channel.

2. The asynchronous transfer mode switch of claim 1, wherein the at least one memory structure further comprises:

a plurality of cell buffers; and

a plurality of first-in-first-out circular arrays respectively associated with the plurality of ATM channels for holding a plurality of cell buffer pointers,

wherein, upon reception of an ATM cell on a particular ATM channel, the cell is placed into a selected one of the plurality of cell buffers and a cell buffer pointer pointing to the selected one of the plurality of cell buffers is placed into the first-in-first-out circular array associated with the ATM channel.

3. The asynchronous transfer mode switch of claim 2, wherein the plurality of first-in-first-out circular arrays respectively associated with the plurality of ATM channels have predetermined sizes based upon the respective ATM channel with which they are associated.

4. A method for switching asynchronous transfer mode cells, comprising the steps of:

receiving an ATM cell at an input port;

identifying an ATM flow associated with the received ATM cell, wherein the ATM flow includes at least memory addresses for an cell reception handler routine and a cell transmission handler routine;

reading the contents of the ATM flow into a plurality of registers, including reading the memory address for the cell reception handler routine into a program counter register for immediate execution;

determining whether the received ATM cell is subject to retransmission; and

performing the following steps if it is determined that the received ATM cell is subject to retransmission;

allocating a cell buffer;

copying the cell contents from the input port to the allocated buffer;

determining whether a circular array of buffer pointers associated with the identified ATM flow is full; and

placing a pointer to the cell buffer into the circular array if it is determined that the circular array is not full.

5. The method of claim 4, further comprising the following steps:

determining that an output port associated with the identified ATM flow is available;

reading a next cell buffer pointer from the circular array into the cell transmission handler routine, the next cell buffer pointer indicating the memory address of the buffer holding the next cell for transmission on the output port; and

transmitting the next cell on the output port.

6. The method of claim 4, wherein the step of determining whether the received ATM cell is subject to retransmission further comprising the steps of:

determining whether the received ATM cell is an operations and management cell;

diverting the received ATM cell to an operations and management flow if it is determined that the received ATM cell is an operations and management cell;

determining whether the received ATM cell is a subject to packet discard;

discarding the received ATM cell if it is determined that the received ATM cell is a subject to packet discard.

7. The method of claim 6, wherein the step of determining whether the received ATM cell is subject to packet discard further comprises the steps of:

determining whether the received ATM cell is the first cell of a multi-cell packet;

performing the following steps if it is determined that the received ATM cell is the first cell of a multi-cell packet;

determining whether sufficient buffer space is available to handle the entire multi-cell packet;

discarding the received ATM cell and all subsequent cells in the multi-cell packet if it is determined that the sufficient buffer space is not available to handle the entire multi-cell packet;

performing the following steps if it is determined that the received ATM cell is not the first cell of a multi-cell packet;

determining whether sufficient buffer space is available for the received ATM cell;

discarding the received ATM cell and all subsequent cells except the last cell in the multi-cell packet if it is determined that sufficient buffer space is not available for the received ATM cell.

8. The method of claim 7, further comprising the steps of:

determining whether an EPD_ACTIVE flag in the ATM flow associated with the received ATM cell has been set to enable or disable early packet discard or partial packet discard for the identified ATM flow;

preventing packet discard if it is determined that an EPD_ACTIVE flag in the ATM flow associated with the received ATM cell has been set to disable.

9. The method of claim 7, wherein the step of determining whether the received ATM cell is the first cell of a multi-cell packet further comprises the step of determining whether an EPD_SEEN_END flag in the ATM flow associated with the received ATM cell has been set to indicate whether the next received cell is predicted to be the start of a new packet.

10. The method of claim 7, wherein the step of discarding the received ATM cell and all subsequent cells except the last cell in the multi-cell packet if it is determined that sufficient buffer space is not available for the received ATM cell further comprises the steps of:

determining whether an EPD_DISCARD_PARTIAL flag in the ATM flow associated with the received ATM cell has been set to indicate that a buffer overload has occurred;

discarding all received ATM cells for which the EPD_DISCARD_PARTIAL flag is set; and

clearing the EPD_DISCARD_PARTIAL flag upon receipt of an end-of packet cell.

11. The method of claim 7, wherein the step of discarding the received ATM cell and all subsequent cells in the multi-cell packet if it is determined that the sufficient buffer space is not available to handle the entire multi-cell packet further comprises the step of:

determining whether an EPD_DISCARD_WHOLE flag in the ATM flow associated with the received ATM cell has been set to indicate that a sufficient buffer space is not available to handle the entire multi-cell packet;

discarding all received ATM cells for which the EPD_DISCARD_WHOLE flag is set; and

clearing the EPD_DISCARD_PARTIAL flag upon the discard of an end-of packet cell.

12. The method of claim 7, wherein the step of determining whether sufficient buffer space is available to handle the entire multi-cell packet further comprises the steps of:

determining whether half of the ATM flow'"'"'s available buffer is filled; and

setting a EPD_DISCARD_WHOLE flag in the ATM flow associated with the received ATM cell to indicate that a sufficient buffer space is not available to handle the entire multi-cell packet if it is determined that half of the ATM flow'"'"'s available buffer is filled.

13. The method of claim 4, further comprising the steps of:

determining that multicast switching of the received ATM cell to a plurality of output ports is required;

identifying a plurality of branch flows associated with the ATM channel and the plurality of output ports;

reading a next cell buffer pointer from the circular array into the cell transmission handler routine, the next cell buffer pointer indicating the memory address of the buffer holding the next cell for transmission; and

replicating the next cell to each of the plurality of branch flows.

14. A computer readable medium incorporating instructions for switching asynchronous transfer mode cells, the instructions comprising:

one or more instructions for receiving an ATM cell at an input port;

one or more instructions for identifying an ATM flow associated with the received ATM cell, wherein the ATM flow includes at least memory addresses for an cell reception handler routine and a cell transmission handler routine;

one or more instructions for reading the contents of the ATM flow into a plurality of registers, including reading the memory address for the cell reception handler routine into a program counter register for immediate execution;

one or more instructions for determining whether the received ATM cell is subject to retransmission; and

performing the following instructions if it is determined that the received ATM cell is subject to retransmission;

one or more instructions for allocating a cell buffer;

one or more instructions for copying the cell contents from the input port to the allocated buffer;

one or more instructions for determining whether a circular array of buffer pointers associated with the identified ATM flow is full; and

one or more instructions for placing a pointer to the cell buffer into the circular array if it is determined that the circular array is not full.

15. The computer readable medium of claim 14, the instructions further comprising:

one or more instructions for determining that an output port associated with the identified ATM flow is available;

one or more instructions for reading a next cell buffer pointer from the circular array into the cell transmission handler routine, the next cell buffer pointer indicating the memory address of the buffer holding the next cell for transmission on the output port; and

one or more instructions for transmitting the next cell on the output port.

16. The computer readable medium of claim 14, wherein the one or more instructions for determining whether the received ATM cell is subject to retransmission further comprising the following instructions:

one or more instructions for determining whether the received ATM cell is an operations and management cell;

one or more instructions for diverting the received ATM cell to an operations and management flow if it is determined that the received ATM cell is an operations and management cell;

one or more instructions for determining whether the received ATM cell is a subject to packet discard;

one or more instructions for discarding the received ATM cell if it is determined that the received ATM cell is a subject to packet discard.

17. The computer readable medium of claim 16, wherein the one or more instructions for of determining whether the received ATM cell is subject to packet discard further comprises the steps of:

one or more instructions for determining whether the received ATM cell is the first cell of a multi-cell packet;

performing the following instructions if it is determined that the received ATM cell is the first cell of a multi-cell packet;

one or more instructions for determining whether sufficient buffer space is available to handle the entire multi-cell packet;

one or more instructions for discarding the received ATM cell and all subsequent cells in the multi-cell packet if it is determined that the sufficient buffer space is not available to handle the entire multi-cell packet;

performing the following instructions if it is determined that the received ATM cell is not the first cell of a multi-cell packet;

one or more instructions for determining whether sufficient buffer space is available for the received ATM cell;

one or more instructions for discarding the received ATM cell and all subsequent cells except the last cell in the multi-cell packet if it is determined that sufficient buffer space is not available for the received ATM cell.

18. The computer readable medium of claim 17, further comprising the following instructions:

one or more instructions for determining whether an EPD_ACTIVE flag in the ATM flow associated with the received ATM cell has been set to enable or disable early packet discard or partial packet discard for the identified ATM flow;

one or more instructions for preventing packet discard if it is determined that an EPD_ACTIVE flag in the ATM flow associated with the received ATM cell has been set to disable.

19. The computer readable medium of claim 17, wherein the one or more instructions for determining whether the received ATM cell is the first cell of a multi-cell packet further comprises one or more instructions for determining whether an EPD_SEEN_END flag in the ATM flow associated with the received ATM cell has been set to indicate whether the next received cell is predicted to be the start of a new packet.

20. The computer readable medium of claim 17, wherein the one or more instructions for discarding the received ATM cell and all subsequent cells except the last cell in the multi-cell packet if it is determined that sufficient buffer space is not available for the received ATM cell further comprises the following instructions:

one or more instructions for determining whether an EPD_DISCARD_PARTIAL flag in the ATM flow associated with the received ATM cell has been set to indicate that a buffer overload has occurred;

one or more instructions for discarding all received ATM cells for which the EPD_DISCARD_PARTIAL flag is set; and

one or more instructions for clearing the EPD_DISCARD_PARTIAL flag upon receipt of an end-of packet cell.

21. The computer readable medium of claim 17, wherein the one or more instructions for discarding the received ATM cell and all subsequent cells in the multi-cell packet if it is determined that the sufficient buffer space is not available to handle the entire multi-cell packet further comprises the following instructions:

one or more instructions for determining whether an EPD_DISCARD_WHOLE flag in the ATM flow associated with the received ATM cell has been set to indicate that a sufficient buffer space is not available to handle the entire multi-cell packet;

one or more instructions for discarding all received ATM cells for which the EPD_DISCARD_WHOLE flag is set; and

one or more instructions for clearing the EPD_DISCARD_PARTIAL flag upon the discard of an end-of packet cell.

22. The computer readable medium of claim 17, wherein the one or more instructions for determining whether sufficient buffer space is available to handle the entire multi-cell packet further comprises the following instructions:

one or more instructions for determining whether half of the ATM flow'"'"'s available buffer is filled; and

one or more instructions for setting a EPD_DISCARD_WHOLE flag in the ATM flow associated with the received ATM cell to indicate that a sufficient buffer space is not available to handle the entire multi-cell packet if it is determined that half of the ATM flow'"'"'s available buffer is filled.

23. The computer readable medium of claim 14, further comprising the following instructions:

one or more instructions for determining that multicast switching of the received ATM cell to a plurality of output ports is required;

one or more instructions for identifying a plurality of branch flows associated with the ATM channel and the plurality of output ports;

one or more instructions for reading a next cell buffer pointer from the circular array into the cell transmission handler routine, the next cell buffer pointer indicating the memory address of the buffer holding the next cell for transmission; and

one or more instructions for replicating the next cell to each of the plurality of branch flows.