CN116671045A - 用于选择性重传丢失数据包的设备和方法 - Google Patents

Abstract

本发明涉及用于在通信网络中高效地重传丢失数据的协议。为此，本发明提出了一种第一网络设备，用于：向第二网络设备发送数据包序列；从所述第二网络设备接收至少一个通知消息，其中所述至少一个通知消息指示在所述第二网络设备处接收的数据包的最大序列号L和在所述第二网络设备处丢失的序列号在L之前的一个或多个数据包；在接收到所述至少一个通知消息之后，下一步重传所述丢失数据包，其中，每个丢失数据包在第一次传输之后指示为丢失数据包，所述每个丢失数据包的序列号X小于L–K。

Description

用于选择性重传丢失数据包的设备和方法

技术领域

本发明涉及通信网络，尤其涉及通信网络数据传输的数据可靠性。本发明提出了一种用于选择性重传丢失数据包的设备和方法。

背景技术

在数据网络中，当两台计算机相互通信时，通常需要确保数据可靠性。为此，发送方为每个数据包附加序列号，接收方告知发送方哪些数据包已经被接收，哪些数据包丢失。发送方必须重传丢失数据包，直到接收方接收到所有数据包。

确保数据可靠性的协议可分为三大类：停等、返回N和选择性重复。

在停等中，发送方发送数据包并等待数据包的确认(acknowledgement，ACK)。一旦ACK到达发送方，发送方就会传输下一个数据包。如果没有接收到ACK，则发送方将再次重传上一个数据包。

在返回N中，已经接收到数据包编号N之前所有数据包的接收方只愿意接受数据包编号N+1。如果没有接收到数据包N+1，但接收到序列号更大的数据包，如N+2或更大的序列号，则接收方丢弃此乱序数据包。当发送方被告知数据包N+1丢失时，发送方得知不仅必须重传此数据包，还必须重传所有后续数据包。

在选择性重复中，接收方愿意接受乱序接收的数据包。接收方将这些数据包放置在重新排序缓冲区中，或在存在直接数据放置(direct data placement，DDP)信息头的情况下直接放置这些数据包。然后，接收方只告知发送方丢失的数据包，发送方只重传丢失数据包。

然而，现有的丢失数据包重传解决方案存在以下一个或多个问题。在某些解决方案中，发送方被多次告知丢失的数据包，并且可能不必要地重传丢失数据包。有些解决方案需要很多逻辑定时器，操作难度大。调整超时是一项非常困难的任务，特别是因为往返时间(round-trip-time，RTT)，即发送数据包与接收数据包的ACK之间的时间，可能会经常变化。错误估计RTT可能导致不必要的重传(超时太短的情况下)，或额外的延迟(超时太长的情况下)。

发明内容

鉴于上述限制，本发明的实施例旨在引入一种新的协议，用于高效地重传丢失数据包，特别是用于选择性地重传丢失数据包。目标是让发送方可以仅重传丢失数据包，而不依赖于每个数据包的定时器，也不需要在第一次重传失败的情况下等待长时间的超时。

通过所附独立权利要求中提供的实施例实现所述目标。实施例的有利实现方式在从属权利要求中进一步定义。

本发明的第一方面提供了一种第一网络设备，用于：向第二网络设备传输数据包序列；从第二网络设备接收至少一个通知消息，其中至少一个通知消息指示已在第二网络设备处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备处丢失的一个或多个数据包；在接收到至少一个通知消息之后，下一步重传一个或多个数据包，其中，一个或多个丢失数据包中的每一个在第一次传输之后由至少一个通知消息指示为丢失数据包，每个丢失数据包的序列号X小于L–K，其中K为非负整数的参数。

第一网络设备(发送方)通过用于在数据包第一次被指示为丢失数据包的情况下立即重传数据包，能够选择性且高效地重传丢失数据包。也就是说，在第一次传输之后由接收方指示为丢失的数据包立即由发送方重传。至少一个通知消息可以包括ACK、否定确认(negative-acknowledgment，NACK)或选择性确认(selective acknowledgment，SACK)中的至少一个。

具体地，在数据包按序路由的情况下，当第一网络设备被告知第二网络设备(接收方)已经接收到数据包L，但没有接收到数据包X(其中X<L)时，第一网络设备得知数据包X丢失。在某些情况下，网络不一定确保数据包按序路由。在该实现方式中，通过引入参数K，可以相应地修改所提出的协议。

具体地，第一网络设备可以维护参数K，该参数K指示当数据包都从第一网络设备发送到第二网络设备时，有多少个数据包可以绕过某个数据包。为了解决数据包不按序路由的场景，参数K为正整数。例如，如果K＝3，则只有当X<L–3时，第一网络设备才能在接收到数据包编号L之后确定数据包编号X丢失。需要注意的是，在K＝0的情况下，解决方案是解决按序数据包路由，即数据包在网络中不相互绕过。

在第一方面的一种实现形式中，第一网络设备用于维护指示至少一个通知消息指示的丢失数据包的第一数据结构；响应于至少一个通知消息而更新第一数据结构。

可选地，第一数据结构可以是指示每一未完成数据包(即，每一未由第二网络设备确认的传输数据包)的状态的位图。这是为了记住哪个数据包已经被接收方接受，哪个数据包没有被接受。

在第一方面的一种实现形式中，第一网络设备用于维护指示待重传数据包的第二数据结构；在重传待重传数据包之后，从第二数据结构中删除该待重传数据包。

可选地，第一网络设备可以维护除第一数据结构之外的另一个数据结构。特别是，第二网络设备要记住必须重传哪个数据包(待重传的集合)。值得注意的是，当数据包被重传时，它将从待重传集合中删除(即，不再在第二数据结构中)；但在它被接收方确认为接收到之前，它仍然被标记为丢失(即，仍然在第一数据结构中)。

在第一方面的一种实现形式中，第一网络设备还用于：如果一个或多个数据包在第一次传输之后由至少一个通知消息指示为丢失数据包，且每个丢失数据包的序列号X小于L–K，则将这些一个或多个数据包添加到第二数据结构中。

值得注意的是，如果第一网络设备确定数据包的第一次传输失败，则该数据包将被放入第二数据结构中。要确定数据包丢失，数据包的序列号应满足前面讨论的条件。

在第一方面的一种实现形式中，第一网络设备还用于：如果满足以下条件，则将一个或多个数据包添加到第二数据结构中：

–一个或多个数据包已经被重传，

–第一网络设备接收到另一通知消息，其中另一通知消息指示一个或多个数据包在第二网络设备处仍然丢失，

–另一通知消息还指示已在第二网络设备处接收到的另一数据包，其中另一数据包是在一个或多个数据包的最后重传之后首次发送的，

–另一通知消息指示的另一数据包具有不小于Y+K的序列号，其中Y为一个或多个数据包的最后重传之后首次发送的第一数据包的序列号。

值得注意的是，对于已经由第一网络设备重传的数据包，在这些数据包到达第二网络设备之前，第二网络设备仍然可以报告这些数据包丢失。为了避免不必要的冗余重传，第一网络设备检查其他条件，即，如上一段所述，并且只有在满足这些条件的情况下，才能再次重传数据包。

在第一方面的一种实现形式中，第一网络设备用于在第一状态和第二状态下工作，其中，在第一状态下，第一网络设备用于传输新数据包；在第二状态下，第一网络设备用于根据第二数据结构重传丢失数据包。

根据协议的实施例，在发送方侧，即在第一网络设备处，时间轴可以分为轮次。每一轮要么是传输新数据包的“常规轮”，要么是根据第二数据结构重传丢失数据包的“重传轮”。

在第一方面的一种实现形式中，其中在第一状态下，第一网络设备用于：如果第二数据结构不为空，则进入第二状态；和/或，如果第二数据结构为空，则保持在第一状态。

也就是说，在“常规轮”中，当第二网络设备第一次告知第一网络设备数据包丢失时，此数据包将立即被添加到第二数据结构中。然后，第一网络设备将立即重传此数据包，因为第二数据结构不为空。不存在此重传是虚假的风险，因为在通往接收方的路上没有此数据包的未完成副本。

在第一方面的一种实现形式中，在第二状态下，第一网络设备用于：如果第二数据结构为空，则进入第一状态；和/或如果第二数据结构不为空，则保持在第二状态。

也就是说，在第一网络设备重传已知丢失的所有数据包之后，第一网络设备将继续传输新数据包。

在第一方面的一种实现形式中，第一网络设备还用于：使用定时器，并在传输数据包和/或重传丢失数据包时设置该定时器；在定时器超时，将未接收到ACK的所有数据包添加到第二数据结构中。

可选地，第一网络设备可以通过超时来决定可以开始新的重传轮。当定时器超时，第一网络设备重传到目前为止还没有接收到ACK的所有数据包。特别地，如前所述，通知消息可以包含ACK和NACK。值得注意的是，ACK表示已经接收到数据包，而NACK表示接收方处丢失数据包。

在第一方面的一种实现形式中，第一网络设备还用于将定时器设置为大于RTT的值。

值得注意的是，RTT是指发送数据包与接收该数据包的ACK之间的时间。

本发明的第二方面提供了一种第二网络设备，用于：从第一网络设备接收数据包序列；向第一网络设备传输至少一个通知消息，其中至少一个通知消息指示已在第二网络设备处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备处丢失的一个或多个数据包。

第二网络设备(接收方)接收数据包并相应地传输通知消息(例如，ACK和/或NACK)，从而让第一网络设备(发送方)以高效的方式重传丢失数据包。

在第二方面的一种实现形式中，第二网络设备还用于当定时器超时时向第一网络设备传输至少一个通知消息。

值得注意的是，接收方还可以具有定时器，如果在超时时段内没有接收到一定数量的数据包，则该定时器触发通知消息的传输。

本发明的第三方面提供了一种由第一网络设备执行的方法，其中所述方法包括：向第二网络设备传输数据包序列；从第二网络设备接收至少一个通知消息，其中至少一个通知消息指示已在第二网络设备处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备处丢失的一个或多个数据包；在接收到至少一个通知消息之后，下一步重传一个或多个丢失数据包，其中，一个或多个丢失数据包中的每一个在第一次传输之后由至少一个通知消息指示为丢失数据包，每个丢失数据包的序列号X小于L–K，其中K为非负整数的参数。

所述第三方面的方法的实现方式可以对应所述第一方面的第一网络设备的实现方式。所述第三方面及其实现方式所述的方法实现了与上述第一方面及其实现方式所述的第一网络设备相同的优点和效果。

本发明的第四方面提供了一种由第二网络设备执行的方法，其中所述方法包括：从第一网络设备接收数据包序列；向第一网络设备传输至少一个通知消息，其中至少一个通知消息指示已在第二网络设备处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备处丢失的一个或多个数据包。

所述第四方面的方法的实现方式可以对应所述第二方面的第二网络设备的实现方式。所述第四方面及其实现方式所述的方法实现了与上述第二方面及其实现方式所述的第二网络设备相同的优点和效果。

本发明的第五方面提供了一种包括程序代码的计算机程序产品，所述程序代码用于在处理器上实现时执行根据所述第三方面和所述第三方面的任何实现方式，或所述第四方面和所述第四方面的任何实现方式所述的方法。

需要说明的是，本申请中描述的所有设备、元件、单元和模块可以在软件或硬件元件或其任何类型的组合中实现。本申请中描述的各种实体所执行的所有步骤以及所描述的各种实体要执行的功能均意在指相应实体用于执行相应步骤和功能。虽然在以下具体实施例的描述中，外部实体执行的具体功能或步骤没有在执行具体步骤或功能的该实体的具体详述元件的描述中反映，但是技术人员应清楚，这些方法和功能可以通过相应的硬件或软件元件或其任何组合实现。

附图说明

结合所附附图，下面具体实施例的描述阐述上述本发明的各方面及实现方式，其中：

图1示出了返回N方法的示例。

图2示出了选择性重复方法的示例。

图3示出了选择性重复方法的模糊性问题。

图4示出了选择性重复方法的示例。

图5示出了选择性重复方法的示例。

图6示出了本发明实施例的第一网络设备。

图7示出了本发明实施例的轻量级高效重传协议(light efficientretransmission protocol，LERP)的示例。

图8示出了本发明实施例的LERP的示例。

图9示出了本发明实施例的LERP的示例。

图10示出了本发明实施例的LERP的示例。

图11示出了本发明实施例的第二网络设备。

图12示出了不保证报文保序的示例。

图13示出了本发明实施例的方法。

图14示出了本发明实施例的方法。

具体实施方式

参考附图描述了用于在通信系统中进行高效数据包重传的方法、设备和程序产品的说明性实施例。尽管此描述提供了可能实现方式的详细示例，但需要说明的是，这些细节旨在是示例性的，并且不会限制本申请的范围。

此外，一个实施例/示例可以指其他多个实施例/示例。例如，一个实施例/示例中提及的任何描述，包括但不限于术语、元件、过程、解释和/或技术优势均适用于其他多个实施例/示例。

如前所述，确保数据可靠性的协议可分为三大类：停等、返回N和选择性重复。

例如，发送方发送了数据包1至5，只有数据包3丢失。在返回N场景中，发送方将重传数据包3至5，而在选择性重复场景中，发送方将只重传数据包3。

图1示出了在返回N中，发送方在被否定ACK(negative ACK，NACK)告知数据包2丢失之前发送了103个数据包的情况。因此，发送方不仅要重传数据包2，而且还要重传数据包3至103。只有在此之后，发送方才能继续传输新数据包(104及以上)。

图2中描绘的示例示出了类似的情况，但具有选择性重复。此处，当发送方被告知数据包2丢失时，它只重传此数据包(即数据包2)，然后它可以继续传输新数据包。

需要说明的是，选择性重复是一种更高效的协议，因为只有未能到达接收方的数据包才会被重传。但是，选择性重复的实现比返回N的实现更困难，主要原因有两个。首先，选择性重复要求接收方存储乱序数据包，或者在其他情况下要求额外的DDP信息头。第二，在异步和不可靠的网络中，告知发送方哪些数据包已经被接收和哪些数据包丢失是一项困难的任务。特别是，有可能接收方告知发送方数据包丢失，而该数据包的传输(重传)正在进行中，并将很快到达接收方。因此，选择性重复发送方总是难以决定是否服从重传请求。

例如，一种情况如图3中所示。具体地，在接收到数据包4之后，接收方明白数据包3丢失了，因为如果它没有丢失，它应该在数据包4之前被接收。接收方可以将此告知发送方。接收方可以发送NACK，可选地，接收方可以在一个通知消息中告知发送方它已经接收到的所有数据包和它尚未接收到的数据包。

当发送方接收到此通知消息时，它将重传数据包编号3。但过了一段时间，发送方接收到另一个通知消息，该通知消息指示数据包5和6也丢失了。此另一通知消息还告知数据包3(仍然)丢失。当发送方接收到此另一通知消息时，它不知道数据包3的重传副本的状态是什么。一方面，如果发送方忽略了此另一通知消息指示数据包3(仍然)丢失这一事实，则它将永远无法得知数据包3的重传副本丢失。另一方面，如果发送方再次重传数据包3，但上一次重传被接收方接收到，则第二次重传是对资源的浪费。

解决上述问题的一种方法是，每个发送方总是服从任何数据包的第一个重传请求。但是，一旦发送方重传数据包，它就会启动定时器，如果在接收到该数据包的ACK之前该定时器超时，则该数据包被再次重传。

在这种情况下，发送方将始终重传数据包作为对NACK的响应。但是，如果重传丢失，发送方得知该丢失的唯一方法是将定时器与每次重传相关联。如果此重传在超时时段内没有被赋予ACK，则它被再次重传。这在图5中示出。需要注意的是，图5未示出被发送或可发送的所有通知消息。在此图中，数据包3的第二次重传是在超时后完成的。

但是，上述方法存在两个问题。首先，它需要许多逻辑定时器。这些定时器的操作很困难，特别是在硬件上实现协议时。其次，协议需要调整超时，这是一项非常困难的任务。这尤其是因为RTT在实践中可能会经常变化。对RTT的错误估计可能导致不必要的重传(在超时太短的情况下)，或者导致额外的延迟(在超时太长的情况下)。

为了解决上述限制和缺陷，本发明的实施例提出了一种用于选择性重传丢失数据包的新协议。此协议被称为轻量级高效重传协议(light efficient retransmissionprotocol，LERP)。LERP最重要的属性之一是，让发送方可以仅重传丢失数据包，而不依赖于每个数据包的定时器，也不需要在第一次重传失败的情况下等待长时间的超时。

图6示出了本发明实施例的第一网络设备600。第一网络设备600可以包括处理电路系统(未示出)，该处理电路系统用于执行、进行或发起本文所述的第一网络设备600的各种操作。处理电路系统可以包括硬件和软件。硬件可以包括模拟电路系统或数字电路系统，或模拟和数字电路系统两者。数字电路系统可以包括专用集成电路(application-specific integrated circuit，ASIC)、现场可编程门阵列(field-programmable gatearray，FPGA)、数字信号处理器(digital signal processor，DSP)或多用途处理器等组件。第一网络设备600还可以包括存储器电路系统，该存储器电路系统存储可以由处理器或处理电路系统执行(具体地，在软件的控制下执行)的一个或多个指令。例如，存储器电路系统可以包括存储可执行软件代码的非瞬时性存储介质，该可执行软件代码在由处理器或处理电路系统执行时使得执行第一网络设备600的各种操作。在一个实施例中，处理电路系统包括一个或多个处理器和连接到一个或多个处理器的非瞬时性存储器。非瞬时性存储器可携带可执行程序代码，该可执行程序代码在由一个或多个处理器执行时使第一网络设备600执行、进行或发起本文所述的操作或方法。

具体地，第一网络设备600用于向第二网络设备610传输数据包序列601。因此，第一网络设备600可以被称为“发送方”，第二网络设备610可以被称为“接收方”，特别是与前面图中所示的发送方和接收方相比。第一网络设备600还用于从第二网络设备610接收至少一个通知消息602。具体地，至少一个通知消息602指示已在第二网络设备610处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备610处丢失的一个或多个数据包603。然后，第一网络设备600特别用于在接收到至少一个通知消息602后，下一步重传一个或多个数据包603，其中，一个或多个丢失数据包603中的每一个在第一次传输之后由至少一个通知消息602指示为丢失数据包，每个丢失数据包603的序列号X小于L–K，其中K为非负整数的参数。

也就是说，当接收方，即第二网络设备610(通过至少一个通知消息602)第一次告知发送方，即第一网络设备600数据包丢失时，如果每个丢失数据包603的序列号X小于L–K，则第一网络设备600可以立即重传该数据包。不存在此重传是虚假的风险，因为在通往第二网络设备610的路上没有此数据包的未完成副本。值得注意的是，如前所述，在接收方处丢失的数据包可以由NACK指示。至少一个通知消息602可以包括ACK和/或NACK。ACK可以指示第二网络设备610已经接收到某个数据包，NACK可以指示在第二网络设备610处丢失某个数据包。因此，决定何时服从NACK和何时不服从NACK的问题仅在数据包被重传之后才相关，并且第一网络设备600继续接收该数据包的NACK，如图3中所示的数据包3的情况。

所提出的协议的思想是，当发送方，即第一网络设备600，重传数据包，例如，数据包X，X为数据包的序列号时，它记住第一次传输的最后一个数据包(例如，数据包Y)的序列号，即，Y。以K＝1的场景为例，当接收到序列号大于Y的数据包的ACK时，第一网络设备600得知到那时它应该已经接收到数据包X的重传副本的ACK。如果没有接收到这个ACK，则数据包X的重传副本一定已经丢失，数据包X可以再次重传。

值得注意的是，至少一个通知消息602可以包括ACK、NACK和SACK中的至少一个。值得注意的是，SACK可以指示一组数据包中的哪些数据包被确认(无论是否定还是肯定)。

具体地，在数据包按序路由的情况下，当第一网络设备600被告知第二网络设备610(接收方)已经接收到数据包L，但没有接收到数据包X(其中X<L)时，第一网络设备600得知数据包X丢失。然而，网络不一定确保数据包按序路由，因此提出的协议引入了参数K，该参数指示当数据包都从第一网络设备发送到第二网络设备时，有多少个数据包可以绕过某个数据包。

值得注意的是，在K＝0的情况下，解决方案是解决按序数据包路由。为了解决数据包不按序路由的场景，参数K为正整数。例如，如果K＝3，则只有当X<L–3时，第一网络设备才能确定数据包X丢失。

发送方侧，即第一网络设备600处的协议，可以将时间轴分为轮次。每一轮要么是传输新数据包的“常规轮”，要么是重传丢失数据包的“重传轮”。这由图7证明。定义了变量StampedMaxDataTx。此变量可用于记住在进入重传轮之前最后一个常规(未重传)传输的数据包。

图7示出了本发明实施例的所提出的协议的示例。需要注意的是，在本具体实施例中，假设K＝0。具体地，在最后一个常规轮中，新数据包100由发送方传输到接收方。发送方可以是如图6中所示的第一网络设备600，接收方可以是如图6中所示的第二网络设备610。在重传轮中，仅传输丢失数据包。此外，变量StampedMaxDataTx被设置为100，因为数据包100是最后一个常规(未重传)传输的数据包。在重传丢失数据包之后，开始常规轮，在该轮次中传输新数据包。新的丢失将被快速重传。也就是说，当第一网络设备600得知数据包第一次被报告为丢失数据包时，第一网络设备600将立即重传该数据包。在这种情况下，当接收到数据包101的NACK或未接收到101的ACK或接收到通知数据包101丢失的通知消息时，第一网络设备600进入“重传轮”。在快速重传之后，将更新StampedMaxDataTx。如本示例所示，在下一个重传轮时，仅传输丢失数据包，变量StampedMaxDataTx被设置为195。

图8示出了本发明实施例的LERP执行示例。在本实施例中，假设K＝0。图8中所示的发送方可以是如图6中所示的第一网络设备600，接收方可以是如图6中所示的第二网络设备610。

在本示例中，接收方正确地接收数据包(0)，并发回ACK(0)。然后，数据包(1)和数据包(2)丢失。当接收到数据包(3)时，接收方明白数据包(1)和数据包(2)丢失了。它可能会发送通知消息，表示数据包编号3之前的所有数据包都已经被正确接收，但没有数据包(1)和数据包(2)。值得一提的是，“SACK”在本图(和图9、图10)中仅用作表示通知消息的示例。接收方，即第二网络设备610，也可以发送其他通知消息，例如ACK或NACK。

此SACK是接收方发送的第一个SACK。当发送方接收到此SACK时，它可以构建重传数据集(本示例中为位图)，该重传数据集指示哪些数据包丢失。它还开始第一个重传轮：StampedMaxDataTx被设置为12(按序发送的最后一个数据包)，另一个变量LastRetx指示哪个丢失数据包是下一个要重传的数据包。在这种情况下，数据包(1)和数据包(2)被重传。然后，第一个重传轮结束，发送方继续传输常规数据包。

当接收到报告数据包(5)丢失的SACK时，仅传输了常规数据包(13)。发送方进入新的重传轮，但在这个轮次中，并不是所有丢失的数据包都被重传，因为发送方不知道数据包(1)和数据包(2)的重传是否成功。发送方将StampedMaxDataTx设置为13，并重传数据包(5)。然后，发送方退出重传轮，并继续传输常规数据包，这些常规数据包中的第一个是数据包(14)。当接收到此数据包的SACK时，它告诉发送方数据包(14)正常，而数据包(2)和数据包(5)仍然丢失。由于StampedMaxDataTx＝13且14>13，发送方得知此时所有的重传应该都已被接收。由于数据包(2)和数据包(5)仍然报告丢失，这意味着新的重传轮可以开始，这些数据包应第二次重传(即，在第三轮中传输)。发送方设置StampedMaxDataTx＝16，并重传数据包(2)和数据包(5)。然后，发送方希望切换到传输常规数据包，但第一次报告数据包(15)丢失。因此，它保持在重传轮中，并重传数据包(15)。

图9继续图8中所示的上述示例。所示的前三个数据包(即，数据包(2)、数据包(5)和数据包(15))是图8中的最后数据包。在本示例中，在发送数据包(21)之后，没有更多的新数据包要发送。数据包18的SACK被接收，该SACK表示数据包(18)已被正确接收。由于StampedMaxDataTx＝16且18>16，发送方进入新的重传轮。发送方还第一次被通知数据包(17)丢失。发送方进入新的重传轮，重传数据包(5)，然后重传数据包(15)，最后重传数据包(17)。所有这些数据包都被成功接收，接收方以ACK(21)响应，协议可以停止。

图10示出了继续图8中的示例的不同方式。所示的前三个数据包(即，数据包(2)、数据包(5)和数据包(15))是图8中的最后数据包。这里假设数据包(17)是最后要发送的。也就是说，在本示例中，在发送数据包(17)之后，没有更多的新数据包要发送。这给发送方带来了问题，因为它没有被告知序列号大于StampedMaxDataTx＝16的数据包已被接受。发送方决定应开始新的重传轮的一种方式为使用超时。每当它传输旧数据包或新数据包时，发送方都会重新启动定时器。此定时器在重传超时(retransmission time out，RTO)之后超时。RTO被设置为大于RTT的值。有许多用于估计RTT的算法，在本发明中不限于此。当定时器超时，发送方重传到目前为止还没有接收到ACK的所有数据包，即数据包(16)和数据包(17)。

可选地，如果不存在新数据，则可以通过在重传之后发送具有新序列号的空数据包来防止RTO的设置。

需要注意的是，图7至图10中的一个中所示的发送方和接收方可以分别是图6中所示的第一网络设备600和第二网络设备610。

为了简化描述，可以假设发送方具有指示每一未完成数据包(即，未被接收方确认的每一传输数据包)的状态的位图。在实践中，当发送方处于正常状态，即传输新数据包的“常规轮”时，在接收方报告新检测到的间隙之前，不需要保存位图。值得注意的是，当数据包不连续时，即，当存在丢失数据包时，会发生间隙。

根据本发明的实施例，第一网络设备600可以用于维护指示至少一个通知消息602指示的丢失数据包的第一数据结构。相应地，第一网络设备600还可以用于响应于至少一个通知消息602而更新第一数据结构。

此外，第一网络设备600可以用于维护指示待重传数据包的第二数据结构；在重传待重传数据包之后，从第二数据结构中删除待重传数据包。

可选地，第一网络设备600还可以用于：如果一个或多个数据包在第一次传输之后由至少一个通知消息602指示为丢失数据包，并且每个丢失数据包603的序列号X小于L–K，则将一个或多个数据包添加到第二数据结构中。

可能地，第一网络设备600还可以用于：如果满足以下条件，则将一个或多个数据包添加到第二数据结构中：

–一个或多个数据包603已经被重传，

–第一网络设备600接收到另一通知消息，其中另一通知消息指示一个或多个数据包603在第二网络设备610处仍然丢失，

–另一通知消息还指示已在第二网络设备610处接收到的另一数据包，其中另一数据包是在一个或多个数据包603的最后重传之后首次发送的，

–另一通知消息指示的另一数据包具有不小于Y+K的序列号，其中Y为一个或多个数据包603的最后重传之后首次发送的第一数据包的序列号。

根据本发明的实施例，在发送方侧，第一网络设备600传输数据包，并接收ACK/NACK和/或SACK消息。第一网络设备600具有两种状态：正常和恢复。在正常状态时，位图没有任何丢失数据包的指示。在恢复状态时，重组位图具有至少一个报告的丢失数据包。

具体地，第一网络设备600可以配置有五个变量：状态、最大按序接收(MaxIORx)、最后重传(LastRetx)、加戳的最大数据Tx(StampedMaxDataTx)和参数K。MaxIORx保存由接收方，即第二网络设备610按序接收的确认数据包的最大PSN。这是最早报告丢失的数据包的前一个数据包的PSN。LastRetx保存最后重传数据包的PSN。StampedMaxDataTx保存当执行重传时传输数据包的最大PSN。值得注意的是，当第一网络设备600重传数据包时，LastRetx和StampedMaxDataTx同时更新。

在特定实施例中，第一网络设备600传输PSN＝498/499/500的数据包，然后重传PSN＝20的数据包，然后传输PSN＝501/502的数据包。在这种情况下，LastRetx＝20，且StampedMaxDataTx＝500。

在发送方侧，本发明实施例的算法如下：

1.当RTO超时：

a.设置：LastRetx←MaxIORx

b.设置：状态←恢复

2.当可以传输数据包时：

a.如果状态＝正常，则传输下一个按序数据包。

b.否则(即，状态为恢复)，如果存在PSN>LastRetx的丢失数据包，则：

i.重传此数据包。

ii.将LastRetx更新为重传数据包的PSN。

iii.如果需要，将StampedMaxDataTx更新为传输的当前最大PSN的PSN。

c.否则(即，状态为恢复，但所有已知的丢失数据包都在上一重传轮中被重传，因此没有PSN>LastRetx的丢失数据包)，传输下一个按序数据包(如在正常状态下完成)。

3.当接收到ACK时(当接收方的序列号中没有间隙时发生这种情况)，这表示ACK.PSN之前的所有数据包都已经被接收。

a.设置：状态←正常(ACK指示没有丢失数据包)

b.更新位图

c.更新MaxIORx

4.当接收到SACK(SACK可包含ACK和NACK)时：

a.状态←恢复。

b.更新位图。如果SACK报告了当前不在发送方位图中的丢失数据包，则仅将PSN满足PSN≤SACK.MaxDataRx的数据包添加到位图中

c.如果(StampedMaxDataTx)<SACK.MaxDataRx，则重置LastRetx＝MaxIORx。

根据本发明的实施例，在接收方侧，第二网络设备610接收数据包，并传输ACK/NACK和/或SACK消息。第一网络设备600可以配置有两个变量：ExpectedPSN和MaxDataRx。具体地，ExpectedPSN保存下一个按序数据包的PSN。它也是所有丢失数据包中的最小(第一个)PSN。MaxDataRx保存接收方接收到的最大PSN。

图11示出了本发明实施例的第二网络设备610。第二网络设备610可以包括处理电路系统(未示出)，该处理电路系统用于执行、进行或发起本文所述的第二网络设备610的各种操作。处理电路系统可以包括硬件和软件。硬件可以包括模拟电路系统或数字电路系统，或模拟和数字电路系统两者。数字电路系统可以包括专用集成电路(application-specific integrated circuit，ASIC)、现场可编程门阵列(field-programmable gatearray，FPGA)、数字信号处理器(digital signal processor，DSP)或多用途处理器等组件。第二网络设备610还可以包括存储器电路系统，该存储器电路系统存储可以由处理器或处理电路系统执行(具体地，在软件的控制下执行)的一个或多个指令。例如，存储器电路系统可以包括存储可执行软件代码的非瞬时性存储介质，该可执行软件代码在由处理器或处理电路系统执行时使得执行第二网络设备610的各种操作。在一个实施例中，处理电路系统包括一个或多个处理器和连接到一个或多个处理器的非瞬时性存储器。非瞬时性存储器可携带可执行程序代码，该可执行程序代码在由一个或多个处理器执行时使第二网络设备610执行、进行或发起本文所述的操作或方法。

具体地，第二网络设备610用于从第一网络设备600接收数据包序列601。然后，第二网络设备610还用于向第一网络设备600传输至少一个通知消息602，其中至少一个通知消息602指示在已第二网络设备610处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备610处丢失的一个或多个数据包603。

在特定实施例中，当接收到从未接收到的编号为PSN的新数据包时，第二网络设备610可以更新接收方侧的位图。具体地，如果PSN>MaxDataRx，则第二网络设备610可以将MaxDataRx设置为PSN的值。如果PSN＝ExpectedPSN，则第二网络设备610可以更新ExpectedPSN。如果MaxDataRx>ExpectedPSN–1(存在丢失数据包)，则第二网络设备610可以发送SACK，否则可以发送ACK。

值得一提的是，为了节省带宽，第二网络设备610可以不针对每一接收到的数据包发送ACK或SACK。例如，接收方可以维护计数器，并在接收到N个数据包之后发送ACK或SACK，其中N≥1。在这种情况下，接收方还应该具有定时器，如果在超时时段内没有接收到N个数据包，则触发ACK/SACK的传输。

可选地，第二网络设备610还可以用于在定时器超时时向第一网络设备600传输至少一个通知消息602。

需要说明的是，流量是双向的，因此每个端点既是发送方，也是接收方。可能地，在具体实现方式中，图6中所示的第一网络设备600可以是图11中所示的第二网络设备610。

此外，需要注意的是，如先前实施例中描述的算法作出了数据包按序路由的隐藏假设。例如，如图8中所示，当在数据包(1)之后接收到数据包(4)时，接收方假设数据包(2)和数据包(3)丢失。这是因为如果这些数据包没有丢失，它们应该在数据包(4)之前被接收。但是，如果数据包不一定在同一路径上路由，则数据包(2)和/或数据包(3)可能会在数据包(4)之后被接收。

另一个示例是当发送方接收到数据包编号StampedMaxDataTx的ACK，并假设所有重传数据包都应该在此数据包之前被接收时。只有当网络保证数据包按序路由时，此假设才成立。

但是，在某些情况下，网络不一定确保数据包按序路由。本发明中提出的LERP也可以适用于此类情况。对于LERP的修改版本，发送方维护变量K，该变量指示乱序距离，即，当数据包都从发送方发送到接收方时，有多少个数据包可以绕过某个数据包。

例如，有两个数据包：数据包(i)和数据包(j)，其中i>j。也就是说，发送方在数据包(i)之前发送数据包(j)，而接收方在数据包(j)之前接收到数据包(i)。乱序距离被定义为i–j。例如，如果数据包(6)在数据包(4)之前被接收，则乱序距离为2。这意味着一个数据包绕过了两个先前发送的数据包。

需要注意的是，假设数据包可以乱序接收，但每两个乱序接收的数据包之间有最大距离。最大距离的值为变量K，其中K≥0。K＝0是数据包始终按序接收的特殊情况。在接收方接收数据包(2)然后接收数据包(6)的情况下，如果K＝2，则数据包(6)可能在数据包(4)和数据包(5)之前被接收，但不可能在数据包(3)之前被接收。因此，接收方可以确定数据包(3)已经丢失。但是，如果K＝3，当接收到数据包(6)时，接收方还不能决定数据包(3)或数据包(4)或数据包(5)是否丢失。

在图8至图10中讨论的所有示例中，变量K等于0。但如图12中所示，我们看到第二个数据包在第三个数据包之后被接收(K＝1)，第5个数据包在第8个数据包之后被接收(K＝3)。因此，在本示例中，K＝3保持不变。

关于图8至图10中述所讨论的实施例，为了解决K>0的乱序情况，可能需要在发送方算法中进行两次更改，而不需要在接收方算法中进行更改。可以在发送方算法的步骤4中进行更改，该步骤可以如下修改：

4.当接收到SACK(SACK报告丢失的数据包)时：

d.状态←恢复。

e.更新位图。如果SACK报告了当前不在发送方位图中的丢失数据包，则仅将PSN满足(PSN≤SACK.MaxDataRx–K)的数据包添加到位图中

f.如果(StampedMaxDataTx+K)<SACK.MaxDataRx，则重置LastRetx＝MaxIORx。

可选地，参数K可以在连接建立期间协商。例如，K可以在第一网络设备600与第二网络设备610之间的连接建立期间协商。或者，参数K也可以在第一网络设备600/第二网络设备610与例如网络控制器的另一网络设备之间的连接建立期间协商。参数K可以是静态参数，也可以是动态参数。值得注意的是，参数K可以是固定的数字。或者，参数K可以是动态更新的数字，该数字可以在变化时通知发送方和接收方。

如本发明实施例中先前描述的算法使用ACK消息和SACK消息。但它也可以在不使用ACK的情况下实现，因为SACK是ACK的广义化。该算法在传输控制与流量控制之间解耦。为简单起见，它假设接收方的位图被维护以覆盖所有未完成的数据包。但是，该算法可以扩展到还实现流量控制机制，以确保发送方不会发送位图资源(或其他资源)在接收方处不可用的数据包。该算法在拥塞控制与流量控制之间解耦。因此，它可以与几乎所有的拥塞控制算法一起实现。具体地，可以在SACK和ACK消息中携带拥塞控制信息。该算法依赖于RTO机制。RTO机制可以包括估计RTT。RTT估计的信息可以集成到数据包、SACK和ACK中。

图13示出了本发明实施例的方法1300。在本发明的特定实施例中，方法1300由图6中所示的第一网络设备600执行。方法1300包括：步骤1301，向第二网络设备610传输数据包序列601；步骤1302，从第二网络设备610接收至少一个通知消息602，其中至少一个通知消息602指示已在第二网络设备610处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备610处丢失的一个或多个数据包603；步骤1303，在接收到至少一个通知消息602之后，下一步重传丢失的一个或多个数据包603，其中，一个或多个丢失数据包603中的每一个在第一次传输之后由至少一个通知消息602指示为丢失数据包，每个丢失数据包603的序列号X小于L–K，其中K为非负整数的参数。可能地，第二网络设备610是图6或图11中所示的第二网络设备。

图14示出了本发明实施例的方法1400。在本发明的特定实施例中，方法1400由图11中所示的第二网络设备610执行。方法1400包括：步骤1401，从第一网络设备600接收数据包序列601；步骤1402，向第一网络设备600传输至少一个通知消息602，其中至少一个通知消息602指示已在第二网络设备610处接收到的数据包的序列号中的最大序列号L和数据包序列中在最大序列号L之前的在第二网络设备610处丢失的一个或多个数据包603。可能地，第一网络设备600是图6或图11中所示的第一网络设备。

本发明已结合各种实施例作为示例以及实现方式进行描述。但是，根据对附图、本发明和所附权利要求书的研究，本领域技术人员在实践所要求保护的发明时，能够理解和实现其他变化。在权利要求书以及说明书中，词语“包括”不排除其他元件或步骤，且不定冠词“一”或“一个”不排除多个。单个元件或其他单元可以满足权利要求书中描述的若干实体或项目的功能。在互不相同的从属权利要求中列举某些措施并不表示这些措施的组合不能用于有利的实现方式中。

此外，本发明的实施例提供的任何方法可以在具有代码模块的计算机程序中实现，该计算机程序由处理模块运行时，使处理模块执行方法步骤。计算机程序包括在计算机程序产品的计算机可读介质中。计算机可读介质基本上可以包括任何存储器，例如只读存储器(read-only memory，ROM)、可编程只读存储器(programmable read-only memory，PROM)、可擦除PROM(erasable PROM，EPROM)、闪存、电可擦除EPROM(electricallyerasable PROM，EEPROM)或硬盘驱动器。

此外，技术人员认识到，第一网络设备600和第二网络设备610的实施例分别包括用于执行方案的功能、模块、单元、元件等形式的必要通信能力。其他此类构件、单元、元件和功能的示例为：处理器、存储器、缓冲器、控制逻辑、编码器、解码器、速率匹配器、降速率匹配器、映射单元、乘法器、决策单元、选择单元、交换机、交织器、解交织器、调制器、解调器、输入端、输出端、天线、放大器、接收单元、传输单元、DSP、格码调制(trellis-codedmodulation，TCM)编码器、TCM解码器、电源单元、电源馈线、通信接口、通信协议等，它们适当地布置在一起以执行解决方案。

具体地，第一网络设备600和第二网络设备610的一个或多个处理器可以包括例如中央处理单元(central processing unit，CPU)、处理单元、处理电路、处理器、专用集成电路(application specific integrated circuit，ASIC)、微处理器，或可以解释和执行指令的其他处理逻辑的一个或多个实例。因此，表达“处理器”可以表示包括多个处理电路的处理电路系统，该处理电路例如为上述处理电路中的任何、一些或全部。处理电路系统还可以执行用于输入、输出和处理数据的数据处理功能，这些数据处理功能包括数据缓冲和设备控制功能，例如调用处理控制、用户界面控制等。

Claims (15)

1.一种第一网络设备(600)，其特征在于，用于：

向第二网络设备(610)传输数据包序列(601)；

从所述第二网络设备(610)接收至少一个通知消息(602)，其中所述至少一个通知消息(602)指示已在所述第二网络设备(610)处接收到的数据包的序列号中的最大序列号L和所述数据包序列中在所述最大序列号L之前的在所述第二网络设备(610)处丢失的一个或多个数据包(603)；

在接收到所述至少一个通知消息(602)之后，下一步重传一个或多个丢失数据包(603)，其中，所述一个或多个丢失数据包(603)中的每一个在第一次传输之后由所述至少一个通知消息(602)指示为丢失数据包，所述每个丢失数据包(603)的序列号X小于L–K，其中K为非负整数的参数。

2.根据权利要求1所述的第一网络设备(600)，其特征在于，用于：

维护指示所述至少一个通知消息(602)指示的所述丢失数据包的第一数据结构；

响应于所述至少一个通知消息(602)而更新所述第一数据结构。

3.根据权利要求2所述的第一网络设备(600)，其特征在于，用于：

维护指示待重传数据包的第二数据结构；

在重传待重传数据包之后，从所述第二数据结构中删除所述待重传数据包。

4.根据权利要求3所述的第一网络设备(600)，其特征在于，用于：

如果所述一个或多个数据包(603)在第一次传输之后由所述至少一个通知消息(602)指示为丢失数据包，并且所述每个丢失数据包(603)的所述序列号X小于L–K，则将所述一个或多个数据包添加到所述第二数据结构中。

5.根据权利要求4所述的第一网络设备(600)，其特征在于，用于：

如果满足以下条件，则将所述一个或多个数据包(603)再次添加到所述第二数据结构中：

–所述一个或多个数据包(603)已经被重传，

–所述第一网络设备(600)接收到另一通知消息，其中所述另一通知消息指示所述一个或多个数据包(603)在所述第二网络设备(610)处仍然丢失，

–所述另一通知消息还指示已在所述第二网络设备(610)处接收到的另一数据包，其中所述另一数据包是在所述一个或多个数据包(603)的最后重传之后首次发送的，

–所述另一通知消息指示的所述另一数据包具有不小于Y+K的序列号，其中Y为所述一个或多个数据包(603)的最后重传之后首次发送的第一数据包的序列号。

6.根据权利要求3至5中任一项所述的第一网络设备(600)，其特征在于，用于在第一状态和第二状态下操作，

其中，在所述第一状态下，所述第一网络设备(600)用于：

传输新数据包；

其中，在所述第二状态下，所述第一网络设备(600)用于：

根据所述第二数据结构重传所述丢失数据包。

7.根据权利要求6所述的第一网络设备(600)，其特征在于，在所述第一状态下，所述第一网络设备(600)用于：

如果所述第二数据结构不为空，则进入所述第二状态；和/或

如果所述第二数据结构为空，则保持在所述第一状态。

8.根据权利要求6或7所述的第一网络设备(600)，其特征在于，在所述第二状态下，所述第一网络设备(600)用于：

如果所述第二数据结构为空，则进入所述第一状态，和/或

如果所述第二数据结构不为空，则保持在所述第二状态。

9.根据权利要求3至8中任一项所述的第一网络设备(600)，其特征在于，还用于：

使用定时器，并在传输新数据包和/或重传丢失数据包时设置所述定时器；

当所述定时器超时，将未接收到确认的所有数据包添加到所述第二数据结构中。

10.根据权利要求9所述的第一网络设备(600)，其特征在于，还用于：

将所述定时器设置为大于往返时间的值。

11.一种第二网络设备(610)，其特征在于，用于：

从第一网络设备(600)接收数据包序列(601)；

向所述第一网络设备(600)传输至少一个通知消息(602)，其中所述至少一个通知消息(602)指示已在所述第二网络设备(610)处接收到的数据包的序列号中的最大序列号L和所述数据包序列中在所述最大序列号L之前的在所述第二网络设备(610)处丢失的一个或多个数据包(603)。

12.根据权利要求11所述的第二网络设备(610)，其特征在于，还用于：

当定时器超时，向所述第一网络设备(600)传输所述一个或多个丢失数据包(603)中的每一个的所述至少一个通知消息(602)。

13.一种由第一网络设备(600)执行的方法(1300)，其特征在于，所述方法(1300)包括：

向第二网络设备(610)传输(1301)数据包序列(601)；

从所述第二网络设备(610)接收(1302)至少一个通知消息(602)，其中所述至少一个通知消息(602)指示已在所述第二网络设备(610)处接收到的数据包的序列号中的最大序列号L和所述数据包序列中在所述最大序列号L之前的在所述第二网络设备(610)处丢失的一个或多个数据包(603)；

在接收到所述至少一个通知消息(602)之后，下一步重传(1303)一个或多个丢失数据包(603)，其中，所述一个或多个丢失数据包(603)中的每一个在第一次传输之后由所述至少一个通知消息(602)指示为丢失数据包，所述每个丢失数据包(603)的序列号X小于L–K，其中K为非负整数的参数。

14.一种由第二网络设备(610)执行的方法(1400)，其特征在于，所述方法(1400)包括：

从第一网络设备(600)接收(1401)数据包序列(601)；

向所述第一网络设备(600)传输(1402)至少一个通知消息(602)，其中所述至少一个通知消息(602)指示已在所述第二网络设备(610)处接收到的数据包的序列号中的最大序列号L和所述数据包序列中在所述最大序列号L之前的在所述第二网络设备(610)处丢失的一个或多个数据包(603)。

15.一种计算机程序，其特征在于，包括用于在计算机上运行时执行根据权利要求13或14所述的方法(1300、1400)的程序代码。