Quality of Service (QoS) has been a major concern in the field of network management, even more so for emerging dynamic multimedia applications (Video on Demand, Telefony over IP etc.) that are becoming mainstream. This problem is particularly sensitive in the context of exchanges accross multiple independent and heterogeneous domains (X-domain), where global SLAs (Service Level Agreement) have to be satisfied accross domains. In this paper, we consider a typical scenario of X-domain provisioning of a video-conference session. The article addresses the problem of how to automatically negotiate QoS budgets between possible service providers (SP) that will meet the end-to-end requirements. We propose a QoS budget negotiation algorithm based on the dynamic programming principle. The negotiation is strictly distributed in the sense that all contracts are agreed on bilaterally between adjacent SPs, and each SP becomes responsible for the subbudget between it and the end-domain.