On October 23rd 2012, we held an internal workshop to foster collaborations. In the morning, several long and short presentations were given (see program below), which were followed by a discussion afternoon.

Workshop Program

09h45â€“11h00: Internet measurements and graphs

Dario Rossi: Remote measurements of bufferbloat (25 min)
Nowadays, due to excessive queuing, Internet delays grow sometimes as large as the propagation delay from moon to earth – for which the bufferbloat term was recently coined. Some points to active queue management (AQM) as its solution, others propose end-to-end congestion control techniques – like BitTorrent that recently replaced TCP with the LEDBAT transport protocol.Assessing the actual amount of bufferbloat that people experience in their daily Internet usage can give important indication of the quality of experience of their interactive delay-sensitive applications. In this talk, we present two methodologies to monitor the upstream queuing delay experienced by remote hosts. One is an active methodology using RTT measurement, the other is passive and relies on either LEDBAT’s native one-way delay measurements or TCP timestamp option. These methodology pose interesting problems that will be illustrated throughout the talk.

More information
Laurent Viennot: Compact routing, spanners, multi-path routing (25 min)
I will give an introduction to compact routing that is how to trade-off the size of routing tables versus the length of routes. We will see that the problem is linked to that of computing a spanner of a graph G, i.e. a subgraph with few edges and comparable distances. As an example of possible extension, I will present work in progress about compacting routing tables in multi-path routing.More information
Timur Friedman: improving Paris Traceroute’s multipath detection algorithm (MDA) (25min)
Paris Traceroute is an improved Traceroute tool that takes into account the fact that routers in the internet routinely load balance traffic across multiple paths. So between a source and a destination there can be a path that diverges into perhaps several paths (and the path can diverge more than once) and reconverges. The only way to detect these paths without prior knowledge is through exploration, trying to uncover the stochastic processes that are governing the assignment of packets to paths. We at UPMC (Renata Teixeira, Timur Friedman, and our doctoral student Brice Augustin) worked together with Darryl Veitch to develop the multipath detection algorithm (MDA) that does just this, and is able to assign confidence levels to the results. However, the first version of the MDA could be made much more efficient if we were to take into account some prior knowledge of the network. We propose to continue the joint work with Darryl, together with a partner at the LINCS who is probability and statistics minded.More information

11h00â€“11h15: Elevator pitches

Thomas Bonald: Graphs with queues (3 min)
Consider a finite set of resources with some exclusion constraints. Such constraints are represented by a graph, each node of the graph corresponding to a resource and each edge to an exclusion constraint between two resources, which cannot be activated simultaneously. Each resource receives a stochastic process of jobs, which are queued until service completion. Each resource with a non-empty queue attempts to become active after some period of random duration. We are interested in the stability (existence of a stationary regime) and performance (queue dynamics) of the system. Applications include wireless networks and packet switches.
Renata Teixeira: Predicting User Dissatisfaction with Internet Application Performance at End-Hosts (3 min)
If a user’s end system could predict when the user will be dissatisfied with the performance of networked applications, then the system could launch automated tools to improve the users’s experience. Example tools include root cause diagnosis to assist the user in fixing the problem, or resource managers (e.g., bandwidth or video playout buffers) to tune the allocation of network resources to better serve the user. Unfortunately, predicting user dissatisfaction with application performance is not as simple as identifying outliers in typical network metrics such as high round-trip times or loss rates. Understanding user perception requires direct feedback from end users. Our recent work has developed predictors of user dissatisfaction with Internet application performance. We train these predictors offline using network performance data collected passively from the machines of 19 users, who also input their feedback on network performance a few times per day. A number of open questions remain. Can we use predictor learned from one user to another? How often do we need to retrain? How to predict user dissatisfaction and launch diagnosis online?
Claude Chaudet: Distributed Intelligent Transportation Systems (3 min)
Urban road traffic is generally managed from a central control center, using data sent by large monitoring devices (magnetic loops) to estimate traffic density. Due to the cost of such equipment, sampling is generally reserved to main roads. Newer works try to use vehicular networks or mobile phones to acquire additional data. To avoid problems related, for example, to the initial deployment, we would like to let a network composed of wireless sensors embedded in traffic lights control locally the lights behavior. Defining a local, distributed algorithm is relatively easy, but the optimization of this algorithm parameters poses non-trivial modeling issues related, for example, to queuing theory and to games theory.
Ana Busic: Bounded state space truncation and censored Markov chains (3 min)
Markov chain modeling often suffers from the curse of dimensionality problems and many approximation schemes have been proposed in the literature that include state-space truncation. Estimating the accuracy of such methods is difficult and the resulting approximations can be far from the exact solution. Censored Markov chains (CMC) allow to represent the conditional behavior of a system within a subset of observed states and provide a theoretical framework to study state-space truncation.
Marc Lelarge: The power of 2 random choices (3 min)
The two-choice paradigm has many interesting applications in computer science, the aim of this talk is to demonstrate its power on a traditional balls and bins problem.

11h15â€“11h45: Break

11h45â€“13h25: Optimizations of large-scale systems

Research topics and challenges at Alcatel-Lucent Bell Labs (25 min)
Alcatel-Lucent Bell Labs addresses various research domains from fundamental aspects (mathematics, physics) to practical ones (transmission, networks, services, …). In this presentation we make a short overview of the different topics addressed in the Bell Labs, and we list several challenges that Alcatel-Lucent members at the LINCS or some of their colleagues at Nozay are currently addressing. This is an opportunity to engage collaborations within the LINCS about some of these topics.
Fabien Mathieu: On the Manipulability of Voting Systems: Application to Multi-Carrier Networks (25 min)
Today, Internet involves many actors who are making revenues on it (operators, companies, service providers,…). It is therefore important to be able to make fair decisions in this large-scale and highly competitive economical ecosystem. One of the main issues is to prevent actors from manipulating the natural outcome of the decision process. For that purpose, game theory is a natural framework. In that context, voting systems represent an interesting alternative that, to our knowledge, has not yet been considered. They allow competing entities to decide among different options. Strong theoretical results showed that all voting systems are susceptible to be manipulated by one single voter, except for some ”degenerated” and non-acceptable cases. However, very little is known about how much a voting system is manipulable in practical scenarios. We investigate empirically the use of voting systems for choosing end-to-end paths in multi-carrier networks, analyzing their manipulability and their economical efficiency. We show that one particular system, called Single Transferable Vote (STV), is largely more resistant to manipulability than the natural system which tries to get the economical optimum. Moreover, STV manages to select paths close to the economical optimum, whether the participants try to cheat or not.More information
Marcelo Dias de Amorim: Traffic offloading (25 min)
In several scenarios, data traffic has been growing in a much faster pace than the capacity of the network. Traffic offloading consists in finding an alternative communication channel to help alleviate the load handled by the main pipe. In this talk, we will focus on two situations where this problem is particularly critical. First, we will consider the case of the 3G/4G wireless infrastructures and how opportunistic networks could help operators meet the growing demands of mobile users. Second, we will investigate the case of inter-datacenter big data transfers and how to offload traffic onto vehicular networks.More information
Phillipe Jacquet: (25 min)
Twitter produces several millions of short texts per hour. Monitoring information tendencies has become a key business. Many information, rumors and counter-rumor may carry wrong informations. A motivating topic is to build trajectory and consensus model that asses the veracity of an information. This is a necessary step is one wants to move from a network of information to a network of knowledge. A fundamental brick would be in the detection of correlations between textual informations.

13h25â€“14h30: Lunch at Via Italia (remember to bring your tickets)

14h30â€“16h30: Brainstorming sessions

Based on the presentations and discussions in the morning, each of us will identify potential topics for collaboration and organize meetings in small groups to brainstorm on the future directions.