A router configured as an autonomous system border router (ASBR) in a local autonomous system (AS), includes: (1) a control component for communicating and computing routing information, the control component running a Border Gateway Protocol (BGP) and peering with at least one BGP peer device in an outside autonomous system (AS) different from the local AS; and (2) a forwarding component for forwarding packets using forwarding information derived from the routing information computed by the control component, wherein the control component (i) receives reachability information for an external prefix corresponding to a device outside the local AS, and (ii) associates the external prefix, as a BGP next hop (B_NH), an abstract next hop (ANH) that identifies a set of BGP (eBGP) sessions that contains at least one eBGP session over which given external prefix has been learned, each of the at least one eBGP sessions being between the ASBR and a BGP peer device in an AS outside the AS, wherein the device located outside the local AS is reachable via the BGP peer device.