Key-value lookup functions have been widely applied to network applications, including FIBs, load balancers, and content distributions. Two key performance requirements of a lookup algorithm are high throughput and small memory cost. One limitation of existing fast network lookup algorithms is that they require multiple independent and uniform hash functions, which cost high computation time and might not be available on existing hardware network devices. Recently developed learned model hashing (LMH) proposes to use a linear machine learning model to replace hash functions to avoid hash computation, but they are not optimized for memory cost. We propose a novel network lookup method called Parrot hashing, which uses a learned model to distribute keys into different buckets and applies a simple perfect hashing method to resolve the collisions of the keys in a bucket. Parrot can be implemented with only one CRC-8, which is available on all network devices. We implement Parrot in three prototypes: a software program on end hosts, a software switch, and a FIB running on a hardware programmable switch. The experimental results show that Parrot achieves the highest lookup throughput on all three prototypes, compared to existing methods. Its memory cost is also significantly lower than that of LMH.

Key-value lookup functions have been widely applied to network applications, including FIBs, load balancers, and content distributions. Two key performance requirements of a lookup algorithm are high throughput and small memory cost. One limitation of existing fast network lookup algorithms is that they require multiple independent and uniform hash functions, which cost high computation time and might not be available on existing hardware network devices. Recently developed learned model hashing (LMH) proposes to use a linear machine learning model to replace hash functions to avoid hash computation, but they are not optimized for memory cost. We propose a novel network lookup method called Parrot hashing, which uses a learned model to distribute keys into different buckets and applies a simple perfect hashing method to resolve the collisions of the keys in a bucket. Parrot can be implemented with only one CRC8, which is available on all network devices. We implement Parrot in three prototypes: a software program on end hosts, a software switch, and a FIB running on a hardware programmable switch. The experimental results show that Parrot achieves the highest lookup throughput on all three prototypes, compared to existing methods. Its memory cost is also significantly lower than that of LMH.

Disaggregated memory systems achieve resource utilization efficiency and system scalability by distributing computation and memory resources into distinct pools of nodes. RDMA is an attractive solution to support high-throughput communication between different disaggregated resource pools. However, existing RDMA solutions face a dilemma: one-sided RDMA completely bypasses computation at memory nodes, but its communication takes multiple round trips; two-sided RDMA achieves one-round-trip communication but requires non-trivial computation for index lookups at memory nodes, which violates the principle of disaggregated memory. This work presents Outback, a novel indexing solution for key-value stores with a one-round-trip RDMA-based network that does not incur computation-heavy tasks at memory nodes. Outback is the first to utilize dynamic minimal perfect hashing and separates its index into two components: one memory-efficient and compute-heavy component at compute nodes and the other memory-heavy and compute-efficient component at memory nodes. We implement a prototype of Outback and evaluate its performance in a public cloud. The experimental results show that Outback achieves higher throughput than both the state-of-the-art one-sided RDMA and two-sided RDMA-based in-memory KVS by 1.06--5.03×, due to the unique strength of applying a separated perfect hashing index.

Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

User-associated contents play an increasingly important role in modern network applications. With growing deployments of edge servers, the capacity of content storage in edge clusters significantly increases, which provides great potential to satisfy content requests with much shorter latency. However, the large number of contents also causes the difficulty of searching contents on edge servers in different locations because indexing contents costs huge DRAM on each edge server. In this work, we explore the opportunity of efficiently indexing user-associated contents and propose a scalable content-sharing mechanism for edge servers, called EdgeCut, that significantly reduces content access latency by allowing many edge servers to share their cached contents. We design a compact and dynamic data structure called Ludo Locator that returns the IP address of the edge server that stores the requested user-associated content. We have implemented a prototype of EdgeCut in a real network environment running in a public geo-distributed cloud. The experiment results show that EdgeCut reduces content access latency by up to 50% and reduces cloud traffic by up to 50% compared to existing solutions. The memory cost is less than 50MB for 10 million mobile users. The simulations using real network latency data show EdgeCut's advantages over existing solutions on a large scale.

Off-chain networks have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. Routing is a core problem. An ideal off-chain networks routing method needs to achieve 1) high scalability that can maintain low per-node memory and communication cost for large networks and 2) high resource utilization of channels. However, none of the existing off-chain routing methods achieve both requirements. In this work, we propose WebFlow, a distributed routing solution for off-chain networks, which only requires each user to maintain localized information and can be used for massive-scale networks with high resource utilization. We make use of two distributed data structures: multi-hop Delaunay triangulation (MDT) originally proposed for wireless networks and our innovation called distributed Voronoi diagram. We propose new protocols to generate a virtual Euclidean space in order to apply MDT to off-chain networks and use the distributed Voronoi diagram to enhance routing privacy. We conduct extensive simulations and prototype implementation to further evaluate WebFlow. The results using real and synthetic off-chain network topologies and transaction traces show that WebFlow can achieve extremely low per-node overhead and a high success rate compared to existing methods.

Radio frequency identification (RFID)-assisted management systems have been widely applied in warehousing, logistics, retailing, etc. In these scenarios, RFID-aided applications, e.g., object tracking and human behavior sensing, rely on a high-efficiency tag reading to realize accurate analyses and timely responses. However, serious tag collisions in those large-scale RFID systems will inevitably lead to significant decreases in the tag reading rates. To meet the strict timeliness requirements of those practical applications, we aim to treat the individual reading rate for each item tag differently and focus more attention on those user-interactive ones. However, due to unpredictable user behaviors, it is impractical to infer the user-interactive tags in advance. In addition, keeping focusing on them for continuous monitoring despite user movements and multipath-prevalent environments is also challenging. To solve these problems, we propose Spotlight, the first concurrent rate-adaptive reading system in passive RFIDs. Spotlight screens the ID-agnostic user-interactive tags by proposing a multichannel feature for narrow-band RFID systems without any hardware or protocol modification and achieves rate-adaptive reading by implementing real-time MU-MIMO beamforming. Substantial experiments with 1000+ COTS RFID tags exhibit that Spotlight outperforms the commercial reader by$2.7\times $and the SDR-based reader by$6.12\times $. In addition, Spotlight first proposes the online parallel decoding method to realize concurrency among multiple users, which breaks the commercial protocol’s throughput ceiling (37%) and achieves up to 59% throughputs.

Allowing a device to verify the digital certificate of another device is an essential requirement and key building block of many security protocols for emerging and future IoT systems that involve device-to-device communication. However, on-device certificate verification is challenging for current devices, mainly because the certificate revocation (CR) checking step costs too much resource on IoT devices and the synchronization of CR status to devices yields a long latency. This paper presents an on-device CR checking system called TinyCR, which achieves 100% accuracy, memory and computation efficiency, low synchronization latency, and low network bandwidth, while being compatible with the current certificate standard. We design a new compact and dynamic data structure called DASS to store and query global CR status on a device in TinyCR. Our implementation shows that TinyCR only costs each device 1.7 MB of memory to track 100 million IoT certificates with 1% revocation rate. Checking the CR status of one certificate spends less than 1 microsecond on a Raspberry Pi 3. TinyCR can also be updated instantly when there are new certificates added or revoked.

Public-key certificate validation is an important building block for various security protocols for IoT devices, such as secure channel establishment, handshaking, and verifying sensing data authenticity from cloud storage. However, certification validation incurs non-trivial overhead on resource-constrained IoT devices, because it either brings long latency or large cache space. This work proposes to utilize the power of distributed caching and explores the feasibility of using the cache spaces on all IoT devices as a large pool to store validated certificates. We design a Collaborative Certificate Validation (CCV) protocol including a memory-efficient and fast locator for certificate holders, a trust model to evaluate the trustworthiness of devices, and a protocol suite for dynamic update and certificate revocation. Evaluation results show that CCV only uses less than 25% validation time and reduces >90% decryption operations on each device, compared to a recent method. Malicious devices that conduct dishonest validations can be detected by the network using the proposed trust model.

A load balancer (LB) is a vital network function for cloud services to balance the load amongst resources. Stateful software LBs that run on commodity servers provide flexibility, cost-efficiency, and packet consistency. However, current designs have two main limitations: 1) states are stored as digests, which may cause packet inconsistency due to digest collisions; 2) the data plane needs to update for every new connection, and frequent updates hurt throughput and packet consistency. In this work, we present a new software stateful LB called Concury, which is the first solution to solve these problems. The key innovation of Concury is a new method to maintain large network states with frequent connection arrivals, which is succinct in memory cost, consistent under network changes, and incurs low update cost. The evaluation results show that the Concury algorithm provides 4x throughput and consumes less memory compared to other LB algorithms, while providing weighted load balancing and false-hit freedom, for both real and synthetic data center traffic. We implement Concury and evaluate it in two real networks. It achieves 67.2 Gbps single-thread throughput on a cheap desktop computer in 100GbE.

Algorithms and data structures for data plane network functions have been extensively studied in the literature. Recently various compact data structures and algorithms have been used in data plane to achieve less memory cost and higher throughput. However, most of these studies only focus on individual network functions, such as packet forwarding information base (FIB), traffic measurement, and load balancing. To our knowledge no study has been conducted to design compact data structures and algorithms for multiple and co-located network functions. We argue that there is a huge space of optimization if we design algorithms and data structures considering multiple co-located network functions, compared to designing them individually. It is because many of them share similar design goals and building blocks. We use two recently published methods as examples and present a new memory-compact design that serves both FIB and traffic measurement functions by a novel integration of the two methods. The preliminary results show that the new design can achieve almost 2x throughput compared to running them individually while achieving higher accuracy of measurement using the same memory. In addition, we will discuss potential research directions and challenges.

Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

We provide the first solution to an important question, “how a physical-layer authentication method can defend against signal replay attacks”. It was believed that if an attacker can replay the exact same reply signal of a legitimate authentication object (such as an RFID tag), any physical-layer authentication method will fail. This paper presents Hu-Fu, the first physical layer RFID authentication protocol that is resilient to the major attacks including tag counterfeiting, signal replay, signal compensation, and brute-force feature reply. Hu-Fu is built on two fundamental ideas, namely inductive coupling of two tags and signal randomization. Hu-Fu does not require any hardware or protocol modification on COTS passive tags and can be implemented with COTS devices. We implement a prototype of Hu-Fu and demonstrate that it is accurate and robust to device diversity and environmental changes, including locations, distance, and temperature. Hu-Fu provides a new direction of battery-free/low-power device authentication that enables numerous IoT applications.

Edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of edge computing when a network of edge servers collaboratively provide data storage. These services require short-latency and low-overhead implementation in network devices and load balance on edge servers. However existing methods such as distributed hash tables (DHTs) are not able to achieve efficient data placement and retrieval services in the edge computing environment. This paper presents GRED, an efficient data placement and retrieval service for edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the software-defined networking paradigm to support a virtual-space based DHT with only one overlay hop. We implement GRED in a P4 prototype. Experimental results show that GRED uses <; 30% routing path lengths and achieves better load balance among edge servers compared to using Chord, a well-known DHT solution.

Forwarding packets based on networking names is essential for network protocols on different layers, where the `names' could be addresses, packet/flow IDs, and content IDs. For long there have been efforts using dynamic and compact data structures for fast and memory-efficient forwarding. In this work, we identify that the recently developed programmable network paradigm has the potential to further reduce the time/memory complexity of forwarding structures by separating the data plane and control plane. This work presents the new designs of network forwarding structures under the programmable network paradigm, applying three typical dynamic and compact data structures: Bloom filters, Cuckoo hashing, and Othello hashing. We conduct careful analyses and experiments in real networks of these forwarding methods for multiple performance metrics, including lookup throughput, memory footprint, construction time, dynamic updates, and lookup errors. The results give rich insights on designing forwarding algorithms with dynamic and compact data structures. In particular, the new designs based on Cuckoo hashing and Othello hashing show significant advantages over the extensively studied Bloom filter based methods, in all situations discussed in this paper.

Public-key certificate validation is an important building block for various security protocols for IoT devices, such as secure channel establishment, handshaking, verifying sensing data authenticity from cloud storage, and Blockchains. However, certification validation incurs non-trivial overhead on resource-constrained IoT devices, because it either requires long latency or large cache space. This work proposes to utilize the power of distributed caching and explores the feasibility of using the cache spaces on all IoT devices as a large pool to store validated certificates. We design a Collaborative Certificate Validation (CCV) protocol including a memory-efficient and fast locator for certificate holders, a trust model to evaluate the trustworthiness of devices, and a protocol suite for dynamic update and certificate revocation. Evaluation results show that CCV only uses less than 25% validation time and reduces >90% decryption operations on each device, compared to a recent method. Malicious devices that conduct dishonest validations can be detected by the network using the proposed trust model.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, these edge servers cache data to provide services for edge users. The data sharing among edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where the switches and the data indexes are associated with the coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying the data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve the data index compared to using Chord, a well-known DHT solution.

We present vacuum filters, a type of data structures to support approximate membership queries. Vacuum filters cost the smallest space among all known AMQ data structures and provide higher insertion and lookup throughput in most situations. Hence they can be used as the replacement of the widely used Bloom filters and cuckoo filters. Similar to cuckoo filters, vacuum filters also store item fingerprints in a table. The memory-efficiency and throughput improvements are from the innovation of a table insertion and fingerprint eviction strategy that achieves both high load factor and data locality without any restriction of the table size. In addition, we propose a new update framework to resolve two difficult problems for AMQ structures under dynamics, namely duplicate insertions and set resizing. The experiments show that vacuum filters can achieve 25% less space in average and similar throughput compared to cuckoo filters, and 15% less space and >10x throughput compared to Bloom filters, with same false positive rates. AMQ data structures are widely used in various layers of computer systems and networks and are usually hosted in platforms where memory is limited and precious. Hence the improvements brought by vacuum filters can be considered significant.

Today's large-scale enterprise networks, data center networks, and wide area networks can be decomposed into multiple administrative or geographical domains. Domains may be owned by different administrative units or organizations. Hence protecting domain information is an important concern. Existing general-purpose Secure Multi-Party Computation (SMPC) methods that preserves privacy for domains are extremely slow for cross-domain routing problems. In this paper we present PYCRO, a cryptographic protocol specifically designed for privacy-preserving cross-domain routing optimization in Software Defined Networking (SDN) environments. PYCRO provides two fundamental routing functions, policy-compliant shortest path computing and bandwidth allocation, while ensuring strong protection for the private information of domains. We rigorously prove the privacy guarantee of our protocol. To improve time efficiency we design the QuIck Pathing (QIP) technique. QIP only requires one-time offline preprocessing and very fast online computation. We have implemented a prototype system that runs PYCRO and QIP on servers in a campus network. Experimental results using real ISP network topologies show that PYCRO and QIP are very efficient in computation and communication costs.