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 the case in which users can identify only sub-optimal paths, as is often the case with multiobjective path optimization.

The complexity of modern networks calls for decentralized control schemes where each user makes its control decisions independently based on some individual performance objectives. The operating points of such noncooperative networks are the Nash equilibria of the underlying control game. Nash equilibria are generically inefficient and lead to suboptimal network performance. Using routing as a control paradigm, a methodology is devised for overcoming this inefficiency based on pricing mechanisms. Assuming that the price for usage of each link's proportional to the congestion level at the link, is shown that the provider can enforce any operating point it deems efficient by offering the capacity of the various links at discount prices. The incentive compatible discount vector is shown to be unique to the extent of a multiplicative constant, and its structure is specified explicitly. An adaptive algorithm for distributed computation of the incentive compatible discount vector is introduced. The applicability of the results in various practical scenarios is investigated by means of a prototype that implements the routing game as a Web-based game.

In this paper a pricing technique for resource management in an intranet environment is given. The price of the services are dynamically determined by the servers of the network, taking into account the general policy of the manager of the network. Both decentralized and centralized control is used to increase the efficiency of the network. An architecture imposing small implementation cost is presented. Implementation issues are discussed and experimental results are given.

In noncooperative networks users make control decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. Nash equilibria are generically inefficient and exhibit suboptimal network performance. Focusing on routing, a methodology is devised for overcoming this deficiency, through the intervention of the network manager. The manager controls part of the network flow, is aware of the noncooperative behavior of the users and performs its routing aiming at improving the overall system performance. The existence of maximally efficient strategies for the manager, i.e., strategies that drive the system into the global network optimum, is investigated. A maximally efficient strategy of the manager not only optimizes the overall performance of the network, but also induces an operating point that is efficient with respect to the performance of the individual users (Pareto efficiency). Necessary and sufficient conditions for the existence of a maximally efficient strategy are derived, and it is shown that they are met in many cases of practical interest. The maximally efficient strategy is shown to be unique and it is specified explicitly.

Traditional computer networks were typically designed with system-wide optimization in mind. In noncooperative networks users make control decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. Nash equilibria exhibit, in general, suboptimal network performance. Focusing on routing, a methodology is devised for overcoming this deficiency, through the intervention of the network manager. The manager controls part of the network flow, is aware of the noncooperative behavior of the users and performs its routing aiming at improving the overall system performance. The existence of maximally efficient strategies for the manager, i.e., strategies that drive the system into the global network optimum, is investigated. Necessary and sufficient conditions for the existence of a maximally efficient strategy are derived. The maximally efficient strategy are shown to be unique and it is specified explicitly.

The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by K users is investigated. The performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. Previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. To overcome this difficulty, a more general approach to study the existence of Nash equilibria for decentralized control schemes is introduced. This approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. For the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of K interdependent linear programs. Employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. Brouwer's theorem implies, then, that the best reply function has a fixed point.

In noncooperative networks users make control decisions that optimize their individual performance measure. Focusing on routing, two methodologies for architecting noncooperative networks are devised, that improve the overall network performance. These methodologies are motivated by problem settings arising in the provisioning and the run time phases of the network. For either phase, Nash equilibria characterize the operating point of the network. The goal in the provisioning phase is to allocate link capacities that lead to systemwide efficient Nash equilibria. The solution of such design problems is, in general, counterintuitive, since adding link capacity might lead to degradation of user performance. For systems of parallel links, it is shown that such paradoxes cannot occur and that the optimal solution coincides with the solution in the single-user case. Extensions to general network topologies are derived. During the run time phase, a manager controls the routing of part of the network flow. The manager is aware of the noncooperative behavior of the users and makes its routing decisions based on this information while aiming at improving the overall system performance. We obtain necessary and sufficient conditions for enforcing an equilibrium that coincides with the global network optimum, and indicate that these conditions are met in many cases of interest.>