Subject: [manet] OLSR2 - Routing Set Updates

From: Saulo Jorge Queiroz <[email-masked]>
Date: Fri, 3 Apr 2009 09:26:29 -0400

Hello,

I've worked on algorithms for maintaining Routing Set in OLSR.  Could anyone
clarify if a change of the known symmetric links and/or attached networks
necessarily changes the routing set?

-- 
Saulo Jorge bq
-
“Os maus de coração não amam nunca; apenas se alegram entre comparsas"
-- Caio Fábio

---

From: Jens de Smit <[email-masked]>
Date: Fri, 3 Apr 2009 15:35:59 +0200

> necessarily changes the routing set?

Well.... That actually depends on your algorithm, doesn't it? But,
unless your algorithm selects each and every node as router, there's
always a topology where the loss of 1 link does not require the
routing set to change to keep the network connected.

Regards,

Jens

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Fri, 3 Apr 2009 14:40:01 +0100

I think the summary (and we're open to changing the exact wording here
if appropriate) of the situation would be
 
- Any change to anything that goes into the Routing Set (including the cases
  you note) has the potential to change the Routing Set.
 
- You ought to keep the Routing Set up to date. (Of course there may be
  quality of implementation issues - do I allow a slightly longer than necessary
  delay in which it's out of date, and if so how long?)
 
- If this means you have to recalculate the Routing Set, so be it. But if (for
  whatever reason) you can patch the set without recalculating it, so much the
  better. If you've got any particularly good ways to do so, please share them
  with us.
 
- The specification talks in terms of recalculating the Routing Set any time
  something changes, because that's a convenient way to specify the protocol..
  But there's also a blanket "as if" that means you don't have to do it that way
  (in fact you don't even have to have a Routing Set in exactly that form).
 
- The Routing Set (and the set of MPRs) also have an additional freedom -
  while there's a suggested how to do it algorithm, the actual specification
  is anything that gives minimum path routes given the specified Topology
  Graph. So there's another permission to do what works for you.
 
- But don't lose sight of that if you try using outdated routes, for as long as
  you do, you will risk looping in the network, and that's not a good thing.

-- 
Christopher Dearlove
Technology Leader, Communications Group
Networks, Security and Information Systems Department
BAE Systems Advanced Technology Centre
West Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194  Fax: +44 1245 242124

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87,
Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK
Registered in England & Wales No: 1996687

________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf Of Saulo Jorge Queiroz
Sent: 03 April 2009 14:26
To: [email-masked]
Subject: [manet] OLSR2 - Routing Set Updates

*** 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,

I've worked on algorithms for maintaining Routing Set in OLSR.  Could anyone clarify if a change of the known symmetric links and/or attached networks necessarily changes the routing set?

-- 
Saulo Jorge bq
-
"Os maus de coração não amam nunca; apenas se alegram entre comparsas"
-- Caio Fábio

********************************************************************
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: Fri, 3 Apr 2009 14:44:29 +0100

> routing set to change to keep the network connected.

That would be a special case (and quite likely a good one) of
the case of only needing to patch the Routing Set when necessary.
Link not used, patch is trivial.

I can see at least two ways to do that - neither of which I'm
claiming is particularly good. One would be to augment to Routing
Tuples to retain the whole path used in each case. Amother would
be to put a flag next to all links which are used when calculating
the Routing Set (and no others). If a flagless link breaks, no
need to recalculate the Routing Set.

---

From: Saulo Jorge Queiroz <[email-masked]>
Date: Fri, 3 Apr 2009 10:50:34 -0400

The Ramalingan and Reps algorithm (and any one based on Bounded Incremental
Computation Model) defines a dag Gd=(V,A') from the graph G=(V,A) in such a
way that A' has all edges which belongs to current known shortest paths.

For every new edge information  the Topology of graph G is necessarily
updated but info about SPTree (pi[v] and d[v] for all v in G) and so, Gd,
are updated only if edge inserted / deleted / updated (weight) belongs
(belonged) to Gd.  Once Gd is affected, the algorithm identify the set of
routers for which shortest paths must be recomputed and do it. The running
time is given in terms of delta (instead all |V|).

I think that routing set could be seen as Gd (i.e. the space complexity is
the same as in Dijkstra)

2009/4/3 Dearlove, Christopher (UK) <[email-masked]>

>  ------------------------------
> *From:* [email-masked] [mailto:[email-masked]] *On Behalf
> Of *Saulo Jorge Queiroz
> *Sent:* 03 April 2009 14:26
> *To:* [email-masked]
> *Subject:* [manet] OLSR2 - Routing Set Updates
>
>   *** WARNING ***
>
> I've worked on algorithms for maintaining Routing Set in OLSR.  Could
> anyone clarify if a change of the known symmetric links and/or attached
> networks necessarily changes the routing set?
>
>
> --
> Saulo Jorge bq
> -

---

From: Saulo Jorge Queiroz <[email-masked]>
Date: Sat, 4 Apr 2009 08:27:34 -0400

2009/4/3 Jens de Smit <[email-masked]>

> anyone
> Well.... That actually depends on your algorithm, doesn't it?

Up to now, I think it depends on more of topology discovery configuration of
OLSR than SSP algorithm.  I performed several (time infinite-horizon)
simulations and noticed that  proportion of times routing table changed
could be  drammatically reduced by turnning MPR (RFC3626) off and by using
fish-eye algorithm (in comparison with RFC3626).

> But,

---

From: Saulo Jorge Queiroz <[email-masked]>
Date: Sun, 5 Apr 2009 12:22:55 -0400

An additional note:

'delta' is the set of routers whose shortest paths changed after one update
on the graph (i.e. delta is in V-{source}, and 0<=|delta|<= |V|-1).

2009/4/3 Saulo Jorge Queiroz <[email-masked]>