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

• US 20020133570A1
• Filed: 03/16/2001
• Published: 09/19/2002
• Est. Priority Date: 03/16/2001
• Status: Active Grant

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Michel, Bartlett Scott Hudson
• Granted Patent: US 7,146,429 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• 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/564 Enhancement of application control based on intercepted application data
• 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, thus reducing the time taken to fetch the requested web content data. The routing and forwarding tables in particular store decomposed web content identifiers and use compression techniques for efficient translation from a user request to the internet protocol address of the cache server where the replicated web content data can be retrieved.

Claims

1. A method for retrieving from a destination web content data specified by a source at a source internet protocol address (IPA) and corresponding to a uniform resource locator (URL) associated with a web server, the method comprising the steps of,

destination IPA storing at a proximal IPA in a forwarding table a destination IPA,

destination URL identifier storing at the proximal IPA in the forwarding table a destination URL identifier for identifying the web content data, the destination URL identifier is stored in the forwarding table in reference to the destination IPA,

receiving from the source a source URL identifier,

matching the source URL identifier to the destination URL identifier,

cross referencing at the proximal IPA in the forwarding table the stored destination URL identifier with the destination IPA,

destination URL identifier transmitting the destination URL identifier to the destination at the destination IPA, and

transmitting from the destination at the destination IPA the web content data to retrieve the web content data from the destination.

2. The method of claim 1 wherein,

the destination is a distal web cache,

the source is a user browser at a source IPA,

the source URL identifier is an exact URL,

the proximal IPA is an IPA of a proximal web cache,

the distal web cache transmits the web content data to the source at the source IPA,

the method further comprising the steps of

receiving the source IPA at the proximal web cache, and

transmitting the source IPA to the distal web cache, the distal cache transmitting the web content data to the user browser.

3. The method of claim 1 wherein,

the destination is a distal web cache,

the destination IPA is a distal web cache IPA

the source is a user browser at a source IPA,

the source URL identifier is an exact URL,

the destination URL identifier is an encoded URL,

the proximal IPA is an IPA of a proximal web cache,

the distal web cache transmits the web content data to the proximal web cache,

the method further comprising the steps of

receiving the source IPA at the proximal web cache,

transmitting the proximal IPA to the distal web cache,

receiving from the distal web cache the web content data at the proximal web cache, and

transmitting the web content data from the proximal web cache to the user browser at the source IPA.

4. The method of claim 1 wherein the destination URL identifier in the forwarding table is a series of compression codes corresponding to respective linked segments of the URL, each of the linked segments corresponding to one or more components of the URL to decompose the URL into the linked segments, the linked segments are linked by parental pointers from a first linked segment having no parental pointer through remaining linked segments having respective parental pointers to a preceding one of the linked segments to a last linked segment reference to the destination IPA.

5. The method of claim 4 wherein

the destination URL identifier references the URL comprising scheme, name, path and type components and delimiters,

the linked segments correspond to successive concatenated components of the URL and are respectively referenced to one or more of the successive concatenated components of the URL,

each of the compression codes are referenced to the linked segments and to the one or more successive concatenated components through pointers for respectively cross referencing the compression codes to the linked segments, and

the destination IPA is referenced to the destination URL identifier when the all of the respective compression codes through the respective pointers point to a complete set of linked segments from the first linked segment to the last linked segment.

6. The method of claim 5 wherein,

the proximal IPA becomes a new source IPA as the destination IPA becomes a new proximal IPA communicating the destination URL identifier to a new destination IPA all of which occurring a plurality of times for indicating a number of hops from the proximal IPA to a last one of a respective plurality of new destination IPAS, the last one of the respective plurality of new destination IPA distally storing the web content data, and

the last linked segment is further referenced to a distance metric indicating a number of hops through the new destination IPAs from the proximal IPA.

7. The method of claim 1 wherein,

the destination stores a set of web content data one of which is the web content data, the set of web content data corresponding to a wildcard URL for indicating a set of URLs one of which is the URL,

the destination URL identifier is a wildcard URL identifier,

the source URL identifier is an exact URL having a plurality of URL components a first of portion of which serving as a prefix to a remaining portion of the exact URL, and

the matching step is a prefix matching step for matching the first portion of the URL components of the exact URL to the wildcard URL identifier in the forwarding table.

8. The method of claim 7 wherein

the prefix matching step is a longest prefix matching step serving to match the longest first portion of the URL components of the exact URL to the wildcard URL among a plurality of wildcard URLs matching a shorter first portion of the URL components of the exact URL.

9. A method for retrieving from a distal cache web content data specified by a user browser at a source internet protocol address (IPA) and corresponding to a uniform resource locator (URL) associated with a web server, the method comprising the steps of,

distal IPA storing at a proximal IPA in a forwarding table a distal IPA,

distal URL identifier storing at the proximal IPA in the forwarding table a distal URL identifier for identifying the web content data, the distal URL identifier is stored in the forwarding table in reference to the distal IPA,

receiving from the user browser a source URL identifier,

matching the source URL identifier to the distal URL identifier,

cross referencing at the proximal IPA in the forwarding table the stored distal URL identifier with the distal IPA,

distal URL identifier transmitting the distal URL identifier to the distal destination at the destination IPA, and

transmitting from the distal cache at the distal IPA the web content data to retrieve the web content data from the distal web cache.

10. The method of claim 9 wherein the web content data is transmitted from the distal cache to the user browser during the transmitting step.

11. The method of claim 9 wherein,

the proximal IPA is a location of a proximal cache,

the web content data is transmitted from the distal cache to the proximal cache during the transmitting step, and

the web content data is further transmitted from the proximal cache to the user browser during the transmitting step.

13. The method of claim 12 further comprising the step of,

repeating the all of the steps one or more times, the destination is one or more intermediate cooperative web caches having a respective one or more intermediate IPAs and respectively storing the distal URL identifier with a respective next one of the one or more intermediate IPAs and lastly the distal IPA, each of the one or more intermediate IPAs being a location a next one of the one or more intermediate cooperative web caches and lastly the distal IPA, the one or more intermediate IPAs indicating next web hop locations in transmitting the distal URL through the intermediate cooperative web caches to the distal web cache, the last one of one or more intermediate cooperative web caches referencing the distal URL to the distal IPA for retrieving the web content data from the distal cache.

14. The method of claim 13 wherein the repeated transmitting step,

the web content data is transmitting from the distal cache through the one or more intermediate web caches and through a proximal cache at the proximal IPA to the user browser.

15. The method of claim 14 further comprising the step of,

assigning the proximal cache and one or more intermediate caches and the distal cache to one or more groups of cooperative caches in a network of grouped cooperative web caches, the web content data being transmitted from a first one of the one or more intermediate caches to a second one of the one or more intermediate caches, the first one and second one of the one or more intermediate caches being within the same group.

12. A method for retrieving from a distal web cache web content data specified by a user browser at a source internet protocol address (IPA) and corresponding to a uniform resource locator (URL) associated with a web server, the method comprising the steps of,

destination IPA storing at a proximal IPA in a forwarding table a distal IPA,

distal URL identifier storing at the proximal IPA in the forwarding table a distal URL identifier for identifying the web content data stored in the distal cache, the distal URL identifier is stored in the forwarding table in reference to the destination IPA,

receiving from the user browser a source URL identifier,

matching the source URL identifier to the destination URL identifier,

cross referencing at the proximal IPA in the forwarding table the stored distal URL identifier with the destination IPA,

distal URL identifier transmitting the distal URL identifier to the destination at the destination IPA, and

transmitting from the destination at the destination IPA the web content data for retrieving the web content data from the distal cache.