asexlsa.c

BCAST Implementation for NS2

	if (lsap->adv_rtr() == ospf->my_id())
	    return(lsap);
    }
    return(0);
}

/* Parse an AS-external-LSA.
 */

void ASextLSA::parse(LShdr *hdr)

{
    ASEhdr *ase;
    uns32 netno;
    uns32 mask;

    ase = (ASEhdr *) (hdr + 1);

    mask = ntoh32(ase->mask);
    netno = ls_id() & mask;
    if (!(rte = inrttbl->add(netno, mask))) {
	exception = true;
	return;
    }
    if ((ase->tos & ~E_Bit) != 0)
	exception = true;
    else if (lsa_length != sizeof(LShdr) + sizeof(ASEhdr))
	exception = true;
    adv_cost = (ase->hibyte << 16) + ntoh16(ase->metric);
    if (ase->faddr) {
	fwd_addr = fa_tbl->add(ntoh32(ase->faddr));
	fwd_addr->resolve();
    }
    else
	fwd_addr = 0;
    e_bit = (ase->tos & E_Bit) != 0;
    adv_tag = ntoh32(ase->rtag);
    // Link into routing table entry
    link = rte->ases;
    rte->ases = this;
    // Should we enter overflow state?
    if (rte != default_route && ++(ospf->n_exlsas) == ospf->ExtLsdbLimit)
	ospf->EnterOverflowState();
}

/* Unparse the AS-external-LSA.
 * Remove from the list in the routing table entry.
 */
void ASextLSA::unparse()

{
    ASextLSA *ptr;
    ASextLSA **prev;

    if (!rte)
	return;
    if (rte != default_route)
	ospf->n_exlsas--;
    // Unlink from list in routing table
    for (prev = &rte->ases; (ptr = *prev); prev = (ASextLSA **)&ptr->link)
	if (*prev == this) {
	    *prev = (ASextLSA *)link;
	    break;
	}
}

/* Enter the overflow state. Flush all locall-originated,
 * non-default ASEs. If configured, start the timer to exit
 * overflow state at a later time.
 */

void OSPF::EnterOverflowState()

{
    if (OverflowState)
	return;
    // Enter overflow state
    OverflowState = true;
    // Flush locally-originated LSAs
    reoriginate_ASEs();
    // Start exit overflow timer
    if (ExitOverflowInterval)
	oflwtim.start(ExitOverflowInterval*Timer::SECOND);
}

/* Exit overflow state. Go through the database of local ASE
 * origination directives, reoriginating all ASEs.
 * This will also reoriginate the default route, which
 * is harmless.
 */

void ExitOverflowTimer::action()

{
    if (ospf->n_exlsas >= ospf->ExtLsdbLimit)
	return;

    ospf->OverflowState = false;
    stop();
    // Reoriginate AS-external-LSAs
    // by rerunning AS-external routing calculations
    ospf->reoriginate_ASEs();
}

/* Reoriginate all the AS-external-LSAs. This is
 * performed when the overflow state changes, and
 * we are forced to withdraw or reinstate our
 * AS-external-LSAs.
 */

void OSPF::reoriginate_ASEs()

{
    INrte *rte;
    INiterator iter(inrttbl);

    while ((rte = iter.nextrte())) {
        if (rte->type() == RT_STATIC)
	    ase_schedule(rte->exdata);
    }
}

/* Build an AS-external-LSA ready for flooding, from an
 * internally parsed version.
 */

void ASextLSA::build(LShdr *hdr)

{
    ASEhdr *ase;

    ase = (ASEhdr *) (hdr + 1);
    ase->mask = hton32(rte->mask());
    ase->tos = (e_bit ? E_Bit : 0);
    ase->hibyte = adv_cost >> 16;
    ase->metric = hton16(adv_cost & 0xffff);
    ase->faddr = (fwd_addr ? hton32(fwd_addr->address()) : 0);
    ase->rtag = hton32(adv_tag);
}


/* Recalculate the best path to an ASBR. For the moment, we
 * always assume that RFC1583Compatibility is set to false.
 * If there is an intra-area route to the ASBR, choose
 * the best, preferring non-zero areas and using cost as
 * tie-breaker. The consider summaries, if either no intra-area
 * route is found or the intra-area route is on Area 0.
 * Finally, Area 0 routes may be modified by transit areas.
 */

void ASBRrte::run_calculation()

{
    RTRrte *abr;
    aid_t oa;
    byte otype;
    bool preferred;

    save_state();
    oa = area();
    otype = r_type;
    r_type = RT_NONE;
    cost = Infinity;

    preferred = false;

    // Check for intra-area paths
    for (abr = parts; abr; abr = abr->asbr_link) {
	SpfArea *ap;
	// Is it reachable?
	if (abr->type() != RT_SPF)
	    continue;
	// Is it an ASBR?
	// Can't have ASBRs in stub areas
	if (!abr->e_bit())
	    continue;
	if (!(ap = ospf->FindArea(abr->area())))
	    continue;
	if (ap->is_stub())
	    continue;
	// Best path so far?
	if (preferred && abr->area() == BACKBONE)
	    continue;
	else if (preferred) {
	    if (abr->cost > cost)
	        continue;
	    if (abr->cost == cost && abr->area() < area())
	        continue;
	}
	// Install new best
	update(abr->r_mpath);
	cost = abr->cost;
	set_area(abr->area());
	r_type = RT_SPF;
	preferred = (abr->area() != BACKBONE);
    }

    // Possibly look at summary-LSAs
    if (r_type != RT_SPF)
	run_inter_area();
    // Adjust for virtual links
    if (intra_AS() && area() == BACKBONE)
	run_transit_areas(summs);
    // Failed virtual next hop resolution?
    if (intra_AS() && r_mpath == 0)
	declare_unreachable();
    // If the ASBR has changed, redo type-4 summary-LSAs
    if (state_changed() || otype != r_type || oa != area() ||
	ospf->exiting_htl_restart) {
	ospf->ase_sched = true;
	ospf->asbr_orig(this);
    }
}

/* Look through type-4 summary LSAs, to see whether there is
 * a better inter-area route to the ASBR.
 * It's assumed that the tie-breakers have already been executed,
 * and that we can simply compare routes based on cost.
 */

void ASBRrte::run_inter_area()

{
    asbrLSA *lsap;
    SpfArea *summ_ap;

    summ_ap = ospf->SummaryArea();
    // Go through list of summary-LSAs
    for (lsap = summs; lsap; lsap = (asbrLSA *) lsap->link) {
	RTRrte	*rtr;
	uns32 new_cost;
	MPath *newnh;
	if (lsap->area() != summ_ap)
	    continue;
	// Ignore self-originated
	if (lsap->adv_rtr() == ospf->my_id())
	    continue;
	// Check that router is reachable
	rtr = (RTRrte *) lsap->source;
	if (!rtr || rtr->type() != RT_SPF)
	    continue;
	// And that a reachable cost is being advertised
	if (lsap->adv_cost == LSInfinity)
	    continue;
	// Compare cost to current best
	new_cost = lsap->adv_cost + rtr->cost;
	if (cost < new_cost)
	    continue;
	else if (cost == new_cost)
	    newnh = MPath::merge(r_mpath, rtr->r_mpath);
	else
	    newnh = rtr->r_mpath;
	// Install as current best cost
	update(newnh);
	cost = new_cost;
	set_area(rtr->area());
	r_type = RT_SPFIA;
    }
}

/* For a given routing table entry, go through all the
 * ASEs to see whether we should install an external route
 * in the routing table.
 * The one case that we don't handle nicely is when one
 * or our AS-external-LSAs is overwritten by an internal
 * route -- we just let the AS-external-LSA hang in that
 * case. This should only generate at most a small extra
 * number of AS-external-LSAs.
 * Information on directly attached interfaces not running
 * OSPF is also considered to be external information, and we
 * handle this first.
 */

void INrte::run_external()

{
    bool best_type2;
    bool best_preferred;
    MPath *best_path;
    ASextLSA *lsap;
    uns32 best_cost;
    uns32 best_t2cost;
    uns32 best_tag;
    byte new_type;
    ExRtData *e;

    exdata = 0;
    new_type = RT_NONE;
    best_tag = 0;
    best_type2 = true;
    best_path = 0;
    best_preferred = false;
    best_t2cost = Infinity;
    best_cost = Infinity;

    // First install any direct or static routes
    for (e = exlist; e; e = e->sll_rte) {
	uns32 new_cost;
	uns32 new_t2cost;
	RTE *egress;
	bool preferred;
	// Valid next hop or outgoing interface?
        if ((!e->faddr || !e->faddr->valid()) &&
	    !sys->phy_operational(e->phyint))
	    continue;
	if (e->cost == LSInfinity)
	    continue;
	// Install direct route?
	if (e->direct) {
	    if (r_type != RT_DIRECT || r_mpath != e->mpath) {
	        r_type = RT_DIRECT;
		update(e->mpath);
		cost = 0;
		sys_install();
	    }
	    return;
	}
	// Intra-AS routes take precedence
	if (intra_AS())
	    continue;
	// Better static route?
	if (e->faddr && e->faddr->valid()) {
	    egress = e->faddr;
	    preferred = e->faddr->area() != BACKBONE;
	}
	else {
	    egress = 0;
	    preferred = true;
	}
	if (e->type2) {
	    new_t2cost = e->cost;
	    new_cost = (egress ? egress->cost : 0);
	}
	else {
	    new_t2cost = Infinity;
	    new_cost = e->cost;
	    new_cost += (egress ? egress->cost : 0);
	}
	// Compare against present route
	if (!e->type2 && best_type2)
	    goto install_static;
	else if (e->type2 && !best_type2)
	    continue;
	else if (new_t2cost < best_t2cost)
	    goto install_static;
	else if (new_t2cost > best_t2cost)
	    continue;
	else if (preferred && !best_preferred)
	    goto install_static;
	else if (!preferred && best_preferred)
	    continue;
	else if (new_cost < best_cost)
	    goto install_static;
	else if (new_cost > best_cost)
	    continue;
	/* Record a better static route
	 */
      install_static:
	best_t2cost = new_t2cost;
	best_cost = new_cost;
	best_type2 = e->type2;
	best_preferred = preferred;
	best_tag = e->tag;
        new_type = RT_STATIC;
	best_path = egress ? egress->r_mpath : e->mpath;
	exdata = e;
    }

    // Get rid of old direct routes
    if (r_type == RT_DIRECT) {
        declare_unreachable();
	sys_install();
    }

    // Intra-AS routes take precedence
    if (intra_AS())
	return;

    for (lsap = ases; lsap; lsap = (ASextLSA *) lsap->link) {
	uns32 new_cost;
	uns32 new_t2cost;
	RTE *egress;
	bool preferred;
	// Check LSA's validity
	if (!lsap->source->valid())
	    continue;
	// TODO: Install multicast sources
	if (lsap->adv_cost == LSInfinity)
	    continue;
	// External data accounted for above
	if (lsap->adv_rtr() == ospf->my_id())
	    continue;
	if (lsap->fwd_addr) {
	    if (!lsap->fwd_addr->valid())
		continue;
	    egress = lsap->fwd_addr;
	}
	else
	    egress = lsap->source;

	/* Calculate type 1 and type two costs
	 */
	if (lsap->e_bit != 0) {
	    new_t2cost = lsap->adv_cost;
	    new_cost = egress->cost;
	}
	else {
	    new_t2cost = Infinity;
	    new_cost = lsap->adv_cost + egress->cost;
	}
	preferred = egress->area() != BACKBONE;

	/* Now check to see if we have an equal-cost
	 * or better path. Tiebreakers are:
	 * 1) type 1 metrics over type 2
	 * 2) type 2 cost
	 * 3) non-backbone paths
	 * 4) type 1 cost
	 */
	if (new_type == RT_NONE)
	    goto install_path;
	else if (!lsap->e_bit && best_type2)
	    goto install_path;
	else if (lsap->e_bit && !best_type2)
	    continue;
	else if (new_t2cost < best_t2cost)
	    goto install_path;
	else if (new_t2cost > best_t2cost)
	    continue;
	else if (preferred && !best_preferred)
	    goto install_path;
	else if (!preferred && best_preferred)
	    continue;
	else if (new_cost < best_cost)
	    goto install_path;
	else if (new_cost > best_cost)
	    continue;
	else if (new_type == RT_STATIC) {
	    if (egress->r_mpath == best_path &&
	        lsap->adv_rtr() < ospf->my_id())
	        continue;
	    else
		goto install_path;
	}
	// Equal-cost logic
        else {
	    best_path = MPath::merge(best_path, egress->r_mpath);
	    continue;
	}
	/* Record a new better path
	 */
      install_path:
	best_t2cost = new_t2cost;
	best_cost = new_cost;
	best_type2 = (lsap->e_bit != 0);
	best_preferred = preferred;
	best_tag = lsap->adv_tag;
        new_type = (best_type2 ? RT_EXTT2 : RT_EXTT1);
	best_path = egress->r_mpath;
	exdata = 0;
    }

    // Delete or install new path
    if (new_type == RT_NONE) {
	if (r_type != RT_NONE) {
	    declare_unreachable();
	    sys_install();
	}
    }
    else if (best_path != r_mpath ||
	new_type != r_type ||
	best_cost != cost ||
	best_t2cost != t2cost ||
	     best_tag != tag ||
	     ospf->exiting_htl_restart) {
	update(best_path);
	r_type = new_type;
	cost = best_cost;
	t2cost = best_t2cost;
	tag = best_tag;
	sys_install();
    }
    else if (new_type == RT_STATIC && exdata->forced) {
	if (ospf->spflog(LOG_IMPORT, 4))
	    ospf->log(this);
	ospf->ase_schedule(exdata);
    }
}