用于设置分组交换通信网络中重传超时周期的方法

摘要

本发明涉及一种用于更新数据单元发送器中超时周期的值的方法。更新包括从响应时间的n个最近测量的值推导中间值、增加中间值、缩减超时周期的当前值、从至少增加的中间值和超时周期的缩减的当前值中确定最大量，并且设置超时周期的新值以设置最大值。

说明书

发明领域

本发明涉及一种用于更新数据单元发送器中超时周期的值的方法及被安排执行此方法的数据单元发送器。

发明背景

通常，在通信领域中区别电路交换连接和数据单元交换通信。在数据单元交换连接中，将许多待发送的数据分成数据单元，接着依照控制通信的协议发送这些数据单元。可以注意到，数据单元在不同协议的上下文中得到不同的名称，例如分组、帧、段等。在本申请中，一般利用术语“数据单元”来论及数据的任何这种细分。

为保证数据的可靠传输，许多协议提供数据单元重传的特征。更具体地说，数据单元重传意思是数据单元接收器执行反馈机制，依照它接收器将反馈消息发送到数据单元发送器，其中每个反馈消息包含关于由数据单元发送器发送的数据单元的接收的信息。反馈消息中的信息类型可以是各种类型，例如，可以确认数据单元的正确接收和/或指示所接收数据单元中的错误。这种反馈消息的例子是从TCP或其他协议得知的确认消息或ACK。数据单元发送器依靠反馈消息中的信息，通过重传一个或多个所发送的数据单元对这些反馈消息作出反应。

一般和重传机制一起提供的特征是所谓的重传超时。超时特征意思是，如果数据单元发送器在给定的超时周期内没有接收到指示给定的数据单元的正确接收的反馈消息，数据单元发送器重发所述给定的数据单元。该特征保证如果数据单元丢失，那么丢失的数据单元将在上面所提的超时周期后自动重传。

提供附有超时特征的重传机制的协议的例子是所谓的传输控制协议(TCP)，它是著名的TCP/IP协议组的一部分。

在给定的发送器和给定的接收器之间的通信中，显然超时周期应该以某一方式取决于响应时间。响应时间表示在发送数据单元和接收关于该数据单元的反馈消息之间经过的时间。在TCP和一些其他协议中，该响应也称作环回时间(RTT)。

如果接收器是“远”的(即长的响应时间)，那么应该将超时周期设置得比“近”的接收器(即短的响应时间)长。同样可以理解的是，应该将超时周期设置为必要得长和尽可能得短。即，如果超时周期太短，那么数据单元发送器将不会为反馈消息的接收等待足够长的时间，并且因此非必要地重传给定的数据单元。这种非必要的重传也称作伪重传。换句话说，伪重传意思是如果发送器已经等待了稍微长一点，它将会接收反馈消息并从而不重传该数据单元。另一方面，如果超时周期设置太长，那么这导致传输中非必要的延迟，因为丢失数据单元的重传不会足够快的发生。

用于在响应时间测量的基础上适当地计算重传超时周期的方法已被讨论了相当一段时间，例如在起始于1983的RfC 889中。关于TCP，目前使用的更新重传超时周期RTO的方法在RfC 2988中定义。依照此RfC，在响应时间或环回时间RTT的测量值的基础上的RTO的更新是：

Δ＝RTT-SRTT

SRTT←SRTT+1/8·Δ

RTTVAR←RTTVAR+·(|Δ|)-RTTVRR)

RTO＝max(SRTT+4·RTTVAR，1sec)。

SRTT表示环回时间RTT的平滑平均，而RTTVAR表示RTT的方差的指示。结果，RfC 2988的概念在于将重传超时周期更新或调整为响应时间的平滑平均和响应时间的方差的加权和，其中保持最小值1秒。

在RfC 2988中定义的概念有许多缺陷。可以理解的是，重传超时周期的值应该跟随响应时间的测量值。换句话说，如果RTT增加，那么RTO应该增加，而如果RTT下降，那么RTO应该下降。然而，对于上述更新RTO的方法，这不总是事实。如果发生突然的RTT下跌，那么在计算RTTVAR中使用Δ的绝对值的事实导致RTTVAR增加，它接着还最终导致RTO陡增。所以，尽管RTT已下降，RTO却增加了，这导致在数据单元的发送中的不必要延迟。

上述RfC 2988的概念中的另一个问题在于作为加权系数使用的所谓的“幻数”1/8和1/4。这些系数经过挑选并被最优化到每个RTT周期仅执行一个测量RTT(即一次仅测量一个RTT)的情形。然而，当例如通过利用时间戳为每个所发送的数据单元作RTT测量时，当未完成的数据单元的数量大时，或如果在连续的RTT样本之间没有重大变化，这些系数在更新RTO中得不到满意的结果。当在有限带宽的链路例如无线链路或调制解调器链路前保持长队列时，这种情形可以发生。

注意到，术语“未完成的数据单元”指被发送但仍没接收到反馈例如没有确认消息的数据单元。

在上述情况下，由RfC 2988提出的方程得出SRTT收敛于RTT的情形，Δ收敛到零，从而RTTVAR也收敛到零。结果，RTO的值收敛到RTT。这是不期望的，因为可以将RTT看作RTO的绝对最小值，既然不可能预期在比RTT更短的时间里接收到反馈消息。结果，上述RTO“暴跌”成RTT的现象导致大大提高伪重传的概率。

WO 01/13587 A2提出改进更新RTO的方法。这些方法例如在于使RTTVAR的计算取决于RTT的阈值条件、在于使加权系数是自适应的并另外使RTO的更新取决于伪重传的数量。

发明目的

本发明的目的是提供一种更新包括重传超时特征的数据单元发送器中超时周期的值的新的和改进的方法。

发明概要

权利要求1中所述的方法和权利要求24中所述的数据单元发送器解决了此目的。有利的实施例在从属权利要求中描述。

依照本发明，超时周期是由考虑响应时间的n个最近值的过程更新的，其中n是正整数。更新过程包括用于设置超时周期的新值的过程，包括依照预定的推导过程从响应时间的n个最近值推导中间值。中间值具有给出现在响应时间的指示的用途。同样，中间值可以是例如最近响应时间(n＝1)、响应时间的n个最近值的选择操作的结果、响应时间的n个最近值上平均操作的结果或者任何其他类型的生成给出现在响应时间的指示的值的函数或选择操作的结果。

依照本发明的更新过程，中间值依照预定的增加过程增加，并且超时周期的当前值依照超时周期缩减过程缩减。接着，将来自至少增加的中间值和超时周期的缩减的当前值中的最大量设置为超时周期的新值。

可见，本发明的概念是完全偏离由RfC 2988提出的概念。不是必须计算响应时间的平滑平均(尽管当确定中间值时这是可能的)，并且尤其是不再考虑计算响应时间的方差。相反，本发明的概念是关于RfC 2988概念的相当大的简化。本发明由此提供用于更新超时周期的机制，其在实验中表现了优良的性能，并且它能解决上面讨论的在RfC 2988中所提出的过程的问题。

更具体地说，由于用于增加中间值的过程，其中中间值给出现在响应时间的指示，所以保证超时周期的值并不“暴跌”成响应时间的值，因为增加过程在中间值和超时周期值之间提供了限定的距离。另一方面，用于缩减超时周期的当前值的缩减过程保证如果中间值下降(它指示响应时间在下降)，那么超时周期的新值也将下降。该下降或衰减的程度通过挑选的缩减过程来调节。

附图简短说明

将马上关于参考附图的某些第三实施例更详细地描述本发明，其中

图1示出本发明实施例的基本流程图，

图2是在网络上通信并且可以作为数据单元发送器执行本发明的许多通信设备的示意性表示，

图3是依照本发明实施例的数据单元发送器的示意性表示，以及

图4是示出在本发明实施例中响应时间和超时周期的特性的图。

详细说明

在下列例子的描述中，将参考从传输控制协议(TCP)得知的术语和表达，例如响应时间的重传超时周期或者RTO和指示在数据单元的发送和关于所述数据单元的反馈消息的接收之间经过的时间的环回时间或者RTT。这些术语和缩写是为了方便和简单而使用，因为本领域内的技术人员非常理解它们，而不是意图将本发明的概念的应用局限于TCP或者任何其他特定的通信协议。同样，上面提及的表达和缩写作一般的使用。即，本发明用于更新超时周期的概念可以用于任何提供重传超时特征的协议，例如SCTP(流控制传输协议)。

图1示出本发明基本实施例的流程图。在步骤S1，依照预定的推导过程从RTT的n个最近值导出中间值IV。在步骤S2，中间值依照预定的增加过程增加，而在步骤S3，RTO的现在值依照预定的RTO缩减过程缩减。在步骤S4，选择IV和缩减的RTO的最大量，并且在步骤S5中设为RTO的新值RTOnew。

这还可以以紧凑的形式表示为伪码：

RTO＝max(Aug(Der(RTT_i))，Red(RTO))             (1)

Red表示缩减过程，例如用于计算RTO的缩减值的函数或者例程，这样Red(RTO)＜RTO。Der(RTT_i)表示用于从RTT的n个最近值推导中间值的例程，这样IV＝Der(RTT_i)，其中i＝1，…，n。Aug(IV)表示增加过程，例如用于增加IV值的函数或例程，这样Aug(IV)＞IV。max表示从这些指出的项中选择最大量的操作。

可以注意到，超时周期RTO的总更新可以涉及另外的过程，并且可以涉及比项Aug和Red更多的。即，可以想到，在最大量选择函数max中考虑另外的控制系数，并且RTO的新值的最后确定涉及另外的步骤也是可能的，例如

RTO＝max(RTO，max(RTT_prev，RTT)+2·tick)      (2)，

在方程(2)中，RTT表示响应时间RTT的当前值，RTT_prev表示RTT的紧接地前一个值，而tick表示基础定时器的基本粒度，即增量，系统定时器依照这些增量增长时间计数。方程(2)在方程(1)之后执行，即，在方程(2)的右手边上指出的值RTO是在方程(1)中左手边上计算的值。

上述基本方法可以在能够当作数据单元发送器并使用重传超时特征的任何设备中体现。图2示出在网络10中安排的通信设备的示意性表示，其中设备21、22、23、24称为终端，而设备25、26、26、27、28、29称为网络中可以当作路由器或者其他类型的服务器的设备。这些设备21-29中的每一个都可以当作数据单元发送器并从而实现本发明的概念。

图3示出可以当作数据单元发送器并且实现本发明概念的通信设备的示意性表示。数据单元发送器3包括用于保存数据的缓冲器31、被安排例如在图2中示出的网络10上来发送数据单元和接收数据单元的发送/接收部分32和能够执行用于控制数据单元的发送和接收的程序的处理器33。38表示由发送器3发送的数据单元，而39表示从通信的接收器(未示出)接收的反馈消息。

示出的处理器33具有实现重传机制的重传元件331，依照该重传机制数据单元发送器3依靠反馈消息重传数据单元。332表示用于实现重复确定响应时间值的响应时间确定机制的响应时间确定元件。最后，333表示被安排来实施用于设置超时周期的新值的值设置过程的值设置元件。在图3的例子中，元件331-333是由处理器33执行的软件元件。软件元件是计算机程序、计算机程序的一部分或者能够执行相应过程的例程。这样，值设置元件333包括用于推导中间值的子元件、用于实施增加过程的子元件、用于实施超时周期缩减过程的子元件、用于选择最大量的子元件及用于将超时周期的新值设置为最大值的子元件。

尽管首选的是用于实施上述过程和将在下文描述的过程的元件是软件元件，但是以任何期望的方式即通过软件、通过硬件或者通过任何适合的硬件和软件的结合来提供这些元件基本上是可能的。由于以软件的形式提供本发明的方法的可能性，可以以包括当在数据单元发送器上执行时能够进行此方法的计算机程序的计算机程序产品的形式来体现本发明。这种计算机程序产品可以是例如数据载体，程序存储在该数据载体上。

用于在RTT的n个最近值的基础上获得中间值的推导步骤的目的是提供给出现在RTT的指示的值。在最简单的情形下，这可以是RTT的最近值，此情形中n＝1。作为选择，为了避免RTT测量中奇异效应的影响，使用响应时间的两个最近值也是可能的，并例如将中间值IV设置为这两个的平均值，或者挑选这两个最近RTT测量的最大量。

通常，当考虑n个最近RTT测量时，为了生成中间值将这些值平均是可能的，或者依照预定的选择标准在所述n个最近RTT值上执行选择操作是可能的，并且接着将所选值设置为中间值。优选地，选择标准是最大值，这样从RTT的n个最近值中选择最大量。

为了保留本发明解决方案的简单性，期望不将n选得太大。同样，值n＝2提供了巨大的简单性，但是同时已经避免RTT测量中的奇异效应(如一个样本的RTT突然的和短暂的下跌)负面地影响RTO更新过程。

为了缩减RTO，可以将缩减过程Red(RTO)以任何合适的或者期望的方式来安排，例如通过从RTO减去恒定的减量值。优选地，缩减过程Red(RTO)包括缩减RTO值到预定的衰减分数，所述衰减分数分布在0与1之间的范围中。缩减到预定的分数可以例如通过乘以值在0与1之间的范围中的适当的系数来进行。

基本上，可以以任何适合的或期望的方式来选择衰减分数，并且可以例如是常数。该常数可以依照要多么积极或保守的缩减RTO值的首选项来调节。即，分数的大值意思是缩减是小的(保守的)，反之分数的小值意思是缩减显著(积极的)。例子是值0.75。

还可以在参与控制发送数据单元的其他控制参数的基础上选择常数。例如，衰减分数可以取决于在与给定的接收器通信中每个响应时间间隔所作的响应时间测量的数量。如果数据单元发送器以一次仅实施一个RTT测量的这种方式来安排，即数据单元发送器在开始下一次RTT测量前等待RTT测量的完成，那么每个响应时间间隔的响应时间测量的这个数量是1。另一方面，如果例如利用时间戳选项为每个发送的数据单元测量RTT，那么每个RTT所进行的RTT测量的数量等于未完成的数据单元的数量(有时也称“在飞行中”的数据单元的数量)，其中未完成的数据单元是被发送但其反馈消息还没有被接收的这样的数据单元。

衰减分数对每个RTT的RTT测量的数量的相关优选地是这样，如果该数量大，则分数比如果数量小时更接近1。达到这种相关的一种方式是例如按下式计算分数：

$>>FRAC>=>1>->>1>>x>·>Samples\; PerRTT>\; >->->->>(>3>)>>>s>$

在方程(3)中x是乘法系数，可以是常数或者自适应的参数(这将在下文更详细地解释)，而SamplesPerRTT表示每个RTT的RTT测量的数量。

在方程(3)的基础上，缩减过程Red(RTO)可以例如安排为

Red(RTO)＝FRAC·RTO                        (4)

如上面指出的，衰减分数可以是常数，又可以取决于另外的参数。然而，衰减分数自身也可以是自适应的。在这种情形下，提供衰减分数更新过程，它优选地依靠在与给定的数据单元接收器通信中伪重传的数据单元的数量来操作。如前面所提到的，如果例如沿着发送器和接收器之间的通信有过多的延迟，则伪重传发生，这样引起超时的数据单元实际上没有丢失，并且要是RTO更长，超时不会发生。

更新过程优选地以这种方式来安排，如果伪重传的数量增加，则它增加衰减分数(使它更接近1)，并且如果伪重传的数量下降则缩减衰减分数(使它更接近0)。

更优选地，衰减分数的更新过程包括监视在发送器和接收器之间的通信中给定的时间范围内伪重传的数据单元的数量和所发送的数据单元的总数的比率。换句话说，更新过程优选地取决于伪重传的相对数量。更新操作可以然后包括提供第一或低阈值和第二或高阈值，所述第二阈值比所述第一阈值高，以及如果所测量的比率位于低阈值以下则降低衰减分数(即，使它更接近0并从而使RTO中的缩减更积极)，或者如果所测量比率超过高阈值则使衰减分数更大(即，使它更接近1，从而使RTO中的缩减更保守)。

伪重传的检测可以以任何适合的或期望的方式完成，例如如EP-A-1 018 821或WO 01/13587 A2中所述，它们都通过引用结合在此。

基本上，通过在由于超时重传给定的数据单元后确定所接收的反馈消息不是响应重传的数据单元而是响应引起超时的数据单元来识别伪超时。

确定伪超时的一种方法可以是使发送器保持与发送器和接收器之间(更具体地说在发送同位体和接收同位体之间)通信关联的RTT的记录，而且尤其是使发送器保持在通信(或者会话)过程中发现的最短的RTT的记录直到考虑中的时间点。于是，如果重传数据单元的反馈消息在比最短RTT预定的百分比更小的超时周期内接收，则发送器确定该反馈属于原始传输而不是重传。该百分比可以设置为固定的值或者它自身可以是自适应的参数。自然地，乘以所述百分比的比较值是测量的最短RTT是不必要的，但是发送器保持平均RTT值例如在介绍中讨论的SRTT值也是可能的，并且该平均值用作确定伪重传的基础。在此意义上，乘以百分比的比较值通常是一个或多个在通信过程中测量的RTT值的函数。

确定伪重传的另一可能性是使发送器添加标记给它发送的数据单元，其中所述标记以它允许区别原始传输和重传的这种方式来定义。接着，接收器可以相应标记反馈消息，从而发送器能够识别反馈消息指的是原始传输还是重传。数据单元的这种标记可以以任何期望的方式完成。例如，在发送的数据单元中仅仅指定单比特是可能的，其中一个比特值指出原始传输而另一个比特值指出重传。另一种可能的标记是可以传送更多信息的比特流。还有一种可能性是使用所谓的时间戳选项，它是例如由于TCP而知名。换句话说，在所发送的数据单元中包括时间戳是可能的，它指出什么时候发送了数据单元。于是接收器可以在反馈消息中仅仅包括相同的时间戳，从而发送器有唯一的识别反馈消息所指的数据单元的方式。

上述衰减分数的更新可以是例如通过相应地更新在方程(3)中示出的x值来达到。更具体地说，基于上述伪重传的数据单元与所发送的数据单元的比率和低阈值及高阈值，如果比率超过高阈值则x可以增加，而如果比率变得比低阈值更小则x可以降低。

低和高阈值可以以任何合适的或者期望的方式选择，其中高阈值可以是例如1％而低阈值为0.5％。x的合适的起始值可以在2到20的范围中。使x更大或更小的操作可以通过利用适当的预定的增量或减量来实现，优选地具有相同的值。

类似于推导过程和超时周期缩减过程，可以以任何适合的或期望的方式挑选增加过程。例如，增加IV使得Aug(IV)＞IV可以通过给IV增加预定的增量来完成。优选地，增加过程包括以值大于1的预定的增加系数乘以中间值。换句话说，增加过程可以按如下进行：

Aug(IV)＝y·IV；y＞1                        (5)

其中y可以是常数，或者可以是自适应的参数。y优选地位于1与2之间的范围中，例如y＝1.5。

如果使增加系数y是可适应的，则提供了增加系数更新过程，它优选地考虑RTT的k个最近值，k是正整数。k可以有和n相同的值，但是也可以挑选得更大或更小。

于是增加系数更新过程可以包括：

推导指示RTT的k个最近值的变化的变化指示参数的新值，依照预定的增加变量缩减过程缩减增加变量的当前值，从所述变化指示参数的所述新值和所述缩减的增加变量中确定最大量，将所述增加变量的新值设置为所述最大量，并且在所述新的增加变量的基础上设置所述增加系数的新值。

通过下列方程(6-8)给出关于此的一个例子：

N_AMP＝(RTT-RTTprev)/RTTprev                (6)

Booster＝max(N_AMP，Red^*(Booster))         (7)

y＝f(Booster)                               (8)

N_AMP表示变化指示参数，在方程(6)的例子中它是RTT的两个最近值即当前响应时间RTT和紧接地前一个响应时间RTTprev之间的相对差。然而，可以注意到，这仅是一个例子，而变化指示参数的其他定义是可能的。

在如方程(6)中指出的确定N_AMP的新值之后，将如此计算的N_AMP的值与增加变量Booster的缩减的当前值比较。在方程(7)中，该值的最大量被设置为增加变量Booster的新值，而方程(8)表示将系数y确定为如此确定的变量Booster的函数。

可以以任何适合的或者期望的方式挑选缩减过程Red^*，从而Red^*(Booster)＜Booster。优选地，Red^*与Red相同，这样

Red^*(Booster)＝FRAC·Booster                (9)

当变化指示参数是响应时间的两个最近值之间的相对差时，y优选地如下确定

y＝1+Booster                                (10)

依照上面的概念，增加系数更新过程依照与RTO的更新过程类似的原理来操作。即，要么将变量Booster设置为与RTT的瞬间变化相等，要么如果缩减的版本比RTT的瞬间变化大则将变量Booster设置为与Booster的前一个值缩减的或衰减的版本相等。从而，如果RTT突然增加，那么Booster并且因此y将跟随，反之如果RTT的变化变小(例如许多RTT测量产生相同的值)，Booster并且因此y将依照缩减过程Red^*衰减。

当使用RTT的这两个最近值之间的相对差时，出现了如何设置此参数N_AMP的初始值的问题，即当只有一个RTT测量可用就是第一或初始测量时。由于第一RTT测量在初始同步的基础上完成，有时它也称作SYN RTT。

当数据单元发送器开始与新的接收器新的通信时要使用的该相对差的初始值可以设置为常数，例如使得N_AMP的初始值是例如1.5或2。

优选地，在与多个其他的数据单元接收器通信中伪发送的初始数据单元的基础上，提供用于使相对差的初始值适应用于新的通信的初始值适应过程。

换句话说，在图2中示出的数据单元发送器(例如设备21-29中的一个)监视它正与之通信的所有不同的数据单元接收器的通信。数据单元发送器接着测量在发送的初始或第一数据单元上发生的伪重传的数量。优选地，数据单元发送器监视预定的时间周期内所有有效通信上伪重传的初始数据单元的数量与所述预定的时间周期内所有有效通信数量的比率，即初始数据单元上的伪重传的相对数量。接着可以通过将所测量比率与低阈值比较而如果比率位于低阈值以下则使初始值更小，以及将此比率与比低阈值更大的高阈值比较而如果比率超过该高阈值则使初始值更大来实施初始值适应过程。使初始值更大或更小的操作可以通过利用适当的预定的增量或减量-优选地具有相同的值-来实现。

这种用于更新连续的RTT测量之间的相对差的初始值的自适应过程的好处对于仅有小数量的数据单元要发送的通信是尤其显著的。在这种情形下，错误设置的相对差的初始值将导致错误设置y的初始值，又不能通过更新y的过程适当地校正它，因为提供更新信息或者更新机会的数据单元太少。

图4示出关于系统定时器的值的RTO值(三角形符号)和RTT值(菱形符号)的图，其中RTO更新如下：

RTO＝max(FRAC·RTO，y·RTT)                (11)

在方程(11)中FRAC依照方程(3)确定，将x设置成常数值4，而将y设置成常数值1.5。清楚注意到，RTO正确跟随RTT的方向而并不暴跌成RTT。

上述详细的实施例用于为那些技术人员提供对本发明的更全面的理解，但是意图不是限制。更确切地，保护的范围由所附权利要求限定。在权利要求中的引用记号只是用于使权利要求更容易阅读而意图不是限制。