Optimal resource allocation in multi-class service systems using pricing

New application requirements and developments in the Internet protocols are leading the way toward an "enhanced" next-generation Internet offering some Quality of Service (QoS) guarantees. This dissertation considers a communication network able to accommodate differentiated classes of service to support various types of bandwidth requirements. Links in the network have finite capacities. The network charges a fee per call which can depend on the current congestion level, and which affects users' demand for calls. Users extract a certain utility when calls are successfully established. The objective is to devise pricing and routing strategies that maximize the long-term average rate at which utility is accumulated, that is, maximize the social welfare.; It is shown that a simple "static pricing" policy is asymptotically optimal in a regime of many, relatively small, users. This implies that pricing and resource allocation decisions should evolve on the time-scale of changes in demand statistics rather than the short time-scale of instantaneous congestion. The result is general and holds under both fixed and dynamic routing scenarios. A characterization of the structure of asymptotically optimal static prices, expressing them in terms of a parsimonious number of parameters, is also provided. Effective parameter values can be found by solving a deterministic optimization problem summarizing network dynamics or by employing simulation-based optimization methods. Further, a distributed and asynchronous stochastic approximation algorithm for the proposed policy, driven by gradient estimates of a system-wide performance measure, is constructed. It is established that the algorithm converges in a strong-sense to a global optimum, both in synchronous and asynchronous scenarios. This implies that distributed resource allocation for large networks is feasible.; This dissertation also considers a revenue maximization problem for airlines with finite seat capacities. A simulation-based actor-critic algorithm is explored in pursuing the optimal fare prices. The theory of actor-critic algorithms seeks to find a sub-optimal solution in complex systems where no or limited structural information is available. A two-layer system consisting of a lower-level inventory controller and an actor-critic optimizer is devised. The algorithm outperforms other heuristics and in many cases it performs close to optimal.