摘 要：為了維護(hù)物理節(jié)點(diǎn)的負(fù)載均衡以提高資源的利用率，本文通過簡(jiǎn)單的裝箱問題探討了虛擬機(jī)與物理機(jī)的關(guān)系，在動(dòng)態(tài)資源分配的過程中，主要研究了Bin Packing系列算法，細(xì)化并實(shí)現(xiàn)了其中的四種算法BF，F(xiàn)F，WF，NF。改進(jìn)了BF，F(xiàn)F算法，通過Matlab對(duì)四種算法和改進(jìn)的BF，F(xiàn)F算法進(jìn)行了仿真和比較，驗(yàn)證了虛擬資源調(diào)度算法對(duì)負(fù)載均衡的積極意義。

關(guān)鍵詞：動(dòng)態(tài)資源調(diào)度算法；網(wǎng)絡(luò)虛擬化；資源分配；資源利用率；負(fù)載均衡

中圖分類號(hào)：TP393.01

Internet的出現(xiàn)使人們獲取和交換信息的方式變得便捷，隨著Internet的不斷發(fā)展已面臨巨大挑戰(zhàn)。當(dāng)前Internet的體系結(jié)構(gòu)存在許多缺點(diǎn)，由于Internet由多個(gè)運(yùn)營(yíng)商共同提供，使Internet體系結(jié)構(gòu)的變革難以實(shí)現(xiàn)，Internet的發(fā)展陷入僵局。網(wǎng)絡(luò)虛擬化[1]是多元化Internet體系結(jié)構(gòu)的組成部分，它支持來自不同服務(wù)提供者的異構(gòu)網(wǎng)絡(luò)體系結(jié)構(gòu)共存，并使得這些網(wǎng)絡(luò)體系結(jié)構(gòu)可以共享由多個(gè)基層設(shè)施提供者管理的物理底層。通過網(wǎng)絡(luò)虛擬化，Internet能夠有效克服僵化問題，網(wǎng)絡(luò)虛擬化使將來的Internet體系結(jié)構(gòu)多元化為一系列相互獨(dú)立的虛擬網(wǎng)絡(luò)，這些虛擬網(wǎng)絡(luò)共享基礎(chǔ)設(shè)施提供者的資源，并支持多種網(wǎng)絡(luò)體系結(jié)構(gòu)、實(shí)驗(yàn)和業(yè)務(wù)。

資源分配是網(wǎng)絡(luò)虛擬化中的一個(gè)基本問題，有效的資源分配能夠提高基礎(chǔ)設(shè)施提供者的物理資源利用率，并降低服務(wù)提供者租用資源所帶來的成本。因此，如何設(shè)計(jì)有效的資源分配算法成為關(guān)鍵和難點(diǎn)問題。

本文第2節(jié)對(duì)相關(guān)工作進(jìn)行討論；第3節(jié)分析和比較當(dāng)前比較主流的虛擬資源調(diào)度算法；第4節(jié)針對(duì)BinPacking系列算法進(jìn)行仿真分析，針對(duì)其缺陷加入優(yōu)化因子，提出改進(jìn)算法，用仿真進(jìn)行改進(jìn)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析；第5節(jié)對(duì)所研究的內(nèi)容進(jìn)行總結(jié)并展望未來研究方向。

1 虛擬資源調(diào)度算法

虛擬資源調(diào)度系統(tǒng)中核心組成部分就是調(diào)度算法。文獻(xiàn)[7]中提到調(diào)度算法根據(jù)針對(duì)的調(diào)度對(duì)象不同，分為服務(wù)器負(fù)載均衡算法，虛擬化系統(tǒng)動(dòng)態(tài)資源調(diào)度等。在本文中主要討論虛擬化系統(tǒng)中的負(fù)載均衡調(diào)度算法。對(duì)當(dāng)前一些常用的調(diào)度算法進(jìn)行分析，并比較其中各個(gè)算法的優(yōu)缺點(diǎn)和適用環(huán)境。

1.1 Greedy算法

貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪心決策的依據(jù)稱為貪心準(zhǔn)則（greedy criterion），也就是從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。

1.2 Bin Packing系列算法

裝箱問題在計(jì)算機(jī)領(lǐng)域中有廣泛的應(yīng)用，多任務(wù)調(diào)度，多處理器調(diào)度，內(nèi)存管理，Cache調(diào)度都是裝箱問題的實(shí)例。

裝箱問題數(shù)學(xué)形式表示為：給定n個(gè)物品，物品的大小為，每一個(gè)箱子的大小都為V，找到一個(gè)整數(shù)m和對(duì){l，2，…，n）的m個(gè)劃分P1 P2 … Pn使得對(duì)任意的j=l，…，m，均有優(yōu)化的目標(biāo)是使得m最小，即使用的箱子數(shù)目最少。在虛擬化動(dòng)態(tài)調(diào)度中，每一個(gè)箱子相當(dāng)于是具有一定資源容量的物理機(jī)，而每一個(gè)物品，則是虛擬機(jī)，通過設(shè)定特定的V（物理機(jī)負(fù)載峰值），使得整個(gè)系統(tǒng)的負(fù)載均衡。

裝箱問題（Bin Packing）是典型的NP-hard問題，有多種求解方法，可以采用近似算法或者優(yōu)化算法如遺傳算法，蟻群算法搜索解空間求解。最為直接的求解思路是使用貪婪策略，使用諸如First Fit，Best Fit，Worst Fit，Next Fit等。

（1）First Fit（FF）：對(duì)每一個(gè)要裝入的物品，從頭開始檢查當(dāng)前打開的箱子，找到第一個(gè)可以放入該物品的箱子，將物品放入；如果當(dāng)前打開的所有箱子中沒有一個(gè)能夠裝入該物品，則打開一個(gè)新箱子，將該物品放入。

（2）Next Fit（NF）。始終維持這一個(gè)當(dāng)前打開的箱子，對(duì)每一個(gè)要放入的物品，檢查該物品是否可以放入到當(dāng)前打開的箱子中，如果可以，則將該物品放入：否則打開一個(gè)空箱子，放入該物品，以該箱子作為當(dāng)前的箱子，并關(guān)閉上一個(gè)箱子。當(dāng)下一個(gè)物品到來時(shí)，持續(xù)此過程，直至所有的物品都放完為止。

（3）Best Fit（BF）。與首次適應(yīng)算法（FF）類似，唯一的區(qū)別是當(dāng)物品裝箱時(shí)，不是直接裝在第一個(gè)可裝入的箱子中，而是裝入在最適合該物體的箱子中（裝入后使得箱子最滿），如果沒有任意一個(gè)箱子可以放入該物品，則開啟空箱子。

（4）Worst Fit（WF）。與最優(yōu)適應(yīng)算法（BF）不同，當(dāng)物品裝箱時(shí)，不是裝在裝入物品后的箱子容積最滿的箱子中，而是裝入到最不適合該物體的箱子中（裝入后使得箱子的體積最空），如果沒有任意一個(gè)箱子可以放入該物品，則開啟空箱子。

1.3 Linear Programing算法

線性規(guī)劃是調(diào)配資源的一種應(yīng)用數(shù)學(xué)方法，在運(yùn)籌學(xué)中使用較多。它的基本思路就是在滿足一定的約束條件下，使預(yù)定的目標(biāo)達(dá)到最優(yōu)。當(dāng)每一次負(fù)載情況發(fā)生變化時(shí)，都需要建立并重新求解線性規(guī)劃，需要耗費(fèi)大量的計(jì)算時(shí)間。并需要對(duì)整個(gè)虛擬機(jī)和物理機(jī)的布局進(jìn)行全盤的重新分配，帶來大量的遷移開銷，因此，在虛擬化系統(tǒng)的動(dòng)態(tài)調(diào)度中主要用到調(diào)度資源初始化和虛擬機(jī)初始放置場(chǎng)景中。

1.4 Sand-Piper算法

Sand.Piper是Xen虛擬機(jī)用來檢測(cè)熱點(diǎn)物理機(jī)的檢測(cè)機(jī)制。它是通過將資源整合為一個(gè)維度，然后貪婪的選擇物理機(jī)，并決定將該物理機(jī)上的虛擬機(jī)放置到哪一臺(tái)物理機(jī)上來實(shí)現(xiàn)負(fù)載均衡和熱點(diǎn)解除。

2 實(shí)驗(yàn)仿真與結(jié)果分析

對(duì)以上幾種調(diào)度算法進(jìn)行對(duì)比和分析可以看出，貪心算法由于只考慮局部最優(yōu)，有可能的不到最優(yōu)解，在極端情況下，算法無法終止，甚至?xí)a(chǎn)生遷移振蕩。Bin packing算法中四種算：BF，F(xiàn)F，WF，NF各有優(yōu)缺點(diǎn)，不過整體來說，bin packing算法能通過簡(jiǎn)單的物品裝箱問題直觀的表示出資源調(diào)度的情況。Linear Programing算法通過線性規(guī)劃得到虛擬機(jī)在物理機(jī)上的調(diào)度情況，不過由于當(dāng)每一次負(fù)載情況發(fā)生變化時(shí)，都需要建立并重新求解線性規(guī)劃，耗費(fèi)了大量的計(jì)算時(shí)間。Sand-Piper算法算法核心思想就是利用Greedy的思想來進(jìn)行Worst Fit。但由于Sand-Piper算法直接將三個(gè)維度的資源合成一個(gè)維度，降維處理比較簡(jiǎn)單，并沒有綜合考慮虛擬機(jī)和物理機(jī)資源維度之間的互補(bǔ)關(guān)系，因此，實(shí)現(xiàn)起來效果不盡如人意。虛擬化系統(tǒng)中的虛擬機(jī)部署問題和調(diào)度問題可以看做是裝箱問題的變體，因此對(duì)網(wǎng)絡(luò)虛擬化中的資源調(diào)度問題，可以選擇BinPacking系列算法并進(jìn)行改進(jìn)。

2.1 四種算法的比較（FF，BF，WF，NF）

FF算法的優(yōu)點(diǎn)是實(shí)現(xiàn)起來簡(jiǎn)單，但缺點(diǎn)是當(dāng)物品從小到大放置時(shí)，結(jié)果可能會(huì)比較壞；NF算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，算法復(fù)雜度低，但是由于每一個(gè)物品放置時(shí)，只有當(dāng)前的箱子和空箱子可以選擇，效率低下，還會(huì)造成箱子的浪費(fèi)；BF優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，易于理解，但如果當(dāng)物品從小到大放置時(shí)，結(jié)果有可能極壞并且還有遍歷所有可以放入的箱子；WF優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，但是實(shí)現(xiàn)效果不是很好。

在這次仿真實(shí)驗(yàn)中，我們首先設(shè)置了幾項(xiàng)基礎(chǔ)參數(shù)如下：

根據(jù)仿真圖，X軸代表物品數(shù)目，也就是代表虛擬機(jī)的個(gè)數(shù)，Y軸代表需要使用的箱子數(shù)目，也就是代表有限的物理資源。從圖片中我們可以看出，當(dāng)物品數(shù)目在小于200時(shí)，BF FF NF WF四種算法所使用的箱子數(shù)目基本差不多。當(dāng)物品數(shù)目達(dá)到500左右時(shí)，WF和NF算法已經(jīng)產(chǎn)生了明顯的劣勢(shì)（即需要使用的箱子數(shù)目明顯增多，其中NF算法使用的箱子數(shù)目最多（即最差），WF其次。而BF和FF算法還沒有產(chǎn)生差距。當(dāng)物品數(shù)目達(dá)到1000時(shí)，BF和FF算法產(chǎn)生了交集，物品數(shù)目1000時(shí)，BF和FF算法所需要使用的箱子數(shù)目相同。不過物品數(shù)目在達(dá)到1000以后，BF和FF算法也并沒有產(chǎn)生太大的差距，BF算法稍占優(yōu)勢(shì)。

根據(jù)圖1，可得出結(jié)論：當(dāng)物品數(shù)目增多時(shí)，4種算法之間的優(yōu)劣性差距顯著提升，其中，算法性能從優(yōu)到劣分別是：BestFit，F(xiàn)irstFit，WorstFit，NextFit。

2.2 FirstFit和BestFit的改進(jìn)算法

從2.1中，我們看出BestFit和FirstFit算法具有較好的性能，那么能否將他們?cè)龠M(jìn)行改進(jìn)呢？于是我們?cè)陔x線的情況下，在FF和BF的基礎(chǔ)上提出加強(qiáng)的FFD和對(duì)BFD算法，以下是算法分析以及仿真實(shí)驗(yàn)比較。

First Fit Decreasing（FFD）：針對(duì)FF算法中物品可能升序出現(xiàn)，先對(duì)物品按降序排序，再按照FF算法進(jìn)行裝箱。但該算法是在知道所有物品信息的情況下才能對(duì)物品按照大小進(jìn)行排序，因此是一個(gè)離線（OffLine）模型。FFD的優(yōu)點(diǎn)是所得到的結(jié)果較為精確，缺點(diǎn)是只適用于離線模型，即要知道所有的物品大小，同時(shí)還要進(jìn)行排序操作，開銷較大。

可得出結(jié)論：當(dāng)物品增多時(shí)，F(xiàn)FD算法較FF算法的優(yōu)越性逐漸提升，F(xiàn)FD在某種程度上對(duì)FF進(jìn)行了性能上的提升。在物品數(shù)目200之前，F(xiàn)F和FFD算法沒有產(chǎn)生太大的差異，在物品數(shù)目在500左右時(shí)，F(xiàn)F和FFD算法產(chǎn)生了交集。當(dāng)物品數(shù)目達(dá)到1000時(shí)，F(xiàn)F和FFD算法產(chǎn)生了差距，F(xiàn)FD算法較FF算法產(chǎn)生了優(yōu)勢(shì)。在物品數(shù)目相同時(shí)，F(xiàn)FD算法需要使用的箱子數(shù)目更少。

Best Fit Decreasing（BFD）：針對(duì)BF算法中物品可能升序出現(xiàn)，先對(duì)物品按降序排序，再按照BF算法進(jìn)行裝箱。和FFD一樣，該算法也是要求知道所有物品的大小信息。

可得出結(jié)論：當(dāng)物品增多時(shí)，F(xiàn)FD算法較FF算法的優(yōu)越性逐漸提升，F(xiàn)FD在某種程度上對(duì)FF進(jìn)行了性能上的提升。在物品數(shù)目200之前，BF和BFD算法相同的物品數(shù)目所使用的箱子數(shù)目差不多。當(dāng)物品數(shù)目500時(shí)，BFD和BF算法有相同的作用，相同的物品數(shù)目所需要的箱子數(shù)目相同。在物品數(shù)目達(dá)到1000時(shí)，BFD比BF算法更好，不過兩種算法產(chǎn)生的函數(shù)圖趨于平穩(wěn)，沒有產(chǎn)生太大的差距。

2.3 BinPacking算法總結(jié)

本節(jié)主要圍繞網(wǎng)絡(luò)虛擬化中的動(dòng)態(tài)分配資源問題展開討論，提出了一種動(dòng)態(tài)資源分配的算法。該算法主要是通過動(dòng)態(tài)地遷移虛擬節(jié)點(diǎn)來實(shí)現(xiàn)負(fù)載在物理節(jié)點(diǎn)上的均衡分布，同時(shí)考慮了節(jié)點(diǎn)遷移對(duì)虛擬網(wǎng)絡(luò)性能和物理網(wǎng)絡(luò)負(fù)載分布的影響，并定義了綜合

影響因子來衡量節(jié)點(diǎn)遷移帶來的綜合影響。通過一定數(shù)量的物品所需要的箱子數(shù)目反應(yīng)出物理網(wǎng)絡(luò)負(fù)載情況。

3 結(jié)束語

資源分配是網(wǎng)絡(luò)虛擬化面臨的主要挑戰(zhàn)之一。有效的資源分配有利于物理絡(luò)的負(fù)載均衡，提高物理網(wǎng)絡(luò)資源的利用率，增加物理網(wǎng)絡(luò)承載虛擬網(wǎng)絡(luò)的數(shù)目，減少SPs的成本。本文研究了網(wǎng)絡(luò)虛擬化中的資源分配問題和當(dāng)前已有資源分配算法，進(jìn)行了詳細(xì)分析、比較和仿真。并對(duì)仿真結(jié)果進(jìn)行了理論分析。仿真結(jié)果表明，本文提出改進(jìn)的資源分配算法能夠更為有效地調(diào)整負(fù)載在物理節(jié)點(diǎn)上的分布，但是該算法只能平衡物理節(jié)點(diǎn)間的負(fù)載，不能對(duì)物理鏈路的負(fù)載進(jìn)行平衡，所以該算法在整個(gè)物理網(wǎng)絡(luò)的負(fù)載平衡方面具有一定的局限性。

參考文獻(xiàn)：

[1]N.M.M.K.Chowdhury，R.Boutaba.Network virtualization：state of the art and research challenges，IEEE Communications Magazine，2009：（47）：20–26.

[2]陳磊.一種啟發(fā)式網(wǎng)絡(luò)虛擬化資源分配算法[D].湖南大學(xué)信息與工程學(xué)院，2012（42）：22-40.

作者簡(jiǎn)介：彭紅姣（1975-），女，湖南祁東人，實(shí)驗(yàn)師，碩士，博士研究生，研究方向：網(wǎng)絡(luò)虛擬化、云計(jì)算、網(wǎng)絡(luò)與通信、計(jì)算機(jī)應(yīng)用。

作者單位：南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京 210023

基金項(xiàng)目：江蘇省高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：CXZZ13_0494）；江蘇省高校自然科學(xué)研究計(jì)劃資助項(xiàng)目（項(xiàng)目編號(hào)：12KJB520007）；江蘇省自然科學(xué)基金項(xiàng)目（項(xiàng)目編號(hào)：No.BK2011754）。