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

#include <neighborhood.hh>

Public Member Functions
	Neighborhood (Olsr &olsr, EventLoop &eventloop, FaceManager &fm)
TopologyManager *	topology_manager ()
void	set_topology_manager (TopologyManager *tm)
RouteManager *	route_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 LogicalLink *	get_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 Neighbor *	get_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.
TwoHopLink *	get_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 TwoHopNeighbor *	get_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::NeighborID >	mpr_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::NeighborID >	mpr_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 LogicalLink *	find_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 TwoHopLink *	find_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:

nid	the 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:

faceid The 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:

vtime	the validity time of the new link.
remote_addr	the protocol address of the remote interface at the far end of the link.
local_addr	the protocol address of the local interface at the near end of the link.

Returns:: the ID of the new link.

Exceptions:

BadLogicalLink if 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_addr	The main address of the new neighbor.
linkid	The ID of the Neighbor's first link.

Returns:: the ID of the newly created neighbor.

Exceptions:

BadNeighbor if 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:

nexthop	The strict one-hop neighbor at the near end of the TwoHopLink being created.
remote_addr	The two-hop neighbor at the far end of the TwoHopLink being created.
vtime	The time for which the TwoHopLink remains valid.

Returns:: the ID of the newly created TwoHopLink.

Exceptions:

BadTwoHopLink if 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_addr	the main address of the two-hop neighbor to create.
tlid	the ID of the initial link to this two-hop neighbor.

Returns:: the ID of the newly created two-hop neighbor.

Exceptions:

BadTwoHopNode if 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_count	The total number of N2 which must be reachable by the MPR set, used as a recursion upper bound.
covered_n2_count	A 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:

faceid The 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:

linkid the 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:

nid	the 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:

nid	The 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:

tlid	ID 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_addr	The address of the Neighbor used to reach the two-hop neighbor given by twohop_addr.
twohop_addr	The 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:

tnid	the 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:

linkid the 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:

linkid the 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:

linkid the 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:

linkid the 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:

nid	the 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:

msg	Pointer to a message which is derived from HelloMessage.
remote_addr	The source address of the packet containing msg.
local_addr	The 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:

tlid	the 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:

n	Pointer to a neighbor N.

Returns:: Pointer to a LogicalLink l which is the best link to N.

Exceptions:

BadLinkCoverage if 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:

n2	Pointer to a neighbor N2.

Returns:: Pointer to a TwoHopLink l2 which is the best link to N2.

Exceptions:

BadTwoHopCoverage if 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_addr	the protocol address of the remote interface at the far end of the link.
local_addr	the protocol address of the local interface at the near end of the link.

Returns:: the ID of the LogicalLink.

Exceptions:

BadLogicalLink if 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:

linkid the ID of the link to look up.

Returns:: a pointer to the logical link.

Exceptions:

BadLogicalLink if 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_list the list to fill out.

const Neighbor * Neighborhood::get_neighbor ( const OlsrTypes::NeighborID nid ) throw (BadNeighbor)

Find a Neighbor's pointer, given its NeighborID.

Parameters:

nid	the ID of the Neighbor.

Returns:: the pointer to the Neighbor instance.

Exceptions:

BadNeighbor if 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_list the 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_addr the main protocol address of the OLSR node.

Returns:: the neighbor ID.

Exceptions:

BadNeighbor if 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_addr the address of one of the interfaces of an OLSR node.

Returns:: the neighbor ID.

Exceptions:

BadNeighbor if 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:

tlid	the ID of a TwoHopLink.

Returns:: the pointer to the TwoHopLink instance.

Exceptions:

BadTwoHopLink if 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_list the 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:

tnid	the ID of a TwoHopNeighbor.

Returns:: the pointer to the TwoHopNeighbor instance.

Exceptions:

BadTwoHopNode if 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_list the 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_addr the main address of a two-hop neighbor.

Returns:: the ID of the two-hop neighbor.

Exceptions:

BadTwoHopNode if 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:

n	the 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_addr the 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:

addr	the 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_set will 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_set reference 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:

BadTwoHopCoverage if 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:

hello the 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:

n	the 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:

n2	the 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_deleted true 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:

coverage the 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:

interval the 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:

interval the 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:

type	the 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:

willingness the 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:

faceid	the ID of the interface where this link appears.
remote_addr	the protocol address of the remote interface at the far end of the link.
local_addr	the protocol address of the local interface at the near end of the link.
vtime	the validity time of the new link.
is_created	will 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:

BadLogicalLink if 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:

nid	the ID of the Neighbor to mark as an MPR selector.
vtime	the 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_addr	The main protocol address of the neighbor.
linkid	The ID of the initially created link to the neighbor.
is_new_link	true if the link the neighbor is being created with has just been instantiated.
will	The neighbor's advertised willingness-to-forward.
is_mpr_selector	true if the neighbor selects us as an MPR.
mprs_expiry_time	the expiry time for the MPR selector tuple.
is_created	set to true if a new neighbor entry was created.

Returns:: the ID of the updated or created neighbor tuple.

Exceptions:

BadNeighbor if 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:

n	Pointer 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_info	The address information for the two-hop neighbor; contains ETX measurements, if applicable.
nexthop	The main address of the immediate neighbor which advertises this TwoHopLink.
faceid	The interface where the advertisement was heard.
vtime	The 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_addr	the main address of the two-hop neighbor.
tlid	the ID of the two-hop link with which the two-hop neighbor is initially associated.
is_new_l2	true if tlid refers to a newly created link.
is_n2_created	set to true if a new TwoHopNeighbor was created.

Returns:: the ID of the two-hop neighbor.

Exceptions:

BadTwoHopNode if 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:

tn	Pointer 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:

nid	the ID of the neighbor to remove.

Member Data Documentation

map<pair<IPv4, IPv4>, OlsrTypes::LogicalLinkID> Neighborhood::_link_addr [private]

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

Used for processing incoming HELLOs.

map<OlsrTypes::LogicalLinkID, LogicalLink*> Neighborhood::_links [private]

This node's links to neighbors.

RFC 3626 Section 4.2.1 Local Link Information Base

map<OlsrTypes::NeighborID, Neighbor*> Neighborhood::_neighbors [private]

This node's neighbors.

RFC 3626 Section 4.3 Neighborhood Information Base

TimeVal Neighborhood::_refresh_interval [private]

The REFRESH_INTERVAL protocol control variable.

RFC 3626 Section 18.2.

TimeVal Neighborhood::_tc_interval [private]

The TC_INTERVAL protocol control variable.

RFC 3626 Section 18.2.

OlsrTypes::TcRedundancyType Neighborhood::_tc_redundancy [private]

The TC_REDUNDANCY protocol control variable.

Section 15.

map<OlsrTypes::TwoHopLinkID, TwoHopLink*> Neighborhood::_twohop_links [private]

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:

/home/greearb/git/xorp.ct.github/xorp/contrib/olsr/neighborhood.hh
/home/greearb/git/xorp.ct.github/xorp/contrib/olsr/neighborhood.cc

Neighborhood Class Reference

Public Member Functions

Protected Types

Protected Member Functions

Private Attributes

Detailed Description

Member Function Documentation

Member Data Documentation