One document matched: draft-baccelli-multi-hop-wireless-communication-05.txt
Differences from draft-baccelli-multi-hop-wireless-communication-04.txt
MANET Autoconfiguration (Autoconf) E. Baccelli
Internet-Draft INRIA
Intended status: Informational C. Perkins
Expires: April 28, 2011 Tellabs
Oct 25, 2010
Multi-hop Ad Hoc Wireless Communication
draft-baccelli-multi-hop-wireless-communication-05
Abstract
This document describes some characteristics of communication between
nodes in a multi-hop ad hoc wireless network. These are not
requirements in the sense usually understood as applying to
formulation of a requirements document. Nevertheless, protocol
engineers and system analysts involved with designing solutions for
ad hoc networks must maintain awareness of these characteristics.
Status of This Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 28, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Baccelli & Perkins Expires April 28, 2011 [Page 1]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Multi-hop Ad Hoc Wireless Networks . . . . . . . . . . . . . . 3
3. Common Packet Transmission Characteristics in Multi-hop Ad
Hoc Wireless Networks . . . . . . . . . . . . . . . . . . . . . 3
3.1. Asymmetry, Time-Variation, and Non-Transitivity . . . . . . 4
3.2. Radio Range and Wireless Irregularities . . . . . . . . . . 5
4. Alternative Terminology . . . . . . . . . . . . . . . . . . . . 7
5. Security Considerations . . . . . . . . . . . . . . . . . . . . 8
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
7. Informative References . . . . . . . . . . . . . . . . . . . . 8
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . . 9
Baccelli & Perkins Expires April 28, 2011 [Page 2]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
1. Introduction
The goal of this document is to describe some aspects of multi-hop ad
hoc wireless communication. Experience gathered with [RFC3626]
[RFC3561] [RFC3684] [RFC4728] [RFC5449] [RFC2501] [DoD01] shows that
this type of communication presents specific challenges. This
document briefly describes these challenges, which one should
maintain awareness of, when designing Internet protocols for ad hoc
networks.
2. Multi-hop Ad Hoc Wireless Networks
A multi-hop ad hoc wireless network is a collection of devices that
each have a radio transceiver, that are using the same physical and
medium access protocols, that are moreover configured to self-
organize and provide store-and-forward functionality on top of these
protocols as needed to enable communications. The devices providing
network connectivity can thus be classified as routers; other non-
routing wireless devices may be present in the ad hoc network and
would be considered as "end-hosts". The considerations in this
document apply equally to routers or end-hosts; we use the term
"node" to refer to any such network device in the ad hoc network.
An example of multi-hop ad hoc wireless network is a wireless
community network such as Funkfeuer [FUNKFEUER] or Freifunk
[FREIFUNK], that consists in routers running OLSR [RFC3626] on 802.11
in ad hoc mode with the same ESSID at link layer. Multi-hop ad hoc
wireless networks may also run on link layers other than 802.11.
Note however that simple hosts communicating through an access point
with 802.11 in infrastructure mode do not form a multi-hop ad hoc
wireless network, since the central role of the access point is
determined a priori, and since hosts do not generally provide store-
and-forward functionality.
3. Common Packet Transmission Characteristics in Multi-hop Ad Hoc
Wireless Networks
Let A and B be two nodes in a multi-hop ad hoc wireless network N.
Suppose that, when node A transmits a packet through its interface on
network N, that packet is correctly received by node B without
requiring storage and/or forwarding by any other device. We will
then say that B "hears" packets from A. Note that therefore, when B
can hear IP packets from A, the TTL of the IP packet heard by B will
be precisely the same as it was when A transmitted that packet.
Let S be the set of nodes that can hear packets transmitted by node A
through its interface on network N. The following section gathers
Baccelli & Perkins Expires April 28, 2011 [Page 3]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
common characteristics concerning packet transmission over such
networks, which were observed through experience with [RFC3626]
[RFC3561] [RFC3684] [RFC4728] [RFC5449].
3.1. Asymmetry, Time-Variation, and Non-Transitivity
First, there is no guarantee that a node C within S can,
symmetrically, send IP packets directly to node A. In other words,
even though C can "hear" packets from A (since it is a member of set
S), there is no guarantee that A can "hear" packets from C. Thus,
multi-hop ad hoc wireless communications may be "asymmetric", and
such case is not uncommon.
Second, there is no guarantee that, as a set, S is at all stable,
i.e. the membership of set S may in fact change at any rate, any
time. Thus, multi-hop ad hoc wireless communications may be "time-
variant". Such variations are not unusual in multi-hop ad hoc
wireless networks due to variability of the wireless medium, and to
node mobility.
Now, conversely, let V be the set of nodes from which A can directly
receive packets -- in other words, A can "hear" packets from any node
in set V. Suppose that node A is communicating at time t0 through its
interface on network N. As a consequence of time variation and
asymmetry, we observe that A:
1. cannot assume that S = V,
2. cannot assume that S and/or V are unchanged at time t1 later than
t0.
Furthermore, transitivity is not guaranteed over multi-hop ad hoc
wireless networks. Indeed, let's assume that, through their
respective interfaces within network N:
1. node B and node A can hear each other (i.e. node B is a member of
sets S and V), and,
2. node A and node C can also hear each other (i.e. node C is a also
a member of sets S and V).
This neither implies that node B can hear node C, nor that node C can
hear node B (through their interface on network N). Such non-
transitivity is not uncommon on multi-hop ad hoc wireless networks.
In a nutshell: multi-hop ad hoc wireless communications can be
asymmetric, non-transitive, and time-varying.
Baccelli & Perkins Expires April 28, 2011 [Page 4]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
3.2. Radio Range and Wireless Irregularities
Section 3.1 presents an abstract description of some common
characteristics concerning packet transmission over multi-hop ad hoc
wireless networks. This section describes practical examples which
illustrate the characteristics listed in Section 3.1.
Wireless communication links are subject to limitations to the
distance across which they may be established. The range-limitation
factor creates specific problems on multi-hop ad hoc wireless
networks. In this context, it is not uncommon that the radio ranges
of several nodes partially overlap. Such partial overlap causes
communication to be non-transitive and/or asymmetric, as described in
Section 3.1.
For example, as depicted in Figure 1, it may happen that a node B
hears a node A which transmits at high power, whereas B transmits at
lower power. In such cases, B can hear A, but A cannot hear B. This
is a practical example of the asymmetry in multi-hop ad hoc wireless
communications mentioned in Section 3.1.
Radio Ranges for Nodes A and B
<~~~~~~~~~~~~~+~~~~~~~~~~~~~>
| <~~~~~~+~~~~~~>
+--|--+ +--|--+
| A |======>| B |
+-----+ +-----+
Figure 1: Asymmetric Link example. Node A can communicate with
node B, but B cannot communicate with A.
Another example, depicted in Figure 2, is known as the "hidden node"
problem. Even though the nodes all have equal power for their radio
transmissions, they cannot all reach one another. In the figure,
nodes B and C cannot hear each other. On the other hand, nodes A and
B can hear each other while A and C can also hear each other. When
nodes B and C try to communicate with node A at the same time, their
radio signals collide. Node A will only be able to detect noise, and
may even be unable to determine the source of the noise. The hidden
terminal problem is a practical example of the non-transitivity in
multi-hop ad hoc wireless communications mentioned in Section 3.1.
Baccelli & Perkins Expires April 28, 2011 [Page 5]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
Radio Ranges for Nodes A, B, C
<~~~~~~~~~~~~~+~~~~~~~~~~~~~> <~~~~~~~~~~~~~+~~~~~~~~~~~~~>
|<~~~~~~~~~~~~~+~~~~~~~~~~~~~>|
+--|--+ +--|--+ +--|--+
| B |=======>| A |<=======| C |
+-----+ +-----+ +-----+
Figure 2: The hidden node problem. Nodes C and B
try to communicate with node A at the same time,
and their radio signals collide.
Another situation, shown in Figure 3, is known as the "exposed node"
problem. In the figure, node A is transmitting (to node B). As
shown, node C cannot communicate properly with node D, because of the
on-going transmission of node A, polluting C's radio-range. Node C
cannot hear D, but node D can hear C because D is outside A's radio
range. Node C is then called an "exposed node", because it is
exposed to co-channel interference from node A and thereby prevented
from transmitting data to node D -- even though the transmission
would be successful and would not interfere with the reception of
data sent from node A to node B.
Radio Ranges for Nodes A, B, C, D
<~~~~~~~~~~~~+~~~~~~~~~~~~> <~~~~~~~~~~~~+~~~~~~~~~~~>
|<~~~~~~~~~~~~+~~~~~~~~~~~~>|<~~~~~~~~~~~~+~~~~~~~~~~~~>
+--|--+ +--|--+ +--|--+ +--|--+
| B |<======| A | | C |======>| D |
+-----+ +-----+ +-----+ +-----+
Figure 3: The exposed node problem. When node A is communicating
with node B, node C is an "exposed node".
Hidden and exposed node situations are not uncommon in multi-hop ad
hoc wireless networks. Problems with asymmetric links may also arise
for reasons other than power inequality (e.g., multipath
interference). Such problems are often resolved by specific
mechanisms below the IP layer. However, depending the link layer
technology in use and the position of the nodes, such problems due to
Baccelli & Perkins Expires April 28, 2011 [Page 6]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
range-limitation and partial overlap may affect the IP layer.
Besides radio range limitations, wireless communications are affected
by irregularities in the shape of the geographical area over which
nodes may effectively communicate (see for instance [MI03]). For
example, even omnidirectional wireless transmission is typically non-
isotropic (i.e. non-circular). Signal strength often suffers
frequent and significant variations, which are not a simple function
of distance. Instead, it is a complex function of the environment
including obstacles, weather conditions, interference, and other
factors that change over time. The analytical formulation of such
variation is typically considered intractable.
These irregularities also cause communications on multi-hop ad hoc
wireless networks to be non-transitive, asymmetric, or time-varying,
as described in Section 3.1, and may impact the IP layer. There may
be no indication to IP when a previously established communication
channel becomes unusable; "link down" triggers are generally absent
in multi-hop ad hoc wireless networks.
4. Alternative Terminology
Many terms have been used in the past to describe the relationship of
nodes in a multi-hop ad hoc wireless network based on their ability
to send or receive packets to/from each other. The terms used in
this document have been selected because the authors believe (or at
least hope) they are unambiguous, with respect to the goal of this
document (see Section 1).
Nevertheless, here are a few other terms that describe the same
relationship between nodes in multi-hop ad hoc wireless networks. In
the following, let network N be, again, a multi-hop ad hoc wireless
network. Let the set S be, as before, the set of nodes that can
directly receive packets transmitted by node A through its interface
on network N. In other words, any node B belonging to S can "hear"
packets transmitted by A. Then, due to the asymmetry characteristic
of wireless links:
- We may say that node B is reachable from node A. In this
terminology, there is no guarantee that node A is reachable from
node B, even if node B is reachable from node A.
- We may say that node A has a link to node B. In this
terminology, there is no guarantee that node B has a link to node
A, even if node A has a link to node B.
Baccelli & Perkins Expires April 28, 2011 [Page 7]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
- We may say that node B is adjacent to node A. In this
terminology, there is no guarantee that node A is adjacent to node
B, even if node B is adjacent to node A.
- We may say that node B is downstream from node A. In this
terminology, there is no guarantee that node A is downstream from
node B, even if node B is downstream from node A.
- We may say that node B is a neighbor of node A. In this
terminology, there is no guarantee that node A is a neighbor of
node B, even if node B a neighbor of node A. As it happens, the
terminology for "neighborhood" is quite confusing for asymmetric
links. When B can hear signals from A, but A cannot hear B, it is
not clear whether B should be considered a neighbor of A at all,
since A would not necessarily be aware that B was a neighbor.
Perhaps it is best to avoid the "neighbor" terminology except for
symmetric links.
This list of alternative terminologies is given here for illustrative
purposes only, and is not suggested to be complete or even
representative of the breadth of terminologies that have been used in
various ways to explain the properties mentioned in Section 3.
5. Security Considerations
This document does not have any security considerations.
6. IANA Considerations
This document does not have any IANA actions.
7. Informative References
[RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and
Evaluation Considerations", RFC 2501, 1999.
[RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State
Routing Protocol", RFC 3626, October 2003.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC3684] Ogier, R., Templin, f., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding",
RFC 3684, February 2004.
Baccelli & Perkins Expires April 28, 2011 [Page 8]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
[RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
Routing Protocol (DSR) for Mobile Ad Hoc Networks for
IPv4", RFC 4728, February 2007.
[RFC4903] Thaler, D., "Multi-Link Subnet Issues", RFC 4903, 2007.
[RFC5449] Baccelli, E., Clausen, T., Jacquet, P., and D. Ngyuen,
"OSPF Multipoint Relay (MPR) Extension for Ad Hoc
Networks", RFC 5449, February 2009.
[IPev] Thaler, D., "Evolution of the IP Model",
draft-thaler-ip-model-evolution-01.txt (work in
progress), 2008.
[DoD01] Freebersyser, J. and B. Leiner, "A DoD perspective on
mobile ad hoc networks", Addison Wesley C. E. Perkins,
Ed., 2001, pp. 29--51, 2001.
[MC03] Corson, S. and J. Macker, "Mobile Ad hoc Networking:
Routing Technology for Dynamic, Wireless Networks",
IEEE Press, Mobile Ad hoc Networking, Chapter 9, 2003.
[MI03] Kotz, D., Newport, C., and C. Elliott, "The Mistaken
Axioms of Wireless-Network Research", Dartmouth College
Computer Science Technical Report TR2003-467, 2003.
[FREIFUNK] "Freifunk Wireless Community Networks,
http://www.freifunk.net".
[FUNKFEUER] "Austria Wireless Community Network,
http://www.funkfeuer.at".
Appendix A. Acknowledgements
This document stems from discussions with the following people, in
alphabetical order: Jari Arkko, Teco Boot, Carlos Jesus Bernardos
Cano, Ian Chakeres, Thomas Clausen, Christopher Dearlove, Ralph
Droms, Ulrich Herberg, Paul Lambert, Kenichi Mase, Thomas Narten,
Erik Nordmark, Alexandru Petrescu, Stan Ratliff, Zach Shelby,
Shubhranshu Singh, Fred Templin, Dave Thaler, Mark Townsley, Ronald
Velt in't, and Seung Yi.
Baccelli & Perkins Expires April 28, 2011 [Page 9]
Internet-Draft Multi-hop Ad Hoc Wireless Communication Oct 2010
Authors' Addresses
Emmanuel Baccelli
INRIA
Phone: +33-169-335-511
EMail: Emmanuel.Baccelli@inria.fr
URI: http://www.emmanuelbaccelli.org/
Charles E. Perkins
Tellabs
Phone: +1-408-435-0777 x337
EMail: charliep@wichorus.com
Baccelli & Perkins Expires April 28, 2011 [Page 10]
| PAFTECH AB 2003-2026 | 2026-04-24 01:56:00 |