spfarea.c

BCAST Implementation for NS2

{
    rtype = 0;
    asbr_link = 0;
    asbr = 0;
    VL = 0;
    ap = a;
}

/* Destructor for an area border router. Make sure that
 * it is removed from the ASBR's component list.
 */

RTRrte::~RTRrte()

{   
    RTRrte **pptr;
    RTRrte *ptr;

    if (!asbr)
	return;
    for (pptr = &asbr->parts; (ptr = *pptr); pptr = &ptr->asbr_link) {
	if (ptr == this) {
	    *pptr = asbr_link;
	    break;
	}
    }
}

/* Constructor for an area aggregate. Add
 * to area's AVL tree.
 */

Range::Range(SpfArea *a, uns32 net, uns32 mask) : AVLitem(net, mask)

{
    ap = a;
    r_rte = inrttbl->add(net, mask);
    r_area = ap->id();
    r_active = false;
    r_cost = 0;
    ap->ranges.add(this);
}

/* Add or delete a given area range.
 * If the area has not yet been defined, add
 * it to the configuration with default parameters
 * After adding or deleting, search through the
 * routing table to see whether any summary-LSAs
 * should be originated or withdrawn
 */

void OSPF::cfgRnge(CfgRnge *m, int status)

{
    SpfArea *ap;
    Range *rp;
    INrte *rangerte;

    // Allocate new area, if necessary
    if (!(ap = ospf->FindArea(m->area_id)))
	ap = new SpfArea(m->area_id);
    if (!(rp = (Range *) ap->ranges.find(m->net, m->mask))) {
	rp = new Range(ap, m->net, m->mask);
	rp->ap = ap;
    }
    if (status == DELETE_ITEM) {
	ap->ranges.remove(rp);
	delete rp;
    }
    else {
	rp->updated = true;
	ap->updated = true;
	if ((rp->r_suppress = (m->no_adv != 0)))
	    rp->r_cost = LSInfinity;
    }
    // Can't use rp now
    rangerte = inrttbl->add(m->net, m->mask);
    ospf->redo_aggregate(rangerte, ap);
}

static void range_to_cfg(const Range& r, struct CfgRnge& msg)

{
    msg.area_id = r.r_area;
    msg.net = r.r_rte->net();
    msg.mask = r.r_rte->mask();
    msg.no_adv = r.r_suppress;
}

bool OSPF::qryRnge(struct CfgRnge& msg,
		   aid_t	   area_id,
		   InAddr	   net,
		   InMask	   mask) const

{
    SpfArea *ap = ospf->FindArea(area_id);
    if (ap == 0) 
	return false;

    Range *rp = (Range*) ap->ranges.find(net, mask);
    if (rp == 0)
	return false;

    range_to_cfg(*rp, msg);
    return true;
}

void OSPF::getRnges(std::list<CfgRnge>& l, aid_t area_id) const

{
    SpfArea *ap = ospf->FindArea(area_id);
    if (ap == 0) return;

    AVLsearch riter(&ap->ranges);
    Range *rp;
    while ((rp = (Range*)riter.next())) {
	CfgRnge msg;
	range_to_cfg(*rp, msg);
	l.push_back(msg);
    }
}

/* Configuration of an aggregate has changed. Reoriginate all
 * necessary summary-LSAs.
 */

void OSPF::redo_aggregate(INrte *rangerte, SpfArea *)

{
    SpfArea *ap;
    INiterator iter(inrttbl);
    INrte *rte;
    AreaIterator a_iter(ospf);

    // Set range flag, if appropriate
    // Reuse ap
    rangerte->range = false;
    while ((ap = a_iter.get_next()))
	if (ap->ranges.find(rangerte->net(), rangerte->mask())) {
	    rangerte->range = true;
	    break;
	}
    
    // Possibly redo summary-LSAs
    // By forcing routing calculation to run again,
    // and everything under the aggregate to read as "changed"
    ospf->full_sched = true;
    iter.seek(rangerte);
    rte = rangerte;
    for (; rte != 0 && rte->is_child(rangerte); rte = iter.nextrte())
	rte->changed = true;
}

/* Range not listed in a reconfig. Delete it.
 */

void Range::clear_config()

{
    ap->ranges.remove(this);
    ospf->redo_aggregate(r_rte, ap);
    delete this;
}

/* Update the cost of all area address ranges containing
 * the given intra-area route.
 * Stop when we find the first matching range, so as
 * to not advertise less specific aggregates unless necessary.
 */

void OSPF::update_area_ranges(INrte *rte)

{
    INrte *prefix;
    SpfArea *ap;

    if (!(ap = FindArea(rte->area())))
	return;
    for (prefix = rte; prefix; prefix = prefix->prefix()) {
	Range *range;
	if (!prefix->is_range())
	    continue;
	range = (Range *) ap->ranges.find(prefix->net(), prefix->mask());
	if (range) {
	    range->r_active = true;
	    if (!range->r_suppress && range->r_cost < rte->cost)
		range->r_cost = rte->cost;
	    return;
	}
    }
}


/* Determine whether a given intra-area routing table entry
 * is within a configured area aggregate. Used when constructing
 * summary-LSAs.
 * Start looking at prefix, because if range configured for
 * the exact INrte this routine will not be called.
 */

int INrte::within_range()

{
    INrte *rte;
    SpfArea *ap;

    if (!(ap = ospf->FindArea(area())))
	return(false);
    for (rte = _prefix; rte; rte = rte->_prefix) {
	if (!rte->range)
	    continue;
	else if (ap->ranges.find(rte->net(), rte->mask()))
	    return(true);
    }

    return(false);
}

/* A given net/mask may be configured as an aggregate for
 * multiple areas. If so, pick the aggregate that is active
 * and has the smallest cost. This is what will be advertised
 * in summary-LSAs.
 */

Range   *OSPF::GetBestRange(INrte *rte)

{
    Range *best;
    AreaIterator a_iter(ospf);
    SpfArea *ap;

    best = 0;
    while ((ap = a_iter.get_next())) {
	Range *range;
	range = (Range *) ap->ranges.find(rte->net(), rte->mask());
	if (!range || !range->r_active)
	    continue;
	else if (!best)
	    best = range;
	else if (best->r_cost > range->r_cost)
	    best = range;
    }

    if (best &&
	rte->intra_area() &&
	rte->area() != best->r_area &&
	rte->cost < best->r_cost)
	return(0);

    return(best);
}

/* Invalidate all the area address ranges, in preparation
 * for the next scan of the routing table.
 */

void OSPF::invalidate_ranges()

{
    AreaIterator a_iter(ospf);
    SpfArea *ap;

    while ((ap = a_iter.get_next())) {
	Range *range;
	AVLsearch riter(&ap->ranges);
	while ((range = (Range *)riter.next())) {
	    range->r_active = false;
	    range->r_cost = 0;
	}
    }
}

/* Attempt to readvertise summary-LSAs for all configured
 * area address ranges. Since we are not forcing advertisements,
 * only those that have changed will really get advertised.
 */

void OSPF::advertise_ranges()

{
    AreaIterator a_iter(ospf);
    SpfArea *ap;

    while ((ap = a_iter.get_next())) {
	Range *range;
	AVLsearch riter(&ap->ranges);
	while ((range = (Range *)riter.next()))
	    sl_orig(range->r_rte);
    }
}

/* Initialize the aggregate adjacency information to a given
 * neighbor.
 */

PPAdjAggr::PPAdjAggr(rtid_t n_id) : AVLitem(n_id, 0)

{
    nbr_cost = 0;
    first_full = 0;
    nbr_mpath = 0;
    n_adjs = 0;
}

/* The state of one of the conversations with a neighbor
 * has changed. If this is a point-to-point link, and we
 * are limiting the number of adjacencies, we may now have
 * to take one ore more of the following actions:
 * a) attempt to establish additional adjacencies
 * b) re-originate our router-LSA
 * c) rerun our routing calculation.
 *
 * If OSPF::PPAdjLimit is non-zero, we limit the number
 * of point-to-point links which will become adjacent
 * to a particular neighbor. If the "enlist" parameter
 * is true, and there are insufficient adjacencies, we
 * add all the 2-Way point-to-point interfaces to the
 * pending adjacency list, since we don't know which
 * ones we will be able to advance.
 */


void SpfArea::adj_change(SpfNbr *xnp, int n_ostate)

{
    bool more_needed;
    PPAdjAggr *adjaggr;
    IfcIterator iter(this);
    SpfIfc *ip;
    rtid_t n_id=xnp->id();
    int n_state=xnp->state();
    bool rescan=false;
    uns16 old_cost;
    SpfIfc *old_first;
    MPath *old_mpath;

    if (xnp->ifc()->type() != IFT_PP)
        return;
    if (ospf->PPAdjLimit == 0)
        return;
    // If necessary, allocate adjacency bookkeeping class
    if (!(adjaggr = (PPAdjAggr *)AdjAggr.find(n_id, 0))) {
        adjaggr = new PPAdjAggr(n_id);
	AdjAggr.add(adjaggr);
    }
    /* Update number of current adjacencies, and determine
     * whether a complete rescan is necessary.
     */
    if (n_state <= NBS_2WAY && n_ostate >= NBS_EXST)
        adjaggr->n_adjs--;
    else if (n_ostate <= NBS_2WAY && n_state >= NBS_EXST)
        adjaggr->n_adjs++;
    if ((n_state >= NBS_2WAY && n_ostate < NBS_2WAY) ||
	(n_state < NBS_2WAY && n_ostate >= NBS_2WAY) ||
	(n_ostate == NBS_FULL || n_state == NBS_FULL))
        rescan = true;

    // End with higher router ID will decide
    more_needed = (ospf->my_id() >n_id) && (adjaggr->n_adjs< ospf->PPAdjLimit);
    // Rescan only on relevant changes
    if (!rescan && !more_needed)
        return;
    // Remember old parameters
    old_cost = adjaggr->nbr_cost;
    old_first = adjaggr->first_full;
    old_mpath = adjaggr->nbr_mpath;
    // Reset parameters before scan
    adjaggr->nbr_cost = 0;
    adjaggr->first_full = 0;
    adjaggr->nbr_mpath = 0;
    /* Find first adjacency, best bidirectional
     * link cost, and calculate the multipath entry
     * of those interfaces having the best cost.
     * Also, modify list of pending adjacencies depending
     * upon whether more are needed.
     */
    while ((ip = iter.get_next())) {
        SpfNbr *np;
        if (ip->type() != IFT_PP)
	    continue;
	if (!(np = ip->if_nlst))
	    continue;
	// To this same neighbor?
	if (np->id() != n_id)
	    continue;
	if (np->state() == NBS_FULL && adjaggr->first_full == 0)
	    adjaggr->first_full = ip;
	if (np->state() == NBS_2WAY) {
	    if (!more_needed)
	        np->DelPendAdj();
	    else
	        np->AddPendAdj();
	}
	if (np->state() >= NBS_2WAY) {
	    if (adjaggr->nbr_cost == 0 || adjaggr->nbr_cost > ip->cost()) {
	        adjaggr->nbr_cost = ip->cost();
		adjaggr->nbr_mpath = 0;
	    }
	    if (adjaggr->nbr_cost == ip->cost()) {
		MPath *add_nh;
		add_nh = MPath::create(ip, np->addr());
		adjaggr->nbr_mpath = MPath::merge(adjaggr->nbr_mpath, add_nh);
	    }
	}
    }
    // Need to re-originate router-LSA?
    if (adjaggr->nbr_cost != old_cost || adjaggr->first_full != old_first)
        rl_orig();
    // Need to rerun routing calculation?
    if (adjaggr->nbr_mpath != old_mpath)
        ospf->full_sched = true;
}