Sites Inria

Version française

RAP Research team

Networks, Algorithms and Probabilities

  • Leader : Philippe Robert
  • Research center(s) : CRI de Paris
  • Field : Networks, Systems and Services, Distributed Computing
  • Theme : Networks and Telecommunications

Team presentation

The RAP project-team (Networks Algorithms and Probability) investigates the design and the analysis of the algorithms in communication networks. It has a strong collaboration with the research group of Orange Labs in Lannion led by F. Guillemin. Since the data traffic is deeply statistical, the probabilistic aspect of this studies is the major research theme of RAP. The variability of the traffic and its impact on the design of the architectures of networks and of the algorithms are a major issue in the studies of the Internet.
The RAP project-team combines algorithmic analysis and probabilistic studies to design simple and scalable algorithms in communication networks.

Research themes

The main research areas

1. Design of Algorithms for Content Centric Networks
2. Algorithms for Bandwidth Allocation in Optical Networks
3. Study of Large Stochastic Networks

Design of Algorithms for Content Centric Networks.
RAP is contributing to the definition and evaluation of a new paradigm for the future Internet: a content-centric network (CCN) where, rather than interconnecting remote hosts like IP, the network directly manages the information objects that users publish, retrieve and exchange. We are building on existing CCN proposals, adopting as a starting point the concept currently promoted by Van Jacobson at the Palo Alto Research Center (PARC) ( Security concerns are addressed at the content level, relaxing requirements on hosts and the network. Users no longer need a universally known address, greatly facilitating management of mobility and intermittent connectivity. Content is supplied under receiver control, limiting scope for denial of service attacks and similar abuse. Since chunks are self-certifying, they can be freely replicated, facilitating caching and bringing significant bandwidth economies. CCN applies to both stored content and to content that is dynamically generated, as in a telephone conversation, for example. The project aims to complement the existing work on CCN with original proposals in the following three technical areas.
  • Traffic control must be completely rethought: TCP is no longer applicable and queue management will require new, name-based criteria to ensure fairness and to realize service differentiation.
  • Naming, routing and forwarding are partially addressed in the PARC proposal. However, choices are often expedients to facilitate overlay implementation. It is necessary to prove the name-based routing and forwarding is scalable and to design algorithms suitable for full-scale implementation.
  • CCN trades off expensive bandwidth for cheap memory as content chunks can be cached within the network, avoiding the need to repeatedly fetch copies of popular items. It largely remains to define replication and caching strategies and to evaluate their performance.

Study of Large Stochastic Networks
As the complexity of communication networks increases (and, consequently, the algorithms regulating them), the classical mathematical methods used to estimate the stationary behavior, the transient behavior show more and more their limitations. For a one/two-dimensional Markov process describing the evolution of some network, it is sometimes possible to write down the equilibrium equations and to solve them. When the number of nodes is more than 3, this kind of approach is not, in general, possible. The key idea to overcome these difficulties is to consider limiting procedures for the system: by considering the asymptotic behavior of the probability of some events like it is done for large deviations at a logarithmic scale or for heavy tailed distributions, or looking at Poisson approximations to describe a sequence of events associated to them. by taking some parameter of the model and look at the behavior of the system when it approaches some critical value. In some cases, even if the model is complicated, its behavior simplifies in the neighborhood of the critical parameter: some of the nodes grow according to some classical limit theorem and the rest of the nodes reach some equilibrium which can be described. by changing the time scale and the space scale with a common normalizing factor N and let N goes to infinity. The list of possible renormalization procedures is, of course, not exhaustive. But for the last ten years, this methodology has become more and more developed. Its advantages lies in its flexibility to various situations and also to the interesting theoretical problems it has raised since then.

International and industrial relations

CRE with Orange Labs ``Algorithmes d'allocation de ressources dans les r\'eseaux optiques''. Contract on bandwidth allocation algorithm in optical networks. Two years starting from 2009

ANR Project ``CONNECT: Content-Oriented Networking: a New Experience for Content Transfer''. The proposal submitted to the VERSO programme has been accepted. The planned starting date is January 2011 and the project is scheduled to last 2 years. The lead partner is Alcatel Lucent Bell Labs France and the other partners are RAP, INRIA/PLANETE, Orange LAbs, TelecomParisTech, UPMC.

Keywords: Networks Stochastic Models Optical Networks Design of Algorithms for Content Centric Networks