Grid capacity planning with negotiation-based advance reservation for optimized QoS

Advance reservation of Grid resources can play a key role in enabling Grid middleware to deliver on-demand resource provision with significantly improved Quality-of-Service (QoS). However, in the Grid, advance reservation has been largely ignored due to the dynamic Grid behavior, underutilization concerns, multi-constrained applications, and lack of support for agreement enforcement. These issues force the Grid middleware to make resource allocations at runtime with reduced QoS. To remedy these, we introduce a new, 3-layered negotiation protocol for advance reservation of the Grid resources. We model resource allocation as an on-line strip packing problem and introduce a new mechanism that optimizes resource utilization and QoS constraints while generating the contention-free solutions. The mechanism supports open reservations to deal with the dynamic Grid and provides a practical solution for agreement enforcement. We have implemented a prototype and performed experiments to demonstrate the effectiveness of our approach