A method of identifying network paths comprising: building a path verification message for transmission from an originator to a destination, wherein the originator is a local customer edge, CE, router and the destination is a remote CE router, the originator and destination interconnected by a path including at least one provider edge, PE, router, the PE router coupled to a plurality of PE routers collectively defining a core network, the core network employing the path verification message for transmitting the identity of the originator to the destination, the remote CE router being ingress point to a remote VPN subnet; storing, at the originator, the identity of the originator in the path verification message, the message being stored in a nonvolatile manner undisturbed by successive routing operations, the path verification message including attributes according to a predetermined path verification protocol and a reachability flag, wherein the attributes are for transporting control information between the PE and CE routers, the attributes including an extended community field indicative of the originator of the path verification message, the attributes further including a reachability flag indicative of either a prefix based or a CE based reachability check according to determining, by the originator, if other CEs receiving the path verification message are to employ a CE based reachability check or a prefix reachability check; transmitting, from the originator, the path verification message to the destination via the at least one PE router; receiving, at the destination, if the transmitting was successful, the path verification message; recovering, at the destination, from the received path verification message, the identity of the transmitting originator by recovering the stored identity; and designating at the destination, a path between the destination and the originator as a verified path based on the recovered identity of the originator, wherein if the reachability flag is set to per CE reachability, then the destination associates the originating CE as a verified CE-CE path from the information in the extended community attribute, and if the reachability flag is set to a prefix based check, then the destination identifies a set of prefixes within the remote VPN subnet reachable via the receiving CE. building a path verification message for transmission from an originator to a destination, wherein the originator is a local customer edge, CE, router and the destination is a remote CE router, the originator and destination interconnected by a path including at least one provider edge, PE, router, the PE router coupled to a plurality of PE routers collectively defining a core network, the core network employing the path verification message for transmitting the identity of the originator to the destination, the remote CE router being ingress point to a remote VPN subnet; storing, at the originator, the identity of the originator in the path verification message, the message being stored in a nonvolatile manner undisturbed by successive routing operations, the path verification message including attributes according to a predetermined path verification protocol and a reachability flag, wherein the attributes are for transporting control information between the PE and CE routers, the attributes including an extended community field indicative of the originator of the path verification message, the attributes further including a reachability flag indicative of either a prefix based or a CE based reachability check according to determining, by the originator, if other CEs receiving the path verification message are to employ a CE based reachability check or a prefix reachability check; transmitting, from the originator, the path verification message to the destination via the at least one PE router; receiving, at the destination, if the transmitting was successful, the path verification message; recovering, at the destination, from the received path verification message, the identity of the transmitting originator by recovering the stored identity; and designating at the destination, a path between the destination and the originator as a verified path based on the recovered identity of the originator, wherein if the reachability flag is set to per CE reachability, then the destination associates the originating CE as a verified CE-CE path from the information in the extended community attribute, and if the reachability flag is set to a prefix based check, then the destination identifies a set of prefixes within the remote VPN subnet reachable via the receiving CE.