[發(fā)明專利]一種面向云計(jì)算網(wǎng)絡(luò)的拓?fù)涮綔y方法

有效

• 申請?zhí)枺?/td>: 201410348943.3
• 申請日: 2014-07-21
• 公開（公告）號: CN104158748A
• 公開（公告）日: 2014-11-19
• 發(fā)明（設(shè)計(jì)）人: 王少輝;董從翔;肖甫;韓志杰;王汝傳;劉佳
• 申請（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L29/08
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 葉連生

1.一種基于云計(jì)算網(wǎng)絡(luò)的拓?fù)涮綔y方法，其特征在于該方法包含以下的具體步驟：

步驟1.按照預(yù)先設(shè)定拓?fù)鋱D進(jìn)行搭建云平臺(tái)管理項(xiàng)目Openstack的真實(shí)環(huán)境，

步驟2.在進(jìn)行第一層網(wǎng)絡(luò)拓?fù)涮綔y時(shí)對每個(gè)路由器下任意選擇一個(gè)虛擬機(jī)進(jìn)行編號并編入相應(yīng)的套接字程序socket程序，通過路由器下的虛擬機(jī)為分別接收大數(shù)據(jù)包與兩個(gè)小的數(shù)據(jù)包，對每對路由器與計(jì)算節(jié)點(diǎn)間的數(shù)據(jù)時(shí)延測量，得到每對小數(shù)據(jù)包的時(shí)間差，通過全局搜索拓?fù)涮綔yMLT算法進(jìn)行推斷，

1)選擇一個(gè)隨機(jī)的開始狀態(tài)s₀＝(T₀+u₀)，

2)進(jìn)入下一狀態(tài)s₁，得到最小值：min{1,p(T1,u1|x)q(s0|s1)p(T0,u0|x)q(s1|s0)×Jf(s1-s0)},]]>

3)重復(fù)步驟1和步驟2的過程，直到建立一個(gè)拓?fù)鋱D；

步驟3.在進(jìn)行第二層網(wǎng)絡(luò)拓?fù)涮綔y時(shí)，對于每個(gè)路由器虛擬機(jī)進(jìn)行安裝信息通信接口庫MPI，并寫入對應(yīng)的時(shí)間測試程序，由公式T_comm＝T_S+mT_W通過測量節(jié)點(diǎn)彼此間發(fā)送不同字節(jié)大小的數(shù)據(jù)包，得到不同數(shù)據(jù)包大小時(shí)對應(yīng)的時(shí)間大小，其中T_comm表示節(jié)點(diǎn)對間實(shí)際測量得到的傳輸時(shí)間；T_S表示節(jié)點(diǎn)對間建立的時(shí)間；T_w表示節(jié)點(diǎn)對間的每單位字節(jié)的發(fā)送時(shí)間；m表示節(jié)點(diǎn)對間發(fā)送的字節(jié)大小；對于每一個(gè)節(jié)點(diǎn)對i,j,用矩陣實(shí)驗(yàn)室MATLAB將其10個(gè)值根據(jù)上述線性公式擬合出該節(jié)點(diǎn)對在T_w矩陣下的值Tw_i,j；

使用并查集算法Union-Find進(jìn)行節(jié)點(diǎn)聚類，并查集是通過樹形結(jié)構(gòu)來存儲(chǔ)的，在合并操作時(shí)利用樹的節(jié)點(diǎn)數(shù)或者利用一個(gè)排列數(shù)組來存儲(chǔ)集合的啟發(fā)式函數(shù)，在查找操作時(shí)進(jìn)行路徑壓縮使后續(xù)的查找操作加速；并查集有三種操作：

合并操作Union；把子集合Root2即根2和子集合Root1即根1合并，要求：Root1和Root2互不相交，否則不執(zhí)行操作；

搜索操作Find；搜索單元素x所在的集合，并返回該集合的名字--根節(jié)點(diǎn)標(biāo)示；UFSets構(gòu)造函數(shù)，將并查集中s個(gè)元素初始化為s個(gè)只有一個(gè)單元素的子集合，利用并查集的算法，將MPI測試數(shù)據(jù)進(jìn)行劃分聚類，number表示節(jié)點(diǎn)的數(shù)量；threshold表示定義的閾值范圍；Tw[number][number]表示T_w矩陣；

1)得到“朋友關(guān)系矩陣”，設(shè)置一個(gè)閾值，遍歷其余節(jié)點(diǎn)，其中有90％～98％比例的節(jié)點(diǎn)到兩觀測節(jié)點(diǎn)的時(shí)間差在閾值范圍內(nèi)，即認(rèn)定兩觀測節(jié)點(diǎn)為“直接朋友”關(guān)系，否則不是，得到“直接朋友關(guān)系”矩陣；

2)初始化把每一節(jié)點(diǎn)當(dāng)成一顆子樹，該樹只有自身一個(gè)節(jié)點(diǎn)，作為根節(jié)點(diǎn)；

3)合并子樹若節(jié)點(diǎn)i,j，為直接朋友關(guān)系，對i,j為根節(jié)點(diǎn)的子樹分別進(jìn)行壓縮路徑，使其子樹中所有非根節(jié)點(diǎn)直接指向根節(jié)點(diǎn)，并合并以i,j為根節(jié)點(diǎn)的子樹，并把編號較小的節(jié)點(diǎn)作為新樹的根節(jié)點(diǎn)，再對新樹同樣進(jìn)行壓縮路徑；

4)差錯(cuò)檢測，在合并子樹的過程中，若節(jié)點(diǎn)i,j不為直接朋友關(guān)系，而遍歷節(jié)點(diǎn)i,j的根時(shí)得到同一根節(jié)點(diǎn)，則說明出現(xiàn)差錯(cuò)；

5)顯示劃分結(jié)果，用map即示意圖存儲(chǔ)不同集合樹當(dāng)中的元素，每棵樹的根節(jié)點(diǎn)編號作為map的下標(biāo)，對應(yīng)的內(nèi)容是一個(gè)向量，用來存儲(chǔ)該樹所有非根節(jié)點(diǎn)，歸并好的節(jié)點(diǎn)即是虛擬機(jī)的部署拓?fù)洌瑥亩贸鲈骗h(huán)境下第二層網(wǎng)絡(luò)拓?fù)洌?/p>

步驟4.在聚類好的虛擬機(jī)結(jié)構(gòu)中，通過測試相互的時(shí)延，由于在同一路由器下的虛擬機(jī)間的通信時(shí)間肯定最短，隨著經(jīng)過的路由器與交換機(jī)的增多通信時(shí)延增加，根據(jù)這一原理，通過比較不同虛擬機(jī)間的時(shí)延相似度來驗(yàn)證之前的聚類分布；

步驟5.將第一層拓?fù)涮綔y結(jié)構(gòu)與第二層拓?fù)涮綔y結(jié)構(gòu)相結(jié)合構(gòu)成完整的云計(jì)算環(huán)境下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。