Abstract
Motivated by trends in the industry towards transforming IT in large integrated service networks, this paper describes algorithms for the adaptive placement of “services” (as abstractions of collections of applications) in networks of “servers” (as abstractions for locations where services can be hosted). Networks comprised of interacting services as the foundation is also a vision pronounced by the Grid [9]. Manageability and “self-operation” of Grids is highly desirable. We analyze the requirements for algorithms one specific problem: the service placement problem. We discuss algorithms that neither require central control nor complete information about the system state. Algorithms are performed on a distributed overlay structure which summarizes load conditions in the underlying service network. The presented algorithms fulfill tasks of making initial placement decisions as well as initiating rearrangements when imbalance is detected. Presented algorithms have different characteristics regarding the tradeoff between accuracy (or quality) of a placement decision and its timeliness within which a decision can be made determining responsiveness.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andrzejak, A., Graupner, S., Kotov, V., Trinks, H.: Self-Organizing Control in Planetary-Scale Computing. In: IEEE International Symposium on Cluster Computing and the Grid (CCGrid), Berlin, May 21-24 (2002)
Andrzejak, A., Xu, Z.: Scalable, Efficient Range Queries for Grid Information Services. In: Second IEEE International Conference on Peer-to-Peer Computing (P2P 2002), Linköping, Sweden (September 5-7, 2002)
The Anthill Project. University of Bologna, http://www.cs.unibo.it/projects/anthill/
Bonabeau, E., Théraulaz, G.: Swarm Smarts. Scientific American, 72–79 (2000)
Brewer, E.A., Katz, R.H., Amir, E., Balakrishnan, H., Chawathe, Y., et al.: A Network Architecture for Heterogeneous Mobile Computing. IEEE Personal Communications Magazine (October 1998)
Dorigo, M., Maniezzo, V., Colorni, A.: The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B 26(1), 29–41 (1969)
El-Rewini, H., Lewis, T.G., Ali, H.H.: Task scheduling in parallel and distributed systems. PTR Prentice Hall, Englewood Cliffs (1994)
Estrin, D., Govindan, R., Heidemann, J., Kumar, S.: Next century challenges: Scalable coordination in sensor networks. In: Proc. MOBICOM, August 1999, pp. 263–270 (1999)
Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing Infrastructure, 2nd edn. Morgan Kaufman, San Francisco (2003)
Foster, I., Kesselman, C., Nick, J.M., Tuecke, S.: The Physiology of the Grid – An Open Grid Services Architecture for Distributed Systems Integration (May 2002), http://www.globus.org/research/papers/ogsa.pdf
The Globus Toolkit, http://www.globus.org/toolkit
Graupner, S., Kotov, V., Andrzejak, A., Trinks, H.: Service-Centric Organization of Globally Distributed Computing. IEEE Internet Computing, special issue on ”Grid Computing”, 36–43 (July/August 2003)
Hedetniemi, S.T., Hedetniemi, S.M., Liestman, A.L.: A survey of broadcasting and gossiping in communication networks. Networks 18, 319–349 (1988)
Hewlett-Packard company. Utility Data Center, http://www.hp.com/go/hpudc , http://www.hp.com/go/always-on
IBM, University of Berkeley. Oceano Project, http://www.research.ibm.com/oceanoproject
IBM. Autonomic Computing Manifesto, http://www.research.ibm.com/autonomic/manifesto
Kermarrec, A.M., Massoulie, L., Ganesh, A.: Reliable Probabilistic Communication in Large- Scale Information Dissemination Systems. Microsoft Research Technical Report MMSRTR- 2000-105 (October 2000)
Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. Cornell Technical Report 99-1776 (October 1999)
Kotov, V.: On Virtual Data Centers and Their Operating Environments, HP Labs Technical Report, HPL-2001-44 (March 2001)
Krauter, K., Buyya, R., Maheswaran, M.: A Taxonomy and Survey of Grid resource Management Systems. Software-Practice and Experience 2002 32(2), 135–164 (2002)
Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., et al.: OceanStore: An Architecture for Global-Scale Persistent Storage. In: ASPLOS 2000 (2000)
Luo, Q.Y., Hendry, P.G., Buchanan, J.T.: Comparison of different approaches for solving distributed constraint satisfaction problems. Research Report RR-93-74, Department of Computer Science, University of Strathclyde, Glasgow (1993)
Marcus, E., Stern, H.: Blueprints for High Availability: Designing Resilent Distributed Systems. John Wiley & Sons, Chichester (2000)
Montresor, A., Meling, H., Babaoğlu, Ö.: Messor: Load-balancing through a swarm of autonomous agents. In: Moro, G., Koubarakis, M. (eds.) AP2PC 2002. LNCS (LNAI), vol. 2530, pp. 125–137. Springer, Heidelberg (2003)
Platform Inc., http://www.platform.com
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A Scalable Content-Addressable Network. In: SIGCOMM 2001 (2001)
Rolia, J., Singhal, S., Friedrich, R.: Adaptive Data Centers. In: Proc. SSGRR 2000 Computer and eBusiness Conference, L’Aquila, Italy (August 2000)
Royer, E.M., Toh, C.-K.: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. IEEE Personal Communications Magazine (April 1999)
Schoonderwoerd, R., Holland, O., Bruten, J., Rothkrantz, L.: Ants for Load Balancing in elecommunications Networks. Adaptive Behavior 2, 169–207 (1996)
Sun Microsystems. The Sun Grid Engine, http://wwws.sun.com/gridware
Werger, B.B., Matarić, M.: From Insect to Internet: Situated Control for Networked Robot Teams. To appear in Annals of Mathematics and Artificial Intelligence
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Graupner, S., Andrzejak, A., Kotov, V., Trinks, H. (2005). Adaptive Service Placement Algorithms for Autonomous Service Networks. In: Brueckner, S.A., Di Marzo Serugendo, G., Karageorgos, A., Nagpal, R. (eds) Engineering Self-Organising Systems. ESOA 2004. Lecture Notes in Computer Science(), vol 3464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494676_19
Download citation
DOI: https://doi.org/10.1007/11494676_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26180-3
Online ISBN: 978-3-540-31901-6
eBook Packages: Computer ScienceComputer Science (R0)