Subject: [Ospf-wireless-design] Some new results for draft-ogier-manet-ospf-extension-03

From: Richard Ogier <[email-masked]>
Date: Sun, 13 Mar 2005 10:34:10 -0800

All,

One of the concerns/doubts about my CDS solution that was voiced
at the OSPF meeting was that a DR has too many dependent/adjacent
neighbors. So I ran a simulation to determine the average number of
new adjacencies that are formed between a new DR and its neighbors.
(I assume that the concern is that it may take a long time for
a new DR to perform database exchange with all of its new adjacent
neighbors.)

Since the results may surprise some of you, let me first explain the
factors that tend to reduce this number. A new DR was probably
already a BDR (since I am using the persistent version of the
Essential CDS algorithm) and therefore already had several adjacent
neighbors.  Also, the majority of nodes are non-DR/BDR, which keep
their adjacencies with their old DR and BDR whenever possible (and
therefore would not form an adjacency with the new DR unless they
lost their old DR or BDR).

I ran the same scenario that I used in my slides: 100 nodes,
radius = 0.5. This is a dense scenario with an average degree of 47.7.
(So the average number of new adjacencies for a new DR could
potentially be as large as 47.7, which might be the reason for
concern.) The average number of new adjacencies for a new DR in
this scenario turns out to be 2.12.
(If the number were much larger, then the problem could be fixed
by using the proposed enhancement which allows DD packets to be
multicast, but that enhancement might not be necessary in light of
this result.)

Since Joe thought the CDS solution would perform worse when
there are node failures and new nodes, I ran the simulation
again with the following change: every 5 seconds, a node was
randomly selected and removed, and a new node was added at
a random position in the square. With this change, the average
number of new adjacencies for a new DR decreased to 1.95.
(The number of new DRs per second increased slightly.)

The reason for this reduction is that, because DRs are persistent,
a new node is unlikely to become a DR (since it is has low priority
for being selected), and in those rare cases that it becomes a DR,
it will likely have fewer Dependent Neighbors.
Of course, if a solution is used in which all neighbors are adjacent,
then a new node would result in 47.7 new adjacencies on average.
All statistics obtained for these two cases are given at the
end of this message.

Does this alleviate some of your concerns/doubts (assuming the
results are correct)? I will assume it does unless I hear
otherwise, so please let me know if it does not.
If so, then what concerns still remain?
Or are we satisfied to wait for simulation results?

I welcome *valid* concerns/doubts regarding my solution, but
I prefer concerns that are supported either by a specific
example, by simulations, or by analysis.
Otherwise, the concerns are just guesses.

The thing that pleases me most about the CDS solution (besides
its efficiency and robustness), is how it generalizes OSPF's use
of DRs and BDRs, in terms of flooding and adjacencies. For example,
I think it is great that each non-DR/BDR still uses the DR and BDR
fields of its Hellos in the same way - to indicate the DR and BDR
(or 2nd DR) with which it is adjacent.

Richard

Here are all the statistics gathered for the above scenarios
(first without the node failure model).

Essential CDS algorithm, persistent version
N = 100
conn_radius = 0.500000
num seconds = 500
Avg num DRs = 7.552000
Avg num BDRs = 5.330000
Avg num adj all = 202.012000
Avg num edges = 2384.288000
Ratio num edges / num adj = 11.802705
Avg num new adj / sec = 19.056000
Avg num new edges / sec = 138.252000
Avg num new DRs / sec = 0.678000
Avg num new adj per DR  = 2.117994
Ratio new edges / new adj = 7.255038
Avg diameter = 3.008000
Avg degree = 47.685760
Avg CDS diameter = 4.236000
Max diameter = 4, Max CDS diameter = 7
Avg hops = 1.561924, Avg CDS hops = 1.710640 Ratio = 1.095213

Results when a random node was removed and
a new node was added every 5 seconds:

N = 100
conn_radius = 0.500000
num seconds = 500
Avg num DRs = 7.672000
Avg num BDRs = 5.354000
Avg num adj all = 202.294000
Avg num edges = 2388.900000
Ratio num edges / num adj = 11.809050
Avg num new adj / sec = 20.484000
Avg num new edges / sec = 146.894000
Avg num new DRs / sec = 0.710000
Avg num new adj per DR  = 1.946479
Ratio new edges / new adj = 7.171158
Avg diameter = 3.010000
Avg degree = 47.778000
Avg CDS diameter = 4.224000
Max diameter = 4, Max CDS diameter = 6
Avg hops = 1.560501, Avg CDS hops = 1.707005 Ratio = 1.093883

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

---

From: "Joe Macker" <[email-masked]>
Date: Mon, 14 Mar 2005 10:32:17 -0500

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On 
> Behalf Of Richard Ogier
> Sent: Sunday, March 13, 2005 1:34 PM
> To: [email-masked]
> Subject: [Ospf-wireless-design] Some new results 
> fordraft-ogier-manet-ospf-extension-03
> 
> All,
> 
> 
> randomly selected and removed, and a new node was added at a 
> random position in the square. With this change, the average 
> The reason for this reduction is that, because DRs are 
> persistent, a new node is unlikely to become a DR (since it 
> is has low priority for being selected), and in those rare 
> cases that it becomes a DR, it will likely have fewer 
> Dependent Neighbors.
> Of course, if a solution is used in which all neighbors are 
> adjacent, then a new node would result in 47.7 new 
> adjacencies on average.
> Does this alleviate some of your concerns/doubts (assuming 
> the results are correct)? I will assume it does unless I hear 

Yes, it does in my case. It makes sense. The persistency in the dense case
is now more clear to me.

> Or are we satisfied to wait for simulation results?

I AM.  

> 
> 
> The thing that pleases me most about the CDS solution 
> (besides its efficiency and robustness), is how it 
> generalizes OSPF's use of DRs and BDRs, in terms of flooding 
> and adjacencies. For example, I think it is great that each 
> non-DR/BDR still uses the DR and BDR fields of its Hellos in 
> the same way - to indicate the DR and BDR (or 2nd DR) with 
> which it is adjacent.

I also thought that was a good feature.

> Essential CDS algorithm, persistent version N = 100 
> conn_radius = 0.500000 num seconds = 500 Avg num DRs = 
> 7.552000 Avg num BDRs = 5.330000 Avg num adj all = 202.012000 
> Avg num edges = 2384.288000 Ratio num edges / num adj = 
> 11.802705 Avg num new adj / sec = 19.056000 Avg num new edges 
> / sec = 138.252000 Avg num new DRs / sec = 0.678000 Avg num 
> new adj per DR  = 2.117994 Ratio new edges / new adj = 
> 7.255038 Avg diameter = 3.008000 Avg degree = 47.685760 Avg 
> CDS diameter = 4.236000 Max diameter = 4, Max CDS diameter = 
> 7 Avg hops = 1.561924, Avg CDS hops = 1.710640 Ratio = 1.095213
> 
> Results when a random node was removed and a new node was 
> added every 5 seconds:
> 
> N = 100
> conn_radius = 0.500000
> num seconds = 500
> Avg num DRs = 7.672000
> Avg num BDRs = 5.354000

---

From: Richard Ogier <[email-masked]>
Date: Mon, 14 Mar 2005 07:54:13 -0800

Joe,

Thanks for your positive comments. I know that my
solution still has some weaknesses, such as the time to
recover if two DR/BDRs fail at about the same time,
but I am working on those now, in addition to adding details.

Richard