Source: ../../rib/rt_tab_extint.hh

Annotated List  Files  Globals  Hierarchy  Index  Top

// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-

// 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/rib/rt_tab_extint.hh,v 1.19 2009/01/05 18:31:07 jtc Exp $

#ifndef __RIB_RT_TAB_EXTINT_HH__
#define __RIB_RT_TAB_EXTINT_HH__

#include "rt_tab_base.hh"


/**
 * @short Make two route @ref RouteTables behave like one, while
 * resolving nexthops that are not immediate neighbors
 *
 * ExtIntTable takes two routing tables and combines them together to
 * form a single table, where routes for the same subnet with a lower
 * admin distance override those with a higher admin distance.  The
 * two parent tables are different: the Internal table takes routes
 * only from IGP protocols, and so the nexthops of routes it provides
 * are always immediate neighbors.  The External table takes routes
 * from EGP protocols, and so the nexthops of routes it provides may
 * not be immediate neighbors.  The ExtIntTable resolves the nexthops
 * of all routes it propagates downstream.  If a nexthop cannot be
 * resolved, it is not propagated downstream, but is stored pending
 * the arrival of a route that would permit the nexthop to be
 * resolved.
 *
 * An add_route request from a parent tables causes a lookup on the
 * other parent table.  If the route is better than the one from the
 * other table, or no route exists in the other table, then the new
 * route is passed downstream.
 *
 * An delete_route request from a parent table also causes a lookup on
 * the other parent table.  The delete_route is propagated downstream.
 * If an alternative route is found, then that is then propagated
 * downsteam as an add_route to replace the deleted route.
 *
 * Lookups from downsteam cause lookups on both parent tables.  The
 * better response is given.
 *
 * A RIB normally only has one ExtIntTable.
 */
template<class A>
class ExtIntTable : public RouteTable<A> {
public:
    /**
     * ExtIntTable Constructor.
     *
     * @param ext_table parent RouteTables supplying EGP routes.
     * @param int_table parent RouteTables supplying IGP routes.
     */
    ExtIntTable(RouteTable<A>* ext_table,
		RouteTable<A>* int_table);

    /**
     * An add_route request from a parent table causes a lookup on the
     * other parent table.  If the route is better than the one from the
     * other table, or no route exists in the other table then it is
     * passed downstream if nexthop resolution is successful.
     *
     * @param route the new route.
     * @param caller the parent table sending the new route.
     * @return XORP_OK on success, otherwise XORP_ERROR.
     */
    int add_route(const IPRouteEntry<A>& route, RouteTable<A>* caller);

    /**
     * An delete_route request from a parent table also causes a
     * lookup on the other parent table.  The delete_route is
     * propagated downstream.  If an alternative route is found and
     * nexthop resolution on it is successful, then it is then
     * propagated downsteam as an add_route to replace the deleted
     * route.
     *
     * @param route the route to be deleted.
     * @param caller the parent table sending the delete_route.
     * @return XORP_OK on success, otherwise XORP_ERROR.
     */
    int delete_route(const IPRouteEntry<A>* route, RouteTable<A>* caller);

    /**
     * Lookup a specific subnet.  The lookup will first look in the
     * ExtIntTable 's table of resolved routes - if there is a route
     * here, then this is returned.  Otherwise the lookup will be sent
     * to both parent tables.  If both give an answer, then the route
     * with the better admin_distance is returned, so long as it gives
     * a nexthop that is resolvable.
     *
     * @param net the subnet to look up.
     * @return a pointer to the route entry if it exists, NULL otherwise.
     */
    const IPRouteEntry<A>* lookup_route(const IPNet<A>& net) const;

    /**
     * Lookup an IP address to get the most specific (longest prefix
     * length) route that matches this address.  The lookup will be
     * sent to both parent tables and the ExtIntTable's internal table
     * of resolved_routes.  The most specific answer is returned, so
     * long as the nexthop resolves.  If more than one route has the
     * same prefix length, then the route with the better
     * admin_distance is returned.
     *
     * @param addr the IP address to look up.
     *
     * @return a pointer to the best most specific route entry if any
     * entry matches and its nexthop resolves, NULL otherwise.
     */
    const IPRouteEntry<A>* lookup_route(const A& addr) const;

    /**
     * Lookup an IP address to get the most specific (longest prefix
     * length) route that matches this address, along with the
     * RouteRange information for this address and route.  As with
     * lookup_route, this involves querying ExtIntTable's
     * resolved_routes table and possibly both parent tables.  The
     * best, most specific route is returned if the nexthop is
     * resolvable, and the tightest bounds on the answer are returned.
     *
     * @see RouteRange
     * @param addr the IP address to look up.
     * @return a pointer to a RouteRange class instance containing the
     * relevant answer.  It is up to the recipient of this pointer to
     * free the associated memory.
     */
    RouteRange<A>* lookup_route_range(const A& addr) const;

    /**
     * @return the table type (@ref TableType).
     */
    TableType type() const	{ return EXTINT_TABLE; }

    /**
     * replumb the parent tables, so that new_parent replaces old_parent
     *
     * @param old_parent the old parent table.
     * @param new_parent the new parent table.
     */
    void replumb(RouteTable<A>* old_parent, RouteTable<A>* new_parent);

    /**
     * Render this ExtIntTable as a string for debugging purposes.
     */
    string str() const;

private:
    typedef typename ResolvedIPRouteEntry<A>::RouteBackLink ResolvedRouteBackLink;
    typedef typename UnresolvedIPRouteEntry<A>::RouteBackLink UnresolvedRouteBackLink;

    int delete_ext_route(const IPRouteEntry<A>* route,
			 bool& is_delete_propagated);

    const ResolvedIPRouteEntry<A>* lookup_in_resolved_table(
	const IPNet<A>& ipv4net);

    void resolve_unresolved_nexthops(const IPRouteEntry<A>& route);

    const ResolvedIPRouteEntry<A>* resolve_and_store_route(
	const IPRouteEntry<A>& route,
	const IPRouteEntry<A>* nexthop_route);

    bool delete_unresolved_nexthop(const IPRouteEntry<A>* route);

    void recalculate_nexthops(const IPRouteEntry<A>& route);

    const ResolvedIPRouteEntry<A>* lookup_by_igp_parent(
	const IPRouteEntry<A>* route);

    const ResolvedIPRouteEntry<A>* lookup_next_by_igp_parent(
	const IPRouteEntry<A>* route,
	const ResolvedIPRouteEntry<A>* previous);

    const IPRouteEntry<A>* lookup_route_in_igp_parent(
	const IPNet<A>& subnet) const;
    const IPRouteEntry<A>* lookup_route_in_igp_parent(const A& addr) const;

    const IPRouteEntry<A>* lookup_route_in_egp_parent(
	const IPNet<A>& subnet) const;
    const IPRouteEntry<A>* lookup_route_in_egp_parent(const A& addr) const;

    RouteTable<A>*				_ext_table;
    RouteTable<A>*				_int_table;
    Trie<A, const ResolvedIPRouteEntry<A>* >	_ip_route_table;
    multimap<A, UnresolvedIPRouteEntry<A>* >	_ip_unresolved_nexthops;
    map<IPNet<A>, UnresolvedIPRouteEntry<A>* >	_ip_unresolved_table;

    // _ip_igp_parents gives us a fast way of finding a route
    // affected by a change in an igp parent route
    multimap<const IPRouteEntry<A>*, ResolvedIPRouteEntry<A>* > _ip_igp_parents;

    // _resolving_routes is a Trie of all the routes that are used to
    // resolve external routes
    Trie<A, const IPRouteEntry<A>* > _resolving_routes;
};

#endif // __RIB_RT_TAB_EXTINT_HH__