The ubiquitous presence of distributed systems has drastically changed the way the world interacts, and impacted not only the economics and governance but also the society at large. It is therefore important for the architecture and infrastructure within the distributed environment to be continuously renewed in order to cope with the rapid changes driven by the innovative technologies. However, many problems in distributed computing are either of dynamic nature, large scale, NP complete, or a combination of any of these. In most cases, exact solutions are hardly found. As a result, a number of intelligent nature-inspired algorithms have been used recently, as these algorithms are capable of achieving good quality solutions in reasonable computational time. Among all the nature-inspired algorithms, evolutionary algorithms are considerably the most extensively applied ones. This chapter presents a systematic review of evolutionary algorithms employed to solve various problems related to distributed systems. The review is aimed at providing an insight of evolutionary approaches, in particular genetic algorithms and genetic programming, in solving problems in five different areas of network optimization: network topology, routing, protocol synthesis, network security, and parameter settings and configuration. Some interesting applications from these areas will be discussed in detail with the use of illustrative examples.
Top1. Introduction
Distributed systems are everywhere, from the World Wide Web, interconnected banking systems, distributed real-time automotive systems, distributed manufacturing systems, e-commerce systems, e-government systems, e-learning systems, to even mobile phone networks. They provide communication infrastructures, both world-wide through the Internet as well as locally by connecting different modules of computer devices or as body area networks. Virtually, every computer system today is either already part of a distributed system or may become one in the near future (Tanenbaum & van Steen, 2002).
These days, Internet technologies, protocols, and applications are growing into maturity and most of them have been widely researched. New forms of networks and distributed computing have also emerged in recent years. Amongst them, we can find wireless networks, sensor networks, smart home environments and other ubiquitous computing applications. Many aspects of these distributed systems are configurable or are dependent on parameter settings, e.g. topology, security, and routing. Finding good configurations and settings for distributed systems is therefore one of the key requirements of today’s Information Technology (IT) industry. Yet, many problems in distributed computing are either of dynamic nature, large scale, NP complete, or a combination of any of these. In most cases, exact solutions are hardly found in practice.
Evolutionary Computation (EC) is a family of the nature-inspired metaheuristic optimization methods. It is well-known for its ability to find satisfactory solutions within a reasonable amount of time, thus very suitable for solving problems of this nature. The study by Sinclair (1999a) reported that more than 120 papers had been published on work which employed EC for optimizing network topologies and dimension, node placement, routing, and wavelength or frequency allocation. The very comprehensive Master’s thesis of Kampstra (Kampstra, 2005; Kampstra et al., 2006) builds on this aforementioned study and classifies over 400 papers. In the year 2000 alone, two books (Corne, Oates, & Smith, 2000 and Pedrycz & Vasilakos, 2000b) have been published on the applications of EC to networking. Many summary papers have been published on this subject ever since (Şekercioğlu, Pitsilides, & Vasilakos, 2001; Pedrycz & Vasilakos, 2000a; Théraulaz & Bonabeau, 2000; Vasilakos, Anagnostakis, & Pedrycz, 2001; Alba & Chicano, 2006; Cortés Achedad et al., 2008). Figure 1 gives an overview of the different areas of applications tackled and the techniques applied by the papers listed in the technical report of Weise et al. (2008).
Figure 1. The number of papers analyzed in the technical report of Weise et al (2008), broken down to application area and optimization method.
Most of these summaries concentrate on giving an overview in the form of a more prosaic version of paper listings. In this chapter, our focus is to give a clear and detailed in-depth discussion of multiple examples of applications and also introduce the optimization algorithms utilized in them. On one hand, such descriptions make the subject more tangible for audiences rooted in only one of the two subject areas involved. On the other hand, we believe that describing some of the most interesting works in great detail will illustrate the ingenuity with which many researchers have found elegant and simple solutions based on evolutionary optimization to hard problems in distributed systems.