diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog
index ac59670..99599f5 100644
--- a/ospfd/ChangeLog
+++ b/ospfd/ChangeLog
@@ -1,3 +1,49 @@
+2006-04-24 Paul Jakma <paul.jakma@sun.com>
+
+	* (general) More Virtual-link fixes, again with much help in
+	  testing / debug from Juergen Kammer. Primarily in SPF.
+	* ospf_spf.h: Add guard. ospf_interface.h will include this
+	  header.
+	* ospf_interface.h: Modify ospf_vl_lookup definition to take
+	  struct ospf as argument, so as to allow for NULL area
+	  argument.
+	  (struct ospf_vl_data) Remove out_oi, instead add a struct
+	  vertex_nexthop, to use as initial nexthop for backbone paths
+	  through a vlink.
+	* ospf_interface.c: (ospf_vl_lookup) Modified to allow
+	  NULL area to be passed to indicate "any" (first) area.
+	  Add extra debug.
+	  (ospf_vl_set_params) vl_oi -> nexthop. Add extra debug.
+	  (ospf_vl_up_check) Fix debug, inet_ntoa returns a static
+	  buffer..
+	* ospf_route.c: (ospf_intra_add_router) Vlinks dont go through
+	  backbone, don't bother checking.
+	* ospf_spf.c: (static struct list vertex_list) Record vertices
+	  that will need to be freed.
+	  (cmp) Order network before router vertices, as required,
+	  wasn't implemented.
+	  (vertex_nexthop_free) Mild additional robustness check.
+	  (vertex_parent_free) Take void argument, as this function
+	  is passed as list deconstructor for vertex parent list.
+	  (ospf_vertex_new) More debug. Set deconstructor for parent
+	  list. Track allocated vertices on the vertex_list.
+	  (ospf_vertex_free) Get rid of the tricky recursive cleanup of
+	  vertices. Now frees only the given vertex. 
+	  (ospf_vertex_add_parent) Fix assert.
+	  (ospf_nexthop_calculation) Fix calculation of nexthop for
+	  VLink vertices, lookup the vl_data and use its previously
+	  recorded nexthop information.
+	  (ospf_spf_calculate) Vertices are freed simply by deleting
+	  vertex_list nodes and letting ospf_vertex_free as deconstructor
+	  work per-node.
+	  (ospf_spf_calculate_timer) Trivial optimisation, leave
+	  backbone SPF calculation till last to reduce SPF churn on
+	  VLink updates.
+	* ospf_vty.c: (ospf_find_vl_data) update call to ospf_vl_lookup
+	  (no_ospf_area_vlink_cmd) ditto.
+	  (show_ip_ospf_interface_sub) For Vlinks, the peer address is
+	  more interesting than the output interface.
+
 2006-04-03 Paul Jakma <paul.jakma@sun.com>
 
 	* (general) Fix issues with handling of Vlinks and entries
diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index 52adc42..1264cac 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -931,16 +931,36 @@
   vlink_count--;
 }
 
+/* Look up vl_data for given peer, optionally qualified to be in the
+ * specified area. NULL area returns first found..
+ */
 struct ospf_vl_data *
-ospf_vl_lookup (struct ospf_area *area, struct in_addr vl_peer)
+ospf_vl_lookup (struct ospf *ospf, struct ospf_area *area,
+                struct in_addr vl_peer)
 {
   struct ospf_vl_data *vl_data;
   struct listnode *node;
-
-  for (ALL_LIST_ELEMENTS_RO (area->ospf->vlinks, node, vl_data))
-    if (vl_data->vl_peer.s_addr == vl_peer.s_addr &&
-        IPV4_ADDR_SAME (&vl_data->vl_area_id, &area->area_id))
-      return vl_data;
+  
+  if (IS_DEBUG_OSPF_EVENT)
+    {
+      zlog_debug ("%s: Looking for %s", __func__, inet_ntoa (vl_peer));
+      if (area)
+        zlog_debug ("%s: in area %s", __func__, inet_ntoa (area->area_id));
+    }
+  
+  for (ALL_LIST_ELEMENTS_RO (ospf->vlinks, node, vl_data))
+    {
+      if (IS_DEBUG_OSPF_EVENT)
+        zlog_debug ("%s: VL %s, peer %s", __func__,
+                    vl_data->vl_oi->ifp->name,
+                    inet_ntoa (vl_data->vl_peer));
+      
+      if (area && !IPV4_ADDR_SAME (&vl_data->vl_area_id, &area->area_id))
+        continue;
+      
+      if (IPV4_ADDR_SAME (&vl_data->vl_peer, &vl_peer))
+        return vl_data;
+    }
 
   return NULL;
 }
@@ -1005,14 +1025,15 @@
 
   for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
     {
-      vl_data->out_oi = vp->nexthop->oi;
+      vl_data->nexthop.oi = vp->nexthop->oi;
+      vl_data->nexthop.router = vp->nexthop->router;
       
       if (!IPV4_ADDR_SAME(&voi->address->u.prefix4,
-                          &vl_data->out_oi->address->u.prefix4))
+                          &vl_data->nexthop.oi->address->u.prefix4))
         changed = 1;
         
-      voi->address->u.prefix4 = vl_data->out_oi->address->u.prefix4;
-      voi->address->prefixlen = vl_data->out_oi->address->prefixlen;
+      voi->address->u.prefix4 = vl_data->nexthop.oi->address->u.prefix4;
+      voi->address->prefixlen = vl_data->nexthop.oi->address->prefixlen;
 
       break; /* We take the first interface. */
     }
@@ -1050,19 +1071,16 @@
                                      &rl->link[i].link_data))
                   changed = 1;
                 vl_data->peer_addr = rl->link[i].link_data;
-              if (IS_DEBUG_OSPF_EVENT)
-                zlog_debug ("ospf_vl_set_params: %s peer address is %s\n",
-                               vl_data->vl_oi->ifp->name, 
-                               inet_ntoa(vl_data->peer_addr));
-              return changed;
             }
         }
     }
     
   if (IS_DEBUG_OSPF_EVENT)
-    zlog_debug ("ospf_vl_set_params: %s peer address is %s\n",
+    zlog_debug ("%s: %s peer address: %s, cost: %d,%schanged", __func__,
                vl_data->vl_oi->ifp->name,
-               inet_ntoa(vl_data->peer_addr));
+               inet_ntoa(vl_data->peer_addr),
+               voi->output_cost,
+               (changed ? " " : " un"));
                
   return changed;
 }
@@ -1088,10 +1106,10 @@
     {
       if (IS_DEBUG_OSPF_EVENT)
 	{
-	  zlog_debug ("ospf_vl_up_check(): considering VL, name: %s", 
-		     vl_data->vl_oi->ifp->name);
-	  zlog_debug ("ospf_vl_up_check(): VL area: %s, peer ID: %s", 
-		     inet_ntoa (vl_data->vl_area_id),
+	  zlog_debug ("%s: considering VL, %s in area %s", __func__,
+		     vl_data->vl_oi->ifp->name,
+		     inet_ntoa (vl_data->vl_area_id));
+	  zlog_debug ("%s: peer ID: %s", __func__,
 		     inet_ntoa (vl_data->vl_peer));
 	}
 
diff --git a/ospfd/ospf_interface.h b/ospfd/ospf_interface.h
index 28d95d7..3c75940 100644
--- a/ospfd/ospf_interface.h
+++ b/ospfd/ospf_interface.h
@@ -24,6 +24,7 @@
 #define _ZEBRA_OSPF_INTERFACE_H
 
 #include "ospfd/ospf_packet.h"
+#include "ospfd/ospf_spf.h"
 
 #define IF_OSPF_IF_INFO(I) ((struct ospf_if_info *)((I)->info))
 #define IF_DEF_PARAMS(I) (IF_OSPF_IF_INFO (I)->def_params)
@@ -82,7 +83,7 @@
   struct in_addr    vl_area_id;	   /* Transit area for this VL. */
   int format;                      /* area ID format */
   struct ospf_interface *vl_oi;	   /* Interface data structure for the VL. */
-  struct ospf_interface *out_oi;   /* The interface to go out. */
+  struct vertex_nexthop nexthop;   /* Nexthop router and oi to use */
   struct in_addr    peer_addr;	   /* Address used to reach the peer. */
   u_char flags;
 };
@@ -250,7 +251,7 @@
 					   struct ospf_vl_data *);
 extern struct ospf_vl_data *ospf_vl_data_new (struct ospf_area *,
 					      struct in_addr);
-extern struct ospf_vl_data *ospf_vl_lookup (struct ospf_area *,
+extern struct ospf_vl_data *ospf_vl_lookup (struct ospf *, struct ospf_area *,
 					    struct in_addr);
 extern void ospf_vl_data_free (struct ospf_vl_data *);
 extern void ospf_vl_add (struct ospf *, struct ospf_vl_data *);
diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c
index 5eedbd8..646b625 100644
--- a/ospfd/ospf_route.c
+++ b/ospfd/ospf_route.c
@@ -343,8 +343,9 @@
   if (IS_DEBUG_OSPF_EVENT)
     zlog_debug ("ospf_intra_add_router: LS ID: %s",
 	       inet_ntoa (lsa->header.id));
-
-  ospf_vl_up_check (area, lsa->header.id, v);
+  
+  if (!OSPF_IS_AREA_BACKBONE(area))
+    ospf_vl_up_check (area, lsa->header.id, v);
 
   if (!CHECK_FLAG (lsa->flags, ROUTER_LSA_SHORTCUT))
     area->shortcut_capability = 0;
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index dbd0636..7228d2d 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -46,6 +46,13 @@
 #include "ospfd/ospf_abr.h"
 #include "ospfd/ospf_dump.h"
 
+static void ospf_vertex_free (void *);
+/* List of allocated vertices, to simplify cleanup of SPF.
+ * Not thread-safe obviously. If it ever needs to be, it'd have to be
+ * dynamically allocated at begin of ospf_spf_calculate
+ */
+static struct list vertex_list = { .del = ospf_vertex_free };
+
 /* Heap related functions, for the managment of the candidates, to
  * be used with pqueue. */
 static int
@@ -54,9 +61,25 @@
   struct vertex * v1 = (struct vertex *) node1;
   struct vertex * v2 = (struct vertex *) node2;
   if (v1 != NULL && v2 != NULL )
-    return (v1->distance - v2->distance);
-  else
-    return 0;
+    {
+      /* network vertices must be chosen before router vertices of same
+       * cost in order to find all shortest paths
+       */
+      if ( ((v1->distance - v2->distance) == 0)
+          && (v1->type != v2->type))
+        {
+          switch (v1->type)
+            {
+              case OSPF_VERTEX_NETWORK:
+                return -1;
+              case OSPF_VERTEX_ROUTER:
+                return 1;
+            }
+        }
+      else
+        return (v1->distance - v2->distance);
+    }
+  return 0;
 }
 
 static void
@@ -81,7 +104,8 @@
 }
 
 /* Free the canonical nexthop objects for an area, ie the nexthop objects
- * attached to the first-hop router vertices.
+ * attached to the first-hop router vertices, and any intervening network
+ * vertices.
  */
 static void
 ospf_canonical_nexthops_free (struct vertex *root)
@@ -106,11 +130,14 @@
       
       /* Free child nexthops pointing back to this root vertex */
       for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp))
-        if (vp->parent == root)
+        if (vp->parent == root && vp->nexthop)
           vertex_nexthop_free (vp->nexthop);
     }
 }      
 
+/* TODO: Parent list should be excised, in favour of maintaining only
+ * vertex_nexthop, with refcounts.
+ */
 static struct vertex_parent *
 vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
 {
@@ -128,7 +155,7 @@
 }
 
 static void
-vertex_parent_free (struct vertex_parent *p)
+vertex_parent_free (void *p)
 {
   XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
 }
@@ -148,48 +175,39 @@
   new->distance = 0;
   new->children = list_new ();
   new->parents = list_new ();
+  new->parents->del = vertex_parent_free;
   
+  listnode_add (&vertex_list, new);
+  
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_debug ("%s: Created %s vertex %s", __func__,
+                new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
+                inet_ntoa (new->lsa->id));
   return new;
 }
 
-/* Recursively free the given vertex and all its children 
- * and associated parent and nexthop information
- * Parent should indicate which parent is trying to free this child,
- * NULL parent is only valid for the root vertex.
- */
 static void
-ospf_vertex_free (struct vertex *v, const struct ospf_area *area)
+ospf_vertex_free (void *data)
 {
-  struct listnode *node, *nnode;
-  struct vertex *vc;
+  struct vertex *v = data;
   
-  assert (*(v->stat) == LSA_SPF_IN_SPFTREE);
+  if (IS_DEBUG_OSPF_EVENT)
+    zlog_debug ("%s: Free %s vertex %s", __func__,
+                v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
+                inet_ntoa (v->lsa->id));
   
-  /* recurse down the tree, freeing furthest children first */
-  if (v->children)
-    {
-      for (ALL_LIST_ELEMENTS (v->children, node, nnode, vc))
-        ospf_vertex_free (vc, area);
-      
-      list_delete (v->children);
-      v->children = NULL;
-    }
-  
-  /* The vertex itself can only be freed when the last remaining parent
-   * with a reference to this vertex frees this vertex. Until then, we
-   * just cleanup /one/ parent association (doesnt matter which) -
-   * essentially using the parents list as a refcount.
+  /* There should be no parents potentially holding references to this vertex
+   * Children however may still be there, but presumably referenced by other
+   * vertices
    */
-  if (listcount (v->parents) > 0)
-    {
-      vertex_parent_free (listgetdata (listhead (v->parents)));
-      list_delete_node (v->parents, listhead (v->parents));
-
-      if (listcount (v->parents) > 0)
-        return; /* there are still parent references left */
-    }
+  //assert (listcount (v->parents) == 0);
   
-  list_delete (v->parents);
+  if (v->children)
+    list_delete (v->children);
+  v->children = NULL;
+  
+  if (v->parents)
+    list_delete (v->parents);
   v->parents = NULL;
   
   v->lsa = NULL;
@@ -248,7 +266,7 @@
   struct vertex_parent *vp;
   struct listnode *node;
   
-  assert (v && v->children);
+  assert (v && v->parents);
   
   for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
     {
@@ -264,7 +282,7 @@
 ospf_spf_init (struct ospf_area *area)
 {
   struct vertex *v;
-
+  
   /* Create root node. */
   v = ospf_vertex_new (area->router_lsa_self);
 
@@ -455,7 +473,7 @@
     }
 
   if (v == area->spf)
-    {
+    {      
       /* 16.1.1 para 4.  In the first case, the parent vertex (V) is the
 	 root (the calculating router itself).  This means that the 
 	 destination is either a directly connected network or directly
@@ -556,11 +574,35 @@
                   ospf_spf_add_parent (v, w, nh);
                 }
               else
-                {
-                  zlog_info("ospf_nexthop_calculation(): "
-                            "could not determine nexthop for link");
-                }
+                zlog_info("ospf_nexthop_calculation(): "
+                          "could not determine nexthop for link");
             } /* end point-to-point link from V to W */
+          else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
+            {
+              struct ospf_vl_data *vl_data;
+              
+              /* VLink implementation limitations: 
+               * a) vl_data can only reference one nexthop, so no ECMP
+               *    to backbone through VLinks. Though transit-area 
+               *    summaries may be considered, and those can be ECMP.
+               * b) We can only use /one/ VLink, even if multiple ones
+               *    exist this router through multiple transit-areas.
+               */
+              vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
+              
+              if (vl_data 
+                  && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
+                {
+                  nh = vertex_nexthop_new ();
+                  nh->oi = vl_data->nexthop.oi;
+                  nh->router = vl_data->nexthop.router;
+                  ospf_spf_add_parent (v, w, nh);
+                }
+              else
+                zlog_info("ospf_nexthop_calculation(): "
+                          "vl_data for VL link not found");
+            } /* end virtual-link from V to W */
+          return;
         } /* end W is a Router vertex */
       else
         {
@@ -572,8 +614,11 @@
               nh->oi = oi;
               nh->router.s_addr = 0;
               ospf_spf_add_parent (v, w, nh);
+              return;
             }
         }
+      zlog_info("ospf_nexthop_calculation(): "
+                "Unknown attached link");
       return;
     } /* end V is the root */
   /* Check if W's parent is a network connected to root. */
@@ -616,6 +661,8 @@
    */
   for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
     ospf_spf_add_parent (v, w, vp->nexthop);
+  
+  return;
 }
 
 /* RFC2328 Section 16.1 (2).
@@ -757,8 +804,9 @@
 
           /* Calculate nexthop to W. */
           w->distance = distance;
-	  ospf_nexthop_calculation (area, v, w, l);
-	  pqueue_enqueue (w, candidate);
+          
+          ospf_nexthop_calculation (area, v, w, l);
+          pqueue_enqueue (w, candidate);
 	}
       else if (w_lsa->stat >= 0)
 	{
@@ -1080,8 +1128,10 @@
    */
   ospf_canonical_nexthops_free (area->spf);
   
-  /* Free SPF vertices */
-  ospf_vertex_free (area->spf, area);
+  /* Free SPF vertices, but not the list. List has ospf_vertex_free
+   * as deconstructor.
+   */
+  list_delete_all_node (&vertex_list);
   
   /* Increment SPF Calculation Counter. */
   area->spf_calculation++;
@@ -1089,7 +1139,8 @@
   gettimeofday (&area->ospf->ts_spf, NULL);
 
   if (IS_DEBUG_OSPF_EVENT)
-    zlog_debug ("ospf_spf_calculate: Stop");
+    zlog_debug ("ospf_spf_calculate: Stop. %ld vertices",
+                mtype_stats_alloc(MTYPE_OSPF_VERTEX));
 }
 
 /* Timer for SPF calculation. */
@@ -1114,8 +1165,20 @@
 
   /* Calculate SPF for each area. */
   for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
-    ospf_spf_calculate (area, new_table, new_rtrs);
-
+    {
+      /* Do backbone last, so as to first discover intra-area paths
+       * for any back-bone virtual-links
+       */
+      if (ospf->backbone && ospf->backbone == area)
+        continue;
+      
+      ospf_spf_calculate (area, new_table, new_rtrs);
+    }
+  
+  /* SPF for backbone, if required */
+  if (ospf->backbone)
+    ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
+  
   ospf_vl_shut_unapproved (ospf);
 
   ospf_ia_routing (ospf, new_table, new_rtrs);
diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h
index 50e590d..c1316e4 100644
--- a/ospfd/ospf_spf.h
+++ b/ospfd/ospf_spf.h
@@ -20,6 +20,9 @@
  * 02111-1307, USA.
  */
 
+#ifndef _QUAGGA_OSPF_SPF_H
+#define _QUAGGA_OSPF_SPF_H
+
 /* values for vertex->type */
 #define OSPF_VERTEX_ROUTER  1  /* for a Router-LSA */
 #define OSPF_VERTEX_NETWORK 2  /* for a Network-LSA */
@@ -60,3 +63,5 @@
 extern void ospf_rtrs_free (struct route_table *);
 
 /* void ospf_spf_calculate_timer_add (); */
+
+#endif /* _QUAGGA_OSPF_SPF_H */
diff --git a/ospfd/ospf_vty.c b/ospfd/ospf_vty.c
index 0b74bdf..74361bc 100644
--- a/ospfd/ospf_vty.c
+++ b/ospfd/ospf_vty.c
@@ -722,7 +722,7 @@
       return NULL;
     }
   
-  if ((vl_data = ospf_vl_lookup (area, vl_config->vl_peer)) == NULL)
+  if ((vl_data = ospf_vl_lookup (ospf, area, vl_config->vl_peer)) == NULL)
     {
       vl_data = ospf_vl_data_new (area, vl_config->vl_peer);
       if (vl_data->vl_oi == NULL)
@@ -1074,7 +1074,7 @@
     {
       /* Basic VLink no command */
       /* Thats all folks! - BUGS B. strikes again!!!*/
-      if ((vl_data = ospf_vl_lookup (area, vl_config.vl_peer)))
+      if ((vl_data = ospf_vl_lookup (ospf, area, vl_config.vl_peer)))
 	ospf_vl_delete (ospf, vl_data);
 
       ospf_area_check_free (ospf, vl_config.area_id);
@@ -2736,10 +2736,27 @@
       vty_out (vty, "  Internet Address %s/%d,",
 	       inet_ntoa (oi->address->u.prefix4), oi->address->prefixlen);
 
-      if (oi->connected->destination)
-	 vty_out (vty, " %s %s,",
-		  ((ifp->flags & IFF_POINTOPOINT) ? "Peer" : "Broadcast"),
-		  inet_ntoa (oi->connected->destination->u.prefix4));
+      if (oi->connected->destination || oi->type == OSPF_IFTYPE_VIRTUALLINK)
+        {
+          struct in_addr *dest;
+          const char *dstr;
+          
+          if ((ifp->flags & IFF_POINTOPOINT)
+              || oi->type == OSPF_IFTYPE_VIRTUALLINK)
+            dstr = "Peer";
+          else
+            dstr = "Broadcast";
+          
+          /* For Vlinks, showing the peer address is probably more
+           * informative than the local interface that is being used
+           */
+          if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
+            dest = &oi->vl_data->peer_addr;
+          else
+            dest = &oi->connected->destination->u.prefix4;
+          
+	  vty_out (vty, " %s %s,", dstr, inet_ntoa (*dest));
+        }
 
       vty_out (vty, " Area %s%s", ospf_area_desc_string (oi->area),
 	       VTY_NEWLINE);