In Grid system, we need an advance reservation to ensure that specified resources are available for applications in a particular time in the future. The impact of advance reservations is decreasing resource utilization due to fragmentations. To mitigate this problem in our previous work we have proposed a novel advance reservation scheduling namely First Come First Serve – Ejecting base Dynamic Scheduling (FCFS-EDS) with advance planning. In order to implement reliable FCFS – EDS scheduling, it is important to store information in data structures about future allocations and to provide fast access to the available information. This paper proposes a novel data structure used by FCFS – EDS scheduling strategy to increase the throughput in a grid environment.

1. Foster, I. , and Kesselman, C. Computational Grids. Morgan Kaufmann, 1998.
2. Joshy Joseph and Craig Fellenstein, Grid Computing, Prentice Hall PTR, New Jersey, December 30, 2003
3. W. Cirne, F. Brasileiro, J. Sauve, N. Andrade, D. Paranhos, E. Santos-Neto, and R. Medeiros. Grid computing for bag of tasks applications. In Proc. of the 3rd IFIP Conference on E-Commerce, E-Business and E-Government, Sep 2003
4. D. Abramson, J. Giddy, and L. Kotler. High performance parametric modeling with Nimrod/G: Killer application for the global grid? In Proc. of the 14th International Symposium on Parallel and Distributed Processing (IPDPS), Cancun, Mexico, May 1–5 2000.
5. Sulistio A. , Buyya R. , A Grid simulation infrastructure supporting advance reservation. In Proceedings 16th International Conference on Parallel and Distributed Computing and Systems, Cambridge, USA, November 9–11 2004.
6. I. Foster, C. Kesselman, C. Lee, R. Lindell, K. Nahrstedt, and A. Roy. A distributed resource management architecture that supports advance reservations and co-allocation. In Proc. of the 7th International Workshop on Quality of Service, London, UK, 1999.
7. S. McGough, L. Young, A. Afzal, S. Newhouse, and J. Darlington. Work?ow enactment in ICENI. UK e-Science All Hands Meeting, pages 894–900, September 2004.
8. Maui Cluster Scheduler. http://www. clusterresources. com/pages/products/maui-cluster-scheduler. php, Last Accessed June 2009
9. B. Nitzberg, J. M. Schopf, and J. P. Jones. PBS Pro: Grid Computing and Scheduling Attributes. In Grid Resource Management: State of the Art and Future Trends, pages 183– 190. Kluwer Academic Publishers, Norwell, MA, USA, 2004.
10. K. Kim. Extended DSRT Scheduling System. Master's thesis, Department of Computer Science, University of Illinois at Urbana-Champaign (USA), Aug. 2000
11. G Garimella, Advance CPU Reservations With The DSRT Scheduler. Master's thesis, Department of Computer Science, University of Illinois at Urbana-Champaign (USA), 1999.
12. Sun Grid Engine. http://gridengine. sunsource. net, 2008
13. R. Buyya and A. Sulistio, Service and Utility Oriented, Data Centers and Grid Computing Environments: Challenges and Opportunities for Modeling and Simulation Communities, Keynote Paper, In Proceedings of the 41st Annual Simulation Symposium (ANSS'08), April 13–16, 2008, Ottawa, Canada.
14. W. Smith, I. Foster and V. Taylor, "Scheduling with Advanced Reservations", In Proc. of the 14th IEEE International Symposium on Parallel and Distributed Processing (IPDPS'00), 2000, pp. 127-132.
15. Rusydi Umar, Arun Agarwal, CR Rao, Advance Planning and Reservation in a Grid System, The Fourth International Conference on Networked Digital Technologies, NDT 2012, April 24 – 26, 2012, Dubai. To Appear in CCIS/LNCS Vol 7899
16. L. -O. Burchard. Analysis of data structures for admission control of advance reservation requests. IEEE Transactions on Knowledge and Data Engineering, 17(3), 2005.
17. L. -O. Burchard and H. -U. Heiss, "Performance Evaluation of Data Structures for Admission Control in Bandwidth Brokers," Proc. Int'l Symp. Performance Evaluation of Computer and Telecommunication Systems (SPECTS '02), Soc. for Modeling and Simulation Int'l, pp. 652-659, 2002.
18. R. Guerin and A. Orda, "Networks with Advance Reservations: The Routing Perspective," Proc. IEEE INFOCOM '99, pp. 118-127, 2000.
19. O. Schelen, A. Nilsson, J. Norrgard, and S. Pink, "Performance of QoS Agents for Provisioning Network Resources," Proc. Seventh Int'l Workshop on Quality of Service (IWQoS '99), pp. 17-26, 1999.
20. A. Brodnik and A. Nilsson. A static data structure for discrete advance bandwidth reservations on the internet. In Proc. of Swedish National Computer Networking Workshop (SNCNW), Stockholm, Sweden, September 2003.
21. R. Brown. Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem. Communications of the ACM, 31(10):1220{1227, 1988.
22. T. Wang and J. Chen. Bandwidth tree – a data structure for routing in networks with advanced reservations. In Proc. of the 21st Intl. Performance, Computing, and Communications Conference (IPCCC), pages 37–44, Phoenix, USA, 2002.
23. L. Yuan, C. -K. Tham, and A. L. Ananda. A probing approach for effective distributed resource reservation. In Proc. of the 2nd International Workshop on Quality of Service in Multiservice IP Networks, pages 672–688, Milan, Italy, February 2003. Springer-Verlag.
24. Q. Xiong, C. Wu, J. Xing, L. Wu, and H. Zhang. A linked-list data structure for advance reservation admission control. In Proc. of the 3rd International Conference on Networking and Mobile Computing (ICCNMC), Zhangjiajie, China, August 2-4 2005.
25. A. Sulistio, U. Cibej, S. Prasad, and R. Buyya, GarQ: An Efficient Scheduling Data Structure for Advance Reservations of Grid Resources, International Journal of Parallel, Emergent and Distributed Systems (IJPEDS), DOI: 10. 1080/17445760801988979, April 4, 2008, Taylor & Francis Publication, UK.

Data Structure Fcfs-eds Advance Reservation