mospf.c

BCAST Implementation for NS2

/*
 *   OSPFD routing daemon
 *   Copyright (C) 1998 by John T. Moy
 *   
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version 2
 *   of the License, or (at your option) any later version.
 *   
 *   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.  See the
 *   GNU General Public License for more details.
 *   
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/* Routines implementing MOSPF.
 */

#include "ospfinc.h"
#include "system.h"
#include "mospf.h"
#include "phyint.h"

/* Clear the entire MOSPF cache on an internal topology change.
 * Also called when the distance to
 * and AS boundary router changes.
 */

void OSPF::mospf_clear_cache()

{
    clear_mospf = false;
    MospfEntry *entry;
    AVLsearch iter(&multicast_cache);

    // Delete from kernel
    while ((entry = (MospfEntry *)iter.next())) {
        InAddr src;
	InAddr group;
	src = entry->index1();
	group = entry->index2();
        sys->del_mcache(src, group);
    }
    // Remove all local entries too
    multicast_cache.clear();
}

/* Clear all sources falling into a particular
 * range. Called when a summary-LSA
 * changes; must clear everything in range
 * and not just best match sources because
 * of the SourceInterArea1 case (and also
 * stub area default route).
 */

void OSPF::mospf_clear_inter_source(INrte *rte)

{
    MospfEntry *entry;
    AVLsearch iter(&multicast_cache);

    if (rte == default_route) {
        clear_mospf = true;
	return;
    }

    // Delete from kernel
    iter.seek(rte->net(), 0);
    while ((entry = (MospfEntry *)iter.next())) {
        InAddr src;
	InAddr group;
	src = entry->index1();
	if (!rte->matches(src))
	    break;
	group = entry->index2();
        sys->del_mcache(src, group);
	multicast_cache.remove(entry);
    }
}

/* When an external route changes, must clear only
 * those entries whose best matching routing
 * table entry was (or is) rte.
 */

void OSPF::mospf_clear_external_source(INrte *rte)

{
    MospfEntry *entry;
    AVLsearch iter(&multicast_cache);

    // Delete from kernel
    iter.seek(rte->net(), 0);
    while ((entry = (MospfEntry *)iter.next())) {
        InAddr src;
	InAddr group;
	src = entry->index1();
	if (entry->srte == rte || mc_source(src) == rte) {
	    group = entry->index2();
	    sys->del_mcache(src, group);
	    multicast_cache.remove(entry);
	}
    }
}

/* Clear all cache entries for a given group. Called
 * when a group-membership-LSA changes.
 */

void OSPF::mospf_clear_group(InAddr group)

{
    MospfEntry *entry;
    AVLsearch iter(&multicast_cache);

    // Delete from kernel
    while ((entry = (MospfEntry *)iter.next())) {
	if (group == entry->index2()) {
	    sys->del_mcache(entry->index1(), group);
	    multicast_cache.remove(entry);
	}
    }
}

/* Determine whether MOSPF is enabled on an interface,
 * so we can tell whether to set the MC-bit in the
 * associated network-LSA.
 */

bool SpfIfc::mospf_enabled()
{
    return (ospf->mospf_enabled() && (if_mcfwd != IF_MCFWD_BLOCKED));
}

/* Request to calculate a multicast routing table entry
 * for a given packet, from which we extract the source
 * and destination.
 */

MCache *OSPF::mclookup(InAddr src, InAddr group)


{
    INrte *rte;
    AreaIterator a_iter(ospf);
    SpfArea *ap;
    uns32 best_cost = 0;
    int best_case = 0;
    SpfArea *best_ap = 0;
    LsaList ds_nodes;
    MospfEntry *entry;
    MospfEntry *new_entry;
    LsaListIterator *l_iter;
    TNode *V;
    MCache *ce;
    int i;
    int n_out;
    PhyInt *phyp;

    // Local scope multicast?
    if ((group & 0xffffff00) == 0xe0000000)
        return(0);

    // If already calculated, just download again
    if ((entry = (MospfEntry *)multicast_cache.find(src, group))) {
        sys->add_mcache(src, group, &entry->val);
	return(&entry->val);
    }
    // Valid multicast source?
    if (!(rte = mc_source(src))) {
        add_negative_mcache_entry(src, 0, group);
	return(0);
    }

    // No interfaces installed in cache entry yet
    AVLsearch iter2(&ospf->phyints);
    while ((phyp = (PhyInt *)iter2.next()))
        phyp->cached = false;

    // Calculate multicast path through each area
    while ((ap = a_iter.get_next())) {
        uns32 cost;
	int path_case;
        ap->mospf_path_calc(group, rte, path_case, cost, &ds_nodes);
	// Merge downstream interfaces
	if (ap->mospf_in_count == 0)
	    continue;
	else if (!best_ap)
	    goto new_best_area;
	else if (path_case < best_case)
	    goto new_best_area;
	else if (path_case > best_case)
	    continue;
	else if (ap->a_id == 0)
	    goto new_best_area;
	else if (best_ap->a_id == 0)
	    continue;
	else if (cost < best_cost)
	    goto new_best_area;
	else if (cost > best_cost)
	    continue;
	else if (ap->a_id < best_ap->a_id)
	    continue;
      new_best_area:
	    best_ap = ap;
	    best_case = path_case;
	    best_cost = cost;
    }

    // If no incoming interface, add negative cache entry
    if (!best_ap) {
        add_negative_mcache_entry(src, rte, group);
	return(0);
    }
    /* Allocate new multicast cache entry
     * Copying incoming interface(s) from the winning
     * area class.
     */
    new_entry = new MospfEntry(src, group);
    new_entry->srte = rte;
    ce = &new_entry->val;
    ce->mask = rte->mask();
    new_entry->val.n_upstream = best_ap->mospf_in_count;
    new_entry->val.up_phys = new int[best_ap->mospf_in_count];
    memcpy(new_entry->val.up_phys, best_ap->mospf_in_phys,
	   best_ap->mospf_in_count * sizeof(int));

    // Calculate downstream interfaces and neighbors
    n_out = ds_nodes.count() + phyints.size();
    new_entry->val.n_downstream = ds_nodes.count();
    ce->down_str = new DownStr[n_out];
    l_iter = new LsaListIterator(&ds_nodes);
    for (i = 0; (V = (TNode *)l_iter->get_next()); i++) {
        SpfIfc *o_ifp;
	l_iter->remove_current();
	V->in_mospf_cache = false;
	o_ifp = ospf->find_ifc(V->t_mpath->NHs[0].if_addr,
			       V->t_mpath->NHs[0].phyint);
	ce->down_str[i].phyint = o_ifp->if_phyint;
	phyp = (PhyInt *)ospf->phyints.find(o_ifp->if_phyint, 0);
	phyp->cached = true;
	ce->down_str[i].ttl = V->closest_member;
	if (V->lsa_type == LST_NET || o_ifp->type() == IFT_PP)
	    ce->down_str[i].nbr_addr = 0;
	else
	    ce->down_str[i].nbr_addr = V->ospf_find_gw(V->t_parent,0,0);
    }
    delete l_iter;

    // Add stub interfaces from local group database
    AVLsearch iter(&ospf->phyints);
    while ((phyp = (PhyInt *)iter.next())) {
	int phyint=(int)phyp->index1();
	if (phyp->cached)
	    continue;
	if (ce->valid_incoming(phyint))
	    continue;
	if (!phyp->mospf_ifp)
	    continue;
	if (phyp->mospf_ifp->is_multi_access() &&
	    phyp->mospf_ifp->if_nfull != 0)
	    continue;
	if (!ospf->local_membership.find(group, phyint))
	    continue;
	    i = new_entry->val.n_downstream;
	    ce->down_str[i].phyint = phyint;
	ce->down_str[i].ttl = 0;
	    ce->down_str[i].nbr_addr = 0;
	    new_entry->val.n_downstream++;
    }

    if (spflog(MCACHE_REQ, 5)) {
        log(&src);
	log("->");
	log(&group);
    }

    multicast_cache.add(new_entry);
    sys->add_mcache(src, group, &new_entry->val);
    return(&new_entry->val);
}

/* Find the routing table entry corresponding to the
 * multicast datagram's source.
 */

INrte *OSPF::mc_source(InAddr src)

{
    INrte *rte;

    if (!(rte = inrttbl->best_match(src)))
	return(0);
    if (rte->intra_AS())
        return(rte);
    // External multicast source
    for (; rte; rte = rte->prefix()) {
	ASextLSA *ase;
	for (ase = rte->ases; ase; ase = (ASextLSA *)ase->link) {
	    if (ase->lsa_age() == MaxAge)
		continue;
	    if ((ase->lsa_opts & SPO_MC) != 0)
		return(rte);
	}
    }
    return(0);
}

/* Calculate the path of a multicast datagram through a
 * given area. Returns the incoming interface if it might
 * be chosen as the one for the cache entry (excludes
 * virtual links, summary-links and AS-external-links).
 */

void SpfArea::mospf_path_calc(InAddr group, INrte *rte, int &mcase,
			      uns32 &cost, LsaList *downstream_nodes)

{
    PriQ cand;
    rtrLSA *rtr;
    netLSA *net;
    rtrLSA *mylsa;

    // Initialize temporary area within area class
    if (size_mospf_incoming < n_active_if) {
        delete [] mospf_in_phys;
	mospf_in_phys = new int[n_active_if];
	size_mospf_incoming = n_active_if;
    }

    // Initialize Dijkstra state
    mospf_in_count = 0;
    cost = Infinity;
    mylsa = (rtrLSA *) ospf->myLSA(0, this, LST_RTR, ospf->myid);
    if (mylsa == 0 || !mylsa->parsed || ifmap == 0)
	return;
    rtr = (rtrLSA *) rtrLSAs.sllhead;
    for (; rtr; rtr = (rtrLSA *) rtr->sll)
	rtr->t_state = DS_UNINIT;
    net = (netLSA *) netLSAs.sllhead;
    for (; net; net = (netLSA *) net->sll)
	net->t_state = DS_UNINIT;

    if (rte->intra_area())
        mcase = mospf_init_intra_area(cand, rte, 0, ILDirect);
    else if (is_stub()) {
        mcase = SourceStubExternal;
	mospf_add_summlsas(cand, default_route, 0);
    }
    else if (rte->inter_area()) {
        mcase = SourceInterArea1;
	mospf_add_summlsas(cand, rte, 0);
    }
    else {
        mcase = SourceExternal;
	mospf_add_ases(cand, rte);
    }

    // Do the main Dijkstra calculation