[發(fā)明專(zhuān)利]一種基于就近原則的虛擬網(wǎng)絡(luò)映射方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110023701.3
• 申請(qǐng)日: 2011-01-21
• 公開(kāi)（公告）號(hào): CN102075429A
• 公開(kāi)（公告）日: 2011-05-25
• 發(fā)明（設(shè)計(jì)）人: 黃韜;劉江;呂博;陳建亞;劉韻潔
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京郵電大學(xué)
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于就近原則的虛擬網(wǎng)絡(luò)映射方法，一個(gè)時(shí)間窗內(nèi)進(jìn)行一次虛擬網(wǎng)絡(luò)映射的步驟包括：

A.釋放前一個(gè)時(shí)間窗內(nèi)離開(kāi)的虛網(wǎng)請(qǐng)求占用的底層物理網(wǎng)資源，上述虛網(wǎng)請(qǐng)求包括完成服務(wù)的請(qǐng)求和被主動(dòng)拒絕的請(qǐng)求；虛網(wǎng)請(qǐng)求包含虛網(wǎng)節(jié)點(diǎn)請(qǐng)求和虛網(wǎng)鏈路請(qǐng)求兩部分；

B.統(tǒng)計(jì)本時(shí)間窗內(nèi)到達(dá)的虛網(wǎng)請(qǐng)求，虛網(wǎng)請(qǐng)求包括新到達(dá)的請(qǐng)求和重新排隊(duì)的請(qǐng)求；

C.將步驟B中統(tǒng)計(jì)的虛網(wǎng)請(qǐng)求按照其收入(Revenue)從大到小進(jìn)行排序，然后按順序映射至底層物理網(wǎng)絡(luò)，若其中任意一個(gè)虛網(wǎng)請(qǐng)求映射成功，即虛網(wǎng)節(jié)點(diǎn)和虛網(wǎng)鏈路同時(shí)映射成功，則更新底層物理網(wǎng)絡(luò)的狀態(tài)；若映射失敗，則將該虛網(wǎng)請(qǐng)求送至等待隊(duì)列，等待下個(gè)時(shí)間窗；預(yù)先設(shè)置虛網(wǎng)請(qǐng)求重新排隊(duì)的次數(shù)，如映射失敗的次數(shù)超過(guò)預(yù)設(shè)次數(shù)，則該請(qǐng)求不再送入等待隊(duì)列，而是直接拒絕。

2.如權(quán)利要求1所述的方法，上述步驟C包括：

C1)首先進(jìn)行節(jié)點(diǎn)映射，將虛網(wǎng)請(qǐng)求按照其收入從大到小進(jìn)行排序；

C2)判斷C1步驟排序后是否有虛網(wǎng)請(qǐng)求未進(jìn)行節(jié)點(diǎn)映射，如果有未進(jìn)行節(jié)點(diǎn)映射的虛網(wǎng)請(qǐng)求，執(zhí)行步驟C3，如果沒(méi)有未進(jìn)行節(jié)點(diǎn)映射的虛網(wǎng)請(qǐng)求，執(zhí)行步驟C9；

C3)選擇C1步驟排序后收入最大的虛網(wǎng)請(qǐng)求，并將該虛網(wǎng)請(qǐng)求內(nèi)的虛網(wǎng)節(jié)點(diǎn)(V_node)按照其剩余資源(Available?Resource，AR)從大到小排序；

C4)判斷C3步驟中選出的虛網(wǎng)請(qǐng)求中是否有虛網(wǎng)節(jié)點(diǎn)未映射，如果有未映射的虛網(wǎng)節(jié)點(diǎn)，執(zhí)行步驟C5，如果沒(méi)有未映射的虛網(wǎng)節(jié)點(diǎn)，執(zhí)行步驟C2；

C5)選擇C3步驟排序后剩余資源最大的虛網(wǎng)節(jié)點(diǎn)，在底層物理網(wǎng)中選擇出這樣的物理網(wǎng)節(jié)點(diǎn)(S_node)：其CPU資源大于上述虛網(wǎng)節(jié)點(diǎn)的CPU資源，將選出的物理網(wǎng)節(jié)點(diǎn)按照其加權(quán)剩余資源(WeightedAvailable?Resource，WAR)從大到小排序；

C6)判斷C5步驟排序后是否有物理網(wǎng)節(jié)點(diǎn)未被映射，如果有未被映射的物理網(wǎng)節(jié)點(diǎn)，執(zhí)行步驟C7，如果沒(méi)有未被映射的物理網(wǎng)節(jié)點(diǎn)，執(zhí)行步驟C8；

C7)將C5步驟排序后加權(quán)剩余資源最大的物理網(wǎng)節(jié)點(diǎn)分配給C5步驟中選出的剩余資源最大的虛網(wǎng)節(jié)點(diǎn)，執(zhí)行步驟C4；

C8)將C3步驟中選出的收入最大的虛網(wǎng)請(qǐng)求送至等待隊(duì)列或拒絕請(qǐng)求，執(zhí)行步驟C2；

C9)開(kāi)始進(jìn)行鏈路映射，將節(jié)點(diǎn)映射成功的虛網(wǎng)請(qǐng)求按收入從大到小進(jìn)行排序；

C10)判斷C9步驟排序后是否有虛網(wǎng)請(qǐng)求未進(jìn)行鏈路映射，如果有未進(jìn)行鏈路映射的虛網(wǎng)請(qǐng)求，執(zhí)行步驟C11，如果沒(méi)有未進(jìn)行鏈路映射的虛網(wǎng)請(qǐng)求，映射算法結(jié)束；

C11)選擇C9步驟排序后收入最大的虛網(wǎng)請(qǐng)求，并將該虛網(wǎng)請(qǐng)求內(nèi)的虛網(wǎng)鏈路(V_hnk)按照其帶寬從大到小排序；

C12)判斷C11步驟中選出的虛網(wǎng)請(qǐng)求中是否有虛網(wǎng)鏈路未映射，如果有未映射的虛網(wǎng)鏈路，執(zhí)行步驟C13，如果沒(méi)有未映射的虛網(wǎng)鏈路，執(zhí)行步驟C10；

C13)選擇C11步驟排序后帶寬最大的虛網(wǎng)鏈路，使用K最短路徑(K-Shortest)算法依次尋找第1至K條最短路徑，這些路徑由一條或多條底層物理網(wǎng)鏈路(S_link)組成，K為大于1的整數(shù)，僅保留這K條路徑中其中滿(mǎn)足該虛網(wǎng)鏈路帶寬的路徑；

C14)判斷C13步驟中保留的物理網(wǎng)路徑是否未被映射，如果有未被映射的物理網(wǎng)路徑，執(zhí)行步驟C15；如果沒(méi)有未被映射的物理網(wǎng)路徑，執(zhí)行步驟C16；

C15)將C13步驟中保留的物理網(wǎng)路徑中的最短路徑分配給C13步驟中選出的帶寬最大的虛網(wǎng)鏈路，執(zhí)行步驟C12；

C16)將C11步驟中選出的收入最大的虛網(wǎng)請(qǐng)求送至等待隊(duì)列或拒絕請(qǐng)求，執(zhí)行步驟C10。

3.如權(quán)利要求2所述的方法，其中

收入是指虛網(wǎng)映射成功獲得的利潤(rùn)，根據(jù)映射成功的虛網(wǎng)帶寬和CPU定義：

Revenue＝α_R∑BW_R+β_R∑CPU_R

其中，BW_R是映射成功的虛網(wǎng)帶寬，CPU_R是映射成功的虛網(wǎng)節(jié)點(diǎn)CPU資源，α_R和β_R是用于調(diào)節(jié)帶寬和CPU的權(quán)重系數(shù)，下標(biāo)R指Revenue(收入)。