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

• US 7,146,429 B2
• Filed: 03/16/2001
• Issued: 12/05/2006
• Est. Priority Date: 03/16/2001
• Status: Expired due to Fees

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Michel, Bartlett Scott Hudson
• Primary Examiner(s): Pwu, Jeffrey
• Assistant Examiner(s): DENNISON, JERRY B
• Application Number:
  US09/810,303
• Publication Number:
  US 20020133570A1
• Time in Patent Office: 2,090 Days
• Field of Search: 709/238, 709/223, 709/203
• US Class Current: 709/238
• 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,

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

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, at the proximal IPA, from the source a source URL identifier,

matching, at the proximal IPA, 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, and

transmitting, from the proximal IPA, the source URL identifier to the destination at the destination IPA for 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 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,

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

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, at the proximal IPA, 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, and

transmitting, from the proximal IPA, the source URL identifier to a destination at a destination IPA for transmitting from a distal web 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.

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,

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

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

receiving, at the proximal IPA, from the user browser a source URL identifier,

matching, at the proximal IPA, the source URL identifier to a destination URL identifier,

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

transmitting, from the proximal IPA, the source URL identifier to a destination at the destination IPA for transmitting from the destination at the destination IPA the web content data for retrieving the web content data from the distal web cache.

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

repeating 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 of 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.