SMARTech Collection: College of Computing Technical Reports

Accord: Middleware Support for Contextual, Ubiquitous Data Management on User Devices

Sat, 29 Oct 2005 22:58:59 GMT

Title: Accord: Middleware Support for Contextual, Ubiquitous Data Management on User Devices

Authors: Cooper, Brian F.; Isbell, Charles Lee, Jr.; Pierce, Jeffrey S.; Roberts, David L.; Bhat, Sooraj

Abstract: People increasingly use a diverse array of computational devices, including desktop PCs, one or more laptops, a cell phone, a PDA, tablet PCs, digital music players, automobile computers, and so on. We present Accord, a middleware system we have implemented to manage user data across all of these devices. Accord emulates an ideal abstraction we call a user data-space: a virtual space in which user files exist independent of any particular physical device. Users put files into the space with whatever device is convenient, and later access those files using any of their devices. This abstraction is difficult to implement, and requires Accord to predict when a file will be needed and on which device. We describe two mechanisms the middleware uses to support such predictions: an object graph, which records contextual and statistical information about file objects, and a file transfer planner, which uses predictions to determine how to efficiently move files between devices despite connectivity, bandwidth and storage constraints. Predictions can be constructed using simple usage statistics, or from more complex machinelearned models of user activities. We also present experimental results demonstrating the effectiveness of our system.

A Decision-Theoretic Approach to File Consistency in Constrained Peer-to-Peer Device Networks

Sat, 29 Oct 2005 22:58:59 GMT

Title: A Decision-Theoretic Approach to File Consistency in Constrained Peer-to-Peer Device Networks

Authors: Roberts, David L.; Bhat, Sooraj; Isbell, Charles Lee, Jr.; Cooper, Brian F.; Pierce, Jeffrey S.

Abstract: As users interact with an increasing array of personal computing devices, maintaining consistency of data across those devices becomes significantly more difficult. Typical solutions assume either access to centralized servers, continual connectivity, or unbounded storage and CPU capacity. In practice, users own devices with widely varying processing and storage capabilities that use intermittent or sparsely-connected networks and incur (often asymmetric) transfer costs. We identify the conditions that enable the seamless management of a user's data across devices and present a multi-agent system built upon a decision-theoretic approach to constructing and executing multiple plans to achieve consistency in a peer-to-peer, partially observable, non-deterministic environment. We analyze the performance of these plans in comparison to a standard epidemic replication algorithm used in many database consistency applications.

Scalable and Efficient Data Streaming Algorithms for Detecting Common Content in Internet Traffic

Sat, 29 Oct 2005 22:58:59 GMT

Title: Scalable and Efficient Data Streaming Algorithms for Detecting Common Content in Internet Traffic

Authors: Sung, Min-Ho; Kumar, Abhishek; Li, Li (Erran); Wang, Jia; Xu, Jun

Abstract: Recent research on data streaming algorithms has provided powerful tools to efficiently monitor various characteristics of traffic passing through a single network link or node. However, it is often desirable to perform data streaming analysis on the traffic aggregated over hundreds or even thousands of links/nodes, which will provide network operators with a holistic view of the network operation. Shipping raw traffic data to a centralized location (i.e., "raw aggregation") for streaming analysis is clearly not a feasible approach for a large network. In this paper, we propose a set of novel Distributed Collaborative Streaming (DCS) algorithms that allow scalable and efficient monitoring of aggregated traffic without the need for raw aggregation. Our algorithms target the specific network monitoring problem of finding common content in the Internet traffic traversing several nodes/links, which has applications in network-wide intrusion detection, early warning for fast propagating worms, and detection of hot objects and spam traffic. We evaluate our algorithms through extensive simulations and experiments on traffic traces collected from a tier-1 ISP. The experimental results demonstrate that our algorithms can effectively detect common content in the traffic traversing across a large network.

RouteSeer: Topological Placement of Nodes in Service Overlays

Sat, 29 Oct 2005 22:58:59 GMT

Title: RouteSeer: Topological Placement of Nodes in Service Overlays

Authors: Srinivasan, Sridhar; Zegura, Ellen W.

Abstract: Overlay networks are being increasingly used to deploy new services on the Internet. As opposed to peer-to-peer overlays, these infrastructure or service overlays offer the opportunity of placing the overlay nodes and selecting the links between them. There has been very little work done in the area of node placement in overlay network design. In this work, our objective is to study the overlay node placement problem based on a specific performance objective, namely, overlay link resiliency. An overlay link is called resilient if there exists an intermediate overlay node through which a connection can be established even if there is a failure in the underlying network links between the overlay nodes. In this paper, we propose an algorithm, called RouteSeer, to solve the overlay node placement problem. We split the problem into two parts, placing some overlay nodes called client proxies “close” to the clients of the overlay service and placing intermediate nodes to provide resilient paths between the client proxies. RouteSeer heuristically places the intermediate overlay nodes by only examining the routing tables at the client proxies and does not require global topology information. In our simulations and experiments on the Internet, we show that RouteSeer can improve on previous schemes by 50-100%.