METHODS AND APPARATUS TO IMPLEMENT A PARTIAL MESH VIRTUAL PRIVATE LOCAL AREA NETWORK SERVICE

• US 20090252061A1
• Filed: 04/08/2008
• Published: 10/08/2009
• Est. Priority Date: 04/08/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Knowledge Ventures, L.P. (AT&T, Inc.)
• Inventors: Ou, Canhui, Spencer, Thomas, Small, David
• Granted Patent: US 8,743,740 B2
• Time in Patent Office: Days
• 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 (VPLS) network, the method comprising:

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.

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

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

4. A method as defined in claim 1 wherein decomposing the partial mesh topology of connections into the plurality of cliques comprises including each connection in only one clique.

5. A method as defined in claim 1 further comprising implementing the union of the plurality of cliques by associating a unique VPLS identifier with each clique in the plurality of cliques.

6. A method as defined in claim 1 wherein the VPLS network further comprises a plurality of attachment circuits, wherein each attachment circuit interconnects a customer edge device with a respective one of the plurality of provider edge devices.

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

8. A method as defined in claim 1 wherein decomposing the partial mesh topology into the plurality of cliques comprises:

determining a degree associated with each provider edge device comprising the VPLS network, wherein the degree of a particular provider edge device corresponds to a number of connections interconnecting with the particular provider edge device;

searching for a first clique in the desired partial mesh topology based on the largest degree determined for the plurality of provider edge devices; and

creating the first clique to correspond with a first subset of the plurality of provider edge devices forming a largest full mesh topology in the desired partial mesh topology.

9. A method as defined in claim 8 wherein the first clique corresponds to a first subset of connections included in the desired partial mesh topology, and wherein the method further comprises:

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

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

10. A method as defined in claim 1 wherein the plurality of cliques comprises a set of cliques each having a rank equal to two and at least one higher ranking clique, wherein the rank of a particular clique corresponds to a number of provider edge devices included in the clique, and wherein decomposing the partial mesh topology into the plurality of cliques comprises:

determining a degree associated with each provider edge device comprising the VPLS, wherein the degree of a particular provider edge device corresponds to a number of connections interconnecting with the particular provider edge device;

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

determining the at least one higher ranking clique from a topology of remaining connections formed by removing each connection associated with each provider edge device whose degree equals one from the desired partial mesh topology of connections.

11-13. -13. (canceled)

14. A system implementing a partial mesh virtual private local area network service (VPLS) network according to a desired partial mesh topology of connections, the system comprising:

a first clique comprising a first full mesh topology of connections for interconnecting a first subset of a plurality of provider edge devices comprising the VPLS network; and

a second clique comprising a second full mesh topology of connections for interconnecting a second subset of the plurality of provider edge devices comprising the VPLS network, wherein the desired partial mesh topology of connections comprising the VPLS includes the first clique and the second clique.

17. A system as defined in claim 14 wherein no connection in the desired partial mesh topology is included in both the first clique and the second clique.

19. A system as defined in claim 14 further comprising a first plurality of attachment circuits to interconnect a first plurality of customer edge devices with the first subset of the plurality of provider edge devices based on a first VPLS identifier defining a first VPLS instance, and a second plurality of attachment circuits to interconnect a second plurality of customer edge devices with the second subset of the plurality of provider edge devices based on a second VPLS identifier defining a second VPLS instance.

15-16. -16. (canceled)

18. (canceled)

20. (canceled)

21. A method to implement a partial mesh virtual private local area network service (VPLS) network, the method comprising:

identifying a desired partial mesh topology of connections for interconnecting a plurality of provider edge devices comprising the VPLS network; and

implementing the desired partial mesh topology of connections using a route reflector to advertise signaling information received from a first provider edge device in the plurality of provider edge devices only to one or more second provider edge devices in the plurality of provider edge devices that are adjacent to the first provider edge device according to the desired partial mesh topology.

22. A method as defined in claim 21 wherein the signaling information comprises a demultiplexor label identifying the VPLS network and the first provider edge device.

23. A method as defined in claim 21 wherein the connections implemented by the route reflector are based on a border gateway protocol.

24. A method as defined in claim 21 further comprising maintaining a table specifying adjacencies between provider edge devices based on the desired partial mesh topology.

25. A method as defined in claim 24 wherein the table includes an entry specifying a prohibited adjacency between a pair of provider edge devices.

26. A method as defined in claim 24 wherein the table includes an entry specifying an allowed adjacency between a pair of provider edge devices.

27. A method as defined in claim 24 wherein the table includes an entry specifying a unidirectional adjacency between a pair of provider edge devices.

28-40. -40. (canceled)