Connection minimization for distributed system

• US 10,454,807 B2
• Filed: 10/13/2016
• Issued: 10/22/2019
• Est. Priority Date: 10/13/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: Li, Li
• Primary Examiner(s): Patel, Hitesh
• Application Number:
  US15/293,207
• Publication Number:
  US 20180109435A1
• Time in Patent Office: 1,104 Days
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A method computer implemented method of minimizing connections in a distributed system includes traversing paths in a directed graph representation of the distributed system having a fixed set of paths between nodes representing resources of the distributed system and edges representing connections between the resources by performing a random walk procedure to provide a reduced number of paths in the directed graph representation, and identifying excessive connections between the resources by simulating a client accessing the resources and identifying as excessive, connections that are not used by any of the reduced number of paths, wherein the excessive connections are removable from the distributed system without preventing client access to resources in the distributed system.

Claims

1. A method of minimizing edges in a directed graph representing a distributed system, the method comprising:

using a representational state transfer application program interface (REST API) including a plurality of resource nodes of the directed graph representing resources identified by uniform resource indicators (URIs) and a plurality of edges of the directed graph representing a plurality of hyperlinks between the resources, traversing paths in the directed graph including;

performing a distinct walk procedure to determine all distinct paths in the directed graph; and

performing a random walk procedure including;

starting from an entry node of the directed graph, selecting an edge at random;

moving to a node coupled by the selected edge and repeating random selection of an edge until a predefined path length is reached or no edge exists from the node coupled by the selected edge;

storing each selected edge; and

repeating selecting an edge at random from the entry node, moving, and repeating selection of an edge until a selected number of paths is obtained;

simulating a client accessing the resources, the simulated client selecting, at each node, one of the stored edges instead of an edge that was not encountered in the random walk procedure; and

identifying as excessive edges, edges that are not used by any of the selected number of paths, wherein the excessive edges are removable from the distributed system without preventing client access to resources in the distributed system.

2. The method of claim 1 wherein:

simulating the client accessing the resources comprises caching the edges of the paths encountered in the random walk procedure; and

identifying the excessive edges comprises applying a cache-first policy to take client cached edges into account followed by application of a recent-first policy to select a more recently cached edge over a less recently cached edge.

3. The method of claim 2 wherein the cache-first policy selects the cached edges over direct edges.

4. The method of claim 2 wherein the cache-first policy and recent-first policy resolve ambiguous edges.

5. The method of claim 1 wherein a different random seed is used at the entry node for each path.

6. The method of claim 1 wherein the hyperlinks include operations comprising get, put, post, and delete.

7. The method of claim 1 wherein the directed graph comprises a resource oriented network (RON) representation of the distributed system comprising the REST API.

8. A device comprising:

a non-transitory memory storage comprising instructions; and

one or more processors in communication with the memory, wherein the one or more processors execute instructions to perform operations including;

using a representational state transfer application program interface (REST API) including a plurality of resource nodes of a directed graph representing resources identified by uniform resource indicators (URIs) and a plurality of edges of the directed graph representing a plurality of hyperlinks between the resources, traversing paths in a directed graph including;

performing a distinct walk procedure to determine all distinct paths in the directed graph; and

performing a random walk procedure including;

starting from an entry node of the directed graph, selecting an edge at random;

moving to a node coupled by the selected edge and repeating random selection of an edge until a predefined path length is reached or no edge exists from the node coupled by the selected edge;

storing each selected edge; and

repeating selecting an edge at random from the entry node, moving, and repeating selection of an edge until a selected number of paths is obtained;

simulating a client accessing the resources, the simulated client selecting, at each node, one of the stored edges instead of an edge that was not encountered in the random walk procedure; and

identifying as excessive edges, edges that are not used by any of the selected number of paths, wherein the excessive edges are removable from a distributed system without preventing client access to resources in the distributed system.

9. The device of claim 8 wherein:

simulating the client accessing the resources comprises caching the edges of the paths encountered in the random walk procedure; and

identifying excessive edges comprises applying a cache-first policy to take client cached edges into account followed by application of a recent-first policy, wherein the cache-first policy selects cached edges over direct edges and wherein the recent-first policy selects a more recently cached edge over a less recently cached edge to resolve ambiguous edges.

10. The device of claim 8 wherein a different random seed is used at the entry node for each path.

11. The device of claim 8 wherein the hyperlinks include operations comprising get, put, post, and delete and wherein the directed graph comprises a resource oriented network (RON) representation of the distributed system comprising the REST API.

12. A system comprising:

a non-transitory storage device comprising instructions; and

one or more processors in communication with the non-transitory storage device, wherein the one or more processors are configured by the instructions to process a resource oriented network (RON) directed graph representation of a distributed system, the instructions comprising;

a REST API (Representational State Transfer Application Program Interface) stored on the non-transitory storage device the REST API including a plurality of resource nodes of the directed graph representing resources identified by uniform resource indicators (URIs) and a plurality of edges of the directed graph representing a plurality of hyperlinks between the resources;

a distinct walk procedure, stored on the non-transitory storage device that conditions the one or more processors to determine all distinct paths in the RON;

a random walk procedure stored on the storage device that conditions the one or more processors to perform a procedure comprising;

starting from an entry node of the directed graph, selecting an edge at random;

moving to a node coupled by the selected edge and repeating random selection of an edge until a predefined path length is reached or no edge exists from the node coupled by the selected edge;

storing each selected edge; and

repeating selecting an edge at random from the entry node, moving, and repeating selection of an edge until a selected number of paths is obtained;

a client model stored on the non-transitory storage device, the client model including a cache-first policy that configures the one or more processors to select a stored edge instead of an edge that was not encountered in the random walk procedure and a recent-first policy that configures the one or more processors to select a more recently stored edge over a less recently stored edge to resolve ambiguous hypertext driven paths; and

a minimization procedure stored on the non-transitory storage device to condition the one or more processors to identify excessive hyperlinks from the selected number of paths, such excessive hyperlinks corresponding to edges in the RON that are not used by any of the selected number of paths.