Hello Ben /all
I have attached the modified file 'topology.cc' that contains the
changes I've made
in the attempt to make OLSR more stable. Unfortunately, there are still
problems
with the OLSR but at least we are one step closer.
Tested Topologies:
1) 9 nodes inline (wireless)
n9 - n8 - n7 - n6 - n1 - n2 - n3 - n4 - n5
2) 16 nodes, in 4x4 grid (wireless)
n1 - n2 - n3 - n4
n5 - n6 - n7 - n8
n9 - 10 - 11 - 12
13 - 14 - 15 - 16
where, N1 is nei with N2, n5, n6,
N2 is nei with n1,n3,n5,n6,n7
N3 is nei with N2,n4,n6,n7,n8
...
N16 is nei with n11, n12, n15.
Topology is stable however a ping from N1 to N16 may not
take the shortest path
(n1-n6-n11-n16) which is 3 hops. Instead, it may follow
path from N1-N2-N7-N12-N16 (4-hops?).
When I re-issue the ping many times, it may take a
different paths.
3) Mobility test: 9 nodes inline (as above).
When moving N9 from N8 to N7 until we get
N9
|
N8 - N7 - N6 - N1 ...
In this case, OLSR asserts.
These are some of the scenarios I used to find the bugs. However, I was
pulled off
this work and assigned something else. I just thought I would contribute
my findings
if anyone want to continue.
Phil.
--
Phil Hugg
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
// vim:set sts=4 ts=8 sw=4:
// Copyright (c) 2001-2009 XORP, Inc.
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, Version 2, June
// 1991 as published by the Free Software Foundation. Redistribution
// and/or modification of this program under the terms of any other
// version of the GNU General Public License is not permitted.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
// see the GNU General Public License, Version 2, a copy of which can be
// found in the XORP LICENSE.gpl file.
//
// XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
// http://xorp.net
#include "olsr_module.h"
#include "libxorp/xorp.h"
#include "libxorp/debug.h"
#include "libxorp/xlog.h"
#include "libxorp/callback.hh"
#include "libxorp/ipv4.hh"
#include "libxorp/ipv4net.hh"
#include "libxorp/status_codes.h"
#include "libxorp/service.hh"
#include "libxorp/eventloop.hh"
// #define DEBUG_LOGGING
// #define DEBUG_FUNCTION_NAME
// #define DETAILED_DEBUG
#include "olsr.hh"
#include "link.hh"
#include "neighbor.hh"
#include "neighborhood.hh"
#include "topology.hh"
TopologyManager::TopologyManager(Olsr& olsr, EventLoop& eventloop,
FaceManager& fm, Neighborhood& nh)
: _olsr(olsr),
_eventloop(eventloop),
_fm(fm),
_nh(nh),
_rm(0),
_next_mid_id(1),
_next_tcid(1)
{
_nh.set_topology_manager(this);
_fm.add_message_cb(callback(this,
&TopologyManager::event_receive_tc));
_fm.add_message_cb(callback(this,
&TopologyManager::event_receive_mid));
}
TopologyManager::~TopologyManager()
{
_fm.delete_message_cb(callback(this,
&TopologyManager::event_receive_tc));
_fm.delete_message_cb(callback(this,
&TopologyManager::event_receive_mid));
clear_tc_entries();
clear_mid_entries();
XLOG_ASSERT(_topology.empty());
XLOG_ASSERT(_mids.empty());
}
/*
* TC entries.
*/
void
TopologyManager::update_tc_entry(const IPv4& dest_addr,
const IPv4& origin_addr,
const uint16_t distance,
const uint16_t ansn,
const TimeVal& vtime,
bool& is_created)
throw(BadTopologyEntry)
{
debug_msg("DestAddr %s OriginAddr %s Distance %u ANSN %u Expiry %s\n",
cstring(dest_addr),
cstring(origin_addr),
XORP_UINT_CAST(distance),
XORP_UINT_CAST(ansn),
cstring(vtime));
OlsrTypes::TopologyID tcid;
bool is_found = false;
TcDestMap::iterator ii = _tc_destinations.find(dest_addr);
for (; ii != _tc_destinations.end(); ii++) {
tcid = (*ii).second;
if (_topology[tcid]->destination() == dest_addr &&
_topology[tcid]->lasthop() == origin_addr) {
is_found = true;
break;
}
}
TimeVal now;
_eventloop.current_time(now);
if (is_found) {
TopologyEntry* tc = _topology[tcid];
// 9.5, 4.1: Update holding time of the existing tuple in the
// topology set.
tc->update_timer(vtime);
// Update the distance of this TC entry, as the hop-count may
// have changed due to other changes in topology.
update_tc_distance(tc, distance);
} else {
// 9.5, 4.2: Record a new tuple in the topology set.
// May throw BadTopologyEntry exception.
tcid = add_tc_entry(dest_addr, origin_addr, distance, ansn, vtime);
debug_msg("%s: Added TC entry %u.\n",
cstring(_fm.get_main_addr()),
XORP_UINT_CAST(tcid));
}
is_created = !is_found;
}
OlsrTypes::TopologyID
TopologyManager::add_tc_entry(const IPv4& dest_addr,
const IPv4& origin_addr,
const uint16_t distance,
const uint16_t ansn,
const TimeVal& expiry_time)
throw(BadTopologyEntry)
{
debug_msg("DestAddr %s OriginAddr %s Distance %u ANSN %u Expiry %s\n",
cstring(dest_addr),
cstring(origin_addr),
XORP_UINT_CAST(distance),
XORP_UINT_CAST(ansn),
cstring(expiry_time));
OlsrTypes::TopologyID tcid = _next_tcid++;
// Throw an exception if we overflowed the TopologyID space.
if (0 != _topology.count(tcid)) {
xorp_throw(BadTopologyEntry,
c_format("Mapping for TopologyID %u already exists",
XORP_UINT_CAST(tcid)));
}
_topology[tcid] = new TopologyEntry(_eventloop, this, tcid,
dest_addr, origin_addr,
distance, ansn, expiry_time);
// Add the new link to the multimaps.
_tc_distances.insert(make_pair(distance, tcid));
_tc_destinations.insert(make_pair(dest_addr, tcid));
_tc_lasthops.insert(make_pair(origin_addr, tcid));
return tcid;
}
bool
TopologyManager::delete_tc_entry(const OlsrTypes::TopologyID tcid)
{
debug_msg("Tcid %u\n", XORP_UINT_CAST(tcid));
map<OlsrTypes::TopologyID, TopologyEntry*>::iterator ii =
_topology.find(tcid);
if (ii == _topology.end())
return false;
TopologyEntry* t = (*ii).second;
// Remove from destination map.
pair<TcDestMap::iterator, TcDestMap::iterator> ra =
_tc_destinations.equal_range(t->destination());
for (TcDestMap::iterator jj = ra.first; jj != ra.second; ) {
if ((*jj).second == tcid) {
_tc_destinations.erase(jj);
break;
}
jj++;
}
// Remove from lasthop map.
pair<TcLasthopMap::iterator, TcLasthopMap::iterator> rb =
_tc_lasthops.equal_range(t->lasthop());
for (TcLasthopMap::iterator kk = rb.first; kk != rb.second; ) {
if ((*kk).second == tcid) {
_tc_lasthops.erase(kk);
break;
}
kk++;
}
// Remove from distance map.
pair<TcDistanceMap::iterator, TcDistanceMap::iterator> rc =
_tc_distances.equal_range(t->distance());
for (TcDistanceMap::iterator ll = rc.first; ll != rc.second; ) {
if ((*ll).second == t->id()) {
_tc_distances.erase(ll);
break;
}
ll++;
}
// Remove from ID map.
_topology.erase(ii);
delete t;
// May be called from destructor.
if (_rm)
_rm->schedule_route_update();
return true;
}
// XXX: This is a definite candidate for a Boost multi_index container.
void
TopologyManager::clear_tc_entries()
{
while (! _topology.empty())
delete_tc_entry((*_topology.begin()).first);
}
bool
TopologyManager::apply_tc_ansn(const uint16_t ansn,
const IPv4& origin_addr)
{
debug_msg("ANSN %u Origin %s\n",
XORP_UINT_CAST(ansn),
cstring(origin_addr));
// The ANSN is regarded as valid until proven otherwise.
bool is_valid = true;
// Find the tuples, if any, recorded from the origin.
TcLasthopMap::iterator ii, jj;
ii = _tc_lasthops.find(origin_addr);
while (is_valid && ii != _tc_lasthops.end()) {
jj = ii++;
OlsrTypes::TopologyID tcid = (*jj).second;
if( (*jj).first == origin_addr && _topology[tcid]->seqno() != ansn ) {
// PRH Mar.18/11
if (is_seq_newer(_topology[tcid]->seqno(), ansn)) {
// 9.5, 2: If any tuple in the topology set has T_seq > ANSN,
// then the TC message was received out of order and MUST be
// silently discarded.
is_valid = false;
} else {
// 9.5, 3: All tuples in the topology set where T_seq < ANSN
// MUST be removed from the topology set.
delete_tc_entry(tcid);
}
} // PRH Mar.18/11
}
return is_valid;
}
OlsrTypes::TopologyID
TopologyManager::get_topologyid(const IPv4& dest_addr,
const IPv4& lasthop_addr)
throw(BadTopologyEntry)
{
debug_msg("DestAddr %s LasthopAddr %s\n",
cstring(dest_addr),
cstring(lasthop_addr));
bool is_found = false;
OlsrTypes::TopologyID tcid;
multimap<IPv4, OlsrTypes::TopologyID>::const_iterator ii =
_tc_destinations.find(dest_addr);
while (ii != _tc_destinations.end()) {
tcid = (*ii).second;
if (_topology[tcid]->lasthop() == lasthop_addr) {
is_found = true;
break;
}
ii++;
}
if (!is_found) {
xorp_throw(BadTopologyEntry,
c_format("No mapping for %s exists", cstring(dest_addr)));
}
return tcid;
}
const TopologyEntry*
TopologyManager::get_topology_entry_by_id(const OlsrTypes::TopologyID tcid)
const throw(BadTopologyEntry)
{
TcIdMap::const_iterator ii = _topology.find(tcid);
if (ii == _topology.end()) {
xorp_throw(BadTopologyEntry,
c_format("No mapping for %u exists", XORP_UINT_CAST(tcid)));
}
return (*ii).second;
}
void
TopologyManager::get_topology_list(list<OlsrTypes::TopologyID>& tclist) const
{
TcIdMap::const_iterator ii;
for (ii = _topology.begin(); ii != _topology.end(); ii++)
tclist.push_back((*ii).first);
}
vector<IPv4>
TopologyManager::get_tc_neighbor_set(const IPv4& origin_addr, uint16_t& ansn)
throw(BadTopologyEntry)
{
debug_msg("MyMainAddr %s Origin %s\n",
cstring(_fm.get_main_addr()),
cstring(origin_addr));
size_t found_tc_count = 0;
vector<IPv4> addrs;
pair<TcLasthopMap::iterator, TcLasthopMap::iterator> rl =
_tc_lasthops.equal_range(origin_addr);
for (TcLasthopMap::iterator ii = rl.first; ii != rl.second; ii++) {
TopologyEntry* t = _topology[(*ii).second];
XLOG_ASSERT(t != 0); // paranoia
// If this is the first match, record the ANSN.
if (ii == rl.first)
ansn = t->seqno();
#ifdef DETAILED_DEBUG
// Invariant: the ANSN of all entries for this peer must be the same.
XLOG_ASSERT(t->seqno() == ansn);
#endif
addrs.push_back(t->destination());
++found_tc_count;
}
if (found_tc_count == 0) {
// Check to see if this origin was recorded as having an empty
// neighbor set.
// OLSR nodes originating TC broadcasts MUST send an
// empty TC message with a new ANSN to invalidate any existing
// topology information when they stop being selected as MPRs.
TcFinalSeqMap::const_iterator ii = _tc_final_seqnos.find(origin_addr);
if (ii != _tc_final_seqnos.end()) {
ansn = (*ii).second;
debug_msg("%s: found final ansn %u for %s\n",
cstring(_fm.get_main_addr()),
XORP_UINT_CAST(ansn),
cstring(origin_addr));
return addrs;
}
// The origin is not known to TopologyManager.
// This is a distinct condition from "there were no entries
// for the given origin".
xorp_throw(BadTopologyEntry,
c_format("No mapping for %s exists", cstring(origin_addr)));
}
return addrs;
}
uint16_t
TopologyManager::get_tc_distance(const IPv4& origin_addr,
const IPv4& dest_addr)
throw(BadTopologyEntry)
{
debug_msg("MyMainAddr %s Origin %s Dest %s\n",
cstring(_fm.get_main_addr()),
cstring(origin_addr),
cstring(dest_addr));
bool is_found = false;
uint16_t distance = 0;
pair<TcLasthopMap::iterator, TcLasthopMap::iterator> rl =
_tc_lasthops.equal_range(origin_addr);
for (TcLasthopMap::iterator ii = rl.first; ii != rl.second; ii++) {
TopologyEntry* t = _topology[(*ii).second];
if (t->destination() == dest_addr) {
is_found = true;
distance = t->distance();
break;
}
}
if (! is_found) {
// No TC entry was found matching that origin and destination.
xorp_throw(BadTopologyEntry,
c_format("No mapping for (%s, %s) exists",
cstring(origin_addr),
cstring(dest_addr)));
}
return distance;
}
size_t
TopologyManager::get_tc_lasthop_count_by_dest(const IPv4& dest_addr)
{
debug_msg("MyMainAddr %s Dest %s\n",
cstring(_fm.get_main_addr()),
cstring(dest_addr));
size_t lasthop_count = 0;
pair<TcDestMap::iterator, TcDestMap::iterator> rl =
_tc_destinations.equal_range(dest_addr);
for (TcDestMap::iterator ii = rl.first; ii != rl.second; ii++) {
++lasthop_count;
}
return lasthop_count;
}
size_t
TopologyManager::tc_node_count() const
{
size_t unique_key_count = 0;
// Count the number of unique keys (main addresses) in the lasthop map.
TcLasthopMap::const_iterator ii;
for (ii = _tc_lasthops.begin();
ii != _tc_lasthops.end();
ii = _tc_lasthops.upper_bound((*ii).first))
{
unique_key_count++;
}
return unique_key_count;
}
void
TopologyManager::update_tc_distance(TopologyEntry* tc, uint16_t distance)
{
if (tc->distance() == distance)
return;
// If the TC entry is already recorded for this distance, remove it.
pair<TcDistanceMap::iterator, TcDistanceMap::iterator> range =
_tc_distances.equal_range(distance);
for (TcDistanceMap::iterator ii = range.first; ii != range.second; ) {
if ((*ii).second == tc->id()) {
_tc_distances.erase(ii);
break;
}
ii++;
}
// Update the TC's distance, and rewire it into the distance map.
tc->set_distance(distance);
_tc_distances.insert(make_pair(distance, tc->id()));
#ifdef DETAILED_DEBUG
// Invariant: the ID of the topology entry must appear once and
// only once in the distances map.
assert_tc_distance_is_unique(tc->id());
#endif
}
void
TopologyManager::assert_tc_distance_is_unique(const OlsrTypes::TopologyID tcid)
throw(BadTopologyEntry)
{
#ifdef DETAILED_DEBUG
size_t id_seen_count = 0;
multimap<uint16_t, OlsrTypes::TopologyID>::const_iterator ii;
for (ii = _tc_distances.begin(); ii != _tc_distances.end(); ii++) {
if (tcid == (*ii).second) {
id_seen_count++;
}
}
if (id_seen_count != 1) {
xorp_throw(BadTopologyEntry,
c_format("Duplicate TopologyID %u in _tc_distances: "
"appeared %u times.",
XORP_UINT_CAST(tcid),
XORP_UINT_CAST(id_seen_count)));
}
#else
UNUSED(tcid);
#endif // DETAILED_DEBUG
}
void
TopologyManager::assert_tc_ansn_is_identical(const IPv4& origin_addr)
throw(BadTopologyEntry)
{
#ifdef DETAILED_DEBUG
bool is_origin_found = false;
bool is_seq_match_failed = false;
uint16_t first_ansn = 0;
TopologyEntry* t = 0;
TcIdMap::const_iterator ii;
for (ii = _topology.begin(); ii != _topology.end(); ii++) {
t = (*ii).second;
if (t->lasthop() == origin_addr) {
if (! is_origin_found) {
// First match; record first sequence number seen
// for this origin.
first_ansn = t->seqno();
is_origin_found = true;
} else {
// We've seen at least one entry for this origin before.
// Do the sequence numbers match, is the ANSN consistent?
if (t->seqno() != first_ansn) {
is_seq_match_failed = true;
break;
}
}
}
}
if (is_origin_found && is_seq_match_failed) {
xorp_throw(BadTopologyEntry,
c_format("Inconsistent ANSN (%s, %s, %u) in TopologyID %u",
cstring(t->lasthop()),
cstring(t->destination()),
XORP_UINT_CAST(t->seqno()),
XORP_UINT_CAST(t->id())));
}
#else
UNUSED(origin_addr);
#endif
}
/*
* MID entries.
*/
void
TopologyManager::update_mid_entry(const IPv4& main_addr,
const IPv4& iface_addr,
const uint16_t distance,
const TimeVal& vtime,
bool& is_mid_created)
throw(BadMidEntry)
{
debug_msg("MyMainAddr %s MainAddr %s IfaceAddr %s Distance %u Vtime %s\n",
cstring(_fm.get_main_addr()),
cstring(main_addr),
cstring(iface_addr),
XORP_UINT_CAST(distance),
cstring(vtime));
is_mid_created = false;
// Do not add redundant MID entries.
if (main_addr == iface_addr) {
debug_msg("Rejecting MID entry from %s for its main address.\n",
cstring(main_addr));
XLOG_TRACE(_olsr.trace()._input_errors,
"Rejecting MID entry from %s for its main address.",
cstring(main_addr));
return;
}
bool is_found = false;
MidEntry* mie = 0;
// Look for MID entry's interface address in existing address map,
// given origin address.
pair<MidAddrMap::iterator, MidAddrMap::iterator> range =
_mid_addr.equal_range(main_addr);
for (MidAddrMap::iterator ii = range.first; ii != range.second; ii++) {
mie = _mids[(*ii).second];
if (mie->iface_addr() == iface_addr) {
is_found = true;
break;
}
}
if (is_found) {
// Section 5.4, 2.1: Update existing MID tuple.
mie->update_timer(vtime);
mie->set_distance(distance);
} else {
// Section 5.4, 2.2: Create new MID tuple.
add_mid_entry(main_addr, iface_addr, distance, vtime);
is_mid_created = true;
}
}
void
TopologyManager::add_mid_entry(const IPv4& main_addr,
const IPv4& iface_addr,
const uint16_t distance,
const TimeVal& vtime)
throw(BadMidEntry)
{
debug_msg("MyMainAddr %s MainAddr %s IfaceAddr %s Distance %u Vtime %s\n",
cstring(_fm.get_main_addr()),
cstring(main_addr),
cstring(iface_addr),
XORP_UINT_CAST(distance),
cstring(vtime));
// Section 5.4, 2.2: Create new MID tuple.
OlsrTypes::MidEntryID mid_id = _next_mid_id++;
// Throw an exception if we overflow the MID ID space.
if (0 != _mids.count(mid_id)) {
xorp_throw(BadMidEntry,
c_format("Mapping for %u already exists",
XORP_UINT_CAST(mid_id)));
}
_mids[mid_id] = new MidEntry(_eventloop, this, mid_id, iface_addr,
main_addr, distance, vtime);
// Tot up another MID entry for this main address and MID entry combo.
_mid_addr.insert(make_pair(main_addr, mid_id));
debug_msg("new MidEntryID %u\n", XORP_UINT_CAST(mid_id));
}
bool
TopologyManager::delete_mid_entry(const OlsrTypes::MidEntryID mid_id)
{
debug_msg("MyMainAddr %s MidEntryID %u\n",
cstring(_fm.get_main_addr()),
XORP_UINT_CAST(mid_id));
bool is_deleted = false;
map<OlsrTypes::MidEntryID, MidEntry*>::iterator ii = _mids.find(mid_id);
if (ii != _mids.end()) {
MidEntry* mie = (*ii).second;
// Withdraw mid_id from multimap of MID IDs per primary address.
pair<MidAddrMap::iterator, MidAddrMap::iterator> range =
_mid_addr.equal_range(mie->main_addr());
for (MidAddrMap::iterator jj = range.first; jj != range.second; jj++) {
if ((*jj).second == mid_id) {
// Only the first match by ID should be deleted.
// Duplicates of the second key, mid_id, SHOULD NOT exist.
_mid_addr.erase(jj);
break;
}
}
delete mie;
_mids.erase(ii);
is_deleted = true;
debug_msg("MidEntryID %u was deleted.\n", XORP_UINT_CAST(mid_id));
}
if (is_deleted) {
// If any MID address entry was deleted, schedule a route
// computation.
// TODO: Find a way of optimizing the processing of MID entries
// in this way, we should just be able to withdraw the MID-derived
// routes for this entry in the routing table.
if (_rm)
_rm->schedule_route_update();
}
return is_deleted;
}
void
TopologyManager::clear_mid_entries()
{
map<OlsrTypes::MidEntryID, MidEntry*>::iterator ii, jj;
for (ii = _mids.begin(); ii != _mids.end(); ) {
jj = ii++;
delete (*jj).second;
_mids.erase(jj);
}
}
vector<IPv4>
TopologyManager::get_mid_addresses(const IPv4& main_addr)
{
#if 0
debug_msg("%s MyMainAddr %s MainAddr %s\n",
__func__,
cstring(_fm.get_main_addr())
cstring(main_addr));
#endif
vector<IPv4> addrs;
pair<MidAddrMap::const_iterator, MidAddrMap::const_iterator> range =
_mid_addr.equal_range(main_addr);
MidAddrMap::const_iterator ii;
for (ii = range.first; ii != range.second; ii++) {
MidEntry* mie = _mids[(*ii).second];
addrs.push_back(mie->iface_addr());
}
return addrs;
}
// Only used by regression tests.
uint16_t
TopologyManager::get_mid_address_distance(const IPv4& main_addr,
const IPv4& iface_addr)
throw(BadMidEntry)
{
debug_msg("MyMainAddr %s MainAddr %s IfaceAddr %s\n",
cstring(_fm.get_main_addr()),
cstring(main_addr),
cstring(iface_addr));
bool is_found = false;
MidEntry* mie = 0;
// Look up all matching interface addresses for main_addr,
// and find the single matching MidEntry.
pair<MidAddrMap::const_iterator, MidAddrMap::const_iterator> range =
_mid_addr.equal_range(main_addr);
MidAddrMap::const_iterator ii;
for (ii = range.first; ii != range.second; ii++) {
mie = _mids[(*ii).second];
if (mie->iface_addr() == iface_addr) {
is_found = true;
break;
}
}
if (! is_found) {
xorp_throw(BadMidEntry,
c_format("No mapping for (%s, %s) exists",
cstring(main_addr),
cstring(iface_addr)));
}
return mie->distance();
}
IPv4
TopologyManager::get_main_addr_of_mid(const IPv4& mid_addr)
throw(BadMidEntry)
{
MidEntry* mie = 0;
bool is_found = false;
map<OlsrTypes::MidEntryID, MidEntry*>::const_iterator ii;
for (ii = _mids.begin(); ii != _mids.end(); ii++) {
mie = (*ii).second;
if (mie->iface_addr() == mid_addr) {
is_found = true;
break;
}
}
if (!is_found) {
xorp_throw(BadMidEntry,
c_format("No mapping for %s exists", cstring(mid_addr)));
}
return mie->main_addr();
}
size_t
TopologyManager::mid_node_count() const
{
size_t unique_key_count = 0;
// Count the number of unique keys (main addresses) in the multimap.
multimap<IPv4, OlsrTypes::MidEntryID>::const_iterator ii;
for (ii = _mid_addr.begin();
ii != _mid_addr.end();
ii = _mid_addr.upper_bound((*ii).first))
{
unique_key_count++;
}
return unique_key_count;
}
const MidEntry*
TopologyManager::get_mid_entry_by_id(const OlsrTypes::MidEntryID midid) const
throw(BadTopologyEntry)
{
MidIdMap::const_iterator ii = _mids.find(midid);
if (ii == _mids.end()) {
xorp_throw(BadMidEntry,
c_format("No mapping for %u exists",
XORP_UINT_CAST(midid)));
}
return (*ii).second;
}
void
TopologyManager::get_mid_list(list<OlsrTypes::MidEntryID>& midlist) const
{
MidIdMap::const_iterator ii;
for (ii = _mids.begin(); ii != _mids.end(); ii++)
midlist.push_back((*ii).first);
}
/*
* RouteManager interaction.
*/
void
TopologyManager::push_topology()
{
size_t tc_link_added_count = 0;
XLOG_ASSERT(_rm != 0);
// For all entries at each recorded radius in the topology set.
TcDistanceMap::const_iterator ii, jj;
for (ii = _tc_distances.begin(); ii != _tc_distances.end(); ) {
// Look up the range of TC entries at the current radius.
uint16_t hops = (*ii).first;
// The following is equivalent to _tc_distances.upper_bound(hops);
// equal_range() has a more efficient expansion.
pair<TcDistanceMap::const_iterator,
TcDistanceMap::const_iterator> rd =
_tc_distances.equal_range(hops);
ii = rd.second;
// Skip neighbors with redundant TC information; that is, those
// which SHOULD have been covered by link state information in
// the Neighborhood as they are less than 2 hops away.
// We can't ignore TCs from two-hop neighbors because they may
// know about other nodes which our neighbors don't. In any event
// the SPF calculation will have screened those out.
// Print detailed information about such hops if debugging.
if (hops < 2) {
debug_msg("%s: skipping %u redundant TC entries at distance %u\n",
cstring(_fm.get_main_addr()),
XORP_UINT_CAST(std::distance(rd.first, rd.second)),
XORP_UINT_CAST(hops));
continue;
}
// 10, 3: The execution will stop if no new TC entry is recorded
// in an iteration.
if (0 == std::distance(rd.first, rd.second))
break;
// For each link in the topology set at the current radius.
for (jj = rd.first; jj != rd.second; jj++) {
TopologyEntry* tc = _topology[(*jj).second];
// Notify RouteManager of the link's existence.
// Duplicates covered by N1/N2 will return false.
// If it cannot connect it with any node on the existing
// boundary of the SPT topology, add_tc_link() will reject it
// by returning false.
if (true == _rm->add_tc_link(tc))
++tc_link_added_count;
}
}
debug_msg("%u TC entries pushed to SPT.\n",
XORP_UINT_CAST(tc_link_added_count));
}
/*
* Event handlers.
*/
bool
TopologyManager::event_receive_tc(
Message* msg,
const IPv4& remote_addr,
const IPv4& local_addr)
{
TcMessage* tc = dynamic_cast<TcMessage *>(msg);
if (0 == tc)
return false; // not for me
// Put this after the cast to skip false positives.
debug_msg("[TC] MyMainAddr %s Src %s RecvIf %s\n",
cstring(_fm.get_main_addr()),
cstring(remote_addr),
cstring(local_addr));
// 9.5.1 Sender of packet must be in symmetric 1-hop neighborhood.
if (! _nh.is_sym_neighbor_addr(remote_addr)) {
debug_msg("Rejecting TC message from %s via non-neighbor %s\n",
cstring(msg->origin()),
cstring(remote_addr));
XLOG_TRACE(_olsr.trace()._input_errors,
"Rejecting TC message from %s via non-neighbor %s",
cstring(msg->origin()),
cstring(remote_addr));
return true; // consumed but invalid.
}
// Invariant: The above call should mean I reject TC messages
// looped back to myself.
XLOG_ASSERT(tc->origin() != _fm.get_main_addr());
// 9.5.1, 9.5.2 Evaluate ANSN.
if (! apply_tc_ansn(tc->ansn(), tc->origin())) {
debug_msg("Rejecting TC message from %s with old ANSN %u\n",
cstring(msg->origin()),
XORP_UINT_CAST(tc->ansn()));
XLOG_TRACE(_olsr.trace()._input_errors,
"Rejecting TC message from %s with old ANSN %u",
cstring(msg->origin()),
XORP_UINT_CAST(tc->ansn()));
return true;
}
#ifdef DETAILED_DEBUG
// Invariant: The ANSN of all TC entries from tc->origin() must
// now be identical.
assert_tc_ansn_is_identical(tc->origin());
#endif
bool is_new_tc = false;
// Determine distance of these TC entries.
// TCs advertise neighbors which are 1 hop from the node which
// originated the message. tc->hops() is not incremented until
// forwarded, so add 1 here to take account of the actual distance.
// However, the distance of the neighbors advertised in the TC is
// one more than the distance of the neighbor itself, so add 2 hops.
uint16_t distance = tc->hops() + 2;
const vector<LinkAddrInfo>& addrs = tc->neighbors();
vector<LinkAddrInfo>::const_iterator ii;
for (ii = addrs.begin(); ii != addrs.end(); ii++) {
update_tc_entry((*ii).remote_addr(), tc->origin(),
distance, tc->ansn(),
tc->expiry_time(), is_new_tc);
}
// Maintain a list of the final sequence numbers seen from origins
// with empty neighbor sets.
TcFinalSeqMap::iterator jj = _tc_final_seqnos.find(tc->origin());
if (jj != _tc_final_seqnos.end())
_tc_final_seqnos.erase(jj);
if (addrs.empty()) {
_tc_final_seqnos.insert(make_pair(tc->origin(), tc->ansn()));
} else {
// Invariant: There must be no 'final' entry recorded if the
// origin advertised any neighbors.
XLOG_ASSERT(0 == _tc_final_seqnos.count(tc->origin()));
}
#ifdef DETAILED_DEBUG
// Invariant: The ANSN of all TC entries from tc->origin() must
// now be identical.
assert_tc_ansn_is_identical(tc->origin());
#endif
// A route computation will be necessary if apply_tc_ansn()
// invalidated any entries or if any entries were added/updated.
// It is possible to receive a TC w/o neighbors, so just assume
// that the TC info changed if we get here.
_rm->schedule_route_update();
_fm.forward_message(remote_addr, msg);
return true; // consumed
}
void
TopologyManager::event_tc_dead(const OlsrTypes::TopologyID tcid)
{
XLOG_ASSERT(0 != _topology.count(tcid));
delete_tc_entry(tcid);
}
bool
TopologyManager::event_receive_mid(
Message* msg,
const IPv4& remote_addr,
const IPv4& local_addr)
{
MidMessage* mid = dynamic_cast<MidMessage *>(msg);
if (0 == mid)
return false; // not for me
// Put this after the cast to skip false positives.
debug_msg("[MID] MyMainAddr %s Src %s RecvIf %s\n",
cstring(_fm.get_main_addr()),
cstring(remote_addr),
cstring(local_addr));
// 5.4.1 Sender must be in symmetric 1-hop neighborhood.
// This condition can be triggered during startup if the
// protocol timers are set low or if we haven't seen a
// HELLO from remote_addr yet.
if (! _nh.is_sym_neighbor_addr(remote_addr)) {
debug_msg("Rejecting MID message from %s via non-neighbor %s\n",
cstring(msg->origin()),
cstring(remote_addr));
XLOG_TRACE(_olsr.trace()._input_errors,
"Rejecting MID message from %s via non-neighbor %s",
cstring(msg->origin()),
cstring(remote_addr));
return true; // consumed but invalid.
}
TimeVal now;
_eventloop.current_time(now);
// 5.4.2 Process each interface listed in MID message.
size_t added_mid_count = 0;
try {
bool is_mid_created = false;
// Message::hops() is not incremented for our last hop until
// forwarded, so take account of this now when measuring distance.
const vector<IPv4>& addrs = mid->interfaces();
const uint16_t distance = mid->hops() + 1;
vector<IPv4>::const_iterator ii;
for (ii = addrs.begin(); ii != addrs.end(); ii++) {
update_mid_entry(mid->origin(), (*ii), distance,
mid->expiry_time(), is_mid_created);
if (is_mid_created)
added_mid_count++;
}
} catch (...) {
// If an exception is thrown, disregard the rest
// of the MID entries in this message, as it is more than
// likely we hit a hard limit. We can still forward the
// message, we just can't process all the MID entries.
}
// Trigger a route computation if and only if we added new MID addresses.
if (added_mid_count > 0)
_rm->schedule_route_update();
_fm.forward_message(remote_addr, msg);
return true; // consumed
UNUSED(local_addr);
}
void
TopologyManager::event_mid_dead(const OlsrTypes::MidEntryID mid_id)
{
XLOG_ASSERT(0 != _mids.count(mid_id));
delete_mid_entry(mid_id);
}
/*
* Child classes.
*/
void
TopologyEntry::update_timer(const TimeVal& vtime)
{
if (_expiry_timer.scheduled())
_expiry_timer.clear();
_expiry_timer = _ev.new_oneoff_after(vtime,
callback(this, &TopologyEntry::event_dead));
}
void
TopologyEntry::event_dead()
{
_parent->event_tc_dead(id());
}
void
MidEntry::update_timer(const TimeVal& vtime)
{
if (_expiry_timer.scheduled())
_expiry_timer.clear();
_expiry_timer = _ev.new_oneoff_after(vtime,
callback(this, &MidEntry::event_dead));
}
void
MidEntry::event_dead()
{
_parent->event_mid_dead(id());
}
103,104c103
< if (_topology[tcid]->destination() == dest_addr &&
< _topology[tcid]->lasthop() == origin_addr) {
---
> if (_topology[tcid]->lasthop() == origin_addr) {
254d252
< if( (*jj).first == origin_addr && _topology[tcid]->seqno() != ansn ) {
// PRH Mar.18/11
265d262
< } // PRH Mar.18/11
_______________________________________________
Xorp-hackers mailing list
[email protected]
http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers
