Measuring Fragmentation of Two-Dimensional Resources Applied to Advance Reservation Grid Scheduling

Whenever a resource allocation fails although enough free capacity being available, fragmentation is easily spotted as cause. But how the fragmentation in a system requiring continuous allocations like time schedules or memory can be quantified is hardly analyzed. A Grid environment using advance reservation even combines two-dimensions: time and resource dimension. In this paper a new way to measure the fragmentation of a system in one dimension is proposed. This measure is then extended to incorporate also the second dimension. Extensive simulations showed that the proposed fragmentation measure is a good indicator of the state of the system.