A Broadcast-Only Communication Model Based on Replicated Append-Only Logs

Christian Tschudin

Abstract

This note is about the interplay between a data structure, the append-only log, and a broadcasting communication abstraction that seems to induce it. We identified real-world systems which have started to exploit this configuration and highlight its desirable properties. Networking research should take note of this develop- ment and adjust its research agenda accordingly.

Download the full article

Precise Detection of Content Reuse in the Web

Calvin Ardi, John Heidemann

Abstract

With vast amount of content online, it is not surprising that unscrupulous entities “borrow” from the web to provide content for advertisements, link farms, and spam. Our insight is that cryptographic hashing and fingerprinting can efficiently identify content reuse for web-size corpora. We develop two related algorithms, one to automatically discover previously unknown duplicate content in the web, and the second to precisely detect copies of discovered or manually identified content. We show that bad neighborhoods, clusters of pages where copied content is frequent, help identify copying in the web. We verify our algorithm and its choices with controlled experiments over three web datasets: Common Crawl (2009/10), GeoCities (1990s–2000s), and a phishing corpus (2014). We show that our use of cryptographic hashing is much more precise than alternatives such as locality-sensitive hashing, avoiding the thousands of false-positives that would otherwise occur. We apply our approach in three systems: discovering and detecting duplicated content in the web, searching explicitly for copies of Wikipedia in the web, and detecting phishing sites in a web browser. We show that general copying in the web is often benign (for example, templates), but 6–11% are commercial or possibly commercial. Most copies of Wikipedia (86%) are commercialized (link farming or advertisements). For phishing, we focus on PayPal, detecting 59% of PayPal-phish even without taking on intentional cloaking.

Download the full article

On the Complexity of Non-Segregated Routing in Reconfigurable Data Center Architectures

Klaus-Tycho Foerster, Maciej Pacut, Stefan Schmid

Abstract

By enhancing the traditional static network (e.g., based on electric switches) with a dynamic topology (e.g., based on reconfigurable optical switches), emerging reconfigurable data centers introduce unprecedented flexibilities in how networks can be optimized toward the workload they serve. However, such hybrid data centers are currently limited by a restrictive routing policy enforcing artificial segregation: each network flow can only use either the static or the flexible topology, but not a combination of the two.

This paper explores the algorithmic problem of supporting more general routing policies, which are not limited by segregation. While the potential benefits of non-segregated routing have been demonstrated in recent work, the underlying algorithmic complexity is not well-understood. We present a range of novel results on the algorithmic complexity of non-segregated routing. In particular, we show that in certain specific scenarios, optimal data center topologies with non-segregated routing policies can be computed in polynomial-time. In many variants of the problem, however, introducing a more flexible routing comes at a price of complexity: we prove several important variants to be NP-hard.

Download the full article

The January 2019 Issue

2019 is a special year for SIGCOMM as your SIG will celebrate its 50th birthday at SIGCOMM’19 in August. During the last half century, the networking field has evolved a lot and SIGCOMM Computer Communication Review (CCR) contributed to this evolution by timely disseminating technical papers. CCR will celebrate SIGCOMM’s birthday with a special issue that will contain editorial notes that reflect on both the past and the future of your SIG. This special issue will be published in October 2019. Its detailed content is still being worked on, but we expect that you will find lots of interesting information in this issue. If you plan to submit papers to CCR, please note that the October 2019 issue will not publish any new technical paper. All the papers submitted between March 1st, 2019 and September 1st, 2019 will be considered for the January 2020 issue.

This January 2019 issue contains one technical paper and four editorial notes. In “Parametrized Complexity of Virtual Network Embeddings: Dynamic & Linear Programming Approximations”, Matthias Rost et al. analyse the problem of mapping a virtual network on a physical one. They propose both theoretical experimental results.

The first two editorial notes are position papers addressing different technical topics. In “Network Telemetry: Towards A Top-Down Approach”, Minlan Yu argues that we should view network telemetry from a different angle. Instead of using a bottom-up approach that relies on passively collecting data from various devices and then inferring the target network-wide information, she suggests a top-down approach and envisions the possibility of providing high- level declarative abstractions that would en- able operators to define specific measurement queries. This editorial note could be of interest for many Internet measurement researchers.

In “Thoughts on Load Distribution and the Role of Programmable Switches”, James McCauley and his colleagues take a step back at some usages of programmable network switches. More precisely, they wonder which type of functionality should be migrated to switches and which functionality should not. This is a very interesting question that should be answered when writing the motivation for many papers on programmable switches.

The two other editorial notes were prepared at a recent Dagstuhl seminar that focused on the reproducibility of network research. In “The Dagstuhl Beginners Guide to Reproducibility for Experimental Networking Research”, Vaibhav Bajpai and his eight co-authors have assembled a very interesting and very useful guide filled with hints and recommendations for young researchers who begin to experiment with networks. This article will probably soon become a must read in many graduate schools. During the same seminar, another group of researchers lead by Alberto Dainotti brainstormed about our x pages two column papers. This format was interesting when articles were disseminated on real paper. Today, thirty years after the invention of the web, there are many other possibilities to disseminate scientific information. Many of these techniques are more collaborative and open than putting pdf files on web servers. “Open Collaborative Hyperpapers: A Call to Action” encourages the measurements community to collaborate on the preparation of hyperpapers. This editorial note explains the motivations for these hyperpapers and discusses some solv- able technical challenges. An interesting point about this approach is that it could encourage both a faster dissemination of research results and a truly open model that encourages authors to collaborate. While brainstorming about the 50th birthday issue of SIGCOMM, we had an interesting teleconference with Vint Cerf who reminded us of the role that SIGCOMM Computer Communication played in allowing a fast dissemination of recent research results. He compared CCR with publications such as the Journal of the ACM that had much longer publication delays.

The hyperpapers in the last editorial note of this issue could be a modern way of disseminating important research results. I would love to see researchers collaborating on hyperpapers in the coming months and submitting their work to CCR. Such a submission would violate the CCR submission guidelines that still assume that authors pro- vide pdf files. If such an hyperpaper gets sub- mitted to CCR, we find a suitable reviewing process within the CCR Editorial board.

I hope that you will enjoy reading this new issue and welcome comments and suggestions on CCR Online (https: //ccronline.sigcomm.org) or by email at ccr-editor at sigcomm.org.

Olivier Bonaventure

CCR Editor

Parametrized Complexity of Virtual Network Embeddings: Dynamic & Linear Programming Approximations

Matthias Rost, Elias Döhne, Stefan Schmid

Abstract

This paper makes the case for a parametrized complexity approach to tackle the fundamental but notoriously hard Virtual Network Embedding Problem. In particular, we show that the structure of the to-be-embedded virtual network requests can be exploited toward fast (i.e., fixed-parameter tractable) approximation algorithms, using dynamic as well as linear programming algorithms. 

Our approach does provide formal guarantees on the runtime and solution quality and can safeguard also latency constraints. Using extensive computational experiments we demonstrate the practical relevance of our novel approach.

Download the full article

Network Telemetry: Towards A Top-Down Approach

Minlan Yu

Abstract

Network telemetry is about understanding what is happening in the current network. It serves as the basis for making a variety of management decisions for improving the performance, availability, security, and efficiency of networks. However, it is challenging to build real-time and fine-grained network telemetry systems because of the need to support a variety of measurement queries, handle a large amount of traffic for large networks, while staying within the resource constraints at hosts and switches. Today, most operators take a bottom-up approach by passively collecting data from individual devices and infer the network-wide information they need. They are often limited by the monitoring tools device vendors provide and find it hard to extract useful information. In this paper, we argue for a top-down approach: We should provide a high-level declarative abstraction for operators to specify measurement queries, programmable measurement primitives at switches and hosts, and a runtime that translates the high-level queries into low-level API calls. We discuss a few recent works taking this top-down approach and call for more research in this direction.

Download the full article

Thoughts on Load Distribution and the Role of Programmable Switches

James McCauley, Aurojit Panda, Arvind Krishnamurthy, Scott Shenker

Abstract

The trend towards powerfully programmable network switching hardware has led to much discussion of the exciting new ways in which it can be used. In this paper, we take a step back, and examine how it should be used.

Download the full article

The Dagstuhl Beginners Guide to Reproducibility for Experimental Networking Research

Vaibhav Bajpai, Anna Brunstrom, Anja Feldmann, Wolfgang Kellerer , Aiko Pras, Henning Schulzrinne, Georgios Smaragdakis, Matthias Wählisch , Klaus Wehrle

Abstract

Reproducibility is one of the key characteristics of good science, but hard to achieve for experimental disciplines like Internet measurements and network systems. This guide provides advice to researchers, particularly those new to the field, on designing experiments so that their work is more likely to be reproducible and to serve as a foundation for follow-on work by others.

Download the full article

Open Collaborative Hyperpapers: A Call to Action

Alberto Dainotti, Ralph Holz, Mirja Kühlewind, Andra Lutu, Joel Sommers, Brian Trammell

Abstract

Drawing on discussions at various venues, we envision a publishing ecosystem for Internet science, supporting publications that are self-contained, interactive, multi-level, open, and collaborative. These publications, which we dub hyperpapers, not only address issues with reproducibility and verifiability of research in Internet science and measurement, but have the potential to increase the impact of our work and change how collaborations work in the field. This note announces initial experiments with Internet measurement hyperpapers with the help of common, tested technologies in data science and software development, and is a call to action to others to come build out this vision with us.

Download the full article

The October 2018 issue

SIGCOMM’18 was held in Hungary and the participants were pleased with both the technical program and the social interactions with all the members of the community. During her keynote on Networks Capable of Change, Jennifer Rexford mentioned two papers published in CCR that have had an important impact on our community : OpenFlow: enabling innovation in campus networks and P4: programming protocol- independent packet processors. These two editorial notes paved the way for Software-Defined Networks and then programmable switches. They are a good illustration of the benefits of having a venue like CCR that is open to other types of papers than the scientific papers that usually appear in our conferences and workshops.

This issue contains three regular papers, two editorial notes and the best papers of five recent SIGCOMM’18 workshops. Our first paper, On Max-min Fair Allocation for Multi-source Transmission, co-authored by G. Li et al., proposes and evaluates an algorithm to provide max-min fairness in a network where the same information can be downloaded from multiple sources. In On Collaborative Predictive Blacklisting, Luca Malis and his colleagues study collaborative predictive blacklisting (CPB) wherein differ- ent organizations share information about attacks in real time and use it to update their blacklists. Finally, in Bootstrapping Privacy Services in Today’s Internet, T. Lee et al. propose and analyse different services that could be provided by Internet Service Providers to provide better privacy to their users.

The two editorial notes published in this issue are very different. In Toward Demand- Aware Networking: A Theory for Self- Adjusting Network, C. Avin and S. Schmid propose to initiate the study of the theory of demand-aware, self-adjusting networks. In The 10th Workshop on Active Internet Measurements (AIMS-10) Report, kc Claffy and David Clark report the lessons learned from a recent workshop.

This issue also contains the best pa- pers selected by the organizers of five SIGCOMM’18 workshops:

• Learning IP Network Representations presented by M. Li et al. at BIG- DAMA’18

• Measuring the Impact of a Success- ful DDoS Attack on the Customer Behaviour of Managed DNS Service Providers presented by A. Abhista et al. at the workshop on traffic measure- ments for Cybersecurity

• Making Content Caching Policies ’Smart’ using the DeepCache Framework presented by A. Narayanan et al. at NetAI’18

• Refining Network Intents for Self- Driving Networks presented by A. Jacobs et al. at SelfDN’18

• A Formally Verified NAT Stack presented by S. Pirelli et al. at KBNets’18

The composition of the Editorial Board has also been modified recently. After several years of active participation, Costin Raiciu, Fahad Dogar, Alberto Dainotti and David Choffnes have concluded their term. I would like to thank them on behalf of the authors of all the papers that they handled during the last years. Sergey Gorinsky (IMDEA Networks, Spain) has agreed to join the Editorial board.

I hope that you will enjoy reading this new issue and welcome comments and suggestions on CCR Online (https: //ccronline.sigcomm.org) or by email at ccr-editor at sigcomm.org.

Olivier Bonaventure

CCR Editor