Category Archives: 2019

The April 2019 Issue

This April 2019 issue contains two technical papers and four editorial notes. In ”On the Complexity of Non-Segregated Routing in Reconfigurable Data Center Architectures”, Klaus-Tycho Foerster and his colleagues analyse whether a data center net- work could dynamically reconfigure its topology the better meet the traffic demand. They explore this problem as a mathematical optimisation problem and seek exact algorithms. The second technical paper, ”Precise Detection of Content Reuse in the Web” ad- dresses the problem of detecting whether the same content is available on different websites. Calvin Ardi and John Heidemann propose a new methodology that enables re- searchers to discover and detect the reutilisation of content on web servers. They provide both a large dataset and software to analyse it.

The four editorial notes cover very different topics. Kc Claffy and Dave Clark summarise in ”Workshop on Internet Economics (WIE2018) Final Report” a recent workshop on Internet economics. In ”Democratizing the Network Edge”, Larry Peterson and six colleagues encourage the community to participate in the innovation that they predict at the intersection between the cloud and the access networks that many refer to as the edge. They propose a plan for action to have a real impact on this emerging domain. In ”A Broadcast-Only Communication Model Based on Replicated Append- Only Logs”, Christian Tschudin looks at the interplay between the append-only log data structure and broadcast communication techniques. He argues that some network architectures could leverage this interplay.

As a reader of CCR, you already know the benefits of releasing the artifacts asso- ciated to scientific papers. This encourages their replicability and ACM has defined a badging system to recognise the papers that provide such artifacts. Several ACM SIGs have associated artifacts evaluation commit- tees to their flagship conferences and encourage their members to release their paper artifacts. Last year, two evaluation of paper artifacts were organised within SIGCOMM. The first one focussed on the papers that were accepted at the Conext’18 conference. Twelve of the papers presented at Conext’18 received ACM reproducibility badges. The second artifacts evaluation was open to pa- pers accepted by CCR and other SIGCOMM conferences. Twenty eight of these papers received ACM reproducibility badges. These evaluations and some lessons learned are dis- cussed in ”Evaluating the artifacts of SIGCOMM papers” by Damien Saucez, Luigi Iannone and myself. We hope that evalu- ating the artifacts will become a habit for all SIGCOMM conferences.

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.

Workshop on Internet Economics (WIE2018) Final Report

kc Claffy, David Clark

Abstract

On 12-13 December 2018, CAIDA hosted the 9th interdisciplinary Workshop on Internet Economics (WIE) at the UC San Diego’s Supercomputer Center. This workshop series provides a forum for researchers, Internet facilities and service providers, technologists, economists, theorists, policy makers, and other stakeholders to exchange views on current and emerging regulatory and policy debates. To add clarity to a range of vigorous policy debates, and in pursuit of actionable objectives, this year’s meeting used a different approach to structuring the agenda. Each attendee chose a specific policy goal or harm, and structured their presentation to answer three questions: (1) What data is needed to measure progress toward/away from this goal/harm? (2) What methods do you propose to gather such data? (3) Who are the right entities to gather such data, and how should such data be managed and shared? With a specific focus on measurement challenges, the topics we discussed included: analyzing the evolution of the Internet in a layered-platform context to gain new insights; measurement and analysis of economic impacts of new technologies using old tools; security and trustworthiness, reach (universal service) and reachability, sustainability of investment into Internet infrastructure, as well as infrastructure to measure the Internet. All slides made available at https://www.caida.org/workshops/wie/1812/.

D ownload the full article

Evaluating the artifacts of SIGCOMM papers

Damien Saucez, Luigi Iannone, Olivier Bonaventure

Abstract

A growing fraction of the papers published by CCR and at SIGCOMM- sponsored conferences include artifacts such as software or datasets. Besides CCR, these artifacts were rarely evaluated. During the last months of 2018, we organised two different Artifacts Evaluation Committees to which authors could submit the artifacts of their papers for evaluation. The first one evaluated the papers accepted by Conext’18 shortly after the TPC decision. It assigned ACM reproducibility badges to 12 different papers. The second one evaluated papers accepted by CCR and any SIGCOMM-sponsored conference. 28 papers received ACM reproducibility badges. We report on the results of a short survey among artifacts authors and reviewers and provide some suggestions for future artifacts evaluations.

Download the full article

Democratizing the Network Edge

Larry Peterson, Tom Anderson, Sachin Katti, Nick Mc Keown, Guru Parulkar, Jennifer Rexford, Mahadev Satyanarayanan, Oguz Sunay, Amin Vahdat

Abstract

With datacenters established as part of the global computing infras- tructure, industry is now in the midst of a transition towards the edge. Previous research initiatives laid the groundwork for this transition, but that is no guarantee the emerging edge will continue to be open to researchers. This paper argues that there is a tremendous opportunity to innovate at the edge, but having impact requires understanding the nature of the current industry momentum, and making a concerted effort to align with that momentum. We believe there are three keys to doing this: (1) focus on the intersection of the cloud and access networks, (2) contribute to the relevant open source projects, and (3) address the challenge of operationalizing the results. The paper puts forward a concrete proposal for all three, and discusses the opportunity to influence how the Internet evolves at the edge and enable new and transformative edge applications.

D ownload the full article

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.

Do wnload 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.

Do wnload 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