5375789
Clustering Web content for efficient replication
Recently, there has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. We first compare uncooperative pulling of Web contents, used by commercial CDNs, with cooperative pushing. The latter can achieve user perceived performance comparable to the former scheme with only 4-5% of replication and update traffic. Therefore, we explore how to push content to CDN nodes efficiently. Using trace-driven simulation, we show that replicating content in units of URLs can yield 60-70% reduction in clients' latency, compared to replicating in units of Web sites. However, such a fine-grained replication is very expensive. We propose to replicate content in units of clusters, each containing objects which are likely to be requested by clients that are topologically close. We describe three clustering techniques, and use various topologies and several large Web server traces to evaluate their performance. Cluster-based replication achieves 40-60% improvement over per Web site based replication. By adjusting the number of clusters, we can smoothly trade off the management and computation cost for better client performance. We also explore incremental clusterings that adaptively add new documents to the existing content clusters. We examine both offline and online incremental clusterings. The offline clusterings yield close to the performance of the complete re-clustering at much lower overhead. The online incremental clustering and replication cut down the retrieval cost by 4.6-8 times compared to no replication and random replication, so it is especially useful for improving document availability during flash crowds.
887532
A Suite of Schemes for User-Level Network Diagnosis without Infrastructure
It is highly desirable and important for end users, with no special privileges, identify and pinpoint faults inside the network that degrade the performance of their applications. However, existing tools are inaccurate to infer the link-level loss rates and have large diagnosis granularity (in terms of the number of hops). To address these problems, we propose a suite of user-level diagnosis approaches in two categories: (1) only need to be deployed at the source and (2) deployed at both source and destination. For the former, we propose two fragmentation aided diagnosis approaches (FAD), Algebraic FAD and Opportunistic FAD, which uses IP fragmentation to enable accurate link-level loss rate inference. For the latter category, we propose Striped Probe Analysis (SPA) which significantly improves the diagnosis granularity over those of the source-only approaches. Internet experiments are applied to evaluate each individual schemes (including an improved version of the state-of-the-art tool, Tulip [1]) and various hybrid approaches. The results indicate that our approaches dramatically outperform existing work (especially for diagnosis granularity) and provide not only the best performance but also smooth tradeoff among deployment requirement, diagnosis accuracy and granularity.
10897641
Reversible sketches for efficient and accurate change detection over network data streams
Traffic anomalies such as failures and attacks are increasing in frequency and severity, and thus identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows and looks for heavy changes in traffic patterns (<i>e.g.</i>, volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is not scalable. The recently proposed sketch-based schemes [14] are among the very few that can detect heavy changes and anomalies over massive data streams at network traffic speeds. However, sketches do not preserve the key (<i>e.g.</i>, source IP address) of the flows. Hence, even if anomalies are detected, it is difficult to infer the culprit flows, making it a big practical hurdle for online deployment. Meanwhile, the number of keys is too large to record.
 To address this challenge, we propose efficient <i>reversible hashing</i> algorithms to infer the keys of culprit flows from sketches without storing any explicit key information. No extra memory or memory accesses are needed for recording the streaming data. Meanwhile, the heavy change detection daemon runs in the background with space complexity and computational time sublinear to the key space size. This short paper describes the conceptual framework of the reversible sketches, as well as some initial approaches for implementation. See [23] for the optimized algorithms in details. comment We further apply various emph IP-mangling algorithms and emph bucket classification methods to reduce the false positives and false negatives. Evaluated with netflow traffic traces of a large edge router, we demonstrate that the reverse hashing can quickly infer the keys of culprit flows even for many changes with high accuracy.
61999607
Towards unbiased end-to-end network diagnosis
Internet fault diagnosis is extremely important for end users, overlay network service providers (like Akamai [1]) and even Internet service providers (ISPs). However, because link-level properties cannot be uniquely determined from end-to-end measurements, the accuracy of existing statistical diagnosis approaches is subject to uncertainty from statistical assumptions about the network. In this paper, we propose a novel Least-biased End-to-end Network Diagnosis (in short, LEND) system for inferring link-level properties like loss rate. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from end-to-end measurements. We also design efficient algorithms to find all the MILSes and infer their loss rates for diagnosis. Our LEND system works for any network topology and for both directed and undirected properties, and incrementally adapts to network topology and property changes. It gives highly accurate estimates of the loss rates of MILSes, as indicated by both extensive simulations and Internet experiments. Furthermore, we demonstrate that such diagnosis can be achieved with fine granularity and in near real-time even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.
166109
End-to-End Inference of Router Packet Forwarding Priority
Packet forwarding prioritization (PFP) in routers is one of the mechanisms commonly available to network administrators. PFP can have a significant impact on the performance of applications, the accuracy of measurement tools' results and the effectiveness of network troubleshooting procedures. Despite their potential impact, no information on PFP settings is readily available to end users. In this paper, we present an end-to-end approach for packet forwarding priority inference and its associated tool, POPI. This is the first attempt to infer router packet-forwarding priority through end-to-end measurement. Our POPI tool enables users to discover such network policies through the monitoring and rank classification of loss rates for different packet types. We validated our approach via statistical analysis, simulation, and wide-area experimentation in PlanetLab. As part of our wide-area experiments, we employed POPI to analyze 156 random paths across 162 PlanetLab nodes. We discovered 15 paths flagged with multiple priorities, 13 of which were further validated through hop-by-hop loss rates measurements. In addition, we surveyed all related network operators and received responses for about half of them confirming our inferences.
10399949
Quantifying Network Denial of Service: A Location Service Case Study
Network Denial of Service (DoS) attacks are increasing in frequency, severity and sophistication, making it desirable to measure the resilience of systems to DoS attacks. In this paper, we propose a simulation-based methodology and apply it to attacks on object location services such as DNS. Our results allow us to contrast the DoS resilience of three distinct architectures for object location.
10348131
An Infrastructure for Web Services Migration for Real-Time Applications
Service-oriented architecture (SOA) is a highly promising technology for software development. It can greatly reduce the development time and cost and achieve system agility. Web service is the current practice for realizing SOA. Due to the nature of widely distributed Web service providers, the service performance could be impacted when the network traffic is congested. There are methods, such as communication cost based service selection strategies, developed to cope with the problem. In this paper, we propose a complementing technology, migratable Web services, to overcome the performance problems for real-time applications. A service can be implemented by multiple light weighted Web services and some of them can be migrated to strategic sites to minimize the communication delays so the real-time requirements can be met. We have designed an infrastructure to support Web service migration and execution. Also, appropriate decision mechanism, which decides whether a Web service should be migrated and where to send it to, is the key for major performance gains. We use genetic algorithm to efficiently make the best migration decisions. Experimental studies show that the approach can achieve significant performance improvement
1548803
I/O-efficient techniques for computing pagerank
Over the last few years, most major search engines have integrated link-based ranking techniques in order to provide more accurate search results. One widely known approach is the Pagerank technique, which forms the basis of the Google ranking scheme, and which assigns a global importance measure to each page based on the importance of other pages pointing to it. The main advantage of the Pagerank measure is that it is independent of the query posed by a user; this means that it can be precomputed and then used to optimize the layout of the inverted index structure accordingly. However, computing the Pagerank measure requires implementing an iterative process on a massive graph corresponding to billions of web pages and hyperlinks.In this paper, we study I/O-efficient techniques to perform this iterative computation. We derive two algorithms for Pagerank based on techniques proposed for out-of-core graph algorithms, and compare them to two existing algorithms proposed by Haveliwala. We also consider the implementation of a recently proposed topic-sensitive version of Pagerank. Our experimental results show that for very large data sets, significant improvements over previous results can be achieved on machines with moderate amounts of memory. On the other hand, at most minor improvements are possible on data sets that are only moderately larger than memory, which is the case in many practical scenarios.
17883721
Classification of self-consumable highlights for soccer video summaries
An effective scheme for soccer summarization is significant to improve the usage of this massively growing video data. The paper presents an extension to our recent work which proposed a framework to integrate highlights into play-breaks to construct more complete soccer summaries. The current focus is to demonstrate the benefits of detecting some specific audio-visual features during play-break sequences in order to classify highlights contained within them. The main purpose is to generate summaries which are self-consumable individually. To support this framework, the algorithms for shot classification and detection of near-goal and slow-motion replay scenes is described. The results of our experiment using 5 soccer videos (20 minutes each) show the performance and reliability of our framework
45083530
Improving backpropagation learning under limited precision
Abstract Most of the work to date on learning in neural networks assumes the availability of unlimited precision for implementing weights and the neural transfer functions. Recently some studies have investigated the effects of limited precision on the learning and generalisation performance. In this paper, we identify the causes of performance degradation due to limited precision and propose a novel algorithm to improve the performance of Backpropagation.
20308502
Object signatures for supporting efficient navigation in object-oriented databases
Most methods that have been proposed to improve query processing in object-oriented databases are designed for the aggregation hierarchy. Although the structure of the generalization hierarchy is similar to the aggregation hierarchy, techniques developed for the aggregation hierarchy cannot fully use the characteristics of the generalization hierarchy to improve performance. We devise a new object signature for the generalization hierarchy. The object signature consists of two parts: a reference signature and a structure signature. The former can be used to eliminate objects that do not match the nested predicates specified in the query, and the latter can be used to eliminate objects that do not belong to the target classes. We propose some processing methods using the object signatures for queries that involve generalization hierarchies. In addition, we define cost models of the object signature and then compare the performance of the traditional query processing method with the object signature method. The results show that using the object signatures can effectively reduce the number of disk accesses in a query.