Models and methods for local area network topology discovery with incomplete data

A lot of network management tasks require a description of the logical and physical computer network topology. Obtaining such a description in an automatic way is complicated due to the possibility of incompleteness and incorrectness of the initial data on the network structure. This article provides a study on the properties of incomplete initial data on network device connectivity on the link layer. Methods for generalized handling of the heterogeneous input data on the link layer are included. We describe models and methods for deriving a missing part of the data, as well as the condition in which it is possible to get a single correct network topology description. The article includes algorithms for building a link layer topology description from incomplete data when this data is possible to fulfill up to the required level. Also, we provide methods for detecting and resolving an ambiguity in the data and methods for improving incorrect initial data. Tests and evaluations provided in the article demonstrate the applicability and effectiveness of the build methods for discovering various heterogeneous real-life networks. Additionally, we show advantages of the provided methods over the previous analogs: our methods are able to derive up to 99% data on link layer connectivity in polynomial time; able to provide a correct solution from an ambiguous data.