Discrete optimization for network security and reliability.

摘要

Any network problems in essence equal to some principle questions in Discrete Mathematics, since all network elements can be abstracted as basic discrete structures, such as graphs, trees and permutations. One branch of discrete math, Graph Theory serves as abundant sources of theoretical support for network researches, from which people have been exploring since the last decade. However, the potential of another branch, Combinatorial Group Testing, has been overlooked, because of the intrinsic differences between its classic model and the practical network problems.;In this thesis, we attempt to fill the gap between Group Testing Theory and Network Optimization Problems, and then provide novel theoretical frameworks and efficient solutions through discrete optimizations for four network security and reliability problems. Specifically, we first provide a new size-constraint model for Group Testing, which thus can find many matches to practical network problems, and then propose an improvement over its traditional optimization solution. Then, we study two network security problems: Defending Application-Layer and Wireless Jamming Denial-of-Service Attacks and two reliability problems: Localizing All-Optical Network Link Failures and Assessing Network Topological Vulnerabilities. For each of these problems, we present a novel optimization framework, show its theoretical hardness, provide efficient algorithms with performance analysis, describe the implementation details and feasibility/scalability, and discuss over potential improvements and future directions.