xorp

routing_table.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8:
00003 
00004 // Copyright (c) 2001-2012 XORP, Inc and Others-2009 XORP, Inc.
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/ospf/routing_table.hh,v 1.49 2008/11/21 00:32:11 atanu Exp $
00022 
00023 #ifndef __OSPF_ROUTING_TABLE_HH__
00024 #define __OSPF_ROUTING_TABLE_HH__
00025 
00026 #include <libxorp/trie.hh>
00027 
00031 template <typename A>
00032 class RouteEntry {
00033  public:
00037     enum PathType {
00038     intra_area = 1,
00039     inter_area = 2,
00040     type1 = 3,
00041     type2 = 4
00042     };
00043 
00044     RouteEntry() : _destination_type(OspfTypes::Router),
00045            _discard(false),
00046            _direct(false),
00047            _address(0),
00048            _id(0),
00049            _area_border_router(false),
00050            _as_boundary_router(false),
00051            _area(0),
00052            _path_type(intra_area),
00053            _cost(0),
00054            _type_2_cost(0),
00055            _nexthop(A::ZERO()),
00056            _nexthop_id(OspfTypes::UNUSED_INTERFACE_ID),
00057            _advertising_router(0),
00058            _filtered(false)
00059     {}
00060 
00061     void set_destination_type(OspfTypes::VertexType destination_type) {
00062     _destination_type = destination_type;
00063     }
00064 
00065     OspfTypes::VertexType get_destination_type() const {
00066     return _destination_type;
00067     }
00068 
00069     void set_discard(bool discard) {
00070     _discard = discard;
00071     }
00072 
00073     bool get_discard() const {
00074     return _discard;
00075     }
00076 
00077     void set_directly_connected(bool direct) {
00078     _direct = direct;
00079     }
00080 
00081     bool get_directly_connected() const {
00082     return _direct;
00083     }
00084 
00085     void set_address(uint32_t address) {
00086     XLOG_ASSERT(OspfTypes::Network == _destination_type);
00087     _address = address;
00088     }
00089 
00090     uint32_t get_address() const {
00091     XLOG_ASSERT(OspfTypes::Network == _destination_type);
00092     return _address;
00093     }
00094 
00095     void set_router_id(OspfTypes::RouterID id) {
00096     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00097     _id = id;
00098     }
00099 
00100     OspfTypes::RouterID get_router_id() const {
00101     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00102     return _id;
00103     }
00104 
00105     void set_area_border_router(bool area_border_router) {
00106     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00107     _area_border_router = area_border_router;
00108     }
00109 
00110     bool get_area_border_router() const {
00111     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00112     return _area_border_router;
00113     }
00114 
00115     void set_as_boundary_router(bool as_boundary_router) {
00116     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00117     _as_boundary_router = as_boundary_router;
00118     }
00119 
00120     bool get_as_boundary_router() const {
00121     XLOG_ASSERT(OspfTypes::Router == _destination_type);
00122     return _as_boundary_router;
00123     }
00124 
00125     void set_area(OspfTypes::AreaID area) {
00126     _area = area;
00127     }
00128 
00129     OspfTypes::AreaID get_area() const {
00130     return _area;
00131     }
00132 
00133     void set_path_type(PathType path_type) {
00134     _path_type = path_type;
00135     }
00136 
00137     PathType get_path_type() const {
00138     return _path_type;
00139     }
00140 
00141     void set_cost(uint32_t cost) {
00142     _cost = cost;
00143     }
00144 
00145     uint32_t get_cost() const {
00146     return _cost;
00147     }
00148 
00149     void set_type_2_cost(uint32_t type_2_cost) {
00150     _type_2_cost = type_2_cost;
00151     }
00152 
00153     uint32_t get_type_2_cost() const {
00154     return _type_2_cost;
00155     }
00156 
00157     void set_nexthop(A nexthop) {
00158     _nexthop = nexthop;
00159     }
00160 
00161     A get_nexthop() const {
00162     return _nexthop;
00163     }
00164 
00165     void set_nexthop_id(uint32_t nexthop_id) {
00166     _nexthop_id = nexthop_id;
00167     }
00168 
00169     uint32_t get_nexthop_id() {
00170     return _nexthop_id;
00171     }
00172 
00173     void set_advertising_router(uint32_t advertising_router) {
00174     _advertising_router = advertising_router;
00175     }
00176 
00177     uint32_t get_advertising_router() const {
00178     return _advertising_router;
00179     }
00180 
00181     void set_lsa(Lsa::LsaRef lsar) {
00182     _lsar = lsar;
00183     }
00184 
00185     Lsa::LsaRef get_lsa() const {
00186     return _lsar;
00187     }
00188 
00189     void set_filtered(bool filtered) {
00190     _filtered = filtered;
00191     }
00192 
00193     bool get_filtered() const {
00194     return _filtered;
00195     }
00196 
00197     string str() {
00198     string output;
00199 
00200     output = c_format("RouteEntry: ");
00201     output += c_format("%s ", OspfTypes::Router == _destination_type ?
00202               "Router" : "Network");
00203     output += c_format("%s", _discard ? "discard " : "");
00204     output += c_format("%s", _direct ? "direct " : "");
00205     if (OspfTypes::Network == _destination_type)
00206         output += c_format("\nAddress %s ", pr_id(_address).c_str());
00207     if (OspfTypes::Router == _destination_type) {
00208         output += c_format("\nRouter ID %s ", pr_id(_id).c_str());
00209         if (_area_border_router)
00210         output += c_format("ABR ");
00211         if (_as_boundary_router)
00212         output += c_format("ASBR ");
00213     }
00214     output += c_format("\nArea %s ", pr_id(_area).c_str());
00215     switch(_path_type) {
00216     case intra_area:
00217         output += c_format("\nintra area cost %d ", _cost);
00218         break;
00219     case inter_area:
00220         output += c_format("\ninter area %d ", _cost);
00221         break;
00222     case type1:
00223         output += c_format("\ntype1 %d ", _cost);
00224         break;
00225     case type2:
00226         output += c_format("\ntype2 %d ", _type_2_cost);
00227         break;
00228     }
00229 
00230     output += c_format("\nnexthop %s ", cstring(_nexthop));
00231     output += c_format("\nadvertising router %s ", 
00232                pr_id(_advertising_router).c_str());
00233 
00234     output += c_format("\n%s ", cstring(*_lsar));
00235 
00236     return output;
00237     }
00238 
00239  private:
00240     OspfTypes::VertexType _destination_type;
00241     bool _discard;          // True if this is a discard route.
00242     bool _direct;           // True if directly connected,
00243                     // this route should not be
00244                     // sent to the RIB.
00245 
00246     uint32_t _address;          // If dest type is Network
00247 
00248     OspfTypes:: RouterID _id;       // If dest type is Router
00249                     // The router that is referred too.
00250                     // For a Router-LSA this is
00251                     // the LSA itself. For Summary
00252                     // LSA that refers to a router
00253                     // (Type 4) its the AS
00254                     // boundary router.
00255 
00256     bool _area_border_router;       // Only valid if dest type is router
00257     bool _as_boundary_router;       // Only valid if dest type is router
00258 
00259     OspfTypes::AreaID _area;        // Associated area.
00260     PathType _path_type;
00261     uint32_t _cost;
00262     uint32_t _type_2_cost;
00263 
00264     A _nexthop;
00265     uint32_t _nexthop_id;
00266     uint32_t _advertising_router;   // The router ID from the LSA
00267                     // that generated this route.
00268 
00269     Lsa::LsaRef _lsar;          // LSA that contributed to this route.
00270                     // Currently only used for debugging.
00271 
00272 
00273     bool _filtered;         // True if this route has been
00274                     // filtered by policy.
00275 };
00276 
00280 template <typename A>
00281 class InternalRouteEntry {
00282  public:
00283     InternalRouteEntry() : _winner(0)
00284     {}
00285 
00286     InternalRouteEntry(const InternalRouteEntry& rhs) {
00287     copy(rhs);
00288     }
00289 
00290     InternalRouteEntry& operator=(const InternalRouteEntry& rhs) {
00291         if(&rhs == this)
00292             return *this;
00293         copy(rhs);
00294 
00295         return *this;
00296     }
00297 
00298     void copy(const InternalRouteEntry& rhs) {
00299     _entries = rhs._entries;
00300     reset_winner();
00301     }
00302 
00307     bool add_entry(OspfTypes::AreaID area, const RouteEntry<A>& rt);
00308     
00309     bool replace_entry(OspfTypes::AreaID area, const RouteEntry<A>& rt);
00310     
00320     bool delete_entry(OspfTypes::AreaID, bool& winner_changed);
00321 
00325     RouteEntry<A>& get_entry() const;
00326 
00335     bool get_entry(OspfTypes::AreaID area, RouteEntry<A>& rt) const;
00336 
00340     bool empty() const {
00341     return 0 == _winner;
00342     }
00343 
00344     string str();
00345  private:
00346     RouteEntry<A> *_winner; // Winning route.
00347     map<OspfTypes::AreaID, RouteEntry<A> > _entries; // Routes by area.
00348 
00349     bool reset_winner();
00350 };
00351 
00355 template <typename A>
00356 class Adv {
00357  public:
00361     void clear_area(OspfTypes::AreaID area);
00362 
00370     bool add_entry(OspfTypes::AreaID area, uint32_t adv,
00371            const RouteEntry<A>& rt, const char* dbg);
00372 
00380     bool replace_entry(OspfTypes::AreaID area, uint32_t adv,
00381                const RouteEntry<A>& rt, const char* dbg);
00382 
00392     bool lookup_entry(OspfTypes::AreaID area, uint32_t adv,
00393               RouteEntry<A>& rt) const;
00394 
00395  private:
00396     typedef map<OspfTypes::RouterID, RouteEntry<A> > AREA;
00397     typedef map<OspfTypes::AreaID, AREA> ADV;
00398     ADV _adv;
00399 };
00400 
00401 template <typename A>
00402 class RoutingTable {
00403  public:
00404     RoutingTable(Ospf<A> &ospf)
00405     : _ospf(ospf), _in_transaction(false), _current(0), _previous(0)
00406     {}
00407 
00408     ~RoutingTable() {
00409     delete _current;
00410     delete _previous;
00411 
00412     _current = _previous = 0;
00413     }
00414 
00419     void begin(OspfTypes::AreaID area);
00420 
00421     bool add_entry(OspfTypes::AreaID area, IPNet<A> net,
00422            const RouteEntry<A>& rt, const char* message);
00423 
00424     bool replace_entry(OspfTypes::AreaID area, IPNet<A> net,
00425                const RouteEntry<A>& rt);
00426 
00430     bool delete_entry(OspfTypes::AreaID area, IPNet<A> net);
00431 
00436     void end();
00437     
00446     bool lookup_entry(A router, RouteEntry<A>& rt);
00447 
00457     bool lookup_entry(OspfTypes::AreaID area, A router, RouteEntry<A>& rt);
00458 
00467     bool lookup_entry(IPNet<A> net, RouteEntry<A>& rt);
00468 
00478     bool lookup_entry(OspfTypes::AreaID area, IPNet<A> net, RouteEntry<A>& rt);
00479 
00489     bool lookup_entry_by_advertising_router(OspfTypes::AreaID area,
00490                         uint32_t adv,
00491                         RouteEntry<A>& rt);
00501     bool longest_match_entry(A router, RouteEntry<A>& rt);
00502 
00509     void remove_area(OspfTypes::AreaID area);
00510 
00514     void push_routes();
00515 
00516  private:
00517     Ospf<A>& _ospf;         // Reference to the controlling class.
00518     bool _in_transaction;       // Flag to verify that the
00519                     // routing table is only
00520                     // manipulated during a transaction.
00521 
00522     Adv<A> _adv;            // Routing entries indexed by
00523                     // advertising router.
00524 
00525     Trie<A, InternalRouteEntry<A> > *_current;
00526     Trie<A, InternalRouteEntry<A> > *_previous;
00527 
00528 
00529     // Yes the RouteEntry contains the area, nexthop and metric but they
00530     // are functionally distinct.
00531     bool add_route(OspfTypes::AreaID area, IPNet<A> net, A nexthop,
00532            uint32_t metric, RouteEntry<A>& rt, bool summaries);
00533     bool delete_route(OspfTypes::AreaID area, IPNet<A> net, RouteEntry<A>& rt,
00534               bool summaries);
00535     bool replace_route(OspfTypes::AreaID area, IPNet<A> net, A nexthop,
00536                uint32_t metric, RouteEntry<A>& rt,
00537                RouteEntry<A>& previous_rt,
00538                OspfTypes::AreaID previous_area);
00539 
00543     bool do_filtering(IPNet<A>& net, A& nexthop, uint32_t& metric,
00544               RouteEntry<A>& rt, PolicyTags& policytags);
00545 };
00546 
00547 #if 0
00548 template <typename A>
00549 class RouteEntry {
00550  public:
00551     list<A> _nexthops;      // Possible nexthops for this route
00552 
00553     bool _discard;      // True if this is a discard route.
00554     uint32_t _users;        // Only valid if this is a discard
00555                 // route. The number of routes below
00556                 // the discard route.
00557     
00558     OspfTypes::AreaID _area;    // Area the LSA came from.
00559     list<Lsa::LsaRef> lsars;    // LSAs the routes came from.
00560     bool _modified;     // True if this route has been
00561                 // modified in the last sweep.
00562 };
00563 
00564 template <typename A>
00565 class RoutingTable {
00566  public:
00567     RoutingTable(Ospf<A> &ospf)
00568     : _ospf(ospf)
00569     {}
00570 
00571     void begin();
00572 
00581     bool add_route(IPNet<A> net,
00582            A nexthop,
00583            uint32_t metric,
00584            bool equal);
00585 
00594     bool replace_route(IPNet<A> net,
00595                A nexthop,
00596                uint32_t metric,
00597                bool equal);
00598 
00602     bool delete_route(IPNet<A> net);
00603 
00604     void end();
00605     
00606  private:
00607     Ospf<A>& _ospf;         // Reference to the controlling class.
00608 
00609     Trie<A, RouteEntry<A> > _trie;
00610 };
00611 #endif
00612 
00613 #endif // __OSPF_ROUTING_TABLE_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations