Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp lấy cảm hứng từ sinh học cho việc triển khai phân tán dịch vụ
Tóm tắt
Chúng tôi xem xét vấn đề đã được biết đến rộng rãi về việc phân bổ các thành phần phần mềm cho các tài nguyên tính toán (nút) trong một mạng lưới, với các ràng buộc về tài nguyên hạ tầng và yêu cầu chất lượng dịch vụ của các thành phần cần phân bổ cho các nút. Vấn đề này có nhiều khía cạnh và đã được nghiên cứu rộng rãi trong tài liệu. Việc giải quyết vấn đề này trở nên đặc biệt phức tạp khi có sự biến động và quy mô lớn. Thông thường, cần phải sử dụng các phương pháp heuristics. Trong bài báo này, chúng tôi trình bày một loại heuristics mới để giải quyết vấn đề này. Đặc điểm phân biệt của cách tiếp cận của chúng tôi là một khuôn khổ tối ưu hóa phi tập trung nhằm tìm ra các ánh xạ gần tối ưu trong thời gian hợp lý và cho quy mô lớn. Ba hình thức khác nhau của vấn đề được khám phá thông qua các mô phỏng. Đối với một ví dụ cụ thể, chúng tôi cũng cung cấp các giải pháp chính xác và cho thấy rằng kỹ thuật của chúng tôi có khả năng tìm ra các giải pháp gần tối ưu với độ biến động thấp. Trong ví dụ lớn nhất, một kịch bản điện toán đám mây công cộng - tư nhân được sử dụng, trong đó các đám mây khác nhau có liên quan đến chi phí tài chính, và chúng tôi cho thấy rằng cách tiếp cận của chúng tôi có khả năng cân bằng tải như mong đợi cho một kịch bản như vậy.
Từ khóa
#Phân bố dịch vụ #Heuristics #Tối ưu hóa phi tập trung #Điện toán đám mây #Chất lượng dịch vụ.Tài liệu tham khảo
Albrecht, J., Oppenheimer, D., Vahdat, A. and Patterson, D. A., “Design and implementation trade-offs for wide-area resource discovery,” ACM Trans. on Internet Technology, 8, 4, Sep. 2008.
Amazon Elastic Compute Cloud, Last checked: Aug 19, 2010. http://aws.amazon.com/ec2
Bastarrica, M. C., et al., “A Binary Integer Programming Model for Optimal Object Distribution,” in 2nd Int'l. Conf. on Principles of Distributed Systems, Amiens, Dec. 1998.
Clark, C. et al., “Live migration of virtual machines,” in 2nd USENIX Symp. on Networked Systems Design and Implementation, May 2005.
Csorba, M. J. and Heegaard, P. E., “Swarm intelligence heuristics for component deployment,” in 16th Eunice Int'l Workshop and IFIP WG6.6 Workshop, LNCS 6164, Trondheim, June 2010.
Csorba, M. J., Heegaard, P. E. and Herrmann, P., “Cost-efficient deployment of collaborating components,” in 8th IFIP Int'l Conf. on Distributed Applications and Interoperable Systems, Oslo, June 2008.
Csorba, M. J., Heegaard, P. E. and Herrmann, P., “Adaptable model-based component deployment guided by artificial ants,” in 2nd Int'l Conf. on Autonomic Computing and Communication Systems, Sep. 2008.
Csorba, M. J., Meling, H. and Heegaard, P. E., “Laying pheromone trails for balanced and dependable component mappings,” in 4th Int'l Workshop on Self-Organizing Systems, LNCS 5918, Zurich, Dec. 2009.
Csorba, M. J., Meling, H. and Heegaard, P. E., “Ant system for service deployment in private and public clouds,” in 2nd Workshop on Bio-Inspired Algorithms for Distributed Systems, Washington, DC, June 2010.
Csorba, M. J., Meling, H., Heegaard, P. E. and Herrmann, P., “Foraging for better deployment of replicated service components,” in 9th Int'l Conf. on Distributed Applications and Interoperable Systems, LNCS 5523, Lisbon, June 2009.
Dorigo, M., et al., “The Ant System: Optimization by a colony of cooperating agents”, IEEE Trans. on Systems, Man, and Cybernetics Part B: Cybernetics, 26, 1, Feb. 1996.
Efe, K., “Heuristic models of task assignment scheduling in distributed systems,” Computer, 15, 6, June 1982.
Elmroth, E. and Larsson, L., “Interfaces for placement, migration, and monitoring of virtual machines in federated clouds,” in 8th Int'l Conf. on Grid and Cooperative Computing, Lanzhou, Gansu, Aug. 2009.
Fernandez-Baca, D., “Allocating modules to processors in a distributed system,” IEEE Trans. on Software Engineering, 15, 11, Nov. 1989.
Heegaard, P. E., Helvik, B. E. and Wittner, O. J., “The cross entropy ant system for network path management,” Telektronikk, 104, 01, pp. 19–40, 2008.
Heegaard, P. E. and Wittner, O. J., “Overhead reduction in a distributed path management system,” Computer Networks, 54, 6, pp. 1019–1041, 2010.
Heimfarth, T. and Janacik, P., “Ant based heuristic for os service distribution on adhoc networks,” Biologically Inspired Cooperative Computing, 2006.
Helvik, B. E. and Wittner, O., “Using the Cross Entropy Method to Guide/Govern Mobile Agent's Path Finding in Networks,” in 3rd Int'l Workshop on Mobile Agents for Telecommunication Applications, LNCS 2164, Aug 2001.
Hirofuchi, T., Ogawa, H., Nakada, H., Itoh, S. and Sekiguchi, S., “A live storage migration mechanism over wan for relocatable virtual machine services on clouds,” in 9th IEEE/ACM Int'l Symp. on Cluster Computing and the Grid, Shanghai, May 2009.
Hunt, G. C. and Scott, M. L., “The Coign Automatic Distributed Partitioning System,” in 3rd USENIX Symp. on Operating Systems Design and Implementation, New Orleans, Feb. 1999.
Joshi, K., Hiltunen, M. and Jung, G., “Performance Aware Regeneration in Virtualized Multitier Applications,” in DSN'09 Workshop on Proactive Failure Avoidance, Recovery and Maintenance, Lisbon, Jun. 2009.
Karp, R. M. and Luby, M. and Marchetti-Spaccamela, A., “A probabilistic analysis of multidimensional bin packing problems,” in 16th annual ACM Symp. on Theory of Computing, Washington, DC, May 1984.
Kephart, J. O. and Das, R., “Achieving self-management via utility functions,” IEEE Internet Computing, 11, pp. 40–48, 2007.
Kichkaylo, T. et al., “Constrained Component Deployment in Wide-Area Networks Using AI Planning Techniques,” Int'l. Parallel and Distributed Processing Symposium, 2003.
Kraemer, F. A. and Herrmann, P., “Service specification by composition of collaborations - an example,” in Proc. of the 2006 Int'l Conf. on Web Intelligence and Intelligent Agent Technology, Hong Kong, IEEE/WIC/ACM, 2006.
Kusber, R., Haseloff, S. and David, K., “An Approach to Autonomic Deployment Decision Making,” in 3rd Int'l Workshop on Self-Organizing Systems, LNCS 5343, December 2008.
Malek, S., “A User-Centric Framework for Improving a Distributed Software System's Deployment Architecture,” Proc. of the doctoral track at the 14th ACM SIGSOFT Symposium on Foundation of Software Engineering, Portland, 2006.
Meling, H. and Gilje, J. L., “A Distributed Approach to Autonomous Fault Treatment in Spread,” in 7th European Dependable Computing Conference, IEEE CS, May 2008.
Meling, H., Montresor, A., Helvik, B. E. and Babaoglu, O., “Jgroup/ARM: a distributed object group platform with autonomous replication management,” Software: Practice and Experience, 38, 9, pp. 885–923, July 2008.
Pu, C., Noe, J. D. and Proudfoot, A., “Regeneration of replicated objects: A technique and its eden implementation,” IEEE Transactions on Software Engineering, 14, 7, pp. 936–945, July 1989.
Rouvoy, R. and Beauvois, M. and Lozano, L., Lorenzo, J. and Eliassen, F., “MUSIC: an autonomous platform supporting self-adaptive mobile applications,” in 1st workshop on Mobile middleware: embracing the personal communication device, Leuven, Dec. 2008.
Rubinstein, R. Y., “The Cross-Entropy Method for Combinatorial and Continuous Optimization,” Methodology and Computing in Applied Probability, 1, 2, 1999.
Sabharwal, R., “Grid infrastructure deployment using smartfrog technology,” in Int'l Conf. on Networking and Services, Santa Clara, USA, pp. 73–79, Jul. 2006.
Stützle, T. and Dorigo, M., “A short convergence proof for a class of ant colony optimization algorithms,” IEEE Trans. Evolutionary Computation, 6, 4, pp. 358–365, 2002.
Verma, A., Ahuja, P. and Neogi, A., “pmapper: power and migration cost aware application placement in virtualized systems,” in 9th Int'l Conf. on Middleware, pp. 243–264, Dec. 2008.
Widell, N. and Nyberg, C., “Cross Entropy based Module Allocation for Distributed Systems,” in IASTED Int'l Conf. on Parallel and Distributed Computing Systems, Cambridge, Nov. 2004.
Wittner, O., “Emergent Behavior Based Implements for Distributed Network Management,” Ph.D. thesis, NTNU, Dept. of Telematics, Norway, 2003.
Wood, T. and Shenoy, P. J. and Venkataramani, A. and Yousif, M. S., “Black-box and Gray-box Strategies for Virtual Machine Migration,” in 4th USENIX Symp. on Networked Systems Design and Implementation, Cambridge, MA, Apr. 2007.
Xu, J. et al., “On the use of fuzzy modeling in virtualized data center management,” in Int'l. Conf. on Autonomic Computing, June 2007.
Yu, H. and Gibbons, P. B., “Optimal inter-object correlation when replicating for availability,” Distributed Computing, 21, 5, pp. 367–384, Feb. 2009.
Yu, H. and Vahdat, A., “Consistent and automatic replica regeneration,” ACM Trans. on Storage, 1, 1, pp. 3–37, Dec. 2004.
Zlochin, M. et al., “Model-based search for combinatorial optimization: A critical survey,” Annals of Operations Research, 131, pp. 373–395, 2004.