Subject: [Ospf-wireless-design] notes from our recent IETF meeting

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 12 Nov 2004 08:42:40 -0800

Ad-hoc meeting of the OSPF MANET Design Team

Tuesday Nov 9, 2004

minutes by Tom Henderson

Attendees:
Abhay Roy
Delia Kecskemeti
Emmanuel Bacceli (filling in for Thomas Clausen)
Joe Macker
Acee Lindem
Rohit Dube
Tom Henderson

Acee expressed that he used to favor a monolithic design team
document but that he is starting to favor the idea of a base
"MANET interface" draft that contains the core (flooding)
behavior, and possible extensions in separate documents.  There
was no opposition expressed to that approach.

Joe mentioned the need to use better terminology.  "Wireless"
has problems because people already run OSPF over wireless links
and don't understand the need.  "Mesh" was suggested but it
was felt that this term typically describes static nodes, although
"mobile mesh" might be better and was an original term for
MANET.  "MANET" seems closest to what we are defining, although
the applicability of what we are doing does extend beyond ad hoc 
networks.  We decided to use MANET and define the scope and 
applicability of the term in this work effort.  To that end, 
it was suggested to agree on some standard terminology.

Another point on terminology-- Joe clarified at the meeting
that the term "source-dependent" was not referring to the
original LSA source but instead the previous transmission--
if we don't take steps to make that clear, it might confuse
people.

Rohit suggested that we might consider some kind of requirements
and terminology document.  Tom suggested that maybe we could
start with these as initial portions of the basic document,
and move them to a separate document if it gets too unwieldy.

Tom expressed his near term plan to try to resolve the basic
flooding design before the March IETF.  In particular, the two
most promising variants under consideration are an MPR-based
approach (based on Cisco's draft) and a SI-CDS approach
(based on Tao Lin's draft).  Boeing plans to distribute,
within the design team, a discrete-event network simulator 
for the purpose of doing some quantitative evaluation of
proposals.  More information on this topic will be distributed
to the design team list.

Tom also said that he would work with a goal of having 
a draft to send to the WG for the March IETF meeting.  The
draft should constitute the base "MANET interface" described
above.  Extensions beyond the base document scope (flooding
optimizations) could be considered as a second priority. 

Joe and Acee asked which algorithms are considered and why?
Tom replied that Boeing was implementing two specific algorihms
that met the requirements of a distributed
algorithm operating with local information:  use of MPRs
with acknowledgments (an example of which is Cisco's 
proposed Overlapping Relays) and source-independent CDS
(an example of which is the algorithm described in 
Tao Lin's papers from Virginia Tech).  In the absence
of other algorithms suggested, we will proceed with evaluating 
both of those specific algorithms.  Are there better ones
to consider?  

There were two comments on source-independent and source-
dependent general approaches:
i) Joe mentioned that source-independent approaches might
have an implementation virtue that they don't require looking
at previous hop info, which may or may not be a difficult
piece of information to obtain at the routing layer depending
on the implementation.
ii) It was previously expressed, by Richard Ogier and then
Tom in his recent design team draft, that SI-CDS might
have a virtue in the OSPF environment that a solution that
elected a few "special nodes" might be more in line with
OSPF's design regarding database synchronization issues
(i.e., like the designated router approach).
Emmanuel (echoing a point made by Joe on the list) mentioned 
that we do not necessarily have to use the same special relay 
nodes used for flooding to perform other tasks like database 
synchronization.  The flooding could be independent or 
decoupled from these other nodes used for other functions.

Acee-- we might be able to have two levels of adjacency (adjacency
for database synchronization, and perhaps others such as ability
to use a "link" between them).  We do things like this for 
Graceful Restart already.  The danger here is that we can introduce
a new level of transients.

Joe:  We've explored some of these different notions of adjacency,
although we found that they tend to help more in unreliable
flooding.

Acee:  There are three things to decide:
i) topology information to flood (whether full or partial)
ii) what router establishes what adjacencies with others
iii) flooding (don't have to flood everyone's LSA)

Abhay:  It may be possible to reduce the number of adjacencies
formed-- we've done some experiments on this topic.

Acee:  A question-- does everyone need to be a router?

Joe:  No, only some nodes need to agree to forward packets.
Some nodes could refuse.  Some nodes could agree to forward
only as a last resort.  We have protocol mechanisms for this
in the MANET protocols.

Tom indicated that he and Acee had agreed to two more members for 
the design team that had indicated experience in this problem
space and a desire to participate.  The first, Delia Kecskemeti
(WindRiver) is implementing OSPFv3.  The second, David Green 
(SRI) has experience in conducting larger-scale MANET experiments.  
Views were expressed that we should not expand the design team 
too much more.  Joe and Abhay suggested that we might also include 
the author of the SI-CDS proposal (Tao Lin) on discussions 
relating to his algorithm-- he doesn't necessarily need to be on
the design team.  Acee said that he would close down the lurkers 
that had accidentally been able to subscribe to the design 
team list.

Note that Padma Pillay-Esnault is now at Cisco and reachable
at [email-masked].

(meeting adjourned)

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 18 Nov 2004 15:51:29 -0800

I was not able to attend the IETF meeting this time, but please see my 
comments below.

Henderson, Thomas R wrote:

> applicability of the term in this work effort.  To that end, it was 
> suggested to agree on some standard terminology.
>
Good point. When talking about a local decision, maybe 
"previous-hop-dependent" is a better term. But if a 
previous-hop-dependent flooding protocol is used, then the resulting set 
of nodes that transmit a given flooded packet (which is a CDS) is also 
source-dependent (i.e., depends on the originator).

> within the design team, a discrete-event network simulator for the 
> purpose of doing some quantitative evaluation of
Perhaps a better reference for relevant CDS algorithms is the following, 
which also describes a few (not necessarily new) CDS algorithms that do 
not require computing MPRs:

  C. Adjih, P. Jacquet, and L. Viennot. "Computing connected
  dominated sets with multipoint relays", INRIA research
  report No. 4597, October 2002.

I assume you are talking about Tao Lin's paper, reference [9] of
http://www.ietf.org/internet-drafts/draft-spagnolo-manet-ospf-design-00.txt
It is not clear from the description in the paper whether the CDS is 
source-independent (in the description, the choice seems to depend on 
the "sender node"). If it is indeed source-indepenent, then it appears 
to be the same as one of the CDS algorithms in the INRIA report, except 
that maximizing node degree is used as an additional objective (which I 
found not to work well, since it favors nodes that are close to the 
center of a given cluster, and also results in a less stable CDS). A 
similar CDS algorithm can be found in the following paper:  J. Wu and H. 
Li. "A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks", 
Telecommunication Systems, Vol. 18, pp. 31-36, 2001.

I plan to describe and present simulation results for a few CDS 
algorithms based on 2-hop neighbor information, including two from the 
above INRIA report and some improved variations.

Another issue is whether existing CDS nodes should remain in the CDS 
whenever possible (to maximize stability), just as a DR in OSPF remains 
a DR whenever possible. This is especially important if adjacencies are 
formed only between CDS nodes and their neighbors (so that a new CDS 
node must form adjacencies with all of its neighbors).

>
> Tom also said that he would work with a goal of having a draft to send 
> to the WG for the March IETF meeting.  The
> with acknowledgments (an example of which is Cisco's proposed 
> Overlapping Relays) and source-independent CDS
> (an example of which is the algorithm described in Tao Lin's papers 
> from Virginia Tech).  In the absence
> of other algorithms suggested, we will proceed with evaluating both of 
> those specific algorithms.  Are there better ones
> to consider? 

As I mentioned above, I will be suggesting (by January) a few more CDS 
algorithms that can be considered.

> piece of information to obtain at the routing layer depending
There are some other advantages of source-independent flooding, such as 
faster recovery from link failures, and avoiding the need to report MPR 
selection to neighbors.

> Emmanuel (echoing a point made by Joe on the list) mentioned that we 
> do not necessarily have to use the same special relay nodes used for 
> flooding to perform other tasks like database synchronization.  The 
> flooding could be independent or decoupled from these other nodes used 
> for other functions.
>
Database synchronization *could* be independent of the CDS/MPR 
selection.  However, it might be best to make them dependent, as in OSPF 
(where the DR is the flooding relay in a broadcast network, and an 
adjacency is formed between the DR and each of its neighbors). In the 
wireless extension, it might be best to form an adjacency only between 
each CDS node and its neighbors.

> to use a "link" between them).  We do things like this for Graceful 
> Restart already.  The danger here is that we can introduce
Perhaps you (Abhay) are talking about forming adjacencies only between 
MPRs and their selectors? I am not sure this guarantees that all nodes 
will be synchronized if the algorithm converges after the last topology 
change.  (Let me know if you mean something else.)  If a CDS is used, 
and an adjacency is formed between each CDS node and its neighbors, then 
all nodes are synchronized (maybe this is another advantage of using a CDS).

However, if MPRs are used, I have indicated in my draft an efficient way 
to achieve synchronization between all nodes:  Each MPR node is 
responsible for flooding a subset of the LSAs (called its "reported 
originator set") , and for synchronizing with its neighbors with respect 
to this subset of LSAs.

Regarding partial topology if a (source-independent) CDS is used, it is 
possible to flood only links that are adjacent to CDS nodes, i.e., only 
CDS nodes would need to originate LSAs. My simulations show that, if the 
right CDS algorithm is used, the resulting path between two nodes is 
only slightly longer than the min-hop path. (I will include this result 
in my upcoming draft.)

Regards,
Richard

> Tom indicated that he and Acee had agreed to two more members for the 
> design team that had indicated experience in this problem
> (WindRiver) is implementing OSPFv3.  The second, David Green (SRI) has 
> experience in conducting larger-scale MANET experiments.  Views were 
> expressed that we should not expand the design team too much more.  
> Joe and Abhay suggested that we might also include the author of the 
> SI-CDS proposal (Tao Lin) on discussions relating to his algorithm-- 
> he doesn't necessarily need to be on
> the design team.  Acee said that he would close down the lurkers that 
> had accidentally been able to subscribe to the design team list.
>
> at [email-masked] .