Activités

• Activity report for 2008 and proposal for 2009
• Activity report for 2007 and proposal for 2008
• Activity report for 2006 and proposal for 2007
• Activity report for 2005 and proposal for 2006
• Activity report for 2004 and proposal for 2005

1. Wireless Gathering Problem

   We have conducted joint research during the preceding years (see reports) on the Wireless Gathering Problem which consists of finding a schedule for data gathering in a wireless static network (call scheduling). Some of the motivation for this research comes from the problem (proposed by France Telecom) of designing efficient strategies to provide Internet access using wireless devices. Typically, several houses in a village wish to access a gateway (a satellite antenna) and have to use multi-hop wireless relay routing to do so. Similar problems arise in sensor networks where a base station has to collect data or distribute tasks for sensor nodes. In particular, we address the problem of gathering information into 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 d_T in the graph, but when doing so it generates interference that does not allow nodes at distance up to d_I 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 have finished the case of toroidals grids for d_T=1 with J. Peters. In particular we have used tools developed for the weighted routing problem by other members of Mascotte R. Klasing, N. Morales, and S. Perennes. Indeed, the weighted routing problem can be viewed as a relaxed version of the problem where we don't care about the scheduling of the calls but just want to insure that there are enough calls on each arc to route the messages using this arc. Using duality, we have obtained lower bounds for our problem that match the number of rounds obtained by the protocols. A final version will be submitted soon to a journal (BePe08). We have also obtained lower bounds for the case of hexagonal grids and are currently designing the protocols matching them.
   • We have completely solved the problem for trees for the case d_T=d_I with J. Yu (a specific case widely considered in the literature under the name of primary interference node or avoiding collisions). In fact we considered the analogous problem of personalized broadcasting where a source wants to send different messages to the nodes of the network (for example web pages). The results appeared in the proceedings of the conference AdHoc Now 08 (BeYu08), a conference where J-C Bermond presented a general invited talk covering the whole problem. Also the article BCY08 concerning the case of paths has been accepted for publication and will be published soon.
   
   
   We are currently using these ideas to obtain results for the weighted routing problem for trees with general d_I where we expect to obtain polynomial algorithms. Finally we have started (internship of Dorian Mazauric Maz08 done both in Mascotte and S.F.U.) to design distributed algorithms for the call scheduling problems with probabilistic traffic (joint work with P. Nain, MAESTRO). This new topic will be emphasized in the future.
   
   
   
2. How to retrieve a large file stored in a peer-to-peer overlay network ?

   The manuscript PePe08 was written during the visit of S. Pérennes to SFU in 2007.
   
   We have persued our research on the problem of streaming a large file (for example a video stream) stored in multiple locations in an overlay network.
   In this problem we considered a peer-to-peer overlay network in which a set of receivers want to stream a file (media object) which is replicated and stored in different server nodes. The file consists of a large number of frames that are partitioned into equal-sized chunks. Each receiver needs to receive all of the chunks approximately in the order that they need to be used. A chunk can arrive at a receiver before the time that it is needed and will be buffered. Our main goal 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 is used (played back or listened to) to avoid jitter during playback.
   
   We have proved that the general problem is NP-hard when the frames cannot be split. However, we have also established that certain cases of practical importance can be solved efficiently. In particular, we have shown that the steady state case, in which a streaming process must be maintained over a long period of time, can be solved efficiently. We have proved a few reults for the realistic scenario in which the peer-to-peer network is dynamic (peers can join and leave the network) using statistical methods.

3. WDM DAG Networks

   As announced in the program last year, we have continued our research on DAG's (Directed Acyclic Graphs) without internal cycles. An internal cycle is an oriented cycle such that all of the vertices have at least one predecessor and one successor. We have found a simpler proof that if a DAG has no internal cycles, then the minimum number of colors (wavelengths) needed to color the paths associated with requests is equal to the load. In particular, we have studied more deeply the class of DAGs with a unique path between any pair of vertices (called UPP graphs). We have shown for this class of graphs that if a graph has an internal cycles, then there exists a family of dipaths with load 2 that needs as many wavelengths as we want. The proof uses a new concept of good labeling for the conflict graph and a recent probabilistic result on coloring of B. Reed. An article is in preparation with M. Cosnard who is supposed to finish it during his "free time" ...

4. Online traffic grooming

   In a WDM network, routing a request consists of assigning it a route and a wavelength in the physical network. If each request uses at most 1/C of the bandwidth of the wavelength, we say that the grooming factor is C. This means that we can groom (group) at most C requests into the same wavelength on a given edge of the network. With this constraint, the objective is either to minimize the number of wavelengths (related to the transmission cost) or to minimize the number of Add Drop Multiplexers (i.e. ADMs) used in the network (related to the cost of the nodes).
   During their visit to Vancouver in August 2008, J-C. Bermond and D. Coudert began joint work with J. Peters on online traffic grooming on the path. In this context, we have to design the network according to a given routing algorithm (or for all possible routing algorithms) to satisfy any set of requests such that at most k requests start from and finish at a given a node. Our parameters are: the length N of the path, the grooming factor C, the number W of wavelengths to which a node is connected, and the neighborhood pattern (i.e. each node u is connected to nodes u+l₁,u+l₂,...,u+l_r). We have already obtained significant results including upper and lower bounds and a manuscript is in preparation.

• 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 K_n, 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 C_n, 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 d_T in the graph, but when doing so it generates interference that does not allow nodes at distance up to d_I (d_I ≥ d_T) 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 d_T = 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 d_I in the first case, and for 1 ≤ d_I ≤ 4, in the second case. Partial results were given in the conference BCY06. However the proof of improved lower bounds and exact values for d_I=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 log_c(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 log₂(N) neighbours, so neighbourhood broadcasting takes at least log log_c(N+1) rounds. In BFPP07 we present asymptotically optimal neighbourhood broadcast protocols for binary hypercubes.

1. J-C. Bermond, R. Correa, and M-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Technical report inria-00168162, HAL, August 2007. [WWW ] [PDF ]


2. J.-C. Bermond, A. Ferreira, S. Pérennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. SIAM Journal on Discrete Mathematics, to appear, 2007. [PDF ]


3. J.-C. Bermond and M.-L. Yu. Vertex disjoint routings of cycles over tori. Networks, 49(3):217-225, 2007. [PDF ]

• M. Cosnard, 3 weeks
• M. Perennes, June-July 2007, 1 month

• J. Peters, 3 weeks
• L. Stacho, 2 weeks
• J. Yu, 3 months

• 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 K_n, 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 C_n, 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 d_T in the graph, but when doing so it generates interference that does not allow nodes at distance up to d_I (d_I ≥ d_T) 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 BCY06 and BCY07 , we consider the case d_I = 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 d_I in the first case, and for 1 ≤ d_I ≤ 4, in the second case. In BePe06 we give optimal algorithms still for d_T = 1 but for grids.
  
  We are currently (with researchers in Salerno University) looking in more details at the case d_I = d_T = 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 M₁,...,M_n (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: M_i is included in M_i+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 log_c(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 log₂(N) neighbours, so neighbourhood broadcasting takes at least log log_c(N+1) rounds. In BFPP07 we present asymptotically optimal neighbourhood broadcast protocols for binary hypercubes.

1. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Algorithmic Operations Research, 1(2), 2006.


2. J-C. Bermond, R. Correa, and M-L. Yu. Gathering algorithms on paths under interference constraints. In 6th Conference on Algorithms and Complexity, Roma,Italy, pages 115-126, May 2006. [PDF ]



3. J-C. Bermond and J. Peters. Optimal Gathering in Radio Grids with Interference.
   Note: Submitted to Discrete Mathematic, 2006.

• J-C. Bermond, septembre 2006 (2 semaines)
• M. Syska, mai - juin 2006 (1 mois)

• J. Peters, juin-juillet 2006 (1 mois)
• L. Stacho, juin-juillet 2006 (3 semaines)
• J. Yu, juin-juillet 2006 (1 mois)

Nous avons poursuivi nos travaux sur les problèmes de réseaux dorsaux et sur les réseaux radio.

Nous avons obtenu de nouveaux résultats sur le problème du groupage de trafic dans les réseaux dorsaux, en particulier dans le cas où le réseau est un chemin orienté BBC05. Nous nous sommes également intéressés au problème de la construction incrémentale de séquences de graphes KLPT05.
Enfin, l'article sur la protection par cycles pour le cas où le graphe des demandes est le graphe complet et le réseau physique un tore a été accepté pour publication dans Networks BeYu07.

Concernant les réseaux radio, nous avons poursuivi les travaux initiés dans BCY05 sur le problème de "gathering" de messages répartis dans les sommets du chemin vers un sommet déterminé sous contraintes que:

1. Un sommet recoit une communication si l'émetteur est à une distance inférieure à d et qu'il n'y a pas d'interférences
2. Une transmission interfère avec la réception d'une autre si l'émetteur de la première est à une distance inférieure à b du récepteur de la deuxième.

1. J-C. Bermond, R. Corrêa, and J. Yu. Gathering in Radio networks, the one-dimensionnal case.
   Note: Manuscript, 2005.


2. J-C. Bermond, L. Braud, and D. Coudert. Traffic Grooming on the Path. In 12th International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Le Mont Saint-Michel, France, pages 34-48, May 24-26 2005. LNCS 3499. [PDF]


3. J-C. Bermond and J. Peters. Efficient Gathering in Radio Grids with Interference.. In ALGOTEL, pages 103-106, 2005. [PDF]


4. J-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Perennes. Hardness and approximation of Gathering in static radio networks. In submitted to FAWN06, Pisa,Italy, 2006. [POSTSCRIPT]


5. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Technical report, INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR, 2005.
   Note: Submitted to Algorithmic Operations Research. [PDF] [POSTSCRIPT]


6. R. Klasing, N. Morales, and S. Perennes. On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands. Technical report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, December 2004. [PDF] [POSTSCRIPT]

• R. Klasing, novembre 2005 (2 semaines)
• S. Perennes, novembre 2005 (1 mois)

• J. Peters, janvier à mai 2005 (5 mois)
• P. Hell (2 semaines)
• J. Yu, février-avril 2005 (3 mois)

Comme annoncé dans le programme de travail nous avons avancé sur les problèmes de réseaux dorsaux et sur les réseaux radio.

Sur les réseaux dorsaux nous avons obtenu des résultats sur le groupage de trafic (technique qui consiste à agréger des flux de trafic élémentaire pour les transporter ensemble sur un même canal optique par exemple). Plusieurs résultats ont été obtenus sur la minimisation du nombre d'ADMs comme par exemple l'article BCLY04.

Sur les problèmes de protection, les résultats sur la protection par cycles obtenus dans BCY03 pour le cas où le graphe des demandes est le graphe complet et le réseau physique un cycle ont été étendus dans BeYu07 au cas où le réseau physique est un tore.

Dans BFPP04 est considéré un problème de communication ou un message doit être transmis aux voisins en utilisant le minimum d'étapes dans un hypercube.

Concernant les réseaux radio dans BCY05 est étudié le "gathering" de messages répartis dans les sommets du chemin vers un sommet determiné sachant qu'un call ne peut avoir lieu que vers un voisin et que deux calls dont la distance entre l'émetteur et le recepteur est inférieure à une certaine valeur d'interférence ne peuvent avoir lieu simultanément . On cherche à minimiser le nombre d'étapes d'un tel protocole (ou a utiliser au mieux la division du spectre radio). Le cas de la grille fait l'objet d'études en cours entre Bermond Peters et Yu.

1. J-C. Bermond, C.J. Colbourn, A. Ling, and M-L.Yu. Grooming in unidirectional rings : K_4-e designs. Discrete Mathematics, Lindner's Volume, 284(1-3):57-62, 2004. [ PS ]


2. J-C. Bermond, R. Correa, and M-L. Yu. Radio transmission with interferences. manuscript, 2004.


3. J-C. Bermond, D. Coudert, and M-L.Yu. On DRC-covering of K_n by Cycles. Journal of Combinatorial Designs, 11:100-112, 2003. [ PS ]


4. J-C. Bermond, A. Ferreira, S. Perennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. Technical report, SFU-CMPT-TR 2004-12, 2004. Submitted to SIAM JDM. [PDF]

• J-C. Bermond
  • Septembre 2003
  • Septembre 2004
• D. Coudert, 15/08-15/09 2004
• R. Klasing, février 2004
• M. Syska, 15/08-15/09 2004

• J. Peters
  • 17/10/2003 -- 21/11/2003
  • 11/05/2004 -- 19/07/2004
• P. Hell
• J. Yu, février-avril 2004

• Le texte de la proposition