Experiences with Hierarchical Request Flow Management for Network-Enabled Server Environments

Abstract

The Distributed Interactive Engineering Toolbox (DIET) is a toolbox for the construction of network-enabled server systems. DIET servers provide transparent access to compute resources; resources can be either a single, interactive machine where the DIET server runs each request directly on its host, or batch-managed systems where the DIET server manages request submission and completion notification. A distributed hierarchy of scheduling agents connects the servers and is responsible for selecting servers appropriate to each client request. DIET seeks scalability by distributing the scheduling process and by keeping resource information measurement and performance prediction at the server level.

DIET has traditionally offered an on-line scheduling model whereby all requests are scheduled immediately or refused. This approach can overload interactive servers in high-load conditions and does not allow adaptation of the schedule to task or data dependences. In this paper we consider an alternative model based on active management of the flow of requests throughout the system. We have added support for (1) limiting the number of concurrent requests on interactive servers, (2) server and agentlevel queues, and (3) window-based scheduling algorithms whereby the request release rate to servers can be controlled and some rearrangement of request to host mappings is possible. We present experiments demonstrating that these approaches can improve performance and that the overheads introduced are not significantly different from those of the standard DIET approach.

Keywords

Distributed scheduling scheduling heuristics on-line scheduling network enabled servers grid computing

Get full access to this article

View all access options for this article.

References

Andresen, D. and McCune, T. 2000. H-SWEB: a hierarchical scheduling system for distributed WWW server clusters . Concurrency: Practice and Experience 12: 189–210 .

Berman, F. , Fox, G. , and Hey, A. , editors. 2003. Grid Computing: Making the Global Infrastructure a Reality, Wiley, New York .

Bosilca, G. , Fedak, G. , and Cappello, F. 2001. OVM: outof-order execution parallel virtual machine . Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID’01),Brisbane, Australia, May.

Caron, E. , Desprez, F. , Lombard, F. , Nicod, J.-M. , Quinson, M. , and Suter, F. 2002. A scalable approach to networkenabled servers. Proceedings of EuroPar 2002, Paderborn,-Germany .

Caron, E. , Chouhan, P. , and Legrand, A. 2004. Automatic deployment for hierarchical network-enabled servers . Proceedings of the 13th Heterogeneous Computing Workshop (HCW 2004), Santa Fe, NM, April.

Carreto, J. , Fernández, J. , García, F. , and Chouhary, A. 2003. A hierarchical disk scheduler for multimedia systems . Future Generation Computer Systems 19: 23–35 .

Casanova, H. and Dongarra, J. 1996. NetSolve: a network server for solving computational science problems . Proceedings of Supercomputing Conference (SC’96), Pittsburgh, PA, November.

Casanova, H. , Legrand, A. , Zagorodnov, D. , and Berman, F. 2000a. Heuristics for scheduling parameter sweep applications in grid environments . Proceedings of the 9th Heterogeneous Computing Workshop (HCW’00),Cancun, Mexico, May.

Casanova, H. , Obertelli, G. , Berman, F. , and Wolski, R. 2000b. The apples parameter sweep template: user-level middleware for the grid . Proceedings of Supercomputing Conference (SC’2000),Dallas, TX, November.

10.

Casanova, H. , Matsuoka, S. , and Dongarra, J. 2001. Networkenabled server systems: deploying scientific simulations on the grid . Proceedings of the High Performance Computing Symposium (HPC’01),Seattle, WA, April.

11.

Dandamudi, S. 2003. Hierarchical Scheduling in Parallel and Cluster Systems, Kluwer Academic/Plenum, New York .

12.

Dandamudi, S. and Ayachi, S. 1999. Performance of hierarchical processor scheduling in shared-memory multiprocessor systems . IEEE Transactions on Computers 48(11): 1202–1213 .

13.

Fedak, G. , Germain, C. , NÉri, V. , and Cappello, F. 2001. XtremWeb: a generic global computing system . Proceedings of the Workshop on Global Computing on Personal Devices, held in conjunction with CCGrid’2001, Brisbane, Australia, May.

14.

Feitelson, G. 1997. A survey of scheduling in multiprogrammed parallel systems. Technical Report RC 19790 (87657), IBM T. J. Watson Research Center .

15.

Feitelson, D. , Rudolf, L. , Schwiegelshohn, U. , Sevcik, K. , and Wong, P. 1997. Theory and practice in parallel job scheduling. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, Vol. 1291, D. Feitelson and L. Rudolf , editors, Springer-Verlag, Berlin , pp. 1–34.

16.

Foster, I. and Kesselman, C. 1998. The Globus Project: A Status Report, IEEE, Piscataway, NJ, pp. 4–18.

17.

Foster, I. and Kesselman, C. , editors. 2004. The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Mateo, CA .

18.

Gehring, J. and Preiss, T. 1999. Scheduling a metacomputer with un-cooperative subschedulers. Proceedings of the IPPS Workshop on Job Scheduling Strategies for Parallel Processing, Puerto Rico, April, Lecture Notes in Computer Science, Vol. 1659, Springer-Verlag, Berlin .

19.

Halderen, A. , Overeinder, B. , and Sloot, P. 1998. Hierarchical resource management in the Polder metacomputing initiative . Parallel Computing 24: 1807–1825 .

20.

Juhasz, Z. , Andics, A. , and Pota, S. 2002. Towards a robust and fault-tolerant multicast discovery architecture for global computing grids . Proceedings of the 4th Austrian– Hungarian Workshop on Distributed and Parallel Systems (DAPSYS 2002), Linz, Austria, September.

21.

Nakada, H. , Sato, M. , and Sekiguchi, S. 1999. Design and implementations of Ninf: towards a global computing infrastructure . Future Generation Computing Systems 15(5–6): 649–658 .

22.

Quinson, M. 2002. Dynamic performance forecasting for network-enabled servers in a metacomputing environment . Proceedings of the International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS’02),Fort Lauderdale, FL, April 15–19.

23.

Santoso, J. , van Albada, G. , Nazief, B. , and Sloot, P. 2001. Simulation of hierarchical job management for metacomputing systems . International Journal of Foundations of Computer Science 12(5): 629–643 .

24.

Seidel, E. , Allen, G. , Merzky, A. , and Nabrzyski, J. 2002. Grid-Lab–a grid application toolkit and testbed . Future Generation Computing Systems 18(8): 1143–1153 .

25.

Seymour, K. , Nakada, H. , Matsuoka, S. , Dongarra, J. , Lee, C. , and Casanova, H. 2002. An overview of GridRPC: a remote procedure call API for grid computing . Proceedings of the 3rd International Workshop on Grid Computing, Baltimore, MD, November.

26.

Subramani, V. , Kettimuthu, R. , Srinivasan, S. , and Sadayappan, P. 2002. Distributed job scheduling on computational grids using multiple simultaneous requests . Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing (HPDC’02),Edinburgh, Scotland, July 24–26.

27.

Thain, T. T. D. and Livny, M. 2005. Distributed computing in practice: the Condor experience . Concurrency and Computation: Practice and Experience 17(2–4): 323–356 .

28.

Wolski, R. , Spring, N. T. , and Hayes, J. 1999. The Network Weather Service: a distributed resource performance forecasting service for metacomputing . Future Generation Computing Systems, Metacomputing Issue 15(5–6): 757–768 .