Method and apparatus for supporting service function chaining in a communication network

Abstract

A method and apparatus supporting service function chaining in a communication network is provided. Service function chaining requires packets of a service to pass through a defined sequence of service nodes of the network. Traffic engineering support includes defining service segments, determining demands for each service segment, determining flow group conservation constraints using the determined demands, and determining a resource allocation for data links which respects the flow group conservation constraints along with a link capacity constraint. A service-based forwarding operation re-labels packets as they traverse each service segment, and forwards packets toward a destination service node of each service segment.

What is claimed is: 
     
         1 . A method for supporting service-based packet communication in a multi-hop data network, comprising:
 receiving an indication of a set of services, each service of the set of services corresponding to a respective node group comprising: one or more source nodes providing packets belonging to the service; a destination node receiving the packets belonging to the service; and a set of service nodes through which the packets belonging to the service are required to pass, each service utilizing a respective set of service links connecting predetermined pairs of members of the respective node group;   for each service node and each destination node belonging to at least one node group, determining a respective service segment corresponding to members of the sets of service links which connect to said service node or destination node and which are indicative of data flow into said service node or destination node fix at least one of the set of services;   for each service segment, and for each node in the node groups, determining a demand indicative of combined demand of source nodes belonging to services, of the set of services, for which service packets pass through said service segment;   for each service segment, and for each of a plurality of nodes of the data network, including nodes of the node groups, determining a flow group conservation constraint indicative that an amount of resource allocation for data links incoming to the node and for the service segment;   is less than an amount of resource allocation for data links outgoing from the node and for the service segment by a first margin equal to the determined demand indicative of combined demand for the node, when the node is a source node or a service node providing service packets to the service segment;   is greater than the amount of resource allocation for data links outgoing from the node and for the service segment by a second margin equal to a sum of determined demands indicative of combined demands, the sum being over source node is a service node or a destination node receiving service packets from the service segment; and   is similar to the amount of resource allocation for data links outgoing from the node and for the service segment otherwise;   for each of a plurality of data links operatively coupling nodes of the data network, the data links including the service links, determining a respective link capacity constraint;   determining a resource allocation respecting the flow group conservation constraints and the link capacity constraints; and   controlling operation of the data network in accordance with the determined resource allocation.   
     
     
         2 . The method of  claim 1 , wherein controlled operation of the data network comprises packet routing, and wherein routing a packet comprises:
 prior to transmission of the packet from a first service node onto a data link corresponding to a first service segment, labeling the packet with an indication of the first service segment;   forwarding the packet toward a second service node based on the indication of the first service segment; and   upon receipt of the packet at the second service node, re-labeling the packet with an indication of a second service segment to be subsequently traversed by the packet.   
     
     
         3 . The method of  claim 2 , wherein forwarding the packet toward the second service node comprises receiving and forwarding the packet by one or more intermediate data network nodes. 
     
     
         4 . The method of  claim 2 , further comprising forwarding the packet toward a third service node or a destination node based on the indication of the second service segment. 
     
     
         5 . The method of  claim 2 , wherein, during re-labeling of the packet, the indication of the second service segment is determined based on the indication of the first service segment or based on a service identifier carried by the packet. 
     
     
         6 . The method of  claim 1 , wherein the resource allocation is determined so as to satisfy a predetermined network objective directed to one or more of: load balancing; sum rate maximization; and weighted sum rate maximization. 
     
     
         7 . The method of  claim 6 , wherein the resource allocation is determined so as to maximize an objective function corresponding to the predetermined network objective. 
     
     
         8 . The method of  claim 1 , wherein the resource allocation specifies, for a link of the plurality of data links, a proportion of data resources of the link which are to be used in support of a specified one of the set of services traversing the link. 
     
     
         9 . The method of  claim 1 , further comprising creating a graph data structure encoding services of the set of services, and wherein determination of the respective service segment is based on computation performed on the graph data structure. 
     
     
         10 . The method of  claim 1 , wherein at least one service link of the set of service links comprises one or more intermediate routers, one or more data path branches, or a combination thereof. 
     
     
         11 . The method of  claim 1 , wherein controlling operation of the data network comprises providing packet handling instructions to one or more nodes of the network, said one or more nodes including the service nodes. 
     
     
         12 . A traffic engineering controller for a multi-hop data network, comprising:
 an input network interface configured to receive an indication of a set of services, each service of the set of services corresponding to a respective node group comprising: one or more source nodes providing packets belonging to the service; a destination node receiving the packets belonging to the service; and a set of service nodes through which the packets belonging to the service are required to pass, each service utilizing a respective set of service links connecting predetermined pairs of members of the respective node group;   a processor configured to:
 for each service node and each destination node belonging to at least one node group, determine a respective service segment corresponding to members of the sets of service links winch connect to said service node or destination node and which are indicative of data flow into said service node or destination node for at least one of the set of services; 
 for each service segment, and for each node the node groups, determine a demand indicative of combined demand of source nodes belonging to services, of the set of services, for which service packets pass through said service segment; 
 for each service segment, and for each of a plurality of nodes of the data network, including nodes of the node groups, determine a flow group conservation constraint indicative that an amount of resource allocation for data links incoming to the node and for the service segment:
 is less than an amount of resource allocation for data links outgoing from the node and for the service segment by a first margin equal to the determined demand indicative of combined demand for the node, when the node is a source node or a service node providing service packets to the service segment; 
 is greater than the amount of resource allocation for data links outgoing from the node and for the service segment by a second margin equal to a sum of determined demands indicative of combined demands, the sum being over source nodes or service nodes providing service packets to the service segment, when the node is a service node or a destination node receiving service packets from the service segment; and 
 is similar to the amount of resource allocation for data links outgoing from the node and for the service segment otherwise; 
 
 for each of a plurality of data links operatively coupling nodes of the data network, the data links including the service links, determine a respective link capacity constraint; and 
 determine a resource allocation respecting the flow group conservation constraints and the link capacity constraints; and 
   an output network interface configured to transmit signals for controlling operation of the data network in accordance with the determined resource allocation.   
     
     
         13 . The traffic engineering controller of  claim 12 , wherein the processor is configured to determine the resource allocation so as to satisfy a predetermined network objective directed to one or more of: load balancing; sum rate maximization; and weighted sum rate maximization. 
     
     
         14 . The traffic engineering controller of  claim 13 , wherein the processor is configured to determine the resource allocation so as to maximize an objective function corresponding to the predetermined network objective. 
     
     
         15 . The traffic engineering controller of  claim 12 , wherein the resource allocation specifies, for a link of the plurality of data links, a proportion of data resources of the link which are to be used in support of a specified one of the set of services traversing the link. 
     
     
         16 . The traffic engineering controller of  claim 12 , wherein the processor is further configured to create a graph data structure encoding services of the set of services, and wherein determination of the respective service segment is based on computation performed on the graph data structure. 
     
     
         17 . The traffic engineering controller of  claim 12 , wherein at least one service link of the set of service links comprises one or more intermediate routers, one or more data path branches, or a combination thereof. 
     
     
         18 . The traffic engineering controller of  claim 12 , wherein controlling operation of the data network comprises providing packet handling instructions to one or more nodes of the network, said one or more nodes including the service nodes. 
     
     
         19 . A router for routing a packet in a multi-hop data network, the packet belonging to a service, the service corresponding to a set of service nodes through which the packet is required to pass, the router communicatively coupled to one of the set of service nodes and comprising a data packet handling interface configured to:
 receive the packet and process a label, carried by the packet, comprising an indication of a first service segment traversed by the data packet;   adjust the label to include an indication of a second service segment to be traversed by the packet upon transmission of the packet from the router; and   transmit the packet toward a further service node of the set of service nodes based on the indication of the second service segment.   
     
     
         20 . The router of  claim 19 , wherein transmitting the packet toward the further service node comprises transmitting the packet to an intermediate router located between the router and the further service node. 
     
     
         21 . The router of  claim 19 , further configured to determine the indication of the further service segment based on the indication of the first service segment or based on a service identifier carried by the packet. 
     
     
         22 . The router of  claim 19 , further comprising an input network interface configured to receive the indication of the second service segment from a traffic engineering controller for inclusion in the label. 
     
     
         23 . The router of  claim 19 , further configured to determine the indication of the second service segment based on the indication of the first service segment, according to service-based label switching information received from a traffic engineering controller via an input network interface of the router. 
     
     
         24 . The router of  claim 19 , further comprising an input network interface configured to receive service-based forwarding information from a traffic engineering controller, wherein transmitting the packet is based on the service-based forwarding information. 
     
     
         25 . The router of  claim 19 , wherein the packet is routed according to destination-based routing based on the label. 
     
     
         26 . A method for supporting service-based packet communication in a multi-hop data network, comprising:
 providing an indication of a plurality of service segments, each service segment corresponding to a set of service links via which data flows into a service node or destination node, said data corresponding to a service requiring the data to pass through a specified sequence of service nodes;   determining a plurality of demand values corresponding respectively to the plurality of service segments, each demand value indicative of a combined demand of source nodes belonging to services for which service packets pass through the respective service segment; and   performing a traffic engineering optimization calculation with all service segments present and in consideration of the determined plurality of demand values.