16 April 2020 in IEEE/ACM Transactions on Networking
Programmable network switches promise flexibility and high throughput, enabling applications such as load balancing and traffic engineering. Network measurement is a fundamental building block for such applications, including tasks such as the identification of heavy hitters (largest flows) or the detection of traffic changes. However, high-throughput packet processing architectures place certain limitations on the programming model, such as restricted branching, limited capability for memory access, and a limited number of processing stages. These limitations restrict the types of measurement algorithms that can run on programmable switches. In this paper, we focus on the Reconfigurable Match Tables (RMT) programmable high-throughput switch architecture, and carefully examine its constraints on designing measurement algorithms. We demonstrate our findings while solving the heavy hitter problem. We introduce PRECISION, an algorithm that uses Partial Recirculation to find top flows on a programmable switch. By recirculating a small fraction of packets, PRECISION simplifies the access to stateful memory to conform with RMT limitations and achieves higher accuracy than previous heavy hitter detection algorithms that avoid recirculation. We also evaluate each of the adaptations made by PRECISION and analyze its effect on the measurement accuracy. Finally, we suggest two algorithms for the hierarchical heavy hitters detection problem in which the goal is identifying the subnets that send excessive traffic and are potentially malicious. To the best of our knowledge, our work is the first to do so on RMT switches.
10 June 2019 in IEEE/ACM Transactions on Networking
Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) -a novel algorithm for the frequency, top-k, and byte volume estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives, for the frequency estimation problem, by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads' skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. In Addition, we present d-way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.
9 October 2023 in IEEE/ACM Transactions on Networking
Network operators want to enforce fair bandwidth sharing between users without solely relying on congestion control running on end-user devices. However, in edge networks (e.g., 5G), the number of user devices sharing a bottleneck link far exceeds the number of queues supported by today’s switch hardware; even accurately tracking per-user sending rates may become too resource-intensive. Meanwhile, traditional software-based queuing on CPUs struggles to meet the high throughput and low latency demanded by 5G users. We propose (), a per-user bandwidth limit enforcer that runs fully in the data plane of commodity switches. tracks each user’s approximate traffic rate and compares it against a bandwidth limit, which is iteratively updated via a real-time feedback loop to achieve max-min fairness across users. Using a novel sketch data structure, avoids storing per-user state, and therefore scales to thousands of slices and millions of users. Furthermore, supports network slicing, where each slice has a guaranteed share of the bandwidth that can be scavenged by other slices when under-utilized. Evaluation shows can achieve fair bandwidth allocation within 3.1ms, 13x faster than prior data-plane hierarchical schedulers.
25 November 2024 in Proceedings of the ACM on Networking
Traffic monitoring in the dataplane is vital for reacting to network events such as microbursts, incast, and attacks. However, current solutions are constrained by the limited resources available on modern ASICs and don't provide the flexibility required to identify repeating patterns, such as applications whose flows communicate with a server at regular intervals. While such flexibility can be achieved using a co-processing CPU, it is generally too slow to provide insights quickly enough. In this paper, we show how an FPGA co-processor placed alongside the switching pipeline enables flexible traffic monitoring at data plane rates. While FPGAs have large memory and expressive processing, their throughput is significantly lower than switch ASICs. To bridge the throughput gap, we split query execution between the switch and FPGA and present methods that prevent processing all packets in FPGA. As a result, our system misses up to 5.0x fewer DDoS attack vectors than ACC-Turbo, the state-of-the-art on-switch solution, and up to 24% fewer microburst-contributing flows for the same precision rate.
1 October 2016 in Journal of Applied Remote Sensing
The high dimensionality of hyperspectral images (HSIs) with significant levels of redundancy and noise is a pervasive problem that creates a heavy burden and many inconveniences in terms of accuracy and efficiency for all the subsequent applications. To address this problem, we proposed an adaptive-boundary adjustment-based groupwise band-categorization (BC) framework that classifies bands by the information contained within each band and redundant/noisy components without compromising the original content from the raw HSI. Since HSI labels are difficult to collect, an unsupervised spectral-spatial adaptive band-noise factor-based formulation is devised for BC based on the measurement of boundary movement/adjustment and band correlation. Robust clustering and boundary-adjustment-based methods involve two key issues: band correlation and band preference. Our proposed method contemplates band correlation and band synergy, and band preference is defined by the discriminative information contained in each band. According to different information-distribution levels, an adaptive mechanism is proposed to retain the spectral correlations in spectral dimensions and match the actual structure in spatial dimensions. The proposed method is based on the observation that clustering and boundary adjustment techniques are sensitive to noise and redundancy, which can effectively contribute to estimates and help classify the bands. Comprehensive experimental results on challenging airborne visible/infrared-imaging spectrometer datasets from Indian Pines, Moffett Field, and Salinas demonstrate the significant advancement in these two applications and show the reliability and effectiveness of the proposed framework without compromising the informative bands. Because of its usefulness, BC can be successfully applied to many practical applications of hyperspectral remote sensing. Effective application of the proposed framework is demonstrated by applying it on HSI classification and also for estimating the noise. The ability of the method to characterize the bands along with the noise estimation of HSIs is of significant benefit for subsequent remote-sensing techniques.