Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured to provide direct connectivity between racks, in the form of edge-disjoint matchings. While state-of-the-art optical switches in principle support microsecond reconfigurations, the demand-aware topology optimization constitutes a bottleneck.

This paper proposes a dynamic algorithms approach to improve the performance of reconfigurable datacenter networks, by supporting faster reactions to changes in the traffic demand. This approach leverages the temporal locality of traffic patterns in order to update the interconnecting matchings incrementally, rather than recomputing them from scratch. In particular, we present six (batch-)dynamic algorithms and compare them to static ones. We conduct an extensive empirical evaluation on 176 synthetic and 39 real-world traces, and find that dynamic algorithms can both significantly improve the running time and reduce the number of changes to the configuration, especially in networks with high temporal locality, while retaining matching quality.

Network operators want to enforce fair bandwidth sharing between users without solely relying on congestion control running on end-user devices. However, in edge networks (e.g., 5G), the number of user devices sharing a bottleneck link far exceeds the number of queues supported by today's switch hardware; even accurately tracking per-user sending rates may become too resource-intensive. Meanwhile, traditional software-based queuing on CPUs struggles to meet the high throughput and low latency demanded by 5G users.
We propose Approximate Hierarchical Allocation of Bandwidth (AHAB), a per-user bandwidth limit enforcer that runs fully in the data plane of commodity switches. AHAB tracks each user's approximate traffic rate and compares it against a bandwidth limit, which is iteratively updated via a real-time feedback loop to achieve max-min fairness across users. Using a novel sketch data structure, AHAB avoids storing per-user state, and therefore scales to thousands of slices and millions of users. Furthermore, AHAB supports network slicing, where each slice has a guaranteed share of the bandwidth that can be scavenged by other slices when under-utilized. Evaluation shows AHAB can achieve fair bandwidth allocation within 3.1ms, 13x faster than prior data-plane hierarchical schedulers.

Datacenters rely on high-bandwidth networks that use inexpensive, shared-buffer switches. The combination of high bandwidth, bursty traffic patterns, and shallow buffers imply that switch buffer is a heavily contended resource and intelligent management of shared buffers among competing traffic (ports, traffic classes) becomes an important challenge. Dynamic Threshold (DT), which is the current state-of-the-art in buffer management, provides either high bandwidth utilization with poor burst absorption/fairness or good burst absorption/fairness with inferior utilization, but not both. We present Protean, which dynamically identifies bursty traffic and allocates more buffer space accordingly. Protean provides more space to queues that experience transient load spikes by observing the gradient of queue length but does not cause persistent unfairness as the gradient cannot continue to remain high in shallow buffered switches for long
periods of time. We implemented Protean in today's programmable switches and demonstrate their high performance with negligible overhead. Our at-scale ns-3 simulations show that Protean
reduces the tail latency by a factor of 5 over DT on average across varying loads with realistic workloads.

Recent datacenter network topologies are shifting towards heterogeneous and structured topologies for high throughput, low cost, and simple manageability. However, they rely on sub-optimal routing approaches that fail to achieve their designed capacity. This paper proposes a process for designing optimal oblivious routing that is programmed compactly on programmable switches. The process consists of three contributions in tandem. We first transform a robust optimization problem for designing oblivious routing into a linear program, which is solvable in polynomial time for small-scale topologies. We then prove that the repeated structures in a datacenter topology lead to a structured optimal solution. We use this insight to formulate a scalable linear program, so an optimal oblivious routing solution is obtained in polynomial time for large-scale topologies. For real-world deployment, the optimal solution is converted to forwarding rules for programmable switches with stringent memory. With this constraint, we utilize the repeated structures in the optimal solution to group the forwarding rules, resulting in compact forwarding rules with a much smaller memory requirement. Extensive evaluations show our process i) obtains optimal solutions faster and more scalable than a state-of-the-art technique and ii) reduces the memory requirement by no less than 90% for most considered topologies.

In object detection and recognition, similar but nonidentical sensing data probably maps to the same result. Therefore, a cache preserving popular results that supports approximate match for similar input requests can accelerate the task by avoiding the otherwise expensive deep learning model inferences. However, the current software and hardware practices carried on edge or cloud servers are less efficient in both cost and performance. Taking advantage of the on-path programmable switches, we propose In-Switch Approximate Cache (ISAC) to reduce the server workload and latency. The unique approximate matching requirement sets ISAC apart from a conventional exact-match cache. Equipped with efficient encoding and qualifying algorithms, ISAC in an on-path switch can fulfill most of the input requests with high accuracy. When adapting to a P4 programmable switch, it can sustain up to 194M frames per second and fulfill 60.3% of them, achieving a considerable reduction on detection latency, server cost, and power consumption. Readily deployable in existing network infrastructure, ISAC is the first-of-its-kind approximate cache that can be completely implemented in a switch to support a class of IoT applications.

We study the caching problem from an online learning point-of-view, i.e., no model assumptions and prior knowledge for the file request sequence. Our goal is to design an efficient online caching policy with minimal regret, i..e, minimizing the total number of cache-miss with respect to the best static configuration in hindsight. Previous studies such as Follow-The-Perturbed-Leader (FTPL) caching policy, have provided some near-optimal results, but their theoretical performance guarantees only valid for the regime wherein all arrival requests could be seen by the cache, which is not the case in some practical scenarios. Hence our work closes this gap by considering the partial-feedback regime wherein only requests for currently cached files are seen by the cache, which is more challenging and has not been studied before. We propose an online caching policy integrating the FTPL with a novel popularity estimation procedure called Geometric Resampling (GR), and show that it yields the first sublinear regret guarantee in this regime. We also conduct numerical experiments to validate the theoretical guarantees of our algorithm.

With the rapidly changing network, rule update in TCAM has become the bottleneck for application performance. In traditional software-defined networks, some application policies are deployed at the edge switches, while the scarce TCAM spaces exacerbate the frequency and difficulty of rule updates. This paper proposes CoLUE, a framework which groups rules into switches in a balance and dependency minimum way. CoLUE is the first work that combines TCAM update and rule placement, making full use of TCAM in distributed switches. Not only does it accelerate update speed, it also keeps the TCAM space load-balance across switches. Composed of ruleset decomposition and subset distribution, CoLUE has an NP-completeness challenge. We propose heuristic algorithms to calculate a near-optimal rule placement scheme. Our evaluations show that CoLUE effectively balances TCAM space load and reduces the average update cost by more than 1.45 times and the worst-case update cost by up to 5.46 times, respectively.

RDMA provides extremely low latency and high bandwidth to distributed systems. But the increasing scale of RDMA networks requires hosts to establish a large number of connections for data exchange, i.e., process-level full mesh, causing heavy performance overhead of the system. This paper presents SRM, a scalable transport mode for RDMA networks. To forestall resource explosion, SRM proposes a kernel-based solution to multiplex workloads from different applications on the same connection. Meanwhile, to preserve RDMA's performance benefits, SRM 1) shares work memory between user space and kernel to avoid syscall overhead; 2) proposes a lock-free approach to prevent SRM from suffering low resource utilization due to contention; 3) adopts multiple optimizations to alleviate head-of-line blocking issues; 4) designs a rapid recovery mechanism to provide high system robustness. We evaluate SRM using extensive testbed experiments and simulations. Microbenchmarks reveal that SRM outperforms tested transports including DCT, RC and XRC, by 4x to 20x in latency performance for all-to-all communication pattern. Simulations of large-scale networks with synthesized traffic from real workloads show that, compared with DCT, RC and XRC, SRM achieves up to 4.42x/4.0x/3.7x speedups respectively in flow completion time while consuming the least memory.

Flow table is a fundamental and critical component in network data plane. Numerous algorithms and architectures have been devised for efficient flow table construction, lookup, and update. The diversity of flow tables and the difficulty to acquire real data sets make it challenging to give a fair and confident evaluation to a design. In the past, researchers rely on ClassBench and its improvements to synthesize flow tables, which become inadequate for today's networks. In this paper, we present a new flow table benchmark tool, FlowBench. Based on a novel design methodology, FlowBench can generate large-scale flow tables with arbitrary combination of matching types and fields in a short time, and yet keep accurate characteristics to reveal the real performance of the algorithms under evaluation. The open-source tool facilitates researchers to evaluate both existing and future algorithms with unprecedented flexibility.

In-band Network Telemetry (INT) and sketching algorithms are two promising directions for measuring network traffics in real time. To combine sketch with INT and preserve their advantages, a representative approach is to use INT to send a switch sketch in small pieces (called sketchlets) to end-host for reconstructing an identical sketch. However, in this paper, we reveal that when naively selecting buckets to sketchlets, the end-host reconstructed sketch is inaccurate. To overcome this problem, we present DUNE, an innovative sketch-INT network measurement system. DUNE incorporates two key innovations: First, we design a novel scatter sketchlet that is more efficient in transferring measurement data by allowing a switch to select individual buckets to add to sketchlets; Second, we propose lightweight data structures for tracing "freshness" of the sketch buckets, and present algorithms for smartly selecting buckets that contain valuable measurement data to send to end-host. We theoretically prove the effectiveness of our proposed methods, and implement a prototype on commodity programmable switch. The results of extensive experiments driven by real-world traffics on DUNE suggest that our proposed system can substantially improve the measurement accuracy at a trivial cost.

Despite that Function-as-a-Service (FaaS) has settled down as one of the fundamental cloud programming models, it is still evolving quickly. Recently, Amazon has introduced S3 Object Lambda, which allows a user-defined function to be automatically invoked to process an object as it is being downloaded from S3. As with any new feature, careful study thereof is the key to elucidate if S3 Object Lambda, or more generally, if inline serverless data processing, is a valuable addition to the cloud. For this reason, we conduct an extensive measurement study of this novel service, in order to characterize its architecture and performance (in terms of coldstart latency, TTFB times, and more). We particularly put an eye on the streaming capabilities of this new form of function, as it may open the door to empower existing serverless systems with stream processing capacities.We discuss the pros and cons of this new capability through several workloads, concluding that S3 Object Lambda can go far beyond its original purpose and be leveraged as a building block for more complex abstractions.

Global-scale IPv6 scan, critical for network measurement and management, is still a mission to be accomplished due to its vast address space. To tackle this challenge, IPv6 scan generally leverages pre-defined seed addresses to guide search directions. Under this general principle, however, the core problem of effectively using the seeds is still largely open. In this work, we propose a novel IPv6 active search strategy, namely HMap6, which significantly improves the use of seeds, w.r.t. the marginal benefit, for large-scale active address discovery in various prefixes. Using a heuristic search strategy for efficient seed collection and alias prefix detection under a wide range of BGP prefixes, HMap6 can greatly expand the scan coverage. Real-world experiments over the Internet in billion-scale scans show that HMap6 can discover 29.39M unique /80 prefixes with active addresses, an 11.88\% improvement over the state-of-the-art methods. Furthermore, the IPv6 hitlists from HMap6 include all-responsive IPv6 addresses with rich information. This result sharply differs from existing public IPv6 hitlists, which contain non-responsive and filtered addresses, and pushes the IPv6 hitlists from quantity to quality. To encourage and benefit further IPv6 measurement studies, we released our tool along with our IPv6 hitlists and the detected alias prefixes.