Optimization Method for Network Topology Discovery Based on Minimum Vertex Cover

The minimum vertex cover problem is a classical combinatorial optimization problem in graph theory, aimed at discovering the minimum set of vertices in a coverage graph. Software defined network is an emerging network architecture in recent years, where controllers are responsible for detecting the topology of the entire network and making decisions on data forwarding. The current network topology discovery algorithms have low efficiency and are difficult to carry large-scale network topology discovery functions. The network topology optimization method based on the minimum vertex cover algorithm first abstracts the network topology as an undirected graph, and then designs a minimum vertex cover algorithm based on a branch and bound framework to calculate the minimum vertex coverage of the network topology. Finally, the controller issues predefined flow table rules to quickly discover the network topology structure. The experiment has proven that the minimum vertex cover theory has good application in software defined network topology discovery, and can significantly improve discovery efficiency and increase network size.