Methods and apparatus to implement a partial mesh virtual private local area network service

• US 8,743,740 B2
• Filed: 04/08/2008
• Issued: 06/03/2014
• Est. Priority Date: 04/08/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Small, David, Spencer, Thomas, Ou, Canhui
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): YOUNG, STEVE R
• Application Number:
  US12/099,553
• Publication Number:
  US 20090252061A1
• Time in Patent Office: 2,247 Days
• Field of Search: None
• US Class Current: 370/255
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272

Abstract

Methods and apparatus to implement a partial mesh virtual private local area network service are disclosed. An example method to implement a partial mesh virtual private local area network service (VPLS) network disclosed herein comprises identifying a desired partial mesh topology of connections for interconnecting a plurality of provider edge devices comprising the VPLS network, and decomposing the partial mesh topology into a plurality of cliques, wherein each clique comprises a respective full mesh topology of connections for interconnecting a respective subset of the plurality of provider edge devices, and wherein a union of the plurality of cliques implements the desired partial mesh topology.

Claims

1. 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.

2. The method as defined in claim 1 wherein each pseudowire of the partial mesh topology corresponds to a pseudowire interconnecting two provider edge devices.

3. The method as defined in claim 1 wherein at least one pseudowire of the partial mesh topology is established based on at least one of a label distribution protocol or a border gateway protocol.

4. The method as defined in claim 1 wherein decomposing the partial mesh topology comprises including each pseudowire in only one clique.

5. The method as defined in claim 1 further comprising implementing the union of the cliques by associating a unique virtual private local area network service identifier with each of the cliques.

6. The method as defined in claim 1 wherein the partial mesh virtual private local area network service network is to be implemented by a plurality of attachment circuits including the first and second attachment circuits, and each attachment circuit is to interconnect a customer edge device with a respective one of the plurality of provider edge devices.

7. The method as defined in claim 6 further comprising implementing the union of the cliques by associating at least two cliques with at least one of the plurality of attachment circuits.

8. The method as defined in claim 1 wherein the first clique corresponds to a first subset of the pseudowires included in the partial mesh topology, and the method further comprises:

forming a topology of remaining pseudowires by removing the first subset of pseudowires from the partial mesh topology; and

creating the second clique to correspond to a second subset of the plurality of provider edge devices forming a largest full mesh topology in the topology of remaining pseudowires.

9. The method as defined in claim 1 wherein the cliques comprise a set of cliques having respective ranks equal to two and at least one higher ranking clique, and decomposing the partial mesh topology into the cliques comprises:

creating a separate rank two clique for each connection associated with each provider edge device whose degree equals one; and

determining the first clique from a topology of remaining pseudowires formed by removing each pseudowire associated with each provider edge device whose degree equals one from the partial mesh topology of pseudowire.

10. A tangible machine readable memory storing machine readable instructions which, when executed, cause a machine to perform operations comprising:

identifying a partial mesh topology of pseudowires for interconnecting a plurality of provider edge devices that are to implement a partial mesh virtual private local area network service network;

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.

11. The tangible machine readable memory as defined in claim 10 wherein each pseudowire of the partial mesh topology corresponds to a pseudowire interconnecting two provider edge devices.

12. The tangible machine readable memory as defined in claim 10 wherein at least one pseudowire of the partial mesh topology is established based on at least one of a label distribution protocol or a border gateway protocol.

13. The tangible machine readable memory as defined in claim 10 wherein decomposing the partial mesh topology comprises including each pseudowire in only one clique.

14. The tangible machine readable memory as defined in claim 10 wherein the operations further comprise implementing the union of the cliques by associating a unique virtual private local area network service identifier with each of the cliques.

15. The tangible machine readable memory as defined in claim 10 wherein the partial mesh virtual private local area network service network is to be implemented by a plurality of attachment circuits including the first and second attachment circuits, and each attachment circuit is to interconnect a customer edge device with a respective one of the plurality of provider edge devices.

16. The tangible machine readable memory as defined in claim 15 wherein the operations further comprise implementing the union of the cliques by associating at least two cliques with at least one of the plurality of attachment circuits.