CN101977159A - 窄带网络带宽资源的管理方法 - Google Patents

Abstract

本发明公开了一种窄带网络带宽资源的管理方法，包括如下步骤：(1)计算路由域内的各节点的紧密度，将紧密度值最大的节点作为中心节点；(2)由中心节点临时充当资源管理者，对当前的全网络带宽资源进行管理；(3)按周期重新计算路由域内的各个节点的紧密度，根据计算出的紧密度值最大的节点，重新确定中心节点，重复步骤(3)、(4)。本发明的有益技术效果是：该方法通过对网络带宽资源采取柔性重组策略，由中心节点按需调配网络带宽资源，具备全网资源调节能力，网络管理开销很小，能够在窄带网络里实现大流量数据传输业务。

Description

窄带网络带宽资源的管理方法

技术领域

    本发明涉及一种通信技术，尤其涉及一种窄带网络带宽资源的管理方法。

背景技术

传统的路由协议采用最短路径算法，未充分考虑业务传输路径上的带宽利用率，不具备全网资源调节能力，这就导致了网络上的流量分布不平衡，容易引起网络部分链路因为负载过重产生拥塞现象，而别的链路却处于空闲状态，影响网络的整体性能。在窄带网络里，窄带链路较难支持大流量数据业务的传输要求，因此，前述问题在窄带网络里更为突出。

利用OSPF的TE扩展来实现网络资源的管理是目前宽带网络的一种通用作法，OSPF(Open Shortest Path First开放式最短路径优先)是一个内部网关协议(Interior Gateway Protocol,简称IGP)，用于在单一自治系统(autonomous system,AS)内决策路由。与RIP相对，OSPF是链路状态路由协议，而RIP是距离向量路由协议。包括O S P F在内，所有的S P F路由协议基于一个数学算法—D i j k s t r a算法。这个算法能使路由选择基于链路状态，而不是距离向量。链路是路由器接口的另一种说法，因此OSPF也称为接口状态路由协议。OSPF通过路由器之间通告网络接口的状态来建立链路状态数据库，生成最短路径树，每个OSPF路由器使用这些最短路径构造路由表。OSPF路由协议是一种典型的链路状态（Link-state）的路由协议，一般用于同一个路由域内。在这里，路由域是指一个自治系统（Autonomous System），即AS，它是指一组通过统一的路由政策或路由协议互相交换路由信息的网络。在这个AS中，所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库（即链路状态数据库），该数据库中存放的是路由域中相应链路的状态信息，OSPF路由器正是通过这个数据库计算出其OSPF路由表的。

作为一种链路状态的路由协议，OSPF将链路状态广播数据包LSA（Link State Advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器。OSPF-TE——带流量工程的OSPF。OSPF-TE对OSPF的流量工程的扩展实质是扩展链路属性，即在OSPF通告中增加链路参数。这种扩展提供一种描述流量工程拓扑（包括带宽和管理限制）和在一个给定OSPF域内分发信息的方法。这个拓扑不需与常规选路的拓扑匹配，但是在描述多接入链路时需依靠网络LSA。OSPF-TE流量工程数据库包括：监视扩展的链路属性、本地基于约束的源路由以及全部的流量工程。当网络中某链路资源（通常为带宽资源）发生变化时，通过装填Opaque LSA并利用OSPF扩展机制来进行全网络扩散，达到网络各节点资源同步的管理目的。这种资源管理方式会占用额外的带宽开销，在宽带网络里开销可以忽略；但在窄带网络里面这种管理开销需要尽量缩减，以节省宝贵的链路带宽资源。

因此，目前的窄带网络的资源管理系统无法满足用户的需求。

发明内容

针对背景技术中的问题，本发明提出了一种窄带网络带宽资源的管理方法，包括如下步骤：

（1）计算路由域内的各节点的紧密度，将紧密度值最大的节点作为中心节点；

（2）由中心节点临时充当资源管理者，对当前的全网络带宽资源进行分配和管理；

（3）定期（周期由网络规模确定）重新计算路由域内的各个节点的紧密度，根据计算出的紧密度值最大的节点，重新确定中心节点，重复步骤（3）、（4）。

步骤（1）包括：若路由域中有n个节点，将各个节点用1至n的序号分别标记，将网络

中某一节点的紧密度指标定义为                                               

，x∈n，y∈n，且x≠y，其含义为：除第x

个节点以外的各个节点到第x个节点的跳数之和的导数；对紧密度指标进行归一化处理，得

，取

计算结果最大值所在的节点为中心节点；

其中，

为第x个节点的紧密度；

为

经归一化处理后的紧密度值。

步骤（2）包括：

1）将OSPF路由协议的链路状态数据库转换成流量工程数据库；

设发出业务请求的源节点到目的节点的路径有M条，该次业务请求所需要的请求带宽量为Q，

2）中心节点根据流量工程数据库中的信息，对当前传输状态下，每条路径的路径带宽权值进行计算，找出路径带宽权值满足要求的路径，假设满足要求的路径有m条；

3）由中心节点对m条路径中每条路径的剩余带宽进行计算并对剩余带宽进行累加，设累加结果为Q1，如Q1≥Q，则将本次业务请求的请求带宽量Q分摊至m条路径上并传输；

如Q1＜Q，则将请求带宽量Q中与Q1数值相等的部分分摊至m条路径上，并计算出Q与Q1的差值Q2，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输；

4）将资源分配及链路调整信息与流量工程数据库同步。

所述将OSPF路由协议的链路状态数据库转换成流量工程数据库，包括：OSPF路由协议的链路状态数据库的拓扑表中，包含了路由域内各节点的连接关系及各链路的度量值Cost，根据公式B=/Cost对度量值Cost进行换算，求得相应的B，将求得的B与链路状态数据库中的原有信息进行对应、结合，从而形成流量工程数据库；式中，

为标识链路带宽。

步骤2）包括：设M条路径中的某一路径P，则路径P的带宽负载率为

其中，i为源节点的标记，j为目的节点的标记，表示从源节点i至目的节点j的某条链路；

表示链路

的带宽负载率，

，式中，

为链路

的剩余带宽，

为链路

的容量；

表示符合路径

P的链路

；

为符合路径P的带宽负载率最大值的链路，也即路径P的带宽负载率；

计算路径P的带宽权值，

，

其中，

为路径P的带宽权值；

为符合路径P的链路的剩余带宽最小值；

计算所有从源节点到目的节点的路径的带宽权值的均值，

其中，e为路由域内从源节点i到目的节点j的所有路径的集合；

查找满足条件>

的所有路径，即得满足要求的m条路径。

步骤3）中，各条路径按如下方法对带宽进行分摊：

设m条路径中的某一路径P，根据下式计算路径P的带宽分摊率

，

其中，e1为由m条路径所组成的路径的集合；

，

为路径P的带宽权值，

为所有从源节点到目的节点的路径的带宽权值的均值；

各条路径按各自对应的带宽分摊率

对请求带宽Q进行分摊。

步骤3）中，按如下方法判断各条路径分摊的带宽总和是否满足条件Q1＜Q：

计算出m条路径所分摊到的带宽的总和Q1；计算m条路径中各条路径的最小剩余带宽，将最小剩余带宽值最小的那条路径记为t，则其最小剩余带宽为

，该条路径的带宽分摊率为，则该条路径所分摊到的带宽为

，若路径t所分摊的带宽满足条件

，则认为Q1≥Q的条件成立，即请求带宽Q被分摊完，可以进行传输；否则，请求带宽Q还未被分摊完，计算Q与Q1的差值Q2=Q-Q1，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输。

本发明的有益技术效果是：该方法通过对网络带宽资源采取柔性重组策略，由中心节点按需调配网络带宽资源，具备全网资源调节能力，网络管理开销很小，能够在窄带网络里实现大流量数据传输业务。

附图说明

图1、本发明中心节点软件模块关系图；

图2、本发明中心节点选择按度指标计算结果示意图；

图3、本发明中心节点选择按紧密度指标计算结果示意图。

具体实施方式

本发明的方案可简述为：从各个节点中选取中心节点，由中心节点为其余节点的当前业务请求进行资源分配，根据运行状态，定期更新中心节点，并由新的中心节点为其余节点的当前业务请求进行资源分配。这种方案可对网络带宽资源进行柔性重组，使网络带宽资源被按需分配，避免了现有技术中，虽然传输路径得到了最短化，但会出现网络拥塞的问题；而且中心节点本身也在被动态调整，很好的兼顾了网络的实际传输状态，使窄带网络能够满足大流量数据传输业务的需要；其具体方案为：

（1）计算路由域内的各节点的紧密度，将紧密度值最大的节点作为中心节点；

（2）由中心节点临时充当资源管理者，对当前的全网络带宽资源进行管理；

（3）定期重新计算路由域内的各个节点的紧密度，根据计算出的紧密度值最大的节点，重新确定中心节点，重复步骤（3）、（4）。

该方案中需要解决的首要问题是如何选取中心节点；现有技术中，在描述这种中心化问题时，一般用度指标来描述静态网络中节点所产生的直接影响力，其值为与该节点直接相连的节点数。设网络中具有n个节点，则节点x的度指标定义为

，其中d(x)表示与节点x直接相连的节点数，称为该节点的度。如果利用度指标来进行节点的中心化，则可以体现出该节点与其周围节点之间建立直接联系的能力。但是，这种“建立直接联系的能力”无法反映出节点的资源分配能力，因此，发明人提出了紧密度指标：

紧密度(Closeness Centrality)可以描述出网络中的节点通过网络到达网络中其它节点的难易程度，紧密度指标较之度指标更加能够反映网络全局的结构，应用紧密度指标进行中心化不仅考虑到了节点度值的大小，而且还考虑到了节点在网络中所处位置的中心性，如图2是根据度指标测试的结果，而图3是根据紧密度指标测试的结果。通过对比容易发现，根据紧密度指标进行中心化测试的准确度明显高于根据度指标进行中心化测试的准确度。因此，紧密度指标更好的反映出了节点通过网络对其它节点施加影响的能力。

中心节点选择的策略是利用紧密度指标作为网络的中心化指标。针对网络中的每个节点，计算它到达所有其他节点的最短路径跳数总和，如果节点与网络中的另一个节点之间不可达，取该路径跳数为255。跳数总和最小的节点即为网络的中心节点。节点定期(采用一个定时器)进行网络中心节点的计算，如果出现了更好的中心节点，就会自动发生转移。

当节点发起的拓扑搜集完成后启动一个定时器，时间长度为T分钟(依据网络规模进行调整)，定时器超时后进行网络中心节点计算和转移。一次计算可能会有多个中心节点，此时查看当前节点是否为中心节点之一。如果是则不进行转移，否则从满足要求的节点中随机选择一个作为中心节点并向其发送一个特殊的目标定位消息，通知其做好准备，并将网络拓扑信息转移到新的节点上。

选取中心节点的具体方案为：

若路由域中有n个节点，将各个节点用1至n的序号分别标记，将网络中某一节点的紧

密度指标定义为

，x∈n，y∈n，且x≠y，其含义为：除第x个节点以外的各个

节点到第x个节点的跳数之和的导数；对紧密度指标进行归一化处理，得

，取

计算结果最大值所在的节点为中心节点；

其中，

为第x个节点的紧密度；

为

经归一化处理后的紧密度值。

选好中心节点后，就可以利用中心节点更容易对其它节点施加影响的能力，来对资源进行分配了，其具体方式是：

1）将OSPF路由协议的链路状态数据库（链路状态数据库是OSPF路由协议本身所具有的）转换成流量工程数据库；数据库的这种转换是中心节点进行后续处理的基础；

设发出业务请求的源节点到目的节点的路径有M条，该次业务请求所需要的请求带宽量为Q，

2）中心节点根据流量工程数据库中的信息，对当前传输状态下，每条路径的路径带宽权值进行计算，找出路径带宽权值满足要求的路径，假设满足要求的路径有m条；

3）由中心节点对m条路径中每条路径的剩余带宽进行计算并对剩余带宽进行累加，设累加结果为Q1，如Q1≥Q，则将本次业务请求的请求带宽量Q分摊至m条路径上并传输；

如Q1＜Q，则将请求带宽量Q中与Q1数值相等的部分分摊至m条路径上，并计算出Q与Q1的差值Q2，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输；

4）将资源分配及链路调整信息与流量工程数据库同步。

前述步骤概括出了一个基本的程序脉络，如下是可实现它的一些具体实施例：

步骤1）中所述将OSPF路由协议的链路状态数据库转换成流量工程数据库，包括：OSPF路由协议的链路状态数据库的拓扑表中，包含了路由域内各节点的连接关系及各链路的度量值Cost，根据公式B=

/Cost对度量值Cost进行换算，求得相应的B，将求得的B与链路状态数据库中的原有信息进行对应、结合，从而形成流量工程数据库；式中，为标识链路带宽。

步骤2）为：设M条路径中的某一路径P，则路径P的带宽负载率为

其中，i为源节点的标记，j为目的节点的标记，

表示从源节点i至目的节点j的某条链路；

表示链路

的带宽负载率，

，式中，为链路

的剩余带宽，

为链路

的容量；

表示符合路径P的链路

；

为符合路径P的带宽负载率最大值的链路，也即路径P的带宽负载率；

计算路径P的带宽权值，

，

其中，为路径P的带宽权值；

为符合路径P的链路的剩余带宽最小值；

计算所有从源节点到目的节点的路径的带宽权值的均值，

其中，e为路由域内从源节点i到目的节点j的所有路径的集合；

查找满足条件

>

的所有路径，即得满足要求的m条路径。

步骤3）中，各条路径按如下方法对带宽进行分摊：

设m条路径中的某一路径P，根据下式计算路径P的带宽分摊率，

其中，e1为由m条路径所组成的路径的集合；

，

为路径P的带宽权值，为所有从源节点到目的节点的路径的带宽权值的均值；

各条路径按各自对应的带宽分摊率

对请求带宽Q进行分摊。

步骤3）中，按如下方法判断各条路径分摊的带宽总和是否满足条件Q1＜Q：

计算出m条路径所分摊到的带宽的总和Q1；计算m条路径中各条路径的最小剩余带宽，将最小剩余带宽值最小的那条路径记为t，则其最小剩余带宽为

，该条路径的带宽分摊率为

，则该条路径所分摊到的带宽为

，若路径t所分摊的带宽满足条件

，则认为Q1≥Q的条件成立，即请求带宽Q被分摊完，可以进行传输；否则，请求带宽Q还未被分摊完，计算Q与Q1的差值Q2=Q-Q1，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输。

Claims (7)

1.一种窄带网络带宽资源的管理方法，其特征在于：包括如下步骤：

（1）计算路由域内的各节点的紧密度，将紧密度值最大的节点作为中心节点；

（2）由中心节点临时充当资源管理者，对当前的全网络带宽资源进行管理；

（3）按周期重新计算路由域内的各个节点的紧密度，根据计算出的紧密度值最大的节点，重新确定中心节点，重复步骤（3）、（4）。

2.如权利要求1所述窄带网络带宽资源的管理方法，其特征在于：步骤（1）包括：若路由域中有n个节点，将各个节点用1至n的序号分别标记，将网络中某一节点的紧密度指

标定义为                                               

，x∈n，y∈n，且x≠y，其含义为：除第x个节点以外的各个节点到

第x个节点的跳数之和的导数；对紧密度指标进行归一化处理，得

，取

计算结果最大值所在的节点为中心节点；

其中，

为第x个节点的紧密度；

为

经归一化处理后的紧密度值。

3.如权利要求1所述窄带网络带宽资源的管理方法，其特征在于：步骤（2）包括：

1）将OSPF路由协议的链路状态数据库转换成流量工程数据库；

设发出业务请求的源节点到目的节点的路径有M条，该次业务请求所需要的请求带宽量为Q，

2）中心节点根据流量工程数据库中的信息，对当前传输状态下，每条路径的路径带宽权值进行计算，找出路径带宽权值满足要求的路径，假设满足要求的路径有m条；

3）由中心节点对m条路径中每条路径的剩余带宽进行计算并对剩余带宽进行累加，设累加结果为Q1，如Q1≥Q，则将本次业务请求的请求带宽量Q分摊至m条路径上并传输；

如Q1＜Q，则将请求带宽量Q中与Q1数值相等的部分分摊至m条路径上，并计算出Q与Q1的差值Q2，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输；

4）将资源分配及链路调整信息与流量工程数据库同步。

4.如权利要求3所述窄带网络带宽资源的管理方法，其特征在于：所述将OSPF路由协议的链路状态数据库转换成流量工程数据库，包括：OSPF路由协议的链路状态数据库的拓扑表中，包含了路由域内各节点的连接关系及各链路的度量值Cost，根据公式B=

/Cost对度量值Cost进行换算，求得相应的B，将求得的B与链路状态数据库中的原有信息进行对应、结合，从而形成流量工程数据库；式中，

为标识链路带宽。

5.如权利要求3所述窄带网络带宽资源的管理方法，其特征在于：步骤2）包括：设M

条路径中的某一路径P，则路径P的带宽负载率为

；

其中，i为源节点的标记，j为目的节点的标记，

表示从源节点i至目的节点j的某条链路；

表示链路

的带宽负载率，

，式中，

为链路

的剩

余带宽，

为链路

的容量；

表示符合路径P的链路

；

为符合路径

P的带宽负载率最大值的链路，也即路径P的带宽负载率；

计算路径P的带宽权值，

，

其中，

为路径P的带宽权值；

为符合路径P的链路的剩余带宽最小值；

计算所有从源节点到目的节点的路径的带宽权值的均值，

其中，e为路由域内从源节点i到目的节点j的所有路径的集合；

查找满足条件

>

的所有路径，即得满足要求的m条路径。

6.如权利要求3所述窄带网络带宽资源的管理方法，其特征在于：步骤3）中，各条路径按如下方法对带宽进行分摊：

设m条路径中的某一路径P，根据下式计算路径P的带宽分摊率

，

其中，e1为由m条路径所组成的路径的集合；

，

为路径P的带宽权值，

为所有从源节点到目的节点的路径的带宽权值的均值；

各条路径按各自对应的带宽分摊率

对请求带宽Q进行分摊。

7.如权利要求3所述窄带网络带宽资源的管理方法，其特征在于：步骤3）中，按如下方法判断各条路径分摊的带宽总和是否满足条件Q1＜Q：

计算出m条路径所分摊到的带宽的总和Q1；计算m条路径中各条路径的最小剩余带宽，将最小剩余带宽值最小的那条路径记为t，则其最小剩余带宽为

，该条路径的带宽分摊率为，则该条路径所分摊到的带宽为

，若路径t所分摊的带宽满足条件

，则认为Q1≥Q的条件成立，即请求带宽Q被分摊完，可以进行传输；否则，请求带宽Q还未被分摊完，计算Q与Q1的差值Q2=Q-Q1，将已分摊的带宽从对应路径上扣除，将Q2作为一个新的请求带宽，重复步骤1）、2）、3），直至Q2≤0，最终得到可以完全分摊请求带宽量Q的所有路径，将Q分摊至这些路径上并传输。

Images