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

From: Lee Speakman <[email-masked]>
Date: Tue, 26 May 2009 18:24:50 +0900

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.

To this end we put forward an Internet draft available in the following
link:

http://www.ietf.org/internet-drafts/draft-speakman-manet-looping-issue-00.txt

We'd be grateful for your consideration and input.

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

Kenichi Mase
Graduate School of Science and Technology, Niigata University, Japan

---

From: Ulrich Herberg <[email-masked]>
Date: Tue, 26 May 2009 13:45:26 +0200

Dear Lee,

I have some questions about your draft. Citing a part of Section 5:

<cite>
  The effect of this is to cause the Link Set in the node that has the
  LLN to change the link over which the packet was dropped from
  Symmetric to Lost ahead of the symmetric link timeouts between the
  nodes.  The surrounding nodes will still have knowledge of the
  existence of this link, and the link will still exist in the Topology
  Sets in the rest of the network for some time, possibly leading to
  the formation of a loop.
</cite>

Well, as soon as the link has been set to LOST by the LLN, a HELLO
will be triggered and the neighbors are informed that this link is
indeed lost. This is not different than using "plain" OLSRv2, only
that the time the link is advertized (even though it's already gone)
is reduced. I don't understand why that should speed up temporary
routing loop forming.

<cite>
 The effect of LLN is to ultimately speed
  the process by which a routing loop forms.  Node 3 or node 4 in
  Figure 1 may not have to wait for a full three times the Hello
  Interval before the Link Set changes its state from Symmetric.

  As LLN is triggered on the failure of a data packet to be forwarded
  over a link
</cite>

Probably, the LLN should not be triggered if only a single packet is
lost. Rather, decrease the Link Quality of that link using some sort
of "smooth" function as described in the OLSRv2 draft.

<cite>
  and the number of LLNs increases with the amount of
  traffic in the network, the number of routing loops also increases
  with the amount traffic in the network.
</cite>

Why is this a logical implication?

<cite>
  Furthermore, as LLN results
  in the removal of links at a rate over and above that by timeouts in
  'plain' OLSRv2, the total number of links in the network is further
  reduced thus increasing the average distance from any source to
  destination.
</cite>

The links that "plain" OLSRv2 keeps while they would be dropped when
using LLNs, are not "valid" any more. So in "plain" OLSRv2 packets
using such links would be dropped. Using LLN, the convergence time
will be decreased, so that a path from the source to the destination
can be recalculated faster.

<cite>
  A larger number of the packets remain in the network,
  taking a longer route, thus adding extra to the network load,
</cite>

While it is true there may be more packets in the network, the
statement "[they] take a longer route" is not really accurate. Without
LLN, the packets would have been dropped during the time OLSRv2 needs
to converge. You could say that this is a very short path -- right
away into the trash can ;-)

<cite>
  impacting the surrounding traffic within interference range of the
  loop, and further encouraging a higher chance of an LLN occurring in
  a node along the route supporting the traffic by collision.  The
  negative effect of increased packet looping caused by LLN works
  against the gains from avoiding dropping packets over broken links
  that plagues 'plain' OLSRv2. The negative effect as load increases
  may exceed the gains, thus causing a greater overall loss.
</cite>

Hmm, sorry, but I really don't understand how you would have more
loops by using L2 notifications. I am also running my own OLSRv2
implementation (JOLSRv2) with L2 notifications on Ns2, and I did not
experience loops. Maybe you could explain using your example, where
exactly you would have routing loops. My intuition is that using L2
notifications might even reduce the number of temporary loops, since
the convergence time is decreased.

Best regards,
Ulrich

On Tue, May 26, 2009 at 11:24 AM, Lee Speakman
<[email-masked]> wrote:
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet

---

From: Lee Speakman <[email-masked]>
Date: Thu, 28 May 2009 19:01:52 +0900

Dear Ulrich,

thank you for your comments, replies inline...

> is reduced. I don't understand why that should speed up temporary
Yes, the change of state is not different between plain OLSRv2 and 
OLSRv2 with LLN.
Only the time at which a link state may change to LOST under "plain" 
OLSRv2 is three times the Hello Period of the last received Hello Packet 
from the respective node, as opposed to OLSRv2 with LLN which may change 
the link state shortly after the link is established and confirmed by Hello.

The way the change of link state in the next Hello Packet is advertised 
is the same between the two.
As such, loops have been seen to form under "plain" OLSRv2, however, 
they are much fewer than the loops under OLSRv2-LLN.

In the paper [6] referred to in the draft, we consider a set time and 
explain how a loop forms naturally for a short "transient" time and then 
is naturally dissolved as the routing protocol  communicates the latest 
link state information with the rest of nodes in the network.
With LLN, the rate at which these transient routing loops are dissolved 
is not changed, however, the changes in link state occur much more 
frequently as it caused by the non-delivery of packets to the next hop.

> of "smooth" function as described in the OLSRv2 draft.
Even if the LLN is only triggered after dropping three consecutive 
packets forwarded at the network layer, the action of the LLN is to make 
link-state changes over and above the link-state changes that occur 
simply from links timing out after not receiving a Hello for some time.
For every link-state change that occurs in node, there is a likelihood 
that a routing loop will be created, which can only be corrected when 
the in-node link-state is advertised in its following control packets.

This document describes the routing loop and packet looping issues in 
mobile ad hoc network (MANET) running proactive routing protocols using 
hop count metric.

Using Link Hysteresis with OLSRv2 with the Link Quality based on the 
Hellos received, we have found improvement in performance upon OLSRv2, 
but not nearly as much as that provided by OLSRv2 with LLN with a Packet 
Discard on Looping Packet Detection, as OLSRv2 with LH (Link Hysteresis) 
still has the problem of forwarded packets over physically dead links.

Using a Path Metric may also help reduce the number of loops, but an 
accurate Path Metric takes time to create and is limited by node mobility.

> Why is this a logical implication?
An LLN only occurs on the failure of a unicast data packet to be 
forwarded from one node to the next.  If the traffic is increased, the 
likelihood of collisions and interference is also increased leading to 
the increased likelihood that a unicast data packet will fail to be 
forwarded to the next hop, thus leading to a LLN (after several attempts 
at forwarding) and a change of link-state of that link to LOST.

> can be recalculated faster.
Total convergence time is decreased as in OLSRv2 with LLN non-performing 
links are removed, but if the network is continually changing, perhaps 
due to mobility, a number of "convergences" are caused by LLNs removing 
non-performing links, in an equivalent period in which plain OLSRv2 
would simply have been forwarding the packet over the original 
non-performing link.

> away into the trash can ;-)
That's right, with plain OLSRv2, some of the perceived routes lead to 
packets being continually forwarded over a non-performing link for the 
duration of the existence of that link being Symmetric in the forwarding 
node's Link Set.

With LLN, it is observed that end-to-end delivered packets on average 
take a longer route, so this ignores these short routes which are 
incapable of delivering packets to the destination.

However we have seen another effect as given in the paper. The effect of 
transient looping packets is to increase the effective load on the 
network and in the medium, increasing the likelihood that this extra 
load will have collision with existing traffic, thus causing some of 
this surrounding traffic to be dropped, leading to LLNs and more links 
being removed from the link sets.  This results in slightly longer 
routes to the destination, also further leading to an increased 
effective load in the network.

> the convergence time is decreased.
We found, as given in figure 2, that LLN improves over "plain" OLSRv2, 
but as the load is increased, the number of routing loops increases and 
soon falls to below the performance (PDR) of plain OLSRv2.  The cause of 
this, as found by packet traces, was due to looping packets.  This was 
further confirmed by setting up a looping packet detection technique and 
discarding looping packets, which resulted in the PDR being 
significantly improved.  Simulations were performed in Qualnet 4 with 60 
nodes, The load was controlled by using CBR applications and changing 
the number of applications.

At very low loads there are no loops.  Less loops are also seen at 
higher node- or link-density.  But we still observe looping packets at 
moderate loads and link densities.

The example in section 4 and 5 of the draft is taken from the paper in 
[6] with the help of a time chart and there is another earlier example 
we expressed in the IEEE CQR Workshop, 2008.

In your simulation for increasing offered load do you find a much more 
rapidly decreasing performance in OLSRv2 with LLN over that for plain 
OLSRv2 similar to figure 2 in the draft?

Thanks for your comments.

Cheers,
   Lee -S-

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

Ref.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 29 May 2009 13:28:59 +0100

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

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.

********************************************************************
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: jacquet <[email-masked]>
Date: Fri, 29 May 2009 15:28:12 +0200

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: Henning Rogge <[email-masked]>
Date: Fri, 29 May 2009 15:54:03 +0200

> particularly at higher loads, the problem of looping packets become more
I would be interested in the radio model you used for your simulations.

Henning Rogge