Publications by Patrick Thiran

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

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

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, w ...

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 effi

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 o ...

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 becaus

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 c ...

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 missi

We present Asymmetric Best-Effort (ABE), a novel service to provide a throughput versus delay jitter service for IP packets. With this service, every best effort packet is marked as either Green or Blue. Green packets, typically sent by real-time applications such as interactive audio, receive more losses during bouts of congestion than Blue ones. In return, they receive a smaller bounded queueing delay. Both Green and Blue services are best-effort. The incentive to choose one or other is based on the natur

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 f

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-t

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 ana

This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the Stochastic Block Model (SBM), which assumes uniform vertex degrees, and to the Degree-Corrected Block Model (DCBM), which applies uniform degree corrections across clusters, PABM introduces separate popularity parameters for intra-and inter-cluster connections. Our main contribution is the characterization of the optimal error rate

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 w ...

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

In order to better understand the high complexity of the brain, the detailed study of its individual components clearly seems insufficient. The backbone of complexity in the nervous system is composed of the large scale architectural characteristics of the neuronal network. Newly, by the advent of MR tractography, its investigation is accessible. We report on two important network characteristics that were already guessed from functional investigations and animal ex vivo studies, but never directly addresse

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-

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

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

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, effic ...

Patrick Thiran

Chat with Graph Search

Interval consensus: from quantized gossip to voting

Learning Hawkes Processes from a Handful of Events

Layered Complex Networks

Preferential Treatment of Acknowledgment Packets in a Differentiated Services Network

The Boolean Solution to the Congested IP Link Location Problem: Theory and Practice

A Measurement-Based Algorithm to Maximize the Utility of Wireless Networks

EZ-Flow: Removing Turbulence in IEEE 802.11 Wireless Mesh Networks without Message Passing

An efficient Fault Localization Algorithm for IP/WDM Networks

The Asymmetric Best-Effort Service

Survivable MApping Algorithm by Ring Trimming (SMART) for large IP-over-WDM networks

A flow-based model for TCP traffic in an IP backbone network

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol (Technical Report)

Optimal Graph Clustering without Edge Density Signals

Error and Attack Tolerance of Layered Complex Networks

A User Study of Perceived Carbon Footprint

Imaging the brain neuronal network with diffusion MRI: a way to understand its global architecture

Reaction-Diffusion Based Transmission Patterns for Ad Hoc Networks

Self-Synchronizing Properties of CSMA Wireless Multi-hop Networks

How CSMA/CA With Deferral Affects Performance and Dynamics in Power-Line Communications

Sub-Matrix Factorization for Real-Time Vote Prediction