Modern storage systems orchestrate a group of disks to achieve their performance and reliability goals. Even though such systems are designed to withstand the failure of individual disks, failure of multiple disks poses a unique set of challenges. We empirically investigate disk failure data from a large number of production systems, specifically focusing on the impact of disk failures on RAID storage systems. Our data covers about one million SATA disks from six disk models for periods up to 5 years. We show how observed disk failures weaken the protection provided by RAID. The count ofreallocated sectorscorrelates strongly with impending failures. With these findings we designed RAIDShield, which consists of two components. First, we have built and evaluated an active defense mechanism that monitors the health of each disk and replaces those that are predicted to fail imminently. This proactive protection has been incorporated into our product and is observed to eliminate 88% of triple disk errors, which are 80% of all RAID failures. Second, we have designed and simulated a method of using the joint failure probability to quantify and predict how likely a RAID group is to face multiple simultaneous disk failures, which can identify disks that collectively represent a risk of failure even when no individual disk is flagged in isolation. We find in simulation that RAID-level analysis can effectively identify most vulnerable RAID-6 systems, improving the coverage to 98% of triple errors. We conclude with discussions of operational considerations in deploying RAIDShieldmore broadly and new directions in the analysis of disk errors. One interesting approach is to combine multiple metrics, allowing the values of different indicators to be used for predictions. Using newer field data that reports an additional metric,medium errors, we find that the relative efficacy of reallocated sectors and medium errors varies across disk models, offering an additional way to predict failures.

Medical images are captured in a 16-bit high-resolution grayscale format and are large, frequently reaching MBs per image and PBs for the archive. Regulatory compliance requirements make de-ploying new full image compression techniques difficult. Instead of forcing applications and end users to deal with the deployment complexity, we show that image data can be effectively and transparently compressed by the storage infrastructure. We analyzed our MICA compressor performance using five million publicly available medical images (> 2.2 TB) in three different image formats from eight sources. With 8KB blocks, we achieved 13% better compression, 10% better compression throughput and 782% better uncompression throughput than JPEG-LS. MICA also offered some compression for non-medical data that was incidentally stored in the same storage system.

DisplayCast is a many to many Intranet screen sharing system. Its screen capture mechanism creates a sequence of pixmap images of the screen updates. Prior systems that used a similar approach were designed to operate over constrained wide-area networks and did not exploit the Intranet network conditions to achieve high capture rates. First we empirically analyzed the screen contents for a variety of scenarios. We showed that screen updates were sporadic with long periods of inactivity. When active, screens were updated at far higher rates than was supported by earlier systems. The mismatch was pronounced for interactive scenarios. Even during active screen updates, the number of updated pixels were frequently small. We showed that crucial information can be lost if individual updates were merged. When the available system resources could not support high capture rates, we showed ways in which updates can be effectively collapsed. Next, we investigate compression mechanisms for streaming these updates. Even while using a hardware encoder, lossy compressors such as H.264 were unable to sustain high frame rates. Though Zlib lossless compression operated within the latency and compression rate requirements, the compression efficiency was poor. By analyzing the screen pixels, we developed a practical transformation that significantly improved compression rates. DisplayCast incorporates these observations. It shares the processor and network resources required for screen capture, compression and transmission with host applications whose output needs to be shared. DisplayCast is agile and uses faster processing capability to achieve even higher performance. Our system components operate natively in Windows 7, Mac OS X and iOS and is deployed in a production setting. DisplayCast is released under a New BSD License.

Real-time tele-immersion requires low latency and synchronized multi-camera capture. Prior high definition (HD) capture systems were bulky. We investigate the suitability of using flocks of smartphone cameras for tele-immersion. Smartphones integrate capture and streaming into a single portable package. However, they archive the captured video into a movie. Hence, we create a sequence of H.264 movies and stream them. Capture delay is reduced by minimizing the number of frames in each movie segment. However, fewer frames reduces compression efficiency. Also, smartphone video encoders do not sacrifice video quality to lower the compression latency or the stream size. On an iPhone 4S, our application that uses published APIs streams 1920×1080 videos at 16.5 fps with a delay of 712 ms between a real-life event and displaying an uncompressed bitmap of this event on a local laptop. Note that the bulky Cisco Tandberg required 300 ms delay. Stereoscopic video from two unsynchronized smartphones also showed minimal visual artifacts in an indoor setting.

Faithful sharing of screen contents is an important collaboration feature. Prior systems were designed to operate over constrained networks. They performed poorly even without such bottlenecks. To build a high performance screen sharing system, we empirically analyzed screen contents for a variety of scenarios. We showed that screen updates were sporadic with long periods of inactivity. When active, screens were updated at far higher rates than was supported by earlier systems. The mismatch was pronounced for interactive scenarios. Even during active screen updates, the number of updated pixels were frequently small. We showed that crucial information can be lost if individual updates were merged. When the available system resources could not support high capture rates, we showed ways in which updates can be effectively collapsed. We showed that Zlib lossless compression performed poorly for screen updates. By analyzing the screen pixels, we developed a practical transformation that significantly improved compression rates. Our system captured 240 updates per second while only using 4.6 Mbps for interactive scenarios. Still, while playing movies in fullscreen mode, our approach could not achieve higher capture rates than prior systems; the CPU remains the bottleneck. A system that incorporates our findings is deployed within the lab.

DisplayCast is a many to many screen sharing system that is targeted towards Intranet scenarios. The capture software runs on all computers whose screens need to be shared. It uses an application agnostic screen capture mechanism that creates a sequence of pixmap images of the screen updates. It transforms these pixmaps to vastly improve the lossless Zlib compression performance. These algorithms were developed after an extensive analysis of typical screen contents. DisplayCast shares the processor and network resources required for screen capture, compression and transmission with host applications whose output needs to be shared. It balances the need for high performance screen capture with reducing its resource interference with user applications. DisplayCast uses Zeroconf for naming and asynchronous location. It provides support for Cisco WiFi and Bluetooth based localization. It also includes a HTTP/REST based controller for remote session initiation and control. DisplayCast supports screen capture and playback in computers running Windows 7 and Mac OS X operating systems. Remote screens can be archived into a H.264 encoded movie on a Mac. They can also be played back in real time on Apple iPhones and iPads. The software is released under a New BSD license.

This paper describes the design and implementation of a file system-based distributed authoring system for campus-wide workgroups. We focus on documents for which changes by different group members are harder to automatically reconcile into a single version. Prior approaches relied on using group-aware editors. Others built collaborative middleware that allowed the group members to use traditional authoring tools. These approaches relied on an ability to automatically detect conflicting updates. They also operated on specific document types. Instead, our system relies on users to moderate and reconcile updates by other group members. Our file system-based approach also allows group members to modify any document type. We maintain one updateable copy of the shared content on each group member's node. We also hoard read-only copies of each of these updateable copies in any interested group member's node. All these copies are propagated to other group members at a rate that is solely dictated by the wireless user availability. The various copies are reconciled using the moderation operation; each group member manually incorporates updates from all the other group members into their own copy. The various document versions eventually converge into a single version through successive moderation operations. The system assists with this convergence process by using the made-with knowledge of all causal file system reads of contents from other replicas. An analysis using a long-term wireless user availability traces from a university shows the strength of our asynchronous and distributed update propagation mechanism. Our user space file system prototype exhibits acceptable file system performance. A subjective evaluation showed that the moderation operation was intuitive for students.

Contemporary systems use centralized as well as peer-to-peer mechanisms for the large scale distribution of media objects. In this work, we investigate a serendipitous mechanism for directly sharing media objects among a local community of wireless users. This localized sharing is attractive when wide area network connectivity is undesirable, expensive or unavailable; especially when the shared media objects are large. With some restrictions, such localized sharing of media objects is also acceptable to content owners. However, localized sharing has to contend with far fewer media providers who may also not offer the variety of objects available from wide-area services. We collected empirical data from the widely deployed Apple iTunes application for our analysis. We showed that users are already making a significant amount of media objects available for serendipitous sharing. Our analysis showed that the shared object annotations exhibited a Zipfian long tail distribution. The availability patterns of wireless iTunes users and the object annotations makes serendipitous sharing inappropriate for scenarios that require access to a specific object. Instead, mechanisms that allow the user to specify classes of interesting objects are better suited for such users. Also, given the smaller scale of these systems, serendipitous sharing can benefit from approaches that allow users to disseminate a compact representation of their shared objects. Though the wireless user availability rates was not as high as what was observed in a corporate desktop setting, a large fraction of the users showed high temporal consistency. This allows for high availability with reasonable replication during weekday daytime hours. We answer important questions regarding the viability of a campus-wide media sharing system.

Placeshifting systems stream videos from the home to a single remote user using the limited upstream capacity of the home broadband link. We analyze the behavior of two placeshifting systems each using two types of broadband networks. We show that the duration between packets did not depend on the way that the servers were sending the packets through the bottleneck link. Even though both of these systems used TCP, the duration between packets did not follow the round trip times either. Instead, it depended on the particular broadband network. Our analysis shows how the bottlenecked first mile network leads to predictable packet delivery at the remote client. Paradoxically, it also leads to shorter periods and a single packet within each data burst. We discuss the limitations imposed by this behavior on a client side energy saving mechanism. We also describe techniques that allow the placeshifting servers to better operate with client side WNIC energy saving mechanisms.

Asynchronous group communication systems propagate updates from each group member to every other member. Contemporary users are wireless and operate from a variety of locations. Hence, we investigate the propagation performance for these users. An analysis of wireless users in academia, corporation and in a city-wide hotspot federation shows that the availability durations and the duration between sessions depends on the locale. A longer term analysis shows that the user session lengths are becoming smaller while the duration between sessions are becoming larger with significant user churn. We show that the propagation performance depends on the locale. New users incur a heavy cost in receiving updates from prior users; applications need to develop expiration mechanisms to reduce this overhead. Also, since users regularly leave the system, practical communication mechanisms need to choose their propagation periodicity in order to respond to scenarios when the user abruptly leaves the system without propagating their updates to other users.

This paper describes the design and implementation of a group authoring system for wireless users. Our analysis of the behavior of various groupware systems using wireless user availability traces showed that prior systems would have performed poorly, especially during peak availability durations wh

The article focuses on the development of a practical groupware system that allows each group member to modify a shared file unlike to traditional groupware systems in which updates from different users will conflict. The moderated collaborated mechanism maintains multiple copies of the shared objec

We evaluate an asynchronous gossiping middleware for wireless users that propagates messages from any group member to all the other group members. This propagation can either be implemented through distributed mechanisms or can be mediated through servers. Our analysis of asynchronous mechanisms using wireless user availability traces from an university, corporation and a hot spot federation shows that the fundamental impediment to the system performance is the wireless user availability patterns. We then investigate the relative performance for several distributed as well as server mediated approaches. We show that pull mechanisms effectively randomizes the times when messages are propagated and thus achieves better performance than push based mechanisms. We then develop an adaptive approach that customizes the propagation frequency using the last session duration and show that this mechanism exhibits good performance when the required propagation intervals are large. We also show that for a given number of gossips, it is preferable to propagate messages to all available nodes rather than increasing the frequency while correspondingly reducing the number of nodes to propagate messages. Our results allow middleware developers to choose the appropriate propagation model to satisfy their application constraints.

Modern P2P systems use hybrid searches to improve search efficiency. They use a synopsis of neighborhood content to determine whether to use a structured or unstructured overlay to satisfy a particular query. Because of their size restrictions, a synopsis cannot hold all the terms from every file in the neighborhood. The challenge is to choose the terms that should be represented in the synopsis. In this work, we investigated the distribution of query terms and file terms in Gnutella networks. We observed that there was a mismatch between terms that were popular among file names and the terms that were popular among the queries generated by the user. Because the query behavior changed with time, a synopsis based on only static set of popular file terms was ill-suited to support efficient searches. We used these observations to design a synopsis creation algorithm that dynamically adapted to the query workload and selected terms for the synopsis to reflect popular terms in both the query workload and file distribution. Our preliminary experimental analysis showed that our Query-Adaptive synopsis improved the search performance over the traditional file-based synopsis model.

The ubiquitous deployment of wireless LAN networks are allowing students to embrace laptops as their preferred computing platform. We investigated the viability of building collaborative applications to share contents amongst student groups. In our application scenario, the university will provide wireless infrastructure throughout the campus but not the storage infrastructure required to store the shared contents. Laptops will likely exhibit weak availability. Hence, these collaborative applications need to tolerate long delays in propagating updates amongst the participants. In this paper, we presented a preliminary analysis of message forwarding behavior under realistically resource constrained node scenarios. Our experiments were based on the observed wireless user behavior at the University of Notre Dame. Our experiments showed the inherent limits of epidemic propagation in real campus wireless network scenarios.

Hybrid P2P systems rely on the assumption that sufficient objects exist nearby in order to make the unstructured search component efficient. This availability depends on the object annotations as well as on the terms in the queries. Earlier work assumed that the object annotations and query terms follow Zipf-like long-tail distribution. We show that the queries in real systems exhibit more complex temporal behavior. To support our position, first we analyzed the names and annotations of objects that were stored in two popular P2P sharing systems; Gnutella and Apple iTunes. We showed that the names and annotations exhibited a Zipf like long tail distribution. The long tail meant that over 98% of the objects were insufficiently replicated (less than 0.1% of the peers). We also analyzed a query trace of the Gnutella network and identified the popularity distribution of the terms used in the queries. We showed that the set of popular query terms remained stable over time and exhibited a similarity of over 90%. We also showed that despite the Zipf popularity distributions of both query terms and file annotation terms, there was little similarity over time (<20%) between popular file annotation terms and popular file terms. Prior P2P search performance analysis did not take this mismatch between the query terms and object annotations into account and thus overestimated the system performance. There is a need to develop unstructured P2P systems that are aware of the temporal mismatch of the object and query popularity distributions.

Peer-to-peer overlays provide a substrate well suited to building distributed storage systems. Applications that use the infrastructure need the ability to control access to their data. However, traditional authorization services were not designed to operate in the face of network partitions, malicious nodes, and on an Internet-wide scale.

This work focuses on scenarios that require the storage of large amounts of data. Such systems require the ability to either continuously increase the storage space or reclaim space by deleting contents. Traditionally, storage systems relegated object reclamation to applications. In this work, content creators explicitly annotate the object using a temporal importance function. The storage system uses this information to evict less important objects. The challenge is to design importance functions that are simple and expressive. We describe a two step temporal importance function. We introduce the notion of storage importance density to quantify the importance levels for which the storage is full. Using extensive simulations and observations of a university wide lecture video capture and storage application, we show that our abstraction allows the users to express the amount of persistence for each individual object.

Gnutella overlays have evolved to use a two-tier topology. However, we observed that the new topology had only achieved modest improvements in search success rates. Also, the new two-tier topology had not reduced the message routing overhead and bandwidth consumption. In this work, we used local information at each node to construct an overlay, Makalu, that improved search performance and reduced bandwidth consumption. The overlay maximized the expansion from each node's neighborhood while minimizing the latency to its neighbors. We show that for a 100,000 node system, wild card searches using flooding successfully resolved most queries within four hops for object replications ratios as lows as 0.05% (50 randomly distributed copies) with less than 3% duplicate messages. Using attenuated bloom filters to route messages for exact identifier searches, we show that Makalu resolved most queries with less than ten messages for networks as large as 100,000 nodes. The performance of this search is comparable to that of structured P2P systems. Finally, using data from traffic traces of Gnutella in 2003 and 2006, we demonstrated search success rates that were up to five times more successful and required 75% less bandwidth on a Makalu overlay than on a modern Gnutella overlay.

Earlier work had shown the positive learning impact of the ability to review class lecture videos. Prior video capture systems used university provided infrastructure such as video technicians and post-production facilities. However, such capture is expensive; forcing schools to carefully choose the courses that can be video taped. We show that technology advances can allow every faculty member to make a modest effort and video tape their lectures, perform simple post processing and disseminate the contents either through their own web servers, using podcasts or via services such as Google video. Consumer grade HD cameras remove the need for accurate tracking of the faculty member and chalkboards; one stationary camera can frame the entire chalkboard. Desktop computers are powerful enough to perform the required multimedia operations. The faculty can also add pedantically useful annotations; a step that is unlikely to be performed by the video technicians. Many students own iPods, PSPs, laptops and other devices that allow them to watch the video at their convenience. We report on the tools used, the associated network cost and our experiences with video recording an undergraduate Operating Systems (Spring 2006). For the twelve month duration from Feb '06 - Feb '07, the OS course consumed over five days worth of our external network link bandwidth. The network cost in distributing all the lectures taught in our university can be prohibitive.

Sensor networks are deployed to monitor the physical environment in public and vulnerable locations. It is not economically viable to house sensors in tamper-resilient enclosures as they are deployed in large numbers. As a result, an adversary can subvert the integrity of the data being produced by gaining physical access to a sensor and altering its code. If the sensor output is timestamped, then tainted data can be distinguished once the time of attack is determined. To prevent the adversary from generating fraudulent timestamps, the data must be authenticated using a forward-secure protocol. Previous work requires the computation of n hashes to verify the (n + 1)threading. This paper describes PAST, a protocol that allows timestamps to be authenticated with high probability using a small constant number of readings. In particular, PAST is parameterized so that the metadata overhead (and associated power consumption) can be reduced at the cost of lower confidence in the authentication guarantee. Our protocol allows arbitrary levels of assurance for the integrity of timestamps (with logarithmically increasing storage costs) while tolerating any predefined fraction of compromised base stations. Unlike prior schemes, PAST does not depend on synchronized clocks

Hosts connected to the Internet continue to suffer attacks with high frequency. The use of an intrusion detector allows potential threats to be flagged. When an alarm is raised, preventive action can be taken. A primary goal of such action is to assure the security of the data stored in the system. If this operation is effected manually, the delay between the alarm and the response may be enough for an intruder to cause significant damage.The alternative proposed in this paper is to provide a response primitive for intrusion detectors to utilize in automating the response. We describe RICE, a modification to the Java file subsystem that provides such functionality for data that is deemed to be threatened by an attack. If it is activated when an intrusion appears likely to succeed, it guarantees the confidentiality, integrity and availability of the protected data even after a system is compromised.In particular, RICE allows cryptographic encapsulation of data to be reduced to simple key deletion so that it can be effected rapidly. Further, it uses digitally signed hashes of file deltas to allow untained data to be distinguished from the rest. Finally, file deltas are replicated at a remote node to ensure that changes made by an attacker can be undone using the remote replicas.

Mobile ad hoc networks have been the subject of active re-search for a number of years. This paper investigates the feasibility of using such networks for transmitting multime-dia streams. We observe that wireless network IO operations can be expensive (e.g., programmed IO cost, energy to op-erate wireless). Moreover, compared to nodes in infrastruc-ture networks that either read or write network traffic, ad hoc traffic requires the intermediate node to perform many expensive network operations twice (read and then resend) and on behalf of other nodes. This observation raises an im-portant question for the ad hoc community, should they a) demand that ad hoc routers support some minimum hard-ware resources (for example, full DMA support, twice the battery capacity)?, b) force an end-to-end resource manage-ment scheme that cooperatively reduces the network flow to half of what can be serviced by the weakest link? This would ensure that no intermediate node would see enough traffic to overwhelm them? or c) require that the local nodes protect themselves from transit traffic? This paper explores the last mechanism in order to provide some control over the resource consumed without a major revamp of existing operating systems or requiring special hardware. We im-plement our mechanism in the network driver and present encouraging preliminary results.

The recent proliferation of streaming multimedia on a variety of mobile devices has severely tested their battery lifetime. The long running nature of typical streaming applications results in significant energy consumption by the wireless network interface card (WNIC) in these mobile devices. In this paper we explore linear prediction-based client-side strategies that reduce the WNIC energy consumption to receive multimedia streams by judiciously transitioning the WNIC to a lower power consuming sleep state during the no-data intervals in the multimedia stream, without explicit support from the multimedia servers themselves. Experimental results on popular streaming formats such as Microsoft Media, Real and Apple QuickTime show that a linear prediction-based strategy performs better than history-based strategies that use simple temporal averaging.

Mobile computers consume significant amounts of energy when receiving large files. The wireless network interface card (WNIC) is the primary source of this energy consumption. One way to reduce the energy consumed is to transmit the packets to clients in a predictable fashion. Specifically, the packets can be sent in bursts to clients, who can then switch to a lower power sleep state between bursts. This technique is especially effective when the bandwidth of a stream is small. This work investigates techniques for saving energy in a multiple-client scenario, where clients may be receiving either UDP or TCP data. Energy is saved by using a transparent proxy that is invisible to both clients and servers. The proxy implementation maintains separate connections to the client and server so that a large increase in transmission time is avoided. The proxy also buffers data and dynamically generates a global transmission schedule that includes all active clients. Results show that energy savings within 10-15% of optimal are common, with little packet loss.

The proliferation of multimedia-capable mobile devices and ubiquitous high-speed network technologies to deliver multimedia objects has fueled the demand of mobile streaming multimedia. A necessary criterion for the mass acceptance of mobile devices is acceptable battery life of these devices. This paper explores linear prediction-based client-side strategies to reduce the wireless network interface card (WNIC) energy consumption by transitioning the WNIC to a lower power consuming sleep state. The basic idea of this strategy is to selectively choose proper periods of time to suspend communication by switching the WNIC to sleep state. A linear prediction-based time series forecasting technique is used to predict future no-data intervals. Simulation results show that linear prediction-based strategy gives better results than those based on simple averaging [Surendar Chandra et al., (2002)].

This paper describes a peer-to-peer (p2p) system (beacond) that is suitable for teaching important concepts in ubiquitous computing. The system exposes issues in peer location, p2p services, security and privacy issues. The system provided enough background to compliment class lectures and assisted students in designing their own course projects. Students continue to explore ideas exposed by beacond; some of these ideas are being further developed for publication in research conferences[1]. We present our experiences in using this framework for three different course offerings.

The ability of a Web service to provide low-latency access to its contents is constrained by available network bandwidth. It is important for the service to manage available bandwidth wisely. While providing differentiated quality of service (QoS) is typically enforced through network mechanisms, in this paper we introduce a robust mechanism for managing network resources at the application level. We use transcoding to allow Web servers to customize the size of objects constituting a Web page, and hence the bandwidth consumed by that page, by dynamically varying the size of multimedia objects on a per-client basis. We leverage earlier work on characterizing quality versus size tradeoffs in transcoding JPEG images to dynamically determine the quality and size of the object to transmit. We evaluate the performance benefits of incorporating this information in a series of bandwidth management policies. We develop metrics to measure the performance of our system. We use realistic workloads and access scenarios to drive our system. The principal contribution of this work is the demonstration that it is possible to use informed transcoding techniques to provide differentiated service and to dynamically allocate available bandwidth among different client classes, while delivering a high degree of information content (quality factor) for all clients.

The ability of a Web service to provide low-latency access to its content is constrained by available network bandwidth. While providing differentiated quality of service (QoS) is typically enforced through network mechanisms, in this paper we introduce a robust mechanism for managing network resources using application-specific characteristics of Web services. We use transcoding to allow Web servers to customize the size of objects constituting a Web page, and hence the bandwidth consumed by that page, by dynamically varying the size of multimedia objects on a per-client basis. We leverage our earlier work on characterizing quality versus size tradeoffs in transcoding JPEG images to supply more information for determining the quality and size of the object to transmit. We evaluate the performance benefits of incorporating this information in a series of bandwidth management policies using realistic workloads and access scenarios to drive our system. The principal contribution of this paper is the demonstration that it is possible to use informed transcoding techniques to provide differentiated service and to dynamically allocate available bandwidth among different client classes, while delivering good quality of information content for all clients. We also show that it is possible to customize multimedia objects to the highly variable network conditions experienced by mobile clients in order to provide acceptable quality and latency depending on the networks used in accessing the service. We show that policies that aggressively transcode the larger images can produce images with quality factor values that closely follow the untranscoded base case while still saving as much as 150 kB. A transcoding policy that has knowledge of the characteristics of the link to the client can avoid as many as 40% of (unnecessary) transcodings.

This paper describes software to support a large-scale project in an undergraduate Computer Networks course, and our experience using that software.