An approximation-based load-balancing algorithm with admission control for cluster web servers with dynamic workloads

The growth of web-based applications in business and e-commerce is building up demands for high performance web servers for better throughputs and lower user-perceived latency. These demands are leading to a widespread substitution of powerful single servers by robust newcomers, cluster web servers, in many enterprise companies. In this respect the load-balancing algorithms play an important role in boosting the performance of cluster servers. The previous load-balancing algorithms which were designed for the handling of static contents in web services suffer from significant performance degradation under dynamic and database-driven workloads. Regarding this, we propose an approximation-based load-balancing algorithm with admission control for cluster-based web servers in this study. Since it is difficult to accurately determine the loads of web servers through feedbacks from distributed agents in web servers, we propose an analytical model of a web server to estimate the web servers’ loads. To achieve this, the algorithm classifies requests based on their service times and track numbers of outstanding requests for each class of each web server node and also based on their resource demands to dynamically estimate the loads of each node. For the error handling of the model a proportional integral (PI) controller from control theory is used. Then the estimated available capacity of each web server is used for load balancing and admission control decisions. The implementation results with a standard benchmark confirm the effectiveness of the proposed scheme, which improves both the mean response time and the throughput of the cluster compared to rival load-balancing algorithms, and also avoids situations in which the cluster is overloaded, even when the request rates are beyond the cluster capacity.     

基于集群的Web服务器负载平衡算法研究

随着互联网访问量的激增,基于集群的Web服务器成为发展趋势,有效、公平的负载平衡直接决定系统的整体性能。建立BCMP排队预测模型,通过控制回路反馈动态调整预测因子,最终利用基于概率预测的PPLB算法平衡分配请求。仿真结果表明,该算法较传统负载平衡算法具有更高的效率和实用性。     

基于内容的Web服务器动态负载均衡算法

研究基于内容的Web服务器动态负载均衡算法,将其中的请求类别对应的服务器数与PICK-KX算法中的K值相结合,提出一种新的算法。模拟实验结果表明,该算法可以在较高的缓存命中率和较小的服务器负载计算负荷之间取得良好的平衡。在极限情况下,经该算法均衡后的集群服务器可以返回更多的请求响应。     

集群服务器在混合请求下的负载均衡优化算法

针对Web集群服务器在处理分配混合页面访问任务时开环负载均衡算法导致局部服务器负载偏高而降低系统效率的问题,建立了一类基于动态调节的闭环负载分配策略。根据服务器处理Web访问页面类型的特点,建立静态页面与动态页面混合处理的负载量模型,形成处理不同服务请求与负载均衡的内在动态映射关系,以此优化静态页面缓存与调用方式,并基于服务器负载率动态预测和均衡指标,采用负载率偏差最小的任务权重最优分配模型,确定服务器集群的最优任务权重,实现了服务器集群处理混合页面访问的负载均衡分配策略和算法。仿真结果验证了负载均衡算法的正确性和有效性,可以达到更好的负载均衡效果。     

一种适合P2P MMOG的动态负载均衡算法*

P2P MMOG中常采用多台服务器集群的结构来处理玩家的请求,但是,玩家在游戏中的走动、打斗常常使某些服务器超载,因此网络游戏系统应该具有一定的负载均衡能力,即能以较高的性能动态地将负载从超载节点迁移到轻载节点中。提出了一种在游戏动态运行过程中与系统空闲时的一种动态负载均衡算法。实验表明,该算法能够有效地均衡负载和提高系统性能。     

Predictive and content-aware load balancing algorithm for peer-service area based IPTV networks

Load balancing is a crucial factor in IPTV delivery networks. Load balancing aims at utilizing the resources efficiently, maximizing the throughput, and minimizing the request rejection rate. The peer-service area is the recent architecture for IPTV delivery networks that overcomes the flaws of the previous architectures. However, it still suffers from the load imbalance problem. This paper investigates the load imbalance problem, and tries to augment the peer-service area architecture to overcome this problem. To achieve the load balancing over the proposed architecture, we suggest a new load-balancing algorithm that considers both the expected and the current load of both contents and servers. The proposed load-balancing algorithm consists of two stages. The first stage is the contents replication according to their expected load, while the second stage is the content-aware request distribution. To test the effectiveness of the proposed algorithm, we have compared it with both the traditional Round Robin algorithm and Cho algorithm. The experimental results depict that the proposed algorithm outperforms the two other algorithms in terms of load balance, throughput, and request rejection rate.     

一种改进的集群动态负载均衡算法

在集群系统的研究中,负载均衡算法是一个重要的方向,因为它关系到多台服务器在整合成一个集群系统后能否很好地相互协作,以更好地完成用户交予的任务。为实现上述目的,本文在分析已有的负载均衡算法基础上,提出一种改进的能够实时收集服务器负载指标,进而动态地计算出服务器在分配用户连接中的权重的方法。测试结果表明,该方法能够有效地防止服务器倾斜,达到良好的负载均衡效果。     

嵌入式Web服务器的负载均衡技术的研究

为提高嵌入式Web服务器的处理能力,克服其计算和存储资源有限的缺点,增强容错性,在分析了嵌入式Web服务器现状及发展趋势的基础上,结合传统Web服务器负载均衡技术,探讨了基于嵌入式Web服务器的负载均衡技术,设计了适合于嵌入式Web服务器的基于访问请求优先级的最少连接数算法,并给出了工作流程,实验表明系统达到了对紧急请求优先、快速、准确执行的目标.     

云数据中心基于负载权重的负载均衡调度算法

针对现有云数据中心的多维资源利用不均衡问题,提出基于资源负载权重的动态多资源负载均衡调度算法。算法结合服务器各维度资源动态负载情况,构造层次分析法（AHP）判断矩阵来处理多维资源对于负载均衡影响权重大小,在此基础上综合考虑任务资源需求,将任务放置到合适服务器来改善资源利用,实现资源间负载均衡。平台仿真显示新算法可有效提高利用率低的资源的利用效率,在提高整体资源利用率、降低资源间负载不均衡率方面有优势。     

基于URL索引划分的Web内容自适应算法

Web集群服务的请求分配算法大多使用Hash方法对请求URL进行散列,并按一定规则对请求内容进行负载均衡调度.提出了一种基于URL词典排序及全部URL按其词典序列分为k*n个集合的URLALLOC算法.该算法通过对URL进行词典序排序并将全部URL按其词典序列分为k*n个集合,依访问流量排序及分段互补等一系列方法将Web负载尽可能均匀地分布到多个后端服务器中.仿真实验结果表明:URLALLOC算法比现有的URL散列方法具有更好的负载均衡能力.     

多服务副本下的一种分布式负载均衡路径算法

目前的服务器负载均衡算法多只针对选择一台服务器提供所有服务,不能满足服务组合需要选择一组服务副本的情况。针对整个集群系统拥有多台服务器,每台服务器具有多个服务副本的服务查找与组合的路径选择和负载均衡问题,提出了一种基于节点负载变化的分布式负载均衡路径算法LCNA（Load Changes of Notes-considered Algorithm）。LCNA算法以基于DHT的路由算法来建立集群系统的服务列表和路由转发列表,以服务器节点的动态负载变化作为测度进行服务节点的选择。实验结果表明,LCNA算法能有效提高多服务副本环境下应用的整体性能,具有良好的负载均衡效果。     

Energy-Efficient Redundant Execution of Processes in a Fault-Tolerant Cluster of Servers

This paper investigates into fault tolerance of cluster of servers and their energy efficiency to realize a reliable and energy aware server cluster system. A client issues a request to one server in a server cluster and the server sends a reply to the client in information systems. Once the server stops by fault, the client does not receive a reply of the request. Even if the request is performed on another server on detection of fault of the server, some QoS requirements like response time may not be satisfied. Hence, each request has to be redundantly performed on multiple servers to be tolerant of server faults. The redundant power consumption laxity-based (RPCLB) algorithm is discussed where multiple servers are selected to redundantly and energy-efficiently perform a request process in our previous studies. Since each application process is redundantly performed on more than one server, the larger amount of electric power is consumed. In this paper, we propose a novel and improved RPCLB (IRPCLB) algorithm to reduce the power consumption of servers, where once a process successfully terminates on one server, meaningless redundant processes are forced to terminate on the other servers. In the evaluation, we show the total power consumption of servers and total execution time of processes are reduced in homogeneous and heterogeneous types of clusters by the IRPCLB algorithm than the RPCLB and RR algorithms.     

Tulip: A New Hash Based Cooperative Web Caching Architecture

With the exponential growth of WWW traffic, web proxy caching becomes a critical technique for Internet web services. Well-organized proxy caching systems with multiple servers can greatly reduce the user perceived latency and decrease the network bandwidth consumption. Thus, many research papers focused on improving web caching performance with the efficient coordination algorithms among multiple servers. Hash based algorithm is the most widely used server coordination mechanism, however, there's still a lot of technical issues need to be addressed. In this paper, we propose a new hash based web caching architecture, Tulip. Tulip aggregates web objects that are likely to be accessed together into object clusters and uses object clusters as the primary access units. Tulip extends the locality-based algorithm in UCFS to hash based web proxy systems and proposes a simple algorithm to reduce the data grouping overhead. It takes into consideration the access speed dispatch between memory and disk and replaces expensive small disk I/O with less large ones. In case a client request cannot be fulfilled by the server in the memory, the system fetches the whole cluster which contains the required object into memory, the future requests for other objects in the same cluster can be satisfied directly from memory and slow disk I/Os are avoided. It also introduces a simple and efficient data dupllication algorithm, few maintenance work need to be done in case of server join/leave or server failure. Along with the local caching strategy, Tulip achieves better fault tolerance and load balance capability with the minimal cost. Our simulation results show Tulip has better performance than previous approaches.     

针对Web服务的动态负载平衡模型

Web服务是一项非常重要的网络技术,如何提高其的性能是一个热点问题。为了增强Web服务系统的容错性和扩展性,将负载平衡技术应用到Web服务领域。报告了负载平衡算法的现状,分析了Web服务对负载平衡的要求,给出了一个针对Web服务的动态负载平衡模型,介绍了动态调整模型中的服务耗费值、负载阀值和服务器权重的方法,及过载保护的方法。     

Design and implementation of an efficient web cluster with content-based request distribution and file caching

We have implemented an efficient and scalable web cluster named LVS-CAD/FC (i.e. LVS with Content-Aware Dispatching and File Caching). In LVS-CAD/FC, a kernel-level one-way content-aware web switch based on TCP Rebuilding is implemented to examine and distribute the HTTP requests from clients to web servers, and the fast Multiple TCP Rebuilding is implemented to efficiently support persistent connection. Besides, a file-based web cache stores a small set of the most frequently accessed web files in server RAM to reduce disk I/Os and a light-weight redirect method is developed to efficiently redirect requests to this cache. In this paper, we have further proposed new policies related to content-based workload-aware request distribution, in which the web switch considers the content of requests and workload characterization in request dispatching. In particular, web files with more access frequencies would be duplicated in more servers’ file-based caches, such that hot web files can be served by more servers. Our goals are to improve cluster performance by obtaining better memory utilization and increasing the cache hit rates while achieving load balancing among servers. Experimental results of practical implementation on Linux show that LVS-CAD/FC is efficient and scales well. Besides, LVS-CAD/FC with the proposed policies can achieve 66.89% better performance than the Linux Virtual Server with a content-blind web switch.     

LVS负载均衡调度算法的改进及实现

采用服务器集群架构提供服务成为互联网服务业中普遍采用的策略,目前使用得比较广泛的网络负载均衡集群是Linux虚拟服务器集群。优秀的负载均衡算法可以将用户请求合理地分配到集群中的真实服务器中．提高集群中服务器的利用率和集群系统的吞吐量。针对LVS默认算法WLC算法的不足之处,对WLC算法进行改进．设计并实现一种基于反馈式的负载均衡算法。实验证明,改进算法能够增大集群的吞吐量,提升集群的整体性能。     

基于Nginx负载均衡的动态改进算法

随着过去几十年互联网服务的指数增长,各大网站的访问量急剧上升。海量的用户请求使得热门网站的网络请求率可能在几秒钟内大规模增加。一旦服务器承受不住这样的高并发请求,由此带来的网络拥塞和延迟会极大地影响用户体验。负载均衡是高可用网络基础架构的关键组件,通过在后端引入一个负载均衡器,将工作负载分布到多个服务器来缓解海量并发请求对服务器造成的巨大压力,提高后端服务器和数据库的性能以及可靠性。而Nginx作为一款高性能的HTTP和反向代理服务器,正越来越多地应用到实践中。文中将分析Nginx服务器负载均衡的体系架构,研究默认的加权轮询算法,并提出一种改进后的动态负载均衡算法,实时收集负载信息,重新计算并分配权值。通过实验测试,对比不同算法下的负载均衡性能,改进后的算法能有效提高服务器集群的性能。     

Web服务器性能评测

Web服务器性能评测是一种理解Web服务器对不同负载反应能力的方法，它对Web服务器的容量规划和性能增强有很大的帮助。讨论了Web服务器性能评测的原理、方法、难点及解决方案，介绍了基于Web负载的特点、ON／OFF源模型及浏览器／服务器体系结构，开发了一个Web服务器性能评测工具－WSBench。WSBench产生渐近自相似的HTTP请求序列，从静态文档、动态文档（没有数据库存取）、动态文档（有数据库存取）及前三者根据Zipf法则的组合4个层次来评测Web服务器的性能。性能测试结果表现为每秒请求数、每秒字节数和往返时间3个指标。最后讨论了Web服务器性能问题及使用WSBench测得的指标来建议Web服务器性能增强可以采用的方法。     

High-Performance Resource Allocation and Request Redirection Algorithms for Web Clusters

With increasing richness in features such as personalization of content, Web applications are becoming increasingly complex and hence compute intensive. Traditional approaches for improving performance of static content Web sites have been based on the assumption that static content such as images are network intensive. However, these methods are not applicable to the dynamic content applications which are more compute intensive than static content. This paper proposes a suite of algorithms which jointly optimize the performance of dynamic content applications by reducing the client access times while also minimizing the resource utilization. A server migration algorithm allocates servers on-demand within a cluster such that the client access times are not affected even under sudden overload conditions. Further, a server selection mechanism enables statistical multiplexing of resources across clusters by redirecting requests away from overloaded clusters. We also propose a cluster decision algorithm which decides whether to migrate in additional servers at the local cluster or redirect requests remotely under different workload conditions. Through a combination of analytical modeling, trace-driven simulation over traces from large e-commerce sites and testbed implementation, we explore the performance savings achieved by the proposed algorithms.