A method and apparatus for connecting multiple customer sites over a wide area network (WAN) using an overlay network is described. In one embodiment of the invention, each one of multiple customer edge (CE) routers establishes a Border Gateway Protocol (BGP) session with one or more BGP route reflectors and announces their private IP network prefixes and one or more transport IP addresses to reach that CE router. The BGP route reflector(s) reflect those IP network prefixes and the one or more transport IP addresses to reach that specific CE router to the other CE routers. The CE routers receive those reflected IP network prefixes and the corresponding transport IP address(es) to reach that CE router in which those IP network prefixes belong and register them in their corresponding routing/forwarding data structures. In this way, the CE routers learn how to reach each other.