Packet scheduling and congestion control in communication networks: Applications to multimedia streaming and switching

Rapid advances in wired and wireless networking over the past decade have revolutionized the way in which we interface with the world to access and disseminate information. Communication networks like the Internet and the mobile cellular system have now become integral parts of modern day living. While data and voice services were prominent in past generation networks, next generation networks promise users a variety of real-time multimedia services such as video streaming, video teleconferencing etc. The tight performance requirements of multimedia applications, coupled with volatile system dynamics, render smart resource scheduling and management imperative to efficient network design and control.; This dissertation considers resource scheduling for supporting packet deadline sensitive multimedia traffic over communication networks. Two different scenarios, which serve as case studies to illustrate important scheduler design principles, are examined in great detail. The first scenario addresses deadline sensitive packet scheduling and power allocation for multimedia streaming on the downlink of cellular wireless systems. Parsimonious mathematical models are analyzed in a dynamic programming framework and the "geometry" of the optimal controls is leveraged to design practical scheduling algorithms. The second scenario addresses congestion control for traffic streams with inter-packet deadline constraints through input queued packet switches, a switching architecture widely deployed in Internet routers. In contrast to prior work where maximizing switch throughput was the primary objective, the emphasis here is on shaping the output of the switch in accordance with desired target profiles, an approach better suited to applications like video streaming. Besides proving theoretical structural results, the performance gains of the proposed algorithms vis-a-vis state-of-the-art benchmarks are demonstrated via experimental results. Apart from highlighting the performance gains achieved by efficient network resource management, this work emphasizes the importance of parsimonious modeling of complex stochastic systems for effective algorithm design.