TL;DR
This paper tackles the challenge of cost-effectively deploying network traffic monitors in large IP networks. The authors propose an optimization framework and heuristics to find the best balance between monitoring coverage and deployment cost, demonstrating significant savings by covering a major portion of traffic rather than the entire network.
What Problem Does This Paper Address?
Operating large IP networks without a clear understanding of traffic flow is akin to navigating blindfolded. Accurate traffic monitoring is essential for crucial tasks like capacity planning, failure diagnosis, and security. However, deploying comprehensive monitoring infrastructure can be prohibitively expensive. This paper addresses the problem of optimizing the deployment of network traffic monitors, specifically focusing on NetFlow and CMON technologies, to achieve a desired level of traffic coverage while minimizing capital expenditure. The core challenge lies in determining where to deploy these monitors (which routers/interfaces for NetFlow, which links for CMON) and how many are needed to strike an optimal cost-coverage tradeoff.
Methods
The authors formulate the problem of optimal NetFlow deployment as an Optimal NetFlow Location Problem (ONLP). They propose two main approaches:
- Integer Linear Programming (ILP): This provides an optimal solution by modeling the problem with decision variables representing router/slot selection, upgrade costs, collector costs, and traffic coverage.
- Greedy Heuristics: Recognizing that ILP can be computationally expensive for large networks, they develop two greedy heuristics:
- Max-Plus (MP): This heuristic starts with no monitoring and iteratively adds the "best" NetFlow-enabled router slot based on a traffic-to-cost ratio until the coverage target is met.
- Least-Minus (LM): This heuristic starts with full monitoring and iteratively removes NetFlow-enabled slots and collectors, prioritizing those with the lowest traffic-to-cost ratio, until the coverage target is met or slightly exceeded.
The methodology is then extended to CMON deployment, and a comparison between the two technologies is presented.
Datasets
The paper uses real-world data from Sprint's North America IP backbone network (SNAIB-NET). This includes:
- Network topology information.
- Traffic snapshots captured via SNMP.
- Router performance characteristics and pricing for upgrades.
The authors note that while they used a single snapshot for traffic, in practice, multiple snapshots and averaging would be ideal to account for traffic fluctuations.
Key Insights and Ideas
- Partial Coverage is Cost-Effective: The most striking insight is that achieving significant cost savings is possible by aiming for high, but not 100%, traffic coverage. For instance, covering 95% of traffic can yield substantial cost reductions compared to covering 100%.
- GSR Upgrades Dominate NetFlow Costs: For NetFlow deployment, upgrading high-capacity routers (GSRs) is the primary cost driver, significantly outweighing 7500 series upgrades and collector costs, especially at higher coverage ratios.
- CMON's Modularity Advantage: CMON's link-based, modular nature makes it more cost-effective for scenarios requiring smaller coverage ratios or uni-directional monitoring, particularly on high-speed peering links.
- Heuristic Performance: The Least-Minus (LM) heuristic demonstrates excellent performance, achieving near-optimal results (within 1-2% difference) compared to the ILP, while the Max-Plus (MP) heuristic is slightly less optimal but still provides good results.
Key Results
- Significant Cost Savings: Covering 95% of network traffic with NetFlow resulted in approximately 55% cost savings compared to covering 100%.
- Heuristic Accuracy: The LM heuristic consistently achieved results within 1-2% of the optimal ILP solution for coverage ratios above 50%.
- NetFlow vs. CMON Cost Comparison:
- For customer traffic with bi-directional monitoring, NetFlow was slightly more expensive (around 4% at 100% coverage).
- When considering both customer and peering traffic, CMON was more cost-effective for lower coverage ratios (e.g., 20% coverage, NetFlow cost ~50% more than CMON). NetFlow became more cost-effective for higher coverage ratios.
- Cost Breakdown: For NetFlow, GSR upgrades accounted for the largest portion of the cost (around 89% for 100% coverage), with 7500 upgrades and collectors being significantly less.
Limitations and Future Work
- Static Traffic Assumption: The current model assumes static traffic conditions. The authors acknowledge that in practice, traffic fluctuates, and a more robust approach would involve multiple traffic snapshots.
- Simplified Cost Model: The paper primarily focuses on hardware costs. Future work could extend the model to include labor, real estate, and operational costs for a more comprehensive cost analysis.
- CMON Collector Cost: While the paper mentions CMON collector costs, the primary comparison focuses on hardware. The authors suggest that dense collector deployment for CMON is often unnecessary due to local processing capabilities, but a more detailed analysis of collector costs in various scenarios would be beneficial.
- Generalization: The authors suggest that the proposed methodology can be applied to other services and network types beyond NetFlow and CMON.
Summary updated