NOTE: This charter is a snapshot of the 40th IETF Meeting in Washington, DC. It may now be out-of-date. Last Modified: 24-Oct-97
Joseph Macker <email@example.com>
Scott Corson <firstname.lastname@example.org>
Routing Area Director(s):
Joel Halpern <email@example.com>
Routing Area Advisor:
Joel Halpern <firstname.lastname@example.org>
General Discussion: email@example.com
To Subscribe: firstname.lastname@example.org
In Body: subscribe manet
Description of Working Group:
A "mobile ad-hoc network" 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 focus of the working group will be to standardize an intra-domain unicast routing protocol which efficiently reacts to topological changes while maintaining effective routing. 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 examine the security issues around this protocol. They will consider the intended usage environments, and the threats that are (or are not) meaningful within that environment.
Goals and Milestones:
Post as an informational Internet-Drafts a discussion of mobile ad-hoc networking and issues.
Agenda bashing, discussion of charter and of mobile ad hoc networking draft.
Post Internet-Drafts for candidate protocols.
Discuss proposed protocols. Obtain early performance results for the protocols.
Obtain comparative performance results for the protocols. Implement the various protocols and test.
Reach consensus on a mobile, ad-hoc unicast routing protocol.
Document mobile ad-hoc routing protocol and submit to the IESG as a proposed standard, including security threat analysis.
· Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations
· Mobile Ad Hoc Networking Terminology
· The Zone Routing Protocol (ZRP) for Ad Hoc Networks
· Ad Hoc On Demand Distance Vector (AODV) Routing
· Temporally-Ordered Routing Algorithm (TORA) Version 1 Functional Specification
· An Internet MANET Encapsulation Protocol (IMEP) Specification
No Request For Comments
Minutes of the Mobile Ad-hoc Networks (manet) WG
Reported by: Erik Guttman <email@example.com>
Edited by: Joseph Macker <firstname.lastname@example.org>
Please note that any decisions will be set out by '***' and indentation.
MANET WG Agenda: Session #1
Opening Issues (0930-0945) - Joe Macker
Agenda Bashing, Charter Issues
Overview of IMEP Internet Draft (0945-1015) - M. Scott Corson
Overview of TORA and Internet Draft (1015-1100) - Vince Park
Overview of AODV Internet Draft (1100-1130) - Charlie Perkins
MANET WG Agenda: Session #2
Update of Other Drafts and Issues (1930-1945) - Joe Macker
NS2 and mobile routing simulation (1945-2000) - Kevin Fall
Overview of ZRP Internet Draft (2000-2030) - Zygmunt Haas
Review of DSR and Monarch Project (2030-2100) - Dave Johnson
Discussion of Mobile Routing Investigations (2100-2130) - Jay Strater
Open Discussion (2130-2200)
Background will be discussed
***Action Item - produce initial routing approaches documents
Drafts will be considered today and Wednesday.
***Issues documents will be INFORMATIONAL.
I. Introduction - Joe Macker
Munich action item was to present some details of proposed protocols at DC. That is what we will do. We will also consider modifications to the charter and pursue general discussion at the end of the Wednesday meeting.
II. IMEP - Scott Corson
Purpose: This protocol draft allows for message aggregation and encapsulation and is designed as a candidate support protocol for manet routing protocols.
Terminology overview: The terms presented in the draft were defined; attention was given to "Mobile Nodes", "Components" and "Topologies".
The idea of a "routing fabric" was discussed. This was described as the union of topologies across multiple physical topologies.
IMEP has a single hop connection state maintenance capability. This is not assumed to be provided by all technologies and this functionality can be TURNED OFF. More detailed connection status capability may be added in the future. Indirect use of "Beacon" and "Hello" techniques can potentially support unidirectional logical connections.
Q & A:
What are the performance considerations? IMEP will consider future extensions for this.
It was pointed out that radios may not be able to overhear traffic (IMEP considers support for both broadcast and point to point cases of link transmission.)
***Open issue: How to best specify the router identifier?
III. Temporally-Ordered Routing Algorithm (TORA) - Vincent Park
See http://tonnant.itd.nrl.navy.mil/tora/tora.html for more information on TORA.
TORA uses a metric referred to as the "height" of the node to assign a direction to links for forwarding packets to a given destination. The node heights can be totally ordered lexicographically, and thus define a directed acyclic graph rooted at the destination.
There are three functions: creating routes, maintaining routes and erasing routes.
Creating routes is performed on demand using a query/replay process.
When a node loses its last downstream link the algorithm reorients the directed acyclic graph such that all downstream paths lead to the destination.
Reoptimization of routes:
TORA does not compute the shortest path: paths may be suboptimal. It starts close to optimal and tends to "loosen", as it reacts to topological changes. A secondary mechanism, not tied to the rate of topological change, is used to reoptimize routes.
Partition detection and erasing routes:
Partitions are detected when a 'reversal' reaches a node with no downstream links and all of its neighbors have the same 'reflected reference level,' which it previously defined. A node that detects a partition initiates the process of erasing the invalid routes.
Performance of TORA was compared to Ideal Link-State (ILS) and pure flooding. Since TORA often provides multiple downstream routes, a next-hop forwarding decision is required. Two different forwarding policies were evaluated: TORA - for each packet randomly(based on uniform distribution) select one of the downstream neighbors to forward the packet to, and TORA LN - forward all packets to the "lowest" downstream neighbor.
Simulations used fixed network topologies with the ability to fail and recover links based on an exponentially distributed time intervals. This was an adjustable parameter used to vary the rate of topological change. Other parameters used to vary average network connectivity and message traffic load. Multiple baseline topologies were used to evaluate the effect of network size on routing performance. Performance comparison was based on measure of control and data traffic, end-to-end message packet delay and message packet throughput. As rate of topological change was increased, the control overhead for ILS increased significantly faster than for TORA. Excessive ILS overhead caused network congestion, resulting in longer end-to-end message delay. TORA outperformed ILS (in terms of bandwidth utilization and end-to-end delay) under conditions of high rates of topological change. As network size was increased, TORA outperformed ILS at lower rates of change. The throughput statistics provided little insight into the difference between TORA and ILS, and thus were not presented. Traffic distribution was chosen to be the WORST case for TORA. Every node generated traffic (at exponentially distributed inter-arrival times) destined for every other node in the network.
Summary of results:
TORA performs better (than ILS) as rate of topological change is increased and as network size is increased. Network connectivity did not significantly affect relative performance of protocols.
In cases where the network is very static, it is better to use ILS. Otherwise, use TORA.
Question: Does TORA always converge?
Answer: TORA converges probabilistically with time. However, an example has been constructed, which shows that under certain conditions TORA can exhibit oscillatory behavior and need not converge within a finite time. The example is dependent on a specific topology and specific timing of events (packet transmissions), which makes it highly unlikely for the behavior to continue for multiple cycles. Vincent and Scott stated that there is a solution which guarantees convergence. An unscalable solution would be to only build routes from the destinations.
Question: Link up/down simulation was used to model motion. Isn't this a problem?
Answer: No - This is an acceptable model for simulation of protocols that do not benefit from spatial/time correlation like TORA.
IV. AODV - Charles Perkins
See http://www.srvloc.org/~charliep for slides and documents.
Assumptions: (to be discussed)
Bidirectional links (AODV can work for unidirectional links)
No sleep mode
Only one route needed per destination (wouldn't this be good anyway?)
The Subnet model from IP is not a good model to work from.
AODV is loop free. There is a proof. Every node which could make a loop has information from the destination (the sequence number.) Even if there are broken links, there is no problem.
AODV won't generate the 'counting to infinity problem.' Shouldn't this be a requirement of any MANET protocol which is promoted as a standard?
The source sequence number is provided for a reverse route. The destination sequence number is used for the forward route. The route discovery request will not obtain older routes than the one which is implied knowledge of the requester: The request includes the sequence number of the destination already known to the requester.
Previously broadcasted messages will not be rebroadcasted, through the use of a unique id. Nodes notify all neighbors when link breakage is detected.
It was claimed there is little overhead for AODV and that it is simple to implement. There is no data overhead for each message passed along known routes.
How was mobility factor simulated? The nodes' speed was increased.
Question: What happens if a node forgets its sequence number?
Answer: An AODV implementation will require some nonvolatile storage, it seems. This requires some more thought and may not be necessary.
The hello message is achieved by L3 beacons, though L2 or L1 would be better if they could be relied upon.
Some simulations comparing AODV to DSR were briefly mentioned and it was claimed that DSR requires more control data and has less effective bandwidth utilization.
I. WG Status Discussion - Joe Macker
Update drafts, folks.
In Munich, it was decided that it was wise to elongate the charter as group convergence and related development efforts likely to take longer than initially surmised. The charter was reviewed in DC during this meeting. The following decisions were made:
***Attempt to wrap up (as informational) the Issues and Terminology drafts by February.
Regarding protocol development and standardization:
***Discuss requirements for proposals and a taxonomy of approaches by March.
Some topics to consider for this March goal:
Are there link layer interface issues that need to be decided before progress can be made? We should talk about this, but how far can and should we go in MANET? Perhaps we should follow the INTSRV model and move these issues to a separate WG, if needed.
Security considerations - Requirements and issues need to be discussed sooner rather than later. Related protocols and interactions with them should also be considered.
Developments should roughly proceed as follows, so says the new charter:
***Initial working prototypes should exist and potential mergers of different proposal features may be considered, if desireable by Summer 98.
Work will progress to meet the following objectives:
***Required modifications to protocols should be achieved. Any required additional performance analysis/comparison should be completed by March 99.
We will end up with a
***Standard track protocol (or protocols) to advance as a proposed standard by December of 1999.
Question: Is there anything wrong with this? (No answer in recorded minutes. No vocal dissent was made to the suggested charter goals.)
Implementation status and reviews should be done as they are ready.
Qualitative and quantitative comparison of protocols: We need common models so that we can compare and analyze results achieved by the different design efforts.
It was noted that common simulation and traffic models would be useful. Should this be MANDATORY? This would be lots of work, but it would be an ideal way to make comparisons between the protocols. Just coming out with these models and techniques would already be a terrific result for the MANET WG.
What are the interactions between protocols? Focus on DNS, SECURITY, etc. Focus on the routing implications.
What is the effect of lower levels? What if information is hidden from the upper layers? How much needs to be discussed regarding L2/L3 interface requirements?
***To clear some of this up, it was suggested that applicability statements be included when and where appropriate. Statements should include notes on where the protocol works best, what scenarios it best applies to and any known limitations.
II. NS2 and directions for Mobile Routing Simulation - Kevin Fall
How is this simulation technology structured and how is it useful to us?
NS2 simulates traffic, multiple protocols and scaling.
There is currently no help desk - get help via the mailing list. There is a user community that is beginning to solve problems independently.
There is a C++ engine with OTCL.
Protocols, links, nodes, packets and other elements are modeled. Objects are implemented in C++ and controlled using OTCL. This is a fine grained simulation (e.g., links may require 3 objects). Routing is a system of objects. Error generators can be added to a topology to simulate motion, using distributions. Queuing is supported, with various different algorithms. Visualization is possible using the "nam" tool.
NS1 was used to simulate tcp congestion control. Newer TCP has nearly the full state machine. Other protocols supported include rtp, rtcp, srm, 802.3, 802.11, tcp (2 modes) and variants, udp, ip...
"Packet filter" capabilities exist.
An example of node modeling and link modeling was presented (see the presenter's slides.)
Strategies for simulation:
Static, precomputed routes with "causality." Only distance vector approaches allow 'dynamic' characteristics to be modeled, for now.
Parameters include multiple routing numbers and preferences.
Routing architecture includes stateful objects which track 'subobjects' This allows fine grained decompositions.
- Dynamic link failures can be simulated.
- All links are simplex.
- IP multicast is supported.
- Many protocols are supported.
- New work (VINT simulation with LIVE networks)
See: http://www_mash.cs.berkeley.edu/ns and others (many) list: email@example.com "subscribe ns-users"
There are some people doing mobility simulation with a NS derivative. Get in touch with them on the mailing list.
Doesn't have links in the classic sense. You would have to simulate this with a time series of up/down links in order to fabricate movement scenarios.
Point to point versus fully connected? MAC additions to NS2 are fairly new. Carrier sense - not implemented. Collisions are implemented.
It is believed that Randy Katz (at UCB) is using NS2 for wireless simulation.
Top down TCP work -
The accuracy of the TCP model will be really useful to help us figure out the affect of manet routing on upper layers (using end to end measurement).
NS2 can use alot of memory especially for links which go up and down (i.e., to simulate mobility). Benchmarking here needs to be further explored.
Finally, it was claimed that the recent ns2 package has become pretty stable.
III. Zone Routing Protocol - Zygmunt J. Haas
Specific classes of ad-hoc network are addressed:
- Large (100s of hops in diameter), with 10,000s of nodes.
- From stationary all the way to highly dynamic configurations
- Diverse data streams (e.g., multimedia)
- Rapid network reconfiguration is required
- Some communication environments are harsh
- Fast protocol convergence is essential (increases in speed or changes in topology result in a proportional raise in control traffic. But, as the topology rapidly changes, most of the control information is not even used.)
- Degree of globalization: (It would be good to propagate information only locally, where it could be of interest. Propagating the information within the whole network corresponds to significant waste of network resources.)
- If too little information is propagated, then flooding needs to be used to discover routes. This leads again to inefficiency and long delays in obtaining routes
- Consider an ad hoc network as a flat space (with overlapping radii) or as a hierarchy.
- We will assume flat for our discussion here.
Proactive routing: continuously learns the network topology, by exchanging routing information; examples: Distance Vector, OSPF, etc.
Reactive routing: (also called "on demand") discovers routes when necessary. Pure flooding is an example of reactive scheme.
Claim: Both are inadequate for ad hoc networking. Proactive wastes effort. Reactive is slow to find destinations (especially with 100s of hops.)
Hybrid schemes remove the disadvantages of both. Use the best of each.
ZRP is NOT "another routing scheme". It takes different schemes and applies it to a much larger network.
- The terms 'zone radius' and 'periphery' were defined.
- Zone is counted in hops not a transmission radius.
- 'bordercast' send to all peripheral nodes.
- Divide and conquer - each node proactively learn its zone (by using AODV, for example) and reactively jump between zones. The first component is called Intrazone routing and the second is Interzone routing.
- Learn the entire topology of zone identity and minimal distances.
- Only within X hops (updates propagate only locally). Use DV or even OSPF.
- Source knows whats in its zone. If the dest is not there it Bordercasts. If it is not there, Bordercast again. Eventually it will reach zone with Destination.
- Since the contend of the zone is much bigger than the number of its peripheral nodes, bordercasting results in much less control packet transmissions, relative to flooding. It also propagates faster than flooding.
- Assumes all links are bidirectional.
- How fast the network can reorganize itself:
If nodes move faster than bordercasting gets to the end and back you can only do flooding.
ZRP assumes the existence of a NDP (Neighbor Discovery Protocol). It defines a RAP (route accumulation protocol). Routes get bordercasted which build up source routes, to be returned to the querying nodes. These source routes are considerably smaller than in classic source routing, since the nodes are separated by zone radius (e.g., 10 addresses not 50, for 50 hops and zone radius = 5).
Flood termination must be carefully optimized. There are a number of flood termination techniques that have been investigated.
Bordercasting with multicast(?) trees are used to optimize. Do NOT bordercast back into zones. 3 Flood termination techniques were eluded to but not elaborated on due to lack of time.
- If there exist multiple routes, the ZRP will find all of them. You can use the first one only. Also, if a node knows a route to the destination, it can respond to the query, terminating the flood thread.
- Flooding is required (traversing all network nodes) to discover a route, but less network resources will be required than a pure flooding approach.
- If there is a route ZRP will find it. There is a proof.
***This proof was requested and will be included by Zygmunt Haas in the minutes.
The choice of the zone radius depends on how fast the network reconfigures itself and how often route requests are generated. In a highly mobile system, use small radius (e.g., radius=1 (flooding)). In a very stable network, assign very large zone radius. The middle ground calls for a setting the radius to an intermediate value. Optimizing the zone radius results in decrease in the amount of control traffic.
Simulation did not include multicast effect. This would further decrease the
control traffic overhead. The simulation used unicast. In general, it is not
clear whether multicasting could be used in highly reconfigurable networks.
IV. DSR - Dave Johnson
Please refer to the minutes of the 39'th IETF for details of the DSR presentation.
V. Modeling considerations for Ad Hoc Routing Protocols - Jay Strater: Mitre
The simulator used was OpNet with homebrew additions, and netlab.
Some channel access and routing protocols have been simulated.
- It would be great to simulate all the way down to the physical layer. But what do you really need?
- The army looks at a mix of traffic, addresses, service requirements, distribution of nodes, terrain, mobility factors.
- The physical and lower layer protocols are approximated.
Classes of traffic:
- Engagement ops: reliable, timely
- Command/control: reliable, slower
- Situational Awareness: time sensitive, not critical
- Entire network of nodes: All nodes are sources and destinations.
- Lots of multicast applications.
Raleigh normal statistics are used. Node distributions, propagation losses and topology are drawn from 'terrain maps'. You can simplify this process by using node connectivity from statistics and propagation analysis.
How many nodes are up or down? Radio mobility was discussed -
- Noise and background interference is hard to simulate.
- Physical layer overhead - important to consider.
- Assume perfect acks.
- Framing overhead
- Transimssion overhead
- Military: Uses long preambles.
Evaluation framework: (factors evaluated for 300 and 1000 nodes, under 300 (platoon sized) are considered too small for the high-grade communication equipment.)
- traffic mixes, types - connectivity (dense/sparse)
- source and destination addressing - mobility factors
- loads - network sizes
- routing protocols
Notes on messages and transport in mobile nets:
- TCP doesn't work well. One needs a variant. Could this be NETBLT?
- Consider packet performance, not message performance.
By the end of the year, the project at MITRE will let folks have access to
their model. They will apply their techniques to Garcia and Perkins
algorithms. They will start work on layouts for terrains, using averages
and histograms for their simulators.
Mix of voice, data with various distributions of range will also be included.
VI. Administrative Issues, Wrap up - Joe Macker
We should wrap up work in the next couple of months on the Issues and Terminology documents.
Items with "!!!" were not adopted as official action items of the WG but they were very clearly points which the WG should address.
!!! We need to decide whether to allow broadcast in MANET protocols. !!!
Also we need to decide on the role of other issues, e.g., QoS and Unidirectional routes angry and.
A noble goal in itself is a common simulation environment for mobile networking software.
On the broadcast issue: We can't ignore this one. Some protocols are not friendly to [the absence of] it. Applicability statements will have to be written noting whether it is required or whether approaches can use it.
With some media, you cannot eavesdrop on communications.
Should we allow or consider heterogeneous link layers? It was pointed out that this is a major goal of routing at the IP layer and should be preserved unless strong arguments are give to the contrary. Design for what is realistic: We don't know where the technology is going in two years.
!!! We need to decide what the design space is for link layer interfaces. !!!
It was pointed out that discussion emphasis has so focused largely on potential radio routing technologies. What about IR? There are "non-radio" wireless technologies. This brought up the point again regarding whether the group should write about "channel access" and "specific link layers" in drafts? It was cautioned that this can lead into a "can of worms" but there was consensus that this warrants more exploration.
!!! We need to decide which security aspects are in or out. !!!
Should the WG consider denial of service attacks? This is very hard for a routing protocol running over wireless environments. It was suggested that a more detailed security context for manet approaches be developed - with work items which can be solved.
With low power and short range, you need to use link layer information (which is specialized). Or do we create a 'family' of protocols which can rely on certain link layer facilities? Or do we work for a general protocol which doesn't use link layer information (which would be more expensive).
- Multipath routing, should we consider it?
- Support for multicast. Is this in or out of scope?
Modeling Considerations for Evaluating Ad Hoc Routing Protocols
NS2 (and possible directions for mobile routing simulation)
The Temporally-Ordered Routing Algorithm (TORA)
go to list