Subject: [manet] Packet looping issue in MANET routing protocol

From: "Yasunori Owada" <[email-masked]>
Date: Mon, 26 Nov 2007 17:41:01 +0900

Hello all,

We have implemented OLSRv2 routing protocol that can run on Linux
platform as daemon prosess and also run on QualNet simulator, and have
been checking the protocol operation and performance.
Through the real world experiments and simulation, we've found that
MANET routing protocol cannot solve the looping path issue completely.
The looping issue is acceralated when the Link Layer Notification is
enabled, and
much Looping occured with the proactive routing protocol such as OLSR
and OLSRv2 compare to the reactive routing protocol such as AODV. This
issue is caused form the node's network topology information
inconsistency (usually more than 2 hop information inconsistency) for
the proactive routing protocols.
Once the looping occures, the traffic load jump up localy, and total
network load incleases up to 20% in our simulation (50 nodes, random
way-point movement, 1500m squared area).
Unicast packet looping causes much traffic overhead because usually the
unicast frame is retransmitted by the MAC layer when the ack frame
doesn't come. This also leads large packet-delivery delay.
In addition, we found that most looping is formed between two nodes
(ping-poing looping).
Very few triangle loops are fouded, but more larger loops are not
found in our simulation.

Loop privention or avoidance is difficult issue considering unstable
wireless environment with multi-path fading and shadowing, but loop
detection is possible. It is expanding DPD technique to the unicast
packet. In this background we have submitted the initial I-D.
The draft can be found at:
http://www.ietf.org/internet-drafts/draft-mase-manet-loopdetect-00.txt

I think this looping issue should be widely discussed in the MANET WG.
Thanks,
--
Assistant Professor of Natural Hazard and Disaster Recovery, Niigata
University, Japan.
Yasunori Owada <[email-masked]>
TEL: +81-25-262-7429

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

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 26 Nov 2007 09:32:33 -0000

That Internet Draft says, in part

   The routing protocol may then act on the given LLN trigger, usually
   simply by removing a record of link from its Information Bases that
   store necessary information for routing and neighbor discovery to be
   able to calculate and update routing table.

That is not what either OLSR or OLSRv2 say to do. You do not simply
remove the entry from the information bases, you mark the entry in
the information bases, change its state, and report that state in
your HELLO messages, thus ensuring consistency. Furthermore they
both indicate that such a change may (actually, should, subject to
minimum message intervals in OLSRv2 - and some implementations of
OLSR) cause you to sent such a HELLO message early.

If implemented as described, you will have problems. But that would
be down to a poor implementation, not a fundamental problem with the
protocol.

********************************************************************
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: "Yasunori Owada" <[email-masked]>
Date: Mon, 26 Nov 2007 20:03:06 +0900

Hello Chris,

Thank you for comment.
We thought the same thing and we'd implemented instant HELLO
generation mechanisms as you mentioned into our OLSRv2 implementation.
But that could prevent only few ping-pong loops, and most loops had
remained.
This is because these loops are formed as a result of the Topology Set
information inconsistency, and the largest number of loops are caused
from this inconsistency.
TC message generation interval is longer than HELL's one, and TC
message is usually only forwarded by the MPR. Considering the
situation that link state changes frequently, MPR selector will be
changed frequently and some TC message may not be forwarded to entire
MANET node correctly. In addition, TC information inconsistency may be
caused by Topology Set timer expiration.
Instant TC message generation is one possibility to prevent this
looping issue, but it incleases control message overhead considerably.
So current solution is just discarding the looping packet.

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Mon, 26 Nov 2007 12:20:20 -0000

If you implement LLNs correctly, I do not see why
LLNs make a significant difference to the issue as
you suggest. Local changes occur on a short timescale
whether due to LLNs or other mechanisms. You do of
course have to have timescales appropriate to your
mobility.

As for sending TCs when things change, that also is
a SHOULD. Yes, it increases load, but the minimum
intervals in OLSRv2 (which we first implemented in
OLSRv1, see my paper at the first OLSR Interop) manage
that quite successfully in our experience.

For these and other reasons I therefore find these
results surprising, and not in keeping with results
we have seen in simulations (and reality, albeit in
smaller networks).

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Yasunori
Owada
Sent: 26 November 2007 11:03
To: Dearlove, Christopher (UK)
Cc: [email-masked]
Subject: Re: [manet] Packet looping issue in MANET routing protocol

               *** WARNING ***

This mail has originated outside your organization,
either from an external partner or the Global Internet. 
     Keep this in mind if you answer this message. 

Hello Chris,

Thank you for comment.

---

From: "Yangcheng Huang" <[email-masked]>
Date: Mon, 26 Nov 2007 17:23:55 +0000

The results are surprising to me. Just had a quick look at the source
code. From the following functions of LLN, ARP entries are used to
determine whether the link is valid or not.

ks2k_proc_lln
proc_link_layer_notification

///////
    if(ifp->now[i].diff > LLN_THRESHOLD){
      proc_link_layer_notification(olsr, ifp, ip);
      check =3D 1;
    }

The OLSR main program polls the system's ARP cache periodically to get
an up-to-date ARP table.

olsr_scheduler(void *ptr)
...
while(tmp_if) {
  get_arp_entry();
  //dump_arp_entry();
  ks2k_proc_lln(olsr, tmp_if);=20
...

So the problems might be caused by the ARP timeout value. By a simple
googling, the default ARP time out value for redhat seems to be 60s,
which will bring inconsistency when the node is in mobility.

Please feel free to correct me.

---

From: "Yasunori Owada" <[email-masked]>
Date: Tue, 27 Nov 2007 11:43:57 +0900

Hello Chris,

We created the packet tracer in QualNet simulator and find this issue.
Same loop could be found in OLSR without using LLN. LLN just
accelerate this looping issue, and the interesting things, much loop
is formed when nodes have no mobility.
In the simulation result, LLN surely improve the performance in terms
of packet delivery ratio. But it generate few loops as the
side-effect. Usually, these looping paths are updated and resolved
within a short period, but in the case that heavy traffic are
generated such as video streaming, many unicast packets may go into
the loop and keep forwarding until TTL expires (Usually 64 is used as
default TTL value in most operating system, so ONE packet is once
enter the loop, it is forwarded 63 times!). These packets only waste
the radio resources and should be discarded.

---

From: "Yasunori Owada" <[email-masked]>
Date: Tue, 27 Nov 2007 12:10:12 +0900

Hello Yangcheng,

Thank you for reviewing our implementation source code.
To implement LLN, we modified Wireless LAN device driver (for
Keystream Chipset wireless LAN card) to count the number of unicast
frame retransmission timeout in each destination MAC address. OLSRv2
Linux daemon poll the WLAN driver every polling interval and get the
list of MAC address and retransmission timeout count. When the
retransmission timeout count difference between previous one and
current one is larger than the LLN_THRESHOLD, then the link to the
destination MAC address assumes to be disconnected. ARP cash is used
for resolving the destination MAC address to IP address. If address
resolution from MAC address to IP address failed, LLN procedure
doesn't happen.
Unfortunately, current LLN implementation only works on the Keystream
Wireless LAN card with modified wireless LAN device driver. If someone
would implement LLN function that works on ar5k chipset wireless LAN
card with MAD-WiFi driver, it's a great help for us.
Thanks,

26 Nov 2007 17:07:14 +0000, Yangcheng Huang <[email-masked]>:
> The results are surprising to me. Just had a quick look at the source code.
> From the following functions of LLN, ARP entries are used to determine
> whether the link is valid or not.
>
> ks2k_proc_lln
>       check = 1;
> The OLSR main program polls the system's ARP cache periodically to get an
> up-to-date ARP table.
>
>           ks2k_proc_lln(olsr, tmp_if);
> ...
>
> googling, the default ARP time out value for redhat seems to be 60s, which
> brings inconsistency when the node is in mobility.
>
>
>
>
> On Nov 26 2007, Dearlove, Christopher (UK) wrote:
>

---

From: "Teco Boot" <[email-masked]>
Date: Tue, 27 Nov 2007 09:09:04 +0100

Hi,

I am interested in the relation between user traffic load and MANET micro
loops. 
I think in a heavily loaded MANET (many TCP flows), with some bad links,
probability on loops is increased and loop duration is typically longer. I
am interested in simulation results on this.

I am also interested in results when adding metrics. I think it can help
preventing loops, when updating metrics smoothly. The effect could be highly
dependent on the metrics update mechanism.

And I am also interested in effects on fish-eye routing, i.e. sending TC
with different hoplimits. I think long-lived loops could occur.   

I support putting effort on loop prevention, loop detection and looped
packet elimination in MANET WG.

Teco.

> -----Oorspronkelijk bericht-----
> Van: Yasunori Owada [mailto:[email-masked]]
> Verzonden: dinsdag 27 november 2007 3:44
> Aan: Dearlove, Christopher (UK)
> CC: [email-masked]
> Onderwerp: Re: [manet] Packet looping issue in MANET routing protocol
> 
> Hello Chris,
> 
> > >    store necessary information for routing and neighbor discovery
> to
> > be

---

From: Yang Cheng Huang <[email-masked]>
Date: Wed, 28 Nov 2007 00:01:38 +0000

>  When the
> destination MAC address assumes to be disconnected. 
>   
Any proof/mechanisms behind such a method? Why the DIFFERENCE between
the number of timeouts can indicate link status?

> ARP cash is used
My guess is the OLSR implementation doesn't make changes in the linux
ARP code. Each arp entry lasts 60s before timed-out. So the address
resolution would succeed even if the neighboring node moves away. The
data packets would get dropped if sent to such neighbors.

---

From: "Yasunori Owada" <[email-masked]>
Date: Wed, 28 Nov 2007 11:35:47 +0900

Comments inline.
> the number of timeouts can indicate link status?

First, we defined MAC frame retry-out as link disconnection because
IEEE802.11 ad-hoc mode doesn't define any link connection consept.
Then we implemented LLN based on this link sensing method in QualNet
simulator and evaluated its performance, and confirm that the packet
delivery performance improves well. To confirm these results in the
real world experiments, we also implement this function to the
wireless LAN device driver. But too many LLN occures in the real world
experiments because of the fading and shadowing. So that we also added
the LLN_THRESHOLD to reduce the LLN occurrence.

> data packets would get dropped if sent to such neighbors.

Our LLN detects such data pcakets loss in each nexthop. The MAC frame
retry-out means the data packet loss as you said. This mechanism don't
need any change to ARP code because this mechanism only uses ARP cache
entry to resolve reverse address resolution from MAC address to IP
address.

---

From: Bruce M Simpson <[email-masked]>
Date: Thu, 29 Nov 2007 00:03:29 +0000

> data packets would get dropped if sent to such neighbors.
This is largely expected -- layer 3 routing protocols should not be 
making changes to layer 2 state.

I'm thinking both ARP and IGMP should be optional in the kernel 
interface MIB for interfaces designated for MANET operation -- as they 
are of limited utility in the MANET scenario.

Whilst ARP could be used with MANET, and indeed currently is, most of 
the MANET protocols I've seen maintain host routes anyway, plumbing them 
into the Layer 3 FIB even when they aren't strictly needed or are 
already covered by interface routes, in the absence of any intermediary RIB.

Layer 2 mapping information could therefore be maintained e.g. using the 
HELLO packets which are part of OLSRv1, or as part of NHDP in OLSRv2 and 
DYMO.

regards,
BMS