Granted Patent B1

US 10,412,018 · App. 15/682,479 · Granted Sep 10, 2019

Inventors: Michael Feng (Mountain View, CA); Anurag Agrawal (Santa Clara, CA); Yi Li (Fremont, CA)

Assignee: BAREFOOT NETWORKS, INC.

H04L47/60H04L49/3036H04L49/3063H04L49/9057

Abstract

Claims (58)

1. A method for scheduling a packet to be dequeued to a processing pipeline of a hardware forwarding element, the method comprising:

selecting a port node representing one of a plurality of ports associated with the processing pipeline;

identifying, based on a configuration that maps (i) each of a plurality of physical queues to one second-layer logical queue, (ii) each second-layer logical queue to one first-layer logical queue, and (iii) each first-layer logical queue to one of the plurality of ports, a set of first-layer logical queue nodes associated with the selected port node;

selecting one of the identified first-layer logical queue nodes based on properties of the identified first-layer logical queue nodes;

identifying, based on the configuration, a set of second-layer logical queue nodes associated with the selected first-layer logical queue node;

selecting one of the identified second-layer logical queue nodes based on properties of the identified second-layer logical queue nodes;

selecting one of a set of physical queues associated with the selected second-layer logical queue node; and

dequeuing a packet from the selected physical queue for processing by the processing pipeline.

2. The method of claim 1 , wherein (i) at least one of the second-layer logical queues is mapped to multiple physical queues, (ii) at least one of the first-layer logical queues is mapped to multiple second-layer logical queues, and (iii) at least one of the ports is mapped to multiple first-layer logical queues.

3. The method of claim 1 , wherein selecting a port node representing one of the ports comprises:

identifying a set of eligible ports; and

using a round robin mechanism to select one of the eligible ports.

4. The method of claim 3 , wherein a particular port is eligible when at least one packet is associated to a physical queue that maps to the particular port through the first and second layers of logical queues.

5. The method of claim 3 , wherein all of the ports are given equal priority for selection when eligible.

6. The method of claim 1 , wherein selecting one of a set of identified logical queue nodes of a particular layer comprises:

removing from the set any logical queue nodes that are ineligible;

determining whether any eligible queues are below their respective guaranteed transmission rates; and

when at least one eligible queue is below its guaranteed transmission rate, selecting one of said queues.

7. The method of claim 6 , wherein a particular logical queue node is ineligible when scheduling has been turned off for the particular logical queue node.

8. The method of claim 6 , wherein a particular logical queue node is ineligible when the particular logical queue node has exceeded a maximum rate for the particular logical queue node.

9. The method of claim 6 , wherein a particular logical queue node is ineligible when the particular logical queue node does not have any packets assigned.

10. The method of claim 6 , wherein selecting one of the set of identified logical queue nodes of a particular layer further comprises:

when all of the eligible queues are above their respective guaranteed transmission rates, identifying a subset of the logical queue nodes with a highest priority; and

selecting one of the subset of logical queue nodes with the highest priority.

11. A method for scheduling a packet to be dequeued to a processing pipeline of a hardware forwarding element, the method comprising:

selecting a port node representing one of a plurality of ports associated with the processing pipeline;

for each of one or more layers of logical queues:

identifying, based on a configuration that maps a plurality of physical queues to the plurality of ports via the one or more layers of logical queues, a set of logical queue nodes associated with a previously selected node, wherein the previously selected node is a port node for a first layer of logical queues and a logical queue node for each subsequent layer of logical queues; and

selecting one of the identified logical queue nodes based on properties of the identified logical queue nodes;

selecting one of a set of physical queues associated with a selected logical queue node of the last layer of logical queues;

dequeuing a packet from the selected physical queue for processing by the processing pipeline;

receiving a message that a new packet has been added to a particular physical queue; and

updating state for the particular physical queue.

12. The method of claim 11 , wherein the layers of logical queues comprise a first layer of logical queues and a second layer of logical queues, wherein the configuration maps (i) each physical queue to one second-layer logical queue, (ii) each second-layer logical queue to one first-layer logical queue, and (iii) each first-layer logical queue to one of the plurality of ports.

13. The method of claim 11 , wherein dequeuing the packet comprises sending a message to a queue manager to dequeue the packet from the selected physical queue.

14. The method of claim 13 further comprising:

receiving a message that a particular packet has been dequeued from the selected physical queue; and

updating state for the selected physical queue and the logical queue nodes at each layer to which the selected physical queue maps.

15. The method of claim 11 further comprising:

mapping the particular physical queue to a particular logical queue node at a first layer of logical queues; and

updating state for the particular logical queue node of the first layer of logical queues.

16. The method of claim 15 further comprising, for each subsequent layer of logical queues:

mapping the particular logical queue node of the previous layer of logical queues to a particular logical queue node of the current layer of logical queues; and

updating state for the particular logical queue node of the current layer of logical queues.

17. A network forwarding integrated circuit (IC) comprising:

a packet processing pipeline;

a plurality of ports associated with the packet processing pipeline; and

a traffic management unit comprising a set of physical queues and a scheduler, the scheduler configured to:

select a port node representing one of the ports;

identify, based on a configuration that maps (i) each of a plurality of physical queues to one second-layer logical queue, (ii) each second-layer logical queue to one first-layer logical queue, and (iii) each first-layer logical queue to one of the plurality of ports, a set of first-layer logical queue nodes associated with the selected port node;

select one of the identified first-layer logical queue nodes based on properties of the identified first-layer logical queue nodes;

identify, based on the configuration, a set of second-layer logical queue nodes associated with the selected first-layer logical queue node;

select one of the identified second-layer logical queue nodes based on properties of the identified second-layer logical queue nodes;

select one of a set of physical queues associated with the selected second-layer logical queue node; and

dequeue a packet from the selected physical queue for processing by the processing pipeline.

18. The network forwarding IC of claim 17 , wherein the scheduler is configured to select a port node representing one of the ports by identifying a set of eligible ports and using a round robin mechanism to select one of the eligible ports.

19. The network forwarding IC of claim 17 , wherein the scheduler is configured to select one of a set of identified logical queue nodes for a particular layer by (i) removing from the set any logical queue nodes that are ineligible, (ii) determining whether any eligible queues are below their respective guaranteed transmission rates, and (iii) when at least one eligible queue is below its guaranteed transmission rate, selecting one of said queues.

20. The network forwarding IC of claim 17 , wherein (i) at least one of the second-layer logical queues is mapped to multiple physical queues, (ii) at least one of the first-layer logical queues is mapped to multiple second-layer logical queues, and (iii) at least one of the ports is mapped to multiple first-layer logical queues.

Assignments (5)

Continuity (2)

Cited By (11)

US 12,191,986 US 12,255,804 US 12,255,835 US 12,288,096 US 12,375,588 US 12,381,962 US 12,399,886 US 12,407,564 US 12,445,542 US 12,457,172 US 12,634,199