diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 316fa5a..c424dd1 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -109,8 +109,12 @@ bgp_info_extra_free (struct bgp_info_extra **extra)
       
       (*extra)->damp_info = NULL;
       
+      if ((*extra)->attr)
+        bgp_attr_unintern(&((*extra)->attr));
+
+      (*extra)->attr = NULL;
+
       XFREE (MTYPE_BGP_ROUTE_EXTRA, *extra);
-      
       *extra = NULL;
     }
 }
@@ -1602,7 +1606,8 @@ bgp_process_main (struct work_queue *wq, void *data)
   struct bgp_info *old_select;
   struct bgp_info_pair old_and_new;
   struct listnode *node, *nnode;
-  struct peer *peer;
+  struct peer *peer, *log_peer = NULL;
+  struct attr *attr;
   
   /* Best path selection. */
   bgp_best_selection (bgp, rn, &bgp->maxpaths[afi][safi], &old_and_new);
@@ -1638,6 +1643,8 @@ bgp_process_main (struct work_queue *wq, void *data)
   for (ALL_LIST_ELEMENTS (bgp->peer, node, nnode, peer))
     {
       bgp_process_announce_selected (peer, new_select, rn, afi, safi);
+      if (log_peer == NULL)
+          log_peer = peer;
     }
 
   /* FIB update. */
@@ -1646,15 +1653,24 @@ bgp_process_main (struct work_queue *wq, void *data)
     {
       if (new_select 
 	  && new_select->type == ZEBRA_ROUTE_BGP 
-	  && new_select->sub_type == BGP_ROUTE_NORMAL)
+	  && new_select->sub_type == BGP_ROUTE_NORMAL) {
 	bgp_zebra_announce (p, new_select, bgp, safi);
+      }
       else
 	{
 	  /* Withdraw the route from the kernel. */
 	  if (old_select 
 	      && old_select->type == ZEBRA_ROUTE_BGP
-	      && old_select->sub_type == BGP_ROUTE_NORMAL)
-	    bgp_zebra_withdraw (p, old_select, safi);
+	      && old_select->sub_type == BGP_ROUTE_NORMAL) {
+            if (CHECK_FLAG (old_select->flags, BGP_INFO_NEW_NHOP_INVALID)) {
+              attr = old_select->attr;
+              old_select->attr = (bgp_info_extra_get(old_select))->attr;
+	      bgp_zebra_withdraw (p, old_select, safi);
+              old_select->attr = attr;
+            } else {
+	      bgp_zebra_withdraw (p, old_select, safi);
+            }
+          }
 	}
     }
     
@@ -2105,7 +2121,7 @@ bgp_update_main (struct peer *peer, struct prefix *p, struct attr *attr,
   struct bgp *bgp;
   struct attr new_attr;
   struct attr_extra new_extra;
-  struct attr *attr_new;
+  struct attr *attr_new, *saved_attr;
   struct bgp_info *ri;
   struct bgp_info *new;
   const char *reason;
@@ -2302,8 +2318,9 @@ bgp_update_main (struct peer *peer, struct prefix *p, struct attr *attr,
 	    bgp_damp_withdraw (ri, rn, afi, safi, 1);  
 	}
 	
-      /* Update to new attribute.  */
-      bgp_attr_unintern (&ri->attr);
+      /* Update to new attribute.  Save the old attr to be freed after we decide
+         the new attribute has next hop that's reachable or not */
+      saved_attr = ri->attr;
       ri->attr = attr_new;
 
       /* Update MPLS tag.  */
@@ -2318,10 +2335,11 @@ bgp_update_main (struct peer *peer, struct prefix *p, struct attr *attr,
 	  ret = bgp_damp_update (ri, rn, afi, safi);
 	  if (ret == BGP_DAMP_SUPPRESSED)
 	    {
-	      bgp_unlock_node (rn);
-	      return 0;
-	    }
-	}
+              bgp_attr_unintern (&saved_attr);
+              bgp_unlock_node (rn);
+              return 0;
+            }
+        }
 
       /* Nexthop reachability check. */
       if ((afi == AFI_IP || afi == AFI_IP6)
@@ -2331,13 +2349,26 @@ bgp_update_main (struct peer *peer, struct prefix *p, struct attr *attr,
 	      || (peer->sort == BGP_PEER_EBGP && peer->ttl != 1)
 	      || CHECK_FLAG (peer->flags, PEER_FLAG_DISABLE_CONNECTED_CHECK)))
 	{
-	  if (bgp_nexthop_lookup (afi, peer, ri, NULL, NULL))
-	    bgp_info_set_flag (rn, ri, BGP_INFO_VALID);
-	  else
-	    bgp_info_unset_flag (rn, ri, BGP_INFO_VALID);
-	}
-      else
+          if (bgp_nexthop_lookup (afi, peer, ri, NULL, NULL)) {
+            bgp_info_set_flag (rn, ri, BGP_INFO_VALID);
+            bgp_attr_unintern (&saved_attr);
+            bgp_info_unset_flag (rn, ri, BGP_INFO_NEW_NHOP_INVALID);
+          } else {
+            bgp_info_unset_flag (rn, ri, BGP_INFO_VALID);
+            bgp_info_set_flag (rn, ri, BGP_INFO_NEW_NHOP_INVALID);
+            if (!ri->extra)
+              ri->extra = bgp_info_extra_new();
+            else
+              if (ri->extra->attr)
+                bgp_attr_unintern(&(ri->extra->attr));
+            ri->extra->attr = saved_attr;
+          }
+        }
+      else {
         bgp_info_set_flag (rn, ri, BGP_INFO_VALID);
+        bgp_attr_unintern (&saved_attr);
+        bgp_info_unset_flag (rn, ri, BGP_INFO_NEW_NHOP_INVALID);
+      }
 
       /* Process change. */
       bgp_aggregate_increment (bgp, p, ri, afi, safi);
diff --git a/bgpd/bgp_route.h b/bgpd/bgp_route.h
index 3d2eea5..60c9b54 100644
--- a/bgpd/bgp_route.h
+++ b/bgpd/bgp_route.h
@@ -40,6 +40,9 @@ struct bgp_info_extra
 
   /* MPLS label.  */
   u_char tag[3];  
+
+  /* Attribute structure. Only for invalid next hop update case  */
+  struct attr *attr;
 };
 
 struct bgp_info
@@ -82,6 +85,7 @@ struct bgp_info
 #define BGP_INFO_COUNTED	(1 << 10)
 #define BGP_INFO_MULTIPATH      (1 << 11)
 #define BGP_INFO_MULTIPATH_CHG  (1 << 12)
+#define BGP_INFO_NEW_NHOP_INVALID (1 << 13)
 
   /* BGP route type.  This can be static, RIP, OSPF, BGP etc.  */
   u_char type;