独立于通信量模式可变性的有效且稳健的路由选择

摘要

一种通过由链路互连，并且具有至少一个入口点和至少一个出口点的节点的网络路由数据的方法包括下述步骤：接收对用于在入口点和出口点之间路由数据的具有服务要求的路径的请求；选择入口点和出口点之间的一组一个或多个中间节点；根据所述网络的带宽，确定从入口点发送给所述一组一个或多个中间节点中的每个节点的数据的相应分数；把确定的相应分数的数据从入口点路由给所述一组一个或多个中间节点中的每个节点；和把数据从所述一组一个或多个中间节点中的每个节点路由给出口点。

说明书

相关申请的交叉参考

本申请要求2004年5月28日提交的共同待审美国临时申请No.60/575350的优先权，该申请的内容全部收录于此，以供参考。

技术领域

本发明涉及通信系统中的路由选择，更具体地说，涉及确定通过网络的多个节点的路径，以便进行具有保证服务水平的路由选择。

背景技术

在诸如因特网之类基于分组的通信网络中，称为分组流的每个数据分组流通过网络路径经由网络从源被传送到目的地。每个网络路径由一组节点定义，所述一组节点由一组链路互连。节点可包括一个或多个路由器，路由器是网络中处理计算机之间的数据传送的设备。

通信系统可被这样构成，以致不同大小的网络被互连，并且另一方面或者另外可包括其中互连同样大小的多个网络的一个或多个对等结构。分组网络可通过称为入口点和出口点的节点与另一分组网络连接。术语入口点和出口点指的是连接到另一分组网络的分组网络的一个节点，或者另一方面，这些术语指的是另一分组网络的连接节点。具有在两个或者更多的分组网络之间传送分组的较高能力的分组网络被称为“基干”网。

图1表示现有技术的具有通过能够实现分组网络102-104之间的通信的链路101互连的节点n1～n9的基干网100。基干网100的入口点之一是节点n1，节点n1从源(即，分组网络102)接收分组，基干网的出口点之一是节点n4，节点n4把分组传送给目的地(即，分组网络104)。基干网100可支持内部路由协议，从而分发网络布局信息，并且根据通过节点n1～n9的最佳努力路由选择(best-effort routing)(例如，基于目的地的最短路径路由选择)在入口点和出口点之间路由分组。可采用集中式网络管理系统105来(i)供给(provision)通过基干网100的虚电路或者分组流；(ii)监视链路101的容量和利用率；和(iii)协调供给的路径的计算和安装。每个节点使用转发表来把每个接收的分组转发给逼近其目的地的下一节点。另外，集中式网络管理系统105也可被用于收集和分发网络布局信息。

内部路由选择协议被用于确定沿着通过基干网的节点的路径，在源和目的地对之间的分组的转发。基于根据内部路由选择协议或者以明确的路线规定建立的路径构成的转发表，一个节点接收的分组被转发给其它节点。内部路由选择协议还可规定节点之间网络布局和链路状态信息(“网络布局信息”)的交换，以允许节点构成对应的转发表。另外，一些路由选择协议把链路“成本”与节点之间的每条链路联系起来。这种链路成本可与例如平均链路利用率或链路产生的收益，以及网络中的链路重要性相关。当在路由器之间交换链路状态信息或者链路带宽(例如连通性或可用带宽)时，网络中的每个节点具有网络布局的完整描述。一种广泛使用的，用于“最佳努力”路由选择的内部路由选择协议的例子是开放式最短路径优先(OSPF)协议。

除了提供连通性之外，路由选择协议还能够实现通信量管理。例如，多协议标记交换(MPLS)标准允许基干网中的这种路由选择协议。MPLS标准可被用于具有虚电路(分组流)的网络，所述虚电路(分组流)具有供给的服务水平(也称为保证服务质量(QoS))。

供给服务水平可以是，例如通过基干网的分组流的路径的保证最小带宽。入口点和出口点之间具有保证服务水平的该路径可被称为网络隧道路径(NTP)。本领域的技术人员显然知道，对不同类型的网络存在NTP的特定实现。作为NTP的例子，可为TCP/IP网络中的分组流建立虚电路，可为异步传输模式(ATM)网络中的信元建立虚电路，对MPLS网络中的分组可建立标记交换路径(LSP)。一旦关于NTP的路由选择被计算，信令协议，例如RSVP用于IP和MPLS网络的预留协议)或LDP(用于MPLS网络的标记分发协议)的分组就可被用于保留链路带宽，并建立NTP。NTP可被提供为沿着基干网的节点之间的特定路径的明确路线，即当为分组流提供NTP时，NTP的入口点和出口点之间的所有中间节点可被指定，分组流的每个分组经过所述所有中间节点。

在MPLS网络中，当在入口点收到分组时，通过把附加信息附到分组上，或者由该分组形成附加信息，分组被封装。称为标记的附加信息被基干网的路由器用于转发分组。图2表示具有附到分组202的标记201的封装分组200。该标记概述分组报头中的信息。该概述可基于报头字段，并且包括识别入口点的地址的起点(源)地址字段(o)210，和识别出口点的地址的终点(目的地)地址字段(t)211。在一些情况下，标记可以只是识别或者以其它方式与接收分组的报头中的特定起点和终点地址字段相关的指示符。标记还包括一个或多个服务水平字段(bd)212。服务水平字段212识别虚电路的所需服务水平(称为“需求”)，例如所需的最小带宽。在一些网络中，从标记本身间接地表示服务水平字段。其它字段213可被包括在标记201中，例如MPLS标准版本，内部路由选择协议版本，最大延迟，或者其它类型的服务水平参数。另一方面，标记201可被插入分组202的分组报头(PH)214中，因此图2中所示的字段的顺序只是示范性的。基干网可采用标记来把具有类似LSP的封装分组归并到多个类别中(等价类别)，可采用转发等价类别的方法来简化LSP的路由选择的计算。

为了产生转发表，计算通过网络节点的一组优选路径，并且可使用权重来计算该组优选路径。每个优选路径具有节点之间的最小总权重(路径的总权重是路径中所有链路的权重的总和)，这被用在本领域中称为最短路径路由选择的技术中。所得到的一组优选路径可利用最短路径树(SPT)定义。具有路由选择信息(例如源-目的地对，源端口，和目的地端口)的转发表由STP产生。路由选择信息随后被用于沿着SPT的最短路径，把接收的分组转发给其目的地。可利用诸如在E.Dijkstra的“A Note：Two Problems In Connection With Graphs”，Numerical Mathematics，vol.1，1959，pp.269-271中说明的Dijkstra算法之类的算法计算SPT，该文献的教导在此引为参考。

路由器采用的产生LSP的路由选择的常见最短路径路由选择算法是最少中继段(min-hop)算法。在最少中继段算法中，每个路由器计算入口点和出口点之间分组流的通过基干网的路径。每个路由器以最少数目的可行链路(“中继段”)(可行链路是具有路由分组流的足够容量的链路)，构成从入口点到出口点路由分组流的路径。现有技术的路由选择方案，例如最短路径路由选择，只根据目的地地址转发分组，并且只使用静态的与通信量特征无关的链路权重来计算路由选择表的路径。某些成对的入口点和出口点之间的最短路径上的一些链路可能被拥塞，而备选路径上的其它链路可能利用不足。

诸如RSVP或LDP之类的信令机制可被用于为分组流保留和建立通过网络的连接。信令机制可规定遍历基干网的LSP的服务质量属性。由多个LSP的最短路径路由选择导致的链路拥塞可能导致信令机制的保留请求的拒绝，即使在只是稍长的备选的利用不足的路径中存在LSP的足够服务水平(服务质量保证)。当采用最短路径路由选择时，可用网络资源并不总是被有效利用。

边界网关协议(BGP)是一种自治系统间路由选择协议。自治系统是在公共管理之下，并且具有公共路由选择策略的网络或一组网络。自治系统间路由选择协议被用于在自治系统之间路由数据。BGP被用于为因特网交换路由选择信息，是在因特网服务提供者(ISP)之间使用的协议。客户网络，例如大学和公司，一般采用内部网关协议(IGP)，例如路由信息协议(RIP)或开放式最短路径优先(OSPF)用于与它们的网络的路由选择信息的交换。客户连接到ISP，ISP使用BGP交换客户和ISP路线。BGP可用在自治系统之间，或者服务提供者可使用BGP在自治系统内交换路线。

网络中的主要问题是BGP引起的通信量变化。由于各种原因，会发生外部网络通信量波动。例如，就与几个其它提供者交换通信量的大型因特网服务提供者来说，电信公司之间的通信量交换一般由长时间内的总的通信量，可能还有峰值速率极限(通常仅仅由物理链路容量确定)规定。在入口点进入到各个网络出口点的通信量的实际分布可能事先不知道，并且能够随着时间而变化。这是因为所述分布由许多因素，例如到不同目的地前缀的通信量的固有变化，和由电信公司本地产生的或者由电信公司不能控制的其它自治系统中发生的变化产生的路由选择改变来决定。通信量分布的固有变化可由许多因素引起，例如响应特殊事件的突如其来的拥塞的出现。能够影响通信量分布的本地路由选择变化的一个例子是与“热土豆”路由选择组合的IGP权重变化，它能够改变预定给一组前缀的通信量否则会选择的网络入口点。“热土豆”路由选择是一种形式的路由选择，其中网络的节点没有在把分组转移给它们最终的预定目的地之前保存分组的任何缓存器，以致被路由的每个分组持续不断地被传送，直到它到达其最终目的地为止。从而，分组像“热土豆”似地跳来跳去，有时进一步远离其目的地，因为它不得不在网络内保持不断移动。另一种例子是当采用多出口标识(MED)时BGP的变化。MED(也称为路线的“外部量度”)是关于到具有多个入口点的自治系统的优选路径对外部邻居的建议。在本地路由选择变化受电信公司控制，从而只在规划的情况下改变通信量模式时，当其它自治系统中的路由选择变化影响下游的自治系统时，会发生不可预测的通信量变化。由于热土豆路由选择的广泛使用，自治系统中的IGP权重改变(它可起因于加入的新链路，维护，通信量工程等)会导致通信量模式的显著变化。IGP成本的改变会影响相当比例的前缀的BGP路线，受影响的前缀会导致相当比例的通信量。从而，由于网络中其它地方的改变，在电信公司会发生通信量的显著变化。

应考虑高通信量可变性的另一原因在于签订对等协议的用户或公司可能不能很好地向各个地点表征他们的通信量。更容易的是只估计接收或发送的总的集合带宽。从而，最好避免不得不依赖于了解准确的通信量矩阵，改为只使用通信量矩阵的部分规范。另外，即使当已知通信量矩阵时，通常也难以检测通信量分布的改变。

网络拥塞一般起因于容量的损失(当路由器或链路发生故障时)或者起因于容量需求的增大(由通信量的巨大增大导致)。响应这些不可控制的事件，电信公司应该再三修改它们的域内路由选择以避免网络拥塞，或者事先留出足够的容量，以适应会发生的不同通信量和故障模式，而不必求助于路由选择改变。由于操作复杂性和成本的缘故，以及由于如果未正确实现改变而导致的网络不稳定性的风险，最好避免频繁的域内路由选择改变。此外，如上所述，一个自治系统中的改变会导致其它自治系统中的级联通信量改变，从而影响许多因特网路径的整体稳定性。避免大的路由选择改变的折衷是为了适应故障或不断改变的通信量模式而必须进行的大量容量的过度提供。理想地，提供者会宁愿使用几乎固定的路由选择方案，所述几乎固定的路由选择方案(i)不要求配置参数的依赖于通信量的动态修改，(ii)使发生故障后的动态容量再分配降至最小，和(iii)过度提供需求最小。

通信量矩阵事先未知的另一种应用是向企业客户提供基于网络的虚拟专用网络(VPN)服务。这里，与每个客户的服务水平协议规定属于VPN的每个站点能够发送或接收的通信量的数量。在这种情况下，用户不知道它们的通信量度量，只向电信公司指定总的通信量容量和峰值速率。电信公司的任务是把所有提供的VPN通信量传送给网络，并运送该通信量，而不引入过多的延迟。从每个站点到其它站点的实际通信分布通常未知，并且会随着时刻而变化。电信公司网络的任务是运送所有提供的VPN通信量，而不致在通信量模式改变时或者在节点或链路发生故障时，出现网络拥塞。

用于网格计算的网络提供另一种情形，其中通信量变化可以是极度的，通信量矩阵事先未知。在网格计算中，复杂的计算任务被划分到不同的计算节点中，所述不同的计算节点可被地理分布，并由网络连接。网格计算节点中的通信模式极度不可预测，并且还能够经历高的猝发传输率。由于通信量矩阵事先未知，一种选择是在底层网络上动态保留容量，但是对于许多网格计算应用来说，这种方法过慢。由于目的地的高可变性和通信量的突发性质，过度提供网络容量导致多数时间容量利用率极差。

当通信量模式不可控制地改变时，为了提供良好的服务，电信公司应快速并且再生地修改他们的域内路由选择以避免网络拥塞，或者事先留出足够的容量以适应可能发生的不同通信量模式，而不求助于路由选择改变。由于(i)操作复杂性和成本，和(ii)如果未正确实现链路度量改变，那么存在网络不稳定性的风险，服务提供者宁愿避免频率的域内路由选择改变。此外，BGP应用中一个自治系统中的改变会导致其它自治系统中级联的通信量改变，从而影响许多因特网路径的整体稳定性。避免路由选择改变的折衷是为了在保持路由选择固定不变的时候，适应不断改变的通信量模式而可进行的大量容量的过度提供。理想地，提供者会愿意使用固定的路由选择方案，该固定的路由选择方案不要求配置参数的取决于通信量的动态修改，并且就其容量要求来说是极度节俭的。

此外，在基于光纤的IP传输网络(OTN)中，路由器通过由一般比IP路由器端口廉价的光交叉连接(OXC)组成的可重新配置的交换光纤基干网，或者说OTN连接。通过利用波分多路复用(WDM)链路，以网格布局互连OXC。由这种OXC组成的核心光纤基干网在光纤层接管交换，修饰和恢复的功能。由于IP通信量在光纤层电路(称为“光路”)上传送，因此渡越通信量的路由器端口的旁路产生将通过在IP-over-OTN中的光纤基干网上互连IP路由器收获的巨大的经济规模的基础。通过把渡越通信量从路由器转移给光纤交换机，随着不断增大的通信量升级路由器存在点(POP)配置的要求被降至最小，因为由于和路由器相比，光纤交换机的端口数目一般被增大，光纤交换机更可缩放。在IP-over-OTN体系结构中，路由器线路卡一般比光纤交换机卡昂贵，从而，一般通过主要把通信量保持在光纤层中，减少网络成本。另外，由于光纤交换机一般比路由器更可靠，因此它们的体系结构一般更稳健和可靠。由于路由器通过交换光纤基干网互连，路由选择过程妥善处理把通信量保持在光纤层和把中间路由器用于分组修饰之间的关系，以便实现数据通信量的有效统计多路复用。

对于许多网络，例如多协议标记交换(MPLS)网络和光纤网格网络来说，具有快速恢复能力的带宽保证路径的动态提供是一种理想的网络服务特征。在光纤网络中，快速恢复也是合乎需要的，因为光纤传输网络运送各种通信量类型，每种通信量具有不同的严格的可靠性要求。在MPLS网络中，类似的快速恢复能力可被用于为诸如分包语音，关键性虚拟专用网络(VPN)通信量，或者其它服务质量(QoS)保证的服务提供所需的可靠性。

网络中的连接可在路径层或链路层受保护。对于链路恢复(也称为本地恢复或快速恢复)来说，连接的每个链路由排除正被保护的链路的一组一个或多个预先提供的便道路径保护。当链路发生故障时，故障链路上的通信量被转换到便道路径。从而，链路恢复提供绕过链路故障进行路由的本地机构。在路径恢复中，连接的主要或者工作路径由从源到目的地的“不同的”备用路径保护。当工作路径上的任意资源发生故障时，源节点把通信量转换到备用路径。链路恢复一般比路径恢复更快地恢复服务，因为恢复被本地激活，并且不同于链路恢复，故障信息不必通过网络传回给源。

服务恢复是光纤网络的一个重要要求。如果网络部件，例如节点(光纤交换机)或者链路(光纤)发生故障，那么故障导致一个或多个特定波长路径发生故障，必须在很短的时间间隔(例如50毫秒)内利用备选路径恢复受影响的通信量流。为了获得相当快速的恢复时间，对于每个波长路径，提供(provisioning)识别通过网络的两条路径：主要(现用)路径和辅助(备用)路径。备用路径是与主要路径分开的链路(现用路径和备用链路并不共用链路)或者节点(现用路径和备用链路并不共用节点或链路)。备用路径中的链路的容量可被专门分配给对应的主要路径(例如波长)，或者对于网络带宽利用效率来说，根据所需恢复的类型，可在不同主要路径的备用路径的链路之间共享所述容量。光纤网络容量设计一般计及对可能存在共享的路线分离的辅助路径的恢复要求。

只有知道因特网服务提供者应使用哪种网络路由选择方法，才能实现现有的高度动态并且不断改变的通信量环境中的稳健网络路由选择，以便(i)在用户希望向不同的目的地发送的通信量不可预测的时候，接纳要求“良好”服务的用户，(ii)使网络中需要进行的“过度提供”的数量降至最小，以使“最佳努力连网更好”，而不必求助于复杂的通信量预测和管理机构，和(iii)以主要静态的路由选择配置有效地运转网络，而不存在动态路由选择调整，从而避免网络的入口点和出口点之间通信量流的显著改变而导致的拥塞。实现这些目标一直困难，导致网络被过多的过度提供容量，以便避免实现使网络路由选择适应变化的通信量要求的通信量管理方案的管理复杂性。

发明内容

本发明提供一种以用修改的路由选择方案替换电信公司(carrier)领域内的最短路径内部网关协议(IGP)路由选择的思想为基础的方案，所述修改的路由选择方案在保证通信量经过也在电信公司的领域中的一个或多个预定中间节点之后，把通信量路由给目的地(中间节点的指派在流量层(flow level)完成，以避免分组重新排序问题)。仍然根据边界网关协议(BGP)确定的自治系统路径和诸如热土豆路由选择之类的辅助电信公司路由选择策略选择出口节点。根据本发明的一个实施例的方案把直接最短路径的IGP路径选择改为通过一个或多个先验指派(a priori-assigned)的中间节点的一条路径。在MPLS网络中，可利用入口节点和根据指定的概率向其分配流量的选择的一组一个或多个中间节点之间的预先配置的一组MPLS LSP，完成该通过一个或多个预定中间节点的路由选择。在纯IP网络中，可通过首先把分组经隧道发送给一个或多个预定的中间节点来实现该路由选择。这种具有一个或多个中间节点的预定选择的路由选择足以处理允许的，受边-链路容量约束条件限制的所有通信量模式，另外提供避免路由器和光纤层链路故障的保护。此外，当通信量矩阵变化时，并不需要修改路由选择，并且该方案有效地利用带宽。

本发明还提供一种路由选择方案，当被应用于IP-over-OTN或其它电路交换网络时，能够在光纤层中路由分组，同时分组只在一个中间路由器上修饰，并且能够向分组交换的理想的统计多路复用性质提供高度可变的通信量。

在一个实施例中，本发明提供一种通过由链路互连，并且具有至少一个入口点和至少一个出口点的节点的网络路由数据的方法，所述方法包括下述步骤：(a)接收对用于在入口点和出口点之间路由数据的具有服务要求的路径的请求；(b)选择入口点和出口点之间的一组一个或多个中间节点；(c)根据所述网络的带宽，确定从入口点发送给所述一组一个或多个中间节点中的每个节点的数据的相应分数(fraction)；(d)把确定的相应分数的数据从入口点路由给所述一组一个或多个中间节点中的每个节点；和(e)把数据从所述一组一个或多个中间节点中的每个节点路由给出口点。

在另一实施例中，本发明提供一种通过由链路互连，并且具有至少一个入口点和一个出口点的节点的网络路由数据的设备，所述设备包括输入模块，处理模块和路由器。输入模块适合于接收：(i)对用于在入口点和出口点之间路由数据的具有服务要求的路径的请求；和(ii)与所述请求相关的数据。处理模块适合于确定所述请求的路径，其中处理模块通过(a)选择入口点和出口点之间的一组一个或多个中间节点；和(b)根据所述网络的带宽，确定从入口点发送给所述一组一个或多个中间节点中的每个节点的数据的相应分数，确定所述路径。路由器适合于根据请求的路径，把分组从所述输入模块传送给路由器的输出模块，其中路由器适合于(c)把确定的相应分数的数据从入口点路由给所述一组一个或多个中间节点中的每个节点；和(d)把数据从所述一组一个或多个中间节点中的每个节点路由给出口点。

在另一实施例中，本发明提供一种保存有多个指令的计算机可读介质，所述多个指令包括当被处理器执行时，使处理器实现通过由链路互连，并且具有至少一个入口点和至少一个出口点的节点的网络路由数据的方法的指令，所述方法包括下述步骤：(a)接收对用于在入口点和出口点之间路由数据的具有服务要求的路径的请求；(b)选择入口点和出口点之间的一组一个或多个中间节点；(c)根据所述网络的带宽，确定从入口点发送给所述一组一个或多个中间节点中的每个节点的数据的相应分数；(d)把确定的相应分数的数据从入口点路由给所述一组一个或多个中间节点中的每个节点；和(e)把数据从所述一组一个或多个中间节点中的每个节点路由给出口点。

在另一实施例中，本发明提供一种通过由链路互连，并且具有至少一个入口点和至少一个出口点的节点的网络路由数据的系统，所述系统包括接收(i)对用于在入口点和出口点之间路由数据的具有服务要求的路径的请求；和(ii)与所述请求相关的数据。所述系统还包括通过(a)选择入口点和出口点之间的一组一个或多个中间节点；和(b)根据所述网络的带宽，确定从入口点发送给所述一组一个或多个中间节点中的每个节点的数据的相应分数，确定请求的路径的装置。所述系统还包括通过(c)把确定的相应分数的数据从入口点发送给所述一组一个或多个中间节点中的每个节点；和(d)把数据从所述一组一个或多个中间节点中的每个节点发送给出口点，根据请求的路径传送分组的装置。

附图说明

图1表示具有通过允许其它分组网络之间的通信的链路互连的节点的例证基干网；

图2表示图1的基干网采用的把分组从入口点路由到出口点的封装分组；

图3表示采用根据本发明的一个实施例的服务水平保证的路由选择方法路由选择标记交换路径的互连节点的网络；

图4表示根据本发明的一个实施例的例证两阶段路由选择方案的物理和逻辑图；

图5是表示根据本发明的一个实施例的例证路由选择方法的流程图；

图6表示根据本发明的一个实施例的例证原始对偶线性程序的一个步骤；

图7表示根据本发明的一个实施例的算法中的行和和列和的路由选择保证的示意图；

图8表示为本发明的例证实现的模拟采用的，只代表电信公司基干网的网络布局的具有28条双向链路的例证15节点网络；

图9是比较图8的例证网络的比例系数的模拟结果图；

图10是比较例证的20节点网络的比较系数的模拟结果图。

具体实施方式

图3表示采用根据本发明的服务水平保证的路由选择方法的例证实现的互连节点n1～n10的网络300。路由选择方法为对网络隧道路径，例如标记交换路径(LSP)的请求确定通过网络300的路径。节点n1～n10均包括根据由按照本发明的路由选择方法确定的路径构成的转发表，转发分组的一个或多个路由器。例证的路由选择方法分两阶段路由被请求LSP的分组，从而输入的通信量首先以预定的比例被路由给一组的一个或多个中间节点，随后从中间节点路由给最终目的地，以便网络吞吐量达到最大。这种路由选择方法可能不必沿着网络内最短的路径，或者最小数目的中断段路由被请求LSP的分组。

虽然这里关于采用MPLS标准和具有相关服务水平的路径请求，例如LSP请求的网络说明了本发明的例证实施例，不过本发明并不局限于此。本发明还可用在其它语境中，例如收到关于入口点和出口点之间具有保证的服务水平的网络隧道路径(NTP)的请求的语境中。NTP可以是例如用于TCP/IP网络中分组流的虚拟电路，异步传输模式(ATM)网络中信元的连接，和LSP(用于MPLS网络中的分组)。在通过由OXC组成的可重新配置的交换光纤基干网连接的路由器的语境中，本发明也在IP-over-OTN(或者其它线路交换网络)中具有特殊应用，从而核心光纤基干网在光纤层接管交换，修饰和恢复的功能。

互连节点的网络，例如网络300被定义为G(N，E)，N是该组节点n1～n10，E是互连节点的一组链路(弧)或(有向)边缘。虽然在这里描述的例证实施例中，可用资源，例如服务水平的值是链路或路径的带宽容量，不过另一方面或者另外，其它实施例中的服务水平值可包括一个或多个链路参数，例如延迟，分组丢失的概率，收益，或者其它服务质量参数。本领域中已知，这些各种服务水平值的一个或多个可由称为有效带宽的数量表示。该组E个链路中的链路e_ij具有两个下标，i和j(0＜i，j≤N)，表示由链路e_ij连接的节点n_i和n_j。在不丧失一般性的情况下，每个链路e_ij是定向的(分组流从节点n_i到n_j)。

图3中的源S₁、S₂和S₃是共同向节点n1、n2、n3、n5和n9中的路由器提供分组流的分组网络，这些节点是连接到外部网络，例如其它电信公司的潜在入口点。类似地，目的地D₁、D₂和D₃是共同从节点n3、n4、n8、n9和n10中的路由器接收分组流的分组网络，这些节点是连接到外部网络的潜在出口点。应认识到网络中的任意节点可以是入口点和/或出口点。源S₁、S₂和S₃与入口点连接，而目的地D₁、D₂和D₃与出口点连接。源-目的地对被定义为(S₁，D₁)、(S₁，D₂)、(S₁，D₃)、(S₂，D₁)、(S₂，D₂)、(S₂，D₃)、(S₃，D₁)、(S₃，D₂)、(S₃，D₃)，每个节点可支持一个或多个源和/或一个或多个目的地。节点n1～n10还具有或者可以访问当前网络布局和链路状态信息(下面称为“网络布局”)，利用分布式协议(例如借助遵守OSPF协议的控制分组)，可通过网络提供和分发所述当前网络布局和链路状态信息。

源S₁、S₂和S₃产生网络300中的新的或者当前提供的LSP的分组，所述分组包括识别入口-出口点对的字段(例如源S₁、S₂或S₃的地址，和目的地D₁、D₂或D₃的地址)。RSVP或LDP的信令分组可被用于向网络部件(例如路由器或节点)传送服务质量(QoS)属性或保证，例如带宽；但是，LSP的分组还可包括对应于QoS属性或保证的一个或多个服务水平参数的值。通过网络300传送的LSP的这些分组可遵守MPLS标准，并且可具有和图2中所示并参考图2说明的类似的格式。

对于图3中所示的网络300，存在九个潜在的入口-出口点对(源-目的地对)。对于下面的说明，互连节点n_i和n_j的每个链路(i，j)(也称为e_ij)具有相关的可用容量u_ij(或u_e)，称为剩余带宽。链路的剩余带宽u_e是链路的总带宽和当前分配给该链路的LSP的带宽需求的总和之间的差值。网络可交换关于链路的剩余容量的信息(例如在QoS最短路径优先(QoSPF)网络中)，所述信息可被用于路线的分布式计算。剩余带宽通常用例如kbit/sec或Mbits/sec为表示，或者表示成链路的总容量的百分率。互连节点n_i和n_j的每个链路(i，j)还具有相关的链路成本c_ij(或c_e)，即，对应于特定链路的相对利用率，重要性或其它成本的相关标量权重。链路成本也称为特定入口-出口点对的标量权重。链路成本可被分配给特定的链路，允许路由选择算法支持或不支持通过特定链路的路由选择，由于例如延迟，提供带宽的成本，其它通信量工程考虑，或者其它物理链路层考虑的缘故。

一般来说，请求到达网络300，从而提供和路由具有请求的服务水平bd(“需求”bd)的入口点o和出口点t之间的路径路由。对于图3例证网络，这可以是提供具有请求带宽bd Mb/sec的源-目的地对，例如(S₁，D₁)之间的路径的LSP或其它形式的NTP请求。在事先不知道未来LSP请求对带宽的需求的特性的情况下，LSP请求可一次一个地到达。另外，(i)QoS属性或保证的特性，(ii)连接到达，保持时间或脱离，和(iii)其它通信量工程信息的先验知识不一定是可得到的。需求bd可以是“等价”或“有效”带宽值，因为分组流的分组可能表现具有不断变化的带宽需要的随机过程。本领域已知，服务水平(例如QoS)属性或要求可被转换成等价或有效带宽值。等价或有效带宽值是接近于基于例如峰值和平均分组速率，到达和保持时间，和连接持续时间的随机变量的确定值。

根据本发明的路由选择方法评估和确定沿着入口-出口点对之间，穿过网络的一个或多个路径的LSP的路线。集合P是包括在网络G(N，E)中的一组特定(特异)的节点入口-出口点对，它们是潜在的源-目的地对(S₁，D₁)，(S₁，D₂)，...，(S₃，D₃)。集合P的元素被表示成(s，d)(即，(s，d)∈P，这里s和d分别对应于源网络和目的地网络。在元素(s，d)之间可提供多个LSP。

给网络300的LSP请求可通过集中式网络管理系统(图3中未示出)实现，或者由根据分布式协议提供给网络300的节点n1～n10的控制消息实现。集中式网络管理系统和/或每个网络路由器实现确定对应于被请求的LSP，将在网络中提供的路径的关于LSP请求的例证路由选择方法。集中式网络管理系统和/或每个网络路由器进行的提供允许RSVP控制(例如RSVP信令协议的QoS请求)建立具有例如需求的带宽或其它类型的服务水平的一个或多个连接(分组流)。

节点-弧关联矩阵M被定义为(n×e)矩阵(这里n等于集合N的元素的数目，e等于集合E的元素的数目)，其中每行对应于集合N的一个不同节点n，每列对应于集合E的一个不同链路e。对于节点n_i和n_j之间的对应链路e_ij，每列具有两个非零项(i，j)。对应于链路e_ij的列在行i中具有“+1”值，在行j中具有“-1”值，在对应于所有其它行的每个位置中具有“0”值。

进入(或离开)网络中的入口(或出口)节点的通信量的总量由位于该节点的所有外部入口(或出口)链路(例如到客户网络或者其它电信公司的线路卡)的总容量限制。对于任意指定节点i，离开节点i的通信量(例如带宽或其它服务水平)的总量的上限为R_i，进入节点i的通信量(例如带宽或其它服务水平)的总量的上限为C_i。根据诸如物理位于路由器的机壳内的硬件的最大容量之类的因素模拟的这些链路容量限度约束网络中的通信量的点对点矩阵。这些约束可能是网络将运行的通信量的唯一已知方面，了解这些等同于了解对通信量矩阵的行和限度(row sum bound)及列和限度，即，最大的可能行和指示最大的可能输出通信量，最大的可能列和指示最大的可能输入通信量。因此，网络的任意允许的通信量矩阵T＝<t_ij>遵守下面的等式(1)和(2)，其中T是(n×n)矩阵(其中n是节点的数目)，第(i，j)项代表从节点i到节点j的通信量：

$>over>>\Sigma >>i>:>i>=>1>>n>>>t>ij>>=>R>,ver>>>\forall >i>>17>>\in >N>>>，and (1)$

$>over>>\Sigma >>j>:>j>\ne >i>>n>>>t>ji>>=>>C>i>>->->\forall >i>\in >N>>> (2)$

考虑上面的等式(1)和(2)中的等式(与≤相反)就足够了，因为通过把矩阵T″和非负(非对角)项相加，其任意和或列相加到小于给定限度的任意矩阵T′∈T(R，C)可被变换成矩阵T＝T′+T″∈T(R，C)。T(R，C)代表所有可能的通信量矩阵的集合。从而，给T定路线的任意路由选择方案也能给T′定路线。

对于给定的R_i和C_i值，仅由它们的行和及列行规定的所有这种矩阵的集合T(R，C)可由下面的等式(3)表示：

应注意通信量分布T可以是T(R，C)中的任意矩阵，并且可随着时间变化。在根据本发明的某些实施例的路由选择体系结构中，关于T需要做出的唯一假设最好是它只由行和限度及列和限度规定。因此，根据本发明的一个实施例的路由选择策略最好(i)应允许路由T(R，C)中的每个矩阵，(ii)应不需要现有连接的重新配置，即应不在意通信量矩阵T中的变化，只要它属于T(R，C)，和(iii)应是带宽高效的，即，不应比提供从节点i到节点j的需求的min(R_i，C_j)量的常规策略使用更多的带宽。

规定VPN的带宽要求的方法的一种已知模型是在N.G.Duffield，P.Goyal，A.G.Greenberg，P.P.Mishra，K.K.Ramakrishnan，J.E.van derMerwe的“A flexible model for resource management in virtualprivate network”，ACM SIGCOMM 1999，August 1999中说明的软管模型，该文献的教导在此引为参考。在该模型中，通信量矩阵只被部分规定，从而对于每个VPN端点i，只规定R_i和C_i，R_i是在任意时候，i将送入网络中的通信量的最大总带宽，C_i是在任意时候，i从网络接收的通信量的最大总带宽。为VPN保留的网络容量应足以满足与R_i和C_i值一致的每种可能的通信量模式。

与本发明的某些实施例一致的路由选择方案允许网络满足任意(并且可能快速变化的)通信量要求，而不需要复杂的通信量工程机制或额外的网络信令。事实上，网络甚至不需要检测通信量分布方面的变化。可能需要的关于通信量的唯一了解是与位于网络边缘的外部接口连接的所有线路卡的总容量施加的限制。

现在参见图4，图中以物理视图和逻辑视图的形式图解说明了与本发明的一个实施例一致的两阶段路由选择方案。在阶段1(401)中，在任意节点i进入网络的通信量的预定一部分α_k被分发给一个或多个中间节点k，与通信量的最终目的地无关。在阶段2(402)中，每个节点k接收预定给不同目的地的通信量，并把接收的通信量路由给相应的目的地。实现这种路由选择方案的一种方法是在节点之间形成固定带宽的隧道，其中的一些隧道运送阶段1通信量，另一些隧道运送阶段2通信量。由于这些隧道所需的带宽只取决于R和C，而不取决于通信量矩阵中的单独项，因此这种两阶段路由选择策略行得通。注意在阶段1中，α₁，α₂，...，α_n是这样的，以致等式(4)被满足：

$>sup>>\Sigma >>i>=>1>>nsup>>>\alpha >i>>=>1>->->->>(>4>)>>>>$

下面更详细地说明两阶段路由选择方法。对于具有最大输出通信量R_i的指定节点i，在阶段1中，节点i把该通信量的α_kR_i量路由给中间节点k，k∈N。从而，作为阶段1的结果的从节点i到节点k的需求为α_kR_i。在阶段1结束时，节点k已从每个节点i收到α_kR_i。注意，由于行限度的和必须等于列限度的和，因此在节点k从所有源i接收的总通信量为 $>over>>\Sigma >>i>=>1>>n>>>\alpha >k>>>R>i>>=over>>\Sigma >>j>=>1>>n>>>\alpha >k>>>C>j>>.>>>在阶段1之后在节点k接收的通信量中，预定给节点j的通信量为\alpha$_kt_ij，假定到相同目的的通信量按照预定的比例划分。从而，在阶段2中需要从节点k路由到节点j的总通信量，即从节点k到节点j的通信量需求如下面的等式(5)中所示：

$>>>\Sigma >>i>\in >N>>>>\alpha >k>>>t>ij>>=>>\alpha >k>>>C>j>>.>->->->>(>5>)>>>>$

因此，由于在阶段1中，k实质上和j相同，并且在阶段2中，k实质上是i，因此作为阶段1和2中的路由选择的结果，从节点i到节点j的总需求是(α_jR_i+α_iC_j)，这可在不知道矩阵T∈T(R，C)的情况下得到。下面的三个性质表征这种两阶段路由选择方案：

(i)路由选择不在意通信量变化。需要在阶段1和2内路由的需求并不依赖于特定的通信量矩阵T∈T(R，C)，而只依赖于约束T(即集合T(R，C))的行和限度和列和限度。

(ii)路由需求不依赖于通信量矩阵。作为阶段1和2中的路由选择结果的节点i和j之间的总需求为t_ij′＝α_jR_i+α_iC_j，并不依赖于特定矩阵T∈T(R，C)。

(iii)提供的容量被完全使用。对于每个矩阵T∈T(R，C)，路由选择方案在阶段1和2完全利用相关的点对点需求。

性质(ii)意味着通过有效地路由只取决于行和限度及列和限度，以及分配比例α₁，α₂，...，α_n，而不依赖于特定矩阵T∈T(R，C)的变换矩阵T′＝<t_ij′>，从而使路由选择方案不注意通信量分布方面的变化，该方案处理通信量矩阵T∈T(R，C)的可变性。

通过使行和限度或列和限度等于在某一节点连接外部接口的线路卡容量的总和，从而在物理层强力实施该约束，可完成遵守行和限度或列和限度的通信量分布。另一方面，区分服务(DiffServ)类控制方案(由此，进入网络的通信量被分类，可能在网络的边界被调节，并被分配给不同的行为集合体)能够对在每个入口节点进入网络的总通信量进行速率限制，并保证每个节点不被过度预约。

从而，在根据本发明的一个实施例的路由选择方法中，在阶段1内在每个源节点的路由决策并不需要任何全网络状态信息(例如，在其它对等点通信量如何变化)，并且阶段2内的路由决策只以分组目的地为基础。另外，网络能够满足任何通信量分布，只要入口/出口点不被过度预约，通过连接其它电信公司的线路卡的硬速率保证，或者通过实现对在某一节点进入网络的通信量进行速率限制的区分服务类控制方案，可避免拥塞。此外，该路由选择方案不在意通信量分布方面的任何变化并且对其是稳固的，提供端对端带宽保证不需要任何实时的网络重构。

如图5的流程图中所示，可按照下述例证方法实现根据本发明的一个实施例的路由选择体系结构：在步骤501，该方法利用在连接其它电信公司的线路卡的自治系统间对等协议和/或速率，开始计算行(或列)限度R_i(或C_i)。随后在步骤502，(利用下面将更详细说明的优化所需网络带宽的例证算法)计算通信量分配比α₁，α₂，...，α_n。随后，在步骤503，对每个节点对i，j，提供两组连接(例如MPLS LSP，IP隧道，或者光纤层电路)：一组用于从节点i到一个或多个中间节点的带宽α_jR_i的阶段1，另一组用于从一个或多个中间节点到节点j的带宽α_iC_j的阶段2。随后，在步骤504，根据阶段1和阶段2路由通信量(如上详细所述，它只需要在源节点和中间节点的本地操作)。随后，在步骤505，使用区分服务类控制机制对在每个节点进入网络的总通信量进行速率限制。随后，在步骤506，确定例如作为新的对等协议或者对现有对等协议的修改的结果，行(或列)限度R_i(或C_i)是否已改变。如果所述限度未改变，那么方法返回步骤504继续路由选择操作。如果所述限度已改变，那么在步骤507，重新优化α_i分配比，在步骤508，在返回步骤504之后，可据此调整用于在阶段1和2内路由选择的LSP(或者光纤层电路，或者IP隧道)的带宽。

在前面的方法中，属于相同端对端连接的分组可无序到达出口节点，如果通信量在相同连接内是分离的。通过在该方案的阶段1中利用按流分离(per-flow splitting)，能够避免这种情形。另外，如同下面更详细所述，通信量分流比α_i可被概括成取决于通信的源和/或目的地节点。

在具有关于入口/出口通信量的链路容量和约束R_i，C_i的网络中，最好经由某一路线路由，以使网络中任意链路的最大利用率降至最小。链路的利用率可被定义为链路上的通信量与链路容量的比值。如果λ·T(R，C)表示T(R，C)中的所有通信量矩阵的集合，同时它们的项被乘以λ，那么线性程序可被用于找出最大乘数λ(吞吐量)，以致λ·T(R，C)中的所有矩阵可被路由。

对于相对分流比，即α_i＝1/ni∈N的情况，节点i和j之间的需求为(R_i+C_j)/n，问题简化为如同在F.Shahrokhi和D.Matula的“TheMaximum Concurrent Flow Problem”，Journal ofACM，37(2)：318-334，1990中说明的最大并行流问题，该文献的教导在此引为参考。

现在说明本发明的一个实施例中的例证的基于链路流的线性规划方法，其中流量在原始问题的解答中被增大，权重以倍增方式在对应的对偶问题的解答中被更新。原始问题和对偶问题及解答可被如下表征：

1.如果原始问题具有n个变量和m个源约束条件，那么对偶问题将具有m个变量和n个源约束条件。于是，对偶问题的约束矩阵是原始问题的约束矩阵的转置矩阵。

2.在原始约束条件和对偶变量之间存在一一对应，即，对偶问题中的变量与原始问题中的不等式成对，对于原始变量和对偶约束条件来说情况类似。

3.对偶问题的目标函数由原始约束条件的右手侧确定，对于原始问题的目标函数和对偶约束条件来说情况类似。

在下面的例证线性规划方法中，已知物品(commodity)索引k，其中术语“物品”指的是源和目的地之间的流，物品k的源节点由s(k)表示，目的地节点由d(k)表示，对应于物品k的流的数量由f(k)表示。矢量x^k(e)表示网络中链路e上物品k的流的数量，Δ^-(i)和Δ⁺(i)分别表示在节点i的输入和输出边的集合。具有等式(6-7)和不等式(8)的约束条件的例证的基于链路流的线性规划方法被如下表示：

$>>max>inizeover>>\Sigma >>i>\in >N>>n>>>\alpha >i>>,>>>$

服从

$>>>\Sigma >>ee\delta >->>(>1>)>>>>>x>k>>>(>e>)>>=>>\Sigma >>e>\in >\delta >+>>(>1>)>>>>>x>k>>>(>e>)>>>>$

          i≠s(k)，d(k)，k，                   (6)

$>>>\Sigma >>e>\in >\delta >+>>(>i>)>>>>>x>k>>>(>e>)>>=>>a>>s>>(>k>)>>>>>C>>d>>(>k>)>>>>+>>a>>d>>(>k>)>>>>>R>>s>>(>k>)>>>>>>$

          i＝s(k)，k，                           (7)

$>>>\Sigma >k>>>x>k>>>(>e>)>>\le >>u>e>>\forall >e>\in >E>.>->->->>(>8>)>>>>$

上述线性程序包括两组决策变量：通信量分流比α_i和由x^k(e)表示的物品k的链路e上流的数量。注意对物品k的要求由α_s(k)C_d(k)+α_d(k)R_s(k)给出。上述线性程序的最佳解答中的α_i值由α_i^*表示，最佳目标函数值由λ^*表示，其中λ^*＝∑_iα_i^*。如果λ^*≥1，那么该问题是可行的，即，指定的需求可在网络上被路由。α_i^*值可被减少到原量的λ^*分之一，从而获得实际的分流比，可根据上述问题的解答确定沿其路由需求的明确路径。如果λ^*＜1，那么该问题是不可行的。这种情况下，通过除以系数1/λ^*，出口(或入口)约束条件R_i(C_i)可被按比例缩小，对于在给定链路容量下的路由选择来说，该问题将是可行的。另一方面，通过乘以系数1/λ^*，链路容量可被按比例放大以适应所有给定需求的路由选择。

下面说明本发明的一个实施例中的例证的基于路径流的线性规划方法，它可被用于提出快速的组合的完全多项式时间近似方案(FPTAS)算法。在下面的例子公式表示中，P_ij表示从节点i到节点j的所有路径的集合，x(P)表示路径P上的通信量。具有等式(9)和不等式(10)的约束条件的例证的基于路径流的线性规范被如下表示：

$>>max>imize>>\Sigma >>i>\in >N>>>>a>i>>,>>>$

服从

$>>>\Sigma >>P>\in >>P>ij>>>>x>>(>P>)>>=>>\alpha >j>>>R>i>>+>>\alpha >i>>>C>j>>\forall >i>,>j>\in >N>,>i>\ne >j>,>->->->>(>9>)>>>>$

$>>>\Sigma >>Pe>\in >P>>>x>>(>P>)>>\le >>u>e>>\forall >e>\in >E>->->->>(>10>)>>>>$

由于网络一般可具有指数数值的路径(就网络的规模来说)，前述(原始)线性程序可能能够具有指数数值的变量，其对偶(将在下面详细提供)能够具有指数数值的约束条件。从而，这些程序可能不是很适合在中到大规模网络上运行。不过，这样的原始/对偶公式表示可用于为该问题设计快速的全多项式时间组合算法，如下所述。

快速组合近似算法可被用于计算高达最佳目标函数值的(1+ε)倍(factor)的分流比，ε＞0。可选择ε的值，以便为解答提供所需程度的最优性。该算法最好是FPTAS方案并且运行为输入大小和1/ε的多项式的时间。由于该算法保持每一步骤的原始解答(primal solution)和对偶解答(dual solution)，因此通过计算原始目标函数值和对偶目标函数值的比值，能够估计最优性差距。

等式(9)和不等式(10)中陈述的线性程序的对偶公式表示使变量w(e)与不等式(10)中的每个链路容量约束条件相联系，使变量π_ij与等式(9)中的每个需求约束条件相联系。SP(i，j)表示在权重w(e)下的最短路径P∈P_ij，如下面的等式(11)中所示：

$>>SP>>(>i>,>j>)>>=>>min>>P>\in >>P>ij>>>>>\Sigma >>e>\in >P>>>w>>(>e>)>>->->->>(>11>)>>>>$

在简化和消除对偶变量π_ij之后，对偶线性规划可被如下表示，具有不等式(12-13)的约束条件：

$>>min>imize>>\Sigma >>e>\in >E>>>>u>e>>w>>(>e>)>>,>>>$

服从

$>>>\Sigma >>i>:>j>\ne >k>>>>R>i>>SP>>(>i>,>k>)>>+>>\Sigma >>j>:>j>\ne >k>>>>C>j>>SP>>(>k>,>j>)>>\ge >1>->->\forall >k>\in >N>,>->->->>(>12>)>>>>$

    w(e)≥0e∈E                    (13)

对于指定节点k，V(k)表示不等式(12)中约束条件的左手侧。已知权重w(e)，注意可借助两个最短路径计算，以多项式时间计算V(k)，一个最短路径计算用于节点k为根节点，并且到达所有目的地的最短路径树，另一个最短路径计算用于从所有其它节点到达节点k的反向最短路径树。

已知一组权重w(e)，当且仅当下面的不等式(14)被满足时，才存在对偶程序的可行解答：

$>>>min>>k>\in >N>>>V>>(>k>)>>\ge >1>->->->>(>14>)>>>>$

该算法开始于使初始权重w(e)等于Δ(参数Δ取决于ε并且在后面导出)。随后，重复下述步骤(1-5)，直到对偶可行性约束条件被满足为止：

(1)如图6中所示，计算其V(k)最小的节点k，从而识别链路k以及关于所有i的从节点i到节点k的路径P_i，和关于所有j的从节点k到节点j的路径Q_j。

(2)对于每个e∈E，N_P(e)被定义为P_i包含链路e的一组节点i，N_Q(e)被定义为Q_j包含链路e的一组节点j。随后利用下面的等式(15)计算分数(fraction)α：

$>>a>=>>min>>e>\in >E>>>>>u>e>>>>\Sigma >>i>\in >>N>P>>>(>e>)>>>>>R>i>>+>>\Sigma >>j>\in >>N>Q>>>(>e>)>>>>>C>j>>>>.>->->->>(>15>)>>>>$

(3)对于所有i，适量的流αR_i在路径P_i上路由，对于所有j，适量的流αC_j在路径Q_j上路由，对于所有e∈E，计算在链路e上发送的总流量Δ(e)。链路e上的流被递增Δ(e)。

(4)对于所有e∈E，权重w(e)被更新为w(e)←w(e)(1+εΔ(e)/u_e)。

(5)与节点k相关的分流比α_k被递增α。

当上述程序结束时，对偶可行性约束条件将被满足。但是，关于每个链路的原始容量约束条件会被违反，因为在该程序中采用了每一级的初始(而不是剩余)链路容量。为了纠正这一点，分流比可被均匀地按比例缩小，从而遵守容量约束条件。

下面提供可用于实现上面说明的例证方法的例证算法的伪代码。在该伪代码中，阵列flow(e)记录链路e上的通信量。变量G被初始化为0，并且只要对偶约束条件仍然未被满足，就保持小于1。在当型循环结束之后，关于每个链路e的容量约束条件被违反的系数被计算到阵列scale(e)中。最后，α_i值被除以最大容量违反系数，所得到的值被输出为最佳值。

提供与该例证算法相关的两个定义，如下所示：

定理1：如果L＝(n-1)(∑_i∈NR_i+∑_j∈NC_j)，并且L′是R_i′和C_j′的最小非零值，并且认为ε和Δ的值与下面陈述的算法的近似系数保证相关，那么对于任意给定的ε′＞0，该算法关于下述等式(16-17)计算具有在最佳值的(1+ε′)倍内的目标函数值的解答：

$>>\delta >=>>>1>+>ϵ>>>>L>\prime >>>>[>>(>1>+>ϵ>)>>>L>>L>\prime >>>]>>>1>/>ϵ>>>>>,>->->->>(>16>)>>>>$

$>>ϵ>=>1>->>1>>1>+>>ϵ>\prime >\; >>.>->->->>(>17>)>>>>$

定理2：对于选择的根据定理1提供所需的近似系数保证的任意给定ε＞0，该算法是输入大小和1/ε的多项式，即 $>>O>>(>>nm>ϵ>>>(>m>+>n>log>n>)>>>log>>1>+>c>>>>L>>L>\prime >>>)>>.>>>$

下面的例证伪代码可被用于实现上面陈述的例证算法：

  a_k←0k∈N；                                      20  w(e)←δe∈E；  flow(e)←0e∈E，  G←0；  while G＜ldo

Compute shortest path of cost SP(i，j)from i to j under link costs w(e)i，j∈N；

V(k)←∑_i∈k RSP(i，k)+∑_j∈k C_jSP(k，j)；

G←min_i∈NV(k)；

if G≥Ibreak；

Let k be the node for which g(k)is minimum；

Let P_i be the shortest path from i to k for all i；

Let Q_j be the shortest path from k to j for all j；

N_P(e)←{i：P_icontainse}for all e；

N_Q(e)←{j：Q_jcontainse}for all e；

$>>\alpha >\leftarrow >>min>>e>\in >E>>>>>u>e>>>>\Sigma >>i>\in >>N>P>>>(>e>)>>>>>R>i>>+>>\Sigma >>j>\in >>N>Q>>>(>e>)>>>>>C>j>>>>;>>>$

Send αR_i flow on path P_i for all i and αC_j flow on path Q_j for all j and compute resulting capacity usagcΔ(e)on link e for all e；

flow(e)←flow(e)+Δ(e)for all e；

w(e)←w(e)(l+εΔ(e)/u_e)for all e；

α_k←α_k+α；  end while  scale(e)←flow(e)/u_e for all e∈E；  scale_max←max_e∈Escale(e)；  a_k←a_k/scale_max for all k∈N；  Output a_k as the optimal traffic split ratios；

定理1和2的证明和基本引理如下：

已知一组对偶权重w(e)，其中D(w)表示对偶目标函数值，Γ(e)表示在所有节点k∈N内，在不等式(12)中陈述的对偶程序约束条件的左手侧的最小值，求解该对偶程序等同于找出一组权重w(e)，以致D(w)/Γ(w)被最小化。D(w)/Γ(w)的最佳目标函数值由θ表示，即θ＝min_wD(w)/Γ(w)。在当型循环(while loop)的迭代t开始时的权重函数由w_t-1表示，f_t-1是一直到迭代t-1结束时∑_j∈Nα_j(原始目标函数)的值。如上所述，L＝(n-1)(∑_i∈NR_i+∑_j∈NC_J)，L′是R_i和C_j的最小非零值。该算法在迭代N次之后结束。

引理1：在算法1≤t≤K的每个迭代t结束时，下面的不等式(17.1)被满足：

$>>\Gamma >>(>>w>t>>)>>\le >\delta Lover>>\Pi >>j>=>1>>t>>[>1>+>>ϵ>\theta >>>(>>f>j>>->>f>>j>->1>>>)>>]>>>$

                                      (17.1)

证明：V(k)最小的节点为k＝k，在迭代t内沿其的流量被增大的对应路径由P_i，Q_j表示，如上定义的那样。权重被更新为w_t(e)＝w_t-1(e)(1+εΔ(e)/u_e)e∈E，其中Δ(e)是在迭代t内在链路e上发送的总流量。利用它，可如下面的等式(17.2)中陈述的那样得到D(w_t)：

$>>D>>(>>w>t>>)>>=>>\Sigma >>e>\in >E>>>>u>e>>>w>t>>>(>e>)>>>>$

$>>=>>\Sigma >>c>\in >E>>>>u>e>>>w>>t>->1>>>>(>e>)>>+>ϵ>>\Sigma >>e>\in >E>>>\Delta >>(>e>)>>>w>>t>->1>>>>(>e>)>>>>$

$>>=>D>>(>>w>>t>->1>>>)>>+>ϵ>>\Sigma >>e>\in >E>>>>w>>t>->1>>>>(>e>)>>[>>\Sigma >>i>\in >>N>P>>>(>e>)>>>>\alpha >>R>i>>+>>\Sigma >>j>\in >>N>Q>>>(>ϵ>)>>>>\alpha >>C>j>>]>>>$

$>>=>D>>(>>w>>t>->1>>>)>>+>ϵ\alpha >[>>\Sigma >i>>>R>i>>>\Sigma >>e>\in >>P>i>>>>>w>>t>->1>>>>(>e>)>>+>>\Sigma >j>>>C>j>>>\Sigma >>e>\in >Q>>>>w>>t>->1>>>>(>e>)>>]>>>$

$>>=>D>>(>>w>>t>->1>>>)>>+>ϵ\alpha \Gamma >>(>>w>>t>->1>>>)>>.>->->->>(>17.2>)>>>>$

通过下至第一次迭代利用上面关于每次迭代导出的等式，D(w_t)可被定义成如下面的等式(17.3)中所示：

$>>D>>(>>w>t>>)>>=>D>>(>>w>0>>)>>+>ϵover>>\Sigma >>j>=>1>>t>>>(>>f>j>>->>f>>j>->1>>>)>>\Gamma >>(>>w>>j>->1>>>)>>->->->>(>17>.>3>)>>>>$

现在考虑权重函数w_t-w₀，已知D(w_t-w₀)＝D(w_t)-D(w₀)，并且Γ(w₀)≤∑_i(n-1)δR_i+∑_j(n-1)δC_j＝δL，因为任意路径P_i，Q_j在长度方面最多为n-1个中继段。从而，Γ(w_t-w₀)≥Γ(w_t)-δL。由于θ是最佳对偶目标函数值，因此下面的不等式(17.4-17.5)成立：

$>>0>\le >>>D>>(>>w>t>>->>w>0>>)>>>>\Gamma >>(>>w>t>>->>w>0>>)>>>>\le >>>D>>(>>w>t>>)>>->D>>(>>w>0>>)>>>>\Gamma >>(>>w>t>>)>>->\delta L>>>,>->->->>(>17.4>)>>>>$

D(w_t)-D(w₀)≥θ(Γ(w_t)-δL).                     (17.5)

通过结合不等式(17.5)和等式(17.3)，可得到下面的不等式(17.6)：

$>>\Gamma >>(>>w>t>>)>>\le >\delta L>+>>ϵ>\theta >over>>\Sigma >>j>=>1>>t>>>(>>f>j>>->>f>>j>->1>>>)>>\Gamma >>(>>w>>j>->1>>>)>>.>->->->>(>17.6>)>>>>$

现在利用不等式(17.6)和关于迭代数目的数学归纳，可证明引理1中的性质。注意归纳基本情况(迭代t＝1)成立，因为w₀(e)＝δe∈E并且Γ(w₀)≤δL。现在，能够估计算法结束时，原始解答中的目标函数f_K需要被缩放的系数，以便保证链路容量约束条件不被违反。

引理2：当算法结束时，为了保证原始可行性，原始解答应被缩放(最多)为下述值的系数：

$>>>log>>1>+>ϵ>>>>>1>+>ϵ>>>\delta >>L>\prime >>>>.>>>$

证明：考虑任何链路e及其相关权重w(e)，当流量在边e上被增大时，w(e)的值被更新。链路e上(每次迭代的)流量增大的序列为Δ₁，Δ₂，...Δ_r，这里r≤K。在链路e上发送的总流量超过其容量k倍，即， $>sup>>\Sigma >>i>=>1>>rsup>>>\Delta >t>>=>k>>u>e>>.>>>由于当\Gamma (w)\ge 1时，该算法结束，并且由于在每次迭代之后，对偶权重最多被更新1+\epsilon 倍，从而\Gamma (w$_K)≤1+ε。注意，紧接在上面提及的每次增大之前，具到至少L′系数的权重w(e)是Γ(w)的求和分量之一。从而，L′w_K(e，f)≤1+ε，w_K(e，f)的值可由下面的等式(17.7)给出：

$>>>w>K>>>(>e>,>f>)>>=>\delta over>>\Pi >>t>=>1>>r>>>(>1>+>>\Delta t>>u>e>>>ϵ>)>>.>->->->>(>17.7>)>>>>$

利用(1+βx)≥(1+x)^βx≥0和0≤β≤1的事实，并设置x＝ε，β＝(Δ_t/u_e)≤1，下面的不等式(17.8-17.9)成立：

$>>>>1>+>ϵ>>>L>\prime >>>\ge >>w>K>>>(>e>,>f>)>>\ge >\delta over>>\Pi >>t>=>1>>r>>>>(>1>+>ϵ>)>>>>\Delta >t>>/>>u>e>>>>>>$

$>>\ge >\delta >>(>1>+>ϵ>)>>sup>>\Sigma >>t>=>1>>rsup>>>>\Delta >t>>/>>u>e>>>>>>$

$>>\ge >\delta >>>(>1>+>ϵ>)>>\kappa >>.>->->->>(>17.8>)>>>>$

$>>\kappa >\le >>log>>1>+>ϵ>>>>>1>+>ϵ>>>\delta L>\prime >>>.>->->->>(>17.9>)>>>>$

定理1的证明：利用引理1和1+x≤e^xx＞0的事实，可得到下面的不等式(17.10)：

$>>\Gamma >>(>>w>t>>)>>\le >\delta Lover>>\Pi >>j>=>1>>t>>>e>>>ϵ>\theta >>>(>>f>j>>->>f>>j>->1>>>)>>>>>>$

$>>\le >\delta L>>e>>ϵ>>f>t>>j\theta >>>.>->->->>(>17.10>)>>>>$

上述步骤中的简化使用关于j的和(f_j-f_j-1)的telescopic消除。由于算法在迭代K次之后结束，因此Γ(w)≥1。从而下面的不等式(17.11-17.12)成立：

$>>1>\le >\Gamma >>(>>w>K>>)>>\le >\delta L>>e>>ϵ>>f>t>>/>\theta >>>->->->>(>17.11>)>>>>$

$>>>\theta >>f>K>>>\le >>ϵ>>ln>>(>1>/>\delta L>)>>>>.>->->->>(>17.12>)>>>>$

根据引理2，缩放之后的可行原始解答的目标函数值至少为下述值：

$>>>>f>K>>>>log>>1>+>ϵ>>>>>1>+>ϵ>>>\delta >>L>\prime >>>>>>.>>>$

原始解答的近似系数最多为原始解答和对偶解答之间的(比值)间隔。利用不等式(17.12)，该间隔可由下面的不等式(17.13)给出：

$>>>\theta >>f>K>>>\le >>>ϵ>>log>>1>+>ϵ>>>>>1>+>ϵ>>>\delta >>L>\prime >>>>>>ln>>(>1>/>\delta L>)>>>>>>$

$>>\le >>ϵ>>ln>>(>1>+>ϵ>)>>>>>>ln>>>1>+>ϵ>>>\delta >>L>\prime >>>>>>ln>>(>1>/>\delta L>)>>>>.>->->->>(>17.13>)>>>>$

对于 $>>\delta >=>>>1>+>ϵ>>>ln>>(>1>+>ϵ>)>>>>/>>>[>>(>1>+>ϵ>)>>>L>>L>\prime >>>]>>>1>/>ϵ>>>>>来说，量值$ >>ln>>>1>+>ϵ>>>\delta L>\prime >>>/>ln>>(>1>/>\delta L>)>>>>等于1/(1-\epsilon )。利用\Delta 的该值，近似系数的上限由下面的不等式(17.14)限定：$$

$>>>ϵ>>ln>>(>1>+>ϵ>)>>>>>1>>(>1>->ϵ>)>>>\le >>ϵ>>>(>ϵ>->>ϵ>2>>/>2>)>>>(>1>->ϵ>)>>>>\le >>1>>>(>1>->ϵ>)>>2>>>.>->->->>(>17.14>)>>>>$

设置1+ε′＝1/(1-ε)²并求解ε，获得在定理1中陈述的ε的值。

定理2的证明：首先，考虑算法的每次迭代的运行时间，其间节点k及其相关路径P_i，Q_j被选择以增大流量。该节点和路径的选择涉及可利用在R.K.Ahuja，T.L.Magnanti和J.B.Orlin的NetworkFlows：Theroy，Algorithms，and Applications，Prentice Hall，February1993中说明的具有斐波纳契堆的Dijkstra的最短路径算法，以O(nm+n²logn)时间实现的所有对最短路径计算，该文献的教导在此引为参考。一次迭代内的所有其它操作被为该所有对最短路径计算所用的时间吸收(一直到一个常数因子)，导致每次迭代总共O(n(m+nlogn))时间。

随后，根据在每次迭代中，流量沿着路径P_i，Q_j被增大的事实，估计算法结束之前的迭代次数，该值使得在迭代期间在链路e上发送的总流量Δ(e)最多为u_e。从而，对于至少一个链路e，Δ(e)＝u_e，并且w(e)被增大1+ε倍。

现在讨论固定的e∈E的权重w(e)。由于w₀(e)＝Δ并且w_K(e)≤(1+ε)/L′，因此该权重可与任意迭代相联系的最大次数可由下面的等式(18)定义：

$>>>log>>1>+>ϵ>>>>>1>+>ϵ>>>\delta >>L>\prime >>>>=>>1>ϵ>>>(>1>+>>log>>1>+>ϵ>>>>L>>L>\prime >>>)>>=>O>>(>>1>ϵ>>>log>>1>+>ϵ>>>>L>>L>\prime >>>)>>.>->->->>(>18>)>>>>$

由于总共存在m个权重w(e)，因此总的迭代次数的上限为 $>>O>>(>>m>ϵ>>>log>>1>+>ϵ>>>>L>>L>\prime >>>)>>.>>>将其乘以每次迭代的运行时间，可得到总的算法运行时间为$ >>O>>(>>nm>ϵ>>>(>m>+>n>log>n>)>>>log>>1>+>ϵ>>>>L>>L>\prime >>>)>>.>>>注意log(L/L\prime )是logn和用于表示R$$_i和C_j值的位的数目的多项式。

现在讨论上面陈述的路由选择方案的容量性能，首先应定义路由选择方案的“路由选择保证”，随后与路由T(R，C)中的所有矩阵的所有方案中的最佳可能方案的“路由选择保证”比较。已知具有链路容量和关于通信量矩阵的限度R_i，C_i的网络，最佳目标函数值由λ^*表示，它是提供λ^*-T(R，C)中的所有矩阵可根据本发明一个实施例的路由选择方案路由的保证的上面陈述的线性问题公式表示的输出。如图7中所示，图7中表示了行和和列和的路由选择保证的示意图，假定任意路由选择方案允许的λ的最可能值为那么 $>>>\lambda >*>>\le ver>>\lambda >^>>,>>>并且借助量值能够测量路由选择方案的效率。$

值可能难以计算。不过，假定存在单一矩阵T∈T(R，C)，并利用例如最大同时流量公式计算最大乘数λ(T)，以致在具有给定链路容量的网络中，λ(T)·T切实可被路由，于是 $>ver>>\lambda >^>>\le >\lambda >>(>T>)>>,>>>从而，下面的不等式(19)被满足：$

$>>>>\lambda >*>>>\lambda >>(>T>)>>>>\le >>>\lambda >*>ver>>\lambda >^>>>\le >1>.>->->->>(>19>)>>>>$

因此，对于任意通信量矩阵T∈T(R，C)，量值λ^*/λ(T)是关于路由选择方案的效率的下限。为了获得关于路由选择效率的更严格的下限，识别其λ(T)最小的矩阵T∈T(R，C)，它可能难以计算，因为这样的矩阵将占用大量的带宽来路由。下面的例证的启发式方法可被用于近似占用大部分带宽来路由的矩阵，其中C(T)表示路由矩阵T∈T(R，C)的最小带宽。利用线性规划，以多项式时间可计算使C(T)最大化的矩阵T∈T(R，C)。由于该问题没有任何容量约束条件，因此能够假定从节点i到节点j的通信量可沿着单一最短路径被整体路由。如果d_ij表示从节点i到节点j的最短路径的中继段计数，那么确定占用最大带宽来路由的通信量矩阵T∈T(R，C)的问题可用公式表达为下面的具有等式(20-21)和不等式(22)的约束条件的例证线性程序：

$>>max>imize>>\Sigma >>i>,>j>\in >N>>>>d>ij>>>t>ij>>,>>>$

服从

$>>>\Sigma >>j>\in >N>,>j>\ne >i>>>>t>ij>>=>>R>i>>\forall >i>\in >N>,>->->->>(>20>)>>>>$

$>>>\Sigma >>j>\in >N>,>j>\ne >i>>>>t>ji>>=>>C>i>>\forall >i>\in >N>,>->->->>(>21>)>>>>$

    t_ij≥0i，j∈N.                    (22)

所获得的带宽是线性程序的目标函数，(定义T(R，C))的行及列行限度形成约束条件。该公式表示可被用于计算矩阵T和值λ(T)，以便提供根据本发明一个实施例的路由选择方案的有效的下限。

关于根据本发明的一个实施例的两阶段路由选择方案的分流比的两个变化提供路由选择方案的一般化，如下所示：

(I)分流比既取决于源又取决于目的地：这种情况下，假定始于节点i，其目的地为节点j的通信量的一部分α_k^ij被路由给中间级中的节点k。随后计算第二阶段中在节点i和j之间需要的容量。在第一阶段中，节点i和j之间所需的容量由下面的不等式(23)定义：

$>>>\Sigma >k>sup>>\alpha >j>iksup>>>t>ik>>\le >>max>k>sup>>\alpha >j>iksup>>>\Sigma >k>>>t>ik>>\le >>max>k>sup>>\alpha >j>iksup>>>R>i>>.>->->->>(>23>)>>>>$

对于第二阶段，节点i和j之间所需的容量由下面的不等式(24)定义：

$>>>\Sigma >k>sup>>\alpha >i>kjsup>>>t>kj>>\le >>max>k>sup>>\alpha >i>kjsup>>>\Sigma >k>>>t>kj>>\le >>max>k>sup>>\alpha >i>kjsup>>>C>i>>.>->->->>(>24>)>>>>$

于是，这两个阶段中在节点i和j之间所需的总容量可由下面的不等式(25)定义：

$>>>C>ij>>\ge sup>>\alpha >j>iksup>>>R>i>>+sup>>\alpha >i>mjsup>>>C>j>>\forall >k>\forall >m>.>->->->>(>25>)>>>>$

(II)分流比只取决于源：在该方案中，α_kⁱ表示进入节点i到节点j的通信量的分数。在阶段1中从节点i流向节点j的通信量的数量由α_jⁱR_i表示，它是阶段1中在节点i和j之间所需的容量。节点i和j之间所需的容量可由下面的不等式(26)定义：

$>>>\Sigma >k>sup>>\alpha >k>isup>>>t>kj>>\le >>max>k>sup>>\alpha >k>isup>>>\Sigma >k>>>t>kj>>\le >>max>k>sup>>\alpha >k>isup>>>C>i>>.>->->->>(>26>)>>>>$

于是，节点i和j之间总的所需容量C_ij由下面的不等式(27)给出：

$>>>C>ij>>\ge sup>>\alpha >j>isup>>>R>i>>+sup>>\alpha >i>ksup>>>C>j>>\forall >k>.>->->->>(>27>)>>>>$

注意在这两种情况下，约束条件都是线性的，与通信量矩阵中的单独项无关，只取决于行和与列和。

对在其尺寸范围中代表电信公司基干网的两种网络布局进行了使用上面陈述的实现的模拟。如图8中所示，第一个网络是一个15节点网络，包括节点n1～n15，以及28条双向链路。第二个网络是一个具有33条双向链路的20节点网络(图中未示出)。对于不同的运行来说，从集合{OC-3，OC-12，OC-48，OC-192}选择每个网络链路的容量。对于结果来说，R_i′s和C_i′s被假定为相等并被归一化为1，即，R_i＝C_t＝1i。对上面两种布局中的每一种计算矩阵T：(I)分流比取决于源和目的地，和(II)分流比只取决于源。量值λ(T)是相等(由λ_equal表示)和不相等(由λ_unequal表示)通信量分流比的两种情况的λ值的上限，并且λ(T)≥λ_unequal≥λ_equal。

图9和10图解说明了对于五次不同的运行，上述三个λ值的曲线图，其中λ值的相对排序和预期一样。可看出，在所有绘出的情况中，根据本发明的一个实施例的方法的路由选择效率非常接受于1.0。对于这两个网络的曲线图来说，路由选择效率从0.9变化到0.99，从而表示根据本发明的一个实施例的方法能够接近于最佳地完成任务。结果还图解说明当允许分流比α_i不相等时，网络吞吐量的增大。对于15节点布局运行来说，吞吐量的百分率增长(λ_unequal-λ_equal)/λ_equal从10％到高达85％。对于20节点布局来说，百分率增长从2％到高达53％。根据这些结果，可得出下面的两个结论：(1)根据本发明一个实施例的路由选择方案能够在通信量不确定的情况下(按照定义的通信量变化模型)高效地路由，同时网络吞吐量不会明显从通信量分布中选择的单一矩阵的吞吐量；(2)通过允许通信量分流比不相等，和分流比相等的情况相比，网络吞吐可被显著增大。

从而，已表明根据本发明一个实施例的路由选择策略能够解决与处理网络中的极端通信量可变性相关的几个已知问题，而不需要动态路由选择，也不需要高的容量过度提供。在不对路由选择进行适应修改的情况下处理通信量变化的能力能够导致更稳定更稳固的因特网行为。利用根据本发明一个实施例的路由选择方案可允许服务提供者路由所有通信量分布(在定义的模型下)，同时(i)网络吞吐量基本上接近于路由单一矩阵的网络吞吐量，(ii)不需要实时检测通信量变化，或者重新配置网络。从而，本发明提供一种简单的网络路由选择方案，和最短路径路由选择相比，实现起来不太复杂，该方案还具有下述有利性质：(i)该方案能够有效地处理在入口-出口链路的容量约束条件内允许的所有通信量模式，(ii)该方案能够避免高通信量可变性下的网络拥塞，而不需要路由选择参数(例如链路权重或路由选择策略)的动态重新配置，和(iii)该方案带宽效率高，并且该方案的容量要求接近于为适应单一的不良通信量模式所需的容量要求，即使该方案能够处理服从入口-出口容量约束条件的所有可能通信量模式。

根据本发明一个实施例的路由选择方法可提供一个或多个下述优点：网络服务级容量的更有效利用，减少网络节点的路由器的拥塞，和网络的更高的分组吞吐量。该方法可由集中式网络管理系统或者由网络的每个节点，或者由这两者为被请求的LSP实现。为了协调新路径的提供，优选采用把结果分给网络节点的集中式网络管理系统的实现。当不存在集中式网络管理系统时和/或如果被请求的LSP是利用通过网络路由的控制分组实现的分布式请求，那么优选在网络的每个节点中的分布式实现。

根据本发明一个实施例的路由选择方法的各种功能可利用电路部件来实现，或者可在数字域中被实现为软件程序中的处理步骤。这种软件可用在例如数字信号处理器，微控制器或者通和计算机中。

应理解这里使用的术语“路由器”可以指的是单一硬件设备，或者多个互连的硬件设备，例如交换机架构，软件和硬件部件的组合，或者软件程序。

可以方法和实践这些方法的设备的形式具体体现本发明。也可以包含在有形介质，例如软盘，CD-ROM，硬盘驱动器，或者任意其它机器可读存储介质中的程序代码的形式具体体现本发明，其中所述程序代码由机器，例如计算机装入并执行，所述机器变成实践本发明的设备。还可以保存在存储介质中，由机器装入和/或执行的程序代码，或者通过一些传输介质，例如通过电线或电缆，通过光纤，或者通过电磁辐射传送的程序代码的形式具体体现本发明，其中当所述程序代码被机器，例如计算机装入并执行时，所述机器变成实践本发明的设备。当实现在通用处理器上时，程序代码段与处理器结合，形成类似于专用逻辑电路工作的独特设备。

应明白这里陈述的例证路由选择方法的步骤不必被要求按照所述的顺序执行，这种方法的步骤的顺序应被理解为只是对本发明的举例说明。同样地，在这种方法中可包括其它步骤，在根据本发明的各个实施例的路由选择方法中，一些步骤可被省略或组合。

还要明白在不脱离由附加权利要求限定的本发明的原理和范围的情况下，本领域的技术人员可在为解释本发明的本质而说明和图示的各个部分的细节，材料和排列方面做出各种改变。