[發明專利]一種查找最大瓶頸速率的方法及系統

有效

• 申請號: 201210479245.8
• 申請日: 2012-11-22
• 公開（公告）號: CN102932189A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 盧漢成;毛譽熹
• 申請（專利權）人: 中國科學技術大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;趙鎮勇

技術領域

本發明涉及網絡通信技術領域，尤其涉及一種查找最大瓶頸速率的方法及系統。

背景技術

為了從理論上更好地描述網絡，通常采用拓撲結構研究網絡。例如，采用帶權圖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為本發明實施例三提供的一種查找最大瓶頸速率的系統的示意圖。

具體實施方式

下面結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例?；诒景l明的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬于本發明的保護范圍。

實施例一

圖1為本發明實施例一提供的一種查找最大瓶頸速率的方法的流程圖，如圖1所示，主要包括如下步驟：

步驟101、按照邊的權值從大到小的順序連接相鄰節點。

構建網絡拓撲圖，網絡拓撲圖中包含若干個節點，相鄰的兩個節點通過“邊”進行連接，每一條邊都具有對應的權值，該權值與相鄰節點間數據傳輸速率大小成正比，具體的：權值可以為相鄰節點間的數據傳輸速率，也可以為基于相鄰節點間的數據傳輸速率的大小確定的參數。