I have two main directions of research:
- IP network congestion control, and particularly TCP type control protocols, both in the point to point and the multicast cases;
- Network tomography and in particular methods aiming at reconstructing the state of a network from measurements made by probes.
CONGESTION CONTROL IN IP NETWORKS
The TCP protocol, which is the key control mechanism used in the Internet, is decentralized, simple and efficient. Here are the main results of our efforts to propose mathematical models for this type of control.
Several workshops were organized on the modeling of TCP at Ecole Normale Supérieure, The following pages contain the programs of these workshops together with several papers on the mathematical modelling of TCP:
- PACKET LEVEL MODELS. These models are in principle equivalent to those obtained by discrete event simulation.
For a survey on the early packet level models, here are the slides of a course taught at the Madison Workshop on Stochastic Networks in June 2000: Part I, Part II, Part III, Part IV
- SINGLE CONNECTION, SEVERAL LINKS, POINT TO POINT. As shown with D. Hong in a ACM-SIGCOMM 2000 paper, TCP admits a quite simple representation as a (max,plus) linear dynamical system (RR-3986). This leads to new ways for computing the throughput and to new simulation methods. This paper is also the basis of the work on multicast quoted below.
- SINGLE CONNECTION, SEVERAL LINKS, MULTIPOINT. When based on feedbacks sent by all receivers of a large reliable multicast group, a TCP like congestion control mechanism cannot work well, even when the classical implosion problem is solved by partial aggregation of the feedback signals along the multicast tree. Jointly with Augustin Chaintreau and Christophe Diot (when he was with Sprint), we showed that even with light tailed randomness in the delays through the routers, the throughput decreases like the inverse of the logarithm of the number of receivers. Our paper (RR-3987) on the matter was presented at INFOCOM 2001. A more promising solution for reliable IP multicast is that based on overlays. Jointly with Augustin Chaintreau and Zhen Liu of IBM Research, we proposed a multicast architecture that we called the One to Many TCP Overlay (RR-5241). Two versions of this architecture were studied: that without backpressure, which was presented at Infocom 2004, and that with backpressure, presented at Infocom 2005. In both cases, we showed that this solution potentially scales to an infinite number of receivers. For more on the matter, see the thesis of Augustin Chaintreau.
- SEVERAL CONNECTIONS, SEVERAL LINKS. The mathematical modelling of the interaction of TCP and UDP flows that we started with T. Bonald (France Telecom R&D) bears on the analysis of the throughput obtained by the TCP connection (RR-3434). Some rather suprising results are found out: the throughput obtained by the TCP connection is neither monotonous nor convex in the send rate of the UDP flows with which it shares the routers: decreasing the send rate of the UDP floes and/or shaping them may result in a decrease of the throughput obtained by the TCP connection.
- HYBRID MODELS. These models combine fluid dynamics and discrete event dynamics. They are linked to transport PDEs as shown in the Questa 2007 paper with David Mc Donald (University of Ottawa) and K. B. KIM.The statistical properties of TCP traffic are among the questions which can be investigated using these hybrid models. In particular, the fractal scaling of aggregated TCP traffic as observed on real traces can be explained by a simple model of the Additive Increase Multiplicative Decrease algorithm, as shown in the AIMD papers. For more on this class of hybrid models, see the aimd web page .
This line of thoughts on hybrid models is continued by the start-up N2NSoft, created by D. Hong , with which I collaborate. The Netscale simulation tool, which is dedicated to the analysis of large IP networks and which is partly based on this modeling approach, was succesfully used for the design of DSLAMs.
- SINGLE CONNECTION, POINT TO POINT. Analysis of Scalable TCP, DOI-10.1109/INFCOM.2009.5061902, with Giovanna Carofiglio and Marta Piancino, presented at Infocom 2009. Analysis of Split TCP in DOI-10.1109/INFOCOM.2008.35 with Giovanna Carofiglio and Serguei Foss, presented at Infocom 2008.
- SEVERAL CONNECTIONS, SINGLE LINK. Together with D. Hong , we introduced a new model for the many-connection case, which was presented at INFOCOM 2002 (AIMD paper). This model reduces the sharing of a bottleneck router by several long lived TCP connections to products of random matrices in the conventional algebra. This line of thought is pursued by the group around Robert Shorten and Douglas Leith at the Hamilton Institute.
- LARGE NUMBER OF CONNECTIONS, SINGLE LINK. Jointly with David Mc Donald (University of Ottawa) and Julien Reynier (ENS), we studied a mean field model for RED that leads to the study of a class of non local PDEs: RR-4449. This line of thoughts was recently extended to the case of on-off flows in a series of papers. The first one RR-5205 (presented at Sigmetrics 2004), is focused on the potential consequences of the in-phasing of the flows; the two others (RR-5301, which was presented at Euro NGI 2005) and RR-5653. These papers are based on collaborations with A. Chaintreau, D. De Vleeschauwer and D. Mc Donald
- LARGE NUMBER OF CONNECTIONS, SEVERAL LINKS. The multi-link extension of the aimd model is considered in the paper "Interaction of TCP Flows as Billiards", RR-4437, the final version of which was published in 2005 by IEEE Transactions on Networking.
- RESIDUAL BANDWIDTH ESTIMATION: we considered multihop available bandwidth estimation using the EM algorithm in doid-1639562.1639597, with B. Kauffmann and Darryl Veitch at Sigmetrics'09.
- NETWORK TOMOGRAPHY AS INVERSE PROBLEMS: Internet probing as inverse problems in queueing theory: DOI-10.1007-s11134-009-9150-9, with B. Kauffmann and Darryl Veitch . This is an invited paper of the special issue of Queuing Systems on the Erlang Centenial in 2009.
- OPTIMAL PROBING FOR DELAY AND LOSS MEASUREMENT: doid-1298306.1298346, with Sridhar Machiraju, Darryl Veitch and Jean Bolot. This was presented at IMC '07.
- DESIGN OF EXPERIMENTS: we addressed the question of the optimal way to send probes in doid-1159913.1159940, with Sridhar Machiraju, Darryl Veitch and Jean Bolot. This was presented at Sigcomm 06.Last revised: July, 2011.