Minutes of Mobile Ad Hoc Networks (manet) Working Group Meeting

Munich IETF, August 1997

Meeting Secretary: Eric Guttman, Sun Microsystems
Minutes Editor: M. Scott Corson, Univ. of Maryland

Meeting convened by WG co-chair M. Scott Corson.
Co-chair Joe Macker (NRL) was absent due to a prior commitment, and
Vince Park (NRL) filled in for Joe.

Agenda:

1) Presentation of a MANET issues draft (Scott Corson)
2) Presentation on the architecture of the NTDR network (Chip Elliott,BBN) 
3) Presentation of AODV and recent results (Charlie Perkins, SUN)
4) Presentation of DSR (Dave Johnson, CMU)
5) Continuing presentation of draft (Scott Corson)
6) Discussion of draft, charter bashing and WG next steps (all)

(Editorial note: At the time of the meeting, the draft had not been
posted to the I-D repository, but has been subsequently submitted and
should be available soon.)

Dave Johnson (Mobicom program chair) made an announcement regarding
Mobicom to be held in  Budapest, Sept 26-30, and mentioned that their
would be a panel discussion on MANETs moderated by Scott.

Agenda Item 1, Scott Corson

Presentation of draft entitled "Mobile Ad Hoc Networks: Routing Protocol
Performance Issues and Evaluation Considerations" by M. Scott Corson and
Joe Macker.

The draft gave a brief history of mobile packet radio, the relationship
of this technology to other networking technologies in the context of
hybrid communication networks, and a list of possible military and
commercial applications.  The draft then goes on to define a Mobile Ad
hoc NETwork (MANET) as a set of mobile nodes (combined radios/routers)
communicating with some form of wireless technology.  The salient
characteristics of MANETs are dynamic, randomly changing topologies,
bandwidth-constrained links, potentially energy-constrained nodes
(battery powered) and limited physical security (easy snooping).

There was discussion of how this definition compared with commercial ad
hoc technology--in particular, IEEE 802.11 and HIPERLAN.  It was
mentioned that in its present form, 802.11 essentially considered only
single-hop operation (no routing), and that the MANET definition was
much closer to the latest version of HIPERLAN which permits multihop
operation using a substantially modified form of link-state routing.

The draft then defined the intent of the WG as "to aid in the
development of a peer-to-peer mobile IP networking capability beyond
the fixed network (supported by traditional IP) and the mobile one-hop
fringe of the fixed network (supported by mobile IP)--which may be
standalone (autonomous operation) or connected to the larger net via
gateway(s)." 

A question was raised regarding the type of network management to be
practiced in these networks.  While not stated explicitly, the draft
document implies that network management and control is to be completely
distributed and automated.

Agenda Item 2, Chip Elliott

Chip presented a brief on the architecture of the NTDR network--a
wireless military network based on the Near-Term Digital Radio
(NTDR)--which has a mobile, multihop topology with roughly 400-1000
mobile nodes/routers.  The 1000 node network will be divided in three
portions--interconnected with gateways--and some form of hierarchical,
link-state routing will be employed. Numerous hosts may hang off each
router on a given mobile platform and the nodes may move at speeds up
to 50 mph. The available radio bandwidth is somewhere between 0.5-1.0
Mbps.  Current status: a 20 node network has been fielded and a 100 node
demonstation is planned in the Winter.

Agenda Item 3, Charlie Perkins

A presentation of the Ad hoc, On-demand Distance Vector (AODV) Routing
Protocol. AODV is a distance-vector routing technique which employs
destination-oriented and sequenced update waves to remove the
counting-to-infinity problem inherent in distributed Bellmann-Ford
approaches without requiring the use of split-horizon/poison-reverse
techniques.  As the name suggests, routes are built *on demand* in
response to source-initiated route requests.  The update waves are
carried in reply packets generated in response to the queries.  Each
update carries among other fields a tag--a pair <SEQ,HOP>--where SEQ is
a sequence number and HOP is the hop count, and nodes are instructed to
pay attention to the pair with the most recent sequence number received
from the destination.  Route requests also carry similar routing
information so that reverse path set up back to the source occurs as
the result of route requests.  Also, requests need not propagate all the
way to the destination, but may stop at some intermediate node which
has a route to the destination. The protocol's properties include quick
convergence, minimal latency for route request, loop-freedom, reduced
BW utilization and triggered updates.  The protocol also incorporates a
hello protocol.

A question was raised as to whether multicast trees could be built
directly using this technique.  The answer was a cautious *maybe*, but
it hadn't been thought about.

Some simulation results were presented, but the results are preliminary.
General observations drawn from the results indicate that AODV's range
of applicability should be when nodes stay within range long enough for
the results obtained from a route request to be used.

Agenda Item 4, Dave Johnson

Dave presented "Dynamic Source Routing" (DSR), another demand-based
routing protocol, but one which uses source routing as opposed to
hop-by-hop routing.  It consists of route discovery and route
maintenence phases. Route maintenence is straighforward, and consists
of passively monitoring the health of existing routes by listening to
the ACKs of data packets transmitted to adjacent neighbors.  The
listening is either explicit through reception of a direct ACK, or
implicit by monitoring adjacent neighbor's transmission activity while
the receiver is in promiscuous mode.  When a route is needed, route
discovery is performed--a process which consists of a two or
three-stage process. First, a source floods a query looking for the
destination, or some intermediate node that has a path to the
destination (as it travels, the query records the route it takes and
grows in length). If neither is found, the source can query again
later.  If either is found (this node is generically referred to as the
*replier*), a reply--carrying a full source route--is sent back towards
the source. If the replier has a route to the source (this will always
be true if one assumes unidirectional links), the reply is unicast;
otherwise, it is piggybacked onto a query looking for the original
source (the query is also recording the route back to the destination).
When the source receives the route, it may begin sending data.  If the
reply was piggybacked, then the source also replies to the replier via
unicast sending it the route by which the source may be reached.  The
protocol makes use of aggressive caching in that any node particpating
in the exchange may snoop on the routing information in the control
packets to keep its cache up-to-date.  Also, the protocol has no hello
protocol (periodic link status messaging)--link health is monitored
passively. It was mentioned that one way to view the protocol is as a
multihop extension or generalization of ARP. 

Simulation results for DSR were also presented, but these are also
preliminary. 

Dave was asked about the suitability of this scheme for supporting
multicast, and the answer was that there was not enough information to
draw any conclusion.  However, there was concern within the group about
the possibility of performing source routing for multicast due to
scalability limitations.

Agenda Item 5, Scott Corson

Resumed presentation of MANET issues draft...

The WG's near-term goal is the development of a *unicast routing
protocol* to support traditional, connectionless IP datagram delivery
in a MANET: integration with the greater Internet is--for the
moment--secondary.  

The protocol may contain multiple routing *modes*, each appropriate for
a given networking *context*, and a standard, distributed *mode
discovery* protocol would be devised to allow nodes to dynamically join
existing networks.  A networking context is a collection of attributes
including network size, rate of topological change, available
bandwidth, radio and link characteristics, battery limitations, etc.
which affect the functioning of a routing algorithm. Implicit in this
approach is that routers be able to function as intermode gateways
should two MANETs running differing modes merge, or should a router
have multiple radios communicating with different neighbors running
different routing modes. (Editorial note: A policy for dynamically
switching modes on-the-fly is viewed as a research issue and is not
being considered.)  It was emphasized that while multiple modes may be
permitted, there would have to be a clear and overwhelming need for
more than one mode--a need demonstrated via comparative simulation. The
intent is for the protocol to operate efficiently in any networking
context or topology--ranging from small, quasi-static work groups to
large, mobile networks.  This may require more than one routing mode.

A discussion then ensued about whether the scope of the group's effort
should be limited to purely *autonomous* operation (standalone with no
integration with the larger Internet), *stub* operation (access to the
greater Internet via a single gateway or multiple gateways), or
*transit* operation (access to the Internet via multiple gateways
permitting flow of exogenous Internet traffic *through* the MANET
cloud).  It was suggested that the transit mode of operation was
significantly more difficult to implement as it required advertisement
of IP reachability information between the gateways, and recommended
only stub network operation.  There was concern in the group that
transit style operation would be too complex, and could also
potentially congest the ad hoc network with exogenous traffic. Still,
there was no attempt to reach consensus in the WG on this issue
yet...people wanted to think about it a bit. There was a request for
someone to author a draft on all the issues and trade-offs of stub vs.
transit operation but, to date, no one has volunteered to do so.

There was a lengthy discussion regarding whether these wireless nodes
(combined routers/radios) should have a unique IP address per interface
(traditional IP practice), or simply one IP address per node (as
assumed by many algorithms proposed for ad hoc routing).  There are
advantages and disadvantages to each approach, and the group consensus
leaned towards staying with the traditional approach.

The question was also raised as to whether routing should be a layer 2
or layer 3 function? Numerous multihop wireless networks have
implemented routing at the layer 2 subnet level with a mapping to IP
only at the edges such as the NTDR network. The consensus of the
working group was to implement routing as a layer 3 function.  The
MANET issues draft states that the rationale is much the same as the
original Internet--to develop a homogeneous networking capability over
a heterogeneous networking infrastructure.  In this case, the
infrastructure is wireless, rather than hardwired, with multiple
platforms, radios and access technologies.

The question was then raised as to whether multicast routing should be
addressed now, or deferred until later.  The consensus was that the issue
should be deferred and that the group should focus on unicast routing. 
However, it was recognized that for efficient operation, multicast
routing could benefit significantly if tightly coupled to the unicast
algorithm.  Thus, suitability for supporting multicast (and QoS) should
be part of the evaluation criteria when examining unicast protocols.

Discussion then drifted to the group's charter and its listing of
milestones.  Then was strong consensus within the group that the existing
charter's schedule is still too aggressive, and that reaching consensus
on one or more MANET modes by August '98 is highly inprobable.  A rough
time scale expansion estimate of 50% was suggested, moving the target
date for consensus back to March '99.

Presentation of the draft continued, listing MANET protocol design
considerations and idiosyncrasies:
- scarce BW
- rapid topology changes
- limited physical security
- unidirectional links
- nodes may need to sleep
and how these need to be considered in the evaluation of proposed MANET
routing modes.

A listing of potentially desirable qualitative characteristics for a MANET
routing mode was given:
- distributed operation (required)
- loop-free operation (recommended)
- demand-based operation (recommended) for non-uniform traffic patterns
- support for unidirectional links (recommended)
- secure operation (recommended)
- sleep period accomodation (recommended)
When writing drafts describing proposed modes, authors should indicate
whether or not their proposals incorporate these characteristics.  In
general, it was requested and emphasized that authors include qualitative
listings of the strengths and weaknesses of their proposals so that a
broad assessment and classification of the protocols in terms of
suitability for various networking contexts can be made.  

Following such assessments, appropriate simulation-based quantitative
studies will be made to determine a mode's: 

* data routing performance--that is, the *goodness* of data routing
measured via throughput and delay or other metrics (the *external* view of
how well a routing mode performs its function).

* routing efficiency--that is, for a given level of data routing
performance, how *efficient* is a routing protocol--measured in terms of
network resource consumption (bandwidth, memory, processing, energy)--in
delivering this level of performance (the *internal* view of how well a
routing mode performs its function).

In MANETs, routing efficiency is paramount as certain network
resources--namely bandwidth and power--may be very scarce, yet are
utilized by the protocol in performing its function.

The discussion on protocol evaluation moved to simulation, and to what
level of detail would be necessary to have an accurate and realistic
performance evaluation.  There was much contention here within the group
covering issues such as:

- how accurately to model a radio channel?
- need we consider terrain/environmental models?
- do we need to model a multiple access protocol in the simulation?
- does the choice of a multiple access protocol favor one mode over
another?
- do we need to use a common simulation tool?
- what sorts of mobility models are appropriate?  If brownian motion is
no good, what's any better?
- how does the choice of a mobility model affect relative protocol
performance?
- etc.

The discussion was contentious and consensus was no where in sight when
the discussion had to be curtailed due to time constraints. During the
discussion, people continued to talk past each other due to the lack of
a common frame of reference (a set of commonly accepted definitions for
the terms being used in this context).  Thus, the need for a *MANET
lexicon* became apparent, and it was agreed to begin drafting one as
an Informational RFC to aid group communication.  What came out of the
discussion was general aggreement as to the need for a common simulation
tool so that models can be shared and simulation results mutually
verified.  The two leading candidates are Maisie and NS as they are
freely available.  There was general aggreement to take the discussion to
the list.

The following is a condensation of *action items* identified during the
meeting:

* Drafts of proposed routing modes are due by the end of October. 
These should be highly detailed documents, fully specifying the
proposed mode's operation with its advantages and limitations.

* Add to MANET issues draft requirement of suitability for future
multicast and QoS support for routing modes

* Add to MANET issues draft section dealing with the pros and cons of
stub vs. transit operation

* Fix MANET issues draft--remove usage of term subnet (too much historical
baggage) and clarify the intended meaning

* Add to MANET charter a list of what we will NOT do--that is, we will
not consider transit operation in the near term, if ever

* Modify MANET charter milestones, pushing back the date for consensus
until March 1998.

* Create MANET Lexicon document (Charlie Perkins to draft)

* Fully define the meaning of performance comparison for routing modes
(take to list)

* Come to aggreement on simulation framework (take to list)

* No hyphen in *Ad hoc*, only a space ;-)


There is an open call for drafts on the following topics:

* Mode discovery protocol

* Intermode gateway framework protocol