Direction des Relations Internationales (DRI)
EQUIPE ASSOCIEE |
COMMUNITY |
sélection |
2009 |
Equipe-Projet INRIA : Planète |
Organisme étranger partenaire : University of California, Santa Cruz |
Centre de recherche INRIA : Sophia Antipolis Méditerranée |
Pays : États-Unis |
|
Coordinateur français |
Coordinateur étranger |
Nom, prénom |
Thierry Turletti |
Katia Obraczka |
Grade/statut |
CR1, responsable permanent EPI Planète |
Professor |
Organisme d'appartenance |
Planète Project-Team |
|
Adresse postale |
2004, route des Lucioles, BP 93 |
|
URL |
http://planete.inria.fr/turletti |
http://www.cs.ucsc.edu/~katia/ |
Téléphone |
+33492387879 |
+18314594308 |
Télécopie |
+33492387978 |
+18314594829 |
Courriel |
turletti@sophia.inria.fr |
katia@cse.ucsc.edu |
La proposition en
bref
Titre de la thématique de collaboration : COMMunication in heterogeneoUs
Networks prone to epIsodic
connectiviTY (Communication dans les réseaux
hétérogènes à connectivité épisodique) |
Descriptif :
The Internet of the
Future is likely to exhibit high degrees of heterogeneity, not only at the
end-system level (i.e., end-user devices) but also at the network level. In
other words, future internets will probably interconnect networks of
different types ranging from traditional wired networks, as well as different
types of wireless networks. The latter include both infrastructure-based as
well as multi-hop ad hoc networks (or MANETs for short). Unlike their
infrastructure-based counterparts, MANETs are characterized mainly by the
fact that they do not rely on any fixed network infrastructure (e.g.,
routers, access points, base stations, etc.) and therefore can be deployed
“on the fly” even when the fixed network infrastructure (wired or
wireless) is non-existent or temporarily/permanently unavailable. MANETs are
thus very attractive for impromptu deployments in both civilian and military
scenarios. More recently, a new class of wireless networks has emerged
motivated by the widespread availability of wireless communication capability
and variety of wireless devices. These so called “delay-tolerant”
or “disruption-tolerant” networks, or DTNs, are characterized by
the fact that there may not be an end-to-end path between every pair of nodes
at all times. These partitions or connectivity
disruptions may be caused by a number of factors including node mobility,
limited power and communication range, volatility of the wireless channel
(due to interference, noise, terrain, obstacles, etc.). In fact, depending on
the characteristics of the environment and driving applications, the network
may be disconnected more often than it is connected. As a result, message
delivery in these intermittently-connected networks cannot be addressed by
traditional routing approaches and thus has attracted much attention from the
network research community over the past few years. This INRIA - UC
Santa Cruz Team will investigate a number of research challenges raised by
message delivery in environments consisting of heterogeneous networks that
may be subject to episodic connectivity. The proposed work will consist of
the following research thrusts: ●
Investigate error- and congestion control techniques in episodically
connected networks. ●
Explore different mechanisms for quality-of-service (QoS) support in such
environments. |
1. Objectifs scientifiques de la
proposition
Communication networks are traditionally assumed to be connected.
However, emerging wireless applications such as vehicular networks,
pocket-switched networks, etc. coupled with volatile links, node mobility, and
power outages, will require the network to operate despite frequent
disconnections. To this end, opportunistic routing techniques have been
proposed, where a node may store-and-carry a message for some time, until a new
forwarding opportunity arises [1,2,3]. Although a
number of such algorithms exist, most focus on relatively homogeneous settings
of nodes. However, in many envisioned applications, participating nodes may
include handhelds, vehicles, sensors, etc. Furthermore, the underlying networks
themselves may also differ from one another. The resulting possibly highly
heterogeneous environment raises several research issues, especially when
participating networks are subject to frequent and arbitrarily long-lived
connectivity outages. In particular, routing is arguably one of the most
challenging problems posed by networks subject to frequent and long-lived
connectivity disruptions. This means that the network may be disconnected very
often and for long periods of time. Traditional MANET routing protocols can
tolerate some degree of disconnection but exhibit rapid and drastic performance
deterioration as disconnections become more frequent and last for longer
periods.
As wireless
communication and portable computing devices become increasingly more
prevalent, applications such as emergency response, special operations, smart
environments (e.g., smart home, highway, office, etc.), impromptu meetings and
conferences, surveillance, environmental- and habitat monitoring will emerge.
However, in order to make them a reality, the more general problem of message
delivery over heterogeneous internets, and the more specific question of
routing across these internets subject to intermittent connectivity must be
solved.
The main goal of
this proposal is to investigate different aspects associated with message
delivery in episodically-connected internets. We will build on the collective
expertise of both groups and leverage our ongoing research on routing under
episodic connectivity. The main thrusts of the proposed research during the
next three years are as follows:
·
Develop a unifying solution to routing that will enable message delivery (point-to-point as
well as multi-point) across heterogeneous networks including under varying connectivity conditions
Today, there are no comprehensive solutions targeting message delivery in
heterogeneous networked environments prone to connectivity disruptions.
Existing proposals either: (1) extend MANETs to handle episodic connectivity
[4,5,6,7], (2) augment the coverage of access points in infrastructure-based
wireless networks by, for example, making use of multi-channel radios or
switching from infrastructure- to ad-hoc mode in 802.11 [8,9,10,11], (3)
provide MANETs with Internet connectivity by using special purpose gateway
nodes and a mechanism to discover them as part of route discovery [12], or (4)
handle heterogeneity only at higher layers of the protocol stack (e.g., Bundle
Architecture [13,14]). The use of specialized nodes is very helpful in
increasing reliability, and in some cases, reducing the overall delay; however,
it does not scale or generalizes well.
To fill this gap, within COMMUNITY, we are proposing a new message
delivery scheme based on a general,
yet efficient framework for data delivery in heterogeneous internets prone to
disruptions in connectivity. To cope with arbitrarily long-lived connectivity
disruptions, the proposed message delivery framework we named MeDeHa, for Message Delivery in Heterogeneous,
Disruption-Prone Networks includes the following features:
- MeDeHa uses available storage within the network to temporarily save messages
for destinations that are currently unreachable; once these destinations
re-connect, messages destined to them are delivered. Unlike existing solutions
(e.g., Bundle Architecture [13,14]), MeDeHa addresses heterogeneity at lower layers, e.g., by
storing data at the data link layer. This is consistent with the goal of
allowing any node to carry and relay data (see below) since some intermediate
nodes may not support higher-layer protocols.
- Unlike existing proposals such as message ferries [15], data mules
[16], or throwboxes [17], MeDeHa
does not require any special-purpose nodes in order to relay data to
intended destinations, or to connect to the backbone network wherever
infrastructure is available: any node can serve as
message relay.
- Temporary message storage
within the network is regulated by node
capability issues (e.g., available buffer and energy capacity at nodes) as well as
application-specific quality-of-service issues such as delivery delay bounds,
message time-to-live (i.e., how long messages are valid for), .message
priority, etc.
In its current implementation, MeDeHa performs
message delivery in an internet comprised of an infrastructure-based wireless
network where mobile nodes roam freely across regions of connectivity (provided
by access points), and become temporarily disconnected from the network.
Simulation results obtained using the OMNET++ network simulator with a variety
of mobility, traffic and connectivity conditions show that MeDeHa
is able to improve message delivery ratio significantly [18]. Future work will
consist on extending MeDeHa with MANET support. To
this end, we will migrate to the new ns-3 [19] network simulator which has
improved network heterogeneity support (in particular, it allows associating
multiple network interfaces to simulation nodes) and which includes more
realistic models, with the possibility to use real communication stacks.
·
Explore error- and congestion control techniques in
heterogeneous networks under episodic connectivity.
End-to-end
reliability and congestion control in networks with intermittent connectivity are
considerably more challenging given that an end-to-end path between source and
destination(s) may not always exist. In fact, some end-to-end paths may never
exist. For instance, consider an environmental monitoring system deployed to
track a wild animal population. The network formed by the set of mobile nodes
deployed on the animals themselves and the set of static nodes placed around
the region the animals inhabit may never be fully connected. Therefore the
feedback loop from the destination(s) back to the source used by most
end-to-end reliability approaches may never -, or, at best, take a long time to
close. Furthermore, control messages generated by traditional network control
mechanisms (e.g., positive/negative acknowledgments, retransmissions, etc.) are
quite expensive in networks with episodic connectivity in terms of node- and
network resources consumed.
As part of this
research thrust we will investigate:
- Error control
mechanisms to address the specific needs and challenges of intermittently
connected networks. Unlike the approach used by Internet protocols (e.g., TCP),
error control needs to be decoupled from congestion control mechanisms.
Furthermore, as hinted above, the Internet’s end-to-end paradigm for
error control is no longer applicable in networks with episodic connectivity.
In these networks, only hop-by-hop control is possible. However, hop-by-hop,
especially when connectivity is intermittent, makes it quite challenging to
support end-to-end delivery guarantees. Our goal here is to then explore
different delivery guarantee semantics to address the needs of a variety of
relevant applications. Then based on our findings, develop error control
mechanisms to support the different semantics.
- We will pursue a
similar approach to developing congestion control mechanisms for heterogeneous,
intermittently connected networks. More specifically, we will define congestion
indicators, i.e., metrics we will use to detect congestion building up in the
network. Then, based on these congestion detection mechanisms, we will explore
ways to control congestion, probably by applying backpressure-based mechanisms.
·
Investigate QoS support mechanisms in heterogeneous
networks under episodic connectivity.
Questions similar
to the ones presented above apply when trying to provide quality of
service guarantees when networks are constantly disconnected. For example, how
can we ensure that messages with explicit delay bounds will be delivered within
the appropriate deadline? Within this research direction, we will explore
solutions to traffic differentiation and QoS guarantees in episodically
connected networks. One of the fundamental questions to be answered is what
kind of guarantees can be provided and under what conditions? And, what
mechanisms should be used to provide such guarantees?
We will start by developing a simple traffic differentiation scheme based
on message tags which could be assigned by the application, for example. Upon
an encounter, messages buffered at a node will be passed to the encountered
node ( a relay or the final destination) based on
their priority. Since the inter-contact time is finite, depending on the
communication data rate, nodes are only able to exchange a limited number of
messages. Messages with higher priority will be transmitted first. Note that
the priority assigned to a message is not necessarily related to the message’s time-to-live. For instance, a news article
may have a short time-to-live (it becomes outdated quickly) but may not be
urgent.
2. Présentation des
partenaires
The Planète project-team conducts research in the
domain of networking, with an emphasis on designing, implementing, and
evaluating Internet protocols and applications. The main objective of the
project-team is to propose and study new architectures, services and protocols
to support efficient and secure communication through the Internet. One of our
research axis focuses on the design of an evaluation environment for the future
Internet: We are highly involved in the elaboration of ns-3, an efficient and realistic network
simulator that includes accurate models and allows integrating real
applications and communication stacks. In parallel, an important part of our
activities focuses on experimental evaluation, which complements theoretical
modelling and simulation. We contribute to the PlanetLab/OneLab
international experimental research network in the area of platforms
federation, wireless extensions and benchmarking of network protocols.
This joint research
team will consolidate our Data-Centric Networking research axis, which focuses
on three specific problems in a data-centric architecture, related to the
transport of the data:
·
Adaptive multimedia transmission protocols for
heterogeneous and episodic connectivity networks;
·
Data dissemination paradigms in
multicasting/broadcasting environments;
·
Data dissemination on a peer-to-peer architecture.
Several researchers are involved in this
Associate Team: Chadi Barakat, Walid Dabbous and Thierry
Turletti. Two PhD students are currently involved: Rao
Naveed Bin Rais
co-supervised by Thierry Turletti and Katia Obraczka
and Mohamed Karim Sbai co-supervised by
Chadi Barakat and Walid Dabbous.
Both theses
focus on Routing in Delay/Disruption Tolerant Heterogeneous Networks and on
data sharing over MANETs, respectively.
Thierry Turletti’s short bio
Thierry Turletti received the M.S. (1990) and the
Ph.D. (1995) degrees in Computer Science both from the
UCSC’s
Internet Research Group (I-NRG)
Computer networks, in particular wireless mobile
networks, is one of the ``areas of excellence'' of UCSC's
Baskin School of Engineering. Prof. Obraczka's
Internet Research Group (I-NRG) conducts research in the design, experimental
evaluation, and implementation of network protocols for internetworks
consisting of wired as well as wireless networks. I-NRG’s research
activities span a number of areas in computer networks and distributed systems.
More specifically, in the area of network protocol design, our work span
several layers of the protocol stack, including medium access, routing,
transport, and application protocols. Currently, Prof. Obraczka
supervises 4 PhD students and 2MSc students. Two of the PhD students are
working on topics related to the work proposed here, namely routing in
disruption-tolerant networks, and will benefit directly from this joint
project.
In terms of its facilities, the I-NRG laboratory
accommodates 10 student stations and is equipped with a dozen laptops and a
dozen hand-held computing devices (PDAs). The lab has
its own servers used to run computing-intensive tasks (e.g., large-scale
network simulations). The lab also has two dozen motes and a half dozen
single-board computers (Crossbow Stargates) equipped
with Web cams.
More recently, we have embarked on developing a
heterogeneous wireless networking testbed SCORPION
(
Katia Obraczka’s short bio
Katia Obraczka received the B.S. and M.S. degrees in electrical and
computer engineering from the Federal University of Rio de Janeiro, Brazil, and
the M.S. and Ph.D. degrees in computer science from the University of Southern California (USC). She is currently a Professor of Computer
Engineering at the
History of the collaboration between
the two Teams:
The collaboration
between the two research groups started
in July 2006 when Prof. Obraczka spent the 2006-2007 academic year at INRIA
Sophia-Antipolis in the Planète Project. The collaboration has already produced
three publications in a distinguished workshop, conference, and journal. Drs.
Turletti and Obraczka are currently co-supervising a PhD student (Naveed Bin Rais) at INRIA.
Communication happens regularly through e-mail and periodic teleconferences.
The funding requested here will augment the current tele-meetings
with a number of face-to-face opportunities besides giving the student the
opportunity of spending some time at UCSC.
3. Impact :
This proposal
requests support for a collaborative research effort between the
The requested
funds will allow periodic face-to-face meetings among the two groups as well as
exchange of graduate students and junior researchers.
Formalizing our current collaboration through the
proposed joint INRIA-UCSC team will also increase our chances to compete for
funding from the
[1] E. P.
Jones and P. A. Ward, “Routing strategies for delay-tolerant
networks,” Submitted to Computer
Communication Review, available at http://ccng.uwaterloo.ca/~ pasward/Publications/.
[2] T. Spyropoulos, K. Psounis, and C.
S. Raghavendra, “Efficient routing in
intermittently connected mobile networks: the single-copy case,” IEEE/ACM
Trans. Networking., vol. 16, no. 1, pp. 63–76, 2008.
[3] T. Spyropoulos, K. Psounis, and C.
S. Raghavendra, “Efficient routing in
intermittently connected mobile networks: the multiple-copy case,” IEEE/ACM
Trans. Networking, vol. 16, no. 1, pp. 77–90, 2008.
[4] N. Sarafijanovic-Djukic, M. Piorkowski,
and M. Grossglauser, “
[5] Jörg Ott, Dirk Kutscher, Christoph Dwertmann, “Integrating DTN and MANET Routing”,
Proc. of ACM SIGCOMM workshop on Challenged Networks (CHANTS), 2006.
[6] A. Vahdat and D. Becker, “Epidemic routing for partially
connected ad hoc networks”, Technical Report CS-200006,
[7] T. Spyropoulos, K. Psounis, C.S. Ragha Vendra, “Spray and
Wait: An Efficient Routing Scheme for Intermittently Connected Mobile
Networks”, ACM SIGCOMM Workshops WDTN,
[8] J.-C.
Chen, S. Li, S.-H. Chan, J.-Y. He, “WIANI:
wireless infrastructure and ad-hoc network integration”, in: Proc. IEEE
International Conference on Communications,
[9] J He
J. Chen, S.-H. G. Chan and S.-C. Liew. “Mixed-mode wlan : The integration of ad hoc mode with wireless LAN
infrastructure”, IEEE Globecom 2003.
[10]
Carlo Parata, Gabriella Convertino,
Vincenzo Scarpa,
"Flex-WiFi: a mixed infrastructure and ad-hoc IEEE
802.11 network for data traffic in a home environment", The First IEEE WoWMoM Workshop on Autonomic and Opportunistic
Communications, 2007.
[11] R.
Chandra, P. Bahl, and P. Bahl,
“MultiNet: Connecting to Multiple IEEE 802.11
Networks Using a SingleWireless Card”, in IEEE Infocom, Hong Kong, 2004.
[12] U. Korner A. Hamidian and A.
Nilsson. “Performance of internet access solutions in mobile ad hoc
networks”, Dagstuhl-Workshop
”Mobility and Wireless in Euro-NGI”, pages 189–201,
2005.
[13] K.
Scott, S. Burleigh, “RFC 5050, Bundle Protocol
Specifications”, IRTF DTN Research Group, November 2007.
[14] V.
Cerf, S. Burleigh, A. Hooke, L. Torgerson,
R. Durst, K. Scott, K. Fall, H. Weiss, “RFC 4838, Delay-Tolerant
Networking Architecture”, IRTF DTN Research Group, April 2007.
[15] W.
Zhao , M. Ammar , E. Zegura,
“A message ferrying approach for data delivery in sparse mobile ad hoc
networks”, Proc. of ACM/IEEE MOBIHOC, 2004.
[16] R.
Shah,
[17] Wenrui Zhao, Yang Chen, Mostafa Ammar, Mark Corner, B.N. Levine, and Ellen Zegura, “Capacity Enhancement using Throwboxes in DTNs”, IEEE International Conference on
Mobile Ad hoc and Sensor Systems (MASS), Vancouver, Canada, October 2006.
[18] T.
Spyropoulos, T. Turletti, K. Obraczka, "Utility-based Message Replication for
Intermittently Connected Heterogeneous Networks", in Proc. of 1st
IEEE WoWMoM Workshop on Autonomic and Opportunistic
Communications (AOC), Helsinki, Finland, June 2007.
[19] The ns-3 network simulator, see http://www.nsnam.org/ .
[21] R.N.
Bin Rais, T. Turletti, K. Obraczka, "Coping with Episodic Connectivity in Heterogeneous
Networks", in Proc.of ACM MSWiM,
[22] M.K. Sbai, C. Barakat, J. Choi,
A.A. Hamra, T. Turletti, "Adapting BitTorrent to wireless ad hoc networks", 7th
International conference on ad hoc networks and wireless (AD-HOC NOW), Sophia
Antipolis, France, September 2008.
[23] A. Krifa,
[24]
[25] M. Bromage, V. Petkov, B. Nunes, K. Obraczka, J. Koshimoto,
S. Bromage, C. Engstrom,
”SCORPION: A
Heterogeneous Wireless Networking Testbed”, poster at the ACM MobiCom 2008, September 2008.
·
Add to the support of MANET to the MeDeHa mechanism.
We will have to port MeDeHa on the new NS-3 network simulator instead of the
OMNET++ simulator in order to use multiple interfaces per mobile node. MANETs
will add significant complexity to MeDeHa; we need to add new heuristics
features and to validate performance of the overall mechanism.
1. Echanges
The
following scientific exchanges to work on the planned activities are envisaged
in 2009:
·
Thierry Turletti will visit UCSC in 2009 (about 1 week
duration); Chadi Barakat plans to visit UCSC in 2009
or in 2010.
·
Naveed Bin Rais and Karim Sbai (INRIA Phd students) will
visit UCSC in 2009 (one or two months each)
·
Katia Obraczka will
visit INRIA to work on the planned research activities for 2009 (about 2
weeks).
·
Vladi Petkov and Matt Bromage (UCSC Phd students) will visit INRIA in 2009 (one or two months
each)
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS
LE PARTENAIRE |
Nombre de personnes |
Coût estimé |
Chercheurs confirmés |
1 |
5 K€ |
Post-doctorants |
||
Doctorants |
2 |
10 K€ |
Stagiaires |
||
Autre (précisez) : |
||
Total |
15 K€ |
2. ESTIMATION DES DÉPENSES EN INVITATIONS DES
PARTENAIRES |
Nombre de personnes |
Coût estimé |
Chercheurs confirmés |
5 K€ |
|
Post-doctorants |
||
Doctorants |
2 |
10 K€ |
Stagiaires |
||
Autre (précisez) : |
||
Total |
15 K€ |
2. Cofinancement
As
previously mentioned, we will submit a proposal to NSF’s International
Program requesting 10 K€ matching funds to support the proposed joint team INRIA-UC
Santa Cruz. We expect that once the project is formally endorsed by INRIA,
funding from NSF should follow.
3. Demande budgétaire
Indiquez, dans le tableau ci-dessous, le
coût global estimé de la proposition et le budget demandé à la DRI dans le
cadre de cette Equipe Associée (maximum 20 K€). Commentaires |
Montant |
A. Coût
global de la proposition |
30 K€ |
B.
Cofinancements utilisés |
10 K€ |
Financement
"Équipe Associée" demandé (A.-B.) |
20 K€ |