Hash-based data structures such as Bloom filters are widely used in network systems for tasks including caching, anomaly detection, and machine learning pipelines. They typically provide binary indications of whether an element belongs to a set of interest, e.g., the contents of a cache. When uncertainty arises due to hash collisions, a positive indication is returned to avoid false negatives. We argue that the certainty associated with such indications can itself be useful information. This work focuses on Counting Bloom Filters (CBFs), a Bloom-filter variant that maintains counters rather than bits. Besides supporting insertions and deletions, these counters provide additional information that can be used to estimate the certainty of positive membership indications. We show how this certainty signal can be exploited in architectures that combine Bloom Filters with machine learning (ML) models.

Fixed-time strategy is a common approach in signal traffic control, characterized by simple and periodic signal plans that are easy to implement without detection mechanisms. A major step in the design of such plans refers to the grouping of the day hours such that the same plan applies for several consecutive hours. The efficacy of the plan, measured by vehicle delays, relies on the matching of traffic with the fixed plan. Accordingly, the time-of-day breakpoints between plans are selected based on the variability of the traffic within each group. The paper studies the selection of time-of-day breakpoints (TODs) based on real traffic characteristics from two cities. Motivated by the Google Green Light project, this study presents an approach to compute TODs based on aggregated traffic statistics computed from anonymized trajectories from navigation applications. We evaluate an optimal dynamic programming algorithm to compute time-of-day breakpoints at an intersection, based on traffic variability among hours. We analyze typical forms of efficient time-of-day breakpoints and examine the impact of the number of daily plans on the ability to predict traffic behavior. We refer to various metrics to measure the variability of the traffic within sets of hours concerning the amount of traffic and its distribution among various movements. We measure the dissimilarity of the time-of-day breakpoints when computed for the different metrics. We also address the joint computation of TODs in adjacent intersections to improve coordination potential.

Access Control Lists (ACLs) are crucial for ensuring the security and integrity of modern cloud and carrier networks by regulating access to sensitive information and resources. However, previous software and hardware implementations no longer meet the requirements of modern datacenters. The emergence of FPGA-based SmartNICs presents an opportunity to offload ACL functions from the host CPU, leading to improved network performance in datacenter applications. However, previous FPGA-based ACL designs lacked the necessary flexibility to support different rulesets without hardware reconfiguration while maintaining high performance. In this paper, we propose HACL, a heterogeneous and adaptive architecture for decision-tree-based ACL engine on FPGA. By employing techniques such as tree decomposition and recirculated pipeline scheduling, HACL can accommodate various rulesets without reconfiguring the underlying architecture. To facilitate the efficient mapping of different decision trees to memory and optimize the throughput of a ruleset, we also introduce a heterogeneous framework with a compiler in CPU platform for HACL. We implement HACL on a typical SmartNIC and evaluate its performance. The results demonstrate that HACL achieves a throughput exceeding 260 Mpps when processing 100K-scale ACL rulesets, with low hardware resource utilization. By integrating more engines, HACL can achieve even higher throughput and support larger rulesets.

Payment channels are auspicious candidates in layer-2 solutions to reduce the number of on-chain transactions on traditional blockchains and increase transaction throughput. To construct payment channels, peers lock funds on 2-of-2 multisig addresses and open channels between one another to transact via instant peer-to-peer transactions. Transactions between peers without a direct channel are made possible by routing the payment over a series of adjacent channels. In certain cases, this can lead to relatively low transaction success rates and high transaction fees. In this work, we introduce pliability to constructing payment channels and graft edges with more than two endpoints into the payment graph. We refer to these constructions as hyperedges. We present hyperedge-based topologies to form hypergraphs and compare them to Bitcoin’s Lightning network and other state-of-the-art solutions. The results demonstrate that hyperedge-based implementations can both increase transaction success rate, in addition to decreasing the network cost by more than 50% compared to that of the Lightning Network.

Cryptocurrencies have gained high popularity in recent years, with over 9000 of them, including major ones such as Bitcoin and Ether. Each cryptocurrency is implemented on one blockchain or over several such networks. Recently, various technologies known as blockchain interoperability have been developed to connect these different blockchains and create an interconnected blockchain ecosystem. This paper aims to provide insights on the blockchain ecosystem and the connection between blockchains that we refer to as the interoperability graph. Our approach is based on the analysis of the correlation between cryptocurrencies implemented over the different blockchains. We examine over 4800 cryptocurrencies implemented on 76 blockchains and their daily prices over a year. This experimental study has potential implications for decentralized finance (DeFi), including portfolio investment strategies and risk management.

In blockchain networks, transaction latency is crucial for determining the quality of service (QoS). The latency of a transaction is measured as the time between its issuance and its inclusion in a block in the chain. A block proposer often prioritizes transactions with higher fees or transactions from accounts it is associated with, to minimize their latencies. To maintain fairness among transactions, a block proposer is expected to select the included transactions randomly. The random selection might cause some transactions to experience high latency following the variance in the time a transaction waits until it is selected. We suggest an alternative, age-aware approach towards fairness so that transaction priority is increased upon observing a large waiting time. We explain that a challenge with this approach is that the age of a transaction is not absolute due to transaction propagation. Moreover, a node might present its transactions as older to obtain priority. We describe a new technique to enforce a fair block selection while prioritizing transactions that observed high latency. The technique is based on various declaration schemes in which a node declares its pending transactions, providing the ability to validate transaction age. By evaluating the solutions on Ethereum data and synthetic data of various scenarios, we demonstrate the advantages of the approach under realistic conditions and understand its potential impact to maintain fairness and reduce tail latency.

Non-fungible tokens (NFTs) are digital assets representing ownership or proof of authenticity of a unique item. NFTs are blockchain-based and rely on smart contracts. The increase in duplicate NFTs in recent years brings the need for discovery tools for forged NFTs, some of which include using image hash functions. Though the problem of image duplication is widely discussed, detecting NFT duplications requires using fast detection methods as a new NFT image needs to be compared with the entire NFT history on the blockchain. In this paper, we analyze the performance of several image-hash functions, examine the cases where each function performs well, and evaluate multiple image-hash-functions-based NFT duplication detectors. Our approach achieves high accuracy in detecting NFT duplications and demonstrates that using several hash functions rather than one increases the ability to detect duplications.

Blockchain networks suffer from a critical scalability problem that is often expressed in two dimensions: the size of the network state and the computational overhead in processing transactions as part of the network update. This paper surveys two major families of solutions known as sketches and rollups that both rely on aggregation methods. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Rollups play in a different form and refer to aggregation of the execution of multiple transactions to allow high transaction rates and low fees. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. In addition, rollups are implemented in several forms to allow high transaction rates through offloading parts of the execution out of the blockchain while keeping its security. This paper overviews the basics of sketches and rollups and provides a comprehensive survey on the wide range of existing applications of the two families in blockchains.

Blockchain leader-based protocols elect leaders for proposing the next block of transactions. Proposed blocks need to pass a validation routine in order to be added to the blockchain. Proposers may prioritize certain transactions based on their fees or accounts, which enables attackers to gain profits through block building, while simultaneously causing negative impacts on other users. A fair block selection follows a random selection of pending transactions among those that a proposer is aware of. We propose CFTO, a protocol that aims at encouraging fair block selection in a leader-based blockchain network while taking into account real network conditions, such as the network’s topology structure and the forwarding protocol. CFTO offers two main contributions. First, it provides incentives for acting honestly and diminishing malicious and dishonest nodes. To accomplish this, we use a reputation system, whereby each node is given a reputation score based on its actions. Second, it consists of an algorithm that evaluates the proposed blocks based on the zone structure of the network. Furthermore, we adapt the evaluation algorithm to fit the additional order constraints implied in Ethereum transaction ordering. We demonstrate the improved accuracy of CFTO in detecting fair blocks, in terms of increasing the probability of approving fair blocks and decreasing the probability of approving unfair blocks, by implementing experiments and comparing them with Helix (Yakira et al., 2021), a previously proposed consensus algorithm for fair block selection. As part of our experiments, we also compare certain features with those of previous studies.

Payment channel networks (PCNs) are a leading method to scale the transaction throughput in cryptocurrencies. Two participants can use a bidirectional payment channel for making multiple mutual payments without committing them to the blockchain. Opening a payment channel is a slow operation that involves an on-chain transaction locking a certain amount of funds. These aspects limit the number of channels that can be opened or maintained. Users may route payments through a multi-hop path and thus avoid opening and maintaining a channel for each new destination. Unlike regular networks, in PCNs capacity depends on the usage patterns and, moreover, channels may become unidirectional. Since payments often fail due to channel depletion, a protection scheme to overcome failures is of interest. We define the stopping time of a payment channel as the time at which the channel becomes depleted. We analyze the mean stopping time of a channel as well as that of a network with a set of channels and examine the stopping time of channels in particular topologies. We then propose a scheme for optimizing the capacity distribution among the channels in order to increase the minimal stopping time in the network. We conduct experiments and demonstrate the accuracy of our model and the efficiency of the proposed optimization scheme.

Payment channel networks (PCNs), also known as off-chain networks, implement a common approach to deal with the scalability problem of blockchain networks. They enable users to execute payments without committing them to the blockchain by relying on predefined payment channels. A pair of users can employ a payment even without a direct channel between them, by routing the payment via payment channels involving other intermediate users. Users, together with the channels, form a graph known as the off-chain network topology. The off-chain topology and the payment characteristics affect network performance such as the average number of intermediate users a payment is routed through or the values of transaction fees. In this paper, we study two basic problems in payment channel network design. First, efficiently mapping users to an off-chain topology with a known structure. Second, constructing a topology with a bounded number of channels that can serve users well with associated payments. We design algorithms for both problems while considering several fundamental topologies. We study topology-related real data statistics of Raiden, the off-chain extension for Ethereum as well as of Lightning, the equivalent off-chain layer of Bitcoin. We conduct experiments to demonstrate the effectiveness of the algorithms for these networks.

Merkle trees play a crucial role in blockchain networks in organizing network state. They allow proving a particular value of an entry in the state to a node that maintains only the root of the Merkle trees, a hash-based signature computed over the data in a hierarchical manner. Verification of particular state entries is crucial in reaching a consensus on the execution of a block where state information is required in the processing of its transactions. For instance, a payment transaction should be based on the balance of the two involved accounts. The proof length affects the network communication and is typically logarithmic in the state size. In this paper, we take advantage of typical transaction characteristics for better organizing Merkle trees to improve blockchain network performance. We focus on the common transaction processing where Merkle proofs are jointly provided for multiple accounts. We first provide lower bounds for the communication cost that are based on the distribution of accounts involved in the transactions. We then describe algorithms that consider traffic patterns for significantly reducing it. The algorithms are inspired by various coding methods such as Huffman coding, partition and weight balancing. We also generalize our approach towards the encoding of smart contract transactions that involve an arbitrary number of accounts. Likewise, we rely on real blockchain data to show the savings allowed by our approach. The experimental evaluation is based on transactions from the Ethereum network and demonstrates cost reduction for both payment transactions and smart contract transactions.

Resource sharing with its implied mutual interference has been considered a major concern for running applications of multiple tenants in shared cloud datacenters. Besides its security benefits, the isolation of traffic might ensure a quality of service (QoS) performance guarantee avoiding interference among tenants. Traffic isolation can be achieved by dedicating the usage of link resources in the network to a single tenant preventing its sharing among others. Accordingly, tenants should be connected through an edge-disjoint tree to enable isolated communication among its hosts. In this paper, we study the problem of establishing edge-disjoint trees in common datacenter topologies. We show that the availability of such trees is highly affected by the mapping of the tenants to hosts of the topology. Specifically, with the flexibility to map tenants in the datacenter topology, we describe a mapping algorithm and an optimal tree establishment for the optimization problem. Given the mapping of the tenants, we prove the problem turns out to be NP-Hard and provide comprehensive heuristics for the problem. Finally, we conduct experiments using real workloads to examine tree availability under various scenarios.

A blockchain is a distributed ledger composed of immutable blocks of data that often refer to money transfers. As blockchain networks gain popularity, there is a rising concern for security against malicious and hacking users. Detection anomalies and unusual account activities can be based on comparing upcoming activity with recent and historical data. However, the size and rapid growth of the complete blockchain history can result in slow and expensive processing. This paper proposes a solution to this challenge by analyzing summarized block data structures, known as sketches, instead of the entire blockchain. Sketches are commonly used in computer systems and blockchain networks to provide efficient query executions while maintaining a compact data representation. This study explores the use of sketches, such as Bloom Filter and HyperLogLog, to identify suspicious accounts without requiring the examination of the entire blockchain data. We design solutions for anomaly detection of certain goals that may be indications of known attacks. We develop methods to identify accounts with high transaction volume, frequency, and node degree. Furthermore, the innovation of this paper lies in the generalization of sketch-based anomaly detection through a generic solution capable of addressing diverse queries. We conduct experiments based on real Ethereum data and compare the accuracy, time complexity, and memory usage of our algorithms with traditional detection algorithms that rely on the complete blockchain data. Our results indicate that sketch-based anomaly detection methods can provide a practical and scalable solution for detecting anomalies in transactions on blockchain networks. We managed to reduce the amount of memory used by the detection process by 90%-96% and reduce the time complexity by 86% while maintaining high accuracy.

Collateral is an item of value serving as security for the repayment of a loan. In blockchain-based loans, cryptocurrencies serve as the collateral. The high volatility of cryptocurrencies implies a serious barrier of entry with a common practice that collateral values equal multiple times the value of the loan. As assets serving as collateral are locked, this requirement prevents many candidates from obtaining loans. In this paper, we aim to make loans more accessible by offering loans with lower collateral, while keeping the risk for lenders bound. We use a credit score based on data recovered from the blockchain to predict how likely someone is to repay a loan. Our protocol does not risk the initial amount granted by liquidity providers, but only risks part of the interest yield gained by the protocol in the past.

Layer-2 is a popular approach to deal with the scalability limitation of blockchain networks. It allows users to execute transactions without committing them to the blockchain by relying on predefined payment channels. Users together with the payment channels form a graph, known as the offchain network topology. Transactions between pairs of users without a connecting channel are also supported through a path of multiple channels. Serving such transactions involves fees paid to intermediate users. In this paper we uncover the potential existence of the Braess paradox in payment networks: Sometimes establishing a new payment channel can increase the fees paid for serving some fixed transactions. We study conditions for the paradox to appear and provide indications for the appearance of the paradox based on real data of Bitcoin's Lightning, a popular layer-2 network. Last, we discuss methods to mitigate the paradox upon establishing a new payment channel.

The Invertible Bloom Lookup Table (IBLT) is a probabilistic data structure for set representation, with applications in network and traffic monitoring. It is known for its ability to list its elements, an operation that succeeds with high probability for sufficiently large table. However, listing can fail even for relatively small sets. This paper extends recent work on the worst-case analysis of IBLT, which guarantees successful listing for all sets of a certain size, by introducing more general IBLT schemes. These schemes allow for greater freedom in the implementation of the insert, delete, and listing operations and demonstrate that the IBLT memory can be reduced while still maintaining successful listing guarantees. The paper also explores the time-memory trade-off of these schemes, some of which are based on linear codes and Bh-sequences over finite fields.

We present the Range Query Recursive Model Index (RQRMI) data structure that trades memory accesses for computations in performance-critical systems that employ Range Matching.

Approximate membership check filters are increasingly used to speed up data processing in many applications. Also, privacy is becoming a key design objective for many systems and thus, the privacy of filters needs to be carefully considered. Previous works have shown that an attacker that knows the implementation details of the filter and has access to its content, may be able to extract some information about the elements stored in the filter. This attack is, however, specific to Bloom filters and requires that the universe of elements must be small. In this article, we show that in many practical settings, an attacker that has only a black-box access to the filter, can extract information about the elements stored in the filter regardless of the specific filter type and the universe size. This is possible based on the key observation that in many applications, the elements stored in the filter are not randomly chosen, but they are concentrated in one or more parts of the universe of elements. To identify these parts, the positive probability can be measured on different parts of the universe; the parts having significantly larger values than the average positive probability for the filter are the ones on which the filter elements are concentrated. This approach is formalized and applied to several case studies showing the process by which the attacker can get additional information about the elements stored for the filters in a wide range of scenarios.

For the efficient analysis of geo-distributed datasets, cloud providers implement data-parallel jobs across geo-distributed sites (e.g., datacenters and edge clusters), which are generally interconnected by wide-area network links. However, current state-of-the-art geo-distributed data analytic methods fail to make full use of the available network and computing resources. The main reason is that such geo-distributed methods must wait for bottleneck sites to complete the corresponding transmission and computation in each phase. Furthermore, such geo-distributed methods may be impractical to the network bandwidth dynamicity and diverse job parallelism. To this end, we propose a Simultaneous Data Transfer and Processing (SDTP) mechanism to accelerate wide-area data analytics, with the joint consideration of network bandwidth dynamics and job parallelism. In the SDTP, a site can execute the computation, provided that it obtains the required input data. As a result, the input data loading, map, shuffle, and reduce phases at each site need not wait for the completion of the previous phases of other sites. We further improve the SDTP method by offering more accurate time estimation and generalizing the mechanism to dynamic situations. The trace-driven results demonstrate that SDTP can improve the wide-area analytic job response time by 19% to 72% compared to other methods.

Mobile edge computing allows efficient cloud servicing by building small-scale cloud infrastructures at the network edge close to end users. The cloud servers implement virtual network functions in a flexible manner without dedicated middleboxes. In such a network design, latency and reliability are two key performance metrics which are not always aligned and a tradeoff can appear between them. In this paper, we identify three key factors that impact the existence of a tradeoff such as the number of services, the number of functions the services require and the existence of redundancy in the implementation of functions. Our main contribution is indicating exactly whether a tradeoff can exist in each combination of these three factors. In case a tradeoff exists, we find guarantees on the performance in a non-optimized metric of an optimal solution to the other metric. We also study the tradeoff when each service should be served in a particular order. We also propose a function placement method that jointly optimizes both latency and reliability. Lastly, we evaluate our analysis in an experimental setting.

Network measurements are important for identifying congestion, DDoS attacks, and more. To support real-time analytics, stream ingestion is performed jointly by multiple nodes, each observing part of the traffic, periodically reporting its measurements to a single centralized server that aggregates them. To avoid communication congestion, each node reports a compressed version of its collected measurements. Traditionally, nodes symmetrically report summaries of the same size computed on their data. We explain that to maximize the accuracy of the joint measurement, nodes should imply various compression ratios on their measurements based on the amount of traffic observed by each node. We illustrate the approach for three common sketches: The Count-Min sketch (CM), which estimates flow sizes as well as for the K-minimum-values (KMV) sketch and the HyperLogLog (HLL), which both estimate the number of distinct flows. For each sketch, we compute node compression ratios based on the traffic distribution. In general, this is done with a single round of communication with the central server, after which the compression ratio for each node can be computed. We perform extensive simulations for the sketches and analytically show that, under real-world scenarios, our sketches send smaller summaries than traditional ones while retaining similar error bounds.

Network survivability has been recognized as an issue of a major importance in terms of security, stability and prosperity. This paper studies fundamental properties of HyperX, an emerging topology for connecting supercomputing and datacenter networks. We focus on the establishment of paths with guaranteed survivability, allowing path availability even upon a restricted number of link failures. We first examine the availability of disjoint paths connecting a pair of input nodes. Disjoint paths guarantee path existence even upon a bounded number of link failures. We explore the inherent tradeoff between allowing slightly longer paths and the ability to extend available sets of mutually disjoint paths. Second, we study the availability of paths in a HyperX topology that already observed link failures. Such failures can increase the length of available paths or even eliminate connectivity between network parts. We also compare basic properties of shortest paths in HyperX to other datacenter topologies. Last, we provide an evaluation to illustrate path availability along with the potential impact of failures.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most${n}$prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We consider the$L_{1}$distance between partitions, which is of interest when overloaded requests are simply dropped, and we want to minimize the total loss. We prove that the Niagara algorithm (Kang et al., 2015) can be used to find the closest partition in$L_{1}$to the desired partition, that can be realized with${n}$TCAM rules. Moreover, we prove it for arbitrary partitions, with (possibly) non-integer parts. We also include a short discussion on similarities and differences to previous work which studies the same problem but for$L_{\infty }$distances.

Open vSwitch (OVS) is a widely used open-source virtual switch implementation. In this work, we seek to scale up OVS to support hundreds of thousands of OpenFlow rules by accelerating the core component of its data-path - the packet classification mechanism. To do so we use NuevoMatch, a recent algorithm that uses neural network inference to match packets, and promises significant scalability and performance benefits. We overcome the primary algorithmic challenge of the slow training rate in the vanilla NuevoMatch, speeding it up by over three orders of magnitude. This improvement enables two design options to integrate NuevoMatch with OVS: (1) as an extra caching layer in front of OVS’s megaflow cache, and (2) using it to completely replace OVS’s data-path while performing classification directly on OpenFlow rules, and obviating control-path upcalls. Comprehensive evaluation on real-world packet traces and ClassBench rules demonstrates geometric mean speedups of$1.9\times $and$12.3\times $for the first and second designs, respectively, for 500K rules, with the latter also supporting up to 60K OpenFlow rule updates/second, by far exceeding the original OVS.

The popular OpenFlow virtual switch Open vSwitch (OVS) uses a variant of Tuple Space Search (TSS) for packet classification. Although it is easy for rule updates, the lookup performance is poor. By introducing partial trees into TSS, the recently proposed CutTSS improves the lookup performance of TSS. However, it is challenging to replace TSS in OVS for two reasons: (1) the hand-tuned partitioning heuristics are rule-set dependent; (2) the complex and irregular data structures make it difficult to be integrated and maintained in real systems. To address these issues, we propose HybridTSS, a recursive TSS scheme for fast packet classification in OVS, which exploits three novel ideas: (1) the recursive partitioning based on reinforcement learning balances global rule partitions with low training complexity; (2) a hybrid TSS scheme combining coarse-grained and fine-grained tuples suppresses tuple explosion in TSS; (3) a heterogeneous search algorithm consisting of TSS and linear search adapts to characteristics of rules at different scales for fast lookups. Using ClassBench, we show that, while immune from the main drawbacks of CutTSS, HybridTSS retains the update performance of TSS, and achieves almost an order of magnitude higher lookup performance than TSS, making it an ideal packet classification algorithm for OVS.

Blockchain leader-based protocols elect leaders for proposing the next block of transactions. Proposed blocks need to pass a validation routine in order to be added to the blockchain. Proposers may prioritize certain transactions based on their fees or accounts. A fair block selection follows a random selection of transactions among pending transactions that a proposer is aware of. The validators may only have partial knowledge of the network transactions making it challenging to validate the random selection. We propose a protocol to encourage fair block selection in a leader-based blockchain network. Our protocol offers two main contributions. First, suggesting an algorithm that evaluates the proposed blocks based on both their transactions’ issuance times and zone structure. Second, providing incentives for acting honestly and diminishing malicious and dishonest nodes. To accomplish this, we use a reputation system, whereby each node is given a reputation score based on its actions (i.e. latest proposals and evaluations). We demonstrate the improved accuracy of our protocol by implementing experiments based on Ethereum topology, comparing it with Helix [1], an existing consensus algorithm for a fair block selection.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most n prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We consider the L1distance between partitions, which is of interest when overloaded requests are simply dropped, and we want to minimize the total loss. We prove that the Niagara algorithm [1] can be used to find the closest partition in L1to the desired partition, that can be realized with n TCAM rules. Moreover, we prove it for arbitrary partitions, with (possibly) non-integer parts.

Traffic splitting is a required functionality in networks, for example for load balancing over paths or servers, or by the source’s access restrictions. The capacities of the servers (or the number of users with particular access restrictions) determine the sizes of the parts into which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming. We analyze the expected size of a representation, for uniformly random ordered partitions. We show that the expected representation size of a random partition is at least half the size for the worst-case partition, and is linear in the number of parts and in the logarithm of the size of the address space.

Estimating the number of distinct elements is required in many computing applications. One of the state-of-the-art algorithms for cardinality estimate is the HyperLogLog; it provides a good estimate over a large range of cardinality values using a small array of counters. As HLL is implemented in computing systems, it is exposed to soft errors that can corrupt bits stored in memories or registers. To avoid data corruption, memories are commonly protected with Error Correction Codes (ECCs). ECCs however incur in significant overhead because protection needs additional memory cells per word to store the parity check bits as well as additional computation for checking them. In this paper, we first study the impact of soft errors on the HLL algorithm by performing simulation by error injection. The results show that the algorithm is quite robust and can filter out most errors. However, for large cardinalities, there are some errors that can cause a large discrepancy in the HLL estimate. Based on the analysis of the experimental results and the HLL algorithm, a protection technique is proposed that effectively mitigates the impact of soft errors at a small overhead. The proposed Remove Minimum (RM) scheme has been validated by error injection experiments.

With the rapid adoption of new technologies and applications, e.g., the Internet of Things, 5G/6G communication networks, big data analytics, and artificial intelligence, a deluge of devices are being connected to the network, thus generating a large amount of data. The collection, processing, and analysis of this vast amount of data are essential to help people and enterprises gain valuable information, make sensible decisions, and subsequently improve the quality of people’s lives. However, the underlying communication networks are thus facing a new number of unprecedented challenges. Managing these large numbers of devices in a scalable and secure manner is bringing significant challenges to the infrastructure construction, maintenance, and management of the communication networks. Recurring data privacy breaches and the lack of control make Internet users and enterprises less willing to provide valuable data for processing and analysis.

Bloom filters are widely used to perform fast approximate membership checking in networking applications. The main limitation of Bloom filters is that they suffer from false positives that can only be reduced by using more memory. We suggest to take advantage of a common repetition in the identity of queried elements to adapt Bloom filters for avoiding false positives for elements that repeat upon queries. In this paper, one memory access Bloom filters are used to design an adaptation scheme that can effectively remove false positives while completing all queries in a single memory access. The proposed filters are well suited for scenarios on which the number of memory bits per element is low and thus complement existing adaptive cuckoo filters that are not efficient in that case. The evaluation results using packet traces show that the proposed adaptive Bloom filters can significantly reduce the false positive rate in networking applications with the single memory access. In particular, when using as few as four bits per element, false positive rates below 5% are achieved.

Caching is at the core of most modern communication systems, where caches are used to store content and traffic classification rules. While network components can leverage caching in a cooperative manner, one important aspect of such systems concerns possible dependencies among stored items. A major use case of such dependencies appears in rule placement across software-defined networks (SDNs). Despite the tremendous success of SDNs in datacenters, their wide adoption still poses a key challenge: the packet-forwarding rules in switches require fast and power-hungry memories. Rule tables, which serve as caches, are of limited size in cheap and energy-constrained devices, motivating novel solutions to achieve high hit rates. We leverage device connectivity in the fast data plane, where delays are in the order of few milliseconds, and propose multiple switches to work together to avoid accessing the control plane, where delays are orders of magnitude greater. As a low priority rule in a cache entails caching higher priority rules, we pose the problem of cooperative caching with dependencies. We provide models and algorithms accounting for dependencies among rules implied by existing switch memory types, andlay the foundations of cooperative caching with dependencies.

Multi-field packet classification is a crucial component in modern software-defined data center networks. To achieve high throughput and low latency, state-of-the-art algorithms strive to fit the rule lookup data structures into on-die caches; however, they do not scale well with the number of rules. We present a novel approach,NuevoMatch, which improves the memory scaling of existing methods. A new data structure,Range Query Recursive Model Index(RQ-RMI), is the key component that enables NuevoMatch to replace most of the accesses to main memory with model inference computations. We describe an efficient training algorithm that guarantees the correctness of the RQ-RMI-based classification. The use of RQ-RMI allows the rules to be compressed into neural networks that fit into the hardware cache. Further, it takes advantage of the growing support for fast neural network processing in modern CPUs, such as wide vector instructions, achieving a latency of tens of nanoseconds per lookup. Our evaluation using 500K multi-field rules from the standard ClassBench benchmark shows a geometric mean compression factor of$4.9\times $,$8\times $, and$82\times $, and average performance improvement of$2.4\times $,$2.6\times $, and$1.6\times $in throughput compared to CutSplit, NeuroCuts, and TupleMerge, all state-of-the-art algorithms.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most$n$prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We give simple and efficient algorithms to find$n$rules that generate a partition closest in$L_\infty $to the desired one. We do the same for a one-sided version of$L_\infty $which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM.

Bloom filters are probabilistic data structures that are popular in networking for set representation; however, they show an inherent inaccuracy due to false positives. One of the potential attacks on Bloom filters is to pollute them with elements that cause the filter to have a larger false positive probability than under normal operation; Pollution is simple when an attacker knows the details of the filter implementation. Recent research has shown that also black-box adversaries can pollute a counting Bloom filter (a common variant of the filter that also supports removals) with no knowledge of its implementation. As over time, many variants and improvements of Bloom filters have been proposed, it is of interest to study whether they can also be polluted and if so also the increase in their false positive probability. This paper first proposes and then evaluates pollution attacks for some of the most common variants including the Block Bloom filters (BBFs), the Variable Increment and Fingerprint Counting Bloom filters (VI-CBFs and FP-CBFs). The results show that with or without knowledge of the implementation, these variants of the Bloom filter are significantly more vulnerable to pollution attacks than the traditional Bloom filter. In particular, BBFs are extremely vulnerable, so providing an insight on their impact and use in practical systems when the number of memory accesses per lookup must be reduced.

Perfect hashing is a hash function that maps a set of distinct keys to a set of continuous integers without collision. However,most existing perfect hash schemes are static, which means that they cannot support incremental updates, while most datasets in practice are dynamic. To address this issue, we propose a novel hashing scheme, namely MapEmbed Hashing. Inspired by divide-and-conquer and map-and-reduce, our key idea is named map-and-embed and includes two phases: 1) Map all keys into many small virtual tables; 2) Embed all small tables into a large table by circular move. Our experimental results show that under the same experimental setting, the state-of-the-art perfect hashing (dynamic perfect hashing) can achieve around 15% load factor, around 0.3 Mops update speed, while our MapEmbed achieves around 90% ~ 95% load factor, and around 8.0 Mops update speed per thread. All codes of ours and other algorithms are open-sourced at GitHub.

Network measurements are important for identifying congestion, DDoS attacks, and more. To support realtime analytics, stream ingestion is performed jointly by multiple nodes, each observing part of the traffic, periodically reporting its measurements to a single centralized server that aggregates them. To avoid communication congestion, each node reports a compressed version of its collected measurements. Traditionally, nodes symmetrically report summaries of the same size computed on their data. We explain that to maximize the accuracy of the joint measurement, nodes should imply various compression ratios on their measurements based on the amount of traffic observed by each node. We illustrate the approach for two common sketches: The Count-Min sketch (CM), which estimates flow frequencies, and the K-minimum-values (KMV) sketch, which estimates the number of distinct flows. For each sketch, we compute node compression ratios based on the traffic distribution. We perform extensive simulations for the sketches and analytically show that, under real-world scenarios, our sketches send smaller summaries than traditional ones while retaining similar error bounds.

Bloom filters and their variants are widely used as space-efficient probabilistic data structures for representing sets and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications, a common engineering solution is to set the false positive rate very small and ignore the existence of the very unlikely false positive answers. This article is devoted to close the gap between the two design concepts ofunlikelyandnot havingfalse positives. We propose a data structure called EGH filter that supports the Bloom filter operations, and besides, it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false-positive free zone of a filter. We then generalize the filter to support the listing of the elements through the use of counters rather than bits. We detail networking applications of the filter and discuss potential generalizations. We evaluate the performance of the filter in comparison with the traditional Bloom filters. We also evaluate the price in terms of memory that needs to be paid to guarantee real false positive-free operations for having a deterministic Bloom filter-like behavior. Our data structure is based on recently developed combinatorial group testing techniques.

The emergence of large-scale dynamic sets in networked and distributed applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional${k}$candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

State sharding is a common solution to the scalability problem in blockchain systems, allowing nodes to hold a partial view of the system state. With sharding, the processing of a transaction might not be completed locally within a node and potentially requires involvement of multiple shards. Such cross-shards transactions have a negative impact on system performance and are frequent with traditional state partition solutions which are often based on a simple mapping of data into shards. By locating together parts of the system state accessed by frequent transactions, the amount of cross-shard transactions can be reduced. On the other hand, the representation of such particular mappings can be memory intensive. In this article, we study traffic-aware sharding that can be described in memory-efficient mappings. We first survey existing mapping schemes in common blockchains. We indicate the tradeoff between the size of the mapping of data to shards and the required transaction processing time and suggest algorithms for finding memory-light sharding of low cross-shard rate. We generalize the approach towards an efficient incremental computation of shards and probabilistic representation of the mapping to shards. We examine the efficiency of the solutions and the required frequency of sharding computation based on real information of the Ethereum network.

The Count-Min sketch is the most popular data structure for flow size estimation, a basic measurement task required in many networks. Typically the number of potential flows is large, eliminating the possibility to maintain a counter per flow within memory of high access rate. The Count-Min sketch is probabilistic and relies on mapping each flow to multiple counters through hashing. This implies potential estimation error such that the size of a flow is overestimated when all flow counters are shared with other flows with observed traffic. Although the error in the estimation can be probabilistically bounded, many applications can benefit from accurate flow size estimation and the guarantee to completely avoid overestimation. We describe a design of the Count-Min sketch with accurate estimations whenever the number of flows with observed traffic follows a known bound, regardless of the identity of these particular flows. We make use of a concept of Bloom filters that avoid false positives and indicate the limitations of existing Bloom filter designs towards accurate size estimation. We suggest new Bloom filter constructions that allow scalability with the support for a larger number of flows and explain how these can imply the unique guarantee of accurate flow size estimation in the well known Count-Min sketch.

We presentHelix, a blockchain-based consensus protocol forfairordering of transactions among nodes in a distributed network. Helix advances in rounds, in each an elected primary node proposes a potential block (a successive set of transactions). For being included in the blockchain, a block must pass validation by an elected committee of nodes. Nodes have two primary preferences. First, to be elected as committee members. Additionally, because each transaction is associated with one of the network nodes, nodes would like to prioritize their own transactions over those of others. Our definition of fairness incorporates three key elements. First, the process of electing nodes to committees is random and unpredictable. Second, a correlated sampling scheme is used to guarantee random selection and ordering of pending transactions in blocks. Third, transactions are encrypted to hide their associations with nodes and prevent censorship. Through the corresponding threshold decryption process we obtain an unpredictable and non-manipulable randomness beacon, which serves both the election process and the correlated sampling scheme. We define a quantitative measure of fairness in the protocol, prove theoretically that fairness manipulation in Helix is significantly limited, and present experiments evaluating fairness in practice.

Multi-party set reconciliation is a key component in distributed and networking systems. It naturally contains two dimensions, i.e., set representation and reconciliation protocol. However, existing sketch data structures are insufficient to satisfy the new needs brought by the multi-party scenario simultaneously, including space-efficiency, mergeability, and completeness. The current reconciliation protocols, on the other hand, fail to achieve the global optimization of communication cost. To this end, in this article, we propose the marked cuckoo filter (MCF), a data structure for representing set members. Grounded on MCF, we implement the MCFsyn protocol to reconcile multiple sets. MCFsyn aggregates and distributes sets information represented by MCFs along with an underlying minimum spanning tree among the participants. The participants then identify the different elements by traversing the overall MCF which contains the information of all elements in the union set. For the identified missing elements, MCFsyn helps the participants to choose the optimal senders to fetch with the minimum communication cost. Comprehensive evaluations indicate that MCFsyn significantly outperforms existing alternatives in terms of both reconciliation accuracy and communication cost.

The wide adoption of Bloom filters makes their security an important issue to be addressed. For example, an attacker can increase their error rate through polluting and eventually saturating the filter by inserting elements that set to one a large number of positions in the filter. This is known as a pollution attack and requires that the attacker knows the hash functions used to construct the filter. Such information is not available in many practical settings and in addition a simple protection can be achieved through using a random salt in the hash functions. The same pollution attacks can also be done to counting Bloom filters that in addition to insertions and lookups support removals. This paper considers pollution attacks on counting Bloom filters. We describe two novel pollution attacks that do not require any knowledge of the counting Bloom filter implementation details and evaluate them. These methods show that a counting Bloom filter is vulnerable to pollution attacks even when the attacker has only access to the filter as a black box to perform insertions, removals, and lookups.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most n TCAM rules are available, restricting the ability to implement the desired partition. We give simple and efficient algorithms to find n rules that generate a partition closest in L∞ to the desired one. We do the same for a one-sided version of L∞ which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM.

In blockchain applications, transaction latency is crucial for determining the quality of service (QoS). Transaction latency is measured as the time between its issuance and its inclusion in a block in the chain. When different applications use the same blockchain network, a block proposer often prioritizes its own application transactions over other applications transactions to minimize its own latency. To maintain fairness, a block proposer is typically supposed to select the included transactions randomly providing each transaction similar chances to be included. The random selection might cause some transactions to experience high latency since this selection implies a high variance in the time a transaction waits until it is selected. We suggest an alternative, age-aware approach towards fairness so that transaction priority is increased upon observing a large waiting time. The challenge with this approach is that the age of a transaction is not absolute due to transaction propagation. Moreover, a node might present its transactions as older to obtain priority. We consider three network restrictions on transaction propagation and explain how to enhance fairness in each one of them. We describe three declaration schemes in which a node declares its pending transactions providing the ability to validate transaction age. We demonstrate the advantages of the solutions on Ethereum and synthetic data in reducing tail latency.

Multi-field packet classification is a crucial component in modern software-defined data center networks. To achieve high throughput and low latency, state-of-the-art algorithms strive to fit the rule lookup data structures into on-die caches; however, they do not scale well with the number of rules.

Software switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. The popular Open vSwitch uses a variant of Tuple Space Search (TSS) for packet classifications. Although it has good performance on rule updates, it is less efficient than decision trees on lookups. In this paper, we propose a two-stage framework consisting of heterogeneous algorithms to adaptively exploit different characteristics of the rule sets at different scales. In the first stage, partial decision trees are constructed from several rule subsets grouped with respect to their small fields. This grouping eliminates rule replications at large scales, thereby enabling very efficient pre-cuttings. The second stage handles packet classification at small scales for non-leaf terminal nodes, where rule replications within each subspace may lead to inefficient cuttings. A salient fact is that small space means long address prefixes or less nesting levels of ranges, both indicating a very limited tuple space. To exploit this favorable property, we employ a TSS-based algorithm for these subsets following tree constructions. Experimental results show that our work has comparable update performance to TSS in Open vSwitch, while achieving almost an order-of-magnitude improvement on classification performance over TSS.

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications, such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria that we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

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.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2Waddresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in O(W k) time. Furthermore, we prove that a recently published load balancer, called Niagara, which runs in O(W k log k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we use these optimal algorithms to experimentally study the number of TCAM rules required to split traffic in typical scenarios.

We present Elmo, a system that addresses the multicast scalability problem in multi-tenant datacenters. Modern cloud applications frequently exhibit one-to-many communication patterns and, at the same time, require sub-millisecond latencies and high throughput. IP multicast can achieve these requirements but has control- and data-plane scalability limitations that make it challenging to offer it as a service for hundreds of thousands of tenants, typical of cloud environments. Tenants, therefore, must rely on unicast-based approaches (e.g., application-layer or overlay-based) to support multicast in their applications, imposing bandwidth and end-host CPU overheads, with higher and unpredictable latencies. Elmo scales network multicast by taking advantage of emerging programmable switches and the unique characteristics of data-center networks; specifically, the hypervisor switches, symmetric topology, and short paths in a datacenter. Elmo encodes multicast group information inside packets themselves, reducing the need to store the same information in network switches. In a three-tier data-center topology with 27,000 hosts, Elmo supports a million multicast groups using an average packet-header size of 114 bytes (max. 325 bytes), requiring as few as 1,100 multicast group-table entries on average in leaf switches, and having a traffic overhead as low as 5% over ideal multicast.

Set reconciliation is a common and fundamental task in distributed systems. In many cases, given set A on $Host_A$ and set B on $Host_B$, applications need to identify those elements that appear in set A but not in set B, and vice versa. However, existing methods incur unsatisfactory space utilization and non-trivial false positives and false negatives. In this paper, we present a novel reconciliation method based on Cuckoo filter (CF). After exchanging the CFs each of which represents a set of elements, we query the local elements against the received CF to determine the elements that only belong to the local host and should be transmitted to the other host. The evaluation results indicate that the CF-based reconciliation method outperforms existing methods significantly.

Short-lived surges in traffic can cause periods of high queue utilization, leading to packet loss and delay. To diagnose and alleviate performance problems, networks need support for real-time, fine-grained queue measurement. By identifying the flows that contribute significantly to queue build-up directly in the data plane, switches can make targeted decisions to mark, drop, or reroute these flows in real time. However, collecting fine-grained queue statistics is challenging even with modern programmable switch hardware, due to limited memory and processing resources in the data plane. We present ConQuest, a compact data structure that identifies the flows making a significant contribution to the queue. ConQuest operates entirely in the data plane, while working within the hardware constraints of programmable switches. Additionally, we show how to measure queues in legacy devices through link tapping and an off-path switch running ConQuest. Simulations show that ConQuest can identify contributing flows with 90% precision on a 1 ms timescale, using less than 65 KB of memory. Experiments with our Barefoot Tofino prototype show that ConQuest-enabled active queue management reduces flow-completion time.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100% reconciliation accuracy; (iii) communication-friendly and time-saving. Prior reconciliation methods fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively.

The emergence of large-scale dynamic sets in networking applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional k candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2Waddresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in Õ(Wk) time. Furthermore, we prove that a recently published load balancer, called Niagara, which also runs in Õ(W k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we rely on our optimal Õ(Wk) runtime algorithm to investigate through extensive experiments the amount of TCAM memory required to represent traffic splitting in typical scenarios.

We present Elmo, a system that addresses the multicast scalability problem in multi-tenant datacenters. Modern cloud applications frequently exhibit one-to-many communication patterns and, at the same time, require sub-millisecond latencies and high throughput. IP multicast can achieve these requirements but has control- and data-plane scalability limitations that make it challenging to offer it as a service for hundreds of thousands of tenants, typical of cloud environments. Tenants, therefore, must rely on unicast-based approaches (e.g., application-layer or overlay-based) to support multicast in their applications, imposing bandwidth and end-host CPU overheads, with higher and unpredictable latencies.

The most demanding tenants of shared clouds require complete isolation from their neighbors, in order to guarantee that their application performance is not affected by other tenants. Unfortunately, while shared clouds can offer an option, whereby tenants obtain dedicated servers, they do not offer any network provisioning service, which would shield these tenants from network interference. In this paper, we introduce links as a service (LaaS), a new abstraction for cloud service that provides isolation of network links. Each tenant gets an exclusive set of links forming a virtual fat-tree, and is guaranteed to receive the exact same bandwidth and delay as if it were alone in the shared cloud. Consequently, each tenant can use the forwarding method that best fits its application. Under simple assumptions, using bipartite graph properties and pigeonhole-based analysis, we derive theoretical conditions for enabling the LaaS without capacity over-provisioning in fat-trees. New tenants are only admitted in the network, when they can be allocated hosts and links that maintain these conditions. We also provide new results on the numbers of tenants and hosts that can fit while guaranteeing network isolation. The LaaS is implementable with common network gear, tested to scale to large networks, and provides full tenant isolation at the cost of a limited reduction in the cloud utilization.

Error Correction Codes (ECCs) are commonly used to protect memories against soft errors with an impact on memory area and delay. For large memories, the area overhead is mostly due to the additional cells needed to store the parity check bits. In terms of delay, the overhead is mostly needed to detect and correct errors when the data is read from the memory. Most ECCs that can correct more than one error have a complex decoding process and so are limited in high speed memory applications. One exception is One Step Majority Logic Decodable (OS-MLD) codes for which decoding can be done in parallel at high speed. Unfortunately, there are only a few OS-MLD codes that provide a limited choice in terms of block sizes, error correction capabilities and code rate. Therefore, there is considerable interest in a novel construction of OS-MLD codes to provide additional choices for protecting memories. In this paper, a new method to construct Double Error Correction (DEC) OS-MLD codes is presented. This method is based on the use of parity check matrices in which two bits have at most two parity check equations in common; the proposed method provides codes that require a smaller number of parity check bits than existing codes like Orthogonal Latin Square (OLS) codes. The drawback of the proposed Two Bit Overlap (TBO) codes is that they require slightly more complex decoding than OLS codes. Therefore, they provide an intermediate solution between OLS and non OS-MLD codes in terms of decoding delay and number of parity check bits. The proposed TBO codes have been implemented for some block sizes and compared to both OLS and BCH codes to illustrate the trade off in delay and memory overhead. Finally, this paper discusses the generalization of the proposed scheme to codes with larger error correction capabilities.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100 percent reconciliation accuracy; and (iii) communication-friendly and time-saving. These three rationales, if realized, will lead to unprecedented benefits for the set reconciliation paradigm. Generally, prior reconciliation methods are mainly designed for simple sets and thus remain inapplicable for multisets. Methods based on probabilistic data structures, e.g., the Counting Bloom Filter (CBF), support efficient representation, and multiplicity queries. Based on these probabilistic data structures, approximate multiset reconciliation can be enabled. However, they often cannot achieve a statisfying accuracy, due to potential hash collisions. The reconciliations enabled by logs or lists incur high time-complexity and communication overhead. Therefore, existing reconciliation methods, fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Moreover, to further reduce the communication overhead during the reconciliation process, we design a partial transmission strategy when exchanging two Tries or FTs. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively. The simulations based on synthetic datasets further indicate that our proposals outperform the CBF-based method in terms of accuracy and communication overhead at most time.

Set representation is a crucial functionality in various areas such as networking and databases. In many applications, memory and time constraints allow only an approximate representation where errors can appear for some queried elements. The Variable-Increment Counting Bloom Filter (VI-CBF) is a popular data structure for the representation of dynamically-changing sets, achieving a good tradeoff between memory efficiency and queries accuracy. For some applications, the required accuracy is higher than that enabled by the VI-CBF. In this paper, we present the Tandem Counting Bloom Filter (T-CBF), a new data structure that relies on the interaction among counters to describe sets with higher accuracy. We analyze its performance and show that by a joint consideration of counters, the T-CBF always performs better than the VI-CBF and it can for some configurations reduce its false positive probability by an order of magnitude. The overhead of such an approach is expressed upon an element insertion or query as read or write operations to a pair of counters rather than a single counter in each hash location. The operations themselves also require considering a larger number of scenarios.

We present Helix, a blockchain-based consensus protocol for fair ordering of transactions among nodes in a distributed network. Helix advances in rounds, where in each round, the primary node (elected among the network nodes) proposes a potential block (a successive set of transactions). In order to be included in the blockchain, a block must pass validation by an elected committee of nodes. Helix nodes are presumed to have two primary preferences. They prefer to be elected as committee members. Additionally, because each transaction is associated with one of the network nodes, they prefer to prioritize their own transactions over those of others. In light of these individual preferences, our definition of fairness incorporates three key elements. First, the process of electing nodes to committees is random and unpredictable. Second, a correlated sampling scheme is used in order to guarantee random selection and ordering of pending transactions in blocks. Third, transactions are encrypted in order to hide their associations with their respective nodes and prevent censorship. Through the corresponding threshold decryption process we obtain an unpredictable and non-manipulable randomness beacon, which serves both the election process and the correlated sampling scheme. We define a quantitative measure of fairness in the protocol, prove theoretically that fairness manipulation in Helix is significantly limited, and present experiments evaluating fairness in practice.

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 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 Probabilistic 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 analyze the effect of each architectural constraint on the measurement accuracy and provide insights for measurement algorithm designers.

Enabling functionality in modern network is achieved through the use of middleboxes. Middleboxes suffer from temporal unavailability due to various reasons, such as hardware faults. We design a backup scheme that takes advantage of Network Function Virtualization (NFV), an emerging paradigm of implementing network functions in software, deployed on commodity servers. We utilize the agility of software-based systems, and the gap between the resource utilization of active and standby components, in order to design an optimal limited-resource backup scheme. We focus on the case where a small number of middleboxes fail simultaneously, and study the backup resources required for guaranteeing full recovery from any set of failures, of up to some limited size. Via a novel graph-based presentation, we develop a provably optimal construction of such backup schemes. Since full recovery is guaranteed, our construction does not rely on failure statistics, which are typically hard to obtain. Simulation results show that our proposed approach is applicable even for the case of larger numbers of failures.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper we suggest an analytical study of such an approach. To do that, we relate the description of distributions in switches to signed representations of positive integers. We suggest an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.

Network function virtualization is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named service function chain (SFC) mapping, with which network functions are deployed over virtualized and shared platforms in data centers. However, failures are quite common in data centers. Therefore, a practical and yet theoretically challenging issue in SFC mapping in such an environment is to manage the availability of the requests. In this paper, we present a framework to provision availability of SFC requests in a data center with multiple layers of connected devices, and the devices follow heterogeneous failure processes with the objective of minimizing resource usage. To expedite the process, we further propose an optimization problem of request mapping and backup estimation and solve it efficiently with an approximation algorithm. With simulations, we demonstrate the effectiveness of our proposed framework.

Enabling functionality in a modern network is achieved through the use of middleboxes. Middleboxes suffer from temporal unavailability due to various reasons, such as hardware faults. We design a backup scheme that takes advantage of network function virtualization, an emerging paradigm of implementing network functions in software, deployed on commodity servers. We utilize the agility of software-based systems, and the gap between the resource utilization of active and standby components, in order to design an optimal limited-resource backup scheme. We focus on the case where a small number of middleboxes fail simultaneously, and study the backup resources required for guaranteeing full recovery from any set of failures, of up to some limited size. Via a novel graph-based presentation, we develop a provably optimal construction of such backup schemes. Since full recovery is guaranteed, our construction does not rely on failure statistics, which are typically hard to obtain. Simulation results show that our proposed approach is applicable even for the case of larger numbers of failures.

Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper, we conduct an analytical study to understand this ability of switches. To do that, we indicate on a surprising strong connection between the description of distributions in switches to signed representations of positive integers. We introduce an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider, we have two sources with known discrete distributions, and we wish to find codes that maximize the success probability that the two source outputs are represented in L bits or less. A good practical use for this problem is a table with two-field entries that is stored in a memory of a fixed width L. Such tables of very large sizes are common in network switches/routers and in data-intensive machine-learning applications. After defining the problem formally, we solve it optimally with an efficient code-design algorithm. We also solve the problem in the more constrained case where a single code is used in both fields (to save space for storing code dictionaries). For both code-design problems we find decompositions that yield efficient dynamic-programming algorithms. With the help of an empirical study we show the success probabilities of the optimal codes for different distributions and memory widths. In particular, this paper demonstrates the superiority of the new codes over existing compression algorithms.

Speeding up network updates is crucial to maintain high agility and to react quickly to network failures. In this paper, we present Ctalyst---a new design to reduce the network update time. We observe that networks offer a power of choice, where there are many equally-good alternative paths that traffic flows can be assigned to, which is facilitated by redundancy in networks. Catalyst exploits this power of choice to assign flows to alternative paths to merge stages in the dependency graph (that captures the update plan), which in turn reduces the total update time. Furthermore, we observe that because of the prevalence of switch stragglers---switches that unexpectedly take longer time to update, simply assigning a flow to a single (shortest) path is not an optimal design as even a single switch straggler can substantially increase the update time. Thus, the second principle in Catalyst is to compute multiple paths for individual flows offline, among which one would be selected at runtime based on temporal switch conditions, in order to enable a fast update. Our evaluation using a load-balancer setting in a data center network shows that Catalyst effectively reduces the total update time by 1.14--2.15x.

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria which we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider we have a source with a known discrete distribution, and we wish to find a code that maximizes the success probability that two source instances can be represented together in L bits or less. A good practical use for this problem is a table with two-element entries that is stored in a memory of a fixed width L. Such tables of very large sizes are used in data-intensive computing applications. We solve the problem by efficiently finding an optimal code that uses a dictionary of linear size in the number of source elements.

In enterprise networks, policies (e.g., QoS or security) are often defined based on the categorization of hosts along dimensions, such as the organizational role of the host (faculty versus student) and department (engineering versus sales). While current best practices (virtual local area networks) help when hosts are categorized along a single dimension, policy may often need to be expressed along multiple orthogonal dimensions. In this paper, we make three contributions. First, we argue for attribute-encoded IPs (ACIPs), where the IP address allocation process in enterprises considers attributes of a host along all policy dimensions. ACIPs enable flexible policy specification in a manner that may not otherwise be feasible owing to the limited size of switch rule-tables. Second, we present Alpaca, algorithms for realizing ACIPs under practical constraints of limited-length IP addresses. Our algorithms can be applied to different switch architectures, and we provide bounds on their performance. Third, we demonstrate the importance and viability of ACIPs on data collected from real campus networks.

In enterprise networks, network functions, such as address translation, firewall, and deep packet inspection, are often implemented in middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. Traditionally, middlebox survivability is achieved by an expensive active-standby deployment where each middlebox has a backup instance, which is activated in case of a failure. Network function virtualization (NFV) is a novel networking paradigm allowing flexible, scalable and inexpensive implementation of network services. In this paper, we suggest a novel approach for planning and deploying backup schemes for network functions that guarantee high levels of survivability with significant reduction in resource consumption. In the suggested backup scheme, we take advantage of the flexibility and resource-sharing abilities of the NFV paradigm in order to maintain only a few backup servers, where each can serve one of multiple functions when corresponding middleboxes are unavailable. We describe different goals that network designers can consider when determining which functions to implement in each of the backup servers. We rely on a graph theoretical model to find properties of efficient assignments and to develop algorithms that can find them. Extensive experiments show, for example, that under realistic function failure probabilities, and reasonable capacity limitations, one can obtain 99.9% survival probability with half the number of servers, compared with standard techniques.

The Internet routing ecosystem is facing substantial scalability challenges due to continuous, significant growth of the state represented in the data plane. Distributed switch architectures introduce additional constraints on efficiency of implementations from both lookup time and memory footprint perspectives. In this paper we explore efficient forwarding information base (FIB) representations in common distributed switch architectures. Our approach introduces substantial savings in memory footprint transparently for existing hardware. Our results are supported by an extensive simulation study on real IPv4 and IPv6 FIBs.

Set synchronization is an essential job for distributed applications. In many cases, given two sets A and B, applications need to identify those elements that appear in set A but not in set B, and vice versa. Bloom filter, a spaceefficient data structure for representing a set and supporting membership queries, has been employed as a lightweight method to realize set synchronization with a low false positive probability. Unfortunately, bloom filters and their variants can only be applied to simple sets rather than more general multisets, which allow elements to appear multiple times. In this paper, we first examine the potential of addressing the multiset synchronization problem based on two existing variants of the bloom filters: the IBF and the counting bloom filter (CBF). We then design a novel data structure, invertible CBF (ICBF), which represents a multiset using a vector of cells. Each cell contains two fields, id and count, which record the identifiers and number of elements mapped into them, respectively. Given two multisets, based on the encoding results, the ICBF can execute the dedicated subtracting and decoding operations to recognize the different elements and differences in the multiplicities of elements between the two multisets. We conduct comprehensive experiments to evaluate and compare the three dedicated multiset synchronization approaches proposed in this paper. The evaluation results indicate that the ICBF-based approach outperforms the other two approaches in terms of synchronization accuracy, timeconsumption, and communication overhead.

Network configuration and policy updates occur frequently, and must be performed in a way that minimizes transient effects caused by intermediate states of the network. It has been shown that accurate time can be used for coordinating network-wide updates, thereby reducing temporary inconsistencies. However, this approach presents a great challenge; even if network devices have perfectly synchronized clocks, how can we guarantee that updates are performed at the exact time for which they were scheduled? In this paper, we present a practical method for implementing accurate time-based updates, using TimeFlips. A TimeFlip is a time-based update that is implemented using a timestamp field in a ternary content addressable memory (TCAM) entry. TimeFlips can be used to implement atomic bundle updates, and to coordinate network updates with high accuracy. We analyze the amount of TCAM resources required to encode a TimeFlip, and show that if there is enough flexibility in determining the scheduled time, a TimeFlip can be encoded by a single TCAM entry, using a single bit to represent the timestamp, while allowing a very high degree of accuracy.

This paper addresses the problem of scheduling a single resource to handle requests for time-sensitive periodic services (i.e., data streams) jointly realizing a distributed application. We specifically consider the case, where the demand of each data stream is expressed as a weight relative to a network-wide cyclic schedule. Within this context, we consider the problem of minimizing the schedule length while satisfying the perfect periodicity constraints: the service intervals for the same data stream are fixed and each data stream is cyclically served exactly as many times as its demand. This problem is challenging, as serving a data stream in one time slot might enforce serving it at some specific time slots in the future. As a result, most of the existing solutions have relaxed either the periodicity or the demand constraints of the data streams. In contrast, we study the strict enforcement of both requirements through perfectly periodic schedules. We show that the considered problem is NP-hard and address special cases for which optimal schedules can be derived. We further discuss the more generic instance of the problem represented by an arbitrary number of data streams and demands. Specifically, we provide an approximation algorithm and an efficient greedy solution for such a general case of arbitrary weights. We conduct extensive simulations to evaluate the performance of the proposed solutions. Finally, we show that it is possible to relax the input demands to improve the communication performance at the cost of some other overhead (e.g., in terms of energy consumption).

Packet classification is a building block in many network services, such as routing, monitoring, and policy enforcement. In commodity switches, classification is often performed by memory components of various rule matching patterns (longest prefix match, ternary matches, exact match, and so on). The memory components are fast but expensive and power-hungry with power consumption proportional to their size. In this paper, we study the applicability of rule caching and lossy compression to create packet classifiers requiring much less memory than the theoretical size limits of the semantically-equivalent representations, enabling significant reduction in their cost and power consumption. This paper focuses on the longest prefix matching. Our objective is to find a limited-size longest prefix match classifier that can correctly classify a high portion of the traffic, so that it can be implemented in commodity switches with classification modules of restricted size. While for the lossy compression scheme a small amount of traffic might observe classification errors, a special indication is returned for traffic that cannot be classified in the rule caching scheme. We develop optimal dynamic-programming algorithms for both problems and describe how to treat the small amount of traffic that cannot be classified. We generalize our solutions for a wide range of classifiers with different similarity metrics. We evaluate their performance on real classifiers and traffic traces and show that in some cases we can reduce a classifier size by orders of magnitude while still classifying almost all traffic correctly.

Pipelines are widely used to increase throughput in multi-core chips by parallelizing packet processing while relying on virtualization. Typically, each packet type is served by a dedicated pipeline with several cores, each implementing a network service. However, with the increase in the number of packet types and their number of required services, there are not enough cores for pipelines. In this paper, we study pipeline sharing, such that a single pipeline can be used to serve several packet types. Pipeline sharing decreases the needed total number of cores, but typically increases pipeline lengths and therefore packet delays. We consider two novel optimization problems of allocating cores between different packet types such that the average or the worst-case delay is minimized. We study the two problems and suggest optimal algorithms that apply under different assumptions on the input. We also present greedy algorithms for the general case. Last, we examine our solutions on synthetic examples as well as on real-life applications and demonstrate that they often achieve close-to-optimal delays.

The most demanding tenants of shared clouds require complete isolation from their neighbors, in order to guarantee that their application performance is not affected by other tenants. Unfortunately, while shared clouds can offer an option whereby tenants obtain dedicated servers, they do not offer any network provisioning service, which would shield these tenants from network interference. In this paper, we introduce Links as a Service (LaaS), a new abstraction for cloud service that provides isolation of network links. Each tenant gets an exclusive set of links forming a virtual fat-tree, and is guaranteed to receive the exact same bandwidth and delay as if it were alone in the shared cloud. Consequently, each tenant can use the forwarding method that best ?ts its application. Under simple assumptions, we derive theoretical conditions for enabling LaaS without capacity over-provisioning in fat-trees. New tenants are only admitted in the network when they can be allocated hosts and links that maintain these conditions. LaaS is implementable with common network gear, tested to scale to large networks and provides full tenant isolation at the worst cost of a 10% reduction in the cloud utilization.

In enterprise networks, network functions such as address translation, firewall and deep packet inspection are often implemented in middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. Traditionally, middlebox survivability is achieved by an expensive active-standby deployment where each middlebox has a backup instance, which is activated in case of a failure. Network Function Virtualization (NFV) is a novel networking paradigm allowing flexible, scalable and inexpensive implementation of network services. In this work we suggest a novel approach for planning and deploying backup schemes for network functions that guarantee high levels of survivability with significant reduction in resource consumption. In the suggested backup scheme we take advantage of the flexibility and resource-sharing abilities of the NFV paradigm in order to maintain only a few backup servers, where each can serve one of multiple functions when corresponding middleboxes are unavailable. We describe different goals that network designers can take into account when determining which functions to implement in each of the backup servers. We rely on a graph theoretical model to find properties of efficient assignments and to develop algorithms that can find them. Extensive experiments show, for example, that under realistic function failure probabilities, and reasonable capacity limitations, one can obtain 99.9% survival probability with half the number of servers, compared to standard techniques.

The Internet routing ecosystem is facing substantial scalability challenges due to continuous, significant growth of the state represented in the data plane. Distributed switch architectures introduce additional constraints on efficient implementations from both lookup time and memory footprint perspectives. In this work we explore efficient FIB representations in common distributed switch architectures. Our approach introduces substantial savings in memory footprint transparently for existing hardware. Our results are supported by an extensive simulation study on real IPv4 and IPv6 FIBs.

Network survivability has been recognized as an issue of major importance in terms of security, stability and prosperity. A crucial research problem in this context is the identification of suitable pairs of disjoint paths. Here, “disjointness” can be considered in terms of either nodes or links. Accordingly, several studies have focused on finding pairs of either link or node disjoint paths with a minimum sum of link weights. In this study, we investigate the gap between the optimal node-disjoint and link-disjoint solutions. Specifically, we formalize several optimization problems that aim at finding minimum-weight link-disjoint paths while restricting the number of its common nodes. We establish that some of these variants are computationally intractable, while for other variants we establish polynomial-time algorithmic solutions. Finally, through extensive simulations, we show that, by allowing link-disjoint paths share a few common nodes, a major improvement is obtained in terms of the quality (i.e., total weight) of the solution.

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench (with real parameters), 90-95% of rules are thus handled, and the other 5-10% of rules can be stored in TCAM to be processed in parallel.

Hardware-based packet classification has become an essential component in many networking devices. It often relies on ternary content-addressable memories (TCAMs), which compare the packet header against a set of rules. TCAMs are not well suited to encode range rules. Range rules are often encoded by multiple TCAM entries, and little is known about the smallest number of entries that one needs for a specific range. In this paper, we introduce the In/Out TCAM, a new architecture that combines a regular TCAM together with a modified TCAM. This custom architecture enables independent encoding of each rule in a set of rules. We provide the following theoretical results for the new architecture: 1) We give an upper bound on the worst-case expansion of range rules in one and two dimensions. 2) For extremal ranges, which are 89% of the ranges that occur in practice, we provide an efficient algorithm that computes an optimal encoding. 3) We present a closed-form formula for the average expansion of an extremal range.

Coping with network failures has become a major networking challenge. The concept of tunable survivability provides a quantitative measure for specifying any desired level (0%-100%) of survivability, thus offering flexibility in the routing choice. Previous works focused on implementing this concept on unicast transmissions. However, vital network information is often broadcast via spanning trees. Accordingly, in this study, we investigate the application of tunable survivability for efficient maintenance of spanning trees under the presence of failures. We establish efficient algorithmic schemes for optimizing the level of survivability under various QoS requirements. In addition, we derive theoretical bounds on the number of required trees for maximum survivability. Finally, through extensive simulations, we demonstrate the effectiveness of the tunable survivability concept in the construction of spanning trees. Most notably, we show that, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees.

Packet classification is a building block in many network services such as routing, filtering, intrusion detection, accounting, monitoring, load-balancing and policy enforcement. Compression has gained attention recently as a way to deal with the expected increase of classifiers size. Typically, compression schemes try to reduce a classifier size while keeping it semantically-equivalent to its original form. Inspired by the advantages of popular compression schemes (e.g. JPEG and MPEG), we study in this paper the applicability of lossy compression to create packet classifiers requiring less memory than optimal semantically-equivalent representations. Our objective is to find a limited-size classifier that can correctly classify a high portion of the traffic so that it can be implemented in commodity switches with classification modules of a given size. We develop optimal dynamic programming based algorithms for several versions of the problem and describe how a small amount of traffic that cannot be classified can be easily treated, especially in software-defined networks. We generalize our solutions for a wide range of classifiers with different similarity metrics. We evaluate their performance on real classifiers and traffic traces and show that in some cases we can reduce a classifier size by orders of magnitude while still classifying almost all traffic correctly.

In enterprise networks, policies (e.g., QoS or security) are often defined based on the categorization of hosts along dimensions such as the organizational role of the host (faculty vs. student), and department (engineering vs. sales). While current best practices (VLANs) help when hosts are categorized along a single dimension, policy may often need to be expressed along multiple orthogonal dimensions. In this paper, we make three contributions. First, we argue for Attribute-Carrying IPs (ACIPs), where the IP address allocation process in enterprises considers attributes of a host along all policy dimensions. ACIPs enable flexible policy specification in a manner that may not otherwise be feasible owing to the limited size of switch rule-tables. Second, we present Alpaca, algorithms for realizing ACIPs under practical constraints of limited-length IP addresses. Our algorithms can be applied to different switch architectures, and we provide bounds on their performance. Third, we demonstrate the importance and viability of ACIPs on data collected from real campus networks.

Network configuration and policy updates occur frequently, and must be performed in a way that minimizes transient effects caused by intermediate states of the network. It has been shown that accurate time can be used for coordinating network-wide updates, thereby reducing temporary inconsistencies. However, this approach presents a great challenge; even if network devices have perfectly synchronized clocks, how can we guarantee that updates are performed at the exact time for which they were scheduled? In this paper we present a practical method for implementing accurate time-based updates, using TIMEFLIPs. A TimeFlip is a time-based update that is implemented using a timestamp field in a Ternary Content Addressable Memory (TCAM) entry. TIMEFLIPs can be used to implement Atomic Bundle updates, and to coordinate network updates with high accuracy. We analyze the amount of TCAM resources required to encode a TimeFlip, and show that if there is enough flexibility in determining the scheduled time, a TimeFlip can be encoded by a single TCAM entry, using a single bit to represent the timestamp, and allowing the update to be performed with an accuracy on the order of 1 microsecond.

In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is harmful and should not be queried. We first analyze conditions under which the Bloom paradox occurs in a Bloom Filter and demonstrate that it depends on the a priori probability that a given element belongs to the represented set. We show that the Bloom paradox also applies to Counting Bloom Filters (CBFs) and depends on the product of the hashed counters of each element. In addition, we further suggest improved architectures that deal with the Bloom paradox in Bloom Filters, CBFs, and their variants. We further present an application of the presented theory in cache sharing among Web proxies. Lastly, using simulations, we verify our theoretical results and show that our improved schemes can lead to a large improvement in the performance of Bloom Filters and CBFs.

We study a perfectly-periodic scheduling problem of a resource shared among several users. Each user is characterized by a weight describing the number of times it has to use the resource within a cyclic schedule. With the constraint that the resource can be used by at most one user in each time slot, we would like to find a schedule with a minimal time period (number of time slots), in which each user is served once in a fixed number of time slots according to its required total number of times. As many other variants of periodic-scheduling problems, we first prove that the problem is NP-hard. We then describe different cases for which we can calculate the exact value of the optimal time period and present algorithms that obtain optimal schedules. We also study the optimal time period in the case of two users with random weights drawn according to known distributions. We then discuss the general case of arbitrary number of users with general weights and provide approximation algorithms that achieve schedules with guaranteed time periods. Last, we conduct simulations to examine the presented analysis.

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time \emph{and} allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench (with real parameters), 90-95% of rules are thus handled, and the other 5-10% of rules can be stored in TCAM to be processed in parallel.

Coping with network failures has become a major networking challenge. The concept of tunable survivability provides a quantitative measure for specifying any desired level (0%-100%) of survivability, thus offering flexibility in the routing choice. Previous works focused on implementing this concept on unicast transmissions. However, vital network information is often broadcasted via spanning trees. Accordingly, in this study, we investigate the application of tunable survivability for efficient maintenance of spanning trees under the presence of failures. We establish efficient algorithmic schemes for optimizing the level of survivability under various QoS requirements. In addition, we derive theoretical bounds on the number of required trees for maximum survivability. Finally, through extensive simulations, we demonstrate the effectiveness of the tunable survivability concept in the construction of spanning trees. Most notably, we show that, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees.

With the rise of datacenter virtualization, the number of entries in the forwarding tables of datacenter switches is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes would not fit on-chip memory using current implementations. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we show that although finding the optimal encoding is NP-hard, we can suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

Packet reordering has now become one of the most significant bottlenecks in next-generation switch designs. A switch practically experiences a reordering delay contagion, such that a few late packets may affect a disproportionate number of other packets. This contagion can have two possible forms. First, since switch designers tend to keep the switch flow order, i.e., the order of packets arriving at the same switch input and departing from the same switch output, a packet may be delayed due to packets of other flows with little or no reason. Further, within a flow, if a single packet is delayed for a long time, then all the other packets of the same flow will have to wait for it and suffer as well. In this paper, we suggest solutions against this reordering contagion. We first suggest several hash-based counter schemes that prevent inter-flow blocking and reduce reordering delay. We further suggest schemes based on network coding to protect against rare events with high queueing delay within a flow. Last, we demonstrate using both analysis and simulations that the use of these solutions can indeed reduce the resequencing delay. For instance, resequencing delays are reduced by up to an order of magnitude using real-life traces and a real hashing function.

Counting Bloom Filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error and support element deletions unlike Bloom Filters. However, they consume significant amounts of memory. In this paper, we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. Unlike CBFs, at each element insertion, the hashed counters are incremented by a hashed variable increment instead of a unit increment. Then, to query an element, the exact value of a counter is considered and not just its positiveness. We present two simple schemes based on this method. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems. We also show how it can be easily implemented in hardware, with limited added complexity and memory overhead. We further explain how this method can extend many variants of CBF that have been published in the literature. We then suggest possible improvements of the presented schemes and provide lower bounds on their memory consumption. Lastly, using simulations with real-life traces and hash functions, we show how it can significantly improve the false positive rate of CBFs given the same amount of memory.

Hardware-based packet classification has become an essential component in many networking devices. It often relies on TCAMs (ternary content-addressable memories), which need to compare the packet header against a set of rules. But efficiently encoding these rules is not an easy task. In particular, the most complicated rules are range rules, which usually require multiple TCAM entries to encode them. However, little is known on the optimal encoding of such non-trivial rules. In this work, we take steps towards finding an optimal encoding scheme for every possible range rule. We first present an optimal encoding for all possible generalized extremal rules. Such rules represent 89% of all non-trivial rules in a typical real-life classification database. We also suggest a new method of simply calculating the optimal expansion of an extremal range, and present a closed-form formula of the average optimal expansion over all extremal ranges. Next, we present new bounds on the worst-case expansion of general classification rules, both in one-dimensional and two-dimensional ranges. Last, we introduce a new TCAM architecture that can leverage these results by providing a guaranteed expansion on the tough rules, while dealing with simpler rules using a regular TCAM. We conclude by verifying our theoretical results in experiments with synthetic and real-life classification databases.

With the rise of datacenter virtualization, the number of entries in forwarding tables is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes can hardly be implemented today in on-chip memory. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

To enable direct access to a memory word based on its index, memories make use of fixed-width arrays, in which a fixed number of bits is allocated for the representation of each data entry. In this paper we consider the problem of encoding data entries of two fields, drawn independently according to known and generally different distributions. Our goal is to find two prefix codes for the two fields, that jointly maximize the probability that the total length of an encoded data entry is within a fixed given width. We study this probability and develop upper and lower bounds. We also show how to find an optimal code for the second field given a fixed code for the first field.

In recent years, hardware-based packet classification has became an essential component in many networking devices. It often relies on ternary content-addressable memories (TCAMs), which can compare in parallel the packet header against a large set of rules. Designers of TCAMs often have to deal with unpredictable sets of rules. These result in highly variable rule expansions, and can only rely on heuristic encoding algorithms with no reasonable guarantees. In this paper, given several types of rules, we provide new upper bounds on the TCAM worst case rule expansions. In particular, we prove that a W-bit range can be encoded in W TCAM entries, improving upon the previously known bound of 2W - 5. We further prove the optimality of this bound of W for prefix encoding, using new analytical tools based on independent sets and alternating paths. Next, we generalize these lower bounds to a new class of codes called hierarchical codes that includes both binary codes and Gray codes. Last, we propose a modified TCAM architecture that can use additional logic to significantly reduce the rule expansions, both in the worst case and using real-life classification databases.

In this paper, we uncover the Bloom paradox in Bloom filters: sometimes, it is better to disregard the query results of Bloom filters, and in fact not to even query them, thus making them useless. We first analyze conditions under which the Bloom paradox occurs in a Bloom filter, and demonstrate that it depends on the a priori probability that a given element belongs to the represented set. We show that the Bloom paradox also applies to Counting Bloom Filters (CBFs), and depends on the product of the hashed counters of each element. In addition, both for Bloom filters and CBFs, we suggest improved architectures that deal with the Bloom paradox. We also provide fundamental memory lower bounds required to support element queries with limited false-positive and false-negative rates. Last, using simulations, we verify our theoretical results, and show that our improved schemes can lead to a significant improvement in the performance of Bloom filters and CBFs.

Counting Bloom Filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error, and support element deletions unlike Bloom Filters. However, they consume significant amounts of memory. In this paper we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. Unlike CBFs, at each element insertion, the hashed counters are incremented by a hashed variable increment instead of a unit increment. Then, to query an element, the exact value of a counter is considered and not just its positiveness. We present two simple schemes based on this method. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems. We also show how it can be easily implemented in hardware, with limited added complexity and memory overhead. We further explain how this method can extend many variants of CBF that have been published in the literature. Last, using simulations, we show how it can improve the false positive rate of CBFs by up to an order of magnitude given the same amount of memory.

Designers of TCAMs (Ternary CAMs) for packet classification deal with unpredictable sets of rules, resulting in highly variable rule expansions, and rely on heuristic encoding algorithms with no reasonable expansion guarantees. In this paper, given several types of rules, we provide new upper bounds on the TCAM worst-case rule expansions. In particular, we prove that a W-bit range can be encoded using W TCAM entries, improving upon the previously-known bound of 2W-5. We also propose a modified TCAM architecture that uses additional logic to significantly reduce the rule expansions, both in the worst case and in experiments with real-life classification databases.

All high-speed Internet devices need to implement classification, i.e. they must determine whether incoming packet headers belong to a given subset of a search space. To do it, they encode the subset using ternary arrays in special high-speed devices called TCAMs (ternary content-addressable memories). However, the optimal coding for arbitrary subsets is unknown. In particular, to encode an arbitrary range subset of the space of all W-bit values, previous works have successively reduced the upper-bound on the code length from 2W-2 to 2W-4, then 2W-5, and finally W TCAM entries. In this paper, we prove that this final result is optimal for typical prefix coding and cannot be further improved, i.e. the bound of W is tight. To do so, we introduce new analytical tools based on independent sets and alternating paths.

Chip multiprocessors (CMPs) combine increasingly many general-purpose processor cores on a single chip. These cores run several tasks with unpredictable communication needs, resulting in uncertain and often-changing traffic patterns. This unpredictability leads network-on-chip (NoC) designers to plan for the worst case traffic patterns, and significantly overprovision link capacities. In this paper, we provide NoC designers with an alternative statistical approach. We first present the traffic-load distribution plots (T-Plots), illustrating how much capacity overprovisioning is needed to service 90, 99, or 100 percent of all traffic patterns. We prove that in the general case, plotting T-Plots is #P-complete, and therefore extremely complex. We then show how to determine the exact mean and variance of the traffic load on any edge, and use these to provide Gaussian-based models for the T-Plots, as well as guaranteed performance bounds. We also explain how to practically approximate T-Plots using random-walk-based methods. Finally, we use T-Plots to reduce the network power consumption by providing an efficient capacity allocation algorithm with predictable performance guarantees.