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

?

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

　　其次,，為了更客觀地說(shuō)明這個(gè)最佳門限組合對(duì)服務(wù)器負(fù)載振蕩狀況的改善,，又進(jìn)行對(duì)比實(shí)驗(yàn)，記錄在T_l與T_j的兩種不同組合下選播組中的某個(gè)服務(wù)器上每秒內(nèi)到達(dá)的客戶請(qǐng)求數(shù),，即代表該服務(wù)器的負(fù)載,，如圖2、圖3所示,。圖2是在T_l和T_j分別為0.1和0.05時(shí)的服務(wù)器負(fù)載狀況,；而圖3則是T_l和T_j為最佳組合時(shí)的服務(wù)器負(fù)載狀況。與圖2相比,，圖3中的服務(wù)器負(fù)載發(fā)生了顯著的變化,。首先請(qǐng)求數(shù)的絕對(duì)值有明顯的降低，其次請(qǐng)求數(shù)的突變現(xiàn)象有明顯的減少,。從整體來(lái)看,，圖3中服務(wù)器負(fù)載的振蕩現(xiàn)象與圖2中的狀況相比得到了極大的緩解，負(fù)載趨于均衡,，因而其性能更優(yōu),。
　　在應(yīng)用層選播通信中，服務(wù)器負(fù)載的振蕩現(xiàn)象不可小視,，它嚴(yán)重地影響著通信的質(zhì)量,。因此，從優(yōu)化服務(wù)器選擇策略角度出發(fā),，本文利用基于等價(jià)子集的服務(wù)器選擇策略,，極大地消除了服務(wù)器負(fù)載振蕩對(duì)選播通信質(zhì)量的影響。仿真實(shí)驗(yàn)證明，該策略較好地實(shí)現(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.