Incentive Compatible Pricing Strategies for QoS Routing

QoS routing mechanisms allow users identify paths that can accommodate their performance requirements and reserve the necessary resources. An important problem is how to conduct such resource allocation efficiently, not only from the single-connection, but also from the network point of view. We propose the use of pricing mechanisms as a means to regulate the users' decisions in a networkwide efficient manner. Focusing on QoS architectures that employ rate-based schedulers, we formulate a congestion-based pricing scheme. We establish the structure of the corresponding user-optimal response, i.e., a path selection algorithm that satisfies the user's requirements at minimal cost. We show that the underlying noncooperative game among users has a unique equilibrium, for any particular choice of price functions. Then, we establish the existence of incentive compatible price functions, which drive the network into an equilibrium point that coincides with the optimum of a social function. Specifically, these price functions are the derivatives of the social function. We then extend our results to scenarios in which users can identify only sub-optimal paths, as is often the case with multi-constrained path optimization.