分组交换多层通信网中的动态路由

摘要

提供了一种在多层网络上对数据分组进行路由的方法，所述网络包括多个节点、一个配备有多条逻辑链路的逻辑层和一个配备有多条物理链路的物理层；每条逻辑链路对应于至少一条所述物理链路；所述方法包括如下步骤：根据所述逻辑层中的第一关键约束为每条逻辑链路分配加权值；根据所述物理层中的第二关键约束精化分配给每条逻辑链路的加权值；根据分配给每条链路的加权值，计算所述逻辑层上将起始节点连接到追踪节点以传送数据分组的路径。

说明书

技术领域

本发明一般地涉及分组交换通信网络，更具体地来说，涉及多层网络中的路由策略。

背景技术

近年来，数据通信(datacom)网络的快速发展以及此类网络，尤其是因特网上用户可用业务量的与日俱增，导致业务量的显著增长而严重影响网络的性能。

事实上，目前的骨干网体系结构(最初是为支持电话业务量而设计的)不足以支持巨大的因特网数据业务量，理想情况下应该被技术先进、最新的硬件网络所取代，所述硬件网络可提供足够的速度和带宽以适应目前和将来的数据业务量需求。

不幸的是，成本是使硬件现代化进程放慢(即使未阻碍)的主要问题：普遍共识是投资相对于预期收益太高。

因此，虽然考虑到所有关键性要求，但下一代网络(NGN)的设计仍基于传统标准。

因此，一个成功NGN的主要要求是看对目前可用硬件装置和及其可用带宽的利用，其中术语带宽是广义上的，包括通信系统的数据传输容量、链路容量、节点吞吐量等。

有效利用可用带宽可以通过业务工程解决方案实现，这就提供了以灵活、动态的方式处理网络资源，以适应随时间变化的业务需求，优化可用资源的利用率和采用有效的路由策略的可能性。

一般来说，大多数通信网络基于采用“开放系统互联(OSI)”提出、并由国际标准化组织(ISO)标准化的熟知七层体系结构的多层体系结构而设计。

七层的每一层提供一个渐进的抽象层，从层1(即物理层)至层7(应用层)，其中通过数据链路层、网络层、传输层、会话层、表示层和应用层。

再者，今天的大多数网络，包括实现因特网的网络都采用了多个熟知且广泛适用的网络层协议来进行分组路由和流量控制(在网络层上执行)，以及采用多个数据链路层协议来进行错误校验或执行使两个节点之间的连接可靠的功能。

再参照最重要的数据通信网络，因特网传输体系结构逐渐向由可以处理高业务量的光核心网络互连高吞吐量路由器的模型迁移。此外，将会发生大量业务朝IP范型的转变，包括实时和多媒体业务以及下一代移动业务。

如此巨大的数据量需要适于处理如此高的数据业务量的相应通信设施，例如采用波分复用(WDM)技术的高容量光网络。

在常规技术中，在基于IP的网络中对分组进行路由完全在网络层上完成。当数据分组到达网络节点或路由器时，节点上运行的网络层进程将分组包含的目的地地址与该节点上维护的路由表中存储的地址前缀列表进行比较。搜索最长的匹配前缀，一发现就将分组转发到与此前缀相关联的另一个节点。随后在当前节点上重复匹配进程，直到达到分组目的地地址为止。

当然，网络中可能存在若干条从起始节点到最终目的节点的路径。优化路径的计算是网络工程中的一个关键运算，它是实现高效网络性能的基础。

就此而言，在当今的多层数据网络中实际上通常可识别四层：承载应用和业务的IP层；用于业务工程的异步传输模式(ATM)层；用于传输的SONET/SDH层；以及用于提供容量的波分复用(WDM)层。

不幸的是，此类常规技术的多层体系结构存在最低公分母效应(lowest common denominator effect)，其中一个层可能限制整个网络的伸缩性，并且已经证实它们不仅成本效率低，而且为适应大业务量进行调整既困难又缓慢。

实际上，因为四个层都参与分组在网络上的实际传输，所以为优化某个层上的性能而执行的路径计算会受其它三个层特性的影响。

出于这些原因，现有技术中已因此而提出了解决在光网络上使用IP的问题的工程解决方案，即将层的数量减少到总共两个。

但是，甚至在此缩减后的体系结构中，迄今为止报告的解决方案旨在通过采用适合的范型(例如多协议标记交换(MPLS)范型)来优化因特网中的IP路由进程或提高光网络的性能。

更具体地来说，已开发了MPLS技术以减少网络路由机制中所用的时间量和计算资源。

通过在每个数据分组的网络层信息头和链路层信息头之间插入固定长度的标记，MPLS就不必执行最长前缀匹配。因此，路由器只须采用分组的MPLS标记作为路由表索引，即可容易地对输入分组作出跳决策，从而减少了将数据分组从节点转发到另一个节点所需的工作量和时间，因此提高了网络性能。有关MPLS的详细描述，参见E.Rosen等人的“多协议标记交换体系结构”(因特网草案draft-ietf-mpls-arch-07.txt；因特网工程任务组(IETF)网络工作组，2001年1月)，这些技术整体全部结合于本文中以作参考。

另一方面，涉及光网络的现有技术解决方案涉及波长路由和波长分配问题，即通常所说的RWA，此问题可以离线或在线方式解决。

在前一种情况中，采用期望的业务矩阵，它表示每对源/目的光节点(如光交接机)需要容纳的以“波长”数表示的所需连接。

在后一种情况中，根据以某种统计规律到达的请求来动态地解决RWA问题。

但是，IP/MPLS和RWA工程方法已经证实并不令人完全满意，因为一个层上的优化仍然频繁地受其它层上的临界负载或不同情况所影响。

因此，本领域需要一种有关多层网络的新策略。

发明的公开

本发明目标是提供一种利用可用网络资源以改善网络性能的方法和系统。

本发明目标内，其目的之一是提供多层网络中的动态路由策略和算法。

本发明的另一目的在于，如允许集成MPLS和光域的通用多协议标记交换(GMPLS)范型所允许的那样，基于正确地将多层网络作为整体进行评估，在多层环境中扩展已知的解决方案以及实施新的标准。

下面将会阐明，可通过一种在多层网络上对数据分组进行路由的方法来实现所述目标、目的和其它方面，所述多层网络包括多个节点、配备有多条逻辑链路的逻辑层和配备有多条物理链路的物理层；每条逻辑链路对应于至少一条所述物理链路；所述方法包括如下步骤：根据所述逻辑层中的第一关键约束，为每条逻辑链路分配一个加权值；根据所述物理层中的第二关键约束，精化分配给每条逻辑链路的加权值；根据分配给每条链路的加权值，计算逻辑层上将起始节点连接到最终节点以便传输所述数据分组的路径。

方便的是，第一关键约束可以是两条逻辑链路之间的总带宽(aggregate bandwidth)，它计算为对应物理链路的可用带宽之和，而第二关键约束可以是单条物理链路上的可用实际带宽。

有利的是，所述加权值和估算所述加权值的函数可以基于与跳计数、可用容量或链路之间的容量分布有关的信息。

根据本发明的一个更具体的方面，提供了一种在多层网络上对数据分组进行路由的方法，所述多层网络包括多个节点、配备有多条逻辑链路的多协议标记交换(MPLS)层和配备有多条物理光链路的光层；每条MPLS链路对应于至少一条所述光链路，所述方法包括如下步骤：根据所述逻辑层中的第一关键约束，为每条逻辑链路分配加权值；根据所述物理层中的第二关键约束，精化分配给每条逻辑链路的加权值；根据分配给每条链路的加权值，计算MPLS层上将起始节点连接到最终节点以便传输所述数据分组的标记交换路径(LSP)。

光层可以是任何合适的层，如波分复用(WDM)层或密集波分复用(DWDM)层。

上述目标和目的还可以通过一种在多层网络上对数据分组进行路由的网络控制程序来实现，所述网络包括多个节点、配备有多条逻辑链路的逻辑层和配备有多条物理链路的物理层；每条逻辑链路对应于至少一条所述物理链路，所述网络控制程序包括：用于根据所述逻辑层中的第一关键约束为每条逻辑链路分配加权值的方法；用于根据所述物理层中的第二关键约束精化分配给每条逻辑链路的加权值的方法；根据分配给每条链路的加权值，计算逻辑层上将起始节点连接到最终节点以便传输所述数据分组的路径的方法。

所述网络控制程序还可以包括根据预定标准，检查所计算的路径上每条逻辑链路的物理链路的实际可用性的方法以及选择逻辑链路中的物理链路的方法。

与现有技术相比，在阻塞概率和总拒绝带宽方面，按照要求权利的本发明进行管理的多层网络取得了更好的性能。

附图简介

通过以下对附图所示非限制性示例的详细说明，可清楚本发明的其它特征和优点，其中：

图1是显示示例通信网络的示意图；

图2是说明包括连接到MPLS域中标记交换路由器的多个节点和光域中的光交叉连接的示例通信网的示意图；

图3是说明两个节点之间的链路以揭示对应于一条逻辑链路的若干物理链路的示意图；

图4是说明波长占用的网络中的多个节点的示意图；

图5是说明根据本公开方法的步骤的数据流程图；

图6至图9是比较本发明所提供的用于选择物理链路的不同标准的性能的图。

实施本发明的方式

图1是说明一个示例性通信网的示意图，所述通信网个包括多个节点10至15和从起始节点10传递到最终节点15的示例性数据分组。

这些节点在两个不同层或域中进行处理：逻辑或路由层和物理层。

逻辑域中的每个节点与一个路由器(随后用相同标号表示为对应节点—)相关联，该路由器沿通往分组最终目的定址的路径将输入分组路由到下一节点。

同样地，物理域中的每个节点与一个交换机相关联，该交换机执行必要的操作，以通过选定的传输方法将输入数据分组物理上传送到下一交换机。

在逻辑域中进行处理的两节点(即源节点和目的节点)之间的通用连接称为逻辑链路，而能够连接物理域中的两个节点的实际装置称为物理链路。

每条逻辑链路至少对应于一条物理链路，其中，大多数逻辑链路实际对应于多条物理链路；每条物理链路可以在物理上将一定大小的数据分组从链路第一端的节点传输到该链路另一端的节点。

根据所公开的优选实施例，路由选择域是MPLS或GMPLS域，而物理域是光域。

因此，为清楚起见，下面将明确地参照GMPLS来详细说明本发明。但本领域技术人员容易理解，同样的发明概念一般地适用于应用于光层或物理层上的任何其它面向连接的网络体系结构。

图2是说明一种示例性多层通信网的示意图，所述多层通信网包括MPLS域中的多个标记交换路由器(LSR)10至15和光域中的多个光路由器(最好是执行波长路由得光交叉连接(OXC)20至25。为此，可采用任何类型的OXC。

MPLS域中的每个LSR 10-15与光域中的OXC 20-25之一相关联，它可以处理标记交换路径(LSP)，以在任何两个不同端点网元(这里表示为起点10和终点15)之间转发数据分组。

应注意，图2的配置是为了更好地理解本发明，并不一定反映网络的真实物理体系结构。具体来说，图2显示了MPLS路由器与OXC之间一对一的关系。事实上，即便图中只显示了位于链路端的两个OXC，连接两个MPLS路由器的链路可容易地对应于一条包括包括多条中间OXC的连接。

例如，链路41可以是OXC 20和OXC 22之间的直接链路或间接链路，其中连接两个OXC的波长经过一个中间OXC(图中未显示)，它未与对应的MPLS路由器相关联。

图2还显示了MPLS域中用于将数据分组从节点10传输到节点15的第一LSP 31、32，其对应于在节点20和节点25之间建立连接的路径41-42。

最后，图2显示了第二LSP 33、34、32(即数据分组从起点20到终点25的行程所遵循的实际路径，下文将对此予以说明)以及对应的路径43、44和42。

图3说明一条示例性链路，以揭示连接节点400和节点401的多条光纤420、421和422。接着，在图中对光纤420作了局部放大，以表示适合物理上通过链路传输数据的若干一定容量波长430的之一。

引用号410表示计算为每条物理链路上的可用单一资源之和的总关键资源，例如逻辑链路的总容量。

网络控制程序(图中未显示)负责计算数据分组从起点10通向终点15的路径。

网络控制程序通过信令协议(如OSPF协议)了解网络状态信息。对于每条链路，状态信息包括该链路的状态、拓朴、网络节点之间的连通性以及每个波长上的可用带宽。

此信息的存储根据常规方法和技术来进行，因此这里不作详述。例如，该信息可以存储在每个节点上的一个表中，该表可由对应路由器访问以对输入分组进行路由；以及由网络控制程序访问，以用于建立从网络起始点到终点的路径。

无论如何，网络控制程序必须能够访问有关MPLS层和光层的信息。在优选实施例中，采用了GMPLS范型，它允许网络控制访问有关MPLS层和光节点的信息。

图5的数据流程图500说明了根据本发明的方法和系统的操作。下文将说明此数据流程图，其中假定信息将从节点10传送到节点15，因此要设置连接这两个节点的LSP。

在方框505，通知网络控制程序，必须建立一条路径来将包含信息的一个或多个数据分组从起始节点10传输至最终节点15，在步骤510，通过考虑网络中将节点i连接至节点j的第一链路来开始对网络链路进行分析。

在步骤515-520，在逻辑层处理链路，并为其分配加权值或加权函数w(i，j)，其指示将该链路用于传输数据分组的成本，所述成本与一个或多个第一关键约束或所需资源相关。

例如，在此示例性情况中，总的可用链路带宽410可以起第一关键资源或约束的作用。

在步骤525，将具体与物理层有关的信息纳入考虑，以检查物理层可用性，即实际物理链路能否满足第二关键资源或第二约束，它可能与在逻辑层上考虑的第一资源或约束等效或受其影响。

但是，第二关键资源还可以是与IP或逻辑层状态无关，对光层的正确操作至关重要的独立约束。

在此情况中，假定第二约束是波长层次上的带宽可用性：因此在步骤530，执行检查以判断链路内是否有至少一个波长可用，以适应数据分组的实际传输。

在没有物理链路能够在物理上适合链路连接的情况下，将先前分配给该链路的加权值设为无穷大(步骤540)，这表示该链路不可用。

例如，图2显示没有物理链路可以提供在节点20和节点22之间进行数据传输所需的带宽，因此要计算的路径将不包括连接节点10和节点12的链路。

另一方面，如果一条或多条物理链路可以适应链路两端节点之间的数据传输，则根据第二资源的可用性修改先前分配给该链路的加权值并对其加以精化，而后将最终的加权值分配给该链路。因此，加权值分配同时将有关链路的汇总信息和物理资源的具体可用性纳入考虑。

最后，在步骤545，进行测试以核查该网络中是否还有更多的链路，此时处理程序跳回步骤510，并对下一条链路重复该过程。

最后，为网络中的每条链路分配一个加权值，现在网络控制程序就可以根据传统的现有技术算法计算逻辑层上的最优路径或标记交换路径。

例如，(步骤550)可以采用Dijkstra算法，该算法适合于针对一对给定的起始和最终节点，计算具有最小成本的路由。图2表示由链路33、34和32组成的最优LSP。

图5所示的数据流程图的下半部分显示了本发明的另一个方面，即适合于进一步优化从起始节点到最终节点的数据传输。

在步骤555，取LSP中的第一链路或逻辑路径，并在步骤560检查有关物理链路(在此情况中为波长)数量，物理链路可在物理上容纳数据传输。

如果有多于一条链路可用，则在步骤565应用标准来选择最合适的物理链路(下文将对此予以详述)，否则选取唯一的可用链路。

如果逻辑路径或LSP中存在多段(segment)(步骤570)，则算法跳回到步骤555，并对LSP中的下一条链路重复该处理过程。

最后在步骤575，将属于所计算的路径的链路存储在专用数据库(未显示)中，该专用数据库由网络控制程序用于在数据传输一结束时就拆除该LSP；而所选物理链路存储在存储有关物理链路状态和占用情况的信息的专用数据库中，而后过程结束(步骤580)。

更详细地说，步骤515-520的目的是为网络的每条链路设置第一加权值，用于根据在逻辑层上考虑的基于约束的量度来查找最优路由，并且该第一加权值通常对应于有关物理层的汇总信息：可用带宽通常是最相关的信息。在此阶段，如上所述，可用带宽是基于整条链路来考虑的，其计算为构成该链路的所有光纤中的所有波长上的可用空闲带宽之和。此值称为用于路由选择的总信息。

在所公开的优选实施例中，用于确定每条链路的加权值的最相关因素是跳计数和可用容量。稍后将介绍第三个因素，即容量分布。

具体而言，跳计数函数的目标是使MPLS网络中的跳数减至最小，以便将每个逻辑节点上引入的路由开销减至最小。

关于可用容量，收集链路状态信息时的可用容量的数量以C_i^AL表示。因此，1/C_i^AL表示链路提供的建立新会话的阻力的量度。链路的可用容量越大，则提供的阻力越小。

优选加权函数w(i)＝C_max^TL/C_i^AL，其中C_max^TL是网络中的最大链路总容量。

此加权函数用于定义网络中适用于单一情况(scenario)的最小阻力。

但是，本领域技术人员理解，链路上的可用带宽并未给出有关每条链路中容量如何分布的信息：C_i^AL实际上是构成该链路的所有光纤的所有空闲容量之和，但并没有提供有关实际容量在光纤中波长上如何分布的指示。

另一方面，因为一条LSP必定由一个波长承载，所以路由算法必须将此因素纳入考虑。

实际情况中，即使容量信息告知链路拥有比建立新LSP连接所需容量更多的容量，捆绑LSP的链路中仍可能不存在任何波长。

出于这些原因，步骤525-540将光层纳入详细的考虑，具体地来说，将链路中每个单一波长的实际带宽分布和可用性纳入考虑，以便找出可以实际捆绑新LSP连接的至少一个波长。

如果这种波长不存在，则将该链路的加权函数设为“无穷大”，并计算新的LSP。“无穷大”的值将防止网络控制程序选择该废弃的链路。

反之，如果有多于一个的波长可用于容纳数据传输，则网络控制程序负责根据预定的标准选择最适合的一个波长，以确保最优的网络性能。下文将参考图4对此予以详细说明，图4给出了一个说明性示例，说明由LSP的路由算法选择的四个节点

图4显示了节点20、21、22和25。为了说明的目的，每对节点之间显示有两条物理链路，每条链路显示以适当测量单位(通常为Mb/s或Gb/s)表示的空闲容量。为了简明起见，可以假定逻辑链路中的每条物理链路具有相同的容量，但这对本发明不构成约束。

具体而言，存在两个部分填充的波长，其具有足够的剩余容量，以容纳连接节点21至节点22的逻辑链路内的数据传输。第一波长具有0.5Mb/s的空闲容量，而第二波长具有0.3Mb/s的空闲容量。

在优选实施例中，网络控制可以编程为选择负载最重或具有最少空闲容量的波长。此选择标准(随后称为WF(波长填充)标准)使找到为需要大容量的其它连接可用的至少一个波长的概率最大。

第二优选标准(随后称为WEF(波长均匀填充)标准)选择负载最轻或具有最大剩余容量的波长，以便实现数据在可用波长中的均匀分布。

为了更好理解本发明方法整体带来的主要优点和上述两个优选标准带来的不同特定优点，将根据支持本发明的发明概念的路由策略的性能与现有技术路由算法(即所谓的“最短路径”算法、  “最少跳”算法和“最小阻力(least resistance)”算法)进行比较。

在所有报告的测试例中，均根据阻塞概率(指示不满足请求的概率)和总拒绝带宽(指示未被满足的所有请求导致的累计带宽)来评价性能。

所报告的结果涉及8个节点的网络拓朴的情况。但是，本领域技术人员应理解，如果考虑节点数量不同的拓朴，则从定性的观点来看，结果不变。最后，假定到达每个节点的连接请求遵循泊松分布。

图6报告有关LSP连接请求与所提供的以尔朗(Erlang)表示的业务负载的阻塞概率。

线条600涉及根据本发明的方法所取得的结果，而线条610、620和630分别涉及“最小阻力”算法、“最小跳”算法和“最短路径”算法。

图6表示根据本发明的路由策略优于所有受测的其它策略，直到网络加载到预计要拒绝大部分请求并且所有性能均变得不可接受为止。

图7显示了计算为所有被拒绝LSP请求之和的总拒绝带宽与所提供的以尔朗表示的业务负载。

线条700涉及根据本发明的方法所取得的结果，而线条710、720和730分别涉及“最小阻力”算法、“最小跳”算法和“最短路径”算法。

根据本发明的路由策略再次优于所有其它策略，直到网络加载到合理数量的负载为止。

应该注意的是，如预计的那样，“最短路径”算法在网络高度拥塞时给出较好的结果。这是最短路径算法相对于任何基于约束的路由算法的一个熟知特征，可以根据如下知识予以解释：当业务拥塞水平达到某个临界值时，算法必然会得到占用更少网络资源的最好结果。但是，应该注意的是，当占用的链路容量达到70％且阻塞概率变得不可接受(超过10％)，即所述条件在实际情况中明显无意义时，“最短路径”算法性能要好于根据本发明的路由策略。

图8报告在将不同标准用于在各波长上分布容量时的阻塞概率与所提供的以尔朗表示的业务负载。

线条800和810分别涉及将所公开的WF和WEF标准应用于根据本发明的策略方法时所得的结果，而线条820和830分别涉及将同样的标准应用于“最短路径”算法时所得的结果。

该图显示，在业务负载处于有效水平时，根据本发明的路由策略配合WF容量分布优于所有其它策略，而根据本发明的另一优选实施例(即适用于所提出的路由策略的WEF容量分布)取得次优性能。

最后，参考图9，在根据本发明的路由策略与所有其它策略之间就阻塞概率拒绝带宽与所提供的以尔朗表示的业务量进行比较，其中线条910、920和930分别涉及“最小阻力”算法、“最小跳”算法和“最短路径”算法。

该图显示，无论采用何种波长选择标准，根据本发明的路由策略均提供最好的性能。

至此说明本发明实现了所提出的目标和目的。显然，本领域技术人员清楚并可以在不背离本发明范围的前提下容易地进行多种修改。因此，权利要求书的范围不限于附图所示或在本说明书中以示例形式给出的优选实施例，确切地说，权利要求书将涵盖存在于本发明中的所有可专利创新特征，包括本领域技术人员视为等效的所有特征。