xorp

TopologyManager Class Reference

Class which manages topology outside of the one-hop and two-hop neighborhood in the OLSR domain. More...

#include <topology.hh>

List of all members.

Public Member Functions

 TopologyManager (Olsr &olsr, EventLoop &eventloop, FaceManager &fm, Neighborhood &nh)
RouteManagerroute_manager ()
void set_route_manager (RouteManager *rm)
void update_tc_entry (const IPv4 &dest_addr, const IPv4 &origin_addr, const uint16_t distance, const uint16_t ansn, const TimeVal &vtime, bool &is_created) throw (BadTopologyEntry)
 Update or create a topology entry in the TC database.
OlsrTypes::TopologyID add_tc_entry (const IPv4 &dest_addr, const IPv4 &origin_addr, const uint16_t distance, const uint16_t ansn, const TimeVal &expiry_time) throw (BadTopologyEntry)
 Add a topology entry to the database.
bool delete_tc_entry (const OlsrTypes::TopologyID tcid)
 Delete a topology entry by ID.
void clear_tc_entries ()
 Clear the TC database.
bool apply_tc_ansn (const uint16_t ansn, const IPv4 &origin_addr)
 Apply the Advertised Neighbor Sequence Number in the given TC message to the Topology Set.
OlsrTypes::TopologyID get_topologyid (const IPv4 &dest_addr, const IPv4 &lasthop_addr) throw (BadTopologyEntry)
 Return a topology entry ID given its destination and origin.
const TopologyEntryget_topology_entry_by_id (const OlsrTypes::TopologyID tcid) const throw (BadTopologyEntry)
 Get a pointer to a topology entry given its ID.
void get_topology_list (list< OlsrTypes::TopologyID > &tclist) const
 Fill out a list of all topology entry IDs.
vector< IPv4get_tc_neighbor_set (const IPv4 &origin_addr, uint16_t &ansn) throw (BadTopologyEntry)
 Retrieve the Advertised Neighbor Set (ANS) for a given OLSR peer.
uint16_t get_tc_distance (const IPv4 &origin_addr, const IPv4 &dest_addr) throw (BadTopologyEntry)
size_t get_tc_lasthop_count_by_dest (const IPv4 &dest_addr)
 Count the number of TC entries which point to a given destination.
size_t tc_node_count () const
 Calculate the number of unique OLSR nodes with TC entries in this node's TC database.
void update_mid_entry (const IPv4 &main_addr, const IPv4 &iface_addr, const uint16_t distance, const TimeVal &vtime, bool &is_mid_created) throw (BadMidEntry)
 Update a Multiple Interface Declaration (MID) entry.
void add_mid_entry (const IPv4 &main_addr, const IPv4 &iface_addr, const uint16_t distance, const TimeVal &vtime) throw (BadMidEntry)
 Create a new entry in the MID database.
bool delete_mid_entry (const OlsrTypes::MidEntryID mid_id)
 Delete a MID entry by ID.
void clear_mid_entries ()
 Clear MID entries.
vector< IPv4get_mid_addresses (const IPv4 &main_addr)
 Given the main address of an OLSR node, return a vector containing all other interface addresses for it, as learned via the MID part of the OLSR protocol.
uint16_t get_mid_address_distance (const IPv4 &main_addr, const IPv4 &iface_addr) throw (BadMidEntry)
 Look up the most recently seen distance of a MID entry, given its origin and interface address.
IPv4 get_main_addr_of_mid (const IPv4 &mid_addr) throw (BadMidEntry)
 Given an address possibly corresponding to a MID entry, return the main address to which it would map.
size_t mid_node_count () const
 Count the number of unique OLSR main addresses in this node's MID database.
const MidEntryget_mid_entry_by_id (const OlsrTypes::MidEntryID midid) const throw (BadTopologyEntry)
 Get a pointer to a MID entry given its ID.
void get_mid_list (list< OlsrTypes::MidEntryID > &midlist) const
 Fill out a list of all MID entry IDs.
void push_topology ()
 Push topology set to the RouteManager for SPT computation.
bool event_receive_tc (Message *msg, const IPv4 &remote_addr, const IPv4 &local_addr)
 Callback method to: process an incoming TC message.
void event_tc_dead (OlsrTypes::TopologyID tcid)
 Callback method to: delete an expiring TopologyEntry.
bool event_receive_mid (Message *msg, const IPv4 &remote_addr, const IPv4 &local_addr)
 Callback method to: process an incoming MID message.
void event_mid_dead (const OlsrTypes::MidEntryID mid_id)
 Callback method to: delete a dying MidEntry.

Protected Member Functions

void update_tc_distance (TopologyEntry *tc, uint16_t distance)
 Internal method to: update a TC entry's distance.
void assert_tc_distance_is_unique (const OlsrTypes::TopologyID tcid) throw (BadTopologyEntry)
 Internal method to: assert that a TC's distance is unique.
void assert_tc_ansn_is_identical (const IPv4 &origin_addr) throw (BadTopologyEntry)
 Internal method to: assert that the ANSNs for all TC entries originated by the node origin_addr are identical.

Private Types

typedef map
< OlsrTypes::MidEntryID,
MidEntry * > 
MidIdMap
 Multiple Interface Association Database.
typedef multimap< IPv4,
OlsrTypes::MidEntryID
MidAddrMap
 A map providing lookup of the MidEntries corresponding to the main protocol address of an OLSR node.
typedef map
< OlsrTypes::TopologyID,
TopologyEntry * > 
TcIdMap
 Topology Information Base.
typedef multimap< uint16_t,
OlsrTypes::TopologyID
TcDistanceMap
 A multimap providing lookup of topology entries by their distance.
typedef multimap< IPv4,
OlsrTypes::TopologyID
TcDestMap
 A multimap providing lookup of topology entries by destination.
typedef multimap< IPv4,
OlsrTypes::TopologyID
TcLasthopMap
 A multimap providing lookup of topology entries by last hop.
typedef map< IPv4, uint16_t > TcFinalSeqMap
 A map of final ANSN numbers for each origin from which we have seen TC messages with empty neighbor sets.

Private Attributes

Olsr_olsr
EventLoop_eventloop
FaceManager_fm
Neighborhood_nh
RouteManager_rm
OlsrTypes::MidEntryID _next_mid_id
OlsrTypes::TopologyID _next_tcid
MidIdMap _mids
MidAddrMap _mid_addr
TcIdMap _topology
TcDistanceMap _tc_distances
TcDestMap _tc_destinations
TcLasthopMap _tc_lasthops
TcFinalSeqMap _tc_final_seqnos

Detailed Description

Class which manages topology outside of the one-hop and two-hop neighborhood in the OLSR domain.


Member Typedef Documentation

A multimap providing lookup of topology entries by destination.

Used by TC updates.

typedef multimap<uint16_t, OlsrTypes::TopologyID> TopologyManager::TcDistanceMap [private]

A multimap providing lookup of topology entries by their distance.

Used for routing computation, the most common case.

typedef map<IPv4, uint16_t> TopologyManager::TcFinalSeqMap [private]

A map of final ANSN numbers for each origin from which we have seen TC messages with empty neighbor sets.

Used by the simulator for verification.

A multimap providing lookup of topology entries by last hop.

Used by ANSN processing.


Member Function Documentation

void TopologyManager::add_mid_entry ( const IPv4 main_addr,
const IPv4 iface_addr,
const uint16_t  distance,
const TimeVal vtime 
) throw (BadMidEntry)

Create a new entry in the MID database.

TODO Find the next available ID if already taken, as the range may recycle quickly in large, dynamically changing topologies.

Parameters:
main_addrthe main address of the node originating the MID entry.
iface_addrthe interface address of the MID entry.
distancethe distance in hops of the origin of the MIS message being processed.
vtimethe time for which the MID entry remains valid.
Exceptions:
BadMidEntryif the entry could not be created or updated.
OlsrTypes::TopologyID TopologyManager::add_tc_entry ( const IPv4 dest_addr,
const IPv4 origin_addr,
const uint16_t  distance,
const uint16_t  ansn,
const TimeVal expiry_time 
) throw (BadTopologyEntry)

Add a topology entry to the database.

Parameters:
dest_addrthe destination of the new topology entry.
origin_addrthe origin of the new topology entry.
distancethe distance in hops from this node to the origin, calculated from the message hop count.
ansnthe advertised sequence number of the topology entry.
expiry_timethe time for which this topology entry remains valid.
bool TopologyManager::apply_tc_ansn ( const uint16_t  ansn,
const IPv4 origin_addr 
)

Apply the Advertised Neighbor Sequence Number in the given TC message to the Topology Set.

Section 9.5: TC Message Processing, 2-3.

Parameters:
ansnthe ANSN to apply.
origin_addrthe origin of the TC message containing
ansn
Returns:
true if the provided ANSN is valid and has been applied, otherwise false if the message is stale and should be rejected.
void TopologyManager::assert_tc_ansn_is_identical ( const IPv4 origin_addr) throw (BadTopologyEntry) [protected]

Internal method to: assert that the ANSNs for all TC entries originated by the node origin_addr are identical.

A full linear search of the TC record space is performed. Stubbed out if DETAILED_DEBUG is not defined.

TODO: Eliminate this function by refactoring the data structures; we SHOULD be able to check if the last ANSN from origin was empty, currently we don't do that.

Parameters:
origin_addrthe node for which to verify the ANSNs.
Exceptions:
BadTopologyEntryif the ANSNs for origin_addr are not identical.
void TopologyManager::assert_tc_distance_is_unique ( const OlsrTypes::TopologyID  tcid) throw (BadTopologyEntry) [protected]

Internal method to: assert that a TC's distance is unique.

Verify that the given TopologyID appears once, and only once, in the _tc_distances array used for route computation. Stubbed out if DETAILED_DEBUG is not defined.

Parameters:
tcidthe topology entry ID to verify.
Exceptions:
BadTopologyEntryif tcid appears more than once in _tc_distances.
bool TopologyManager::delete_mid_entry ( const OlsrTypes::MidEntryID  mid_id)

Delete a MID entry by ID.

Parameters:
mid_idthe ID of the MID entry to delete.
Returns:
true if the MID entry was deleted.
bool TopologyManager::delete_tc_entry ( const OlsrTypes::TopologyID  tcid)

Delete a topology entry by ID.

It must be removed from last-hop and destination maps.

Parameters:
tcidthe ID of the toplogy entry to delete.
Returns:
true if the topology entry was deleted, false if it could not be found.
bool TopologyManager::event_receive_mid ( Message msg,
const IPv4 remote_addr,
const IPv4 local_addr 
)

Callback method to: process an incoming MID message.

Section 5.4: MID Message Processing.

Parameters:
msgthe message to process.
remote_addrthe source address of the Packet containing msg
local_addrthe address of the interface where
msgwas received.
Returns:
true if this method consumed
Parameters:
msg
bool TopologyManager::event_receive_tc ( Message msg,
const IPv4 remote_addr,
const IPv4 local_addr 
)

Callback method to: process an incoming TC message.

Section 9.5: TC Message Processing.

Parameters:
msgPointer to a message which is derived from TcMessage.
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.
void TopologyManager::event_tc_dead ( OlsrTypes::TopologyID  tcid)

Callback method to: delete an expiring TopologyEntry.

Parameters:
tcidthe ID of the expiring TopologyEntry.
IPv4 TopologyManager::get_main_addr_of_mid ( const IPv4 mid_addr) throw (BadMidEntry)

Given an address possibly corresponding to a MID entry, return the main address to which it would map.

Used by the protocol simulator. Requires a linear search of MID space, returns first match, there should be no other matches; no invariant.

Parameters:
mid_addrthe interface address to look up.
Returns:
the main address of the node with the given interface address.
Exceptions:
BadMidEntryif mid_addr was not found.
uint16_t TopologyManager::get_mid_address_distance ( const IPv4 main_addr,
const IPv4 iface_addr 
) throw (BadMidEntry)

Look up the most recently seen distance of a MID entry, given its origin and interface address.

Internal method. Stubbed out if DETAILED_DEBUG is not defined.

Parameters:
main_addrthe main address of the OLSR node to look up.
iface_addrthe interface address of the OLSR node to look up.
Exceptions:
BadMidEntryif the entry could not be found.
vector< IPv4 > TopologyManager::get_mid_addresses ( const IPv4 main_addr)

Given the main address of an OLSR node, return a vector containing all other interface addresses for it, as learned via the MID part of the OLSR protocol.

Parameters:
main_addrthe main address to look up
Returns:
a vector of protocol addresses, which may be empty.
const MidEntry * TopologyManager::get_mid_entry_by_id ( const OlsrTypes::MidEntryID  midid) const throw (BadTopologyEntry)

Get a pointer to a MID entry given its ID.

Used by the XRL layer.

Parameters:
mididthe ID of the MID entry to look up.
Returns:
the MID entry pointer.
Exceptions:
BadTopologyEntryif the entry could not be found.
void TopologyManager::get_mid_list ( list< OlsrTypes::MidEntryID > &  midlist) const

Fill out a list of all MID entry IDs.

Used by the XRL layer.

Parameters:
midlistthe list to fill out.
size_t TopologyManager::get_tc_lasthop_count_by_dest ( const IPv4 dest_addr)

Count the number of TC entries which point to a given destination.

Used by protocol simulator.

Parameters:
dest_addrthe TC destination.
Returns:
The number of TC entries pointing to dest_addr.
vector< IPv4 > TopologyManager::get_tc_neighbor_set ( const IPv4 origin_addr,
uint16_t &  ansn 
) throw (BadTopologyEntry)

Retrieve the Advertised Neighbor Set (ANS) for a given OLSR peer.

Typically used by protocol simulator.

Given the address of a node in the topology, retrieve the addresses from all TC entries originated by that node. Assumes that the "all entries for origin have same ANSN" invariant holds.

TODO: Also return the per-link ETX information.

Parameters:
origin_addrthe originating node to look up in the TC database.
ansnthe sequence number of origin_addr's neighbor set.
Exceptions:
BadTopologyEntryif origin_addr was not found.
const TopologyEntry * TopologyManager::get_topology_entry_by_id ( const OlsrTypes::TopologyID  tcid) const throw (BadTopologyEntry)

Get a pointer to a topology entry given its ID.

Used by the XRL layer.

Parameters:
tcidthe ID of the TC entry to look up.
Returns:
the MID pointer.
Exceptions:
BadTopologyEntryif the entry could not be found.
void TopologyManager::get_topology_list ( list< OlsrTypes::TopologyID > &  tclist) const

Fill out a list of all topology entry IDs.

Used by the XRL layer.

Parameters:
tclistthe list to fill out.
OlsrTypes::TopologyID TopologyManager::get_topologyid ( const IPv4 dest_addr,
const IPv4 lasthop_addr 
) throw (BadTopologyEntry)

Return a topology entry ID given its destination and origin.

Note: This is not declared 'const' due to the undeclared mutability of map::operator[].

Parameters:
dest_addrthe destination of the TC entry to look up.
lasthop_addrthe origin of the TC entry to look up.
Returns:
the topology ID.
Exceptions:
BadTopologyEntryif the entry could not be found.
size_t TopologyManager::mid_node_count ( ) const

Count the number of unique OLSR main addresses in this node's MID database.

Returns:
the number of OLSR main addresses in _mid_addr.
void TopologyManager::push_topology ( )

Push topology set to the RouteManager for SPT computation.

Section 10: Route computation.

In ascending order, we push the rest of the known network topology, starting with the TC entries which would have been originated by two-hop neighbors. If we encounter incomplete TC information for the network topology, that is, there are no known nodes at a particular distance, we stop pushing topology to RouteManager.

TODO: Use ETX measurements for edge choice.

size_t TopologyManager::tc_node_count ( ) const

Calculate the number of unique OLSR nodes with TC entries in this node's TC database.

Returns:
the number of unique main addresses in the TC lasthop map.
void TopologyManager::update_mid_entry ( const IPv4 main_addr,
const IPv4 iface_addr,
const uint16_t  distance,
const TimeVal vtime,
bool &  is_mid_created 
) throw (BadMidEntry)

Update a Multiple Interface Declaration (MID) entry.

The entry will be created if it does not exist.

Parameters:
main_addrthe main address of the node originating the MID entry.
iface_addrthe interface address of the MID entry.
distancethe distance in hops of the origin of the MIS message being processed.
vtimethe time for which the MID entry remains valid.
is_mid_createdset to true if a new MID entry was created.
Exceptions:
BadMidEntryif the entry could not be created or updated.
void TopologyManager::update_tc_distance ( TopologyEntry tc,
uint16_t  distance 
) [protected]

Internal method to: update a TC entry's distance.

It is necessary to maintain an insertion sort collation order in the TcDistanceMap as it is used for route calculation.

Parameters:
tcpointer to the TopologyEntry to update.
distancethe new distance of the TopologyEntry.
void TopologyManager::update_tc_entry ( const IPv4 dest_addr,
const IPv4 origin_addr,
const uint16_t  distance,
const uint16_t  ansn,
const TimeVal vtime,
bool &  is_created 
) throw (BadTopologyEntry)

Update or create a topology entry in the TC database.

Parameters:
dest_addrthe destination of the topology entry.
origin_addrthe origin of the topology entry.
distancethe distance in hops from this node to the origin, calculated from the message hop count.
ansnthe advertised sequence number of the topology entry.
vtimethe time for which this topology entry remains valid.
is_createda boolean which is set to true if a new entry has been created.
Exceptions:
BadTopologyEntryif the entry could not be created.

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