Edge server selection for device-specific network topologies

• US 10,021,175 B2
• Filed: 05/11/2016
• Issued: 07/10/2018
• Est. Priority Date: 08/02/2004
• Status: Active Grant

• Current Assignee: Genghiscomm Holdings, LLC
• Original Assignee: Genghiscomm Holdings, LLC
• Inventors: Shattil, Steve J
• Primary Examiner(s): Liu, Jung
• Application Number:
  US15/152,028
• Publication Number:
  US 20160255140A1
• Time in Patent Office: 790 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An apparatus configured for selecting a plurality of edge-server sets, comprising: A metrics manager collects network topology information from edge servers and/or client devices. A request-routing mechanism determines a device network topology for each of a plurality of device types. For each device network topology, a device-specific edge-server set is selected. Device-specific data signals are distributed for storage on a corresponding device-specific edge-server set. A trellis-exploration algorithm can be used to determine each device-specific edge-server set.

Claims

1. An apparatus configured for selecting a plurality of edge-server sets, comprising:

a metrics manager configured to collect network topology information from at least one of a set of edge servers and a set of client devices; and

a request-routing mechanism configured to;

determine a device network topology for each of a plurality of device types;

for each device network topology, select a device-specific edge-server set from the set of edge servers; and

distribute device-specific data signals for storage on a corresponding selected device-specific edge-server set;

wherein the request-routing mechanism is configured to employ a trellis-exploration algorithm to select each device-specific edge-server set, the trellis-exploration algorithm comprising;

constructing a trellis having a number of states at least equal to a number of edge servers in the device-specific edge-server set, wherein each state comprises a plurality of nodes, each node corresponding to one of a plurality of candidate edge servers;

calculating a fitness function based on network performance and cost corresponding to each candidate edge server and the network topology information; and

employing a trellis-exploration algorithm to select the device-specific edge-server set by identifying a path through the trellis having optimal path metrics derived from the fitness function, comprising providing interconnects between each node of a first state to each of a plurality of nodes in a next state, and for each node in a state, selecting a path corresponding to a best path metric that connects to a node in a previous state, wherein the best path metric comprises the fitness function.

2. The apparatus recited in claim 1, wherein the device network topology further comprises at least one of channel state information from at least one of edge servers and client devices in a wireless network, estimated transmission rates, distances between nodes, queue backlogs, latency, signal types, channel estimates, error rates, congestion, transmission power, requests for retransmission, error correction coding parameters, link reliability estimates, and a statistical model of network topology state.

3. The apparatus recited in claim 1, wherein the device type is determined from at least one of operating system, application software, and display capabilities.

4. The apparatus recited in claim 1, wherein the device network topology includes at least one of demand topology, geographical locations, and temporal variations of geographical locations.

5. The apparatus recited in claim 4, wherein the demand topology is based on an expectation that certain types of content will be requested from certain geographical locations at certain times.

6. The apparatus recited in claim 1, wherein the device-specific edge-server set is selected based on at least one performance metric that differs for different types of requested network services.

7. The apparatus recited in claim 1, wherein the device-specific edge-server set is selected based on a performance metric calculated from a backpressure routing algorithm.

8. The apparatus recited in claim 1, wherein the device-specific edge-server set is selected to store specific content.

9. The apparatus recited in claim 1, wherein the set of edge servers comprises client devices in a mobile wireless network configured to perform edge server functions.

10. The apparatus recited in claim 1, further comprising a reflector configured to receive requests from the set of client devices and process the requests based on the corresponding selected device-specific edge-server set.

11. A server comprising a processor;

and a memory coupled to the processor, the memory including instructions stored therein and executable by the processor to;

collect network topology information from at least one of a set of edge servers and a set of client devices;

determine a device network topology for each of a plurality of device types;

based on each device network topology, select a device-specific edge-server set from the edge servers for the each of the plurality of device types; and

distribute device-specific data signals for storage on a corresponding selected device-specific edge-server set;

wherein the instruction to select a device-specific edge-server set is configured to employ a trellis-exploration algorithm to select each device-specific edge-server set, the trellis-exploration algorithm comprising;

constructing a trellis having a number of states at least equal to a number of edge servers in the device-specific edge-server set, wherein each state comprises a plurality of nodes, each node corresponding to one of a plurality of candidate edge servers;

calculating a fitness function based on network performance and cost corresponding to each candidate edge server and the network topology information; and

employing a trellis-exploration algorithm to select the device-specific edge-server set by identifying a path through the trellis having optimal path metrics derived from the fitness function, comprising providing interconnects between each node of a first state to each of a plurality of nodes in a next state, and for each node in a state, selecting a path corresponding to a best path metric that connects to a node in a previous state, wherein the best path metric comprises the fitness function.

12. The server recited in claim 11, wherein the device network topology further comprises at least one of channel state information from at least one of edge servers and client devices in a wireless network, estimated transmission rates, distances between nodes, queue backlogs, latency, signal types, channel estimates, error rates, congestion, transmission power, requests for retransmission, error correction coding parameters, link reliability estimates, and a statistical model of network topology state.

13. The apparatus recited in claim 11, wherein the device type is determined from at least one of operating system, application software, and display capabilities.

14. The server recited in claim 11, wherein the device network topology includes at least one of demand topology, geographical locations, and temporal variations of geographical locations.

15. The server recited in claim 14, wherein the demand topology is based on an expectation that certain types of content will be requested from certain geographical locations at certain times.

16. The server recited in claim 11, wherein the device-specific edge-server set is selected based on at least one performance metric that differs for different types of requested network services.

17. The server recited in claim 11, wherein the device-specific edge-server set is selected based on a performance metric calculated from a backpressure routing algorithm.

18. The server recited in claim 11, wherein the device-specific edge-server set is selected to store specific content.

19. The server recited in claim 11, wherein the set of edge servers comprises client devices in a mobile wireless network configured to perform edge server functions.

20. The server recited in claim 11, further comprising instructions to receive requests from the set of client devices and process the requests based on the corresponding selected device-specific edge-server set.

21. A method configured to:

collect network topology information from at least one of a set of edge servers and a set of client devices;

determine a device network topology for each of a plurality of device types;

based on each device network topology, select a device-specific edge-server set from the edge servers for the each of the plurality of device types; and

distribute device-specific data signals for storage on a corresponding selected device-specific edge-server set;

wherein the instruction to select a device-specific edge-server set is configured to employ a trellis-exploration algorithm to select each device-specific edge-server set, the trellis-exploration algorithm comprising;

constructing a trellis having a number of states at least equal to a number of edge servers in the device-specific edge-server set, wherein each state comprises a plurality of nodes, each node corresponding to one of a plurality of candidate edge servers;

calculating a fitness function based on network performance and cost corresponding to each candidate edge server and the network topology information; and

employing a trellis-exploration algorithm to select the device-specific edge-server set by identifying a path through the trellis having optimal path metrics derived from the fitness function, comprising providing interconnects between each node of a first state to each of a plurality of nodes in a next state, and for each node in a state, selecting a path corresponding to a best path metric that connects to a node in a previous state, wherein the best path metric comprises the fitness function.

22. The method recited in claim 21, wherein the device network topology further comprises at least one of channel state information from at least one of edge servers and client devices in a wireless network, estimated transmission rates, distances between nodes, queue backlogs, latency, signal types, channel estimates, error rates, congestion, transmission power, requests for retransmission, error correction coding parameters, link reliability estimates, and a statistical model of network topology state.

23. The method recited in claim 21, wherein the device type is determined from at least one of operating system, application software, and display capabilities.

24. The method recited in claim 21, wherein the device network topology includes at least one of demand topology, geographical locations, and temporal variations of geographical locations.

25. The method recited in claim 24, wherein the demand topology is based on an expectation that certain types of content will be requested from certain geographical locations at certain times.

26. The method recited in claim 21, wherein the device-specific edge-server set is selected based on at least one performance metric that differs for different types of requested network services.

27. The method recited in claim 21, wherein the device-specific edge-server set is selected based on a performance metric calculated from a backpressure routing algorithm.

28. The method recited in claim 21, wherein the device-specific edge-server set is selected to store specific content.

29. The method recited in claim 21, wherein the set of edge servers comprises client devices in a mobile wireless network configured to perform edge server functions.

30. The method recited in claim 21, further comprising instructions to receive requests from the set of client devices and process the requests based on the corresponding selected device-specific edge-server set.