监视传输中分组以优化网络中的分组流量的系统和方法

摘要

公开了优化网络中的分组流的系统和方法。互联网络包含多个网络，每个网络具有多个非路由器节点及至少一个路由器节点。第一网络的非路由器节点可以被配置成执行拥塞控制。非路由器节点发送请求分组至第二网络中的节点。当该请求分组被发送到该第二网络节点时且当从该第二网络节点接收到响应分组时，与该网络相关联的传输中分组计数器的数值被调整。该非路由器节点基于该传输中分组计数器的数值来确定另一请求分组是否能被发送到该互联网络中的另一网络。

说明书

技术领域

所公开的系统和方法通常涉及在计算机网络或互联网络 (internetwork)中节点之间的通信与数据交换，尤其涉及基于因特网协 议的网络和互联网络。各示例性实施例特别针对的是计算机节点之间 的有效且经济的数据传输。

背景技术

互联网络是使用公共的路由技术连接的不同计算机网络的集合。 “因特网”是这种互联网络的例子，其中不同网络中节点之间的通信 受到诸如因特网协议(IP)组的互联网络协议标准的帮助。

适当的名词“因特网”(Internet或INTERNET)指的是使用因 特网协议组来交换数据的互联分组交换网络的一种全球公开接入系 统。

不是“因特网”但使用该因特网协议组的互联网络有时被不同地 称为“互联网”、“IP互联网络”、“私有互联网”、“私有IP互 联网络”或“私有IP网络”。也就是说，尽管由于其全球且公开可接 入本质而非常普及，但是“因特网”仅为基于IP的互联网络的一个例 子。

如一般在IP网络中所知，为了使IP互联网络中的一节点发送数 据到该IP互联网络中的另一节点，该数据必须被封装于IP分组中。

图1A是与现有技术一致的计算机网络的方块图。如图1A中所 示，节点1、节点2、节点3和节点4都被连接至计算机网络10。对 于在网络之间发生的数据交换来说，必须形成互联网络。互联网络的 形成取决于被特别地称为“路由器”的某些节点的使用。

图1B是与现有技术一致的互联网络的方块图。如图1B中所示， 互联网络20包含网络A、网络B、网络C、及网络D。该些网络中每 一个都包含以一圆圈区分开来的特定节点。特定节点节点A、节点B、 节点C、及节点D是路由器，并且此后将其分别指定为路由器A、路 由器B、路由器C、及路由器D。

在一个例子中，如果网络C的节点C3发送一分组至网络A的节 点A1，则该分组必须先被发送到网络C的路由器C。路由器C接着 发送该分组至网络B的路由器B。从路由器B将该分组发送到网络路 由器A的路由器A，其将该分组递送至网络A的节点A1。对于在网 络之间如何将一分组自一个节点路由至另一节点的命名经常被称为节 点之间的“路径”。路径是路由器的有序列表，并且一路径的每个元 素被不同地称为“中间节点”、“中介节点”、或更简单地称为“跳 跃”。

例如：从节点C3至节点A1的路径能被指定为P＝(C，B，A)， 其中路由器C、B、及A全都是有序列表P中的跳跃或中间节点。

节点或路由器之间的路径能以动态或静态的方式形成。诸如路由 信息协议(RIP)、边界网关协议(BGP)、及开放最短路径优先(OSPF) 之类的通信协议是IP互联网络中所使用的动态互联网络协议的例子。

拥塞控制在概念上被说明为：以最大化通信节点之间的理想吞吐 量且同时避免拥塞崩溃为目标来控制分组进入给定网络的流入流量的 速率。拥塞崩溃是其中存在因为拥塞而发生的很少或无用的通信的情 形。

在诸如IP互联网络的分组交换互联网络中存在两种能够实现拥 塞控制的普遍方法：

1.路由器丢弃分组。互联网络中的路由器通过丢弃由节点所发 送的分组，否则这些分组将导致超过两个路由器之间的最大分组或数 据速率，来执行拥塞控制。这种例子能在Sally Floyd及Van Jacobson 的论文“Random Early Detection(RED)Gateways For Congestion  Avoidance(拥塞避免之随机早期侦测(RED)网关器)”所述的方 法中找到。

2.非路由器节点执行端到端拥塞控制。节点可使用类似传输控 制协议(TCP)的拥塞避免的拥塞避免算法，其在IP互联网络中的两 个非路由器节点之间执行拥塞控制。TCP拥塞避免具有多个变型，包 括如下变型：TCP Reno、TCP Tahoe、及TCP Vegas。Kevin Fall及 Sally Floyd的论文“Simulation-based Comparisons of Tahoe，Reno  and SACK TCP(Tahoe、Reno及SACK TCP的模拟式比较)”作为 Van Jacobson的“Congestion Avoidance and Control(拥塞避免和控 制)”的有用参考文献。

类似于上文所述的“路由器丢弃分组”方法的方法是非端到端拥 塞控制模型。Sally Floyd和Van Jacobson的“RED Gateways For  Congestion Avoidance(用于拥塞避免的RED网关)”描述了一种由 路径的路由器和中介跳跃丢弃分组以强化最大链路容量的方法。

类似于TCP拥塞避免同时是端到端的方法不将互联网络路径的 中介跳跃(路由器)看作为拥塞点。在该TCP拥塞避免技术中，关于 是否发送一分组的决定是基于端点的孤立的通信成功率。

发明内容

本文所述的多个示例性实施例通过考虑中介节点的分摊 (amortized)的成功及失败率来优化在网络上的两个端点之间的分组流 量。这种拥塞控制方法不同于其它拥塞控制方法，并且提供了端到端 拥塞控制，其在确定是否要发送一分组时使用网络的路由器的最大容 量作为主要考虑。

公开了一种在具有多个网络的互联网络中进行拥塞控制的示例 性方法。所述方法包括：将请求分组发送到第二网络中的节点；在请 求分组被发送到该第二网络的节点时或是否从该第二网络的节点接收 到响应分组，对传输中分组计数器的数值进行调整；以及基于该传输 中分组计数器的数值来确定是否能发送另一请求分组。

另一示例性方法涉及在具有多个网络的互联网络的第一网络中 的节点处进行的拥塞控制。所述方法包括：将来自第一网络中的节点 的第一请求分组发送到第二网络中的节点；减小所述第一网络节点的 传输中分组计数器；和启动所述第一网络节点的定时器。所述方法还 包括：在从所述第二网络节点接收到响应分组或所述定时器的期满时 间被超过时，增大所述第一网络节点的传输中分组计数器；以及基于 所述传输中分组计数器的数值来确定是否能从所述第一网络节点发送 第二请求分组。

以程序编码一种示例性计算机可读介质，所述程序用于在具有多 个网络的互联网络中的第一网络的基于处理器的节点处执行拥塞控 制。所述计算机可读介质包括：第一模块，将请求分组发送到第二网 络中的节点；第二模块，基于所述请求分组被发送到所述第二网络的 节点、从所述第二网络的节点接收到响应分组和与所述请求分组相关 联的定时器的期满时间中的一个，对传输中分组计数器的数值进行调 整；以及第三模块，基于所述传输中分组计数器的数值来确定是否能 发送另一请求分组。

示例性方法涉及在具有多个网络的互联网络中进行的拥塞控制。 所述方法系包括：在所述多个网络中的第一网络的多个节点中，建立 分别与所述多个网络中的其它网络相关联的多个分组队列和传输中分 组计数器。对于将要从所述第一网络中的节点发送到所述其它网络的 给定网络中的节点的请求分组，所述方法还包括：以至少一个请求分 组加载与所述给定网络队列相关联的分组，其中所述至少一个请求分 组的目的地为所述互联网络的所述给定网络中的节点；将所述至少一 个请求分组发送到所述给定网络中的所述节点；在所述请求分组被发 送到所述给定网络中的所述节点时在一个方向上调整与所述给定网络 相关联的传输中分组计数器的数值，并且在从所述给定网络中的所述 节点接收到响应分组时，在另一方向上调整所述传输中分组计数器； 以及基于所述传输中分组计数器的数值来确定是否能将另一请求分组 发送到所述给定网络中的所述节点。

附图说明

在下面参考附图详细描述本发明的示例性实施例，在附图中：

图1A是根据现有技术的计算机网络的方块图；

图1B是根据现有技术的互联网络的方块图；

图2A是根据示例性实施例的互联网络的示意图；

图2B及2C是根据示例性实施例的拥塞控制方法的流程图；

图3是根据示例性实施例的互联网络的示意图；

图4A至4D是每一个网络队列在根据示例性实施例的拥塞控制 处理期间的示意图；以及

图5是根据示例性实施例的公用设施监视和控制网络的示意图。

具体实施方式

图2A是根据示例性实施例的互联网络的示意图。如图2A中所 示，分组交换互联网络200包含分组交换网络A到D。每一个分组交 换网络都包含多个非路由器节点及至少一个路由器节点。例如，网络 A包含多个非路由器节点A₁至A_N及路由器A_R，网络B包含多个非 路由器节点B₁至B_N及路由器B_R，网络C包含多个非路由器节点C₁至C_N及路由器C_R，而网络D包含多个非路由器节点D₁至D_N及路由 器D_R。在此后，将参照示例性网络X和Y(未图示)描述互联网络 200中分组交换网络的共同特征。

在示例性实施例中，IP互联网络中的非路由器节点能被配置成发 送分组至互联网络200中的其它非路由器节点。在该互联网络上发送 这些分组的节点在此后被称为“发送节点”。意欲在该互联网络上接 收分组的节点在此后被称为“接收节点”。具体而言，该示例性实施 例针对其中在分组交换互联网络的给定分组交换网络中的发送节点将 分组发送到相同互联网络中的不同网络的接收节点的情况。

例如，网络A中的节点A2(发送节点)能被配置成发送分组至 网络B上的接收节点节点B1、节点B2、节点B3、和节点B4；网络 C上的节点C1、节点C2、节点C3、和节点C4；及网络D上的节点 D1、节点D2、节点D3、和节点D4。

通常真实的是不论发送节点何时将分组发送到接收节点，该发送 节点在发送了原始分组之后的某一时间量内期望获得作为响应于所发 送的原始分组的确认的分组。该确认分组可仅含有确认或可含有响应 数据(其暗示了确认)。源自发送节点的分组将被称为请求分组，而 由接收节点所发送的分组将被称为响应分组。

普通技术人员将理解：对于任何互联网络来说，一个网络至任一 其它网络之间的路径具有最大(可能是变化的)延迟和数据吞吐率。 示例性实施例提供了一种用于端到端拥塞控制的方法，其在确定是否 要发送分组时使用网络的路由器的最大容量作为主要考虑。

在网络X处，在互联网络中诸如网络Y(未示出)的每一个其它 分组交换网络都具有相关的分组队列。例如，队列Y指定从网络X中 的节点要发送到网络Y中的接收节点的请求分组的队列。该分组队列 的实施方式被显示于图2A中。例如，网络A能包含队列B、队列C 和队列D。同样尽管没有显示，网络B能包含队列A、队列C和队列 D；网络C能包含队列A、队列B和队列D；及网络D能包含队列A、 队列B和队列C。

超时数值Timeout与发送节点发送到接收节点的每一个请求分 组相关联。普通技术人员将理解：Timeout的数值对于每一个请求分 组不必都是相同的，且事实上可能对于由该发送节点所发送的每一个 请求分组是不同的。数值Timeout表示发送节点在宣告请求分组或响 应分组丢失之前等待从接收节点接收响应分组的以秒为单位(可能为 分数)的最大时间。

可以在该互联网络中的一个网络处为互联网络200中的每一个其 它网络定义最大可允许的传输中分组计数器。例如，对于网络X，针 对网络Y的传输中分组计数器能被指定为PIF-INITIAL-Y。针对网络 Y的计数器PIF-INITIAL-Y能被指派大于0的初始整数值。而且，网 络X处的每一个PIF-INITIAL的初始值对于每一个网络可以是不同 的。PIF-INITIAL数值表示可能被发送到给定网络的未被确认的请求 分组的最大数目。传输中分组计数器的示例性实施方式被显示于图2A 中。例如，对于网络A，PIF-INITIAL-B与网络B相关联， PIF-INITIAL-C与网络C相关联，而PIF-INITIAL-D与网络D相关 联。

未被确认的请求分组是发送节点还未收到响应分组或还未超过 期满时间的请求分组。期满时间能如下定义：

期满时间＝当前时间+Timeout

在互联网络中的一个网络处为该互联网络中的每一个其它网络 定义多个目前未被确认的传输中分组计数器。对于示例性网络X来说， 针对网络Y的目前未被确认的传输中分组计数器能被指定为 PIF-UNACKED-Y。该PIF-UNACKED-Y数值能为具有初始值0的整 数值。PIF-UNACKED数值表示已被发送到给定网络的未被确认的请 求分组的当前数目。如先前所定义的那样，未被确认的请求分组是发 送节点还未收到响应分组或还未超过期满时间的请求分组。目前未被 确认的传输中分组计数器的示例性实施方式被显示于图2A中。例如， 对于网络A，PIF-UNACKED-B与网络B相关联，PIF-UNACKED-C 与网络C相关联，而PIF-UNACKED-D与网络D相关联。

图2B及2C是根据示例性实施例的拥塞控制方法的流程图。

如图2B中所示，如果符合两个提件，则发送节点能发送请求分 组至接收节点。第一，对于网络X，与网络Y中的接收节点相关联的 分组队列队列Y必须为非空(S200)。第二，与网络Y相关联的 PIF-UNACKED-Y数值必须小于也与网络Y相关联的 PIF-INITIAL-Y(S202)。如果符合这两个条件，则分组从网络X中 的队列Y中移出且被发送到网络Y的接收节点(S204)。 PIF-UNACKED-Y的数值被增大且所发送的请求分组的期满时间被 设定为：期满时间＝当前时间+Timeout(步骤S206)。另一方面， 如果PIF-UNACKED-Y的数值等于PIF-INITIAL-Y，则网络X中的 发送节点在此时不进行任何动作。

如图2C中所示，如果在网络X处收到来自网络Y中的接收节点 的响应分组，则计数器PIF-UNACKED-Y被减小(S208)。另一方面， 如果在网络X处未收到来自网络Y中的接收节点的响应分组，则发送 节点确定是否超出期满时间(S208)。如果已经超出了发送到网络Y 中的接收节点的请求分组的期满时间，则计数器PIF-UNACKED-Y被 减小(S210)。每当用于任何给定网络Y的计数器PIF-INITIAL-Y 的数值大于0时，则对于网络X中的发送节点来说，可以针对网络Y 中的接收节点重复进行步骤S200。

在替代性实施例中，不同于在发送分组至接收节点时增大计数器 和在从接收节点收到分组或已经超过期满时间时减小计数器，该系统 能被配置成在发送分组时减小计数器和在收到分组或已经超过期满时 间时增大计数器。例如，在示例性网络X中，计数器PIF-UNACKED-Y 能被计数器PIF-REMAINING-Y取代，其中计数器 PIF-REMAINING-Y表示针对网络Y，网络X中的可允许的剩余传输 中分组。在这种情况下，PIF-REMAINING-Y的初始数值被设定为 PIF-INITIAL-Y。只要PIF-REMAINING-Y大于0，则来自队列Y的 分组可被发送到网络Y。当发送分组时，PIF-REMAINING-Y被减小 1。当收到来自网络Y的响应分组或超过期满时间时，则 PIF-RE MAINING-Y被增大。

图3是根据示例性实施例的互联网络的示意图。

如图3中所示，互联网络300包含被指定为网络A、网络B、网 络C及网络D的多个网络。每一个网络包括多个节点。该多个节点及 其与相应网络的成员关系能如下定义：

·网络A包含节点A1、A2、A3、A4；

·网络B包含节点B1、B2、B3、B4；

·网络C包含节点C1、C2、C3、C4；及

·网络D包含节点D1、D2、D3、D4。

普通技术人员将理解：根据需要，互联网络300可具有任何数目 的网络且每一个网络可具有任何数目的多个节点。网络的数目及每个 网络的节点的数目能随着实施方式而改变。

在基于互联网络300的示例性实施方式中，节点A1能发送请求 分组至节点B1、B2、B3、B4、C1、C2、C3、C4、D1、D2、D3、D4 中的每一个。为了区别一个分组与另一个分组，目的地为这些节点中 的每一个的请求分组能够被标注以标记RP:RECEIVING-NODE。例 如，目的地为接收节点B1的请求分组被标记为RP:B1，而目的地为 接收节点C2的请求分组被标记为RP:C2，且依此类推。

目的地为节点B1至B4、C1至C4和D1至D4的请求分组中的 每一个能被列举如下：

RP:B1、RP:B2、RP:B3、RP:B4、RP:C1、RP:C2、RP:C3、RP:C4、 RP:D1、RP:D2、RP:D3及RP:D4。

每一个请求分组具有以秒为单位的相关期满时间或超时数值T。 请求分组的超时数值不必全部都相同，根据需要，每一个请求分组可 以具有特有的超时数值。

可以基于接收节点所对应的目的地网络组织请求分组。也就是， 对于网络A来说，能为网络B、C和D中的每一个建立一队列，其中 如果与请求分组相关联的节点是与队列相关联的网络的成员，则该请 求分组是该队列的成员。而且，对于这些队列中的每一队列，初始的 传输中分组(PIF-INITIAL)变量能被设定为某一初始数值，且这些 队列中的每一队列的未被确认的传输中分组(PIF-UNACKED)变量 能被设定为0。

在以下讨论中，将在互联网络300的一实施方式的上下文中描述 如图2B及2C中所示的拥塞控制方法。

如果每一网络队列都为非空且每一队列的PIF-INITIAL的数值 都被初始化，则节点A1能发送请求分组至节点B1至B4、C1至C4、 和D1至D4中的任一个(S200)。

图4A说明了在完成S200之后每一队列的示例性状态。如图4A 中所示，以相应的请求分组加载每一队列，且每一队列的初始PIF数 值被初始化为PIF-INITIAL-B＝3、PIF-INITIAL-C＝1、 PIF-INITIAL-D＝2。

如果一队列的PIF-UNACKED数值小于相应的PIF-INITIAL数 值(S202、S204)，则请求分组可以从该队列中被移出且被发送到指 定的接收节点。同时，PIF-UNACKED数值被增大1(S206)。另一 方面，如果该队列的PIF-UNACKED数值不小于该队列的相应的 PIF-INITIAL数值，则处理回到步骤S200以确定该队列是否为非空。

可以针对每一队列重复进行步骤S200至S206，直到 PIF-UNACKED数值等于PIF-INITIAL数值。

图4B说明网络A的队列队列B、队列C和队列D在完成步骤 S206之后且在PIF-UNACKED等于PIF-INITIAL数值时的示例性状 态。

比较图4A及4B，普通技术人员将理解：分组已经从其相应的队 列中被移出，并且基于如下所示的与每个相应分组相关联的队列和网 络，将所述分组发送到指定的接收节点：

·网络B、队列B：RP:B4、RP:B3、RP:B2

·网络C、队列C：RP:C3

·网络D、队列D：RP:D4、RP:D1

每当网络的PIF-UNACKED数值小于该网络的PIF-INITIAL数 值时，则与该网络相关联的队列中的分组能被移出。一旦从该队列中 被移出，分组被发送到所指定的接收节点，且计数器PIF-UNACKED 的数值被更新以反映未被确认的分组的数目。在没有收到来自接收节 点的响应或还未超过该分组的期满时间时，分组未被确认。

再次回到图2C的拥塞控制方法，如果超过了所发送分组的期满 时间，则该分组被宣告丢失。可替代地，如果收到相应的响应分组， 则分组通信是成功的(S208)。在任一情况下，用于该网络的计数器 PIF-UNACKED的数值被减小1(S210)。

例如，如果RP:C3被宣告成功或丢失，则PIF-UNACKED-C的 数值被减小1，使得PIF-UNACKED-C＝0。

图4C是反映网络A中的每一队列在完成步骤S208之后的示例 性状态的示意图。

如图4C中所示，PIF-UNACKED-C＝0，其小于 PIF-INITIAL-C＝1。因此，队列C中的下一个分组被移出(RP:C1) 且被发送到接收节点C1。PIF-UNACKED-C的数值被增大1，使得 PIF-UNACKED-C＝1。

图4D是说明每一队列在完成步骤S210之后的示例性状态的示 意图。如图4D中所示，RP:C1已被移出队列C且 PIF-UNACKED-C＝1。

普通技术人员将理解：要发送的请求分组的设定不必是固定的。 例如，如果在运行在发送节点上的应用程序的存活期间有额外分组要 被发送到另一节点，则请求分组能被加载到与适当网络相关联的适当 队列内。

图2B及2C中所示的算法可以由发送节点处的处理器执行，使 得该发送节点能基于每个网络来执行拥塞控制。

示例性实施例能以各种不同类型的通信系统来实施。一个说明性 例子是公用设施监视和控制网络。图5是根据示例性实施例的公用设 施监视和控制网络的示意图。该公用设施监视和控制网络能基于图3 的示例性互联网络实施方式进行配置。该示例性公用设施监视和控制 网络能具有以下节点和网络定义：

·网络A能被指定为公用设施的后端支持网络(back office  network)。

·路由器A能被指定为后端支持虚拟私有网络(VPN)集中器。

·路由器B、路由器C和路由器D能被指定为无线接入点，且 此后分别被称为接入点B、接入点C和接入点D；或AP-B、AP-C和 AP-D。

·网络B、网络C和网络D能被指定为无线网格网络。

·AP-B、AP-C和AP-D之间的互联链路能为广域网(WAN)链 路。WAN链路的本质能为多种类型中的一种，所述多种类型包括： 以太网、码分多址(CDMA)、通用分组无线电业务(GPRS)、演 进数据优化(EVDO)、宽带码分多址(WCDMA)、或根据需要为 任何其它合适的WAN链路。

·节点B1至B4、C1至C4和D1至D4中的每一个都能被指定 为无线网格网络中的节点。

·节点B1至B4、C1至C4和D1至D4中的每一个都能经由串 行线被连接至公用设施计量装置。该公用设施计量装置能被指定为住 宅或商用或工业用的各种电表、气表、和水表，或根据需要为任何其 它合适的计量装置。

·节点B1至B4、C1至C4和D1至D4中的每一个的处理器能 通过软件被配置为基于图2B及2C中所示的拥塞控制算法来发送查询 和命令至所连接的公用设施计量装置和发送这些查询的结果和命令至 该互联网络中的其它节点。

上文所述的示例性系统和方法提供了优于传统拥塞控制和/或避 免技术的数个优势。特别是，在另一方面，如本文中所述的用于监视 网络中的传输中分组的示例性系统和方法并非由路由器而是由非路由 器发送节点所实施。而且，上述系统和方法将发送分组至网络的确定 基于该网络的路由器的总体容量，而非该网络的单一节点的孤立容量。

本文中所述的系统和方法能通过经编码、记录、或储存在计算机 可读介质上的软件代码来实施。该计算机可读介质能用于配置每一个 发送节点中，所述发送节点如上文所述被连接至互联网络。普通技术 人员将理解：该计算机可读介质能包含光盘、磁盘、闪存、磁带、或 根据需要是任何有形储存装置或介质。

普通技术人员将理解：本文中所述的拥塞控制系统和方法能适应 任意数量的网络和互联网络、任意数量的请求分组、和每一网络中的 任意数量的节点。

尽管已经参考具体实施例描述了本发明，但是该描述仅仅是本发 明的表示而不被解释为限制本发明。对于本领域技术人员而言可以有 各种修改和应用，而不背离由所附权利要求定义的本发明的真实精神 和范围。