System and method for fair shared de-queue and drop arbitration in a buffer

Abstract

Systems and methods consistent with the present invention provide a mechanism that can efficiently manage multiple queues and maintain fairness among ports while not placing additional performance demands on the memory used to store the queue data structures. Within a port, high priority traffic is dropped only if it is consuming more than its fair share of bandwidth allocated to that port. Queue arbitration is of low performance cost and simple because it arbitrates only across queues per port, rather than across all the queues in parallel. Accordingly, fair arbitration with relatively little hardware cost.

1 - 21 . (canceled) 
     
     
         22 . A method implemented by a device, the method comprising:
 receiving packets at an input port of the device;   placing the packets in a plurality of queues that are associated with the input port;   determining an operation to perform on the queues; and   performing the operation on the queues based on a relationship between a latency and a priority,   where each queue is associated with a latency or a priority.   
     
     
         23 . The method of  claim 22 , where the operation is performed on a low latency queue before the operation is performed on a high priority queue. 
     
     
         24 . The method of  claim 22 , where the operation is performed on a high priority queue before the operation is performed on a best effort priority queue. 
     
     
         25 . The method of  claim 22 , where performing the operation comprises:
 de-queuing at least one packet in at least one of the plurality of queues.   
     
     
         26 . The method of  claim 22 , where performing the operation comprises:
 dropping at least one packet in at least one of the plurality of queues.   
     
     
         27 . The method of  claim 22 , where each of the plurality of queues is associated with a priority. 
     
     
         28 . The method of  claim 27 , further comprising:
 determining a priority for each of the plurality of queues based on information included in each of the packets; and   placing each of the packets in the plurality of queues based on the determined priority.   
     
     
         29 . A device, comprising:
 a memory to store a plurality of instructions; and   a processor to execute the stored instructions to:
 receive packets at an input port of the device; 
 place the packets in a plurality of queues that are associated with the input port; 
 determine an operation to perform on the queues; and 
 perform the operation on the queues based on a relationship between a latency and a priority, 
 where each queue is associated with a latency or a priority. 
   
     
     
         30 . The device of  claim 29 , where the operation is performed on a low latency queue before the operation is performed on a high priority queue. PATENT 
     
     
         31 . The device of  claim 29 , where the operation is performed on a high priority queue before the operation is performed on a best effort priority queue. 
     
     
         32 . The device of  claim 29 , where, when performing the operation, the processor is further to:
 de-queue at least one packet in at least one of the plurality of queues.   
     
     
         33 . The device of  claim 29 , where, when performing the operation, the processor is further to:
 drop at least one packet in at least one of the plurality of queues.   
     
     
         34 . The device of  claim 29 , where each of the plurality of queues is associated with a priority. 
     
     
         35 . The device of  claim 34 , where the processor is further to:
 determine a priority for each of the plurality of queues based on information included in each of the packets; and   place each of the packets in the plurality of queues based on the determined priority.   
     
     
         36 . A computer-readable memory comprising computer-executable instructions, the computer-readable memory comprising:
 one or more instructions to receive packets at an input port of a device;   one or more instructions to place the packets in a plurality of queues that are associated with the input port;   one or more instructions to determine an operation to perform on the queues; and   one or more instructions to perform the operation on the queues based on a relationship between a latency and a priority,   where each queue is associated with a latency or a priority.   
     
     
         37 . The computer-readable memory of  claim 36 , where the operation is performed on a low latency queue before the operation is performed on a high priority queue. 
     
     
         38 . The computer-readable memory of  claim 36 , where the operation is performed on a high priority queue before the operation is performed on a best effort priority queue. 
     
     
         39 . The computer-readable memory of  claim 36 , further comprising:
 one or more instructions to de-queue, when performing the operation, at least one packet in at least one of the plurality of queues.   
     
     
         40 . The computer-readable memory of  claim 36 , further comprising:
 one or more instructions to drop, when performing the operation, at least one packet in at least one of the plurality of queues.   
     
     
         41 . The computer-readable memory of  claim 36 , further comprising:
 one or more instructions to determine a priority for each of the plurality of queues based on information included in each of the packets; and   one or more instructions to place each of the packets in the plurality of queues based on the determined priority.