Back pressure control system for network switch port

• US 7,058,070 B2
• Filed: 05/01/2001
• Issued: 06/06/2006
• Est. Priority Date: 05/01/2001
• Status: Active Grant

• Current Assignee: Microsemi Storage Solutions, Inc (Microchip Technology Incorporated)
• Original Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Inventors: Divivier, Robert J., Tran, Toan D.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Moore, Ian N.
• Application Number:
  US09/847,079
• Publication Number:
  US 20040213251A1
• Time in Patent Office: 1,862 Days
• Field of Search: 370229-240, 370/395.7, 370/395.71, 370/395.72, 370/412, 370/415, 370/416, 370/419, 370428-429, 370/392, 709/235, 709/244, 710/29, 710 52- 60, 711/143, 711/153, 711/171
• US Class Current: 370/412
• 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/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9084 Reactions to storage capacity overflow

Abstract

A network switch port includes a cell memory, a queuing system, a data path controller and an output buffer. The data path controller stores incoming cells derived from network data transmissions in the cell memory. The queuing system generates the cell memory address of each stored cell when the cell is to be forwarded from the cell memory, and the data path controller appends the cell memory address of that cell to a linked list of addresses of cells to be forwarded from the memory. When the linked list is not empty, the data path controller forwards cells from the cell memory to the output buffer in the order that their cell memory addresses were appended to the linked list. The output buffer stores and then sequentially forwards the cells outward from the switch port to a receiving network component which store them in a cell buffer until it can forward them elsewhere. The receiving network component produces a multiple bit back pressure data indicating how much of its cell buffer is currently filled with cells. Depending on the fill amount the back pressure data indicates, the output buffer either halts or continues to forward cells to the receiving network component, and either halts or continues allowing the data path controller to forward cells from the cell memory to the output buffer.

Claims

1. An apparatus for receiving and storing incoming cells derived from data transmissions conveyed on a network, and for then forwarding the cells elsewhere in the network, the apparatus comprising:

a cell memory for sequentially receiving and storing the incoming cells in separate memory blocks, each of the memory blocks being identified by a unique identification number (BLOCK_ID), and for thereafter reading out a cell stored in any one of the memory blocks when its BLOCK_ID is transmitted to the cell memory;

queuing means (36) for sequentially generating BLOCK_IDs of memory blocks storing cells to be read out of the cell memory; and

memory control means (30) for maintaining a BLOCK_ID queue, for adding BLOCK_IDs generated by the queuing means to the BLOCK_ID queue in an order in which they a generated by the queuing means, and for removing BLOCK_IDs from the BLOCK_ID queue and transmitting them to the cell memory in an order in which the BLOCK_IDs were added to the BLOCK_ID queue such that cell memory reads out the cells stored in the memory blocks identified by the BLOCK_IDs transmitted by the memory control means.

2. The apparatus in accordance with claim 1 further comprising:

first buffer means (37) for storing cells read out of the cell memory, and for thereafter reading out and forwarding cells it has stored.

3. The apparatus in accordance with claim 2

wherein the first buffer means produces and sends first back pressure data to the memory control means indicating whether a number of cells stored in the first buffer means is above a first threshold level,

wherein the memory control means successively removes BLOCK_IDs from the BLOCK_ID queue and transmits them to the cell memory whenever the BLOCK_ID queue contains at least one BLOCK_ID and the first back pressure data indicates the number of cells stored in the first FIFO buffer means is above the first threshold level, and

wherein the memory control means refrains from removing BLOCK_IDs from the BLOCK_ID queue and transmitting them to the cell memory whenever the first back pressure data indicates that the number of cells stored in the first buffer means is below the first threshold level.

4. The apparatus in accordance with claim 3 further comprising

second buffer means (24) for storing cells read out of the first buffer means and for thereafter forwarding each cell it stores elsewhere in the network.

5. The apparatus in accordance with claim 4

wherein the second buffer means generates second back pressure data indicating an amount of unoccupied storage capacity of the second buffer means, and

wherein the first buffer means sets the first threshold level in response to the second back pressure data.

6. A method for receiving and storing cells derived from data transmissions conveyed on a network, and for then forwarding the cells elsewhere in the network, the method comprising the steps of;

a. sequentially receiving and writing the cells into separate blocks of a cell memory, wherein each memory block is identified by a unique identification number (BLOCK_ID);

b. generating a sequence of BLOCK_IDs of memory blocks currently storing cells;

c. adding each generated BLOCK_ID to a BLOCK_ID queue,

d. successively removing each BLOCK_ID from the BLOCK_ID queue in an order in which BLOCK_IDs were added to the BLOCK_ID queue whenever the BLOCK_ID queue contains BLOCK_IDs and first back pressure data indicates that BLOCK_IDs may be removed from the BLOCK_ID queue, and refraining from removing BLOCK_IDs from the BLOCK_ID queue when the first back pressure data indicates that BLOCK_IDs may not be removed from the BLOCK_ID queue,

e. reading a cell out of the cell memory whenever the BLOCK_ID of the memory block in which it is stored is removed from the BLOCK_ID queue at step d.

7. The method in accordance with claim 6 further comprising the steps of.

f. writing cells read out of the cell memory into first buffer means for storing and reading out cells,

g. reading the cells out of the first buffer means, and

h. setting the first back pressure data to indicate that BLOCK_IDs may not be removed from the BLOCK_ID queue whenever a number of cells stored in the first buffer means rises above a threshold level, and setting the first back pressure data to indicate that BLOCK_IDs may be removed from the BLOCK_ID queue whenever the number of cells stored in the first buffer means falls below the threshold level.

8. The method in accordance with claim 7 further comprising the steps of:

i. storing cells read out of the first buffer means in second buffer means for storing and reading out cells;

j. reading cells out of the second buffer means and forwarding them elsewhere in the network;

k. generating a second back pressure data indicating an amount of unoccupied storage capacity of the second buffer means; and

l. setting the threshold level in response to the value of the code conveyed in the second back pressure data.

9. A method for receiving and storing cells derived from data transmissions conveyed on a network, and for then forwarding the cells elsewhere in the network, wherein each cell is identified as belonging to one of a plurality of flows, wherein each flow has defined minimum and maximum forwarding rates, and wherein each flow is assigned to one of a plurality of virtual output queues (VOQs), the method comprising the steps of;

a. sequentially receiving and writing the cells into separate blocks of a cell memory, wherein each memory block is identified by a unique identification number (BLOCK_ID);

b. for each flow for which cells identified as belonging thereto are currently stored in the cell memory, generating BLOCK_IDs of memory blocks storing such cells at a rate bounded by that flow'"'"'s defined minimum and maximum forwarding rates;

c. establishing a separate BLOCK_ID queue corresponding to each of the VOQs,

d. adding each BLOCK_ID generated at step b to a BLOCK_ID queue corresponding to the VOQ to which is assigned the flow of a cell stored in a memory block identified by the generated BLOCK_ID,

e. for each VOQ providing corresponding first back pressure data indicating whether BLOCK_IDs may or may not be removed from the BLOCK_ID queue corresponding to the VOQ;

f. for each VOQ, whenever the corresponding first back pressure data indicates BLOCK_IDs may be removed from the corresponding BLOCK_ID queue, successively removing BLOCK_IDs from the corresponding BLOCK_ID queue in an order which they were added to the BLOCK_ID queue;

g. for each VOQ, whenever the corresponding first back pressure data indicates BLOCK_IDs may be not be removed from the corresponding BLOCK_ID queue, refraining from removing BLOCK_IDs from the corresponding BLOCK_ID queue; and

h. reading a cell out of the cell memory whenever the BLOCK_ID of the memory block in which the cell is stored is removed from any BLOCK_ID queue at step f.

10. The method in accordance with claim 9 further comprising the steps of:

i. storing each cell read out of the cell memory in first buffer means,

j. reading the cells out of the first buffer means, and k, for each VOQ, generating the corresponding first back pressure data,

wherein the first back pressure data indicates that BLOCK_IDs may be removed from the BLOCK_ID queue corresponding to the VOQ when a number of cells of flows assigned to that VOQ stored in the first buffer means is below a first threshold level, and

wherein the first back pressure data indicates that BLOCK_IDs may no be removed from the BLOCK_ID queue corresponding to the VOQ when a number of cells of flows assigned to that VOQ stored in the first butter means is above the first threshold level.

11. The method in accordance with claim 10 further comprising the steps of:

l. storing cells read out of the first buffer means in second buffer means;

m. reading cells out of the second buffer means and forwarding them elsewhere in said network;

n. for each VOQ, generating corresponding second back pressure data indicating an amount of unoccupied storage capacity of the second buffer means, and

o. adjusting the first threshold level corresponding to each VOQ in response to the second back pressure data corresponding to that VOQ.

12. The method in accordance with claim 11 further comprising the step of:

p. for each VOQ, generating a corresponding third back pressure data indicating whether a number of BLOCK_IDs residing in the corresponding BLOCK_ID queue is above or below a second threshold level,

wherein a rate at which BLOCK_IDs of cells identified as belonging to each flow assigned to the VOQ are generated at step g is set to the flow'"'"'s assigned minimum forwarding rate when the corresponding third back pressure data indicates that the number of BLOCK_IDs residing in the corresponding BLOCK_ID queue is above the second threshold level, and

wherein the rate at which BLOCK_IDs of cells identified as belonging to each flow assigned to the VOQ are generated at step g is set higher than the flow'"'"'s assigned minimum forwarding rate when the corresponding third back pressure data indicates that the number of BLOCK_IDs residing in the corresponding BLOCK₁₃ ID queue is below the second threshold level.

13. The method in accordance with claim 9 further comprising the step of:

i. for each VOQ, generating a corresponding third back pressure data indicating whether a number of BLOCK_IDs residing in the corresponding BLOCK_ID queue is above or below a second threshold levels,

wherein a rate at which BLOCK_IDs of cells identified as belonging to each flow assigned to the VOQ are generated at step g is set to the flow'"'"'s assigned minimum forwarding rate when the corresponding third back pressure data indicates that the number of BLOCK_IDs residing in the corresponding BLOCK_ID queue is above the second threshold level, and

wherein the rate at which BLOCK_IDs of cells identified as belonging to each flow assigned to the VOQ are generated at step g is set higher than the flow'"'"'s assigned minimum forwarding rate when the corresponding third back pressure data indicates that the number of BLOCK_IDs residing in the corresponding BLOCK_ID queue is below the second threshold level.