spfcalc.c

BCAST Implementation for NS2

    for (lp = t_links; lp != 0; lp = lp->l_next) {
	TLink *tlp;
	if (lp->l_ltype == LT_STUB)
	    continue;
	tlp = (TLink *) lp;
	if (tlp->tl_nbr == V)
	    gw_addr = tlp->l_data;
	if (net && (gw_addr & mask) == net)
	    break;
    }

    return(gw_addr);
}

/* Add next hop to a transit node, based on the parent.
 * Currently not doing multipath, so we set the next hop
 * only if a previous one has not been found.
 */

void TNode::add_next_hop(TNode *V, int _index)

{
    MPath *new_nh;
    SpfIfc *t_ifc;
    InAddr t_gw;

    // If parent is the root
    if (V == lsa_ap->mylsa) {
	if (!(t_ifc = lsa_ap->ifmap[_index]))
	    return;
	if (lsa_type == LST_NET)
	    t_gw = 0;
	else
	    t_gw = ospf_find_gw(V, t_ifc->net(), t_ifc->mask());
	new_nh = MPath::create(t_ifc, t_gw);
	new_nh = t_ifc->add_parallel_links(new_nh, this);
    }
    // Not adjacent to root, simply inherit
    else if (!V->t_direct || V->ls_type() != LST_NET)
	new_nh = V->t_mpath;
    // Directly connected to root through transit net
    else {
	INrte *rte;
	rte = (INrte *) V->t_dest;
	t_gw = ospf_find_gw(V, rte->net(), rte->mask());
	new_nh = MPath::addgw(V->t_mpath, t_gw);
    }

    t_mpath = MPath::merge(t_mpath, new_nh);
}

/* Update the status of all AS boundary routers.
 */

void OSPF::update_asbrs()
    
{
    ASBRrte *rrte;

    for (rrte = ASBRs; rrte; rrte = rrte->next())
	rrte->run_calculation();
}	


/* Update the status of all area boundary routers. Upon status
 * changes or chnages in cost, update any related virtual
 * links.
 */

void OSPF::update_brs()
    
{
    AreaIterator iter(this);
    SpfArea *ap;

    // Put all our own router-LSAs onto candidate list
    while ((ap = iter.get_next())) {
	rtrLSA *root;
	bool local_changed;
	RTRrte *abr;
	AVLsearch rrsearch(&ap->abr_tbl);
	root = (rtrLSA *) myLSA(0, ap, LST_RTR, myid);
	local_changed = (root != 0 && root->parsed && root->t_dest->changed);

	while ((abr = (RTRrte *)rrsearch.next())) {
	    // ABR now unreachable?
	    if ((abr->type() == RT_SPF) &&
		((n_dijkstras & 1) != abr->dijk_run)) {
		abr->declare_unreachable();
		abr->changed = true;
	    }
	    // Change to virtual link endpoint?
	    if (abr->changed || abr->state_changed() || local_changed) {
		if (abr->VL)
		    abr->VL->update(abr);
		abr->changed = false;
	    }
	}
    }
}	


/* Go through the routing table, in order. Called recursively in
 * order to correctly aggregate routes for advertising summary-LSAs.
 * First checks to see whether intra-area routes have been deleted
 * by the Dijkstra calculation.
 */

void OSPF::rt_scan()

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

    // Change in area transit status?
    transit_changes = false;
    while ((ap = a_iter.get_next())) {
	if (ap->was_transit != ap->a_transit)
	    transit_changes = true;
    }

    while ((rte = iter.nextrte())) {
	// Delete old intra-area routes
	if (rte->intra_area() &&
	    ((n_dijkstras & 1) != rte->dijk_run)) {
	    rte->declare_unreachable();
	    rte->changed = true;
	}
	// Look at summary-LSAs
	if (rte->inter_area() || rte->summs)
	    rte->run_inter_area();
	// Transit area processing
	if (rte->intra_AS() && rte->area() == BACKBONE)
	    rte->run_transit_areas(rte->summs);
	// Failed virtual next hop resolution?
	if (rte->intra_AS() && rte->r_mpath == 0)
	    rte->declare_unreachable();
	// Update cost, activity of area ranges
	if (rte->intra_area()) {
	    rte->tag = 0;
	    update_area_ranges(rte);
	}
	// On changes, re-originate summary-LSAs
	// Ranges ignored if also physical link
	if (rte->changed || rte->state_changed() || exiting_htl_restart) {
	    rte->changed = false;
	    rte->sys_install();
	    if (!rte->is_range())
	        sl_orig(rte);
	}
	// Don't originate summaries of backbone routes
	// into transit areas
	else if (transit_changes &&
		 rte->intra_area() &&
		 rte->area() == BACKBONE &&
		 !rte->is_range())
	    sl_orig(rte, true);
    }
}

/* Install a new route into the kernel's routing table. Depending
 * on the state of the routing table entry, either add, delete,
 * or install a reject route.
 */

void INrte::sys_install()

{
    AVLitem *item;
    int msgno;

    // If necessary, recalculate certain entries in the
    // forwarding address table. This is only necessary
    // for incremental changes
    switch(r_type) {
      case RT_DIRECT:
	fa_tbl->resolve();
	break;
      case RT_NONE:
      case RT_STATIC:
      case RT_EXTT1:
      case RT_EXTT2:
	fa_tbl->resolve(this);
	break;
      default:
	break;
    }

    // We're about to synchronize with the kernel
    // Don't synchronize if we are in hitless restart
    if (ospf->in_hitless_restart())
        return;
    // If kernel deleted entry, we're going to rewrite, so
    // don't bother to respond in OSPF::krt_sync()
    if ((item = ospf->krtdeletes.find(net(), mask()))) {
        ospf->krtdeletes.remove(item);
	delete item;
    }

    // Update system kernel's forwarding table
    switch(r_type) {
      case RT_NONE:
	msgno = LOG_DELRT;
	sys->rtdel(net(), mask(), last_mpath);
	break;
      case RT_REJECT:
	msgno = LOG_ADDREJECT;
	sys->rtadd(net(), mask(), 0, last_mpath, true);
	break;
      default:
	msgno = LOG_ADDRT;
	sys->rtadd(net(), mask(), r_mpath, last_mpath, false);
	break;
    }

    last_mpath = r_mpath;
    if (ospf->spflog(msgno, 3))
	ospf->log(this);

    /* At this point we must decide whether to
     * (re)originate or flush an AS-external-LSA.
     */
    if (r_type == RT_STATIC)
        ospf->ase_schedule(exdata);
    else if (ase_orig) {
        ase_orig = false;
	ospf->ase_orig(this, 0);
    }
}

/* Resynchronize the routing table by re-adding routes that
 * the kernel deleted fror some unknown reason.
 */

void OSPF::krt_sync()

{
    AVLsearch iter(&krtdeletes);
    KrtSync *item;

    if (shutting_down())
        return;

    while ((item = (KrtSync *)iter.next())) {
        InAddr net;
	InMask mask;
	INrte *rte;
	if (time_diff(sys_etime, item->tstamp) < 5*Timer::SECOND)
	    continue;
	net = item->index1();
	mask = item->index2();
	krtdeletes.remove(item);
	delete item;
	rte = inrttbl->find(net, mask);
	if (!rte || !rte->valid())
	    continue;
	if (ospf->spflog(LOG_KRTSYNC, 5))
	    ospf->log(rte);
	sys->rtadd(net, mask, rte->r_mpath, rte->last_mpath, 
		   rte->r_type == RT_REJECT);
    }
}

/* When we construct the entry indicating that the
 * kernel deleted a route before we did, note the
 * time so that we can wait long enough to know whether
 * we should re-add it. Must wait until an updated LSA
 * is reissued and the routing calculation is rerun.
 */

KrtSync::KrtSync(InAddr net, InMask mask) : AVLitem(net, mask)

{
    tstamp = sys_etime;
}

/* (Re)resolve the reachability and cost of all forwarding
 * addresses.
 * If any of the forwarding addresses have changed, schedule
 * the routing calculation, and also look into reoriginating
 * our own LSAs.
 */

void FWDtbl::resolve()

{
    AVLsearch iter(&root);
    FWDrte *faddr;

    while ((faddr = (FWDrte *) iter.next())) {
	faddr->resolve();
	if (faddr->changed)
	    ospf->ase_sched = true;
    }
}

/* Resolve only those forwarding addresses matching
 * a routing table entry that has just been modified.
 */

void FWDtbl::resolve(INrte *changed_rte)

{
    InAddr start;
    InAddr end;
    AVLsearch iter(&root);
    FWDrte *faddr;

    start = changed_rte->net() - 1;
    end = changed_rte->broadcast_address();
    if (changed_rte != default_route)
        iter.seek(start, 0);

    while ((faddr = (FWDrte *) iter.next())) {
        if (faddr->address() > end)
	    break;
	if (faddr->match && !changed_rte->is_child(faddr->match))
	    continue;
	faddr->resolve();
	if (faddr->changed)
	    ospf->ase_sched = true;
    }
}

/* (Re)resolve a forwarding address. If the cost or state
 * of the forwarding address changes, return true.
 */

void FWDrte::resolve()

{
    aid_t oa;
    byte otype;
    MPath *new_path;

    save_state();
    oa = area();
    otype = r_type;
    
    ifp = ospf->find_nbr_ifc(address());
    match = inrttbl->best_match(address());
    if (!match || !match->intra_AS())
	r_type = RT_NONE;
    else {
	r_type = match->type();
	new_path = MPath::addgw(match->r_mpath, address());
	set_area(match->area());
	update(new_path);
	cost = match->cost;
    }

    changed = (state_changed() || otype != r_type || oa != area());
}

/* Run through all the AS-external-LSAs, recalculating all
 * external routes.
 * Can't be run inside rt_scan(), because we must wait until
 * all forwarding addresses are recalculated.
 */

void OSPF::do_all_ases()

{
    INrte *rte;
    INiterator iter(inrttbl);

    ase_sched = false;
    while ((rte = iter.nextrte())) {
	if (rte->ases || rte->exlist)
	    rte->run_external();
    }
    // Clear multicast cache
    clear_mospf = true;
}

/* Incremental calculation for a single changed summary-LSA.
 * Returns true if entire routing calculation needs to be rerun,
 * false otherwise.
 */

void INrte::incremental_summary(SpfArea *a)

{
    byte otype;
    aid_t oa;

    otype = r_type;
    oa = area();
    if (intra_AS())
	save_state();

    // New update of transit area forces Dijkstra
    if ((otype == RT_SPF && oa == BACKBONE && r_mpath->some_transit(a)) ||
	(!intra_AS() && summs)) {
	ospf->full_sched = true;
	return;
    }

    // Incremental summary-LSA calculations
    run_inter_area();
    if (inter_area() && area() == BACKBONE)
	run_transit_areas(summs);
    // Failed virtual next hop resolution?
    if (intra_AS() && r_mpath == 0)
	declare_unreachable();
    if (state_changed() || otype != r_type || oa != area()) {
	// Clear changed flag
        changed = false;
	// Install in kernel routing table
	sys_install();
	// Originate new summary-LSA
	ospf->sl_orig(this);
	// Recalculate forwarding addresses
	fa_tbl->resolve();
	// Clear multicast cache with this source
	ospf->mospf_clear_inter_source(this);
    }
}

/* When we are limiting the adjacencies formed over
 * parallel point-to-point links, add all links in
 * state 2-Way as next hops.
 */

MPath *SpfIfc::add_parallel_links(MPath *new_nh, TNode *)

{
    return(new_nh);
}

MPath *VLIfc::add_parallel_links(MPath *new_nh, TNode *)

{
    return(new_nh);
}

MPath *PPIfc::add_parallel_links(MPath *new_nh, TNode *dst)

{
    rtid_t nbr_id;
    PPAdjAggr *adjaggr;

    nbr_id = dst->ls_id();
    if (ospf->PPAdjLimit == 0)
        return(new_nh);
    else if (!(adjaggr = (PPAdjAggr *)if_area->AdjAggr.find(nbr_id, 0)))
        return(new_nh);
    else if (!adjaggr->nbr_mpath)
        return(new_nh);
    return (adjaggr->nbr_mpath);
}