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

US 5,901,147 A
Filed: 08/30/1996
Issued: 05/04/1999
Est. Priority Date: 08/30/1996
Status: Expired due to Term

- Alert
- Pin

Associated Cases

Associated Defendants

First Claim

Patent Images

1. A method for processing cells in an ATM switch, the method comprising:

creating one or more queues for the cells;

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;

determining a threshold for the number of cells from the region ID in order to control congestion of the switch; and

changing the threshold when the region ID changes so that threshold changes inversely depending on the number of cells.

View all claims

8 Assignments

Timeline View

Assignment View

Litigations

0 Petitions

Accused Products

Abstract

In an ATM switch, queue thresholds vary dynamically depending on switch congestion. All the queues are organized in one or more classes. The thresholds for each class depend inversely on the number of cells in all the queues of the class.

100 Citations

View as Search Results

32 Claims

1. A method for processing cells in an ATM switch, the method comprising:
- creating one or more queues for the cells;
  
  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;
  
  determining a threshold for the number of cells from the region ID in order to control congestion of the switch; and
  
  changing the threshold when the region ID changes so that threshold changes inversely depending on the number of cells.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 22)
- - 2. 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, andwherein changing the threshold includes increasing the threshold when the total number of cells in said queues decreases.
  - 3. The method of claim 2 wherein a separate queue is created for cells received on each virtual channel.
  - 4. 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, andwherein changing the threshold includes decreasing the threshold when the total number of cells in said queues increases.
  - 5. The method of claim 4 wherein a separate queue is created for cells received on each virtual channel.
  - 6. 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.
  - 7. 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.
  - 9. 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.
  - 10. 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.
  - 11. 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.
  - 12. The method of claim 1 wherein the regions do not overlap.
  - 22. 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.

8. A method for processing cells in an ATM switch, the method comprising:
- creating a plurality of queues for the cells;
  
  setting a threshold for the number of cells in order to control congestion of the switch; and
  
  changing the threshold depending on congestion of the switch;
  
  wherein the threshold is a discard threshold such that when any cell C1 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, 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 loss priority flag CLP=1, the cell is discarded, but if CLP=0, the cell is not discarded.

13. 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.
- View Dependent Claims (14, 15, 16, 17, 18, 19, 21)
- - 14. 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, andwherein the circuit for changing the threshold includes a circuit for increasing the threshold when the total number of cells in said queues decreases.
  - 15. 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.
  - 16. 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, andwherein the circuit for changing the threshold includes a circuit for decreasing the threshold when the total number of cells in said queues increases.
  - 17. 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.
  - 18. 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.
  - 19. 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.
  - 21. 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.

20. 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.

23. 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.
- View Dependent Claims (24, 25)
- - 24. 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.
  - 25. 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.

26. A method for processing cells in an ATM switch, the method comprising:
- creating a plurality of classes of queues for ATM cells;
  
  providing a class ID that identifies the class containing the queue for an incoming cell;
  
  a class counter table storing a current number of cells in each class and providing the class counter in response to the class ID;
  
  a region ID table 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 providing the region ID for the incoming cell in response to the cell'"'"'s class ID;
  
  one or more limit tables storing upper and lower limits for each region of each class, and providing the upper and lower limits in response to the class ID and the region ID of the incoming cell; and
  
  comparing a class counter with the upper and lower limits and changing the respective region ID if the class counter indicates that the region ID is to be changed.
- View Dependent Claims (27, 28)
- - 27. 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.
  - 28. 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.

29. A method for processing network data in a network routing apparatus, the method comprising:
- creating one or more queues for the network data;
  
  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;
  
  determining a threshold for the amount of data from the region ID in order to control congestion of the apparatus; and
  
  changing the threshold when the region ID changes so that the threshold changes inversely depending on the amount of data.
- View Dependent Claims (30)
- - 30. 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.

31. 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.
- View Dependent Claims (32)
- - 32. 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.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
RPX Corporation
Original Assignee
MMC Networks, Inc. (MACOM Technology Solutions Holdings, Inc.)
Inventors
Joffe, Alexander
Primary Examiner(s)
Nguyen, Chau
Assistant Examiner(s)
VU, THINH D

Application Number

US08/706,103
Time in Patent Office

977 Days
Field of Search

370/230, 370/235, 370/252, 370/253, 370/395, 370/397, 370/412, 370/413, 370/415, 370/417, 370/468, 395/200.65
US Class Current

370/412
CPC Class Codes

H04L 12/5602   Bandwidth control in ATM Ne...

H04L 2012/5636   Monitoring or policing, e.g...

H04L 2012/5651   Priority, marking, classes

H04L 2012/5681   Buffer or queue management

H04Q 11/0478   Provisions for broadband co...

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

First Claim

8 Assignments

Litigations

0 Petitions

Accused Products

Abstract

100 Citations

32 Claims

Specification

Solutions

Use Cases

Quick Links

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

First Claim

8 Assignments

Subscription Required

Subscription Required

Litigations

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

100 Citations

32 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links