One critical step to successfully integrate wireless data networks to the high-speed wired backbone is the design of network control policies that efficiently utilize resources to provide Quality of Service (QoS) to the users in the integrated networks. Such a design has remained a challenge since wireless networks are time-varying in nature, not only in terms of user/packet arrivals but also in terms of physical channel conditions and access opportunities. In this thesis, we study the stochastic control of time-varying networks to design efficient scheduling and resource allocation policies. In particular, in Chapter 3, we focus on a broad class of control policies that work based on a pick-and-compare principle for networks with time-varying channels. By trading the throughput for complexity and memory requirement, these policies require less complexity compared to the well-investigated throughput-optimal Generalized Maximum Weight Matching (GMWM) policy and also require only linear-memory storage with the number of data-flows. Through Lyapunov analysis tools, we characterize the stability region and delay performance of the studied policies and show how they vary in response to the channel variations. In Chapter 4, we go into further detail and consider the problem of network control from a new perspective through which we carefully incorporate the time-efficiency of underlying scheduling algorithms. Specifically, we develop a policy that dynamically adjusts the time given to the available scheduling algorithms according to queue-backlog and channel correlations. We study the resulting stability region of developed policy and show that the region is at least as large as the one for any static policy. Finally, motivated by the current under-utilization of wireless spectrum, in Chapter 5, we investigate the control of cognitive radio networks as a special example of networks that provide time-varying access opportunities. We assume that users dynamically join and leave the network and may have different utility functions, or could collaborate for a common purpose. We develop a policy that performs joint admission and resource control and works for any user load, either inside or outside the capacity region. Through Lyapunov Optimization techniques, we show that the developed policy can achieve a utility performance arbitrarily close to the optimality with a tradeoff in the average service delay of admitted users.

Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).

Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).