Method and apparatus for optimal rebasing of web page transmission using a plurality of different rebasing tests and a Cost-Effectiveness determination

• US 6,260,066 B1
• Filed: 10/19/1999
• Issued: 07/10/2001
• Est. Priority Date: 03/17/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Munson, Jonathan Paul, Bittinger, Reed Richard, Lindquist, David Bruce, Housel, Barron Cornelius III
• Primary Examiner(s): Meky, Moustafa M.
• Assistant Examiner(s): Kupstas, Tod
• Application Number:
  US09/421,079
• Time in Patent Office: 630 Days
• Field of Search: 709/224, 709/203, 709/206, 709/205, 709/204, 709/231, 709/232, 709/233, 709/234, 707/203
• US Class Current: 709/224
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation

Abstract

A method of updating or rebasing templates for information sent across a relatively slow transmission link such that only changed information is transmitted across the links. In addition, the information is updated such that the information transmitted across the links is minimized by updating the templates based on the characteristics of the data being sent. 7

Claims

1. In a computer network containing wireless communications connections, a method for optimizing transmission of information across a wireless link, comprising the steps of:

identifying an information base form as a template for transmission of information from a first computer to a second computer;

comparing information to be sent across said wireless link from said first computer to said second computer with said information base form, said comparing step calculating a difference between said information base form and said information to be sent;

performing a plurality of different rebasing tests to detect whether a rebase of said information base form is indicated;

determining whether said rebase is cost-effective when said rebase is indicated, wherein said rebase is cost-effective if said rebase results in a lower cost of sending said information across said wireless link than not rebasing;

sending said calculated difference from said first computer to said second computer;

updating said information base form with said information to be sent when said rebase is indicated and said rebase is cost-effective; and

sending a rebasing indicator from said first computer to said second computer when said rebase is indicated and said rebase is cost-effective, along with said calculated difference.

2. The method as in claim 1, wherein said step of determining whether said rebase is cost-effective further comprises the steps of:

determining a cost of rebasing; and

determining an average number of requests between rebases; and

further comprising the step of concluding that said rebase is cost-effective only if the average number of requests between rebases exceeds the cost of rebasing.

7. The method as in claim 1, wherein said performing a plurality of different rebasing tests step further comprises the step of performing a sharp increase detection test.

8. The method as in claim 7, wherein said performing said sharp increase detection test step further comprises the steps of:

computing a mean difference since a last rebase;

comparing said computed mean difference to a detection threshold;

recomputing said detection threshold when said computed mean difference is not greater than said detection threshold;

determining whether said detection threshold has been exceeded a predetermined number of times when said computed mean difference is greater than said detection threshold; and

concluding that said rebase is indicated when said determining whether said detection threshold has been exceeded step has a positive result.

9. The method as in claim 1, wherein said performing a plurality of different rebasing tests step further comprises the step of performing a gradual increase detection test.

10. The method as in claim 9, wherein said performing said gradual increase detection test step further comprises the steps of:

incrementing a response counter;

comparing said response counter to a sampling value to determine whether a sample should be taken; and

taking said sample when said comparing step determines that said response counter is greater than said sampling value, further comprising the steps of;

determining whether a current average of differences is greater than a historical difference of averages plus a predetermined threshold; and

concluding that said rebase is indicated when said determining whether said current average is greater step has a positive result.

19. The method as in claim 2, wherein said step of determining said cost of rebasing further comprises the steps of:

multiplying a number of clients expected to request said information to be transmitted before a next rebasing of said base form by a mean size of a recent sample of response differences, resulting in a first product;

subtracting an estimate of an expected mean difference size if said next rebasing occurred from said mean size of said recent sample, resulting in a first difference; and

dividing said first product by said first difference, resulting in said cost of rebasing.

3. A computer communication system for optimizing transmission of information from a first computer of a plurality of computers connected together with communications links to a second computer of said plurality, said transmission occurring across said communications links, said system comprising:

means for identifying a base form used as a template at said first computer;

means for calculating a difference between said information to be transmitted and said base form template;

means for calculating a size of said difference between said information to be transmitted and said base form template;

means for performing a plurality of different rebasing tests to detect whether a rebase of said base form template is indicated;

means for determining whether said rebase is cost-effective when said rebase is indicated, wherein said rebase is cost-effective if said rebase results in a lower cost of sending said information across said wireless link than not rebasing;

means for transmitting said calculated difference from said first computer to said second computer;

means for updating said base form template with said information to be transmitted when said rebase is indicated and said rebase is cost-effective; and

means for transmitting a rebase indicator from said first computer to said second computer when said rebase is indicated and said rebase is cost-effective, along with said calculated difference.

4. The computer communication system as claimed in claim 3, wherein said means for determining whether said rebase is cost-effective further comprises:

means for programmatically determining a cost of updating said template; and

means for programmatically determining an average number of requests between updates to said template; and

further comprising means for concluding that said rebase is cost-effective if said average number of request between updates exceeds said cost of updating said template.

11. The system as in claim 3, wherein said means for performing a plurality of different rebasing tests further comprises means for performing a sharp increase detection test.

12. The system as in claim 11, wherein said means for performing said sharp increase detection test further comprises:

means for computing a mean difference since a last rebase;

means for comparing said computed mean difference to a detection threshold;

means for recomputing said detection threshold when said computed mean difference is not greater than said detection threshold;

means for determining whether said detection threshold has been exceeded a predetermined number of times when said computed mean difference is greater than said detection threshold; and

means for concluding that said rebase is indicated when said means for determining whether said detection threshold has been exceeded has a positive result.

13. The system as in claim 3, wherein said means for performing a plurality of different rebasing tests further comprises means for performing a gradual increase detection test.

14. The system as in claim 13, wherein said means for performing said gradual increase detection test further comprises:

means for incrementing a response counter;

means for comparing said response counter to a sampling value to determine whether a sample should be taken; and

means for taking said sample when said means for comparing determines that said response counter is greater than said sampling value, further comprising;

means for determining whether a current average of differences is greater than a historical difference of averages plus a predetermined threshold; and

means for concluding that said rebase is indicated when said means for determining whether said current average is greater has a positive result.

20. The computer communication system as in claim 4, wherein said first means for programmatically determining said cost of updating said template further comprises:

means for multiplying a number of clients expected to request said information to be transmitted before a next rebasing of said base form by a mean size of a recent sample of response differences, resulting in a first product;

means for subtracting an estimate of an expected mean difference size if said next rebasing occurred from said mean size of said recent sample, resulting in a first difference; and

means for dividing said first product by said first difference, resulting in said cost of updating said template.

5. A program product residing on a machine readable medium, said program product comprising:

machine readable means for connecting together a plurality of computers with communications links, said plurality of computers having a first computer and a second computer;

programmable means for transmitting information from said first computer to said second computer across said communications links, said programmable means further comprising;

programmatic means for identifying a base form used as a template at said first computer;

programmatic means for calculating a difference between said information to be transmitted and said base form template;

programmatic means for calculating a size of said difference between said information to be transmitted and said base form template;

programmatic means for performing a plurality of different rebasing tests to detect whether a rebase of said base form template is indicated;

programmatic means for determining whether said rebase is cost-effective when said rebase is indicated, wherein said rebase is cost-effective if said rebase results in a lower cost of sending said information across said wireless link than not rebasing;

programmatic means for transmitting said calculated difference from said first computer to said second computer;

programmatic means for updating said base form template with said information to be transmitted when said rebase is indicated and said rebase is cost-effective; and

programmatic means for transmitting a rebase indicator from said first computer to said second computer when said rebase is indicated and said rebase is cost-effective, along with said calculated difference.

6. The program product as claimed in claim 5, wherein said programmatic means for determining whether said rebase is cost-effective further comprises:

programmatic means for determining a cost of updating said template; and

programmatic means for determining an average number of requests between updates to said template; and

further comprising programmatic means for concluding that said rebase is cost-effective if said average number of requests between updates to said template exceeds said cost of updating said template.

15. The program product as in claim 5, wherein said programmatic means for performing a plurality of different rebasing tests further comprises programmatic means for performing a sharp increase detection test.

16. The program product as in claim 15, wherein said programmatic means for performing said sharp increase detection test further comprises:

programmatic means for computing a mean difference since a last rebase;

programmatic means for comparing said computed mean difference to a detection threshold;

programmatic means for recomputing said detection threshold when said computed mean difference is not greater than said detection threshold;

programmatic means for determining whether said detection threshold has been exceeded a predetermined number of times when said computed mean difference is greater than said detection threshold; and

programmatic means for concluding that said rebase is indicated when said programmatic means for determining whether said detection threshold has been exceeded has a positive result.

17. The program product as in claim 5, wherein said programmatic means for performing a plurality of different rebasing tests further comprises programmatic means for performing a gradual increase detection test.

18. The program product as in claim 17, wherein said programmatic means for performing said gradual increase detection test further comprises:

programmatic means for incrementing a response counter;

programmatic means for comparing said response counter to a sampling value to determine whether a sample should be taken; and

programmatic means for taking said sample when said programmatic means for comparing determines that said response counter is greater than said sampling value, further comprising;

programmatic means for determining whether a current average of differences is greater than a historical difference of averages plus a predetermined threshold; and

programmatic means for concluding that said rebase is indicated when said programmatic means for determining whether said current average is greater has a positive result.

21. The program product as in claim 6, wherein said first programmatic means for determining said cost of updating said template further comprises:

programmatic means for multiplying a number of clients expected to request said information to be transmitted before a next rebasing of said base form by a mean size of a recent sample of response differences, resulting in a first product;

programmatic means for subtracting an estimate of an expected mean difference size if said next rebasing occurred from said mean size of said recent sample, resulting in a first difference; and

programmatic means for dividing said first product by said first difference, resulting in said cost of updating said template.