Method and apparatus for policing connections using a leaky bucket algorithm with token bucket queuing

• US 20070147404A1
• Filed: 12/27/2005
• Published: 06/28/2007
• Est. Priority Date: 12/27/2005
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: van Haalen, Ronald
• Application Number:
  US11/318,894
• Publication Number:
  US 20070147404A1
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues

Abstract

The invention includes a method and apparatus for performing packet policing by operating an input queue as a leaky bucket queue. The method includes storing a received packet in a shared memory shared by a plurality of input queues and a plurality of output queues, storing a corresponding packet pointer for the packet in one of the plurality of input queues, transferring the packet pointer from the one of the plurality of input queues to one of the plurality of output queues associated with an output port to which the packet is assigned, and transmitting the packet from the output port using the packet pointer. The packet pointer identifies a storage location in the shared memory. The packet pointer is removed from the one of the plurality of output queues and used for retrieving the packet from the shared memory.

Claims

1. A method for performing packet policing, comprising:

storing a received packet in a memory shared by a plurality of input and output queues;

storing a corresponding packet pointer in an input queue, the packet pointer identifying a storage location of the packet in the shared memory;

transferring the packet pointer from the input queue to an output queue associated with an output port to which the packet is assigned; and

transmitting the packet from the output port using the packet pointer.

2. The method of claim 1, wherein storing the packet in the shared memory comprises:

determining whether the input queue has available storage space;

determining whether the shared memory has available storage space; and

storing the packet in the shared memory in response to a determination that both the input queue and the shared memory have available storage space.

3. The method of claim 1, wherein storing the packet in the shared memory comprises:

determining an available storage space of the shared memory; and

storing the packet in the shared memory in response to a determination that the available storage space of the shared memory is sufficient for storing the packet.

4. The method of claim 1, wherein storing the packet in the shared memory comprises:

determining an available storage space of a portion of the shared memory, the portion of the shared memory associated with the input queue and the output queue; and

storing the packet in the portion of the shared memory in response to a determination that the available storage space of the portion of the shared memory is sufficient for storing the packet.

5. The method of claim 1, wherein storing the packet pointer for the packet comprises:

generating the packet pointer in response to storing the packet in the shared memory; and

storing the packet pointer in the input queue.

6. The method of claim 1, wherein transferring the packet pointer from the input queue to the output queue is performed in accordance with an information rate.

7. The method of claim 1, wherein transferring the packet pointer from the input queue to the output queue is performed in a manner for maintaining the packet in the shared memory.

8. The method of claim 1, wherein transmitting the packet from the output port comprises:

removing the packet pointer from the output queue;

retrieving the packet from the shared memory using the packet pointer; and

transmitting the packet over a communication link associated with the output port.

9. The method of claim 8, wherein the packet pointer is removed from the output queue when the packet is scheduled to be transmitted.

10. An apparatus for performing packet policing, comprising:

means for storing a received packet in a memory shared by a plurality of input and output queues;

means for storing a corresponding packet pointer in an input queue, the packet pointer identifying a storage location of the packet in the shared memory;

means for transferring the packet pointer from the input queue to an output queue associated with an output port to which the packet is assigned; and

means for transmitting the packet from the output port using the packet pointer.

11. The apparatus of claim 10, wherein the means for storing the packet in the shared memory comprises:

means for determining whether the input queue has available storage space;

means for determining whether the shared memory has available storage space; and

means for storing the packet in the shared memory in response to a determination that both the input queue and the shared memory have available storage space.

12. The apparatus of claim 10, wherein the means for storing the packet in the shared memory comprises:

means for determining an available storage space of the shared memory; and

means for storing the packet in the shared memory in response to a determination that the available storage space of the shared memory is sufficient for storing the packet.

13. The apparatus of claim 10, wherein the means for storing the packet in the shared memory comprises:

means for determining an available storage space of a portion of the shared memory, the portion of the shared memory associated with the input queue and the output queue; and

means for storing the packet in the portion of the shared memory in response to a determination that the available storage space of the portion of the shared memory is sufficient for storing the packet.

14. The apparatus of claim 10, wherein the means for storing the packet pointer for the packet comprises:

means for generating the packet pointer in response to storing the packet in the shared memory; and

means for storing the packet pointer in the input queue.

15. The apparatus of claim 10, wherein the means for transferring the packet pointer from the input queue to the output queue moves the packet pointer in accordance with an information rate.

16. The apparatus of claim 10, wherein the means for transmitting the packet from the output port using the packet pointer comprises:

means for removing the packet pointer from the output queue;

means for retrieving the packet from the shared memory using the packet pointer; and

means for transmitting the packet over a communication link associated with the output port.

17. An apparatus for performing packet policing, comprising:

an input interface comprising an input queue for storing a packet pointer associated with a received packet;

an output interface comprising an output queue for storing a packet pointer associated with a packet transmitted from an output port associated with the output queue; and

a shared memory coupled to the input interface and the output interface and shared by the input queue and the output queue, the shared memory adapted for storing each packet.

18. The apparatus of claim 17, further comprising:

a controller coupled to the input interface, the output interface, and the shared memory, the controller adapted for;

generating the packet pointer for the received packet;

storing the packet pointer in the input queue; and

transferring the packet pointer from the input queue to the output queue in accordance with an information rate.

19. The apparatus of claim 18, wherein the controller is further adapted for:

determining whether the input queue has available storage space;

determining whether the shared memory has available storage space; and

storing the packet in the shared memory in response to a determination that both the input queue and the shared memory have available storage space.

20. The apparatus of claim 19, wherein the controller is further adapted for:

retrieving the packet from the shared memory using the packet pointer in response to removal of the packet pointer from the output queue; and

providing the retrieved packet to the output port associated with the output queue for transmitting the packet over a communication link.