Subject: [manet] OLSR - link hysteresis questions

From: Andreas T <[email-masked]>
Date: Sat, 21 Feb 2004 00:57:07 +0100

Hi all,

I have just finished implementing link hysteresis in the UniK OLSR 
deamon. However - I have a couple of questions regarding my 
understanding of the described functioning(RFC3626 section 14).
The part I am uncertain of is the cases in which the "instability rule" 
should be applied. Section 14.3 states:
[QUOTE]
    The loss of OLSR packet is detected by tracking the missing Packet
    Sequence Numbers on a per interface basis and by "long period of
    silence" from a node.  A "long period of silence may be detected
    thus: if no OLSR packet has been received on interface I from
    interface NI during HELLO emission interval of interface NI (computed
    from the Htime field in the last HELLO message received from NI), a
    loss of an OLSR packet is detected.
{/QUOTE]

1. "a long periode of silence" implementation

I have implemented detection of "a long period of silence" in this way:
A link tuple records the following in addition to the fields specified 
in the RFC:

next_hello_timer - a timer describing withing what time a new HELLO 
should be received on this link.
last_htime - last recorded htime value from the neighbor(which this link 
connects us to).

Upon receiving a HELLO the next_hello_timer is set to now + received 
htime(+ some slack) and the last_htime is set to the received htime.

the link set is constantly checked for timed out entris with regards to 
the next_hello_timer. If a links next_hello_timer is timed out - a "long 
period of silence" is considered detected and the instabillity rule is 
applied to that links link_quality. The next_hello_timer is the set to 
now + last_htime to be able to detect another "long periode of silence".

I assume this is the correct way to do this? Or should this test not be 
"reset" once a long period of silence is detected?
Comments are appreciated.

2. Loss of packets

To detect a missing packet section 14.3 suggests checking "Packet 
Aequence numbers". This is the sequence number of the "generic OLSR 
packet header" - not any of the message sequence numbers.

The way I see it - this leads to a situation I am not sure hysteresis 
was intended to lead to:

Lets look at a situation with nodes A and B running OLSR with 
link-hysteresis using the proposed values(scaling=0.5, upper 
threshold=0.8 and lower threashold=0.8). We'll look at the situation fra 
As point of wiev:

- A has received a continues series of HELLO messages from B which has 
set As entry of B->L_link_quality to 0.99.

- A then misses out on ONE of Bs HELLO messages.
This leads to the instabillity rule beeing applied on As registered 
B->L_link_quality due to a detected "long periode of silence". As 
B->L-link_quality would now be ~0.5. This is not beneath the lower 
threshold so no change in link state is set.
But as soon as a receives the next HELLO message from B a missing 
package is detected due to the Packet Sequence Number of the received 
OLSR packet. So the instabillity rule is applied to B->L_link_quality 
again. This time it ends up at ~0.25 which is below the lower treshold 
so the link status is recalculated and the neighbor is set to be asymetric.
Ofcause B->L_link_quality is recalculated immedeatley since the 
stabillity rule is to be applied upon every received HELLO - but this 
will not bring the quality up above the upper treshold. Upon the next 
received HELLO(in sequence) the quality will be high enough for the 
status to be recalculated.

This means that missing out on _ONE_ HELLO packet causes a link(and 
therefore a neighbor if no other symmetric links to it exist) to be set 
to asymmetric and the MPR set and routingtable to be recalculated.

Is this the way hysteresis is supposed to work? Should seqno checking 
not be applied to links that have experienced a "long period of 
silience"? Or am I missing something here?

regards,
Andreas T

-- 

-- 
Andreas Tønnesen([email-masked])
UniK University Graduation Center
University of Oslo
http://www.olsr.org

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 26 Feb 2004 13:54:22 -0800

Hello David,

David Young wrote:

> My experience with the OSPF Hello protocol on 802.11b networks has been
> that it is not effective for link sensing.

Suppose we agree that link sensing is typically better done
using Hello messages, and that Hello messages should only
be used for links that do not offer any better mechanism.

Would that sound about right to you?

But then, doesn't it still mean that we ought to specify
Hello messages for links that don't offer any better mechanism?
And even if the determination can be made that the link is
active, or broken, we still might unicast a Hello message
to acquire the necessary layer-3 information.

Regards,
Charlie P.

---

From: "John Mullen" <[email-masked]>
Date: Thu, 26 Feb 2004 17:00:39 -0700

Hi Charles,

One problem is that received power is a stochastic function of distance,
etc., which means that successive packets can differ in signal strength
by 20 or 30 db.  In marginal areas, therefore, it is not possible to
determine link quality on the basis of a single reception.  Field tests
seem to indicate that some mechanism is needed to deal with the
stochastic nature of wireless links and Hello messages are one
possibility, but not the only one.  I would agree with your (corrected)
statement, but also point out that link unreliability is an issue that
will always bleed through to the MANET layer in some way.

Hi David,

Your interpretation may be right, but I suggest you look at a log of
RREQ and RREP packets.  A great deal of capacity is lost due to
occasional successes over unreliable links, causing unreliable routes to
be chosen, which then fail.  That is, there may be another cause for the
symptoms you describe.

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Charles E. Perkins
Sent: Thursday, February 26, 2004 2:54 PM
To: David Young
Cc: [email-masked]
Subject: Re: [manet] hello protocols inappropriate for link sensing?

Hello David,

David Young wrote:

> My experience with the OSPF Hello protocol on 802.11b networks has 
> been that it is not effective for link sensing.

Suppose we agree that link sensing is typically better done using Hello
messages, and that Hello messages should only be used for links that do
not offer any better mechanism.

But then, doesn't it still mean that we ought to specify
Hello messages for links that don't offer any better mechanism? And even
if the determination can be made that the link is active, or broken, we
still might unicast a Hello message to acquire the necessary layer-3
information.

Regards,
Charlie P.

---

From: ruchir sinha <[email-masked]>
Date: Thu, 26 Feb 2004 19:23:26 -0800 (PST)

Hi,
     Can anyone suggest the reason as to why DSR chooses a longer route sometimes in prefernece to existing shorter route....even if there is no break in nay of the links involved...i obseved this tendency of the DSR protocol while following the path followed by the protocol for a particular source destination pair.....
 
While one may understand the logic in switching to shorter path even without breaks i clearly don't see the justification in going for a longer path....something DSR does...in absence fo any link breaks....can anyone explain
 
Regards
Ruchir

David Young <[email-masked]> wrote:
The discussion of OLSR link hysteresis & OLSR hello protocol reminds me
of my misgivings about using hello protocols for link-sensing.

My experience with the OSPF Hello protocol on 802.11b networks has been
that it is not effective for link sensing. The multicast Hello packets
get "clobbered" (to use the technical term) by the unicast packets.
Routes are quite stable until the network sees prolonged unicast
traffic. For example, during an FTP download, hellos do not get through,
and OSPF detects that links are down in spite of their ability to bear
traffic. My network is static, so I "solved" the problem by raising the
OSPF Dead Interval. That is no solution for a mobile network.

Note that in my example, the FTP stream will produce ample evidence of
the link's bearing ability, if only OSPF will "eavesdrop" on it.

It will depend on the link layer whether or not hello messages help
fulfill the link-sensing role, so I question whether it is appropriate
for a layer-3 routing protocol to define link-sensing as a role for
the hello protocol. It seems that a layer-3 routing protocol should
define an abstract link-sensing module, only. A link-sensing module will
provide link indications (up/down, percentage BER/PER, S/N, "goodness")
to a routing module (OLSR, AODV, whatever). A routing module can assist
the link-sensing module by registering as a beacon-producing/expecting
agent. In Java-like pseudocode, the abstract interface might look
like this

abstract class link_sense_listener {
link_sense(neighbor, link_quality);
}

abstract class link_sense_module {
registration register_listener(link_sense_listener listener);
unregister_listener(registration r);
registration register_beacon(integer interval, integer jitter,
integer pkt_length, boolean does_produce,
boolean does_expect);
unregister_beacon(registration r);
}

class router extends link_sense_listener {

registration link_listen_registration, beacon_registration;

link_sense(neighbor n, link_quality q) {
/* update link database here */
}

router constructor(ip_address my_ip, integer hello_rate,
link_sense_module lm)
{
self.link_listen_registration =
lm.register_listener(self);
self.beacon_registration =
lm.register_beacon(hello_rate, .1 * hello_rate,
128, true, true);
}
}

Thoughts?

Dave

-- 
David Young OJC Technologies
[email-masked] Urbana, IL * (217) 278-3933

---------------------------------
Do you Yahoo!?
Get better spam protection with Yahoo! Mail

---

From: [email-masked]
Date: Fri, 27 Feb 2004 02:16:43 -0500

Why would you want a routing protocol to pick the shortest path (vs the best 
path)?

> 
> Hi,
>      Can anyone suggest the reason as to why DSR chooses a longer route
> sometimes in prefernece to existing shorter route....even if there is no
> break in nay of the links involved...i obseved this tendency of the DSR
> protocol while following the path followed by the protocol for a particular
> source destination pair.....
>  
> While one may understand the logic in switching to shorter path even without
> breaks i clearly don't see the justification in going for a longer
> path....something DSR does...in absence fo any link breaks....can anyone
> explain
>  
> Regards
> Ruchir
>

---

From: David Young <[email-masked]>
Date: Fri, 27 Feb 2004 22:01:50 -0600

> to acquire the necessary layer-3 information.

I think we are essentially agreed. I do not want to get rid of Hellos
altogether. I do think that it would be a good idea to relieve the
protocol and the link of the periodic hello-message burden, when both
a better link-sensing alternative exists, and periodic hello messages
serve no other purpose.

I see what you mean about unicasting Hellos.

Dave

---

From: David Young <[email-masked]>
Date: Fri, 27 Feb 2004 22:23:10 -0600

> be chosen, which then fail.  That is, there may be another cause for the

It is an OSPF network, but I know what you mean in the abstract about
RREQ/RREP succeeding over unreliable links.  The network in question
has no alternative routes, so I don't think that's the problem.

I am surprised if the RREQ/RREP packets' successes on marginal links
are only occasional.  I am interested to hear more about that. I have
pessimistically assumed that RREQ/RREP discovery frequently yields paths
that carry small RREQ/RREP packets fine, but which perform badly with
longish TCP segments.

Dave