US 11,381,514 B2Granted

Methods and apparatus for early delivery of data link layer packets

AssigneeApple Inc.

InventorsKaran Sanghi, Saurabh Garg, Cahya Adiansyah Masputra

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and apparatus for non-sequential packet transfer. Prior art multi-processor devices implement a complete network communications stack at each processor. The disclosed embodiments provide techniques for delivering network layer (L3) and/or transport layer (L4) data payloads in the order of receipt, rather than according to the data link layer (L2) order. The described techniques enable e.g., earlier packet delivery. Such design topologies can operate within a substantially smaller memory footprint compared to prior art solutions. As a related benefit, applications that are unaffected by data link layer corruptions can receive data immediately (rather than waiting for the re-transmission of an unrelated L4 data flow) and thus the overall network latency can be greatly reduced and user experience can be improved.

Claims14

Dependent claims

A processor apparatus configured to support non-sequential delivery of data packets, the processor apparatus comprising:

a first data interface;
a second data interface configured to interface to another processor apparatus;
a data processing element;
and
a non-transitory computer-readable medium comprising one or more instructions configured to, when executed by the data processing element, cause the processor apparatus to:
receive a plurality of transmissions, each transmission containing the data packets for delivery to one of a first application or a second application operable by the another processor apparatus;
responsive to a determination that the another processor apparatus supports non-sequential delivery of the data packets:
provide the data packets to the another processor apparatus in a non-sequential order, the data packets comprising information relating to (i) a network port associated with a corresponding one of the first application or the second application, (ii) an endpoint-to-endpoint transport order associated with a subset of the data packets that are designated for a particular one of the first and second applications, and (iii) an over-the-air transport order associated with at least some of the data packets that defines an order in which the data packets are transmitted relative to other data packets of the plurality of transmissions;
and
cause the another processor apparatus to route the subset of the data packets to the particular one of the first and second applications via the network port on a transmission-by-transmission basis provided that the endpoint-to-endpoint transport order indicates that the subset of the data packets are sequentially contiguous with data packets already sent to the particular one of the first and second applications or with data packets stored in a memory of the another processor apparatus,
store, in the memory of the another processor apparatus, the subset of the data packets provided that the endpoint-to-endpoint transport order indicates that the subset of the data packets are not sequentially contiguous with data packets already sent or with data packets stored in the memory of the another processor apparatus;
and
receive a request to retransmit at least one missing intervening data packet based on a flush event, the missing intervening packet being identified based on the endpoint-to-endpoint transport order.

10 more elements

A processor apparatus configured to receive non-sequential delivery of data packets, the processor apparatus comprising:

a first interface configured to receive a plurality of data packets;
a memory structure;
a digital processor;
and
a non-transitory computer-readable medium comprising one or more instructions which are configured to, when executed by the digital processor, cause the processor apparatus to:
execute a plurality of applications;
identify a plurality of data flows from another processor apparatus, the plurality of data flows corresponding to the plurality of applications, where each data flow of the plurality of data flows comprises a respective subset of the plurality of data packets;
and
for the each data flow of the plurality of data flows:
responsive to the respective subset being successfully received, determine a first data packet order for the respective subset, and determine a second data packet order for the plurality of data packets, the first data packet order received at a first portion of the memory structure, and the second data packet order received at a second portion of the memory structure;
and
re-order the respective subset according to the first data packet order;
provide the each data flow to a corresponding one of the plurality of applications in accordance with the re-ordered subset of the plurality of data packets provided that the re-ordered subset of the plurality of data packets are sequentially contiguous with data packets already sent to the corresponding one of the plurality of applications, and provide the plurality of data packets to the plurality of applications in accordance with the second data packet order;
store, in the memory structure, the re-ordered subset of the plurality of data packets provided that the first data packet order indicates that the re-ordered subset of the plurality of data packets is not sequentially contiguous with data packets already sent to the corresponding one of the plurality of applications;
identify at least one missing intervening data packet based on the first data packet order;
and
request re-transmission of the at least one missing intervening data packets based on a flush event,
wherein the first data packet order defines a relationship between packets of the subset of data packets within a corresponding data flow, and
wherein the second data packet order defines an order in which the plurality of data packets were transmitted.

16 more elements

A method for non-sequential delivery of packets, comprising:

executing a plurality of applications;
identifying a plurality of data flows corresponding to the executed plurality of applications;
receiving sets of data packets corresponding to various ones of the plurality of data flows, each of the sets of data packets comprising:
(i) first metadata indicative of a corresponding one of the plurality of applications;
(ii) second metadata indicative of a transport order associated with the set of data packets, the transport order defining an order of the packets within a corresponding set of data packets;
and
(iii) third metadata indicative of another transport order associated with the plurality of data flows, the another transport order defining an order in which the data packets were transmitted;
identifying, based on the second metadata of the data packets being non-sequentially contiguous, that an intervening data packet associated with one data flow of the plurality of data flows is missing;
waiting to retrieve the data packets associated with the one data flow in response to the identifying;
storing in a memory, the data packets whose second metadata is later in sequence from that of the missing intervening data packet;
retrieving and routing the stored data packets associated with the one data flow to the corresponding application based on the first metadata, and based on the missing intervening data packet being successfully received;
and
requesting re-transmission of the missing intervening data packet based on a flush event,
wherein the identifying of the plurality of data flows is based at least on (i) one or more of a network address or network port and (ii) the second metadata associated with an application, and
wherein the identifying of the missing intervening data packets is based on the second metadata.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/973,153Filed 7 May 2018
Published: US 2019/0342225 A17 Nov 2019
Granted: 5 Jul 2022
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

H04L 47/624
Characterised by scheduling criteria: altering the ordering of packets in an individual queue
H04L 45/30
Routing or path finding of packets in data switching networks: routing of multiclass traffic
H04L 47/6205
Characterised by scheduling criteria: arrangements for avoiding head of line blocking
H04L
Digital communication