CN100583808C - 在具有通信量分布的分组网中将分布权重分配给连接段 - Google Patents

Abstract

本发明涉及一种用于在具有多路径路由或分布扇的网络中匹配分布权重的方法。通过匹配分布扇内的相对分布权重，减少超过通信量阈值的连接段(11、12、13)上的或超过通信量阈值的经由节点(K)的通信量。通过本方法，在均匀的通信量分布的意义上在网络内实现分布权重的转移。给出在通信量超出网络容量的情况下的中断判据。在遵守单个连接段的负载极限的条件下的通信量分配就保证经由该网络实现的电信业务的业务质量特性而言是一个重要步骤。

Description

在具有通信量分布的分组网中将分布权重分配给连接段

目前对于通信技术人员、网络专家和因特网专家而言或许最重要的任务领域在于，实现经由面向分组网络的实时数据通信。首先语音数据(在这方面经常指IP承载语音)、但是视频信息也应当能够实时地并且以高的业务质量经由分组网、重要的IP网来传输。主要基于本地路由判定和“最大努力”数据传输的因特网的高灵活性对于实时通信量的传输来说是一个障碍。在传统的IP网络、例如因特网中，由于上述特性不能保证数据传输的业务质量(常说quality of service)。通常在数据传输时的延迟时间对于语音传输来说还是过高。此外，还可能导致对不稳定的业务质量负责的瓶颈，而不稳定的业务质量对于数据传输来说是可容忍的，但是对于语音传输来说是不可接受的。因而，进一步发展应能够遵循业务质量特征的IP网络。

一种用于经由基于分组的网络的实时通信量传输的重要措施是所谓的差分业务方案(DiffServ-Konzept)。在这个概念的范围内，进入网络的数据包在网络边缘处根据业务类别被标记，并且在网内路由时根据业务类别被处理。这里也说到classes of service。对于语音信息的传输来说，可以划分为相应的业务类别，使得在网内路由时优先处理附属的数据包。这种方法允许在实时业务路由时进行处理并由此实现这种高优先级的业务的、比在常规IP网络中更好的业务质量特征。被相应地分类的业务的相对业务质量变得更好。但是，不能保证绝对业务质量特征。在需要遵守的绝对极限方面，业务类别的相对改善是不够的，这些绝对极限是诸如在传输语音信息时的最大延迟时间或在传输视频数据时的最大丢失率。

第二个重要的方案是所谓的MPLS(Multi Protocol LabelSwitching)方法，在该方法中通过分组网转换固定连接。MPLS方法虽然能够为具有高业务质量要求的业务保留带宽。然而，这个优点是用放弃常规因特网的大部分灵活性而换来的。

本发明的任务是给出一种改进的通过分组网路由的方法。

该任务通过根据权利要求1和3的方法来解决。

为了更好地理解本发明方法，下面简短地介绍用于保证业务(经由分组网传输)质量的方案，本发明方法可被用于该方案。该方案的目的在于，在遵循业务质量特征的情况下经由分组网传输数据，而无须为此放弃过多的常规数据网络的固有灵活性。此外，该方案基于以下两点：

1.为了避免分组网内的过载情况，通过以下方式来限制总通信量，即在网络边缘处监控进入和出去的通信量并且在超过阈值时对其进行限制。

2.通过在该网络内分配通信量，而在分组网内避免瓶颈。

总通信量的限制以及通信量的灵活分配允许控制经由该网络的数据通信量的传输，这在恰当地选择参数时能够以高的概率保证业务质量特征(诸如遵守某些极限)。

在通信量分配时，例如可以观察在输入和输出节点对之间经由网络传输的通信量。对于该通信量来说，则有不同的路由可供使用，该通信量通过这些路由来进行分配。对于一个输入节点，可以针对网络的每个节点观察连接段的总量，其中经由每个节点来传输通过所述输入节点到达网络的通信量，由所述节点转传的数据包能够经由所述连接段到达所述输出节点。这个与节点相关的、通向输出节点并且依赖于输入和输出节点的连接段的总量在下面被称为“分布扇(Verteilungsfaecher)”。概念“连接段”(在本文献中也经常使用概念“链路(link)”)在这里被用作逻辑概念，为其分配了在两个节点之间的物理连接和方向。因此，根据这里所使用的语言惯用法，具有双工通信通话的物理连接段对应于两个指向相反方向的连接段。

根据本发明的方法力求在用节点和连接段所构成的分组网中匹配分布权重的匹配。在此，在分组网中借助于分布扇进行通信量分配。在根据本发明的第一方法中，为了避免网络节点上的过载，确定从该节点导出或导入该节点的所有通信负载，并且检验，总的通信负载是否超过阈值。当超过该阈值时，如此匹配位于该节点之前的、属于包含该节点的分布扇的连接段的分布权重，以致经由所述节点引导的通信量被降低。例如当位于该过载节点之前的节点具有三个属于同一分布扇的并且通向不同节点的替代导出连接段时，可以提高两个不通向该过载节点的连接段的分布权重，并相应地降低通向该过载节点的连接段的分布权重。可以对分组网的所有节点一直实施这种方法，直到所述节点不超出该阈值或者满足中断判据。

在一个细微的变型方案中，可以在减少分组网的连接段的负载的意义上应用本方法。在此，针对该连接段确定总的通信负载，并检验，总的通信负载是否超过阈值。当超过该阈值时，如此匹配属于包含所述连接段的分布扇的连接段的分布权重，以致经由所述连接段引导的通信量被降低。例如，所涉及的连接段是三个属于一个分布扇的、从同一节点导出的连接段之一。于是可以降低所涉及的连接段的、对其他两个连接段不利的分布权重。类似于用于减少经由节点引导的通信量的方法，也可以对数据网的所有连接段一直实施本方法，直到所有连接段不超过该阈值或者满足中断判据。

一般地，当不超过该阈值时，可以结束用于减少连接段或节点的负载的分布权重的匹配。节点的阈值例如通过从该节点导出的或导入该节点的全部连接段的带宽与一个因子相乘的值来给出。对于连接段，可以将与该因子相乘的连接段的带宽用作阈值。在此情况下，该因子处于0和1之间。在一个优选的实施方案中，该因子接近1。通过将带宽与小于1的因子相乘，设法在分组网满载时实现保留。不能期待发生完美的经由网络的通信量分配，因此按计划利用带宽可能引起100％的阻塞。

经由单个链路或节点的通信负载的确定可以借助于通信量矩阵来进行。这样一个通信量矩阵例如可以以“最坏情况”、也就是最大通信负载的情况为基础，或者也可以动态地或同时每隔一定时间针对分布权重的重新调整来确定。由连接段中的多个节点所构成的网络中的分布权重的分配是一个复杂的任务。根据分组网的连接段的带宽和通信量矩阵来计算分布权重，通常导致一个具有很多非线性方程的系统，该系统通常在数值上也不是唯一精确可解的。本发明方法是一种花费低的、切合实际的方法，利用该方法可以实现用于分组网内的有效的通信量分配的分布权重。首先在借助于限制总通信量并在网络内有效地分配通信量来遵守业务质量标准方面，本发明方法有助于根据权重因子在网络内最佳地分配通信量。

在一个有利的改进方案中，在降低连接段的通信负载时通过以下方式来实现这种降低，即依照根据本发明的第一方法降低经由位于该连接段之前的节点所引导的通信量。如果分布扇的连接段之间的权重的匹配未导致下降到阈值之下，则通过前置的节点来降低连接段的通信负载就特别有意义。通过按照本发明移动和重新分配分布权重，通信负载在网络中被转移。当这种通信负载的转移导致遵守判据或者遵守网络的每个连接段或每个节点的阈值时，可以停止该方法。然而，也有可能的是，该方法不收敛或不快速收敛，也就是说，在迭代了可接受的次数时，没有实现对所有连接段或节点的阈值的辨别。于是，可以应用不同的中断判据。中断判据是：

1.在经由网络的所有节点或连接段运行了一次或多次时，通信负载超过阈值的节点或连接段的数量没有降低。

2.在运行了一次或多次时，对通信负载超过阈值的所有节点或连接段求和得到的、总通信负载和阈值之差的平方和没有降低。

3.执行了最大次数的运行，也就是说，当迭代次数达到一个预定的最大值时，中断。

本发明方法导致在均匀的通信量分布的意义上分布权重的重新安排或匹配。为了能够进行重新安排，必须在开始时初始化节点和连接段的分布权重的值，也就是说，必须分配初始值。合适的初始值分配就本方法的位置收敛而言是重要的，其中将不超过所有节点或连接段的阈值称作收敛。分布权重的初始化可以例如通过分配初始值来实现，其中针对一个节点，属于同一分布扇的、从该节点导出或导入该节点的连接段按照其相对带宽分配到分布权重。这种初始值分配还可以通过以下方式来改进，即在减少连接段的数量的意义上按照分布扇内连接段的数量来进行分布扇的分布权重的相对匹配，其中数据包必须经由这些连接段从连接段传输到目的地。这种改进目的在于缩短网络内的路径，通过该路径在分组网内引导通信量。明显有意义的是，在一个分布扇内，该分布扇为属于固定的输入节点和输出节点的通信量确定可能的路径替代方案，优选这样的路径，该路径经过尽可能少的连接段。缩短在网络中所经过的路径导致网络中通信量的减少，其中必须避免单个连接段的过载，这通过引入阈值来保证。

此外，有意义的是，附加地进行分组网的总负载检验，以便一开始就选出本发明方法不收敛的情况。在检验分组网的总负载时，例如针对网络的每个边缘节点，确定经由该边缘节点进入分组网的通信量和经由它出去的通信量。这也可以例如借助于通信量矩阵来实现。然后，将经由网络的边缘节点进入或出去的总通信量与从该节点导出或导向该边缘节点的全部连接段的带宽和一个因子相乘的值进行比较。在此，该因子是在0和1之间的数。当经由网络的边缘节点进入或出去的总通信量超过从该边缘节点导出或导向该边缘节点的连接段和在0和1之间的因子相乘的总带宽时，中断本方法。通过这种方式避免这样的情况，在该情况下在边缘节点出现通信量过载，该通信量过载也可能导致网络内过高的总通信量。

总通信量的直接检验通过另一改进方案来实现。在此，借助于通信量矩阵根据一开始所分配的分布权重，计算所有网络段上的总通信量，并且当总量超过在整个网络上求和得到的并且乘以在0和1之间的因子的分组网连接段的总带宽时，中断本方法。

在一个优选的实施变型方案中，针对网络的每个内部节点，设置两个导出的连接段。

下面在实施例的范围内借助附图来详细说明本发明方法。

附图示出一个用节点和连接段构成的网络。在此，边缘节点由用斜线填充的圆来表示，而内部节点由常规的圆来表示。连接段由连接节点的线或箭头来表示。

针对输入节点I和输出节点E示出一个分布扇，该分布扇包括由虚线箭头和点线箭头表示的连接段。此外，该分布扇包括内部节点R和K。针对节点K，示出一个包含虚线连接段的分布扇。该分布扇包括从节点K导出的链路(连接段)11、12和13。从位于节点K之前的节点R导出链路r1、r2和r3。针对本实施例，引入以下概念：

●Hammock-sd：包含在多路径路由中的从网络的输入节点s到输出节点d的所有路径的数量。Hammock-sd对应于在两个边缘节点、例如边缘节点I和E之间的分布扇。

●Fan-isd：节点i是Hammock-sd的一部分。Fan-isd是节点i的路径扇(Wegefaecher)，该节点在目标方向上可使用该路径扇(Hammock-sd中节点i的部分，由多个输出链路组成)。例如，如果节点K是由边缘节点I和E定义的Hammock-sd的一部分，则节点K的Fan-isd由链路11、12和13组成。

●Reserve a：应以通信量将链路仅加载到其带宽的a倍(a＜1)，以便获得一定的保留。因此，为了过载保护的目的，发生网络的超尺寸。

对于该实施例来说，下列起始假设应成立：

●对于该网络来说，存在通信量矩阵。该通信量矩阵列出在该网络的所有边缘节点之间的相应通信量。

●所有的多路径路由(Hammocks)是确定的并且存在。建议，如下将分布权重分配给单个链路：

1.针对该网络的每个边缘节点(例如边缘节点I和E)检验，它是否能够完全承受经由其链路到达它和离开它的总通信量。为此针对各个边缘节点由通信量矩阵通过相加得出离开的通信量，并且将该通信量与其离开链路的带宽之和的a倍进行比较。针对到达的通信量进行类似的操作。如果存在超过，那么该网络尺寸过小，并且停止本方法。

2.为了进行初始化，对于网络中的每个Hammock，在Hammock-sd中的每个节点i处，为Fan-isd的每个链路k选择与各个链路的带宽成比例的分布权重w_i，sd，k(归一化，以便Fan-isd的分布权重之和为一)。例如链路11、12和13的分布权重与其带宽成比例地来确定。

3.利用按照步骤1暂时确定的权重，基于通信量矩阵计算每个链路的通信负载(将所有Hammock的通信量分量相加)。

4.作为对足够的网络尺寸的渐进测试(在路由给定的情况下)，将如此计算出的所有链路的通信量相加，并且将其与所有链路的带宽之和的a倍进行比较。如果这里存在超过，那么该网络尺寸过小，并停止本方法。

5.针对网络的每个节点检验，按照步骤3所计算的经由其所有输出链路的通信量之和是否超过输出链路的带宽之和的a倍。例如对于节点K，将经由链路11、12和13的通信量相加。如果情况如此，那么该节点就不能够承担分配给它的总通信量。必须将该通信量分配给网络中的其他节点：

●对于每个这种“过载”节点，逐步地在单个或所有包含朝着所涉及的节点方向的链路的Fans-isd的、单个或所有前节点处如此移动分布权重(归一化，使得Fan-isd的分布权重之和为一)，以致朝着所涉及的节点方向的链路被卸载到如此程度，直到满足在5中给出的条件。因而，例如在节点K过载时，匹配节点R的输出链路r1、r2和r3的分布权重。(导向节点K的)链路12的权重被降低，而链路11和13的权重相应地被提高。

●步骤5一直重复，直到没有发现其他的过载节点，或者根据合适的中断判据确定“不可解”。在后一种情况下，中断本方法。

6.针对网络中的每个链路检验，按照步骤3所计算的通信负载是否超过其容量的a倍。如果情况如此，那么该链路(在考虑到“保留”的情况下)是过载的，在这个节点上的通信量必须被重新分配到其他链路上。

●对于在节点i上的每个这种“过载”链路，逐步减少在单个或所有包含这个链路的Fans-isd中的分布权重(归一化，使得Fan-isd的分布权重之和继续为一，因此Fan-ist中的其他链路的权重被相应地提高)，直到实现期望的Reservea。例如，在链路12过载时，链路11和13的相对权重被提高。

●在此，当重新分配时注意，Fan-isd的其他链路在其一侧不会由于重新分配而超过“a倍带宽”的限制。优选地，考虑未满载的链路来接收通信量。

●如果按这种方式不能针对所有链路实现相应的保留(Reserve)，那么到达所涉及的节点的通信量过高。于是，(类似于步骤5)应在前节点(例如节点R)中如此修改分布权重(例如r1、r2和r3)，以致这些前节点的经由所涉及的链路的通信量相应地被减少。

●在步骤6的每次运行中，首先类似于步骤5针对连接有需要卸载的链路的节点进行“节点测试”。由于前面运行时的通信量的重新分配，在单个节点上可能产生过载，那么使得步骤6对于这个节点来说原则上不可解。如果在一个节点上情况如此，那么根据步骤5来处理它。

●一直重复步骤6，直到不再找到其他的过载链路，或者根据合适的中断判据确定“不可解”。在后一种情况下中断本方法。

通常，多次执行步骤5和6，直到达到令人满意的网络满载。此外，该循环的中断判据是：

●当在一次经由整个网络的运行中超过值a(带宽满载的极限值)的链路(或在步骤5中的节点)的数量没有降低，和/或

●当在一次运行中a的正偏差的平方没有降低(也就是说，网络满载的目标值被超出)，和/或

●当达到了预定次数的运行。

如果没有针对所有链路或至少针对这些链路的所要求的部分达到目标值、也就是带宽的一小部分a，那么提高在一个或多个链路上的带宽是必要的。

采用所述方法实现在通常情况下所有链路均匀地满载，并且特别是还具有相同大小的针对最大负载的相对保留(与相应的链路带宽有关)，因此能够实现最佳的通信量分配。

代替这里提出的用于优化网络使用的渐进方法，也能够替代地或补充地使用其他的确定的优化方法，然而这些方法通常需要高的计算花费。代替均匀的网络使用，也可以考虑其他判据作为目标量，例如有目的地将通信量集中到特殊的、例如特别可靠的链路上，或者优化允许的高优先级的通信量部分，或者最小化成本。

可能的扩展：

●如果就计算花费而言是可行的，也可以为了再次优化分布权重而使用已知的优化方法，如梯度方法或其变型(例如Fletcher/Reeves、Fletcher/Powell)。

●在权重的初始分配时，可以考虑在Fan-isd中经由相应的链路k直到目的地所需的路程段的数量，例如，与路程段的数量成反比例地减少权重。由此减少网络的总负载。

●在最初分配权重时，可以放大地评估相邻节点之间经由直接链路的通信量，以便也因此最小化较高的网络负载。

本方法并不局限于在实施例中所介绍的步骤顺序或步骤组合。

Claims (10)

1.用于在分组网中针对避免节点过载的通信量分配来匹配分布权重的方法，其中所述分组网是用多个节点(I、E、R、K)和连接段(l1、l2、l3、r1、r2、r3)构成的，并且在所述分组网中借助于分布扇进行通信量分配，

其中，

-针对所述分组网的每个节点，

--确定从所述节点导出的或导向所述节点的连接段(l1、l2、l3)的总通信负载，

--检验从所述节点导出的或导向所述节点的连接段的总通信负载是否超出阈值，

--在超出所述阈值时，匹配属于包含所述节点的分布扇的、位于所述节点之前的连接段(r1、r2、r3)的分布权重，以致经由所述节点引导的通信量被降低，

-直到对于所述分组网的所有节点来说都未超出所述阈值或者都满足中断判据。

2.用于在分组网中针对避免连接段过载的通信量分配来匹配分布权重的方法，其中所述分组网是用多个节点(I、E、R、K)和连接段(l1、l2、l3、r1、r2、r3)构成的，并且借助于分布扇进行通信量分配，

其中，

-对于所述分组网的每个连接段，

--针对正被观察的连接段，确定总通信负载，

--检验所述总通信负载是否超出阈值，和

--在超出所述阈值时，匹配属于包含被观察的连接段的分布扇的并且从同一节点导出的其它连接段的分布权重，以致经由被观察的连接段引导的通信量被降低，

-直到对于所述分组网的所有连接段来说都未超出所述阈值或都满足中断判据。

3.按照权利要求1或2之一的方法，

其特征在于，

-在不超出所述阈值时，结束所述分布权重的匹配。

4.按照权利要求1或2之一的方法，

其特征在于，

-从一节点导出的或导向所述节点的全部连接段的带宽与一因子相乘的值被用作所述节点的阈值，其中所述因子是在0和1之间的数，以及

-连接段的带宽与所述因子相乘的值被用作所述连接段的阈值。

5.按照上述权利要求1或2之一的方法，

其特征在于，

-使用下列中断判据之一：

--在经由所述分组网的所有节点(I、E、R、K)或连接段(l1、l2、l3、r1、r2、r3)运行了所述方法一次或多次时，如下节点或连接段的数量没有下降，这些节点或连接段的通信负载超出相应的节点或连接段的阈值，

--在运行了所述方法一次或多次时，在使用每个节点的阈值的情况下，对通信负载超出分别所属的阈值的所有节点求和得到的、总通信负载和阈值之差的平方总和没有降低，或在使用每个连接段的阈值的情况下，对通信负载超出分别所属的阈值的所有连接段求和得到的、总通信负载和阈值之差的平方总和没有降低，

--所述方法已执行最大次数的运行。

6.按照权利要求1或2之一的方法，

其特征在于，

在本方法开始时给所述分布权重分配初始值，其中针对一个节点，属于同一分布扇的、从所述节点导出的或导向所述节点的连接段按照其相对带宽被分配到分布权重。

7.按照权利要求6的方法，

其特征在于，

在给连接段(l1、l2、l3、r1、r2、r3)分配分布权重的初始值时，按照数据包从该连接段传输至目的地必须经由的分布扇内连接段的数量，在减少连接段的数量的意义上进行分布扇的分布权重的相对匹配。

8.按照权利要求1或2之一的方法，其中在开始执行权利要求1或2中所述的方法步骤之前执行所述分组网的总负载检验，

其中

-针对所述分组网的每个边缘节点(I、E)，确定经由该边缘节点进入所述分组网和经由其出去的总通信量，

-将经由所述分组网的边缘节点进入或出去的总通信量与从所述边缘节点导出的或导向所述边缘节点的全部连接段的带宽与一因子相乘的值进行比较，其中所述因子是在0和1之间的数，以及

-当经由所述分组网的边缘节点进入或出去的总通信量超出从所述边缘节点导出的或导向所述边缘节点的连接段的总带宽与所述因子相乘的值时，中断本方法。

9.按照权利要求8的方法，

其特征在于，

-借助于通信量矩阵和最初所分配的分布权重，计算经由所述分组网的所有连接段的通信量的总和，以及

-当这样计算出的通信量的总和超出所述分组网的连接段的对所述分组网的所有连接段求和得到的并且与所述因子相乘的总带宽时，中断本方法。

10.按照前述权利要求1或2之一的方法，

其特征在于，

在所述分组网的每个内部节点处布置两个从相应节点导出的连接段。

Images