METHOD AND SYSTEM FOR ROUTING A NETWORK FUNCTION CHAIN
First Claim
1. A method implemented in an electronic device coupled to a network including a plurality of network elements, wherein traffic flows of the network pass through network function chains, wherein each network function is associated with at least one network element, the method comprising:
- for each of a plurality of network functions of a network function chain, generating a subgraph, wherein a representation of each of the plurality of network elements is split into two vertexes, and an edge is added between the split two vertexes of the representation of each network element that hosts that network function of the subgraph;
ordering the subgraphs according to an order of the plurality of network functions of the network function chain;
connecting the ordered subgraphs to form a graph, wherein for each ordered subgraph except the last ordered subgraph, each vertex with an edge in the ordered subgraph being connected with an edge to another vertex with an edge in the next ordered subgraph, each connection including all paths of the network between a pair of network elements represented by the vertexes connected with the edge, and wherein each edge in the graph includes a cost measure;
determining vertexes of a representation of a source network element and a representation of a destination network element in the graph; and
selecting a path from the vertex of the representation of the source network element to the vertex of the representation of the destination network element in the graph to identify a route through the plurality of network functions of the network function chain, wherein each edge of the path is selected based on at least its cost measure.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, a request is received to route a network function chain. For each contained network function, a subgraph is generated, where each of a plurality of network elements in a network is split into two vertexes, and one edge is added between the split two vertexes for each network element that hosts that network function of the subgraph. The subgraphs are ordered and connected through connecting each vertex with one edge to another vertex with one edge in a subsequent subgraph to form a graph, where the connection is included in a representation of the network. Each edge includes a cost measure. The method selects a path from the vertex representing the source network element to the vertex representing the destination network element in the graph to route the network function chain, where each edge of the path is selected based on at least its cost measure.
128 Citations
20 Claims
-
1. A method implemented in an electronic device coupled to a network including a plurality of network elements, wherein traffic flows of the network pass through network function chains, wherein each network function is associated with at least one network element, the method comprising:
-
for each of a plurality of network functions of a network function chain, generating a subgraph, wherein a representation of each of the plurality of network elements is split into two vertexes, and an edge is added between the split two vertexes of the representation of each network element that hosts that network function of the subgraph; ordering the subgraphs according to an order of the plurality of network functions of the network function chain; connecting the ordered subgraphs to form a graph, wherein for each ordered subgraph except the last ordered subgraph, each vertex with an edge in the ordered subgraph being connected with an edge to another vertex with an edge in the next ordered subgraph, each connection including all paths of the network between a pair of network elements represented by the vertexes connected with the edge, and wherein each edge in the graph includes a cost measure; determining vertexes of a representation of a source network element and a representation of a destination network element in the graph; and selecting a path from the vertex of the representation of the source network element to the vertex of the representation of the destination network element in the graph to identify a route through the plurality of network functions of the network function chain, wherein each edge of the path is selected based on at least its cost measure. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method implemented in an electronic device coupled to a network including a plurality of network elements, wherein traffic flows of the network pass through network function chains, wherein each network function is associated with at least one network element, the method comprising:
-
calculating a set of lowest cost paths for each pair of network elements of the plurality of network elements, wherein each lowest cost path includes a cost measure; for each of a plurality of network functions of a network function chain, generating a subgraph, wherein a representation of each of the plurality of network elements is split into two vertexes, and an edge is added between the split two vertexes of the representation of each network element that hosts that network function of the subgraph; ordering the subgraphs according to an order of the plurality of network functions of the network function chain; connecting the ordered subgraphs to form a graph, wherein for each ordered subgraph except the last ordered subgraph, each vertex with an edge in the ordered subgraph is connected, with at least one edge, to another vertex with an edge in the next ordered subgraph, wherein each connection between vertexes in different ordered subgraphs is associated with at least one path but no more than the calculated set of lowest cost paths for the pair of network elements with representation vertexes connected by the at least one edge, and wherein each edge in the graph includes a cost measure; determining vertexes of a representation of a source network element and a representation of a destination network element in the graph; and selecting a path from the vertex of the representation of the source network element to the vertex of the representation of the destination network element in the graph to identify a route through the plurality of network functions of the network function chain, wherein each edge of the path is selected based on at least its cost measure. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations in an electronic device coupled to a network including a plurality of network elements, wherein traffic flows of the network pass through network function chains, wherein each network function is associated with at least one network element, the operations comprising:
-
for each of a plurality of network functions of a network function chain, generating a subgraph, wherein a representation of each of the plurality of network elements is split into two vertexes, and an edge is added between the split two vertexes of the representation of each network element that hosts that network function of the subgraph; ordering the subgraphs according to an order of the plurality of network functions of the network function chain; connecting the ordered subgraphs to form a graph, wherein for each ordered subgraph except the last ordered subgraph, each vertex with an edge in the ordered subgraph being connected with an edge to another vertex with an edge in the next ordered subgraph, each connection including all paths of the network between a pair of network elements represented by the vertexes connected with the edge, and wherein each edge in the graph includes a cost measure; determining vertexes of the representation of a source network element and a representation of a destination network element in the graph; and selecting a path from the vertex of the representation of the source network element to the vertex of the representation of the destination network element in the graph to identify a route through the plurality of network functions of the network function chain, wherein each edge of the path is selected based on at least its cost measure. - View Dependent Claims (18)
-
-
19. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations in an electronic device coupled to a network including a plurality of network elements, wherein traffic flows of the network pass through network function chains, wherein each network function is associated with at least one network element, the operations comprising:
-
calculating a set of lowest cost paths for each pair of network elements of the plurality of network elements, wherein each lowest cost path includes a cost measure; for each of a plurality of network functions of a network function chain, generating a subgraph, wherein a representation of each of the plurality of network elements is split into two vertexes, and an edge is added between the split two vertexes of the representation of each network element that hosts that network function of the subgraph; ordering the subgraphs according to an order of the plurality of network functions of the network function chain; connecting the ordered subgraphs to form a graph, wherein for each ordered subgraph except the last ordered subgraph, each vertex with an edge in the ordered subgraph is connected, with at least one edge, to another vertex with an edge in the next ordered subgraph, wherein each connection between vertexes in different ordered subgraphs is associated with at least one path but no more than the calculated set of lowest cost paths for the pair of network elements with representation vertexes connected by the at least one edge, and wherein each edge in the graph includes a cost measure; determining vertexes of a representation of a source network element and a representation of a destination network element in the graph; and selecting a path from the vertex of the representation of the source network element to the vertex of the representation of the destination network element in the graph to identify a route through the plurality of network functions of the network function chain, wherein each edge of the path is selected based on at least its cost measure. - View Dependent Claims (20)
-
Specification