Hamilton-Jacobi equations on networks
The research focuses on some open questions concerning both modeling and performance analysis of active networks for Internet access or other traffic models where the behavior of each single node depends on the locally acquired information and the information distributed in the other nodes.
The research activity aims to:
1) model the access network via a MFG model defined on a suitable graph, where each edge is characterized by a couple of differential-type equations (of Hamilton-Jacobi-Bellman type and Transport type) describing the optimal instantaneous uploaded/downloaded/relayed traffic flows, and each queue-equipped node introduces a transition condition reflecting the local information flow across the node.
2) Extend the theory of MFGs to graphs in order to prove existence, uniqueness and stability results for the solution of the resulting system of partial differential equations
3) Solve via numerical algorithms the MFG system on the graphs and prove the convergence of the schemes.
State of the art:
Several phenomena in physics, chemistry and biology described by interaction of different media can be translated into mathematical problems involving differential equations which are not defined on connected manifolds as usual, but instead on so-called ramified spaces. The latter can be roughly visualized as a collection of different manifolds of the same dimension (branches) with certain parts of their boundaries identified (ramification space).
The simplest examples of ramified spaces are networks, which basically are topological graphs embedded in the Euclidean space. The interaction among the collection of differential equations describing the behaviour of the physical quantities on the edges is described by certain transition conditions governing the interaction of the quantities across the nodes.
From a mathematical point of view, the concept of ramified spaces has originally been introduced by Lumer (CRAS 1980) and many results have been published treating different kinds of interaction problems involving linear and semi-linear differential equations.
The study of fully nonlinear equations on networks has recently started in two main directions. From one side conservation laws on a network as a model for the traffic flow of cars on roads with junctions has been extensively studied both from theoretical point of view and from a numerical one (see Coclite-Garavello-Piccoli SIMA 2006).
On the other side the shortest path problem, or also more general control problem, on a network in which the running cost varies in a continuous way
along the arcs give raise in a natural way to the study of Hamilton-Jacobi equations on this geometric structure. Hamilton-Jacobi equations and the corresponding extension of the theory of viscosity solutions to networks have been considered in some recent papers (Camilli-Schieborn 2012, Imbert-Zidani-Monneau 2011).
From a mathematical point (for the several applications of MFG to networks we refer to Palermo's unit project) the study of MFGs on networks has recently initiated by Gueant for the case of a finite state-continuous time model problem. Even if this model already contains interesting peculiarity with respect to the corresponding problem in the Euclidean space, it seems not suitable to describe peculiar effects of traffic flow on networks involving for example congestion along the edges, shocks formation, traffic lights delays at the nodes, overload delays, etc.
Extending continuous time-continuous state MFGs to networks involves the study of a coupled system of a Hamilton-Jacobi equation for the value function and of a conservation law for the distribution. For each of the two types of equations a suitable theory has been already developed, as explained before. For the coupled system the crucial point is to find the appropriate transition condition to impose at the vertices of the graph
for which the two previous theories can be simultaneously applied. It is worth noticing that different transition conditions can model different effects at the nodes. The simplest condition is the conservation of the mass distribution flowing across a vertex, but for example a cross-light traffic model can be obtained prescribing suitable periodic functions at the nodes.
In principle, an appealing strategy for delivering media contents to/from end-users of internet system is to exploit in a cooperative way the peer-to-peer nature of the overall network. The MFG model approach takes into account in a natural way this peculiarity of the internet network.
However, this approach presents still open challenges at multiple levels, basically arising from the: i) randomly time-varying nature of the topology of the internet access network; ii) heterogeneous up/downloading and processing capabilities of the nodes; and iii) heterogeneous levels of media quality requested by users. Hence, the research activity of
the unit aims to model the evolution of the topology of the network via a robust MFG approach, and then, to exploit the resulting model to design topology constrained content-delivery strategies.
1. G.Lumer, Espaces ramifiés, et diffusions sur les réseaux topologiques. (French) C. R. Acad. Sci. Paris Sér. A-B 291 (1980), no. 12, A627–A630.
2. Coclite, G. M.; Garavello, M.; Piccoli, B. Traffic flow on a road network. SIAM J. Math. Anal. 36 (2005), no. 6, 1862–1886.
3. D.Schieborn and F. Camilli, Viscosity solutions of Eikonal equations on topological network, arXiv:1103.4041v1, to appear on Calc. Var. Partial Differential Equations.
4. C. Imbert, R. Monneau and H. Zidani, A Hamilton-Jacobi approach to junction problems and application to traffic flows, arXiv:1107.3250, 2011.
5. O.Gueant, An existence and uniqueness result for mean field games with congestion effect on graphs, arXiv:1110.3442.