Graph identification techniques applied to network management problems
Isabelle M. Rouvellou · 1993
Communication networks have increased dramatically in size and complexity in the last few years. Furthermore, they tend to be more and more dynamic. Meanwhile, our dependence on networks has also drastically increased. The field of network management has thus drawn a wide interest in the industry and research. This thesis proposes new approaches to two network management problems: network topology identification and alarm correlation. In both cases, graph identification techniques are used. In dynamic networks, a precise and timely knowledge of the topology is critical for network management and control (e.g., routing). If every network node could instantly provide reliable information about itself and its neighbors, it would be relatively easy to assemble this information and derive the overall network topology. However, both the assumptions of correctness and instantaneous delivery of the information do not hold in practice. We thus address the problem of identifying the topology of a network (i.e., a graph) from noisy data collected at some node. Our model describes and relates the network topology and the collected data using a phrase-structured grammar. We reduce our problem to a combinatorial optimization problem and propose a suboptimal pseudo polynomial-time algorithm which yields reasonable solutions as shown by a range of examples. In today's networks, a large number of alarms exist to signal any abnormal network behavior and a network fault typically results in a number of correlated observed alarms. Thus, a major problem in fault management is of correlating these different alarms and identifying their source. This problem has been so far handled from a model-based expert system point of view. We propose a new approach where each fault is modeled as a stochastic grammar (represented by a probabilistic graph). Alarm sequences then correspond to sentences generated by the grammar. The structure of each grammar is learned automatically from the history of data associated with given faults. By classifying new alarm sequences as members of particular grammars, we then are able to identify the occurrence of possibly simultaneous faults. This method was tested on data from a real network.