Network resource allocation: Distributed algorithms and pricing schemes

This dissertation contributes to three significant aspects of network resource allocation. First, it expands the scope of applicability of a price-based distributed resource allocation algorithm that is representative of the ubiquitous and well-entrenched Transmission Control Protocol (TCP). A common assumption behind the algorithm is that traffic flows are elastic, which means that they adapt gracefully to degradations in allocated rate and that there is no hard limit on the allocated rate. The elastic flows are assigned utility functions that are concave and continuous leading to the tractability of a network utility maximization problem, for which the algorithm is shown to achieve the optimal. Our work focuses on inelastic flows, with associated utility functions that might be neither concave nor continuous. We present conditions under which the standard price-based distributed algorithm can still converge to the globally optimal rate allocation despite non-concavity of utility functions. We then show how to provision link capacity to guarantee convergence of the standard distributed algorithm.Second, the dissertation proposes a novel distributed optimal algorithm for joint optimization of signal to interference ratio (SIR) and transmit powers in a multi-cell wireless network. Previous solutions to this joint optimization problem have been either distributed but suboptimal, or optimal but centralized. The main issue that has been the research bottleneck is the complicated and coupled feasible SIR region constraint set. We resolve the complication through a re-parametrization in terms of the loads on the base stations, and an indication of the potential interference from mobile stations, which we term spillage.Third, we consider resource allocation jointly with resource consumers' willingness to pay for allocation. We probe first into the question of whom to price for network resource allocation. Pricing application and content-providers instead of or in addition to end-users for rate allocation is an evolving model on the Internet. The implications are heavily debated in telecom policy circles, and some advocates of "Network Neutrality" have opposed the ensuing price based differentiation in connectivity. However, pricing content providers can possibly subsidize the end-user's cost of connectivity, and the consequent increase in end-user demand can benefit ISPs and content providers. Our work provides a framework to quantify the precise trade-off in the distribution of benefits among ISPs, content-providers, and end-users.We then investigate pricing of Internet connectivity services in the context of a monopoly ISP selling broadband access to consumers. We first study the optimal combination of flat-rate and usage-based components in access price for maximization of ISP revenue subject to a capacity constraint on the resulting data-rate demand. Next, we consider time-varying consumer utilities for broadband data rates that can result in uneven demand for data-rate over time. Practical considerations limit the viability of altering prices over time to smoothen out the demanded data-rate. Despite such constraints on pricing, our analysis reveals that the ISP can retain the revenue by setting a low usage fee and dropping packets of consumer demanded data that exceed capacity. We also characterize the loss in ISP revenue if regulatory attention prevents such congestion management. Regulatory requirements further impose limitations on price discrimination across consumers, and we derive the revenue loss to the ISP from such restrictions.Through a combination of tools in optimization theory, matrix theory and economics, we push the envelope on the applicability of the well-known TCP algorithm, propose a novel distributed optimal algorithm with significant applicability in new generation wireless data networks, and incorporate pricing into resource allocation to analyze related regulatory and market effects.