On 09/30/2009 01:56 PM, Bruce Simpson wrote:
Ben Greear wrote:
The more I look, the weirder it seems..but I may be mis-interpreting
things.
It really takes some visualization to get through, I sat up with a good
book on graph theory to work it all out. "Introduction to Graph Theory"
by Trudeau is really good to have around.
Some of the naming in the RFC is counterintuitive. E.g. an MPR set is
the set of relays chosen by the local node, an MPR selector set is the
set of neighbours which choose the local node as a relay.
All of this is happening in near-real-time, or at least as close to real
time as you can get with the link state update quantization. So the
regression tests can sometimes fail on slow machines due to timer aliasing.
My regression tests are more horrible yet...I'm using 'real' routers :)
But, I'm not exhaustively checking that route propagating works properly
in all directions at this point.
The code looks quite tricky..and reading the pertinent subsection of
the RFC
is not helping too much.
No worries. I had to read it about 3 times incrementally before it sank
in, and even then I had what you might call a minor nervous breakdown.
Here's an attached patch that seems to fix things. I believe the main error
was checking for (!is_mpr()) in consider_remaining_cand_mprs
I can't see why that check helps anything, and it was excluding from
consideration the mpr
that was needed to find the 2-hop neighbor in my setup.
With the attached patch, no more crashes and routes seem to be propagating
properly,
though I haven't done a full verification of the (large amount of) routes.
Most of the patch is debugging, but since I fear I'll be visiting this again
someday, I'm leaving that in my tree...
Considering OLSR seems to be at least mostly working, maybe you could commit
the two patches I posted a few days ago that enables other ppl to build OLSR?
Thanks,
Ben
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
diff --git a/contrib/olsr/neighbor.cc b/contrib/olsr/neighbor.cc
index e13ae66..6f1a4bc 100644
--- a/contrib/olsr/neighbor.cc
+++ b/contrib/olsr/neighbor.cc
@@ -86,6 +86,13 @@ Neighbor::Neighbor(EventLoop& ev,
update_cand_mpr(false);
}
+string Neighbor::toStringBrief() {
+ ostringstream oss;
+ oss << id() << "-(" << main_addr().str() << ")";
+ return oss.str();
+}
+
+
OlsrTypes::NeighborType
Neighbor::neighbor_type() const
{
diff --git a/contrib/olsr/neighbor.hh b/contrib/olsr/neighbor.hh
index 46a9f41..8482366 100644
--- a/contrib/olsr/neighbor.hh
+++ b/contrib/olsr/neighbor.hh
@@ -77,6 +77,8 @@ class Neighbor {
inline const IPv4 main_addr() const { return _main_addr; }
+ string toStringBrief();
+
OlsrTypes::NeighborType neighbor_type() const;
/**
diff --git a/contrib/olsr/neighborhood.cc b/contrib/olsr/neighborhood.cc
index b57516c..882f7f2 100644
--- a/contrib/olsr/neighborhood.cc
+++ b/contrib/olsr/neighborhood.cc
@@ -1482,18 +1482,26 @@ Neighborhood::recount_mpr_set()
// 8.3.1, 1: Start with an MPR set made of all members of N with
// willingness equal to WILL_ALWAYS.
covered_n2_count += consider_persistent_cand_mprs();
+ //XLOG_WARNING("covered_n2_count after consider_persistent: %zi
reachable_n2_count: %zi\n",
+ // covered_n2_count, reachable_n2_count);
// 8.3.1, 3: If N2 is still not fully covered, ensure that for
// all uncovered strict N2 reachable only via 1 edge, their
// neighbor N is selected as an MPR.
- if (covered_n2_count < reachable_n2_count)
+ if (covered_n2_count < reachable_n2_count) {
covered_n2_count += consider_poorly_covered_twohops();
+ //XLOG_WARNING("covered_n2_count after consider_poorly_covered: %zi
reachable_n2_count: %zi\n",
+ // covered_n2_count, reachable_n2_count);
+ }
// 8.3.1, 4: If N2 is still not fully covered, consider
// candidate MPRs in descending order of willingness, reachability
// and degree.
- if (covered_n2_count < reachable_n2_count)
+ if (covered_n2_count < reachable_n2_count) {
consider_remaining_cand_mprs(reachable_n2_count, covered_n2_count);
+ //XLOG_WARNING("covered_n2_count after consider_remaining: %zi
reachable_n2_count: %zi\n",
+ // covered_n2_count, reachable_n2_count);
+ }
// Invariant: All reachable N2 must now be covered by MPRs.
XLOG_ASSERT(covered_n2_count >= reachable_n2_count);
@@ -1710,8 +1718,11 @@ Neighborhood::reset_twohop_mpr_state()
update_twohop_reachability(n2);
// If N2 is strict and is reachable, count it as a member of N2.
- if (n2->is_strict() && n2->is_reachable())
- n2_count++;
+ if (n2->is_strict() && n2->is_reachable()) {
+ //XLOG_WARNING("Counting 2-hop neighbor, is strict and reachable:
%i, n2: %s",
+ // n2->reachability(), n2->toStringBrief().c_str());
+ n2_count++;
+ }
}
return n2_count;
@@ -1817,8 +1828,13 @@ Neighborhood::consider_persistent_cand_mprs()
XLOG_ASSERT(n->is_mpr());
n2->add_covering_mpr(n->id());
+ //XLOG_WARNING("Covered n2: %s in consider_persistent.",
n2->toStringBrief().c_str());
covered_n2_count++;
}
+ else {
+ //XLOG_WARNING("NOT covering n2: %s in consider_persistent, strict:
%i n: %s n->willingness: %i",
+ // n2->toStringBrief().c_str(), n2->is_strict(),
n->toStringBrief().c_str(), n->willingness());
+ }
}
// The count may be 0 if the persistent MPRs have no 2-hop links.
@@ -1858,8 +1874,15 @@ Neighborhood::consider_poorly_covered_twohops()
//
n2->add_covering_mpr(n->id());
n->set_is_mpr(true);
+ //XLOG_WARNING("Counting poorly_covered n2: %s n is set as mpr:
%s",
+ // n2->toStringBrief().c_str(), n->toStringBrief().c_str());
covered_n2_count++;
}
+ else {
+ //XLOG_WARNING("NOT Counting poorly_covered n2: %s strict: %i
reachability: %i n2-covered: %i",
+ // n2->toStringBrief().c_str(), n2->is_strict(),
n2->reachability(),
+ // n2->is_covered());
+ }
}
return covered_n2_count;
@@ -1870,6 +1893,7 @@ Neighborhood::consider_remaining_cand_mprs(const size_t
n2_count,
size_t& covered_n2_count)
{
typedef set<Neighbor*, CandMprOrderPred> CandMprBag;
+ UNUSED(n2_count);
CandMprBag cand_mprs;
@@ -1878,8 +1902,8 @@ Neighborhood::consider_remaining_cand_mprs(const size_t
n2_count,
map<OlsrTypes::NeighborID, Neighbor*>::iterator ii;
for (ii = _neighbors.begin(); ii != _neighbors.end(); ii++) {
Neighbor* n = (*ii).second;
- if (! n->is_mpr() && n->is_cand_mpr() &&
- n->willingness() != OlsrTypes::WILL_ALWAYS) {
+ if (n->is_cand_mpr() &&
+ (n->willingness() != OlsrTypes::WILL_ALWAYS)) {
// 8.4.1, 4.1:
// Recompute n's reachability. We cannot amortize or
// distribute this computation as it depends on the
@@ -1892,6 +1916,10 @@ Neighborhood::consider_remaining_cand_mprs(const size_t
n2_count,
if (n->reachability() > 0)
cand_mprs.insert(n); // Insertion sort.
}
+ else {
+ //XLOG_WARNING("Not using n: %s as cand_mpr, willingness: %i
is_cand_mpr: %i is_mpr: %i\n",
+ // n->toStringBrief().c_str(), n->willingness(),
n->is_cand_mpr(), n->is_mpr());
+ }
}
// 8.3.1, 4.2: Select as an MPR the node with highest
@@ -1900,9 +1928,14 @@ Neighborhood::consider_remaining_cand_mprs(const size_t
n2_count,
for (jj = cand_mprs.begin(); jj != cand_mprs.end(); jj++) {
Neighbor* n = (*jj);
+ //XLOG_WARNING("Checking neighbour: %s link count: %zi\n",
+ // n->toStringBrief().c_str(), n->twohop_links().size());
+
// If all N2 are covered, we're done.
- if (covered_n2_count >= n2_count)
- break;
+ // How do you know you haven't counted duplicates?? Comments indicate
that redundant
+ // MPRs will be cleaned up below.... --Ben
+ //if (covered_n2_count >= n2_count)
+ // break;
// Mark each N2 reachable from this N as covered,
// and mark this N as a candidate MPR.
@@ -1914,10 +1947,15 @@ Neighborhood::consider_remaining_cand_mprs(const size_t
n2_count,
TwoHopNeighbor* n2 = l2->destination();
if (n2->is_strict()) {
// Mark this strict N2 as covered by N. Mark N as MPR.
+ //XLOG_WARNING("Adding covering_mpr: %s to n2: %s\n",
+ // n->toStringBrief().c_str(),
n2->toStringBrief().c_str());
n2->add_covering_mpr(n->id());
n->set_is_mpr(true);
covered_n2_count++;
}
+ else {
+ //XLOG_WARNING("n2: %s is strict, skipping.",
n2->toStringBrief().c_str());
+ }
}
}
}
diff --git a/contrib/olsr/twohop.cc b/contrib/olsr/twohop.cc
index 84930e1..3c2580f 100644
--- a/contrib/olsr/twohop.cc
+++ b/contrib/olsr/twohop.cc
@@ -53,6 +53,13 @@ TwoHopNeighbor::TwoHopNeighbor(EventLoop& ev, Neighborhood*
parent,
add_twohop_link(tlid);
}
+string TwoHopNeighbor::toStringBrief() {
+ ostringstream oss;
+ oss << id() << "-(" << main_addr().str() << ")";
+ return oss.str();
+}
+
+
void
TwoHopNeighbor::add_twohop_link(const OlsrTypes::TwoHopLinkID tlid)
{
diff --git a/contrib/olsr/twohop.hh b/contrib/olsr/twohop.hh
index 62b39b8..6346de9 100644
--- a/contrib/olsr/twohop.hh
+++ b/contrib/olsr/twohop.hh
@@ -45,6 +45,8 @@ class TwoHopNeighbor {
inline OlsrTypes::TwoHopNodeID id() const { return _id; }
inline IPv4 main_addr() const { return _main_addr; }
+ string toStringBrief();
+
/**
* Associate this N2 with an N1, using an instance of
* the association class TwoHopLink.
_______________________________________________
Xorp-hackers mailing list
[email protected]
http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers
