Method and apparatus for data buffer management in a communications switch

• US 6,539,024 B1
• Filed: 03/26/1999
• Issued: 03/25/2003
• Est. Priority Date: 03/26/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Pezeshki-Esfahani, Hossain, Heller, Albert D., Janoska, Mark William
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): HO, CHUONG T
• Application Number:
  US09/277,361
• Time in Patent Office: 1,460 Days
• Field of Search: 370/429,412,229,236.1,236.2,233,230,235,395.7,395.71,395.72,413,417 709/213,232,235 710/52,53,54,56,57
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method and apparatus is for buffering data cells in a queuing element is presented. Each queuing element includes a partitioned buffer, where the partitioned buffer includes a plurality of partitions. Each of the partitions stores data cells received by the queuing element. Storage of the data cells into the partitions is accomplished by using an array of logical queues. Each logical queue of the array of logical queues maps data cells corresponding to that logical queue to a particular partition of the plurality of partitions. More than one logical queue may map data cells to a particular partition. Each partition may include a reserved portion, where each logical queue that maps to the partition may map a portion of its data cells to the reserved portion. The resources of the reserved portion to which a logical queue maps data cells are reserved to that specific logical queue and cannot be utilized by other logical queues. Each partition also includes a shared portion, where all of the logical queues that map to a partition are able to utilize the storage space included in the shared portion. Each logical queue includes a maximum size. Depth pointers corresponding to the logical queue and the partition are updated as data cells are enqueued to, and dequeued from, the logical queue.

Claims

1. A method for buffering data cells comprising:

(a) receiving a data cell;

(b) determining a logical queue corresponding to the data cell from a plurality of logical queues, wherein determining the logical queue is based on information in the data cell, wherein the logical queue is used to store data in a partition of a partitioned buffer;

(c) determining if a depth pointer of the logical queue is less than a maximum depth;

(d) when the depth pointer of the logical queue is not less than the maximum depth, discarding the data cell;

(e) when the depth pointer of the logical queue is less than the maximum depth;

(f) determining if the depth pointer of the logical queue exceeds a reserved threshold;

(g) when the depth pointer does not exceed the reserved threshold;

storing the data cell in a reserved portion of the partition; and

incrementing the depth pointer of the logical queue;

(h) when the depth pointer of the logical queue exceeds the reserved threshold;

(i) determining if a shared depth pointer of the partition is less than a maximum shared depth;

(j) when the shared depth pointer is not less than the maximum shared depth, discarding the data cell; and

(k) when the shared depth pointer is less than the maximum shared depth;

storing the data cell in the shared portion of the partition;

incrementing the depth pointer of the logical queue; and

incrementing the shared depth pointer of the partition.

2. The method of claim 1, wherein step (g) further comprises:

when the depth pointer does not exceed the reserved threshold;

determining if a reserved depth pointer of the partition is less than a maximum reserved depth;

when the reserved depth pointer of the partition is less than the maximum

reserved depth;

storing the data cell in the reserved portion of the partition;

incrementing the depth pointer of the logical queue; and

incrementing the reserved depth pointer of the partition;

when the reserved depth pointer is not less than the maximum reserved depth, discarding the data cell.

3. The method of claim 1, wherein step (g) further comprises:

when the depth pointer does not exceed the reserved threshold;

determining if the data cell is discard enabled;

when the data cell is discard enabled;

determining if the depth pointer exceeds a discard threshold of the logical queue;

when the depth pointer does not exceed the discard threshold;

storing the data cell in a reserved portion of the partition; and

incrementing the depth pointer of the logical queue;

when the depth pointer exceeds the discard threshold, discarding the data cell;

when the data cell is not discard enabled;

storing the data cell in a reserved portion of the partition; and

incrementing the depth pointer of the logical queue.

4. The method of claim 1, wherein step (k) further comprises:

when the shared depth pointer is less than the maximum shared depth;

determining if the data cell is discard enabled;

when the data cell is not discard enabled;

storing the data cell in the shared portion of the partition;

incrementing the depth pointer of the logical queue; and

incrementing the shared depth pointer of the partition;

when the data cell is discard enabled;

determining if the depth pointer of the logical queue exceeds a

discard threshold of the logical queue;

when the depth pointer exceeds the discard threshold, discarding the data cell;

when the depth pointer does not exceed the discard threshold of the logical queue;

determining if the shared depth pointer of the of the partition exceeds a shared discard threshold of the partition;

when the shared depth pointer exceeds the shared discard threshold, discarding the data cell;

when the shared depth pointer does not exceed the shared discard threshold;

storing the data cell in the shared portion of the partition;

incrementing the depth pointer of the logical queue; and

incrementing the shared depth pointer of the partition.

5. A method for buffering data cells comprising:

receiving a data cell;

determining a logical queue corresponding to the data cell from a plurality of logical queues, wherein determining the logical queue is based on information in the data cell, wherein the logical queue is used to store data in a partition of a partitioned buffer;

determining if a depth pointer of the logical queue is less than a maximum depth;

when the depth pointer of the logical queue is not less than the maximum depth, discarding the data cell;

when the depth pointer of the logical queue is less than the maximum depth;

 

determining if the depth pointer of the logical queue exceeds a reserved threshold;

when the depth pointer does not exceed the reserved threshold;

 

determining if a reserved depth pointer of the partition is less than a maximum reserved depth;

 

when the reserved depth pointer of the partition is not less than the maximum reserved depth, discarding the data cell;

 

when the reserved depth pointer of the partition is less than the maximum reserved depth;

deter mining if the data cell is discard enabled;

when the data cell is discard enabled;

 

determining if the depth pointer exceeds a discard threshold of the logical queue;

 

when the depth pointer does not exceed the discard threshold;

storing the data cell in the reserved portion of the partition;

incrementing the depth pointer of the logical queue; and

incrementing the reserved depth pointer of the partition;

 

when the depth pointer exceeds the discard threshold, discarding the data cell;

when the data cell is not discard enabled;

 

storing the data cell in the reserved portion of the partition;

 

incrementing the depth pointer of the logical queue; and

 

incrementing the reserved depth pointer of the partition;

when the depth pointer of the logical queue exceeds the reserved threshold;

 

determining if a shared depth pointer of the partition is less than a maximum shared depth;

 

when the shared depth pointer is not less than the maximum shared depth, discarding the data cell; and

 

when the shared depth pointer is less than the maximum shared depth;

determining if the data cell is discard enabled;

when the data cell is not discard enabled;

 

storing the data cell in the shared portion of the partition;

 

incrementing the depth pointer of the logical queue; and

 

incrementing the shared depth pointer of the partition;

when the data cell is discard enabled;

 

determining if the depth pointer of the logical queue exceeds a discard threshold of the logical queue;

 

when the depth pointer exceeds the discard threshold, discarding the data cell;

 

when the depth pointer does not exceed the discard threshold of the logical queue;

determining if the shared depth pointer of the of the partition exceeds a shared discard threshold of the partition;

when the shared depth pointer exceeds the shared discard threshold, discarding the data cell;

when the shared depth pointer does not exceed the shared discard threshold;

 

storing the data cell in the shared portion of the partition;

 

incrementing the depth pointer of the logical queue; and

 

incrementing the shared depth pointer of the partition.

6. The method of claim 5, further comprises:

providing the data cell to an output;

determining if the depth pointer of the logical queue is greater than the reserved threshold;

when the depth pointer is greater than the reserved threshold, decrementing the shared depth pointer of the partition;

when the depth pointer is not greater than the reserved threshold, decrementing the reserved depth pointer of the partition; and

decrementing the depth pointer of the logical queue.

7. A buffer management circuit, comprising:

a buffer, wherein the buffer is partitioned into a plurality of partitions, wherein each partition includes a shared portion, wherein a shared size value indicates the number of data cells that can be stored in the shared portion of each partition, wherein a shared depth pointer indicates the number of data cells currently stored in the shared portion of each partition, wherein when a partition includes a reserved portion, a reserved size value indicates the number of data cells that can be stored in the reserved portion of the partition and a reserved depth pointer indicates the number of data cells currently stored in the reserved portion of the partition; and

an array of logical queues operably coupled to the buffer, wherein each logical queue stores data cells in a corresponding partition of the plurality of partitions, wherein more than one logical queue may correspond to a partition, wherein a queue size value indicates the total number of data cells that the logical queue can store, wherein a queue depth pointer indicates the number of data cells currently stored by the logical queue, wherein when a logical queue includes a reserved portion, a queue reserved size value indicates the number of data cells that the logical queue can store in the reserved portion of the partition.

8. The buffer management circuit of claim 7, wherein a shared congestion threshold is used to determine when stored data cells in the shared portion of the buffer exceeds a shared discard threshold level.

9. The buffer management circuit of claim 8, wherein a logical queue congestion threshold is used to determine when the number of data cells currently stored by the logical queue exceeds a queue discard threshold level.

10. The buffer management circuit of claim 9, wherein the shared size values, the shared depth pointers, the reserved size values, the reserved depth pointers, the queue size value, the queue depth pointers, the queue reserved size values, the shared discard threshold levels, and the queue discard threshold levels for the array of logical queues and the plurality of partitions are maintained by software.

11. The buffer management circuit of claim 10 further comprises a processor that enqueues data cells into the array of logical queues based on a portion of each data cell that selects a corresponding logical queue of the array of logical queues for each data cell, and the shared size values, the shared depth pointers, the reserved size values, the reserved depth pointers, the queue size value, the queue depth pointers, the queue reserved size value, the shared discard threshold level, and the queue discard threshold levels of the corresponding logical queue and a partition of the plurality of partitions in which the corresponding logical queue stores data cells.

12. The buffer management circuit of claim 11 further comprises an arbiter operably coupled to the processor, wherein the processor dequeues data cells from the array of logical queues based on arbitration information received from the arbiter, wherein dequeuing data cells includes updating pointers corresponding to a logical queues and partitions from which the data cells are dequeued.

13. The buffer management circuit of claim 12, wherein data cells to be enqueued are received by the buffer management circuit from a first set of line cards of a communications switch, wherein data cells which are dequeued are provided to a at least one line card of second set of line cards of the communications switch.

14. The buffer management circuit of claim 13, wherein the communications switch is a cell based communications switch.

15. The buffer management circuit of claim 13, wherein the communications switch is a packet based communications switch.

16. The buffer management circuit of claim 15, wherein the communications switch is an asynchronous transfer mode switch.

17. A buffer maintenance processor, comprising:

a processing module; and

memory operably coupled to the processing module, wherein the memory includes operating instruction that cause the processing module to;

 

determine a logical queue corresponding to a received data cell from a plurality of logical queues, wherein determining the logical queue is based on information in the data cell, wherein the logical queue is used to store data in a partition of a partitioned buffer;

 

determine if a depth pointer of the logical queue is less than a maximum depth;

 

when the depth pointer of the logical queue is not less than the maximum depth, discard the data cell;

 

when the depth pointer of the logical queue is less than the maximum depth;

determine if the depth pointer of the logical queue exceeds a reserved threshold;

 

when the depth pointer does not exceed the reserved threshold;

determine if a reserved depth pointer of the partition is less than a maximum reserved depth;

when the reserved depth pointer of the partition is not less than the maximum reserved depth, discard the data cell;

when the reserved depth pointer of the partition is less than the maximum reserved depth;

 

determine if the data cell is discard enabled;

 

when the data cell is discard enabled;

determine if the depth pointer exceeds a discard threshold of the logical queue;

when the depth pointer does not exceed the discard threshold;

 

store the data cell in the reserved portion of the partition;

 

increment the depth pointer of the logical queue; and

 

increment the reserved depth pointer of the partition;

when the depth pointer exceeds the discard threshold, discard the data cell;

 

when the data cell is not discard enabled;

store the data cell in the reserved portion of the partition;

increment the depth pointer of the logical queue; and

increment the reserved depth pointer of the partition;

 

when the depth pointer of the logical queue exceeds the reserved threshold;

determine if a shared depth pointer of the partition is less than a maximum shared depth;

when the shared depth pointer is not less than the maximum shared depth, discard the data cell; and

when the shared depth pointer is less than the maximum shared depth;

 

determine if the data cell is discard enabled;

 

when the data cell is not discard enabled;

store the data cell in the shared portion of the partition;

increment the depth pointer of the logical queue; and

increment the shared depth pointer of the partition;

when the data cell is discard enabled;

determine if the depth pointer of the logical queue exceeds a discard threshold of the logical queue;

when the depth pointer exceeds the discard threshold, discard the data cell;

when the depth pointer does not exceed the discard threshold of the logical queue;

 

determine if the shared depth pointer of the of the partition exceeds a shared discard threshold of the partition;

 

when the shared depth pointer exceeds the shared discard threshold, discard the data cell;

 

when the shared depth pointer does not exceed the shared discard threshold;

store the data cell in the shared portion of the partition;

increment the depth pointer of the logical queue; and

increment the shared depth pointer of the partition.

18. The buffer maintenance processor of claim 17 further comprises operating instructions stored in the memory that cause the processing module to:

provide the data cell to an output;

determine if the depth pointer of the logical queue is greater than the reserved threshold;

when the depth pointer is greater than the reserved threshold, decrement the shared depth pointer of the partition;

when the depth pointer is not greater than the reserved threshold, decrement the reserved depth pointer of the partition; and

decrement the depth pointer of the logical queue.