Modern ML applications increasingly rely on complex deep learning models and large datasets. There has been an exponential growth in the amount of computation needed to train the largest models. Therefore, to scale computation and data, these models are inevitably trained in a distributed manner in clusters of nodes, and their updates are aggregated before being applied to the model. However, a distributed setup is prone to Byzantine failures of individual nodes, components, and software. With data augmentation added to these settings, there is a critical need for robust and efficient aggregation systems. We define the quality of workers as reconstruction ratios $\in (0,1]$, and formulate aggregation as a Maximum Likelihood Estimation procedure using Beta densities. We show that the Regularized form of log-likelihood wrt subspace can be approximately solved using iterative least squares solver, and provide convergence guarantees using recent Convex Optimization landscape results. Our empirical findings demonstrate that our approach significantly enhances the robustness of state-of-the-art Byzantine resilient aggregators. We evaluate our method in a distributed setup with a parameter server, and show simultaneous improvements in communication efficiency and accuracy across various tasks.

In-network applications, such as congestion control, load-balancing, and policy enforcement, require complicated arithmetic operations to track networking parameters. Unfortunately, programmable switches that implement protocol independent switch architecture (PISA) support only a limited set of arithmetic operations, such as addition and subtraction, to guarantee high packet throughput. Existing work addresses this problem by implementing unsupported operations (e.g., multiplication) using TCAM match-action tables; they use wildcards to match over a range of operand values. However, because TCAM is a scarce resource, operators must make a difficult trade-off between accuracy and TCAM occupancy. This problem leads to large and unpredictable errors, and also limits the applicability of in-network computing to many applications.In this paper, we propose ADA, a practical, lightweight approach to reduce TCAM entries without sacrificing accuracy by exploiting the value distribution of operands. ADA tracks the operands’ distribution via a simple binning mechanism to determine the most accessed interval in the domain space of operands and allocates more (or less) entries based on the observed distribution. Our proposed mechanism, (1) saves TCAM space for other applications by aggregating entries that are unused or less popular, and (2) reduces average error by assigning more TCAM entries to intervals with a higher probability of occurrence (and sub-divides these intervals further, if needed). We implement ADA on P4 on a 100 Gbps Barefoot Tofino switch and demonstrate its efficacy by deploying it in existing state-of-the-art in-network applications; ADA imposes a negligible overhead of less than 2% in the switch data plane and about 5% in the control plane. We further evaluate ADA using our C++ and ns-3 simulators over two existing arithmetic-heavy applications (i.e., Nimble and RCP) to demonstrate that ADA can achieve performance close to an ideal implementation with unlimited TCAM space.

Memory caches are critical components of modern web services that improve response times and reduce the load on backend databases. In multi-tenant clouds, several instances of caches compete for memory. The current state-of-the-art is to statically allocate memory for cache instances (e.g., based on cost-tier) but such allocation tends to be sub-optimal as memory demands of instances often vary with time and not known apriori. We propose MemSweeper, which dynamically manages memory between cache instances. MemSweeper uses a novel, score-based metric and an associated algorithm to identify cache instances whose working sets fit well within their allocated memory and thus can relinquish a portion of the memory without suffering appreciable loss in their hit rates. Using a combination of synthetic and production traces on a real implementation, we show that MemSweeper achieves 74% improvement (on average) in the miss rate of critical tenants without degrading the performance of other tenants.

This paper presents the motivation and design of MTP, a new offload-friendly message transport protocol. Existing transport protocols like TCP, MPTCP, and UDP/Quic all have key limitations when used in a network that may potentially offload computation from end-servers into NICs, switches, and other network devices. To enable important new in-network computing use cases and correct congestion control in the face of ever changing network paths and application replicas, MTP introduces a new message transport protocol design and pathlet congestion control, a new approach where end-hosts explicitly communicate messaging information to network devices and network devices explicitly communicate network path and congestion information back to end-hosts.

Important datacenter applications generate extremely bursty traffic patterns and demand low latency tails as well as high throughput. Datacenter networks employ shallow-buffered, shared-memory switches to cut cost and to cope up with ever-increasing link speeds. End-to-end congestion control cannot react in time to handle bursty, short flows that dominate datacenter traffic and they incur buffer overflows, which cause long latency tails and degrade throughput. Therefore, there is a need for agile, switch-local mechanisms that quickly sense congestion and provision enough buffer space dynamically to avoid costly buffer overflows. We propose Smartbuf, an online learning algorithm that accurately predicts buffer requirement of each switch port before the onset of congestion. Our key novelty lies in fingerprinting bursts based on the gradient of queue length and using this information to provision just enough buffer space. Our preliminary evaluations show that our algorithm can predict buffer demands accurately within an average error margin of 6% and achieve an improvement in the 99thpercentile latency by a factor of 8x at high loads, while providing good fairness among ports.

Several important datacenter applications cause incast congestion, which severely degrades flow completion times of short flows and throughput of long flows. Further, because most flows are short and the incast duration is shorter than typical round-trip times, reactive mechanisms that rely on congestion control are not effective. While modern datacenter topologies provide high bisection bandwidth to support all-to-all traffic, incast is fundamentally a many-to-one traffic pattern, and therefore, requires deep buffers or high bandwidth at the network edge.

Large data transfers can result in significant congestion and performance degradation for interactive end-user applications such as web browsing and streaming. While there are existing TCP congestion control algorithms for delivery of large volume data (e.g., LEDBAT, TCP-LP), our results show that these protocols are not effective in cellular networks due to variability in radio channel conditions and the use of cellular schedulers in base stations. We propose Legilimens, an agile TCP variant for cellular downlink transfers, which not only retains desirable properties of existing approaches, but also exploits the properties of the cellular schedulers to estimate load and capacity and addresses the challenges in cellular networks. As a result, Legilimens is able to deliver traffic using only the spare capacity on the downlink. We conduct extensive evaluations of Legilimens in multiple settings-in a large cellular network for real-world performance, on the PhantomNet emulator for controlled experiments, and ns-3 simulator for scaled experiments-all of which demonstrate that Legilimens is superior to existing protocols in transferring large volumes of data without interfering with regular user traffic. Compared to existing low-priority protocols, Legilimens improves the throughput of background flows by 2x on average (up to 5x) without degrading the performance of foreground flows across all the three testbeds.

Datacenters host a mix of applications: foreground applications perform distributed lookups in order to service user queries and background applications perform batch processing tasks such as data reorganization, backup, and replication. While background flows produce the most load, foreground applications produce the most number of flows. Because packets from both types of applications compete at switches for network bandwidth, the performance of applications is sensitive to scheduling mechanisms. Existing schedulers use flow size to distinguish critical flows from non-critical flows. However, recent studies on datacenter workloads reveal that most flows are small (e.g., most flows consist of only a handful number of packets). In light of recent findings, we make the key observation that because most flows are small, flow size is not sufficient to distinguish critical flows from non-critical flows and therefore existing flow schedulers do not achieve the desired prioritization. In this paper, we introduce ResQueue, which uses a combination of flow size and packet history to calculate the priority of each flow. Our evaluation shows that ResQueue improves tail flow completion times of short flows by up to 60% over the state-of-the-art flow scheduling mechanisms.

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.

Though Remote Direct Memory Access (RDMA) promises to reduce datacenter network latencies significantly compared to TCP (e.g., 10x), end-to-end congestion control in the presence of incasts is a challenge. Targeting the full generality of the congestion problem, previous schemes rely on slow, iterative convergence to the appropriate sending rates (e.g., TIMELY takes 50 RTTs). Several papers have shown that even in oversubscribed datacenter networks most congestion occurs at the receiver. Accordingly, we propose a divide-and-specialize approach, called Dart, which isolates the common case of receiver congestion and further subdivides the remaining in-network congestion into the simpler spatially-localized and the harder spatially-dispersed cases. For receiver congestion, we propose direct apportioning of sending rates (DASR) in which a receiver for n senders directs each sender to cut its rate by a factor of n, converging in only one RTT. For the spatially-localized case, Dart provides fast (under one RTT) response by adding novel switch hardware for in-order flow deflection (IOFD) because RDMA disallows packet reordering on which previous load balancing schemes rely. For the uncommon spatially-dispersed case, Dart falls back to DCQCN. Small-scale testbed measurements and at-scale simulations, respectively, show that Dart achieves 60% (2.5x) and 79% (4.8x) lower 99t'-percentile latency, and similar and 58% higher throughput than InfiniBand, and TIMELY and DCQCN.

Multi-tenant datacenters and cloud networks must provide both isolation and interactive service to tenant applications, many of which are sensitive to tail flow completion times. Network operators must also ensure high utilization of network capacity to reduce cost. Existing approaches that statically partition network capacity, in either time or space, provide good isolation but suffer from under-utilization. Existing schemes that dynamically allocate capacity to tenants incur either decreased fairness or high tail flow completion times. To overcome these limitations, we propose Ether. Ether is able to overcome these limitations because it can prioritize bursty flows during short congestion episodes while still ensuring fairness at long timescales. In this paper, we present a preliminary design of Ether and discuss its feasibility in today's programmable switches. Our evaluations show that, at high loads, Ether achieves 23% improvement in tail flow completion times (FCT) when compared with idealized fair queueing (FQ) while still providing similar fairness as FQ. In contrast, pFabric, which optimizes FCT, worsens fairness by a factor of 1.8 when compared with Ether.

Datacenter applications frequently cause incast congestion, which degrades short flows' flow completion times and long flows' throughput. Existing congestion control schemes (e.g., DCTCP) do not explicitly detect and isolate incast. Instead, they rely on existing Explicit Congestion Notification (ECN) to react to general congestion. They, therefore, lose performance due to slow, cautious, and inaccurate reaction to incast. We propose a novel algorithm that detects incasts and notifies senders using a new Explicit Incast Notification EIN). We show that our incast detection is fast and accurate. Next, we present our congestion control scheme, called Pulser , which isolates incasts using EIN. Unlike DCTCP, which gradually adjusts sending rate, Pulser drastically backs off during incast and rapidly restores sending rate once incast ends (i.e., like a pulse). Our real experiments and ns-3 simulations show that Pulser outperforms prior schemes, DCTCP and ICTCP, in both flow completion times and throughput.

A large variety of traffic - time-sensitive “foreground” traffic (e.g., web browsing) and time-insensitive “background” traffic (e.g., software updates) - compete for the scarce cellular bandwidth, especially on the downlink. While there is limited in-network support for traffic prioritization, existing endto-end, “low priority transport protocols” exhibit sub-optimal performance in cellular networks. We propose Sneaker, which yields to time-sensitive foreground traffic during periods of congestion and enables time-insensitive background traffic to efficiently utilize any spare capacity. Sneaker achieves the desired goal by randomly dropping packets coming into the base station, based on traffic type and network conditions. Our key contribution is the derivation of the optimal dropping rate and a practical dropping rate, which performs close to optimal. Further, Sneaker co-exists and performs well with existing cellular schedulers and transport protocols.

Datacenter applications demand both low latency and high throughput; while interactive applications (e.g., WebSearch) demand low tail latency for their short messages due to their partition-aggregate software architecture, many data-intensive applications (e.g., Map-Reduce) require high throughput for long flows as they move vast amounts of data across the network. Recent proposals improve latency of short flows and throughput of long flows by addressing the shortcomings of existing packet scheduling and congestion control algorithms, respectively. We make the key observation that long tails in theFlow Completion Times (FCT) of short flows result from packetsthat suffer congestion at more than one switch along their paths in the network. Our proposal,Slytherin, specifically targets packets that suffered from congestion at multiple points and prioritizes them in the network. Slytherin leverages ECN mechanism which iswidely used in existing datacenters to identify such tail packets and dynamically prioritizes them using existing priority queues. As compared to existing state-of-the-art packet scheduling proposals, Slytherin achieves 18.6% lower 99th percentile flow completion times for short flows without any loss of throughput. Further, Slytherin drastically reduces 99th percentile queue length in switches by a factor of about 2x on average.

Online Search (OLS) is a key component of many popular Internet services. Datacenters running OLS consume significant amounts of energy. However, reducing their energy is challenging due to their tight response time requirements. A key aspect of OLS is that each user query goes to all or many of the nodes in the cluster, so that the overall time budget is dictated by the tail of the replies' latency distribution; replies see latency variations both in the network and compute. Previous work proposes to achieve load-proportional energy by slowing down the computation at lower datacenter loads based directly on response times (i.e., at lower loads, the proposal exploits the average slack in the time budget provisioned for the peak load). In contrast, we propose TimeTrader to reduce energy by exploiting the latency slack in the sub-critical replies which arrive before the deadline (e.g., 80% of replies are 3-4x faster than the tail). This slack is present at all loads and subsumes the previous work's load-related slack. While the previous work shifts the leaves' response time distribution to consume the slack at lower loads, TimeTrader reshapes the distribution at all loads by slowing down individual sub-critical nodes without increasing missed deadlines. TimeTrader exploits slack in both the network and compute budgets. Further, TimeTrader leverages Earliest Deadline First scheduling to largely decouple critical requests from the queuing delays of sub-critical requests which can then be slowed down without hurting critical requests. A combination of real-system measurements and at-scale simulations shows that without adding to missed deadlines, TimeTrader saves 15% and 40% energy at 90% and 30% loading, respectively, in a datacenter with 512 nodes, whereas previous work saves 0% and 30%. Further, as a proof-of-concept, we build a small-scale real implementation to evaluate TimeTrader and show 10-30% energy savings.

Datacenter networks provide high path diversity for traffic between machines. Load balancing traffic across these paths is important for both, latency- and throughput-sensitive applications. The standard load balancing techniques used today obliviously hash a flow to a random path. When long flows collide on the same path, this might lead to long lasting congestion while other paths could be underutilized, degrading performance of other flows as well. Recent proposals to address this shortcoming incur significant implementation complexity at the host that would actually slow down short flows (MPTCP), depend on relatively slow centralized controllers for rerouting large congesting flows (Hedera), or require custom switch hardware, hindering near-term deployment (DeTail).

An important class of datacenter applications, called Online Data-Intensive (OLDI) applications, includes Web search, online retail, and advertisement. To achieve good user experience, OLDI applications operate under soft-real-time constraints (e.g., 300 ms latency) which imply deadlines for network communication within the applications. Further, OLDI applications typically employ tree-based algorithms which, in the common case, result in bursts of children-to-parent traffic with tight deadlines. Recent work on datacenter network protocols is either deadline-agnostic (DCTCP) or is deadline-aware (D3) but suffers under bursts due to race conditions. Further, D3 has the practical drawbacks of requiring changes to the switch hardware and not being able to coexist with legacy TCP. We propose Deadline-Aware Datacenter TCP (D2TCP), a novel transport protocol, which handles bursts, is deadline-aware, and is readily deployable. In designing D2TCP, we make two contributions: (1) D2TCP uses a distributed and reactive approach for bandwidth allocation which fundamentally enables D2TCP's properties. (2) D2TCP employs a novel congestion avoidance algorithm, which uses ECN feedback and deadlines to modulate the congestion window via a gamma-correction function. Using a small-scale implementation and at-scale simulations, we show that D2TCP reduces the fraction of missed deadlines compared to DCTCP and D3 by 75% and 50%, respectively.

Packet Classification is a key functionality provided by modern routers. Previous approaches --- TCAM and algorithmic --- perform well in either lookup efficiency (power and number of accesses) or update effort but not both. To perform well in both, we propose TreeCAM, which employs three novel ideas. (1) Dual versions of TreeCAM's decision tree to decouple lookups and updates: A coarse version with a few thousand rules per leaf achieves efficient lookups and a fine version with a few tens of rules per leaf reduces update effort. (2) Interleaved layout of the rules in the TCAM: Combined with the fine version's few rules per leaf, the layout enables us to bound our worst-case update effort. (3) Path-by-path updates to enable update work to be interspersed with packet lookups (i.e., non-atomic updates), eliminating packet buffering or packet drops during update. Using simulations of 100,000-rule classifiers, we show that TreeCAM performs well in both lookups and updates: (1) 6--8 TCAM subarray accesses per packet, matching modern TCAMs. (2) close to an idealized TCAM in worst-case update effort while requiring little buffering of packets.

Packet Classification is a key functionality provided by modern routers. Previous decision-tree algorithms, HiCuts and HyperCuts, cut the multi-dimensional rule space to separate a classifier's rules. Despite their optimizations, the algorithms incur considerable memory overhead due to two issues: (1) Many rules in a classifier overlap and the overlapping rules vary vastly in size, causing the algorithms' fine cuts for separating the small rules to replicate the large rules. (2) Because a classifier's rule-space density varies significantly, the algorithms' equi-sized cuts for separating the dense parts needlessly partition the sparse parts, resulting in many ineffectual nodes that hold only a few rules. We propose EffiCuts which employs four novel ideas: (1) Separable trees: To eliminate overlap among small and large rules, we separate all small and large rules. We define a subset of rules to be separable if all the rules are either small or large in each dimension. We build a distinct tree for each such subset where each dimension can be cut coarsely to separate the large rules, or finely to separate the small rules without incurring replication. (2) Selective tree merging: To reduce the multiple trees' extra accesses which degrade throughput, we selectively merge separable trees mixing rules that may be small or large in at most one dimension. (3) Equi-dense cuts: We employ unequal cuts which distribute a node's rules evenly among the children, avoiding ineffectual nodes at the cost of a small processing overhead in the tree traversal. (4) Node Co-location: To achieve fewer accesses per node than HiCuts and HyperCuts, we co-locate parts of a node and its children. Using ClassBench, we show that for similar throughput EffiCuts needs factors of 57 less memory than HyperCuts and of 4-8 less power than TCAM.