While secure efficient operation of computer networks requires cost-effective line-rate packet classification, network programmability strengthens this need. A promising approach is to transform a packet classifier to a semantically equivalent representation that supports more effective classification. This paper explores transformation of ternary classifiers to equivalent prefix representations so that classification can benefit from efficient Longest Prefix Match solutions. We propose the property of prefix disjointness and design PREDICAT, a method that leverages this new property in combination with a variety of existing techniques to convert an arbitrary ternary classifier to an equivalent prefix representation. The paper analyzes prefix disjointness and evaluates PREDICAT against state-of-the-art transformation alternatives on a packet classification benchmark in regard to the number of lookups. The evaluation shows that PREDICAT outperforms a ternary-to-binary method by up to an order of magnitude, improves on another ternary-to-prefix solution by up to a factor of 5, and performs similarly to a ternary-to-ternary approach that requires costly power-hungry Ternary Content-Addressable Memories to efficiently handle the resulting ternary representation.

We introduce a novel representation of packet classifiers allowing to operate on partially available input data varying dynamically. For a given packet classifier, availability of fields or complexity of field computations, and free target specific resources, the proposed infrastructure computes a classifier representation satisfying performance and robustness requirements. We show the feasibility to reconstruct a classification result in this noisy environment, allowing for the improvement of performance and the achievement of additional robustness levels of network infrastructure. Our results are supported by extensive evaluations in various settings where only a partial input is available.

Modern datacenter transports are required to support latency constraints, usually represented by various forms of flow completion time (FCT). Most implemented congestion control mechanisms that minimize FCT are based on SRPT priorities (e.g., pFabric and Homa). However, SRPT-based scheduling requires prior knowledge of flow sizes, making this discipline problematic in general. Non-SRPT-based alternatives such as LAS and PIAS are able to cope with this level of uncertainty but suffer from their own limitations: LAS can lead to significant starvation of concurrent elephant flows, while PIAS requires a centralized entity for correct settings. In this work, we generalize SRPT-based scheduling to allow flows with known and unknown sizes to sojourn at the same time. We not only show analytic properties of this generalization but rigorously prove important properties of non-SRPT alternatives with competitive analysis. Based on the proposed SRPT generalization, we introduce a new ASCC congestion control. Our main goal is not to propose yet another congestion control but to identify preferable and pathological traffic patterns with unknown flow sizes for various scheduling disciplines. Our observations are validated by an extensive evaluation study.

In-band real-time telemetry is a promising direction for management of modern programmable networks. While network noise in the form of packet reordering and loss affects inband collection of distributed state, there is a need to compute telemetry functions on the collected state correctly despite the network noise. To address this common need, we propose TeleNoise that equips each packet with few sync bits and offers primitives of group affiliation and group completion to support noise-resilient computation of per-group telemetry functions. This paper gives real-world examples of such functions, elaborates on the role of TeleNoise in a modular in-band telemetry architecture, and presents algorithms for the two TeleNoise primitives. We derive analytical guarantees on correctness and performance of the algorithms and report a trace-driven evaluation that corroborates the effective low-overhead profile of TeleNoise, e.g., the assuredly correct operation and at most 1.6 packets of the average measurement lag for 12-packet groups and 3 sync bits.

To simplify definitions of network-wide behaviors (e.g., in datacenter transports), networks are often represented by virtual switches. In most cases, the buffering architecture of a representing virtual switch is inherited from analytic models implementing the desired properties, and is completely decoupled from the represented network topology. Thus, it is unclear how well the network infrastructure is exploited. This paper makes the first attempt in understanding which buffering architectures can best represent a given network, and how buffer management decisions can be mapped back to a represented network.

Unrelenting traffic growth, device heterogeneity, and load unevenness create scalability challenges for traffic monitoring. In this paper, we propose Robust Distributed Computation (RoDiC), a new approach that addresses these challenges by shifting a portion of the monitoring-task execution from an overloaded network element to another element that has spare resources. Moving the entire execution of the task away from the overloaded element might be infeasible because execution on multiple elements is inherent in the task or requires at least partial participation by the designated overloaded element. Furthermore, distributed execution of a stateful task has to be resilient to network noise in the form of packet reordering and loss. The RoDiC approach relies on two main principles of packet grouping and state overlap to support exact robust distributed monitoring of traffic flows under network noise. RoDiC uses an open-loop paradigm that does not add any control packets, communicates flow state in-band by appending few control bits to packets of monitored flows, and keeps measurement latency low. We apply RoDiC to the problem of flow-size computation and discuss how to instantiate our general technique for real-time packet-loss telemetry. The paper develops robust algorithms, proves their correctness and performance properties, and reports an evaluation driven by realistic traffic traces. The RoDiC algorithms successfully distribute the monitoring-task load while keeping the memory and computation overhead low.

Performing exact computations can require significant resources. Approximate computing allows to alleviate resource constraints, sacrificing the accuracy of results. In this work, we consider a generalization of the classical packet classification problem. Our major contribution is to introduce representations of approximate packet classifiers with controlled accuracy and optimization techniques to reduce classifier sizes exploiting this new level of flexibility. In this work, we propose methods constructing efficient approximate representations for both LPM (longest prefix match) classifiers and classifiers with general ternary-bit filters. We validate our theoretical results with a comprehensive evaluation study showing that a small error in the actions of a classifier can lead to significant memory reductions, often comparable to the best possible theoretical reduction in the trivial case when all rules have the same action.

Deep Packet Inspection (DPI) is an essential building block implementing various services on data plane [5]. Usually, DPI engines are centered around efficient implementation of regular expressions both from the required memory and lookup time perspectives. In this paper, we explore and generalize original approaches used for packet classifiers [7] to regular expressions. Our preliminary results establish a promising direction for the efficient implementation of DPI engines.

Growing expressiveness of services increases the size of a manageable state at the network data plane. A service policy is an ordered set of classification patterns (classes) with actions; the same class can appear in multiple policies. Previous studies mostly concentrated on efficient representations of a single policy instance. In this work, we study space efficiency of multiple policies, cutting down a classifier size by sharing instances of classes between policies that contain them. In this paper we identify conditions for such sharing, propose efficient algorithms and analyze them analytically. The proposed representations can be deployed transparently on existing packet processing engines. Our results are supported by extensive evaluations.

Scalable monitoring of traffic flows faces challenges posed by unrelenting traffic growth, device heterogeneity, and load unevenness. We explore an approach that tackles these challenges by shifting a portion of the monitoring-task execution from an overloaded network element to another element that has spare resources. Moving the entire execution of the task to a lightly loaded element might be infeasible because execution on multiple elements is inherent in the task or requires at least partial participation by the particular overloaded element (e.g., flow-size computation at the ingress element for billing purposes). Distributed execution of a stateful traffic-monitoring task has to be robust against packet reordering or loss, i.e., network noise. This paper designs robust traffic monitoring where the goal is to determine a flow metric for each flow exactly in spite of network noise. We follow the open-loop paradigm that does not add any control packets, communicates flow state in-band by appending few (on the order of 2 or 4) control bits to packets of the monitored flows, and keeps latency low. We consider the task of flow-size computation, analytically derive conditions assuring correct operation of the designed algorithms, and evaluate the algorithms on realistic traffic traces. The algorithms successfully distribute the monitoring-task load without imposing significant computation or storage overhead.

Performing exact computations can require significant resources. Approximate computing allows to alleviate resource constraints, sacrificing the accuracy of results. In this work, we consider a generalization of the classical packet classification problem. Our major contribution is to introduce various representations for approximate packet classifiers with controlled accuracy and optimization techniques to reduce classifier sizes exploiting this new level of flexibility. We validate our theoretical results with a comprehensive evaluation study.

Growing expressiveness of services increases the size of a manageable state at the network data plane. A service policy is an ordered set of classification patterns (classes) with actions; the same class can appear in multiple policies. Previous studies mostly concentrated on efficient representations of a single policy instance. In this work, we study space efficiency of multiple policies, cutting down a classifier size by sharing instances of classes between policies that contain them. In this paper we identify conditions for such sharing, propose efficient algorithms and analyze them analytically. The proposed representations can be deployed transparently on existing packet processing engines. Our results are supported by extensive evaluations.