Source: ../../contrib/olsr/topology.hh


 
LOGO
 Annotated List  Files  Globals  Hierarchy  Index  Top
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
// vim:set sts=4 ts=8 sw=4:

// Copyright (c) 2001-2009 XORP, Inc.
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, Version 2, June
// 1991 as published by the Free Software Foundation. Redistribution
// and/or modification of this program under the terms of any other
// version of the GNU General Public License is not permitted.
// 
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
// see the GNU General Public License, Version 2, a copy of which can be
// found in the XORP LICENSE.gpl file.
// 
// XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
// http://xorp.net

// $XORP: xorp/contrib/olsr/topology.hh,v 1.4 2009/01/05 18:30:47 jtc Exp $

#ifndef __OLSR_TOPOLOGY_HH__
#define __OLSR_TOPOLOGY_HH__

class TopologyManager;

/**
 * @short A multiple interface record (MID).
 *
 * There is one MidEntry per interface address advertised by an OLSR peer.
 * As such, a primary address may be associated with multiple MID entries.
 */
class MidEntry {
public:
    MidEntry(EventLoop& ev, TopologyManager* parent,
	     const OlsrTypes::MidEntryID id, const IPv4& iface_addr,
	     const IPv4& main_addr, const uint16_t distance,
	     const TimeVal& vtime)
     : _ev(ev), _parent(parent), _id(id),
       _iface_addr(iface_addr), _main_addr(main_addr),
       _distance(distance)
    {
	update_timer(vtime);
    }

    inline OlsrTypes::MidEntryID id() const { return _id; }
    inline IPv4 iface_addr() const { return _iface_addr; }
    inline IPv4 main_addr() const { return _main_addr; }
    inline uint16_t distance() const { return _distance; }

    inline void set_distance(const uint16_t distance) {
	_distance = distance;
    }

    /**
     * @return the amount of time remaining until this
     *         MID entry expires.
     */
    inline TimeVal time_remaining() const {
	TimeVal tv;
	_expiry_timer.time_remaining(tv);
	return tv;
    }

    /**
     * Update the MidEntry's expiry timer.
     *
     * @param vtime the new value of the expiry timer.
     */
    void update_timer(const TimeVal& vtime);

    /**
     * Callback method to: delete a dying MidEntry.
     */
    void event_dead();

private:
    EventLoop&		_ev;
    TopologyManager*	_parent;
    OlsrTypes::MidEntryID		_id;
    IPv4		_iface_addr;
    IPv4		_main_addr;
    uint16_t		_distance;
    XorpTimer		_expiry_timer;
};

/**
 * @short A topology control record (TC).
 */
class TopologyEntry {
public:
    TopologyEntry(EventLoop& ev, TopologyManager* parent,
		  OlsrTypes::TopologyID id,
		  const IPv4& dest, const IPv4& lasthop,
		  const uint16_t distance,
		  const uint16_t seqno,
		  const TimeVal& vtime)
     : _ev(ev), _parent(parent), _id(id), _destination(dest),
       _lasthop(lasthop), _distance(distance), _seqno(seqno)
    {
	update_timer(vtime);
    }

    inline OlsrTypes::TopologyID id() const { return _id; }
    inline IPv4 destination() const { return _destination; }
    inline IPv4 lasthop() const { return _lasthop; }
    inline uint16_t distance() const { return _distance; }
    inline uint16_t seqno() const { return _seqno; }

    inline void set_distance(const uint16_t d) { _distance = d; }

    /**
     * @return the amount of time remaining until this
     *         TC entry expires.
     */
    inline TimeVal time_remaining() const {
	TimeVal tv;
	_expiry_timer.time_remaining(tv);
	return tv;
    }

    /**
     * Update the TopologyEntry's expiry timer.
     *
     * @param vtime the new value of the expiry timer.
     */
    void update_timer(const TimeVal& vtime);

    /**
     * Callback method to: delete a dying TopologyEntry.
     */
    void event_dead();

private:
    EventLoop&			_ev;
    TopologyManager*		_parent;

    /**
     * @short unique identifier.
     */
    OlsrTypes::TopologyID	_id;

    /**
     * @short destination address.
     */
    IPv4	_destination;	// T_dest_addr

    /**
     * @short The last hop to reach _dest.
     */
    IPv4	_lasthop;	// T_last_addr

    /**
     * @short The number of hops from the origin to the neighbor
     * advertised in this TC entry.
     */
    uint16_t	_distance;	// Not named -- Section 10, 3.1

    /**
     * @short The ANSN of this entry.
     */
    uint16_t	_seqno;		// T_seq

    /**
     * @short The time at which this entry will expire.
     */
    XorpTimer	_expiry_timer;	// T_time
};

/**
 * @short Class which manages topology outside of the one-hop and
 * two-hop neighborhood in the OLSR domain.
 */
class TopologyManager {
  public:
    TopologyManager(Olsr& olsr, EventLoop& eventloop,
		    FaceManager& fm, Neighborhood& nh);
    ~TopologyManager();

    inline RouteManager* route_manager() { return _rm; }

    void set_route_manager(RouteManager* rm) { _rm = rm; }

    //
    // TC entries.
    //

    /**
     * Update or create a topology entry in the TC database.
     *
     * @param dest_addr the destination of the topology entry.
     * @param origin_addr the origin of the topology entry.
     * @param distance the distance in hops from this node to the origin,
     *                 calculated from the message hop count.
     * @param ansn the advertised sequence number of the topology entry.
     * @param vtime the time for which this topology entry
     *              remains valid.
     * @param is_created a boolean which is set to true if a new entry
     *                   has been created.
     * @throw BadTopologyEntry if the entry could not be created.
     */
    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);

    /**
     * Add a topology entry to the database.
     *
     * @param dest_addr the destination of the new topology entry.
     * @param origin_addr the origin of the new topology entry.
     * @param distance the distance in hops from this node to the origin,
     *                 calculated from the message hop count.
     * @param ansn the advertised sequence number of the topology entry.
     * @param expiry_time the time for which this topology entry
     *                    remains valid.
     */
    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);

    /**
     * Delete a topology entry by ID.
     * It must be removed from last-hop and destination maps.
     *
     * @param tcid the ID of the toplogy entry to delete.
     * @return true if the topology entry was deleted, false if it could
     *              not be found.
     */
    bool delete_tc_entry(const OlsrTypes::TopologyID tcid);

    /**
     * Clear the TC database.
     */
    void clear_tc_entries();

    /**
     * Apply the Advertised Neighbor Sequence Number in the given TC
     * message to the Topology Set.
     * Section 9.5: TC Message Processing, 2-3.
     *
     * @param ansn the ANSN to apply.
     * @param origin_addr the origin of the TC message containing @param ansn
     * @return true if the provided ANSN is valid and has been applied,
     *              otherwise false if the message is stale and should be
     *              rejected.
     */
    bool apply_tc_ansn(const uint16_t ansn, const IPv4& origin_addr);

    /**
     * Return a topology entry ID given its destination and origin.
     *
     * Note: This is not declared 'const' due to the undeclared
     * mutability of map::operator[].
     *
     * @param dest_addr the destination of the TC entry to look up.
     * @param lasthop_addr the origin of the TC entry to look up.
     * @return the topology ID.
     * @throw BadTopologyEntry if the entry could not be found.
     */
    OlsrTypes::TopologyID get_topologyid(const IPv4& dest_addr,
					 const IPv4& lasthop_addr)
	throw(BadTopologyEntry);

    /**
     * Get a pointer to a topology entry given its ID.
     *
     * Used by the XRL layer.
     *
     * @param tcid the ID of the TC entry to look up.
     * @return the MID pointer.
     * @throw BadTopologyEntry if the entry could not be found.
     */
    const TopologyEntry* get_topology_entry_by_id(
	const OlsrTypes::TopologyID tcid) const
	throw(BadTopologyEntry);

    /**
     * Fill out a list of all topology entry IDs.
     *
     * Used by the XRL layer.
     *
     * @param tclist the list to fill out.
     */
    void get_topology_list(list<OlsrTypes::TopologyID>& tclist) const;

    /**
     * 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.
     *
     * @param origin_addr the originating node to look up in the TC database.
     * @param ansn the sequence number of origin_addr's neighbor set.
     * @throw BadTopologyEntry if origin_addr was not found.
     */
    vector<IPv4> get_tc_neighbor_set(const IPv4& origin_addr, uint16_t& ansn)
	throw(BadTopologyEntry);

    /*
     * Look up the distance of a TC entry.
     * Used by protocol simulator.
     *
     * @param origin_addr the address of the node originating this TC entry.
     * @param neighbor_addr the address of the destination node.
     * @return the number of hops to reach neighbor_addr via origin_addr.
     * @throw BadTopologyEntry if the entry does not exist.
     */
    uint16_t get_tc_distance(const IPv4& origin_addr, const IPv4& dest_addr)
	throw(BadTopologyEntry);

    /**
     * Count the number of TC entries which point to a given destination.
     * Used by protocol simulator.
     *
     * @param dest_addr the TC destination.
     * @return The number of TC entries pointing to dest_addr.
     */
    size_t get_tc_lasthop_count_by_dest(const IPv4& dest_addr);

    /**
     * Calculate the number of unique OLSR nodes with TC entries in this
     * node's TC database.
     *
     * @return the number of unique main addresses in the TC lasthop map.
     */
    size_t tc_node_count() const;

    //
    // MID entries.
    //

    /**
     * Update a Multiple Interface Declaration (MID) entry.
     *
     * The entry will be created if it does not exist.
     *
     * @param main_addr the main address of the node originating
     *                  the MID entry.
     * @param iface_addr the interface address of the MID entry.
     * @param distance the distance in hops of the origin of the
     *                 MIS message being processed.
     * @param vtime the time for which the MID entry remains valid.
     * @param is_mid_created set to true if a new MID entry was created.
     * @throw BadMidEntry if the entry could not be created or updated.
     */
    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);

    /**
     * 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.
     *
     * @param main_addr the main address of the node originating
     *                  the MID entry.
     * @param iface_addr the interface address of the MID entry.
     * @param distance the distance in hops of the origin of the
     *                 MIS message being processed.
     * @param vtime the time for which the MID entry remains valid.
     * @throw BadMidEntry if the entry could not be created or updated.
     */
    void add_mid_entry(const IPv4& main_addr, const IPv4& iface_addr,
		       const uint16_t distance, const TimeVal& vtime)
	throw(BadMidEntry);

    /**
     * Delete a MID entry by ID.
     *
     * @param mid_id the ID of the MID entry to delete.
     * @return true if the MID entry was deleted.
     */
    bool delete_mid_entry(const OlsrTypes::MidEntryID mid_id);

    /**
     * Clear MID entries.
     */
    void clear_mid_entries();

    /**
     * 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.
     *
     * @param main_addr the main address to look up
     * @return a vector of protocol addresses, which may be empty.
     */
    vector<IPv4> get_mid_addresses(const IPv4& main_addr);

    /**
     * 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.
     *
     * @param main_addr the main address of the OLSR node to look up.
     * @param iface_addr the interface address of the OLSR node to look up.
     * @throw BadMidEntry if the entry could not be found.
     */
    uint16_t get_mid_address_distance(const IPv4& main_addr,
				      const IPv4& iface_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.
     *
     * @param mid_addr the interface address to look up.
     * @return the main address of the node with the given interface address.
     * @throw BadMidEntry if mid_addr was not found.
     */
    IPv4 get_main_addr_of_mid(const IPv4& mid_addr)
	throw(BadMidEntry);

    /**
     * Count the number of unique OLSR main addresses in this node's MID
     * database.
     *
     * @return the number of OLSR main addresses in _mid_addr.
     */
    size_t mid_node_count() const;

    /**
     * Get a pointer to a MID entry given its ID.
     *
     * Used by the XRL layer.
     *
     * @param midid the ID of the MID entry to look up.
     * @return the MID entry pointer.
     * @throw BadTopologyEntry if the entry could not be found.
     */
    const MidEntry* get_mid_entry_by_id(
	const OlsrTypes::MidEntryID midid) const
	throw(BadTopologyEntry);

    /**
     * Fill out a list of all MID entry IDs.
     *
     * Used by the XRL layer.
     *
     * @param midlist the list to fill out.
     */
    void get_mid_list(list<OlsrTypes::MidEntryID>& midlist) const;


    //
    // RouteManager interaction.
    //

    /**
     * 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.
     */
    void push_topology();

    //
    // Event handlers.
    //

    /**
     * Callback method to: process an incoming TC message.
     * Section 9.5: TC Message Processing.
     *
     * @param msg Pointer to a message which is derived from TcMessage.
     * @param remote_addr The source address of the packet containing msg.
     * @param local_addr The address of the interface where this packet was
     *                   received.
     * @return true if this function consumed msg.
     */
    bool event_receive_tc(Message* msg,
	const IPv4& remote_addr, const IPv4& local_addr);

    /**
     * Callback method to: delete an expiring TopologyEntry.
     *
     * @param tcid the ID of the expiring TopologyEntry.
     */
    void event_tc_dead(OlsrTypes::TopologyID tcid);

    /**
     * Callback method to: process an incoming MID message.
     * Section 5.4: MID Message Processing.
     *
     * @param msg the message to process.
     * @param remote_addr the source address of the Packet containing msg
     * @param local_addr the address of the interface where @param msg was
     *                   received.
     * @return true if this method consumed @param msg
     */
    bool event_receive_mid(Message* msg,
	const IPv4& remote_addr, const IPv4& local_addr);

    /**
     * Callback method to: delete a dying MidEntry.
     */
    void event_mid_dead(const OlsrTypes::MidEntryID mid_id);

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.
     *
     * @param tc pointer to the TopologyEntry to update.
     * @param distance the new distance of the TopologyEntry.
     */
    void update_tc_distance(TopologyEntry* tc, uint16_t distance);

    /**
     * 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.
     *
     * @param tcid the topology entry ID to verify.
     * @throw BadTopologyEntry if tcid appears more than once in _tc_distances.
     */
    void assert_tc_distance_is_unique(const OlsrTypes::TopologyID tcid)
	throw(BadTopologyEntry);

    /**
     * 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.
     *
     * @param origin_addr the node for which to verify the ANSNs.
     * @throw BadTopologyEntry if the ANSNs for origin_addr are not identical.
     */
    void assert_tc_ansn_is_identical(const IPv4& origin_addr)
	throw(BadTopologyEntry);

private:
    Olsr&		_olsr;
    EventLoop&		_eventloop;
    FaceManager&	_fm;
    Neighborhood&	_nh;
    RouteManager*	_rm;

    OlsrTypes::MidEntryID	_next_mid_id;
    OlsrTypes::TopologyID	_next_tcid;

    /**
     * Multiple Interface Association Database.
     */
    typedef map<OlsrTypes::MidEntryID, MidEntry*> MidIdMap;
    MidIdMap _mids;

    /**
     * A map providing lookup of the MidEntries corresponding to the
     * main protocol address of an OLSR node.
     */
    typedef multimap<IPv4, OlsrTypes::MidEntryID> MidAddrMap;
    MidAddrMap _mid_addr;

    /**
     * Topology Information Base.
     */
    typedef map<OlsrTypes::TopologyID, TopologyEntry*> TcIdMap;
    TcIdMap _topology;

    /**
     * A multimap providing lookup of topology entries by
     * their distance.
     * Used for routing computation, the most common case.
     */
    typedef multimap<uint16_t, OlsrTypes::TopologyID> TcDistanceMap;
    TcDistanceMap _tc_distances;

    /**
     * A multimap providing lookup of topology entries by destination.
     * Used by TC updates.
     */
    typedef multimap<IPv4, OlsrTypes::TopologyID> TcDestMap;
    TcDestMap _tc_destinations;

    /**
     * A multimap providing lookup of topology entries by last hop.
     * Used by ANSN processing.
     */
    typedef multimap<IPv4, OlsrTypes::TopologyID> TcLasthopMap;
    TcLasthopMap _tc_lasthops;

    /**
     * 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 map<IPv4, uint16_t>	    TcFinalSeqMap;
    TcFinalSeqMap _tc_final_seqnos;
};

#endif // __OLSR_TOPOLOGY_HH__

Generated by: pavlin on kobe.xorp.net on Wed Jan 7 19:11:15 2009, using kdoc 2.0a54+XORP.