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

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

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, bu

Alternative Best-Effort (ABE) is a novel service for IP networks which offers applications the choice between receiving a lower end-to-end delay and receiving more overall throughput. Every best effort packet is marked as either green or blue. Green packets receive a low, bounded queueing delay. To ensure blue packets do not suffer as a result, green flows receive less throughput during bouts of congestion. The unique combination of lower delay with reduced throughput for green makes it different from recen

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

The Susceptible-Infected-Susceptible (SIS) model is a widely used model for the spread of information and infectious diseases, particularly nonimmunizing ones, on a graph. Given a highly contagious disease, a natural question is how to best vaccinate individuals to minimize the disease's extinction time. While previous works showed that the problem of optimal vaccination is closely linked to the NP-hard Spectral Radius Minimization (SRM) problem, they assumed that the graph is known, which is often not the

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

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

Some recent papers [KMT97, MR98] have shown that congestion control based on additive increase and multiplicative decrease tends to share bandwidth according to proportional fairness. Proportional fairness is a form of fairness which distributes bandwidth with a bias in favour of flows using a smaller number of hops, this is in contrast with max-min fairness, which gives absolute priority to small flows. We revisit those results by using the modelling framework based on the ordinary differential equation me

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

Some recent papers have shown that congestion control based on additive increase and multiplicative decrease tends to share bandwidth according to proportional fairness. Proportional fairness is a form of fairness which distributes bandwidth with a bias in favour of flows using a smaller number of hops; this is in contrast with max-min fairness, which gives absolute priority to small flows. We revisit those results by using the modelling framework based on the ordinary differential equation method in [LJU77

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

We analyze some queueing problems arising in guaranteed service and controlled load networks using min-plus algebra. We find an explicit representation for the sub-additive closure of the minimum of two operators, and we introduce a new, useful family of idempotent, time-varying, and min-plus linear operators. We model queueing systems arising in networks networks as non-linear min-plus systems that can be bounded by linear systems, and apply our concepts to: the optimal shaper studied by Anantharam and Kon

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

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

We present Asymmetric Best-Effort, a novel service to provide a ``throughput versus delay jitter'' differentiated 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 less delay jitter. Both green and blue services are best-effort. The incentive to choose one or other is based on the nature

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

Patrick Thiran

Chat with Graph Search

ABE: Providing a Low Delay Service Within Best-Effort

Fairness of MAC protocols: IEEE 1901 vs. 802.11

Understanding and Tackling the Root Causes of Instability in Wireless Mesh Networks: (extended version)

The Alternative Best-Effort Service

The Alternative Best Effort Service

Back to the Source: an Online Approach for Sensor Placement and Source Localization

Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control

Sequential metric dimension for random graphs

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

A Note on the Fairness of Additive Increase and Multiplicative Decrease

The Fairness of Additive Increase and Multiplicative Decrease

Optimal Number of Paths with Multipath Routing in Hybrid Networks

A Note on the Fairness of Additive Increase and Multiplicative Decrease

Disparity Between Batches as a Signal for Early Stopping

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol

Network Calculus viewed as a Min-plus System Theory applied to Communication Networks

Measurement and Analysis of Single-Hop Delay on an IP Backbone Network

A Variational Inference Approach to Learning Multivariate Wold Processes

The Asymmetric Best-Effort Service

Mining Democracy