Network Working Group F. Baker
Internet-Draft Cisco Systems
Expires: September 15, 2002 March 17, 2002
An outsider's view of MANET
draft-baker-manet-review-01
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
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."
The list of current Internet-Drafts can be accessed at http://
www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on September 15, 2002.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract
This note addresses routing in chaotic non-engineered radio networks.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [2].
Baker Expires September 15, 2002 [Page 1]
Internet-Draft Document March 2002
1. Overview and disclaimer
This note addresses routing in chaotic non-engineered radio networks.
The "chaos" in these networks derives from a combination of device
motion and interactions with the environment.
Wireless links are quite susceptible to time varying statistical
behavior caused by many factors, including the physics of the
propagation medium, inner city fading characteristics, shadowing
(e.g., a person walking by a device), potential power control, etc
induce effects that need addressing even in pseudo-static scenarios.
Examples of such networks vary from webs of radio-linked sensors
distributed like seed by air drop, to the behavior of satellites in
random orbits, to automotive applications in which cars and traffic
lights are communicating nodes, to military applications such as
battlefield communications among soldiers, unmanned reconnaissance
platforms, vehicle-mounted devices, fixed bases, and field
encampments.
Such networks have been the subject of significant research over the
past several years, with numerous routing proposals, and offers to
re-engineer TCP to make applications operate well in the network.
The fundamental bent of this note, however, differs from this
research in intent. Mobile ad hoc networks, or manets, are not seen
as networks in their own right any more than local area networks are
networks in their own right. Instead, manets are seen as localities
within networks, much as LANs operate as the local access to a wider
area Internet. The operation of manets in isolation is a special
case of their operation as part of a larger network.
Taken from this perspective, the important question is not so much
"please design a routing protocol that will be useful in a manet", as
it is "please design a routing protocol that will be useful in a
network that contains one or more manets".
Baker Expires September 15, 2002 [Page 2]
Internet-Draft Document March 2002
2. IETF History and Work: the MANET Working Group
The MANET working group was chartered in 1997, to discuss and develop
solutions for what were described as Mobile Ad Hoc Networks.
Although it was chartered as an engineering group, one could argue
that it was then and is now a research organization. There has been
little if any commercial activity related to this type of network;
activity has been focused in the research divisions of various
companies, notably Nokia, Inria, SRI, Intel, and others, and with
academic institutions such as UCSB, Rice, and so on.
2.1 Problem Statement
The problem statement that the MANET working group was given, which
may be found at http://www.ietf.org/html.charters/manet-charter.html,
says:
A "mobile ad hoc network" (MANET) is an autonomous system of
mobile routers (and associated hosts) connected by wireless
links--the union of which form an arbitrary graph. The routers
are free to move randomly and organize themselves arbitrarily;
thus, the network's wireless topology may change rapidly and
unpredictably. Such a network may operate in a standalone
fashion, or may be connected to the larger Internet.
The primary focus of the working group is to develop and
evolve MANET routing specification(s) and introduce them to
the Internet Standards track. The goal is to support networks
scaling up to hundreds of routers. If this proves successful,
future work may include development of other protocols to
support additional routing functionality. The working group
will also serve as a meeting place and forum for those
developing and experimenting with MANET approaches.
The working group will examine related security issues around
MANET. It will consider the intended usage environments, and
the threats that are (or are not) meaningful within that
environment.
In general, a MANET network is very similar to any other Internet
technology; one researcher, in a discussion of how to manage low
signal-to-noise ratio channels, ruefully remarked that the
researchers in the area frequently find themselves re-inventing
wheels. Where it differs from standard routing, however, is the
structure and characteristics of a low-power radio network.
Baker Expires September 15, 2002 [Page 3]
Internet-Draft Document March 2002
As an example of the kind of interesting radio environment that can
exist, consider the sad case of Alice, Bob, and Carol in figure 1.
An environmental obstacle separates Alice and Bob, so their radios
cannot "hear" each other, but Carol can "hear" them both quite well,
as long as they do not happen to "speak" at the same time. Carol can
interconnect them by repeating their messages; they might also be
able to correct the problem by taking a few steps or lifting their
radios - anything that would obviate the obstacle. Clearly, these
devices are in close physical proximity, but their views of the
network are very different, and their ability to use it differ
markedly as well. As they move, or as their environment changes
around them, this view of the network will also change - often
appearing to change randomly.
| Environmental
| Obstacle (metal building,
| hill, vegetation, etc)
|
Alice | Bob
/ \ | / \
/ \ | / \
/ \ / \
/ \ / \
/ \/ \
/ /\ \
/ / \ \
/ / \ \
/ /Carol \ \
Figure 1: Varying views in a radio network
2.1.1 Neighbor sets
Unlike wired networks, each device in a radio network has a slightly
different view of its world. From the router's perspective, a LAN is
an essentially fixed set of routing neighbors, which changes only on
administrative action, with additional end systems, which may come
and go. It is therefore rational and desirable to have the routers
elect one among them to perform coordination tasks - what is called a
"designated router" in OSPF and IS-IS. In a MANET, however, any
system might be called upon to relay traffic for others.
Signal quality between a wireless transmission source and a receiver,
usually measured as a signal-to-noise ratio, can be a difficult to
model and quantify. Although there are simple propagation models for
ideal conditions that are represented by deterministic equations
(e.g., free space ~1/r^2 and log distance path models ~1/r^n), the
Baker Expires September 15, 2002 [Page 4]
Internet-Draft Document March 2002
complex mechanism of electromagnetic wave propagation can be
attributed to reflection, diffraction, and scattering effects. Many
mobile radio systems will operate in urban areas or within buildings
where time varying signal fading and shadowing effects may naturally
occur. Thus, real world propagation effects often result in a time
varying function for received signal power from a source. These real
world physics effects make signal strength prediction and short-term
estimation of link quality more complex.
Since systems are in different locations, each system may have a
different set of neighbors that it is able to communicate effectively
with, which overlay each other haphazardly. For this reason, the
rules that allow OSPF to reduce its flooding statistics from an
exponential to linear behavior by electing a designated router to
perform the job are unusable in a radio network.
2.1.2 Random Interconnection Topology
Another issue is the aspect of mobility, which is different from what
has traditionally been termed "IP mobility". The concept in IP
Mobility is that a device has a normal home in some topological part
of a stable network, as indicated by its address, but may temporarily
move somewhere else. That "address" then becomes something more like
a name. A home agent translates it into a second address, which
represents the device's current actual topological location, and the
packet stream is forwarded there. The device may then advise its
correspondent of its current topological "care-of" address,
facilitating more direct routing. In a MANET, the address is tied to
the device, not a topological location, as there is no fixed network
infrastructure. When the addressed device moves, therefore, the
motion changes the routing infrastructure. There is no question of
the correspondent transmitting to the new care-of address, or of a
home agent forwarding traffic from "the right place" to "somewhere
else" along a dog-leg path; standard routing will get the packets
there as a direct outcome as routing tracks the motion of the device.
Mobility is not an aspect of all MANETs; some varieties of sensor
networks (such as forest fire sensors scattered by airdrop in the
region of a fire) can be expected to be stationary once deployed.
However, even in this case, topological relationships are arbitrary
and unengineered. In applications where node mobility is in view, it
can be haphazard, and in extreme cases can result in entire networks
randomly partitioning and joining together.
The fundamental behavior of a manet is that a routing node carries
with it an address or address prefix, and when it moves, it moves the
actual address. When this happens, routing must be recalculated in
accordance with the new topology.
Baker Expires September 15, 2002 [Page 5]
Internet-Draft Document March 2002
This has ramifications for such normal behaviors as autoconfiguration
of address prefixes and router IDs, which can be replicated in
separate networks and will require resolution when they join. It
also has ramifications for movement among what OSPF or IS-IS would
call "areas"; if an address is "known" to be someplace and suddenly
pops up somewhere else, it will need to change areas as well.
IP Mobility solves an issue in addressing caused by temporary
mobility; MANET routing solves a routing problem in a network where
mobility is normal. When mobility is solved using routing,
addressing-based solutions are irrelevant.
2.1.3 Radio issues
The IEEE 802.11 radio networks that typically connect research manets
have all of the radios on the same frequency, using a Carrier Sense
Multiple Access (CSMA) discipline. In other words, if the receiver
can tell that someone else is transmitting, it may attempt to not
interrupt, but there is no guarantee that it will be able to sense
collisions. In such cases, since all radios use the same frequency
and spread spectrum patterns, the transmitters effectively jam each
other.
One could imagine solving that using disciplines similar to that used
in LDDI, wherein each system has a sequence number and transmissions
are made in that order, to generate a form of Slotted ALOHA. What
many of the MANET routing protocols are doing, though, is finding
reasons to not have correlated reasons to transmit, such as
acknowledging multicast messages, and relying then on randomization
to evade the problem. Past research on such approaches suggests that
it is helpful, but introduces complexities of its own as well.
There are, of course, other varieties of radios. Military radios may
use Code Division Multiple Access (Spread Spectrum CDMA) or Time
Division Multiplexing (TDMA) disciplines.
2.1.4 Convergence Requirements
Internet routing protocols, such as RIP, OSPF, IS-IS, and BGP, have
always been developed on the assumption that networks proceed from a
converged state to a converged state through epochal transitions such
as changes to router configurations, loss or restoration of links, or
loss or restoration of routers. For this reason, instability in
networks is viewed with some alarm. OSPF and IS-IS were developed in
large part because it was increasingly observed that existing
distance-vector IGPs displayed unacceptably long convergence
intervals or were not sufficiently resilient. The increased
expressiveness of what were then called "variable length subnets",
Baker Expires September 15, 2002 [Page 6]
Internet-Draft Document March 2002
and are now called Classless Inter-Domain Routing (CIDR) was also a
significant factor. At this time, concern is raised in many quarters
because the BGP4+ backbone displays significant instability and long
convergence intervals.
MANET networks display exactly the opposite characteristic: due to
node mobility and constantly changing neighbor interconnectivity, the
network may display episodes in which it converges, but normally is
in a state of flux. The question becomes what level of convergence
is required: is it worthwhile to expend a great deal of effort to
attempt to maintain a higher level of convergence, or is it better to
accept partial convergence? The answer to that is not obvious, and
most likely varies from network to network and application to
application.
2.1.5 Unidirectional Routing
Manet research has blown hot and cold on the matter of directional
routing.
Common routing protocols depend on bidirectional connectivity.
Distance Vector protocols, for example, advertise what might be
considered to be statements that "you can reach [this prefix] with
[these attributes] via me, on the interface that you receive this
message on". OSPF and IS-IS, while not making statements of that
form, explicitly refuse to use links that lack bidirectional
connectivity. They refuse to neighbor, and the SPF implementation
checks that the far end of a link is reporting bidirectional linkage
before accepting the extension of a route.
In a manet network, as previously discussed, a given relationship can
be unidirectional. System A may be able to "hear" system B, but B
not "hear" A, and it may make operational sense to allow A->B to be
used as a message forwarding link. Few if any published protocols do
this today, but it is raised as a desirable capability in some
discussions.
The operational and protocol issues are immense. For a solution to
support unidirectional links, either the sender on such a link must
be sending messages for which it cannot determine whether any given
target receives them, or it must have another path (perhaps also
unidirectional) via which it receives routing information that tells
it of its hearing neighbor. This fact limits the classes of
protocols that can be used to deploy such a network, and applications
that will find such a network useful. Operationally, the fact that a
link is bidirectional is often the only way a system can know it is
working at all.
Baker Expires September 15, 2002 [Page 7]
Internet-Draft Document March 2002
2.1.6 Solution Approaches
There are a number of ways to solve these issues, as the number of
proposals made to the MANET working group attests. They are commonly
broken down into two broad classes: reactive protocols, which
determine what route to use when the route is needed, and proactive
protocols, that predetermine routes on the assumption that they may
be needed.
Reactive protocols follow approaches such as source routing or some
form of routing on demand. These are designed with the premises:
o Network locality is strong: most active routes are topologically
local, within one or two hops.
o The application can work around occasional routing glitches if
recovery is expedited
o While routing may change continuously in the global sense,
individual routes generally survive long enough to perform common
application tasks.
o The overhead of searching for a route when it is needed (which may
take several round trip times) is acceptable.
o The ratio of multi-hop routes actively being discovered and
maintained is small compared to the number of such possible routes
within a manet area.
o Route exploration surges, which result from the movement of
"keystone" nodes, are at an acceptable level.
If one accepts these premises, then it is reasonable to assume that
one will search for paths when they are needed, and save them either
in the source system or the intervening nodes.
Proactive protocols generally follow some form of link-state
algorithm, such as SPF (Dijkstra) or of map-based explicit routing.
These are designed with the premises:
o Network locality is indeterminate; routes of any length may be
commonly used, or not at all.
o The application can work around occasional routing glitches, but
recovery must be almost immediate.
o The constant route changes that happen globally may materially
affect the correct operation of individual nodes.
Baker Expires September 15, 2002 [Page 8]
Internet-Draft Document March 2002
o The overhead of calculation and information flooding is
acceptable, but the overhead of searching is not.
It is possible to mix the two models as well; a link state database
could be maintained through the network, but inspected only when it
changes the routing behavior of a network node known to be relevant
to a route that is currently in use or a new route is needed.
2.2 Progress of the group
Since 1997, at least ten protocols have been proposed. These fall
into several categories. Dynamic Source Routing (DSR) is similar in
many respects to IEEE 802.5 Source Route Bridging. Ad hoc On-Demand
Distance Vector (AODV) is a reactive protocol that introduces routing
state in a network only when needed. Topology Multicast Reverse Path
Forwarding (TBRPF) and Optimized Link State Routing (OLSR) are SPF-
based protocols, which may be compared to OSPF or IS-IS. They differ
from these in operational detail, and in the way they flood routing
database information.
Security is an issue that none of these protocols has directly
addressed, although some general analyses have been floated in the
working group. Security flaws exist in many of them, which could be
exploited; for example, DSR is subject to man-in-the-middle attacks,
and according to one of the authors has experienced them (in the form
of a lack of routing robustness when stations move) in field-testing.
Similarly, scaling is an issue that has been dealt with only on the
surface. The stated goal of these protocols is "scaling up to
hundreds of routers"; whether or not the features that allow this
level of scaling will in turn enable scaling to thousands or tens of
thousands of routers remains to be shown. The difference between
proactive and reactive protocols is intended to address some issues
in scaling, with different trade-offs. A reactive protocol might be
appropriate in a network where most connectivity is local and non-
local routes tend to remain fairly stable for the duration of a
typical session; the router maintains no state that is not in current
use, and is willing to perform an expensive set-up when it needs non-
local routing state. A proactive protocol might be appropriate in
network in which non-local communications are normal and route
maintenance must be rapid. The trade-off is that in a proactive
protocol, topological turbulence causes nodes to constantly store,
propagate, and adjust routing information that has no current
utility.
Quality of Service (important for voice applications) is also not
addressed, except in AODV. There is a draft that describes QoS use
of the routing protocol, which would have it seek a path in which
Baker Expires September 15, 2002 [Page 9]
Internet-Draft Document March 2002
certain bandwidth and delay bounds are met, and in which the request
for a route would fail if its conditions cannot be satisfied. QoS
routing is, of course, seen as a research topic by much of the IETF
community, due to a lack of commercial demand and the difficulty of
the problem in a destination-routed connectionless network [6][10].
Distributed address autoconfiguration in manet is non-trivial due to
the need for multi-hop DAD algorithms. There have been discussions
with zeroconf participants to explore possibilities and issues.
While extending any of these protocols to IPv6 is straightforward, in
publicly available documents, only AODV has materially addressed
IPv6. There are drafts on stateless autoconfiguration of IPv6
networks in a MANET, but it is independent of the routing protocol,
and apply to non-routing hosts which neighbor with routers, rather
than to systems capable of forwarding packets. OLSR mentions how it
could be extended to address IPv6. Likewise, TBRPF states (section
9.7.2) that
Transition mechanisms described in the IETF NGTRANS working
group (e.g. ISATAP) enable IPv6 operation over IPv4 routing
infrastructures. ISATAP [19] can be used on TBRPF MANETs to
enable automatic IPv6-in-IPv4 operation regardless of route
changes due to mobility. Future versions of this draft will
specify a native IPv6 capability for TBRPF using mechanisms
similar to those specified in [21]. Packet formats which
implement such mechanisms will use 4-octet router ID's instead
of 16-octet IPv6 addresses for greater efficiency.
DHCP is not mentioned in any posted draft, although there are an
argument that some form of address assignment protocol adapted to
MANET networks is required. IP Mobility is not addressed either.
An initial requirements document has been published, as RFC 2501 [7].
DSR and AODV have been proposed to the IESG for publication as
Experimental RFCs. No other drafts have been sent to the IESG.
2.3 Probable directions
The Working Group expects to publish several protocols as
Experimental, including DSR and AODV, but expect to take one reactive
and one proactive protocol onto the IETF standards track. These will
likely be AODV and OLSR.
In 1997, the working group chairs asked the authors of OLSR to
publish their work in the IETF context (although one of the working
Baker Expires September 15, 2002 [Page 10]
Internet-Draft Document March 2002
group chairs is the author of a competing proposal), because they
considered it a well architected solution to the problem. Although
some details remain to be worked out, they still consider it among
the better proposals on the table.
AODV is likewise a quite workable solution, with an interoperability
test of as many as fifteen academic implementations scheduled in
March 2002. It alone, of the candidates, addresses IPv6 or Quality
of Service issues.
TBRPF is interesting, and should work correctly, although the
operational utility of some of its optimizations may be open to
question in a given network. SRI has aggressively marketed TBRPF and
its IPRs to the working group. The fact that a patent has been
applied for on certain aspects is, however, severely limiting
politically. If there is any way in which the IETF is absolutely
predictable, it is that when confronted with a choice between a
proposal encumbered with IPR issues and an unencumbered proposal, it
will choose the unencumbered one.
The other proposals are either not as far along, have encountered
problems, or have less traction in the working group.
Baker Expires September 15, 2002 [Page 11]
Internet-Draft Document March 2002
3. Market issues
From the perspective of the marketplace, at this time there is little
commercial demand for MANET-style protocols. This is not an issue in
the protocols themselves; it is an issue of the applications in which
they might be used. While interactive automotive mapping services
are common in Japan and some European countries, these use direct-
connect short-reach radio technologies or third generation wireless,
rather than packet networks. Sensor networks remain the realm of
research, and military uses are in research. As a result, not only
are we limited by the lack of standards, but by a distinct lack of
market interest.
In fairness, when IPv4 was first deployed, there was little
commercial demand for it, either. Until the mid-1990's, Novell
Netware and Apple AppleTalk had more commercial penetration and
offered superior application features, and IBM SNA absolutely
controlled the financial services sector. At this point, while few
dispute that IPv6 gives more addresses, and therefore is a good
solution to certain market issues, there is significant dispute that
markets demand IPv6 deployment. Dismissing MANET-style routing as
meeting with little market demand is at best shortsighted. Rather,
since it meets some market requirements, the most sensible approach
is to develop the capability experimentally and see if markets grow
to depend on it.
Baker Expires September 15, 2002 [Page 12]
Internet-Draft Document March 2002
4. Protocol Proposals
For completeness, I will now discuss various possible approaches to
MANET routing as described in some of the leading protocols. I will
first discuss the use of OSPF Version 2 [4]as a MANET protocol, which
has both issues and opportunities. I will also discuss the proposals
that I perceive to be leading in the MANET working group, for
comparison.
4.1 OSPF Version 2 and IS-IS
From the perspective of a commercial vendor, the most obvious routing
protocol to use for any application is one that is already
implemented. For this reason, companies like Cisco and many of their
customers would likely look first to such standard protocols as OSPF,
IS-IS, or possibly proprietary protocols such as EIGRP, before
assuming a special purpose protocol is required. It also serves as a
point of perspective, defining terms and surfacing issues, which the
remaining discussion may refer to. If a workable scenario can be
found for OSPF or IS-IS in a MANET, interoperation with wired
internet components, including wired networks within vehicles, wired
bases, and the internet proper, becomes within the grasp of a MANET
network, which is one of MANET's clear expectations in its charter.
IS-IS and OSPF V2 mirror each other in many respects. Each is an
SPF-based protocol, which means that link connectivity information is
advertised by each router in the network and maintained in a database
by every node. Routes are then calculated through the network by
each router separately, but in a consistent manner and using
consistent information, which results in rapid convergence on a
usable set of routes.
The interfaces in an IS-IS or OSPF network fall into four categories:
o Local Area Network: A LAN is viewed as a stable and consistent set
of neighbors with consistent addressing within an address prefix,
which can use LAN multicast or multicast technology for
communications. This permits several optimizations over
describing them as pairwise point to point connections.
o Non-Broadcast Multi-Access: OSPF defines an NBMA interface as a
special case of a LAN, which does not support a multicast or
multicast capability. It is primarily used in Frame Relay and ATM
networks.
o Point to Point: A point-to-point interface is an interface on
which there are exactly two neighbors.
Baker Expires September 15, 2002 [Page 13]
Internet-Draft Document March 2002
o Point to Multipoint: OSPF defines a Point to Multipoint is a
grouping of point-to-point relationships over a common interface.
It is primarily used in Frame Relay and ATM networks.
Of these types, it will be observed that only two support a multicast
or multicast capability - the LAN and the Point to Multipoint
Interface. The fundamental issue relates to the process of bringing
up a new routing neighbor. In an SPF-based routing network, all
routing databases must be consistent to guarantee consistent results.
As a result, it is necessary only for a router joining an operational
network to synchronize with one router in order to obtain that
database. The routers on a LAN elect one among them (called the
"designated router") to perform synchronization tasks; as a result,
rather than experiencing database flooding traffic on the order of
the square of the number of routers on the LAN, that traffic is
linear with the number of routers on the LAN. Points to point links,
of course, require no such optimization.
In the design of OSPF, Frame Relay was originally viewed as being
much like a LAN, with internal connectivity that need not be visible
to the routing protocol. For this reason, Frame Relay was modeled as
an NBMA network, using a designated router like a LAN to make traffic
distributions linear. A problem was discovered in Frame Relay
networks, however, which used switching equipment that did not
support dynamic rerouting around failed internal trunks. In this
case, a failure of the trunk connecting the designated router and its
backup (shown in figure 2) would cause a designated router election,
in which various systems elected different designated routers.
OSPF's solution to this is to wait for a uniform election result
before continuing, resulting in a complete failure of routing.
Other
Router
|
Switch
/ \
/ \
Switch -- Switch
| |
| |
Designated Backup
Router Designated
Router
Figure 2: Routed IP network surrounding a Frame Relay network
The solution was to view a Frame Relay network as a bundle of point-
Baker Expires September 15, 2002 [Page 14]
Internet-Draft Document March 2002
to-point connections, which was called a point to multipoint network
interface. While this is subject to traffic volumes on the order of
the square of the number of connected routers, the loss of an
internal trunk does not result in the loss of external connectivity
unless no connectivity exists.
In MANET environments, OSPF V2 or IS-IS are likely to encounter a
number of challenges. The radio network is a multicast network, so
it is tempting to think of it as a LAN, perhaps an 802.11 variant.
However, in this environment several issues immediately result:
o When routers with different parameters on an interface, including
area number or address prefix, find themselves in communication,
they each assume that the other is misconfigured. As a result,
they refuse to accept each other as routing neighbors.
o Because each router's view is slightly different, even among
routers that choose to become neighbors, the designated router
election has inconsistent and inconclusive results. While some
sets of routers may converge on consistent designated router
choices, the network does not, and routing is not even unstable -
it is non-existent.
o If the router did calculate routes, other routers would understand
from its advertisement that it was able to deliver traffic
directly to any router using the same prefix, which would be
untrue.
o Since flooding occurs away from the interface that information is
received on, the only routers that will receive a given bit of
routing information will be those within radio range of the
originating router.
o If N routers advertise an LSA among themselves, in the average
case each will send with a link state update or a link state
acknowledge to the DR and from the DR to the others, for O(3N)
messages.
o If a multicast link state update is sent, OSPF has each recipient
respond with a unicast acknowledgement right away. In a CSMA
network, this is a recipe for disaster; the various senders have a
high probability of colliding. If acknowledgements or
retransmissions are delayed for a random interval long enough to
materially reduce the probability of collision, network
convergence is delayed by the same amount.
o Since OSPF uses only provably bidirectional links, unidirectional
links will be excluded from use.
Baker Expires September 15, 2002 [Page 15]
Internet-Draft Document March 2002
The most straightforward repair within the existing specification is
to consider the MANET to be a point-to-multipoint link, and allocate
the interface addresses from a single large prefix per area. In this
environment, routing through the MANET is straightforward, and the
other issues are resolved. However, these issues remain:
o A router that is not configured for a certain OSPF area will not
neighbor with routers in that area.
o In a multi-area, should a router change its area but retain the
same prefix on the radio link, the prefix will appear to be in
both areas, and devices in those or other areas will have
incorrect routing to some subset of the addresses in that prefix.
o Link state updates can be multicast, but the acknowledgements are
unicast. Thus, total transmissions are on the order of the square
of the number of neighboring routers.
o Since OSPF uses only provably bidirectional links, unidirectional
links will be excluded from use.
4.2 Ad hoc On-Demand Distance Vector (AODV) Routing
AODV is an example of a reactive protocol developed in the MANET
context. The authors are Charles Perkins (Nokia Research Center),
Elizabeth Belding-Royer (University of California, Santa Barbara) and
Samir Das (University of Cincinnati).
It has, in draft 10, three messages: a Route Request, and Route
Reply, and a Route Error. The Route Reply is essentially a route
announcement or update, in the parlance of more traditional distance
vector protocols; it says, "You can get to this IP Prefix via me". A
Route Request, as its name suggests, searches for a route to an
address. When a system needs a route from here to there, it emits a
local multicast that floods to all systems within some number of hops
away; those systems also learn from the Route Request a least hop
count path to the originator of the request. If a copy of the Route
Request gets to the target or to any system which has a route to the
target, that system issues a Route Reply, which is forwarded along
the best path to the source, and installs a route to the destination.
This route has a timer on it; it will survive until a movement of one
of the devices en route changes it, or until the timer expires.
A route reply is used in another way as well. It can optionally be
periodically flooded to all neighbors within a certain distance; the
specification refers to such behavior as a "hello", and suggests
limiting the flood to directly accessible routers. In this way, all
Baker Expires September 15, 2002 [Page 16]
Internet-Draft Document March 2002
neighboring systems normally have routes, and need not search among
immediate neighbors.
The routers also keep state on any route that is in use; if a packet
is sent from "here" to "there", each system en route tags the route
with the fact that the previous hop router to "here" recently used
the route. In the event that a route fails (the route is in use and
times out, the next hop is lost, or the next hop issues a Route Error
to it), it issues a Route Error to its neighbors that are using the
route. This gets back to the source of the traffic. The source
recalls how many hops away the destination was and issues a slightly
wider diameter search, to set up a new route to the destination.
The protocol was originally specified to support IPv4 in a best
effort model. It has been extended, in separate drafts, to carry
IPv6 information, and to eschew routes that fail specified criteria.
The latter is referred to as "QoS Routing", on the premise that a
route which has no more than a certain percentage utilization of the
link and no more than a specified worst case delay will deliver a
specified quality of service.
One issue in robustness has been reported; it is possible to receive
a Route Reply hello through a link that has a poor signal to noise
ratio, and be unable to actually use the route for communication.
Unfortunately, drivers may or may not report the signal to noise
ratio, the signal to noise ratio does not necessarily translate into
a statement that a certain percentage of traffic will survive a link,
and mechanisms in 802.11b that should mitigate this are unimplemented
and perhaps unimplementable in most drivers. Experimentation is
ongoing with filters to detect and deal with this issue.
4.3 Optimized Link State Routing (OLSR) Protocol
OLSR is an example of a proactive protocol using Dijkstra's algorithm
to calculate routes. Thomas Clausen, Philippe Jacquet, Anis Laouiti,
Pascale Minet, Paul Muhlethaler, Amir Qayyum, and Laurent Viennot,
all of INRIA Rocquencourt in France, originally developed it.
Comparisons are made to OSPF, of the form "it is a simplified version
of OSPF". It is fairer to say that it uses similar fundamental
algorithms; it distributes connectivity information using a flooding
algorithm, and maintains a route table calculated using the SPF
algorithm. Unlike OSPF, the flooding algorithm is unreliable.
Fundamentally, the protocol consists of two message exchanges: hello
messages and link state flooding (which includes both connectivity
information and withdrawal of the same). Each system in the network
emits a periodic hello, which lists the systems whose hellos it is
hearing. If those systems can also hear it, the message identifies
Baker Expires September 15, 2002 [Page 17]
Internet-Draft Document March 2002
bidirectional channels (channels which carry control traffic in both
directions). As they listen to each other, they can determine that
they may be in possession of information from some of their neighbors
that other neighbors do not have; they are therefore also able to
forward these link connectivity messages (or the withdrawal of those
messages) to their peers. They can then run an SPF calculation to
calculate the correct routes.
This breaks down in two places. One is that, since every system has
a slightly different set of neighbors, every system can often justify
repeating its message to someone. However, this logic results in far
more relay transmission of the link state database than is actually
necessary. A small subset of those relay systems is capable of
delivering the same effectiveness in flooding. The difficult
question is "what subset should be used?"
OLSR provides a way of resolving this, by asking each system to
identify the neighboring system that seems most capable of giving it
information about the part of the network it is not hearing from
somewhere else, and designate that system as a MultiPoint Relay
(MPR). The systems so designated form a lattice across the larger
network, relaying routing information and multihop route messages
among themselves, and relegating the other systems to a status more
similar to that of hosts in the general Internet. This provides no
area hierarchy, in the OSPF sense, but does provide a way to minimize
the remulticast of routing information, and settles the network on a
backbone of sorts. This backbone shifts, as the network itself
shifts.
The other problem inherent in OLSR is the same robustness issue found
in AODV. It is possible to receive a Hello through a link that has a
poor signal to noise ratio, and be unable to actually use the route
for communication. As with AODV, experimentation is ongoing with
filters to detect and deal with this issue.
The robustness issue has another side effect, however, this more
serious. Since flooding is unreliable and links are error-prone,
there is a nontrivial chance that the information fails to be
delivered everywhere. In such cases, routing may recover; the best
route may not be calculated, but the network may succeed in
calculating one that works. If routing does not, one can only hope
that the route is not used until it is corrected.
Ongoing research is looking at the MPR determination heuristic and
the use of filters to identify unacceptably lossy links.
Baker Expires September 15, 2002 [Page 18]
Internet-Draft Document March 2002
4.4 Extensions to OSPF Version 3
OSPF Version 3 [12]is an extension of OSPF to IPv6, and uses IPv6 to
accomplish its goals. It is quite similar to OSPF V2 in most
respects, but an important consideration is that it uses the IPv6
link-local address for all inter-router links, and injects prefixes
into an area in an LSA separate from the LSA used to construct the
area's routing lattice. This reduces or eliminates complexities
related to un-numbered links, choice of prefix, and so on, and adds
some capabilities in prefix advertisement. Two properly configured
routers can neighbor even if they have no prefixes in common, as a
result. In a MANET, this is an important result.
MANET routing should be manageable in OSPF V3 if two extensions are
adopted: area mobility and a "MANET" interface type with appropriate
procedure and metric accommodation to the MANET network. If these
two modifications are accepted, then the only remaining issue is that
OSPF only uses bidirectional links, which is not necessarily bad.
4.4.1 Area Mobility
One issue in MANET routing using OSPF is what happens when a router
finds itself faced with someone of a different area. For example, if
a vehicle associated with one area goes around a hill to a region
occupied by another, it still needs to communicate with its home
base, but the only available connectivity may be through the new OSPF
area. It is possible to configure the use of every possible area on
the MANET interface, but this is problematic. It seems like a better
approach would be to autodetect the area and join it. For scaling
reasons, in some cases, a special "joining area" is also advisable.
Apart from administrative issues, autodetection is itself
straightforward: as the device moves into the new area, it will start
receiving hellos from new neighbors, which carry the configuration of
the interface that they use. When configured to do so, and assuming
that appropriate authentication has taken place, the router auto-
creates an OSPF interface on the MANET interface that adopts those
parameters. The hellos initiated on that OSPF interface will now
neighbor with the new devices.
Several problems instantly materialize, however.
A router which is in two or more areas, in OSPF, is considered to be
an Area Border Router. As an ABR, one of the areas it must support
is area 0.0.0.0, the backbone area, and if there is only an indirect
connection to other ABRs, a direct connection should be created using
a virtual link. For several reasons, this is problematic in a manet.
Unless the device is configured to be an ABR, it would be better if
Baker Expires September 15, 2002 [Page 19]
Internet-Draft Document March 2002
it would advertise all of its prefixes in both areas, and depend on
the multipath routing characteristics of OSPF to resolve the issue.
This may be considered similar to running multiple instances of an
OSPF process, and advertising all local prefixes in both.
A router which automatically discovers a new area needs an algorithm
to determine when it should adopt or discard it, and therefore to
create or collapse the auto-generated area configuration and
database. The simplest approach I have come up with involves
noticing whether a route exists to an ABR.
The fundamental principle is the principle of least change, coupled
with the observation that OSPF often summarizes information into the
backbone, creating a preferred, or "home", area for any given router.
If a router has the option of communicating in its "home area" or
another area, it should choose the home area, to maximize the scaling
utility of summarization. If this does not result in connectivity to
an ABR in its home area, however, it will only be able to communicate
with routers in other areas by joining one or more of them. If it
finds an ABR in one of those other areas, it can treat that area as
its temporary "home" until it finds connectivity in its real "home
area"; it should join that area and drop other non-home connectivity
in which an ABR is found.
One issue with this is that it must join each area long enough to
determine whether ABR connectivity exists, and stay in the area if
ABR connectivity is absent. To minimize the pain of such exchanges,
I propose an option or attribute on the OSPF Hello that indicates
whether the device has connectivity to an ABR. A device trying to
determine whether it need join an area can determine from this which
area to join without the full exchange having taken place.
Another issue arises when several routers meet which have no
connectivity to any ABR. In such a case, the algorithm as described
so far requires them all to join all of their various areas, which at
best is a great deal of overhead. A better approach would be to
specify a special "joining area". This should be a stub area, to
limit the advertisement of summaries into it. Routers issue hellos
in this area if and only if either
o the router has no route to an ABR in any other area
or
o the router has a route to an ABR in another area, and
o it is receiving hellos from at least one router in the "joining
area" which has no ABR connectivity to the backbone.
Baker Expires September 15, 2002 [Page 20]
Internet-Draft Document March 2002
In the latter case, the router advertises itself as an ABR into the
stub "joining area" (but not the other area), as will be discussed.
Consider the examples in figures 3a, 3b, 3c, and 3d.
********************************************************************
* Backbone *
********************************************************************
ABR ABR
****************** ******************
***** ***** ***** *****
***** Router - - - - - - - - - - ->Router *****
***** A ***** ***** A *****
***** ***** ***** *****
***** ***** ***** Router *****
***** ***** ***** B *****
****************** ******************
Figure 3a: Router changing areas through a non-connectivity zone
In Figure 3a, we see one fairly common situation: Router A leaves its
area, has no connectivity, and then finds another area. It has the
choice of joining the new area, meeting the devices in the area
through the "joining area", or having no connectivity. The downside
of using the "joining area" in this case is that it requires extra
overhead. It should join the new area. As router A hears router B's
hello multicasts (which indicate that it has connectivity to an ABR),
it creates an OSPF interface in that area based on the values
advertised in B's hello message including the area ID. In this new
area, it will download the link state database, calculate its OSPF
routing, and join the area. Even though its old area is summarizing
prefixes into the backbone, and therefore into the new area, its own
prefix being advertised into the new area will be a longer prefix
match, and will therefore take precedence, even in the old area.
Baker Expires September 15, 2002 [Page 21]
Internet-Draft Document March 2002
***********************************************************
* Backbone *
***********************************************************
ABR ABR
****************** ******************
***** ***** ***** *****
***** Router - - - - - - - - - - ->Router *****
***** A . . A *****
***** . . *****
***** . Router B. *****
***** ***** ***** *****
****************** ******************
Figure 3b: Router changing areas through an overlapping region
Figure 3b is like 3a, with the exception that the two areas overlap.
In this case, Router A has a choice as it moves from one area to
another, as does Router B. The simplest choice for each to make in
the region of overlap is to minimize their own level of change - they
remain solely in their own "home" areas, and communicate via the
backbone. However, as Router A moves, it finds that it eventually
loses connectivity to its ABR, and therefore to the backbone. To
communicate globally, it must therefore join the new area, which in
essence reduces to the case in figure 3a.
Similarly, if the router is not in its "home" area but has
connectivity to an ABR in the area it has roamed to, it has no reason
to change areas other than rejoining its home area. It should stay
in the area it has roamed to until that no longer works.
When the router comes into contact with a device with ABR
connectivity in its "home" area, the same thing happens but with a
different bias. Router A prefers its "home" area over all others due
to the global optimization that summarization affords. Therefore,
when it hears such a hello in its home area, it joins that area even
if it has ABR connectivity in another area, and then leaves the other
area. In such a case, for robustness, it does not actively leave the
other area until connectivity to an ABR has been established in its
own area.
Baker Expires September 15, 2002 [Page 22]
Internet-Draft Document March 2002
***********************************************************
* Backbone *
***********************************************************
ABR ABR
****************** ******************
***** ***** ***** *****
***** . . *****
***** . . *****
***** Router A. . Router B *****
***** \ ***** ***** / *****
*************\**** ******/***********
\ /
- -\- - - - - - -/- -
* \ / *
* Router Router * joining
* A B * Area
* *
- - - - - - - - - - -
Figure 3c: Routers meeting apart from their "homes" in the "joining
area"
In figure 3c, two routers leave their regions of connectivity, as
Router A did in figure 3a. However, rather than finding each other's
areas, they find each other as entities isolated from the backbone.
As soon as they lose ABR connectivity, they started issuing hello
messages in the "joining area", and now neighbor there. This affords
them local connectivity (with each other).
Baker Expires September 15, 2002 [Page 23]
Internet-Draft Document March 2002
***********************************************************
* Backbone *
***********************************************************
ABR
******************
***** *****
***** Router *****
***** A *****
***** *****
***** *****
***** - Router- - - - - - -
************ B *
* Router * Joining
* Router C * Area
* D *
- - - - - - - - - - -
Figure 3d: Routers in the "joining area" meet another area
In figure 3d, a device (Router B) in the "joining area" hears hellos
from a device in another area which has ABR connectivity. Its first
instinct is, of course, to join that area, either because it is its
home area, or because it is an area with ABR connectivity. However,
doing so precipitously leaves the other routers in the "joining area"
without connectivity. Therefore, the router does not actively leave
the "joining area", but participates in a controlled switchover,
leaving only when its services are no longer needed.
Once it has synchronized with the other area, it starts issuing
hellos in the new area that indicate that it is connected to an ABR.
Other routers in the "joining area" will hear these, and by the same
logic, synchronize with it in the new area. In short order, the
"joining area" will collapse into the new area, lattices, prefixes,
and all, and the last router out will turn off the lights.
4.4.2 MANET Interface Type
Section 4.1details the behavior and issues of either the point to
multipoint interface or a multicast interface. In context, it seems
that MANET calls for an interface type which
o Is multicast capable, and uses multicast for link state flooding.
o Does not elect a designated router.
o Enables a router that becomes active with a large number of
communicating routers simultaneously to synchronize its LSA
Baker Expires September 15, 2002 [Page 24]
Internet-Draft Document March 2002
database with them serially (or at least one of them first) on a
unicast basis, on the assumption that they are likely to already
be synchronized among themselves.
o Results in a set of point to point relationships with its
neighbors being advertised in its router links LSA.
o Repeats a new LSA in a multicast on the interface it was received
on, both to implicitly acknowledge its receipt and to propagate it
to neighbors who may not have received the initial multicast.
This is very similar to the point to multipoint interface type, with
the exception of the final bullet. The implication is that it need
not respond to a multicast announcement with a unicast
acknowledgement; the multicast retransmission implicitly acknowledges
the update. However, a unicast retransmission of the update needs to
result in a unicast acknowledgement. Thus, an LSA update requires
each router in the area to make a single multicast transmission (ie,
there area linear distribution effects), potentially with some level
of unicast retransmission. There is one side-effect of this behavior
that bears investigation: sending a multicast which requires its
receivers to each potentially send a message has correlated
transmissions as a necessary result. In a CSMA environment, the
implication is that they are likely to collide, resulting in a high
rate of loss.
Many of the MANET routing protocols find ways to not have correlated
reasons to transmit, by not acknowledging, or by including the
acknowledgements in uncorrelated messages. On multiplexed
interfaces, OSPF is often implemented with some form of randomized
delay or link layer serialization prior to acknowledgement, to limit
this effect. There is an issue in randomized delays, however, in a
radio environment: for the randomization to have the necessary
effect, the distribution of the messages must be uniform, and the
interval must be long enough that any two transmitters have a very
low probability of collision. As a result, the period over which the
transmissions occur must be a multiple of the message duration and
the number of relevant routers, minimally on the order of two to four
times that product. This tends to result in an arbitrary extension
of the network convergence interval.
One could also imagine solving that using link layer disciplines
similar to that used in LDDI, wherein each router generates a link
layer sequence number and transmissions are made in that order. The
routing protocol could carry in its "hello" message a "transmission
sequence number", which is essentially a random number that the
routers verify is different among neighboring routers. In LDDI, the
link protocol assigns each device a time slot by giving it a sequence
Baker Expires September 15, 2002 [Page 25]
Internet-Draft Document March 2002
number in a range 1..N. System number 1 gets the first turn; it
either leaves a minimum-sized message duration idle, or transmits a
message. System 2 listens, and when System 1's message duration or
transmission is done, leaves a minimum-sized interval or transmits a
message. The process repeats through system N, who will have waited
through N-M idle time slots and seen M messages. System N then sends
its own message, if it has one, followed by a short message as though
from system 0, triggering the start of a new round. Through this
scheme, they effectively pass a token for access to the otherwise-
CSMA link, but do so without a "token" message.
In a radio network, when acknowledging a multicast message, this
could be emulated if every router organized a sequence number among
its neighbors. This would be a random integer not duplicated among
neighboring routers, an a relatively small range such as 1..twice the
number of neighboring routers. It is transmitted in the "hello"
message, and any router receiving its own number from a neighboring
system is obligated to change its number. When a multicast link
state advertisement is received, or similar message which the router
realizes that it must acknowledge and is likely to collide with
others while doing, it schedules the message sequence*interval time
units in the future, to limit the probability of collision; with CSMA
techniques, there is an improved chance of collision avoidance.
"Interval", of course, must be defined; one might expect it to be the
MANET interface's MTU in bits divided by its link speed, perhaps with
some randomization.
A simple way to generate the sequence number would be to sort the
addresses listed in the combined hellos of a set of neighbors. If a
system has N neighbors, and constructs the union of the link
addresses or router ids that they are advertising, and sorts them
numerically as unsigned numbers, any given system's sequence number
may be its own index in that array. While every system will have a
slightly different view of the array, the approach at least has the
possibility of distributing the traffic.
There are good reasons to put this behavior in the link layer
protocol, as the designers of LDDI did. However, if the MANET
routing protocol is the only protocol that has a message-burst issue,
one could also argue for making it a configurable feature if the
routing protocol.
4.4.3 Metric issues: selecting a path with adequate link quality
OSPF leaves the design of the routing metric to the administration,
with only the proviso that it will use the route that minimizes the
sum of the metrics en route, and they must fit in a specified range.
Baker Expires September 15, 2002 [Page 26]
Internet-Draft Document March 2002
One example might be a hierarchical function
metric = f(policy)*2^j + g(quality)*2^k + h(throughput)
where
o The OSPF metric is in 1..2^16-1, and specifies "goodness" of the
link. The "best" links have small numbers.
o "f(Policy)" is a variable with four to eight values, and indicates
the device's willingness to act as a router. A device with a
stable power source, for example, may be more willing than a
battery-powered device, and a device with a recently charged
battery may be more willing than a device whose battery is
depleted. Preferred links have small numbers.
o "g(Quality)" is a measure of link quality to the neighbor, with a
small number of values indicating "good" to "poor" quality - on
the order of two to four numeric values plus "not reachable".
This might derive from the signal to noise ratio, the correction
rate of the convolutional decoder, the bit error rate, or similar
measures. The measure it is derived from should be filtered using
a technique such as a median value filter feeding into an
exponentially weighted moving average, with the result being
compared to thresholds to determine the value to advertise. High
quality relationships have small numbers.
o "h(Throughput)" is a measure of the capacity of the link to move
data, perhaps an 12 bit integer. Since radios vary in their
effective transmission rate, both by design and environment, this
may have to be variable. If it is, changes should be similarly
filtered. The fastest links have small numbers
The reason for such a complex metric is that mobile ad hoc networks
have a more complex environment than wired networks. As mentioned in
Section 2, signal quality can vary on the same neighbor relationship
in the absence of motion, and neighbor relationships can be very
dynamic. The metric should enable path optimization where it can,
but focus on measured link quality and communication policy where it
must.
The downside of this approach is that the utility of links can change
rapidly and dramatically, changing the routing. The changes in
routing, of course, are to work around problems in the network, and
without the changes, communication is hindered. However, oscillation
is itself problematic (as the BBN SPF experience demonstrated), and
to be minimized.
Baker Expires September 15, 2002 [Page 27]
Internet-Draft Document March 2002
One issue that remains, with this metric as proposed, is that it
describes what is being received from a neighbor, while OSPF metrics
typically describe what can be sent to an interface or a neighbor.
Ideally, this should be advertised at the link layer, so that the
network layer protocol need not change. Otherwise, the simplest way
to describe this will be to have the metric advertised by the routing
peer be used in the SPF calculation, which at best is a cumbersome
modification to that algorithm.
In any event, it seems best if the metric, or at least the "goodness"
and "speed" components, is considered a vale read from or presented
through a link layer API. The ideal API would enable reading the
value on demand, and either present the new value when significant
events happen (such as a major change in the metric) or trigger its
being read.
4.4.4 Scaling Properties
The scaling properties of a manet routing protocol are a subject of
frequent concern. It is to ameliorate these issues that OLSR
developed the concept of a Multi-Point Relay, or MPR. In essence, if
a few devices can stand in routing as interchange points and the rest
can adopt the role of a host, the scaling properties of a network are
improved.
Without further modification, OSPF cannot readily develop that role.
What it can do, however, is limit the neighbor relationships. If a
router discovers that it has more neighbors than some threshold,
perhaps the number of Router IDs than will fit in a Hello message,
one option is to send only a subset of those Router IDs. The router
might choose, for example, to neighbor only with those routers whose
metrics are in the lowest third of the range, or only with those most
"willing" to connect.
4.4.5 IPv4 routing using IPv6
As discussed in the IP Version 6 Addressing Architecture [5][29],
there are two ways to carry IPv4 addresses within IPv6 addresses.
One, written "::a.b.c.d", describes IPv4 addresses whose end system
supports both IPv4 and IPv6 and need not be translated either way.
The other, written "::FFFF:a.b.c.d", describes an address used by an
IPv4-only host.
If the latter is carried as an IPv6 address in OSPF V3, the end
system can (at least in theory) be relied on to send it as IPv4
messages; in the event that a host sends an IPv6 message to it, a
translating gateway can translate the messages. However, OSPF V3
does not natively install IPv4 routes, depending instead on an IPv4
Baker Expires September 15, 2002 [Page 28]
Internet-Draft Document March 2002
routing protocol to do this.
It seems that it would be wise to implement a configuration option
that would import IPv4 interface prefixes and advertise them in IPv6
routing, and would generate an IPv4 route table from IPv6 routes in
these cases. This would facilitate IPv4 connectivity in an IPv6
routing infrastructure.
Baker Expires September 15, 2002 [Page 29]
Internet-Draft Document March 2002
5. Application and Transport Protocols
A related set of issues has been reviewed by various researchers at
the transport layer and its counterpart in applications. Wireless
networks are notably subject to loss due to issues in physics and
timing issues among devices that cannot "hear" each other but are
attempting to communicate with other devices, which can. The
temptation is to change TCP (which is widely used in Internet
communications) or to absorb the transport into the application layer
in a special manner. One example of such an application protocol
runs on UDP and places a sequence number in each message. The entire
file is transferred in serial order, with the receiver acknowledging
received messages. Transmission of unacknowledged packets is
repeated at intervals until all packets are acknowledged. Such
procedures avoid the vagaries of TCP's congestion avoidance behavior,
but are obviously ill-suited to a larger internet.
Section 2.1 stated, however, that interoperation with the larger
internet is indeed important. Manets occur as stand-alone networks,
but they also occur as stubs off larger backbones, and as transit
systems between small edge networks. Further, commercially available
applications are designed to use TCP. In order to use those
applications in manet environments, we face a choice: we can convince
the manufacturer to rehost the application for our amusement, or we
can adapt the environment to support the application. Both avenues
have difficulties.
One particularly promising development is found in a combination of
TCP Congestion Control [8] with "New Reno" Fast Recovery [9],
Selective Acknowledgment [1][13], and Explicit Congestion
Notification [14]. If congestion is explicitly signaled and managed,
then lost data may be more aggressively retransmitted, and still
remain interoperable with more reliable parts of the Internet.
Baker Expires September 15, 2002 [Page 30]
Internet-Draft Document March 2002
6. Conclusions
The discussion yields no strong conclusions at this time. A number
of protocols have been considered in research, with the result that
we have learned quite a bit about these networks. Some of that
learning has been relearning lessons already learned in the Internet
itself, with the resultant reinvention of related solutions, or
remembering the reasons they were invented.
6.1 Selecting a protocol
It is not obvious that a single protocol is an adequate solution for
all MANET problems. As in wired networks, there is room for
creativity, and for difference of opinion. To give an idea of the
classes of applications and aspects of solutions that drive them,
consider these three cases:
6.1.1 Military Communications
A SEAL team and a battalion of Army Rangers land in some random
mountainous country in southern Asia. Rather than depend on local
infrastructure, they will use satellites and may install temporary
fixed infrastructure if the plan of battle warrants it.
In contexts like this, proactive manet protocols (TBRPF, OLSR, a
modified OSPF, etc) make the most sense. The important issue is not
the high level of dynamism. It is the fact that there is a
continuous lower-rate change, the fact that there is no external
infrastructure to depend on, and the fact that applications in the
network need the network to be stable and working when they decide
the time has come to use it.
6.1.2 Automotive Networks
Consider a service in which automobiles can "talk to the road" to
obtain maps, weather, congestion-and-accident-ahead updates, and so
on. It might also be used to check passing hotel availability, and
to talk car to car, for example to facilitate navigation in a
caravan. In Japan, this is done with wideband CDMA in late-model
automobiles.
It does not make a lot of sense to view "every road in the world" as
a single manet; more likely, sections of road, geographic regions,
administrations running the roads, or political regions will be
manets. It is also not obvious what the "backbones" would be -
freeways, perhaps, but in much of the world distinguished systems are
not obvious. Protocols like AODV have strong appeal in such
environments. They would, however, need some provision for crossing
Baker Expires September 15, 2002 [Page 31]
Internet-Draft Document March 2002
administrative boundaries in the same fashion, perhaps by having
nodes that pass an administrative boundary give it some routing
information as they pass.
Mobile IP has been proposed as a means of managing administrative
boundaries. However, it seems to not make operational sense to this
author. The issue is the rate of change. A vehicle mostly needs to
"talk" to the next street lamp and the car a half a mile away,
especially when the car takes an unexpected turn. The radio in the
car halfway in between, which I have been traveling with for the past
ten minutes, is a more stable relay system than the street lamps I'm
passing or any ISP link. There is no reason to be constantly
updating my home ISP every time I pass another street lamp, and no
reason to form a new IPv6 address, either.
6.1.3 Classic Sensor Network
There's a brushfire in your favorite place to not have a brushfire,
and we want to manage it. So we have a plane drop "golf balls" all
over it - organic styrofoam-like stuff protecting the level of
electronics one finds in a wrist watch these days, which has just
enough smarts and capability to GPS where it is located, to
periodically say "I'm [here], and I'm still here", and to forward
similar messages from other devices. These talk to a central PC,
which keeps track of which "golf balls" are still up and which have
failed. When a device fails, the central system dispatches someone
to wonder why.
This seems to be a good application for a source routed protocol like
DSR. The only routing any given system needs is its current route to
the central system. Exploration surges will be huge at times,
especially at first, but having once subsided will likely be of
limited impact. If the central system needs a route back, it has
plenty of capacity in which to store it.
6.2 Commercial Considerations
Commercially, if I had to hang my hat on two solutions, one reactive
and one proactive, at this time I would go with AODV and some
extensions to OSPF V3. The reasons for those choices are:
o AODV is well advanced and has good capabilities for its target
networks.
o AODV is publicly documented, as opposed to being partially
documented in corporate research reports or intellectual property
declarations.
Baker Expires September 15, 2002 [Page 32]
Internet-Draft Document March 2002
o AODV has preliminary work on QoS Routing and IPv6 routing in
place; for other protocols, these are futures.
o OSPF has significant market traction.
o OSPF can be extended to include MANET-type interfaces,
incorporating lessons from OLSR, TBRPF, and so on.
o If this is done, OSPF can span wired and wireless networks.
Baker Expires September 15, 2002 [Page 33]
Internet-Draft Document March 2002
7. Security Considerations
In routing, beside the fundamental faults of undebugged code, there
are three primary threats.
o A network may require privacy in order to not give away important
information.
o A network device may be improperly configured, so that the
information it exchanges is incorrect, or its presence otherwise
disrupts the network.
o A rogue system may mimic, inject, or remove routes in order to
disrupt traffic flow.
OSPF performs simple neighboring parameter verification to detect and
avoid misconfigured neighbors, and several protocols mention IPSEC
for authentication or privacy. Besides that, no proposed manet
routing protocol explicitly addresses any of these issues.
In MANET networks where link privacy is a significant consideration,
it is logical to presume physical or link layer encryption. IPSEC
encryption could be used, but a radio listener who read the IP
headers could deduce much of the routing information. This could be
of military value, for example; if I know that a large number of
communicating systems are reached via one system and a small number
by another, and can determine which is which via radio direction
finding, I may be able to locate a force concentration or detect the
splitting off of a sortie. I may also be able to locate a single
point of failure, a system that is temporarily critical to
battlefield communications, and know to target it.
The deployment of any form of link or IPSEC encryption, however,
requires some form of key distribution. This is a problem which has
not been solved at this writing.
Neighbor authentication and privacy techniques do not, however, place
a signature on an LSA, such as is suggested in OSPF with Digital
Signatures [3], or otherwise address the issues raised in Routing
Policy System Security [11]. Thus, these protocols do not secure the
network against a rogue system once its neighbors decide to trust it.
Baker Expires September 15, 2002 [Page 34]
Internet-Draft Document March 2002
8. Acknowledgements
The author acknowledges the inputs of many in this document, most
especially Joe Macker, Scott Corson, Abhay Roy, Alexander Zinin,
Elizabeth Belding-Royce, and Charlie Perkins. Joe commented in
detail and contributed text to some sections of the document.
Brainstorming with Abhay was particularly useful in working out the
details of OSPF V3 routing exchanges.
Baker Expires September 15, 2002 [Page 35]
Internet-Draft Document March 2002
References
[1] Mathis, M., Mahdavi, J., Floyd, S. and A. Romanow, "TCP
Selective Acknowledgment Options", RFC 2018, October 1996.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[3] Murphy, S., Badger, M. and B. Wellington, "OSPF with Digital
Signatures", RFC 2154, June 1997.
[4] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[5] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 2373, July 1998.
[6] Rajagopalan, B., Nair, R., Sandick, H. and E. Crawley, "A
Framework for QoS-based Routing in the Internet", RFC 2386,
August 1998.
[7] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation
Considerations", RFC 2501, January 1999.
[8] Allman, M., Paxson, V. and W. Stevens, "TCP Congestion
Control", RFC 2581, April 1999.
[9] Floyd, S. and T. Henderson, "The NewReno Modification to TCP's
Fast Recovery Algorithm", RFC 2582, April 1999.
[10] Apostolopoulos, G., Kamat, S., Williams, D., Guerin, R., Orda,
A. and T. Przygienda, "QoS Routing Mechanisms and OSPF
Extensions", RFC 2676, August 1999.
[11] Villamizar, C., Alaettinoglu, C., Meyer, D. and S. Murphy,
"Routing Policy System Security", RFC 2725, December 1999.
[12] Coltun, R., Ferguson, D. and J. Moy, "OSPF for IPv6", RFC 2740,
December 1999.
[13] Floyd, S., Mahdavi, J., Mathis, M. and M. Podolsky, "An
Extension to the Selective Acknowledgement (SACK) Option for
TCP", RFC 2883, July 2000.
[14] Ramakrishnan, K., Floyd, S. and D. Black, "The Addition of
Explicit Congestion Notification (ECN) to IP", RFC 3168,
September 2001.
Baker Expires September 15, 2002 [Page 36]
Internet-Draft Document March 2002
[15] Das, S., Perkins, C. and E. Royer, "Ad Hoc On Demand Distance
Vector (AODV) Routing", draft-ietf-manet-aodv-10 (work in
progress), January 2002.
[16] Perkins, C., "IP Flooding in Ad hoc Mobile Networks", draft-
ietf-manet-bcast-00 (work in progress), November 2001.
[17] Johnson, D., Maltz, D., Hu, Y. and J. Jetcheva, "The Dynamic
Source Routing Protocol for Mobile Ad Hoc Networks", draft-
ietf-manet-dsr-07 (work in progress), February 2002.
[18] Gerla, M., "Fisheye State Routing Protocol (FSR) for Ad Hoc
Networks", draft-ietf-manet-fsr-02 (work in progress), January
2002.
[19] Gerla, M., "Landmark Routing Protocol (LANMAR) for Large Scale
Ad Hoc Networks", draft-ietf-manet-lanmar-03 (work in
progress), January 2002.
[20] Jacquet, P. and T. Clausen, "Optimized Link State Routing
Protocol", draft-ietf-manet-olsr-05 (work in progress), October
2001.
[21] Lewis, M., Templin, F., Bellur, B. and R. Ogier, "Topology
Broadcast based on Reverse-Path Forwarding (TBRPF)", draft-
ietf-manet-tbrpf-04 (work in progress), January 2002.
[22] Johnson, D. and J. Jetcheva, "The Adaptive Demand-Driven
Multicast Routing Protocol for Mobile Ad Hoc Networks (ADMR)",
draft-jetcheva-manet-admr-00 (work in progress), August 2001.
[23] Labiod, H. and H. Moustafa, "The Source Routing-based Multicast
Protocol for Mobile Ad Hoc Networks (SRMP)", draft-labiod-
manet-srmp-00 (work in progress), November 2001.
[24] Perkins, C. and E. Belding-Royer, "Quality of Service for Ad
hoc On-Demand Distance Vector Routing", draft-perkins-manet-
aodvqos-00 (work in progress), November 2001.
[25] Perkins, C., "IP Address Autoconfiguration for Ad Hoc
Networks", draft-perkins-manet-autoconf-01 (work in progress),
November 2001.
[26] Belding-Royer, E., "Global Connectivity for IPv4 Mobile Ad hoc
Networks", draft-royer-manet-globalv4-00 (work in progress),
November 2001.
[27] Wakikawa, R., "Global Connectivity for IPv6 Mobile Ad Hoc
Baker Expires September 15, 2002 [Page 37]
Internet-Draft Document March 2002
Networks", draft-wakikawa-manet-globalv6-00 (work in progress),
November 2001.
[28] Zitterbart, M. and K. Weniger, "IPv6 Stateless Address
Autoconfiguration for Hierarchical Mobile Ad Hoc Networks",
draft-weniger-manet-addressautoconf-ipv6-00 (work in progress),
February 2002.
[29] Hinden, B. and S. Deering, "IP Version 6 Addressing
Architecture", draft-ietf-ipngwg-addr-arch-v3-07 (work in
progress), November 2001.
[30] Yi, Y., "Passive Clustering in Ad Hoc Networks (PC)", draft-yi-
manet-pc-00 (work in progress), November 2001.
Author's Address
Fred Baker
Cisco Systems
1121 Via Del Rey
Santa Barbara, CA 93117
US
Phone: +1-408-526-4257
Fax: +1-413-473-2403
Baker Expires September 15, 2002 [Page 38]
Internet-Draft Document March 2002
Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Baker Expires September 15, 2002 [Page 39]