ISU Electrical and Computer Engineering Archives

Techniques in Placing Network Monitors

Tang, Yongping (2007) Techniques in Placing Network Monitors. PhD thesis, Iowa State University.

Full text available as:

PDF - Registered users only - Requires Adobe Acrobat Reader or other PDF viewer.


Network monitoring systems are important components to protect networks. Due to large amount of data captured by monitors and the economical and technical constraints in adding monitors into network, research in monitor placement techniques is critical in network security. In this thesis, we first present a network monitor structure with the ability of data reduction to reduce the space requirement of monitor systems. Then we discuss the techniques for the optimal placement of passive monitors in AS level and router level topologies where there are constraints on the number of available monitors for deployment. Arithmetic coding is used in data reduction and statistical models of the data being captured are provided. For monitor placement in the AS level topology, we first define average entropy and worst-case entropy to describe the remaining uncertainty of locating the origin of an attack given the monitors work perfectly, and use edge observed graph to present the possible deployment. Heuristic methods based on graph centrality to find the optimal placement with the minimized entropy are provided. For monitor placement in the router level topology, we set up a network model including routing strategies and threat model for generic network topologies and define the monitor placement problem as maximizing the observation of attack events. Results of heuristic solutions and greedy algorithm are compared. Monitor placement problems for both levels of topologies are proved to be NP-complete problems. Because of the existence of asymmetric routing in Internet and the need of bidirectional data for stepping-stone analysis, we extended our research to capture bidirectional traffic via monitor placement. Greedy placement algorithms are provided for bi-directional traffic capturing. Experiment results are compared to demonstrate the tradeoffs in these algorithms. In our research, we also notice that it is hard to get network topologies with routing information, especially asymmetric routing information. As a result, we introduce asymmetric routing simulation techniques, which use the network topology generator as the data source, and provide simulation algorithms to generate the asymmetric routing on these topologies. The contribution from this research include: (1) Network monitor with data reduction, (2) Monitor placement in AS-level network topologies, (3) Monitor placement in router-level network topologies, (4) Algorithms to capture bi-directional traffic through monitor placement and (5) Simulation of network routing asymmetry.

EPrint Type:Thesis (PhD)
Uncontrolled Keywords:Data reduction, Monitor placement, Asymmetric routing simulation
Subjects:Computer Engineering > INFORMATION SYSTEMS SECURITY & NETWORKING > Computer Networking and Security
ID Code:381
Identification Number:Identification Number UNSPECIFIED
Deposited By:Yongping Tang
Deposited On:22 November 2007

Archive Staff Only: edit this record