A hierarchical and multiscale approach to analyze E-business workloads

Abstract

Understanding the characteristics of electronic business (E-business) workloads is a crucial step to improve the quality of service offered to customers in E-business environments. This paper proposes a hierarchical and multiple time scale approach to characterize E-business workloads. The three levels of the hierarchy are user, application, and protocol, and are associated with customer sessions, functions requested, and HTTP requests, respectively. Within each layer, an analysis across several time scales is conducted. The approach is illustrated by presenting a detailed characterization of two actual E-business sites: an online bookstore and an electronic auction site. Our analysis of the workloads showed that the session length, measured in number of requests to execute E-business functions, is heavy-tailed, especially for sites subject to requests generated by robots. An overwhelming majority of the sessions consist of only a handful requests, which seems to suggest that most customers are human (as opposed to robots). A significant fraction of the functions requested by customers were found to be product selection functions as opposed to product ordering. An analysis of the popularity of search terms revealed that it follows a Zipf distribution. However, Zipf’s law as applied to E-business is time scale dependent due to the shift in popularity of search terms. We also found that requests to execute frequent E-business functions exhibit a pattern similar to the HTTP request arrival process. Finally, we demonstrated that there is a strong correlation in the arrival process at the HTTP request level. These correlations are particularly stronger at intermediate time scales of a few minutes.

Introduction

Electronic business (E-business) sites are very complex, composed of several tiers of servers of different types (e.g., web servers, application servers, and database servers), and are subject to workloads that vary in ways hard to predict. The quality of service requirements for E-business sites are strict since customers demand fast response times and high availability or else they turn to competitors. Understanding the nature and characteristics of E-business workloads is a crucial step to improve the quality of service offered to customers in E-business environments. E-business workload characterization can lead to a better understanding of the interaction between customers and web sites and can also help design systems with better performance and availability [16]. This paper presents a hierarchical and multiple scale approach to the characterization of E-business workloads.

E-business workloads are composed of sessions. A session is a sequence of requests of different types made by a single customer during a single visit to a site. During a session, a customer requests the execution of various E-business functions such as browse, search, select, add to the shopping cart, register, and pay. A request to execute an E-business function may generate many HTTP requests to the site. For example, several images may have to be retrieved to display the page that contains the results of the execution of an E-business function.

Past studies of WWW workloads concentrated on information provider sites and found several characteristics common to them [5], [7], [9], [18]. Some of these characteristics deal with file size distributions, file popularity distribution, self-similarity in web traffic, reference locality, and user request patterns. A number of studies of different web sites found file sizes to exhibit heavy-tailed distributions and object popularity to be Zipf-like. Other studies of different web site environments demonstrated long-range dependencies in the user request process, in other words, strong correlations in the user requests. In particular, Arlitt and Williamson [7] identified 10 workload properties, called invariants, across six different data sets, which included different types of information provider web sites. Some of the most relevant invariants are: (i) images and HTML files account for 90–100% of the files transferred; (ii) 10% of the documents account for 90% of all requests and bytes transferred; (iii) file sizes follow the Pareto distribution, and (iv) file inter-reference times are independent and exponentially distributed. Shortly after, Almeida et al. [5] discovered that the popularity of documents served by web sites dedicated to information dissemination follows a Zipf’s law. In [9], the authors pointed to the self-similar nature of web server traffic. All these studies were performed almost 5 years ago. Since then, several major changes have been observed in the WWW. The most important are: clients now have much larger bandwidth, the number of users has grown exponentially, and E-business became one of the major applications on the web.

In [12], the authors introduce the notion of session, consisting of many individual HTTP requests. However, they do not characterize the workload of E-business sites, which is composed of typical requests such as browse, search, select, add, and pay. The analysis focuses only on the throughput gains obtained by an admission control mechanism that aims at guaranteeing the completion of any accepted session. The work in [19] proposes a workload characterization for E-business servers, where customers follow typical sequences of URLs as they move towards the completion of transactions. The authors though do not present any characterization or properties of actual E-business workloads.

There are very few published studies [6], [14], [17] of E-business workloads because of the difficulty in obtaining actual logs from electronic companies. Most companies consider web logs to be very sensitive data. In [17], the authors propose a graph-based methodology for characterizing E-business workloads and apply it to an actual workload to obtain metrics related to the interaction of customers with a site. For example, the paper shows how to obtain information such as the number of sessions, average session length, and buy-to-visit ratio. Ref. [15] presents several models (e.g., customer behavior model graph and customer visit model) for workload characterization of E-business sites. It also shows how workload models can be obtained from HTTP logs. Our previous work [14], extended here, discussed the issue of how to obtain invariants for E-business workloads. In [6], Arlitt et al. characterize the workload of an actual E-commerce site for the purpose of analyzing its scalability. They use performance-related criteria to cluster requests into similar groups. They then use multiclass queuing models to carry out a capacity planning study for the site. In [3], the authors study the impact of time scale on operational analysis for a large web-based shopping system. They show that time-related service level agreements and input parameters for predictive queuing models are sensitive to time scale.

A question that naturally arises is: are the characteristics and invariants found in information provider web sites still valid for E-business workloads? To answer this question, we define a hierarchical and multiscale approach to characterize the workload of E-business sites. The three layers of the hierarchy are: session, function, and HTTP request, as defined in Section 2. Within each layer, an analysis across several time scales is conducted. The approach is illustrated by presenting a detailed characterization of two actual E-business sites: an online bookstore and an electronic auction site. This paper extends our previous work [14] and examines statistical and distributional properties of the E-business workloads and compare these properties across the two data sets. As much as possible, we compare the features of these workloads with the invariants that were discovered for information dissemination web sites and provide an extended multiscale analysis of the workload. The same hierarchical approach was used by the authors to study the presence of robots in web workloads [4].

The rest of the paper is organized as follows. Section 2 shows the approach used to characterize E-business workloads. The next section describes the data collection process. Section 4 analyzes two logs from actual E-business sites and characterizes the workload at the HTTP request level. Characterizations at the E-business function and session levels are provided in 5 Function characterization, 6 Session characterization, respectively. Finally, Section 7 presents concluding remarks.