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

• US 6,154,744 A
• Filed: 12/17/1998
• Issued: 11/28/2000
• 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:
  US09/213,946
• Time in Patent Office: 712 Days
• Field of Search: 707/10, 707/104, 707/204, 709/203, 709/226
• US Class Current: 709/203
• 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 preferred delivery site from which to receive a file, the preferred delivery site being one of a plurality of delivery sites located on a distributed network, at least one of the delivery sites storing at least one copy of the file, comprising:

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

a user terminal connected to the network; and

a network traffic testing apparatus connected to the user terminal for selecting the preferred delivery site from the plurality of delivery sites,

wherein the file is downloaded from the preferred delivery site to the user terminal.

2. The system as recited in claim 1, wherein the file is a graphics file.

3. The system as recited in claim 1, wherein the file is a text file.

4. The system as recited in claim 1, wherein the file is a video file.

5. The system as recited in claim 1, wherein the file is an audio file.

6. The system as recited in claim 1, wherein the network testing apparatus comprises a first software program for testing the network and selecting the preferred delivery site from all delivery sites connected to the network.

7. The system as recited in claim 6, further comprising a downloading apparatus connected to the user terminal, the downloading apparatus including a second software program capable of downloading the file from the preferred delivery site to the user terminal.

8. The system as recited in claim 7, further comprising one or more domain name service (DNS) servers connected to the network, wherein the DNS servers translate the domain names of the delivery sites to their Internet Protocol (IP) addresses.

9. The system as recited in claim 8, wherein the DNS servers are connected in a hierarchy.

10. The system as recited in claim 1, further comprising a database connected to the network, said database having a list of available delivery sites.

11. The system as recited in claim 10, wherein the network testing apparatus analyzes the network and selects the preferred delivery site from the list of delivery sites maintained by the database.

12. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Ping tests to determine the round trip travel time between the user terminal and one or more delivery sites.

13. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Trace-route tests.

14. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Reverse Trace-route tests.

15. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Dynamic Trace-route tests.

16. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Throughput tests.

17. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Throughput variation tests.

18. The system as recited in claim 11, wherein the network testing apparatus calculates the Error Rates between one or more delivery sites and the user terminal.

19. The system as recited in claim 11, wherein the network testing apparatus conducts one or more Packet Fragmentation tests to determine if transmission from a delivery site is subject to fragmentation.

20. The system as recited in claim 11, wherein the network testing apparatus calculates the transmission capacity of one or more delivery sites.

21. The system as recited in claim 11, wherein the network testing apparatus calculates the average load of one or more delivery sites.

22. The system as recited in claim 11, wherein the network testing apparatus creates a prioritized list of preferred delivery sites based on the network analysis.

23. The system as recited in claim 22, further comprising:

means for routing traffic towards underutilized regions of the network based on the network analysis results, thereby decreasing the time to download the file.

24. The system as recited in claim 22, wherein the nesting testing apparatus comprises a configuration utility file that downloads a delivery site file, the delivery site file including a list of available delivery sites and a list of network tests to be run.

25. The system as recited in claim 11, further comprising a graphical interface displaying the location of the user terminal and the locations of each delivery site tested.

26. The system as recited in claim 25, wherein the graphical interface displays the geographic and electronic distance of the delivery sites from the user terminal.

27. The system as recited in claim 26, wherein the user terminal and the delivery sites are displayed on a monitor as "blips" superimposed over a map of the pertinent geographical region.

28. The system as recited in claim 27, further comprising:

means for encrypting the files prior to storing in the delivery sites; and

means for decrypting the files when they are downloaded from the delivery site.

29. A method for selecting a preferred delivery site from which to receive a file, the preferred delivery site being one of a plurality of delivery sites located on a distributed network, at least one of the delivery sites storing at least one copy of the file, the method comprising the steps of:

connecting at least one content provider to the network, said content provider storing at least one file;

connecting a user terminal to the network;

testing the network using a network traffic testing apparatus connected to the user terminal;

selecting the preferred delivery site from the plurality of delivery sites based on the results of the test; and

downloading the file from the preferred delivery site to the user terminal.

30. The method as recited in claim 29, wherein the file is a graphics file.

31. The method as recited in claim 29, wherein the file is a video file.

32. The method as recited in claim 29, wherein the file is an audio file.

33. The method as recited in claim 29, wherein the file is a text file.

34. The method as recited in claim 29, wherein the network testing apparatus comprises a first software program for testing the network and selecting the preferred delivery site from all delivery sites connected to the network.

35. The method as recited in claim 34, further comprising the step of connecting a downloading apparatus to the user terminal, the downloading apparatus including a second software program capable of downloading the file from the preferred delivery site to the user terminal.

36. The method as recited in claim 35, further comprising the steps of connecting one or more domain name service (DNS) servers to the network;

and translating the domain names of the delivery sites to their respective Internet Protocol (IP) addresses.

37. The method as recited in claim 36, wherein the DNS servers are connected in a hierarchy.

38. The method as recited in claim 29, further comprising the step of connecting a database to the network, wherein the database includes a list of available delivery sites.

39. The method as recited in claim 38, further comprising the step of selecting the preferred delivery site from the list of delivery sites maintained by the database.

40. The method as recited in claim 39, further comprising the steps of:

analyzing the network using the network testing apparatus; and

selecting the preferred delivery site from the list of delivery sites maintained by the database based on the results of the network analysis.

41. The method as recited in claim 40, further comprising the step of creating a prioritized list of preferred delivery sites based on the network analysis.

42. The method as recited in claim 41, further comprising the step of routing traffic towards underutilized regions of the network based on the network analysis results, thereby decreasing the time to download the file.

43. The method as recited in claim 42, further comprising the step of downloading a delivery site file using a configuration utility file, the delivery site file including a list of available delivery sites and a list of network tests to be run.

44. The method as recited in claim 43, further comprising the step of displaying the location of the user terminal and the locations of each delivery site by a graphical interface.

45. The method as recited in claim 44, further comprising the step of displaying the geographic and electronic distance of the delivery sites from the user terminal by the graphical interface.

46. The method as recited in claim 45 further comprising the step of displaying the user terminal and the delivery sites as "blips" superimposed over a map of the pertinent geographical region.

47. The method as recited in claim 46, further comprising the steps of:

selecting a subset of delivery sites from the list; and

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

48. The method as recited in claim 47, wherein the test is selected from a plurality of tests.

49. The method as recited in claim 48, further comprising the step of weighting the results of the network analysis test.

50. The method as recited in claim 49, wherein the weighting steps utilize weights specified in the list of delivery sites.

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

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

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

downloading the file from the preferred delivery site.

52. The method as recited in claim 51, further comprising the step of repeating the identifying and downloading steps until downloading is successful.

53. The method as recited in claim 52, further comprising the step of downloading the file from a content provider if the repeated downloading steps are unsuccessful.

54. The method as recited in claim 51, wherein the file is a graphics file.

55. The method as recited in claim 51, wherein the file is a text file.

56. The method as recited in claim 51, wherein the file is a video file.

57. The method as recited in claim 51, wherein the file is an audio file.

58. 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 graphics files throughout the network according to the determined network performance.