CN101193053B

CN101193053B - 一种有中心管理的多网关路由选择方法

Info

Publication number: CN101193053B
Application number: CN2006101456801A
Authority: CN
Inventors: 杨博; 孔亚洲; 王进; 洪艳霞
Original assignee: ZTE Corp
Current assignee: ZTE Corp
Priority date: 2006-11-23
Filing date: 2006-11-23
Publication date: 2011-04-20
Anticipated expiration: 2026-11-23
Also published as: CN101193053A

Abstract

本发明公开了一种有中心管理的多网关路由选择方法，包括如下步骤：呼叫控制服务器根据网络拓扑配置，将入局侧网关和出局侧网关之间跳数小于等于配置的公平跳数的路径选择出来，根据这些线路的资源配置总数和已占用资源数分别计算每条路径的修正平均线路紧张程度，在所有的路径中选取修正平均线路紧张程度最小的路径为承载路径。本发明还公开了另一种有中心管理的多网关路由选择方法，该方法中若最短路径的每一个线路的紧张程度因子都小于配置的负荷启动门限，就选用最短路径作为当前呼叫的承载路径，否则选取修正平均线路紧张程度最小的路径为承载路径。本发明克服了因网关间资源分配不公平而容易导致拥塞，使整个网络可控、稳定、公平地运行。

Description

一种有中心管理的多网关路由选择方法

技术领域

本发明涉及一种路由选择方法，尤其涉及一种有中心管理的多网关路由选择方法。

背景技术

两个、三个或者更多个网关同时注册到一个呼叫控制服务器上，这种网络模型称为有中心管理的多网关模型；由于这种网络模型实用、经济，因此很快就得到了应用，随着这种模型的大规模应用，就会出现越来越多的大区内采用多网关模型来组网，而在大区间采用呼叫控制服务器间的局间互联。这种应用达到一定程度以后，同一个呼叫控制服务器下管辖的网关会越来越多，这些网关间的负荷也会越来越大，而多网关间的资源数目却是有限的，因此就有可能有些网关间比较繁忙，而有些网关间不太繁忙。如何让这些负荷地平均分担到其他网关上去，并且如何有效的在负荷突然增大的情况下避免某些网关间的资源耗尽，而其他的网关间却十分空闲，是需要解决的问题。

目前网关间的路由选择有多种方式，如按照路由最短的原则进行按需分配，这种选路的方法很单一，而且不能够较好的利用网关间的资源。假设有两个网关，它们之间有两条路径，一条比较短，另一条比较长，当这两个网关间的负荷很多的情况下，这两个网关间的最短路径将会很繁忙。在负荷增大到一定程度，最短路径上的资源将被耗尽，其它的希望经过这条路径的负荷将被拒绝；而这个时候比较长的那条路径上因为没有负荷而空闲，这时就在较短的路径上出现拥塞。

如果能在最短路径上的资源耗尽之前，分担出一部分负荷来走较长的那个路径，那么就不会出现较长的路由上没有负荷，而较短的路径上却资源耗尽的情况。因此就出现了另一种选路的方式，按照负荷分担的方式进行选路，这种方式简单的按照资源的比例作为权值来给两条不同的路径分配负荷量，资源配置比较多的分配的负荷多一些，资源配置比较少的分配的负荷少一些，但是这种方式没有考虑负荷持续的时间，有的负荷持续时间短，有些负荷持续时间长，承载资源也会一直被占用。另一方面，路径上负荷是不断变化的，该方法没有把负荷变化作为选路的依据，因此最终的结果将是无序和难以控制的，同样容易出现资源耗尽的情况，只是这种情况的几率降低了一些。

另一方面，对于包括多个线路(指路径上两个相邻网关间的路由)的路径来说，在计算时一般是将各线路的资源简单平均后来比较。但是，这种算法虽然在一定程度上体现了路径的资源配置或占用情况，但如果其中的某一条线路已非常紧张，而其它线路资源比较充裕，其平均值可能相对较低而被选中，但这时却可能因为该条线路不能再分配资源而导致选路失败。

由此可见，目前在实际应用中采用的技术和选路策略，实际上是不公平的，也不能较好的协调多网关模型中的网关间的资源利用和分配。

发明内容

本发明要解决的技术问题就是提供一种有中心管理的多网关路由选择方法，克服因为网关间资源分配不公平而容易导致拥塞，从而使整个网络可控、稳定、公平地运行。

为了解决上述技术问题，本发明提供一种有中心管理的多网关路由选择方法，包括如下步骤：

(1)呼叫控制服务器根据网络拓扑配置，将入局侧网关和出局侧网关之间跳数小于等于配置的公平跳数的路径选择出来，读取这些线路的资源配置总数和已占用资源数；

(2)分别计算每条路径上每一个线路的修正线路紧张程度因子＝f(线路紧张程度因子)，其中线路紧张程度因子＝已占用资源数/资源配置总数，函数f(x)的定义域为：0＜＝x＜＝1；并且f(x)是一个f(0)＝0，f(1)＝无穷大的平滑函数；

(3)再分别计算每条路径的修正平均线路紧张程度，修正平均线路紧张程度为路径上每个线路的修正线路紧张程度因子之和，再除以该路径的跳数；

(4)在所有的路径中选取修正平均线路紧张程度最小的路径为承载路径。

进一步地，对于网关间是由时分复用线路承载，资源配置总数为网关间配置的可用的时分复用电路识别码的数目，已占用资源数为已经占用的时分复用电路识别码的数目。

进一步地，对于网关间是由IP线路承载，资源配置总数为网关间可用的承载总带宽，已占用资源数为已经使用掉的带宽。

进一步地，所述函数f(x)＝1/(1-x)-1。

本发明还提供了一种有中心管理的多网关路由选择方法，包括如下步骤：

(2)分别计算每条路径上的线路集中每一个线路的线路紧张程度因子，其中线路紧张程度因子＝已占用资源数/资源配置总数；

(3)当步骤2中最短路径的每一个线路的紧张程度因子都小于配置的负荷启动门限，就选用最短路径作为当前呼叫的承载路径，否则，执行步骤4；

(4)分别计算每条路径的修正平均线路紧张程度，修正平均线路紧张程度为路径上每个线路的修正线路紧张程度因子之和，再除以该路径的跳数，其中修正线路紧张程度因子＝f(线路紧张程度因子)，函数f(x)的定义域为：0＜＝x＜＝1；并且f(x)是一个f(0)＝0，f(1)＝无穷大的平滑函数；

(5)在所有的路径中选取修正平均线路紧张程度最小的路径为承载路径。

进一步地，所述函数f(x)＝1/(1-x)-1。

本发明有如下有益效果：

1、将一条路径上所有的线路的繁忙程度因子加起来再求平均值，利用这样的方法当这条路径上的一段线路很繁忙而另一段线路很空闲的时候，求平均值会掩盖了线路繁忙的那一段资源紧张的事实，而这个时候这条路径再作为被选择的路径可能会加重线路紧张的那一段的线路紧张程度，进而造成拥塞。而采用函数f(x)进行修正以后，最终的修正平均线路紧张程度就会变得对对拥塞很敏感，能在拥塞即将发生的时候立即反映在修正平均线路紧张程度会变成一个很大的值，进而这条路径被选中的可能性就会迅速降低，这样就起到了避免拥塞的作用。当即将拥塞的线路上的呼叫释放掉了一部分以后，这条路径可能被选中了机会就会增大。因此该发明可以有效地避免拥塞。

2、与均匀的或者加权的按照负荷分担的选路方式相比，均匀的或者加权的按照负荷分担的方法，没有考虑到不同的负荷持续时间长短的差异，因此容易出现公平性上存在较大的波动。而本发明则把目前的资源配置总数和已经占用的资源总数作为评价不同路由好坏的一个重要的因素，它利用了所有的网关都处于同一管理服务中心的管辖范围之内，而且管理服务中心很容易动态观测到所有节点间的繁忙程度的优点，来控制在不同的路径上均匀的负荷分担。

3、如果选择最短路径作为当前路径，有可能会出现跳数较少的最短路径上的负荷过重，甚至资源耗尽，而跳数较长的路径上却没有任何负荷，实际上只要一条路径的跳数在可以容忍的范围内，就应该把一部分负荷分担到这些路径上去，以缓解跳数较少的较短路径的压力。因此本发明把选路的范围限制在一个网管可以配置的公平跳数以内，这样既可以做到把负荷分担到较长的路径上去，又可以让用户对这些较长路径做出限制，以免路径太长开销太大。

4、本发明通过设定一个负荷启动门限，将路由最短和拥塞避免两种因素都考虑在内，当最短路径上的每一段线路的线路紧张程度因子都小于负荷控制启动门限的时候，说明用户认为这个时候不会发生拥塞，因此应该选用最短路径作为当前呼叫承载的路径。当最短路径上的任何一段线路的线路紧张程度因子大于拥塞控制门限的时候就需要启动负荷分担的机制，来由其他路径帮助最短路径来分担负荷。因此本发明兼顾了路由最短和拥塞避免两个方面的优点。

附图说明

图1是本发明呼叫控制服务器和网关连接示意图；

图2是本发明有中心管理的多网关路由选择方法的流程图；

图3是本发明有中心管理的多网关路由选择方法的另一流程图；

图4是本发明图1中的网关间资源占用/配置的示例图；

图5是本发明实现多网关模型下的路由选择功能的系统中，在1->6->5和1->7->5两条路径上的资源占用/配置情况。

具体实施方式

下面结合附图及具体实施例对本发明进行详细说明。

如图1所示，图中节点8是呼叫控制服务器，节点从1到7是隶属于节点8管理的网关。节点8与节点从1到7之间的虚线是信令链路；节点1到7相互之间的实线则是承载链路。本发明的系统包括网管(图中未示)、至少一个呼叫控制服务器，至少四个网关，同一个呼叫控制服务器下管辖的多个网关之间组成网状连接，两个不相邻的网关之间有一条以上的路径。

如图2所示，本发明一种有中心管理的多网关路由选择方法，包括如下步骤：

步骤201，开始；

步骤202，呼叫控制服务器接收到一个入局侧网关(Ni)呼叫，根据网管配置的信息确定出局侧网关(Nj)；

步骤203，呼叫控制服务器根据网络拓扑配置和公平跳数配置(hop)在Ni和Nj之间将跳数小于等于hop的所有路径选择出来；

每个路径可能是由一条或者多条线路所组成的，将每条路径用线路集的形式记录下来，假设Ni和Nj之间某一条路径只经过一个节点Nk，那么这条路径的线路集为{(Ni，Nk)，(Nk，Nj)}；

步骤204，呼叫控制服务器根据步骤203中各路径的线路集来读取这些线路的资源配置总数(T(Ni，Nk)，T(Nk，Nj))和已占用资源数(A(Ni，Nk)，A(Nk，Nj))，对于网关间是TDM(时分复用)承载的情况，T(Ni，Nk)表示网关间配置的可用的CIC(TDM电路识别码)的数目，A(Ni，Nk)表示已经占用的CIC的数目；对于IP承载T(Ni，Nk)表示网关间可用的承载总带宽，A(Ni，Nk)表示已经使用掉的带宽；

步骤205，按照公式A(Ni，Nk)/T(Ni，Nk)来计算路径(Ni，Nk)的线路紧张程度因子，由于当前被占用的资源A(Ni，Nk)总是少于配置的资源T(Ni，Nk)，因此A(Ni，Nk)/T(Ni，Nk)＜＝1；按照该公式分别计算步骤203中每条路径上的线路集中每一个线路的线路紧张程度因子；

步骤206，分别计算每条路径的工程修正平均线路紧张程度：

{A(Ni，Nk)/T(Ni，Nk)+...+A(Nk，Nj)/T(Nk，Nj)}/h＝平均线路紧张程度(公式1)

{f(A(Ni，Nk)/T(Ni，Nk))+...+f(A(Nk，Nj)/T(Nk，Nj))}/h＝修正平均线路紧张程度(公式2)

其中((Ni，Nk)，...(Nk，Nj))∈线路集，h为该线路集的跳数；

其中函数f(x)应具备以下特性：

f(x)的定义域为：0＜＝x＜＝1；并且f(x)如果是一个f(0)＝0，f(1)＝无穷大的平滑函数，那么就可使f(A(Ni，Nk)/T(Ni，Nk))接近于1的最繁忙，使f(A(Ni，Nk)/T(Ni，Nk))接近于0的最不繁忙。f(x)＝1/(1-x)-1具备上述条件，将f(x)代入公式2，得到公式3。

{A(Ni，Nk)/(T(Ni，Nk)-A(Ni，Nk))+...+A(Nk，Nj)/(T(Nk，Nj)-A(Nk，Nj))}/h＝工程修正平均线路紧张程度(公式3)

步骤207：利用步骤206中计算出来的各条路径的工程修正平均线路紧张程度来在所有的路径中选取工程修正平均线路紧张程度最小的那个路径作为当前呼叫的路径。

步骤208，呼叫控制服务器根据当前呼叫的路径信息来控制在该路径上的所有网关建立承载；

步骤209，结束。

公式3中所指出的工程修正算法，是把函数f(x)＝1/(1-x)-1代入公式2所得到的，而符合f(x)特征的平滑函数有很多，如1/(1-sin((π/2)*x))-1等高等数学中常用到的函数，都符合f(x)的特征，这些平滑函数不应该仅仅局限于f(x)＝1/(1-x)-1，因此该函数应该是可以配置的，并且用户可以根据路由控制模块上报给网管的资源占用情况参数，来衡量不同的f(x)对负荷控制效果的影响，进而可以修正f(x)。

如图3所示，本发明还提供一种有中心管理的多网关路由选择方法，包括如下步骤：

步骤301，开始；

步骤302，呼叫控制服务器接收到一个入局侧网关(Ni)呼叫，根据网管配置的信息确定出局侧网关(Nj)；

步骤303，呼叫控制服务器根据网络拓扑配置和公平跳数配置(hop)在Ni和Nj之间将跳数小于等于hop的所有路径选择出来；每个路径可能是由一条或者多条线路所组成的，将每条路径用线路集的形式记录下来，假设Ni和Nj之间某一条路径只经过一个节点Nk，那么这条路径的线路集为{(Ni，Nk)，(Nk，Nj)}；

步骤304，呼叫控制服务器根据步骤303中各路径的线路集来读取这些线路的资源配置总数(T(Ni，Nk)，T(Nk，Nj))和已占用资源数(A(Ni，Nk)，A(Nk，Nj))；

步骤305，按照公式A(Ni，Nk)/T(Ni，Nk)来计算线路(Ni，Nk)的线路紧张程度因子，由于当前被占用的资源A(Ni，Nk)总是少于配置的资源T(Ni，Nk)，因此A(Ni，Nk)/T(Ni，Nk)＜＝1；按照该公式分别计算步骤303中每条路径上的线路集中每一个线路的线路紧张程度因子；

步骤306，将最短路径线路的紧张程度因子与网管设定的启动负荷控制门限相比较，如果最短路径的每一个线路的紧张程度因子都小于负荷启动门限，那么就选用最短路径作为当前呼叫的承载路径；

步骤307，呼叫控制服务器根据该承载路径信息来控制在该路径上的所有网关建立承载；

步骤308，结束。

步骤309，如果步骤306中最短路径的每一个线路的紧张程度因子有大于负荷启动门限的，这就说明目前的最短路径比较拥塞，因此就应该启动负荷分担机制，分别计算每条路径的工程修正平均线路紧张程度；

步骤310，利用步骤309中计算出来的各条路径的工程修正平均线路紧张程度在所有的路径中选取修正平均线路紧张程度最小的那个路径作为当前呼叫的路径；

步骤311，呼叫控制服务器根据该承载路径信息来控制在该路径上的所有网关建立承载，然后进入步骤308，结束过程。

同样，本例中，工程修正平均线路紧张程度使用的函数f(x)＝1/(1-x)-1，符合f(x)特征的平滑函数有很多，这些平滑函数不应该仅仅局限于f(x)＝1/(1-x)-1，因此该函数应该是可以配置的，并且用户可以根据路由控制模块上报给网管的资源占用情况参数，来衡量不同的f(x)对负荷控制效果的影响，进而可以修正f(x)。

图4是本发明网关间资源占用/配置例图。图中所有节点间的分数，分子表示的是节点间已经被占用的资源总数A(Ni，Nk)，而分母表示的是节点间配置的资源总数T(Ni，Nk)。而这个分数表示的则是两个节点(Ni，Nk)间的线路紧张程度因子A(Ni，Nk)/T(Ni，Nk)。

图5是一个例图，说明的是在1->6->5和1->7->5两条路径上的资源占用/配置情况。

如果按照公式1来在这两条路径之间选择一个空闲的路径，则路径1->6->5的平均线路紧张程度为：(0.53+0.97)/2＝0.75，路经1->7->5的平均线路紧张程度为：(0.85+0.85)/2＝0.85。如果直接选择平均线路紧张程度较小的路径为当前路径，则应该选择1->6->5为当前的路径，但是很明显，这个时候路径1-->6->5之间的线路6->5的线路利用率已经达到了97％，这个时候如果仍然在1->6->5这条路径上面选路，马上会在线路6->5之间产生拥塞，因此实际上应该选择1->7->5为当前路径。

如果按照公式3来计算在这两条路径之间选择一个空闲的路径，则路径1->6->5的修正平均线路紧张程度为：(53/(100-53)+97/(100-97))/2＝33.427，路经1->7->5的平均线路紧张程度为：(85/(100-85)+85(100-85))/2＝5.56。选择修正平均线路紧张程度较小的路径为当前路径，则应该选择1->7->5为当前的路径，这个时候就避开了那条即将拥塞的路径，这就说明经过修正以后的公式3当一条路径中的任何一段线路即将发生拥塞的时候修正平均线路紧张程度马上会变得很大，从而减小了负荷选择到这条路径上的可能，从而达到了拥塞避免的目的。

本发明通过计算修正平均线路紧张程度、设置负荷分担启动门限、设置负荷分担公平跳数的方法用于路由选择，兼顾了路由最短和拥塞避免两个方面的优点，有效地协调同一个呼叫控制服务器下多网关间的负荷，使整个网络可控的、稳定的、公平的运行。

Claims

1.一种有中心管理的多网关路由选择方法，包括如下步骤：

2.根据权利要求1所述的方法，其特征在于：对于网关间是由时分复用线路承载，资源配置总数为网关间配置的可用的时分复用电路识别码的数目，已占用资源数为已经占用的时分复用电路识别码的数目。

3.根据权利要求1所述的方法，其特征在于：对于网关间是由IP线路承载，资源配置总数为网关间可用的承载总带宽，已占用资源数为已经使用掉的带宽。

4.根据权利要求1～3中任意一项所述的方法，其特征在于：所述函数f(x)＝1/(1-x)-1。

5.一种有中心管理的多网关路由选择方法，包括如下步骤：

6.根据权利要求5所述的方法，其特征在于：对于网关间是由时分复用线路承载，资源配置总数为网关间配置的可用的时分复用电路识别码的数目，已占用资源数为已经占用的时分复用电路识别码的数目。

7.根据权利要求5所述的方法，其特征在于：对于网关间是由IP线路承载，资源配置总数为网关间可用的承载总带宽，已占用资源数为已经使用掉的带宽。

8.根据权利要求5～7中任意一项所述的方法，其特征在于：所述函数f(x)＝1/(1-x)-1。