One document matched: draft-baccelli-multi-hop-wireless-communication-04.txt
Differences from draft-baccelli-multi-hop-wireless-communication-03.txt
MANET Autoconfiguration (Autoconf) E. Baccelli
Internet-Draft INRIA
Intended status: Informational C. Perkins
Expires: November 25, 2010 Tellabs
May 24, 2010
Multi-hop Ad Hoc Wireless Communication
draft-baccelli-multi-hop-wireless-communication-04
Abstract
This document describes some important 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 November 25, 2010.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
Baccelli & Perkins Expires November 25, 2010 [Page 1]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
This document is subject to BCP 78 and the IETF Trust's Legal
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. Communication in Multi-hop Ad Hoc Wireless Networks . . . . . . 3
2.1. Asymmetry, Time-Variation, and Non-Transitivity . . . . . . 3
2.2. Radio Range and Wireless Irregularities . . . . . . . . . . 4
3. Alternative Terminology . . . . . . . . . . . . . . . . . . . . 7
4. Security Considerations . . . . . . . . . . . . . . . . . . . . 8
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
6. Informative References . . . . . . . . . . . . . . . . . . . . 8
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . . 9
Appendix B. Changes from previous version . . . . . . . . . . . . 9
Baccelli & Perkins Expires November 25, 2010 [Page 2]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
1. Introduction
The goal of this document is to describe some important aspects of
multi-hop ad hoc wireless communication. These characteristics have
been very well researched, and numerous results have been published
during many years of experience dealing with wireless communications.
Experience gathered with [RFC2501] [RFC3626] [RFC3561] [RFC3684]
[RFC4728] [RFC5449] [DoD01] shows that this type of communication
presents specific challenges that are relevant to the design of
Internet protocols that are intended for establishing connectivity in
multi-hop ad hoc wireless networks. This document briefly describes
some of these challenges.
2. Communication in Multi-hop Ad Hoc Wireless Networks
In this document, we consider a multi-hop ad hoc wireless network to
be a collection of devices that all have radio transceivers using the
same physical and medium access protocols. They may be configured to
provide store-and-forward functionality on top of these protocols, as
needed to enable communications; consequently, such nodes would
usually be classified as routers in the resulting wireless network.
In the following, we will just refer to these devices as nodes.
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 detectable by node B without requiring
storage and/or forwarding by any other node. In this circumstance,
we will say that B can receive packets directly from A.
Alternatively, we may also 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. We will now describe some
fundamental characteristics of multi-hop ad hoc wireless
communication. Because of these characteristics, some assumptions
about packet transmission that are typically made in wired networks,
are often untrue in multi-hop ad hoc wireless networks.
2.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 node A (since it is a member of
set S), there is no guarantee that A can "hear" packets from node C.
Thus, multi-hop ad hoc wireless communications may be "asymmetric".
Such asymmetry is often experienced on multi-hop ad hoc wireless
Baccelli & Perkins Expires November 25, 2010 [Page 3]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
networks, due to well-known properties of wireless communication.
Second, there is no guarantee that, as a set, S is at all stable.
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 often experienced 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 often observed on multi-hop ad hoc wireless networks.
In a nutshell: multi-hop ad hoc wireless communications often prove
to be asymmetric, non-transitive, and time-varying in character.
2.2. Radio Range and Wireless Irregularities
In Section 2.1 we presented an abstract description of some multi-hop
ad hoc wireless communication characteristics. This section points
out a practical reality, at the root of these characteristics.
Wireless communication links are often subject to significant
limitations to the distance across which they may be established. In
the extreme cases, some radio links are measured in centimeters, not
meters, although such short-range radio links are not typically
considered to support multi-hop ad hoc networks. More often, radio
Baccelli & Perkins Expires November 25, 2010 [Page 4]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
links are encountered with range limited to several tens or hundreds
of meters.
The range-limitation factor creates specific problems, observed in
multi-hop ad hoc wireless networks. In this context, it is indeed
not rare that the radio ranges of several nodes partially overlap.
This partial overlap often causes communication on multi-hop ad hoc
wireless networks to be non-transitive and/or asymmetric, as
described in Section 2.1.
For example, it often happens that a sending node transmits a packet
at higher power than is used by the node receiving the packet.
Radio Ranges for Nodes A and B
<~~~~~~~~~~~~~+~~~~~~~~~~~~~>
| <~~~~~~+~~~~~~>
+--|--+ +--|--+
|NodeA|======>|NodeB|
+-----+ +-----+
Figure 1: Asymmetric Link example. Node A can communicate with
node B, but node B cannot communicate with node A.
Another example, depicted in Figure 2, is known as the "hidden node"
problem. Even though the nodes are shown as all having equal power
for their radio transmissions, they are not at all equally accessible
to each other. 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 noisy interference, and may even be unable to
determine the source of the issue. The hidden node problem is a
practical example of the non-transitivity of multi-hop ad hoc
wireless communications mentioned in Section 2.1.
Radio Ranges for Nodes A, B, C
<~~~~~~~~~~~~~+~~~~~~~~~~~~~> <~~~~~~~~~~~~~+~~~~~~~~~~~~~>
|<~~~~~~~~~~~~~+~~~~~~~~~~~~~>|
+--|--+ +--|--+ +--|--+
|NodeB|=======>|NodeA|<=======|NodeC|
+-----+ +-----+ +-----+
Figure 2: The hidden node problem. When nodes C and B
try to communicate with node A at the same time,
their radio signals collide.
Baccelli & Perkins Expires November 25, 2010 [Page 5]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
A related situation is shown in Figure 3, illustrating 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, in node C's radio-range. Node C
cannot hear D, but node D can hear C because node D is outside node
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
<~~~~~~~~~~~~+~~~~~~~~~~~~> <~~~~~~~~~~~~+~~~~~~~~~~~>
|<~~~~~~~~~~~~+~~~~~~~~~~~~>|<~~~~~~~~~~~~+~~~~~~~~~~~~>
+--|--+ +--|--+ +--|--+ +--|--+
|NodeB|<======|NodeA| |NodeC|======>|NodeD|
+-----+ +-----+ +-----+ +-----+
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 common in multi-hop ad hoc
wireless networks. Problems with asymmetric links 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 on the situation and the link layer
technology in use, such problems, and others caused by 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 within radio range, omnidirectional wireless
transmission area is generally far from isotropic (circular). Nodes
seldom hear each other perfectly, and signal strength often varies
significantly. The variation is not a simple function of distance,
but rather a complex function of the environment including obstacles,
weather conditions, interferences as well as other factors that
change over time. The analytical formulation of the functional
variation is often 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 2.1. Just as with the problems introduced by
limited wireless range, the irregularities of wireless communications
often require resolution below the network (IP) layer, and yet
nevertheless may impact the network layer. For example, there may be
Baccelli & Perkins Expires November 25, 2010 [Page 6]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
no indication to IP when a previously established communication
channel becomes unusable. In other words, "link down" triggers are
often absent in wireless systems. This lack can potentially break
various assumptions that have been used for features designed for
wired communication links, and cause failures or poor performance.
3. 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 relatively unambiguous, with respect to the goal
of this document (see Section 1).
Nevertheless, here are a few other phrasings, describing the same
relationship between wireless nodes. 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
node 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.
- 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.
Baccelli & Perkins Expires November 25, 2010 [Page 7]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
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 2.
4. Security Considerations
This document does not have any security considerations.
5. IANA Considerations
This document does not have any IANA actions.
6. 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.
[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.
Baccelli & Perkins Expires November 25, 2010 [Page 8]
Internet-Draft Multi-hop Ad Hoc Wireless Communication May 2010
[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.
Appendix A. Acknowledgements
This document stems from discussions with the following people, in no
particular order: Thomas Clausen, Erik Nordmark, Teco Boot, Seung Yi,
Stan Ratliff, Fred Templin, Thomas Narten, Ronald Velt in't,
Christopher Dearlove, Shubhranshu Singh, Carlos Jesus Bernardos Cano,
Kenichi Mase, Paul Lambert, Ralph Droms, Ulrich Herberg, Zach Shelby,
Alexandru Petrescu, Ian Chakeres, Dave Thaler, Jari Arkko, and Mark
Townsley.
Appendix B. Changes from previous version
o Corrected the description of exposed nodes in Section 2.2
o Added more text to describe the problem that wireless media often
lack a "link-down" trigger.
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 November 25, 2010 [Page 9]
| PAFTECH AB 2003-2026 | 2026-04-24 03:14:53 |