Fog computing network resource partitioning

• US 10,243,878 B2
• Filed: 06/16/2016
• Issued: 03/26/2019
• Est. Priority Date: 06/16/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Byers, Charles Calvin, Salgueiro, Gonzalo, Clarke, Joseph Michael
• Primary Examiner(s): Nano, Sargon N
• Application Number:
  US15/184,171
• Publication Number:
  US 20170366472A1
• Time in Patent Office: 1,013 Days
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/38 for collecting sensor information
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]

Abstract

Various implementations disclosed herein enable improved allocation of fog node resources, which supports performance driven partitioning of competing client applications. In various implementations, methods are performed by a fog orchestrator configured to determine allocations of fog resources for competing client applications and partition the competing client applications based on the fog resource allocations. Methods include receiving reservation priority values (RPVs) associated with a plurality of client applications competing for a contested fog node resource, transmitting, to a subset of client devices, a request to provide updated RPVs, and awarding the contested fog node resource to one of the plurality of client applications based on the received RPVs and any updated RPVs. In various implementations, methods also include determining, for each of the plurality of client applications, a respective mapping for a respective plurality of separable components of the client application based on the awarded contested fog node resource.

Claims

1. A method comprising:

at a fog orchestrator configured to determine allocations of fog resources for competing client applications and partition the competing client applications based on the fog resource allocations, the fog orchestrator including a non-transitory memory, one or more processors, and one or more network interfaces;

receiving, from a plurality of client devices, reservation priority values (RPVs) associated with a plurality of client applications competing for a contested fog node resource;

transmitting, to a subset of the plurality of client devices, a request to provide updated RPVs for the contested fog node resource, wherein transmitting includes iteratively transmitting the request until responses to a last transmitted request are not received within a threshold response duration for receiving responses;

awarding the contested fog node resource to one of the plurality of client applications based on the received RPVs and any updated RPVs received in response to the transmitted request; and

determining, for each of the plurality of client applications, a respective mapping for a respective plurality of separable components of the client application based on the awarded contested fog node resource, each respective mapping includes assignment of the respective plurality of separable components to fog node resources within the fog network.

2. The method of claim 1, wherein each of the plurality of client applications including a respective plurality of separable components characterizing a processing pipeline that together generate one or more application-level outputs, wherein the processing pipeline includes at least one of sequential processing components and parallel processing components.

3. The method of claim 1, wherein the fog resources include a combination of one or more of processing resources, memory resources, connectivity resources, and input-output (I/O) interface resources.

4. The method of claim 1, wherein receiving the RPVs receiving new client application requests that include the RPVs.

5. The method of claim 4, wherein each new client application request includes a client application manifest listing of separable components of the corresponding client application, and a RPV associated with each of the separable components of the corresponding client application.

6. The method of claim 1, wherein receiving the RPVs includes determining RPVs for in process application components for currently executing partitions and fog node resource allocations.

7. The method of claim 1, further comprising selecting the subset of the plurality of client devices to transmit the request to provide updated RPVs for the contested fog node resource to by selecting client devices that previously provided RPVs that satisfy a cutoff value.

8. The method of claim 1, further comprising selecting the subset of the plurality of client devices to transmit the request to provide updated RPVs for the contested fog node resource to by selecting client devices that previously provided RPVs that are below a single highest RPV value provided by another one of the plurality of client devices.

9. The method of claim 1, wherein transmitting includes iteratively transmitting the request until an iteration threshold has been satisfied.

10. The method of claim 1, wherein awarding the contested fog node resource includes selecting the client application associated with the highest RPV received.

11. The method of claim 1, wherein awarding the contested fog node resource includes selecting the client application based on a combination of service level agreement parameters and a RPV magnitude.

12. The method of claim 1, wherein awarding the contested fog node resource includes selecting the client application based on priority levels associated with a spectrum of RPV magnitudes.

13. The method of claim 1, wherein determining the respective mappings includes repartitioning the fog node resources among the competing client devices based on the award of the contested fog node resources, wherein at least one in process application is provided with a new mapping to fog node resources.

14. The method of claim 13, wherein the new mapping to fog node resources for the at least one in process application includes at least one of moving a separable component of the at least one in process application to a fog node higher in a fog node hierarchy and moving a separable component of the at least one in process application to a fog node lower in a fog node hierarchy.

15. A system comprising:

a plurality of fog nodes arranged in a hierarchical network between a gateway device and a plurality of endpoint devices; and

a fog orchestrator configured to determine allocations of fog resources for competing client applications and partition the competing client applications based on the fog resource allocations, the fog orchestrator including one or more network interfaces, one or more processors, and a non-transitory memory that includes instructions that when executed by the one or more processors causes the fog orchestrator to;

receive, from a plurality of client devices, reservation priority values (RPVs) associated with a plurality of client applications competing for a contested fog node resource;

transmit, to a subset of the plurality of client devices, a request to provide updated RPVs for the contested fog node resource, wherein transmitting includes iteratively transmitting the request until responses to a last transmitted request are not received within a threshold response duration for receiving responses;

award the contested fog node resource to one of the plurality of client applications based on the received RPVs and any updated RPVs received in response to the transmitted request; and

determine, for each of the plurality of client applications, a respective mapping for a respective plurality of separable components of the client application based on the awarded contested fog node resource, each respective mapping includes assignment of the respective plurality of separable components to fog node resources within the fog network.

16. The system of claim 15, wherein the hierarchical network includes a plurality of layers, wherein each layer includes a group of one or more fog nodes, defined by relative distance ranges or latency ranges relative to the gateway device or endpoint devices.

17. The system of claim 15, wherein each of the plurality of client applications including a respective plurality of separable components characterizing a processing pipeline that together generate one or more application-level outputs.

18. The system of claim 15, wherein fog resources include a combination of one or more of processing resources, memory resources, connectivity resources, and input-output (I/O) interface resources.

19. A fog node orchestrator comprising:

means for receiving, from a plurality of client devices, reservation priority values (RPVs) associated with a plurality of client applications competing for a contested fog node resource;

means for transmitting, to a subset of the plurality of client devices, a request to provide updated RPVs for the contested fog node resource, wherein transmitting includes iteratively transmitting the request until responses to a last transmitted request are not received within a threshold response duration for receiving responses;

means for awarding the contested fog node resource to one of the plurality of client applications based on the received RPVs and any updated RPVs received in response to the transmitted request; and

means for determining, for each of the plurality of client applications, a respective mapping for a respective plurality of separable components of the client application based on the awarded contested fog node resource, each respective mapping includes assignment of the respective plurality of separable components to fog node resources within the fog network.

20. The fog node orchestrator of claim 19, wherein each of the plurality of client applications including a respective plurality of separable components characterizing a processing pipeline that together generate one or more application-level outputs.