Subject: RE: [Ospf-wireless-design] Simulation needed: CDS vs. OverlappingRelays

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 7 Feb 2005 22:23:47 -0800

> >However, I think that we (DT) need to do 
> >simulations to really understand and compare the behavior of the CDS 
> >algorithms and Overlapping Relays.  It wouldn't be fruitful 
> to embark 
> >on a theoretical debate without the simulations.
> >
> Yes, I agree.  Theoretical debates can be misleading.
> I think that Tom's group is planning to implement some of the 
> algorithms from my draft in the GTnetS simulation.
> I can also help with this.
> 
> >
> >
> >How can we work as a DT to have Richard's models and 
> Boeing's models on 
> >the same simulation platform...maybe Richard's models can be 
> ported to 
> >the GTnetS simulation engine that Tom released?  This would be very 
> >helpful in running simulations to compare CDS and 
> Overlapping relays.  
> >Of course, we would need to validate the simulation models to ensure 
> >that they faithfully represent the algorithms before we can 
> confidently 
> >use them as decision tools.
> >
> Right. It is easy to make a given method look bad by not 
> implementing it in the best way, e.g., using the wrong 
> parameters.  Also, it is important to compare the methods in 
> larger networks (e.g., 100 nodes or more), since scalability 
> is clearly a desirable attribute.

We are planning to make a new code and documentation release of the
GTNetS simulator, aiming for next week.  It will contain the following:
- a simplified wireless MAC model, to improve scalability
- porting everything forward to the recent quagga 0.98 release
- code will be distributed both as a simulator and as a patch against
0.98 (for easier implementation compiling)
- some validation examples of Cisco's overlapping relays in action
- some more test results

After that point in time, we plan to develop extensions to model
Richard's algorithms, and start to do some comparative studies.

I think that our simulator scalability will likely top out at about 50
mobile nodes.  Therefore, other techniques that do not involve modeling
of the full quagga implementation might be desirable for focused studies
of e.g., the RNS selection technique in isolation in larger graphs.  I
think that Richard has been conducting simulations along these lines
based on random graph generation.

Tom

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Richard Ogier <[email-masked]>
Date: Fri, 11 Feb 2005 09:33:38 -0800

>based on random graph generation.

Yes. I am also working on ns-2 simulations with mobile nodes. This
will allow measuring things such as the number of new adjacencies
per second. I also plan to work with GTNetS, to experiment with
different options and variations of my solution.

There will be a few more changes to my draft that were not included
in the tentative version I sent earlier. One important change, for
the Essential CDS algorithm, is that not all neighbors of a DR will
be required to be dependent/adjacent. The adjacent neighbors will be
the neighbor j that maximizes (RtrPri, RID) and all other neighbors
that cannot be reached from node j via neighbors that have a
larger value of (RtrPri, RID) than the router running the algorithm.

The idea is that the DRs should ideally form a tree, with only n-1
adjacencies, which is the case in legacy OSPF. It won't actually
be a tree, because each router uses only 2-hop neighbor information,
so there will typically be more than n-1 adjacencies, but it makes
sense to minimize the number of adjacencies.

In addition, I will describe the Suurballe-Tarjan algorithm in detail,
since I think this is important for minimizing the number of BDRs.

Richard