>
> Ondrej Zajicek <santi...@crfreenet.org> wrote on 2010/04/21 20:15:07:
> > On Wed, Apr 21, 2010 at 09:41:47AM +0200, Joakim Tjernlund wrote:
> > > I am using Quagga ATM but I had a quick look at BIRD and I got a few
> > > observations.
> >
> > Hello. Thank you for your tips and notes.
> >
> > > The LSA/checksum code seem very inefficient.
> > > LSAs are built allocating/reallocing bits
> > > of memory. This is slow and will case memory fragmentation.
> >
> > You mean lsab_alloc() in originate_rt_lsa_body()?
> > This allocation is just a sequential allocation in a persistent memory
> > buffer,
> > therefore it is very efficient (in most cases just increase of lsab_used
> > counter)
> > and there si no memory fragmentation (all is done inside a persistent
> > memory buffer).
>
> Yes, you do realloc on small amounts of memory. Also, receives LSAs
> seems to be impl. differently so you need handle these somewhat
> differently.
> >
> > > The fletcher checksum is very slow as it has extra tests in the hot path
> > > and also
> > > flips endian in the LSA back and forth.
> >
> > Do you have some suggestions for a better algorithm, or just a better
> > implementation? Yes, the problem with flipping endianity is known.
> > I do not studied this part of the code yet (the checksum algorithm).
>
> Yes, but not at the moment. The endian problem should be addressed when you
> build the lsa.
>
> >
> > > I can't work out how the SPF next hop works(calc_next_hop). I tried to
> compare it with
> > > Quagga's ospf_nexthop_calculation() but the structure is too different.
> > > The reason
> > > for me looking into this was to see how much work it would be to add
> > unnumbered ppp links
> > > but as I can't work out how nexthop is working I didn't get very far.
> >
> > The current code is different from what RFC says. For direct neighbors
> > (on both ptp and non-ptp networks), we just use IP address taken from
> > the source address of the HELLO packet of the neighbor (stored in
> > neighbor structure returned by find_neigh_noifa()).
> >
> > This works well [*] for both broadcast and ptp links (numbered or
> > unnumbered), but is broken on NBMA networks. I have some not-yet-commited
> > changes to calc_next_hop() that on broadcast and NBMA networks uses the
> > standard way (taking IP address from the router LSA) and the source address
> > from HELLO packet as a nexthop is used just for PTP links.
> > Such behavior is also suggested by RFC 5340 (for OSFPv3).
> >
> > [*] Regardless of how the other side is implemented.
> >
> > > I have impl. unnumbered ppp link for Quagga that works really well but
> > > this work
> > > hasn't been accepted into Quagga yet since Quagga development has stalled.
> > > I could show you how I did it Quagga though.
> >
> > The development state of Quagga is sad. Do you implement it in a different
> > way than in BIRD? I wonder whether there is any other possible way to get
> > next hop address for unnumbered ptp links than from source address
> > of HELLO packet.
> Yep, now it gets tricky. It took me quite some time to figure out what to
> do. The secret is that you never use search for the interface using IP
> addresses
> in the LSA's. Instead you record what interface created what entry in in your
> own Router LSA. Based on the position of on entry in your own router
> LSA you can lookup the interface that created that entry. Once
> you know the interface, the reset is easy.
>
> One way to impl. this is to build an array of interface pointers when
> you construct the Router LSA:
> RLSA Array
> Item 0 ptr to ppp0
> Item 1 ptr to ppp0
> Item 2 ptr to eth0
> ...
> Item n ptr to if n
>
> Now you can easily find the interface if you pass on the position of the
> the entry in the RLSA you are processing to the nexthop calculation.
>
> I have a few patches to Quagga that does this somewhere, they are all
> on the Quagga mailing list and a few of them are also in my personal
> git repo at the Quagga site.
>
> Jocke
Found two different impl. I did for Quagga. Figured you could use
them to get an idea.
>From e4703f876b2085fdb583a3ee8bd5d524255f71e4 Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund <joakim.tjernl...@transmode.se>
Date: Tue, 3 Jun 2008 18:41:28 +0200
Subject: [PATCH] [ospfd] Optimize and improve SPF nexthop calculation
Maintain a table of OSPF interface pointers paralell
to the router LSA. Use the table in nexthop_calculation to
find the right OSPF interface for the nexthop.
This has the following advantages:
- Possible to have multiple PtP interfaces with the same
IP address between two routers.
- Possible to use Unnumbered PtP on just one end of
the link.
- No more seaching for the OSPF interface, hence much faster.
---
ospfd/ospf_interface.c | 2 +
ospfd/ospf_lsa.c | 91 +++++++++++++++++++++++++++--
ospfd/ospf_lsa.h | 12 ++++
ospfd/ospf_spf.c | 151 +++++++++++++++++++++++++----------------------
4 files changed, 179 insertions(+), 77 deletions(-)
diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index afe3acf..fc39a81 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -335,6 +335,8 @@ ospf_if_free (struct ospf_interface *oi)
listnode_delete (oi->ospf->oiflist, oi);
listnode_delete (oi->area->oiflist, oi);
+ ospf_oi_seq_if_delete(oi);
+
memset (oi, 0, sizeof (*oi));
XFREE (MTYPE_OSPF_IF, oi);
}
diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index 0ba1834..a12dd7a 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -241,6 +241,27 @@ ospf_lsa_dup (struct ospf_lsa *lsa)
return new;
}
+static void
+ospf_lsa_oi_seq_free (struct lsa_oi_seq *oi_seq)
+{
+ XFREE (MTYPE_OSPF_LSA_DATA, oi_seq->seq_nr);
+ XFREE (MTYPE_OSPF_LSA_DATA, oi_seq);
+}
+
+void
+ospf_oi_seq_if_delete(struct ospf_interface *oi)
+{
+ int i;
+ struct ospf_lsa *lsa = oi->area->router_lsa_self;
+
+ if (!lsa || !lsa->oi_seq)
+ return;
+ /* "delete" all entries of oi */
+ for (i=0; i < lsa->oi_seq->length/sizeof(seq_nr_t); i++)
+ if (lsa->oi_seq->seq_nr[i] == oi)
+ lsa->oi_seq->seq_nr[i] = NULL;
+}
+
/* Free OSPF LSA. */
void
ospf_lsa_free (struct ospf_lsa *lsa)
@@ -254,6 +275,8 @@ ospf_lsa_free (struct ospf_lsa *lsa)
if (lsa->data != NULL)
ospf_lsa_data_free (lsa->data);
+ if (lsa->oi_seq != NULL)
+ ospf_lsa_oi_seq_free (lsa->oi_seq);
assert (lsa->refresh_list < 0);
memset (lsa, 0, sizeof (struct ospf_lsa));
@@ -306,6 +329,24 @@ ospf_lsa_data_new (size_t size)
return XCALLOC (MTYPE_OSPF_LSA_DATA, size);
}
+static struct lsa_oi_seq *
+ospf_lsa_oi_seq_new (void)
+{
+ struct lsa_oi_seq *new;
+
+ new = XCALLOC (MTYPE_OSPF_LSA_DATA, sizeof(*new));
+ return new;
+}
+
+static seq_nr_t *
+ospf_lsa_oi_seq_data_new (size_t size)
+{
+ seq_nr_t *new;
+
+ new = XMALLOC (MTYPE_OSPF_LSA_DATA, size);
+ return new;
+}
+
/* Duplicate LSA data. */
struct lsa_header *
ospf_lsa_data_dup (struct lsa_header *lsah)
@@ -318,6 +359,18 @@ ospf_lsa_data_dup (struct lsa_header *lsah)
return new;
}
+static void *
+ospf_lsa_oi_seq_dup (struct lsa_oi_seq *oi_seq)
+{
+ struct lsa_oi_seq *new;
+
+ new = ospf_lsa_oi_seq_new ();
+ new->length = oi_seq->length;
+ new->seq_nr = ospf_lsa_oi_seq_data_new (oi_seq->length);
+ memcpy (new->seq_nr, oi_seq->seq_nr, oi_seq->length);
+ return new;
+}
+
/* Free LSA data. */
void
ospf_lsa_data_free (struct lsa_header *lsah)
@@ -653,13 +706,24 @@ lsa_link_ptomp_set (struct stream *s, struct
ospf_interface *oi)
return links;
}
+struct ospf_interface *
+router_lsa_to_oi(struct ospf_lsa *lsa, int index)
+{
+ if (lsa->oi_seq && index >= 0)
+ return lsa->oi_seq->seq_nr[index];
+
+ zlog_debug ("%s: oi_seq:%p, index:%d!",
+ __func__, lsa->oi_seq, index);
+ return NULL;
+}
/* Set router-LSA link information. */
static int
-router_lsa_link_set (struct stream *s, struct ospf_area *area)
+router_lsa_link_set (struct stream *s, seq_nr_t oi_list[],
+ struct ospf_area *area)
{
struct listnode *node;
struct ospf_interface *oi;
- int links = 0;
+ int links = 0, old_links, i;
for (ALL_LIST_ELEMENTS_RO (area->oiflist, node, oi))
{
@@ -670,6 +734,7 @@ router_lsa_link_set (struct stream *s, struct ospf_area
*area)
{
if (oi->state != ISM_Down)
{
+ old_links = links;
/* Describe each link. */
switch (oi->type)
{
@@ -691,6 +756,8 @@ router_lsa_link_set (struct stream *s, struct ospf_area
*area)
case OSPF_IFTYPE_LOOPBACK:
links += lsa_link_loopback_set (s, oi);
}
+ for (i = old_links; i < links; i++)
+ oi_list[i] = oi;
}
}
}
@@ -699,8 +766,9 @@ router_lsa_link_set (struct stream *s, struct ospf_area
*area)
}
/* Set router-LSA body. */
-static void
-ospf_router_lsa_body_set (struct stream *s, struct ospf_area *area)
+static u_int16_t
+ospf_router_lsa_body_set (struct stream *s, seq_nr_t oi_list[],
+ struct ospf_area *area)
{
unsigned long putp;
u_int16_t cnt;
@@ -718,10 +786,12 @@ ospf_router_lsa_body_set (struct stream *s, struct
ospf_area *area)
stream_putw(s, 0);
/* Set all link information. */
- cnt = router_lsa_link_set (s, area);
+ cnt = router_lsa_link_set (s, oi_list, area);
/* Set # of links here. */
stream_putw_at (s, putp, cnt);
+
+ return cnt;
}
static int
@@ -790,6 +860,9 @@ ospf_router_lsa_new (struct ospf_area *area)
struct lsa_header *lsah;
struct ospf_lsa *new;
int length;
+ u_int16_t cnt;
+ /* oi_list, less than 1KB, allocat on stack */
+ seq_nr_t oi_list[((OSPF_MAX_LSA_SIZE*2)/3)/sizeof(seq_nr_t)];
if (IS_DEBUG_OSPF (lsa, LSA_GENERATE))
zlog_debug ("LSA[Type1]: Create router-LSA instance");
@@ -806,7 +879,8 @@ ospf_router_lsa_new (struct ospf_area *area)
OSPF_ROUTER_LSA, ospf->router_id, ospf->router_id);
/* Set router-LSA body fields. */
- ospf_router_lsa_body_set (s, area);
+ memset(oi_list, 0, sizeof(oi_list));
+ cnt = ospf_router_lsa_body_set (s, oi_list, area);
/* Set length. */
length = stream_get_endp (s);
@@ -826,6 +900,11 @@ ospf_router_lsa_new (struct ospf_area *area)
/* Copy LSA data to store, discard stream. */
new->data = ospf_lsa_data_new (length);
memcpy (new->data, lsah, length);
+
+ new->oi_seq = ospf_lsa_oi_seq_new ();
+ new->oi_seq->length = cnt*sizeof(seq_nr_t);
+ new->oi_seq->seq_nr = ospf_lsa_oi_seq_data_new (new->oi_seq->length);
+ memcpy (new->oi_seq->seq_nr, oi_list, new->oi_seq->length);
stream_free (s);
return new;
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h
index 8dd054c..7bee1dc 100644
--- a/ospfd/ospf_lsa.h
+++ b/ospfd/ospf_lsa.h
@@ -68,6 +68,13 @@ struct lsa_header
u_int16_t length;
};
+#define seq_nr_t struct ospf_interface *
+/* Router LSA sequnce number list */
+struct lsa_oi_seq {
+ u_int16_t length;
+ seq_nr_t *seq_nr;
+};
+
/* OSPF LSA. */
struct ospf_lsa
{
@@ -84,6 +91,9 @@ struct ospf_lsa
/* LSA data. */
struct lsa_header *data;
+ /* Router LSA OI sequence number */
+ struct lsa_oi_seq *oi_seq;
+
/* Received time stamp. */
struct timeval tv_recv;
@@ -247,10 +257,12 @@ extern void ospf_lsa_free (struct ospf_lsa *);
extern struct ospf_lsa *ospf_lsa_lock (struct ospf_lsa *);
extern void ospf_lsa_unlock (struct ospf_lsa **);
extern void ospf_lsa_discard (struct ospf_lsa *);
+extern struct ospf_interface * router_lsa_to_oi(struct ospf_lsa *, int);
extern struct lsa_header *ospf_lsa_data_new (size_t);
extern struct lsa_header *ospf_lsa_data_dup (struct lsa_header *);
extern void ospf_lsa_data_free (struct lsa_header *);
+extern void ospf_oi_seq_if_delete(struct ospf_interface *);
/* Prototype for various LSAs */
extern int ospf_router_lsa_update_timer (struct thread *);
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 610fc9b..07a31c5 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -480,13 +480,16 @@ 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)
{
@@ -505,30 +508,41 @@ 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 = router_lsa_to_oi(area->router_lsa_self, 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 (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 "
+ zlog_debug("%s: considering link "
"type %d link_id %s link_data %s",
- l->m[0].type,
+ __func__, 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)
{
+ int nh_found = 0;
+ struct in_addr nexthop;
+ unsigned long ifindex;
+
/* 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)
@@ -548,59 +562,50 @@ ospf_nexthop_calculation (struct ospf_area *area, struct
vertex *v,
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)
+ {
+ if (ntohl(l->link_data.s_addr) <= 0x00ffffff)
+ nh_found = 1; /* Unnumbered */
+ else if (IPV4_ADDR_SAME (&oi->address->u.prefix4,
+ &l->link_data))
+ nh_found = 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 */
+ nh_found = 1;
+ nexthop = l2->link_data;
+ break;
+ }
+ }
+
+ if (nh_found)
{
/* 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",
+ __func__);
} /* end point-to-point link from V to W */
else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
{
@@ -633,19 +638,22 @@ 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)
+ if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
+ &l->link_data))
{
- nh = vertex_nexthop_new ();
- nh->oi = oi;
- nh->router.s_addr = 0;
- ospf_spf_add_parent (v, w, nh, distance);
- return 1;
- }
+ zlog_info("%s: Interface %s:%s does not match Link Data:%s",
+ __func__, oi->ifp->name,
+ inet_ntop (AF_INET, &oi->address->u.prefix4, buf1,
BUFSIZ),
+ inet_ntop (AF_INET, &l->link_id, buf2, BUFSIZ));
+ return 0;
+ }
+
+ nh = vertex_nexthop_new ();
+ nh->oi = oi;
+ nh->router.s_addr = 0;
+ 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)
@@ -714,7 +722,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. */
@@ -742,7 +750,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
if (v->lsa->type == OSPF_ROUTER_LSA)
{
l = (struct router_lsa_link *) p;
-
+ lsa_pos = lsa_pos_next; /* LSA link position */
+ lsa_pos_next++;
p += (ROUTER_LSA_MIN_SIZE +
(l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
@@ -864,7 +873,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");
@@ -884,7 +893,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 +903,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
>From a33c98b1bb7c54e97b10e239c2134f184ea93d56 Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund <joakim.tjernl...@transmode.se>
Date: Fri, 7 Aug 2009 20:57:51 +0200
Subject: [PATCH] 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 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_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 *ifp,
struct prefix *p)
}
else
return oi;
-
+
+ ospf_lsa_pos_set(-1,-1, oi); /* delete position in router LSA */
+
/* Set zebra interface pointer. */
oi->ifp = ifp;
oi->address = 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 >= 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 = pos_beg;
+ oi->lsa_pos_end = 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, >= */
+ 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_area *,
+ int);
+extern void ospf_lsa_pos_set(int, int, struct ospf_interface *);
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 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 = 0;
+ int links = 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 != ISM_Down)
{
+ old_links = 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);
}
+ 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 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)
{
@@ -505,30 +507,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)
@@ -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 = 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)
{
@@ -633,19 +628,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)
@@ -714,7 +703,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. */
@@ -742,7 +731,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
if (v->lsa->type == OSPF_ROUTER_LSA)
{
l = (struct router_lsa_link *) p;
-
+ lsa_pos = lsa_pos_next; /* LSA link position */
+ lsa_pos_next++;
p += (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 = 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");
@@ -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
