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

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:

> 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).

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.

>
>
> 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.

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

>
>
> Emmanuel
>
>
>
>
> Richard Ogier a écrit :
>
>> 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
> Ospf-manet@ietf.org
> https://www1.ietf.org/mailman/listinfo/ospf-manet
>
>

_______________________________________________
Ospf-manet mailing list
Ospf-manet@ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-manet