Skip to content

Commit

Permalink
ospfd: Optimize and improve SPF nexthop calculation
Browse files Browse the repository at this point in the history 
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@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
  • Loading branch information
@joakim-tjernlund @eqvinox
joakim-tjernlund authored and eqvinox committed Jul 25, 2012
1 parent 7b92589 commit c81ee5c
Show file tree
Hide file tree
Showing 4 changed files with 100 additions and 83 deletions.
18 changes: 18 additions & 0 deletions ospfd/ospf_interface.c
View file
Expand Up @@ -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)
Expand Down Expand Up @@ -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);

Expand Down
6 changes: 6 additions & 0 deletions ospfd/ospf_interface.h
View file
Expand Up @@ -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 */
Expand Down Expand Up @@ -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
*,
Expand Down
2 changes: 2 additions & 0 deletions ospfd/ospf_lsa.c
View file
Expand Up @@ -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)
{
Expand All @@ -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;
}
}
}
Expand Down
157 changes: 74 additions & 83 deletions ospfd/ospf_spf.c
View file
Expand Up @@ -490,13 +490,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)
{
Expand All @@ -515,30 +517,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)
Expand All @@ -549,68 +559,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)
{
Expand Down Expand Up @@ -643,19 +638,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)
Expand Down Expand Up @@ -736,7 +725,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. */
Expand Down Expand Up @@ -765,6 +754,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));

Expand Down Expand Up @@ -886,7 +877,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");
Expand All @@ -906,7 +897,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
Expand All @@ -916,7 +907,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.
Expand Down

0 comments on commit c81ee5c

Please sign in to comment.