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

#include <topology.hh>

Public Member Functions
	TopologyManager (Olsr &olsr, EventLoop &eventloop, FaceManager &fm, Neighborhood &nh)
RouteManager *	route_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 TopologyEntry *	get_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< IPv4 >	get_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< IPv4 >	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.
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 MidEntry *	get_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

typedef multimap<IPv4, OlsrTypes::TopologyID> TopologyManager::TcDestMap [private]

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.

typedef multimap<IPv4, OlsrTypes::TopologyID> TopologyManager::TcLasthopMap [private]

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_addr	the main address of the node originating the MID entry.
iface_addr	the interface address of the MID entry.
distance	the distance in hops of the origin of the MIS message being processed.
vtime	the time for which the MID entry remains valid.

Exceptions:

BadMidEntry if 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_addr	the destination of the new topology entry.
origin_addr	the origin of the new topology entry.
distance	the distance in hops from this node to the origin, calculated from the message hop count.
ansn	the advertised sequence number of the topology entry.
expiry_time	the 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:

ansn	the ANSN to apply.
origin_addr	the 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_addr the node for which to verify the ANSNs.

Exceptions:

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

tcid	the topology entry ID to verify.

Exceptions:

BadTopologyEntry if 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_id the 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:

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

msg	the message to process.
remote_addr	the source address of the Packet containing msg
local_addr	the address of the interface where
msg	was 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:

msg	Pointer to a message which is derived from TcMessage.
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.

void TopologyManager::event_tc_dead ( OlsrTypes::TopologyID tcid )

Callback method to: delete an expiring TopologyEntry.

Parameters:

tcid	the 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_addr the interface address to look up.

Returns:: the main address of the node with the given interface address.

Exceptions:

BadMidEntry if 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_addr	the main address of the OLSR node to look up.
iface_addr	the interface address of the OLSR node to look up.

Exceptions:

BadMidEntry if 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_addr the 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:

midid the ID of the MID entry to look up.

Returns:: the MID entry pointer.

Exceptions:

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

midlist the 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_addr the 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_addr	the originating node to look up in the TC database.
ansn	the sequence number of origin_addr's neighbor set.

Exceptions:

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

tcid	the ID of the TC entry to look up.

Returns:: the MID pointer.

Exceptions:

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

tclist the 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_addr	the destination of the TC entry to look up.
lasthop_addr	the origin of the TC entry to look up.

Returns:: the topology ID.

Exceptions:

BadTopologyEntry if 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_addr	the main address of the node originating the MID entry.
iface_addr	the interface address of the MID entry.
distance	the distance in hops of the origin of the MIS message being processed.
vtime	the time for which the MID entry remains valid.
is_mid_created	set to true if a new MID entry was created.

Exceptions:

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

tc	pointer to the TopologyEntry to update.
distance	the 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_addr	the destination of the topology entry.
origin_addr	the origin of the topology entry.
distance	the distance in hops from this node to the origin, calculated from the message hop count.
ansn	the advertised sequence number of the topology entry.
vtime	the time for which this topology entry remains valid.
is_created	a boolean which is set to true if a new entry has been created.

Exceptions:

BadTopologyEntry if the entry could not be created.

The documentation for this class was generated from the following files:

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

TopologyManager Class Reference

Public Member Functions

Protected Member Functions

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

Member Function Documentation