[發(fā)明專利]一種網(wǎng)絡(luò)節(jié)點排序方法及虛擬網(wǎng)絡(luò)映射方法

有效

• 申請?zhí)枺?/td>: 201810600998.7
• 申請日: 2018-06-12
• 公開（公告）號: CN108833162B
• 公開（公告）日: 2020-10-27
• 發(fā)明（設(shè)計）人: 曲樺;趙季紅;牛浩時;李靜;趙建龍
• 申請（專利權(quán)）人: 西安交通大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/911;G06F9/455
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 楊博

本發(fā)明公開了一種提供了一種網(wǎng)絡(luò)節(jié)點排序方法及虛擬網(wǎng)絡(luò)映射方法，該方法基于向量中心度的節(jié)點重要性指標(biāo)計算方法，對網(wǎng)絡(luò)節(jié)點的重要性指標(biāo)進(jìn)行計算，同時考慮網(wǎng)絡(luò)節(jié)點自身資源屬性以及直連節(jié)點對節(jié)點重要性的影響和非直連的鄰居網(wǎng)絡(luò)節(jié)點對當(dāng)前節(jié)點重要性的影響，最后根據(jù)網(wǎng)絡(luò)節(jié)點重要性指標(biāo)確定虛擬網(wǎng)絡(luò)節(jié)點的映射順序。能夠有限考慮資源豐富的底層物理網(wǎng)絡(luò)節(jié)點和鏈路，有效降低網(wǎng)絡(luò)發(fā)生碎片的概率；并且合理利用物理網(wǎng)絡(luò)資源。

技術(shù)領(lǐng)域

本發(fā)明屬于搭建虛擬網(wǎng)絡(luò)技術(shù)領(lǐng)域；具體涉及一種網(wǎng)絡(luò)節(jié)點排序方法及虛擬網(wǎng)絡(luò)映射方法。

背景技術(shù)

為了構(gòu)建全新的互聯(lián)網(wǎng)體系架構(gòu)，以普林斯頓大學(xué)Larry Peterson教授為首的團(tuán)隊于2005年提出使用網(wǎng)絡(luò)虛擬化技術(shù)推動未來網(wǎng)絡(luò)體系架構(gòu)的根本性變革。虛擬化技術(shù)是一種高度的抽象，隱藏了底層的實現(xiàn)細(xì)節(jié)，在虛擬化環(huán)境下虛擬網(wǎng)絡(luò)就好像真實的物理網(wǎng)絡(luò)，并且多個虛擬網(wǎng)絡(luò)可以同時使用底層的物理基礎(chǔ)設(shè)施。網(wǎng)絡(luò)虛擬化的基本實體是虛擬網(wǎng)絡(luò)，一個虛擬網(wǎng)絡(luò)是一組虛擬節(jié)點和虛擬鏈路的形成的虛擬拓?fù)洹Ｍ粋€物理網(wǎng)絡(luò)上的多個邏輯網(wǎng)絡(luò)，屬于不同的服務(wù)提供商，基礎(chǔ)設(shè)施提供商可以向不同的虛擬網(wǎng)絡(luò)提供不同的網(wǎng)絡(luò)拓?fù)滟Y源，不同的虛擬網(wǎng)絡(luò)的使用和管理相互獨立，彼此互不影響。近年來，世界各國和許多國際組織都認(rèn)識到網(wǎng)絡(luò)虛擬化技術(shù)對于未來網(wǎng)絡(luò)的重要意義，陸續(xù)展開了許多相關(guān)的大型研究項目，例如，GENI、4WARD、PlanetLab、VITRO等，這些都極大的推動了網(wǎng)絡(luò)虛擬化的發(fā)展。

在網(wǎng)絡(luò)虛擬化環(huán)境中一個重要的技術(shù)就是虛擬網(wǎng)絡(luò)映射，由于網(wǎng)絡(luò)在運(yùn)行過程中存在大量的不確定因素，如網(wǎng)絡(luò)中節(jié)點的緩存隊列的變化、鏈路的帶寬和延遲的變化等等，造成了物理網(wǎng)絡(luò)中資源的動態(tài)改變，具有不確定性。如何高效的對底層資源進(jìn)行管理和分配，完成虛擬網(wǎng)絡(luò)請求的處理，為用戶提供所需的網(wǎng)絡(luò)資源，保證服務(wù)質(zhì)量，這是網(wǎng)絡(luò)虛擬化必須解決的問題，這類問題廣泛被稱為虛擬網(wǎng)絡(luò)映射問題(Virtual Network Mapping)或虛擬網(wǎng)絡(luò)嵌入問題(VirtualNetwork Embedding)

在虛擬網(wǎng)絡(luò)映射問題中，有一種典型的算法叫做兩階段的映射算法，這類算法執(zhí)行虛擬網(wǎng)絡(luò)映射分為兩個步驟節(jié)點映射和鏈路映射，在進(jìn)行節(jié)點映射時需要根據(jù)節(jié)點的資源對節(jié)點進(jìn)行排序，然后執(zhí)行映射，鏈路映射時采用最短路徑算法或多商品流算法。該類算法的執(zhí)行策略是在進(jìn)行虛擬網(wǎng)絡(luò)映射時，應(yīng)該優(yōu)先占用底層物理資源豐富的節(jié)點和鏈路，這樣可以避免某些節(jié)點和鏈路的資源被過早的消耗完導(dǎo)致物理網(wǎng)絡(luò)資源的碎片化，使得總的資源足夠，但是無法分配的情況出現(xiàn)。

發(fā)明內(nèi)容

本發(fā)明提供了一種網(wǎng)絡(luò)節(jié)點排序方法；在虛擬網(wǎng)絡(luò)映射過程中的節(jié)點映射階段確定網(wǎng)絡(luò)節(jié)點的映射順序，以及相應(yīng)的映射關(guān)系，從而達(dá)到對資源合理利用，減少局部節(jié)點或鏈路資源用盡導(dǎo)致網(wǎng)絡(luò)碎片化的情況出現(xiàn)。

本發(fā)明還提供了一種虛擬網(wǎng)絡(luò)映射方法，基于上述網(wǎng)絡(luò)節(jié)點排序方法構(gòu)建虛擬網(wǎng)絡(luò)，能夠有限考慮資源豐富的底層物理網(wǎng)絡(luò)節(jié)點和鏈路，有效降低網(wǎng)絡(luò)發(fā)生碎片的概率；并且合理利用物理網(wǎng)絡(luò)資源。

本發(fā)明的技術(shù)方案是：一種網(wǎng)絡(luò)節(jié)點排序方法，包括基于向量中心度思想計算網(wǎng)絡(luò)節(jié)點的重要性指標(biāo)，其計算公式為：其中γ_i-1γ_i，Nⁱ(n)為當(dāng)前節(jié)點i跳的節(jié)點集合；其中γ₀·r(n)表示節(jié)點自身的資源大小，r(n)為歸一化后網(wǎng)絡(luò)節(jié)點n的局部資源；表示鄰居節(jié)點對當(dāng)前節(jié)點重要性的貢獻(xiàn)；計算得到所有節(jié)點的重要性，根據(jù)節(jié)點重要性對虛擬網(wǎng)絡(luò)節(jié)點和物理網(wǎng)絡(luò)節(jié)點進(jìn)行遞減排序。

更進(jìn)一步的，本發(fā)明的特點還在于：

其中鄰居節(jié)點對當(dāng)前節(jié)點重要性的貢獻(xiàn)包括直連鄰居節(jié)點對當(dāng)前節(jié)點重要性的貢獻(xiàn)和非直連鄰居節(jié)點對當(dāng)前節(jié)點重要性的貢獻(xiàn)；表示為：