流媒體系統中基于請求遷移的任務調度算法

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

(1.中國科學院聲學研究所 國家網絡新媒體工程技術研究中心，北京100190;2.中國科學院大學，北京100190)

0 引 言

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

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

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

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

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

1 VoD 系統性能描述

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

表1 符號說明Table 1 Key variables

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

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

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

2 基于請求遷移的任務調度算法

2.1 有限步請求遷移描述

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

圖1 系統請求遷移示意圖Fig.1 Demonstration of migration in VoD

2.2 新任務到達時請求遷移

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

2.3 故障時請求遷移

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

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

2.4 RMTS 算法

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

式中:B 和n 為參數，本文在第3 節討論賦值問題。

圖3 遷移概率與媒體服務器負載狀態的關系Fig.3 Relationship between migration possibility and server load

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

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

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

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

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

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

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

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

Step2 調度器生成隨機數p，0 ≤p ≤1。如果pi≥p 則轉到Step 3;否則轉到Step 4。

Step3 調度器向路徑上的服務器發送遷移消息。請求遷移在路徑上進行，R(j)被保持在調度器節點。

Step4 Si開始服務新到達的請求。調度器更新VoD 系統各節點的負載狀態，轉到Step 6。

Step5 拒絕請求R(j)。

Step6 調度器等待下一個請求。

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

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

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

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

2.5 復雜度分析

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

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

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

3 試驗及結果分析

3.1 試驗環境

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

3.2 結果分析

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

圖4 請求成功率與系統負載之間的關系Fig.4 Relationship between request success rate and load

圖5 服務時延與系統負載之間的關系Fig.5 Relationship between service delay and load

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

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

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

圖7 服務時延與α 取值的關系Fig.7 Service delay as a function of α

4 結束語

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

［1］吳偉.流媒體服務器遷移技術研究［D］.北京:中國科學技術大學信息科學技術學院，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，Fu 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］楊戈，廖建新，朱曉民，等.流媒體分發系統關鍵技術綜述［J］.電子學報，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.