一种查找最大瓶颈速率的方法及系统

摘要

本发明公开了一种查找最大瓶颈速率的方法及系统，其中，该方法包括：构建网络拓扑图，该拓扑图中连接相邻节点的边的权值大小与相邻节点间的数据传输速率大小成正比；按照边的权值从大到小的顺序连接相邻节点；当源节点与目的节点连接于同一连通分支时，确定连接该连通分支的最后一条边的权值为该连通分支中的最大瓶颈速率。通过采用本发明公开的方法，提高了效率，降低了查找时间复杂度。

说明书

技术领域

本发明涉及网络通信技术领域，尤其涉及一种查找最大瓶颈速率的方法及系统。

背景技术

为了从理论上更好地描述网络，通常采用拓扑结构研究网络。例如，采用带权图G=(V, E)，V={1,2,…，n}表示网络的拓扑结构，其中V为节点集合，E为边集合，从节点u到节点 v的边记为（u，v）。

网络中从源节点到目的节点的传输速率取决于该链路（连通分支）上传输速率最小的 一跳的传输速率，该传输速率称为瓶颈速率。而从源节点到目的节点一般存在多条链路， 每条链路中又存在不同的瓶颈速率，其中，数值最大的瓶颈速率称之为源节点到目的节点 的最大瓶颈速率。

为了得到从源节点到目的节点的所有路径上的单路径最大传输速率，现有的方法是找 出从源节点到达目的节点的所有链路，然后单独计算每条链路上的瓶颈速率，通过相互比 较得到最大瓶颈速率。但是，该方法效率低，时间复杂度大（时间复杂度为O(n!)，其中 n为节点的数量）。

发明内容

本发明的目的是提供一种查找最大瓶颈速率的方法及系统，用于提高工作效率及降低 查找时间复杂度。

一种查找最大瓶颈速率的方法，该方法包括：

构建网络拓扑图，该拓扑图中连接相邻节点的边的权值大小与相邻节点间的数据传输 速率大小成正比；

按照边的权值从大到小的顺序连接相邻节点；

当源节点与目的节点连接于同一连通分支时，确定连接该连通分支的最后一条边的权 值为该连通分支中的最大瓶颈速率。

一种查找最大瓶颈速率的系统，该系统包括：

网络拓扑图构建模块，用于构建网络拓扑图，该拓扑图中连接相邻节点的边的权值大 小与相邻节点间的数据传输速率大小成正比；

节点连接模块，用于按照边的权值从大到小的顺序连接相邻节点；

最大瓶颈速率确定模块，用于当源节点与目的节点连接于同一连通分支时，确定连接 该连通分支的最后一条边的权值为该连通分支中的最大瓶颈速率。

由上述本发明提供的技术方案可以看出，在网络拓扑图中通过以边的权值大小连接节 点，直接查找权值最大的连通分支，并以此确定最大瓶颈速率，提高了工作效率，降低了 查找时间复杂度。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附 图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领 域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附 图。

图1为本发明实施例一提供的一种查找最大瓶颈速率的方法的流程图；

图2为本发明实施例二提供的又一种查找最大瓶颈速率的方法的流程图；

图3为本发明实施例二提供的一种网络拓扑图的示意图；

图4为本发明实施例二提供的一种网络拓扑图中连接相邻节点的示意图；

图5为本发明实施例二提供的一种网络拓扑图中连接相邻节点的示意图；

图6为本发明实施例二提供的一种网络拓扑图中连接相邻节点的示意图；

图7为本发明实施例二提供的一种网络拓扑图中连接相邻节点的示意图；

图8为本发明实施例二提供的一种网络拓扑图中连接相邻节点的示意图；

图9为本发明实施例三提供的一种查找最大瓶颈速率的系统的示意图。

具体实施方式

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描 述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发 明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施 例，都属于本发明的保护范围。

实施例一

图1为本发明实施例一提供的一种查找最大瓶颈速率的方法的流程图，如图1所示，主 要包括如下步骤：

步骤101、按照边的权值从大到小的顺序连接相邻节点。

构建网络拓扑图，网络拓扑图中包含若干个节点，相邻的两个节点通过“边”进行连 接，每一条边都具有对应的权值，该权值与相邻节点间数据传输速率大小成正比，具体的： 权值可以为相邻节点间的数据传输速率，也可以为基于相邻节点间的数据传输速率的大小 确定的参数。

在网络拓扑图中预先标定源节点与目的节点，而源节点至目的节点可能存在若干条连 通分支，且每条连通分支中存在独立的瓶颈速率。为了快速的查找最大瓶颈速率，则在网 络拓扑图中直接查找权值最大的连通分支。因此，在网络拓扑图中按照边的权值从大到小 的顺序连接各个相邻节点，具体的：预先计算所有相邻节点间传输速率，按照传输速率的 从大到小的顺序依次连接相邻节点。

步骤102、当源节点与目的节点连接于同一连通分支时，确定连接该连通分支的最后 一条边的权值为该连通分支中的最大瓶颈速率。

通过执行步骤101的操作，直至源节点与目的节点处于同一连通分支下，此时源节点 与目的节点所处的连通分支为权值最大的连通分支。该连通分支是按照边的权值从大到小 的顺序连接相邻节点所获得的，因此，该连通分支中边的最小权值应大于或等于其他连通 分支边的最大权值。换言之，该连通分支中边的最小权值（该连通分支的瓶颈速率）大于 或等于其他连通分支的最大速率，即可以确定该连通分支中边的最小权值则为源节点到目 的节点的最大瓶颈速率。

另外，此时已查找到源节点与目的节点间的最大瓶颈速率，可以终止步骤101的操作。

本发明实施例通过边的权值大小连接节点，直接查找权值最大的连通分支，并以此确 定最大瓶颈速率，提高了工作效率，降低了查找时间复杂度。

实施例二

为了便于理解本发明，结合附图2-8对本发明做进一步介绍，如图2所示，主要包括以 下步骤：

步骤201、计算相邻节点边的权值。

构建网络拓扑图，网络拓扑图中包含若干个节点，相邻的两个节点通过“边”进行连 接，每一条边都具有对应的权值，该权值与相邻节点间数据传输速率大小成正比，具体的： 权值可以为相邻节点间的数据传输速率，也可以为基于相邻节点间的数据传输速率的大小 确定的参数。如图3所示，为一网络拓扑图的示意图，图中数字1-7表示网络节点，节点中 连线表示边，边上的数字为边的权值（传输速率或传输速率大小的参数）。

步骤202、按照边的权值从大到小的顺序连接相邻节点。

在网络拓扑图中预先标定源节点与目的节点，而源节点至目的节点可能存在若干条连 通分支，且每条连通分支中存在独立的瓶颈速率。为了快速的查找最大瓶颈速率，则需要 先找到权值最大的连通分支。而根据步骤201可知边的权值，因此，根据边的权值从大到 小的顺序连接节点，以获得权值最大的连通分支。

进一步的，本实施例通过查找权值最大的连通分支来确定源节点与目的节点间的最大 瓶颈速率，而该连通分支一般为单路径，无需形成回路，因此，为提高最大瓶颈速率的查 找效率，在连接相邻节点之前还需判断欲连接的两个相邻节点是否处于同一连通分支中； 若不是，则连接；否则，忽略本次连接，进入下一条边的连接判断。

为了便于理解本步骤，现结合图3-图7做详细的介绍。

首先，将图3中的节点1作为源节点，节点7作为目的节点。将各个边的权值由大到小 的顺序排列：20、19、18、16、16、14、14、13、13、10、10和8。本示例中 基于相邻节点间的数据传输速率的大小确定的参数作为相邻节点的边的权值，显然，此处 仅为举例，并非对其进行限制。

其次，如图4所示，20为权值最大的边，而该边对应的节点为3与5，并且节点3与5为 孤立的节点，因此两者处于不同的连通分支中，即连接节点3与5。

再次，如图5-图6所示，权值为19的边对应的为节点6-7，同理，节点6-7处于不同的连 通分支中，因此，直接连接。权值为18的边对应的为节点3-4，节点4是孤立的节点，因此， 可将节点3与4连接。

然后，权值为16的边有两条，节点5与6及节点3与6均处于不同的连通分支下，但是， 连接其中一条边之后，则另外一条边无法连接。此时，可随机连接其中一条边。如图7所 示，本示例以先连接节点5与6为例，当节点5与6连接后，节点3与6则处于同一连通分支下， 因此，不进行连接。

最后，权值为14的边也有两条，节点1与3及节点2与5均处于不同的连通分支下，并且， 连接其中一条边后，不会影响另外一条边的连接。此时，可随机选择其中一条先连接。如 图8所示，本示例以先连接节点1与3为例，当节点1与3连接之后，源节点1与目的节点7处 于同一连通分支下。显然，也可先连接节点2与5，再连接节点1与3，本示例仅为举例并非 对其进行限制。

步骤203、当源节点与目的节点连接于同一连通分支时，确定连接该连通分支的最后 一条边的权值为该连通分支中的最大瓶颈速率。

通过执行步骤202的操作，直至源节点与目的节点处于同一连通分支下，此时源节点 与目的节点所处的连通分支为权值最大的连通分支。该连通分支是按照边的权值从大到小 的顺序连接相邻节点所获得的，因此，该连通分支中边的最小权值应大于或等于其他连通 分支边的最大权值。换言之，该连通分支中边的最小权值（该连通分支的瓶颈速率）大于 或等于其他连通分支的最大速率，即可以确定该连通分支中边的最小权值则为源节点到目 的节点的最大瓶颈速率。

如图8所示，当权值为14的边连接后，则源节点1与目的节点7处于同一连通分支下， 并且未连接的边的权值均小于等于14，因此，可以确定14为源节点与目的节点间的最大瓶 颈速率。此时，流程结束，对于权值小于14的边可以终止连接。

另外，当按照边的权值从大到小的顺序连接各个相邻节点后，若还无法将源节点与目 的节点连通于同一连通分支中，则表明源节点与目的节点无法连通，此时，其最大传输速 率为零。

本发明实施例通过以边的权值大小连接节点，直接查找权值最大的连通分支，并以此 确定最大瓶颈速率，提高了工作效率，降低了查找时间复杂度。

实施例三

图9为本发明提供的一种查找最大瓶颈速率的系统的示意图，如图9所示，该系统主要 包括：

网络拓扑图构建模块91，用于构建网络拓扑图，该拓扑图中连接相邻节点的边的权值 大小与相邻节点间的数据传输速率大小成正比；

节点连接模块92，用于按照边的权值从大到小的顺序连接相邻节点；

最大瓶颈速率确定模块93，用于当源节点与目的节点连接于同一连通分支时，确定连 接该连通分支的最后一条边的权值为该连通分支中的最大瓶颈速率。

该系统还包括：

判断连接模块921，用于判断需连接的两个相邻节点是否处于同一连通分支中；若不 是，则连接；否则，忽略本次连接，进入下一条边的连接判断。

其中，判断连接模块921可以集成在所述节点连接模块92中。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，仅以上述各功能模块 的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能模块完 成，即将系统的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。 上述描述的系统的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任 何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都 应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围 为准。