Communication networks are, increasingly, the backbone upon which the world's financial, educational, and governmental institutions rely. Surprisingly, very little is known about how much information current communication networks can carry. The absence of tools for characterizing the "capacities" of large, complex networks makes it difficult to determine how to improve the capabilities of current communication networks or to design better networks for the future. This research involves the development of new systematic strategies for building computational tools for characterizing the capacities of large networks.
This research involves bounding the capacity of a complex network by first factoring the network into individual components, then replacing those components by simpler models, and finally employing computational tools to bound the capacities of the modeling networks. Researchers create a library of component models by deriving both upper and lower bounding models for each component studied. Unlike prior mechanisms for characterizing the behaviors of individual channels, these upper and lower bounding models capture the full range of behaviors of an individual component. Thus the capacity of any network is bounded from above by the capacity of another network where each component is replaced by its upper bounding model and bounded from below by the capacity of a distinct network where each component is replaced by its lower bounding model. Researchers are developing models for both individual transmission devices like broadcast, multiple access, and interference channels and sub-networks built from component models. Modeling sub-networks allows networks to be analyzed hierarchically, yielding a technique that scales to very large networks.
Communication networks play a fundamental role in our society. They connect people to friends and institutions, enable commerce for companies and individuals, store health records for use by patients and their doctors, and enable governments to reach out to citizens and to each other. As a result, the success of our financial, governmental, educational, health, and community institutions is tied to the continuing growth and improvement of communication networks. To be successful, our networks must not only expand in their reach but also must increase in the amount of information that they can carry. The amount of information that a network can carry is called its capacity. Surprisingly little is known about how to find the capacity of modern communication networks or of future network designs. Tools for bounding network capacity are critical for understanding the limits of the communication systems that we already have in place, for learning to better use existing communication resources, and for building better networks in the future. For example, the availability of good tools for bounding network capacity would enable the direct capacity comparison of a variety of network designs, allowing us to make the best possible design decisions in building the communication networks of the future. Intellectual Merit: This grant focused on developing computationally efficient tools for analyzing the capacities of current networks and proposed networks for the future. The intellectual merit of the work performed is captured in a collection of scientific and technological advances made possible by the grant. These include new techniques for bounding the capacity of a network by finding upper and lower bounding models for its components. The bounding models developed under this grant have the property that replacing each component by its upper bounding model gives a new network whose capacity is an upper bound on the capacity of the original network and for which the capacity is more easily solved. Likewise, replacing a component by its lower bounding model gives a new network whose capacity is a lower bound on the capacity of the original network. Bounding models contrast with prior component characterizations that worked in isolation but failed to characterize the behavior of each network component inside the larger network in which they operated. Results include new bounding models that are far simpler to derive than previous model and are shown to be optimal for some component types. Optimal here means that no other model could better characterize the full range of behaviors of the given component. Other outcomes include proofs showing that the capacity of some very complicated networks (e.g., multple multicast networks, in which every transmitter sends messages to an arbitrary number of receivers) can be solved through the solution of simpler networks (e.g., multiple unicast networks, in which every transmitter sends information to a single receiver). Broader Impact: Since network communication technology affects so many aspects of our lives, the impact of technological developments in this area extends far beyond the technical field, impacting the very medium through which we stay connected with the world. The broader impact of the grant also includes changes to courses to incorporate the technological and scientific advances developed under the award and outreach in the form of lectures aimed at young students considering possible futures in STEM fields and tutoring for women and under-represented minorities.
