patch2.4

BCAST Implementation for NS2

  */
 
-LShdr *OSPF::BuildLSA(LSA *lsap)
+LShdr *OSPF::BuildLSA(LSA *lsap, LShdr *hdr)
 
 {
-    LShdr *hdr;
     int	blen;
 
+    if (hdr == 0) {
     if (lsap->lsa_length > build_size) {
 	delete [] build_area;
 	build_size = lsap->lsa_length;
 	build_area = new byte[lsap->lsa_length];
     }
-
     hdr = (LShdr *) ospf->build_area;
+    }
+    // Fill in standard Link state header
     *hdr = *lsap;
+    // Fill in body of LSA
     if (!lsap->exception)
 	lsap->build(hdr);
     else {
diff -X exclude_files -Nabur ospfd2.3/src/lsa.h ospfd2.4/src/lsa.h
--- ospfd2.3/src/lsa.h	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/lsa.h	Thu Sep 13 16:05:43 2001
@@ -57,7 +57,8 @@
 	parsed:1,	// Parsed for easy calculation?
         sent_reply:1,	// Sent reply for older LSA received
         checkage:1,	// Queued for xsum verification
-        min_failed:1;	// MinArrival failed
+        min_failed:1,	// MinArrival failed
+        we_orig:1;	// We have originated this LSA
     uns16 lsa_hour;	// Hour counter, for DoNotAge refresh
 
     static LSA *AgeBins[MaxAge+1];// Aging Bins
@@ -110,6 +111,7 @@
     friend LShdr& LShdr::operator=(class LSA &lsa);
     friend inline uns16 Age2Bin(age_t);
     friend inline age_t Bin2Age(uns16);
+    friend void lsa_flush(LSA *);
 };
 
 // Inline functions
diff -X exclude_files -Nabur ospfd2.3/src/lsdb.C ospfd2.4/src/lsdb.C
--- ospfd2.3/src/lsdb.C	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/lsdb.C	Thu Sep 13 16:05:43 2001
@@ -138,22 +138,26 @@
 /* Append all the LSAs of a particular type to a given lsalist.
  * Use for example when creating a Database Summary list at the
  * beginning of the Database Description process.
+ * When in hitless restart, we don't add our own router-LSAs
+ * to the list, as they will look like topology changes
+ * to the neighboring routers. Instead, we reflood the router-LSAs
+ * at the conclusion of hitless restart.
  */
 
 void SpfIfc::AddTypesToList(byte lstype, LsaList *lp)
 
 {
     AVLtree *btree;
-    AVLitem *ptr;
+    LSA *lsap;
     SpfArea *ap;
 
     ap = area();
     if (!(btree = ospf->FindLSdb(this, ap, lstype)))
 	return;
 
-    ptr = (LSA *) btree->sllhead;
-    for (; ptr; ptr = (LSA *) ptr->sll)
-	lp->addEntry((LSA *) ptr);
+    lsap = (LSA *) btree->sllhead;
+    for (; lsap; lsap = (LSA *) lsap->sll)
+	lp->addEntry(lsap);
 }
 
 /* Add an LSA to the database. If there is already a database copy, and
@@ -253,8 +257,14 @@
     if (hdr->ls_type >= LST_LINK_OPQ && hdr->ls_type <= LST_AS_OPQ)
         upload_opq(lsap);
     // If changes, schedule new routing calculations
-    if (changed)
+    if (changed) {
 	rtsched(lsap, old_rte);
+	// Only LS types 1-5 are significant for hitless restart
+	if (lsap->lsa_type <= LST_ASL)
+	    topology_change = true;
+	if (in_hitless_restart())
+	    htl_check_consistency(ap, hdr);
+    }
 
     return(lsap);
 }
@@ -500,6 +510,56 @@
 	}
 	ls_type = 0;
     } while ((ap = NextArea(a_id)));
+
+    return(lsap);
+}
+
+/* This version of Next LSA can be used to get Link-local LSAs.
+ * For link-local LSAs associated with virtual links, the
+ * taid is the virtual link's Transit Area (non-zero)
+ * and if_addr is the Router ID of the other endpoint of the
+ * virtual link.
+ */
+
+LSA *OSPF::NextLSA(InAddr if_addr, int phyint, aid_t taid, 
+		   byte ls_type, lsid_t id, rtid_t advrtr)
+
+{
+    LSA *lsap;
+    SpfIfc *ip;
+    AVLtree *tree;
+
+    // Iterate over all areas
+    lsap = 0;
+    ip = (taid ? find_vl(taid, if_addr) : find_ifc(if_addr, phyint));
+    do {
+	// Iterate over LS types
+	for (; ls_type <= MAX_LST; id = advrtr = 0, ++ls_type) {
+	    if (flooding_scope(ls_type) != LocalScope)
+	        continue;
+	    tree = FindLSdb(ip, 0, ls_type);
+	    if (tree) {
+	        AVLsearch iter(tree);
+		iter.seek(id, advrtr);
+	        if ((lsap = (LSA *) iter.next()))
+		    return(lsap);
+	    }
+	}
+	ls_type = 0;
+	if (ip && ip->is_virtual()) {
+	    taid = ip->transit_area()->a_id;
+	    if_addr = *ip->vl_endpt();
+	}
+	else if (ip) {
+	    if_addr = ip->if_addr;
+	    phyint = ip->if_phyint;
+	}
+	// Get next interface
+	if (taid) 
+	   ip = next_vl(taid, if_addr);
+	else if (!(ip = next_ifc(if_addr,phyint)))
+	   ip = next_vl(0, 0);
+    } while (ip);
 
     return(lsap);
 }
diff -X exclude_files -Nabur ospfd2.3/src/lshdr.h ospfd2.4/src/lshdr.h
--- ospfd2.3/src/lshdr.h	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/lshdr.h	Thu Sep 13 16:05:43 2001
@@ -174,3 +174,41 @@
     uns32 ls_type;	// Router-LSA or network-LSA
     rtid_t ls_id;	// Link State ID
 };
+
+/* Assigned Opaque Types.
+ */
+
+enum {
+    OPQ_T_TE = 1,	// Traffic Engineering extensions
+    OPQ_T_HLRST = 3,	// Hitless restart extensions
+};
+
+/* Format of the TLVs found in the body of some Opaque-LSAs.
+ * Length field covers only the body, not the header, and
+ * when the length is not a multiple of 4 bytes, the TLV
+ * is padded with zeroes.
+ */
+
+struct TLV {
+    uns16 type;
+    uns16 length;
+};
+
+/* TLV types used in the Hitless Restart extensions
+ */
+
+enum {
+    HLRST_PERIOD = 1,	// Length of grace period
+    HLRST_REASON = 2,	// Reason for restart
+    HLRST_IFADDR = 3,	// Interface address
+};
+
+/* Encodings for the reason for a hitless restart.
+ */
+
+enum {
+   HLRST_REASON_UNKNOWN = 0,
+   HLRST_REASON_RESTART = 1,
+   HLRST_REASON_RELOAD = 2,	// Reload/upgrade
+   HLRST_REASON_SWITCH = 3,	// Switch to redundant processor
+};
diff -X exclude_files -Nabur ospfd2.3/src/monitor.C ospfd2.4/src/monitor.C
--- ospfd2.3/src/monitor.C	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/monitor.C	Thu Sep 13 16:05:43 2001
@@ -69,6 +69,7 @@
     msg->body.statrsp.vmajor = vmajor;
     msg->body.statrsp.vminor = vminor;
     msg->body.statrsp.fill1 = 0;
+    msg->body.statrsp.n_orig_allocs = hton32(n_orig_allocs);
 
     sys->monitor_response(msg, Stat_Response, mlen, conn_id);
 }
@@ -430,6 +431,87 @@
     }
 
     sys->monitor_response(msg, LSA_Response, mlen, conn_id);
+}
+
+/* Respond to a query to access a Link-local LSA.
+ */
+
+void OSPF::lllsa_stats(class MonMsg *req, int conn_id)
+
+{
+    MonRqLLLsa *llreq;
+    InAddr if_addr;
+    int phyint;
+    aid_t taid;
+    byte ls_type;
+    lsid_t id;
+    rtid_t advrtr;
+    LSA *lsap;
+    int mlen;
+    MonMsg *msg;
+    char *phyname;
+
+    llreq = &req->body.lllsarq;
+    if_addr = ntoh32(llreq->if_addr);
+    phyint = ntoh32(llreq->phyint);
+    taid = ntoh32(llreq->taid);
+    ls_type = ntoh32(llreq->ls_type);
+    id = ntoh32(llreq->ls_id);
+    advrtr = ntoh32(llreq->adv_rtr);
+
+    lsap = 0;
+
+    if (req->hdr.exact != 0) {
+	SpfIfc *ip;
+	if (taid != 0)
+	    ip = find_vl(taid, if_addr);
+	else
+	    ip = find_ifc(if_addr, phyint);
+	if (ip)
+	    lsap = FindLSA(ip, 0, ls_type, id, advrtr);
+    } else
+        lsap = NextLSA(if_addr, phyint, taid, ls_type, id, advrtr);
+
+    mlen = sizeof(MonHdr) + sizeof(MonRqLLLsa);
+    if (lsap)
+        mlen += lsap->ls_length();
+    msg = get_monbuf(mlen);
+    msg->hdr.version = OSPF_MON_VERSION;
+    msg->hdr.retcode = 1;
+    msg->hdr.exact = req->hdr.exact;
+    msg->hdr.id = req->hdr.id;
+
+    if (lsap) {
+        MonRqLLLsa *llrsp;
+	LShdr *hdr;
+	SpfIfc *ip;
+	ip = lsap->lsa_ifp;
+	msg->hdr.retcode = 0;
+	llrsp = &msg->body.lllsarq;
+	if (!ip->is_virtual()) {
+	    llrsp->if_addr = hton32(ip->if_addr);
+	    llrsp->taid = 0;
+	    phyname = sys->phyname(ip->if_phyint);
+	    strncpy(llrsp->phyname, phyname, MON_PHYLEN);
+	}
+	else {
+	    char *p;
+	    llrsp->taid = hton32(ip->transit_area()->id());
+	    llrsp->if_addr = hton32(*ip->vl_endpt());
+	    p = (char *) &llrsp->taid;
+	    sprintf(llrsp->phyname, "%d.%d.%d.%d",
+		    (int)p[0], (int)p[1], (int)p[2], (int)p[3]);
+	}
+	llrsp->phyint = hton32(ip->if_phyint);
+	llrsp->a_id = hton32(ip->area()->id());
+	llrsp->ls_type = hton32(lsap->lsa_type);
+	llrsp->ls_id = hton32(lsap->ls_id());
+	llrsp->adv_rtr = hton32(lsap->adv_rtr());
+	hdr = BuildLSA(lsap);
+	memcpy((llrsp + 1), hdr, lsap->ls_length());
+    }
+
+    sys->monitor_response(msg, LLLSA_Response, mlen, conn_id);
 }
 
 /* Get information concerning a routing table entry.
diff -X exclude_files -Nabur ospfd2.3/src/monitor.h ospfd2.4/src/monitor.h
--- ospfd2.3/src/monitor.h	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/monitor.h	Thu Sep 13 16:05:43 2001
@@ -53,6 +53,20 @@
     uns32 adv_rtr;
 };
 
+struct MonRqLLLsa {
+    // Interface specification
+    InAddr if_addr;
+    int phyint;
+    aid_t taid;	// Transit area ID for virtual links
+    // Informational only
+    aid_t a_id;
+    char phyname[MON_PHYLEN]; // Interface name
+    // Link-local LSA specification
+    uns32 ls_type;
+    uns32 ls_id;
+    uns32 adv_rtr;
+};
+
 struct MonRqRte {
     InAddr net;
     InAddr mask;
@@ -77,6 +91,7 @@
     byte vmajor;
     byte vminor;
     uns16 fill1;
+    uns32 n_orig_allocs;
 };
 
 /* Response to a request for area statistics.
@@ -202,6 +217,7 @@
         MonRqVL vlrq;
 	MonRqNbr nbrrq;
 	MonRqLsa lsarq;
+        MonRqLLLsa lllsarq;
 	MonRqRte rtrq;
 
         StatRsp statrsp;// Responses
@@ -228,6 +244,7 @@
     MonReq_Rte,		// Dump routing table entry
     MonReq_OpqReg,	// Register for Opaque-LSAs
     MonReq_OpqNext,	// Get next Opaque-LSA
+    MonReq_LLLSA,	// Dump Link-local LSA contents
 
     Stat_Response = 100, // Global statistics response
     Area_Response,	// Area response
@@ -236,6 +253,7 @@
     LSA_Response,	// LSA
     Rte_Response,	// Routing table entry
     OpqLSA_Response,	// Opaque-LSA response
+    LLLSA_Response,	// Link-local LSA
 
     OSPF_MON_VERSION = 1, // Version of monitoring messages
 };
diff -X exclude_files -Nabur ospfd2.3/src/nbrfsm.C ospfd2.4/src/nbrfsm.C
--- ospfd2.3/src/nbrfsm.C	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/nbrfsm.C	Thu Sep 13 16:05:43 2001
@@ -228,7 +228,7 @@
     tap = n_ifp->transit_area();
     // now Full
     if (n_state == NBS_FULL) {
-        if (n_ifp->if_nfull++ == 0)
+        if (!we_are_helping() && n_ifp->if_nfull++ == 0)
 	    n_ifp->reorig_all_grplsas();
 	ospf->n_dbx_nbrs--;
 	n_progtim.stop();
@@ -242,12 +242,14 @@
 	ospf->n_dbx_nbrs++;
     // Never go from Full state immed back into dbxchng
     else if (n_ostate == NBS_FULL) {
+	if (!we_are_helping()) {
 	if (n_ifp->if_nfull-- == 1)
 	    n_ifp->reorig_all_grplsas();
 	if (tap && tap->n_VLs-- == 1)
 	    tap->rl_orig();
 	ap->rl_orig();
     }
+    }
     else if (n_state <= NBS_2WAY && n_ostate >= NBS_EXST) {
 	exit_dbxchg();
 	if (n_ostate > NBS_EXST)
@@ -475,7 +477,6 @@
     nba_clr_lists();
     n_dr = UnknownAddr;
     n_bdr = UnknownAddr;
-    demand_helapse = 0;
     rq_suppression = false;
 
     // Stop remaining timers
diff -X exclude_files -Nabur ospfd2.3/src/netlsa.C ospfd2.4/src/netlsa.C
--- ospfd2.3/src/netlsa.C	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/netlsa.C	Thu Sep 13 16:05:43 2001
@@ -30,35 +30,66 @@
 /* Originate a network-LSA. Must be the Designated Router for the
  * network, and be fully adjacent to at least one other
  * router.
+ * if_nfull includes all those neighbors that we
+ * are currently helping through hitless restart.
  */
 
 void SpfIfc::nl_orig(int forced)
 
 {
     LSA *olsap;
+    LShdr *hdr;
+
+    // If in hitless restart, queue exit check
+    if (ospf->in_hitless_restart())
+        ospf->check_htl_termination = true;
 
     olsap = ospf->myLSA(0, if_area, LST_NET, if_addr);
+    hdr = nl_raw_orig();
 
-    if (if_state != IFS_DR)
-	lsa_flush(olsap);
-    else if (if_nfull == 0)
+    if (hdr == 0)
 	lsa_flush(olsap);
     else {
+        seq_t seqno;
+	seqno = ospf->ospf_get_seqno(LST_NET, olsap, forced);
+	if (seqno != InvalidLSSeq) {
+	    // Fill in rest of LSA contents
+	    hdr->ls_seqno = hton32(seqno);
+	    (void) ospf->lsa_reorig(0, if_area, olsap, hdr, forced);
+	}
+	ospf->free_orig_buffer(hdr);
+    }
+}
+
+/* Build the contents of the network-LSA that should be
+ * originated for the interface. returning a pointer to the
+ * link-state header (built in a static memory space). If no
+ * network-LSA should be originated, 0 is returned.
+ * LS Sequence Number must be filled in by the caller, who also
+ * must call OSPF::free_orig_buffer() when done with the
+ * constructed LSA.
+ */
+
+LShdr *SpfIfc::nl_raw_orig()
+
+{
 	LShdr *hdr;
 	NetLShdr *nethdr;
 	uns16 length;
-	seq_t seqno;
 	rtid_t *nbr_ids;
 	NbrIterator iter(this);
 	SpfNbr *np;
+
+    if (if_state != IFS_DR)
+	return(0);
+    else if (if_nfull == 0)
+	return(0);
+
 	// Build new LSA
 	length = sizeof(NetLShdr) + (if_nfull+1)*sizeof(rtid_t);
 	length += sizeof(LShdr);
-	seqno = ospf->ospf_get_seqno(olsap, length, forced);
-	if (seqno == InvalidLSSeq)