Network service computation system

Abstract

A method and system for implementing a network service computation system uses distributed graph processing at a plurality of network controllers corresponding to a plurality of network domains. Each network controller may manage and maintain a network graph for its respective network domain. Each network controller many communicate with nodes (or vertices) in its respective network domain, while the network controllers may communicate with each other for path discovery and computation purposes.

What is claimed is: 
     
       1. A method, comprising:
 receiving a network request at a first network controller, the network request specifying a source vertex and a destination vertex, wherein the source vertex is located in a first network domain managed by the first network controller, and wherein the destination vertex is located in a second network domain managed by a second network controller; 
 performing distributed graph processing at a plurality of network controllers, including the first network controller and the second network controller, corresponding to a plurality of network domains to determine a network path between the source vertex and the destination vertex, the distributed graph processing including:
 within each network domain, executing a plurality of supersteps, wherein each superstep includes identifying a minimum path distance between each vertex in the network domain and the source vertex; 
 sending, subsequent to each superstep, a controller message among the plurality of network controllers, wherein the controller message includes a first field specifying a sending vertex identifier, a second field specifying a target vertex identifier, and a third field specifying the minimum path distance from the source vertex to a target vertex corresponding to the target vertex identifier, wherein a sending vertex corresponding to the sending vertex identifier is included in a network domain of a network controller sending the controller message and the target vertex is included in a network domain of a network controller receiving the controller message; 
 repeating, after each superstep, sending a controller message until all network paths between the source vertex and the destination vertex are recorded, wherein the path information does not change based on a given network topology among the plurality of network domains; 
 recording, by each network controller for each vertex in the network domain corresponding to the network controller, path information comprising: the minimum path distance from the source vertex to the vertex; and a parent vertex identifier for a parent vertex from the vertex resulting in the minimum path distance to the source vertex; 
 receiving new path information for the respective vertex after path information is recorded for a respective vertex; and 
 discarding new path information for the respective vertex when the new path information for the respective vertex specifies a value for the minimum path distance greater than the minimum path distance recorded in the path information; and 
 
 providing at least one network service to at least one customer of a service provider using an output path, wherein the output path is computed based on the path information. 
 
     
     
       2. The method of  claim 1 , wherein the distributed graph processing begins with the first network controller at the first network domain. 
     
     
       3. The method of  claim 1 , wherein the distributed graph processing begins with the second network controller at the second network domain. 
     
     
       4. The method of  claim 1 , further comprising:
 aggregating the path information corresponding to the minimum path distance; and 
 based on the path information aggregated, computing an output path spanning a minimum distance between the source vertex and the destination vertex. 
 
     
     
       5. The method of  claim 4 , wherein the aggregating the path information further comprises:
 aggregating path information only for border vertices for each network domain. 
 
     
     
       6. The method of  claim 4 , wherein the aggregating the path information is performed by one of: the first network controller and the second network controller, and further comprising:
 responding, by the first network controller, to the network request with the output path. 
 
     
     
       7. The method of  claim 1 , wherein the plurality of network controllers are software-defined network controllers. 
     
     
       8. A network system comprising a plurality of network controllers associated with a respective plurality of network domains, including a first network controller and a second network controller, wherein each of the plurality of network controllers further comprises:
 a memory; 
 a processor coupled to the memory; and 
 processor-executable instructions stored on the memory, 
 wherein the plurality of network controllers are enabled to execute the instructions to:
 receive a network request at the first network controller, the network request specifying a source vertex and a destination vertex, wherein the source vertex is located in a first network domain managed by the first network controller, and wherein the destination vertex is located in a second network domain managed by a second network controller; 
 perform distributed graph processing at the plurality of network controllers to determine a network path between the source vertex and the destination vertex, the distributed graph processing causing the processor to execute the instructions to:
 within each network domain, execute a plurality of supersteps, wherein each superstep includes a minimum path distance between each vertex in the network domain and the source vertex; 
 send, subsequent to each superstep, a controller message among the plurality of network controllers, wherein the controller message includes a first field specifying a sending vertex identifier, a second field specifying a target vertex identifier, and a third field specifying the minimum path distance from the source vertex to a target vertex corresponding to the target vertex identifier, wherein a sending vertex corresponding to the sending vertex identifier is included in a network domain of a network controller sending the controller message and the target vertex is included in a network domain of a network controller receiving the controller message; 
 repeat, after each superstep, sending a controller message until all network paths between the source vertex and the destination vertex are recorded, wherein the path information does not change based on a given network topology among the plurality of network domains; 
 record, by each network controller for each vertex in the network domain corresponding to the network controller, path information comprising: the minimum path distance from the source vertex to the vertex; and a parent vertex identifier for a parent vertex from the vertex resulting in the minimum path distance to the source vertex; 
 receive new path information for the respective vertex after path information is recorded for a respective vertex; and 
 discard new path information for the respective vertex when the new path information for the respective vertex specifies a value for the minimum path distance greater than the minimum path distance recorded in the path information; and 
 
 provide at least one network service to at least one customer of a service provider using an output path, wherein the output path is computed based on the path information. 
 
 
     
     
       9. The network system of  claim 8 , wherein the distributed graph processing begins with the first network controller at the first network domain. 
     
     
       10. The network system of  claim 8 , wherein the distributed graph processing begins with the second network controller at the second network domain. 
     
     
       11. The network system of  claim 8 , further comprising instructions to:
 aggregate the path information corresponding to the minimum path distance; and 
 based on the path information aggregated, compute an output path spanning a minimum distance between the source vertex and the destination vertex. 
 
     
     
       12. The network system of  claim 11 , wherein the instructions to aggregate the path information further comprise instructions to:
 aggregate only border nodes for each network domain. 
 
     
     
       13. The network system of  claim 11 , wherein the instructions to aggregate the path information are performed by one of: the first network controller and the second network controller, and further comprising instructions to:
 respond, by the first network controller, to the network request with the output path. 
 
     
     
       14. The network system of  claim 8 , wherein the plurality of network controllers are software-defined network controllers.