# US 2014/0192815 A1 · Maintaining packet order in a parallel processing network device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0192815 A1 - Document ID: US20140192815A1 - Status: Published application - Kind: A1 - Application number: 14/209,513 - Filed: 2014-03-13 - Published: 2014-07-10 - Earliest claimed: 2012-12-17 - Assignees: Marvell Israel (M.I.S.L) Ltd. - Applicants: Marvell Israel (M.I.S.L) Ltd. - Inventors: Evgeny Shumsky; Gil Levy; Adar Peery; Amir Roitshtein - Web page: https://patentgrep.com/patent/US20140192815A1 ## CPC - H04L 47/6295: using multiple queues, one for each individual QoS, connection, flow or priority - H04L 47/6215: {Individual queue per QOS, rate or priority} - H04L 49/552: by ensuring the integrity of packets received through redundant connections - H04L 49/9057: Arrangements for supporting packet reassembly or resequencing - H04L 49/9015: for supporting a linked list - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A plurality of packets that belong to a data flow are received and are distributed to two or more packet processing elements, wherein a packet is sent to a first packet processing element. A first instance of the packet is queued at a first packet processing element according to an order of the packet within the data flow. The first instance of the packet is caused to be transmitted when processing of the first instance is completed and the first instance of the packet is at a head of a queue at the first ordering unit. A second instance of the packet is queued at a second ordering unit. The second instance of the packet is caused to be transmitted when processing of the second instance is completed and the second instance of the packet is at a head of a queue at the second ordering unit. ## Claims ### Claim 1 A method for processing packets in a network device, the method comprising: receiving a plurality of packets at a port of the network device, wherein the plurality of packets belong to a data flow; distributing the packets among two or more packet processing elements for processing of the packets, including distributing a packet of the plurality of packet to a first packet processing element for processing of the packet by the first packet processing element; queuing, at a first ordering unit, a first instance of the packet according to an order of the packet within the data flow; causing the first instance of the packet to be transmitted when both of (i) processing of the first instance of the packet is completed and (ii) the first instance of the packet is at a head of a queue at the first ordering unit; queuing, at a second ordering unit, a second instance of the packet according to the order of the packet within the data flow; and causing the second instance of the packet to be transmitted when both of (i) processing of the second instance of the packet is completed and (ii) the second instance of the packet is at a head of a queue at the second ordering unit. ### Claim 2 (depends on 1) The method of claim 1, further comprising assigning, by the first ordering unit, a first packet ID to the packet, wherein queuing the first instance of the packet comprises queuing the first packet ID assigned to the packet. ### Claim 3 (depends on 2) The method of claim 2, further comprising: issuing, by the first packet processing element, a first instruction indicating that processing of the first instance of the packet has been completed, and storing the instruction at the first ordering device; wherein causing the first instance of the packet to be transmitted when the first instance of the packet is at the head of the queue at the first ordering device is based on the stored first instruction. ### Claim 4 (depends on 3) The method of claim 3, wherein the first instruction includes at least (i) the first packet ID and (ii) an indication that the first instance of the packet is not a last instance of the packet to be transmitted by the network device. ### Claim 5 (depends on 4) The method of claim 4, further comprising, after causing the first instance of the packet to be transmitted: assigning, by the second ordering unit, a second packet ID to the packet; providing the second packet ID to the first packet processing element; issuing, by the first packet processing element, a second instruction indicating that processing of the second instance of the packet has been completed; and providing the second instruction to the second ordering unit, wherein the second instruction includes the second packet ID. ### Claim 6 (depends on 5) The method of claim 5, wherein assigning the first packet ID to the packet comprises assigning the first packet ID from a pool of non-sequential free packet IDs local to the first ordering unit; and assigning the second packet IP to the packet comprises assigning the second packet ID from a pool of non-sequential free packet IDs local to the second ordering unit. ### Claim 7 (depends on 6) The method of claim 6, wherein causing the first instance of the packet to be transmitted includes: forwarding the first instance of the packet to a target port for transmission of the first instance of the packet via the target port; removing the first packet ID from a queue in which the first packet ID is queued at the first ordering unit; and returning the first packet ID to the pool of free packet IDs at the first ordering unit. ### Claim 8 (depends on 5) The method of claim 5, further comprising after causing the first instance of the packet to be transmitted, sending a request for the second packet ID from the first ordering unit to the second ordering unit, wherein assigning the second packet ID is performed by the second ordering unit in response to receiving the request from the first ordering unit. ### Claim 9 (depends on 1) The method of claim 1, wherein queuing the first instance of the packet includes: queuing the first instance of the packet in a default class queue, assigning the first instance of the packet to a packet class, and when the first instance of the packet reaches a head of the default class queue, moving the first instance of the packet from the head of the default class queue to a tail of a queue that corresponds to the assigned packet class. ### Claim 10 (depends on 8) The method of claim 8, wherein queuing the first instance of the packet in the default class queue comprises queuing the first instance of the packet in a default class queue corresponding to a source port via which the packet was received by the network device. ### Claim 11 A network device, comprising: a plurality of network ports configured to receive and to transmit packets on a network; a plurality of packet processing elements configured to process packets received via the network ports; and a plurality of ordering including at least a first ordering unit and a second ordering unit, the first ordering unit configured to: distribute a plurality of packets among two or more packet processing elements for processing of the packets, wherein the plurality of packets belong to a data flow; queue a first instance of a packet of the plurality of packets according to an order of the packet within the data flow; cause the first instance of the packet to be transmitted when both of (i) processing of the first instance of the packet is completed and (ii) the first instance of the packet is at a head of a queue at the first ordering unit; and cause a second instance of the packet to be queued at a second instance of the packet according to an order of the packet within the data flow; and wherein the second ordering unit is configured to cause the second instance of the packet to be transmitted when both of (i) processing of the second instance of the packet is completed and (ii) the second instance of the packet is at a head of a queue at the second ordering unit. ### Claim 12 (depends on 11) The network device of claim 11, wherein the first ordering unit is further configured to assign a first packet ID to the packet, and wherein queuing the first instance of the packet comprises queuing the first packet ID assigned to the packet. ### Claim 13 (depends on 12) The network device of claim 12, wherein the first ordering unit is further configured to: receive, from the first ordering unit, a first instruction indicating that processing of the first instance of the packet has been completed, store the first instruction; and cause the first instance of the packet to be transmitted (i) when the first instance of the packet is at the head of the queue in which the first instance of the packet is queued and (i) based on the stored first instruction. ### Claim 14 (depends on 13) The network device of claim 13, wherein the first instruction includes (i) the first packet ID and (ii) an indication that the first instance of the packet is not a last instance of the packet to be transmitted by the network device. ### Claim 15 (depends on 13) The network device of claim 13, wherein the first ordering unit is configured to, after causing the first instance of the packet to be transmitted: forward, to the second ordering unit, a request for the second ordering unit to assign a second packet ID to the packet; receive, from the second ordering unit, the second packet ID assigned to the packet by the second ordering unit; and provide the second packet ID to a packet processing element processing the packet. ### Claim 16 (depends on 15) The network device of claim 15, wherein the packet processing is configured to issue a second instruction indicating that processing of the second instance of the packet has been completed; and provide the second instruction to the second ordering unit, wherein the second instruction includes the second packet ID. ### Claim 17 (depends on 15) The network device of claim 15, wherein the first ordering unit is configured to assign the first packet ID from a pool of non-sequential free packet IDs local to the first ordering unit; and the second ordering unit is configured to assign the second packet ID from a pool of non-sequential free packet IDs local to the second ordering unit. ### Claim 18 (depends on 17) The network device of claim 17, wherein the first ordering unit is configured to case the first instance of the packet to be transmitted at least by: sending the first instance of the packet to a target port for transmission of the first instance of the packet from the target port; removing the first packet ID from a queue in which the first packet ID is queued at the first ordering unit; and returning the first packet ID to the pool of free packet IDs at the first ordering unit. ### Claim 19 (depends on 11) The network device of claim 11, wherein a packet processing element is configured to assign the packet to a packet class, and wherein the first ordering unit is further configured to, prior to the packet being assigned to the packet class, queue the first instance of the packet in a queue corresponding to a default packet class. ### Claim 20 (depends on 19) The network device of claim 19, wherein the default class queue corresponds to a source port via which the packet was received by the network device.