摘　要： 选播" title="选播">选播通信是下一代网络中一种新的通信方式。其中应用层" title="应用层">应用层选播以其标准灵活、易于扩展和实现等优势，已成为近年来通信领域研究的热点。分析了受到普遍关注的应用层选播通信中服务器负载均衡问题，在此基础提出了基于等价子集" title="等价子集">等价子集的服务器选择策略，并且通过实验证明了该策略的有效性。
　　关键词： 选播 等价子集 负载均衡 服务器选择

　　选播通信是下一代网络中一种新的通信方式^[1-3]。由于这种选播方式可以分别在网络层和应用层实现，因此存在着两种选播通信模型：应用层选播和网络层选播。总的来说，网络层选播实现方法简单，但是存在许多缺陷。例如:需要修改路由器配置、不便于改善通信的无状态性、不支持用户对服务器选择的定义、在选择标准方面缺乏灵活性。而应用层选择的标准灵活、易于扩展和实现、不需要修改路由器。
　　目前,国内外对网络层选播的研究比较多，但由于网络层选播的局限性，许多研究者试图从应用层选播方面找到提高通信质量的突破口。网络层选播仅仅依靠网络自身的拓扑结构来选择最近的服务器(如路由器跳数最小)，而应用层选播依赖于外部的实体来为用户选择一个当前性能最好的服务器。对于用户来说，“最近”的服务器并不能保证是性能“最好”的，因此应用层选播对通信质量更有保证，并且服务器选择具有更多的灵活性和可扩展性。
　　但是在进一步的研究中发现，应用层选播仍然存在着一个不容忽视的问题，即服务器负载的振荡。因此，本文对应用层选播通信的关键技术服务器选择进行了深入分析，找到了实现服务器负载均衡的突破口，提出了基于等价子集的选择策略。在等价子集中包含了多个“最好”的服务器，这就为用户提供了更多的选择。当等价子集的规模发生变化时，可以得到不同服务器负载分布。而且从中发现：等价子集的准入、准出条件的不同组合可在不同程度上缓解服务器负载振荡，最终找到实现服务器负载均衡的最佳准入、准出条件的组合。
1 应用层选播中的服务器负载振荡问题
　　在应用层选播通信中，选播解析器" title="解析器">解析器通常会引导客户与当前性能最好的服务器进行连接，这样似乎已经非常完美了，客户似乎也可以享受到最好的通信服务了。然而应用层选播通信中一个潜在问题，即服务负载振荡就会随之产生。
　　当选播解析器发现某个服务器当前性能最好时，选播解析器可能会引导不只一个客户端" title="客户端">客户端与其建立连接。因而造成该服务器的负担过重，该服务器不能及时地响应所有客户请求，导致其性能的下降。而此时其他的服务器却因没有客户请求的到来而仍然处于空闲状态。当选播解析器又一次刷新所有服务器的性能参数时，又发现新的性能最好的服务器，它又会引导多个客户端到这个服务器上，出于相同的原因后者的性能也很快降了下来，而前者负载过重的状况也因此得到了缓解。这就是服务负载振荡^[4]。
　　由于服务器负载振荡的产生，会影响到服务器与客户之间的通信。对于服务器，其负载会很不均衡，时而非常繁忙时而又十分空闲，从概率论的角度来看不利于资源的有效利用；对于客户，其通信建立的时间会因为盲目地蜂拥抢占当前最好的服务器而延长，这对于实时性要求高的通信服务是致命的。总之，振荡问题不仅使得网络资源的利用率极低，还使得选播通信的质量难以保证。
2 负载均衡的实现
2.1等价子集的引入
　　多方蜂拥而上争夺某个有限资源的范例屡见不鲜。通常的解决方法是分散各方的注意力，从所有资源供应点中选出多个同样高性能的点，组成一个等价子集ES(Equivalent Subcollection)，尽量把各方的需求引向子集中不同的资源点。该方法既可以保证各方都能及时得到最优的资源，又可以避免资源点上频繁的供需变换造成需求振荡。
　　本文因此借用了上述的思想来解决负载振荡问题，实现服务器负载的均衡。于是将等价子集的概念引入应用层选播通信的服务器选择策略之中，并对选播原型做了一些修改。因为服务器的选择关系到选播通信的质量，是选播通信中的关键技术。与原型相比最大的不同是：选播解析器不是直接为客户选择当前最好的服务器，而是根据客户需求提供多个当前最好的服务器，再由客户自己来选择其中的一个，与其建立连接。具体过程如下：客户端发送选播请求到选播解析器，当选播解析器收到这个请求时，先把请求中的选播域名和服务器选择标准分别提取出来，然后把选播域名映射为相应的某个选播组，从其数据库提取该选播组所有服务器地址以及相关性能参数，最后用客户端提供的选择标准来筛选出一组“最好”的服务器，组成基于性能参数的等价子集，并把首次选择的结果返回给客户端。当选播应答数据包到达客户端时，再由客户端进行第二次筛选。因为子集中的服务器均可满足客户定义的标准，所以在客户端把它们视为“等价”服务器，客户端的应用层程序会从其中随机地选择一个来建立连接。
2.2 选播组中等价子集的确定
　　由上分析可见，选播组中的等价子集的确定作为服务器选择中的关键环节，在两次筛选中起到承上启下的作用。它是在选播解析器上首次筛选后得到的一个服务器集合，是选播组的一个子集。这个子集的确定虽然是在选播解析器上进行，但选择服务器的标准是客户定义的，并和选播域名一起发送到选播解析器，选播解析器仅仅依据这个标准执行操作，确定等价子集的范围。
　　一般是通过判断当前选播组中服务器性能值是否满足给定的条件来确定子集范围，并在每次更新信息到选播解析器时，都会刷新所有服务器的性能值，并重新确定这个等价的子集，直到下一次刷新之前，子集中的服务器成员暂时恒定。
　　本文采用的是一种滞后的阀值法。它的基本思想是：假设子集成员的准出门限值和准入门限值分别是T_l和T_j(T_l≥T_j)。首先刷新各个服务器性能值；随后找到性能最高的，即服务响应时间最小的一个R_min；然后让当前子集中与这个最小值差距大于T_l的服务器退出子集(R_j-R_min>T_l)，而让当前子集外与这个最小值差距小于T_j的服务器加入子集(R_j-R_min≤T_j)；最后得到新的等价子集。这种方法的滞后效果表现在加入和退出子集都有一个保护带，其宽度为T_l－T_j。该方法的优势在于选择策略对服务器性能有一定的容忍性。
2.3 门限值的设定
　　通过上面的分析可以发现，准出门限值和准入门限值的设定直接影响到等价子集的大小，进而影响到服务器的负载均衡程度以及选播通信的质量。具体分析如下：
　　(1)当准出门限值T_l和准入门限T_j值都很小时，等价子集的准入条件显得十分苛刻，而准出条件却很容易满足，这时等价子集非常小，甚至只包含一个服务器。这是非常危险的情况，因为在这种情况下通常会导致服务器负载的振荡。当客户端向选播解析器发送选播请求时，选播解析器当然地会把当前最好性能的服务器子集返回给每个客户。然而，这个子集因为只有一个服务器，在这种情况下客户实际上丧失了第二次选择的机会，客户端只能别无选择地蜂拥到那个最好的服务器上等候服务，等待能快速与其建立通信连接。可是它们很快就意识到蜂拥而上的结果需要更长的等待时间。此时客户端要么继续等候，要么放弃转而重新向选播解析器发送选播请求。实际上很多实时性强的客户端都无法容忍这样的延时产生，因而客户与服务器之间的通信质量同样难以保证。
　　(2) 随着T_l和T_j的增大，等价子集就可能包括不只一个性能最好的服务器，这样就可以为客户端提供多个“最好”服务器的选择。当客户端有选播请求时，就可从中随机地选出一个服务器，与之建立通信。客户端重新获得了随机选择的机会，两次选择都得以顺利实现。因此可尽量避免蜂拥抢占服务器资源的情况发生，进而缓解服务器负载的振荡。
　　(3) 当T_l和T_j都很大时，等价子集的准出又显得很困难，而准入却变得很容易，这时等价子集就很大了，甚至包括整个选播组的服务器。这种情况下选播解析器对服务器的首次选择几乎失效了，仅保留客户端的随机选择。这时选播通信中服务器的选择完全是随机的，选播系统几乎无法保证引导客户与最好的服务器通信，因而客户与服务器之间的通信质量同样难以保证。
3 实验及结果
　　运用上述的思想来解决服务器负载振荡问题，在C++编程环境下模拟了选播通信过程，进而实现服务器负载均衡。通过测试不同的准出门限值和准入门限值的组合对选播通信的质量指标―服务响应时间的影响，试图找到最优的门限设置组合，使得服务响应时间得到明显改善，以此证明此时服务器负载的振荡得到最大的缓解，以及服务器负载均衡的实现。

　　其次，为了更客观地说明这个最佳门限组合对服务器负载振荡状况的改善，又进行对比实验，记录在T_l与T_j的两种不同组合下选播组中的某个服务器上每秒内到达的客户请求数，即代表该服务器的负载，如图2、图3所示。图2是在T_l和T_j分别为0.1和0.05时的服务器负载状况；而图3则是T_l和T_j为最佳组合时的服务器负载状况。与图2相比，图3中的服务器负载发生了显著的变化。首先请求数的绝对值有明显的降低，其次请求数的突变现象有明显的减少。从整体来看，图3中服务器负载的振荡现象与图2中的状况相比得到了极大的缓解，负载趋于均衡，因而其性能更优。
　　在应用层选播通信中，服务器负载的振荡现象不可小视，它严重地影响着通信的质量。因此，从优化服务器选择策略角度出发，本文利用基于等价子集的服务器选择策略，极大地消除了服务器负载振荡对选播通信质量的影响。仿真实验证明，该策略较好地实现了选播服务器的负载均衡。
参考文献
[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.