Subject: [manet] New draft for CDS flooding in MANETs

From: Richard Ogier <[email-masked]>
Date: Tue, 11 Jan 2005 20:23:51 -0800

Hello,

I have submitted a new draft describing and evaluating a family of
interoperable CDS algorithms for flooding in MANETs.

http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-02.txt

This work was done mainly for the OSPF-MANET effort, but should also
be pertinent to the MANET effort to develop a flooding protocol.

The following bullets summarize the main features of the solution
presented in the draft:

   - The document presents a family of interoperable CDS algorithms,
     which allow a tradeoff between path optimality and CDS size.
     Simulation results are presented to show this tradeoff.

   - The CDS algorithms are based only on 2-hop neighbor information,
     to provide fast convergence following topology changes.

   - The CDS algorithms are interoperable because the CDS computed by
     each algorithm contains a minimal, source-independent CDS called
     the "Essential" CDS. The Essential CDS can be computed in O(d^2)
     time, where d is the number of neighbors.

   - The Essential CDS is very scalable, as shown by the simulation
     results in Section 10. In a 300 node network with average degree
     64 and diameter 5, the Essential CDS consists of only 23 (8%) of
     the nodes on average.

   - The Essential CDS provides a minimal, source-independent set
     of relays for flooding LSAs (or other flooded packets).
     The flooding procedure also allows source-dependent flooding
     (using previous-hop information) as an option, if it is desired
     to flood packets along min-hop paths.

   - For improved CDS stability, each algorithm in the family has a
     "persistent" version, in which a router in the CDS remains in
     the CDS until it becomes redundant.

   - Generalizes the OSPF concept of a Designated Router (DR) and
     Backup DR to MANETs. The set of DRs forms a CDS, and the set of
     DRs and Backup DRs forms a biconnected CDS for robustness.
     When applied to a broadcast network, the persistent version of
     each algorithm computes the same DR and Backup DR as OSPF.

   - Adjacencies are formed only between CDS nodes (DRs and Backup DRs)
     and their neighbors, as in legacy OSPF.

   - Provides a flexible choice of which neighbors to include in LSAs,
     from a minimum set of neighbors adjacent to DRs and Backup DRs,
     to the full network topology.

Regards,
Richard

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet