CN112385186B - 用于对数据包进行排序的设备和方法 - Google Patents

Abstract

本发明提供一种用于对数据包进行排序，尤其是对无序到达的数据包进行重新排序的设备和方法。为此目的，所述设备包括用于存储所接收数据包的缓冲区和用于控制所述缓冲区以将每个所接收数据包存储在对应于与所述数据包相关联的唯一序列号的不同缓冲区位置处的处理逻辑。此外，所述处理逻辑用于控制读指针指向缓冲区位置，接着从所述缓冲区从所述缓冲区位置输出数据包，控制最后写指针指向与最高序列号相关联的所接收数据包的缓冲区位置，并控制第一间隙指针指向第一所接收无序数据包的缓冲区位置。所述处理逻辑还用于维持前计数器，所述前计数器存储在所述读指针与所述第一间隙指针之间的空缓冲区位置的数量，并且用于维持后计数器，所述后计数器存储在所述第一间隙指针之后的空缓冲区位置的数量。

Description

用于对数据包进行排序的设备和方法

技术领域

本发明大体上涉及通信系统和交换结构。确切地说，本发明涉及一种用于对所接收数据包进行排序，尤其是对所接收无序数据包进行重新排序的设备和方法。由此，所述设备和方法能够处理通信系统中的偶发性丢包。

背景技术

通信系统由彼此连接的多个交换机(称为网络或结构)组成，以便允许多个节点彼此通信。节点是任何能够使用所述网络(即，计算机、工作站、数据存储设备/阵列或网络接口)进行通信的设备。一般来说，节点能够同时传输并接收数据包。在给定数据包的传输中，传输数据包的节点在下文中称为传输或源节点，并且接收数据包的节点在下文中称为接收或目的地节点。

交换机含有多个双向端口。交换机的端口连接到其它交换机或连接到通信节点。整个网络包括多个交换机以及通过交换机的端口而彼此连接的多个节点，如在图13中示例性地说明。

通过网络在两个节点之间设置的任何连接都用唯一信息标识，所述唯一信息保存在每个从源传输到目的地的数据包(称为标头)内(当使用TCP和以太网协议时，此信息通常称为5元组)。从同一源到同一目的地的数据包统称为“流”。有可能存在从同一源到同一目的地的多个流。然而，每个流都是唯一标识的。

基于交换机内为每个数据包制定的路由决策，将来自输入端口的到达流量引导到输出端口。通常，交换机为流选择相同输出端口(即，将来自特定源的所有数据包都路由到特定目的地)。此方法避免了数据包无序地到达目的地的情况。如果通过不同输出端口发送给定流的数据包，则所述流的数据包可能会由于网络内的路径长度不同而无序(不按顺序)地到达目的地。

然而，完全通过网络中的唯一路径发送给定流效率不高，因为这很容易在网络中产生拥塞区域，同时使其它区域未被充分利用。因此，各种技术试图优化通过网络的数据包传输，以便最小化特定路径上的拥塞并减小时延(即，从源到目的地的传输时间)。所有技术都旨在通过交换机的不同输出端口传递给定流的数据包。

然而，这些技术可能会导致数据包无序地到达目的地。因此，在目的地需要重新排序机制。此外，网络有时可能会出于各种原因而丢弃数据包，例如，在数据包传递期间出现数据损坏，由于拥塞(存储区域不足)而在交换机内做出决策等。因此，为了利用所述技术，每个目的地需要能够对给定流的数据包的到达流进行重新排序，并将所述数据包依序传递到实际终端用户，同时还要处置网络中的丢包。丢包意味着至少一些数据包将不会到达它们的目的地。

一种用于对数据包进行重新排序的常规机制需要每个源将序列号(SN)附接到每个已传递的数据包上。每个数据包的SN都是唯一的且在每次发送数据包时递增。例如，当发送n个数据包时，第1个数据包的SN为i，第2个数据包的SN为i+1，第3个数据包的SN为i+2，依此类推，而第n个数据包的SN为i+n-1。在每个源与目的地之间，SN的序列必须是唯一的。例如，如果一个特定源具有两个目的地，分别是A和B，则这个源需要维持两个不同的序列，一个用于源A，另一个用于源B。

在这个用于对数据包进行重新排序的常规机制中，目的地使用从特定源接收的SN，以便将所接收的数据包重新排序为它们的原始序列，即，重新排序为它们从这个源离开的序列。当这样做时，目的地必须考虑到一些数据包可能已被网络丢弃的情况，并且近期内不会到达所述目的地(值得注意的是，源与目的地之间的高级别协议可能会识别出丢包，且所述目的地可能会请求重新传输所丢失的数据包)。

一种在目的地使用来自特定源的数据包的到达SN的常规重新排序机制借助用于存储所到达的数据包(或存储指向到达数据包的指针，同时将数据包存储在通用存储器中)的缓冲区而实现。缓冲区通常维持以下两个值：

·读指针(RdPtr)，它是从缓冲区中读取已处于序列中的数据包的指针。

·预期序列号(ExpSN)，其中SN对应于由RdPtr指向的条目。

此机制的示例在图14中示出。每个到达数据包都相对于ExpSN根据其SN写入缓冲区，即，写入等于SN-ExpSN的缓冲区位置。这意味着数据包被写入缓冲区中对应于其在数据包流中的序列的缓冲区位置，所述序列由源基于SN确定。当在由RdPtr指向的位置中存在数据包时，此数据包被视为有序(按顺序)数据包，并且可以从缓冲区中读出。当从缓冲区中读出数据包时，RdPtr以1递增，且ExpSN也以1递增。

由于网络中每个数据包的时延不同，所以最大方差被定义为多个到达无序数据包之间的最大间隙。如果在期望具有ExpSN的数据包时，最大方差被定义为数据包的数量，则具有高于ExpSN+最大方差的SN的数据包将无法到达目的地。多个到达数据包之间的最大方差决定了缓冲区大小，因为缓冲区中累积数据包的最大数量必须容纳在所述最大方差内到达的所有数据包。

通过以下伪码来说明上文所描述的重新排序机制的算法(此伪码并不考虑初始化进程，使得源处的SN匹配目的地处的ExpSN)：

初始化(重置)时：

RdPtr＝0

ExpSN＝0//假定所有源均以SN＝0开头

数据包到达(具有SN)时：

//数据包在RdPtr移位之后到达，或者

//数据包到达且超出缓冲区大小

如果((SN<ExpSN)或(SN>ExpSN+缓冲区大小)

立即将此数据包传出缓冲区

否则

WriteAddress＝RdPtr+(SN-ExpSN)

在缓冲区中的位置WriteAddress写入数据包

在每个时钟周期中：

如果(RdPtr处的位置具有有效数据包)

将数据包传出缓冲区

RdPtr++

当网络不可能发生偶发性丢包，从而确保每个所传输的数据包都能到达其目的地时，数据包到达RdPtr位置的等待时间就无关紧要，因为数据包最终将到达并被传出缓冲区。然而，当网络可能发生偶发性丢包时，数据包到达RdPtr位置的等待时间必须受到限制，以免等待时间无限长。因此，等待时间通常被限制为与最大方差时间相关的值。如果在此等待时间期间数据包并未到达，则被视为丢包，并将RdPtr递增到下一位置。

如果等待时间过长，则会发生缓冲区膨胀，因为在所述时间期间没有数据包从缓冲区传出去。如果等待时间过短，则无序数据包将会从缓冲区传出去，因为RdPtr位置处的数据包最终可到达(未丢弃)且从缓冲区传出去。

发明内容

当使用上文所描述的常规重新排序机制时，且当网络偶尔丢弃一个或多个数据包时，需要识别数据包到达目的地的序列中的间隙，并等待足够长的时间以使数据包能够到达，但不用等待太久，因为等待时间过长会导致缓冲区膨胀。

以下方法原则上是可行的解决方案：

1.为每个到达数据包应用具有最大允许时间的计时器(例如，如果可以测量，则最大允许等待时间可以是网络的最大方差)。当计时器到期时，将对应的数据包和所有先前的数据包转发到缓冲区之外，而不用等待它们中还没有到达的数据包。

不利的是，此方法中每个数据包都需要一个计时器，这在硬件上是昂贵的。此外，可以累积的数据包的数量(也是计时器的数量)取决于网络提供的最大方差。

2.一种初级的方法是将计时器应用于要放置在RdPtr位置的数据包中(当缓冲区不为空时，这意味着数据包无序到达)。通过此方法，每个空RdPtr都等待最大超时值。不利的是，即使到达无序数据包跳过了两个数据包指针，每个数据包也必须等待最大超时。因此，此方法过于保守。

鉴于上述问题和不利的解决方案，本发明旨在改进常规的重新排序机制。本发明的目标是提供一种用于以更高效率对所接收数据包进行排序的设备和方法。因此，不需要太多额外的硬件资源来实现解决方案，但是，所述解决方案也不会太保守。确切地说，本发明旨在提供一种能够准确地检测到达数据包之间的间隙且跟踪所述间隙的填充水平的机制。此外，本发明意图以更有效的方式使用一个或多个计时器。即，应确保等待时间不会太短也不会太长。

本发明的目标通过所附独立权利要求中提供的解决方案实现。在从属权利要求中进一步定义了本发明的有利实施方案。

本发明背后的假设是，一旦一定数量的无序数据包到达，除了在网络中丢弃的数据包之外，所有先前的数据包都应在最大方差时间内到达目的地。本发明的一个实现想法是使用两个计数器。当在到达数据包(即，到达的无序数据包)序列中检测到间隙时，一个计数器会对在一数据包之前到达且产生间隙的数据包的数量进行计数(即，到达数据包的SN小于此数据包的SN)，另一个计数器会对在一数据包之后到达且产生间隙的数据包的数量进行计数(即，到达数据包的SN高于此数据包的SN)。

本发明的第一方面提供一种用于对所接收数据包进行排序的设备，所述设备包括：缓冲区，其用于存储所述所接收数据包；以及处理逻辑，其用于：控制所述缓冲区以将每个所接收数据包存储在对应于与所述数据包相关联的唯一SN的不同缓冲区位置，控制读指针指向缓冲区位置，接着从缓冲区从所述缓冲区位置输出数据包，控制最后写指针指向与最高SN相关联的所接收数据包的缓冲区位置，控制第一间隙指针指向第一所接收无序数据包的缓冲区位置，维持前计数器，所述前计数器存储在所述读指针和所述第一间隙指针之间的空缓冲区位置的数量，并且维持后计数器，所述后计数器存储在所述第一间隙指针之后的空缓冲区位置的数量。

在缓冲区中存储数据包尤其包括将整个数据包(数据包信息)写入缓冲区，或将指向数据包的指针写入缓冲区，同时将整个数据包(数据包信息)写入通用存储器等等中。

控制最后写指针和第一间隙指针使得能够识别出到达数据包序列中的间隙。然而，不需要太多额外的硬件来实现这些指针。作为上文所提及的两个计数器的后计数器和前计数器的维持能够跟踪数据包序列中的间隙的填充水平。综上所述，第一方面的设备实现了一种比常规使用的设备更有效的排序或重新排序机制。

在第一方面的实现形式中，处理逻辑进一步用于：如果数据包存储在读指针的缓冲区位置处，则从缓冲区输出所接收数据包。

在第一方面的另一实现形式中，处理逻辑进一步用于丢弃具有对应于在读指针之前的缓冲区位置的SN的所接收数据包或绕过缓冲区输出所接收数据包。

因此，所述设备非常适合有时出于一些原因而不得不丢弃数据包的网络。

在第一方面的另一实现形式中，处理逻辑进一步用于：如果所接收数据包存储在读指针和第一间隙指针之间的空缓冲区位置，则使前计数器递减；且如果前计数器减小到0，则将第一间隙指针移动到最后写指针，或如果最后写指针无效，则使前计数器失效。

因此，前计数器允许跟踪读指针与第一间隙指针之间的间隙的填充，即数据包序列中的第一间隙的填充。一旦间隙被填满，就将第一间隙指针移动到最后写指针，且将第一间隙指针的先前位置和第一间隙指针的新位置之间的范围视为下一间隙，此间隙可能已经填充有一些数据包(根据后计数器)。

在第一方面的另一实现形式中，处理逻辑进一步用于：如果前计数器减小到0并且如果最后写指针有效，则根据后计数器设置前计数器，并重置后计数器，否则前计数器保持为0。

因此，后计数器用作下一个间隙的预处理，并且如果第一间隙是闭合的，则后计数器的值将转移到前计数器。

在第一方面的另一实现形式中，处理逻辑进一步用于如果所接收数据包存储在第一间隙指针和最后写指针之间的空缓冲区位置，则使后计数器递减。

因此，后计数器跟踪下一间隙的填充。

在第一方面的另一实现形式中，处理逻辑进一步用于当控制第一间隙指针移动到另一缓冲区位置或从无效变为有效时启动或重新启动计时器。

计时器允许在数据包丢失且从未到达的情况下，即在间隙可能从未被完全填充的情况下，减少等待时间。

在第一方面的另一实现形式中，处理逻辑进一步用于在启动计时器时将计时器限制为接收数据包的最大时间方差，其中最大时间方差定义为数据包的最快到达时间与数据包的最慢到达时间之间的差。

这提供了等待时间和数据包传输效率之间的最佳折衷方案。

在第一方面的另一实现形式中，处理逻辑进一步用于当重新启动计时器时，将计时器限制为基于后计数器校正的接收数据包的最大时间方差。

由于一些数据包已经到达并且由后计数器跟踪，因此计时器持续时间可以减少，以便优化等待时间。

在第一方面的另一实现形式中，处理逻辑进一步用于在计时器到期的情况下将缓冲区设置为超时状态。

在超时状态下，为设备提供关于处理各种指针和计数器的一些特定功能。

在第一方面的另一实现形式中，处理逻辑进一步用于：在超时状态下，通过移动读指针并跳过空缓冲区位置而搜索下一非空缓冲区位置，输出存储在所发现的非空缓冲区位置处的数据包，且将读指针进一步移动到在所输出数据包的缓冲区位置之后的缓冲区位置。

因此，可快速输出下一数据包，且因此减少等待时间。

在第一方面的另一实现形式中，处理逻辑进一步用于：在超时状态下，将具有对应于被跳过的缓冲区位置的SN的数据包视为已丢弃，及/或将具有对应于在读指针之前的缓冲区位置的SN的所接收数据包视为已丢弃。

因此，设备能够在无低效等待时间的情况下处理丢包。

在第一方面的另一实现形式中，处理逻辑进一步用于：在超时状态下，绕过缓冲区输出被视为已丢弃的到达数据包或丢弃到达数据包。

因此，到达较晚的数据包不会丢失，而借助于缓冲区实现的排序机制的效率也不会受到影响。

在第一方面的另一实现形式中，处理逻辑进一步用于：在超时状态下，将具有对应于在读指针的当前缓冲区位置之后的缓冲区位置的SN的到达数据包存储到缓冲区中，同时移动读指针以搜索下一个非空缓冲区位置。

因此，即使在超时状态下，如果并不妨碍根据读指针输出数据包，则仍然可以保存数据包。

在第一方面的另一实现形式中，处理逻辑进一步用于：当读指针指向与第一间隙指针相同的缓冲区位置时或当缓冲区为空时，从超时状态退出。

在第一方面的另一实现形式中，处理逻辑进一步用于：当读指针指向与第一间隙指针相同的缓冲区位置且缓冲区不为空且最后写指针有效并且后计数器大于0时，重新进入超时状态，并在重新进入超时状态时重新启动计时器。

在第一方面的另一实现形式中，处理逻辑进一步用于维持与读指针的缓冲区位置相对应的预期SN。

在第一方面的另一实现形式中，所述设备进一步包括解析器，所述解析器用于抽取与所接收数据包相关联的SN且将所抽取的SN提供到处理逻辑。

本发明的第二方面提供一种用于对所接收数据包进行排序的方法，所述方法包括：控制缓冲区以将每个所接收数据包存储在对应于与所述数据包相关联的唯一序列号SN的不同缓冲区位置，控制读指针指向缓冲区位置，接着从所述缓冲区从所述缓冲区位置输出数据包，控制最后写指针指向与最高SN相关联的所接收数据包的缓冲区位置，控制第一间隙指针指向第一所接收无序数据包的缓冲区位置，维持前计数器，所述前计数器存储在所述读指针和所述第一间隙指针之间的空缓冲区位置的数量，并且维持后计数器，所述后计数器存储在所述第一间隙指针之后的空缓冲区位置的数量。

在第二方面的一种实现形式中，所述方法进一步包括：如果数据包存储在读指针的缓冲区位置，则从缓冲区输出所接收数据包。

在第二方面的另一实现形式中，所述方法进一步包括：丢弃具有与在读指针之前的缓冲区位置相对应的SN的所接收数据包或绕过缓冲区输出所接收数据包。

在第二方面的另一实现形式中，所述方法进一步包括：如果所接收数据包存储在读指针和第一间隙指针之间的空缓冲区位置，则使前计数器递减；且如果前计数器减小到0，则将第一间隙指针移动到最后写指针；或如果最后写指针无效，则使前计数器无效。

在第二方面的另一实现形式中，所述方法进一步包括：如果前计数器减小到0，且如果最后写指针有效，则根据后计数器设置前计数器且随后重置后计数器，否则前计数器保持为0。

在第二方面的另一实现形式中，所述方法进一步包括：如果所接收数据包存储在第一间隙指针与最后写指针之间的空缓冲区位置处，则使后计数器递减。

在第二方面的另一实现形式中，所述方法进一步包括：当控制第一间隙指针移动到另一缓冲区位置或从无效变为有效时，启动或重新启动计时器。

在第二方面的另一实现形式中，所述方法进一步包括：在启动计时器时将计时器限制为接收数据包的最大时间方差，其中最大时间方差定义为数据包的最快到达时间与数据包的最慢到达时间之间的差。

在第二方面的另一实现形式中，所述方法进一步包括：当重新启动计时器时，将计时器限制为基于后计数器校正的接收数据包的最大时间方差。

在第二方面的另一实现形式中，所述方法进一步包括：在计时器到期的情况下将缓冲区设置为超时状态。

在第二方面的另一实现形式中，所述方法进一步包括：在超时状态下，通过移动读指针并跳过空缓冲区位置而搜索下一非空缓冲区位置，输出存储在所发现的非空缓冲区位置处的数据包，且将读指针进一步移动到在所输出数据包的缓冲区位置之后的缓冲区位置。

在第二方面的另一实现形式中，所述方法进一步包括：在超时状态下，将具有对应于被跳过的缓冲区位置的SN的数据包视为已丢弃，及/或将具有对应于在读指针之前的缓冲区位置的SN的所接收数据包视为已丢弃。

在第二方面的另一实现形式中，所述方法进一步包括：在超时状态下，绕过缓冲区输出被视为已丢弃的到达数据包或丢弃所述到达数据包。

在第二方面的另一实现形式中，所述方法进一步包括：在超时状态下，将具有对应于在读指针的当前缓冲区位置之后的缓冲区位置的SN的到达数据包存储到缓冲区中，同时移动读指针以搜索下一个非空缓冲区位置。

在第二方面的另一实现形式中，所述方法进一步包括：当读指针指向与第一间隙指针相同的缓冲区位置时或当缓冲区为空时，从超时状态退出。

在第二方面的另一实现形式中，所述方法进一步包括：当读指针指向与第一间隙指针相同的缓冲区位置且缓冲区不为空且最后写指针有效并且后计数器大于0时，重新进入超时状态，并在重新进入超时状态时重新启动计时器。

在第二方面的另一实现形式中，所述方法进一步包括：维持对应于读指针的缓冲区位置的预期SN。

在第二方面的另一实现形式中，所述方法进一步包括：抽取与所接收数据包相关联的SN且将所抽取的SN提供到处理逻辑。

第二方面的方法和其实现形式实现了第一方面的设备和其相应实现形式的上述所有优点和效果。

必须注意，在本申请中描述的所有设备、元件、单元和装置都可以在软件或硬件元件或其任何种类的组合中实施。本申请中描述的各种实体所执行的所有步骤和所描述的将由各种实体执行的功能旨在表明各个实体适于或用于执行相应步骤和功能。虽然在以下具体实施例的描述中，由外部实体执行的特定功能或步骤没有在执行所述特定步骤或功能的所述实体的具体元件的描述中反映出来，但是技术人员应该清楚的是这些方法和功能可以在相应的硬件或软件元件或其任意组合中实现。

附图说明

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

图1示出了根据本发明实施例的设备。

图2示出了根据本发明实施例的设备。

图3示出了具有锁定SN和计时器的示例重新排序。

图4示出了在正常状态下针对入队情况1-4设置计数器/指针。

图5示出了在正常状态下针对入队情况5-6设置计数器/指针。

图6示出了在正常状态下针对入队情况7-8设置计数器/指针。

图7示出了在正常状态下针对入队情况9-12设置计数器/指针。

图8示出了在正常状态下针对出队情况1-5设置计数器/指针。

图9示出了在超时状态下针对入队情况1-4设置计数器/指针。

图10示出了在超时状态下针对出队情况1-4设置计数器/指针。

图11示出了在超时状态下针对出队情况5-7设置计数器/指针。

图12示出了根据本发明实施例的方法。

图13示出了由交换机和节点组成的通信系统的示例。

图14示出了重新排序技术的示例。

具体实施方式

图1示出了用于对所接收数据包101进行排序，尤其是用于对未按顺序到达的数据包101进行重新排序(重新确定顺序)的设备100。设备100包括：缓冲区102，其用于存储到达(即，所接收)数据包101；以及处理逻辑103，其用于控制缓冲区102，且控制指针和维持计数器，如下文所描述。

确切地说，处理逻辑103用于控制缓冲区102，以在对应于与数据包101相关联的唯一SN的不同缓冲区位置104处存储每个所接收数据包101。每个到达数据包101都具有唯一SN，即具有不同的SN。此外，每个缓冲区位置104都与一个所确定的SN有关。因此，处理逻辑103可以控制缓冲区102以根据到达数据包的各个SN依序存储到达数据包。

此外，处理逻辑103用于控制读指针105指向缓冲区位置104，接着从缓冲区102从缓冲区位置104输出数据包101。即，读指针105是用于从缓冲区102读取那些已经在序列中的数据包101的指针。

此外，处理逻辑103用于控制最后写指针106指向与最高SN相关联的所接收数据包101的缓冲区位置104。最后写指针106特别地将到目前为止具有最高SN的所接收数据包101的SN(或缓冲区位置104)存储，不管数据包是否已经写入缓冲区102中。最后写指针106可能带有一个有效指示，用于指示其内容是否有效。

此外，处理逻辑103用于控制第一间隙指针107指向第一所接收无序数据包101的缓冲区位置104。第一间隙指针107存储到达缓冲区102的第一无序数据包101的SN(或缓冲区位置104)，直到所有先前的数据包都到达为止。接着，如果第一间隙指针107的先前值与当前最后写指针值之间存在间隙，则第一间隙指针107可以存储最后写指针106的指针，即，将第一间隙指针107移动到最后写指针。此外，第一间隙指针107可能带有一个有效指示，用于指示其内容是否有效。

此外，处理逻辑103用于维持前计数器108，所述前计数器存储在读指针105与第一间隙指针107之间的空缓冲区位置104的数量。每当数量改变时，例如当接收到新的数据包101时，处理逻辑103用于根据所接收的新数据包101更新所存储的数量。因此，前计数器108存储在第一间隙指针107之前的漏失数据包的数量，即从读指针105到第一间隙指针107的所有数据包的数量。当一个带有在第一间隙指针107之前的SN的数据包到达时，前计数器108递减，因为现在少了1个漏失数据包101。

此外，处理逻辑103用于维持后计数器109，所述后计数器存储在第一间隙指针107之后的空缓冲区位置104的数量。每当数量改变时，例如当接收到新的数据包101时，处理逻辑103用于根据最新接收到的数据包101更新所存储的述空缓冲区位置的数量。因此，后计数器109存储从第一间隙指针107到最后写指针106的未到达数据包101的数量。

图2示出了根据本发明实施例的设备100，其以在图1中示出的设备100为基础。图1和图2中的相同元件用相同的附图标记，并且功能也相同。图2特别示出了用于实现设备100的高级框图。类似于图1，图2示出了数据包缓冲区102、处理逻辑103以及所接收和所输出数据包101。

然而，与图1相比，图2还示出了设备100的解析器200，所述解析器200用于抽取与所接收数据包101相关联的SN，并将所抽取的SN提供给处理逻辑103。因此，到达数据包101首先经过解析器200，使得与数据包101相关联的SN被抽取出。接着所抽取的SN被转发到处理逻辑103，如上所述，所述处理逻辑用于基于到达SN分别管理指针105、106和107以及计数器108和109。处理逻辑103块可确定到达数据包101是要写入数据包缓冲区102还是直接绕过缓冲区进行输出。这可通过控制写入(‘Wr’)和‘绕过’指示来完成。并且，处理逻辑103用于基于读指针105(状态)并且潜在地另外基于来自接收数据包101的输出有序流的下一块的流控制来管理来自数据包缓冲区102的读取。

在下文中，将更详细地描述如图1或图2所示的设备100的操作。设备100能够执行的主要步骤是：

·锁定第一无序到达数据包101的SN。这意味着数据包101到达的时间太早，因此在此数据包之前存在一个或多个尚未到达的数据包101。

·当锁定SN时，将第一间隙指针107设置成指向与锁定的SN相对应的缓冲区位置104，即，它可从无效变为有效。计时器在最大方差的持续时间内开始计数。具体地说，处理逻辑103用于当控制第一间隙指针107从无效变为有效时，或者控制第一间隙指针107移动到另一缓冲区位置104时，启动或重新启动计时器。

·如果在锁定的SN之前的所有数据包101并未全都在最大方差时间内到达，即当计时器在接收到所有数据包101之前到期时，为缓冲区102声明超时。换句话说，缓冲区102进入超时状态。

·如果在锁定的SN之前的所有数据包101都在最大方差时间内到达，即在计时器到期之前到达，则释放SN的锁定，并且第一间隙指针107被控制指向当时最早到达的数据包的SN。为了监视最早到达的数据包101，最后写指针106始终用于存储最大到达SN。因此，也就是说，第一间隙指针107移动到最后写指针106。

在SN的第一次锁定(通过验证和设置第一间隙指针107)的时间到释放锁定(且第一间隙指针107移动或失效)的时间期间，可能存在多个到达的数据包101，其中一些带有小于锁定SN的SN的数据包，且一些带有高于锁定SN的SN的数据包。当释放锁定SN时，计时器从所述SN重新启动到所有数据包101的最大方差，直到当时的最早到达SN为止。这基本上用单个计数器覆盖了到达数据包101的序列中的任何间隙。因此，为了跟踪到达无序数据包101之间的间隙并确定是否以及何时应用计时器，控制和维持上述最后写指针106、第一间隙指针107、前计数器108以及后计数器109。

图3示出了上述内容的示例。图3特别示出了以下：

1.数据包1-4依序到达，即迄今为止不存在间隙。因此，第一间隙指针107(到目前为止)无效。最后写指针106指向带有SN＝4的数据包101，因为它现在是所到达数据包101的最高SN。

2.数据包7到达，形成两个缓冲区位置104的间隙(序列中有两个漏失数据包101)。因此，前计数器108设置为2(并且指示用于填充间隙的剩余数据包的数量)，并且第一间隙指针107设置为7。从现在开始，后计数器109对在第一间隙指针107之后的未到达数据包101的数量进行计数。最后写指针106设置为7，因为这是当前接收到的最高SN。

3.数据包5和6到达，以填充间隙。然而，在此期间，数据包13、14、18到达，产生了两个新的间隙。最后写指针106设置为18，因为这是现在到达的最高SN。此时，第一间隙指针107设置为18，前计数器108(达到0)设置为后计数器109的值，即根据后计数器109(指示6个漏失数据包)设置，且后计数器109设置为0。

4.所述间隙由漏失数据包101填充，且由于不存在更多间隙，而且第一间隙指针107失效，因此最后写指针106保持为18，因为没有其它数据包101到达。

在计数时间和等待数据包101在第一间隙指针107之前到达期间，数据包101也可能在第一间隙指针106之后到达。因此，当将第一间隙指针107移位到最后写指针106时，优选地是不再将计时器设置为最大方差，因为数据包101已经在第一间隙指针107之后到达。最大方差应根据数据包的到达时间来计算。为了补偿此时间，可执行以下操作：

始终锁定最后写指针106的到达时间。

1.当将第一间隙指针107移位到最后写指针106时。

a.根据前计数器108设置后计数器109且重置后计数器108。

i.已知填满第一间隙指针107的漏失数据包101的数量。

b.设置计时器＝超时时间-(当前时间-最后写指针106到达时间)。

i.如果计算结果为负，则设置为零或最小值。

2.继续对后计数器109和前计数器108进行计数。

a.如果前计数器109达到数据包101的所需数量。

i.停止计时器

ii.转到步骤1

b.如果计时器在前计数器108达到之前到期，则声明超时。

一般来说，计时器被限制为基于后计数器109校正的接收数据包101的最大时间方差。

在下文中，描述了关于设置计数器108和109以及指针105、106和107的更多细节。由此，将到达数据包101写入缓冲区102的过程称为“入队”。从缓冲区102读取依序数据包101并将其传递的过程称为“出队”。使用这些定义，计数器108、109和指针105-107的大部分更改都会在到达数据包101的入队阶段期间发生。

以下是在系统初始化(重置)之后指针105-107(以及指针的有效指示)和计数器108、109的典型值：

1.第一间隙指针107＝NA(无效)

2.第一间隙指针有效＝0

3.最后写指针106＝NA(无效)

4.最后写指针有效＝0

5.前计数器108＝0

6.后计数器109＝0

图4至11以图形方式示出了在针对入队或出队设置指针105-107和计数器108、109时以及在缓冲区102不处于超时状态时或在所述缓冲区处于超时状态时要考虑的所有情况。

图4示出了当缓冲区102不处于超时状态时的入队情况1-4。起点是空缓冲区102或不为空但没有任何间隙的缓冲区102。情况1示出了数据包101依序到达，且最后写指针106设置为存储所述数据包101的缓冲区位置104。此缓冲区位置104对应于读指针105，使得接下来将输出数据包101。情况2示出了无序数据包101到达，且最后写指针106和第一间隙指针107设置为存储数据包101的缓冲区位置104。前计数器108设置为与读指针105的差，即，设置为4。情况3示出了最后写指针106已设置，此时数据包101依序到达且具有对应于在因此移动的最后写指针107之后的缓冲区位置104的SN。不存在间隙。情况4示出了最后写指针106已设置，并且数据包101不按顺序到达且具有对应于在因此移动的最后写指针107之后的缓冲区位置104SN。由于形成了间隙，设置第一间隙指针107、前计数器108和后计数器。

图5示出了当缓冲区102不处于超时状态时针对具有对应于在第一间隙指针107之前(情况5)和在第一间隙指针107之后(情况6)的缓冲区位置104的SN的到达数据包101的入队情况5-6，其中此时第一间隙指针107等于最后写指针106。在情况5中，前计数器108以1递减，后计数器109(保持)为0。在情况6中，最后写指针106根据到达数据101的SN而移动，并且后计数器以1递增。

图6示出了当缓冲区102不处于超时状态时针对具有对应于在第一间隙指针107之前(情况7)和在第一间隙指针107之后(情况8)的缓冲区位置104的SN的到达数据包101的入队情况7-8，此时第一间隙指针107不等于最后写指针106。在情况7中，前计数器108以1递减，且在情况8中，后计数器以1递增。

图7示出了当缓冲区102不处于超时状态时针对在第一间隙指针107之前的缓冲区位置104处填充间隙(前计数器达到0)的到达数据包101的入队情况9-11。在情况9中，第一间隙指针107在最后写指针106处。在入队之后，不存在更多间隙，使得第一间隙指针107失效。在情况10中，仍然存在另一间隙，使得第一间隙指针107移动到最后写指针106。在情况11中，第一间隙指针107与最后写指针106不同。在入队之后，不存在更多间隙，使得第一间隙指针107失效。图7进一步示出了针对在第一间隙指针107之后的缓冲区位置104处填充间隙的到达数据包101的情况12。在此情况下，当后计数器以1递增时，不移动第一间隙指针107。

图8示出了当缓冲区102不处于超时状态时的出队情况1-5，即示出了在缓冲区102的正常状态下的出队情况。出队阶段并未更改后计数器109和前计数器108的值。情况1示出了数据包101存储在读指针105的缓冲区位置104处。因此，输出数据包101，并且将读指针105移动到下一个缓冲区位置104。情况2示出了相同的情况，但是在情况1中，第一间隙指针107和最后写指针106指向不同的缓冲区位置104，而在情况2中，它们指向相同的缓冲区位置104。情况3示出了多个依序数据包101(无间隙)中的第一数据包101的读取。情况4示出了在最后写指针106处的数据包101的读取，即最后存储的数据包101的读取。在情况5中，第一间隙指针107在出队之前还指向读指针105的缓冲区位置104。

当缓冲区102处于超时状态时，第一间隙指针107的值被锁定，并且在超时状态结束之前不会更改。仅当具有与第一间隙指针107之前的缓冲区位置104相对应的SN的所有数据包101都到达时，入队阶段才能终止超时状态。仅当读指针105等于或大于第一间隙指针107时，出队阶段才能终止超时状态。值得注意的是，在出队期间，可以在搜索缓冲区102中的下一个有效数据包101时跳过读指针105。

图9示出了当缓冲区102处于超时状态时的入队情况1-4。在情况1中，接收具有与在读指针105之后的缓冲区位置104相关的SN的数据包101，并且所述数据包101被存储到缓冲区101中。前计数器108达到0且第一间隙指针107失效。缓冲区102退出超时状态。在情况2中，由于第一间隙被到达数据包101填充，所以缓冲区102针对第一间隙指针107的原始值也退出超时状态，但是针对移动到最后写指针106的第一间隙指针107的新值而重新进入超时状态。情况3与情况1相似，但是第一间隙指针107在出队之前不在最后写指针106处。在情况4中，带有在读指针105之后并且还在第一间隙指针107之后的SN的数据包101到达。因此，后计数器109增加，但保持超时状态。

图10示出了当缓冲区102处于超时状态时的出队情况1-4。应注意，如果未跳过读指针105，则正常状态出队适用于超时状态出队情况。在情况1中，在空缓冲区位置104上跳过读指针105，直到找到要输出的数据包101为止。随后，读指针105移动到在所输出数据包101之后的下一个缓冲区位置104。情况2与情况1相似，但第一间隙指针107在输出数据包101之后移位到最后写指针106，因为序列中存在间隙(由后计数器109的值指示)，并且新的超时开始。在情况3中，由于第一间隙指针107与最后写指针106之间不存在间隙，因此第一间隙指针107失效，且超时状态在输出数据包101之后终止。在情况4中，读指针105跳到在最后写指针106的缓冲区位置104处的数据包101，所述数据包101被输出并且超时状态终止。

图11示出了当缓冲区102处于超时状态时的出队情况5-7。在情况5中，在可以输出下一个数据包101之前跳过缓冲区位置104。第一间隙指针107和最后写指针106设置为不同的缓冲区位置104。在情况6中，读指针105位于数据包101的位置104，无需跳过缓冲区位置104即可输出所述数据包。在情况7中，输出最后的依序数据包101。然后，将第一间隙指针107移动到最后写指针106，根据后计数器109设置前计数器108，并将后计数器109重置为0。

图12示出了根据本发明实施例的方法1200。方法1200可由例如在图1或图2中所示出的设备100执行。方法1200包括步骤1201：控制缓冲区以将每个所接收数据包101存储在对应于与数据包101相关联的唯一SN的不同缓冲区位置104处。此外，所述方法包括步骤1202：控制读指针105指向缓冲区位置104，接着从缓冲区102从缓冲区位置104输出数据包101。方法1200进一步包括步骤1203：控制最后写指针106指向与最高SN相关联的所接收数据包101的缓冲区位置105；以及步骤1204：控制第一间隙指针107指向第一所接收无序数据包101的缓冲区位置104。方法1200还包括步骤1205：维持存储在读指针105与第一间隙指针107之间的空缓冲区位置104的数量的前计数器108，以及步骤1206：维持存储在第一间隙指针107之后的缓冲区位置104处存储的所接收数据包101的数量的后计数器109。

已经结合作为实例的不同实施例以及实施方案描述了本发明。但本领域技术人员通过实践所请发明，研究附图、本公开以及独立权利要求项，能够理解并获得其它变体。在权利要求以及描述中，术语“包括”不排除其它元件或步骤，且“一”并不排除复数可能。单个元件或其它单元可满足权利要求书中所叙述的若干实体或项目的功能。在某些措施被记载在相互不同的从属权利要求书中这个单纯的事实并不意味着这些措施的结合不能在有利的实现方式中使用。

Claims (19)

1.一种用于对所接收数据包(101)进行排序的设备(100)，其特征在于，所述设备(100)

包括

缓冲区(102)，所述缓冲区(102)用于存储所述所接收数据包(101)，以及

处理逻辑(103)，其用于

-控制所述缓冲区(102)以将每个所接收数据包(101)存储在对应于与所述数据包(101)相关联的唯一序列号SN的不同缓冲区位置(104)，

-控制读指针(105)指向缓冲区位置(104)，接着从所述缓冲区(102)从所述缓冲区位置(104)输出数据包(101)，

-控制最后写指针(106)指向与最高SN相关联的所接收数据包(101)的缓冲区位置(104)，

-控制第一间隙指针(107)指向第一所接收无序数据包(101)的缓冲区位置(104)，

-维持前计数器(108)，所述前计数器(108)存储在所述读指针(105)和所述第一间隙指针(107)之间的空缓冲区位置(104)的数量，并且

-维持后计数器(109)，所述后计数器(109)存储在所述第一间隙指针(107)之后的空缓冲区位置(104)的数量。

2.根据权利要求1所述的设备(100)，其特征在于

所述处理逻辑(103)进一步用于

-如果所述数据包(101)存储在所述读指针(105)的所述缓冲区位置(104)处，则从所述缓冲区(102)输出所接收数据包(101)。

3.根据权利要求1或2所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-丢弃具有对应于在所述读指针(105)之前的缓冲区位置(104)的SN的所接收数据包(101)或绕过所述缓冲区(102)输出所述所接收数据包(101)。

4.根据权利要求1所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-如果所接收数据包(101)存储在所述读指针(105)与所述第一间隙指针(107)之间的空缓冲区位置(104)处，则使所述前计数器(108)递减，

-如果所述前计数器(108)减小到0，则将所述第一间隙指针(107)移动到所述最后写指针(106)，或如果所述最后写指针(106)无效，则使所述前计数器(108)失效。

5.根据权利要求4所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-如果所述前计数器(108)减小到0且如果所述最后写指针(106)有效，则根据所述后计数器(109)设置所述前计数器(108)，且随后重置所述后计数器(109)，否则所述前计数器(108)保持为0。

6.根据权利要求1所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-如果所接收数据包(101)存储在所述第一间隙指针(107)与所述最后写指针(106)之间的空缓冲区位置(104)处，则使所述后计数器(109)递减。

7.根据权利要求1所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-当控制所述第一间隙指针(107)移动到另一缓冲区位置(104)或从无效变为有效时，启动或重新启动计时器。

8.根据权利要求7所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在启动所述计时器时，

-将所述计时器限制为接收数据包(101)的最大时间方差，其中所述最大时间方差被定义为数据包(101)的最快到达时间与数据包(101)的最慢到达时间之间的差；所述最快到达时间和所述最慢到达时间是基于测量先前的数据包在网络中的传输过程得到的。

9.根据权利要求7所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在重新启动所述计时器时，

-将所述计时器限制为基于所述后计数器(109)校正的接收数据包(101)的最大时间方差。

10.根据权利要求7所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-在所述计时器到期的情况下，则将所述缓冲区(102)设置为超时状态。

11.根据权利要求10所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在所述超时状态下，

-通过移动所述读指针(105)且跳过空缓冲区位置(104)而搜索下一个非空缓冲区位置(104)，

-输出存储在发现的非空缓冲区位置(104)处的所述数据包(101)，并且

-将所述读指针(105)进一步移动到在所输出数据包(101)的所述缓冲区位置(104)之后的所述缓冲区位置(104)。

12.根据权利要求11所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在所述超时状态下，

-将具有对应于被跳过的缓冲区位置(104)的SN的数据包(101)视为已丢弃，及/或

-将具有对应于在所述读指针(105)之前的缓冲区位置(104)的SN的所接收数据包(101)视为已丢弃。

13.根据权利要求12所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在所述超时状态下，

-绕过所述缓冲区输出被视为已丢弃的到达数据包(101)或丢弃所述到达数据包(101)。

14.根据权利要求11至13中任一权利要求所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于在所述超时状态下，

-将具有对应于在所述读指针(105)的当前缓冲区位置(104)之后的缓冲区位置(104)的SN的到达数据包(101)存储到所述缓冲区(102)中，同时移动所述读指针(105)以搜索所述下一个非空缓冲区位置(104)。

15.根据权利要求10所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-当所述读指针(105)指向与所述第一间隙指针(107)相同的缓冲区位置(104)时或当所述缓冲区(102)为空时，从所述超时状态退出。

16.根据权利要求15所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于

-当所述读指针(105)指向与所述第一间隙指针(107)相同的缓冲区位置(104)且所述缓冲区(102)不为空且所述最后写指针(106)有效且所述后计数器(109)高于0时，重新进入所述超时状态，

-当重新进入所述超时状态时，重新启动所述计时器。

17.根据权利要求1所述的设备(100)，其特征在于，

所述处理逻辑(103)进一步用于维持

-与所述读指针(105)的所述缓冲区位置(104)相对应的预期SN。

18.根据权利要求1所述的设备(100)，其特征在于，进一步包括

解析器(200)，其用于抽取与所接收数据包(101)相关联的SN且将所抽取的SN提供到所述处理逻辑(103)。

19.一种用于对所接收数据包(101)进行排序的方法(1200)，其特征在于，所述方法(1200)

包括

-控制缓冲区(102)以将每个所接收数据包(101)存储在对应于与所述数据包(101)相关联的唯一序列号SN的不同缓冲区位置(104)，

-控制读指针(105)指向缓冲区位置(104)，接着从所述缓冲区(102)从所述缓冲区位置(104)输出数据包(101)，

-控制最后写指针(106)指向与最高SN相关联的所接收数据包(101)的缓冲区位置(104)，

-控制第一间隙指针(107)指向第一所接收无序数据包(101)的缓冲区位置(104)，

-维持前计数器(108)，所述前计数器(108)存储在所述读指针(105)和所述第一间隙指针(107)之间的空缓冲区位置(104)的数量，并且

-维持后计数器(109)，所述后计数器存储在所述第一间隙指针(107)之后的空缓冲区位置(104)的数量。

Images