[CUWiN-Dev] hsls routing multihop

[David Young]

On Tue, Mar 01, 2005 at 01:24:33AM -0500, Gurung, Provin [IE] wrote:
> 
> I am having some multihop routing update problems with HSLS.

Provin,

A few questions:

How old are the sources you are using?  I have fixed a lot of bugs since
0.5.5 was released.  I urge you to update to the most up-to-date sources.
You may also find it useful to subscribe to our "cu-wireless-commits"
mailing list at lists.chambana.net.  You can use that list to track
changes to the sources.

Have you tried turning on debug messages?  I recommend it.  It will
really help you see what's happening.  The daemon is able to produce
reams of debug log messages.  You can control the messages that do and
do not get printed using the -L and -l options.  -l turns on a category
of debug message, and -L turns off a category.  Search the sources for
the regular expression _DEFN to find out the names of the "switches"
that turn a category on and off.  Since revision 2643 on the 2 Feb,
the switches are arranged in a tree.  Here is the description (terse,
sorry) I put into the log message:

        ------------------------------------------------------------------------
        r2643 | dyoung | 2005-02-02 23:55:53 -0600 (Wed, 02 Feb 2005) | 33 lines

        Introduce a new style of logging.  Now there is a hierarchy of
        log tri-state switches.  Switches that are lower in the hierarchy
        supercede superior switches:

        The state of a switch X is the state of the first switch on
        the path from X to the root of the tree that is in state 'on'
        or 'off'.  If every switch on the path is in the 'pass' state,
        then the state of switch X evaluates to 'off'.

        Here is an example tree:

                      all:off
                        / \
                       /   \
                      /     \
                     /       \
                    /         \
              spf_any:pass  peer_any:on
                  /   \          \
                 /     \          \
          spf_quiet:  spf_loud:  peer_quiet:
            on          pass       pass

        And the switches' state:

                all:            off
                spf_quiet:      on
                spf_loud:       off
                spf_any:        off
                peer_any:       on
                peer_quiet:     on

> Now if I revert back to the first configuration (i.e. one of multihop nodes)
> than the routing table never gets updated, i.e. routing table on X continues
> to show Z as directly connected, even though the routing table should have
> said that the node is reachable only through Y.

Make sure that a new adjacency is formed.  (Run with '-l peer_any' to
see the adjacencies come and go).

Regarding the deltas, you can see those with '-l spf_quiet'.

I will describe how deltas are computed.  I store the destination-nexthop
pairs for my forwarding table on a priority queue.  I label each dst-nhop
pair with its "generation number," N, and I sort the priority queue
using the tuples [N - N % 2, dst, nhop, N % 2] as keys.  Greater keys
have higher priority.  The generation number increases by two with every
SPF computation.  Say that the generation number is N before I begin a
new SPF computation.  As the SPF computation yields new dst-nhop pairs,
I label each with generation number N+1, and enqueue it.  When the SPF
computation completes, there are dst-nhop pairs labeled N and N+1 in
the queue.

I dequeue dst-nhop pairs until either the queue is empty or there is a
pair labeled N+2 at the head.  Identical dst-nhop pairs will be dequeued
consecutively.  If I dequeue a dst-nhop pair in generation N, and I had
not previously dequeued the same pair in N+1, then I delete the pair
from the forwarding table.  If I dequeue a dst-nhop pair in generation
N+1, and the next pair I dequeue is not in N, then I add the pair to
the forwarding table, and re-enqueue the pair with generation N+2.
If consecutive dst-nhop pairs are equal, then I re-enqueue one with
generation N+2, and I do not change the forwarding table.

> Btw I modified the HSLS to run on Linux, so I am not sure if the problem

That is good.  Porting should not affect the HSLS sources very much.
Mainly, changes should be confined to the socket library, I would think.

> One more question, In the HSLS document from BBN I think it mentioned that
> HSLS routes are not to be deleted if a node does not hear from its peers,
> but rather the increase the metrics to a high number. Does the HSLS
> implementation do that or does it just delete the routes?

I do not immediately delete a link if it is not 'UP'.  Do I set a very
high metric on the link?  No, I don't.  Thank you for finding my bug.
I have just committed a patch to the trunk that ought to fix it.

BTW, do you use the ETX metric?  That metric should increase quickly
with the loss of an adjacency.

Dave

-- 
David Young             OJC Technologies
dyoung at ojctech.com      Urbana, IL * (217) 278-3933