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 2006

 

Scientific report, 2004-2006

In this section, we review the results obtained jointly during the last 3 years.

  • WorkshopJCB60

    We organized the workshop JCB60 in honor of the 60th birthday of Jean-Claude Bermond, december 8-9 2005 in Sophia Antipolis. The scientific program can be found here. In particular, we had two communications from members of this EA:

    • Joseph G. Peters: Communication Graphs.
    • Frédéric Havet: Design of fault tolerant on-board networks


  • Survivability in WDM networks

    We study the problem of designing a survivable WDM network based on covering the communication requests with subnetworks that are protected independently from each other. 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 BeYu06.

  • Traffic grooming

    We have addressed the problem of traffic grooming in WDM rings or paths with All-to-All uniform unitary traffic. The goal is to minimize the total number of SONET add-drop multiplexers (ADMs) required. We have shown that this problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges (where C is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for C=5 in BCLY04.

  • 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. In BeYu06, BCY06 and BCY06b , we consider the case dI = 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. In BePe05 and BePe06 we give optimal algorithms still for dT = 1 but for grids.

    We are currently (with researchers in Salerno University) looking in more details at the case dI = dT = 1 where we have a polynomial algorithm in trees and hope to extend it to general graphs. this leads us to introduce the notion of gather-center of a graph.

  • 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) and with J-C. Bermond during his stay in SFU (September 2006).

    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.

    A first solution based on graph matching has been implemented with the mascopt optimization library. Experimental results proved that the critical point is the buffer space allowed at receiver nodes and we keep on working on the algorithm.

  • Constructing incremental sequences in graphs

    Given a weighted graph G=(V,E,w), we investigate in KLPT06 the problem of constructing a sequence of n=|V| subsets of vertices M1,...,Mn (called groups) with small diameters, where the diameter of a group is calculated using distances in G. The constraint on these n groups is that they must be incremental: Mi is included in Mi+1.

  • Neighbourhood Broadcasting in Hypercubes

    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 BFPP06 we present asymptotically optimal neighbourhood broadcast protocols for binary hypercubes.

 

Rapport financier 2006

1. Dépenses EA (effectuées sur les crédits de l'équipe associée)
 
Budget EA alloué
Montant dépensé
Accueil   3500€
Missions   6500€
Total
 (a) 10000€ (b) 10000€
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   1520€
Missions   3800€
Total
   5320€
Nom de l'organisme 2 (*): SFU
Accueil    
Missions   6000€
Total
   6000€

Total des financements externes

alloués : (c)

dépensés : 11320€

(*) 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 : 21320€

Taux de co-financement (c /d %)

53%

Bilan des échanges effectués en 2006


1. Seniors

Nom
statut (1)
 provenance
destination
objet (2)
durée (en semaines)
Coût (EA)
Coût (externe)
J-C. Bermond DR Sophia Antipolis SFU Visite 2 3800€ (Mascotte)
M. Syska A-Pr Sophia Antipolis SFU Visite 4 6500€
J. Peters Pr SFU Sophia Antipolis Visite 4 2200€ 660€ (Mascotte)
1200€ (SFU)
L. Stacho A-Pr SFU Sophia Antipolis Visite 3 1300€ 1800€ (SFU)
J. Yu A-Pr SFU Sophia Antipolis Visite 4 860€ (Mascotte)
3000€ (SFU)

Total des durées en semaines
  17
(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 2007

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 on both backbone networks and wireless networks as described below. Notice that the solution developped here may be used in other contexts.

  1. Traffic grooming

    See [HPS02] [BPS02] [BDPS03] [BCY03] [BeCe03] [BeCo03] [BCM03] [GHLO03] [BCLY04] [BBC05] [BCC+05] [CDR05] [FMSZ05] [BeCo06] [BCCP06] [BCMS06] [HDR06] [FMSZ06] [FSZ06a] [FSZ06b]

    In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes).

    The traffic grooming problem is to minimize the total number of SONET add-drop multiplexers (ADMs) required. We have addressed this problem in WDM rings or paths with All-to-All uniform unitary traffic using tools of graph and design theory (see for example [BCLY04] and [BeCo06]). Approximation algorithms for general traffic patterns have also been developped [GHLO03] [FSZ06a] but are far from practical solutions. Thus we aim to develop algorithmic solutions allowing to compute efficiently optimal or near optimal solutions.

  2. Survivability in backbone networks

    See [GuPe99] [MaSt99] [BCCT01a] [BDD02] [DaSo04] [BCY03] [JVY05] [Lep05] [BeYu06] [CDP+06] [CPRV06] [GMS06] [Far06]

    We intend to consider jointly various problems in survivability. A first problem studied in Mascotte concern Shared Risk Resource groups, that is groups of resources (set of nodes or links) that fails simultaneously. This concept has been modelled with colored graphs where edges of the same color belong to the same group of risk. In this context we minimize the risk of failure of a path by minimizing its number of colors. Unfortunately, computing such a path is in general NP-hard and difficult to approximate (see CDP+06 for a survey on complexity and approximability issues in this context). Fortunately we were able to identify some polynomial cases [CPRV06]. We shall now continue to identify cases that are polynomialy tractable.

    Another measure of fault tolerance introduced by researchers at S.F.U. [GMS06] consists of asking each request to be routed via f + 1 vertex disjoint paths. So, the network can tolerate f faults. One can generalize the classical notions of load and optical index and define the f-load and the f-optical index; for example the f-optical index is the minimum number of wavelengths to be assigned to the paths associated to the requests in order that no two paths that share an arc receive the same wavelength. In the internship done in Mascotte [Lep05], these parameters are determined for the complete graphs and partly for other topologies like tori and bipartite complete graphs when the set of requests is All to All. The proofs need construction of specific idempotent orthogonal latin squares. We intend to pursue the research on this topic where many problems are still open; for example it will be interesting to determine, if the result, for f=0, that for multicast the f-optical index is equal to the f-load is still valid for any f.

  3. Wireless Gathering Problem

    See [Hav01] [GvPe01] [GaOl01] [FGPR01] [FeKr01] [HaYu02] [HaZe02] [CHRV03] [FFM04] [BePe05] [BePe06] [BCY06] [BCY06b] [BeYu06] [BKMS06] [BKMS06] [GaRe06]

    We intend to pursue our join research 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 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.

    In BeYu06, BCY06 and BCY06b , we consider 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. In BePe05 and BePe06 we give optimal algorithms still for dT = 1 but for grids.

    We are currently (with researchers in Salerno University [GaRe06]) looking in more details at the case dI = dT = 1 , where we think to have a polynomial algorithm in trees and hope to extend it to general graphs. This leads us to introduce the notion of gather-center of a graph. We also want to extend to bigger dI, still with dT = 1, but in the uniform case (one message to gather from each node). The problem seems solvable at least with the assumption that nodes cannot buffer information and a packet must be forwarded immediately after receiving it. In the general case it will be interesting to get a 1-approximation algorithm for trees. Finally we intend to consider the cases where some nodes fail either permanently (sensors with no more battery) or intermittently (computers shut off).

  4. 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) and with J-C. Bermond during his stay in SFU (September 2006).

    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.

    A first solution based on graph matching has been implemented with the mascopt optimization library. Experimental results proved that the critical point is the buffer space allowed at receiver nodes and we keep on working on the algorithm.



Budget prévisionnel 2007

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 6 15000€ 15000€ 30000€
Post-doctorants
        
Doctorants 2   6000€ 6000€

Stagiaires

       
Autre (précisez) :
        
Total
 8 15000€ 21000€ 36000€
   
- total des co-financements
 26000€
  Financement "Equipe Associée" demandé 10000€


Remarques ou observations :

 

 

 

© INRIA - mise à jour le 20/10/2005