2021 · 29 citations · 24 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsPath PlanningCombinatorial OptimizationNetwork OptimizationCoverage OptimizationEulerian PathsNetwork MeasurementNetwork TelemetryOrchestrationPath Optimization
Visibility is essential for operating and troubleshooting intricate networks. In-band Network Telemetry (INT) has been embedded in the latest merchant silicons to offer high-precision device and traffic state visibility. INT is actually an underlying technique and each INT instance covers only one monitoring path. The network-wide measurement coverage therefore requires a high-level orchestration to provision multiple INT paths. An optimal path planning is expected to produce a minimum number of paths with a minimum number of overlapping links. Eulerian trail has been used to solve the general problem. However, in production networks, the vantage points where one can deploy probes to start and terminate INT paths are constrained. In this work, we propose an optimal path planning algorithm, INT-probe, which achieves the network-wide telemetry coverage under the constraint of stationary probes. INT-probe formulates the constrained path planning into an extended multi-depot k-Chinese postman problem (MDCPP-set) and then reduces it to a solvable minimum weight perfect matching problem. We analyze algorithm's theoretical bound and the complexity. Extensive evaluation on both wide area networks and data center networks with different scales and topologies are conducted. We show INT-probe is efficient, high-performance, and practical for real-world deployment. For a large-scale data center networks with 1125 switches, INT-probe can generate 112 monitoring paths (reduced by 50.4 %) by allowing only 1.79% increase of the total path length, promptly resolving link failures within 744.71ms.
24
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Pat Bosshart, Dan Daly, Glen Gibb et al. · ACM SIGCOMM Computer Communication Review · 2014 · 2.8K citations
A scalable, commodity data center network architecture
Mohammad Al-Fares, Alexander Loukissas, Amin Vahdat · 2008 · 1.7K citations · Full text
SNDlib 1.0—Survivable Network Design Library
S. Orlowski, Roland Wessäly, Michał Pióro et al. · Networks · 2009 · 924 citations