The objective of this proposed research is for the development and analysis of message-passing algorithms that address large-scale optimization problems. Case studies involving applications in resource allocation and computer network monitoring will be conducted to validate ideas. Algorithms will be designed to address both convex and nonconvex optimization problems and to be executed in either centralized or asynchronous distributed formats. All variations will be considered in the case studies, which will address problem formulations that call for these features.
If successful, this research will lead to useful analytical and computational methods that complement the set of tools currently available from more traditional areas of optimization such as linear, convex, and integer programming. In the context of resource allocation, message-passing algorithms will provide asynchronous distributed algorithms that address nonconvex optimization. This can be used, for example, to design new protocols that govern transmission rates in communication networks with inelastic traffic. In the context of computer network monitoring, message-passing algorithms support efficient mechanisms through which flows can be efficiently estimated using a manageable number of hardware counters. This is necessary for billing, ensuring that service level agreements between providers are met, and for security. It is also useful in for traffic engineering and capacity planning.
