趙 星

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

利用多目標(biāo)優(yōu)化方法實(shí)現(xiàn)的GSON網(wǎng)拓?fù)錁?gòu)建算法

趙 星

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

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

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

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

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

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

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

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

目前，Overlay拓?fù)錁?gòu)建作為覆蓋網(wǎng)路由，資源搜索定位和信息分發(fā)的基礎(chǔ)，對上述功能有極大影響。而Overlay拓?fù)錁?gòu)建中影響Overlay性能的關(guān)鍵問題是拓?fù)涞母兄屯負(fù)涞钠ヅ?，層次化Overlay構(gòu)建中，由于節(jié)點(diǎn)的部署是固定的，其拓?fù)浒l(fā)現(xiàn)和構(gòu)建的關(guān)鍵點(diǎn)在于構(gòu)建拓?fù)涞奶摂M鏈路。算法可大致分為2類：一類算法基于坐標(biāo)和位置信息來優(yōu)化結(jié)構(gòu)化網(wǎng)絡(luò)使得拓?fù)渚哂懈玫钠ヅ湫?，如有關(guān)文獻(xiàn)提到的基于Chord和基于CAN改進(jìn)的Overlay構(gòu)建算法；另一類算法基于節(jié)點(diǎn)位置感知底層拓?fù)錁?gòu)建虛擬鏈路和Overlay拓?fù)?，其中較為經(jīng)典的算法分別是最小生成樹算法和臨近連接算法等。

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

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

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

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

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

(1)

(2)

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

(3)

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

(4)

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

3 算法流程

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

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

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

基于MOO的GSON網(wǎng)構(gòu)建拓?fù)渌惴?MOO-GSON)為

輸入：物理網(wǎng)絡(luò)的拓?fù)銰。

輸出： 構(gòu)建代價(jià)最小且感知物理拓?fù)涞腛verlay

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

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

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

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

5)保留各個(gè)連通分支最小生成樹的邊，構(gòu)成優(yōu)化的拓?fù)洹?/p>

基于多目標(biāo)優(yōu)化的GSON拓?fù)錁?gòu)建算法特點(diǎn)在于：1)在網(wǎng)絡(luò)層拓?fù)涓兄糠?，考慮鏈路復(fù)用保證了網(wǎng)絡(luò)層鏈路較低的重用，并避免了服務(wù)節(jié)點(diǎn)的重復(fù)計(jì)算，使得構(gòu)建出的覆蓋網(wǎng)與網(wǎng)絡(luò)層拓?fù)浔３州^高的匹配度，且具有更好的抗毀性能；2)基于最小生成樹算法優(yōu)化邏輯鏈路，使整個(gè)覆蓋網(wǎng)拓?fù)涞拇鷥r(jià)為最小，有效保證服務(wù)節(jié)點(diǎn)間的通信，保證了更好的業(yè)務(wù)QoS和用戶QoE。

4 仿真實(shí)驗(yàn)與數(shù)據(jù)分析

4.1 仿真環(huán)境

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

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

[2]齊寧, 均衡虛擬網(wǎng)構(gòu)建算法研究[J]. 電子與信息學(xué)報(bào), 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ù)覆蓋網(wǎng)拓?fù)湓O(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 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.

責(zé)任編輯李思文

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-)，男，講師，主要從事計(jì)算機(jī)技術(shù)及教學(xué)等方面的研究。

2015-01-05