Method and apparatus for dynamically resizing queues utilizing programmable partition pointers

• US 6,044,418 A
• Filed: 06/30/1997
• Issued: 03/28/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Muller, Shimon
• Primary Examiner(s): Palys, Joseph E.
• Assistant Examiner(s): Mai, Rijue
• Application Number:
  US08/885,232
• Time in Patent Office: 1,002 Days
• Field of Search: 395/650, 395/311, 395/800, 395/843, 395/600, 395/846, 395/876, 395/874.5, 395/564, 395/497.04, 395/250, 395/235, 395/200.17, 395/859, 395/860, 395/861, 364/900, 370/392, 710/56, 710/39.41, 711/173
• US Class Current: 710/56
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

A system and method for dynamically resizing queues used in a network switch to accommodate potential congestion situations without experiencing data loss. In one embodiment, partition pointer registers are used to indicate when resizing is desirable. The control logic then determines when it is safe to update the size of the queue such that no data loss occurs and timely updates the queue size.

Claims

1. A method for modifying sizes of queues comprising the steps of:

programming partition pointers to indicate an updated location of at least one partition boundary of at least one queue;

for each partition boundary to be updated;

checking states of the at least one queue affected by movement of the location of the partition boundary;

determining when it is safe to move each location of the partition boundary; and

when it is determined that it is safe to move the location of the partition boundary, updating the partition boundary to the updated location.

2. The method as set forth in claim 1, further comprising the steps of:

setting a completion register to a first state to indicate that at least one partition boundary is to be updated; and

setting the completion register to a second state to indicate that the step of updating the partition boundary has completed.

3. The method as set forth in claim 2, wherein:

the step of setting the completion register to the first state comprises for each partition to be updated, setting a corresponding bit in the completion register to a first value; and

the step of setting the completion register to the second state comprises for each partition that is updated, setting the corresponding bit in the completion register to a second value.

4. The method as set forth in claim 1, wherein the step of determining that it is safe comprises the step of determining that data is not located in the area affected by movement of the partition boundary.

5. An apparatus comprising:

a memory comprising at least one queue, each queue defined by partition boundaries;

at least one partition pointer, each partition pointer identifying a location of a partition boundary; and

control logic coupled to the memory and the at least one partition pointer, said control logic detecting when the at least one partition pointer is updated to a new location, determining when it is safe to move the partition boundary, and when it is safe to move the partition boundary, moving the partition boundary.

6. The apparatus as set forth in claim 5, wherein the memory comprises a plurality of queues ordered contiguously.

7. The apparatus as set forth in claim 5, further comprising a completion register, said completion register set to a first state to indicate that at least one partition boundary is to be updated and set to a second state to indicate that the at least one partition pointer has been updated.

8. The apparatus as set forth in claim 7, wherein the completion register comprises a plurality of bits, each bit corresponding to a partition boundary, such that a corresponding bit is set to a first value when a corresponding partition boundary is to be updated and set to a second value after the corresponding partition boundary has been updated.

9. The apparatus as set forth in claim 5, further comprising a start of queue pointer and end of queue pointer corresponding to each queue, said partition boundary updated by modifying the start of queue or end of queue.

10. The apparatus as set forth in claim 5, further comprising a write pointer and read pointer corresponding to each queue, said write pointer and read pointer used to determine when it is safe to update the partition boundary.

11. In a switch coupled to a network, said switch comprising a plurality of output ports, each port comprising at least one queue utilized to control the buffering of data to be output through the output port, a method for dynamically resizing queues comprising the steps of:

determining when a queue needs to be resized;

programming a partition pointer corresponding to a partition boundary of the queue to indicate an updated location of the partition boundary;

checking states of at least one queue affected by movement of the location of the partition boundary;

determining when it is safe to move the location of the partition boundary; and

when it is determined that it is safe to move the location of the partition boundary, updating the partition boundary to the updated location.

12. The method as set forth in claim 11, further comprising the steps of:

setting a completion register to a first state to indicate that at least one partition boundary is to be updated; and

setting the completion register to a second state to indicate that step of updating the partition boundary has completed.

13. The method as set forth in claim 12, wherein:

the step of setting the completion register to the first state comprises for each partition to be updated, setting a corresponding bit in the completion register to a first value; and

the step of setting the completion register to the second state comprises for each partition that is updated, setting the corresponding bit in the completion register to a second value.

14. The method as set forth in claim 11, wherein the step of determining that it is safe comprises the step of determining that data is not located in the area affected by movement of the partition boundary.

15. The method as set forth in claim 11, wherein the queue is resized to be larger.

16. The method as set forth in claim 11, wherein the queue is resized to be smaller.