System and method for optimized storage and retrieval of data on a distributed computer network

• US 6,003,030 A
• Filed: 10/18/1996
• Issued: 12/14/1999
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: InterVU, Inc. (Akamai Technologies, Inc.)
• Inventors: Kenner, Brian, Karush, Arnold
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US08/733,516
• Time in Patent Office: 1,152 Days
• Field of Search: 395/200.33, 395/200.31, 395/182.02, 395/182.03, 395/182.04, 395/200.54, 395/200.55, 395/200.56, 395/200.53, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0823 Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1021 : based on client or server locations
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/60 : Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04N 21/2181 : comprising remotely distributed storage units, e.g. when movies are replicated over a plurality of video servers distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: H04N 21/222 : Secondary servers, e.g. proxy server, cable television Head-end provisioning of proxy services in data packet switching networks H04L67/56
• CPC Class Codes: H04N 21/23106 : involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/23109 : by placing content in organized collections, e.g. EPG data repository details of retrieval of video data and associated meta data in video databases G06F16/739
• CPC Class Codes: H04N 21/2385 : Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/2402 : Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/2543 : Billing , e.g. for subscription services payment schemes, architectures or protocols G06Q20/00; e-commerce G06Q30/00; arrangements for billing for the use of broadcast information or broadcast-related information H04H60/21
• CPC Class Codes: H04N 21/25841 : involving the geographical location of the client retrieval from the Internet by querying based on geographical locations G06F16/9537; arrangements for identifying locations of receiving stations in broadcast systems H04H60/51; location of the user terminal in data switching networks H04L67/52; services making use of the location of users or terminals in wireless networks H04W4/02; locating users or terminals in wireless networks H04W64/00
• CPC Class Codes: H04N 21/2743 : Video hosting of uploaded data from client
• CPC Class Codes: H04N 21/2747 : Remote storage of video programs received via the downstream path, e.g. from the server
• CPC Class Codes: H04N 21/4331 : Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/44209 : Monitoring of downstream path of the transmission network originating from a server, e.g. bandwidth variations of a wireless network arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896
• CPC Class Codes: H04N 21/44245 : Monitoring the upstream path of the transmission network, e.g. its availability, bandwidth
• CPC Class Codes: H04N 21/4622 : Retrieving content or additional data from different sources, e.g. from a broadcast channel and the Internet web site content organization and management for information retrieval from the Internet G06F16/958; transmission by internet of broadcast information H04H60/82; stock exchange data over packet-switching network H04L12/1804; push services including data channel over packet-switching network H04L12/1859
• CPC Class Codes: H04N 21/4782 : Web browsing , e.g. WebTV
• CPC Class Codes: H04N 21/6125 : involving transmission via Internet transmission by internet of broadcast information H04H60/82
• CPC Class Codes: H04N 21/6543 : for forcing some client operations, e.g. recording remote booting in general G06F9/4416
• CPC Class Codes: H04N 7/17336 : Handling of requests in head-ends
• CPC Class Codes: Y10S 707/914 : Video
• CPC Class Codes: Y10S 707/916 : Audio
• CPC Class Codes: Y10S 707/917 : Text
• CPC Class Codes: Y10S 707/919 : Geographic
• CPC Class Codes: Y10S 707/959 : Network
• CPC Class Codes: Y10S 707/966 : Distributed

Abstract

A system and method for the optimized storage and retrieval of video data at distributed sites calls for the deployment of "Smart Mirror" sites throughout a network, each of which maintains a copy of certain data managed by the system. Every user is assigned to a specific delivery site based on an analysis of network performance with respect to each of the available delivery sites. Generalized network performance data is collected and stored to facilitate the selection of additional delivery sites and to ensure the preservation of improved performance in comparison to traditional networks.

Claims

1. A system for selecting a delivery site, located on a distributed computer network, from which to a. receive a file, the system comprising:

a distributed computer network;

at least one content provider connected to the network, wherein the content provider stores at least one file;

a plurality of delivery sites connected to the network, wherein at least one of the delivery sites stores at least one copy of the same file;

a user terminal connected to the network;

a network traffic testing apparatus for selecting a preferred delivery site from all delivery sites connected to the network; and

a downloading apparatus for downloading the file from the preferred delivery site to the user terminal.

2. A system according to claim 1, wherein the network testing apparatus comprises a first storage medium connected to the user terminal, wherein the first storage medium embodies a first software program for testing the network and selecting a preferred delivery site from all delivery sites connected to the network.

3. A system according to claim 2, wherein the downloading apparatus comprises a second storage medium connected to the user terminal, wherein the second storage medium embodies a second software program capable of downloading the file from the preferred delivery site to the user terminal.

4. A system according to claim 3, further comprising a database connected to the network.

5. A system according to claim 4, wherein the first software program uses a list of delivery sites created by the database.

6. A system according to claim 5, wherein the first software program uses results from a network analysis procedure to choose the preferred delivery site from the list of delivery sites.

7. A system according to claim 6, wherein the network analysis procedure is performed at least in part at the user terminal.

8. A system according to claim 7, wherein the network analysis procedure comprises a plurality of network tests.

9. A system according to claim 8, wherein the network tests are selected from a list of tests maintained in the database.

10. A system according to claim 9, wherein the list of tests includes a download elapsed time test.

11. A system according to claim 10, wherein the elapsed time test is normalized by an average load experienced by each tested delivery site.

12. A system according to claim 11, wherein the average load is monitored by each delivery site, and a number corresponding to the average load is stored by each delivery site to be accessible to the network.

13. A system according to claim 8, wherein the network testing procedure yields a numerical performance rating for each tested delivery site.

14. A system according to claim 13, wherein the numerical performance rating is calculated as a weighted sum of results from the network tests.

15. A system according to claim 14, wherein the weighted sum is calculated using weights provided for each network test by the database.

16. A system according to claim 8, wherein results from the network tests are provided to the database.

17. A system according to claim 16, wherein the results are stored in the database.

18. A system according to claim 9, wherein the first software program performs the network tests in conjunction with the user terminal.

19. A system according to claim 18, wherein the second software program performs the download in conjunction with the user terminal.

20. A system according to claim 18, wherein the first software program can be executed at any time.

21. A system according to claim 20, wherein the first software program is executed automatically before any file is downloaded.

22. A system according to claim 5, wherein the first software program uses results from a network analysis procedure to create a prioritized list of preferred delivery sites.

23. A system according to claim 22, wherein the second software program uses the prioritized list.

24. A system according to claim 23, wherein the second software program first attempts to use a first delivery site specified in the prioritized list.

25. A system according to claim 24, wherein if the first delivery site fails, the second software program will attempt to use succeeding delivery sites specified in the prioritized list.

26. A system according to claim 25, wherein if all delivery sites in the prioritized list fail, the second software program will attempt to download directly from the content provider.

27. A system according to claim 1, wherein the file comprises a video clip.

28. A system according to claim 1, wherein the file has characteristic information associated therewith.

29. A system according to claim 28, wherein the characteristic information includes information specifying that the file is stored on at least two delivery sites.

30. A system according to claim 29, wherein the characteristic information identifies the content provider.

31. A system according to claim 28, wherein the characteristic information includes content rating information.

32. A system according to claim 28, wherein the characteristic information is stored within an "EMBED" statement corresponding to the file.

33. The system of claim 1 further comprising a file request apparatus connected to the user terminal, the file request apparatus for requesting a file from one of the delivery sites.

34. The system of claim 1 wherein a delivery site that is located a shortest electronic distance from a user terminal is designated as the preferred delivery site.

35. A method for determining a set of preferred delivery sites from a plurality of delivery sites on a network, comprising the steps of:

obtaining a list of delivery sites;

performing at least one network traffic test to determine file delivery performance associated with a plurality of paths in the network that are associated with the delivery sites;

processing results from the network test; and

prioritizing the delivery sites according to the test results.

36. The method of claim 35, wherein the performing step comprises testing some of the delivery sites in the list.

37. The method of claim 36, wherein the performing step comprises:

selecting a subset of delivery sites from the list; and

running at least one test for each of the delivery sites in the subset.

38. The method of claim 37, wherein the test is selected from a plurality of tests.

39. The method of claim 38, wherein the plurality of tests is specified in a database connected to the network.

40. The method of claim 39, wherein the test is selected from the plurality by way of random selection based on a frequency specified in the database.

41. The method of claim 35, further comprising the step of sending the results to a database connected to the network.

42. The method of claim 35, wherein the processing step comprises weighting the results.

43. The method of claim 42, wherein the weighting step uses weights specified in the list of delivery sites.

44. The method of claim 35, wherein the prioritizing step comprises storing the set of delivery sites in a preferred order.

45. The method of claim 44, wherein the preferred order is determined by the test results.

46. The method of claim 35, wherein the list of delivery sites is obtained from a database.

47. The method of claim 35 wherein the performing, processing and priortizing steps are performed by a client application.

48. The method of claim 35 wherein the priortizing step is bases on a shortest electronic distance from a delivery site to an entity in the network.

49. A method for downloading a file from a delivery site, comprising the steps of:

identifying a desired file;

determining whether the desired file is mirrored on one or more delivery sites;

if the desired file is mirrored, identifying at least one preferred delivery site according to the results of at least one network traffic test; and

downloading the desired file from the preferred delivery site.

50. The method of claim 49, wherein the identifying and downloading steps are repeated until the downloading step is successful.

51. The method of claim 50, further comprising the step of downloading the desired file from a content provider site if the repeated retrieving and downloading steps are unsuccessful.

52. The method of claim 49, further comprising the step of verifying file authorization after the determining step.

53. The method of claim 52, wherein the verifying step comprises the substeps of:

checking if the desired file has a content rating;

if the file has a content rating, comparing the content rating against a standard specified by a user;

if the content rating is acceptable to the user, or if the clip has no content rating and unrated clips are acceptable to the user, authorizing the downloading step; and

otherwise declining the downloading step.

54. The method of claim 53, wherein the downloading step is performed only if it is authorized.

55. The method of claim 49, further comprising the step of storing the downloaded file in a data area on the user terminal.

56. The method of claim 55, wherein the storing step comprises the substeps of:

determining if there is sufficient room in the data area to store the downloaded file;

if there is not sufficient room, deleting the least-recently-used files from the data area; and

saving the downloaded file to the data area.

57. The method of claim 56, further comprising the steps of:

prior to the downloading step, searching for the desired file in the data area;

if the desired file is found as a stored file, verifying that the stored file is identical to the desired file; and

if the desired file and stored file are identical, displaying the stored file instead of downloading the desired file.

58. The method of claim 57, wherein the verifying step comprises comparing the dates and times of creation for the stored file and the desired file.

59. The method of claim 49, further comprising the step of informing a mirror service provider of a successful download.

60. The method of claim 49 further including the step of requesting a file from one of the delivery sites.

61. The method of claim 49 wherein a delivery site that is located a shortest electronic distance from an entity in the network is designated as the preferred delivery site.

62. A method for locating and maintaining a network of delivery sites for the optimized storage and retrieval of files, comprising the steps of:

receiving network traffic test results from a plurality of users;

storing the test results in a database;

processing the test results;

determining network performance at various locations on the network; and

distributing the delivery sites and the files throughout the network according to the determined network performance.

63. The method of claim 62 wherein the distributing step is based on a shortest electronic distance from a delivery site to a user.

64. The method of claim 62 further including the step of mirroring data from a content provider to at least one delivery site.

65. The method of claim 62 further including the step of notifying the users of the existence of at least one delivery site.

66. The method of claim 62 wherein the distributing step is based on the use of content by users in the system.

67. A system for selecting a delivery site, located on a distributed computer network, from which to a receive a file, the system comprising:

a distributed computer network;

at least one content provider connected to the network, wherein the content provider stores at least one file;

a plurality of delivery sites connected to the network, wherein at least one of the delivery sites stores at least one copy of the same file;

a user terminal connected to the network;

a network testing apparatus for selecting a preferred delivery site from all delivery sites connected to the network, wherein the network testing apparatus uses results from a plurality of network tests to choose the preferred delivery site from a list of delivery sites, the network tests including a download elapsed time test that is normalized by an average load experienced by each tested delivery site;

a downloading apparatus for downloading the file from the preferred delivery site to the user terminal.

68. A method for determining a set of preferred delivery sites from a plurality of delivery sites on a network, comprising the steps of:

obtaining a list of delivery sites;

performing at least one network test to determine file delivery performance associated with at least one path in the network, the performing step comprising;

selecting a subset of delivery sites from a list of delivery sites;

running at least one test for each of the delivery sites in the subset, wherein one of the at least one test is selected by way of a random selection based on a specified frequency;

processing results from the network test; and

prioritizing the delivery sites according to the test results.