Described are a network, computer program product, and method of distributing routing information for a virtual private network (VPN) application through a packet-switched network (PSN) having fully meshed provider edge (PE) routers through Provider Backbone Bridge (PBB) tunnels. A PE router is configured to participate in a VPN and to run a BGP (Border Gateway Protocol) as an auto-discovery process for finding one or more other PE routers participating in the VPN. The VPN is associated with a PBB tunnel. A service instance identifier (I-SID) is assigned to the VPN. The PE router advertises membership in the VPN by including the I-SID assigned to the VPN in a BGP message issued during the auto-discovery process.