Direction des Relations Européennes et Internationales (DREI)

Programme INRIA "Equipes Associées"

 

I. DEFINITION

EQUIPE ASSOCIEE RESEAUXCOM
sélectionnée en
 2004

Projet INRIA : MASCOTTE, commun CNRS-I3S-INRIA Organisme étranger partenaire : Network Modelling Group, Simon Fraser University
Unité de recherche INRIA : Sophia Antipolis
Thème INRIA : Com B		 Pays : Canada
 
 
Coordinateur français
Coordinateur étranger
Nom, prénom Bermond, Jean-Claude Peters, Joseph
Grade/statut Directeur de recherches Professeur
Organisme d'appartenance
(précisez le département et/ou le laboratoire)		 CNRS Simon Fraser University
Adresse postale Projet Mascotte, commun I3S(CNRS/UNSA)-INRIA
INRIA Sophia-Antipolis
2004, route des Lucioles -- B.P. 93
06902 Sophia-Antipolis Cedex
France		 School of Computing Science
Faculty of Applied Sciences
Simon Fraser University
Burnaby, British Columbia V5A 1S6
Canada
URL http://www-sop.inria.fr/mascotte/ http://www.cs.sfu.ca/research/groups/NML/
Téléphone +33 (0)4 92 38 76 79 +1 604 291 3780
Télécopie +33 (0)4 92 38 79 71 +1 604 291 3045
Courriel Jean-Claude.Bermond@sophia.inria.fr peters@cs.sfu.ca

La proposition en bref
Titre de la thématique de collaboration (en français et en anglais):
Réseaux de Communications / Communication Networks
Thématique de la collaboration :

L'objectif de cette collaboration est de factoriser les connaissances des deux équipes pour la modélisation et la résolution des problèmes issus des télécommunications, dont un grand nombre sont issus de nos partenariats industriels (France Telecom, Alcatel, ...).
Nous souhaitons principalement nous concentrer sur deux types de réseaux, les réseaux dorsaux et les réseaux sans fil. En particulier nous étudions conjointement les problèmes de groupage de trafic et de tolérance aux pannes dans les réseaux dorsaux, de concentration de données dans les réseaux sans fils et de recherches de données dans les réseaux peer-to-peer.

Abstract :

This collaboration aims to share the expertise of both teams for modeling and solving telecommunication problems. Many problems are motivated by our industrial partners (France Telecom, Alcatel,...).
We plan to concentrate on both backbone networks and wireless networks. In particular intend to join forces on traffic grooming and survivability issues in backbone networks, gathering problems in wireless networks and data discovery in peer-to-peer overlay networks.



Présentation de l'Equipe Associée

1. Présentation du coordinateur étranger

Joseph Peters (born in 1951) earned his Ph.D. in Computer Science at the University of Toronto in 1984. He has been with the School of Computing Science at Simon Fraser University (SFU) near Vancouver since 1983 and has been a Professor since 1996. His current research interests are the modelling and analysis of communication protocols and networks. Previous research interests included parallel and distributed algorithms and topics in operations research and matroid theory. He has written approximately twenty-five papers on these subjects and has supervised ten theses during the last ten years. He has also held many administrative positions at SFU and he has been a member of several program committees. He has been in France numerous times including sabbatical years in Sophia Antipolis and Grenoble, and shorter visits to Sophia Antipolis, Grenoble, Orsay, Lyon, Bordeaux, Evry, and Nantes. He has been a rapporteur for many theses including eight French theses. He was a member of the external review team for Program 1A of INRIA in 2000.

2. Historique de la collaboration

3. Impact :

4. Divers : toute autre information que vous jugerez utile d'ajouter.

II. BILAN 2007

 

Scientific report for 2007

  • Survivability in WDM networks

    We finished our study on the problem of designing a survivable WDM network based on covering the communication requests with subnetworks that are protected independently from each other. The final version of the paper announced last year appeared in Networks in 2007 BeYu07. The subnetworks are chosen to be loops (cycles) in order to minimize the complexity of the routing problem with full survivability. The advantage is that a loop (cycle) is secured by its reverse loop. Given the failure of any single link, we can reroute the traffic going through the failed link via the other part of the cycle. (More precisely one can associate two wavelengths to each cycle of the covering: one for the normal traffic and another as a spare one.)

    The survivability problem mentioned above consists of finding a cycle partition or covering of the edges of I with an associated routing over the graph G which should satisfy the Disjoint Routing constraint, or DR constraint, i.e :the requests involved in a cycle of the covering are routed via vertex disjoint paths (equivalently, their routings form an elementary cycle in the physical graph G).

    The aim is to minimize the cost of the network; that is a very complex function depending on the size of the ADM's put in each node, the number of wavelengths (associated to the subnetworks) in transit in each optical node and a cost of regeneration and amplification of the signal. In a first approximation, some authors reduce it to minimize the number of cycles of the covering (which is related to the problem of minimizing the number of wavelengths used and the cost of transmission); other minimize the sum of the number of vertices of the rings; other insist on using very small cycles in the covering (short cycles are easier to manage and in case of failures, rerouting is easier). One can also want to minimize the total load (using or not shortest paths). We have obtained exact results when the logical graph I is Kn, which corresponds to the instance of communication called total exchange or all-to-all, where each vertex wants to communicate with all the others simultaneously. In particular we have extended the result of BCY03 obtained for the physical graph Cn, a cycle of length n to a torus T(n) of size n by n BeYu07.

  • Gathering in wireless networks

    The Wireless Gathering Problem is to find a schedule for data gathering in a wireless static network (call scheduling). One motivation came from the problem of designing efficient strategies to provide Internet access using wireless devices (problem asked by France Telecom). Typically, in one village several houses wish to access a gateway (a satellite antenna) and have to use multi-hop wireless relay routing to do so. This problem is also addressed in sensor networks where a base station has to collect data or to distribute tasks for sensor nodes.

    In particular we address the problem of gathering information in a specific node (or sink) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most dT in the graph, but when doing so it generates interference that does not allow nodes at distance up to dI (dI ≥ dT) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed.

    We pursued our research for the case dT = 1 and give algorithms and lower bounds on the minimum number of rounds for this problem, when the network is a path and the destination node is either at one end or at the center of the path. The algorithms are shown to be optimal for any dI in the first case, and for 1 ≤ dI ≤ 4, in the second case. Partial results were given in the conference BCY06. However the proof of improved lower bounds and exact values for dI=3,4 appeared to be more complicated than thought. Eventually, we succeed during the join visit of J. Yu and R. Correa in completing them and the full article has been submitted BCY07.

    With Joe Peters we considered the case of grids (toroidal and hexagonal). We obtained new results, but did not have time till now to finish the writing of the article.

    We also pursued our research (started with researchers of Salerno University) for trees, where have been able to find the value of the gathering time when there is no buffering at a node. With J. Yu we considered the case of buffering. We also determine the value in that case (surprisingly the methods used are completely different) and we are currently writing the proofs.We intend to finish this work in 2008 where we want also to extend the results.

  • How to retrieve a large file stored in a peer-to-peer overlay network ?

    During his stay in SFU (May 16th to June 16th 2006), M. Syska has started working with J. Peters on the problem of retrieving a large file (for example a video stream) stored in multiple locations in an overlay network. This work has been pursued with L. Stacho in Sophia Antipolis (visit of J. Peters and L. Stacho - July 2006), with J-C. Bermond during his stay in SFU (September 2006) and more recently with S. Pérennes and J. Peters (visit of S. Pérennes at SFU, June 10th to July 10th 2007).

    In this problem we consider a peer-to-peer overlay network in which a set of receivers want to stream some file (media object) which is replicated and stored in different servers nodes. The file is partitioned into a large number of equal-sized chunks. Each receiver requests to receive all the chunks in order. A chunk can arrive at a receiver before the time that it is needed and will be buffered. Our main constraint is to avoid gaps between chunks. In other words, a chunk must arrive no later than the time that the previous chunk in the sequence has been used (played back or listened to) to avoid jitter during play back. The objective is to minimize the makespan: time at which all the receivers have completed the reception of the last chunk of the sequence.

    In 2007, we worked on the streaming problem; we discarded the network flow approach and made some changes to the model. We regarded the network itself as a black box and analyzed what is essentially a streaming version of BitTorrent.

    We hope the current results will be improved with the help of simulation, as we will use this approach in the context of the new ANR SPREADS: Safe P2p-based REliable Architecture for Data Storage.

  • Neighbourhood Broadcasting in Hypercubes

    We finished in 2007 the work on this topic by writing the final version of the paper which should appear in 2007 BFPP07.

    In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbour at a time, broadcasting takes at least logc(N) rounds in a network of N nodes. In the neighbourhood broadcasting problem, the node that is broadcasting only needs to inform its neighbours. In a binary hypercube with N nodes, each node has log2(N) neighbours, so neighbourhood broadcasting takes at least log logc(N+1) rounds. In BFPP07 we present asymptotically optimal neighbourhood broadcast protocols for binary hypercubes.

 

Rapport financier 2007

1. Dépenses EA (effectuées sur les crédits de l'équipe associée)
 
Budget EA alloué
Montant dépensé
Accueil   2800€
Missions   5630€
Total
 (a) 4000+4500=8500€ (b) 8430€
Taux d'utilisation des crédits EA alloués (b/a %)
 100%

 

2. Dépenses externes (soutenues par des financements hors EA)
 
Budget alloué
Montant dépensé
Nom de l'organisme 1 (*): MASCOTTE
Accueil   3860€
Missions   2360€
Total
   6220€
Nom de l'organisme 2 (*): SFU
Accueil   2000€ 
Missions   5400€
Total
   7400€

Total des financements externes

alloués : (c)

dépensés : 13620€

(*) Ajouter ou supprimer des lignes au tableau ci-dessus de faÇon à faire figurer tous les organismes ayant contribué au financement de l'équipe associée

Total des financements EA et externes

alloués : (d)

dépensés : 22050€

Taux de co-financement (c /d %)

62%

Bilan des échanges effectués en 2007


1. Seniors

Nom
statut (1)
 provenance
destination
objet (2)
durée (en semaines)
Coût (EA)
Coût (externe)
M. Cosnard Pr Sophia Antipolis SFU Visite 3 5630€
S. Perennes CR CNRS Sophia Antipolis SFU Visite 4 2360€ (Mascotte) + 2000€ (SFU)
J. Peters Pr SFU Sophia Antipolis Visite 3 1800€ 1200€ (SFU)
L. Stacho A-Pr SFU Sophia Antipolis Visite 2 1000€ 1200€ (SFU)
J. Yu A-Pr SFU Sophia Antipolis Visite 12 3860€ (Mascotte)
3000€ (SFU)

Total des durées en semaines
  24
(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....

2. Juniors

(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....

 

III. PREVISIONS 2008

Programme de travail

 

This collaboration aims to share the expertise of both teams for modeling and solving telecommunication problems. Many problems are motivated by our industrial partners (France Telecom, Alcatel,...).
We plan to concentrate our work in 2008 on 3 subjects on both wireless, peer to peer and WDM networks as described below.

  1. Wireless Gathering Problem

    We intend to pursue our join research done during the preceding years (see report above) on the Wireless Gathering Problem which consists of finding a schedule for data gathering in a wireless static network (call scheduling). One motivation came from the problem of designing efficient strategies to provide Internet access using wireless devices (problem asked by France Telecom). Typically, in one village several houses wish to access a gateway (a satellite antenna) and have to use multi-hop wireless relay routing to do so. This problem is also addressed in sensor networks where a base station has to collect data or to distribute tasks for sensor nodes.
    In particular, with Joe Peters we want to finish the case of grids (toroidal and hexagonal). Some details for a complete proof are missing and we want also to determine where is the best location of the base station.
    With J. Yu we want to finish the work started in 2007 concerning algorithms and exact values of the gathering time in a tree with possible buffering in the nodes.We think to have the complete solution for the case dT=dI=1. It will be nice to extend the results and perhaps find a polynomial algorithm for trees and any values of dI or at least a 1-approximation algorithm.
    Finally we intend to consider the cases where some nodes fail either permanently (sensors with no more battery) or intermittently (computers shut off).
    Also it will be interesting to design distributed algorithms.

  2. How to retrieve a large file stored in a peer-to-peer overlay network ?

    We will persue our research on the problem of retrieving a large file (for example a video stream) stored in multiple locations in an overlay network.
    In this problem we consider a peer-to-peer overlay network in which a set of receivers want to stream some file (media object) which is replicated and stored in different servers nodes. The file is partitioned into a large number of equal-sized chunks. Each receiver requests to receive all the chunks in order. A chunk can arrive at a receiver before the time that it is needed and will be buffered. Our main constraint is to avoid gaps between chunks. In other words, a chunk must arrive no later than the time that the previous chunk in the sequence has been used (played back or listened to) to avoid jitter during play back. The objective is to minimize the makespan: time at which all the receivers have completed the reception of the last chunk of the sequence.

    We intend to improve the current results with the help of simulation. Also, we plan to use this approach in the context of the new ANR SPREADS: Safe P2p-based REliable Architecture for Data Storage.

  3. WDM DAG Networks

    During his visit to Vancouver, M. Cosnard started a work with J. Peters to extend some results of the article BeCo07. In this article we characterized the DAGs (Directed acyclic graphs) for which the minimum number of colors (wavelengths) needed to color the paths associated to requests is equal to the load. We found during the cooperation efficient algorithms to attribute the wavelengths for trees and DAGs without internal cycles. We should continue the work by studying more deeply the class of DAGs with a unique path between any pair of vertices (called UPP graphs). We will also try to tackle the conjecture stating that for any DAG and for the particular case where the set of requests is All-to-All, the minimum number of wavelengths is equal to the load.



Budget prévisionnel 2008

1. Co-financement

ESTIMATION PROSPECTIVE DES CO-FINANCEMENTS
Organisme
Montant
MASCOTTE 16000€
SFU 10000€
Total
26000€

2. Echanges

ESTIMATION DES DEPENSES
Montant
 
Nombre
Accueil
Missions
Total
Chercheurs confirmés 5 10000€ 15000€ 25000€
Post-doctorants
        
Doctorants 1   3000€ 3000€

Stagiaires

1 (*)   6000€ 6000€
Autre (précisez) :
        
Total
 8 10000€ 24000€ 34000€
   
- total des co-financements
 25000€
  Financement "Equipe Associée" demandé 11000€ (*)


Remarques ou observations :

(*) We plan that Dorian Mazauric will do his Master Internship part time in Mascotte and part time in SFU (at least 2 months). So we ask exceptionnal funding for him.  

 

 

© INRIA - mise à jour le 22/10/2007