CAREER: Foundations of Network Design: Real-World Networks, Special Topologies, and Game Theory

University Of Maryland, College Park, College Park MD

Investigators

Abstract

The Internet has undergone tremendous growth recently, fueled by the emergence of user-generated video, TV- and movie-on-demand services, peer-to-peer file sharing, social networking, and rapid proliferation of smart phones. These new application mixes and the resulting characteristics of network traffic have raised numerous research challenges for practitioners working on various aspects of networks including construction, routing, and staged deployment. As a result, "network design" or more generally "networking," with its many variants, is one of the most active research areas in computer science. Theoretical modeling of networks plays a vital role in understanding computer and communication networks. Examples of such theoretical models that will be addressed further in this project are cost and efficiency optimizations with applications in Fiber Optic Networks, Content Distribution Networks (CDNs), Virtual Private Networks (VPNs), Cellular Networks, and Social Networks. The Principal Investigator will invent and use a variety of techniques in approximation and randomized algorithms, fixed parameter algorithms, algorithmic game theory, and his own Bidimensionality theory, to optimize cost and performance of these strategic networks. As a broader impact, the PI seeks to leverage his network of collaborators to apply these theoretical developments to the design of practical algorithms and mechanisms, to deploy them in real-world settings, and to perform experiments to characterize and explain their behavior and performance. The PI believes that variations of the algorithms designed in this project will be used in real networks, enabling faster networks and cheaper Internet access in practice. This is an especially important goal since the Internet in the U.S. is currently not as fast or cheap as in several other developed or even developing countries. The wealth of attractive open problems in foundations of network design provide, at one extreme, challenging research topics, and at the other extreme, intuitive and accessible problems to inspire students to enter research in computer science, mathematics, and economics. The educational thrust of this project is to actively engage undergraduate and graduate students in study of and research into network design foundations.