Visible to the public Clean Slate 2015

SoS Newsletter- Advanced Book Block


SoS Logo

Clean Slate


The “clean slate” approach looks at designing networks and internets from scratch, with security built in, in contrast to the evolved Internet in place. The research presented here covers a range of research topics, and includes items of interest to the Science of Security, including human behavior, resilience, metrics, and policy governance. These works were published or presented in 2015.

Zhong Shao; “Clean-Slate Development of Certified OS Kernels,” CPP ’15, Proceedings of the 2015 Conference on Certified Programs and Proofs, January 2015, Pages 95–96. doi:10.1145/2676724.2693180
Abstract: The CertiKOS project at Yale aims to develop new language-based technologies for building large-scale certified system software. Initially, we thought that verifying an OS kernel would require new program logics and powerful proof automation tools, but it should not be much different from standard Hoare-style program verification. After several years of trials and errors, we have decided to take a different path from the one we originally planned. We now believe that building large-scale certified system software requires a fundamental shift in the way we design the underlying programming languages, program logics, and proof assistants. In this talk, I outline our new clean-slate approach, explain its rationale, and describe various lessons and insights based on our experience with the development of several new certified OS kernels.
Keywords: abstraction layer, certified os kernels, horizontal composition, program verification, vertical composition (ID#: 15-6973)


Guoshun Nan, Xiuquan Qiao, Yukai Tu, Wei Tan, Lei Guo, Junliang Chen; “Design and Implementation: the Native Web Browser and Server for Content-Centric Networking,” SIGCOMM ’15, Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, August 2015, Pages 609–610. doi:10.1145/2829988.2790024
Abstract: Content-Centric Networking (CCN) has recently emerged as a clean-slate Future Internet architecture which has a completely different communication pattern compared with exiting IP network. Since the World Wide Web has become one of the most popular and important applications on the Internet, how to effectively support the dominant browser and server based web applications is a key to the success of CCN. However, the existing web browsers and servers are mainly designed for the HTTP protocol over TCP/IP networks and cannot directly support CCN-based web applications. Existing research mainly focuses on plug-in or proxy/gateway approaches at client and server sides, and these schemes seriously impact the service performance due to multiple protocol conversions. To address above problems, we designed and implemented a CCN web browser and a CCN web server to natively support CCN protocol. To facilitate the smooth evolution from IP networks to CCN, CCNBrowser and CCNxTomcat also support the HTTP protocol besides the CCN. Experimental results show that CCNBrowser and CCNxTomcat outperform existing implementations. Finally, a real CCN-based web application is deployed on a CCN experimental testbed, which validates the applicability of CCNBrowser and CCNxTomcat.
Keywords: content-centric networking, web browser, web server (ID#: 15-6974)


Tim Nelson, Andrew D. Ferguson, Da Yu, Rodrigo Fonseca, Shriram Krishnamurthi; “Exodus: Toward Automatic Migration of Enterprise Network Configurations to SDNs,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 13. doi:10.1145/2774993.2774997
Abstract: We present the design and a prototype of Exodus, a system that consumes a collection of router configurations (e.g., in Cisco IOS), compiles these into a common, intermediate semantic form, and then produces corresponding SDN controller software in a high-level language. Exodus generates networks that are functionally similar to the original networks, with the advantage of having centralized programs that are verifiable and evolvable. Exodus supports a wide array of IOS features, including non-trivial kinds of packet-filtering, reflexive access-lists, NAT, VLANs, static and dynamic routing. Implementing Exodus has exposed several limitations in both today’s languages for SDN programming and in OpenFlow itself. We briefly discuss these lessons learned and provide guidance for future SDN migration efforts.
Keywords: OpenFlow, SDN migration, software-defined networking (ID#: 15-6975)


Abdulkader Benchi, Pascale Launay, Frédéric Guidec; “Solving Consensus in Opportunistic Networks,” ICDCN ’15, Proceedings of the 2015 International Conference on Distributed Computing and Networking, January 2015, Article No. 1. doi:10.1145/2684464.2684479
Abstract: Opportunistic networks are partially connected wireless ad hoc networks, in which pairwise unpredicted transient contacts between mobile devices are the only opportunities for these devices to exchange information or services. Ensuring the coordination of multiple parts of a distributed application in such conditions is a challenge. This paper presents a system that can solve consensus problems in an opportunistic network. This system combines an implementation of the One-Third Rule (OTR) algorithm with a communication layer that supports network-wide, content-driven message dissemination based on controlled epidemic routing. Experimental results obtained with a small flotilla of smartphones are also presented, that validate the system and demonstrate that consensus can be solved effectively in an opportunistic network.
Keywords: Consensus, opportunistic computing, opportunistic networking (ID#: 15-6976)


Joel Sommers; “Lowering the Barrier to Systems-level Networking Projects,”  SIGCSE ’15, Proceedings of the 46th ACM Technical Symposium on Computer Science Education, February 2015, Pages 651–656. doi:10.1145/2676723.2677211
Abstract: Developing systems-level networking software to implement switches, routers, and middleboxes is challenging, rewarding, and arguably an essential component for developing a deep understanding of modern computer networks. Unfortunately, existing techniques for building networked system software use low-level and error-prone tools and languages, making this task inaccessible for many undergraduates. Moreover, working at such a low-level of abstraction complicates debugging and testing and can make assessment difficult for instructors and TAs. We describe a Python-based environment called Switchyard that is designed to facilitate student projects for building and testing software-based network devices like switches, routers, and middleboxes. Switchyard exposes a networking abstraction similar to a \textit{raw socket}, which allows a developer to receive and send Ethernet frames on specific network ports, and provides a set of classes to simplify parsing and construction of packets and packet headers. Systems-level software created using Switchyard can be deployed on a standard Linux host or in an emulated environment like Mininet. Perhaps most importantly, Switchyard provides facilities for test-driven development by transparently allowing the underlying network to be replaced with a test harness that is specifically designed to help students through the development and debugging process. We describe experiences with using Switchyard in an undergraduate networking course in which students created an Ethernet learning switch, a fully functional IPv4 router, a firewall with rate limiter, and a deep-packet inspection middlebox device.
Keywords: middleboxes, routing, switching, test-driven development (ID#: 15-6977)


Sanjib Sur, Teng Wei, Xinyu Zhang; “Bringing Multi-Antenna Gain to Energy-Constrained Wireless Devices,” IPSN ’15, Proceedings of the 14th International Conference on Information Processing in Sensor Networks, April, 2015, Pages 25-36. doi:10.1145/2737095.2737099
Abstract: Leveraging the redundancy and parallelism from multiple RF chains, MIMO technology can easily scale wireless link capacity. However, the high power consumption and circuit-area cost prevents MIMO from being adopted by energy-constrained wireless devices. In this paper, we propose Halma, that can boost link capacity using multiple antennas but a single RF chain, thereby, consuming the same power as SISO. While modulating its normal data symbols, a Halma transmitter hops between multiple passive antennas on a per-symbol basis. The antenna hopping pattern implicitly carriers extra data, which the receiver can decode by extracting the index of the active antenna using its channel pattern as a signature.  We design Halma by intercepting the antenna switching and channel estimation modules in modern wireless systems, including ZigBee and WiFi. Further, we design a model-driven antenna hopping protocol to balance a tradeoff between link quality and dissimilarity of channel signatures. Remarkably, by leveraging the inherent packet structure in ZigBee, Halma’s link capacity can scale well with the number of antennas. Using the WARP software radio, we have implemented Halma along with a ZigBee- and WiFi-based PHY layer. Our experiments demonstrate that Halma can improve ZigBee’s throughput and energy efficiency by multiple folds under realistic network settings. For WiFi, it consumes similar power as SISO, but boosts throughput across a wide range of link conditions and modulation levels.
Keywords: MIMO, energy efficiency, mobile devices (ID#: 15-6978)


Xinshu Dong, Hui Lin, Rui Tan, Ravishankar K. Iyer, Zbigniew Kalbarczyk; “Software-Defined Networking for Smart Grid Resilience: Opportunities and Challenges,” CPSS ’15, Proceedings of the 1st ACM Workshop on Cyber-Physical System Security, April 2015, Pages 61–68 . doi:10.1145/2732198.2732203
Abstract: Software-defined networking (SDN) is an emerging networking paradigm that provides unprecedented flexibility in dynamically reconfiguring an IP network. It enables various applications such as network management, quality of service (QoS) optimization, and system resilience enhancement. Pilot studies have investigated the possibilities of applying SDN on smart grid communications, while the specific benefits and risks that SDN may bring to the resilience of smart grids against accidental failures and malicious attacks remain largely unexplored. Without a systematic understanding of these issues and convincing validations of proposed solutions, the power industry will be unlikely to embrace SDN, since resilience is always a key consideration for critical infrastructures like power grids. In this position paper, we aim to provide an initial understanding of these issues, by investigating (1) how SDN can enhance the resilience of typical smart grids to malicious attacks, (2) additional risks introduced by SDN and how to manage them, and (3) how to validate and evaluate SDN-based resilience solutions. Our goal is also to trigger more profound discussions on applying SDN to smart grids and inspire innovative SDN-based solutions for enhancing smart grid resilience.
Keywords: cyber-physical systems, cyber-security, resilience, smart grids, software-defined networking (ID#: 15-6979)


Tal Mizrahi, Efi Saat, Yoram Moses; “Timed Consistent Network Updates,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 21. doi:10.1145/2774993.2775001
Abstract: Network updates such as policy and routing changes occur frequently in Software Defined Networks (SDN). Updates should be performed consistently, preventing temporary disruptions, and should require as little overhead as possible. Scalability is increasingly becoming an essential requirement in SDN. In this paper we propose to use time-triggered network updates to achieve consistent updates. Our proposed solution requires lower overhead than existing update approaches, without compromising the consistency during the update. We demonstrate that accurate time enables far more scalable consistent updates in SDN than previously available. In addition, it provides the SDN programmer with fine-grained control over the tradeoff between consistency and scalability.
Keywords: IEEE 1588, PTP, SDN, clock synchronization, management, time (ID#: 15-6980)


Luyuan Fang, Fabio Chiussi, Deepak Bansal, Vijay Gill, Tony Lin, Jeff Cox, Gary Ratterree; “Hierarchical SDN for the Hyper-Scale, Hyper-Elastic Data Center and Cloud,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 7. doi:10.1145/2774993.2775009
Abstract: With the explosive growth in the demand for cloud services, the Data Center and Data Center Interconnect have to achieve hyper-scale and provide unprecedented elasticity and resource availability. The underlay network infrastructure has to scale to support tens of millions of physical endpoints at low cost; the virtualized overlay layer has to scale to millions of Virtual Networks connecting hundreds of millions of Virtual Machines (VMs) and Virtualized Network Functions (VNFs), and provide seamless VM and VNF mobility.  In this paper, we present Hierarchical SDN (HSDN), an architectural solution that achieves hyper scale using surprisingly small forwarding tables in the network nodes. HSDN introduces a new paradigm for the forwarding and control planes, in that all paths in the network are pre-established in the forwarding tables and the labels identify entire paths rather than simply destinations. These properties of HSDN dramatically simplify establishing tunnels, and thus enable optimal handling of both ECMP and any-to-any end-to-end TE, which in turn yields extremely high network utilization with small buffers in the switches. The pre-established tunnels make HSDN the ideal underlay infrastructure to enable seamless and lossless VM and VNF overlay mobility, and achieve excellent elasticity.  HSDN is suitable for a full SDN implementation, using a scalable SDN controller to configure all forwarding tables in the network nodes and in the endpoints, as well as a hybrid approach, using conventional routing protocols in conjunction with a SDN controller.
Keywords: cloud, data center architecture, scalability, software-defined networking, traffic engineering, virtualization (ID#: 15-6981)


Arne Ludwig, Jan Marcinkowski, Stefan Schmid; “Scheduling Loop-free Network Updates: It’s Good to Relax!,” PODC ’15, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, July 2015, Pages 13–22. doi:10.1145/2767386.2767412
Abstract: We consider the problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. We are interested in fast network updates, i.e., in schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a k-round schedule exists is NP-complete already for k = 3, and there are problem instances requiring Ω(n) rounds, where n is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We prove that O(log n)-round relaxed loop-free schedules always exist, and can also be computed efficiently.
Keywords: NP-hardness, graph algorithms, scheduling, software-defined networking (ID#: 15-6982)


Pat Pannuto, Yoonmyung Lee, Ye-Sheng Kuo, ZhiYoong Foo, Benjamin Kempke, Gyouho Kim, Ronald G. Dreslinski, David Blaauw, Prabal Dutta; “MBus: An Ultra-Low Power Interconnect Bus for Next Generation Nanopower Systems,” ISCA ’15, Proceedings of the 42nd Annual International Symposium on Computer Architecture, June 2015, Pages 629-641. doi:10.1145/2749469.2750376
Abstract: As we show in this paper, I/O has become the limiting factor in scaling down size and power toward the goal of invisible computing. Achieving this goal will require composing optimized and specialized---yet reusable---components with an interconnect that permits tiny, ultra-low power systems. In contrast to today’s interconnects which are limited by power-hungry pull-ups or high-overhead chip-select lines, our approach provides a superset of common bus features but at lower power, with fixed area and pin count, using fully synthesizable logic, and with surprisingly low protocol overhead.  We present MBus, a new 4-pin, 22.6 pJ/bit/chip chip-to-chip interconnect made of two “shoot-through” rings. MBus facilitates ultra-low power system operation by implementing automatic power-gating of each chip in the system, easing the integration of active, inactive, and activating circuits on a single die. In addition, we introduce a new bus primitive: power oblivious communication, which guarantees message reception regardless of the recipient's power state when a message is sent. This disentangles power management from communication, greatly simplifying the creation of viable, modular, and heterogeneous systems that operate on the order of nanowatts.  To evaluate the viability, power, performance, overhead, and scalability of our design, we build both hardware and software implementations of MBus and show its seamless operation across two FPGAs and twelve custom chips from three different semiconductor processes. A three-chip, 2.2mm3 MBus system draws 8nW of total system standby power and uses only 22.6 pJ/bit/chip for communication. This is the lowest power for any system bus with MBus's feature set.
Keywords: (not provided) (ID#: 15-6983)


Kevin Boos, Ardalan Amiri Sani, Lin Zhong; “Eliminating State Entanglement with Checkpoint-based Virtualization of Mobile OS Services,” APSys ’15, Proceedings of the 6th Asia-Pacific Workshop on Systems, July 2015, Article No. 20. doi:10.1145/2797022.2797041
Abstract: Mobile operating systems have adopted a service model in which applications access system functionality by interacting with various OS Services in separate processes. These interactions cause application-specific states to be spread across many service processes, a problem we identify as state entanglement. State entanglement presents significant challenges to a wide variety of computing goals: fault isolation, fault tolerance, application migration, live update, and application speculation. We propose CORSA, a novel virtualization solution that uses a lightweight checkpoint/restore mechanism to virtualize OS Services on a per-application basis. This cleanly encapsulates a single application's service-side states into a private virtual service instance, eliminating state entanglement and enabling the above goals. We present empirical evidence that our ongoing implementation of CORSA on Android is feasible with low overhead, even in the worst case of high frequency service interactions.
Keywords: (not provided) (ID#: 15-6984)


Exequiel Rivas, Mauro Jaskelioff, Tom Schrijvers; “From Monoids to Near-semirings: The Essence of MonadPlus and Alternative,” PPDP ’15, Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming, July 2015, Pages 196–207. doi:10.1145/2790449.2790514
Abstract: It is well-known that monads are monoids in the category of endofunctors, and in fact so are applicative functors. Unfortunately, the benefits of this unified view are lost when the additional nondeterminism structure of MonadPlus or Alternative is required.  This article recovers the essence of these two type classes by extending monoids to near-semirings with both additive and multiplicative structure. This unified algebraic view enables us to generically define the free construction as well as a novel double Cayley representation that optimises both left-nested sums and left-nested products.
Keywords: Cayley representation, alternative, applicative functor, free construction, monad, monadplus, monoid, near-semiring (ID#: 15-6985)


Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica; “Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity,” SIGMOD ’15, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, Pages 1327–1342. doi:10.1145/2723372.2737784
Abstract: The rise of data-intensive “Web 2.0” Internet services has led to a range of popular new programming frameworks that collectively embody the latest incarnation of the vision of Object-Relational Mapping (ORM) systems, albeit at unprecedented scale. In this work, we empirically investigate modern ORM-backed applications’ use and disuse of database concurrency control mechanisms. Specifically, we focus our study on the common use of feral, or application-level, mechanisms for maintaining database integrity, which, across a range of ORM systems, often take the form of declarative correctness criteria, or invariants. We quantitatively analyze the use of these mechanisms in a range of open source applications written using the Ruby on Rails ORM and find that feral invariants are the most popular means of ensuring integrity (and, by usage, are over 37 times more popular than transactions). We evaluate which of these feral invariants actually ensure integrity (by usage, up to 86.9%) and which—due to concurrency errors and lack of database support—may lead to data corruption (the remainder), which we experimentally quantify. In light of these findings, we present recommendations for database system designers for better supporting these modern ORM programming patterns, thus eliminating their adverse effects on application integrity.
Keywords: application integrity, concurrency control, impedance mismatch, invariants, orms, ruby on rails (ID#: 15-6986)


Carsten S. Østerlund, Pernille Bjørn, Paul Dourish, Richard Harper, Daniela K. Rosner; “Sociomateriality and Design,” CSCW ’15 Companion, Proceedings of the 18th ACM Conference Companion on Computer Supported Cooperative Work & Social Computing, February 2015, Pages 126–130. doi:10.1145/2685553.2699336
Abstract: Design research and the literature on sociomateriality emerge out of different academic traditions but share a common interest in the material. A sociomaterial perspective allows us to account for the complex ways people mingle and mangle information systems of all sorts into their social endeavors to accomplish organizational tasks. But, how do we account for these sociomaterial phenomena in all their complexity when faced with the task of designing information systems? The panel brings together prominent researchers bridging the gap between design research and the current debate on sociomateriality. Each presenter addresses the challenges associated with informing grounded design work with insights from a highly abstract intellectual debate.
Keywords: design research, ethnography, sociomateriality (ID#: 15-6987)


Daejun Park, Andrei Stefănescu, Grigore Roşu; “KJS: A Complete Formal Semantics of JavaScript,” PLDI 2015, Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2015, Pages 346–356. doi:10.1145/2737924.2737991
Abstract: This paper presents KJS, the most complete and throughly tested formal semantics of JavaScript to date. Being executable, KJS has been tested against the ECMAScript 5.1 conformance test suite, and passes all 2,782 core language tests. Among the existing implementations of JavaScript, only Chrome V8’s passes all the tests, and no other semantics passes more than 90%. In addition to a reference implementation for JavaScript, KJS also yields a simple coverage metric for a test suite: the set of semantic rules it exercises. Our semantics revealed that the ECMAScript 5.1 conformance test suite fails to cover several semantic rules. Guided by the semantics, we wrote tests to exercise those rules. The new tests revealed bugs both in production JavaScript engines (Chrome V8, Safari WebKit, Firefox SpiderMonkey) and in other semantics. KJS is symbolically executable, thus it can be used for formal analysis and verification of JavaScript programs. We verified non-trivial programs and found a known security vulnerability.
Keywords: JavaScript, K framework, mechanized semantics (ID#: 15-6988)


Vladimir Andrei Olteanu, Felipe Huici, Costin Raiciu; “Lost in Network Address Translation: Lessons from Scaling the World’s Simplest Middlebox,” HotMiddlebox ’15, Proceedings of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization, August 2015, Pages 19–24. doi:10.1145/2785989.2785994
Abstract: To understand whether the promise of Network Function Virtualization can be accomplished in practice, we set out to create a software version of the simplest middlebox that keeps per flow state: the NAT. While there is a lot of literature in the wide area of SDN in general and in scaling middleboxes, we find that by aiming to create a NAT good enough to compete with hardware appliances requires a lot more care than we had thought when we started our work. In particular, limitations of OpenFlow switches force us to rethink load balancing in a way that does not involve the centralized controller at all. The result is a solution that can sustain, on six low-end commodity boxes, a throughput of 40Gbps with 64B packets, on par with industrial offerings but at a third of the cost.  To reach this performance, we designed and implemented our NAT from scratch to be migration friendly and optimized for common cases (inbound traffic, many mappings). Our experience shows that OpenFlow-based load balancing is very limited in the context of NATs (and by relation NFV), and that scalability can only be ensured by keeping the controller out of the data plane.
Keywords: (not provided) (ID#: 15-6989)


Sadegh Farhang, Yezekael Hayel, Quanyan Zhu; “Physical Layer Location Privacy Issue in Wireless Small Cell Networks,” WiSec ’15, Proceedings of the 8th ACM Conference on Security & Privacy in Wireless and Mobile Networks, June 2015, Article No. 32. doi:10.1145/2766498.2774990
Abstract: High data rates are essential for next-generation wireless networks to support a growing number of computing devices and networking services. Small cell base station (SCBS) (e.g., picocells, microcells, femtocells) technology is a cost-effective solution to address this issue. However, one challenging issue with the increasingly dense network is the need for a distributed and scalable access point association protocol. In addition, the reduced cell size makes it easy for an adversary to map out the geographical locations of the mobile users, and hence breaching their location privacy. To address these issues, we establish a game-theoretic framework to develop a privacy-preserving stable matching algorithm that captures the large scale and heterogeneity nature of 5G networks. We show that without the privacy-preserving mechanism, an attacker can infer the location of the users by observing wireless connections and the knowledge of physical-layer system parameters. The protocol presented in this work provides a decentralized differentially private association algorithm which guarantees privacy to a large number of users in the network. We evaluate our algorithm using case studies, and demonstrate the tradeoff between privacy and system-wide performance for different privacy requirements and a varying number of mobile users in the network. Our simulation results corroborate the result that the total number of mobile users should be lower than the overall network capacity to achieve desirable levels of privacy and QoS.
Keywords: (not provided) (ID#: 15-6990)


Julius Schulz-Zander, Carlos Mayer, Bogdan Ciobotaru, Stefan Schmid, Anja Feldmann; “OpenSDWN: Programmatic Control over Home and Enterprise WiFi,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 16. doi:10.1145/2774993.2775002
Abstract: The quickly growing demand for wireless networks and the numerous application-specific requirements stand in stark contrast to today’s inflexible management and operation of WiFi networks. In this paper, we present and evaluate OpenSDWN, a novel WiFi architecture based on an SDN/NFV approach. OpenSDWN exploits datapath programmability to enable service differentiation and fine-grained transmission control, facilitating the prioritization of critical applications. OpenSDWN implements per-client virtual access points and per-client virtual middleboxes, to render network functions more flexible and support mobility and seamless migration. OpenSDWN can also be used to out-source the control over the home network to a participatory interface or to an Internet Service Provider.
Keywords: WLAN, enterprise, network function virtualization, software-defined networking, software-defined wireless networking (ID#: 15-6991)


Daniel A. Epstein, An Ping, James Fogarty, Sean A. Munson; “A Lived Informatics Model of Personal Informatics,” UbiComp ’15, Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, September 2015, Pages 731–742. doi:10.1145/2750858.2804250
Abstract: Current models of how people use personal informatics systems are largely based in behavior change goals. They do not adequately characterize the integration of self-tracking into everyday life by people with varying goals. We build upon prior work by embracing the perspective of lived informatics to propose a new model of personal informatics. We examine how lived informatics manifests in the habits of self-trackers across a variety of domains, first by surveying 105, 99, and 83 past and present trackers of physical activity, finances, and location and then by interviewing 22 trackers regarding their lived informatics experiences. We develop a model characterizing tracker processes of deciding to track and selecting a tool, elaborate on tool usage during collection, integration, and reflection as components of tracking and acting, and discuss the lapsing and potential resuming of tracking. We use our model to surface underexplored challenges in lived informatics, thus identifying future directions for personal informatics design and research.
Keywords: finances, lapsing, lived informatics, location, personal informatics, physical activity, self-tracking (ID#: 15-6992)


Joongi Kim, Keon Jang, Keunhong Lee, Sangwook Ma, Junhyun Shim, Sue Moon; “NBA (Network Balancing Act): A High-Performance Packet Processing Framework for Heterogeneous Processors,” EuroSys ’15, Proceedings of the Tenth European Conference on Computer Systems, April 2015, Article No. 22. doi:10.1145/2741948.2741969
Abstract: We present the NBA framework, which extends the architecture of the Click modular router to exploit modern hardware, adapts to different hardware configurations, and reaches close to their maximum performance without manual optimization. NBA takes advantages of existing performance-excavating solutions such as batch processing, NUMA-aware memory management, and receive-side scaling with multi-queue network cards. Its abstraction resembles Click but also hides the details of architecture-specific optimization, batch processing that handles the path diversity of individual packets, CPU/GPU load balancing, and complex hardware resource mappings due to multi-core CPUs and multi-queue network cards. We have implemented four sample applications: an IPv4 and an IPv6 router, an IPsec encryption gateway, and an intrusion detection system (IDS) with Aho-Corasik and regular expression matching. The IPv4/IPv6 router performance reaches the line rate on a commodity 80 Gbps machine, and the performances of the IPsec gateway and the IDS reaches above 30 Gbps. We also show that our adaptive CPU/GPU load balancer reaches near-optimal throughput in various combinations of sample applications and traffic conditions.
Keywords: (not provided) (ID#: 15-6993)


Florian Schmidt, Oliver Hohlfeld, René Glebke, Klaus Wehrle; “Santa: Faster Packet Delivery for Commonly Wished Replies,” SIGCOMM ’15, Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, August 2015, Pages 597–598. doi:10.1145/2829988.2790014
Abstract: Increasing network speeds challenge the packet processing performance of networked systems. This can mainly be attributed to processing overhead caused by the split between the kernel-space network stack and user-space applications. To mitigate this overhead, we propose Santa, an application agnostic kernel-level cache of frequent requests. By allowing user-space applications to offload frequent requests to the kernel-space, Santa offers drastic performance improvements and unlocks the speed of kernel-space networking for legacy server software without requiring extensive changes.
Keywords: (not provided) (ID#: 15-6994)


Nan Cen, Zhangyu Guan, Tommaso Melodia; “Multi-view Wireless Video Streaming Based on Compressed Sensing: Architecture and Network Optimization,” MobiHoc ’15, Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing, June 2015, Pages 137–146. doi:10.1145/2746285.2746309
Abstract: Multi-view wireless video streaming has the potential to enable a new generation of efficient and low-power pervasive surveillance systems that can capture scenes of interest from multiple perspectives, at higher resolution, and with lower energy consumption. However, state-of-the-art multi-view coding architectures require relatively complex predictive encoders, thus resulting in high processing complexity and power requirements. To address these challenges, we consider a wireless video surveillance scenario and propose a new encoding and decoding architecture for multi-view video systems based on Compressed Sensing (CS) principles, composed of cooperative sparsity-aware block-level rate-adaptive encoders, feedback channels and independent decoders. The proposed architecture leverages the properties of CS to overcome many limitations of traditional encoding techniques, specifically massive storage requirements and high computational complexity. It also uses estimates of image sparsity to perform efficient rate adaptation and effectively exploit inter-view correlation at the encoder side.  Based on the proposed encoding/decoding architecture, we further develop a CS-based end-to-end rate distortion model by considering the effect of packet losses on the perceived video quality. We then introduce a modeling framework to design network optimization problems in a multi-hop wireless sensor network. Extensive performance evaluation results show that the proposed coding framework and power-minimizing delivery scheme are able to transmit multi-view streams with guaranteed video quality at low power consumption.
Keywords: compressed sensing, multi-view video streaming, network optimization (ID#: 15-6995)


Petr Hosek, Cristian Cadar; “VARAN the Unbelievable: An Efficient N-version Execution Framework,” ASPLOS ’15, Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, March 2015, Pages 339–353. doi:10.1145/2775054.2694390
Abstract: With the widespread availability of multi-core processors, running multiple diversified variants or several different versions of an application in parallel is becoming a viable approach for increasing the reliability and security of software systems. The key component of such N-version execution (NVX) systems is a runtime monitor that enables the execution of multiple versions in parallel. Unfortunately, existing monitors impose either a large performance overhead or rely on intrusive kernel-level changes. Moreover, none of the existing solutions scales well with the number of versions, since the runtime monitor acts as a performance bottleneck.  In this paper, we introduce Varan, an NVX framework that combines selective binary rewriting with a novel event-streaming architecture to significantly reduce performance overhead and scale well with the number of versions, without relying on intrusive kernel modifications.  Our evaluation shows that Varan can run NVX systems based on popular C10k network servers with only a modest performance overhead, and can be effectively used to increase software reliability using techniques such as transparent failover, live sanitization and multi-revision execution.
Keywords: N-version execution, event streaming, live sanitization, multi-revision execution, record-replay, selective binary rewriting, transparent failover (ID#: 15-6996)


Naga Katta, Haoyu Zhang, Michael Freedman, Jennifer Rexford; “Ravana: Controller Fault-Tolerance in Software-Defined Networking,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 4. doi:10.1145/2774993.2774996
Abstract: Software-defined networking (SDN) offers greater flexibility than traditional distributed architectures, at the risk of the controller being a single point-of-failure. Unfortunately, existing fault-tolerance techniques, such as replicated state machine, are insufficient to ensure correct network behavior under controller failures. The challenge is that, in addition to the application state of the controllers, the switches maintain hard state that must be handled consistently. Thus, it is necessary to incorporate switch state into the system model to correctly offer a “logically centralized” controller. We introduce Ravana, a fault-tolerant SDN controller platform that processes the control messages transactionally and exactly once (at both the controllers and the switches). Ravana maintains these guarantees in the face of both controller and switch crashes. The key insight in Ravana is that replicated state machines can be extended with lightweight switch-side mechanisms to guarantee correctness, without involving the switches in an elaborate consensus protocol. Our prototype implementation of Ravana enables unmodified controller applications to execute in a fault-tolerant fashion. Experiments show that Ravana achieves high throughput with reasonable overhead, compared to a single controller, with a failover time under 100ms.
Keywords: OpenFlow, fault-tolerance, replicated state machines, software-defined networking (ID#: 15-6997)


Peng Sun, Laurent Vanbever, Jennifer Rexford; “Scalable Programmable Inbound Traffic Engineering,” SOSR ’15, Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research, June 2015, Article No. 12.  doi:10.1145/2774993.2775063
Abstract: With the rise of video streaming and cloud services, enterprise and access networks receive much more traffic than they send, and must rely on the Internet to offer good end-to-end performance. These edge networks often connect to multiple ISPs for better performance and reliability, but have only limited ways to influence which of their ISPs carries the traffic for each service. In this paper, we present Sprite, a software-defined solution for flexible inbound traffic engineering (TE). Sprite offers direct, fine-grained control over inbound traffic, by announcing different public IP prefixes to each ISP, and performing source network address translation (SNAT) on outbound request traffic. Our design achieves scalability in both the data plane (by performing SNAT on edge switches close to the clients) and the control plane (by having local agents install the SNAT rules). The controller translates high-level TE objectives, based on client and server names, as well as performance metrics, to a dynamic network policy based on real-time traffic and performance measurements. We evaluate Sprite with live data from “in the wild” experiments on an EC2-based testbed, and demonstrate how Sprite dynamically adapts the network policy to achieve high-level TE objectives, such as balancing YouTube traffic among ISPs to improve video quality.
Keywords: scalability, software-defined networking, traffic engineering (ID#: 15-6998)


Eddie Q. Yan, Jeff Huang, Gifford K. Cheung; “Masters of Control: Behavioral Patterns of Simultaneous Unit Group Manipulation in StarCraft 2,” CHI ’15, Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, April 2015, Pages 3711–3720. doi:10.1145/2702123.2702429
Abstract: Most user interfaces require the user to focus on one element at a time, but StarCraft 2 is a game where players often control more than a hundred units simultaneously. The game interface provides an optional mechanism called “control groups” that allows players to select multiple units and assign them to a group in order to quickly recall previous selections of units. From an analysis of over 3,000 replays, we show that the usage of control groups is a key differentiator of individual players as well as players of different skill levels—novice users rarely use control groups while experts nearly always do. But players also behave differently in how they use their control groups, especially in time-pressured situations. While certain control group behaviors are common across all skill levels, expert players appear to be better at remaining composed and sustaining control group use in battle. We also qualitatively analyze discussions on web forums from players about how they use control groups to provide context about how such a simple interface mechanic has produced numerous ways of optimizing unit control.
Keywords: control groups, player behavior, skill, video games (ID#: 15-6999)


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.