ospf6d: schedule SPF to run on events rather than directly on each event.
OSPV3 SPF triggers on every SPF-able event instead of using timers the way
OSPFv2 does. This patch makes SPF be triggered/throttled similar to OSPFv2.
It adds a command to quagga identical to the OSPFv2 equivalent to configure
these timers.
Summary:
Signed-off-by: Dinesh Dutt <ddutt at cumulusnetworks.com>
Reviewed-by: Scott Feldman <sfeldma at cumulusnetworks.com>
[DL: removed reference to oa->ts_spf for rebase]
[DL: killed timeval_subtract]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
diff --git a/doc/ospf6d.texi b/doc/ospf6d.texi
index 6667221..c01c051 100644
--- a/doc/ospf6d.texi
+++ b/doc/ospf6d.texi
@@ -28,6 +28,44 @@
be specified as 0.
@end deffn
+@deffn {OSPF6 Command} {timers throttle spf @var{delay} @var{initial-holdtime} @var{max-holdtime}} {}
+@deffnx {OSPF6 Command} {no timers throttle spf} {}
+This command sets the initial @var{delay}, the @var{initial-holdtime}
+and the @var{maximum-holdtime} between when SPF is calculated and the
+event which triggered the calculation. The times are specified in
+milliseconds and must be in the range of 0 to 600000 milliseconds.
+
+The @var{delay} specifies the minimum amount of time to delay SPF
+calculation (hence it affects how long SPF calculation is delayed after
+an event which occurs outside of the holdtime of any previous SPF
+calculation, and also serves as a minimum holdtime).
+
+Consecutive SPF calculations will always be seperated by at least
+'hold-time' milliseconds. The hold-time is adaptive and initially is
+set to the @var{initial-holdtime} configured with the above command.
+Events which occur within the holdtime of the previous SPF calculation
+will cause the holdtime to be increased by @var{initial-holdtime}, bounded
+by the @var{maximum-holdtime} configured with this command. If the adaptive
+hold-time elapses without any SPF-triggering event occuring then
+the current holdtime is reset to the @var{initial-holdtime}.
+
+@example
+@group
+router ospf6
+ timers throttle spf 200 400 10000
+@end group
+@end example
+
+In this example, the @var{delay} is set to 200ms, the @var{initial
+holdtime} is set to 400ms and the @var{maximum holdtime} to 10s. Hence
+there will always be at least 200ms between an event which requires SPF
+calculation and the actual SPF calculation. Further consecutive SPF
+calculations will always be seperated by between 400ms to 10s, the
+hold-time increasing by 400ms each time an SPF-triggering event occurs
+within the hold-time of the previous SPF calculation.
+
+@end deffn
+
@node OSPF6 area
@section OSPF6 area
diff --git a/ospf6d/ospf6_area.c b/ospf6d/ospf6_area.c
index 2d20e62..1e07d85 100644
--- a/ospf6d/ospf6_area.c
+++ b/ospf6d/ospf6_area.c
@@ -67,7 +67,7 @@
zlog_debug ("Schedule SPF Calculation for %s",
OSPF6_AREA (lsa->lsdb->data)->name);
}
- ospf6_spf_schedule (OSPF6_AREA (lsa->lsdb->data));
+ ospf6_spf_schedule (OSPF6_PROCESS(OSPF6_AREA (lsa->lsdb->data)->ospf6));
break;
case OSPF6_LSTYPE_INTRA_PREFIX:
@@ -97,7 +97,7 @@
zlog_debug ("Schedule SPF Calculation for %s",
OSPF6_AREA (lsa->lsdb->data)->name);
}
- ospf6_spf_schedule (OSPF6_AREA (lsa->lsdb->data));
+ ospf6_spf_schedule (OSPF6_PROCESS(OSPF6_AREA (lsa->lsdb->data)->ospf6));
break;
case OSPF6_LSTYPE_INTRA_PREFIX:
diff --git a/ospf6d/ospf6_interface.c b/ospf6d/ospf6_interface.c
index 467479b..7c45fe4 100644
--- a/ospf6d/ospf6_interface.c
+++ b/ospf6d/ospf6_interface.c
@@ -75,12 +75,18 @@
static void
ospf6_interface_lsdb_hook (struct ospf6_lsa *lsa)
{
+ struct ospf6_interface *oi;
+
+ if (lsa == NULL)
+ return;
+
+ oi = lsa->lsdb->data;
switch (ntohs (lsa->header->type))
{
case OSPF6_LSTYPE_LINK:
- if (OSPF6_INTERFACE (lsa->lsdb->data)->state == OSPF6_INTERFACE_DR)
- OSPF6_INTRA_PREFIX_LSA_SCHEDULE_TRANSIT (OSPF6_INTERFACE (lsa->lsdb->data));
- ospf6_spf_schedule (OSPF6_INTERFACE (lsa->lsdb->data)->area);
+ if (oi->state == OSPF6_INTERFACE_DR)
+ OSPF6_INTRA_PREFIX_LSA_SCHEDULE_TRANSIT (oi);
+ ospf6_spf_schedule (oi->area->ospf6);
break;
default:
diff --git a/ospf6d/ospf6_spf.c b/ospf6d/ospf6_spf.c
index da0ee13..e4c424d 100644
--- a/ospf6d/ospf6_spf.c
+++ b/ospf6d/ospf6_spf.c
@@ -506,39 +506,128 @@
ospf6_spf_calculation_thread (struct thread *t)
{
struct ospf6_area *oa;
+ struct ospf6 *ospf6;
struct timeval start, end, runtime;
+ struct listnode *node;
+ struct ospf6_route *route;
- oa = (struct ospf6_area *) THREAD_ARG (t);
- oa->thread_spf_calculation = NULL;
-
- if (IS_OSPF6_DEBUG_SPF (PROCESS))
- zlog_debug ("SPF calculation for Area %s", oa->name);
- if (IS_OSPF6_DEBUG_SPF (DATABASE))
- ospf6_spf_log_database (oa);
+ ospf6 = (struct ospf6 *)THREAD_ARG (t);
+ ospf6->t_spf_calc = NULL;
/* execute SPF calculation */
quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
- ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa);
+
+ for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa))
+ {
+
+ if (oa == ospf6->backbone)
+ continue;
+
+ if (IS_OSPF6_DEBUG_SPF (PROCESS))
+ zlog_debug ("SPF calculation for Area %s", oa->name);
+ if (IS_OSPF6_DEBUG_SPF (DATABASE))
+ ospf6_spf_log_database (oa);
+
+ ospf6_spf_calculation (ospf6->router_id, oa->spf_table, oa);
+ ospf6_intra_route_calculation (oa);
+ ospf6_intra_brouter_calculation (oa);
+ }
+
+ if (ospf6->backbone)
+ {
+ if (IS_OSPF6_DEBUG_SPF (PROCESS))
+ zlog_debug ("SPF calculation for Backbone area %s",
+ ospf6->backbone->name);
+ if (IS_OSPF6_DEBUG_SPF (DATABASE))
+ ospf6_spf_log_database(ospf6->backbone);
+
+ ospf6_spf_calculation(ospf6->router_id, ospf6->backbone->spf_table,
+ ospf6->backbone);
+ ospf6_intra_route_calculation(ospf6->backbone);
+ ospf6_intra_brouter_calculation(ospf6->backbone);
+ }
+
+ /* Redo summaries if required */
+ for (route = ospf6_route_head (ospf6->route_table); route;
+ route = ospf6_route_next (route))
+ ospf6_abr_originate_summary(route);
+
quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
timersub (&end, &start, &runtime);
+ ospf6->ts_spf_duration = runtime;
+
if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
zlog_debug ("SPF runtime: %ld sec %ld usec",
runtime.tv_sec, runtime.tv_usec);
- ospf6_intra_route_calculation (oa);
- ospf6_intra_brouter_calculation (oa);
-
return 0;
}
+/* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
+ set timer for SPF calc. */
void
-ospf6_spf_schedule (struct ospf6_area *oa)
+ospf6_spf_schedule (struct ospf6 *ospf6)
{
- if (oa->thread_spf_calculation)
+ unsigned long delay, elapsed, ht;
+ struct timeval now, result;
+
+ if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
+ zlog_debug ("SPF: calculation timer scheduled");
+
+ /* OSPF instance does not exist. */
+ if (ospf6 == NULL)
return;
- oa->thread_spf_calculation =
- thread_add_event (master, ospf6_spf_calculation_thread, oa, 0);
+
+ /* SPF calculation timer is already scheduled. */
+ if (ospf6->t_spf_calc)
+ {
+ if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
+ zlog_debug ("SPF: calculation timer is already scheduled: %p",
+ ospf6->t_spf_calc);
+ return;
+ }
+
+ /* XXX Monotic timers: we only care about relative time here. */
+ now = recent_relative_time ();
+ timersub (&now, &ospf6->ts_spf, &result);
+
+ elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
+ ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
+
+ if (ht > ospf6->spf_max_holdtime)
+ ht = ospf6->spf_max_holdtime;
+
+ /* Get SPF calculation delay time. */
+ if (elapsed < ht)
+ {
+ /* Got an event within the hold time of last SPF. We need to
+ * increase the hold_multiplier, if it's not already at/past
+ * maximum value, and wasn't already increased..
+ */
+ if (ht < ospf6->spf_max_holdtime)
+ ospf6->spf_hold_multiplier++;
+
+ /* always honour the SPF initial delay */
+ if ( (ht - elapsed) < ospf6->spf_delay)
+ delay = ospf6->spf_delay;
+ else
+ delay = ht - elapsed;
+ }
+ else
+ {
+ /* Event is past required hold-time of last SPF */
+ delay = ospf6->spf_delay;
+ ospf6->spf_hold_multiplier = 1;
+ }
+
+ if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
+ zlog_debug ("SPF: calculation timer delay = %ld", delay);
+
+ zlog_info ("SPF: Scheduled in %ld msec", delay);
+
+ ospf6->t_spf_calc =
+ thread_add_timer_msec (master, ospf6_spf_calculation_thread, ospf6, delay);
}
void
@@ -666,6 +755,59 @@
return CMD_SUCCESS;
}
+static int
+ospf6_timers_spf_set (struct vty *vty, unsigned int delay,
+ unsigned int hold,
+ unsigned int max)
+{
+ struct ospf6 *ospf = vty->index;
+
+ ospf->spf_delay = delay;
+ ospf->spf_holdtime = hold;
+ ospf->spf_max_holdtime = max;
+
+ return CMD_SUCCESS;
+}
+
+DEFUN (ospf6_timers_throttle_spf,
+ ospf6_timers_throttle_spf_cmd,
+ "timers throttle spf <0-600000> <0-600000> <0-600000>",
+ "Adjust routing timers\n"
+ "Throttling adaptive timer\n"
+ "OSPF6 SPF timers\n"
+ "Delay (msec) from first change received till SPF calculation\n"
+ "Initial hold time (msec) between consecutive SPF calculations\n"
+ "Maximum hold time (msec)\n")
+{
+ unsigned int delay, hold, max;
+
+ if (argc != 3)
+ {
+ vty_out (vty, "Insufficient arguments%s", VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+
+ VTY_GET_INTEGER_RANGE ("SPF delay timer", delay, argv[0], 0, 600000);
+ VTY_GET_INTEGER_RANGE ("SPF hold timer", hold, argv[1], 0, 600000);
+ VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max, argv[2], 0, 600000);
+
+ return ospf6_timers_spf_set (vty, delay, hold, max);
+}
+
+DEFUN (no_ospf6_timers_throttle_spf,
+ no_ospf6_timers_throttle_spf_cmd,
+ "no timers throttle spf",
+ NO_STR
+ "Adjust routing timers\n"
+ "Throttling adaptive timer\n"
+ "OSPF6 SPF timers\n")
+{
+ return ospf6_timers_spf_set (vty,
+ OSPF_SPF_DELAY_DEFAULT,
+ OSPF_SPF_HOLDTIME_DEFAULT,
+ OSPF_SPF_MAX_HOLDTIME_DEFAULT);
+}
+
int
config_write_ospf6_debug_spf (struct vty *vty)
{
@@ -679,6 +821,19 @@
}
void
+ospf6_spf_config_write (struct vty *vty)
+{
+
+ if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT ||
+ ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT ||
+ ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
+ vty_out (vty, " timers throttle spf %d %d %d%s",
+ ospf6->spf_delay, ospf6->spf_holdtime,
+ ospf6->spf_max_holdtime, VTY_NEWLINE);
+
+}
+
+void
install_element_ospf6_debug_spf (void)
{
install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
@@ -698,6 +853,6 @@
void
ospf6_spf_init (void)
{
+ install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
+ install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
}
-
-
diff --git a/ospf6d/ospf6_spf.h b/ospf6d/ospf6_spf.h
index c7069c2..6c40424 100644
--- a/ospf6d/ospf6_spf.h
+++ b/ospf6d/ospf6_spf.h
@@ -22,6 +22,8 @@
#ifndef OSPF6_SPF_H
#define OSPF6_SPF_H
+#include "ospf6_top.h"
+
/* Debug option */
extern unsigned char conf_debug_ospf6_spf;
#define OSPF6_DEBUG_SPF_PROCESS 0x01
@@ -81,11 +83,12 @@
extern void ospf6_spf_calculation (u_int32_t router_id,
struct ospf6_route_table *result_table,
struct ospf6_area *oa);
-extern void ospf6_spf_schedule (struct ospf6_area *oa);
+extern void ospf6_spf_schedule (struct ospf6 *ospf);
extern void ospf6_spf_display_subtree (struct vty *vty, const char *prefix,
int rest, struct ospf6_vertex *v);
+extern void ospf6_spf_config_write (struct vty *vty);
extern int config_write_ospf6_debug_spf (struct vty *vty);
extern void install_element_ospf6_debug_spf (void);
extern void ospf6_spf_init (void);
diff --git a/ospf6d/ospf6_top.c b/ospf6d/ospf6_top.c
index df856b4..540ef38 100644
--- a/ospf6d/ospf6_top.c
+++ b/ospf6d/ospf6_top.c
@@ -46,6 +46,7 @@
#include "ospf6_asbr.h"
#include "ospf6_abr.h"
#include "ospf6_intra.h"
+#include "ospf6_spf.h"
#include "ospf6d.h"
/* global ospf6d variable */
@@ -127,6 +128,11 @@
o->lsdb->hook_add = ospf6_top_lsdb_hook_add;
o->lsdb->hook_remove = ospf6_top_lsdb_hook_remove;
+ o->spf_delay = OSPF_SPF_DELAY_DEFAULT;
+ o->spf_holdtime = OSPF_SPF_HOLDTIME_DEFAULT;
+ o->spf_max_holdtime = OSPF_SPF_MAX_HOLDTIME_DEFAULT;
+ o->spf_hold_multiplier = 1;
+
o->route_table = OSPF6_ROUTE_TABLE_CREATE (GLOBAL, ROUTES);
o->route_table->scope = o;
o->route_table->hook_add = ospf6_top_route_hook_add;
@@ -650,6 +656,7 @@
ospf6_redistribute_config_write (vty);
ospf6_area_config_write (vty);
+ ospf6_spf_config_write (vty);
for (ALL_LIST_ELEMENTS_RO (ospf6->area_list, j, oa))
{
diff --git a/ospf6d/ospf6_top.h b/ospf6d/ospf6_top.h
index 4b2d2c3..27eb18c 100644
--- a/ospf6d/ospf6_top.h
+++ b/ospf6d/ospf6_top.h
@@ -38,6 +38,7 @@
/* list of areas */
struct list *area_list;
+ struct ospf6_area *backbone;
/* AS scope link state database */
struct ospf6_lsdb *lsdb;
@@ -59,6 +60,18 @@
u_char flag;
+ /* SPF parameters */
+ unsigned int spf_delay; /* SPF delay time. */
+ unsigned int spf_holdtime; /* SPF hold time. */
+ unsigned int spf_max_holdtime; /* SPF maximum-holdtime */
+ unsigned int spf_hold_multiplier; /* Adaptive multiplier for hold time */
+
+ struct timeval ts_spf; /* SPF calculation time stamp. */
+ struct timeval ts_spf_duration; /* Execution time of last SPF */
+
+ /* Threads */
+ struct thread *t_spf_calc; /* SPF calculation timer. */
+ struct thread *t_ase_calc; /* ASE calculation timer. */
struct thread *maxage_remover;
};