Computer Communication Review: Papers

Find a CCR issue:
  • P. Brighten Godfrey, Igor Ganichev, Scott Shenker, and Ion Stoica

    We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly exible building block, capturing policy constraints as well as enabling an exponentially large number of path choices. In particular, we show that pathlet routing can emulate the policies of BGP, source routing, and several recent multipath proposals.

    This exibility lets us address two major challenges for Internet routing: scalability and source-controlled routing. When a router's routing policy has only \local" constraints, it can be represented using a small number of pathlets, leading to very small forwarding tables and many choices of routes for senders. Crucially, pathlet routing does not impose a global requirement on what style of policy is used, but rather allows multiple styles to coexist. The protocol thus supports complex routing policies while enabling and incentivizing the adoption of policies that yield small forwarding plane state and a high degree of path choice.

  • Asfandyar Qureshi, Rick Weber, Hari Balakrishnan, John Guttag, and Bruce Maggs

    Energy expenses are becoming an increasingly important fraction of data center operating costs. At the same time, the energy expense per unit of computation can vary significantly between two different locations. In this paper, we characterize the variation due to fluctuating electricity prices and argue that existing distributed systems should be able to exploit this variation for significant economic gains. Electricity prices exhibit both temporal and geographic variation, due to regional demand differences, transmission inefficiencies, and generation diversity. Starting with historical electricity prices, for twenty nine locations in the US, and network traffic data collected on Akamai’s CDN, we use simulation to quantify the possible economic gains for a realistic workload. Our results imply that existing systems may be able to save millions of dollars a year in electricity costs, by being cognizant of locational computation cost differences.

  • Randy Baden, Adam Bender, Neil Spring, Bobby Bhattacharjee, and Daniel Starin

    Online social networks (OSNs) are immensely popular, with some claiming over 200 million users [10]. Users share private content, such as personal information or photographs, using OSN applications. Users must trust the OSN service to protect personal information even as the OSN provider benefits from examining and sharing that information.

    We present Persona, an OSN where users dictate who may access their information. Persona hides user data with attribute-based encryption (ABE), allowing users to apply fine-grained policies over who may view their data. Persona provides an effective means of creating applications in which users, not the OSN, define policy over access to private data.

    We demonstrate new cryptographic mechanisms that enhance the general applicability of ABE. We show how Persona provides the functionality of existing online social networks with additional privacy benefits. We describe an implementation of Persona that replicates Facebook applications and show that Persona provides acceptable performance when browsing privacy-enhanced web pages, even on mobile devices.

  • Micah Z. Brodsky and Robert T. Morris

    Carrier sense is often used to regulate concurrency in wireless medium access control (MAC) protocols, balancing interference protection and spatial reuse. Carrier sense is known to be imperfect, and many improved techniques have been proposed. Is the search for a replacement justified? This paper presents a theoretical model for average case two-sender carrier sense based on radio propagation theory and Shannon capacity. Analysis using the model shows that carrier sense performance is surprisingly close to optimal for radios with adaptive bitrate. The model suggests that hidden and exposed terminals usually cause modest reductions in throughput rather than dramatic decreases. Finally, it is possible to choose a fixed sense threshold which performs well across a wide range of scenarios, in large part due to the role of the noise floor. Experimental results from an indoor 802.11 testbed support these claims.

  • Shyamnath Gollakota, Samuel David Perli, and Dina Katabi

    The throughput of existing MIMO LANs is limited by the number of antennas on the AP. This paper shows how to overcome this limita- tion. It presents interference alignment and cancellation (IAC), a new approach for decoding concurrent sender-receiver pairs in MIMO networks. IAC synthesizes two signal processing techniques, inter- ference alignment and interference cancellation, showing that the combination applies to scenarios where neither interference align- ment nor cancellation applies alone. We show analytically that IAC almost doubles the throughput of MIMO LANs. We also implement IAC in GNU-Radio, and experimentally demonstrate that for 2x2 MIMO LANs, IAC increases the average throughput by 1.5x on the downlink and 2x on the uplink.

  • Xi Liu, Anmol Sheth, Michael Kaminsky, Konstantina Papagiannaki, Srinivasan Seshan, and Peter Steenkiste

    The demand for wireless bandwidth in indoor environments such as homes and offices continues to increase rapidly. Although wireless technologies such as MIMO can reach link throughputs of 100s of Mbps (802.11n) for a single link, the question of how we can deliver high throughput to a large number of densely-packed devices remains an open problem. Directional antennas have been shown to be an effective way to increase spatial reuse, but past work has focused largely on outdoor environments where the interactions between wireless links can usually be ignored. This assumption is not acceptable in dense indoor wireless networks since indoor deployments need to deal with rich scattering and multipath effects. In this paper we introduce DIRC, a wireless network design whose access points use phased array antennas to achieve high throughput in dense, indoor environments. The core of DIRC is an algorithm that increases spatial reuse and maximizes overall network capacity by optimizing the orientations of a network of directional antennas. We implemented DIRC and evaluated it on a nine node network in an enterprise setting. Our results show that DIRC improves overall network capacity in indoor environments, while being flexible enough to adapt to node mobility and changing traffic workloads.

  • Ashley Flavel and Matthew Roughan

    Routing oscillation is highly detrimental. It can decrease performance and lead to a high level of update churn placing unnecessary workload on router the problem is distributed between many providers. However, iBGP — the routing protocol used to distribute routes inside a single Autonomous System —has also been shown to oscillate. Despite the fact that iBGP is configured by a single provider according to apparently straight forward rules, more than eight years of research has not solved the problem of iBGP oscillation. Various solutions have been proposed but they all lack critical features: either they are complicated to implement, restrict routing flexibility, or lack guarantees of stability. In this paper we propose a very simple adaptation to the BGP decision process. Despite its simplicity and negligible cost we prove algebraically that it prevents iBGP oscillation. We extend the idea to provide routing flexibility, such as respecting the MED attribute, without sacrificing network stability.

  • Petri Jokela, András Zahemszky, Christian Esteve Rothenberg, Somaya Arianfar, and Pekka Nikander

    A large fraction of today’s Internet applications are internally publish/subscribe in nature; the current architecture makes it cumbersome and inept to support them. In essence, supporting efficient publish/subscribe requires data-oriented naming, efficient multicast, and in-network caching. Deployment of native IP-based multicast has failed, and overlay- based multicast systems are inherently inefficient. We surmise that scalable and efficient publish/subscribe will require substantial architectural changes, such as moving from endpoint-oriented systems to information-centric architectures.

    In this paper, we propose a novel multicast forwarding fabric, suitable for large-scale topic-based publish/subscribe. Due to very simple forwarding decisions and small forwarding tables, the fabric may be more energy efficient than the currently used ones. To understand the limitations and potential, we provide efficiency and scalability analysis via simulations and early measurements from our two implementations. We show that the system scales up to metropolitan WAN sizes, and we discuss how to interconnect separate networks.

  • Lorenzo De Carli, Yi Pan, Amit Kumar, Cristian Estan, and Karthikeyan Sankaralingam

    New protocols for the data link and network layer are being proposed to address limitations of current protocols in terms of scalability, security, and manageability. High-speed routers and switches that implement these protocols traditionally perform packet processing using ASICs which offer high speed, low chip area, and low power. But with inflexible custom hardware, the deployment of new protocols could happen only through equipment upgrades. While newer routers use more flexible network processors for data plane processing, due to power and area constraints lookups in forwarding tables are done with custom lookup modules. Thus most of the proposed protocols can only be deployed with equipment upgrades.

    To speed up the deployment of new protocols, we propose a flexible lookup module, PLUG (Pipelined Lookup Grid). We can achieve generality without loosing efficiency because various custom lookup modules have the same fundamental features we retain: area dominated by memories, simple processing, and strict access patterns defined by the data structure. We implemented IPv4, Ethernet, Ethane, and SEATTLE in our dataflow-based programming model for the PLUG and mapped them to the PLUG hardware which consists of a grid of tiles. Throughput, area, power, and latency of PLUGs are close to those of specialized lookup modules.

  • Yu-Wei Eric Sung, Carsten Lund, Mark Lyn, Sanjay G. Rao, and Subhabrata Sen

    Business and economic considerations are driving the extensive use of service differentiation in Virtual Private Networks (VPNs) operated for business enterprises today. The resulting Class of Service (CoS) designs embed complex policy decisions based on the described priorities of various applications, extent of bandwidth availability, and cost considerations. These inherently complex high-level policies are realized through low-level router configurations. The configuration process is tedious and error-prone given the highly intertwined nature of CoS configuration, the multiple router configurations over which the policies are instantiated, and the complex access control lists (ACLs) involved. Our contributions include (i) a formal approach to modeling CoS policies from router configuration files in a precise manner; (ii) a practical and computationally efficient tool that can determine the CoS treatments received by an arbitrary set of flows across multiple routers; and (iii) a validation of our approach in enabling applications such as troubleshooting, auditing, and visualization of network-wide CoS design, using router configuration data from a cross-section of 150 diverse enterprise VPNs. To our knowledge, this is the first effort aimed at modeling and analyzing CoS configurations.

  • Ajay Anil Mahimkar, Zihui Ge, Aman Shaikh, Jia Wang, Jennifer Yates, Yin Zhang, and Qi Zhao

    IPTV is increasingly being deployed and offered as a commercial service to residential broadband customers. Compared with traditional ISP networks, an IPTV distribution network (i) typically adopts a hierarchical instead of mesh-like structure, (ii) imposes more stringent requirements on both reliability and performance, (iii) has different distribution protocols (which make heavy use of IP multicast) and traffic patterns, and (iv) faces more serious scalability challenges in managing millions of network elements. These unique characteristics impose tremendous challenges in the effective management of IPTV network and service.

    In this paper, we focus on characterizing and troubleshooting performance issues in one of the largest IPTV networks in North America. We collect a large amount of measurement data from a wide range of sources, including device usage and error logs, user activity logs, video quality alarms, and customer trouble tickets. We develop a novel diagnosis tool called Giza that is specifically tailored to the enormous scale and hierarchical structure of the IPTV network. Giza applies multi-resolution data analysis to quickly detect and localize regions in the IPTV distribution hierarchy that are experiencing serious performance problems. Giza then uses several statistical data mining techniques to troubleshoot the identified problems and diagnose their root causes. Validation against operational experiences demonstrates the effectiveness of Giza in detecting important performance issues and identifying interesting dependencies. The methodology and algorithms in Giza promise to be of great use in IPTV network operations.

  • Srikanth Kandula, Ratul Mahajan, Patrick Verkaik, Sharad Agarwal, Jitendra Padhye, and Paramvir Bahl

    By studying trouble tickets from small enterprise networks, we conclude that their operators need detailed fault diagnosis. That is, the diagnostic system should be able to diagnose not only generic faults (e.g., performance-related) but also application specific faults (e.g., error codes). It should also identify culprits at a fine granularity such as a process or firewall configuration. We build a system, called NetMedic, that enables detailed diagnosis by harnessing the rich information exposed by modern operating systems and applications. It formulates detailed diagnosis as an inference problem that more faithfully captures the behaviors and interactions of fine-grained network components such as processes. The primary challenge in solving this problem is inferring when a component might be impacting another. Our solution is based on an intuitive technique that uses the joint behavior of two components in the past to estimate the likelihood of themimpacting one another in the present.We find that our deployed prototype is effective at diagnosing faults that we inject in a live environment. The faulty component is correctly identified as themost likely culprit in 80% of the cases and is almost always in the list of top five culprits.

  • Ramana Rao Kompella, Kirill Levchenko, Alex C. Snoeren, and George Varghese

    Many network applications have stringent end-to-end latency requirements, including VoIP and interactive video conferencing, automated trading, and high-performance computing—where even microsecond variations may be intolerable. The resulting fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing. We propose instrumenting routers with a hash-based primitive that we call a Lossy Difference Aggregator (LDA) to measure latencies down to tens of microseconds and losses as infrequent as one in a million.

    Such measurement can be viewed abstractly as what we refer to as a coordinated streaming problem, which is fundamentally harder than standard streaming problems due to the need to coordinate values between nodes. We describe a compact data structure that efficiently computes the average and standard deviation of latency and loss rate in a coordinated streaming environment. Our theoretical results translate to an efficient hardware implementation at 40 Gbps using less than 1% of a typical 65-nm 400-MHz networking ASIC.When compared to Poisson-spaced active probing with similar overheads, our LDA mechanism delivers orders of magnitude smaller relative error; active probing requires 50–60 times as much bandwidth to deliver similar levels of accuracy.

  • Yin Zhang, Matthew Roughan, Walter Willinger, and Lili Qiu

    Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availability and accuracy of traffic matrices. However, in practice it is challenging to reliably measure traffic matrices. Missing values are common. This observation brings us into the realm of compressive sensing, a generic technique for dealing with missing values that exploits the presence of structure and redundancy in many realworld systems. Despite much recent progress made in compressive sensing, existing compressive-sensing solutions often perform poorly for traffic matrix interpolation, because real traffic matrices rarely satisfy the technical conditions required for these solutions.

    To address this problem, we develop a novel spatio-temporal compressive sensing framework with two key components: (i) a new technique called SPARSITY REGULARIZED MATRIX FACTORIZATION (SRMF) that leverages the sparse or low-rank nature of real-world traffic matrices and their spatio-temporal properties, and (ii) a mechanism for combining low-rank approximations with local interpolation procedures. We illustrate our new framework and demonstrate its superior performance in problems involving interpolation with real traffic matrices where we can successfully replace up to 98% of the values. Evaluation in applications such as network tomography, traffic prediction, and anomaly detection confirms the flexibility and effectiveness of our approach.

  • Pavlos Papageorge, Justin McCann, and Michael Hicks

    We present the Measurement Manager Protocol (MGRP), an in-kernel service that schedules and transmits probes on behalf of active measurement tools. Unlike prior measurement services, MGRP transparently piggybacks application packets inside the often significant amounts of empty padding contained in typical probes. Using MGRP thus combines the modularity, flexibility, and accuracy of standalone active measurement tools with the lower overhead of passive measurement techniques. Microbenchmark experiments show that the resulting bandwidth savings makes it possible to measure the network accurately, but faster and more aggressively than without piggybacking, and with few ill effects to piggybacked application or competing traffic. When using MGRP to schedule measurements on behalf of MediaNet, an overlay service that adaptively schedules media streams, we show MediaNet can achieve significantly higher streaming rates under the same network conditions.

  • Costin Raiciu, Felipe Huici, Mark Handley, and David S. Rosenblum

    To search the web quickly, search engines partition the web index over many machines, and consult every partition when answering a query. To increase throughput, replicas are added for each of these machines. The key parameter of these algorithms is the trade-off between replication and partitioning: increasing the partitioning level improves query completion time since more servers handle the query, but may incur non-negligible startup costs for each subquery. Finding the right operating point and adapting to it can significantly improve performance and reduce costs.

    We introduce Rendezvous On a Ring (ROAR), a novel distributed algorithm that enables on-the-fly re-configuration of the partitioning level. ROAR can add and remove servers without stopping the system, cope with server failures, and provide good load-balancing even with a heterogeneous server pool. We demonstrate these claims using a privacy-preserving search application built upon ROAR.

  • Vijay Vasudevan, Amar Phanishayee, Hiral Shah, Elie Krevat, David G. Andersen, Gregory R. Ganger, Garth A. Gibson, and Brian Mueller

    This paper presents a practical solution to a problem facing high-fan-in, high-bandwidth synchronized TCP workloads in datacenter Ethernets|the TCP incast problem. In these networks, receivers can experience a drastic reduction in application throughput when simultaneously requesting data from many servers using TCP. Inbound data overffills small switch buffers, leading to TCP timeouts lasting hundreds of milliseconds. For many datacenter workloads that have a barrier synchronization requirement (e.g., filesystem reads and parallel data-intensive queries), throughput is reduced by up to 90%. For latency-sensitive applications, TCP timeouts in the datacenter impose delays of hundreds of milliseconds in networks with round-trip-times in microseconds.

    Our practical solution uses high-resolution timers to enable microsecond-granularity TCP timeouts. We demonstrate that this technique is effective in avoiding TCP incast collapse in simulation and in real-world experiments. We show that eliminating the minimum retransmission timeout bound is safe for all environments, including the wide-area.

  • Sharad Agarwal and Jacob R. Lorch

    The latency between machines on the Internet can dramatically affect users’ experience for many distributed applications. Particularly, in multiplayer online games, players seek to cluster themselves so that those in the same session have low latency to each other. A system that predicts latencies between machine pairs allows such matchmaking to consider many more machine pairs than can be probed in a scalable fashion while users are waiting. Using a far-reaching trace of latencies between players on over 3.5 million game consoles, we designed Htrae, a latency prediction system for game matchmaking scenarios. One novel feature of Htrae is its synthesis of geolocation with a network coordinate system. It uses geolocation to select reasonable initial network coordinates for new machines joining the system, allowing it to converge more quickly than standard network coordinate systems and produce substantially lower prediction error than state-of-the-art latency prediction systems. For instance, it produces 90th percentile errors less than half those of iPlane and Pyxida. Our design is general enough to make it a good fit for other latency-sensitive peer-topeer applications besides game matchmaking

  • S. Keshav

    I first attended SIGCOMM in 1989 and recently spent the third week of August 2009 at SIGCOMM, spanning a period of 20 years. Two things strike me about that sentence. The first is that by the inevitable passage of time I seem to have become an ‘old-timer.’ The second is that like everyone else I have conflated the conference and the SIG. This editorial digs deeper into these two facts (and yes, they are related).

    Looking back, what strikes me is that many researchers who I first met in 1989 still take the time to attend, are still active in research and are still making the annual pilgrimage to the conference. It is always a pleasure to run into someone I have met on and off for the better part of two decades.Some colleagues were graduate students like me in 1989 and we reminisce about the old times together. Others were graduate students when I first met them and are now full-fledged researchers. And yet others were students that I had the pleasure of supervising with whom I renew a long-ago relationship that has now turned into a friendship among peers. To see a fresh-faced grad student transition into a leading researcher and a pillar of the community is an unalloyed joy!

    Now to the other thread, of conflating the conference and the SIG. For a long time, I did not think that the SIG had any role to play other than to organize the conference. So it seemed natural to refer to both as SIGCOMM, as most people still do. Actually, I think there is something deeper here. I think what makes SIGCOMM a community is our coming together every year to listen to the same papers, meet fellow researchers, and to participate in shared activities, such as the banquet, the demo and poster sessions, and to cheer and boo at the outrageous opinion session. That is, attending the conference is the act that binds us and makes us a community. It turns out that this technique of creating community is age old: in 600 BCE, the Buddha asked all his followersto gather once a year and re-affirm the tenets of their faith. It worked then and it works now. And that is why the conference and the community are inextricable.Conflating the conference and SIG, however, leads to some problems because there is more to the SIG than SIGCOMM and more to the community than attending the conference. Let me talk first about the other activities of the SIG (do also read Bruce Davie’s editorial in this issue).

    The SIG sponsors several other conferences besides SIGCOMM, such as IMC, HotNets, SenSys, and CoNEXT. It also puts out this newsletter, makes awards, and provides a forum for community discussion by means of a blog and CCR Online. It is now gearing up to provide a forum for industry-academic collaboration through several initiatives. These activities of the SIG allow members to present papers, learn of cuttingedge research in the field, and to get feedback on ideas from their peers.There is more to participating in the community than attending conferences. The SIG is entirely run by volunteers. Volunteer duties include reviewing papers, helping with our website, participating in programcommittees, serving as CCR and ToN area editors, helping in the running of the various conferences, and liaison with the ACM and related communities. If you are interested in any of these, write to the Chair, Bruce Davie, or anyone on the executive committee. We are always happy to hear from you. Of course, some jobs – such as servingon the SIGCOMM TPC – are more sought after than others, but I am sure that anyone who wishes to contribute can.

    Why bother participating? It is not just the joy of doing something to benefit others that gives a warm fuzzy feeling. It is also that volunteers in the community form relationships that are professionally and personally rewarding. If you want to learn about the latest advances in some area whose research leader is a member of SIGCOMM (which is nearly always the case) and you have met that member in the course of your volunteer duties, then you have a way to contact that person and get the inside track. Email from a person you have met and interacted with is much more likely to get responded to than email from a total stranger. Over time, meeting the same people in different roles opens doors to research collaboration, funding, and an added perspective on your research career. Volunteering has its privileges!

    So there you have it. Attending SIGCOMM – the conference – for the last twenty years has made me keenly aware of the SIGCOMM community. I have gained much from being a part of the community. I encourage all of you to participate in the community and make SIGCOMM your own.

  • Xiaolong Li and Homayoun Yousefi'zadeh

    In the recent years, end-to-end feedback-based variants of TCP as well as VCP have emerged as practical alternatives of congestion control by requiring the use of only one or two ECN bits in the IP header. However, all such schemes suffer from a relatively low speed of convergence and exhibit a biased fairness behavior in moderate bandwidth high delay networks due to utilizing an insufficient amount of congestion feedback. In this paper, we propose a novel distributed ECN-based congestion control protocol to which we refer as Multi Packet Congestion Control Protocol (MPCP). In contrast to other alternatives, MPCP is able to relay a more precise congestion feedback yet preserve the utilization of the two ECN bits. MPCP distributes (extracts) congestion related information into (from) a series of n packets, thus allowing for a 2n-bit quantization of congestion measures with each packet carrying two of 2n bits in its ECN bits. We describe the design, implementation, and performance evaluation of MPCP through both simulations and experimental studies.

    Dmitri Krioukov
  • F. Gringoli, Luca Salgarelli, M. Dusi, N. Cascarano, F. Risso, and k. c. claffy

    Much of Internet traffic modeling, firewall, and intrusion detection research requires traces where some ground truth regarding application and protocol is associated with each packet or flow. This paper presents the design, development and experimental evaluation of gt, an open source software toolset for associating ground truth information with Internet traffic traces. By probing the monitored host’s kernel to obtain information on active Internet sessions, gt gathers ground truth at the application level. Preliminary experimental results show that gt’s effectiveness comes at little cost in terms of overhead on the hosting machines. Furthermore, when coupled with other packet inspection mechanisms, gt can derive ground truth not only in terms of applications (e.g., e-mail), but also in terms of protocols (e.g., SMTP vs. POP3).

    Pablo Rodriguez
  • Bruce Davie

    In my first month as SIGCOMM chair, I have been asked “what is your vision for SIGCOMM?”, “can we make SIGCOMM more transparent?”, and “will you write an article for CCR?”. This article is an attempt to address all three of those questions.

  • Barry M. Leiner, Vinton G. Cerf, David D. Clark, Robert E. Kahn, Leonard Kleinrock, Daniel C. Lynch, Jon Postel, Larry G. Roberts, and Stephen Wolff

    This paper was first published online by the Internet Society in December 2003 and is being re-published in ACM SIGCOMM Computer Communication Review because of its historic import. It was written at the urging of its primary editor, the late Barry Leiner. He felt that a factual rendering of the events and activities associated with the development of the early Internet would be a valuable contribution. The contributing authors did their best to incorporate only factual material into this document. There are sure to be many details that have not been captured in the body of the document but it remains one of the most accurate renderings of the early period of development available.

  • k. c. claffy, Marina Fomenkov, Ethan Katz-Bassett, Robert Beverly, Beverly A. Cox, and Matthew Luckie

    Measuring the global Internet is a perpetually challenging task for technical, economic and policy reasons, which leaves scientists as well as policymakers navigating critical questions in their field with little if any empirical grounding. On February 12-13, 2009, CAIDA hosted the Workshop on Active Internet Measurements (AIMS) as part of our series of Internet Statistics and Metrics Analysis (ISMA) workshops which provide a venue for researchers, operators, and policymakers to exchange ideas and perspectives. The two-day workshop included presentations, discussion after each presentation, and breakout sessions focused on how to increase potential and mitigate limitations of active measurements in the wide area Internet. We identified relevant stakeholders who may support and/or oppose measurement, and explored how collaborative solutions might maximize the benefit of research at minimal cost. This report describes the findings of the workshop, outlines open research problems identified by participants, and concludes with recommendations that can benefit both Internet science and communications policy. Slides from workshop presentations are available at http://www.caida.org/workshops/isma/0902/.

  • Ehab Al-Shaer, Albert Greenberg, Charles Kalmanek, David A. Maltz, T. S. Eugene Ng, and Geoffrey G. Xie

    Network management represents an architectural gap in today’s Internet [1]. Many problems with computer networks today, such as faults, misconfiguration, performance degradation, etc., are due to insufficient support for network management, and the problem takes on additional dimensions with the emerging programmable router paradigm. The Internet Network Management Workshop is working to build a community of researchers interested in solving the challenges of network management via a combination of bottoms-up analysis of data from existing networks and a top-down design of new architectures and approaches driven by that data. This editorial sets out some of the research challenges we see facing network management, and calls for participation in working to solve them.

  • Kentaro Toyama and Muneeb Ali

    Poverty and the associated sufferings remain a global challenge, with over a billion people surviving on less than a dollar a day. Technology, applied appropriately, can help improve their lives. Despite some clear examples of technical research playing a key role in global development, there is a question that repeatedly arises in this area: can technologies for developing regions be considered a core area of computer science research? In this note, we examine some of the arguments on both sides of this question, deliberately avoid answering the question itself (for the lack of community consensus), and provide some suggestions for the case where the answer is in the affirmative.

  • Dirk Trossen

    While many initiatives have been discussing the future of the Internet, the EIFFEL1 think tank set out to push these discussions forward by assembling a community of researchers debating the potential thrusts towards the Future Internet. This article provides an account of these discussions, being addressed both to the EIFFEL membership and more widely to members of the community interested in medium to long-term developments. We outline immediate problems as well as potentially missed opportunities in the current Internet, while focussing the debate on the need for a Future Internet on the style we conduct research as well as how we design systems at large. Most importantly, we recognize that an inter-disciplinary dialogue is required to formulate actions to be taken and to remove barriers to their realization.

  • Richard Gass and Christophe Diot

    Increasing popularity in personal access points and travel routers has begun to rise with the advent of smaller and more battery conscious devices. This article introduces the YAAP (Yet Another Access Point), an open source software that enables ad-hoc infrastructure services in the absence of network connectivity. The YAAP provides a familiar way to connect users to each other and provides a set of useful services. We list and describe its applications, explain how it can be used, provide details about the code, and point readers to where it can be downloaded.

  • S. Keshav

    As a member of the SIGCOMM TPC, I recently had a chance to read over thirty submissions by the best and brightest in our field. Imagine my surprise to find that all but one of them had significant flaws in statistical analysis. These flaws were severe enough that in many other disciplines the papers would have been summarily rejected. Yet, a few of them not only were accepted but also are likely to become role models for the next generation of students. For, though statistically flawed, they were not far from common practice, so it was felt that they should not be unfairly punished.

    In this editorial, I will focus on why statistical analysis matters, three common statistical errors I saw, why I think we have a rather relaxed approach to statistical analysis, and what we can do about it.

    In conducting experiments, only the most trivial situations allow a comprehensive exploration of the underlying parameter space: simulations and measurements alike allow us to explore only a small portion of the space. One role of statistical analysis is guide the selection of the parameter space using techniques from experimental design.

    A second role of statistical analysis is to allow a researcher to draw cautious and justifiable conclusions from a mass of numbers. Over a hundred years of work has created tried-and-tested techniques that allow researchers to compensate for unavoidable measurement errors, and to infer with high probability that the improvement seen due a particular algorithm or system is significant, rather than due to mere luck. Without statistical analysis, one is on thin ice.

    These two roles of statistical analysis make it an essential underpinning for networking research, especially for experimental design, measurement, and performance analysis. Unfortunately, despite its importance, papers in our field--both submissions to SIGCOMM and published papers in similar top-tier conferences--suffer from severe statistical errors. The three most common errors I found were: (1) confusing a sample with a population and, as a corollary, not specifying the underlying population (2) not presenting confidence intervals for sample statistics and (3) incorrect hypothesis testing.

    Most authors did not seem to realize that their measurements represented a sample from a much larger underlying population. Consider the measured throughput during ten runs between two nodes using a particular wireless protocol. These values are a sample of the population of node-to-node throughputs obtained using all possible uses of the protocol under all conceivable circumstances. Wireless performance may, however, vary widely depending on the RF environment. Therefore, the sample can be considered to be representative only if every likely circumstance has a proportionate chance of being represented. Authors need to strongly argue that the sample measurements are chosen in a way that sufficiently covers the underlying parameter space. Otherwise, the sample represents nothing more than itself! Yet, this test for scientific validity was rarely discussed in most papers.

    Given that a sample is not the population, it is imperative that the statistics of a sample be presented along with a confidence interval in which, with high confidence, the population parameters lie. These are the familiar error bars in a typical graph or histogram. Lacking error bars, we cannot interpret the characteristics of the population with any precision; we can only draw conclusions about the sample, which is necessarily limited. To my surprise, only one paper I read had error bars. This is a serious flaw.

    Finally, it is axiomatic in statistical analysis that a hypothesis cannot be proved; it can only rejected or not rejected. Hypothesis testing requires carefully framing a null hypothesis and using standard statistical analysis to either reject or not reject it. I realize that in many cases the null hypothesis is obvious and need not be formally stated. Nevertheless, it appeared that none of the papers I read had tested hypotheses with adequate care.

    Why do papers in our field lack statistical rigor? I think that one reason could be that we teach statistics too early in the academic curriculum. Students who learn statistical inference and hypothesis testing as a chore in a freshman class have all but forgotten it by the time they are writing papers. In my own case, I am embarrassed to admit that I did not thoroughly understand these techniques until I recently wrote a chapter on statistical techniques for networking researchers. I suspect that many of my colleagues are in the same boat. Unfortunately, this makes our weakness self-perpetuating. Having forgotten statistical analysis, we are neither in a position to carry it out properly, nor do we insist upon it during peer review. Thus, we stumble from one flawed paper to the next, continuing the cycle.

    What can we do about this? I suggest that all graduate students be required to take a course on statistical analysis. This need not be a formal course, but could be taken online or using distance education. The concepts are well known and the techniques are explained in numerous textbooks. We just need to buy into the agenda. Second, I think that we need to raise the bar during paper evaluation. Inadequate statistical analysis should be pointed out and should form one criterion for paper rejection. For papers with good experimental results but with poor statistical analysis, we should insist that these issues be rectified during shepherding. Finally, we need to educate the educators. Perhaps SIGCOMM can sponsor online or offline tutorials where researchers can quickly come up to speed in statistical analysis.

    These steps will raise the scientific merit of our discipline, and, more importantly, prevent us from accepting incorrect results due to flaws in statistical analysis.

  • Dragana Damjanovic and Michael Welzl

    When data transfers to or from a host happen in parallel, users do not always consider them to have the same importance. Ideally, a transport protocol should therefore allow its users to manipulate the fairness among ows in an almost arbitrary fashion. Since data transfers can also include real-time media streams which need to keep delay - and hence buffers - small, the protocol should also have a smooth sending rate. In an effort to satisfy the above requirements, we present MulTFRC, a congestion control mechanism which is based on the TCP-friendly Rate Control (TFRC) protocol. It emulates the behavior of a number of TFRC ows while maintaining a smooth sending rate. Our simulations and a real-life test demonstrate that MulTFRC performs significantly better than its competitors, potentially making it applicable in a broader range of settings than what TFRC is normally associated with.

    Darryl Veitch
  • Alice Este, Francesco Gringoli, and Luca Salgarelli

    This paper presents a statistical analysis of the amount of information that the features of traffic flows observed at the packet-level carry, with respect to the protocol that generated them. We show that the amount of information of the majority of such features remain constant irrespective of the point of observation (Internet core vs. Internet edge) and to the capture time (year 2000/01 vs. year 2008). We also describe a comparative analysis of how four statistical classifiers fare using the features we studied.

    Konstantina Papagiannaki
  • Don Bowman

    The Internet is a primary engine of innovation, communication, and entertainment in our society. It is used by diverse and potentially conflicting interests. When these interests collide in the form of technology, should the Internet stay true to its roots and let things take their course naturally, or should regulation and legislation be enacted to control what may or may not be done. This author believes public opinion is best served by light regulation and a strong focus on allowing technological innovation to take its natural course.

  • Romain Kuntz, Antoine Gallais, and Thomas Noel

    Although research on algorithms and communication pro- tocols in Wireless Sensor Networks (WSN) has yielded a tremendous effort so far, most of these protocols are hardly used in real deployments nowadays. Several reasons have been put forward in recent publications. In this paper, we further investigate this trend from a Medium Access Control (MAC) perspective by analyzing both the reasons behind successful deployments and the characteristics of the MAC layers proposed in the literature. Although research on algorithms and communication protocols in Wireless Sensor Networks (WSN) has yielded a tremendous effort so far, most of these protocols are hardly used in real deployments nowadays. Several reasons have been put forward in recent publications. In this paper, we further investigate this trend from a Medium Access Control (MAC) perspective by analyzing both the reasons behind successful deployments and the characteristics of the MAC layers proposed in the literature. The effort allocated to develop suitable protocols from scratch every new deployment could however be minimized by using already existing contributions which provide code reuse and adaptive protocols. Though we advocate their use for nowadays deployments, we have identified several shortcomings in foreseen scenarios for which we provide guidelines for future researches.

  • Chip Elliott and Aaron Falk

    In this paper we discuss the current status of the Global Environment for Network Innovations. Early prototypes of GENI are starting to come online as an end-to-end system and network researchers are invited to participate by engaging in the design process or using GENI to conduct experiments.

  • Deep Medhi and Peter A. Freeman

    A US-JapanWorkshop on Future Networks was held in Palo Alto, CA on October 31 - November 1, 2008. This workshop brought together leading US and Japanese network researchers and network research infrastructure developers who are interested in future networks. The focus was on research issues and experimental infrastructure to support research on future generation networks. The goal was to foster cooperation and communication between peers in the two countries. Through this workshop, a number of research challenges were identified. The workshop also made recommendations to: create a new funding mechanism to foster special collaborations in networking and experimentation, extend current national testbeds with international connectivity; and urge the respective governments to exert strong leadership to ensure that collaborative research for creating future networks is carried out.

  • Henning Schulzrinne

    As the community develops an ever more diverse set of venues for disseminating and discussing technical work and as the traditional resource constraints change from pages and shelf space to reviewer time, the traditional prohibition against double submission deserves closer consideration. We discuss reasons why double submissions have been frowned upon, and try to establish a set of guidelines that ensure appropriate review and dissemination, without preventing informal early discussion of research projects.

  • Konstantina Papagiannaki and Luigi Rizzo

    Selecting a technical program for a conference, and running the process so that decisions are well received by authors and participants, is a challenging task. We report our experience in running the SIGCOMM 2009 Technical Program Committee (TPC). The purpose of this article is to document the process that we followed, and discuss it critically. This should let authors get a better understanding of what led to the final acceptance or rejection of their work, and hopefully let other

  • Michalis Faloutsos

    “Don’t even get me started” is a powerful and direct, yet vague and meaningless, expression. What if you reply: “By all means, please, get started”. I believe that this will stun your opponent (it may be a friendly discussion, but if you don’t believe the other person is an opponent, you will never win.). Then, you can quickly grab his/her nose and yell: ”Twos before eights, and one bird in the bush”. It can be very entertaining unless the other person is your boss or your psychiatrist. In any case, this column dares to go where no column at CCR has gone before. It is all about getting started. And by that, we mean starting start-ups.

    Warning: the content below is not suitable for small children or adults with common sense.

  • S. Keshav

    We are living in the worst economic times since the 1930s. The US economy contracted at an annualized rate of 3.8% in the fourth quarter of 2008, the corresponding figure for Japan is 12.7%, and Iceland may become the first post-depression Western economy to suffer from an outright fiscal collapse. Economists tell us that one of the reasons for this worldwide recession is a ‘housing bubble’ where banks overestimated a borrower's ability to pay back a loan and where house buyers – armed with cheap loans – overestimated the true worth of a house.

    The recent Internet bubble is still fresh in some of our minds, where there was a similar overestimation of the true worth of Internet-enabled businesses. That bubble crashed too, with consequences suffered by the entire economy.

    Unfortunately, bubbles are not uncommon in networking research. Certain topics appear seemingly from nowhere, become ‘hot,’ propelled by interest from both leading researchers and funding agencies, and just as mysteriously die off, leaving behind a flood of papers, mostly in second- and third-tier conferences, written by authors only too keen to jump on a trend. Bubbles lead to an overexpenditure of research effort on marginal topics, wasting resources and breeding a certain degree of cynicism amongst our brightest young minds. Moreover, they drain resources from more deserving but less hyped ventures. Can our experience with economic bubbles shed light on research bubbles and teach us how to avoid them?

    Both economic and research bubbles share some similarities, such as having unrealistic expectations about what can be achieved by a company, the real-estate market, or a new technology. Bubble participants either naively or cynically invest time and money in solutions and technologies whose success is far from assured and whose widespread adoption would require the complete overthrow of legacy infrastructure. To avoid being caught in a bubble, or to merely avoid being caught in the tail end of one (being at the leading edge of a bubble is both fun and profitable!), ask tough questions about the underlying assumptions. In the midst of the housing bubble, could one point out housing prices could down as easily as they could go up? Could anyone have believed in the ’90s that videoconferencing, ATM, RSVP and other 'hot' topics would soon be consigned to the midden heap of history? I think so. It only requires the willingness to question every assumption and draw the inevitable conclusions.

    I think that in the end, what really inflates a bubble is money. Cheap money from venture capitalists, banks, and funding agencies makes it profitable to enter a bubble and make it grow. So it is important that the gatekeepers of funding be vigilant. They should be prepared to turn down applications for funding that smack of riding the bubble. Experienced researchers should willingly serve on grant panels, then should be prepared to be critical with even their favourite areas of research if necessary.

    Finally, bubbles can be identified and quashed by an active media. The press should have more deeply questioned the Internet and housing bubbles. Research conferences in our field should do the same for research bubbles. Paper reviewers and program committees thus play the same role as investigative journalists.

    This is not to say that all speculative ideas should be systematically de-funded and rejected. There should always be room for open-minded, blue-sky research. However, this activity should be limited and clearly identified. Perhaps every conference should have blue-sky sessions where all assumptions are left unchallenged (our community has done this with recent papers on ‘cleanslate’ designs). The best of these ideas, when proven to be sound, could then be funded and widely adopted.

    Of course, I am assuming that that we can get out of bubbles by rational means. Humans are all too fallible, however, and bubble thinking plays on human foibles. Worse, there is an incentive structure that encourages bubble formation: people at the leading edge of a bubble are disproportionately rewarded and people at the tail end can point to large body of literature (emerging from top-ranked places!) to justify their work, which reduces their cognitive effort. So, bubbles may be here to stay.

    Nevertheless, given the destructive effects of bubbles over the long term, I suggest that we look out for them, deflating them before they deflate us!

  • Brian E. Carpenter

    This paper reports some observations on the relationships between three measures of the size of the Internet over more than ten years. The size of the BGP4 routing table, the number of active BGP4 Autonomous Systems, and a lower bound on the total size of the Internet, appear to have fairly simple relationships despite the Internet’s growth by two orders of magnitude. In particular, it is observed that the size of the BGP4 system appears to have grown approximately in proportion to the square root of the lower-bound size of the globally addressable Internet. A simple model that partially explains this square law is described. It is not suggested that this observation and model have predictive value, since they cannot predict qualitative changes in the Internet topology. However, they do offer a new way to understand and monitor the scaling of the BGP4 system.

    Michalis Faloutsos
Syndicate content