Apparatus and method for providing red in packet switched network

Abstract

An apparatus for providing a random early detection (RED) in a packet switched network, comprising: a dequeue counter which is incremented upon each dequeue of a data packet from a queue (Q), and which is reset upon each enqueue of a data packet into the Q; a coefficient memory table (CMT), which stores a predetermined number M of decay coefficients (C); and a calculation unit which is adapted to calculate upon each enqueue of a data packet in the Q, an average queue size (AQS), of the Q, depending on a decay coefficient (C) read from a memory address of the CMT to which the dequeue counter points before it is reset.

What is claimed is: 
     
         1 . An apparatus for providing a random early detection (RED) in a packet switched network, the apparatus comprising:
 a dequeue counter which is incremented upon each dequeue of a data packet from a queue (Q) and which is reset upon each enqueue of a data packet into the Q;   a coefficient memory table (CMT) which stores plurality of decay coefficients (C); and   a calculation unit which is configured to calculate, upon each enqueue of a data packet in the Q, an average queue size (AQS) of the Q, depending on a decay coefficient C, wherein the decay coefficient is read from a memory address of the CMT to which the dequeue counter points before the dequeue counter is reset.   
     
     
         2 . The apparatus according to  claim 1 , wherein the calculation unit is configured to compare the calculated AQS of the Q, with a maximum threshold value and a minimum threshold value to drop a received data packet if the AQS, exceeds the maximum threshold value, to enqueue the received data packet if the AQS is lower than the minimum threshold value and to drop the received data packet randomly if the calculated AQS is between the minimum threshold value and the maximum threshold value. 
     
     
         3 . The apparatus according to  claim 2 , wherein the received data packets are dropped randomly with a different drop probability per traffic priority if the calculated AQS is between the minimum threshold value and the maximum threshold value. 
     
     
         4 . The apparatus according to  claim 1 , wherein the calculation unit is adapted to calculate the AQS of the queue Q, as follows:
   [Curr AQS−Queue Size Diff]× C +Queue Size Diff,
   wherein Curr AQS is the current AQS,   wherein   Queue Size Diff is a queue size difference,   wherein   Queue Size Diff=(Prev Queue Size−Curr Queue Size)/2,   wherein Prev Queue Size is the previously calculated queue size of the queue (Q),   Curr Queue Size is the currently calculated queue size of the queue (Q),   C is the decay coefficient read from the CMT, depending on the pointer value of the dequeue counter of the Q.   
     
     
         5 . The apparatus according to  claim 1 , wherein the decay coefficients (C) are decay coefficients of an exponential decay function stored in the CMT. 
     
     
         6 . The apparatus according to  claim 5 , wherein the calculation unit is adapted to calculate in advance the decay coefficients (C) of the exponential decay function as follows:
     x[i+ 1]= x[i ]×( N−W )/ N  
       C[i+ 1]=( x[i+ 1]− x[ 0])/ x[ 0]
   wherein x[0] is an arbitrary number, N, W are arbitrary numbers (W<N) and i is a variable.   
     
     
         7 . The apparatus according to  claim 6 , wherein
 x[0] is set to 100,   W is set to 1,   N is set to 256.   
     
     
         8 . A method for providing a random early detection (RED) in a packet switched network, comprising:
 incrementing a dequeue counter upon each dequeue of a data packet from a queue (Q), and resetting the dequeue counter upon each enqueue of a data packet in the Q; and   calculating, upon each enqueue of a data packet in the Q, an average queue size (AQS) of the Q, depending on a decay coefficient (C), wherein the decay coefficient is read from a memory address of a coefficient memory table (CMT) to which the dequeue counterpoints before the dequeue counter is reset.   
     
     
         9 . The method according to  claim 8 , wherein the method further comprises comparing the calculated AQS of the Q, with a maximum threshold value and a minimum threshold value;
 dropping a received data packet if the calculated AQS exceeds the maximum threshold value, enqueuing the received data packet if the calculated AQS is lower than the minimum threshold value and dropping randomly the received data packet if the calculated AQS is between the minimum threshold value and the maximum threshold value.   
     
     
         10 . The method according to  claim 9 , wherein the dropping randomly the received data packet comprises dropped randomly the received data packets with a different drop probability per traffic priority. 
     
     
         11 . The method according to  claim 8 ,
 wherein calculating the AQS of the Q, depending on a decay coefficient (C), as follows:
   [Curr AQS−Queue Size Diff]× C +Queue Size Diff,
 
   wherein Curr AQS is the current AQS, wherein   Queue Size Diff is the queue size difference, wherein Queue Size Diff=(Prev Queue Size−Curr Queue Size)/2, wherein Prev Queue Size is the previously calculated queue size of the Q, Curr Queue Size is the currently calculated queue size and C is the decay coefficient read from the CMT, depending on the pointer value of the dequeue counter of the Q.   
     
     
         12 . The method according to  claim 8 , wherein the decay coefficients (C) are decay coefficients of an exponential decay function stored in the CMT. 
     
     
         13 . The method according to  claim 8 , wherein the method further comprises calculating in advance the decay coefficient (C) of the exponential decay function as follows:
     x[i+ 1]= x[i ]×( N−W )/ N  
       C[i+ 1]=( x[i+ 1]− x[ 0])/ x[ 0]
   wherein x[0] is an arbitrary number,   wherein N, W are arbitrary numbers (W<N) and i is a variable.