Multibank egress queuing system in a network device

• US 9,306,876 B1
• Filed: 04/01/2014
• Issued: 04/05/2016
• Est. Priority Date: 04/01/2013
• Status: Active Grant

• Current Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Inventors: Bromberg, Dror, Arad, Carmi, Ulman, Sharon, Sherman, Roi
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): Ohri, Romani
• Application Number:
  US14/242,321
• Time in Patent Office: 735 Days
• Field of Search: 711/103, 711/163, 370/412, 370/416, 370/390
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 13/1647 with interleaved bank access
• CPC Class Codes: G06F 13/1694 Configuration of memory controller to different memory types
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 2212/261 Storage comprising a plurality of storage devices
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

In a method of managing queues in an egress queuing system in a network device, a plurality of packets to be stored in a first egress queue are received. The first egress queue is distributed among a plurality of memory banks. The packets are distributed among the plurality of memory banks. Memory banks in which to store the packets are selected based on pseudorandom numbers generated for the packets. The pseudorandom numbers are generated using a first pseudorandom number generator initialized with a first seed. Subsequently, the packets are retrieved from the plurality of memory banks. Memory banks from which to retrieve the packets are selected based on pseudorandom numbers regenerated for the packets. The pseudorandom numbers are regenerated using a second pseudorandom number generator initialized with the first seed.

Claims

1. A method of managing queues in an egress queuing system in a network device, the method comprising:

receiving a plurality of packets to be stored in a first egress queue, wherein the first egress queue is distributed among a plurality of memory banks;

distributing the packets among the plurality of memory banks, including selecting memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a first pseudorandom number generator initialized with a first seed; and

subsequently retrieving the packets from the plurality of memory banks, including selecting memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a second pseudorandom number generator initialized with the first seed.

2. The method of claim 1, wherein each memory bank among the plurality of memory banks includes a local queue corresponding to the first egress queue, and wherein writing a packet to a selected memory bank comprises writing the packet to a head of the local queue in the selected memory bank.

3. The method of claim 2, wherein retrieving a packet from a selected memory bank comprises retrieving the packet from a tail of the local queue in the selected memory bank.

4. The method of claim 1, wherein distributing the plurality of packets, to be stored in the first queue, among the plurality of memory banks configured to store the first queue, includes writing, in a same clock cycle, multiple packets to the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is written to a respective memory bank selected for storing the packet such that respective packets among the multiple packets to be stored in the first queue are written, in the same clock cycle, to different ones of the memory banks among the plurality of memory banks configured to store the first queue.

5. The method of claim 1, wherein retrieving the packets from the first queue includes retrieving, in a same clock cycle, multiple packets from the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is retrieved from a respective memory bank selected for retrieving the packet such that respective packets among the multiple packets are retrieved, in the same clock cycle, from different ones of the memory banks configured to store the first queue.

6. The method of claim 1, wherein the plurality of packets is a first plurality of packets, the method further comprising:

receiving a second plurality of packets to be stored in a second queue, wherein the second egress queue is distributed among the plurality of memory banks;

distributing the second plurality of packets among the plurality of memory banks, including selecting memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a third pseudorandom number generator initialized with a second seed, the second seed associated with the second queue; and

subsequently retrieving the second plurality of packets from the plurality of memory banks, including selecting memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a fourth pseudorandom number generator initialized with the second seed associated with the second queue.

7. The method of claim 6, wherein each memory bank supports a single write operation in a same clock cycle, and wherein the method further comprises:

storing write requests corresponding to packets to be written to the memory banks, wherein each write request is associated with the selected memory bank in which to store the corresponding packet; and

when multiple ones of the stored write requests are associated with a same memory bank, selecting a write request, from the multiple write requests, to be performed in the same memory bank in a given clock cycle, including selecting an oldest one of the multiple write requests in the list of write requests.

8. The method of claim 6, wherein each memory bank supports a single read operation in a same clock cycle, and wherein the method further comprises:

storing read requests corresponding to packets to be retrieved from the memory banks, wherein each read request is associated the selected memory bank from which to retrieve the corresponding packet; and

when multiple ones of the stored read requests are associated with a same memory bank, selecting a read request, from the multiple read requests, to be performed in the same memory bank in a given clock cycle, including selecting an oldest one of the multiple read requests in the list of read requests.

9. An egress queuing system, comprising:

a plurality of memory banks for storing egress queues, wherein each egress queue is distributed among two or more memory banks of the plurality of memory banks;

a write controller coupled to the plurality of memory banks, the write controller configured to

receive a plurality of packets to be stored in a first egress queue, and

distribute the packets among the plurality of memory banks configured to store the first queue, wherein the write controller is configured to select memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a first pseudorandom number generator initialized with a first seed; and

a read controller coupled to the plurality of memory banks, the read controller configured to retrieve the packets from the plurality of memory banks configured to store the first queue, wherein the read controller is configured to select memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a second pseudorandom number generator initialized with the first seed.

10. The egress queuing system of claim 9, wherein each memory bank among the plurality of memory banks includes a local queue corresponding to the first egress queue, and wherein the write controller is configured to write a packet to a head of the local queue in a memory bank selected for storing the packet.

11. The egress queuing system of claim 10, wherein the read controller is configured to retrieve a packet from a tail of the local queue in a memory bank selected for retrieving the packet.

12. The egress queuing system of claim 9, wherein the write controller is configured to write, in a same clock cycle, multiple packets to the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is written to a respective memory bank selected for storing the packet, such that respective packets among the multiple packets to be stored in the first queue are written, in the same clock cycle, to different ones of the memory banks among the plurality of memory banks configured to store the first queue.

13. The egress queuing system of claim 9, wherein the read controller is configured to retrieve, in a same clock cycle, multiple packets from the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is retrieved from a respective memory bank selected for retrieving the packet, such that respective packets among the multiple packets are retrieved, in the same clock cycle, from different ones of the memory banks configured to store the first queue.

14. The egress queuing system of claim 9, wherein the plurality of packets is a first plurality of packets, and wherein:

the write controller is further configured to

receive a second plurality of packets to be stored in a second egress queue, and

distribute the packets among the plurality of memory banks, wherein the write controller is configured to select memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a third pseudorandom number generator initialized with a second seed; and

the read controller is further configured to retrieve the packets from the plurality of memory banks, wherein the read controller is configured to select memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a fourth pseudorandom number generator initialized with the second seed.

15. The egress queuing system of claim 14, wherein each memory bank supports a single write operation in a same clock cycle, and wherein the write controller is further configured to

store write requests corresponding to packets to be written to the memory banks, wherein each write request is associated with the selected memory bank in which to store the corresponding packet;

and

when multiple ones of the stored write requests are associated with a same memory bank, select a write request, from the multiple write requests, to be performed in the same memory bank in a given clock cycle, including selecting an oldest one of the multiple write requests in the list of write requests.

16. The egress queuing system of claim 14, wherein each memory bank supports a single read operation in a same clock cycle, and wherein the method further comprises:

storing read requests corresponding to packets to be retrieved from the memory banks, wherein each read request is associated the selected memory bank from which to retrieve the corresponding packet; and

when multiple ones of the stored read requests are associated with a same memory bank, selecting a read request, from the multiple read requests, to be performed in the same memory bank in a given clock cycle, including selecting an oldest one of the multiple read requests in the list of read requests.

17. A network device, comprising:

one or more packet processing cores configured to receive packets from a network and to transmit packets on a network; and

an egress queuing system coupled to the one or more packet processing cores, the egress queuing system configured to

receive, from one or more packet processing cores, a plurality of packets to be stored in a first egress queue, wherein the first queue is distributed among a plurality of memory banks, distribute the packets among the plurality of memory banks, wherein the egress queuing system is configured to select memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a first pseudorandom number generator initialized with a first seed; and

subsequently retrieve the packets from the plurality of memory banks, wherein the egress queuing system is configured to select memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a second pseudorandom number generator initialized with the first seed.

18. The network device of claim 17, wherein each memory bank among the plurality of memory banks includes a local queue corresponding to the first egress queue, and wherein the egress queuing system is configured to write a packet to a head of the local queue in a memory bank selected for storing the packet, and to retrieve the packet from a tail of the local queue in the memory bank selected for retrieving the packet.

19. The network device of claim 17, wherein the egress queuing system is configured to write, in a same clock cycle, multiple packets to the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is written to a respective memory bank selected for storing the packet, such that respective packets among the multiple packets to be stored in the first queue are written, in the same clock cycle, to different ones of the memory banks among the plurality of memory banks configured to store the first queue.

20. The network device of claim 17, wherein the egress queuing system is configured to retrieve, in a same clock cycle, multiple packets from the first queue in multiple memory banks configured to store the first queue, wherein each packet of the multiple packets is retrieved from a respective memory bank selected for retrieving the packet, such that respective packets among the multiple packets are retrieved, in the same clock cycle, from different ones of the memory banks configured to store the first queue.

21. The network device of claim 17, wherein the plurality of packets is a first plurality of packets, and wherein the egress queuing system is further configured to

receive a second plurality of packets to be stored in a second egress queue,

distribute the packets among the plurality of memory banks, wherein the egress queuing system is configured to select memory banks in which to store the packets based on pseudorandom numbers generated for the packets, wherein the pseudorandom numbers are generated using a third pseudorandom number generator initialized with a second seed, and

subsequently retrieve the packets from the plurality of memory banks, wherein the egress queuing system is configured to select memory banks from which to retrieve the packets based on pseudorandom numbers regenerated for the packets, wherein the pseudorandom numbers are regenerated using a fourth pseudorandom number generator initialized with the second seed.