Distributed Resource Allocation in Communication Networks.

The ever increasing size and autonomy of communication networks demand that the management of communication resources be distributed to individual nodes in the network. In this thesis, we develop distributed resource allocation techniques applied by individual nodes with the aim of optimizing various social objectives. We also investigate the outcome of resource allocation when every node only works to maximize its own benefit. We study distributed optimization specifically for wireless networks, where the traditional problems of routing and congestion control need to be considered in conjunction with power control. We formulate a general problem in which link capacities, traffic input rates, and traffic routes are jointly configured to minimize the sum of convex link costs. Using the scaled gradient projection method, we develop a suite of power control, congestion control, and routing algorithms which can be iterated by individual nodes to achieve the optimal configuration from any initial operating point. We then generalize the algorithms to optimize resource allocation across multiple frequencies. Operating wireless networks on multiple frequencies can avoid severe interference caused by a transmitter at co-located receivers. We derive the minimum number of frequencies and develop a distributed frequency allocation algorithm with which every transmitter and its co-located receivers can be activated on different frequencies. We also adapt the original algorithms to find the optimal network coding configuration in wireless networks. Despite the difference between network coding and routing, network coding subgraphs can be optimized using our node-based routing technique. Finally, we demonstrate the use of the power control algorithms to achieve throughput optimal control of wireless networks under the stochastic model. Rather than modeling the traffic as fluid flows, the stochastic model views the traffic as consisting of individual packets with random arrivals and dynamic queuing. We prove that the adaptive and iterative adjustment of the link service rates through the power control algorithms can stabilize the queues at all nodes whenever the arrival rates of the stochastic traffic are within the network throughput region. Rather than following certain algorithms to fulfill a social objective, selfish nodes seek to use their resources to their own advantage. We analyze this phenomenon in relay networks where nodes compete to forward traffic. The competition is modeled as a pricing game where nodes price their services and route their traffic to maximize individual profits. While the socially optimal routing can always be induced by an equilibrium, the pricing game in general also have inefficient equilibria. They arise in oligopolies due to the monopolistic pricing power of a superior relay. Pricing games of general topology suffer from the intrinsic multi-hop network structure, which may lead to arbitrarily inefficient equilibria.