Close
Home
Collections
Login
USC Login
Register
0
Selected
Invert selection
Deselect all
Deselect all
Click here to refresh results
Click here to refresh results
USC
/
Digital Library
/
University of Southern California Dissertations and Theses
/
Enhancing network object caches through cross -domain prediction
(USC Thesis Other)
Enhancing network object caches through cross -domain prediction
PDF
Download
Share
Open document
Flip pages
Contact Us
Contact Us
Copy asset link
Request this asset
Transcript (if available)
Content
ENHANCING NETWORK OBJECT CACHES THROUGH CROSS-DOMAIN PREDICTION Copyright 2002 by Amy Suzanne Hughes A Dissertation Presented to the FACULTY OF THE GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY (COMPUTER SCIENCE) December 2002 Amy Suzanne Hughes Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. UMI Number: 3093774 Copyright 2002 by Hughes, Amy Suzanne All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3093774 Copyright 2003 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.O. Box 1346 Ann Arbor, Ml 48106-1346 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. UNIVERSITY OF SOUTHERN CALIFORNIA THE GRADUATE SCHOOL UNIVERSITY PARK LOS ANGELES, CALIFORNIA 90089-1695 This dissertation, written by under the direction o f ht*f" dissertation committee, and approved by all its members, has been presented to and accepted by the Director o f Graduate and Professional Programs, in partial fulfillment o f the requirements fo r the degree of D OCTOR O F PHILOSOPHY V /1 Director D a t e - De-rre m b e -r- 1 8 ,—2 0 0 2 Dissertation Committee Chair Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Acknowledgements I’d like to thank the Mawrtyr List and to Mooses International for distractions and support throughout the past seven years. In particular, love and mooses to Kathleen Jones and Susan Wood. Many thanks to my family - my own personal cheering section. I’d also like to thank the T-Troup for being guinea pigs, testing software, speedy editing feedback, and commiserating, especially in the last few months. Special thanks to Lars Eggert and Yushun Wang who are slogging through this process right behind me, and to Alba Regalado-Palacios and Jeanine Yamazaki for helping with the “small” details, like navigating administrivia. And, thank you to my advisor, Joe Touch, for encouragement, guidance, patience, and setting exhaustingly high standards. Finally, my sincerest love and gratitude to my husband, Scott, for all the love, advice, support, hand-holding, and firms kicks in the butt. And for knowing when I just needed ice cream with sprinkles and a mini-vacation, kiv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table of Contents Acknowledgements.................................................................................................................ii List of Tables.......................................................................................................................... ix List of Figures......................................................................................................................... xi Abstract.................................................................................................................................xvii 1 Introduction......................................................................................................................1 2 Modeling Predictive Applications................................................................................ 7 2.1 Benefits and Costs of Prediction...........................................................................9 2.2 Predictor Functions................................................................................................ 11 2.2.1 Usage Relationships..................................................................................... 12 2.2.2 Syntax Relationships....................................................................................13 2.2.3 Semantic Relationships................................................................................16 2.3 Timeliness of Predictors....................................................................................... 17 2.4 Models of Predictive Applications......................................................................19 2.4.1 Reuse Predictions.........................................................................................20 2.4.2 Extended Use Predictions............................................................................22 2.4.3 Delayed Use Predictions..............................................................................25 2.4.4 New Use Predictions................................................................................... 27 2.5 Composing Predictions and Multi-Object Predictions..................................... 28 2.6 Summary................................................................................................................. 34 3 Cross-Domain Predictors............................................................................................. 35 iii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.1 Abstract Model of Cross-Domain Prediction....................................................36 3.2 2-Domain Predictors............................................................................................. 39 3.2.1 Inferred R euse............................................................................................. 42 3.2.1.1 Reuse — » • Reuse........................................................................................42 3.2.1.2 Extend — > Reuse.......................................................................................43 3.2.1.3 Delay — > Reuse.........................................................................................44 3.2.1.4 New Use — > Reuse................................................................................... 45 3.2.2 Inferred Extended U se................................................................................46 3.2.2.1 Reuse — » Extend......................................................................................46 3.2.2.2 Extend — > Extend.................................................................................... 48 3.2.2.3 Delay — > Extend...................................................................................... 49 3.2.2.4 New Use — > Extend.................................................................................49 3.2.3 Inferred Delayed Use.................................................................................. 50 3.2.3.1 Reuse — > Delay........................................................................................51 3.2.3.2 Extend — > D elay.......................................................................................52 3.2.3.3 Delay — » • Delay.........................................................................................53 3.2.3.4 New Use — » Delay................................................................................... 54 3.2.4 Inferred New U se........................................................................................54 3.2.4.1 Reuse — > • New Use.................................................................................. 55 3.2.4.2 Extend — > New U se.................................................................................56 3.2.4.3 Delay — > New Use................................................................................... 57 3.2.4.4 New Use — > New Use..............................................................................58 iv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.3 Cross-Domain Prediction Opportunities............................................................59 3.3.1 Web-DNS Prediction................................................................................... 60 3.3.2 E-mail-Web Prediction...............................................................................62 3.4 Multi-Domain Predictors..................................................................................... 64 3.4.1 Multiple Source Predictions in Series.......................................................64 3.4.2 3-Domain Prediction................................................................................... 65 3.4.3 Asymmetric M appings................................................................................66 3.4.4 Hybrid Predictions........................................................................................67 3.5 Summary.................................................................................................................69 4 Issues in Prediction and Related Work...................................................................... 71 4.1 Prediction Agents................................................................................................. 72 4.1.1 Prediction Generation.................................................................................. 73 4.1.2 Prediction Execution................................................................................... 73 4.1.3 Intermediate Agents......................................................................................74 4.1.4 Agents in Web Prediction............................................................................76 4.2 Predictive Information..........................................................................................76 4.2.1 Object Characteristics.................................................................................. 78 4.2.2 Pattern-Based Prediction.............................................................................78 4.2.3 Reactive Predictions.................................................................................... 79 4.3 Prediction Resources............................................................................................80 4.4 Prediction and Failure...........................................................................................81 4.5 Prediction Types................................................................................................... 83 v Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.5.1 Reuse Predictions..........................................................................................83 4.5.2 Extended Use Predictions............................................................................ 84 4.5.3 Delayed Use Predictions...............................................................................84 4.5.4 New Use Predictions....................................................................................84 4.5.5 Cross-Domain Predictions........................................................................... 85 4.6 Summary.................................................................................................................86 5 Investigating Web-DNS Prediction............................................................................ 88 5.1 DNS Overhead in Web Requests.......................................................................90 5.1.1 LAN-Connected DNS Server (Cases 1 and 2 ) ......................................... 93 5.1.2 ISDN-Connected DNS Server (Cases 3 and 4 )........................................ 95 5.2 Web Server Name Reuse and DNS Optimization............................................ 98 5.3 International Requests........................................................................................104 5.4 Web-DNS Summary........................................................................................... 106 6 E-mail-Web Design and Implementation.................................................................108 6.1 Design Approach.................................................................................................109 6.2 Implementation....................................................................................................I l l 6.2.1 Mozilla..........................................................................................................116 6.2.2 Apache..........................................................................................................120 6.2.3 E-mail Relays..............................................................................................122 6.2.3.1 POP3 relay..............................................................................................123 6.2.3.2 IMAP relay.............................................................................................125 6.2.4 Preloader.......................................................................................................127 vi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 6.3 Installation and Configuration...........................................................................128 6.4 Summary...............................................................................................................129 7 E-mail-Web Analysis.................................................................................................130 7.1 Results..................................................................................................................130 7.1.1 Request Sources..........................................................................................131 7.1.2 E-mailed URLs...........................................................................................136 7.1.3 E-mail URL Prefetching...........................................................................140 7.2 Discussion............................................................................................................ 143 7.2.1 Web Prefetching.........................................................................................143 7.2.1.1 Benefits....................................................................................................145 7.2.1.2 Prerequisites........................................................................................... 145 7.2.1.3 Implementation Issues........................................................................... 147 7.2.1.3.1 Client Changes................................................................................148 7.2.1.3.2 Server Changes................................................................................148 7.2.1.3.3 Protocol Changes............................................................................ 149 7.2.1.4 Effects of Full Implementation............................................................150 7.2.1.5 Remaining Issues....................................................................................151 7.2.2 Cross-Domain Prediction..........................................................................153 7.2.2.1 Prerequisites........................................................................................... 153 7.2.2.2 Implementation Issues..........................................................................154 7.2.2.2.1 Client Changes...............................................................................154 7.2.2.2.2 Server Changes................................................................................ 155 vii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1.2.2.23 Protocol changes............................................................................. 155 7.2.2.3 Effects of Full Implementation............................................................156 1.2.2.4 Remaining Issues...................................................................................156 7.3 Summary..............................................................................................................157 8 Conclusions...................................................................................................................159 9 Bibliography................................................................................................................. 162 Appendix A E-mail-Web System Design.....................................................................172 A. 1 Approach and Analysis Requirements............................................................172 Data Collection Requirements...................................................................................176 Implementation Requirements...................................................................................176 A.2 Implementation Candidates.............................................................................. 176 A.3 Summary..............................................................................................................182 viii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. List of Tables Table 2.1: Base Predictors....................................................................................................34 Table 3.1: Base Predictors....................................................................................................40 Table 3.2: All 2-Domain Predictions.................................................................................. 40 Table 3.3: Valid Recurrence Predictions............................................................................41 Table 3.4: Valid New Use Sources..................................................................................... 41 Table 3.5: Inferred Reuse Predictions................................................................................42 Table 3.6: Reuse — > Reuse Prediction................................................................................42 Table 3.7: Extend — > Reuse Prediction..............................................................................43 Table 3.8: Delay — » Reuse Prediction................................................................................44 Table 3.9: New Use -» Reuse Prediction...........................................................................45 Table 3.10: Inferred Extended Use Predictions.................................................................46 Table 3.11: Reuse — > Extend Prediction............................................................................46 Table 3.12: Extend — » Extend Prediction...........................................................................48 Table 3.13: Delay -» Extend Prediction.............................................................................49 Table 3.14: New Use -» Extend Prediction...................................................................... 49 Table 3.15: Inferred Delayed Use Predictions.................................................................. 51 Table 3.16: Reuse — > Delay Prediction..............................................................................51 Table 3.3: Extend — » Delay Prediction............................................................................... 52 Table 3.3: Delay -» Delay Prediction................................................................................ 53 Table 3.3: New Use — > Delay Prediction...........................................................................54 ix Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 3.3: Inferred New Use Predictions...........................................................................55 Table 3.3: Reuse — > New Use Prediction...........................................................................55 Table 3.3: Extend — > New Use Prediction.........................................................................56 Table 3.3: Delay -» New Use Prediction...........................................................................57 Table 3.3: New Use -» New Use Prediction..................................................................... 58 Table 4.1: Web Prediction Generation and Execution.....................................................77 Table A .l: Solution Comparison....................................................................................... 182 x Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. List of Figures Figure 1.1: Cross-Domain Representation of Web-DNS Prediction................................ 5 Figure 2.1: Sequential Relationships between Application Objects...............................12 Figure 2.2: Parallel and Sequential Relationships between Application Objects 13 Figure 2.3: Example of HTML Parallel and Sequential Relationships.......................... 13 Figure 2.4: Data Dependencies in HTML Files................................................................ 14 Figure 2.5: Predictive Models of HTML Files.................................................................. 15 Figure 2.6: Data Dependencies in DNS Records.............................................................. 15 Figure 2.7: Sequential Use of DNS Records......................................................................16 Figure 2.8: Temporal Breakdown of Predictors................................................................ 17 Figure 2.9: Late Prediction...................................................................................................18 Figure 2.10: Desired Tim ing................................................................................................18 Figure 2.11: Annotated Predictive M odel.......................................................................... 19 Figure 2.12: Reuse Model - URL Reuse in Web Browser Caching.............................. 21 Figure 2.13: Predict New Use in Another Path.................................................................22 Figure 2.14: Reuse Model - URL Reuse in Web Proxy Caching...................................22 Figure 2.15: Extended Use Model.......................................................................................23 Figure 2.16: Reuse Model - Linear Reuse of Destination Server (incorrect)...............24 Figure 2.17: Subsequent Connections to Server A (Ports P and Q )............................... 24 Figure 2.18: Extended Use Model - Extended Port Use in Persistent Connections ....25 Figure 2.19: Delayed Use Model.........................................................................................25 xi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 2.20: Reuse Model - Reuse of Packet Headers (incorrect)................................. 26 Figure 2.21: Delayed Use Model - Delayed Packet Header Use in Packet Aggregation ........................................................................................................................................ 27 Figure 2.22: New Use Model - New Use in Web Prefetch............................................. 28 Figure 2.23: Non-Contiguous Series of New Use Predictions........................................29 Figure 2.24: Contiguous New Use Predictions.................................................................30 Figure 2.25: Contiguous Extend Predictions..................................................................... 30 Figure 2.26: Contiguous Extend - Delay Predictions (non-sensical)............................. 31 Figure 2.27: Contiguous Delay - Extend Predictions...................................................... 31 Figure 2.28: A Series of Two Delay Predictions Separated by Reuse...........................32 Figure 2.29: Multiple Target Predictions...........................................................................33 Figure 2.30: A Series Predicts a New U se.........................................................................33 Figure 2.31: An Object Predicts a Series............................................................................33 Figure 3.1: Abstract Cross-Domain M odel...................................................................... 37 Figure 3.2: Homomorphism Prediction.............................................................................37 Figure 3.3: Homomorphism Prediction Detail.................................................................38 Figure 3.4: Reuse — > Reuse Prediction..............................................................................43 Figure 3.5: Extend -» Reuse Prediction........................................................................... 44 Figure 3.6: Delay -» Reuse Prediction..............................................................................45 Figure 3.7: New Use -> Reuse Prediction........................................................................46 Figure 3.8: Reuse -» Extend Prediction........................................................................... 47 Figure 3.9: Extend — » Extend Prediction.......................................................................... 48 xii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 3.10: Delay — » Extend Prediction..........................................................................49 Figure 3.11: New Use — > Extend Prediction.................................................................... 50 Figure 3.12: Reuse -» Delay Prediction............................................................................51 Figure 3.13: Extend — » Delay Prediction..........................................................................52 Figure 3.14: Delay -» Delay Prediction............................................................................53 Figure 3.15: New Use — > Delay Prediction...................................................................... 54 Figure 3.16: Reuse — » New Use Prediction...................................................................... 56 Figure 3.17: Extend -* New Use Prediction.................................................................... 57 Figure 3.18: Delay — » New Use Prediction...................................................................... 58 Figure 3.19: New Use — > New Use Prediction.................................................................59 Figure 3.20: Web — » DNS Prediction Overview..............................................................60 Figure 3.21: Web -> DNS Prediction (New Use -» New U se).......................................61 Figure 3.22: E-mail — > Web Prediction Overview.......................................................... 62 Figure 3.23: E-mail — > ■ Web Prediction (Extend -» New Use)........................................63 Figure 3.24: Multiple Source Predictions in Series......................................................... 65 Figure 3.25: 3-Domain Prediction......................................................................................66 Figure 3.26: 3-Domain Prediction with Asymmetric Mappings....................................67 Figure 3.27: 3-Domain Prediction with Multiple Source Predictors in Series..............68 Figure 3.28: Multiple Sources Hybrid Prediction........................................................... 69 Figure 5.1: DNS and Web Request Interaction................................................................. 89 Figure 5.2: Web Connection Components.........................................................................92 xiii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 5.2: Extended DNS Request.....................................................................................92 Figure 5.3: Network Diagram for LAN with Remote Requests......................................94 Figure 5.4: Case 1 - Web Connection Breakdown for LAN with Remote Requests .. 94 Figure 5.5: Network Diagram for LAN with Local Requests......................................... 95 Figure 5.6: Case 2 - Web Connection Breakdown for LAN with Local Requests...... 95 Figure 5.7: Network Diagram for ISDN with Remote Requests.....................................96 Figure 5.8: Case 3 - Web Connection Breakdown for ISDN with Remote Requests . 96 Figure 5.9: Network Diagram for ISDN with Local Requests........................................ 97 Figure 5.10: Case 4 - Web Connection Breakdown for ISDN with Local Requests... 97 Figure 5.11: Web — > DNS Prediction Overview...............................................................99 Figure 5.12: Maximum Hit Probability per Size of Cache.............................................100 Figure 5.13: DNS Cache Size over Tim e.........................................................................101 Figure 5.14: Size of Anticipation Cache Compared to Size of Simple Cache 102 Figure 5.15: Proportion of DNS Requests Satisfied by Cache...................................... 103 Figure 5.16: DNS Miss Rate Reduction........................................................................... 103 Figure 5.17: Daily Distribution of Requests and Servers in Squid L ogs.....................105 Figure 6.1: Browser Interaction with Web and E-mail Servers.................................... 109 Figure 6.2: E-mail — > Web Prediction (Extend — » New Use)...................................... 110 Figure 6.3: E-mail and Web Downloads without Intermediaries..................................112 Figure 6.4: E-mail and Web Downloads with Web Proxy............................................113 Figure 6.5: E-mail Preloading System.............................................................................114 Figure 6.6: Temporal Breakdown of Requests................................................................ 115 xiv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 6.7: Preloading System Revisited - Mozilla Highlighted..................................116 Figure 6.8: Preloading System Revisited - Apache Highlighted..................................121 Figure 6.9: Preloading System Revisited - E-mail Relay Highlighted........................ 123 Figure 6.10: POP3 Relay Pseudocode.............................................................................. 124 Figure 6.11: parse urls Pseudocode..................................................................................125 Figure 6.12: imaprelay.pl Pseudocode............................................................................ 126 Figure 6.13: Preloading System Revisited - Preloader Highlighted............................ 127 Figure 6.14: Preloader Pseudocode...................................................................................128 Figure 7.1: URL Source Breakdown................................................................................ 132 Figure 7.2: Non-Predicted Requests from E-mailed URLs............................................135 Figure 7.3: Cumulative Frequency of Non-Predicted URLs......................................... 136 Figure 7.4: Frequency of URLs in Received E-mail Messages.................................... 137 Figure 7.5: Type of URLs Received in E-mail Messages..............................................137 Figure 7.6: Type of SRC URLs Received in E-mail M essages.................................... 138 Figure 7.7: Cumulative Frequency of Unique URLs in Received E-mail Messages. 139 Figure 7.8: Cumulative Frequency of Unique SRCs in Received E-mail Messages . 140 Figure 7.9: Intervals between Downloading and Reading E-mail Messages.............. 141 Figure 7.10: Burden of E-mailed URLs on Total Requests...........................................142 Figure 7.11: Proportion of Messages Read containing URLs, Clicked URLs 143 Figure A .l: E-mail — > Web Prediction (Extend — » New Use)...................................... 174 Figure A.2: E-mail/Web System with Modified Web and E-mail Servers..................177 Figure A.3: E-mail/Web System with Modified Apache Web Proxy.......................... 178 xv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure A.4: E-mail/Web System with Apache Web Proxy and E-mail Relay............ 179 Figure A.5: E-mail/Web System with Mozilla Web and E-mail Client....................... 180 Figure A.6: Composite E-mail/Web System....................................................................181 xvi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Abstract User-perceived latency prevents the web and other request/response applications from being truly interactive. Some delays can be reduced by upgrading equipment and links, but the only way to completely avoid latency is to predict which objects will be requested and prefetch them. The main contribution of this dissertation is a method for providing new structure to support prefetching. To prefetch objects that will be requested by the user, a function that determines likely future requests must exist. Some applications lack structure useful for making predictions. For these applications, it may be possible to import predictive structure from other applications that are related through shared data or functional dependencies. This document presents a model for single-application predictors highlighting predictive structure. It extends the model to create more sophisticated predictors by homomorphically composing multiple applications, which is called cross-domain prediction. Two example applications presented in detail are Web-DNS prediction and E-mail-Web prediction. Web-DNS prediction forecasts future DNS requests using web documents, enabling prediction in a system where none was previously possible. A log-based simulation shows that DNS prefetching based on web requests reduces the miss rate by 15% with only a threefold increase in the DNS cache size. With E-mail-Web prediction, incoming e-mail messages predict web requests. A six- month, multi-user study examining e-mail messages and web requests showed that e- xvii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. mailed URLs enable prediction for about a 25% of previously unpredictable requests, with negligible impact on overall load. xviii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1 Introduction User-perceived latency prevents the web from being a truly interactive application. Human factors research shows that delays as small as 100 ms negatively affect human-computer interaction. A variety of factors contribute to web latency. Some delays can be reduced by upgrading equipment or links, but the only way to completely avoid latency is to predict which pages will be requested and prefetch them. Unfortunately, not every page can be predicted because the application data lacks the necessary structure. The main contribution of this dissertation is a method for providing new structure to support prefetching. Users want interactivity; they want pages to load immediately when they click on links. For example, when revisiting content, users prefer the “back” button that pulls the page from the cache to a new click on the same URL that might request the page anew. Most web delays are no more than a few seconds - short enough for users to tolerate, but long enough to cause significant problems. Studies of human-computer interaction [Mil68] have found that delays longer than 100 ms disrupt thinking patterns. This number is due to the latency in human perceptions and is susceptible to learning. For highly skilled users, 100 ms may be too long. Users respond to delays in a variety of ways, but the result is a loss of productivity. Some users wait during the delay, becoming fatigued and allowing their minds to wander. Others multitask, switching between the browser and other applications such as e-mail or word processing. Some even attempt a manual version 1 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. of prefetching by opening several interesting pages at once, reading the first while others load. The loss of attention from boredom and the context switches required in multitasking mean that a user cannot devote their full attention to any one task. As a result of tiny delays, researchers may examine fewer alternatives or experiment less. Shoppers may purchase fewer items than they would if their curiosity was rewarded with speedy response. Eliminating all delay maximizes user interaction with web pages and may foster new applications. Web delays can be caused by slow clients, busy servers, or limited bandwidth. However, latency matters even when servers are idle and bandwidth is plentiful. Coast-to-coast round-trip latency in the United States is less than 50 ms for a straight path, based on the speed of light in glass. Over an IP network, round-trip latency approaches 100 ms due to indirect paths, store-and-forward switching, queuing delays, encoding delays, etc. Requests to servers outside the U.S. may be relayed over satellites, adding a 0.25 second delay. In the not so distant future, clients may be on the moon or in outer space with delays greater than 1 second. This distance-based latency can only be remedied with anticipation. Even when client and server are close, web transactions are rarely satisfied with one packet exchange. DNS resolution and TCP connection establishment add several round-trips before the HTTP request is made. Persistent connections may avoid repeating these setup delays, but a single web page can rarely be satisfied with just one request. The average web page is composed of six or more files. Some of 2 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. these files, such as sound or video files, may be too large to send in one packet. Again, anticipation is the only way to avoid latency for web requests. To prefetch files that will be requested by the user, there must be a function that makes guesses, called the predictor function. It is based on structure in the application, such as behavioral patterns or object characteristics. Some applications do not have structure useful for making predictions. For these applications, it may be possible to use predictive structure from other applications related by shared data or functional dependencies. This document presents a model for single-application predictors, highlighting predictive structure. It extends the model to create more sophisticated predictors involving multiple applications. With multi-application predictions, structure in one application domain is used to make predictions in another domain. This cross-domain prediction can increase prediction in some applications and provide predictors to applications that lack the necessary behavioral patterns or object structure. Caching applications use predictor functions to manage cached items. These applications remove latency for repeated requests for objects such as disk blocks, DNS records, or web pages. The cache stores objects locally in case they are needed again, avoiding the repetition of a costly retrieval or computation. Predictor functions that also anticipate new content can hide delay for first-time requests. Predictor functions can be found by examining object relationships and the behavior of the client. A syntactic analysis of the internal structure of an object can reveal dependencies or usage sequences. Higher-level semantic analyses can provide 3 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. other object relationships and may be used for anticipation. Other behavior-based predictors may be developed independently of syntax or semantic content of any given object. A good predictor function is necessary to make anticipation useful to the user and to minimize wasted resources. Generating predictions and acting on them requires computation and other resources. A function that yields many predictions at one time must prioritize its output to minimize this impact. Often these costs are weighed against the benefits a correct prediction provides. Incorrect predictions in reuse caches consume only storage space in the cache, whereas an incorrect prediction in making an anticipatory first-time request consumes resources that would never have been used without the prediction. The accuracy, costs, and benefits of a given predictor function depend on the predicting application. This document focuses on the mechanics of predictor functions and will not explore implementation-based factors in great detail. Examples of possible cross-domain opportunities are presented in Chapter 3, where the full design space of 2-domain prediction is explored. Two examples are explored in more detail in later chapters: Web-DNS prediction and E-mail-Web prediction. With Web-DNS prediction, future DNS requests can be inferred from web predictions, allowing prediction in a system where none was previously possible. With E-mail-Web prediction, incoming e-mail messages directly predict web requests, reducing the number of web requests that cannot be predicted. Figure 1.1 illustrates cross-domain Web-DNS prediction showing new DNS predictions. DNS caches alone contain no useful information for predicting future 4 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. requests. Web browsers must make DNS requests before they can open a connection to a web server for the first time and web requests can be predicted using the syntax of HTML documents. Domain names from predicted URLs can be used to make DNS predictions. DNS domain names syntax web browsing html docs ty Figure 1.1: Cross-Domain Representation of Web-DNS Prediction An investigation into the DNS component of connection setup reveals that DNS requests can account for as much as 50% of connection setup delay. Because web browsers use persistent connections, this cost cannot be amortized over a series of web requests. A log-based simulation shows that DNS prefetching based on web requests reduces the miss rate by 15% with only a threefold increase in the DNS cache size. DNS records are small so this increase in cache size is not prohibitive. Web browsers contain many opportunities for prediction, yet there are still URLs that cannot be predicted. These URLs come from outside applications or are typed in by the user. E-mail-Web prediction aims to reduce the number of unpredicted requests by scanning incoming e-mail messages for URLs that can be prefetched. To investigate E-mail-Web prediction, a test system was created using a browser, a web proxy, and e-mail filters. Six months of data were collected about user interaction 5 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. with URLs embedded in e-mail messages. Non-predictable requests account for up to 15% of all URL requests a user makes. E-mailed URLs account for about 25% of non-predictable requests. Some e-mailed URLs have side effects, such as discontinuing a service, so a working prediction system must filter the URLs it prefetches. However, more than 50% of e-mailed URLs are good candidates for prefetching. This dissertation is organized as follows. Chapter 2 presents a simple model for caching that graphically represents all single-domain predictive systems. It identifies four base predictor types. Chapter 3 combines these base predictors to create new predictors. It extends the model to cross-domain systems, describing the unique contribution of this work. The related work is discussed in Chapter 4. Single domain predictions are used throughout the web; prefetching has been studied from numerous angles, including using predictors from other domains. Chapter 5 presents possible benefits for Web-DNS prediction. The design and implementation of the E- mail-Web cross-domain system is discussed in Chapter 6, with discussion of the results and requirements in Chapter 7. Chapter 8 concludes that cross-domain prediction provides new predictions to networked applications, reducing user latency. Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 2 Modeling Predictive Applications Prediction enhances applications by reducing delays and improving resource use. With caching applications, it can avoid duplication of effort by reuse. With prefetching or precomputing applications, it can improve application response time by speculatively starting lengthy operations before their results are needed. This chapter introduces the terminology for discussing predictive applications and presents a model and graphical representation for them. It then applies the model to several well-known predictive applications. This chapter focuses on prediction in a single application. Chapter 3 will extend these models to show how prediction in one application can help another application, the latter of which cannot predict all requests. This document uses the term domain in its mathematical sense: a set of inputs over which a function is defined. The function is the application to be optimized; it maps high-level directives into concrete actions that form its range: /(domain) (range). User behavior provides a sequence of domain elements that determines a path through the range, the series of objects or actions used by the application. Consider web browsing, where the domain is the set of user page requests that drive the system. The function maps these user requests to a set of protocol GET requests: /(URLs) -> (GETs). The series of user requests determines the browser’s path through the range; some of these paths are the result of the fact that a page returned for the GET contains domain elements (URLs) that the user may request in the future. Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Elements of the range are called objects and are used by the application. A predictor function,p, forecasts future objects in the application’s path: p(<input>) -> (range). In the predictions explored in this chapter, the domain of the predictor function is also the application’s range. Continuing the web browsing example, protocol GET requests return pages containing new URLs that can be used to predict future user requests: p(<page>) -> (URLs). Predictors with external domains will be explored in the next chapter. Because the predictor operates in the range of the application, the range must be defined on the resource(s) that the application designer seeks to improve. With web browsing, if the predictor aims to reduce user-perceived latency, the range may be the browser’s series of GET requests. If the designer wishes to improve object rendering in the browser, the elements of the range are the acts of preparing each object for presentation. This document models predictors as one-to-one relationships; they may also be composed into many-to-many. Some examples of predictors using multiple objects appear in Section 2.4. A given input may forecast multiple output objects and many different input objects may forecast a single output object. This is fine as long as the predicted set of objects is broad enough to contain those actually requested. This chapter presents the need for predictors and discusses aspects of their design and implementation. It presents a graphical model for representing predictors and introduces a set of four canonical predictor types that operate within a single 8 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain. The next chapter extends this model, introducing predictors that operate across domains. This chapter is organized as follows. Section 2.1 explores the costs and benefits of prediction. They help guide the design of a predictive system. Section 2.2 discusses the relationships that can yield predictor functions. Section 2.3 examines the timing of predictors to provide maximum benefit and minimize waste. Section 2.4 presents the canonical set of single-domain predictors. In Chapter 3, these predictors will be combined across applications. Section 2.5 explores combinations of the canonical predictors in series. 2.1 Benefits and Costs of Prediction Prediction improves applications by reducing the usage cost of one or more key resources or by improving user-perceived quality of service. Cost reduction can be explicit, such as reduced use of leased or limited resources, or implicit, such as reduced number of disk accesses. For interactive systems, user-perceived quality of service usually means response latency. The accuracy of the predictor is crucial to these benefits; inaccurate predictions can waste resources and increase costs. A predictor achieves these benefits by exploiting other resources in the system. For example, caching disk blocks in main memory reduces subsequent disk accesses at the cost of increased memory use. With a networked application, these costs or benefits extend beyond the client machine: they m ay affect the server m achine(s), intermediate nodes, and/or the network itself. For example, web prefetching reduces user-perceived latency by increasing the use of local storage, web server request load, 9 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. and network traffic. The effects of exploiting these resources can be minimized by background prefetching using idle cycles. This will be discussed further in Chapter 7. The designer of a predictive system will choose which resources should be exploited to achieve the desired benefit, often selecting those that have minimal impacts on others, or those where impact is not important. A single optimization can be tweaked to yield further benefits. For example, web caching directly benefits the user by reducing their perceived latency; it also indirectly benefits other users and the network, reducing request load through selective document retention. Likewise, proxy caching can reduce user-perceived latency by sharing cached documents, but also reduces server request load by increasing the reuse of transferred documents. A prediction is accurate when the application uses the forecasted object. Accurate predictions provide benefits with little costs — the resources needed to execute the prediction are often those that would be used to access the object upon request. If a prediction is inaccurate, those objects are never used and resources are wasted. Timing is important as well - accurate predictions may be wasted if they cannot be completed before the object is needed. The timing of predictions will be addressed in Section 2.3. A predictor’s utility allows a designer to weigh the benefit of accurate predictions against the cost of accurate plus inaccurate predictions. If a function’s benefits outweigh its costs, the function has high utility. Predictors that forecast many objects for one input may have a high success rate but low utility because effort is 10 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. wasted executing many incorrect predictions. On the other hand, an accurate prediction with large benefits can outweigh many low-cost inaccurate predictions. Some predictive systems are transparent to applications, but others change object access patterns. Applications that are optimized to these usage patterns, such as cache replacement algorithms, may suffer performance degradation and must also change. Applications that interact with predictive systems may not be able to distinguish predictive use from actual use and may suffer. For example, a web server with predictive clients may not be able to distinguish between a document that is popular to users (e.g., the URL “linuxtrix.html” that appeared on Slashdot [Sla]) and one that is highly predicted (e.g., the link “copyright.html” that appears on all server pages). Predictor functions are usually embedded in the applications that they benefit, but this is not always the case. Sometimes they are implemented as external helper applications that coexist with the primary application. Also, the application that uses forecasted objects may not be the primary beneficiary of the prediction. For example, a web server might push popular pages to a client to reduce future request load. The user will benefit from reduced latency even though the browser is not actively involved in the prediction. 2.2 Predictor Functions Predictor functions are based on the relationships between objects in the application path. Within a given application, there are many sources of predictor functions. They fall into three main categories: object use, object syntax, and object 11 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. semantics. The source of the predictor can determine how easy it is to use. The costs discussed in the previous section focused on executing the prediction. This section considers the effort required to generate predictions. 2.2.1 Usage Relationships Usage order relates objects in an application. The objects may be ordered components of a larger object, such as the disk blocks of a file. To the application, disk block usage exhibits a serial data dependency between objects - a new one starts where the previous one ends. Using disk block content is context-free; the order in which the blocks are used cannot be altered and items cannot be substituted. Such rigidity can be useful because it limits the number of possible predictions, increasing the success of prediction. Other linear relationships may be context-sensitive, meaning that the usage sequence may depend on other requests. Predictors based on these relationships may be less accurate, as shown in Figure 2.1. The request pattern suggests that the object used after A at time U will be B, but in fact, it may be a new object not yet seen, in this case D. A B C A D t\ h h t/\ ts Figure 2.1: Sequential Relationships between Application Objects When an application uses two or more objects at the same time, the objects have a concurrent, parallel relationship, as shown in Figure 2.2. For example, multimedia applications use video and sound files simultaneously. Concurrent use 12 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. may also be context-sensitive. In Figure 2.2, object A is used in parallel first with object B, and later with object E. t\ h h U t$ Figure 2.2: Parallel and Sequential Relationships between Application Objects Web browsers use web objects both serially and in parallel, as shown in Figure 2.3. User behavior drives the series of web requests and can be quite varied. This loose relationship between web objects means that there are more possible predictions and thus forecasted objects are less likely to be used, reducing the utility of the predictor function. C.html A.html A.html E.gif D.html G.gif E.gif B.gif t\ t\ t\ t\ Figure 2.3: Example of HTML Parallel and Sequential Relationships 2.2.2 Syntax Relationships The internal structure of an object may contain data dependencies that relate it to other objects. These data dependencies (e.g., HTML links, document keywords, C 13 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. include directives) appear in the object syntax. Syntax relationships, where they exist, are very easy to use in an automated predictive system. Generating such predictions is typically quick and inexpensive (e.g., by parsing an object).- Consider HTML files which contain information about relationships between web objects with syntax that specifies a web page by referring to support files. Figure 2.4 shows the relationships between objects that based on parsed HTML syntax. <href> tags indicate possible linear use of objects, symbolizing next-hop pages to be displayed by the browser. A variety of other tags, such as <img>, <applet>, and <frame> tags, indicate support files used in parallel with the main HTML file. Z.gif X.html <href> <href: <img> W.html <frame£- <hre1 Figure 2.4: Data Dependencies in HTML Files Figure 2.5 shows how the syntactical information in Figure 2.4 translates to predictions for each HTML file shown above. The first diagram illustrates the use of W.html, which contains a parallel <img> reference to Z.gif and a parallel <frame> reference to X.html. The <href> tag within W.html points to a possible future request for Y.html. The other diagrams similarly illustrate X.html and Y.html. 14 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Y.html Y.html Z.gif W.html Z.gif X.html Y.html X.html Xhtm l hc ty Figure 2.5: Predictive Models of HTML Files Not all syntactical data dependencies translate to predictions. For example, DNS records reference other records, but not in a way that suggests future use. A minimal DNS record contains the name and IP address of a given system (the “A” record), as well as the name server for the record (the “NS” record). The name server entry refers back to the parent of the DNS record and is not helpful for guessing future requests. An example of DNS dependencies is illustrated in Figure 2.6. The syntactical information may be used to construct a tree of these records that is rooted at the top-level domain. Figure 2.7 shows how they might be used sequentially. A: usc.edu = xxx.xxx.xxx.xxx NS: edu A: edu = xxx.xxx.xxx.xxx A: www.usc.edu = xxx.xxx.xxx.xxx NS: usc.edu A: mit.edu = xxx.xxx.xxx.xxx NS: edu A: www.mit.edu = xxx.xxx.xxx.xxx NS: mit.edu Figure 2.6: Data Dependencies in DNS Records 15 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. www.usc.edu edu usc.edu ti t2 t2 Figure 2.7: Sequential Use of DNS Records 2.2.3 Semantic Relationships Semantic information can also indicate relationships between objects. It is based on the meaning of the attributes of an object, such as its subject or the author’s native language. There are some cases where semantic information is encoded as part of the syntax of an object, such as a keyword in an abstract or HTML code. This information may help categorize pages by subject or characteristic, or might be used by a cache or search engine to organize and retrieve documents. Though semantic information can be very descriptive, it is often hard to get and difficult to use for prediction because it is subjective and general. The descriptive nature also makes predictions based on such information hard to automate. As an example, consider an object that is an action photo of Teemu Selanne, a hockey player for the San Jose Sharks. One obvious categorization would be “sports”, suggesting a target object relating to hockey. However, the user may actually be interested in aquatic animals, athletic equipment, or people with unusual names. Given the number of semantic categories that apply, the pool of possible future requests is large. Retrieving all related objects is prohibitive and thus the probability of a hit is very low. 16 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 2.3 Timeliness of Predictors The timing of a prediction is important to the success of a predictor function. Timing breaks down into three steps, shown in Figure 2.8. Generating a prediction is the act of determining the forecasted object. Once an object is chosen, it must be made available to the application. For example, once a web page is forecasted, it must be requested from the server and stored in the cache. The speed of prediction generation depends on the complexity of the predictor function, but is generally shorter than retrieving the forecast object. For the prediction to be completely successful, these two steps must be completed before the object is used by the application. If the forecasted object is made available before it is needed by the application, the application must hold it in a cache. A long hold time can cause the application to use invalid data or may require a correction, requiring new effort; it also consumes storage resources. If the predicted object is needed before it can be made available, the prediction is late. This is shown in Figure 2.9. Even though the prediction is correct, the late prediction may waste resources by duplicating effort. Because the prediction had not been completed when the object was used, the application needed to retrieve it, duplicating work that may have already been started. An application may detect > jSer^ ^ Make ^ o ld Figure 2.8: Temporal Breakdown of Predictors 17 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. pending predictions and wait for them to finish instead of duplicating work, but external predictions cannot be detected. In the web server push example, a late prediction may cause the browser to request a page that the server is already pushing. t Figure 2.9: Late Prediction Ideally, the prediction should be completed just when the object is needed by the application, shown in Figure 2.10. This minimizes the need for a correction and avoids any duplication of effort. It may also minimize the resources needed to store the object before use. Coinciding availability with use is the goal of “just-in-time” manufacturing where vendors attempt to keep minimal inventories. This is also the way airlines manage aircraft availability and there is almost no margin for error - small, unexpected events can cause huge problems. The effects of delay must be considered when relying on predictions. t Figure 2.10: Desired Timing 18 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 2.4 Models of Predictive Applications This section presents the model and corresponding visual representations of predictive applications and derives the set of predictive relationships that can exist between two objects in a single domain. Figure 2.11 shows the abstract model of a predictive system. With the predictor function,;?, object P can predict object Q. Both objects exist in path a of domain x. The object shape differs to indicate that the objects are not the same. Many different predictive applications reduce to the same graphical model but they differ in the costs and benefits that motivate their use. Some of these applications will be presented in the next few subsections along with detailed discussions of the models. predictor /?(P) domain x path a tx tx +A Figure 2.11: Annotated Predictive Model Predictor functions are grouped into categories based on their effects in the application path. Four canonical models have been identified. The first three models are identity functions, but differ in how the object recurs. A Reuse prediction indicates a repeated, discrete use of the input object. An Extended Use prediction indicates a sustained use of the input object. A Delayed Use prediction indicates the postponed use of the input object. In the fourth model, a New Use prediction generates an object that differs from the input object. The following subsections 19 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. examine each of these models in more detail. After presenting the four models, Section 2.5 discusses the concatenation of the models. Chapter 3 extends the models, combining predictions in multiple applications. 2.4.1 Reuse Predictions Reuse predictions occur when the predictor function outputs the same object as was input. Each object use is discrete. Reuse predictors require a cache to store the object or state for the action that will be reused. The cache requires additional system resources. It may also require isolation to protect against side effects and to allow predictive actions to be undone if they are never used. The simplest example of the Reuse model is the practice of caching in the web and elsewhere. Caches store objects that have been used in the past in case they are requested again. They are indicated in applications that exhibit patterns of reuse in the path. They are often used in web browsers, exploiting storage on the client machine. When cached documents are used, they reduce user-perceived retrieval latency, web server load, and request traffic in the network because these costs are incurred only for the first request of a given object. Web caching is represented by the Reuse Model, shown in Figure 2.12. Each object in the path represents a single URL. A pattern of reuse is the predictor that keeps an item in the cache. 20 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. reuse web browsing URLs t Figure 2.12: Reuse Model - URL Reuse in Web Browser Caching Web browser caches usually handle the series of requests for a single user. However, some documents are popular and are requested by many users. An isolated browser cache would miss the opportunity to take advantage of this popularity. A proxy cache provides the benefits of reuse caching for some first-time user requests by aggregating the request streams of multiple users. Like the previous example, the proxy cache reduces latency, web server load, and network traffic. The costs however, are somewhat different. The cache might not be located on the same machine as the users’ browsers, further delaying requests that are cache misses. The cache machine must have storage space for the cached documents and must handle a request load that it might otherwise not incur, with the extra processing and network traffic that entails. Finally, latency reduction may not diminish compared with a browser cache. Figure 2.13 illustrates web proxy caching where the predictor operates between paths in the range of the application. The popularity of a given object predicts its use by another client of the cache. Unlike browser caching, proxy caching uses a predictor that crosses paths. It uses the actions of one client to predict the actions of another client. However, because the proxy cache aggregates client requests, the correct domain for the predictor is the aggregate request stream of all of the cache’s clients. 21 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. web browsing P ............ > client 1 reqs popularity t+A web_browsing client 2 reqs __ t Figure 2.13: Predict New Use in Another Path Rather than considering these as two crossed paths, as in Figure 2.13, Figure 2.14 shows that proxy caching conforms to the Reuse Model where document popularity predicts the reuse of objects in the path. Although there is only one domain, the figure reflects the user’s request streams that combine to form the application path. The different paths in the figure above are combined into the main path of the proxy application. If browsing habits overlap, the larger request pool may result in an increase in successful predictions due to the ability to satisfy first-time client requests. Figure 2.14: Reuse Model - URL Reuse in Web Proxy Caching 2.4.2 Extended Use Predictions In some applications, the predicted reuse of an object translates to extending the use of that object. This is useful in cases where multiple discrete uses of an object are more expensive than a single persistent use. These situations are represented by popularity wek browsing all user reqs t t+A 22 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. the Extended Use model, shown in Figure 2.15. This model may be appropriate for applications concerned with resource management. Spatial resources [EggOl], such as disk blocks or memory, may be shared among many applications that will host the resources as long as necessary. Extending the use of an object requires the application to maintain state for that object and is best suited to connection-oriented protocols and applications. predictor /?(P) domain x path a t t+A Figure 2.15: Extended Use Model Object extension may cause side effects or result in failure. The length of object use can cause side effects. If the objects use limited or exclusive resources, extending them can cause deadlock or starvation. Undoing the prediction may not be possible. The prediction can fail if resources have forced termination limits that cannot be extended. In these cases, the prediction is not wasted, fits the Reuse model. To understand the Extended Use model, consider persistent HTTP connections. They optimize web browsing by maintaining the connection to a web server in case the browser makes future requests to the same server. At first it may seem that the Reuse model is appropriate for this application because future requests reuse the connection to the web server. Figure 2.16 shows this incorrect view, where the domain is the set of connections to remote servers. 23 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. reuse exit mgmt serverx t+A Figure 2.16: Reuse Model - Linear Reuse of Destination Server (incorrect) The above figure presents persistent connections as two discrete occurrences of the connection to a single server. This is incorrect: discrete connections to a single server differ from each other because they use a different set of ports. Thus, the application determines a path through the ports used to access the given server. Figure 2.17 presents the correct path through this domain. If the connection to the given server is closed and reopened in the short time scale of a series of web requests, the first connection would still be in TIM EW A IT and thus the ports cannot be reused. exit to x port # Q t+A Figure 2.17: Subsequent Connections to Server X (Ports P and Q) Now it is clear that persistent connections reuse not only the endpoint of the connection, but also the state associated with the connection. Because the connection is persistent, the instances of using it cannot be discrete. The initial use does not terminate, and the connection state is maintained in anticipation of reuse. Figure 2.18 presents the correct model for persistent connections. 24 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. reuse cxn to x port # t t+A Figure 2.18: Extended Use Model - Extended Port Use in Persistent Connections 2.4.3 Delayed Use Predictions In contrast to applications that extend object use, sometimes the predicted reuse of an object translates to a Delayed Use of the object. The Delayed Use model is shown in Figure 2.19. It is useful in applications where delaying use increases object utility. For example, the application may hold a packet to send it out with more data. It may also be useful for temporal resources [EggOl], such as NIC access or disk bandwidth, that cannot be used simultaneously by applications. The delay can allow a more efficient use of the resources when it finally occurs. predictor /?(P) domain x path a t t+A Figure 2.19: Delayed Use Model Delay predictions should be used with delay-tolerant protocols and applications. Like with Extended Use, the application should have some limitation to the length of the delay, after which the object must be used. The delay of object use or action may cause side effects. Once the decision is made to delay the action or use, no 25 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. isolation or reversal is possible. However, delays may improve the sharing of limited or exclusive resources, thus reducing starvation and deadlock. To understand the Delayed Use model, consider packet aggregation. It is similar to persistent connections in that it reuses application state. When requests or data to be sent to a single destination are smaller than the maximum packet size, several objects can be combined into one packet. This reduces the number of packets sent over the network and thus the per-packet overhead. Aggregation increases the size of individual packets and incurs an additional latency penalty for the requests or data that wait to be sent. It is implemented in TCP as the Nagle algorithm [Nag84], where TCP holds small packets waiting for more data. TCP will send the packet if 200 ms pass before it is full. Unlike the examples above, packet aggregation may not be used to reduce user-perceived latency. At first glance, packet aggregation reuses the packet header and seems to conform to the Reuse Model, as seen in Figure 2.20, but this is incorrect. reuse data xmission pkt header t t+A Figure 2.20: Reuse Model - Reuse of Packet Headers (incorrect) Like persistent connections, the application takes advantage of reuse of the destination. However, it is not the destination that is reused, it is the packet header. Again, the domain must be chosen carefully to accurately model the system. The 26 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. packet header is not reused so much as the packet is delayed awaiting further data. Packet aggregation is correctly represented with the Delayed Use Model, shown in Figure 2.21, a time-reversed version of the Extended Use Model. pkt dest t t+A Figure 2.21: Delayed Use Model - Delayed Packet Header Use in Packet Aggregation 2.4.4 New Use Predictions The models presented so far share the same predictor effect - object recurrence in the path. In the web, examination of other usage patterns and object syntax has yielded predictor functions that forecast the use of new objects in the path. Instead of reducing latency when a document is reused, the predictor can be used to retrieve documents before they are requested the first time. If the prefetched document is actually used, the costs are the same as retrieving the document at that time. If it is not used, there are additional costs in the wasted effort in retrieving and storing the document - server load, network traffic, and local storage space. Prefetching is represented by the New Use Model in Figure 2.22, showing that the forecasted object is completely new. reuse data xmission 21 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. syntax, use, etc web browsing URLs P > t t+A Figure 2.22: New Use Model - New Use in Web Prefetch In web caches, prefetching can work as follows. The user requests a web page. While the user is viewing the page, the browser parses it for URLs that correspond to links the user might click on. The browser requests these pages and stores them in the cache. When the user finally clicks on a new link, the page is loaded instantly from the cache. Predictions of new objects can occur in any application. They require cache like storage for predicted objects or state for predicted actions. Like Reuse predictors, these predictions may require isolation to protect against side effects and allow reversal. 2.5 Composing Predictions and Muiti-Object Predictions The sections above considered the dynamics of a single prediction. This section considers a series of predictions within an application and the constraints on composing different types of predictors. When a predicted object in turn predicts another object, the predictions are contiguous. When a series of predictions does not share object instances, they are non-contiguous. Multi-object predictions are those where the input and/or output of a predictor function is a set of objects. 28 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 2.23 shows an example of a non-contiguous series of New Use predictions. Ideal applications should have a long series of contiguous predictions. That Q cannot predict R represents an opportunity for increased predictions within the application. The types of predictions that appear in a given series depend on the both the application characteristics (e.g., avoid Delay predictions in a delay-sensitive application) and the constraints and compatibility between the types of predictors. Although each object in Figure 2.23 is given a separate name to introduce the concept, the objects in the second prediction may be recurring instances of the objects (P, Q, R, S) in the first prediction, so long as R jt S. (e.g., R = P and S = Q, or R = Q and S = P) prediction 1 prediction 2 domain x path a tx tx+A, tx +A2 tx +A3 Figure 2.23: Non-Contiguous Series of New Use Predictions Figure 2.24 shows a pair of contiguous New Use predictions, possibly merging those shown in Figure 2.23. Object P predicts [Q = R], which when used, predicts S. It is important to note that this model represents only primary predictions. Object Q must be used before S can be predicted. In this model, the prediction of Q cannot be used to generate a secondary prediction of S. Some implementations may wait until one prediction has been proven correct before making further predictions based on its results, but this is not necessary. Other implementations, that predict based on other 29 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. predictions, must take the product of the probabilities of each prediction into account, leading to rapidly diminishing returns. prediction 1 prediction 2 domain x path a Q = R tx tx +Al tx+A2 Figure 2.24: Contiguous New Use Predictions Contiguous predictions are limited by the nature of the application, but they have a few additional restrictions. The use of the target object in the first prediction may govern how it can predict other objects. New Use predictions can always appear as either the first or second in a contiguous pair. They combine with any other type of prediction in a straightforward way. Two contiguous Extend predictions combine to form a larger prediction of the same type, as shown in Figure 2.25. The use of P at time tx can predict the further use of P. The use of P at tx +Ai generates another prediction of further use. Thus, the use of P has been extended from tx to tx+A2. A pair of contiguous Delay predictions behaves in a similar way, combining to form one large Delay prediction. domain x path a tx Figure 2.25: Contiguous Extend Predictions 30 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Extend and Delay predictions may be combined provided both types of predictions are allowed in the application. When they are combined, the Delay prediction must always come first. The next two figures show why this is necessary. Figure 2.26 shows the non-sensical case where the Extend prediction comes first. An Extend prediction implies the application first uses P at time tx and continues to use it until tx+Ai. In contrast, a Delay prediction implies that P is not used until the end of the prediction at tx+A2. Clearly, this order contradicts the definitions of the predictors. domain x tx C+Ai C+A2 Figure 2.26: Contiguous Extend - Delay Predictions (non-sensical) Figure 2.27 shows the ordering of these predictors that is consistent with their definitions. The use of P is first indicated at tx, but the predictor causes that use to be delayed until tx+A\. When it is used, at tx+Ai, a second prediction causes it to be extended until 4 +A2. domain x tx C+Ai tx+A 2 Figure 2.27: Contiguous Delay - Extend Predictions Like New Use predictors, Reuse predictors may appear as either the first or second prediction in a contiguous pair. When used together with an Extend or a Delay predictor, they indicate a situation where extending or delaying the use of the object 31 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. was no longer possible. Perhaps a connection timed out or a delay-tolerant application had reached a capacity limitation requiring action. In either case, it is still possible to predict the reuse of the object. Figure 2.28 shows this for Delay predictions. The use of P is delayed until tx+A\. At this time, the application can predict additional use, but can no longer delay it. The next predicted use, at tx+A2, predicts the next delayed use at tx+A3. domain x tx tx+Ai tx+A 2 k+A3 Figure 2.28: A Series of Two Delay Predictions Separated by Reuse The next few examples consider predictions that involve more than two objects. A single object can predict several other objects. Figure 2.29 shows P predicting both Q and R. User behavior may determine when Q and R are used and in what order, so the predictions themselves do not necessarily include this information. Because this model can only predict what objects might be used and not when they might be used, an object cannot predict multiple instances of another object. If the object predicts itself, the prediction will be one of Reuse, Extend, or Delay. Predictions of objects other than itself are New Use by definition. 32 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x path a tx tx+ A i tx + A 2 Figure 2.29: Multiple Target Predictions Sometimes the prediction includes ordering information obtained from the application’s history. Figure 2.30 shows a sequence of object uses that predicts a new object. In this application, the use of P followed by the use of Q predicts R. Figure 2.31 shows an object that predicts a sequence of other objects; P predicts the use of Q followed by R. In both of these figures, the dashed rectangle encloses objects that together are the input or output of the predictor function. These predictions may be any one of the four basic types, depending on the application. The accuracy of these predictions depends on the application, but it seems likely that the first example may be more accurate than the second because there is more input to the predictor function. domain x path a tx t x+ A i tx + A 2 Figure 2.30: A Series Predicts a New Use domain x path a tx t r + A i tx + A 2 Figure 2.31: An Object Predicts a Series 33 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 2.6 Summary In addition to discussing the motivations behind predictive applications, this chapter has developed a template for representing them graphically. By examining common predictive applications, four base predictors have been identified: Reuse, Extended Use, Delayed Use, and New Use. All single-domain predictors conform to one of these models. These models and their iconized representations are summarized in the table below. Model Icon Constraints Reuse requires caching Extend — a m i r t h - connection-oriented requires state Delay — . i o a delay-tolerant requires caching New Use requires caching Table 2.1: Base Predictors This chapter also considered the combination of predictions in series. Again, the characteristics of a given application and compatibility between predictions determine which predictions may occur in the series and how they may be combined. Predictors may take multiple objects as input or may output multiple objects. The predictor functions in these models and their combinations all operate within the same domain. The next chapter will explore predictor functions that combine across domains and extend the model to cover these situations. 34 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3 Cross-Domain Predictors The predictors examined in the previous chapters operate within a single path in a single domain. The domain and range of the predictor function are the same set of objects. This chapter explores predictors that operate across domains. It focuses on developing the relationships between domains that can be used to generate predictors. Once a formalism for relating two domains has been established, the base predictors in Chapter 2 are extended to multiple domains. The extension is applied to two examples, Web-DNS prediction and E-mail-Web prediction, that will be discussed in Chapters 5, 6, and 7. The relationships between domains are mapping functions of the same categories as object relationships within a domain: usage patterns, object syntax, and semantic relevance. The resulting predictor in a cross-domain system will be the product of mappings between domains. The discussion of cross-domain predictors focuses mainly on 2 -domain cases, but these techniques can be extended to an arbitrary number of domains. Two 2-domain predictor examples will be explored in greater depth in later chapters: Web-DNS prediction and E-mail-Web prediction. Cross-domain Web-DNS prediction uses web predictors to prefetch DNS records. It can significantly reduce user-perceived latency for clients with high-latency first hop links or for clients accessing international sites. E-mail-Web prediction provides new web predictors 35 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. from URLs embedded inside e-mail messages. These URLs represent requests the browser cannot otherwise predict. This chapter is organized as follows. Section 3.1 extends the single-domain predictors to two domains. Section 3.2 describes the full set of 2-domain predictions and identifies traits for each. Section 3.3 presents examples of 2-domain predictor implementation and defines corresponding predictors for each. Section 3.4 uses the techniques from Section 3.1 to explore predictors using more than two domains. 3.1 Abstract Model of Cross-Domain Prediction As mentioned above, the predictors of Chapter 2 operate in one domain and a single path. However, some applications have no predictors within their domain or cannot predict all objects that will be needed. This chapter presents a way to increase the number of predictors in a domain by obtaining them from other domains. In effect, these obtained predictors operate across domains. Figure 3.1 presents an abstract view of cross-domain prediction. The goal is to increase the number of predictions in a domain (domain x in Figure 3.1), with a predictor function that uses objects from another domain (domainy in the figure). By identifying relationships between the domains, the predictor can be imported to domain x. This is similar to Figure 2.13 where two clients share a cache, but it differs because the two paths occur in different domains. 36 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x path a domain y H ? predictor ^(M) path P M ■> Figure 3.1: Abstract Cross-Domain Model The model above presents the essence of the cross-domain prediction but does not suggest how it can be accomplished. Objects in the target domain relate to objects in the source domain with a homomorphism, as shown in Figure 3.3. The inferred prediction in the target domain that takes the form of one of the four basic predictors presented in Chapter 2. The exact type of inferred prediction depends on the target application and will be discussed in the next section. d(P): inferred predictor domain x path a H ? Q n r tv +A , a(P): mapping x -> y h(M): source predictor •y~2A n + q C (N): mapping y -> x domain y path P t i . ’ +An Figure 3.2: Homomorphism Prediction The homomorphism prediction results from a pair of mappings between two domains together with a source prediction in one domain. It allows the inference of a 37 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. prediction in domain x, d(P), based on a prediction in domain y, Z>(M ). The mappings between domains are required to identify the inferred prediction. 4: d{P) domain x f ? j ST /jd“ An+q 1: a(P) 2: KM) 3; C (N) path [5 domain y ty ty + A n Figure 3.3: Homomorphism Prediction Detail Figure 3.3 is numbered to show the steps of the inferred prediction. First, there must be a mapping function, a(P), that relates object P of domain x to an object, M, in domain y (step 1). The prediction in domain y, &(M), yields object N (step 2). Then, there must exist a reverse mapping function to relate object N of domain y, back to an object in domain x (step 3). This function c(N) yields object Q of domain x. These three functions together result in the new prediction in domain x, i.e. d(P) = Q (step 4). The result is described by the functions shown in Equation 3.1. d(P) = c(b{a{ P))) & a(P) = M = c(6(M)) & &(M) = N = c(N) & c(N) = Q = Q Equation 3.1: Homomorphism Prediction 38 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The ordering of objects in the homomorphism is somewhat flexible, as long as the prediction is generated before object Q is used. Objects P and M may be used in any order if there is a function that maps between them. Likewise, the order in which objects N and Q are used is not important. For example, a predicted web page (N) can predict a DNS record (Q) but the DNS record will be used before the web page. In some cases, object N may never be used. To correctly predict object Q, it is only necessary to predict N and map between N and Q. Identifying mappings between domains that have predictions and those that do not is key to identifying applications that can use cross-domain prediction. The types of mappings between objects in different domains are the same as the mappings within a single domain: usage patterns and dependencies, syntax, and semantics. As discussed in Chapter 2, these relationships have different properties. Users should not notice any cost from applications that use regular or inferred predictions. The application itself may need alterations to accommodate the increased complexity of the inferred predictions, but overall, the goal is that the user should experience a net gain in performance. 3.2 2-Domain Predictors The last section introduced cross-domain prediction which can generate predictions when single-domain predictions are not available or not possible. This section explores the design space of 2-domain homomorphism predictions built from combinations of Reuse, Extend, Delay, and New Use predictors shown in Table 3.1. 39 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. R: Reuse E: Extend D: Delay N: New Use Table 3.1: Base Predictors The full set of base predictor combinations is presented in Table 3.2. Rows represent source predictors; columns represent inferred predictors. In the rest of this discussion, each base predictor is referred to by the first letter of its name. A simple mapping relation represents the situation where one type of prediction leads to another: for example, N — » N means a New Use prediction allows the inference of another New Use prediction. A smaller version of this table will appear throughout this chapter to highlight discussion about features of these predictors. Inferred R Recurrence Inferred: E Inferred: D New Info Inferred: N Source: R o R > R R > E R > D R~> N <D Source: E O E > R E -> E E > D E ^ N CD Source: D D > R D > E D > D D »N New Source: N N > R N > E N > D N > N Table 3.2: All 2-Domain Predictions 40 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. As with predictions in series, not every combination will translate to a meaningful implementation. Some general rules are discussed below. In particular, the first three entries in the Inferred: N column are shaded in Table 3.2 because these predictions are unlikely, given their meanings, but not impossible. The recurrence predictors, {R, E, D}, do not provide new information and New Use thus should not be inferred. Examples will be presented that show otherwise. In general: {R, E, D} -» {R, E, D} are valid 2-domain predictions; exceptions will be discussed below. This is shown in Table 3.3. Inferred R E D N R R-> R R^E D R > N E E^R £->£ £-> D E->N D D^R D-» £ D>D D^N N N->R N-> £ N^D N-> W Table 3.3: Valid Recurrence Predictions N provides new information to the system and may translate to other New Use predictions (N -» N). However, objects in the source domain may map to two instances of the same object in the target domain, resulting in one of the recurrence predictions (N — > {R, E, D}). Thus, any of N — » {/?, E, D, N} are valid predictions, shown in Table 3.4. Inferred R E D N R R-> R R> E R^D R->N E E > R £->£ E^D E^N D D^R D-+E D-»D D-> N _N_\ N->R N^E N^D N->N | Table 3.4: Valid New Use Sources 41 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The following subsections address each entry in Table 3.2. They are organized by inferred prediction, i.e. by the columns in Table 3.2, and each section includes a specific example of a corresponding use. 3.2.1 Inferred Reuse Applications that support Reuse predictions must have a cache to store objects or state for actions that will recur. The following figures present each source prediction in combination with an inferred Reuse, the first column in Table 3.5. Inferred R E D N R R— >R R> E R -> D R->N E E-> R E->E E^D E > N D D -> R D ~> E D->D D — > N N N-> R N^E N— >D N-> N Table 3.5: Inferred Reuse Predictions Sometimes Reuse predictions appear in applications that might otherwise use Extend or Delay predictions. Section 2.5 discussed this in more detail. A timeout or other resource limitation might cause the discontinuation of an extended object or the use of a delayed object. When a new use of this same object is indicated, it will appear as a Reuse prediction. 3.2.1.1 Reuse -> Reuse Inferred R E D N R R ~ > R R->E R^D R~> N E E > R E->E E^D E-> N D D — > R D -> E D > D D^>N N N-> R N-> E N— > D N->N Table 3.6: Reuse — > Reuse Prediction 42 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 3.4 shows a Reuse predictor as both the source and the inferred predictions. Many applications are optimized with Reuse mechanisms to avoid duplication of effort. One example is web browsing where domain y corresponds to a series of page requests and domain x to connections to web servers: R (URL) — > R (web server). Typically, a web page would be cached locally to avoid the need for reconnecting. However, if a repeat request for the page occurs a long time after the first request, the object may have been removed from the cache and a new connection would be needed. domain x path a domain y path ty Figure 3.4: Reuse — » Reuse Prediction 3.2.1.2 Extend — ► Reuse Inferred ty^~ Am 2 3 o R E D N R R > R R-> E R~> D R-> N E E^R E-> E E-> D E->N D D-> R D^E D->D D-> N N N ^R N^E N-> D N->N Table 3.7: Extend — » Reuse Prediction In Figure 3.5, extended use of an object in one domain implies the reuse of an object in another domain. This can occur when P cannot be extended, as with a 43 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. stateless application. If the application in domain x is not stateless, this model indicates a timeout or other event that forced P ’s termination. The application in domain y can predict the extended use of M. Because of the mappings between M and P, Reuse of P is inferred by the application in domain x, which caches the object. domain x path a / / / p H ? P />T A m 2+ p2 domain y path ft m . ' M tv Figure 3.5: Extend — > Reuse Prediction 3.2.1.3 Delay — ► Reuse Inferred 3 O t / 1 I I R E D N R R > R /?-> E R->D R-> N E E-> R E->E E->D E-yN D D^R D^E D-> D D— fN N N^R N E N^D N-yN Table 3.8: Delay — )• Reuse Prediction Figure 3.6 shows a Delay predictor in the source domain implying the reuse of an object in the target domain. Because of the relationships between M and P, the delay of M allows the application in domain x to infer the reuse of P. However, it seems incongruous that the first use of P can be related to the non-use of M in the source domain. As with the E -» R prediction above, it could be that the target 44 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. application would have delayed the first use of P, but cannot due to a timeout or other restriction. For example, the target application may be delay-sensitive and must act even though the source application would wait. domain x path a domain y path ft (y " ^ " A m 2 + p 2 ! M ! tv tjP ~ Am 2 Figure 3.6: Delay -> Reuse Prediction 3.2.1.4 New Use — > Reuse Inferred R E D N R R-+R R— >E R->D R^N E E-+R E— rE E^D E— rN D D^R D->E D->D D^N N N -> R N->E N->D Table 3.9: New Use — » Reuse Prediction Figure 3.7 shows New Use in the source domain predicting Reuse in the target domain. This might occur when viewing web pages. Clicking on a link to view a new page may require the reuse of one of the support objects for that site, such as a logo image: W(*.html) -» R(*.gif). 45 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x path a domain y path ft An Figure 3.7: New Use Reuse Prediction 3.2.2 Inferred Extended Use Applications that support Extend predictions must maintain state for the predicted object or action throughout its lifetime. Extend predictions are especially well-suited for connection-oriented protocols and applications. The following figures present each source prediction in combination with an Extend prediction, column 2 in the table of predictions. Inferred 3 O C /3 R E D N R R->R R^E R -> D R N E E^R E->E E->D E->N D D^R D-> E D~>D D-+N N N-> R N->E N->D N->N Table 3.10: Inferred Extended Use Predictions 3.2.2.1 Reuse — > Extend Inferred o o C /3 R E D N R Rh>R R-> E R^>D R-> N E E-> R E->E E-> D E~> N D D > R D --> E D~>D N N N-> R W -> E N->D N-> N Table 3.11: Reuse -» Extend Prediction 46 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 3.8 shows a Reuse prediction that implies an Extend prediction. This prediction might occur in a web browser, where page requests predict server connections: /?(URL) — > E(server connection). In this case, the same relationship between objects is exploited for both forward and reverse mappings. The user requests page M, which the browser satisfies by making a connection to server P. When the user makes a second request for page M, the browser can satisfy the request from its cache, but it must validate the page with a second request to the web server. The server maintains the connection to the server in order to do this; from its perspective (domain x), a predicted Extended Use has been created because of the user’s actions in domainy. path a domain x t path fi domain y > (> d ~ A m 2 Figure 3.8: Reuse — > Extend Prediction 47 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.2.2.2 Extend -► Extend Inferred S o W R E D N R R-yR R ^E R-yD R-yN E E^yR E->E E^yD E-yN D D-y R D-> E D-yD D-yN N N-y R N-y E N^yD N^yN Table 3.12: Extend — ► Extend Prediction In Figure 3.9, an Extend prediction generates another Extend prediction. This can occur when one connection-oriented application depends on another. For example, the user wishes to view a lengthy file on their PDA. The file is too large to store in the memory of the PDA, so it is displayed remotely. This remote-display application depends on the continued use of the connection between the PDA and the file server. If the file has not been viewed completely, it can predict the continued use of the network connection. Again, the server in domain x keeps a connection open because of a prediction (this time Extended Use) in domain y. domain x path a P T > >? -> ! P I A (y " t_ Am 2+p2 domain y path ft ty+Am 2 Figure 3.9: Extend -» Extend Prediction 48 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.2.2.3 Delay — ► Extend Inferred = 3 O 0 0 R E D N R R - > R R ^ y E R -y D R - y N E E ^ R £ - > £ £ - > D E - y N D D ^ R D-y E D-y D D^yN N N-y R N->E N -y D N - y N Table 3.13: Delay — > Extend Prediction Figure 3.10 shows a Delay prediction implying an Extend prediction. Such a prediction can occur when a connection-oriented application depends on a delay- tolerant application. The application in domain y may sporadically generate data but delays it to send larger packets. Through cooperation, the application in domain x can extend its connection, waiting on the delayed data. domain x y 1 ^m2+p2 domain y path P Figure 3.10: Delay — » Extend Prediction 3.2.2.4 New Use — ► Extend Inferred t iT Am 2 R E D N R R - y R /? -> £ R - y D R - y N E E - y R E - y E E -y D E -y N D D - y R D-y E D-> D D - y N N N ^ y R N-y E N - y D N - y N Table 3.14: New Use -> Extend Prediction 49 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 3.11 shows a New Use prediction generating an Extend prediction. This is similar to persistent connections in the web where the browser maintains a connection to the current server in anticipation of future requests to that server. In practice, persistent connections are based on patterns of clustered requests to the same server and are closed after an idle period. This could be improved by following the model below and considering the syntax of the current page. If the page contains links to URLs for new pages from the same server, the connection should be maintained; otherwise, it should be closed. In summary, N(server URL) -» E(server connection). domain x path a s ' j - ! p i A L"FAn + p 2 domain y path fi ty Figure 3.11: New Use — » ■ Extend Prediction 3.2.3 Inferred Delayed Use Applications that support Delay predictions must be delay-tolerant. They require additional storage or state to support the delays. The following figures present each source prediction in combination with a Delay prediction, column 3 in the table of predictions. 50 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Inferred = * o CZ) R E o N R R->R R-> E R > D R-> N E E ^ R E-> E E->D E ^ N D D->R D->E D->D D-> N N N -> R N-> E N->D N -> N Table 3.15: Inferred Delayed Use Predictions 3.2.3.1 Reuse — > Delay Inferred = 3 O c/5 R E D N R R >R R — >E R-> D R > N E E ^ R E->E E -» D E->N D D > R D-r E D->D D-> N N N-> R N~> E N — r D N Table 3.16: Reuse -» Delay Prediction Figure 3.12 shows a Delay prediction that is based on a Reuse prediction. An example is packet aggregation, where packets are held awaiting data, like with TCP Nagle [Nag84], The sender will delay the outgoing packet if the socket is going to be reused: R(socket) — > ■ D(packet transmission). domain x path a r < --- - i P ! IP - C y F A m 2 + p 2 domain y path /? ty Figure 3.12: Reuse — > Delay Prediction 51 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.2.3.2 Extend — > Delay Inferred D O 0 0 R E D N R R ^ R R — >E R->D R->N E E-+R E ^ E E-> D E > N D D-> R D ^ E D->D D->N N N^>R N-> E A/— > D N > N Table 3.17: Extend — » Delay Prediction In Figure 3.13, an Extend prediction generates a Delay prediction. This can occur when a delay-tolerant application depends on a connection-oriented application. The application in domain x may delay an action until the connection in domain y has terminated. This can occur with an application, in domain x, using a writeback cache. The cache is used by an application, in domain y, receiving data over an established connection. Writing data out from the cache can be delayed if the connection is predicted to continue. domain x path a P i r tx ^ y " t“ Am 2 + p 2 domain y path P ty Figure 3.13: Extend -> Delay Prediction 52 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.2.3.3 Delay — * ■ Delay Inferred R E D N R R - » R R E R D R - » N E E - > R E - » E E -* D E - > N D D - » R D - > E D - > D D - > N N N - > R N — >E N - > D N - > N Table 3.18: Delay -» Delay Prediction The combination of two Delay predictions is shown in Figure 3.14. This situation arises when two delay-tolerant applications interact. One possible scenario is application x must delay using P until application y has used M. For example, application x may send packets aggregating requests from application y. A prediction of delayed requests in application y allows application x to delay sending packets awaiting further requests. domain x path a -x - -i P l r t y ^ Am 2+p2 domain y path [J ty Figure 3.14: Delay -> Delay Prediction 53 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.2.3.4 New Use — ► Delay Inferred o c / o R E D N R / ? - > R R ^ E R-> D R->N E E-> R E-> E E-yD E^>N D D ^ R D ^ E D->D D-yN N N ^ R N - > E N^>D N - > N Table 3.19: New Use -» Delay Prediction Figure 3.15 shows a New Use prediction that generates a Delayed Use prediction. Perhaps the application in domain x manages a writeback cache receiving changed data from the application in domain y. If the application in domain y can predict that more writes will occur, application x can delay the writeback. domain x path a — <— P ! domain y path ft ty Figure 3.15: New Use -» Delay Prediction 3.2.4 Inferred New Use Applications that can support New Use predictions must have storage for predicted objects before they are used or for extra state for predicted actions. This discussion focuses on predictions in column 4 in Table 3.2. Recall that {R, E, D} are recurrence predictors and do not provide new information to the system. As a result, 54 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. they are unlikely (as was denoted by the shading in Table 3.2), but not impossible. Depending on the applications involved, they may yield New Use predictions as shown in the examples below. Inferred R E D N R R ->R R-> E R > D R ^ N E E->R m 4 - i n E ^ D E-> N D D — >R D - > E D — fD D ^ N N N-> R N-> E N-> D N-> N Table 3.20: Inferred New Use Predictions 3.2.4.1 Reuse — ► New Use Inferred R E D N R R ^ R R > E R - > D R - > N E E~>R E -■ > E E->D E->N D D -> R D ^ E D - > D D ^ N N N-> R N->E N - > D N->N Table 3.21: Reuse — » New Use Prediction Figure 3.16 shows a Reuse prediction that generates a New Use prediction. In general, this situation seems unlikely because the Reuse predictor does not provide any new information to the system, but a count of object uses may trigger a new reporting message. For example, a web cache may periodically transmit accounting information to a web server. Also, implementation decisions may prevent reusing resources in domain x. This might occur in a system with limited resources that cannot cache recurring objects, requiring a new connection to retrieve the object for the second use. It may also occur in a cache that requires validation in a system without persistent connections. 55 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x path a domain y path [i Figure 3.16: Reuse — > New Use Prediction 3.2.4.2 Extend — > • New Use Inferred 3 O G O R E D N R R >R R -► E R ->■ D R N E E - > R E ->■ E E - » D E - > N D D R D - > E D - > D D N N N - > R N - > E N - » D N - > N fy+A m 2 Table 3.22: Extend -> New Use Prediction Figure 3.17 shows an Extend prediction that generates a New Use prediction, another unlikely combination. The Extend prediction does not provide any new information, but there may exist applications where extending the use of an object in domain y implies the use of a new object in domain x. This prediction occurs in E- mail-Web prediction, which will be discussed in Chapters 6 and 7, where e-mailed URLs are used to predict future web requests. 56 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x y ' i-'m 2+q domain y ' M ) path ft Figure 3.17: Extend -> New Use Prediction 3.2.4.3 Delay — > ■ New Use Inferred t y ^ ~ Am 2 3 o C / 7 R E D N R R -yR R-y E R~y D R^yN E E^yR E — yE E-yD E-yN D D-y R D-> E D -yD D > N N N^yR N -yE N~±D N - > W Table 3.23: Delay -> New Use Prediction The last unlikely prediction is shown in Figure 3.18, where a Delay prediction generates a New Use prediction. The Delay prediction does not generate any new information but a New Use prediction may be inferred in certain applications. For example, a dynamically created web page, object P, may be used along with object M. When M is delayed, changes occur in domain x that require the new generation of object Q. Also, if the web cache provides accounting callbacks to a web server, it delays sending them while it collects more usage information. When the delay ends, it will issue a new transmission to the server. 57 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. domain x domain y ty ty+Am 2 Figure 3.18: Delay -» New Use Prediction 3.2.4.4 New Use — > New Use Inferred R E D N R R - > R R-y E R ^ D R-yN E E — > R E - > E E-y D E-yN D D -y R D-y E D-yD D-yN N N -y R N-y E N ^ D Table 3.24: New Use — » • New Use Prediction There are many examples of a New Use prediction generating other New Use predictions, the model shown in Figure 3.19. A web browser may predict a new page that in turn must be retrieved from a new web server. In order to make the connection to the new web server, a new DNS request is necessary to resolve the IP address. Cross-domain Web-DNS prediction will be examined further in Chapter 5. This combined prediction is possible between any applications that interact. 58 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. / domain x P 1 ? Q -------- > path a T path fi domain y > ty+An Figure 3.19: New Use -* New Use Prediction 3.3 Cross-Domain Prediction Opportunities Cross-domain predictive systems are complex to construct and may require altering both application implementations. This section will present two different cross-domain systems that have been studied in this work in reference to this model. The first, Web-DNS prediction uses a homomorphism to infer a predictor in the DNS domain. DNS resolution can add a round-trip or more to web connection setup. Chapter 5 will present data that makes the case for implementing this system. The second example, E-mail-Web prediction, provides additional Web predictors by examining e-mail messages that sometimes contain URLs. A detailed examination of this second system is given in Chapters 6 and 7. In addition to showing the opportunities for these predictions, this section will discuss example mapping functions between domains and will examine some implementation details. It will also discuss the expected benefits of these systems and the costs incurred in running them. 59 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.3.1 Web-DNS Prediction Although a DNS request is small, it can add an additional round-trip time or more to connection setup. The DNS system lacks predictors within itself, but requests are ultimately dependent on other applications. If these applications have predictors, they can be used to support allow DNS prediction. One possible application is a web browser, in which information about future web requests can be used to generate predictions of future DNS requests. Figure 3.20 gives a conceptual overview of Web- DNS prediction, suggesting that information from web pages is used to predict DNS requests. DNS domain names syntax tv +A web browsing html docs ty Figure 3.20: Web -> DNS Prediction Overview Web pages can predict other web pages, but they do not directly predict DNS requests, so cooperation between the two domains must be formalized with a homomorphism. Figure 3.21 shows the details of the prediction. The DNS request, P, maps to the web page that was the source of the request. Within the browser, HTML syntax predicts possible future web pages. Requesting the predicted web page is dependent on the related DNS request, Q. As a result, a New Use web page prediction generates a New Use (or sometimes Reuse) DNS request. 60 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. inferred DNS domain names <href> syntax request source usage dependency web browsing html docs t y t y T A n Figure 3.21: Web — » DNS Prediction (New Use — > New Use) The first mapping from the DNS to the web browser already exists in the application. Implementing Web-DNS prediction involves the web prediction and the mapping from the web page into the DNS. The web prediction can be satisfied in the browser by parsing web pages, looking for URLs that correspond to links the user might click on. The second mapping back to the DNS is the inter-application mechanism that passes predicted requests to the DNS resolver. Executing anticipated DNS requests can reduce web latency for first-time page requests to new servers. When the requests are closely spaced, reuse validation and further requests to the same web server are handled by persistent connections that do not need further DNS requests. Repeated requests on somewhat longer time frames will find the entries in the DNS cache, because the entries typically have a 24-hour lifetime. Web-DNS prediction can be further optimized by having the resolver bundle a collection of requests before sending them out. The resulting system combines 61 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. predictions in three domains: Web, DNS, and UDP packet headers. The predictor is a multi-domain inferred prediction: A/(Web) — > A/(DNS) — > D(header). 3.3.2 E-mail-Web Prediction As discussed above, web browsers can make some predictions based on the syntax of HTML files. Other intra-domain web predictions are possible, deriving from usage patterns or hints from web servers. However, there are pages that cannot be predicted because the request comes from outside the browser. If outside applications can predict web requests, they can cooperate with the browser to allow it to prefetch the corresponding pages that they end up triggering. One source for predicting web requests is e-mail messages that contain URLs. Figure 3.22 shows that syntactical parsing of e-mail messages can provide these URLs. web browsing URLs syntax e-mail reading e-mail msgs t y Figure 3.22: E-mail — » Web Prediction Overview The user is likely to continue reading an e-mail message until clicking on a URL within it, so the resulting homomorphism is an Extend — » New Use prediction; details are shown in Figure 3.23. The mapping from the browser to the e-mail client is based on user behavior. The user will be interacting with both software packages. 62 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The e-mail client will parse e-mail messages as the user reads them, looking for URLs to provide to the browser. inferred web browsing 1 URLs 1 usage pattern e-mail reading e-mail msgs usage syntax Figure 3.23: E-mail -» Web Prediction (Extend -» New Use) Cooperation between e-mail clients and web browsers needs explicit support in both applications. The e-mail client must be able to identify URLs in e-mail messages. The browser must have a prefetching mechanism. Both applications need support for passing URLs from the e-mail client to the browser. If the browser is not running when the user reads e-mail, a further benefit comes from launching the browser when e-mailed URLs are discovered. Such a system was implemented and studied as the core work of this dissertation. Chapter 6 presents the design of the system, presenting different implementation options and the rationale for the chosen system. Chapter 7 presents the results of the system in practice. Extended discussion of implementation can be found in Appendix A. 63 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 3.4 Multi-Domain Predictors The two-domain models can be extended to multiple domains by combining existing models and predictors. Additional mappings may be necessary to translate from the target domain to the source domain and back again. These mappings may not be symmetric. A series of source predictions may also be necessary. This section presents several different multi-domain combinations. Multi-domain predictions may be more complicated to implement and less efficient to use. The number of domains involved in the prediction indicates the number of applications that must be altered. The increased complication may translate longer durations to execute the prediction and higher risk of late or incorrect predictions. For simplicity, the following examples involve only New Use predictors. Any of the recurrence predictions can be substituted for either source or inferred predictions as long as they result in valid predictions and are allowed in the applications, as discussed previously. 3.4.1 Multiple Source Predictions in Series Figure 3.24 shows an example where multiple predictions are required in the source domain before a prediction can be inferred in the target domain. This situation can occur with Web-DNS cooperation. The DNS request P corresponds to a web request for page M. M can predict page N, but it is from the same server and does not require a new DNS request (especially if the web browser uses persistent connections). In turn, page N can predict page O, which comes from a different web server and 64 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. requires a new DNS request. Through the cooperation, this request, Q, can be executed in advance. domain x (DNS reqs) path a domain y (web pages) path [i t y t y ~ ^ A n / y “t“A n + 0 Figure 3.24: Multiple Source Predictions in Series 3.4.2 3-Domain Prediction Figure 3.25 shows a prediction that requires an intermediary domain to relate the source and target objects. When viewed more closely, this prediction more accurately represents the Web-DNS prediction discussed above. As before, domain x is the DNS application. The source prediction, in domain z, occurs with HTML files. But HTTP connections are required to download HTML files and this occurs in domain y. In this example, the mapping from P to M is the DNS request needed to set up the HTTP connection. The mapping from M to R is the HTTP GET request that downloads R. R predicts S with HTML syntax. S maps to N because the browser needs the connection to download the file, and N maps to Q because the domain name must be resolved as well. In this case, a prediction may also be inferred in domain y, 65 f _ y '1 ”^n+o+q Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. allowing the connection to the new server to be opened in advance. There may be other examples where predictions cannot be executed in the intermediary domain. domain x (DNS reqs) path a path P domain y > t (TCP cxns) { * > inferred H ? Q " S ' tz“ ^As+ n + q iz+As- domain z (web pages) path y Figure 3.25: 3-Domain Prediction 3.4.3 Asymmetric Mappings Figure 3.26 shows a multi-domain prediction where the mappings between the source and target domains are asymmetric. An extra domain is required to map from the target domain to the source domain, but there is a single mapping function from the source domain back into the target domain. 6 6 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. inferred domain x path a domain y path ft domain z path y t'Z tz~ ^ ~ ^ 5 Figure 3.26: 3-Domain Prediction with Asymmetric Mappings 3.4.4 Hybrid Predictions The example in Figure 3.27 is a combination of multiple domains and predictions in series. The source predictions themselves are in different domains. First, the target domain maps to object M in domain y. This object predicts N in the same domain. Then, N is mapped to object S in domain z. A second prediction occurs to yield object T. Finally T maps all the way back to Q generating the prediction in domain x. This example could also be reversed, first requiring the prediction in domain z, then the prediction in domain y. 67 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. inferred domain x path a domain y path domain z path y A"^~An i r /y + A n + r+ g Figure 3.27: 3-Domain Prediction with Multiple Source Predictors in Series Figure 3.28 presents one last example incorporating all of the prediction composition techniques presented in this chapter. A series of predictions, first in domain z then in domain x, is needed to generate the prediction in domain w. However, a fourth domain is needed to support the mapping from domain z to domain x. These examples show the basic principles of creating predictors involving three or more domains. Additional mappings are needed to construct these predictors. Predictions in series and asymmetric mappings may be required. Further examples to create an exhaustive study of multi-domain predictors are unnecessary. 6 8 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. inferred domain w | path a I H ? domain y path y domain z path 8 tz Q IfT ^y“^Au+s+n+o+q domain x path f$ tx Figure 3.28: Multiple Sources Hybrid Prediction 3.5 Summary Prediction is the only way to avoid latency. It is employed in many applications from computer hardware to computer networks, often in a single domain. These past two chapters have formalized predictors, enabling the methodical creation of new ones and the creation of predictors in domains that previously had none. This chapter explored the full design space of 2-domain predictors, discussed their use, and presented examples where they might be used. The multi-domain predictors developed in this chapter build on the single-domain predictors from 69 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Chapter 2. Homomorphism coupled with an existing predictor in a related domain allows the inference of new predictors in domains that lack them. More complicated predictors require additional mappings to relate objects in different domains. These techniques can be generalized to create predictors involving three or more domains. The next chapter discusses predictors in related work. Many of these are single-domain predictors, examples of the models developed in Chapter 2. There are a handful of examples of multi-domain predictors. Multi-domain predictors are more difficult to develop because they require looking beyond the target resource, considering the ways that it interacts with other applications. Despite the difficulty, cross-domain predictors are the only way to improve applications that have no internal predictors, or for which use of internal predictors has been exhausted. Chapters 5, 6, and 7 use the new tools developed in this chapter and apply cross-domain prediction. They explore the two specific opportunities for implementation introduced above, Web-DNS prediction and E-mail-Web prediction, in more detail. The Web-DNS predictor will be revisited in Chapter 5. A detailed examination of E-mail-Web prediction can be found in Chapters 6 and 7. 70 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4 Issues in Prediction and Related Work The previous two chapters focused on the mechanics of prediction and the effect prediction has on objects in the system. This chapter considers other issues in prediction and highlights related works where they apply. Although prediction is used in all areas of computer science, this chapter will mainly focus on Web prediction and other networked applications. Prediction is not limited to computer applications; other predictive systems will be discussed when they illustrate key issues. For the most part, the issues raised in this chapter apply to all predictions. Exceptions that apply specifically to cross-domain prediction will be highlighted. In addition to examples of cross-domain prediction, related work concerns the development and deployment of prediction in the Web. Reuse caching is extensively employed in browsers and proxy caches. Much work has been done to optimize caches with admittance and replacement policies. Another body of work attempts to predict new requests. This chapter is organized as follows. Section 4.1 considers participants in a prediction, which can be generalized as producers and consumers. Section 4.2 examines relationships used to make predictions. Section 4.3 discusses resources involved in predictions; some are conserved, others exploited. Section 4.4 explores relationships between prediction and failure. Some systems react badly to failed predictions, thus some predictions explicitly attempt to avoid failures. Section 4.5 presents specific examples of different types of predictions presented in the previous 71 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. two chapters, including cross-domain prediction. Section 4.6 summaries the issues discussed in this chapter. 4.1 Prediction Agents There are several participants, or agents, in a predictive system. The primary ones are the producer that originates predicted objects and the consumer that uses them. Each agent has a different view of the system and therefore a different approach to generating and executing predictions. Intermediary agents, such as proxies or middleboxes, handle objects between producer and consumer, and thus exhibit qualities of both. Cross-domain cooperation does not limit which agents may generate or execute predictions, but may introduce a new, external agent. The external agent is neither a direct producer nor consumer, but may be able to generate and execute predictions. In computer applications, producers may be servers that distribute files or information. They may also be resource managers controlling resource use. Consumers are clients or applications. In networked applications, intermediaries are mirrored or replicated servers, or proxy caches. Mirrored servers proposed by Smith [Smi94] and replicated servers implemented by Akamai [Aka] and others act as substitute producers. Proxy caches [DHS93, Gla94, LA94], such as middleboxes or transparent caches store files requested by clients and have features of both producers and clients. 72 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.1.1 Prediction Generation The agent that generates a prediction decides which objects to generate, use, retrieve, or retain. There are many examples where web servers generate predictions. These predictions can be tuned to aggregate request patterns or document popularity. Servers can also predict requests for dynamic pages and generate them before they are requested [SKS98]. In addition to predicting future object use, the server can control object caches by setting a “no cache” directive or distributing documents with short lifetimes [Wes95]. Increasingly, this accounts for uncacheable documents [DRJ01]. Server predictions require the server to identify clients to pass predictive information or objects. It may do so with subscription-based services such as AMP [NB97] or USC/ISI’s LSAM [TH98], Clients can generate predictions that are tuned to user preferences [WC96] or patterns [LD97], These predictions involve a range of servers, but may lack the “big picture” information available at individual servers. Proxy cache predictions [JC98] may behave more like client or server predictions depending on the number of clients they serve. Proxies identify popular documents from a range of individual servers and may also take advantage of user-specific knowledge. 4.1.2 Prediction Execution The agent that executes a prediction provides the predicted objects to the consumer. This action may be separate from deciding which objects to predict. Caches execute predictions when admitting or removing objects [KSW98a]. In the Web, execution involves transferring the object to the client. 73 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Servers that execute predictions, proposed by Touch [Tou94, Tou95] and Bestarvos [Bes96, BC96], push objects to the clients. The burden of distributing files to multiple clients may be reduced with multicast. This was tried with AMP, [NB97], WebCanal [Lia97] and LSAM [TH98]. Clients execute predictions by pulling anticipated objects [PM96, LD97] or by retaining objects in the cache. Client-side execution allows the client to efficiently manage its resources. Adaptive Push-Pull [DKP01] is a combination of push and pull that can reduce the burden on the server while maximizing object freshness. Proxy caches [JC98] may behave as clients or servers, combining the benefits of each. 4.1.3 Intermediate Agents Intermediate agents are distributors that may act in place of producers. They can reduce producer burden, increase the number of satisfied consumers, and provide redundancy in case of failure. For example, a farmer may grow com and sell it directly to consumers at a rural farmer’s market once a week. The farmer may also distribute the com to a chain of grocery stores. More consumers can be satisfied by grocery stores that are conveniently located and open daily. Intermediary distributors may increase the cost of com, but customers may prefer to shop at local stores rather than travel to the farmer’s market. These local stores have the added benefit of providing other products as well. In networked applications, mirrored servers act as additional producers, allowing more clients to receive direct satisfaction. These mirrors may be explicitly identified with individual names, or they may operate implicitly through DNS 74 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. redirection. Proxy caches, like Squid [Squ] act more like distributors, aggregating both clients and producers. They may be implicit or explicit. The number and inter-organization of intermediary agents may affect how well they can satisfy clients. Placement of intermediaries must balance deployment costs and expected benefits. Those located near clients may provide the best service, but may suffer limited clientele. High-traffic locations may serve the greatest number of clients, but may be expensive to deploy and maintain [GS95]. Active intermediaries, such as Adaptive Web Cache [ZFJ97] and Self-Organizing Caches [BCZ97], can adapt to request loads, placing caches where most needed or best used. Hierarchical intermediaries combine express client-side service and high- traffic client aggregation. Hierarchical web proxies, like Harvest [CDN96], that are closer to clients provide quick responses but store a limited number of documents. More distant proxies have a larger set of clients and therefore store a larger set of documents. They can satisfy more requests, but with larger delay. An analogy can be made with food distribution: convenience stores offer a limited selection of very popular products on every comer, whereas full-service grocery stores offer a wider selection of food but are less populous. Intermediaries may be organized into peer groups [JDB96, GRC97, KSR98b, RF98] where peers offer identical or specialized service. Requests that cannot be satisfied by one peer may be put to the group before being passed to the server. Hybrid combinations of peer groups and hierarchies combine the strengths of each configuration [TDV98, TH98]. 75 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.1.4 A gents in Web Prediction Table 4.1 organizes web predictions by generation and execution. Columns correspond to prediction generation, rows to execution. Because proxies may act as clients and servers, the type of execution they achieve must be differentiated. Web cache admittance and replacement predictions are usually generated and executed on the client. In the table, these are identified as “cache management”. Although this table groups together many different works in the same categories, each is distinguished by the information it uses to generate predictions and the resources they seek to optimize. Cross-domain work is highlighted with italicized text. The examples presented in later chapters are explicitly named in the table. 4.2 Predictive Information This section explores information used to make predictions. Chapter 2 discussed predictive relationships between objects or actions, considering both object characteristics and usage patterns and their implications for automating prediction. Predictions may also be reactive, where events determine the course of future actions or the demand on certain objects. Available information may affect the type of prediction an agent can make. Cross-domain predictions may be based on any of the information sources presented here, but are particularly suited to reactive predictions, as will be discussed. 76 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Server Prediction Proxy Generation Client External Server Touch [Tou94] [Tou95]; Gwertzman [Gwe95]; Wessels [Wes95]; Bestavros [Bes96] [BC96]; Markatos [MC96]; DNS Hints [ CV97J; AMP [NB971 d o '■ g Proxy Push o < L > Push-Caching [LG96] Smart Caching [DCW96]; Tewari, et. al. [TDV981 W a - 4—> o '* 3 o & Proxy Pull Cohen, et. al [CKR98] Smart Caching [DCW96]; Chinen, Yamaguchi [CY97]; Jacobson, Cao [JC98]; Adaptive Web Caching [YZL011 Client Padmanabhan, Mogul [PM96]; Hine, et. al. [HWM98]; Duchamp [Duc99] Fan, et. al. [FCL99] Padmanabhan, Mogul [PM94]; Jiang, Kleinrock [JK97]; cache mgmt; Means prefetching [CKOO]; Web-DNS E-mail- Web Table 4.1: Web Prediction Generation and Execution 77 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.2.1 Object Characteristics Object characteristics are both internal and external. Internal characteristics depend on an object’s content and are either syntactical or semantic. They require an understanding of object composition that may be limited to the consumer. External characteristics can be determined solely by observing an object [KSW98b], or the side effects of object use [Tou94] and can be employed by any predictive agent. Predictors based on object characteristics may be tempered by usage patterns or reactive predictions and are easily automated in computer applications. Content-based predictors usually function by parsing objects [DCW96, CY97, WM99c]. HTML syntax refers to other objects that may be requested either to display in parallel with the current object or in the future [CY97], Caching algorithms may use this information to decide which documents to store or replace [WM99c]. Property-based predictors consider the attributes of an object or action, usually in the context of its environment. Cache admittance or replacement algorithms are based on attributes such as object size [MAM98], type [CDN96, WAS96], retrieval time [BH96, SSV97, WA97], expected lifetime [RF98], or a combination of these attributes [CI97], Resource schedulers may consider execution times and application deadlines. 4.2.2 Pattern-Based Prediction Historical patterns can suggest future use based on object popularity [MC96], groupings [TH98, CKR99], or expected usage sequences [Bes96, BC96, PM96, YZL01], Patterns also form the basis for cache replacement algorithms [PR94, 78 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. KR98]. For consumers, patterns usually suggest reuse but can filter other prefetching based on user profiles [CJ97]; for producers, patterns can predict new use in consumers. A cyclical pattern is one that repeats itself within some period. This period may affect its utility. Short cycles allow constant prediction. Grocery stores use daily and weekly cycles to predict which products to stock and in what quantities. Fluctuations in hourly cycles allow public transportation authorities to schedule busses and trains to handle demand. Similar cycles have been observed in the web, suggesting prefetching algorithms that also predict when documents should be available. Long cycles may cause occasional disruptions in applications that are optimized to shorter cycles. Cache replacement algorithms may discard valid objects that have not been used recently, without regard for the expected reuse when the cycle repeats. In order to meet these occasional demands, additional provisions may be necessary. For example, airlines fly half-empty planes on some routes in order to move them to areas of greater future demand. 4.2.3 Reactive Predictions Sometimes actions occur in response to other actions or events, called trigger events. The response is usually a specific increase in object popularity. For example, certain weather conditions cause people to stock up on food supplies and to purchase weatherproofing materials for their homes. Some of these conditions, like winter storms or hurricanes, can be predicted with enough lead time to employ precautions. 79 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Others, like tornadoes, are highly variable and only give enough warning for people to take cover. Other natural events, like earthquakes, strike without warning and it is only possible to predict the need for recovery supplies. The weather-related examples generate recurrence predictions. Requests for entirely new objects can be generated by a trigger event. A trigger event can be created through advertising. New products, such as movies or software, are promoted well in advance of availability so that they are instantly popular. Vendors anticipate this popularity and provision accordingly. Sometimes the trigger event is hidden. If the event can be exposed, the response can be predicted. One example is the “Slashdot effect” [Adl99]. Web pages that are discussed on this popular message board experience sudden increases of traffic, often crippling the host server. To the server administrator, the cause of the new popularity is hidden. A delay in message posting might allow the content to be moved to a more robust site. When the trigger event can be predicted, the reactive prediction is cross domain. For example, the prediction of inclement weather patterns allows the prediction of weatherproofing sales. In web applications, more work is needed to identify trigger events and to speed the deployment of the necessary resources. 4.3 Prediction Resources Prediction resources include not only the specific objects being predicted, but those that are optimized and exploited by the prediction as well. They represent the costs and benefits of the prediction. Predicted objects may be stateless, such as web 80 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. documents, disk blocks, DNS records, or routing entries, or they may be resources requiring state, such as server connections or compiler branches. The optimized resources define the goals of the system. In the shopping examples, the goal is to retain customers and attract new ones. Web servers try to improve the user experience by reducing latency. Other web optimizations aim to reduce server load and network bandwidth. Computer applications may also optimize storage resources, execution latency, or processor cycles. The exploited resources define the costs of the system. The web server may reduce latency by pushing documents to the client, exploiting bandwidth. For networked applications, these resources include server load, network bandwidth, and latency. Other applications may exploit redundant or idle resources such as processor cycles and storage. Web predictions are employed both to reduce server and network load and to reduce user-perceived latency. In some cases, these goals conflict. Aggressive prefetching can reduce latency, but increases request traffic. Load reduction that multicasts responses or shifts requests to proxies can increase delay for some requests. 4.4 Prediction and Failure Prediction can be used to avoid failure or reduce the impact of failure in critical systems. Failure avoidance often involves over-provisioning critical resources or deploying redundant systems. Intermediate agents may serve as redundant distributors. 81 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Cache coherence mechanisms attempt to increase the lifetime or validity of cached objects, avoiding failure when these objects are needed. Like other predictions, object coherence can be determined by both the producer, through notification [CDN96] or push [NB97, KR01], and the consumer, either proactively [KW97] or on demand [Apa, Moz, Net], Cooperating intermediaries may also distribute updated copies when changes are detected [TDV98], Coherence can be updated periodically or on demand. Sometimes object lifetimes can be extended in the way that food preservatives increase shelf life. Web objects are subject to changes; invalid objects can be replaced with valid versions [CK01] or updated with relevant changes [WAS96, BDR97, MDF97, MKD02], Other work is underway to increase document cacheability [FCD99, WM99a, WM99b, WMOO] and to cache dynamic objects [CZB98, CID99, SAY99], This section also considers the repercussions of failed predictions. They increase the costs in an application and may cause other failures as well. A failure of provisioning translates to unavailable products that may be costly to obtain. Sometimes, other products may be substituted; movie distributors make reactive predictions when they release small movies on the same weekend as expected blockbusters, hoping to catch sell-out spillover. When failures occur in web caches, unpredicted requests must be satisfied by the server, causing delays. In systems that routinely depend on accurate predictions, a failed prediction or unpredicted event can cause other failures. Airlines schedules are optimized for error- 82 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. free operation. A single mechanical failure or cancelled flight can displace passengers on many routes and it may take days to recover. Sometimes predictions overestimate the need for an object. In stores, over stocked items occupy shelf space that could be used by other items. Returning surplus to the distributor incurs further costs; selling these items at a discount cuts profit. Libraries also face the problem of managing shelf space, accounting for circulation when purchasing new lending materials [Buc75]. In caches, storing objects that will no longer be needed may displace more useful objects. If they can be detected, deleting them is not costly. 4.5 Prediction Types Chapter 2 introduced four base predictor types: Reuse, Extended Use, Delayed Use, and New Use. Chapter 3 extended them to predictors that involve multiple domains. This section presents specific examples of these predictors as deployed in other work. 4.5.1 Reuse Predictions Caches are the primary example of reuse predictions. Web browsers [BCC95] and proxies [Apa] store web pages and embedded objects in file system and memory caches. Web servers use memory caches to reduce disk accesses and latency for frequently requested files. Reuse predictions also motivate cache coherence algorithms, which try to predict both if an item will be used again and whether the 83 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. item has changed since it was last used. Caches are also used in file systems, compilers, operating systems, and hardware. 4.5.2 Extended Use Predictions Extended Use predictions are useful for managing resources or connections. Applications that lease resources may predict the extension of their use. In the web, persistent HTTP connections [Mog95, FGM99] are the most common example. Maintaining the connection to a web server avoids incurring additional setup delays for future requests to the server. Extending HTTP connections adds an additional management burden on both the client and the server machine that might be managed through cooperation [CKZ99]. 4.5.3 Delayed Use Predictions Delayed Use predictions allow an application to maximize the impact of an action by aggregating dependencies. In TCP, the Nagle algorithm [Nag84] delays transmission of small packets awaiting more data. In the web, there have been several attempts to collect requests for popular pages and multicast the response to all [CA95, Ham95], Multicast minimizes the number of times that the server must transmit the page and can reduce the number of copies in the network, but it may cause users to wait longer for pages. 4.5.4 New Use Predictions All prefetching works discussed above, whether occurring at the client, the server, or an intermediary, are examples of New Use predictions. Other examples of 84 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. New Use predictions in the network include replicated or mirrored servers. The content provider attempts to predict which pages will be requested and moves the content closer to the clients, such as in LSAM [TH98] or Adaptive Web Caching [ZFJ97], This also requires predicting where the new clients will be located. Replicated servers differ from prefetching proxy caches in where the prediction is generated and what objects can be predicted. Proxy caches usually operate as clients and can only manage static documents. Replicated servers may server the full range of objects on behalf of the parent server. 4.5.5 Cross-Domain Predictions Each predictive application resolves the above issues in ways that distinguish it from other applications. For the cross-domain Web-DNS prediction that will be presented in Chapter 5, the web browser is a client that generates predictions for the DNS resolver based on the content of web documents. The resolver executes predictions, increasing the load on remote DNS servers and increasing storage requirements for the local cache. Overall, the system reduces connection setup latency. Failed predictions increase the size of the cache and require new requests to resolve names that could not be predicted. A secondary prediction of aggregating requests is also possible. Two other cross-domain DNS prediction examples appear in other work. Cohen and Kaplan [C K O O ] implement DNS prefetching as a by-product of prefetching the “means” for web requests. The web browser generates predictions based on document content or user request patterns. The prefetcher then initiates speculative 85 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. connections and sends dummy requests sets up state needed to reduce latency for actual requests. Opening these predictive connections exploits stateful resources in the client, network, and server by making these speculative dummy requests, consuming resources that may be needed by other non-speculative requests. DNS resolution is also predicted in [CV97] where IP addresses are pushed to clients in place of server names in HTML documents. In this work, the web server generates and executes predictions based on the content of pages it serves. While pushing IP address eliminates DNS resolution from connection setup, IP addresses provided to the web server may differ from those that would be provided to clients. DNS redirection, by Akamai [Aka] and others tries to point clients to replicated servers near them. Also, pushing IP addresses in place of domain names may cause increased delays for subsequent requests. If not universally implemented, the first request will be via IP address, but later requests will contain names that now must be resolved. In E-mail-Web prediction is presented in Chapters 6 and 7. Predictions are generated by the e-mail client based on message content and are executed by an intermediary, the preloader. Prefetching web pages exploits server and network load and requires storage space in the intermediary cache. As with DNS prefetching, failed predictions increase cache size and require new requests. 4.6 Summary The related work presented in this chapter involves prediction in the web. Examples of each of the four base predictors were presented. Reuse caches reduce 86 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. latency for repeated requests. Extended Use persistent connections remove connection setup latency for multiple requests to a given server. Delayed Use predictions appear in systems that aggregates requests and multicast responses. New requests can be satisfied with prefetching. Similar projects differ in where the prediction occurs (server, proxy, or client) and in what information is used to generate predictions. Some cross-domain efforts were also examined. Several different projects use web information to predict DNS and connection setup. In DNS pre-resolution [CV97], the server replaces domain names with IP addresses in pages it distributes. “Means” prefetching [CK01] is a client-side scheme that speculatively opens connections to servers and sends dummy requests to initialize stateful resources. With Web-DNS prefetching, the browser parses web pages for possible future requests and resolves corresponding domain names. This will be explored further in Chapter 5. E- mail-Web prediction uses e-mailed URLs to predict web pages and will be presented in Chapters 6 and 7. Challenges to prefetching mean that practical efforts been directed at relocating content through replicated servers and distributed proxies. Chapter 7 provides a detailed discussion of these challenges and some potential. 87 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5 Investigating Web-DNS Prediction Most Web requests require DNS requests to resolve target Web server names. These DNS requests can contribute significant overhead to Web connections. The relationship between Web documents and DNS records forms a foundation for cooperation between these two caching systems. This chapter presents investigations showing that cross-domain prediction between Web caches and DNS caches can provide increased latency reductions [HT99, CK01]. In Web-DNS prediction, predictive structure in a Web cache can be shared with a DNS cache. The DNS cache can use this new information to prefetch objects that may be used to retrieve future Web documents. Figure 5.1 shows how Web and DNS requests are related. The user wishes to visit www.domain.com. To contact the web server, the browser must resolve the domain name into an IP address, issuing a request to its local DNS name server. This server is located either on the user machine or on another machine in the same domain. If the name server does not have the necessary record, it either forwards the request to its parent in a name server hierarchy or contacts the authoritative server directly. Either option may require several message exchanges incurring additional latency with each request. Once the web server IP address is obtained, the local name server caches the address and passes it to the browser. The browser may also cache it. Now the browser can contact the web server and request the necessary document. 88 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1: www.domain.com DNS nam e server 4: A.B.C.D Browser '.ache ■ v 5: GET /index.html 6: index.html 2: www 3: A.B.C.D domain.com DNS Server W eb Server user machine Figure 5.1: DNS and Web Request Interaction Timing measurements of Web requests indicate that clients with a high-latency connection setup, either due to a high-latency first hop or distant servers, would benefit from a local DNS cache. The DNS request represents a significant portion of connection setup on these clients, one third to one half of the total connection overhead, because the server is as far away as its DNS [HT99], Squid [Squ] is a web proxy cache is deployed at many sites. Request streams from Squid logs indicate a high percentage of server name reuse suggesting that a DNS cache would be heavily used, with potential hit rates up to 85-95%. This hit rate is much higher than the demonstrated reuse rate of 30-50% for Web caches [Gla94, ASA95, CDF98], A trace-driven simulation of the DNS cache using Squid logs to model individual clients was created to measure the burden of a DNS request on small clients such as PDAs or similar personal network presence devices. The simulation downloaded HTML documents in the request stream and preloaded the DNS entries corresponding to internal references. The result is that anticipation increases the size 89 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. of the DNS cache by a factor of two to three. Improvement to the hit ratio was 15%. Squid logs were also used to explore international requests. These requests usually involve a high-latency link, such as a satellite, and DNS prefetching can reduce user- perceived latency for connection setup. This Chapter discusses and extends work found in [HT98], Section 5.1 illustrates the impact of the DNS request on Web requests and shows that local DNS caches can reduce latency. Section 5.2 shows the high amount of reuse in Web server names and the advantages and costs of anticipating them. Section 5.3 explores requests that cross continents. Limitations of this analysis and a summary are presented in the Section 5.4. 5.1 DNS Overhead in Web Requests When a client performs a Web request, there is an initial DNS lookup which can add significant delay to the connection setup, depending on the configuration of the network and the location of the DNS server. If there is no local DNS cache and the first hop is a high-latency link, the DNS transaction will be a significant component of the overhead. The impact of DNS requests in several network configurations will be shown below. An individual Web transaction starts when the browser sends a request to resolve a domain name for a new web connection and ends when the final closing acknowledgement of the TCP connection has been received. For the user, the most significant delay occurs during connection setup, while waiting for requested data to first appear in the browser. For the analysis in this section, this duration is called 90 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Start-Total. Start-Total begins with the DNS request and ends when the first data packet is received. It can be broken down into three pieces. The first piece is the DNS request. This request goes to the client’s configured name server and then perhaps to the authoritative server for the desired domain. Once the server name is resolved, the client can open a connection to the Web server. The second piece, Connect, starts when the client issues the first TCP SYN packet and ends with the arrival of the SYN/ACK. The third piece, called First-Response, begins with the transmission of the GET request, and ends when the client receives the first packet of response data. To compare the duration of connection setup overhead to the time it takes to receive all the data packets, a fifth duration called End-Total starts with the DNS request and ends when the TCP FIN is received, indicating the end of a simple Web transaction. These five durations are illustrated in Figure 5.2. Although the DNS request is modeled as a single exchange in Figure 5.2, it may involve requests to multiple servers, shown in Figure 5.3. If the user’s local DNS server does not have the record, the server must request it from the authoritative server for that domain. Locating the authoritative DNS server may require a request to the root DNS server. Each of these requests increases the cost of the DNS component of connection setup. 91 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Client DNS server 1: DNS 2: Connect 3: First-Response 4: Start-Total 5: End-Total Request Response SYN/ACK DATA DATA DATA FIN/ACK Figure 5.2: Web Connection Components Client ISP DNS server Root DNS server H 3 CD W W eb DNS server Server Figure 5.3: Extended DNS Request Tracing these five durations with different network configurations for 200-300 user requests resulted in the following four cases. In each configuration, the client 92 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. sends requests to a single Web server. To model connections to a set of different servers, the client does not use persistent connections and does not maintain a DNS cache. In the first two cases, the client’s first hop is a low-latency LAN connection. In the third and fourth cases, the client is connected over a high-latency ISDN line. In each set of two cases, the first represents requests sent to a distant server, and the second represents requests sent to a server on the LAN. 5.1.1 LAN-Connected DNS Server (Cases 1 and 2) There are two cases of a LAN-connected DNS server: remote web server and local web server. Figure 5.5 shows connection times for a client connected via a LAN. As illustrated by the network diagram in Figure 5.4, the remote server is located on the far side of the network cloud (Case 1). The DNS server is located on the client side of the network cloud. In the plot, times for the DNS duration are represented by the line on the far left, labeled with the number 1. Because the DNS server is located much closer to the client than is the Web server, the DNS overhead is negligible, 1-2 orders of magnitude smaller than any other part of the connection. 93 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Network Server Client DNS Figure 5.4: Network Diagram for LAN with Remote Server 100 1: DNS 50 - 2: Connect (A < / > 4 0 - a > §- 30 a > “ 20 - 3: First-Response 4: Start-Total 5: End-Total 10 - 100 0.1 1 10 0.001 0.01 Seconds (log) Figure 5.5: Case 1 - Web Connection Breakdown for LAN with Remote Server In Figure 5.6, the client is connected to a Web server on the LAN. In this network, the DNS server is the same distance from the client as the Web server (Case 2). In Figure 5.7, the Web server connection, line 2, costs the same as the DNS request, line 1. Again, for a LAN connection, the DNS component is a very small part of the connection overhead. 94 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. I I- Client Server DNS Figure 5.6: Network Diagram for LAN with Local Server •o 0 ) C O C O < / > +■» < / > a > 3 a * a > 0 1 0.001 0.01 0.1 1 Seconds (log) IUU - 90 f f 80 - y 11 70 - < 11 60 - ; If 60 - II .......... 1: DNS 40 - > f t .......... 2: Connect 30 - ' / / 3: First-Response 20 - i 1 / .—— 4: Start-Total 10 - ; IJ n . 1 2) 3 4A 10 100 Figure 5.7: Case 2 - Web Connection Breakdown for LAN with Local Server 5.1.2 ISDN-Connected DNS Server (Cases 3 and 4) Again, there are two cases of the ISDN-connected DNS server: remote and local web server. The impact of the DNS request changes for a client connected to the network with an ISDN line. In this case, the bottleneck is located in the first hop. The next two cases show the connection times for this client. In Figure 5.8, the configured DNS server is located on the far side of the first-hop bottleneck, but before the 95 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. network cloud (Case 3). In Figure 5.9, the DNS request is similar to the initial Web server connection (line 2) and the time needed for the first response (line 3). It accounts for about one-third of the Start-total. In most cases, the DNS request takes longer than a tenth of a second, a delay that is noticeable to most users. Client Network Server ISDN line DNS Figure 5.8: Network Diagram for ISDN with Remote Server 100 90 cr 80 ^ o' v 70 a > a 60 h C O a 4 0 -i a > g- 3 0 -I v * 20 10 - 0 0.001 0.01 1 r ' ? 3 0.1 1 Seconds (log) .......... 1: DNS .......... 2: Connect 3: First-Response — ****— 4: Start-Total ---------- 5: End-Total 10 100 Figure 5.9: Case 3 - Web Connection Breakdown for ISDN with Remote Server 96 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The network configuration in Figure 5.10 eliminates the delay imposed by the remote connection, and shows the case where the DNS server and the Web server are equidistant from the client (Case 4). In Figure 5.11, the DNS request is the largest delay, nearly half of the Start-total, and takes upwards of one-tenth of a second. Client ISDN line Server DNS Figure 5.10: Network Diagram for ISDN with Local Server 1: DNS 2: Connect 3: First-Response 4: Start-Total 5: End-Total Seconds (log) Figure 5.11: Case 4 - Web Connection Breakdown for ISDN with Local Server 97 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. In each of the previous cases, the client contacts a single Web server. If the client were using persistent connections, the aggregate connection overhead would be reduced, magnifying the impact of the DNS request shown in Equation 5.1. With individual connections, the DNS lookup occurs a single time and each request requires a connection to transfer the document. With persistent connections, the total time required for a set of transfers is reduced because a single connection is established. However, the impact of the DNS lookup becomes more pronounced as overall connection time is reduced. In this analysis, repeatedly connecting to a single Web server is a simplification of connecting to a variety of Web servers. With multiple Web servers, persistent connections are not relevant. In either case, the ISDN client would benefit from maintaining a DNS cache. The next section quantifies the possible benefit and costs of doing so. A = Document Transfer Time B = Connection Establishment Time C = DNS Request Time A + B + C = Total Connection Time n = Number of Requests C < C An + Bn + C An + B + C Individual Persistent Connections Connections Equation 5.1: Relation of DNS Overhead to Total Connection Time 5.2 Web Server Name Reuse and DNS Optimization As discussed above, DNS caches and Web caches are related by how they are used by their parent application. The domain name of the origin server must be resolved before that server can be contacted for the Web request. When the two 98 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. applications cooperate, next-hop information in the Web cache can be used to preload the DNS cache. Figure 5.12 gives an overview of the inferred prediction. Because preload requests are not user-driven, they can be aggregated for further benefit. DNS domain names syntax web browsing html docs ty Figure 5.12: Web — > DNS Prediction Overview In this section, Squid logs were analyzed as typical client request streams, with each client examined separately. These daily logs contained requests from both individual users and client caches. They were obtained from the six root NLANR [Squ] caches daily for one month. A simple analysis of the client request stream indicates that caching all DNS entries on a busy client could satisfy nearly 90% of all DNS requests. In addition, the overall size of the cache for a 24-hour request cycle is relatively low. Figure 5.13 compares the size of the DNS cache to the probability of a hit for one client. This figure presents an upper bound for the hit rate, given an optimal replacement policy. This upper bound of 90% is reached at a cache size of 5000 items. Using an approximate entry size of 250 bytes, 5000 entries translate to a local DNS cache of about 1.25MB. Caching all the entries for the day would increase the cache size to about 2.25MB, about 10% of a corresponding Web cache. Although cache size varies 99 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. with the activity level of the client, the hit rate below is representative the clients in the logs examined. 100 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 Size of Cache (# of entries) Figure 5.13: Maximum Hit Probability per Size of Cache The next few figures examine how the DNS cache changes with anticipation, using next-hop Web information. For each request stream, each HTML file was downloaded in turn. Internal reference information was collected and new server names were treated as requests for DNS prefetches. Even though the number of misses is low, Section 5.1 shows that in the case of a DNS miss, the cost of the DNS request can be larger than the cost of contacting the server, comprising as much as 50% of the total connection setup cost. Reducing this cost with anticipation will reduce the overall latency for the client. Anticipation increases the size of the DNS cache, but not so much that it is prohibitive. Figure 5.14 presents the size of the DNS cache over time for a single Squid client. The cache grows as the client makes more requests. The lower line 100 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. represents simple caching, where entries are added to the cache as they are requested. By the end of the day, the cache has grown to approximately 9000 entries when retaining all entries, as is typical of a DNS cache. The upper line represents anticipation, where all internal references are harvested from HTML documents and cached in addition to the original DNS request. 25000 % 20000 - L_ + • » C < D o 15000 - 0 ) J C ra 10000 - o o .§ 5000 to Simple Caching Anticipation 10 12 14 16 18 20 22 24 2 4 6 8 0 Time (hours) Figure 5.14: DNS Cache Size over Time Figure 5.15 compares the sizes of the caches with and without anticipation. With anticipation, the size of the DNS cache increases by a factor of 2.5, to 6.75 MB. For most clients, this is not prohibitive. 101 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4 3.5 < o ■ £ ^ <o o CO J 2.5 o O N 1 .................... 1 ..................... 1 ............................1 ............ 1 ------------- I -------------------- 1 ----------------1 ---------------- 1 ---------------- 1 ....................1 ....................— “ 1 ----------- 0 2 4 6 8 10 12 14 16 18 20 22 24 Time (hours) Figure 5.15: Size of Anticipation Cache Compared to Size of Simple Cache The next two figures examine how anticipation changes the hit rate and the miss rate over time. Figure 5.16 presents the hit rate for simple caching (lower line) and caching with anticipation (upper line). After the initial cache loading period in the first hour, the hit rate for simple caching approaches the rate expected in Figure 5.13. Although DNS anticipation does yield an improvement, the total benefit to individual clients as measured is small. Figure 5.17 shows the reduction in misses made possible through cooperation with the Web cache. This translates to a significant reduction in delay because each miss can contribute up to 50% of the connection cost. Because DNS records typically expire after 24 hours, the results shown at the end of the day in each plot represent the maximum that would be obtained through sustained use. 102 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 100 90 80 70 - ■ 60 - 50 - 40 - 30 - 20 10 0 0 -Simple Caching Anticipation 10 12 14 Time (hours) 16 18 20 22 24 Figure 5.16: Proportion of DNS Requests Satisfied by Cache 20 c o 0 3 * D Q > 0 1 ( 0 O ' (A (A i 10 12 14 16 18 20 22 24 0 2 4 6 8 Time (hours) Figure 5.17: DNS Miss Rate Reduction As discussed in Section 5.2, the DNS cache itself contains little information to support anticipation or aggregation. The benefits from anticipation in Web-DNS prediction are straightforward as discussed above. With anticipation, a DNS cache has the ability to aggregate requests for further savings. In the data set collected, an 103 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. HTML file that contains external references includes an average of 6-7 external servers. Because these requests are small, they can be combined into a single packet. In most cases, the responses will be small enough to be combined as well, for a further reduction in the number of packets and per-packet processing costs. 5.3 International Requests When the web client and the necessary servers are located on different continents (or different planets, in the near future), requests often traverse a high- latency link, such as a satellite. In these cases, the request latency is dominated by the transfer latency and reducing the number of round-trips between the client and server can significantly reduce user-perceived latency. Persistent connections help for multiple requests, but the first request is still very costly. The impact that this has on the user depends on the number of requests the made to distant servers. A desired web server is not always located near its corresponding DNS server. Many global companies have web servers located throughout the world, all with a single authoritative DNS server, others use distributed DNS caches such as UltraDNS [Ult]. An accurate assessment of the total latency for a connection must consider the locations of the DNS and web servers with respect to the location of the user. Figure 5.18 shows the average daily destination distribution of web requests in the Squid logs examined above. All clients are located in the United States. About 78% of all servers contacted are in the .com, .net, and .org hierarchies, accounting for about 88% of all requests made. From the data available, it is not possible to determine where the individual web and DNS servers in this group are located, but it 104 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. is likely that a large number of them are located in the United States. With the remaining servers, the top-level country code is used to determine the location of the web and DNS servers. From this metric, 8% of the servers are located in North and South America. The remaining servers are located on other continents. Prefetching the DNS records for these servers can significantly reduce the latency for these requests. Requests Servers ‘ .corn; *.net; *.org Asia Europe Americas Other Figure 5.18: Daily Distribution of Requests and Servers in Squid Logs Data was unavailable for the distribution of requests originating from other continents. Anecdotal evidence suggests that a large proportion of these requests are for servers within the United States. As compared to U.S. clients, these clients have an even larger latency burden due to DNS requests. 105 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5.4 Web-DNS Summary This chapter explored Web-DNS cooperation. Although some benefit is shown, Squid log information is limited for modeling Web-DNS cooperation and thus the benefits presented above are only approximations of the true benefits. Clients extracted from the Squid logs often represent other aggregate caches instead of individual users, and the request streams are likewise combined. Further, accurate analysis requires the examination of every document in the request stream, not possible after the log is collected. To better quantify DNS reuse, DNS hits and misses need to be defined. With a Web request, the cache lookup is binary: the document is in the cache or it is not. For a DNS request, the relationship is more flexible. A DNS cache record stores a collection of information. For example, consider a request for www.yahoo.com. The initial request is a complete miss. After the request, the DNS cache stores the IP address for this site as well as information about the authoritative DNS server for the domain yahoo, com. Later requests for www.yahoo.com would yield a complete hit. A later request for maps.yahoo.com would not find the IP address in the DNS cache, but would find domain server information. This is a partial hit. It is not clear whether the partial hit is as costly as a full miss. Another problem with this analysis is that Squid logs mask the original user request. Some browsers allow users to enter a type of request shorthand, yahoo for www.yahoo.com, that masks the actual number of requests needed to resolve the server name. Preliminary investigations suggest that when this type of shorthand is used, the 106 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. browser makes a series of intelligent guesses about the actual server name. Each of these requests generates a failed DNS request until an actual domain is found (or the request fails completely). Overall, this analysis shows that simple latency reductions are possible by placing a cache on the user machine. Doing this will co-locate the Web cache and the DNS cache, providing the opportunity for cooperation. Web-DNS prediction is a good example of cross-domain prediction; a simple retrieval analysis shows that some DNS lookups can be satisfied by prefetch with new reductions in user latency. 107 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 6 E-mail-Web Design and Implementation User-perceived latency in the web is a serious problem that cannot be solved by simply adding resources. Caching can reduce latency for reused documents but does not help for new requests or for repeated requests for dynamic pages. Persistent connections reduce connection setup latency for additional requests to recently used servers but they do not remove transfer latency and they do not provide benefits for connections to new servers. The only way to completely avoid user-perceived latency is to prefetch pages while the user is busy with other activities. Prefetching requires good prediction algorithms to determine what to prefetch and to prioritize requests to reduce their impact. The web has many opportunities for prediction. Browsers can track local request patterns, bookmark entries provide a list of frequently visited pages, HTML syntax contains references to possible future requests, and servers can provide hints about popular pages or common request patterns. Unfortunately, these methods cannot predict every URL a user will request. Cooperation with other applications that provide unpredicted URLs, such as e-mail clients, allows more prefetching. Chapter 3 identified e-mail messages as a source for outside URL predictions and gave an overview of E-mail-Web prediction. Figure 6.1 presents the usual interaction between a browser/e-mail client and related servers. For web requests, the browser contacts the web servers indicated in each request. For e-mail messages, the browser contacts the user’s e-mail server and downloads messages. Sometimes these 108 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. e-mail messages contain URLs the user might request. E-mailed URLs should be highly cacheable because the sender intends to refer to a specific item. web servers browser user machine e-mail server Figure 6.1: Browser Interaction with Web and E-mail Servers This chapter describes E-mail-Web prediction in detail and presents a test system implementation. Section 6.1 describes the approach taken to implement the test system and details the design goals. Section 6.2 presents the implementation. Section 6.3 details the installation of the system. Chapter 7 presents the results of these tests. Appendix A provides further implementation details. 6.1 Design Approach The E-mail-Web test system includes both data collection and a prototype e- mail URL preloader. Data collection involves examining user interaction with URLs and categorizing URLs that arrive in e-mail messages. The preloader must examine incoming e-mail messages to find URLs and download and store them for the browser. Figure 6.2 shows E-mail-Web prediction. The implementation requires an e- mail parser that finds URLs within e-mail messages and a preloader that fetches e- 109 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. mailed URLs and caches them for the browser. If these components are implemented separately, there must be support for communication between them to share the URLs. inferred web browsing D | URLs 1 H ? usage pattern e-mail reading e-mail msgs ( y f A m+q syntax usage (y+Am Figure 6.2: E-mail -» Web Prediction (Extend — > New Use) The list of URLs the user requests and the sources of those requests are needed to understand which URLs the browser can and cannot predict. The list of user requests is a subset of the list of all URLs that the browser requests, namely those HTML documents that are the primary requests for a web page. URLs for dependent objects, such as in-line images or frame contents, can be predicted by the primary pages. The request source indicates where the user found the URL, either within the browser or externally. URLs from within the browser can be predicted. These include requests that originate from a user click in the current web page (collected by parsing HTML files) or requests selected from the bookmark list or other configurable buttons, such as “Home” or “Search”. The browser cannot itself predict external URLs that are hand-typed or pasted into the browser, or those from other applications that may launch the browser. 110 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The e-mail client must record the list of all URLs found in e-mail messages. Later analysis will determine the frequency of URLs in e-mail messages and whether these URLs might be cacheable. Parsing e-mail messages for URLs will discover references to images or applets that enhance e-mail messages, called “SRC” URLs. For e-mail messages composed in HTML, SRC URLs represent other opportunities for prefetching, so data about these URLs will also be collected. 6.2 Implementation This section presents the implementation of the test system and the interaction between its components. The test system is a composite of open source software and new utilities. The Mozilla browser [Moz] provides integrated web and e-mail clients. The Apache proxy server [Apa] provides a transparent web cache for the preloader. The new utilities implement the preloader. To simply Mozilla implementation, the decision was made to build the system for a single platform. FreeBSD was chosen because it has good Perl support for the relays and preloader. It is also the right choice for Apache, which is not available for MacOS and which is difficult to build for Microsoft Windows. With all of the components built for a single platform, the entire system can be run on the user’s machine. This closely replicates an integrated implementation. It allows the user complete control over installation and execution of the system and minimizes the communication latency between the components in the system. The next few figures show the messages exchanged between components. I l l Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 6.3 shows a normal exchange of messages between the browser client and the e-mail and web servers. The messages are numbered with the order in which they are issued. First, the user downloads e-mail: Mozilla sends the e-mail request directly to the e-mail server (1) and receives the text of the message in response (2). When reading the message, the user clicks on a URL within it. Mozilla issues a HTTP GET request to the corresponding web server (3) and receives the web page in response (4). 3: GET /e-mailURL 4: e-mailURL user nachine 1: RETR msgX 2: msgX ozilla server.com httpd server e-mail server Figure 6.3: E-mail and Web Downloads without Intermediaries This conventional system was augmented with an Apache proxy that sits between Mozilla and the web servers and caches documents for the browser. Figure 6.4 shows how that proxy fits into the system. The user machine is enlarged to show the processes within, where it runs both Mozilla and Apache. The e-mail exchange occurs conventionally (1,2). In the augmented system, when the user clicks on the e- mailed URL, the request goes to Apache (3). Because it is a new request, the document is not cached and Apache requests it directly from the web server (4). On 112 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. receiving the response from the web server (5), Apache stores a copy of the document in the cache and sends the document to Mozilla (6). Future requests for this document will be satisfied from Apache’s cache. 3: GET http://server.com/e-mailURL Apache 4: GET /e-mailURL,£=7| 6: ht p://server.com/e-mailURL_____ cache proxy 5: e-mailURL server.com httpd server □□□ Mozilla 1: RETR msgX e-mail server 2: msgX user machine Figure 6.4: E-mail and Web Downloads with Web Proxy Figure 6.5 shows the complete test system, adding the e-mail relay and the preloader on the user’s machine. In this complete system, the e-mail request passes through the e-mail relay (1,2). When the relay receives the text of the message from the server (3), it passes it back to Mozilla (4a), while passing any e-mailed URLs to the preloader (4b). The preloader issues the GET request to the web server (5) and receives the document (6). It formats the document and stores it in the Apache cache (7). When the user clicks on the e-mailed URL, Mozilla requests it from Apache (8). Because the preloader put the document in the cache, Apache returns the document without contacting the web server (9). Any other requests for documents from the 113 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. same server will proceed as above, with Apache requesting them and storing them in its cache before passing them to Mozilla. 8: GET http://server.com/e-mailURL 9: http 7server.com/e-mailURL Mozilla 7: http://server.com/e-ma 4b: http://server.com/e-mailURL / 1: RETR msgX Apache proxy cache preloader 4a: msgX e-mail relay GET /e-mailURL 6: e-mailURL I: RETR msgX server.com httpd server 3: msgX e-mail server user machine Figure 6.5: E-mail Preloading System Although the preloader system increases the activity in the system, requests for e-mailed URLs can be satisfied more quickly than without it. Figure 6.6 shows the timing of the requests without and with preloading. At time t, the user downloads the e-mail message. Once it is received, the user reads it and then clicks on the URL at time /+A. Without the test system, Mozilla must contact the server and download the page (A). With the preloader, the URL is detected when the message passes through the relay and the preloader begins to download the page while the message is being delivered to the e-mail client and read by the user. When the user clicks on the page, the request is satisfied by the Apache cache more quickly than without prefetching (B). 114 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. mail Apache/ mail Mozilla server Mozilla preloader server :ETR msgX RETR msgX t :ETR msgX server.com server.com msgX 1 — GEJ_/emailedURL msgX m sg X emailedURL GET /emailedURL g JemailedtJgL GET /emailedURL A emailedURL with preloader w/o preloader Figure 6.6: Temporal Breakdown of Requests Figure 6.6 ignores opening TCP connections between the processes and the servers. The e-mail relay adds a small delay because 2 connections must be opened, one between Mozilla and the relay, and a second between the relay and the e-mail server. However, this delay is minimized because Mozilla and the relay are running on the same machine; at any rate, the delay is not critical because downloading e-mail messages is not an interactive application. The connection between the preloader and the web server occurs while the user is otherwise occupied and is hidden along with the latency for retrieving the page. The extra TCP connection between the browser and Apache can be ignored. The browser will maintain a persistent connection to Apache and so the delay only occurs when the browser first starts. 115 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Now that the interaction between the components has been described, the rest of this section focuses on the implementation of each piece. Both Mozilla and Apache have been altered from their standard distributions. The e-mail relays and the preloader are new utilities developed for this test system. 6.2.1 Mozilla Mozilla provides the browser and e-mail client and is the main user interface to the system. Shown in Figure 6.7, its primary functions of downloading web pages and e-mail messages have not been altered. To serve the test system, additional logging messages were added to collect data and it was reconfigured to use Apache and the e- mail relays. The logging required modification of the code to track user behavior and record e-mailed URLs. All changes to Mozilla are transparent to the user during normal use of the browser and e-mail client. A p a c h e p r o x y I: GET http://server.conVe-mailURL^ 9: http://server.conVe-mailURL h ttp d s e r v e r cache □□□ Mozilla p r e lo a d c r e - m a il 2: RETR msqX 1: RETR msqX e - m a il re la y 3: msgX 4 : msgX u s e r m a c h in e Figure 6.7: Preloading System Revisited - Mozilla Highlighted Mozilla is a large software project and uses a variety of programming languages and packages. The core engine, which handles network interaction and 116 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. page rendering, is written in C++. Support modules for the core, such as logging, are written in C. Mozilla has a cross-platform user interface language written in JavaScript that provides high-level interface access. Low-level interface implementation is platform-dependent. Alterations were necessary to the core engine, to some support modules, and to the high-level interface code. Mozilla logging recorded user interaction with URLs and e-mail. Mozilla has powerful logging support in the core engine, designed to aid in debugging. When Mozilla is compiled with logging support, logging features can be controlled with environment variables. Tailoring Mozilla to log page request and e-mail information entailed constructing a custom log format, adding log messages throughout the code, and compiling Mozilla with logging support. A few small changes were needed to the log module itself. Log output contained a variety of unnecessary debug information that was removed. In order to correlate items in the Mozilla log to items in logs of other components of the test system, timestamps were added to the log output. The source of a URL request is the user interface action that caused the URL to be retrieved. Recording those events helps determine which requests could be predicted by the browser. In the core engine, interface actions eventually correspond to “LoadURL” commands. In the core engine, all “LoadURL” commands were logged, indicating the URL that was requested. For the most part, this command corresponds to primary page requests, but also includes some secondary frame content pages. 117 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Some requests are the result of user clicks of e-mailed URLs. Logging those events helps characterize e-mailed URLs and the lead time for prefetching them. Mozilla was altered to observe both e-mail protocol and interface actions but also the content of e-mail messages. The POP3 [MR96] and IMAP [Cri96] modules were updated to log message download and read actions. The main messenger module also had code inserted to pull URLs from text-based e-mail messages. Mozilla uses its main web page rendering code for HTML-based e-mail messages, so it was not possible to log URLs in these messages within Mozilla without also logging all internal URLs for all pages displayed. To circumvent this, URLs within e-mail messages were collected by the e-mail relays. While it was possible to distinguish URLs that came from e-mail messages and those that were clicked on in the browser window, it was clear from an early examination of the data that a larger number of URLs were neither e-mailed nor clicked on. Some of these URLs were available to the browser as the “Home” button or other features, but it was not possible to determine the source for all of them. Thus, a second phase of Mozilla development sought to determine the selection of all URLs requested. For the undetermined URLs, the main goal was to distinguish outside URLs that were hand-typed or pasted into the browser from those available as bookmarks, from the history menu, or from other configurable navigation buttons. This information can only come from the user interface code. Mozilla’s user interface project has developed a powerful and flexible interface system that is isolated from the 118 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. core engine of the browser. It allows the interface to be altered without altering the main system. Unfortunately, this isolation means that there is no logging support. Attempts to add variables to identify interface elements were unsuccessful. In the end, the URL itself was overloaded with this information so that it could be passed to the core engine for logging. The URL overloading required additional support in other parts of the core engine to hide the additional information from validity tests executed before the URL is requested. The e-mail modules were altered to log each message as it is downloaded. Mozilla supports both the POP3 and IMAP protocols and users choose which protocol they use with their e-mail accounts. Mozilla treats e-mail messages like web pages for the purpose of rendering them, so LoadURL commands appear each time a message is read. In the POP3 protocol, messages are downloaded and stored on the client machine. Unfortunately, it was not possible to correlate message downloads with message reads for POP3 because Mozilla uses a different set of message identifiers for these two functions. In the IMAP protocol, messages are stored on the remote server and downloaded when they are read. Mozilla uses a single message identifier for both download and read, so these are correlated. It is possible to configure Mozilla for disconnected operation in which IMAP behaves more like POP3, storing messages locally, but test users did not do this. As mentioned above, only text-based e-mail message URLs were logged by Mozilla. Setting Mozilla to use Apache and the e-mail relays required some additional configuration by the users. These components were started as part of the Mozilla 119 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. startup script. Within this script, an e-mail relay had to be configured for each e-mail account. This script was also configured to set the environment variables for logging. Within Mozilla, e-mail accounts were set to access a relay in lieu of the desired mail server. To support Apache, local Mozilla caching was disabled and Mozilla was configured to use the local Apache installation as a proxy server. Thus, all web requests were sent through Apache. This forced the browser to rely on the proxy for all caching. Although the number of changes to the Mozilla code is small, Mozilla represented the biggest challenge to the development of the test system. The Mozilla Project is a large effort that had not released a completed product by the end of test system development in January 2002. The very large code base changed frequently (every 3-4 weeks) and substantially (major sections or coding formalisms were rewritten in each version). It was necessary to keep current with the development code in order to provide the best services and fewest bugs to the test users and to take advantage of the development tools available. Development of the system began with Mozilla version 0.9.4 and continued through 0.9.9. Modified distributions of versions 0.9.7, 0.9.8, and 0.9.9 were used to collect data. 6.2.2 Apache Although the test system collected customized logs from Apache, this data was redundant to that collected by Mozilla. The proxy was needed primarily for preloader support. By default, Apache is built as a primary web server, without proxy caching support. To provide the cache, Apache was built with the proxy features. Figure 6.8 120 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. shows how Apache handles requests between the browser and the web servers, including a cache that receives documents from the preloader. 9: http://server.conVe-mailURl Apache proxy cache □□□ H 7: http://server.conVe-mailURU p r e lo a d e r 4 : http://server.com/e-mailURL' 1: RETR msqX e - m a il r e la y 5: GET /e-mailURL s e rv e r .c o m h ttp d s e r v e r e - m a il s e rv e r u s e r m a c h in e Figure 6.8: Preloading System Revisited - Apache Highlighted Apache was chosen for the cache because the proxy does not store a cache lookup table in memory, but instead maintains the cache solely in the file system. This allows the preloader to insert files by writing into the appropriate directory with the appropriate name. To provide quick access, files are named with an MD5 hash [Riv92] of the URL. Checksum strings are inserted at the top of cached files based on the access and expire times of the files. The functions that create filenames and the checksum string were extracted from the proxy code into small utilities that provide this information. The Apache makefiles were updated to build and install these utilities so they were available to the preloader. The Apache code base, written in C, is mature and lean. Version 1.3.22 was distributed with the preloader. Light development continues on Apache v 1 .x, but any future changes should not interfere with the use of the preloader. During development of this system, Apache v2.0 was available and under development but lacked mature 121 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. caching features. When completed, if the cache management features have not changed significantly, it should be trivial to substitute it for earlier versions of the proxy. 6.2.3 E-mail Relays The e-mail relays log the transfer of e-mail messages between client and server and harvest e-mailed URLs for the preloader. They were initially conceived as a packet sniffer for the e-mail stream, but it quickly became clear that a more sophisticated URL harvester was needed that understood the e-mail protocols. Written in Perl, separate relays handle POP3 and IMAP protocols. They are configured one per e-mail account. The relays log details about e-mailed URLs such as the number of URLs per e-mail message and the placement of those URLs within the message. The relays are configured and launched by the Mozilla startup script. On installation, the user must edit this script providing the target server for each relay and the local port to listen to for connections from the e-mail client. The e-mail client must be configured to send all e-mail commands to this port. Aside from differences owing to the function of their respective protocols, the relays share the same basic operation, as shown in Figure 6.9. Mozilla sends all e- mail commands directly to the relay that in turn sends them to the mail server. Responses from the mail server are sent to the relay. The relay examines e-mail messages as they pass through, forwarding the message back to Mozilla and sending URLs to the preloader. Key actions such as message download and URLs are logged. Protocol specific accommodations are discussed in the next two subsections. 122 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. A p a c h e p r o x y i: GET htto/Zserver.com /e-rrailU RL^ 9: htlp://server.corrVe-mailURL h ttp d s e r v e r cache □□□ M o z illa p r e lo a d e r c - m a il 2: RETR msqX e-mail relay 3: msgX 4 : msgX u s e r m a c h in e Figure 6.9: Preloading System Revisited - E-mail Relay Highlighted 6.2.3.1 POP3 relay In the POP3 protocol, messages are downloaded to the client machine in batches. The client makes discrete sequential connections to the mail server; interaction with the server is strictly client-driven. The POP3 relay listens for new connections from the client and opens connections to the mail server as needed. The relay must examine the command stream from the client to determine when e-mail messages are transferred and to determine when to close the connection to the server. Because e-mail messages are transferred independently from requests for unique identifiers and the size of the message, the relay had to issue additional commands to the server to get this information for the log. Figure 6.10 presents a simplified view of the POP3 relay code. 123 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. pop3relay.pl: # connect to pop server Sserver_sock = new Socket("$popserver:110"); while ($quit == 0) { # get client command $client_buf = read_sock($client_sock); if (matches($client_buf, "RETR")) { # if RETR, get additional data $retr = 1; $client_buf = substitute("RETR","UIDL"); print $server_sock $client_buf; $uidl_str = read_sock($server_sock); $client_buf = substitute("UIDL","RETR"); print $server_sock $client_buf; } if (matches($client_buf, "QUIT")) ( # if quit, setup to close $quit = 1; } # pass command to server print $server_sock $client_buf; # get server response $server_buf = read_sock($server_sock); if (Sretr == 1) { # if e-mail message, get URLs 0URLs array = parse_urls($serv_buf); foreach $url (@URLs_array) { print LOG "$now $uidl_str $url\n"; spawn_child; if (child_process) { system("preloader.pi $url"); } } Sretr = 0; } # pass response to client print $client_sock $server_buf; # quit gracefully if needed if ($quit == 1) { close $client_sock; close $server_sock; ) Figure 6.10: POP3 Relay Pseudocode Figure 6.11 presents a simplified view of the parse_urls() function that is shared by both the POP3 and IMAP relays to find URLs in e-mail messages. The implemented function is more complex than is presented here and can parse multiple URLs on a single line as well as URLs that span lines. The function parses in a 124 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. greedy fashion, starting with either “http://” or “www.” and continuing until it encounters white space or an invalid URL character, as determined by the URI standard [BFM98]. The function can detect “SRC” URLs in HTML-based e-mail messages, that indicate in-line images or applets, and logs those as well. The e-mail relays do not pass SRC URLs to the preloader. parse_urls ($buf) { @lines_array = split ("\n", Sbuf); foreach $line (@lines_array) { if ((matches($line, "http://")) or (matches($line, "www.")) ( $new_url = extract_url($line); push $new_url @URLs_array; } } return @URLs_array; Figure 6.11: parseurls Pseudocode 6.2.3.2 IMAP relay In the IMAP protocol, e-mail messages and folders are stored on the server and transferred to the client as requested. The client opens several persistent connections to the server and communication may originate from either party. As a result, the IMAP relay forks multiple processes to handle each connection. Each process is fully bi-directional and forks listeners for both the client and the server. Communication between the client and server is line-oriented. The end of an e-mail message is signified with a line containing a single “)”. IMAP messages are identified with a mailbox ID and a mailbox index number, or UID. Commands from the client set and change the current mailbox. All message- related commands contain only the index number. Mailbox IDs and UIDs are logged 125 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. as they appear. All log lines are tagged with the process ID of the parent process (corresponding to the connection “stream”) to reconcile this information and create logs with complete message IDs during post-processing. if (parent_process){ # Mozilla->IMAP server while ($client_buf = read_sock($client_sock)) { if (matches($client_buf, "select") { # log box ID info @command_array = split(' $client_buf); $boxID = $command_array[length($command_array)]; print LOG ”5now, $streampid BOX $boxID\n"; } # pass command to server print $server_sock $client_buf; ) } else { # IMAP server -> Mozilla while ($server_buf = read_sock($server_sock)) { if (matches($server_buf, "fetch")) { # if e-mail message, get log info Sfetching = 1; %msg_info_hash = split ( ' $server_buf); $uidl = $msg_info_hash{"(UID"}; } if (matches($server_buf, "")")) { # detect end of e-mail message $ fetching = 0; } if ($fetching) { # retrieve e-mail message @URLs_array = parse_urls($server_buf); foreach $url (@URLs_array) { print LOG "Snow $streampid URL $uidl $url\n"; spawn_child(); if (child_process) { system("preloader.pi $url"); } # pass response to client print $client_sock $server_buf; } Figure 6.12: imaprelay.pl Pseudocode Figure 6.12 presents a simplified view of the IMAP relay code. Details concerning socket management and opening and closing connections are omitted. 126 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Socket listeners are forked off from the main “stream” and use the ID of that process in log files. The relay uses the same parse_urls() function as the POP3 relay. 6.2.4 Preloader The preloader is written in Perl and is a stand-alone utility that downloads web pages and stores them in the Apache cache, as seen in Figure 6.13. It is called by the e-mail relays when they find URLs in e-mail messages. The preloader does no URL screening and attempts to download any URL it is given. As a result, the relays must screen e-mailed URLs and avoid preloading those that may have side effects. Once the preloader has downloaded the given URL, it formats the file with utilities extracted from the Apache code and places it in the Apache cache. A p a c h e p r o x y _8|iG ETht^W sgw ricofTVe^rai|UR^^ 9: hltp;//server.corrVe-mailURL h ttp d s e r v e r cache M o z illa 7: http://server.com/e-mailURl preloader e -m a il 2: RETR msqX e - m a il re la y 4 : msgX 3: msgX u s e r m a c h in e Figure 6.13: Preloading System Revisited - Preloader Highlighted Figure 6.14 presents an overview of the preloader code. Perl has native support for HTTP requests, so this module is used to download the file. If the document request is successful, the filename is determined using the “hash” utility extracted from Apache. The file is opened in the Apache cache directory and the 127 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. document is printed along with the response headers and Apache date strings provided by the “checksum” utility. preloader.pi: $url = $ARGV[0]; $response = new HTTP::request("GET", $url); if ($response->status == 200) { $cachefile = system("hash $url"); open (OUT, "$cachefile"); $checksum = system("checksum $response->dates"); print OUT $checksum; print OUT $response->base_url; print OUT $response->headers; print OUT $response->content; close OUT; } Figure 6.14: Preloader Pseudocode 6.3 Installation and Configuration The test system was distributed as an all-inclusive Unix tar archive. The archive included the pre-compiled Mozilla distribution, the Apache code with build instructions, and the e-mail relay and preloader scripts. The user unpacked this archive in their desired location. Once the archive was unpacked, some initial setup was required. The Apache proxy compiles with path information, so the user had to build the proxy in the desired location. The user also had to edit the Mozilla startup script to configure relays for each of their e-mail accounts and set an environment variable with the location of the Apache proxy. This variable provided the location of the cache utilities for the preloader. The user starts Mozilla with the startup script. On the first run, Mozilla imports user preferences from Netscape [Net] if these exist. The user must 128 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. (re)conflgure e-mail accounts to use the e-mail relays and configure the browser to use Apache as a web proxy. They must also disable browser caching. Once these initial settings are made, no other configuration is needed. The user starts Mozilla with the startup script and interacts with it normally. No other accommodations are needed. 6.4 Summary This chapter described the implementation of the test system. It consists of modified versions of Mozilla and Apache and new Perl utilities. Mozilla was modified to log web requests and e-mail messages. Apache provides an accessible cache for the preloader and utilities extracted from Apache allow the creation of valid cache files. The new e-mail relays harvest URLs from e-mail messages and pass them to the new preloader. The final design for the test system was chosen over several other candidates. In addition to providing the necessary data, candidate systems were judged on ease of implementation and ease of use. A detailed presentation of the design goals for the system and a comparison of the other candidates can be found in Appendix A. Test users installed and configured the test system and used it as their exclusive web and e-mail client for several months. Due to concerns about privacy- related side effects, no e-mailed URLs were actually preloaded. The data from their sessions is presented in the next chapter, along with discussion about these potential side effects. 129 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7 E-mail-Web Analysis E-mail-Web prediction is a demonstration of cross-domain prediction introduced in Chapter 3. Chapter 6 presented the implementation of the E-mail-Web test system. It is a composite system using altered off-the-shelf components together with new Perl daemons. This chapter presents the results from a six-month user test of the system. The results indicate that 95% of page requests can be predicted within the browser, either through request history, bookmark lists, or examination of current page syntax, representing one-domain prediction. O f the 5% of page requests that could not be predicted within one domain, about a 25% came from e-mail messages. Prefetching all e-mailed URLs would increase page requests by up to 65%, and reduce the external misses of the browser by up to 25%. This chapter presents the results in detail and discusses their implications. Section 7.1 will present the data and results. Section 7.2 will discuss implications of cross-domain prediction. Section 7.3 summarizes this chapter. 7.1 Results Six test subjects used the test system as their primary web and e-mail client for six months. After the first three months, initial data revealed that the first implementation in Mozilla required some adjustments to more precisely indicate the sources for each type of page request. After these changes were made, four of the users continued with the updated system for two months. Although the initial data 130 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. could not be used to determine specific request sources, it was used to characterize URLs embedded in e-mail messages. The size of the user pool was restricted due to privacy and security concerns. It was originally intended that URLs logged by this system would be hashed to preserve user privacy and anonymity of the users. However, this was not possible because initial tests revealed that URLs were transformed between their appearance in e-mail messages and their use by the browser such that too much data was lost through hashing. Examining unaltered e-mailed URLs provided new insights about the way that e-mailed URLs are transformed by the browser and also used to convey information about the recipient. This section presents core results from the user trials. Section 7.1.1 determines the frequency and cacheability of unpredicted URLs. They represent opportunities for cross-domain prediction, as presented in Chapter 3. Section 7.1.2 characterizes URLs embedded in e-mail messages, a major source for unpredicted URLs. Section 7.1.3 considers the impact of prefetching e-mailed URLs. 7.1.1 Request Sources The source of browser requests determ ines whether they can be predicted by the browser or other means. The source of a request is the manner in which it was selected, such as users clicking on a link in the current page, users choosing one of the brow ser’s navigational features, or im ported by an outside application. Requests from the first two sources can be predicted within the browser; requests from outside 131 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. applications cannot. The figures in this section represent experiences of four users during two months of using the test system. Figure 5.7 presents the average components of request sources. The categories, “Click”, “History”, “Bookmarks”, and “Miscellaneous” represent requests that the browser can predict. Requests in the other two categories, “No Prediction” and “E-mail”, cannot be predicted by the browser; these are projected into their own chart, and they represent opportunities for improved prediction through cross-domain cooperation. E-mailed URLs make up about a quarter of the non-predicted requests. The remaining requests come from other applications or are typed into the browser. Other applications include word processors and PDF readers and were not available on the test operating system. 37% CIZD History nmn Bookmarks v m m Miscellaneous ^ ^ N o Prediction EZD E-mail Figure 7.1: URL Source Breakdown 132 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The largest source for requests is clicks in the current page. The browser can predict requests by parsing each page as it is loaded. The next biggest source is the set grouped together as “History”. These are repeated requests explicitly generated by clicking the “Back” or “Reload” buttons or those that come from HTML “refresh” directives. The browser can also predict these requests. “Back” requests can be satisfied by the cache; “Reload” and “refresh” requests may update pages and are candidates for prefetching. The set of “History” requests does not include repeated requests generated by repeat clicking or other means and are not indicative of URL reuse. In these logs, repeated (and non-dynamic) requests account for 30-50% of each set of user requests, matching results found elsewhere [Gla94, ASA95, CDF98], The remaining predictable categories are “Bookmarks” and “Miscellaneous”. Bookmark lists contain frequently visited URLs. The browser can keep these pages current in the cache, which may also satisfy requests that have other sources. The “Miscellaneous” category contains requests that come from configurable browser buttons, such as “Home” or “Search”. One user had a large number of these because his “Home” page is a list of frequently accessed sites. Unlike bookmarks, this list is accessible from any browser, but may have different implications for prefetching. Non-predicted requests do not fit the categories above. They are typed into the browser or imported from other applications, such as e-mail clients or word processors. In this system, requests from e-mail can be tracked because an e-mail client is part of the browser application. However, tracking requests from other software was not possible with the test system because these programs do not interact 133 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. with the browser in FreeBSD like they do in Windows or MacOS. In these other operating systems, further work is needed to determine how many non-predicted URLs are available to the system. For a predicted URL to be useful, either the prediction must coincide with use or the URL must be cacheable. Because request timing is difficult to predict, this work focuses on cacheable URLs. In the following figures, cacheable URLs are “static” URLs - those without search keys in the URL1 . Determining cacheability based solely on the URL is imperfect for several reasons. Some servers incorrectly represent the characteristics of their pages, either through sloppy configuration or purposeful misdirection. Headers alone cannot predict whether a page is likely to change. Some URLs with search keys may always return the same content and should be cached. Despite these drawbacks, URL-based cacheability approximates the behavior of the browser and supports the spirit of content reuse. Figure 7.2 presents non-predicted requests and the cacheability of those requests that come from e-mail messages. URLs requested from e-mail are more likely to be static and are good candidates for successful prefetching. ' Microsoft’s Active Server Pages [Mic] do not require keys, but are generated as needed by the server and are also non-cacheable. 134 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. ESS1 Non-Predicted C viyT il E-mail (Static) E S I E-mail (Dynamic) Figure 7.2: Non-Predicted Requests from E-mailed URLs The frequency of each non-predicted URL can determine if these requests might be satisfied in other ways. Figure 7.3 shows the frequency of non-predicted requests split into static and dynamic requests. The figure presents the requests for one user, but is representative of the results for each user. Most non-predicted URLs are requested a single time. A handful of non-predicted URLs have multiple requests, with static requests repeated slightly more than dynamic requests. Some of these repeated requests might be satisfied by the cache. A very small number of URLs were requested many times (more than 20). The large number of requests for URLs in this last set indicates that they should be added to the user’s bookmarks. 135 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 100 40 a Static Dynamic 10 20 1 Number of Requests Figure 7.3: Cumulative Frequency of Non-Predicted URLs 7.1.2 E-mailed URLs The previous section considered only those e-mailed URLs that were requested by the user. This section looks at all e-mailed URLs received by each user, the superset those URLs considered above. Data in this section was generated by the full test group of six users over six months. E-mailed URLs were collected by e-mail relays that parsed each message as it passed through. The relays found two types of embedded URLs: sequential URLs that represent future web requests the user might make, and parallel URLs that represent images and applets to be displayed together with the e-mail message. These latter URLs are called “SRC” URLs and could be prefetched to display with the e-mail message. Figure 7.4 shows the frequency of e-mail messages with URLs or SRC URLs for each test user. About 50% of all e-mail messages contained at least one URL. On average, fewer than 10% of e-mail messages contain images or applets. 136 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 100 S. 90 ■ Msgs w/URLs ■ Msgs w/SRCs User 1 User 2 User 3 User 4 User 5 User 6 Figure 7.4: Frequency of URLs in Received E-mail Messages Figure 7.5 shows the proportions of e-mailed URLs that are static or dynamic, according to the definitions used in the previous section. About half of e-mailed URLs are static and are good candidates for prefetching. These URLs are likely not to have side effects such as enrolling in a service or unsubscribing from a mailing list. From Figure 7.2, static URLs are more likely to be requested by the user. E23 Static E w i Dynamic Figure 7.5: Type of URLs Received in E-mail Messages 137 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 7.6 shows the types of SRC URLs that appear in e-mail messages. As expected, most of these URLs are images2 that enhance the message. A surprising result of this analysis is that some SRC URLs have search keys attached to them, implying that requesting the image causes side effects. As many as 20% of SRC URLs that arrive in e-mail messages have these keys; they are listed as dynamic because the presence of the key prevents caching. According to the automated analysis, a small number of SRC URLs were neither images nor dynamic URLs. A visual inspection suggests that they may also be dynamic. 18% E Z 3 Dynamic Other Figure 7.6: Type of SRC URLs Received in E-mail Messages Some search keys attached to dynamic images contain the recipient’s e-mail address in plain text; others are encoded with unknown information. Images with names like “ lxl.gif?<key>” suggest the recipient may not even be aware the image is there. There are concerns that the act of requesting an embedded URL validates an e- mail address, creating a target for unwanted e-mail messages. This data reveals that it is not necessary to request a URL (“unsubscribe” or otherwise) to validate an e-mail 1 Images include URLs ending with “.g if’, “.jpg”, and “.jpeg”. 138 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. address. For users with graphical e-mail clients, the act of reading e-mail messages exposes information including the user’s e-mail address and the source of the URL. The next few figures quantify the number of URLs embedded in each e-mail message. Figure 7.7 shows the number of unique URLs per message for each user. Most messages contain few URLs, but some messages contain many URLs. The most extreme case was a message containing 323 unique URLs (not shown in the figure). On average, 90% of e-mail messages contain fewer than five URLs. 100 90 d 80 tfl g, 70 fl3 « 60 © * 50 0 1 40 1 30 C l 2 20 Q_ 10 0 0 10 20 30 40 50 Number of Unique URLs per Message Figure 7.7: Cumulative Frequency of Unique URLs in Received E-mail Messages Figure 7.8 shows the number of SRC URLs embedded in each e-mail message. Very few messages have embedded images or applets. Of those messages that do have SRC URLs, most have at least two. / s ' / ------User 1 ------User 2 User 3 — — User 4 - ------User 6 139 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 100 !=•■ l ............ - ............................................................................ 90-----^ ------------------------------------------------------------------------------- b 8 0 -— -------------------------------------------------------------------------------------------- 0 ) o > 7 0 ---------- . ---------------------------------------------------------------------------------------- 03 j j j 6 0 ---------- - * 5 0 User 1 _ o ----- User 2 c 4 0 --- ------------------------------------------------------------------ o User 3 2 30 user 4 8 20 User 5 - o. 1 0 |— _____________________________________________ ____ User6 _ 0 J --------, ----r — r— , ----, ----_ ----, ----, ----, ----, ----, ----, ----, ----, r— 0 5 10 15 20 Number of Unique SRCs per Message F igu re 7.8: C u m u lative F req u en cy o f U n iq u e S R C s in R eceived E -m ail M essages 7.1.3 E-mail URL Prefetching This section examines the burden of prefetching URLs that appear in e-mail messages. It considers both the amount of time available for prefetching these URLs and the impact prefetching has compared to the total request traffic generated by each user. Figure 7.9 presents intervals between downloading e-mail message headers and reading the corresponding message. In the test system, this correlation was only possible for users that download their e-mail with the IMAP protocol, excluding User 6. By default, IMAP transfers new message headers when the server is contacted and transfers the body of an e-mail message when the user wishes to read it. If URL prefetching is used, arrival of the message header would trigger the prefetching. For most users, more than half of their messages were read more than a minute after the header was downloaded. This provides ample time for prefetching URLs. Messages 140 — s / ------User 1 ----- User 2 User 3 ----- User 4 UoUl o ------User 6 . Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. read less than 24 hours after receipt are likely to be valid in the cache if prefetched. The shaded area in the figure represents this valid range. 100 o > User 1 User 2 User 3 User 4 User 5 40 105 10 1 100 ~1.5min ~15min ~3hrs ~1day Seconds between Download and Read (log) Figure 7.9: Intervals between Downloading and Reading E-mail Messages Figure 7.10 compares the number of e-mailed URLs to the total number of page requests made by each user. Note that the number of page requests does not include requests for embedded objects and is much smaller than the total number of web requests made by each user. For test users, e-mailed URLs would increase page requests by as much as 65%, but on average much less. Overall, this increase is small compared to the number of requests that might be made if browser-based prefetching was employed as well. This analysis ignores the size of each request, but there is no reason to suspect that e-mailed URLs would require fdes that were substantially larger or smaller than other page requests. 141 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. User 1 User 2 User 3 User 4 User 5 User 6 Figure 7.10: Burden of E-mailed URLs on Total Requests Because of the large number of e-mailed URLs, some sort of filter should be used to reduce the amount of prefetching. This filter represents yet another prediction in the system. Design of suitable filters is beyond the scope of this work; it is probably better suited to machine learning or artificial intelligence. One suggestion is to limit prefetched URLs to those that come from well-known senders, perhaps correspondents that appear in the user’s address book. Another suggestion is to avoid prefetching frequently recurring URLs, in the belief that they are likely to appear in a sender’s signature or as maintenance URLs for a mailing list or other service. Another way to narrow the pool of URLs to prefetch is to try to predict which e-mail messages a user will actually read. Many users employ filters to discard unwanted messages on arrival and ignore others. Figure 7.11 examines URLs in messages that users actually read. The height of the column is the percentage of all read messages containing URLs. The top portion is the percentage of those messages 142 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. that generated a page request. Of these messages, on average about half contain URLs. O f the messages with URLs, about 5% generated a page request. —100 ■ Clicked ■ With URLs User 1 User 2 User 3 User 4 User 5 Figure 7.11: Proportion of Messages Read containing URLs, Clicked URLs 7.2 Discussion This section considers the implications of E-mail-Web prediction. Cross domain prediction is intended to augment full-scale web prefetching that non- invasively uses idle resources. The first subsection focuses solely on single-domain web prefetching. The second subsection will explore cross-domain prediction not only in the web, but also in the DNS as described in Chapter 5. 7.2.1 Web Prefetching As discussed in Chapter 1, distance-based latency between client and server can only be resolved by moving content closer to clients. This can be achieved either by physical relocation of the source (through replication or proxy caching) or by 143 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. speculatively transferring content to the client machine. Relocation can reduce delays but cannot remove all delays. Successful prefetching can remove all delays, but technical challenges have directed practical efforts toward replication and relocation. Challenges for prefetching include the large number of uncacheable web documents that cannot be prefetched and the additional network traffic and server load that prefetching causes. Web caching is defeated by dynamic content and by servers that disallow it to collect accounting information. Prefetching pages increases request traffic, effort that is wasted if prefetched items are not used. The additional effort required to transfer them can interfere with non-speculative traffic. These roadblocks are not insurmountable. Many documents that cannot be cached have content that does not change. Separating content transfer from accounting may encourage servers to support caching. Servers would allow their pages to be cached, trusting the cache to transmit notifications when the cached pages are viewed. There are also solutions for prefetching dynamic pages, perhaps by moving content generation to clients. Networks and servers are provisioned for peak loads and most have idle cycles even during peak periods. Using techniques developed by the LSAM project [TH98], speculative requests can be managed to consume only these cycles and not interfere with non-speculative traffic. These solutions will be described in more detail later in this section. 144 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7.2.1.1 Benefits The primary benefit of prefetching is latency reduction for users. Because requested pages are already on the client machine, web browsers can respond nearly immediately when users click for new pages. Prefetching also provides benefits to content providers and allows new protocol optimizations. Content providers that support caching and prefetching will appear to respond faster than those that do not. Users that are happy with server responsiveness will prefer that server in the future, especially when they have a choice of content providers, such as news services that supply Associated Press or Reuters feeds. Further, by using server idle cycles, content providers maximize the utility of their machines, using capacity that would otherwise be wasted. Wide support for prefetching will allow other optimizations. Servers can take advantage of the traffic reduction benefits of multicast for distributing speculative pages to a large group of users. Aggregate page requests and responses are also possible, reducing per-packet overheads associated with individual requests. Though aggregation is currently possible without prefetching, it is not widely used and requires a set of requests to one server. Speculative requests provide new opportunities for aggregation because they are more likely to come in batches. 7.2.1.2 Prerequisites Prefetching creates new requests that will require resources at the client, the server, and in the network. Without new support for background requests using idle 145 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. capacity, prefetching requests will compete with non-speculative traffic, increasing web delays and disrupting other applications. Most networks and servers are provisioned to handle peak loads. During lighter loads, unused processing capacity cannot be stored for future use and is wasted. The LSAM project developed mechanisms for background processing using these idle cycles and capacity [TH98]. In processors, background processes have much lower priorities than foreground processes and are preempted when foreground processes need resources. In the network, routers would handle background packets only when no foreground packets are available. Background packets should also be preempted if foreground packets arrive. If all prefetching requests are issued as background requests, they only consume resources that would otherwise be idle and do not interfere with non-speculative requests. A fair implementation of prefetching requires that all prefetch requests are handled as background (competing only with other background requests). Clients must have surplus processing capacity to issue prefetching requests and storage necessary to store corresponding pages. These requests should not compete with primary page requests nor should they compete with other applications on the machine. Prefetching must be a non-critical optimization that defers to other primary applications. This is possible with the backgrounding support described above together with existing process priority support. Extra storage space for prefetched pages should be available. Disk space is usually plentiful on client machines as disk drives become increasingly less expensive. 146 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Web servers must have sufficient capacity to handle increased request traffic. Most web servers are configured to handle peak request loads and have ample excess capacity under average loads. Processing cycles cannot be saved and excess capacity is wasted. Increased web delays will occur if speculative requests compete with non- speculative requests. Thus, servers must be able to recognize speculative requests and refuse them during peak loads or defer them to idle periods. The network must be able to handle increased traffic due to prefetching. This new traffic will compete with non-speculative web requests and with other applications, increasing delays for all. Like web servers, networks also experience varying loads and unused capacity is wasted. Issuing prefetch requests in the background allows this excess capacity to be used and avoids interfering with other applications. 7.2.1.3 Implementation Issues At a minimum, web prefetching requires changes only to the client software where the actual prefetching will take place. However, this greedy implementation is inconsiderate to other web clients and network applications. Prefetch-aware web servers can handle speculative requests in the background, minimizing impact on other users. While prefetching does not require changing the HTTP protocol, alterations to HTTP allow efficient implementation. Finally, the effects on other network applications can be minimized with changes to network and transport protocols to support background packet transmission as described above. 147 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7.2.1.3.1 Client Changes A prefetching engine can be implemented as an independent proxy, but may be best suited to the browser where it has access to user behavior and other sources of prefetching information, such as bookmarks. Adding prefetching to the browser will increase application complexity. The browser must parse web pages for prefetch URLs and may need to exploit other predictive structure. Prefetched pages will require increased cache storage as well as more complex cache management. Separate algorithms may be needed to manage the reuse and prefetch caches. If servers support post-transfer accounting, the browser must collect page request information and periodically transmit it. The browser will also need changes to support background processing and packet transmission. Prefetching filters can increase request accuracy through selective requests or by prioritizing how requests are issued. These filters may perform security checks on candidate URLs to avoid requesting those with side effects. Filters should learn from user request patterns and they may be configurable. A user may specify a “current” list of URLs that must always be available. 7.2.1.3.2 Server Changes Prefetching support in the server allows it to manage increased request load. If speculative requests are clearly identified, the server can handle them in idle cycles and will require additional complexity for background support. Further optimizations, such as multicasting speculative responses [TH98], will also increase complexity. 148 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. To increase prefetching opportunities, the content provider should increase object cacheability. The first step is accurate configuration of object lifetimes. More useful changes include indicating whether a URL has side effects, using frames or other templates to accurately divide static and dynamic content, and using JavaScript or other client-side actions to push dynamic generation to the client. Content providers can add increased structure to objects by listing keywords and adding prefetch URL lists. Finally, if the content provider supports prefetching with post-transfer accounting, the server must be altered to collect it. Accounting information may improve prefetching because it allows the server to differentiate documents that are popular from those that are highly predicted. The server can then provide the client with refined prefetching hints. The Mozilla browser is starting to support these hints using optional HTML <link> tags [Moz], The browser scans all pages for these tags and downloads any corresponding URLs. 7.2.1.3.3 Protocol Changes Although prefetching is possible without HTTP support, some of the changes suggested above may be best implemented in the protocol. New request types are required to indicate speculative requests and to provide post-transfer accounting information. A GIVE request could indicate a speculative request that the server can choose to ignore [TH98, Low]. A GOT request could indicate post-transfer accounting. More aggressive optimizations such as aggregated requests or multicast responses would require further protocol changes or new protocols altogether. 149 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7.2.1.4 Effects of Full Implementation Prefetching will increase the requests that must be handled by the network and server. Issuing speculative requests as background requests can reduce this burden. However, increased dependence on servers to support caching and on clients to supply post-transfer accounting information opens new possibilities for abuse. As discussed above, prefetching will increase network traffic and server load. Implementations that use backgrounding will minimize the impact of this additional traffic. Background traffic will improve the efficiency of the network and servers by consuming cycles that would not otherwise be used. Because networks and servers are provisioned to handle peak loads, speculative requests will not be permanently starved. Further, requests satisfied by prefetching replace non-speculative requests that contribute the peak load. Prefetching may reduce peak capacity required by servers. Sometimes idle capacity may not be sufficient to handle all prefetching requests. These cases fail-over to non-speculative requests if the user requests the document. Pricing structures for leased servers and network lines may need to change. Increased traffic translates to increased costs for customers that are charged per bit. Flat fee plans often charge for average use and these will increase as well. Cost increases mostly affect content providers who will tolerate increases if they translate to increased customer satisfaction and loyalty. Using idle resources to satisfy speculative requests creates two classes of request traffic. A client that prefetches with foreground requests will compete with 150 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. other foreground traffic increasing network delays. In cases where idle cycles are not sufficient to handle all prefetch traffic, this may improve performance slightly, but at the cost of increasing delays for all non-speculative requests the user makes. A server can use the volume of requests and the lack of speculative requests to detect a misbehaving client. It can correct the behavior by responding to all requests with background responses. A client may also abuse speculation by neglecting to submit post-transfer accounting information. This reduces the follow-up work required of the client and may also provide greater user privacy by masking their activity. A server can detect this by correlating speculative requests with accounting responses. It can correct the behavior by refusing all speculative requests from a misbehaving client. User privacy concerns may be addressed with the use of proxies to handle accounting information. Servers may also abuse prefetching by misrepresenting the side effects of their pages. By doing so, they can artificially increase the amount of traffic or customers they can claim. This behavior should be self-correcting because exploiting prefetching to enroll customers in a service will generate bad press and could have legal repercussions. 7.2.1.5 Remaining Issues Prefetching reduces latency for items that can be cached, but there is still a large set of objects that cannot be cached. These include dynamically generated pages and URLs with side effects. As suggested above, dynamic content may be generated at the client by pushing code and input data. Side effects, such as subscription or 151 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. purchasing, are more difficult to address because they may rely on fluctuating data, but partial solutions are possible. Borrowing techniques from branch prediction, a server may supply all responses to a given query to transfer the main content and rely on an “at-the- moment” request to determine which item is displayed to the user [Tou94]. Other inventory or approval based transactions may be anticipated by temporarily reserving resources. For inventory-dependent transactions, a small quantity of items may be reserved for the customer. If the customer completes a purchase for fewer than the reserved quantity, a purchase confirmation is sent to the server to lock in the items. Lack of a confirmation will release them. Similarly, if the merchant has a customer’s credit card information, it can pre-authorize the predicted sale amount and commit the purchase later. This type of transaction is already conducted by rental car companies and even by shopping mall retailers who settle accounts at the end of the day. Unfortunately, even when objects are cacheable, not every application has the structure needed to prefetch. Sometimes the structure is hidden and can be revealed by changing the scope of the search. For example, good candidates for prediction may be more evident at servers that observe aggregate request patterns. But, in other cases, no structure can be found. Overall, lack of structure is the motivating problem of this dissertation and the first three chapters address this problem in detail. Cross-domain prediction is the proposed solution and the next section will address additional issues it presents. 152 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7.2.2 Cross-Dom ain Prediction Cross-domain prediction offers similar costs and benefits as single-domain prediction, but increases the number of items that can be prefetched. For some applications, no single-domain prediction is possible and cross-domain prediction introduces potential for prefetching to the application. As before, users experience significantly reduced latency for successfully prefetched items. Content providers will experience an increase in page transfers but if idle-cycle backgrounding is used, wasted cycles will be reduced. And, users will perceive these servers as fast, encouraging customer loyalty. Cross-domain prediction allows new optimizations to applications that previously could not predict. For example, Web-DNS prediction now allows DNS aggregation and multicast distribution of responses. 7.2.2.1 Prerequisites E-mail-Web prediction should be implemented to augment existing web prefetching, so it requires the same support any prefetching would. This includes network and transfer protocol support for background requests. It also includes server and browser support for issuing speculative requests during idle cycles. Finally, it includes optimal document cacheability, including post-transfer accounting. Lack of this assumed support presents the same challenges as faced by single-domain web prefetching, discussed above. This discussion assumes that the browser and e-mail client are located on the same machine. This is not always the case. Some users run one or both clients 153 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. remotely, displaying the interfaces on a local machine. For these users, communication between the two applications to share URLs is more complicated. However, this additional complexity should not hinder the cross-domain prediction. Web-DNS prediction introduces prefetching to the DNS. Like web prefetching, it assumes network and protocol background requests. It presents new requirements for client caches and DNS servers. Chapter 5 showed that cache sizes can triple for speculative DNS records, but this increase is not an undue burden. DNS servers must be able to handle the increase in request traffic, but like web servers, they are provisioned for peak traffic and have excess cycles on average. 7.2.2.2 Implementation Issues E-mail-Web prediction requires changes to e-mail clients and web browsers. It is not necessary to alter e-mail protocols or HTTP beyond any changes discussed above. Web servers only need alterations to support prefetching. Web-DNS prediction requires changes to web browsers. It can be implemented without altering DNS servers or protocols, but may be more efficient if these are changed to support prefetching. 7.2.2.2.1 Client Changes Changes to support E-mail-Web prediction are simple. E-mail clients must be altered to parse e-mail messages for URLs. A small amount of additional complexity is needed in the e-mail client to pass these URLs to the browser. The browser must be altered to accept these new URLs. Some additional URL filters may be necessary to 154 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. determine which senders are good sources for URLs and to allow the user to block URLs from blacklisted senders. For Web-DNS prediction, the local DNS client will need a larger cache and support for background requests. Like any application needing structure, there will be increased complexity to accept or mine structure from another application. In this case, the DNS client must accept speculative domain names from the browser. With cross-domain prediction, cooperating applications must be altered to provide structure to the necessary applications. For Web-DNS prediction, the browser must be altered to harvest predictive server names and to provide them to the DNS client. 7.2.2.2.2 Server Changes E-mail-Web prediction builds on other web prefetching and assumes server support for speculative requests and post-transfer accounting. No additional changes are necessary due to URL requests that come from e-mail messages. Web-DNS prediction creates new DNS predictions. It is possible without direct support in the DNS servers, but may be more efficient if the servers are altered to handle speculative requests differently. Changes include support for speculative request identification and idle-cycle backgrounding. 7.2.2.23 Protocol changes. E-mail-Web prediction builds on other web prefetching and assumes HTTP support for speculative requests, such as background requests and processing, and post-transfer accounting. No additional changes are necessary due to URL requests 155 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. that come from e-mail messages. Although no change is necessary for Web-DNS prediction, a simple change to DNS protocols to indicate speculative requests allows name servers to respond to these requests when idle. 7.2.2.Z Effects of Full Implementation E-mail-Web prediction will increase web request traffic in the network. This increase will be small compared to other web prefetching traffic and efficient use of backgrounding should prevent these requests from interfering with non-speculative requests and other traffic. Because e-mail becomes a source of URLs that will be prefetched, there may be an increase in unsolicited e-mail messages from content providers that wish to force page transfers. Web-DNS prediction will also create new request traffic and server load. Again, proper use of idle capacity should minimize the effect these requests have on primary requests and other applications. 7.2.2A Remaining Issues Web prefetching is only possible for cacheable objects and cross-domain prediction does not improve this. Solutions for dynamically generated pages and for transactions with side effects were discussed above. E-mail-Web prediction introduces a new issue of privacy. It is possible, through object naming, to associate e-mail addresses with URLs. If these URLs are prefetched, information about the user may be exposed even if the user never actually requests the page. However, this same information is exposed for users with HTML enabled e-mail clients that request 156 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. embedded images. In these cases, users who disallow images in e-mail messages may also choose to disallow E-mail-Web prefetching or to delay images until time-of-read. 7.3 Summary This chapter presented results from a six-month multi-user study of E-mail- Web prediction. In addition to demonstrating the benefits of cross-domain prediction, an examination of URLs embedded in e-mail messages raised new issues of personal privacy and e-mail. E-mail-Web prediction can be implemented without changes to external systems, but may work better with support for prefetching. Discussions with potential users revealed fears of security threats associated with prefetching e-mailed URLs. Some of these URLs have side effects and they cannot be easily distinguished from those that will not. Search keys associated with a URL may point to either an intended action, such as purchasing a product or unsubscribing from a list, or they may simply refine the page that will be displayed, such as an article in a web magazine or the product details in an online store. External support for prefetching includes increased document cacheability and idle-cycle backgrounding. Content providers can increase document cacheability by accurately reporting document lifetimes. New solutions for dynamic content may enable caching for frequently changing pages. Idle-cycle backgrounding support in servers and in the network prevents speculative requests from interfering with non- speculative requests and utilizes capacity that would otherwise be wasted. Results from this study show that cross-domain prediction between the browser and e-mail client can increase the number of predictions in the browser and 157 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. reduce user latency. Overall, e-mailed URLs make up a quarter of the requests the browser cannot predict. Over half of these requests are good candidates for prefetching. Doing so increases the number of pages requests by up to 65%. In sum, E-mail-Web prediction would nicely complement other browser-based prefetching and is a successful example of the benefits of cross-domain prediction. 158 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 8 Conclusions Predictions are used in many applications to reduce user-perceived delays and improve resource use. In the web, moving data closer to the user through prediction is key to reducing user-perceived delays, but not all requests can be predicted with current methods. This dissertation presented a new model for representing predictors and developed an extension of the model, cross-domain predictors, that can be used to construct new predictions. With cross-domain prediction, information in one domain is used to make predictions in another domain. Cross-domain prediction was successfully employed in two applications. Chapter 2 introduced the basic model for representing predictions in a single domain. The model highlights the effect a prediction has on the objects in the system, resulting in reuse, extended use, delayed use, or new use. Understanding this effect aids implementing predictive applications. Using the model to represent applications allows comparisons and underlines motivations behind applications employing the same base predictor. This methodical approach to identifying predictors allows all sources to be identified and applied, maximizing the use of prediction in applications. In Chapter 3, the model was extended to develop predictions that involve multiple domains. These cross-domain predictions provide new information to applications, circumventing limitations by providing entirely new predictions or augmenting existing ones. These new predictions may reinforce or improve the accuracy of existing predictors. 159 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The benefits of cross-domain prediction were studied in two applications. Web latency can be reduced by prefetching web pages before they are needed. Although web browsers already contain single-domain predictors, E-mail-Web prediction adds additional predictions previously not possible. Web-DNS prediction can reduce connection setup latency by pre-resolving web server domain names, improving all requests and providing benefit even when the web request itself cannot be prefetched. Approximately 5% of all page requests originate outside the browser. These requests cannot be predicted with conventional means. Cross-domain E-mail-Web prediction can predict some of these requests using URLs embedded in e-mail messages. Results from a 6-month user study show that e-mailed URLs account for 25% of the unpredicted requests. Cross-domain Web-DNS cooperation introduces prediction to DNS caches. An investigation into web connections showed that DNS requests account for up to 50% of the setup costs. Predictions based on URLs embedded in web pages can reduce the DNS miss rate by 15%. Doing so is low cost, requiring less than a threefold increase in the DNS cache size. When attempting to reduce user-perceived latency, predictions are very important. In the web, there are solutions to reduce latency even when documents cannot be cached, but they miss the main point. Completely reducing web latency requires prefetching objects that can be cached. For dynamic objects, the computation 160 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. needs to be moved to the client machine. For static objects, new tracking methods are needed to encourage content providers to support caching. Prediction is key to reducing user-perceived latency and will become more crucial as humans communicate throughout the world and universe. The model developed in this dissertation allows the creation of new predictions through a scientific analysis of the structure available in an application. When useful structure is not available, the extended model provides a way to predict by capitalizing on structure in related applications. Predictors based on this model reduced DNS and web latency and easily transfer to other applications. 161 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 9 Bibliography [ASA95] Abrams, M., Standridge, C. R., Abdulla, G., Williams, S., and Fox, E. A., "Caching Proxies: Limitations and Potentials", in Proceedings of the Fourth International Conference on the WWW, Boston, Massachusetts, December 1995. [Adl99] Adler, S., “The Slashdot Effect, An Analysis of Three Internet Publications”, http://ssadler.phy.bnl.gov/adler/SDE/SlashDotEffect.html (published online only) [Aka] Akamai Technologies, 500 Technology Square, Cambridge, Massachusetts. [Apa] The Apache HTTP Server Project, The Apache Software Foundation, http://www.apache.org. [BDR97] Banga, G., Douglis, F., and Rabinovich, M., “Optimistic Deltas for WWW Latency Reduction”, in Proceedings of the 1997 USENIX Annual Technical Conference, Anaheim, California, January 1997, pp. 289-303. [BFM98] Bemers-Lee, T., Fielding, R., and Mastiner, L., “Uniform Resource Locators (URI): Generic Syntax”, Request for Comments 2396, August 1998. [BCC95] Bestavros, A., Carter, R. L., Crovella, M. E., Cunha, C. R., Heddaya, A., and Mirdad, S. A., “Application-Level Document Caching in the Internet”, in Proceedings of the Second International Workshop on Services in Distributed and Networked Environments (SDNE '95), Whistler, British Columbia, June 1995,p p .166-173. [Bes96] Bestavros, A., "Speculative Data Dissemination and Service to Reduce Server Load, Network Traffic and Service Time for Distributed Information Systems", in Proceedings of 1996 International Conference on Data Engineering (ICDE '96), New Orleans, Louisiana, March 1996, pp. 180-189. [BC96] Bestavros, A., and Cunha, C., “Server-Initiated Document Dissemination for the WWW”, IEEE Data Engineering Bulletin, September 1996, pp. 3-11. [BCZ98] Bhattacharjee, S., Calvert, K. L., Zegura, E. W., “Self-Organizing Wide- Area Network Caches”, in Proceedings of the Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings (INFOCOM ’98), San Francisco, California, April 1998, v. 2, pp. 600-608. 162 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [BH96] Bolot, J.-C., and Hoschka, P., “Performance Engineering of the World-Wide Web: Application to Dimensioning and Cache Design”, in Proceedings of the Fifth International WWW Conference, Paris, France, May 1996; Computer Networks and ISDN Systems, v. 28, n. 7-11, pp. 1397-1405. [Buc75] Buckland, M. K., Book Availability and the Library User, New York, Pergamon Press, 1975. [CDF98] Caceres, R., Douglis, F., Feldmann, A., Glass, G., and Rabinovich, M., "Web Proxy Caching: The Devil in the Details", in Proceedings of the Workshop on Internet Server Performance, Madison, Wisconsin, June 1998, pp. 111-118. [CI97] Cao, P., and Irani, S., “Cost-Aware Web Proxy Caching”, Technical Report CS-1343, Computer Science Department, University of Wisconsin-Madison, Madison, Wisconsin, 1997. [CZB98] Cao, P., Zhang, J., and Beach, K., “Active Cache: Caching Dynamic Contents on the Web”, in Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware ’98), The Lake District, England, September 1998. [CID99] Challenger, J., Iyengar, A., and Dantzig, P., “A Scalable System for Consistently Caching Dynamic Web Data”, in Proceedings of the Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’99), New York, New York, March 1999, v. 1, pp. 294- 303. [CV97] Chandramenon, G. P., and Varghese, G., “Reducing Web Latencies Using Precomputed Hints”, Technical Report WUCS-97-24, Department of Computer Science, Washington University, St. Louis, Missouri, 1997. [CDN96] Chankhunthod, A., Danzig, P. B., Neerdaels, C., Schwartz, M. F., and Worrell, K. J., “A Hierarchical Internet Object Cache”, in Proceedings of the 1996 USENIX Technical Conference, San Diego, California, January 1996, pp. 153-163. [CY97] Chinen, K.-I., and Yamaguchi, S., “An Interactive Prefetching Proxy Server for Improvement of WWW Latency”, in Proceedings of the Seventh Annual Conference of the Internet Society (INET'97), Kuala Lumpur, Malaysia, June 1997. [CA95] Clark, R. J. and Ammar, M. H., “Providing Scalable Web Service Using Multicast Delivery”, Technical Report GIT-CC-95-03, College of Computing, Georgia Institute of Technology, Atlanta, Georgia, 1995. 163 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [CKOO] Cohen, E., and Kaplan, H., “Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency,” in Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’00), Tel Aviv, Israel, March 2000, v. 2, pp. 854-863. [CK01] Cohen, E., and Kaplan, H., “Refreshment Policies for Web Content Caches”, in Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’01), Anchorage, Alaska, April 2001, v. 3, pp. 1398-1406. [CKZ99] Cohen, E., Kaplan, H., and Zwick, U., “Connection Caching”, in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, May 1999, pp. 612-621. [CKR98] Cohen, E., Krishnamurthy, B., and Rexford, J., “Evaluating Server-Assisted Cache Replacement in the Web”, in Proceedings of the Sixth European Symposium on Algorithms, Springer-Verlag, Lecture Notes in Computer Science, August 1998, v. 1461, pp. 307-319. [CKR99] Cohen, E., Krishnamurthy, B., and Rexford, J., “Efficient Algorithms for Predicting Requests to Web Servers”, in Proceeding of the Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’99), New York, New York, March 1999, v.l, pp. 284-293. [Cri96] Crispin, M., “Internet Message Access Protocol - Version 4revl”, Request for Comments 2060, December 1996. [CJ97] Cunha, C. R., and Jaccoud, C. F. B., “Determining WWW User's Next Access and Its Application to Pre-Fetching”, in Proceedings of the Second IEEE Symposium on Computers and Communications (ISCC '97), Alexandria, Egypt, July 1997, pp. 6-11. [DHS93] Danzig, P. B., Hall, R. S., and Schwartz, M. F., “A Case for Caching File Objects Inside Internetworks”, in Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM ’ 93), San Francisco, California, September 1993, pp. 281-292. [DKP01] Deolasee, P., Katkar, A., Panchbudhe, A., Ramamritham, K., and Shenoy, P., “Adaptive Push-Pull: Disseminating Dynamic Web Data”, in Proceedings of the Tenth International WWW Conference, Hong Kong, China, May 2001, p p . 2 6 5 - 2 7 4 . [DCW96] Dias, G. V., Cope, G., and Wijayaratne, R., “A Smart Internet Caching System”, in Proceedings of the Sixth Annual Conference of the Internet Society (INET'96), Montreal, Canada, June 1996. 164 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [Duc99] Duchamp, D., “Prefetching Hyperlinks”, in Proceedings of the Second USENIX Symposium on Internet Technologies and Systems (USITS ’ 99), Boulder, Colorado, October 1999. [DRJ01] Dykes, S. G., Robbins, K. A., and Jeffery, C. L., “Uncacheable Documents and Cold Starts in Web Proxy Cache simulations: How Two Wrongs Appear Right”, Technical Report CS-2001-01, Division of Computer Science, University of Texas at San Antonio, San Antonio, Texas, January 2001. [EggOl] Eggert, L., “Speculative Use of Idle Resources”, Ph.D. Dissertation Proposal, ISI Technical Report ISI-TR-560, USC Information Sciences Institute, Marina del Rey, California, October 2001. [FCL99] Fan, L., Cao, P., Lin, W., and Jacobson, Q., “Web Prefetching Between Low- Bandwidth Clients and Proxies: Potential and Performance”, in Proceedings of the International ACM Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’99), Atlanta, GA, May 1999, pp. 178-187. [FCD99] Feldman, A., Caceres, R., Douglis, F., Glass, G., and Rabinovich, M., “Performance of Web Proxy Caching in Heterogeneous Bandwidth Environments”, in Proceedings of the Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’99), New York, New York, March 1999, v. 1, pp. 107-116. [FGM99] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., Bemers-Lee, T., “Hypertext Transfer — HTTP/1.1”, Request for Comments 2616, June 1999. [FT99] Finn, G. G., and Touch, J., "The Personal Node," in Proceedings of the USENIX Workshop on Embedded Systems, March 1999; more complete version available as ISI Research Report ISI-TR-98-461, USC Information Sciences Institute, Marina del Rey, California, July 1998. [GRC97] Gadde, S., Rabinovich, M., and Chase, J., “Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches”, in Proceedings of the IEEE Sixth Workshop on Hot Topics in Operating Systems (HotOS ‘97), Cape Cod, Massachusetts, May 1997, pp. 93-98. [Gla94] Glassman, S., “A Caching Relay for the World-Wide Web”, in Proceedings of the First International WWW Conference, Geneva, Switzerland, May 1994; Computer Networks and ISDN Systems, v. 20, n. 2, pp. 165-173. [Gwe95] Gwertzman, J., “Autonomous Replication in Wide-Area Internetworks”, Technical Report TR-17-95, Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts, April 1995. 165 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [GS95] Gwertzman, J., and Seltzer, M., “The Case for Geographical Push-Caching”, in Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS ‘95), Orcas Island, Washington, May 1995, pp. 51-55. [Ham95] Hamilton, M., “Multicast Approaches to World-Wide Web Caching”, Technical Report LUT CS-TR 988, Department of Computer Studies, Loughborough University of Technology, Loughborough Leics, United Kingdom, August 1995. [HWM98] Hine, J. H., Wills, C. E., Martel, A., and Sommers, J., “Combining Client Knowledge and Resource Dependencies for Improved World Wide Web Performance”, in Proceedings of the Eighth Annual Conference of the Internet Society (INET'98), Geneva, Switzerland, July 1998. [HT98] Hughes, A. S., and Touch, J. “Cross-Domain Cache Cooperation for Small Clients,” in Proceedings of NetStore ’99, Seattle, Washington, October 1999. [JC98] Jacobson, Q., and Cao, P., “Potential and Limits of Web Prefetching Between Low-Bandwidth Clients and Proxies”, in Proceedings of the Third International WWW Caching Workshop, Manchester, England, June 1998. [JDB96] Jeffery, C. L., Das, S. R., and Bemal, G. S., “Proxy-Sharing Proxy Servers”, in Proceedings of the First Annual Conference on Emerging Technologies and Applications in Communications, Portland, Oregon, May 1996, pp. 116-119. [JK97] Jiang, Z., and Kleinrock, L., “Prefetching Links on the WWW”, in Proceedings of the IEEE International Conference on Communications (ICC '97), Montreal, Canada, June 1997, pp. 483-489. [KR01] Kangasharju, J., and Ross, K. W., “A Replicated Architecture for the Domain Name System”, in Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’00), Tel Aviv, Israel, March 2000, v. 2, pp. 660-669. [KW97] Krishnamurthy, B., and Willis, C. E., “Study of Piggyback Cache Validation for Proxy Caches in the World Wide Web”, Proceedings of USENIX Symposium on Internet Technologies and Systems (USITS ‘97), Monterey, California, December 1997, pp. 1-12. [KSR98a] Kurcewicz, M., Sylwestrzak, W., and Wierzbicki, A., “A Filtering Algorithm for Web Caches”, Computer Networks and ISDN Systems, November 1998, v. 30, n. 22-23, pp. 2203-2209. 166 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [KSR98b] Kurcewicz, M., Sylwestrzak, W., and Wierzbicki, A., “A Distributed WWW Cache”, Computer Networks and ISDN Systems, November 1998, v. 30, n. 22-23, pp. 2261-2267. [Lia97] Liao, T., “WebCanal: a Multicast Web Application”, in Proceedings of the Sixth International WWW Conference, Santa Clara, California, April 1997. [LD97] Lei, H., and Duchamp, D., “An Analytical Approach to File Prefetching,” in Proceedings of the USENIX 1997 Annual Technical Conference, Anaheim, California, January 1997, pp. 275-288. [LG96] Lopez-Ortiz, A., and German, D. M., “A Multicollaborative Push-Caching HTTP Protocol for the WWW”, in Proceedings of the Fifth International WWW Conference, Paris, France, May 1996. [Low] The Lowlat Project, USC Information Sciences Institute, http://www.isi.edu/lowlat (published online only) [LA94] Luotonen, A., and Altis, K., “World-Wide Web Proxies”, in Proceedings of the First International WWW Conference, Geneva, Switzerland, May 1994. [MC96] Markatos, E. P., and Chronaki, C. E., “A Top-10 Approach for Prefetching the Web”, Technical Report No. 173, ICS-FORTH, Heraklion, Crete, Greece, August 1996; also in Proceedings of the Eighth Annual Conference of the Internet Society (INET '98), Geneva, Switzerland, July 1998. [Mic] Microsoft® Active Server Pages (ASP), Microsoft Corporation, Redmond, Washington. [Mil68] Miller, R. B., “Response time in man-computer conversational transactions”, in Proceedings of the AFIPS Fall Joint Computer Conference, Montvale, New Jersey, 1968, v. 33, pp. 267-277 [Mog95] Mogul, J. C., “The Case for Persistent-Connection HTTP”, in Proceedings of ACM SIGCOMM '95 Conference, Cambridge, Massachusetts, August 1995, pp. 299-314. [MDF97] Mogul, J.C., Douglis, F., Feldmann, A., and Krishnamurthy, B., “Potential Benefits of Delta-Encoding and Data Compression for HTTP”, in Proceedings of the ACM SIGCOMM ’97 Conference, Cannes, France, September 1997, pp. 181-194. [MKD02] Mogul, J., Krishnamurthy, B., Douglis, F., Feldmann, A., Goland, Y., van Hoff, A., Hellerstein, D., “Delta Encoding in HTTP”, Request for Comments 3229, January 2002. 167 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [Moz] Mozilla, The Mozilla Organization, http://www.mozilla.org [MAM98] Murta, C. D., Almeida, V., and Meira, Jr., W., “Analyzing Performance of Partitioned Caches for the WWW”, in Proceedings of the Third International WWW Caching Workshop, Manchester, England, June 1998. [MR96] Myers, J., and Rose, M., “Post Office Protocol - Version 3”, Request for Comments 1939, May 1996. [Nag84] Nagle, J., “Congestion Control in TCP/IP Internetworks”, Computer Communications Review, v. 14, n. 4, October 1984, pp. 11-17. [Net] Netscape Communicator, Netscape Communications, Mountain View, California. [NB97] Nonnenmacher, J., and Biersack, E. W., “Asynchronous Multicast Push: AMP”, in Proceedings of the International Conference on Computer Communications (ICCC'97), Cannes, France, November 1997, pp. 419-430. [PM96] Padmanabhan, V. N., and Mogul, J. C., “Using Predictive Prefetching to Improve World Wide Web Latency”, Computer Communications Review, v. 26, n. 3, July 1996, pp. 22-36. [PR94] Pitkow, J. E., and Recker, M. M., “A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns”, in Proceedings of the Second International WWW Conference, Chicago, Illinois, October 1994, v. 2, pp. 1039-46. [RF98] Reddy, M., and Fletcher, G. P., “Intelligent Web Caching Using Document Life Histories: A Comparison with Existing Cache Management Techniques”, in Proceedings of the Third International WWW Caching Workshop, Manchester, England, June 1998. [Riv92] Rivest, R., “The MD5 Message-Digest Algorithm”, Request for Comments 1321, April 1992. [RF98] Rousskov, A., and Wessels, D., “Cache Digests”, Computer Networks and ISDN Systems, v. 30, n. 22-23, November 1998, pp. 2155-2168. [SKS98] Schechter, S., Krishnan, M., and Smith, M. D., “Using Path Profiles to Predict HTTP Requests”, Computer Networks and ISDN Systems, v. 30 n. 1-7, April 1998, pp. 457-467. 168 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [SSV98] Scheuermann, P., Shim, J., and Vingralek, R., “A Case for Delay-Conscious Caching of Web Documents”, in Proceedings of the Sixth International WWW Conference, Santa Clara, California, April 1997; also Computer Networks and ISDN Systems, v. 29 n. 8-13, September 1997, pp. 997-1005. [Sla] Slashdot, http://www.slashdot.org. [SAY99] Smith, B., Acharya, A., Yang, T., and Zhu, H., “Exploiting Result Equivalence in Caching Dynamic Web Content”, in Proceedings of Second USENIX Symposium on Internet Technologies and Systems (USITS ’99), Boulder, Colorado, October 1999, pp. 209-220. [Smi94] Smith, N., “What Can Archives Offer the World Wide Web?”, in Proceedings of the First International WWW Conference, Geneva, Switzerland, May 1994; also Technical Report 11*, University of Kent, Computing Laboratory, University of Kent, Canterbury, UK, July 1994. [Squ] The Squid Internet Object Cache, http://www.nlanr.net/ Squid/ [TRS97] Tatarinov, I., Rousskov, A., and Soloviev, V., “Static Caching in Web Servers”, in Proceedings of the Sixth International Conference on Computer Communications and Networks (IC3N ‘97), Las Vegas, Nevada, September 1997, p p .410-417. [TDV98] Tewari, R., Dahlin, M., Harrick, H., and Kay, J., “Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet”, Technical Report TR98-0, University of Texas at Austin, Austin, Texas, February 1998. [TVD98] Tewari, R., Vin, H. M., Dan, A., and Sitaram, D., “Resource-Based Caching for Web Servers”, in Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking, San Jose, California, January 1998. [Tou94] Touch, J. D., and Farber, D. J., “An Experiment in Latency Reduction”, Proceedings of the Thirteenth Annual Joint Conference of the IEEE Computer and Communications Societies. (INFOCOM ’94), Toronto, Canada, June 1994, p p .175-181. [Tou95] Touch, J. D., “Defining 'High Speed' Protocols: Five Challenges & an Example That Survives the Challenges”, IEEE JSAC., Special Issue on Applications Enabling Gigabit Networks, v. 13, n. 5, June 1995, pp. 828-835; also ISI Technical Report ISI-TR-95-408, USC Information Sciences Institute, Marina del Rey, California. 169 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [TH98] Touch, J., and Hughes, A. S., “The LSAM Proxy Cache - a Multicast Distributed Virtual Cache”, Computer Networks and ISDN System, v. 30 n. 22-23, November 1998, pp. 2245-2252. [Ult] UltraDNS Corporation, San Mateo, California. [WC96] Wang, Z., and Crowcroft, J., “Prefetching in World-Wide Web”, in Proceedings of the 1996 IEEE Global Telecommunications Conference, London, England, December 1996, pp. 28-32. [Wes95] Wessels, D., “Intelligent Caching for World-Wide Web Objects”, in Proceedings of the Fifth Annual Conference of the Internet Society (INET'95), Honolulu, Hawaii, June 1995. [WAS96] Williams, S., Abrams, M., Standridge, C. R., Abdulla, G., and Fox, E. A., “Removal Policies in Network Caches for World-Wide Web Documents”, in Proceedings of the ACM SIGCOMM '96 Symposium, Stanford, California, August 1996, pp. 293-305. [WM99a] Wills, C. E., and Mikhailov, M., “Examining the Cacheability of User- Requested Web Resources”, in Proceedings of the Fourth International Web Caching Workshop, San Diego, CA, March/April 1999, pp. 78-87. [WM99b] Wills, C. E., and Mikhailov, M., “Towards a Better Understanding of Web Resources and Server Responses for Improved Caching”, in Proceedings of the Eighth International WWW Conference, Toronto, Canada, May 1999; also Computer Networks and ISDN Systems, v. 31, n. 11-16, May 1999, pp. 1231- 1243. [WM99c] Wills, C. E., and Mikhailov, M., “Exploiting Object Relationships for Web Caching”, Technical Report WPI-CS-TR-99-29, Computer Science Department, Worcester Polytechnic Institute, October 1999. [WM00] Wills, C. E., and Mikhailov, M., “Studying the Impact of More Complete Server Information on Web Caching”, in Proceedings of the Fifth International Web Caching and Content Delivery Workshop (WCW ’00), Lisbon, Portugal, May 2000. [WA97] Wooster, R. P., and Abrams, M., “Proxy Caching that Estimates Page Load Delays”, in Proceedings of the Sixth International WWW Conference, Santa Clara, California, April 1997, pp. 325-334. 170 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [YZL01] Yang, Q., Zhang, H. H., Li, T., “Mining Web Logs for Prediction Models in WWW Caching and Prefetching”, in Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD'01, San Francisco, California, August 2001. [ZFJ97] Zhang, L., Floyd, S., and Jacobson, V., “Adaptive Web Caching”, in Proceedings of the 1997 NLANR Web Cache Workshop, Boulder, Colorado, June 1997. Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Appendix A E-mail-Web System Design The design of the E-mail-Web test system described in Chapter 5 was not chosen arbitrarily. The selected system met the necessary data requirements while balancing software development and ease of use challenges. This chapter explores these challenges in detail, developing a list of criteria for evaluating candidate systems. The candidate systems are presented and evaluated based on these criteria. This chapter is organized as follows. Section A .l describes the approach taken, listing design goals for the test system and specific needs for the implementation. Section A.2 presents implementation options, detailing strengths and weaknesses of these choices. A.1 Approach and Analysis Requirements The E-mail-Web test system will include both data collection and a prototype e-mail URL preloader. Data collection involves examining user interaction with URLs and categorizing URLs that arrive in e-mail messages. The preloader must examine incoming e-mail messages to find URLs and download and store them for the browser. An analysis of user behavior is necessary to quantify the number of URLs that the browser cannot predict. The focus is not on the full set of browser requests, but rather the “top-level” URLs, HTML documents that are the primary requests for any web page; other URL requests for dependent objects can be predicted by these top- level pages. A browser can easily predict page requests that originate from a user click in the current web page (these can be collected by parsing HTML files), as well 172 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. as requests selected from the bookmark list or other configurable buttons, such as “Home” or “Search”. The browser cannot predict URLs that are hand-typed, pasted into the browser, or from other applications that may launch the browser. The analysis of e-mailed URLs will examine the frequency of URLs in e-mail messages and try to determine whether these URLs might be cacheable. It will count the number of URLs that appear in an e-mail message. Parsing e-mail messages for URLs will discover references to images or applets that enhance e-mail messages, called “SRC” URLs. For e-mail messages composed in HTML, SRC URLs represent other opportunities for prefetching, so data about these URLs will be collected. There are three ways to conduct this type of analysis: simulation, log analysis, and implementation. Simulation is not suitable because it requires well-understood models of behavior to emulate. A lot is known about web request patterns at individual servers and in the aggregate at web proxies, but these models do not include information about a user’s URL selection. URLs in e-mail messages have not previously been studied. Log analysis involves collecting logs from working systems and looking for desired behavior. Such analysis requires both web and e-mail logs from individual users to correlate e-mailed URLs with the user’s web requests. While there are many web server logs available for analysis, they do not contain URL selection information. E-mail logs are harder to find. Some system administrators may record statistics about e-mail received by individual users, but these logs do not detail message content. 173 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Because simulation and log analysis are not viable options here, a new system must be implemented to gather data. This system will also support the prototype for the e-mail-based web preloader. As mentioned above, a set of request and behavior logs must be collected. Figure A .l shows E-mail-Web prediction. The implementation breaks down into these components: an e-mail parser that finds URLs within e-mail messages and a preloader that fetches e-mailed URLs and caches them for the browser. If these components are implemented separately, there must be support for communication between them to share URLs. inferred web browsing I URLs 1 usage pattern e-mail reading e-mail msgs H ? usage Q JK~ syntax f y + A m Figure A.l: E-mail — > Web Prediction (Extend — » New Use) A URL request log must contain all top-level “page” requests. If it includes URLs for frame content files or for inline images and applets, these should be distinguished from top-level requests. This log should also indicate how the user selected a URL, whether the request was triggered by a page click, a bookmark or 174 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. other browser source, whether it was hand-typed or pasted into the browser, or whether it came from an e-mail message or other external source. E-mail message details must be logged. This log should include only those messages that the user actually reads. Some e-mail messages are filtered to the trash, explicitly deleted unopened, or ignored. Essentially, the user never receives those messages. Timestamps are important for both e-mail and request logs so that the interval between downloading and reading a message can be determined. This interval provides the lead time for prefetching URLs. The e-mail log should list URLs and SRCs found in e-mail messages. It should provide a count of these for each e-mail message. Short development time is preferable and existing solutions should be used where possible to collect data and implement the preloader. If existing solutions are available, they must be open source and easy to modify as needed. Candidate software needs logging capabilities. Software with existing support for the preloader is desirable. The software should also be supported on many platforms to increase the potential test user pool. Finally, test users should feel comfortable with the test system. It should be easy for them to install and configure. It should also be easy to use. A familiar and powerful graphical interface is preferred. The system should also be passive - using the test system should not inconvenience users nor cause them to change their habits greatly. 175 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The data collection and implementation requirements discussed above are summarized in the lists below. The implementation requirements apply both to data collection and to the preloader. Data Collection Requirements • Complete list of “page” requests • Selection type for each “page” • List of e-mail messages read • List of all URLs and SRCs from e-mail messages Implementation Requirements • Easy to develop/modify code • Quick implementation • Logging capacity • Preload capability • Available for many platforms • Easy to install • Easy to use • Passive (must not alter user behavior) A.2 Implementation Candidates This section considers options for implementation, presenting each with its strengths and weaknesses. Solutions that satisfy all the data requirements are preferred over those that cannot. In the chosen solution, concessions were made with implementation requirements in order to complete the project in a reasonable time frame. 176 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure A.2 shows the configuration of software and servers for the average user. The user runs a browser and an e-mail client on their local machine. The browser interacts with many different web servers. The e-mail client interacts with a POP3 [MR96] or IMAP [Cri96] server for each of the user’s e-mail accounts. Modifying these software packages to log necessary information is impractical because many do not publish their source code. web servers (httpd+) browser e-mail client preload info user machine pop/imap server+ Figure A.2: E-mail/Web System with Modified Web and E-mail Servers Modifying web and e-mail servers, the right side of Figure A.2, allows test users to keep their preferred software. However, it would require modifying all web servers, an impossible task. The e-mail servers must be modified as well (although these would be limited to those used by the test group). Further, with this implementation it would be difficult to isolate requests from a single user and impossible to determine URL selection. One major problem with the above option is the wealth of web servers. A work around is to use a web proxy to provide a single modification point. A web 177 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. proxy handles URL traffic between the browser and web servers, as seen in Figure A.3. The Apache [Apa] proxy server is a full-featured proxy cache that is open source and easy to modify. If the proxy shares a LAN with the user or runs on the user machine, caching documents at the proxy can provide the same response time as in the browser, allowing the proxy to become an effective preloader. web servers (httpd) Apache+ proxy browser e-mail client i preload info user machine pop/imap server Figure A.3: E-mail/Web System with Modified Apache Web Proxy Likewise, an e-mail relay can be used in place of e-mail server modifications. Shown in Figure A.4, the relay functions like a web proxy, passing all e-mail traffic from the client to the server. Once installed, the relay is transparent to the user, allowing them to continue using their preferred e-mail client. Unfortunately, solutions that use proxies and relays cannot provide URL selection information. This must be supplied by the browser. 178 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. web servers (httpd) Apache+ proxy browser e-mail client preload info user machine pop/imap server e-mail relay Figure A.4: E-mail/Web System with Apache Web Proxy and E-mail Relay Mozilla [Moz] is an open source web browser and e-mail client that is based on Netscape [Net], It is supported on many platforms and can be modified to collect e-mailed URLs and URL selection data. The interface is nearly identical to Netscape; in particular, Netscape configuration files can be imported, allowing a smooth transition for test users. The preloader can be implemented within Mozilla as well, requiring no external support. Figure A.5 shows how it would replace a test user’s current browser and e-mail client. Unfortunately, Mozilla has a large, complicated code base, making even small changes very difficult. The code was far from stable during the development of this project, with new versions released every few weeks, including substantial modifications. This translated to execution instabilities, making it less stable than other software the user might choose. Further, Mozilla is difficult to build even on a single platform, making multi-platform support extremely difficult. 179 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. web servers Mozilla+ pop/imap server user machine Figure A.5: E-mail/Web System with Mozilla Web and E-mail Client In spite of the various problems with the previous solutions, replacing Mozilla with an entirely new browser and e-mail client to collect data and preload URLs is not a viable solution. A full-featured browser with a sophisticated user interface is difficult to implement and it is unwise to attempt to do so when better alternatives exist. Overall, the long development time required is outside the scope of this project. The chosen implementation is shown in Figure A.6. It is a composite of two of the solutions discussed above and minimizes the burden of working with Mozilla. A modified version of Mozilla replaces the user’s browser and e-mail client. This new browser tracks URL selection information and records e-mailed URLs and other data. An e-mail relay parses e-mail messages as the e-mail client downloads them. It passes the URLs to a preloading module that downloads the related documents and stores them in the Apache cache. The proxy, relay, and preloader may be installed on the user’s machine. 180 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Apache+ proxy Mozilla+ preload info user machine web (http) e-mail relay & preloader pop/imap server Figure A.6: Composite E-mail/Web System Although this system has several components, the development of each piece is small, allowing greater control and reduced development time. Test users are required to use Mozilla as their browser and e-mail client, and are constrained to one platform to simplify changes to Mozilla. Installation is non-trivial, as the user must install and configure each piece. Because the preloader is an independent module, it may be distributed for use with other systems after data collection is complete. Table A.l summarizes and compares each of the solutions. Requirements with relative values are rated on a subjective scale: poor, fair, neutral, good, great. Requirements judged on a binary scale are satisfied (“•”) or unsatisfied (“x”). The last row summarizes each solution. 181 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Need Generic (no changes) Modify servers Modify Apache Modify Apache + e-mail relay Modify Mozilla New Client Composite D ata Requirements List “page” requests X X • • • • • List “page” selection X X X X • • • List e-mail messages read X X X X • • • List e-mail URLs X • X • • • • Implementation Requirements Open source X ? • • • • • Easy to develop/modify poor poor great great fair fair neutral Quick implementation great neutral great great fair poor neutral Logging capacity fair neutral great great great great great Preload capability X X X X • • • Multi-platform • • • • X X Easy to install great great great good neutral neutral fair Easy to use great great great great good fair good Summary poor poor poor fair good neutral great 1 Unmodified Mozilla available for multiple platforms Table A.1: Solution Comparison The solutions in the last three columns - modified Mozilla, New Client, and Composite system - are the only ones that can collect all the necessary data. Of these solutions, creating a new system is the weakest. It presents the greatest challenges to the developer and the test users. Between the other two, the composite system is a better choice due to the difficulty in modifying Mozilla to implement the preloader. A.3 Summary This chapter presented goals for the test system. After examining various implementation options, a composite of modified software packages augmented with 182 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. newly-created support packages was chosen. Chapter 6 provides details about system implementation. Results from running the system are presented in Chapter 7. 183 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
Abstract (if available)
Linked assets
University of Southern California Dissertations and Theses
Conceptually similar
PDF
Background use of idle resource capacity
PDF
Applying aggregate-level traffic control algorithms to improve network robustness
PDF
Distributed resource allocation in networks for multiple concave objectives
PDF
Adaptive routing services in ad-hoc and sensor networks
PDF
An implicit-based haptic rendering technique
PDF
Architectural support for network -based computing
PDF
Facial animation by expression cloning
PDF
Combining compile -time and run -time parallelization
PDF
Directed diffusion: An application -specific and data -centric communication paradigm for wireless sensor networks
PDF
Bioscope: Actuated sensor network for biological science
PDF
Compression, correlation and detection for energy efficient wireless sensor networks
PDF
An efficient design space exploration for balance between computation and memory
PDF
Coordinating multiagent teams in uncertain domains using distributed POMDPs
PDF
Human -like movement in virtual environments
PDF
G -folds: An appearance-based model of facial gestures for performance driven facial animation
PDF
Design of wireless sensor network based structural health monitoring systems
PDF
An integrated environment for modeling, experimental databases and data mining in neuroscience
PDF
Combinatorial approaches to signal finding and gene finding in DNA sequences
PDF
A flexible framework for replication in distributed systems
PDF
Architectural support for efficient utilization of interconnection network resources
Asset Metadata
Creator
Hughes, Amy Suzanne
(author)
Core Title
Enhancing network object caches through cross -domain prediction
School
Graduate School
Degree
Doctor of Philosophy
Degree Program
Computer Science
Publisher
University of Southern California
(original),
University of Southern California. Libraries
(digital)
Tag
Computer Science,OAI-PMH Harvest
Language
English
Contributor
Digitized by ProQuest
(provenance)
Advisor
Touch, Joe (
committee chair
)
Permanent Link (DOI)
https://doi.org/10.25549/usctheses-c16-256166
Unique identifier
UC11339320
Identifier
3093774.pdf (filename),usctheses-c16-256166 (legacy record id)
Legacy Identifier
3093774.pdf
Dmrecord
256166
Document Type
Dissertation
Rights
Hughes, Amy Suzanne
Type
texts
Source
University of Southern California
(contributing entity),
University of Southern California Dissertations and Theses
(collection)
Access Conditions
The author retains rights to his/her dissertation, thesis or other graduate work according to U.S. copyright law. Electronic access is being provided by the USC Libraries in agreement with the au...
Repository Name
University of Southern California Digital Library
Repository Location
USC Digital Library, University of Southern California, University Park Campus, Los Angeles, California 90089, USA