TECHNICAL FIELD

The present disclosure relates to a receiver-agnostic scheme for reliable delivery of data over multipath from a sender device to a receiver device. The sender device of this disclosure can select, for each of a plurality of data packets to be sent to the receiver device, one of multiple paths for sending the data packet. The sender device of this disclosure is further able to apply a transport protocol using selective-repeat for the multipath sending of the data packets.

BACKGROUND

In modem datacenters, data packets can be lost due to congestion. Thus, a protocol for a reliable transmission of data packets is needed. Examples for such protocols are transmission control protocol (TCP) and remote direct memory access (RDMA). In these protocols, the receiver device informs the sender device about which data packets have been received, and the sender device decides which data packets have to be retransmitted. In some cases, to increase throughput and decrease latency, the sender device can split its traffic over multiple paths to the receiver device. This is called "multipath transport".

However, when such multipath transport is used, data packets may be received out of order at the receiver device, which complicates the decision about which packet to retransmit, and when to retransmit, at the sender device. For this reason, multipath transport does not always improve the throughput, and its contribution depends on which paths are used, what is the load on these paths, and what is the load on the alternative paths.

SUMMARY

This disclosure and its solutions are based further on the following considerations.

The sender device may determine in real-time, whether it is beneficial to add a path or to remove a path, in order to use the multipath transport in the best way. It may be much more efficient to allow the sender device to make such decisions without involving the receiver device, in which case the receiver device is agnostic to whether one path or multiple paths are used, and to which paths are used. This disclosure aims to propose a scheme for combining reliable transmission of data packets with multipath, such that the receiver device does not have to know if the sender device uses a single path or multiple paths. A goal is that the receiver device can work in the same way in both cases. Thereby, the disclosure is concerned with a scenario where the sender device and the receiver device support selective-repeat. Another goal is to enable the sender device to decide how many paths to use, without coordinating this with the receiver device. Moreover, the disclosure aims for a sender device that is able to dynamically change the paths it uses, for example, according to their availability and according to congestion control considerations.

This is achieved by the solution of this disclosure as described in the independent claims. Advantageous implementations are defined in the dependent claims.

A first aspect of this disclosure provides a sender device for sending data packets to a receiver device, the sender device being configured to: determine a set of one or more paths between the sender device and the receiver device; select, for each data packet, one of the paths of the set of paths for sending the data packet to the receiver device; maintain, for each data packet, path information indicating the selected path on which the data packet was sent to the receiver device; receive a feedback message from the receiver device, wherein the feedback message comprises status information for each of one or more data packets; and determine, based on the feedback message, whether to consider a missing data packet lost and whether to retransmit the missing data packet, based on the path information of the missing data packet and the status information for one or more other data packets transmitted on the same path to the receiver device as the missing data packet.

The sender device is configured to determine, whether a missing data packet should be considered lost, based on the path information of the missing data packet and based on the status information included in the feedback message for the one or more other data packets transmitted on the same path to as the missing data packet. The sender device decides whether and when to retransmit a lost data packet based on the rules of the underlying single-path transport protocol. Notably, a missing data packet may be a data packet that was not received at the receiver device, although a data packet with a higher sequence number has been received. A missing data packet may be considered lost by the sender device, and in this case it may be retransmitted by the sender device. However, due to the possibility of the one or more paths for sending the data packets, not each missing data packet at the receiver device has to be considered lost by the sender device.

The sender device of the first aspect can thus support multi-path selective-repeat, which involves retransmitting missing data packets that are considered lost, and thus provides a scheme for a reliable transmission of data packets with multipath. The receiver device in this disclosure may be agnostic to the selected path, and does not have to know if the sender device uses a single path or multiple paths. The receiver device functionality may be the same in both cases, and the receiver device can be a conventional receiver device that supports a standard (single-path) selective-repeat based protocol.

The sender device can decide how many paths to use without coordinating this with the receiver device. Moreover, the sender device can dynamically change the set of paths it uses, for instance, according to availability of paths and according to one or more congestion control considerations. The decision which data packet to send on which path of the set of paths can be taken by the sender device according to a per-path congestion control, or in any other way. Only one set of sequence number space may be used, i.e., each data packet may only have one sequence number. This may mean that only one data packet is assigned a specific sequence number, i.e., the specific sequence number is not assigned two more than one data packet. This may be in contrast to other multipath transport protocols, such as multipath TCP, which use two sequence number spaces, i.e., two sequence numbers per data packet, one per path and one for the whole connection.

In an implementation form of the first aspect, the status information of each data packet indicates whether that data packet has been received by the receiver device or is missing at the receiver device.

The sender device may thus determine missing packets that are considered lost based on the status information, and may base also the decision on whether to use retransmission of such data packets considered lost based on the status information.

In an implementation form of the first aspect, the sender device is configured to, if the feedback message indicates that a received data packet with a sequence number larger than a sequence number of the missing data packet has been received at the receiver device: not consider the missing data packet lost and not retransmit the missing data packet, if the received data packet was sent on a different path to the receiver device than the missing data packet.

This may avoid that the missing data packet is retransmitted, although it is only temporarily missing (not completely lost), because it is sent on the different path.

In an implementation form of the first aspect, the sender device is configured to consider the missing data packet lost and retransmit the missing data packet, if the received data packet was sent on the same path to the receiver device as the missing data packet, and if retransmission is required by the underlying transport protocol used for sending the data packets.

In this case, the missing data packet is considered lost, and may be retransmitted for reasons of reliability.

In an implementation form of the first aspect, the sender device is configured to retransmit the missing data packet on the same path on which it was transmitted for the first time to the receiver device.

This simplifies the tracking of the data packets sent on the various paths.

In an implementation form of the first aspect, the sender device is configured to: receive a further feedback message from the receiver device, wherein the further feedback message indicates that a further received data packet with a sequence number larger than a sequence number of the missing data packet has been received at the receiver device; and consider the missing data packet lost and retransmit the missing data packet, if the further received data packet was sent on the same path to the receiver device as the missing data packet, and if retransmission is required by the underlying transport protocol used for sending the data packets.

That is, with each received feedback message, wherein feedback messages may be received periodically or after certain events from the receiver device, the sender device may reevaluate whether to consider a missing data packet lost and accordingly retransmit the missing data packet. In an implementation form of the first aspect, the sender device is configured to, in order to determine the set of paths, select the one or more paths from all available paths between the sender device and the receiver device.

In an implementation form of the first aspect, the sender device is configured to determine the set of paths based on a result of performing a per-path congestion control on available paths between the sender device and the receiver device.

This may avoid that data packets sent over these path are delayer or lost due to congestion.

In an implementation form of the first aspect, the sender device is configured to select, for each data packet, the path for sending that data packet to the receiver device based on one or more congestion control considerations.

For instance, the sender device may determine on which path to send a certain data packet based on considerations regarding the certain data packet (e.g., a priority) and/or considerations regarding the paths (e.g., current congestion, time required over this path, etc.)

In an implementation form of the first aspect, the sender device is configured to add a new path to the set of paths.

In an implementation form of the first aspect, the sender device is configured to delete a path from the set of paths.

In an implementation form of the first aspect, the sender device is configured to, in order to delete the path from the set of path: stop sending data packets on the path to be deleted; retransmit any missing data packet on the path to be deleted; and if all data packets, which were transmitted or retransmitted on the path to be deleted, are received at the receiver device, remove the path to be deleted from the set of paths.

In this way, the path can be deleted without impairing the transmission of the data packets. In an implementation form of the first aspect, the sender device is configured to, if a path fails, on which one or more missing data packets are to be retransmitted, retransmit the one or more missing data packets on one or more other paths of the set of paths.

Thus, reliability of sending the data packets is improved.

In an implementation form of the first aspect, the feedback message is an acknowledgment, (ACK) message, or a negative ACK (NACK) message, or a selective ACK (SACK) message.

A second aspect of this disclosure provides a method for sending data packets from a sender device to a receiver device, the method comprising: determining a set of one or more paths between the sender device and the receiver device; selecting, for each data packet, one of the paths of the set of paths for sending the data packet to the receiver device; maintaining, for each data packet, path information indicating the selected path on which the data packet was sent to the receiver device; receiving a feedback message from the receiver device, wherein the feedback message comprises status information for each of one or more data packets; and determining, based on the feedback message, whether to consider a missing data packet lost and whether to retransmit the missing data packet, based on the path information of the missing data packet and the status information for one or more other data packets transmitted on the same path to the receiver device as the missing data packet.

In an implementation form of the second aspect, the status information of each data packet indicates whether that data packet has been received by the receiver device or is missing at the receiver device.

The method may comprises determining missing packets based on the status information, and also the decision on whether to consider missing data packets lost and accordingly use retransmission may be based on the status information.

In an implementation form of the second aspect, the method comprises, if the feedback message indicates that a received data packet with a sequence number larger than a sequence number of the missing data packet has been received at the receiver device: not considering the missing data packet lost and not retransmitting the missing data packet, if the received data packet was sent on a different path to the receiver device than the missing data packet. In an implementation form of the second aspect, the method comprises considering the missing data packet lost and retransmitting the missing data packet, if the received data packet was sent on the same path to the receiver device as the missing data packet, and if retransmission is required by the underlying transport protocol used for sending the data packets.

In an implementation form of the second aspect, the method comprises retransmitting the missing data packet on the same path on which it was transmitted for the first time to the receiver device.

In an implementation form of the second aspect, the method comprises: receiving a further feedback message from the receiver device, wherein the further feedback message indicates that a further received data packet with a sequence number larger than a sequence number of the missing data packet has been received at the receiver device; and considering the missing data packet lost and retransmitting the missing data packet, if the further received data packet was sent on the same path to the receiver device as the missing data packet, and if retransmission is required by the underlying transport protocol used for sending the data packets.

In an implementation form of the second aspect, the method comprises, in order to determine the set of paths, selecting the one or more paths from all available paths between the sender device and the receiver device.

In an implementation form of the second aspect, the method comprises determining the set of paths based on a result of performing a per-path congestion control on available paths between the sender device and the receiver device.

In an implementation form of the second aspect, the method comprises selecting, for each data packet, the path for sending that data packet to the receiver device based on one or more congestion control considerations.

In an implementation form of the second aspect, the method comprises adding a new path to the set of paths. In an implementation form of the second aspect, the method comprises deleting a path from the set of paths.

In an implementation form of the second aspect, the method comprises, in order to delete the path from the set of path: stop sending data packets on the path to be deleted; retransmitting any missing data packet on the path to be deleted; and if all data packets, which were transmitted or retransmitted on the path to be deleted, are received at the receiver device, remove the path to be deleted from the set of paths.

In an implementation form of the second aspect, the method comprises, if a path fails, on which one or more missing data packets are to be retransmitted, retransmitting the one or more missing data packets on one or more other paths of the set of paths.

In an implementation form of the second aspect, the feedback message is an acknowledgment, (ACK) message, or a negative ACK (NACK), message, or a selective ACK (SACK) message.

The method of the second aspect and its implementation forms achieve the same advantages as described above for the sender device of the first aspect and its respective implementation forms.

A third aspect of this disclosure provides a computer program comprising instructions which, when the program is executed by a computer, cause the computer to perform the method according to the second aspect or any of its implementation forms.

A fourth aspect of this disclosure provides a storage medium storing executable program code which, when executed by a processor, causes the method according to the second aspect or any of its implementation forms to be performed.

It has to be noted that all devices, elements, units and means described in the present application could be implemented in the software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity, which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

The above described aspects and implementation forms will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which

FIG. 1 shows a sender device according to this disclosure.

FIG. 2 shows an exemplary flow-diagram of a retransmission scheme used by a sender device according to this disclosure.

FIG. 3 shows a method for sending data packets according to this disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS

FIG. 1 shows a sender device 100 according to this disclosure. The sender device 100 is configured to send data packets 101 on a connection to a receiver device 110. The sender device

100 is configured to use one or more paths 102 for the connection, i.e., to send the data packets

101 on paths 102 or multiple paths 102. The sender device 100 may be configured to select the paths 101, and may change the connection from one path 102, over which the data packets are sent to the receiver device 110 up to the moment of the change, to a new path 102, over which the data packets are sent from the moment of the change. This change of the connection may also be referred to as a rerouting of the connection. The sender device 100 may be further configured to send the data packets 101 to the receiver device 110 by using an underlying transport protocol that involves selective-repeat.

The sender device 100 is configured to determine a set of one or more paths 102 between the sender device 100 and the receiver device 110. For instance, the sender device 100 may determine the set of paths 102 based on a result of performing a per-path congestion control on available paths 102 between the sender device 100 and the receiver device 110. The sender device 100 may perform the per-path congestion control.

Further, the sender device 100 is configured to select, for each data packet 101, one of the paths

102 of the determined set of paths 102 for sending the data packet 101 to the receiver device 110. The sender device may, for example, select for each data packet 101 the path 102 for sending that data packet 101 to the receiver device 110, based on one or more congestion control considerations. The sender device 100 may then send each data packet 101 on the respectively selected path 102.

The sender device 100 may be further configured to maintain, for each data packet 101, path information 103, which indicates the selected path 102 on which the data packet 101 was sent to the receiver device 110. The path information 103 may be a variable stored at the sender device 100. The path information 103 of a particular data packet 101 may associate a sequence number of that particular data packet 101 with information regarding the path 102 on which that particular packet is or was sent. This information may be a path number of the selected path 102, or a path index or a path ID of the selected path 102.

The sender device 100 may further receive a feedback message 111 from the receiver device 110. The feedback message 111 may be an ACK message, or a NACK message, or a SACK message. The feedback message 111 comprises status information for each of one or more data packets 101. For example, the status information 103 of each data packet 101 could indicate whether that data packet 101 has been received by the receiver device 110 or is missing at the receiver device 110. The feedback message 111 may comprise a bitmap for indicating the status information. For example, the bitmap could indicate, which one or more sequence numbers have been received at the receiver device 110, and/or which of one or more sequence numbers of packets have not been received, or have been received out-of-order.

The sender device 100 is then configured to determine, based on the feedback message 111, whether to consider a missing data packet lost and whether to retransmit the missing data packet 101. The sender device 100 takes this decision at least based on the path information 103 of the missing data packet 101 and the status information for one or more other data packets 101 transmitted on the same path 102 to the receiver device 110 as the missing data packet 101. For instance, the sender device 100 may determine to consider the missing data packet 101 lost based path information 103 and status information, and determine to retransmit the missing data packet 101 based further on the rules of an underlying transport protocol.

The sender device 100 may comprise a processor or processing circuitry (not shown) configured to perform, conduct or initiate the various operations of the sender device 100 described herein. The processing circuitry may comprise hardware and/or the processing circuitry may be controlled by software. The hardware may comprise analog circuitry or digital circuitry, or both analog and digital circuitry. The digital circuitry may comprise components such as applicationspecific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or multi-purpose processors. The sender device 100 may further comprise memory circuitry, which stores one or more instruction(s) that can be executed by the processor or by the processing circuitry, in particular under control of the software. For instance, the memory circuitry may comprise a non-transitory storage medium storing executable software code which, when executed by the processor or the processing circuitry, causes the various operations of the sender device 100 to be performed. In one embodiment, the processing circuitry comprises one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the sender device 100 to perform, conduct or initiate the operations or methods described herein.

In this disclosure, the aim is that data that is divided into the data packets 101 is sent reliably from the sender device 100 to the receiver device 110. The data packets 101 may be assigned a sequence number each, as in the case of a conventional single path transport.

The sender device 100 may determine how many paths 102 to use for sending the data packets 101, and which paths 102 to use for each data packet 101. There may be many ways to signal this information to the network. For example, by changing the source port number in a user datagram protocol (UDP) header, or by adding a routing header to the data packet 101.

The sender device 100 may run a per-path congestion control protocol. The receiver device 110 can participate in the congestion control protocol without knowing how many paths are used by the sender device 100. For example, the received device 110 may send a response control packet, for instance, a SACK, for each received data packet 101. Further, the receiver device 110 may indicate whether or not this data packet 101 experienced congestion. Another example is that the receiver device 110 sends a control packet after multiple data packets 101 have been received, and indicates in this control packet over which path each of the data packets 101 has been received, and optionally whether or not these data packets 101 experienced congestion. A data packet 101 can be sent on any available path 102 the sender device 100 wants. The decision may be taken at the sender device according to one or more congestion control considerations. The sender device 100 may remember the path 102, over which each outstanding packet was transmitted, by means of the path information 103.

The receiver device 110 may, for example only send SACK messages as feedback messages 111, for example, periodically, or after receiving N data-packets, where N>1. The SACK message may indicate congestion control information. In addition, the SACK message may indicate which data packets 101 were received by the receiver device 110 so far. For example, the SACK message can indicate that all the data packets 101 up to a certain sequence number, for example 120, have been received, except the data packets 101 with certain other sequence numbers, for example 115 and 118.

When the sender device 100 receives the SACK message, it can decide for each outstanding data packet 101, whether or not to consider this data packet 101 lost and whether to retransmit this data packet 101. The decision may be taken according to (a) the path 102 over which this data packet 101 was sent, (b) according to the status of the data packets 101 transmitted over this path 102 (indicated by the status information in the feedback message 111), and (c) and according to the rules of the underlying transport protocol regarding retransmission. For instance, different transport protocols may have different retransmission strategies. It is possible that a missing data packet 101 is considered lost by the sender device 100, and is accordingly retransmitted according to the retransmission strategy of the transport protocol used. It is also possible that a missing data packet 101 is considered lost by the sender device 100, but is not retransmitted due to the retransmission strategy of the transport protocol used. It is also possible that a missing data packet 101 is not considered lost, at least not yet, and is thus not retransmitted.

FIG. 2 shows a flow-diagram of an example of the retransmission scheme used by the sender device 100 in this disclosure and as described above. In the shown example, the data packets 101 with the sequence numbers 1 and 3 are sent over a path 102 number #0, and the data packets 101 with the sequence numbers 2 and 4 are sent over path 102 number #1. In this example, if two data packets 101 are transmitted over the same path 102, the underlying transport protocol expects them to be received in the same order, unless one of them is lost. In this example, a feedback message 111 (e.g., a SACK message) indicates that all the data packets 101 up to the data packet 101 with the sequence number 1 were correctly received. Further, the second feedback message 111 (e.g., a second SACK message) informs that the data packet 101 with the sequence number 3 has been correctly received, but that the data packet 101 with the sequence number 2 is missing. However, the sender device 100 does not retransmit the data packet 101 with the sequence number 2, because it was transmitted on a different path and therefore it may be correctly received after the data packet 101 with the sequence number 3, and is therefore not considered lost at this point by the sender device.

However, when a third feedback message 111 (e.g., a third SACK message) informs that the data packet with the sequence number 4 is also received, but that the data packet 101 with the sequence number 2 is still missing, the sender device 100 considers the missing data packet 101 with the sequence number 2 lost and retransmits the data packet 101 with the sequence number 2. The retransmission is conducted over the same path than the original data packet 101 with the sequence number 2 was transmitted (for the first time).

Another feature of this disclosure is the ability of the sender device 100 to add and/or delete one or more paths 102 from the set of paths 102. For instance, the sender device 100 may dynamically, and optionally without coordinating this with the receiver device 110, add and/or delete the one or more paths 102. This may be done in the following way.

To delete a path 102 the sender device 100 may first stop using this path 102 for new data packets 101. It may put this path 102 in a “suspended” state, and may wait until all the data packets 101 transmitted over this path 102 are correctly received. If some of these data packets 101 are considered lost, they are retransmitted over this path 102. When there is no outstanding data packet 101 belonging to this path 102 anymore, the sender device 100 may remove this path 102 from the list of active paths 102. If the path 102 fails while there are some outstanding data packets 101, the sender device 100 may stop using it and may retransmit all outstanding data packets 101 over the other paths 102. To add a path 102, the sender device 100 can simply start using this path 102 for new data packets 101.

In a conventional multipath TCP (MP-TCP) transport protocol, the receiver device and the sender device must agree about each path 102 (called mini-flow) added to the connection (called flow). This is done using a mini-flow connection setup. This is unlike the solution of this disclosure, where the sender device 100 and the receiver device 110 do not have to agree. Thus, an advantage of this disclosure over MP-TCP is that such an agreement and negotiation is not needed.

Moreover, in MP-TCP, each data packet has two sequence numbers. A first sequence number that indicates the order of the data packet inside its mini-flow, and a second sequence number that indicates the order of the data packet within the whole flow. In this disclosure, only one sequence number per packet (corresponding to the first sequence number) is used. Thus, a simpler protocol is enabled.

FIG. 3 shows a method 300 according to this disclosure. The method 300 can be used for sending data packets 101 from a sender device 100 to a receiver device 110. The method 300 may be performed by the sender device 100 described above.

The method 300 comprises a step 301 of determining a set of one or more paths 102 between the sender device 100 and the receiver device 110. The method 300 further comprises a step 302 of selecting, for each data packet 101, one of the paths 102 of the set of paths 102 for sending the data packet 101 to the receiver device 110). The method 300 comprises a step 303 of maintaining 303, for each data packet 101, path information 103 indicating the selected path 102 on which the data packet 101 was sent to the receiver device 110.

Further, the method 300 comprises a step 304 of receiving a feedback message 111 from the receiver device 110. The feedback message 111 comprises status information for each of one or more data packets 101. The status information 103 of each data packet 101 may indicate, whether that data packet 101 has been received by the receiver device 110 or is missing at the receiver device 100. The method 300 also comprises a step 304 of determining, based on the feedback message, whether to consider a missing data packet 101 lost and whether to retransmit the missing data packet 101, based on the path information of the missing data packet and the status information for one or more other data packets transmitted on the same path to the receiver device as the missing data packet. The determination whether to retransmit the missing data packet 101 may be further based on the rules of the underlying transport protocol used for sending the data packets 101. This protocol may be a single-path transport protocol. The present disclosure has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed matter, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article “a” or “an” does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.