2025

Hierarchical Reinforcement Learning with Targeted Causal Interventions
M. Khorasani, S. Salehkaleybar, N. Kiyavash and M. Grossglauser
42nd International Conference on Machine Learning, ICML 2025, Vancouver, 2025-07-13 - 2025-07-19.

Hierarchical reinforcement learning (HRL) improves the efficiency of long-horizon reinforcement-learning tasks with sparse rewards by decomposing the task into a hierarchy of subgoals. The main challenge of HRL is efficient discovery of the hierarchical structure among subgoals and utilizing this structure to achieve the final goal. We address this challenge by modeling the subgoal structure as a causal graph and propose a causal discovery algorithm to learn it. Additionally, rather than intervening on the subgoals at random during exploration, we harness the discovered causal model to prioritize subgoal interventions based on their importance in attaining the final goal. These targeted interventions result in a significantly more efficient policy in terms of the training cost. Unlike previous work on causal HRL, which lacked theoretical analysis, we provide a formal analysis of the problem. Specifically, for tree structures and, for a variant of Erdős-Rényi random graphs, our approach results in remarkable improvements. Our experimental results on HRL tasks also illustrate that our proposed framework outperforms existing work in terms of training cost.

Assessing the Performance of NOMA in a Multi-Cell Context: A General Evaluation Framework
A. Bardou, J. M. Gorce and T. Begin
IEEE Transactions on Wireless Communications, 1 - 1, 2025.
[view at publisher]

Non-Orthogonal Multiple Access (NOMA) is a Resource Sharing Mechanism (RSM) initially studied for 5G cellular networks and brought back to the agenda for 6G networks. While NOMA’s benefit at the level of a single cell has been properly established, assessing its performance at the scale of a cellular network remains an open research problem. This is mainly due to the inter-dependencies between scheduling, power control and inter-cell interference. Some algorithms have been proposed to optimize resource allocation in a multi-cell network, but they require a perfect and unrealistic knowledge of the whole channel states. In this paper, we leverage Bayesian Optimization techniques to build a versatile evaluation framework, able to assess the performance of multi-cell networks implementing a large variety of RSMs under a minimal set of assumptions. Subsequently, we illustrate how this evaluation framework can be used to compare the performance of several well-known RSMs under various fairness requirements and beamforming efficiencies. Our results show that, among the RSMs studied on a simple multi-cell network simulation, NOMA combined with a full reuse policy consistently emerges as the one able to achieve the highest end-users achievable rates under fairness constraints.

Efficiently Escaping Saddle Points for Policy Optimization
M. Khorasani, S. Salehkaleybar, N. Kiyavash, N. He and M. Grossglauser
41th Conference on Uncertainty in Artificial Intelligence (UAI 2025), Rio de Janiro, Brazil, 2025-07-21-2025-07-26.

Policy gradient (PG) is widely used in reinforcement learning due to its scalability and good performance. In recent years, several variance-reduced PG methods have been proposed with a theoretical guarantee of converging to an approximate first-order stationary point (FOSP) with the sample complexity of O(ϵ −3). However, FOSPs could be bad local optima or saddle points. Moreover, these algorithms often use importance sampling (IS) weights which could impair the statistical effectiveness of variance reduction. In this paper, we propose a variance-reduced second-order method that uses second-order information in the form of Hessian vector products (HVP) and converges to an approximate second-order stationary point (SOSP) with sample complexity of Õ(ϵ −3). This rate improves the best-known sample complexity for achieving approximate SOSPs by a factor of O(ϵ −0.5). Moreover, the proposed variance reduction technique bypasses IS weights by using HVP terms. Our experimental results show that the proposed algorithm outperforms the state of the art and is more robust to changes in random seeds.

Differentiating between Hierarchical and Flat Communities
D. Kuroda
ACM SIGMETRICS Performance Evaluation Review, vol. 52, no. 4, 9 - 10; ACM SIGMETRICS Performance Evaluation Review, vol. 52, no. 4, 9 - 10, 2025.
[view at publisher]

As data proliferate in the form of pairwise interactions or networks-from social media exchanges and physical infrastructures, like railways and the internet, to biological systems-extracting meaningful insights remains a significant challenge. Community detection is a pivotal task in this regard, viewing networks as groups of nodes. Importantly, community structures can exhibit hierarchical organization, and identifying such hierarchies, known as Hierarchical Community Detection (HCD), is essential.

Reducing Sensor Requirements by Relaxing the Network Metric Dimension
P. Mürmann, R. Jaccard, M. Dreveton, A. Alavi Razavi Ravari and P. Thiran
SIGMETRICS '25: ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Stony Brook, NY, USA, 2025-06-09 - 2025-06-13.
[view at publisher]

Source localization in graphs involves identifying the origin of a phenomenon or event, such as an epidemic outbreak or a misinformation source, by leveraging structural graph properties. One key concept in this context is the metric dimension, which quantifies the minimum number of strategically placed sensors needed to uniquely identify all vertices based on their distances. While powerful, the traditional metric dimension imposes a stringent requirement that every vertex must be uniquely identified, often necessitating a large number of sensors. In this work, we relax the metric dimension and allow vertices at a graph distance less than k to share identical distance profiles relative to the sensors. This relaxation reduces the number of sensors needed while maintaining sufficient resolution for practical applications like source localization and network monitoring. We provide two main theoretical contributions: an analysis of the k -relaxed metric dimension in deterministic trees, revealing the interplay between structural properties and sensor placement, and an extension to random trees generated by branching processes, offering insights into stochastic settings. We also conduct numerical experiments across a variety of graph types, including random trees, random geometric graphs, and real-world networks. For graphs with loops, we use a greedy algorithm to obtain an upper-bound on the relaxed metric dimension. The results show that the relaxed metric dimension is significantly smaller than the traditional metric dimension. Furthermore, the number of vertices indistinguishable from any given target vertex always remains small. Finally, we propose and evaluate a two-step localization strategy that balances the trade-off between resolution and the number of sensors required. This strategy identifies an optimal relaxation level that minimizes the total number of sensors across both steps, providing a practical and efficient approach to source localization.

Pricing for Routing and Flow-control in Payment Channel Networks
S. Sankagiri and B. Hajek
IEEE TRANSACTIONS ON NETWORKING; IEEE Transactions On Networking, 2025.
[view at publisher]

A payment channel network is a blockchain-based overlay mechanism that allows parties to transact more efficiently than directly using the blockchain. These networks are composed of payment channels that carry transactions between pairs of users. Due to its design, a payment channel cannot sustain a net flow of money in either direction indefinitely. Therefore, a payment channel network cannot serve transaction requests arbitrarily over a long period of time. We introduce DEBT control, a joint routing and flow-control protocol that guides a payment channel network towards an optimal operating state for any steady-state demand. In this protocol, each channel sets a price for routing transactions through it. Transacting users make flow-control and routing decisions by responding to these prices. A channel updates its price based on the net flow of money through it. We develop the protocol by formulating a network utility maximization problem and solving its dual through gradient descent. We provide convergence guarantees for the protocol and also illustrate its behavior through simulations.

Chronology and Sequence of Permanent Tooth Eruption in a Multi-Ethnic Urban Population
O. Micheli, M. Athanasiou, V. Kristof and G. S. Antonarakis
Dentistry Journal, vol. 13, no. 8; Dentistry Journal, vol. 13, no. 8, 356, 2025.
[view at publisher]

Objective: This study aimed to evaluate the mean age of eruption of permanent teeth and their clinical emergence sequence in a longitudinal sample of children from a multi-ethnic urban population. Methods: A total of 854 children (413 females and 441 males), aged between 4 and 13 years, were examined annually for a minimum of 4 consecutive years, as part of their annual dental screening appointment. The presence of permanent teeth was recorded at each examination. Mean and median ages, with standard deviations, of individual tooth eruption were calculated, in addition to the eruption sequence, and the analysis of the data was performed using the lognormal distribution model. Regarding the error of the method, two examiners reviewed all relevant dental screening forms, and any discrepancies were resolved through consultation with the senior author. Results: The sequence of permanent tooth eruption followed a consistent pattern across sexes, with distinct differences between the maxillary and mandibular arches. In the maxilla, eruption began with the first molar, while in the mandible, it started with the central incisor. Mandibular teeth generally erupted earlier than maxillary teeth, with girls experiencing earlier eruption than boys, with some exceptions, and prolonged eruption periods. No statistically significant differences were found in the timing of eruption between contralateral homologous teeth. Conclusions: Based on the present data, the observed sequence of tooth eruption in a multi-ethnic urban population showed similar patterns across sexes. Mandibular teeth generally erupt earlier than maxillary teeth, with girls experiencing earlier eruption than boys.

A Framework for Efficient Estimation of Closeness Centrality and Eccentricity in Large Networks
P. C. Trindade, M. Dreveton and D. R. Figueiredo
16th Conference on Complex Networks, Fortaleza, Brazil, 2025-04-22 - 2025-04-25.
[view at publisher]

Centrality indices, such as closeness and eccentricity, are key to identifying influential nodes within a network, with applications ranging from social and biological networks to communication and transportation systems. However, computing these indices for every node in large graphs is computationally prohibitive due to the need for solving the All-Pairs Shortest Path (APSP) problem. This paper introduces a framework for approximating closeness and eccentricity centrality by selecting a sequence of strategically chosen anchor nodes, from which Breadth-First Searches (BFS) are performed. We present two anchor-selection strategies that minimize estimation error for these indices and evaluate their effectiveness on synthetic and real-world networks. Comparative results indicate that while random anchor selection occasionally achieves lower errors for closeness, other strategies outperform in eccentricity estimation. This study highlights the effectiveness of anchor-based approximations and the trade-offs between different selection methods in estimating centrality at scale.

2024

Almost exact recovery in noisy semi-supervised learning
K. Avrachenkov and M. Dreveton
Probability in the Engineering and Informational Sciences, 1 - 22, 2024.
[view at publisher]

2024.Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classification. In particular, we derive the maximum a posteriori (MAP) estimator for clustering a degree corrected stochastic block model when a noisy oracle reveals a fraction of the labels. We then propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.

Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models
M. Dreveton, A. Gözeten, M. Grossglauser and P. Thiran
The 37th Annual Conference on Learning Theory, Edmonton, Canada, 2024-06-30 - 2024-07-03.

Clustering is a pivotal challenge in unsupervised machine learning and is often investigated through the lens of mixture models. The optimal error rate for recovering cluster labels in Gaussian and sub-Gaussian mixture models involves ad hoc signal-to-noise ratios. Simple iterative algorithms, such as Lloyd's algorithm, attain this optimal error rate. In this paper, we first establish a universal lower bound for the error rate in clustering any mixture model, expressed through Chernoff information, a more versatile measure of model information than signal-to-noise ratios. We then demonstrate that iterative algorithms attain this lower bound in mixture models with sub-exponential tails, notably emphasizing location-scale mixtures featuring Laplace-distributed errors. Additionally, for datasets better modelled by Poisson or Negative Binomial mixtures, we study mixture models whose distributions belong to an exponential family. In such mixtures, we establish that Bregman hard clustering, a variant of Lloyd's algorithm employing a Bregman divergence, is rate optimal.

HiddenMarkovModels.jl: generic, fast and reliable state space modeling
G. Dalle
Journal of Open Source Software, vol. 9, no. 96; The Journal of Open Source Software, vol. 9, no. 96, 6436, 2024.
[view at publisher]

Optimal performance of Graph Convolutional Networks on the Contextual Stochastic Block Model
G. Dalle and P. Thiran
The Third Learning On Graphs Conference, Online, 2024-12-02.

For Graph Neural Networks, oversmoothing denotes the homogenization of vertex embeddings as the number of layers increases. To better understand this phenomenon, we study community detection with a linearized Graph Convolutional Network on the Contextual Stochastic Block Model. We express the distribution of the embeddings in each community as a Gaussian mixture over a low-dimensional latent space, with explicit formulas in the case of a single layer. This yields tractable estimators for classification accuracy at finite depth. Numerical experiments suggest that modeling with a single Gaussian is insufficient and that the impact of depth may be more complex than previously anticipated.

This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization
A. Bardou, P. Thiran and G. Ranieri
38th Annual Conference on Neural Information Processing Systems, Vancouver Convention Center, 2024-12-10 - 2024-12-15.

Bayesian Optimization (BO) has proven to be very successful at optimizing a static, noisy, costly-to-evaluate black-box function f : S → R. However, optimizing a black-box which is also a function of time (i.e., a dynamic function) f : S ×T → R remains a challenge, since a dynamic Bayesian Optimization (DBO) algorithm has to keep track of the optimum over time. This changes the nature of the optimization problem in at least three aspects: (i) querying an arbitrary point in S × T is impossible, (ii) past observations become less and less relevant for keeping track of the optimum as time goes by and (iii) the DBO algorithm must have a high sampling frequency so it can collect enough relevant observations to keep track of the optimum through time. In this paper, we design a Wasserstein distance-based criterion able to quantify the relevancy of an observation with respect to future predictions. Then, we leverage this criterion to build W-DBO, a DBO algorithm able to remove irrelevant observations from its dataset on the fly, thus maintaining simultaneously a good predictive performance and a high sampling frequency, even in continuous-time optimization tasks with unknown horizon. Numerical experiments establish the superiority of W-DBO, which outperforms state-of-the-art methods by a comfortable margin.

Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression
L. Clarte, A. Vandenbroucque, G. Dalle, B. Loureiro, F. Krzakala and L. Zdeborová
40th Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, 2024-07-15 - 2024-07-19.

We investigate popular resampling methods for estimating the uncertainty of statistical models, such as subsampling, bootstrap and the jackknife, and their performance in high-dimensional supervised regression tasks. We provide a tight asymptotic description of the biases and variances estimated by these methods in the context of generalized linear models, such as ridge and logistic regression, taking the limit where the number of samples and dimension of the covariates grow at a comparable fixed rate. Our findings are threefold: i) resampling methods are fraught with problems in high dimensions and exhibit the double-descent-like behavior typical of these situations; ii) only when the sampling ratio is large enough do they provide consistent and reliable error estimations (we give convergence rates); iii) in the over-parametrized regime relevant to modern machine learning practice, their predictions are not consistent, even with optimal regularization.

Why the Metric Backbone Preserves Community Structure
M. Dreveton, C. Chucri, M. Grossglauser and P. Thiran
38th Annual Conference on Neural Information Processing Systems, Vancouver Convention Center, 2024-12-10 - 2024-12-15.
[view at publisher]

The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is obtained by removing all edges $(u,v)$ that are not the shortest path between $u$ and $v$. In networks with well-separated communities, the metric backbone tends to preserve many inter-community edges, because these edges serve as bridges connecting two communities, but tends to delete many intra-community edges because the communities are dense. This suggests that the metric backbone would dilute or destroy the community structure of the network. However, this is not borne out by prior empirical work, which instead showed that the metric backbone of real networks preserves the community structure of the original network well. In this work, we analyze the metric backbone of a broad class of weighted random graphs with communities, and we formally prove the robustness of the community structure with respect to the deletion of all the edges that are not in the metric backbone. An empirical comparison of several graph sparsification techniques confirms our theoretical finding and shows that the metric backbone is an efficient sparsifier in the presence of communities.

Fast Interactive Search under a Scale-Free Comparison Oracle
D. Chumbalov, L. H. Klein, L. Maystre and M. Grossglauser
40th Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, 2024-07-15 - 2024-07-19.

A comparison-based search algorithm lets a user find a target item t in a database by answering queries of the form, "Which of items i and j is closer to t?" Instead of formulating an explicit query (such as one or several keywords), the user navigates towards the target via a sequence of such (typically noisy) queries. We propose a scale-free probabilistic oracle model called γ-CKL for such similarity triplets (i, j; t), which generalizes the CKL triplet model proposed in the literature. The generalization affords independent control over the discriminating power of the oracle and the dimension of the feature space containing the items. We develop a search algorithm with provably exponential rate of convergence under the γ-CKL oracle, thanks to a backtracking strategy that deals with the unavoidable errors in updating the belief region around the target. We evaluate the performance of the algorithm both over the posited oracle and over several real-world triplet datasets. We also report on a comprehensive user study, where human subjects navigate a database of face portraits.

Discovering Lobby-Parliamentarian Alignments through NLP
A. Suresh, L. Radojević, F. Salvi, A. Magron, V. Kristof and M. Grossglauser
2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Mexico City, Mexico., June 16-21, 2024.
[full text]

We discover alignments of views between interest groups (lobbies) and members of the European Parliament (MEPs) by automatically analyzing their texts. Specifically, we do so by collecting novel datasets of lobbies’ position papers and MEPs’ speeches, and comparing these texts on the basis of semantic similarity and entailment. In the absence of ground-truth, we perform an indirect validation by comparing the discovered alignments with a dataset, which we curate, of retweet links between MEPs and lobbies, and with the publicly disclosed meetings of MEPs. Our best method performs significantly better than several baselines. Moreover, an aggregate analysis of the discovered alignments, between groups of related lobbies and political groups of MEPs, correspond to the expectations from the ideology of the groups (e.g., groups on the political left are more aligned with humanitarian and environmental organisations). We believe that this work is a step towards enhancing the transparency of the intricate decision-making processes within democratic institutions.

Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization
A. Bardou, P. Thiran and T. Begin
The Twelfth International Conference on Learning Representations, Vienna, Austria, May 7-11, 2024.
[full text]

Bayesian Optimization (BO) is typically used to optimize an unknown function f that is noisy and costly to evaluate, by exploiting an acquisition function that must be maximized at each optimization step. Even if provably asymptotically optimal BO algorithms are efficient at optimizing low-dimensional functions, scaling them to high-dimensional spaces remains an open problem, often tackled by assuming an additive structure for f. By doing so, BO algorithms typically introduce additional restrictive assumptions on the additive structure that reduce their applicability domain. This paper contains two main contributions: (i) we relax the restrictive assumptions on the additive structure of f without weakening the maximization guarantees of the acquisition function, and (ii) we address the over-exploration problem for decentralized BO algorithms. To these ends, we propose DuMBO, an asymptotically optimal decentralized BO algorithm that achieves very competitive performance against state-of-the-art BO algorithms, especially when the additive structure of f comprises high-dimensional factors.

Recovering Static and Time-Varying Communities Using Persistent Edges
K. Avrachenkov, M. Dreveton and L. Leskela
Ieee Transactions On Network Science And Engineering, vol. 11, no. 2, 2087 - 2099, 2024.
[full text] [view at publisher]

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all temporal snapshots) does not always produce satisfying results. To utilise information carried by temporal correlations, we propose to employ different weights on freshly appearing and persistent edges. We show that spectral clustering on such weighted graphs can be explained as a relaxation of the maximum likelihood estimator of an extension of the degree-corrected stochastic block model with Markov interactions. We also study the setting of evolving communities, for which we use the prediction at time t-1 as an oracle for inferring the community labels at time t. We demonstrate the accuracy of the proposed methods on synthetic and real data sets.

It’s All Relative: Learning Interpretable Models for Scoring Subjective Bias in Documents from Pairwise Comparisons
A. Suresh, C. H. Wu and M. Grossglauser
18th Conference of the European Chapter of the Association for Computational Linguistics (EACL 2024), Malta, March 17th -22nd, 2024.
[full text]

We propose an interpretable model to score the subjective bias present in documents, based only on their textual content. Our model is trained on pairs of revisions of the same Wikipedia article, where one version is more biased than the other. Although prior approaches based on bias classification have struggled to obtain a high accuracy for the task, we are able to develop a useful model for scoring bias by learning to accurately perform pairwise comparisons. We show that we can interpret the parameters of the trained model to discover the words most indicative of bias. We also apply our model in three different settings by studying the temporal evolution of bias in Wikipedia articles, comparing news sources based on bias, and scoring bias in law amendments. In each case, we demonstrate that the outputs of the model can be explained and validated, even for the two domains that are outside the training-data domain. We also use the model to compare the general level of bias between domains, where we see that legal texts are the least biased and news media are the most biased, with Wikipedia articles in between.

2023

Exact recovery and Bregman hard clustering of node-attributed Stochastic Block Model
M. Dreveton, F. Fernandes and D. Figueiredo
Advances in Neural Information Processing Systems 36, New Orleans, USA, 2023-12-10 - 2023-12-15.

Network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios, nodes also have attributes that are correlated with the clustering structure. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this work establishes an information-theoretic criterion for the exact recovery of community labels and characterizes a phase transition determined by the Chernoff-Hellinger divergence of the model. The criterion shows how network and attribute information can be exchanged in order to have exact recovery (e.g., more reliable network information requires less reliable attribute information). This work also presents an iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong to exponential families. This covers a broad range of possible interactions (e.g., edges with weights) and attributes (e.g., non-Gaussian models), as well as sparse networks, while also exploring the connection between exponential families and Bregman divergences. Extensive numerical experiments using synthetic data indicate that the proposed algorithm outperforms classic algorithms that leverage only network or only attribute information as well as state-of-the-art algorithms that also leverage both sources of information. The contributions of this work provide insights into the fundamental limits and practical techniques for inferring community labels on node-attributed networks.

Stochastic Models for Comparison-based Search
D. Chumbalov
2023.
[view at publisher]

In this thesis we study a problem of searching in a space of objects using comparisons. To navigate through the space to the target object $t$, we ask a sequence of questions of the form ``which object $i$ or $j$ is closer to $t$?'' for which we observe noisy answers. We propose two new probabilistic models for triplet comparisons $(i,j;t)$, which fit the real world data better than the state-of-the-art. We study theoretical properties of these models and for both derive search algorithms that are scalable in the number of objects $n$ and that have convergence guarantees. Finally, we conduct two experiments with real users, in which we demonstrate the efficiency of the proposed methods.

How Words Move Hearts: Interpretable Machine Learning Models of Bias, Engagement, and Influence in Socio-Political Systems
A. Suresh
2023.
[view at publisher]

We study socio-political systems in representative democracies. Motivated by problems that affect the proper functioning of the system, we build computational methods to answer research questions regarding the phenomena occurring in them. For each phenomenon, we curate novel datasets and propose interpretable models that build upon prior work on distributional representations of text, topic models, and discrete choice models. These models provide valuable insights and enable the construction of tools that could help solve some of the problems affecting the systems. First, we look at the problem of subjective bias in documents on the Web and in media. We curate a novel dataset based on Wikipedia's revision history that contains pairs of versions of the same Wikipedia article, where the subjective bias in one version has been corrected to generate the other version. We train a Bradley-Terry model that uses text features to perform a pairwise comparison of bias between these versions. We show that we can interpret the parameters of the model to discover the words most indicative of bias. Our model also learns to compute a real-valued bias score for documents. We show that this score can be used as a measure of bias across topics and domains not seen in training, including in the media, political speeches, law amendments, and tweets. Second, we infer effective strategies for improving user engagement in social media campaigns, taking the example of tweets about climate change. We build an interpretable model to rank tweets on the basis of predicted engagement by using their topic and metadata features. The ranking framework enables us to avoid the influence of confounding factors such as author popularity. We make several recommendations for the optimization of engagement, based on the learned model parameters, such as talking about mitigation and adaptation strategies, instead of projections and effects. Third, we study the influence of interest groups (lobbies) on parliaments, taking the European Parliament (EP) as an example. We curate novel datasets of the position papers of the lobbies and speeches of the members of the EP (MEPs), and we match them to discover interpretable links between lobbies and MEPs. In the absence of ground-truth data, we indirectly validate the discovered links by comparing them with a dataset, which we curate, of retweet links between lobbies and MEPs and with the publicly disclosed meetings of MEPs. An aggregate analysis of the discovered links reveals patterns that follow ideology (e.g., the center-left political group is more associated with social causes). Finally, we study the law-making process within the EP. We mine a rich dataset of edits to law proposals and develop models that predict their acceptance by parliamentary committees. Our models use textual and metadata features of the edit, and latent features to capture the interaction between parliamentarians and laws. We show that the model accurately predicts the acceptance of the edits. Furthermore, we interpret the parameters of the learned model to derive interesting insights into the legislative process. We show that, among other observations, edits that narrow the scope of the law and insert recommendations for actions are more likely to be accepted than those that insert obligations.

Leveraging Unlabeled Data to Track Memorization
M. Forouzesh, H. Sedghi and P. Thiran
11th International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda, May 1-5, 2023.

Deep neural networks may easily memorize noisy labels present in real-world data, which degrades their ability to generalize. It is therefore important to track and evaluate the robustness of models against noisy label memorization. We propose a metric, called susceptibility, to gauge such memorization for neural networks. Susceptibility is simple and easy to compute during training. Moreover, it does not require access to ground-truth labels and it only uses unlabeled data. We empirically show the effectiveness of our metric in tracking memorization on various architectures and datasets and provide theoretical insights into the design of the susceptibility metric. Finally, we show through extensive experiments on datasets with synthetic and real-world label noise that one can utilize susceptibility and the overall training accuracy to distinguish models that maintain a low memorization on the training set and generalize well to unseen clean data.

Deep Learning Generalization with Limited and Noisy Labels
M. Forouzesh
2023.
[view at publisher]

Deep neural networks have become ubiquitous in today's technological landscape, finding their way in a vast array of applications. Deep supervised learning, which relies on large labeled datasets, has been particularly successful in areas such as image classification. However, the effectiveness of these networks heavily depends on the quality of the data they can use. In most practical applications, obtaining high-quality labeled data is expensive, time-consuming, and sometimes even impossible, making the available dataset limited both in size and in quality, as the labeled data may contain noise due to various reasons such as human labeling errors. The main objective of this thesis is to develop practical methods measuring the quality of the generalization of deep neural networks in such settings with limited and/or noisy labeled data. We propose novel methods and metrics for estimating generalization, overfitting, and memorization throughout training, which are easy to deploy, which eliminate the need for a high-quality validation/test set and which optimize the use of the available data. First, we establish a connection between neural network output \emph{sensitivity} and variance in the bias-variance decomposition of the loss function. Through extensive empirical results, we show that sensitivity is strongly correlated with the test loss and can serve as a promising tool for selecting neural network architectures. We find that sensitivity is particularly effective in identifying the benefits of certain architectural choices, such as convolutional layers. Additionally, we promote sensitivity as a zero-cost metric that can estimate model generalization even before training. Our results show that sensitivity effectively captures the benefits of specific regularization and initialization techniques, such as batch normalization and Xavier parameter initialization. Second, we introduce \emph{generalization penalty}, which measures how much a gradient step on one mini-batch negatively affects the performance on another mini-batch. From this, we derive a new metric called \emph{gradient disparity} and propose it as an early stopping criterion for deep neural networks trained with mini-batch gradient descent. Our extensive empirical experiments demonstrate that gradient disparity is strongly correlated with the generalization error in state-of-the-art configurations. Moreover, it is very efficient to use because of its low computational tractability. Gradient disparity even outperforms traditional validation methods such as $k$-fold cross-validation when the available data is limited, because it can use all available samples for training. When the available data has noisy labels, it signals overfitting better than the validation data. Third, we propose a metric called \emph{susceptibility} to evaluate neural network robustness against label noise memorization. Susceptibility is easy to compute during training and requires only unlabeled data, making it practical for real-world applications. We demonstrate its effectiveness in tracking memorization on various architectures and datasets, accurately distinguishing models that maintain low memorization on the training set. We also provide theoretical insights into the design of susceptibility as a metric for tracking memorization. We demonstrate its effectiveness through thorough experiments on several datasets with synthetic and real-world label noise.

Mining Effective Strategies for Climate Change Communication
A. Suresh, L. Milikic, F. Murray, Y. Zhu and M. Grossglauser
ICLR 2023 Workshop on Tackling Climate Change with Machine Learning, Kigali, Rwanda, May 4, 2023.
[full text]

With the goal of understanding effective strategies to communicate about climate change, we build interpretable models to rank tweets related to climate change with respect to the engagement they generate. Our models are based on the Bradley-Terry model of pairwise comparison outcomes and use a combination of the tweets’ topic and metadata features to do the ranking. To remove confounding factors related to author popularity and minimise noise, they are trained on pairs of tweets that are from the same author and around the same time period and have a sufficiently large difference in engagement. The models achieve good accuracy on a held-out set of pairs. We show that we can interpret the parameters of the trained model to identify the topic and metadata features that contribute to high engagement. Among other observations, we see that topics related to climate projections, human cost and deaths tend to have low engagement while those related to mitigation and adaptation strategies have high engagement. We hope the insights gained from this study will help craft effective climate communication to promote engagement, thereby lending strength to efforts to tackle climate change.

2022

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function
S. Masiha, S. Salehkaleybar, N. He, N. Kiyavash and P. Thiran
2022.
[full text]

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with $1\le\alpha\le2$ which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving $\epsilon$-global optimum is $\mathcal{O}(\epsilon^{-7/(2\alpha)+1})$ for $1\le\alpha< 3/2$ and $\mathcal{\tilde{O}}(\epsilon^{-2/(\alpha)})$ for $3/2\le\alpha\le 2$. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to ${\mathcal{O}}(\epsilon^{-2})$ for $\alpha=1$ using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.

Causal Effect Identification with Context-specific Independence Relations of Control Variables
E. Mokhtarian, F. Jamshidi, J. Etesami and N. Kiyavash
International Conference on Artificial Intelligence and Statistics, ELECTR NETWORK, Mar 28-30, 2022.

We study the problem of causal effect identification from observational distribution given the causal graph and some context-specific independence (CSI) relations. It was recently shown that this problem is NP-hard, and while a sound algorithm to learn the causal effects is proposed in Tikka et al. (2019), no provably complete algorithm for the task exists. In this work, we propose a sound and complete algorithm for the setting when the CSI relations are limited to observed nodes with no parents in the causal graph. One limitation of the state of the art in terms of its applicability is that the CSI relations among all variables, even unobserved ones, must be given (as opposed to learned). Instead, We introduce a set of graphical constraints under which the CSI relations can be learned from mere observational distribution. This expands the set of identifiable causal effects beyond the state of the art.

The Role of Adaptivity in Source Identification with Time Queries
G. Odor
2022.
[view at publisher]

Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final size of the epidemic on the location of the initial infected agents (sources): common sense dictates that the most dangerous location for the sources is the largest city, but the second chapter of the thesis shows that this holds true only if the epidemic is just above the infection threshold. Identifying the initial infected agents can help us better understand the epidemic. The focus of this thesis is on identifying the very first infected agent, also called the source or patient zero. According to the standard assumptions, a few agents reveal their symptom onset time, and then it is our goal to identify the source based on this information, together with full knowledge of the underlying network. Unfortunately, even if we can choose the set of agents that are queried about their symptom onset time, the number of queries required for reliable source identification is too large for practical applications. In this thesis, we carefully assess if this issue can be mitigated by introducing adaptivity to the standard assumptions. Our main goal is to study the reduction in the query complexity if the queries can be chosen adaptively to previous answers, but we also investigate whether adaptively querying the edges can relax the full knowledge assumption on the network. Providing rigorous proofs about source identification with time queries is difficult. A notable exception is when the infection is passed with a known, deterministic delay from each agent to all of its neighbors, in which case the number of required non-adaptive and adaptive queries are equivalent to well-known notions in combinatorics; the metric dimension (MD) and the sequential metric dimension (SMD), respectively. We extend previous results in the field by computing the MD of a large class of random trees, where adaptivity can significantly reduce the query complexity, and the SMD of Erdos-Rényi random networks, where the reduction is found to be small, at most a constant factor. We address the case of non-deterministic diffusion processes for the first time in the mathematical literature: on the path graph, we observe a striking, double logarithmic decrease in adaptive query complexity compared to the non-adaptive case. Our analysis on the robustness of the MD to adding a single edge to specially constructed and d-dimensional grid networks suggests that even small changes in the network could easily derail source identification algorithms. This is concerning since it is difficult to obtain a perfect dataset about the entire contact network in practice. Inspired by recent implementations of contact tracing, we propose new source identification assumptions, where not only the symptom onset times, but also the edges of the network are queried by the algorithm, resulting in less, but potentially higher quality information. We propose two local search algorithms that outperform state of the art identification algorithms tailored to the new assumptions, and we analytically approximate their success probabilities on realistic random graph models. The adaptive assumptions enable us to evaluate our algorithms on a COVID-19 epidemic simulator: the first time that source identification algorithms are tested on such a complex dataset.

TB Hackathon: Development and Comparison of Five Models to Predict Subnational Tuberculosis Prevalence in Pakistan
S. Alba, E. Rood, F. Mecatti, J. M. Ross, P. J. Dodd, S. Chang, M. Potgieter, G. Bertarelli, N. J. Henry, K. E. LeGrand, W. Trouleau, D. Shaweno, P. MacPherson, Z. Z. Qin, C. Mergenthaler, F. Giardina, E. Augustijn, A. Q. Baloch and A. Latif
Tropical Medicine And Infectious Disease, vol. 7, no. 1, 13, 2022.
[view at publisher]

Pakistan's national tuberculosis control programme (NTP) is among the many programmes worldwide that value the importance of subnational tuberculosis (TB) burden estimates to support disease control efforts, but do not have reliable estimates. A hackathon was thus organised to solicit the development and comparison of several models for small area estimation of TB. The TB hackathon was launched in April 2019. Participating teams were requested to produce district-level estimates of bacteriologically positive TB prevalence among adults (over 15 years of age) for 2018. The NTP provided case-based data from their 2010-2011 TB prevalence survey, along with data relating to TB screening, testing and treatment for the period between 2010-2011 and 2018. Five teams submitted district-level TB prevalence estimates, methodological details and programming code. Although the geographical distribution of TB prevalence varied considerably across models, we identified several districts with consistently low notification-to-prevalence ratios. The hackathon highlighted the challenges of generating granular spatiotemporal TB prevalence forecasts based on a cross-sectional prevalence survey data and other data sources. Nevertheless, it provided a range of approaches to subnational disease modelling. The NTP's use and plans for these outputs shows that, limitations notwithstanding, they can be valuable for programme planning.

On the robustness of the metric dimension of grid graphs to adding a single edge
S. Mashkaria, G. Odor and P. Thiran
Discrete Applied Mathematics, vol. 316, 1 - 27, 2022.
[view at publisher]

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to the graph. The extra edge can either be selected adversarially, in which case we are interested in the largest possible value that the MD can take, or uniformly at random, in which case we are interested in the distribution of the MD. The adversarial setting has already been studied by [Eroh et. al., 2015] for general graphs, who found an example where the MD doubles on adding a single edge. By constructing a different example, we show that this increase can be as large as exponential. However, we believe that such a large increase can occur only in specially constructed graphs, and that in most interesting graph families, the MD at most doubles on adding a single edge. We prove this for $d$-dimensional grid graphs, by showing that $2d$ appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of $d=2$, we show that it suffices to choose the four corners as landmarks. Finally, when the extra edge is sampled uniformly at random, we conjecture that the MD of 2-dimensional grids converges in probability to $3+\mathrm{Ber}(8/27)$, and we give an almost complete proof.

The power of adaptivity in source identification with time queries on the path
V. Lecomte, G. Odor and P. Thiran
Theoretical Computer Science, vol. 911, 92 - 123, 2022.
[view at publisher]

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph $G=(V,E)$, an unknown source node $v^* \in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $e\in E$, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $\sigma^2$. An algorithm then attempts to identify $v^*$ by querying nodes $q \in V$ and being told the length of the shortest path between $q$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: \emph{non-adaptive}, in which all query nodes must be decided in advance, and \emph{adaptive}, in which each query can depend on the results of the previous ones. Both settings are motivated by an application of the problem to epidemic processes (where the source is called patient zero), which we discuss in detail. We characterize the query complexity when $G$ is an $n$-node path. In the non-adaptive setting, $\Theta(n\sigma^2)$ queries are needed for $\sigma^2 \leq 1$, and $\Theta(n)$ for $\sigma^2 \geq 1$. In the adaptive setting, somewhat surprisingly, only $\Theta(\log\log_{1/\sigma}n)$ are needed when $\sigma^2 \leq 1/2$, and $\Theta(\log \log n)+O_\sigma(1)$ when $\sigma^2 \geq 1/2$. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process.

2021

Adversarial orthogonal regression: Two non-linear regressions for causal inference
M. R. Heydari, S. Salehkaleybar and K. Zhang
Neural Networks, vol. 143, 66 - 73, 2021.
[view at publisher]

We propose two nonlinear regression methods, namely, Adversarial Orthogonal Regression (AdOR) for additive noise models and Adversarial Orthogonal Structural Equation Model (AdOSE) for the general case of structural equation models. Both methods try to make the residual of regression independent from regressors, while putting no assumption on noise distribution. In both methods, two adversarial networks are trained simultaneously where a regression network outputs predictions and a loss network that estimates mutual information (in AdOR) and KL-divergence (in AdOSE). These methods can be formulated as a minimax two-player game; at equilibrium, AdOR finds a deterministic map between inputs and output and estimates mutual information between residual and inputs, while AdOSE estimates a conditional probability distribution of output given inputs. The proposed methods can be used as subroutines to address several learning problems in causality, such as causal direction determination (or more generally, causal structure learning) and causal model estimation. Experimental results on both synthetic and real-world data demonstrate that the proposed methods have remarkable performance with respect to previous solutions.

Sequential metric dimension for random graphs
G. Odor and P. Thiran
Journal of Applied Probability, vol. 58, no. 4, 909 - 951, 2021.
[view at publisher]

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, the distance between the nodes v_j and v* . The sequential metric dimension (SMD) is the minimal number of queries that the player needs to guess the target with absolute certainty, no matter where the target is. The term SMD originates from the related notion of metric dimension (MD), which can be defined the same way as the SMD except that the player’s queries are non-adaptive. In this work we extend the results of Bollobás, Mitsche, and Prałat on the MD of Erdős–Rényi graphs to the SMD. We find that, in connected Erdős–Rényi graphs, the MD and the SMD are a constant factor apart. For the lower bound we present a clean analysis by combining tools developed for the MD and a novel coupling argument. For the upper bound we show that a strategy that greedily minimizes the number of candidate targets in each step uses asymptotically optimal queries in Erdős–Rényi graphs. Connections with source localization, binary search on graphs, and the birthday problem are discussed.

Switchover phenomenon induced by epidemic seeding on geometric networks
G. Odor, D. Czifra, J. Komjáthy, L. Lovász and M. Karsai
Proceedings Of The National Academy Of Sciences Of The United States Of America (PNAS), vol. 118, no. 41, e2112607118, 2021.
[view at publisher]

It is a fundamental question in disease modeling how the initial seeding of an epidemic, spreading over a network, determines its final outcome. One important goal has been to find the seed configuration, which infects the most individuals. Although the identified optimal configurations give insight into how the initial state affects the outcome of an epidemic, they are unlikely to occur in real life. In this paper we identify two important seeding scenarios, both motivated by historical data, that reveal a complex phenomenon. In one scenario, the seeds are concentrated on the central nodes of a network, while in the second one, they are spread uniformly in the population. Comparing the final size of the epidemic started from these two initial conditions through data-driven and synthetic simulations on real and modeled geometric metapopulation networks, we find evidence for a switchover phenomenon: When the basic reproduction number R0 is close to its critical value, more individuals become infected in the first seeding scenario, but for larger values of R0, the second scenario is more dangerous. We find that the switchover phenomenon is amplified by the geometric nature of the underlying network and confirm our results via mathematically rigorous proofs, by mapping the network epidemic processes to bond percolation. Our results expand on the previous finding that, in the case of a single seed, the first scenario is always more dangerous and further our understanding of why the sizes of consecutive waves of a pandemic can differ even if their epidemic characters are similar.

Disparity Between Batches as a Signal for Early Stopping
M. Forouzesh and P. Thiran
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2021), Bilbao, Basque Country, Spain, September 13-17, 2021.
[view at publisher]

We propose a metric for evaluating the generalization ability of deep neural networks trained with mini-batch gradient descent. Our metric, called gradient disparity, is the l2 norm distance between the gradient vectors of two mini-batches drawn from the training set. It is derived from a probabilistic upper bound on the difference between the classification errors over a given mini-batch, when the network is trained on this mini-batch and when the network is trained on another mini-batch of points sampled from the same dataset. We empirically show that gradient disparity is a very promising early-stopping criterion (i) when data is limited, as it uses all the samples for training and (ii) when available data has noisy labels, as it signals overfitting better than the validation data. Furthermore, we show in a wide range of experimental settings that gradient disparity is strongly related to the generalization error between the training and test sets, and that it is also very informative about the level of label noise.

Learning Self-Exciting Temporal Point Processes Under Noisy Observations
W. Trouleau
2021.
[view at publisher]

Understanding the diffusion patterns of sequences of interdependent events is a central question for a variety of disciplines. Temporal point processes are a class of elegant and powerful models of such sequences; these processes have become popular across multiple fields of research due to the increasing availability of data that captures the occurrence of events over time. A notable example is the Hawkes process. It was originally introduced by Alan Hawkes in 1971 to model the diffusion of earthquakes and was subsequently applied across fields such as epidemiology, neuroscience, criminology, finance, genomic, and social-network analysis. A central question in these fields is the inverse problem of uncovering the diffusion patterns of the events from the observed data. The methods for solving this inverse problem assume that, in general, the data is noiseless. However, real-world observations are frequently tainted by noise in a number of ways. Most existing methods are not robust against noise and, in the presence of even a small amount of noise in the data, they might completely fail to recover the underlying dynamics. In this thesis, we remedy this shortcoming and address this problem for several types of observational noise. First, we study the effects of small event-streams that are known to make the learning task challenging by amplifying the risk of overfitting. Using recent advances in variational inference, we introduce a new algorithm that leads to better regularization schemes and provides a measure of uncertainty on the estimated parameters. Second, we consider events corrupted by unknown synchronized time delays. We show that the so-called synchronization noise introduces a bias in the existing estimation methods, which must be handled with care. We provide an algorithm to robustly learn the diffusion dynamics of the underlying process under this class of synchronized delays. Third, we introduce a wider class of random and unknown time shifts, referred to as random translations, of which synchronization noise is a special case. We derive the statistical properties of Hawkes processes subject to random translations. In particular, we prove that the cumulants of Hawkes processes are invariant to random translations and we show that cumulant-based algorithms can be used to learn their underlying causal structure even when unknown time shifts distort the observations. Finally, we consider another class of temporal point processes, the so-called Wold process that solves a computational limitation of the Bayesian treatment of Hawkes processes while retaining similar properties. We address the problem of learning the parameters of a Wold process by relaxing some of the restrictive assumptions made in the state of the art and by introducing a Bayesian approach for inferring its parameters. In summary, the results presented in this dissertation highlight the shortcomings of standard inference methods used to fit temporal point processes. Consequently, these results deepen our ability to extract reliable insights from networks of interdependent event streams.

Discrete-Choice Mining of Social Processes
V. Kristof
2021.
[view at publisher]

Poor decisions and selfish behaviors give rise to seemingly intractable global problems, such as the lack of transparency in democratic processes, the spread of conspiracy theories, and the rise in greenhouse gas emissions. However, people are more predictable than we think, and with machine-learning algorithms and sufficiently large datasets, we can design accurate models of human behavior in a variety of settings. In this thesis, to gain insight into social processes, we develop highly interpretable probabilistic choice-models. We draw from the econometrics literature on discrete-choice models and combine them with matrix factorization methods, Bayesian statistics, and generalized linear models. These predictive models enable interpretability through their learned parameters and latent factors. First, we study the social dynamics behind group collaborations for the collective creation of content, such as in Wikipedia, the Linux kernel, and the European Union law-making process. By combining the Bradley-Terry and Rasch models with matrix factorization and natural language processing, we develop a model of edit acceptance in peer-production systems. We discover controversial components (e.g., Wikipedia articles and European laws) and influential users (e.g., Wikipedia editors and parliamentarians), as well as features that correlate with a high probability of edit acceptance. The latent representations capture non-linear interactions between components and users, and they cluster well into different topics (e.g., historical figures and TV characters in Wikipedia, business and environment in European laws). Second, we develop an algorithm for predicting the outcome of elections and of referenda by combining matrix factorization and generalized linear models. Our algorithm learns representations of votes and regions, which capture ideological and cultural voting patterns (e.g., liberal/conservative, rural/urban), and it predicts the vote results in unobserved regions from partial observations. We test our model on voting data in Germany, Switzerland, and the US, and we deploy it on a Web platform to predict Swiss referendum votes in real-time. On average, our predictions reach a mean absolute error of 1% after observing only 5% of the regions. Third, we study how people perceive the carbon footprint of their day-to-day actions. We cast this problem as a comparison problem between pairs of actions (e.g., the difference between flying across continents and using household appliances), and we develop a statistical model of relative comparisons reminiscent of the Thurstone model in psychometrics. The model learns the usersâ perception as the parameters of a Bayesian linear regression, which enables us to derive an active-learning algorithm to collect data efficiently. Our experiments show that users overestimate the emissions of low-footprint actions and underestimate those of high-footprint actions. Finally, we design a probabilistic model of pairwise-comparison outcomes that capture a wide range of time dynamics. We achieve this by replacing the static parameters of a class of popular pairwise-comparison models with continuous-time Gaussian processes. We also develop an efficient inference algorithm that computes, with only a few linear-time iterations over the data, an approximate Bayesian posterior distribution.

Generalization Comparison of Deep Neural Networks via Output Sensitivity
M. Forouzesh, F. Salehi and P. Thiran
25th International Conference on Pattern Recognition, Milan, Italy, January 10-15, 2021.
[full text] [view at publisher]

Although recent works have brought some insights into the performance improvement of techniques used in state-of-the-art deep-learning models, more work is needed to understand their generalization properties. We shed light on this matter by linking the loss function to the output's sensitivity to its input. We find a rather strong empirical relation between the output sensitivity and the variance in the bias-variance decomposition of the loss function, which hints on using sensitivity as a metric for comparing the generalization performance of networks, without requiring labeled data. We find that sensitivity is decreased by applying popular methods which improve the generalization performance of the model, such as (1) using a deep network rather than a wide one, (2) adding convolutional layers to baseline classifiers instead of adding fully-connected layers, (3) using batch normalization, dropout and max-pooling, and (4) applying parameter initialization techniques.

War of Words II: Enriched Models of Law-Making Processes
V. Kristof, A. Suresh, M. Grossglauser and P. Thiran
The Web Conference 2021 (WWW '21), Ljubljana, Slovenia, April 19-23, 2021.
[full text] [view at publisher]

The European Union law-making process is an instance of a peer- production system. We mine a rich dataset of law edits and intro- duce models predicting their adoption by parliamentary committees. Edits are proposed by parliamentarians, and they can be in conflict with edits of other parliamentarians and with the original proposition in the law. Our models combine three different categories of features: (a) Explicit features extracted from data related to the edits, the parliamentarians, and the laws, (b) latent features that capture bi-linear interactions between parliamentarians and laws, and (c) text features of the edits. We show experimentally that this combination enables us to accurately predict the success of the edits. Furthermore, it leads to model parameters that are interpretable, hence provides valuable insight into the law-making process.

A Variational Inference Approach to Learning Multivariate Wold Processes
J. Etesami, W. Trouleau, N. Kiyavash, M. Grossglauser and P. Thiran
24th International Conference on Artificial Intelligence and Statistics (AISTATS), San Diego, California, USA, April 13-15, 2021.
[full text]

Temporal point-processes are often used for mathematical modeling of sequences of discrete events with asynchronous timestamps. We focus on a class of temporal point-process models called multivariate Wold processes (MWP). These processes are well suited to model real-world communication dynamics. Statistical inference on such processes often requires learning their corresponding parameters using a set of observed timestamps. In this work, we relax some of the restrictive modeling assumptions made in the state-of-the-art and introduce a Bayesian approach for inferring the parameters of MWP. We develop a computationally efficient variational inference algorithm that allows scaling up the approach to high-dimensional processes and long sequences of observations. Our experimental results on both synthetic and real-world datasets show that our proposed algorithm outperforms existing methods.

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees
J. Komjáthy and G. Odor
European Journal of Combinatorics, vol. 95, 103317, 2021.
[view at publisher]

The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. In this paper we show a Law of Large Numbers (LLN) for the metric dimension of some classes of trees: critical Galton–Watson trees conditioned to have size n, and growing general linear preferential attachment trees. The former class includes uniform random trees, the latter class includes Yule-trees (also called random recursive trees), m-ary increasing trees, binary search trees, and positive linear preferential attachment trees. In all these cases, we are able to identify the limiting constant in the LLN explicitly. Our result relies on the insight that the metric dimension can be related to subtree properties, and hence we can make use of the powerful fringe-tree literature developed by Aldous and Janson et al.

2020

Augmenting and Tuning Knowledge Graph Embeddings
R. Bamler, F. Salehi and S. Mandt
35th Uncertainty in Artificial Intelligence (UAI) Conference, Tel Aviv, ISRAEL, Jul 22-25, 2019.

Knowledge graph embeddings rank among the most successful methods for link prediction in knowledge graphs, i.e., the task of completing an incomplete collection of relational facts. A downside of these models is their strong sensitivity to model hyperparameters, in particular regularizers, which have to be extensively tuned to reach good performance [Kadlec el al, 2017]. We propose an efficient method for large scale hyperparameter tuning by interpreting these models in a probabilistic framework. After a model augmentation that introduces perentity hyperparameters, we use a variational expectation-maximization approach to tune thousands of such hyperparameters with minimal additional cost. Our approach is agnostic to details of the model and results in a new state of the art in link prediction on standard benchmark data.

A meta-learning approach for genomic survival analysis
Y. L. Qiu, H. Zheng, A. Devos, H. Selby and O. Gevaert
Nature Communications, vol. 11, no. 1, 6350, 2020.
[full text] [view at publisher]

RNA sequencing has emerged as a promising approach in cancer prognosis as sequencing data becomes more easily and affordably accessible. However, it remains challenging to build good predictive models especially when the sample size is limited and the number of features is high, which is a common situation in biomedical settings. To address these limitations, we propose a meta-learning framework based on neural networks for survival analysis and evaluate it in a genomic cancer research setting. We demonstrate that, compared to regular transfer-learning, meta-learning is a significantly more effective paradigm to leverage high-dimensional data that is relevant but not directly related to the problem of interest. Specifically, meta-learning explicitly constructs a model, from abundant data of relevant tasks, to learn a new task with few samples effectively. For the application of predicting cancer survival outcome, we also show that the meta-learning framework with a few samples is able to achieve competitive performance with learning from scratch with a significantly larger number of samples. Finally, we demonstrate that the meta-learning model implicitly prioritizes genes based on their contribution to survival prediction and allows us to identify important pathways in cancer. RNA-sequencing data from tumours can be used to predict the prognosis of patients. Here, the authors show that a neural network meta-learning approach can be useful for predicting prognosis from a small number of samples.

MPGM: Scalable and Accurate Multiple Network Alignment
E. Kazemi and M. Grossglauser
Ieee-Acm Transactions On Computational Biology And Bioinformatics, vol. 17, no. 6, 2040 - 2052, 2020.
[view at publisher]

Protein-protein interaction (PPI) network alignment is a canonical operation to transfer biological knowledge among species. The alignment of PPI-networks has many applications, such as the prediction of protein function, detection of conserved network motifs, and the reconstruction of species' phylogenetic relationships. A good multiple-network alignment (MNA), by considering the data related to several species, provides a deep understanding of biological networks and system-level cellular processes. With the massive amounts of available PPI data and the increasing number of known PPI networks, the problem of MNA is gaining more attention in the systems-biology studies. In this paper, we introduce a new scalable and accurate algorithm, called MPGM, for aligning multiple networks. The MPGM algorithm has two main steps: (i) SeedGeneration and (ii) MultiplePercolation. In the first step, to generate an initial set of seed tuples, the SeedGeneration algorithm uses only protein sequence similarities. In the second step, to align remaining unmatched nodes, the MultiplePercolation algorithm uses network structures and the seed tuples generated from the first step. We show that, with respect to different evaluation criteria, MPGM outperforms the other state-of-the-art algorithms. In addition, we guarantee the performance of MPGM under certain classes of network models. We introduce a sampling-based stochastic model for generating k correlated networks. We prove that for this model if a sufficient number of seed tuples are available, the MULTIPLEPERCOLATION algorithm correctly aligns almost all the nodes. Our theoretical results are supported by experimental evaluations over synthetic networks.

Scalable and Efficient Comparison-based Search without Features
D. Chumbalov, L. Maystre and M. Grossglauser
37th International Conference on Machine Learning (ICML 2020), Online, July 13-18, 2020.

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generates noisy answers. First, we consider the non-blind setting where these features are accessible. We propose a new Bayesian comparison-based search algorithm with noisy answers; it has low computational complexity yet is efficient in the number of queries. We provide theoretical guarantees, deriving the form of the optimal query and proving almost sure convergence to the target t. Second, we consider the blind setting, where the object features are hidden from the search algorithm. In this setting, we combine our search method and a new distributional triplet embedding algorithm into one scalable learning framework called LEARN2SEARCH. We show that the query complexity of our approach on two real-world datasets is on par with the non-blind setting, which is not achievable using any of the current state-of-the- art embedding methods. Finally, we demonstrate the efficacy of our framework by conducting an experiment with users searching for movie actors.

Self-Supervised Prototypical Transfer Learning for Few-Shot Classification
C. Medina, A. Devos and M. Grossglauser
7th ICML Workshop on Automated Machine Learning (AutoML 2020), Vienna, Austria, Jul 12, 2020 – Jul 18, 2020.
[video] [code] [full text]

Recent advances in transfer learning and few-shot learning largely rely on annotated data related to the goal task during (pre-)training. However, collecting sufficiently similar and annotated data is often infeasible. Building on advances in self-supervised and few-shot learning, we propose to learn a metric embedding that clusters unlabeled samples and their augmentations closely together. This pre-trained embedding serves as a starting point for classification with limited labeled goal task data by summarizing class clusters and fine-tuning. Experiments show that our approach significantly outperforms state-of the-art unsupervised meta-learning approaches, and is on par with supervised performance. In a cross-domain setting, our approach is competitive with its classical fully supervised counterpart.

Regression Networks for Meta-Learning Few-Shot Classification
A. Devos and M. Grossglauser
7th ICML Workshop on Automated Machine Learning (AutoML 2020), Vienna, Austria, 2020-07-12 - 2020-07-18.
[video] [code] [full text]

We propose regression networks for the problem of few-shot classification, where a classifier must generalize to new classes not seen in the training set, given only a small number of examples of each class. In high dimensional embedding spaces the direction of data generally contains richer information than magnitude. Next to this, state-of-the-art few-shot metric methods that compare distances with aggregated class representations, have shown superior performance. Combining these two insights, we propose to meta-learn classification of embedded points by regressing the closest approximation in every class subspace while using the regression error as a distance metric. Similarly to recent approaches fo few-shot learning, regression networks reflect a simple inductive bias that is beneficial in this limited-data regime and they achieve excellent results, especially when more aggregate class representations can be formed with multiple shots.

Sub-Matrix Factorization for Real-Time Vote Prediction
A. Immer, V. Kristof, M. Grossglauser and P. Thiran
The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining - KDD ’20, Virtual Event, August 23–27, 2020.
[view at publisher]

We address the problem of predicting aggregate vote outcomes (e.g., national) from partial outcomes (e.g., regional) that are revealed sequentially. We combine matrix factorization techniques and generalized linear models (GLMs) to obtain a flexible, efficient, and accurate algorithm. This algorithm works in two stages: First, it learns representations of the regions from high-dimensional historical data. Second, it uses these representations to fit a GLM to the partially observed results and to predict unobserved results. We show experimentally that our algorithm is able to accurately predict the outcomes of Swiss referenda, U.S. presidential elections, and German legislative elections. We also explore the regional representations in terms of ideological and cultural patterns. Finally, we deploy an online Web platform (www.predikon.ch) to provide real- time vote predictions in Switzerland and a data visualization tool to explore voting behavior. A by-product is a dataset of sequential vote results for 330 referenda and 2196 Swiss municipalities.

Quantifying the Effects of Contact Tracing, Testing, and Containment Measures in the Presence of Infection Hotspots
L. Lorch, H. Kremer, W. Trouleau, S. Tsirtsis, A. Szanto, B. Schölkopf and M. Gomez-Rodriguez
2020.
[code]

Multiple lines of evidence at the individual and population level strongly suggest that infection hotspots, or superspreading events, where a single individual infects many others, play a key role in the transmission dynamics of COVID-19. However, most of the existing epidemiological models either assume or result in a Poisson distribution of the number of infections caused by a single infectious individual, often called secondary infections. As a result, these models overlook the observed overdispersion in the number of secondary infections and are unable to accurately characterize infection hotspots. In this work, we aim to fill this gap by introducing a temporal point process framework that explicitly represents sites where infection hotspots may occur. Under our model, overdispersion on the number of secondary infections emerges naturally. Moreover, using an efficient sampling algorithm, we demonstrate how to apply Bayesian optimization with longitudinal case data to estimate the transmission rate of infectious individuals at sites they visit and in their households, as well as the mobility reduction due to social distancing. Simulations using fine-grained demographic data and site locations from several cities and regions demonstrate that our framework faithfully characterizes the observed longitudinal trend of COVID-19 cases. In addition, the simulations show that our model can be used to estimate the effect of testing, contact tracing, and containment at an unprecedented spatiotemporal resolution, and reveal that these measures do not decrease overdispersion in the number of secondary infections.

War of Words: The Competitive Dynamics of Legislative Processes
V. Kristof, M. Grossglauser and P. Thiran
The Web Conference - WWW ’20, Taipei, Taiwan, April 20-24, 2020.
[video] [code] [data] [view at publisher]

A body of law is an example of a dynamic corpus of text documents that are jointly maintained by a group of editors who compete and collaborate in complex constellations. Our goal is to develop predictive models for this process, thereby shedding light on the competitive dynamics of parliamentarians who make laws. For this purpose, we curated a dataset of 450 000 legislative edits introduced by European parliamentarians over the last ten years. An edit modifies the status quo of a law, and could be in competition with another edit if it modifies the same part of that law. We propose a model for predicting the success of such edits, in the face of both the inertia of the status quo and the competition between overlapping edits. The parameters of this model can be interpreted in terms of the influence of parliamentarians and of the controversy of laws.

Multi-armed Bandits in Action
F. Salehi
2020.
[view at publisher]

Making decisions is part and parcel of being human. Among a set of actions, we want to choose the one that has the highest reward. But the uncertainty of the outcome prevents us from always making the right decision. Making decisions under uncertainty can be studied in a principled way by the exploitation-exploration framework. The multi-armed bandit (MAB) framework is perhaps one of the simplest, and yet one of the most powerful settings to optimize a sequence of choices within an exploitation-exploration framework. In this thesis, I study several MAB related problems, from three different perspectives: I study (1) how machine-learning (ML) can benefit from MAB algorithms, (2) how MAB algorithms can affect humans, and (3) how human interactions can be studied in the MAB framework. (1) Optimization lies at the heart of almost all ML algorithms. Stochastic-gradient descent (SGD) and stochastic-coordinate descent (CD) are perhaps two of the most well known and widely used optimization algorithms. In Chapters 2 and 3, I revisit the datapoint and coordinate-selection procedure of SGD and CD from an MAB point of view. The goal is to reduce the training time of ML models. SGD works by estimating, on the fly, the gradient of the cost function by sampling a datapoint uniformly at random from a training set, and CD works by updating only a single decision variable (coordinate) sampled at random. Updating the modelâ s parameters based on, respectively, different datapoints or different coordinates, yields various improvements. However, a priori, it is not clear which datapoint or coordinate improves the model the most. I address this challenge by studying these problems in an MAB setting, and I develop algorithms to learn the optimal datapoint or coordinate selection strategies. Our methods often significantly reduce the training time of several machine-learning models. (2) Although some MAB algorithms are designed to improve ML algorithms, they can affect humansâ opinions about the outside world. In the personalized recommender systems, the goal is to predict the preference of a user and to suggest the best content to them. However, recent studies suggest that a personalized algorithm can learn and propagate systematic biases and polarize opinions [Pariser, 2011]. In Chapter 4, to combat bias, I propose to use constraints on the distribution from which a content is selected. The constraints can be designed to ameliorate polarization and biases. I combine the classic MAB setting with these constraints and show how an adaptation of an MAB algorithm can lead to a scalable algorithm with provable guarantees for the constrained setting. Furthermore, I show that our algorithms often significantly outperform the existing algorithms that we could apply to this setting. (3) Interacting with others is one of the main sources of information for us. In Chapter 5, I study how this natural setting in the human world can be studied in the bandit framework. I extend the classic single decision-maker setting of MAB to multiple decision-makers, where a decision-maker observes her neighborsâ decisions and rewards. Presumably, the additional information of the neighbors should improve the decisions. I show how to model such a decision-making process that appeals to the classic MAB framework. I study the new setting, in both stochastic and adversarial MAB frameworks, and I develop algorithms that incorporate the additional knowledge of the peers.

2019

A User Study of Perceived Carbon Footprint
V. Kristof, V. Quelquejay-Leclère, R. Zbinden, L. Maystre, M. Grossglauser and P. Thiran
Climate Change Workshop at NeurIPS, Vancouver, BC, Canada, December 8-14, 2019.
[full text]

We propose a statistical model to understand people's perception of their carbon footprint. Driven by the observation that few people think of CO2 impact in absolute terms, we design a system to probe people's perception from simple pairwise comparisons of the relative carbon footprint of their actions. The formulation of the model enables us to take an active-learning approach to selecting the pairs of actions that are maximally informative about the model parameters. We define a set of 18 actions and collect a dataset of 2183 comparisons from 176 users on a university campus. The early results reveal promising directions to improve climate communication and enhance climate mitigation.

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs
O. E. Dai, D. Cullina, N. Kiyavash and M. Grossglauser
Joint International Conference on Measurement and Modeling of Computer Systems - SIGMETRICS '19, Phoenix, AZ, USA, June, 2019.
[view at publisher]

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rényi graphs. However, very little is known about the existence of efficient algorithms to achieve graph alignment without seeds. In this work we identify a region in which a straightforward O(n11/5 log n)-time canonical labeling algorithm, initially introduced in the context of graph isomorphism, succeeds in aligning correlated Erdos-Rényi graphs. The algorithm has two steps. In the first step, all vertices are labeled by their degrees and a trivial minimum distance alignment (i.e., sorting vertices according to their degrees) matches a fixed number of highest degree vertices in the two graphs. Having identified this subset of vertices, the remaining vertices are matched using a alignment algorithm for bipartite graphs. Finally, we show that the implementation of a variant of this algorithm allows for the efficient alignment of large graphs under limited noise.

Learning Hawkes Processes from a Handful of Events
F. Salehi, W. Trouleau, M. Grossglauser and P. Thiran
33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, December 8-14, 2019.
[code] [full text]

Learning the causal-interaction network of multivariate Hawkes processes is a useful task in many applications. Maximum-likelihood estimation is the most common approach to solve the problem in the presence of long observation sequences. However, when only short sequences are available, the lack of data amplifies the risk of overfitting and regularization becomes critical. Due to the challenges of hyper-parameter tuning, state-of-the-art methods only parameterize regularizers by a single shared hyper-parameter, hence limiting the power of representation of the model. To solve both issues, we develop in this work an efficient algorithm based on variational expectation-maximization. Our approach is able to optimize over an extended set of hyper-parameters. It is also able to take into account the uncertainty in the model parameters by learning a posterior distribution over them. Experimental results on both synthetic and real datasets show that our approach significantly outperforms state-of-the-art methods under short observation sequences.

Learning Hawkes Processes Under Synchronization Noise
W. Trouleau, J. Etesami, M. Grossglauser, N. Kiyavash and P. Thiran
36th International Conference on Machine Learning, Long Beach, California, USA, June 9-15, 2019.
[full text]

Multivariate Hawkes processes (MHP) are widely used in a variety of fields to model the occurrence of discrete events. Prior work on learning MHPs has only focused on inference in the presence of perfect traces without noise. We address the problem of learning the causal structure of MHPs when observations are subject to an unknown delay. In particular, we introduce the so-called synchronization noise, where the stream of events generated by each dimension is subject to a random and unknown time shift. We characterize the robustness of the classic maximum likelihood estimator to synchronization noise, and we introduce a new approach for learning the causal structure in the presence of noise. Our experimental results show that our approach accurately recovers the causal structure of MHPs for a wide range of noise levels, and significantly outperforms classic estimation methods.

Pairwise Comparisons with Flexible Time-Dynamics
L. Maystre, V. Kristof and M. Grossglauser
25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), Anchorage, AK, August 04-08, 2019.
[full text] [view at publisher]

Inspired by applications in sports where the skill of players or teams competing against each other varies over time, we propose a probabilistic model of pairwise-comparison outcomes that can capture a wide range of time dynamics. We achieve this by replacing the static parameters of a class of popular pairwise-comparison models by continuous-time Gaussian processes; the covariance function of these processes enables expressive dynamics. We develop an efficient inference algorithm that computes an approximate Bayesian posterior distribution. Despite the flexbility of our model, our inference algorithm requires only a few linear-time iterations over the data and can take advantage of modern multiprocessor computer architectures. We apply our model to several historical databases of sports outcomes and find that our approach a) outperforms competing approaches in terms of predictive performance, b) scales to millions of observations, and c) generates compelling visualizations that help in understanding and interpreting the data.

Controlling Polarization in Personalization: An Algorithmic Framework
L. E. Celis, S. Kapoor, F. Salehi and N. Vishnoi
ACM Conference on Fairness, Accountability, and Transparency (FAT), Atlanta, GA, Jan 29-31, 2019.
[view at publisher]

Personalization is pervasive in the online space as it leads to higher efficiency for the user and higher revenue for the platform by individualizing the most relevant content for each user. However, recent studies suggest that such personalization can learn and propagate systemic biases and polarize opinions; this has led to calls for regulatory mechanisms and algorithms that are constrained to combat bias and the resulting echo-chamber effect. We propose a versatile framework that allows for the possibility to reduce polarization in personalized systems by allowing the user to constrain the distribution from which content is selected. We then present a scalable algorithm with provable guarantees that satisfies the given constraints on the types of the content that can be displayed to a user, but- subject to these constraints- will continue to learn and personalize the content in order to maximize utility. We illustrate this framework on a curated dataset of online news articles that are conservative or liberal, show that it can control polarization, and examine the trade-off between decreasing polarization and the resulting loss to revenue. We further exhibit thefl exibility and scalability of our approach by framing the problem in terms of the more general diverse content selection problem and test it empirically on both a News dataset and the MovieLens dataset.

Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees
L. E. Celis, L. Huang, V. Keswani and N. K. Vishnoi
ACM Conference on Fairness, Accountability, and Transparency (FAT), Atlanta, GA, Jan 29-31, 2019.
[view at publisher]

Developing classification algorithms that are fair with respect to sensitive attributes of the data is an important problem due to the increased deployment of classification algorithms in societal contexts. Several recent works have focused on studying classification with respect to specific fairness metrics, modeled the corresponding fair classification problem as constrained optimization problems, and developed tailored algorithms to solve them. Despite this, there still remain important metrics for which there are no fair classifiers with theoretical guarantees; primarily because the resulting optimization problem is non-convex. The main contribution of this paper is a meta-algorithm for classification that can take as input a general class of fairness constraints with respect to multiple non disjoint and multi-valued sensitive attributes, and which comes with provable guarantees. In particular, our algorithm can handle non-convex "linear fractional" constraints (which includes fairness constraints such as predictive parity) for which no prior algorithm was known. Key to our results is an algorithm for a family of classification problems with convex constraints along with a reduction from classification problems with linear fractional constraints to this family. Empirically, we observe that our algorithm is fast, can achieve near-perfect fairness with respect to various fairness metrics, and the loss in accuracy due to the imposed fairness constraints is often small.

A dashboard for controlling polarization in personalization
L. E. Celis, S. Kapoor, F. Salehi, V. Keswani and N. K. Vishnoi
Ai Communications, vol. 32, no. 1, 77 - 89, 2019.
[view at publisher]

Personalization is pervasive in the online space as it leads to higher efficiency for the user and higher revenue for the platform by individualizing the most relevant content for each user. However, recent studies suggest that such personalization can learn and propagate systemic biases and polarize opinions; this has led to calls for regulatory mechanisms and algorithms that are constrained to combat bias and the resulting echo-chamber effect. We present our balanced news feed via a demo that displays a dashboard through which users can view the political leaning of their news consumption and set their polarization constraints. The balanced feed, as generated by the user-defined constraints, is then showcased side-by-side with the unconstrained (polarized) feed for comparison.

[Re] Meta learning with differentiable closed-form solvers
A. Devos, S. Chatel and M. Grossglauser
The ReScience journal C, 2019.
[full text]

In this work, we present a reproduction of the paper of Bertinetto et al. ”Meta- learning with differentiable closed-form solvers” as part of the ICLR 2019 Reproducibility Challenge. In successfully reproducing the most crucial part of the paper, we reach a performance that is comparable with or superior to the original paper on two benchmarks for several settings. We evaluate new baseline results, using a new dataset presented in the paper. Yet, we also provide multiple remarks and recommendations about reproducibility and comparability. After we brought our reproducibility work to the authorsʼ attention, they have updated the original paper on which this work is based and released code as well. Our contributions mainly consist in reproducing the most important results of their original paper, in giving insight in the reproducibility and in providing a first open-source implementation.

A General Framework for Sensor Placement in Source Localization
B. Spinelli, E. Celis and P. Thiran
IEEE Transactions on Network Science and Engineering, vol. 6, no. 2, 86 - 102, 2019.
[full text] [view at publisher]

When an epidemic spreads in a given network of individuals or communities, can we detect its source using only the information provided by a small set of nodes? We propose a general framework that incorporates two dimensions. First, we can either rely exclusively on a set of selected nodes (i.e., sensors) which always reveal their state independently of any particular epidemic (these are called static), or we can add some sensors (called dynamic) as an epidemic spreads, depending on which additional information is required. Second, the method can either localizes the source after an epidemic has spread through the entire network (offline), or while the epidemic is ongoing (online). We empirically study the performance of offline and online localization both with and without dynamic sensors. Our analysis shows that, by using dynamic sensors, the number of sensors necessary to localize the source is reduced by up to a factor of 10 and that, even with high-variance transmission delays, the source can be localized by using fewer than 5% of the nodes as sensors.

2018

SLANG: Fast Structured Covariance Approximations for Bayesian Deep Learning with Natural Gradient
A. Mishkin, F. Kunstner, D. Nielsen, M. Schmidt and M. E. Khan
32nd Conference on Neural Information Processing Systems (NIPS), Montreal, CANADA, Dec 02-08, 2018.

Uncertainty estimation in large deep-learning models is a computationally challenging task, where it is difficult to form even a Gaussian approximation to the posterior distribution. In such situations, existing methods usually resort to a diagonal approximation of the covariance matrix despite the fact that these matrices are known to result in poor uncertainty estimates. To address this issue, we propose a new stochastic, low-rank, approximate natural-gradient (SLANG) method for variational inference in large, deep models. Our method estimates a "diagonal plus low-rank" structure based solely on back-propagated gradients of the network log-likelihood. This requires strictly less gradient computations than methods that compute the gradient of the whole variational objective. Empirical evaluations on standard benchmarks confirm that SLANG enables faster and more accurate estimation of uncertainty than mean-field methods, and performs comparably to state-of-the-art methods.

Coordinate Descent with Bandit Sampling
F. Salehi, P. Thiran and L. E. Celis
32nd Conference on Neural Information Processing Systems (NIPS), Montreal, CANADA, Dec 02-08, 2018.

Coordinate descent methods usually minimize a cost function by updating a random decision variable (corresponding to one coordinate) at a time. Ideally, we would update the decision variable that yields the largest decrease in the cost function. However, finding this coordinate would require checking all of them, which would effectively negate the improvement in computational tractability that coordinate descent is intended to afford. To address this, we propose a new adaptive method for selecting a coordinate. First, we find a lower bound on the amount the cost function decreases when a coordinate is updated. We then use a multi-armed bandit algorithm to learn which coordinates result in the largest lower bound by interleaving this learning with conventional coordinate descent updates except that the coordinate is selected proportionately to the expected decrease. We show that our approach improves the convergence of coordinate descent methods both theoretically and experimentally.

Stochastic Optimal Control of Epidemic Processes in Networks
L. Lorch, A. De, S. Bhatt, W. Trouleau, U. Upadhyay and M. Gomez-Rodriguez
Machine Learning for Health (ML4H) Workshop at NeurIPS 2018, Palais des Congrès de Montréal, Montréal, Canada, December 8, 2018.
[full text]

We approach the development of models and control strategies of susceptible-infected-susceptible (SIS) epidemic processes from the perspective of marked temporal point processes and stochastic optimal control of stochastic differential equations (SDEs) with jumps. In contrast to previous work, this novel perspective is particularly well-suited to make use of fine-grained data about disease outbreaks and lets us overcome the shortcomings of current control strategies. Our control strategy resorts to treatment intensities to determine who to treat and when to do so to minimize the amount of infected individuals over time. Preliminary experiments with synthetic data show that our control strategy consistently outperforms several alternatives. Looking into the future, we believe our methodology provides a promising step towards the development of practical data-driven control strategies of epidemic processes.

Improving Throughput, Latency and Privacy with Hybrid Networks and Multipath Routing
S. C. Henri
2018.
[view at publisher]

Over the last few years, residential and enterprise networking have faced several challenges due to the increasing demand of users for high-throughput connectivity. As a result, efforts are being made to improve coverage, throughput, and robustness. Several solutions have been recently proposed. The first solution is to use mesh networking; it is gaining momentum, as it effectively improves performance, but at the cost of an increased complexity compared to the infrastructure mode, as several paths can now be employed with potentially several hops. The second solution is to exploit the different technologies that are available, wired (e.g., power-line communication (PLC) or Ethernet) and wireless (e.g., WiFi or cellular). Networks with various technologies are referred to as hybrid networks. When the technologies do not interfere with each other, it is possible to aggregate their capacity, thus enabling immediate throughput improvements; by increasing the number of possible paths that a packet can take, hybrid networks also increase complexity. The third solution is to use multipath routing, which can improve performance significantly. But again, this comes at the cost of an increased complexity. In this dissertation, we study the effect of these solutions in terms of throughput and coverage, latency, and privacy. We focus, in particular, on hybrid networks with shared-medium and orthogonal technologies, where two links that use the same technology are subject to interference (shared-medium), but not two links that use two distinct technologies (orthogonal). First, we study the effect of these solutions on throughput and coverage. We show that, in hybrid mesh networks, the optimal number of paths achieving maximal throughput with multipath routing is tightly linked with the number of technologies. This result makes it possible to develop an efficient and practical multipath routing protocol that yields the maximal throughput. Next, we introduce two novel algorithms for optimizing throughput: A distributed multipath congestion controller that, when each flow uses one multipath fixed in advance, provably achieves optimal throughput and an algorithm based on the multi-armed-bandit framework that finds the best multipath and converges to the best achievable throughput. We implement these algorithms in a real testbed with PLC and two orthogonal WiFi channels. Their experimental evaluation shows that using technologies with distinct physical layers, such as PLC and WiFi, improves spatial diversity compared to using multi-channel WiFi and brings further improvements of throughput and coverage. Then, we investigate latency in hybrid networks. We study analytically how the variance of a time-varying service rate affects queueing delays. We also study latency when multipath routing is used, i.e., when traffic is split between two technologies. We show that finding the optimal splitting scheme is difficult, as it depends on the rate at which packets arrive, and that the best static scheme, where the splitting probability remains the same for all arrival rates, can be significantly sub-optimal in time-varying networks. Finally, we study how hybrid networks and multipath can improve privacy. We show that they can significantly improve the resistance against traffic analysis attacks, such as website fingerprinting, by enabling the user to split the traffic between two networks.

Optimal Number of Paths with Multipath Routing in Hybrid Networks
S. Henri and P. Thiran
19th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), Chania, GREECE, Jun 12-15, 2018.
[view at publisher]

In recent years, multipath routing, i.e., employing several paths simultaneously, has emerged as an efficient way to provide significant throughput gains in local networks. This has been observed both with technologies that are not subject to interference, such as Ethernet, and with technologies that are, such as WiFi, power-line communications (PLC) and LTE. With technologies that are subject to interference, adding more paths is not always beneficial. We investigate the number of simultaneous paths necessary to reach maximal throughput when using multipath routing in multi-hop mesh networks with several self-interfering technologies. We show analytically, numerically and experimentally that the optimal number of paths M-opt is tightly linked with the number of technologies K. For certain classes of networks (in particular, for typical home networks), we prove analytically that M-opt = K, and our analytical findings are verified both with simulations and with experiments on a testbed composed of PLC and two orthogonal WiFi channels. In general networks, our numerical and experimental results show that the throughput loss caused by using at most K simultaneous paths is very small: The relative loss is smaller than 0.05 in 97% of the networks and smaller than 0.1 in 99% of the networks.

Profit Maximizing Logistic Regression Modeling for Credit Scoring
A. Devos, J. Dhondt, E. Stripling, B. Baesens, S. vanden Broucke and G. Sukhatme
IEEE Data Science Workshop (DSW), Lausanne, Switzerland, 2018.
[full text] [view at publisher]

On the Combinatorial Version of the Slepian-Wolf Problem
D. Chumbalov and A. Romashchenko
IEEE Transactions on Information Theory, vol. 64, no. 9, 6054 - 6069, 2018.
[view at publisher]

Load Balancing Video Clients in Enterprise Wireless Networks
A. Suresh, S. Mena, D. Tomozei, L. Granai, X. Zhu and S. Ferrari
IEEE Wireless Communications and Networking Conference (WCNC), Apr 15-18, 2018, Apr 15-18, 2018.
[view at publisher]

Given the increasing popularity of real-time video communication over enterprise wireless networks, ensuring good quality of experience is becoming critical. A common problem in such networks is that the clients typically adopt the strategy of associating to the access point with the highest signal strength, which can lead to load imbalance, unfair throughput allocation, and low overall video quality. In this paper, we propose to improve load balancing across video clients by selectively triggering directed roams of chosen clients, while explicitly accounting for the cost of roaming. We formulate the problem of identifying the directed roams to perform as an optimization problem where the objective function reflects both the overall utility of all video clients and the cost due to roaming. We subsequently apply relaxations to the original NP-Hard problem, and propose a three-stage algorithm that efficiently computes an approximate solution. Simulations show that by selectively roaming just 5% of the clients, we increase throughput relative to an initial strongest signal based association by at least 10% for over half of the clients and by at least 20% for over a quarter of the clients. We also increase aggregate throughput, improve fairness and thereby increase the overall video quality.

Multi-Armed Bandit in Action: Optimizing Performance in Dynamic Hybrid Networks
S. Henri, C. Vlachou and P. Thiran
IEEE/ACM Transactions on Networking, 1 - 14, 2018.
[view at publisher]

Today's home networks are often composed of several technologies such as Wi-Fi or power-line communication (PLC). Yet, current network protocols rarely fully harness this diversity and use each technology for a specific, pre-defined role, for example, wired media as a backbone and the wireless medium for mobility. Moreover, a single path is generally employed to transmit data; this path is established in advance and remains in use as long as it is valid, although multiple possible paths offer more robustness against varying environments. We introduce HyMAB, an algorithm that explores different multipaths and finds the best one in a mesh hybrid network, while keeping congestion under control. We employ the multi-armed-bandit framework and prove that HyMAB achieves optimal throughput under a static scenario. HyMAB design also accounts for real-network intricacies and dynamic conditions; it adapts to varying environments and switches multipaths when needed. We implement HyMAB on a PLC/Wi-Fi test bed. This is, to the best of our knowledge, the first implementation on a real test bed of multi-armed-bandit strategies in the context of routing. Our experimental results confirm the optimality of HyMAB and its ability to adapt to dynamic network conditions, as well as the gains provided by employing multi-armed-bandit strategies.

Can Who-Edits-What Predict Edit Survival?
A. B. Yardım, V. Kristof, L. Maystre and M. Grossglauser
24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, United Kingdom, August 19-23, 2018.
[code] [full text] [view at publisher]

As the number of contributors to online peer-production systems grows, it becomes increasingly important to predict whether the edits that users make will eventually be beneficial to the project. Existing solutions either rely on a user reputation system or consist of a highly specialized predictor that is tailored to a specific peer-production system. In this work, we explore a different point in the solution space that goes beyond user reputation but does not involve any content-based feature of the edits. We view each edit as a game between the editor and the component of the project. We posit that the probability that an edit is accepted is a function of the editor's skill, of the difficulty of editing the component and of a user-component interaction term. Our model is broadly applicable, as it only requires observing data about who makes an edit, what the edit affects and whether the edit survives or not. We apply our model on Wikipedia and the Linux kernel, two examples of large-scale peer-production systems, and we seek to understand whether it can effectively predict edit survival: in both cases, we provide a positive answer. Our approach significantly outperforms those based solely on user reputation and bridges the gap with specialized predictors that use content-based features. It is simple to implement, computationally inexpensive, and in addition it enables us to discover interesting structure in the data.

On the Delays in Time-Varying Networks: Does Larger Service-Rate Variance Imply Larger Delays?
S. Henri, S. Shneer and P. Thiran
Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Los Angeles, CA, USA, June 26 - 29, 2018.
[view at publisher]

In all networks, link or route capacities fluctuate for multiple reasons, e.g., fading and multi-path effects on wireless channels, interference and contending users on a shared medium, varying loads in WAN routers, impedance changes on power-line channels. These fluctuations severely impact packet delays. In this paper, we study delays in time-varying networks. Intuitively, we expect that for a given average service rate, an increased service rate variability yields larger delays. We find that this is not always the case. Using a queuing model that includes time-varying service rates, we show that for certain arrival rates, a queue with larger service rate variance offers smaller average delays than a queue with the same average service rate and lower service rate variance. We also verify these findings on a wireless testbed. We then study the conditions under which using simultaneously two independent paths helps in terms of delays, for example, in hybrid networks where the two paths use different physical layer technologies. We show that using two paths is not always better, in particular for low arrival rates. We also show that the optimal traffic splitting between the two paths depends on the arrival rate.

Optimal Number of Paths with Multipath Routing in Hybrid Networks
S. Henri and P. Thiran
2018.

In recent years, multipath routing, i.e., employing several paths simultaneously, has emerged as an efficient way to provide significant throughput gains in local networks. This has been observed both with technologies that are not subject to interference, such as Ethernet, and with technologies that are, such as WiFi, power-line communications (PLC) and LTE. With technologies that are subject to interference, adding more paths is not always beneficial. We investigate the number of simultaneous paths necessary to reach maximal throughput when using multipath routing in multi-hop mesh networks with several self-interfering technologies. We show analytically, numerically and experimentally that the optimal number of paths Mopt is tightly linked with the number of technologies K. For certain classes of networks (in particular, for typical home networks), we prove analytically that Mopt = K, and our analytical findings are verified both with simulations and with experiments on a testbed composed of PLC and two orthogonal WiFi channels. In general networks, our numerical and experimental results show that the throughput loss caused by using at most K simultaneous paths is very small: The relative loss is smaller than 0.05 in 97% of the networks and smaller than 0.1 in 99% of the networks.

Localizing the Source of an Epidemic Using Few Observations
B. Spinelli
2018.
[view at publisher]

Localizing the source of an epidemic is a crucial task in many contexts, including the detection of malicious users in social networks and the identification of patient zeros of disease outbreaks. The difficulty of this task lies in the strict limitations on the data available: In most cases, when an epidemic spreads, only few individuals, who we will call sensors, provide information about their state. Furthermore, as the spread of an epidemic usually depends on a large number of variables, accounting for all the possible spreading patterns that could explain the available data can easily result in prohibitive computational costs. Therefore, in the field of source localization, there are two central research directions: The design of practical and reliable algorithms for localizing the source despite the limited data, and the optimization of data collection, i.e., the identification of the most informative sensors. In this dissertation we contribute to both these directions. We consider network epidemics starting from an unknown source. The only information available is provided by a set of sensor nodes that reveal if and when they become infected. We study how many sensors are needed to guarantee the identification of the source. A set of sensors that guarantees the identification of the source is called a double resolving set (DRS); the minimum size of a DRS is called the double metric dimension (DMD). Computing the DMD is, in general, hard, hence estimating it with bounds is desirable. We focus on G(N,p) random networks for which we derive tight bounds for the DMD. We show that the DMD is a non-monotonic function of the parameter p, hence there are critical parameter ranges in which source localization is particularly difficult. Again building on the relationship between source localization and DRSs, we move to optimizing the choice of a fixed number K of sensors. First, we look at the case of trees where the uniqueness of paths makes the problem simpler. For this case, we design polynomial time algorithms for selecting K sensors that optimize certain metrics of interest. Next, turning to general networks, we show that the optimal sensor set depends on the distribution of the time it takes for an infected node u to infect a non-infected neighbor v, which we call the transmission delay from u to v. We consider both a low- and a high-variance regime for the transmission delays. We design algorithms for sensor placement in both cases, and we show that they yield an improvement of up to 50% over state-of-the-art methods. Finally, we propose a framework for source localization where some sensors (called dynamic sensors) can be added while the epidemic spreads and the localization progresses. We design an algorithm for joint source localization and dynamic sensor placement; This algorithm can handle two regimes: offline localization, where we localize the source after the epidemic spread, and online localization, where we localize the source while the epidemic is ongoing. We conduct an empirical study of offline and online localization and show that, by using dynamic sensors, the number of sensors we need to localize the source is up to 10 times less with respect to a strategy where all sensors are deployed a priori. We also study the resistance of our methods to high-variance transmission delays and show that, even in this setting, using dynamic sensors, the source can be localized with less than 5% of the nodes being sensors.

2017

Csma/ca in time and frequency domains
J. Herzen, P. Thiran, A. Banchs and V. Shneer
2017.

The present invention concerns a method for a communication device to transmit a data packet in a wireless communication system. The method comprises: determining (21) a first set of transmission parameters comprising a first central transmission frequency and a first spectral bandwidth; transmitting (33) a first data packet by applying the first set of transmission parameters; determining (35) whether or not the first data packet collided with a second data packet from a second communication device; determining (37) a second set of transmission parameters, which in case of collision comprises a second central transmission frequency, different from the first central transmission frequency, and a second spectral bandwidth, which is different from the first spectral bandwidth with a first, non-zero probability and the same as the first spectral bandwidth with a second probability; and transmitting (33) a second data packet by applying the second set of transmission parameters.

Multiphase digitally controlled oscillator for future 5G phased arrays in 90 nm CMOS
A. Devos, M. Vigilante and P. Reynaert
IEEE Nordic Circuits and Systems Conference (NORCAS), Copenhagen, Denmark, 2017.
[full text] [view at publisher]

The effect of transmission variance on observer placement for source-localization
B. Spinelli, E. Celis and P. Thiran
Applied Network Science, vol. 2, 20, 2017.
[full text] [view at publisher]

ChoiceRank: Identifying Preferences from Node Traffic in Networks
L. Maystre and M. Grossglauser
International Conference on Machine Learning, Sydney, Australia, August 6-11, 2017.
[code] [full text]

Understanding how users navigate in a network is of high interest in many applications. We consider a setting where only aggregate node-level traffic is observed and tackle the task of learning edge transition probabilities. We cast it as a preference learning problem, and we study a model where choices follow Luce's axiom. In this case, the O(n) marginal counts of node visits are a sufficient statistic for the O(n^2) transition probabilities. We show how to make the inference problem well-posed regardless of the network's structure, and we present ChoiceRank, an iterative algorithm that scales to networks that contains billions of nodes and edges. We apply the model to two clickstream datasets and show that it successfully recovers the transition probabilities using only the network structure and marginal (node-level) traffic data. Finally, we also consider an application to mobility networks and apply the model to one year of rides on New York City's bicycle-sharing system.

Just Sort It! A Simple and Effective Approach to Active Preference Learning
L. Maystre and M. Grossglauser
International Conference on Machine Learning, Sydney, Australia, August 6-11, 2017.
[full text]

We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.

Applications of Approximate Learning and Inference for Probabilistic Models
Y. J. Ko
2017.
[view at publisher]

We develop approximate inference and learning methods for facilitating the use of probabilistic modeling techniques motivated by applications in two different areas. First, we consider the ill-posed inverse problem of recovering an image from an underdetermined system of linear measurements corrupted by noise. Second, we consider the problem of inferring user preferences for items from counts, pairwise comparisons and user activity logs, instances of implicit feedback. Plausible models for images and the noise, incurred when recording them, render posterior inference intractable, while the scale of the inference problem makes sampling based approximations ineffective. Therefore, we develop deterministic approximate inference algorithms for two different augmentations of a typical sparse linear model: first, for the rectified-linear Poisson likelihood, and second, for tree-structured super-Gaussian mixture models. The rectified-linear Poisson likelihood is an alternative noise model, applicable in astronomical and biomedical imaging applications, that operate in intensity regimes in which quantum effects lead to observations that are best described by counts of particles arriving at a sensor, as well as in general Poisson regression problems arising in various fields. In this context we show, that the model-specific computations for Expectation Propagation can be robustly solved by a simple dynamic program. Next, we develop a scalable approximate inference algorithm for structured mixture models, that uses a discrete graphical model to represent dependencies between the latent mixture components of a collection of mixture models. Specifically, we use tree-structured mixtures of super-Gaussians to model the persistence across scales of large coefficients of the Wavelet transform of an image for improved reconstruction. In the second part on models of user preference, we consider two settings: the global static and the contextual dynamic setting. In the global static setting, we represent user-item preferences by a latent low-rank matrix. Instead of using numeric ratings we develop methods to infer this latent representation for two types of implicit feedback: aggregate counts of users interacting with a service and the binary outcomes of pairwise comparisons. We model count data using a latent Gaussian bilinear model with Poisson likelihoods. For this model, we show that the Variational Gaussian approximation can be further relaxed to be available in closed-form by adding additional constraints, leading to an efficient inference algorithm. In the second implicit feedback scenario, we infer the latent preference matrix from pairwise preference statements. We combine a low-rank bilinear model with non-parameteric item- feature regression and develop a novel approximate variational Expectation Maximization algorithm that mitigates the computational challenges due to latent couplings induced by the pairwise comparisons. Finally, in the contextual dynamic setting, we model sequences of user activity at the granularity of single interaction events instead of aggregate counts. Routinely gathered in the background at a large scale in many applications, such sequences can reveal temporal and contextual aspects of user behavior through recurrent patterns. To describe such data, we propose a generic collaborative sequence model based on recurrent neural networks, that combines ideas from collaborative filtering and language modeling.

Back to the Source: an Online Approach for Sensor Placement and Source Localization
B. Spinelli, L. E. Celis and P. Thiran
26th International World Wide Web Conference (WWW), 2017.
[full text] [view at publisher]

Source localization, the act of finding the originator of a disease or rumor in a network, has become an important problem in sociology and epidemiology. The localization is done using the infection state and time of infection of a few designated sensor nodes; however, maintaining sensors can be very costly in practice. We propose the first online approach to source localization: We deploy a priori only a small number of sensors (which reveal if they are reached by an infection) and then iteratively choose the best location to place new sensors in order to localize the source. This approach allows for source localization with a very small number of sensors; moreover, the source can be found while the epidemic is still ongoing. Our method applies to a general network topology and performs well even with random transmission delays.

Alignment and Assembly : Inferring Networks from Noisy Observations
L. Yartseva
2017.
[view at publisher]

Over recent years, many large network datasets become available, giving rise to novel and valuable applications of data mining and machine learning techniques. These datasets include social networks, the structure of the Internet, and protein-interaction networks, to name just a few. Graph mining exploits information hidden in these data to shed light on such problems as finding relevant pages on the web, or identifying communities of strongly connected individuals. Clearly, to address such problems, we first need the complete and reliable network graph. In many real-world scenarios, the full graph is not available for free. For example, data-collection processes may be noisy and unreliable or node identifiers may be hidden for privacy protection. Therefore, we cannot rely on the node labels to infer the full graph. In this thesis, we address fundamental and practical questions of inferring a true full network from multiple ambiguous observations. We formulate two variations of this problem: network alignment and network assembly. In each variant, we address two types of questions: first, we characterize how graph features impact the fundamental feasibility of reconstruction; second, we seek efficient algorithms that can scale to very large networks. In the first part of this thesis, we consider network alignment. We assume two large, noisy observations of the true network that are not labeled. Network alignment refers to the problem of aligning the vertices of the two networks using only structural cues and it can be viewed as a generalization of the classic graph-isomorphism problem. We make the following contributions. First, we introduce a random bigraph model with parameters p, t and s that generates two correlated graphs. We characterize conditions on p, t and s for the feasibility of alignment of two graphs. Second, we create an algorithm named percolation graph-matching (PGM) that builds an alignment from a small set of pre-matched nodes S. We prove conditions on the parameters p, t , s and r for which PGM succeeds, and we establish a phase transition in |S|. In the second part of this thesis, we consider network assembly. We assume many small, noisy observations of the true network, called patches. The node labels are either absent or not unique. The network assembly problem consists in reconstructing the true graph from these patches. We make the following contributions. First, we introduce a novel random-graph model with parameters p and q that generates a network with high clustering. We characterize conditions on p and q for feasibility of assembly. Second, we propose a heuristic assembly algorithm to reconstruct the true graph from arbitrary patches with label ambiguity.

How CSMA/CA With Deferral Affects Performance and Dynamics in Power-Line Communications
C. Vlachou, A. Banchs, J. Herzen and P. Thiran
Ieee-Acm Transactions On Networking, vol. 25, no. 1, 250 - 263, 2017.
[view at publisher]

Power-line communications (PLC) are becoming a key component in home networking, because they provide easy and high-throughput connectivity. The dominant MAC protocol for high data-rate PLC, the IEEE 1901, employs a CSMA/CA mechanism similar to the backoff process of 802.11. Existing performance evaluation studies of this protocol assume that the backoff processes of the stations are independent (the so-called decoupling assumption). However, in contrast to 802.11, 1901 stations can change their state after sensing the medium busy, which is regulated by the so-called deferral counter. This mechanism introduces strong coupling between the stations and, as a result, makes existing analyses inaccurate. In this paper, we propose a performance model for 1901, which does not rely on the decoupling assumption. We prove that our model admits a unique solution for a wide range of configurations and confirm the accuracy of the model using simulations. Our results show that we outperform current models based on the decoupling assumption. In addition to evaluating the performance in steady state, we further study the transient dynamics of 1901, which is also affected by the deferral counter.

2016

Just One More: Modeling Binge Watching Behavior
W. Trouleau, A. Ashkan, W. Ding and B. Eriksson
22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, California, USA, August 13-17, 2016.
[full text] [view at publisher]

Easy accessibility can often lead to over-consumption, as seen in food and alcohol habits. On video on-demand (VOD) services, this has recently been referred to as binge watching, where potentially entire seasons of TV shows are consumed in a single viewing session. While a user viewership model may reveal this binging behavior, creating an accurate model has several challenges, including censored data, deviations in the population, and the need to consider external influences on consumption habits. In this paper, we introduce a novel statistical mixture model that incorporates these factors and presents a first of its kind characterization of viewer consumption behavior using a real-world dataset that includes playback data from a VOD service. From our modeling, we tackle various predictive tasks to infer the consumption decisions of a user in a viewing session, including estimating the number of episodes they watch and classifying if they continue watching another episode. Using these insights, we then identify binge watching sessions based on deviation from normal viewing behavior. We observe different types of binging behavior, that binge watchers often view certain content out-of-order, and that binge watching is not a consistent behavior among our users. These insights and our findings have application in VOD revenue generation, consumer health applications, and customer retention analysis.

Assignment Techniques for Crowdsourcing Sensitive Tasks
L. E. Celis, S. P. Reddy, I. P. Singh and S. Vaya
19th ACM Conference on Computer-Supported Cooperative Work and Social Computing (CSCW), San Francisco, CA, FEB 27-MAR 02, 2016.
[view at publisher]

Protecting the privacy of crowd workers has been an important topic in crowdsourcing, however, task privacy has largely been ignored despite the fact that many tasks, e.g., form digitization, live audio transcription or image tagging often contain sensitive information. Although assigning an entire job to a worker may leak private information, jobs can often be split into small components that individually do not. We study the problem of distributing such tasks to workers with the goal of maximizing task privacy using such an approach. We introduce information loss functions to formally measure the amount of private information leaked as a function of the task assignment. We then design assignment mechanisms for three different assignment settings: PUSH, PULL and a new setting Tug Of War (TOW), which is an intermediate approach that balances flexibility for both workers and requesters. Our assignment algorithms have zero privacy loss for PUSH, and tight theoretical guarantees for PULL. For TOW, our assignment algorithm provably outperforms PULL; importantly the privacy loss is independent of the number of tasks, even when workers collude. We further analyze the performance and privacy tradeoffs empirically on simulated and real-world collusion networks and find that our algorithms outperform the theoretical guarantees.

Online Collaborative Prediction of Regional Vote Results
V. Etter, M. E. Khan, M. Grossglauser and P. Thiran
2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA), Montreal, QC, Canada, 17-19 October 2016.
[full text] [view at publisher]

We consider online predictions of vote results, where regions across a country vote on an issue under discussion. Such online predictions before and during the day of the vote are useful to media agencies, polling institutes, and political parties, e.g., to identify regions that are crucial in determining the national outcome of a vote. We analyze a unique dataset from Switzerland. The dataset contains 281 votes from 2352 regions over a period of 34 years. We make several contributions towards improving online predictions. First, we show that these votes exhibit a bi-clustering of the vote results, i.e., regions that are spatially close tend to vote similarly, and issues that discuss similar topics show similar global voting patterns. Second, we develop models that can exploit this bi-clustering, as well as the features associated with the votes and regions. Third, we show that, when combining vote results and features together, Bayesian methods are essential to obtaining good performance. Our results show that Bayesian methods give better estimates of the hyperparameters than non-Bayesian methods such as cross-validation. The resulting models generalize well to many different tasks, produce robust predictions, and are easily interpretable.

Uncovering Latent Behaviors in Ant Colonies
M. Kafsi, R. Braunschweig, D. Mersch, M. Grossglauser, L. Keller and P. Thiran
2016 SIAM International Conference on Data Mining, Miami, Florida, USA, May 5-7, 2016.
[full text] [view at publisher]

Many biological systems exhibit collective behaviors that strengthen their adaptability to their environment, compared to more solitary species. Describing these behaviors is challenging yet necessary in order to understand these biological systems. We propose a probabilistic model that enables us to uncover the collective behaviors observed in a colony of ants. This model is based on the assumption that the behavior of an individual ant is a time-dependent mixture of latent behaviors that are specific to the whole colony. We apply this model to a large-scale dataset obtained by observing the mobility of nearly 1000 Camponotus fellah ants from six different colonies. Our results indicate that a colony typically exhibits three classes of behaviors, each characterized by a specific spatial distribution and a level of activity. Moreover, these spatial distributions, which are uncovered automatically by our model, match well with the ground truth as manually annotated by domain experts. We further explore the evolution of the behavior of individual ants and show that it is well captured by a second order Markov chain that encodes the fact that the future behavior of an ant depends not only on its current behavior but also on its preceding one.

PROPER: global protein interaction network alignment through percolation matching
E. Kazemi, H. Hassani, M. Grossglauser and H. P. Modarres
BMC Bioinformatics, vol. 17, 527, 2016.
[full text] [view at publisher]

Background The alignment of protein-protein interaction (PPI) networks enables us to uncover the relationships between different species, which leads to a deeper understanding of biological systems. Network alignment can be used to transfer biological knowledge between species. Although different PI-network alignment algorithms were introduced during the last decade, developing an accurate and scalable algorithm that can find alignments with high biological and structural similarities among PPI networks is still challenging. Results In this paper, we introduce a new global network alignment algorithm for PPI networks called PROPER. Compared to other global network alignment methods, our algorithm shows higher accuracy and speed over real PPI datasets and synthetic networks. We show that the PROPER algorithm can detect large portions of conserved biological pathways between species. Also, using a simple parsimonious evolutionary model, we explain why PROPER performs well based on several different comparison criteria. Conclusions We highlight that PROPER has high potential in further applications such as detecting biological pathways, finding protein complexes and PPI prediction. The PROPER algorithm is available at http://proper.epfl.ch.

EMPoWER Hybrid Networks: Exploiting Multiple Paths over Wireless and ElectRical Mediums
S. Henri, C. Vlachou, J. Herzen and P. Thiran
ACM Conference on emerging Networking EXperiments and Technologies (CoNEXT) 2016, Irvine, California, USA, December 12-15, 2016.
[view at publisher]

Several technologies, such as WiFi, Ethernet and power-line communications (PLC), can be used to build residential and enterprise networks. These technologies often co-exist; most networks use WiFi, and buildings are readily equipped with electrical wires that can offer a capacity up to 1 Gbps with PLC. Yet, current networks do not exploit this rich diversity and often operate far below the available capacity. We design, implement, and evaluate EMPoWER, a system that exploits simultaneously several potentially-interfering mediums. It operates at layer 2.5, between the MAC and IP layers, and combines routing (to find multiple concurrent routes) and congestion control (to efficiently balance traffic across the routes). To optimize resource utilization and robustness, both components exploit the heterogeneous nature of the network. They are fair and efficient, and they operate only within the local area network, without affecting remote Internet hosts. We demonstrate the performance gains of EMPoWER, by simulations and experiments on a 22-node testbed. We show that PLC/WiFi, benefiting from the diversity offered by wireless and electrical mediums, provides significant throughput gains (up to 10x) and improves coverage, compared to multi-channel WiFi.

Network Alignment: Theory, Algorithms, and Applications
E. Kazemi
2016.
[view at publisher]

Networks are central in the modeling and analysis of many large-scale human and technical systems, and they have applications in diverse fields such as computer science, biology, social sciences, and economics. Recently, network mining has been an active area of research. In this thesis, we study several related network-mining problems, from three different perspectives: the modeling and theory perspective, the computational perspective, and the application perspective. In the bulk of this thesis, we focus on network alignment, where the data provides two (or more) partial views of the network, and where the node labels are sometimes ambiguous. Network alignment has applications in social-network reconciliation and de-anonymization, protein-network alignment in biology, and computer vision. In the first part of this thesis, we investigate the feasibility of network alignment with a random-graph model. This random-graph model generates two (or several) correlated networks, and lets the two networks to overlap only partially. For a particular alignment, we define a cost function for structural mismatch. We show that the minimization of the proposed cost function (assuming that we have access to infinite computational power), with high probability, results in an alignment that recovers the set of shared nodes between the two networks, and that also recovers the true matching between the shared nodes. The most scalable network-alignment approaches use ideas from percolation theory, where a matched node-couple infects its neighboring couples that are additional potential matches. In the second part of this thesis, we propose a new percolation-based network-alignment algorithm that can match large networks by using only the network structure and a handful of initially pre-matched node-couples called seed set. We characterize a phase transition in matching performance as a function of the seed-set size. In the third part of this thesis, we consider two important application areas of network mining in biology and public health. The first application area is percolation-based network alignment of protein-protein interaction (PPI) networks in biology. The alignment of biological networks has many uses, such as the detection of conserved biological network motifs, the prediction of protein interactions, and the reconstruction of phylogenetic trees. Network alignment can be used to transfer biological knowledge between species. We introduce a new global pairwise-network alignment algorithm for PPI networks, called PROPER. The PROPER algorithm shows higher accuracy and speed compared to other global network-alignment methods. We also extend PROPER to the global multiple-network alignment problem. We introduce a new algorithm, called MPROPER, for matching multiple networks. Finally, we explore IsoRank, one of the first and most referenced global pairwise-network alignment algorithms. Our second application area is the control of epidemic processes. We develop and model strategies for mitigating an epidemic in a large-scale dynamic contact network. More precisely, we study epidemics of infectious diseases by (i) modeling the spread of epidemics on a network by using many pieces of information about the mobility and behavior of a population; and by (ii) designing personalized behavioral recommendations for individuals, in order to mitigate the effect of epidemics on that network.

Collaborative Recurrent Neural Networks for Dynamic Recommender Systems
Y. J. Ko, L. Maystre and M. Grossglauser
The 8th Asian Conference on Machine Learning, Hamilton, New Zealand, November 16-18, 2016.
[full text]

Modern technologies enable us to record sequences of online user activity at an unprecedented scale. Although such activity logs are abundantly available, most approaches to recommender systems are based on the rating-prediction paradigm, ignoring temporal and contextual aspects of user behavior revealed by temporal, recurrent patterns. In contrast to explicit ratings, such activity logs can be collected in a non-intrusive way and can offer richer insights into the dynamics of user preferences, which could potentially lead more accurate user models. In this work we advocate studying this ubiquitous form of data and, by combining ideas from latent factor models for collaborative filtering and language modeling, propose a novel, flexible and expressive collaborative sequence model based on recurrent neural networks. The model is designed to capture a user’s contextual state as a personalized hidden vector by summarizing cues from a data-driven, thus variable, number of past time steps, and represents items by a real-valued embedding. We found that, by exploiting the inherent structure in the data, our formulation leads to an efficient and practical method. Furthermore, we demonstrate the versatility of our model by applying it to two different tasks: music recommendation and mobility prediction, and we show empirically that our model consistently outperforms static and non-collaborative methods.

Analysis and Enhancement of CSMA/CA With Deferral in Power-Line Communications
C. Vlachou, A. Banchs, P. Salvador, J. Herzen and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. 34, no. 7, 1978 - 1991, 2016.
[view at publisher]

Power-line communications are employed in home networking to provide easy and high-throughput connectivity. The IEEE 1901, the MAC protocol for power-line networks, employs a CSMA/CA protocol similar to that of 802.11, but is substantially more complex, which probably explains why little is known about its performance. One of the key differences between the two protocols is that whereas 802.11 only reacts upon collisions, 1901 also reacts upon several consecutive transmissions and thus can potentially achieve better performance by avoiding unnecessary collisions. In this paper, we propose a model for the 1901 MAC. Our analysis reveals that the default configuration of 1901 does not fully exploit its potential and that its performance degrades with the number of stations. Based on analytical reasoning, we derive a configuration for the parameters of 1901 that drastically improves throughput and achieves optimal performance without requiring the knowledge of the number of stations in the network. In contrast, 802.11 requires knowing the number of contending stations to provide a similar performance, which is unfeasible for realistic traffic patterns. We confirm our results and enhancement with testbed measurements, by implementing the 1901 MAC protocol on WiFi hardware.

Assembling a Network out of Ambiguous Patches
L. Yartseva, J. S. Elbert and M. Grossglauser
Allerton, Allerton Park and Retreat Center, Monticello, IL, USA, 2016.
[view at publisher]

Many graph mining and network analysis problems rely on the availability of the full network over a set of nodes. But inferring a full network is sometimes non-trivial if the raw data is in the form of many small {\em patches} or subgraphs, of the true network, and if there are ambiguities in the identities of nodes or edges in these patches. This may happen because of noise or because of the nature of data; for instance, in social networks, names are typically not unique. \textit{Graph assembly} refers to the problem of reconstructing a graph from these many, possibly noisy, partial observations. Prior work suggests that graph assembly is essentially impossible in regimes of interest when the true graph is Erdos-Renyi. The purpose of the present paper is to show that a modest amount of clustering is sufficient to assemble even very large graphs. We introduce the $G(n,p;q)$ random graph model, which is the random closure over all open triangles of a $G(n,p)$ Erdos-Renyi, and show that this model exhibits higher clustering than an equivalent Erdos-Renyi. We focus on an extreme case of graph assembly: the patches are small ($1$-hop egonets) and are unlabeled. We show that in realistic regimes, graph assembly is fundamentally feasible, because we can identify, for every edge $e$, a subgraph induced by its neighbors that is unique and present in every patch containing $e$. Using this result, we build a practical algorithm that uses canonical labeling to reconstruct the original graph from noiseless patches. We also provide an achievability result for noisy patches, which are obtained by edge-sampling the original egonets.

The Player Kernel: Learning Team Strengths Based on Implicit Player Contributions
L. Maystre, V. Kristof, A. J. González Ferrer and M. Grossglauser
Machine Learning and Data Mining for Sports Analytics 2016, Riva del Garda, Italy, September 19, 2016.
[full text]

In this work, we draw attention to a connection between skill-based models of game outcomes and Gaussian process classification models. The Gaussian process perspective enables a) a principled way of dealing with uncertainty and b) rich models, specified through kernel functions. Using this connection, we tackle the problem of predicting outcomes of football matches between national teams. We develop a player kernel that relates any two football matches through the players lined up on the field. This makes it possible to share knowledge gained from observing matches between clubs (available in large quantities) and matches between national teams (available only in limited quantities). We evaluate our approach on the Euro 2008, 2012 and 2016 final tournaments.

Observer Placement for Source Localization: the Effect of Budgets and Transmission Variance
B. Spinelli, L. E. Celis and P. Thiran
54th Annual Allerton Conference on Communication, Control, and Computing, 2016.
[full text] [view at publisher]

When an epidemic spreads in a network, a key question is where was its source, i.e., the node that started the epidemic. If we know the time at which various nodes were infected, we can attempt to use this information in order to identify the source. However, maintaining observer nodes that can provide their infection time may be costly, and we may have a budget k on the number of observer nodes we can maintain. Moreover, some nodes are more informative than others due to their location in the network. Hence, a pertinent question arises: Which nodes should we select as observers in order to maximize the probability that we can accurately identify the source? Inspired by the simple setting in which the node-to-node delays in the transmission of the epidemic are deterministic, we develop a principled approach for addressing the problem even when transmission delays are random. We show that the optimal observer-placement differs depending on the variance of the transmission delays and propose approaches in both low- and high-variance settings. We validate our methods by comparing them against state-of-the-art observer-placements and show that, in both settings, our approach identifies the source with higher accuracy.

Measuring, Modeling and Enhancing Power-Line Communications
C. Vlachou
2016.
[view at publisher]

Power-line communication (PLC) is a technology that has become very popular, as it offers easy and high-throughput connectivity in local networks. Although it is widely adopted in hybrid PLC/WiFi networks and commercially successful, PLC has received little attention from the research community. In this thesis, we build the foundations for evaluating, exploiting and boosting PLC performance. When deploying hybrid networks, there are open questions that arise: Does PLC perform better than WiFi? How can we accurately estimate PLC capacity for deciding to which medium data should be forwarded? To answer these questions, we conduct an experimental study with PLC and WiFi stations and delve into the spatio-temporal variations of capacity. We uncover crucial differences between the two mediums and prove that PLC largely extends coverage and augments network reliability. We discover that PLC links are highly asymmetric and that temporal variation occurs on three time-scales. There is a high correlation between link quality and its variability, which has a direct impact on probing overhead and on accurate link-metric estimations. We propose guidelines for link-metric estimation. The subsequent open questions are related to efficiency when stations contend for the medium. We investigate the PLC CSMA/CA protocol that bears a resemblance to that of WiFi, in the sense that it uses a binary exponential backoff. WiFi stations double the contention window only after experiencing a collision. In contrast, PLC enables the stations to also double their contention window before a collision. PLC introduces a new variable, called deferral counter, that regulates the frequency of this proactive reaction based on congestion in the network. We introduce a model for evaluating performance. The model relies on the decoupling assumption that asserts that the backoff processes of the stations are independent and has been widely used for modeling WiFi. Our model boils down to a single fixed-point equation of the collision probability. We prove the uniqueness of the solution and exploit the model to devise configurations that significantly boost performance for best-effort applications. We corroborate our model and performance gains via extensive simulation and measurements on WiFi and PLC hardware. After delving into the average performance of PLC CSMA/CA, we explore the short-term dynamics. We find analytically, experimentally and in simulation that, contrary to WiFi, PLC is short-term unfair. This yields high delay-variance (jitter) and affects delay-sensitive applications. The deferral counter introduces unfairness and determines a tradeoff between throughput and fairness, which we extensively study. We reveal that this unfairness leads to strong dependence between stations, which can penalize the accuracy of models relying on the decoupling assumption. To improve the modeling accuracy of PLC CSMA/CA, we propose another model that does not resort to the decoupling assumption and takes into account the short-term dynamics. The resulting model is more complex compared to the first one, but it performs better for small number of stations. Here too, we prove that the model admits a unique solution. This is the first model of the PLC CSMA/CA that reaches this level of accuracy. By using this model and our research on fairness, we propose an algorithm that yields configurations with low jitter, given throughput constraints and a set of possible configurations.

Where You Are is Who You Are: User Identification by Matching Statistics
F. Movahedi Naini, J. Unnikrishnan, P. Thiran and M. Vetterli
IEEE Transactions on Information Forensics and Security, vol. 11, no. 2, 358 - 372, 2016.
[full text] [view at publisher]

Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be used to identify and track users by using only the observed patterns in the behavior. We study the task of identifying users from statistics of their behavioral patterns. Specifically, we focus on the setting in which we are given histograms of users’ data collected in two different experiments. In the first dataset, we assume that the users’ identities are anonymized or hidden and in the second dataset we assume that their identities are known. We study the task of identifying the users in the first dataset by matching the histograms of their data with the histograms from the second dataset. In a recent work [1], [2] the optimal algorithm for this user identification task was introduced. In this paper, we evaluate the effectiveness of this method on a wide range of datasets with up to 50, 000 users, and in a wide range of scenarios. Using datasets such as call data records, web browsing histories, and GPS trajectories, we demonstrate that a large fraction of users can be easily identified given only histograms of their data, and hence these histograms can act as users’ fingerprints. We also show that simultaneous identification of users achieves better performance compared to one-by-one user identification. Furthermore, we show that using the optimal method for identification does indeed give higher identification accuracies than heuristics-based approaches in such practical scenarios. The accuracies obtained under this optimal method can thus be used to quantify the maximum level of user identification that is possible in such settings. We show that the key factors affecting the accuracy of the optimal identification algorithm are the duration of the data collection, the number of users in the anonymized dataset, and the resolution of the dataset. We also analyze the effectiveness of k-anonymization in resisting user identification attacks on these datasets.

2015

Traveling Salesman in Reverse: Conditional Markov Entropy for Trajectory Segmentation
M. Kafsi, M. Grossglauser and P. Thiran
2015 IEEE International Conference on Data Mining, Atlantic City, NJ, USA, November 14-17, 2015.
[full text] [view at publisher]

We are interested in inferring the set of waypoints (or intermediate destinations) of a mobility trajectory in the absence of timing information. We find that, by mining a dataset of real mobility traces, computing the entropy of conditional Markov trajectory enables us to uncover waypoints, even though no timing information nor absolute geographic location is provided. We build on this observation and design an efficient algorithm for trajectory segmentation. Our empirical evaluation demonstrates that the entropy-based heuristic used by our segmentation algorithm outperforms alternative approaches as it is 43% more accurate than a geometric approach and 20% more accurate than path-stretch based approach. We further explore the link between trajectory entropy, mobility predictability and the nature of intermediate locations using a route choice model on real city maps.

Budgeted sensor placement for source localization on trees
L. E. Celis, F. Pavetic, B. Spinelli and P. Thiran
Latin-American Algorithms, Graphs and Optimization Symposium, 2015.
[full text] [view at publisher]

We address the problem of choosing a fixed number of sensor vertices in a graph in order to detect the source of a partially-observed diffusion process on the graph itself. Building on the definition of double resolvability we introduce a notion of vertex resolvability. For the case of tree graphs we give polynomial time algorithms for both finding the sensors that maximize the probability of correct detection of the source and for identifying the sensor set that minimizes the expected distance between the real source and the estimated one.

Kullback-Leibler Proximal Variational Inference
M. E. Khan, P. B. Baqué, F. Fleuret and P. Fua
Advances in Neural Information Processing Systems (NIPS), Montreal, Canada, December 9, 2015.

We propose a new variational inference method based on a proximal framework that uses the Kullback-Leibler (KL) divergence as the proximal term. We make two contributions towards exploiting the geometry and structure of the variational bound. Firstly, we propose a KL proximal-point algorithm and show its equivalence to variational inference with natural gradients (e.g. stochastic variational inference). Secondly, we use the proximal framework to derive efficient variational algorithms for non-conjugate models. We propose a splitting procedure to separate non-conjugate terms from conjugate ones. We linearize the non-conjugate terms to obtain subproblems that admit a closed-form solution. Overall, our approach converts inference in a non-conjugate model to subproblems that involve inference in well-known conjugate models. We show that our method is applicable to a wide variety of models and can result in computationally efficient algorithms. Applications to real-world datasets show comparable performance to existing methods.

UAVs using Bayesian Optimization to LocateWiFi Devices
M. Carpin, S. Rosati, B. Rimoldi and M. E. Khan
Bayesopt 2015, Montreal, Canada, December 12, 2015.

We address the problem of localizing non-collaborative WiFi devices in a large region. Our main motive is to localize humans by localizing their WiFi devices, e.g. during search-and-rescue operations after a natural disaster. We use an active sensing approach that relies on Unmanned Aerial Vehicles (UAVs) to collect signal-strength measurements at informative locations. The problem is challenging since the measurement is received at arbitrary times and they are received only when the UAV is in close proximity to the device. For these reasons, it is extremely important to make prudent decision with very few measurements. We use the Bayesian optimization approach based on Gaussian process (GP) regression. This approach works well for our application since GPs give reliable predictions with very few measurements while Bayesian optimization makes a judicious trade-off between exploration and exploitation. In field experiments conducted over a region of 1000 × 1000 m2, we show that our approach reduces the search area to less than 100 meters around the WiFi device within 5 minutes only. Overall, our approach localizes the device in less than 15 minutes with an error of less than 20 meters.

Combine and Conquer : Mining Social Systems for Prediction
V. Etter
2015.
[view at publisher]

In this thesis, we explore the application of data mining and machine learning techniques to several practical problems. These problems have roots in various fields such as social science, economics, and political science. We show that computer science techniques enable us to bring significant contributions to solving them. Moreover, we show that combining several models or datasets related to the problem we are trying to solve is key to the quality of the solution we find. The first application we consider is human mobility prediction. We describe our winning contribution to the Nokia Mobile Data Challenge, in which we predict the next location a user will visit based on his history and the current context. We first highlight some data characteristics that contribute to the difficulty of the task, such as sparsity and non-stationarity. Then, we present three families of models and observe that, even though their average accuracies are similar, their performances vary significantly across users. To take advantage of this diversity, we introduce several strategies to combine models, and show that the combinations outperform any individual predictor. The second application we examine is predicting the success of crowdfunding campaigns. We collected data on Kickstarter (one of the most popular crowdfunding platforms) in order to predict whether a campaign will reach its funding goal or not. We show that we obtain good performances by simply using information about money, but that combining this information with social features extracted from Kickstarter's social graph and Twitter improves early predictions. In particular, predictions made a few hours after the beginning of a campaign are improved by 4%, to reach an accuracy of 76%. Then, we move to the realms of politics, and first investigate the ideologies of politicians. Using their opinion on several aspects of politics, gathered on a voting advice application (VAA), we show that the themes that divide politicians the most are the ones that we usually associate with left-wing/right-wing and liberal/conservative, thus validating the simplified two-dimensional view of the political system that many people use. We bring attention to the potentially malicious uses of VAAs by creating a fake candidate profile that is able to gather twice as many voting recommendations as any other. To counter this, we demonstrate that we are able to monitor politicians after they were elected, and potentially detect changes of opinion, by combining the data extracted from the VAA with the votes that they cast at the Parliament. Finally, we study the outcome of issue votes. We first show that simply considering vote results at a fine geographical level is sufficient to highlight characteristic geographical voting patterns across a country, and their evolution over time. It also enables us to find representative regions that are crucial in determining the national outcome of a vote. We then demonstrate that predicting the actual result of a vote in all regions (in opposition to the binary national outcome) is a much harder task that requires combining data about regions and votes themselves to obtain good performances. We compare the use of Bayesian and non-Bayesian models that combine matrix-factorization and regression. We show that, here too, combining appropriate models and datasets improves the quality of the predictions, and that Bayesian methods give better estimates of the model's hyperparameters.

Expectation Propagation for Rectified Linear Poisson Regression
Y. J. Ko and M. Seeger
7th Asian Conference on Machine Learning (ACML), Hong Kong, November 20-22, 2015.

The Poisson likelihood with rectified linear function as non-linearity is a physically plausible model to discribe the stochastic arrival process of photons or other particles at a detector. At low emission rates the discrete nature of this process leads to measurement noise that behaves very differently from additive white Gaussian noise. To address the intractable inference problem for such models, we present a novel efficient and robust Expectation Propagation algorithm entirely based on analytically tractable computations operating re- liably in regimes where quadrature based implementations can fail. Full posterior inference therefore becomes an attractive alternative in areas generally dominated by methods of point estimation. Moreover, we discuss the rectified linear function in the context of other common non-linearities and identify situations where it can serve as a robust alternative.

Hierarchical Routing Over Dynamic Wireless Networks
D. Tschopp, S. Diggavi and M. Grossglauser
Random Structures & Algorithms, vol. 47, no. 4, 669 - 709, 2015.
[view at publisher]

The topology of a mobile wireless network changes over time. Maintaining routes between all nodes requires the continuous transmission of control information, which consumes precious power and bandwidth resources. Many routing protocols have been developed, trading off control overhead and route quality. In this paper, we ask whether there exist low-overhead schemes that produce low-stretch routes, even in large networks where all the nodes are mobile. We present a scheme that maintains a hierarchical structure within which constant-stretch routes can be efficiently computed between every pair of nodes. The scheme rebuilds each level of the hierarchy periodically, at a rate that decreases exponentially with the level of the hierarchy. We prove that this scheme achieves constant stretch under a mild smoothness condition on the nodal mobility processes. Furthermore, we prove tight bounds for the network-wide control overhead under the additional assumption of the connectivity graph forming a doubling metric space. Specifically, we show that for a connectivity model combining the random geometric graph with obstacles, constant-stretch routes can be maintained with a total overhead of n log2 n bits of control information per time unit.

Fast and Accurate Inference of Plackett-Luce Models
L. Maystre and M. Grossglauser
Neural Information Processing Systems (NIPS), Montreal, Quebec, Canada, December 7-12, 2015.
[full text]

We show that the maximum-likelihood (ML) estimate of models derived from Luce’s choice axiom (e.g., the Plackett–Luce model) can be expressed as the stationary distribution of a Markov chain. This conveys insight into several recently proposed spectral inference algorithms. We take advantage of this perspective and formulate a new spectral algorithm that is significantly more accurate than previous ones for the Plackett–Luce model. With a simple adaptation, this algorithm can be used iteratively, producing a sequence of estimates that converges to the ML estimate. The ML version runs faster than competing approaches on a benchmark of five datasets. Our algorithms are easy to implement, making them relevant for practitioners at large

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?
E. Kazemi, L. Yartseva and M. Grossglauser
53rd IEEE Communication, Control, and Computing (Annual Allerton Conference), University of Illinois at Urbana-Champaign, September 30-October 2, 2015.
[view at publisher]

Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network analysis, privacy, pattern recognition, computer vision, and computational biology. A number of heuristic algorithms have been proposed in these fields. Recent progress in the analysis of network alignment over stochastic models sheds light on the interplay between network parameters and matchability. In this paper, we consider the alignment problem when the two networks overlap only partially, i.e., there exist vertices in one network that have no counterpart in the other. We define a random bigraph model that generates two correlated graphs $G_{1,2}$; it is parameterized by the expected node overlap $t^2$ and by the expected edge overlap $s^2$. We define a cost function for structural mismatch under a particular alignment, and we identify a threshold for perfect matchability: if the average node degrees of $G_{1,2}$ grow as $\omega\left( (s^{-2}t^{-1} \log(n) \right)$, then minimization of the proposed cost function results in an alignment which (i) is over exactly the set of shared nodes between $G_1$ and $G_2$, and (ii) agrees with the true matching between these shared nodes. Our result shows that network alignment is fundamentally robust to partial edge and node overlaps.

Electri-Fi Your Data: Measuring and Combining Power-Line Communications with WiFi
C. Vlachou, S. Henri and P. Thiran
ACM Internet Measurement Conference (IMC) 2015, Tokyo, Japan, October 28-30, 2015.
[view at publisher]

Power-line communication (PLC) is widely used as it offers high data-rates and forms a network over electrical wiring, an existing and ubiquitous infrastructure. PLC is increasingly being deployed in hybrid networks that combine multiple technologies, the most popular among which is WiFi. However, so far, it is not clear to which extent PLC can boost network performance or how hybrid implementations can exploit to the fullest this technology. We compare the spatial and temporal variations of WiFi and PLC. Despite the potential of PLC and its vast deployment in commercial products, little is known about its performance. To route or load balance traffic in hybrid networks, a solid understanding of PLC and its link metrics is required. We conduct experiments in a testbed of more than 140 links. We introduce link metrics that are crucial for studying PLC and that are required for quality-aware algorithms by recent standardizations of hybrid networks. We explore the spatial and temporal variation of PLC channels, showing that they are highly asymmetric and that link quality and link-metric temporal variability are strongly correlated. Based on our variation study, we propose and validate a capacity estimation technique via a metric that only uses the frame header. We also focus on retransmissions due to channel errors or to contention, a metric related to delay, and examine the sensitivity of metrics to background traffic. Our performance evaluation provides insight into the implementation of hybrid networks; we ease the intricacies of understanding the performance characteristics of the PHY and MAC layers.

Flexible Spectrum Assignment for Local Wireless Networks
J. Herzen
2015.
[view at publisher]

In this dissertation, we consider the problem of assigning spectrum to wireless local-area networks (WLANs). In line with recent IEEE 802.11 amendments and newer hardware capabilities, we consider situations where wireless nodes have the ability to adapt not only their channel center-frequency but also their channel width. This capability brings an important additional degree of freedom, which adds more granularity and potentially enables more efficient spectrum assignments. However, it also comes with new challenges; when consuming a varying amount of spectrum, the nodes should not only seek to reduce interference, but they should also seek to efficiently fill the available spectrum. Furthermore, the performances obtained in practice are especially difficult to predict when nodes employ variable bandwidths. We first propose an algorithm that acts in a decentralized way, with no communication among the neighboring access points (APs). Despite being decentralized, this algorithm is self-organizing and solves an explicit tradeoff between interference mitigation and efficient spectrum usage. In order for the APs to continuously adapt their spectrum to neighboring conditions while using only one network interface, this algorithm relies on a new kind of measurement, during which the APs monitor their surrounding networks for short durations. We implement this algorithm on a testbed and observe drastic performance gains compared to default spectrum assignments, or compared to efficient assignments using a fixed channel width. Next, we propose a procedure to explicitly predict the performance achievable in practice, when nodes operate with arbitrary spectrum configurations, traffic intensities, transmit powers, etc. This problem is notoriously difficult, as it requires capturing several complex interactions that take place at the MAC and PHY layers. Rather than trying to find an explicit model acting at this level of generality, we explore a different point in the design space. Using a limited number of real-world measurements, we use supervised machine-learning techniques to learn implicit performance models. We observe that these models largely outperform other measurement-based models based on SINR, and that they perform well, even when they are used to predict performance in contexts very different from the context prevailing during the initial set of measurements used for learning. We then build a second algorithm that uses the above-mentioned learned models to assign the spectrum. This algorithm is distributed and collaborative, meaning that neighboring APs have to exchange a limited amount of control traffic. It is also utility-optimal -- a feature enabled both by the presence of a model for predicting performance and the ability of APs to collaboratively take decisions. We implement this algorithm on a testbed, and we design a simple scheme that enables neighboring APs to discover themselves and to implement collaboration using their wired backbone network. We observe that it is possible to effectively gear the performance obtained in practice towards different objectives (in terms of efficiency and/or fairness), depending on the utility functions optimized by the nodes. Finally, we study the problem of scheduling packets both in time and frequency domains. Such ways of scheduling packets have been made possible by recent progress in system design, which make it possible to dynamically tune and negotiate the spectrum band [...]

CSMA/CA in Time and Frequency Domains
J. Herzen, A. Banchs, V. Shneer and P. Thiran
IEEE ICNP, San Francisco, CA, November 10-13, 2015.
[full text] [view at publisher]

It has recently been shown that flexible channelization, whereby wireless stations adapt their spectrum bands on a per-frame basis, is feasible in practice. In this paper, we propose TF-CSMA/CA, an algorithm for flexible channelization that schedules packets in time and frequency domains. TFCSMA/CA is a simple extension of the CSMA/CA protocol used by IEEE 802.11. Contrary to existing channelization schemes, it is entirely distributed and it reacts only to packet collisions, successful transmissions and carrier sensing. With TF-CSMA/CA, when a station is involved in a collision, it performs backoff in both time and frequency domains. Backing off also in the frequency domain allows the transmitters to be much more efficient and aggressive in the time domain, which significantly reduces the severe overheads present with recent 802.11 PHY layers. The main challenge, however, is that the stations need some level of self-organization in order to find spectrum bands of variable widths that minimize interference, while still efficiently using the available spectrum. Using analysis and simulations, we show that such an extension of CSMA/CA to the frequency domain drastically improves both throughput and fairness. Notably, it enables the stations to find interference-free spectrum bands of appropriate size using no communication – relying only on collisions and successes as implicit signals.

Learning Wi-Fi Performance
J. Herzen, H. Lundgren and N. Hegde
IEEE SECON, Seattle, WA, June 22-25, 2015.
[full text] [view at publisher]

Accurate prediction of wireless network performance is important when performing link adaptation or resource allocation. However, the complexity of interference interactions at MAC and PHY layers, as well as the vast variety of possible wireless configurations make it notoriously hard to design explicit performance models. In this paper, we advocate an approach of “learning by observation” that can remove the need for designing explicit and complex performance models. We use machine-learning techniques to learn implicit performance models, from a limited number of real-world measurements. These models do not require to know the internal mechanics of interfering Wi-Fi links. Yet, our results show that they improve accuracy by at least 49% compared to measurement-seeded models based on SINR. To demonstrate that learned models can be useful in practice, we build a new algorithm that uses such a model as an oracle to jointly allocate spectrum and transmit power. Our algorithm is utility-optimal, distributed, and it produces efficient allocations that significantly improve performance and fairness.

Mining, Modeling and Predicting Mobility
M. Kafsi
2015.
[view at publisher]

Mobility is a central aspect of our life, and our movements reveal much more about us than simply our whereabouts. In this thesis, we are interested in mobility and study it from three different perspectives: the modeling perspective, the information-theoretic perspective, and the data mining perspective. For the modeling perspective, we represent mobility as a probabilistic process described by both observable and latent variables, and we introduce formally the notion of individual and collective dimensions in mobility models. Ideally, we should take advantage of both dimensions to learn accurate mobility models, but the nature of data might limit us. We take a data-driven approach to study three scenarios, which differ on the nature of mobility data, and present, for each scenario, a mobility model that is tailored for it. The first scenario is individual-specific as we have mobility data about individuals but are unable to cross reference data from them. In the second scenario, we introduce the collective model that we use to overcome the sparsity of individual traces, and for which we assume that individuals in the same group exhibit similar mobility patterns. Finally, we present the ideal scenario, for which we can take advantage of both the individual and collective dimensions, and analyze collective mobility patterns in order to create individual models. In the second part of the thesis, we take an information-theoretic approach in order to quantify mobility uncertainty and its evolution with location updates. We discretize the userâ s world to obtain a map that we represent as a mobility graph. We model mobility as a random walk on this graph â equivalent to a Markov chain â and quantify trajectory uncertainty as the entropy of the distribution over possible trajectories. In this setting, a location update amounts to conditioning on a particular state of the Markov chain, which requires the computation of the entropy of conditional Markov trajectories. Our main result enables us to compute this entropy through a transformation of the original Markov chain. We apply our framework to real-world mobility datasets and show that the influence of intermediate locations on trajectory entropy depends on the nature of these locations. We build on this finding and design a segmentation algorithm that uncovers intermediate destinations along a trajectory. The final perspective from which we analyze mobility is the data mining perspective: we go beyond simple mobility and analyze geo-tagged data that is generated by online social medias and that describes the whole user experience. We postulate that mining geo-tagged data enables us to obtain a rich representation of the user experience and all that surrounds its mobility. We propose a hierarchical probabilistic model that enables us to uncover specific descriptions of geographical regions, by analyzing the geo-tagged content generated by online social medias. By applying our method to a dataset of 8 million geo-tagged photos, we are able to associate with each neighborhood the tags that describe it specifically, and to find the most unique neighborhoods in a city.

Electri-Fi Your Data: Measuring and Combining Power-Line Communications with WiFi (Technical Report 210617, EPFL)
C. Vlachou, S. Henri and P. Thiran
2015.

Introduction aux sciences de l'information
J. Le Boudec, P. Thiran and R. Urbanke
2015.
[full text]

Les fichiers échangés sur Internet et stockés sur les disques durs contiennent de l’information qui deviendra finalement du texte, des images ou des sons. Mais comment cette information est-elle mesurée et comprimée ? Comment est-elle sécurisée pour éviter les copies illicites ? Comment est-elle protégée contre les erreurs lors d’une recopie ? Voici les questions auxquelles répond cet ouvrage. Sans équivalent dans la littérature, il présente pour la première fois les théories de l’entropie, du codage et de la cryptographie de façon simple, claire et pédagogique. Principalement destiné aux étudiants en sciences de première année de Bachelor, il intéressera aussi, et plus largement, tous ceux curieux de comprendre la théorie scientifique à la base du traitement de l’information.

Growing a Graph Matching from a Handful of Seeds
E. Kazemi, S. H. Hassani and M. Grossglauser
Proceedings of the VLDB Endowment International Conference on Very Large Data Bases, vol. 8, no. 10, 1010 - 1021, 2015.
[full text] [view at publisher]

In many graph–mining problems, two networks from different domains have to be matched. In the absence of reliable node attributes, graph matching has to rely on only the link structures of the two networks, which amounts to a generalization of the classic graph isomorphism problem. Graph matching has applications in social–network reconciliation and de-anonymization, protein–network alignment in biology, and computer vision. The most scalable graph–matching approaches use ideas from percolation theory, where a matched node pair “infects” neighbouring pairs as additional potential matches. This class of matching algorithm requires an initial seed set of known matches to start the percolation. The size and correctness of the matching is very sensitive to the size of the seed set. In this paper, we give a new graph–matching algorithm that can operate with a much smaller seed set than previous approaches, with only a small increase in matching errors. We characterize a phase transition in matching performance as a function of the seed set size, using a random bigraph model and ideas from bootstrap percolation theory. We also show the excellent performance in matching several real large-scale social networks, using only a handful of seeds.

Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks
R. Zhang, P. Thiran and M. Vetterli
2015.
[full text]

Energy efficiency of wireless sensor networks (WSNs) can be improved by moving base stations (BSs), as this scheme evenly distributes the communication load in the network. However, physically moving BSs is complicated and costly. In this paper, we propose a new scheme: virtually moving the BSs. We deploy an excessive number of BSs and adaptively re-select a subset of active BSs so as to emulate the physical movement. Beyond achieving high energy-efficiency, this scheme obviates the difficulties associated with physically moving the BSs. The challenges are (i) that the energy efficiency of BSs should be considered as well, in addition to that of the sensor nodes and (ii) that the number of candidate subset of active BSs is exponential with the number of BSs. We show that scheduling the virtual movement of BSs is NP-hard. Then, we propose a polynomial-time algorithm that is guaranteed under mild conditions to achieve a lifetime longer than 62% of the optimal one. In practice, as verified through extensive numerical simulations, the lifetime achieved by the proposed algorithm is always very close to the optimum.

Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks
R. Zhang, P. Thiran and M. Vetterli
The Sixteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hangzhou, China, June 22-25, 2015.
[full text] [view at publisher]

Energy efficiency of wireless sensor networks (WSNs) can be improved by moving base stations (BSs), as this scheme evenly distributes the communication load in the network. However, physically moving BSs is complicated and costly. In this paper, we propose a new scheme: virtually moving BSs. We deploy an excessive number of BSs and adaptively re-select a subset of active BSs so as to emulate the physical movement. Beyond achieving high energy efficiency, this scheme obviates the difficulties associated with physically moving BSs. Challenges are that (i) the energy efficiency of BSs should be considered as well, in addition to that of the sensor nodes; (ii) the number of candidate subset of active BSs is exponential with the number of BSs. We show that scheduling the virtual movement of BSs is NP-hard. Then, we propose a polynomial-time algorithm that is guaranteed under mild conditions to achieve a lifetime longer than 62% of the optimal one. In practice, as verified through extensive numerical simulations, the lifetime achieved by the proposed algorithm is always very close to the optimum.

The Beauty of the Commons: Optimal Load Sharing by Base Station Hopping in Wireless Sensor Networks
R. Zhang, F. Ingelrest, G. Barrenetxea, P. Thiran and M. Vetterli
IEEE Journal on Selected Areas in Communications, vol. 33, no. 8, 1480 - 1491, 2015.
[full text] [view at publisher]

In wireless sensor networks (WSNs), the base station (BS) is a critical sensor node whose failure causes severe data losses. Deploying multiple fixed BSs improves the robustness, yet requires all BSs to be installed with large batteries and large energy-harvesting devices due to the high energy consumption of BSs. In this paper, we propose a scheme to coordinate the multiple deployed BSs such that the energy supplies required by individual BSs can be substantially reduced. In this scheme, only one BS is selected to be active at a time and the other BSs act as regular sensor nodes. We first present the basic architecture of our system, including how we keep the network running with only one active BS and how we manage the handover of the role of the active BS. Then, we propose an algorithm for adaptively selecting the active BS under the spatial and temporal variations of energy resources. This algorithm is simple to implement but is also asymptotically optimal under mild conditions. Finally, by running simulations and real experiments on an outdoor testbed, we verify that the proposed scheme is energy-efficient, has low communication overhead and reacts rapidly to network changes.

Opportunistic Sampling for Joint Population Size and Density Estimation
F. Movahedi Naini, O. Dousse, P. Thiran and M. Vetterli
IEEE Transactions on Mobile Computing, vol. 14, no. 12, 2530 - 2543, 2015.
[code] [full text] [view at publisher]

Consider a set of probes, called “agents”, who sample, based on opportunistic contacts, a population moving between a set of discrete locations. An example of such agents are Bluetooth probes that sample the visible Bluetooth devices in a population. Based on the obtained measurements, we construct a parametric statistical model to jointly estimate the total population size (e.g., the number of visible Bluetooth devices) and their spatial density. We evaluate the performance of our estimators by using Bluetooth traces obtained during an open-air event and Wi-Fi traces obtained on a university campus.

2014

Variational Gaussian Inference for Bilinear Models of Count Data
Y. J. Ko and M. E. Khan
6th Asian Conference on Machine Learning, Nha Trang, Vietnam, 2014.
[full text]

Bilinear models of count data with Poisson distribution are popular in applications such as matrix factorization for recommendation systems, modeling of receptive fields of sensory neurons, and modeling of neural-spike trains. Bayesian inference in such models remains challenging due to the product term of two Gaussian random vectors. In this paper, we propose new algorithms for such models based on variational Gaussian (VG) inference. We make two contributions. First, we show that the VG lower bound for these models, previously known to be intractable, is available in closed form under certain non-trivial constraints on the form of the posterior. Second, we show that the lower bound is biconcave and can be efficiently optimized for mean-field approximations. We also show that bi-concavity generalizes to the larger family of log-concave likelihoods, that subsume the Poisson distribution. We present new inference algorithms based on these results and demonstrate better performance on real-world problems at the cost of a modest increase in computation. Our contributions in this paper, therefore, provide more choices for Bayesian inference in terms of a speed-vs-accuracy tradeoff.

On the MAC for Power-Line Communications: Modeling Assumptions and Performance Tradeoffs (Technical Report 205771, EPFL)
C. Vlachou, A. Banchs, J. Herzen and P. Thiran
2014.

Simulator and Experimental Framework for the MAC of Power-Line Communications
C. Vlachou, J. Herzen and P. Thiran
2014.

Buy-It-Now or Take-a-Chance: Price Discrimination Through Randomized Auctions
L. E. Celis, G. Lewis, M. Mobius and H. Nazerzadeh
Management Science, vol. 60, no. 12, 2927 - 2948, 2014.
[view at publisher]

Increasingly detailed consumer information makes sophisticated price discrimination possible. At fine levels of aggregation, demand may not obey standard regularity conditions. We propose a new randomized sales mechanism for such environments. Bidders can "buy-it-now" at a posted price, or "take-a-chance" in an auction where the top d > 1 bidders are equally likely to win. The randomized allocation incentivizes high-valuation bidders to buy-it-now. We analyze equilibrium behavior and apply our analysis to advertiser bidding data from Microsoft Advertising Exchange. In counterfactual simulations, our mechanism increases revenue by 4.4% and consumer surplus by 14.5% compared to an optimal second-price auction.

Data-driven healthcare: from patterns to actions
M. Grossglauser and H. Saner
European Journal Of Preventive Cardiology, vol. 21, 14 - 17, 2014.
[view at publisher]

The era of big data opens up new opportunities in personalised medicine, preventive care, chronic disease management and in telemonitoring and managing of patients with implanted devices. The rich data accumulating within online services and internet companies provide a microscope to study human behaviour at scale, and to ask completely new questions about the interplay between behavioural patterns and health. In this paper, we shed light on a particular aspect of data-driven healthcare: autonomous decision-making. We first look at three examples where we can expect data-driven decisions to be taken autonomously by technology, with no or limited human intervention. We then discuss some of the technical and practical challenges that can be expected, and sketch the research agenda to address them.

Analyzing and Boosting the Performance of Power-Line Communication Networks
C. Vlachou, A. Banchs, J. Herzen and P. Thiran
ACM 10th International Conference on emerging Networking EXperiments and Technologies (CoNEXT), Sydney, Australia, December 2-5, 2014.
[full text] [view at publisher]

Power-line communications are employed in home networking to provide easy and high-throughput connectivity. IEEE 1901, the MAC protocol for power-line networks, employs a CSMA/CA protocol similar to that of 802.11, but is substantially more complex, which probably explains why little is known about its performance. One of the key differences between the two protocols is that whereas 802.11 only reacts upon collisions, 1901 also reacts upon several consecutive transmissions and thus can potentially achieve better performance by avoiding unnecessary collisions. In this paper, we propose a model for the 1901 MAC. Our analysis reveals that the default configuration of 1901 does not fully exploit its potential and that its performance degrades with the number of stations. We derive analytically the optimal configuration parameters for 1901; this drastically improves throughput and achieves optimal performance without requiring the knowledge of the number of stations in the network. In contrast, to provide a similar performance, 802.11 requires knowing the number of contending stations, which is unfeasible for realistic traffic patterns. Our solution can be readily implemented by vendors, as it only consists in modifying existing MAC parameters. We corroborate our results with testbed measurements, unveiling a significant signaling overhead in 1901 implementations.

On the MAC for Power-Line Communications: Modeling Assumptions and Performance Tradeoffs
C. Vlachou, A. Banchs, J. Herzen and P. Thiran
IEEE 22nd International Conference on Network Protocols (ICNP), The Research Triangle, North Carolina, 2014.
[full text] [view at publisher]

Power-line communications are becoming a key component in home networking. The dominant MAC protocol for high data-rate power-line communications, IEEE 1901, employs a CSMA/CA mechanism similar to the backoff process of 802.11. Existing performance evaluation studies of this protocol assume that the backoff processes of the stations are independent (the so-called decoupling assumption). However, in contrast to 802.11, 1901 stations can change their state after sensing the medium busy, which introduces strong coupling between the stations, and, as a result, makes existing analyses inaccurate. In this paper, we propose a new performance model for 1901, which does not rely on the decoupling assumption. We prove that our model admits a unique solution. We confirm the accuracy of our model using both testbed experiments and simulations, and we show that it surpasses current models based on the decoupling assumption. Furthermore, we study the tradeoff between delay and throughput existing with 1901. We show that this protocol can be configured to accommodate different throughput and jitter requirements, and give systematic guidelines for its configuration.

Mining Democracy
V. Etter, J. Herzen, M. Grossglauser and P. Thiran
ACM Conference on Online Social Networks (COSN'14), Dublin, Ireland, October 1-2, 2014.
[full text] [view at publisher]

Switzerland has a long tradition of direct democracy, which makes it an ideal laboratory for research on real-world politics. Similar to recent open government initiatives launched worldwide, the Swiss government regularly releases datasets related to state affairs and politics. In this paper, we propose an exploratory, data-driven study of the political landscape of Switzerland, in which we use opinions expressed by candidates and citizens on a web platform during the recent Swiss parliamentary elections, together with fine-grained vote results and parliament votes. Following this purely data-driven approach, we show that it is possible to uncover interesting patterns that would otherwise require both tedious manual analysis and domain knowledge. In particular, we show that traditional cultural and/or ideological idiosyncrasies can be highlighted and quantified by looking at vote results and pre-election opinions. We propose a technique for comparing the candidates' opinions expressed before the elections with their actual votes cast in the parliament after the elections. This technique spots politicians that do not vote consistently with the opinions that they expressed during the campaign. We also observe that it is possible to predict surprisingly precisely the outcome of nationwide votes, by looking at the outcome in a single, carefully selected municipality. Our work applies to any country where similar data is available; it points to some of the avenues created by user-generated data emerging from open government initiatives, which enable new data-mining approaches to political and social sciences.

Population Sensing Using Mobile Devices : a Statistical Opportunity or a Privacy Nightmare?
F. Movahedi Naini
2014.
[view at publisher]

In our daily lives, our mobile phones sense our movements and interactions via a rich set of embedded sensors such as a GPS, Bluetooth, accelerometers, and microphones. This enables us to use mobile phones as agents for collecting spatio-temporal data. The idea of mining these spatio-temporal data is currently being explored for many applications, including environmental pollution monitoring, health care, and social networking. When used as sensing devices, a particular feature of mobile phones is their aspect of mobility, in contrast to static sensors. Furthermore, despite having useful applications, collecting data from mobile phones introduces privacy concerns, as the collected data might reveal sensitive information about the users, especially if the collector has access to auxiliary information. In the first part of this thesis, we use spatio-temporal data collected by mobile phones in order to evaluate different features of a population related to their mobility patterns. In particular, we consider the problems of population-size and population-density estimation that have applications, among others, in crowd monitoring, activity-hotspot detection, and urban analysis. We first conduct an experiment where ten attendees of an open-air music festival act as Bluetooth probes. Next, we construct parametric statistical models to estimate the total number of visible Bluetooth devices and their density in the festival area. We further test our proposed models against Wi-Fi traces obtained on the EPFL campus. We conclude that mobile phones can be effectively used as sensing devices to evaluate mobility-related parameters of a population. For the specific problem of population-density estimation, we investigate the mobility aspect of sensing: We quantitatively analyze the performance of mobile sensors compared to static sensors. Under an independent and identically distributed mobility model for the population, we derive the optimal random-movement strategy for mobile sensors in order to yield the best estimate of population density (in the mean-squared error sense). This enables us to plan an adaptive trajectory for the mobile sensors. In particular, we demonstrate that mobility brings an added value to the sensors; these sensors outperform static sensors for long observation intervals. In the second part of this thesis, we analyze the vulnerability of anonymized mobility statistics stored in the form of histograms. We consider an attacker who has access to an anonymized set of histograms of a set of users’ mobility traces and to an independent set of non-anonymized histograms of traces belonging to the same users. We study the hypothesis-testing problem of identifying the correct matching between the anonymized histograms and the non-anonymized histograms. We show that the solution can be obtained by using a minimum-weight matching algorithm on a complete weighted bipartite graph. By applying the algorithm to Wi-Fi traces obtained on the EPFL campus, we demonstrate that in fact anonymized histograms contain a significant amount of information that could be used to uniquely identify users by an attacker with access to auxiliary information about the users. Finally, we demonstrate how trust relationships between users can be exploited to enhance their privacy. We consider the specific problem of the privacy-preserving computation of functions of data that belong to users in a social network. An example of an application is a poll or a survey on a private issue. Most of the known non-cryptographic solutions to this problem can be viewed as belonging to one of the following two extreme regimes. The first regime is when every user trusts only herself and she is responsible for protecting her own privacy. In other words, the circle of trust of a user has a single member: herself. In the second regime, every user trusts herself and the server, but not any of the other users. In other words, the circle of trust of a user comprises herself and the server. We investigate this problem under the assumption that users are willing to share their private data with trusted friends in the network, hence we consider a regime in which the circle of trust of a user consists of herself and her friends. Thus, our approach falls in-between the two mentioned regimes. Our algorithm consists of first partitioning users into circles of trust and then computing the global function by using results of local computations within each circle. We demonstrate that such trust relationships can be exploited to significantly improve the tradeoff between the privacy of users' data and the accuracy of the computation.

Performance Analysis of MAC for Power-Line Communications
C. Vlachou, A. Banchs, J. Herzen and P. Thiran
ACM SIGMETRICS 2014 (poster session), Austin, Texas, USA, 16-20 June, 2014.
[full text] [view at publisher]

We investigate the IEEE 1901 MAC protocol, the dominant protocol for high data rate power-line communications. 1901 employs a CSMA/CA mechanism similar to – but much more complex than – the backoff mechanism of 802.11. Because of this extra complexity, and although this mechanism is the only widely used MAC layer for power-line networks, there are few analytical results on its performance. We propose a model for the 1901 MAC that comes in the form of a single fixed-point equation for the collision probability. We prove that this equation admits a unique solution, and we evaluate the accuracy of our model by using simulations.

Privacy-Preserving Function Computation by Exploitation of Friendships in Social Networks
F. Movahedi Naini, J. Unnikrishnan, P. Thiran and M. Vetterli
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Florence, Italy, May 4-9, 2014.
[view at publisher]

We study the problem of privacy-preserving computation of functions of data that belong to users in a social network under the assumption that users are willing to share their private data with trusted friends in the network. We demonstrate that such trust relationships can be exploited to significantly improve the trade-off between the privacy of users’ data and the accuracy of the computation. Under a one-hop trust model we design an algorithm for partitioning the users into circles of trust and develop a differentially private scheme for computing the global function using results of local computations within each circle. We quantify the improvement in the privacy--accuracy trade-off of our scheme with respect to other mechanisms that do not exploit inter-user trust. We verify the efficiency of our algorithm by implementing it on social networks with up to one million nodes. Applications of our method include surveys, elections, and recommendation systems.

Hiding in the Mobile Crowd: Location Privacy through Collaboration
R. Shokri, G. Theodorakopoulos, P. Papadimitratos, E. Kazemi and J. Hubaux
IEEE Transactions on Dependable and Secure Computing, vol. 11, no. 3, 266 - 279, 2014.
[view at publisher]

Location-aware smartphones support various location-based services (LBSs): users query the LBS server and learn on the fly about their surroundings. However, such queries give away private information, enabling the LBS to track users. We address this problem by proposing a user-collaborative privacy preserving approach for LBSs. Our solution does not require changing the LBS server architecture and does not assume third party servers; yet, it significantly improves users’ location privacy. The gain stems from the collaboration of mobile devices: they keep their context information in a buffer and pass it to others seeking such information. Thus, a user remains hidden from the server, unless all the collaborative peers in the vicinity lack the sought information. We evaluate our scheme against the Bayesian localization attacks that allow for strong adversaries who can incorporate prior knowledge in their attacks. We develop a novel epidemic model to capture the, possibly time-dependent, dynamics of information propagation among users. Used in the Bayesian inference framework, this model helps analyze the effects of various parameters, such as users’ querying rates and the lifetime of context information, on users’ location privacy. The results show that our scheme hides a high fraction of location-based queries, thus significantly enhancing users’ location privacy. Our simulations with real mobility traces corroborate our model-based findings. Finally, our implementation on mobile platforms indicates that it is lightweight and the cost of collaboration is negligible.

Hiding in the Mobile Crowd: Location Privacy through Collaboration
R. Shokri, G. Theodorakopoulos, P. Papadimitratos, E. Kazemi and J. Hubaux
2014.

Location-aware smartphones support various location-based services (LBSs): users query the LBS server and learn on the fly about their surroundings. However, such queries give away private information, enabling the LBS to track users. We address this problem by proposing a user-collaborative privacy preserving approach for LBSs. Our solution does not require changing the LBS server architecture and does not assume third party servers; yet, it significantly improves users’ location privacy. The gain stems from the collaboration of mobile devices: they keep their context information in a buffer and pass it to others seeking such information. Thus, a user remains hidden from the server, unless all the collaborative peers in the vicinity lack the sought information. We evaluate our scheme against the Bayesian localization attacks that allow for strong adversaries who can incorporate prior knowledge in their attacks. We develop a novel epidemic model to capture the, possibly time-dependent, dynamics of information propagation among users. Used in the Bayesian inference framework, this model helps analyze the effects of various parameters, such as users’ querying rates and the lifetime of context information, on users’ location privacy. The results show that our scheme hides a high fraction of location-based queries, thus significantly enhancing users’ location privacy. Our simulations with real mobility traces corroborate our model-based findings. Finally, our implementation on mobile platforms indicates that it is lightweight and the cost of collaboration is negligible.

2013

A Bayesian Method for Matching Two Similar Graphs without Seeds
P. Pedarsani, D. R. Figueiredo and M. Grossglauser
Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, October 2013.
[full text] [view at publisher]

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited to either small graphs (e.g., tens or hundreds of nodes), or to large graphs in combination with side information beyond the graph structure (e.g., a seed set of pre-mapped node pairs). In this paper, we cast AGM in a Bayesian framework based on a clean definition of the probability of correctly mapping two nodes, which leads to a polynomial time algorithm that does not require side information. Node features such as degree and distances to other nodes are used as fingerprints. The algorithm proceeds in rounds, such that the most likely pairs are mapped first; these pairs subsequently generate additional features in the fingerprints of other nodes. We evaluate our method over real social networks and show that it achieves a very low matching error provided the two graphs are sufficiently similar. We also evaluate our method on random graph models to characterize its behavior under various levels of node clustering.

Mitigating Epidemics through Mobile Micro-measures
M. Kafsi, E. Kazemi, L. Maystre, L. Yartseva, M. Grossglauser and P. Thiran
NetMob, Boston, Massachusetts, USA, May 2013.

De-anonymizing Private Data by Matching Statistics
J. Unnikrishnan and F. Movahedi Naini
Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, USA, October 2-4, 2013.
[view at publisher]

Where to go from here? Mobility prediction from instantaneous information
V. Etter, M. Kafsi, E. Kazemi, M. Grossglauser and P. Thiran
Pervasive And Mobile Computing, vol. 9, no. 6, 784 - 797, 2013.
[view at publisher]

We present the work that allowed us to win the Next-Place Prediction task of the Nokia Mobile Data Challenge. Using data collected from the smartphones of 80 users, we explore the characteristics of their mobility traces. We then develop three families of predictors, including tailored models and generic algorithms, to predict, based on instantaneous information only, the next place a user will visit. These predictors are enhanced with aging techniques that allow them to adapt quickly to the users' changes of habit. Finally, we devise various strategies to blend predictors together and take advantage of their diversity, leading to relative improvements of up to 4%. (C) 2013 Elsevier B.V. All rights reserved.

Wireless Multi-hop Networks Beyond Capacity
A. Aziz, S. Shneer and P. Thiran
19th IEEE International Workshop on Local and Metropolitan Area Networks (LANMAN), 2013.
[view at publisher]

Wireless multi-hop local area networks use in general scheduling schemes that assume the network capacity to be known. Indeed in most of the throughput-optimal algorithms the sources are assumed to send at a rate within the capacity region. However, measurements made on real deployments show that the network capacity is usually difficult to characterize and also time-varying. It is therefore important to understand how the network behaves when the sources attempt to transmit at a rate above capacity. Toward this goal, we show 3-phase regime in the effect of the input rate lambda on the end-to-end throughput mu of a multi-hop network. First, when lambda is smaller than a threshold lambda(1), mu is an increasing function of lambda. Second, when lambda is larger than another threshold lambda(2) > lambda(1), mu is independent of lambda. Third, when lambda(1) < lambda < lambda(2), mu decreases with lambda. To understand this phenomenon, we capture the relation between the end-to-end throughput and the queue stability with a mathematical model that allows us to explain and derive the exact values of the transition points lambda(i). We then validate experimentally our simulation results with measurements on a testbed composed of five wireless routers.

SAW: Spectrum Assignment for WLANs
J. Herzen, R. Merz and P. Thiran
ACM S3 2013, Miami, Florida, USA, September 30, 2013.
[full text]

We consider the problem of jointly allocating channel center-frequencies and bandwidths for IEEE 802.11 wireless LANs (WLANs). The bandwidth used on a link significantly affects both the capacity experienced on this link and the interference produced on neighboring links. Therefore, when jointly assigning both center frequencies and channel widths, a trade-off must be found between interference mitigation and the potential capacity offered on each link. We study this trade-off and present SAW (spectrum assignment for WLANs), a decentralized algorithm that finds efficient configurations. SAW is tailored for 802.11 home networks. It is distributed, online and transparent. It does not require a central coordinator and it constantly adapts the spectrum usage without disrupting network traffic. The algorithm is decentralized and self-organizing; it provably converges towards efficient spectrum allocations. We evaluate SAW using both simulation and a deployment on an indoor testbed composed of off-the-shelf 802.11 hardware. We observe that it dramatically increases the overall network efficiency and fairness, even when some Access Points (APs) do not behave socially.

On the Performance of Percolation Graph Matching
L. Yartseva and M. Grossglauser
COSN'13: Conference on Online Social Networks, Boston, Massachusetts, USA, October 7-8, 2013.
[full text] [view at publisher]

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and information networks and, more generally, in the merging of structural data from different domains. One class of graph-matching algorithms starts with a known seed set of matched node pairs. Despite the success of these algorithms in practical applications, their performance has been observed to be very sensitive to the size of the seed set. The lack of a rigorous understanding of parameters and performance makes it difficult to design systems and predict their behavior. In this paper, we propose and analyze a very simple percolation $\!$-based graph matching algorithm that incrementally maps every pair of nodes $(i,j)$ with at least $r$ neighboring mapped pairs. The simplicity of this algorithm makes possible a rigorous analysis that relies on recent advances in bootstrap percolation theory for the $G(n,p)$ random graph. We prove conditions on the model parameters in which percolation graph matching succeeds, and we establish a phase transition in the size of the seed set. We also confirm through experiments that the performance of percolation graph matching is surprisingly good, both for synthetic graphs and real social-network data.

Launch Hard or Go Home! Predicting the Success of Kickstarter Campaigns
V. Etter, M. Grossglauser and P. Thiran
The first ACM conference on Online Social Networks (COSN'13), Boston, Massachusetts, USA, October 7-8, 2013.
[full text] [view at publisher]

Crowdfunding websites such as Kickstarter are becoming increasingly popular, allowing project creators to raise hundreds of millions of dollars every year. However, only one out of two Kickstarter campaigns reaches its funding goal and is successful. It is therefore of prime importance, both for project creators and backers, to be able to know which campaigns are likely to succeed. We propose a method for predicting the success of Kickstarter campaigns by using both direct information and social features. We introduce a first set of predictors that uses the time series of money pledges to classify campaigns as probable success or failure and a second set that uses information gathered from tweets and Kickstarter's projects/backers graph. We show that even though the predictors that are based solely on the amount of money pledged reach a high accuracy, combining them with predictors using social features enables us to improve the performance significantly. In particular, only 4 hours after the launch of a campaign, the combined predictor reaches an accuracy of more than 76% (a relative improvement of 4%).

The Entropy of Conditional Markov Trajectories
M. Kafsi, M. Grossglauser and P. Thiran
IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 59, no. 9, 5577 - 5583, 2013.
[view at publisher]

To quantify the randomness of Markov trajectories with fixed initial and final states, Ekroot and Cover proposed a closed-form expression for the entropy of trajectories of an irreducible finite state Markov chain. Numerous applications, including the study of random walks on graphs, require the computation of the entropy of Markov trajectories conditional on a set of intermediate states. However, the expression of Ekroot and Cover does not allow for computing this quantity. In this paper, we propose a method to compute the entropy of conditional Markov trajectories through a transformation of the original Markov chain into a Markov chain that exhibits the desired conditional distribution of trajectories. Moreover, we express the entropy of Markov trajectories—a global quantity—as a linear combination of local entropies associated with the Markov chain states.

Nowhere to Hide: Navigating around Privacy in Online Social Networks
M. Humbert, T. Studer, M. Grossglauser and J. Hubaux
The 18th European Symposium on Research in Computer Security (ESORICS), Egham, United Kingdom, September 9-11, 2013.
[view at publisher]

In this paper, we introduce a navigation privacy attack, where an external adversary attempts to find a target user by exploiting publicly visible attributes of intermediate users. If such an attack is successful, it implies that a user cannot hide simply by excluding himself from a central directory or search function. The attack exploits the fact that most attributes (such as place of residence, age, or alma mater) tend to correlate with social proximity, which can be exploited as navigational cues while crawling the network. The problem is exacerbated by privacy policies where a user who keeps his profile private remains nevertheless visible in his friends' "friend lists"; such a user is still vulnerable to our navigation attack. Experiments with Facebook and Google+ show that the majority of users can be found efficiently using our attack, if a small set of attributes are known about the target as side information. Our results suggest that, in an online social network where many users reveal a (even limited) set of attributes, it is nearly impossible for a specific user to "hide in the crowd".

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol (Technical Report)
J. Herzen, C. Westphal and P. Thiran
2013.

We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a space of concise dimensionality, which enables greedy routing based only on local knowledge. PIE is a general routing scheme, meaning that it works on any graph. We focus however on the Internet, where routing scalability is an urgent concern. We show analytically and by using simulation that the scheme scales extremely well on Internet-like graphs. In addition, its geometric nature allows it to react efficiently to topological changes or failures by finding new paths in the network at no cost, yielding better delivery ratios than standard algorithms. The proposed routing scheme needs an amount of memory polylogarithmic in the size of the network and requires only local communication between the nodes. Although each node constructs its coordinates and routes packets locally, the path stretch remains extremely low, even lower than for centralized or less scalable state-of-the-art algorithms: PIE always finds short paths and often enough finds the shortest paths.

Distributed Spectrum Assignment for Home WLANs
J. Herzen, R. Merz and P. Thiran
IEEE Infocom 2013, Torino, Italy, April 15-19, 2013.
[full text] [view at publisher]

We consider the problem of jointly allocating chan- nel center frequencies and bandwidths for IEEE 802.11 wireless LANs (WLANs). The bandwidth used on a link affects sig- nificantly both the capacity experienced on this link and the interference produced on neighboring links. Therefore, when jointly assigning both center frequencies and channel widths, there is a trade-off between interference mitigation and the potential capacity offered on each link. We study this trade- off and we present SAW (spectrum assignment for WLANs), a decentralized algorithm that finds efficient configurations. SAW is tailored for 802.11 home networks. It is distributed, online and transparent. It does not require a central coordinator and it constantly adapts the spectrum usage without disrupting network traffic. A key feature of SAW is that the access points (APs) need only a few out-of-band measurements in order to make spectrum allocation decisions. Despite being completely decentralized, the algorithm is self-organizing and provably converges towards efficient spectrum allocations. We evaluate SAW using both simulation and a deployment on an indoor testbed composed of off-the-shelf 802.11 hardware. We observe that it dramatically increases the overall network efficiency and fairness.

Privacy and Dynamics of Social Networks
P. Pedarsani
2013.
[view at publisher]

Over the past decade, investigations in different fields have focused on studying and understanding real networks, ranging from biological to social to technological. These networks, called complex networks, exhibit common topological features, such as a heavy-tailed degree distribution and the small world effect. In this thesis we address two interesting aspects of complex, and more specifically, social networks: (1) users’ privacy, and the vulnerability of a network to user identification, and (2) dynamics, or the evolution of the network over time. For this purpose, we base our contributions on a central tool in the study of graphs and complex networks: graph sampling. We conjecture that each observed network can be treated as a sample from an underlying network. Using this, a sampling process can be viewed as a way to observe dynamic networks, and to model the similarity of two correlated graphs by assuming that the graphs are samples from an underlying generator graph. We take the thesis in two directions. For the first, we focus on the privacy problem in social networks. There have been hot debates on the extent to which the release of anonymized information to the public can leak personally identifiable information (PII). Recent works have shown methods that are able to infer true user identities, under certain conditions and by relying on side information. Our approach to this problem relies on the graph structure, where we investigate the feasibility of de-anonymizing an unlabeled social network by using the structural similarity to an auxiliary network. We propose a model where the two partially overlapping networks of interest are considered samples of an underlying graph. Using such a model, first, we propose a theoretical framework for the de-anonymization problem, we obtain minimal conditions under which de-anonymization is feasible, and we establish a threshold on the similarity of the two networks above which anonymity could be lost. Then, we propose a novel algorithm based on a Bayesian framework, which is capable of matching two graphs of thousands of nodes - with no side information other than network structures. Our method has several potential applications, e.g., inferring user identities in an anonymized network by using a similar public network, cross-referencing dictionaries of different languages, correlating data from different domains, etc. We also introduce a novel privacy-preserving mechanism for social recommender systems, where users can receive accurate recommendations while hiding their profiles from an untrusted recommender server. For the second direction of this work, we focus on models for network growth, more specifically where the number of edges grows faster than the number of nodes, a property known as densification. The densification phenomenon has been recently observed in various real networks, and we argue that it can be explained simply through the way we observe (sample) networks. We introduce a process of sampling the edges of a fixed graph, which results in the super-linear growth of edges versus nodes, and show that densification arises if and only if the graph has a power-law degree distribution.

Fairness of MAC protocols: IEEE 1901 vs. 802.11
C. Vlachou, J. Herzen and P. Thiran
IEEE 17th International Symposium On Power Line Communications And Its Applications (ISPLC), Johannesburg, South Africa, 2013.
[full text] [view at publisher]

The MAC layer of the IEEE 1901 standard for power line communications employs a CSMA/CA method similar to, but more complex than, this of IEEE 802.11 for wireless communications. The differences between these protocols raise questions such as which one performs better and under what conditions. We study the fairness of the 1901 MAC protocol in single contention domain networks, where all stations hear each other. We examine fairness at the packet level: a MAC layer protocol is fair if all stations share equitably the medium during a fixed time interval. We focus on short-term fairness, that is, over short time intervals. Short-term fairness directly impacts end-user experience, because unfair protocols are susceptible to introduce substantial packet delays. We evaluate short-term fairness with two metrics: Jain's fairness index and the number of inter-transmissions. We present test-bed results of both protocols and compare them with simulations. Both simulation and test-bed results indicate that 802.11 is fairer in the short-term when the number of stations N is between 2 and 5. However, simulation results reveal that 1901 is fairer in the short-term for N >= 15. Importantly, our test-bed measurements indicate that 1901 unfairness can cause significant additional delay when N = 2. Finally, we confirm these results by showing analytically that 1901 is short-term unfair for N = 2.

2012

Music Recommendation to Groups
L. Maystre
2012.

First we present Unison, a conceptual music recommender system for groups of people; the system aims at generating a playlist that takes musical tastes of all the group members into account. We discuss both theoretical and practical concerns related to such a system. We develop a model of user preferences and discuss how we can shift from individual recommendations to group consensus. In constructing the user preferences model we use an intermediary music track model that combines user-generated tags with a dimensionality reduction technique to build a compact spatial embedding of tracks. Secondly we introduce GroupStreamer, a practical implementation of the system that runs on Android devices. We present the technological choices that were made along the way.

Privacy and Dynamics of Social Networks (PhD Thesis: pre-print)
P. Pedarsani
2012.
[full text]

Over the past decade, investigations in different fields have focused on studying and understanding real networks, ranging from biological to social to technological. These networks, called complex networks, exhibit common topological features, such as a heavy-tailed degree distribution and the small world effect. In this thesis we address two interesting aspects of complex, and more specifically, social networks: (1) users' privacy, and the vulnerability of a network to user identification, and (2) dynamics, or the evolution of the network over time. For this purpose, we base our contributions on a central tool in the study of graphs and complex networks: graph sampling. We conjecture that each network snapshot can be treated as a sample from an underlying network. Using this, a sampling process can be viewed as a way to observe dynamic networks, and to model the similarity of two correlated graphs by assuming that the graphs are samples from an underlying generator graph. We take the thesis in two directions. For the first, we focus on the privacy problem in social networks. There have been hot debates on the extent to which the release of anonymized information to the public can leak personally identifiable information (PII). Recent works have shown methods that are able to infer true user identities, under certain conditions and by relying on side information. Our approach to this problem relies on the graph structure, where we investigate the feasibility of de-anonymizing an unlabeled social network by using the structural similarity to an auxiliary network. We propose a model where the two partially overlapping networks of interest are considered samples of an underlying graph. Using such a model, first, we propose a theoretical framework for the de-anonymization problem, we obtain minimal conditions under which de-anonymization is feasible, and we establish a threshold on the similarity of the two networks above which anonymity could be lost. Then, we propose a novel algorithm based on a Bayesian framework, which is capable of matching two graphs of thousands of nodes - with no side information other than network structures. Our method has several potential applications, e.g., inferring user identities in an anonymized network by using a similar public network, cross-referencing dictionaries of different languages, correlating data from different domains, etc. We also introduce a novel privacy-preserving mechanism for social recommender systems, where users can receive accurate recommendations while hiding their profiles from an untrusted recommender server. For the second direction of this work, we focus on models for network growth, more specifically for network densification, by using a sampling process. The densification phenomenon has been recently observed in various real networks, and we argue that it can be explained simply through the way we observe (sample) the networks. We introduce a process of sampling the edges of a fixed graph, which results in the super-linear growth of edges versus nodes and the increase of the average degree as the network evolves.

Locating the Source of Diffusion in Large-Scale Networks
P. Pinto, P. Thiran and M. Vetterli
Physical Review Letters, vol. 109, no. 6, 068702, 2012.
[full text] [view at publisher]

How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks---such as the Internet or the human social graph---it is usually infeasible to observe the state of all nodes in a network. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely-placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe efficient implementations with complexity O(N^{\alpha}) , where \alpha=1 for arbitrary trees, and \alpha=3 for arbitrary graphs. In the context of several case studies, we determine how localization accuracy is affected by various system parameters, including the structure of the network, the density of observers, and the number of observed cascades.

Content Management in Mobile Wireless Networks
F. De Meneses Neves Ramos Dos Santos
2012.

Approximately one billion users have access to mobile broadband, through which they intend to obtain the same data they can reach using a wired connection. Because of the cost of transmitting data over a mobile-broadband connection and given that 3G networks are quickly reaching their data-transfer capacity, some researchers envision the inter-connection of mobile devices using Wi-Fi, forming a challenged network. Such networks suffer from high latency, low data rates, and frequent disconnections; because end to end paths between pairs of nodes may not always exist, a mobile device must store content before delivering it to the intended receivers. We designed the content-optimal delivery algorithm (CODA) for distributing named data over a delay-tolerant network (DTN), which is a network of challenged networks. Current content-dissemination techniques for DTNs consist mainly of the following items: a content store, for caching and indexing retrieved content, and a query and response mechanism to search the network for matching content. Some algorithms attempt to optimize an objective function, such as the total delivery-delay. While disseminating content, CODA maximizes the network throughput by computing the utility of each item published: a device with a full buffer drops content in order of increasing utility and transmits content in order de- creasing utility. We implemented CODA over the CCNx protocol, which provides the basic tools for querying, caching, and transmitting content.

Been There, Done That: What Your Mobility Traces Reveal about Your Behavior
V. Etter, M. Kafsi and E. Kazemi
Mobile Data Challenge by Nokia Workshop, in conjunction with Int. Conf. on Pervasive Computing, Newcastle, UK, June 18-19, 2012.

Mobility is a central aspect of our life; the locations we visit reflect our tastes and lifestyle and shape our social relationships. The ability to foresee the places a user will visit is therefore beneficial to numerous applications, ranging from forecasting the dynamics of crowds to improving the relevance of location-based recommendations. To solve the Next Place Prediction task of the Nokia Mobile Data Challenge, we developed several mobility predictors, based on graphical models, neural networks, and decision trees, and explain some of the challenges that we faced. Then, we combine these predictors using different blending strategies, which improve the prediction accuracy over any individual predictor.

Practical Network Tomography
D. G. Ghita
2012.
[full text] [view at publisher]

In this thesis, we investigate methods for the practical and accurate localization of Internet performance problems. The methods we propose belong to the field of network loss tomography, that is, they infer the loss characteristics of links from end-to-end measurements. The existing versions of the problem of network loss tomography are ill-posed, hence, tomographic algorithms that attempt to solve them resort to making various assumptions, and as these assumptions do not usually hold in practice, the information provided by the algorithms might be inaccurate. We argue, therefore, for tomographic algorithms that work under weak, realistic assumptions. We first propose an algorithm that infers the loss rates of network links from end-to-end measurements. Inspired by previous work, we design an algorithm that gains initial information about the network by computing the variances of links' loss rates and by using these variances as an indication of the congestion level of links, i.e., the more congested the link, the higher the variance of its loss rate. Its novelty lies in the way it uses this information – to identify and characterize the maximum set of links whose loss rates can be accurately inferred from end-to-end measurements. We show that our algorithm performs significantly better than the existing alternatives, and that this advantage increases with the number of congested links in the network. Furthermore, we validate its performance by using an "Internet tomographer" that runs on a real testbed. Second, we show that it is feasible to perform network loss tomography in the presence of "link correlations," i.e., when the losses that occur on one link might depend on the losses that occur on other links in the network. More precisely, we formally derive the necessary and sufficient condition under which the probability that each set of links is congested is statistically identifiable from end-to-end measurements even in the presence of link correlations. In doing so, we challenge one of the popular assumptions in network loss tomography, specifically, the assumption that all links are independent. The model we propose assumes we know which links are most likely to be correlated, but it does not assume any knowledge about the nature or the degree of their correlations. In practice, we consider that all links in the same local area network or the same administrative domain are potentially correlated, because they could be sharing physical links, network equipment, or even management processes. Finally, we design a practical algorithm that solves "Congestion Probability Inference" even in the presence of link correlations, i.e., it infers the probability that each set of links is congested even when the losses that occur on one link might depend on the losses that occur on other links in the network. We model Congestion Probability Inference as a system of linear equations where each equation corresponds to a set of paths. Because it is infeasible to consider an equation for each set of paths in the network, our algorithm finds the maximum number of linearly independent equations by selecting particular sets of paths based on our theoretical results. On the one hand, the information provided by our algorithm is less than that provided by the existing alternatives that infer either the loss rates or the congestion statuses of links, i.e., we only learn how often each set of links is congested, as opposed to how many packets were lost at each link, or to which particular links were congested when. On the other hand, this information is more useful in practice because our algorithm works under assumptions weaker than those required by the existing alternatives, and we experimentally show that it is accurate under challenging network conditions such as non-stationary network dynamics and sparse topologies.

2011

Towards Unbiased BFS Sampling
M. Kurant, A. Markopoulou and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. 29, 1799 - 1809, 2011.
[view at publisher]

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify and correct the degree bias of BFS.

Inference Algorithms Analysis
D. Ghita
2011.

Shifting Network Tomography Toward A Practical Goal
D. Ghita, C. Karakus, K. Argyraki and P. Thiran
ACM International Conference on emerging Networking EXperiments and Technologies (CoNext), Tokyo, Japan, December 6–9, 2011.
[view at publisher]

Boolean Inference makes it possible to observe the congestion status of end-to-end paths and infer, from that, the congestion status of individual network links. In principle, this can be a powerful monitoring tool, in scenarios where we want to monitor a network without having direct access to its links. We consider one such real scenario: a Tier-1 ISP operator wants to monitor the congestion status of its peers. We show that, in this scenario, Boolean Inference cannot be solved with enough accuracy to be useful; we do not attribute this to the limitations of particular algorithms, but to the fundamental difficulty of the Inference problem. Instead, we argue that the "right" problem to solve, in this context, is compute the probability that each set of links is congested (as opposed to try to infer which particular links were congested when). Even though solving this problem yields less information than provided by Boolean Inference, we show that this information is more useful in practice, because it can be obtained accurately under weaker assumptions than typically required by Inference algorithms and more challenging network conditions (link correlations, non-stationary network dynamics, sparse topologies).

Use of Learned Dictionaries in Tomographic Reconstruction
V. Etter, I. Jovanovic and M. Vetterli
SPIE Conference Wavelets and Sparsity XIV, San Diego, California, USA, August 21-25, 2011.
[view at publisher]

We study the use and impact of a dictionary in a tomographic reconstruction setup. First, we build two different dictionaries: one using a set of bases functions (Discrete Cosine Transform), and the other that is learned using patches extracted from training images, similar to the image that we would like to reconstruct. We use K-SVD as the learning algorithm. These dictionaries being local, we convert them to global dictionaries, ready to be applied on whole images, by generating all possible shifts of each atom across the image. During the reconstruction, we minimize the reconstruction error by performing a gradient descent on the image representation in the dictionary space. Our experiments show promising results, allowing to eliminate standard artifacts in the tomographic reconstruction, and to reduce the number of measurements required for the inversion. However, the quality of the results depends on the convergence of the learning process, and on the parameters of the dictionaries (number of atoms, convergence criterion, atom size, etc.). The exact influence of each of these remains to be studied.

Population Size Estimation Using a Few Individuals as Agents
F. Movahedi Naini, O. Dousse, P. Thiran and M. Vetterli
IEEE International Symposium on Information Theory (ISIT), Saint-Petersburg, Russia, July 31 - August 5, 2011.
[full text] [view at publisher]

We conduct an experiment where ten attendees of an open-air music festival are acting as Bluetooth probes. We then construct a parametric statistical model to estimate the total number of visible Bluetooth devices in the festival area. By comparing our estimate with ground truth information provided by probes at the entrances of the festival, we show that the total population can be estimated with a surprisingly low error (1.26% in our experiment), given the small number of agents compared to the area of the festival and the fact that they are regular attendees who move randomly. Also, our statistical model can easily be adapted to obtain more detailed estimates, such as the evolution of the population size over time.

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol
J. Herzen, C. Westphal and P. Thiran
IEEE ICNP, Vancouver, Canada, October 17-20, 2011.
[full text] [view at publisher]

We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a space of concise dimensionality, which enables greedy routing based only on local knowledge. PIE is a general routing scheme, meaning that it works on any graph. We focus however on the Internet, where routing scalability is an urgent concern. We show analytically and by using simulation that the scheme scales extremely well on Internet-like graphs. In addition, its geometric nature allows it to react efficiently to topological changes or failures by finding new paths in the network at no cost, yielding better delivery ratios than standard algorithms. The proposed routing scheme needs an amount of memory polylogarithmic in the size of the network and requires only local communication between the nodes. Although each node constructs its coordinates and routes packets locally, the path stretch remains extremely low, even lower than for centralized or less scalable state-of-the-art algorithms: PIE always finds short paths and often enough finds the shortest paths.

Computational Criminology
V. Etter
2011.

In this report, we present our work done in spring 2011 on the UK crimes dataset. This dataset was first released in December 2010, and contains reports of crimes committed in England and Wales, with their type and location. We first perform some exploratory analysis on this data, by looking at the correlation of crime rates with some independent variables, such as the population density or the unemployment rate, as well as the relationship between different types of crimes. We also study the spatial autocorrelation of the crime rates. Then, we define a classification problem in which we are interested in identifying probable criminals from mobility traces and aggregated crimes reports. We first introduce a basic algorithm to try and solve this problem, and then reformulate our model to fit a probabilistic group testing setup.

A Measurement-Based Algorithm to Maximize the Utility of Wireless Networks
J. Herzen, A. Aziz, R. Merz, S. Shneer and P. Thiran
ACM S3 2011, Las Vegas, Nevada, USA, September 19, 2011.
[view at publisher]

The goal of jointly providing fairness and efficiency in wireless networks can be seen as the problem of maximizing a given utility function. The main difficulty when solving this problem is that the capacity region of wireless networks is typically unknown and time-varying, which prevents the usage of traditional optimization tools. As a result, scheduling and congestion control algorithms are either too conservative because they under-estimate the capacity region, or suffer from congestion collapse because they over-estimate it. We propose a new adaptive congestion control algorithm, called Enhance & Explore (E&E). It maximizes the utility of the network without requiring any explicit characterization of the capacity region. E&E works above the MAC layer and is decoupled from the underlying scheduling mechanism. It provably converges to a state of optimal utility. We evaluate the performance of the algorithm in a WLAN setting, using both simulations and measurements on a real testbed composed of IEEE 802.11 wireless routers.

The Distributed Multiple Voting Problem
F. Bénézit, P. Thiran and M. Vetterli
IEEE Journal of Selected Topics in Signal Processing, vol. 5, no. 4, 791 - 804, 2011.
[view at publisher]

A networked set of agents holding binary opinions does not seem to be able to compute its majority opinion by means of local binary interactions only. However, the majority problem can be solved using two or more bits, instead of one [1]. Pairs of agents asynchronously exchange their states and update them according to a voting automaton. This paper presents binary voting automata as well as solutions to the multiple voting problem, where agents can vote for one candidate among |C| >= 2 candidates and need to determine the majority vote. The voting automata are derived from the pairwise gossip algorithm, which computes averages. In the binary case (|C| = 2), we focus on averages in dimension 1, but in the multiple case (|C| >= 2) we quantize gossip in dimension |C | - 1, which is larger than or equal to 1. We show in particular that a consensus on majority can be reached using 15 possible states (4 bits) for the ternary voting problem, and using 100 possible states (7 bits) for the quaternary voting problem.

Rethinking Boolean Network Tomography
D. Ghita
2011.

Boolean Inference makes it possible to observe the congestion status of end-to-end paths and infer, from that, the congestion status of individual network links. In principle, this can be a powerful monitoring tool, in scenarios where we want to monitor a network without having direct access to its links. We consider one such real scenario: a Tier-1 ISP operator wants to monitor the congestion status of its peers. We show that, in this scenario, Boolean Inference cannot be solved with enough accuracy to be useful; we do not attribute this to the limitations of particular algorithms, but to the fundamental difficulty of the Inference problem. Instead, we argue that the ``right'' problem to solve, in this context, is compute the probability that each set of links is congested (as opposed to try to infer which particular links were congested when). Even though solving this problem yields less information than provided by Boolean Inference, we show that this information is more useful in practice, because it can be obtained accurately under weaker assumptions than typically required by Inference algorithms and more challenging network conditions (link correlations, non-stationary network dynamics, sparse topologies).

On the Privacy of Anonymized Networks
P. Pedarsani and M. Grossglauser
17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD-2011), San Diego, CA, USA, August 21-24, 2011.
[view at publisher]

The proliferation of online social networks, and the concomitant accumulation of user data, give rise to hotly debated issues of privacy, security, and control. One specific challenge is the sharing or public release of anonymized data without accidentally leaking personally identifiable information (PII). Unfortunately, it is often difficult to ascertain that sophisticated statistical techniques, potentially employing additional external data sources, are unable to break anonymity. In this paper, we consider an instance of this problem, where the object of interest is the structure of a social network, i.e., a graph describing users and their links. Recent work demonstrates that anonymizing node identities may not be sufficient to keep the network private: the availability of node and link data from another domain, which is correlated with the anonymized network, has been used to re-identify the anonymized nodes. This paper is about conditions under which such a de-anonymization process is possible. We attempt to shed light on the following question: can we assume that a sufficiently sparse network is inherently anonymous, in the sense that even with unlimited computational power, deanonymization is impossible? Our approach is to introduce a random graph model for a version of the de-anonymization problem, which is parameterized by the expected node degree and a similarity parameter that controls the correlation between two graphs over the same vertex set. We find simple conditions on these parameters delineating the boundary of privacy, and show that the mean node degree need only grow slightly faster than log n with network size n for nodes to be identifiable. Our results have policy implications for sharing of anonymized network information.

Models of 802.11 Multi-Hop Networks: Theoretical Insights and Experimental Validation
A. Aziz, M. Durvy, O. Dousse and P. Thiran
COMSNETS 2011, Bangalore, India, January 4-8, 2011.
[full text] [view at publisher]

Wireless Multi-Hop CSMA/CA Networks are challenging to analyze. On the one hand, their dynamics are complex and rather subtle effects may severely affect their performance. Yet, understanding these effects is critical to operate upper layer protocols, such as TCP/IP. On the other hand, their models tend to be very complex in order to reproduce all the features of the protocol. As a result, they do not convey much insight into the essential features. We review two models of 802.11 protocols, which are simple enough to first explain why a trade-off needs to be found between fairness and spatial reuse (throughput) in saturated wireless networks (where all nodes have packets to transmit to their neighbors); and then to explain why non-saturated networks (where only some nodes, the sources, have packets to transmit to their destinations in a multi-hop fashion) that are more than 3 hops longs suffer from instability. We confront both models either to realistic simulations in ns-2 or to experiments with a testbed deployed at EPFL. We find that the predictions of both models help us understand the performance of the 802.11 protocol, and provide hints about the changes that need to be brought to the protocol.

Bringing Stability to Wireless Mesh Networks
A. Aziz
2011.
[full text] [view at publisher]

Wireless mesh networks were designed as a mean to rapidly deliver large-scale communication capabilities without the support of any prior infrastructure. Among the different properties of mesh networks, the self-organizing feature is particularly interesting for developing countries or for emergency situations. However, these benefits also bring new challenges. For example, the scheduling decision needs to be performed in a distributed manner at each node of the network. Toward this goal, most of the current mesh deployments are based on the IEEE 802.11 protocol, even if it was not designed for multi-hop communications. The main goals of this thesis are (i) to understand and model the behavior of IEEE 802.11-based mesh networks and more specifically the root causes that lead to congestion and network instability; (ii) to develop an experimental infrastructure in order to validate with measurements both the problems and the solutions discussed in this thesis; (iii) to build efficient hop-by-hop scheduling schemes that provide congestion control and inter-flow fairness in a practical way and that are backward-compatible with the current protocol; and (iv) to explain the non-monotonic relation between the end-to-end throughput and the source rate and to introduce a model to derive the rationale behind this artifact. First, we propose a Markovian model and we introduce the notion of stealing effect to explain the root causes behind the 3-hop stability boundary, where linear networks up to 3 hops are stable, and larger topologies are intrinsically unstable. We validate our analytical results both through simulations and through measurements on a small testbed deployment. Second, to support the experimental research presented in this thesis, we design and deploy a large-scale mesh network testbed on the EPFL campus. We plan our architecture to be as flexible as possible in order to support a wide range of other research areas such as IEEE 802.11 indoor localization and opportunistic routing. Third, we introduce EZ-flow, a novel hop-by-hop congestion-control mechanism that operates at the Medium Access Control layer. EZ-flow is fully backward-compatible with the existing IEEE 802.11 deployments and it works without any form of message passing. To perform its task EZ-flow takes advantage of the broadcast nature of the wireless medium in order to passively derive the queue size at the next-hop node. This information is then used by each node to adapt accordingly its channel access probability, through the contention window parameter of IEEE 802.11. After detailing the different components of EZ-flow, we analyze its performance analytically, through simulations and real measurements. Fourth, we show that hop-by-hop congestion-control can be efficiently performed at the network layer in order to not abuse the contention mechanism of IEEE 802.11. Additionally, we introduce a complete framework that jointly achieves congestion-control and fairness without requiring a prior knowledge of the network capacity region. To achieve the fairness part, we propose the Explore & Enhance algorithm that finds a fair and achievable rate allocation vector that maximizes a desired function of utility. We show experimentally that this algorithm reaches its objective by alternating between exploration phases (to discover the capacity region) and enhancement phases (to improve the utility through a gradient ascent). Finally, we note that, as opposed to wired networks, the multi-hop wireless capacity is usually unknown and time-varying. Therefore, we study how the end-to-end throughput evolves as a function of the source rate when operating both below and above the network capacity. We note that this evolution follows a non-monotonic curve and we explain, through an analytical model and simulations, the rationale behind the different transition points of this curve. Following our analysis, we show that no end-to-end congestion control can be throughput-optimal if it operates directly over IEEE 802.11. Hence, this supports the methodology of performing congestion control in a hop-by-hop manner. After validating experimentally the non-monotonicity, we compare through simulations different state-of-the-art scheduling schemes and we highlight the important tradeoff that exists in congestion-control schemes between efficiency (i.e., throughput-optimality) and robustness (i.e., no throughput collapse when the sources attempt to operate at a rate above the network capacity).

Understanding and Tackling the Root Causes of Instability in Wireless Mesh Networks
A. Aziz, P. Thiran and D. Starobinski
IEEE/ACM Transactions on Networking, vol. 19, no. 4, 1178 - 1193, 2011.
[view at publisher]

We investigate, both theoretically and experimentally, the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called “stealing effect”, a consequence of the hidden node problem and non-zero transmission delays. We consider the case of a greedy source and prove, by using Foster’s theorem, that 3-hop networks are stable, but only if the stealing effect is accounted for. We also prove that 4-hop networks are, on the contrary, always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and non-linear topologies. To tackle this instability problem, we propose and evaluate a novel, distributed flow-control mechanism, called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-theshelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a 9-node testbed deployed over 4 different buildings, show that EZ-flow effectively smoothes traffic and improves delay, throughput, and fairness performance.

Enhance & Explore: an Adaptive Algorithm to Maximize the Utility of Wireless Networks
A. Aziz, J. Herzen, R. Merz, V. Shneer and P. Thiran
ACM Mobicom, Las Vegas, USA, September 19-23, 2011.
[view at publisher]

The goal of jointly providing efficiency and fairness in wireless networks can be seen as the problem of maximizing a given utility function. In contrast with wired networks, the capacity of wireless networks is typically time-varying and not known explicitly. Hence, as the capacity region is impossible to know or measure exactly, existing scheduling schemes either under-estimate it and are too conservative, or they over-estimate it and suffer from congestion collapse. We propose a new adaptive algorithm, called Enhance & Explore (E&E). It maximizes the utility of the network without requiring any explicit characterization of the capacity region. E&E works above the MAC layer and it does not demand any modification to the existing networking stack. We first evaluate our algorithm theoretically and we prove that it converges to a state of optimal utility. We then evaluate the performance of the algorithm in a WLAN setting, using both simulations and real measurements on a testbed composed of IEEE 802.11 wireless routers. Finally, we investigate a wireless mesh network setting and we find that, when coupled with an efficient mechanism for congestion control, the E&E algorithm greatly increases the utility achieved by multi-hop networks as well.

2010

A Practical Hand-on Guide for Deploying a Large-scale Wireless Multi-hop Network
A. Aziz and J. Herzen
2010.

The knowledge of how to exactly deploy a wireless multi-hop network can be of interest for both researchers and engineers. Engineers may be interested in the possibility of extending the coverage area of their traditional access point and to provide ubiquitous Internet connectivity at a significantly reduced cost and some communities have already started to do so. Researchers need large-scale testbeds offering a certain level of flexibility in order to study the behavior of existing protocols, validate their analytical model and prototype their novel algorithms. Indeed, experimental validation is a key phase in order to transfer the academical knowledge from a lab to the real world and this requires the deployment of a testbed. As researcher working in between theory and practice, we needed to deploy such a testbed. Since the beginning our deployment in 2007 we faced many challenges until reaching the current status of our testbed today in 2010, mostly due to the fact that we could not find in the literature a complete hand-on guide of how to deploy such a network. In order to bridge this gap, we provide this technical report in order to share the know-how we acquire while building this 12 km2 testbed on the EPFL campus.

Order-Optimal Consensus Through Randomized Path Averaging
F. Bénézit, A. G. Dimakis, P. Thiran and M. Vetterli
IEEE Transactions on Information Theory, vol. 56, no. 10, 5150 - 5167, 2010.
[view at publisher]

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust mes- sage-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wire- less ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding ( O(n^2) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a n^1/2 factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional n^1/2 factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high prob- ability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algo- rithms operating over various graph topologies.

Understanding and Tackling the Root Causes of Instability in Wireless Mesh Networks: (extended version)
A. Aziz, D. Starobinski and P. Thiran
2010.

We investigate, both theoretically and experimentally, the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called "stealing effect", a consequence of the hidden node problem and non-zero transmission delays. We consider the case of a greedy source and prove, by using Foster's theorem, that 3-hop networks are stable, but only if the stealing effect is accounted for. We also prove that 4-hop networks are, on the contrary, always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and non-linear topologies. To tackle this instability problem, we propose and evaluate a novel, distributed flow-control mechanism, called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a 9-node testbed deployed over 4 different buildings, show that EZ-flow effectively smoothes traffic and improves delay, throughput, and fairness performance.

Network Tomography on Correlated Links
D. Ghita, K. Argyraki and P. Thiran
ACM Internet Measurement Conference (IMC), Melbourne, Australia, November 1-3, 2010.
[view at publisher]

Network tomography establishes linear relationships between the characteristics of individual links and those of end-to-end paths. It has been proved that these relationships can be used to infer the characteristics of links from end-to-end measurements, provided that links are not correlated, i.e., the status of one link is independent from the status of other links. In this paper, we consider the problem of identifying link characteristics from end-to-end measurements when links are "correlated," i.e., the status of one link may depend on the status of other links. There are several practical scenarios in which this can happen; for instance, if we know the network topology at the IP-link or at the domain-link level, then links from the same local-area network or the same administrative domain are potentially correlated, since they may be sharing physical links, network equipment, even management processes. We formally prove that, under certain well defined conditions, network tomography works when links are correlated, in particular, it is possible to identify the probability that each link is congested from end-to-end measurements. We also present a practical algorithm that computes these probabilities. We evaluate our algorithm through extensive simulations and show that it is accurate in a variety of realistic congestion scenarios.

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices
F. Bénézit, V. Blondel, P. Thiran, J. Tsitsiklis and M. Vetterli
IEEE International Symposium on Information Theory, Austin, Texas, USA, June 13-18, 2010.
[view at publisher]

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

Netscope: Practical Network Loss Tomography
D. Ghita, H. Nguyen, M. Kurant, K. Argyraki and P. Thiran
IEEE Conference on Computer Communications (INFOCOM), San Diego, CA, USA, March 15-19, 2010.
[view at publisher]

We present Netscope, a tomographic technique that infers the loss rates of network links from unicast end-to-end measurements. Netscope uses a novel combination of first- and second-order moments of end-to-end measurements to identify and characterize the links that cannot be (accurately) characterized through existing practical tomographic techniques. Using both analytical and experimental tools, we show that Netscope enables scalable, accurate link-loss inference: in a simulation scenario involving 4000 links, 20% of them lossy, Netscope correctly identifies 94% of the lossy links with a false positive rate of 16%—a significant improvement over the existing alternatives. Netscope is robust in the sense that it requires no parameter tuning, moreover its advantage over the alternatives widens when the number of lossy links increases. We also validate Netscope’s performance on an “Internet tomographer” that we deployed on an overlay of 400 PlanetLab nodes.

Self-Synchronizing Properties of CSMA Wireless Multi-hop Networks
K. Xu, O. Dousse and P. Thiran
ACM Sigmetrics, New York, June 14–18, 2010.
[view at publisher]

We show that CSMA is able to spontaneously synchronize transmissions in a wireless network with constant-size packets, and that this property can be used to devise efficient synchronized CSMA scheduling mechanisms without message passing. Using tools from queuing theory, we prove that for any connected wireless networks with arbitrary interference constraints, it is possible to implement self-synchronizing TDMA schedules without any explicit message passing or clock synchronization besides transmitting the original data packets, and the interaction can be fully local in that each node decides when to transmit next only by overhearing its neighbors’ transmissions. We also provide a necessary and sufficient condition on the emergence of self-synchronization for a given TDMA schedule, and prove that such conditions for self-synchronization can be checked in a finite number of steps for a finite network topology.

Demo Abstract of Net-Controller: a Network Visualization and Management Tool
J. Herzen, A. Aziz and P. Thiran
Infocom demo, San Diego, March 2010.

Net-Controller is a user-friendly network visualization and management tool developed at EPFL in order to easily retrieve and display in real time network statistics, such as link throughput and queue occupancy from a large testbed composed of wireless routers. Additionally, Net-Controller allows to control and modify the parameters of a complete network from a central point, and to easily generate traffic between different nodes. We intend to illustrate some of the features of Net-Controller through two examples that show how easily this tool detects and helps elucidate the throughput degradation that occurs in a wireless multi-hop network. The first example shows how and why fair queuing [6] improves performance compared to the standard FIFO policy used in off-the-shelf routers. The second example shows how and why a hop-by-hop congestion control mechanism, such as EZ-Flow [4] is needed to tackle the instability problem of a multi-hop scenario.

Collaborative Transportation Systems
M. Piorkowski
IEEE Wireless Communication and Networking Conference, Sydney, Australia, April 18-21.
[view at publisher]

We propose a new class of applications for Intelligent Transportation Systems (ITSs), called collaborative transportation applications that aim at solving transportation problems such as congestion and parking. Specifically, we define two applications: SmartPark and SmartRide that leverage shortrange wireless communication. We quantify the potential benefits these collaborative transportation applications can offer to an individual and to the public. To this extent, we conduct both the realistic simulations and the analysis of the performance of a taxi cab fleet from San Francisco. Our analysis shows that both collaborative transportation applications can provide with significant savings in travel times, fuel consumptions, etc. Finally, we discuss the functional requirements of collaborative transportation applications and we present the challenges that these applications are facing.

Collaborative routing in mobile partitioned networks
N. Sarafijanovic-Djukic
2010.
[full text] [view at publisher]

Embedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spatially heterogeneous node distributions, which may cause network partitions. In this thesis, we consider the problem of routing in mobile networks under such challenging conditions. More specifically, we endeavor to identify features of mobility common to different applications, in order to devise routing methods that are tailored to exploit these features. We explore two features in particular, (i) predictability and (ii) stable and heterogeneous spatial node distribution. A mobility process is predictable if the future location of a node can be well estimated, given knowledge of its current and past locations and possibly other statistics. We show how the performance of routing can be improved by explicitly incorporating mobility prediction. Specifically, we consider the performance of Last Encounter Routing (LER) under a simple synthetic random waypoint (RWP) mobility model. We extend the LER algorithm so that it takes into account predicted node trajectories when making routing decisions, and we show that this significantly improves its performance. A mobility process has a stable spatial node distribution if, informally, the node density remains the same over time, even though individual nodes are not constrained in space. This is a common feature of many mobility patterns because the spatial distribution is determined by the natural or constructed environment, regardless of the behavior of individual nodes. This typically leads to heterogeneous connectivity and to network partition, where highly connected clusters are interspersed with low-connectivity regions. We model such a situation with a set of stable concentration points (CPs) characterized by high node density, and with a mobility process that describes how nodes move between these islands of connectivity. We study two instances of this model: the G-model, where the CPs and the flow of nodes are abstracted as a graph, and the H-model, where nodes perform heterogeneous random walks on the plane. We exploit the presence of this stable CP topology in order to develop an efficient routing algorithm under these two mobility models. Our routing algorithm, Island Hopping (IH), exploits knowledge of the CP topology to make routing decisions. IH achieves a very good delay-throughput trade-off compared with several other existing routing algorithms, and it scales well with the network size. In many situations, it would be unrealistic to assume that CPs and the flows of mobile nodes among them are known a-priori. We develop methods, collectively called Collaborative Graph Discovery (COGRAD), that allow the nodes to discover the CP graph without any explicit signals from the environment (such as GPS coordinates or fixed beacons). We show that COGRAD can replace an oracle with knowledge of the CP topology after a sufficient warm-up period, allowing IH to operate even in scenarios without any cues from the environment.

Routing and search on large scale networks
D. Tschopp
2010.
[full text] [view at publisher]

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

2009

On the Fairness of Large CSMA Networks
M. Durvy, O. Dousse and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. 27, no. 7, 1093 - 1104, 2009.
[view at publisher]

We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, such as IEEE 802.11, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. This unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large one-dimensional networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In two-dimensional networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness.

Mobility-centric design of collaborative transportation systems
M. Piorkowski
2009.
[full text] [view at publisher]

Embedded sensors and actuators are revolutionizing the way we perceive and interact with the physical world. Current research on such Cyber-Physical Systems (CPSs) has focused mostly on distributed sensing and data gathering. The next step is to move from passive information extraction from the physical world towards an active framework where information is retrieved, processed, and acted upon in situ. As an example of such sensor-actuator systems that provide large-scale, distributed coordination, we consider Intelligent Transportation Systems (ITSs), with the goal of increasing travel safety and efficiency. The proliferation of wireless technologies enables different actors (e.g., pedestrians, motorists, traffic operators) to communicate with each other cheaply, efficiently, and securely. By embedding computational intelligence, communication and control into such ITSs, it will be possible to build collaborative transportation applications that help solve, for example, congestion and parking problems. This thesis explores the following question: To what extent is it possible to build distributed ITS systems that rely exclusively on local communication between nodes? The potential benefits of building such systems without infrastructure are numerous, including lower fixed and variable costs, avoiding regulatory hurdles, lower entry barriers for new players, and more control over privacy. On the other hand, self-organized ITSs without infrastructure have to operate under challenging conditions: large scale, high mobility, lack of end-to-end connectivity, ephemeral contacts between wireless nodes, and heterogeneous node capabilities. Although the networking research community has invested a significant effort in designing service abstractions that mimic traditional IP connectivity on top of wireless ad hoc networks, the ITS scenarios considered in this work are too challenging to implement such a service model. The main goal of this thesis is to design communication service models and their underlying protocols that can operate in collaborative transportation applications, and to demonstrate their effectiveness through analysis of traffic data and through realistic simulations. A key point is that the ITS applications we consider can rely on more limited service primitives, because they do not require a general any-to-any delivery service with strict performance guarantees. We first define the collaborative transportation applications of interest. Then we quantify their potential benefits and discuss their functional requirements. Next, we focus on the problem of the collection of large-scale mobility data. We propose a new method for collecting such data and introduce a novel mobility data mining framework, which is necessary to study collective mobility patterns in the context of wireless ad hoc networking. Relying on the analysis of real-life mobility traces, we find that despite the high node mobility, clusters of time-stable connectivity emerge and last at specific locations. Outside such clusters the connectivity between nodes remains sparse. This leads us to the proposal of a new mobility model that captures in an elegant way two phenomena observed in reality, i.e., emergence of stable clusters and network partitioning. This mobility model, called Heterogeneous Random Walk (HRW), appears to be the worst-case mobility model for many mobility-assisted protocols. Moreover, we show that the HRW mobility model predicts the performance of an epidemic dissemination protocol more accurately than other, similarly parsimonious models. Based on the lessons learned from the mobility data analysis, we propose a new abstraction that allows us to capture collective mobility patterns. This abstraction, called a Mobility Map, can be shared globally among mobile nodes and it can be used to improve communication in mobile partitioned networks (MPNs). Notably, we present a new geocasting protocol called GeoMobCast, which uses Mobility Maps to minimize message delay. This protocol is designed to provide the users of the collective transportation applications with the required communication service. Finally, we turn our attention on the real-life implementation of the distributed ITS that leverage short-range wireless communication. To this extent, we present the results of our experimental work with wireless sensor network technologies. We also present the necessary simulation toolbox designed to implement and evaluate collaborative transportation applications.

Distributed average consensus for wireless sensor networks
F. Bénézit
2009.
[full text] [view at publisher]

Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the energy consumption of each component, synchronizing the sensors, etc. In this thesis, we focus on the processing of the sensed data within the network itself. We study a specific network signal processing problem, called distributed average consensus. In this problem, the sensors, which are connected in a wireless network, need to know the average of all the measurements in the network. Instead of gathering the data at a central node, which would compute the average and broadcast it to the network, average consensus algorithms offer a distributed solution to the averaging problem. By local message passing and iterative local computations only, nodes can learn the average of the measurements. More precisely, in average consensus algorithms, nodes iteratively compute local weighted averages that conserve the global average of the estimates in the network. The estimates at each node contract until they all converge to the average. Many distributed average consensus algorithms were designed and the literature is vast. This thesis starts by classifying the existing algorithms. Then it describes a small number of useful techniques, which can handle the analysis of all the algorithms. Preexisting algorithms as well as algorithms that we designed are revisited with these unifying and simple techniques. In addition, the performance of the algorithms depends on the topology of the network, and a variety of networks are explored: simple graphs as circles or trees, lattices, random geometric graphs, complete graphs etc. Finally, an extension of average consensus to voting consensus is derived. In particular, we show that with two bits of memory at each node, a network can reach consensus in finite time on majority, when the initial measurements are binary. Distributed algorithms to compute majority with finite memory for ternary and quaternary signals are also given.

EZ-Flow: Removing Turbulence in IEEE 802.11 Wireless Mesh Networks without Message Passing
A. Aziz, D. Starobinski, P. Thiran and A. El Fawal
ACM CoNEXT 2009, Rome, December 1-4, 2009.
[view at publisher]

Recent analytical and experimental work demonstrate that IEEE 802.11-based wireless mesh networks are prone to turbulence. Manifestations of such turbulence take the form of large buffer build-up at relay nodes, end-to-end delay fluctuations, and traffic congestion. In this paper, we propose and evaluate a novel, distributed flow-control mechanism to address this problem, called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a 9-node testbed deployed over 4 different buildings, show that EZ-flow effectively smoothes traffic and improves delay, throughput, and fairness performance. We further corroborate these results with a mathematical stability analysis and extensive ns-2 simulations run for different traffic workloads and network topologies.

Sampling Urban Mobility through On-line Repositories of GPS Tracks
M. Piorkowski
The 1st ACM International Workshop on Hot Topics of Planet-scale Mobility Measurements, HotPlanet, Krakow, Poland, June 22, 2009.
[view at publisher]

We analyze urban mobility by relying on the short-term mobility traces gathered from a publicly available web-based repository of GPS tracks - the Nokia Sports Tracker service. All mobility traces are obtained from a set of kml files. We show how the data collected voluntarily by individuals, equipped with GPS-enabled mobile phones, can be used to infer accurate, large-scale footprint of urban mobility. This method, unlike others - for example, personal interviewing, is more scalable and less time consuming. It exploits the fact that the on-line masses are willing to share their experience with others. We present a set of heuristics used to filter out bogus tracks from the dataset. We show that the mobility patterns, inferred from the remaining, credible, short-term mobility traces have macroscopic characteristics similar to the characteristics of mobility patterns retrieved from the long-term mobility traces, gathered in different urban environments. The results of our analysis lead to a proposal for creating city-specific mobility profiles. We discuss how such profiles could help improve location privacy and help develop new context-aware applications and services for mobile users.

Elucidating the Instability of Random Access Wireless Mesh Networks
A. Aziz, D. Starobinski and P. Thiran
Sixth Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks - SECON 2009, Rome, June 22-26, 2009.
[view at publisher]

We investigate both theoretically and experimentally the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called “stealing effect”, a consequence of the hidden node problem and non-zero propagation delays. We consider the case of a greedy source and prove, by using Foster’s theorem, that 3-hop networks are stable, but only if the stealing effect is accounted for. On the other hand, we prove that 4-hop networks are always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and non-linear topologies. We devise a stabilization strategy that throttles the source and prove that there exists a finite, non-zero rate at which the source can transmit while keeping the system stable. We run real experiments on a testbed composed of IEEE 802.11 nodes, which show the contrasting behavior of 3-hop and 4-hop networks and the effectiveness of our stabilization strategy.

Aziala-net: Deploying a Scalable Multi-hop Wireless Testbed Platform for Research Purposes
A. Aziz, A. El Fawal, J. Le Boudec and P. Thiran
MobiHoc Sˆ3 2009, New Orleans, Louisiana, May 18, 2009.
[view at publisher]

Aziala-net is a flexible and scalable experimental testbed for wireless multi-hop networks based on simple off-the-shelf hardware that is able to adapt to various research purposes. It is composed of more than 50 Asus wireless routers that have been adapted to either work as fixed base station or as mobile nodes. After describing the technical details of Aziala-net, we illustrate the potential of the testbed by showing two samples of works that are currently under study in the testbed. The first example focus on the use of the IEEE 802.11 MAC layer protocol for multi-hop networks and the stability problem that it faces in the case of wireless mesh networks. The second example focus on epidemic forwarding protocols and their performance in a real testbed deployment.

Interval consensus: from quantized gossip to voting
F. Benezit, P. Thiran and M. Vetterli
ICASSP 2009, Taipei, Taiwan, April 19-24, 2009.
[view at publisher]

We design distributed and quantized average consensus algorithms on arbitrary connected networks. By construction, quantized algorithms cannot produce a real, analog average. Instead, our algorithm reaches consensus on the quantized interval that contains the average. We prove that this consensus in reached in finite time almost surely. As a byproduct of this convergence result, we show that the majority voting problem is solvable with only 2 bits of memory per agent.

Self-Organization Properties of CSMA/CA Systems and Their Consequences on Fairness
M. Durvy, O. Dousse and P. Thiran
IEEE Transactions on Information Theory, vol. 55, no. 3, 931 - 943, 2009.
[view at publisher]

Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the IEEE 802.11 protocol, are known to be unfair. In multihop networks, they can even favor some links to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood.We find that the capture effect and the relative values of the receive and carrier sensing ranges play a crucial role in the performance of these protocols. Using a simple Markovian model, we show that an idealized CSMA/CA protocol suffers from starvation when the receiving and sensing ranges are equal, but quite surprisingly that this unfairness is reduced or even disappears when these two ranges are sufficiently different. We also show that starvation has a positive counterpart, namely organization. When its access intensity is large the protocol organizes the transmissions in space in such a way that it maximizes the number of concurrent successful transmissions. We obtain exact formulae for the so-called spatial reuse of the protocol on large line networks.

A Parsimonious Model of Mobile Partitioned Networks with Clustering
M. Piorkowski, N. Sarafijanovoc-Djukic and M. Grossglauser
THE First International Conference on COMmunication Systems and NETworkS (COMSNETS), Bangalore, India, January 5-10, 2009.
[view at publisher]

Mobile wireless networks frequently possess, at the same time, both dense and sparse regions of connectivity; for example, due to a heterogeneous node distribution or radio propagation environment. This paper is about modeling both the mobility and the formation of clusters in such networks, where nodes are concentrated in clusters of dense connectivity, interspersed with sparse connectivity. Uniformly dense and sparse networks have been extensively studied in the past, but not much attention has been devoted to clustered networks. We present a new mobility model for clustered networks, which is important for the design and evaluation of routing protocols. We refer to our model as Heterogeneous Random Walk (HRW). This model is simple, mathematically tractable, and it captures the phenomenon of emerging clusters, observed in real partitioned networks. We provide a closed-form expression for the stationary distribution of node position and we give a method for “perfect simulation”. Moreover, we provide evidence, based on mobility traces, for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. In particular, we show that in some scenarios, nodes have statistically very similar mobility patterns. Also, we discuss cluster dynamics and the relationship between node speed and node density.

Robustness to failures in two-layer communication networks
M. Kurant
2009.
[full text] [view at publisher]

A close look at many existing systems reveals their two- or multi-layer nature, where a number of coexisting networks interact and depend on each other. For instance, in the Internet, any application-level graph (such as a peer-to-peer network) is mapped on the underlying IP network that, in turn, is mapped on a mesh of optical fibers. This layered view sheds new light on the tolerance to errors and attacks of many complex systems. What is observed at a single layer does not necessarily reflect well the state of the entire system. On the contrary, a tiny, seemingly harmless disruption of one layer, may destroy a substantial or essential part of another layer, thus making the whole system useless in practice. In this thesis we consider such two-layer systems. We model them by two graphs at two different layers, where the upper-layer (or logical) graph is mapped onto the lower-layer (physical) graph. Our main goals are the following. First, we study the robustness to failures of existing large-scale two-layer systems. This brings us some valuable insights into the problem, e.g., by identifying common weak points in such systems. Fortunately, these two-layer problems can often be effectively alleviated by a careful system design. Therefore, our second major goal is to propose new designs that increase the robustness of two-layer systems. This thesis is organized in three main parts, where we focus on different examples and aspects of the two-layer system. In the first part, we turn our attention to the existing large-scale two-layer systems, such as peer-to-peer networks, railway networks and the human brain. Our main goal is to study the vulnerability of these systems to random errors and targeted attacks. Our simulations show that (i) two-layer systems are much more vulnerable to errors and attacks than they appear from a single layer perspective, and (ii) attacks are much more harmful than errors, especially when the logical topology is heterogeneous. These results hold across all studied systems. A natural next step consists in improving the failure robustness of two-layer systems. In particular, in the second part of this thesis, we consider the IP/WDM optical networks, where an IP backbone network is mapped on a mesh of optical fibers. The problem lies in designing a survivable mapping, such that no single physical failure disconnects the logical topology. This is an NP-complete problem. We introduce a new concept of piecewise survivability, which makes the problem much easier in practice. This leads us to an efficient and scalable algorithm called SMART, which finds a survivable mapping much faster (often by orders of magnitude) than the other approaches proposed to date. Moreover, the formal analysis of SMART allows us to prove that a given survivable mapping does or does not exist. Finally, this approach helps us to find vulnerable areas in the system, and to effectively reinforce them, e.g., by adding new links. In the third part of this thesis, we shift our attention one layer higher, to the application-over-IP setting. In particular, we consider the design of Application-Level Multicast (ALM) for interactive applications, where a single source sends a delay-constrained data stream to a number of destinations. Interactive ALM should (i) respect stringent delay requirements, and (ii) proactively protect the system against overlay node failures and against (iii) the packet losses at the IP layer. We propose a two-layer-aware approach to this problem. First, we prove that the average packet loss rate observed at the destinations can be effectively approximated by a purely topological metric that, in turn, drops with the amount of IP-level and overlay-level path diversity available in the system. Therefore, we propose a framework that accommodates and generalizes various techniques to increase the path diversity in the system. Within this framework we optimize the structure of ALM. As a result, we reduce the effective loss rate of real Internet topologies by typically 30%-70%, compared to the state of the art. Finally, in addition to the three main parts of the thesis, we also present a set of results inspired by the study of ALM systems, but not directly related to the 'two-layer' paradigm (and thus moved to the Appendix). In particular, we consider a transmission of a delay-sensitive data stream from a single source to a single destination, where the data packets are protected by a Forward Error Correction (FEC) code and sent over multiple paths. We show that the performance of such a scheme can often be further improved. Our key observation is that the propagation times on the available paths often significantly differ, typically by 10-100ms. We propose to exploit these differences by appropriate packet scheduling, which results in a two- to five-fold improvement (reduction) in the effective loss rate.

2008

Trajectory sampling with unreliable reporting
N. Duffield and M. Grossglauser
IEEE/ACM Transactions On Networking, vol. 16, 37 - 50, 2008.
[view at publisher]

We define and evaluate methods to perform robust network monitoring using trajectory sampling in the presence of report loss. The first challenge is to reconstruct an unambiguous set of packet trajectories from the reports on sampled packets received at a collector. In this paper we extend the reporting paradigm of trajectory sampling to enable the elimination of ambiguous groups of reports, but without introducing bias into any characterization of traffic based on the surviving reports.

Routing in mobile wireless networks
D. Tschopp, S. Diggavi and M. Grossglauser
International Zurich Seminar on Communications, Zurich, SWITZERLAND, Mar 12-14, 2008.
[view at publisher]

Border effects, fairness, and phase transition in large wireless networks
M. Durvy, O. Dousse and P. Thiran
27th IEEE Conference on Computer Communications (INFOCOM 2008), Phoenix, AZ, Apr 15-17, 2008.
[view at publisher]

We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, such as IEEE 802.11, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. This unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel.

Balanced relay allocation on heterogeneous unstructured overlays
H. X. Nguyen, D. R. Figueiredo, M. Grossglauser and P. Thiran
27th IEEE Conference on Computer Communications (INFOCOM 2008), Phoenix, AZ, Apr 15-17, 2008.
[view at publisher]

Due to the increased usage of NAT boxes and firewalls, it has become harder for applications to establish direct connections seamlessly among two end-hosts. A recently, adopted proposal to mitigate this problem is to use relay nodes, end-hosts that act as intermediary points to bridge connections. Efficiently selecting a relay node is not a trivial problem, specially ill a large-scale unstructured overlay, system where end-hosts are heterogeneous.. In such environment, heterogeneity, among the relay nodes comes from the inherent differences in their capacities and from the way overlay networks are constructed. Despite this fact, good relay selection algorithms should effectively balance the aggregate load across the set of relay nodes. In this paper, we address this problem using algorithms based on the two, random choices method. We first prove that the classic load-based algorithm can effectively balance the load even when relays are heterogeneous, and that its performance depends directly on relay, heterogeneity. Second, we propose an utilization -based random choice algorithm to distribute load in order to balance relay, utilization. Numerical evaluations through simulations illustrate the effectiveness of this algorithm, indicating that it might also yield provable performance (which we conjecture). Finally, we support our theoretical findings through simulations of various large-scale scenarios, with realistic relay heterogeneity.

VANET Connectivity Analysis
M. Kafsi, P. Papadimitratos, O. Dousse, T. Alpcan and J. Hubaux
IEEE Workshop on Automotive Networking and Applications (Autonet), New Orleans, LA, USA, Dec. 2008.

Vehicular Ad Hoc Networks (VANETs) are a peculiar subclass of mobile ad hoc networks that raise a number of technical challenges, notably from the point of view of their mobility models. In this paper, we provide a thorough analysis of the connectivity of such networks by leveraging on wellknown results of percolation theory. By means of simulations, we study the influence of a number of parameters, including vehicle density, proportion of equipped vehicles, and radio communication range. We also study the influence of traffic lights and roadside units. Our results provide insights on the behavior of connectivity. We believe this paper to be a valuable framework to assess the feasibility and performance of future applications relying on vehicular connectivity in urban scenarios.

Densification Arising from Sampling Fixed Graphs
P. Pedarsani, D. Figueiredo and M. Grossglauser
ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Annapolis, MD, USA, June 2-6, 2008.
[view at publisher]

During the past decade, a number of different studies have identified several peculiar properties of networks that arise from a diverse universe, ranging from social to computer networks. A recently observed feature is known as network densification, which occurs when the number of edges grows much faster than the number of nodes, as the network evolves over time. This surprising phenomenon has been empirically validated in a variety of networks that emerge in the real world and mathematical models have been recently proposed to explain it. Leveraging on how real data is usually gathered and used, we propose a new model called Edge Sampling to explain how densification can arise. Our model is innovative, as we consider a fixed underlying graph and a process that discovers this graph by probabilistically sampling its edges. We show that this model possesses several interesting features, in particular, that edges and nodes discovered can exhibit densification. Moreover, when the node degree of the fixed underlying graph follows a heavy-tailed distribution, we show that the Edge Sampling model can yield power law densification, establishing an approximate relationship between the degree exponent and the densification exponent. The theoretical findings are supported by numerical evaluations of the model. Finally, we apply our model to real network data to evaluate its performance on capturing the previously observed densification. Our results indicate that edge sampling is indeed a plausible alternative explanation for the densification phenomenon that has been recently observed.

Mobility-Centric Geocasting For Mobile Partitioned Networks
M. Piorkowski
The 16th IEEE International Conference on Network Protocols, Orlando, Florida, USA, October 19-22, 2008.
[full text] [view at publisher]

We describe our design of a geocast service for mobile partitioned networks (MPNs). We focus mainly on minimizing the delivery latency. Our approach exploits the time-stability of the collective mobility pattern. In MPNs, in contrast to MANETs, the end-to-end path is frequently not available. Thus, communication in such networks becomes problematic. To overcome this difficulty, researchers propose a solution in which the node’s mobility is exploited. This paradigm is often called mobility-assisted forwarding. In order to design routing protocols for MPNs, researchers study key mobility metrics, for example the inter-contact times between nodes. Based on the analysis of a real-life mobility trace, we show that the inter-contact time distribution is spatially dependent. This is a result of spatially heterogeneous mobility pattern that appears to be stable in time. We demonstrate that any georouting protocol designed to work in MPNs can benefit from knowing such an underlying mobility pattern. We propose an abstraction called mobility map that represents the collective mobility pattern. We also present how mobility maps can be used for georouting in MPNs and we also show a simple mechanism for the collaborative discovery of mobility maps. Finally, we propose a geocast protocol for MPNs - GeoMobCast - that explicitly uses mobility maps and is designed to minimize the expected message delay while maximizing the message delivery. We empirically evaluate the protocol by using simulations and we observe the improved performance, compared to other approaches.

Which Distributed Averaging Algorithm Should I Choose for my Sensor Network?
P. Denantes, F. Benezit, P. Thiran and M. Vetterli
IEEE INFOCOM 2008, Phoenix, AZ, 13-18 April 2008.
[view at publisher]

Average consensus and gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. Inspired by heat diffusion, they compute the average of sensor networks measurements by iterating local averages until a desired level of convergence. Confronted with the diversity of these algorithms, the engineer may be puzzled in his choice for one of them. As an answer to his/her need, we develop precise mathematical metrics, easy to use in practice, to characterize the convergence speed and the cost (time, message passing, energy...) of each of the algorithms. In contrast to other works focusing on time-invariant scenarios, we evaluate these metrics for ergodic time- varying networks. Our study is based on Oseledec’s theorem, which gives an almost-sure description of the convergence speed of the algorithms of interest. We further provide upper bounds on the convergence speed. Finally, we use these tools to make some experimental observations illustrating the behavior of the convergence speed with respect to network topology and reliability in both average consensus and gossip algorithms.

On Clustering Phenomenon in Mobile Partitioned Networks
M. Piorkowski, N. Sarafijanovic-Djukic and M. Grossglauser
The First ACM SIGMOBILE International Workshop on Mobility Models for Networking Research, Hong Kong SAR, China, 26 May.
[full text] [view at publisher]

According to different kinds of connectivity, we can distinguish three types of mobile ad-hoc networks: dense, sparse and clustered networks. This paper is about modeling mobility in clustered networks, where nodes are concentrated into clusters of dense connectivity, and in between there exists sparse connectivity. The dense and sparse networks are extensively studied and modeled, but not much attention is paid to the clustered networks. In the sparse and clustered networks, an inherently important aspect is the mobility model, both for the design and evaluation of routing protocols. We propose a new mobility model for clustered networks, called Heterogeneous Random Walk. This model is simple, mathematically tractable and most importantly it captures the phenomenon of emerging clusters, observed in real partitioned networks, in an elegant way. We provide a closed-form expression for the stationary distribution of node position and we give a recipe for the "perfect simulation". Moreover, based on the real mobility trace we provide strong evidence for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. For the very first time in the literature we show evidence for the correlation between the spatial speed distribution and the cluster formation. We also present the results of the analysis of real cluster dynamics caused by nodes' mobility.

Effect of 802.11 Adaptive Exponential Backoffs on the Fluidity of Downlink Flows in Mesh Networks
A. Aziz, R. Karrer and P. Thiran
WinMee 2008, Berlin, March 31 2008.

Efficient multihop traffic management is a need for successful Wireless Mesh Networks (WMNs) deployment. Using an analogy with fluid mechanism, we classify a flow as laminar if the packets flow smoothly from the Wired Access Point (WAP) over the mesh network, and as turbulent otherwise. We identify a particular but frequent collision scenario, which sets the flow to be turbulent, resulting in a strongly reduced downlink end-to-end throughput. We show that the exponential backoff mechanism in an 802.11WMN is responsible for this problem and suggest a modification of the current exponential backoff policy of 802.11 for WMNs. We support these findings both with simulations and real measurements on a testbed infrastructure.

Model validation through experimental testbed: the fluid flow behavior example
A. Aziz, T. Huehn, R. Karrer and P. Thiran
Tridentcom 2008, Innsbruck, Austria, March 18-20.

This testbed practice paper presents our efforts to validate an analytical model for fluid flow behavior in wireless mesh networks with an experimental evaluation. We have developed a fluid model for multihop communication in wireless mesh networks and analyzed it with simulations. Now, we describe our efforts to reproduce the modeled and simulated network with an indoorWiFi mesh network and to measure flow parameters that allow us to verify that the underlying assumptions and the flow behavior can be matched in real networks. Our experiences emphasize the need to gap the bridge between simulations and experimental validation as well as the lack of tools to efficiently validate results. These findings are particularly true in wireless mesh networks where interference is beyond the control of the experiment and where nodes are distributed such that an easy coordination and monitoring of the nodes is not possible.

User-level Internet tomography and overlay routing
X. H. Nguyen
2008.
[full text] [view at publisher]

In this thesis, we study methods to detect, localize and overcome performance problems experienced by end-users in communication networks. These problems are extremely difficult to solve when the only available information are end-to-end data. We first consider the simple problem of identifying poorly performing links in a network. Even though end-to-end data do not provide sufficient information to calculate link loss rates exactly, we show that in many settings they provide enough information to identify the lossy links. We introduce an inference technique based on the maximum likelihood inference principle, which handles well noisy measurements and routing changes. We apply our technique to locate lossy links in sensor networks. Compared to wired networks, sensor networks pose two additional challenges for monitoring functions: they support much less probing traffic, and they change their routing topologies much more frequently. A Boolean performance model that requires a small number of probes is therefore particularly suited to sensor networks. We evaluate the performance of our inference algorithm in simulation and on real-network traces. We find that the proposed technique achieves high detection and low false positive rates. In IP networks where the network topology is stable and the number of end-to-end probes is large, we consider a second approach to the Boolean tomography problem where we take multiple measurements of the network to learn the probability that a link is going to be congested. We show that these probabilities can be uniquely identified from a small set of measurements by using properties of Boolean algebra. We can then use the learnt probabilities as priors to find rapidly the congested links at any time, with an order-of-magnitude gain in accuracy over existing algorithms. We validate our results both by simulation and real implementation in the PlanetLab network. Taking multiple snapshots of the network also allows us to calculate link loss rates from end-to-end measurements exactly. This operation is possible despite that the system of equations relating link loss rates with end-to-end loss rates has multiple solutions. The main reasons are that losses due to congestion occur in bursts, hence the loss rates of congested links have high variances. On the contrary, most links on the Internet are un-congested, hence the averages and variances of their loss rates are virtually zero. We first prove that the variances of link loss rates can be uniquely calculated from the covariances of the measured end-to-end loss rates in any realistic topology. After calculating the link variances, we remove the un-congested links with small variances from the first-order moment equations in order to obtain a full-rank linear system of equations, from which we can calculate precisely the loss rates of the remaining congested links. Our proposed solution uses only regular unicast probes and thus is applicable in today's Internet. It is accurate and scalable, as shown in our simulations and experiments on PlanetLab. After locating the performance bottlenecks, we study methods that mitigate these performance problems using relay nodes, end-hosts that act as intermediary points to bridge connections. Efficiently selecting a relay node is not a trivial problem, especially in a large-scale unstructured overlay system where end-hosts are heterogeneous and do not have the full knowledge of all available relays. Despite these facts, good relay selection algorithms should effectively balance the aggregate load across the set of relay nodes. We address these problems using algorithms based on the two random choices method. In the presence of the relay heterogeneity, we first prove that the classic load-based algorithm can effectively balance the load, even when relays are heterogeneous, and that its performance depends directly on relay heterogeneity. Second, we propose an utilization-based random choice algorithm to distribute load in order to balance relay utilization. Numerical evaluations through simulations illustrate the effectiveness of this algorithm, indicating that it might also yield provable performance (which we conjecture). Finally, we support our theoretical findings through simulations of various large-scale scenarios, with realistic relay heterogeneity. When end-hosts have only a limited knowledge of available relays, we prove that even if each end-host knows only a small fraction of the number of relays, the two-random-choice algorithm still guarantees good load balancing performance. However, when the number of known relays for each end-host does not grow fast enough with the total number of relays, a modified two-choice algorithm is needed to guarantee good load balancing. This algorithm consists in first selecting two relay sets and then sampling two relays, one from each of them.

TraNS: Realistic Joint Traffic and Network Simulator for VANETs
M. Piorkowski, M. Raya, A. Lugo, P. Papadimitratos, M. Grossglauser and J. Hubaux
ACM SIGMOBILE Mobile Computing and Communications Review, vol. 12, no. 1, 31 - , 2008.
[view at publisher]

Realistic simulation is a necessary tool for the proper evaluation of newly developed protocols for Vehicular Ad Hoc Networks (VANETs). Several recent efforts focus on achieving this goal. Yet, to this date, none of the proposed solutions fulfill all the requirements of the VANET environment. This is so mainly because road traffic and communication network simulators evolve in disjoint research communities. We are developing TraNS, an open-source simulation environment, as a step towards bridging this gap. This short paper describes the TraNS architecture and our ongoing development efforts.

2007

Gossip along the way: order-optimal consensus through randomized path averaging
F. Benezit, A. Dimakis, P. Thiran and M. Vetterli
Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing, University of Illinois at Urbana-Champaign, September 26-28, 2007.

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. However for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges very slowly. A recently proposed algorithm called geographic gossip improves gossip efficiency by a $\sqrt{n / \log n}$ factor for random geometric graphs, by exploiting geographic information of node locations. In this paper we prove that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional $\sqrt{n / \log n}$ factor and is order optimal for grids and random geometric graphs. Our analysis provides some general techniques and can be used to provide bounds on the performance of randomized message passing algorithms operating over various graph topologies.

Performance of Averaging Algorithms in Time-Varying Networks
P. Denantes
2007.

We study averaging algorithms in time-varying networks, and means tomeasure their performance. We present sufficient conditions on these algorithms, which ensure they lead to computation at each node, of the global average of measurements provided by each node in the network. Further, we present and use results from ergodic theory to define an accurate performance metric for averaging algorithms. This metric, the contraction coefficient, differs from previously used metrics such as the second largest eigenvalue of the expected weighting matrix, which gives an approximation of the real convergence rate only in some special cases which are hard to specify. On the other hand, the contraction coefficient as set forth herein characterizes exactly the actual asymptotic convergence rate of the system. Additionally, it may be bounded by a very concise formula, and simulations show that this bound is, at least in all studied cases, reasonably tight so as to be used as an approximation to the actual contraction coefficient. Finally, we provide a few results and observations which make use of the derived tools. These observations may be used to find new optima for design parameters of some averaging algorithms, and also open the door to new problems in the study of the underlying mathematical models.

Promiting Fluidity in the Flow of Packets of 802.11 Wireless Mesh Networks
A. Aziz, R. Karrer and P. Thiran
CoNEXT'07, New York, December 10-13 2007.

Wireless Mesh Networks (WMNs) are based on packet forwarding and therefore require efficient multi-hop protocols for their deployment. Toward this objective, we study the flow of packets through the network and using an analogy with fluid physics we classify them as being either laminar in the case of a smooth propagation or turbulent otherwise. Following this terminology, we present the tendency of current 802.11 to generate turbulent flows, i.e. to queue packets at the intermediate nodes for a non-deterministic time. However numerous applications such as VoIP, TCP and streaming are very delay sensitive and therefore laminar behavior is desirable. We model existing 802.11 multi-hop networks and identify the exponential backoff policy as a main parameter in the transition between laminar and turbulent behavior.

TraNS: Joint Traffic and Network Simulator for VANETs
M. Piorkowski, M. Raya, A. Lugo, P. Papadimitratos, M. Grossglauser and J. Hubaux
MobiCom 2007, Montreal, Canada, 9-14, September, 2007.

Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction
M. Kurant and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. 25, no. 5, 922 - 933, 2007.
[view at publisher]

Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called survivable. Finding a survivable mapping is known to be NP-complete, making it impossible in practice to assess the existence or absence of such a mapping for large networks. (i) We first introduce a new concept of piecewise survivability, which makes the problem much easier in practice (although still NP-complete), and allows us to formally prove that a given survivable mapping does or does not exist. (ii) Secondly, we show how to trace the vulnerable areas in the topology, and how to strengthen them to enable a survivable mapping. (iii) Thirdly, we give an efficient and scalable algorithm that finds a survivable mapping. In contrast to the heuristics proposed in the literature to date, our algorithm exhibits a number of provable properties (e.g., it guarantees the piecewise survivability) that are crucial for (i) and (ii).

Error and Attack Tolerance of Layered Complex Networks
M. Kurant, P. Thiran and P. Hagmann
Physical Review E, vol. 76, no. 2, 026103, 2007.
[view at publisher]

Many complex systems may be described by not one but a number of complex networks mapped on each other in a multi-layer structure. Because of the interactions and dependencies between these layers, the state of a single layer does not necessarily reflect well the state of the entire system. In this paper we study the robustness of five examples of two-layer complex systems: three real-life data sets in the fields of communication (the Internet), transportation (the European railway system), and biology (the human brain), and two models based on random graphs. In order to cover the whole range of features specific to these systems, we focus on two extreme policies of system's response to failures, no rerouting and full rerouting. Our main finding is that multi-layer systems are much more vulnerable to errors and intentional attacks than they appear from a single layer perspective.

Towards Reliable Broadcasting using ACKs
M. Durvy, C. Fragouli and P. Thiran
ISIT, Nice, June 24-29, 2007.
[view at publisher]

We propose a mechanism for reliable broadcasting in wireless networks, that consists of two components: a method for bandwidth efficient acknowledgment collection, and a coding scheme that uses acknowledgments. Our approach combines ideas from network coding and distributed space time coding.

Closing the gap in the capacity of random wireless networks via percolation theory
M. Franceschetti, O. Dousse, D. N. C. Tse and P. Thiran
IEEE Transactions on Information Theory, vol. 53, no. 3, 1009 - 1018, 2007.
[view at publisher]

An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics. It is shown that randomly scattered nodes can achieve, with high probability, the same 1/\sqrt{n} transmission rate of arbitrarily located nodes. This contrasts with previous results suggesting that a 1/\sqrt{nlogn} reduced rate is the price to pay for the randomness due to the random location of the nodes. The network operation strategy to achieve the result corresponds to the transition region between order and disorder of an underlying percolation model. If nodes are allowed to transmit over large distances, then paths of connected nodes that cross the entire network area can be easily found, but these generate excessive interference. If nodes transmit over short distances, then such crossing paths do not exist. Percolation theory ensures that crossing paths form in the transition region between these two extreme scenarios. Nodes along these paths are used as a backbone, relaying data for other nodes, and can transport the total amount of information generated by all the sources. A lower bound on the achievable bit rate is then obtained by performing pairwise coding and decoding at each hop along the paths, and using a time division multiple access scheme.

Modelling the IEEE 802.11 protocol in wireless multi-hop networks
M. Durvy
2007.
[full text] [view at publisher]

IEEE 802.11 is probably the most widely used, medium access control protocol in current wireless networks. In the Wireless LAN (i.e., single-hop) setting, its performance is by now quite well understood. However, in the multi-hop setting where relay nodes are used to achieve end-to-end communication, there is, to date, no widely accepted model. Consequently, when confronted with experimental results, people often find it hard to interpret them. The goals of this thesis are (i) to model protocols "à la 802.11" in the context of multi-hop ad hoc networks, (ii) to derive theoretical limits for their performance, (iii) to contrast the performance of the current IEEE 802.11 protocol with these limits and (iv) to identify all the factors that prevent IEEE 802.11 from reaching these limits. Most of this thesis is dedicated to achieving the two first goals. We begin by proposing an idealized version of IEEE 802.11. We model this idealized protocol using a continuous Markov chain. We then use the properties and the stationary distribution of this Markov chain to derive the performance of the idealized 802.11 protocol. We first look at its spatial reuse or, in other words, at its ability to schedule a large number of concurrent successful transmissions. We show that the idealized 802.11 protocol organizes the transmissions in space in such a way that it leads to an optimal spatial reuse when its access intensity is large. This is encouraging, as it shows that a protocol using only local interactions can find a global optimum in a completely decentralize way. We then consider the short and long-term fairness properties of the idealized 802.11 protocol. We observe a clear trade-off between its spatial reuse and its fairness. At low access intensities, its fairness is high but its spatial reuse is low; whereas at high access intensities, the reverse is true. As a result, the access intensity of the protocol can be used to adapt its performance to fit the requirements of the applications running on top of it. The fairness performance of 802.11 also highly depends on the underlying network topology – 802.11 only amplifies the existing topological inequalities. In regular lattice topologies these inequalities arise only at the border where the nodes have fewer neighbors than the nodes inside the network. We demonstrate that, in large line networks and for all finite access-intensities, this border effect does not propagate inside the network, as a result 802.11 is fair. In contrast, we demonstrate that in large grid topologies a phase transition occurs. Under a certain access intensity, the border effect fades away; whereas above a certain access intensity, it propagates throughout the network, and the protocol is severely unfair. Finally, after extending our model to consider different node sensing and capture capabilities, we compare the performance of the ns-2 implementation of IEEE 802.11 and of the idealized protocol. We observe a large gap between the theoretical and practical performance. We identify the three problems that are responsible for this gap. We then propose a remedy to address each of these problems, and show that a 'cured' IEEE 802.11 can achieve the level of performance of the idealized 802.11 protocol.

Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks
N. Sarafijanovic-Djukic, M. Piorkowski and M. Grossglauser
2007.

Mobile wireless ad hoc and sensor networks can be permanently partitioned in many interesting scenarios. This implies that instantaneous end-to-end routes do not exist. Nevertheless, when nodes are mobile, it is possible to forward messages to their destinations through mobility. In these many interesting settings we observe that spatial node distributions are very heterogeneous and possess concentration points of high node density. The locations of these concentration points and the flow of nodes between them tend to be stable over time. This motivated us to propose a novel mobility model, where nodes move randomly between stable islands of connectivity, where they are likely to encounter other nodes, while connectivity is very limited outside these islands. Our goal is to exploit such a stable topology of concentration points by developing algorithms that allow nodes to collaborate in order to discover this topology and to use it for efficient mobility forwarding. We achieve this without any external signals to nodes, such as geographic positions or fixed beacons; instead, we rely only on the evolution of the set of neighbors of each node. We propose an algorithm for this collaborative graph discovery problem and show that the inferred topology can greatly improve the efficiency of mobility forwarding. Using the proposed mobility model we show through simulations that our approach achieves end-to-end delays comparable to those of epidemic approaches and requires a significantly lower transmission overhead.

Network Loss Inference with Second Order Statistics of End-to-End Flows
H. X. Nguyen and P. Thiran
ACM Internet Measurement Conference (IMC'07), San Diego, USA, October 24-26, 2007.
[full text] [view at publisher]

We address the problem of calculating link loss rates from end-to-end measurements. Contrary to existing works that use only the average end-to-end loss rates or strict temporal correlations between probes, we exploit second-order moments of end-to-end flows. We first prove that the variances of link loss rates can be uniquely calculated from the covariances of the measured end-to-end loss rates in any realistic topology. After calculating the link variances, we remove the un-congested links with small variances from the first-order moment equations to obtain a full rank linear system of equations, from which we can calculate precisely the loss rates of the remaining congested links. This operation is possible because losses due to congestion occur in bursts and hence the loss rates of congested links have high variances. On the contrary, most links on the Internet are un-congested, and hence the averages and variances of their loss rates are virtually zero. Our proposed solution uses only regular unicast probes and thus is applicable in today's Internet. It is accurate and scalable, as shown in our simulations and experiments on PlanetLab.

Modeling the 802.11 protocol under different capture and sensing capabilities
M. Durvy, O. Dousse and P. Thiran
Infocom 2007, Anchorage, Alaska , USA., 2007.
[view at publisher]

Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the 802.11 protocol, are known to be unfair. In multi-hop networks, they can even favor some connections to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood. We find that the capture effect and the relative values of the receiving and carrier sensing ranges play a crucial role in the unfairness of these protocols. We show that an idealized 802.11 protocol does suffer from starvation when the receiving and sensing ranges are equal, but quite surprisingly this unfairness is reduced or even disappears when these two ranges are sufficiently different. Using a Markovian model, we explain why apparently benign variations in these ranges have such a dramatic impact on the 802.11 protocol performance.

Robust Geo-Routing on Embeddings of Dynamic Wireless Networks
D. Tschopp, S. Diggavi, M. Grossglauser and J. Widmer
2007.
[view at publisher]

Wireless routing based on an embedding of the connectivity graph is a very promising technique to overcome shortcomings of geographic routing and topology-based routing. This is of particular interest when either absolute coordinates for geographic routing are unavailable or when they poorly reflect the underlying connectivity in the network. We focus on dynamic networks induced by time-varying fading and mobility. This requires that the embedding is stable over time, whereas the focus of most existing embedding algorithms is on low distortion of single realizations of a graph. We develop a beaconbased distributed embedding algorithm that requires little control overhead, produces low distortion embeddings, and is stable. We also show that a low-dimensional embedding suffices, since at a sufficiently large scale, wireless connectivity graphs are dictated by geometry. The stability of the embedding allows us to combine georouting on the embedding with last encounter routing (LER) for node lookup, further reducing the control overhead. Our routing algorithm avoids dead ends through randomized greedy forwarding. We demonstrate through extensive simulations that our combined embedding and routing scheme outperforms existing algorithms. I. INTRODUCTION

The Boolean Solution to the Congested IP Link Location Problem: Theory and Practice
H. X. Nguyen and P. Thiran
IEEE INFOCOM 2007, Anchorage, Alaska, 6-12 May 2007.
[view at publisher]

Like other problems in network tomography or traffic matrix estimation, the location of congested IP links from end-to-end measurements requires solving a system of equations that relate the measurement outcomes with the variables representing the status of the IP links. In most networks, this system of equations does not have a unique solution. To overcome this critical problem, current methods use the unrealistic assumption that all IP links have the same prior probability of being congested. We find that this assumption is not needed, because these probabilities can be uniquely identified from a small set of measurements by using properties of Boolean algebra. We can then use the learnt probabilities as priors to find rapidly the congested links at any time, with an order of magnitude gain in accuracy over existing algorithms. We validate our results both by simulation and real implementation in the PlanetLab network.

2006

Mobile User Navigation Supported by WSAN: Full-fledge Demo of the SmartPark System
M. Piorkowski, M. Grossglauser and A. Papaioannou
MobiHoc'06, 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Florence, Italy, May 22-25 2006.

The purpose of this demonstration is to illustrate that an off-the-shelf Wireless Sensor and Actuator Network (WSAN) can be used to discover resource availability and guide mobile users to these resources without any support from a navigation system like GPS. The motivating application of this technical demonstration is SmartPark, a distributed system that provides drivers with turn-by-turn instructions to free parking spots in an urban environment. This demo illustrates the usage of simple localized algorithms in the scenario where no node (fixed and mobile) has a full view of the entire network and that exploit the mobility of nodes. The SmartPark application is developed in WASAL, a laboratory for prototyping ad-hoc sensor and actuator applications.

Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks
N. Sarafijanovic-Djukic, M. Piorkowski and M. Grossglauser
SECON'06, Reston, VA, September 25-28.
[view at publisher]

Mobile wireless ad hoc and sensor networks can be permanently partitioned in many interesting scenarios. This implies that instantaneous end-to-end routes do not exist. Nevertheless, when nodes are mobile, it is possible to forward messages to their destinations through mobility. We observe that in many practical settings, spatial node distributions are very heterogeneous and possess concentration points of high node density. The locations of these concentration points and the flow of nodes between them tend to be stable over time. This motivates a novel mobility model, where nodes move randomly between stable islands of connectivity, where they are likely to encounter other nodes, while connectivity is very limited outside these islands. Our goal is to exploit such a stable topology of concentration points by developing algorithms that allow nodes to collaborate to discover this topology and to use it for efficient mobility forwarding.We achieve this without any external signals to nodes, such as geographic positions or fixed beacons; instead, we rely only on the evolution of the set of neighbors of each node. We propose an algorithm for this collaborative graph discovery problem and show that the inferred topology can greatly improve the efficiency of mobility forwarding. Using both synthetic and data-driven mobility models we show through simulations that our approach achieves end-to-end delays comparable to those of epidemic approaches, while requiring a significantly lower transmission overhead.

Layered Complex Networks
M. Kurant and P. Thiran
Physical Review Letters, vol. 96, 138701, 2006.
[view at publisher]

Many complex networks are only a part of larger systems, where a number of coexisting topologies interact and depend on each other. We introduce a layered model to facilitate the description and analysis of such systems. As an example of its application, we study the load distribution in three transportation systems, where the lower layer is the physical infrastructure and the upper layer represents the traffic flows. This layered view allows us to capture the fundamental differences between the real load and commonly used load estimators, which explains why these estimators fail to approximate the real load.

Extraction and analysis of traffic and topologies of transportation networks
M. Kurant and P. Thiran
Physical Review E, vol. 74, no. 3, 036114, 2006.
[view at publisher]

The knowledge of real-life traffic patterns is crucial for a good understanding and analysis of transportation systems. These data are quite rare. In this paper we propose an algorithm for extracting both the real physical topology and the network of traffic flows from timetables of public mass transportation systems. We apply this algorithm to timetables of three large transportation networks. This enables us to make a systematic comparison between three different approaches to construct a graph representation of a transportation network; the resulting graphs are fundamentally different. We also find that the real-life traffic pattern is very heterogeneous, in both space and traffic flow intensities, which makes it very difficult to approximate the node load with a number of topological estimators.

Understanding the Gap between the IEEE 802.11 Protocol Performance and the Theoretical Limits
M. Durvy and P. Thiran
SECON 2006, Reston, VA, USA, 2006.
[view at publisher]

The ability of the IEEE 802.11 Medium Access Control (MAC) protocol to perform well in multi-hop ad hoc networks has been recently questioned. We observe levels of spatial reuse that are 30% to 50% away from the theoretical limit. The goal of this paper is to answer the following question: what prevents the IEEE 802.11 MAC protocol from operating at the limit determined by its physical layer? We identify three problems in the contention resolution mechanism of the IEEE 802.11 MAC protocol, and we show that they account for most of the gap separating the actual and optimal performances of the protocol. For each of the problems, we propose a solution that, once implemented, allows us to quantify the impact of the problem on the performance of the IEEE 802.11 MAC protocol. The resulting protocol operates 10% to 15% away from the theoretical limit. Finally, we show that reducing the overhead of the protocol to some negligible quantity brings the spatial reuse of the protocol to the theoretical limits. It also makes apparent the powerful organizing capacity of the IEEE 802.11 MAC protocol.

Robust checkers for self-calibrating designs
F. Worm
2006.
[full text] [view at publisher]

So far, performance and reliability of circuits have been determined by worst-case characterisation of silicon and of environmental conditions such as noise and temperature. As nanometer technologies exacerbate process variations and reduce noise margins, worst-case design will eventually fail to meet an aggressive combination of objectives in performance, reliability, and power. In order to circumvent these difficulties, researchers have recently proposed a new design paradigm: self-calibrating circuits. The design parameters (e.g., operating points) of a self-calibrating circuit are tuned at run-time by a controller. The latter receives feedback from a checker that monitors correct operation of the circuit. A self-calibrating circuit can thus trade dynamically reliability for power or performance, depending on actual silicon capabilities and noise conditions. This thesis pioneers the use of digital self-calibration techniques to dynamically tune the operating points of an on-chip link based on the detection of run-time transfer errors. In particular, we show that the energy overhead induced by the checker and operating point controller is offset by the operating of the link at sub-critical voltage. Such a system-level study strengthens the interest into self-calibrated links by demonstrating their feasibility. The primary focus of the thesis bears on the development of robust and low overhead checkers for a self-calibrating on-chip data link subject to errors caused by operation at sub-critical voltage. Such errors –we call them timing errors– may be numerous and cause error rates as large as 100%. We abstract timing errors by the failure of bit transitions and propose ad-hoc coding techniques to detect them reliably. We emphasise the originality of the coding requirements by showing that (i) traditional error correcting codes (like CRCs) fail to detect timing errors under over-aggressive operation of the link, and (ii) asynchronous codes such as dual-rail detect all timing errors, but incur a significant bandwidth overhead in the synchronous context of our problem. Next, we introduce a novel code-based checker satisfying such requirements and featuring unique detection capabilities towards both timing and additive errors. Then, we contrast the error detection capabilities of the code-based checker with the one of double sampling flip-flops. We stress the complementarity of the two approaches and show how to optimally combine them into an even more robust checker featuring a very limited wiring and circuitry overhead. Finally, we extend our work to computing elements by giving preliminary research directions on the detection of timing errors resulting from the self-calibration of the operating points of an adder. The main contribution of this work is to propose novel checker architectures based on codes and/or double sampling flip-flops to detect massive timing errors caused by self-calibration of the link operating points. A requirement rendering our work unique is that reliable operation of the checker should be ensured over the whole range of bit error rates from 0 to 100%. Furthermore, we have developed a unified framework bringing fundamental insights into the timing error detection capabilities of various practical encoding schemes.

Locating Mobile Nodes with EASE: Learning Efficient Routes from Encounter Histories Alone
M. Grossglauser and M. Vetterli
IEEE/ACM Transactions on Networking, vol. 14, no. 3, 457 - 469, 2006.
[view at publisher]

Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient location service, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that node mobility can be exploited to disseminate destination location information without incurring any communication overhead. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has ``diffused'' estimates of that location. We define and analyze a very simple algorithm called EASE (Exponential Age Search) and show that in a model where $\Theta(n)$ nodes perform independent random walks on a square lattice of size $n$, the length of the routes computed by EASE are of the same order as the distance between the source and destination {\em even for very large $n$.} Therefore, without disseminating any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalability.

Using End-to-End Data to Infer Lossy Links in Sensor Networks
H. X. Nguyen and P. Thiran
IEEE Infocom 2006, Barcelona, Spain, 23-30 April, 2006.
[view at publisher]

Compared to wired networks, sensor networks pose two additional challenges for monitoring functions: they support much less probing traffic, and they change their routing topologies much more frequently. We propose therefore to use only end-to-end application traffic to infer performance of internal network links. End-to-end data do not provide sufficient information to calculate link loss rates exactly, but enough to identify poorly performing (lossy) links. We introduce inference techniques based on Maximum likelihood and Bayesian principles, which handle well noisy measurements and routing changes. We evaluate the performance of both inference algorithms in simulation and on real network traces. We find that these techniques achieve high detection and low false positive rates.

MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks
J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser and J. Hubaux
2nd IEEE/ACM DCOSS, San Francisco, CA, USA, June 2006.
[view at publisher]

Improving network lifetime is an important issue involved in every aspect of the design and deployment of wireless sensor networks. There is a recent research trend of studying the application of a mobile sink to transport (rather than let the sensor nodes transmit) data back. Whereas this approach trades data delivery latency for reduced (node) energy consumption (and thus an improved lifetime), our experience tells us that sacrificing latency to extend lifetime is not necessary. In this paper, in line with our previous work, we investigate the approach that makes use of a mobile sink for balancing the traffic load and in turn improving network lifetime. We engineer a routing protocol that effectively supports sink mobility. Through intensive simulations in TOSSIM with a real implementation, we prove the feasibility of our mobile sink approach by demonstrating the improved network lifetime in several deployment scenarios.

Percolation in the signal to interference ratio graph
O. Dousse, M. Franceschetti, N. Macris, R. Meester and P. Thiran
Journal of Applied Probability, vol. 43, no. 2, 552 - , 2006.
[view at publisher]

Continuum percolation models in which pairs of points of a two-dimensional Poisson point process are connected if they are within some range to each other have been extensively studied. This paper considers a variation in which a connection between two points depends not only on their Euclidean distance, but also on the positions of all other points of the point process. This model has been recently proposed to model interference in radio communication networks. Our main result shows that, despite the infinite range dependencies, percolation occurs in the model when the density of the Poisson point process is greater than the critical density value of the independent model, provided that interference from other nodes can be sufficiently reduced (without vanishing).

A Packing Approach to Compare Slotted and Non-Slotted Medium Access Control
M. Durvy and P. Thiran
Infocom 2006, Barcelona, April 23-29, 2006.
[view at publisher]

In multi-hop ad hoc networks, the efficiency of a medium access control protocol under heavy traffic load depends mainly on its ability to schedule a large number of simultaneous non-interfering transmissions. However, as each node has only a local view of the network, it is difficult to globally synchronize transmission times over the whole network. How does the lack of global coordination affect spatial reuse in multi-hop wireless networks? We show that in a de-centralized network the spatial reuse does not benefit from global clock synchronization. On the contrary, we demonstrate that non-slotted protocols using collision avoidance mechanisms can achieve a higher spatial reuse than the corresponding slotted protocols. By means of a simple backoff mechanism, one can thus favor the spontaneous emergence of spatially dense transmission schedules.

Constrained Tracking on a Road Network
M. Piorkowski and M. Grossglauser
European Workshop on Wireless Sensor Networks EWSN2006, ETH Zurich, Switzerland, February 13-15, 2006.
[full text] [view at publisher]

Many applications of wireless ad hoc sensor and actuator networks (WSANs) rely on the knowledge of node locations. These are challenging to obtain when nodes are mobile and are not equipped with any expensive positioning hardware. In this paper, we are interested in scenarios where there are constraints on the movement of nodes, such as with cars on the road network. We develop and analyse a tracking algorithm called MOONwalk, which explicitly takes such constraints into account in order to improve the tracking precision. Furthermore, MOONwalk does not require global knowledge of the network, and therefore lends itself well to large-scale and high-mobility applications. We evaluate the accuracy of MOONwalk by comparing it to the optimal maximum likelihood estimator, under different radio conditions and deployment scenarios. We find that MOONwalk performs well despite its localized operation.

On the throughput scaling of wireless relay networks
O. Dousse, M. Franceschetti and P. Thiran
IEEE Transactions on Information Theory, vol. 52, no. 6, 2756 - , 2006.
[view at publisher]

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed non-zero rate imply some of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

2005

Percolation in the signal to interference ratio graph
O. Dousse, M. Franceschetti, N. Macris, R. Meester and P. Thiran
44th Allerton Conference on Communication, Control and Computing, Monticello, Illinois, September 2005.

Percolation in the signal to interference ratio graph
O. Dousse, M. Franceschetti, N. Macris, R. Meester and P. Thiran
Allerton Conference, Monticello, IL, September 2005.

Continuum percolation models in which pairs of points of a two-dimensional Poisson point process are connected if they are within some range to each other have been extensively studied. This paper considers a variation in which a connection between two points depends not only on their Euclidean distance, but also on the positions of all other points of the point process. This model has been recently proposed to model interference in radio communication networks. Our main result shows that, despite the infinite range dependencies, percolation occurs in the model when the density of the Poisson point process is greater than the critical density value of the independent model, provided that interference from other nodes can be sufficiently reduced (without vanishing).

MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks
J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser and J. Hubaux
2005.

Improving network lifetime is an important issue involved in every aspect of the design and deployment of wireless sensor networks. There is a recent research trend of studying the application of a mobile sink to transport (rather than let the sensor nodes transmit) data back. Whereas this approach trades data delivery latency for reduced (node) energy consumption (and thus an improved lifetime), our experience tells us that sacrificing latency to extend lifetime is not necessary. In this paper, in line with our previous work, we investigate the approach that makes use of a mobile sink for balancing the traffic load and in turn improving network lifetime. We engineer a routing protocol that effectively supports sink mobility. Through intensive simulations in TOSSIM with a real implementation, we prove the feasibility of our mobile sink approach by demonstrating the improved network lifetime in several deployment scenarios.

Asymptotic properties of wireless multi-hop networks
O. Dousse
2005.
[full text] [view at publisher]

In this dissertation, we consider wireless multi-hop networks, where the nodes are randomly placed. We are particularly interested in their asymptotic properties when the number of nodes tends to infinity. We use percolation theory as our main tool of analysis. As a first model, we assume that nodes have a fixed connectivity range, and can establish wireless links to all nodes within this range, but no other (Boolean model). We compute for one-dimensional networks the probability that two nodes are connected, given the distance between them. We show that this probability tends exponentially to zero when the distance increases, proving that pure multi-hopping does not work in large networks. In two dimensions however, an unbounded cluster of connected nodes forms if the node density is above a critical threshold (super-critical phase). This is known as the percolation phenomenon. This cluster contains a positive fraction of the nodes that depends on the node density, and remains constant as the network size increases. Furthermore, the fraction of connected nodes tends rapidly to one when the node density is above the threshold. We compare this partial connectivity to full connectivity, and show that the requirement for full connectivity leads to vanishing throughput when the network size increases. In contrast, partial connectivity is perfectly scalable, at the cost of a tiny fraction of the nodes being disconnected. We consider two other connectivity models. The first one is a signal-to-interference- plus-noise-ratio based connectivity graph (STIRG). In this model, we assume deterministic attenuation of the signals as a function of distance. We prove that percolation occurs in this model in a similar way as in the previous model, and study in detail the domain of parameters where it occurs. We show in particular that the assumptions on the attenuation function dramatically impact the results: the commonly used power-law attenuation leads to particular symmetry properties. However, physics imposes that the received signal cannot be stronger than the emitted signal, implying a bounded attenuation function. We observe that percolation is harder to achieve in most cases with such an attenuation function. The second model is an information theoretic view on connectivity, where two arbitrary nodes are considered connected if it is possible to transmit data from one to the other at a given rate. We show that in this model the same partial connectivity can be achieved in a scalable way as in the Boolean model. This result is however a pure connectivity result in the sense that there is no competition and interferences between data flows. We also look at the other extreme, the Gupta and Kumar scenario, where all nodes want to transmit data simultaneously. We show first that under point-to-point communication and bounded attenuation function the total transport capacity of a fixed area network is bounded from above by a constant, whatever the number of nodes may be. However, if the network area increases linearly with the number of nodes (constant density), or if we assume power-law attenuation function, a throughput per node of order 1/√n can be achieved. This latter result improves the existing results about random networks by a factor (log n)1/2. In the last part of this dissertation, we address two problems related to latency. The first one is an intruder detection scenario, where a static sensor network has to detect an intruder that moves with constant speed along a straight line. We compute an upper bound to the time needed to detect the intruder, under the assumption that detection by disconnected sensors does not count. In the second scenario, sensors switch off their radio device for random periods, in order to save energy. This affects the delivery of alert messages, since they may have to wait for relays to turn on their radio to move further. We show that asymptotically, alert messages propagate with constant, deterministic speed in such networks.

Deux applications de processus ponctuels aux réseaux de communication
O. Dousse, H. X. Nguyen and P. Thiran
GRETSI, Louvain-la-Neuve, Belgium, 2005.

This paper (in Frensh) summarizes recent results obtained by using shot noise processes for two applications in communication networks: first, TCP/IP traffic models for backbone networks; and next the study of connectivity under rate constraints in wireless ad hoc networks.

Failure Location in Transparent Optical Networks: The Asymmetry Between False and Missing Alarms
H. X. Nguyen and P. Thiran
The 19th International Teletraffic Congress (ITC19), Beijing, China, 2005.

Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices. Setting the thresholds low results in false alarms, whereas setting them high presents the risk of missing a significant degradation in network performance because of missing alarms. In this work, we study the time complexity of the failure location problem in transparent optical networks and provide an efficient algorithm to solve this problem. More significantly, we show that for a network with binary alarms (alarms are either present or not), there is an asymmetry between false and missing alarms. We prove that false alarms can be corrected in polynomial time, but that the correction of missing alarms is NP-hard. Because of this asymmetry between false and missing alarms, false alarms have lesser effect on the accuracy of the diagnosis results than missing alarms do. Network operators therefore, when allowed, should set the threshold low to favor false alarms rather than high.

Binary Versus Analogue Path Monitoring in IP Networks
H. X. Nguyen and P. Thiran
PAM2005, Boston, USA, 2005.
[view at publisher]

Monitoring systems that can detect path outages and periods of degraded performance are important for many distributed applications. Trivial pairwise probing systems do not scale well and cannot be employed in large networks. To build scalable path monitoring systems, two different approaches have been proposed in the literature. The first approach [1], which we call the continuous or analogue model, takes real measurement values and infers the performance metrics of unmeasured paths using traditional (+,) algebra. The second approach [2], which we call the Boolean model, takes binary values from measurements (e.g., whether the delay/loss of an end-to-end path is above a given threshold) and infers the performance quality of unmeasured paths using Boolean algebra. Both approaches exploit the fact that end-to-end paths share network links and hence that the measurements of some paths can be used to infer the performance on others. In this work, we are only in- terested in detecting whether the performance of a path is below an acceptable level or not. We show that when the number of beacons (nodes that can send probes and collect monitoring information) is small, the Boolean model requires fewer direct measurements; whereas for a large number of beacons the continuous model requires fewer direct measurements. When the number of beacons is significantly large, however, there is no difference in terms of the number of paths that we need to measure directly in both models. We verify the results by simulations on inferred network topologies and on real measurement data.

On Survivable Routing of Mesh Topologies in IP-over-WDM Networks
M. Kurant and P. Thiran
INFOCOM, Miami, USA, 2005.
[view at publisher]

Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called survivable. Finding a survivable mapping is known to be NP-complete, making it impossible in practice to assess the existence or absence of such a mapping for large networks. (i) We first introduce a new concept of piecewise survivability, which makes the problem much easier, and allows us to formally prove that a given survivable mapping does or does not exist. (ii) Secondly, we show how to trace the vulnerable areas in the topology, and how to strengthen them to enable a survivable mapping. (iii) Thirdly, we give an efficient and scalable algorithm that finds a survivable mapping. In contrast to the heuristics proposed in the literature to date, our algorithm exhibits a number of provable properties that are crucial for (i) and (ii). We consider both link and node failures at the physical layer.

Failure Location in WDM Networks
C. Mas, H. X. Nguyen and P. Thiran
Emerging Optical Network Technologies, 379 - 399, 2005.
[view at publisher]

Fault identification and location in optical networks must cope with a multitude of factors: (i) the redundancy and the lack of coordination (internetworking) of the managements at the different layers (WDM, SDH/SONET, ATM, IP)

Mobility Improves Coverage of Sensor Networks
B. Liu, P. Brass, O. Dousse, P. Nain and D. Towsley
Mobihoc, Urbana-Champaign, IL, 2005.

Previous work on the coverage of mobile sensor networks focuses on algorithms to reposition sensors in order to achieve a static configuration with an enlarged covered area. In this paper, we study the dynamic aspects of the coverage of a mobile sensor network that depend on the process of sensor movement. As time goes by, a position is more likely to be covered; targets that might never be detected in a static sensor network can now be detected by moving sensors. We characterize the area coverage at specific time instants and during time intervals, as well as the time it takes to detect a randomly located static target. Our results show that sensor mobility can be exploited to compensate for the lack of sensors and improve the network coverage. For mobile targets, we take a game theoretic approach and derive optimal mobility strategies for sensors and the targets from their own perspectives.

Reaction-Diffusion Based Transmission Patterns for Ad Hoc Networks
M. Durvy and P. Thiran
Infocom, Miami, 2005.
[view at publisher]

We present a new scheme that mimics pattern formation in biological systems to create transmission patterns in multi-hop ad hoc networks. Our scheme is decentralized and relies exclusively on local interactions between the network nodes to create global transmission patterns. A transmission inhibits other transmissions in its immediate surrounding and encourages nodes located further away to transmit. The transmission patterns created by our medium access control scheme combine the efficiency of allocation-based schemes at high traffic loads and the flexibility of random access schemes. Moreover, we show that with appropriately chosen parameters our scheme converges to collision free transmission patterns that guarantee some degree of spatial reuse.

Information theoretic bounds on the throughput scaling of wireless relay networks
O. Dousse, M. Franceschetti and P. Thiran
Infocom, Miami, 2005.
[view at publisher]

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed non-zero rate imply some of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

Impact of Interferences on Connectivity in Ad Hoc Networks
O. Dousse, F. Baccelli and P. Thiran
IEEE/ACM Trans. on Networking, vol. 13, no. 2, 425 - 436, 2005.
[view at publisher]

We study the impact of interferences on the connectivity of large-scale ad-hoc networks, using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at the receiver is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient gamma, and of a background noise. We find that there is a critical value of gamma above which the network is made of disconnected clusters of nodes. We also prove that if gamma is non zero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of gamma cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every n-th time slot. We show that it achieves connectivity similar to the previous system with a parameter gamma/n.

2004

Undetection error probability of linear and alternating-phase codes over the timing error channel
F. Worm, P. Ienne and P. Thiran
2004.

We develop a channel model for errors originated from over-aggressive operation of a communication link. Such a situation arises in the context of on-chip self-calibrating communication, where a link controller has to determine adaptively the operating voltage and frequency. Based on this channel model, we derive an analytical expression for the undetection error probability of linear codes, and alternating-phase codes, the latter being an extension of the former.

Survivable MApping Algorithm by Ring Trimming (SMART) for large IP-over-WDM networks
M. Kurant and P. Thiran
BroadNets, San Jose, California, USA, 2004.

We develop a fast and efficient algorithm that finds a survivable (i.e., robust to single fiber failures) mapping of IP topology on the mesh of fibers in IP-over-WDM networks; we call it SMART. A number of algorithms solving this problem can be found in the literature. Since ILP solutions are highly complex, many heuristics were proposed. They usually start with some initial mapping and then try to gradually improve it. This involves the evaluation of the entire topology at each iteration, which is costly for large topologies. We propose a different approach. The SMART algorithm breaks down the task into a set of independent and very simple subtasks. The combination of solutions of these subtasks is a survivable mapping. This is why SMART is orders of magnitude faster than other proposals, especially when dealing with large topologies. We also extend the SMART algorithm to obtain a mapping resilient to fiber span failures, node failures and double-link failures. Finally, we show that the scalability of the standard heuristic approaches is additionally limited (contrary to SMART) when applied to double-link failures.

Controlled Use of Excess Backbone Bandwidth for Providing New Services in IP-Over-WDM Networks
A. Nucci, N. Taft, C. Barakat and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. JSAC-22, no. 9, 1692 - , 2004.
[view at publisher]

We study an approach to quality-of-service (QoS) that offers end-users the choice between two service classes defined according to their level of transmission protection. The fully protected (FP) class offers end-users a guarantee of survivability in the case of a single-link; all FP traffic is protected using a 1:1 protection scheme at the WDM layer. The second class of service, called Best-Effort Protected (BEP), is not protected; instead restoration at the IP layer is provided. The FP service class mimics what Internet users receive today. The BEP traffic is designed to run over the large amounts of unused bandwidth that exist in today`s Internet. The motivation of this approach is to give carriers a mechanism for increasing the load carried on backbone networks without reducing the QoS received by existing customers. In order to support two such services, we have to solve two problems: the off-line problem of mapping logical links to pairs of disjoint fiber paths, and an on-line scheduling problem for differentiating packets from two classes at the IP layer. We provide an algorithm based on a Tabu Search meta-heuristic to solve the mapping problem, and a simple but efficient scheduler based on Weighted Fair Queuing for service differentiation at the IP layer. We consider numerous requirements that carriers face and illustrate the tradeoffs they induce. We evaluate the throughput, delay and loss performance of the two traffic classes and illustrate that we can successfully increase the total network load by a factor between three and ten and still meet all the carrier requirements.

The Costly Path from Percolation to Full Connectivity
O. Dousse, M. Franceschetti and P. Thiran
Allerton Conference, Monticello IL, 2004.

Requiring all nodes of a wireless multihop network to be connected is expensive and results in a poor scalability of properties such as transport capacity. We show however that it is no longer the case if we only slightly loosen the connectivity requirement, by just imposing that most nodes be connected to each other (so that the network ``percolates``). This feature is found in models neglecting interferences, taking interferences as noise or taking a more information theoretic approach.

Last Encounter Routing under Random Waypoint Mobility
N. Sarafijanovic-Djukic and M. Grossglauser
Networking 2004, Athens, Greece, 2004.

Last Encounter Routing (LER) algorithms for mobile ad hoc networks rely only on encounter histories at every node to route packets, and therefore do not need control traffic to track topology changes due to node mobility. LER exploits the fact that past information about a node`s mobility helps to locate that node in the future. As we have pointed out in earlier work \cite{mg}, the performance of LER algorithms depends on the mobility processes of nodes. In this paper, we ask whether LER can work under the random waypoint (RWP) mobility model. This question is important for several reasons. First, as shown in \cite{mg}, a good performance for the RWP model is harder to achieve than for another prominent mobility model, the random walk. This is because the RWP model has a much shorter relaxation time, i.e., a time-horizon over which past information is still useful. Also, the RWP model has a much less favorable ratio of number of encounters between nodes and the traveled distance. Second, in contrast to the random walk, the RWP model is predictable. This provides us with an opportunity to exploit additional information collected in an encounter (such as speed, direction, etc.) to improve routing. We formally define the RWP model, and compute the optimal predictors for several observation sets, i.e., observed parameters of node mobility. We develop a new LER algorithm tuned to the RWP model called GREASE-RWP, and present simulation results that demonstrate that an efficient and scalable LER for the RWP model is possible.

Active measurement for multiple link failure diganosis in IP networks
H. X. Nguyen and P. Thiran
Passive and active measurment workshop, Antibes-Juan les Pins, 2004.

Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that minimizes both the additional traffic due to probe messages and the measurement infrastructure costs. In the first phase, using elements from max-plus algebra theory, we show that the optimal set of probes can be determined in polynomial time, and we provide an algorithm to find this optimal set of probes. In the second phase, given the optimal set of probes, we compute the location of a minimal set of measurement points (beacons) that can generate these probes. We show that the beacon placement problem is NP-hard and propose a constant factor approximation algorithm for this problem. We then apply our algorithms to existing ISP networks using topologies inferred by the Rocketfuel tool \cite{Spring02:1}. We study in particular the difference between the number of probes and beacons that are required for multiple and single failure(s) diagnosis.

Closing the gap in the capacity of random wireless networks
M. Franceschetti, O. Dousse, D. Tse and P. Thiran
ISIT 2004, Chicago, 2004.
[view at publisher]

We consider the problem of how throughput in a wireless network with randomly located nodes scales as the number of users grows. Following the physical model of Gupta and Kumar, we show that randomly scattered nodes can achieve the optimal 1/sqrt(n) per-node transmission rate of arbitrarily located nodes. This contrasts with previous achievable results suggesting that a 1/sqrt(n log(n)) reduced rate is the price to pay for the additional randomness introduced into the system. Of independent interest is that we directly apply results from percolation theory to prove our result.

Latency of wireless sensor networks with uncoordinated power saving mechanisms
O. Dousse, P. Mannersalo and P. Thiran
Mobihoc, Tokyo, 2004.

We consider a wireless sensor network, where nodes switch between an active (on) and a sleeping (off) mode, to save energy. Their switching on/off schedules are completely non-coordinated. Their positions are distributed according to a Poisson process, and their connectivity range is larger or equal to their sensing range. The durations of active and sleeping periods are such that the number of active nodes at any particular time is so low that the network is always disconnected. Is it possible to use such a network for time-critical monitoring of an area? Such a scenario requires indeed to have bounds on the latency, which is the delay elapsed between the time at which an incoming event is sensed by some node of the network, and the time at which this information is retrieved by the data collecting sink. A positive answer is provided to this question under some assumptions discussed in the paper. More precisely, we prove that the messages sent by a sensing node reach the sink with a fixed asymptotic speed, which does not depend on the random location of the nodes, but only on the network parameters (node density, connectivity range, duration of active and sleeping periods). The results are obtained rigorously by using an extension of first passage percolation theory.

On the correlation of TCP traffic in backbone networks
H. X. Nguyen, P. Thiran and C. Barakat
ISCAS (IEEE International Symposium on Circuits and Systems), Vancouver, Canada, 2004.
[view at publisher]

Connectivity vs Capacity in Dense Ad Hoc Networks
O. Dousse and P. Thiran
IEEE Infocom, Hong Kong, 2004.
[view at publisher]

We study the connectivity and capacity of finite area ad hoc wireless networks, with an increasing number of nodes (dense networks). We find that the properties of the network strongly depend on the shape of the attenuation function. For power law attenuation functions, connectivity scales, and the available rate per node is known to decrease like 1/sqrt(n). On the contrary, if the attenuation function does not have a singularity at the origin and is uniformly bounded, we obtain bounds on the percolation domain for large node densities, which show that either the network becomes disconnected, or the available rate per node decreases like 1/n.

2003

Measurement and Analysis of Single-Hop Delay on an IP Backbone Network
K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran and C. Diot
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, vol. 21, no. 6, 908 - 921, 2003.
[view at publisher]

We measure and analyze the single-hop packet delay through operational routers in the Sprint Internet protocol (IP) backbone network. After presenting our delay measurements through a single router for OC-3 and OC-12 link speeds, we propose a methodology to identify the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delay at the output link, we observe the presence of very large delays that cannot be explained within the context of a first-in first-out output queue model. We isolate and analyze these outliers. Results indicate that there is very little queueing taking place in Sprint’s backbone. As link speeds increase, transmission delay decreases and the dominant part of single-hop delay is packet processing time. We show that if a packet is received and transmitted on the same linecard, it experiences less than 20 s of delay. If the packet is transmitted across the switch fabric, its delay doubles in magnitude. We observe that processing due to IP options results in single-hop delays in the order of milliseconds. Milliseconds of delay may also be experienced by packets that do not carry IP options. We attribute those delays to router idiosyncratic behavior that affects less than 1% of the packets. Finally, we show that the queueing delay distribution is long-tailed and can be approximated with aWeibull distribution with the scale parameter a = 0.5 and the shape parameter b = 0.6 to 0.82.

Connectivity of self-organized ad hoc wireless networks
O. Dousse and P. Thiran
IEEE Intelligent Systems, vol. 18, no. 4, 83 - 86, 2003.

Modeling Internet backbone traffic at the flow level
C. Barakat, P. Thiran, G. Iannaconne, C. Diot and P. Owerzazki
IEEE Transactions on Signal Processing, vol. 51, no. 8, 2111 - 2124, 2003.
[view at publisher]

Our goal is to design a traffic model for non congested IP backbone links, which is simple enough to be used in network operation, while being as general as possible. The proposed solution is to model the traffic at the flow level by a Poisson shot-noise process. In our model, a flow is a generic notion that must be able to capture the characteristics of any kind of data stream. We analyze the accuracy of the model with real traffic traces collected on the Sprint IP backbone network. Despite its simplicity, our model provides a good approximation of the real traffic observed in the backbone and of its variation. Finally, we discuss the application of our model to network design and dimensioning.

Network Availability Based Service Differentiation
C. Diot, N. Taft, M. Durvy and P. Thiran
IWQoS, Monterey CA, 2003.
[view at publisher]

Numerous approaches have been proposed to manage Quality of Service in the Internet. However, none of them was successfully deployed in a commercial IP backbone, mostly because of their complexity. In this paper, we take advantage of the excess network bandwidth to offer a degraded class of traffic. We identify and analyze the impact of link failures on such a service and show that under a variety of circumstances failures provide a natural mechanism for service differentiation. We simulate our QoS scheme on a real IP backbone topology and derive Service Level Agreements for the new degraded service. We find that by adding a degraded class of traffic in the network, we can at least double the link utilization with no impact on the current backbone traffic.

Impact of Interferences on Connectivity in Ad Hoc Networks
O. Dousse, F. Baccelli and P. Thiran
Infocom, San Francisco, 2003.
[view at publisher]

We study the impact of interferences on the connectivity of large-scale ad-hoc networks, using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at reception is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient g, and of a background noise. We find that there is a critical value of g above which the network is made of disconnected clusters of nodes. We also prove that if g is non zero but small enough, there exist node spatial densities at which the network contains an large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of g cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every n-th time slot. We show qualitatively that it even achieves a better connectivity than the previous system with a parameter g/n.

2002

Mobility Increases the Capacity of Ad Hoc Wireless Networks
M. Grossglauser and D. Tse
IEEE/ACM Transactions on Networking, vol. 10, no. 4, 477, 2002.
[view at publisher]

A Pragmatic Definition of Elephants in Internet Backbone Traffic
K. Papagiannaki, N. Taft, S. Bhattacharyya, K. Salamatian, C. Diot and P. Thiran
ACM Sigcomm Internet Measurement Workshop, Marseille, France, 2002.
[view at publisher]

A Min-Plus system Theory for Constrained Traffic
C. S. Chang, R. Cruz, J. Le Boudec and P. Thiran
ACM/IEEE Transactions on Networking, vol. 10, no. 6, 805 - 817, 2002.
[view at publisher]

Increasing Link Utilization in IP over WDM Networks
A. Nucci, N. Taft, H. Zang, C. Diot and P. Thiran
Opticomm 2002, Boston, 2002.
[view at publisher]

A flow-based model for Internet backbone traffic
C. Barakat, G. Iannaccone, C. Diot, P. Owerzaski and P. Thiran
IMW 2002, Marseille, 2002.
[view at publisher]

Min-plus System Theory Applied to Communication Networks
J. Le Boudec and P. Thiran
MTNS`02, Univ. Notre-Dame, South Bend, Indiana, 2002.

Network Calculus is a set of recent developments, which provide a deep insight into flow problems encountered in networking. It can be viewed as the system theory that applies to computer networks. Contrary to traditional system theory, it relies on max-plus and min-plus algebra. In this paper, we show how a simple but important fixed-point theorem (residuation theorem in min-plus algebra) can be successfully applied to a number of problems in networking, such as window flow control, multimedia smoothing, and bounds on loss rates.

On Internet backbone traffic modeling
C. Barakat, G. Iannaconne, C. Diot and P. Thiran
Sigmetrics 02, Marina Del Rey, California, 2002.
[view at publisher]

A flow-based model for TCP traffic in an IP backbone network
C. Barakat, P. Thiran and C. Diot
2002.
[full text]

We present a model of TCP flows suited to Internet backbone traffic, where links are usually not congested. We characterize the traffic using information on flows, i.e., arrival time, size, and duration. The major contribution of this paper is a model capturing the variation of the transmission rate during a TCP flow solely based on the above flow parameters. This model accounts for the dynamics of TCP congestion window and for the Timeout mechanism. It is independent of the packet loss rate and the round-trip time of the connection. We then model the traffic on a backbone link by aggregating TCP flows. Our model is easy to compute, and we show via simulations that it gives a good approximation of Internet backbone traffic.

Analysis of measured single-hop delay from an operational backbone network
K. Papagiannaki, S. Moon, C. Fraleigh, F. Tobagi, C. Diot and P. Thiran
Infocom2002, New York, 2002.
[view at publisher]

Connectivity in ad-hoc and hybrid networks
O. Dousse, P. Thiran and M. Hasler
IEEE Infocom 2002, New York, 2002.
[view at publisher]

We consider a large-scale wireless network, but with a low density of nodes per unit area. Interferences are then less critical, contrary to connectivity. This paper studies the latter property for both a purely ad-hoc network and a hybrid network, where fixed base stations can be reached in multiple hops. We assume here that power constraints are modeled by a maximal distance above which two nodes are not (directly) connected. We find that the introduction of a sparse network of base stations does significantly help in increasing the connectivity, but only when the node density is much larger in one dimension than in the other. We explain the results by percolation theory. We obtain analytical expressions of the probability of connectivity in the 1-dim. case. We also show that at a low spatial density of nodes, bottlenecks are unavoidable. Results obtained on actual population data confirm our findings.

2001

Trajectory Sampling for Direct Traffic Observation
N. Duffield and M. Grossglauser
IEEE/ACM Transactions on Networking, vol. 9, no. 3, 280, 2001.
[view at publisher]

A flow-based model for Internet backbone traffic
C. Barakat, P. Thiran, G. Iannaccone, C. Diot and P. Owezarski
2001.

We model traffic on an uncongested backbone link of an IP network using Poisson Shot-noise process and M/G/$\infty$ queue. We validate the model by simulation. We analyze the model accuracy with real traffic traces collected on the Sprint IP backbone network. We show that despite its simplicity, our model provides a good approximation of the real traffic observed on OC-3 links. This model is also very easy to use and requires few simple parameters to be input.

A protection-based approach to QoS in Packet over fiber networks
P. Thiran, N. Taft, C. Diot, H. Zang and R. Mac Donald
2001.

-reserved-

A Novel Scheduler For a Low Delay Service Within Best-Effort
P. Hurley, M. Kara, J. Le Boudec and P. Thiran
2001.

We present a novel scheduling algorithm, Duplicate Scheduling with Deadlines (DSD). This algorithm implements the ABE service which allows interactive, adaptive applications, that mark their packets green, to receive a low bounded delay at the expense of maybe less throughput. ABE retains the best-effort context by protecting flows that value higher throughput more than low bounded delay, whose packets are marked blue. DSD optimises green traffic performance while satisfying the constraint that blue traffic must not be adversely affected. Using a virtual queue, deadlines are assigned to packets upon arrival, and green and blue packets are queued separately. At service time, the deadlines of the packets at the head of the blue and green queues are used to determine which one to serve next. It supports any mixture of TCP, TCP Friendly and non TCP Friendly traffic. We motivate, describe and provide an analysis of DSD, and show simulation results.

ABE: Providing a Low-Delay Service within best-effort
P. Hurley, M. Kara, J. Le Boudec and P. Thiran
2001.

We propose Alternative Best-Effort (ABE), a novel service for IP networks, which relies on the idea of providing low-delay at the expense of maybe less throughput. The objective is to retain the simplicity of the original Internet single class, best effort service, while providing low delay to interactive, adaptive applications. With ABE, every best effort packet is marked as either green or blue. Green packets are guaranteed a low bounded delay in every router. In exchange, green packets are more likely to be dropped (or marked using congestion notification) during periods of congestion than blue packets. For every packet, the choice of one or other colour is made by the application, based on the nature of its traffic and on global traffic conditions. Typically, an interactive application with real-time deadlines, such as audio, will mark most of its packets as green, as long as the network conditions offer a large enough throughput. In contrast, an application that transfers binary data such as bulk data transfer, will seek to minimise overall transfer time and send blue traffic. We propose router requirements that aim at enforcing benefit for all types of traffic, namely, that green traffic achieves a low delay and blue traffic receives at least as much throughput as it would in a flat (legacy) best-effort network. ABE is different from differentiated or integrated services in that neither packet colour can be said to receive better treatment, thus flat rate pricing may be maintained, and there is no need for reservations or profiles. In this paper, we define the ABE service, its requirements, properties and usage. We discuss the implications of replacing the existing IP best effort service by the ABE service. We propose and analyse an implementation based on a new scheduling method called Duplicate Scheduling with Deadlines (DSD). It supports any mixture of TCP, TCP Friendly and non TCP Friendly traffic.

A Protection-based Approach to QoS in Packet over Fiber Networks
N. Taft, C. Diot, H. Zang, R. Mac Donald and P. Thiran
IWDC 2001, Taormina, Italy, 2001.
[full text]

We propose a novel approach to Quality of Service, intended for IP over SONET (or IP over WDM) networks, that offers end-users the choice between two service classes defined according to their level of transmission protection. The first service class (called Fully Protected (FP)) offers end-users a guarantee of survivability: all FP traffic is protected in the case of a (single) failure. The second service class (called Best-Effort Protected (BEP)) does not offer any specific level of protection but is cheaper. When failures occur, the network does the best it can by only restoring as much BEP traffic as possible. We motivate the need for two classes of protection services based on observations about backbone network practices that include overprovisioning and an ongoing but unbalanced process of link upgrades. We use an ILP formulation of the problem for finding primary and backup paths for these two classes of service. As a proof of concept, we evaluate the gain of providing two protection services rather than one in a simple topology. These initial results demonstrate that it is possible to increase the network load (and hence revenue) without affecting users that want complete survivability guarantees.

Preferential Treatment of Acknowledgment Packets in a Differentiated Services Network
K. Papagiannaki, P. Thiran, J. Crowcroft, C. Diot and P. Thiran
IWQoS 2001, Karlsruhe, 2001.
[full text]

In the context of Differentiated Services (DiffServ), we investigate the effect of acknowledgment marking on the throughput of TCP connections. We carry out experiments on a testbed offering three classes of service (Premium, Assured and Best-Effort), and different levels of congestion on the data and acknowledgment path. We apply a full factorial statistical design and deduce that marking TCP data packets is not sufficient and that acknowledgment marking on the reverse path is a necessary condition to efficiently match targeted performance in DiffServ. We find that the optimal marking strategy depends on the level of congestion on the reverse path. In the practical case where Internet Service Providers cannot obtain such information in order to mark acknowledgment packets, we show that the strategy leading to optimal overall performance is to copy the mark of the respective data packet, provided that the affected service class is appropriately provisioned.

A review on Fault Location Methods and their application to optical networks
C. Mas and P. Thiran
Optical Networks Magazine, 2001.
[full text]

A Novel Scheduler for a Low Delay Service Within Best-Effort
M. Kara, P. Hurley, J. Le Boudec and P. Thiran
IwQoS 2001, Karlsruhe, 2001.

We present a novel scheduling algorithm, Duplicate Scheduling with Deadlines (DSD). This algorithm implements the ABE service which allows interactive, adaptive applications, that mark their packets green, to receive a low bounded delay at the expense of maybe less throughput. ABE retains the best-effort context by protecting flows that value higher throughput more than low bounded delay, those packets are marked blue. DSD optimises green traffic performance while satisfying the constraint that blue traffic must not be adversely affected. Using a virtual queue, deadlines are assigned to packets upon arrival, and green and blue packets are queued separately. At service time, the deadlines of the packets at the head of the blue and green queues are used to determine which one to serve next. It supports any mixture of TCP, TCP Friendly and non TCP Friendly traffic. We motivate, describe and provide an analysis of DSD, and show simulation results.

ABE: providing a low-delay service within best effort
P. Hurley, M. Kara, J. Le Boudec and P. Thiran
IEEE Network, vol. 15, no. 3, 60 - 69, 2001.
[view at publisher]

Alternative best effort (ABE) is a novel service for IP networks, which relies on the idea of providing low delay at the expense of possibly less throughput. The objective is to retain the simplicity of the original Internet single-class best-effort service while providing low delay to interactive adaptive applications.

Network Calculus applied to Optimal Multimedia Smoothing
P. Thiran, J. Le Boudec and F. Worm
INFOCOM2001, Anchorage, 2001.
[full text] [view at publisher]

We consider a scenario where multimedia data are sent over a network offering a guaranteed service. A smoothing device writes the stream into a transmitting device with limited input buffer

Network Calculus
J. Le Boudec and P. Thiran
Lecture Notes in Computer Science; 2050, 2001.
[full text]

Network Calculus is a collection of results based on Min-Plus algebra, which applies to deterministic queuing systems found in communication networks. It can be used for example to understand - the computations for delays used in the IETF guaranteed service - why re-shaping delays can be ignored in shapers or spacer-controllers - a common model for schedulers - deterministic effective bandwidth and much more.

2000

ABE: Providing a Low Delay Service Within Best-Effort
P. Hurley, M. Kara, J. Le Boudec and P. Thiran
2000.

We propose Alternative Best-Effort (ABE), a novel service for IP networks, which retains the simplicity of the original Internet single class, best effort service, while providing low delay to interactive, adaptive applications. With ABE, applications choose between either a lower end-to-end delay or more overall throughput. Every best effort packet is marked as either green or blue. Green packets are guaranteed a low bounded delay in every router. In exchange, green packets are more likely to be dropped (or marked using congestion notification) during periods of congestion than blue packets. For every packet, the choice of one or other colour is done by the application, based on the nature of its traffic and on global traffic conditions. Typically, an interactive application with real-time deadlines, such as audio, will mark most of its packets as green, as long as the network conditions offer a large enough throughput. In contrast, an applications that is transferring binary data, such as bulk data transfer, will seek to minimise overall transfer time and send blue traffic. There is benefit for all traffic in that green traffic achieves a low delay and blue traffic receives at least as much throughput as it would in a flat, that is existing, best-effort network. The key feature of ABE is that neither packet colour can be said to receive better treatment, thus flat rate pricing may be maintained, and there is no need for reservations or profiles. ABE is thus different from differentiated or integrated services: it offers no priorities, reservations or guarantees, but it offers a new dimension to best-effort services. In this paper, we define the ABE service, its requirements, properties and usage. We discuss the implications of replacing the existing IP best effort service by the ABE service, and analyse in particular the relationship with TCP friendliness. We identify the ABE router requirements. We propose and implement a method for supporting the ABE service at the output port of a router. We discuss its algorithmic aspects and compliance to the ABE router requirements, and present initial simulation results.

Fault location algorithms for optical networks
C. Mas Machuca
2000.
[full text] [view at publisher]

Today, there is no doubt that optical networks are the solution to the explosion of Internet traffic that two decades ago we only dreamed about. They offer high capacity with the use of Wavelength Division Multiplexing (WDM) techniques among others. However, this increase of available capacity can be betrayed by the high quantity of information that can be lost when a failure occurs because not only one, but several channels will then be interrupted. Efficient fault detection and location mechanisms are therefore needed. Our challenge is to identify and locate failures (single or multiple) at the physical layer of an optical network in the presence of some lost and/or false alarms. After briefly introducing optical networks and the multiplexing techniques that can be used, we study the most common components and their most usual failures. We propose a classification of all the network components based on their behaviour when failures occur. This classification gives an abstract model of the optical network, which is appropriate for developing algorithms to locate faulty elements. Two algorithms that solve the fault location problem are proposed. Both algorithms cope with existence of false and missing alarms when locating single and multiple failures. The problem of locating multiple failures already in the absence of false or missing alarms, has been shown to be NP-complete. The first algorithm, which is called Alarm Filtering Algorithm (AFA) is based on the combination of two approaches: forward and backward. The forward approach returns for each network element, their domain, which is the set of network elements that will send an alarm when the considered element fails. The backward approach returns the set of elements that are directly related to the received alarms. In this approach, the alarms that are considered to provide redundant information, are discarded. The combination of the results given by both approaches allows the location of multiple failures, given an allowed number of false and missing alarms. However, this algorithm does not minimize the complexity when new alarms are received. Hence, a second algorithm, which is called Fault Location Algorithm (FLA), is proposed. The FLA concentrates the complexity in ,a pre-computation phase, so that when new alarms are received, the result of the algorithm is rapidly displayed. The FLA algorithm is based on the construction of a binary tree that realizes a non linear error correcting code. The FLA has also been extended to locate soft failures in addition to hard failures. Hard failures are unexpected failures, whereas soft failures are progressive failures due to equipment aging, misalignments or external factors such as temperature or pressure. Both algorithms are compared on some simulated networks using different network topologies and failure cases. The comparison has also be done on the basis of their worst case complexity. Some conclusions indication with which settings each algorithm perform the best, were obtained.

An efficient algorithm for locating soft and hard failures in WDM networks
C. Mas and P. Thiran
IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, 1900 - , 2000.
[full text] [view at publisher]

Fault identification and location in optical networks is hampered by a multitude of factors: (i) the redundancy and the lack of coordination (internetworking) of the managements at the different layers (WDM, SDH/SONET, ATM, IP)

An efficient Fault Localization Algorithm for IP/WDM Networks
C. Mas and P. Thiran
IEEE/ACM/SPIE Workshop on Optical Networks, University of Texas at Dallas, 2000.

We propose an algorithm for localizing multiple failures in an IP/WDM network. They can be either hard failures (unexpected events that interrupt suddenly the established channels) or soft failures (events that progressively degrade the quality of transmission). Hard failures are detected at the WDM layer, whereas soft failures can be detected at the optical layer if proper testing equipment is deployed, and/or by performance monitoring at a higher layer, which is here IP. The algorithm also tolerates missing and false alarms. Even without missing and false alarms, multiple fault localization is NP-hard. The diagnosis phase (i.e., the localization of the faulty components upon reception of the alarms) can however remain very fast, but at the expense of a very complex precomputation phase, carried out whenever the optical channels are set up or cleared down. We show how the algorithm performs on an example of an IP/WDM network.

A short tutorial on network calculus II: min-plus system theory applied to communication networks
J. Le Boudec, P. Thiran and S. Giordano
ISCAS 2000, Geneva, 2000.
[full text] [view at publisher]

A short tutorial on network calculus, part II

A short tutorial on network calculus I: fundamental bounds in communication networks
J. Le Boudec and P. Thiran
ISCAS 2000, Geneva, 2000.
[full text] [view at publisher]

A short tutorial on network calculus, part I