Subject: [Ospf-manet] [Fwd: RE: [Ospf-wireless-design] Design team outbrief (draft slides) posted]

From: Richard Ogier <[email-masked]>
Date: Mon, 23 Jan 2006 08:47:56 -0800

Philippe Jacquet wrote:

> Dear Richard,
>
> I am sure that there are very good reasons why OSPF needs that 
> advertized links be synchronized. If you don't do so then this will be 
> a strong exception to the fact that wired OSPF should not be affected 
> by the wireless extension, since wired nodes would receive 
> non-synchronized link advertizements. 

Philippe,

I will respond to your note by referring you to a post by Phil Spagnolo on
November 7 (shown below), in which he points out that OSPF allows 
routing over
non-adjacent links in a broadcast network. These links are not directly 
synchronized,
but may be considered to be *indirectly* synchronized.
OSPF-MDR generalizes this to multi-hop networks.

> By the way, we have shown that MPR links will generate a number of 
> synchronizations that is similar to your bi-connected CDS, and in 
> theory not more than two or three times a minimal tree CDS

I recall that the factor is about three for 100 nodes.
For 100 nodes or more, database synchronization becomes a major contributor
to overhead (when partial-topology LSAs are used), so three times as many
adjacencies is not good. But it is worse than that, because the rate of
new adjacencies is more important than the average number of adjacencies.
(This fact has been mentioned several times, but you have not addressed it.)

Richard

-------- Forwarded Message --------
Subject: RE: [Ospf-wireless-design] Design team outbrief (draft slides) 
posted
Date: Mon, 7 Nov 2005 12:58:28 -0800
From: "Spagnolo, Phillip A" <[email-masked]>
To: "Emmanuel Baccelli" <[email-masked]>, 
<[email-masked]>

Emmanuel,

One of the benefits to OSPF-MDR is exactly what you point out.  OSPF-MDR
is not derived from the point-to-multipoint interface only (which does
not route over non-adjacent links), but it is also derived from the
broadcast interface (which routes over non-adjacent links).  

For example, picture a broadcast network with nodes 1 to 5.  Node 1 is
the DR and node 2 is the BDR.  Node 3 wants to send a packet to node 5.
Node 3 does not send to node 1 and then to node 5.  Node 3 sends
directly to node 5.  Thus, it is routing over a non-adjacent link
because node 3 and 5 are adjacent to the DR.

The same is true with OSPF-MDR as long as a node is adjacent to the MDR
backbone then it can route to other nodes adjacent to the MDR backbone.

I find this as part of the beauty of the design.

Sincerely,
Phil

> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[email-masked]] 
> Sent: Monday, November 07, 2005 9:45 AM
> To: [email-masked]
> Subject: Re: [Ospf-wireless-design] Design team outbrief 
> (draft slides) posted
> 
> 
> I think there is something rather confusing in the latest 
> discussions: 
> the use of the term adjacency, especially when compared to its 
> traditional meaning in OSPF. For example, some simulation 
> results tend 
> to show that the MDR approach features a reduced number of 
> adjacencies 
> without featuring any route stretching -- if "min-hop" LSAs a used.  
> However, this supposes that routing is not only done over adjacencies 
> (indeed, if routing was only done over adjacencies, the MDR approach 
> leads to more than 50% route stretching in most cases). This is thus 
> very confusing, since in traditional OSPF routing is supposed 
> to happen 
> only over adjacencies. So there is here at least a vocabulary issue, 
> that needs to be clarified in my opinion.
> 
> Emmanuel
> 
> 
> Richard Ogier wrote:
> 
> >> Emmanuel Baccelli stated that MPR flooding offers better 
> properties 
> >> than CDS flooding, with at least as good topology reduction 
> >> capabilities, and better routing stretch performance
> >
> >
> > After further consideration, I partly agree with the above statement
> > depending on how it is interpreted.
> > The part about "better route stretch performance" is true if we are
> > talking only about *flooding* and not *routing* (since routing can
> > occur along non-adjacencies).  Min-hop routing can be 
> achieved either
> > with MPRs or with the min-cost LSAs described in the MDR draft.
> >
> > The part about "good topology reduction capabilities" depends on how
> > adjacencies are defined. (By topology reduction I am talking about
> > adjacencies, keeping in mind that LSAs can also include non-adjacent
> > neighbors.) In our simulations, Phil and I showed that this
> > is certainly not true if each node forms an adjacency with each of
> > its MPRs and MPR selectors, and Emmanuel has agreed with this:
> >
> >> On the other hand using
> >> MPR/MPRselector adjacencies does yield more adjacencies,
> >> but no route stretching whatsoever.
> >
> >
> >
> > If adjacencies are defined in another way, then the method needs
> > to be specified. One possible way (which I plan to investigate by
> > modifying OSPF-MDR) is to select the CDS/MDRs by pruning MPRs
> > and then defining adjacencies as in the MDR draft, but Emmanuel
> > did not specify such a method.
> >
> > Richard
> >
> >
> >
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
> >
> 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> 

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

-- 
Internal Virus Database is out-of-date.
Checked by AVG Anti-Virus.
Version: 7.0.344 / Virus Database: 267.12.4/146 - Release Date: 10/21/2005

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

---

From: Philippe Jacquet <[email-masked]>
Date: Thu, 26 Jan 2006 10:38:20 +0100

Dear Richard,

Undirect synchronization and direct synchronization are not equivalent. 
Direct synchronization is a certificate that the routers are well 
synchronized when they advertise their common link. This ensures to 
remote nodes that routing on this synchronized link will be ultimately 
loop free. If wireless OSPF advertizes links that are not synchronized  
or are not to be used for routing, then this extension is not really 
needed, a simple gateway between OSPF and a MANET would suffice.

The number of advertized links is somewhat equivalent with  MPR and 
(bi-connected) MDR. The minimum is tree (uni-connected) adjacencies 
which is (n-1) links, around the third in adjacency number but with a 
large stretch factor.

The following table shows the simulation:

nodes number, MPR links, MDR links, minimum tree adjacencies

  10         10.50           11.70               9

20         32.72           37.80               19

30         57.56           65.80               29

40         84.14           96.70               39

50       114.56           129.80             49

60       143.88           169.00             59

70       178.64           196.30             69

80       211.04           238.20             79

90       241.80           276.10             89

100     273.90           306.20             99

 Best regards,

Philippe

Richard Ogier wrote:

>> advertized links be synchronized. If you don't do so then this will 
>> be a strong exception to the fact that wired OSPF should not be 
>> affected by the wireless extension, since wired nodes would receive 
> non-adjacent links in a broadcast network. These links are not 
> directly synchronized,
> Subject: RE: [Ospf-wireless-design] Design team outbrief (draft 
> slides) posted
>> From: Emmanuel Baccelli [mailto:[email-masked]] Sent: 
>> Monday, November 07, 2005 9:45 AM
>> Subject: Re: [Ospf-wireless-design] Design team outbrief (draft 
>> slides) posted
>>
>>
>> discussions: the use of the term adjacency, especially when compared 
>> to its traditional meaning in OSPF. For example, some simulation 
>> results tend to show that the MDR approach features a reduced number 
>> of adjacencies without featuring any route stretching -- if "min-hop" 
>> LSAs a used.  However, this supposes that routing is not only done 
>> over adjacencies (indeed, if routing was only done over adjacencies, 
>> the MDR approach leads to more than 50% route stretching in most 
>> cases). This is thus very confusing, since in traditional OSPF 
>> routing is supposed to happen only over adjacencies. So there is here 
>> at least a vocabulary issue, that needs to be clarified in my opinion.
>>
>> Emmanuel
>>
>>
>> Richard Ogier wrote:
>>
>> properties >> than CDS flooding, with at least as good topology 
>> reduction >> capabilities, and better routing stretch performance
>> >
>> >
>> > occur along non-adjacencies).  Min-hop routing can be achieved either

---

From: Richard Ogier <[email-masked]>
Date: Tue, 31 Jan 2006 14:39:09 -0800

Philippe,

You are comparing only the average number of adjacencies, not the rate at
which new adjacencies are formed (as I have mentioned before).
The rate of new adjacencies is very important because OSPF performs
database exchange (synchronization) when forming a new adjacency.
My simulations show that even if the number of MPR adjacencies is about
the same as the number of biconnected MDR adjacencies, the rate of
new MPR adjacencies is much larger than the rate of new MDR adjacencies.
The problem is that MPRs have to change more frequently than MDRs in order
to maintain the stretch factor of 1 (something that is not needed if we
allow indirectly synchronized neighbors to be included in LSAs).
These results depend on how MPRs are selected, e.g., whether they are
selected persistently.  Selecting MPRs persistently can reduce the rate
of new adjacencies, but will increase the number of MPRs.
Also, if you never tear down an adjacency (even if the link is no longer 
an MPR
link), this helps reduce the rate of new adjacencies, but increases the 
average
number of adjacencies.  I am wondering why you have not presented any 
results
for the *rate* of new adjacencies (unless it is because those results do not
favor MPRs).

Also, unlike biconnected MDR adjacencies, MPRs do not guarantee that the
adjacency subgraph is biconnected.  Backup MPRs could be added to ensure
this, but would increase the number of adjacencies.

Richard

Philippe Jacquet wrote:

> Dear Richard,
>
>
> Undirect synchronization and direct synchronization are not 
> equivalent. Direct synchronization is a certificate that the routers 
> are well synchronized when they advertise their common link. This 
> ensures to remote nodes that routing on this synchronized link will be 
> ultimately loop free. If wireless OSPF advertizes links that are not 
> synchronized  or are not to be used for routing, then this extension 
> is not really needed, a simple gateway between OSPF and a MANET would 
> suffice.
>
>> broadcast interface (which routes over non-adjacent links). For 
>> example, picture a broadcast network with nodes 1 to 5.  Node 1 is
>>> of adjacencies without featuring any route stretching -- if 
>>> "min-hop" LSAs a used.  However, this supposes that routing is not 
>>> only done over adjacencies (indeed, if routing was only done over 
>>> adjacencies, the MDR approach leads to more than 50% route 
>>> stretching in most cases). This is thus very confusing, since in 
>>> traditional OSPF routing is supposed to happen only over 
>>> adjacencies. So there is here at least a vocabulary issue, that 
>>> needs to be clarified in my opinion.
>>>
>>> Emmanuel
>>>
>>>
>>> Richard Ogier wrote:
>>>

---

From: Russ White <[email-masked]>
Date: Tue, 31 Jan 2006 21:08:04 -0500

> which new adjacencies are formed (as I have mentioned before).

See my other email--I don't agree that think it's always a good thing to 
simply cut down adjacencies in mobile environments, no matter how much 
efficiency you gain by doing so.

> database exchange (synchronization) when forming a new adjacency.

Perhaps we should address this issue in some way, rather than degrading 
network stability by reducing adjacencies? There are always more ways to 
solve a problem than the immediately obvious one.

Not that I have any specific suggestions, but I think it's unfruitful to 
assume that adjacency reduction is "the" answer to the problem, without 
considering the tradeoffs.

:-)

Russ

- -- 
[email-masked] CCIE <>< Grace Alone