Principles and methods of adaptive network algorithm design under various quality-of-service requirements

Motivated by the increasing deployment of the real-time applications over various networks, we are interested in the design and analysis of new adaptive algorithms to satisfy their quality-of-service (QoS) requirements that are beyond the widely studied throughput performance. For example, most real-world applications are sensitive to the mean end-to-end delay they experience, interactive applications often have a stringent delay constraint, the VoIP applications need a certain fraction of their packets to be delivered successfully before a fixed deadline, and online video streaming applications may require a fixed bandwidth and regulated service rate.;However, unlike the more extensively studied throughput performance that is determined by the first-order statistics, such QoS requirements often relate to the higher-order statistics of the arrival and service processes in the network. Hence, they are highly challenging to characterize and analyze directly, and new approaches must be developed in the design of provably good algorithms in satisfying the aforementioned QoS requirements. In this dissertation, we address this deficiency by systematically exploring the principles and methods of adaptive network algorithm design to manage variety of challenging QoS requirements, including the traffic heterogeneity, delay, reliability, and service regularity, with theoretical guarantees.;Since the above QoS metrics are typically challenging to analyze, we utilize different frameworks and methods to overcome different types of QoS requirements. For example, in designing the adaptive network algorithm under real vs. non-real-time traffic heterogeneity, we utilize an optimization-based formulation, leading to a novel two-leveled prioritization queueing architecture that achieves the optimal load-balancing and utility maximization solution. In the direction of achieving low mean delay performance, we reveal and exploit a unique characteristic of a well-known dual solution of the joint congestion control and routing problem to develop an efficient adaptive routing scheme that avoids unnecessary loops and hence provides significant improvement in the mean delay performance.;While these design methods are based on appropriately formulated optimization frameworks, other QoS metrics necessitate the use of stochastic control methodologies, requiring the introduction and control of new dynamic variables into the system. For example, we add deficit counters for the deadline-constrained flows with delivery ratio requirements, whose value measures how this requirement is violated over time. In the challenging scenario of deadline-constrained multi-hop flows, we develop a novel queueing architecture in addition to deficit counters that are used by our adaptive algorithms to automatically adapt the service discipline to their deadline and reliability requirements. In the case of serving such deadline-constrained flows with channel coding capabilities over fading channels, an untraditional finite-horizon dynamic-programming approach is employed to solve the optimization problem. In the formulation and analysis of the service regularity performance, the novel parameter of time-since-last-service is introduced, which enables us to study the second moment behavior of the inter-service time by analyzing the mean of this new quantity.;Our investigations in these QoS metrics yield different adaptive algorithms with provable QoS performance. These results show the powerfulness and significance of the method of exploiting new elements in the system when designing adaptive algorithms to satisfy QoS requirements.