Abstract

Contents

Introduction. Theme urgency

The extensive growth of Internet traffic leads to an ever increasing number of requests to the popular sites, which creates traffic going far beyond the limits of a single server. In this connection there may be long delays to users information access. Changing website infrastructure on the local cluster does not provide a complete solution of this problem, as the channel between the cluster and the global network can be a bottleneck of this infrastructure. More effective solution is to distribute the servers geographically so that they are located on separate networks. The role of load balancing when using such an architecture increases because the request object can do redirection based on both network and server load, and on the basis of the distance between clients and servers.

2. Goal and tasks of the research

The main purpose of this study is to improve the quality of the existing load balancing algorithms.

Main tasks of the research:

  1. Analysis of the existing load balancing algorithms in global networks. Setting goals and objectives of the modernization.
  2. Mathematical modeling of geographically distributed servers and the existing load balancing algorithms. Analysis of parameters, definition of deficiencies.
  3. Modernization of the algorithms to achieve this goal.
  4. Simulation and verification of the results.
  5. Research and analysis of scientific results.

Research object: telecommunications networks with geographically distributed replica servers.

Research subject: methods for improving efficiency of load balancing algorithms.

2. Research methods of load balancing in wide area networks

Load balancing defines which server is better at serving a given client request. The concept of "better" in this case is defined by the load balancing metric.

The main purpose of measures of scaling up the web server is to minimize delay which is perceived by the user. This delay in its turn consists of two components: the delay introduced by the network and the delay introduced by the server.

The representative of the first component may be the time Round Trip Time (RTT). The second component is determined by the server load. Thus to achieve this goal there should be applied either integrated or hierarchical metric (on the first level one must select from the server’ pool's load, on the second level from the selected servers one must choose a specific parameter of RTT).

The task of distributing the requests is supposed to break into two parts: the development of requesting policies and the selection of referral mechanism.

The policy is actually the algorithm that performs the selection of a particular server, and the mechanism is the object that informs the client about the selected server.

Classification of policies:

  • Adaptive — track the current state (user's information: intensity and location of the user query, status of servers and network)
  • Nonadaptive — choose a replica without the condition monitoring system. (RR, random selection of the server).

An adaptive policy will be used in the developed algorithm, as minimization of delay on the basis of non-adaptive policy is not possible (not guaranteed).

In [4] was given the classification of the mechanisms of routing client requests to the server site. The criterion for selection of different types of distributed Web-server’ architectures is the object that implements the distribution of user queries.

There are mechanisms for the following types:

  • DNS-based
  • Dispatcher-based
  • Sever-based

In DNS-based methods the requests distribution is made by authorized DNS-server of domain. Transparency in architecture for the user is implemented at the application level of Open System Interconnection (OSI) model — the site has a URL.

The principle of the method based on DNS

Figure 1 – The principle of the DNS-based method
(Animation: 5 frames, 7 cycles of repetition, 129 KB)

However monitoring for requests distribution from the DNS is limited as between the client and the DNS-server, performing balancing, there are a large number of intermediate DNS-servers, which can cache the DNS-records in order to reduce the amount of traffic. The control by managing of the DNS server balancing is weak because if it sets the TTL close to zero the number of intermediate servers will ignore this value.

In the framework of mechanisms on the basis of DNS there are algorithms with constant TTL, which in connection with the described problem and exercise use the control over a very small fraction of queries and algorithms with dynamic TTL value [2], performing apart from balancing the selection of the TTL for each record (the less TTL value can be assigned to requests from domains with a large number of users and queries sent to the less powerful server). The algorithms of the first type in global networks are not used opposed to the dynamic ones, which are easily scalable because they require the information that can be dynamically obtained by the DNS-server (the frequency of requests for each domain, and the productivity of each server).

However, these methods when selecting a server do not take into account the distance between the client and the server. Dynamic assignment policy TTL in conjunction with the mechanism of calculating of the distance to the customer is able to provide the better performance.

Dispatcher methods implement transparency to the user at the network level, to each cluster is assigned a virtual IP-address which is the address of the specialized device carrying out routing of the requests — dispatcher.

The server methods use a two-tiered mechanism for balancing queries: they were originally distributed across multiple servers using the DNS-server-based methods like DNS; then each server can redirect the received request to any other server. This approach allows to overcome the most of restrictions imposed on the approaches based on the DNS. Redirection of servers is realized by the same mechanisms of routing as in the dispatching approach.

Conclusions

At the moment there was made the classification of existing approaches to load balancing, also there were listed all the disadvantages of each method. The methods of the DNS-based and the server possess the best scalability. For use in a wide area network the object performing balancing must take into account not only the download servers, but also the load of communication channels and the distance between the client and the server. Thus complex metric should be used when selecting a particular server.

The resulting study information will be considered when implementing a new algorithm for load balancing.

Important note

This master's work is not completed yet. Final completion: December 2012. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Colajanni M., Yu P.S., Cardellini V., “Dynamic load balancing in geographically distributed heterogeneous Web–servers”, Amsterdam, The Netherlands, May 1998.
  2. Sivasubramanian S., Szymaniak M., Pierre G., “Replication for web hosting systems,” ACM Computing Surveys, vol. 36, no. 3, no. 3, pp. 291–334, 2004.
  3. Pathan M. and Buyya R. A Taxonomy of CDNs. Content Delivery Networks, pages 33–78, 2008.
  4. Mulerikkal J. and Khalil I. An architecture for distributed content delivery network. In Proc. IEEE International Conference on Networks, pages 359–364, 2007.
  5. Theilmann W., Rothermel K. Dynamic Distance Maps of the Internet. In Proceedings of the 2000 IEEE INFOCOM Conference, Tel Aviv, Israel, Mar. 2000 [Электронный ресурс]. — Режим доступа: http://elib.uni-stuttgart.de/opus/volltexte/1999/494/pdf/TR-1999-08.pdf.
  6. Francis P., Jamin S., Jin C., Jin Y., Raz D., Shavitt Y., and Zhang L. IDMaps: A global Internet host distance estimation service. IEEE/ACM Transactions on Networking, Oct. 2001.
  7. Banga G., Druschel P. Measuring the capacity of a Web server under realisitc loads. World Wide Web Journal, 2, May 1999.
  8. Hunt G., Nahum E., Tracey J. Enabling content–based load distribution for scalable services. / G. Hunt, E. Nahum, J. Tracey. — IBM T.J. Watson Research Center, 1997. — Technical report.
  9. Тао Чжоу. Системы балансировки нагрузки web–серверов. — Windows magazine, #03/2000.
  10. Kevin Delgadillo. Cisco DistributedDirector. — Cisco Systems, Inc., 1999. — Technical report.
  11. Chou W., “Inside SSL: The Secure Sockets Layer Protocol”, IT Pro, July/August 2002, pp. 47–52, published by the IEEE Computer Society.
  12. Таненбаум Э., Ван Стеен М. Распределённые системы. Принципы и парадигмы. — СПб.: Питер, 2003.
  13. Casalicchio E., Cardellini V., Colajanni M., Content-aware dispatching algorithms for cluster-based web servers, Cluster Computing, vol. 5, no. 1, pp. 65–74, 2002.
  14. Петренко А.С., Червинский В.В. Исследование методов балансировки нагрузки в глобальных сетях. Автоматизація технологічних об’єктів та процесів. Пошук молодих. Збірник наукових праць ХІI науково-технічної конференції аспірантів та студентів в м. Донецьку 17–20 квітня 2012 р. — Донецьк, ДонНТУ, 2012. — с. 79–80.