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

　　其次，為了更客觀地說(shuō)明這個(gè)最佳門(mén)限組合對(duì)服務(wù)器負(fù)載振蕩狀況的改善，又進(jìn)行對(duì)比實(shí)驗(yàn)，記錄在T_l與T_j的兩種不同組合下選播組中的某個(gè)服務(wù)器上每秒內(nèi)到達(dá)的客戶(hù)請(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.