bluuebunny/crossref_metadata_2025 huggingface dataset:
STABILIZER
Authors: Curtsinger Charlie , Berger Emery D.
Published: April 2020

Researchers and software developers require effective performance evaluation. Researchers must evaluate optimizations or measure overhead. Software developers use automatic performance regression tests to discover when changes improve or degrade performance. The standard methodology is to compare execution times before and after applying changes.

Unfortunately, modern architectural features make this approach unsound. Statistically sound evaluation requires multiple samples to test whether one can or cannot (with high confidence) reject the null hypothesis that results are the same before and after. However, caches and branch predictors make performance dependent on machine-specific parameters and the exact layout of code, stack frames, and heap objects. A single binary constitutes just one sample from the space of program layouts, regardless of the number of runs. Since compiler optimizations and code changes also alter layout, it is currently impossible to distinguish the impact of an optimization from that of its layout effects.

This paper presents Stabilizer, a system that enables the use of the powerful statistical techniques required for sound performance evaluation on modern architectures. Stabilizer forces executions to sample the space of memory configurations by repeatedly re-randomizing layouts of code, stack, and heap objects at runtime. Stabilizer thus makes it possible to control for layout effects. Re-randomization also ensures that layout effects follow a Gaussian distribution, enabling the use of statistical tests like ANOVA. We demonstrate Stabilizer's efficiency (<7% median overhead) and its effectiveness by evaluating the impact of LLVM's optimizations on the SPEC CPU2006 benchmark suite. We find that, while -O2 has a significant impact relative to -O1, the performance impact of -O3 over -O2 optimizations is indistinguishable from random noise.
A study of the scalability of stop-the-world garbage collectors on multicores
Authors: Gidra Lokesh , Thomas Gaël , Sopena Julien , Shapiro Marc
Published: April 2020

Large-scale multicore architectures create new challenges for garbage collectors (GCs). In particular, throughput-oriented stop-the-world algorithms demonstrate good performance with a small number of cores, but have been shown to degrade badly beyond approximately 8 cores on a 48-core with OpenJDK 7. This negative result raises the question whether the stop-the-world design has intrinsic limitations that would require a radically different approach. Our study suggests that the answer is no, and that there is no compelling scalability reason to discard the existing highly-optimised throughput-oriented GC code on contemporary hardware. This paper studies the default throughput-oriented garbage collector of OpenJDK 7, called Parallel Scavenge. We identify its bottlenecks, and show how to eliminate them using well-established parallel programming techniques. On the SPECjbb2005, SPECjvm2008 and DaCapo 9.12 benchmarks, the improved GC matches the performance of Parallel Scavenge at low core count, but scales well, up to 48~cores.
Iago attacks
Authors: Checkoway Stephen , Shacham Hovav
Published: April 2020

In recent years, researchers have proposed systems for running trusted code on an untrusted operating system. Protection mechanisms deployed by such systems keep a malicious kernel from directly manipulating a trusted application's state. Under such systems, the application and kernel are, conceptually, peers, and the system call API defines an RPC interface between them.

We introduce
Iago attacks
, attacks that a malicious kernel can mount in this model. We show how a carefully chosen sequence of integer return values to Linux system calls can lead a supposedly protected process to act against its interests, and even to undertake arbitrary computation at the malicious kernel's behest.

Iago attacks are evidence that protecting applications from malicious kernels is more difficult than previously realized.
Safe and automatic live update for operating systems
Authors: Giuffrida Cristiano , Kuijsten Anton , Tanenbaum Andrew S.
Published: April 2020

Increasingly many systems have to run all the time with no downtime allowed. Consider, for example, systems controlling electric power plants and e-banking servers. Nevertheless, security patches and a constant stream of new operating system versions need to be deployed without stopping running programs. These factors naturally lead to a pressing demand for live update---upgrading all or parts of the operating system without rebooting. Unfortunately, existing solutions require significant manual intervention and thus work reliably only for small operating system patches.

In this paper, we describe an automated system for live update that can safely and automatically handle major upgrades without rebooting. We have implemented our ideas in Proteos, a new research OS designed with live update in mind. Proteos relies on system support and nonintrusive instrumentation to handle even very complex updates with minimal manual effort. The key novelty is the idea of
state quiescence
, which allows updates to happen only in safe and predictable system states. A second novelty is the ability to automatically perform transactional live updates at the
process level
, ensuring a safe and
stable
update process. Unlike prior solutions, Proteos supports automated state transfer, state checking, and
hot rollback
. We have evaluated Proteos on 50 real updates and on novel live update scenarios. The results show that our techniques can effectively support both simple and complex updates, while outperforming prior solutions in terms of flexibility, security, reliability, and stability of the update process.
Verifying security invariants in ExpressOS
Authors: Mai Haohui , Pek Edgar , Xue Hui , King Samuel Talmadge , Madhusudan Parthasarathy
Published: April 2020

Security for applications running on mobile devices is important. In this paper we present ExpressOS, a new OS for enabling high-assurance applications to run on commodity mobile devices securely. Our main contributions are a new OS architecture and our use of formal methods for proving key security invariants about our implementation. In our use of formal methods, we focus solely on proving that our OS implements our security invariants correctly, rather than striving for full functional correctness, requiring significantly less verification effort while still proving the security relevant aspects of our system.

We built ExpressOS, analyzed its security, and tested its performance. Our evaluation shows that the performance of ExpressOS is comparable to an Android-based system. In one test, we ran the same web browser on ExpressOS and on an Android-based system, and found that ExpressOS adds 16% overhead on average to the page load latency time for nine popular web sites.
Stochastic superoptimization
Authors: Schkufza Eric , Sharma Rahul , Aiken Alex
Published: April 2020

We formulate the loop-free binary superoptimization task as a stochastic search problem. The competing constraints of transformation correctness and performance improvement are encoded as terms in a cost function, and a Markov Chain Monte Carlo sampler is used to rapidly explore the space of all possible programs to find one that is an optimization of a given target program. Although our method sacrifices completeness, the scope of programs we are able to consider, and the resulting quality of the programs that we produce, far exceed those of existing superoptimizers. Beginning from binaries compiled by llvm -O0 for 64-bit x86, our prototype implementation, STOKE, is able to produce programs which either match or outperform the code produced by gcc -O3, icc -O3, and in some cases, expert handwritten assembly.
Traffic management
Authors: Dashti Mohammad , Fedorova Alexandra , Funston Justin , Gaud Fabien , Lachaize Renaud , Lepers Baptiste , Quema Vivien , Roth Mark
Published: April 2020

NUMA systems are characterized by Non-Uniform Memory Access times, where accessing data in a remote node takes longer than a local access. NUMA hardware has been built since the late 80's, and the operating systems designed for it were optimized for access locality. They co-located memory pages with the threads that accessed them, so as to avoid the cost of remote accesses. Contrary to older systems, modern NUMA hardware has much smaller remote wire delays, and so remote access costs per se are not the main concern for performance, as we discovered in this work. Instead,
congestion on memory controllers and interconnects
, caused by memory traffic from data-intensive applications, hurts performance a lot more. Because of that, memory placement algorithms must be redesigned to target traffic congestion. This requires an arsenal of techniques that go beyond optimizing locality. In this paper we describe
Carrefour
, an algorithm that addresses this goal. We implemented
Carrefour
in Linux and obtained performance improvements of up to 3.6 relative to the default kernel, as well as significant improvements compared to NUMA-aware patchsets available for Linux.
Carrefour
never hurts performance by more than 4% when memory placement cannot be improved. We present the design of
Carrefour
, the challenges of implementing it on modern hardware, and draw insights about hardware support that would help optimize system software on future NUMA systems.
Efficient virtualization on embedded power architecture® platforms
Authors: Mittal Aashish , Bansal Dushyant , Bansal Sorav , Sethi Varun
Published: April 2020

Power Architecture® processors are popular and widespread on embedded systems, and such platforms are increasingly being used to run virtual machines. While the Power Architecture meets the Popek-and-Goldberg virtualization requirements for traditional trap-and-emulate style virtualization, the performance overhead of virtualization remains high. For example, workloads exhibiting a large amount of kernel activity typically show 3-5x slowdowns over bare-metal.

Recent additions to the Linux kernel contain guest and host side paravirtual extensions for Power Architecture platforms. While these extensions improve performance significantly, they are guest-specific, guest-intrusive, and cover only a subset of all possible virtualization optimizations.

We present a set of host-side optimizations that achieve comparable performance to the aforementioned paravirtual extensions, on an unmodified guest. Our optimizations are based on adaptive in-place binary translation. Unlike the paravirtual approach, our solution is guest neutral. We implement our ideas in a prototype based on Qemu/KVM. After our modifications, KVM can boot an unmodified Linux guest around 2.5x faster. We contrast our optimization approach with previous similar binary translation based approaches for the x86 architecture; in our experience, each architecture presents a unique set of challenges and optimization opportunities.
Research directions for 21st century computer systems
Authors: Hill Mark D.
Published: April 2020

Four recent efforts call out architectural challenges and opportunities up and down the software/hardware stack. This panel will discuss,
"What should the community do to facilitate, transcend, or refute these partially overlapping visions?"
The panel is chaired by Mark D. Hill with other panel members not finalized for the ASPLOS'13 proceedings.
Fine-grained fault tolerance using device checkpoints
Authors: Kadav Asim , Renzelmann Matthew J. , Swift Michael M.
Published: April 2020

Recovering faults in drivers is difficult compared to other code because their state is spread across both memory and a device. Existing driver fault-tolerance mechanisms either restart the driver and discard its state, which can break applications, or require an extensive logging mechanism to replay requests and recreate driver state. Even logging may be insufficient, though, if the semantics of requests are ambiguous. In addition, these systems either require large subsystems that must be kept up-to-date as the kernel changes, or require substantial rewriting of drivers.

We present a new driver fault-tolerance mechanism that provides fine-grained control over the code protected. Fine-Grained Fault Tolerance (FGFT) isolates driver code at the granularity of a single entry point. It executes driver code as a transaction, allowing roll back if the driver fails. We develop a novel checkpointing mechanism to save and restore device state using existing power management code. Unlike past systems, FGFT can be incrementally deployed in a single driver without the need for a large kernel subsystem, but at the cost of small modifications to the driver.

In the evaluation, we show that FGFT can have almost zero runtime cost in many cases, and that checkpoint-based recovery can reduce the duration of a failure by 79% compared to restarting the driver. Finally, we show that applying FGFT to a driver requires little effort, and the majority of drivers in common classes already contain the power-management code needed for checkpoint/restore.
GPUfs
Authors: Silberstein Mark , Ford Bryan , Keidar Idit , Witchel Emmett
Published: April 2020

PU hardware is becoming increasingly general purpose, quickly outgrowing the traditional but constrained GPU-as-coprocessor programming model. To make GPUs easier to program and easier to integrate with existing systems, we propose making the host's file system directly accessible from GPU code. GPUfs provides a POSIX-like API for GPU programs, exploits GPU parallelism for efficiency, and optimizes GPU file access by extending the buffer cache into GPU memory. Our experiments, based on a set of real benchmarks adopted to use our file system, demonstrate the feasibility and benefits of our approach. For example, we demonstrate a simple self-contained GPU program which searches for a set of strings in the entire tree of Linux kernel source files over seven times faster than an eight-core CPU run.
Wait-n-GoTM
Authors: Jafri Syed Ali Raza , Voskuilen Gwendolyn , Vijaykumar T. N.
Published: April 2020

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware TMs (HTMs) use one of three conflict-resolution policies: (1)
always-abort,
(2)
always-wait
for some conflicting transactions to complete, or (3)
always-go
past conflicts and resolve acyclic conflicts at commit or abort upon cyclic dependencies. While each policy has advantages, the policies degrade performance under contention by limiting concurrency (always-abort, always-wait) or incurring late aborts due to cyclic dependencies (always-go). Thus, while always-go avoids acyclic aborts, no policy avoids cyclic aborts. We propose
Wait-n-GoTM (WnGTM)
to increase concurrency while avoiding cyclic aborts. We observe that most cyclic dependencies are caused by threads interleaving multiple accesses to a few heavily-read-write-shared delinquent data cache blocks. These accesses occur in code sections called
cycle inducer sections (CISTs)
. Accordingly, we propose
Wait-n-Go (WnG)
conflict-resolution to avoid many cyclic aborts by predicting and serializing the CISTs. To support the WnG policy, we extend previous HTMs to (1) allow multiple readers and writers, (2) scalably identify dependencies, and (3) detect cyclic dependencies via new mechanisms, namely, conflict transactional state, order-capture, and hardware timestamps, respectively. In 16-core simulations of STAMP, WnGTM achieves average speedups of 46% for higher-contention benchmarks and 28% for all benchmarks over always-abort (TokenTM) with low-contention benchmarks remaining unchanged, compared to always-go (DATM) and always-wait (LogTM-SE), which perform worse than and 6% better than TokenTM, respectively.
Volition
Authors: Qian Xuehai , Torrellas Josep , Sahelices Benjamin , Qian Depei
Published: April 2020

Sequential Consistency (SC) is the most intuitive memory model, and SC Violations (SCVs) produce unintuitive, typically incorrect executions. Most prior SCV detection schemes have used data races as proxies for SCVs, which is highly imprecise. Other schemes that have targeted data-race cycles are either too conservative or are designed only for two-processor cycles and snoopy-based systems.

This paper presents Volition, the first hardware scheme that detects SCVs in a relaxed-consistency machine precisely, in a scalable manner, and for an arbitrary number of processors in the cycle. Volition leverages cache coherence protocol transactions to dynamically detect cycles in memory-access orders across threads. When a cycle is about to occur, an exception is triggered. Volition can be used in both directory- and snoopy-based coherence protocols. Our simulations of Volition in a 64-processor multicore with directory-based coherence running SPLASH-2 and Parsec programs shows that Volition induces negligible traffic and execution overhead. In addition, it can detect SCVs with several processors. Volition is suitable for on-the-fly use.
Exploring the Tradeoffs between Programmability and Efficiency in Data-Parallel Accelerators
Authors: Lee Yunsup , Avizienis Rimas , Bishara Alex , Xia Richard , Lockhart Derek , Batten Christopher , Asanović Krste
Published: April 2020

We present a taxonomy and modular implementation approach for data-parallel accelerators, including the MIMD, vector-SIMD, subword-SIMD, SIMT, and vector-thread (VT) architectural design patterns. We introduce Maven, a new VT microarchitecture based on the traditional vector-SIMD microarchitecture, that is considerably simpler to implement and easier to program than previous VT designs. Using an extensive design-space exploration of full VLSI implementations of many accelerator design points, we evaluate the varying tradeoffs between programmability and implementation efficiency among the MIMD, vector-SIMD, and VT patterns on a workload of compiled microbenchmarks and application kernels. We find the vector cores provide greater efficiency than the MIMD cores, even on fairly irregular kernels. Our results suggest that the Maven VT microarchitecture is superior to the traditional vector-SIMD architecture, providing both greater efficiency and easier programmability.
Efficient control of epidemics over random networks
Authors: Lelarge Marc
Published: April 2020

Motivated by the modeling of the spread of viruses or epidemics with coordination among agents, we introduce a new model generalizing both the basic contact model and the bootstrap percolation. We analyze this percolated threshold model when the underlying network is a random graph with fixed degree distribution. Our main results unify many results in the random graphs literature. In particular, we provide a necessary and sufficient condition under which a single node can trigger a large cascade. Then we quantify the possible impact of an attacker against a degree based vaccination and an acquaintance vaccination. We define a security metric allowing to compare the different vaccinations. The acquaintance vaccination requires no knowledge of the node degrees or any other global information and is shown to be much more efficient than the uniform vaccination in all cases.
Botnet spam campaigns can be long lasting
Authors: Pathak Abhinav , Qian Feng , Hu Y. Charlie , Mao Z. Morley , Ranjan Supranamaya
Published: April 2020

Accurately identifying spam campaigns launched by a large number of bots in a botnet allows for accurate spam campaign signature generation and hence is critical to defeating spamming botnets. The straight-forward approach of clustering all spam containing the same label such as an URL into a campaign can be easily defeated by techniques such as simple obfuscations of URLs. In this paper, we perform a comprehensive study of content-agnostic characteristics of spam campaigns,
e.g.
duration and source-network distribution of spammers, in order to ascertain whether and how they can assist the simple label-based clustering methods in identifying campaigns and generating campaign signatures. In particular, from a five-month trace collected by a relay sinkhole, we manually identified and then analyzed seven URL-based botnet spam campaigns consisting of 52 million spam messages sent over 2.09 million SMTP connections originated from over 150,000 non-proxy spamming hosts and destined to about 200,000 end domains. Our analysis shows that the spam campaigns, when observed from large destination domains, exhibit durations far longer than the five-day period as reported in a recent study. We analyze the implications of this finding on spam campaign signature generation. We further study other characteristics of these long-lasting campaigns. Our analysis reveals several new findings regarding workload distribution, sending patterns, and coordination among the spamming machines.
Unveiling core network-wide communication patterns through application traffic activity graph decomposition
Authors: Jin Yu , Sharafuddin Esam , Zhang Zhi-Li
Published: April 2020

As Internet communications and applications become more complex,operating, managing and securing networks have become increasingly challenging tasks. There are urgent demands for more sophisticated techniques for understanding and analyzing the behavioral characteristics of network traffic. In this paper, we study the network traffic behaviors using traffic activity graphs (TAGs), which capture the interactions among hosts engaging in certain types of communications and their collective behavior. TAGs derived from real network traffic are large, sparse, yet seemingly complex and richly connected, therefore difficult to visualize and comprehend. In order to analyze and characterize these TAGs, we propose a novel statistical traffic graph decomposition technique based on orthogonal nonnegative matrix tri-factorization (tNMF) to decompose and extract the core host interaction patterns and other structural properties. Using the real network traffic traces, we demonstrate that our tNMF-based graph decomposition technique produces meaningful and interpretable results. It enables us to characterize and quantify the key structural properties of large and sparse TAGs associated with various applications, and study their formation and evolution.
Topological transformation approaches to optimizing TCAM-based packet classification systems
Authors: Meiners Chad R. , Liu Alex X. , Torng Eric
Published: April 2020

Several range reencoding schemes have been proposed to mitigate the effect of range expansion and the limitations of small capacity, large power consumption, and high heat generation of TCAM-based packet classification systems. However, they all disregard the semantics of classifiers and therefore miss significant opportunities for space compression.

In this paper, we propose new approaches to range reencoding by taking into account classifier semantics. Fundamentally different from prior work, we view reencoding as a topological transformation process from one colored hyperrectangle to another where the color is the decision associated with a given packet. We present two orthogonal, yet composable, reencoding approaches, domain compression and prefix alignment. Our techniques significantly outperform all previous reencoding techniques. In comparison with the state-of-the-art results, our experimental results show that our techniques achieve at least 7 times more space reduction in terms of TCAM space for an encoded classifier and at least 3 times more space reduction in terms of TCAM space for a reencoded classifier and its transformers.
The age of gossip
Authors: Chaintreau Augustin , Le Boudec Jean-Yves , Ristanovic Nikodin
Published: April 2020

Disseminating a piece of information, or updates for a piece of information, has been shown to benefit greatly from simple randomized procedures, sometimes referred to as gossiping, or epidemic algorithms. Similarly, in a network where mobile nodes occasionally receive updated content from a base station, gossiping using opportunistic contacts allows for recent updates to be efficiently maintained, for a large number of nodes. In this case, however, gossiping depends on node mobility. For this reason, we introduce a new gossip model, with mobile nodes moving between different
classes
that can represent locations or states, which determine gossiping behavior of the nodes. Here we prove that, when the number of mobile nodes becomes large, the age of the latest updates received by mobile nodes approaches a deterministic mean-field regime. More precisely, we show that the occupancy measure of the process constructed, with the ages defined above, converges to a deterministic limit that can be entirely characterized by differential equations. This major simplification allows us to characterize how mobility, source inputs and gossiping influence the age distribution for low and high ages. It also leads to a scalable numerical evaluation of the performance of mobile update systems, which we validate (using a trace of 500 taxicabs) and use to propose infrastructure deployment.
Scheduling in multi-channel wireless networks
Authors: Bodas Shreeshankar , Shakkottai Sanjay , Ying Lei , Srikant R.
Published: April 2020

We consider the problem of designing scheduling algorithms for the downlink of cellular wireless networks where bandwidth is partitioned into tens to hundreds of parallel channels, each of which can be allocated to a possibly different user in each time slot. We prove that a class of algorithms called Iterated Longest Queues First (iLQF) algorithms achieves the smallest buffer overflow probability in an appropriate large deviations sense. The class of iLQF algorithms is quite different from the class of max-weight policies which have been studied extensively in the literature, and it achieves much better performance in the regimes studied in this paper.
Network adiabatic theorem
Authors: Rajagopalan Shreevatsa , Shah Devavrat , Shin Jinwoo
Published: April 2020

The popularity ofAloha-like algorithms for resolution of contention between multiple entities accessing common resources is due to their extreme simplicity and distributed nature. Example applications of such algorithms include Ethernet and recently emerging wireless multi-access networks. Despite a long and exciting history of more than four decades, the question of designing an algorithm that isessentiallyas simple and distributed as Aloha while being efficient has remained unresolved.

In this paper, we resolve this question successfully for a network of queues where contention is modeled through independent-set constraints over the network graph. The work by Tassiulas and Ephremides (1992) suggests that an algorithm that schedules queues so that the summation of `weight' of scheduled queues is maximized, subject to constraints, is efficient. However, implementing such an algorithm using Aloha-like mechanism has remained a mystery. We design such an algorithm building upon a Metropolis-Hastings sampling mechanism along with selection of `weight' as an appropriate function of the queue-size. The key ingredient in establishing the efficiency of the algorithm is a noveladiabatic-like theorem for the underlying queueing network, which may be of general interest in the context of dynamical systems.
Optimal power allocation in server farms
Authors: Gandhi Anshul , Harchol-Balter Mor , Das Rajarshi , Lefurgy Charles
Published: April 2020

Server farms today consume more than 1.5% of the total electricity in the U.S. at a cost of nearly $4.5 billion. Given the rising cost of energy, many industries are now seeking solutions for how to best make use of their available power. An important question which arises in this context is how to distribute available power among servers in a server farm so as to get maximum performance.

By giving more power to a server, one can get higher server frequency (speed). Hence it is commonly believed that, for a given power budget, performance can be maximized by operating servers at their highest power levels. However, it is also conceivable that one might prefer to run servers at their lowest power levels, which allows more servers to be turned on for a given power budget. To fully understand the effect of power allocation on performance in a server farm with a fixed power budget, we introduce a queueing theoretic model, which allows us to predict the optimal power allocation in a variety of scenarios. Results are verified via extensive experiments on an IBM BladeCenter.

We find that the optimal power allocation varies for different scenarios. In particular, it is not always optimal to run servers at their maximum power levels. There are scenarios where it might be optimal to run servers at their lowest power levels or at some intermediate power levels. Our analysis shows that the optimal power allocation is non-obvious and depends on many factors such as the power-to-frequency relationship in the processors, the arrival rate of jobs, the maximum server frequency, the lowest attainable server frequency and the server farm configuration. Furthermore, our theoretical model allows us to explore more general settings than we can implement, including arbitrarily large server farms and different power-to-frequency curves. Importantly, we show that the optimal power allocation can significantly improve server farm performance, by a factor of typically 1.4 and as much as a factor of 5 in some cases.
Restrained utilization of idleness for transparent scheduling of background tasks
Authors: Mi Ningfang , Riska Alma , Li Xin , Smirni Evgenia , Riedel Erik
Published: April 2020

A common practice in system design is to treat features intended to enhance performance and reliability as low priority tasks by scheduling them during idle periods, with the goal to keep these features transparent to the user. In this paper, we present an algorithmic framework that determines the schedulability of non-preemptable low priority tasks in storage systems. The framework estimates
when
and
for how long
idle times can be utilized by low priority background tasks, without violating pre-defined performance targets of user foreground tasks. The estimation is based on monitored system information that includes the histogram of idle times. This histogram captures accurately important statistical characteristics of the complex demands of the foreground activity. The robustness and the effectiveness of the proposed framework is corroborated via extensive trace driven simulations under a wide range of system conditions and background activities, and via experimentation on a Linux kernel 2.6.22 prototype.
Neighbor-specific BGP
Authors: Wang Yi , Schapira Michael , Rexford Jennifer
Published: April 2020

The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to protocol oscillation. The best-known sufficient conditions of BGP global routing stability impose restrictions on the kinds of local routing policies individual ASes can safely implement. In this paper, we present
neighbor-specific BGP
(NS-BGP), a modest extension to BGP that enables a much wider range of local policies without compromising global stability. Whereas a conventional BGP-speaking router selects a single "best" route (for each destination prefix), NS-BGP allows a router to customize the route selection on behalf of each neighbor. For example, one neighbor may prefer the shortest route, another the most secure route, and yet another the least expensive route. Surprisingly, we prove that the much more flexible NS-BGP is guaranteed to be stable under much less restrictive conditions on how routers "rank" the candidate routes. We also show that it is safe to deploy NS-BGP incrementally, as a routing system with a partial deployment of NS-BGP is guaranteed to be stable, even in the presence of failure and other topology changes. In addition to our theoretical results, we also describe how NS-BGP can be deployed by individual ASes independently without changes to the BGP message format or collaboration from neighboring ASes.
Delay tolerant bulk data transfers on the internet
Authors: Laoutaris Nikolaos , Smaragdakis Georgios , Rodriguez Pablo , Sundaram Ravi
Published: April 2020

Many emerging scientific and industrial applications require transferring multiple Tbytes of data on a daily basis. Examples include pushing scientific data from particle accelerators/colliders to laboratories around the world, synchronizing data-centers across continents, and replicating collections of high definition videos from events taking place at different time-zones. A key property of all above applications is their ability to tolerate delivery delays ranging from a few hours to a few days. Such
Delay Tolerant Bulk
(DTB) data are currently being serviced mostly by the postal system using hard drives and DVDs, or by expensive dedicated networks. In this work we propose transmitting such data through commercial ISPs by taking advantage of already-paid-for off-peak bandwidth resulting from diurnal traffic patterns and percentile pricing. We show that between sender-receiver pairs with small time-zone difference, simple source scheduling policies are able to take advantage of most of the existing off-peak capacity. When the time-zone difference increases, taking advantage of the full capacity requires performing store-and-forward through intermediate storage nodes. We present an extensive evaluation of the two options based on traffic data from 200+ links of a large transit provider with PoPs at three continents. Our results indicate that there exists huge potential for performing multi Tbyte transfers on a daily basis at little or no additional cost.
Leveraging discarded samples for tighter estimation of multiple-set aggregates
Authors: Cohen Edith , Kaplan Haim
Published: April 2020

Many datasets, including market basket data, text or hypertext documents, and events recorded in different locations or time periods, can be modeled as a collection of sets over a ground set of keys. Common queries over such data, including similarity or association rules are represented as the weight or selectivity of keys that satisfy some selection predicate defined over keys' attributes and memberships in particular sets.

On massive data sets, exact computation of such aggregates can be inefficient or infeasible, and therefore, approximate queries are processed over sketches of the sets. Sketches based on coordinated random samples are scalable and flexible and well suited for many applications. Queries are resolved by producing a sketch of the union of sets used in the predicate from the sketches of these sets and then applying an estimator to this union-sketch.

We derive novel tighter (unbiased) estimators that leverage sampled keys that are present in the union of applicable sketches but excluded from the union sketch. We establish analytically that our estimators dominate estimators applied to the union-sketch for
all queries and data sets
. Empirical evaluation on synthetic and real data reveals that on typical applications we can expect a 25% 4 fold reduction in estimation error.
Maximum likelihood estimation of the flow size distribution tail index from sampled packet data
Authors: Loiseau Patrick , Gonçalves Paulo , Girard Stéphane , Forbes Florence , Vicat-Blanc Primet Pascale
Published: April 2020

In the context of network traffic analysis, we address the problem of estimating the tail index of flow (or more generally of any group) size distribution from the observation of a sampled population of packets (individuals). We give an exhaustive bibliography of the existing methods and show the relations between them. The main contribution of this work is then to propose a new method to estimate the tail index from sampled data, based on the resolution of the maximum likelihood problem. To assess the performance of our method, we present a full performance evaluation based on numerical simulations, and also on a real traffic trace corresponding to internet traffic recently acquired.
Modeling channel popularity dynamics in a large IPTV system
Authors: Qiu Tongqing , Ge Zihui , Lee Seungjoon , Wang Jia , Zhao Qi , Xu Jun
Published: April 2020

Understanding the channel popularity or content popularity is an important step in the workload characterization for modern information distribution systems (e.g., World Wide Web, peer-to-peer file-sharing systems, video-on-demand systems).

In this paper, we focus on analyzing the channel popularity in the context of Internet Protocol Television (IPTV). In particular, we aim at capturing two important aspects of channel popularity - the distribution and temporal dynamics of the channel popularity. We conduct in-depth analysis on channel popularity on a large collection of user channel access data from a nation-wide commercial IPTV network. Based on the findings in our analysis, we choose a stochastic model that finds good matches in all attributes of interest with respect to the channel popularity. Furthermore, we propose a method to identify subsets of user population with inherently different channel interest.

By tracking the change of population mixtures among different user classes, we extend our model to a multi-class population model, which enables us to capture the moderate diurnal popularity patterns exhibited in some channels. We also validate our channel popularity model using real user channel access data from commercial IPTV network.
Surprising results on task assignment in server farms with high-variability workloads
Authors: Harchol-Balter Mor , Scheller-Wolf Alan , Young Andrew R.
Published: April 2020

This paper investigates the performance of task assignment policies for server farms, as the variability of job sizes (service demands) approaches infinity. Our results reveal that some common wisdoms regarding task assignment are flawed. The Size-Interval-Task-Assignment policy (SITA), which assigns each server a unique size range, was heretofore thought of by some as the panacea for dealing with high-variability job-size distributions. We show SITA to be inferior to the much simpler greedy policy, Least-Work-Left (LWL), for certain common job-size distributions, including many modal, hyperexponential, and Pareto distributions. We also define regimes where SITA's performance is superior, and prove simple closed-form bounds on its performance for the above-mentioned distributions.
Self-adaptive admission control policies for resource-sharing systems
Authors: Gupta Varun , Harchol-Balter Mor
Published: April 2020

We consider the problem of admission control in resource sharing systems, such as web servers and transaction processing systems, when the job size distribution has high variability, with the aim of minimizing the mean response time. It is well known that in such resource sharing systems, as the number of tasks concurrently sharing the resource is increased, the server throughput initially increases, due to more efficient utilization of resources, but starts falling beyond a certain point, due to resource contention and thrashing. Most admission control mechanisms solve this problem by imposing a fixed upper bound on the number of concurrent transactions allowed into the system, called the Multi-Programming-Limit (MPL), and making the arrivals which find the server full queue up. Almost always, the MPL is chosen to be the point that maximizes server efficiency.

In this paper we abstract such resource sharing systems as a Processor Sharing (PS) server with state-dependent service rate and a First-Come-First-Served (FCFS) queue, and we analyze the performance of this model from a queueing theoretic perspective. We start by showing that, counter to the common wisdom, the peak efficiency point is not always optimal for minimizing the mean response time. Instead, significant performance gains can be obtained by running the system at less than the peak efficiency. We provide a simple expression for the static MPL that achieves near-optimal mean response time for general distributions.

Next we present two traffic-oblivious dynamic admission control policies that adjust the MPL based on the instantaneous queue length while also taking into account the variability of the job size distribution. The structure of our admission control policies is a mixture of fluid control when the number of jobs in the system is high, with a stochastic component when the system is near-empty. We show via simulations that our dynamic policies are much more robust to unknown traffic intensities and burstiness in the arrival process than imposing a static MPL.
Virtual networks -- distributed communication resource management
Authors: Heisswolf Jan , Zaib Aurang , Weichslgartner Andreas , König Ralf , Wild Thomas , Teich Jürgen , Herkersdorf Andreas , Becker Jürgen
Published: April 2020

Networks-on-Chip (NoC) enable scalability for future manycore architectures, facilitating parallel communication between multiple cores. Applications running in parallel on a NoC-based architecture can affect each other due to overlapping communication. Quality-of-Service (QoS) must be supported by the communication infrastructure to execute communication-, real-time- and safety-critical applications on such an architecture. Different strategies have been proposed to provide QoS for point-to-point connections. These strategies allow each node to set up a limited number of connections to other nodes.

In this work Virtual Networks (VN) are proposed to enable QoS for regions of a NoC-based architecture. Virtual Networks overcome the limitation of point-to-point connections. A VN behaves like an exclusive physical network. Virtual Networks can be defined and configured during runtime. The size of the VN region and the assigned bandwidth can be adjusted depending on the application requirements. Virtual Networks enable the decoupling of local from global communication. Therefore, the communication of the application mapped into the region is assigned to a Virtual Network established in that specific region. This concept targets packet-switched networks with virtual channels and is realized by an intelligent hardware unit that manages the virtual channel reservation process at system runtime. Virtual Networks can be established and administrated independent of each other, enabling distributed communication resource management.

The proposed concept is implemented as a cycle-accurate SystemC simulation model. The simulation results of executing communicating graphs obtained from real application highlight the usefulness of Virtual Networks by showing improved throughput and reduced delay in the respective scenarios. A hardware implementation demonstrates a low impact on area utilization and power consumption.
A comprehensive performance analysis of virtual routers on FPGA
Authors: Ganegedara Thilan , Prasanna Viktor
Published: April 2020

Network virtualization has gained much popularity with the advent of datacenter networking. The hardware aspect of network virtualization,
router virtualization
, allows network service providers to consolidate network hardware, reducing equipment cost and management overhead. Several approaches have been proposed to achieve router virtualization to support several virtual networks on a single hardware platform. However, their performance has not been analyzed quantitatively to understand the benefits of each approach. In this work, we perform a comprehensive analysis of performance of these approaches on Field Programmable Gate Array (FPGA) with respect to memory consumption, throughput, and power consumption. Generalized versions of virtualization approaches are evaluated based on post place-and-route results on a state-of-the-art FPGA. Grouping of routing tables is proposed as a novel approach to improve scalability (i.e., the number of virtual networks hosted on a single chip) of virtual routers on FPGA with respect to memory requirement. Further, we employ floor-planning techniques to efficiently utilize chip resources and achieve high performance for virtualized, pipelined architectures, resulting in 1.6× speedup on the average compared with the non-floor-planned approach. The results indicate that the proposed solution is able to support 100+ and 50 virtual routers per chip in the near-best and near-worst case scenarios, while operating at 20+ Gbps rates.
Teaching human-centered security using nontraditional techniques
Authors: Renaud Karen , Cutts Quintin
Published: April 2020

Computing science students amass years of programming experience and a wealth of factual knowledge in their undergraduate courses. Based on our combined years of experience, however, one of our students' abiding shortcomings is that they think there is only
one correct answer
to issues in most courses: an
idealistic
stance. Human-centered security, as well as other areas, requires students to understand that they have to weigh up a number of different possible solutions, and satisfice, rather than choose the one that is undeniably the best. In other words, they need to adopt a more
realistic
stance. Lecture-based teaching cannot develop this facility, due to its inability to engage students deeply with the issues and possible solutions. We argue that
depth
(in terms of understanding the complexity and issues involved) as well as
breadth
(in terms of appreciating the different positions taken by users on these issues) are essential for developing the realistic stance. This article reports on an instructional design that was used to help students become more realistic in their decision making. The design is based on seven educational strategies that, in tandem, help students to see the depth and breadth of topics in the course. We detail the instructional design and its application to three topic areas in the course, and report on the outcomes. We found evidence that students did indeed develop the depth and breadth we were hoping for. In concluding, we reflect on the design and the positive result, and propose changes to further improve the course.
Visual object detection with deformable part models
Authors: Felzenszwalb Pedro , Girshick Ross , McAllester David , Ramanan Deva
Published: April 2020

We describe a state-of-the-art system for finding objects in cluttered images. Our system is based on deformable models that represent objects using local part templates and geometric constraints on the locations of parts. We reduce object detection to classification with latent variables. The latent variables introduce invariances that make it possible to detect objects with highly variable appearance. We use a generalization of support vector machines to incorporate latent information during training. This has led to a general framework for discriminative training of classifiers with latent variables. Discriminative training benefits from large training datasets. In practice we use an iterative algorithm that alternates between estimating latent values for positive examples and solving a large convex optimization problem. Practical optimization of this large convex problem can be done using active set techniques for adaptive subsampling of the training data.