Non-Overlapped Network Graph Coverage Algorithm For In-band Network Telemetry

Today's data center networks have become larger as the deployment of diverse cloud services has increased.As the network size continues to grow,fine-grained network monitoring is a prerequisite for network reliability and closed-loop traffic control.However,due to the continuous interaction between the control plane and the data plane,and limited CPU capabilities,such a monitoring mechanism is coarse-grained and cause a large query delay that cannot scale well in modern networks with high-density data center network with drastic traffic dynamics.In order to increase the problem of the scalability,In-band network telemetry(INT)has been proposed by P4 Language Consortium(P4.org)which provides real-time data plane monitoring.In this thesis,we raise the concept of the wide network telemetry and propose to use a routing path generation policy to solve the problem.In WINT system,we can accurately control each probing paths and thus,we can develop a diverse INT path planning algorithm for non-overlapped INT path generation that covers the entire network graph with minimum path number and give an exhaustive analysis of algorithm run-time complexity.Here,we first propose a simple algorithm based on depth-first search(DFS)which is simple but time-efficient.Secondly an Euler trail-based algorithm that optimally generates non-overlapped INT paths with a minimum path number.To achieve better load balancing,the classic data center network topology is compatible and there are several multi-path topology patterns.So INT-paths is very suitable for the deployment in Data Center network.Additionally,the result shows that the execution time of Euler is greater than DFS.Because the Euler is more sensitive to odd vertex and generated minimum INT path number which cover the entire network and also give an exhaustive analysis of algorithm run-time complexity.