用于防止需求死锁并实现均衡链路利用的流量工程系统

摘要

本文描述了示例性流量工程方案。根据示意性实施例，可提供代表网络中的链路的可分配容量的多个分层阈值。所述分层阈值可有效地限制流量工程系统被允许在网络中的链路上分配的数据量。所述流量工程系统可尝试根据最小的阈值在网络中分配数据流。若所述网络不能根据最小的阈值接纳所述数据流，则可尝试次小的阈值。依逐渐增大的顺序依次测试所述阈值直至最大的阈值被尝试为止。若找到了可行的阈值，则所述数据流可被分配至网络内的路径。若所述流量工程系统不能在任何一个所述分层阈值上接纳所述数据流，则所述流量工程系统可报告失败。

说明书

背景技术

在通信网络中，信息(诸如，数据串流(data stream)或数据包)可 被从源传输到目的地。所述信息可以被作为数据流(data flow)传输，其 中，所述数据流是于所述源与所述目的地之间沿路径携带所述信息的被分 配的连接。通常，数据流具有相关的大小(比如，特定数据流每秒发送五 个单位(诸如兆比特)的信息)。

所述源和所述目的地可为所述网络中的节点。节点代表与网络通信的 装置，并且信息可经由所述装置传递、发源、和/或终止。所述节点可例如 是：诸如个人计算机、电话或平板电脑之类的计算装置；诸如电子邮件服 务器、数据服务器或网页服务器的服务器；路由器；交换机；以及其他网 络装置。

所述数据流可经网络中的路径传输。两节点之间的连接被称为“链路 (link)”，并且一个或多个链路可形成连接源和目的地的路径。网络中的 路径可使用一个或多个传输介质从所述源连接至所述目的地，可能沿途经 过一个或多个节点。

所述传输介质可为适于传输信息的任何介质，诸如，铜线、光缆、或 者经空气传播的无线电波，及其他选择。

每个链路都有相关的容量，所述容量代表所述链路在任意给定时间能 够接收的数据量。当一个链路无法接纳更多数据流时，后续数据流可被分 配至不同的链路。流量工程涉及在不同的可能通信路径之间优化网络路由 以满足在网络中传递数据的应用或节点的需求的问题。

随着更多的节点、数据流以及链路被加入网络，为不同数据流分配路 径变得越来越复杂。选择合适的数据量以分配给给定的链路，并平衡网络 中的链路的带宽以期以最快、最高效的方式路由每个数据流是流量工程系 统的难题。

发明内容

本文描述了示例性流量工程解决方案。根据示意性实施例，可提供二、 三或更多个分层阈值，所述分层阈值代表网络中的链路的可分配容量。所 述分层阈值可有效地限制流量工程系统被允许在网络中的链路上分配的 数据量(并且，累积地，为网络整体分配的数据量)。所述流量工程系统 可尝试根据最小的阈值在网络中分配数据流。若所述网络能够根据最小的 阈值接纳所述数据流，则所述数据流可被分配。若所述网络根据最小的阈 值不能接纳所述数据流，则可尝试次小的阈值。可依逐渐增大的顺序依次 测试所述阈值直至最大的阈值被尝试为止。若所述流量工程系统能够在所 述分层阈值的其中一个上接纳所述数据流，则所述数据流可被分配至网络 内的路径。若所述流量工程系统不能在任何一个所述分层阈值上接纳所述 数据流，则所述流量工程系统可报告失败。

根据一个示例性实施例，可识别网络中的数据流。所述网络可具有由 链路相互连接的多个节点。每个所述链路具有可被分配至其上的数据的最 大容量。所述流可被从网络中的源节点传输至网络中的目的地节点。

可提供多个分层阈值。每个分层阈值可代表一个阈值大小，所述阈值 大小可为链路的容量的可被分配以由网络中的流使用的一部分。与所述分 层阈值相关联的所述可分配容量可小于或等于链路的最大容量。所述分层 阈值可包括至少三层阈值大小。

可确定网络中所述源节点和所述目的地节点之间的路径。确定所述路 径可包含基于一个分层阈值的阈值大小评估网络中的链路以确定所述链 路是否能够在所述一个分层阈值上形成所述路径。若在所述链路被限于所 述一个分层阈值的阈值大小时，所述链路能够形成在所述源和所述目的地 之间的完整路径，则所述流可被分配到所述路径。若所述链路不能够在所 述阈值大小形成路径，则可顺序测试剩余分层阈值的其他阈值大小。可重 复所述测试直至确定所述路径或确定使用所述分层阈值中的任何一个均 无法形成所述路径。若确定所述网络无法接纳所述流，则可报告该失败。

为在所述网络中确定路径，可构建所述网络的图形。所述图形可初始 为空。所述图形可以由可分配容量大于所述流需求的容量大小的链路填 充。可检索所述被填充的图形以寻找所述源节点和所述目的地节点之间的 路径。

所述流量工程系统可为多个流分配路径。若所述流量工程系统确认所 述网络无法在第一分层阈值接纳第一流，但所述网络可在第二分层阈值接 纳所述第一流，则所述流量工程系统可将此情形解释为所述网络在所述第 一分层阈值过载。因此，可不必在所述第一阈值为后续流检索路径。故而， 所述流量工程系统可不考虑所述第一分层阈值而开始在所述第二分层阈 值检索第二、后续路径。

所述流可包括多个流组分。在这种情况下，可为每个流组分单独确定 路径。

在一些情况下，流可能是延迟敏感的。相应地，所述流量工程系统可 确定哪些流是延迟敏感的，并基于流的延迟敏感度将路径优先分配给所述 流。例如，可首先分配延迟敏感路径，并可将所述图形中更加高效的路径 分配给所述延迟敏感路径。

所述流量工程系统可被实施为存储于非瞬时介质上的指令、方法、或 包括存储器和处理器的系统，以及其他可能性。使用上述流量工程系统， 数据流可以高效且有效的方式被分布在网络中，同时为所述数据流的增长 提供空间而不接近所述链路的最大容量(若在给定的网络的约束下有可能 完成这种配置)。

附图说明

图1示出了示例通信网络100；

图2A示出了网络100中从节点A到节点B的第一路径；

图2B示出了网络100中从节点A到节点B的第二路径；

图3示出了来自网络100的示例链路140；

图4是示出了用于将k个流组分分配至网络中的一个或多个可用路径 的示例算法的流程图；

图5是示出了用于在网络中为给定的流组分寻找路径的示例方法论的 流程图；

图6示出了适用于本文所述的示例性实施例的示例电子装置600；

图7示出了适于实施本文所述的示例性实施例的示例分布环境。

具体实施方式

本文描述的示意性实施例根据一系列分层阈值在网络中将数据流分 配至路径/链路。使用所述分层阈值使得数据流能够被分散到网络中，进而 将本可能被指定到“热门”链路的数据流移动到拥塞较少的链路，并减少 网络中的任意给定链路溢出的可能性。若在某特定分层阈值上无法接纳网 络中的所有数据流，则可将阈值增加至下一层。故而，在保持在整个网络 的链路中对数据流的平均分配的同时，能够接纳不断增加的数据流。只要 数据流在一个分层上可被接纳，该数据流即可在网络中被允许；然而，数 据流不会集中于热门链路。故而，所述网络可被充分利用，同时仍限制链 路将溢出的可能性。

根据不同的衡量标准，数据流可被分配至网络中的不同路径。直觉地， 人们可能希望通过网络沿最短、最快且最高效的路径发送每个信息单位。 然而，该方案从长远看来并非总是可能的，或者甚至不是可取的。

例如，图1示出了通信网络100，所述通信网络100具有三个节点： 节点A 110、节点B 120和节点C 130。在该示例中，节点A 110是源节点， 其将信息发送至节点B 120。节点B 120是目的地节点。

从所述源至所述目的地的路径可包括一条或多条链路140、150、160。 一条链路代表两个节点之间的连接，其可形成一条路径的部分或全部。例 如，若所述路径是所述源与所述目的地之间的直接连接，则所述路径包括 单个链路。

在一个给定的源和一个给定的目的地之间可存在不止一条路径。为了 决定哪些数据流将使用哪些路径，流量工程系统170可与不同的节点110、 120、130进行通信。所述流量工程系统170可分析网络中的流量(traffic  flow)并将数据流指定至特定的路径。参照附图4-6详细描述所述流量工 程系统170。

例如，如图2A所示，网络100中的第一路径210始于节点A 110且 终于节点B 120，未经过任何中间节点。因此，所述第一路径210包括单 个链路：链路AB 140。

第二路径220(见图2B)亦始于节点A 110且终于节点B 120。然而， 所述第二路径220还经过节点C 130，且因此包括两条链路：链路AC 150 和链路CB 160。故而，以在节点A 110和节点B 120之间传输信息为目的， 所述第二路径220可能比所述第一路径120更慢和/或效率更低。

如图3所示，考虑节点A 110(图1)沿所述链路AB 140传输两个数 据流(第一流310和第二流320)至节点B 120(图1)的情况。所述链路 AB 140可具有链路容量330，其中，所述链路容量330可例如被表示为单 位时间所述链路AB 140能够接纳的若干信息单位(比如，6千兆比特每秒， 或“Gbps”)。在该示例中，所述第一流310可能需求3Gbps，而所述第二 流也需求3Gbps。在此情况下，所述链路AB 140能够接纳数据流310和 320两者，因为所述链路AB 140的容量等于或大于所述链路AB 140承载 的所述数据流310、320置于所述链路AB 140上的需求。

然而，若所述第二流320随后增加至4Gbps，所述链路AB 140不再 能接纳数据流310、320两者。幸运的是，另一路径(第二路径180)存在 于节点A 110和节点B 120之间(见图2B)。因此，数据流310、320的其 中之一可移动至所述第二路径220。

相似的，若第三数据流被加入至网络(例如，节点B 120将需求3Gbps 的数据流传回至节点A 110)，则所述链路AB 140将无法接纳所述第三数 据流。所述第三流可因此被分配至所述第二路径220。

然而，如上文提到的，以在节点A 110和节点B 120之间传输信息为 目的，所述第二路径220可能比所述第一路径120更慢和/或效率更低。这 是由于与所述第一路径210相比，在所述第二路径220上的中间节点(节 点C 130)的增加引起的额外的延迟。

尽管如此，将至少部分容量分配到速度较慢或者效率较低的链路上可 能是重要的。试想，例如，网络利用传输控制协议(TCP)以在数据流中 传输包。若链路变得过载，部分正在链路上被传输的包被丢弃。当遭遇被 丢弃的包时，TCP被设计为大幅缩减被传输的包的数量以避免网络中拥塞 崩溃。

相应的，若链路的全部容量被分配(如图3所示示例中，其中所述第 一流310和所述第二流320一起利用链路AB 140的全部6Gbps容量)，所 述链路很容易在出现流量尖峰的时候(如所述第二流320增长至4Gbps的 情况)过载。因此，TCP将会使在所述链路上的所述流310、320显著地 降低其传输速率，这导致由所述链路AB 140表示的连接质量和速度受到 损害。

可通过将所述数据流中的一些分配至较长的第二路径220来避免该问 题。例如，所述第一流310可被分配至所述第一路径210，同时所述第二 流320被分配至所述第二路径220。虽然所述第二流320使用较长路径通 过网络100，但链路140、150、160中的每一个均保有额外的容量。故而， 流310、320具有额外的空间来增长而不会导致链路140、150、160过载。

数据流分配问题的一个可能的解决方案是选择要应用于网络中的链 路的阈值。一个链路可被分配总计多达所述阈值的数据流，但不能超过所 述阈值。例如，一个链路可被分配所述链路总容量的70％(比如，可处理 10Gbps的链路被视为一个7Gbps链路)。这种策略为分配至所述链路的数 据流提供了空间以增长，而不致拥塞所述链路。

然而，这种解决方案可能是有问题的，因为根据这种方法运行的流量 工程系统可能错误地报告所述网络无法接纳额外的数据流，而实际上所述 网络可能能够接纳所述数据流。

例如，考虑图1中的网络。假设每个所述链路(链路AB 140、链路 AC 150，以及链路CB 160)具有10Gbps容量。若所述流量工程系统指定 一个70％的阈值，则所述流量工程系统可指定多达7Gbps至每个链路。

从节点A至节点B的第一数据流可能需求3Gbps。所述流量工程系统 可检查可分配的容量并确定所述第一数据流可被接纳于链路AB 140上。 这在所述链路AB 140上留下4Gbps的可用容量(即，在70％的阈值上 10Gbps给出7Gbps可分配容量，其中的3Gbps被分配给所述第一数据流， 余下4Gbps留以分配)。

然后，若节点B请求所述流量工程系统接纳从节点B传输至节点C 且运行在12Gbps的第二数据流，所述流量工程系统将报告无法接纳该数 据流。这是因为，在由节点B至节点C的路径上没有留下12Gbps的可分 配容量。

应当注意到，在一些实施例中，数据流可被拆分成数据流组分。数据 流组分是将数据流分割而形成的更小的片段。故而，12Gbps的数据流可被 拆分成7Gbps的组分和5Gbps的组分。

在此情况下，所述流量工程系统可尝试在链路CB 160(其仍有完整的 7Gbps的可分配容量)接纳所述7Gbps组分。这就余下必须由节点B传输 至节点C的5Gbps。节点B和节点C之间仅有的其他可用路径是经由链路 AB 140沿节点B至节点A，且随后经链路AC 150从节点A至节点C。虽 然链路AC 150未被分配且因此具有7Gbps可分配容量，但所述数据流必 须首先经链路AB 140传输，其中3Gbps已经被分配给所述第一流。故而， 该路径上仅有4Gbps可用，而所述第二数据流中仍有5Gbps。因此，所述 数据工程系统报告所述第二数据流不能被接纳于网络中的任何路径上。

然而，可以看出，阻止所述12Gbps的第二数据流被接纳于网络中的 唯一因素是所述人为的70％分配阈值。实际上，链路AB 140具有7Gbps 的剩余容量(而不是由于所述70％分配阈值的应用而被报告的4Gbps)。 在该情况下，由于所述70％分配阈值仅是应对网络溢出的缓冲且链路AB 能够轻易接纳额外的5Gbps(伴随2Gbps的容量留下以备用)，因此接纳 所述第二数据流是可取的。

一种可能性是单纯使用更高的阈值，诸如80％。然而，这仍是一个有 问题的解决方案。若阈值初始设置为更高的大小(80％而非70％)，则更 多容量被指定给初始数据流。当所述阈值接近100％时，上文指出的过度 分配问题(以及相关的链路溢出的风险)会更加严重。因此，某些链路， 诸如连接高流量节点的链路，会被频繁使用，而其他链路可能保持大部分 未被分配。这种数据流的集中增加了流量尖峰将导致更加热门的链路出现 溢出的风险。

此外，无法保证更高的阈值将能够接纳网络中的所有数据流。在这个 意义上，80％的阈值并不比70％的阈值好，因为请求分配的容量无法被预 测，且因此总有请求分配的容量会大于人为阈值的可能。

有鉴于此，示例性实施例提供了一种定义了多层阈值的流量工程系 统。如上所述，流量工程系统可以通过应用初始阈值在任何可能时候在网 络中不同的路径(且因此不同的链路)之间平衡数据流。对初始阈值的使 用允许将数据流分散于网络中，减少任何一个链路会溢出的风险。若所述 链路在当前阈值出现饱和，所述阈值可被增加至下一层，进而接纳更多的 数据流，同时保持所述数据流在网络中的链路之间尽可能分散。所述链路 可被动态地分配(比如，当更多数据流请求网路中的路径时，所述分层阈 值可被增加)，以便当更多的数据流被加入所述网络时保持平衡。

更具体地，示例性实施例经过多轮以在网络中找到路径。替代于每个 链路具有固定的阈值(比如，70％)，一系列的阈值可被用于所有链路。例 如，可定义诸如50％、70％和100％的层(T_1＝50％、T_2＝70％，和 T_3＝100％)。

最初，所述流量工程系统可假设所有链路仅有(T_1*Link_capacity) 可用以尝试在网络中寻找路径。在上述示例中，所述流量工程系统可假设 每个链路仅使用其容量的最多50％以寻找路径。若所述流量工程系统成功 找到可行路径，则将所述数据流分配至所述路径。若所述流量工程系统未 成功，所述流量工程系统可将每个链路视为所述链路可使用其容量的最多 70％。因为所述链路容量已被增大，一些新路径可能变为可用。所述流量 工程系统可继续进行至下一层直到所有数据流已经被分配至路径，直到所 有层已被耗尽。

该技术可有助于使链路更均衡地被利用。例如，若使用每个链路的仅 50％可满足流的需求，则初始时链路被利用了不超过50％。这有助于更好 地管理网络的增长并因此降低成本。

例如，图4是示出了用于将k个流组分分配至网络中的一个或多个可 用路径的示例算法的流程图。

应当注意到，图4和图5是从流量工程系统的角度呈现的，该流量工 程系统在网络中的节点为数据流请求路径时实时动态地在网络中分配数 据流。尽管对图4和图5的描述将涉及“流组分”，但应当注意到这些步 骤可同样地应用于整个数据流。此外，不需要所有的流组分属于相同的数 据流。

在步骤410中，可确认k个流组分，其中k可为整数值。所述流组分 可为一更大的数据流的各个部分。所述流量工程系统可以根据预定的算法 将数据流拆分成流组分。例如，所述流量工程系统可确立流组分的最大大 小，并可将所述数据流拆分成不超过所述最大大小的流组分。可替代地， 所述流量工程系统可检查网络中链路之间未被分配的容量，并可基于可用 容量的数量将所述数据流拆分成流组分(比如，若网络中的路径能够接纳 最多xGbps，则所述组分之一可为大小x)。

在步骤420中，所述流量工程系统可为下一个流组分确定路径。下文 参考附图5详细描述步骤420。

在步骤430中，确定是否为图4中的流组分成功找到了路径。若否， 则在步骤440中所述流量工程系统报告失败。例如，所述流量工程系统可 向请求为所述数据流分配路径的节点发送消息。所述消息可表明没有路径 可用。

若在步骤430确定成功地找到了路径，则在步骤450中可更新网络上 的链路分配。对于在步骤420中确认的路径中的每个链路，可从所述链路 的剩余的可分配容量中减去所述流组分的大小。

在步骤460中，所述流量工程系统可确定是否具有额外的流组分请求 被指定路径。若在步骤460的确定是“是”，则流程返回至步骤420并试 图为下一个流组分寻找路径。若在步骤460的确定是“否”，则所有流组 分已被分配至路径。所述流量工程系统相应地进行至步骤470，且处理结 束，直至另一节点为另一数据流请求路径。

图4的步骤可由下述伪代码表示。

为下述伪代码的目的，假设我们意在为与感兴趣的数据流对应的k个 组分寻找路径。每个组分(也被称作标记交换路径或者“LSP”)可以是数 据流的源和目的地之间的一个虚拟路径。每个所述组分可具有D单位的传 输能力需求(即，流的总需求是k*D)。注意，不需要每个组分具有相同 的需求D，并且所述算法可被轻易修改以应对每个组分具有不同需求的情 况。

抽象变量network_state_ptr表示网络拓扑状态(Network Topology  State)数据结构。进一步地，令T[]为分层阈值的数组(比如，T[1]＝50％， T[2]＝70％，T[3]＝100％)。令N为数组T[]中的层数(比如，若T为 {0.5,0.8,1.0}，则N＝3)。令src为流的源。令dst为流的目的地。

下述伪代码通过网络为一组给定的数据流组分(LSPs)寻找所有可用 的路径。一旦路径被确认，所述路径被指定并且所述网络拓扑状态数据结 构被更新以说明在路径中链路上被减少的可分配容量。结合附图5详细描 述的函数FindOnePath()负责通过在顺序增加的分层阈值上顺序地测试所 述网络链路以为所述数据流组分定位可用的路径。

伪代码：

                   

            

图5是示出了用于为网络中给定的流组分寻找路径的示例方法论的流 程图。例如，可将图5的步骤作为图4的步骤420实施，或作为上述伪代 码中的函数FindOnePath()的实施方式。

在步骤510中，确认i个分层阈值，其中，i可为整数值。所述分层阈 值可代表用于网络中链路上的可分配容量的两个、三个，或者更多个值。 分层阈值的个数和每个分层的数值可被预先确定并被预先编程到所述流 量工程系统中。可通过所述网络的实验或模拟以确定最佳的或可行的阈值 来初始确定所述分层阈值。可替代地，可由所述流量工程系统通过分析所 述网络当前状态或网络中的历史数据流模式以程序方式确定所述分层阈 值。

最大分层阈值可被设为100％以使得所述流量工程系统能够分配一个 链路的所有容量，以备为了接纳数据流而需要如此做。虽然本文将所述分 层阈值依百分比表示，但应当注意所述分层阈值的数值不必以百分比表 示。所述分层阈值的数值可被表示为例如分数、或应用于所述链路的最大 容量的乘数，或要从所述链路的数值中被减去的数值。

在步骤515中，可确认下一个分层阈值。所述流量工程系统可以按升 序评估所述分层阈值。若此为图5所述的算法的初次运行，则可使用第一 分层阈值。然而，应当注意，在某些情况下图5所述算法的首次运行可使 用不同的值。这类场景将于本部分结尾处的伪代码之后描述。

为了确定对于给定的流组分是否存在任何可行的路径，可利用图论。 故而，在步骤520中,可创建一个空的网络图形。所述空的网络图形可被 所述网络的节点填充，但没有所述网络的链路。

在步骤525中，可确认网络中的链路。例如，所述网络中的每个链路 可被指定一个识别号码，并且所述流量工程系统可按顺序遍历所述网络中 的链路。可替代地，可选择网络中的两个节点，并且评估所述节点之间的 链路。

在步骤530中，基于在步骤515中确认的阈值确定所选择的链路的可 分配容量。可通过评定所述链路的最大容量，并将在步骤515确认的阈值 的数值应用至所述最大容量以得到可分配容量，来确定所述链路的可分配 容量。例如，若当前的阈值是50％，且所述链路的最大容量是10Gbps， 则所述链路的可分配容量是5Gbps。

所述链路的最大容量可被预先编程到所述流量工程系统中。可替代 地，所述流量工程系统可通过检查当前或历史经过所述链路的数据流来确 定所述链路的最大容量。可替代地，所述流量工程系统可询问另一装置(诸 如，附接于所述链路的节点之一或网络中的服务器)来确定所述链路的最 大容量。

在步骤535中，确定在步骤530中确定的所述链路的可分配容量是否 超过正被评估的所述流组分所要求的容量值。若是，在步骤540中可将所 述链路添加至所述网络图形。

在步骤545中，可确定是否有任何链路待评估。若是，流程返回至步 骤525并评估网络中的剩余未评估的链路。若否，则所述网络图形已被能 够接受正被评估的所述流组分的链路完全填充。流程因此执行至步骤550。

在步骤550中，现存在被填充的网络图形。所述网络图形被所有具有 足够容量以接纳正被评估的所述流组分的链路填充。然而，即使已经找到 了一些可用的链路，仍可能存在所述链路不能连接在一起以形成所述流组 分的源和所述流组分的预期目的地之间的路径的情况。故而，在步骤550 中确定利用在步骤525-545中确认的可用链路是否可形成所述源和目的地 之间的可用路径。

存在很多用于确定图中是否存在路径的合适算法。例如，可使用 Dijkstra算法来确定是否存在这样的路径。Dijkstra算法仅是用于在图中寻 找路径的合适算法中的一例，且也可以采用其他合适的算法。

确认路径存在并使用被确认的第一路径可能就足够了。可替代地，可 确认最有效率的路径，其中效率由与每个链路关联的代价表示。所述代价 可代表，例如，当在给定的链路上发送流量时遭受的延迟的量。然后，可 选择最少代价路径。在一些实施例中，可确定多个可用路径并选择最少代 价的路径。

若在步骤550中确定有路径可用，则在步骤555中返回所确认的路径。

若在步骤550中确定在当前分层阈值没有可用路径，则在步骤560中 所述流量工程系统确定是否存在用于评估的额外的层。若没有额外的层存 在，则在步骤565中所述流量工程系统可报告失败。若存在额外的层，则 可在步骤515开始评估下一层。

附图5的步骤可由以下伪代码表示：

                   

            

注意，在上述用于寻找K个路径的方案中，FindOnePath()开始于所述 第一层级(即，k＝1)。然而，在找到第一路径之后，即知道了存在允许可 用路径的链路的最小层。因此，可将该层值(k)由FindOnePath()返回至 FindALLPaths()。然后，在下一个循环中，不再从k＝1开始，FindOnePath() 可从之前的层值k开始。这样可在当存在大的层数值，和/或网络拥塞时显 著提高FindAllPaths()的速度。

可将上述行为中的一个或多个编码为可由处理逻辑执行的计算机可 执行指令。所述计算机可执行指令可被存储于一个或多个非瞬时计算机可 读介质上。可在适当编程的电子装置中执行上述行为中的一个或多个。图 6示出了可适用于本文披露的一个或多个行为的电子装置600的示例。

所述电子装置600可为多种形式，包括但不限于计算机、工作站、服 务器、网络计算机、量子计算机、光学计算机、网络家电、移动装置、寻 呼机、平板电脑、智能传感器、专用处理装置，等等。

所述电子装置600是示意性的且可为其他形式。例如，所述电子装置 600的一个可替换实施例可具有更少的部件、更多的部件，或者是配置与 图6的配置不同的部件。可使用基于硬件的逻辑、基于软件的逻辑，和/ 或基于硬件和软件的逻辑的组合的逻辑(例如混合逻辑)来实施本文描述 的附图6和/或其他附图的部件；因此，附图6和/或其他附图中示出的部 件不限于特定类型的逻辑。

处理器602可包括基于硬件的逻辑或基于硬件的逻辑和软件的组合以 代表所述电子装置600执行指令。所述处理器602可包括可解释、执行， 和/或以其他方式处理包含于例如内存604中的信息的逻辑。所述信息可包 括可实施本发明的一个或多个实施例的计算机可执行指令和/或数据。所述 处理器602可包括多种同构或异构硬件。所述硬件可例如包括一个或多个 下述部件的组合：处理器、微处理器、现场可编程门阵列(FPGA)、专用 指令集处理器(ASIP)、专用集成电路(ASIC)、复杂可编程逻辑器件 (CPLD)、图形处理器(GPU)，或可解释、执行、操作，和/或以其他方 式处理信息的其他类型的处理逻辑。所述处理器可包括单个核心或多个核 心603。此外，所述处理器602可包括片上系统(SoC)或者系统级封装 (SiP)。

所述电子装置600可包括一个或多个用于存储一个或多个计算机可执 行指令或软件的有形的非瞬时计算机可读存储介质，该计算机可执行指令 或软件可实施本发明的一个或多个实施例。所述非瞬时计算机可读存储介 质可例如为内存604或存储器618。所述内存604可包括随机存取存储器 (RAM)，其中所述RAM可包括可存储信息的RAM装置。所述RAM装 置可为易失的或非易失的，且可包括例如一个或多个动态随机存取存储器 (DRAM)装置、闪存装置、静态随机存取存储器(SRAM)装置、零电 容随机存取存储器(ZRAM)装置、双晶体管随机存取存储器(TTRAM) 装置、只读存储器(ROM)装置、铁电随机存取存储器(FeRAM)装置、 磁阻随机存取存储器(MRAM)装置、相变内存随机存取存储器(PRAM) 装置，或替他类型的RAM装置。

一个或多个计算装置600可包括用于执行加载在内存604中的指令的 虚拟机(VM)605。可提供虚拟机605以控制运行在多个处理器上的进程， 进而所述进程可如同仅使用了一个计算资源而非多个计算资源。可在所述 电子装置600中采用虚拟化技术(virtualization)，以便所述电子装置中的 基础结构和资源可被动态地共享。多个虚拟机605可驻留于单个计算装置 600上。

硬件加速器606可被实现于ASIC、FPGA，或一些其他装置中。所述 硬件加速器606可被用于减少所述电子装置600的一般处理时间。

所述电子装置600可包括网络接口608以通过各种连接接合至局域网 (LAN)、广域网(WAN)或互联网，其中，所述各种连接包括但不限于 标准电话线、LAN或WAN链路(比如，T1、T3、56kb、X.25)、宽带连 接(比如，综合业务数字网(ISDN)、帧中继、异步传输模式(ATM)、 无线连接(比如，802.11)、高速互连(比如，无限带宽、千兆以太网、 Myrinet)或上述任意一些或全部的某种组合。所述网络接口608可包括内 置网络适配器、网络接口卡、个人计算机内存卡国际联合会(PCMCIA) 网卡、卡总线网络适配器、无线网络适配器、通用串行总线(USB)网络 适配器、调制解调器，或任何其他适于将所述电子装置600接合至能够通 信并执行本文所述的操作的任何类型的网络的装置。

所述电子装置600包括一个或多个可被用于接收来自例如用户的输入 的输入装置610，诸如，键盘、多点触摸界面、指示装置(比如，鼠标)、 陀螺仪、加速计、触觉反馈装置、触觉感应装置、神经装置、麦克风，或 相机。注意，电子装置600可包括其他合适的输入输出(I/O)外围设备。

所述输入装置610可允许用户提供注册在视觉显示装置614上的输 入。图形用户界面(GUI)616可被显示于所述显示装置614上。

存储装置618也可与所述计算机600关联。所述处理器602可经I/O 总线访问所述存储装置618。所述信息可被所述处理器602执行、解释、 操作，和/或以其他方式处理。所述存储装置618可例如包括诸如如下的存 储装置：磁盘、光盘(optical disk)(比如，CD-ROM、DVD播放器)、随 机存取存储器(RAM)盘、磁带单元(tape unit)，和/或闪存驱动器。所 述信息可被存储于一个或多个包含于所述存储装置中的非瞬时有形计算 机可读介质上。该介质可包括例如磁盘、光盘、磁带，和/或储存装置(比 如，闪存装置、静态随机存取存储器(SRAM)装置、动态随机存取存储 器(DRAM)装置，或其他储存装置)。所述信息可包括可实施本发明的 一个或多个实施例的数据和/或计算机可执行指令。

所述存储装置618可进一步存储应用624，并且所述电子装置600可 运行操作系统(OS)626。OS 626的示例可包括操 作系统、Unix和Linux操作系统、用于麦金塔电脑的诸如塞班 操作系统的嵌入式操作系统、实时操作系统、开源操作系统、专有操作系 统、用于移动电子装置的操作系统，或能够在所述电子装置上运行并执行 本文所述的操作的其他操作系统。所述操作系统可在本机模式或仿真模式 中运行。

所述存储装置618可进一步包括用于执行流量工程功能的流量工程逻 辑628。所述流量工程逻辑628可包括用于执行附图4和5中所述的步骤 的指令。如上文参考附图5提到的，所述存储装置618也可维护描述网络 上的链路的可分配容量的网络图形。

可使用可实现于一个或多个非瞬时有形计算机可读介质上的计算机 可执行指令和/或数据来实施本发明的一个或多个实施例。所述介质可为， 但不限于，硬盘、高密度光盘、数字通用光盘、闪存卡、可编程只读存储 器(PROM)、随机存取存储器(RAM)、只读存储器(ROM)、磁阻随机 存取存储器(MRAM)、磁带，或其他计算机可读介质。

图7示出了可实施本发明的一个或多个实施例的网络实施方式。系统 700可包括计算装置600、网络712、服务提供者713、目标环境714，以 及集群(cluster)715。图7的实施例是示意性的，且其他实施例可包括更 多装置、更少装置，或布置与图7的布置不同的装置。

所述网络712可将数据从源传输到目的地。所述网络712的实施例可 使用网络装置及连接(比如，链路)以传输数据，其中所述网络装置诸如 路由器、交换机、防火墙，和/或服务器(未示出)。数据可涉及具有可适 用于一个或多个网络和/或一个或多个装置(比如，所述计算装置600、所 述服务提供者713等)的基本上任意格式的任意类型的机器可读信息。数 据可包括数字信息或模拟信息。数据还可为封包的和/或非封包的。

所述网络712可为使用有线导体和/或光纤的硬布线网络，和/或可为 使用自由空间光学传输路径、射频(RF)传输路径，和/或声学传输路径 的无线网络。在一个实施方式中，所述网络712可为实质上开放的公用网 络，诸如互联网。在另一个实施方式中，所述网络712可为更加受限的网 络，诸如企业虚拟网络。所述网络712可包括互联网、内联网、局域网 (LAN)、广域网(WAN)、城域网(MAN)、无线网络(比如，使用IEEE 802.11)，或其他类型的网络。所述网络712可使用中间件，诸如，公共对 象请求代理体系结构(CORBA)或分布式组件对象模型(DCOM)。本文 所述的网络和/或在网络上运行的装置的实施方式并不限于例如任何特定 的数据类型、协议、和/或架构/配置。

所述服务提供者713可包括使服务对另一个装置可用的装置。例如， 所述服务提供者713可包括使用服务器和/或其他装置向目的地提供一个 或多个服务的实体(比如，个人、公司、教育机构、政府机关等)。服务 可包括被目的地执行以实施操作(比如，最优化操作)的指令。可替代地， 服务可包括代表目的地被执行以代表目的地实施操作的指令。

所述服务器714可包括通过所述网络712接收信息的装置。例如，所 述服务器714可为接收来自所述计算机600的用户输入的装置。

所述集群715可包括若干执行单元(UE)716，且可代表所述计算机 600和/或(诸如所述服务提供者713或服务器714的)另一装置实施处理。 例如，所述集群715可并行处理接收自所述计算机600的操作。所述集群 715可包括位于单个装置或芯片上或位于若干装置或芯片上的执行单元 716。

所述执行单元(UE)716可包括代表装置(诸如请求装置)实施操作 的处理装置。执行单元(UE)可为微处理器、现场可编程门阵列(FPGA)， 和/或其他类型的处理装置。UE 716可包括代码，诸如用于操作环境的代 码。例如，UE可运行关于并行处理活动的操作环境的一部分。所述服务 提供者713可操作所述集群715，并且可以根据订阅(比如，经由网络服 务)向所述计算机600提供交互式优化能力。

执行单元(UE)可为应用624提供远程/分布式处理能力。硬件执行 单元可包括装置(比如，硬件资源)，其中，所述装置可实施和/或参与并 行编程活动。例如，硬件执行单元可响应于其接收到的(比如，直接接收 或经由代理(proxy)接收)请求和/或任务实施和/或参与并行编程活动。 硬件执行单元可使用一个或多个装置实施和/或参与基本上任何类型的并 行编程(比如，任务处、数据处理、流处理等)。例如，硬件执行单元可 包括单个处理装置，所述单个处理装置包括多核心或若干处理器。硬件执 行单元也可为可编程装置，诸如现场可编程门阵列(FPGA)、专用集成电 路(ASIC)、数字信号处理器(DSP)，或其他可编程装置。在硬件执行单 元中使用的装置可被布置为多种不同配置(或拓扑结构)，诸如网格、环 状、星形，或其他配置。硬件执行单元在实施处理操作时可支持一个或多 个线程(或进程)。

软件执行单元可包括软件资源(比如，技术计算环境)，其中所述软 件资源可实施和/或参与一个或多个并行编程活动。软件执行单元可响应于 收到程序和/或该程序的一个或多个部分来实施和/或参与一个或多个并行 编程活动。软件执行单元可使用一个或多个硬件执行单元来实施和/或参与 不同类型的并行编程。软件执行单元在实施处理操作时可支持一个或多个 线程和/或进程。

术语“并行编程”可被理解为包括多种类型的并行编程，比如，任务 并行编程、数据并行编程以及流并行编程。并行编程可包括多种类型的处 理，其中所述处理可以跨越多个资源(比如，软件执行单元、硬件执行单 元、处理器、微处理器、集群、实验室)分布，并可同时执行。

例如，并行编程可包括任务并行编程，其中，可在若干软件执行单元 上同时处理若干任务。在任务并行编程中，可独立于其他任务执行来处理 一个任务，例如，同时处理。

并行编程可包括数据并行编程，其中数据(比如，数据集)可被解析 为可以使用例如软件执行单元并行执行的若干部分。在数据并行编程中， 所述软件执行单元和/或所述数据部分可以在处理进行时互相通信。

并行编程可包括流并行编程(有时称为流水线并行编程)。流并行编 程可使用被例如串联(例如，线)布置的若干软件执行单元，其中，第一 软件执行单元可产生可被送入第二软件执行单元的第一结果，所述第二软 件执行单元在获得所述第一结果后产生第二结果。流并行编程也可包括一 个状态，其中任务分配可被表示为一个有向无环图(DAG)或循环图。

其他并行编程技术可包含仅任务、数据、和/或流并行编程技术的一些 组合，或任务、数据，和/或流并行编程技术与其他类型的处理技术的一些 组合，以形成混合并行编程技术。

前面的说明书可提供本发明的多种实施例的说明和描述，但是并非意 在穷举或将本发明限制于所披露的具体形式。根据上述教导进行修改和变 化是可能的或其可由对本发明的实施而获得。例如，由于上文已描述了一 系列行为，可以在与本发明的原则一致的其他实施方式中修改所述行为的 顺序。另外，非依赖性行为可被并行实施。

此外，在不脱离本发明的精神的情况下，可以使用与所述附图中示出 的和说明书中描述的装置和/或配置不同的一个或多个装置和/或配置来实 施与本发明的原则一致的一个或多个实施方式。取决于具体的部署和/或应 用，可向所述附图的实施方式中加入和/或从所述附图的实施方式中移除一 个或多个装置和/或部件。而且，一个或多个所披露的实施方式可不限于硬 件的特定组合。

另外，本发明的某些部分可被实施为可执行一个或多个功能的逻辑。 该逻辑可包括硬件(诸如，硬布线逻辑、专用集成电路、现场可编程门阵 列、微处理器)、软件、或硬件与软件的组合。

在本发明的说明书中使用的元件、行为或指令不应被解释为对本发明 是关键的或必不可少的，除非存在此类明确的描述。例如，可在不使用空 闲期间分析器160或不确定系统110是否处于空闲期间的情况下实施本发 明。因此，非延迟敏感性请求可被分割为子请求并且被服务而不考虑空闲 期间是否生效。可替代地，在不将所述非延迟敏感性请求分成子请求的情 况下可使用所述空闲期间分析器160。

另外，本文使用的，冠词“一”旨在包括一个或多个项目。在意在表 示一个项目的场合，会使用词语“单个”或类似语言。另外，本文所使用 的词语“基于”意在表示“至少部分基于”，除非有明确的其他不同表述。 此外，本文所使用的词语“用户”意在被宽泛地解释以包括例如电子装置 (比如，工作站)或者电子装置的用户，除非有其他不同说明。

本发明并非意在受限于上述披露的特定实施例，相反，本发明意在包 括落入所附权利要求的范围内的任何及全部的特定实施例和等同替换。