CIF: Small: Computational Tools for Bounding Network Capacities

California Institute Of Technology, Pasadena CA

Investigators

Abstract

---- 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.