LLM serving is increasingly dominated by decode attention, which is a memory-bound operation due to massive KV cache loading from global memory. Meanwhile, real-world workloads exhibit substantial, hierarchical shared prefixes across requests (e.g., system prompts, tools/templates, RAG). Existing attention implementations fail to fully exploit prefix sharing: one-query-per-CTA execution repeatedly loads shared prefix KV cache, while one-size-fits-all tiling leaves on-chip resources idle and exacerbates bubbles for uneven KV lengths. These choices amplify memory bandwidth pressure and stall memory-bound decode attention.

Modern deep neural network (DNN) and large language model (LLM) applications integrate multiple models into inference pipelines with stringent latency requirements for customized tasks. To mitigate extensive request timeouts caused by accumulation, systems for inference pipelines commonly drop a subset of requests so the remaining ones can satisfy latency constraints. Since it is commonly believed that request dropping adversely affects goodput, existing systems only drop requests when they have to, which we call reactive dropping. However, this reactive policy can not maintain high goodput, as it neither makes timely dropping decisions nor identifies the proper set of requests to drop, leading to issues of dropping requests too late or dropping the wrong set of requests.

The hardware scheduler on NVIDIA GPUs is highly inefficient in utilizing micro-architectural hardware resources. It places blocks from the same kernel within the same GPU Streaming Multiprocessor (SM) core, resulting in a stacking colocating problem, where identical blocks are placed within the same SM core, saturating only a subset of intra-SM hardware resources while leaving others underutilized. The primary challenge in addressing this issue is that the NVIDIA hardware is closed-source, preventing us from directly modifying the hardware scheduler. To bridge the semantic gap between the resource demands of kernels and the scheduler, we introduce µ Share, which enables intra-SM scattered colocating of kernels through a non-intrusive half-plus blocksize shaping method. It shapes the blocksize of kernels to a halfplus blocksize (i.e., slightly more than half of the SM's thread capacity), scattering identical blocks of the same kernel across different SMs. It further adopts a time-shifted launching method to reduce intra-SM resource contention. Compared to state-of-the-art systems, µ Share does not require intrusive modifications to hardware or kernel code, yet it can still improve inference throughput by 26.90%-54.09% and increases low-level hardware utilization by 38.53%-61.15%.

Memory disaggregation architecture presents unique challenges in ensuring data consistency due to the limited computational power available at memory servers. One line of pessimistic solutions utilizes lock tables to deal with this challenge. Since the lock release signal cannot be immediately synchronized to the compute server, such solutions can only achieve suboptimal memory utilization. To address the aforementioned limitation, another line of solutions operates optimistically, polling the memory server until the operation completes successfully. However, these solutions trigger a massive number of unnecessary retries, resulting in performance collapse in high contention scenarios.high memory utilization while avoiding the need for retries. Our key idea is that compute servers proactively predict the appropriate retry interval and schedule accordingly. By analyzing the properties of requests on memory disaggregation, we find that the retry interval mainly consists of network fluctuations and host congestion delay. ECC design builds upon insights gained from this analysis. We have integrated ECC into Clover—a state-of-the-art memory disaggregation system and evaluated it through simulations and testbed experiments. Our testbed results show that ECC improves throughput by 50.8% over Clover.

The lack of actionable guidance is a fundamental limitation in Action Quality Assessment (AQA), as traditional methods provide overall scores without offering specific insights for improvement. Moreover, existing interpretable approaches often rely on expensive supervised spatial annotations or yield noisy, unsigned saliency maps. To address these challenges, we propose Learning Interpretability Based Supervoxels (LIBS), a novel framework for generating instructional feedback. Distinguishing itself from fully supervised methods, LIBS employs an unsupervised soft-clustering mechanism to segment videos into coherent supervoxels without requiring pixel-level mask annotations. This allows for scalable, fine-grained spatio-temporal analysis while preserving action continuity. Furthermore, we introduce a sensitivity propensity analysis to quantify the contribution of each supervoxel. Unlike traditional attribution methods, this mechanism explicitly decomposes the quality score into positive (strengths) and negative (flaws) components, enabling the system to decode abstract scores into concrete, actionable instructions. Experimental validation across multiple datasets demonstrates that LIBS achieves superior interpretability and efficiency compared to state-of-the-art baselines, marking an improvement from diagnostic to instructional AQA applications.

Distributed stream processing has recently gained much interest due to the need of extracting meaningful results from continuous data stream. To keep the extracted results fresh, the underlying network flows are often required to transmit packets continuously. Otherwise, these results will become stale, and their staleness is determined by the slowest flow. At this point,coflowscan be semantically comprised. Hence, efficient coflow transmission is critical for streaming applications. However, prior coflow-based solutions have significant limitations. They use a one-shot performance metric—CCT (coflow completion time), which cannot continuously reflect the staleness of the output results for a streaming application. To this end, we propose a new performance metric—coflow age(CA), for coflows generated by distributed streaming applications. The CA tracks thelongest time-since-last-serviceamong all flows in a coflow. In such a context, we consider a data center network with multiple coflows that continuously transmit packets between their source-destination pairs and address the problem of minimizing the average long-term CA while simultaneously satisfying the throughput constraints from the coflows. To solve this problem efficiently, we design a randomized algorithm and a drift-plus-age algorithm, and show that they can make the average long-term CA to achieve nearly two times and arbitrarily close to the optimal value, respectively. Through extensive simulations, we further demonstrate that both of the proposed algorithms can significantly reduce the CA of coflows, without violating the throughput requirement of any coflow, when compared to the state-of-the-art solution in both scenario with the packet arrival probability being known and unknown a prior.

In-network aggregation accelerates distributed training by offloading gradient aggregation to the programmable switches. However, in multi-tenant learning environments, contention for limited switch memory can cause memory overflows that significantly degrade aggregation throughput. To mitigate memory overflow, prior work has proposed selective in-network aggregation, which allocates switch memory to a subset of jobs based on memory availability. This approach classifies jobs into INA jobs (which perform in-network aggregation) and PS jobs (which perform in-server aggregation). Despite these efforts, network congestion occurs and slows INA jobs, resulting in inefficient memory utilization and reduced aggregation throughput. In this paper, we present FlexINA, which rethinks selective in-network aggregation to deliver high aggregation throughput. The first challenge is how to avoid excessive memory under-utilization by INA jobs during network congestion. FlexINA introduces INA-aware congestion control, prioritizing reducing the sending window of PS jobs during network congestion. The second challenge is how to allow PS jobs to utilize under-utilized aggregators without affecting the aggregation of INA jobs. FlexINA implements an adaptive head-tail aggregation, optimizing memory usage by combining static head mapping for INA jobs (to use allocated head memory) and dynamic tail mapping for PS jobs (to use under-utilized tail memory). We implement a FlexINA prototype and evaluate it on both a small-scale testbed and in large-scale simulation experiments. Our evaluation shows that FlexINA improves aggregation throughput by up to$1.9\times $and$1.4\times $compared to selective in-network aggregation NetPack (ATP) and NetPack (A2TP), respectively.

Video large language models (VideoLLMs) have significantly advanced video question answering (VideoQA) applications, which demand both low latency and high accuracy. To meet the requirements, VideoLLMs are typically deployed on GPUs for parallel acceleration. However, the massive computational load from long video contexts often makes such acceleration insufficient. Existing techniques like token pruning and speculative decoding attempt to address this challenge by altering the computational load, but often fail to balance both speed and accuracy. Sparse self-speculation mitigates these limitations via selecting a subset of tokens on a specific token budget to draft the output and then verify it using all tokens. However, existing sparse self-speculation is designed for text-based scenarios and cannot be directly applied to VideoQA tasks, as it fails to account for discrepancies in critical multimodal tokens and the dynamic nature of optimal token budget in VideoQA, leading to suboptimal scale and inappropriate composition of parallel computational load. We argue that achieving both high accuracy and low latency in VideoQA tasks requires managing the computational load with awareness of these discrepancies and dynamics. To achieve this, we introduce ViDA, a selective sparse self-speculation inference system. It progressively searches token budgets by iteratively refining lower and upper bounds of search space derived from long contexts, aiming to find and allocate varying optimal budgets in real-time adaptively. Additionally, it leverages insights from discrepancies in critical multimodal tokens to perform a discrepancy-aware token selection approach for identifying critical tokens. Evaluations across various VideoQA workloads show that compared to state-of-the-art methods, ViDA preserves exact model outputs while reducing average time-per-outputtoken (TPOT) by 15% to 46% and average end-to-end latency by up to 28%, while decreasing the divergence from optimal token budget distribution by up to 93

Many existing transport designs aim to deliver ultra-low latency and high bandwidth for applications in high-speed datacenter networks. However, almost all of them intertwine the control of small and large flows using the same control entity (e.g., sender or receiver) and congestion feedback signal (e.g., ECN or credit), thus bringing significant performance impairments. By contrast, we seek to decouple the rate control of small flows from that of large ones.

Mixture-of-Experts (MoE) architectures have emerged as a scalable and efficient alternative to dense Transformer models by activating only a subset of experts per layer. However, deploying MoE models in multi-GPU environments faces severe challenges due to expert load imbalance and the resulting inefficient GPU utilization. Existing static replication strategies fail to adapt to dynamic token distributions, while dynamic rebalancing methods incur excessive communication and memory-access overheads, often outweighing the benefits of load balancing. This paper presents MoEoM, an inference system that enhances the efficiency of MoE models by innovatively taking memory-access costs into consideration. MoEoM integrates two complementary techniques: (i) a load-aware offline expert deployer, which symmetrically groups experts across GPUs and selectively replicates high-load experts, and (ii) an I/O-aware online token reallocator, which dynamically redistributes tokens among original and backup experts to minimize the maximum latency across GPUs. Experimental evaluations on state-of-theart MoE models demonstrate that MoEoM reduces end-toend inference latency by up to 16.6 %, improves throughput by 11–20 % in the prefill stage and 11–23 % in the decode stage, and decreases cross-GPU imbalance by 65–80 % (about 75 % on average), compared to prior MoE inference baselines. These results highlight the importance of incorporating both computation and memory-access overhead into expert placement and token scheduling for efficient large-scale MoE deployment.

Programmable packet scheduling enables users to customize scheduling algorithms flexibly without designing new ASICs. Existing schemes prefre to approximate optimal Push-In First-Out (PIFO) using First-In First-Out (FIFO) queues in commodity programmable switches. Despite its availability, these schemes suffer performance degradation due to the unawareness of available switch buffer. To be specific, when the port buffer is drained, existing schemes discard all incoming packets, even though these packets have higher priorities than the enqueued packets. In this paper, we reveal that the problem's key culprit is the lack of coordination between buffer management and packet scheduling in the switch. To fill this gap, we present Lark, a buffer-aware building block for programmable scheduling schemes designed to solve the above problem. Its key idea is to proactively drop the low-priority packets when the allocated buffer is to be drained, thereby admitting the later-arriving high-priority packets. Lark contains two modules, a lightweight gradient-based online prediction module and a simple priority-based decision module. Lark relies the former module to identify whether the allocated buffer is to be drained and uses the later to determine whether to drop the incoming packet. We have integrated Lark into two representative schemes, SP-PIFO and AIFO. Our large-scale evaluations over three realistic workloads show that Lark can significantly optimize their key metrics without sacrificing throughnut.

Advances in deep neural networks (DNNs) have significantly contributed to the development of real-time video processing applications. Efficient scheduling of DNN workloads in cloud-hosted inference systems is crucial to minimizing serving costs while meeting application latency constraints. However, existing systems suffer from excessive module latency during request dispatching, low execution throughput during module scheduling, and wasted latency budget during latency splitting for multi-DNN applications, which undermines their capability to minimize the serving cost. In this paper, we design a DNN inference system called Harpagon, which minimizes the serving cost under latency constraints with a three-level design. It first maximizes the batch collection rate with a batch-aware request dispatch policy to minimize the module latency. It then maximizes the module throughput with multi-tuple configurations and proper amount of dummy requests. It also carefully splits the end-to-end latency into per-module latency budget to minimize the total serving cost for multi-DNN applications. Evaluation shows that Harpagon outperforms the state of the art by 1.49 to 2.37 times in serving cost while satisfying the latency objectives. Additionally, compared to the optimal solution using brute force search, Harpagon derives the lower bound of serving cost for 91.5% workloads with millisecond level runtime.

Large language models (LLMs) have demonstrated remarkable performance across a wide range of tasks, largely due to their substantial model size. However, this also results in significant GPU memory demands during inference. To address these challenges on hardware with limited GPU memory, existing approaches employ offloading techniques that offload unused tensors to CPU memory, thereby reducing GPU memory usage. Since offloading involves data transfer between GPU and CPU, it introduces transfer overhead. To mitigate this, prior works typically overlap data transfer with GPU computation using a fixed pipelining strategy applied uniformly across all inference iterations, referred to asstaticoffloading. However, static offloading policies fail to maximize inference throughput because they cannot adapt to the dynamically changing transfer overhead during the inference process, leading to increasing GPU idleness and reduced inference throughput.We propose that offloading policies should beadaptiveto the varying transfer overhead across inference iterations to maximize inference throughput. To this end, we design and implement an adaptive offloading-based inference system called TightLLM with two key innovations. First, its key-value (KV) distributor employs atrade-compute-for-transferstrategy to address growing transfer overhead by dynamically recomputing portions of the KV cache, effectively overlapping data transfer with computation and minimizing GPU idleness. Second, TightLLM’s weight loader slices model weights and distributes the loading processacross multiple batches, amortizing the excessive weight loading overhead and significantly improving throughput. Evaluation across various combinations of GPU hardware and LLM models shows that TightLLM achieves 1.3 to 23 times higher throughput during the decoding phase and 1.2 to 22 times higher throughput in the prefill phase compared to state-of-the-art offloading systems. Due to the higher throughput in prefill and decoding phases, TightLLM can reduce the completion time for large-scale tasks, which involve processing and generating a substantial number of tokens, by 59.6% to 94.9%.

In-Network Aggregation (INA) solutions represent the forefront in advancing All-Reduce, utilizing limited switch memory for efficient gradient aggregation. However, existing INA solutions primarily focus on enhancing aggregation efficiency, often overlooking the efficient utilization of memory. Isolation solutions typically pre-allocate resources for each job, leading to memory wastage due to the uncontrolled use of resources. In contrast, the sharing solutions encounter significant memory contention, resulting in performance degradation within a multi-tenant environment. In this paper, we propose DynaINA, a flexible job scheduler to support multi-tenant training. The core idea of DynaINA is to provide spatial and temporal compatibility between jobs. For spatial compatibility, DynaINA utilizes multiple dynamic memory pools to provide job isolation. For temporal compatibility, DynaINA employs contention-aware job scheduling to facilitate memory sharing. Furthermore, DynaINA prioritizes communication-intensive jobs, leveraging the benefits of INA to enhance overall performance in training clusters. Extensive experiments with popular vision and language models demonstrate that DynaINA reduces training time by up to 65.16% and improves switch memory utilization by up to 85.02% compared to state-of-the-art solutions in a 100Gbps network.

The rise of Machine Learning as a Service (MLaaS) has driven the demand for complex and customized real-time inference tasks, often requiring cascading multiple deep neural network (DNN) models into inference pipelines. However, these pipelines pose significant challenges due to scheduling complexity, particularly in maintaining strict latency service level objectives (SLOs). Existing systems serve pipelines with model-independent scheduling policies, which ignore the unique workload characteristics introduced by model cascading in the inference pipeline, leading to SLO violations and resource inefficiencies. In this paper, we propose that the serving system should exploit the model-cascading nature and inter-model workload dependency of the inference pipeline to ensure strict latency SLO cost-effectively. Based on this, we design and implementSLOpt, a serving system optimized for real-time inference pipelines with a three-stage co-design of workload estimation, resource provisioning, and request execution.SLOptproposes cascade workload estimation and ahead-of-time tuning, which together address the challenge of cascade blocking and head-of-line blocking in workload estimation and resource provisioning.SLOptfurther implements an adaptive batch drop policy to mitigate latency amplification issues within the pipeline. These innovations enableSLOptto reduce the 99th percentile latency (P99 latency) by 1.4 to 2.5 times compared to the state of the arts while lowering serving costs by up to 29%. Moreover, to achieve comparable P99 latency,SLOptrequires up to 70% less cost than existing systems. Extensive evaluations on a 64-GPU cluster demonstrateSLOpt’s effectiveness in meeting strict P99 latency SLOs under diverse real-world workloads.

RDMA has been widely deployed to improve the performance of applications with frequently fine-grained remote access. However, restricted on-chip resources result in cache misses under high concurrency that significantly degrade network performance. QPC-aware solutions only focus on the number of concurrent QPs, ignoring the impact of WQE within QPs. SMART limits the number of WQEs in each QP with a credit-based scheme. Nevertheless, we find that equal treatment increases the tail latency of messages ranging from 32 bytes to 1024 bytes by 2× when mixing messages of different sizes. In this paper, we introduce WQEFC, a scalable RDMA message scheduler that provides lower latency and higher throughput for applications with heavily concurrent messages. Our key insight is that there is a significant difference in the sensitivity to cache miss between messages of different sizes. For messages smaller than 32 bytes, which are sensitive to cache misses, we combine the credit limiter and sub-message poller, limiting the number of concurrent wqes to avoid cache miss while ensuring optimal message completion latency. For other messages, which are insensitive to cache miss, we assign them a higher priority and use the sub-message poller to ensure message concurrency while reducing cache miss. We implement WQEFC as a middleware between the driver layer and the application layer for flexible deployment. WQEFC outperforms the state-of-the-art solution Smart by increasing system throughput by 61.3%, and reducing the tail latency of messages smaller than 32 bytes and larger than 32 bytes by 41.6% and 72.6%, respectively.

Memory disaggregation, a promising technique allowing applications to use remote memory, is increasingly appealing in datacenters due to its high resource utilization. Operationally, the application’s host server constantly evicts unused data to remote to make room for memory allocation of new pages. Inefficient evictions allow memory usage to hit its limit, resulting in application blocking, which brings severe throughput degradation. However, most existing works neglect the importance of eviction. They offload the eviction to a background thread and set a fixed trigger timing, rendering a belated eviction. Worse still, they overlook the impact of network congestion on eviction efficiency, making their strategy flawed in large-scale scenarios. In this paper, we present Glitter, an adaptive, multi-level awareness eviction solution that accelerates applications by minimizing the overhead of application blocking from host and network aspects. For host, Glitter presents an adaptive eviction threshold adjustment to optimize the eviction timing, reducing the occurrence of application blocking. For network, Glitter adopts an eviction flow scheduling to address the hazards posed by flow contention at switches, decreasing the duration of each application blocking. Through comprehensive experiments, Glitter gives an average 1.4 throughput boost to Fastswap, a state-of-the-art disaggregated×memory system.

Large-scale datacenter networks are increasingly using in-network aggregation (INA) and remote direct memory access (RDMA) techniques to accelerate deep neural network (DNN) training. However, existing research trends suggest that these two techniques are on an inevitable collision course. To fill this gap, we present FreeINA, a host-driven in-network aggregation aimed at providing RDMA reliable connection (RC) for multi-tenant learning settings. FreeINA relies on dual transmission paths to support RC compatibility, with one path for INA and another one for aggregation on end-host parameter server. With dynamic control of these two paths, FreeINA can leave the traditional in-server aggregation unaffected while ensuring INA’s reliability without modifying RDMA network interfaces (RNICs). To support multi-tenant learning, FreeINA employs all-reduce-level memory allocation, which can capture the well-known "on and off" DNN training pattern and thus improve switch memory efficiency. We have implemented a FreeINA prototype using P4-programmable switch and commercial RNICs, and evaluated it extensively using 100Gbps testbed. The results show that compared to the state-of-the-art solution—ATP, FreeINA improves single-job training speedup ratio by 1.20×, while improving the aggregation throughput by 2.65× in multi-job scenario.

With the rapid growth of datacenter network link speed, multi-round matching based proactive solutions (e.g., dcPIM) has become increasingly attractive. Such solutions enable receivers to obtain as much global information as possible through multi-round matching, thereby facilitating them to make near-optimal decisions on bandwidth allocation. However, the matching phase before transmitting data introduces significant latency overhead. In this paper, we present Mild, a zero-wait solution that runs a second sender-driven control loop in parallel, leveraging in-network telemetry (INT) to detect and fill the spare bandwidth during the matching phase. Furthermore, we introduce a selective dropping mechanism to ensure that the packets from the second loop do not impact the data transmission of the primary loop. Additionally, we use the well-protected primary loop to perform loss recovery for the dropped packets efficiently. We integrate Mild into a representative proposal dcPIM and evaluate its performance through 100Gbps large-scale simulations. Compared to the state-of-the-art solution, Mild reduces the tail flow completion time (FCT) of short flows by up to 55% while achieving up to 57%/45% lower average FCT of medium/large flows.

This paper introduces PPT, a pragmatic transport that achieves comparable performance to proactive transports while maintaining good deployability as reactive transports. Our key idea is to run a low-priority control loop to leverage the available bandwidth left by the reactive transports. The main challenge is to send just enough packets to improve performance without harming the primary control loop. We combine two unconventional techniques: an intermittent loop initialization and an exponential window decrease, enabling us to dynamically identify and fill the spare bandwidth. We further complement PPT's design with a buffer-aware flow scheduling scheme to optimize the average FCT of small flows without prior knowledge of flow size information. We have implemented a PPT prototype in the Linux kernel with ~400 lines of code and demonstrated that compared to Homa, it delivers up to 46.3% lower overall average FCT and even 25%/55.5% lower average/tail FCT of small flows in an Memcached workload.

Many existing datacenter transports perform one-shot packet priority tagging at end-hosts and leave them fixed during the packet's transmission. In this paper, we experimentally show that: (1) such fixed packet priority is not sufficient for FCT (flow completion time) minimization, and (2) adjusting packet transmission priority in the network requires effective coordination among switches. Building on these insights, we present Anole, a new datacenter transport that advocates packet re-prioritization in near-bottleneck switches to minimize FCT. To this end, Anole integrates three simple-yet-effective techniques. First, it employs an in-network telemetry (INT) based approach to dynamically detect the bottleneck for each flow. Second, it adopts an on-off rate control mechanism for each sender to pause heavily congested flows but send lightly- and non-congested ones. Last, it leverages an altruistic scheduling policy at each switch to let the flows whose next hops are bottleneck switches give way to others. We implement an Anole prototype based on DPDK and show, through both testbed experiments and simulations, that Anole delivers significant performance advantages. For example, compared to EPN, Homa, and Aeolus, it shortens the average FCT of all (small) flows by up to 61.6% (89.1%).

The coexistence of RDMA and TCP is prevalent in the datacenter. Despite the sound isolation at the end hosts, they share the same switches in the network. Their different networking behaviors (E.g., in hardware demand and transport protocols) lead to huge differentiated buffer demand for switches. However, existing buffer management schemes ignore these dissimilarities and simply treat such RDMA/TCP mix-flows as the typical multi-class traffic, resulting in inferior isolation and degrading networking performances. This paper presents BRT, a first systematic solution for the buffer management of RDMA/TCP mix-flows in the DCN. BRT’s key insight is to allocate buffer with the awareness of traffic’s networking characteristics while minimally impacting the other’s performance. Guided by this insight, it first employs a traffic characteristics-based window to detect whether queues are in the state of persistent long queues. Then, it adjusts the total allocated buffer for each traffic type based on the number of persistent long queues and the normalized dequeue rates to reduce the buffer occupancy of meaningless queuing. Last, it calculates the buffer threshold for RDMA/TCP queues separately and uses a simple yet effective approach to prioritize the absorption of small flows. Our large-scale packet-level evaluations show that BRT can effectively optimize the networking performances for RDMA/TCP mix-flows. For example, compared to current practice, BRT achieves up to 53.5%, 46.7%, and 48.5% lower average FCT for incast flows, RDMA small flows, and TCP small flows, respectively, without sacrificing the overall throughput.

Incast happens in data center networks (DCNs) when many senders simultaneously send flows to one receiver. Incast occurs frequently and compromises flow performance severely. However, widely deployed end-to-end congestion control (CC) protocols are inefficient at handling incast, as they rely on delayed congestion signals and can not isolate incast flows. Recently, researchers have favored per-hop flow control protocols since they could achieve fast reaction and incast isolation. Nevertheless, these impressive advantages are impractical because of hardware resource limitations.In this paper, we present a new per-hop flow control protocol dBFC (Destination-based Backpressure Flow Control), which achieves these advantages within limited hardware resources. Our key insight is that the number of destinations reached by queued packets in a port is minuscule. dBFC is compatible with existing CC protocols. We use large-scale NS3 simulations to evaluate dBFC. In our evaluation, compared with deployed CC protocols and the state-of-the-art per-hop flow control protocol, dBFC reduces the maximum buffer occupancy by 5 − 23× and thus provides up to 21× lower flow completion time of small flows in limited hardware resources.

In-memory key-value stores are widely used in modern web services to support large-scale user requests by caching popular data. Their performance is critical, and BMC, the state-of-the-art work, builds an in-kernel cache and processes requests before the stack using eBPF to reduce the overhead of the kernel network stack. However, BMC fails to support stateful protocol TCP because pre-stack processing creates TCP state bias between the client and server.TCP is widely used by in-memory key-value stores, is even the only choice for some applications (e.g., Redis), and also suffers from performance issues. In this work, we present MiddleCache, a TCP-enabled in-memory key-value store acceleration design. Our key observation is that the TCP state bias of the client and server can be inferred and eliminated with packet length. The design of MiddleCache has two key parts: (i) A compact TCP state maintenance mechanism that accumulates packet lengths and applies corrections to the packet header, which realize TCP support within the constrains of eBPF. (ii) Lock-free accumulation counters that support high-performance concurrent access by utilizing Receive Side Scaling (RSS). Our experiments show that, compared with Memcached, MiddleCache reduces 56% processing latency on cache hit and achieves a 3.8× throughput improvement on Facebook-like small-size requests workload.

Container overlay network, though being widely adopted to enable communication between containers on different hosts, is a key downside for latency-sensitive applications. The state-of-the-art solution seeks to shorten the data path in packet processing by replacing overlay connection file descriptors with host namespace ones. While promising, it must block each overlay connection until the relevant host connection is set up, thus heavily influencing the request latency. In this paper, we present ShuntFlow, a systematic data delivery framework that seamlessly integrates the host and overlay networks to reduce the application's request-response latency. ShuntFlow first lets all connections flow in the overlay network directly. Then, it adopts a simple-yet-effective syscall-threshold-based mechanism to pick appropriate connections and switches their data delivery to the host network in a blocking-free way using a multi-threading technique. As such, unnecessary connection switches are prevented; yet, the pre-setup phase dilemma is eliminated. We have implemented a ShuntFlow prototype based on Linux and Docker and evaluated it extensively on a 40 Gbps testbed. The results show that ShuntFlow achieves 13%/72% and 19%/69% reductions, in average/tail request-response latency of a web server and an in-memory key-value store, respectively, while incurring less CPU overhead, compared to Slim.

Proactive transport has been attractive in modern high-speed and shallow buffered datacenter networks. At its heart, the link capacity is proactively allocated as credit, and then following scheduled packets are triggered by active senders according to credits, providing (near) zero loss rate and extremely low latency. Despite being promising, when waiting for credits in the first RTT, called the “pre-credit phase a substantial amount of spare bandwidth is being underutilized. To bridge this gap, current practices send a Bandwidth-Delay-Product (BDP) worth of unscheduled packets with line rate in the pre-credit phase, however, degrading throughput or tail latency. One key insight is that they consider the spare bandwidth in the pre-credit phase as a fixed value but actually changes across time and space. In this paper, we present Schef, a novel switch-based bandwidth calculation mechanism to address the pre-credit phase challenge without introducing network congestion or throughput degradation. The main idea is to calculate the spare bandwidth and apply efficient control of unscheduled packets at switches. Schef is compatible with existing proactive transports. We integrate it into a representative proposal NDP and evaluate its performance through large-scale simulations. Compared with the state-of-art, Schef reduces the average and 99th flow completion time (FCT) of short flows by up to 23% and 31%, and achieves 13% higher goodput simultaneously.

Short-lived TCP connections are important for modern Internet applications and call for efficient network stack support. Traditional Linux TCP stack is inefficient because of the inherent kernel overheads like context switching and memory copy. A promising alternative, called user-level TCP stack, is thus becoming attractive in this context. However, existing user-level stacks mainly focus on scalability issues when handling shortlived connections and fall short in optimizing request-response latency. To fill this gap, this paper presents Pallas, a built-in packet scheduler in the user-space mTCP stack, to prioritize the transmissions of short connections over long connections to reduce the request-response latency. Pallas schedules at packetlevel first to complete 1-packet short connections as quickly as possible and then smoothly switches to connection-level to defer the transmissions of long connections. We have implemented a Pallas prototype and evaluated it on a 4-core machine. The results show that Pallas-enhanced mTCP delivers significant performance. For example, it speeds up the overall request response time of mTCP by 1.49 times.

Load balancing is essential for datacenter networks. However, prior solutions have significant limitations: they either are oblivious to congestion or involve a daunting and time-consuming parameter-tunning task over their heuristics for achieving good performance. Thus, we ask: is it possible to learn to balance datacenter traffic? While deep reinforcement learning (DRL) sounds like a good answer, we observe that it is too heavyweight due to the long decision-making latency. Therefore, we introduce BULB, a lightweight and automated datacenter load balancer. BULB learns link weights to guide the end-hosts to spread traffic, so as to free the central agent from quick flow-level decision-making. BULB offline trains a DRL agent for optimizing link weights but employs an imitation learning based approach to faithfully translate this agent’s DNN to a decision tree for online deployment. We implement a BULB prototype with a popular machine learning framework and evaluate it extensively in ns-3. The results show that BULB achieves up to 36.6%/56.4%, 19.9%/42.5%, 35.9%/54.8%, and 45.1%/67.7% better average/tail flow completion time than ECMP, CONGA, LetFlow, and Hermes, respectively. Moreover, BULB reduces the decision latency by 175 times while incurring only 2% performance loss after converting the DNN into a decision tree.

Distributed machine learning (DML) is an increasingly important workload. In a DML job, each communication phase can comprise acoflow, and there are dependencies among its coflows. Thus, efficient coflow scheduling becomes critical for DML jobs. However, the majority of existing solutions focus on scheduling single-stage coflows with no dependencies. While there are a few studies schedule dependent coflows of multi-stage jobs, they suffer from either practical or theoretical issues. Motivated by this situation, we study how to schedule dependent coflows of multiple DML jobs to minimize the total JCT in a shared cluster. We present a formal mathematical formulation for this problem and prove its NP-hardness. To solve this problem without job size information, we present an online coflow-aware optimization framework calledParrot. The core idea inParrotis to infer the job with the shortest remaining processing time (SRPT) each time and dynamically control the inferred job's bandwidth based on how confident it is an SRPT job while being mindful of not starving any other job. Specifically, in the design ofParrot, we present a least per-coflow attained service (LPCAS) policy to infer the SRPT job. We further propose a dynamic job weight assignment mechanism and a linear program (LP) based weighted bandwidth scaling strategy for sharing bandwidth among DML jobs. We have proved thatParrotalgorithm has a non-trivial competitive ratio. The results from large-scale trace-driven simulations further demonstrate that ourParrotcan reduce the total JCT by up to 58.4 percent, compared to the state-of-the-art Aalo solution.

In the era of global-scale services, analytical queries are performed on datasets that span multiple data centers (DCs). Such geo-distributed queries generate a large amount of inter-DC data transfers at run time. Due to the expensive inter-DC bandwidth, various methods have been proposed to reduce the traffic cost in geo-distributed data analytics. However, current methods do not attempt to address the throughput issue in geo-distributed analytics. In this article, we target at characterizing and optimizing a cost-throughput tradeoff problem in geo-distributed data analytics. Our objectives are two-fold: (1) we minimize the inter-DC traffic cost when serving geo-distributed analytics with uncertain query demand, and (2) we maximize the system throughput, in terms of the number of query requests that can be successfully served with guaranteed queuing delay. Specifically, we formulate a stochastic optimization problem that seamlessly combines these two objectives. To solve this problem, we take advantage of Lyapunov optimization techniques to design and analyze a two-timescale online control framework. Without prior knowledge of future query requests, this framework makes online decisions on input data placement and admission control of query requests. Rigorous theoretical analyses show that our framework can achieve a near-optimal solution and maintain system stability and robustness as well. Extensive trace-driven simulation results further demonstrate that our framework is capable of reducing inter-DC traffic cost, improving system throughput, and guaranteeing a maximum delay for each query request.

Over the last decade, traffic engineering (TE) has always been a research hotspot in data center networks. For routing flows efficiently and practically, existing TE schemes explore experience-driven heuristics or machine learning (ML) techniques to predict/identify network flows’ size information. However, these TE schemes have significant limitations: they either identify the flow size information too late or are unaware of the ML models’ prediction errors. In this paper, we present DarkTE, a novel TE solution that can learn to predict flow size information timely for achieving better routing performance while being robust to the prediction errors. At its heart, DarkTE employs an ensemble learning technique (i.e., random forest) to classify flows into mice and elephant flows with high accuracy. It then leverages a confidence-based rate allocation and path selection scheme to mitigate the occasional classification errors. Large-scale simulations demonstrate that DarkTE classifies flows within hundreds of microseconds, and the classification accuracy is at least 86.4% over three different realistic workloads. Further, DarkTE completes flows 2.94 times faster on average and makes more links to experience over 90% bandwidth utilization than the Hedera solution.

Nowadays, more and more sensors, devices and applications are connected in Industrial Internet of Things (IIoT), producing massive real-time flows which need to be scheduled for Quality-of-Service provision. To realize application-aware and adaptive flow scheduling, the problem of traffic classification must be addressed at first. When edge computing paradigm is introduced into IIoT, the traffic classification service can be deployed on edge node in the near-end. Recently, deep-learning-based IIoT traffic classification methods show better performance, but the computational cost of deep learning model is too high to be deployed on edge node. Moreover, increasingly unknown flows generated by new devices and emerging industrial APPs lead to frequent training of traffic classifiers. It is difficult to migrate the complex process of classifier training from cloud server to edge nodes with limited resources. To address these issues, we take the benefits of hash mechanism and consensus mechanism in blockchain to design a lightweight IIoT traffic classification service, which is more applicable for edge computing paradigm. First, inspired by the hash mechanism in blockchain and the learning to hash for big data, we propose a new learning-to-hash method named extension hashing. By this method, we can build the set of binary coding tress (BCT set), then generating hash table for more efficient k-nearest neighbor-based classification without complex classifier training. Then, we design a new voting-based consensus algorithm to synchronize the BCT sets and the hash tables across edge nodes, thereby providing the traffic classification service. Finally, we conduct data-driven simulations to evaluate the proposed service. By comparing traffic classification results on public data set, we can see that the proposed service achieves the highest classification accuracy with the minimal time cost and memory usage.

Data-parallel applications generate a mix of coflows with and without deadlines. Deadline coflows are mission-critical and must be completed within deadlines, while the non-deadline coflows desire to be completed as soon as possible. Scheduling such mix-coflows is an important problem in modern datacenters. However, existing solutions only focus on one of the two types of coflows: they either solely concentrate on meeting the deadlines of deadline-aware coflows or reducing the coflow completion times (CCTs) of non-deadline coflows. In this article, we study the problem of optimizing deadline and non-deadline coflows simultaneously. To this end, we present a new optimization framework,mixCoflow, to schedule deadline coflows to minimize and balance their bandwidth footprint, such that non-deadline coflows can be scheduled as early as possible. Specifically, we develop the mathematical model and formulate the scheduling problem for deadline coflows as a lexicographical min-max integer linear programming (ILP) problem. Through rigorous theoretical analysis, this ILP problem has been proved to be equivalent to a linear programming (LP) problem that can be solved with standard LP solvers. By solving this LP,mixCoflowis able to balance the bandwidth footprint of deadline coflows while guaranteeing their deadlines. As a result, non-deadline coflows can be scheduled as soon as possible whenever they arrive. To demonstrate the effectiveness of our work, we have conducted extensive simulations based on a widely used Facebook data trace. The simulation results verify thatmixCoflowcan achieve significant improvement on the average CCT of non-deadline coflows, at no expense of increasing the deadline miss rates of deadline coflows, when compared to the state-of-art solutions.

Low latency stream processing on large clusters consisting of hundreds to thousands of servers is an increasingly important challenge. A crucial barrier to tackling this challenge is stragglers, i.e., tasks that are significantly straggling behind others in processing the stream data. However, prior straggler mitigation solutions have significant limitations. They balance streaming workloads among tasks but may incur imbalanced backlogs when the workloads exhibit variance, causing stragglers as well. Fortunately, we observe that carefully scheduling the outgoing tuples of different tasks can yield benefits for balancing backlogs, and thus avoids stragglers. To this end, we present Hone, a tuple scheduler that aims to minimize the maximum queue backlog of all tasks over time. Hone leverages an online Largest-Backlog-First (LBF) algorithm with a provable good competitive ratio to perform efficient tuple scheduling. We have implemented Hone based on Apache Storm and evaluated it extensively via both simulations and testbed experiments. Our results show that under the same workload balancing strategy-shuffle grouping, Hone outperforms the original Storm significantly, with the end-to-end tuple processing latency reduced by 78.7 percent on average.

Geographically distributed cloud is a promising technique to achieve high performance for service providers. For inter-datacenter transfers, deadline guarantee and fairness are the two most important requirements. On the one hand, to ensure more transfers finish before their deadlines, preemptive scheduling policies are widely used, leading to the transfer starvation problem and is hence unfair. On the other hand, to ensure fairness, inter-datacenter bandwidth is fairly shared among transfers with per-flow bandwidth allocation, which leads to deadline missing problem. A mechanism that achieves these two seemingly conflicting objectives simultaneously is still missing. In this paper, we propose TINA to schedule network transfers fairly while providing deadline guarantees. TINA allows each transfer to compete freely with each other for bandwidth. More specifically, each transfer is assigned a probability to indicate whether to transmit or not. We formulate the competition among the transfers as an El Farol game while keeping the traffic load under a threshold to avoid congestion. We then prove that the Nash Equilibrium is the optimal strategy and propose a light-weight algorithm to derive it. Finally, both simulations and testbed experiments results show that TINA achieves superior performance than state-of-art methods in terms of fairness and deadline guarantee rate.

Distributed streaming applications require the underlying network flows to transmit packets continuously to keep their output results fresh. These results will become stale if no updates come, and their staleness is determined by the slowest flow. At this point, coflows can be semantically comprised. Hence, efficient coflow transmission is critical for streaming applications. However, prior coflow-based solutions have significant limitations. They use a one-shot performance metric-CCT (coflow completion time), which cannot continuously reflect the staleness of the output results for a streaming application.To this end, we propose a new performance metric-coflow age (CA), for coflows generated by distributed streaming applications. The CA tracks the longest time-since-last-service among all flows in a coflow. In such a context, we consider a data center network with multiple coflows that continuously transmit packets between their source-destination pairs and address the problem of minimizing the average long-term CA while simultaneously satisfying the throughput constraints from the coflows. To solve this problem efficiently, we design a randomized algorithm and a drift-plus-age algorithm, and show that they can make the average long-term CA to achieve nearly two times and arbitrarily close to the optimal value, respectively. Through extensive simulations, we further demonstrate that both of the proposed algorithms can significantly reduce the CA of coflows, without violating the throughput requirement of any coflow, when compared to the state-of-the-art solution.

Over the last decade, we have witnessed growing data volumes generated and stored across geographically distributed datacenters. Processing such geo-distributed datasets may suffer from significant slowdown as the underlying network flows have to go through the inter-datacenter networks with relatively low and highly heterogeneous available link bandwidth. Thus, optimizing the transmissions of inter-datacenter flows, especially coflows that capture application-level semantics, is important for improving the communication performance of such geo-distributed applications. However, prior solutions on coflow scheduling have significant limitations: they schedule coflows with already-fixed endpoints of flows, making them insufficient to optimize the coflow completion time (CCT). In this article, we focus on the problem of jointly considering endpoint placement and coflow scheduling to minimize the average CCT of coflows across geo-distributed datacenters. To solve this problem without any prior knowledge of coflow arrivals, we present a coflow-aware optimization framework called SmartCoflow. In SmartCoflow, we first apply an approximate algorithm to obtain the endpoint placement and scheduling decisions for a single coflow. Based on the single-coflow solution, we then develop an efficient online algorithm to handle the dynamically arrived coflows. Through rigorous theoretical analysis, we prove that SmartCoflow has a non-trivial competitive ratio. We also extend SmartCoflow to incorporate various design choices or requirements of applications and operators, such as enforcing an inter-datacenter bandwidth usage budget and considering coflow deadline. Through experimental results from testbed implementation and trace-driven simulations, we demonstrate that SmartCoflow can reduce the average CCT, lower bandwidth usage, and improve coflow deadline meet rate, when compared to the state-of-the-art scheduling-only method.

The emerging deployment of large-scale cloud applications incurs significant inter-datacenter traffic, which makes the scarce wide-area bandwidth across data centers become the performance bottleneck. To achieve the desirable network performance, bandwidth guarantee should be provided for the resulting inter-datacenter traffic. However, the existing bandwidth allocation methods mainly focus on intra-datacenter traffic, and cannot achieve the cost-minimizing bandwidth guarantee for inter-datacenter traffic. In this paper, we focus on the bandwidth guarantee problem for inter-datacenter traffic and present a novel bandwidth allocation model. Our model can ensure the bandwidth guarantee, minimize the resulting network cost, and efficiently avoid the potential traffic overload on low cost links. To solve the large-scale optimization problem in our model, we are motivated to develop a distributed algorithm by blending the advantages of alternating direction method of multipliers (ADMM) and the auxiliary variable method. Specifically, we efficiently decompose the optimization problem into many small sub-problems, which are allowed to be processed in a large-scale computing environment, where each server solves a few small sub-problems. We further present a theoretically proved globally, asymptotically stable algorithm to solve these sub-problems. Extensive evaluation results demonstrate that our bandwidth allocation method can effectively realize the bandwidth guarantee for inter-datacenter traffic with reduced network cost and outperforms the prior method PS-L. In particular, the total network cost is reduced by 59.57 percent on average.

Currently, parallel data transmissions in large-scale datacenter networks are becoming increasingly crucial to application performance. Despite fine-grained control by SDN-enabled networks, some transmission errors, such as misconfigurations, will inevitably occur, resulting in high-level forwarding policies that cannot be conformed to at the data plane. Therefore, flow trajectory detection is very important for allowing datacenter network operators to troubleshoot problems and ensure that all traffic flows are running on the correct paths. However, existing solutions detect flow trajectories by recording the entire path of each packet. These methods are prone to imposing significant overheads in terms of both the number of switch entries and the amount of packet header space required. To considerably reduce this overhead, we present FlowTracer, an efficient flow trajectory detection solution, which can sample a path one link at a time instead of recording the entire path. FlowTracer consists of a method of probabilistic packet tagging and a method of trajectory reconstruction. In this paper, we first introduce the method of probabilistic packet tagging, which is performed in OpenFlow-enabled switches with very few switch entries and limited packet header space by means of double VLAN tags. Then, we explore the topological structure of datacenter networks and propose our method of trajectory reconstruction, which is performed at end hosts and achieves rapid convergence. Finally, we evaluate FlowTracer on a 48-ary fat-tree topology. The results show that FlowTracer can detect trajectories quickly while placing far smaller demands on both switch entries and packet header space than state-of-the-art techniques.

Modern stream processing frameworks, such as Spark Streaming, are designed to support a wide variety of stream processing applications, such as real-time data analytics in social networks. As the volume of data to be processed increases rapidly, there is a pressing need for processing them across multiple geo-distributed datacenters. However, these frameworks are not designed to take limited and varying inter-datacenter bandwidth into account, leading to longer query latencies. In this paper, we present the design and implementation of an extended Spark Streaming framework to automatically and optimally schedule tasks, select data flow routes and determine micro-batch sizes across geo-distributed datacenters in wide-area networks. To make these decisions, we propose a sparsity-regularized ADMM algorithm to efficiently solve a nonconvex optimization problem, based on readily measurable operating traces. Toward incremental real-world deployment, we take a non-intrusive approach to support flexible routing of micro-batches by adding a new DStream transformation we have developed to the existing Spark Streaming framework. As a result, our implementation can enforce scheduling decisions by modifying application workflows only. We have deployed our implementation on Amazon EC2 with emulated bandwidth constraints, and our experimental results on various types of queries have demonstrated the effectiveness of our proposed framework, as compared to the existing Spark Streaming scheduler and other data-locality-based heuristics.

Coflow scheduling is crucial to improve the communication performance of data-parallel jobs, especially when these jobs running in the inter-datacenter networks with limited and heterogeneous link bandwidth. However, prior solutions on coflow scheduling assume the endpoints of flows in a coflow to be fixed, making them insufficient to optimize the coflow completion time (CCT). In this paper, we focus on the problem of jointly considering endpoint placement and coflow scheduling to minimize the average CCT of coflows across geo-distributed datacenters. We first develop the mathematical model and formulate a mixed integer linear programming (MILP) problem to characterize the intertwined relationship between endpoint placement and coflow scheduling, and reveal their impact on the average CCT. Then, we present SmartCoflow, a coflow-aware optimization framework, to solve the MILP problem without any prior knowledge of coflow arrivals. In SmartCoflow, we first apply an approximate algorithm to obtain the endpoint placement and scheduling decisions for a single coflow. Based on the single-coflow solution, we then develop an efficient online algorithm to handle the dynamically arrived coflows. To validate the efficiency and practical feasibility of SmartCoflow, we implement it as a real-world coflow scheduler based on the Varys open-source framework. Through experimental results from both a small-scale testbed implementation and large-scale simulations, we demonstrate that SmartCoflow can achieve significant improvement on the average CCT, when compared to the state-of-the-art scheduling-only method.

Data-parallel applications generate a mix of coflows with and without deadlines. Deadline coflows are mission-critical and must be completed within deadlines, while non-deadline coflows desire to be completed as soon as possible. Scheduling such mix-coflows is an important problem in modern datacenters. However, existing solutions only focus on one of the two types of coflows: they either solely focus on meeting the deadlines of deadline-aware coflows or reducing the coflow completion times (CCTs) of non-deadline coflows. In this paper, we study the problem of optimizing deadline and non-deadline coflows simultaneously. To this end, we present a new optimization framework, mixCoflow, to schedule deadline coflows with the objective of minimizing and balancing their bandwidth footprint, such that non-deadline coflows can be scheduled as early as possible. Specifically, we develop the mathematical model and formulate the scheduling problem for deadline coflows as a lexicographical min-max integer linear programming (ILP) problem. Through rigorous theoretical analysis, this ILP problem has been proved to be equivalent to a linear programming (LP) problem that can be solved with standard LP solvers. By solving this LP, mixCoflow is able to balance the bandwidth footprint of deadline coflows while guaranteeing their deadlines. As a result, non-deadline coflows can be scheduled as soon as possible whenever they arrive. To demonstrate the effectiveness of our work, we have conducted extensive simulations based on a widely used Facebook data trace. The simulation results verify that mixCoflow can achieve significant improvement on the average CCT of non-deadline coflows, at no expense of increasing the deadline miss rates of deadline coflows, when compared to the state-of-art solutions.

Summary Virtual cluster has recently emerged as a common abstraction for cloud applications or tenants to specify and reserve resources. Such virtual cluster brings valuable insights into the cloud elasticity when scaling up or down the number of resources on demand. Unfortunately, for global‐scale applications running on geo‐distributed datacenters, it is always a challenge to scale the virtual cluster. Due to the fact that the inter‐datacenter bandwidth is an expensive and scarce resource, it is increasingly important yet typically hard to achieve cost‐minimizing bandwidth guarantees when scaling. However, existing approaches mainly focus on the scaling within intra‐datacenter networks and cannot be simply extended to the inter‐datacenter scenario. In this paper, we study the problem of scaling up a virtual cluster with consideration of both bandwidth cost minimization and bandwidth guarantees fulfillment targeting inter‐datacenter networks. Specifically, we first propose an efficient algorithm to scale up the virtual cluster without changing its original VM placement. With the observation that such VM placement can hinder the cluster scalability, we further present an optimized algorithm, which exploits VM migration when scaling. Finally, we conduct extensive simulations to demonstrate the effectiveness of our algorithms, in terms of both bandwidth cost and the acceptance rate of scaling requests with bandwidth guarantees.

Inefficient bandwidth sharing in a datacenter network, between different application frameworks, e.g., MapReduce and Spark, can lead to inelastic and skewed usage of link bandwidth and increased completion times for the applications. Existing work, however, either solely focuses on managing computation and storage resources or controlling only sending/receiving rate at hosts. In this paper, we present CoMan, a solution that provides global in-network bandwidth management in multiplexed data centers, with two goals: improving bandwidth utilization and reducing application completion time. CoMan first designs a novel abstraction of virtual link groups (VLGs) to establish a shared bandwidth resource pool. Based on this pool, CoMan implements a three-level bandwidth allocation model, which enables elastic bandwidth sharing among computing frameworks as well as guarantees network performance for the applications. CoMan further improves the bandwidth utilization by devising a VLG dependency graph and solves an optimization problem to guide the path selection using a 32-approximation algorithm. We conduct comprehensive trace-driven simulations as well as small-scale testbed experiments to evaluate the performance of CoMan. Extensive simulation results show that CoMan improves the bandwidth utilization and speeds up the application completion time by up to 2.83× and 6.68×, respectively, compared to the ECMP + ElasticSwitch solution. Our implementation also verifies that CoMan can realistically speed up the application completion times by 2.32× on average.

Increasing number of Internet-scale applications, such as video streaming, incur huge amount of wide area traffic. Such traffic over the unreliable Internet without bandwidth guarantee suffers unpredictable network performance. This result, however, is unappealing to the application providers. Fortunately, Internet giants like Google and Microsoft are increasingly deploying their private wide area networks (WANs) to connect their global datacenters. Such high-speed private WANs are reliable, and can provide predictable network performance. In this paper, we propose a new type of service-inter-datacenter network as a service (iDaaS), where traditional application providers can reserve bandwidth from those Internet giants to guarantee their wide area traffic. Specifically, we design a bandwidth trading market among multiple iDaaS providers and application providers, and concentrate on the essentialbandwidth pricingproblem. The involved challenging issue is that the bandwidth price of each iDaaS provider is not only influenced by other iDaaS providers, but also affected by the application providers. To address this issue, we characterize the interaction between iDaaS providers and application providers using a Stackelberg game model, and analyze the existence and uniqueness of the equilibrium. We further present an efficient bandwidth pricing algorithm by blending the advantage of a geometrical Nash bargaining solution and the demand segmentation method. For comparison, we present two bandwidth reservation algorithms, where each iDaaS provider's bandwidth is reserved in a weighted fair manner and a max-min fair manner, respectively. Finally, we conduct comprehensive trace-driven experiments. The evaluation results show that our proposed algorithms not only ensure the revenue of iDaaS providers, but also provide bandwidth guarantee for application providers with lower bandwidth price per unit.

The emerging deployment of geographically distributed data centers (DCs) incurs a significant amount of data transfers over the Internet. Such transfers are typically charged by Internet Service Providers (ISPs) with the widely adopted q-th percentile charging model. In such charging model, the time slots with top 100-q percent of data transmission do not affect the total transmission cost, and can be viewed as free. This brings the opportunity to optimize the scheduling of inter-DC transfers to minimize the entire transmission cost. However, very little work has been done to exploit those free time slots for scheduling inter-DC transfers. The crux is that existing work either lacks a mechanism to accumulate traffic to free time slots, or inevitably relies on prior knowledge of traffic arrival patterns. In this paper, we attempt to exploit those free time slots by leveraging diverse time-sensitivities among inter-DC transfers, so as to reduce or even minimize the transmission cost. Specifically, we advocate that a simple principle should be followed: more traffic peaks should be scheduled in free time slots, while less traffic differentiation should be maintained among the remaining time slots. To this end, we take advantage of the Lyapunov optimization techniques to design a pricing-aware control framework. This framework efficiently makes online decisions for inter-DC transfers without requiring a prior knowledge of traffic arrivals. To verify our proposed framework, we conduct small-scale testbed implementation. The results show that our framework can realistically reduce the transmission cost by up to 19.38%.

In the era of global-scale services, analytical queries are performed on datasets that span multiple data centers (DCs). Due to the scarce and expensive inter-DC bandwidth, various methods have been proposed to reduce either the traffic cost or the completion time for those analytics queries. However, current methods make no attempt to maximize the number of successfully served query requests. Moreover, most of them rely on unrealistic assumptions - such as analytical queries are repeated or known in advance. In this paper, we target at characterizing and optimizing the cost-performance tradeoff for geo-distributed data analytics. Our objectives are two-fold: (1) we minimize the inter-DC traffic cost when serving geo-distributed analytics with uncertain query demand, and (2) we maximize the system throughput, in terms of the number of query requests that can be successfully served with guaranteed queuing delay. To achieve these objectives, we take advantage of Lyapunov optimization techniques to design a two-timescale online control framework. Without prior knowledge of future query requests, this framework makes online decisions on input data placement and admission control of query requests. Extensive trace-driven simulation results demonstrate that our framework is capable of reducing inter-DC traffic cost, improving system throughput and guaranteeing a maximum delay for each query request.

Summary Multicast performs better than unicast in delivering the same content from a fixed single source to a set of destinations. Many efforts have been made to optimize such kind of deterministic multicast, such as minimizing the transmission cost of each multicast session. In practice, it is not necessary that the source of each multicast session has to be in a specific location, as long as certain constraints are satisfied. Accordingly, applications usually meet a novel multicast with uncertain sources, ie, uncertain multicast. That is, multiple nodes have the responsibility to act as the root node of a multicast session. Prior proposals have addressed an uncertain multicast by constructing the minimum cost forest. However, it is still unknown how to efficiently share the network resources, when a set of uncertain multicast occupies the network simultaneously. To tackle such a challenging issue, we present the packing problem of uncertain multicasts (MPU) to minimize the total transmission cost, under the constraint of link capacity. We prove that the MPU problem is NP‐hard. An intrinsic solution is constructing the minimum cost forest for each uncertain multicast individually. This method, however, is inefficient and may be infeasible because of the constraint of link capacity. Thus, we design 2 dedicated greedy methods, named priority‐based and adjusting congested link, to approximate the optimal solution. The comprehensive results indicate that both of our 2 methods can find a feasible solution for the MPU problem. Moreover, given a set of uncertain multicasts, the adjusting congested link method can generate a desired transmission structure for each uncertain multicast and achieve the least total cost when packing them.

In large-scale Internet applications running on geographically distributed datacenters, such as video streaming, it is important to efficiently allocate requests among datacenters. To the best of our knowledge, existing approaches, however, either solely focus on minimizing total cost for provider, or guaranteeing QoS for end-users. In this paper, we apply the software defined network (SDN) controller to enable the central control of the entire network, and propose a joint optimization model to consider high bandwidth utilization for provider and low delay for users. We present the Nash bargaining solution (NBS) based method to model both requirements of provider's high bandwidth utilization and end-users' low delay. Specifically, we formulate the design of request allocation under those requirements as an optimization problem, which is NP-hard. To solve such hard optimization problem, we develop an efficient algorithm blending the advantages of Logarithmic Smoothing technique and the auxiliary variable method. According to the theoretical analysis, we verify the existence and uniqueness of our solution and the convergence of our algorithm. We conduct a large amount of experiments based on real-world workload traces and demonstrate the efficiency of our algorithm compared to both greedy and locality algorithms.

Traditional networks are surprisingly fragile and difficult to manage. Software Defined Networking (SDN) gained significant attention from both academia and industry, as if simplify network management through centralized configuration. Existing work primarily focuses on networks of limited scope such as data-centers and enterprises, which makes the development of SDN hindered when it comes to large-scale network environments. One way of enabling communication between data-centers, enterprises and ISPs in a large-scale network is to establish a standard communication mechanism between these entities. In this paper, we propose Zebra, a framework for enabling communication between different SDN domains. Zebra has two modules: Heterogeneous Controller Management (HCM) module and Domain Relationships Management (DRM) module. HCM collects network information from a group of controllers with no interconnection and generate a domain-wide network view. DRM collects network information from other domains to generate a global-wide network view. Moreover, HCM supports different SDN controllers, such as floodlight, maestro and so on. To test this framework, we develop a prototype system, and give some experimental results.

Summary Large‐scale online services and distributed execution engines (i.e., MapReduce and Dryad) generate large volumes of traffic in data center networks. As a consequence, significant congestion can occur in the data center network. To the best of our knowledge, most existing approaches either focus on local congestion‐aware mechanisms, which have only a poor ability to handle asymmetry or use explicit congestion notification packets, which are difficult to implement directly in switch hardware. These methods are insufficient to solve the congestion problem. In this paper, we focus on a congestion‐free routing strategy, resorting to the global view of the data center network in a software‐defined networking controller. Specifically, a timeslot allocation was first conducted for the coming packets, and then the corresponding routing paths were computed for each packet. In view of the efficiency, the timeslot allocation algorithm follows a heuristic pattern, and the path selection is modeled as a bin‐packing problem. Simulation results showed that the congestion‐free routing strategy proposed here performs well in throughput, queuing, and end‐to‐end round‐trip time. Copyright © 2015 John Wiley & Sons, Ltd.

Large-scale data centers are the key infrastructures for hosting and running a variety of applications. Besides traditional L2/L3 devices, middleboxes are widely deployed in data centers and perform many important functions, e.g., the intrusion detection and firewall. Middleboxes are equipped with multiple kinds of resources, such as CPU and memory. Data flows undergoing different functions have heterogeneous processing time requirements on diverse resources. Researchers are in a dilemma as to how to provide fair service for flows and efficiently utilize those scarce resources. To address this problem, we propose a novel packet scheduling method, active time fairness queuing (ATFQ), for multi-resource environments. Prior packet scheduling methods usually focus on pursuing the fairness among flows, resulting in enormous waste of those scarce resources. ATFQ overcomes this essentially by redefining the fairness and can maximize the resource utilization with the guarantee of fairness. We conduct extensive simulations to evaluate the performance of ATFQ. The evaluation results demonstrate that flows get better service in many aspects under ATFQ. Meanwhile, the resource utilization rises up by about 10% than the traditional DRFQ, which is one of the mainstream involved methods.