Robust Sketch Orchestration in Programmable Networks

Date
2025-01-15
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

As modern networks grow in scale and speed, sketch-based algorithms have become essential for achieving accurate and low-overhead network monitoring. These algorithms enable efficient data summarization, allowing network operators to monitor traffic patterns without placing significant computational or memory demands on network devices. However, existing solutions for sketch-based network monitoring assume that traffic rates are fixed and known in advance. This assumption, while simplifying the monitoring process, fails to reflect the dynamic nature of real-world traffic, leading to degraded monitoring accuracy. In this thesis, we propose a novel approach for coordinated sketch placement on programmable network devices, such as switches and SmartNICs, without relying on the fixed traffic rate assumption. Instead, we consider scenarios where only statistical information about traffic rates, such as their means and variances, is available. To this end, we show that the problem can be formulated as an integer second-order cone program (ISOCP). Given the computational challenges of solving such optimization problems, especially in large-scale networks, we introduce an approximation technique to transform the problem into a linear formulation. This approximation not only reduces computational complexity but also enables efficient solutions for large instances of the problem using standard optimization tools. Our evaluations, conducted with realistic workloads and network configurations, demonstrate that, by accounting for dynamic traffic rates, our approach can increase monitoring accuracy in the network by up to 2× across different workloads compared to the existing solutions that do not explicitly consider these dynamics.

Description
Keywords
Network monitoring, Optimization, Dynamic Flow Rates
Citation
Erfanmanesh, Z. (2025). Robust sketch orchestration in programmable networks (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.