Joakim.Tjernlund at transmode
Jul 7, 2012, 8:06 AM
Post #1 of 45
(1051 views)
Permalink
|
|
[PATCH 1/4] ospfd: Optimize and improve SPF nexthop calculation
|
|
Maintain router LSA positions in OSPF interface.
Find the OSPF interface in nexthop_calculation using
the position in the router LSA. This is possible because
the only time nexthop_calculation needs to look up interfaces
is when dealing with its own Router LSA.
This has the following advantages:
- Multiple PtP interfaces with the same IP address between two routers.
- Use Unnumbered PtP on just one end of the link.
- Faster OI lookup for the OSPF interface and only
done once for PtoP links.
*ospf_interface.h: (struct ospf_interface) Add storage for
storing router LSA position.
*ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
lookup OSPF I/F in an area using LSA position.
*ospf_lsa.c: (router_lsa_link_set) record Router LSA position.
*ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
(ospf_nexthop_calculation) Add lsa position argument.
call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
Clean up and remove all calls ospf_if_is_configured() the
rest. Adjust a few debug logs.
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund [at] transmode>
---
ospfd/ospf_interface.c | 18 ++++++
ospfd/ospf_interface.h | 6 ++
ospfd/ospf_lsa.c | 2 +
ospfd/ospf_spf.c | 157 ++++++++++++++++++++++-------------------------
4 files changed, 100 insertions(+), 83 deletions(-)
diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index dc0787d..a37dde1 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -392,6 +392,21 @@ ospf_if_exists (struct ospf_interface *oic)
return NULL;
}
+/* Lookup OSPF interface by router LSA posistion */
+struct ospf_interface *
+ospf_if_lookup_by_lsa_pos (struct ospf_area *area, int lsa_pos)
+{
+ struct listnode *node;
+ struct ospf_interface *oi;
+
+ for (ALL_LIST_ELEMENTS_RO (area->oiflist, node, oi))
+ {
+ if (lsa_pos >= oi->lsa_pos_beg && lsa_pos < oi->lsa_pos_end)
+ return oi;
+ }
+ return NULL;
+}
+
struct ospf_interface *
ospf_if_lookup_by_local_addr (struct ospf *ospf,
struct interface *ifp, struct in_addr address)
@@ -801,6 +816,9 @@ ospf_if_down (struct ospf_interface *oi)
return 0;
OSPF_ISM_EVENT_EXECUTE (oi, ISM_InterfaceDown);
+ /* delete position in router LSA */
+ oi->lsa_pos_beg = 0;
+ oi->lsa_pos_end = 0;
/* Shutdown packet reception and sending */
ospf_if_stream_unset (oi);
diff --git a/ospfd/ospf_interface.h b/ospfd/ospf_interface.h
index 6db8877..9de6550 100644
--- a/ospfd/ospf_interface.h
+++ b/ospfd/ospf_interface.h
@@ -127,6 +127,10 @@ struct ospf_interface
/* OSPF Area. */
struct ospf_area *area;
+ /* Position range in Router LSA */
+ uint16_t lsa_pos_beg; /* inclusive, >= */
+ uint16_t lsa_pos_end; /* exclusive, < */
+
/* Interface data from zebra. */
struct interface *ifp;
struct ospf_vl_data *vl_data; /* Data for Virtual Link */
@@ -244,6 +248,8 @@ extern int ospf_if_down (struct ospf_interface *);
extern int ospf_if_is_up (struct ospf_interface *);
extern struct ospf_interface *ospf_if_exists (struct ospf_interface *);
+extern struct ospf_interface *ospf_if_lookup_by_lsa_pos (struct ospf_area *,
+ int);
extern struct ospf_interface *ospf_if_lookup_by_local_addr (struct ospf *,
struct interface
*,
diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index d5959eb..493209a 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -670,6 +670,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
{
if (oi->state != ISM_Down)
{
+ oi->lsa_pos_beg = links;
/* Describe each link. */
switch (oi->type)
{
@@ -691,6 +692,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area *area)
case OSPF_IFTYPE_LOOPBACK:
links += lsa_link_loopback_set (s, oi);
}
+ oi->lsa_pos_end = links;
}
}
}
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index d7f9ba2..e866d0c 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -477,13 +477,15 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w,
static unsigned int
ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
struct vertex *w, struct router_lsa_link *l,
- unsigned int distance)
+ unsigned int distance, int lsa_pos)
{
struct listnode *node, *nnode;
struct vertex_nexthop *nh;
struct vertex_parent *vp;
struct ospf_interface *oi = NULL;
unsigned int added = 0;
+ char buf1[BUFSIZ];
+ char buf2[BUFSIZ];
if (IS_DEBUG_OSPF_EVENT)
{
@@ -502,30 +504,38 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
the OSPF interface connecting to the destination network/router.
*/
+ /* we *must* be supplied with the link data */
+ assert (l != NULL);
+ oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
+ if (!oi)
+ {
+ zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
+ __func__, lsa_pos,
+ inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
+ inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
+ return 0;
+ }
+
+ if (IS_DEBUG_OSPF_EVENT)
+ {
+ zlog_debug("%s: considering link:%s "
+ "type:%d link_id:%s link_data:%s",
+ __func__, oi->ifp->name, l->m[0].type,
+ inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
+ inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
+ }
+
if (w->type == OSPF_VERTEX_ROUTER)
{
/* l is a link from v to w
* l2 will be link from w to v
*/
struct router_lsa_link *l2 = NULL;
-
- /* we *must* be supplied with the link data */
- assert (l != NULL);
-
- if (IS_DEBUG_OSPF_EVENT)
- {
- char buf1[BUFSIZ];
- char buf2[BUFSIZ];
-
- zlog_debug("ospf_nexthop_calculation(): considering link "
- "type %d link_id %s link_data %s",
- l->m[0].type,
- inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
- inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
- }
if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
{
+ struct in_addr nexthop;
+
/* If the destination is a router which connects to
the calculating router via a Point-to-MultiPoint
network, the destination's next hop IP address(es)
@@ -536,68 +546,53 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
provides an IP address of the next hop router.
At this point l is a link from V to W, and V is the
- root ("us"). Find the local interface associated
- with l (its address is in l->link_data). If it
- is a point-to-multipoint interface, then look through
- the links in the opposite direction (W to V). If
- any of them have an address that lands within the
+ root ("us"). If it is a point-to-multipoint interface,
+ then look through the links in the opposite direction (W to V).
+ If any of them have an address that lands within the
subnet declared by the PtMP link, then that link
- is a constituent of the PtMP link, and its address is
+ is a constituent of the PtMP link, and its address is
a nexthop address for V.
*/
- oi = ospf_if_is_configured (area->ospf, &l->link_data);
- if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
- {
- struct prefix_ipv4 la;
-
- la.family = AF_INET;
- la.prefixlen = oi->address->prefixlen;
-
- /* V links to W on PtMP interface
- - find the interface address on W */
- while ((l2 = ospf_get_next_link (w, v, l2)))
- {
- la.prefix = l2->link_data;
-
- if (prefix_cmp ((struct prefix *) &la,
- oi->address) == 0)
- /* link_data is on our PtMP network */
- break;
- }
- } /* end l is on point-to-multipoint link */
- else
- {
- /* l is a regular point-to-point link.
- Look for a link from W to V.
- */
- while ((l2 = ospf_get_next_link (w, v, l2)))
- {
- oi = ospf_if_is_configured (area->ospf,
- &(l2->link_data));
-
- if (oi == NULL)
- continue;
-
- if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
- &l->link_data))
- continue;
-
- break;
- }
- }
-
- if (oi && l2)
+ if (oi->type == OSPF_IFTYPE_POINTOPOINT)
+ {
+ added = 1;
+ nexthop.s_addr = 0; /* Nexthop not required */
+ }
+ else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
+ {
+ struct prefix_ipv4 la;
+
+ la.family = AF_INET;
+ la.prefixlen = oi->address->prefixlen;
+
+ /* V links to W on PtMP interface
+ - find the interface address on W */
+ while ((l2 = ospf_get_next_link (w, v, l2)))
+ {
+ la.prefix = l2->link_data;
+
+ if (prefix_cmp ((struct prefix *) &la,
+ oi->address) != 0)
+ continue;
+ /* link_data is on our PtMP network */
+ added = 1;
+ nexthop = l2->link_data;
+ break;
+ }
+ }
+
+ if (added)
{
/* found all necessary info to build nexthop */
nh = vertex_nexthop_new ();
nh->oi = oi;
- nh->router = l2->link_data;
+ nh->router = nexthop;
ospf_spf_add_parent (v, w, nh, distance);
return 1;
}
else
- zlog_info("ospf_nexthop_calculation(): "
- "could not determine nexthop for link");
+ zlog_info("%s: could not determine nexthop for link %s",
+ __func__, oi->ifp->name);
} /* end point-to-point link from V to W */
else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
{
@@ -630,19 +625,13 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
else
{
assert(w->type == OSPF_VERTEX_NETWORK);
- oi = ospf_if_is_configured (area->ospf, &(l->link_data));
- if (oi)
- {
- nh = vertex_nexthop_new ();
- nh->oi = oi;
- nh->router.s_addr = 0;
- ospf_spf_add_parent (v, w, nh, distance);
- return 1;
- }
+
+ nh = vertex_nexthop_new ();
+ nh->oi = oi;
+ nh->router.s_addr = 0; /* Nexthop not required */
+ ospf_spf_add_parent (v, w, nh, distance);
+ return 1;
}
- zlog_info("ospf_nexthop_calculation(): "
- "Unknown attached link");
- return 0;
} /* end V is the root */
/* Check if W's parent is a network connected to root. */
else if (v->type == OSPF_VERTEX_NETWORK)
@@ -723,7 +712,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
u_char *lim;
struct router_lsa_link *l = NULL;
struct in_addr *r;
- int type = 0;
+ int type = 0, lsa_pos=-1, lsa_pos_next=0;
/* If this is a router-LSA, and bit V of the router-LSA (see Section
A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
@@ -752,6 +741,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
{
l = (struct router_lsa_link *) p;
+ lsa_pos = lsa_pos_next; /* LSA link position */
+ lsa_pos_next++;
p += (OSPF_ROUTER_LSA_LINK_SIZE +
(l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
@@ -873,7 +864,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
w = ospf_vertex_new (w_lsa);
/* Calculate nexthop to W. */
- if (ospf_nexthop_calculation (area, v, w, l, distance))
+ if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
pqueue_enqueue (w, candidate);
else if (IS_DEBUG_OSPF_EVENT)
zlog_debug ("Nexthop Calc failed");
@@ -893,7 +884,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
{
/* Found an equal-cost path to W.
* Calculate nexthop of to W from V. */
- ospf_nexthop_calculation (area, v, w, l, distance);
+ ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
}
/* less than. */
else
@@ -903,7 +894,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
* valid nexthop it will call spf_add_parents, which
* will flush the old parents
*/
- if (ospf_nexthop_calculation (area, v, w, l, distance))
+ if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
/* Decrease the key of the node in the heap.
* trickle-sort it up towards root, just in case this
* node should now be the new root due the cost change.
--
1.7.3.4
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev
|
