CCR Papers from July 2012

Find a CCR issue:
  • S. Keshav

    Networking researchers seem to fall into two nearly non-overlapping categories: those whose blood runs with the practical clarity of “rough consensus and running code” (in the words of Dave Clark) and those who worship, instead, at the altar of mathematical analysis. The former build systems that work, even work well, but don’t necessarily know at what level of scaling or load their systems will catastrophically fail. Congestion collapse in the Internet in the mid-1980’s, for example, was a direct result of this approach, and similar scaling failures recur periodically (HTTP 1.0, “push” content distribution, and Shoutcast, to name a few), although many pragmatically-engineered systems, such as DNS, email, and Twitter, have proved to be incredibly scalable and robust.

    Proponents of mathematical modeling are better able to quantify the performance of their systems, using the powerful tools arising from theories such as model checking, queueing theory, and control theory. However, purely analytical approaches (remember PetriNets?) have had little practical success due to three inherent limitations. To begin with, it is not clear what mathematical approach is the best fit to a given problem. There are a plethora of approaches -- each of which can take years to master -- and it is nearly impossible to decide, a priori, which one best matches the problem at hand. For example, to optimize a system one can use linear or quadratic optimization, or any number of heuristic approaches, such as hill-climbing, genetic algorithms, and taboo search. Which one to pick? It all depends on the nuances of the problem, the quality of the available tools, and prior experience in using these approaches. That’s pretty daunting for a seasoned researcher, let alone a graduate student. Second, every mathematically sound approach necessarily makes simplifying assumptions. Fitting the square peg of reality into the round hole of mathematical assumptions can lead to impractical, even absurd, designs. As a case in point, assumptions of individual rationality needed by decision and game theory rarely hold in practice. Third, having spent the time to learn about a particular modeling approach, a researcher may be seduced into viewing the approach as being more powerful than it really is, ignoring its faults and modeling assumptions. For these reasons, I believe that one should couple a healthy respect for mathematical modeling with a hearty skepticism of its outcomes.
    When mathematical modeling and pragmatic system design come together, it can lead to beautiful systems. The original Ethernet, for example, brought together the elegant mathematics of researchers like Kleinrock, Tobagi, Lam, and Abramson with hands-on implementation by Metcalfe. Similarly, Jacobson and Karels brought a deep understanding of control theory to their inspired design of TCP congestion control. More recently, the Google Page Rank algorithm by Page, Brin, Motwani, and Winograd is based on eigenvalue computation in sparse Markov matrices.
    Given these enormous successes, it is no wonder that researchers in our community try hard to combine mathematical modeling with system building. Most papers in SIGCOMM these days build and study real systems applying analytical techniques arising from areas such as optimization, protocol verification, information theory, and communication theory. Although I must confess that the mathematical details of many papers are beyond my understanding (despite my recent attempt to remedy the situation), I think this is a positive development.
    Yet, much needs to be done. As a field, we lack widely accepted abstractions for even relatively simple concepts such as names and addresses, let alone routing and middleboxes. These have stymied our ability to build standard models for networking problems or a standard list of Grand Challenges. The recent emphasis on clean-slate design has renewed focus on these problems, and I look forward to the outcomes of these efforts in the years to come.
  • Vinh The Lam, Sivasankar Radhakrishnan, Rong Pan, Amin Vahdat, George Varghese

    Application performance in cloud data centers often depends crucially on network bandwidth, not just the aggregate data transmitted as in typical SLAs. We describe a mechanism for data center networks called NetShare that requires no hardware changes to routers but allows bandwidth to be allocated predictably across services based on weights. The weights are either specified by a manager, or automatically assigned at each switch port based on a virtual machine heuristic for isolation. Bandwidth unused by a service is shared proportionately by other services, providing weighted hierarchical max-min fair sharing. On a testbed of Fulcrum switches, we demonstrate that NetShare provides bandwidth isolation in various settings, including multipath networks.

    Sharad Agarwal
  • Yosuke Himura, Yoshiko Yasuda

    Multi-tenant datacenter networking, with which multiple customer (tenant) networks are virtualized over a single shared physical infrastructure, is cost-effective but poses significant costs on manual configuration. Such tasks would be alleviated with configuration templates, whereas a crucial difficulty stems from creating appropriate (i.e., reusable) ones. In this work, we propose a graph-based method of mining configurations of existing tenants to extract their recurrent patterns that would be used as reusable templates for upcoming tenants. The effectiveness of the proposed method is demonstrated with actual configuration files obtained from a business datacenter network.

    Sharad Agarwal
  • Anonymous

    Some ISPs and governments (most notably the Great Firewall of China) use DNS injection to block access to "unwanted" websites. The censorship tools inspect DNS queries near the ISP's boundary routers for sensitive domain keywords and inject forged DNS responses, blocking the users from accessing censored sites, such as twitter and facebook. Unfortunately this causes collateral damage, affecting communication beyond the censored networks when outside DNS traffic traverses censored links. In this paper, we analyze the causes of the collateral damages and measure the Internet to identify the injecting activities and their effect. We find 39 ASes in China injecting forged DNS replies. Furthermore, 26 of 43,000 measured open resolvers outside China, distributed in 109 countries, may suffer some collateral damage from these forged replies. Different from previous work that considers the collateral damage being limited to queries to root servers (F, I, J) located in China, we find that most collateral damage arises when the paths between resolvers and some TLD name servers transit through ISPs in China.

    Philip Levis
  • kc claffy

    On Monday, 22 August 2011, CAIDA hosted a one-day workshop to discuss scalable measurement and analysis of BGP and traceroute topology data, and practical applications of such data analysis including tracking of macroscopic censorship and filtering activities on the Internet. Discussion topics included: the surprisingly stability in the number of BGP updates over time; techniques for improving measurement and analysis of inter-domain routing policies; an update on Colorado State's BGPMon instrumentation; using BGP data to improve the interpretation of traceroute data, both for real-time diagnostics (e.g., AS traceroute) and for large-scale topology mapping; using both BGP and traceroute data to support detection and mapping infrastructure integrity, including different types of of filtering and censorship; and use of BGP data to analyze existing and proposed approaches to securing the interdomain routing system. This report briefly summarizes the presentations and discussions that followed.

  • Jon Crowcroft

    In all seriousness, Differential Privacy is a new technique and set of tools for managing responses to statistical queries over secured data, in such a way that the user cannot reconstruct more precise identification of principles in the dataset beyond a formally well-specified bound. This means that personally sensitive data such as Internet packet traces or social network measurements can be shared between researchers without invading personal privacy, and that assurances can be made with accuracy. With less seriousness, I would like to talk about Differential Piracy, but not without purpose. For sure, while there are legitimate reasons for upstanding citizens to live without fear of eternal surveillance, there is also a segment of society that gets away with things they shouldn't, under a cloak. Perhaps that is the (modest) price we have to pay for a modicum less paranoia in this brave new world. So, there has been a lot of work recently on Piracy Preserving Queries and Differential Piracy. These two related technologies exploit new ideas in statistical security. Rather than security through obscurity, the idea is to offer privacy through lack of differentiation (no, not inability to perform basic calculus, more the inability to distinguish between large numbers of very similar things).

  • kc claffy

    On February 8-10, 2012, CAIDA hosted the fourth Workshop on Active Internet Measurements (AIMS-4) as part of our series of Internet Statistics and Metrics Analysis (ISMA) workshops. As with the previous three AIMS workshops, the goals were to further our understanding of the potential and limitations of active measurement research and infrastructure in the wide-area Internet, and to promote cooperative solutions and coordinated strategies to address future data needs of the network and security operations and research communities. This year we continued to focus on how measurement can illuminate two specific public policy concerns: IPv6 deployment and broadband performance. This report briefly describes topics discussed at this year's workshop. Slides and other materials related to the workshop are available at

  • Rute Sofia, Paulo Mendes, Manuel José Damásio, Sara Henriques, Fabio Giglietto, Erica Giambitto, Alessandro Bogliolo

    This paper provides an interdisciplinary perspective concerning the role of prosumers on future Internet design based on the current trend of Internet user empowerment. The paper debates the prosumer role, and addresses models to develop a symmetric Internet architecture and supply-chain based on the integration of social capital aspects. It has as goal to ignite the discussion concerning a socially-driven Internet architectural design.

  • Dirk Trossen

    The late noughties have seen an influx of work in different scientific disciplines, all addressing the question of 'design' and 'architecture'. It is a battle between those advocating the theory of 'emergent properties' and others who strive for a 'theory for 'architecture'. We provide a particular insight into this battle, represented in the form of a story that focuses on the role of a possibly unusual protagonist and his influence on computer science, the Internet, architecture and beyond. We show his relation to one of the great achievements of system engineering, the Internet, and the possible future as it might unfold. Note from the writer: The tale is placed in a mixture of reality and fiction, while postulating a certain likelihood for this fiction. There is no proof for the assertions made in this tale, leaving the space for a sequel to be told.

  • Marshini Chetty, Nick Feamster

    Managing a home network is challenging because the underlying infrastructure is so complex. Existing interfaces either hide or expose the network's underlying complexity, but in both cases, the information that is shown does not necessarily allow a user to complete desired tasks. Recent advances in software defined networking, however, permit a redesign of the underlying network and protocols, potentially allowing designers to move complexity further from the user and, in some cases, eliminating it entirely. In this paper, we explore whether the choices of what to make visible to the user in the design of today's home network infrastructure, performance, and policies make sense. We also examine whether new capabilities for refactoring the network infrastructure - changing the underlying system without compromising existing functionality - should cause us to revisit some of these choices. Our work represents a case study of how co-designing an interface and its underlying infrastructure could ultimately improve interfaces for that infrastructure.

  • Cheng Yi, Alexander Afanasyev, Lan Wang, Beichuan Zhang, Lixia Zhang

    In Named Data Networking (NDN) architecture, packets carry data names rather than source or destination addresses. This change of paradigm leads to a new data plane: data consumers send out Interest packets, routers forward them and maintain the state of pending Interests, which is used to guide Data packets back to the consumers. NDN routers' forwarding process is able to detect network problems by observing the two-way traffic of Interest and Data packets, and explore multiple alternative paths without loops. This is in sharp contrast to today's IP forwarding process which follows a single path chosen by the routing process, with no adaptability of its own. In this paper we outline the design of NDN's adaptive forwarding, articulate its potential benefits, and identify open research issues.

Syndicate content