spflood.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.
 */

/* Implementation of the OSPF flooding algorithm.
 * This is specified in Section 13 of the OSPF Specification.
 */

#include "ospfinc.h"
#include "ifcfsm.h"
#include "nbrfsm.h"
#include "system.h"

/* Receive a Link State Update Packet. Called with a packet
 * structure and the neighbor that the
 * packet was received from. Then do the processing in Section
 * 13 of the OSPF spec, going through all LSAs listed in the
 * update, acknowledging, installing and/or flooding each one
 * as appropriate.
 */

void SpfNbr::recv_update(Pkt *pdesc)

{
    SpfIfc *ip;
    SpfArea *ap;
    int count;
    UpdPkt *upkt;
    LShdr *hdr;
    byte *end_lsa;

    if (n_state < NBS_EXCH) {
        if (n_ifp->type() == IFT_PP)
	    // Tell neighbor there is no adjacency
	    n_ifp->send_hello(true);
	return;
    }

    ip = n_ifp;
    ap = ip->area();
    upkt = (UpdPkt *) pdesc->spfpkt;
    ip->in_recv_update = true;

    count = ntoh32(upkt->upd_no);
    hdr = (LShdr *) (upkt+1);

    for (; count > 0; count--, hdr = (LShdr *) end_lsa) {
	int errval=0;
	int lslen;
	int lstype;
	lsid_t lsid;
	rtid_t orig;
	age_t lsage;
	LSA *olsap;
	int compare;
	int rq_cmp;

	lstype = hdr->ls_type;
	lsage = ntoh16(hdr->ls_age);
	if ((lsage & ~DoNotAge) >= MaxAge)
	    lsage = MaxAge;
	lslen = ntoh16(hdr->ls_length);
	end_lsa = ((byte *)hdr) + lslen;
	if (end_lsa > pdesc->end)
	    break;

	if (!hdr->verify_cksum())
	    errval = ERR_LSAXSUM;
	else if (!ospf->FindLSdb(ip, ap, lstype))
	    errval = ERR_BAD_LSA_TYPE;
	else if (flooding_scope(lstype) == GlobalScope && ap->is_stub())
	    errval = ERR_EX_IN_STUB;
	else if (lstype == LST_GM && !ospf->mospf_enabled())
	    continue;

	if (errval != 0) {
	    if (ospf->spflog(errval, 5)) {
		ospf->log(hdr);
		ospf->log(this);
	    }
	    continue;
	}

	/* If the network doesn't support DoNotAge, turn that
	 * bit off!
	 */
	if ((lsage & DoNotAge) != 0) {
	    if ((flooding_scope(lstype) == GlobalScope && !ospf->donotage()) ||
		(flooding_scope(lstype) == AreaScope && !ap->donotage())) {
	        if (ospf->spflog(ERR_DONOTAGE, 5)) {
		    ospf->log(hdr);
		    ospf->log(this);
		}
		hdr->ls_age = hton16(lsage & ~DoNotAge);
	    }
	}

	/* Find current database copy, if any */
	lsid = ntoh32(hdr->ls_id);
	orig = ntoh32(hdr->ls_org);
	olsap = ospf->FindLSA(ip, ap, lstype, lsid, orig);

	/* If no instance in database, and received
	 * LSA has LS age equal to MaxAge, and there
	 * are no neighbors undergoing Database Exchange, then
	 * simply ack the LSA and discard it.
	 */
	if (lsage == MaxAge && (!olsap) && ospf->maxage_free(lstype)){
	    build_imack(hdr);
	    continue;
	}

	/* Compare to database instance */
	compare = (olsap ? olsap->cmp_instance(hdr) : 1);

	/* If received LSA is more recent */
	if (compare > 0) {
	    bool changes;
	    LSA *lsap;
	    if (olsap && olsap->since_received() < MinArrival) {
	        // One time grace period
	        if (olsap->min_failed) {
	            if (ospf->spflog(LOG_MINARRIVAL, 4)) {
		        ospf->log(hdr);
			ospf->log(this);
		    }
		    continue;
		}
	    }
	    // If self-originated forces us to re-originate
	    changes = (olsap ? olsap->cmp_contents(hdr) : true);
	    if (changes && ospf->self_originated(this, hdr, olsap))
		continue;
	    /* Perform database overflow logic.
	     * Discard non-default AS-external-LSAs
	     * if the number exceeds the limit.
	     * TODO: Note: OverflowState is entered in
	     * lsa_parse().
	     */
	    if ((!olsap) && lstype == LST_ASL &&
		lsid != DefaultDest &&
		ospf->ExtLsdbLimit &&
		ospf->n_exlsas >= ospf->ExtLsdbLimit) {
		continue;
	    }
	    // Otherwise, install and flood
	    if (ospf->spflog(LOG_RXNEWLSA, 1))
		ospf->log(hdr);
	    lsap = ospf->AddLSA(ip, ap, olsap, hdr, changes);
	    lsap->flood(this, hdr);
	}
	else if (ospf_rmreq(hdr, &rq_cmp)) {
	    // Error in Database Exchange
	    nbr_fsm(NBE_BADLSREQ);
	}
	else if (compare == 0) {
	    // Not implied acknowledgment?
	    if (!remove_from_rxlist(olsap))
		build_imack(hdr);
	}
	else {
	    LShdr *ohdr;
	    // Database copy more recent
	    if (olsap->ls_seqno() == MaxLSSeq)
		continue;
	    if (olsap->sent_reply)
	        continue;
	    ohdr = ospf->BuildLSA(olsap);
	    add_to_update(ohdr);
	    olsap->sent_reply = true;
	    ospf->replied_list.addEntry(olsap);
	}
    }
    
    // Flood out interfaces
    ospf->send_updates();
    ip->nbr_send(&n_imack, this);
    ip->nbr_send(&n_update, this);
    ip->in_recv_update = false;
    // Continue to send requests, if necessary
    if (n_rqlst.count() && n_rqlst.count() <= rq_goal) {
	n_rqrxtim.restart();
	send_req();
    }
}

/* Flood a LSA.
 * For each neighbor in Exchange or greater, add the LSA to the
 * neighbor's link state retransmission list. If it has been added
 * to any retransmission lists, then flood out the interface, except
 * if it was received on the interface. In that case, only flood
 * back out if you are the Designated Router (in which case you
 * also stop the delayed ack by zeroing out the LSA's from
 * field). Returns whether any buffer allocation failures were
 * encountered.
 * Must do demand circuit refresh inhibition *after* removing
 * requests from the link-state request list.
 */

void LSA::flood(SpfNbr *from, LShdr *hdr)

{
    IfcIterator ifcIter(ospf);
    SpfIfc *r_ip;
    SpfIfc *ip;
    byte lstype;
    int scope;
    bool flood_it=false;
    bool on_demand=false;
    bool on_regular=false;

    lstype = lsa_type;
    scope = flooding_scope(lstype);
    r_ip = (from ? from->ifc() : 0);
    if (!hdr)
	hdr = ospf->BuildLSA(this);
    
    while ((ip = ifcIter.get_next())) {
	SpfArea *ap;
	SpfNbr *np;
	NbrIterator nbrIter(ip);
	int n_nbrs;

	ap = ip->area();
	if (scope == GlobalScope && ap->is_stub())
	    continue;
	if (scope == GlobalScope && ip->is_virtual())
	    continue;
	if (scope == AreaScope && ap != lsa_ap)
	    continue;
	if (scope == LocalScope && ip != lsa_ifp)
	    continue;

	n_nbrs = 0;
	while ((np = nbrIter.get_next())) {
	    int rq_cmp;

	    if (np->state() < NBS_EXCH)
		continue;
	    if (np->ospf_rmreq(hdr, &rq_cmp) && rq_cmp <= 0)
		continue;
	    if (np == from)
		continue;
	    if (lstype == LST_GM && (!np->supports(SPO_MC)))
		continue;
	    if ((lstype >= LST_LINK_OPQ && lstype <= LST_AS_OPQ)
		&& (!np->supports(SPO_OPQ)))
		continue;
	    if (ip->demand_flooding(lstype) && !changed)
	        continue;

	    // Add to neighbor retransmission list
	    n_nbrs++;
	    np->add_to_rxlist(this);
	}

	// Decide which updates to build
	if (ip == r_ip &&
	    (ip->state() == IFS_DR && !from->is_bdr() && n_nbrs != 0)) {
	    ip->add_to_update(hdr);
	}
	else if ((r_ip == 0 && n_nbrs != 0) &&
		 (ip->in_recv_update || scope == LocalScope))
	    ip->add_to_update(hdr);
	else if (ip != r_ip) {
	    if (n_nbrs == 0)
		continue;
	    flood_it = true;
	    if (scope == AreaScope)
		ip->area_flood = true;
	    else
		ip->global_flood = true;
	    if (ip->demand_flooding(lstype))
		on_demand = true;
	    else
		on_regular = true;
	}
	// Or decide whether to send ack
	else
	    ip->if_build_dack(hdr);
    }

    // Place LSA in appropriate update, according to scope
    if (!flood_it)
	return;
    else if (scope == AreaScope) {
	if (on_regular)
	    lsa_ap->add_to_update(hdr, false);
	if (on_demand)
	    lsa_ap->add_to_update(hdr, true);
    }
    else {	// AS scope
	if (on_regular)
	    ospf->add_to_update(hdr, false);
	if (on_demand)
	    ospf->add_to_update(hdr, true);
    }
}

/* Remove requests for this LSA instance, or previous instances
 * of the LSA, from the neighbor's link state request queues. If this
 * causes the neighbor request queue to become empty, then if the
 * neighbor state is Exchange, send another Database Description Packet.
 * If the neighbor state is Loading, then transition to Full state.
 *
 * Returns whether instance (not necessarily the same instance) has been
 * found on the link state request list.
 */

int SpfNbr::ospf_rmreq(LShdr *hdr, int *compare)
    
{
    byte ls_type;
    lsid_t ls_id;
    rtid_t adv_rtr;
    LsaListIterator iter(&n_rqlst);
    LSA *lsap;

    ls_type = hdr->ls_type;
    ls_id = ntoh32(hdr->ls_id);
    adv_rtr = ntoh32(hdr->ls_org);

    if (!(lsap = iter.search(ls_type, ls_id, adv_rtr)))
	return(0);
    if ((*compare = lsap->cmp_instance(hdr)) >= 0) {
	iter.remove_current();
	if (n_rqlst.is_empty()) {
	    n_rqrxtim.stop();
	    if (n_state == NBS_LOAD)
		nbr_fsm(NBE_LDONE);
	    else
		send_dd();
	}
    }
    return(1);
}

/* Determine whether LSAs should have DoNotAge set when
 * flooded over this interface. For the moment, we never
 * set DoNotAge when flooding link-scoped LSAs over
 * a demand interfaces. This is done so that grace-LSAs work
 * correctly, although should be revisited when we start originating