Internet centers host services for e-banks, e-auctions and other clients. Hosting centers then must allocate servers among clients to maximize revenue. The limited number of servers, costs of reallocating servers, and unpredictability of requests make server allocation optimization difficult
Based on the many similarities between server and honey bee colony forager allocation, we pro pose a new decentralized honey bee algorithm which dynamically allocates servers to satisfy request loads. We compare it against an omniscient optimality algorithm, a conventional greedy algorithm, and an algorithm that computes omnisciently the optimal static allocation. We evaluate performance on simulated request streams and commercial trace data
Our algorithm performs better than static or greedy for highly variable request loads, but greedy can outperform it under low variability. Honey bee forager allocation, though suboptimal for static food sources, may possess a counterbalancing responsiveness to food source variability.
Appleby, K. , Fakhouri, S. , Fong, L. , Goldszmidt, G. , Kalantar, M. , Krishnakumar, S. , Pazel, D. P. , Pershing, J. , & Rochwerger, B. (2001). Oceano—SLA based management of a computing utility . Seventh IFIP/IEEE International Symposium on Integrated Network Management, pp. 855-868 .
2.
Arlitt, M. , & Jin, T. (1999). Workload characterization of the 1998 World Cup web site. Technical Report HPL-1999-35R1. HP Laboratories .
3.
Baker, M. , Buyya, R. , & Laforenza, D. (2000). The grid: International efforts in global computing . In Proceedings of the International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet.
4.
Banga, G. , Druschel, P. , & Mogul, J. C. (1999). Resource containers: A new facility for resource management in server systems . Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI).
5.
Bartholdi III, J. J. , Seeley, T. D. , Tovey, C. A. , & Vande Vate, J. H. (1993). The pattern and effectiveness of forager allocation among flower patches by honey bee colonies . Journal of Theoretical Biology, 160, 23-40 .
6.
Baratloo, A. , Dasgupta, P. , & Kedem, Z. M. (1996). CALYPSO: A novel software system for fault-tolerant parallel processing on distributed platforms . Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing HPDC-4.
7.
Baratloo, A. , Itzkovitz, A. , Kedem, Z. M. , & Zhao, Y. (1998). Just-in-time transparent resource management in distributed systems. Technical Report TR1998-762. Computer Science Department, New York University .
8.
Bonabeau, E. , Dorigo, M. , & Theraulaz, G. (1999). Swarm intelligence: Fom natural to artificial systems. Oxford: Oxford University Press .
9.
Bonabeau, E. , & Meyer, C. (2001). Swarm intelligence: A whole new way to think about business . Harvard Business Review, 19(5) 107-114 .
10.
Brewer, E. A. (2000). Lessons from giant-scale services. http://db.cs.berkeley.edu/%7Ejmh/cs262
11.
Brown, L. , Gans, N. , Mandelbaum, A. , Sakov, A. , Shen, H. , Zeltyn, S. , & Zhao, L. (2002). Statistical analysis of a telephone call center: a queueing-science perspective. http://stat.wharton.upenn.edu/%7Ehaipeng/
12.
Buyya, R. , Abramson, D. , & Giddy, J. (2000). Economy driven resource management architecture for computational power grids . In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA2000).
13.
Chase, J. S. , Anderson, D. C. , Thakar, P. N. , & Vahdat, A. M. (2001). Managing energy and servers resources in hosting centers . In 18th ACM Symposium on Operating Systems Principles (SOSP) (pp. 103-116 ). New York, NY: ACM Press.
14.
Cicirello, V. A. , & Smith, S. F. (2001). Insect societies and manufacturing . In IJCAI-01 Workshop on Artificial Intelligence and Manufacturing: New AI Paradigm for Manufacturing.
15.
Crovella, M. E. (1998). Generating representative web workloads for network and server performance evaluation . In Proceedings of Performance ’98/ACM SIGMETRICS’98. http://www.cs.bu.edu/faculty/crovella/links.html
16.
Czajkowski, K. , Foster, I. T. , Karonis, N. T. , Kesselman, C. , Martin, S. , Smith, W. , & Tuecke, S. (1998). A resource management architecture for metacomputing systems . In Proceedings of the IPPS/SPDP’98 Workshop on Job Scheduling Strategies for Parallel Processing (pp. 62-82 ).
17.
Dasgupta, P. , Kedem, Z. M. , & Rabin, M. O. (1995). Parallel processing on networks of workstations: A fault-tolerant, high performance approach . In Proceedings of the 15th International Conference on Distributed Computing Systems (ICDCS-15).
18.
Dusseau, A. C. , Arpaci, R. H. , & Culler, D. E. (1996). Effective distributed scheduling of parallel workloads . In ACM SIG-METRICS’96 Conference on the Measurement and Modeling of Computer Systems (pp. 25-36 ). New York, NY: ACM Press..
19.
Dusseau, A. C. , & Culler, D. E. (1997). Extending proportional-share scheduling to a network of workstations . In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’97).New York, NY: ACM Press.
Ford, B. & Susarla, S. (1996). CPU inheritance scheduling . In Usenix Association Second Symposium on Operating Systems Design and Implementation (OSDI) (pp. 91-105 ).
22.
Fox, A. , Gribble, S. D. , Chawathe, Y. , Brewer, E. A. , & Gauthier, P. (1997). Cluster-based scalable network services . In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP-16).
23.
De Farias, D. P. , King, A. J. , Squillante, M. S. , & Roy, B. V. (2002). Dynamic control of web server farms . INFORMS Conference-Revenue Management Section, Columbia University.
24.
Gelenbe, E. (Ed.) (2000). Internet traffic: periodicity, tail behavior and performance implication. System Performance Evaluation: Methodologies and Application (Chapt. 2). Boca Raton, FL: CRC Press .
25.
Hill, J. M. D. , Donaldson, S. R. & Lanfear, T. (1998). Process migration and fault tolerance of BSPlib programs running on networks of workstations . D. J. Pritchard & J. Reeve, European Conference on Parallel Processing (Europar-98) (pp. 151-164 ).
26.
HP (2004). http://www.hp.com/hps/infrastructure/in_datacenter.html
27.
IBM (2003). http://www-3.ibm.com/services/e-business/hosting/managed_hosting.html
28.
Jayram, T. S. , Kimbrel, T. , Krauthgamer, R. , Schieber, B. , & Sviridenko, M. (2001). Online server allocation in a server farm via benefit task systems . In 33rd ACM Symposium on Theory of Computing. New York, NY: ACM Press.
29.
Jones, M. B. , Rosu, D. , & Rosu, M. (1995). Modular real-time resource management in the Rialto operating system. Technical Report MSR-TR-95-16, Microsoft Research .
30.
Jones, M. B. , Rosu, D. , & Rosu, M. (1997). CPU reservations and time constraints: Efficient, predictable scheduling of independent activities . In Symposium on Operating Systems Principles (pp. 198-211 ). New York, NY: ACM Press.
31.
Little (1994). C++SIM. University of Newcastle Upon Tyne. http://cxxsim.ncl.ac.uk/
32.
Litzkow, M. , Tannenbaum, T. , Basney, J. , & Livny, M. (1997). Checkpoint and migration of UNIX processes in the Condor distributed processing system. Technical Report 1346, Computer Science Department, University of Wisconsin at Maddison .
33.
Manasse, M. S. , McGeoch, L. A. , & Sleator, D. D. (1988). Competitive algorithm for online problems . In 20th Annual ACM Symposium on Theory of Computing (pp. 323-333 ).
34.
Markoff, J. (2003). IBM says it benefits two ways from on-demand computing . New York Times13th November. http://www.iht.com/articles/117552.html.
35.
Nakrani, S. , & Tovey C. (2004). Honey bee waggle dance protocol and autonomic server orchestration in internet hosting centers . In Workshop on Nature Inspired Approaches to Network and Telecommunication in 8th International Conference on Parallel Problem Solving from Nature,
36.
Nielsen, J. (2000). Designing web usability. Berkeley, CA: Pearson Education/New Rider Publishing .
37.
Palmer, J. , & Mitrani, I. (2003). Dynamic server allocation in heterogeneous clusters. Technical Report CS-TR:799, School of Computing Science, University of Newcastle, UK .
38.
Seeley T. D. (1995). The wisdom of the hive. Cambridge, MA, Harvard University Press .
39.
Seeley, T. D. , Camazine, S. , & Sneyd, J. (1991). Collective decision making in honey bees: How colonies choose among nectar sources . Behavioral Ecology and Sociology, 28, 277-290 .
40.
Sychron (2004). http://www.sychron.com/
41.
Verio (2003). http://hosting.verio.com/
42.
Waldspurger, C. A. , & Weihl, W. E. (1994). Lottery scheduling: Flexible proportional-share resource management . In Proceedengs of the First Symposium on Operating Systems Design and Implementation (pp. 1-11 ) New York, NY: ACM Press.
43.
Waldspurger, C. A. & Weihl, W. E. (1995). Stride scheduling: Deterministic proportional-share resource management. Technical MemorandumMIT/LCS/TM-528 MIT Laboratory for Computer Science .
44.
Wolf, J. L. , & Yu, P. S. (2001). On balancing the load in a clustered web farm . ACM Transactions on Internet Technology, 1, (2), 231-261 .
