[PATCH] ospfd: Optimize and improve SPF nexthop calculation
Joakim Tjernlund
Joakim.Tjernlund at transmode.se
Fri Aug 7 20:57:51 CEST 2009
Maintain router LSA positions in OSPF interface.
Find the OSPF interface in nexthop_calculation using
the position in the router LSA.
This has the following advantages:
- Multiple PtP interfaces with the same IP address between two rout=
ers.
- 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_pos_set) assign LSA position to OSPF
interface.
*ospf_lsa.c: (router_lsa_link_set) Call ospf_lsa_pos_set() to record
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.
---
ospfd/ospf_interface.c | 28 ++++++++-
ospfd/ospf_interface.h | 7 ++
ospfd/ospf_lsa.c | 4 +-
ospfd/ospf_spf.c | 158 ++++++++++++++++++++++------------------=
-------
4 files changed, 111 insertions(+), 86 deletions(-)
diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index afe3acf..f11fdef 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -211,7 +211,9 @@ ospf_if_new (struct ospf *ospf, struct interface *i=
fp, struct prefix *p)
}
else
return oi;
-
+
+ ospf_lsa_pos_set(-1,-1, oi); /* delete position in router LSA */
+
/* Set zebra interface pointer. */
oi->ifp =3D ifp;
oi->address =3D p;
@@ -397,6 +399,29 @@ 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 >=3D oi->lsa_pos_beg && lsa_pos < oi->lsa_pos_end)
+ return oi;
+ }
+ return NULL;
+}
+
+/* Set OSPF interface position in router LSA */
+void
+ospf_lsa_pos_set(int pos_beg, int pos_end, struct ospf_interface *oi)
+{
+ oi->lsa_pos_beg =3D pos_beg;
+ oi->lsa_pos_end =3D pos_end;
+}
+
struct ospf_interface *
ospf_if_lookup_by_local_addr (struct ospf *ospf,
struct interface *ifp, struct in_addr address)
@@ -803,6 +828,7 @@ ospf_if_down (struct ospf_interface *oi)
return 0;
OSPF_ISM_EVENT_EXECUTE (oi, ISM_InterfaceDown);
+ ospf_lsa_pos_set(-1, -1, oi); /* delete position in router LSA */
/* Shutdown packet reception and sending */
ospf_if_stream_unset (oi);
diff --git a/ospfd/ospf_interface.h b/ospfd/ospf_interface.h
index ab0b758..cd39411 100644
--- a/ospfd/ospf_interface.h
+++ b/ospfd/ospf_interface.h
@@ -124,6 +124,10 @@ struct ospf_interface
/* OSPF Area. */
struct ospf_area *area;
+ /* Position range in Router LSA */
+ int lsa_pos_beg; /* inclusive, >=3D */
+ int lsa_pos_end; /* exclusive, < */
+
/* Interface data from zebra. */
struct interface *ifp;
struct ospf_vl_data *vl_data; /* Data for Virtual Link */
@@ -242,6 +246,9 @@ 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_a=
rea *,
+ int);
+extern void ospf_lsa_pos_set(int, int, struct ospf_interface *);
extern struct ospf_interface *ospf_if_lookup_by_local_addr (struct osp=
f *,
struct interface
*,
diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index 0ba1834..3cbd99b 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -659,7 +659,7 @@ router_lsa_link_set (struct stream *s, struct ospf_=
area *area)
{
struct listnode *node;
struct ospf_interface *oi;
- int links =3D 0;
+ int links =3D 0, old_links;
for (ALL_LIST_ELEMENTS_RO (area->oiflist, node, oi))
{
@@ -670,6 +670,7 @@ router_lsa_link_set (struct stream *s, struct ospf_=
area *area)
{
if (oi->state !=3D ISM_Down)
{
+ old_links =3D 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 +=3D lsa_link_loopback_set (s, oi);
}
+ ospf_lsa_pos_set(old_links, links, oi);
}
}
}
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 610fc9b..3cac594 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -480,13 +480,15 @@ ospf_spf_add_parent (struct vertex *v, struct ver=
tex *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 =3D NULL;
unsigned int added =3D 0;
+ char buf1[BUFSIZ];
+ char buf2[BUFSIZ];
if (IS_DEBUG_OSPF_EVENT)
{
@@ -505,30 +507,38 @@ ospf_nexthop_calculation (struct ospf_area *area,=
struct vertex *v,
the OSPF interface connecting to the destination network/rout=
er.
*/
+ /* we *must* be supplied with the link data */
+ assert (l !=3D NULL);
+ oi =3D 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_dat=
a:%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 =3D=3D OSPF_VERTEX_ROUTER)
{
/* l is a link from v to w
* l2 will be link from w to v
*/
struct router_lsa_link *l2 =3D NULL;
-
- /* we *must* be supplied with the link data */
- assert (l !=3D 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, BUFSI=
Z));
- }
if (l->m[0].type =3D=3D 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)
@@ -539,68 +549,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 =3D ospf_if_is_configured (area->ospf, &l->link_data)=
;
- if (oi && oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT)
- {
- struct prefix_ipv4 la;
-
- la.family =3D AF_INET;
- la.prefixlen =3D oi->address->prefixlen;
-
- /* V links to W on PtMP interface
- - find the interface address on W */
- while ((l2 =3D ospf_get_next_link (w, v, l2)))
- {
- la.prefix =3D l2->link_data;
-
- if (prefix_cmp ((struct prefix *) &la,
- oi->address) =3D=3D 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 =3D ospf_get_next_link (w, v, l2)))
- {
- oi =3D ospf_if_is_configured (area->ospf,
- &(l2->link_data));
-
- if (oi =3D=3D NULL)
- continue;
-
- if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
- &l->link_data))
- continue;
-
- break;
- }
- }
-
- if (oi && l2)
+ if (oi->type =3D=3D OSPF_IFTYPE_POINTOPOINT)
+ {
+ added =3D 1;
+ nexthop.s_addr =3D 0; /* Nexthop not required */
+ }
+ else if (oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT)
+ {
+ struct prefix_ipv4 la;
+
+ la.family =3D AF_INET;
+ la.prefixlen =3D oi->address->prefixlen;
+
+ /* V links to W on PtMP interface
+ - find the interface address on W */
+ while ((l2 =3D ospf_get_next_link (w, v, l2)))
+ {
+ la.prefix =3D l2->link_data;
+
+ if (prefix_cmp ((struct prefix *) &la,
+ oi->address) !=3D 0)
+ continue;
+ /* link_data is on our PtMP network */
+ added =3D 1;
+ nexthop =3D l2->link_data;
+ break;
+ }
+ }
+
+ if (added)
{
/* found all necessary info to build nexthop */
nh =3D vertex_nexthop_new ();=
nh->oi =3D oi;
- nh->router =3D l2->link_data;
+ nh->router =3D 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 =3D=3D LSA_LINK_TYPE_VIRTUALLINK)
{
@@ -633,19 +628,13 @@ ospf_nexthop_calculation (struct ospf_area *area,=
struct vertex *v,
else
{
assert(w->type =3D=3D OSPF_VERTEX_NETWORK);
- oi =3D ospf_if_is_configured (area->ospf, &(l->link_data));
- if (oi)
- {
- nh =3D vertex_nexthop_new ();
- nh->oi =3D oi;
- nh->router.s_addr =3D 0;
- ospf_spf_add_parent (v, w, nh, distance);
- return 1;
- }
+
+ nh =3D vertex_nexthop_new ();
+ nh->oi =3D oi;
+ nh->router.s_addr =3D 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 =3D=3D OSPF_VERTEX_NETWORK)
@@ -714,7 +703,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
u_char *lim;
struct router_lsa_link *l =3D NULL;
struct in_addr *r;
- int type =3D 0;
+ int type =3D 0, lsa_pos=3D-1, lsa_pos_next=3D0;
/* 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. *=
/
@@ -742,7 +731,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
if (v->lsa->type =3D=3D OSPF_ROUTER_LSA)
{
l =3D (struct router_lsa_link *) p;
-
+ lsa_pos =3D lsa_pos_next; /* LSA link position */
+ lsa_pos_next++;
p +=3D (ROUTER_LSA_MIN_SIZE +
(l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
@@ -864,7 +854,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
w =3D 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_p=
os))
pqueue_enqueue (w, candidate);
else if (IS_DEBUG_OSPF_EVENT)
zlog_debug ("Nexthop Calc failed");
@@ -884,7 +874,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
@@ -894,7 +884,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.6.4.4
=
More information about the Bird-users
mailing list