The emergence of rich interactive collaborative applications on desktop and mobile platforms demands a robust network infrastructure. The network must recover quickly from link and node failures and must do so while having only a small amount of information. This project seeks to develop scalable proactive failure recovery techniques that require only a constant factor increase in the information maintained at every node. The techniques developed in this project are applicable to circuit-switched and packet-switched networks. In order to improve the robustness of the network further, link and node performances may be monitored periodically by observing the behavior of end-to-end paths, referred to as network tomography. This project seeks to develop fundamental theories and practical algorithms for the identifiability of link and node metrics from end-to-end path observations. The expected results from this project include: (1) algorithms and protocols that may be employed in the data link and network layers of the protocols stack; (2) tools for evaluating different recovery and monitoring techniques; and (3) novel games based on the research problems, targeted at mobile platforms such as iPhone/iPod touch and Android-based devices. The results of the project will be integrated into the undergraduate and graduate networking and graph theory courses.

The intellectual merit of the project is in identifying the fundamental graph theoretical problems underlying the various techniques developed for recovering from multiple link failures and network tomography. The result will lead to new insights into network design, operation, and monitoring with guaranteed performance.

The results of this project will have significant broader impact. The algorithms developed for network tomography is applicable to similar problems in the fields of nanoelectronics, compressive sensing, and power systems management. The impact of games derived from the research concepts will reach beyond the intended audience, as the games will be made available through the iTunes App Store for world-wide dissemination and students will share the games their siblings, relatives, and friends.

National Science Foundation (NSF)
Division of Computer and Network Systems (CNS)
Standard Grant (Standard)
Application #
Program Officer
Joseph Lyles
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of Arizona
United States
Zip Code