Resource reservation is a essential component in providing QoS guarantees to distributed multimedia applications that run over the internetwork. Early reservation systems, including both immediate reservation and advance reservation, have taken an "all-or-nothing" approach in which both QoS and temporal parameters of requests are inflexible. This paper describes a new probe-based adaptive reservation approach using Probing Requests that exploits the potential flexibility in reservation requests to increase resource utilization and reduce rejection rates. Compared to other approaches that support flexibility, the probe-based approach is more efficient in finding alternatives, and it causes less signaling overhead and incurs a lower computational load on the often busy resource providers. The Probing Request mechanism has been implemented as part of our inter-domain bandwidth broker, can also be applied to other resource reservation schemes.