优化网络中的需求的路由的方法
专利名称：优化网络中的需求的路由的方法
技术领域：
本发明涉及用于优化网络中的需求(demand)路由的方法和装置，具体而言(尽管并非排他性地)，涉及用于诸如多协议标签交换(MPLS)分组交换通信网络之类的分组交换通信网络中的需求优化的方法和装置。
背景技术：
MPLS被用在通信网络中，具体而言用在异步传输模式(ATM)和因特网协议(IP)网络中以提供附加特征，例如对路由的精确控制，允许改善客户服务。MPLS最初被开发用来增强性能和网络可扩展性。IETF(因特网工程任务组)内的工作组进行该主题的标准化工作，这记载在“注释请求”(RFC)中。
如所公知的，在分组交换网络中，数据分组被路由经过从起始点到目的地点的多条链路。链路通过路由器耦合在一起，路由器接收分组，并依赖于各种因素(当然包括分组的目的地点)判定用哪一条链路来发送分组。然而，路由器还可以基于链路上的流量，并且在某些情况下基于数据的特定分组的优先级来判定如何路由特定分组。另一方面，在MPLS网络中，特定的传入分组在分组经过网络或经过网络的特定区域的路由的起始之处，被标签边缘路由器(LER)指派以一个“标签(label)”。被指派给分组的标签提供了关于分组经过网络所要采取的特定路由的信息。因而，分组被沿着标签交换路径(LSP)从一个标签交换路由器(LSR)转发到下一个LSR，其中每个LSR仅仅基于标签的内容作出转发判决。在每一“跳”处，LSR剥离现有的标签并施加新的标签，新的标签告诉下一LSR如何转发分组。
由于沿着标签交换路径流动的流量由在LSP的入口节点处施加的标签定义，因此这些路径可被当作隧道，这种隧道处于正常的IP路由和过滤机制之下。当LSP被以这种方式使用时，其被称为LSP隧道。
LSP隧道允许实现与网络性能优化有关的多种政策。例如，LSP隧道可被自动或手工地路由以避开网络故障、拥塞和瓶颈。此外，在两个节点之间可以建立多条平行的LSP隧道，并且两个节点之间的流量可以根据本地政策被映射到LSP隧道上。
为了有效使用可用网络资源，需要流量工程。然而，为了能够作到这一点，必须获得对网络上的流量模式以及可能存在的任何问题，例如网络故障、拥塞和瓶颈的理解。完成这一点的一种方式是监视MPLS网络中的链路。这确保了预定义的服务质量(QoS)水平和服务水平协议(SLA)得以满足。
需求通常代表对于入口节点和出口节点之间的一定量的带宽的要求(requirement)，经常具有关联的流量类别或QoS要求。需求来自于多种源。对供应高带宽视频链路的请求可视为一个需求。另一种需求源是从入口到出口跨核心网络的聚集“微流”，这种流具有公共流量类别，即，需求可能承载单个高带宽流，或者由许多更小的流形成。流量类别利用诸如最大延迟或成本之类的参数约束可用于满足需求的可接受路由。在某些情况下，对于带宽的需求(具有某一QoS)随时间的变化将是完全可预测的，以至于流量可被指派给MPLS路径，然后可为这些路径确定使拥塞最小的最佳路由。只要带宽要求的可变性没有过量，与在线精细调节的使用(其是为了调节“运行时”的保留(reservation))相耦合的离线路径布置就可以产生有用的网络优化策略，例如在白皮书“Auto-bandwidthallocator for MPLS traffic engineering”，Cisco 2003中所讨论的。离线和在线需求优化一般是由于不同的原因并且在不同的时间尺度内发生的，其中每一种优化使用不同的机制。
ATM网络先前已被用在网络核心内，并且离线工具已被开发出来以优化经过ATM网络“云”的路径的路由。这些工具迅速被改动以支持经过MPLS云的带宽保证LSP的离线优化。给定小规模的典型核心网络，该优化问题还是相当容易处理的。主要的约束是需求一定不能被分割。它们代表了聚集流的集合，很难将其分割为跨多条路径，而不在各个流内引入不必要的分组重排。
流之间服务区分的需要近来已变得越来越重要，这是因为操作者正努力找到有利可图的收入流。然而，关于可以实现多少服务区分是有限制的。一种方法是使用MPLS来提供跨网络的多条路径，然后基于其流量类别向这些路径指派流。然而，这可能将额外的复杂度引入到压力已经很重的网络的一部分中。
近年来，MPLS边界已经逐渐移出核心外，移入网络的接入部分(被称为接入网)中。这允许在分组到达核心之前对分组进行分类并指派给LSP，利用隧道传输来选择跨核心的期望路径，并且最小化核心路由器必须支持的信令和状态。在更复杂的场景中，其还允许操作者选择跨接入网自身的不同路径。
对于任何离线优化而言，该趋势具有若干后果。MPLS云的大小不再局限于核心网络的大小。对于任何优化工具(优化器)，这产生了严重的扩展问题，要求开发出将问题分解为某种更加易于管理的问题的技术。发起于接入层内的流量一般比起核心内的流量来说聚集度要低，因此表现出更大的波动。这使得难以识别足够持久和稳定以至于值得进行离线路由的LSP。
诸如在白皮书“Traffic optimizer product overview”，Cplane 2003和“IP/MPLSViewIntegrated network planning，configuration management &performance management”，WANDL 2002中描述的系统允许操作者优化跨网络核心的MPLS需求。其假定将网络按预定义划分为接入和核心路由器，因而随后要优化的需求则限于核心。其他需求可能发起于接入网中，例如基于IP的语音(VoIP网络)中的那些。关于为何应当不同地对待“接入网”优化问题和等同的核心问题，有若干个原因。
一个原因是全局地优化跨越许多路由器的大量需求在计算上是非常昂贵的。随着需求和/或路由器数目的增大，这一成本迅速增大。如果要实现现实的优化时间，则将问题分解为更简单问题的集合是必要的。
第二个原因是许多组织使用不同的人群组来管理核心和接入网。即使可以跨整个云路由需求，也可能由于这些管理性的划分而无法部署这种解决方案。更好的方法可能是使用接入需求来构造用于支持该流量所必需的核心需求的一组要求。这些要求随后可以被传递到处理网络核心的优化的群组(核心群组)，核心群组可以利用传统的或新的优化技术优化这些需求的布置。处理网络的接入部分的优化的群组(接入群组)将使用针对这些要求的解决方案来建立LSP以支持原始需求。从一组接入需求投射到核心上的要求在性质上可能与一组传统的核心需求相当不同，因而可能要求不同的核心优化工具。
另一个原因是由于这样的事实逐跳(hop-by-hop)供应跨入口和出口之间的整个路由的LSP可能是效率不高的。沿着路途的每个路由器将需要处理保持LSP存活所必需的信令流量，并且保留路由器内的状态。定义跨核心的一组LSP，然后使用这些作为发起于接入网中的永久LSP的隧道可能是更加有效的。然后，只有接入路由器将存储特定于接入LSP的状态。
优化跨网络的需求布置在计算上是昂贵的。有两种主要的方法来解决该问题(该问题在本领域中被称为多物(multi-commodity)流问题)，基于边缘的策略和基于路径的策略，这两种方法也是本领域中已知的。
在基于边缘的策略中，线性程序尝试计算由网络中的每条链路承载的每个需求的量。在最坏情况下，对于完全的需求网格以及高度相连的网络图，将存在0(n2)个需求和0(n2)个边缘。在2003年2月University ofWürzburg的Institute of Computer Science的Tech.Rep.304中发表的作者为Khler，S.和Binzenhfer的论文“MPLS traffic engineering in OSPF networks-a combined approach”包含了五个大小增大的示例性拓扑。还可以证明，随着网络大小的增长计算时间迅速地增加。当需求具有与其相附着的附加QoS约束时，基于边缘的策略具有另一个缺点。由优化器找到的路径可能不满足例如延迟或跳长度之类的约束，导致解无效。在优化过程期间增强这些约束的尝试迅速地导致不易处理的模型，即使对于小的网络也是如此。因此，基于边缘的方法最适合于具有不严格的QoS约束的需求，例如尽力而为流量。
另一种方法可以是对于每一需求首先识别一组可能的路径，每条路径满足QoS约束。然后可以使用线性程序来计算每条路径应当承载多少需求。如果只有很小数目的路径被用于一个需求，则优化问题的大小可以限制在易处理的范畴。不足之处在于该解决方案与路径的选择有关。如果路径的数目增大，则为了增大找到最优解决方案的机会，优化时间增长得非常迅速，尤其对于高度相连的网络图而言更是如此。
对于具有严格QoS属性的需求，最佳策略可以是使用基于路径的方法，并且希望每个需求的有效路径的数目较小。但是随着网络大小的增长，迅速到达了优化时间变得不易处理的阶段。对于基于路径的方法而言，存在经过接入网的多条路径的情形也产生了困难。利用类似于2001年Liu，C.和Ramakrishnan，K.C.的“A*pruneAn algorithm for finding kshortest paths subject to multiple constraints”，INFOCOM.743-749中所公开的A*Prune之类的算法，可以看出大多数路径共享跨核心的公共子路径。在许多情况下，为了找到针对优化问题的好的解决方案，要求路径中具有更多的可变性。
在典型的骨干网中，可能有上百或更多个节点。即使单个流量类别(在每对设备之间有需求)也生成了直接优化起来会非常昂贵的问题。看起来很明显，需要找到用于简化需求布置问题的(一种或多种)装置和方法(如果这种规模或更大规模的问题可以被恰当地处理的话)。
发明内容
因此，本发明的目的是提供一种用于优化网络中的需求的路由的方法，该方法克服了，或至少减轻了现有技术的缺点。
因此，本发明提供了一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，每个需求包括源节点、目的地节点和至少一个需求参数要求，该方法包括a)将网络的节点和链路划分为链路和节点的一组集群(cluster)；b)对该组集群施加分级树结构(hierarchical tree structure)，以使得任何一对集群在其间都具有经由最近公共祖先的唯一路径；c)通过仅在分级树结构的同一分支中的所有较低集群都已被处理之后才处理每个集群中的需求，来确定所有需求的最优路径以使得这些路径满足至少一个需求参数要求，所述对于每个集群的处理包括i.将每个需求分割为集群内需求和(如果适当的话)集群间需求，在集群内需求中，源和目的地节点处于同一集群中，在集群间需求中，源和目的地节点处于不同集群中；ii.确定所有集群内需求的最优路径，以便满足至少一个需求参数要求；以及iii.将所有集群间需求向上传递到分级树结构中的下一集群，以作为其中的需求进行处理。
在一个实施例中，该方法还包括将与已经被优化的路径的网络成本有关的信息向上传递到分级树结构中的下一集群，以使得在确定仍要优化的集群内需求的最优路径时，可以利用已经使用的网络成本。
网络成本可以包括针对特定的需求参数要求导致的成本，所述特定需求参数要求例如是流量类别要求，例如最大延迟要求。
所述确定所有需求的最优路径的步骤可以包括基于至少一个网络参数要求(例如流量密度要求)确定最优路径。
现在将参考附图以示例方式更完全地描述本发明的若干实施例，在附图中图1示出了根据本发明第一实施例的用于优化网络中的需求的路由的装置的示意图；图2示出了描述包含在图1的装置中的网络结构分析器的操作方法的流程图；图3示出了网络的示意图；图4的图示出了对图3所示的网络执行的双连接成分(component)分析的结果；图5的图示出了将树合并规则应用到图4的结果的结果；图6的图示出了将分级树结构施加到图5的结果的结果；
图7的图示出了根据本发明第一实施例的简单的需求替换和优化示例；图8示出了根据本发明第一实施例的出口集群的需求分割过程；以及图9示出了图1的装置的需求替换和优化操作的流程图。
具体实施例方式
因而，如上所述，希望能够优化电信网络中的需求的路由以增大网络的容量。在第一实施例中，本发明提供了一种用于执行这种优化的方法和装置，这是通过以下步骤实现的分析网络并虚拟地将路由器或节点组织为集群，随后集群被以分级方式组织，其中网络的“中央核心”位于该分级结构的根处。
因而，图1是示出了根据本发明第一实施例的需求优化器的体系结构的示意图。需求优化器51包括输入处理器(handler)53，输入处理器53经由输入链路52接收网络结构的细节和要优化的需求。输入处理器53经由链路54将网络结构细节和需求传递到存储器59。网络结构分析器55经由双向链路63耦合到存储器59，并且执行网络结构的分析，这将在下面进一步描述。需求管理器57也经由双向链路60耦合到存储器59，并且经由链路56耦合到网络结构分析器55。输出处理器61经由链路58耦合到存储器59，并且允许外部经由输出链路62访问结果。输出处理器61可以在例如GUI(图形用户界面)上提供结果。需求优化器51可以实现在Unix机器上，但是本领域技术人员应当清楚，其也可以以任何其他合适方式实现。输入处理器53也可以接收用户配置输入，这将在下面进一步讨论。
图2示出了描述结合在图1的需求优化器中的网络结构分析器的一般操作的示意性流程图，其开始于点“S”，结束于点“F”。因而，一般，首先分析网络结构以将节点划分为若干集群(见要素C1)，接着在要素C2中对这些集群施加树状分级结构。如下更完整地描述，很清楚，在分级的树结构中，有若干个分支，一个分支中的每个集群沿核心方向连接到单个“父”集群，该“父集群”又沿核心方向连接到进一步的“祖父”集群(如果需要的话)，就这样一路返回到核心(或“根”)集群自身。为了优化所有集群，优化从后代集群(descendent cluster)向祖先集群(ancestor cluster)进行。“后代”集群被认为是在任何特定的树中离核心集群最远的集群。因而，首先确定并优化最年轻的未优化集群(见要素C3)，然后确定并优化另一个最年轻的未优化集群。这样，一个集群只有在其所有“后代”集群都已被优化之后才被优化。
集群的优化涉及将在该集群中具有起始点或目的地点的任何集群间需求分割为一对需求，其中一个是集群内需求(两个端点都在该集群中)，一个是集群间需求(见要素C5)。集群内需求被优化，并且集群间需求被在树状分级结构中向上传递到特定集群的父集群，在父集群处它们被当作是该集群中的需求。然后在要素C6中确定是否所有的集群都已被优化。如果是，则过程在点“F”结束。如果不是，则过程移回要素C3，在C3处找到分支中的另一个最年轻的未优化集群。因而，该过程将从分级树结构的外围开始向核心集群优化所有集群，直到所有集群都已被优化为止。
因而，为了分解网络以将节点划分为若干集群，必须分析网络。一个集群一般是紧密连接的节点和其间的链路的群组，其中集群自身松散地连接到紧密连接的节点的另一个集群。每个集群将利用一个或多个连接节点(connecting node)相接合，这一个或多个连接节点将该集群连接到另一个集群，因而连接节点可被认为是这两个集群的一部分。当然，在某些情况下，集群可以只具有一个或多个连接节点。
为了更好地描述图2的要素C1，图3示出了具有多个节点n1、n2、n3、...n26的简单网络的示意图。节点n1...n26通过链路13以各种方式相连以形成网络。如上所述，首先分析网络以将节点划分为节点集群。可以使用任何类型的合适的集群分析。例如，可以使用的一种已知类型的分析是双连接成分分析。然而，本领域技术人员将会清楚，作为替代，也可以使用任何合适的集群分析技术，例如主要成分(Principal Components)。图4示出了对图3的网络执行的双连接成分分析的结果。
为了执行双连接成分分析，使用了下面的规则
◆连接的网络中的节点n在以下情况下是连接节点(connectionnode)从网络中删除节点n，以及删除到节点n的所有链路，会使得网络断开连接，成为两个或更多个非空部分；◆当且仅当一个网络(部分)不包含连接节点时，这个网络(部分)是双连接(bi-connected)的；◆一个网络在以下情况下是最大双连接(maximally bi-connected)的当且仅当该网络不具有其他包含最大双连接的网络部分的所有节点和链路的双连接部分。最大双连接的网络部分是双连接的集群(bi-connectedcluster)；◆两个双连接的集群可以具有至多一个公共节点，并且该节点是连接节点；以及◆具有来自多于一个集群的链路的节点是连接节点。
在执行了双连接成分分析之后，网络被划分为多个集群，编号为C0、C1、C2、...C12，这些集群由连接节点相连，如图4所示。因而，如表1所示，每个集群包含来自图3的网络中的不是连接节点的某些节点，以及形成其连接的每个集群的一部分的连接节点(为了看起来方便，连接节点被示为部分在其连接的每个集群的外部)，如下所示
表1 双连接成分分析的结果例如，集群C0包含原始节点n5，n6，n7，n8，n9，n10和n11，而集群C4和C5分别只具有连接节点n10，n15和n21以及n4和n5。因此，来自图3的网络的所有节点要么完全在集群内，要么是连接节点。
尽管不是必要的，但是最好通过找到可以合并在一起的集群来进一步简化该集群结构。很清楚，树结构中的节点很容易处理，这是因为在树中的任何两个节点之间有唯一的路径。因而，布置需求是意义不大的，因为没有其他的选择。由于通常的双连接成分分析将把树分割为集群的分级结构，因此将其分割为大量的小集群并不是总是高效的。因此，进一步处理这些结果以查找已经从树子结构生成的集群并将这些合并为更大的结构可能是有用的(高效的)，尽管不是必要的。或者，可以使用其他的集群化技术，这些技术不需要这种进一步的处理步骤。例如，可以改变双连接成分分析，以使其在进行时执行这种合并。可以重复使用第一树集群合并规则以合并兄弟(sibling)成分。
图5的图示出了将树合并规则应用到前述结果的结果。在该图中，符号“x∪y”被用于表示包含集群“x”和“y”的并集的集群。例如，C7∪C8图示了集群“C7”和“C8”的并集。
图5中所示的集群图相对于图3的节点网络提供了某种简化，但是仍然需要识别出核心集群，即，网络的核心(这与图2的步骤C2有关)。核心集群可以按多种不同方式确定。挑选最大集群(例如包括其连接节点)看起来似乎是合理的，只不过对于非常大的网络，可能存在比“真实”核心更多的大节点。类似地选择到所有其他集群的最大路径长度最小的集群看起来是合理的，因为其往往会找出树的“中心”处的集群。然而，具有许多跳的网络往往会使这种方法失灵，这是因为接近这种集群链的末端的集群更有可能被不正确地识别为核心集群。
更加健壮的解决方案是选择到所有其他集群的平均路径长度最小的集群。对于参考图5给定的示例而言，平均路径长度在表2中给出。
表2 来自每个成分的平均路径长度在表2中，已经算出了从每个集群到下一集群的跳数，即，已经忽略了连接节点。利用平均长度作为量度将导致集群C0或集群C4被选为根。由于这两个集群具有相同的平均路径长度，因此选择哪一个集群并不是实质性的问题，为了下面的讨论，集群C0被选为根或核心集群。给定对根集群的这一选择，可以对树链路进行排序，以引入向核心移动和远离核心移动的概念，如图6所示，因而提供分级树结构。
如图6所示，网络核心被示为集群C0，集群C0经由连接节点连接到其他集群。如所说明的，利用该方法仍然存在可能选择“错误”的根的可能性。因此，需求优化器突出了其“认为”构成核心集群C0的(一个或多个)路由器。如果这是不正确的，则需求优化器向用户提供选择替换路由器的机制。然后，包含该路由器的集群可被当作核心集群。
在分级树结构已被施加在网络上的情况下(这是虚拟意义上的，因为很显然，实际的网络不受影响)，需求优化过程现在可以发生。简而言之，策略是利用各自跨越单个集群的许多其他需求来分解跨越网络中多于一个集群的需求。此外，这种解决方案应当处理这样的情形即在到达核心之前需要穿越多个集群。对于这些集群中的每一个应当执行优化，因为现在将有多条路径跨过这些集群(中的某一些)。在详细描述该优化过程之前，应当注意◆所有有根(即，分级的)树将具有在核心(根)处的一个集群和在叶子处的多个集群，其中相邻的集群被连接节点彼此分离；◆对于从入口到出口的每个需求，存在跨集群树的唯一路径；◆单个需求在集群树中具有相同的入口和出口节点；◆如果需求的路径具有长度1，则该需求是本地的，否则是非本地的。对于处于连接节点处的单个需求的退化情形，允许长度为0；◆需求的入口集群是路径中的第一集群；◆出口集群是此路径中的最后一个集群；◆如果集群C处于需求的路径中，并且既不是入口集群也不是出口集群，则该需求穿越集群C；◆与每一集群C相关联的是其路径包括集群C的一组需求。每一集群还具有一组子集群，可能为空。这些是经由单个连接节点连接到集群C的树中的集群C的后代。
很明显，如果与一个集群相关联的所有需求对于该集群来说都是本地的，则需求优化器可以很容易跨过该集群优化这些需求，而不考虑任何其他集群。在遇到非本地需求的情况下，所采取的策略是将其分解为两个需求，其中一个是本地的，另一个在分级集群树中的更高处开始或结束。通过重复应用该过程，所有需求将最终变为某个集群的本地需求。更准确地说，非本地需求被“提升”到分级集群树中入口和出口集群的最低公共祖先。
该过程中的复杂因素在于附着到每个需求的QoS约束。这些限定了需求的可接受路径。当一个需求被分解为在树中的更高处开始或结束的一个需求时，必须计算新的QoS约束，其考虑了从原始端点到达新的端点的成本。如果集群内的所有节点都以树的方式链接在一起，则这可以在单个步骤中完成，因为经过这些集群的路径是唯一的，因此计算穿越这些路径的成本是意义不大的。但是在更一般的情况下，可能有多条路径经过每个集群，这就提出了应当使用哪一种成本的问题。
在图7中示出了一个示例，其中具有入口节点ni和出口节点ne的需求d的最低公共祖先是集群33(Ca)。因而，从图中可见，存在唯一的集群序列，该序列必须被需求穿越，以从集群33中的入口节点ni开始到达集群31(Ca)。当然，存在另一个必须被穿越以从集群31(Ca)到达集群32中的入口节点ni的集群序列。此外，从节点ni到集群31(Ca)的路径将经由某一连接节点36(APe)进入集群31(Ca)，并经由另一连接节点37(APi)离开集群31(Ca)。很明显，这两个连接节点36和37必须是不同的，因为如果它们是相同的，则形成集群36的左孩子的集群将是最低公共祖先，而不是集群31自身。原始需求30(d)被示为在集群33和32之间。
因而，为了优化需求30，在集群33中考虑它，并将它分割为本地(集群内)需求和集群间需求。分割需求的过程将参考图8进一步描述，图8示出了入口集群的需求分割过程。尽管需求可以在入口和出口集群中的任一处或者在这两处进行分割，但是将仅参考入口集群进一步描述该过程。
因而，发起于集群33中的入口节点ni的需求d可被分割为两个子需求，即本地需求dl和余者，即集群间需求dr。然后，本地需求dl随后可以与集群33中的所有其他集群内需求一起被优化，而集群间需求dr被向上传递到树中的下一集群34。当然，原始需求d具有与其相关联的QoS约束。这可能约束了沿着用于承载需求d的流量的任何路径可允许的总延迟。很明显，这种限制必须在子需求dr和子需求dl之间进行分割。给予跨需求dl的路由的自由度越大，可用于路由子需求dr的自由度就越小，反之亦然。如果从集群33中的入口节点ni到集群33和集群34之间的连接节点35有唯一的路径，则没有选择余地。原始需求d的成本被该路径固定，因此这仅能被从原始成本中减去以确定用于需求dr的QoS约束。然而，在更一般的情况下，将存在许多种分割QoS约束的方式。需求替换和优化过程所采取的策略可以是首先解决包含入口节点ni的集群33的优化问题。可以给予诸如子需求dl之类的需求以优先处理，以增大它们被分配以经过集群33的最短可能路由的可能性。一旦一条路径被指派给子需求dl，这就可用于计算用于子需求dr的剩余QoS配额。当方向相反并且为原始需求d处理出口集群时，可以使用类似的策略。在已经确定了子需求dr所要求的QoS约束的情况下，其布置随后可被托付给父集群33。一旦整个树已被优化，被选择用于子需求dl和子需求dr的路径就可用于确定用于原始需求d的路径。
因此，可以看出，需求d或者将被指派以一组路径(在本地需求的情况下)，或者被分割成一对子需求(dl，dr)。需求替换和优化过程的目的是以一种满足需求的QoS约束的方式设置本地需求或子需求。这将参考图9更完全地描述。然而，应当提到，仅仅给需求指派一组路径可能是不够的；还需要知道应当给这些路径中的每一条分配多少带宽。然而，为了说明的方便，该细节在下面的内容中被忽略。
图9示出了描述需求替换和优化过程的要素的流程图。需求替换和优化过程的目的是为系统中的所有需求限定路径。在集群的优化期间，本地需求将被分配以一条或多条路径。在非本地需求的情况下，与路径的关联是由子需求dl，dr隐性限定的。最初所有需求将不被处理。因此，每个集群将直到队列为空时才被处理。换句话说，如果需求是非本地的，则其必须经由集群的唯一父连接节点离开或进入该集群。
需求替换和优化过程是由下面的要素实现的，参考图9，该过程开始于要素SB1构造队列。通过执行集群树的后向穿越(post-order traversal)构造要处理的所有集群的队列Q，其中跳过了连接节点。后向穿越是用于探索树结构的一种算法，其在访问树中的每一集群的孩子之后，访问该集群。
B2定义集合。构造集合U作为所有未处理需求的集合。
B3Q为空？然后检查队列以查看其是否具有任何未处理集群。如果Q非空则继续进行到B4。如果为空则继续进行到B14。
B4取得队列中的第一集群。取得队列中的第一集群进行处理，过程移到B5。
B5所有需求是本地的？被处理的集群中的所有需求都是本地的？如果是，则转到B11。如果不是，则必然有集群的父连接节点，然后移到步骤B6。
B6取得第一非本地需求。取得第一非本地需求进行处理，过程移到B7。
B7集群是出口？对于考虑的非本地需求而言，被处理的集群是入口集群或出口集群。如果是入口集群，则过程移到B8；如果不是，则移到B9。
B8创建本地子需求。如果是入口集群，则创建从入口节点ni到父连接节点的新的本地子需求dl，过程移到B10。
B9创建远程子需求。如果不是入口集群，则创建从父连接节点到出口节点ne的新的远程子需求dr，过程移到B10。在新的子需求的图(map)中作出一个条目。当向图添加新条目时，从映射中去除具有相同关键字(key)的任何现有条目是很重要的。
B10更新集合。通过删除刚刚已被分割的需求来更新要处理的需求的集合U，并且向集合添加新的远程子需求，即集群间子需求。过程然后返回B5，检查是否还有任何要处理的非本地需求。
B11计算路径集合。在这时，被处理的集群中的所有需求都是本地的，因此对于这些需求中的每一个可以计算一组路径。在一般情况下，需要解决优化问题。本地需求的路由成本需要被最小化，以给予相应的继续子需求以最大路由自由度。现在使用基于路径的优化策略，该策略开始于向本地需求指派最短“权重”路径(或多条路径)，并且向剩余需求指派更完全的一组路径。在考虑单个属性(例如跳数)的情况下，这意味着路径是按照最短路径长度来应用的。如果权重是成本，则路径将按照最小成本来应用。如果不能满足所有需求，则这组路径需要被加宽，并且需求替换和优化过程被重复。如果需求替换和优化过程允许多条路径被指派给一个需求，则灵活性限于非本地需求。如果不能满足一个需求(例如由于QoS度量太严格)，则这组路径将为空。
B12更新远程子需求。现在利用与原始需求相同的属性更新在B9中创建的远程(非本地)子需求，只不过QoS约束减少了分配给相应本地子需求dl的路径的权重。过程随后移回B3，检查是否还有任何未处理的集群。
B13路径构造。如果所有集群都已被处理，即，队列为空，则过程移到B13。由于现在所有需求都已被优化，因此对于经过所有集群的所有需求都可以构造路径。
应当意识到，如上所述的需求替换和优化过程的有序程度可能大于必要的程度。取代使用队列，一个集群可以与集群树中的其他集群并行地被处理。
理想情况下，随着需求替换和优化过程沿集群树向上移动，需求应当被利用公共属性聚集。例如，当需求被添加到父集群时，可能已经存在一个去往相同目的地(或来自相同发源)的需求，其具有兼容的流量类别。在这种情况下，可能只需要增大现有需求的带宽要求，而不是添加第二需求。集群被处理的顺序也可能影响这种聚集的潜在可能。我们推测，尝试优化隧道产生的穿越顺序也可能增大需求聚集的可能性。
许多网络操作者跨多个组织边界地分割网络管理。将集群与每个组织对齐是很重要的，因此需求替换和优化过程并不尝试在多个组织群组的控制下优化路由器的集合。注意，这并不暗示只应当构造与组织实体一样多的集群，而是必须确保没有集群被跨这些实体地分割。
先前已经讨论了集群合并，上面讨论了集群分割。给定预定义的路由器分组，则需要自动完成由双连接集群分析标识的集群的合并和分割，因此所得到的集群遵循该分组。以上实施例的需求替换和优化算法尝试布置所有需求。然而，当网络被沿着管理边界划分时，该方法可能需要改进。
例如，假定接入网由接入群组管理。接入群组将执行需求替换和优化过程，直到需求被提升到(一个或多个)核心集群为止。所得到的需求将被呈现给核心群组作为一组要求。这些将最终被一组LSP所满足，这组LSP随后被反馈到需求替换和优化过程中，该过程随后可以完成接入LSP的供应或布置。在某些场景中(例如在VoIP网关的情况下)，可以接受这些核心需求要求被LSP的集合所满足，以分散负载。
因而，如上所述，各种算法可用于以一种满足需求布置的优化的方式分解网络拓扑。接入树很容易标识，在某些情况下，接入树可能足以产生易处理的问题。对于那些网络的接入元素在结构上更加复杂的示例，开发出了基于双连接集群的标识的方法。在这种情况下优化过程被更多地涉及到，但是允许解决丰富得多的网络集合。为了将集群与管理边界对齐，并且为了分割对于整体优化来说仍然太大的个体成分，引入了虚拟连接节点。当然，可能存在这些技术中的任何一种都不足够的某些网络。
上述优化策略是基于开发瓶颈节点的，或者自然地发生在网络中，或者是人工创建来帮助分解过程的。这里存在明显的矛盾，因为从路径保护的角度来看，是不希望有瓶颈的。多个节点可能需要被分组，并且链接到虚拟节点中，从而允许物理级别的冗余性，同时对于需求优化和替换过程来说看起来像单个对象。分级结构还能够用于简化路径恢复问题。
在虚拟网络节点的引入可以允许多接入网络与网络核心解耦合的同时，它也使得任何优化后处理变得复杂，例如在发起于多接入网络中的需求被发起在网络节点处的需求替换的情况下。如果多接入网络具有进入核心的多个进入点，则在优化过程期间，网络节点最终将被当作核心的一部分。需求替换和优化过程将计算一条或多条路径以承载发起于网络节点处的需求。但是该节点并不实际存在，因此这些路径不能被简单地映射到LSP。这些路径的每一条中的第一跳将是核心内的实际路由器，因此该路由器可用作与路径相关联的LSP的出口。原始需求将以隧道方式经过这些LSP，如同在点对点情形中一样。
上述实施例提供了对于优化需求的问题(尤其是对于复杂的接入网)的解决方案。该实施例的装置和方法能够从这些需求中推断出渡过核心的LSP的一组要求。在已经优化了核心LSP的情况下，它们就可用于路由接入LSP。
应当意识到，尽管只详细描述了本发明的一个特定实施例，但是本领域技术人员可以进行各种修改和改进，而不脱离本发明的范围。
权利要求
1.一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，每个需求包括源节点、目的地节点和至少一个需求参数要求，所述方法包括a)将网络的节点和链路划分为链路和节点的一组集群；b)对该组集群施加分级树结构，以使得任何一对集群在其间都具有经由最近公共祖先的唯一路径；c)通过仅在所述分级树结构中的所有后代集群都已被处理之后才处理每个集群中的需求，来确定所有需求的最优路径以使得所述路径满足所述至少一个需求参数要求，所述对于每个集群的处理包括i.将每个需求分割为集群内需求和集群间需求，后者在适当情况下才存在，在所述集群内需求中，所述源和目的地节点处于同一集群中，在所述集群间需求中，所述源和目的地节点处于不同集群中；ii.确定所有集群内需求的最优路径，以便满足所述至少一个需求参数要求；以及iii.将所有集群间需求向上传递到所述分级树结构中的下一集群，以作为其中的需求进行处理。
2.如权利要求1所述的优化网络中的需求的路由的方法，还包括将与已经被优化的路径的网络成本有关的信息向上传递到所述分级树结构中的下一集群，以使得在确定仍要优化的集群内需求的最优路径时，可以利用已经使用的网络成本。
3.如权利要求2所述的优化网络中的需求的路由的方法，其中所述网络成本包括针对特定的需求参数要求导致的成本。
4.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述至少一个需求参数要求包括最大延迟要求。
5.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述至少一个需求参数要求包括流量类别要求。
6.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述确定所有需求的最优路径的步骤包括基于至少一个网络参数要求确定最优路径。
7.如权利要求6所述的优化网络中的需求的路由的方法，其中所述至少一个网络参数要求包括流量密度要求。
8.一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，所述方法实质是这里参考附图所描述的方法。
全文摘要
本发明涉及用于分组交换通信网络中的需求的优化的方法，尤其是(尽管并非排他性地)用于多协议标签交换(MPLS)分组交换通信网络中的需求优化的方法。本发明提供了一种能够使诸如路由器之类的网络节点被集群成成分的方法，其中各个成分按分级方式组织，并且网络“核心”位于该分级结构的根处。发起或终止于核心外部的成分处，但是穿越核心的需求被发起和终止于核心成分内部的需求临时替换。在优化了所得到的一组需求后，然后示出如何使用解决方案来满足原始需求。多接入网络导致某些复杂因素，并且这些复杂因素被考虑到了。另外，已经开发了进一步的需求替换方法，其考虑到了复杂的接入情形。具体而言，如上所述，已经考虑到了这样的情形即存在现有的路由器的划分，例如划分为核心和接入路由器，这一点需要被遵循。
文档编号H04L12/56GK101035069SQ200710005659
公开日2007年9月12日 申请日期2007年3月8日 优先权日2006年3月9日
发明者凯文·米切尔 申请人:安捷伦科技有限公司
技术领域：
本发明涉及用于优化网络中的需求(demand)路由的方法和装置，具体而言(尽管并非排他性地)，涉及用于诸如多协议标签交换(MPLS)分组交换通信网络之类的分组交换通信网络中的需求优化的方法和装置。
背景技术：
MPLS被用在通信网络中，具体而言用在异步传输模式(ATM)和因特网协议(IP)网络中以提供附加特征，例如对路由的精确控制，允许改善客户服务。MPLS最初被开发用来增强性能和网络可扩展性。IETF(因特网工程任务组)内的工作组进行该主题的标准化工作，这记载在“注释请求”(RFC)中。
如所公知的，在分组交换网络中，数据分组被路由经过从起始点到目的地点的多条链路。链路通过路由器耦合在一起，路由器接收分组，并依赖于各种因素(当然包括分组的目的地点)判定用哪一条链路来发送分组。然而，路由器还可以基于链路上的流量，并且在某些情况下基于数据的特定分组的优先级来判定如何路由特定分组。另一方面，在MPLS网络中，特定的传入分组在分组经过网络或经过网络的特定区域的路由的起始之处，被标签边缘路由器(LER)指派以一个“标签(label)”。被指派给分组的标签提供了关于分组经过网络所要采取的特定路由的信息。因而，分组被沿着标签交换路径(LSP)从一个标签交换路由器(LSR)转发到下一个LSR，其中每个LSR仅仅基于标签的内容作出转发判决。在每一“跳”处，LSR剥离现有的标签并施加新的标签，新的标签告诉下一LSR如何转发分组。
由于沿着标签交换路径流动的流量由在LSP的入口节点处施加的标签定义，因此这些路径可被当作隧道，这种隧道处于正常的IP路由和过滤机制之下。当LSP被以这种方式使用时，其被称为LSP隧道。
LSP隧道允许实现与网络性能优化有关的多种政策。例如，LSP隧道可被自动或手工地路由以避开网络故障、拥塞和瓶颈。此外，在两个节点之间可以建立多条平行的LSP隧道，并且两个节点之间的流量可以根据本地政策被映射到LSP隧道上。
为了有效使用可用网络资源，需要流量工程。然而，为了能够作到这一点，必须获得对网络上的流量模式以及可能存在的任何问题，例如网络故障、拥塞和瓶颈的理解。完成这一点的一种方式是监视MPLS网络中的链路。这确保了预定义的服务质量(QoS)水平和服务水平协议(SLA)得以满足。
需求通常代表对于入口节点和出口节点之间的一定量的带宽的要求(requirement)，经常具有关联的流量类别或QoS要求。需求来自于多种源。对供应高带宽视频链路的请求可视为一个需求。另一种需求源是从入口到出口跨核心网络的聚集“微流”，这种流具有公共流量类别，即，需求可能承载单个高带宽流，或者由许多更小的流形成。流量类别利用诸如最大延迟或成本之类的参数约束可用于满足需求的可接受路由。在某些情况下，对于带宽的需求(具有某一QoS)随时间的变化将是完全可预测的，以至于流量可被指派给MPLS路径，然后可为这些路径确定使拥塞最小的最佳路由。只要带宽要求的可变性没有过量，与在线精细调节的使用(其是为了调节“运行时”的保留(reservation))相耦合的离线路径布置就可以产生有用的网络优化策略，例如在白皮书“Auto-bandwidthallocator for MPLS traffic engineering”，Cisco 2003中所讨论的。离线和在线需求优化一般是由于不同的原因并且在不同的时间尺度内发生的，其中每一种优化使用不同的机制。
ATM网络先前已被用在网络核心内，并且离线工具已被开发出来以优化经过ATM网络“云”的路径的路由。这些工具迅速被改动以支持经过MPLS云的带宽保证LSP的离线优化。给定小规模的典型核心网络，该优化问题还是相当容易处理的。主要的约束是需求一定不能被分割。它们代表了聚集流的集合，很难将其分割为跨多条路径，而不在各个流内引入不必要的分组重排。
流之间服务区分的需要近来已变得越来越重要，这是因为操作者正努力找到有利可图的收入流。然而，关于可以实现多少服务区分是有限制的。一种方法是使用MPLS来提供跨网络的多条路径，然后基于其流量类别向这些路径指派流。然而，这可能将额外的复杂度引入到压力已经很重的网络的一部分中。
近年来，MPLS边界已经逐渐移出核心外，移入网络的接入部分(被称为接入网)中。这允许在分组到达核心之前对分组进行分类并指派给LSP，利用隧道传输来选择跨核心的期望路径，并且最小化核心路由器必须支持的信令和状态。在更复杂的场景中，其还允许操作者选择跨接入网自身的不同路径。
对于任何离线优化而言，该趋势具有若干后果。MPLS云的大小不再局限于核心网络的大小。对于任何优化工具(优化器)，这产生了严重的扩展问题，要求开发出将问题分解为某种更加易于管理的问题的技术。发起于接入层内的流量一般比起核心内的流量来说聚集度要低，因此表现出更大的波动。这使得难以识别足够持久和稳定以至于值得进行离线路由的LSP。
诸如在白皮书“Traffic optimizer product overview”，Cplane 2003和“IP/MPLSViewIntegrated network planning，configuration management &performance management”，WANDL 2002中描述的系统允许操作者优化跨网络核心的MPLS需求。其假定将网络按预定义划分为接入和核心路由器，因而随后要优化的需求则限于核心。其他需求可能发起于接入网中，例如基于IP的语音(VoIP网络)中的那些。关于为何应当不同地对待“接入网”优化问题和等同的核心问题，有若干个原因。
一个原因是全局地优化跨越许多路由器的大量需求在计算上是非常昂贵的。随着需求和/或路由器数目的增大，这一成本迅速增大。如果要实现现实的优化时间，则将问题分解为更简单问题的集合是必要的。
第二个原因是许多组织使用不同的人群组来管理核心和接入网。即使可以跨整个云路由需求，也可能由于这些管理性的划分而无法部署这种解决方案。更好的方法可能是使用接入需求来构造用于支持该流量所必需的核心需求的一组要求。这些要求随后可以被传递到处理网络核心的优化的群组(核心群组)，核心群组可以利用传统的或新的优化技术优化这些需求的布置。处理网络的接入部分的优化的群组(接入群组)将使用针对这些要求的解决方案来建立LSP以支持原始需求。从一组接入需求投射到核心上的要求在性质上可能与一组传统的核心需求相当不同，因而可能要求不同的核心优化工具。
另一个原因是由于这样的事实逐跳(hop-by-hop)供应跨入口和出口之间的整个路由的LSP可能是效率不高的。沿着路途的每个路由器将需要处理保持LSP存活所必需的信令流量，并且保留路由器内的状态。定义跨核心的一组LSP，然后使用这些作为发起于接入网中的永久LSP的隧道可能是更加有效的。然后，只有接入路由器将存储特定于接入LSP的状态。
优化跨网络的需求布置在计算上是昂贵的。有两种主要的方法来解决该问题(该问题在本领域中被称为多物(multi-commodity)流问题)，基于边缘的策略和基于路径的策略，这两种方法也是本领域中已知的。
在基于边缘的策略中，线性程序尝试计算由网络中的每条链路承载的每个需求的量。在最坏情况下，对于完全的需求网格以及高度相连的网络图，将存在0(n2)个需求和0(n2)个边缘。在2003年2月University ofWürzburg的Institute of Computer Science的Tech.Rep.304中发表的作者为Khler，S.和Binzenhfer的论文“MPLS traffic engineering in OSPF networks-a combined approach”包含了五个大小增大的示例性拓扑。还可以证明，随着网络大小的增长计算时间迅速地增加。当需求具有与其相附着的附加QoS约束时，基于边缘的策略具有另一个缺点。由优化器找到的路径可能不满足例如延迟或跳长度之类的约束，导致解无效。在优化过程期间增强这些约束的尝试迅速地导致不易处理的模型，即使对于小的网络也是如此。因此，基于边缘的方法最适合于具有不严格的QoS约束的需求，例如尽力而为流量。
另一种方法可以是对于每一需求首先识别一组可能的路径，每条路径满足QoS约束。然后可以使用线性程序来计算每条路径应当承载多少需求。如果只有很小数目的路径被用于一个需求，则优化问题的大小可以限制在易处理的范畴。不足之处在于该解决方案与路径的选择有关。如果路径的数目增大，则为了增大找到最优解决方案的机会，优化时间增长得非常迅速，尤其对于高度相连的网络图而言更是如此。
对于具有严格QoS属性的需求，最佳策略可以是使用基于路径的方法，并且希望每个需求的有效路径的数目较小。但是随着网络大小的增长，迅速到达了优化时间变得不易处理的阶段。对于基于路径的方法而言，存在经过接入网的多条路径的情形也产生了困难。利用类似于2001年Liu，C.和Ramakrishnan，K.C.的“A*pruneAn algorithm for finding kshortest paths subject to multiple constraints”，INFOCOM.743-749中所公开的A*Prune之类的算法，可以看出大多数路径共享跨核心的公共子路径。在许多情况下，为了找到针对优化问题的好的解决方案，要求路径中具有更多的可变性。
在典型的骨干网中，可能有上百或更多个节点。即使单个流量类别(在每对设备之间有需求)也生成了直接优化起来会非常昂贵的问题。看起来很明显，需要找到用于简化需求布置问题的(一种或多种)装置和方法(如果这种规模或更大规模的问题可以被恰当地处理的话)。
发明内容
因此，本发明的目的是提供一种用于优化网络中的需求的路由的方法，该方法克服了，或至少减轻了现有技术的缺点。
因此，本发明提供了一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，每个需求包括源节点、目的地节点和至少一个需求参数要求，该方法包括a)将网络的节点和链路划分为链路和节点的一组集群(cluster)；b)对该组集群施加分级树结构(hierarchical tree structure)，以使得任何一对集群在其间都具有经由最近公共祖先的唯一路径；c)通过仅在分级树结构的同一分支中的所有较低集群都已被处理之后才处理每个集群中的需求，来确定所有需求的最优路径以使得这些路径满足至少一个需求参数要求，所述对于每个集群的处理包括i.将每个需求分割为集群内需求和(如果适当的话)集群间需求，在集群内需求中，源和目的地节点处于同一集群中，在集群间需求中，源和目的地节点处于不同集群中；ii.确定所有集群内需求的最优路径，以便满足至少一个需求参数要求；以及iii.将所有集群间需求向上传递到分级树结构中的下一集群，以作为其中的需求进行处理。
在一个实施例中，该方法还包括将与已经被优化的路径的网络成本有关的信息向上传递到分级树结构中的下一集群，以使得在确定仍要优化的集群内需求的最优路径时，可以利用已经使用的网络成本。
网络成本可以包括针对特定的需求参数要求导致的成本，所述特定需求参数要求例如是流量类别要求，例如最大延迟要求。
所述确定所有需求的最优路径的步骤可以包括基于至少一个网络参数要求(例如流量密度要求)确定最优路径。
现在将参考附图以示例方式更完全地描述本发明的若干实施例，在附图中图1示出了根据本发明第一实施例的用于优化网络中的需求的路由的装置的示意图；图2示出了描述包含在图1的装置中的网络结构分析器的操作方法的流程图；图3示出了网络的示意图；图4的图示出了对图3所示的网络执行的双连接成分(component)分析的结果；图5的图示出了将树合并规则应用到图4的结果的结果；图6的图示出了将分级树结构施加到图5的结果的结果；
图7的图示出了根据本发明第一实施例的简单的需求替换和优化示例；图8示出了根据本发明第一实施例的出口集群的需求分割过程；以及图9示出了图1的装置的需求替换和优化操作的流程图。
具体实施例方式
因而，如上所述，希望能够优化电信网络中的需求的路由以增大网络的容量。在第一实施例中，本发明提供了一种用于执行这种优化的方法和装置，这是通过以下步骤实现的分析网络并虚拟地将路由器或节点组织为集群，随后集群被以分级方式组织，其中网络的“中央核心”位于该分级结构的根处。
因而，图1是示出了根据本发明第一实施例的需求优化器的体系结构的示意图。需求优化器51包括输入处理器(handler)53，输入处理器53经由输入链路52接收网络结构的细节和要优化的需求。输入处理器53经由链路54将网络结构细节和需求传递到存储器59。网络结构分析器55经由双向链路63耦合到存储器59，并且执行网络结构的分析，这将在下面进一步描述。需求管理器57也经由双向链路60耦合到存储器59，并且经由链路56耦合到网络结构分析器55。输出处理器61经由链路58耦合到存储器59，并且允许外部经由输出链路62访问结果。输出处理器61可以在例如GUI(图形用户界面)上提供结果。需求优化器51可以实现在Unix机器上，但是本领域技术人员应当清楚，其也可以以任何其他合适方式实现。输入处理器53也可以接收用户配置输入，这将在下面进一步讨论。
图2示出了描述结合在图1的需求优化器中的网络结构分析器的一般操作的示意性流程图，其开始于点“S”，结束于点“F”。因而，一般，首先分析网络结构以将节点划分为若干集群(见要素C1)，接着在要素C2中对这些集群施加树状分级结构。如下更完整地描述，很清楚，在分级的树结构中，有若干个分支，一个分支中的每个集群沿核心方向连接到单个“父”集群，该“父集群”又沿核心方向连接到进一步的“祖父”集群(如果需要的话)，就这样一路返回到核心(或“根”)集群自身。为了优化所有集群，优化从后代集群(descendent cluster)向祖先集群(ancestor cluster)进行。“后代”集群被认为是在任何特定的树中离核心集群最远的集群。因而，首先确定并优化最年轻的未优化集群(见要素C3)，然后确定并优化另一个最年轻的未优化集群。这样，一个集群只有在其所有“后代”集群都已被优化之后才被优化。
集群的优化涉及将在该集群中具有起始点或目的地点的任何集群间需求分割为一对需求，其中一个是集群内需求(两个端点都在该集群中)，一个是集群间需求(见要素C5)。集群内需求被优化，并且集群间需求被在树状分级结构中向上传递到特定集群的父集群，在父集群处它们被当作是该集群中的需求。然后在要素C6中确定是否所有的集群都已被优化。如果是，则过程在点“F”结束。如果不是，则过程移回要素C3，在C3处找到分支中的另一个最年轻的未优化集群。因而，该过程将从分级树结构的外围开始向核心集群优化所有集群，直到所有集群都已被优化为止。
因而，为了分解网络以将节点划分为若干集群，必须分析网络。一个集群一般是紧密连接的节点和其间的链路的群组，其中集群自身松散地连接到紧密连接的节点的另一个集群。每个集群将利用一个或多个连接节点(connecting node)相接合，这一个或多个连接节点将该集群连接到另一个集群，因而连接节点可被认为是这两个集群的一部分。当然，在某些情况下，集群可以只具有一个或多个连接节点。
为了更好地描述图2的要素C1，图3示出了具有多个节点n1、n2、n3、...n26的简单网络的示意图。节点n1...n26通过链路13以各种方式相连以形成网络。如上所述，首先分析网络以将节点划分为节点集群。可以使用任何类型的合适的集群分析。例如，可以使用的一种已知类型的分析是双连接成分分析。然而，本领域技术人员将会清楚，作为替代，也可以使用任何合适的集群分析技术，例如主要成分(Principal Components)。图4示出了对图3的网络执行的双连接成分分析的结果。
为了执行双连接成分分析，使用了下面的规则
◆连接的网络中的节点n在以下情况下是连接节点(connectionnode)从网络中删除节点n，以及删除到节点n的所有链路，会使得网络断开连接，成为两个或更多个非空部分；◆当且仅当一个网络(部分)不包含连接节点时，这个网络(部分)是双连接(bi-connected)的；◆一个网络在以下情况下是最大双连接(maximally bi-connected)的当且仅当该网络不具有其他包含最大双连接的网络部分的所有节点和链路的双连接部分。最大双连接的网络部分是双连接的集群(bi-connectedcluster)；◆两个双连接的集群可以具有至多一个公共节点，并且该节点是连接节点；以及◆具有来自多于一个集群的链路的节点是连接节点。
在执行了双连接成分分析之后，网络被划分为多个集群，编号为C0、C1、C2、...C12，这些集群由连接节点相连，如图4所示。因而，如表1所示，每个集群包含来自图3的网络中的不是连接节点的某些节点，以及形成其连接的每个集群的一部分的连接节点(为了看起来方便，连接节点被示为部分在其连接的每个集群的外部)，如下所示
表1 双连接成分分析的结果例如，集群C0包含原始节点n5，n6，n7，n8，n9，n10和n11，而集群C4和C5分别只具有连接节点n10，n15和n21以及n4和n5。因此，来自图3的网络的所有节点要么完全在集群内，要么是连接节点。
尽管不是必要的，但是最好通过找到可以合并在一起的集群来进一步简化该集群结构。很清楚，树结构中的节点很容易处理，这是因为在树中的任何两个节点之间有唯一的路径。因而，布置需求是意义不大的，因为没有其他的选择。由于通常的双连接成分分析将把树分割为集群的分级结构，因此将其分割为大量的小集群并不是总是高效的。因此，进一步处理这些结果以查找已经从树子结构生成的集群并将这些合并为更大的结构可能是有用的(高效的)，尽管不是必要的。或者，可以使用其他的集群化技术，这些技术不需要这种进一步的处理步骤。例如，可以改变双连接成分分析，以使其在进行时执行这种合并。可以重复使用第一树集群合并规则以合并兄弟(sibling)成分。
图5的图示出了将树合并规则应用到前述结果的结果。在该图中，符号“x∪y”被用于表示包含集群“x”和“y”的并集的集群。例如，C7∪C8图示了集群“C7”和“C8”的并集。
图5中所示的集群图相对于图3的节点网络提供了某种简化，但是仍然需要识别出核心集群，即，网络的核心(这与图2的步骤C2有关)。核心集群可以按多种不同方式确定。挑选最大集群(例如包括其连接节点)看起来似乎是合理的，只不过对于非常大的网络，可能存在比“真实”核心更多的大节点。类似地选择到所有其他集群的最大路径长度最小的集群看起来是合理的，因为其往往会找出树的“中心”处的集群。然而，具有许多跳的网络往往会使这种方法失灵，这是因为接近这种集群链的末端的集群更有可能被不正确地识别为核心集群。
更加健壮的解决方案是选择到所有其他集群的平均路径长度最小的集群。对于参考图5给定的示例而言，平均路径长度在表2中给出。
表2 来自每个成分的平均路径长度在表2中，已经算出了从每个集群到下一集群的跳数，即，已经忽略了连接节点。利用平均长度作为量度将导致集群C0或集群C4被选为根。由于这两个集群具有相同的平均路径长度，因此选择哪一个集群并不是实质性的问题，为了下面的讨论，集群C0被选为根或核心集群。给定对根集群的这一选择，可以对树链路进行排序，以引入向核心移动和远离核心移动的概念，如图6所示，因而提供分级树结构。
如图6所示，网络核心被示为集群C0，集群C0经由连接节点连接到其他集群。如所说明的，利用该方法仍然存在可能选择“错误”的根的可能性。因此，需求优化器突出了其“认为”构成核心集群C0的(一个或多个)路由器。如果这是不正确的，则需求优化器向用户提供选择替换路由器的机制。然后，包含该路由器的集群可被当作核心集群。
在分级树结构已被施加在网络上的情况下(这是虚拟意义上的，因为很显然，实际的网络不受影响)，需求优化过程现在可以发生。简而言之，策略是利用各自跨越单个集群的许多其他需求来分解跨越网络中多于一个集群的需求。此外，这种解决方案应当处理这样的情形即在到达核心之前需要穿越多个集群。对于这些集群中的每一个应当执行优化，因为现在将有多条路径跨过这些集群(中的某一些)。在详细描述该优化过程之前，应当注意◆所有有根(即，分级的)树将具有在核心(根)处的一个集群和在叶子处的多个集群，其中相邻的集群被连接节点彼此分离；◆对于从入口到出口的每个需求，存在跨集群树的唯一路径；◆单个需求在集群树中具有相同的入口和出口节点；◆如果需求的路径具有长度1，则该需求是本地的，否则是非本地的。对于处于连接节点处的单个需求的退化情形，允许长度为0；◆需求的入口集群是路径中的第一集群；◆出口集群是此路径中的最后一个集群；◆如果集群C处于需求的路径中，并且既不是入口集群也不是出口集群，则该需求穿越集群C；◆与每一集群C相关联的是其路径包括集群C的一组需求。每一集群还具有一组子集群，可能为空。这些是经由单个连接节点连接到集群C的树中的集群C的后代。
很明显，如果与一个集群相关联的所有需求对于该集群来说都是本地的，则需求优化器可以很容易跨过该集群优化这些需求，而不考虑任何其他集群。在遇到非本地需求的情况下，所采取的策略是将其分解为两个需求，其中一个是本地的，另一个在分级集群树中的更高处开始或结束。通过重复应用该过程，所有需求将最终变为某个集群的本地需求。更准确地说，非本地需求被“提升”到分级集群树中入口和出口集群的最低公共祖先。
该过程中的复杂因素在于附着到每个需求的QoS约束。这些限定了需求的可接受路径。当一个需求被分解为在树中的更高处开始或结束的一个需求时，必须计算新的QoS约束，其考虑了从原始端点到达新的端点的成本。如果集群内的所有节点都以树的方式链接在一起，则这可以在单个步骤中完成，因为经过这些集群的路径是唯一的，因此计算穿越这些路径的成本是意义不大的。但是在更一般的情况下，可能有多条路径经过每个集群，这就提出了应当使用哪一种成本的问题。
在图7中示出了一个示例，其中具有入口节点ni和出口节点ne的需求d的最低公共祖先是集群33(Ca)。因而，从图中可见，存在唯一的集群序列，该序列必须被需求穿越，以从集群33中的入口节点ni开始到达集群31(Ca)。当然，存在另一个必须被穿越以从集群31(Ca)到达集群32中的入口节点ni的集群序列。此外，从节点ni到集群31(Ca)的路径将经由某一连接节点36(APe)进入集群31(Ca)，并经由另一连接节点37(APi)离开集群31(Ca)。很明显，这两个连接节点36和37必须是不同的，因为如果它们是相同的，则形成集群36的左孩子的集群将是最低公共祖先，而不是集群31自身。原始需求30(d)被示为在集群33和32之间。
因而，为了优化需求30，在集群33中考虑它，并将它分割为本地(集群内)需求和集群间需求。分割需求的过程将参考图8进一步描述，图8示出了入口集群的需求分割过程。尽管需求可以在入口和出口集群中的任一处或者在这两处进行分割，但是将仅参考入口集群进一步描述该过程。
因而，发起于集群33中的入口节点ni的需求d可被分割为两个子需求，即本地需求dl和余者，即集群间需求dr。然后，本地需求dl随后可以与集群33中的所有其他集群内需求一起被优化，而集群间需求dr被向上传递到树中的下一集群34。当然，原始需求d具有与其相关联的QoS约束。这可能约束了沿着用于承载需求d的流量的任何路径可允许的总延迟。很明显，这种限制必须在子需求dr和子需求dl之间进行分割。给予跨需求dl的路由的自由度越大，可用于路由子需求dr的自由度就越小，反之亦然。如果从集群33中的入口节点ni到集群33和集群34之间的连接节点35有唯一的路径，则没有选择余地。原始需求d的成本被该路径固定，因此这仅能被从原始成本中减去以确定用于需求dr的QoS约束。然而，在更一般的情况下，将存在许多种分割QoS约束的方式。需求替换和优化过程所采取的策略可以是首先解决包含入口节点ni的集群33的优化问题。可以给予诸如子需求dl之类的需求以优先处理，以增大它们被分配以经过集群33的最短可能路由的可能性。一旦一条路径被指派给子需求dl，这就可用于计算用于子需求dr的剩余QoS配额。当方向相反并且为原始需求d处理出口集群时，可以使用类似的策略。在已经确定了子需求dr所要求的QoS约束的情况下，其布置随后可被托付给父集群33。一旦整个树已被优化，被选择用于子需求dl和子需求dr的路径就可用于确定用于原始需求d的路径。
因此，可以看出，需求d或者将被指派以一组路径(在本地需求的情况下)，或者被分割成一对子需求(dl，dr)。需求替换和优化过程的目的是以一种满足需求的QoS约束的方式设置本地需求或子需求。这将参考图9更完全地描述。然而，应当提到，仅仅给需求指派一组路径可能是不够的；还需要知道应当给这些路径中的每一条分配多少带宽。然而，为了说明的方便，该细节在下面的内容中被忽略。
图9示出了描述需求替换和优化过程的要素的流程图。需求替换和优化过程的目的是为系统中的所有需求限定路径。在集群的优化期间，本地需求将被分配以一条或多条路径。在非本地需求的情况下，与路径的关联是由子需求dl，dr隐性限定的。最初所有需求将不被处理。因此，每个集群将直到队列为空时才被处理。换句话说，如果需求是非本地的，则其必须经由集群的唯一父连接节点离开或进入该集群。
需求替换和优化过程是由下面的要素实现的，参考图9，该过程开始于要素SB1构造队列。通过执行集群树的后向穿越(post-order traversal)构造要处理的所有集群的队列Q，其中跳过了连接节点。后向穿越是用于探索树结构的一种算法，其在访问树中的每一集群的孩子之后，访问该集群。
B2定义集合。构造集合U作为所有未处理需求的集合。
B3Q为空？然后检查队列以查看其是否具有任何未处理集群。如果Q非空则继续进行到B4。如果为空则继续进行到B14。
B4取得队列中的第一集群。取得队列中的第一集群进行处理，过程移到B5。
B5所有需求是本地的？被处理的集群中的所有需求都是本地的？如果是，则转到B11。如果不是，则必然有集群的父连接节点，然后移到步骤B6。
B6取得第一非本地需求。取得第一非本地需求进行处理，过程移到B7。
B7集群是出口？对于考虑的非本地需求而言，被处理的集群是入口集群或出口集群。如果是入口集群，则过程移到B8；如果不是，则移到B9。
B8创建本地子需求。如果是入口集群，则创建从入口节点ni到父连接节点的新的本地子需求dl，过程移到B10。
B9创建远程子需求。如果不是入口集群，则创建从父连接节点到出口节点ne的新的远程子需求dr，过程移到B10。在新的子需求的图(map)中作出一个条目。当向图添加新条目时，从映射中去除具有相同关键字(key)的任何现有条目是很重要的。
B10更新集合。通过删除刚刚已被分割的需求来更新要处理的需求的集合U，并且向集合添加新的远程子需求，即集群间子需求。过程然后返回B5，检查是否还有任何要处理的非本地需求。
B11计算路径集合。在这时，被处理的集群中的所有需求都是本地的，因此对于这些需求中的每一个可以计算一组路径。在一般情况下，需要解决优化问题。本地需求的路由成本需要被最小化，以给予相应的继续子需求以最大路由自由度。现在使用基于路径的优化策略，该策略开始于向本地需求指派最短“权重”路径(或多条路径)，并且向剩余需求指派更完全的一组路径。在考虑单个属性(例如跳数)的情况下，这意味着路径是按照最短路径长度来应用的。如果权重是成本，则路径将按照最小成本来应用。如果不能满足所有需求，则这组路径需要被加宽，并且需求替换和优化过程被重复。如果需求替换和优化过程允许多条路径被指派给一个需求，则灵活性限于非本地需求。如果不能满足一个需求(例如由于QoS度量太严格)，则这组路径将为空。
B12更新远程子需求。现在利用与原始需求相同的属性更新在B9中创建的远程(非本地)子需求，只不过QoS约束减少了分配给相应本地子需求dl的路径的权重。过程随后移回B3，检查是否还有任何未处理的集群。
B13路径构造。如果所有集群都已被处理，即，队列为空，则过程移到B13。由于现在所有需求都已被优化，因此对于经过所有集群的所有需求都可以构造路径。
应当意识到，如上所述的需求替换和优化过程的有序程度可能大于必要的程度。取代使用队列，一个集群可以与集群树中的其他集群并行地被处理。
理想情况下，随着需求替换和优化过程沿集群树向上移动，需求应当被利用公共属性聚集。例如，当需求被添加到父集群时，可能已经存在一个去往相同目的地(或来自相同发源)的需求，其具有兼容的流量类别。在这种情况下，可能只需要增大现有需求的带宽要求，而不是添加第二需求。集群被处理的顺序也可能影响这种聚集的潜在可能。我们推测，尝试优化隧道产生的穿越顺序也可能增大需求聚集的可能性。
许多网络操作者跨多个组织边界地分割网络管理。将集群与每个组织对齐是很重要的，因此需求替换和优化过程并不尝试在多个组织群组的控制下优化路由器的集合。注意，这并不暗示只应当构造与组织实体一样多的集群，而是必须确保没有集群被跨这些实体地分割。
先前已经讨论了集群合并，上面讨论了集群分割。给定预定义的路由器分组，则需要自动完成由双连接集群分析标识的集群的合并和分割，因此所得到的集群遵循该分组。以上实施例的需求替换和优化算法尝试布置所有需求。然而，当网络被沿着管理边界划分时，该方法可能需要改进。
例如，假定接入网由接入群组管理。接入群组将执行需求替换和优化过程，直到需求被提升到(一个或多个)核心集群为止。所得到的需求将被呈现给核心群组作为一组要求。这些将最终被一组LSP所满足，这组LSP随后被反馈到需求替换和优化过程中，该过程随后可以完成接入LSP的供应或布置。在某些场景中(例如在VoIP网关的情况下)，可以接受这些核心需求要求被LSP的集合所满足，以分散负载。
因而，如上所述，各种算法可用于以一种满足需求布置的优化的方式分解网络拓扑。接入树很容易标识，在某些情况下，接入树可能足以产生易处理的问题。对于那些网络的接入元素在结构上更加复杂的示例，开发出了基于双连接集群的标识的方法。在这种情况下优化过程被更多地涉及到，但是允许解决丰富得多的网络集合。为了将集群与管理边界对齐，并且为了分割对于整体优化来说仍然太大的个体成分，引入了虚拟连接节点。当然，可能存在这些技术中的任何一种都不足够的某些网络。
上述优化策略是基于开发瓶颈节点的，或者自然地发生在网络中，或者是人工创建来帮助分解过程的。这里存在明显的矛盾，因为从路径保护的角度来看，是不希望有瓶颈的。多个节点可能需要被分组，并且链接到虚拟节点中，从而允许物理级别的冗余性，同时对于需求优化和替换过程来说看起来像单个对象。分级结构还能够用于简化路径恢复问题。
在虚拟网络节点的引入可以允许多接入网络与网络核心解耦合的同时，它也使得任何优化后处理变得复杂，例如在发起于多接入网络中的需求被发起在网络节点处的需求替换的情况下。如果多接入网络具有进入核心的多个进入点，则在优化过程期间，网络节点最终将被当作核心的一部分。需求替换和优化过程将计算一条或多条路径以承载发起于网络节点处的需求。但是该节点并不实际存在，因此这些路径不能被简单地映射到LSP。这些路径的每一条中的第一跳将是核心内的实际路由器，因此该路由器可用作与路径相关联的LSP的出口。原始需求将以隧道方式经过这些LSP，如同在点对点情形中一样。
上述实施例提供了对于优化需求的问题(尤其是对于复杂的接入网)的解决方案。该实施例的装置和方法能够从这些需求中推断出渡过核心的LSP的一组要求。在已经优化了核心LSP的情况下，它们就可用于路由接入LSP。
应当意识到，尽管只详细描述了本发明的一个特定实施例，但是本领域技术人员可以进行各种修改和改进，而不脱离本发明的范围。
权利要求
1.一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，每个需求包括源节点、目的地节点和至少一个需求参数要求，所述方法包括a)将网络的节点和链路划分为链路和节点的一组集群；b)对该组集群施加分级树结构，以使得任何一对集群在其间都具有经由最近公共祖先的唯一路径；c)通过仅在所述分级树结构中的所有后代集群都已被处理之后才处理每个集群中的需求，来确定所有需求的最优路径以使得所述路径满足所述至少一个需求参数要求，所述对于每个集群的处理包括i.将每个需求分割为集群内需求和集群间需求，后者在适当情况下才存在，在所述集群内需求中，所述源和目的地节点处于同一集群中，在所述集群间需求中，所述源和目的地节点处于不同集群中；ii.确定所有集群内需求的最优路径，以便满足所述至少一个需求参数要求；以及iii.将所有集群间需求向上传递到所述分级树结构中的下一集群，以作为其中的需求进行处理。
2.如权利要求1所述的优化网络中的需求的路由的方法，还包括将与已经被优化的路径的网络成本有关的信息向上传递到所述分级树结构中的下一集群，以使得在确定仍要优化的集群内需求的最优路径时，可以利用已经使用的网络成本。
3.如权利要求2所述的优化网络中的需求的路由的方法，其中所述网络成本包括针对特定的需求参数要求导致的成本。
4.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述至少一个需求参数要求包括最大延迟要求。
5.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述至少一个需求参数要求包括流量类别要求。
6.如任何一个在先权利要求所述的优化网络中的需求的路由的方法，其中所述确定所有需求的最优路径的步骤包括基于至少一个网络参数要求确定最优路径。
7.如权利要求6所述的优化网络中的需求的路由的方法，其中所述至少一个网络参数要求包括流量密度要求。
8.一种优化网络中的需求的路由的方法，所述网络包括通过链路互连的节点，所述方法实质是这里参考附图所描述的方法。
全文摘要
本发明涉及用于分组交换通信网络中的需求的优化的方法，尤其是(尽管并非排他性地)用于多协议标签交换(MPLS)分组交换通信网络中的需求优化的方法。本发明提供了一种能够使诸如路由器之类的网络节点被集群成成分的方法，其中各个成分按分级方式组织，并且网络“核心”位于该分级结构的根处。发起或终止于核心外部的成分处，但是穿越核心的需求被发起和终止于核心成分内部的需求临时替换。在优化了所得到的一组需求后，然后示出如何使用解决方案来满足原始需求。多接入网络导致某些复杂因素，并且这些复杂因素被考虑到了。另外，已经开发了进一步的需求替换方法，其考虑到了复杂的接入情形。具体而言，如上所述，已经考虑到了这样的情形即存在现有的路由器的划分，例如划分为核心和接入路由器，这一点需要被遵循。
文档编号H04L12/56GK101035069SQ200710005659
公开日2007年9月12日 申请日期2007年3月8日 优先权日2006年3月9日
发明者凯文·米切尔 申请人:安捷伦科技有限公司
最新回复(0)