MSIM Project: Estimation of the Source and Destination of a Network Transmission from Internally Sensed Intercepts

Estimation of the Source and Destination of a Network Transmission from Internally Sensed Intercepts

Project Title: Estimation of the Source and Destination of a Network Transmission from Internally Sensed Intercepts

Co-PI's Involved: Alfred O. Hero III,
Professor, Electrical Engineering & Computer Science, University of Michigan

Student: Derek Justice
Ph.D. Candidate (expected 2006), Electrical Engineering & Computer Science, University of Michigan

Project Description

We consider the problem of estimating the endpoints (source and destination) of a transmission in a network based on partial measurement of the transmission path. Sensors placed at various points within the network provide the basis for this reconstruction by indicating that a specific transmission has passed their assigned locations. During a training phase, test transmissions are made between various pairs of endpoints in the network and the sensors they activate are noted. From these possibly noisy measurements, we develop necessary constraints that any feasible network topology must satisfy. Randomized rounding of the solution to a semidefinite programming relaxation generated from the constraints is used to produce samples from the distribution of network topologies defined over the feasible set. When a subset of the deployed sensors are activated, corresponding to the occurrence of a transmission with unknown endpoints, a monte carlo approximation of the posterior distribution of source/destination pairs given the activated sensors is computed and used in maximum a posteriori estimation of the endpoints.

Fig. 1 : Example of an unknown network with sensors (red) on the links. Possible source and destination pairs are illustrated as (S1,D1) and (S2,D2).

References

1. Y. Vardi, “Network tomography: estimating the source-destination traffic intensities from link data,” J. Amer. Stat. Assoc., vol. 91, pp. 365–377, 1996.

2. M. Goemans and D. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM, vol. 42, no. 6, pp. 1115–1145, Nov. 1995.

3. J. Treichler, M. Larimore, S. Wood, and M. Rabbat, “Determining the topology of a telephone system using internally sensed network tomography,” Proc. of 11th Digital Signal Processing Workshop, Aug. 2004.

4. D. Justice and A.O. Hero (2006), "A binary linear programming reformulation of the graph edit distance for graph recognition," to appear in IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI).

5. D. Justice and A.O. Hero (2006), "Estimation of message source and destination from link intercepts," to appear in IEEE Trans. on Information Forensics and Security.