Memory management for packet switching device
View Patent ↗A method and system for managing memory in a packet switching device is disclosed. The method and system comprises managing the memory as a single FIFO when inserting packets and managing the memory as a plurality of FIFO queues when removing packets. A memory management scheme in accordance with the present invention takes advantage of the nature of packet switching to give an efficient implementation of multiple independent queues in a memory. The key observation that is made is that in a packet switch it is expected that packets may be stored in the memory for a time no greater than the time it takes to fill up the memory. If a packet due to extreme congestion is delayed longer than that, then deleting that packet is an acceptable result.
1. A method of managing a plurality of queues of received packets, the method comprising:
sequentially inserting said packets into a circular first-in-first-out memory scheme; and
selectively associating said packets with said plurality of queues by updating queue information that links between a packet being inserted into said memory scheme and a previous packet associated with the same queue as the packet being inserted.
2. The method of claim 1 further comprising removing said packets from said memory scheme according to said plurality of queues.
3. The method of claim 1 , wherein said plurality of queues comprises a plurality of independent first-in-first-out queues.
4. The method of claim 1 , wherein sequentially inserting said packets comprises:
inserting a start of a packet at a memory word indicated by a write pointer; and
advancing said write pointer to indicate a memory word located after a memory word containing an end of said packet.
5. The method of claim 4 , wherein sequentially inserting said packets comprises advancing a delete pointer jointly with said write pointer such that an empty zone of a predetermined length is maintained between said write pointer and said delete pointer.
6. The method of claim 5 further comprising dropping an indicated packet corresponding to a memory word indicated by said delete pointer, if said indicated packet is linked to one of said plurality of queues.
7. The method of claim 6 further comprising determining if said indicated packet is linked to one of said plurality of queues by comparing a location of the memory word indicated by said delete pointer to a location indicated by a head pointer of a queue associated with said memory word.
8. The method of claim 6 further comprising determining a queue associated with said memory word based on information associating between a plurality of memory words and said plurality of queues.
9. The method of claim 1 , wherein updating said queue information comprises updating a linking pointer associated with said previous packet to identify a location of the packet being inserted.
10. The method of claim 1 further comprising identifying said previous packet based on a tail pointer corresponding to the queue associated with the packet being inserted.
11. The method of claim 1 further comprising managing a plurality of header pointers identifying the beginning of said plurality of queues, respectively.
12. The method of claim 1 further comprising updating one or more values corresponding to at least one of a header pointer of a queue, a tail pointer of said queue, and a link pointer linking between two consecutive packets of said queue.
13. The method of claim 1 , wherein a capacity of said memory scheme is predetermined based on an expected rate for receiving said packets into said memory scheme.
14. A system for managing a plurality of queues of received packets, the system comprising:
a circular first-in-first-out memory scheme to sequentially store said packets; and
a memory manager able to associate said packets with said plurality of queues by updating queue information that links between a packet being inserted into said memory scheme and a previous packet associated with the same queue as the packet being inserted.
15. The system of claim 14 , wherein said memory manager is able to remove said packets from said memory scheme according to said plurality of queues.
16. The system of claim 14 , wherein said plurality of queues comprises a plurality of first-in-first-out queues.
17. The system of claim 14 , wherein said memory scheme comprises a write pointer to indicate a memory word for inserting a word of a received packet.
18. The system of claim 17 , wherein said memory scheme comprises a delete pointer to be advanced jointly with said write pointer such that an empty zone of a predetermined length is maintained between said write pointer and said delete pointer.
19. The system of claim 18 , wherein said memory manager is able to drop an indicated packet corresponding to a memory word indicated by said delete pointer, if said indicated packet is linked to one of said plurality of queues.
20. The system of claim 19 , wherein said memory manager is able to determine if said indicated packet is linked to one of said plurality of queues by comparing a location of the memory word indicated by said delete pointer to a location indicated by a head pointer of a queue associated with said memory word.
21. The system of claim 19 , wherein said memory manager is able to determine a queue associated with said memory word based on information associating between a plurality of memory words and said plurality of queues.
22. The system of claim 14 , wherein said memory manager is able to update a linking pointer associated with said previous packet to identify a location of the packet being inserted.
23. The system of claim 14 , wherein said memory manager is able to manage a plurality of header pointers identifying the beginning of said plurality of queues, respectively.
24. The system of claim 14 , wherein said memory manager is able to identify said previous packet based on a tail pointer corresponding to the queue associated with the packet being inserted.
25. The system of claim 14 , wherein said memory manager is able to maintain one or more values corresponding to at least one of a header pointer of a queue, a tail pointer of said queue, and a link pointer linking between two consecutive packets of said queue.
26. The system of claim 14 , wherein a capacity of said memory scheme is predetermined based on an expected rate for receiving said packets into said memory scheme.
27. The method of claim 2 , wherein said removing comprises removing a packet identified by a header pointer of a queue, and updating said header pointer to identify a successive packet which is linked to the packet being removed.
28. The method of claim 6 , wherein dropping said indicated packet comprises updating a header pointer of a queue associated with said indicated packet to identify a successive packet, which is linked to said indicated packet.
29. The method of claim 6 , wherein dropping said indicated packet comprises dropping an oldest packet stored in said memory.
30. The system of claim 15 , wherein said memory manager is able to remove a packet identified by a header pointer of a queue, and update said header pointer to identify a successive packet which is linked to the packet being removed.
31. The system of claim 19 , wherein said memory manager is able to update a header pointer of a queue associated with said indicated packet to identify a successive packet, which is linked to said indicated packet.
32. The system of claim 19 , wherein said indicated packet comprises an oldest packet stored in said memory.