Publications by Mark Crovella

Understanding the nature of the workloads and system demands created by users of the World Wide Web is crucial to properly designing and provisioning Web services. Previous measurements of Web client workloads have been shown to exhibit a number of characteristic features; however, it is not clear how those features may be changing with time. In this study we compare two measurements of Web client workloads separated in time by three years, both captured from the same computing facility at Boston University. The older dataset, obtained in 1995, is well-known in the research literature and has been the basis for a wide variety of studies. The newer dataset was captured in 1998 and is comparable in size to the older dataset. The new dataset has the drawback that the collection of users measured may no longer be representative of general Web users; however using it has the advantage that many comparisons can be drawn more clearly than would be possible using a new, different source of measurement. Our results fall into two categories. First we compare the statistical and distributional properties of Web requests across the two datasets. This serves to reinforce and deepen our understanding of the characteristic statistical properties of Web client requests. We find that the kinds of distributions that best describe document sizes have not changed between 1995 and 1998, although specific values of the distributional parameters are different. Second, we explore the question of how the observed differences in the properties of Web client requests, particularly the popularity and temporal locality properties, affect the potential for Web file caching in the network. We find that for the computing facility represented by our traces between 1995 and 1998, (1) the benefits of using size-based caching policies have diminished; and (2) the potential for caching requested files in the network has declined.

One role for workload generation is as a means for understanding how servers and networks respond to variation in load. This enables management and capacity planning based on current and projected usage. This paper applies a number of observations of Web server usage to create a realistic Web workload generation tool which mimics a set of real users accessing a server. The tool, called Surge (Scalable URL Reference Generator) generates references matching empirical measurements of 1) server file size distribution; 2) request size distribution; 3) relative file popularity; 4) embedded file references; 5) temporal locality of reference; and 6) idle periods of individual users. This paper reviews the essential elements required in the generation of a representative Web workload. It also addresses the technical challenges to satisfying this large set of simultaneous constraints on the properties of the reference stream, the solutions we adopted, and their associated accuracy. Finally, we present evidence that Surge exercises servers in a manner significantly different from other Web server benchmarks.

Recent measurements of network traffic have shown that self-similarity is an ubiquitous phenomenon present in both local area and wide area traffic traces. In previous work we have shown a simple, robust application layer causal mechanism of traffic self-similarity, namely, the transfer of files in a network system where the file size distributions are heavy-tailed. In this paper, we study the effect of scale-invariant burstiness on network performance when the functionality of the transport layer and the interaction of traffic sources sharing bounded network resources is incorporated.

First, we show that transport layer mechanisms are important factors in translating the application layer causality into link traffic self-similarity. Network performance as captured by throughput, packet loss rate, and packet retransmission rate degrades gradually with increased heavy-tailedness while queueing delay, response time, and fairness deteriorate more drastically. The degree to which heavy-tailedness affects self-similarity is determined by how well congestion control is able to shape a source traffic into an on-average constant output stream while conserving information.

Second, we show that increasing network resources such as link bandwidth and buffer capacity results in a superlinear improvement in performance. When large file transfers occur with nonnegligible probability, the incremental improvement in throughput achieved for large buffer sizes is accompanied by long queueing delays vis-a-vis the case when the file size distribution is not heavy-tailed. Buffer utilization continues to remain at a high level implying that further improvement in throughput is only achieved at the expense of a disproportionate increase in queueing delay. A similar trade-off relationship exists between queueing delay and packet loss rate, the curvature of the performance curve being highly sensitive to the degree of self-similarity.

Third, we investigate the effect of congestion control on network performance when subject to highly self-similar traffic conditions. We implement an open-loop congestion control using unreliable transport on top of UDP where the data stream is throttled at the source to achieve a fixed arrival rate. Decreasing the arrival rate results in a decline in packet loss rate whereas link utilization increases. In the context of reliable communication, we compare the performance of three versions of TCP---Reno, Tahoe, and Vegas---and we find that sophistication of control leads to improved performance that is preserved even under highly self-similar traffic conditions. The performance gain from Tahoe to Reno is relatively minor while the performance jump from TCP Reno to Vegas is more pronounced consistent with quantitative results reported elsewhere.

A number of recent measurements of local-area and wide-area traffic have indicated that such traffic shows variability at a wide range of scales --- self-similarity. However, a full understanding of how self-similarity arises in networks has not yet been developed. In this paper we examine a mechanism that may give rise to self-similar network traffic, and present some of its performance implications. The mechanism we examine is the transfer of files whose sizes are drawn from a heavy-tailed distribution, using a reliable and flow-controlled transport protocol. We examine these effects through detailed transport-level simulations of multiple simultaneous TCP streams in an internetwork.

First, we show that in a realistic client/server network environment (that is, one with bounded resources and coupling among traffic sources through competition for resources) the degree to which file sizes are heavy-tailed can directly determine the degree of traffic self-similarity. We show that this relationship is not significantly affected by changes in network configuration (bottleneck bandwidth and buffer capacity), the influence of cross-traffic, or the distribution of interarrival times.

Second, we show that properties of the transport layer play an important role in preserving this relationship. In particular, the reliable transmission and flow control mechanisms of TCP (Reno or Tahoe) serve to maintain the long-range dependence structure induced by heavy-tailed file size distributions. In contrast, if a non-flow-controlled and unreliable (UDP-like) transport protocol is used, the resulting traffic shows little self-similar characteristics: although still bursty at short time scales, it has little long-range dependence.

In exploring the relationship between file sizes, transport protocols, and self-similarity, we are also able to show some of the performance implications of self-similarity. We show the relationship between traffic self-similarity and network performance measures including packet loss rate, retransmission rate, and mean queue length at network switches. Increased self-similarity, as expected, results in degradation of performance; and mean queue lengths in particular exhibit drastic increases with increasing self-similarity. However, we note that packet loss and retransmission rates increase only fairly gradually with increasing traffic self-similarity, as long as a reliable, flow-controlled transport protocol is used.

Recently the notion of self-similarity has been shown to apply to wide-area and local-area network traffic. In this paper we examine the mechanisms that give rise to the self-similarity of network traffic. We present a hypothesized explanation for the possible self-similarity of traffic by using a particular subset of wide area traffic: traffic due to the World Wide Web (WWW). Using an extensive set of traces of actual user executions of NCSA Mosaic, reflecting over half a million requests for WWW documents, we examine the dependence structure of WWW traffic. While our measurements are not conclusive, we show evidence that WWW traffic exhibits behavior that is consistent with self-similar traffic models. Then we show that the self-similarity in such traffic can be explained based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, the effect of user "think time", and the superimposition of many such transfers in a local area network. To do this we rely on empirically measured distributions both from our traces and from data independently collected at over thirty WWW sites.

Recently the notion of self-similarity has been shown to apply to wide-area and local-area network traffic. In this paper we examine the mechanisms that give rise to self-similar network traffic. We present an explanation for traffic self-similarity by using a particular subset of wide area traffic: traffic due to the World Wide Web (WWW). Using an extensive set of traces of actual user executions of NCSA Mosaic, reflecting over half a million requests for WWW documents, we show evidence that WWW traffic is self-similar. Then we show that the self-similarity in such traffic can be explained based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, the effect of user ``think time'', and the superimposition of many such transfers in a local area network. To do this we rely on empirically measured distributions both from our traces and from data independently collected at over thirty WWW sites.

The explosion of WWW traffic necessitates an accurate picture of WWW use, and in particular requires a good understanding of client requests for WWW documents. To address this need, we have collected traces of actual executions of NCSA Mosaic, reflecting over half a million user requests for WWW documents. In this paper we describe the methods we used to collect our traces, and the formats of the collected data. Next, we present a descriptive statistical summary of the traces we collected, which identifies a number of trends and reference patterns in WWW use. In particular, we show that many characteristics of WWW use can be modelled using power-law distributions, including the distribution of document sizes, the popularity of documents as a function of size, the distribution of user requests for documents, and the number of references to documents as a function of their overall rank in popularity (Zipf's law). Finally, we show how the power-law distributions derived from our traces can be used to guide system designers interested in caching WWW documents.