bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimized leaf ordering with class labels for hierarchical clustering
Authors: Novoselova Natalia , Wang Junxi , Klawonn Frank
Published: March 2015

Hierarchical clustering is extensively used in the bioinformatics community to analyze biomedical data. These data are often tagged with class labels, as e.g. disease subtypes or gene ontology (GO) terms. Heatmaps in connection with dendrograms are the common standard to visualize results of hierarchical clustering. The heatmap can be enriched by an additional color bar at the side, indicating for each instance in the data set to which class it belongs. In the ideal case, when the clustering matches perfectly with the classes, one would expect that instances from the same class cluster together and the color bar consists of well-separated color blocks without frequent alteration of colors (classes). But even in the case when instances from the same class cluster perfectly together, the dendrogram might not reflect this important aspect due to the fact that its representation is not unique. In this paper, we propose a leaf ordering algorithm for the dendrogram that preserving the hierarchical clustering result tries to group instances from the same class together. It is based on the concept of dynamic programming which can efficiently compute the optimal or nearly optimal order, consistent with the structure of the tree.
Star decomposition of graphs
Authors: Zhao Yang , Wu Baoyindureng
Published: March 2015

Let k be a positive integer and G be a graph. If d(u) + d(v) ≥ 4k - 3 for any uv ∈ E(G), then G admits a star decomposition in which all stars have size at least k. In particular, every graph G with δ(G) ≥ 2k - 1 admits such a decomposition. The bounds are best possible, in the sense that there exist infinitely many graphs G with δ(G) ≥ 2k - 2 and without such a decomposition.
Theoretical study on the electronic structure, mechanical property, and thermal expansion of yttrium oxysulfide
Authors: Gao Ruipeng , Li Yefei
Published: March 2015

The electronic structure, mechanical property and thermal expansion of yttrium oxysulfide are calculated from first-principles using the theory of density functional. The calculated cohesive energy indicates its thermodynamic stable nature. From bond structure, the calculated bandgap is obtained as 2.7 eV; and strong covalent bonds exist between Y and O atoms intra 2D [ Y – O ] layer in material, while relatively weak covalent bonds also exist inter 2D [ Y – O ] layer and S atoms. From simulation, it is found that the bulk modulus is about 119.4 GPa for the elastic constants, and the bulk modulus shows weak anisotropy because the surface contours of them are close to a spherical shape. The calculated B/G clearly implies its ductile nature, and the Y 2 O 2 S phase can also be compressed easily. The temperature dependence of thermal expansions is mainly caused by the restoration of thermal energy due to lattice excitations at low temperature. When the temperature is very high, the thermal expansion coefficient increases linearly with temperature increasing. Meanwhile, the heat capacities are also calculated and discussed by thermal expansion and elasticity.
Chapter 10 Palaeo-Mesoproterozoic sedimentation and tectonics of the Singhbhum Craton, eastern India, and implications for global and craton-specific geological events
Authors: Mazumder Rajat , De Shuvabrata , Ohta Tohru , Flannery David , Mallik Leena , Chaudhury Trisrota , Chatterjee Priyanka , Ranaivoson Marinah A. , Arima Makoto
Published: March 2015

The Singhbhum Craton in eastern India preserves a depositional record from the Palaeo-Mesoarchaean to the Mesoproterozoic. Herein, we have summarized the Palaeo-Mesoproterozoic supracrustal record of the Singhbhum Craton, discussed tectonosedimentary processes and discriminated Palaeo-Mesoproterozoic global and craton-specific events. The late Palaeo-Mesoproterozoic supracrustal record of the Singhbhum Craton is limited. It includes evidence for high continental freeboard conditions during 2.6–2.1 Ga in the form of terrestrial deposits (alluvial fan–fluvial) of the Dhanjori Formation. This was followed by a major transgression and a transition to the relatively deeper-water shelf to shallow intertidal environments recorded by the Chaibasa Formation. A long hiatus ensued before deposition of the Dhalbhum Formation and conformably overlying Dalma and Chandil formations, suggesting continued high continental freeboard during 2.2–1.6 Ga. In significant contrast to the craton-specific Dhanjori Formation volcanism, the 1.7–1.6 Ga plume-related Dalma volcanism was probably part of a global tectonothermal event.
Chapter 17 Sedimentation in the Papaghni Group of rocks in the Papaghni sub-basin of the Proterozoic Cuddapah Basin, India
Authors: Chakrabarti G. , Eriksson P. G. , Shome D.
Published: March 2015

The Gulcheru Quartzite (30–200 m thick) overlies Archaean basement rocks, and comprises an impersistent conglomerate at the base of more widespread quartzites, with shale and ferruginous interbeds. The overlying Vempalle Formation (≤1500 m) comprises mainly stromatolitic carbonates, lesser cherts and mudrocks. Together, these two units make up the Palaeoproterozoic Papaghni Group, which displays an arcuate outcrop belt in the SW Cuddapah Basin, bearing no obvious relationship to the tectonic grain in the basement lithologies. Facies defined in the Gulcheru Quartzite are ascribed to initial alluvial fans, which transitioned into a shallow-marine coastline and shelf, as transgression occurred under overall thermal subsidence, possibly related to post-plume thermal relaxation. The shallow siliciclastic Gulcheru shelf is inferred to have evolved to a stromatolitic ramp that accommodated deposition of the Vempalle chemical sediments. The abrupt vertical transition from clastic to carbonate deposits is ascribed to rapid sea-level rise. Late-stage shoreline progradation during uppermost Vempalle times and concomitant clastic inflows terminated the carbonate factory.
Chapter 2 Classification of basins, with special reference to Proterozoic examples
Authors: Allen P. A. , Eriksson P. G. , Alkmim F. F. , Betts P. G. , Catuneanu O. , Mazumder R. , Meng Q. , Young G. M.
Published: March 2015

Basin classification rests on a plate tectonic foundation, highlighting lithospheric substrate, proximity to plate margin and relative motion of the nearest plate boundary. Major mechanisms for regional subsidence and uplift are subdivided into isostatic, flexural and dynamic groups. Basin-forming mechanisms and basin types do not exhibit simple cause-and-effect relationships, but rather reflect a matrix-type relationship. Different basin types have different spans of existence, with generally shorter life spans related to more tectonically active settings. Many ‘polyhistory’ basins, composed of two or more megasequences, reflect a long evolution dominated by different basin-forming and basin-modifying mechanisms. The supercontinent cycle is marked by distinct sets of basin types, developed during successive phases of the cycle. Major classification schemes are reviewed briefly, before surveying the range of basin types represented in the Proterozoic of several key cratonic areas. Basins examined encompass almost the entire Neoarchaean–Neoproterozoic period. All of these basins have a relatively long history of preservation, which can be tied to the essentially continental character of their basement rocks and concomitant enhanced ‘survivability’. Their preservation thus underlines the longevity and inherent stability of the continental lithosphere. The distinction between basin occurrence over geological time and preferential preservation is important when viewing the geological record.
Chapter 22 Precambrian metallic mineralization in India
Authors: Mishra Biswajit
Published: March 2015

Four Archaean cratons (Aravalli–Bundelkhand, Singhbhum, Bastar and Dharwar), together with the marginal Proterozoic mobile belts and sedimentary basins, constitute the geology of peninsular India. Huge resources of ferrous metals (Fe and Mn) and chromite, the lone granitoid-hosted Malanjkhand Cu–Mo deposit, a moderate occurrence of gold and promising platinum group element mineralization constitute the Archaean metal inventory of India. Additionally, the Proterozoic Aeon witnessed diverse mineralization in the mobile belts and craton–mobile belt contacts. These include vast resources of base metals in the northwestern Indian Shield and Mn in the central Indian block, apart from considerable U–Cu deposits in the Singhbhum Shear Zone. These ores formed as a consequence of an entire genetic spectrum, covering various orthomagmatic, volcanosedimentary and diverse hydrothermal processes, aided and abetted by supergene enrichment, as in the case of iron ores.
Chapter 4 Lithostratigraphic, geochronological and depositional framework of the Precambrian basins of the Aravalli Mountains and adjoining areas, Rajasthan, India
Authors: Roy A. B. , Purohit Ritesh
Published: March 2015

The Aravalli Mountains and neighbouring areas have well-preserved records of a protracted history of development of Precambrian basins, which spans about 2500 myr of the Earth's history. The oldest depositional basins are the greenstone belts that occur within the Archaean gneiss–granite terrain. Geochronological data indicate evolution of one such greenstone belt from 3300 to 2850 Ma. The younger Proterozoic cover successions include the Aravalli Supergroup, Delhi Supergroup and Sirohi Group, which evolved during three successive orogenic cycles spanning between
c.
2200 and
c.
1850 Ma,
c.
1700 and
c.
1450 Ma, and
c.
1000 and
c.
850 Ma, respectively. Each of these lithostratigraphic units evolved in separate basins having distinctive tectonic, metallogenic and evolutionary histories. The inversion of the youngest ‘orogenic’ basin marks the final cratonization of the Precambrian Aravalli crust at around 850 Ma. The succeeding depositional episodes include formation of ephemeral basins during the early phase of the plume-related Malani Group from 780 to 730 Ma, and the formation of the Marwar Supergroup deposited in stable platformal basins marks the terminal phase of the Precambrian crust-building history in the region.
A Model-Based Approach for Developing Data Cleansing Solutions
Authors: Mezzanzanica Mario , Boselli Roberto , Cesarini Mirko , Mercorio Fabio
Published: March 2015

The data extracted from electronic archives is a valuable asset; however, the issue of the (poor) data quality should be addressed before performing data analysis and decision-making activities. Poor data quality is frequently cleansed using business rules derived from domain knowledge. Unfortunately, the process of designing and implementing cleansing activities based on business rules requires a relevant effort. In this article, we illustrate a model-based approach useful to perform inconsistency identification and corrective interventions, thus simplifying the process of developing cleansing activities. The article shows how the cleansing activities required to perform a sensitivity analysis can be easily developed using the proposed model-based approach. The sensitivity analysis provides insights on how the cleansing activities can affect the results of indicators computation. The approach has been successfully used on a database describing the working histories of an Italian area population. A model formalizing how data should evolve over time (i.e., a data consistency model) in such domain was created (by means of formal methods) and used to perform the cleansing and sensitivity analysis activities.
The Natural History Production Line
Authors: Heerlien Maarten , Van Leusen Joost , Schnörr Stephanie , De Jong-Kole Suzanne , Raes Niels , Van Hulsen Kirsten
Published: March 2015

In 2010, Naturalis Biodiversity Center started one of the largest and most diverse programs for natural history collection digitization to date. From a total collection of 37 million specimens and related objects, 7 million relevant objects are to be digitized in a 5-year period. This article provides an overview of the program and discusses the chosen industrial production line approach, the applied method for prioritization of collections that are to be digitized, and some preliminary results.
Constant-Round Nonmalleable Commitments from Any One-Way Function
Authors: Lin Huijia , Pass Rafael
Published: March 2015

We show unconditionally that the existence of commitment schemes implies the existence of
constant-round
nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or subexponential one-way functions.

Our protocol also satisfies the stronger notions of concurrent nonmalleability and robustness. As a corollary, we establish that constant-round nonmalleable zero-knowledge arguments for
NP
can be based on one-way functions and constant-round secure multiparty computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
Hybrid Skeletal-Surface Motion Graphs for Character Animation from 4D Performance Capture
Authors: Huang Peng , Tejera Margara , Collomosse John , Hilton Adrian
Published: March 2015

We present a novel hybrid representation for character animation from 4D Performance Capture (4DPC) data which combines skeletal control with surface motion graphs. 4DPC data are temporally aligned 3D mesh sequence reconstructions of the dynamic surface shape and associated appearance from multiple-view video. The hybrid representation supports the production of novel surface sequences which satisfy constraints from user-specified key-frames or a target skeletal motion. Motion graph path optimisation concatenates fragments of 4DPC data to satisfy the constraints while maintaining plausible surface motion at transitions between sequences. Space-time editing of the mesh sequence using a learned part-based Laplacian surface deformation model is performed to match the target skeletal motion and transition between sequences. The approach is quantitatively evaluated for three 4DPC datasets with a variety of clothing styles. Results for key-frame animation demonstrate production of novel sequences that satisfy constraints on timing and position of less than 1% of the sequence duration and path length. Evaluation of motion-capture-driven animation over a corpus of 130 sequences shows that the synthesised motion accurately matches the target skeletal motion. The combination of skeletal control with the surface motion graph extends the range and style of motion which can be produced while maintaining the natural dynamics of shape and appearance from the captured performance.
Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model
Authors: Chang Naiwen , Cheng Eddie , Hsieh Sunyuan
Published: March 2015

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n-11 for
n
≥ 4 except for the
n
-dimensional star graph for which it has been shown to be 8
n
-21 for
n
≥ 5 (refer to Chang and Hsieh [2014]).
Prolonging Lifetime of PCM-Based Main Memories through On-Demand Page Pairing
Authors: Asadinia Marjan , Arjomand Mohammad , Azad Hamid Sarbazi
Published: March 2015

With current memory scalability challenges, Phase-Change Memory (PCM) is viewed as an attractive replacement to DRAM. The preliminary concern for PCM applicability is its limited write endurance that results in fast wear-out of memory cells. Worse, process variation in the deep-nanometer regime increases the variation in cell lifetime, resulting in an early and sudden reduction in main memory capacity due to the wear-out of a few cells. Recent studies have proposed redirection or correction schemes to alleviate this problem, but all suffer poor throughput or latency. In this article, we show that one of the inefficiency sources in current schemes, even when wear-leveling algorithms are used, is the nonuniform write endurance limit incurred by process variation, that is, when some memory pages have reached their endurance limit, other pages may be far from their limit. In this line, we present a technique that aims to displace a faulty page to a healthy page. This technique, called On-Demand Page Paired PCM (OD3P, for short), when applied at page level, can improve PCM time-to-failure by 20% on average for different multithreaded and multiprogrammed workloads while also improving IPC by 14% on average compared to previous page-level techniques. The comparison between line-level OD3P and previous line-level techniques reveals about 2× improvement of lifetime and performance.
CamMark
Authors: Schaber Philipp , Kopf Stephan , Wetzel Sina , Ballast Tyler , Wesch Christoph , Effelsberg Wolfgang
Published: March 2015

To support the development of any system that includes the generation and evaluation of camcorder copies, as well as to provide a common benchmark for robustness against camcorder copies, we present a tool to simulate digital video re-acquisition using a digital video camera. By resampling each video frame, we simulate the typical artifacts occurring in a camcorder copy: geometric modifications (aspect ratio changes, cropping, perspective and lens distortion), temporal sampling artifacts (due to different frame rates, shutter speeds, rolling shutters, or playback), spatial and color subsampling (rescaling, filtering, Bayer color filter array), and processing steps (automatic gain control, automatic white balance). We also support the simulation of camera movement (e.g., a hand-held camera) and background insertion. Furthermore, we allow for an easy setup and calibration of all the simulated artifacts, using sample/reference pairs of images and videos. Specifically temporal subsampling effects are analyzed in detail to create realistic frame blending artifacts in the simulated copies. We carefully evaluated our entire camcorder simulation system and found that the models we developed describe and match the real artifacts quite well.
Reshaping the limits of design in HCI
Authors: Rosner Daniela K.
Published: March 2015

This forum highlights conversations at the intersection of design methods and social studies of technology. By highlighting a diversity of perspectives on design interventions and programs, we aim to forge new connections between HCI design and communication, science and technology studies, and media studies scholarship. ---
Daniela K. Rosner, Editor
Children as participants in design and evaluation
Authors: Read Janet
Published: March 2015

This forum addresses conceptual, methodological, and professional issues that arise in the UX field's continuing effort to contribute robust information about users to product planning and design. ---
David Siegel and Susan Dray, Editors
DREAM
Authors: Moshref Masoud , Yu Minlan , Govindan Ramesh , Vahdat Amin
Published: March 2015

Software-defined networks can enable a variety of concurrent, dynamically instantiated, measurement tasks, that provide fine-grain visibility into network traffic. Recently, there have been many proposals to configure TCAM counters in hardware switches to monitor traffic. However, the TCAM memory at switches is fundamentally limited and the accuracy of the measurement tasks is a function of the resources devoted to them on each switch. This paper describes an adaptive measurement framework, called DREAM, that dynamically adjusts the resources devoted to each measurement task, while ensuring a user-specified level of accuracy. Since the trade-off between resource usage and accuracy can depend upon the type of tasks, their parameters, and traffic characteristics, DREAM does not assume an a priori characterization of this trade-off, but instead dynamically searches for a resource allocation that is sufficient to achieve a desired level of accuracy. A prototype implementation and simulations with three network-wide measurement tasks (heavy hitter, hierarchical heavy hitter and change detection) and diverse traffic show that DREAM can support more concurrent tasks with higher accuracy than several other alternatives.
SAX-PAC (Scalable And eXpressive PAcket Classification)
Authors: Kogan Kirill , Nikolenko Sergey , Rottenstreich Ori , Culhane William , Eugster Patrick
Published: March 2015

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time \emph{and} allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench (with real parameters), 90-95% of rules are thus handled, and the other 5-10% of rules can be stored in TCAM to be processed in parallel.
Using RDMA efficiently for key-value services
Authors: Kalia Anuj , Kaminsky Michael , Andersen David G.
Published: March 2015

This paper describes the design and implementation of HERD, a key-value system designed to make the best use of an RDMA network. Unlike prior RDMA-based key-value systems, HERD focuses its design on reducing network round trips while using efficient RDMA primitives; the result is substantially lower latency, and throughput that saturates modern, commodity RDMA hardware.

HERD has two unconventional decisions: First, it does not use RDMA reads, despite the allure of operations that bypass the remote CPU entirely. Second, it uses a mix of RDMA and messaging verbs, despite the conventional wisdom that the messaging primitives are slow. A HERD client writes its request into the server's memory; the server computes the reply. This design uses a single round trip for all requests and supports up to 26 million key-value operations per second with 5μs average latency. Notably, for small key-value items, our full system throughput is similar to native RDMA read throughput and is over 2X higher than recent RDMA-based key-value systems. We believe that HERD further serves as an effective template for the construction of RDMA-based datacenter services.
Fastpass
Authors: Perry Jonathan , Ousterhout Amy , Balakrishnan Hari , Shah Devavrat , Fugal Hans
Published: March 2015

An ideal datacenter network should provide several properties, including low median and tail latency, high utilization (throughput), fair allocation of network resources between users or applications, deadline-aware scheduling, and congestion (loss) avoidance. Current datacenter networks inherit the principles that went into the design of the Internet, where packet transmission and path selection decisions are distributed among the endpoints and routers. Instead, we propose that each sender should delegate control---to a centralized arbiter---of when each packet should be transmitted and what path it should follow.

This paper describes Fastpass, a datacenter network architecture built using this principle. Fastpass incorporates two fast algorithms: the first determines the time at which each packet should be transmitted, while the second determines the path to use for that packet. In addition, Fastpass uses an efficient protocol between the endpoints and the arbiter and an arbiter replication strategy for fault-tolerant failover. We deployed and evaluated Fastpass in a portion of Facebook's datacenter network. Our results show that Fastpass achieves high throughput comparable to current networks at a 240x reduction is queue lengths (4.35 Mbytes reducing to 18 Kbytes), achieves much fairer and consistent flow throughputs than the baseline TCP (5200x reduction in the standard deviation of per-flow throughput with five concurrent connections), scalability from 1 to 8 cores in the arbiter implementation with the ability to schedule 2.21 Terabits/s of traffic in software on eight cores, and a 2.5x reduction in the number of TCP retransmissions in a latency-sensitive service at Facebook.
Planck
Authors: Rasley Jeff , Stephens Brent , Dixon Colin , Rozner Eric , Felter Wes , Agarwal Kanak , Carter John , Fonseca Rodrigo
Published: March 2015

Software-defined networking introduces the possibility of building self-tuning networks that constantly monitor network conditions and react rapidly to important events such as congestion. Unfortunately, state-of-the-art monitoring mechanisms for conventional networks require hundreds of milliseconds to seconds to extract global network state, like link utilization or the identity of "elephant" flows. Such latencies are adequate for responding to persistent issues, e.g., link failures or long-lasting congestion, but are inadequate for responding to transient problems, e.g., congestion induced by bursty workloads sharing a link. In this paper, we present Planck, a novel network measurement architecture that employs oversubscribed port mirroring to extract network information at 280 µs--7 ms timescales on a 1 Gbps commodity switch and 275 µs--4 ms timescales on a 10 Gbps commodity switch,over 11x and 18x faster than recent approaches, respectively (and up to 291x if switch firmware allowed buffering to be disabled on some ports). To demonstrate the value of Planck's speed and accuracy, we use it to drive a traffic engineering application that can reroute congested flows in milliseconds. On a 10 Gbps commodity switch, Planck-driven traffic engineering achieves aggregate throughput within 1--4% of optimal for most workloads we evaluated, even with flows as small as 50 MiB, an improvement of up to 53% over previous schemes.
Turbocharging ambient backscatter communication
Authors: Parks Aaron N. , Liu Angli , Gollakota Shyamnath , Smith Joshua R.
Published: March 2015

Communication primitives such as coding and multiple antenna processing have provided significant benefits for traditional wireless systems. Existing designs, however, consume significant power and computational resources, and hence cannot be run on low complexity, power constrained backscatter devices. This paper makes two main contributions: (1) we introduce the first multi-antenna cancellation design that operates on backscatter devices while retaining a small form factor and power footprint, (2) we introduce a novel coding mechanism that enables long range communication as well as concurrent transmissions and can be decoded on backscatter devices. We build hardware prototypes of the above designs that can be powered solely using harvested energy from TV and solar sources. The results show that our designs provide benefits for both RFID and ambient backscatter systems: they enable RFID tags to communicate directly with each other at distances of tens of meters and through multiple walls. They also increase the communication rate and range achieved by ambient backscatter systems by 100X and 40X respectively. We believe that this paper represents a substantial leap in the capabilities of backscatter communication.
OpenNF
Authors: Gember-Jacobson Aaron , Viswanathan Raajay , Prakash Chaithan , Grandl Robert , Khalid Junaid , Das Sourav , Akella Aditya
Published: March 2015

Network functions virtualization (NFV) together with software-defined networking (SDN) has the potential to help operators satisfy tight service level agreements, accurately monitor and manipulate network traffic, and minimize operating expenses. However, in scenarios that require packet processing to be redistributed across a collection of network function (NF) instances, simultaneously achieving all three goals requires a framework that provides efficient, coordinated control of both internal NF state and network forwarding state. To this end, we design a control plane called OpenNF. We use carefully designed APIs and a clever combination of events and forwarding updates to address race conditions, bound overhead, and accommodate a variety of NFs. Our evaluation shows that OpenNF offers efficient state control without compromising flexibility, and requires modest additions to NFs.
CONGA
Authors: Alizadeh Mohammad , Edsall Tom , Dharmapurikar Sarang , Vaidyanathan Ramanan , Chu Kevin , Fingerhut Andy , Lam Vinh The , Matus Francis , Pan Rong , Yadav Navindra , Varghese George
Published: March 2015

We present the design, implementation, and evaluation of CONGA, a network-based distributed congestion-aware load balancing mechanism for datacenters. CONGA exploits recent trends including the use of regular Clos topologies and overlays for network virtualization. It splits TCP flows into flowlets, estimates real-time congestion on fabric paths, and allocates flowlets to paths based on feedback from remote switches. This enables CONGA to efficiently balance load and seamlessly handle asymmetry, without requiring any TCP modifications. CONGA has been implemented in custom ASICs as part of a new datacenter fabric. In testbed experiments, CONGA has 5x better flow completion times than ECMP even with a single link failure and achieves 2-8x better throughput than MPTCP in Incast scenarios. Further, the Price of Anarchy for CONGA is provably small in Leaf-Spine topologies; hence CONGA is nearly as effective as a centralized scheduler while being able to react to congestion in microseconds. Our main thesis is that datacenter fabric load balancing is best done in the network, and requires global schemes such as CONGA to handle asymmetry.
One tunnel is (often) enough
Authors: Peter Simon , Javed Umar , Zhang Qiao , Woos Doug , Anderson Thomas , Krishnamurthy Arvind
Published: March 2015

A longstanding problem with the Internet is that it is vulnerable to outages, black holes, hijacking and denial of service. Although architectural solutions have been proposed to address many of these issues, they have had difficulty being adopted due to the need for widespread adoption before most users would see any benefit. This is especially relevant as the Internet is increasingly used for applications where correct and continuous operation is essential.

In this paper, we study whether a simple, easy to implement model is sufficient for addressing the aforementioned Internet vulnerabilities. Our model, called ARROW (Advertised Reliable Routing Over Waypoints), is designed to allow users to configure reliable and secure end to end paths through participating providers. With ARROW, a highly reliable ISP offers tunneled transit through its network, along with packet transformation at the ingress, as a service to remote paying customers. Those customers can stitch together reliable end to end paths through a combination of participating and non-participating ISPs in order to improve the fault-tolerance, robustness, and security of mission critical transmissions. Unlike efforts to redesign the Internet from scratch, we show that ARROW can address a set of well-known Internet vulnerabilities, for most users, with the adoption of only a single transit ISP. To demonstrate ARROW, we have added it to a small-scale wide-area ISP we control. We evaluate its performance and failure recovery properties in both simulation and live settings.
Wi-fi backscatter
Authors: Kellogg Bryce , Parks Aaron , Gollakota Shyamnath , Smith Joshua R. , Wetherall David
Published: March 2015

RF-powered computers are small devices that compute and communicate using only the power that they harvest from RF signals. While existing technologies have harvested power from ambient RF sources (e.g., TV broadcasts), they require a dedicated gateway (like an RFID reader) for Internet connectivity. We present Wi-Fi Backscatter, a novel communication system that bridges RF-powered devices with the Internet. Specifically, we show that it is possible to reuse existing Wi-Fi infrastructure to provide Internet connectivity to RF-powered devices. To show Wi-Fi Backscatter's feasibility, we build a hardware prototype and demonstrate the first communication link between an RF-powered device and commodity Wi-Fi devices. We use off-the-shelf Wi-Fi devices including Intel Wi-Fi cards, Linksys Routers, and our organization's Wi-Fi infrastructure, and achieve communication rates of up to 1 kbps and ranges of up to 2.1 meters. We believe that this new capability can pave the way for the rapid deployment and adoption of RF-powered devices and achieve ubiquitous connectivity via nearby mobile devices that are Wi-Fi enabled.
An experimental study of the learnability of congestion control
Authors: Sivaraman Anirudh , Winstein Keith , Thaker Pratiksha , Balakrishnan Hari
Published: March 2015

When designing a distributed network protocol, typically it is infeasible to fully define the target network where the protocol is intended to be used. It is therefore natural to ask: How faithfully do protocol designers really need to understand the networks they design for? What are the important signals that endpoints should listen to? How can researchers gain confidence that systems that work well on well-characterized test networks during development will also perform adequately on real networks that are inevitably more complex, or future networks yet to be developed? Is there a tradeoff between the performance of a protocol and the breadth of its intended operating range of networks? What is the cost of playing fairly with cross-traffic that is governed by another protocol?

We examine these questions quantitatively in the context of congestion control, by using an automated protocol-design tool to approximate the best possible congestion-control scheme given imperfect prior knowledge about the network. We found only weak evidence of a tradeoff between operating range in link speeds and performance, even when the operating range was extended to cover a thousand-fold range of link speeds. We found that it may be acceptable to simplify some characteristics of the network---such as its topology---when modeling for design purposes. Some other features, such as the degree of multiplexing and the aggressiveness of contending endpoints, are important to capture in a model.
FastForward
Authors: Bharadia Dinesh , Katti Sachin
Published: March 2015

This paper presents, FastForward (FF), a novel full duplex relay that constructively forwards signals such that wireless network throughput and coverage is significantly enhanced. FF is a Layer 1 in-band full duplex device, it receives and transmits signals directly and simultaneously on the same frequency. It cleanly integrates into existing networks (both WiFi and LTE) as a separate device and does not require changes to the clients. FF's key invention is a constructive filtering algorithm that transforms the signal at the relay such that when it reaches the destination, it constructively combines with the direct signals from the source and provides a significant throughput gain. We prototype FF using off-the-shelf software radios running a stock WiFi PHY and show experimentally that it provides a 3× median throughput increase and nearly a 4× gain at the edge of the coverage area.
A global name service for a highly mobile internetwork
Authors: Sharma Abhigyan , Tie Xiaozheng , Uppal Hardeep , Venkataramani Arun , Westbrook David , Yadav Aditya
Published: March 2015

Mobile devices dominate the Internet today, however the Internet rooted in its tethered origins continues to provide poor infrastructure support for mobility. Our position is that in order to address this problem, a key challenge that must be addressed is the design of a massively scalable global name service that rapidly resolves identities to network locations under high mobility. Our primary contribution is the design, implementation, and evaluation of auspice, a next-generation global name service that addresses this challenge. A key insight underlying auspice is a demand-aware replica {placement engine} that intelligently replicates name records to provide low lookup latency, low update cost, and high availability. We have implemented a prototype of auspice and compared it against several commercial managed DNS providers as well as state-of-the-art research alternatives, and shown that auspice significantly outperforms both. We demonstrate proof-of-concept that auspice can serve as a complete end-to-end mobility solution as well as enable novel context-based communication primitives that generalize name- or address-based communication in today's Internet.
Towards a quantitative comparison of location-independent network architectures
Authors: Gao Zhaoyu , Venkataramani Arun , Kurose James F. , Heimlicher Simon
Published: March 2015

This paper presents a quantitative methodology and results comparing different approaches for {\it location-independent} communication. Our approach is empirical and is based on real Internet topologies, routing tables from real routers, and a measured workload of the mobility of devices and content across network addresses today. We measure the extent of network mobility exhibited by mobile devices with a home-brewn Android app deployed on hundreds of smartphones, and measure the network mobility of Internet content from distributed vantage points. We combine this measured data with our quantitative methodology to analyze the different cost-benefit tradeoffs struck by location-independent network architectures with respect to routing update cost, path stretch, and forwarding table size. We find that more than 20% of users change over 10 IP addresses a day, suggesting that mobility is the norm rather than the exception, so intrinsic and efficient network support for mobility is critical. We also find that with purely name-based routing approaches, each event involving the mobility of a device or popular content may result in an update at up to 14% of Internet routers; but, the fraction of impacted routers is much smaller for the long tail of unpopular content. These results suggest that recent proposals for pure name-based networking are suitable for highly aggregateable content that does not move frequently but may need to be augmented with addressing-assisted approaches to handle device mobility.
Multi-resource packing for cluster schedulers
Authors: Grandl Robert , Ananthanarayanan Ganesh , Kandula Srikanth , Rao Sriram , Akella Aditya
Published: March 2015

Tasks in modern data parallel clusters have highly diverse resource requirements, along CPU, memory, disk and network. Any of these resources may become bottlenecks and hence, the likelihood of wasting resources due to fragmentation is now larger. Today's schedulers do not explicitly reduce fragmentation. Worse, since they only allocate cores and memory, the resources that they ignore (disk and network) can be over-allocated leading to interference, failures and hogging of cores or memory that could have been used by other tasks. We present Tetris, a cluster scheduler that packs, i.e., matches multi-resource task requirements with resource availabilities of machines so as to increase cluster efficiency (makespan). Further, Tetris uses an analog of shortest-running-time-first to trade-off cluster efficiency for speeding up individual jobs. Tetris' packing heuristics seamlessly work alongside a large class of fairness policies. Trace-driven simulations and deployment of our prototype on a 250 node cluster shows median gains of 30% in job completion time while achieving nearly perfect fairness.
Calendaring for wide area networks
Authors: Kandula Srikanth , Menache Ishai , Schwartz Roy , Babbula Spandana Raj
Published: March 2015

Datacenter WAN traffic consists of high priority transfers that have to be carried as soon as they arrive alongside large transfers with pre-assigned deadlines on their completion (ranging from minutes to hours). The ability to offer guarantees to large transfers is crucial for business needs and impacts overall cost-of-business. State-of-the-art traffic engineering solutions only consider the current time epoch and hence cannot provide pre-facto promises for long-lived transfers. We present Tempus, an online traffic engineering scheme that exploits information on transfer size and deadlines to appropriately pack long-running transfers across network paths and time, thereby leaving enough capacity slack for future high-priority requests. Tempus builds on a tailored approximate solution to a mixed packing-covering linear program, which is parallelizable and scales well in both running time and memory usage. Consequently, Tempus is able to quickly and effectively update its solution when new transfers arrive or unexpected changes happen. These updates involve only small edits to existing transfers. Therefore, as experiments on traces from a large production WAN show, Tempus can offer and keep promises to long-lived transfers well in advance of their actual deadline; the promise on minimal transfer size is comparable with an offline optimal solution and outperforms state-of-the-art solutions by 2-3X.
Accelerating incast and multicast traffic delivery for data-intensive applications using physical layer optics
Authors: Samadi Payman , Gupta Varun , Birand Berk , Wang Howard , Zussman Gil , Bergman Keren
Published: March 2015

We present a control plane architecture to accelerate multicast and incast traffic delivery for data-intensive applications in cluster-computing interconnection networks. The architecture is experimentally examined by enabling physical layer optical multicasting on-demand for the application layer to achieve non-blocking performance.
T-DNS
Authors: Zhu Liang , Hu Zi , Heidemann John , Wessels Duane , Mankin Allison , Somaiya Nikita
Published: March 2015

DNS is the canonical protocol for connectionless UDP. Yet DNS today is challenged by eavesdropping that compromises privacy, source-address spoofing that results in denial-of-service (DoS) attacks on the server and third parties, injection attacks that exploit fragmentation, and size limitations that constrain policy and operational choices. We propose T-DNS to address these problems. It uses TCP to smoothly support large payloads and to mitigate spoofing and amplification for DoS. T-DNS uses transport-layer security (TLS) to provide privacy from users to their DNS resolvers and optionally to authoritative servers. Our model shows end-to-end latency from TLS to the recursive resolver is only about 9% slower when UDP is used to the authoritative server, and 22% slower with TCP to the authoritative. With diverse traces we show that frequent connection reuse is possible (60-95% for stub and recursive resolvers, although half that for authoritative servers). Our experiment shows that after connection establishment, TCP and TLS latency is equivalent to UDP. With conservative timeouts (20 s at authoritative servers and 60 s elsewhere) and conservative estimates of connection state memory requirements, we show that server memory requirements well within current, commodity server hardware. We identify the key design and implementation decisions needed to minimize overhead: query pipelining, out-of-order responses, TLS connection resumption, and plausible timeouts. This poster abstract summarizes work we describe in detail in ISI-TR-2014-693.
OpenSAN
Authors: Bao Jinzhen , Zhao Baokang , Yu Wanrong , Feng Zhenqian , Wu Chunqing , Gong Zhenghu
Published: March 2015

In recent years, with the rapid development of satellite technology including On Board Processing (OBP) and Inter Satellite Link (ISL), satellite network devices such as space IP routers have been experimentally carried in space. However, there are many difficulties to build a future satellite network with current terrestrial Internet technologies due to the distinguished space features, such as the severely limited resources, remote hardware/software upgrade in space. In this paper, we propose OpenSAN, a novel architecture of software-defined satellite network. By decoupling the data plane and control plane, OpenSAN provides satellite network with high efficiency, fine-grained control, as well as flexibility to support future advanced network technology. Moreover, we also discuss some practical challenges in the deployment of OpenSAN.
Mahimahi
Authors: Netravali Ravi , Sivaraman Anirudh , Winstein Keith , Das Somak , Goyal Ameesh , Balakrishnan Hari
Published: March 2015

This demo presents a measurement toolkit, Mahimahi, that records websites and replays them under emulated network conditions. Mahimahi is structured as a set of arbitrarily composable UNIX shells. It includes two shells to record and replay Web pages, RecordShell and ReplayShell, as well as two shells for network emulation, DelayShell and LinkShell. In addition, Mahimahi includes a corpus of recorded websites along with benchmark results and link traces (https://github.com/ravinet/sites).

Mahimahi improves on prior record-and-replay frameworks in three ways. First, it preserves the multi-origin nature of Web pages, present in approximately 98% of the Alexa U.S. Top 500, when replaying. Second, Mahimahi isolates its own network traffic, allowing multiple instances to run concurrently with no impact on the host machine and collected measurements. Finally, Mahimahi is not inherently tied to browsers and can be used to evaluate many different applications.

A demo of Mahimahi recording and replaying a Web page over an emulated link can be found at http://youtu.be/vytwDKBA-8s. The source code and instructions to use Mahimahi are available at http://mahimahi.mit.edu/.
SENSS
Authors: Alwabel Abdulla , Yu Minlan , Zhang Ying , Mirkovic Jelena
Published: March 2015

We propose a new software-defined security service -- SENSS -- that enables a victim network to request services from remote ISPs for traffic that carries source IPs or destination IPs from this network's address space. These services range from statistics gathering, to filtering or quality of service guarantees, to route reports or modifications. The SENSS service has very simple, yet powerful, interfaces. This enables it to handle a variety of data plane and control plane attacks, while being easily implementable in today's ISP. Through extensive evaluations on realistic traffic traces and Internet topology, we show how SENSS can be used to quickly, safely and effectively mitigate a variety of large-scale attacks that are largely unhandled today.
A cliq of content curators
Authors: Jiang Angela H. , Bischof Zachary S. , Bustamante Fabian E.
Published: March 2015

A social news site presents user-curated content, ranked by popularity. Popular curators like Reddit, or Facebook have become effective way of crowdsourcing news or sharing for personal opinions. Traditionally, these services require a centralized authority to aggregate data and determine what to display. However, the trust issues that arise from a centralized system are particularly damaging to the "Web democracy" that social news sites are meant to provide. In this poster, we present cliq, a decentralized social news curator. cliq is a P2P based social news curator that provides private and unbiased reporting. All users in cliq share responsibility for tracking and providing popular content. Any user data that cliq needs to store is also managed across the network. We first inform our design of cliq through an analysis of Reddit. We design a way to provide content curation without a persistent moderator, or usernames.