Patent Description:
Network protocols, such as Transmission Control Protocol (TCP) utilize a retransmission timer to ensure that data that has not been acknowledged by the receiver is retransmitted. For example, such a timer may be set to a default value or a value based upon a measured round trip time between the sender and the receiver. When the timer expires before receiving acknowledgement of a packet, the packet is retransmitted and the length of the timer may be increased. With greater and varied amounts of packet loss, e.g., with wireless network connections, delivery of data may be slowed by waiting for the expiration of a retransmission timer to retransmit lost packets.

Document <CIT> discloses a method in which a last packet is duplicated and the acknowledgement of the duplicate additional packet generates the retransmission of the unacknowledged packets in the sequence. In one embodiment of the method the number of repetitions is adapted according to packet loss.

There is a need for apparatuses and methods for managing packet loss by dynamically determining a number of duplicate copies of packets to transmit within a sequence of packets. Such systems and methods optionally complement or replace conventional systems for managing packet loss.

In accordance with some embodiments, a method includes the steps of independent claim <NUM>.

The dependent claims address other embodiments of the invention.

In accordance with some embodiments, a non-transitory computer-readable medium stores instructions, which, when executed by a processing device, cause the processing device to perform a method according to any of claims <NUM> to <NUM>.

In accordance with some embodiments, an apparatus comprises a processing device and a memory coupled to the processing device. The memory stores instructions which, when executed by the processing device, cause the apparatus to perform a method according to any of claims <NUM> to <NUM>.

The present embodiments are illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements, and in which:.

This document describes embodiments that manage packet loss by dynamically determining a number of duplicate copies of packets to transmit within a sequence of packets and utilizing acknowledgements of duplicated packets to detect the loss of non-duplicated packets. For example, embodiments create one or more duplicates of a packet within a plurality of packets to be transmitted to a destination computing node as a sequence of packets. The plurality of packets, including the one or more duplicates of the packet, are transmitted to the destination computing node. In transmitting multiple copies of the packet, the probability of the destination computing node receiving and acknowledging the packet increases. Upon receiving a first acknowledgement of the packet from the destination computing node, embodiments determine that the first acknowledgment is directed to a duplicated packet. In response to determining that the acknowledgment is directed to a duplicated packet, embodiments determine if an acknowledgement has not been received for one or more packets within the plurality of packets transmitted prior to the original copy of packet in the sequence. In response to determining that an acknowledgement has yet to be received for any of the one or more packets transmitted prior to the packet, embodiments retransmit the corresponding one or more packets to the destination computing node. In an embodiment, the number of packets to be duplicated and/or the number of duplicate copies created are set based upon a determined amount of packet loss. As a result, embodiments detect and react to the loss of packets prior to the expiration of a retransmission timer while dynamically adjusting the amount of duplicate packets transmitted.

<FIG> illustrates, in block diagram form, exemplary network <NUM> including processing devices, one or more of which implement embodiments of management of packet loss as described within this document. Data content is transmitted across network <NUM>, e.g., from origin <NUM> to destination <NUM>. The data is transmitted along a path that includes egress node <NUM>, intermediate node(s) <NUM>, and ingress node <NUM> before reaching destination <NUM>. Origin <NUM> represents one or more processing devices such as an end user device (e.g., personal computer, mobile device, etc.) and/or servers. Similarly, destination <NUM> represents one or more processing devices such as an end user device (e.g., personal computer, mobile device, etc.) and/or servers. In one embodiment, destination <NUM> is an end user device coupled to network <NUM> via a wireless connection.

In one embodiment, one or more of egress node <NUM>, intermediate node(s) <NUM>, and ingress node <NUM> are a part of a content delivery network (CDN). The CDN includes a geographically distributed set of network server nodes deployed in multiple data centers. The CDN network server nodes are configured to serve content with high availability and performance.

Ingress Node <NUM> is illustrated as including hardware <NUM>. Each of origin <NUM>, egress node <NUM>, intermediate node(s) <NUM>, and destination <NUM> may also include similar hardware. Hardware <NUM> includes one or more processors ("CPU(s)"), data storage and memory (e.g., "RAM"), and network interface controllers ("NIC(s)"). The data storage and memory may be used for storing data, metadata, and programs for execution by the processor(s). The data storage and memory may include one or more of volatile and nonvolatile memories, such as Random Access Memory ("RAM"), Read Only Memory ("ROM"), a solid state disk ("SSD"), Flash, Phase Change Memory ("PCM"), or other types of data storage, such as magnetic disk drives, optical disk drives, etc. The memory may be internal or distributed memory. One or more buses (not shown) may be used to interconnect the various components of hardware <NUM>. Additionally, NIC(s) may be used to connect ingress node <NUM>, via a wired or wireless network, with intermediate node(s) <NUM> and destination <NUM>.

Ingress Node <NUM> is illustrated as also including packet loss module <NUM>. In one embodiment, packet loss module <NUM> monitors packet loss using duplicate packets and retransmits lost packets, e.g., as described with reference to <FIG>. In one embodiment, each of one or more of egress node <NUM> and intermediate nodes <NUM> also includes packet loss module <NUM>.

<FIG> illustrates exemplary bursts <NUM>, <NUM>, and <NUM> of packets including extra copies of a subset of packets. As illustrated, each of bursts <NUM>, <NUM>, and <NUM> includes a sequence of <NUM> packets. Bursts of packets, however, may include fewer or more packets than illustrated in this example. Each of bursts <NUM>, <NUM>, and <NUM> is illustrated as including duplicates of every Nth packet, where N = <NUM>. Duplicating every Nth packet provides for a minimum number of non-duplicated packets to be transmitted between duplicated packets. Duplicate copies of packets are illustrated with an asterisk to emphasize in the illustration that they are duplicates. For example, duplicate <NUM> is a copy of the fifth packet in the sequence, duplicate <NUM> is a copy of the tenth packet in the sequence, duplicate <NUM> is a copy of the fifteenth packet in the sequence, and duplicate <NUM> is a copy of the twentieth packet in the sequence. This pattern of duplication continues through the remainder of the sequence, as represented by the ellipses in <FIG>. As described with reference to <FIG>, the value of N may be variable and set based upon a default value or based upon a determined amount of packet loss in transmitting packets to destination <NUM>.

In one embodiment, X copies of each duplicated packet is created and inserted into the sequence. For example, one or more copies of each duplicated packet may be inserted following the original copy of that packet and/or at the end of the sequence of packets. The greater the value of X, the greater the likelihood that destination <NUM> will receive and acknowledge the duplicated packet. bursts <NUM> and <NUM> is illustrated as having only a single duplicate <NUM> following immediately after the fifth packet. Similarly, burst <NUM> is illustrated as having only a single duplicate <NUM> following immediately after the one hundredth packet. In one embodiment, however, multiple duplicates <NUM> may follow immediately after the fifth packet (e.g., prior to the non-duplicated, sixth packet in the sequence), after the one hundredth packet, or elsewhere to increase the likelihood of receiving an acknowledgement of the fifth packet in the sequence. Similarly, multiple duplicates <NUM>, <NUM>, <NUM>, etc. may be inserted immediately following their corresponding original packets or following the last packet in a burst. As described with reference to <FIG>, the value of X may be variable and set based upon a default value or based upon a determined amount of packet loss in transmitting packets to destination <NUM>.

In one embodiment, one or more copies of each duplicated packet (e.g., as defined by X as described above) is inserted following the original copy of that packet and following each subsequent duplicated packet in the sequence. For example, as illustrated, duplicate <NUM> of the fifth packet is inserted after the fifth packet and after each of the subsequent Nth packets (tenth, fifteenth, twentieth, etc.). Duplicate <NUM> of the tenth packet is inserted after the tenth packet and each of the subsequent Nth packets (fifteenth, twentieth, etc.). Distributing duplicates throughout burst <NUM> increases the likelihood that destination <NUM> will receive and acknowledge the duplicated packet even when there is a cluster of lost packets. Alternatively, the one or more copies of each duplicated packet is inserted only following the corresponding original copy of that packet and not following each subsequent duplicated packet in the sequence.

In another embodiment, a maximum number, M, of duplicated packets in the sequence is inserted at each point in in the burst. For example, as illustrated in burst <NUM>, M = <NUM>, so only two instances of duplicate packets are inserted at each point in burst <NUM>. Duplicate <NUM> of the fifth packet is inserted after the fifth packet. There are no other duplicate packets at this point, so only a single duplicate is inserted. Duplicate <NUM> of the fifth packet and duplicate <NUM> of the tenth packet are inserted after the tenth packet. Following the fifteenth packet, however, duplicate <NUM> of the fifth packet is not inserted again. In this example, when the number of duplicate packets would exceed M, the earliest packet(s) in the burst are dropped from being duplicated. As such, duplicate <NUM> of the tenth packet and duplicate <NUM> of the fifteenth packet are inserted following the fifteenth packet and duplicate <NUM> of the fifth packet is not. Similarly, duplicate <NUM> of the fifteenth packet and duplicate <NUM> of the twentieth packet are inserted following the twentieth packet and duplicates <NUM> and <NUM> are not.

In one example, not covered by the invention as defined in the appended claims, one or more copies of each duplicated packet (e.g., as defined by X as described above) is inserted at the end of the burst of packets. For example, burst <NUM> does not include duplicates distributed throughout as illustrated in bursts <NUM> and <NUM>. Instead, burst <NUM> only include the duplicates at the end of the burst. In another example, the burst of packets may include one or more duplicates immediately following the original packet (e.g., duplicate <NUM> following the fifth packet in the sequence) and at the end of the burst (e.g., duplicate <NUM> following the hundredth packet in the sequence) but not otherwise distributed throughout (e.g., no duplicate <NUM> following the tenth, fifteenth, etc. packets). In yet another example, as illustrated, burst <NUM> may include duplicates distributed throughout and at the end of the burst.

<FIG> is a flow chart illustrating exemplary method <NUM> of managing packet loss. At block <NUM>, packet loss module <NUM> creates one or more duplicates of every Nth packet within a sequential set of packets. For example, as described with reference to <FIG>, X duplicates may be created of every Nth packet. Packet loss module may use default values of X and N or set the values of X and N based upon an estimated packet loss value, as described with reference to block <NUM> below.

At block <NUM>, packet loss module <NUM> stores the sequence numbers (or other identifiers that uniquely identify packets within a burst, hereinafter "sequence numbers") of the packets that were duplicated. These sequence numbers indicate "marker packets" that have an increased likelihood of being received and acknowledged by destination <NUM>. The sequence numbers for these marker packets are saved to enable packet loss module <NUM> to compare them against sequence numbers received in acknowledgements from destination <NUM>.

At block <NUM>, packet loss module <NUM> transmits the sequential set of packets along with the duplicate copies to destination <NUM>. As described with reference to <FIG>, the duplicate copies may be inserted following the corresponding original copy, distributed throughout the sequence, and/or at the end of the set of packets.

At block <NUM>, packet loss module <NUM> receives an acknowledgement from destination <NUM>. For example, packet loss module <NUM> may receive an acknowledgement or selective acknowledgment according to Internet Engineering Task Force (IETF) RFC <NUM> TCP Selective Acknowledgment Options. In one embodiment, the received acknowledgement includes the sequence number (or other unique identifier) of the packet received by destination <NUM>.

At block <NUM>, packet loss module <NUM> determines if the received acknowledgement includes the sequence number (or other unique identifier) of a duplicated marker packet. If the received acknowledgement does not include the sequence number of a duplicated marker packet, at block <NUM>, packet loss module optionally stores a copy of the acknowledged non-duplicated packet sequence number(s) or otherwise updates a value representing acknowledged packets to track which packets have been successfully transmitted and do not need to be retransmitted.

At block <NUM>, packet loss module <NUM> determines if additional packets within the set have yet to be acknowledged. If all packets have been acknowledged, method <NUM> returns to block <NUM> to transmit another burst of packets. If additional packets within the set have yet to be acknowledged, method <NUM> returns to block <NUM> to await additional acknowledgments.

If a received acknowledgement includes the sequence number of a duplicated marker packet, at block <NUM>, packet loss module <NUM> determines if any non-duplicated packets that are prior to the duplicated packet in the sequence lack an acknowledgement. For example, packet loss module <NUM> may store acknowledged sequence numbers as described with reference to block <NUM> and determine which packets prior to the presently acknowledged packet are missing from that data structure or other representation. Alternatively, the received acknowledgement may indicate multiple sets of one or more packets received and, therefore, imply which packets have not been acknowledged.

In one example not covered by the present invention, packet loss module <NUM> determines if any of the N-<NUM> non-duplicated packets that are prior to the current duplicated packet in the sequence lack an acknowledgement. Using the example illustrated in <FIG>, if packet loss module <NUM> receives acknowledgement of the tenth packet in the sequential set of packets and determines that the tenth packet has been duplicated (e.g., duplicate <NUM>), packet loss module <NUM> determines if the sixth through ninth packets have been acknowledged (e.g., in burst <NUM>, N = <NUM>, N-<NUM> = <NUM>, and the <NUM> packets prior to the tenth packet in the sequence are the sixth, seventh, eighth, and ninth packets). In the present invention, packet loss module <NUM> determines if any packets that are prior to the current duplicated packet in the sequence lack an acknowledgement (e.g., for acknowledgement of the tenth packet in burst <NUM>, the first through the ninth packets are evaluated for lack of acknowledgement).

If prior packets are lacking acknowledgement, at block <NUM>, packet loss module <NUM> retransmits copies of the prior packets determined to be lacking acknowledgement. As a result, packet loss module <NUM> is able to retransmit packets lacking acknowledgement in response to receiving acknowledgement of a duplicated marker packet and, e.g., without waiting for the expiration of a retransmission timer.

If no prior packets are lacking acknowledgment or following retransmission of unacknowledged packets, at block <NUM>, packet loss module <NUM> optionally updates an estimated packet loss value for transmitting packets to destination <NUM>. For example, packet loss module <NUM> may calculate a percentage or other value representing the packet loss for packets transmitted to destination <NUM>. If one packet in a sequence of twenty is lost, packet loss module <NUM> may calculate a <NUM>% packet loss value for transmitting packets to destination <NUM>.

In one embodiment, the estimated packet loss value is mapped to a value of X and/or a value of N to be used when duplicating packets in subsequent bursts. For example, packet loss module <NUM> may utilize a data structure to map packet loss values, or ranges of packet loss values, to a value of X and/or a value of N. As the packet loss value increases, so do the value(s) of X and/or N. In one embodiment, packet loss module <NUM> determines if the packet loss value exceeds a threshold and, if so, determines that no duplication of packets is necessary. For example, if packet loss exceeds <NUM>% or another threshold value, packet loss module <NUM> may determine that destination <NUM> is likely to lose a wireless connection or that retransmission of packets according to method <NUM> is not beneficial.

Following the optional block <NUM>, method <NUM> returns to block <NUM> to determine if additional packets within the sequential set of packets remain to be acknowledged.

It will be apparent from this description that aspects of the inventions may be embodied, at least in part, in software. That is, packet loss module <NUM> and/or computer-implemented method <NUM> may be implemented or otherwise carried out in a computer system or other data processing system, such as nodes <NUM>, <NUM>, and/or <NUM>, in response to its processor executing sequences of instructions contained in a memory or other non-transitory machine-readable storage medium. The software may further be transmitted or received over a network (not shown) via a network interface. In various embodiments, hardwired circuitry may be used in combination with the software instructions to implement the present embodiments. Thus, the techniques are not limited to any specific combination of hardware circuitry and software, or to any particular source for the instructions executed by a node <NUM>, <NUM>, and/or <NUM>. It will also be appreciated that additional components, not shown, may also be part of nodes <NUM>, <NUM>, and/or <NUM>, and, in certain embodiments, fewer components than that shown in <FIG> may also be used in nodes <NUM>, <NUM>, and/or <NUM>.

An article of manufacture may be used to store program code providing at least some of the functionality of the embodiments described above. Additionally, an article of manufacture may be used to store program code created using at least some of the functionality of the embodiments described above. An article of manufacture that stores program code may be embodied as, but is not limited to, one or more memories (e.g., one or more flash memories, random access memories - static, dynamic, or other), optical disks, CD-ROMs, DVD-ROMs, EPROMs, EEPROMs, magnetic or optical cards, solid state drives (SSD), or other type of non-transitory computer-readable media suitable for storing electronic instructions. Additionally, embodiments of the invention may be implemented in, but not limited to, hardware or firmware utilizing an FPGA, ASIC, a processor, a computer, or a computer system including a network. Modules and components of hardware or software implementations can be divided or combined without significantly altering embodiments of the invention.

In the foregoing specification, the invention(s) have been described with reference to specific exemplary embodiments thereof. Various embodiments and aspects of the invention(s) are described with reference to details discussed in this document, and the accompanying drawings illustrate the various embodiments. The description above and drawings are illustrative of the invention and are not to be construed as limiting the invention. References in the specification to "one embodiment," "an embodiment," "an exemplary embodiment," etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but not every embodiment may necessarily include the particular feature, structure, or characteristic. Furthermore, when a particular feature, structure, or characteristic is described in connection with an embodiment, such feature, structure, or characteristic may be implemented in connection with other embodiments whether or not explicitly described. Additionally, as used in this document, the term "exemplary" refers to embodiments that serve as simply an example or illustration. The use of exemplary should not be construed as an indication of preferred examples. Blocks with dashed borders (e.g., large dashes, small dashes, dot-dash, dots) are used to illustrate virtualized resources or, in flow charts, optional operations that add additional features to embodiments of the invention. However, such notation should not be taken to mean that these are the only options or optional operations, and/or that blocks with solid borders are not optional in certain embodiments of the invention.

Claim 1:
A computer-implemented method, comprising:
duplicating a first packet within a first plurality of packets to be transmitted to a destination computing node (<NUM>) as a first sequence of packets;
duplicating a second packet within a second plurality of packets to be transmitted to the destination computing node (<NUM>) as a second sequence of packets, wherein the second sequence of packets is subsequent to the first sequence of packets;
transmitting the first plurality of packets including the duplicate of the first packet to the destination computing node (<NUM>);
subsequent to transmitting the first plurality of packets, transmitting the second plurality of packets including the duplicate of the second packet to the destination computing node (<NUM>);
receiving a first acknowledgement from the destination computing node (<NUM>), wherein the first acknowledgement includes a unique identifier of a packet received by the destination computing node (<NUM>);
determining that the first acknowledgment is directed to the second packet or a duplicate of the second packet; and
in response to determining that the first acknowledgment is directed to the second packet or a duplicate of the second packet:
determining that a corresponding further acknowledgement including a unique identifier of a respective packet prior to the current duplicated packet has yet to be received for each of the one or more packets transmitted prior to the second packet;
in response to determining that an acknowledgement has yet to be received for any of the one or more packets transmitted prior to the second packet, retransmitting the corresponding one or more packets to the destination computing node (<NUM>).