One embodiment of the present invention provides a system that transparently interconnects multiple network links into a single virtual network link. During operation, a Rbridge (Rbridge) within the system receives a packet, wherein the Rbridge belongs to a set of one or more Rbridges that transparently interconnect the multiple network links into the single virtual network link. These Rbridges automatically obtain information specifying which endnodes are located on the multiple network links without the endnodes having to proactively announce their presence to the Rbridges. If a destination for the packet resides on the same virtual network link, the Rbridge routes the packet to the destination. This route can be an optimal path to the destination, and is not constrained to lie along a spanning tree through the set of Rbridges.