This research investigates communication strategies for time-varying networks, with the goal of developing a fundamental theory for analysis and control of network delay. While much is known about network throughput optimization, the delay problem is more complex and less understood. Delay-aware algorithms must be designed for very large systems and must be able to optimally adapt to environmentswhere future network traffic, link conditions, and mobile user locations are uncertain. This project seeks to establish mathematical techniques for computing tight delay bounds, and to develop scheduling and routing algorithms that achieve provably high throughput with order-optimal delay. This project also explores intelligent mechanisms for scheduling redundant packet information and for making use of (and controlling) network mobility. Indeed, although redundancy and mobility increase the complexity of decision options, both can be used advantageously to improve network performance.
This project also introduces a new topic of mathematical optimization: The study of controlling Lagrange multipliers. Specifically, it is known that network optimization is closely related to convex programming theory, where Lagrange multipliers can play a role analogous to queue backlogs and/or "network prices." However, there has been little research in the area of controlling the magnitude of the Lagrange multipliers that are used in an optimization problem. A general theory of controlled Lagrange multipliers is thus important to this study of network delay and for related problems of network pricing and economics. Such a theory may also prove useful in other optimization contexts, and may have broader applications to machine learning and online dynamic programming.
