xorp

Neighborhood Class Reference

Representation of OLSR node's one-hop and two-hop neighborhood. More...

#include <neighborhood.hh>

List of all members.

Public Member Functions

 Neighborhood (Olsr &olsr, EventLoop &eventloop, FaceManager &fm)
TopologyManagertopology_manager ()
void set_topology_manager (TopologyManager *tm)
RouteManagerroute_manager ()
void set_route_manager (RouteManager *rm)
size_t populate_hello (HelloMessage *hello)
 Given an empty HELLO message, fill it out as appropriate for its interface ID property.
void push_topology ()
 Push the topology to the RouteManager for route computation.
bool set_tc_redundancy (const OlsrTypes::TcRedundancyType type)
 Attempt to set the redundancy of links advertised in TC broadcasts.
OlsrTypes::TcRedundancyType get_tc_redundancy () const
uint32_t mpr_coverage () const
bool set_mpr_coverage (const uint32_t coverage)
 Attempt to set the required level of MPR coverage.
TimeVal get_refresh_interval () const
void set_refresh_interval (const TimeVal &interval)
 Set the value of the REFRESH_INTERVAL protocol variable.
TimeVal get_tc_interval ()
void set_tc_interval (const TimeVal &interval)
 Set the interval between TC broadcasts.
void set_willingness (const OlsrTypes::WillType willingness)
 Set the WILLINGNESS protocol variable.
OlsrTypes::WillType willingness () const
TimeVal get_neighbor_hold_time ()
TimeVal get_topology_hold_time ()
void add_face (const OlsrTypes::FaceID faceid)
 Add an interface to the neighborhood.
void delete_face (const OlsrTypes::FaceID faceid)
 Delete an interface from the neighborhood.
OlsrTypes::LogicalLinkID update_link (const OlsrTypes::FaceID faceid, const IPv4 &remote_addr, const IPv4 &local_addr, const TimeVal &vtime, bool &is_created) throw (BadLogicalLink)
 Update a LogicalLink.
OlsrTypes::LogicalLinkID add_link (const TimeVal &vtime, const IPv4 &remote_addr, const IPv4 &local_addr) throw (BadLogicalLink)
 Add a link to the local link database.
bool delete_link (OlsrTypes::LogicalLinkID linkid)
 Delete the link tuple specified by the given link id.
void clear_links ()
 Clear the neighborhood one-hop links.
const LogicalLinkget_logical_link (const OlsrTypes::LogicalLinkID linkid) throw (BadLogicalLink)
 Look up a LogicalLink's pointer given its LogicalLinkID.
void get_logical_link_list (list< OlsrTypes::LogicalLinkID > &l1_list) const
 Fill out a list of all LogicalLinkIDs in the database.
OlsrTypes::LogicalLinkID get_linkid (const IPv4 &remote_addr, const IPv4 &local_addr) throw (BadLogicalLink)
 Look up a LogicalLink's ID given its interface addresses.
OlsrTypes::NeighborID update_neighbor (const IPv4 &main_addr, const OlsrTypes::LogicalLinkID linkid, const bool is_new_link, const OlsrTypes::WillType will, const bool is_mpr_selector, const TimeVal &mprs_expiry_time, bool &is_created) throw (BadNeighbor)
 Update or create a Neighbor in the one-hop neighbor database.
OlsrTypes::NeighborID add_neighbor (const IPv4 &main_addr, OlsrTypes::LogicalLinkID linkid) throw (BadNeighbor)
 Add a new Neighbor to the one-hop neighbor database.
bool delete_neighbor (const OlsrTypes::NeighborID nid)
 Delete a neighbor from the neighbor database.
const Neighborget_neighbor (const OlsrTypes::NeighborID nid) throw (BadNeighbor)
 Find a Neighbor's pointer, given its NeighborID.
void get_neighbor_list (list< OlsrTypes::NeighborID > &n1_list) const
 Fill out a list of all NeighborIDs in the database.
OlsrTypes::NeighborID get_neighborid_by_main_addr (const IPv4 &main_addr) throw (BadNeighbor)
 Find a neighbor ID, given its main address.
OlsrTypes::NeighborID get_neighborid_by_remote_addr (const IPv4 &remote_addr) throw (BadNeighbor)
 Find a neighbor ID, given the address of one of its interfaces.
bool is_sym_neighbor_addr (const IPv4 &addr)
 Check if a remote address belongs to a symmetric one-hop neighbor.
bool is_tc_advertised_neighbor (Neighbor *n)
void schedule_ans_update (const bool is_deleted)
 Schedule an update of the Advertised Neighbor Set.
OlsrTypes::TwoHopLinkID update_twohop_link (const LinkAddrInfo &node_info, Neighbor &nexthop, const OlsrTypes::FaceID faceid, const TimeVal &vtime) throw (BadTwoHopLink)
 Update the link state information for a two-hop neighbor.
OlsrTypes::TwoHopLinkID add_twohop_link (Neighbor *nexthop, const IPv4 &remote_addr, const TimeVal &vtime) throw (BadTwoHopLink)
 Add a TwoHopLink to the Neighborhood.
bool delete_twohop_link (OlsrTypes::TwoHopNodeID tlid)
 Delete the TwoHopLink to a two-hop neighbor.
bool delete_twohop_link_by_addrs (const IPv4 &nexthop_addr, const IPv4 &twohop_addr)
 Delete the TwoHopLink to a two-hop neighbor.
TwoHopLinkget_twohop_link (const OlsrTypes::TwoHopLinkID tlid) throw (BadTwoHopLink)
 Given the ID of a TwoHopLink, return its instance pointer.
void get_twohop_link_list (list< OlsrTypes::TwoHopLinkID > &l2_list) const
 Fill out a list of all TwoHopLinkIDs in the database.
OlsrTypes::TwoHopNodeID update_twohop_node (const IPv4 &main_addr, const OlsrTypes::TwoHopLinkID tlid, const bool is_new_l2, bool &is_n2_created) throw (BadTwoHopNode)
 Update a two-hop neighbor.
OlsrTypes::TwoHopNodeID add_twohop_node (const IPv4 &main_addr, const OlsrTypes::TwoHopLinkID tlid) throw (BadTwoHopNode)
 Add a two-hop neighbor to the two-hop neighborhood.
bool delete_twohop_node (OlsrTypes::TwoHopNodeID tnid)
 Delete an entry in the two-hop neighbor table.
OlsrTypes::TwoHopNodeID get_twohop_nodeid_by_main_addr (const IPv4 &main_addr) throw (BadTwoHopNode)
 Look up a two-hop neighbor by main address.
const TwoHopNeighborget_twohop_neighbor (const OlsrTypes::TwoHopNodeID tnid) const throw (BadTwoHopNode)
 Given the ID of a TwoHopNeighbor, return its instance pointer.
void get_twohop_neighbor_list (list< OlsrTypes::TwoHopNodeID > &n2_list) const
 Fill out a list of all TwoHopNodeIDs in the database.
bool is_mpr () const
void update_mpr_selector (const OlsrTypes::NeighborID nid, const TimeVal &vtime)
 Update a Neighbor's status in the MPR selector set, possibly adding it.
void delete_mpr_selector (const OlsrTypes::NeighborID nid)
 Remove a neighbor from the MPR selector set by its ID.
bool is_mpr_selector_addr (const IPv4 &remote_addr)
 Check if an address belongs to a one-hop neighbor which is also an MPR selector.
set< OlsrTypes::NeighborIDmpr_selector_set () const
void schedule_mpr_recount ()
 Trigger a recount of the MPR set.
void add_cand_mpr (const OlsrTypes::NeighborID nid)
 Add a neighbor to the set of MPR candidates for the interfaces from which it is reachable.
void withdraw_cand_mpr (const OlsrTypes::NeighborID nid)
 Remove a neighbor from the set of MPR candidates for all interfaces.
void recount_mpr_set ()
 Callback method to: recount the MPR set for all configured OLSR interfaces.
void reset_onehop_mpr_state ()
 Clear all existing MPR state for Neighbors.
size_t reset_twohop_mpr_state (ostringstream &dbg)
 Clear all existing MPR state for TwoHopNeighbors.
void update_onehop_reachability (Neighbor *n)
 Compute one-hop neighbor reachability and update it in the Neighbor to avoid repetitively computing it on every MPR recount.
void update_twohop_reachability (TwoHopNeighbor *tn)
 Compute two-hop neighbor reachability.
size_t consider_persistent_cand_mprs (ostringstream &dbg)
 Consider persistent MPR candidates for MPR selection.
size_t consider_poorly_covered_twohops (ostringstream &dbg)
 Consider MPR coverage of poorly covered two-hop neighbors.
void consider_remaining_cand_mprs (const size_t n2_count, size_t &covered_n2_count, ostringstream &oss)
 Consider remaining MPR candidates for MPR selection.
size_t mark_all_n1_as_mprs (set< OlsrTypes::NeighborID > &final_mpr_set)
 Mark all N1 neighbors was MPRs.
size_t minimize_mpr_set (set< OlsrTypes::NeighborID > &final_mpr_set) throw (BadTwoHopCoverage)
 Minimize the MPR set, based on the MPR coverage parameter.
bool is_essential_mpr (const Neighbor *n)
 Determine if an MPR is essential to covering the entire two-hop neighborhood.
set< OlsrTypes::NeighborIDmpr_set () const
void event_link_sym_timer (OlsrTypes::LogicalLinkID linkid)
 Callback method to: service a LogicalLink's SYM timer.
void event_link_asym_timer (OlsrTypes::LogicalLinkID linkid)
 Callback method to: service a LogicalLink's ASYM timer.
void event_link_lost_timer (OlsrTypes::LogicalLinkID linkid)
 Callback method to: service a LogicalLink's LOST timer.
void event_link_dead_timer (OlsrTypes::LogicalLinkID linkid)
 Callback method to: service a LogicalLink's DEAD timer.
void event_twohop_link_dead_timer (const OlsrTypes::TwoHopLinkID tlid)
 Callback method to: service a TwoHopLink's DEAD timer.
void event_mpr_selector_expired (const OlsrTypes::NeighborID nid)
 Callback method to: service an MPR selector's EXPIRY timer.
bool event_receive_hello (Message *msg, const IPv4 &remote_addr, const IPv4 &local_addr)
 Callback method to: process an incoming HELLO message.
bool event_send_tc ()
 Callback method to: service the TC transmission timer.
void stop_all_timers ()
 Stop all timers in Neighborhood.
void start_tc_timer ()
 Start the TC transmission interval timer.
void stop_tc_timer ()
 Stop the TC transmission interval timer.
void restart_tc_timer ()
 Restart the TC transmission interval timer.

Protected Types

enum  TcTimerState { TC_STOPPED = 0, TC_RUNNING = 1, TC_FINISHING = 2 }

Protected Member Functions

const LogicalLinkfind_best_link (const Neighbor *n) throw (BadLinkCoverage)
 Find the best link to a neighbor N.
bool push_neighbor (const Neighbor *n)
 Push a single Neighbor, and its links, to the RouteManager.
const TwoHopLinkfind_best_twohop_link (const TwoHopNeighbor *n2) throw (BadTwoHopCoverage)
 Find the best link to a two-hop neighbor N2.
bool push_twohop_neighbor (TwoHopNeighbor *n2)
 Push a single TwoHopNeigbor, and its links, to the RouteManager.
void finish_tc_timer ()
 Transition to the 'finish' state for the TC timer.
void reschedule_immediate_tc_timer ()
 Schedule the TC timer as soon as possible.
void reschedule_tc_timer ()
 Reschedule the TC timer if the TC interval changed.

Private Attributes

Olsr_olsr
EventLoop_eventloop
FaceManager_fm
TopologyManager_tm
RouteManager_rm
LinkOrderPred _link_order_pred
TwoHopLinkOrderPred _twohop_link_order_pred
OlsrTypes::LogicalLinkID _next_linkid
OlsrTypes::NeighborID _next_neighborid
OlsrTypes::TwoHopLinkID _next_twohop_linkid
OlsrTypes::TwoHopNodeID _next_twohop_nodeid
uint32_t _enabled_face_count
 The count of administratively up and running OLSR interfaces in this OLSR routing process.
OlsrTypes::WillType _willingness
 Willingness of this node to forward packets for other nodes.
TimeVal _refresh_interval
 The REFRESH_INTERVAL protocol control variable.
bool _mpr_computation_enabled
 true if the MPR algorithm is enabled, false if all one-hop neighbors willing to forward should always be considered as MPRs.
uint32_t _mpr_coverage
 Section 16.1: MPR_COVERAGE Parameter.
XorpTask _mpr_recount_task
 A task which may be scheduled to recompute the global MPR set.
set< OlsrTypes::NeighborID_mpr_selector_set
 The neighbors which select this node as an MPR.
set< OlsrTypes::NeighborID_mpr_set
 The global set of neighbors which this node has selected as MPRs.
TimeVal _tc_interval
 The TC_INTERVAL protocol control variable.
OlsrTypes::TcRedundancyType _tc_redundancy
 The TC_REDUNDANCY protocol control variable.
XorpTimer _tc_timer
 The TC broadcast timer.
TcTimerState _tc_timer_state
 The current state of the TC timer: STOPPED, RUNNING or FINISHING.
uint32_t _tc_timer_ticks_remaining
 The number of ticks remaining until the TC timer transitions from FINISHING state to STOPPED state.
uint16_t _tc_current_ansn
 The current advertised neighbor sequence number.
uint16_t _tc_previous_ans_count
 The previous advertised neighbor count.
bool _loss_triggered_tc_enabled
 true if TC messages should be flooded immediately when an MPR selector is deleted.
bool _change_triggered_tc_enabled
 true if TC messages should be flooded immediately when any change in the ANSN is detected.
map< OlsrTypes::LogicalLinkID,
LogicalLink * > 
_links
 This node's links to neighbors.
map< pair< IPv4, IPv4 >
, OlsrTypes::LogicalLinkID
_link_addr
 A map providing lookup of Link ID based on remote and local protocol addresses in that order.
map< OlsrTypes::NeighborID,
Neighbor * > 
_neighbors
 This node's neighbors.
map< IPv4, OlsrTypes::NeighborID_neighbor_addr
 A map providing lookup of Neighbor ID based on the node's main address.
map< OlsrTypes::TwoHopLinkID,
TwoHopLink * > 
_twohop_links
 The two-hop link table.
map< pair< IPv4, IPv4 >
, OlsrTypes::TwoHopLinkID
_twohop_link_addrs
 A map providing lookup of two-hop link ID based on the main addresses of the one-hop and two-hop neighbors, in that order.
map< OlsrTypes::TwoHopNodeID,
TwoHopNeighbor * > 
_twohop_nodes
 The two-hop neighbor table.
map< IPv4,
OlsrTypes::TwoHopNodeID
_twohop_node_addrs
 A map providing lookup of two-hop neighbor ID based on its main protocol address and the next-hop used to reach it.

Detailed Description

Representation of OLSR node's one-hop and two-hop neighborhood.

Responsible for originating TC broadcasts when the node is selected as an MPR by other nodes.


Member Function Documentation

void Neighborhood::add_cand_mpr ( const OlsrTypes::NeighborID  nid)

Add a neighbor to the set of MPR candidates for the interfaces from which it is reachable.

Parameters:
nidthe ID of the neighbor to add.
void Neighborhood::add_face ( const OlsrTypes::FaceID  faceid)

Add an interface to the neighborhood.

Called whenever an instance of Face is configured administratively up.

Parameters:
faceidThe ID of the interface which has been configured administratively up.
OlsrTypes::LogicalLinkID Neighborhood::add_link ( const TimeVal vtime,
const IPv4 remote_addr,
const IPv4 local_addr 
) throw (BadLogicalLink)

Add a link to the local link database.

Parameters:
vtimethe validity time of the new link.
remote_addrthe protocol address of the remote interface at the far end of the link.
local_addrthe protocol address of the local interface at the near end of the link.
Returns:
the ID of the new link.
Exceptions:
BadLogicalLinkif the link could not be created.
OlsrTypes::NeighborID Neighborhood::add_neighbor ( const IPv4 main_addr,
OlsrTypes::LogicalLinkID  linkid 
) throw (BadNeighbor)

Add a new Neighbor to the one-hop neighbor database.

A Neighbor must be created with at least one LogicalLink.

Parameters:
main_addrThe main address of the new neighbor.
linkidThe ID of the Neighbor's first link.
Returns:
the ID of the newly created neighbor.
Exceptions:
BadNeighborif the neighbor entry could not be created.
OlsrTypes::TwoHopLinkID Neighborhood::add_twohop_link ( Neighbor nexthop,
const IPv4 remote_addr,
const TimeVal vtime 
) throw (BadTwoHopLink)

Add a TwoHopLink to the Neighborhood.

The constructor signature forces us to associate the near end of the TwoHopLink with a Neighbor. It MUST be associated with a TwoHopNeighbor after construction to be considered valid.

Parameters:
nexthopThe strict one-hop neighbor at the near end of the TwoHopLink being created.
remote_addrThe two-hop neighbor at the far end of the TwoHopLink being created.
vtimeThe time for which the TwoHopLink remains valid.
Returns:
the ID of the newly created TwoHopLink.
Exceptions:
BadTwoHopLinkif the TwoHopLink could not be created.
OlsrTypes::TwoHopNodeID Neighborhood::add_twohop_node ( const IPv4 main_addr,
const OlsrTypes::TwoHopLinkID  tlid 
) throw (BadTwoHopNode)

Add a two-hop neighbor to the two-hop neighborhood.

Parameters:
main_addrthe main address of the two-hop neighbor to create.
tlidthe ID of the initial link to this two-hop neighbor.
Returns:
the ID of the newly created two-hop neighbor.
Exceptions:
BadTwoHopNodeif the two-hop neighbor could not be created.
void Neighborhood::clear_links ( )

Clear the neighborhood one-hop links.

The neighbors and two-hop neighbors associated with these links will be removed. Assertions for this are in the destructor.

size_t Neighborhood::consider_persistent_cand_mprs ( ostringstream &  dbg)

Consider persistent MPR candidates for MPR selection.

8.3.1, 1: Start with an MPR set made of all members of N with willingness equal to WILL_ALWAYS.

This introduces the funky situation that a neighbor may be selected as an MPR even if it has no two-hop links. Such neighbors are always chosen as MPRs before other neighbors.

Returns:
The number of two-hop neighbors which have been covered by considering the persistent MPR candidates.
size_t Neighborhood::consider_poorly_covered_twohops ( ostringstream &  dbg)

Consider MPR coverage of poorly covered two-hop neighbors.

8.3.1, 3: Ensure that for all uncovered strict N2 reachable *only via 1 edge*, their neighbor N is selected as an MPR.

TODO: Use ETX measurements.

Returns:
The number of two-hop neighbors which have been covered by considering the persistent MPR candidates.
void Neighborhood::consider_remaining_cand_mprs ( const size_t  n2_count,
size_t &  covered_n2_count,
ostringstream &  oss 
)

Consider remaining MPR candidates for MPR selection.

Candidates are considered in descending order of willingness, reachability and degree.

Note: As we only use the result of the insertion sort in this scope, this block is a candidate for a Boost++ filter_iterator. However a filter iterator might keep scanning the N space and blowing the l2/l3 cache.

Parameters:
n2_countThe total number of N2 which must be reachable by the MPR set, used as a recursion upper bound.
covered_n2_countA reference to the cumulative number of N2 which are reachable by the MPR set, and which this method will update.
void Neighborhood::delete_face ( const OlsrTypes::FaceID  faceid)

Delete an interface from the neighborhood.

Called whenever an instance of Face is configured administratively down.

Parameters:
faceidThe ID of the interface which has been configured administratively down.
bool Neighborhood::delete_link ( OlsrTypes::LogicalLinkID  linkid)

Delete the link tuple specified by the given link id.

Note: The associated Neighbor may be deleted. State change is also propagated to the FaceManager.

Parameters:
linkidthe identifier of the link tuple.
Returns:
true if the link was deleted.
void Neighborhood::delete_mpr_selector ( const OlsrTypes::NeighborID  nid)

Remove a neighbor from the MPR selector set by its ID.

If the node no longer has any MPR selectors, it is no longer considered an MPR, and it must continue to originate empty TCs for TOP_HOLD_TIME, after which it shall stop.

Parameters:
nidthe ID of the Neighbor to add as an MPR selector.
bool Neighborhood::delete_neighbor ( const OlsrTypes::NeighborID  nid)

Delete a neighbor from the neighbor database.

Called when the last link to the neighbor has been deleted.

Parameters:
nidThe ID of this neighbor.
Returns:
true if the neighbor was removed, false if it cannot be found.
bool Neighborhood::delete_twohop_link ( OlsrTypes::TwoHopNodeID  tlid)

Delete the TwoHopLink to a two-hop neighbor.

The deletion is propagated to the Neighbor and TwoHopNeighbor instances on the near and far ends of the link respectively.

Parameters:
tlidID of the two-hop link which is to be deleted.
Returns:
true if the link thus deleted was the last link to the two-hop node it is used to reach, otherwise false.
bool Neighborhood::delete_twohop_link_by_addrs ( const IPv4 nexthop_addr,
const IPv4 twohop_addr 
)

Delete the TwoHopLink to a two-hop neighbor.

The link is identified by the near and far end main addresses.

Parameters:
nexthop_addrThe address of the Neighbor used to reach the two-hop neighbor given by twohop_addr.
twohop_addrThe two-hop neighbor whose link has been lost.
Returns:
true if this was the last link to the two-hop neighbor and it was deleted as a result.
bool Neighborhood::delete_twohop_node ( OlsrTypes::TwoHopNodeID  tnid)

Delete an entry in the two-hop neighbor table.

Parameters:
tnidthe ID of a two-hop neighbor.
Returns:
true if the neighbor was deleted, otherwise false.
void Neighborhood::event_link_asym_timer ( OlsrTypes::LogicalLinkID  linkid)

Callback method to: service a LogicalLink's ASYM timer.

Whilst the ASYM interval timer is pending, the link is considered asymmetric. When the timer fires, the link is considered LOST.

Parameters:
linkidthe ID of the link whose ASYM timer has fired.
void Neighborhood::event_link_dead_timer ( OlsrTypes::LogicalLinkID  linkid)

Callback method to: service a LogicalLink's DEAD timer.

Parameters:
linkidthe ID of the link whose DEAD timer has fired.
void Neighborhood::event_link_lost_timer ( OlsrTypes::LogicalLinkID  linkid)

Callback method to: service a LogicalLink's LOST timer.

Section 13: Link Layer Notification.

TODO: Not yet implemented, as it relies on link layer support from the host platform which does not yet exist. In practice this should not pose a problem, as 802.11 IBSS disassociation is often unreliable anyway.

Parameters:
linkidthe ID of the link whose LOST timer has fired.
void Neighborhood::event_link_sym_timer ( OlsrTypes::LogicalLinkID  linkid)

Callback method to: service a LogicalLink's SYM timer.

Whilst the SYM interval timer is pending, the link is considered symmetric. When the timer fires, the link is considered ASYM. If both the ASYM and SYM timers fire in the same event loop quantum, the ASYM timer is considered to have priority.

Parameters:
linkidthe ID of the link whose SYM timer has fired.
void Neighborhood::event_mpr_selector_expired ( const OlsrTypes::NeighborID  nid)

Callback method to: service an MPR selector's EXPIRY timer.

Parameters:
nidthe ID of the Neighbor whose MPR selector tuple has expired.
bool Neighborhood::event_receive_hello ( Message msg,
const IPv4 remote_addr,
const IPv4 local_addr 
)

Callback method to: process an incoming HELLO message.

Section 7.1.1: HELLO Message Processing.

Parameters:
msgPointer to a message which is derived from HelloMessage.
remote_addrThe source address of the packet containing msg.
local_addrThe address of the interface where this packet was received.
Returns:
true if this function consumed msg.
bool Neighborhood::event_send_tc ( )

Callback method to: service the TC transmission timer.

Section 9.2: Advertised Neighbor Set.

Flood a TC message to the rest of the OLSR domain which contains our Advertised Neighbor Set (ANS). This method should only be called if the TC timer is running or finishing. The finishing state is entered when a node has stopped being an MPR or when the ANS set becomes empty.

TODO: Account for ETX metrics in selecting advertised neighbors. TODO: Fish-eye TC emission optimization; transmit only.

Returns:
true if the callback should be rescheduled, otherwise false.
void Neighborhood::event_twohop_link_dead_timer ( const OlsrTypes::TwoHopLinkID  tlid)

Callback method to: service a TwoHopLink's DEAD timer.

Parameters:
tlidthe ID of the two-hop link whose DEAD timer has fired.
const LogicalLink * Neighborhood::find_best_link ( const Neighbor n) throw (BadLinkCoverage) [protected]

Find the best link to a neighbor N.

Parameters:
nPointer to a neighbor N.
Returns:
Pointer to a LogicalLink l which is the best link to N.
Exceptions:
BadLinkCoverageif none of the links are reachable or is of suitable ETX criteria.
const TwoHopLink * Neighborhood::find_best_twohop_link ( const TwoHopNeighbor n2) throw (BadTwoHopCoverage) [protected]

Find the best link to a two-hop neighbor N2.

Parameters:
n2Pointer to a neighbor N2.
Returns:
Pointer to a TwoHopLink l2 which is the best link to N2.
Exceptions:
BadTwoHopCoverageif none of the links are reachable, or of suitable ETX criteria.
OlsrTypes::LogicalLinkID Neighborhood::get_linkid ( const IPv4 remote_addr,
const IPv4 local_addr 
) throw (BadLogicalLink)

Look up a LogicalLink's ID given its interface addresses.

Parameters:
remote_addrthe protocol address of the remote interface at the far end of the link.
local_addrthe protocol address of the local interface at the near end of the link.
Returns:
the ID of the LogicalLink.
Exceptions:
BadLogicalLinkif the link could not be found.
const LogicalLink * Neighborhood::get_logical_link ( const OlsrTypes::LogicalLinkID  linkid) throw (BadLogicalLink)

Look up a LogicalLink's pointer given its LogicalLinkID.

Parameters:
linkidthe ID of the link to look up.
Returns:
a pointer to the logical link.
Exceptions:
BadLogicalLinkif the link could not be found.
void Neighborhood::get_logical_link_list ( list< OlsrTypes::LogicalLinkID > &  l1_list) const

Fill out a list of all LogicalLinkIDs in the database.

Parameters:
l1_listthe list to fill out.
const Neighbor * Neighborhood::get_neighbor ( const OlsrTypes::NeighborID  nid) throw (BadNeighbor)

Find a Neighbor's pointer, given its NeighborID.

Parameters:
nidthe ID of the Neighbor.
Returns:
the pointer to the Neighbor instance.
Exceptions:
BadNeighborif the Neighbor does not exist.
TimeVal Neighborhood::get_neighbor_hold_time ( ) [inline]
Returns:
the current value of the NEIGHB_HOLD_TIME protocol variable.
void Neighborhood::get_neighbor_list ( list< OlsrTypes::NeighborID > &  n1_list) const

Fill out a list of all NeighborIDs in the database.

Parameters:
n1_listthe list to fill out.
OlsrTypes::NeighborID Neighborhood::get_neighborid_by_main_addr ( const IPv4 main_addr) throw (BadNeighbor)

Find a neighbor ID, given its main address.

Parameters:
main_addrthe main protocol address of the OLSR node.
Returns:
the neighbor ID.
Exceptions:
BadNeighborif the neighbor is not found.
OlsrTypes::NeighborID Neighborhood::get_neighborid_by_remote_addr ( const IPv4 remote_addr) throw (BadNeighbor)

Find a neighbor ID, given the address of one of its interfaces.

Parameters:
remote_addrthe address of one of the interfaces of an OLSR node.
Returns:
the neighbor ID.
Exceptions:
BadNeighborif the neighbor is not found.
TimeVal Neighborhood::get_refresh_interval ( ) const [inline]
Returns:
the value of the REFRESH_INTERVAL protocol variable.
TimeVal Neighborhood::get_tc_interval ( ) [inline]
Returns:
the value of the TC_INTERVAL protocol variable.
OlsrTypes::TcRedundancyType Neighborhood::get_tc_redundancy ( ) const [inline]
Returns:
the value of the TC_REDUNDANCY protocol variable.
TimeVal Neighborhood::get_topology_hold_time ( ) [inline]
Returns:
the current value of the TOP_HOLD_TIME protocol variable.
TwoHopLink * Neighborhood::get_twohop_link ( const OlsrTypes::TwoHopLinkID  tlid) throw (BadTwoHopLink)

Given the ID of a TwoHopLink, return its instance pointer.

Parameters:
tlidthe ID of a TwoHopLink.
Returns:
the pointer to the TwoHopLink instance.
Exceptions:
BadTwoHopLinkif tlid does not exist.
void Neighborhood::get_twohop_link_list ( list< OlsrTypes::TwoHopLinkID > &  l2_list) const

Fill out a list of all TwoHopLinkIDs in the database.

Parameters:
l2_listthe list to fill out.
const TwoHopNeighbor * Neighborhood::get_twohop_neighbor ( const OlsrTypes::TwoHopNodeID  tnid) const throw (BadTwoHopNode)

Given the ID of a TwoHopNeighbor, return its instance pointer.

Parameters:
tnidthe ID of a TwoHopNeighbor.
Returns:
the pointer to the TwoHopNeighbor instance.
Exceptions:
BadTwoHopNodeif tnid does not exist.
void Neighborhood::get_twohop_neighbor_list ( list< OlsrTypes::TwoHopNodeID > &  n2_list) const

Fill out a list of all TwoHopNodeIDs in the database.

Parameters:
n2_listthe list to fill out.
OlsrTypes::TwoHopNodeID Neighborhood::get_twohop_nodeid_by_main_addr ( const IPv4 main_addr) throw (BadTwoHopNode)

Look up a two-hop neighbor by main address.

Parameters:
main_addrthe main address of a two-hop neighbor.
Returns:
the ID of the two-hop neighbor.
Exceptions:
BadTwoHopNodeif the two-hop neighbor could not be found.
bool Neighborhood::is_essential_mpr ( const Neighbor n)

Determine if an MPR is essential to covering the entire two-hop neighborhood.

Parameters:
nthe Neighbor to evaluate.
Returns:
true if any of N's links cover a poorly covered strict TwoHopNeighbor.
bool Neighborhood::is_mpr ( ) const [inline]
Returns:
true if this node has been selected as an MPR by any one-hop neighbor, that is, the MPR selector set is non-empty.
bool Neighborhood::is_mpr_selector_addr ( const IPv4 remote_addr)

Check if an address belongs to a one-hop neighbor which is also an MPR selector.

Referenced from: Section 3.4.1 Default Forwarding Algorithm.

Parameters:
remote_addrthe IPv4 interface address to look up in the neighbor database.
Returns:
true if addr is an interface address of a symmetric one-hop neighbor which selects this node as an MPR.
bool Neighborhood::is_sym_neighbor_addr ( const IPv4 addr)

Check if a remote address belongs to a symmetric one-hop neighbor.

Referenced from: Section 5.4 point 1 MID Message Processing. Section 9.5 point 1 TC Message Processing. Section 12.5 point 1 HNA Message Processing.

Parameters:
addrthe interface address of a neighbor.
Returns:
true if addr is an interface address of a symmetric one-hop neighbor.
bool Neighborhood::is_tc_advertised_neighbor ( Neighbor n) [inline]
Returns:
true if the Neighbor n would be advertised in a TC broadcast, given the current TC_REDUNDANCY.
size_t Neighborhood::mark_all_n1_as_mprs ( set< OlsrTypes::NeighborID > &  final_mpr_set)

Mark all N1 neighbors was MPRs.

Considers all reachable one-hop neighbors with willingness of other than WILL_NEVER as MPRs. This feature is typically used as a workaround in dense OLSR topologies which are not sufficiently partitioned.

Parameters:
final_mpr_setwill have the result set of this method merged with it.
Returns:
the number of neighbors which have been selected as MPRs.
size_t Neighborhood::minimize_mpr_set ( set< OlsrTypes::NeighborID > &  final_mpr_set) throw (BadTwoHopCoverage)

Minimize the MPR set, based on the MPR coverage parameter.

Produces the final MPR set in a std::set container, for debugging purposes. Section 8.3.1, 4.

Parameters:
final_mpr_setreference to an empty MPR set that shall contain the resultant MPR set after it has been minimized.
Returns:
the number of elements removed from the MPR set, as it appears in the one-hop neighbor database.
Exceptions:
BadTwoHopCoverageif the MPR minimization algorithm detects that a two-hop node is now uncovered by any MPRs.
uint32_t Neighborhood::mpr_coverage ( ) const [inline]
Returns:
the value of the MPR_COVERAGE protocol variable.
set<OlsrTypes::NeighborID> Neighborhood::mpr_selector_set ( ) const [inline]
Returns:
the MPR selector set.

For use by simulation framework.

set<OlsrTypes::NeighborID> Neighborhood::mpr_set ( ) const [inline]
Returns:
the MPR selector set.

For use by simulation framework.

size_t Neighborhood::populate_hello ( HelloMessage hello)

Given an empty HELLO message, fill it out as appropriate for its interface ID property.

If the message is not empty the results are undefined.

TODO: Support ETX measurements.

Parameters:
hellothe HELLO message to be filled out, which MUST contain the FaceID of where it is to be sent.
Returns:
the number of link addresses, including neighbors which are not local to this link, filled out in hello.
bool Neighborhood::push_neighbor ( const Neighbor n) [protected]

Push a single Neighbor, and its links, to the RouteManager.

The SPT structure can only hold a single edge between each neighbor at the moment. We also need to select each node by its ETX. In the absence of ETX measurements, we select the most recently heard symmetric link which is up.

Parameters:
nthe neighbor to push.
Returns:
true if the neighbor was pushed, false if it was not.
void Neighborhood::push_topology ( )

Push the topology to the RouteManager for route computation.

When we do incremental SPT this can partially go away. The SPT can contain only one edge between each node -- the nested methods here deal with this.

bool Neighborhood::push_twohop_neighbor ( TwoHopNeighbor n2) [protected]

Push a single TwoHopNeigbor, and its links, to the RouteManager.

Here, we select the best link to this TwoHopNeighbor.

Parameters:
n2the two-hop neighbor to push.
Returns:
true if the two-hop neighbor was pushed, false if it was not.
size_t Neighborhood::reset_twohop_mpr_state ( ostringstream &  dbg)

Clear all existing MPR state for TwoHopNeighbors.

Compute number of now uncovered reachable nodes at radius=2.

Returns:
The number of reachable, strict two-hop neighbors to be considered by MPR selection.
void Neighborhood::schedule_ans_update ( const bool  is_deleted)

Schedule an update of the Advertised Neighbor Set.

Parameters:
is_deletedtrue if the update is being scheduled in response to the deletion of a Neighbor.
void Neighborhood::schedule_mpr_recount ( ) [inline]

Trigger a recount of the MPR set.

Invoked whenever there is a change of state which would cause the MPR set to change. Calculating the MPR set is an expensive operation, so it is scheduled as a one-off task in the event loop.

bool Neighborhood::set_mpr_coverage ( const uint32_t  coverage)

Attempt to set the required level of MPR coverage.

If successful, and OLSR is running on any configured interface, the MPR set will be recalculated.

Parameters:
coveragethe new value of the MPR_COVERAGE variable.
Returns:
true if the MPR_COVERAGE was set to coverage.
void Neighborhood::set_refresh_interval ( const TimeVal interval) [inline]

Set the value of the REFRESH_INTERVAL protocol variable.

Parameters:
intervalthe new value of REFRESH_INTERVAL..
void Neighborhood::set_tc_interval ( const TimeVal interval)

Set the interval between TC broadcasts.

The timer will only be restarted if previously scheduled. If the period of the TC broadcasts is changed, a TC broadcast is scheduled to take place immediately.

Parameters:
intervalthe new value of TC_INTERVAL.
bool Neighborhood::set_tc_redundancy ( const OlsrTypes::TcRedundancyType  type)

Attempt to set the redundancy of links advertised in TC broadcasts.

Parameters:
typethe new redundancy level to set.
Returns:
true if the TC_REDUNDANCY was set to type.
void Neighborhood::set_willingness ( const OlsrTypes::WillType  willingness)

Set the WILLINGNESS protocol variable.

Parameters:
willingnessthe new value of the WILLINGNESS protocol variable.
OlsrTypes::LogicalLinkID Neighborhood::update_link ( const OlsrTypes::FaceID  faceid,
const IPv4 remote_addr,
const IPv4 local_addr,
const TimeVal vtime,
bool &  is_created 
) throw (BadLogicalLink)

Update a LogicalLink.

The link will be created if it does not exist. Links are specified by their remote and local interface addresses.

Parameters:
faceidthe ID of the interface where this link appears.
remote_addrthe protocol address of the remote interface at the far end of the link.
local_addrthe protocol address of the local interface at the near end of the link.
vtimethe validity time of the new link.
is_createdwill be set to true if the link did not previously exist and was created by this method.
Returns:
the ID of the link tuple.
Exceptions:
BadLogicalLinkif the link could not be updated.
void Neighborhood::update_mpr_selector ( const OlsrTypes::NeighborID  nid,
const TimeVal vtime 
)

Update a Neighbor's status in the MPR selector set, possibly adding it.

If our node now has a non-empty MPR selector set, it must now originate TC advertisements.

Parameters:
nidthe ID of the Neighbor to mark as an MPR selector.
vtimethe duration of the MPR selector set membership.
OlsrTypes::NeighborID Neighborhood::update_neighbor ( const IPv4 main_addr,
const OlsrTypes::LogicalLinkID  linkid,
const bool  is_new_link,
const OlsrTypes::WillType  will,
const bool  is_mpr_selector,
const TimeVal mprs_expiry_time,
bool &  is_created 
) throw (BadNeighbor)

Update or create a Neighbor in the one-hop neighbor database.

This method has the weak exception guarantee that BadNeighbor will only be thrown before it is associated with LogicalLink.

Parameters:
main_addrThe main protocol address of the neighbor.
linkidThe ID of the initially created link to the neighbor.
is_new_linktrue if the link the neighbor is being created with has just been instantiated.
willThe neighbor's advertised willingness-to-forward.
is_mpr_selectortrue if the neighbor selects us as an MPR.
mprs_expiry_timethe expiry time for the MPR selector tuple.
is_createdset to true if a new neighbor entry was created.
Returns:
the ID of the updated or created neighbor tuple.
Exceptions:
BadNeighborif the neighbor entry could not be updated.
void Neighborhood::update_onehop_reachability ( Neighbor n)

Compute one-hop neighbor reachability and update it in the Neighbor to avoid repetitively computing it on every MPR recount.

Coverage must be valid. If this method is called outside of an MPR recount results are undefined.

Reachability is defined as: the number of uncovered N2 nodes which have edges to this N. We do this outside of Neighbor for code brevity.

Parameters:
nPointer to a Neighbor, which is normally an MPR candidate.
OlsrTypes::TwoHopLinkID Neighborhood::update_twohop_link ( const LinkAddrInfo node_info,
Neighbor nexthop,
const OlsrTypes::FaceID  faceid,
const TimeVal vtime 
) throw (BadTwoHopLink)

Update the link state information for a two-hop neighbor.

This method may create a TwoHopNeighbor and/or a TwoHopLink if they do not already exist.

Parameters:
node_infoThe address information for the two-hop neighbor; contains ETX measurements, if applicable.
nexthopThe main address of the immediate neighbor which advertises this TwoHopLink.
faceidThe interface where the advertisement was heard.
vtimeThe time for which the TwoHopLink remains valid.
Returns:
the ID of the two-hop neighbor.
OlsrTypes::TwoHopNodeID Neighborhood::update_twohop_node ( const IPv4 main_addr,
const OlsrTypes::TwoHopLinkID  tlid,
const bool  is_new_l2,
bool &  is_n2_created 
) throw (BadTwoHopNode)

Update a two-hop neighbor.

If the TwoHopNeighbor does not exist it will be created. A valid two-hop link must be provided; if the link is also newly created, this method will create the back-reference.

Parameters:
main_addrthe main address of the two-hop neighbor.
tlidthe ID of the two-hop link with which the two-hop neighbor is initially associated.
is_new_l2true if tlid refers to a newly created link.
is_n2_createdset to true if a new TwoHopNeighbor was created.
Returns:
the ID of the two-hop neighbor.
Exceptions:
BadTwoHopNodeif the two-hop neighbor could not be updated.
void Neighborhood::update_twohop_reachability ( TwoHopNeighbor tn)

Compute two-hop neighbor reachability.

It will be updated it in the TwoHopNeighbor to avoid computing it more than once during an MPR recount. If an N2 is reachable via an N with WILL_ALWAYS this takes precedence.

TODO: WHEN ETX IS IMPLEMENTED, A LINK WITH NO 'GOOD' LINKS MUST BE CONSIDERED UNREACHABLE.

Two-hop reachability is defined as: the number of MPR candidates with edges linking them to N2. Note: This is NOT THE SAME as a one-hop neighbor's reachability.

We do this outside of TwoHopNeighbor to avoid playing too many tedious C++ accessor games. MPR candidacy of linked neighbors must be valid. If this method is called outside of an MPR recount, its results are undefined.

Parameters:
tnPointer to a TwoHopNeighbor.
OlsrTypes::WillType Neighborhood::willingness ( ) const [inline]
Returns:
the current value of the WILLINGNESS protocol variable.
void Neighborhood::withdraw_cand_mpr ( const OlsrTypes::NeighborID  nid)

Remove a neighbor from the set of MPR candidates for all interfaces.

Parameters:
nidthe ID of the neighbor to remove.

Member Data Documentation

A map providing lookup of Link ID based on remote and local protocol addresses in that order.

Used for processing incoming HELLOs.

This node's links to neighbors.

RFC 3626 Section 4.2.1 Local Link Information Base

This node's neighbors.

RFC 3626 Section 4.3 Neighborhood Information Base

The REFRESH_INTERVAL protocol control variable.

RFC 3626 Section 18.2.

The TC_INTERVAL protocol control variable.

RFC 3626 Section 18.2.

The TC_REDUNDANCY protocol control variable.

Section 15.

The two-hop link table.

This is not part of the RFC however we break the implementation of two-hop neighbors into links and nodes to facilitate faster convergence of MPR sets when links change in the vicinity.


The documentation for this class was generated from the following files:
 All Classes Namespaces Functions Variables Typedefs Enumerations