高先明張曉哲 王寶生 盧澤新 馬世聰

(國防科學技術大學計算機學院 長沙 410073)

面向虛擬路由器的基于歷史轉發(fā)開銷的資源調(diào)度算法

高先明*張曉哲 王寶生 盧澤新 馬世聰

(國防科學技術大學計算機學院 長沙 410073)

通過研究以Xen為代表的虛擬工具中資源調(diào)度算法，得知它們無法保證虛擬路由器中資源共享的公平性。該文提出一種基于歷史轉發(fā)開銷的資源調(diào)度算法，用來確保路由器實例占用資源的公平性，尤其物理平臺的輸入/輸出(I/O)資源。該算法通過統(tǒng)計路由器實例最近的報文轉發(fā)開銷來計算出路由器實例調(diào)度的優(yōu)先級，確保平均吞吐量較低的路由器實例獲得被調(diào)度的機會。同時，該算法通過設置優(yōu)先級計算公式中處理延遲的值，達到對延遲敏感強的路由器實例的支持，以及通過預測報文處理時間決定待處理報文是否丟棄，避免不必要的系統(tǒng)開銷。通過實驗測試，相對于Credit算法，該文算法在確保虛擬路由器資源共享的公平性方面存在明顯優(yōu)勢，并且能為延遲敏感的路由器實例提供支持。

網(wǎng)絡虛擬化；虛擬路由器；路由器實例；資源調(diào)度算法；公平性

1 引言

在過去的幾十年里，因特網(wǎng)已成為支撐社會經(jīng)濟發(fā)展和科技創(chuàng)新的重要信息基礎設施，并深刻地影響著當代人們生活與學習方式，比如電子商務、遠程教育等[1]。當傳統(tǒng)網(wǎng)絡面臨來自安全性、移動性和服務質(zhì)量等方面的技術挑戰(zhàn)時[2]，通常采用“打補丁”的方式來解決所遇到的難題，而不是采用自上而下地設計與部署全新的網(wǎng)絡體系架構。正是這種行為并不能有效地解決互聯(lián)網(wǎng)自身固有的問題，并嚴重阻礙了創(chuàng)新型網(wǎng)絡體系架構的部署[3]。為了破解當前互聯(lián)網(wǎng)所面臨的困境，研究機構在借鑒系統(tǒng)虛擬化技術思想的基礎上，提出了將虛擬化技術應用到傳統(tǒng)網(wǎng)絡架構的思想，并逐漸形成和完善了網(wǎng)絡虛擬化技術[4]。而路由器虛擬化技術直接關系到網(wǎng)絡虛擬化技術的部署，它的轉發(fā)性能還影響到網(wǎng)絡虛擬化技術的應用與推廣。因此，學術界和工業(yè)界對虛擬路由器模型以及優(yōu)化機制展開深入地研究[5]。

目前，虛擬路由器研究方向聚焦在軟件路由器方面，即采用系統(tǒng)虛擬化技術實現(xiàn)虛擬路由器[6,7]。如何保證虛擬路由器中資源共享的公平性是其成功部署的前提。研究人員嘗試利用系統(tǒng)虛擬化技術中現(xiàn)有的資源調(diào)度算法來保證虛擬路由器資源共享的公平性，比如文獻[8]中BVT(Borrowed Virtual Time)算法[9]、Credit算法[10]、SEDF (Simple Earliest Deadline First)算法[11]以及優(yōu)化算法[12-14]。然而，這些資源調(diào)度算法設計的初衷是解決桌面系統(tǒng)和服務器中CPU公平性問題，而非輸入/輸出(I/O)資源的公平性。在虛擬路由器中報文轉發(fā)過程主要涉及到的報文存儲/讀取、報文頭部校驗與修改以及轉發(fā)表查找等，這些操作都是與I/O有關的。這使得虛擬路由器更多地開銷花費在I/O資源上。另外，某些路由器實例的部署不僅要求物理資源得到保障，而且對處理延遲有著嚴格要求。因此，利用系統(tǒng)虛擬化技術中資源調(diào)度算法是無法滿足虛擬路由器中資源共享公平性的需求。

因此，本文提出了一種基于歷史轉發(fā)開銷的資源調(diào)度算法(Historical Forwarding Overhead Based the Resource Scheduling Algorithm, HFOB_ RSA)來解決虛擬路由器在物理平臺的資源調(diào)度方面所面臨的難題。該算法通過統(tǒng)計每個路由器實例最近α次報文轉發(fā)開銷，計算出路由器實例調(diào)度的優(yōu)先級，確定路由器實例被調(diào)度的次序，從而保證虛擬路由器資源共享的公平性。另外，該算法能預測報文處理時間，通過與路由器實例中預設的處理時延對比，預先決定報文處理方式(比如處理、丟棄等)，從而降低無效報文引入的額外轉發(fā)開銷。最后，通過重配置優(yōu)先級計算公式中處理延遲的值，從而達到了對延遲敏感強的路由器實例的支持。通過實驗證明：HFOB_RSA能有效地保證虛擬路由器資源共享的公平性。同時，該算法能夠根據(jù)路由器實例的延遲敏感度來降低報文的等待時間，為延遲敏感的路由器實例提供支持。

2 基本思想

HFOB_RSA能依據(jù)路由器實例的報文轉發(fā)歷史開銷數(shù)據(jù)計算出實例調(diào)度優(yōu)先級，并根據(jù)優(yōu)先級向路由器實例推數(shù)據(jù)包。通過控制路由器實例的調(diào)度次序來確保虛擬路由器資源共享的公平性。本節(jié)著重介紹虛擬路由器中資源調(diào)度模型以及HFOB_ RSA的基本思想。

2.1 資源調(diào)度模型

在虛擬路由器模型中，若干個路由器實例運行在同一物理平臺，并且它們相互獨立、互不干擾。路由器實例作為報文處理的應用，通常位于虛擬路由器模型的頂層。它首先從下層讀取報文，根據(jù)自定報文處理方式來處理報文，最后將報文下發(fā)至下層。為了有效地保證資源共享的公平性，虛擬路由器常常采用資源調(diào)度算法控制路由器實例讀取報文的次序，是由虛擬路由器資源調(diào)度模型決定的。

在虛擬路由器資源調(diào)度模型中，報文調(diào)度模塊負責將入隊列中報文發(fā)送到對應的路由器實例，并將路由器實例已處理完畢的報文讀取到出隊列中。報文流在報文調(diào)度模塊與路由器實例間的動作分為推操作和拉操作：推操作是指路由器實例被動地等待報文調(diào)度模塊正在處理的數(shù)據(jù)包；拉操作是指報文調(diào)度模塊主動地向路由器實例請求已處理完畢的報文，如圖1所示。

圖1 虛擬路由器資源調(diào)度模型

虛擬路由器資源調(diào)度模型如何控制路由器實例調(diào)度的順序？由于報文調(diào)度模塊與路由器實例間的連接方式，路由器實例在沒有接收到來自報文調(diào)度模塊的數(shù)據(jù)包時，只能處于等待狀態(tài)，直至報文調(diào)度模塊從入隊列推數(shù)據(jù)包到它。因此，報文調(diào)度模塊可以通過推報文次序來控制路由器實例調(diào)度的次序，優(yōu)先向優(yōu)先級最高的路由器實例推數(shù)據(jù)包。

2.2 基本思想

虛擬路由器資源調(diào)度模型關鍵在于路由器實例優(yōu)先級的計算。只有優(yōu)先級最高的路由器實例才會得到報文調(diào)度模塊上推的數(shù)據(jù)包，其他路由器實例則處于等待狀態(tài)，直至其優(yōu)先級變?yōu)樽罡摺＿@使得資源調(diào)度算法中優(yōu)先級的計算優(yōu)劣直接影響到虛擬路由器資源共享的公平性。

優(yōu)先級的計算涉及到多方面的因素：僅考慮一個因素，可能導致優(yōu)先級存在偏差，無法正確反映出路由器實例對資源使用的實際狀況；而某些因素可以忽略不計，考慮這些因素會增加優(yōu)先級的復雜性，不能清晰地反映出優(yōu)先級的主要因子。因此，合理地考慮影響因素是得出優(yōu)先級計算公式的第一步。

優(yōu)先級不僅要考慮路由器實例占用帶寬資源的權值，而且要考慮入隊列中報文等待處理時間。因為報文在入隊列中等待時間越久，報文被丟棄的幾率就越大。因此，報文等待時間越久，對應的路由器實例優(yōu)先級就應該越高，以避免報文由于長時間等待超時而被丟棄。同時，除了考慮以上兩種因素之外，優(yōu)先級還須將路由器實例最近α次的報文轉發(fā)開銷計算在內(nèi)。因為報文的長度、查表的次數(shù)、緩存(cache)的命中等都影響到路由器實例的處理開銷，如果不考慮路由器實例以往的開銷，就可能造成虛擬路由器中路由器實例占用共享資源的不公平，無法保證資源使用率較低的路由器實例優(yōu)先得到調(diào)度。此外，優(yōu)先級還需要利用處理延遲來反映路由器實例的延遲敏感度。最后，在入隊列中報文由于等待時間過程可能導致其被丟棄，需要在報文尚未處理前通過預測報文處理時間來決定該報文是否被丟棄。

3 核心算法及特征

HFOB_RSA中，路由器實例調(diào)度的順序是由它們優(yōu)先級決定的。路由器實例優(yōu)先級最高，那么它就會被優(yōu)先調(diào)度。本節(jié)著重探討了HFOB_RSA中優(yōu)先級公式、衡量算法性能的偏差量、算法的描述以及算法的可行性和時空復雜度分析。

3.1 優(yōu)先級的計算公式

優(yōu)先級用來表示虛擬路由器中路由器實例調(diào)度的次序。路由器實例優(yōu)先級的大小直接決定它從報文調(diào)度模塊獲取報文的次序。同時，優(yōu)先級計算的前提條件能夠有效地避免由不期望的報文處理引入的額外系統(tǒng)開銷。優(yōu)先級計算公式如式(1)所示。

式中Pi表示第i路由器實例調(diào)度的優(yōu)先級；λi表示第i路由器實例帶寬的權值；Di[n]為等待因子，表示第i路由器實例對應的報文等待處理的時間；Ti表示第i路由器實例容忍的最大處理時延；Rmax表示第i路由器實例的最大吞吐量；為歷史因子，表示第i路由器實例最近α條報文轉發(fā)開銷的均值；為預測處理時間，表示第i路由器實例下一報文預測處理時間，L表示報文的長度。

從式(1)可以看出：當路由器實例對應的報文等待處理時間與預測處理時間之和不超過該路由器實例容忍的最大處理時延時，優(yōu)先級公式才會被調(diào)用。路由器實例調(diào)度的優(yōu)先級不僅與它分配帶寬的權值和報文的等待處理時間呈正比，而且與它設置的最大容忍延遲、最大吞吐量以及它最近α條報文轉發(fā)開銷的均值呈反比。其中，優(yōu)先級與帶寬iλ呈正相關，帶寬的權值越大，那么路由器實例的調(diào)度優(yōu)先級就越高。Di[n]是表示入隊列中報文等待時間，Di[n]越大，對應的路由器實例就越容易被調(diào)度。同時，入隊列中報文的等待時間Di[n]加上預測處理時間超過Ti門限時就會被丟棄，從而避免不期望的處理開銷。Ti值表示路由器實例容忍的最大處理延遲，Ti越大，路由器實例對延遲敏感度越低，調(diào)度優(yōu)先級也就越小。Rmax反映了路由器實例處理報文的能力：處理報文能力越強，它支持的最大吞吐量就越高?？紤]到路由器實例間調(diào)度公平性，反映路由器實例最近的轉發(fā)開銷，與優(yōu)先級呈反比，越大，那么其優(yōu)先級就越低，從而確保平均吞吐量小的路由器實例也有機會獲得調(diào)度。

其中，ti[n]表示第i路由器實例最近第n次轉發(fā)開銷。α值表示路由器最近報文轉發(fā)開銷的次數(shù)，是歷史因子的閾值。α值直接影響到歷史因子的表現(xiàn)：閾值α過大，歷史因子無法準確地反映出路由器實例當前時間段的平均吞吐量，尤其報文流波動明顯時；如果閾值α過小，歷史因子僅能反映最近時間段內(nèi)路由器實例狀況，無法有效地保證資源共享的公平性。

(2)前提條件 優(yōu)先級計算的前提條件能在報文尚未處理前決定報文行為(包括處理或丟棄)。具體來講，通過判斷預測報文處理時間和報文等待時間之和是否超過路由器實例預設處理時延：如果沒有超過，則計算路由器實例優(yōu)先級；否則直接丟棄該報文，避免該報文引入的不必要的開銷。前提條件中，Di[n]表示報文的等待處理時間，iT表示路由器實例預設的處理時延，是已知的。前提條件判斷待處理報文是否超時取決于與歷史因子和報文長度L兩個參數(shù)相關。表示預測的報文處理時間，其計算公式為

3.2 偏差量

偏差量是指虛擬路由器中路由器實例實際占用的共享資源與理論占用的共享資源的均方差，用于衡量資源調(diào)度算法的公平性，偏差量計算公式為

式中?表示資源調(diào)度算法的偏差量；Treal(i)表示路由器實例i實際的處理報文開銷；Ttheory(i)表示路由器實例i理論的處理時間。從式(4)可以看出：偏差量?的大小取決于路由器實例占用共享資源的公平性。如果偏差量0?→，表示該資源算法能夠完全保證共享資源的公平性。如果偏差量?越大，表示該資源調(diào)度算法在保證共享資源公平性方面表現(xiàn)就越差。因此，可以利用偏差量?來評估閾值α對HFOB_RSA性能的影響，從而決定閾值α的取值范圍。當偏差量超過某個設定值，可以通過增加閾值α來保證虛擬路由器中資源公平性。

3.3 算法具體描述

HFOB_RSA中歷史因子反映當前路由器實例的平均處理能力，并盡可能地保證各個路由器實例占用資源的公平性。相對于其他資源調(diào)度算法，它能根據(jù)路由器實例歷史轉發(fā)開銷，確保那些平均吞吐量低的路由器實例更易獲取被調(diào)度的機會，從而保證虛擬路由器資源共享的公平性。HFOB_RSA通過優(yōu)先級決定路由器實例調(diào)度的次序，并能預判待處理報文處理方式。算法的具體描述如表1所示。

表1 算法的具體描述

通過HFOB_RSA描述可知：只有入隊列存在報文時才觸發(fā)該調(diào)度算法，否則，報文調(diào)度模塊一直處于空轉狀態(tài)。在該資源調(diào)度算法中，首先利用前提條件預測待處理報文是否超時，如果存在超時情況，則讀取入隊列中下一條報文；否則計算出路由器實例的歷史因子和調(diào)度優(yōu)先級。最后，比較出優(yōu)先級最高的路由器實例，并將報文上推到該路由器實例中。HFOB_RSA與其他調(diào)度算法最大差別在于前者通過統(tǒng)計路由器實例的歷史轉發(fā)開銷來更加精確地確定路由器實例調(diào)度次序，從而確保虛擬路由器資源共享的公平性。

4 實驗與分析

本小節(jié)主要利用實驗來測量HFOB_RSA和Credit算法的性能，驗證HFOB_RSA在保證資源公平性方面和支持延遲敏感服務方面具有優(yōu)勢。

4.1 實驗環(huán)境

本實驗拓撲包括一臺客戶端和一臺部署虛擬路由器的服務器，客戶端采用lenovo ThinkCentre，具有雙核的2.70 GHz奔騰處理器，4 G內(nèi)存，和2個1 Gbps接口，虛擬路由器部署在lenovo Think Centre，具有雙核的2.13 GHz Xeon處理器，4 G內(nèi)存，和2個1 Gbps接口，如圖2所示。客戶端采用Lan Traffic[15]發(fā)送報文長度不同的用戶數(shù)據(jù)報協(xié)議(User Datagram Protocol, UDP)報文，比如64 byte、128 byte等長度。同時，客戶端建立UDP服務器，用于監(jiān)聽虛擬路由器轉發(fā)的UDP報文，并記錄數(shù)據(jù)包的相關信息(包括報文ID號、報文長度、報文發(fā)送時間戳和報文接收時間戳)。虛擬路由器采用類似Click軟件路由器實現(xiàn)。在虛擬路由器中，每個路由器實例對應于一個類似Click軟件路由器實例。在本實驗中，類似Click軟件路由器實例處理IPv4協(xié)議報文，實現(xiàn)報文從一個端口接收和另一端口發(fā)送。

本文實驗有3個目標：(1)探討α值對HFOB_ RSA性能的影響；(2)探討報文長度對HFOB_ RSA與Credit算法的影響；(3)驗證HFOB_RSA支持延遲敏感的路由器實例。

4.2 前提條件中k值的測量

圖2 實驗環(huán)境中網(wǎng)絡拓撲結構

前提條件中k值是與物理平臺的處理能力和報文長度有關的，是未知量。為了求出該變量的取值范圍，本實驗測試了虛擬路由器在該平臺上處理不同長度報文(包括64 byte, 128 byte, 256 byte, 512 byte, 768 byte, 1024 byte, 1500 byte)時，單條報文的處理時間，如圖3所示。

圖3 不同報文長度時的處理時間

從圖3可以看出，隨著報文長度的增加，其報文的處理時間也相應地增加。報文的處理時間與它的長度存在一定的相關性。由式(3)的定義可知：可以表示下一報文的處理時間，那么進一步推導出k值的計算公式為

Ti[len]表示該長度報文的處理時間；Ti[Blen]表示基長度報文的處理時間，本實驗是以64 byte報文作為參照值。利用式(5)和圖3的實驗數(shù)據(jù)，計算出k的取值范圍為區(qū)間[0.000716, 0.001106]。如果k值取值過小，會使報文的預測處理時間小于實際處理時間，可能導致部分不滿足前提條件的報文而實際被路由器實例處理，從而引入額外的系統(tǒng)開銷。因此，實驗中k值設定為該區(qū)間的上限，即0.001106。

4.3 α對HFOB_RSA性能的影響

虛擬路由器部署3臺路由器實例：路由器實例1、路由器實例2和路由器實例3。它們的處理能力分別為轉發(fā)64 byte報文的速率是150 Mbps, 150 Mbps和300 Mbps。同時，配置3臺路由器實例的報文長度比值為1:2:2，帶寬比值為1:1:2，并設置HFOB_RSA中α值為1, 10, 20, 30, 40, 50。當整個虛擬路由器處理報文數(shù)目為1000時，通過利用式(5)來計算出HFOB_RSA的偏差量，以及統(tǒng)計出3個路由器實例處理的報文數(shù)目，如表2所示。

從表2中看出，在6種不同場景，路由器實例的處理報文數(shù)目存在差異。當偏差量值小于0.02795時，路由器實例處理的報文數(shù)目不再發(fā)生改變。隨著偏差量逐漸減少，路由器實例處理報文數(shù)目趨于恒定，這說明HFOB_RSA在保證資源公平性方面表現(xiàn)也越來越好。實驗中，偏差量為0.02795時，HFOB_RSA算法在保證資源公平性方面已經(jīng)滿足于本文的需求(在本實驗中30α=)。

表2 HFOB_RSA的偏差量及路由器實例處理的報文數(shù)

4.4 報文長度的差異

在虛擬路由器中部署了兩個路由器實例：路由器實例A和路由器實例B。它們兩者的處理能力相同，為轉發(fā)128 byte報文的速率為300 Mbps。同時，配置路由器實例A轉發(fā)的報文長度分別為64 byte、128 byte和256 byte，路由器實例B的轉發(fā)報文長度為128 byte。通過測量兩臺路由器實例在實際運行過程中占用的共享資源來探討報文長度對Credit算法和HFOB_RSA性能的影響，如圖4所示(橫軸表示時間，縱軸表示路由器實例A與路由器實例B占用共享資源的比值)。

通過分析圖4可以發(fā)現(xiàn)：當路由器實例A轉發(fā)的報文長度為64 byte時，Credit算法中路由器實例A占用的共享資源幾乎是路由器實例B的兩倍，HFOB_RSA使路由器實例A與路由器實例B占用共享資源的比值在1.2左右；在路由器實例轉發(fā)128 byte報文時，兩種算法的表現(xiàn)基本一致；當路由器實例A轉發(fā)256 byte報文時，Credit算法中路由器實例A占用的資源僅為路由器實例B的大約65%，而HFOB_RSA則能將路由器實例A與路由器實例B占用共享資源的比值提高到80%。

4.5 延遲敏感度的差異

虛擬路由器部署兩臺路由器實例：路由器實例C和路由器實例D。它們的處理能力相同，轉發(fā)的報文長度相同，為轉發(fā)64 byte報文的速率是300 Mbps。同時，配置路由器實例C的延遲敏感度為1，路由器實例D的延遲敏感度為2(即式(1)中iT值為1:2)，使得路由器實例D的延遲敏感程度要強于路由器實例C。統(tǒng)計兩臺路由器實例中報文等待時間的均值，如圖5所示(橫軸表示時間，縱軸表示報文等待時間)

圖4 兩臺路由器實例的占用資源比值

圖5 路由器實例中報文等待時間

從圖5中可以清晰地看出：由于路由器實例C的報文優(yōu)先于路由器實例D的報文到達，Credit算法依據(jù)先來先處理的原則，優(yōu)先處理路由器實例C的報文，所以導致路由器實例D中報文等待時間是路由器C的4倍。而HFOB_RSA能夠根據(jù)延遲敏感的需求，優(yōu)先調(diào)度延遲敏感度高的路由器實例D，這樣使得路由器實例D中報文等待時間明顯低于路由器實例C中報文等待時間。

5 結束語

由于虛擬路由器支持多個路由器實例并行運行在同一物理平臺，這使得多個路由器實例同時訪問物理資源時，就會產(chǎn)生資源競爭的問題。如何保證虛擬路由器中資源共享的公平性是當前迫切需要解決的問題。本文針對現(xiàn)有的資源調(diào)度算法存在的不足，提出了一種HFOB_RSA。該算法能利用路由器實例最近α次的轉發(fā)開銷來確定它們的調(diào)度次序，從而確保共享資源的公平性。通過實驗分析，相比較Credit算法，HFOB_RSA在保證資源公平性方面具有明顯的優(yōu)勢。同時，HFOB_RSA可以為延遲敏感高的路由器實例提供支持。

然而，HFOB_RSA也存在一些問題：(1)α值取值多少才能滿足需求，過大就會引入較多的系統(tǒng)開銷，從而降低虛擬路由器的整體性能，較少則無法保證資源的公平性；(2)從圖4可以看出HFOB_ RSA并不能嚴格地保證資源的公平性，只是相對其他資源調(diào)度算法而言，能較好地保證資源公平性。

[1] Anderson T, Peterson L, Shenker S, et al.. Overcoming the Internet impasse through virtualization[J]. Computer, 2005, 38(4): 34-41.

[2] Clark D, Braden R, Sollins K, et al.. New arch: future generation internet architecture[R]. Massachusetts Institute of Technology Cambridge Lab for Computer Science, Massachusetts, USA, 2004.

[3] Turner J S and Taylor D E. Diversifying the internet[C]. Proceedings of the Global Telecommunications Conference, Saint Louis, USA, 2005, 2: 755-760.

[4] Guimaraes P H V, Ferraz L H G, Torres J V, et al.. Experimenting content-centric networks in the future internet testbed environment[C]. Proceedings of the 2013 IEEE International Conference on Communications Workshops, Budapest, Hungary, 2013: 1383-1387.

[5] Wang A, Iyer M, Dutta R, et al.. Network virtualization: technologies, perspectives, and frontiers[J]. Journal of Lightwave Technology, 2013, 31(4): 523-537.

[6] Fischer A, Berl A, and de Meer H. Virtualized networks based on system virtualization[C]. Proceedings of the 2nd GI/ITG KuVS Workshop on The Future Internet, Munich, Germany, 2008: 44-47.

[7] Ahn C, Lee S H, and Yoo C. Performance analysing for virtual router on xen hypervisor[C]. Proceedings of the 8th International Symposium on Embedded Technology, Daegu, Korea, 2013: 1-2.

[8] Bourguiba M, Haddadou K, and Pujolle G. Evaluating and enhancing xen-based virtual routers to support real-time applications[C]. Proceedings of the Consumer Communications and Networking Conference (CCNC), Nevada, USA, 2010: 1-5.

[9] Duda K J and Cheriton D R. Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a generalpurpose scheduler[C]. Proceedings of the ACM SIGOPS Operating Systems Review, New York, USA, 1999: 261-276.

[10] Kim N, Cho J, and Seo E. Energy-credit scheduler: an energy-aware virtual machine scheduler for cloud systems[J]. Future Generation Computer Systems, 2014, 32: 128-137.

[11] Gu Z and Zhao Q. A state-of-the-art survey on real-time issues in embedded systems virtualization[J]. Journal of Software Engineering & Applications, 2012, 5(4): 277-290.

[12] Gulati A, Merchant A, and Varman P J. mClock: handling throughput variability for hypervisor IO scheduling[C]. Proceedings of the 9th USENIX conference on Operating systems design and implementation, British Columbia, Canada, 2010: 1-7.

[13] Liao G, Guo D, Bhuyan L, et al.. Software techniques to improve virtualized I/O performance on multi-core systems [C]. Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, San Jose, USA, 2008: 161-170.

[14] Ongaro D, Cox A L, and Rixner S. Scheduling I/O in virtual machine monitors[C]. Proceedings of the fourth ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, Seattle, USA, 2008: 1-10.

[15] Packet Data Systems Ltd. Lan Traffic[OL]. http://www. pds-test.co.uk/products/ip_generation.html, 2014.4.

高先明： 男，1988年生，博士，研究方向為新型網(wǎng)絡體系結構、網(wǎng)絡虛擬化技術.

張曉哲： 男，1976年生，碩士生導師，副研究員，研究方向為新型網(wǎng)絡體系結構、路由器體系架構.

王寶生： 男，1970年生，博士生導師，研究員，研究方向為計算機網(wǎng)絡與通信、網(wǎng)絡安全.

盧澤新： 男，1964年生，碩士生導師，研究員，研究方向為計算機網(wǎng)絡與通信、網(wǎng)絡安全.

馬世聰： 男，1986年生，博士，研究方向為新型網(wǎng)絡體系結構、網(wǎng)絡虛擬化技術.

Historical Forwarding Overhead Based the Resource Scheduling Algorithm for the Virtual Router

Gao Xian-ming Zhang Xiao-zhe Wang Bao-sheng Lu Ze-xin Ma Shi-cong
(School of Computer, National University of Defense Technology, Changsha 410073, China)

The current resource scheduling algorithms can not offer promise for the fairness of shared resources based on research on the resource scheduling algorithms in the system virtualization tools represented by Xen. This paper proposes a Historical Forwarding Overhead Based the Resource Scheduling Algorithm (HFOB_RSA) to ensure that router instances occupy determinate physical resources including I/Os that should be proportional to actual requirements. This algorithm can determine the scheduling priority of router instances by calculating the last several forwarding overhead of each router instance to make those router instances with low real throughput have an opportunity for being scheduled. Meanwhile, this algorithm also sets the value of processing delay in priority formula to provide support for those delay-sensitive router instances and determines whether or not to discard the non-disposed packets in advance by forecasting their processing time to avoid the unwanted overhead. The experimental results prove that the HFOB_RSA has superiority over Credit algorithm in terms of the fairness of shared resources in the virtual router. And HFOB_RSA also is able to provide support for the delay-sensitive router instances.

Network virtualization; Virtual router; Router instance; Resource scheduling algorithm; Fairness

TP393.4

A

1009-5896(2015)03-0686-07

10.11999/JEIT140491

2014-04-15收到，2014-07-31改回

國家973計劃項目(2012CB315906)和高等學校博士學科點專項科研基金(20114307110006)資助課題

*通信作者：高先明 gxm9000@163.com