ripngd: add ECMP support

* Each node in the routing table is changed into a list, holding
  the multiple equal-cost paths.

* If one of the multiple entries gets less-preferred (greater
  metric or greater distance), it will be directly deleted instead
  of starting a garbage-collection timer for it.
  The garbage-collection timer is started only when the last entry
  in the list gets INFINITY.

* Some new functions are used to maintain the ECMP list. And hence
  ripng_route_process(), ripng_redistribute_add() and ripng_timeout()
  are significantly simplified.

* ripng_zebra_ipv6_add() and ripng_zebra_ipv6_delete() now can share
  the common code. The common part is moved to ripng_zebra_ipv6_send().

Signed-off-by: Feng Lu <lu.feng@6wind.com>
Reviewed-by: Alain Ritoux <alain.ritoux@6wind.com>
Signed-off-by: Nicolas Dichtel <nicolas.dichtel@6wind.com>
Acked-by: Vincent Jardin <vincent.jardin@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

6 files changed, 459 insertions, 349 deletions

diff --git a/ripngd/ripng_interface.c b/ripngd/ripng_interface.c
index 8717bfb0..35884634 100644
--- a/ripngd/ripng_interface.c
+++ b/ripngd/ripng_interface.c
@@ -163,38 +163,15 @@ ripng_if_down (struct interface *ifp)
   struct route_node *rp;
   struct ripng_info *rinfo;
   struct ripng_interface *ri;
+  struct list *list = NULL;
+  struct listnode *listnode = NULL, *nextnode = NULL;
 
   if (ripng)
-    {
-      for (rp = route_top (ripng->table); rp; rp = route_next (rp))
-	if ((rinfo = rp->info) != NULL)
-	  {
-	    /* Routes got through this interface. */
-	    if (rinfo->ifindex == ifp->ifindex
-		&& rinfo->type == ZEBRA_ROUTE_RIPNG
-		&& rinfo->sub_type == RIPNG_ROUTE_RTE)
-	      {
-		ripng_zebra_ipv6_delete ((struct prefix_ipv6 *) &rp->p,
-					 &rinfo->nexthop,
-					 rinfo->ifindex);
-
-		ripng_redistribute_delete (rinfo->type, rinfo->sub_type,
-					   (struct prefix_ipv6 *)&rp->p,
-					   rinfo->ifindex);
-	      }
-	    else
-	      {
-		/* All redistributed routes got through this interface,
-		 * but the static and system ones are kept. */
-		if ((rinfo->ifindex == ifp->ifindex) &&
-		    (rinfo->type != ZEBRA_ROUTE_STATIC) &&
-		    (rinfo->type != ZEBRA_ROUTE_SYSTEM))
-		  ripng_redistribute_delete (rinfo->type, rinfo->sub_type,
-					     (struct prefix_ipv6 *) &rp->p,
-					     rinfo->ifindex);
-	      }
-	  }
-    }
+    for (rp = route_top (ripng->table); rp; rp = route_next (rp))
+      if ((list = rp->info) != NULL)
+        for (ALL_LIST_ELEMENTS (list, listnode, nextnode, rinfo))
+          if (rinfo->ifindex == ifp->ifindex)
+            ripng_ecmp_delete (rinfo);
 
   ri = ifp->info;
   
diff --git a/ripngd/ripng_route.c b/ripngd/ripng_route.c
index d4bf0262..f26302e8 100644
--- a/ripngd/ripng_route.c
+++ b/ripngd/ripng_route.c
@@ -40,7 +40,7 @@ ripng_aggregate_new ()
   return new;
 }
 
-static void
+void
 ripng_aggregate_free (struct ripng_aggregate *aggregate)
 {
   XFREE (MTYPE_RIPNG_AGGREGATE, aggregate);
@@ -76,6 +76,23 @@ ripng_aggregate_decrement (struct route_node *child, struct ripng_info *rinfo)
       }
 }
 
+/* Aggregate count decrement check for a list. */
+void
+ripng_aggregate_decrement_list (struct route_node *child, struct list *list)
+{
+  struct route_node *np;
+  struct ripng_aggregate *aggregate;
+  struct ripng_info *rinfo = NULL;
+  struct listnode *node = NULL;
+
+  for (np = child; np; np = np->parent)
+    if ((aggregate = np->aggregate) != NULL)
+      aggregate->count -= listcount (list);
+
+  for (ALL_LIST_ELEMENTS_RO (list, node, rinfo))
+    rinfo->suppress--;
+}
+
 /* RIPng routes treatment. */
 int
 ripng_aggregate_add (struct prefix *p)
@@ -85,6 +102,8 @@ ripng_aggregate_add (struct prefix *p)
   struct ripng_info *rinfo;
   struct ripng_aggregate *aggregate;
   struct ripng_aggregate *sub;
+  struct list *list = NULL;
+  struct listnode *node = NULL;
 
   /* Get top node for aggregation. */
   top = route_node_get (ripng->table, p);
@@ -99,11 +118,12 @@ ripng_aggregate_add (struct prefix *p)
   for (rp = route_lock_node (top); rp; rp = route_next_until (rp, top))
     {
       /* Suppress normal route. */
-      if ((rinfo = rp->info) != NULL)
-	{
-	  aggregate->count++;
-	  rinfo->suppress++;
-	}
+      if ((list = rp->info) != NULL)
+        for (ALL_LIST_ELEMENTS_RO (list, node, rinfo))
+          {
+            aggregate->count++;
+            rinfo->suppress++;
+          }
       /* Suppress aggregate route.  This may not need. */
       if (rp != top && (sub = rp->aggregate) != NULL)
 	{
@@ -124,6 +144,8 @@ ripng_aggregate_delete (struct prefix *p)
   struct ripng_info *rinfo;
   struct ripng_aggregate *aggregate;
   struct ripng_aggregate *sub;
+  struct list *list = NULL;
+  struct listnode *node = NULL;
 
   /* Get top node for aggregation. */
   top = route_node_get (ripng->table, p);
@@ -135,11 +157,12 @@ ripng_aggregate_delete (struct prefix *p)
   for (rp = route_lock_node (top); rp; rp = route_next_until (rp, top))
     {
       /* Suppress normal route. */
-      if ((rinfo = rp->info) != NULL)
-	{
-	  aggregate->count--;
-	  rinfo->suppress--;
-	}
+      if ((list = rp->info) != NULL)
+        for (ALL_LIST_ELEMENTS_RO (list, node, rinfo))
+          {
+            aggregate->count--;
+            rinfo->suppress--;
+          }
 
       if (rp != top && (sub = rp->aggregate) != NULL)
 	{
diff --git a/ripngd/ripng_route.h b/ripngd/ripng_route.h
index 2f5b7575..fe65c883 100644
--- a/ripngd/ripng_route.h
+++ b/ripngd/ripng_route.h
@@ -48,7 +48,10 @@ extern void ripng_aggregate_increment (struct route_node *rp,
                                        struct ripng_info *rinfo);
 extern void ripng_aggregate_decrement (struct route_node *rp,
                                        struct ripng_info *rinfo);
+extern void ripng_aggregate_decrement_list (struct route_node *rp,
+                                       struct list *list);
 extern int ripng_aggregate_add (struct prefix *p);
 extern int ripng_aggregate_delete (struct prefix *p);
+extern void ripng_aggregate_free (struct ripng_aggregate *aggregate);
 
 #endif /* _ZEBRA_RIPNG_ROUTE_H */
diff --git a/ripngd/ripng_zebra.c b/ripngd/ripng_zebra.c
index 68f37be3..b5cf445d 100644
--- a/ripngd/ripng_zebra.c
+++ b/ripngd/ripng_zebra.c
@@ -24,12 +24,15 @@
 
 #include "command.h"
 #include "prefix.h"
+#include "table.h"
 #include "stream.h"
+#include "memory.h"
 #include "routemap.h"
 #include "zclient.h"
 #include "log.h"
 
 #include "ripngd/ripngd.h"
+#include "ripngd/ripng_debug.h"
 
 /* All information about zebra. */
 struct zclient *zclient = NULL;
@@ -42,11 +45,19 @@ int ripng_interface_delete (int, struct zclient *, zebra_size_t);
 int ripng_interface_address_add (int, struct zclient *, zebra_size_t);
 int ripng_interface_address_delete (int, struct zclient *, zebra_size_t);
 
-void
-ripng_zebra_ipv6_add (struct prefix_ipv6 *p, struct in6_addr *nexthop,
-		      unsigned int ifindex, u_char metric)
+/* Send ECMP routes to zebra. */
+static void
+ripng_zebra_ipv6_send (struct route_node *rp, u_char cmd)
 {
+  static struct in6_addr **nexthops = NULL;
+  static unsigned int *ifindexes = NULL;
+  static unsigned int nexthops_len = 0;
+
+  struct list *list = (struct list *)rp->info;
   struct zapi_ipv6 api;
+  struct listnode *listnode = NULL;
+  struct ripng_info *rinfo = NULL;
+  int count = 0;
 
   if (zclient->redist[ZEBRA_ROUTE_RIPNG])
     {
@@ -54,40 +65,62 @@ ripng_zebra_ipv6_add (struct prefix_ipv6 *p, struct in6_addr *nexthop,
       api.flags = 0;
       api.message = 0;
       api.safi = SAFI_UNICAST;
+
+      if (nexthops_len < listcount (list))
+        {
+          nexthops_len = listcount (list);
+          nexthops = XREALLOC (MTYPE_TMP, nexthops,
+                               nexthops_len * sizeof (struct in6_addr *));
+          ifindexes = XREALLOC (MTYPE_TMP, ifindexes,
+                                nexthops_len * sizeof (unsigned int));
+        }
+
       SET_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP);
-      api.nexthop_num = 1;
-      api.nexthop = &nexthop;
       SET_FLAG (api.message, ZAPI_MESSAGE_IFINDEX);
-      api.ifindex_num = 1;
-      api.ifindex = &ifindex;
+      for (ALL_LIST_ELEMENTS_RO (list, listnode, rinfo))
+        {
+          nexthops[count] = &rinfo->nexthop;
+          ifindexes[count] = rinfo->ifindex;
+          count++;
+          if (cmd == ZEBRA_IPV6_ROUTE_ADD)
+            SET_FLAG (rinfo->flags, RIPNG_RTF_FIB);
+          else
+            UNSET_FLAG (rinfo->flags, RIPNG_RTF_FIB);
+        }
+
+      api.nexthop = nexthops;
+      api.nexthop_num = count;
+      api.ifindex = ifindexes;
+      api.ifindex_num = count;
+
+      rinfo = listgetdata (listhead (list));
+
       SET_FLAG (api.message, ZAPI_MESSAGE_METRIC);
-      api.metric = metric;
-      
-      zapi_ipv6_route (ZEBRA_IPV6_ROUTE_ADD, zclient, p, &api);
+      api.metric = rinfo->metric;
+
+      zapi_ipv6_route (cmd, zclient,
+                       (struct prefix_ipv6 *)&rp->p, &api);
+
+      if (IS_RIPNG_DEBUG_ZEBRA)
+        zlog_debug ("%s: %s/%d nexthops %d",
+                    (cmd == ZEBRA_IPV6_ROUTE_ADD) ? \
+                        "Install into zebra" : "Delete from zebra",
+                    inet6_ntoa (rp->p.u.prefix6), rp->p.prefixlen, count);
     }
 }
 
+/* Add/update ECMP routes to zebra. */
 void
-ripng_zebra_ipv6_delete (struct prefix_ipv6 *p, struct in6_addr *nexthop,
-			 unsigned int ifindex)
+ripng_zebra_ipv6_add (struct route_node *rp)
 {
-  struct zapi_ipv6 api;
-
-  if (zclient->redist[ZEBRA_ROUTE_RIPNG])
-    {
-      api.type = ZEBRA_ROUTE_RIPNG;
-      api.flags = 0;
-      api.message = 0;
-      api.safi = SAFI_UNICAST;
-      SET_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP);
-      api.nexthop_num = 1;
-      api.nexthop = &nexthop;
-      SET_FLAG (api.message, ZAPI_MESSAGE_IFINDEX);
-      api.ifindex_num = 1;
-      api.ifindex = &ifindex;
+  ripng_zebra_ipv6_send (rp, ZEBRA_IPV6_ROUTE_ADD);
+}
 
-      zapi_ipv6_route (ZEBRA_IPV6_ROUTE_DELETE, zclient, p, &api);
-    }
+/* Delete ECMP routes from zebra. */
+void
+ripng_zebra_ipv6_delete (struct route_node *rp)
+{
+  ripng_zebra_ipv6_send (rp, ZEBRA_IPV6_ROUTE_DELETE);
 }
 
 /* Zebra route add and delete treatment. */
diff --git a/ripngd/ripngd.c b/ripngd/ripngd.c
index 4c0b67df..21e45b6e 100644
--- a/ripngd/ripngd.c
+++ b/ripngd/ripngd.c
@@ -421,8 +421,13 @@ ripng_garbage_collect (struct thread *t)
   rp = rinfo->rp;
 
   /* Unlock route_node. */
-  rp->info = NULL;
-  route_unlock_node (rp);
+  listnode_delete (rp->info, rinfo);
+  if (list_isempty ((struct list *)rp->info))
+    {
+      list_free (rp->info);
+      rp->info = NULL;
+      route_unlock_node (rp);
+    }
 
   /* Free RIPng routing information. */
   ripng_info_free (rinfo);
@@ -430,41 +435,159 @@ ripng_garbage_collect (struct thread *t)
   return 0;
 }
 
-/* Timeout RIPng routes. */
-static int
-ripng_timeout (struct thread *t)
+static void ripng_timeout_update (struct ripng_info *rinfo);
+
+/* Add new route to the ECMP list.
+ * RETURN: the new entry added in the list
+ */
+struct ripng_info *
+ripng_ecmp_add (struct ripng_info *rinfo_new)
 {
-  struct ripng_info *rinfo;
-  struct route_node *rp;
+  struct route_node *rp = rinfo_new->rp;
+  struct ripng_info *rinfo = NULL;
+  struct list *list = NULL;
 
-  rinfo = THREAD_ARG (t);
-  rinfo->t_timeout = NULL;
+  if (rp->info == NULL)
+    rp->info = list_new ();
+  list = (struct list *)rp->info;
 
-  /* Get route_node pointer. */
-  rp = rinfo->rp;
+  rinfo = ripng_info_new ();
+  memcpy (rinfo, rinfo_new, sizeof (struct ripng_info));
+  listnode_add (list, rinfo);
+
+  if (ripng_route_rte (rinfo))
+    {
+      ripng_timeout_update (rinfo);
+      ripng_zebra_ipv6_add (rp);
+    }
+
+  ripng_aggregate_increment (rp, rinfo);
+
+  /* Set the route change flag on the first entry. */
+  rinfo = listgetdata (listhead (list));
+  SET_FLAG (rinfo->flags, RIPNG_RTF_CHANGED);
+
+  /* Signal the output process to trigger an update. */
+  ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
+
+  return rinfo;
+}
+
+/* Replace the ECMP list with the new route.
+ * RETURN: the new entry added in the list
+ */
+struct ripng_info *
+ripng_ecmp_replace (struct ripng_info *rinfo_new)
+{
+  struct route_node *rp = rinfo_new->rp;
+  struct list *list = (struct list *)rp->info;
+  struct ripng_info *rinfo = NULL, *tmp_rinfo = NULL;
+  struct listnode *node = NULL, *nextnode = NULL;
+
+  if (list == NULL || listcount (list) == 0)
+    return ripng_ecmp_add (rinfo_new);
+
+  /* Get the first entry */
+  rinfo = listgetdata (listhead (list));
+
+  /* Learnt route replaced by a local one. Delete it from zebra. */
+  if (ripng_route_rte (rinfo) && !ripng_route_rte (rinfo_new))
+    if (CHECK_FLAG (rinfo->flags, RIPNG_RTF_FIB))
+      ripng_zebra_ipv6_delete (rp);
+
+  if (rinfo->metric != RIPNG_METRIC_INFINITY)
+    ripng_aggregate_decrement_list (rp, list);
+
+  /* Re-use the first entry, and delete the others. */
+  for (ALL_LIST_ELEMENTS (list, node, nextnode, tmp_rinfo))
+    if (tmp_rinfo != rinfo)
+      {
+        RIPNG_TIMER_OFF (tmp_rinfo->t_timeout);
+        RIPNG_TIMER_OFF (tmp_rinfo->t_garbage_collect);
+        list_delete_node (list, node);
+        ripng_info_free (tmp_rinfo);
+      }
+
+  RIPNG_TIMER_OFF (rinfo->t_timeout);
+  RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
+  memcpy (rinfo, rinfo_new, sizeof (struct ripng_info));
+
+  if (ripng_route_rte (rinfo))
+    {
+      ripng_timeout_update (rinfo);
+      /* The ADD message implies an update. */
+      ripng_zebra_ipv6_add (rp);
+    }
+
+  ripng_aggregate_increment (rp, rinfo);
+
+  /* Set the route change flag. */
+  SET_FLAG (rinfo->flags, RIPNG_RTF_CHANGED);
+
+  /* Signal the output process to trigger an update. */
+  ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
+
+  return rinfo;
+}
+
+/* Delete one route from the ECMP list.
+ * RETURN:
+ *  null - the entry is freed, and other entries exist in the list
+ *  the entry - the entry is the last one in the list; its metric is set
+ *              to INFINITY, and the garbage collector is started for it
+ */
+struct ripng_info *
+ripng_ecmp_delete (struct ripng_info *rinfo)
+{
+  struct route_node *rp = rinfo->rp;
+  struct list *list = (struct list *)rp->info;
+
+  RIPNG_TIMER_OFF (rinfo->t_timeout);
+
+  if (rinfo->metric != RIPNG_METRIC_INFINITY)
+    ripng_aggregate_decrement (rp, rinfo);
+
+  if (listcount (list) > 1)
+    {
+      /* Some other ECMP entries still exist. Just delete this entry. */
+      RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
+      listnode_delete (list, rinfo);
+      if (ripng_route_rte (rinfo) && CHECK_FLAG (rinfo->flags, RIPNG_RTF_FIB))
+        /* The ADD message implies the update. */
+        ripng_zebra_ipv6_add (rp);
+      ripng_info_free (rinfo);
+      rinfo = NULL;
+    }
+  else
+    {
+      assert (rinfo == listgetdata (listhead (list)));
 
-  /* - The garbage-collection timer is set for 120 seconds. */
-  RIPNG_TIMER_ON (rinfo->t_garbage_collect, ripng_garbage_collect, 
-		  ripng->garbage_time);
+      /* This is the only entry left in the list. We must keep it in
+       * the list for garbage collection time, with INFINITY metric. */
 
-  /* Delete this route from the kernel. */
-  ripng_zebra_ipv6_delete ((struct prefix_ipv6 *)&rp->p, &rinfo->nexthop,
-				rinfo->ifindex);
-  /* - The metric for the route is set to 16 (infinity).  This causes
-     the route to be removed from service. */
-  rinfo->metric = RIPNG_METRIC_INFINITY;
-  rinfo->flags &= ~RIPNG_RTF_FIB;
+      rinfo->metric = RIPNG_METRIC_INFINITY;
+      RIPNG_TIMER_ON (rinfo->t_garbage_collect,
+                      ripng_garbage_collect, ripng->garbage_time);
 
-  /* Aggregate count decrement. */
-  ripng_aggregate_decrement (rp, rinfo);
+      if (ripng_route_rte (rinfo) && CHECK_FLAG (rinfo->flags, RIPNG_RTF_FIB))
+        ripng_zebra_ipv6_delete (rp);
+    }
 
-  /* - The route change flag is to indicate that this entry has been
-     changed. */
-  rinfo->flags |= RIPNG_RTF_CHANGED;
+  /* Set the route change flag on the first entry. */
+  rinfo = listgetdata (listhead (list));
+  SET_FLAG (rinfo->flags, RIPNG_RTF_CHANGED);
 
-  /* - The output process is signalled to trigger a response. */
+  /* Signal the output process to trigger an update. */
   ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
 
+  return rinfo;
+}
+
+/* Timeout RIPng routes. */
+static int
+ripng_timeout (struct thread *t)
+{
+  ripng_ecmp_delete ((struct ripng_info *)THREAD_ARG (t));
   return 0;
 }
 
@@ -628,11 +751,12 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
   int ret;
   struct prefix_ipv6 p;
   struct route_node *rp;
-  struct ripng_info *rinfo;
+  struct ripng_info *rinfo = NULL, newinfo;
   struct ripng_interface *ri;
   struct in6_addr *nexthop;
-  u_char oldmetric;
   int same = 0;
+  struct list *list = NULL;
+  struct listnode *node = NULL;
 
   /* Make prefix structure. */
   memset (&p, 0, sizeof (struct prefix_ipv6));
@@ -653,24 +777,23 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
   if (ret < 0)
     return;
 
+  memset (&newinfo, 0, sizeof (newinfo));
+  newinfo.type = ZEBRA_ROUTE_RIPNG;
+  newinfo.sub_type = RIPNG_ROUTE_RTE;
+  if (ripng_nexthop->flag == RIPNG_NEXTHOP_ADDRESS)
+    newinfo.nexthop = ripng_nexthop->address;
+  else
+    newinfo.nexthop = from->sin6_addr;
+  newinfo.from = from->sin6_addr;
+  newinfo.ifindex = ifp->ifindex;
+  newinfo.metric = rte->metric;
+  newinfo.metric_out = rte->metric; /* XXX */
+  newinfo.tag = ntohs (rte->tag);   /* XXX */
+
   /* Modify entry. */
   if (ri->routemap[RIPNG_FILTER_IN])
     {
       int ret;
-      struct ripng_info newinfo;
-
-      memset (&newinfo, 0, sizeof (struct ripng_info));
-      newinfo.type = ZEBRA_ROUTE_RIPNG;
-      newinfo.sub_type = RIPNG_ROUTE_RTE;
-      if (ripng_nexthop->flag == RIPNG_NEXTHOP_ADDRESS)
-        newinfo.nexthop = ripng_nexthop->address;
-      else
-        newinfo.nexthop = from->sin6_addr;
-      newinfo.from   = from->sin6_addr;
-      newinfo.ifindex = ifp->ifindex;
-      newinfo.metric = rte->metric;
-      newinfo.metric_out = rte->metric; /* XXX */
-      newinfo.tag    = ntohs(rte->tag); /* XXX */
 
       ret = route_map_apply (ri->routemap[RIPNG_FILTER_IN], 
 			     (struct prefix *)&p, RMAP_RIPNG, &newinfo);
@@ -731,24 +854,66 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
   /* Lookup RIPng routing table. */
   rp = route_node_get (ripng->table, (struct prefix *) &p);
 
-  /* Sanity check */
-  rinfo = rp->info;
+  newinfo.rp = rp;
+  newinfo.nexthop = *nexthop;
+  newinfo.metric = rte->metric;
+  newinfo.tag = ntohs (rte->tag);
+
+  /* Check to see whether there is already RIPng route on the table. */
+  if ((list = rp->info) != NULL)
+    for (ALL_LIST_ELEMENTS_RO (list, node, rinfo))
+      {
+        /* Need to compare with redistributed entry or local entry */
+        if (!ripng_route_rte (rinfo))
+          break;
+
+        if (IPV6_ADDR_SAME (&rinfo->from, &from->sin6_addr) &&
+            IPV6_ADDR_SAME (&rinfo->nexthop, nexthop))
+          break;
+
+        if (!listnextnode (node))
+          {
+            /* Not found in the list */
+
+            if (rte->metric > rinfo->metric)
+              {
+                /* New route has a greater metric. Discard it. */
+                route_unlock_node (rp);
+                return;
+              }
+
+            if (rte->metric < rinfo->metric)
+              /* New route has a smaller metric. Replace the ECMP list
+               * with the new one in below. */
+              break;
+
+            /* Metrics are same. Keep "rinfo" null and the new route
+             * is added in the ECMP list in below. */
+          }
+      }
+
   if (rinfo)
     {
       /* Redistributed route check. */
       if (rinfo->type != ZEBRA_ROUTE_RIPNG
 	  && rinfo->metric != RIPNG_METRIC_INFINITY)
-	return;
+        {
+          route_unlock_node (rp);
+          return;
+        }
 
       /* Local static route. */
       if (rinfo->type == ZEBRA_ROUTE_RIPNG
 	  && ((rinfo->sub_type == RIPNG_ROUTE_STATIC) ||
 	      (rinfo->sub_type == RIPNG_ROUTE_DEFAULT))
 	  && rinfo->metric != RIPNG_METRIC_INFINITY)
-	return;
+        {
+          route_unlock_node (rp);
+          return;
+        }
     }
 
-  if (rp->info == NULL)
+  if (!rinfo)
     {
       /* Now, check to see whether there is already an explicit route
 	 for the destination prefix.  If there is no such route, add
@@ -756,53 +921,10 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
 	 infinity (there is no point in adding a route which
 	 unusable). */
       if (rte->metric != RIPNG_METRIC_INFINITY)
-	{
-	  rinfo = ripng_info_new ();
-	  
-	  /* - Setting the destination prefix and length to those in
-	     the RTE. */
-	  rp->info = rinfo;
-	  rinfo->rp = rp;
-
-	  /* - Setting the metric to the newly calculated metric (as
-	     described above). */
-	  rinfo->metric = rte->metric;
-	  rinfo->tag = ntohs (rte->tag);
-
-	  /* - Set the next hop address to be the address of the router
-	     from which the datagram came or the next hop address
-	     specified by a next hop RTE. */
-	  IPV6_ADDR_COPY (&rinfo->nexthop, nexthop);
-	  IPV6_ADDR_COPY (&rinfo->from, &from->sin6_addr);
-	  rinfo->ifindex = ifp->ifindex;
-
-	  /* - Initialize the timeout for the route.  If the
-	     garbage-collection timer is running for this route, stop it. */
-	  ripng_timeout_update (rinfo);
-
-	  /* - Set the route change flag. */
-	  rinfo->flags |= RIPNG_RTF_CHANGED;
-
-	  /* - Signal the output process to trigger an update (see section
-	     2.5). */
-	  ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
-
-	  /* Finally, route goes into the kernel. */
-	  rinfo->type = ZEBRA_ROUTE_RIPNG;
-	  rinfo->sub_type = RIPNG_ROUTE_RTE;
-
-	  ripng_zebra_ipv6_add (&p, &rinfo->nexthop, rinfo->ifindex,
-				rinfo->metric);
-	  rinfo->flags |= RIPNG_RTF_FIB;
-
-	  /* Aggregate check. */
-	  ripng_aggregate_increment (rp, rinfo);
-	}
+        ripng_ecmp_add (&newinfo);
     }
   else
     {
-      rinfo = rp->info;
-	  
       /* If there is an existing route, compare the next hop address
 	 to the address of the router from which the datagram came.
 	 If this datagram is from the same router as the existing
@@ -810,9 +932,6 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
       same = (IN6_ARE_ADDR_EQUAL (&rinfo->from, &from->sin6_addr) 
 	      && (rinfo->ifindex == ifp->ifindex));
 
-      if (same)
-	ripng_timeout_update (rinfo);
-
       /* Next, compare the metrics.  If the datagram is from the same
 	 router as the existing route, and the new metric is different
 	 than the old one; or, if the new metric is lower than the old
@@ -820,96 +939,24 @@ ripng_route_process (struct rte *rte, struct sockaddr_in6 *from,
       if ((same && rinfo->metric != rte->metric) ||
 	  rte->metric < rinfo->metric)
 	{
-	  /* - Adopt the route from the datagram.  That is, put the
-	     new metric in, and adjust the next hop address (if
-	     necessary). */
-	  oldmetric = rinfo->metric;
-	  rinfo->metric = rte->metric;
-	  rinfo->tag = ntohs (rte->tag);
-	  IPV6_ADDR_COPY (&rinfo->from, &from->sin6_addr);
-	  rinfo->ifindex = ifp->ifindex;
-
-	  /* Should a new route to this network be established
-	     while the garbage-collection timer is running, the
-	     new route will replace the one that is about to be
-	     deleted.  In this case the garbage-collection timer
-	     must be cleared. */
-
-	  if (oldmetric == RIPNG_METRIC_INFINITY &&
-	      rinfo->metric < RIPNG_METRIC_INFINITY)
-	    {
-	      rinfo->type = ZEBRA_ROUTE_RIPNG;
-	      rinfo->sub_type = RIPNG_ROUTE_RTE;
-
-	      RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
-
-	      if (! IPV6_ADDR_SAME (&rinfo->nexthop, nexthop))
-		IPV6_ADDR_COPY (&rinfo->nexthop, nexthop);
-
-	      ripng_zebra_ipv6_add (&p, nexthop, ifp->ifindex, rinfo->metric);
-	      rinfo->flags |= RIPNG_RTF_FIB;
-
-	      /* The aggregation counter needs to be updated because
-		     the prefixes, which are into the gc, have been
-			 removed from the aggregator (see ripng_timout). */
-		  ripng_aggregate_increment (rp, rinfo);
-	    }
-
-	  /* Update nexthop and/or metric value.  */
-	  if (oldmetric != RIPNG_METRIC_INFINITY)
-	    {
-	      ripng_zebra_ipv6_delete (&p, &rinfo->nexthop, rinfo->ifindex);
-	      ripng_zebra_ipv6_add (&p, nexthop, ifp->ifindex, rinfo->metric);
-	      rinfo->flags |= RIPNG_RTF_FIB;
-
-	      if (! IPV6_ADDR_SAME (&rinfo->nexthop, nexthop))
-		IPV6_ADDR_COPY (&rinfo->nexthop, nexthop);
-	    }
-
-	  /* - Set the route change flag and signal the output process
-	     to trigger an update. */
-	  rinfo->flags |= RIPNG_RTF_CHANGED;
-	  ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
-
-	  /* - If the new metric is infinity, start the deletion
-	     process (described above); */
-	  if (rinfo->metric == RIPNG_METRIC_INFINITY)
-	    {
-	      /* If the new metric is infinity, the deletion process
-		 begins for the route, which is no longer used for
-		 routing packets.  Note that the deletion process is
-		 started only when the metric is first set to
-		 infinity.  If the metric was already infinity, then a
-		 new deletion process is not started. */
-	      if (oldmetric != RIPNG_METRIC_INFINITY)
-		{
-		  /* - The garbage-collection timer is set for 120 seconds. */
-		  RIPNG_TIMER_ON (rinfo->t_garbage_collect, 
-				  ripng_garbage_collect, ripng->garbage_time);
-		  RIPNG_TIMER_OFF (rinfo->t_timeout);
-
-		  /* - The metric for the route is set to 16
-		     (infinity).  This causes the route to be removed
-		     from service.*/
-		  ripng_zebra_ipv6_delete (&p, &rinfo->nexthop, rinfo->ifindex);
-		  rinfo->flags &= ~RIPNG_RTF_FIB;
-
-		  /* Aggregate count decrement. */
-		  ripng_aggregate_decrement (rp, rinfo);
-
-		  /* - The route change flag is to indicate that this
-		     entry has been changed. */
-		  /* - The output process is signalled to trigger a
-                     response. */
-		  ;  /* Above processes are already done previously. */
-		}
-	    }
-	  else
-	    {
-	      /* otherwise, re-initialize the timeout. */
-	      ripng_timeout_update (rinfo);
-	    }
+          if (listcount (list) == 1)
+            {
+              if (newinfo.metric != RIPNG_METRIC_INFINITY)
+                ripng_ecmp_replace (&newinfo);
+              else
+                ripng_ecmp_delete (rinfo);
+            }
+          else
+            {
+              if (newinfo.metric < rinfo->metric)
+                ripng_ecmp_replace (&newinfo);
+              else /* newinfo.metric > rinfo->metric */
+                ripng_ecmp_delete (rinfo);
+            }
 	}
+      else /* same & no change */
+        ripng_timeout_update (rinfo);
+
       /* Unlock tempolary lock of the route. */
       route_unlock_node (rp);
     }
@@ -921,7 +968,8 @@ ripng_redistribute_add (int type, int sub_type, struct prefix_ipv6 *p,
 			unsigned int ifindex, struct in6_addr *nexthop)
 {
   struct route_node *rp;
-  struct ripng_info *rinfo;
+  struct ripng_info *rinfo = NULL, newinfo;
+  struct list *list = NULL;
 
   /* Redistribute route  */
   if (IN6_IS_ADDR_LINKLOCAL (&p->prefix))
@@ -930,10 +978,20 @@ ripng_redistribute_add (int type, int sub_type, struct prefix_ipv6 *p,
     return;
 
   rp = route_node_get (ripng->table, (struct prefix *) p);
-  rinfo = rp->info;
 
-  if (rinfo)
+  memset (&newinfo, 0, sizeof (struct ripng_info));
+  newinfo.type = type;
+  newinfo.sub_type = sub_type;
+  newinfo.ifindex = ifindex;
+  newinfo.metric = 1;
+  newinfo.rp = rp;
+  if (nexthop && IN6_IS_ADDR_LINKLOCAL(nexthop))
+    newinfo.nexthop = *nexthop;
+
+  if ((list = rp->info) != NULL && listcount (list) != 0)
     {
+      rinfo = listgetdata (listhead (list));
+
       if (rinfo->type == ZEBRA_ROUTE_CONNECT
           && rinfo->sub_type == RIPNG_ROUTE_INTERFACE
 	  && rinfo->metric != RIPNG_METRIC_INFINITY) {
@@ -953,42 +1011,12 @@ ripng_redistribute_add (int type, int sub_type, struct prefix_ipv6 *p,
 	  return;
 	}
       }
-      
-      RIPNG_TIMER_OFF (rinfo->t_timeout);
-      RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
-
-      /* Tells the other daemons about the deletion of
-       * this RIPng route
-       **/
-      if (ripng_route_rte (rinfo))
-	ripng_zebra_ipv6_delete ((struct prefix_ipv6 *)&rp->p, &rinfo->nexthop,
-			       rinfo->metric);
-
-      rp->info = NULL;
-      ripng_info_free (rinfo);
 
+      rinfo = ripng_ecmp_replace (&newinfo);
       route_unlock_node (rp);
-
     }
-
-  rinfo = ripng_info_new ();
-
-  rinfo->type = type;
-  rinfo->sub_type = sub_type;
-  rinfo->ifindex = ifindex;
-  rinfo->metric = 1;
-  rinfo->rp = rp;
-  
-  if (nexthop && IN6_IS_ADDR_LINKLOCAL(nexthop))
-    rinfo->nexthop = *nexthop;
-  
-  rinfo->flags |= RIPNG_RTF_FIB;
-  rp->info = rinfo;
-
-  /* Aggregate check. */
-  ripng_aggregate_increment (rp, rinfo);
-
-  rinfo->flags |= RIPNG_RTF_CHANGED;
+  else
+    rinfo = ripng_ecmp_add (&newinfo);
 
   if (IS_RIPNG_DEBUG_EVENT) {
     if (!nexthop)
@@ -1021,31 +1049,37 @@ ripng_redistribute_delete (int type, int sub_type, struct prefix_ipv6 *p,
 
   if (rp)
     {
-      rinfo = rp->info;
-
-      if (rinfo != NULL
-	  && rinfo->type == type 
-	  && rinfo->sub_type == sub_type 
-	  && rinfo->ifindex == ifindex)
-	{
-	  /* Perform poisoned reverse. */
-	  rinfo->metric = RIPNG_METRIC_INFINITY;
-	  RIPNG_TIMER_ON (rinfo->t_garbage_collect, 
-			ripng_garbage_collect, ripng->garbage_time);
-	  RIPNG_TIMER_OFF (rinfo->t_timeout);
-
-	  /* Aggregate count decrement. */
-	  ripng_aggregate_decrement (rp, rinfo);
-
-	  rinfo->flags |= RIPNG_RTF_CHANGED;
-	  
-          if (IS_RIPNG_DEBUG_EVENT)
-            zlog_debug ("Poisone %s/%d on the interface %s with an infinity metric [delete]",
-                       inet6_ntoa(p->prefix), p->prefixlen,
-                       ifindex2ifname(ifindex));
-
-	  ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
-	}
+      struct list *list = rp->info;
+
+      if (list != NULL && listcount (list) != 0)
+        {
+          rinfo = listgetdata (listhead (list));
+          if (rinfo != NULL
+              && rinfo->type == type
+              && rinfo->sub_type == sub_type
+              && rinfo->ifindex == ifindex)
+            {
+              /* Perform poisoned reverse. */
+              rinfo->metric = RIPNG_METRIC_INFINITY;
+              RIPNG_TIMER_ON (rinfo->t_garbage_collect,
+                              ripng_garbage_collect, ripng->garbage_time);
+              RIPNG_TIMER_OFF (rinfo->t_timeout);
+
+              /* Aggregate count decrement. */
+              ripng_aggregate_decrement (rp, rinfo);
+
+              rinfo->flags |= RIPNG_RTF_CHANGED;
+
+              if (IS_RIPNG_DEBUG_EVENT)
+                zlog_debug ("Poisone %s/%d on the interface %s with an "
+                            "infinity metric [delete]",
+                            inet6_ntoa (p->prefix), p->prefixlen,
+                            ifindex2ifname (ifindex));
+
+              ripng_event (RIPNG_TRIGGERED_UPDATE, 0);
+            }
+        }
+      route_unlock_node (rp);
     }
 }
 
@@ -1054,14 +1088,16 @@ void
 ripng_redistribute_withdraw (int type)
 {
   struct route_node *rp;
-  struct ripng_info *rinfo;
+  struct ripng_info *rinfo = NULL;
+  struct list *list = NULL;
 
   if (!ripng)
     return;
   
   for (rp = route_top (ripng->table); rp; rp = route_next (rp))
-    if ((rinfo = rp->info) != NULL)
+    if ((list = rp->info) != NULL)
       {
+	rinfo = listgetdata (listhead (list));
 	if ((rinfo->type == type)
 	    && (rinfo->sub_type != RIPNG_ROUTE_INTERFACE))
 	  {
@@ -1296,7 +1332,7 @@ ripng_request_process (struct ripng_packet *packet,int size,
 
 	  if (rp)
 	    {
-	      rinfo = rp->info;
+	      rinfo = listgetdata (listhead ((struct list *)rp->info));
 	      rte->metric = rinfo->metric;
 	      route_unlock_node (rp);
 	    }
@@ -1404,12 +1440,18 @@ static void
 ripng_clear_changed_flag (void)
 {
   struct route_node *rp;
-  struct ripng_info *rinfo;
+  struct ripng_info *rinfo = NULL;
+  struct list *list = NULL;
+  struct listnode *listnode = NULL;
 
   for (rp = route_top (ripng->table); rp; rp = route_next (rp))
-    if ((rinfo = rp->info) != NULL)
-      if (rinfo->flags & RIPNG_RTF_CHANGED)
-	rinfo->flags &= ~RIPNG_RTF_CHANGED;
+    if ((list = rp->info) != NULL)
+      for (ALL_LIST_ELEMENTS_RO (list, listnode, rinfo))
+        {
+          UNSET_FLAG (rinfo->flags, RIPNG_RTF_CHANGED);
+          /* This flag can be set only on the first entry. */
+          break;
+        }
 }
 
 /* Regular update of RIPng route.  Send all routing formation to RIPng
@@ -1587,6 +1629,8 @@ ripng_output_process (struct interface *ifp, struct sockaddr_in6 *to,
   struct ripng_aggregate *aggregate;
   struct prefix_ipv6 *p;
   struct list * ripng_rte_list;
+  struct list *list = NULL;
+  struct listnode *listnode = NULL;
 
   if (IS_RIPNG_DEBUG_EVENT) {
     if (to)
@@ -1603,7 +1647,9 @@ ripng_output_process (struct interface *ifp, struct sockaddr_in6 *to,
  
   for (rp = route_top (ripng->table); rp; rp = route_next (rp))
     {
-      if ((rinfo = rp->info) != NULL && rinfo->suppress == 0)
+      if ((list = rp->info) != NULL &&
+          (rinfo = listgetdata (listhead (list))) != NULL &&
+          rinfo->suppress == 0)
 	{
 	  /* If no route-map are applied, the RTE will be these following
 	   * informations.
@@ -1635,8 +1681,17 @@ ripng_output_process (struct interface *ifp, struct sockaddr_in6 *to,
 	  if (ri->split_horizon == RIPNG_SPLIT_HORIZON)
 	  {
 	    /* We perform split horizon for RIPng routes. */
-	    if ((rinfo->type == ZEBRA_ROUTE_RIPNG) &&
-		rinfo->ifindex == ifp->ifindex)
+	    int suppress = 0;
+	    struct ripng_info *tmp_rinfo = NULL;
+
+	    for (ALL_LIST_ELEMENTS_RO (list, listnode, tmp_rinfo))
+	      if (tmp_rinfo->type == ZEBRA_ROUTE_RIPNG &&
+	          tmp_rinfo->ifindex == ifp->ifindex)
+	        {
+	          suppress = 1;
+	          break;
+	        }
+	    if (suppress)
 	      continue;
 	  }
 
@@ -1715,9 +1770,12 @@ ripng_output_process (struct interface *ifp, struct sockaddr_in6 *to,
 	   * for RIPng routes.
 	   **/
 	  if (ri->split_horizon == RIPNG_SPLIT_HORIZON_POISONED_REVERSE) {
-	    if ((rinfo->type == ZEBRA_ROUTE_RIPNG) &&
-	         rinfo->ifindex == ifp->ifindex)
-	         rinfo->metric_out = RIPNG_METRIC_INFINITY;
+	    struct ripng_info *tmp_rinfo = NULL;
+
+	    for (ALL_LIST_ELEMENTS_RO (list, listnode, tmp_rinfo))
+	      if ((tmp_rinfo->type == ZEBRA_ROUTE_RIPNG) &&
+	           tmp_rinfo->ifindex == ifp->ifindex)
+	        rinfo->metric_out = RIPNG_METRIC_INFINITY;
 	  }
 
 	  /* Add RTE to the list */
@@ -1983,6 +2041,8 @@ DEFUN (show_ipv6_ripng,
   struct ripng_info *rinfo;
   struct ripng_aggregate *aggregate;
   struct prefix_ipv6 *p;
+  struct list *list = NULL;
+  struct listnode *listnode = NULL;
   int len;
 
   if (! ripng)
@@ -2020,7 +2080,8 @@ DEFUN (show_ipv6_ripng,
 		   VTY_NEWLINE);
 	}
 
-      if ((rinfo = rp->info) != NULL)
+      if ((list = rp->info) != NULL)
+        for (ALL_LIST_ELEMENTS_RO (list, listnode, rinfo))
 	{
 	  p = (struct prefix_ipv6 *) &rp->p;
 
@@ -2757,24 +2818,37 @@ ripng_clean()
   int i;
   struct route_node *rp;
   struct ripng_info *rinfo;
+  struct ripng_aggregate *aggregate;
+  struct list *list = NULL;
+  struct listnode *listnode = NULL;
 
   if (ripng) {
     /* Clear RIPng routes */
-    for (rp = route_top (ripng->table); rp; rp = route_next (rp)) {
-      if ((rinfo = rp->info) != NULL) {
-        if ((rinfo->type == ZEBRA_ROUTE_RIPNG) &&
-            (rinfo->sub_type == RIPNG_ROUTE_RTE))
-          ripng_zebra_ipv6_delete ((struct prefix_ipv6 *)&rp->p,
-                                   &rinfo->nexthop, rinfo->metric);
-
-        RIPNG_TIMER_OFF (rinfo->t_timeout);
-        RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
-
-        rp->info = NULL;
-        route_unlock_node (rp);
-
-        ripng_info_free(rinfo);
-      }
+    for (rp = route_top (ripng->table); rp; rp = route_next (rp))
+      {
+        if ((list = rp->info) != NULL)
+          {
+            rinfo = listgetdata (listhead (list));
+            if (ripng_route_rte (rinfo))
+              ripng_zebra_ipv6_delete (rp);
+
+            for (ALL_LIST_ELEMENTS_RO (list, listnode, rinfo))
+              {
+                RIPNG_TIMER_OFF (rinfo->t_timeout);
+                RIPNG_TIMER_OFF (rinfo->t_garbage_collect);
+                ripng_info_free (rinfo);
+              }
+            list_delete (list);
+            rp->info = NULL;
+            route_unlock_node (rp);
+          }
+
+        if ((aggregate = rp->aggregate) != NULL)
+          {
+            ripng_aggregate_free (aggregate);
+            rp->aggregate = NULL;
+            route_unlock_node (rp);
+          }
     }
 
     /* Cancel the RIPng timers */
diff --git a/ripngd/ripngd.h b/ripngd/ripngd.h
index ab06d81b..75c5dfa0 100644
--- a/ripngd/ripngd.h
+++ b/ripngd/ripngd.h
@@ -389,12 +389,8 @@ extern void ripng_redistribute_withdraw (int type);
 extern void ripng_distribute_update_interface (struct interface *);
 extern void ripng_if_rmap_update_interface (struct interface *);
 
-extern void ripng_zebra_ipv6_add (struct prefix_ipv6 *p,
-                                  struct in6_addr *nexthop,
-                                  unsigned int ifindex, u_char metric);
-extern void ripng_zebra_ipv6_delete (struct prefix_ipv6 *p,
-                                     struct in6_addr *nexthop,
-                                     unsigned int ifindex);
+extern void ripng_zebra_ipv6_add (struct route_node *);
+extern void ripng_zebra_ipv6_delete (struct route_node *);
 
 extern void ripng_redistribute_clean (void);
 extern int ripng_redistribute_check (int);
@@ -418,4 +414,8 @@ extern int ripng_interface_address_delete (int command, struct zclient *, zebra_
 
 extern int ripng_network_write (struct vty *, int);
 
+extern struct ripng_info *ripng_ecmp_add (struct ripng_info *);
+extern struct ripng_info *ripng_ecmp_replace (struct ripng_info *);
+extern struct ripng_info *ripng_ecmp_delete (struct ripng_info *);
+
 #endif /* _ZEBRA_RIPNG_RIPNGD_H */