Project 3-2: Scalable Design Methods for Topology Aware Networks

Principal Investigator: Amin Saberi (Stanford University)
(New project: 2010)

A complex military network must be effective and survivable in a highly mobile and dynamic environment. The goal of this project is to characterize the structural properties that affect the performance and scalability of data management and communication protocols. Algebraic graph theory will be used to define metrics that characterize global network performance using low-overhead distributed and local computation. Scalable algorithms will enable the elements of a system to efficiently identify whether the system is globally in a good state of connectivity or if there are "critical areas" in the network, including holes or narrow bridges.

Such an understanding of network structure will have several applications at the information dissemination level: a global understanding of the network topology allows local "greedy" methods for information discovery and brokerage to work effectively and in load-balance fashion. This structural understanding also helps with the implementation of mathematical methods because by helping to find the correct boundary conditions, establishing rendezvous points, and other factors.

AHPCRC researchers will work toward providing appropriate metrics for the connectivity of network topologies. This will enable network clients to know whether a given network configuration provides adequate conductance, or if large spectral gaps are present. Methods of maintaining network connectivity and discovering critical areas will be explored.