System, computer program, and method for dividing services into subsets based on interdependencies

• US 10,104,187 B2
• Filed: 06/15/2016
• Issued: 10/16/2018
• Est. Priority Date: 06/15/2016
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Shi, Hang, Dai, Huida
• Primary Examiner(s): Nano, Sargon
• Application Number:
  US15/183,694
• Publication Number:
  US 20170366623A1
• Time in Patent Office: 853 Days
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A system, computer program, and method are provided for service placement in a network. Information is stored on a collection of services that are configured to be performed in a dynamic order. Further, one or more interdependencies between at least a portion of the services are identified. Still yet, the collection of services is divided into one or more subsets of the services, based on the one or more interdependencies. A plurality of parts of at least one of the one or more subsets of the services is combined, resulting in one or more composite subsets of the services that are outputted to at least one of a plurality of service nodes.

Claims

1. A method of service placement in a network, comprising:

storing information on a collection of services that are configured to be performed in a dynamic order;

identifying, from the information, one or more interdependencies between at least a portion of the services;

dividing the collection of services into one or more subsets of the services, based on the one or more interdependencies, wherein each subset of the one or more subsets includes a portion of the services that are interdependent with one another;

for each subset of the one or more subsets, combining the portion of the services included therein into a composite service;

for each composite service, assigning the composite service to a single service node of a plurality of service nodes; and

deploying, by each service node of the plurality of service nodes, the services in the composite service assigned thereto.

2. The method of claim 1, further comprising:

receiving at least one other interdependency from a user.

3. The method of claim 2, wherein the collection of services is divided into the one or more subsets of the services, based on the at least one other interdependency from the user.

4. The method of claim 1, further comprising receiving at least one rule from a user.

5. The method of claim 4, wherein the collection of services is divided into the one or more subsets of the services, based on the at least one rule from the user.

6. The method of claim 1, wherein the plurality of service nodes are autonomous.

7. The method of claim 1, wherein each composite service is configured for being moved from the service node assigned thereto to at least one other service node of the plurality of service nodes.

8. The method of claim 1, wherein wherein a first composite service is assigned to a first service node of the plurality of service nodes, and wherein a second composite service is assigned to a different second service node of the plurality of service nodes.

9. The method of claim 1, further comprising:

identifying a cost associated with each composite service, and assigning the composite service to the single service node, based on the cost.

10. The method of claim 9, wherein the cost includes a cost in resources.

11. The method of claim 1, wherein the information on the collection of services is at least one of a graph, an array, a table, or a digital structure.

12. The method of claim 1, wherein the one or more interdependencies are received from at least one user or automatically generated utilizing heuristics.

13. The method of claim 1, wherein each composite service includes a metric that is a sum of a plurality of metrics associated with the portion of the services included therein.

14. The method of claim 1, wherein each composite service includes a metric that is a largest one of a plurality of metrics associated with the portion of the services included therein.

15. The method of claim 1, wherein assigning the composite service utilizes a first fit decreasing (FFD) bin pack algorithm.

16. The method of claim 1, wherein the information defines a service graph that includes the collection of services, and wherein the composite service represented by a sub-graph of the service graph.

17. The method of claim 1, wherein assigning the composite service to a single service node of a plurality of service nodes includes:

determining a composite resource requirement for the composite service, the composite resource requirement being determined based on individual resource requirements of each service included in the composite service;

determining a resource capacity of the single service e node; and

assigning the composite service to the single service node, based on the determined composite resource requirement and the determined resource capacity.

18. An apparatus, comprising:

memory configured to store information on a collection of services that are configured to be performed in a dynamic order;

a policy manager in communication with the memory, the policy manager configured to identify, from the information, one or more interdependencies between at least a portion of the services;

a service orchestrator in communication with the policy manager, the service orchestrator configured to;

divide the collection of services into one or more subsets of the services, based on the one or more interdependencies, wherein each subset of the one or more subsets includes a portion of the services that are interdependent with one another, and

for each subset of the one or more subsets, combine the portion of the services included therein into a composite service; and

a controller in communication with the service orchestrator, the controller configured to;

for each composite service, assign the composite service to a single service node of a plurality of service nodes;

wherein each service node of the plurality of service nodes deploys the services in the composite service assigned thereto.

19. The apparatus of claim 18, wherein the policy manager is configured for identifying the one or more interdependencies by receiving the one or more interdependencies from at least one user.

20. The apparatus of claim 18, wherein the policy manager is configured for identifying the one or more interdependencies by automatically generating the one or more interdependencies utilizing heuristics.

21. The apparatus of claim 18, wherein the apparatus is configured for modeling the collection of services as a directed acyclic graph (DAG), based on the one or more interdependencies.

22. The apparatus of claim 18, wherein the apparatus is configured such that each composite service includes a metric that is a sum of a plurality of metrics associated with the portion of the services included therein.

23. The apparatus of claim 18, wherein the apparatus is configured such that each composite service includes a metric that is a largest one of a plurality of metrics associated with the portion of the services included therein.

24. The apparatus of claim 18, wherein the controller is configured to assign the composite service utilizing a first fit decreasing (FFD) bin pack algorithm.

25. An apparatus, comprising:

memory configured to store information on a collection of services that are configured to be performed in a dynamic order;

one or more processors in communication with the memory, the one or more processors configured to;

identify, from the information, one or more interdependencies between at least a portion of the services;

divide the collection of services into one or more subsets of the services, based on the one or more interdependencies, wherein each subset of the one or more subsets includes a portion of the services that are interdependent with one another; and

for each subset of the one or more subsets, combine the portion of the services included therein into a composite service; and

a controller in communication with the one or more processors, the controller configured to;

for each composite service, assign the composite service to a single service node of a plurality of service nodes;

wherein each service node of the plurality of service nodes deploys the services in the composite service assigned thereto.

26. A service placement system, comprising:

a non-transitory memory storage comprising instructions; and

one or more processors in communication with the memory storage, wherein the one or more processors execute the instructions to;

store information on a collection of services that are configured to be performed in a dynamic order;

identify, from the information, one or more interdependencies between at least a portion of the services;

divide the collection of services into one or more subsets of the services, based on the one or more interdependencies, wherein each subset of the one or more subsets includes a portion of the services that are interdependent with one another;

for each subset of the one or more subsets, combine the portion of the services included therein into a composite service;

for each composite service, assign the composite service to a single service node of a plurality of service nodes; and

deploy, by each service node of the plurality of service nodes, the services in the composite service assigned thereto.

27. The system of claim 26, wherein deploying the services in the composite service includes performing the services in the composite service.

28. The system of claim 26, wherein the system is configured such that each composite service is configured for being moved from the service node assigned thereto to at least one other service node of the plurality of service nodes.