A layer-2 virtual-private-network (L2-VPN) service with automatic discovery and connection establishment is provided within a wide-area, multiple-autonomous-system (AS) network according to one of two approaches. In the first approach, inter-AS tunnels are used to connect pairs of provider edge (PE) routers of different ASes, and the PE routers then establish signaling connections to each other which are used to create pseudowires that implement the layer-2 connectivity. A second approach utilizes so-called “pseudowire switching” in which separate pseudowires are created within each AS and between ASes, and then the separate pseudowires are stitched together to form end-to-end connections. The first approach has the benefit of transparent operation provided by the tunnel, while the second approach requires fewer inter-AS signaling connections.