基于磁盤系統(tǒng)的多用戶視頻準(zhǔn)入算法

（1.電子科技大學(xué) 計算機科學(xué)與工程學(xué)院， 成都 610054； 2.中國民航飛行學(xué)院， 四川 廣漢 618307）



摘要：分析了基于磁盤系統(tǒng)的視頻服務(wù)器的準(zhǔn)入策略，提出了基于磁盤系統(tǒng)的為保證視頻服務(wù)器接納更大數(shù)目用戶的準(zhǔn)入算法，即在每個服務(wù)周期中每個用戶要求檢索到的數(shù)據(jù)塊的數(shù)目與其對應(yīng)的回放速率成比例，視頻服務(wù)器通過過量預(yù)約資源來允許更大數(shù)量的客戶數(shù)。這種算法允許視頻服務(wù)器接納更大數(shù)目的用戶，滿足多用戶媒體回放的穩(wěn)態(tài)性和遷移態(tài)連續(xù)性的要求。

關(guān)鍵詞：磁盤系統(tǒng)； 多用戶； 視頻存儲服務(wù)器； 準(zhǔn)入控制； 算法

中圖分類號：TP388.6文獻標(biāo)志碼：A

文章編號：1001-3695(2008)11-3314-03



Access algorithm of video server based on disk system



HE Yuan-qing1，2， SUN Shi-xin1



(1.School of Computer Science Engineering，University of Electronic Science Technology of China， Chengdu610054， China; 2. Civil Aviation Flight University， Guanghan Sichuan 618307， China)



Abstract:This paper analyzed the access strategy of the video server which was based on the disk system. In order to guarantee the larger number of users accepted by the video storage server， it put forward a disk-system-based access algorithm， which meant that the data block numbers searched by each user in each cycle of service were in proportion to the playback rate correspondingly. This algorithm can meet the demands of the steady supporting the multi-user media playback and continuity of migration.

Key words：disk system; multi-user; video storage server; access control; algorithm



通信、高速分組交換、移動數(shù)據(jù)通信、媒體壓縮及處理器和存儲器設(shè)計的飛速發(fā)展，使得分布式多媒體應(yīng)用逐漸變得切實可行。多媒體郵件、組合表現(xiàn)、高質(zhì)量視頻點播、音頻、多媒體文檔的協(xié)同編輯、大型圖書館或多媒體檔案以及虛擬現(xiàn)實環(huán)境等交互式應(yīng)用將會在這些基礎(chǔ)設(shè)施中廣泛存在^[1]。用戶可以從各種終端系統(tǒng)上訪問這些軟件，如PDA、機頂盒、個人計算機等。這些應(yīng)用軟件的交互性要求使用者控制結(jié)果顯示或多媒體數(shù)據(jù)流的內(nèi)容，如視頻、音頻和圖表等。使用者尤其要會裁減、放大、篩選、存儲等媒體編輯功能。而且，大多數(shù)應(yīng)用軟件是以存儲亦即靜態(tài)的形式處理多媒體信息的。應(yīng)用軟件的功效直接取決于存儲多媒體信息的存儲服務(wù)器的功效。

1大規(guī)模視頻存儲服務(wù)器的性能指標(biāo)要求

對視頻存儲服務(wù)器的要求與對現(xiàn)有的基于網(wǎng)絡(luò)的服務(wù)器的要求大相徑庭。首先，視頻數(shù)據(jù)的實時性要求周期性檢索及數(shù)據(jù)傳送形式的QoS保證，使用準(zhǔn)入控制和資源預(yù)定可以提供這種保證。服務(wù)器存儲設(shè)備

中的數(shù)據(jù)布局及服務(wù)器安排搜索的算法在設(shè)計上必須保證這些資源預(yù)定在合法用戶的使用過程中一直有效。很顯然，準(zhǔn)入控制、數(shù)據(jù)布局及存儲訪問安排在設(shè)計中極為重要^[2]。而且，服務(wù)器必須具備同時滿足成百上千獨立客戶的能力，即直接轉(zhuǎn)換為對成千上萬G位的存儲和網(wǎng)絡(luò)處理能力的要求；服務(wù)器體系結(jié)構(gòu)根據(jù)網(wǎng)絡(luò)流量及客戶數(shù)量具有可伸縮性也至關(guān)重要。為此，要求大規(guī)模視頻存儲服務(wù)器滿足以下幾點性能指標(biāo)^[3]：

a)并行性。服務(wù)器可能必須同時向數(shù)以千計的并行客戶提供服務(wù)，每個客戶有一些激活的視頻流連接，獨立地訪問相同或不同的視頻數(shù)據(jù)。并行性指標(biāo)可定義為在任何播放控制狀態(tài)下可獨立訪問同一視頻數(shù)據(jù)的最大客戶數(shù)。

b）訪問延時和操作延時。訪問延時是客戶發(fā)出請求到視頻數(shù)據(jù)被傳輸?shù)娇蛻舳怂璧却臅r間，這主要取決于服務(wù)器的服務(wù)模式和雙向網(wǎng)絡(luò)延遲，一般應(yīng)少于幾秒；操作延時是客戶進行交互操作，如快進、倒退、隨機訪問等，高度的交互性要求操作延時低于1 s。

c)可伸縮性。服務(wù)器體系結(jié)構(gòu)應(yīng)隨客戶數(shù)量可伸縮；服務(wù)器還必須支持不同種類的客戶、媒體數(shù)據(jù)和訪問網(wǎng)絡(luò)。

d)可擴展性。服務(wù)器必須有很大的可擴展性，可支持多個應(yīng)用軟件設(shè)想，可擴展為支持不同服務(wù)模型。

按以上性能指標(biāo)，可將視頻服務(wù)器分為如表1所示的幾類。假設(shè)按NTSC的視頻連接的速率為5 Mbps的MPEG視頻流，對HTDV質(zhì)量的壓縮視頻流來說，存儲和網(wǎng)絡(luò)帶寬要求會更多。鑒于存儲技術(shù)的發(fā)展而使得存儲容量的增加大于存儲總處理能力的增加，因此從存儲系統(tǒng)獲得更大的總處理能力比提供更大的存儲容量更具有挑戰(zhàn)性。未來的分布式多媒體系統(tǒng)中服務(wù)器的存儲體系結(jié)構(gòu)將是包含多層的層次結(jié)構(gòu)，包括直接訪問存儲磁盤（DASD）、光盤、磁帶和光帶等磁光設(shè)備。

2大規(guī)模視頻存儲服務(wù)器體系結(jié)構(gòu)

大規(guī)模視頻存儲服務(wù)器硬件結(jié)構(gòu)必須具備支持大規(guī)模并行處理能力的特性。一般地，視頻服務(wù)器是采用多個處理節(jié)點（或稱模塊）分布式互連的體系結(jié)構(gòu)，每個處理模塊均有自己的CPU和內(nèi)存。基于目前的服務(wù)器體系結(jié)構(gòu)，每個模塊必須具備存儲I/O接口、外部網(wǎng)絡(luò)I/O接口、模塊間互連I/O接口三種必備的接口，此外還有用于多個處理模塊間同步的源同步時鐘接口等。模塊的基本結(jié)構(gòu)如圖1所示。

視頻服務(wù)器模塊的這種特殊結(jié)構(gòu)可以使其具有很高的可擴展性，可以從一個模塊擴展到成百上千個模塊，模塊之間通過互連I/O實現(xiàn)互連，模塊互連的接口實現(xiàn)方式有許多種，目前有HiPPI、SCI、ATM、Ethernet、PCI等。視頻服務(wù)器在本質(zhì)上是網(wǎng)絡(luò)文件吞吐服務(wù)器，因此對I/O性能要求非常高，大型視頻服務(wù)器的網(wǎng)絡(luò)吞吐能力可以從100 Mbps擴展到到幾百個Gbps之間，能支持多達10萬個2~4 Mbps流媒體用戶同時在線，其內(nèi)部互連I/O 的峰值則可達到幾百到幾千Gbps。

模塊化的設(shè)計注定了視頻服務(wù)器采用分布式體系結(jié)構(gòu)，多個處理模塊之間通過內(nèi)部互連I/O實現(xiàn)高帶寬、低時延的無級互連，以達成系統(tǒng)的高度可伸縮性，如圖2所示。

由于內(nèi)部模塊間的連接方式具有很高的靈活性，基于不同的互連方式，其內(nèi)部高速互聯(lián)網(wǎng)具有不同的拓撲結(jié)構(gòu)，視頻服務(wù)器具有不同的硬件體系結(jié)構(gòu)。

3基于磁盤系統(tǒng)的視頻服務(wù)器的準(zhǔn)入算法

一個大規(guī)模視頻服務(wù)器要求同時滿足多個用戶的需求。在最好的方案中，所有的用戶要求檢索相同的數(shù)據(jù)流，則服務(wù)器只需從磁盤上檢索一次視頻流并多路發(fā)送給所有的用戶。但更經(jīng)常的是，不同的用戶可能要求對不同視頻流的檢索；甚至當(dāng)多個用戶要求檢索相同的視頻流時，其要求也存在著相當(dāng)大的差別（可能每一個用戶在相同的時間內(nèi)檢索視頻流的不同部分）。保證每個要求的實時檢索的簡單方案是為每個要求指定一個磁盤頭^[4，5]，但這將可同時服務(wù)的用戶數(shù)目限定在可用的磁盤頭數(shù)目內(nèi)，該數(shù)量遠小于使得視頻服務(wù)器具有經(jīng)濟可行性所需要的用戶數(shù)目^[6]。

為精確描述該問題，假定一個視頻服務(wù)器可以準(zhǔn)入τ個用戶，每個用戶都在檢索一個視頻流。視頻服務(wù)器在τ個用戶中進行多路復(fù)合傳輸，在切換到另一個請求前對每個請求i∈[1，τ]檢索一定數(shù)目的數(shù)據(jù)塊ki。每個序列k1，k2，…，kτ的檢索構(gòu)成一個服務(wù)循環(huán)。視頻服務(wù)器重復(fù)執(zhí)行服務(wù)循環(huán)直到完成所有的命令。盡管粒度和分散度參數(shù)決定了一個視頻流連接的連續(xù)視頻數(shù)據(jù)塊檢索的速率，從一個連接切換到另一個連接也需要額外的時間，其最大值為從一個流的數(shù)據(jù)塊移動磁盤頭到另一個流的數(shù)據(jù)塊所需的搜索時間（數(shù)據(jù)布局并不限制不同流間的相對位置）。因此，在一次服務(wù)循環(huán)中，檢索第i個請求的ki個數(shù)據(jù)塊所需的總時間由以下幾部分組成：

a）α是從第i個請求切換到第i-1個請求所需的時間和傳送第i個請求的一個數(shù)據(jù)塊所需的時間；

b）β是在這個服務(wù)循環(huán)中傳送第i個請求的剩余ki-1個數(shù)據(jù)塊所需的時間。

若η1ms，η2ms，…，ητms代表粒度，l1ds，l2ds，…，lτds代表分散度參數(shù)，R1pl，R2pl，…，Rτpl代表同時檢索的τ個流的回放速率，則當(dāng)且僅當(dāng)每個循環(huán)的總體服務(wù)時間不超過所有請求的回放時限的最小值時，每個請求的連續(xù)性檢索才能被保證。

∑τi=1[(lmaxseek+(ηims×Simu)/Rdr)α+(ki-1)×(lids+(ηims×simu)/Rdr)β]≤mini∈[1，τ](ki×(ηims/Ripl)）(1)

式(1)中：lmaxseek為最大搜索（延遲）時間；Simu為第i個請求的媒體數(shù)據(jù)單位尺寸；Rdr是磁盤數(shù)據(jù)傳輸速率；lids為尋道到第i個請求的數(shù)據(jù)塊所需的時間。當(dāng)且僅當(dāng)k1，k2，…，kτ值滿足式(1)時，視頻服務(wù)器才可能同時服務(wù)于所有的τ項請求。注意到式(1)含有τ個變量而僅存在一個等式，k1，k2，…，kτ的值的確定需要附加策略。

從式(1)中可以看出，若k1=k2=…=k1=k，則式(2)給出通過循環(huán)Robin算法算出的可被服務(wù)的用戶請求的最大數(shù)目為

τcmax=ηavgms/[Rmaxpl×(lavgds+(ηavgms×Savgmu)/Rdr)]

(2)

可見，由循環(huán)Robin算法算出的可被服務(wù)的用戶請求的數(shù)目受限于具有最大回放速率請求。此外，具有最大回放速率的請求將準(zhǔn)確檢索出它在一個服務(wù)循環(huán)時限中需要的數(shù)據(jù)塊的數(shù)目，盡管其他回放速率較小的請求將檢索出多于它們在每個服務(wù)循環(huán)中所需的數(shù)據(jù)塊的數(shù)目。結(jié)果，通過削減兩個服務(wù)周期中檢索出的此類用戶請求的數(shù)據(jù)塊的數(shù)目，可以接納更大數(shù)目的用戶。

保證在每個服務(wù)周期中為每個用戶要求檢索到的數(shù)據(jù)塊的數(shù)目與其對應(yīng)的回放速率成比例將是一個更好的選擇。從而，若k是比例常數(shù)，得到k1=k×R1pl，k2=k×R2pl，…，kτ=k×Rτpl。在式(1)中代入ki的值，可得

∑τi=1[(lmaxseek+(ηims×simu)/Rdr)+(k×Ripl-1)×

(lids+(ηims×simu)/Rdr)]≤k×mini∈[1，τ](ηims)(3)

更進一步地，可以從式(3)推出能被同時服務(wù)的用戶最大數(shù)目τpmax：

τpmax≤ηavgms/[Ravgpl×(lavgds+(ηavgms×savgms)/Rdr)](4)

給定用戶請求的數(shù)目τ≤τpmax，式(3)可以用來決定k，然后就可以得到k1，k2，…，kτ的值。注意，這樣得到的k值可能不是整數(shù)。因為數(shù)據(jù)流的回放以定量的形式進行，如視頻幀，如果每個數(shù)據(jù)塊都被假設(shè)包含一個定量，一個數(shù)據(jù)塊的一小部分檢索結(jié)果將不能回放，從而引起回放的缺乏直到余下的部分到達為止，這很可能在下一個周期才發(fā)生。為了改變這種狀況，對于所有的請求，在每個服務(wù)周期中檢索得到的數(shù)據(jù)塊數(shù)目必須是整數(shù)。

通過在每個周期為每個用戶請求i檢索的數(shù)據(jù)塊的數(shù)目在ki」和「ki間變化使能狀態(tài)^[11]，以便在平均水平上檢索速率為每服務(wù)周期ki個數(shù)據(jù)塊。更進一步，不同用戶請求的使能被錯開；一個用戶的使能與另一個用戶的使能不相匹配。這樣使每個周期中的服務(wù)時間均無凈增長，所以不會違背連續(xù)性檢索的要求。那些數(shù)據(jù)塊使能的用戶是在服務(wù)周期中因較長時間的不能使而面臨缺乏的用戶。該方法滿足了在每個服務(wù)周期中每個視頻流連續(xù)性播放的要求。

從式(4)可以看出，假設(shè)用戶請求在視頻流的回放速率中具有較大的離散性，在上述技術(shù)能夠接收更多的用戶連接請求。事實上，給定任何τ用戶請求的集合一個優(yōu)先權(quán)，若存在一個集合k′1，k′2，…，k′τ滿足連續(xù)性要求不等式(1)，則上述算法可以保證得到滿足不等式(1)的非負整數(shù)k1，k2，…，kτ。

若被準(zhǔn)入的用戶數(shù)目事先并不知道，而且可能動態(tài)變化，則連續(xù)性要求不僅在穩(wěn)定狀態(tài)被維持，也需要在新用戶的動態(tài)準(zhǔn)入過程中被維持。為理解其原因，假設(shè)一個視頻服務(wù)器在服務(wù)于r個請求的集合時，又將服務(wù)于一個新的請求。若τ+1≤τpmax，則視頻服務(wù)器可以計算出滿足(τ+1)個請求所必需的k的新值knew。若knew=kold（這里kold是視頻服務(wù)器服務(wù)于已存在的τ個請求時所使用的k值），則視頻服務(wù)器可立即接收第(τ+1)個用戶請求。若knew≠kold，則knew＞kold，且視頻服務(wù)器為所有的用戶計算出新值ki，即ki=knew×Ripl，對所有的i∈[1，τ]成立，且開始為每個i∈[1，τ]傳送knewi數(shù)據(jù)塊。但是，在接收第(τ+1)個用戶的請求后的第一個服務(wù)周期中，第i個用戶可得到的數(shù)據(jù)塊的數(shù)量是那些當(dāng)前服務(wù)周期中的塊，即kold，其回放時間或許短于為每個i∈[1，τ+1]傳輸knewi個數(shù)據(jù)塊所需的時間，從而導(dǎo)致在該遷移服務(wù)周期中對連續(xù)性要求的違背。

為避免這樣的遷移不連續(xù)性，可以對算法進行修正，使得傳送ki+1個數(shù)據(jù)塊所用的時間（即k×Ripl而不是k×Ripl-1）是式(3)左邊所使用的時間，而回放ki塊是右邊所使用的時間（即右邊沒有變化）。在這種情況下可以看出，對于τ≤τpmax，式(3)左邊和右邊的差異隨著k的增加而增加，結(jié)果第一步便可保證從kold到knew的順利遷移，由此即可得到支持多用戶媒體回放的穩(wěn)態(tài)和遷移態(tài)連續(xù)性的準(zhǔn)入控制算法。

4結(jié)束語

基于磁盤系統(tǒng)的多用戶視頻準(zhǔn)入控制策略，在保證每個服務(wù)周期中為每個用戶要求檢索到的數(shù)據(jù)塊的數(shù)目與其對應(yīng)的回放速率成比例是一個較好的選擇，能夠得到支持多用戶媒體回放的穩(wěn)態(tài)性和遷移態(tài)連續(xù)性的要求， 保證視頻服務(wù)器接納更大數(shù)目的用戶；在大規(guī)模視頻服務(wù)器中，采用分層準(zhǔn)入控制策略，視頻服務(wù)器通過過量預(yù)約資源能從總體水平上允許更大數(shù)量的客戶數(shù)。

參考文獻：

［1］GUTTAG K， GOVE R，Van AKEN J R，et al. A single-chip multiprocessor for multimedia:the MVP[J].IEEE Computer Graphics and Application，1992，12(6):53-64.

[2]何元清，孫世新，黃天云.基于并行磁盤陣列的視頻數(shù)據(jù)布局[J].計算機應(yīng)用研究，2004，21(4):63-65.

[3]HE Yuan-qing， SUN Shi-xin， CHEN Wen-yu. Network communication delay effects parallel efficiency[J].Journal of the University of Electronic Science and Technology of China，2002，31(2):156-158.

[4]CHANG E D， ZAKHOR A. Admission control and data placement for VBR video server[C]//Proc of the 1st International Conference on Image Processing.Piscataway:IEEE Press， 1994：278-282.

[5]Sarnoff Real-Time Corporation. MAGIC media server: a scalable and cost effective video server[K]. Princeton NJ: Wikipedia.

[6]GOPALAKRISHNAN P G. Real-time upcalls， WUCS95-06[R].Washington DC:Washington University， 1995.