Direction des Relations Internationales (DRI)
Programme INRIA "Equipes Associées"
(Dossier de renouvellement)
EQUIPE ASSOCIEE | RESEAUXCOM |
sélection |
2004 |
Renouvellement |
2009 |
Equipe-Projet INRIA: MASCOTTE, commun INRIA, I3S, CNRS, Univ. Nice Sophia | Organisme étranger partenaire: Network Modelling Group, Simon Fraser University |
Centre de recherche INRIA: Sophia Antipolis - Méditerranée 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 778 782 3780 |
Télécopie | +33 (0)4 92 38 79 71 | +1 778 782 3045 |
Courriel | Jean-Claude.Bermond@sophia.inria.fr | peters@cs.sfu.ca |
Titre de la thématique de collaboration (en
français et en anglais): |
||
Thématique de la collaboration :
|
We intend to continue the successful joint research that we have done in
recent 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 work 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 they have to use
multi-hop wireless relay routing. Similar problems arise in sensor networks
where a base station has to collect data or distribute tasks for sensor nodes.
This problem appears to be very difficult but we hope to obtain good
approximation algorithms for specific topologies such as trees. In the future,
we also intend to determine the best location for the base station and to
deal with the case of multiple access points and where to place them. We plan
to consider a variant of the problem in which no buffering is allowed in the
nodes and for which the complexity is still not known. The tools developed
in BePe08 and by other members of the team should be
useful to solve the relaxed version (weighted routing problem) which is
important for applications that interest Orange. In particular we hope to
find optimal solutions for the primary interference node model (in which a
round corresponds to a matching) for general graphs and general types of
requests. Surprisingly, the problem is already very difficult for the simple
case of routing information from one point to another when there is no
even cycle containing them. We also expect to obtain polynomial or
1-approximation algorithms for trees and other kinds of networks in the
general case of interference.
In the longer term, we intend to consider
the cases in which some nodes fail permanently (sensors exhaust their
batteries) or intermittently (computers shut off); the first task will be
to obtain a good model of the problem.
Distributed link scheduling in wireless networks is challenging due to
the presence of interference between transmissions and the need for
distributed solutions. In this context, our aim is to design and
evaluate the performance of distributed algorithms for call scheduling.
Applications include sensor networks and radio networks used to « bring
Internet to the villages », where only a small number of nodes --
called gateway nodes -- are able to collect data or to access the
Internet. In such networks, each node transmits the traffic it receives
to its « neighboring » nodes (i.e. nodes in its coverage area)
according to an enforced scheduling algorithm.
In addition, these algorithms should take into account the statistical
nature of the traffic and the availability of nodes. The final
objective will be to design distributed algorithms that are stable
and that induce traffic overhead that is independent of the size of the
network. Following the research done in this domain, we will suppose
that communications are synchronous. More generally, we will say that
two calls are compatible (admissible) if the receiver of one call is
not in the interference zone of the sender of the other call. The
interference zone can be approximated by a distance d in a graph
(two nodes at distance at most d interfere). During each time slot,
only pairwise compatible transmissions may occur. Note that when a node can
simultaneously emit or receive at most one packet, a set of pairwise compatible
transmissions corresponds to a matching in the graph.
During his joint internship,
D. Mazauric
started to study distributed algorithms that have limited control and knowledge
with the objective of maximizing the number of calls. The initial results are
very encouraging and we intend to pursue the work with the long term goal of
solving the gathering problem in which the calls are correlated.
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).
See BeCo06,
BCL08,
MuSa08,
BBC07, APS07,
BCC+05,
BCLY04,
and BeCe03 for more details.
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+l1,u+l2,...,u+lr). We have already obtained significant
results including upper and lower bounds and a manuscript is in
preparation. However, a lot of questions and variants of the problem are
still open.
|
Comme indiqué dans l'historique de la collaboration, nous souhaitons poursuivre la collaboration qui s'est révélé fructueuse durant les 5 dernières années. La mise en commun d'outils théoriques et des applications de chaque projet nous a aidé dans nos relations industrielles en obtenant par exemple des résultats sur le problème du gathering dans les réseaux wireless (posé par France Telecom et qui rentre dans le cadre du CRC CORSO ou sur les problèmes de stockage des données dans les réseaux pair-à-pair qui fait l'objet d'une ANR SPREADS (Safe P2p-based REliable Architecture for Data Storage) qui a démarré en octobre 2007 avec Ubistorage.
Changements majeurs survenus concernant l'Equipe
Associée (modifications des objectifs scientifiques,
des chercheurs impliqués) |
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 dT in the graph, but when doing so it generates interference that does not allow nodes at distance up to dI 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.
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.
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" ...
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+l1,u+l2,...,u+lr). We
have already obtained significant results including upper
and lower bounds and a manuscript is in preparation.
Nom |
statut |
provenance | destination |
objet |
durée (en semaines) |
Coût (EA) |
Coût (Mascotte) |
Coût (SFU) |
J-C. Bermond | DR CNRS | Sophia Antipolis | SFU | Visite | 3 | 3000€ | 1400€ | |
D. Coudert | CR INRIA | Sophia Antipolis | SFU | Visite | 5 | 2000€ | 2000€ | |
D. Mazauric | Doctorant | Sophia Antipolis | SFU | Stage | 9 | 2000€ | 2600€ | |
J. Peters | Pr | SFU | Sophia Antipolis | Visite | 4 | 2000€ | 2000€ | |
J. Yu | A-Pr | SFU | Sophia Antipolis | Visite | 12 | 4000€ | 3000€ | |
Totaux | 33 | 8000€ | 7600€ | 8400€ | ||||
Total des dépenses | 24.000€ | |||||||
Ratio financement EA/Total | 33% |
We want to finish the case of hexagonal grids with Joseph
Peters. Some optimal protocols have to be designed for
specific vertices in a zone called the partial
interference boundary. With J. Yu, we are preparing the
journal version
of BeYu08
(to be submitted to Ad Hoc & Sensor Wireless
Networks). We will use the tools and ideas developed
in BePe08
and by other members of the team to solve the relaxed
version (weighted routing problem) which is important for
applications that are of interest to Orange.
In particular we hope to find optimal solutions for the
primary interference node model (in which a round
corresponds to a matching) for general graphs, first in
the simple case of routing information from one point to
another when there is not an even cycle containing
them. Then we will solve the case of grids and bounded
degree graphs for requests that are symmetrically
distributed and to other cases where we can design
protocols meeting the lower bound. We also expect to
obtain polynomial or 1-approximation algorithms for trees
and other kinds of networks in the general case of
interference.
During 2009 we will design distributed algorithms for the
call scheduling problem with the objectives of reducing
the queues on the edges and insuring a non-exponential
increase. First, we will use simulations, and hopefully
analysis, to determine the value of the input/output ratio
under which the system is stable.
We will compare the
back-off log algorithm introduced
in Maz08
with other algorithms and try to analyze its behavior in
specific graphs such as paths and cycles.
Our first task in 2009 will be to finalize the work and the manuscript started this year on online traffic grooming in which bounds are independent of the routing algorithm. Then, we will further investigate what kind of bounds we can obtain when we specify the routing algorithms (centralized, distributed, localized, with partial knowledge of future requests,...). Finally, we will extend our work to other topologies such as unidirectional and bidirectional rings, corresponding to effective network topologies.
We will hopefully finish our work on UPP DAGs and peer-to-peer systems started during the preceding collaboration.
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE | Nombre de personnes | Coût estimé |
Chercheurs confirmés | 3 | 12.000€ |
Post-doctorants | ||
Doctorants | 1 | 4.000€ |
Stagiaires |
||
Autre (précisez) : |
||
Total | 4 | 16.000€ |
2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES | Nombre de personnes | Coût estimé |
Chercheurs confirmés | 3 | 14.000€ |
Post-doctorants |
||
Doctorants | ||
Stagiaires |
||
Autre (précisez) : |
||
Total | 3 | 14.000€ |
Commentaires | Montant |
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) | 30.000€ |
B. Cofinancements utilisés (financements autres que "Equipe Associée") | 20.000€ |
Financement "Équipe Associée" demandé (A.-B.) (maximum 10 K€) | 10.000€ |