Random Early Detect and Differential Packet Aging Flow Control in Switch Queues

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.

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 of  claim 1 , further comprising discarding the incoming packet if its associated lifetime value is below the predetermined threshold value. 
     
     
         3 . The method of  claim 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 of  claim 1 , further comprising periodically decrementing the lifetime value of the incoming packet in the output queue. 
     
     
         5 . The method of  claim 1 , wherein producing the lifetime value is performed by a random early detect engine. 
     
     
         6 . The method of  claim 5 , further comprising producing the lifetime value based on a random aging time. 
     
     
         7 . The method of  claim 1 , wherein a packet with a lower weight value is aged out faster than a packet with a higher weight value. 
     
     
         8 . The method of  claim 1 , further comprising operating the packet switch in a computer network. 
     
     
         9 . The method of  claim 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 of  claim 1 , wherein the incoming packet comprises an IP packet. 
     
     
         11 . The method of  claim 1 , further comprising determining the weight value based on the priority of the incoming packet. 
     
     
         12 . The method of  claim 1 , further comprising storing the incoming packet in the output queue. 
     
     
         13 . The method of  claim 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 of  claim 14 , wherein the method is performed by a packet switch. 
     
     
         16 . The method of  claim 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 of  claim 17 , wherein the packet classification engine, first engine, aging engine and comparator are implemented by a packet switch. 
     
     
         19 . The method of  claim 17 , further comprising aging out the incoming packet from the output queue if a time limit is exceeded. 
     
     
         20 . The method of  claim 17 , further comprising discarding the incoming packet prior to storing the packet if the lifetime value is below a threshold.