Methods and systems for caching packets to be written to or read from packet memory

• US 7,606,249 B1
• Filed: 12/21/2004
• Issued: 10/20/2009
• Est. Priority Date: 12/21/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Swenson, Erik R.
• Primary Examiner(s): Kumar, Pankaj
• Assistant Examiner(s): Duong, Duc T
• Application Number:
  US11/018,132
• Time in Patent Office: 1,764 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/235, 370412-418, 370/428, 370/429, 709/223, 709/224, 711/118, 711/119
• US Class Current: 370/412
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing

Abstract

Methods and systems for caching packets to improve utilization of packet memory are disclosed. In one method, packets to be written to a packet memory are accumulated in write caches on an egress queue basis. That is, each write cache stores packets corresponding to an egress queue in the system. When one of the queues has a size that corresponds to a burst length of the packet memory, the packets are written from the queue to the packet memory. Packets are read from the packet memory to read caches. Subsequent accesses to packets stored in the read caches avoid the need to access the packet memory.

Claims

1. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer defined by a user or by physical limitations of the packet memory to ensure efficient utilization of the packet memory;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache; and

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of the burst length B packets in the one write cache, and, in response to failing to accumulate the burst length B of packets in any of write caches, continuing to accumulate packets in the write caches on an egress queue basis.

2. The system of claim 1 wherein the packet memory comprises a dynamic random access memory (DRAM) and the write cache comprises a static random access memory (SRAM).

3. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache; and

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of a burst length B of packets in the one write cache, wherein the packet memory comprises a static random access memory (SRAM) of a first size and a first random access time and wherein the plurality of write caches are implemented using a second SRAM having a second size less than the first size and a random access time less than the first random access time.

4. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache; and

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of a burst length B of packets in the one write cache, wherein the cache manager is adapted to maintain a timer for each of the write caches, and in response to expiration of the timer for the first write cache, the cache manager is adapted to write packets from the one write cache to the packet memory.

5. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache;

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of a burst length B of packets in the one write cache;

(e) a plurality of read caches operatively associated with the packet memory for storing packets read from the packet memory, each of the read caches being capable of storing at least a burst length B of packets; and

(f) a scheduler for scheduling packets, wherein, responsive to a scheduling event, a burst length B of packets is written from the packet memory to one of the read caches.

6. The system of claim 5 wherein the cache manager is adapted to retain the burst length B of packets in the one read cache until the one read cache is over-written.

7. The system of claim 6 wherein, in response to a second scheduling event for one of the packets in the one read cache, the scheduler is adapted to extract the packets from the one read cache.

8. The system of claim 5 comprising a cut-through path between the one write cache and the one read cache, wherein the cache manager is adapted to write packets from the one write cache to the one read cache responsive to a dequeue event that occurs for a packet in the one write cache.

9. The system of claim 8 wherein the cache manager is adapted to inhibit extraction of existing packets from the one write cache during writing of packets to the one write cache and wherein the cache manager is adapted to delay extraction of the packets from the write cache while the reading is inhibited.

10. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache;

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of a burst length B of packets in the one write cache, and, in response to failing to accumulate the burst length B of packets in any of write caches, continuing to accumulate packets in the write caches on an egress queue basis; and

(e) a multicast memory for storing multicast packets, wherein the packet classifier is adapted to classify multicast packets to the multicast memory.

11. A system for caching packets to improve utilization of a packet memory, the system comprising:

(a) a packet memory having a burst length B, B being an integer;

(b) a plurality of write caches associated with the packet memory for storing packets to be written to the packet memory, each write cache corresponding to an egress queue;

(c) a packet classifier for classifying packets to one of the egress queues and writing each packet to the corresponding write cache;

(d) a cache manager for monitoring the size of each of the egress queues and for writing packets from one of the plurality of write caches to the packet memory in response to accumulation of a burst length B of packets in the one write cache; and

(e) at least one multicast write cache and at least one multicast read cache for respectively storing multicast packets to be written to the packet memory and multicast packets read from the packet memory.

12. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory, the burst length being an integer B defined by a user or by physical limitations of the packet memory to ensure efficient utilization of the packet memory;

(c) in response to determining that the size of the queue is equal to at least the burst length B, writing B packets from the one write cache to the packet memory; and

(d) in response to failing to accumulate B packets in any of the write caches, continuing to accumulate packets in the write caches on an egress queue basis.

13. The method of claim 12 wherein accumulating packets in a plurality of write caches includes accumulating packets in a dynamic random access memory (DRAM) and wherein writing the packets in the queue to the packet memory includes writing the packets to a static random access memory (SRAM).

14. The method of claim 12 comprising, responsive to a scheduling event, writing a burst length of packets from the packet memory to a read cache operatively associated with the packet memory.

15. The method of claim 12 comprising, in response to a scheduling event for a packet in the one write cache, writing the packet directly to a read cache.

16. The method of claim 14 comprising maintaining the burst length of packets in the read cache.

17. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, wherein accumulating packets in a plurality of write caches includes accumulating packets in a static random access memory (SRAM) having a first random access time and a first size and wherein writing the packets form the queue to the packet memory includes writing the packets to a second SRAM having a second size greater than the first size and a second random access time that is greater than the first random access time.

18. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory;

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory;

(d) maintaining a timer for each of the write caches, and, in response to expiration of the timer for the one write cache, writing packets from the one write cache to the packet memory.

19. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, responsive to a scheduling event, writing a burst length of packets from the packet memory to a read cache operatively associated with the packet memory, maintaining the burst length of packets in the read cache, and, responsive to a second scheduling event for one of the packets in the read cache, extracting the packet from the read cache.

20. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, inhibiting extraction of existing packets from the one write cache during writing of a packet to the one write cache.

21. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory;

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, wherein accumulating packets in a plurality of write caches includes accumulating multicast packets in a multicast memory separate from the packet memory and the write caches; and

(d) in response to failing to accumulate B packets in any of the write caches, continuing to accumulate packets in the write caches on an egress queue basis.

22. A method for caching packets to improve utilization of packet memory, the method comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory; and

(d) maintaining at least one multicast write cache for caching multicast packets to be written to the packet memory and at least one multicast read cache for storing multicast packets read from the packet memory.

23. A computer-readable medium having stored thereon computer readable instructions that when executed by a processor of a computer perform steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory the burst length being an integer B defined by a user or by physical limitations of the packet memory to ensure efficient utilization of the packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length B, writing B packets from the one write cache to the packet memory, and, in response to failing to accumulate the burst length B of packets in any of write caches, continuing to accumulate packets in the write caches on an egress queue basis.

24. The computer readable medium of claim 23 wherein accumulating packets in a plurality of write caches includes accumulating packets in a dynamic random access memory (DRAM) and wherein writing the packets in the queue to the packet memory includes writing the packets to a static random access memory (SRAM).

25. The computer readable medium of claim 23 comprising, responsive to a scheduling event, writing a burst length of packets from the packet memory to a read cache operatively associated with the packet memory.

26. The computer readable medium of claim 25 comprising maintaining the burst length of packets in the read cache.

27. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, wherein accumulating packets in a plurality of write caches includes accumulating packets in a static random access memory (SRAM) having a first random access time and a first size and wherein writing the packets form the queue to the packet memory includes writing the packets to a second SRAM having a second size greater than the first size and a second random access time that is greater than the first random access time.

28. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory;

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory; and

(d) maintaining a timer for each of the write caches, and, in response to expiration of the timer for the one write cache, writing packets from the one write cache to the packet memory.

29. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, responsive to a scheduling event, writing a burst length of packets from the packet memory to a read cache operatively associated with the packet memory, maintaining the burst length of packets in the read cache, and, responsive to a second scheduling event for one of the packets in the read cache, extracting the packet from the read cache.

30. A computer readable medium having stored thereon computer-executable instructions that when executed by the processor of a computer perform steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, in response to a scheduling event for a packet in the one write cache, writing the packet directly to a read cache.

31. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, inhibiting extraction of existing packets from the one write cache during writing of a packet to the one write cache.

32. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory;

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory, wherein accumulating packets in a plurality of write caches includes accumulating multicast packets in a multicast memory separate from the packet memory and the write caches; and

(d) in response to failing to accumulate B packets in any of the write caches, continuing to accumulate packets in the write caches on an egress queue basis.

33. A computer readable medium having stored thereon computer-executable instructions that when executed by a processor of a computer steps comprising:

(a) accumulating packets in a plurality of write caches on an egress queue basis;

(b) determining whether a queue stored in one of the write caches has a size that is equal to at least a burst length of a packet memory; and

(c) in response to determining that the size of the queue is equal to at least the burst length, writing a burst length of packets from the one write cache to the packet memory; and

(d) maintaining at least one multicast write cache for caching multicast packets to be written to the packet memory and at least one multicast read cache for storing multicast packets read from the packet memory.