Content delivery in wireless wide area networks

• US 9,325,805 B2
• Filed: 10/09/2012
• Issued: 04/26/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
• Primary Examiner(s): LIU, JUNG
• Application Number:
  US13/647,686
• Publication Number:
  US 20140098685A1
• Time in Patent Office: 1,295 Days
• Field of Search: 370/203, 370204-215, 370229-240, 370310-337, 370338-350, 370351-394, 370/395.1, 370/395.3, 370/395.4, 370/395.41, 370/395.42, 370/395.5, 370/395.52, 370431-457, 370458-463, 370464-497, 370498-529
• 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

Selecting an edge-server set in a wireless network comprises generating channel-quality measurements of wireless links between available nodes; determining a network topology state based on the measurements; calculating a performance metric for each candidate edge-server set; and selecting a candidate edge-server set based on the performance metric. An iterative process may be employed for selecting the best edge-server set. The iterative process may employ a trellis-exploration algorithm. A back-pressure routing algorithm may be used to calculate the performance metric. A server processes a request from a client residing on a wireless network by determining if another client on the wireless network has the requested object; determining if the requesting client can communicatively couple to the other client; and directing the request to the other client.

Claims

1. A method for selecting an edge-server set from a plurality of edge servers in a wireless network, comprising:

constructing a trellis having a number of states 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;

and

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 wherein at least one of the plurality of candidate edge servers is selected based on which clients a candidate edge server can reach using peer-to-peer wireless links.

2. The method 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.

3. The method 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.

4. The method 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.

5. The method of claim 1, wherein the network topology state is determined by at least one of active scanning and passive scanning.

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

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

8. A non-transitory machine-readable medium, comprising instructions for performing the method of claim 1.

9. A method employing an iterative process 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;

and

employing a trellis-exploration algorithm for selecting 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 comprises a network topology state based on channel state information, and wherein at least one of the plurality of candidate edge servers is selected based on which clients a candidate edge server can reach using peer-to-peer wireless links.

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

11. The method of claim 9, 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.

12. The method of claim 9, wherein the performance metric is calculated using a backpressure routing algorithm.

13. A non-transitory machine-readable medium, comprising instructions for performing the method of claim 9.

14. A method 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 improvements and costs corresponding to each candidate edge server; and

employing a trellis-exploration algorithm to identify 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 wherein at least one of the plurality of candidate edge servers is selected based on which clients a candidate edge server can reach using peer-to-peer wireless links.

15. The method of claim 14, further comprising performing multiple iterations through the trellis to refine selecting the edge server set.

16. The method of claim 14, wherein the network performance improvements comprise at least one of predicted performance improvements and measured performance improvements.

17. A non-transitory machine-readable medium, comprising instructions for peforming the method of claim 14.