US20100274897A1 - Random Early Detect and Differential Packet Aging Flow Control in Switch Queues - Google Patents

Abstract

Flow control is provided for a packet switch. An incoming packet is classified according to its priority based on predefined rules to produce a weight value based on the priority of the packet. A lifetime value associated with the packet is produced based on the weight value and the queue occupancy in a queue to which the packet is assigned. The packet is discarded if its associated lifetime value is less than or equal to a threshold value. Otherwise the packet and associated lifetime value are sent to the queue. The lifetime value is periodically changed and compared to a threshold value. The packet is removed from the queue when its lifetime value reaches the threshold value.

Description

• This application is a continuation of U.S. application Ser. No. 11/495,651, entitled “Random early detect and differential packet aging flow control in switch queues,” filed on Jul. 28, 2006, which is a divisional of U.S. application Ser. No. 10/752,622, entitled “Random early detect and differential packet aging flow control in switch queues,” filed on Jan. 6, 2004, both of which applications are incorporated herein by reference in their entirety.
BACKGROUND
• Devices using queuing systems for packets, for example gateways, switches and routers, are often used in networks supporting IP or TCPIP, such as Ethernet. A problem is, however, that packets get stuck in that queues when there is congestion in the network, or when a link is down or not ready. Under this stuck condition two things happen.
• (1) Packets are stored in buffers and referenced through link lists. Complex conditions arise when packets are destined for multiple ports, and the packets can exit from some of the ports but not from others. Furthermore, new packets enter from other ports. The result can be that the packets can get stuck in the buffers indefinitely.
• (2) Buffer space can be taken up by packets that are of lower priority, and higher priority packets get dropped.
• One prior art solution is to wait until the congesting condition in the port is removed, and then the packets can exit from the port. The disadvantage of this solution is that during the time when the packets are locked in the switching device, they take up valuable space resources. As such, a condition may arise that low priority packets remain locked in the device while high priority packets are dropped when they enter the switching device from other ports.
• Another solution is to remove all the packets when they have exceeded a time limit in the switching device. This is done indiscriminately for all packets regardless of priority. The disadvantage of this solution is that it does not differentiate between low and high priority packets. It also does not differentiate between time critical packets (e.g. for real time applications such as voice-over-IP, video-over-IP or other types of time critical packets).
• It would be desirable to prevent packets from becoming stagnant within queues. It would also be desirable to prevent high-priority packets from being dropped by buffers already filled with low priority packets. Finally, it would be desirable to control the congestion in the network that causes these other problems.
SUMMARY OF THE INVENTION
• The present invention helps solve the problems of stagnant packets within queues, dropped high-priority packets and network congestion, using a random early detect and differential packet aging flow control method. A differential random early detect mechanism is used to prevent congestion in the Internet traffic. An aging mechanism solves the problem of packets being locked in the queue of a switching device for a certain time because it cannot exit the queue.
• In more general terms, flow control is provided for a packet switch. An incoming packet is classified according to its priority based on predefined rules to produce a weight value based on the priority of the packet. A lifetime value associated with the packet is produced based on the weight value and the queue occupancy in a queue to which the packet is assigned. The packet is discarded if its associated lifetime value is less than or equal to a threshold value. Otherwise the packet and associated lifetime value are sent to the queue. The lifetime value is periodically changed and compared to a threshold value. The packet is removed from the queue when its lifetime value reaches the threshold value.
BRIEF DESCRIPTION OF THE FIGURES
• Further preferred features of the invention will now be described for the sake of example only with reference to the following figures, in which:
• FIG. 1 is a schematic diagram illustrating a switching device implementing the differential packet aging and random early detect method of the present invention;
• FIG. 2 diagrammatically illustrates the method performed by the RED engine ofFIG. 1; and
• FIG. 3 is a flowchart illustrating the method used by the aging engine ofFIG. 1.
DETAILED DESCRIPTION OF THE EMBODIMENTS
• FIG. 1 is a schematic diagram illustrating aswitching device101 implementing the differential packet aging and random early detect method of the present invention to control one ormore queues11,13,15. Apacket103 enters apacket classification engine105 of theswitching device101. Theclassification engine105 checks the priority of the packet based on a set ofrules107 that can be programmed by a user or which can be hard-coded.
• Based on the priority determined by theclassification engine105, a “weight”value109 is determined by a weightvalue determination section110 and is assigned to thepacket103. Packets that should be aged out faster from the queue will have a smaller weight, and thus have a higher probability for a shorter lifetime.
• The weight value is then fed into a “random early detect” (RED)engine111. Also, the queue occupancy (number of packets)113 in the queue to which thepacket103 is assigned (in this example the queue11) is determined by aqueue occupancy section114 and is fed into theRED engine111. The REDengine111 uses theweight value109 and thequeue occupancy113 to determine alifetime115 of thepacket103 in thequeue11. Thelifetime115 is a random aging time based on the random early detect scheme.
• Once thelifetime115 is assigned to thepacket103, the REDengine111 checks thelifetime115 against alifetime threshold117.FIG. 2 shows the method performed by the REDengine111 in more detail. Theweight value109 and thequeue occupancy113 are processed using anRED algorithm201 of the REDengine111. The REDalgorithm201 calculates alifetime115. The REDengine111 then compares thelifetime115 to thelifetime threshold117. If thelifetime115 is below thethreshold117, the packet is discarded. This helps control congestion in the network. Otherwise thelifetime115 is attached to thepacket103 and sent to thequeue11 as shown inFIG. 1.
• When thepacket103 reaches thequeue11, its life-time is decremented periodically by anaging engine119. A tick is generated periodically, and theaging engine119 acts upon this tick. Theaging engine119 looks through all the packets in the queues and decrements their lifetimes by the same amount. When thelife time115 of thepacket103 in thequeue11 reaches thethreshold117, thepacket103 is removed from thequeue11. The resource occupied can then be used by another packet.
• FIG. 3 is a flowchart illustrating the method used by theaging engine119 in greater detail. Wait ticks are periodically generated atstep301 causingstep303 to determine whether or not the queue is empty. The subsequent steps are not performed until a determination is made that the queue has packets in it. If the queue has packets in it then a first packet pointer pointing to a first packet is fetched atstep305. An agingstep307 is performed on the packets in the queue. Atstep309 it is determined whether the packet has reached or is below thelifetime threshold117, and if it has then the packet is removed from the queue atstep311. It then checks for the next available packet atstep313. If the next packet is not available then the method goes back to periodically generating wait ticks atstep301. If the next packet is found atstep313, then the next packet pointer is fetched at step315 (the pointer points to the packet next to the packet that was previously pointed to) and the method returns to thestep307.
• Thus the present invention solves the problems of the prior art:
• a) The problem of packets locked within a port indefinitely is solved. A packet is aged out if they exceed the time limit assigned to it.
• b) The problem of packets being aged out indiscriminately is solved. Packets are aged out based on the differential random early detection scheme.
• c) Network Congestion is reduced using the random early detection scheme.
• The described invention is appropriate for complex gateways, switches and routers, where the extra gate-count introduced is not much compared to the overall count in the chip. However, in a simpler embodiment, more appropriate for implementation in simple switches, routers, etc., where gate-count is an issue, the differential packet aging is performed without performing RED. Thelifetime115 is assigned directly to the packet based on the set ofrules107 without first determining theweight109 or determining thequeue occupancy113 as inFIG. 1. Packets that should be aged out faster are assigned a lower lifetime. All the packets in the queue are decremented at the same frequency. When the lifetime of the packet in the queue reaches a threshold, the packet is removed from the queue. Thus, in this embodiment, packets are aged out if they exceed the time limits assigned to them or based on the priority assigned to them.
• Thus, although the invention has been described above using particular embodiments, many variations are possible within the scope of the claims, as will be clear to a skilled reader.

Claims (20)

1. A method of operating a packet switch, the method comprising:

classifying an incoming packet according to its priority based on a Quality of Service to produce a classification;

producing a lifetime value based on the classification, the lifetime value relating to an aging time, a weight value and a queue occupancy;

periodically changing the lifetime value of the incoming packet in an output queue; and

removing the incoming packet from the output queue when the changed lifetime value reaches a predetermined threshold.

2. The method ofclaim 1, further comprising discarding the incoming packet if its associated lifetime value is below the predetermined threshold value.

3. The method ofclaim 1, further comprising discarding the incoming packet before storing the incoming packet and its associated lifetime value to the output queue if its associated lifetime value is below the predetermined threshold value.

4. The method ofclaim 1, further comprising periodically decrementing the lifetime value of the incoming packet in the output queue.

5. The method ofclaim 1, wherein producing the lifetime value is performed by a random early detect engine.

6. The method ofclaim 5, further comprising producing the lifetime value based on a random aging time.

7. The method ofclaim 1, wherein a packet with a lower weight value is aged out faster than a packet with a higher weight value.

8. The method ofclaim 1, further comprising operating the packet switch in a computer network.

9. The method ofclaim 1, wherein:

the classifying is performed by a classification engine of the packet switch;

the producing the lifetime value is performed by a first engine of the packet switch; and

the periodically changing the lifetime value is performed by an aging engine of the packet switch; and

a comparator determines when the lifetime value reached the predetermined threshold.

10. The method ofclaim 1, wherein the incoming packet comprises an IP packet.

11. The method ofclaim 1, further comprising determining the weight value based on the priority of the incoming packet.

12. The method ofclaim 1, further comprising storing the incoming packet in the output queue.

13. The method ofclaim 12, further comprising storing a lifetime value associated with the incoming packet in the output queue.

14. A method of operating a computer network, the method comprising:

classifying an incoming packet according to a priority of the incoming packet;

producing a lifetime value based on the classifying, the lifetime value based on an aging time, the weight value and a queue occupancy to which the incoming packet is assigned;

storing the incoming packet in an output queue;

periodically changing the lifetime value of the incoming packet in the output queue; and

removing the incoming packet from the output queue when the lifetime value reaches a predetermined threshold.

15. The method ofclaim 14, wherein the method is performed by a packet switch.

16. The method ofclaim 14, wherein the method is performed by a router.

17. A method of processing packets, the method comprising:

a packet classification engine classifying an incoming packet, the classifying performed according to a priority based on a Quality of Service of the incoming packet;

a first engine producing a lifetime value based on the classifying, the lifetime value based on an aging time, the weight value and a queue occupancy in an output queue to which the incoming packet is assigned;

storing the incoming packet in the output queue;

an aging engine periodically changing the lifetime value of the incoming packet in the output queue; and

a comparator removing the incoming packet from the output queue when the lifetime value reaches a predetermined threshold.

18. The method ofclaim 17, wherein the packet classification engine, first engine, aging engine and comparator are implemented by a packet switch.

19. The method ofclaim 17, further comprising aging out the incoming packet from the output queue if a time limit is exceeded.

20. The method ofclaim 17, further comprising discarding the incoming packet prior to storing the packet if the lifetime value is below a threshold.

Images