Merge pull request #219 from opensourcerouting/feature/isis-draft-ietf-rtgwg-backoff-algo

Add support for draft-ietf-rtgwg-backoff-algo to IS-IS

9 files changed, 606 insertions, 136 deletions

diff --git a/isisd/isis_lsp.c b/isisd/isis_lsp.c
index fac62f6e1b..f633a8fb78 100644
--- a/isisd/isis_lsp.c
+++ b/isisd/isis_lsp.c
@@ -156,7 +156,6 @@ lsp_destroy (struct isis_lsp *lsp)
     }
 
   isis_spf_schedule (lsp->area, lsp->level);
-  isis_spf_schedule6 (lsp->area, lsp->level);
 
   if (lsp->pdu)
     stream_free (lsp->pdu);
@@ -425,7 +424,6 @@ lsp_inc_seqnum (struct isis_lsp *lsp, u_int32_t seq_num)
                     ntohs (lsp->lsp_header->pdu_len) - 12, 12);
 
   isis_spf_schedule (lsp->area, lsp->level);
-  isis_spf_schedule6 (lsp->area, lsp->level);
 
   return;
 }
@@ -640,7 +638,6 @@ lsp_insert (struct isis_lsp *lsp, dict_t * lspdb)
   if (lsp->lsp_header->seq_num != 0)
     {
       isis_spf_schedule (lsp->area, lsp->level);
-      isis_spf_schedule6 (lsp->area, lsp->level);
     }
 }
 
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index c1fb062e55..db46078f20 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -33,6 +33,7 @@
 #include "hash.h"
 #include "if.h"
 #include "table.h"
+#include "spf_backoff.h"
 
 #include "isis_constants.h"
 #include "isis_common.h"
@@ -50,9 +51,6 @@
 #include "isis_route.h"
 #include "isis_csm.h"
 
-int isis_run_spf_l1 (struct thread *thread);
-int isis_run_spf_l2 (struct thread *thread);
-
 /* 7.2.7 */
 static void
 remove_excess_adjs (struct list *adjs)
@@ -266,14 +264,12 @@ isis_spftree_new (struct isis_area *area)
   tree->last_run_timestamp = 0;
   tree->last_run_duration = 0;
   tree->runcount = 0;
-  tree->pending = 0;
   return tree;
 }
 
 void
 isis_spftree_del (struct isis_spftree *spftree)
 {
-  THREAD_TIMER_OFF (spftree->t_spf);
 
   spftree->tents->del = (void (*)(void *)) isis_vertex_del;
   list_delete (spftree->tents);
@@ -1240,7 +1236,6 @@ isis_run_spf (struct isis_area *area, int level, int family, u_char *sysid)
 
 out:
   isis_route_validate (area);
-  spftree->pending = 0;
   spftree->runcount++;
   spftree->last_run_timestamp = time (NULL);
   monotime(&time_now);
@@ -1248,11 +1243,10 @@ out:
   end_time = (end_time * 1000000) + time_now.tv_usec;
   spftree->last_run_duration = end_time - start_time;
 
-
   return retval;
 }
 
-int
+static int
 isis_run_spf_l1 (struct thread *thread)
 {
   struct isis_area *area;
@@ -1261,8 +1255,7 @@ isis_run_spf_l1 (struct thread *thread)
   area = THREAD_ARG (thread);
   assert (area);
 
-  area->spftree[0]->t_spf = NULL;
-  area->spftree[0]->pending = 0;
+  area->spf_timer[0] = NULL;
 
   if (!(area->is_type & IS_LEVEL_1))
     {
@@ -1277,11 +1270,13 @@ isis_run_spf_l1 (struct thread *thread)
 
   if (area->ip_circuits)
     retval = isis_run_spf (area, 1, AF_INET, isis->sysid);
+  if (area->ipv6_circuits)
+    retval = isis_run_spf (area, 1, AF_INET6, isis->sysid);
 
   return retval;
 }
 
-int
+static int
 isis_run_spf_l2 (struct thread *thread)
 {
   struct isis_area *area;
@@ -1290,8 +1285,7 @@ isis_run_spf_l2 (struct thread *thread)
   area = THREAD_ARG (thread);
   assert (area);
 
-  area->spftree[1]->t_spf = NULL;
-  area->spftree[1]->pending = 0;
+  area->spf_timer[1] = NULL;
 
   if (!(area->is_type & IS_LEVEL_2))
     {
@@ -1305,6 +1299,8 @@ isis_run_spf_l2 (struct thread *thread)
 
   if (area->ip_circuits)
     retval = isis_run_spf (area, 2, AF_INET, isis->sysid);
+  if (area->ipv6_circuits)
+    retval = isis_run_spf (area, 2, AF_INET6, isis->sysid);
 
   return retval;
 }
@@ -1323,126 +1319,55 @@ isis_spf_schedule (struct isis_area *area, int level)
     zlog_debug ("ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
                 area->area_tag, level, diff);
 
-  if (spftree->pending)
-    return ISIS_OK;
-
-  THREAD_TIMER_OFF (spftree->t_spf);
-
-  /* wait configured min_spf_interval before doing the SPF */
-  if (diff >= area->min_spf_interval[level-1])
-      return isis_run_spf (area, level, AF_INET, isis->sysid);
-
-  if (level == 1)
-    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
-                     area->min_spf_interval[0] - diff);
-  else
-    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
-                     area->min_spf_interval[1] - diff);
-
-  if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
-                area->area_tag, level, area->min_spf_interval[level-1] - diff);
-
-  spftree->pending = 1;
-
-  return ISIS_OK;
-}
-
-static int
-isis_run_spf6_l1 (struct thread *thread)
-{
-  struct isis_area *area;
-  int retval = ISIS_OK;
-
-  area = THREAD_ARG (thread);
-  assert (area);
-
-  area->spftree6[0]->t_spf = NULL;
-  area->spftree6[0]->pending = 0;
-
-  if (!(area->is_type & IS_LEVEL_1))
+  if (area->spf_delay_ietf[level - 1])
     {
-      if (isis->debugs & DEBUG_SPF_EVENTS)
-        zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
-      return ISIS_WARNING;
-    }
-
-  if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
-
-  if (area->ipv6_circuits)
-    retval = isis_run_spf (area, 1, AF_INET6, isis->sysid);
+      /* Need to call schedule function also if spf delay is running to
+       * restart holdoff timer - compare draft-ietf-rtgwg-backoff-algo-04 */
+      long delay = spf_backoff_schedule(area->spf_delay_ietf[level -1]);
+      if (area->spf_timer[level - 1])
+        return ISIS_OK;
 
-  return retval;
-}
-
-static int
-isis_run_spf6_l2 (struct thread *thread)
-{
-  struct isis_area *area;
-  int retval = ISIS_OK;
-
-  area = THREAD_ARG (thread);
-  assert (area);
-
-  area->spftree6[1]->t_spf = NULL;
-  area->spftree6[1]->pending = 0;
-
-  if (!(area->is_type & IS_LEVEL_2))
-    {
-      if (isis->debugs & DEBUG_SPF_EVENTS)
-        zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
-      return ISIS_WARNING;
+      if (level == 1)
+        {
+          THREAD_TIMER_MSEC_ON(master, area->spf_timer[0],
+                               isis_run_spf_l1, area, delay);
+        }
+      else
+        {
+          THREAD_TIMER_MSEC_ON(master, area->spf_timer[1],
+                               isis_run_spf_l2, area, delay);
+        }
+      return ISIS_OK;
     }
 
-  if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area->area_tag);
-
-  if (area->ipv6_circuits)
-    retval = isis_run_spf (area, 2, AF_INET6, isis->sysid);
-
-  return retval;
-}
-
-int
-isis_spf_schedule6 (struct isis_area *area, int level)
-{
-  int retval = ISIS_OK;
-  struct isis_spftree *spftree = area->spftree6[level - 1];
-  time_t now = time (NULL);
-  time_t diff = now - spftree->last_run_timestamp;
-
-  assert (diff >= 0);
-  assert (area->is_type & level);
-
-  if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L%d SPF schedule called, lastrun %lld sec ago",
-                area->area_tag, level, (long long)diff);
-
-  if (spftree->pending)
+  if (area->spf_timer[level -1])
     return ISIS_OK;
 
-  THREAD_TIMER_OFF (spftree->t_spf);
-
   /* wait configured min_spf_interval before doing the SPF */
   if (diff >= area->min_spf_interval[level-1])
-      return isis_run_spf (area, level, AF_INET6, isis->sysid);
+    {
+      int retval = ISIS_OK;
+
+      if (area->ip_circuits)
+        retval = isis_run_spf (area, level, AF_INET, isis->sysid);
+      if (area->ipv6_circuits)
+        retval = isis_run_spf (area, level, AF_INET6, isis->sysid);
+
+      return retval;
+    }
 
   if (level == 1)
-    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
+    THREAD_TIMER_ON (master, area->spf_timer[0], isis_run_spf_l1, area,
                      area->min_spf_interval[0] - diff);
   else
-    THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
+    THREAD_TIMER_ON (master, area->spf_timer[1], isis_run_spf_l2, area,
                      area->min_spf_interval[1] - diff);
 
   if (isis->debugs & DEBUG_SPF_EVENTS)
-    zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %lld sec from now",
-                area->area_tag, level,
-		(long long)(area->min_spf_interval[level-1] - diff));
-
-  spftree->pending = 1;
+    zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
+                area->area_tag, level, area->min_spf_interval[level-1] - diff);
 
-  return retval;
+  return ISIS_OK;
 }
 
 static void
diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h
index 0e42cac81f..fb534542d0 100644
--- a/isisd/isis_spf.h
+++ b/isisd/isis_spf.h
@@ -60,11 +60,9 @@ struct isis_vertex
 
 struct isis_spftree
 {
-  struct thread *t_spf;		/* spf threads */
   struct list *paths;		/* the SPT */
   struct list *tents;		/* TENT */
   struct isis_area *area;       /* back pointer to area */
-  int pending;			/* already scheduled */
   unsigned int runcount;        /* number of runs since uptime */
   time_t last_run_timestamp;    /* last run timestamp for scheduling */
   time_t last_run_duration;     /* last run duration in msec */
@@ -80,5 +78,4 @@ void spftree_area_adj_del (struct isis_area *area,
                            struct isis_adjacency *adj);
 int isis_spf_schedule (struct isis_area *area, int level);
 void isis_spf_cmds_init (void);
-int isis_spf_schedule6 (struct isis_area *area, int level);
 #endif /* _ZEBRA_ISIS_SPF_H */
diff --git a/isisd/isis_vty.c b/isisd/isis_vty.c
index 848c56a6ac..721959859a 100644
--- a/isisd/isis_vty.c
+++ b/isisd/isis_vty.c
@@ -22,7 +22,9 @@
  */
 
 #include <zebra.h>
-#include <command.h>
+
+#include "command.h"
+#include "spf_backoff.h"
 
 #include "isis_circuit.h"
 #include "isis_csm.h"
@@ -1707,6 +1709,63 @@ DEFUN (no_spf_interval_l2,
   return CMD_SUCCESS;
 }
 
+DEFUN (no_spf_delay_ietf,
+       no_spf_delay_ietf_cmd,
+       "no spf-delay-ietf",
+       NO_STR
+       "IETF SPF delay algorithm\n")
+{
+  VTY_DECLVAR_CONTEXT (isis_area, area);
+
+  spf_backoff_free(area->spf_delay_ietf[0]);
+  spf_backoff_free(area->spf_delay_ietf[1]);
+  area->spf_delay_ietf[0] = NULL;
+  area->spf_delay_ietf[1] = NULL;
+
+  return CMD_SUCCESS;
+}
+
+DEFUN (spf_delay_ietf,
+       spf_delay_ietf_cmd,
+       "spf-delay-ietf init-delay (0-60000) short-delay (0-60000) long-delay (0-60000) holddown (0-60000) time-to-learn (0-60000)",
+       "IETF SPF delay algorithm\n"
+       "Delay used while in QUIET state\n"
+       "Delay used while in QUIET state in milliseconds\n"
+       "Delay used while in SHORT_WAIT state\n"
+       "Delay used while in SHORT_WAIT state in milliseconds\n"
+       "Delay used while in LONG_WAIT\n"
+       "Delay used while in LONG_WAIT state in milliseconds\n"
+       "Time with no received IGP events before considering IGP stable\n"
+       "Time with no received IGP events before considering IGP stable (in milliseconds)\n"
+       "Maximum duration needed to learn all the events related to a single failure\n"
+       "Maximum duration needed to learn all the events related to a single failure (in milliseconds)\n")
+{
+  VTY_DECLVAR_CONTEXT (isis_area, area);
+
+  long init_delay = atol(argv[2]->arg);
+  long short_delay = atol(argv[4]->arg);
+  long long_delay = atol(argv[6]->arg);
+  long holddown = atol(argv[8]->arg);
+  long timetolearn = atol(argv[10]->arg);
+
+  size_t bufsiz = strlen(area->area_tag) + sizeof("IS-IS  Lx");
+  char *buf = XCALLOC(MTYPE_TMP, bufsiz);
+
+  snprintf(buf, bufsiz, "IS-IS %s L1", area->area_tag);
+  spf_backoff_free(area->spf_delay_ietf[0]);
+  area->spf_delay_ietf[0] = spf_backoff_new(master, buf, init_delay,
+                                            short_delay, long_delay,
+                                            holddown, timetolearn);
+
+  snprintf(buf, bufsiz, "IS-IS %s L2", area->area_tag);
+  spf_backoff_free(area->spf_delay_ietf[1]);
+  area->spf_delay_ietf[1] = spf_backoff_new(master, buf, init_delay,
+                                            short_delay, long_delay,
+                                            holddown, timetolearn);
+
+  XFREE(MTYPE_TMP, buf);
+  return CMD_SUCCESS;
+}
 
 static int
 area_max_lsp_lifetime_set(struct vty *vty, int level,
@@ -2096,4 +2155,8 @@ isis_vty_init (void)
   install_element (ISIS_NODE, &domain_passwd_md5_cmd);
   install_element (ISIS_NODE, &domain_passwd_clear_cmd);
   install_element (ISIS_NODE, &no_area_passwd_cmd);
+
+  install_element (ISIS_NODE, &spf_delay_ietf_cmd);
+  install_element (ISIS_NODE, &no_spf_delay_ietf_cmd);
+
 }
diff --git a/isisd/isisd.c b/isisd/isisd.c
index 9bef250883..2863d2f678 100644
--- a/isisd/isisd.c
+++ b/isisd/isisd.c
@@ -35,6 +35,7 @@
 #include "prefix.h"
 #include "table.h"
 #include "qobj.h"
+#include "spf_backoff.h"
 
 #include "isisd/dict.h"
 #include "isisd/isis_constants.h"
@@ -245,6 +246,12 @@ isis_area_destroy (struct vty *vty, const char *area_tag)
 
   spftree_area_del (area);
 
+  THREAD_TIMER_OFF(area->spf_timer[0]);
+  THREAD_TIMER_OFF(area->spf_timer[1]);
+
+  spf_backoff_free(area->spf_delay_ietf[0]);
+  spf_backoff_free(area->spf_delay_ietf[1]);
+
   /* invalidate and validate would delete all routes from zebra */
   isis_route_invalidate (area);
   isis_route_validate (area);
@@ -856,6 +863,7 @@ config_write_debug (struct vty *vty)
       vty_out (vty, "debug isis lsp-sched%s", VTY_NEWLINE);
       write++;
     }
+  write += spf_backoff_write_config(vty);
 
   return write;
 }
@@ -1273,6 +1281,57 @@ vty_out_timestr(struct vty *vty, time_t uptime)
   vty_out (vty, " ago");
 }
 
+DEFUN (show_isis_spf_ietf,
+       show_isis_spf_ietf_cmd,
+       "show isis spf-delay-ietf",
+       SHOW_STR
+       "IS-IS information\n"
+       "IS-IS SPF delay IETF information\n")
+{
+  if (!isis)
+    {
+      vty_out (vty, "ISIS is not running%s", VTY_NEWLINE);
+      return CMD_SUCCESS;
+    }
+
+  struct listnode *node;
+  struct isis_area *area;
+
+  for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area))
+    {
+      vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
+               VTY_NEWLINE);
+
+      for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++)
+        {
+          if ((area->is_type & level) == 0)
+            continue;
+
+          vty_out (vty, "  Level-%d:%s", level, VTY_NEWLINE);
+          vty_out (vty, "    SPF delay status: ");
+          if (area->spf_timer[level -1])
+            {
+              struct timeval remain = thread_timer_remain(area->spf_timer[level - 1]);
+              vty_out(vty, "Pending, due in %ld msec%s",
+                      remain.tv_sec * 1000 + remain.tv_usec / 1000,
+                      VTY_NEWLINE);
+            }
+          else
+            {
+              vty_out(vty, "Not scheduled%s", VTY_NEWLINE);
+            }
+
+          if (area->spf_delay_ietf[level - 1]) {
+            vty_out(vty,  "    Using draft-ietf-rtgwg-backoff-algo-04%s", VTY_NEWLINE);
+            spf_backoff_show(area->spf_delay_ietf[level - 1], vty, "    ");
+          } else {
+            vty_out(vty,  "    Using legacy backoff algo%s", VTY_NEWLINE);
+          }
+        }
+    }
+  return CMD_SUCCESS;
+}
+
 DEFUN (show_isis_summary,
        show_isis_summary_cmd,
        "show isis summary",
@@ -1327,14 +1386,18 @@ DEFUN (show_isis_summary,
 
       vty_out (vty, "  Level-%d:%s", level, VTY_NEWLINE);
       spftree = area->spftree[level - 1];
-      if (spftree->pending)
-        vty_out (vty, "    IPv4 SPF: (pending)%s", VTY_NEWLINE);
+      if (area->spf_timer[level - 1])
+        vty_out (vty, "    SPF: (pending)%s", VTY_NEWLINE);
       else
-        vty_out (vty, "    IPv4 SPF:%s", VTY_NEWLINE);
+        vty_out (vty, "    SPF:%s", VTY_NEWLINE);
 
-      vty_out (vty, "      minimum interval  : %d%s",
-          area->min_spf_interval[level - 1], VTY_NEWLINE);
+      vty_out (vty, "      minimum interval  : %d",
+          area->min_spf_interval[level - 1]);
+      if (area->spf_delay_ietf[level - 1])
+         vty_out (vty, " (not used, IETF SPF delay activated)");
+      vty_out (vty, VTY_NEWLINE);
 
+      vty_out (vty, "    IPv4 route computation:%s", VTY_NEWLINE);
       vty_out (vty, "      last run elapsed  : ");
       vty_out_timestr(vty, spftree->last_run_timestamp);
       vty_out (vty, "%s", VTY_NEWLINE);
@@ -1346,13 +1409,7 @@ DEFUN (show_isis_summary,
           spftree->runcount, VTY_NEWLINE);
 
       spftree = area->spftree6[level - 1];
-      if (spftree->pending)
-        vty_out (vty, "    IPv6 SPF: (pending)%s", VTY_NEWLINE);
-      else
-        vty_out (vty, "    IPv6 SPF:%s", VTY_NEWLINE);
-
-      vty_out (vty, "      minimum interval  : %d%s",
-          area->min_spf_interval[level - 1], VTY_NEWLINE);
+      vty_out (vty, "    IPv6 route computation:%s", VTY_NEWLINE);
 
       vty_out (vty, "      last run elapsed  : ");
       vty_out_timestr(vty, spftree->last_run_timestamp);
@@ -1651,6 +1708,7 @@ area_resign_level (struct isis_area *area, int level)
       isis_spftree_del (area->spftree6[level - 1]);
       area->spftree6[level - 1] = NULL;
     }
+  THREAD_TIMER_OFF(area->spf_timer[level - 1]);
   if (area->route_table[level - 1])
     {
       route_table_finish (area->route_table[level - 1]);
@@ -2010,6 +2068,20 @@ isis_config_write (struct vty *vty)
 		write++;
 	      }
 	  }
+
+	/* IETF SPF interval */
+	if (area->spf_delay_ietf[0])
+	  {
+	    vty_out (vty, " spf-delay-ietf init-delay %ld short-delay %ld long-delay %ld holddown %ld time-to-learn %ld%s",
+	             spf_backoff_init_delay(area->spf_delay_ietf[0]),
+	             spf_backoff_short_delay(area->spf_delay_ietf[0]),
+	             spf_backoff_long_delay(area->spf_delay_ietf[0]),
+	             spf_backoff_holddown(area->spf_delay_ietf[0]),
+	             spf_backoff_timetolearn(area->spf_delay_ietf[0]),
+	             VTY_NEWLINE);
+	    write++;
+	  }
+
 	/* Authentication passwords. */
 	if (area->area_passwd.type == ISIS_PASSWD_TYPE_HMAC_MD5)
 	  {
@@ -2097,6 +2169,8 @@ isis_init ()
 
   install_element (VIEW_NODE, &show_isis_summary_cmd);
 
+  install_element (VIEW_NODE, &show_isis_spf_ietf_cmd);
+
   install_element (VIEW_NODE, &show_isis_interface_cmd);
   install_element (VIEW_NODE, &show_isis_interface_detail_cmd);
   install_element (VIEW_NODE, &show_isis_interface_arg_cmd);
@@ -2182,4 +2256,6 @@ isis_init ()
 
   install_element (ISIS_NODE, &log_adj_changes_cmd);
   install_element (ISIS_NODE, &no_log_adj_changes_cmd);
+
+  spf_backoff_cmd_init();
 }
diff --git a/isisd/isisd.h b/isisd/isisd.h
index efbfafc5fb..e1d3a69f8d 100644
--- a/isisd/isisd.h
+++ b/isisd/isisd.h
@@ -127,6 +127,9 @@ struct isis_area
                                     [ZEBRA_ROUTE_MAX + 1][ISIS_LEVELS];
   struct route_table *ext_reach[REDIST_PROTOCOL_COUNT][ISIS_LEVELS];
 
+  struct spf_backoff *spf_delay_ietf[ISIS_LEVELS]; /*Structure with IETF SPF algo parameters*/
+  struct thread *spf_timer[ISIS_LEVELS];
+
   QOBJ_FIELDS
 };
 DECLARE_QOBJ_TYPE(isis_area)
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 780d4bc1b8..a9fe646938 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -28,6 +28,7 @@ libfrr_la_SOURCES = \
 	event_counter.c \
 	grammar_sandbox.c \
 	srcdest_table.c \
+	spf_backoff.c \
 	strlcpy.c \
 	strlcat.c
 
@@ -50,6 +51,7 @@ pkginclude_HEADERS = \
 	skiplist.h qobj.h wheel.h \
 	event_counter.h \
 	monotime.h \
+	spf_backoff.h \
 	srcdest_table.h
 
 noinst_HEADERS = \
diff --git a/lib/spf_backoff.c b/lib/spf_backoff.c
new file mode 100644
index 0000000000..e923f232b8
--- /dev/null
+++ b/lib/spf_backoff.c
@@ -0,0 +1,341 @@
+/*
+ * This is an implementation of the IETF SPF delay algorithm
+ * as explained in draft-ietf-rtgwg-backoff-algo-04
+ *
+ * Created: 25-01-2017 by S. Litkowski
+ *
+ * Copyright (C) 2017 Orange Labs http://www.orange.com/
+ * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
+ *
+ * This file is part of FreeRangeRouting (FRR)
+ *
+ * FRR is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * FRR is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with FRR; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#include <zebra.h>
+
+#include "spf_backoff.h"
+
+#include "command.h"
+#include "memory.h"
+#include "thread.h"
+#include "vty.h"
+
+DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff")
+DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name")
+
+static bool debug_spf_backoff = false;
+#define backoff_debug(...) \
+  do \
+    { \
+      if (debug_spf_backoff) \
+        zlog_debug(__VA_ARGS__); \
+    } \
+  while (0)
+
+enum spf_backoff_state {
+  SPF_BACKOFF_QUIET,
+  SPF_BACKOFF_SHORT_WAIT,
+  SPF_BACKOFF_LONG_WAIT
+};
+
+struct spf_backoff {
+  struct thread_master *m;
+
+  /* Timers as per draft */
+  long init_delay;
+  long short_delay;
+  long long_delay;
+  long holddown;
+  long timetolearn;
+
+  /* State machine */
+  enum spf_backoff_state state;
+  struct thread *t_holddown;
+  struct thread *t_timetolearn;
+
+  /* For debugging */
+  char *name;
+  struct timeval first_event_time;
+  struct timeval last_event_time;
+};
+
+static const char *
+spf_backoff_state2str(enum spf_backoff_state state)
+{
+  switch (state)
+    {
+    case SPF_BACKOFF_QUIET:
+      return "QUIET";
+    case SPF_BACKOFF_SHORT_WAIT:
+      return "SHORT_WAIT";
+    case SPF_BACKOFF_LONG_WAIT:
+      return "LONG_WAIT";
+    }
+  return "???";
+}
+
+struct spf_backoff *
+spf_backoff_new(struct thread_master *m,
+                const char *name,
+                long init_delay,
+                long short_delay,
+                long long_delay,
+                long holddown,
+                long timetolearn)
+{
+  struct spf_backoff *rv;
+
+  rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
+  rv->m = m;
+
+  rv->init_delay = init_delay;
+  rv->short_delay = short_delay;
+  rv->long_delay = long_delay;
+  rv->holddown = holddown;
+  rv->timetolearn = timetolearn;
+
+  rv->state = SPF_BACKOFF_QUIET;
+
+  rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
+  return rv;
+}
+
+void
+spf_backoff_free(struct spf_backoff *backoff)
+{
+  if (!backoff)
+    return;
+
+  THREAD_TIMER_OFF(backoff->t_holddown);
+  THREAD_TIMER_OFF(backoff->t_timetolearn);
+  XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
+
+  XFREE(MTYPE_SPF_BACKOFF, backoff);
+}
+
+static int
+spf_backoff_timetolearn_elapsed(struct thread *thread)
+{
+  struct spf_backoff *backoff = THREAD_ARG(thread);
+
+  backoff->t_timetolearn = NULL;
+  backoff->state = SPF_BACKOFF_LONG_WAIT;
+  backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
+                backoff->name, spf_backoff_state2str(backoff->state));
+  return 0;
+}
+
+static int
+spf_backoff_holddown_elapsed(struct thread *thread)
+{
+  struct spf_backoff *backoff = THREAD_ARG(thread);
+
+  backoff->t_holddown = NULL;
+  THREAD_TIMER_OFF(backoff->t_timetolearn);
+  timerclear(&backoff->first_event_time);
+  backoff->state = SPF_BACKOFF_QUIET;
+  backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
+                backoff->name, spf_backoff_state2str(backoff->state));
+  return 0;
+}
+
+long spf_backoff_schedule(struct spf_backoff *backoff)
+{
+  long rv;
+  struct timeval now;
+
+  gettimeofday(&now, NULL);
+
+  backoff_debug("SPF Back-off(%s) schedule called in state %s",
+                backoff->name, spf_backoff_state2str(backoff->state));
+
+  backoff->last_event_time = now;
+
+  switch (backoff->state)
+    {
+    case SPF_BACKOFF_QUIET:
+      backoff->state = SPF_BACKOFF_SHORT_WAIT;
+      THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_timetolearn,
+                           spf_backoff_timetolearn_elapsed, backoff,
+                           backoff->timetolearn);
+      THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown,
+                           spf_backoff_holddown_elapsed, backoff,
+                           backoff->holddown);
+      backoff->first_event_time = now;
+      rv = backoff->init_delay;
+      break;
+    case SPF_BACKOFF_SHORT_WAIT:
+    case SPF_BACKOFF_LONG_WAIT:
+      THREAD_TIMER_OFF(backoff->t_holddown);
+      THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown,
+                           spf_backoff_holddown_elapsed, backoff,
+                           backoff->holddown);
+      if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
+        rv = backoff->short_delay;
+      else
+        rv = backoff->long_delay;
+      break;
+    default:
+      zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
+      rv = backoff->init_delay;
+    }
+
+  backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay",
+                backoff->name, spf_backoff_state2str(backoff->state), rv);
+  return rv;
+}
+
+static const char *
+timeval_format(struct timeval *tv)
+{
+  struct tm tm_store;
+  struct tm *tm;
+  static char timebuf[256];
+
+  if (!tv->tv_sec && !tv->tv_usec)
+    return "(never)";
+
+  tm = localtime_r(&tv->tv_sec, &tm_store);
+  if (!tm || strftime(timebuf, sizeof(timebuf),
+                      "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0)
+    {
+      return "???";
+    }
+
+  size_t offset = strlen(timebuf);
+  snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec);
+
+  return timebuf;
+}
+
+void
+spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
+                 const char *prefix)
+{
+  vty_out(vty, "%sCurrent state:     %s%s", prefix,
+          spf_backoff_state2str(backoff->state), VTY_NEWLINE);
+  vty_out(vty, "%sInit timer:        %ld msec%s", prefix,
+          backoff->init_delay, VTY_NEWLINE);
+  vty_out(vty, "%sShort timer:       %ld msec%s", prefix,
+          backoff->short_delay, VTY_NEWLINE);
+  vty_out(vty, "%sLong timer:        %ld msec%s", prefix,
+          backoff->long_delay, VTY_NEWLINE);
+  vty_out(vty, "%sHolddown timer:    %ld msec%s", prefix,
+          backoff->holddown, VTY_NEWLINE);
+  if (backoff->t_holddown)
+    {
+      struct timeval remain = thread_timer_remain(backoff->t_holddown);
+      vty_out(vty, "%s                   Still runs for %ld msec%s",
+              prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
+    }
+  else
+    {
+      vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
+    }
+
+  vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix,
+          backoff->timetolearn, VTY_NEWLINE);
+  if (backoff->t_timetolearn)
+    {
+      struct timeval remain = thread_timer_remain(backoff->t_timetolearn);
+      vty_out(vty, "%s                   Still runs for %ld msec%s",
+              prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
+    }
+  else
+    {
+      vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
+    }
+
+  vty_out(vty, "%sFirst event:       %s%s", prefix,
+          timeval_format(&backoff->first_event_time), VTY_NEWLINE);
+  vty_out(vty, "%sLast event:        %s%s", prefix,
+          timeval_format(&backoff->last_event_time), VTY_NEWLINE);
+}
+
+DEFUN(spf_backoff_debug,
+      spf_backoff_debug_cmd,
+      "debug spf-delay-ietf",
+      DEBUG_STR
+      "SPF Back-off Debugging\n")
+{
+  debug_spf_backoff = true;
+  return CMD_SUCCESS;
+}
+
+DEFUN(no_spf_backoff_debug,
+      no_spf_backoff_debug_cmd,
+      "no debug spf-delay-ietf",
+      NO_STR
+      DEBUG_STR
+      "SPF Back-off Debugging\n")
+{
+  debug_spf_backoff = false;
+  return CMD_SUCCESS;
+}
+
+int
+spf_backoff_write_config(struct vty *vty)
+{
+  int written = 0;
+
+  if (debug_spf_backoff)
+    {
+      vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE);
+      written++;
+    }
+
+  return written;
+}
+
+void
+spf_backoff_cmd_init(void)
+{
+  install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
+  install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
+  install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
+  install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
+}
+
+long
+spf_backoff_init_delay(struct spf_backoff *backoff)
+{
+  return backoff->init_delay;
+}
+
+long
+spf_backoff_short_delay(struct spf_backoff *backoff)
+{
+  return backoff->short_delay;
+}
+
+long
+spf_backoff_long_delay(struct spf_backoff *backoff)
+{
+  return backoff->long_delay;
+}
+
+long
+spf_backoff_holddown(struct spf_backoff *backoff)
+{
+  return backoff->holddown;
+}
+
+long
+spf_backoff_timetolearn(struct spf_backoff *backoff)
+{
+  return backoff->timetolearn;
+}
diff --git a/lib/spf_backoff.h b/lib/spf_backoff.h
new file mode 100644
index 0000000000..552ca4ae41
--- /dev/null
+++ b/lib/spf_backoff.h
@@ -0,0 +1,66 @@
+/*
+ * This is an implementation of the IETF SPF delay algorithm
+ * as explained in draft-ietf-rtgwg-backoff-algo-04
+ *
+ * Created: 25-01-2017 by S. Litkowski
+ *
+ * Copyright (C) 2017 Orange Labs http://www.orange.com/
+ * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
+ *
+ * This file is part of FreeRangeRouting (FRR)
+ *
+ * FRR is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * FRR is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with FRR; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+#ifndef _ZEBRA_SPF_BACKOFF_H
+#define _ZEBRA_SPF_BACKOFF_H
+
+struct spf_backoff;
+struct thread_master;
+struct vty;
+
+struct spf_backoff *spf_backoff_new(struct thread_master *m,
+                                    const char *name,
+                                    long init_delay,
+                                    long short_delay,
+                                    long long_delay,
+                                    long holddown,
+                                    long timetolearn);
+
+void spf_backoff_free(struct spf_backoff *backoff);
+
+/* Called whenever an IGP event is received, returns how many
+ * milliseconds routing table computation should be delayed */
+long spf_backoff_schedule(struct spf_backoff *backoff);
+
+/* Shows status of SPF backoff instance */
+void spf_backoff_show(struct spf_backoff *backoff,
+                      struct vty *vty,
+                      const char *prefix);
+
+/* Writes out global SPF backoff debug config */
+int spf_backoff_write_config(struct vty *vty);
+
+/* Registers global SPF backoff debug commands */
+void spf_backoff_cmd_init(void);
+
+/* Accessor functions for SPF backoff parameters */
+long spf_backoff_init_delay(struct spf_backoff *backoff);
+long spf_backoff_short_delay(struct spf_backoff *backoff);
+long spf_backoff_long_delay(struct spf_backoff *backoff);
+long spf_backoff_holddown(struct spf_backoff *backoff);
+long spf_backoff_timetolearn(struct spf_backoff *backoff);
+
+#endif