Klaus Herrmann
Abstract
Ambient Intelligence (AmI) is an IT concept by which mobile users shall be seamlessly supported in their everyday activities. This includes interactions with remote resources as well as with their current physical environment. We have developed the so-called Ad hoc Service Grid (ASG) infrastructure that supports the latter form of interactions. It allows operators to cover arbitrary locations with ambient services in a drop-and-deploy fashion. An ambient service may autonomously distribute (replicate and migrate) within an ASG network to optimize its availability, response times, and network usage. In this article, we propose a fully decentralized, dynamic, and adaptive service placement algorithm for AmI environments like the ASG. This algorithm achieves a coordinated global placement pattern that minimizes the communication costs without any central controller. It does not even require additional communication among the replicas. Moreover, placement patterns stabilize if no changes occur in the environment while replicas still retain their ability to adapt. Mechanisms for self-organized placement of services are very important for AmI environments in general since they allow for autonomous adaptations to dynamic changes and, thus, remove the need for manual (re)configuration of a running system. We present a detailed evaluation of the algorithm's performance and compare it with three other algorithms to show its competitiveness. Furthermore, we discuss how the desired self-organizing behavior emerges from the interactions of a few simple, local rules that govern the individual placement decisions. In order to do so, we give an in-depth analysis of a series of emergent effects that are not directly encoded into the placement algorithm but stem from its collective dynamics.
- Andrzejak, A., Graupner, S., Kotov, V., and Trinks, H. 2002. Algorithms for self-organization and adaptive service placement in dynamic distributed systems. Tech. rep. HPL-2002-259, HP Laboratories Palo Alto.Google Scholar
- Chandra, R., Qiu, L., Jain, K., and Mahdian, M. 2004. Optimizing the placement of integration points in multihop wireless networks. In Proceedings of the 12th IEEE International Conference on Network Protocols. Google ScholarDigital Library
- Choi, S. and Shavitt, Y. 2001. Placing servers for session-oriented services. Tech. rep. WUCS-2001-41, Department of Computer Science, Washington University.Google Scholar
- Coppens, J., Wauters, T., Turck, F. D., Dhoedt, B., and Demeester, P. 2005. Evaluation of replica placement and retrieval algorithms in self-organizing CDNs. In Proceeding of the IFIP/IEEE International Workshop on Self-Managed Systems & Services (SelfMan'05).Google Scholar
- Cornuéjols, G. P., Nemhauser, G. L., and Wolsey, L. A. 1990. The uncapacitated facility location problem. In Discrete Location Theory, Wiley, 119--171.Google Scholar
- Cronin, E., Jamin, S., Jin, C., Kurc, A., Raz, D., and Shavitt, Y. 2002. Constrained mirror placement on the Internet. IEEE J. Select. Areas Comm. 20, 7, 1369--1382. Google ScholarDigital Library
- Ducatel, K., Bogdanowicz, M., Scapolo, F., Leijten, J., and Burgelman, J.-C. 2001. Scenarios for ambient intelligence in 2010. Tech. rep., The IST Advisory Group (ISTAG).Google Scholar
- Herrmann, K. 2006. Self-Organizing infrastructures for ambient services. Ph.D. thesis, Berlin University of Technology.Google Scholar
- Herrmann, K. 2007a. Group anti-entropy—Achieving eventual consistency in mobile service environments. In Proceedings of the 8th IEEE International Conference on Mobile Data Management (MDM'07). IEEE Computer Society Press. Google ScholarDigital Library
- Herrmann, K. 2007b. Self-Organizing replica placement—A case study on emergence. In Proceedings of the 1st IEEE International Conference on Self-Adaptive and Self-Organizing Systems. IEEE Computer Society Press. Google ScholarDigital Library
- Herrmann, K., Geihs, K., and Mühl, G. 2004. Ad hoc service grid—A self-organizing infrastructure for mobile commerce. In Proceedings of the IFIP TC8 Working Conference on Mobile Information Systems (MOBIS'04). IFIP—International Federation for Information Processing, Springer-Verlag.Google Scholar
- Herrmann, K., Mühl, G., and Jaeger, M. A. 2005. A self-organizing lookup service for dynamic ambient services. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS'05). IEEE Computer Society Press, 707--716. Google ScholarDigital Library
- Jia, X., Li, D., Hu, X., and Du, D. 2001a. Optimal placement of Web proxies for replicated Web servers in the Internet. The Comput. J. 44, 5, 329--339.Google ScholarCross Ref
- Jia, X., Li, D., Hu, X., and Du, D. 2001b. Placement of read-write Web proxies in the Internet. In Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS'01). 687--690. Google ScholarDigital Library
- Kalpakis, K., Dasgupta, K., and Wolfson, O. 2001. Optimal placement of replicas in trees with read, write, and storage costs. IEEE Trans. Parallel Distrib. Syst. 12, 6, 628--637. Google ScholarDigital Library
- Kangasharju, J., Roberts, J., and Ross, K. W. 2002. Object replication strategies in content distribution networks. Comput. Comm. 25, 4, 367--383. Google ScholarDigital Library
- Karlsson, M. and Karamanolis, C. 2004. Choosing replica placement heuristics for wide-area systems. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS). 350--359. Google ScholarDigital Library
- Ko, B.-J. and Rubenstein, D. 2004. Distributed server replication in large scale networks. In Proceedings of the 14th International Workshop on Network and Operating Systems Support for Digital Audio and Video. ACM Press, New York, 127--132. Google ScholarDigital Library
- Kraemer, R. and Schwander, P. 2003. Bluetooth based wireless Internet applications for indoor hot spots: Experience of a successful experiment during CeBIT 2001. Comput. Netw. 41, 3, 303--312. Google ScholarDigital Library
- Lee, B.-D. and Weissman, J. B. 2001. Dynamic replica management in the service grid. In Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC'01). Google ScholarDigital Library
- Li, B., Deng, X., Golin, M. J., and Sohraby, K. 1998. On the optimal placement of Web proxies in the Internet. In Proceedings of the IFIP TC-6 8th International Conference on High Performance Networking (HPN'98). Kluwer Academic Publishers, 485--495. Google ScholarDigital Library
- Li, K. and Shen, H. 2004. Optimal placement of Web proxies for tree networks. In Proceedings of the IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'04). 479--486. Google ScholarDigital Library
- Liu, K. Y., Lui, J. C., and Zhang, Z.-L. 2004. Distributed algorithm for service replication in service overlay network. In Proceedings of the 3rd IEEE/IFIP TC-6 Networking Conference (Networking'04).Google Scholar
- Milnor, J. 1985. On the concept of attractor. Comm. Math. Phys. 99, 2, 177--195.Google ScholarCross Ref
- Perkins, C. E. and Bhagwat, P. 1994. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In Proceedings of the ACM SIGCOMM. 234--244. Google ScholarDigital Library
- Qiu, L., Padmanabhan, N. V., and Voelker, M. G. 2001. On the placement of Web server replicas. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). 12--22.Google Scholar
- Radoslavov, P., Govindan, R., and Estrin, D. 2001. Topology-Informed Internet replica placement. In Proceedings of the 6th International Workshop on Web Caching and Content Distribution.Google Scholar
- Repast. 2009. The RePast website. http://repast.sourceforge.net/.Google Scholar
- Szymaniak, M., Pierre, G., and van Steen, M. 2005. Latency-Driven replica placement. In Proceedings of the International Symposium on Applications and the Internet (SAINT). 399--405. Google ScholarDigital Library
- Tang, X., Chi, H., and Chanson, S. T. 2007. Optimal replica placement under TTL-based consistency. IEEE Trans. Parallel Distrib. Syst. 18, 3, 351--363. Google ScholarDigital Library
- Tenzakhti, F., Day, K., Ould-Khaoua, M., and Obadiat, M. S. 2004. Placement of Web proxies with server capacity constraints. In Proceedings of High Performance Computing Symposium (HPC'04). Kluwer Academic Publishers, 101--106.Google Scholar
- Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In Proceedings of the 15th ACM Symposium on Operating Systems Principles. ACM Press, New York, 172--182. Google ScholarDigital Library
- Weiser, M. 1991. The computer for the 21st century. Sci. Amer. 265, 66--75.Google Scholar
Index Terms
- Self-organized service placement in ambient intelligence environments
Recommendations
A survey of service composition in ambient intelligence environments
This article presents a comparative review of systems performing service composition in Ambient Intelligence Environments. Such environments should comply to ubiquitous or pervasive computing guidelines by sensing the user needs or wishes and offering ...
Architecting ambient intelligence systems
HCC '08: Proceedings of the 3rd ACM international workshop on Human-centered computingAmbient Intelligence (AmI) systems refer to ubiquitous computing with focus on human experiences. The AmI ideas are based on the premise that if environment around individuals can be personalized for the current needs of an individual, then the lives ...
Cognitive resource-aware unobtrusive service provisioning in ambient intelligence environments
Affect Aware Ubiquitous ComputingThe cognitive load placed on users by both the proactive and spontaneous provisioning of service functionality and by the physical activities performed in ambient intelligence environments can lead to the depletion of their mental resources. This paper ...
Reviews
David Gary Hill
Mobile users can benefit from application services that are provided within what is called an ad hoc services grid (ASG) network. An ASG is a network environment that may be limited to thousands of square meters. An ASG could be provided for temporary events, such as a trade show, but also for a more durable environment, such as a shopping mall or a hospital. In fact, a shopping mall may be the most striking example, as a wide range of services-such as a navigation service, a shopping guidance service, a product information service, and a reservation service-could be provided. Generally, two alternatives have been provided for an ASG: a wireless local area network (WLAN) or a cellular phone network. Unfortunately, both a WLAN access point to the Internet and a cellular mobile phone network have cost- and service-related issues for an ASG, as discussed in the paper. This paper explores an alternative method for providing access within an ASG network. This approach falls within the information technology (IT) concept of ambient intelligence (AmI), where mobile users are seamlessly connected to services within an ASG. This paper discusses a proposal for a fully decentralized, dynamic, and adaptive service placement algorithm for AmI environments. The discussion is precise and mathematical. That discussion builds and extends upon previous work on somewhat similar algorithms. In addition, the paper compares and contrasts other algorithms with the one proposed. The paper is meant to be read by specialists in the area. Those readers should find the discussion very useful. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments