CCR Papers from October 2012

Find a CCR issue:
  • S. Keshav

    I considered many ideas for my last CCR editorial but, in the end, decided to write about something that I think I share with every reader of CCR, yet is something we rarely acknowledge even in conversation, let alone in print: the joy of research.

    For me, research is the process of exploring new ideas, formulating problems in areas yet undefined, and then using our ever-expanding toolkit of algorithms, technologies, and theories to solve them. I find this process to be deep, satisfying, and fun. It is fun to explore new ideas, fun to learn new tools, techniques, and theories, and fun to solve puzzles. I'm especially delighted during that brief, sharp, shining moment when it is as if a puzzle piece has clicked into place and confusion is transformed into simplicity. It is this that keeps me fueled as a researcher; it is the direct experience of the fun of research that converts the best of our students to our ranks.
     
    To be sure, there are many other ways to have fun. One can climb mountains or hike forbidding landscapes; swim the waves or fly from continent to continent in search of exotic cuisines. I have done some of these, but find them all, to some degree, unsatisfying. These experiences are intense but ephemeral. Besides, it is hard to justify that they have any socially redeeming value. In contrast, research, especially the kind of work that is both theoretically challenging yet practically applicable, is not only fun but also worthwhile.
     
    Of course, not all aspects of research are fun. Behind each sweet moment of success there can be many dreary hours of work, with little guarantee that a hunch may pan out. Each idea carried into practice, each paper accepted for publication, and each research project that benefits society builds on many discarded ideas, rejcted papers, and failed projects. Yet, even in the face of these failures, I feel that the process itself is fun. I sympathize with Oscar Wilde, who wrote “We are all in the gutter, but some of us are looking at the stars.”
     
    I think every researcher, at some level, has a directunderstanding of what I mean by the joy of research. I know this because our shared experience binds us despite barriers of geography, culture, and language. I find an instant rapport with other researchers when discussing each other’s work: the barriers to communication drop as we share our experiences, hunches, and ideas. The excitement simply shines through.
     
    Unfortunately, we do not often share our sense of joy with outsiders. Our ideas are usually hidden behind walls of jargon, inscrutable mathematical notation, and the arcane conventions of academic publishing. This does not serve us well: baffled funders and soporific students do not aid our cause. Instead, we should let our exuberance and joy--tempered with gratitude to our employers--motivate us to share our ideas. By interpreting our work to non-experts we open channels of communication with those who can directly benefit from our ideas and innovations. For many of us, this is the one of the deepest motivations for our work.
     
    So, let the joy of research be your touchstone. Share this joy with your fellow researchers, but share it too with others, that the fire in your work may ignite a light elsewhere, and that your work benefit society at large.
  • Xuetao Wei, Nicholas Valler, B. Aditya Prakash, Iulian Neamtiu, Michalis Faloutsos, Christos Faloutsos

    If a false rumor propagates via Twitter, while the truth propagates between friends in Facebook, which one will prevail? This question captures the essence of the problem we address here. We study the intertwined propagation of two competing "memes" (or viruses, rumors, products etc.) in a composite network. A key novelty is the use of a composite network, which in its simplest model is defined as a single set of nodes with two distinct types of edges interconnecting them. Each meme spreads across the composite network in accordance to an SIS-like propagation model (a flu-like infection-recovery). To study the epidemic behavior of our system, we formulate it as a non-linear dynamic system (NLDS). We develop a metric for each meme that is based on the eigenvalue of an appropriately constructed matrix and argue that this metric plays a key role in determining the "winning" meme. First, we prove that our metric determines the tipping point at which both memes become extinct eventually. Second, we conjecture that the meme with the strongest metric will most likely prevail over the other, and we show evidence of that via simulations in both real and synthetic composite networks. Our work is among the first to study the interplay between two competing memes in composite networks.

    Augustin Chaintreau
  • Sebastian Zander, Lachlan L.H. Andrew, Grenville Armitage, Geoff Huston, George Michaelson

    The Teredo auto-tunnelling protocol allows IPv6 hosts behind IPv4 NATs to communicate with other IPv6 hosts. It is enabled by default on Windows Vista and Windows 7. But Windows clients are self-constrained: if their only IPv6 access is Teredo, they are unable to resolve host names to IPv6 addresses. We use web-based measurements to investigate the (latent) Teredo capability of Internet clients, and the delay introduced by Teredo. We compare this with native IPv6 and 6to4 tunnelling capability and delay. We find that only 6--7% of connections are from fully IPv6-capable clients, but an additional 15--16% of connections are from clients that would be IPv6-capable if Windows Teredo was not constrained. However, Teredo increases the median latency to fetch objects by 1--1.5 seconds compared to IPv4 or native IPv6, even with an optimally located Teredo relay. Furthermore, in many cases Teredo fails to establish a tunnel.

    Jia Wang
  • Ingmar Poese, Benjamin Poese, Georgios Smaragdakis, Steve Uhlig, Anja Feldmann, Bruce Maggs

    Today, a large fraction of Internet traffic is originated by Content Delivery Networks (CDNs). To cope with increasing demand for content, CDNs have deployed massively distributed infrastructures. These deployments pose challenges for CDNs as they have to dynamically map end-users to appropriate servers without being full+y aware of the network conditions within an Internet Service Provider (ISP) or the end-user location. On the other hand, ISPs struggle to cope with rapid traffic shifts caused by the dynamic server selection policies of the CDNs. The challenges that CDNs and ISPs face separately can be turned into an opportunity for collaboration. We argue that it is sufficient for CDNs and ISPs to coordinate only in server selection, not routing, in order to perform traffic engineering. To this end, we propose Content-aware Traffic Engineering (CaTE), which dynamically adapts server selection for content hosted by CDNs using ISP recommendations on small time scales. CaTE relies on the observation that by selecting an appropriate server among those available to deliver the content, the path of the traffic in the network can be influenced in a desired way. We present the design and implementation of a prototype to realize CaTE, and show how CDNs and ISPs can jointly take advantage of the already deployed distributed hosting infrastructures and path diversity, as well as the ISP detailed view of the network status without revealing sensitive operational information. By relying on tier-1 ISP traces, we show that CaTE allows CDNs to enhance the end-user experience while enabling an ISP to achieve several traffic engineering goals.

    Renata Teixeira
  • Marko Zec, Luigi Rizzo, Miljenko Mikuc

    Can a software routing implementation compete in a field generally reserved for specialized lookup hardware? This paper presents DXR, an IPv4 lookup scheme based on transforming large routing tables into compact lookup structures which easily fit into cache hierarchies of modern CPUs. DXR supports various memory/speed tradeoffs and scales almost linearly with the number of CPU cores. The smallest configuration, D16R, distills a real-world BGP snapshot with 417,000 IPv4 prefixes and 213 distinct next hops into a structure consuming only 782 Kbytes, less than 2 bytes per prefix, and achieves 490 million lookups per second (MLps) in synthetic tests using uniformly random IPv4 keys on a commodity 8-core CPU. Some other DXR configurations exceed 700~MLps at the cost of increased memory footprint. DXR significantly outperforms a software implementation of DIR-24-8-BASIC, has better scalability, and requires less DRAM bandwidth. Our prototype works inside the FreeBSD kernel, which permits DXR to be used with standard APIs and routing daemons such as Quagga and XORP, and to be validated by comparing lookup results against the BSD radix tree.

    Nikolaos Laoutaris
  • Jon Whiteaker, Fabian Schneider, Renata Teixeira, Christophe Diot, Augustin Soule, Fabio Picconi, Martin May

    The success of over-the-top (OTT) services reflects users' demand for personalization of digital services at home. ISPs propose fulfilling this demand with a cloud delivery model, which would simplify the management of the service portfolio and bring them additional revenue streams. We argue that this approach has many limitations that can be fixed by turning the home gateway into a flexible execution platform. We define requirements for such a "service-hosting gateway" and build a proof of concept prototype using a virtualized Intel Groveland system-on-a-chip platform. We discuss remaining challenges such as service distribution, security and privacy, management, and home integration.

    David Wetherall
  • Jeffrey C. Mogul, Lucian Popa

    Infrastructure-as-a-Service ("Cloud") data-centers intrinsically depend on high-performance networks to connect servers within the data-center and to the rest of the world. Cloud providers typically offer different service levels, and associated prices, for different sizes of virtual machine, memory, and disk storage. However, while all cloud providers provide network connectivity to tenant VMs, they seldom make any promises about network performance, and so cloud tenants suffer from highly-variable, unpredictable network performance. Many cloud customers do want to be able to rely on network performance guarantees, and many cloud providers would like to offer (and charge for) these guarantees. But nobody really agrees on how to define these guarantees, and it turns out to be challenging to define "network performance" in a way that is useful to both customers and providers. We attempt to bring some clarity to this question.

  • Tanja Zseby, kc claffy

    On May 14-15, 2012, CAIDA hosted the first international Workshop on Darkspace and Unsolicited Traffic Analysis (DUST 2012) to provide a forum for discussion of the science, engineering, and policy challenges associated with darkspace and unsolicited traffic analysis. This report captures threads discussed at the workshop and lists resulting collaborations.

  • Tobias Lauinger, Nikolaos Laoutaris, Pablo Rodriguez, Thorsten Strufe, Ernst Biersack, Engin Kirda

    Named Data Networking architectures have been proposed to improve various shortcomings of the current Internet architecture. A key part of these proposals is the capability of caching arbitrary content in arbitrary network locations. While caching has the potential to improve network performance, the data stored in caches can be seen as transient traces of past communication that attackers can exploit to compromise the users' privacy. With this editorial note, we aim to raise awareness of privacy attacks as an intrinsic and relevant issue in Named Data Networking architectures. Countermeasures against privacy attacks are subject to a trade-off between performance and privacy. We discuss several approaches to countermeasures representing different incarnations of this tradeoff, along with open issues to be looked at by the research community.

  • Sameer S. Tilak, Philip Papadopoulos

    Software Operations and Management (O&M) i.e., installing, configuring, and updating thousands of software components within a conventional Data Center is a well-understood issue. Existing frameworks such as the Rocks toolkit have revolutionized the way system administrators deploy and manage large-scale compute clusters, storage servers, and visualization facilities. However, existing tools like Rocks are designed for a "friendly" Data Center environment where stable power along with high-performance compute, storage, and networking is the norm. In contrast, sensor networks are embedded deeply within the harsh physical environment where node failures, node mobility and idiosyncrasies of wireless networks are the norm. In addition, device heterogeneity and resource-constrained nature (e.g., power, memory, CPU capability) of the sensor cyberinfrastructure (CI) are realities that must be addressed and reconciled. Although sensor CI must be more adaptable and more-rapidly reconfigurable than the data center equivalents, few if any of the existing software O&M tools and techniques have been adapted to the significantly more challenging environment of sensor networks. A more automated approach to software O&M would provide significant benefits to system builders, operators, and sensor network researchers. We argue that by starting with software O&M techniques developed for data centers, and then adapting and extending them to the world of resource-constrained sensor networks, we will be able to provide robust and scientifically reproducible mechanisms for defining the software footprint of individual sensors and networks of sensors. This paper describes the current golden-image based software O&M practice in Android world. We then propose an approach that adapts the Rocks toolkit to allow one to rapidly and reliably build complete Android environments (firmware flashes) at the individual sensor level and extend to a large networks of diverse sensors.

  • Dimitri Papadimitriou, Lluís Fàbrega, Pere Vilà, Davide Careglio, Piet Demeester

    In this paper, we report the results of the workshop organized by the FP7 EULER project on measurement-based research and associated methodology, experiments and tools. This workshop aimed at gathering all Future Internet Research and Experimentation (FIRE) experimental research projects under this thematic. Participants were invited to present the usage of measurement techniques in their experiments, their developments on measurement tools, and their foreseeable needs with respect to new domains of research not currently addressed by existing measurement techniques and tools.

Syndicate content