Subject: draft minutes for ietf 40

From: Erik Guttman <[email-masked]>
Date: Tue, 23 Dec 1997 08:22:43 +0100 (MET)

You will find a draft of the MANET minutes, mime attached to this message.

Please send revision notes to Joe Macker who will do the final revision
of the minutes for submission to the IETF secretariat.

Erik Guttman

Manet minutes at the 40'th IETF
=======================================================================

Minutes by Erik Guttman <[email-masked]>
Prepared 23 December, 1997.

Please note that any decisions will be set out by '***' and 
indentation. 

----------------------------------------------------------------------
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 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 allows aggregation and encapsulation.  
  It provides layering for upper level 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 is the union
  of topologies acros multiple physical topologies.
  
IMEP has connection state maintenance.  This is not assumed to 
  be provided by all technologies.  It can be TURNED OFF.
  More detailed connection status may be added in the future.
  "Beacons" and "Hellos":  Indirect use of these techniques
  can potentially support unidirectional logical connections.
  
Q & A:

Unidirectional links:

  What are the performance considerations?
  
  IMEP will consider extensions for this.
  
  Radios may not be able to overhear traffic (consider the 
  broadcast vs point to point cases of transmission.)
  
What is the name of the end points?  Does this raise questions about the
use of identifiers?  

  ***
      Open issue:  How does one specify the identifier?
  ***

TORA - Vincent Park
-------------------

TORA has two functions, route creation and route maintenance.

  (Unique IDs are achieved by using IP addresses.  Administration
  of these addresses is not specified.)
  
TORA uses height values to achieve a 'lexicographical representation.'

There are three functions:  
  UPD (update) - propogates routes back, using a link reversal
    algorithm.  UPD is also used for maintenance, and may result in
    reorienting the direction of directed graphs edges.  
  ERA (erase)
  QRY (query) - Flooded.

  It achieves a 'direction assignment' through calculations of these
  weights.  This becomes a directed acyclic graph for each node in the
  network.
  
  Example:  Propogation of UPD informs neighbors of heights, provides
  information for calculating (close to) optimal routes.
  
Route maintenance:

  When a node loses its last downstream link it attempts to
  'regenerate' a route.  Decisions are made as part of the algorithm to
  generate a new route, erase an old one or detect existing ones.

Reoptimize routes:

  It is possible to reoptimize routes over time.  TORA does not give
  you the shortest path:  It is suboptimal.  It starts close to optimal
  and "loosens", diverging with time.  Reoptimizing routes should occur
  more often if there is more change in the network. The less often it
  is done, the less control overhead.
  
Partition:

  Partitions are detected when a 'reversal' reaches the node where
  there exists no downstream links.  All neighbors have the same
  'reference level.'  Total ordering removes ambiguity (the highest
  'timestamp' achieves the new 'highest level') - each node has a
  consistent view of the topology after partition information is
  propogated.
  
Simulation:

  Question - what measures should be used for comparing protocols?
  Suggestion - Data and control traffic should be normalized with
  control bits.
  
  End to end delay was considered, as was throughput.
  
  Scenarios:

    A random uniform distribution was assumed.
    The policy of "always forward to one's best neighbor" was compared
    against an "ILS" textbook shortest path algorithm.  TORA performed
    close to 'best'.
  
  Simulation description:
  
    LInks go up and down on an exponential distribution.  This was an
    adjustable parameter (used to simulation motion, right?)
    
    Control requirements increases faster with TLS (as the failure #s
    increase) than for TORA.  TORA outperformed TLS (in terms of delay)
    in high rates of change in the network.  Throughput statistics
    provided little insight into the differences between TORA and TLS.
    
    Simulation parameters were chosen to be the WORST case for TORA.
    Every node generated traffic with every other, with fixed
    transmission rates.
    
  Summary of results:
  
    TORA performed better in conditions of topological change and as
    size increases (than TLS).  Connectivity did not factor into the
    comparison (it was deemed to be an independent parameter.)  
    
    In cases where the network is very static, it is better to use TLS.
    Otherwise, use TORA.
    
Problem:

  There was a condition discovered in analysis of TORA which makes it
  difficult to converge.  Vincent and Scott stated that there is a
  solution which guarantees convergence in this case.  
  
  An unscalable solution to this problem 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 - Simulation experience indicates that it isn't.

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.

There is little overhead and 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 nonvolitile
           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.

DSR requires more controld data and has less good bandwidth
utilization, it was claimed.

----------------------------------------------------------------------
Wednesday meeting
----------------------------------------------------------------------

WG status discussion - Joe Macker
---------------------------------

Update drafts, folks. 

In Munich, it was decided that it was wise to elongate the charter as
convergence might 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
        Termionology drafts - by FEBRUARY.
   ***
   
Regarding protocol development and standardization:

   ***  
        Discuss requirements for proposals and taxonomize problems - 
        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 we go
  in MANET?  Perhaps we should follow the INTSRV model and move these
  issues to a separate WG.

  Security considerations - Requirements and issues need to be discussed
  sooner rather than later.

  Related protocols and interactions with them should be considered.
   
Developments should proceed as follows, so says the new charter:

   ***
        Working prototypes exist.
        Mergers of different proposals considered.
        - By SUMMER 98.
   ***
   
Work will progress to meet the following objectives:

   ***
        Modifications to protocols have been achieved.
        Interoperable implementations of the protocols exist.
        - By MARCH 99.
   ***
   
We will end up with a 

   ***
       Standard track protocol (or protocols) to advance as a proposed
       standard.  - By end 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.

Charlie 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?

   ***
        Write applicability statements.  Include notes on where the
        protocol works best and what scenarios it applies to.
   ***

NS2 and directions for Mobile Routing Simulation - Kevin Fall
-------------------------------------------------------------

How is this routing 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 (links may require 3 objects, etcetra.)

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.  This is good for evaluating
dynamic effects, such as Ack implosions.  This tool has been ported to
various unix platforms, and may run under windows.

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.

Multicast routing, ip routing, static unicast, dynamic (distance
vector) unicast, Queuing (red, fifo with last drop, cbq, wrr, drr, sfq)
Scheduling

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: [email-masked] "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 which is MANET protocol is best (using end to end measurement).

January 23 there will be an all day presentation on how to use this
simulation package.  

It uses a lot of memory especially for links which go up and down (ie.
to simulate mobility). 

The package has become pretty stable.

Zone Routing Protocol - Zygmunt Haas
------------------------------------

Specific classes of network were defined:

 - Large (100s of hops in diameter), with 10,000s of nodes.
 - Stationary, all the way to dynamic.
 - Diverse data streams (multimedia, and so on)
 
Considerations:
 
 - Rapid configuration required
 
 - some applications are 'harsh'

 - diverse topologies (Increases in speed or changes in topology have
   the result of a proportional raise in control traffic.  More updates
   are generated than are actually useful, since little of the
   topological state information will ever be used.)

 - degree of globalization:  (It would be good to propogate information
   as little as possible.  This is especially true of information which
   is of local relevence only.)
 
 - If too little information is propogated, other problems arise.
   (I did not get Zygmunt's point here.  I assume if too little
   information is propogated one must resort to flooding, which is
   inefficient compared to using routing information you have already 
   gleened.)
   
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: Distance vector, OSPF, continuously knows routes.
Reactive routing: Flooding is the purest form.

Claim:  Both are terrible 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 a number of hops not a transmission radius.
 - 'bordercast' send to all peripheral nodes.
 - Divide and conquer - proactively (as with AODV)
 
Intrazone:

 - Learn the entire topology of zone identity and minimal distances.
 - Only within X hops (updates only propogate 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.
 - The radius of bordercast is bigger than the broadcast radius.
 - Assumes all links are bidirectional.
 - Assumption: 
 
     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 for updates.  These rates are
considerably smaller than classic source routing (10 addresses not 50, 
for 50 hops and radius = 5).

Very important:

  Flood termination must be optimized or worse performance than a pure
  flooding approach will be achieved.
  
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, this will find all of them.  You can
   get the first one.  Or transit nodes which know the routes can respond.
 - 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.
   ***
   
In a highly mobile system, just use radius = 1 (flooding).  If there is
a fully stable network, increase the radius and achieve real routing.
The middle ground calls for a hybrid approach, setting the radius to an
intermediate value.

Simulation did not inlcude multicast effect.  This would decrease the
control traffic overhead.  The simulation used unicast.

DSR - Dave Johnson
------------------

Please refer to the minutes of the 39'th IETF for details of the DSR
presentation.

Modeling considerations for evaluating Ad Hoc Routing Protocols - ???
from Mitre
---------------------------------------------------------------------

The simulator used was OpNet with homebrew additions, and netlab.

Channel access and routing protocols 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 fractors.
   
 - 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 addresssing:

 - Entire network of nodes:  All nodes are sources and destinations.  
 - Lots of multicast applications.
 
Raliegh normal statistics are used.  Node distributions, propogation
losses and topology are drawn from 'terrain maps'.  You can simplify
this process by using node connectivity from statistics and propogation
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.
  
Comments:

  !!!
      We need to decide whether to allow broadcast in MANET protocols.
  !!!
  
  Also we need to decide on QOS and Unidirectional routes.  If we
  decide now, we won't get angry and be unable to converge later.
  
  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 can use it.
  
  You need broadcast to discover things.  Do others need to listen to
  broadcasts?  Do others have the keys to decrypt broadcast messages?
  No directional beams are to be assumed, right?
  
  With some media, you cannot evesdrop on communications.
  
  Should we allow or consider heterogenous link layers?
  
  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.
  !!!
  
  Radio:  What about IR?  There are others. Should we write about 
  "channel access" in drafts?  This can create a mess:  Refer to the 
  mess created in the INTSRV WG.
  
  !!!
      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.  Develop a security context - 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:

 - Even in a radio environment you need topological routing.
 
 - Multipath routing, should we consider it?
 
 - Support for multicast.  Is this in or out of scope?

---

From: [email-masked] (Joseph P. Macker)
Date: Tue, 23 Dec 1997 11:59:41 -0500

>of the minutes for submission to the IETF secretariat.
Thanks to Erik for doing these draft minutes.
We are really on a short rope since the minutes are due tomorrow and I will not be working tomorrow or reading e-mail.  If you have critical input on these minutes, please get them to me ASAP as I will wrap up the final, revised version for submittal at 1700 EST today.
-joe