Method and apparatus for optimizing and scaling control plane traffic in carrier ethernet transport networks

1. A method for determining multiplexer and de multiplexer nodes in a network for multiplexing and de multiplexing connectivity check message (CCM) traffic, the method comprising:

receiving a set of services in the network;

constructing an optimization problem which, when solved, identifies nodes in the network that should be configured as multiplexer nodes to multiplex multiple CCMs into a group CCM and/or as de-multiplexer nodes to de-multiplex a group CCM into multiple CCMs wherein said constructing includes:

defining an objective function that minimizes a total amount of CCM traffic that is sent in the network during a predetermined time period,

defining constraints to restrict the number of times CCM traffic for a given service is merged to ensure that the service recovers from a failure within a predetermined recovery time, and

where said constructing includes defining constraints to prevent nested merging of CCM traffic in the network;

solving, by computer, the optimization problem to obtain a solution; and configuring nodes in the network as multiplexer nodes and/or as de multiplexer nodes according to the solution.

2. The method of claim 1 , wherein the network is an Ethernet network, and wherein a CCM is an Ethernet frame that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

3. The method of claim 1 , wherein a CCM is a Multi-Protocol Label Switching (MPLS) or MPLS Transport Profile (MPLS-TP) packet that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

4. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for determining multiplexer and de-multiplexer nodes in a network for multiplexing and de-multiplexing connectivity check message (CCM) traffic, the method comprising:

receiving a set of services in the network;

constructing an optimization problem which, when solved, identifies nodes in the network that should be configured as multiplexer nodes to multiplex multiple CCMs into a group CCM and/or as de-multiplexer nodes to de-multiplex a group CCM into multiple CCMs wherein said constructing includes:

defining an objective function that minimizes a total amount of CCM traffic that is sent in the network during a predetermined time period, and

defining constraints to restrict the number of times CCM traffic for a given service is merged to ensure that the service routers from a failure within a predetermined recovery time;

wherein said constructing includes defining constraints to prevent nested merging of CCM traffic in the network;

solving the optimization problem to obtain a solution;

and configuring nodes in the network as multiplexer nodes and/or as de-multiplexer nodes according to the solution.

5. The non-transitory computer-readable storage medium of claim 4 , wherein the network is an Ethernet network, and wherein a CCM is an Ethernet frame that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

6. The non-transitory computer-readable storage medium of claim 4 , wherein a CCM is a Multi-Protocol Label Switching (MPLS) or MPLS Transport Profile (MPLS-TP) packet that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

7. An apparatus, comprising:

a processor;

and a non-transitory processor-readable storage medium storing instructions that are capable of being executed by the processor, the instructions comprising:

instructions for receiving a set of services in the network;

instructions for constructing an optimization problem which, when solved, identifies nodes in the network that should be configured as 8 multiplexer nodes to multiplex multiple CCMs into a group CCM and/or as de-multiplexer nodes to de-multiplex a group CCM into multiple CCMs wherein said constructing includes:

defining an objective function that minimizes a total amount of traffic that is sent in the network during a predetermined time period, and defining constraints to restrict the number of times CCM traffic for a given service is merged to ensure that the service recovers from a failure within a predetermined recovery time;

wherein the instructions for constructing include instructions for defining constraints to prevent nested merging of CCM traffic in the network;

instructions for solving the optimization problem to obtain a solution;

and instructions for configuring nodes in the network as multiplexer nodes and/or as de-multiplexer nodes according to the solution.

8. The apparatus of claim 7 , wherein the network is an Ethernet network, and wherein a CCM is an Ethernet frame that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

9. The apparatus of claim 7 , wherein a CCM is a Multi-Protocol Label Switching (MPLS) or MPLS Transport Profile (MPLS-TP) packet that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

10. A method for determining multiplexer and de-multiplexer nodes in a network for multiplexing and de-multiplexing connectivity check message (CCM) traffic, the method comprising:

receiving a set of services in the network;

constructing a tripartite graph H ={S, P, D}, wherein set S includes source nodes for services in the network, set D includes destination nodes for services in the network, and set P includes nodes that correspond to different paths that can be used to route services from their respective source nodes to their respective destination nodes, and wherein each node in set P is assigned a weight which is equal to a product of the length of a path that corresponds to the node and a quantity of services whose route shares the path;

and iteratively performing, by computer, the following operations until no more CCMs corresponding to services can be merged:

selecting a node in set P such that the node has the highest weight and a path corresponding to the node is shared between at least two or more CCMs corresponding to services that have not been merged;

merging CCM traffic of the at least two or more CCMs over the path that corresponds to the selected node in set P;

and removing the at least two or more CCMs from a set of CCMs corresponding to services that can be merged.

11. The method of claim 10 , wherein the network is an Ethernet network, and wherein a CCM is an Ethernet frame that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.

12. The method of claim 10 , wherein a CCM is a Multi-Protocol Label Switching (MPLS) or MPLS Transport Profile (MPLS-TP) packet that is periodically sent from a source node of a service to a destination node of the service to enable the destination node to detect a failure in the network that impacts the service.