Minutes of the Recent MANET Meetings

1) Introduction

The manet WG met in two sessions. The presentation and
discussion topics covered a number of important mobile routing areas
including: modeling and simulation, protocol performance results,
implementation progress, interrouter authentication for manet,
methods for query optimization in on-demand protocols,
discussions on multicast and Quality of Service (QoS) approaches for manet, 
and a new draft routing proposal. 
The group continues to make progress towards using a common set of 
ns simulation models for cross protocol comparison, and non-author 
WG participants (participants not authoring protocol drafts) are 
making use of these models as well to conduct simulations of manet protocols
in specific scenarios of interest to them.

Implementations of several manet protocol proposals now exist in 
various stages of maturity and here is an overview of some known status.
A networked, spread spectrum radio system 
is commercially available from Nova Engineering, Cincinnati, OH which
contains an implementation of the Temporally-Ordered Routing Algorithm 
(TORA) running atop the Internet MANET Encapsulation Protocol
(IMEP) (see http://www.novaengr.com/stards57kvm.html).
Enhanced Linux 2.1.95-based versions of IMEP and TORA are running 
at the University of Maryland and will be made available shortly.  
The Carnegie Mellon University (CMU) Monarch project 
has a pre-alpha" level release of the Dynamic Source Routing (DSR) protocol
for FreeBSD 2.2.7 available (see http://www.monarch.cs.cmu.edu/dsr-impl.html).
Laboratory versions of the Core Extraction Distributed Ad hoc Routing (CEDAR)
algorithm, Optimized Link State Routing (OLSR)
algorithm and the Associativity-Based Routing (ABR) 
protocol are also reported.

The meeting began with the standard agenda bashing session, which
was then followed by a presentation on a set of wireless and mobility
enhancements being made to the ns simulator 
(see http://www-mash.CS.Berkeley.EDU/ns/) as a result of the
some of the manet WG related activities and input.
This was followed by presentation from Ericsson of
simulation results comparing the DSR and the Ad hoc On-demand 
Distance Vector (AODV) routing algorithms operating
in "power conserving" modes for various scenaria. 
A presentation from CMU followed describing their recent experiences 
in designing, setting up and using a manet testbed along the 
Monongahela River in Pittsburgh, including manet nodes operating in 
mobile vehicles (i.e.,cars).

This was followed by an update
to the MANET Authentication Architecture draft---a draft
which may be evolving towards a general lightweight authentication 
specification for mobile architectures.  Two query optimization techniques were then 
presented which are applicable to a set of on-demand routing protocols.
This was followed by a presentation on a multicast extension to CEDAR,
and by a presentation on estimating the appropriate balance
between reactive and proactive traffic in MANETs.
The usefulness of flooding for delivering multicast traffic in MANETs was 
then discussed.  This was followed by a presentation of the ABR protocol.
The meeting concluded with a discussion on QoS issues in manets and 
the extent to which QoS should be considered by the WG.

In conclusion, progress was evidenced in the continuing development of 
implementations, ongoing comparative performance analysis of proposed
protocols and the recent incorporation of common simulation extensions
for manet into the base ns simulator release.  
New work was added into the group, including a new protocol draft and 
approaches, and continuing work on security and multicast for manet.  
Work remains in defining and reaching consensus on specific manet evaluation
scenarios (e.g., mobility models, traffic models) so that we may begin 
the process of scoping down the set of proposed algorithms.

The following sections give more details regarding various presentations.

2) NS-2 Wireless and Mobility Extensions

Joe Macker from the U.S.  Naval Research Laboratory presented a set
of slides provided by the UC-Berkeley/VINT ns team describing recent extentions to the
presently available ns 2.1b5 release that include wireless and mobile routing capabilities.
The capabilities include code modules contributed by CMU, Sun
Microsystems and UC-Berkeley.  Modifications include 
802.11 multiple access models, 
and an implementation of DSR and DSDV from CMU's 
initial August 1998 release, channel and radio models incorporating 
signal attenuation, collision and capture based on a 2-ray
ground reflection model.  A set of validation
test suites for these added features are also included.  
Future work on these models 
is desired in the areas of link and physical layer
models ("Bluetooth" is sorely needed), improved scalability, 
additional routing protocols, and visualization.

3) Ericsson Simulation Work

Tony Larsson from Ericsson presented an overview of work comparing
 the performance of DSR and AODV 
for usage with Bluetooth-enabled wireless nodes.  
As Bluetooth-equipped
devices will generally be battery powered, it was pointed out that 
energy conservation is a 
primary system issue.  Thus, the two routing protocols studied were examined in
their most "power efficient" modes.  For DSR, these means operation 
without the usage of promiscuous mode, as promiscuous mode operation
in a low power device such as Bluetooth was stated to consume 
roughly 50% more energy as the receiver would frequently need to be 
actively decoding a received packet---an energy consumptive activity.
For AODV, this meant usage of "link level" neighbor status detection
(so-called AODV-LL operation) operating both  with and without periodic
HELLO exchanges.  Several random scenaria and three specific "real world"
scenarios---conference, event coverage and disaster area---were simulated.
There are many details to the study, and its reading is encouraged.
A paper on this study will appear at Mobicom '99, and details are 
available now in his Master's thesis from the Lulea University of
Technology in Sweden.  

In summary, the tests performed found that DSR and AODV performed
quite well for almost all the cases tested.  Unsurprisingly, it found
that DSR should be considered for networks with a limited number of
hops where packet overhead must be minimized, whereas AODV handles 
larger networks with many hops and less byte overhead at the
expense of greater packet overhead.  However, one significant aspect of the 
study showed that even for the relatively small networks tested, 
DSR data delivery performance begins to suffer relative to AODV as 
traffic levels rise.  This is due to the impact of the source routing
overhead included in every 64 byte data packet.  This congests the channel
and affects performance relative to a non-source routed protocol such
as AODV.  This aspect did not appear in the earlier CMU 
study as traffic levels were kept relatively low.

4) CMU MANET Testbed

Dave Johnson from Carnegie Mellon University described his research group's
experiences in designing, building and using a MANET testbed.
The effort consisted of two stages: laboratory and field testing.
In the laboratory, "macfilter" software was written so that a set of 
testbench-mounted laptops could emulate a dynamic mobile network topology 
by selectively dropping received packets from neighboring laptops 
according to preconfigured timescripts.  This capability greatly simplified
the task of initially debugging the protocol implementation.
This was followed by field trials where a MANET was constructed with
five mobile nodes (rental cars) and two fixed nodes interconnected with
915 MHz CSMA-based WaveLAN.  The two fixed nodes were placed approximately
750 meters apart, and the mobiles would drive back and forth between the 
two fixed nodes in an elongated loop.  This would create a dynamic,
relatively linear topology between the two fixed nodes with a diameter of
two to three hops.  All sorts of interesting multipath phenomena was 
observed and it was concluded that wireless reality is much more
unpredictable than presented experiences with the simulation models.  
For example, while WaveLANs used have a nominal range of 250m, it would
occasionally be possible for the two fixed nodes to communicate
even though separated by 750m.  So far, most of the testbed runs have
been spent debugging the protocol, and little performance information
is available.  In the "lessons learned" category, the implementation
has clearly shown the need for using adaptive retransmission timers 
and multi-priority queues when building a real system.
A paper describing this testbed in more detail is available 
(see http://www.monarch.cs.cmu.edu/dsr-impl.html).

5) Manet Authentication Architecture

Stu Jacobs from GTE presented an updated draft of a proposed Manet
Authentication Architecture.
The draft is intended to support authentication in bandwidth-constrainted
environments where the usage of presented network security standards may be too
heavyweight.
Discussions during the presentation concluded that it might be best 
if the draft 
eventually became part of a larger, lightweight authentication
approach for mobile architectures within the IETF.
The draft is currently written from the perspective of operating within
IMEP, but its concepts are general and are being amended to permit
usage with other manet protocols.  
It specifies authentication and certificate extensions,
and specifies several 
authentication options: keyed-MD5, user-defined, 4 levels of RSA-based
public keys, 3 levels of elliptic curve as well as DSA.
Stu indicated that he will be making a Linux-based version available soon.
Only the crypto libraries need to be purchased separately.
It also supports usage of an informal PGP "web of trust" mode if
desired through the user defined option.

6) Query Optimizations for On-demand Routing Protocols

Samir Das from the University of Texas at San Antonio (UTSA) presented 
results from "Query Localization Techniques for On-demand 
Routing Protocols in Ad Hoc Networks", a paper to appear at the
upcoming Mobicom '99 conference.  The mechanisms utilize a 
"spatial locality" assumption in that they assume that a 
destination (once lost) cannot be too far from its previous position,
so searches can be localized around the destination's previous position.
The mechanisms proposed are relative and topologically-based and 
do not make use of absolute position information such as that 
obtainable from GPS.  They utilize prior routing
histories to localize the query flood to a limited region
of the network, and can be used with source and non-source
routed protocols. Simulation results demonstrate excellent
reduction of routing overheads with this mechanism
(40% to 60% reduction in query traffic). This
also contributes to a reduced level of network congestion
and better end-to-end delay performance of data packets.

7) Multicast Extension to CEDAR (MCEDAR)

Raghupathy Sivakumar from the University of Illinois at Urbana-Champaign
presented a multicast extension to CEDAR.  The goal of the design 
is to match the forwarding efficiency of trees with the robustness
of meshes while, at the same time, minimizing the number of nodes 
involved in the multicast routing computation.  Senders and receivers
join the nearest of CEDAR's core nodes (nodes forming the algorithm's
tunneled backbone).  In response, these core nodes form a tunneled mesh
of a desired robustness, and forward tunneled multicast packets 
along a tree within this mesh.  Many details were left out of the 
presentation as they are still being developed.  A draft is expected
shortly.

8) Balancing Proactive and Reactive Control Traffic

Marc Pearlman from Cornell presented some work on estimating the optimal 
balance of control traffic in combined reactive/proactive routing 
protocols such as the Zone Routing Protocol (ZRP).
His results suggest that the optimal balance is when the amount of
reactive traffic equals the amount of proactive traffic.
This is an interesting result, and one which should be kept in mind
as work continues on such hybrid routing approaches.
During the presentation, several WG members challenged the feasability
of online implementation of this approach in real systems, as it was 
apparent that the results had been obtained under rather ideal circumstances.

9) Why Route when Flooding Will Do?

Katia Obraczka from the USC Information Science Institute
presented some very preliminary work on multicast flooding.
The basic idea here is that in some cases---particularly in 
highly dynamic networks---flooding may be a more effective means
of disseminating IP multicast information than an approach that
maintains a routing structure such as a tree or mesh.
This is certainly intuitively pleasing, and it remains to be seen
what general conclusions result from this work.

10) Associativity-Based Routing

Chai Keong Toh presented work on long-lived routing based on the concept
of associativity.  The basic idea here is to favor more stable, longer
lived routes when forming routing tables.  A draft is expected to be
posted to the WG shortly which elaborates on the details.
He also showed video clips of a demonstration showing simple connectivity 
testing of the ABR protocol implemented in Unix-based IBM laptops with WaveLAN.

11) Quality of Service Issues

Derya Cansever from GTE presented a new draft entitled
"A Framework for QoS Support in Mobile Ad-hoc Networks".
The notion here is that QoS may be desirable for time sensitive data
in MANETs.  It is clear that MANETs are a bandwidth-constrained 
environment, so overprovisioning is not an attractive option.
The draft and the discussion in the WG during the presentation
centered on what might be reasonable approaches to providing some
level of QoS for MANETs.  Most WG members seemed to favor some form
of differentiated services approach, feeling that a hard-state 
reservation-based approach does not fit well with the more dynamic 
nature of MANETs.  It was noted, however, that until commercial
multiple access layers become available that support some form of 
prioritized or controlled channel access, 
discussion of QoS will remain well-intentioned but idle talk.  
The chair requested that the author of this draft bring more detailed 
rationale and technical discussion to the mailing list for further 
review and debate.  There was consensus that this area needs much more work 
and discussion to iron out the merits and potential relevant scope.

12) Conclusions

In conclusion, the manet WG continues to move forward in the areas of 
implementing and testing routing protocol draft proposals.  
Varied participants are beginning to report 
both simulation and "live" network testing results.  
Also, additional manet protocol enhancements 
areas (e.g.,  security, multicast, and quality of service) 
continue to be discussed and presented
within the group.  With the reported progress of integrated 
manet protocols and new wireless
physical and MAC layer models in the ns simulator, we expect 
more protocol investigations and test reports in the near future,
...so stay tuned.