Infrastructure adaptation and emergence of loops in network routing with time-dependent loads

Abstract

Network routing approaches are widely used to study the evolution in time of self-adapting systems. However, few advances have been made for problems where adaptation is governed by time-dependent inputs. In this work, we study a dynamical systems where the edge conductivities – capacities – of a network are regulated by time-varying mass loads injected on nodes. Motivated by empirical observations, we assume that conductivities adapt slowly with respect to the characteristic time of the loads. Furthermore, assuming the loads to be periodic, we derive a new dynamics where the evolution of the system is governed by a matrix obtained with the Fourier coefficients of the input loads. Remarkably, we find a sufficient condition on these coefficients that determines when the resulting network topologies are trees. We show an example of this on the Bordeaux bus network where we tune the input loads to interpolate between loopy and tree topologies. We validate our model on several synthetic networks and provide an expression for long-time solutions of the original conductivities, supported by numerical observations and analytical arguments.

Publication
Submitted
Alessandro Lonardi
Alessandro Lonardi
PhD student

The main focus of my current research is studying routing problems combining approaches stemming from optimal transport and belief propagation. In particular, I am interested in understanding how different route selection mechanisms affect traffic and total path length of networks. The applications of my work span from urban to biological networks. Previously I was a Master’s Student in Mathematical Engineering at UniPd (Padua, Italy), where I also obtained my Bachelor’s degree in Physics.

Caterina De Bacco
Caterina De Bacco
CyberValley Research Group Leader

My research focuses on understanding, optimizing and predicting relations between the microscopic and macroscopic properties of complex large-scale interacting systems.

Related