Manet Meeting Minutes at the 40'th IETF
=======================================================================
Minutes by Erik Guttman <eguttman@eng.sun.com>
Edited by Joseph Macker <macker@itd.nrl.navy.mil>
Prepared 23 December, 1997.
Please note that any decisions will be set out by '***' and indentation.
MANET WG Agenda: Session #1
Monday (0930-1130)
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
Wednesday (1930-2200)
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)
Close
----------------------------------------------------------------------
Monday meeting
----------------------------------------------------------------------
Background will be discussed
***
Action Item - produce initial routing approaches documents
***
Drafts will be considered today and Wednesday.
***
Issues documents will be INFORMATIONAL.
***
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.
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:
Unidirectional links:
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?
***
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:
Creating routes is performed on demand using a query/replay process.
Maintaining routes:
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.
Simulation:
Protocol comparison:
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.
Simulation description:
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.
AODV - Charles Perkins
----------------------
See http://www.srvloc.org/~charliep for slides and documents.
Topics:
Assumptions: (to be discussed)
Broadcast
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.
----------------------------------------------------------------------
Wednesday meeting
----------------------------------------------------------------------
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 Dec 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.
***
NS2 and directions for Mobile Routing Simulation - Kevin Fall
-------------------------------------------------------------
How is this simulation technology structured and how is it
useful to us?
NS began as work by Van Jacobsen at LBL. It was used by the VINT
project, and is now being worked on at USC/ISI, UCB, LBNL, Xerox and
other sites. Funding continues till mid 1999.
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.
More detail:
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.
Facts:
- 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: majordomo@mash.cs.berkeley.edu "subscribe ns-users"
There are some people doing mobility simulation with a NS derivative.
Get in touch with them on the mailing list.
Radio:
- 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 vs. 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 (ie.
to simulate mobility). Benchmarking here needs to be further explored.
Finally, it was claimed that the recent ns2 package has become pretty stable.
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)
Considerations:
- 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
Hierarchies:
- 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.
ZRP:
- 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.
Intrazone:
- Learn the entire topology of zone identity and minimal distances.
- Only within X hops (updates propagate only locally). Use DV or even
OSPF.
Intrazone:
- 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).
Very important:
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.
Claims:
- 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.
DSR - Dave Johnson
------------------
Please refer to the minutes of the 39'th IETF for details of the DSR
presentation.
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.
Considerations:
- 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
Network addressing:
- 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.
Link layer:
- 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.
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.
Group Comments:
!!!
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 absense 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 heterogenous 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 2 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).
Other issues:
- Multipath routing, should we consider it?
- Support for multicast. Is this in or out of scope?
From - Thu Jan 15 14:27:22 1998
Received: from itd.nrl.navy.mil (s2.itd.nrl.navy.mil [132.250.83.3])
by ns.ietf.org (8.8.7/8.8.7a) with ESMTP id OAA07790
for <minutes@ietf.org>; Thu, 15 Jan 1998 14:24:30 -0500 (EST)
Received: from roux.itd.nrl.navy.mil (roux.itd.nrl.navy.mil [132.250.92.49])
by itd.nrl.navy.mil (8.8.8/8.8.8) with SMTP id OAA21659;
Thu, 15 Jan 1998 14:23:32 -0500 (EST)
Message-Id: <3.0.1.32.19980115142134.006c1d5c@pop.itd.nrl.navy.mil>
X-Sender: macker@pop.itd.nrl.navy.mil
X-Mailer: Windows Eudora Pro Version 3.0.1 (32)
Date: Thu, 15 Jan 1998 14:21:34 -0800
To: minutes@ns.ietf.org
From: Joe Macker <macker@itd.nrl.navy.mil>
Subject: Revision of Manet Minutes from 40th IETF
Cc: kfall@ee.lbl.gov, corson@isr.umd.edu
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Length: 24905
Status:
X-Mozilla-Status: 8001
There has been a slight correction made to the manet minutes.
Please substitute this latest version for the previous submitted minutes.
----------------- cut here ----------------------
Manet Meeting Minutes at the 40'th IETF
=======================================================================
Minutes by Erik Guttman <eguttman@eng.sun.com>
Edited by Joseph Macker <macker@itd.nrl.navy.mil>
Prepared 23 December, 1997.
Please note that any decisions will be set out by '***' and indentation.
MANET WG Agenda: Session #1
Monday (0930-1130)
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
Wednesday (1930-2200)
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)
Close
----------------------------------------------------------------------
Monday meeting
----------------------------------------------------------------------
Background will be discussed
***
Action Item - produce initial routing approaches documents
***
Drafts will be considered today and Wednesday.
***
Issues documents will be INFORMATIONAL.
***
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.
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:
Unidirectional links:
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?
***
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:
Creating routes is performed on demand using a query/replay process.
Maintaining routes:
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.
Simulation:
Protocol comparison:
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.
Simulation description:
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.
AODV - Charles Perkins
----------------------
See http://www.srvloc.org/~charliep for slides and documents.
Topics:
Assumptions: (to be discussed)
Broadcast
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.
----------------------------------------------------------------------
Wednesday meeting
----------------------------------------------------------------------
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 Dec 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.
***
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.
More detail:
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.
Facts:
- 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: majordomo@mash.cs.berkeley.edu "subscribe ns-users"
There are some people doing mobility simulation with a NS derivative.
Get in touch with them on the mailing list.
Radio:
- 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 vs. 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 (ie.
to simulate mobility). Benchmarking here needs to be further explored.
Finally, it was claimed that the recent ns2 package has become pretty stable.
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)
Considerations:
- 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
Hierarchies:
- 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.
ZRP:
- 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.
Intrazone:
- Learn the entire topology of zone identity and minimal distances.
- Only within X hops (updates propagate only locally). Use DV or even
OSPF.
Intrazone:
- 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).
Very important:
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.
Claims:
- 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.
DSR - Dave Johnson
------------------
Please refer to the minutes of the 39'th IETF for details of the DSR
presentation.
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.
Considerations:
- 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
Network addressing:
- 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.
Link layer:
- 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.
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.
Group Comments:
!!!
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 absense 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 heterogenous 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 2 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).
Other issues:
- Multipath routing, should we consider it?
- Support for multicast. Is this in or out of scope?