梁寧寧,蘭巨龍,程國振,楊 琴
(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州450002;2.78006部隊 成都610066)
隨著網(wǎng)絡(luò)業(yè)務(wù)形態(tài)的不斷豐富、應(yīng)用規(guī)模的不斷擴大,互聯(lián)網(wǎng)為人類工作生活提供了便利。然而,由于當(dāng)前IP承載模式的簡單僵化、功能單一,基礎(chǔ)網(wǎng)絡(luò)所能提供的服務(wù)與業(yè)務(wù)需求之間的差距日趨顯著[1]。
基于此,可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系將底層網(wǎng)絡(luò)與服務(wù)提供在邏輯上相分離,底層網(wǎng)絡(luò)為承載網(wǎng)提供網(wǎng)絡(luò)資源,可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)為用戶提供定制服務(wù),而網(wǎng)絡(luò)服務(wù)的提供主要通過為用戶構(gòu)建服務(wù)承載網(wǎng)的方式實現(xiàn)[2]??芍貥?gòu)服務(wù)承載網(wǎng)(reconfigurable service carrying network,RSCN)優(yōu)先考慮業(yè)務(wù)需求與網(wǎng)絡(luò)拓?fù)洹①Y源狀態(tài)等條件,構(gòu)建出多個在底層物理資源上存在交集,能夠提供不同服務(wù)能力的承載子網(wǎng),如圖1所示。
圖1 可重構(gòu)服務(wù)承載網(wǎng)示意
服務(wù)承載網(wǎng)的構(gòu)建是指依據(jù)某種約束條件,將業(yè)務(wù)需求映射到底層網(wǎng)絡(luò)的相應(yīng)物理路徑,并在路徑上分配帶寬的過程。其本質(zhì)是底層資源分配問題?,F(xiàn)有服務(wù)承載網(wǎng)構(gòu)建存在以下兩個問題:首先,現(xiàn)有構(gòu)建方法一般假設(shè)不同業(yè)務(wù)并發(fā)地申請有限的底層資源,業(yè)務(wù)之間相互隔離,忽略了業(yè)務(wù)間的競爭;其次,現(xiàn)有服務(wù)承載網(wǎng)構(gòu)建算法一般是在底層網(wǎng)絡(luò)拓?fù)渥兓ǖ讓庸?jié)點或鏈路失效)或者新到達(dá)請求被拒絕時執(zhí)行重映射,沒有涉及不同業(yè)務(wù)場景下的動態(tài)構(gòu)建措施。
在不同業(yè)務(wù)對有限的底層網(wǎng)絡(luò)進行共享時,如何根據(jù)業(yè)務(wù)需求建立服務(wù)承載網(wǎng),并實時感知業(yè)務(wù)變化,動態(tài)調(diào)整服務(wù)承載網(wǎng)的構(gòu)建,以期實現(xiàn)整體系統(tǒng)的利益最大化,這是本文要討論的問題。
為解決上述問題,本文提出了一種基于拍賣博弈的可重構(gòu)服務(wù)承載網(wǎng)動態(tài)構(gòu)建 (dynamic auction game-based reconfigurable service carrying network construction,DAGR)算法,以拍賣機制為基礎(chǔ),設(shè)計簡單的定價方式,降低系統(tǒng)的附加處理和計算負(fù)擔(dān)。引入合作博弈理論并進行周期映射,在最大化承載網(wǎng)總體構(gòu)建收益的同時,減少系統(tǒng)開銷。具體過程如圖2所示。首先各業(yè)務(wù)提出自身的構(gòu)建需求,由基于拍賣的定價機制計算各業(yè)務(wù)需支付的費用,并返回業(yè)務(wù),然后對于確定加入網(wǎng)絡(luò)的業(yè)務(wù),引入以最大化系統(tǒng)效用為目標(biāo)的合作博弈理論構(gòu)建服務(wù)承載網(wǎng),對底層資源進行分配。
圖2 基于拍賣博弈的可重構(gòu)服務(wù)承載網(wǎng)架構(gòu)
當(dāng)前有關(guān)服務(wù)承載網(wǎng)構(gòu)建的研究主要集中在資源分配和網(wǎng)絡(luò)映射等方面[3~7]。參考文獻(xiàn)[8]以負(fù)載均衡為目標(biāo),首先將虛擬節(jié)點映射到距離已映射虛擬節(jié)點較近且負(fù)載最輕的底層節(jié)點上,而后使用最短路徑算法映射虛擬鏈路,并根據(jù)底層網(wǎng)絡(luò)資源狀況對承載網(wǎng)進行重映射。參考文獻(xiàn)[9]提出了節(jié)點與鏈路同時考慮的一步映射算法,然而由于該算法是基于分布式的,在性能和最優(yōu)性方面都與集中式存在差距。且算法沒有動態(tài)考慮構(gòu)建請求的生存時間,即為已允許的構(gòu)建需求所分配的資源將持久分配,這對新進請求的加入造成限制。參考文獻(xiàn)[10]提出了一種協(xié)調(diào)節(jié)點和鏈路映射的數(shù)學(xué)規(guī)劃。使用虛擬節(jié)點地理位置作為啟發(fā)式信息減少搜索空間,將造成熱點問題。且映射方案基于簡單經(jīng)濟模型構(gòu)建,其定價/花費是線性函數(shù),沒有提供能夠最大化底層網(wǎng)絡(luò)的承載網(wǎng)構(gòu)建請求之間的競爭機制。
為了提高服務(wù)承載網(wǎng)請求接受率,最大化成本收益,博弈論也日益受到研究者的關(guān)注。參考文獻(xiàn)[11]設(shè)計了一種分布式算法,以實現(xiàn)數(shù)據(jù)中心網(wǎng)絡(luò)中有效公平的帶寬分配。算法通過調(diào)整基礎(chǔ)帶寬,為云提供者提供了公平共享與最小數(shù)據(jù)保障之間的均衡折中。參考文獻(xiàn)[12]針對視頻數(shù)據(jù)爆發(fā)性增長,提出了一種整數(shù)規(guī)劃算法;并通過綜合考慮視頻片段的大小和流行分布,提出了一種快速貪婪的方法解決這一NP難問題。參考文獻(xiàn)[13]引入博弈論,提出了一種解決服務(wù)器上視頻需求瞬間擁擠的遷移方法。但是,以上算法僅針對視頻需求,并未建立承載網(wǎng)構(gòu)建的一般模型。參考文獻(xiàn)[14]以底層節(jié)點和鏈路作為參與者,通過構(gòu)建合作博弈模型進行承載網(wǎng)映射。然而,算法將節(jié)點映射與鏈路映射相分離,分別進行博弈模型構(gòu)建,而后將兩個博弈進行嵌套,增加了算法復(fù)雜度。
基于此,本文提出了一種基于拍賣的周期映射承載網(wǎng)構(gòu)建算法。算法通過構(gòu)建合作博弈模型,最大化承載網(wǎng)整體構(gòu)建效益。通過周期映射,將時間周期內(nèi)的業(yè)務(wù)請求聚類,在最大化構(gòu)建收益和最小化構(gòu)建請求與建立的等待時間之間進行平衡。
構(gòu)建底層資源模型,將底層物理網(wǎng)絡(luò)抽象為無向圖Gs=(Ns,Ls,Cs),其中,Ns和Ls分別代表底層網(wǎng)絡(luò)中節(jié)點和鏈路的集合,Cs代表底層資源,即底層物理網(wǎng)絡(luò)所能提供的能力。底層資源通常包括節(jié)點資源和鏈路資源。其中,節(jié)點資源包括節(jié)點CPU和內(nèi)存容量,鏈路資源則主要指帶寬資源。同時,引入鏈路資源單位花費Clink和節(jié)點資源單位花費Cnode。
RSCN業(yè)務(wù)需求模型可表示為無向圖Gr=(Nr,Lr,Rr),其中,Nr和Lr分別表示RSCN中虛擬節(jié)點和虛擬鏈路的集合,分別是Ns和Ls的子集,RSCN構(gòu)建請求通常包含對底層物理節(jié)點和鏈路的約束,用Rr代表對虛擬節(jié)點和虛擬鏈路的需求,包括虛擬節(jié)點的計算資源需求和存儲資源需求,虛擬鏈路的帶寬資源需求及時延需求。
同時,業(yè)務(wù)需求中還包括每個業(yè)務(wù)構(gòu)建服務(wù)承載網(wǎng)的請求函數(shù),包括愿購買資源量、愿出價格及使用時間等。
RSCN構(gòu)建問題可以表述成滿足Gr中約束條件Rr的由Gr到Gs子集的一個映射,表示如下:
其中,Nv奐Ns,Lv奐Ls,Gv表示構(gòu)建RSCN的底層物理網(wǎng)絡(luò)的服務(wù)能力。RSCN構(gòu)建可以分割成節(jié)點映射和鏈路映射。
節(jié)點映射:
鏈路映射:
其中,RrN和RrL分別表示RSCN構(gòu)建中對虛擬節(jié)點和虛擬鏈路的限制條件,CvN和CvL分別代表構(gòu)建RSCN的底層資源情況,即底層物理節(jié)點和鏈路所能提供的服務(wù)承載能力。
(1)底層資源最大化利用
構(gòu)建服務(wù)承載網(wǎng)的初衷即在存在交集的多個物理資源上,提供具有不同服務(wù)能力的承載子網(wǎng),對于有限的底層網(wǎng)絡(luò),最大化底層資源利用,最大化總體構(gòu)建收益即服務(wù)承載網(wǎng)的構(gòu)建目標(biāo)。因此,定義承載網(wǎng)整體構(gòu)建收益如下:
(2)周期性映射
在服務(wù)承載網(wǎng)映射中,構(gòu)建請求通常不會按照某種特定規(guī)律的時間間隔到達(dá),本文算法提出周期映射的方式。將某一時間周期到達(dá)的服務(wù)承載網(wǎng)構(gòu)建請求聚類處理,而后針對不同業(yè)務(wù)類型進行映射,既減少了系統(tǒng)開銷,又最優(yōu)化了構(gòu)建收益。定義時間周期為T,則服務(wù)承載網(wǎng)構(gòu)建請求集合為Gr(T)。
對于每個提出服務(wù)承載網(wǎng)構(gòu)建請求的業(yè)務(wù),構(gòu)建的服務(wù)承載網(wǎng)為其分配相應(yīng)的底層資源,而其終極目標(biāo)即最大化系統(tǒng)總體效用,試圖使每個業(yè)務(wù)相互合作,形成合作博弈模型。這里假設(shè)業(yè)務(wù)都是按照自己的需求真實上報,并不存在謊報的情況。
(1)參與者
定義業(yè)務(wù)為博弈參與者,用N={1,2,3,…,n}表示。
(2)策略
構(gòu)建博弈的策略集合C={Bw,Dl,Cbm,CPcpu},其中,Bw表示鏈路帶寬,Dl表示時延需求,即業(yè)務(wù)提出的相應(yīng)的鏈路需求;節(jié)點需求分別由Cbm和CPcpu表示,Cbm為緩存容量(buffer memory capacity),CPcpu為CPU計算能力(CPU calculate power)。
(3)效用函數(shù)
效用函數(shù)定義為最大化服務(wù)承載網(wǎng)構(gòu)建整體收益,即由業(yè)務(wù)的支付總和減去滿足業(yè)務(wù)需求所構(gòu)建服務(wù)承載網(wǎng)的花費的“凈收入”,即:
那么,最大化整體收益問題可以表示為:
其中,式(7)表示構(gòu)建請求出價大于底層資源損耗;式(8)表示所選路徑時延小于構(gòu)建請求的時延需求;式(9)表示當(dāng)前承載的n個業(yè)務(wù)的虛擬節(jié)點消耗的緩存資源之和小于節(jié)點最大緩存容量;式(10)表示當(dāng)前承載的n個業(yè)務(wù)的虛擬節(jié)點消耗的CPU計算資源之和小于節(jié)點最大CPU計算能力;式(11)表示當(dāng)前承載的n個業(yè)務(wù)的虛擬鏈路消耗的帶寬資源之和小于鏈路的最大帶寬。
現(xiàn)有定價機制主要包括針對特定用戶、協(xié)商及拍賣等。針對特定用戶的定價,一是缺乏普適應(yīng),二是增加系統(tǒng)開銷;協(xié)商定價需要服務(wù)提供方與業(yè)務(wù)就價格反復(fù)商議,直到達(dá)成共識,其收斂時間較長,系統(tǒng)開銷大;而拍賣定價機制只需業(yè)務(wù)向服務(wù)提供方提出所需資源及支付意愿,服務(wù)提供方據(jù)此進行服務(wù)承載網(wǎng)構(gòu)建,分配底層資源并收費。當(dāng)然,其前提條件是提出構(gòu)建服務(wù)承載網(wǎng)需求的業(yè)務(wù)真實地表達(dá)了自身的業(yè)務(wù)需求。因此,本算法基于拍賣機制定價。
4.2.1 業(yè)務(wù)需求函數(shù)
所謂業(yè)務(wù)需求函數(shù)qn(Pn,tn),是在使用時間tn內(nèi),業(yè)務(wù)n愿意為所需資源qn支付的價格Pn。本文定義業(yè)務(wù)需求函數(shù)中的參數(shù)包括:愿出價格、購買資源量、資源使用時間,表示為
4.2.2 拍賣規(guī)則
假設(shè)在某一周期T,n個業(yè)務(wù)提出構(gòu)建服務(wù)承載網(wǎng)的請求,競爭總量為Q的底層資源,已知在不同的資源價格Pn下,業(yè)務(wù)n愿意購買資源qn。首先根據(jù)各業(yè)務(wù)的出價確定周期T內(nèi)的單位資源價格:
式(12)表示,在滿足n個業(yè)務(wù)構(gòu)建總需求不大于底層總資源量Q的情況下,將n個業(yè)務(wù)中單位資源價格的最大值作為周期T內(nèi)的單位資源價格,由此可得:
業(yè)務(wù)n可分得的資源qn(T)為:
業(yè)務(wù)n需為此支付的費用cn為:
4.2.3 拍賣規(guī)則性質(zhì)
當(dāng)業(yè)務(wù)的出價qn(Pn,tn)是真實的,由式(12)所得為市場出清價格,這將使資源配置達(dá)到最優(yōu),即當(dāng)所有參與者都已知業(yè)務(wù)數(shù)量n和資源總量Q時,且Q不變,則在拍賣結(jié)果中存在Nash均衡[15]。即若參與的某業(yè)務(wù)有意壓低報價,將導(dǎo)致服務(wù)承載網(wǎng)構(gòu)建的整體效益降低。
實際情況中,n和Q不可能成為所有業(yè)務(wù)的公共知識,對業(yè)務(wù)而言,n和Q是不確定的,這就迫使業(yè)務(wù)要真實的表達(dá)自身需求。同時,在網(wǎng)絡(luò)條件下,業(yè)務(wù)對底層網(wǎng)絡(luò)的信息優(yōu)勢受到抑制,這也促使業(yè)務(wù)要“講真話”。
4.2.4 拍賣中存在的問題
算法采用的拍賣機制是周期性的。在不同周期T,資源價格是變化的。然而對于跨越幾個計費周期的業(yè)務(wù)而言,按照各周期的資源價格進行收費顯然是不現(xiàn)實的,這將給業(yè)務(wù)造成超出預(yù)算的風(fēng)險和負(fù)擔(dān)。因此,算法規(guī)定,單位資源價格以業(yè)務(wù)加入網(wǎng)絡(luò)時為準(zhǔn),其生存時間內(nèi),不隨周期性的拍賣機制變化。但當(dāng)前生存周期結(jié)束,再次請求資源時,就需按當(dāng)時的單位資源繳費。
假設(shè)時間周期T內(nèi),到達(dá)了n個業(yè)務(wù)的服務(wù)承載網(wǎng)構(gòu)建請求,每個構(gòu)建請求提交信息分別包括使用時間tn、資源需求qn和愿付價格Pn。由拍賣機制確定業(yè)務(wù)需要為此支付的費用cn,并將其反饋給相應(yīng)業(yè)務(wù)。對于接受費用的業(yè)務(wù)請求構(gòu)建請求集合,進行服務(wù)承載網(wǎng)構(gòu)建。
在服務(wù)承載網(wǎng)映射中,首先將業(yè)務(wù)請求構(gòu)建為集合Qn,并按照業(yè)務(wù)類型將其聚類為Qi。收集底層網(wǎng)絡(luò)資源信息,計算得到滿足業(yè)務(wù)需求的所有可行路徑集合,將各條路徑代入式(5),得到最優(yōu)路徑及最優(yōu)帶寬,至此,將Qi映射到滿足其業(yè)務(wù)需求的底層網(wǎng)絡(luò),完成服務(wù)承載網(wǎng)構(gòu)建。算法流程如圖3所示。
圖3 基于拍賣博弈的可重構(gòu)服務(wù)承載網(wǎng)構(gòu)建流程
為評估算法的效能,本文將與基于簡單經(jīng)濟模型并協(xié)調(diào)節(jié)點與鏈路映射的ViNEYard[10]算法和以負(fù)載均衡為目標(biāo)的G-SP[8]算法進行性能比較。
仿真實驗中的基礎(chǔ)網(wǎng)絡(luò)拓?fù)溆葿RITE工具隨機產(chǎn)生的150個節(jié)點組成,節(jié)點連接率為0.5,節(jié)點與鏈路資源服從50~100的均勻分布。RSCN節(jié)點個數(shù)需求滿足2~10的均勻分布,鏈路帶寬需求、節(jié)點CPU能力及緩存容量均服從0~30的均勻分布,節(jié)點連接率為0.5。業(yè)務(wù)請求構(gòu)建RSCN的到達(dá)過程服從時間單位為100、強度為10的泊松過程;每個RSCN的生存時間服從期望值為1000的指數(shù)分布。映射周期為一個單位時間T。假設(shè)各業(yè)務(wù)構(gòu)建請求單位資源出價服從1~3的均勻分布,而底層節(jié)點單位花費和鏈路單位花費相等且均為1。并假設(shè)只要通過拍賣機制后的單位資源價格不高于該業(yè)務(wù)出價的兩倍,業(yè)務(wù)都可接受。為了仿真結(jié)果的準(zhǔn)確性,本文共進行仿真實驗20次,所取結(jié)果為所有實驗結(jié)果的平均值。
圖4 服務(wù)承載網(wǎng)構(gòu)建總收益
圖4 所示為10個周期T內(nèi),不同算法構(gòu)建服務(wù)承載網(wǎng)的總收益??梢钥闯?,DAGR算法較之其他算法,能帶來更多的收益。雖然G-SP算法以負(fù)載均衡為目標(biāo),但在進行服務(wù)承載網(wǎng)映射時,將節(jié)點映射與鏈路映射分兩階段處理,大大限制了方案空間,因此總收益比同時考慮節(jié)點和鏈路映射的ViNEYard算法略低。而基于拍賣機制的DAGR算法激發(fā)了各業(yè)務(wù)之間的競爭,比其他兩種算法相應(yīng)地得到了更高的構(gòu)建總收益。
定義1(RSCN構(gòu)建成功率)RSCN已構(gòu)建成功的請求個數(shù)與構(gòu)建請求總數(shù)之比,即:
式(15)中,Csuccess表 示RSCN成 功 構(gòu) 建 的 請 求 數(shù),Call表示構(gòu)建請求總數(shù)。如圖5所示為不同時間周期內(nèi)的服務(wù)承載網(wǎng)構(gòu)建成功率。由于ViNEYard算法進行承載網(wǎng)映射時,將節(jié)點映射和鏈路映射協(xié)調(diào)為一階段,因此,其構(gòu)建成功率比采用節(jié)點、鏈路分別映射的G-SP算法高。DAGR算法以構(gòu)建總收益為目標(biāo),存在定價時與業(yè)務(wù)的“雙向選擇”問題。實驗中設(shè)定,業(yè)務(wù)對于超過雙倍價于自己報價的定價,不予接受,基于此,在構(gòu)建初期,會有部分業(yè)務(wù)主動放棄構(gòu)建服務(wù)承載網(wǎng)的請求。因此,該算法的構(gòu)建成功率在某些周期相對ViNEYard算法較低,在75%左右。
圖5 服務(wù)承載網(wǎng)構(gòu)建成功率
針對不同業(yè)務(wù)對有限的底層網(wǎng)絡(luò)共享時存在的競爭問題,本文提出了一種基于拍賣博弈的服務(wù)承載網(wǎng)動態(tài)構(gòu)建算法。算法能夠根據(jù)業(yè)務(wù)需求建立服務(wù)承載網(wǎng),并實時感知業(yè)務(wù)變化,動態(tài)調(diào)整服務(wù)承載網(wǎng)的構(gòu)建,最終實現(xiàn)整體系統(tǒng)的利益最大化。
1 蘭巨龍,程東年,胡宇翔.可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究.通信學(xué)報,2014,35(1):128~139 Lan J L,Cheng D N,Hu Y X.Research on reconfigurable information communication basal network architecture.Journal on Communications,2014,35(1):128~139
2 中華人民共和國科學(xué)技術(shù)部.《可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究》項目計劃任務(wù)書,2011 Ministry of Science and Technology of the People’s Republic of China.Project Plan of Research on Reconfigurable Information Communication Basal Network Architecture,2011
3 Fischer A,Botero J F,Beck M T,et al.Virtual network embedding:a survey.IEEE Communications Surveys & Tutorials,2013,15(4):1888~1906
4 Gomes R L,Bittencourt L F,Madeira E R M.A bandwidth-feasibility algorithm for reliable virtual network allocation.Proceedings of IEEE 28th International Conference on Advanced Information Networking and Applications,Victoria,Australia,2014:504~511
5 Kareche S,Ductor S,Mezghiche M.A new robust heuristic for assigning substrate network resources to virtual networks.Proceedings of International Conference on Advanced Networking Distributed Systems and Applications,Bejaia,Algeria,2014:47~52
6 Chase J,Kaewpuang R,Wen Y G,et al.Joint virtual machine and bandwidth allocation in software defined network(SDN)and cloud computing environments.Proceedings of IEEE ICC,Sydney,Australia,2014:2969~2974
7 江逸茗,蘭巨龍,周慧琴.網(wǎng)絡(luò)虛擬化環(huán)境下的資源監(jiān)控策略.電子與信息學(xué)報,2014,36(3):708~714 Jiang Y M,Lan J L,Zhou H Q.Resource monitoring policy for network virtualization environment.Journal of Electronics &Information Technology,2014,36(3):708~714
8 Zhu Y,Ammar M.Algorithms for assigning substrate network resources to virtual network components.Proceedings of IEEE INFOCOM,Barcelona,Spain,2006:1~12
9 He J,Zhang S R,Li Y,et al.Davinci:dynamically adaptive virtual networks for a customized internet.Proceedings of ACM CoNEXT,Madrid,Spain,2008:1~12
10 Chowdhury N,Rahman M,Boutaba R.ViNEYard:virtual network embedding algorithms with coordinated node and link mapping.ACM/IEEE Transaction on Networking,2011,20(1):206~219
11 Guo J,Liu F M,Zeng D,et al.A cooperative game based allocation for sharing data center networks.Proceedings of IEEE INFOCOM,Turin,Italy,2013:2139~2147
12 He J,Zhao X M,Zhao B H.A fast,simple and near-optimal content placement scheme for a large-scale VoD system.Proceedings of 2012 IEEE International Conference on Communication Systems(ICCS),Singapore,2012:378~382
13 Feng Y,Li B.Bargaining towards maximized resource utilization in video streaming datacenters.Proceedings of IEEE INFOCOM,Orlando,2012:1134~1142
14 Soualah O,Fajjari I,Aitsaadi N,et al.A reliable virtual network embedding algorithm based on game theory within cloud’s backbone.Proceedings of IEEE International Conference on Communications(ICC),Sydney,Australia,2014:2975~2981
15 Back K,Zender J F.Auctions of divisible goods:on the rationale for the Treasury experiment.Review of Financial Studies,1993,30(3):733~764