UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Spatial trend prefetching for online maps mashups Zhang, Jun 2008

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2008_fall_zhang_jun.pdf [ 2.01MB ]
Metadata
JSON: 24-1.0051241.json
JSON-LD: 24-1.0051241-ld.json
RDF/XML (Pretty): 24-1.0051241-rdf.xml
RDF/JSON: 24-1.0051241-rdf.json
Turtle: 24-1.0051241-turtle.txt
N-Triples: 24-1.0051241-rdf-ntriples.txt
Original Record: 24-1.0051241-source.json
Full Text
24-1.0051241-fulltext.txt
Citation
24-1.0051241.ris

Full Text

Spatial Trend Prefetching for Online Maps Mashups by Jun Zhang  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in The Faculty of Graduate Studies (Computer Science)  The University Of British Columbia (Vancouver) August, 2008  © Jun Zhang 2008  Abstract Mashups try to merge some specific information together with online maps application by displaying related markers onto maps. Sometimes markers will be displayed very slowly. In this thesis, we have presented an approach to improve the performance of related applications by reducing network latency for those responses. We use Spatial Trend Web Prefetching Model to predict the areas which can be possibly arrived at after next movements. We classified movements into three patterns. Then this model will check history operations done by a specific user, find possible pattern he may be following and then predict next possible operations for the user according to the specific algorithm responding to that pattern. In our experiments done for lab environment (Nearby Cities application) and Internet environment (Skype-Google Map application), we can see that our approach can achieve hit rate of about 85% when movement interval is not less than l000ms and larger than 30% when movement interval is less than l000ms.  11  Table of Contents Abstract  ii  Table of Contents  iii  List of Tables  v  List of Figures  .  Acknowledgements 1  vi  .  viii  .  Introduction  1  2 Background and Related Work 2.1 Technology for Mashup Applications 2.2 Related Work  4 4 6  3  Spatial Trend Web Prefetching Model 3.1 Definitions 3.2 Spatial Trend Web Prefetching Model 3.2.1 Model Summary 3.2.2 Prefetching for Pattern I 3.2.3 Prefetching for Pattern II 3.2.4 Prefetching for Pattern III 3.2.5 Extensions 3.3 Implementation  8 8 12 12 16 18 19 21 22  4  Analytic Evaluation 4.1 Around Prefetching Approach 4.2 Method 4.3 Results and Analysis for Lab Environment Experiments 4.3.1 Single Pattern Experiment 4.3.2 Simulation Experiment 4.4 Results and Analysis for Real World Case  25 25 26 30 30 45 52  .  .  :iii  Table of Contents 4.4.1 4.4.2  •  Single Pattern Experiments Simulation Experiment  52 57  5  Discussion 5.1 How Mashup Server Affects Prefetching? 5.2 How Prefetching Affects Response Time 7 5.3 Factors Causing the Latency of Displaying Markers 5.4 Future Work  59 59 60 61 62  6  Conclusion  64  Bibliography  65  Appendices A Algorithm, Results and Analysis for Pattern IIIB A.1 Algorithm A.2 Results and Analysis for Experiment IJIB in Lab Environ ment A.3 Results and Analysis for Real Case Experiments  67 67 67 70  iv  List of Tables Experiment Variables and Their Possible Value Experiment Configuration for Single Pattern Experiments in Lab Environment 4.3 Average RT for Un-hit Responses While MI=l000ms 4.4 Results for Three Representative Experiment lilA (MI=Oms) 4.5 Experiment Configuration for Simulation Experiments in Lab Environment 4.6 Trend Prefetching vs Around Prefetching for Simulation Ex periments 4.7 Experiment Configuration for Single Pattern Experiments of Real World Case 4.8 Trend Prefetching vs. Around Prefetching for Simulation Ex periment  4.1 4.2  28 31 33 36 49 51 53 58  v  List of Figures 3.1 3.2 3.3 3.4 3.5 3.6 3.7  A Route to Move Google Map Bound Distance Classes of Pattern III Pattern I Prefetching for 1st look-ahead step Pattern II Prefetching for 1st look-ahead step Pattern II Prefetching for 1st look-ahead step Pattern III A Prefetching  4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23  Hit Rate Changes According to Different P1/MI Increased Traffic Rate Changes According to Different P1/MI Response Time for Experiment lilA while MI=3000ms Response Time for Experiment lIlA while MI=2000ms Response Time for Experiment lilA while MI=l000ms Response Time for Experiment lilA while MI=Oms Average Response Time Hit Rates Increased Traffic Rate Movement Time for Experiment lilA while MI=S000ms Movement Time for Experiment lilA while MI=2000ms Movement Time for Experiment lilA while MI=l000ms Movement Time for Experiment lIlA while MI=Oms Average Movement Time for Experiment III A Series Metrics Sorted According to Different Move Patterns Hit Rate vs. Average Response Time Hit Rates (No Stress on Application Server) Increased Traffic Rate (No Stress on Application Server) Average Response Time (No Stress on Application Server) Response Time for Simulation Experiment Movement Time for Simulation Experiment Hit Rates for Real World Case Increased Traffic Rate for Real World Case  9 11 14 16 18 18 20  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  32 32 33 34 34 34 35 38 39 40 40 41 41 41 43 44 46 47 48 50 50 54 55  vi  List of Figures  4.24 4.25 4.26 4.27  Average Response Time for Real World Case 56 Response Time for Experiment lilA When MI =Oms 57 Response Time for Simulation Experiment of Real World Case 58 Movement Time for Simulation Experiment of Real World Case 58  A.1 Pattern TuB Prefetching A.2 Experiment Results for Experiment IIIB in Lab Environment with Stress on Mashup Server A.3 Experiment Results of Experiment IIIB for Real World Case  68 69 71  vi’  Acknowledgements First I would like to thank my supervisor, Eric Wohlstadter, for helping me throughout my research. He always had time to discuss things and gave priority to reviewing my documents in a timely manner. When I felt lost and did not know where my research was going, he helped me see the overall plan and helped me remain grounded. It was a great opportunity to work with Eric, who is an amazing supervisor and person. I’d also like to thank Peng Li and Chao Yan for their helpful advice on my thesis.  viii  Chapter 1  Introduction Websites such as Google.com and Yahoo.com provide online maps and re lated APIs, and applications have been developed by use of them. We call those applications mashups related to online maps. Some of those mashups display some markers representing some specific information for specific ad dresses, which are covered by the screen. They will display new markers as users move the map to a new area. Those mashups are becoming more and more popular, since they can not only enable users to access some specific information but also relate that information to some specific addresses and their surroundings. For example, through the weatherbonk.com application [21], we can know the weather information of Toronto and also can learn the weather information for those cities near Toronto or those cities along a highway from Ottawa to Toronto. However, we find that sometimes it is very slow for some mashups to display markers onto online maps. Some of this kind of slowness is caused by the rendering of display markers. Sometimes it is caused by slowness of mashups on mashup servers. To solve those issues, programmers can improve their source code to dis play markers as quickly as possible. Some programmers improve mashup performance by reducing the number of requests. For example, Skype Google Map in Section 4.4 gets information, which can be covered by the current screen together with its surrounding areas. Then when users do not move out of that range, there will be no new requests sent out. So it can save some time for network latency by reducing the number of the requests. However, it is very easy for users to move out of the range. When it hap pens, it will be very slow to display markers. Even sometimes, it takes more time because for each request, the mashup gets more data for a larger area. So it can not always solve the problem. To reduce the network latency, which causes markers in mashups to be displayed onto online maps slowly, we adopt the technology of web prefetch ing to predict next possible requests and to get responses for them in ad vance. Then when clients send those requests, those related responses can be retrieved from the memory of clients instead of remote servers. Since 1  Chapter 1. Introduction mashups related to online maps are comparatively new, some traditional web prefetching technologies [12, 15—17, 20, 25] can not be applied. We have developed a new web prefetching model, the Spatial Trend Web Prefetch ing Model. It does prediction based on the operation history done by the specific user. Since operations of users are to move online maps, history data shall include the information related to those movements, such as the distance to move online maps and the interval between every two continuous movements etc. To find the possible trend embedded in movement history data, we have classified movements into several patterns. The model checks which pattern the latest movement follows, how long the interval has taken between the last movement and the step before the latest one, and then does prediction for next possible movements accordingly. We have evaluated the performance of this approach compared with the one without any prefetching and with another prefetching approach analytically in the lab environment and the Internet environment. In the lab environment, we set up a simple mashup application to simulate a real world case and add stress to the mashup server to simulate work load in the real world. For our particular experiments done in the lab environment, the hit rate is about 85% when movement interval (See Definition 3.6) is not less than l000ms and is larger than 50% when movement interval is less than l000ms, except when movement distance (See Definition 3.1) is longer than bound distance (See Definition 3.9 and 3.10). For our experiments done in Internet environment, we choose Skype-Google Map as an experiment subject. Hit rate is no less than 85% when movement interval is not less than l000ms and is at least 30% when the movement interval is less than l000ms. Accordingly the response time in both environments is generally reduced a lot, except when the movement interval is approaching to be Oms and there are big jumps for response time caused by too many requests sent to the mashup server. These specific results depend somewhat on the specific environment and application used. So we discuss those dependencies in detail in Chapter 4. We also find that the movement patterns followed by the latest move ment, the interval between every two movements, the load of the mashup server and the bottleneck of Google Map and Firefox would affect the hit rate and the time to display the markers onto online maps. We begin by providing background information about the technology on mashup applications related to online maps and the work done on prefetch ing or other technologies to improve the performance of those applications in Chapter 2. Then we present our approach to predict next possible move ments based on the history of operations done by users in Chpater 3. We 2  Chapter 1. Introduction present the evaluation done in both the lab environment and the real world case in Chpater 4. Then we discuss some outstanding issues with the am proach and the possible solutions in Chapter 5. After that, we will provide our conclusion in Chapter 6.  3  Chapter 2  Background and Related Work In this part, we will introduce the technology related to mashups for online maps. Additionally, we will discuss related research literature.  2.1  Technology for Mashup Applications  A mashup is “a web application that combines data from more than one source into a single integrated tool” [22]. Currently, the most popular mashups are the Google Maps mashups. According to the statistics data on the programmableweb.com [18], about 23%. of mashups listed belong to this type. Google Maps mashups combine data elements from multiple sources, hiding this behind the graphical in terface of a Google Map. Those mashups display markers at some specific coordinates on Google Maps. It displays those markers as overlays onto the images of Google Maps. According to W3C standards for HTML [23], the overlay element is used to overlay images on top of a base image. The process to build up a Google Maps mashup uses Google Maps APIs [3]. Google’s Maps APIs are based on coordinates; one must specify the latitude and longitude of a location to show it on the map. Google’s APIs have provided a geo-coding service by which you can translate an address to coordinates and show an address on the map. Also, a lot of third parties can help developers get latitude and longitude information. For example, in our own application, Nearby City, to be used in Chapter 4 in the lab experiments, we used the database dump of geonames [9]. For each city, it includes the specific cities’ name, latitude and longitude information. Additionally, we can get this kind of information from some web service. For example, there is a service from geocoder.us [10] that uses public domain data to translate US addresses to coordinates. Google Maps are based on AJAX technology, which provides a way of loading tiles of a large image from Google servers. Programmers ap 4  Chapter 2. Background and Related Work ply AJAX to the development of mashups. When the marker information database, for example, the database on weather information or cities in formation, is deployed on the mashup server, it wifi be very easy to get response information from it. However, when data source has to be got from a third-party server, there will be some problem: For security reasons, most browsers do not allow cross-domain calls. At that time, we may need to make the mashup server forward those requests to a remote server and forward responses back to the client. Then the framework will be like the one in [5], which is used for GPS applications. It takes more network la tency to get data remotely. So prefetching is much more important for those mashups. To begin the development of Google Maps mashups, we have to get a key to use Google Maps APIs at first and then use the key to load a JavaScript file, which includes all of the symbols and definitions you need to use the Google Maps APIs. The first step is to create a Google Map on your own web page by use of the class GMap2 to create a new map instance, which is to be specified by an element in the web page (usually a div element) as a container for the map. To initialize the map, we should provide a pair of latitude and longitude as the center of the map, which can be changed as we move the Google Map. Next, we should develop a script in Javascript to send out AJAX re quests to the mashup server. Those requests shall include the information about the size of the screen, which can be got by GBound, a class in Google Maps APIs and will be sent to the mashup server to get the response in formation, which shall include the information of longitude and latitude for some specific addresses. To display response information onto the Google Map, we use GMarker to create markers for that information related to some specific addresses. We assign a click listener to a marker that pops open an information window over the marker. Then we display those markers by adding the related overlays onto the Google Map. To enable the markers to be updated as we move the Google Map, we use GEvent to catch some specific events. For example, in the Nearby City example, we catch every movestart and moveend event. When those events are caught, the old markers will be removed from the Google Map and the new markers will be displayed onto the Google Map. The Nearyby City application firstly displays the area whose center is the city of Beijing. If the zoom level is set to be 6, the screen may cover the cities including Tianjin, Shi Jiazhuang, Jinan and Zhengzhou and so on. Also there are Google Map default markers to be displayed onto the 5  Chapter 2. Background and Related Work points which represent those cities. Those markers will be updated, when we change the bounds of the screen by changing the zoom level or moving Google Maps. Besides the above basic knowledge, there are two points we have to men tion: Firstly, since Google Maps mashups are related to spatial movements, their performance can be improved by spatial query, which has been ex plored in [7, 11]. Also, most industry databases engines, such as MySQL and Oracle, have provided such functions. So when we design mashups, we can use related techniques to improve the mashup’s performance. The sec ond one: we have found that some security mechanism set up on a mashup server can slow down responses. Generally, there are some firewalls or other ways to help protect mashup servers from intrusion or attack by hackers. So if there are a lot of requests sent to a mashup server, some related firewalls or intrusion detection software may consider those requests are to attack the server and then start the protection mechanism, which will slow down the speed for clients to get responses or make lots of responses get lost. It can be shown by our experiments in Chapter 4.  2.2  Related Work  Web prefetching can be used to improve the performance of web applications. This technology can predict the next possible HTTP operations for users and then get the responses for those operations in advance. Then when users really do those operations, it will get those responses with less time. According to who initiates the prefetching, the prefetching technologies can be classified into three types [16]: Server Side Prefetching, Proxy Side Prefetching and Client Side Prefetching. For Server Side Prefetching, it uses information from the web server to predict the documents that will be requested soon and prefetches the object from the disk to the main memory of the server. Sometimes, it can provide clues on the next possible steps to the client to improve the client’s response time and then the client can initiate a prefetch. For example, in [25], an efficient mechanism is provided for video streaming over wide-area networks with server-assisted prefetching. For the Proxy Side Prefetching, the proxy prefetches documents from web servers and stores them in a proxy cache. It can gather information from multi-clients or multi-servers, which makes it possible to do good prediction. Prefetching from the proxy side is a well studied concept [12, 15]. For Client Side Prefetching, it works with a browser to learn the personal 6  Chapter 2. Background and Related Work profile to predict future requests and uses the available bandwidth to retrieve documents. For example, in [6], the potential of a client-side prefetching mechanism has been explored by use of trace driven simulations. Among the three kinds of prefetching, the Server Side Profetching can not solve the issues caused by network latency and it mainly focuses on reducing the time to access to the hard disk or database. The Proxy Side Prefetching may not be able to reduce the network latency, since sometimes there is network traffic jam between the proxy server and clients. Compar atively, the performance of the Client Side Prefetching may be limited by the resources of the client. Several algorithms have been provided for prefetching to do prediction. Some of them try to do prediction based on statistics data from clients’ visit information. For example the Top-b Prefetching [17] predicts the next re quests by a prediction table consisting of the documents that are accessed very frequently. Some prefetching approaches determine which link wifi be visited based on client behavior characterization. For example, Inteffigent Prefetching [20] does prefetching based on the operations of a web client or behavior learning of the client. It is a prefetching technique by character izing the client side behavior alone. The factors considered to determine prediction include the trend in visit counts and the order of visits of URLs by the web client. This prefetching provides a framework for web client behavior characterization, which classifies the web client’s operations into three modes, and a model to capture and predict client behavior. Since mashups are new kinds of web applications, there is little work done on web prefetching for this kind of application. However, some explo ration has been done to improve the performance of Web 2.0 applications, which can give some clues for us. Doloto [13] tries to reduce the time to load Javascript by doing code splitting for network bound Web 2.0 applications. During this process, Doloto uses a prefetching queue on the application server to store the split source code to be loaded to the client. Another example, the Skype-Google Map application [19] reduces the requests for the application server by getting the response information to cover the sur rounding areas of the current screen. It provides some clues for us that prefetching for around areas is a very straightforward way for programmers to do prefetching, which is why we choose it to do a comparison with our approach in Chapter 4.  7  Chapter 3  Spatial Trend Web Prefetching Model According to our own experience, we can learn that sometimes there are some rules for our usage of an online map. For example, we may move the map for a long distance quickly and as we approach to some object address, we may slow down and move the map with little distance to search the object carefully. To do efficient predictions, it is necessary to analyze the trend or rules embedded in the users’ history of operations. Spatial Trend Web Prefetching Model does predictions based on the analysis of users’ operation history. Firstly we will give the definitions used in the Spatial Trend Web Prefetch ing Model in Section 3.1. After that, we begin to introduce the model in Section 3.2 and provide the details for the algorithm for different movement patterns in Section 3.2.1 3.2.4. At last, Section 3.3 will give details of how we implemented it. -  Definitions  3.1  Before the introduction of Spatial Trend Web Prefetching Model, we give some basic definitions in this section. In Figure 3.1, there are n movements from P 0 to P. The points of P are center points of those screens which are arrived at after each Po movement. For example, Po is the center point of the screen of Google Maps before the 1st movement. We use P to represent the center point of the current screen after the latest movement. For each point, we use the pair of longitude and latitude to represent its position. For example, P (lng, lat). .  .  .  Definition 3.1 (Movement Distance): The distance between two center points of two continuous movements is defined as movement distance. Suppose the ith step is a movement from P to P÷ , then the movement 1  8  Chapter 3. Spatial Trend Web Prefetching Model  •R3(Ing3LaL) r -  -  P2 cIng2.Lat2) —  --  __•  ) (lngc. talc)  amglc(PI.P2) -  Figure 3.1: A Route to Move Google Map: Black points represent center points of the screens after movements  9  Chapter 3. Spatial Trend Web Prefetching Model distance is: Distance(P,P+i)  =  J(lat  —  2 + (lng lat+i)  —  2 lngj+i)  (3.1)  The movement distance is composed of two parts: one in latitude di mension and the other in longitude dimension. Generally, we use those two parts to evaluate how far a map has been moved. Definition 3.2 (Latitude Distance): The movement distance in lat itude dimension (LatDistance) is LatDistance(P, P+ ) 1  =  latj+i  —  latI  (3.2)  Definition 3.3 (Longitude Distance): The movement distance in longitude dimension (LngDistance) is LngDistance(P, P ) 1  =  lng+i  —  lngI  (3.3)  Definition 3.4 (Movement Angle): The angle of movement from P to P 1 is the angle between the line PP 1 and the line parallel to longitude in east as is usual. In Figure 3.1, the angle of P 2 is 2 1 ,P 1 angle(P ) . We can get it by: 1 latZ) lat ) = Arctg( 2 angle(Pi,P (3.4) lngi lng —  —  Definition 3.5 (Response Time): Let the time when a client sends 8 and the time when the client gets its response be Tr. out a request be T Then the response time for this request is: 3 RTTrT  (3.5)  Definition 3.6 (Movement Interval): Let the time when a browser finishes the latest movement be Te and the time when the browser begins to do next movement be Tb. Then the movement interval between those two movements is: (3.6) MITbTe Definition 3.7 (Look-ahead Step): We define those movements pos sibly to be done in the future as look-ahead steps. Let the number of look ahead steps be L. When L=1, this means we are predicting the next move ment; when L=, this means we are predicting the next, next movement and etc. 10  Chapter 3. Spatial Trend Web Prefetching Model Definition 3.8 (Prefetching Interval): Let the time when we do prefetching for ith look-ahead step (L=i) be T and the time when we do prefetching for (i+1)th look-ahead step be Then the prefetching in terval is: P1= T T (3.7) —  Suppose NorthEast and SouthWest represent the diagonal points for the online map displayed in the current screen, as in Figure 3.2. NorthEast (lngejatn)  —Lat Bound Distance—  Lng Bound Distance  SouthWest (lngw,lats)  Figure 3.2: Bound Distance: The lines represent bounds of a screen. The black points represent the SouthWest node and the NorthEast node of the screen. Definition 3.9 (Latitude Bound Distance): The distance between two bounds parallel to latitude lines is Latitude Bound Distance. LatBoundDistance  =  Ilnge  —  lngI  (3.8)  Definition 3.10 (Longitude Bound Distance): Similar to Definition 3.9, Longitude Bound Distance is: LngBoundDistance  =  Ilat  —  I 3 lat  (3.9)  Definition 3.11 (Latitude Distance Ratio): The ratio of LatDis tance and LngBoundDistance: LatDistanceRatio(P, P+ ) 1  =  LatDistance(F, P ) 1 LngBoundDistance  (310) 11  Chapter 3. Spatial Trend Web Prefetching Model Definition 3.12 (Longitude Distance Ratio): The ratio of LngDis tance and LatBoundDistance: LngDistanceRatio(P, P+i)  = LngDistance(F, P ) 1  LatBoundD’istance  (3.11)  The last three definitions will help -describe the Pattern III prefetching algorithm in Section 3.2. Definition 3.13 (Main Direction): The direction in which the map is moved for a longer distance than in other directions. Definition 3.14 (Row Area): The continuous areas with the same size, whose centers have the same latitude are defined as a row area. Definition 3.15 (Column Area): The continuous areas with the same size, whose centers have the same longitude are defined as a column area. Figure 3.7 provides an illustration.  3.2 3.2.1  Spatial Trend Web Prefetching Model Model Summary  There are three assumptions: 1. Users generally do not change their movement patterns constantly, including the direction and distance. 2. The faster for users to move the map, the less possibility for users to change their movement patterns. 3. At most time, movement distance would not exceed one screen bound distance in both dimensions. At that time, LngBoundDistance and <= LatDistance(P_i, P) LngDistance(P_i, P) <= LatBoundDistance. Based on those three assumptions, Spatial Trend Web Prefetching Model predicts the possible direction and distance of look-ahead steps according to history data. Spatial Trend Web Prefetching Model does predictions by applying two main steps: (i) checking and (ii) predicting.  12  Chapter 3. Spatial Trend Web Prefetching Model Checking Based on movement angle and distance, Spatial Trend Web Prefetching Model classifies movements into three movement patterns: Pattern I (Little Distance Pattern): Movement follows Pat tern I only if 0 < LatDistanceRatio(P_i, P) < 1% and 0 < LngDistanceRatio(P_i, P) <= 1% Here we choose 1% instead of a fixed distance value, since some specific distance value may be very little for some zoom level, e.g. 1, but will be very large for another zoom level, e.g. 10. .  Pattern II (Single Direction Pattern): Movement follows Pattern II only if it meets with one of the following conditions: • LatDistance(P_i, P) = 0 and LngDistanceRatio(P_i, P) <= 1% • LngDistarice(P_i, P) = 0 and LatDistanceRatio(P_i, P) <= 1% When one of movement distances exceeds 1% of bound distance and the other one is equal to 0, then we say that the movement follows Single Direction Pattern. Pattern III (Multi Direction Pattern): Movement follows Pattern III only if it meets with one of the following conditions: • LatDistance(P_i, P) > 0 and LngDistanceRatio(P_i, P) > 1% • LngDistarice(Pi, P) > 0 and LatDistanceRatio(P_i, P) > 1% When both movement distances are larger than 0 and at least one of them is larger than 1% of bound distance, then the movement follow Multi Direction Pattern. Based on the main direction, we can classify Pattern III into the following sub-classes: • Pattern III (1): If ( ang1e(P_i, P) <45 and angle(P_i, P) > —45 ), the main direction is east ; • Pattern III (2): If ( angle(P_i,P) < —45 and angle(P_i,P) > —135 ), the main direction is west; • Pattern III (3): If ( angle(P_i, P) >= 135 and ang1e(P_i, P) <= 225), the main direction is south; 13  Chapter 3. Spatial flend Web Prefetching Model  //  •NorthWesl (nurth.*cat)  NcnthLat (nuqtLent)  Pattern ILl (2)  / /  PamFl[()  V  Pattern tUfl)  N  Panern [II (4) •SsuthWest (oUT1i3esU  N. •sournEast flouthsasD  Figure 3.3: Classes of Pattern III  14  Chapter 3. Spatial Trend Web Prefetching Model • Pattern III (4): If ( angle(P_i,P) >= 45 and angle(P_i,P) <= 135 ), the main direction is north; For Pattern III, sometimes the latest movement distance follows some history trend, that is, there is no big change for its distance compared with those of previous ones. Sometimes, there is a big change for the distance of the latest movement. To make sure the prediction is efficient, we should check if the latest movement follows the history trend: •  ILatDistance(Pc_i,Pc)—LatDistance(Pc_ , 2 P_i)I <— LatDstari,ce(PC2 ,P_ ) 1 —  •  LngDistance(P_i,P)—LngDistance(P_2,P_i)I <— LngDisIance _ 0 2,P_j) (P —  0 25 0 25  If both above conditions are ture, we will conclude that the distance of the latest movement follows the same trend with previous movements. Here, we choose 0.25 since if it is increased, hit rate may be decreased and if it is decreased, some needless areas may be prefetched. We chose this parameter’s value based on our intuition. So far we have not validated that it is always optimal. Predicting Next, we do prediction according to the movement pattern information and history information. For Pattern I, the model predicts that look-ahead steps will move with little distance. Since movement distance is little, we do not care about movement angle and distance. For Pattern II, the model predicts look-ahead steps will continue to move in the same direction and movement distance will be no larger than one bound distance. Since to move in a single direction, users have to use move ment cursor buttons in Figure 2.1, which enable maps to move for a short distance, for example about 1/3 of LatBoundDistance or 1/3 of LngBound Distance for a Google Map. For Pattern III, we analyze movement angle and provide a range for those areas to be prefetched. During this process, we predict movement distance based on history data which depends on if the latest movement followed some trend or not. We predict movement distance as below: • If the latest movement followed some trend, then we predict movement distance to be the average value of related movements. This means: Suppose the it/i step till latest movement, movement distance follows the same trend. Then for look-ahead steps, we predict the latitude distance and longitude distance to be: 15  Chapter 3. Spatial Trend Web Prefetching Model  LatDistance(Pk, Pk+1)  1  k=i  2.  k=i  c—i+1  (i  <  c) and  (i  <  c)  LngDistance(Pk, Pk+1) c—i+1  • Otherwise, we predict movement distance to be equal to the last move ment distance. This means: If there is a big change for the distance of the latest movement compared with those previous ones, then we predict the latitude distance and the longitude distance for look-ahead steps to be: LatDistance(P_i, P) and LngDistarice(P_i, Ps); Additionally, in Spatial Trend Web Prefetching Model, we do prediction not just limited to one look-ahead step. Instead, we will do prefetching iteratively. For each ioop, we sleep for a prefetching interval, since constantly sending requests to application server can cause pressure for the mashup server and clients. The details of the prefetching are described in 3.2.2 3.2.4. -  3.2.2  Prefetching for Pattern I  For Pattern I, we define it to move maps for little distance. Since we assume that those look-ahead steps will move map with little distance, then if there is one look-ahead step, that step can be covered by the current screen and those areas around the current one. So, for the 1st look-ahead step we prefetch the surrounding areas. In Figure 3.4, suppose Area 5 is the current screen which the latest movement arrived at. We wifi do prefetching for Area 1 9 for the 1st look-ahead step. -  Figure 3.4: Pattern I Prefetching for 1st look-ahead step  In summary, the algorithm for Pattern I is to find possible areas at first and then do prefetch.hig for those areas. 16  Chapter 3. Spatial Trend Web Prefetching Model  Algorithm 1 Prefetching Algorithm for Pattern I • Input: the bounds information for the area after the latest movement • Procedure: —  —  Find the possible areas to be prefetched: the surrounding area of the current screen. Send requests to the mashup server for those areas;  17  Chapter 3. Spatial Trend Web Prefetching Model  3.2.3  Prefetching for Pattern II  We define Pattern H to move maps in a single direction. Here, we predict that look-ahead steps move in the same direction with the latest movement if it follows Pattern II. For movement distance, we predict it to be Lat BoundDistance or LngBoundDistance. For the 1st look-ahead step, we do prefetching for the next area in the movement direction. For example, in Figure 3.5, suppose the latest move ment arrived at Area 1 from west, we will do prefetching for Area 2 as the 1st look-ahead step.  HII Figure 3.5: Squares represent screens of maps  1  2  3  4  5  6  7  2  9  Figure 3.6: Squares represent screens of maps  Algorithm 2 Prefetching Algorithm for Pattern II • Input: the bounds information for the area after the latest movement • Procedure: —  For each loop *  * * —  j (j  >=  1):  Find possible areas to be prefetched: the jth area next to the current area in the movement direction Send requests to the mashup server for those areas Sleep for prefetching interval  Repeat the loop;  If we do prefetching for several look-ahead steps, we will do prefetching for one additional area extended in the movement direction. In Figure 3.6, continuing the example in Figure 3.5, if we do prefetching for the 6th look ahead step, we will prefetch for Area 6. 18  Chapter 3. Spatial Trend Web Prefetching Model The algorithm for Pattern II is similar to that for Pattern I, except for the way to find possible areas to be prefetched. 3.2.4  Prefetching for Pattern III  We define Pattern III as a movement which moves not in a single direction or little distance. Suppose the center point of the current screen is P and the center point of the previous one is Ps_i, then we do prefetching for the areas that are selected from those which have overlaps with the area defined by (as in Figure 3.7) [—Iangle(P_i, P)I, angle(P_i, P)I]  (3.12)  Since we suppose next movements will be with similar angles to the latest movement, their movement angles will fall in the range defined by formula 111-1 at most times. Suppose the distance of the latest movement in latitude is LatDistanceP and the distance in longitude is LngDistanceP. Check the following conditions: LatDistance(P_i, P) < LngBoundDistance  (3.13)  LngDistance(P_i, P)  (3.14)  <z=  LatBoundDistance  We define Pattern lilA and Pattern IIIB based on 3.13 and 3.14 and design our algorithm accordingly: If both 3.13 and 3.14 are true, then we think movements are following Pattern III A and the next rows and columns could cover next steps. Prefetching will be done starting with the row or column area next to the current one in the main direction. If one of them is not true, then we think movements are following Pattern III B and the next rows and columns could not cover the steps, since those steps have move out of the prefetched areas. We provide a related algorithm in Appendix A. For each look-ahead step, we will do prefetching for one row or column area falling in the specific area defined by formula 3.12: If latest movement follows Pattern III (1) or (2), then we will do prefetching for one column area; otherwise we will do prefetching for one row area. We try to explain above ideas by use of the following examples. In Figure 3.7, after a map is moved from the center of Area 21 to that of Area 17 and both conditions of 3.13 and 3.14 are true, then we will do prefetching for the column with Area 17 and the column beside Area 17 as the 1st look-ahead step, the one with Area 18 for the 2nd look-ahead step, then the one with Area 19 as the 3rd step and the one with Area 20 as the 4th step, etc. 19  Chapter 3. Spatial Trend Web Prefetching Model  -  -  / 1  2  3  6  7  8/9  I -  -  4/5  ,  10  ,  ——-[.---—16...  2y  2  18  19  20  23  24  25  I  L  Figure 3.7: Pattern III A Prefetching  Algorithm 3 Prefetching Algorithm for Pattern III  • Input: the bounds information for the area after the latest movement and history data • Procedure: • Calculate movement distance for look-ahead steps: suppose they are LatDistanceP and LngDistanceP. • For each loop  j (j  >=  1):  — Find the possible areas to be prefetched: *  *  —  —  If the latest movement follows Pattern III (1) or (2): the jth column area next to the current area in the main direction If the latest movement follows Pattern III (3) or (4): the jth row area next to the current area in the main direction  Send requests to the mashup server for those areas;  Sleep for prefetching interval;  • Repeat the loop;  20  Chapter 3. Spatial Trend Web Prefetching Model To sum up, the algorithm for Pattern III is to calculate the movement dis tance at first, next to predict possible row or column areas to be prefetched. It will sleep for one prefetching interval between each iteration. 3.2.5  Extensions  Based on experimental results, we make some improvements for the algo rithm described above: Extension I To avoid duplicate prefetching, we check if there is a hit in memory for the area to be prefetched. If 20 continuous look-ahead steps can get hit, we will conclude that there is a duplication about prefetching. Then to save the resource, we will not continue the process to do prefetching. The reason for us to check 20 continuous steps is that: According to our experiments in the lab environment, if we set that value to be 15 or 10, hit rate would be lower, since some prefetching processes which shall be continued have been stopped. Extension II If movement interval is less than response time, then the hit rate for Spatial Trend Web Prefetching Model will be very low for Pattern II and Pattern III, since before clients can get responses for the prefetching, the map has been moved for several steps. Then it is impossible to get a hit in memory. To solve the problem, we have improved the above algorithm as below: 1. Find the specific look-ahead step whose response is possibly hit. We can get it by RT = ceil(J). 2. If the latest movement follows Pattern II, then for the 1st look-ahead step, we will do prefetching from the area to the one which is the RMth area in the main direction. Starting with the 2nd look-ahead step, we will do prefetching for RM areas extended in the movement direction. 3. If the latest movement follows Pattern III, then for the 1st look-ahead step, we will do prefetching from the column or row beside to the current screen to the RMth column or row area. Starting with the 2nd step, prefetching will be done for every RM rows or columns.  21  Chapter 3. Spatial Trend Web Prefetching Model Here we do not change the algorithm for Pattern I, the reason is that if look-ahead steps follows Pattern I, the possibility for them to move out of those areas around the current one is very low. Extension III We do not want prefetching to be done forever, which will waste a lot of traffic. We use the latest number of continous steps which follow the same movement trend as the number of the steps to do prefetching, since it provides some indication how long a user might follow the same pattern of the latest movement.  3.3  Implementation  There are two ways to implement this web prefetching tool. Both of them need to interrupt the HTTP requests sent from browsers, analyze those requests and do prefetching based on the analysis with Spatial Trend Web Prefetching Model. One is to upload a Javascript by use of GreaseMonkey, an extension for Firefox, and then use the script to interrupt the XMLHTTPRequest, analyze the request information and do prefetching if necessary. The prefetched information will be cached in the memory allocated for Firefox. The whole prefetching process will cost resources of Firefox. It can make Firefox slow down. Also, this way just can work with Firefox, since no other browsers provide a similar extension for different operating systems. The other way is to develop an independent prefetching server on clients, which will interrupt all HTTP requests through setting proxies of browsers and then do prefetching accordingly. This way does not cost the resources for browsers. Also, it can be applicable to work with any browser. So at last we choose this way to implement a multithreaded prefetching server. We implement the model as a Java application, which can be divided into the following parts: Thread Pools There are two thread pools set on the prefetching server. One thread pooi enables this server to catch all of the requests from browsers. The other thread pooi is to do prefetching. For each request, the server selects one of the idle threads from the first pool to handle it. Since for some movement patterns, we have to do prefetching for several steps and there are limited threads in the first pooi, we prefer to use an idle one in the second pool to 22  Chapter 3. Spatial Trend Web Prefetching Model handle prefetching. Caching All of the information is stored in memory as vectors. Here we do not use hash table. The reason is that the process to check if the current area can be hit needs us to check all areas which have overlaps with the current one, since sometimes a hit can compose several responses cached. So hash table can not help us here. In the future, we can use a more advanced data structure such as a spatial index [11]. The information stored is not limited to response content but also in cludes part of the request header, the bound information of the area and zoom level, which are used to differentiate requests. • Since it is possible that some users would like to use two mashups at the same time, we store URL headers for responding applications. • One area cached can be defined by the points SouthWest and NothEast (See Figure 3.2). Then the information of an area to be cached is {lat, tat , lng, lng}. 8 • Also, different zoom levels can produce different responses for an ap plication. For example, the fastfoodmaps application [8] will display only cities who have fast food restaurants on Google Maps when zoom level is 4 and will display the specific restaurants when zoom level is 8. Matching For each request to the mashup server, we check if there is a hit in the memory. We do that by matching the request header, bounds information and zoom level information with those cached ones. If there is a hit, we will return the response content to the client directly. Sometimes, a hit is made up of several responses in the cache. At that time, we have to handle the response by forwarding the combination of them to the client in a correct format. The reason for us not to parse those responses and cache information for separate markers is that: Different mashups provide different formats for their responses and it is very difficult for us to provide a general way to parse them and create a new response. Rate of j4 According to our experiments, when the ratio between prefetching inter val and movement interval is 1/6 in the lab environment, the hit rate will 23  Chapter 3. Spatial Trend Web Prefetching Model be the best. But in the real world case, to save some traffic and avoid big jumps for the response time, we just use the rate of them to be 1/3 and accordingly, the hit rate will become lower. For the details, see Section 4.3 and 4.4.  24  Chapter 4  Analytic Evaluation The evaluation of the efficiency of Spatial Trend Web Prefetching Model will focus on two points: • If our approach can improve the performance of mashups compared with those which do not use any prefetching approach; • If our approach can improve the performance of mashups better than those which use a simple approach For the second point, we choose a simple prefetching approach, Around Prefetching, which is described in Section 4.1. After that, we will do exper iments for the three approaches, the one without prefetching (No Prefetch ing), the one with Around Prefeching and our approach (Trend Prefetching) and analyze the results accordingly. We chose to do experiments in a lab environment first, since we want to evaluate our approach in a clean environment to avoid other factors of the real world that disturb the results, such as unstable response times and security mechanisms (See 5.1) adopted by mashup servers. To make the results convincing, we use various ways together to simulate real-world network traffic. Section 4.2 will give the details of the lab experiments. Section 4.3 will provide the results and accordingly the analysis for the lab experiments. Then we do some experiments outside the lab for a real world mashup, which is covered by Section 4.4.  4.1  Around Prefetching Approach  Since we need to measure how well our approach has improved mashup performance compared with other approaches, we need to find an alternative approach to ours. An easy way to do prefetching is to prefetch around areas after each movement. That is: • For each movement, we will do prefetching for around areas, just like the 1st look-ahead step as mentioned in Figure 3.1. 25  Chapter 4. Analytic Evaluation • For each movement, we just do only one look-ahead step. • Before each operation of prefetching, we will check if there is a hit already for the areas to be prefetched. If yes, then we will not prefetch those areas. In the experiments, we have implemented a prefetching proxy for this Around Prefetching approach.  4.2  Method  To do evaluation in the lab environment, we set up a private subnet, includ ing a desktop as the mashup server, whose CPU is Intel Pentium 4 3.00GHZ and RAM is 1024M, and a laptop as the client, whose CPU is Intel Pentium M 1.30GHZ and RAM is 768M. Also, we chose to develop a mashup, named Nearby Cities, by ourselves using Apache Tomcat, Java Servlet and Mysql. This application is developed to simulate a real world Google Maps mashups using Google Maps APIs. After each movement, the application will display makers for no more than 10 cities in the current screen. For example, if we move a Google Map to the screen with the center of “Beijing”, then the markers representing cities like Beijing, Tianjin and etc. will be displayed accordingly. Those old markers will be removed before displaying new markers. We got the data about cities information all over the world from the Geoname web services [9] and import part of them into our local database. For each city, the information includes its name, the province it belongs to, the country it belongs to, its latitude and longitude, etc. To simulate real world mashup server resource usage, we use netperf [14] to add enough stress to the mashup server to make sure its CPU utilization is about 90% and memory utilization is about 55%. Also to simulate network latency, we make each thread on the mashup server to handle the requests sleep for l000ms, before sending out responses to clients. Another important factor we have to consider is how to design the route to move a Google Map. For the Nearby Cities mashup, we designed routes by selecting the capital cities covered by our database firstly, including Bei jing, Astana, Tashkent, Bishkek, and Ulaanbaatar. Then based on their latitude and longitude, we use Traveling Salesman Problem TSP [1] Sim ulated Annealing SA algorithm [2] to provide a route to move Google Maps. After that, we divide the route between every two continuous points into eight parts and set one point for each part. Google Maps could be moved —  26  Chapter 4. Analytic Evaluation automatically using a Greasemonkey script or the prefetching server, by which we modify some Javascript of the application. This kind of automatic movement can reduce the incorrectness caused by hand. For experiment configuration, we considered several variables which can affect experiment results: movement pattern and movement interval and so on. For details, see Table 4.1. Based on whether movements follow a single pattern or mixtures of pat terns, our experiments are mainly classified into several classes as below: Single Pattern Experiments: In an experiment, movements follow only one movement pattern. For example, in some experiments, we just move a Goolge Map following Pattern III. We will provide a fixed value for movement interval of each experiment. Then the combination of experiment category and movement interval will define different experiment groups. Simulation Experiments: In an experiment, movements simulate how users might use mashups which are related to online maps. That is, our movements will follow a mixture of those patterns in different usage modes. Also, movement interval value is not fixed and will be changed according to different usage modes. To make sure the evaluation to be reasonable and measurable, we use several metrics. We focus on measuring the performance with some met rics, including Hit Rate, Response Time and Average Response Time. We evaluate if prefetching approaches can affect other parts of the application with the metrics of Movement Time and Average Movement Time. Also, we will evaluate increased resources used by our approach with the metric Increased Traffic Rate. The details for the metrics are listed below: Metric 1 (Hit Rate): Let the number of requests that are hit be Nh, and let the total number of requests sent from client to the mashup server be N. Then the hit rate is: HR  x 100%  (4.1)  Metric 2 (Response Time): It has been defined in Definition 3.5 (Response Time) of Chapter 3. Metric 3 (Average Response Time): Suppose there are N steps of 27  Chapter 4. Analytic Evaluation  Table 4.1: Experiment Variables and Their Possible Value Experiment Variables Experiment Category  Movement Interval  Number of Movements  Zoom Level  Possible Value Experiment I: Movements follow Pattern I Experiment II: Movements follow Pattern II Experiment lilA: Movements follow Pattern III and movement distance does not exceed one bound distance in both two dimensions Experiment TuB: Movements follow Pattern III and movement distance will exceed one bound distance in at least one dimension. Oms: Movement interval is set to be Oms. In fact, since it takes some time for a map to be moved, suppose it to be , and then is the real movement interval. See Figure 4.13, it displays the real movement interval while movement in terval is set to be Oms. 250ms: Movement interval is set to be 250ms. 500ms: Movement interval is set to be 500ms. 750ms: Movement interval is set to be 750ms. l000ms: Movement interval is set to be 1000ms. 2000ms: Movement interval is set to be 2000ms. 3000ms: Movement interval is set to be 3000ms. The number of steps to do movement in an ex periment. Let its value to be N. Then we choose N to be: N >= 20 and N <= 40. Since the two mashups used in later parts just cover part of Google Map, if we move for too many steps, we may move into an area not covered by those mashups. Then we can not get response for that movement. So we set the maximum value for N to be 40. At the same time, we want to make sure the precision of our experiment results, so we set N no less than 20. Since we use Google Maps in our experiment, the value for zoom level fall in its range: 0-18.  28  Chapter 4. Analytic Evaluation movements and the ith response time is RT and the average response time is: N  RT  (4.2) N Hit Rate and Response Time are used to evaluate web prefetching ap proaches. By use of the metrics of Response Time, we can check whether a hit can save some response time for the client. However, since a mashup is a real-time application, its response time is dependent on whether the mashup server is stable or not. Sometimes, some individual response time does not change a lot even after using prefetching. For example, in experiments in Section 4.3 and 4.4, there are big jumps for response time as movement in terval is shortened. This may cause us to get an erroneous evaluation. To solve this issue, on one hand, we collect response time for all movements and try to find the graphical trend of them; on the other hand, we use Average Response Time to measure if there is some improvement on the speed for a client to get responses. ART  =  Metric 4 (Movement Time): Let the time to finish a movement be . The movement time is: 8 Te. Let the time to start the movement be T 8 MT=T-T  (4.3)  Metric 5 (Average Movement Time): Suppose there are N steps of movements and the ith movement time is MT, then the average movement time is: N  MT  AMT  (4.4) N Generally there are two parts for a mashup: One part is to display spe cific areas of online maps and the other is the application part which is to display markers and information onto online maps. Our web prefetching ap proach focuses on improving the performance of the application part, that is, to improve the speed of displaying markers onto online maps. During this process, we do not want our approach to affect the performance of another part, such as to delay displaying tiles of online maps. So we provide Move ment Time to measure how quick the map can be moved successfully. Just =  29  Chapter 4. Analytic Evaluation like Response Time, Movement Time also depends on real world network latency. So we also analyze the graphical trend of Movement Time and the metrics of Average Movement Time to measure the speed to move online maps and to check if prefetching approaches have affected displaying online maps. Metric 6 (Increased Traffic Rate): Suppose the traffic generated by prefetched requests and responses is Bpref, suppose the traffic generated by those no-prefetched responses and requests is Bunpref, and suppose the traffic generated by responses and requests while not using any prefetching is B, then increased traffic rate is: ITR  4.3  =  Bpref + Bunpref  —  B  100%  (4.5)  Results and Analysis for Lab Environment Experiments  In the lab environment, we have carried out both the single pattern experi ments and simulation experiments. The details will be shown in this section and Appendix A.1. For each experiment in this section and Appendix A.1, we have repeated it for at least five times. 4.3.1  Single Pattern Experiment  In this section we will do experiments whose movements will follow a single pattern and the movement interval will be with a fixed value throughout an experiment. The configuration of these experiments could be defined by the combination of the values in Table 4.2. There are some points that should be explained: Generally, we set zoom level to be 6 in the experiments. However, sometimes, we have to set it to be 9. As we know, if given the same screen size, LatBound and LngBound distances for Google Map with zoom level 6 is about 8 times of those for the one with zoom level 9. Since we just imported part of cities in the world into our database, sometimes if we use a map with zoom level 6, there will not be enough space for us to move around. When we do Experiment TuB, we set zoom level to be 9, because in that experiment we need to move for a long distance for 40 times. For other experiments, including Experiment I, II and lilA, they are done with the zoom level set to be 6. Here, we just provide and discuss the experiment results for Experiment I, II and 30  Chapter 4. Analytic Evaluation  Table 4.2: Experiment Configuration for Single Pattern Experiments in Lab Environment Experiment Variables Experiment Category  Movement Interval Number of Movements Zoom Level  Possible Value Experiment I Experiment II Experiment lilA Experiment IIIB Oms l000ms 2000ms 3000ms 40 steps When we do experiments in Experiment TuB, we set zoom level to be 9. For other kinds of experiments, they are done with the zoom level set to be 6.  lilA. Appendix A.1 covers the related content for Experiment IIIB. These additional experiments for IIIB are not central to the argument of the thesis. Through those experiments, we will explore the following topics: Topic 1: P1 vs. MI In Chapter 3, when we introduced Spatial Trend Web Prefetching Model, we said that there is a prefetching interval for the proxy server to sleep before starting another loop of prefetching. To find if find there is some relationship between Hit Rate, Increased Traffic Rate and the ratio between Prefetching Interval(PI) and Moving Interval(MT), we did Experiment lilA, since at most time, users move maps following Pattern III with movement distance no larger than one bound distance. According to Figure 4.1 and Figure 4.2, we can conclude that the hit rate and increased traffic rate will change when the ratio between PT and MI changes. Obviously, when the ratio of PT and MI is 1/6, the hit rate will achieve a comparatively high value and increased traffic rate will achieve a comparatively low value. So we choose to set PT to be 1/6 of the latest MI in the following experiments. One point we need to explain here is about why hit rate decreases, when 31  Chapter 4. Analytic Evaluation  Hit Rate Poi- Different Ratio of P1/MI 100  —  -  80  . —.  0  c  40  -  20 1(1/3  1(1/4  1(3/5  1(1/6  4.XI3000ms —a—XIc2000ms XI1000ms XI=Oms  1(1/8  Prefetching Interval (me)  Figure 4.1: Hit Rate Changes According to Different PT/MI  Increased Traffic Rate for Different Ratio of P2/MI  a  300  :  k  100 50  a  —  MI=l000ms MIOms  0  1(1/3  MI/4 1(1/5 1(1/6 MI/S Prefetching Interval (me)  Figure 4.2: Increased Traffic Rate Changes According to Different PT/MI  32  Chapter 4. Analytic Evaluation the rate of PT and MI is less than 1/6, especially when movement interval is less than l000ms. As we know, if the ratio between PT and MI is becoming less, then more prefetching requests will be sent out to the related mashup server. Then when movment interval is small enough like l000ms, there will be too many requests sent out, which increases pressure for the mashup server and results in response time being increased (See Table 4.3). That is, although we have sent out a lot of prefetching requests, we can not get responses in time. So hit rate will be less. This kind of phenomena may not happen in other cases, since our mashup server is just a desktop with lower hardware configurations. Table 4.3: Average RT for Un-hit Responses While MI=l000ms Average RT for Un-hit Responses (PI=MI/5) 1351ms  Average RT for Un-hit Responses (PI=MI/8) 1892ms  According to Figure 4.2, we can conclude as the ratio of PT and MI becomes smaller, increased traffic rate generally remains stable, that is, to be increased little. In Figure 4.9, we will see that when the ratio is fixed, increased traffic rate will be determined by movement patterns. Topic 2: Trend Prefetching vs. Prefetching  No Prefetching vs.  Around  Response Time for Experiment lilA (M13000ms) 2000 u  1500  I  —.—--No Prefetching —-—Trend Prefetching Around Prefetching  1000 500  0 1  471013161922252831343740 ith Movement  Figure 4.3: Response Time for Experiment lIlA while MI=3000ms  33  Chapter 4. Analytic Evaluation  Response Time for Experiment lilA (11=2000mm)  1500 S  .  t  1000  L  —e---No Prefetching —a-—Trend Prefetching  500  Around Prefetching e’enr .nlW’LS  1  3 5 7  Ply ‘Sl.flrlfllflfl,w.,nhl  911 1115171921232527293133151739 ith Movement  Figure 4.4: Response Time for Experiment lilA while MI=2000ms  Response Time for Experiment 111k (1I1000me)  2000  7  1500  [No Prefetching —--—Trend Prefetching Around Prefetthing  u 1000 500  —  -  -. 0  — -  1  3  5  7  9111315171921212527293111353739 ith Movement  Figure 4.5: Response Time for Experiment lilA while MI=l000ms  Response Time for Experiment lIlA (MIOms) 12500  •.  --______  -  __________  _  0  th.,ar. w 1 fl.rler • 13579i1i115i71921232527293139353799  ith Movement  Figure 4.6: Response Time for Experiment lilA while MI=Oms  34  cii  I-  CD  CD  CD  —  ‘5  CD  CD  I  Average Response Time (ins)  I  -I  C  0s  0  ‘0  C  I  1. I-I  CD  ‘5  CD  CD  Averee Response Time (ins)  I  Chapter 4. Analytic Evaluation As at most time, users move maps following Pattern III with movement distance no larger than one bound distance, from Figure 4.3 to 4.6, we show response time for one representative trial of Experiment lilA. Apparently, if there is a hit for a request, then its response will just cost a very short time, no matter which prefetching approach is used. According to those figures, we also can see that if movement interval is becoming short, response time will be increased accordingly. See in Fig ure 4.3, the maximum value for response time for No Prefetching is about lSOOms and in Figure 4.5 and 4.6, the responding value is about l800ms. Also, according to Figure 4.7, the average value of response time is increased while we decrease movement interval. More importantly, when movement interval is shortened, prefetching ap proaches may cause big jumps for the responses. This can be found by comparing Figure 4.3 with Figure 4.6. This also can be proven by the ex periment data listed in Table 4.4. Apparently, it results in the increase of the average response time. The reason to cause those big jumps is that: When using short movement interval, those prefetching approaches will send requests at a very quick speed, which causes the responding mashup server to receive a lot of requests in a short time. Table 4.4: Results for Three Representative Experiment lilA (MI=Oms) Experiment  Experiment 1  Experiment 2  Experiment 3  Prefetching proach  Ap-  No Prefetching Trend Prefetching Around Prefetching No Prefetching Trend Prefetching Around Prefetching No Prefetching Trend Prefetching Around Prefetching  Average sponse (ms) 1373.975 592.4 1246.95  ReTime  Number of responses whose time is larger than l500ms 12 9 11  1311.25 831.5 1161.925  13 11 11  1129.575 510.55 978.875  2 1 4  36  Chapter 4. Analytic Evaluation We can compare the performance of Trend Prefetching and Around Prefetching by checking their average response time. In Figure 4.7, we can see the results for both ways are very similar with each other for Experiment I, since they use the same algorithm for Pattern I. In later figures, we can see that their hit rate and average response time are similar with each other in Experiment I. For Experiment II and lilA, we can see that as movement interval is decreased, the average response time for Around Prefetching in creases more than that for Trend Prefetching. Especially, when movement interval is set to be Oms, there is a big jump for Around Prefetching, which is approaching to No Prefetching. Comparatively, the value of average re sponse time for Trend Prefetching is much less, which demonstrates that our approach can save time for users. So, although there are big jumps for response time of Trend Prefetching, yet the hit rate makes the average value much smaller. Based on Figure 4.8, we can compare hit rate for Trend Prefetching and Around Prefetching. The graphical changes for the three figures are similar with each other. When movement interval is large enough, e.g. 3000ms or 2000ms, hit rate for those two approaches are almost the same. However, when movement interval becomes shorter, especially when it is Oms, hit rate for Around Prefetching will be decreased much more. This can prove that in these experiments, our approach is better than Around Prefetching on predicting next steps, especially when movement interval is very short. According to Figure 4.9, increased traffic rate for both approaches are different according to different movement patterns. We wifi explain them one by one. In Figure 4.9 I, for Experiment I, increased traffic rate of Around Prefetch ing sometimes is the same with or similar to that of Trend Prefetching, Since they use the same algorithm for Pattern I. In Figure 4.9 II, for Experiment II, increased traffic rate of Around Prefetching is more than that of Trend Prefetching, which is caused by the policy of prefetching. If maps are moved in a single direction, Trend Prefetching is just to do prefetching for areas next to the current one, which are not more than 3 times or at most times about 1 or 2 times of the current screen. However, for Around Prefetching, we have to prefetch about 9 times of the current screen for each movement. As a result, increased traffic rate for Around Prefetching is much higher. Figure 4.9 III is very similar to Figure 4.9 II: increased traffic rate of Around Prefetching is more than that of Trend Prefetching. The reason for it is: for Trend Prefetching when movement distance is less than one bound distance, a lot of areas that we want to prefetch will duplicate with 37  Chapter 4. Analytic Evaluation  Hit Rate fGr Experiment T 100  1  80  =  60 40  HI_Around Prefetehing  3000ms 2000ms l000ms Movement Interval  I  300Cms  ISThV STWY f  hte ) htr ()  t t  Prefetching  ‘  Ome  2000ms l06Oms 0  Q0t1t  0  t134  I  S t10034  0o 17075 10721,1  I Hit Rate for Eperirnent I  Series  Hit Rate for Experiment II 100  ; c  p  1  40 20 0 300o  200ho  —+—Trend Prefetchuiig —a--Arotind  100o  Ois  Prefetchiitg  Movement Interval (ms) 3000mg S!V f It boa (w) SItVfxmtbte(W)  20ms  l000as Omo 01 1 369306 39i2847 OL1349306 6020797  (5  1110034  II Hit Rate for Experiment II Series Hit Rate for Experiment lilA 100 ,-.  80 60 —  J—.-—Trend Prefetching —.—Around Prefetching  0  I  20  0 3000.s 2000s 1000o 0.i Movement Interval (ma)  F I Sl 0* IsV  3O00oso  bOa OW) boo  ()  0 1114  20(0mg l000mi 0 I  1 iI34 30618  O.o SO 39021  III Hit Rate for Experiment lilA Series Figure 4.8: Hit Rates  38  Chapter 4. Analytic Evaluation  Increased Traffic Rate for Experiment I 80 60 40 -.  Trend Prefetching —--—Around Prefetchjng  20  •0 2O00,  S000m, I-.  1000mg  0s  Movement Interval ()  I  3WOmi  trV f HR  Jar HR (IP)  200Ori  I000ms  Omi  O.223O7  0  I 699412  18470’6  3118934  0  4426339  108389  I Increased Traffic Rate for Kxperiment E Series Increased Traffic Rate for E,peIiRent II C  200 150  ‘a, ‘a, 2 I. -  C C  50 0 30G0s  2000*:  1000  Move.ent Interval  0*: (es)  3000  fttV fi flR CTP) SIV f HR C  2000.  0694392 0.473762 1.112034 0  lOO0n,  0.  1369306  392847  6.073273  II Increased Traffic Rate for Experiment II Series Increaaed Traffic Rate for Experiment lilA 160  140 120 100 0—  40  3000*: C  —.—Trend Prefetching  —  2000*:  1000*:  Iove*ent Interval  fw F!! (1? TV f& Ii! (WI  0*:  -—Around Prefetching  (*s)  3000*.s 2000*j 1000ms 10*0 3048403 0333071 23081)3 j 1404377 1118034 7 97’62L33 97268 0  III Increased Traffic Rate for Experiment 11L4 Series Figure 4.9: Increased Traffic Rate 39  Chapter 4. Analytic Evaluation each other. Since we have the mechanism to check duplicate areas to be prefetched before each prefetching, so the area to be prefetched is much less than the model has planned and even less than that for Around Prefetching. Lastly, we will check if prefetching approaches affect movement time of Google Map, the part related to displaying online maps in mashups. Movement Time for Experiment lilA (MlE000ins) 600 500 400  —_  300 200  —--—No Prefetching —Trend Prefetohing Around Prefetching  —  10o  —  -  0 1  4  7  10  13  16  19 22  25  28  31  34 37  40  ith Movement  Figure 4.10: Movement Time for Experiment lilA while MI=3000ms  Just because of the reason mentioned before, here, from Figure 4.10 to 4.13, we just display movement time for one representative trial of Ex periment lilA. There is no big difference between movement time for No Prefetching and that using either of the two prefetching approaches. The results for Experiment I, and II are similar to that displayed in Figure 4.10 to Figure 4.13. So based on those data, we can conclude both prefetching approaches will not adversely affect other parts of map mashups.  Topic 3: How movement pattern and movement interval affect Movement Time for Experiment lilA (MI=2000ms)  II  Zi!j  ‘00 0  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ith Movement  Figure 4.11: Movement Time for Experiment lilA while MI=2000ms  40  Chapter 4. Analytic Evaluation  lovement Time for Experiment lilA CElolOllOms)  —.—No Prefetcjiing —‘-Trend Prefetching  Around Prefetching  1  3  5  Figure 4.12:  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ith Invement  Movement Time for Experiment lilA while MI=l000ms  Movement Time for Experiment lilA (MI=ns) -; 1200  1000  I 1  3  5  7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ith Movement  Figure 4.13:  Movement Time for Experiment lilA while MI=Oms  Average Movement Time for Experiment lilA V .  E  350 250 200  —.-—No Prefetching  -:  io  —e---Trend Prefetching Around Prefetchir€  50 C  2  S00Oms  Figure  4.14:  2OOus iCICles Movement Interval (ins)  Average Movement  Time  Cmx  for Experiment  III A  Series  41  Chapter 4. Analytic Evaluation metrics  In these experiments, we considered movement patterns, including move ment angles and movement distances, and movement interval as variables. We will check how those factors affect our metrics results. According to the Figure 4.8 and 4.9, we can know that as movement interval is decreased, hit rate is decreased. As we know, if movement interval is decreased, this means the time available for a client to get response is decreased and this also means that the time available for prefetching server to send out prefetching requests is decreased, which in turn results in the decrease of the possibility for requests to get hit. Based on Figure 4.3 to Figure 4.7, we can see that as movement interval is decreased, response time is increased or even sometimes there are big jumps for it, because of the pressure added and requests jam caused by our prefetching for our mashup server. Figure 4.10 to Figure 4.13 tell us when movement interval is decreased to Oms, movement time is not stable, which is caused by the bottleneck of the performance of Firefox. From Figure 4.14, we can see there is no big change for average movement time as movement interval changes. Now in Figure 4.15, we compare experiment results for different move ment patterns of Trend Prefetching. According to Figure 4.15 I and III, visual trends for hit rate and average response time remain similar for Ex periment I, II and lilA, except for the one when movement interval is set to be Oms. The results of Experiment II are better than others. The reason for it is that: ‘When a map is moved in a single direction with distance less than LatBound or LngBound, it is very easy to do prediction by looking ahead one area in the movement direction if the RT/MI is no more than 1, otherwise for (RT/MI+1) areas. Then if direction is not changed, it can get hit when we get responses in time. Since the area to be prefetched is not as much as those for other patterns and it is easier for Pattern II to get response in time, so when movement interval is Oms, its hit rate ranks as the top one. Based on Figure 4.15 IV, we also can conclude that when movement interval is larger than bOOms, average movement time is very similar with each other for the three patterns. Topic 4: Hit Rate vs. Performance In this topic, we want to explore if there is any graphical relationship between hit rate and performance of Trend Prefetching. Here, we use average response time to represent its performance.  42  Co  CD  0  0  0 fr  C, C-:,  CD  (I) 0  C,:,  CD  C,’  CD  o.q  I  Chapter 4. Analytic Evaluation  Hit Rate vs. Average Response Time for Experiment I 400 J350 • 300 250  —.—-Hit Rate —.—Average Response Tim.  .  200  5 150 100 j 50  L  0 3000mm  2000mm  1000mm  Oma  Hoveinent Interval (as) 3000e SflV fmr I E1ZVforRT  2000ms  0 1657  0 0418  l000eu  1.111034 21336  Cmi, 7.7075  62239  I Experiment I Hit Rate vs.  Averme Resparise Time for Rxperiien’t 11  600 —.—Hit Rate  ‘—8  -  300  -.--Average Response Time  /1/’  -  100  I 3000ms  1000,ns 2000ma Movement Interval (ms)  Urns  3O00m  I I  ST8V SI1EV f  00ms 20  0 0.292  1000ms  0 0.529  I  Omi  1369306 13.7133  [  3 952847 75.131  II Experiment II Hit Rate vs. Average Response Time for Experiment lilA a 9  600 500 (00 300 200  an .-  100 0  r  —a-—Hit Rate  _“-  S000ms  SI1V fDr NI S1V  for  : 2000am  —a-—Average Response Time  1000as  Oms  Movemani Interval (ma) 3000nis 54.879  2000,ms 23.124  3.7713  I 3525  36.563  Cans 115.225  11.303  126.7794  I000nts  III Experiment lilA Figure 4.16: Hit Rate vs. Average Response Time  44  Chapter 4. Analytic Evaluation According to Figure 4.16, we can see that hit rate and average response time will follow the same rules: As the movement interval is decreased, hit rate is decreased and then there will be a big jump for average response time. Based on the analysis above, we know there are two reasons for it: On one hand, decreased hit rate makes more response times have a higher value. On the other hand, decreased movement interval causes traffic jam on mashup servers, which in turn makes response time jump higher.  Topic 5: What happens when there is no stress added to the application server? According to Figure 4.17, when there is no stress on CPU and Memory, hit rate for both of Trend Prefetching and Around Prefetching will be no less than those when we added some stress to the related mashup server to make its CPU utilization be 90% and its Memory utilization be 55%. Especially, when movement interval is l000ms and Oms, hit rate for Trend Prefetching is larger than those in Figure 4.8. The reason is simple: When there is no stress for CPU and Memory, then even there are lots of requests sent to the mashup server at a sudden, the server has enough resource to handle them and then there will be no big jumps for response time then. At the same time, we can see that the graphical trends of the two figures are very similar with each other. According to Figure 4.19, we can see that average response time for those two approaches has been improved, since there are no big jumps for response time and higher hit rate makes more requests to be with less responses time. Accordingly in Figure 4.18, increased traffic rate is increased, since more responses can be got by client before movements are finished. In Figure 4-9, some responses can not be got by client or even lost before movements are finished, which we do not consider as our prefetching traffic. Also, we can see that the graphical trends of the two figures are very similar with each other. 4.3.2  Simulation Experiment  To do a simulation experiment, we analyzed possible operations for a user to use Google Map to find some information for a specific area and its surroundings. We designed the movement route as below: The map is moved following the mixture of Pattern III, II and I and the movement intervals are a mixture of 2000ms, l000ms and Oms. The distances for those steps do not exceed the bound in any dimension. The details of the mixture are: The first 7 steps follow Pattern III for which movement 45  CD  U)  0  C,  0  CD C,-) Co  0  CD Cr)  CD  a  M-J to  0  I  I  0 0  §  H  -[1H  .;-*I  1I lit I’l  !1  Bto  0 0  o  Rate eø  000000  Hit  a  t. x  I  o  tD  to  50  0 0  o  .4  0  0  :,  ‘a  a  to  03-4  a  a  to a  :3 0-  0.  —Sc  .-o  500-50  so  a  •1  so  U  51  to  0  -a  so  a  I oo— ‘0c  a  -03>  a  Rate (%)  oa h a  Hit  0  a  ‘a  S  a  a ‘a 0I 0  S 50  hi  a a  B  0-  0a _s 0  C  a  .4  a  s3> •0-4  Cr  a 0-  Cr  a o  ‘sa 0-  a a a — o_ — a o  —50  00*0  1 h  x  0  to  a  0  C  ‘0  a  U  0  s_c  0  -5  S  a  a 0  $0  0 a  00  a  0  a  *  Rate (s)  a a a a. a 0  Hit  I  I z  —  ‘4  N  C  ‘4  0  N  0%  0  N  0 N  -J  N  §  I  a  N  80  ‘4  0  0  0  0  ‘4  a  0  ‘4  I  0  ‘4  —w  <0  ‘5  I —e  —  0  Is  a  0  0  0  0  0  0  o  C C  o CC  0a  • 0 0 0. 0. —  •G ••%C  f  0.4 -c-c  0(50 0 0 0  GO ,.,C  .1-c  0  OCfl  ——  Increased Traffic Rate (%)  a  I  ‘1  a  S  ‘1  0  0  a  a  C  ‘4’  S  ‘1  .4  0.  a  a  a  a  ‘1  C  I  I  — —  ‘4  0  5’ ‘4  C)  -J  C)  N  a,  Ca C,  C  0  a  (5  N  b1 .3 ‘a  a  N  C  C  0  8  0  a  5 0  —  a  a a  a  S  I  0  ‘10  a  a  a  0  I  I  0  N 0  am  “50 ‘5 0.  C  05  C 5  C  .40..s (1 0  5C ‘5 0  ‘•C’l  0 0  ‘1.1  5’ 0  04  5’ 0  •0>  + 0  -I I-  (5  (5  (5 ‘1  Ca S  ‘1  0  ‘4,  (5  14  0  0  Is “5  •1  -4  ‘5 0.  a,  Is  (1 ‘1 ‘5  I  Increased Traffic Rate (%)  I  I  —  a  0  ‘0  -J a 9 N a ‘a  a  ‘I 0  a  i  a  —  ;II  0  a  Ia  a  0 0 0  Ca  0  0  0  C  00 GO. 0. — 0 ‘5 0  ‘.o  IC  Go  .c  ‘c’l .1’l  0  0  57 -i  0  0  U>  0  0 0  Increased Traffic Rate (%)  a  a  ‘1  a  K  cm  ‘1  0  ‘4  ‘5  a  0  .5  ‘4,  -a -c a  0.  a a  C,  a  •1  0  I  Go  I  CD  —  06  N  S  0O  Ca  N  ‘a  <0 N  C  0  0 0  0  <0  0  <00  I-i  N  0  0  Ca 0 0 0  <0  ff  I.  I 00  a  C,  60  71  .7%  0’  <0  <0  laO  00  N  0  ‘4  I 0 N Ca  Ca  7.3  ‘0  0.  I—, <-1 I-.  C.  DO (7  (7  N  0  00 (7  77 (7  0  (0  00 •0  .7. . Mo 0440  0  ‘1  (010 46 .0 a  z-l a  0000000  —  DO Do (0  a N  Ca  0 0 0  0  Ca  N  Ca  77’, Ca NOD  Ca  N 0  N  Ca  lao  0  0  -4  DO  <C  ii ‘(0  ‘1 0  ‘(0 ‘(0Mb  0.  (0  Ml 40  O (0’  0’  <0  a  Oo  (0  (0’a  (0<071  4b  —  0.70  Ml  4,  .7  4,  a-Ia 010  I,  (0  a  71,  .7  0  Ml  0  -I  0. °70  0  a 0 a  0  0 C 0  4 (7 •1 a a 0  -4  (0 DO 0  (ms)  (ms) 0 0I W 0 C) 000000  Average Response Time  Average Response Time  00  Ca  a  ‘0  0 a  ‘0 a  ‘.0  7.  N  to  Ca 10  N  00  to  7.  7.  a  Ca N  N a 7, 00  N  Ca  (7  N  ‘0  N  U  0  8  0  0  g  0  DO 0  -4  a  00  o  (Do  C.  0 0 0 DO  DO 0  000  C,,  0  4.  4.  o o  (71  0  4.  0’  7  0’  I  0  o  0  (me) 0  co  (71  -4  00 (0  (0 1  N  0 .7  0(0k  00 (7  (0  00  0  a  (7  (0 1 DO 0(0 (0  Average Response Time  Chapter 4. Analytic Evaluation interval is l000ms. The next one follows Pattern I with movement interval to be Oms. The next 7 steps also follow Pattern III and their movement interval is Oms. Then the next 3 steps change to follow Pattern II and the corresponding movement interval is Oms. Then the next 7 movements change back to follow Pattern III and movement interval is l000ms. The next 4 steps will follow Pattern II and movement interval is 2000ms and the last 2 steps follow Pattern I whose movement intervals are Oms. This movement route is designed to simulate how users might move Google Maps to find some specific address: At the beginning, users move very quickly, since they may be far from their object address. As they ap proach to the subject, they slow down. So movement interval is short at first and then becomes larger. During this process, they may make mistake for using the mouse so there is some step following Pattern I. Also, they move following Pattern II and III. At last, they may want to move around to see surroundings quickly. So the last steps follow Pattern I or II with short movement interval. To make sure there is enough space for us to move around, we set zoom level to be 9. So the experiment configuration would be: Table 4.5: Experiment Configuration for Simulation Experiments in Lab Environment Experiment Variables Experiment Category Movement Interval Number of Movements Zoom Level  Possible Value Mixture of Experiment I, Experiment II and Ex periment lIlA. Mixture of Oms, l000ms and 2000ms 31 steps. 6  According to Figure 4.20, we can see that there is less frequency for Trend Prefetching to have jumps on response time compared with Around Prefetching. And there are more responses got hit for Trend Prefetching. So it got higher hit rate and less average response time (See Table 4.6). At the same time, there are some big jumps for Trend Prefetching in Figure 4.20. The reason for those jumps is that: We set movement interval to be Oms since 8th step to 20th step, which causes requests to be increased at once and then in turn results in big jumps of those steps. According to Figure 4.21, there is no big difference for movement time. 49  Chapter 4. Analytic Evaluation  Reonse Time for Simulation Experiment  :y: ;ziz  l500  1  3  7  5  9  ArdPrefetvh  11 13 15 17 19 21 23 25 27 29 31  ith Movement  Figure 4.20: Response Time for Simulation Experiment  Movement Time for Simulation Experiment -600 C -,  :500 400  -  E—  v  -  —a—No Prefetchin I—Trend Prefetching  [ 1  3  5  7  Around Prefetching  9 1113 15 17 1921 232527 2931 ith Movement  Figure 4.21: Movement Time for Simulation Experiment  50  Chapter 4. Analytic Evaluation  Table 4.6: Trend Prefetching vs Around Prefetching for Simulation Experi ments Trend Prefetching (Average STDEV) 7 3.15 292.57 28.14  Around Prefetching (Average STDEV) 49 1.8 299.08 18.71  No Prefetching (Average STDEV) N/A N/A  364.79  522.7396  1017.9  —  Hit Rate % Increased Traffic Rate % Average Response Time ms Average Movement Time ms  —  89.2  —  —  16.74  12.72  —  —  —  85.725  —  —  19.93  11.87  —  96.175  —  —  0.68  18.05  51  Chapter 4. Analytic Evaluation  4.4  Results and Analysis for Real World Case  For the real world case, we have carried out both the single pattern experi ments and simulation experiments. The details will be shown in this section and Appendix A.2. For each experiment in this section and Appendix A.2, we have repeated it for at least five times.  4.4.1  Single Pattern Experiments  In the real world environment, we chose Skype-Google Map [19] from real world ones. This application also is developed on Google Maps. When a Google Map is moved, some icons representing skype contacts of the web administrator will be displayed onto screens. For the real world case, we have  done Experiment II, lilA and TuB. Since the application itself sends requests to cover some around areas of the current screen, so if we do Experiment I, there will be few requests sent out. Then it wifi make results of experiment not make sense at all. Here, we just provide and discuss the experiment results for Experiment II and lilA. For Experiment TuB result, please see Appendix A. We did Experiment II, lilA and TuB using the laptop, which acted as the client in Section 4.3 and is connected to the internet through the private subnet of UBC SPL lab. Then the experiment configuration can be summarized as: During the experiment, we set Pl=MI/3 to save some traffic and avoid possible jumps for response time. Also, we reduced threads in both thread pools to receive connections from browsers and to send prefetching requests, since both ways reduce the increased traffic rate and add less pressure for mashup servers but decrease the hit rate, although not very much. For Experiment lilA, when movement interval is less than 500ms, aver age response time is increased a lot. The reason for this situation is that: Although there is a high hit rate for Trend Prefetching, there are also some big jumps in response time, which makes average response time very big (See Figure 4.25). For Around Prefetching, its hit rate is comparatively low and there are more jumps than No Prefetching. As a result the average value is also very high. The reason for those big jumps is very complex, which can be caused by network traffic jam, and also can be caused by security protection on mashup servers or sometimes can be caused by the pressure already on mashup servers. Comparatively, for Experiment II, since those areas needed to be prefetched in Trend Prefetching are less than those for Experiment lilA, then there are 52  Chapter 4. Analytic Evaluation  Table 4.7: Experiment Configuration for Single Pattern Experiments of Real World Case Experiment Variables Experiment Category  Movement Interval  Number of Movements Zoom Level  Possible Value Experiment II Experiment lilA Experiment IIIB Oms 250ms 500ms 7öOms l000ms 2000ms 3000ms 30 steps. When we do experiments in Experiment IIIB, we set zoom level to be 8. For other kinds of experiments, they are done with the zoom level set to be 6.  53  Chapter 4. Analytic Evaluation  Hit Fate for Experiment II 80 60  p  I—  —.—  Trend Prefetehi ng  —I—around  Prefetching  20  •  .  3000.o 2000as l000ms  750.s  500.s  250.s  U.s  Iovs.ent Interval (is) 3000is  .  f  sniv for If (w)  2000iii  0 0  (W)  1 lSOmo  I000ms  0 0  1.8329841 0.218234  500ms  250ms  Urns  2.237423  2.838933  1.8234321  1.38398311.328287 1.383499f 4.210924 0518724  I Hit Rate for Experiment II Series Hit Rate for Experiment lilA  1 0  _.I-  20  .  .  3000.s  2  10Ona  ?SUis  50  25n  Oirn  Iovit 1ntva1 ()  STt(V for STt(V for I  (1?)  3C0Om 0.854478  20%ins 0  (w)  a  a  1000,,s 7 S Oitu 0 854479 0 0.954478  5.2!4991  5rns 2SOms 0 1.652917 0 6.659627  Ois 0 0  II Hit Rate for Experiment lilA Series Figure 4.22: Hit Rates for Real World Case  54  Chapter 4. Analytic Evaluation  Increased Traffic Rate for Experiment II 300 ‘250 200 150 100  -.  —•--  3000s 2000ms 1O00 750s 500,s 25Ois Moveinnt Interval (as)  ST1V f IlK CIP) SIllY fr Ill (P)  Oi  Trend Prefetching Around Prefetching  750,ns Ous SOOsu 250m 0277369 0.531539 2692285 2444224 0.005774 1248786 0.919239 2236901 17.53851  3000mg  2000mg  I000ms  0628039  0.005714  1289431  0473427  0.11547  I Increased Traffic Rate for Experiment II Series Increased Traffic Rate for Experiment ItI 100 .300  -  —--Trend Prefetching ---Around Prefetching  1C’0 3000ms 2000ms 1O0O 750u SOOms 25055 0 Movement Interval 3000ms  (55)  lSOms 2SOm 0m SOOms 0277369 0.531539 2692285 2444224 0 11547 0005774 1248786 0919239 2236901 1753851  2000ms  SillY fr IlK UP)  0.628039 0,005774  SIlKY Zx 118 CaP)  0473427  i000ms  1.289431  II Increased Traffic Rate for Experiment lilA Figure 4.23: Increased Traffic Rate for Real World Case  55  Cs’  a  o  C  I. PM  Ci)  —  N,  00 V.  ‘0  I  •3  V.  V.  0  § §  Average Raspoe Time (ms)  ‘0  a  I  Average  Respore Time (ms)  Chapter 4. Analytic Evaluation  not so many big jumps and so average response time for Trend Prefetching is not higher than that for No Prefetching. Response Time for Experiment lilA (MI0ms) 3000 2500 • 2000  r  -—__________  /  /•  —.—--Na Prefetching roundPrefetchinj  ith lovesient  Figure 4.25: Response Time for Experiment lilA When MI =Oms  4.4.2  Simulation Experiment  We did the simulation experiment by use of the laptop which connected to the internet through the private subnet of UBC SPL. We suppose the administrator of Skype Google Map to drive from the east of the United States to the west of the United States to travel a half circle of the country. During the process, he wants to visit some of his friends, skype contacts of Skype-Google Map. We simulated him to go through a Google Map to find the correct way to travel to drop by those friends. The whole process was recorded by a Greasemonkey script, including those center points of the screens and movement intervals. Then during the experiment we re played those movements with that script. The whole process included 22 movements and all of them follow Pattern III and most of those movement intervals are less than l500ms and half of them are less than l000ms and larger than 500ms. The zoom level is 8. Just like experiments in Section 4.4.1, we set PI=MI/3 to reduce requests and avoid possible jumps for response time. And, we reduced threads in both thread pools in the experiment to avoid using too much resource on the client. According to Figure 4.26 and Table 4.8, we can see that, hit rate for Trend Prefetching is much higher than that for Around Prefetching. Ac cordingly, average response time for Trend Prefetching is much less than that for Around Prefetching. Figure 4.27 and Table 4.8 show that both prefetching approaches will not affect movement time. -  57  Chapter 4. Analytic Evaluation  Response Time for Simulation Experiment  —-—No Prefetching —a-—Trend Prefetching Around Prefetching  1000 500 0 3  1  11 13 15 9 ith Movement  7  5  17  19  23  21  Figure 4.26: Response Time for Simulation Experiment of Real World Case  Movement Time for Simulation Experiment 1500  ,  ‘::  1  3  5  7  11 13 15 9 jth Movement  17  19  21  Figure 4.27: Movement Time for Simulation Experiment of Real World Case  Table 4.8: Trend Prefetching vs. Around Prefetching for Simulation Exper iment  Prefetch-  Trend  jug  (Average  %  Increased Rate  82.61  —  Traffic  152.98  Re-  205.44  1.54  —  Prefetching  Around Prefetch-  No  ing  (Average  (Average  30.44  —  2.23  319.8  11.24  321.39  —  —  —  STDEV)  STDEV)  STDEV) Hit Rate  —  3.89  N/A  10.17  N/A  %  Average spouse  —  —  7.79  32.13  463.35  23.82  130.5—38.28  —  Time  ms Average  Move-  ment Time  ms  150.54— 32.29  152.41  —  58  Chapter 5  Discussion We discuss factors of the problem domain that complicate web prefetching for mashup applications which are related to online maps and discuss future research.  5.1  How Mashup Server Affects Prefetching?  From Chapter 4, we can see that in the lab environment, those metrics look much better than those collected in real world environment. It is because in lab environment, we have set up a simple and clean environment. In real world, the situation is much more complex. We just discuss some factors that we have found affect prefetching: The first one is the security mechanism set up on a mashup server, which we have mentioned in Chapter 2. Generally, the firewalls or other ways to help protect mashup servers from intrusion or attack may slow down responses. In fact, this kind of protection will not just affect prefetching work in this way, but can also be applied to clients. During the experiments described in Chapter 4, we found that Kaspersky Anti-Virus 6.0 on our laptop blocked or slowed down responses especially when movement interval is set to be about or less than l000ms. Secondly, the performance of the application deployed on a mashup server can affect response time, which in turn will affect the hit rate of prefetching. We think a prefetching or caching tool on the mashup server can help solve the problem. That is, we can provide a tool to help save time of geting data from database by prefetching related data to the memory of the server. The third factor is about the stress on mashup servers. In Chapter 4, we tried to simulate the load in real world to set CPU utilization to be 90% and memory utilization to be 55%. Then we did experiments when there is no stress on the same mashup server. By comparing the results, we found that the stress on the mashup server can affect hit rate, response time and etc.  59  Chapter 5. Discussion Lastly, we notice that some mashup applications provide different re— sponses based on bounds information sent in a request. For example, in fastfoodmaps application [8], perhaps it displays some specific fast food restaurants in the current screen when we set zoom level to be 8. But when we send a request with the screen size three times of the current one, then the response will just include the summary information of some cities to have fast food restaurants but not specific restaurants. While in our prefetching implementation, to avoid creating too many requests for mashup servers, we just do prefetching for the area whose size is three times of the current screen. Otherwise, response time in real world case will be much larger. So if response information varies according to the size of screens, response got from the cache may be not the correct one. Our prefetching can not work in this situation. To solve this issue, we can use the aggrega tion mechanism mentioned in [24] to aggregate separate requests for those areas which have the same size of the current screen together on clients and to aggregate responses for those request on mashup servers. That is, it needs mashup servers to provide the mechanism to analyze and separate aggregation requests and to aggregate responses.  5.2  How Prefetching Affects Response Time?  According to Figure 4.7 and 4.24, we can see that as movement interval is decreased, average response time while using prefetching approaches will be increased much more than that without using any prefetching approach. According to Table 4.4, when movement interval is set to be Urns, there will be big jumps for response time while using Trend Prefetching. So we can conclude that when movement interval is very short, especially when it ap proaches to Urns, prefetching approaches may increase instead of decreasing average response time and slow down the displaying of markers. The reasons are very complex. The first possible reason is the pressure for mashup servers added by prefetching requests. In the lab environment, when we added pressure to the mashup server, the large amount of requests would cause bigger latency. While according to Figure 4.19, when we did not add pressure to the mashup server, average response time would not be increased as much as that displayed in Figure 4.7. So although the pressure for the rnashup server caused by the prefetching requests is limited, yet when there is already enough pressure, it may increase response time a lot. Another possible reason is security protection on mashup servers, which has been mentioned in Section 5.1. When movement interval is shortened  60  Chapter 5. Discussion to be Oms, the speed to send out requests will be very quick. Some security protection mechanism wifi take it as attack for mashup servers and begin to slow down those responses, which will increase response time. Additionally, there may be some other environmental causes for it, such as, the network traffic added by prefetching requests and responses and so on.  5.3  Factors Causing the Latency of Displaying Markers  The goal of our web prefetching is to help speed up markers to be displayed onto online maps. As we know, in a Google Maps mashup, after clients get responses, some Javascript will analyze those responses, create, and then display markers onto Google Maps. So the latency to display those markers includes two parts: network latency, which refers to response time, and dis playing time which refers to the time to create markers and display them. Our prefetching tool just focuses on reducing response time. We have not handled the time to create markers and display them. But sometimes, this factor determines whether markers can be displayed quickly. For example, we have checked weatherbonk.com application [21]. All of the icons of mark ers are loaded remotely when clients display them. It costs a lot of time or even l000ms at worst to load and display them. And response time is just about SOOms. So under this kind of condition, our tool can not improve the speed of displaying markers very much. However, we can use some programming techniques to reduce that la tency: For example, when they design and develop an application, they can make the responding script to load markers in advance and require clients’ browser to cache those icons. Then when clients want to use those icons, they can get them from their cache instead of loading it remotely. Another possible reason affecting displaying markers is the performance of the browser. During our experiments process, we found there is bottleneck for the performance of Firefox. For the same experiment, Firefox costs about 80% percent of CPU utilization on my laptop and Safari just costs about 50% percent of CPU utilization. Also Firefox costs much more memory utilization. When movement interval is very short or set to be Oms, Firefox can not display moved Google Maps and we just saw grey color displayed in screens. And we can not see markers on maps too. However, when we use Safari, we can see the Map and markers displayed in the screen.  61  Chapter 5. Discussion  5.4  Future Work  According to the experiment results, we can see that there are still a lot of work needed to be done to improve our prefetching tool, such as to reduce increased traffic rate; to improve hit rate while the movement interval is short and to consider other factors to improve the performance of mashups and etc. Currently we cache all responses prefetched, which waste a lot of memory of clients. In the future we would provide a mechanism for cache replace ment. Also, we should do further analysis for the performance of mashups when movement interval is less than l000ms. For example to simplify the factors which wifi affect the prefetching results, perhaps we can download the whole Google Map locally, which will reduce the effect caused by latency of Google Maps. Our prefetching tool is based on the assumption that every user would follow some pattern to use online maps. Also, we assume that once a user follows some pattern, generally he wifi not change it at once. However, hi real world, move patterns may be much more complex than those assumptions. So we need more analysis on users’ usage history information and then provide better prediction. For example, we can try to use some machine learning knowledge and artificial inteffigence knowledge to help improve our approach by predicting the possible area with higher possibility and aJso in a smaller range. Then both hit rate and increased traffic rate can be improved. Since fewer requests are sent out to mashup servers, there will be less big jumps for response time. Also, we can consider other factors mentioned above which affect our prefetching. For example, we can set up another prefetching tool on a mashup server, which can do prefetching from databases and then cache responses which are used most frequently by clients in its memory. Then it will save a lot of time to do search again from databases. Accordingly response time will be improved. Another example, on clients, we also can analyze Javascript loaded and do some modification by use of some Greasemonkey script to load some picture or icons related to markers in advance. Then we can save a lot of time to display markers. Additionally, until now, all of the experiments are done in cable network environments. We have not evaluated our prefetching tool in a wireless environment. As more and more mashup applications have been developed for mobile or wireless environment, there is such need to make it to be applied in this kind of environment. Since there is big difference on the 62  Chapter 5. Discussion speed between cable network and wireless one, so perhaps, this will need higher efficiency for our approach to be able to cause less increased traffic rate while maintaining a reasonable hit rate. In this thesis, we have only tried to support applications using the HTTP protocol. However, applications such as Google Maps might be supported better in the future by streaming protocols or other more efficient protocols, since the Map should respond to user input in soft real-time. For example, perhaps we can use Comet protocol [4] to improve the performance.  63  Chapter 6  Conclusion More and more mashup applications are developed on online maps, such as Yahoo! Map and Google Map. They try to merge some specific information together with online maps application to provide a new kind of service for users. Those services are very attractive. But sometimes markers will be displayed very slowly, which is caused by network latency. In this thesis, we have presented an approach, which is deployed on clients, to improve the performance of related applications by reducing net work latency for those responses. In this approach, we use Spatial Trend Web Prefetching Model to predict the areas which can be possibly arrived at after next movements. We classified movements into three patterns. Then this model will check history operations done by a specific user, find possible patterns he may be following and then predict next possible operations for the user according to the specific algorithm responding to that pattern. Ac cording to our evaluation, we can see that our approach can achieve hit rate of about 85% when movement interval is not less than l000ms and larger than 30% when movement interval is less than l000ms in our experiments. Although there are stifi some issues in our approach, e.g. there may be some big jumps for response time when there is no hit in real world case experiment, we analyzed them and try to provide possible solutions for them.  64  Bibliography [1] D.L. Applegate, R.E. Bixby, V. Chvtal, and W.J. Cook. The Travel ing Salesman Problem: A Computational Study. Princeton University Press, 2006. [2] V. Cerny. A thermodynamical approach to the traveffing salesman problem: an effi.cient simulation algorithm. Journal of Optimization Theory and Applications, 45:41—51, 1985. [3] http://code.google.com/apis/maps/. [4] http://cometdaily.com/. [5] C. du Mouza and P. Rigaux. Web architectures for scalable moving object servers. In the 10th ACM international symposium on Advances in geographic information systems, pages 17—22, 2002. [6] A. Eden, B. Joh, and T. Mudge. Web latency reduction via client-side prefetching. In Proc. p000 IEEE mt. Symp. on Performance Analysis of Systems Software ISPASS 2000, pages 193—200, 2000. —  [7] Max J. Egenhofer. Spatial sql: A query and presentation language. IEEE TKDE, 6-1, 1994. [8] http://www.fastfoodmaps.com. [9] http://www.geonames.org/export/. [10] http://www.geocoder.us. [11] Chia-Hsin Huang, Tyng-Ruey Chuang, Dong-Po Deng, and Hahn Ming Lee. Efficient gml-native processors for web-based gis: Tech niques and tools. In L4th International Symposium of ACM GIS AdvancesinGeographicinformationSystems, November 2006.  [12] Thomas M. Kroger, D. E. Long, and J.C. Mogul. Exploring the bounds of web latency reduction from cacheing and prefetching. In Proceedings 65  Bibliography of the Symposium on Interworking Systems and Technologies, pages 13—22, December 1997. [13] BenJamin Livshits and Emre Kiciman. Doloto: Code splitting for network-bound web 2.0 applications. Technical report, Microsoft Re search, 2008. [14] http://www.unixguide.net/hp/faq/7.1.2.3.shtml. [15] V.N. Padmanabhan and J.C. Mogul. Using predictive prefetching to improve world wide web latency. Computer Communications Review, 26:22—36, 1996. [16] http://www.utd.edu/Ilyen/course/web/yanlou.ppt. [17] http: //www.ics.forth.gr/carv/r-d-activities/wwwPerf/INET98_prefetch/. [181 http://www.programmableweb.com. [19] http://www.voidstar.com/skymap/. [20] N. Swaminathan and S.V. Raghavan. Intelligent prefetch in www us ing client behavior characterization. IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunica tions Systems MASCOTS’00, page 13, 2000. [21] http://www.weatherbonk.com/. [22] http://en.wikipedia.org/wild/Mashup_webapplication_hybrid/. [23] http://www.w3.org/MarkUp/htm13/overlays.htnil. [24] K.C. Yeung and P.H.J. Kelly. Optimising java rmi programs by com munication restructuring, in: Proceedings of the middleware 2003. Springer Verlag, pages 324—343, 2003. [25] Jun11 Yuan, Qibin Sun, and Susanto Rahardja. Server-assisted prefetch ing for internet streaming media delivery. In Multimedia Systems and Applications IX, SPIEá International Symposium on Optics East OO6, October 2006.  66  Appendix A  Algorithm, Results and Analysis for Pattern TuB A.1  Algorithm  If one of the formulas 3.13 and 3.14 in Chpater 3 is not true, then the next rows and columns could not cover the steps, since those steps have move out of that prefetched areas. Then we have to calculate the proper areas to be prefetched by use of LatDistanceP in latitude dimension and LngDistauceP in longitude dimension. Then we have to calculate the proper areas to be prefetched by use of LatDistanceP in latitude dimension and LngDistanceP in longitude dimension. Prefetching will be done starting with the row or column area in the main direction, whose distance from the current one is LatDistanceP in latitude dimension and LngDistanceP in longitude dimension. For example, in Figure A.1, suppose the map is moved from the center of Area 21 to that of Area 13 and there is a big change for the movement distance although it also follows Pattern III A, then we will do prefetching for the column with Area 13 for the 1st look-ahead step and then do prefetching for the one with Area 20 for the 2nd loop-ahead step. To improve the hit rate, we are not limited to doing prefetching for the column in the main direction. We will also do prefetching for the column next to the predicted column in the opposite direction, since sometimes users would reduce movement distance at once.  A.2  Results and Analysis for Experiment TuB in Lab Environment  In the experiments done in lab environment mentioned in Chapter 4, we have got the results shown in following Figures. Figure A.2 I seems very different from those three ones in Figure 4.8: hit rate for Around Prefetching is 0% in the experiments no matter how long 67  Appendix A. Algorithm, Results and Analysis for Pattern IIIB  1 6 —  —  11  2  3  7  8..  —  4•/• 5 9  10  —  12/ 13  14  15  —---  16/,/  18  19  20  2/’2  23  24  25  .  -  -  —  -  -  -  Figure A.1: Pattern IHB Prefetching  68  Appendix A. Algorithm, Results and Analysis for Pattern IIIB  Average Response Time for Experiment IIIB 1500  i  —+--No Prefetching  0 03  1000  E  Trend  —1  .  Prefetthing  0 3000ms 2CXX)ms l000ins Oms Movement Interval (ms)  I Average Response Time for Experiment IIIB Series Hit Rote for ExperiRent 100  tuB  -,  —.—  80  4  Trend  Prefetching ching  “—S  — 30001$  20001s  j000is  01$  Movement Interval (mo) 3007ms STtV CTP) S1Vf(Ij’)  2OOO.s 0 o  1377  1OO0s 287439  o  0 875)376 o  II Hit Rate for Experiment IIIB Series Increased Traffic Rate for Experiment IllS ‘.  0i  1400 1200  —.—Trend  1000  Prefetching  -i  800 4’ 1.  u  —.—Around —  —  200Os  l000ms  BOO 400  Prefetching  200  0 3000ms  Os  Movement Interval (ms)  I  Isco StV f i-rn (19) SflV f fiR (IE)  I2eoo.,  4911874  1862158  11040s 704558  0  0  0  Io  I  4008158 1499582  III Increased Traffic Rate for Experiment IIIB Series Figure A.2: Experiment Results for Experiment TuB in Lab Environment with Stress on Mashup Server 69  Appendix A. Algorithm, Results and Analysis for Pattern IIIB movement interval is set to be. The reason is that: For Around Prefetching, we just do prefetching for areas around the current screen. If movement distance is longer than LatBound or LngBound, we can not get a hit, since we have move out of those around areas. In Figure A.2 I, as we can see when movement interval is decreased, hit rate for Trend Prefetching is decreased a lot. This can be explained by the design of the experiment. For Experiment I, II and lilA, all of them is done while setting zoom level to be 6. Then its LatBound is 8.42 and LngBound is 10.98 in our application. For Experiment IIIB, when we set zoom level to be 9, its LatBound is 1.05 and LngBound is 1.37. Obviously, the previous one can cover much more possible areas than the later one. So it is much easier for requests in the one with zoom level to be 6 to get a hit. For the later one, it can not prefetch proper areas for the 1st look-ahead step but may get them for several steps. So when movement interval is long enough for it to do prefetching for several steps, then it will get a high hit rate. When movement interval is decreased, and there is no such chances and accordingly, hit rate will be decreased a lot. In Figure A.2 III, when movements follow Pattern III and movement distance is more than one bound distance in at least one of the dimensions, increased traffic rate of Around Prefetching is much less than that of Trend Prefetching. Just as what we have said in above paragraphs, to make sure hit rate to be acceptable, if there is enough time, Trend Prefetching approach will prefetch for several steps in main direction, each of which will add about 10 more areas to be prefetched. As movement interval is decreased, area to be able to be prefetched becomes smaller. So when movement interval is large enough, increased traffic rate for Trend Prefetching is much larger and it will be decreased to be almost the same with that for Around Prefetching when movement interval is Oms.  A.3  Results and Analysis for Real Case Experiments  Based on Figure A.3, we could see that the results for Experiment IIIB follow similar graphical trend as those in Figure A.2, except that: compared with results displayed Figure A.2 III, increased traffic rate seems to be much lower for both prefetching approaches. The reason is that: For some areas, responses of Skype-Google Map are very short, since there are no skype contacts living in that area.  70  Appendix A. Algorithm, Results and Analysis for Pattern IIIB  Hit Rate for Experiuient II 100  -.  ----  •  -------  —-  80  20 0  •  I  280  I  75  1s  5  et 1nteva1 300Gm,  sntv f  2000m,  (w)  058325  C  STRVf,r(S?)  0  C  ()  lOm,  750 SOO 25Gm, 0 3 218749 4.28321 t652977 0 0 0 0  721084 0  Hit Rate for Experiment IIIB Series Irorased Traffic Rate for eriu98nt II --  —  .  .  .  .-_;_  D0  1cs  20X1,s  1o 320m,  gntv 23R (W) I831tVforI1R(P)  .15 1 ms  -.—Trid Pefetching efetcing  -  3934  1ntavo1 228is  .  ()  1l0,n  5On 7  5OGm  49.28941 24.12985 57.12883 6023819 GI 0 01 0  250  0  34.2834 72.23814 89.23987 ol 124383127.12811!  Increased Traffic Rate for Experiment IIIB Series Resxme Tia fr Brinrnt IIB  iai  ------------  -  hict  —  —s—N:, F9fetthirg  —I--Td Ffetd±g —---—---  i  j ahE ahE sm 7Eha  &o.ri Fafeb±ir€  Gis  Interval  Average Response Time for Experiment IIIB Series Figure A.3: Experiment Results of Experiment TuB for Real World Case 71  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0051241/manifest

Comment

Related Items