[發明專利]一種多拓撲虛擬網絡映射方法

有效

• 申請號: 201110342242.5
• 申請日: 2011-11-03
• 公開（公告）號: CN102546232A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 黃韜;劉江;王健;陳建亞;劉韻潔
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種多拓撲虛擬網絡映射方法，在一個時間窗內進行一次虛擬網絡映射的步驟包括：

A.釋放前一個時間窗內離開的虛網請求占用的底層物理網資源，離開的虛網請求包括完成服務的請求和被主動拒絕的請求；虛網請求包含虛網節點請求和虛網鏈路請求兩部分；

B.統計本時間窗內到達的虛網請求，到達的虛網請求包括新到達的請求和重新排隊的請求；

C.將步驟B中統計的到達的虛網請求按照其收入(Revenue)從大到小進行排序，然后根據虛網請求者使用的變量TOPO值，對虛網請求的拓撲類型進行識別，然后分別使用相應的隨機型，星型，環形，樹型拓撲映射算法將到達的虛網請求按順序映射至底層物理網絡，若其中任意一個到達的虛網請求映射成功，即虛網節點和虛網鏈路同時映射成功，則更新底層物理網絡的狀態；若映射失敗，則將該虛網請求送至等待隊列，等待下個時間窗或直接拒絕。

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

C1)首先進行虛網請求節點映射，將虛網請求按照其收入從大到小進行排序，形成請求隊列(Q_request)；

C2)判斷當前請求隊列中是否存在虛網請求，如果是，執行步驟C3，如果否，執行步驟D1；

C3)選擇當前請求隊列中排在首位的虛網請求，根據TOPO的取值0、1、2、3，分別執行下列C3.1、C3.2、C3.3、C3.4子步驟，TOPO取除0、1、2、3的其他值，則使用缺省值TOPO＝0，并執行步驟C3.1；

C3.1)TOPO＝0，將該虛網請求內的虛網節點(V_node)按照其剩余資源(Available?Resource，AR)從大到小排序，形成虛網節點隊列(Q_{v_node})；

C3.2)TOPO＝1，將該虛網請求內的虛網節點(V_node)按照中心節點排首位、其余節點按照剩余資源(Available?Resource，AR)從大到小排序，形成虛網節點隊列(Q_{v_node})；

C3.3)TOPO＝2，將該虛網請求內的虛網節點(V_node)按照剩余資源(Available?Resource，AR)最大節點排首位，其余節點按照環型連接順序排序，形成虛網節點隊列(Q_{v_node})；

C3.4)TOPO＝3，將該虛網請求內的虛網節點(V_node)按照上層節點優先、同層節點按照父節點順序、同一父節點按照剩余資源(Available?Resource，AR)從大到小排序，形成虛網節點隊列(Q_{v_node})；

C4)判斷當前虛網節點隊列中是否存在虛網節點，如果是，執行步驟C5，如果否，則將當前請求隊列中排在首位的虛網請求移出請求對列，執行步驟C2；

C5)選擇當前虛網節點隊列中排在首位的虛網節點，在底層物理網中選擇物理網節點(S_node)，選擇的物理網節點的CPU資源不小于當前虛網節點隊列中排在首位的虛網節點CPU資源；并將滿足CPU條件的物理網節點組成物理網節點子集(S_{s_node})

C6)判斷物理網節點子集中是否存在物理網節點，如果是，執行步驟C7，如果否，則當前虛網請求隊列中排在首位虛網請求映射失敗，將該請求移出虛網請求隊列，并送至下個時間窗的等待隊列或拒絕請求，執行步驟C2；

C7)根據TOPO的取值0、1、2、3，分別執行C7.1、C7.2、C7.3、C7.4子步驟，TOPO取除0、1、2、3的其他值，則使用缺省值TOPO＝0，并執行步驟C7.1；

C7.1)TOPO＝0，選出當前物理網節點子集中隨機型加權剩余資源(General?Weighted?Available?Resource，GWAR)最大的物理網節點，并將當前虛網節點隊列中排在首位的虛網節點映射至該物理網節點，將當前虛網節點隊列中排在首位的虛網節點移出虛網節點隊列，執行步驟C4；

C7.2)TOPO＝1，選出當前物理網節點子集中星型加權剩余資源(Star?Weighted?Available?Resource，SWAR)最大的物理網節點，并將當前虛網節點隊列中排在首位的虛網節點映射至該物理網節點，將當前虛網節點隊列中排在首位的虛網節點移出虛網節點隊列，執行步驟C4；

C7.3)TOPO＝2，選出當前物理網節點子集中環型加權剩余資源(Ring?Weighted?Available?Resource，RWAR)最大的物理網節點，并將當前虛網節點隊列中排在首位的虛網節點映射至該物理網節點，將當前虛網節點隊列中排在首位的虛網節點移出虛網節點隊列，執行步驟C4；

C7.4)TOPO＝3，選出當前物理網節點子集中樹型加權剩余資源(Tree?Weighted?Available?Resource，TWAR)最大的物理網節點，并將當前虛網節點隊列中排在首位的虛網節點映射至該物理網節點，將當前虛網節點隊列中排在首位的虛網節點移出虛網節點隊列，執行步驟C4。

C8)開始進行鏈路映射，將節點映射成功的虛網請求按收入從大到小進行排序，形成請求隊列(Q_request)。

C9)判斷當前請求隊列中是否存在虛網請求，如果是，執行步驟C10，如果否，當前時間窗的映射算法結束；

C10)選擇當前請求隊列中排在首位的虛網請求，并將該虛網請求內的虛網鏈路(V_link)按照其帶寬(BW)從大到小排序，形成虛網鏈路隊列(Q_{v_link})；

C11)判斷當前虛網鏈路隊列中是否存在虛網鏈路，如果是，執行步驟C12，如果否，則將當前請求隊列中排在首位的虛網請求移出請求隊列，執行步驟C9；

C12)選擇當前虛網鏈路隊列中排在首位的虛網鏈路，使用K最短路徑(K-Shortest)算法依次尋找第1至K條最短路徑，這些路徑由一條或多條底層物理網鏈路(S_link)組成，K為大于1的整數，僅保留這K條路徑這樣的路徑：組成路徑的所有物理網鏈路的最低帶寬滿足當前虛網鏈路隊列中排在首位的虛網鏈路帶寬；保留的路徑形成物理網路徑子集(S_{s_path})；

C13)判斷當前物理網路徑子集中是否存在物理網路徑，如果是，執行步驟C14；如果否，則當前虛網請求隊列中排在首位虛網請求映射失敗，將該請求移出虛網請求隊列，并送至下個時間窗的等待隊列或拒絕請求，執行步驟C9；

C14)將當前虛網鏈路隊列中排在首位的虛網鏈路映射至當前物理網路徑子集中的最短路徑，將當前虛網鏈路隊列中排在首位的虛網鏈路移出虛網鏈路隊列，執行步驟C11。