Category Archives: CCR January 2019

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: // or by email at ccr-editor at

Olivier Bonaventure

CCR Editor

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

Matthias Rost, Elias Döhne, Stefan Schmid


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


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


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


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


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