spflood.c

BCAST Implementation for NS2

 * other kinds of local-scoped LSAs.
 */

bool SpfIfc::demand_flooding(byte lstype) const
{
    int scope;
    if (if_demand == 0)
	return(false);
    scope = flooding_scope(lstype);
    if (scope == LocalScope)
        return(false);
    else if (scope == GlobalScope)
        return(ospf->donotage());
    else // Area scope
        return(if_area->donotage());
}


/* Add an LSA to an update packet to be sent to a particular
 * neighbor. Send the Link State Update if it is now full.
 * Returns the available space, so that if this is a retransmission
 * we can keep track of the number of packets sent.
 */

int SpfNbr::add_to_update(LShdr *hdr)

{
    int lsalen;
    Pkt *pkt;

    lsalen = ntoh16(hdr->ls_length);
    pkt = &n_update;
    // If no more room, send the current packet
    if (pkt->iphdr && (pkt->dptr + lsalen) > pkt->end)
	n_ifp->nbr_send(pkt, this);
    // Add LSA to packet.
    ospf->build_update(pkt, hdr, n_ifp->if_mtu,
		       n_ifp->demand_flooding(hdr->ls_type));
    // Return remaining space available
    return((int)(pkt->end - pkt->dptr));
}

/* Add an LSA to an update packet to be sent out a particular
 * interface. Send the Link State Update if it is now full.
 * Returns the available space, so that if this is a retransmission
 * we can keep track of the number of packets sent.
 */

int SpfIfc::add_to_update(LShdr *hdr)

{
    int lsalen;
    Pkt *pkt;

    lsalen = ntoh16(hdr->ls_length);
    pkt = &if_update;
    // If no more room, send the current packet
    if (pkt->iphdr && (pkt->dptr + lsalen) > pkt->end)
	if_send(pkt, if_faddr);
    // Add LSA to packet.
    ospf->build_update(pkt, hdr, if_mtu, demand_flooding(hdr->ls_type));
    // Return remaining space available
    return((int)(pkt->end - pkt->dptr));
}

/* Add an LSA to an update packet to be sent out all interfaces
 * to a particular area. Send the Link State Update if it is now full.
 */

void SpfArea::add_to_update(LShdr *hdr, bool demand_upd)

{
    int lsalen;
    Pkt *pkt;

    lsalen = ntoh16(hdr->ls_length);
    pkt = demand_upd ? &a_demand_upd : &a_update;
    pkt->hold = true;
    // If no more room, send the current packet
    if (pkt->iphdr && (pkt->dptr + lsalen) > pkt->end) {
	SpfIfc *ip;
	IfcIterator iter(this);
	while ((ip = iter.get_next())) {
	    if (demand_upd == ip->demand_flooding(hdr->ls_type))
		ip->if_send(pkt, ip->if_faddr);
	}
	pkt->hold = false;
	ospf->ospf_freepkt(pkt);
	pkt->hold = true;
    }
    // Add LSA to packet.
    ospf->build_update(pkt, hdr, a_mtu, demand_upd);
}

/* Add an LSA to an update packet to be sent out all interfaces.
 * Stub areas and virtual links are excepted.
 * Send the Link State Update if it is now full.
 */

void OSPF::add_to_update(LShdr *hdr, bool demand_upd)

{
    int lsalen;
    Pkt *pkt;

    lsalen = ntoh16(hdr->ls_length);
    pkt = demand_upd ? &o_demand_upd : &o_update;
    pkt->hold = true;
    // If no more room, send the current packet
    if (pkt->iphdr && (pkt->dptr + lsalen) > pkt->end) {
	SpfIfc *ip;
	IfcIterator iter(this);
	while ((ip = iter.get_next())) {
	    if (ip->area()->is_stub())
		continue;
	    if (ip->is_virtual())
		continue;
	    if (demand_upd == ip->demand_flooding(hdr->ls_type))
		ip->if_send(pkt, ip->if_faddr);
	}
	pkt->hold = false;
	ospf->ospf_freepkt(pkt);
	pkt->hold = true;
    }
    // Add LSA to packet.
    ospf->build_update(pkt, hdr, ospf_mtu, demand_upd);
}

/* Add an LSA to a Link State Update Packet. Caller ensures
 * that the LSA will fit into the current packet.
 *
 * Callers of OSPF::build_update() (or their callers, etc.) must
 * either call OSPF::send_updates() or if_send() before they exit,
 * or the last update will remain unsent and queued on the interface
 * or neighbor structures.
 *
 * Called when 1) received new LSA during flooding, 2) responding to
 * a link state request packet or 3) retransmitting an LSA.
 * We cheat and always use 1 for the transmission delay!
 */

void OSPF::build_update(Pkt *pkt, LShdr *hdr, uns16 mtu, bool demand)

{
    int lsalen;
    UpdPkt *upkt;
    age_t c_age, new_age;
    LShdr *new_hdr;
    int donotage;

    lsalen = ntoh16(hdr->ls_length);
    if (!pkt->iphdr) {
	uns16 size;
	size = MAX(lsalen+sizeof(InPkt)+sizeof(UpdPkt), mtu);
	if (ospf_getpkt(pkt, SPT_UPD, size) == 0)
	    return;
	upkt = (UpdPkt *) (pkt->spfpkt);
	upkt->upd_no = 0;
	pkt->dptr = (byte *) (upkt + 1);
    }
    /* Get pointer to link state update packet. Increment count
     * of LSAs, copy in the current LSA and increment the
     * buffer point.
     */
    upkt = (UpdPkt *) (pkt->spfpkt);
    upkt->upd_no = hton32(ntoh32(upkt->upd_no) + 1);
    new_hdr = (LShdr *) pkt->dptr;
    // Increment age by interface's transmission delay
    // Set DoNotAge if demand interface
    c_age = ntoh16(hdr->ls_age);
    donotage = (c_age & DoNotAge) != 0;
    c_age &= ~DoNotAge;
    new_age = MIN(MaxAge, c_age + 1);
    if (new_age < MaxAge && (donotage || demand))
	new_age |= DoNotAge;
    new_hdr->ls_age = hton16(new_age);
    // Copy rest of LSA into update 
    memcpy(&new_hdr->ls_opts, &hdr->ls_opts, lsalen - sizeof(age_t));
    pkt->dptr += lsalen;
}

/* Last step of the flooding procedure.
 * Go through the interface structures, sending any
 * updates which have been queued by the add_to_update()s.
 *
 * On non-broadcast networks, the interface's send packet routine
 * will actually send out separate updates to each adjacent neighbor.
 *
 * We loop through all the interfaces in order to send
 * a) link-scoped LSAs and b) LSAs that are flooded back out the
 * receiving interface.
 */

void OSPF::send_updates()

{
    AreaIterator aiter(this);
    SpfArea *a;
    SpfIfc *ip;
    IfcIterator iiter(this);

    while ((ip = iiter.get_next()))
        ip->if_send_update();

    // Area scope flood
    while ((a = aiter.get_next())) {
	IfcIterator iter(a);
	Pkt *pkt;
	if (!a->a_demand_upd.partial_checksum() &&
	    !a->a_update.partial_checksum())
	    continue;
	while ((ip = iter.get_next())) {
	    if (!ip->area_flood)
		continue;
	    if (ip->demand_flooding(LST_RTR))
		pkt = &a->a_demand_upd;
	    else
		pkt = &a->a_update;
	    ip->if_send(pkt, ip->if_faddr);
	    ip->area_flood = false;
	}

	a->a_demand_upd.hold = false;
	ospf_freepkt(&a->a_demand_upd);
	a->a_update.hold = false;
	ospf_freepkt(&a->a_update);
    }

    // AS flood scope
    if (o_demand_upd.partial_checksum() || o_update.partial_checksum()) {
	IfcIterator iter(this);
	while ((ip = iter.get_next())) {
	    Pkt *pkt;
	    if (!ip->global_flood)
		continue;
	    pkt = ip->demand_flooding(LST_ASL) ? &o_demand_upd : &o_update;
	    ip->if_send(pkt, ip->if_faddr);
	    ip->global_flood = false;
	}

	o_demand_upd.hold = false;
	ospf_freepkt(&o_demand_upd);
	o_update.hold = false;
	ospf_freepkt(&o_update);
    }
}

/* Compare a link state advertisement received from the network (hdr)
 * with one installed in the database. Returns -1, 0 and 1 depending
 * in whether the received copy is less recent, the same instance or
 * more recent than the database copy. As always, the link state
 * advertisement received from the network is in network byte-order,
 * while the database copy has been converted to machine byte-order.
 *
 * The algorithm for determining which LSA is more recent is given in
 * Section 13.1 of the OSPF spec.
 */

int LSA::cmp_instance(LShdr *hdr)

{
    age_t rcvd_age;
    age_t db_age;
    seq_t rcvd_seq;
    xsum_t rcvd_xsum;

    if ((rcvd_age = (ntoh16(hdr->ls_age) & ~DoNotAge)) > MaxAge)
	rcvd_age = MaxAge;
    if ((db_age = (lsa_age() & ~DoNotAge)) > MaxAge)
	db_age = MaxAge;

    rcvd_seq = ntoh32(hdr->ls_seqno);
    rcvd_xsum = ntoh16(hdr->ls_xsum);

    if (rcvd_seq > lsa_seqno)
	return(1);
    else if (rcvd_seq < lsa_seqno)
	return(-1);
    else if (rcvd_xsum > lsa_xsum)
	return(1);
    else if (rcvd_xsum < lsa_xsum)
	return(-1);
    else if (rcvd_age == MaxAge && db_age != MaxAge)
	return(1);
    else if (rcvd_age != MaxAge && db_age == MaxAge)
	return(-1);
    else if ((rcvd_age + MaxAgeDiff) < db_age)
	return(1);
    else if (rcvd_age > (db_age + MaxAgeDiff))
	return(-1);
    else
	return(0);
}


/* Compare the contents of an LSA received during flooding to the
 * current LSA instance in the router's database. Returns 1 if the
 * contents are significantly different (i.e., would cause a routing
 * calculation to be rerun), otherwise returns 0.
 */

int     LSA::cmp_contents(LShdr *hdr)

{
    LShdr *dbcopy;
    age_t rcvd_age;
    age_t db_age;
    int size;

    // Create network-ready version of database copy
    dbcopy = ospf->BuildLSA(this);

    // Mask out DoNotAge bit
    if ((rcvd_age = (ntoh16(hdr->ls_age) & ~DoNotAge)) > MaxAge)
	rcvd_age = MaxAge;
    if ((db_age = (lsa_age() & ~DoNotAge)) > MaxAge)
	db_age = MaxAge;

    // Check for significant changes
    if (rcvd_age != db_age && (rcvd_age == MaxAge || db_age == MaxAge))
	return(1);
    if (hdr->ls_opts != dbcopy->ls_opts)
	return(1);
    if (hdr->ls_length != dbcopy->ls_length)
	return(1);
    if (lsa_length <= sizeof(LShdr))
	return(0);

    // Compare body of advertisements
    size = lsa_length - sizeof(LShdr);
    if (memcmp((hdr + 1), (dbcopy + 1), size))
	return(1);

    return(0);
}

/* Decide whether to keep a MaxAge LSA in the database, even though
 * it has been completely flooded. Keep if there are neighbors
 * undergoing Database Exchange. One exception: if it is an
 * external-LSA and we're in overflow state, free the LSA --
 * otherwise we wouldn't be able to complete Database Exchange
 * in this state.
 */

bool OSPF::maxage_free(byte lstype)

{
    if (n_dbx_nbrs == 0)
	return(true);
    else if (!OverflowState)
	return(false);
    else if (lstype == LST_ASL)
	return(true);
    else
	return(false);
}