Queuing methods and apparatus in a network device

Patent metadata

Field	Value
Publication number	US-9628398-B1
Application number	US-201313781125-A
Country	US
Kind code	B1
Filing date	Feb 28, 2013
Priority date	Feb 28, 2012
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

Abstract

In a method for queuing data units in a network device, a plurality of physical queues corresponding to a port of the network device are defined in a memory of the network device. Respective subsets of the plurality of physical queues are logically coupled to define a plurality of logical queues that are respectively formed of logically coupled physical queues. The logical queues correspond to respective data flows of the port. A data unit belonging to a data flow is received. A logical queue for storing the data unit is selected, based on the data flow of the data unit, from the plurality of logical queues The A physical queue for storing the data unit is then selected from the subset of physical queues that corresponds to the selected logical queue. The data unit is stored in the selected physical queue.

First claim

What is claimed is:

1. A method for queuing data units in a network device, the method comprising:
defining, in a memory of the network device, a plurality of physical queues corresponding to a port of the network device;
logically coupling respective subsets of the plurality of physical queues to define a plurality of logical queues that are respectively formed of logically coupled multiple physical queues, the logical queues corresponding to respective data flows of the port;
receiving a data unit to be stored in the memory, the data unit belonging to a data flow;
selecting, from the plurality of logical queues, a logical queue for storing the data unit based at least in part on the data flow of the data unit;
selecting, from the subset of multiple physical queues that corresponds to the logical queue, a physical queue for storing the data unit;
storing the data unit in the physical queue;
retrieving data units from the subset of multiple physical queues corresponding to the logical queue, including retrieving at least some of the data units concurrently from different physical queues of the subset of multiple physical queues;
releasing buffers that were used to store the data units retrieved from the subset of multiple physical queues so that the released buffers can be reallocated among the plurality of physical queues;
allocating, to the logical queue, free buffers that have memory space available for storing data units in the logical queue; and
distributing, according to a predetermined arbitration scheme that determines an order in which free buffers are provided to physical queues of the subset of multiple physical queues, the free buffers that have memory space available for storing data units in the logical queue among the subset of multiple physical queues that corresponds to the logical queue.

2. A method according to claim 1 , wherein a data flow corresponds to a priority associated with the data unit, and wherein selecting the logical queue for storing the data unit comprises selecting the logical queue based on the priority associated with the data unit.

3. A method according to claim 1 , wherein selecting the physical queue for storing the data unit comprises selecting, in a round robin manner, a physical queue from the subset of multiple physical queues that corresponds to the logical queue.

4. A method according to claim 1 , wherein the data unit is a first data unit, the method further comprising:
receiving a second data unit to be stored in the memory, wherein the second data unit belongs to the same data flow as the first data unit;
selecting, based on the data flow of the second data unit, the logical queue for storing the second data unit;
selecting, for storing the second data unit, a physical queue from the subset of multiple physical queues that corresponds to the logical queue, wherein the physical queue selected for the second data unit is different than the physical queue selected for the first data unit; and
storing the second data unit in the physical queue selected for the second data unit.

5. A method according to claim 4 , wherein retrieving data units from the subset of multiple physical queues comprises, subsequent to storing the second data unit, retrieving, concurrently from the memory, the first data unit and the second data unit.

6. A method according to claim 1 , wherein the data unit is a first data unit and the logical queue selected for the first data unit is a first logical queue, further comprising:
subsequent to receiving the first data unit, receiving a second data unit to be stored in the memory, wherein the second data unit belongs to a different data flow than the data flow of the first data unit;
selecting, based on the data flow of the second data unit, a second logical queue for storing the second data unit, the second logical queue different than the first logical queue;
selecting, for storing the second data unit, a physical queue from the subset of multiple physical queues that corresponds to the second logical queue; and
storing the second data unit in the physical queue selected for the second data unit.

7. A method according to claim 6 , wherein the data flow of the second data unit corresponds to a higher priority than the data flow of the first data unit, and wherein retrieving data units from the subset of multiple physical queues comprises:
subsequent to storing the second data unit, retrieving the first data unit and the second data unit, wherein the second data unit is retrieved prior to retrieval of the first data unit.

8. A method according to claim 1 , wherein the network device includes a packet processor for processing packets received by the network device, and wherein receiving the data unit comprises receiving the data unit from the packet processor after completion of ingress processing of the data unit by the packet processor.

9. A method of claim 1 , wherein defining the plurality of physical queue comprises forming each physical queue in the plurality physical queues by a respective linked list of buffers.

10. A method according to claim 1 , wherein receiving the data unit comprises receiving a packet descriptor associated with a packet being processed in the network device.

11. A method according to claim 1 , wherein distributing, according to the predetermined arbitration scheme, the free buffers among the subset of multiple physical queues that corresponds to the logical queue comprises distributing the free buffers in a round robin manner among the subset of multiple physical queues that corresponds to the logical queue.

12. An apparatus for queuing data units in a network device, the apparatus comprising:
a memory having a plurality of physical queues corresponding to a network port of the network device; and
a queue controller configured to:
logically couple respective subsets of the plurality of physical queues to define a plurality of logical queues that are respectively formed of logically coupled multiple physical queues, the logical queues corresponding to respective data flows of the port;
receive a data unit to be stored in the memory, the data unit belonging to a data flow;
select, from the plurality of logical queues, a logical queue for storing the data unit based at least in part on the data flow of the data unit;
select, from the subset of multiple physical queues that corresponds to the logical queue, a physical queue for storing the data unit;
store the data unit in the physical queue;
retrieve data units from the subset of multiple physical queues corresponding to the logical queue, wherein the queue controller is configured to queues of the subset of multiple physical queues;
release buffers that were used to store the data units retrieved from the subset of multiple physical queues so that the released buffers can be reallocated among the plurality of physical queues;
allocate, to the logical queue, free buffers that have memory space available for storing data units in the logical queue; and
distribute, according to a predetermined arbitration scheme that determines an order in which free buffers are provided to physical queues of the subset of multiple physical queues, the free buffers that have memory space available for storing data units in the logical queue among the subset of multiple physical queues that corresponds to the logical queue.

13. An apparatus according to claim 12 , wherein the data flow corresponds to a priority associated with the data unit, and wherein the queue controller is configured to select the logical queue for storing the data unit based on the priority associated with the data unit.

Assignees

• Marvell Israel (M I S L) Ltd

Inventors

• Malchi Gal
• Bromberg Dror

Classifications

• H04L47/6275 Primary

  based on priority · CPC title

• H04L47/10

  Flow control; Congestion control · CPC title

• H04W28/06

  Optimizing {the usage of the radio link}, e.g. header compression, information sizing {, discarding information (system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365)} · CPC title

• H04L47/6225

  Fixed service order, e.g. Round Robin · CPC title

• H04L47/6295

  using multiple queues, one for each individual QoS, connection, flow or priority · CPC title