摘　要： 選播" title="選播">選播通信是下一代網(wǎng)絡(luò)中一種新的通信方式。其中應(yīng)用層" title="應(yīng)用層">應(yīng)用層選播以其標(biāo)準(zhǔn)靈活、易于擴(kuò)展和實現(xiàn)等優(yōu)勢，已成為近年來通信領(lǐng)域研究的熱點。分析了受到普遍關(guān)注的應(yīng)用層選播通信中服務(wù)器負(fù)載均衡問題，在此基礎(chǔ)提出了基于等價子集" title="等價子集">等價子集的服務(wù)器選擇策略，并且通過實驗證明了該策略的有效性。
　　關(guān)鍵詞： 選播 等價子集 負(fù)載均衡 服務(wù)器選擇

?

　　選播通信是下一代網(wǎng)絡(luò)中一種新的通信方式^[1-3]。由于這種選播方式可以分別在網(wǎng)絡(luò)層和應(yīng)用層實現(xiàn)，因此存在著兩種選播通信模型：應(yīng)用層選播和網(wǎng)絡(luò)層選播。總的來說，網(wǎng)絡(luò)層選播實現(xiàn)方法簡單，但是存在許多缺陷。例如:需要修改路由器配置、不便于改善通信的無狀態(tài)性、不支持用戶對服務(wù)器選擇的定義、在選擇標(biāo)準(zhǔn)方面缺乏靈活性。而應(yīng)用層選擇的標(biāo)準(zhǔn)靈活、易于擴(kuò)展和實現(xiàn)、不需要修改路由器。
　　目前,國內(nèi)外對網(wǎng)絡(luò)層選播的研究比較多，但由于網(wǎng)絡(luò)層選播的局限性，許多研究者試圖從應(yīng)用層選播方面找到提高通信質(zhì)量的突破口。網(wǎng)絡(luò)層選播僅僅依靠網(wǎng)絡(luò)自身的拓?fù)浣Y(jié)構(gòu)來選擇最近的服務(wù)器(如路由器跳數(shù)最小)，而應(yīng)用層選播依賴于外部的實體來為用戶選擇一個當(dāng)前性能最好的服務(wù)器。對于用戶來說，“最近”的服務(wù)器并不能保證是性能“最好”的，因此應(yīng)用層選播對通信質(zhì)量更有保證，并且服務(wù)器選擇具有更多的靈活性和可擴(kuò)展性。
　　但是在進(jìn)一步的研究中發(fā)現(xiàn)，應(yīng)用層選播仍然存在著一個不容忽視的問題，即服務(wù)器負(fù)載的振蕩。因此，本文對應(yīng)用層選播通信的關(guān)鍵技術(shù)服務(wù)器選擇進(jìn)行了深入分析，找到了實現(xiàn)服務(wù)器負(fù)載均衡的突破口，提出了基于等價子集的選擇策略。在等價子集中包含了多個“最好”的服務(wù)器，這就為用戶提供了更多的選擇。當(dāng)?shù)葍r子集的規(guī)模發(fā)生變化時，可以得到不同服務(wù)器負(fù)載分布。而且從中發(fā)現(xiàn)：等價子集的準(zhǔn)入、準(zhǔn)出條件的不同組合可在不同程度上緩解服務(wù)器負(fù)載振蕩，最終找到實現(xiàn)服務(wù)器負(fù)載均衡的最佳準(zhǔn)入、準(zhǔn)出條件的組合。
1 應(yīng)用層選播中的服務(wù)器負(fù)載振蕩問題
　　在應(yīng)用層選播通信中，選播解析器" title="解析器">解析器通常會引導(dǎo)客戶與當(dāng)前性能最好的服務(wù)器進(jìn)行連接，這樣似乎已經(jīng)非常完美了，客戶似乎也可以享受到最好的通信服務(wù)了。然而應(yīng)用層選播通信中一個潛在問題，即服務(wù)負(fù)載振蕩就會隨之產(chǎn)生。
　　當(dāng)選播解析器發(fā)現(xiàn)某個服務(wù)器當(dāng)前性能最好時，選播解析器可能會引導(dǎo)不只一個客戶端" title="客戶端">客戶端與其建立連接。因而造成該服務(wù)器的負(fù)擔(dān)過重，該服務(wù)器不能及時地響應(yīng)所有客戶請求，導(dǎo)致其性能的下降。而此時其他的服務(wù)器卻因沒有客戶請求的到來而仍然處于空閑狀態(tài)。當(dāng)選播解析器又一次刷新所有服務(wù)器的性能參數(shù)時，又發(fā)現(xiàn)新的性能最好的服務(wù)器，它又會引導(dǎo)多個客戶端到這個服務(wù)器上，出于相同的原因后者的性能也很快降了下來，而前者負(fù)載過重的狀況也因此得到了緩解。這就是服務(wù)負(fù)載振蕩^[4]。
　　由于服務(wù)器負(fù)載振蕩的產(chǎn)生，會影響到服務(wù)器與客戶之間的通信。對于服務(wù)器，其負(fù)載會很不均衡，時而非常繁忙時而又十分空閑，從概率論的角度來看不利于資源的有效利用；對于客戶，其通信建立的時間會因為盲目地蜂擁搶占當(dāng)前最好的服務(wù)器而延長，這對于實時性要求高的通信服務(wù)是致命的。總之，振蕩問題不僅使得網(wǎng)絡(luò)資源的利用率極低，還使得選播通信的質(zhì)量難以保證。
2 負(fù)載均衡的實現(xiàn)
2.1等價子集的引入
　　多方蜂擁而上爭奪某個有限資源的范例屢見不鮮。通常的解決方法是分散各方的注意力，從所有資源供應(yīng)點中選出多個同樣高性能的點，組成一個等價子集ES(Equivalent Subcollection)，盡量把各方的需求引向子集中不同的資源點。該方法既可以保證各方都能及時得到最優(yōu)的資源，又可以避免資源點上頻繁的供需變換造成需求振蕩。
　　本文因此借用了上述的思想來解決負(fù)載振蕩問題，實現(xiàn)服務(wù)器負(fù)載的均衡。于是將等價子集的概念引入應(yīng)用層選播通信的服務(wù)器選擇策略之中，并對選播原型做了一些修改。因為服務(wù)器的選擇關(guān)系到選播通信的質(zhì)量，是選播通信中的關(guān)鍵技術(shù)。與原型相比最大的不同是：選播解析器不是直接為客戶選擇當(dāng)前最好的服務(wù)器，而是根據(jù)客戶需求提供多個當(dāng)前最好的服務(wù)器，再由客戶自己來選擇其中的一個，與其建立連接。具體過程如下：客戶端發(fā)送選播請求到選播解析器，當(dāng)選播解析器收到這個請求時，先把請求中的選播域名和服務(wù)器選擇標(biāo)準(zhǔn)分別提取出來，然后把選播域名映射為相應(yīng)的某個選播組，從其數(shù)據(jù)庫提取該選播組所有服務(wù)器地址以及相關(guān)性能參數(shù)，最后用客戶端提供的選擇標(biāo)準(zhǔn)來篩選出一組“最好”的服務(wù)器，組成基于性能參數(shù)的等價子集，并把首次選擇的結(jié)果返回給客戶端。當(dāng)選播應(yīng)答數(shù)據(jù)包到達(dá)客戶端時，再由客戶端進(jìn)行第二次篩選。因為子集中的服務(wù)器均可滿足客戶定義的標(biāo)準(zhǔn)，所以在客戶端把它們視為“等價”服務(wù)器，客戶端的應(yīng)用層程序會從其中隨機地選擇一個來建立連接。
2.2 選播組中等價子集的確定
　　由上分析可見，選播組中的等價子集的確定作為服務(wù)器選擇中的關(guān)鍵環(huán)節(jié)，在兩次篩選中起到承上啟下的作用。它是在選播解析器上首次篩選后得到的一個服務(wù)器集合，是選播組的一個子集。這個子集的確定雖然是在選播解析器上進(jìn)行，但選擇服務(wù)器的標(biāo)準(zhǔn)是客戶定義的，并和選播域名一起發(fā)送到選播解析器，選播解析器僅僅依據(jù)這個標(biāo)準(zhǔn)執(zhí)行操作，確定等價子集的范圍。
　　一般是通過判斷當(dāng)前選播組中服務(wù)器性能值是否滿足給定的條件來確定子集范圍，并在每次更新信息到選播解析器時，都會刷新所有服務(wù)器的性能值，并重新確定這個等價的子集，直到下一次刷新之前，子集中的服務(wù)器成員暫時恒定。
　　本文采用的是一種滯后的閥值法。它的基本思想是：假設(shè)子集成員的準(zhǔn)出門限值和準(zhǔn)入門限值分別是T_l和T_j(T_l≥T_j)。首先刷新各個服務(wù)器性能值；隨后找到性能最高的，即服務(wù)響應(yīng)時間最小的一個R_min；然后讓當(dāng)前子集中與這個最小值差距大于T_l的服務(wù)器退出子集(R_j-R_min>T_l)，而讓當(dāng)前子集外與這個最小值差距小于T_j的服務(wù)器加入子集(R_j-R_min≤T_j)；最后得到新的等價子集。這種方法的滯后效果表現(xiàn)在加入和退出子集都有一個保護(hù)帶，其寬度為T_l－T_j。該方法的優(yōu)勢在于選擇策略對服務(wù)器性能有一定的容忍性。
2.3 門限值的設(shè)定
　　通過上面的分析可以發(fā)現(xiàn)，準(zhǔn)出門限值和準(zhǔn)入門限值的設(shè)定直接影響到等價子集的大小，進(jìn)而影響到服務(wù)器的負(fù)載均衡程度以及選播通信的質(zhì)量。具體分析如下：
　　(1)當(dāng)準(zhǔn)出門限值T_l和準(zhǔn)入門限T_j值都很小時，等價子集的準(zhǔn)入條件顯得十分苛刻，而準(zhǔn)出條件卻很容易滿足，這時等價子集非常小，甚至只包含一個服務(wù)器。這是非常危險的情況，因為在這種情況下通常會導(dǎo)致服務(wù)器負(fù)載的振蕩。當(dāng)客戶端向選播解析器發(fā)送選播請求時，選播解析器當(dāng)然地會把當(dāng)前最好性能的服務(wù)器子集返回給每個客戶。然而，這個子集因為只有一個服務(wù)器，在這種情況下客戶實際上喪失了第二次選擇的機會，客戶端只能別無選擇地蜂擁到那個最好的服務(wù)器上等候服務(wù)，等待能快速與其建立通信連接。可是它們很快就意識到蜂擁而上的結(jié)果需要更長的等待時間。此時客戶端要么繼續(xù)等候，要么放棄轉(zhuǎn)而重新向選播解析器發(fā)送選播請求。實際上很多實時性強的客戶端都無法容忍這樣的延時產(chǎn)生，因而客戶與服務(wù)器之間的通信質(zhì)量同樣難以保證。
　　(2) 隨著T_l和T_j的增大，等價子集就可能包括不只一個性能最好的服務(wù)器，這樣就可以為客戶端提供多個“最好”服務(wù)器的選擇。當(dāng)客戶端有選播請求時，就可從中隨機地選出一個服務(wù)器，與之建立通信。客戶端重新獲得了隨機選擇的機會，兩次選擇都得以順利實現(xiàn)。因此可盡量避免蜂擁搶占服務(wù)器資源的情況發(fā)生，進(jìn)而緩解服務(wù)器負(fù)載的振蕩。
　　(3) 當(dāng)T_l和T_j都很大時，等價子集的準(zhǔn)出又顯得很困難，而準(zhǔn)入?yún)s變得很容易，這時等價子集就很大了，甚至包括整個選播組的服務(wù)器。這種情況下選播解析器對服務(wù)器的首次選擇幾乎失效了，僅保留客戶端的隨機選擇。這時選播通信中服務(wù)器的選擇完全是隨機的，選播系統(tǒng)幾乎無法保證引導(dǎo)客戶與最好的服務(wù)器通信，因而客戶與服務(wù)器之間的通信質(zhì)量同樣難以保證。
3 實驗及結(jié)果
　　運用上述的思想來解決服務(wù)器負(fù)載振蕩問題，在C++編程環(huán)境下模擬了選播通信過程，進(jìn)而實現(xiàn)服務(wù)器負(fù)載均衡。通過測試不同的準(zhǔn)出門限值和準(zhǔn)入門限值的組合對選播通信的質(zhì)量指標(biāo)―服務(wù)響應(yīng)時間的影響，試圖找到最優(yōu)的門限設(shè)置組合，使得服務(wù)響應(yīng)時間得到明顯改善，以此證明此時服務(wù)器負(fù)載的振蕩得到最大的緩解，以及服務(wù)器負(fù)載均衡的實現(xiàn)。

　　其次，為了更客觀地說明這個最佳門限組合對服務(wù)器負(fù)載振蕩狀況的改善，又進(jìn)行對比實驗，記錄在T_l與T_j的兩種不同組合下選播組中的某個服務(wù)器上每秒內(nèi)到達(dá)的客戶請求數(shù)，即代表該服務(wù)器的負(fù)載，如圖2、圖3所示。圖2是在T_l和T_j分別為0.1和0.05時的服務(wù)器負(fù)載狀況；而圖3則是T_l和T_j為最佳組合時的服務(wù)器負(fù)載狀況。與圖2相比，圖3中的服務(wù)器負(fù)載發(fā)生了顯著的變化。首先請求數(shù)的絕對值有明顯的降低，其次請求數(shù)的突變現(xiàn)象有明顯的減少。從整體來看，圖3中服務(wù)器負(fù)載的振蕩現(xiàn)象與圖2中的狀況相比得到了極大的緩解，負(fù)載趨于均衡，因而其性能更優(yōu)。
　　在應(yīng)用層選播通信中，服務(wù)器負(fù)載的振蕩現(xiàn)象不可小視，它嚴(yán)重地影響著通信的質(zhì)量。因此，從優(yōu)化服務(wù)器選擇策略角度出發(fā)，本文利用基于等價子集的服務(wù)器選擇策略，極大地消除了服務(wù)器負(fù)載振蕩對選播通信質(zhì)量的影響。仿真實驗證明，該策略較好地實現(xiàn)了選播服務(wù)器的負(fù)載均衡。
參考文獻(xiàn)
[1] DEERING S, HINDEN R. Internet protocol, version 6(IPv6). IETF RFC 2460, Dec. 1998.
[2] ?BHATTACHARJEE S, AMMAR M, ZEGURA E, et al.Application level anycasting. Tech. Rep.96-25, College of ?Computing, Georgia Institute of Technology,1996.
[3] ?PARTRIDGE C, MENDEZ T, MILLIKEN W. Host anycasting Service. RFC 1546, Nov. 1993.
[4] ?COLAJANNI M, YU P. Adaptive TTL schemes for load balancing of distributed web servers. Performance Evaluation Rev. ACMSIGMETRICS, 1997,25(2):36-42.
[5] ?VEIZADES J, GUTTMAN E, PERKINS C, et al. Service location protocol. RFC 2165, June 1997.
[6] ?ROSENBERG J, SCHULZRINNE H, SUTER B. Wide area ?network service location. Internet Draft(work in progress)? draft-ietf-svrloc-wasrv-Ol.txt, November 1997.
[7] ?CROVELLA M, CARTER R. Dynamic server selection in? the Internet. in Proc. 3rd IEEE Workshop Architecture and Implementation of High Performance Communication Subsystems (HPCS’95), Aug. 1995.