Subject: Re: [Ospf-manet] URL for MPR-extension software

From: Richard Ogier <[email-masked]>
Date: Mon, 11 Dec 2006 15:19:33 -0800

Emmanuel Baccelli wrote:

> Hi Acee,
> here is a link to the source code http://ndquan.free.fr/gtnets.tar.bz2
> I must have missed Tom's post in the usual after-IETF email avalanche, 
> sorry about that ;)
> Emmanuel

Emmanuel,

I looked at your code.  It looks like all you did was modify Cisco's
Overlapping Relay (OR) code to generate LSAs that include only MPRs
and MPR selectors.

So, your GTNetS implementation is essentially just a modification
or extension of Cisco's OR solution.  In particular, you have not
implemented adjacency reduction based on MPRs, which is needed
in order to compare your solution to the MDR and OR/SP
solutions with adjacency reduction.
As Boeing has shown, both adjacency reduction and LSA reduction
are needed to achieve scalability to 100 or more nodes.
Recall the 100-node example that would have 2384 adjacencies
without adjacency reduction:
http://www3.ietf.org/proceedings/05mar/slides/ospf-5/sld17.htm

When do you plan to release code that implements adjacency
reduction based on MPRs, as described in your draft?

Since your GTNetS implementation is simply an extension of
Cisco's OR implementation, this makes me think that a separate
draft is not needed, i.e., that Cisco's OR draft and INRIA's
draft can be combined into a single draft.
Can you give any reason why this is not possible?

In any case, INRIA still needs to provide GTNetS code that
implements their solution (including adjacency reduction)
so that it can be compared to the other proposals.
Without such a comparison, it is possible (and I think likely)
that INRIA's solution will generate more than 10 times as
much overhead as MDR in a dense 100-node network, possibly
consuming all the network bandwidth.
The burden of proof is on INRIA.  Unless they can provide
evidence that their solution can support networks that are
roughly as large as those supportable by MDR, then I don't
think there is justification for accepting their draft as an
experimental WG document.

I think we should set a deadline to share current GTNetS code
before the next IETF meeting.  I plan to release updated GTnetS
for MDR in mid February.  This will be able to support more
than 100 nodes, using min-cost LSAs.  I hope that INRIA will also
release code that includes adjacency reduction.

Richard

P.S. Regarding terminology.  The term "topology reduction",
similar to "topology control", means that the actual network
topology is limited, i.e., the set of bidirectional neighbors,
or perhaps the set of adjacent neighbors.
But if you are only reducing the set of neighbors that are
advertised in LSAs, you are not reducing the topology, but
are reducing the *advertised* topology.  Therefore, I prefer to
call this LSA reduction.  Put another way, "topology reduction"
is ambiguous because it can refer to the topology defined by
bidirectional links, or by adjacencies, or by advertised links.

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

---

From: Emmanuel Baccelli <[email-masked]>
Date: Wed, 13 Dec 2006 10:09:53 +0100

Richard,

We do think that our draft provides a standard way to get topology 
reduction, which is indeed present in none of the other drafts.
We showed during our last presentation at the IETF that topology 
reduction is at least as effective as adjacency reduction, if not more. 
This is the point that was made, based on the results we published.

The comparison of importance between topology reduction and adjacency 
reduction can be explained easily. Basically, without reductions:

- Each time a link comes up: local synchronization between the new 
neighbors has to take place, and new LSAs have to be flooded globally, 
to the whole OSPF area.

- Each time a link goes down: new LSAs have to be flooded globally, to 
the whole OSPF area.

In other words if we call f the frequency at which links come up, we 
have a synchronization rate equal to f and LSA generation rate equal to 
2f. Each synchronization costs N headers therefore f*N overhead rate. 
Each LSA flooding costs M_r*N/M retransmissions, where M is the average 
neighbor size, M_r is the number of retransmissions per neighborhood (in 
general M_r=4-10). Since the LSA contains the identifiers of M neighbor 
nodes, then the LSA overhead rate is 2f*M_r N which is larger than f*N 
(even if one considers the header cost versus identifier cost).

Obviously, the importance of reducing the occurence and the size of LSAs 
flooded globally is as important (if not more) as the task of reducing 
the cost of synchronizations that are done locally.

The solution specified by the MPR-OSPF draft is indeed simple as you 
pointed out, and we showed it works well. It features topology and 
adjacency reduction in a way compliant with traditional OSPF: routing is 
always done over synchronized links. This is not the case with other 
drafts. In particular, the adjacency reduction proposed in the MDR draft 
assumes the use of non synchronized links, which may create loops and 
out of track routing.

Emmanuel

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 14 Dec 2006 17:04:32 -0800

> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[email-masked]] 
> Sent: Wednesday, December 13, 2006 1:10 AM
> To: [email-masked]
> Subject: Re: [Ospf-manet] URL for MPR-extension software
> 
> Richard,
> 

Emmanuel,
On this point, our results have suggested that adjacency reduction is
complementary to advertised topology reduction, and provides as much or
more overhead reduction depending on the setting.

For instance, Figure 4 of our Milcom 2006 paper shows a comparison of
three variants of Overlapping Relays:
i) full adjacencies, full advertised topology
ii) smart peering adjacencies, full advertised topology
iii) smart peering adjacencies, minimal LSAs (reporting only
adjacencies)

The largest reduction in overhead occurs when moving from case i) to
ii), and additional savings in moving from ii) to iii).

If you would like more details, this is all available on our server at:
http://hipserver.mct.phantomworks.org/ietf/ospf/

> reduction is at least as effective as adjacency reduction, if 

I just reviewed the slides in the proceedings and didn't see any
simulation results pertaining to adjacency reduction.  What are you
referring to?

Thanks,
Tom

---

From: Richard Ogier <[email-masked]>
Date: Mon, 18 Dec 2006 08:44:15 -0800

Emmanuel,

Most of us agree that both LSA reduction and adjacency reduction
are important.  In fact, as show in Boeing's simulations, both
are needed to achieve scalability to 100 or more nodes.

But you avoided my main question:
When do you plan to release code that implements adjacency
reduction based on MPRs, as described in your draft?

It looks like you are focusing on LSA reduction now, and don't
have any results to show for adjacency reduction.
That is understandable, since based on simulations by Boeing
and myself, requiring each router to be synchronized with each
of its MPRs and MPR selectors (and each "synch" node to be
synchronized with all of its neighbors) does not scale well
in dense networks with 100 or more nodes.
On the other hand, the MDR and OR/SP solutions have been shown
to perform well in dense 100-node networks.

As agreed by Acee and Tom Henderson on the OSPF list (see Tom
Henderson's message dated 11/14/2006), you need to make code
that implements your solution available for comparison with
the other proposals.  You have not done this, since the code you
released implements only a small part of your draft (LSA reduction
based on MPRs) and only as an extension to the OR solution.

Since you are focusing on LSA reduction based on "path MPRs",
the rest of my comments will pertain to this.
This is a reasonable method for LSA reduction,
and can be applied both to the OR draft (as you have done
in GTNetS) and to the MDR draft.  I think the term "path MPRs"
is a misnomer, since they are not used for multipoint relaying.
However, they cover all neighbors like MPRs, so I won't quibble
about the term.  (One could just call them "selected advertised
neighbors", regardless of the selection method used.)

My point is that LSA reduction based on "path MPRs" is not (by itself)
a MANET extension of OSPF, but is a valid method that can applied to
the existing MANET extensions (based on ORs and MDRs).

Similarly, "min-cost LSAs", used in the MDR solution, is another
valid method for LSA reduction.  There is no need to argue the
advantages of min-cost LSAs versus path-MPR-based LSAs, since the
MDR solution can use either method for LSA reduction (and I plan to
compare these in GTNetS later).  Each method has its advantages.
For example, one disadvantage of path-MPR-based LSAs is that
they require Hellos to advertise both the link cost to each neighbor
and the *reverse* link cost from each neighbor.  (This not only
requires more overhead, but also causes more delay in responding
to topology changes.)  Path-MPR-based LSAs also have some
advantages, but as I said, we don't need to compare the two
methods at this time.  Also, just as your draft says
"Other algorithms, as well as improvements over this algorithm,
are possible", I am also experimenting with different variations
of min-cost LSAs.

More comments below.

Emmanuel Baccelli wrote:

> reduction is at least as effective as adjacency reduction, if not 
> more. This is the point that was made, based on the results we published.
>
> have a synchronization rate equal to f and LSA generation rate equal 
> to 2f. Each synchronization costs N headers therefore f*N overhead 
> rate. Each LSA flooding costs M_r*N/M retransmissions, where M is the 
> average neighbor size, M_r is the number of retransmissions per 
> neighborhood (in general M_r=4-10). Since the LSA contains the 
> identifiers of M neighbor nodes, then the LSA overhead rate is 2f*M_r 
> N which is larger than f*N (even if one considers the header cost 
> versus identifier cost).

In OSPF, "retransmission" has a particular meaning, but I don't
think you are using this term in the OSPF sense.
Maybe M_r is the average number of MPRs per router, or
the number of neighbors that forward a given LSA?

Also, you are not considering the fact that LSAs must be retransmitted
over adjacencies (but not over non-adjacencies) when an Ack
is not received.  This can create a lot of overhead if adjacency
reduction is not used.

>
>
> Obviously, the importance of reducing the occurence and the size of 
> LSAs flooded globally is as important (if not more) as the task of 
> reducing the cost of synchronizations that are done locally.

Anyway, we agree that both LSA reduction and adjacency reduction are 
important.

> adjacency reduction in a way compliant with traditional OSPF: routing 
> is always done over synchronized links. This is not the case with 
> other drafts. In particular, the adjacency reduction proposed in the 
> MDR draft assumes the use of non synchronized links, which may create 
> loops and out of track routing.

You stated before that "routing is always done over synchronized links",
which led to people pointing out your error, then you agreed that the
first hop of a path might not be synchronized.
(See posts dated 2/27/2006.)
It was also pointed out that requiring all hops (except the first)
to be synchronized may result in a lot of synchronization overhead.

Actually, the fact that the first hop of a path may not be synchronized
concerns me.  In fact, the first hop may be completely out of sync
due to a recent network partition, which can cause routing loops.
This is not the case with MDR or with OR/SP, since all links of
a path are required to be "routable", which is an indirect
synchronization requirement.  It seems to me that your MPR solution
should use the concept of "routable" neighbors for the first hop
of a route, to ensure it is not seriously out of sync.

Richard

>>> I must have missed Tom's post in the usual after-IETF email 
>>> avalanche, sorry about that ;)
>>> Emmanuel
>>
>>
>> Emmanuel,
>>