Patent ID: 8743740

Claim:
A method to implement a partial mesh virtual private local area network service network, the method comprising: identifying a partial mesh topology of pseudowires for interconnecting a plurality of provider edge devices that are to implement the partial mesh virtual private local area network service network; electronically decomposing the partial mesh topology into cliques of pseudowires, a union of the cliques of pseudowires implementing the partial mesh topology and being carried by a full mesh of outer tunnels interconnecting the plurality of provider edge devices, each clique comprising a respective full mesh topology of pseudowires for interconnecting a respective subset of the plurality of provider edge devices, each clique having no pseudowire in more than one of the cliques, the cliques including a first clique that is a largest clique in the partial mesh topology, the cliques also including a second clique that is a largest clique in a topology formed by removing the first clique from the partial mesh topology; and interconnecting a customer edge device to a first provider edge device included in the first clique and the second clique using first and second attachment circuits, the first attachment circuit associated with the first clique by a first demultiplexor label, the second attachment circuit associated with the second clique by a second demultiplexor label, both the first and second attachment circuits to carry first data sent from the customer edge device to the first provider edge device, the first data to be further routed through the partial mesh virtual private local area network service network by either the first clique or the second clique based on a destination of the first data, wherein a rank of the first clique corresponds to a number of provider edge devices included in the first clique, and decomposing the partial mesh topology comprises: determining respective degrees for respective ones of the provider edge devices, a degree for a respective one of the provider edge devices corresponding to a number of pseudowires interconnecting with the respective one of the provider edge devices in the partial mesh topology; determining a largest degree among the respective degrees for the respective ones of the provider edge devices; performing a first search for the first clique by (1) setting search rank to be one greater than the largest degree and (2) searching for any clique in the partial mesh topology having a respective rank equal to the search rank; and if the first search is unsuccessful, iteratively reducing the search rank and performing a subsequent search until the first clique is found.