Robust Sketch Orchestration in Programmable Networks

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.

Name thesis:degree_name

Master of Science (MSc)

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher.institution

Graduate Studies

Year dc:date.issued

2025

Author dc:creator

• Erfanmanesh, Zeinab

Advisor dc:contributor.advisor

• Ghaderi, Majid

Committee members dc:contributor.committeemember

• Wang, Mea
• Fapojuwo, Abraham

• Network monitoring
• Optimization
• Dynamic Flow Rates

Statement dc:rights

• University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.

Language dc:language.iso

en

DOI

https://dx.doi.org/10.11575/PRISM/48109

OAI identifier oai:identifier

oai:ucalgary.scholaris.ca:1880/120500