Cooperative adaptive web caching routing and forwarding web content data broadcasting method

• US 7,555,561 B2
• Filed: 03/19/2001
• Issued: 06/30/2009
• Est. Priority Date: 03/19/2001
• Status: Expired due to Fees

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Michel, Bartlett Scott Hudson
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): DIVECHA, KAMAL B
• Application Number:
  US09/812,139
• Publication Number:
  US 20020143984A1
• Time in Patent Office: 3,025 Days
• Field of Search: 709238-242, 709/203, 709213-216, 709/250, 709/201, 709/217, 709/226, 709/229
• US Class Current: 709/238
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

Adaptive cooperative web caches construct and maintain routing and forwarding tables for efficient location of replicated web content data. The data stored in routing and forwarding tables indicate associations between web content requests and the internet protocol address of the web cache server where the replicated web content data is stored. These associations are communicated between groups of adaptive web cache servers by broadcasting routing information for updating the forwarding tables within the web cache servers for efficient location of sought after web content data.

Claims

1. A method of broadcasting from a proximal cache at a proximal internet protocol address (IPA) forwarding and routing information for indicating an originator storing web content data associated with an originating uniform resource locator (URL) of a web server at an originating IPA permanently storing the web content data, the method comprising the steps of:

generating at the proximal IPA the originating URL for indicating the originator,

generating at the proximal IPA a sourcing IPA for indicating the originator,

generating at the proximal IPA a destination IPA for indicating a destination cache,

generating a distance metrics for indicating a web hop distance of a number of the plurality of cooperative web caches through which the URL web content data would be communicated from a source at the sourcing IPA through a plurality of cooperative web caches to the proximal web cache at the proximal IPA,

associating at the proximal IPA the sourcing IPA with the originating URL with the distance metric as the forwarding and routing information,

transmitting the forwarding and routing information from the proximal cache at the proximal IPA to the destination cache at a destination IPA, the transmitting of the forwarding and routing information associating the sourcing IPA with the originating URL with the destination IPA with the distance metric, for generating a forwarding and routing table in the destination cache, and

storing in the destination cache at the destination IPA in a forwarding and routing table the association between the originating URL and the sourcing IPA with the distance metric, the forwarding and routing table for determining the sourcing IPA from a URL request for forwarding and routing a request for web content data to the sourcing IPA.

2. The method of claim 1 wherein,

the originating URL is a proximal URL, the sourcing IPA is the proximal IPA, the proximal cache stores locally the web content data, and

the distance metric is one indicating that one web hop is between the destination cache to the proximal cache.

3. The method of claim 1 wherein, the originating URL is the source,

the sourcing IPA indicates an IPA location of the source distally storing the web content data,

the distance metric is greater than one indicating a number greater than one of the number of web hops between the destination cache through the proximal cache to the source distally storing the web content data.

4. The method of claim 3 wherein,

the source is the web server distally and permanently storing the web content data, and

the sourcing IPA is a web server IPA indicating the IPA location of the web server.

5. The method of claim 1 wherein,

the originating URL is selected from the group consisting of

an exact URL comprising a plurality of URL components,

a wildcard URL comprising a plurality of URL components a last URL component of which being a wildcard component, and

a coded URL being a coded URL comprising a series of hashing codes of a decomposed URL being a decomposition of the URL selected from the group consisting of either an exact URL or a wildcard URL each of which comprising a series of URL components, the series of hashing codes being a sequence of hashing codes of respective URL segments of a respective series of increasingly concatenated URL components of the series of URL components of the URL.

15. The method of claim 1 wherein,

the forwarding and routing information is communicated in a packet comprising a routing item associating the sourcing IPA and the originating URL.

16. The method of claim 1, wherein

the forwarding and routing information is unilaterally communicated from the proximal cache to the destination cache in a routing packet.

6. A method of broadcasting from a proximal cache at a proximal internet protocol address (IPA) forwarding and routing information for indicating a distal web cache storing web content data associated with a uniform resource locator (URL) of a web server permanently storing the web content data, a proximal web cache is a first one of a plurality of cooperative web caches, the distal web cache is a last one of the plurality of cooperative web caches, the method comprising the steps of:

generating at the proximal IPA a distal URL for indicating the web content data of the distal URL stored in the distal web cache,

generating at the proximal IPA the proximal IPA for indicating the location of the proximal cache,

generating at the proximal IPA a destination IPA for indicating a destination cache,

generating at the proximal IPA a distance metric for indicating a web hop distance of any number of the plurality of cooperative web caches through which the web content data would be communicated from the distal web cache to the destination web cache,

associating at the proximal IPA the proximal IPA and the distal URL and the distance metric as the forwarding and routing information, and

transmitting the routing information from the proximal cache at the proximal IPA to the destination cache at a destination IPA, the transmitting of the forwarding and routing information associating the sourcing IPA with the originating URL with the destination IPA with the distance metric for generating a forwarding and routing table in at least one of the plurality of cooperative web caches, and

storing in the destination cache at the destination IPA in a forwarding and routing table the association between the originating URL with the distance metric with the sourcing IPA, the forwarding and routing table for determining the sourcing IPA from a URL request for forwarding and routing a request for web content data to the sourcing IPA.

7. The method of claim 6 wherein,

the distance metric is greater than one indicating a number greater than one of the number of web hops between the destination cache through the proximal cache to the distal web cache storing the web content data.

8. The method of claim 6 wherein, the distal URL is selected from the group consisting of:

an exact URL comprising a plurality of URL components,

a wildcard URL comprising a plurality of URL components a last URL component of which being a wildcard component, and

a coded URL being a coded URL comprising a series of hashing codes of a decomposed URL being a decomposition of the exact URL or the wildcard URL, the series of hashing codes being a sequence of hashing codes of respective URL segments of a respective series of increasingly concatenated URL components of the series of URL components of the exact URL or the wildcard URL.

9. The method of claim 6 further comprising the steps of:

repeating the distal URL generating step, proximal IPA generating step, distance metric generating step, the associating step, a plurality of times for generating a plurality of forwarding and routing information each comprising a distal URL and a respective distance metric, and

incorporating the plurality of forwarding and routing information within a protocol data structure within a routing packet prior to the transmitting step, the routing protocol packet comprising the distal URL and a respective distance metric and comprising the proximal IPA and the destination IPA.

10. A method of broadcasting from a proximal cache at a proximal internet protocol address (IPA) forwarding and routing information for indicating a distal web cache storing web content data associated with an originating uniform resource locator (URL) of a web server permanently storing the web content data, a proximal web cache is a first one of a plurality of cooperative web caches, the distal web cache is a last one of the plurality of cooperative web caches, the method comprising the steps of:

storing at the proximal IPA in a forwarding and routing table a plurality of originating URLs cross referenced to a respective plurality of distance metrics,

generating at the proximal IPA a URL identifier of the plurality of originating URLs, the originating URL for indicating the web content data of the originating URL stored in the distal web cache,

generating at the proximal IPA the proximal IPA for indicating the location of the proximal cache,

generating at the proximal IPA a destination IPA for indicating a destination cache,

generating at the proximal IPA a distance metric by cross referencing the originating URL to one of the plurality of originating URLs and to a respective one of the plurality of distance metrics for indicating a web hop distance of any number of the plurality of cooperative web caches through which the web content data would be communicated from the distal web cache to the destination web cache,

associating the proximal IPA and the originating URL and the distance metric as the forwarding and routing information,

transmitting the forwarding and routing information in a routing packet within a routing protocol from the proximal cache at the proximal IPA to the destination cache at a destination IPA, the transmitting of the forwarding and routing information associating the proximal IPA with the originating URL with the destination IPA with the distance metric, for generating a forwarding and routing table in one of a plurality of cooperative web caches, and

storing at the destination IPA a forwarding and routing table for cross referencing the plurality of originating URLs to the plurality of distance metrics and to one or more juxtaposed cooperative web caches IPAs of one or more juxtaposed cooperative web caches of the plurality of cooperative web caches, the one or more juxtaposed cooperative web caches for forwarding and routing originating URLs to distal web caches storing the web content data of the respective plurality of originating URLs.

11. The method of claim 10 wherein,

the originating URL is selected from the group consisting of:

an exact URL comprising a plurality of URL components,

a wildcard URL comprising a plurality of URL component a last URL component of which being a wildcard component, and

a coded URL comprising a series of hashing codes of a decomposed URL being a decomposition of the exact URL or the wildcard URL, the series of hashing codes being a sequence of hashing codes of respective hashing of URL segments of a respective series of increasingly concatenated URL components or the series of URL components of the exact URL or the wildcard URL.

12. The method of claim 10 further comprising the steps of:

repeating the original URL generating step, proximal IPA generating step, distance metric generating step, and associating step, a plurality of times for generating a plurality of routing information each comprising an originating URL and a respective distance metric, and

incorporating the plurality of routing information within a protocol data structure within the routing packet prior to the transmitting step, the routing protocol packet comprising the originating URL and the respective distance metric and comprising the proximal IPA and the destination IPA.

13. The method of claim 10 wherein,

the proximal cache and the one or more juxtaposed cooperative web caches being within a local group of cooperative web caches.

14. The method of claim 13 wherein,

the proximal cache is within one or more local groups of cooperative web caches.