[quagga-dev 5024] OSPF shortest path computation

Atis Elsts atis at mikrotik.com
Mon Aug 6 15:06:07 BST 2007


Hi,
there seems to be a problem with shortest path tree calculations - for setups 
that contain loops. The optimal path is not always found. I believe that 
vertex relaxation in Dijkstra algorithm is done incorrectly.

patch (for the current CVS snapshot):

diff -ruN quagga-0.99.8-old/lib/pqueue.c quagga-0.99.8/lib/pqueue.c
--- quagga-0.99.8-old/lib/pqueue.c      2007-08-06 16:41:52.000000000 +0300
+++ quagga-0.99.8/lib/pqueue.c  2007-08-06 16:51:37.000000000 +0300
@@ -42,7 +42,7 @@
 #define RIGHT_OF(x) (2 * x + 2)
 #define HAVE_CHILD(x,q) (x < (q)->size / 2)

-static void
+void
 trickle_up (int index, struct pqueue *queue)
 {
   void *tmp;
diff -ruN quagga-0.99.8-old/ospfd/ospf_spf.c quagga-0.99.8/ospfd/ospf_spf.c
--- quagga-0.99.8-old/ospfd/ospf_spf.c  2007-08-06 16:41:52.000000000 +0300
+++ quagga-0.99.8/ospfd/ospf_spf.c      2007-08-06 16:51:20.000000000 +0300
@@ -898,7 +898,7 @@
               if (ospf_nexthop_calculation (area, v, w, l, distance))
                 /* Decrease the key of the node in the heap,
                  * re-sort the heap. */
-                trickle_down (w_lsa->stat, candidate);
+                trickle_up (w_lsa->stat, candidate);
             }
         } /* end W is already on the candidate list */
     } /* end loop over the links in V's LSA */



More information about the Quagga-dev mailing list