Discard policy method and apparatus

• US 7,426,575 B1
• Filed: 05/14/2001
• Issued: 09/16/2008
• Est. Priority Date: 05/14/2001
• Status: Expired due to Term

• Current Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Original Assignee: Turin Networks, Inc. (Dell Technologies Inc.)
• Inventors: Jin, Lei, Zhang, Hui, West, Stephen John, Reissfelder, Bob, Zhu, Shuangxia Sarah, Ali, Shahzad, Jia, Yantao
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): El Chanti; Hussein A
• Application Number:
  US09/859,192
• Time in Patent Office: 2,682 Days
• Field of Search: 709/209, 709/219, 709/223, 709/225, 709/227, 709/229, 709230-232, 709/238, 709/240
• US Class Current: 709/240
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• 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/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]

Abstract

An arriving cell is admitted when a flow occupancy level is less than a flow minimum threshold. When the flow occupancy level is not less than the flow minimum threshold, a drop probability based on per-class thresholds is applied to determine if the arriving is to be rejected. When the arriving cell is not to be rejected after applying the drop probability based on the per-class thresholds, a drop probability based on per-flow thresholds is applied.

Claims

1. A computer implemented method, comprising:

admitting an arriving cell of a first flow into an ingress buffer of a network element when a flow occupancy level associated with the first flow in the ingress buffer is less than a flow minimum threshold associated with the first flow, the ingress buffer storing a plurality of classes of network traffic, each class having a plurality of flows, and each class having specific per-class thresholds and each flow having specific per-flow thresholds, wherein at least one per-flow threshold is different than at least one per-class threshold;

when the flow occupancy level is not less than the flow minimum threshold, applying a drop probability based on per-class thresholds to determine whether the arriving cell should be dropped, wherein a drop probability of the arriving cell is determined based on per-class thresholds corresponding to a class associated with the first flow;

when the arriving cell is not rejected after applying the drop probability based on the per-class thresholds, applying a drop probability based on per-flow thresholds associated with the first flow to determined whether the arriving cell should be dropped;

admitting the arriving cell if the arriving cell is not dropped based on the drop probability based on the per-flow thresholds; and

wherein applying the drop probability based on per-flow thresholds is performed when the arriving cell is not rejected and is not admitted using the drop probability based on the per-class thresholds.

2. The method of claim 1, wherein applying the drop probability based on the per-class thresholds comprises using an average class occupancy level maintained in a class profile of a class associated with the drop probability based on the per-class thresholds.

3. The method of claim 2, wherein the per-class thresholds comprises a class minimum threshold and a class maximum threshold maintained in the corresponding class profile.

4. The method of claim 3, further comprising dropping the arriving cell when the average class occupancy level exceeds the class maximum threshold and admitting the arriving cell if the average class occupancy level is below the class minimum threshold.

5. The method of claim 4, wherein the flow occupancy level is an average flow occupancy level maintained in a flow profile associated with the first flow.

6. The method of claim 5, wherein the per-flow thresholds comprises a flow minimum threshold and a flow maximum threshold maintained in the corresponding flow profile.

7. The method of claim 6, further comprising:

dropping the arriving cell when the average flow occupancy level exceeds the flow maximum threshold; and

admitting the arriving cell when the average flow occupancy level is below the flow maximum threshold and the arriving cell is not dropped after applying the drop probability based on the per-class thresholds.

8. A computer readable medium having stored thereon sequences of instructions which are executable by a system, and which, when executed by the system, cause the system to:

admit an arriving cell of a first flow into an ingress buffer of a network element when a flow occupancy level associated with the first flow in the ingress buffer is less than a flow minimum threshold associated with the first flow, the ingress buffer storing a plurality of classes of network traffic, each class having a plurality of flows, and each class having specific per-class thresholds and each flow having specific per-flow thresholds, wherein at least one per-flow threshold is different than at least one per-class threshold;

when the flow occupancy level is not less than the flow minimum threshold, apply a drop probability based on per-class thresholds to determine whether the arriving cell should be dropped, wherein a drop probability of the arriving cell is determined based on per-class thresholds corresponding to a class associated with the first flow;

when the arriving cell is not rejected after applying the drop probability based on the per-class thresholds, apply a drop probability based on per-flow thresholds associated with the first flow to determine whether the arriving cell should be dropped;

admitting the arriving cell if the arriving cell is not dropped based on the drop probability based on the per-flow thresholds; and

wherein applying the drop probability based on per-flow thresholds is performed when the arriving cell is not rejected and is not admitted using the drop probability based on the per-class thresholds.

9. The computer readable medium of claim 8, wherein applying the drop probability based on the per-class thresholds comprises using an average class occupancy level maintained in a class profile of a class associated with the drop probability based on the per-class thresholds.

10. The computer readable medium of claim 9, wherein the per-class thresholds comprises a class minimum threshold and a class maximum threshold maintained in the corresponding class profile.

11. The computer readable medium of claim 10, further comprising dropping the arriving cell when the average class occupancy level exceeds the class maximum threshold and admitting the arriving cell if the average class occupancy level is below the class minimum threshold.

12. The computer readable medium of claim 11, wherein the flow occupancy level is an average flow occupancy level maintained in a flow profile associated with the first flow.

13. The computer readable medium of claim 12, wherein the per-flow thresholds comprises a flow minimum threshold and a flow maximum threshold maintained in the corresponding flow profile.

14. The computer readable medium of claim 13, further comprising:

dropping the arriving cell when the average flow occupancy level exceeds the flow maximum threshold; and

admitting the arriving cell when the average flow occupancy level is below the flow maximum threshold and the arriving cell is not rejected after applying the drop probability based on the per-class thresholds.

15. A system, comprising a router that stores a logic when executed, performs the steps of:

admitting an arriving cell of a first flow into an ingress buffer of a network element when a flow occupancy level associated with the first flow in the ingress buffer is less than a flow minimum threshold associated with the first flow, the ingress buffer storing a plurality of classes of network traffic, each class having a plurality of flows, and each class having specific per-class thresholds and each flow having specific per-flow thresholds, wherein at least one per-flow threshold is different than at least one per-class threshold;

when the flow occupancy level is not less than the flow minimum threshold, applying a drop probability based on per-class thresholds to determine whether the arriving cell should be dropped, wherein a drop probability of the arriving cell is determined based on per-class thresholds corresponding to a class associated with the first flow;

when the arriving cell is not rejected after applying the drop probability based on the per-class thresholds, applying a drop probability based on per-flow thresholds to determine whether the arriving cell should be dropped;

admitting the arriving cell if the arriving cell is not dropped based on the drop probability based on the per-flow thresholds; and

wherein applying the drop probability based on per-flow thresholds is performed when the arriving cell is not rejected and is not admitted using the drop probability based on the per-class thresholds.

16. The system of claim 15, wherein the drop probability based on the per-class thresholds is applied using an average class occupancy level maintained in a class profile of a class associated with the drop probability based on the per-class thresholds.

17. The system of claim 16, wherein the per-class thresholds comprises a class minimum threshold and a class maximum threshold maintained in the corresponding class profile.

18. The system of claim 17, wherein the arriving cell is dropped when the average class occupancy level exceeds the class maximum threshold, wherein the arriving cell is admitted if the average class occupancy level is below the class minimum threshold.

19. The system of claim 18, wherein the flow occupancy level is an average flow occupancy level maintained in a flow profile associated with the first flow.

20. The system of claim 19, wherein the per-flow thresholds comprises a flow minimum threshold and a flow maximum threshold maintained in the corresponding flow profile.

21. The system of claim 20, wherein the arriving cell is rejected when the average flow occupancy level exceeds the flow maximum threshold, and wherein the arriving cell is admitted when the average flow occupancy level is below the.