Resource and Task Allocation Algorithm for WAN-based Distributed Computing Environment
Treść / Zawartość
In the paper an approximate algorithm for optimizing of distributed computing WAN network is proposed. Distributed computing systems become the common tools in different kind of business, science and even entertainment. In order to minimize processing time of data and utilize spare resources available on remote systems, many companies and institutions decide to build and maintain own wide area networks (WAN) for ensuring reliable and secure distributed processing of data. Design of WANs in concerned with solving different optimization problems, like routing assignment, capacities of channel selection, resource (i.e. servers, management centre) allocation. Due to peculiar structure of wide area networks and nature of protocols, proper optimization methods and algorithms should be constructed for WAN-based distributed computing systems. In the paper the model of the distributed environment, built on WAN infrastructure is presented. Then, the optimization problem for routing assignment, channel capacities assignment and grid management center (data repository) allocation is formulated. Finally, an approximate algorithm is presented for formulated problem. Proposed algorithm, observations and conclusions should effect in improving of distributed computing systems design.
Bibliogr. 24 poz.
-  H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2 ed., Wiley-Interscience, 2004.
-  M. Baker, R. Buyya, and D. Laforenza, Grids and Grid Technologies for Wide-Area Distributed Computing, Software — Practice and Experience, Hoboken, NJ: Wiley, 2002.
-  K. Chari, “Resource allocation and capacity assignment in distributed systems”, Computers & Operations Research, vol. 23, no. 11, 1996, pp. 1025–1041.
-  M. P. Clark, Data networks, IP and the Internet: protocols, design and operation, John Wiley & Sons, 2003.
-  S. Demeyer, M. De Leenheer, J. Baert, M. Pickavet, and P. Demeester, “Ant colony optimization for the routing of jobs in optical grid networks,” Journal of Optical 8etworking, vol. 7, no. 2, 2008.
-  I. Foster, “The Grid: A New Infrastructure for 21st Century Science,” Physics Today, vol. 55, no. 2, 2002, pp. 42–47.
-  I. Foster and C. Kesselman, The Grid: Blueprint for a 8ew Computing Infrastructure, Morgan Kaufmann Publishers, 1999.
-  I. Foster, C. Kesselman, and S. Tuecke, “The Anatomy of the Grid,” International Journal of Supercomputer Applications, 2001.
-  L. Fratta, M. Gerla, and L. Kleinrock, “The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design,” 8etworks, vol. 3, 1973, pp. 97–133.
-  B. Gavish and I. Neuman, “A System for Routing and Capacity Assignment in Computer Communication Networks,” IEEE Transactions on Communications, vol. 37, 1989, pp. 360–366.
-  C. Gu Kang and H. H. Tan, “Combined channel allocation and routing algorithms in packed switched networks,” Computer Communications, vol. 20, no. 13, 1997, pp. 1175–1190.
-  Y. Itami, T. Ishigooka, and T. Yokoyama,“A Distributed Computing Environment for Embedded Control Systems with Time-Triggered and Event-Triggered Processing,” in Proc. The 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2008, pp. 45–54.
-  A. Kasprzak, Topological Design of the Wide Area Networks, Wroclaw: Wroclaw University of Technology Press, 2001.
-  D. D. Kouvatsos and I. M. Mkwawa, “Multicast communication in grid computing networks with background traffic,” IEE Proceedings - Software, vol. 150, no. 4, 2003, pp. 257–264.
-  M. Markowski and A. Kasprzak, “An exact algorithm for host allocation, capacity and flow assignment problem in WAN,” in Proc. the IFIP TC6/WG6.4 Workshop on Internet Technologies, Applications and Social Impact, Kluwer Academic Publishers, 2002, pp. 73–82.
-  M. Markowski and A. Kasprzak, “An approximate algorithm for replica allocation problem in wide area networks”, in Proc. 3rd Polish-German Teletraffic Symposium, VDE Verlag, Berlin, 2004, pp. 161–166.
-  M. Markowski and A. Kasprzak, “An approximate algorithm for web replica allocation and topology assignment problem in WAN,” in Proc. 17th IMACS World Congress, Paris, France, 2005.
-  M. Markowski and A. Kasprzak, “The web replica allocation and topology assignment problem in wide area networks: algorithms and computational results,” Lecture 8otes in Computer Science, vol. 3483, 2005, pp. 772–781.
-  M. Markowski and A. Kasprzak, “The Three-Criteria Servers Replication and Topology Assignment Problem in Wide Area Networks,” Lecture 8otes in Computer Science, vol. 3982, 2006, pp. 1119–1128.
-  J. Nabrzyski, J. Schopf, and J. Weglarz (eds.), Grid resource management: state of the art and future trends, Boston: Kluwer Academic Publishers, 2004.
-  M. Pioro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer 8etworks, San Francisco: Elsevier, Morgan Kaufmann Publishers, 2004.
-  R. Sterritt and D. Bustard, “Towards an Autonomic Computing Environment,” in Proceedings of the 14th International Workshop on Database and Expert Systems Applications, 2003, pp. 699–703.
-  F. Travostino, Grid 8etworks, J. Wiley & Sons, 2006.
-  C. T. Yang, P. C. Shih, and K.C. Li, “A High-Performance Computational Resource Broker for Grid Computing Environments,” in Proc. International Conference on AIMA, vol. 2, 2005, pp. 333–336.