15953152
Understanding network delay changes caused by routing events
Network delays and delay variations are two of the most important network performance metrics directly impacting real-time applications such as voice over IP and time-critical financial transactions. This importance is illustrated by past work on understanding the delay constancy of Internet paths and recent work on predicting network delays using virtual coordinate systems. Merely understanding currently observed delays is insufficient, as network performance can degrade not only due to traffic variability but also as a result of routing changes. Unfortunately this latter effect so far has been ignored in understanding and predicting delay related performance metrics of Internet paths. Our work is the first to address this short coming by systematically analyzing changes in network delays and jitter of a diverse and comprehensive set of Internet paths. Using empirical measurements, we illustrate that routing changes can result in roundtrip delay increase of converged paths by more than 1 second. Surprisingly, intradomain routing changes can also cause such large delay increase.
 Given these observations, we develop a framework to analyze in detail the impact of routing changes on network delays between end-hosts. Using topology information and properties associated with routing changes, we explain the causes for observed delay fluctuations and more importantly identify routing changes that lead to predictable effects on delay-related metrics. Using our framework, we study the predictability of delay and jitter changes in response to both passively observed interdomain and actively measured intradomain routing changes.
463081
Topology-Aware Routing in Structured Peer-to-Peer Overlay Networks
Structured peer-to-peer (p2p) overlay networks like CAN, Chord, Pastry and Tapestry offer a novel platform for a variety of scalable and decentralized distributed applications. They provide efficient and fault-tolerant routing, object location and load balancing within a self-organizing overlay network. One important aspect of these systems is how they exploit network proximity in the underlying Internet. We present a study of topology-aware routing approaches in p2p overlays, identify proximity neigbor selection as the most promising technique, and present an improved design in Pastry. Results obtained via analysis and via simulation of two large-scale topology models indicate that it is possible to efficiently exploit network proximity in self-organizing p2p substrates. Proximity neighbor selection incurs only a modest additional overhead for organizing and maintaining the overlay network. The resulting locality properties improve application performance and reduce network usage in the Internet substantially. Finally, we show that the impact of proximity neighbor selection on the load balancing in the p2p overlay is minimal.
43789567
A Self-Organizing Flock of Condors
1998178
A Hierarchical Approach to Internet Distance Prediction
Internet distance prediction gives pair-wise latency information with limited measurements. Recent studies have revealed that the quality of existing prediction mechanisms from the application perspective is short of satisfactory. In this paper, we explore the root causes and remedies for this problem. Our experience with different landmark selection schemes shows that although selecting nearby landmarks can increase the prediction accuracy for short distances, it can cause the prediction accuracy for longer distances to degrade. Such uneven prediction quality significantly impacts application performance. Instead of trying to select the landmark nodes in some "intelligent" fashion, we propose a hierarchical prediction approach with straightforward landmark selection. Hierarchical prediction utilizes multiple coordinate sets at multiple distance scales, with the "right" scale being chosen for prediction each time. Experiments with Internet measurement datasets show that this hierarchical approach is extremely promising for increasing the accuracy of network distance prediction.
481550
Improving Fine-Grained Irregular Shared-Memory Benchmarks by Data Reordering
We demonstrate that data reordering can substantially improve the performance of fine-grained irregular shared-memory benchmarks, on both hardware and software shared-memory systems. In particular, we evaluate two distinct data reordering techniques that seek to co-locate in memory objects that are in close proximity in the physical system modeled by the computation. The effects of these techniques are increased spatial locality and reduced false sharing. We evaluate the effectiveness of the data reordering techniques on a set of five irregular applications from SPLASH-2 and Chaos. We implement both techniques in a small library, allowing us to enable them in an application by adding less than 10 lines of code. Our results on one hardware and two software shared-memory systems show that, with data reordering during initialization, the performance of these applications is improved by 12%-99% on the Origin 2000, 30%-366% on TreadMarks, and 14%-269% on HLRC.
1334946
Program counter based techniques for dynamic power management
Reducing energy consumption has become one of the major challenges in designing future computing systems. We propose a novel idea of using program counters to predict I/O activities in the operating system. We present a complete design of program-counter access predictor (PCAP) that dynamically learns the access patterns of applications and predicts when an I/O device can be shut down to save energy. PCAP uses path-based correlation to observe a particular sequence of program counters leading to each idle period, and predicts future occurrences of that idle period. PCAP differs from previously proposed shutdown predictors in its ability to: (1) correlate I/O operations to particular behavior of the applications and users, (2) carry prediction information across multiple executions of the applications, and (3) attain better energy savings while incurring low mispredictions.
12662534
A Framework for Managing Emergent Transmissions in IP Networks
Theories and experiments have shown that average end-to-end delay of flows increases and TCP becomes inefficient and instable during network congestion period, regardless of which queue management and packet scheduling mechanism are being applied. Despite the concerns of network congestion problem have raised by the implementations of various per-flow based transmission protocols and queue policies on routers, there are still very few efforts to assess the feasibility of modifying network infrastructure to accommodate these new algorithms. It is practically impossible to reach the performance that claimed by the per-flow based algorithms, while updating routers is very costly and beyond the control of every individual network domain. In this paper, we present an application layer reliable multi-connection best effort framework which provides quality of service (QoS) for emergent communications with no or very few changes of the existing network infrastructure. Performance of our approach and other several existing algorithms is studied by using the network simulator NS2.
2595430
A new approach to intranet search based on information extraction
This paper is concerned with 'intranet search'. By intranet search, we mean searching for information on an intranet within an organization. We have found that search needs on an intranet can be categorized into types, through an analysis of survey results and an analysis of search log data. The types include searching for definitions, persons, experts, and homepages. Traditional information retrieval only focuses on search of relevant documents, but not on search of special types of information. We propose a new approach to intranet search in which we search for information in each of the special types, in addition to the traditional relevance search. Information extraction technologies can play key roles in such kind of 'search by type' approach, because we must first extract from the documents the necessary information in each type. We have developed an intranet search system called 'Information Desk'. In the system, we try to address the most important types of search first - finding term definitions, homepages of groups or topics, employees' personal information and experts on topics. For each type of search, we use information extraction technologies to extract, fuse, and summarize information in advance. The system is in operation on the intranet of Microsoft and receives accesses from about 500 employees per month. Feedbacks from users and system logs show that users consider the approach useful and the system can really help people to find information. This paper describes the architecture, features, component technologies, and evaluation results of the system.
15964904
JPEG2000 Image Adaptation for MPEG-21 Digital Items
MPEG-21 user cases bring out a scenario of Universal Multimedia Access which is becoming the reality: people use different devices such as desktop PC, personal digital assistant as well as smartphone to access multimedia information. Viewing images on mobile devices is more and more popular than before. However, due to the screen size limitation, the experience of viewing large image on small screen devices is awkward. In this paper, an enhanced JPEG2000 image adaptation system is proposed for MPEG-21 digital item adaptation. The image is adapted considering both visual attentive region(s) of image and terminal screen size. Through the subjective testing, the system has been approved to be a solution of efficiently displaying large images in different devices.
10956379
DraXRouter: global routing in X-architecture with dynamic resource assignment
In recent years, the X-architecture is introduced to obtain better performance for integrated circuit physical design. This paper reformulates the global routing problem in X-architecture under the liquid routing model. Then, a dynamic resource assignment (Dra) method is presented to reduce potential vias. At last, a global router called DraXRouter, is designed, in which we adopt a dynamic-tabulist-based tree construction algorithm and a stochastic optimization strategy to gain high quality routing solution. Tested on ISPD'98 benchmarks, DraXRouter achieves better routing performance compared with two recent global routers.
834526
Efficient 3D reconstruction for face recognition
Face recognition with variant pose, illumination and expression (PIE) is a challenging problem. In this paper, we propose an analysis-by-synthesis framework for face recognition with variant PIE. First, an efficient two-dimensional (2D)-to-three-dimensional (3D) integrated face reconstruction approach is introduced to reconstruct a personalized 3D face model from a single frontal face image with neutral expression and normal illumination. Then, realistic virtual faces with different PIE are synthesized based on the personalized 3D face to characterize the face subspace. Finally, face recognition is conducted based on these representative virtual faces. Compared with other related work, this framework has following advantages: (1) only one single frontal face is required for face recognition, which avoids the burdensome enrollment work; (2) the synthesized face samples provide the capability to conduct recognition under difficult conditions like complex PIE; and (3) compared with other 3D reconstruction approaches, our proposed 2D-to-3D integrated face reconstruction approach is fully automatic and more efficient. The extensive experimental results show that the synthesized virtual faces significantly improve the accuracy of face recognition with changing PIE.