利用多目標優(yōu)化方法實現(xiàn)的GSON網(wǎng)拓撲構(gòu)建算法

趙 星

(陜西財經(jīng)職業(yè)技術(shù)學院，陜西 咸陽 712000)

利用多目標優(yōu)化方法實現(xiàn)的GSON網(wǎng)拓撲構(gòu)建算法

趙 星

(陜西財經(jīng)職業(yè)技術(shù)學院，陜西 咸陽 712000)

覆蓋網(wǎng)(Overlay)虛擬化能有效分離網(wǎng)絡應用服務與底層網(wǎng)絡基礎(chǔ)設(shè)施，提升服務質(zhì)量和用戶體驗，設(shè)計了一種利用多目標優(yōu)化(multi-objective optimization, 簡稱MOO)的通用覆蓋網(wǎng)(general service overlay network，簡稱GSON)網(wǎng)拓撲構(gòu)建算法(MOO-GSON)。該算法利用多目標優(yōu)化模型提出了以服務節(jié)點和物理鏈路重用為約束，從而提高了虛擬拓撲與物理網(wǎng)絡匹配度，最小化虛擬鏈路代價。降低了網(wǎng)絡總體開銷。采用隨機網(wǎng)絡拓撲進行試驗仿真的結(jié)果表明，在滿足各類約束的條件下，本算法能有效地優(yōu)化時間和成本。

異構(gòu)網(wǎng)絡；QoS參數(shù)；參數(shù)映射；映射模型；映射方法；Omnet

Overlay是移動互聯(lián)網(wǎng)體系中部署為滿足各種新業(yè)務發(fā)展需求的虛擬化網(wǎng)絡。移動互聯(lián)網(wǎng)是互聯(lián)網(wǎng)與移動通信網(wǎng)的融合[1]，Overlay借助虛擬化技術(shù)，在原有網(wǎng)絡基礎(chǔ)之上虛擬化服務節(jié)點以及連接服務節(jié)點的虛擬鏈路組成虛擬網(wǎng)絡。虛擬網(wǎng)通過虛擬節(jié)點和虛擬鏈路相連接，為移動互聯(lián)網(wǎng)的新業(yè)務提供增值服務和QoS保障，形成GSON。核心網(wǎng)絡運營商利用虛擬化技術(shù)， 不僅能夠便捷地在現(xiàn)有網(wǎng)絡架構(gòu)基礎(chǔ)上推出新興服務，而且能夠統(tǒng)一管理各個虛擬網(wǎng)，一方面加快了新服務的部署速度，另一方面降低了基礎(chǔ)設(shè)施的投入成本[2]，并為 QoS 的敏感業(yè)務提供良好的 QoS 保證[3]。

Overlay可以根據(jù)其應用分為多種，包括P2P overlay network，服務覆蓋網(wǎng)(service overlay network，簡稱SON)，內(nèi)容分發(fā)網(wǎng)絡(content deliver network，簡稱CDN)以及虛擬實驗床 PlantLab等。大多數(shù)Overlay服務提供商根據(jù)服務需求、終端用戶的規(guī)模等設(shè)置節(jié)點服務器，節(jié)點通常由服務內(nèi)容提供商與ISP(Internet 服務提供商)簽署相關(guān)服務等級協(xié)議(service level agreement，簡稱SLA)部署，同時向ISP提供帶寬保障[4]。由于應用型的Overlay架構(gòu)、節(jié)點部署，ISP 帶寬預留租用等都需要大的投資資金，拓撲設(shè)計就成為 Overlay 構(gòu)建的關(guān)鍵問題。選擇良好的拓撲構(gòu)建和優(yōu)化算法，能夠滿足運營需求，提供給終端用戶具有端到端QoS保證的Internet增值服務，同時考慮最優(yōu)的拓撲結(jié)構(gòu)，最少的構(gòu)建費用和帶寬預留的租用費用。

Overlay的拓撲構(gòu)建本質(zhì)是在 ISP 提供的底層物理網(wǎng)絡中抽象出一個子網(wǎng)，該子網(wǎng)能夠提供指定節(jié)點間的數(shù)據(jù)傳輸服務。其拓撲是一種層次化拓撲，層次化拓撲在節(jié)點固定的情況下，根據(jù)節(jié)點關(guān)系和互聯(lián)網(wǎng)的自治域(autonomous system)鏈接來生成Overlay的拓撲，其邏輯拓撲和物理拓撲有較好的匹配性，易于優(yōu)化提高網(wǎng)絡的資源利用率和數(shù)據(jù)傳輸性能。本文設(shè)計了一種通用型的服務覆蓋網(wǎng)(GSON)拓撲構(gòu)建算法——基于多目標優(yōu)化的GSON構(gòu)建算法(multi objective optimization，MOO-GSON)，該算法結(jié)合服務節(jié)點和節(jié)點間鏈路性能感知物理拓撲，并利用最小生成樹來優(yōu)化覆蓋網(wǎng)邏輯鏈路，進行算法收斂，具有與物理拓撲匹配度高，整體開銷小的優(yōu)點。

1 國內(nèi)外研究現(xiàn)狀

根據(jù)覆蓋網(wǎng)的結(jié)構(gòu)，其拓撲構(gòu)建方式可以分為集中式拓撲(centralized topology)、分布式非結(jié)構(gòu)化拓撲(decentralized unstructured topology)、分布式結(jié)構(gòu)化拓撲[5]和層次化拓撲(hierarchical control)，集中式拓撲中，Overlay架構(gòu)包括控制節(jié)點和一般節(jié)點，集中式機構(gòu)由于控制節(jié)點存在單點失效，安全性和通信流量問題，因此只針對特定規(guī)模應用[6]。結(jié)構(gòu)化Overlay系統(tǒng)通常利用DHT等來構(gòu)建虛擬的應用層覆蓋網(wǎng)絡，相比起無結(jié)構(gòu)化Overlay和P2P 系統(tǒng)，其路由更有目的性，構(gòu)建并不基于節(jié)點物理位置，易造成邏輯拓撲結(jié)構(gòu)和物理拓撲結(jié)構(gòu)不匹配?；谝苿踊ヂ?lián)網(wǎng)的Overlay整合了多項新業(yè)務應用，作為一種GSON，具有層次化特征。Overlay節(jié)點均為服務器節(jié)點，除路由存儲轉(zhuǎn)發(fā)功能外，還提供其他處理能力，其虛擬鏈路則由多條物理鏈路組成，能夠結(jié)合應用層的業(yè)務需求，選擇相應的應用層資源。

目前，Overlay拓撲構(gòu)建作為覆蓋網(wǎng)路由，資源搜索定位和信息分發(fā)的基礎(chǔ)，對上述功能有極大影響。而Overlay拓撲構(gòu)建中影響Overlay性能的關(guān)鍵問題是拓撲的感知和拓撲的匹配，層次化Overlay構(gòu)建中，由于節(jié)點的部署是固定的，其拓撲發(fā)現(xiàn)和構(gòu)建的關(guān)鍵點在于構(gòu)建拓撲的虛擬鏈路。算法可大致分為2類：一類算法基于坐標和位置信息來優(yōu)化結(jié)構(gòu)化網(wǎng)絡使得拓撲具有更好的匹配性，如有關(guān)文獻提到的基于Chord和基于CAN改進的Overlay構(gòu)建算法；另一類算法基于節(jié)點位置感知底層拓撲構(gòu)建虛擬鏈路和Overlay拓撲，其中較為經(jīng)典的算法分別是最小生成樹算法和臨近連接算法等。

最小生成樹算法在全網(wǎng)狀覆蓋層拓撲的基礎(chǔ)上進行多次最小生成樹的構(gòu)建。KMST鏈路代價為物理層網(wǎng)絡層跳數(shù)，其優(yōu)點是便于實現(xiàn)性能測量開銷最小化，缺點是網(wǎng)絡跳數(shù)感知不能獲得物理鏈路的重用而導致的網(wǎng)絡擁塞?；贙MST同時感知物理鏈路的的Overlay拓撲構(gòu)建算法是拓撲感知K最小生成樹算法，該算法是基于全網(wǎng)狀覆蓋層拓撲，感知物理節(jié)點和鏈路被納入拓撲的次數(shù)，其構(gòu)建最小生成樹代價是鏈路跳數(shù)，當兩跳覆蓋網(wǎng)鏈路通過相同的IP層鏈路，則根據(jù)通過的相同IP鏈路數(shù)目增加這兩條覆蓋網(wǎng)鏈路的代價；因此，算法提供了節(jié)點對在IP層不同的物理路徑匹配，避免了鏈路和節(jié)點的過載。

2 構(gòu)建目標模型

基于移動互聯(lián)網(wǎng)的GSON構(gòu)建準則如下。

1)約束條件。約束條件體現(xiàn)在節(jié)點約束和鏈路約束，節(jié)點約束表示物理節(jié)點的處理能力存在限制，虛擬鏈路不應多次經(jīng)過服務節(jié)點，增加轉(zhuǎn)發(fā)和處理壓力，增大節(jié)點度數(shù)；鏈路約束包括構(gòu)造的邏輯鏈路最大可用帶寬，跳數(shù)存在限制，由于鏈路可用帶寬限制，要求物理鏈路不能重復被多條虛擬鏈路抽象，當出現(xiàn)物理鏈路重用，應相應增大虛擬鏈路代價。

2)最大最小化要求。最大最小化要求體現(xiàn)在感知物理網(wǎng)絡基礎(chǔ)上進行拓撲優(yōu)化，在滿足業(yè)務運營要求基礎(chǔ)上，構(gòu)建GSON能夠最大化網(wǎng)絡資源利用率，最小化網(wǎng)絡構(gòu)建的時間代價和成本代價，最大化提升用戶體驗以及可用資源利用率。

(1)

(2)

B(eij)≥B0,w(eij)≤L

(3)

在滿足節(jié)點約束和鏈路約束的條件下，最小化網(wǎng)絡構(gòu)建的時間和成本代價，并盡可能最大化用戶體驗和網(wǎng)絡資源利用率，該問題可以被完全建模成一個多目標優(yōu)化模型，可以使用整數(shù)線性規(guī)劃來求解模型，該模型中c,b,a均為確定的參數(shù)：

(4)

根據(jù)整數(shù)線性約束集合具有的結(jié)構(gòu)特點，整數(shù)線性約束集合中的復雜約束通過拉格朗日乘子被引入到目標函數(shù)中，導出具有約束系數(shù)矩陣是全幺模矩陣特點的整數(shù)線性規(guī)劃問題，從而這類整數(shù)線性規(guī)劃問題能用單純形法迭代地求解。該問題采用多目標優(yōu)化建模抽象Overlay拓撲構(gòu)建問題，利用線性規(guī)劃和單純形法獲得模型的最優(yōu)解可以作為算法優(yōu)劣的評價標準。

3 算法流程

根據(jù)建模階段的理論結(jié)果，將算法分成兩階段，第一階段實現(xiàn)滿足約束，滿足節(jié)點和鏈路能力的約束需求，構(gòu)建虛擬鏈路時，將經(jīng)過的重用節(jié)點虛擬鏈路刪除，并將重用的物理鏈路代價增大；第二階段實現(xiàn)優(yōu)化需求，在原有虛擬鏈路基礎(chǔ)上，根據(jù)最小化條件進行拓撲優(yōu)化。因此，算法分為拓撲構(gòu)建和拓撲優(yōu)化兩階段；拓撲構(gòu)建是在部署節(jié)點的Overlay上，根據(jù)物理網(wǎng)絡鏈路，構(gòu)建全相連的虛擬鏈路，計算每一個虛擬節(jié)點與其他節(jié)點之間虛擬鏈路代價，鏈路代價計算利用節(jié)點、跳數(shù)以及鏈路重用作為約束，在每次進行計算時其值會隨著經(jīng)過的節(jié)點以及重用的鏈路跳數(shù)動態(tài)改變，深度遍歷以后最終的輸出是一個或多個無環(huán)無重邊的無向連通分支，分支之間是不連通的；拓撲優(yōu)化是在多個分支基礎(chǔ)上構(gòu)建滿足最小化的子圖，遍歷拓撲判斷連通性，針對每個子圖構(gòu)建最小生成樹，得到生成樹森林，形成GSON的虛擬鏈路。

在拓撲構(gòu)建階段，排序服務節(jié)點，將所有節(jié)點設(shè)為全相連，感知服務器節(jié)點間的物理路徑，選取網(wǎng)絡層拓撲的跳數(shù)作為路徑的代價，構(gòu)建兩虛擬節(jié)點之間的虛擬鏈路，回避服務節(jié)點，如虛擬鏈路經(jīng)過Overlay中的節(jié)點，將w(eij)標記為無窮大，并跳出計算；對物理鏈路的重用進行計數(shù)，每次選取同一跳物理鏈路時，該虛擬鏈路的代價w(eij)增加一個物理單位；因此，鏈路代價值將隨經(jīng)過節(jié)點和鏈路重用而改變。構(gòu)建拓撲得到的拓撲結(jié)構(gòu)較復雜，節(jié)點之間存在多個虛擬鏈路，需要進一步優(yōu)化，剪去多余鏈路，縮小路由表項規(guī)模，便于實現(xiàn)GSON的路由，資源查找定位以及多播等多項服務網(wǎng)絡的通用功能。

在拓撲優(yōu)化階段，選用圖的深度遍歷算法或者廣度遍歷算法從根出發(fā)對拓撲構(gòu)建得到無向圖進行遍歷，得到1個或多個分支，多個分支之間是不連通的。采用Prim等貪心策略執(zhí)行最小生成樹算法，得到生成樹或者生成森林(每個生成樹則為1個連通分支，生成森林則為該圖的連通分支集合)?；谧钚』瘶?gòu)建成本代價和時間代價作為一個優(yōu)化后的模型，結(jié)構(gòu)簡單，便于應用服務的加載，能有效提高業(yè)務的QoS和用戶的QoE。

基于MOO的GSON網(wǎng)構(gòu)建拓撲算法(MOO-GSON)為

輸入：物理網(wǎng)絡的拓撲G。

輸出： 構(gòu)建代價最小且感知物理拓撲的Overlay

1)初始化所有Overlay 節(jié)點，并將各個節(jié)點設(shè)為全相連，邊權(quán)值為null。

2)計算全相連虛擬鏈路的實際值，并賦值；當虛擬鏈路經(jīng)過Overlay節(jié)點，則設(shè)邊權(quán)值為∞，跳出；當虛擬鏈路經(jīng)過重用的物理鏈路，該虛擬鏈路權(quán)值動態(tài)增加，繼續(xù)(得到虛擬鏈路的構(gòu)建拓撲)。

3)深度遍歷構(gòu)建好的拓撲，得到各個連通分支(連通分支數(shù)≥1)。

4)深度遍歷構(gòu)建好的拓撲，得到各個連通分支最小生成樹。

5)保留各個連通分支最小生成樹的邊，構(gòu)成優(yōu)化的拓撲。

基于多目標優(yōu)化的GSON拓撲構(gòu)建算法特點在于：1)在網(wǎng)絡層拓撲感知部分，考慮鏈路復用保證了網(wǎng)絡層鏈路較低的重用，并避免了服務節(jié)點的重復計算，使得構(gòu)建出的覆蓋網(wǎng)與網(wǎng)絡層拓撲保持較高的匹配度，且具有更好的抗毀性能；2)基于最小生成樹算法優(yōu)化邏輯鏈路，使整個覆蓋網(wǎng)拓撲的代價為最小，有效保證服務節(jié)點間的通信，保證了更好的業(yè)務QoS和用戶QoE。

4 仿真實驗與數(shù)據(jù)分析

4.1 仿真環(huán)境

本文采用GT-ITM拓撲產(chǎn)生器創(chuàng)建平面隨機圖進行試驗仿真，GT-ITM是由喬治亞理工學院于2000年研發(fā)并投入到大規(guī)模Internet的仿真模擬的研究中。許多文獻的研究都使用該拓撲生成器進行模擬仿真。隨機拓撲結(jié)構(gòu)適用于大規(guī)模網(wǎng)絡拓撲仿真。使用隨機拓撲進行仿真可以客觀驗證算法的普遍適用性，在和同類算法進行對比仿真實驗時其仿真結(jié)果更為可信。

GT-ITM可生成各種平面隨機圖作為模型?；灸Ｐ褪羌冸S機模型，隨著邊概率函數(shù)不同，GT-ITM包括Waxman 1，Waxman 2 和Doar-Leslie多種冪律拓撲。本文采用Waxman 1模型。在Waxman 1模型中，從節(jié)點u到v的存在邊概率為P(u,v)=α×exp(-d/(βL))，其中0<α，β≤1，d是節(jié)點u,v的歐式距離，L是平面上任意兩節(jié)點間的最大距離。當增加α時，模型將有更多短邊，更長跳數(shù)，β增大則增加圖中長邊比例。

采用文件形式輸入模擬器構(gòu)建模型，拓撲的節(jié)點隨機選取，智能服務器在所有節(jié)點中占有的比例為Ps。本試驗的目的在于驗證算法有效性，在有效優(yōu)化拓撲基礎(chǔ)上，盡量減小網(wǎng)絡時間代價，從節(jié)點度和時間復雜度來驗證算法。服務節(jié)點的節(jié)點度決定了轉(zhuǎn)發(fā)的大小以及Overlay中和其他服務節(jié)點相連的有效路徑的多少。本文設(shè)計了GSON拓撲構(gòu)建算法中，節(jié)點度通過虛擬鏈路數(shù)來獲得，通常情況下，當其他性能參數(shù)一致，則節(jié)點度越低越好，因為高節(jié)點度會增大網(wǎng)絡拓撲的維護開銷。GSON拓撲構(gòu)建算法除了能夠構(gòu)建出與物理層匹配的拓撲外，還需控制其時間性能，使得服務節(jié)點能夠有效轉(zhuǎn)發(fā)數(shù)據(jù)。

4.2 數(shù)據(jù)分析

本算法在仿真過程中選取了2種Overlay拓撲構(gòu)建算法，即最小生成樹算法(KMST算法)和最小生成樹算法(TKMST算法)，算法選取節(jié)點度和算法時間性能進行評估。節(jié)點度體現(xiàn)了該節(jié)點在邏輯鏈路路徑數(shù)，節(jié)點度包含出度入度，通常較低較平均的節(jié)點度能體現(xiàn)網(wǎng)絡資源的均衡利用。算法的時間復雜度是算法的直接開銷，體現(xiàn)了實際組網(wǎng)應用的價值。3種算法節(jié)點度和時間復雜度的性能分析對比如圖1和圖2所示。圖1中，橫坐標為GT-ITM隨機拓撲中的參數(shù)α，α值的大小與網(wǎng)絡中節(jié)點個數(shù)成正比；圖2中，橫坐標為另一個參數(shù)β，β增加節(jié)點不變情況下邊長增加。仿真時，本文將參數(shù)設(shè)定為：s=0.3。

圖1 3種算法節(jié)點度、時間復雜度與節(jié)點數(shù)目關(guān)系對比

圖2 3種算法節(jié)點度、時間復雜度與邊長關(guān)系對比

圖1為本算法與KMST算法、TKMST算法仿真時的節(jié)點度、時間復雜度與節(jié)點數(shù)目之間關(guān)系的對比情況。TKMS-T算法的平均節(jié)點度最低，本算法的平均節(jié)點度處于中間位置，而KMST算法的平均節(jié)點度遠高于前2個算法。其主要原因是本算法在拓撲構(gòu)建時充分考慮節(jié)點的重用，因此算法在節(jié)點度上高于KMST，低于TKMST。對于時間復雜度，本算法在節(jié)點度數(shù)增加時，其時間復雜度增幅在二者之間，但在節(jié)點數(shù)目增多時，收斂較快。

圖 2為本算法與KMST算法、TKMST算法仿真時的節(jié)點度、時間復雜度與邊長度之間關(guān)系的對比情況。長邊比例增加，物理跳數(shù)不變，將降低本算法的鏈路復用，而長邊比例對三種算法的時間復雜度關(guān)系暫無明顯影響，本算法時間復雜度仍處于二者之間。考慮到算法的構(gòu)建成功率，仿真中將有30%左右概率KMST算法和TKMST算法無法完成覆蓋網(wǎng)構(gòu)建，主要原因是KMST算法和TKMST算法在構(gòu)建最小生成樹的拓撲上遇到了非連通分支，導致算法的非正常收斂。而本算法考慮非連通分支能夠在此基礎(chǔ)上判斷并進行拓撲優(yōu)化，因此本算法更具實用性。

5 結(jié)語

網(wǎng)絡虛擬化將應用服務與物理網(wǎng)絡設(shè)施分離，從而在不改變網(wǎng)絡設(shè)施的基礎(chǔ)上，有效提升業(yè)務QoS和用戶QoE。本文關(guān)注Overlay的拓撲構(gòu)建問題，采用多目標優(yōu)化的方法對該問題進行建模，分析了求解的線性規(guī)劃方法，給出了為解決鏈路和節(jié)點重用的構(gòu)建基本方案，該算法基于最小生成樹方法，將原始Overlay拓撲進行優(yōu)化，得到一個簡約高效的Overlay的拓撲結(jié)構(gòu)，減小了Overlay構(gòu)建的時間和代價成本，簡化了服務器節(jié)點路由器表空間。為驗證本方案的有效和實用性，從理論分析和仿真角度做出了對比，仿真采用隨機網(wǎng)絡生成器提供試驗數(shù)據(jù)，和傳統(tǒng)算法KMST和TKMST相比，優(yōu)化過程增加了對節(jié)點的感知和算法收斂條件，拓撲構(gòu)建結(jié)果對物理網(wǎng)絡有更好匹配度。試驗結(jié)果表明，該算法在滿足各約束的基礎(chǔ)上，有效優(yōu)化了生成的時間和成本代價。

[1]李偉, 徐正全,楊鑄.應用于移動互聯(lián)網(wǎng)的 Peer-to-Peer 關(guān)鍵技術(shù)[J]. 軟件學報, 2009, 20(8): 2199-2213.

[2]齊寧, 均衡虛擬網(wǎng)構(gòu)建算法研究[J]. 電子與信息學報, 2011(6): 1301-1306.

[3]Zhi L, Mohapatra P. QRON: QoS-aware routing in overlay networks. Selected Areas in Communications, IEEE Journal on, 2004, 22(1):29-40.

[4]Duan Z, Zhang Z, Hou Y T. Service overlay networks: SLAs, QoS, and bandwidth provisioning. IEEE/ACM Transactions on Networking (TON), 2003，11(6):870-883.

[5]張棟,吳春明,姜明,等. 大規(guī)模服務覆蓋網(wǎng)拓撲設(shè)計[J]. 電子與信息學報, 2010(4): 841-845.

[6]Lua E K. A survey and comparison of peer-to-peer overlay network schemes[J]. IEEE Communications Surveys and Tutorials, 2005，7(1-4): 72-93.

責任編輯李思文

OverlayConstructionandOptimizationMethodwithMOO

ZHAO Xing

(Shaanxi Vocational College of Finance and Economics, Xianyang 712000, China)

Considering that the Overlay (network) virtualization can effectively separate network application service and the underlying network infrastructure, improve service quality and user experience. A way was designed by using a multi-objective optimization (multi - objective optimization, MOO), a general network (GSON) network topology construction algorithm (MOO-GSON), the algorithm using the multi-objective Optimization model is put forward to the service nodes and the physical link reuse as constraint, thus improve the virtual topology and the physical network compatibility, minimized the virtual link cost, reduces the network overhead as a whole. Using random network topology experiment simulation, the results showed that under the condition of satisfying various constraints, the algorithm can effectively optimize the time and costs.

heterogeneous network, QoS parameters, parameter mapping, mapping model, mapping method, Omnet

TP 393.2

：A

趙星(1982-)，男，講師，主要從事計算機技術(shù)及教學等方面的研究。

2015-01-05