Subject: Re: [manet] New draft: "Routing Loop Issue in Mobile Ad Hoc Networks (MANETs)"

From: Lee Speakman <[email-masked]>
Date: Tue, 02 Jun 2009 11:46:14 +0900

Dear Christopher Dearlove,

thank you for your comments, replies inline...
>> An LLN only occurs on the failure of a unicast data packet to be 
>> forwarded from one node to the next.
>>     
>
> Note that this is not a specification of OLSRv2. OLSRv2 specifies
> that if you have link layer information, you can use it. But it
> doesn't specify anything about whether to use unicast data packets
> or not. Our implementation of OLSR, which uses link layer information
> is not specified as you have it above.
>   
Thank you, perhaps this needs to be further explained and clarified in 
our draft.

> I would like to know if this is simply the work previously presented
> at the IETF. That work was demonstrably flawed - as could be seen
> from the stationary case, and discussions then indicated a poor LLN
> approach.
>   
I know there was some mention of this previously at the IETF but am not 
aware to what was "demonstrably flawed."
I think the LLN approach we used is very effective and our results show 
this.

As an example, it would be more particularly useful in comparison to 
full path metrics where there is greater mobility and the path metric 
approach takes some time to build up and so may not always be accurate.
This LLN approach is simple and is able to respond quickly to changes in 
the network, however, does create transient routing loops. When used 
with a Loop Detection (looping packet detection) technique with an 
action to respond to the loop, it is able to support greater loads and 
packet delivery rate whilst maintaining small end-to-end delay, showing 
potential to be very useful under various conditions.

Thanks for your comments.

Cheers,
  Lee -S-

Lee Speakman, Research Center for Natural Hazard and Disaster Recovery, 
Niigata, Japan

---

From: Lee Speakman <[email-masked]>
Date: Tue, 02 Jun 2009 19:44:14 +0900

Dear Philippe,

We have done simulations in which we issue a new "Instant Hello" on the 
loss of link, however, even though it is beneficial in some ways and 
solves ~10% of the loops under certain conditions, we find that it 
increases the overhead to an extent that it roughly counters the gain 
from dissolving ~10% of the loops. We find that for ~90% of the loops 
the loop comes about from an incoherent perception of the network 
between adjacent nodes through their Topology Sets and so cannot be 
fixes with an Instant Hello.
The effect of an LLN cutting a link that is unphysical is often to cause 
a change such that a loop appears not only one link away (an adjacent 
link), but also two links or more away from the lost link.

The likelihood of a loop appearing reduces as the node density (and 
link-density) is increased.

We haven't performed the second (a TC with a new MPR selector set number).

Cheers,
Lee -S-

jacquet さんは書きました:
> Seems interesting. I remember that with old RFC 3626 we assumed that a 
> node which detects a link failure, either by LLN or by hello loss, 
> should immediately issue:
> 1. a hello with lost indication
> 2. a TC with a new MPR selector set number since one MPR selector is 
> down.
> A loop could only happen after the loss detection, during the jitter 
> time of notification hellos and/or TC's. Here I don't see how the LLN 
> option could bring a significant distortion.
>
> Philippe
>

---

From: "Teco Boot" <[email-masked]>
Date: Wed, 3 Jun 2009 13:44:23 +0200

Hi,

|jacquet wrote:
|> Seems interesting. I remember that with old RFC 3626 we assumed that a
|> node which detects a link failure, either by LLN or by hello loss,
|> should immediately issue:
|> 1. a hello with lost indication
|> 2. a TC with a new MPR selector set number since one MPR selector is
|> down.

It is a MAY, not a SHOULD.
Hello (RFC3626 page 43):
  -    An additional HELLO message MAY be sent when the MPR set
       changes.
TC (RFC3626 page 45):
   A node MAY transmit additional TC-messages to increase its
   reactiveness to link failures.

We can think of changing it to SHOULD.

|> A loop could only happen after the loss detection, during the jitter
|> time of notification hellos and/or TC's. Here I don't see how the LLN
|> option could bring a significant distortion.

When link metrics are used, the goal is forecasting the 
failure and circumvent problems. This needs smooth increase
of metric values. Not that easy, because we need hysteresis
also. And the question sending TCs immediately or not.

I experienced mail delivery problems on May 29, for mails 
from [Dearlove, Jacquet, Rogge].

Teco.

---

From: Lee Speakman <[email-masked]>
Date: Thu, 04 Jun 2009 10:55:05 +0900

Dear Henning Rogge,

I used Qualnet 4.0 for simulations with an updated nOLSRv2 implementation.

We used a data rate of 2Mbps at 2.4GHz with a two-ray propagation
pathloss model. The other radio model simulation parameters are shown below.

Cheers,
Lee -S-

Henning Rogge さんは書きました:
> Am Dienstag 26 Mai 2009 11:24:50 schrieb Lee Speakman:
>   
>> Dear MANET WG members,
>>
>> we at Niigata University have implemented and tested the OLSRv2 protocol
>> according to a recent draft.
>>
>> The implementation has been put to use in simulation and real world
>> physical nodes.
>>
>> Simulation under various scenarios indicate that the use of LLN (Link
>> Layer Notification) leads to a looping packets becoming a problem in the
>> network.
>>
>> In larger networks where the TTL or Hop Count cannot be kept small, and
>> particularly at higher loads, the problem of looping packets become more
>> significant.
>>     
> I would be interested in the radio model you used for your simulations.
>
> Henning Rogge
>
>   

Qualnet (4.0) config part:

PROPAGATION-CHANNEL-FREQUENCY 2.4e9
PROPAGATION-LIMIT -111.0
PROPAGATION-PATHLOSS-MODEL TWO-RAY
PROPAGATION-SHADOWING-MODEL CONSTANT
PROPAGATION-SHADOWING-MEAN 4.0
PROPAGATION-FADING-MODEL NONE

PHY-MODEL PHY802.11b
PHY-RX-MODEL PHY802.11b

PHY-LISTENABLE-CHANNEL-MASK 1
PHY-LISTENING-CHANNEL-MASK 1

PHY-TEMPERATURE 290
PHY-NOISE-FACTOR 7.0

PHY802.11-AUTO-RATE-FALLBACK NO
PHY802.11-DATA-RATE 2000000
PHY802.11-DATA-RATE-FOR-BROADCAST 2000000

PHY802.11b-TX-POWER--1MBPS 15.0
PHY802.11b-TX-POWER--2MBPS 15.0
PHY802.11b-TX-POWER--6MBPS 15.0
PHY802.11b-TX-POWER-11MBPS 15.0
PHY802.11b-RX-SENSITIVITY--1MBPS -93.0
PHY802.11b-RX-SENSITIVITY--2MBPS -89.0
PHY802.11b-RX-SENSITIVITY--6MBPS -87.0
PHY802.11b-RX-SENSITIVITY-11MBPS -83.0

ANTENNA-GAIN 0.0
ANTENNA-EFFICIENCY 0.8
ANTENNA-MISMATCH-LOSS 0.3
ANTENNA-CABLE-LOSS 0.0
ANTENNA-CONNECTION-LOSS 0.2
ANTENNA-HEIGHT 1.5

ANTENNA-MODEL OMNIDIRECTIONAL

---

From: Henning Rogge <[email-masked]>
Date: Thu, 4 Jun 2009 09:14:07 +0200

> pathloss model. The other radio model simulation parameters are shown
Does you real world testbed support the results of the Qualnet simulations ? I 
ask because simulations with two-ray ground radio propagation and no 
smallscale fading are sometimes not reproducable in real world hardware.

-- 
Henning Rogge

*************************************************
Diplom Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: [email-masked]
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Prof. Dr. rer. nat. Maurus Tacke (komm. Vors.), Prof. Dr.-Ing. 
Joachim Ender (Stellv.)

---

From: jacquet <[email-masked]>
Date: Thu, 04 Jun 2009 15:44:20 +0200

It was a "may" because LLN was very experimental. I remember it is very 
difficult to implement in real networks. It was very unclear if one must 
consider a neighbor off just because of a single data packet failure. 
Sometimes it is more convenient to consider the link on.

Anyhow the underlying idea behind LLN considerations should be that 
instant hello and instant TC should be sent within same timing and not 
be considered as to be transmitted independently.

This said, I still not understand why in this simulation, instant hellos 
(without TC) triggered by hello loss or by LLN lead to so different loop 
situations.

Philippe

Teco Boot a écrit :
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>
>
>

---

From: Lee Speakman <[email-masked]>
Date: Fri, 05 Jun 2009 15:52:13 +0900

> smallscale fading are sometimes not reproducable in real world hardware.
Thanks for the information regarding fading.

We have detected loops occurring in the testbed with our implementation
nOLSRv2 with hop count metric but have not yet compared the nature of
the response (of looping packets) with respect to varying the load.

We observed this by looking at various packet traces from the nodes
which also have a limited collection capability, particularly as loops
occur at higher loads. The testbed isn't yet capable of detecting
looping packets in real time in node so it is hard to confirm everything
we have observed with the same nOLSRv2 code under simulation (Qualnet 4.0).

Regarding the fading in the simulation model, I understand that the
physical model can have an effect on the frame being sent and thus the
success or failure of a broadcast or unicast packet being received by
any particular node, and thus whether an LLN is generated at any
particular moment and whether a link remains or is lost (from successive
non-received Hellos or an LLN in node). But as to my understanding,
fading would only have an effect on the quantity of loops under any
particular environment rather than the fact that they occur or not in
that particular environment.

As far as I can see the reason they occur (or not) would be the
coherence or lack thereof between the perceived topologies of the
network in each of the nodes and the nature in which they select the
next hop from the information available to them at that time. So having
fading may change the quantity of observed loops compared to having no
fading, but I think they would still occur in some quantity if they were
occurring before.

So I can see the physical model may have an effect on this quantity of
loops (if they occur) but not whether they occur or not. I'd very much
like to know your opinion on this.

We will consider fading further in our simulations and see what we get.

We are very grateful for your input.

Thanks,
Lee -S-

---

From: "Teco Boot" <[email-masked]>
Date: Fri, 5 Jun 2009 09:13:44 +0200

I think LLN for declaring a link to a neighbor as dead is a different 
topic as instant hello / instant TC.

LLN (or any other link layer feedback) is used for a better interface
between link layer and network layer. There are mechanisms for
detection of "link-up", "link-down" or "link-status" (data rate, signal
quality etc.).
My test results show clearly that immediate response on link layer
feedback makes the network unstable. Dampening and hysteresis are to
be used.

When a link state change is detected, we have the question what to do
with it. A straightforward approach is accepting this change locally 
(update routing table) and schedule a message for notifying other 
routers. Now we have the question when to send out this message, 
either direct, delayed with jitter or waiting for interval timer. 
During the delay, the routing tables of routers may be out of sync
and routing loops may occur. So an immediate send out would shorten
the interval that routing tables are out of sync. But this has a 
drawback, that the load of the routing protocol becomes bursty, 
also by the fact that the change in topology could affect many 
routers. Moreover, the bust by itself could influence the 
topology. This can result in a sort of melt-down of the MANET. 

It would be nice if we have practical guidance for configuring the
best setting for dampening / hysteresis and instant messages for
fast routing table synchronization while not overloading the MANET.

Philippe, you mentioned instant hellos and instant TCs should be
sent out with same timing (same packet). Is this important?
If so, I think it needs to be specified.

Instant hellos would have local load, so costs are lower related
to instant TCs. But do instant hellos solve the out-of-sync routing
table problem? I can think of a mechanism where info in hello
message is used for updating the topology set, declaring
links from 1-hop neighbors to 2-hop neighbors as dead. Normally,
we need TCs for this. OK, we can use instant TCs with hop-limit 
for this. But originating TCs with hop-limit = 1 is not allowed 
in OLSRv2.

If one comes up with a more fundamental method circumventing loops,
I am all ears!

Teco.

|-----Oorspronkelijk bericht-----
|Van: jacquet [mailto:[email-masked]]
|Verzonden: donderdag 4 juni 2009 15:44
|Aan: Teco Boot
|CC: 'Lee Speakman'; 'mase'; [email-masked]
|Onderwerp: Re: [manet] New draft: "Routing Loop Issue in Mobile Ad Hoc
|Networks (MANETs)"
|
|It was a "may" because LLN was very experimental. I remember it is very
|difficult to implement in real networks. It was very unclear if one must
|consider a neighbor off just because of a single data packet failure.
|Sometimes it is more convenient to consider the link on.
|
|Anyhow the underlying idea behind LLN considerations should be that
|instant hello and instant TC should be sent within same timing and not
|be considered as to be transmitted independently.
|
|This said, I still not understand why in this simulation, instant hellos
|(without TC) triggered by hello loss or by LLN lead to so different loop
|situations.
|
|Philippe
|
|Teco Boot a écrit :
|> Hi,
|>
|> |jacquet wrote:
|> |> Seems interesting. I remember that with old RFC 3626 we assumed
|that a
|> |> node which detects a link failure, either by LLN or by hello loss,
|> |> should immediately issue:
|> |> 1. a hello with lost indication
|> |> 2. a TC with a new MPR selector set number since one MPR selector
|is
|> |> down.
|>
|> It is a MAY, not a SHOULD.
|> Hello (RFC3626 page 43):
|>   -    An additional HELLO message MAY be sent when the MPR set
|>        changes.
|> TC (RFC3626 page 45):
|>    A node MAY transmit additional TC-messages to increase its
|>    reactiveness to link failures.
|>
|> We can think of changing it to SHOULD.
|>
|>
|> |> A loop could only happen after the loss detection, during the
|jitter
|> |> time of notification hellos and/or TC's. Here I don't see how the
|LLN
|> |> option could bring a significant distortion.
|>
|> When link metrics are used, the goal is forecasting the
|> failure and circumvent problems. This needs smooth increase
|> of metric values. Not that easy, because we need hysteresis
|> also. And the question sending TCs immediately or not.
|>
|>
|> I experienced mail delivery problems on May 29, for mails
|> from [Dearlove, Jacquet, Rogge].
|>
|>
|> Teco.
|>
|>
|>
|> _______________________________________________
|> manet mailing list
|> [email-masked]
|> https://www.ietf.org/mailman/listinfo/manet
|>
|>
|>

---

From: Lee Speakman <[email-masked]>
Date: Fri, 05 Jun 2009 18:47:06 +0900

Dear Philippe,

in correction to my previous comment, we have actually performed the 
second - an "Instant TC" both separately and together with "Instant 
Hello" triggered on LLN.

The "Instant Hello" and "Instant TC" was tried both instantly and with a 
fractional delay of the jitter that is used for the periodic control 
packets.

For a variety of simulation environments we couldn't find good results 
from these methods, as the network was more overwhelmed by the broadcast 
packets triggered by the occurring LLNs than it benefited the routing 
mechanism.

The biggest positive effect out of this research was the observation 
that "Instant Hello" was capable of dissolving a fraction (~10%) of the 
routing loops, although any gain being countered by its increased 
overhead as explained earlier.

This is what led to our pursuit of why the majority of the loops 
remained which led us to find that ~90% of the loops are not over a link 
directly adjacent to the node in which the link break occurred and 
therefore cannot be solved by an Hello from that node.

In our simulations, the LLN occurs only after the Link Layer (802.11b) 
has attempted to forward a unicast packet up to 4 or 7 times. If the 
sending Link Layer fails to receive a CTS, it will reattempt 7 times by 
new RTS (ShortRetryLimit) before a L2 notification, else it will 
reattempt to forward 4 times (LongRetryLimit) if it fails to receive an ACK.

We have performed with and without RTS/CTS and with multiple network 
layer retries that are a multiple of this 4 or 7 times, but loops still 
exist, only in differing quantities.

As it is much less likely to find looping packets where the best routes 
are just two or three hops, we aimed to have in our simulations cases 
where there are also longer multihop routes present between a given 
source-destination pair.  With greater separation (and 
multi-hopped-ness) increases the likelihood that a looping packet will 
be observed.

The likelihood of a loop appearing also increases as the load is increased.

Cheers,
   Lee -S-

Lee Speakman さんは書きました:
> Dear Philippe,
>
> We have done simulations in which we issue a new "Instant Hello" on 
> the loss of link, however, even though it is beneficial in some ways 
> and solves ~10% of the loops under certain conditions, we find that it 
> The effect of an LLN cutting a link that is unphysical is often to 
> cause a change such that a loop appears not only one link away (an 
> adjacent link), but also two links or more away from the lost link.
>
> Lee Speakman, Research Center for Natural Hazard and Disaster 
> Recovery, Niigata, Japan
>
>
> jacquet さんは書きました:
>> Seems interesting. I remember that with old RFC 3626 we assumed that 
>> a node which detects a link failure, either by LLN or by hello loss,

---

From: jacquet <[email-masked]>
Date: Fri, 05 Jun 2009 14:24:48 +0200

> for this. But originating TCs with hop-limit = 1 is not allowed 

I guess we should have unlimited TC. As Lee said the loop are not 
necessarily adjacent to the broken link.  If you consider the line

...-1--2--3--4--5--6--7--8--9-...
with a flow from node 1 to node 9.

Assume link 7-8 breaks.

Instant hello will inform node 6 about the breakage of link 7->8. 
Therefore a loop will occur either between node 6 and node 7 or between 
node 5 and node 6, if  the later perform 2-hop topology update after the 
instant hello.  Of course assuming another path exists before node 1 
toward 9.

The TC with TTL=x will bring the breakage information down to node 7-x 
and create a loop there. Thus if x=infinity, there should not be any 
persistent loop in an ideal world.

The TC plays the role of informing about the loss of the link 7->8 to 
the part of the network below node 7, and is more pertinent than the 
instant hello regarding the routing of the flow we consider.

---

From: jacquet <[email-masked]>
Date: Fri, 05 Jun 2009 14:52:58 +0200

But the instant TC should reach the nodes far from the broken link, the 
instant hello not.

I would be surprised that the transmission of a single instant hello and 
of a single instant TC bring any significant increase of overhead, at 
least it should be negligible compared to the loop overhead (data 
packets being repeated 255 times). But maybe the loops congest the 
network and prevent the instant TC or the instant hello to be actually 
received. This is a plausible explanation since you say somewhere that 
the loops also create other link failures, and then other loops.

One remedy would be that at detection of link failure a node just 
cancels the route, then drop packets while sending the new TC, and AFTER 
do new route calculation.

Philippe

Lee Speakman a écrit :
> The "Instant Hello" and "Instant TC" was tried both instantly and with 
> a fractional delay of the jitter that is used for the periodic control 
> packets.
>
> from these methods, as the network was more overwhelmed by the 
> broadcast packets triggered by the occurring LLNs than it benefited 
> the routing mechanism.
>
> that "Instant Hello" was capable of dissolving a fraction (~10%) of 
> the routing loops, although any gain being countered by its increased 
> remained which led us to find that ~90% of the loops are not over a 
> link directly adjacent to the node in which the link break occurred 
> and therefore cannot be solved by an Hello from that node.
>
>
> sending Link Layer fails to receive a CTS, it will reattempt 7 times 
> by new RTS (ShortRetryLimit) before a L2 notification, else it will 
> layer retries that are a multiple of this 4 or 7 times, but loops 
> still exist, only in differing quantities.
>
>
> As it is much less likely to find looping packets where the best 
> routes are just two or three hops, we aimed to have in our simulations 
> cases where there are also longer multihop routes present between a 
> given source-destination pair.  With greater separation (and 
>> and solves ~10% of the loops under certain conditions, we find that 
>> it increases the overhead to an extent that it roughly counters the 
>> gain from dissolving ~10% of the loops. We find that for ~90% of the 
>> loops the loop comes about from an incoherent perception of the 
>> network between adjacent nodes through their Topology Sets and so 
>> cannot be fixes with an Instant Hello.
>>> time of notification hellos and/or TC's. Here I don't see how the 
>>> LLN option could bring a significant distortion.
>>>
>>> Philippe
>>>
>>
>
>
>

---

From: "Teco Boot" <[email-masked]>
Date: Fri, 5 Jun 2009 15:09:12 +0200

|Teco Boot a écrit :
|> Philippe, you mentioned instant hellos and instant TCs should be
|> sent out with same timing (same packet). Is this important?
|> If so, I think it needs to be specified.
|>
|> Instant hellos would have local load, so costs are lower related
|> to instant TCs. But do instant hellos solve the out-of-sync routing
|> table problem? I can think of a mechanism where info in hello
|> message is used for updating the topology set, declaring
|> links from 1-hop neighbors to 2-hop neighbors as dead. Normally,
|> we need TCs for this. OK, we can use instant TCs with hop-limit
|> for this. But originating TCs with hop-limit = 1 is not allowed
|> in OLSRv2.
|>
|
|I guess we should have unlimited TC. As Lee said the loop are not
|necessarily adjacent to the broken link.  If you consider the line
|
|...-1--2--3--4--5--6--7--8--9-...
|with a flow from node 1 to node 9.
|
|Assume link 7-8 breaks.
|
|Instant hello will inform node 6 about the breakage of link 7->8.
|Therefore a loop will occur either between node 6 and node 7 or between
|node 5 and node 6, if  the later perform 2-hop topology update after the
|instant hello.  Of course assuming another path exists before node 1
|toward 9.
|
|The TC with TTL=x will bring the breakage information down to node 7-x
|and create a loop there. Thus if x=infinity, there should not be any
|persistent loop in an ideal world.
|
|The TC plays the role of informing about the loss of the link 7->8 to
|the part of the network below node 7, and is more pertinent than the
|instant hello regarding the routing of the flow we consider.

Yes, this is the explanation of having loops. And also an argument
against the hop-limit feature.

The instant hello is used for triggering a TC on the neighbor nodes
and MPR selection only and doesn't help avoiding loops directly. Correct?
How to explain the 10% loop reduction by instant hellos, reported by
Lee? Due to topology reduction mechanisms, where the node sending
the instant hello was no longer MPR ??? 

My test results on looped packets showed micro-loops, with one router
that detected the dead link. Mainly because I work with a limited
set of routers and the diameter is up to 3 hops.
Topology looks like:
   1_____
   |     \___
   |     ____3  
   2____/

When links to 3 fades away (movement to right, obstacle between 1&2
and 3), the loop may occur. Both 1 and 2 know their link to 3 is 
lost (e.g. signaled in same hello message from 3), but both assume
the path via the other, nearby node is still alive, we have the loop.
TCs (with hop-limit >= 1) solve the loop. We don't need widely
spread TCs for it.

Lee reports network meltdown due to overload of instant TCs. I have 
seen similar behavior in another context. For this reason I say
hysteresis and dampening is essential (a MUST).

Teco.

|
|> If one comes up with a more fundamental method circumventing loops,
|> I am all ears!
|>
|> Teco.
|>
|>

---

From: Elektra <[email-masked]>
Date: Fri, 5 Jun 2009 15:10:38 +0200

Hello all!

I'd dare to state that transient routing loops are normal in Olsr and other 
Link State protocols in a wireless environment with fluctuating link quality as 
long as TCs are communicated via broadcasts. (Using unicasts instead doesn't 
seem like a viable solution).

Since the topology data base has to be synced amongst adjacent nodes via a 
lossy medium to avoid loops (up to 3 hops range I'd say) I have drawn and 
tested the following conclusions when hacking on RFC3626 for the Freifunk 
community mesh network in Berlin together with Tomas Lopatic and others in the 
years 2004 and 2005:

- when we tested RFC3626 with participants of the Wizards of OS 3 conference 
the results were devastating in a ~25 node mesh

- MPRs are contra-indicated if you want to avoid loops - the redundancy of 
multiple paths propagating TC information is desperately needed in a 
productive environment where payload saturates the links. Otherwise TC data 
bases get out of sync locally and things become very, very messy

- MPRs don't help much in terms of scalability as long as every TC has a 
global TTL

- RFC3626's hysteresis is a no-no - especially in combination with MPRs. MPRs 
are selected which frequently get kicked out by hysteresis - the problem of 
syncing TC information gets even worse & the protocol needs to negotiate the 
MPR set again.

- A simple fish-eye algorithm worked much better in terms of scalability and 
allowed us to send TC updates more often than Hellos without suffocating our 
city wide mesh network of +400 nodes (mostly Linksys WRT54G) at the time. 
Hence TC updates were redundant which drastically mitigated the looping 
problem. Still under very high network load we had transient routing loops. 
This is still a issue. The mesh grew up to ~650 nodes in Berlin without 
problems - however we were pushing the CPU load to the limits before the code 
was optimized by the Olsr-ng project. 

- Minimum hop count metric optimizes packet loss, so the first thing we did was 
adding a metric based on ETX which communicates link quality data with every 
Hello message to single hop neighbors (LQ/NLQ)

The experience of the Freifunk people with OLSR is described in more detail 
here: https://www.open-mesh.org/wiki/the-olsr-story Note that the document is 
summing up the experience until mid 2005.

Our work was/is miserably documented to say the least. As an excuse I can say 
that we were focused on getting the mesh network usable for the community. The 
modifications are present in the Olsr implementation from olsr.org and can be 
switched on and off via the configuration file. Sample configurations come with 
the source code or can be found in the wiki pages of the wireless communities.

I don't know any real-life network using the RFC3626 configuration in a 
productive environment. If you do know, let me know. However there are 
community networks in Tanzania, South Africa, India, Europe and elsewhere 
successfully using the Olsr daemon with the modifications. 

The modified Olsr daemon has been tested with up to 850 nodes in real life. It 
is working on low-end consumer APs running Openwrt with moderate CPU load 
thanks to the OLSR-NG project which has optimized the code after I ceased 
being active in the Olsr.org development. 

We have started a new community-driven mesh protocol development site in 2006 
- open-mesh.net. The name of our current protocol project is BATMAN. 
Generation three of the algorithm is described in a document available here: 
http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00

A reviewer has claimed that the protocol allegedly would loop and consume too 
much CPU and battery power for a MANET protocol. We didn't bother to defend 
the draft because we have better use for our time. Please reprieve me from 
protocol discussion dogfights.

Note that the document is referring to mark III of the algorithm, while we are 
currently working on designing mark 5. Implementations of mark 4 are available 
from our web site and as opkg-packages in Openwrt.

A comparison between Batman mark IV (Batman-experimental branch) and the 
modified (!) OLSR daemon is available here: 
http://wirelessafrica.meraka.org.za/wiki/images/9/98/Batman_ifip.pdf

BATMAN is a stigmeric approach which has proven to be loop-free and scalable. 
There are two competing implementations and change sets for OSI Layer 3 and 
one for "Layer 2.5". The largest real-life deployments have ~120 nodes - we 
are currently facing the difficulty to establish the new protocol in the 
community alongside the modified OLSR, because people hesitate to change their 
"running system" and known "standard" for something new. And some people love 
to defend "their" protocol. Germans tend to say: "The apple in the hand is 
better than the sparrow on the roof." No matter how cute the sparrow is ;-)

Cheers,
Elektra

---

From: Richard Ogier <[email-masked]>
Date: Sat, 06 Jun 2009 00:11:38 -0700

>the instant hello was no longer MPR ???

Here is one possible explanation.
Letting X -> Y -> Z be the first two hops of a calculated path, it is
possible that Y is not an MPR of Z, since the topology graph can use
2-hop neighbor info, and MPRs will not always cover all 2-hop neighbors
due to topology changes.
(In fact, the above path could be used even if there is another
path X -> W -> Z in which W is an MPR of Z.)
In this case, Y -> Z is not advertised in a TC message, so X knows
about this link only from hellos.
Therefore, if Y sends an instant hello when Y -> Z fails, this could
avoid a loop between X and Y (if there is another path from X to Z).

Richard

P.S. Philippe described a similar example, but did not mention that
an instant hello avoids a loop only if the failed link was not
advertised in a TC message.

---

From: "Teco Boot" <[email-masked]>
Date: Sat, 6 Jun 2009 16:06:39 +0200

Hi Richard,

|-----Oorspronkelijk bericht-----
|Van: Richard Ogier [mailto:[email-masked]]
|Verzonden: zaterdag 6 juni 2009 9:12
|Aan: Teco Boot
|CC: [email-masked]
|Onderwerp: Re: [manet] New draft: "Routing Loop Issue in Mobile Ad Hoc
|Networks (MANETs)"
|
|  Teco Boot wrote:
|
|>The instant hello is used for triggering a TC on the neighbor nodes
|>and MPR selection only and doesn't help avoiding loops directly.
|Correct?
|>How to explain the 10% loop reduction by instant hellos, reported by
|>Lee? Due to topology reduction mechanisms, where the node sending
|>the instant hello was no longer MPR ???
|>
|>
|
|Here is one possible explanation.
|Letting X -> Y -> Z be the first two hops of a calculated path, it is
|possible that Y is not an MPR of Z, since the topology graph can use
|2-hop neighbor info, and MPRs will not always cover all 2-hop neighbors
|due to topology changes.

I think the MPR set of Z will always cover all known 2-hop neighbors
via symmetric links. But yes, due to delay in flooding, others might
have other, outdated info. I am not sure this is the explanation.

|(In fact, the above path could be used even if there is another
|path X -> W -> Z in which W is an MPR of Z.)

Using the OLSRv2 Appendix C. Algorithm, topology tuples are selected
before 2-hop neighbor tuples.

When the algorithm is updated for validating a routing tuple if 
R_dist = 2, checking the 2-Hop set, the instant hello would have
effect.
Update Appendix C ??

Teco.

|In this case, Y -> Z is not advertised in a TC message, so X knows
|about this link only from hellos.
|Therefore, if Y sends an instant hello when Y -> Z fails, this could
|avoid a loop between X and Y (if there is another path from X to Z).
|
|Richard
|
|P.S. Philippe described a similar example, but did not mention that
|an instant hello avoids a loop only if the failed link was not
|advertised in a TC message.

---

From: Richard Ogier <[email-masked]>
Date: Sat, 06 Jun 2009 09:05:12 -0700

>have other, outdated info. I am not sure this is the explanation.

I'm not sure either. I'm just saying it is one possibility. For
example, if Z selected W to be an MPR that covers X, and then W -> Z
fails, then it could be a few seconds before Z learns of this failure
(via hellos) and selects Y as MPR, and could be several seconds
before X is finally informed that Y -> Z is advertised in a TC.

>before 2-hop neighbor tuples.

OK, but this algorithm is not required, and I don't know if Lee used it.
Also, note that this can't always be done if metrics are used.

>R_dist = 2, checking the 2-Hop set, the instant hello would have

I'm not sure what you mean. Maybe you mean that if a received hello
indicates that Y -> Z failed, then that link should not be allowed even
if Y -> Z is represented by a topology tuple.  In other words, a
topology tuple for Y -> Z, where Y is a neighbor, is valid only if
Y -> Z is also in the 2-Hop set.  This might help.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Sat, 06 Jun 2009 10:58:26 -0700

Teco Boot wrote:

>via symmetric links.

Although not my main point, I will show that the above is not true.
  X
 / \
Y   W
 \ /
  Z
Assume Z selects W as its only MPR.
Assume the link between X and W fails. (It is possible that X detects
the failure before W, but this is not necessary for the example.)
Assuming no instant hellos (or even if there are instant hellos,
they are not reliable), it can be a few seconds before Z knows
about the link failure.  During this time, X is still a known 2-hop
neighbor but is not covered by an MPR, although Z *thinks* it is.

Of course, when X detects the failure, it will update its route
to go through Y, even though Y is not is not an MPR of Z (but
we agree on that).

Richard

---

From: "Teco Boot" <[email-masked]>
Date: Sun, 7 Jun 2009 09:05:38 +0200

|>When the algorithm is updated for validating a routing tuple if
|>R_dist = 2, checking the 2-Hop set, the instant hello would have
|>effect.
|>Update Appendix C ??
|>
|I'm not sure what you mean. Maybe you mean that if a received hello
|indicates that Y -> Z failed, then that link should not be allowed even
|if Y -> Z is represented by a topology tuple.  In other words, a
|topology tuple for Y -> Z, where Y is a neighbor, is valid only if
|Y -> Z is also in the 2-Hop set.  This might help.

Yes, this is my proposal.

Teco.

---

From: "Teco Boot" <[email-masked]>
Date: Sun, 7 Jun 2009 09:12:32 +0200

|-----Oorspronkelijk bericht-----
|Van: Richard Ogier [mailto:[email-masked]]
|Verzonden: zaterdag 6 juni 2009 19:58
|Aan: Teco Boot
|CC: [email-masked]
|Onderwerp: Re: [manet] New draft: "Routing Loop Issue in Mobile Ad Hoc
|Networks (MANETs)"
|
|Teco Boot wrote:
|
|>I think the MPR set of Z will always cover all known 2-hop neighbors
|>via symmetric links.
|>
|
|Although not my main point, I will show that the above is not true.
|  X
| / \
|Y   W
| \ /
|  Z
|Assume Z selects W as its only MPR.
|Assume the link between X and W fails. (It is possible that X detects
|the failure before W, but this is not necessary for the example.)
|Assuming no instant hellos (or even if there are instant hellos,
|they are not reliable), it can be a few seconds before Z knows
|about the link failure.  During this time, X is still a known 2-hop
|neighbor but is not covered by an MPR, although Z *thinks* it is.
|
|Of course, when X detects the failure, it will update its route
|to go through Y, even though Y is not is not an MPR of Z (but
|we agree on that).

Agreed. My text after the quotation:
>>> But yes, due to delay in flooding, others might
>>> have other, outdated info. 
Maybe "due to delay of detecting and flooding" and not only flooding.

Our main point is loops have to do with out-of-sync Network Topology 
Graph and not with LLN.

Teco.

---

From: Henning Rogge <[email-masked]>
Date: Sun, 7 Jun 2009 09:24:16 +0200

Just as a comment, both Elektras and (mostly) mine experience with mesh net 
protocols were made on 802.11 hardware, so it should be applicable for most 
CSMA-CA networks, but not for TDMA networks.

> bases get out of sync locally and things become very, very messy
Yes.

I think MPRs can be useful in high density situations. If you have 30 one-hop 
neighbors on a market place, you might not want to flood through all of them.

But in sparse mesh networks (especially in urban terrain which 
restricts line of sight and limit broadcast redundancy) a strict MPR set 
combined with packet loss can easily break the flooding propagation through 
the mesh, leading to inconsistent topology databases and routing loops.

> - MPRs don't help much in terms of scalability as long as every TC has a
The effect on scalability of MPRs depends on the node density and on the size 
of the broadcast domains. In simulations and in dense networks without 
obstacles MPRs can be even more effective than many fisheye implementations 
(the OLSR.org fisheye would not reduce the number of packets for flooding by 
more than a factor of 16 for example, even on a hypotetical infinite network).
But 802.11 adhoc networks have problems with neighborhoods of 30-50 nodes.

The usage of MPR sets can create problems by itself, especially the loss of a 
Hello can be bad for MPR flooding.

Example:
A node X has two neighbors (A and B), and A is it's MPR at the moment.
Now node X want to switch to B as it's MPR and begin to send a Hello with the 
corresponding MPR choice. If A receives the Hello but B does NOT receive it no 
node will forward the packages for X unter the Hello is correctly received by 
B.

The "MPR desynchronization could be prevented if nodes signal their MPR 
Selector Set in hello messages. This way nodes could be sure that a new MPR 
has acknowledged it's status before switching off the old MPRs.

> - RFC3626's hysteresis is a no-no
I don't agree with this, I think the "metric" (exponential aging 
with an aging factor of 0.5) is the problem here. The OLSR RFC suggests using 
the last 3 Hellos as a way to determine the quality of the link, which results 
in a nearly random result. It might be interesting to test what happens with 
hysteresis and a very low aging factor (aging 0.1 and longer Hello timeouts), 
but I think using a real routing metric with Hellos AND TCs is definitely a 
better choice.

> especially in combination with MPRs.
> MPRs are selected which frequently get kicked out by hysteresis - the
> problem of syncing TC information gets even worse & the protocol needs to
> negotiate the MPR set again.
>
> - A simple fish-eye algorithm worked much better in terms of scalability
> and allowed us to send TC updates more often than Hellos without
> suffocating our city wide mesh network of +400 nodes (mostly Linksys
> WRT54G) at the time. Hence TC updates were redundant which drastically
> mitigated the looping problem. Still under very high network load we had
> transient routing loops. This is still a issue. The mesh grew up to ~650
> nodes in Berlin without problems - however we were pushing the CPU load to
> the limits before the code was optimized by the Olsr-ng project.
>
> - Minimum hop count metric optimizes packet loss, so the first thing we did
> was adding a metric based on ETX which communicates link quality data with
> every Hello message to single hop neighbors (LQ/NLQ)
Hopcount metric works well in simulations without smallscale fading. I don't 
think it works well in real networks outside the laboratory.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 8 Jun 2009 12:18:06 +0100

> fast routing table synchronization while not overloading the MANET.

In OLSRv2 there are minimum intervals that do this job. (We - BAE
Systems - actually first implemented these in OLSRv1.) The suggested
setting for these is 1/4 of the standard (maximum) intervals. The
ideal setting will of course depend on many factors (which is why it
is a parameter) but we have found 1/4 to be a reasonable value in at
least some scenarios. (See paper in the 1st OLSR Interop.)

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 8 Jun 2009 12:21:31 +0100

> from these methods, as the network was more overwhelmed by the
broadcast 
> packets triggered by the occurring LLNs than it benefited the routing 

The LLN mechanism has a hysteresis function (two thresholds) so that you
can avoid flapping the link state too often. If you are getting swamped
then that suggests you should possibly reduce the frequency of
LLN-induced
link state changes, plus managing a maximum TC sending rate - which is
why
we have minimum intervals in OLSRv2.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 8 Jun 2009 12:28:44 +0100

> RFC3626's hysteresis is a no-no

Except for those of us who use it in practice successfully. But we
set our thresholds carefully, and with a specific requirement - to
avoid the 802.11 "grey zone" problem. We don't allow over-rapid link
flapping, and regulate our update frequency. We use LLNs based on SNR,
but that's not the only option.

Like several features in OLSR (more in OLSRv2) it's a tool to be used
with care. Yes, used badly it can make things worse.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 8 Jun 2009 13:25:56 +0100

Henning Rogge wrote:
> Elektra wrote:
> with an aging factor of 0.5) is the problem here.

I wrote the following text, then revisited the above three lines,
and in short I think Henning said in two lines what's taken me a
lot more than two lines (though with details).

I think the first problem is that there are a number of things,
which in  RFC 3626 are lumpted together as hysteresis. In OLSRv2
we've attempted to clearly separate them

- Having a link quality mechanism that allows the exclusion of a
  link based other than on HELLO reception and timeout.

- What to use for that link quality. RFC 3626 first suggests a
  direct value (e.g. from SNR) then an alternative (next point).

- That alternative, which is a "leaky integrator" approach based
  on packet/HELLO reception/loss.

- Hysteresis, which is avoiding "flapping" by memory. The specific
  mechanism is the two thresholds where when in the region between
  them, it depends on whether you were more recently good or bad.

The first of these is essential, for 802.11 in particular (but not
only) because of the "grey zone" problem (differing multicast/unicast
characteristics).

OLSRv2 is clearer (I think) that there are various options for the
second point. SNR is one option with definite value.

OLSRv2 does not include the third point. It notes you can use
packet/HELLO
reception/loss (and even the point to avoid double-counting). But it
does
not include the specific leaky integrator case (though it makes a
reference
to that a leaky integrator - not specified is a possibility as I
recall).
That would be because it is (a) over-specific, and (b) debatable. (And
that's
not addressing the issue of whether 0.5 is a suitable factor - in OLSRv2
that's not an issue, there is no suggested factor parameter or value.)

Hysteresis of some form (and two thresholds is the simplest - and many
mechanism can be mapped to it) is necessary.

So if the objection to RFC 3626 in this area is specific to the leaky
integrator based on HELLO/packet reception loss, OK. For a start it
does nothing to solve the 802.11 grey zone problem. However the other
three components (ability to exclude links, various possibilities
exist, using hysteresis) is something needed.

---

From: Rex Buddenberg <[email-masked]>
Date: Mon, 08 Jun 2009 08:48:42 -0700

> CSMA-CA networks, but not for TDMA networks.

Henning,

Has anyone worked the same problems with scheduling algorithms?  What
would be the effects if you were to substitute an IEEE 802.16 or TIA LTE
network for an IEEE 802.11 one?

A lot of the same problems that we see in meshing also negatively affect
MAC issues -- too many stations with too much traffic and the MAC
stalls.  This means that contention MACs are wholly unsuitable for
radio-WANs ... yet this is the territory that we need good MANET
performance.  

-- 
Rex Buddenberg
Naval Postgraduate School
Code IS/Bu
Monterey, Ca 93943
831/656-3576

---

From: Henning Rogge <[email-masked]>
Date: Mon, 8 Jun 2009 19:48:03 +0200

Am Montag 08 Juni 2009 17:48:42 schrieb Rex Buddenberg:
> > Just as a comment, both Elektras and (mostly) mine experience with mesh
> > net protocols were made on 802.11 hardware, so it should be applicable
> > for most CSMA-CA networks, but not for TDMA networks.
>
The problem is that a "collision avoidance" wireless network will always have 
problems like hidden stations... and a performance decrease at a certain 
amount of traffic.

> radio-WANs ... yet this is the territory that we need good MANET
neither WLAN nor WIMAX were designed for large mesh networks. According to my 
knowledge WIMAX is not mesh capable between the client stations, only the base 
stations can create a full mesh.

We are still waiting for a special "mesh net optimized" waveform for software 
defined radios. ;)

Henning

---

From: Lee Speakman <[email-masked]>
Date: Wed, 10 Jun 2009 19:15:40 +0900

> we have minimum intervals in OLSRv2.
We have found that the use of a hysteresis on link formation based on 
the reception or lack thereof of Hello Packets can only go so far in 
providing for link stability, particularly in networks with node 
mobility, and the problem of looping packets still remains somewhat, 
even if only triggering a link-state change in OLSRv2 after multiple LLNs.
The number of LLNs in-node required before making a change to the 
link-state in OLSRv2 then becomes a tradeoff between forwarding packets 
potentially to be dropped over an unphysical link and making a premature 
or unnecessary link-state change. We have generally found that having a 
link-state change triggered only after 2 or 3 LLNs is not much different 
in the result to having a link-state change triggered only after 1 LLN, 
except in the delay in the change of link-state, as each LLN requires up 
to 4 or 7 retries at the link layer.
The tradeoff in the use of the hysteresis is also with responsiveness to 
the changes in the network against more stable links.

It is certainly worth having minimum intervals though. Thanks.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Wed, 10 Jun 2009 11:31:42 +0100

> providing for link stability

If we are specifically discussing link quality (hysteresis is a
mechanism
used to manage link quality changes) based purely on HELLO messages
and/or packets (saying Hello Packets is misleading) then I'm not
defending that. While of course 802.11 is not the only game in town,
it is a case where link quality based purely on HELLO messages and
packets
is insufficient, but the link quality mechanism is useful, or even
essential
(at least without link metrics, and even with them it can be usefully
used)
- just base it on something else, from the link layer.

> We have generally found that having a 
> link-state change triggered only after 2 or 3 LLNs

What do you mean here by an LLN? Packets and HELLOs can be done at the
network layer. Or do you mean real link layer information?

I think it really is helpful to separate out the concepts of link
quality, hysteresis, link layer notifications, and link loss. Then
we can be clear if we are discussing the same thing. Unfortunately
RFC 3626 doesn't do this as well as it should - I hope NHDP is
better (but of course if we've missed anything, do let us know).

---

From: Henning Rogge <[email-masked]>
Date: Wed, 10 Jun 2009 13:57:02 +0200

Am Wednesday 10 June 2009 12:15:40 schrieb Lee Speakman:
> mobility,
This is no supprise, it's just a result of the statistic attributes of the 
link quality metric. Each loss/reception of a hello is just a binary event.

Even if the loss propability of the link is totally stable, you need a lot 
more than 3 events (Hellos) to get a good approximation of the loss 
probability.

With a loss propability of 50% (as an example) 1/8 of the possible "3 Hello 
events" will tell OLSR it has a perfect link (no loss), 3/8 will see a "33% 
loss" link, 3/8 will see a "66% loss" link and 1/8 will get no Hello at all. 
The hysteresis could not prevent a static link like this to switch on/off.

It's necessary to get better data (signal strength and other layer 2 
measurements) or more data (integrate over a longer time) for a working 
hysteresis.

-- 
Henning Rogge

---

From: Lee Speakman <[email-masked]>
Date: Thu, 11 Jun 2009 19:03:38 +0900

> But the instant TC should reach the nodes far from the broken link, 
> the instant hello not.
>
> I would be surprised that the transmission of a single instant hello 
> and of a single instant TC bring any significant increase of overhead, 
> at least it should be negligible compared to the loop overhead (data 
We did not examine the Instant TC in detail, but we certainly observed 
the effect of the Instant Hello not being well received in the adjacent 
nodes.  We increased the chance of this being received by scheduling one 
of more Instant Hellos on a trigger event - either an LLN or a Loop 
Detection - although at the cost of increasing the overhead.

We could increase the chance that the loops would be dissolved up to a 
limit (~10%) by using more Instant Hello broadcasts, therefore 
potentially providing a gain, but the overhead from the broadcasts 
canceled all such gains.

Yup. Once loops are formed, even though transiently, the surrounding 
network is effectively blocked, or particularly has significantly 
reduced chance to medium access, and in the neighboring flows packets 
are dropped, and are perceived  as link failures, leading to new longer 
routes being selected to route the packets in those flows, this in turn 
leads to the likelihood of more effective load in the network and the 
likelihood that more loops will form.

In our simulations we have a TTL of 63, rather than 255

> cancels the route, then drop packets while sending the new TC, and 
> AFTER do new route calculation.
>
I'm not sure I know what you mean, but to clarify, you mean also for 
that node to wait for receiving a new TC before doing a new route 
calculation, and in the meantime just drop packets?

Wouldn't this result in high loss for at least a short time?

Cheers,
   Lee -S-

---

From: Ulrich Herberg <[email-masked]>
Date: Thu, 11 Jun 2009 12:14:08 +0200

Hi,

On Thu, Jun 11, 2009 at 12:03 PM, Lee Speakman <[email-masked]
> wrote:

> [...]
> We did not examine the Instant TC in detail, but we certainly observed the
> effect of the Instant Hello not being well received in the adjacent nodes.
>  We increased the chance of this being received by scheduling one of more
> Instant Hellos on a trigger event - either an LLN or a Loop Detection -
> although at the cost of increasing the overhead.
> [...]

Can you explain why the Instant Hello is not well received? What often are
they lost? Do you use jitter for the instant Hello? Do you respect minimum
HELLO intervals in your implementation?

Cheers,
Ulrich

---

From: Lee Speakman <[email-masked]>
Date: Thu, 11 Jun 2009 19:29:12 +0900

> - just base it on something else, from the link layer.
Agreed.

> better (but of course if we've missed anything, do let us know).
By "LLN", further qualified by in-node LLN, we so far use the term to 
indicate an in-node link layer notification to the routing protocol that 
occurs on the event that an acknowledgment frame is not received after 
attempting to forward a unicast packet to another node. For the case of 
802.11b in our simulations this would occur on failure to receive an ACK 
after 4 (LongRetryLimit) or 7 (ShortRetryLimit) retries depending on if 
RTS/CTS is in use.

By "link loss" I indicate the loss of the link in routing protocol, for 
example OLSRv2's Link Set and so also from its Routing Table that should 
always be consistent with the Link Set.

I use the term "unphysical link" if the link is perceived to exist by a 
node, for example is still in OLSRv2's Link Set and the Routing Table, 
but no physical link could possible be supported at that time.

Cheers,
Lee -S-

---

From: jacquet <[email-masked]>
Date: Thu, 11 Jun 2009 13:21:18 +0200

I mean that instant hellos cannot dissolve the loops in your topology, 
only instant TCs could. Do you plan to simulate those TC's?

I still not understand via LLNs create more loops than link failure 
detected by hello loss.

Are you sure there are no flaws in your simulations? Maybe there are 
uncontrolled overheads, for example you say that extra hellos create 
such overhead that cancels any gain, which is obviously not true:  few 
extra hellos should create very negligible overhead compared to datas, 
retried datas, and looping datas.

Regards,
Philippe

Lee Speakman a écrit :
>> and of a single instant TC bring any significant increase of 
>> overhead, at least it should be negligible compared to the loop 
>> overhead (data packets being repeated 255 times). But maybe the loops 
>> congest the network and prevent the instant TC or the instant hello 
>> to be actually received. This is a plausible explanation since you 
>> say somewhere that the loops also create other link failures, and 
>> then other loops.
> the effect of the Instant Hello not being well received in the 
> adjacent nodes.  We increased the chance of this being received by 
> scheduling one of more Instant Hellos on a trigger event - either an 
> LLN or a Loop Detection - although at the cost of increasing the 
> overhead.
>
> are dropped, and are perceived  as link failures, leading to new 
> longer routes being selected to route the packets in those flows, this 
> in turn leads to the likelihood of more effective load in the network 
> and the likelihood that more loops will form.
>

---

From: Lee Speakman <[email-masked]>
Date: Thu, 11 Jun 2009 20:09:06 +0900

Agreed.

> more than 3 events (Hellos) to get a good approximation of the loss 
Yes. Admittedly hysteresis is useful in not selecting links which
fluctuate on receiving Hellos (sometimes receiving packets, sometimes not).
One thing though is that when nodes move out of range of each other,
perhaps suddenly by going round a corner, even if previously a perfect
link had existed as established by a previously consistent number of
Hello receptions, if that link is supporting traffic, hysteresis is too
slow a process in order to respond in the sudden unphysicalness of that
link. So the LLN (a link layer notification in-node to the routing
protocol on the failure of that node to receive acknowledgment of the
successful forwarding of a unicast packet to a neighboring node) is
required.
The nature of the in-node LLN seems to be such that it causes sudden
changes in perception of the network leading to the increased likelihood
of loop formation. In such cases, if there are several traffic flows in
the network, the combined effect of links lost through these LLN causes
several incoherencies in perceived maps of the network that may lead to
several transient routing loops and the looping packet over it.

So even though using hysteresis to build up a fairly good set of
neighboring nodes, we use LLN in order to respond quickly to sudden loss
of links in the network, so as not to drop them resulting in high loss
under various scenarios.

The problem is intensified as even though the LLN is ideally used to
remove the unphysical link where two nodes are no longer in range of
each other, the effect of transient looping packets is to cause sudden
intense use of the medium, reducing medium access in the vicinity of the
looping packets and so further unnecessary LLNs occur due to this.

> measurements) or more data (integrate over a longer time) for a working 
Yes. I think this is an important approach.
We are exploring layer 2 measurements to support a quick response to
changes in the network.

In a static mesh network, it may be possible to effectively do away with
all loops by using a number of mechanisms, hysteresis and layer 2
measurements, as long as nodes do not suddenly fail, but with mobility,
there is still the need to respond quickly to unphysical links.

As far as we see, this will introduce incoherencies in the perceived
topology maps between the nodes of the network, leading to routing loops
and looping packets, so we need to deal with this in some way.

Cheers,
Lee -S-

---

From: "Hokelek, Ibrahim" <[email-masked]>
Date: Thu, 11 Jun 2009 10:17:40 -0400

>>I still not understand via LLNs create more loops than link failure

Is the reason because of more failures are detected via LLNs compared to the hello loss
mechanism. Is there any simulation result showing how many failures detected via LLNs vs hello
loss?

Thanks,
Ibrahim

---

From: Lars Landmark <[email-masked]>
Date: Thu, 11 Jun 2009 17:02:48 +0200

Phillip and Lee;

> only instant TCs could. Do you plan to simulate those TC's?

According to the reference 6 in Lee’s draft, on page 1217 figure 5a, majority of the loops are formed over “2-way”. Instant TC messages would only help loops formed over three hops or more. Hence, instant TC messages would only have small contribution, or am I wrong?  

> I still not understand via LLNs create more loops than link failure

 I am not sure, and have neither verified the next hypothesis; 
Assuming that the HELLO packets are scheduled within a constant hello interval of 2 seconds, plus jitter, then all 1-hop neighbors are notified about a link break simultaneously 6 seconds after the last received HELLO message. On the other hand, if LLN is being used, the node experiencing the unsuccessful transmission will immediately tear down the link. On average, this will occur approximately one second after the last scheduled HELLO message and one second before the next scheduled HELLO message. That is, by the remaining one second until scheduling the next HELLO message the local node and its surrounding 1-hop nodes will operate on different topology maps. However, I am not sure whether the large number of packets entering a loop can be explained by this short time of inconsistent topology maps. It would depend on the surrounding traffic load.  

A typical problem of high traffic load is high loss of control packets and different system time. In this context, the system time is queuing time and transmission time. If control packets are scheduled after experiencing high system time, the local node and its suroundings will likely operate on different topology maps. The next question would then be; are the control packets scheduled with priority or equal to the ordinary data traffic? 
 
Since the problem of route loops appear to be lower in dens networks, would it be an idea to increasing the number of MPR’s, i.e. covering all 2-hop by at least 2 MPR’s? It would not solve the problem, but perhaps reduce the problem, at least in sparse networks, without “to much overhead”.  

Regards
Lars
Student      

Regards,
Philippe

---

From: jacquet <[email-masked]>
Date: Thu, 11 Jun 2009 18:28:03 +0200

Dear Lars and Lee,

Unfortunately I cannot access this reference. :-(

Is "2-way" refering to hop number or status over symmetric links? I 
understood from Lee's previous posts that most loops were not adjacent 
to the broken link. The instant hello cannot solve loops that are not 
adjacent to the broken link while the instant TC will do it (if 
correctly received).

I don't think there is a significant impact on overhead.

Philippe

---

From: Lee Speakman <[email-masked]>
Date: Fri, 12 Jun 2009 15:34:32 +0900

Dear Phillipe and Ulrich,

Firstly, there are several researches we have done with the Instant 
Hello.  I establish in more detail and more precisely what we have done 
before continuing.

The problem of looping is observed to occur where there are higher loads 
in the network, in our case with multiple flows crisscrossing the network.
If, on an event, we send just one Instant Hello, then in such cases, due 
to already circling packets around loops, there is a lesser probability 
that surrounding nodes will be able to successfully receive the Instant 
Hello compared to when there is little traffic in the network.

What we first observed was that a single Instant Hello triggered on 
in-node LLN (caused by failure to receive successive link layer 
acknowledgements from attempting to forward a unicast packet) made very 
little difference in the PDR (end-to-end delivery) and the number of 
loops which we were measuring at that time, regardless of if the packet 
was scheduled immediately, or using the full jitter interval or a 
fraction of it.  There were only minor improvements in PDR of a few 
percent when network load was such that PDR was down to ~70% in 
OLSRv2-LLN which was not very effective.

As we were just sending one Instant Hello on LLN to explore it in the 
use of dissolving loops, we did not use a minimum Hello interval.

To see if the cause was due to the Instant Hello not being received, we 
scheduled multiple Hellos, this reduced the number of loops further 
(showing that a single Hello had probably not been well received) but 
also increased the overhead.  For that simulation with multiple Instant 
Hellos in short succession this is where we could get around ~10% of the 
loops dissolved, but at the cost of the overhead increasing as we 
increased the number of loops, thereby countering any gains from the 
reduced number of loops.

Sorry, I had not intended to confuse when I originally expressed our 
observed effects of the use of Instant Hellos.  I was only mentioning 
this briefly to express under certain scenarios how we find that for 
~90% of the loops the loop comes about from an incoherent perception of 
the network between adjacent nodes through their Topology Sets and so 
cannot be fixes with an Instant Hello, and that the effect of an LLN 
cutting a link that is unphysical is often to cause a change such that a 
loop appears not only one link away (an adjacent link), but also two 
links or more away from the lost link.

After studying various packet traces and all nodes Link Set and Topology 
Sets to find out why we could never dissolve more than ~10% of loops in 
this particularly scenario, we found that the majority of loops are more 
than one link-hop away from where the LLN is occur.  The node in which 
an LLN occurs from dropping a unicast packet only selects a new route 
(after removal of that link), forwarding it along a different path, and 
further in that path a loop occurs.

In more recent simulation, with the same parameters as given in our 
published work, we measure the number of nodes that receive each 
broadcast packet (control packet).

This is done for 60 nodes with a maximum mobility of 5m/s (random 
waypoint, random mobility between 0 and 5m/s).

i. At modest loads, 8 applications (CBR, UDP), then we find that 
OLSRv2-LLN has a ~85% PDR (end-to-end delivery) with ~1700 looping 
packet observations on average per simulation.
An Instant Hello on LLN gives no improvement in PDR and the number of 
loops is approximately the same.  An Instant TC on LLN gives the same 
result.

At almost no load, a control packet is on average received by 17.5 nodes 
(more in the center, less on the edges), but at a load of 8 apps this is 
down to just over 16 nodes.  This is worse at the time a transient 
looping packet is existing.

Disregarding Instant Hellos / TCs, we can get real improvements by 
simply using a Loop Detection mechanism and discarding the packets 
(Packet Discard), bringing the PDR up to ~94.5%, and better improvements 
by cutting the link over which a looping packet is detected (Link Cut), 
bringing the PDR up to ~96%.

ii. At 12 application, where there are more loops, then we find that 
OLSRv2-LLN has a ~74% PDR with ~4300 looping packet observations on 
average per simulation.
An Instant Hello on LLN gives about a 3% improvement in PDR (to ~77%) 
and the number of observed loops is ~3700.  An Instant TC on LLN gives 
the same result.

At almost no load, a control packet is on average received by 17.5 nodes 
(more in the center, less on the edges), but at a load of 12 apps this 
is down to less than 15 nodes.  This is worse at the time a transient 
looping packet is existing.

Again, using Packet Discard on Loop Detection brings the PDR up to 
~92.5%, and with Link Cut on Loop Detection we get the PDR up to ~94%.

Simply discarding the observed looping packets and the improvement that 
has on PDR shows the negative effects of looping packets on surrounding 
traffic.

We have also looked at Instant Hellos and Instant TC on Loop Detection 
which shows some improvement; to 88% PDR (up 3%) for 8 apps (removing 
~24% of loops), and to 79% PDR (up 4%) for 12 apps (removing ~19% if 
loops).  This appears to become less effective at higher loads.  The 
looping packet is not discarded nor is the link cut over which the 
packet loops, so on every node the looping packet passes an Instant 
Hello or TC is generated on Loop Detection.

None of these Instant Hellos / TCs interrupted any of the periodic 
scheduling of the control packet broadcasts but were done "extra."

Cheers,
   Lee -S-

---

From: Ulrich Herberg <[email-masked]>
Date: Fri, 12 Jun 2009 09:09:23 +0200

Dear Lee,

thanks for the more detailed information. Were your simulations performed in
Ns2? If so, I would be interested in having your tcl script for the scenario
in order to reproduce your simulation with my OLSRv2 implementation.
It's a pity that your paper is not public .

Cheers,
Ulrich

On Fri, Jun 12, 2009 at 8:34 AM, Lee Speakman
<[email-masked]>wrote:

> Firstly, there are several researches we have done with the Instant Hello.
>  I establish in more detail and more precisely what we have done before
> continuing.
>
> The problem of looping is observed to occur where there are higher loads in
> the network, in our case with multiple flows crisscrossing the network.
> If, on an event, we send just one Instant Hello, then in such cases, due to
> already circling packets around loops, there is a lesser probability that
> surrounding nodes will be able to successfully receive the Instant Hello
> compared to when there is little traffic in the network.
>
> What we first observed was that a single Instant Hello triggered on in-node
> LLN (caused by failure to receive successive link layer acknowledgements
> from attempting to forward a unicast packet) made very little difference in
> the PDR (end-to-end delivery) and the number of loops which we were
> measuring at that time, regardless of if the packet was scheduled
> immediately, or using the full jitter interval or a fraction of it.  There
> were only minor improvements in PDR of a few percent when network load was
> such that PDR was down to ~70% in OLSRv2-LLN which was not very effective.
>
> As we were just sending one Instant Hello on LLN to explore it in the use
> of dissolving loops, we did not use a minimum Hello interval.
>
> scheduled multiple Hellos, this reduced the number of loops further (showing
> that a single Hello had probably not been well received) but also increased
> the overhead.  For that simulation with multiple Instant Hellos in short
> succession this is where we could get around ~10% of the loops dissolved,
> but at the cost of the overhead increasing as we increased the number of
> loops, thereby countering any gains from the reduced number of loops.
>
> observed effects of the use of Instant Hellos.  I was only mentioning this
> briefly to express under certain scenarios how we find that for ~90% of the
> loops the loop comes about from an incoherent perception of the network
> between adjacent nodes through their Topology Sets and so cannot be fixes
> with an Instant Hello, and that the effect of an LLN cutting a link that is
> unphysical is often to cause a change such that a loop appears not only one
> link away (an adjacent link), but also two links or more away from the lost
> link.
>
> Sets to find out why we could never dissolve more than ~10% of loops in this
> particularly scenario, we found that the majority of loops are more than one
> link-hop away from where the LLN is occur.  The node in which an LLN occurs
> from dropping a unicast packet only selects a new route (after removal of
> that link), forwarding it along a different path, and further in that path a
> loop occurs.
>
>
> published work, we measure the number of nodes that receive each broadcast
> packet (control packet).
>
> This is done for 60 nodes with a maximum mobility of 5m/s (random waypoint,
> random mobility between 0 and 5m/s).
>
>
> i. At modest loads, 8 applications (CBR, UDP), then we find that OLSRv2-LLN
> has a ~85% PDR (end-to-end delivery) with ~1700 looping packet observations
> on average per simulation.
> An Instant Hello on LLN gives no improvement in PDR and the number of loops
> is approximately the same.  An Instant TC on LLN gives the same result.
>
> down to just over 16 nodes.  This is worse at the time a transient looping
> packet is existing.
>
> Disregarding Instant Hellos / TCs, we can get real improvements by simply
> using a Loop Detection mechanism and discarding the packets (Packet
> Discard), bringing the PDR up to ~94.5%, and better improvements by cutting
> the link over which a looping packet is detected (Link Cut), bringing the
> PDR up to ~96%.
>
>
> OLSRv2-LLN has a ~74% PDR with ~4300 looping packet observations on average
> per simulation.
> An Instant Hello on LLN gives about a 3% improvement in PDR (to ~77%) and
> the number of observed loops is ~3700.  An Instant TC on LLN gives the same
> result.
>
> (more in the center, less on the edges), but at a load of 12 apps this is
> down to less than 15 nodes.  This is worse at the time a transient looping
> packet is existing.
>
> Again, using Packet Discard on Loop Detection brings the PDR up to ~92.5%,
> and with Link Cut on Loop Detection we get the PDR up to ~94%.
>
>
> Simply discarding the observed looping packets and the improvement that has
> on PDR shows the negative effects of looping packets on surrounding traffic.
>
>
> which shows some improvement; to 88% PDR (up 3%) for 8 apps (removing ~24%
> of loops), and to 79% PDR (up 4%) for 12 apps (removing ~19% if loops).
>  This appears to become less effective at higher loads.  The looping packet
> is not discarded nor is the link cut over which the packet loops, so on
> every node the looping packet passes an Instant Hello or TC is generated on
> Loop Detection.
>

---

From: Lee Speakman <[email-masked]>
Date: Fri, 12 Jun 2009 16:31:08 +0900

Dear Philippe and Lars,

I used "2 way" loops to refer to packets that loop back and forth 
between just 2 nodes; A --> B --> A --> B --> ... (A <--> B).
Where, for example, 3-way loops would be triangular loops between 3 
node; A --> B --> C --> A --> B --> C --> ... .

About 93% of observed looping packets are "2-way", except at lighter 
loads with few loops in which almost all of these looping packets tend 
to be "2-way".
The remaining 7% are "3-way" or higher, where "3-way" loops are more 
dominant than "4-way" and so on to higher order.

This is just the observed nature of the looping packet and may not be 
directly related to if they are adjacent to nodes that have had a LLN.

In what way the loops exist is dependent on a number of factors; load, 
node-density (link density) and mobility being three we have explored.
 From the use of Instant Hello on LLN (at 12 app load), we come to the 
conclusion that for this case perhaps around ~13% of loops are adjacent 
to and dissolvable by Instant Hellos triggered on LLN (one Instant Hello 
triggered per LLN). There's unlikely to be significant impact on 
overhead from this but it only gives a 3% improvement in PDR (to ~77%).

In the event that there are looping packets, for a short time the 
network is busy forwarding looping packets, the medium is kept very busy 
and the probability that control packets are received is also decreased.

We plan to look further at Instant TCs, perhaps in use with a Packet 
Discard technique on Loop Detection so that the Hellos and TCs can once 
again be successfully received by the surrounding nodes.

Cheers,
Lee -S-

jacquet さんは書きました:
>> According to the reference 6 in Lee’s draft, on page 1217 figure 5a, 
>> majority of the loops are formed over “2-way”. Instant TC messages 
>> would only help loops formed over three hops or more. Hence, instant 
>> TC messages would only have small contribution, or am I wrong?
>
>

---

From: Lee Speakman <[email-masked]>
Date: Fri, 12 Jun 2009 16:44:45 +0900

Dear Ulrich,

we performed the simulations with Qualnet 4.0 with an updated version of 
nOLSRv2.
We have the simulation config and other files for this in order to 
recreate the simulations. Though to track looping packets, count them 
and see their nature ("2-way" etc.) we made modification to the 
simulation suite in simulation space.

It would be good to be able to recreate such results in Ns2 with another 
implementation of OSLRv2.

Cheers,
Lee -S-

Ulrich Herberg さんは書きました:
> Dear Lee,
>
> thanks for the more detailed information. Were your simulations 
> performed in Ns2? If so, I would be interested in having your tcl 
> script for the scenario in order to reproduce your simulation with my 
> OLSRv2 implementation.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 12 Jun 2009 10:02:11 +0100

> slow a process in order to respond in the sudden unphysicalness of
that

Can I make another appeal for precise terminology (although I admit
RFC 3626 encourages the poor use). This is not hysteresis. Hysteresis
is about link state having memory, in OLSR (v1 and v2) implemented using
higher and lower thresholds for a good link. The process that's too
slow is one of (I think - and that's why precision is important, so
we know what we are talking about) counting HELLO messages and/or
packets.

> So the LLN (a link layer notification in-node to the routing

I would agree that, if possible, information from the link layer is
desirable.

> of loop formation.

Since there are different possible LLN mechanisms, whether one such
causes multiple sudden changes depends entirely on the nature of that
LLN mechanism - and in particular on what hysteresis (in the proper
sense of the term) you apply to it.

But in the case of your example of going round a corner, a sudden (how
sudden depends on speed and the nature of the propagation round the
corner) loss of link is what actually happens physically. The ideal is
to discard that link locally, and by signalling, remotely as soon as
possible (consistent with managing signalling load, a standard
tradeoff).

But this is about link loss. There's nothing new in using LLN, you will
lose that link going round the corner at some point (expiry of Link
Tuple
in particular). The point of LLNs in this case is to accelerate the loss
- in the case of a sharp corner there is no extra problem in using LLNs,
you get the same one event, just earlier. This makes things better, not
worse (shorter period when packets will actually be lost despite having
an entry in the routing table) and no extra signalling is required, just
signalling earlier.

The only case when LLNs add to the frequency of link state changes is
when (e.g. using SNR) you are marginal, and the link fluctuates good
and bad. But that's the point of the hysteresis (again, the precise
usage) to prevent such fluctuations.

In short, a properly configured use of suitable LLNs, in most
scenarios, accelerates link removal, it doesn't cause a significant
increase in the frequency of link loss (and similarly link formation).
If turning on LLNs is significantly adding to the rate, the nature of
the LLNs, and the hysteresis used, need careful examination.

Now, whether using LLNs or not, there will be link losses. And until
signalled, there will be transients in the consistency of routing
tables.
And that's what responsive (as we say in OLSRv2) HELLO and TC messages
are for, to ensure that those transients are short enough. (If the full
message interval is short enough, you don't need them, if it's too long,
you do - we make this cleaner in OLSRv2 with minimum intervals.)

(Of course there's also the well-known fisheye principle that says out
of date long distance information may be sufficient. This depends a lot
on your network density and other factors. It might mean that responsive
TC messages can have a smaller hop limit. Or it might not.)

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 12 Jun 2009 10:07:04 +0100

> According to the reference 6 in Lee's draft, on page 1217 figure 5a,
> majority of the loops are formed over "2-way". Instant TC messages

TC-message created Topology Tuples are also used for links from 1-hop
to 2-hop neighbours. There are good reasons for this in the steady state
(using MPRs - which is good because it makes willingness work properly).
But there may be an issue in the transient case where the 2-Hop Tuple
disappears but the Topology Tuple remains. Teco Boot has suggested a
modification to prevent this, and the OLSRv2 authors are considering it
(but a higher priority is to get NHDP finished).

---

From: Lars Landmark <[email-masked]>
Date: Fri, 12 Jun 2009 14:00:46 +0200

> (but a higher priority is to get NHDP finished).

I see, however this point out the importance of operating over similar link attributes, i.e. using links with different timeouts, within similar hop distance, causes different topology maps.  It does not mean that topology links are not to be used within the same scope as HELLO links, but they MUST share the link timeout.

>From the wired domain, it exist different proposals for loop preventions. One suggestion is not-via, which will not direct looping packets over this not-via address. A simple method, or a start, would be to route traffic, already involved in a loop, over an alternative next-hop node knowing to be reachable to the not-via address. This alternative node address may be retrieved from HELLO messages. I am not sure whether this would be a suggestion, but at least the packets are prevented from being discarded. 

A curios question, is the loop problem an OLSRv2 issue or does it also apply for OLSR? 

Regards
Lars

---

From: Henning Rogge <[email-masked]>
Date: Fri, 12 Jun 2009 14:08:04 +0200

> A curios question, is the loop problem an OLSRv2 issue or does it also
It does definitely also apply for OLSR.

Henning Rogge

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 12 Jun 2009 13:44:06 +0100

Am Freitag 12 Juni 2009 14:00:46 schrieb Lars Landmark:
>> A curios question, is the loop problem an OLSRv2 issue or does it
also
>> apply for OLSR?

Looping is a possibility with any decentralised routing
protocol (here, link state protocols) where topological
information can become transiently inconsistent.

I have however not seen anything that doesn't make me
believe the particular issues seen here of large problems
aren't the result of poor practices in use of link quality
and the failure to use responsive messages well.

---

From: jacquet <[email-masked]>
Date: Fri, 12 Jun 2009 15:21:11 +0200

Dear Lee,

It is still not clear if you properly simulate the instant TC. Instant 
hellos can only push loops one hop away the failed link but would not 
suppress them (unless the source is one hop away). What surprise me is 
this 10% loop reduction means 170 packet transmission less, and you 
assume it is still smaller than the instant hello overhead. Do you mean 
you attempt to send more than 170 instant hellos for the same LLN?

I think you may have a MAC issue if the first packet loop blocks the 
transmission of hellos. If this phenomenon is not a simulation artefact 
(look strange anyhow) then Chris proposal to send instant TC before 
clearing link in the local routing table may work well and suppress 
transient loops.

Loop Deduction mechanism would locally suppress loops but would not 
increase delivery rate (since packets don't reach destination). To make 
it working you must send the instant TC anyhow.

Best regards,
Philippe

Lee Speakman a écrit :
> Hello.  I establish in more detail and more precisely what we have 
> done before continuing.
>
> The problem of looping is observed to occur where there are higher 
> loads in the network, in our case with multiple flows crisscrossing 
> the network.
> If, on an event, we send just one Instant Hello, then in such cases, 
> due to already circling packets around loops, there is a lesser 
> probability that surrounding nodes will be able to successfully 
> receive the Instant Hello compared to when there is little traffic in 
> the network.
>
> acknowledgements from attempting to forward a unicast packet) made 
> very little difference in the PDR (end-to-end delivery) and the number 
> of loops which we were measuring at that time, regardless of if the 
> packet was scheduled immediately, or using the full jitter interval or 
> a fraction of it.  There were only minor improvements in PDR of a few 
> To see if the cause was due to the Instant Hello not being received, 
> we scheduled multiple Hellos, this reduced the number of loops further 
> also increased the overhead.  For that simulation with multiple 
> Instant Hellos in short succession this is where we could get around 
> ~10% of the loops dissolved, but at the cost of the overhead 
> increasing as we increased the number of loops, thereby countering any 
> gains from the reduced number of loops.
>
> ~90% of the loops the loop comes about from an incoherent perception 
> of the network between adjacent nodes through their Topology Sets and 
> so cannot be fixes with an Instant Hello, and that the effect of an 
> LLN cutting a link that is unphysical is often to cause a change such 
> that a loop appears not only one link away (an adjacent link), but 
> also two links or more away from the lost link.
>
> After studying various packet traces and all nodes Link Set and 
> Topology Sets to find out why we could never dissolve more than ~10% 
> of loops in this particularly scenario, we found that the majority of 
> loops are more than one link-hop away from where the LLN is occur.  
> The node in which an LLN occurs from dropping a unicast packet only 
> selects a new route (after removal of that link), forwarding it along 
> a different path, and further in that path a loop occurs.
>
>
> At almost no load, a control packet is on average received by 17.5 
> nodes (more in the center, less on the edges), but at a load of 8 apps 
> this is down to just over 16 nodes.  This is worse at the time a 
> transient looping packet is existing.
>
> (Packet Discard), bringing the PDR up to ~94.5%, and better 
> improvements by cutting the link over which a looping packet is 
> detected (Link Cut), bringing the PDR up to ~96%.
>
>
> At almost no load, a control packet is on average received by 17.5 
> nodes (more in the center, less on the edges), but at a load of 12 
> apps this is down to less than 15 nodes.  This is worse at the time a 
> transient looping packet is existing.
>
> Simply discarding the observed looping packets and the improvement 
> that has on PDR shows the negative effects of looping packets on 
> surrounding traffic.
>
>

---

From: Henning Rogge <[email-masked]>
Date: Fri, 12 Jun 2009 15:16:16 +0200

Am Freitag 12 Juni 2009 14:44:06 schrieb Dearlove, Christopher (UK):
>>> also apply for OLSR?
Yes.

> and the failure to use responsive messages well.
The problem with big networks is that you have choose a tradeoff between 
network resources and responsiveness of the network.

Henning

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 12 Jun 2009 14:22:03 +0100

> network resources and responsiveness of the network.

Indeed. And there's a special case of fisheye - or similarly HSLS
- that makes an additional tradeoff of short and long distance
responsiveness. And no doubt others.

But the specific issue discussed here was about how use of
link quality in OLSR impacts on this. And that isn't adding up.

---

From: "Hokelek, Ibrahim" <[email-masked]>
Date: Fri, 12 Jun 2009 11:27:42 -0400

>From the wired domain, it exist different proposals for loop preventions. One suggestion is not-via, which will >not direct looping packets over this not-via address. A simple method, or a start, would be to route traffic,
>already involved in a loop, over an alternative next-hop node knowing to be reachable to the not-via address. >This alternative node address may be retrieved from HELLO messages. I am not sure whether this would be a >suggestion, but at least the packets are prevented from being discarded.

>A curios question, is the loop problem an OLSRv2 issue or does it also apply for OLSR?

When a link is decided as "failed" by a failure detection mechanism running at the local node (using hello loss mechanism, LLN, or any other), ideally the nodes affected from this topology change should update their Routing Tables (RTs) as fast as possible in order to prevent any micro-looping issue due to this link failure or minimize its effects. It is essential to send the failure information to the nodes affected from this failure immediately (other nodes can get this info later). The fast convergence to new RTs can be achieved using Fast Reroute techniques which usually pre-compute loop-free alternative paths (LFAPs) for anticipated topology changes. However, the requirements of a fast reroute technique in MANETs are different than the wired network, where, i) overhead should be minimal, ii) more frequent failures (specifically multiple simultaneous failures) should be handled, iii) transient failures need to be handled carefully (e.g., link flapping case).

There is a clearly benefit of detecting a link failure earlier using link layer information for the case where the link is really failed, however how to use this information in order to get the maximum benefit requires further thoughts.

Regards,
Ibrahim

---

From: Richard Ogier <[email-masked]>
Date: Fri, 12 Jun 2009 10:50:14 -0700

>information can become transiently inconsistent.

Sure, but there exist MANET protocols where topological (or distance)
information never becomes inconsistent. For example, the paper by
Perkins and Bhagwat states "At all instants, the DSDV protocol
guarantees loop-free paths to each destination."
Also, I believe TBRPF will avoid loops with a small modification: the
removal of the following feature summarized in Section 5.2 of RFC 3684:
"To allow immediate rerouting, the restriction that each link (u,v) in
TG must be reported by p(u) is relaxed temporarily if p(u) changes to
a neighbor that is not reporting the link."
(It is not known how this modification would affect performance, but
the point is there are ways to avoid all routing loops.)

It is possible that most (or many) of the loops observed by Lee
are simply a result of unreliable TC flooding, which would occur
even if instant TC messages are sent. If a node several hops from
the failed link does not receive the first TC message reporting
the failure, it may have to wait 5 or more seconds before receiving
the correct information.

As Philippe mentioned, instant TC messages need to be sent, and we
need to see how much this reduces looping. I think that if an
instant hello is sent, then an instant TC should also be sent
if the failed link was a topology tuple. In this case, there
should be no need to validate a topology tuple based on the
2-hop set.

Richard