Apparatus and methods to change thresholds to control congestion in ATM switches

Claim 3

The method of claim 1 further comprising creating a plurality of queues for the cells, wherein the threshold is a threshold for the number of cells in a single queue, and wherein changing the threshold includes increasing the threshold when the total number of cells in said queues decreases.

Claim 4

The method of claim 2 wherein a separate queue is created for cells received on each virtual channel.

Claim 5

The method of claim 1 further comprising creating a plurality of queues for the cells, wherein the threshold is a threshold for the number of cells in a single queue, and wherein changing the threshold includes decreasing the threshold when the total number of cells in said queues increases.

Claim 6

The method of claim 4 wherein a separate queue is created for cells received on each virtual channel.

Claim 7

The method of claim 1 further comprising creating a plurality of queues for the cells, wherein the threshold is a queue limit such that when a cell arrives for any queue Q1 which is one of the queues, and the total number of cells in the queue Q1 exceeds the threshold, the cell is discarded.

Claim 8

The method of claim 1 further comprising creating a plurality of queues for the cells, wherein the threshold is a marking threshold such that when a cell arrives for any queue Q1 which is one of the queues, and when the total number of cells in the queue Q1 exceeds the threshold, the switch indicates that cells from the queue Q1 are to be transmitted with an overload indication.

Claim 11

The method of claim 1 further comprising creating a separate queue of cells for each input virtual channel (IVC), the queues being subdivided into classes of queues, wherein the range of the possible number of cells in each class of queues is subdivided into regions and a separate region ID is provided for each class to identify the region containing the current number of cells in the class, wherein a separate threshold is provided for each region of each class of queues, each threshold being determined by the region ID of the class, wherein at least two thresholds for different classes are different from each other.

Claim 12

The method of claim 1 wherein at least two of the regions overlap, and the region ID changes so that: when the number of cells increases, the region ID changes not before the number of cells reaches an upper limit of a region; and when the number of cells decreases, the region ID changes not before the number of cells reaches a lower limit of a region.

Claim 13

The method of claim 1 wherein at least two of the regions overlap, and the region ID changes with a hysterisis based on the direction of change of the number of cells when the number of cells moves between overlapping regions.

Claim 14

The method of claim 1 wherein the regions do not overlap.

Claim 15

An ATM switch comprising: a circuit for creating one or more queues for cells; a circuit for determining a region ID for the one or more queues, wherein the range of the possible number of cells in the one or more queues is subdivided into regions and the region ID identifies the region containing the current number of cells in the one or more queues; and a circuit for determining a threshold for the number of cells from the region ID in order to control congestion of the switch so that the threshold changes inversely depending on the number of cells when the region ID changes.

Claim 16

An ATM switch comprising: a circuit for creating one or more queues for cells; a circuit for determining a region ID for the one or more queues, wherein the range of the possible number of cells in the one or more queues is subdivided into regions and the region ID identifies the region containing the current number of cells in the one or more queues; and a circuit for determining a threshold for the number of cells from the region ID in order to control congestion of the switch so that the threshold changes inversely depending on the number of cells when the region ID changes.

Claim 17

The switch of claim 13 further comprising a circuit for creating a plurality of queues for the cells, wherein the threshold is a threshold for the number of cells in a single queue, and wherein the circuit for changing the threshold includes a circuit for increasing the threshold when the total number of cells in said queues decreases.

Claim 18

The switch of claim 14 wherein the circuit for creating a plurality of queues comprises a circuit for creating a separate queue for cells received on each virtual channel.

Claim 19

The switch of claim 13 further comprising a circuit for creating a plurality of queues for the cells, wherein the threshold is a threshold for the number of cells in a single queue, and wherein the circuit for changing the threshold includes a circuit for decreasing the threshold when the total number of cells in said queues increases.

Claim 20

The switch of claim 16 wherein the circuit for creating a plurality of queues comprises a circuit for creating a separate queue for cells received on each virtual channel.

Claim 21

The switch of claim 13 further comprising a circuit for creating a plurality of queues for the cells, wherein the threshold is a queue limit such that when a cell arrives for any queue Q1 which is one of the queues, and the total number of cells in the queue Q1 exceeds the threshold, the cell is discarded.

Claim 22

The switch of claim 13 further comprising a circuit for creating a plurality of queues for the cells, wherein the threshold is a marking threshold such that when a cell arrives for any queue Q1 which is one of the queues, and the total number of cells in the queue Q1 exceeds the threshold, the switch indicates that cells from the queue Q1 are to be transmitted with an overload indication.

Claim 23

An ATM switch comprising: a circuit for creating a plurality of queues for cells; a circuit for setting a threshold for the number of cells in order to control congestion of the switch; and a circuit for changing the threshold depending on congestion of the switch; wherein the threshold is a discard threshold such that when a cell C1 arrives for any queue Q1 which is one of the queues, and the total number of cells in the queue Q1 exceeds the threshold, then: if the cell C1 arrives in the frame based operation mode in which each frame of cells from one input virtual channel (IVC) is transmitted to a destination port or sub-port without any intervening cells from other IVCs or frames, and the cell C1 is the first cell in a frame, then the whole frame is discarded, but if the cell C1 is not the first in a frame and a previous cell in the frame was not discarded, then the cell C1 is not discarded; if the cell C1 arrives in the normal mode with the cell lost priority flag CLP=1, the cell is discarded, but if CLP=0, the cell is not discarded.

Claim 24

An ATM switch comprising: a circuit for creating a plurality of queues for cells; a circuit for setting a threshold for the number of cells in order to control congestion of the switch; and a circuit for changing the threshold depending on congestion of the switch; wherein the threshold is a discard threshold such that when a cell C1 arrives for any queue Q1 which is one of the queues, and the total number of cells in the queue Q1 exceeds the threshold, then: if the cell C1 arrives in the frame based operation mode in which each frame of cells from one input virtual channel (IVC) is transmitted to a destination port or sub-port without any intervening cells from other IVCs or frames, and the cell C1 is the first cell in a frame, then the whole frame is discarded, but if the cell C1 is not the first in a frame and a previous cell in the frame was not discarded, then the cell C1 is not discarded; if the cell C1 arrives in the normal mode with the cell lost priority flag CLP=1, the cell is discarded, but if CLP=0, the cell is not discarded.

Claim 25

The switch of claim 13 further comprising a circuit for creating a separate queue of cells for each input virtual channel (IVC), the queues being subdivided into classes of queues, wherein the range of the possible number of cells in each class of queues is subdivided into regions and a separate region ID is provided for each class to identify the region containing the current number of cells in the class, wherein a separate threshold is provided for each region of each class of queues, each threshold being determined by the region ID of the class, wherein at least two thresholds for different classes are different from each other.

Claim 26

The ATM switch of claim 10 wherein at least two of the regions overlap, and the switch comprises a circuit for changing the region ID so that: when the number of cells increases, the region ID changes not before the number of cells reaches an upper limit of a region; and when the number of cells decreases, the region ID changes not before the number of cells crosses a lower limit of a region.

Claim 27

An ATM switch comprising: a circuit for creating a plurality of classes of queues for ATM cells; a circuit for providing a class ID that identifies the class containing the queue for an incoming cell; a class counter table for storing a class counter for each class, wherein the class counter is a current number of cells in each class, and for providing a class counter in response to a class ID; a region ID table for storing a current region ID for each class, wherein the range of the possible number of cells in each class is subdivided into regions and the region ID for each class identifies the region containing the current number of cells in the class, the region ID table being for providing a region ID in response to a class ID; one or more limit tables for storing upper and lower limits for each region of each class, and for providing the upper and lower limits in response to a class ID and a region ID; and a circuit for comparing a class counter with the upper and lower limits and for changing the respective region ID when the class counter indicates that the region ID is to be changed.

Claim 28

An ATM switch comprising: a circuit for creating a plurality of classes of queues for ATM cells; a circuit for providing a class ID that identifies the class containing the queue for an incoming cell; a class counter table for storing a class counter for each class, wherein the class counter is a current number of cells in each class, and for providing a class counter in response to a class ID; a region ID table for storing a current region ID for each class, wherein the range of the possible number of cells in each class is subdivided into regions and the region ID for each class identifies the region containing the current number of cells in the class, the region ID table being for providing a region ID in response to a class ID; one or more limit tables for storing upper and lower limits for each region of each class, and for providing the upper and lower limits in response to a class ID and a region ID; and a circuit for comparing a class counter with the upper and lower limits and for changing the respective region ID when the class counter indicates that the region ID is to be changed.

Claim 29

The ATM switch of claim 23 further comprising: a threshold table for storing one or more thresholds for each class and each region, and for providing the one or more thresholds in response to a class ID and a region ID; and a circuit for comparing the one or more thresholds with a number of cells in the queue for which a cell is received, and for generating a signal indicating which, if any, of the thresholds is exceed by the number of cells in said queue.

Claim 30

The ATM switch of claim 23 wherein the circuit for creating a plurality of classes of queues for ATM cells is to create a separate queue for each input virtual channel.

Claim 33

The method of claim 26 further comprising: a threshold table storing one or more thresholds for each class and each region, and providing the one or more thresholds in response to the class ID and the region ID of the incoming cell; and comparing the one or more thresholds with a number of cells in the queue for which the cell is received, and generating a signal indicating which, if any, of the thresholds is exceed by the number of cells in said queue.

Claim 34

The method of claim 26 wherein creating a plurality of classes of queues for ATM cells comprises creating a separate queue for each input virtual channel.

Claim 37

The method of claim 29 wherein the data are queued and transmitted in fixed size data units, and the region ID identifies the region containing the current number of data units in the one or more queues.

Claim 38

A network routing apparatus comprising: a circuit for creating one or more queues for network data; a circuit for determining a region ID for the one or more queues, wherein the range of the possible amount of data in the one or more queues is subdivided into regions and the region ID identifies the region containing the current amount of data in the one or more queues; and a circuit for determining a threshold for the amount of data from the region ID in order to control congestion of the apparatus so that the threshold changes inversely depending on the amount of data when the region ID changes.

Claim 39

A network routing apparatus comprising: a circuit for creating one or more queues for network data; a circuit for determining a region ID for the one or more queues, wherein the range of the possible amount of data in the one or more queues is subdivided into regions and the region ID identifies the region containing the current amount of data in the one or more queues; and a circuit for determining a threshold for the amount of data from the region ID in order to control congestion of the apparatus so that the threshold changes inversely depending on the amount of data when the region ID changes.

Claim 40

The apparatus of claim 31 wherein the data in the queues are in fixed size data units, and the region ID identifies the region containing the current number of data units in the one or more queues.