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

Annotated List  Files  Globals  Hierarchy  Index  Top

Public Methods

•  Neighborhood (Olsr& olsr, EventLoop& eventloop, FaceManager& fm)
•  ~Neighborhood ()
• TopologyManager*  topology_manager ()
• void  set_topology_manager (TopologyManager* tm)
• RouteManager*  route_manager ()
• void  set_route_manager (RouteManager* rm)
• size_t  populate_hello (HelloMessage* hello)
• void  push_topology ()
• bool  set_tc_redundancy (const OlsrTypes::TcRedundancyType type)
• OlsrTypes::TcRedundancyType  get_tc_redundancy () const
• inline uint32_t  mpr_coverage () const
• bool  set_mpr_coverage (const uint32_t coverage)
• TimeVal  get_refresh_interval () const
• void  set_refresh_interval (const TimeVal& interval)
• TimeVal  get_tc_interval ()
• void  set_tc_interval (const TimeVal& interval)
• void  set_willingness (const OlsrTypes::WillType willingness)
• OlsrTypes::WillType  willingness () const
• TimeVal  get_neighbor_hold_time ()
• TimeVal  get_topology_hold_time ()
• void  add_face (const OlsrTypes::FaceID faceid)
• void  delete_face (const OlsrTypes::FaceID faceid)
• OlsrTypes::LogicalLinkID  update_link ( const OlsrTypes::FaceID faceid, const IPv4& remote_addr, const IPv4& local_addr, const TimeVal& vtime, bool& is_created)
• OlsrTypes::LogicalLinkID  add_link ( const TimeVal& vtime, const IPv4& remote_addr, const IPv4& local_addr)
• bool  delete_link (OlsrTypes::LogicalLinkID linkid)
• void  clear_links ()
• const LogicalLink*  get_logical_link (const OlsrTypes::LogicalLinkID linkid)
• void  get_logical_link_list (list<OlsrTypes::LogicalLinkID>& l1_list) const
• OlsrTypes::LogicalLinkID  get_linkid (const IPv4& remote_addr, const IPv4& local_addr)
• 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)
• OlsrTypes::NeighborID  add_neighbor (const IPv4& main_addr, OlsrTypes::LogicalLinkID linkid)
• bool  delete_neighbor (const OlsrTypes::NeighborID nid)
• const Neighbor*  get_neighbor (const OlsrTypes::NeighborID nid)
• void  get_neighbor_list (list<OlsrTypes::NeighborID>& n1_list) const
• OlsrTypes::NeighborID  get_neighborid_by_main_addr (const IPv4& main_addr)
• OlsrTypes::NeighborID  get_neighborid_by_remote_addr (const IPv4& remote_addr)
• bool  is_sym_neighbor_addr (const IPv4& addr)
• inline bool  is_tc_advertised_neighbor (Neighbor* n)
• void  schedule_ans_update (const bool is_deleted)
• OlsrTypes::TwoHopLinkID  update_twohop_link (const LinkAddrInfo& node_info, Neighbor& nexthop, const OlsrTypes::FaceID faceid, const TimeVal& vtime)
• OlsrTypes::TwoHopLinkID  add_twohop_link (Neighbor* nexthop, const IPv4& remote_addr, const TimeVal& vtime)
• bool  delete_twohop_link (OlsrTypes::TwoHopNodeID tlid)
• bool  delete_twohop_link_by_addrs (const IPv4& nexthop_addr, const IPv4& twohop_addr)
• TwoHopLink*  get_twohop_link (const OlsrTypes::TwoHopLinkID tlid)
• void  get_twohop_link_list (list<OlsrTypes::TwoHopLinkID>& l2_list) const
• OlsrTypes::TwoHopNodeID  update_twohop_node ( const IPv4& main_addr, const OlsrTypes::TwoHopLinkID tlid, const bool is_new_l2, bool& is_n2_created)
• OlsrTypes::TwoHopNodeID  add_twohop_node ( const IPv4& main_addr, const OlsrTypes::TwoHopLinkID tlid)
• bool  delete_twohop_node (OlsrTypes::TwoHopNodeID tnid)
• OlsrTypes::TwoHopNodeID  get_twohop_nodeid_by_main_addr ( const IPv4& main_addr)
• const TwoHopNeighbor*  get_twohop_neighbor ( const OlsrTypes::TwoHopNodeID tnid) const
• void  get_twohop_neighbor_list (list<OlsrTypes::TwoHopNodeID>& n2_list) const
• inline bool  is_mpr () const
• void  update_mpr_selector (const OlsrTypes::NeighborID nid, const TimeVal& vtime)
• void  delete_mpr_selector (const OlsrTypes::NeighborID nid)
• bool  is_mpr_selector_addr (const IPv4& remote_addr)
• set<OlsrTypes::NeighborID>  mpr_selector_set () const
• inline void  schedule_mpr_recount ()
• void  add_cand_mpr (const OlsrTypes::NeighborID nid)
• void  withdraw_cand_mpr (const OlsrTypes::NeighborID nid)
• void  recount_mpr_set ()
• void  reset_onehop_mpr_state ()
• size_t  reset_twohop_mpr_state ()
• void  update_onehop_reachability (Neighbor* n)
• void  update_twohop_reachability (TwoHopNeighbor* tn)
• size_t  consider_persistent_cand_mprs ()
• size_t  consider_poorly_covered_twohops ()
• void  consider_remaining_cand_mprs (const size_t n2_count, size_t& covered_n2_count)
• size_t  mark_all_n1_as_mprs (set<OlsrTypes::NeighborID>& final_mpr_set)
• size_t  minimize_mpr_set (set<OlsrTypes::NeighborID>& final_mpr_set)
• bool  is_essential_mpr (const Neighbor* n)
• set<OlsrTypes::NeighborID>  mpr_set () const
• void  event_link_sym_timer (OlsrTypes::LogicalLinkID linkid)
• void  event_link_asym_timer (OlsrTypes::LogicalLinkID linkid)
• void  event_link_lost_timer (OlsrTypes::LogicalLinkID linkid)
• void  event_link_dead_timer (OlsrTypes::LogicalLinkID linkid)
• void  event_twohop_link_dead_timer (const OlsrTypes::TwoHopLinkID tlid)
• void  event_mpr_selector_expired (const OlsrTypes::NeighborID nid)
• bool  event_receive_hello (Message* msg, const IPv4& remote_addr, const IPv4& local_addr)
• bool  event_send_tc ()
• void  stop_all_timers ()
• void  start_tc_timer ()
• void  stop_tc_timer ()
• void  restart_tc_timer ()

Protected Types

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

Protected Methods

• const LogicalLink*  find_best_link (const Neighbor* n)
• bool  push_neighbor (const Neighbor* n)
• const TwoHopLink*  find_best_twohop_link (const TwoHopNeighbor* n2)
• bool  push_twohop_neighbor (TwoHopNeighbor* n2)
• void  finish_tc_timer ()
• void  reschedule_immediate_tc_timer ()
• void  reschedule_tc_timer ()

Detailed Description

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

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:

Returns: the number of link addresses, including neighbors which are not local to this link, filled out in hello.

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.

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

Parameters:

Returns: true if the TC_REDUNDANCY was set to type.

[const]

Returns: the value of the TC_REDUNDANCY protocol variable.

[const]

Returns: the value of the MPR_COVERAGE protocol variable.

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:

Returns: true if the MPR_COVERAGE was set to coverage.

[const]

Returns: the value of the REFRESH_INTERVAL protocol variable.

Set the value of the REFRESH_INTERVAL protocol variable.

Parameters:

Returns: the value of the TC_INTERVAL protocol variable.

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:

Set the WILLINGNESS protocol variable.

Parameters:

[const]

Returns: the current value of the WILLINGNESS protocol variable.

Returns: the current value of the NEIGHB_HOLD_TIME protocol variable.

Returns: the current value of the TOP_HOLD_TIME protocol variable.

Add an interface to the neighborhood. Called whenever an instance of Face is configured administratively up.

Parameters:

Delete an interface from the neighborhood. Called whenever an instance of Face is configured administratively down.

Parameters:

Update a LogicalLink.

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

Parameters:

Returns: the ID of the link tuple. @throw BadLogicalLink if the link could not be updated.

Add a link to the local link database.

Parameters:

Returns: the ID of the new link. @throw BadLogicalLink if the link could not be created.

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:

Returns: true if the link was deleted.

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.

Look up a LogicalLink's pointer given its LogicalLinkID.

Parameters:

Returns: a pointer to the logical link. @throw BadLogicalLink if the link could not be found.

[const]

Fill out a list of all LogicalLinkIDs in the database.

Parameters:

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

Parameters:

Returns: the ID of the LogicalLink. @throw BadLogicalLink if the link could not be found.

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:

Returns: the ID of the updated or created neighbor tuple. @throw BadNeighbor if the neighbor entry could not be updated.

Add a new Neighbor to the one-hop neighbor database. A Neighbor must be created with at least one LogicalLink.

Parameters:

Returns: the ID of the newly created neighbor. @throw BadNeighbor if the neighbor entry could not be created.

Delete a neighbor from the neighbor database. Called when the last link to the neighbor has been deleted.

Parameters:

Returns: true if the neighbor was removed, false if it cannot be found.

Find a Neighbor's pointer, given its NeighborID.

Parameters:

Returns: the pointer to the Neighbor instance. @throw BadNeighbor if the Neighbor does not exist.

[const]

Fill out a list of all NeighborIDs in the database.

Parameters:

Find a neighbor ID, given its main address.

Parameters:

Returns: the neighbor ID. @throw BadNeighbor if the neighbor is not found.

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

Parameters:

Returns: the neighbor ID. @throw BadNeighbor if the neighbor is not found.

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:

Returns: true if addr is an interface address of a symmetric one-hop neighbor.

Returns: true if the Neighbor n would be advertised in a TC broadcast, given the current TC_REDUNDANCY.

Schedule an update of the Advertised Neighbor Set.

Parameters:

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:

Returns: the ID of the two-hop neighbor.

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:

Returns: the ID of the newly created TwoHopLink. @throw BadTwoHopLink if the TwoHopLink could not be created.

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:

Returns: true if the link thus deleted was the last link to the two-hop node it is used to reach, otherwise false.

Delete the TwoHopLink to a two-hop neighbor.

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

Parameters:

Returns: true if this was the last link to the two-hop neighbor and it was deleted as a result.

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

Parameters:

Returns: the pointer to the TwoHopLink instance. @throw BadTwoHopLink if tlid does not exist.

[const]

Fill out a list of all TwoHopLinkIDs in the database.

Parameters:

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:

Returns: the ID of the two-hop neighbor. @throw BadTwoHopNode if the two-hop neighbor could not be updated.

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

Parameters:

Returns: the ID of the newly created two-hop neighbor. @throw BadTwoHopNode if the two-hop neighbor could not be created.

Delete an entry in the two-hop neighbor table.

Parameters:

Returns: true if the neighbor was deleted, otherwise false.

Look up a two-hop neighbor by main address.

Parameters:

Returns: the ID of the two-hop neighbor. @throw BadTwoHopNode if the two-hop neighbor could not be found.

[const]

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

Parameters:

Returns: the pointer to the TwoHopNeighbor instance. @throw BadTwoHopNode if tnid does not exist.

[const]

Fill out a list of all TwoHopNodeIDs in the database.

Parameters:

[const]

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.

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:

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:

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:

Returns: true if addr is an interface address of a symmetric one-hop neighbor which selects this node as an MPR.

[const]

For use by simulation framework.

Returns: the MPR selector set.

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.

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

Parameters:

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

Parameters:

Callback method to: recount the MPR set for all configured OLSR interfaces.

Clear all existing MPR state for Neighbors.

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.

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:

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:

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.

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.

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:

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:

Returns: the number of neighbors which have been selected as MPRs.

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:

Returns: the number of elements removed from the MPR set, as it appears in the one-hop neighbor database. @throw BadTwoHopCoverage if the MPR minimization algorithm detects that a two-hop node is now uncovered by any MPRs.

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

Parameters:

Returns: true if any of N's links cover a poorly covered strict TwoHopNeighbor.

[const]

For use by simulation framework.

Returns: the MPR selector set.

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:

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:

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:

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

Parameters:

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

Parameters:

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

Parameters:

Callback method to: process an incoming HELLO message. Section 7.1.1: HELLO Message Processing.

Parameters:

Returns: true if this function consumed msg.

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.

Stop all timers in Neighborhood.

Start the TC transmission interval timer.

Stop the TC transmission interval timer.

Restart the TC transmission interval timer.

[protected]

Find the best link to a neighbor N.

Parameters:

Returns: Pointer to a LogicalLink l which is the best link to N. @throw BadLinkCoverage if none of the links are reachable or is of suitable ETX criteria.

[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:

Returns: true if the neighbor was pushed, false if it was not.

[protected]

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

Parameters:

Returns: Pointer to a TwoHopLink l2 which is the best link to N2. @throw BadTwoHopCoverage if none of the links are reachable, or of suitable ETX criteria.

[protected]

Push a single TwoHopNeigbor, and its links, to the RouteManager. Here, we select the best link to this TwoHopNeighbor.

Parameters:

Returns: true if the two-hop neighbor was pushed, false if it was not.

[protected]

Transition to the 'finish' state for the TC timer.

[protected]

Schedule the TC timer as soon as possible.

[protected]

Reschedule the TC timer if the TC interval changed.

[protected]