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 run-time 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 online 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