Network service computation system

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.