[PATCH] ospf: improve nexthop_calc

Joakim Tjernlund Joakim.Tjernlund at transmode.se
Fri Dec 17 10:03:32 CET 2010


Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund at transmode.se>
---
 proto/ospf/iface.c    |    4 +++-
 proto/ospf/ospf.h     |   21 +++++++++++++++++++++
 proto/ospf/rt.c       |   38 ++++++++++++++++++++------------------
 proto/ospf/topology.c |    5 +++--
 4 files changed, 47 insertions(+), 21 deletions(-)

diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 8b21f94..53de2f4 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -203,6 +203,8 @@ ospf_iface_down(struct ospf_iface *ifa)
     ifa->cost = 0;
     ifa->vip = IPA_NONE;
   }
+  /* delete position in router LSA */
+  ospf_lsa_pos_set(0, 0, ifa);
 }


@@ -422,7 +424,7 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, struct ifa *addr,
   ifa->iface = iface;
   ifa->addr = addr;
   ifa->pool = pool;
-
+  ospf_lsa_pos_set(0, 0, ifa);
   ifa->cost = ip->cost;
   ifa->rxmtint = ip->rxmtint;
   ifa->inftransdelay = ip->inftransdelay;
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 2ef0180..62e71e2 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -189,6 +189,8 @@ struct ospf_iface
   u32 csn;                      /* Last used crypt seq number */
   bird_clock_t csn_use;         /* Last time when packet with that CSN was sent */
 #endif
+  u32 lsa_pos_beg; /* inclusive, >= */
+  u32 lsa_pos_end; /* exclusive, <  */

   ip_addr drip;			/* Designated router */
   ip_addr bdrip;		/* Backup DR */
@@ -821,6 +823,25 @@ void ospf_sh_iface(struct proto *p, char *iff);
 void ospf_sh_state(struct proto *p, int verbose, int reachable);
 void ospf_sh_lsadb(struct proto *p);

+static inline struct ospf_iface *
+ospf_pos_to_ifa (struct ospf_area *oa, int lsa_pos)
+{
+    struct proto_ospf *po = oa->po;
+    struct ospf_iface *ifa;
+
+    WALK_LIST(ifa, po->iface_list)
+	if (lsa_pos >= ifa->lsa_pos_beg && lsa_pos < ifa->lsa_pos_end)
+	    return ifa;
+    return NULL;
+}
+
+static inline void
+ospf_lsa_pos_set(int beg, int end,
+		 struct ospf_iface * ifa)
+{
+    ifa->lsa_pos_beg = beg;
+    ifa->lsa_pos_end = end;
+}

 #define EA_OSPF_METRIC1	EA_CODE(EAP_OSPF, 0)
 #define EA_OSPF_METRIC2	EA_CODE(EAP_OSPF, 1)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 6b8886b..e410603 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -10,7 +10,7 @@

 static void add_cand(list * l, struct top_hash_entry *en,
 		     struct top_hash_entry *par, u32 dist,
-		     struct ospf_area *oa, struct ospf_lsa_rt_link *rtl);
+		     struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 pos);
 static void rt_sync(struct proto_ospf *po);

 /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
@@ -396,7 +396,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct to
       if (tmp)
 	DBG("Going to add cand, Mydist: %u, Req: %u\n",
 	    tmp->dist, act->dist + rtl->metric);
-      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, rtl);
+      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, rtl, i);
     }
 }

@@ -494,7 +494,7 @@ ospf_rt_spfa(struct ospf_area *oa)
 	  DBG("Found :-)\n");
 	else
 	  DBG("Not found!\n");
-	add_cand(&oa->cand, tmp, act, act->dist, oa, NULL);
+	add_cand(&oa->cand, tmp, act, act->dist, oa, NULL, i);
       }
       break;
     }
@@ -1351,7 +1351,7 @@ inherit_nexthops(struct mpnh *pn)

 static struct mpnh *
 calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
-	      struct top_hash_entry *par, struct ospf_lsa_rt_link *rtl)
+	      struct top_hash_entry *par, struct ospf_lsa_rt_link *rtl, u32 pos)
 {
   // struct proto *p = &oa->po->proto;
   struct proto_ospf *po = oa->po;
@@ -1377,9 +1377,12 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
   /* The first case - local network */
   if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
   {
-    WALK_LIST(ifa, po->iface_list)
-      if (match_dr(ifa, en))
-	return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
+    ifa = ospf_pos_to_ifa(oa, pos);
+    if (!ifa)
+	 return NULL;
+
+    if (match_dr(ifa, en))
+	 return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);

     return NULL;
   }
@@ -1389,15 +1392,14 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
   {
     if (rtl->type == LSART_VLNK)
       return new_nexthop(po, IPA_NONE, NULL, 0);
-
-    WALK_LIST(ifa, po->iface_list)
-      if (match_rtlink(ifa, rtl))
-      {
-	struct ospf_neighbor *m = find_neigh(ifa, rid);
-	if (m && (m->state == NEIGHBOR_FULL))
-	  return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
-      }
-
+    ifa = ospf_pos_to_ifa(oa, pos);
+    if (!ifa)
+	 return NULL;
+    {
+	 struct ospf_neighbor *m = find_neigh(ifa, rid);
+	 if (m && (m->state == NEIGHBOR_FULL))
+	      return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
+    }
     return NULL;
   }

@@ -1523,7 +1525,7 @@ merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en,
 /* Add LSA into list of candidates in Dijkstra's algorithm */
 static void
 add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
-	 u32 dist, struct ospf_area *oa, struct ospf_lsa_rt_link *rtl)
+	 u32 dist, struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 pos)
 {
   struct proto_ospf *po = oa->po;
   node *prev, *n;
@@ -1557,7 +1559,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
   if (!link_back(oa, en, par))
     return;

-  struct mpnh *nhs = calc_next_hop(oa, en, par, rtl);
+  struct mpnh *nhs = calc_next_hop(oa, en, par, rtl, pos);
   if (!nhs)
   {
     log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index e604bf8..0d333bf 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -228,8 +228,9 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)

   WALK_LIST(ifa, po->iface_list)
   {
-    int net_lsa = 0;
+    int net_lsa = 0, beg_pos;

+    beg_pos = i;
     if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
 	(!EMPTY_LIST(ifa->neigh_list)))
     {
@@ -291,7 +292,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
         log("Unknown interface type %s", ifa->iface->name);
         break;
       }
-
+    ospf_lsa_pos_set(beg_pos, i, ifa);
     /* Now we will originate stub area if there is no primary */
     if (net_lsa ||
 	(ifa->type == OSPF_IT_VLINK) ||
--
1.7.2.2





More information about the Bird-users mailing list