System and method for regulating data traffic in a network device

• US 7,660,252 B1
• Filed: 03/17/2005
• Issued: 02/09/2010
• Est. Priority Date: 03/17/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hoffman, Robert, Huang, Yiren
• Primary Examiner(s): Chou; Albert T
• Application Number:
  US11/083,884
• Time in Patent Office: 1,790 Days
• Field of Search: 370/229, 370/235, 370/409, 370/466, 370/395, 709/235, 709/240
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method and a system for controlling a packet passing through a network device are provided. The method includes timestamping the packet with an arrival time when it arrives at the network device, and determining the time the packet spends in the network device. The time spent is calculated by comparing the arrival time stamp and the exit time stamp. Subsequently, the packet is labeled, based on a function of the determined time spent in the network device. The packet can be labeled, to be dropped, suppressed or temporarily stopped. The system for controlling the packet passing through the network device comprises the means for performing the above mentioned steps.

Claims

1. A method for controlling a packet passing through a network device, the method comprising:

timestamping the packet with an arrival time when the packet arrives at a queue in the network device;

timestamping the packet with an exit time when the packet exits the queue;

determining a queue time that is a length of time the packet has been in the queue;

determining a regulating level for labeling packets, wherein the regulating level is based on a weighted average time, wherein the weighted average time is based on the queue time of the packet, an average queue time of a predefined number of packets that previously spent time in the queue, and a weight factor, and wherein the weight factor gives more weight to either the queue time of the packet or to the average queue time;

labeling the packet to be dropped if the regulating level is greater than a predefined threshold; and

processing the packet in the network device based on the labeling.

2. The method of claim 1 wherein the weighted average time is based on an expression Tave(i)=Tave(i−

1)*(1−

w)+T(i)*w, wherein Tave(i) is the weighted average time, wherein Tave(i−

1) is the average queue time, wherein T(i) is queue time of the packet, and wherein w is the weight factor.

3. The method of claim 2 additionally comprising configuring a packet dropping level criteria based on a Random Early Dropping (RED) algorithm, wherein the packet is labeled with a regulating level based on the weighted moving average.

4. The method of claim 2 wherein a criteria for dropping the packet is based on a Weighted Random Early Dropping (WRED) algorithm.

5. The method of claim 1 wherein said processing comprises notifying a downstream device of traffic congestion in the network device.

6. The method of claim 1 wherein the network device comprises a Combined Input Output Queue (CIOQ) switching system.

7. The method of claim 1 wherein said processing comprises temporarily stopping the packet if the packet exceeds regulating level criteria.

8. A system for regulating a flow of packets in a network, the network comprising at least one packet source, at least one packet receiver and a network device, the system comprising:

means for timestamping a packet with an arrival time when the packet arrives at a queue in the network device;

means for timestamping the packet with an exit time when the packet exits the queue;

means for determining a queue time that is a length of time the packet has been in the queue;

means for determining a regulating level for labeling packets, wherein the regulating level is based on a weighted average time, wherein the weighted average time is based on the queue time of the packet, an average queue time of a predefined number of packets that previously spent time in the queue, and a weight factor, and wherein the weight factor gives more weight to either the queue time of the packet or to the average queue time;

means for labeling the packet to be dropped if the regulating level is greater than a predefined threshold; and

means for regulating the flow of the packets based on the labeling.

9. The system of claim 8 further comprises means for determining the time spent by the packet in an input queue at the network device.

10. The system of claim 8 wherein the means for regulating the flow of the packets comprises means for temporarily stopping the packet if the packet exceeds the regulating level criteria.

11. A system for regulating a flow of packets in a network, the network comprising at least one packet source, at least one packet receiver and a network device, the system comprising:

a regulator for;

timestamping a packet with an arrival time when the packet arrives at a queue in the network device;

timestamping the packet with an exit time when the packet exits the queue;

determining a queue time that is a length of time the packet has been in the queue;

a configuration module for determining a regulating level for labeling packets, wherein the regulating level is based on a weighted average time, wherein the weighted average time is based on the queue time of the packet, an average queue time of a predefined number of packets that previously spent time in the queue, and a weight factor, and wherein the weight factor gives more weight to either the queue time of the packet or to the average queue time;

a packet labeler for labeling the packet to be dropped if the regulating level is greater than a predefined threshold; and

a packet processor for processing the packets based on the labeling.

12. The system of claim 11 wherein the network device comprises a Combined Input Output Queue (CIOQ) switching system.

13. The system of claim 11 wherein the packet processor is further operable to temporarily stop the packet if the packet exceeds regulating level criteria.

14. An apparatus for regulating a flow of packets in a network, the network comprising at least one packet source, at least one packet receiver and a network device, the apparatus comprising:

a processor; and

a computer-readable medium including instructions stored thereon, which are executable by the processor, the instructions comprising;

one or more instructions for timestamping the packet with an arrival time when the packet arrives at a queue in the network device;

one or more instructions for timestamping the packet with an exit time when the packet exits the queue;

one or more instructions for determining a queue time that is a length of time the packet has been in the queue;

one or more instructions for determining a regulating level for labeling packets, wherein the regulating level is based on a weighted average time, wherein the weighted average time is based on the queue time of the packet, an average queue time of a predefined number of packets that previously spent time in the queue, and a weight factor, and wherein the weight factor gives more weight to either the queue time of the packet or to the average queue time;

one or more instructions for labeling the packet to be dropped if the regulating level is greater than a predefined threshold; and

one or more instructions for processing the packet in the network device based on the labeling.

15. The apparatus of claim 14 wherein the computer-readable medium further comprises one or more instructions for temporarily stopping the packet if the packet exceeds regulating level criteria.

16. A computer-readable medium including instructions stored thereon, which are executable by a processor for regulating a flow of packets in a network, the network comprising at least one packet source, at least one packet receiver and a data switching system, the computer-readable storage device comprising:

one or more instructions for timestamping the packet with an arrival time when the packet arrives at a queue in the network device;

one or more instructions for timestamping the packet with an exit time when the packet exits the queue;

one or more instructions for determining a queue time that is a length of time the packet has been in the queue;

one or more instructions for determining a regulating level for labeling packets, wherein the regulating level is based on a weighted average time, wherein the weighted average time is based on the queue time of the packet, an average queue time of a predefined number of packets that previously spent time in the queue, and a weight factor, and wherein the weight factor gives more weight to either the queue time of the packet or to the average queue time;

one or more instructions for labeling the packet to be dropped if the regulating level is greater than a predefined threshold; and

one or more instructions for processing the packet in the network device based on the labeling.

17. The computer-readable medium of claim 16 wherein said one or more instructions for processing comprises one or more instructions for dropping the packet from the network device.

18. The computer-readable medium of claim 16 wherein said one or more instructions for processing comprises one or more instructions for setting a priority for the packet.

19. The computer-readable medium of claim 16 wherein said one or more instructions for processing comprises one or more instructions for notifying a downstream device of traffic congestion in the network device.

20. The computer-readable medium of claim 16 said processing comprises temporarily stopping the packet if the packet exceeds regulating level criteria.