流媒體系統(tǒng)中基于請求遷移的任務(wù)調(diào)度算法

李 軍，倪 宏，王玲芳，陳 君

(1.中國科學(xué)院聲學(xué)研究所 國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京100190;2.中國科學(xué)院大學(xué)，北京100190)

0 引 言

流媒體服務(wù)將傳統(tǒng)媒體內(nèi)容網(wǎng)絡(luò)化、數(shù)字化并以用戶點播的方式向其提供服務(wù)。流媒體系統(tǒng)架構(gòu)一般包括中央調(diào)度系統(tǒng)、多個媒體服務(wù)器等模塊。調(diào)度模塊負責整個流媒體系統(tǒng)的任務(wù)調(diào)度和管理、用戶交互操作管理以及維護系統(tǒng)當前服務(wù)狀態(tài)，包括用戶請求參數(shù)、視頻內(nèi)容分布、點播統(tǒng)計信息、點播會話等。媒體服務(wù)器主要接收調(diào)度模塊的命令，從本地存儲或緩存中讀取內(nèi)容向用戶提供服務(wù)。媒體服務(wù)器一般帶有存儲，由于多媒體內(nèi)容體積較大，普通服務(wù)器存儲容量有限，每個媒體服務(wù)器的服務(wù)能力有限。同時，經(jīng)統(tǒng)計發(fā)現(xiàn)用戶對流媒體內(nèi)容的訪問服從一定的規(guī)律，80%的用戶訪問20%的流媒體對象［1-2］，也就是說流媒體內(nèi)容存在不同的流行度分布。對于熱門內(nèi)容可采取多副本放置的方法通過多臺服務(wù)器同時向用戶提供服務(wù)，以提高用戶并發(fā)數(shù)量。由于各個媒體服務(wù)節(jié)點上內(nèi)容分布不一致和影片流行度的傾斜性，導(dǎo)致節(jié)點之間的負載內(nèi)容不均勻分布，節(jié)點之間的帶寬資源和磁盤I/O 資源沒有充分利用，系統(tǒng)的服務(wù)質(zhì)量達不到最優(yōu)化。同時，流媒體服務(wù)系統(tǒng)需要不間斷地向用戶提供服務(wù)，但服務(wù)器出現(xiàn)故障不可避免，因此，當某個媒體服務(wù)器出現(xiàn)故障時，其上正在服務(wù)中的請求需要快速遷移到其他服務(wù)器上，以保障用戶媒體流不中斷。

媒體服務(wù)器相互存儲內(nèi)容副本，通過請求到達時基于負載均衡的實時任務(wù)調(diào)度達到系統(tǒng)負載均衡。傳統(tǒng)的遷移算法只在新到達的請求被阻塞時才進行請求遷移，這種策略稱為最后一分鐘請求遷移(Last-minute request migration)［3］。這種傳統(tǒng)的遷移算法有兩個問題:一是當遷移發(fā)生時系統(tǒng)負載已經(jīng)嚴重不平衡，導(dǎo)致VoD 系統(tǒng)性能下降;二是由于較高的不均衡內(nèi)容請求到達導(dǎo)致一些視頻服務(wù)器已經(jīng)達到其性能上限而出現(xiàn)不再接收其他媒體服務(wù)器遷移過來的客戶請求的現(xiàn)象發(fā)生，這將產(chǎn)生更多的VoD 系統(tǒng)時延。第一種情況將出現(xiàn)請求被拒絕，從而導(dǎo)致VoD 系統(tǒng)的服務(wù)失敗率上升;第二種情況會使得用戶請求被阻塞而導(dǎo)致系統(tǒng)響應(yīng)時延上升。這兩種情況都會導(dǎo)致流媒體系統(tǒng)用戶體驗下降。

為了解決媒體服務(wù)器節(jié)點之間負載不均勻分布以及服務(wù)不間斷冗余容災(zāi)帶來的問題，人們在流媒體服務(wù)基于遷移的任務(wù)調(diào)度方面進行了大量研究。Wolf 等提出一種DASD 跳躍算法［4-5］，通過媒體服務(wù)器間的請求遷移來維護硬盤負載均衡。Guo 等［6］提出了一種組合負載均衡算法(Combinational load balance)，通過視頻副本放置來減少用戶請求的阻塞率。Zhao 等［7］研究了同構(gòu)分布式VoD 系統(tǒng)的負載遷移和動態(tài)文件副本更新問題，提出了隨機早期遷移(Random early migration，REM)算法，較好地解決了服務(wù)失敗率和時延問題。

上述方法主要關(guān)注的是請求到達時的任務(wù)分配問題，根據(jù)當前流媒體服務(wù)系統(tǒng)的負載狀態(tài)均衡各媒體服務(wù)器的負載，以達到系統(tǒng)整體負載均衡的目的。同時，在考慮請求均衡分配時，系統(tǒng)整體負載較重的情況下，如果需要通過多步遷移以接收一個新到達的請求，將不可避免地造成對正在服務(wù)中的請求以及新到達的請求引入服務(wù)的短暫中斷和服務(wù)時延增加。流媒體系統(tǒng)在組建完成后，任何兩個節(jié)點間是否可遷移已經(jīng)確定，故可預(yù)先計算任意一個節(jié)點到其他所有節(jié)點的所有可能遷移路徑，避免遷移決策實時計算開銷。另外，上述研究均沒有考慮到當正在服務(wù)中的設(shè)備出現(xiàn)故障時的服務(wù)遷移問題。

本文提出了基于請求遷移的任務(wù)調(diào)度算法，包括:①對于新到達的點播請求，如果包含該請求媒體內(nèi)容的所有媒體服務(wù)器均處于滿負載狀態(tài)，在保障當前正在服務(wù)中請求不間斷的情況下通過有限步的請求遷移滿足新到達請求被服務(wù);如果需要遷移的請求數(shù)量超過預(yù)設(shè)閾值，則拒絕新到達請求以保障正在服務(wù)中的會話質(zhì)量;②如果某個正在服務(wù)中的媒體服務(wù)器出現(xiàn)故障不能服務(wù)時，調(diào)度模塊檢測到后立即將該服務(wù)器負責的請求快速遷移到其他存儲有相應(yīng)媒體內(nèi)容的服務(wù)器上繼續(xù)為用戶提供服務(wù)，保障用戶服務(wù)不中斷。

1 VoD 系統(tǒng)性能描述

表1 為符號說明。針對VoD 系統(tǒng)的性能質(zhì)量，近期一些研究者關(guān)注服務(wù)器系統(tǒng)、客戶端以及它們之間的網(wǎng)絡(luò)。Mundur 等［8］研究了接納控制和網(wǎng)絡(luò)傳輸機制以滿足數(shù)據(jù)比特率、端到端VoD服務(wù)時延約束的QoS 要求。他們的系統(tǒng)中仍然采用簡單的最后一分鐘遷移策略，遷移只有在請求被阻塞時才會發(fā)生。楊戈等［9］分析了基于CDN(Content distribution network)和基于遷移只有在請求被阻塞時才會發(fā)生的情況。還分析了基于CDN(Content distribution network)和基于P2P(Peer-to-peer)，采用批處理、補丁等算法的流媒體系統(tǒng)。Barnett 等［10］在中央控制的視頻系統(tǒng)和分布式視頻系統(tǒng)上根據(jù)存儲和流化成本兩方面比較了“setup”的開銷。Kao 等［11］研究融合了基于CDN 的用戶交互操作來分析不同VoD 系統(tǒng)中通信和存儲開銷之間的平衡。

表1 符號說明Table 1 Key variables

對VoD 點播系統(tǒng)而言，系統(tǒng)穩(wěn)定性體現(xiàn)在是否能夠持續(xù)不斷地為用戶提供服務(wù)。而VoD 系統(tǒng)的穩(wěn)定性又主要體現(xiàn)在請求成功率和服務(wù)時延上。其中，請求成功率μ 定義為:

請求服務(wù)時延Ti定義為從系統(tǒng)接收到請求到媒體服務(wù)器開始為其提供服務(wù)之間的時間間隔。假設(shè)所有媒體服務(wù)器對請求的處理時間τ 都相同。如果新請求能夠一次被某個媒體服務(wù)器服務(wù)，則服務(wù)時延為τ;如果該請求經(jīng)過有限步驟遷移后被某媒體服務(wù)器服務(wù)，則服務(wù)時延為遷移路徑上服務(wù)器的數(shù)量乘以τ;如果調(diào)度器在決策時發(fā)現(xiàn)經(jīng)過限定的遷移步驟仍然無法為該請求提供服務(wù)，則拒絕請求。

本文采用請求成功率和服務(wù)時延兩個性能指標來衡量VoD 系統(tǒng)的性能。

2 基于請求遷移的任務(wù)調(diào)度算法

2.1 有限步請求遷移描述

如圖1(a)所示的VoD 系統(tǒng)中有3 臺媒體服務(wù)器，每個服務(wù)器能夠存儲2 個視頻內(nèi)容，同時共享一個大的存儲空間。每個服務(wù)器可以同時服務(wù)5 個用戶。假設(shè)一個內(nèi)容A 的新請求或遷移請求在某時刻到達。由于只有媒體服務(wù)器1 上存儲有視頻A，而此時服務(wù)器1 已經(jīng)達到其服務(wù)能力上限。為了能夠為新請求提供服務(wù)，需要從服務(wù)器1 上遷出一個視頻B 正在服務(wù)中的請求到服務(wù)器2 上。遷移的請求不能立即被服務(wù)器2 接收，因為它也已經(jīng)滿負載運行。此時，服務(wù)器2 將一個視頻C 的請求遷移到媒體服務(wù)器3，由于服務(wù)器3這個時候還沒有滿負載，能夠接收該遷入的請求。至此，經(jīng)過2 步遷移后，新請求被媒體服務(wù)器1 接收和服務(wù)。在遷移完成之后，除了最后一臺服務(wù)器負載增加了1，遷移路徑上其他服務(wù)器負載都保持不變，圖1(b)展示了遷移過程和遷移后的系統(tǒng)狀態(tài)。如圖1(c)所示，如果共享存儲中有視頻A，則該請求可以直接被分配到媒體服務(wù)器3，由其接收并提供服務(wù)。

圖1 系統(tǒng)請求遷移示意圖Fig.1 Demonstration of migration in VoD

2.2 新任務(wù)到達時請求遷移

新任務(wù)到達時請求遷移分為兩種:一種是存在多個媒體服務(wù)器存儲有被請求的內(nèi)容時，根據(jù)當前各服務(wù)器的負載狀態(tài)對請求任務(wù)進行分配，以保證各服務(wù)器負載平衡;另外一種是在一個VoD 系統(tǒng)中，當某個熱門視頻的請求到達時，所有緩存有該視頻的服務(wù)器都達到負載容量上限，這時該請求將會被阻塞。但這里仍然可以通過遷移一個正在服務(wù)中的請求到其他服務(wù)器上來服務(wù)該新請求。被遷移的請求可能被其他服務(wù)器立即接收，也可能在其遷移成功前引起一系列的遷移操作。這種遷移是由調(diào)度器在決定遷移之后發(fā)起，本文稱之為新任務(wù)到達時請求遷移。

2.3 故障時請求遷移

故障時請求遷移主要目的是在出現(xiàn)單機故障時保障用戶服務(wù)不間斷。當集群中的某個媒體服務(wù)器因為硬件或軟件原因出現(xiàn)故障無法為用戶提供服務(wù)時，調(diào)度服務(wù)器監(jiān)測到后，及時將該服務(wù)器正在服務(wù)的用戶請求遷移到其他存儲有相應(yīng)視頻內(nèi)容的服務(wù)器上，繼續(xù)為用戶提供服務(wù)。如果在遷移過程中發(fā)現(xiàn)某個用戶請求的視頻內(nèi)容在其他服務(wù)器及共享存儲上均不存在時，則調(diào)度服務(wù)器記錄任務(wù)故障信息并向用戶發(fā)送消息以中止服務(wù)。圖2 為故障時遷移前、后VoD 系統(tǒng)媒體流狀態(tài)。這種遷移由調(diào)度服務(wù)器在發(fā)現(xiàn)故障后發(fā)起，本文稱之為被動請求遷移，也叫故障時請求遷移。

圖2 故障時請求遷移Fig.2 Migration in server failure

2.4 RMTS 算法

圖3 展示了傳統(tǒng)遷移算法、REM 算法以及本文提出的調(diào)度算法中遷移概率pi和當前服務(wù)負載li的關(guān)系。圖3(a)表示傳統(tǒng)的遷移算法只有在新到達的請求被阻塞時才進行請求遷移，這種策略稱為最后一分鐘請求遷移。圖3(b)中，REM算法中給出兩個閾值Max_th 和Min_th，當負載大于Max_th 時，表示服務(wù)器負載很重，任何新請求都將導(dǎo)致遷移事件發(fā)生。當負載介于Min_th 和Max_th 之間時，請求遷移發(fā)生的概率隨著負載的上升線性增加。由于過早遷移浪費服務(wù)能力，同時還會使得服務(wù)時延增加，而過晚遷移會導(dǎo)致系統(tǒng)負載不均衡。本文的調(diào)度算法在新請求到達時，根據(jù)各媒體服務(wù)器的全局負載狀態(tài)，決定是否直接將請求分配到某個服務(wù)器上還是經(jīng)過λ(λ＜Γ)步遷移后為其提供服務(wù)。遷移概率的計算公式為:

式中:B 和n 為參數(shù)，本文在第3 節(jié)討論賦值問題。

圖3 遷移概率與媒體服務(wù)器負載狀態(tài)的關(guān)系Fig.3 Relationship between migration possibility and server load

當負載li小于閾值時，說明該媒體服務(wù)器負載較輕，可繼續(xù)提供服務(wù)。當負載li大于閾值時，表示當前媒體服務(wù)器正在為一定數(shù)量的用戶提供服務(wù)，但仍然有能力接收新的請求。為了使系統(tǒng)的整體負載趨于均衡，可以在多個媒體服務(wù)器間進行請求遷移。由于請求遷移一方面會影響正在服務(wù)的用戶，同時會使得新到達的請求服務(wù)時延增加。因此，在媒體服務(wù)器負載達到設(shè)定的閾值Lth后，本文在S 型曲線基礎(chǔ)之上進行改進，計算遷移概率pi。從圖3(c)中可以看到:改進后的S型曲線在負載接近Lth時計算得到的遷移概率pi較小;當負載接近上限L 時計算得到的遷移概率pi較大，也就是說在服務(wù)可用的前提下，只有在負載較高時才進行請求遷移，以減少遷移引入的服務(wù)時延。當pi大于系統(tǒng)計算的隨機值時，進行負載均衡遷移。由于服務(wù)時延將隨著遷移路徑長度的增長而增加。因此本文對遷移路徑長度進行限制以保障用戶服務(wù)質(zhì)量。當根據(jù)媒體內(nèi)容分布H和媒體服務(wù)器物理連接拓撲Λ 計算得到的遷移路徑長度大于系統(tǒng)容忍的最大遷移路徑長度Γ時，將拒絕為接收該請求而進行正在服務(wù)中的請求遷移。

改進的S 型曲線，當參數(shù)n 越大時曲線越快趨近于1。本文中n 是為了接收新請求而進行的遷移路徑長度λ 的函數(shù)，且隨遷移路徑長度的增加而快速減小。因此，本文采用負指數(shù)函數(shù)形式表示，如式(2)所示:

結(jié)合式(1)和式(2)，可以得到如下屬性:

屬性1 調(diào)度器接收到新請求R(j)，如果所有存儲有媒體內(nèi)容j 的服務(wù)器負載均大于閾值Lth時，為了系統(tǒng)負載均衡需要計算遷移概率;當計算得到的遷移路徑長度λ 越大時，n 值越小，遷移概率越小。

由于請求遷移長度直接影響正在服務(wù)的用戶請求，上述性質(zhì)避免產(chǎn)生過長遷移路徑的遷移行為，保障用戶的服務(wù)質(zhì)量。

對于遷移路徑的獲取，在已知VoD 系統(tǒng)媒體內(nèi)容分布H 和媒體服務(wù)器物理連接拓撲Λ 時，將每個媒體服務(wù)器作為一個節(jié)點，部署有相同內(nèi)容的節(jié)點之間通過直線相連形成圖。本文假設(shè)系統(tǒng)中內(nèi)容保持穩(wěn)定，沒有更新，即圖中各節(jié)點的連接關(guān)系保持不變。當系統(tǒng)部署完成后，可根據(jù)改進的Dijkstra 算法［12-13］求得圖中任意節(jié)點為起始點到其他所有可到達節(jié)點的最短路徑集合。任務(wù)遷移發(fā)生時遷移路徑為該集合中的成員而無需再重新計算所有的遷移路徑。

本文在VoD 系統(tǒng)的調(diào)度服務(wù)器上展示基于請求遷移的調(diào)度算法。調(diào)度器收到一個視頻j 的請求R(j)時，將執(zhí)行以下算法:

Step1 對于R(j)，調(diào)度服務(wù)器根據(jù)當前媒體分布狀態(tài)H、系統(tǒng)各媒體服務(wù)器的負載li決定是否需要遷移:①如果服務(wù)器Si存儲有內(nèi)容j 且li＜Lth，則將R(j)分配給Si，更新Si負載狀態(tài)，轉(zhuǎn)到Step 6。②如果所有存儲內(nèi)容j 的服務(wù)器Si，均有l(wèi)i＞Lth:如果ω(i)集合中至少有一條路徑中緊隨Si的節(jié)點負載小于L，則計算各路徑的長度，再根據(jù)式(1)和(2)計算遷移概率pi;否則，轉(zhuǎn)到Step 5;

Step2 調(diào)度器生成隨機數(shù)p，0 ≤p ≤1。如果pi≥p 則轉(zhuǎn)到Step 3;否則轉(zhuǎn)到Step 4。

Step3 調(diào)度器向路徑上的服務(wù)器發(fā)送遷移消息。請求遷移在路徑上進行，R(j)被保持在調(diào)度器節(jié)點。

Step4 Si開始服務(wù)新到達的請求。調(diào)度器更新VoD 系統(tǒng)各節(jié)點的負載狀態(tài)，轉(zhuǎn)到Step 6。

Step5 拒絕請求R(j)。

Step6 調(diào)度器等待下一個請求。

RMTS 算法中，每個請求遷移發(fā)生前都要找到最優(yōu)路徑。由于遷移過程中新到達的請求保持在調(diào)度器，需要找到最優(yōu)的遷移路徑以減少其服務(wù)時延和保障系統(tǒng)負載均衡。為了選擇最優(yōu)路徑，定義負載均衡方差σ 為:

本文采用加權(quán)系數(shù)法來權(quán)衡遷移路徑長度和負載均衡方差，如式(4)所示:

式中:λ 為各個可選路徑的長度，λ ＜Γ。

當有多于一條最短路徑時，根據(jù)屬性1 在所有可選遷移路徑中選擇mp 值最小的路徑作為最終遷移路徑。

2.5 復(fù)雜度分析

通過上面給出的詳細步驟可以看出:調(diào)度器具有整個系統(tǒng)的全局信息，遷移決策、遷移路徑選擇以及統(tǒng)計信息更新都由調(diào)度器完成。當?shù)竭_一個新的請求時，調(diào)度器計算出遷移概率，如果需要遷移則選擇最優(yōu)的遷移路徑。更新統(tǒng)計信息以保持系統(tǒng)信息一致。調(diào)度器可以調(diào)度下一個請求而不是等待所有媒體服務(wù)器中的遷移任務(wù)完成，調(diào)度器的決策和按步遷移可以并行進行。在這種情況下，RMTS 算法的復(fù)雜度取決于遷移決策的計算以及遷移路徑的選擇，這也是算法中最耗時的部分。由于在系統(tǒng)內(nèi)容放置以及物理連接確定的情況下，可以預(yù)計算出所有可能的遷移路徑Ω 以及以節(jié)點i 為起始點到其他任意節(jié)點的路徑集合ω(i)，因此遷移路徑選擇是一個路徑長度排序問題，選擇mp 最小的路徑即可。時間復(fù)雜度是O(logN)，此處N 為可選遷移路徑的數(shù)量。RMTS算法可以很容易地擴展到由異構(gòu)服務(wù)器組成的VoD 系統(tǒng)，每個服務(wù)器可以有不同的存儲容量或服務(wù)能力。RMTS 算法對服務(wù)器的存儲容量沒有要求。對于存儲更多視頻副本的服務(wù)器，它們可能有更大的服務(wù)能力。

前文提到的REM 算法與RMTS 算法的區(qū)別主要為:REM 算法中視頻服務(wù)器服務(wù)負載達到兩個閾值中間時以一定的概率進行請求遷移，同時其根據(jù)最短路徑的原則實時計算遷移路徑。當系統(tǒng)內(nèi)容放置以及物理連接確定后，任意兩節(jié)點間是否可達即確定，故可以提前計算好所有節(jié)點到其他節(jié)點的遷移路徑，避免在遷移決策時計算開銷。RMTS 算法在選擇遷移路徑時使用負載均衡度和服務(wù)時延綜合評價函數(shù)，在保證負載均衡的同時選擇最短的遷移路徑以減小服務(wù)時延。另外，本文限定遷移路徑的長度。由于遷移會引入服務(wù)時延、影響被遷移的用戶服務(wù)質(zhì)量，因此當遷移路徑超過閾值時將拒絕進行請求遷移。與REM 算法相比，RMTS 算法能夠在更快得到遷移路徑的同時保障更小的服務(wù)時延。最后，在系統(tǒng)重負載條件下RMTS 算法會優(yōu)先保障正在服務(wù)中的用戶服務(wù)不受影響。

參數(shù)Lth的選擇，當服務(wù)器處于輕負載時，它有足夠的空間來接收新請求，所以請求被阻塞或拒絕的概率很小。此外，每次請求遷移都涉及到控制消息傳輸成本、接納控制以及任務(wù)調(diào)度。在本文的仿真實驗中，設(shè)定Lth為滿負載的70%，從而避免不必要的遷移。

3 試驗及結(jié)果分析

3.1 試驗環(huán)境

本文通過仿真試驗比較了RMTS 算法與傳統(tǒng)最后一分鐘請求遷移算法、DASD 算法和REM 算法在請求成功率、服務(wù)時延兩個方面的性能。試驗條件為:模擬20 臺媒體服務(wù)器和1 個中央調(diào)度器，200 個不同大小的媒體內(nèi)容;每個媒體服務(wù)器能夠存儲1000 個內(nèi)容，并且能夠同時服務(wù)120 個用戶。仿真VoD 系統(tǒng)中的所有媒體內(nèi)容存儲有不同數(shù)量的副本，200 個不同內(nèi)容所有的存儲數(shù)量為20 000。同時，假設(shè)用戶點播請求服務(wù)到達率為ξ 個請求每分鐘的泊松分布［14］，其中ξ 的取值范圍為36 到44。內(nèi)容點播模型采用θ=0.27的Zipf 分布［15-16］。假設(shè)所有內(nèi)容時長為60 min，模擬VoD 系統(tǒng)初始化時負載為0，則在一個影片播放時間內(nèi)該系統(tǒng)可以并發(fā)支持2400 個用戶點播請求，也就是說平均請求到達率約為40 請求/min。分析式(1)(2)，在媒體服務(wù)器負載超過112 的情況下，B 值取2680 時，請求遷移概率快速接近于1，即當媒體服務(wù)器負載快接近服務(wù)能力上限時，發(fā)生請求遷移的概率接近于1。模擬系統(tǒng)中α 分別取0.3、0.5、0.7 進行比較。

3.2 結(jié)果分析

圖4 和圖5 分別給出了α=0.3、α=0.5、α=0.7 三種情況下系統(tǒng)請求成功率與系統(tǒng)負載、服務(wù)時延與系統(tǒng)負載之間的變化關(guān)系。從圖中可以看到，隨著用戶到達率的增加，系統(tǒng)負載上升，請求成功率在下降，服務(wù)時延在增加。當系統(tǒng)負載較小時(ξ ＜41)，請求成功率和服務(wù)時延性能表現(xiàn)較好。當負載接近媒體服務(wù)器的能力上限時，請求成功率下降而服務(wù)時延上升。

圖4 請求成功率與系統(tǒng)負載之間的關(guān)系Fig.4 Relationship between request success rate and load

圖5 服務(wù)時延與系統(tǒng)負載之間的關(guān)系Fig.5 Relationship between service delay and load

從圖4 中可以看出，本文提出的RMTS 算法請求成功率在α=0.3、α=0.5、α=0.7 三種情況下均優(yōu)于REM 算法、DASD 算法以及傳統(tǒng)遷移算法。其中在α=0.5 時，RMTS 算法的請求成功率比REM 算法高出14%，而比傳統(tǒng)遷移算法高出15%。同時，從圖5 中可以看出，當α =0.5時，RMTS 算法的性能表現(xiàn)比α=0.3 和α=0.7時要好，這是因為α=0.5 時遷移路徑長度與媒體服務(wù)器當前負載對遷移概率的影響具有同等比重，在一定程度上能夠改善系統(tǒng)的請求成功率和服務(wù)時延。

圖6 和圖7 分別給出了α 取不同值時用戶請求成功率和服務(wù)時延的變化，同樣可以看出:當α取0.5 時系統(tǒng)的效率和服務(wù)時延最優(yōu)。

圖6 請求成功率與α 取值的關(guān)系Fig.6 Request success rate as a function of α

圖7 服務(wù)時延與α 取值的關(guān)系Fig.7 Service delay as a function of α

4 結(jié)束語

通過對流媒體點播系統(tǒng)中任務(wù)調(diào)度的研究，提出了基于新任務(wù)到達時以及故障時請求遷移的任務(wù)調(diào)算法。試驗結(jié)果表明:該算法能夠在新任務(wù)到達VoD 系統(tǒng)以及系統(tǒng)中出現(xiàn)服務(wù)器故障時對任務(wù)進行調(diào)度，提高系統(tǒng)的請求成功率并降低服務(wù)時延。

［1］吳偉.流媒體服務(wù)器遷移技術(shù)研究［D］.北京:中國科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院，2009.Wu Wei.The study of the request migration for streaming server［D］.Beijing:School of Information Science and Technology，University of Science and Technology of China，2009.

［2］Zhou Y，F(xiàn)u T Z J，Chiu D M.On replication algorithm in P2P VoD［J］.Association for Computing Machinery，2013，21(1):233-243.

［3］Dhage S N，Meshram B B.Design and implementation of video servers for VoD system［J］.International Journal of Cloud Computing，2013，2(1):61-88.

［4］Wolf J L，Yu P S，Shachnai H.DASD Dancing:a disk load-balancing optimization scheme for on-demand video-on-demand computer systems［J］.Sigmetrics Performance Evaluation Review，1995，23(1):157-166.

［5］Dhage S，Meshram B B.Disk load balancing and video ranking algorithm for efficient access in video server［C］∥International Conference on Communication，Information＆ Computing Technology，Mumbai，India，2012:1-6.

［6］Guo J，Taylor P，Zukerman M，et al.On the efficient use of video-on-demand storage facility［C］∥2003 International Conference on Multimedia and Expo，2003:329-332.

［7］Zhao Y，Kuo C C J.Video server scheduling using random early request migration［J］.Multimedia Systems，2005，10(4):302-316.

［8］Mundur P，Simon R，Sood A K.End-to-end analysis of distributed video-on-demand systems［J］.IEEE Transactions on Multimedia，2004，6(1):129-141.

［9］楊戈，廖建新，朱曉民，等.流媒體分發(fā)系統(tǒng)關(guān)鍵技術(shù)綜述［J］.電子學(xué)報，2009，37(1):137-145.Yang Ge，Liao Jian-xin，Zhu Xiao-min，et al.Survey of key technologies of the distribution system for streaming media［J］.Acta Electronica Sinica，2009，37(1):137-145.

［10］Barnett S A，Anido G J.A cost comparison of distributed and centralized approaches to video-on-demand［J］.IEEE Journal on Selected Areas in Communications，1996，14(6):1173-1183.

［11］Kao Y C，Lee C N，Wu P J，et al.A network coding equivalent content distribution scheme for efficient peerto-peer interactive VoD streaming［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23(6):985-994.

［12］Chao Y，Hongxia W.Developed Dijkstra shortest path search algorithm and simulation［C］∥2010 International Conference on Computer Design and Applications(ICCDA)，Qinhuangdao，China，2010:116-119.

［13］Dijkstra E W.A note on two problems in connexion with graphs［J］.Numerische Mathematic，1959，1(1):269-271.

［14］Haight F A.Handbook of the Possion Distribution［M］.New York:Wiley，1967.

［15］Kali R.The city as a giant component:a random graph approach to Zipf＇s law［J］.Applied Economics Letters，2003，10(11):717-720.

［16］Kingsley Z G.Human Behavior and the Principle of Least Effort［M］.Boston:Addison-Wesley，1949.