Computer Communication Review: Papers

Find a CCR issue:
  • Sangjin Han, Keon Jang, KyoungSoo Park, and Sue Moon

    We present PacketShader, a high-performance software router framework for general packet processing with Graphics Processing Unit (GPU) acceleration. PacketShader exploits the massively-parallel processing power of GPU to address the CPU bottleneck in current software routers. Combined with our high-performance packet I/O engine, PacketShader outperforms existing software routers by more than a factor of four, forwarding 64B IPv4 packets at 39 Gbps on a single commodity PC. We have implemented IPv4 and IPv6 forwarding, OpenFlow switching, and IPsec tunneling to demonstrate the flexibility and performance advantage of PacketShader. The evaluation results show that GPU brings significantly higher throughput over the CPU-only implementation, confirming the effectiveness of GPU for computation and memory-intensive operations in packet processing.

  • Balajee Vamanan, Gwendolyn Voskuilen, and T. N. Vijaykumar

    Packet Classification is a key functionality provided by modern routers. Previous decision-tree algorithms, HiCuts and HyperCuts, cut the multi-dimensional rule space to separate a classifier’s rules. Despite their optimizations, the algorithms incur considerable memory overhead due to two issues: (1) Many rules in a classifier overlap and the overlapping rules vary vastly in size, causing the algorithms’ fine cuts for separating the small rules to replicate the large rules. (2) Because a classifier’s rule-space density varies significantly, the algorithms’ equi-sized cuts for separating the dense parts needlessly partition the sparse parts, resulting in many ineffectual nodes that hold only a few rules. We propose EffiCuts which employs four novel ideas: (1) Separable trees: To eliminate overlap among small and large rules, we separate all small and large rules. We define a subset of rules to be separable if all the rules are either small or large in each dimension. We build a distinct tree for each such subset where each dimension can be cut coarsely to separate the large rules, or finely to separate the small rules without incurring replication. (2) Selective tree merging: To reduce the multiple trees’ extra accesses which degrade throughput, we selectively merge separable trees mixing rules that may be small or large in at most one dimension. (3) Equi-dense cuts: We employ unequal cuts which distribute a node’s rules evenly among the children, avoiding ineffectual nodes at the cost of a small processing overhead in the tree traversal. (4) Node Co-location: To achieve fewer accesses per node than HiCuts and HyperCuts, we co-locate parts of a node and its children. Using ClassBench, we show that for similar throughput EffiCuts needs factors of 57 less memory than HyperCuts and of 4-8 less power than TCAM.

  • Franck Le, Geoffrey G. Xie, and Hui Zhang

    Recent studies have shown that the current primitives for connecting multiple routing protocol instances (OSPF 1, OSPF 2, EIGRP 10, etc.) are pervasively deployed in enterprise networks and the Internet. Furthermore, these primitives are extremely vulnerable to routing anomalies (route oscillations, forwarding loops, etc.) and at the same time too rigid to support some of today’s operational objectives. In this paper, we propose a new theory to reason about routing properties across multiple routing instances. The theory directly applies to both link-state and vector routing protocols. Each routing protocol still makes independent routing decisions and may consider a combination of routing metrics, including bandwidth, delay, cost, and reliability. While the theory permits a range of solutions, we focus on a design that requires no changes to existing routing protocols. Guided by the theory, we derive a new set of connecting primitives, which are not only provably safe but also more expressive than the current version. We have implemented and validated the new primitives using XORP. The results confirm that our design can support a large range of desirable operational goals, including those not achievable today, safely and with little manual configuration.

  • Patrick Wendell, Joe Wenjie Jiang, Michael J. Freedman, and Jennifer Rexford

    Geo-replicated services need an effective way to direct client requests to a particular location, based on performance, load, and cost. This paper presents DONAR, a distributed system that can offload the burden of replica selection, while providing these services with a sufficiently expressive interface for specifying mapping policies. Most existing approaches for replica selection rely on either central coordination (which has reliability, security, and scalability limitations) or distributed heuristics (which lead to suboptimal request distributions, or even instability). In contrast, the distributed mapping nodes in DONAR run a simple, efficient algorithm to coordinate their replica-selection decisions for clients. The protocol solves an optimization problem that jointly considers both client performance and server load, allowing us to show that the distributed algorithm is stable and effective. Experiments with our DONAR prototype—providing replica selection for CoralCDN and the Measurement Lab—demonstrate that our algorithm performs well “in the wild.” Our prototype supports DNS- and HTTP-based redirection, IP anycast, and a secure update protocol, and can handle many customer services with diverse policy objectives.

  • Mohammad Hajjat, Xin Sun, Yu-Wei Eric Sung, David Maltz, Sanjay Rao, Kunwadee Sripanidkulchai, and Mohit Tawarmalani

    In this paper, we tackle challenges in migrating enterprise services into hybrid cloud-based deployments, where enterprise operations are partly hosted on-premise and partly in the cloud. Such hybrid architectures enable enterprises to benefit from cloud-based architectures, while honoring application performance requirements, and privacy restrictions on what services may be migrated to the cloud. We make several contributions. First, we highlight the complexity inherent in enterprise applications today in terms of their multi-tiered nature, large number of application components, and interdependencies. Second, we have developed a model to explore the benefits of a hybrid migration approach. Our model takes into account enterprise-specific constraints, cost savings, and increased transaction delays and wide-area communication costs that may result from the migration. Evaluations based on real enterprise applications and Azure-based cloud deployments show the benefits of a hybrid migration approach, and the importance of planning which components to migrate. Third, we shed insight on security policies associated with enterprise applications in data centers. We articulate the importance of ensuring assurable reconfiguration of security policies as enterprise applications are migrated to the cloud. We present algorithms to achieve this goal, and demonstrate their efficacy on realistic migration scenarios.

  • Xin Liu, Xiaowei Yang, and Yong Xia

    Denial of Service (DoS) attacks frequently happen on the Internet, paralyzing Internet services and causing millions of dollars of financial loss. This work presents NetFence, a scalable DoSresistant network architecture. NetFence uses a novel mechanism, secure congestion policing feedback, to enable robust congestion policing inside the network. Bottleneck routers update the feedback in packet headers to signal congestion, and access routers use it to police senders’ traffic. Targeted DoS victims can use the secure congestion policing feedback as capability tokens to suppress unwanted traffic. When compromised senders and receivers organize into pairs to congest a network link, NetFence provably guarantees a legitimate sender its fair share of network resources without keeping per-host state at the congested link. We use a Linux implementation, ns-2 simulations, and theoretical analysis to show that NetFence is an effective and scalable DoS solution: it reduces the amount of state maintained by a congested router from per-host to at most per-(Autonomous System).

  • Fernando Silveira, Christophe Diot, Nina Taft, and Ramesh Govindan

    When many flows are multiplexed on a non-saturated link, their volume changes over short timescales tend to cancel each other out, making the average change across flows close to zero. This equilibrium property holds if the flows are nearly independent, and it is violated by traffic changes caused by several, potentially small, correlated flows. Many traffic anomalies (both malicious and benign) fit this description. Based on this observation, we exploit equilibrium to design a computationally simple detection method for correlated anomalous flows. We compare our new method to two well known techniques on three network links. We manually classify the anomalies detected by the three methods, and discover that our method uncovers a different class of anomalies than previous techniques do.

  • Zhichun Li, Gao Xia, Hongyu Gao, Yi Tang, Yan Chen, Bin Liu, Junchen Jiang, and Yuezhou Lv

    Accuracy and speed are the two most important metrics for Network Intrusion Detection/Prevention Systems (NIDS/NIPSes). Due to emerging polymorphic attacks and the fact that in many cases regular expressions (regexes) cannot capture the vulnerability conditions accurately, the accuracy of existing regex-based NIDS/NIPS systems has become a serious problem. In contrast, the recently-proposed vulnerability signatures [10, 29] (a.k.a. data patches) can exactly describe the vulnerability conditions and achieve better accuracy. However, how to efficiently apply vulnerability signatures to high speed NIDS/NIPS with a large ruleset remains an untouched but challenging issue.

    This paper presents the first systematic design of vulnerability signature based parsing and matching engine, NetShield, which achieves multi-gigabit throughput while offering much better accuracy. Particularly, we made the following contributions: (i) we proposed a candidate selection algorithm which efficiently matches thousands of vulnerability signatures simultaneously requiring a small amount of memory; (ii) we proposed an automatic lightweight parsing state machine achieving fast protocol parsing. Experimental results show that the core engine of NetShield achieves at least 1.9+Gbps signature matching throughput on a 3.8GHz single-core PC, and can scale-up to at least 11+Gbps under a 8-core machine for 794 HTTP vulnerability signatures. We release our prototype and sample signatures at www.nshield.org.

  • Ye Wang, Hao Wang, Ajay Mahimkar, Richard Alimi, Yin Zhang, Lili Qiu, and Yang Richard Yang

    Network resiliency is crucial to IP network operations. Existing techniques to recover from one or a series of failures do not offer performance predictability and may cause serious congestion. In this paper, we propose Resilient Routing Reconfiguration (R3), a novel routing protection scheme that is (i) provably congestionfree under a large number of failure scenarios; (ii) efficient by having low router processing overhead and memory requirements; (iii) flexible in accommodating different performance requirements (e.g., handling realistic failure scenarios, prioritized traffic, and the trade-off between performance and resilience); and (iv) robust to both topology failures and traffic variations. We implement R3 on Linux using a simple extension of MPLS, called MPLS-ff. We conduct extensive Emulab experiments and simulations using realistic network topologies and traffic demands. Our results show that R3 achieves near-optimal performance and is at least 50% better than the existing schemes under a wide range of failure scenarios.

  • Ajay Anil Mahimkar, Han Hee Song, Zihui Ge, Aman Shaikh, Jia Wang, Jennifer Yates, Yin Zhang, and Joanne Emmons

    Networks continue to change to support new applications, improve reliability and performance and reduce the operational cost. The changes are made to the network in the form of upgrades such as software or hardware upgrades, new network or service features and network configuration changes. It is crucial to monitor the network when upgrades are made because they can have a significant impact on network performance and if not monitored may lead to unexpected consequences in operational networks. This can be achieved manually for a small number of devices, but does not scale to large networks with hundreds or thousands of routers and extremely large number of different upgrades made on a regular basis.

    In this paper, we design and implement a novel infrastructure MERCURY for detecting the impact of network upgrades (or triggers) on performance. MERCURY extracts interesting triggers from a large number of network maintenance activities. It then identifies behavior changes in network performance caused by the triggers. It uses statistical rule mining and network configuration to identify commonality across the behavior changes. We systematically evaluate MERCURY using data collected at a large tier-1 ISP network. By comparing to operational practice, we show that MERCURY is able to capture the interesting triggers and behavior changes induced by the triggers. In some cases, MERCURY also discovers previously unknown network behaviors demonstrating the effectiveness in identifying network conditions flying under the radar.

  • Daniel Turner, Kirill Levchenko, Alex C. Snoeren, and Stefan Savage

    Of the major factors affecting end-to-end service availability, network component failure is perhaps the least well understood. How often do failures occur, how long do they last, what are their causes, and how do they impact customers? Traditionally, answering questions such as these has required dedicated (and often expensive) instrumentation broadly deployed across a network.

    We propose an alternative approach: opportunistically mining “low-quality” data sources that are already available in modern network environments. We describe a methodology for recreating a succinct history of failure events in an IP network using a combination of structured data (router configurations and syslogs) and semi-structured data (email logs). Using this technique we analyze over five years of failure events in a large regional network consisting of over 200 routers; to our knowledge, this is the largest study of its kind.

  • Guohui Wang, David G. Andersen, Michael Kaminsky, Konstantina Papagiannaki, T.S. Eugene Ng, Michael Kozuch, and Michael Ryan

    Data-intensive applications that operate on large volumes of data have motivated a fresh look at the design of data center networks. The first wave of proposals focused on designing pure packetswitched networks that provide full bisection bandwidth. However, these proposals significantly increase network complexity in terms of the number of links and switches required and the restricted rules to wire them up. On the other hand, optical circuit switching technology holds a very large bandwidth advantage over packet switching technology. This fact motivates us to explore how optical circuit switching technology could benefit a data center network. In particular, we propose a hybrid packet and circuit switched data center network architecture (or HyPaC for short) which augments the traditional hierarchy of packet switches with a high speed, low complexity, rack-to-rack optical circuit-switched network to supply high bandwidth to applications. We discuss the fundamental requirements of this hybrid architecture and their design options. To demonstrate the potential benefits of the hybrid architecture, we have built a prototype system called c-Through. c-Through represents a design point where the responsibility for traffic demand estimation and traffic demultiplexing resides in end hosts, making it compatible with existing packet switches. Our emulation experiments show that the hybrid architecture can provide large benefits to unmodified popular data center applications at a modest scale. Furthermore, our experimental experience provides useful insights on the applicability of the hybrid architecture across a range of deployment scenarios.

  • Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat

    The basic building block of ever larger data centers has shifted from a rack to a modular container with hundreds or even thousands of servers. Delivering scalable bandwidth among such containers is a challenge. A number of recent efforts promise full bisection bandwidth between all servers, though with significant cost, complexity, and power consumption. We present Helios, a hybrid electrical/optical switch architecture that can deliver significant reductions in the number of switching elements, cabling, cost, and power consumption relative to recently proposed data center network architectures. We explore architectural trade offs and challenges associated with realizing these benefits through the evaluation of a fully functional Helios prototype.

  • Minlan Yu, Jennifer Rexford, Michael J. Freedman, and Jia Wang

    Ideally, enterprise administrators could specify fine-grain policies that drive how the underlying switches forward, drop, and measure traffic. However, existing techniques for flow based networking rely too heavily on centralized controller software that installs rules reactively, based on the first packet of each flow. In this paper, we propose DIFANE, a scalable and efficient solution that keeps all traffic in the data plane by selectively directing packets through intermediate switches that store the necessary rules. DIFANE relegates the controller to the simpler task of partitioning these rules over the switches. DIFANE can be readily implemented with commodity switch hardware, since all data-plane functions can be expressed in terms of wildcard rules that perform simple actions on matching packets. Experiments with our prototype on Click-based OpenFlow switches show that DIFANE scales to larger networks with richer policies.

  • Bimal Viswanath, Ansley Post, Krishna P. Gummadi, and Alan Mislove

    Recently, there has been much excitement in the research community over using social networks to mitigate multiple identity, or Sybil, attacks. A number of schemes have been proposed, but they differ greatly in the algorithms they use and in the networks upon which they are evaluated. As a result, the research community lacks a clear understanding of how these schemes compare against each other, how well they would work on real-world social networks with different structural properties, or whether there exist other (potentially better) ways of Sybil defense.

    In this paper, we show that, despite their considerable differences, existing Sybil defense schemes work by detecting local communities (i.e., clusters of nodes more tightly knit than the rest of the graph) around a trusted node. Our finding has important implications for both existing and future designs of Sybil defense schemes. First, we show that there is an opportunity to leverage the substantial amount of prior work on general community detection algorithms in order to defend against Sybils. Second, our analysis reveals the fundamental limits of current social network-based Sybil defenses: We demonstrate that networks with well-defined community structure are inherently more vulnerable to Sybil attacks, and that, in such networks, Sybils can carefully target their links in order make their attacks more effective.

  • Josep M. Pujol, Vijay Erramilli, Georgos Siganos, Xiaoyuan Yang, Nikos Laoutaris, Parminder Chhabra, and Pablo Rodriguez

    The difficulty of scaling Online Social Networks (OSNs) has introduced new system design challenges that has often caused costly re-architecting for services like Twitter and Facebook. The complexity of interconnection of users in social networks has introduced new scalability challenges. Conventional vertical scaling by resorting to full replication can be a costly proposition. Horizontal scaling by partitioning and distributing data among multiples servers – e.g. using DHTs – can lead to costly inter-server communication.

    We design, implement, and evaluate SPAR, a social partitioning and replication middle-ware that transparently leverages the social graph structure to achieve data locality while minimizing replication. SPAR guarantees that for all users in an OSN, their direct neighbor’s data is co-located in the same server. The gains from this approach are multi-fold: application developers can assume local semantics, i.e., develop as they would for a single server; scalability is achieved by adding commodity servers with low memory and network I/O requirements; and redundancy is achieved at a fraction of the cost.

    We detail our system design and an evaluation based on datasets from Twitter, Orkut, and Facebook, with a working implementation. We show that SPAR incurs minimum overhead, and can help a well-known open-source Twitter clone reach Twitter’s scale without changing a line of its application logic and achieves higher throughput than Cassandra, Facebook’s DHT based key-value store database.

  • David R. Choffnes, Fabián E. Bustamante, and Zihui Ge

    The user experience for networked applications is becoming a key benchmark for customers and network providers. Perceived user experience is largely determined by the frequency, duration and severity of network events that impact a service. While today’s networks implement sophisticated infrastructure that issues alarms for most failures, there remains a class of silent outages (e.g., caused by configuration errors) that are not detected. Further, existing alarms provide little information to help operators understand the impact of network events on services. Attempts to address this through infrastructure that monitors end-to-end performance for customers have been hampered by the cost of deployment and by the volume of data generated by these solutions.

    We present an alternative approach that pushes monitoring to applications on end systems and uses their collective view to detect network events and their impact on services - an approach we call Crowdsourcing Event Monitoring (CEM). This paper presents a general framework for CEM systems and demonstrates its effectiveness for a P2P application using a large dataset gathered from BitTorrent users and confirmed network events from two ISPs. We discuss how we designed and deployed a prototype CEM implementation as an extension to BitTorrent. This system performs online service-level network event detection through passive monitoring and correlation of performance in end-users’ applications.

  • S. Keshav

    When I took my oral qualifying exam at Berkeley many years ago, my seniors told me that if I made it past the assumptions slide, I would pass. Assumptions are the foundations on which a dissertation is built and the examining committee subjects a candidate’s assumptions to harsh analysis. If the assumptions are correct, then the rest of the dissertation, even if flawed, is correctible. Nothing can rescue a dissertation built on incorrect assumptions.

    What is true for dissertations at Berkeley is just as true for presentations, papers, and indeed your research career. It is supremely important to ensure that assumptions underlying your work are sound.

    Unfortunately, there is an inherent problem in validating your assumptions. If you are both making the assumptions and validating them, then it is likely that you are going to be biased in your evaluation. So, you may overlook a flaw that a more critical eye could easily discern. That is the reason why I think it is a good idea to frequently subject your ideas to open inspection by a critical audience. You can do this by giving talks or by talking to your peers one-on-one. The more directly your assumptions are questioned the better. If your assumptions can survive several rounds of criticism then you can be relatively certain of their validity.

    For our discipline to progress, it is important that both ends of the bargain be kept. Researchers should share their ideas openly and be prepared to defend their assumptions. And, as a listener and critic, you should dissect and criticize the assumptions in the talks that you hear and the papers that you read.

    As an aside, I know that I may not always be a welcome member of some audiences because I pull no punches in my skewering of what, to me, appear to be incorrect assumptions. For the record, this is never personal: I am playing my role as a critic in what think is in the best scientific tradition. I will paraphrase the great Hamming to state that scientists should attend talks not to congratulate the speaker but tear them apart!

    Which brings me back to the papers in CCR. As you read, do take the time to think through whether the assumptions make sense. Our reviewers and editors do as thorough a job as they can, but the onus is still upon you. Do also read the public review of a paper, where the Area Editor discusses the pros and cons of each technical paper. This will help you understand the assumptions with which an Area Editor agrees or disagrees. Remember that CCR Online is available for your comments and discussion. Of course, you can also write to an author directly with your questions and constructive criticism.

  • László Gyarmati and Tuan Anh Trinh

    Data centers have a crucial role in current Internet architecture supporting content-centric networking. State-of-theart data centers have different architectures like fat-tree, DCell, or BCube. However, their architectures share a common property: symmetry. Due to their symmetric nature, a tricky point with these architectures is that they are hard to be extended in small quantities. Contrary to state-of-the-art data center architectures, we propose an asymmetric data center topology generation method called Scafida inspired by scale-free networks; these data centers have not only small diameters and high fault tolerance, inherited by scale-free networks, but can also be scaled in smaller and less homogenous increments. We extend the original scale-free network generation algorithm of Barabási and Albert to meet the physical constraints of switches and routers. Despite the fact that our method artificially limits the node degrees in the network, our data center architectures keep the preferable properties of scale-free networks. Based on extensive simulations we present preliminary results that are promising regarding the error tolerance, scalability, and flexibility of the architecture.

    S. Agarwal
  • Igor Ganichev, Bin Dai, P. Brighten Godfrey, and Scott Shenker

    Multipath routing is a promising technique to increase the Internet’s reliability and to give users greater control over the service they receive. However, past proposals choose paths which are not guaranteed to have high diversity. In this paper, we propose yet another multipath routing scheme (YAMR) for the interdomain case. YAMR provably constructs a set of paths that is resilient to any one inter-domain link failure, thus achieving high reliability in a systematic way. Further, even though YAMR maintains more paths than BGP, it actually requires significantly less control traffic, thus alleviating instead of worsening one of the Internet’s scalability problems. This reduction in churn is achieved by a novel hiding technique that automatically localizes failures leaving the greater part of the Internet completely oblivious.

    J. Wang
  • Niccolo' Cascarano, Pierluigi Rolando, Fulvio Risso, and Riccardo Sisto

    This paper presents iNFAnt, a parallel engine for regular expression pattern matching. In contrast with traditional approaches, iNFAnt adopts non-deterministic automata, al- lowing the compilation of very large and complex rule sets that are otherwise hard to treat.

    iNFAnt is explicitly designed and developed to run on graphical processing units that provide large amounts of concurrent threads; this parallelism is exploited to handle the non-determinism of the model and to process multiple packets at once, thus achieving high performance levels.

    Y. Zhang
  • Mark Allman

    In this paper we propose a system that will allow people to communicate their status with friends and family when they find themselves caught up in a large disaster (e.g., sending “I’m fine” in the immediate aftermath of an earthquake). Since communication between a disaster zone and the non-affected world is often highly constrained we design the system around lightweight triggers such that people can communicate status with only crude infrastructure (or even sneaker-nets). In this paper we provide the high level system design, discuss the security aspects of the system and study the overall feasibility of a purpose-built social networking system for communication during an emergency.

    S. Saroiu
  • Alisa Devlic

    Context-aware applications need quickly access to current context information, in order to adapt their behavior before this context changes. To achieve this, the context distribution mechanism has to timely discover context sources that can provide a particular context type, then acquire and distribute context information from these sources to the applications that requested this type of information. This paper reviews the state-of-the-art context distribution mechanisms according to identified requirements, then introduces a resource listbased subscription/notification mechanism for context sharing. This SIP-based mechanism enables subscriptions to a resource list containing URIs of multiple context sources that can provide the same context type and delivery of aggregated notifications containing context updates from each of these sources. Aggregation of context is thought to be important as it reduces the network traffic between entities involved in context distribution. However, it introduces an additional delay due to waiting for context updates and their aggregation. To investigate if this aggregation actually pays off, we measured and compared the time needed by an application to receive context updates after subscribing to a particular resource list (using RLS) versus after subscribing to each of the individual context sources (using SIMPLE) for different numbers of context sources. Our results show that RLS aggregation outperforms the SIMPLE presence mechanism with 3 or more context sources, regardless of their context updates size. Database performance was identified as a major bottleneck during aggregation, hence we used in-memory tables & prepared statements, leading to up to 57% database time improvement, resulting in a reduction of the aggregation time by up to 34%. With this reduction and an increase in context size, we pushed the aggregation payoff threshold closer to 2 context sources.

    K. Papagiannaki
  • Augusto Ciuffoletti

    Infrastructure as a Service (IaaS) providers keep extending with new features the computing infrastructures they offer on a pay per use basis. In this paper we explore reasons and opportunities to include networking within such features, meeting the demand of users that need composite computing architectures similar to Grids.

    The introduction of networking capabilities within IaaSs would further increase the potential of this technology, and also foster an evolution of Grids towards a confluence, thus incorporating the ex- periences matured in this environment.

    Network monitoring emerges as a relevant feature of such virtual architectures, which must exhibit the distinguishing properties of the IaaS paradigm: scalability, dynamic configuration, accounting. Monitoring tools developed with the same purpose in Grids provide useful insights on problems and solutions.

  • kc claffy, Emile Aben, Jordan Auge, Robert Beverly, Fabian Bustamante, Benoit Donnet, Timur Friedman, Marina Fomenkov, Peter Haga, Matthew Luckie, and Yuval Shavitt

    On February 8-10, 2010, CAIDA hosted the second Workshop on Active Internet Measurements (AIMS-2) as part of our series of Internet Statistics and Metrics Analysis (ISMA) workshops. The goals of this workshop 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 addressing future data needs of the network and security research communities. The three-day workshop included presentations, group discussion and analysis, and focused interaction between participating researchers, operators, and policymakers from all over the world. This report describes the motivation and findings of the workshop, and reviews progress on recommendations developed at the 1st Active Internet Measurements Workshop in 2009 [18]. Slides from the workshop presentations are available at [9].

  • Anthony Rutkowski, Youki Kadobayashi, Inette Furey, Damir Rajnovic, Robert Martin, Takeshi Takahashi, Craig Schultz, Gavin Reid, Gregg Schudel, Mike Hird, and Stephen Adegbite

    The cybersecurity information exchange framework, known as CYBEX, is currently undergoing its first iteration of standardization efforts within ITU-T. The framework describes how cybersecurity information is exchanged between cybersecurity entities on a global scale and how the exchange is assured. The worldwide implementation of the framework will eventually minimize the disparate availability of cybersecurity information. This paper provides a specification overview, use cases, and the current status of CYBEX.

  • Balachander Krishnamurthy

    This is a brief journey across the Internet privacy landscape. After trying to convince you about the importance of the problem I will try to present questions of interest and how you might be able to apply your expertise to them.

  • Andreas Maeder and Nader Zein

    OFDMA will be the predominant technology for the air interface of broadband mobile wireless systems for the next decades. In recent years, OFDMA-based networks based on IEEE 802.16, and increasingly also on 3GPP LTE are rolled out for commercial use. This article gives an overview of the main challenges for the deployment and operation of state-of-the-art OFDMA networks, along with an outlook into future developments for 4G and beyond 4G networks.

  • S. Keshav

    Every scientific discipline builds on the past: new ideas invariably appear from the analysis, synthesis, and repudiation of prior work. Even an innovator like Sir Isaac Newton wrote to Robert Hooke on 15 February 1676: “If I have seen further it is only by standing on the shoulders of giants.” A necessary prerequisite for building on the past is for the body of archival work to be of the highest possible quality. Work that enters the communal memory should have no errors that either that the authors are aware of, or that can be rectified by careful peer review. Of course, no process can hope to eliminate errors altogether, but archival work should be free from errors that can be avoided with reasonable care.

    Conference publications, by their very nature, are susceptible to errors. The process is driven by strict deadlines, preventing authors from having a back-and-forth exchange with the reviewers in an attempt to fix problems. Program committee members, faced with a stack of 15 to 25 papers to review, naturally limit the depth of their reviews. Moreover, the selection of a paper for publication means only that a paper ranked amongst the best of those submitted for consideration by the program committee, rather than a guarantee of absolute quality. Although shepherding does improve the quality of an accepted paper, even shepherding is only mildly effective when faced with the natural reluctance of authors to do additional work for a paper that has already been accepted for publication. For these reasons, a field that treats conferences as archival publications is building on a foundation of sand.

    The Computer Research Association (CRA), however, arguing on behalf of the entire field of computer science, states that: “The reason conference publication is preferred to journal publication, at least for experimentalists, is the shorter time to print (7 months vs 1-2 years), the opportunity to describe the work before one’s peers at a public presentation, and the more complete level of review (4-5 evaluations per paper compared to 2-3 for an archival journal) [Academic Careers, 94]. Publication in the prestige conferences is inferior to the prestige journals only in having significant page limitations and little time to polish the paper. In those dimensions that count most, conferences are superior.” [1]

    The two negatives for conferences identified by the CRA, page limits and ‘lack of polish’ are worth examining. Today, the IEEE/ACM Transactions on Networking (ToN) limits papers to ten free pages and a maximum of 14 pages [2]. This is scarcely longer than many conference papers. Thus, the situation for journal papers is even worse than what the CRA states. On the other hand, what the CRA dismissively calls a ‘lack of polish’ sweeps many issues under the metaphorical carpet: issues like inadequate experimental design, lack of rigour in statistical analysis, and incorrect proofs. It seems unwise to permit these severe problems in papers that we admit to archival status. Unfortunately, given the conference publication process, these errors are unavoidable. Perhaps it would be better to think of ways of improving the journal publication process instead.

    Let's start by considering the reasons why the CRA thinks conference publications are superior to journal publications. Two of the three reasons – number of reviews and time to publication – are easily remedied. There is no reason why journal editors could not ask for more reviews. Few conference papers receive more than three reviews and this number could be easily matched by journal editors. Second, the two-to-three year publication delay for a journal paper, according to Henning Schulzrinne, who has had a long history of dealing with this process at ToN, arises primarily from the delay in assigning papers to reviewers and the delay in the authors’ responses to the first round of reviewer comments. The equivalent processes at conferences take only a few weeks. Why can’t journals match that? As a contrasting data point, journals in civil engineering have review times of 90 days and publication delays of only three to five months [3], which is shorter than even conference publication delays in computer science.

    This leaves conferences with just one advantage over journals, that of permitting face-to-face meetings. Specifically, in his recent article in CACM [3], Lance Fortnow argues that conferences allow the community:
    * To rate publications and researchers.
    * To disseminate new research results and ideas.
    * To network, gossip, and recruit.
    * To discuss controversial issues in the community.

    These are tangible and valuable benefits. However, as Fortnow and others have argued, we could organize conferences where not all accepted papers are presented on stage, leaving some to be presented in the form of posters. These would result in better-attended, more inclusive conferences, which would meet the needs Fortnow identifies, while not detracting from the archival value of journals. The informal poster format would also allow the presentation of early-stage ideas, which is valuable both to authors and to the research community. If posters are clearly marked, this would not detract from the prestige of full papers already published in the conference.

    I believe that we can begin to restore the integrity of archival publications by taking the following steps. First, we should increase the number and perceived prestige of posters at SIGCOMM-sponsored conferences, with more time set aside in the technical program for attendees to view posters. This would boost conference participation and better disseminate early stage ideas. Second, we should re-engineer the journal publication process to cap publication delay to six months. Third, journal editors should allow papers to be as lengthy as they need to be, instead of imposing an artificial page limit. Fourth, a greater emphasis on journal publications will be possible only if journals themselves are economically viable. If it turns out that print journals are unviable (a debatable point), we should consider moving to electronic-only journals or subsidize the production cost from conference fees.

    As these changes are made, other synergies may also present themselves. For example, reducing the conference review load could free up resources for journal reviews. Similarly, increased conference attendance from a more generous poster acceptance policy could increase journal subsidies, and moving to electronic journals would not only reduce costs, but would also cut publication delay.

    The net result of these changes will be to restore the integrity of our archival work. We cannot afford to let this slip much longer: the time to act is now!

    [1] D. Patterson, J. Snyder, J. Ullman, Evaluating computer scientists and engineers for promotion and tenure; http://www.cra.org/reports/tenure_review.html, August 1999.
    [2] http://www.ton.seas.upenn.edu/submissions.html#format
    [3] http://pubs.asce.org/editors/journal/resourceeditor/editorresponsibiliti...
    [4] Lance Fortnow, Viewpoint: Time for computer science to grow up, Communications of the ACM. Vol. 52 No. 8, Pages 33-35.

  • Sardar Ali, Irfan Ul Haq, Sajjad Rizvi, Naurin Rasheed, Unum Sarfraz, Syed Ali Khayam, and Fauzan Mirza

    Real-time Anomaly Detection Systems (ADSs) use packet sampling to realize tra±c analysis at wire speeds. While recent studies have shown that a considerable loss of anomaly detection accuracy is incurred due to sampling, solutions to mitigate this loss are largely unexplored. In this paper, we propose a Progressive Security-Aware Packet Sampling (PSAS) algorithm which enables a real-time inline anomaly detector to achieve higher accuracy by sampling larger volumes of malicious tra±c than random sampling, while adhering to a given sampling budget. High malicious sampling rates are achieved by deploying inline ADSs progressively on a packet's path. Each ADS encodes a binary score (malicious or benign) of a sampled packet into the packet before forwarding it to the next hop node. The next hop node then samples packets marked as malicious with a higher probability. We analytically prove that under certain realistic conditions, irrespective of the intrusion detection algorithm used to formulate the packet score, PSAS always provides higher malicious packet sampling rates. To empirically evaluate the proposed PSAS algorithm, we simultaneously collect an Internet tra±c dataset containing DoS and portscan attacks at three di®erent deployment points in our university's network. Experimental results using four existing anomaly detectors show that PSAS, while having no extra communication overhead and extremely low complexity, allows these detectors to achieve signi¯cantly higher accuracies than those operating on random packet samples.

    R. Teixeira
  • Roch Guérin and Kartik Hosanagar

    Although IPv6 has been the next generation Internet protocol for nearly 15 years, new evidences indicate that transitioning from IPv4 to IPv6 is about to become a more pressing issue. This paper attempts to quantify if and how such a transition may unfold. The focus is on “connectivity quality,” e.g., as measured by users’ experience when accessing content, as a possible incentive (or disincentive) for migrating to IPv6, and on “translation costs” (between IPv6 and IPv4) that Internet Service Providers will incur during this transition. The paper develops a simple model that captures some of the underlying interactions, and highlights the ambiguous role of translation gateways that can either help or discourage IPv6 adoption. The paper is an initial foray in the complex and often puzzling issue of migrating the current Internet to a new version with which it is incompatible.

    S. Saroiu
  • Nandita Dukkipati, Tiziana Refice, Yuchung Cheng, Jerry Chu, Tom Herbert, Amit Agarwal, Arvind Jain, and Natalia Sutin

    TCP flows start with an initial congestion window of at most four segments or approximately 4KB of data. Because most Web transactions are short-lived, the initial congestion window is a critical TCP parameter in determining how quickly flows can finish. While the global network access speeds increased dramatically on average in the past decade, the standard value of TCP’s initial congestion window has remained unchanged.

    In this paper, we propose to increase TCP’s initial congestion window to at least ten segments (about 15KB). Through large-scale Internet experiments, we quantify the latency benefits and costs of using a larger window, as functions of network bandwidth, round-trip time (RTT), bandwidthdelay product (BDP), and nature of applications. We show that the average latency of HTTP responses improved by approximately 10% with the largest benefits being demonstrated in high RTT and BDP networks. The latency of low bandwidth networks also improved by a significant amount in our experiments. The average retransmission rate increased by a modest 0.5%, with most of the increase coming from applications that effectively circumvent TCP’s slow start algorithm by using multiple concurrent connections. Based on the results from our experiments, we believe the initial congestion window should be at least ten segments and the same be investigated for standardization by the IETF.

    Y. Zhang
  • Zuoning Yin, Matthew Caesar, and Yuanyuan Zhou

    Software errors and vulnerabilities in core Internet routers have led to several high-profile attacks on the Internet infrastructure and numerous outages. Building an understanding of bugs in open-source router software is a first step towards addressing these problems. In this paper, we study router bugs found in two widely-used open-source router implementations. We evaluate the root cause of bugs, ease of diagnosis and detectability, ease of prevention and avoidance, and their effect on network behavior.

    S. Saroiu
  • Michael Buettner and David Wetherall

    We have developed a low cost software radio based platform for monitoring EPC Gen 2 RFID traffic. The Gen 2 standard allows for a range of PHY layer configurations and does not specify exactly how to compose protocol messages to inventory tags. This has made it difficult to know how well the standard works, and how it is implemented in practice. Our platform provides much needed visibility into Gen 2 systems by capturing reader transmissions using the USRP2 and decoding them in real-time using software we have developed and released to the public. In essence, our platform delivers much of the functionality of expensive (> $50,000) conformance testing products, with greater extensibility at a small fraction of the cost. In this paper, we present the design and implementation of the platform and evaluate its effectiveness, showing that it has better than 99% accuracy up to 3 meters. We then use the platform to study a commercial RFID reader, showing how the Gen 2 standard is realized, and indicate avenues for research at both the PHY and MAC layers.

    A. Chaintreau
  • Jon Crowcroft

    I’m so Bored of the Future Internet (FI). There are so many initiatives to look at the Internet’s Future1, anyone would think that there was some tremendous threat like global warming, about to bring about its immediate demise, and that this would bring civilisation crashing down around our ears.

    The Internet has a great future behind it, of course. However, my thesis is that the Future Internet is about as relevant as Anthropogenic Global Warming (AGW), in the way it is being used to support various inappropriate activities. Remember that the start of all this was not the exhaustion of IPv4 address space, or the incredibly slow convergence time of BGP routes, or the problem of scaling router memory for FIBs. It was the US research community reacting to a minor (as in parochial) temporary problem of funding in Communications due to slow down within NSF and differing agendas within DARPA.

    It is not necessary to invoke all the hype and hysteria - it is both necessary and sufficient to talk about sustainable energy2, and good technical communications research, development, deployment and operations.

    To continue the analogy between FI and AGW, what we really do not need is yet more climatologists with dodgy data curation methodologies (or ethnographers studying Internet governance).

    What we do need is some solid engineering, to address a number of problems the Internet has. However, this is in fact happening, and would not stop happening if the entire Future Internet flagship was kidnapped by aliens.
    “We don’t need no” government agency doing top down dictats about what to do when. It won’t work and it will be a massive waste of time, energy and other resources - i.e. like AGW, it will be a load of hot air:)

    On the other hand, there are a number of deeper lessons from the Internet Architecture which might prove useful in other domains, and in the bulk of this opinion piece, I give examples of these, applying the Postel and End-to-end principles to transport, energy, government information/vices.

  • Constantine Dovrolis, Krishna Gummadi, Aleksandar Kuzmanovic, and Sascha D. Meinrath

    Measurement Lab (M-Lab) is an open, distributed server platform for researchers to deploy active Internet measurement tools. The goal of M-Lab is to advance network research and empower the public with useful information about their broadband connections. By enhancing Internet transparency, M-Lab helps sustain a healthy, innovative Internet. This article describes M-Lab’s objectives, administrative organization, software and hardware infrastructure. It also provides an overview of the currently available measurement tools and datasets, and invites the broader networking research community to participate in the project.

  • S. Keshav

    This editorial is about some changes that will affect CCR and its community in the months ahead.

    Changes in the Editorial Board

    CCR Area Editors serve for a two-year term. Since the last issue, the terms of the following Area Editors have expired:
    • Kevin Almeroth, UC Santa Barbara, USA
    • Chadi Barakat, INRIA Sophia Antipolis, France
    • Dmitri Krioukov, CAIDA, USA
    • Jitendra Padhye, Microsoft Research, USA
    • Pablo Rodriguez, Telefonica, Spain
    • Darryl Veitch, University of Melbourne, Australia

    I would like to thank them for their devotion, time, and effort. They have greatly enhanced the quality and reputation of this publication.

    Taking their place is an equally illustrious team of researchers:
    • Augustin Chaintreau, Thomson Research, France
    • Stefan Saroiu, Microsoft Research, USA
    • Renata Teixeira, LIP6, France
    • Jia Wang, AT&T Research, USA
    • David Wetherall, University of Washington, USA Welcome aboard!

    Online Submission System

    This is the first issue of CCR completely created using an online paper submission system rather than email. A slight variant to Eddie Kohler's HotCRP, the CCR submission site allows authors to submit papers at any time, and for them to receive reviews as they are finalized.

    Moreover, they can respond to the reviews and conduct an anonymized conversation with their Area Editor. The system is currently batched: reviewer assignments and reviews are done once every three months. However, starting shortly, papers will be assigned to an Area Editor for review as they are submitted and the set of accepted papers will be published quarterly in CCR. We hope that this will allow authors to have the benefits of a 'rolling deadline,' similar to that pioneered by the VLDB journal.

    Reviewer Pool

    The reviewer pool is a set of volunteer reviewers, usually post-PhD, who are called upon by Area Editors to review papers in their special interests. The current set of reviewers in the pool can be found here: http://blizzard.cs.uwaterloo.ca/ccr/reviewers.html. If you would like to join the pool, please send mail to ccr-edit@uwaterloo.ca with your name, affiliation, interests, and contact URL.

    Page Limits

    We have had a six-page limit for the last year. The purpose of this limit was to prevent CCR from becoming a cemetery for dead papers. This policy has been a success: the set of technical papers in each issue has been vibrant and well-suited to this venue. However, we recognize that it is difficult to fit work into six pages. Therefore, from now on, although submissions will still be limited to six pages (unless permission is obtained in advance), if the reviewers suggest additional work, additional pages will be automatically granted.

    I hope that these changes will continue to make CCR a bellwether for our community. As always, your comments and suggestions for improvement are always welcome.

  • Hilary Finucane and Michael Mitzenmacher

    We provide a detailed analysis of the Lossy Difference Aggregator, a recently developed data structure for measuring latency in a router environment where packet losses can occur. Our analysis provides stronger performance bounds than those given originally, and leads us to a model for how to optimize the parameters for the data structure when the loss rate is not known in advance by using competitive analysis.

    Dmitri Krioukov
  • Marta Carbone and Luigi Rizzo

    Dummynet is a widely used link emulator, developed long ago to run experiments in user-configurable network environments. Since its original design, our system has been extended in various ways, and has become very popular in the research community due to its features and to the ability to emulate even moderately complex network setups on unmodified operating systems.

    We have recently made a number of extensions to the emulator, including loadable packet schedulers, support for better MAC layer modeling, the inclusion in PlanetLab, and development of Linux and Windows versions in addition to the native FreeBSD and Mac OS X ones.

    The goal of this paper is to present in detail the current features of Dummynet, compare it with other emulation solutions, and discuss what operating conditions should be considered and what kind of accuracy to expect when using an emulation system.

    Kevin Almeroth
  • Hamed Haddadi

    Online advertising is currently the richest source of revenue for many Internet giants. The increased number of online businesses, specialized websites and modern profiling techniques have all contributed to an explosion of the income of ad brokers from online advertising. The single biggest threat to this growth, is however, click-fraud. Trained botnets and individuals are hired by click-fraud specialists in order to maximize the revenue of certain users from the ads they publish on their websites, or to launch an attack between competing businesses.

    In this note we wish to raise the awareness of the networking research community on potential research areas within the online advertising field. As an example strategy, we present Bluff ads; a class of ads that join forces in order to increase the effort level for click-fraud spammers. Bluff ads are either targeted ads, with irrelevant display text, or highly relevant display text, with irrelevant targeting information. They act as a litmus test for the legitimacy of the individual clicking on the ads. Together with standard threshold-based methods, fake ads help to decrease click-fraud levels.

    Adrian Perrig
Syndicate content