waashk/dblp huggingface dataset:
automatic optimization of parallel dataflow programs. large-scale parallel dataflow systems, e.g., dryad and map-reduce, have attracted significant attention recently. high-level dataflow languages such as pig latin and sawzall are being layered on top of these systems, to enable faster program development and more maintainable code. these languages engender greater transparency in program structure, and open up opportunities for automatic optimization. this paper proposes a set of optimization strategies for this context, drawing on and extending techniques from the database community.
measurement and analysis of large-scale network file system workloads. in this paper we present the analysis of two large-scale network file system workloads. we measured cifs traffic for two enterprise-class file servers deployed in the netapp data center for a three month period. one file server was used by marketing, sales, and finance departments and the other by the engineering department. together these systems represent over 22tb of storage used by over 1500 employees, making this the first ever large-scale study of the cifs protocol. we analyzed how our network file system workloads compared to those of previous file system trace studies and took an in-depth look at access, usage, and sharing patterns. we found that our workloads were quite different from those previously studied; for example, our analysis found increased read-write file access patterns, decreased read-write ratios, more randomfile access, and longer file lifetimes. in addition, we found a number of interesting properties regarding file sharing, file re-use, and the access patterns of file types and users, showing that modern file system workload has changed in the past 5-10 years. this change in workload characteristics has implications on the future design of network file systems, which we describe in the paper.
conflict-aware scheduling for dynamic content applications. we present a new lazy replication technique, suitable for scaling the back-end database of a dynamic content site using a cluster of commodity computers. our technique, called conflict-aware scheduling, provides both throughput scaling and 1-copy serializability. it has generally been believed that this combination is hard to achieve through replication because of the growth of the number of conflicts. we take advantage of the presence in a database cluster of a scheduler through which all incoming requests pass. we require that transactions specify the tables that they access at the beginning of the transaction. using that information, a conflictaware scheduler relies on a sequence-numbering scheme to implement 1-copy serializability, and directs incoming queries in such a way that the number of conflicts is reduced. we evaluate conflict-aware scheduling using the tpcw e-commerce benchmark. for small clusters of up to eight database replicas, our evaluation is performed through measurements of a web site implementing the tpc-w specification. we use simulation to extend our measurement results to larger clusters, faster database engines, and lower conflict rates. our results show that conflict-awareness brings considerable benefits compared to both eager and conflict-oblivious lazy replication for a large range of cluster sizes, database speeds, and conflict rates. conflict-aware scheduling provides near-linear throughput scaling up to a large number of database replicas for the browsing and shopping workloads of tpc-w. for the write-heavy ordering workload, throughput scales, but only to a smaller number of replicas.
using fault injection and modeling to evaluate the performability of cluster-based services. we propose a two-phase methodology for quantifying the performability (performance and availability) of cluster-based internet services. in the first phase, evaluators use a fault-injection infrastructure to measure the impact of faults on the server's performance. in the second phase, evaluators use an analytical model to combine an expected fault load with measurements from the first phase to assess the server's performability. using this model, evaluators can study the server's sensitivity to different design decisions, fault rates, and environmental factors. to demonstrate our methodology, we study the performability of 4 versions of the press web server against 5 classes of faults, quantifying the effects of different design decisions on performance and availability. finally, to further show the utility of our model, we also quantify the impact of two hypothetical changes, reduced human operator response time and the use of raids.
mining longest repeating subsequences to predict world wide web surfing. modeling and predicting user surfing paths involves tradeoffs between model complexity and predictive accuracy. in this paper we explore predictive modeling techniques that attempt to reduce model complexity while retaining predictive accuracy. we show that compared to various markov models, longest repeating subsequence models are able to significantly reduce model size while retaining the ability to make accurate predictions. in addition, sharp increases in the overall predictive capabilities of these models are achievable by modest increases to the number of predictions made.
mayday: distributed filtering for internet services. mayday is an architecture that combines overlay networks with lightweight packet filtering to defend against denial of service attacks. the overlay nodes perform client authentication and protocol verification, and then relay the requests to a protected server. the server is protected from outside attack by simple packet filtering rules that can be efficiently deployed even in backbone routers. mayday generalizes earlier work on secure overlay services. mayday improves upon this prior work by separating the overlay routing and the filtering, and providing a more powerful set of choices for each. through this generalization, mayday supports several different schemes that provide different balances of security and performance, continuum, and supports mechanisms that achieve better security or better performance than earlier systems. to evaluate both mayday and previous work, we also present several practical attacks, two of them novel, that are effective against filtering-based systems.
active names: flexible location and transport of wide-area resources. in this paper, we explore flexible name resolution as a way of supporting extensibility for wide-area distributed services. our approach, called active names, maps names to a chain of mobile programs that can customize how a service is located and how its results are transformed and transported back to the client. to illustrate the properties of our system, we implement prototypes of server selection based on end-to-end performance measurements, location-independent data transformation, and caching of composable active objects and demonstrate up to a five-fold performance improvement to end users. we show how these new services are developed, composed, and secured in our framework. finally, we develop a set of algorithms to control how mobile active name programs are mapped onto available wide-area resources to optimize performance and availability.
a user's and programmer's view of the new javascript security model. in this paper we introduce a new security model for javascript in mozilla, as well as its programming interface. we present important concepts via examples from electronic commerce applications. we also describe our experience of implementing the model in the publicly available mozilla source code. this model is likely to be integrated into navigator 5.0, which, as of this writing, is scheduled to be released in late fall, 1999.
secure public internet access handler (spinach). this paper describes a system that controls access to computer networks through publicly accessible lans, enabling network administrators to authorize users either on a permanent or occasional basis. the system has been designed with minimal assumptions about the software and hardware required of users, and requires very little specialized equipment within the network infrastructure. we enumerate the requirements for such a system, describe the design and implementation of the system, and note tradeoffs between security and efficiency.
using full reference history for efficient document replacement in web caches. with the increase in popularity of the world wide web, the research community has recently seen a proliferation of web caching algorithms. this paper presents a new such algorithm, that is efficient and robust, called least unified-value (luv). luv evaluates a web document based on its cost normalized by the likelihood of it being re-referenced. this results in a normalized assessment of the contribution to the value of a document, leading to a fair replacement policy. luv can conform to arbitrary cost functions of web documents, so it can optimize any particular performance measure of interest, such as the hit rate, the byte hit rate, or the delay-savings ratio. unlike most existing algorithms, luv exploits complete reference history of documents, in terms of reference frequency and recency, to estimate the likelihood of being re-referenced. nevertheless, luv allows for an efficient implementation in both space and time complexities. the space needed to maintain the reference history of a document is only a few bytes and furthermore, the time complexity of the algorithm is o(log2n), where n is the number of documents in the cache. trace-driven simulations show that the luv algorithm outperforms existing algorithms for various performance measures for a wide range of cache configurations.
sase: implementation of a compressed text search engine. keyword based search engines are the basic building block of text retrieval systems. higher level systems like content sensitive search engines and knowledge-based systems still rely on keyword search as the underlying text retrieval mechanism. with the explosive growth in content, internet and intranet information repositories require efficient mechanisms to store as well as index data. in this paper we discuss the implementation of the shrink and search engine (sase) framework which unites text compression and indexing to maximize keyword search performance while reducing storage cost. sase features the novel capability of being able to directly search through compressed text without explicit decompression. the implementation includes a search server architecture, which can be accessed from a java front-end to perform keyword search on the internet. the performance results show that the compression efficiency of sase is within 7-17% of gzip one of the best lossless compression schemes. the sum of the compressed file size and the inverted indices is only between 55-76% of the original database while the search performance is comparable to a fully inverted index. the framework allows a flexible trade-off between search performance and storage requirements for the search indices.
measuring the capacity of a web server. the widespread use of the world wide web and related applications places interesting performance demands on network servers. the ability to measure the effect of these demands is important for tuning and optimizing the various software components that make up a web server. to measure these effects, it is necessary to generate realistic http client requests. unfortunately, accurate generation of such traffic in a testbed of limited scope is not trivial. in particular, the commonly used approach is unable to generate client request-rates that exceed the capacity of the server being tested even for short periods of time. this paper examines pitfalls that one encounters when measuring web server capacity using a synthetic workload. we propose and evaluate a new method for web traffic generation that can generate bursty traffic, with peak loads that exceed the capacity of the server. finally, we use the proposed method to measure the performance of a web server.
adaptive overload control for busy internet servers. as internet services become more popular and pervasive, a critical problem that arises is managing the performance of services under extreme overload. this paper presents a set of techniques for managing overload in complex, dynamic internet services. these techniques are based on an adaptive admission control mechanism that attempts to bound the 90th-percentile response time of requests flowing through the service. this is accomplished by internally monitoring the performance of the service, which is decomposed into a set of event-driven stages connected with request queues. by controlling the rate at which each stage admits requests, the service can perform focused overload management, for example, by filtering only those requests that lead to resource bottlenecks. we present two extensions of this basic controller that provide class-based service differentiation as well as application-specific service degradation. we evaluate these mechanisms using a complex web-based e-mail service that is subjected to a realistic user load, as well as a simpler web server benchmark.
providing dynamic and customizable caching policies. web caching has emerged as one solution for improving client latency on the web. cache effectiveness depends on the policies used to route requests to other caches and servers, to maintain up-to-date web objects and to remove objects from the cache. traditional caches apply one set of policies, which determines the efficiency as well as the effectiveness of the caches. this set of policies often does not exploit the diversity inherent in different web objects, caches and clients. policies that do exploit this diversity result in convoluted caching policies that attempt to combine multiple policies and guess at the unknown characteristics of web objects, caches and clients. in this paper, we present an extensible caching infrastructure in which cache administrators, servers, and end users can customize how web objects are cached, replaced, and kept consistent. the infrastructure includes a domain-specific language, cachel, for defining customizable caching policies that can be changed dynamically. analysis of our prototype, polisquid, shows the benefits of the infrastructure for variable coherency policies, localized removal policies, and early removal of objects from servers.
organization-based analysis of web-object sharing and caching. performance-enhancing mechanisms in the world wide web primarily exploit repeated requests to web documents by multiple clients. however, little is known about patterns of shared document access, particularly from diverse client populations. the principal goal of this paper is to examine the sharing of web documents from an organizational point of view. an organizational analysis of sharing is important, because caching is often performed on an organizational basis; i.e., proxies are typically placed in front of large and small companies, universities, departments, and so on. unfortunately, simultaneous multi-organizational traces do not currently exist and are difficult to obtain in practice. the goal of this paper is to explore the extent of document sharing (1) among clients within single organizations, and (2) among clients across different organizations. to perform the study, we use a large university as a model of a diverse collection of organizations. within our university, we have traced all external web requests and responses, anonymizing the data but preserving organizational membership information. this permits us to analyze both inter-and intra-organization document sharing and to test whether organization membership is significant. as well, we characterize a number of parameters of our data, including basic object characteristics, object cacheability, and server distributions.
cost-aware www proxy caching algorithms. web caches can not only reduce network traffic and downloading latency, but can also affect the distribution of web traffic over the network through cost-aware caching. this paper introduces greedydual-size, which incorporates locality with cost and size concerns in a simple and non-parameterized fashion for high performance. trace-driven simulations show that with the appropriate cost definition, greedydual-size outperforms existing web cache replacement algorithms in many aspects, including hit ratios, latency reduction and network cost reduction. in addition, greedydual-size can potentially improve the performance of main-memory caching of web documents.
efficient support for content-based routing in web server clusters. clustered server architectures have been employed for many years on the internet as a way to increase performance, reliability and scalability in the presence of the internet's explosive growth. a routing mechanism for mapping requests to individual servers within cluster is at the heart of any server clustering techniques. in this paper, we first analyze the deficiencies of existing request-routing approaches. based on these observations, we argue that the request routing mechanism in a cluster-based server should factor in the content of a request in making decisions. thus, we designed and implemented a new mechanism to efficiently support content-aware routing in web server clusters. with this mechanism, we also built in a number of sophisticated content-aware intelligence for making routing decision. performance evaluation on a prototype implementation demonstrates substantial performance improvements over contemporary routing schemes. the proposed mechanism can also enable many new capabilities in cluster-based servers, such as sophisticated load balancing, differentiated service, special content deployment, session integrity, etc.
hierarchical cache consistency in a wan. this paper explores ways to provide improved consistency for internet applications that scale to millions of clients. we make four contributions. first, we identify how workloads affect the scalability of cache consistency algorithms. second, we define two primitive mechanisms, split and join, for growing and shrinking consistency hierarchies, and we present a simple mechanism for implementing them. third, we describe and evaluate policies for using split and join to address the fault tolerance and performance challenges of consistency hierarchies. fourth, using synthetic workload and trace-based simulation, we compare various algorithms for maintaining strong consistency in a range of hierarchy configurations. our results indicate that a promising configuration for providing strong consistency in a wan is a two-level consistency hierarchy where servers and proxies work to maintain consistency for data cached at clients. specifically, by adapting to clients' access patterns, two-level hierarchies reduce the read latency for demanding workloads without introducing excessive overhead for nondemanding workloads. also, they can improve scalability by orders of magnitude. furthermore, this configuration is easy to deploy by augmenting proxies, and it allows invalidation messages to traverse firewalls.
jpeg compression metric as a quality-aware image transcoding. transcoding is becoming a preferred technique to tailor multimedia objects for delivery across variable network bandwidth and for storage and display on the destination device. this paper presents techniques to quantify the quality-versus-size tradeoff characteristics for transcoding jpeg images. we analyze the characteristics of images available in typical web sites and explore how we can perform informed transcoding using the jpeg compression metric. we present the effects of this transcoding on the image storage size and image information quality. we also present ways of predicting the computational cost as well as potential space benefits achieved by the transcoding. these results are useful in any system that uses transcoding to reduce access latencies, increase effective storage space as well as reduce access costs.
anypoint: extensible transport switching on the edge. anypoint is a new model for one-to-many communication with ensemble sites-aggregations of end nodes that appear to the external internet as a unified site. policies for routing any-point traffic are defined by application-layer plugins residing in extensible routers at the ensemble edge. anypoint's switching functions operate at the transport layer at the granularity of transport frames. communication over an anypoint connection preserves end-to-end transport rate control, partial ordering, and reliable delivery. experimental results from a host-based anypoint prototype and an nfs storage router application show that anypoint is a powerful technique for virtualizing and extending cluster services, and is amenable to implementation in high-speed switches. the anypoint prototype improves storage router throughput by 29% relative to a tcp proxy.
cha-cha: a system for organizing intranet search results. although search over world wide web pages has recently received much academic and commercial attention, surprisingly little research has been done on how to search the web pages within large, diverse intranets. intranets contain the information associated with the internal workings of an organization. a standard search engine retrieves web pages that fall within a widely diverse range of information contexts, but presents these results uniformly, in a ranked list. as an alternative, the cha-cha system organizes web search results in such a way as to reflect the underlying structure of the intranet. in our approach, an "outline" or "table of contents" is created by first recording the shortest paths in hyperlinks from root pages to every page within the web intranet. after the user issues a query, these shortest paths are dynamically combined to form a hierarchical outline of the context in which the search results occur. the system is designed to be helpful for users with a wide range of computer skills. preliminary user study and survey results suggest that some users find the resulting structure more helpful than the standard retrieval results display for intranet search.
fastreplica: efficient large file distribution within content delivery networks. in this work, we consider a large-scale distributed network of servers and a problem of content distribution across it. we propose a novel algorithm, called fastreplica, for an efficient and reliable replication of large files in the internet environment. there are a few basic ideas exploited in fastreplica. in order to replicate a large file among n nodes (n is in the range of 10-30 nodes), the original file is partitioned into n subfiles of equal size and each subfile is transferred to a different node in the group. after that, each node propagates its subfile to the remaining nodes in the group. thus instead of the typical replication of an entire file to n nodes by using n internet paths, connecting the original node to the replication group, fastreplica exploits n × n internet paths within the replication group where each path is used for transferring 1/n -th of the file. we design a scalable and reliable fastreplica algorithm which can be used for replication of large files to a large group of nodes. the new method is simple and inexpensive. it does not require any changes or modifications to the existing internet infrastructure, and at the same time, it significantly reduces the file replication time as we demonstrate through experiments on a prototype implementation of fastreplica in a wide-area testbed.