A method performed by a provider edge device includes generating pseudo-wire tables based on virtual private local area network service advertisements from other provider edge devices, where the provider edge device services customer edge devices, and establishing pseudo-wires with respect to the other provider edge devices, based on the pseudo-wire tables, where the pseudo-wires include an active pseudo-wire and at least one standby pseudo-wire with respect to each of the other provider edge devices. The method also includes generating and advertising VPLS advertisement to the other provider edge devices, detecting a communication link failure associated with one of the customer edge devices in which the provider edge device services, and determining whether the at least one standby pseudo-wire needs to be utilized because of the communication link failure.