Content Delivery in Wireless Wide Area Networks

• US 20160205016A1
• Filed: 03/21/2016
• Published: 07/14/2016
• Est. Priority Date: 08/02/2004
• Status: Active Grant

• Current Assignee: Genghiscomm Holdings, LLC, Twin Technologies, Inc.
• Original Assignee: Genghiscomm Holdings, LLC, Twin Technologies, Inc.
• Inventors: Shattil, Steve J.
• Granted Patent: US 9,774,505 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

A set of edge servers in a content delivery network is selected to serve a set of users. Selection comprises constructing a trellis having a number of states at least equal to a number of edge servers in the edge-server set, wherein each state comprises a plurality of nodes, each node corresponding to one of a plurality of candidate edge servers. A fitness function is calculated based on network performance improvement and cost corresponding to each candidate edge server. A trellis-exploration algorithm is used to select the edge-server set by identifying a path through the trellis having optimal path metrics derived from the fitness function. The algorithm provides 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, a path is selected that corresponds to a best path metric that connects to a node in a previous state, wherein the best path metric comprises the fitness function. Data signals are transmitted to each edge server in the edge-server set for storage, which are then delivered to requesting client devices.

Claims

1. A non-transitory machine-readable medium, comprising instructions for selecting an edge-server set from a plurality of candidate edge servers, comprising:

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

employing a trellis-exploration algorithm to select the edge-server set, 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 performance metric that connects to a node in a previous state, wherein each performance metric comprises a network topology state based on channel-quality measurements; and

transmitting data signals to be stored on the edge-server set for delivery to client devices.

2. The medium of claim 1, wherein the performance metric comprises channel state information from at least one of edge servers and client devices in a wireless network.

3. The medium of claim 1, wherein employing the trellis-exploration algorithm comprises at least one of adapting a network topology and allocating channels to serve the client devices.

4. The medium of claim 1, wherein the network topology state comprises at least one of estimated bit rates, link-delay information, requests for retransmission, a wireless communication channel model, congestion, queue backlogs, and latency.

5. The medium of claim 1, wherein the network topology state comprises a statistical model of the network topology state comprising a time-average of at least one of server loads, user demands, queue backlogs, bit rates, channel quality, and geographical distributions of users.

6. The medium of claim 1, wherein the network topology state comprises at least one of a device network topology for each of a plurality of device types and a demand topology for each of a plurality of content types.

7. The medium of claim 1, wherein the network topology state comprises data collected from client-side metrics managers.

8. The medium of claim 1, wherein the performance metric comprises monetary costs for employing at least one of the plurality of candidate edge servers.

9. The medium of claim 1, wherein the trellis exploration algorithm comprises allocating channels to at least one of edge servers and client devices in a wireless network.

10. A non-transitory machine-readable medium comprising instructions for employing an iterative process to select an edge-server set, comprising:

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

employing a trellis-exploration algorithm to select the edge-server set, 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 performance metric that connects to a node in a previous state, wherein the best performance metric comprises a benefit minus a cost for serving clients; and

scheduling data transmissions from the edge-server set to deliver transmission signals to the clients.

11. The medium of claim 10, wherein the performance metric comprises channel state information.

12. The medium of claim 10, wherein employing the trellis-exploration algorithm comprises adapting at least one of a network topology and a network topology state of the edge-server set.

13. The medium of claim 10, wherein employing the trellis-exploration algorithm comprises selecting channels to serve the clients.

14. The medium of claim 10, wherein the edge-server set is selected after a predetermined number of iterations or when a predetermined criterion is met.

15. The medium of claim 10, wherein selecting the edge-server set comprises at least one of appending and deleting at least one edge server from a previous edge-server set.

16. The medium of claim 10, wherein the performance metric is calculated using a backpressure routing algorithm.

17. A non-transitory machine-readable medium, comprising instructions for selecting an edge-server set, comprising:

constructing a trellis having a number of states at least equal to a number of edge servers in the 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 improvement and cost corresponding to each candidate edge server;

employing a trellis-exploration algorithm to select the 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; and

transmitting a data signal to each edge server in the edge-server set for storage, to be delivered to each of a plurality of client devices.

18. The medium of claim 17, further comprising performing multiple iterations through the trellis to refine selecting the edge-server set.

19. The medium of claim 17, wherein the network performance improvements comprise at least one of predicted performance improvements and measured performance improvements.

20. The medium of claim 17, wherein path metrics comprise channel state information.

21. The medium of claim 17, wherein employing the trellis-exploration algorithm comprises adapting at least one of a network topology and a network topology state of the edge-server set.

22. The medium of claim 17, wherein employing the trellis-exploration algorithm comprises selecting channels to serve the plurality of client devices.