mospf.c

BCAST Implementation for NS2

    mospf_dijkstra(group, cand, mcase == SourceIntraArea, downstream_nodes);
}

/* Do the Dijkstra calculation, MOSPF-style.
 */

void SpfArea::mospf_dijkstra(InAddr group, PriQ &cand, bool use_forward,
			     LsaList *ds_nodes)

{
    TNode *V;
    TNode *nh=0;

    mylsa = (rtrLSA *) ospf->myLSA(0, this, LST_RTR, ospf->my_id());

    while ((V = (TNode *) cand.priq_rmhead())) {
	int i, j;
	Link *lp;
	V->t_state = DS_ONTREE;
	/* If downstream, determine whether or not this
	 * branch of the delivery tree should be pruned.
	 */
	if ((V->t_downstream) && (nh = V->t_mospf_dsnode) != 0) {
	    byte mbr_ttl=255;
	    if (V->has_members(group))
	        mbr_ttl = V->t_ttl;
	    if (!nh->in_mospf_cache || nh->closest_member > mbr_ttl)
	        nh->closest_member = mbr_ttl;
	    if (!nh->in_mospf_cache) {
	        nh->in_mospf_cache = true;
		ds_nodes->addEntry(nh);
	    }
	}

	for (lp = V->t_links, i=0, j=0; lp != 0; lp = lp->l_next, i++) {
	    TLink *tlp;
	    TNode *W;
	    int il_type;
	    uns32 cost;
	    if (lp->l_ltype == LT_STUB)
	        continue;
	    tlp = (TLink *) lp;
	    // If adding root to SPF tree, set one or more incoming interfaces
	    if ((V == mylsa) &&
		(mylsa->t_parent != 0) &&
		(tlp->tl_nbr == mylsa->t_parent) &&
		(lp->l_ltype != LT_VL) &&
		(mylsa->t_parent->lsa_type != LST_NET || j == 0)) {
		mospf_in_phys[j++] = ifmap[i]->if_phyint;
	        mospf_in_count = j;
	    }
	    // Only use bidirectional links
	    if (!(W = tlp->tl_nbr))
		continue;
	    // Prune non-MOSPF nodes
	    if (!(W->lsa_opts & SPO_MC))
	        continue;
	    // Possibly add to candidate list
	    il_type = ((lp->l_ltype == LT_VL) ? ILVirtual : ILNormal);
	    cost = V->cost0;
	    cost += (use_forward ? tlp->l_fwdcst : tlp->tl_rvcst);
	    mospf_possibly_add(cand, W, cost, V, il_type, i);
	}
    }
}

/* Initialize the MOSPF candidate list when the source, or
 * an external source's forwarding address, belongs to
 * a local area. Splits into two cases depending on
 * whether the area in question is the same, or different
 * area than the one undergoing path calculation.
 */

int SpfArea::mospf_init_intra_area(PriQ &cand, INrte *rte, uns32 cost, 
				  int il_type)

{
    TNode *W;
    int mcase;

    if (rte->area() == a_id) {
	SpfData *rd;
	mcase = SourceIntraArea;
	rd = rte->r_ospf;
	W = (TNode *) ospf->FindLSA(0, this, rd->lstype, rd->lsid, rd->rtid);
	if (W == 0)
	    return(mcase);
	if (W->ls_id() == ospf->my_id()) {
	    // Record incoming interface
	    mospf_in_count = 1;
	    mospf_in_phys[0] = rte->ifc() ? rte->ifc()->if_phyint : -1;
	}
	mospf_possibly_add(cand, W, cost, 0, il_type, 0);
    }
    else {
        INrte *orte;
	mcase = SourceInterArea2;
	if ((orte = find_best_summlsa(rte)))
	    mospf_add_summlsas(cand, orte, cost);
	}

    return(mcase);
}

/* (Re)add a node to the candidate list. If you are trying
 * to replace the node on the candidate list, you must
 * do so according to the MOSPF tiebreakers: first cost,
 * the incoming link type, then if network is parent, and
 * finally those with the larger ID.
 */

void SpfArea::mospf_possibly_add(PriQ &cand, TNode *W, uns32 cost,
			      TNode *V, int il_type, int _index)

{
    SpfIfc *t_ifc;

    if (W->t_state == DS_ONTREE)
        return;
    if (W->t_state == DS_ONCAND) {
        PriQElt temp;
	temp.cost0 = cost;
	temp.cost1 = il_type;
	temp.tie1 = V ? V->ls_type() : 0;
	temp.tie2 = V ? V->ls_id() : 0;
	if (W->costs_less(&temp))
	    return;
	else
	    cand.priq_delete(W);
    }

    /* (Re)add to candidate list
     */

    W->t_state = DS_ONCAND;
    W->t_parent = V;
    W->cost0 = cost;
    W->cost1 = il_type;
    W->tie1 = V ? V->ls_type() : 0;
    W->tie2 = V ? V->ls_id() : 0;
    cand.priq_add(W);

    /* Set MOSPF parameters of node.
     * To forward to a downstream node, the packet's
     * TTL (after decrementing) must be strictly
     * larger that t_ttl.
     */

    if (!V)
	W->t_downstream = false;
    else if (V == mylsa) {
	W->t_downstream = true;
	W->t_direct = true;
	W->t_ttl = 0;
	t_ifc = ifmap[_index];
	W->t_mpath = MPath::create(t_ifc, 0);
	if (t_ifc && t_ifc->if_mcfwd == IF_MCFWD_MC)
	    W->t_mospf_dsnode = W;
	else
	    W->t_mospf_dsnode = 0;
    }
    else if ((W->t_downstream = V->t_downstream)) {
	W->t_direct = false;
	W->t_mpath = V->t_mpath;
	W->t_ttl = (V->lsa_type == LST_RTR) ? V->t_ttl+1 : V->t_ttl;
	if (V->lsa_type == LST_NET && V->t_direct && V->t_mospf_dsnode == 0)
	    W->t_mospf_dsnode = W;
	else
	    W->t_mospf_dsnode = V->t_mospf_dsnode;
    }

}

/* In the SourceInterArea2 case, we have to find the 
 * best matching summary-LSA so that we can perform
 * the same datagram path calculation that the
 * routers interior to the area will.
 * Those advertising a cost of LSInfinity or
 * advertised by now unreachable routers are ignored.
 */

INrte *SpfArea::find_best_summlsa(INrte *rte)

{
    INrte *orte;

    for (orte = rte; orte; orte = rte->prefix()) {
	summLSA *summ;
	for (summ = orte->summs; summ; summ = (summLSA *)summ->link) {
	    if (summ->area() != this)
	        continue;
	    if (summ->adv_cost == LSInfinity)
	        continue;
	    if ((summ->source && summ->source->type() == RT_SPF) ||
		(summ->adv_rtr() == ospf->my_id()))
	        return(orte);
	}
    }

    return(0);
}

/* Add the router-LSAs that have originated the summary
 * LSAs advertising the particular network to the candidate
 * list.
 */

void SpfArea::mospf_add_summlsas(PriQ &cand, INrte *rte, uns32 add_cost)

{
    summLSA *summ;

    for (summ = rte->summs; summ; summ = (summLSA *)summ->link) {
	if (summ->area() != this)
	    continue;
	if (summ->adv_cost == LSInfinity)
	    continue;
	if ((summ->source && summ->source->type() == RT_SPF) ||
	    (summ->adv_rtr() == ospf->my_id())) {
	    TNode *W;
	    lsid_t id;
	    id = summ->adv_rtr();
	    if ((W = (TNode *) ospf->FindLSA(0, this, LST_RTR, id, id)))
	        mospf_possibly_add(cand,W, summ->adv_cost+add_cost,
				   0,ILSummary, 0);
	}
    }
}

/* Add the router-LSAs of the routers advertising
 * ASEs to the candidate list. These routers can also
 * be advertising the ASE indirtectly, by advertising
 * ASBR-summaries for the ASE's originators.
 * Go through the ASEs first to determine the best cost.
 * This is forced by the type 1/2 metric split.
 */

void SpfArea::mospf_add_ases(PriQ &cand, INrte *rte)

{
    ASextLSA *ase;
    bool type1=false;
    uns32 type2_cost=LSInfinity;

    for (ase = rte->ases; ase; ase = (ASextLSA *)ase->link) {
	if ((ase->lsa_opts & SPO_MC) == 0)
	    continue;
	if (ase->adv_cost == LSInfinity)
	    continue;
	if ((!ase->source || !ase->source->valid()) &&
	    (ase->adv_rtr() != ospf->my_id()))
	    continue;
	if (ase->fwd_addr && !ase->fwd_addr->valid())
	    continue;
	if (ase->e_bit == 0) {
	    type1 = true;
	    break;
	}
	else if (ase->adv_cost < type2_cost)
	    type2_cost = ase->adv_cost;
    }

    for (ase = rte->ases; ase; ase = (ASextLSA *)ase->link) {
	TNode *W;
	lsid_t id;
	ASBRrte *asbr;
	asbrLSA *summ;
	uns32 cost;
	if ((ase->lsa_opts & SPO_MC) == 0)
	    continue;
	if (ase->adv_cost == LSInfinity)
	    continue;
	if ((!ase->source || !ase->source->valid()) &&
	    (ase->adv_rtr() != ospf->my_id()))
	    continue;
	if (type1) {
	    if (ase->e_bit)
	        continue;
	}
	else if (ase->adv_cost > type2_cost)
	    continue;
	// Add forwarding address to candidate list?
	cost = type1 ? ase->adv_cost : 0;
	if (ase->fwd_addr) {
	    INrte *match;
	    match = inrttbl->best_match(ase->fwd_addr->address());
	    if (match->intra_area())
	        mospf_init_intra_area(cand, match, cost, ILExternal);
	    else if (match->inter_area())
	        mospf_add_summlsas(cand, match, cost);
	    continue;
	}
	// Add ASBR to candidate list
	asbr = (ASBRrte *) ase->source;
	if ((id = asbr->rtrid()) == ospf->my_id() && rte->exdata) {
	    mospf_in_count = 1;
	    mospf_in_phys[0] = rte->exdata->phyint;
	}
	if ((W = (TNode *) ospf->FindLSA(0, this, LST_RTR, id, id)))
	    mospf_possibly_add(cand,W,cost,0,ILExternal, 0);
	for (summ = asbr->summs; summ; summ = (asbrLSA *)summ->link) {
	    if (summ->area() != this)
	        continue;
	    if (summ->adv_cost == LSInfinity)
	        continue;
	    if ((summ->source && summ->source->type() == RT_SPF) ||
		(summ->adv_rtr() == ospf->my_id())) {
	        id = summ->adv_rtr();
		if ((W = (TNode *) ospf->FindLSA(0, this, LST_RTR, id, id)))
		    mospf_possibly_add(cand, W, cost+summ->adv_cost,
				       0, ILSummary, 0);
	    }
	}
    }
}

/* Constructor for a cache entry.
 */

MCache::MCache()

{
    n_upstream = 0;
    up_phys = 0;
    n_downstream = 0;
    down_str = 0;
}

/* Cache entry destructor.
 */

MCache::~MCache()

{
    delete [] up_phys;
    delete [] down_str;
}

/* Construct the internal version of a multicast
 * cache entry.
 */

MospfEntry::MospfEntry(InAddr src, InAddr group) : AVLitem(src, group)

{
}

/* Add a cache entry that indicates that matching
 * multicast datagrams should not be forwarded.
 * Only called if we already know that the cache
 * entry doesn't exist.
 */

void OSPF::add_negative_mcache_entry(InAddr src, INrte *srte, InAddr group)

{
    MospfEntry *entry;
    entry = new MospfEntry(src, group);
    entry->srte = srte;
    multicast_cache.add(entry);
    sys->add_mcache(src, group, &entry->val);
}