Proceedings of the ACM Special Interest Group on Data Communication, SIGCOMM 2019, Beijing, China, August 19-23, 2019. ACM 【DBLP Link】
【Paper Link】 【Pages】:1-14
【Authors】: James Murphy McCauley ; Yotam Harchol ; Aurojit Panda ; Barath Raghavan ; Scott Shenker
【Abstract】: Recent Internet research has been driven by two facts and their contradictory implications: the current Internet architecture is both inherently flawed (so we should explore radically different alternative designs) and deeply entrenched (so we should restrict ourselves to backwards-compatible and therefore incrementally deployable improvements). In this paper, we try to reconcile these two perspectives by proposing a backwards-compatible architectural framework called Trotsky in which one can incrementally deploy radically new designs. We show how this can lead to a permanent revolution in Internet architecture by (i) easing the deployment of new architectures and (ii) allowing multiple coexisting architectures to be used simultaneously by applications. By enabling both architectural evolution and architectural diversity, Trotsky would create a far more extensible Internet whose functionality is not defined by a single narrow waist, but by the union of many coexisting architectures. By being incrementally deployable, Trotsky is not just an interesting but unrealistic clean-slate design, but a step forward that is clearly within our reach.
【Keywords】: Networks; Network architectures; Network types; Public Internet
【Paper Link】 【Pages】:15-28
【Authors】: Yuanjie Li ; Kyu-Han Kim ; Christina Vlachou ; Junqing Xie
【Abstract】: The 4G/5G cellular edge promises low-latency experiences anywhere, anytime. However, data charging gaps can arise between the cellular operators and edge application vendors, and cause over-/under-billing. We find that such gap can come from data loss, selfish charging, or both. It can be amplified in the edge, due to its low-latency requirements. We devise TLC, a Trusted, Loss-tolerant Charging scheme for the cellular edge. In its core, TLC enables loss-selfishness cancellation to bridge the gap, and constructs publicly verifiable, cryptographic proof-of-charging for mutual trust. We implement TLC with commodity edge nodes, OpenEPC and small cells. Our experiments in various edge scenarios validate TLC's viability of reducing the gap with marginal latency and other overhead.
【Keywords】: Networks; Network algorithms; Network economics; Network properties; Network security; Mobile and wireless security; Network protocols; Protocol correctness; Protocol testing and verification; Network types; Mobile networks
【Paper Link】 【Pages】:29-43
【Authors】: Jeremy Bogle ; Nikhil Bhatia ; Manya Ghobadi ; Ishai Menache ; Nikolaj Bjørner ; Asaf Valadarsky ; Michael Schapira
【Abstract】: To keep up with the continuous growth in demand, cloud providers spend millions of dollars augmenting the capacity of their wide-area backbones and devote significant effort to efficiently utilizing WAN capacity. A key challenge is striking a good balance between network utilization and availability, as these are inherently at odds; a highly utilized network might not be able to withstand unexpected traffic shifts resulting from link/node failures. We advocate a novel approach to this challenge that draws inspiration from financial risk theory: leverage empirical data to generate a probabilistic model of network failures and maximize bandwidth allocation to network users subject to an operator-specified availability target. Our approach enables network operators to strike the utilization-availability balance that best suits their goals and operational reality. We present TEAVAR (Traffic Engineering Applying Value at Risk), a system that realizes this risk management approach to traffic engineering (TE). We compare TEAVAR to state-of-the-art TE solutions through extensive simulations across many network topologies, failure scenarios, and traffic patterns, including benchmarks extrapolated from Microsoft's WAN. Our results show that with TEAVAR, operators can support up to twice as much throughput as state-of-the-art TE schemes, at the same level of availability.
【Keywords】: Networks; Network algorithms; Control path algorithms; Traffic engineering algorithms; Network economics; Network performance evaluation
【Paper Link】 【Pages】:44-58
【Authors】: Yuliang Li ; Rui Miao ; Hongqiang Harry Liu ; Yan Zhuang ; Fei Feng ; Lingbo Tang ; Zheng Cao ; Ming Zhang ; Frank Kelly ; Mohammad Alizadeh ; Minlan Yu
【Abstract】: Congestion control (CC) is the key to achieving ultra-low latency, high bandwidth and network stability in high-speed networks. From years of experience operating large-scale and high-speed RDMA networks, we find the existing high-speed CC schemes have inherent limitations for reaching these goals. In this paper, we present HPCC (High Precision Congestion Control), a new high-speed CC mechanism which achieves the three goals simultaneously. HPCC leverages in-network telemetry (INT) to obtain precise link load information and controls traffic precisely. By addressing challenges such as delayed INT information during congestion and overreac-tion to INT information, HPCC can quickly converge to utilize free bandwidth while avoiding congestion, and can maintain near-zero in-network queues for ultra-low latency. HPCC is also fair and easy to deploy in hardware. We implement HPCC with commodity programmable NICs and switches. In our evaluation, compared to DCQCN and TIMELY, HPCC shortens flow completion times by up to 95%, causing little congestion even under large-scale incasts.
【Keywords】: Networks; Network protocols; Transport protocols; Network types; Data center networks
【Paper Link】 【Pages】:59-74
【Authors】: Quentin De Coninck ; François Michel ; Maxime Piraux ; Florentin Rochet ; Thomas Given-Wilson ; Axel Legay ; Olivier Pereira ; Olivier Bonaventure
【Abstract】: Application requirements evolve over time and the underlying protocols need to adapt. Most transport protocols evolve by negotiating protocol extensions during the handshake. Experience with TCP shows that this leads to delays of several years or more to widely deploy standardized extensions. In this paper, we revisit the extensibility paradigm of transport protocols.
【Keywords】: Networks; Network protocols; Network protocol design; Transport protocols
【Paper Link】 【Pages】:75-89
【Authors】: Kun Qian ; Wenxue Cheng ; Tong Zhang ; Fengyuan Ren
【Abstract】: Many applications in distributed systems rely on underlying lossless networks to achieve required performance. Existing lossless network solutions propose different hop-by-hop flow controls to guarantee zero packet loss. However, another crucial problem called network deadlock occurs concomitantly. Once the system traps in a deadlock, a large part of network would be disabled. Existing deadlock avoidance solutions focus all their attentions on breaking the cyclic buffer dependency to eliminate circular wait (one necessary condition of deadlock). These solutions, however, impose many restrictions on network configurations and side-effects on performance.
【Keywords】: Networks; Network algorithms; Data path algorithms; Network protocols; Link-layer protocols
【Paper Link】 【Pages】:90-103
【Authors】: Bojie Li ; Tianyi Cui ; Zibo Wang ; Wei Bai ; Lintao Zhang
【Abstract】: Communication intensive applications in hosts with multi-core CPU and high speed networking hardware often put considerable stress on the native socket system in an OS. Existing socket replacements often leave significant performance on the table, as well have limitations on compatibility and isolation.
【Keywords】: Networks; Network protocols; Transport protocols; Software and its engineering; Software organization and properties; Contextual software domains; Operating systems
【Paper Link】 【Pages】:104-116
【Authors】: Yuchen Jin ; Sundararajan Renganathan ; Ganesh Ananthanarayanan ; Junchen Jiang ; Venkata N. Padmanabhan ; Manuel Schröder ; Matt Calder ; Arvind Krishnamurthy
【Abstract】: The network communications between the cloud and the client have become the weak link for global cloud services that aim to provide low latency services to their clients. In this paper, we first characterize WAN latency from the viewpoint of a large cloud provider Azure, whose network edges serve hundreds of billions of TCP connections a day across hundreds of locations worldwide. In particular, we focus on instances of latency degradation and design a tool, BlameIt, that enables cloud operators to localize the cause (i.e., faulty AS) of such degradation. BlameIt uses passive diagnosis, using measurements of existing connections between clients and the cloud locations, to localize the cause to one of cloud, middle, or client segments. Then it invokes selective active probing (within a probing budget) to localize the cause more precisely. We validate BlameIt by comparing its automatic fault localization results with that arrived at by network engineers manually, and observe that BlameIt correctly localized the problem in all the 88 incidents. Further, BlameIt issues 72X fewer active probes than a solution relying on active probing alone, and is deployed in production at Azure.
【Keywords】: Networks; Network performance evaluation; Network measurement; Network performance analysis; Network properties; Network reliability; Error detection and error correction; Network services; Network monitoring; Network types; Public Internet
【Paper Link】 【Pages】:117-129
【Authors】: Chenshu Wu ; Feng Zhang ; Yusen Fan ; K. J. Ray Liu
【Abstract】: Inertial measurements are critical to almost any mobile applications. It is usually achieved by dedicated sensors (e.g., accelerometer, gyroscope) that suffer from significant accumulative errors. This paper presents RIM, an RF-based Inertial Measurement system for precise motion processing. RIM turns a commodity WiFi device into an Inertial Measurement Unit (IMU) that can accurately track moving distance, heading direction, and rotating angle, requiring no additional infrastructure but a single arbitrarily placed Access Point (AP) whose location is unknown. RIM makes three key technical contributions. First, it presents a spatial-temporal virtual antenna retracing scheme that leverages multipath profiles as virtual antennas and underpins measurements of distance and orientation using commercial WiFi. Second, it introduces a super-resolution virtual antenna alignment algorithm that resolves sub-centimeter movements. Third, it presents an approach to handle measurement noises and thus delivers an accurate and robust system. Our experiments, over a multipath rich area of > 1,000 m2 with one single AP, show that RIM achieves a median error in moving distance of 2.3 cm and 8.4 cm for short-range and long-distance tracking respectively, and 6.1° mean error in heading direction, all significantly outperforming dedicated inertial sensors. We also demonstrate multiple RIM-enabled applications with great performance, including indoor tracking, handwriting, and gesture control.
【Keywords】: Computer systems organization; Embedded and cyber-physical systems; Human-centered computing; Ubiquitous and mobile computing
【Paper Link】 【Pages】:130-144
【Authors】: Fangfan Li ; Arian Akhavan Niaki ; David R. Choffnes ; Phillipa Gill ; Alan Mislove
【Abstract】: Net neutrality has been the subject of considerable public debate over the past decade. Despite the potential impact on content providers and users, there is currently a lack of tools or data for stakeholders to independently audit the net neutrality policies of network providers. In this work, we address this issue by conducting a one-year study of content-based traffic differentiation policies deployed in operational networks, using results from 1,045,413 crowdsourced measurements conducted by 126,249 users across 2,735 ISPs in 183 countries/regions. We develop and evaluate a methodology that combines individual per-device measurements to form high-confidence, statistically significant inferences of differentiation practices, including fixed-rate bandwidth limits (i.e., throttling) and delayed throttling practices. Using this approach, we identify differentiation in both cellular and WiFi networks, comprising 30 ISPs in 7 countries. We also investigate the impact of throttling practices on video streaming resolution for several popular video streaming providers.
【Keywords】: Networks; Network performance evaluation; Network measurement
【Paper Link】 【Pages】:145-158
【Authors】: Ramakrishna Padmanabhan ; Aaron Schulman ; Dave Levin ; Neil Spring
【Abstract】: Weather is a leading threat to the stability of our vital infrastructure. Last-mile Internet is no exception. Yet, unlike other vital infrastructure, weather's effect on last-mile Internet outages is not well understood. This work is the first attempt to quantify the effect of weather on residential outages.
【Keywords】: Networks; Network performance evaluation; Network measurement; Network properties; Network reliability
【Paper Link】 【Pages】:159-173
【Authors】: Axel Dahlberg ; Matthew Skrzypczyk ; Tim Coopmans ; Leon Wubben ; Filip Rozpedek ; Matteo Pompili ; Arian Stolk ; Przemyslaw Pawelczak ; Robert Knegjens ; Julio de Oliveira Filho ; Ronald Hanson ; Stephanie Wehner
【Abstract】: Quantum communication brings radically new capabilities that are provably impossible to attain in any classical network. Here, we take the first step from a physics experiment to a quantum internet system. We propose a functional allocation of a quantum network stack, and construct the first physical and link layer protocols that turn ad-hoc physics experiments producing heralded entanglement between quantum processors into a well-defined and robust service. This lays the groundwork for designing and implementing scalable control and application protocols in platform-independent software. To design our protocol, we identify use cases, as well as fundamental and technological design considerations of quantum network hardware, illustrated by considering the state-of-the-art quantum processor platform available to us (Nitrogen-Vacancy (NV) centers in diamond). Using a purpose built discrete-event simulator for quantum networks, we examine the robustness and performance of our protocol using extensive simulations on a supercomputing cluster. We perform a full implementation of our protocol in our simulator, where we successfully validate the physical simulation model against data gathered from the NV hardware. We first observe that our protocol is robust even in a regime of exaggerated losses of classical control messages with only little impact on the performance of the system. We proceed to study the performance of our protocols for 169 distinct simulation scenarios, including trade-offs between traditional performance metrics such as throughput, and the quality of entanglement. Finally, we initiate the study of quantum network scheduling strategies to optimize protocol performance for different use cases.
【Keywords】: Computer systems organization; Architectures; Other architectures; Quantum computing; Hardware; Emerging technologies; Quantum technologies; Quantum computation; Quantum communication and cryptography; Networks; Network protocols; Link-layer protocols; Network protocol design
【Paper Link】 【Pages】:174-186
【Authors】: Mohammad Hossein Mazaheri ; Soroush Ameli ; Ali Abedi ; Omid Abari
【Abstract】: With the advent of the Internet of Things (IoT), billions of new connected devices will come online, placing a huge strain on today's WiFi and cellular spectrum. This problem will be further exacerbated by the fact that many of these IoT devices are low-power devices that use low-rate modulation schemes and therefore do not use the spectrum efficiently. Millimeter wave (mmWave) technology promises to revolutionize wireless networks and solve spectrum shortage problem through the usage of massive chunks of high-frequency spectrum. However, adapting this technology presents challenges. Past work has addressed challenges in using mmWave for emerging applications, such as 5G, virtual reality and data centers, which require multiple-gigabits-per-second links, while having substantial energy and computing power. In contrast, this paper focuses on designing a mmWave network for low-power, low-cost IoT devices. We address the key challenges that prevent existing mmWave technology from being used for such IoT devices. First, current mmWave radios are power hungry and expensive. Second, mmWave radios use directional antennas to search for the best beam alignment. Existing beam searching techniques are complex and require feedback from access points (AP), which makes them unsuitable for low-power, low-cost IoT devices. We present mmX, a novel mmWave network that addresses existing challenges in exploiting mmWave for IoT devices. We implemented mmX and evaluated it empirically.
【Keywords】: Hardware; Communication hardware, interfaces and storage; Networking hardware; Signal processing systems; Beamforming; Wireless devices; Very large scale integration design; Analog and mixed-signal circuits; Radio frequency and wireless circuits; Networks; Network components; Wireless access points, base stations and infrastructure; Network types; Wireless access networks
【Paper Link】 【Pages】:187-199
【Authors】: Junsu Jang ; Fadel Adib
【Abstract】: We present Piezo-Acoustic Backscatter (PAB), the first technology that enables backscatter networking in underwater environments. PAB relies on the piezoelectric effect to enable underwater communication and sensing at near-zero power. Its architecture is inspired by radio backscatter which works well in air but cannot work well underwater due to the exponential attenuation of radio signals in water.
【Keywords】: Applied computing; Physical sciences and engineering; Earth and atmospheric sciences; Environmental sciences; Hardware; Communication hardware, interfaces and storage; Wireless integrated network sensors; Networks; Network architectures
【Paper Link】 【Pages】:200-213
【Authors】: Karthick Jayaraman ; Nikolaj Bjørner ; Jitu Padhye ; Amar Agrawal ; Ashish Bhargava ; Paul-Andre C. Bissonnette ; Shane Foster ; Andrew Helwer ; Mark Kasten ; Ivan Lee ; Anup Namdhari ; Haseeb Niaz ; Aniruddha Parkhi ; Hanukumar Pinnamraju ; Adrian Power ; Neha Milind Raje ; Parag Sharma
【Abstract】: We describe our experiences using formal methods and automated theorem proving for network operation at scale. The experiences are based on developing and applying the SecGuru and RCDC (Reality Checker for Data Centers) tools in Azure. SecGuru has been used since 2013 and thus, is arguably a pioneering industrial deployment of network verification. SecGuru is used for validating ACLs and more recently RCDC checks forwarding tables at Azure scale. A central technical angle is that we use local contracts and local checks, that can be performed at scale in parallel, and without maintaining global snapshots, to validate global properties of datacenter networks. Specifications leverage declarative encodings of configurations and automated theorem proving for validation. We describe how intent is automatically derived from network architectures and verification is incorporated as prechecks for making changes, live monitoring, and for evolving legacy policies. We document how network verification, grounded in architectural constraints, can be integral to operating a reliable cloud at scale.
【Keywords】: Computer systems organization; Dependable and fault-tolerant systems and networks; Availability; Reliability; Computing methodologies; Modeling and simulation; Model development and analysis; Model verification and validation; Networks; Network services; Cloud computing; Network management; Network monitoring
【Paper Link】 【Pages】:214-226
【Authors】: Bingchuan Tian ; Xinyi Zhang ; Ennan Zhai ; Hongqiang Harry Liu ; Qiaobo Ye ; Chunsheng Wang ; Xin Wu ; Zhiming Ji ; Yihong Sang ; Ming Zhang ; Da Yu ; Chen Tian ; Haitao Zheng ; Ben Y. Zhao
【Abstract】: In-network Access Control List (ACL) is an important technique in ensuring network-wide connectivity and security. As cloud-scale WANs today constantly evolve in size and complexity, in-network ACL rules are becoming increasingly more complex. This presents a great challenge to the updating process of ACL configurations: network operators are frequently required to update "tangled" ACL rules across thousands of devices to meet diverse business requirements, and even a single ACL misconfiguration may lead to network disruptions. Such increasing challenges call for an automated system to improve the efficiency and correctness of ACL updates. This paper presents Jinjing, a system that aids Alibaba's network operators in automatically and correctly updating ACL configurations in Alibaba's global WAN. Jinjing allows the operators to express in a declarative language, named LAI, their update intent (e.g., ACL migration and traffic control). Then, Jinjing automatically synthesizes ACL update plans that satisfy their intent. At the heart of Jinjing, we develop a set of novel verification and synthesis techniques to rigorously guarantee the correctness of update plans. In Alibaba, our operators have used Jinjing to efficiently update their ACLs and have thus prevented significant service downtime.
【Keywords】: Networks; Network properties; Network reliability; Network services; Network management
【Paper Link】 【Pages】:227-240
【Authors】: Kenneth L. McMillan ; Lenore D. Zuck
【Abstract】: QUIC is a new Internet secure transport protocol currently in the process of IETF standardization. It is intended as a replacement for the TLS/TCP stack and will be the basis of HTTP/3, the next official version of the hypertext transfer protocol. As a result, it is likely, in the near future, to carry a substantial fraction of traffic on the Internet. We describe our experience applying a methodology of compositional specification-based testing to QUIC. We develop a formal specification of the wire protocol, and use this specification to generate automated randomized testers for implementations of QUIC. The testers effectively take one role of the QUIC protocol, interacting with the other role to generate full protocol executions, and verifying that the implementations conform to the formal specification. This form of testing generates significantly more diverse stimuli and stronger correctness criteria than interoperability testing, the primary method used to date to validate QUIC and its implementations. As a result, numerous implementation errors have been found. These include some vulnerabilities at the protocol and implementation levels, such as an off-path denial of service scenario and an information leak similar to the "heartbleed" vulnerability in OpenSSL.
【Keywords】: Software and its engineering; Software creation and management; Software verification and validation; Software defect analysis; Software testing and debugging
【Paper Link】 【Pages】:241-255
【Authors】: Minsung Kim ; Davide Venturelli ; Kyle Jamieson
【Abstract】: User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely only because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an exponential rate both with the number of users and with the data rate of each user is often required. The base station's computational capacity is thus becoming one of the key limiting factors on wireless capacity. QuAMax is the first large MIMO centralized radio access network design to address this issue by leveraging quantum annealing on the problem. We have implemented QuAMax on the 2,031 qubit D-Wave 2000Q quantum annealer, the state-of-the-art in the field. Our experimental results evaluate that implementation on real and synthetic MIMO channel traces, showing that 10 µs of compute time on the 2000Q can enable 48 user, 48 AP antenna BPSK communication at 20 dB SNR with a bit error rate of 10-6 and a 1,500 byte frame error rate of 10-4.
【Keywords】: Hardware; Emerging technologies; Quantum technologies; Quantum computation; Networks; Network components; Wireless access points, base stations and infrastructure
【Paper Link】 【Pages】:256-269
【Authors】: Eric Liang ; Hang Zhu ; Xin Jin ; Ion Stoica
【Abstract】: Packet classification is a fundamental problem in computer networking. This problem exposes a hard tradeoff between the computation and state complexity, which makes it particularly challenging. To navigate this tradeoff, existing solutions rely on complex hand-tuned heuristics, which are brittle and hard to optimize.
【Keywords】: Networks; Network algorithms; Data path algorithms; Packet classification; Theory of computation; Theory and algorithms for application domains; Machine learning theory; Reinforcement learning
【Paper Link】 【Pages】:270-288
【Authors】: Hongzi Mao ; Malte Schwarzkopf ; Shaileshh Bojja Venkatakrishnan ; Zili Meng ; Mohammad Alizadeh
【Abstract】: Efficiently scheduling data processing jobs on distributed compute clusters requires complex algorithms. Current systems use simple, generalized heuristics and ignore workload characteristics, since developing and tuning a scheduling policy for each workload is infeasible. In this paper, we show that modern machine learning techniques can generate highly-efficient policies automatically.
【Keywords】: Computing methodologies; Machine learning; Learning paradigms; Reinforcement learning; Networks; Network algorithms; Control path algorithms; Network resources allocation; Software and its engineering; Software organization and properties; Contextual software domains; Operating systems; Process management; Scheduling
【Paper Link】 【Pages】:289-302
【Authors】: Xu Zhang ; Siddhartha Sen ; Daniar Kurniawan ; Haryadi Gunawi ; Junchen Jiang
【Abstract】: Conventional wisdom states that to improve quality of experience (QoE), web service providers should reduce the median or other percentiles of server-side delays. This work shows that doing so can be inefficient due to user heterogeneity in how the delays impact QoE. From the perspective of QoE, the sensitivity of a request to delays can vary greatly even among identical requests arriving at the service, because they differ in the wide-area network latency experienced prior to arriving at the service. In other words, saving 50ms of server-side delay affects different users differently.
【Keywords】: Human-centered computing; Information systems; World Wide Web; Web services
【Paper Link】 【Pages】:303-317
【Authors】: A. Pinar Ozisik ; Gavin Andresen ; Brian Neil Levine ; Darren Tapp ; George Bissias ; Sunny Katkuri
【Abstract】: We introduce Graphene, a method and protocol for interactive set reconciliation among peers in blockchains and related distributed systems. Through the novel combination of a Bloom filter and an Invertible Bloom Lookup Table (IBLT), Graphene uses a fraction of the network bandwidth used by deployed work for one- and two-way synchronization. We show that, for this specific problem, Graphene is more efficient at reconciling n items than using a Bloom filter at the information theoretic bound. We contribute a fast and implementation-independent algorithm for parameterizing an IBLT so that it is optimally small in size and meets a desired decode rate with arbitrarily high probability. We characterize our performance improvements through analysis, detailed simulation, and deployment results for Bitcoin Cash, a prominent cryptocurrency. Our implementations of Graphene, IBLTs, and our IBLT optimization algorithm are all open-source code.
【Keywords】: Networks; Network protocols; Network protocol design
【Paper Link】 【Pages】:318-333
【Authors】: Ming Liu ; Tianyi Cui ; Henry Schuh ; Arvind Krishnamurthy ; Simon Peter ; Karan Gupta
【Abstract】: Emerging Multicore SoC SmartNICs, enclosing rich computing resources (e.g., a multicore processor, onboard DRAM, accelerators, programmable DMA engines), hold the potential to offload generic datacenter server tasks. However, it is unclear how to use a SmartNIC efficiently and maximize the offloading benefits, especially for distributed applications. Towards this end, we characterize four commodity SmartNICs and summarize the offloading performance implications from four perspectives: traffic control, computing capability, onboard memory, and host communication.
【Keywords】: Hardware; Communication hardware, interfaces and storage; Networking hardware; Networks; Network services; In-network processing; Programmable networks
【Paper Link】 【Pages】:334-350
【Authors】: Zaoxing Liu ; Ran Ben-Basat ; Gil Einziger ; Yaron Kassner ; Vladimir Braverman ; Roy Friedman ; Vyas Sekar
【Abstract】: Software switches are emerging as a vital measurement vantage point in many networked systems. Sketching algorithms or sketches, provide high-fidelity approximate measurements, and appear as a promising alternative to traditional approaches such as packet sampling. However, sketches incur significant computation overhead in software switches. Existing efforts in implementing sketches in virtual switches make sacrifices on one or more of the following dimensions: performance (handling 40 Gbps line-rate packet throughput with low CPU footprint), robustness (accuracy guarantees across diverse workloads), and generality (supporting various measurement tasks).
【Keywords】: Networks; Network performance evaluation; Network measurement; Network services; Network monitoring
【Paper Link】 【Pages】:351-366
【Authors】: Praveen Kumar ; Nandita Dukkipati ; Nathan Lewis ; Yi Cui ; Yaogong Wang ; Chonggang Li ; Valas Valancius ; Jake Adriaens ; Steve Gribble ; Nate Foster ; Amin Vahdat
【Abstract】: Network virtualization stacks are the linchpins of public clouds. A key goal is to provide performance isolation so that workloads on one Virtual Machine (VM) do not adversely impact the network experience of another VM. Using data from a major public cloud provider, we systematically characterize how performance isolation can break in current virtualization stacks and find a fundamental tradeoff between isolation and resource multiplexing for efficiency. In order to provide predictable performance, we propose a new system called PicNIC that shares resources efficiently in the common case while rapidly reacting to ensure isolation. PicNIC builds on three constructs to quickly detect isolation breakdown and to enforce it when necessary: CPU-fair weighted fair queues at receivers, receiver-driven congestion control for backpressure, and sender-side admission control with shaping. Based on an extensive evaluation, we show that this combination ensures isolation for VMs at sub-millisecond timescales with negligible overhead.
【Keywords】: Networks; Network algorithms; Network properties; Network reliability; Network protocols; Transport protocols; Network services; Cloud computing
【Paper Link】 【Pages】:367-379
【Authors】: Vishal Shrivastav
【Abstract】: With increasing link speeds and slowdown in the scaling of CPU speeds, packet scheduling in software is resulting in lower precision and higher CPU utilization. By offloading packet scheduling to the hardware such as a NIC, one can potentially overcome these drawbacks. However, to retain the flexibility of software packet schedulers, packet scheduler in hardware must be programmable, while also being fast and scalable. State-of-the-art packet schedulers in hardware either compromise on scalability (Push-In-First-Out (PIFO)) or the ability to express a wide range of packet scheduling algorithms (First-In-First-Out (FIFO)). Further, even a general scheduling primitive like PIFO is not expressive enough to express certain key classes of packet scheduling algorithms. Hence in this paper, we propose a generalization of the PIFO primitive, called Push-In-Extract-Out (PIEO), which like PIFO, maintains an ordered list of elements, but unlike PIFO which only allows dequeue from the head of the list, PIEO allows dequeue from arbitrary positions in the list by supporting a programmable predicate-based filtering at dequeue. Next, we present a fast and scalable hardware design of PIEO scheduler and prototype it on a FPGA. Overall, PIEO scheduler is both more expressive and over 30× more scalable than PIFO.
【Keywords】: Hardware; Communication hardware, interfaces and storage; Networking hardware; Networks; Network services; Programmable networks
【Paper Link】 【Pages】:380-393
【Authors】: Devdeep Ray ; Jack Kosaian ; K. V. Rashmi ; Srinivasan Seshan
【Abstract】: Social live video streaming (SLVS) applications are becoming increasingly popular with the rise of platforms such as Facebook-Live, YouTube-Live, Twitch and Periscope. A key characteristic that differentiates this new class of applications from traditional live streaming is that these live streams are watched by viewers at different delays; while some viewers watch a live stream in real-time, others view the content in a time-shifted manner at different delays. In the presence of variability in the upload bandwidth, which is typical in mobile environments, existing solutions silo viewers into either receiving low latency video at a lower quality or a higher quality video with a significant delay penalty, without accounting for the presence of diverse time-shifted viewers.
【Keywords】: Information systems; Information systems applications; Multimedia information systems; Multimedia streaming
【Paper Link】 【Pages】:394-407
【Authors】: Yu Guan ; Chengyuan Zheng ; Xinggong Zhang ; Zongming Guo ; Junchen Jiang
【Abstract】: Streaming 360° videos requires more bandwidth than non-360° videos. This is because current solutions assume that users perceive the quality of 360° videos in the same way they perceive the quality of non-360° videos. This means the bandwidth demand must be proportional to the size of the user's field of view. However, we found several quality-determining factors unique to 360° videos, which can help reduce the bandwidth demand. They include the moving speed of a user's viewpoint (center of the user's field of view), the recent change of video luminance, and the difference in depth-of-fields of visual objects around the viewpoint.
【Keywords】: Networks; Network protocols; Application layer protocols
【Paper Link】 【Pages】:408-423
【Authors】: Vikram Nathan ; Vibhaalakshmi Sivaraman ; Ravichandra Addanki ; Mehrdad Khani Shirkoohi ; Prateesh Goyal ; Mohammad Alizadeh
【Abstract】: The growth of video traffic makes it increasingly likely that multiple clients share a bottleneck link, giving video content providers an opportunity to optimize the experience of multiple users jointly. But today's transport protocols are oblivious to video streaming applications and provide only connection-level fairness. We design and build Minerva, the first end-to-end transport protocol for multi-user video streaming. Minerva uses information about the player state and video characteristics to adjust its congestion control behavior to optimize for QoE fairness. Minerva clients receive no explicit information about other video clients, yet when multiple of them share a bottleneck link, their rates converge to a bandwidth allocation that maximizes QoE fairness. At the same time, Minerva videos occupy only their fair share of the bottleneck link bandwidth, competing fairly with existing TCP traffic. We implement Minerva on an industry standard video player and server and show that, compared to Cubic and BBR, 15-32%of the videos using Minerva experience an improvement in viewing experience equivalent to a jump in resolution from 720p to 1080p. Additionally, in a scenario with dynamic video arrivals and departures, Minerva reduces rebuffering time by an average of 47%.
【Keywords】: Networks; Network protocols; Application layer protocols
【Paper Link】 【Pages】:424-440
【Authors】: Sucha Supittayapornpong ; Barath Raghavan ; Ramesh Govindan
【Abstract】: The performance and availability of cloud and content providers often depends on the wide area networks (WANs) they use to interconnect their datacenters. WAN routers, which connect to each other using trunks (bundles of links), are sometimes built using an internal Clos topology connecting merchant-silicon switches. As such, these routers are susceptible to internal link and switch failures, resulting in reduced capacity and low availability. Based on the observation that today's WAN routers use relatively simple trunk wiring and routing techniques, we explore the design of novel wiring and more sophisticated routing techniques to increase failure resilience. Specifically, we describe techniques to 1) optimize trunk wiring to increase effective internal router capacity so as to be resilient to internal failures, 2) compute the effective capacity under different failure patterns, and 3) use these to compute compact routing tables under different failure patterns, since switches have limited routing table sizes. Our evaluations show that our approach can mask failures of up to 75% of switches in some cases without exceeding routing table limits, whereas competing techniques can sometimes lose half of a WAN router's capacity with a single failure.
【Keywords】: Computer systems organization; Dependable and fault-tolerant systems and networks; Availability; Fault-tolerant network topologies; Reliability; Networks; Network algorithms; Control path algorithms; Network design and planning algorithms; Network components; Intermediate nodes; Routers; Network performance evaluation; Network performance analysis; Network properties; Network structure; Topology analysis and generation
【Paper Link】 【Pages】:441-457
【Authors】: Philipp H. Kindt ; Samarjit Chakraborty
【Abstract】: Mobile devices apply neighbor discovery (ND) protocols to wirelessly initiate a first contact within the shortest possible amount of time and with minimal energy consumption. For this purpose, over the last decade, a vast number of ND protocols have been proposed, which have progressively reduced the relation between the time within which discovery is guaranteed and the energy consumption. In spite of the simplicity of the problem statement, even after more than 10 years of research on this specific topic, new solutions are still proposed even today. Despite the large number of known ND protocols, given an energy budget, what is the best achievable latency still remains unclear. This paper addresses this question and for the first time presents safe and tight, duty-cycle-dependent bounds on the worst-case discovery latency that no ND protocol can beat. Surprisingly, several existing protocols are indeed optimal, which has not been known until now. We conclude that there is no further potential to improve the relation between latency and duty-cycle, but future ND protocols can improve their robustness against beacon collisions.
【Keywords】: Networks; Network performance evaluation; Network performance analysis; Network protocols; Network protocol design; Network types; Ad hoc networks; Mobile ad hoc networks
【Paper Link】 【Pages】:458-471
【Authors】: Muhammad Shahbaz ; Lalith Suresh ; Jennifer Rexford ; Nick Feamster ; Ori Rottenstreich ; Mukesh Hira
【Abstract】: We present Elmo, a system that addresses the multicast scalability problem in multi-tenant datacenters. Modern cloud applications frequently exhibit one-to-many communication patterns and, at the same time, require sub-millisecond latencies and high throughput. IP multicast can achieve these requirements but has control- and data-plane scalability limitations that make it challenging to offer it as a service for hundreds of thousands of tenants, typical of cloud environments. Tenants, therefore, must rely on unicast-based approaches (e.g., application-layer or overlay-based) to support multicast in their applications, imposing bandwidth and end-host CPU overheads, with higher and unpredictable latencies.
【Keywords】: Networks; Network protocols; Network protocol design; Network services; In-network processing; Programmable networks; Network types; Data center networks