xorp

neighborhood.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8 sw=4:
00003 
00004 // Copyright (c) 2001-2011 XORP, Inc and Others
00005 //
00006 // This program is free software; you can redistribute it and/or modify
00007 // it under the terms of the GNU General Public License, Version 2, June
00008 // 1991 as published by the Free Software Foundation. Redistribution
00009 // and/or modification of this program under the terms of any other
00010 // version of the GNU General Public License is not permitted.
00011 // 
00012 // This program is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00015 // see the GNU General Public License, Version 2, a copy of which can be
00016 // found in the XORP LICENSE.gpl file.
00017 // 
00018 // XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00019 // http://xorp.net
00020 
00021 // $XORP: xorp/contrib/olsr/neighborhood.hh,v 1.3 2008/10/02 21:56:35 bms Exp $
00022 
00023 #ifndef __OLSR_NEIGHBORHOOD_HH__
00024 #define __OLSR_NEIGHBORHOOD_HH__
00025 
00026 class Olsr;
00027 class LogicalLink;
00028 class Neighbor;
00029 class TwoHopNeighbor;
00030 class TwoHopLink;
00031 class HelloMessage;
00032 class TopologyManager;
00033 class RouteManager;
00034 class Neighborhood;
00035 
00042 struct CandMprOrderPred {
00051     bool operator()(const Neighbor* lhs, const Neighbor* rhs) const;
00052 };
00053 
00060 struct LinkOrderPred {
00061     Neighborhood* _nh;
00062 
00063     inline LinkOrderPred(Neighborhood* nh) : _nh(nh) {}
00064 
00080     bool operator()(const OlsrTypes::LogicalLinkID lhid,
00081             const OlsrTypes::LogicalLinkID rhid);
00082 };
00083 
00090 struct TwoHopLinkOrderPred {
00091     Neighborhood* _nh;
00092 
00093     inline TwoHopLinkOrderPred(Neighborhood* nh) : _nh(nh) {}
00094 
00103     bool operator()(const OlsrTypes::TwoHopLinkID lhid,
00104             const OlsrTypes::TwoHopLinkID rhid);
00105 };
00106 
00113 class Neighborhood {
00114   public:
00115     Neighborhood(Olsr& olsr, EventLoop& eventloop, FaceManager& fm);
00116     ~Neighborhood();
00117 
00118     //
00119     // Top level associations.
00120     //
00121 
00122     TopologyManager* topology_manager() { return _tm; }
00123     void set_topology_manager(TopologyManager* tm) { _tm = tm; }
00124 
00125     RouteManager* route_manager() { return _rm; }
00126     void set_route_manager(RouteManager* rm) { _rm = rm; }
00127 
00140     size_t populate_hello(HelloMessage* hello);
00141 
00149     void push_topology();
00150 
00151     //
00152     // RFC 3626 Section 18.2: Protocol control variables.
00153     //
00154 
00161     bool set_tc_redundancy(const OlsrTypes::TcRedundancyType type);
00162 
00166     OlsrTypes::TcRedundancyType get_tc_redundancy() const {
00167     return _tc_redundancy;
00168     }
00169 
00173     inline uint32_t mpr_coverage() const { return _mpr_coverage; }
00174 
00184     bool set_mpr_coverage(const uint32_t coverage);
00185 
00189     TimeVal get_refresh_interval() const { return _refresh_interval; }
00190 
00196     void set_refresh_interval(const TimeVal& interval) {
00197     _refresh_interval = interval;
00198     }
00199 
00203     TimeVal get_tc_interval() { return _tc_interval; }
00204 
00214     void set_tc_interval(const TimeVal& interval);
00215 
00221     void set_willingness(const OlsrTypes::WillType willingness);
00222 
00226     OlsrTypes::WillType willingness() const { return _willingness; }
00227 
00231     TimeVal get_neighbor_hold_time() { return _refresh_interval * 3; }
00232 
00236     TimeVal get_topology_hold_time() { return _tc_interval * 3; }
00237 
00238     //
00239     // Face interaction.
00240     //
00241 
00249     void add_face(const OlsrTypes::FaceID faceid);
00250 
00258     void delete_face(const OlsrTypes::FaceID faceid);
00259 
00260     //
00261     // Link database.
00262     //
00263 
00281     OlsrTypes::LogicalLinkID update_link(
00282     const OlsrTypes::FaceID faceid,
00283     const IPv4& remote_addr,
00284     const IPv4& local_addr,
00285     const TimeVal& vtime,
00286     bool& is_created)
00287     throw(BadLogicalLink);
00288 
00300     OlsrTypes::LogicalLinkID add_link(
00301     const TimeVal& vtime,
00302     const IPv4& remote_addr,
00303     const IPv4& local_addr)
00304     throw(BadLogicalLink);
00305 
00315     bool delete_link(OlsrTypes::LogicalLinkID linkid);
00316 
00323     void clear_links();
00324 
00332     const LogicalLink* get_logical_link(const OlsrTypes::LogicalLinkID linkid)
00333     throw(BadLogicalLink);
00334 
00340     void get_logical_link_list(list<OlsrTypes::LogicalLinkID>& l1_list)
00341     const;
00342 
00353     OlsrTypes::LogicalLinkID get_linkid(const IPv4& remote_addr,
00354     const IPv4& local_addr)
00355     throw(BadLogicalLink);
00356 
00357     //get_link_list
00358 
00359     //
00360     // Neighbor database.
00361     //
00362 
00380     OlsrTypes::NeighborID update_neighbor(const IPv4& main_addr,
00381     const OlsrTypes::LogicalLinkID linkid,
00382     const bool is_new_link,
00383     const OlsrTypes::WillType will,
00384     const bool is_mpr_selector,
00385     const TimeVal& mprs_expiry_time,
00386     bool& is_created)
00387     throw(BadNeighbor);
00388 
00398     OlsrTypes::NeighborID add_neighbor(const IPv4& main_addr,
00399     OlsrTypes::LogicalLinkID linkid)
00400     throw(BadNeighbor);
00401 
00410     bool delete_neighbor(const OlsrTypes::NeighborID nid);
00411 
00419     const Neighbor* get_neighbor(const OlsrTypes::NeighborID nid)
00420     throw(BadNeighbor);
00421 
00427     void get_neighbor_list(list<OlsrTypes::NeighborID>& n1_list) const;
00428 
00436     OlsrTypes::NeighborID get_neighborid_by_main_addr(const IPv4& main_addr)
00437     throw(BadNeighbor);
00438 
00447     OlsrTypes::NeighborID
00448     get_neighborid_by_remote_addr(const IPv4& remote_addr)
00449     throw(BadNeighbor);
00450 
00463     bool is_sym_neighbor_addr(const IPv4& addr);
00464 
00465     //
00466     // Advertised neighbor set.
00467     //
00468 
00473     inline bool is_tc_advertised_neighbor(Neighbor* n) {
00474     if ((_tc_redundancy == OlsrTypes::TCR_ALL) ||
00475         (_tc_redundancy == OlsrTypes::TCR_MPRS_INOUT && n->is_mpr()) ||
00476          n->is_mpr_selector()) {
00477         return true;
00478     }
00479     return false;
00480     }
00481 
00488     void schedule_ans_update(const bool is_deleted);
00489 
00490     //
00491     // Two hop link database.
00492     //
00493 
00508     OlsrTypes::TwoHopLinkID update_twohop_link(const LinkAddrInfo& node_info,
00509                            Neighbor& nexthop,
00510                            const OlsrTypes::FaceID faceid,
00511                            const TimeVal& vtime)
00512     throw(BadTwoHopLink);
00513 
00529     OlsrTypes::TwoHopLinkID add_twohop_link(Neighbor* nexthop,
00530                         const IPv4& remote_addr,
00531                         const TimeVal& vtime)
00532     throw(BadTwoHopLink);
00533 
00544     bool delete_twohop_link(OlsrTypes::TwoHopNodeID tlid);
00545 
00557     bool delete_twohop_link_by_addrs(const IPv4& nexthop_addr,
00558                      const IPv4& twohop_addr);
00559 
00567     TwoHopLink* get_twohop_link(const OlsrTypes::TwoHopLinkID tlid)
00568     throw(BadTwoHopLink);
00569 
00575     void get_twohop_link_list(list<OlsrTypes::TwoHopLinkID>& l2_list) const;
00576 
00577     //
00578     // Two hop node database.
00579     //
00580 
00596     OlsrTypes::TwoHopNodeID update_twohop_node(
00597     const IPv4& main_addr,
00598     const OlsrTypes::TwoHopLinkID tlid,
00599     const bool is_new_l2,
00600     bool& is_n2_created)
00601     throw(BadTwoHopNode);
00602 
00611     OlsrTypes::TwoHopNodeID add_twohop_node(
00612         const IPv4& main_addr,
00613     const OlsrTypes::TwoHopLinkID tlid)
00614     throw(BadTwoHopNode);
00615 
00622     bool delete_twohop_node(OlsrTypes::TwoHopNodeID tnid);
00623 
00631     OlsrTypes::TwoHopNodeID get_twohop_nodeid_by_main_addr(
00632     const IPv4& main_addr)
00633     throw(BadTwoHopNode);
00634 
00642     const TwoHopNeighbor* get_twohop_neighbor(
00643     const OlsrTypes::TwoHopNodeID tnid) const throw(BadTwoHopNode);
00644 
00650     void get_twohop_neighbor_list(list<OlsrTypes::TwoHopNodeID>& n2_list)
00651     const;
00652 
00653     //
00654     // MPR selector set methods.
00655     //
00656 
00661     inline bool is_mpr() const { return !_mpr_selector_set.empty(); }
00662 
00673     void update_mpr_selector(const OlsrTypes::NeighborID nid,
00674                  const TimeVal& vtime);
00675 
00685     void delete_mpr_selector(const OlsrTypes::NeighborID nid);
00686 
00699     bool is_mpr_selector_addr(const IPv4& remote_addr);
00700 
00706     set<OlsrTypes::NeighborID> mpr_selector_set() const {
00707     return _mpr_selector_set;
00708     }
00709 
00710     //
00711     // MPR set methods.
00712     //
00713 
00721     inline void schedule_mpr_recount() {
00722     _mpr_recount_task.reschedule();
00723     }
00724 
00731     void add_cand_mpr(const OlsrTypes::NeighborID nid);
00732 
00738     void withdraw_cand_mpr(const OlsrTypes::NeighborID nid);
00739 
00744     void recount_mpr_set();
00745 
00749     void reset_onehop_mpr_state();
00750 
00758     size_t reset_twohop_mpr_state(ostringstream& dbg);
00759 
00772     void update_onehop_reachability(Neighbor* n);
00773 
00795     void update_twohop_reachability(TwoHopNeighbor* tn);
00796 
00810     size_t consider_persistent_cand_mprs(ostringstream& dbg);
00811 
00823     size_t consider_poorly_covered_twohops(ostringstream& dbg);
00824 
00842     void consider_remaining_cand_mprs(const size_t n2_count,
00843                       size_t& covered_n2_count, ostringstream& oss);
00844 
00857     size_t mark_all_n1_as_mprs(set<OlsrTypes::NeighborID>& final_mpr_set);
00858 
00874     size_t minimize_mpr_set(set<OlsrTypes::NeighborID>& final_mpr_set)
00875     throw(BadTwoHopCoverage);
00876 
00885     bool is_essential_mpr(const Neighbor* n);
00886 
00892     set<OlsrTypes::NeighborID> mpr_set() const {
00893     return _mpr_set;
00894     }
00895 
00896     //
00897     // Event handlers.
00898     //
00899 
00910     void event_link_sym_timer(OlsrTypes::LogicalLinkID linkid);
00911 
00920     void event_link_asym_timer(OlsrTypes::LogicalLinkID linkid);
00921 
00934     void event_link_lost_timer(OlsrTypes::LogicalLinkID linkid);
00935 
00941     void event_link_dead_timer(OlsrTypes::LogicalLinkID linkid);
00942 
00948     void event_twohop_link_dead_timer(const OlsrTypes::TwoHopLinkID tlid);
00949 
00956     void event_mpr_selector_expired(const OlsrTypes::NeighborID nid);
00957 
00968     bool event_receive_hello(Message* msg,
00969     const IPv4& remote_addr, const IPv4& local_addr);
00970 
00987     bool event_send_tc();
00988 
00989     //
00990     // Timer methods.
00991     //
00992 
00996     void stop_all_timers();
00997 
01001     void start_tc_timer();
01002 
01006     void stop_tc_timer();
01007 
01011     void restart_tc_timer();
01012 
01013 protected:
01014     //
01015     // One-hop link selection.
01016     //
01017 
01026     const LogicalLink* find_best_link(const Neighbor* n)
01027         throw(BadLinkCoverage);
01028 
01040     bool push_neighbor(const Neighbor* n);
01041 
01042     //
01043     // Two-hop link selection.
01044     //
01045 
01054     const TwoHopLink* find_best_twohop_link(const TwoHopNeighbor* n2)
01055     throw(BadTwoHopCoverage);
01056 
01064     bool push_twohop_neighbor(TwoHopNeighbor* n2);
01065 
01069     void finish_tc_timer();
01070 
01074     void reschedule_immediate_tc_timer();
01075 
01079     void reschedule_tc_timer();
01080 
01081     enum TcTimerState {
01082     TC_STOPPED = 0,
01083     TC_RUNNING = 1,
01084     TC_FINISHING = 2
01085     };
01086 
01087 private:
01088     Olsr&       _olsr;
01089     EventLoop&      _eventloop;
01090     FaceManager&    _fm;
01091     TopologyManager*    _tm;
01092     RouteManager*   _rm;
01093 
01094     LinkOrderPred       _link_order_pred;
01095     TwoHopLinkOrderPred     _twohop_link_order_pred;
01096 
01097     OlsrTypes::LogicalLinkID    _next_linkid;
01098     OlsrTypes::NeighborID   _next_neighborid;
01099     OlsrTypes::TwoHopLinkID _next_twohop_linkid;
01100     OlsrTypes::TwoHopNodeID _next_twohop_nodeid;
01101 
01106     uint32_t            _enabled_face_count;
01107 
01111     OlsrTypes::WillType     _willingness;
01112 
01117     TimeVal         _refresh_interval;
01118 
01119     /*
01120      * MPR sets.
01121      */
01122 
01127     bool            _mpr_computation_enabled;
01128 
01132     uint32_t            _mpr_coverage;
01133 
01137     XorpTask            _mpr_recount_task;
01138 
01142     set<OlsrTypes::NeighborID>  _mpr_selector_set;
01143 
01147     set<OlsrTypes::NeighborID>  _mpr_set;
01148 
01149     /*
01150      * Topology Control
01151      */
01152 
01157     TimeVal         _tc_interval;
01158 
01163     OlsrTypes::TcRedundancyType _tc_redundancy;
01164 
01168     XorpTimer            _tc_timer;
01169 
01173     TcTimerState        _tc_timer_state;
01174 
01179     uint32_t            _tc_timer_ticks_remaining;
01180 
01184     uint16_t            _tc_current_ansn;
01185 
01189     uint16_t            _tc_previous_ans_count;
01190 
01195     bool            _loss_triggered_tc_enabled;
01196 
01201     bool            _change_triggered_tc_enabled;
01202 
01203     /*
01204      * Link state databases.
01205      */
01206 
01211     map<OlsrTypes::LogicalLinkID, LogicalLink*> _links;
01212 
01218     map<pair<IPv4, IPv4>, OlsrTypes::LogicalLinkID> _link_addr;
01219 
01224     map<OlsrTypes::NeighborID, Neighbor*>   _neighbors;
01225 
01230     map<IPv4, OlsrTypes::NeighborID>        _neighbor_addr;
01231 
01239     map<OlsrTypes::TwoHopLinkID, TwoHopLink*>       _twohop_links;
01240 
01246     map<pair<IPv4, IPv4>, OlsrTypes::TwoHopLinkID>  _twohop_link_addrs;
01247 
01251     map<OlsrTypes::TwoHopNodeID, TwoHopNeighbor*>   _twohop_nodes;
01252 
01257     map<IPv4, OlsrTypes::TwoHopNodeID>          _twohop_node_addrs;
01258 };
01259 
01260 #endif // __OLSR_NEIGHBORHOOD_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations