LSM-tree has been widely used in data management production systems for write-intensive workloads. However, as read and write workloads co-exist under LSM-tree, data accesses can experience long latency and low throughput due to the interferences to buffer caching from the compaction, a major and frequent operation in LSM-tree. After a compaction, the existing data blocks are reorganized and written to other locations on disks. As a result, the related data blocks that have been loaded in the buffer cache are invalidated since their referencing addresses are changed, causing serious performance degradations. To re-enable high-speed buffer caching during intensive writes, we propose Log-Structured buffered-Merge tree (simplified as LSbM-tree) by adding a compaction buffer on disks to minimize the cache invalidations on buffer cache caused by compactions. The compaction buffer efficiently and adaptively maintains the frequently visited datasets. In LSbM, strong locality objects can be effectively kept in the buffer cache with minimum or no harmful invalidations. With the help of a small on-disk compaction buffer, LSbM achieves a high query performance by enabling effective buffer caching, while retaining all the merits of LSM-tree for write-intensive data processing and providing high bandwidth of disks for range queries. We have implemented LSbM based on LevelDB. We show that with a standard buffer cache and a hard disk, LSbM can achieve 2x performance improvement over LevelDB. We have also compared LSbM with other existing solutions to show its strong cache effectiveness.

LSM-tree has been widely used in data management production systems for write-intensive workloads. However, as read and write workloads co-exist under LSM-tree, data accesses can experience long latency and low throughput due to the interferences to buffer caching from the compaction, a major and frequent operation in LSM-tree. After a compaction, the existing data blocks are reorganized and written to other locations on disks. As a result, the related data blocks that have been loaded in the buffer cache are invalidated since their referencing addresses are changed, causing serious performance degradations. In order to re-enable high-speed buffer caching during intensive writes, we propose Log-Structured buffered-Merge tree (simplified as LSbM-tree) by adding a compaction buffer on disks, to minimize the cache invalidations on buffer cache caused by compactions. The compaction buffer efficiently and adaptively maintains the frequently visited data sets. In LSbM, strong locality objects can be effectively kept in the buffer cache with minimum or without harmful invalidations. With the help of a small on-disk compaction buffer, LSbM achieves a high query performance by enabling effective buffer caching, while retaining all the merits of LSM-tree for write-intensive data processing, and providing high bandwidth of disks for range queries. We have implemented LSbM based on LevelDB. We show that with a standard buffer cache and a hard disk, LSbM can achieve 2x performance improvement over LevelDB. We have also compared LSbM with other existing solutions to show its strong effectiveness.

Backlight scaling is a technique proposed to reduce the display panel power consumption by strategically dimming the backlight. However, for mobile video applications, a computationally intensive luminance compensation step must be performed in combination with backlight scaling to maintain the perceived appearance of video frames. This step, if done by the Central Processing Unit (CPU), could easily offset the power savings via backlight dimming. Furthermore, computing the backlight scaling values requires per-frame luminance information, which is typically too energy intensive to compute on mobile devices. In this article, we propose Content-Adaptive Display (CAD) for two typical Internet mobile video applications: video streaming and real-time video communication. CAD uses the mobile device’s Graphics Processing Unit (GPU) rather than the CPU to perform luminance compensation at reduced power consumption. For video streaming where video frames are available in advance, we compute the backlight scaling schedule using a more efficient dynamic programming algorithm than existing work. For real-time video communication where video frames are generated on the fly, we propose a greedy algorithm to determine the backlight scaling at runtime. We implement CAD in one video streaming application and one real-time video call application on the Android platform and use a Monsoon power meter to measure the real power consumption. Experiment results show that CAD can save more than 10% overall power consumption for up to 55.7% videos during video streaming and up to 31.0% overall power consumption in real-time video calls.

The display subsystem of a mobile device usually consumes 38%-68% [1] of the total battery power in video streaming. Therefore, a few schemes have been designed to reduce the display power consumption. The basic idea is to dim the backlight level while properly compensating the pixel luminance to maintain image fidelity. The luminance compensation and proper backlight level calculation are computation intensive and demand per-frame luminance information. For these reasons, existing schemes only work for video-on-demand where each frame (and thus the luminance information) is available in advance. In addition, they demand additional computing resource support. Otherwise, if the computation is conducted on the mobile device, the power consumption due to such computation can easily offset the power savings from dimming the backlight. In this work, we set to investigate power saving for real-time video calls on mobile devices. Different from video-on-demand, real-time video calls are highly delay sensitive and the frame luminance information is not known in advance. Moreover, video calls often involve multiple streaming sources from multiple (≥2) participants, making it more difficult. Because there are few background changes and the frame rate is usually small in video calls, we design a Greedy Display Power saving scheme, called LCD-GDP, which utilizes the commonly available GPU on mobile devices without demanding additional support. Our design is implemented on WebRTC, a popular real-time web browser based video call standard. Experiments show that our scheme can save up to 33% power consumption in video calls without affecting the video call quality.

In-memory key-value stores play a critical role in data processing to provide high throughput and low latency data accesses. In-memory key-value stores have several unique properties that include (1) data intensive operations demanding high memory bandwidth for fast data accesses, (2) high data parallelism and simple computing operations demanding many slim parallel computing units, and (3) a large working set. As data volume continues to increase, our experiments show that conventional and general-purpose multicore systems are increasingly mismatched to the special properties of key-value stores because they do not provide massive data parallelism and high memory bandwidth; the powerful but the limited number of computing cores do not satisfy the demand of the unique data processing task; and the cache hierarchy may not well benefit to the large working set. In this paper, we make a strong case for GPUs to serve as special-purpose devices to greatly accelerate the operations of in-memory key-value stores. Specifically, we present the design and implementation of Mega-KV, a GPU-based in-memory key-value store system that achieves high performance and high throughput. Effectively utilizing the high memory bandwidth and latency hiding capability of GPUs, Mega-KV provides fast data accesses and significantly boosts overall performance. Running on a commodity PC installed with two CPUs and two GPUs, Mega-KV can process up to 160+ million key-value operations per second, which is 1.4-2.8 times as fast as the state-of-the-art key-value store system on a conventional CPU-based platform.

With the advancements in wireless networks and the pervasive adoptions of smartphones with camera capabilities, hundreds of millions mobile users are attracted to video messaging services on their smartphones. Unlike text messaging, transmitting large video messages (with a size of ~ 10 MBytes vs. a 140 Bytes limit for text messages) demands effective network resource provisioning.

The Internet has witnessed rapidly increasing streaming traffic to various mobile devices. In this paper, through analysis of a server-side workload and experiments in a controlled lab environment, we find that current practice has introduced a significant amount of redundant traffic. In particular, for the popular iOS based mobile devices, accessing popular Internet streaming services typically involves about 10%-70% redundant traffic. Such a practice not only over-utilizes and wastes resources on the server side and the network (cellular or Internet), but also consumes additional battery power on user's mobile devices and leads to possible monetary cost. To alleviate such a situation without changing the server side or the client side, we design and implement CStreamer that can transparently work between existing mobile clients and servers. We have implemented a prototype and installed on Amazon EC2. Experiments conducted based on this prototype show that CStreamer can completely eliminate the redundant traffic without degrading user's QoS.

Social network spam increases explosively with the rapid development and wide usage of various social networks on the Internet. To timely detect spam in large social network sites, it is desirable to discover unsupervised schemes that can save the training cost of supervised schemes. In this work, we first show several limitations of existing unsupervised detection schemes. The main reason behind the limitations is that existing schemes heavily rely on spamming patterns that are constantly changing to avoid detection. Motivated by our observations, we first propose a sybil defense based spam detection scheme SD2 that remarkably outperforms existing schemes by taking the social network relationship into consideration. In order to make it highly robust in facing an increased level of spam attacks, we further design an unsupervised spam detection scheme, called UNIK. Instead of detecting spammers directly, UNIK works by deliberately removing non-spammers from the network, leveraging both the social graph and the user-link graph. The underpinning of UNIK is that while spammers constantly change their patterns to evade detection, non-spammers do not have to do so and thus have a relatively non-volatile pattern. UNIK has comparable performance to SD2 when it is applied to a large social network site, and outperforms SD2 significantly when the level of spam attacks increases. Based on detection results of UNIK, we further analyze several identified spam campaigns in this social network site. The result shows that different spammer clusters demonstrate distinct characteristics, implying the volatility of spamming patterns and the ability of UNIK to automatically extract spam signatures.

The Internet has witnessed rapidly increasing streaming traffic to various mobile devices. In this paper, we find that for the popular iOS based mobile devices, accessing popular Internet streaming services typically involves about 10% - 70% unnecessary redundant traffic. Such a practice not only overutilizes and wastes resources on the server side and the network (cellular or Internet), but also consumes additional battery power on users' mobile devices and leads to possible monetary cost. To alleviate such a situation without changing the server side or the iOS, we design and implement a CStreamer prototype that can transparently work between existing iOS devices and media servers. We also build a CStreamer iOS App to enable end users to access Internet streaming services via CStreamer. Experiments conducted based on this prototype running on Amazon EC2 show that CStreamer can completely eliminate the redundant traffic without degrading user's QoS.

Receiving Internet streaming services on various mobile devices is getting increasingly popular, and cloud platforms have also been gradually employed for delivering streaming services to mobile devices. While a number of studies have been conducted at the client side to understand and characterize Internet mobile streaming delivery, little is known about the server side, particularly for the recent cloud-based Internet mobile streaming delivery. In this work, we aim to investigate the Internet mobile streaming service at the server side. For this purpose, we have collected a 4-month server-side log on the cloud (with 1,002 TB delivered video traffic) from a top Internet mobile streaming service provider serving worldwide mobile users. Through trace analysis, we find that 1) a major challenge for providing Internet mobile streaming services is rooted from the mobile device hardware and software heterogeneity. In this workload, we find over 3,400 different hardware models with more than 100 different screen resolutions running 14 different mobile OS and three audio codecs and four video codecs. 2) To deal with the device heterogeneity, CPU-intensive transcoding is used on the cloud to customize the video to the appropriate versions at runtime for different devices. A video clip could be transcoded into more than 40 different versions to serve requests from different devices. 3) Compared to videos in traditional Internet streaming, mobile streaming videos are typically of much smaller size (a median of 1.68 MBytes) and shorter duration (a median of 2.7 minutes). Furthermore, the daily mobile user accesses are more skewed following a Zipf-like distribution but users' interests also quickly shift. Considering the huge demand of CPU cycles for online transcoding, we further examine server-side caching to reduce the total CPU cycle demand from the cloud. We show that a policy considering different versions of a video altogether outperforms other intuitive ones when the cache size is limited.

Spam content is surging with an explosive increase of user generated content (UGC) on the Internet. Spammers often insert popular keywords or simply copy and paste recent articles from the Web with spam links inserted, attempting to disable content-based detection. In order to effectively detect spam in user generated content, we first conduct a comprehensive analysis of spamming activities on a large commercial UGC site in 325 days covering over 6 million posts and nearly 400 thousand users. Our analysis shows that UGC spammers exhibit unique non-textual patterns, such as posting activities, advertised spam link metrics, and spam hosting behaviors. Based on these non-textual features, we show via several classification methods that a high detection rate could be achieved offline. These results further motivate us to develop a runtime scheme, BARS, to detect spam posts based on these spamming patterns. The experimental results demonstrate the effectiveness and robustness of BARS.

Receiving Internet streaming services on various mobile devices is getting more and more popular. To understand and better support Internet streaming delivery to mobile devices, a number of studies have been conducted. However, existing studies have mainly focused on the client side resource consumption and streaming quality. So far, little is known about the server side, which is the key for providing successful mobile streaming services. In this work, we set to investigate the Internet mobile streaming service at the server side. For this purpose, we have collected a one-month server log (with 212 TB delivered video traffic) from a top Internet mobile streaming service provider serving worldwide mobile users. Through trace analysis, we find that (1) a major challenge for providing Internet mobile streaming services is rooted from the mobile device hardware and software heterogeneity. In this workload, we find over 2800 different hardware models with about 100 different screen resolutions running 14 different mobile OS and 3 audio codecs and 4 video codecs. (2) To deal with the device heterogeneity, transcoding is used to customize the video to the appropriate versions at runtime for different devices. A video clip could be transcoded into more than 40 different versions in order to serve requests from different devices. (3) Compared to videos in traditional Internet streaming, mobile streaming videos are typically of much smaller size (a median of 1.68 MBytes) and shorter duration (a median of 2.7 minutes). Furthermore, the daily mobile user accesses are more skewed following a Zipf-like distribution but users' interests also quickly shift. Considering the huge demand of CPU cycles for online transcoding, we further examine server-side caching in order to reduce CPU cycle demand. We show that a policy considering different versions of a video altogether outperforms other intuitive ones when the cache size is limited.

Internet streaming applications are becoming increasingly popular on mobile devices. However, receiving streaming services on mobile devices is often constrained by their limited battery power supply. Various techniques have been proposed to save battery power consumption on mobile devices, mainly focusing on how much data to transmit and how to transmit.

P2P streaming applications are very popular on the Internet today. However, a mobile device in P2P streaming not only needs to continuously receive streaming data from other peers for its playback, but also needs to continuously exchange control information (e.g., buffermaps and file chunk requests) with neighboring peers and upload the downloaded streaming data to them. These lead to excessive battery power consumption on the mobile device.

The pervasive usage of mobile devices and wireless networking support have enabled more and more Internet stream- ing services to all kinds of heterogeneous mobile devices. However, Internet mobile streaming services are challenged by the inherently limited on-device resources, device heterogeneity, and the bulk amount of streaming data.

BitTorrent (BT) has carried out a significant and continuously increasing portion of Internet traffic. While several designs have been recently proposed and implemented to improve the resource utilization by bridging the application layer (overlay) and the network layer (underlay), these designs are largely dependent on Internet infrastructures, such as ISPs and CDNs. In addition, they also demand large-scale deployments of their systems to work effectively. Consequently, they require multiefforts far beyond individual users' ability to be widely used in the Internet. In this paper, aiming at building an infrastructure-independent user-level facility, we present our design, implementation, and evaluation of a topology-aware BT system, called TopBT, to significantly improve the overall Internet resource utilization without degrading user downloading performance. The unique feature of TopBT client lies in that a TopBT client actively discovers network proximities (to connected peers), and uses both proximities and transmission rates to maintain fast downloading while reducing the transmitting distance of the BT traffic and thus the Internet traffic. As a result, a TopBT client neither requires feeds from major Internet infrastructures, such as ISPs or CDNs, nor requires large-scale deployment of other TopBT clients on the Internet to work effectively. We have implemented TopBT based on widely used open-source BT client code base, and made the software publicly available. By deploying TopBT and other BitTorrent clients on hundreds of Internet hosts, we show that on average TopBT can reduce about 25% download traffic while achieving a 15% faster download speed compared to several prevalent BT clients. TopBT has been widely used in the Internet by many users all over the world.

In P2P assisted multi-channel live streaming systems, it is commonly believed that in unpopular channels, quality degradation is due to the small number of participating peers with almost-the-same set of available data; this phenomena prevents effective data exchanges among peers themselves and automatically leads to data request contentions once a new data chunk becomes available. In popular programs, our measurement on PPLive for a continuous three-month period at various locations also shows numerous occurrences of quality degradation because of the even higher ratio (up to 190%) of repetitive data requests for the same data chunks.

With the ever-increasing P2P Internet traffic, recently much attention has been paid to the topology mismatch between the P2P overlay and the underlying network due to the large amount of cross-ISP traffic. Mainly focusing on BitTorrent-like file sharing systems, several recent studies have demonstrated how to efficiently bridge the overlay and the underlying network by leveraging the existing infrastructure, such as CDN services or developing new application-ISP interfaces, such as P4P. However, so far the traffic locality in existing P2P live streaming systems has not been well studied. In this work, taking PPLive as an example, we examine traffic locality in Internet P2P streaming systems. Our measurement results on both popular and unpopular channels from various locations show that current PPLive traffic is highly localized at the ISP level. In particular, we find: (1) a PPLive peer mainly obtains peer lists referred by its connected neighbors (rather than tracker servers) and up to 90% of listed peers are from the same ISP as the requesting peer; (2) the major portion of the streaming traffic received by a requesting peer (up to 88% in popular channels) is served by peers in the same ISP as the requestor; (3) the top 10\% of the connected peers provide most (about 70%) of the requested streaming data and these top peers have smaller RTT to the requesting peer. Our study reveals that without using any topology information or demanding any infrastructure support, PPLive achieves such high ISP level traffic locality spontaneously with its decentralized, latency based, neighbor referral peer selection strategy. These findings provide some new insights for better understanding and optimizing the network- and user-level performance in practical P2P live streaming systems.

Millions of residential users are widely served by cable or DSL connections with modest upload bandwidth and relatively high download bandwidth. For the increasingly important and demanding P2P applications such as VoIP, BitTorrent, and Internet streaming, stable or high upload bandwidth is required. Inadequate upload bandwidth degrades the performance of these applications among residential users. On the other hand, our Internet measurements show that plenty of idle upload bandwidth (from 50% to 80%) is always available in a local residential network. Based on this observation, we propose a system prototype to Coordinate Upload Bandwidth Sharing (CUBS) among neighboring residential users. Specifically, the idle upload bandwidth of neighbors can be used upon a request from a demanding user. Since it has become a common practice to deploy wireless access points in a residential user's home, we have built CUBS by leveraging the support from the wireless networks. In CUBS, to discover and manage idle bandwidth, a localized overlay is constructed by the cooperative users. CUBS is application independent as the bandwidth sharing is implemented at the network layer. CUBS is also ISP transparent because the sharing of neighbors' bandwidth does not demand any additional bandwidth supplies. We have evaluated the CUBS system prototype with experiments on Internet. The experimental results demonstrate that CUBS can effectively improve the performance of upload intensive applications by more than 30%.

Various online social networks (OSNs) have been developed rapidly on the Internet. Researchers have analyzed different properties of such OSNs, mainly focusing on the formation and evolution of the networks as well as the information propagation over the networks. In knowledge-sharing OSNs, such as blogs and question answering systems, issues on how users participate in the network and how users "generate/contribute" knowledge are vital to the sustained and healthy growth of the networks. However, related discussions have not been reported in the research literature.

The commonly agreed Zipf-like access pattern of Web workloads is mainly based on Internet measurements when text-based content dominated the Web traffic. However, with dramatic increase of media traffic on the Internet, the inconsistency between the access patterns of media objects and the Zipf model has been observed in a number of studies. An insightful understanding of media access patterns is essential to guide Internet system design and management, including resource provisioning and performance optimizations.

The success and popularity of social network systems, such as del.icio.us, Facebook, MySpace, and YouTube, have generated many interesting and challenging problems to the research community. Among others, discovering social interests shared by groups of users is very important because it helps to connect people with common interests and encourages people to contribute and share more contents. The main challenge to solving this problem comes from the difficulty of detecting and representing the interest of the users. The existing approaches are all based on the online connections of users and so unable to identify the common interest of users who have no online connections.

Flooding is a fundamental file search operation in unstructured peer-to-peer (P2P) file sharing systems, in which a peer starts the file search procedure by broadcasting a query to its neighbors, who continue to propagate it to their neighbors. This procedure repeats until a time-to-live (TTL) counter is decremented to 0. Flooding can seriously limit system scalability, because the number of redundant query messages grows exponentially during the message propagation. Our study shows that more than 70 percent of the generated messages are redundant in a flooding with a TTL of 7 in a moderately connected Gnutella network. Existing efforts to address this issue have been focused on limiting the use of the flooding operation. We propose a new flooding scheme, called LightFlood, with the objective of minimizing the number of redundant messages and retaining a similar message-propagating scope as that of the standard flooding. In the scheme, each peer keeps track of the connectivities of every immediate and next indirect neighbor peers, which can be acquired locally. LightFlood identifies the neighbor with the highest connectivity and uses the link to that neighbor to form a suboverlay within the existing P2P overlay. In LightFlood, flooding is divided into two stages. The first stage is a standard flooding with a limited number of TTL hops, where a message can spread to a sufficiently large scope with a small number of redundant messages. In the second stage, message propagating is only conducted along the suboverlay, significantly reducing the number of redundant messages. Our analysis and simulation experiments show that the LightFlood scheme provides a low-overhead broadcast facility that can be effectively used in P2P search. For example, compared with standard flooding with seven TTL hops, we show that LightFlood with an additional two to three hops can reduce up to 69 percent of the flooding messages and retain the same flooding scope. We believe that LightFlood can be widely used as a core mechanism for efficient message broadcasting in P2P systems due to its near-optimal performance.

The increasing number of wireless users in Internet P2P applications causes two new performance problems due to the requirement of uploading the downloaded traffic for other peers, limited bandwidth of wireless communications, and resource competition between the access point and wireless stations. First, an active P2P wireless user can significantly reduce the downloading throughput of other wireless users in the WLAN. Second, the slowdown of a P2P wireless user communication can also delay its relay and data sharing service for other dependent wired/wireless peers. In order to address these problems, in this paper, we propose an efficient caching mechanism called SCAP (Smart Caching in Access Points). Conducting intensive Internet measurements on representative P2P streaming applications, we observe a high percentage of duplicated data packets in successive downloading and uploading data streams. Through duplication detection and caching at the access point, these duplicated packets can be compressed so that the uploading traffic in the WLAN is significantly reduced. Our prototype-based experimental evaluation demonstrates that by effectively reducing the redundant P2P traffic in the WLAN, SCAP improves the throughput of the WLAN by up to 88% and reduces the response delay to other Internet users meanwhile.

Instant messaging (IM) has become increasingly popular due to its quick response time, its ease of use, and possibility of multitasking. It is estimated that there are several millions of instant messaging users who use IM for various purposes: simple requests and responses, scheduling face to face meetings, or just to check the availability of colleagues and friends. Despite its popularity and user base, little has been done to characterize IM traffic. One reason might be its relatively small traffic volume, although this is changing as more users start using video or voice chats and file attachments. Moreover, all major instant messaging systems route text messages through central servers. While this facilitates firewall traversal and gives instant messaging companies more control, it creates a potential bottleneck at the instant messaging servers. This is especially so for large instant messaging operators with tens of millions of users and during flash crowd events. Another reason for the lack of previous studies is the difficulty in getting access to instant messaging traces due to privacy concerns. In this paper, we analyze the traffic of two popular instant messaging systems, AOL Instant Messenger (AIM) and MSN/Windows Live Messenger, from thousands of employees in a large enterprise. We found that most instant messaging traffic is due to presence, hints, or other extraneous traffic. Chat messages constitute only a small percentage of the total IM traffic. This means, during overload, IM servers can protect the instantaneous nature of the communication by dropping extraneous traffic. We also found that the social network of lM users does not follow a power law distribution. It can be characterized by a Weibull distribution. Our analysis sheds light on instant messaging system design and optimization and provides a scientific basis for instant messaging workload generation.

While the 802.11 power saving mode (PSM) and its enhancements can reduce power consumption by putting the wireless network interface (WNI) into sleep as much as possible, they either require additional infrastructure support, or may degrade the transmission throughput and cause additional transmission delay. These schemes are not suitable for long and bulk data transmissions with strict QoS requirements on wireless devices. With increasingly abundant bandwidth available on the Internet, we have observed that TCP congestion control is often not a constraint of bulk data transmissions as bandwidth throttling is widely used in practice. In this paper, instead of further manipulating the trade-off between the power saving and the incurred delay, we effectively explore the power saving potential by considering the bandwidth throttling on streaming/downloading servers. We propose an application-independent protocol, called PSM-throttling. With a quick detection on the TCP flow throughput, a client can identify bandwidth throttling connections with a low cost Since the throttling enables us to reshape the TCP traffic into periodic bursts with the same average throughput as the server transmission rate, the client can accurately predict the arriving time of packets and turn on/off the WNI accordingly. PSM-throttling can minimize power consumption on TCP-based bulk traffic by effectively utilizing available Internet bandwidth without degrading the application's performance perceived by the user. Furthermore, PSM-throttling is client-centric, and does not need any additional infrastructure support. Our lab-environment and Internet-based evaluation results show that PSM-throttling can effectively improve energy savings (by up to 75%) and/or the QoS for a broad types of TCP-based applications, including streaming, pseudo streaming, and large file downloading, over existing PSM-like methods.

No abstract available.

This paper presents a performance study of BitTorrent-like P2P systems by modeling, based on extensive measurements and trace analysis. Existing studies on BitTorrent systems are single-torrent based and usually assume the process of request arrivals to a torrent is Poisson-like. However, in reality, most BitTorrent peers participate in multiple torrents and file popularity changes over time. Our study of representative BitTorrent traffic provides insights into the evolution of single-torrent systems and several new findings regarding the limitations of BitTorrent systems: (1) Due to the exponentially decreasing peer arrival rate in a torrent, the service availability of the corresponding file becomes poor quickly, and eventually it is hard to locate and download this file. (2) Client performance in the BitTorrent-like system is unstable, and fluctuates significantly with the changes of the number of online peers. (3) Existing systems could provide unfair services to peers, where a peer with a higher downloading speed tends to download more and upload less. Motivated by the analysis and modeling results, we have further proposed a graph based model to study interactions among multiple torrents. Our model quantitatively demonstrates that inter-torrent collaboration is much more effective than stimulating seeds to serve longer for addressing the service unavailability in BitTorrent systems. An architecture for inter-torrent collaboration under an exchange based instant incentive mechanism is also discussed and evaluated by simulations.

As a family of wireless local area network (WLAN) protocols between physical layer and higher layer protocols, IEEE 802.11 has to accommodate the features and requirements of both ends. However, current practice has addressed the problems of these two layers separately and is far from satisfactory. On one end, due to varying channel conditions, WLANs have to provide multiple physical channel rates to support various signal qualities. A low channel rate station not only suffers low throughput, but also significantly degrades the throughput of other stations. On the other end, the power saving mechanism of 802.11 is ineffective in TCP-based communications, in which the wireless network interface (WNI) has to stay awake to quickly acknowledge senders, and hence, the energy is wasted on channel listening during idle awake time. In this paper, considering the needs of both ends, we utilize the idle communication power of the WNI to provide a Cooperative Relay Service (CRS) for WLANs with multiple channel rates. We characterize energy efficiency as energy per bit, instead of energy per second. In CRS, a high channel rate station relays data frames as a proxy between its neighboring stations with low channel rates and the Access Point, improving their throughput and energy efficiency. Different from traditional relaying approaches, CRS compensates a proxy for the energy consumed in data forwarding. The proxy obtains additional channel access time from its clients, leading to the increase of its own throughput without compromising its energy efficiency. Extensive experiments are conducted through a prototype implementation and ns-2 simulations to evaluate our proposed CRS. The experimental results show that CRS achieves significant performance improvements for both low and high channel rate stations

Peer-to-peer (P2P) technology has been successfully applied in Internet telephony or Voice over Internet Protocol (VoIP), such as the Skype system, where P2P is used for both searching clients and relaying voice packets. Selecting one or multiple suitable peers to relay voice packets is a critical factor for the quality, scalability and cost of a VoIP system. In this paper, we first present two sets of intensive Internet measurement results to confirm the benefits gained by peer relays in VoIP, and to investigate the performance of the Skype system. We obtain the following results: (1) many relay peer selections are suboptimal; (2) the waiting time to select a relay node can be quite long; and (3) there are a large number of unnecessary probes, resulting in heavy network traffic to limit scalability of the VoIP system. Our further analysis shows that two main reasons cause these problems. First, the peer selections do not take Autonomous System (AS) topology into consideration, and second, the complex communication relationships among peers are not well utilized. Motivated by our measurements and analysis, we propose an AS-aware peer-relay protocol called ASAP. Our objective is to significantly improve VoIP quality and system scalability with low overhead. Our intensive evaluation by trace-driven simulation shows ASAP is highly effective and easy to implement on the Internet for building large and scalable VoIP systems.

Modern Internet streaming services have utilized various techniques to improve the quality of streaming media delivery. Despite the characterization of media access patterns and user behaviors in many measurement studies, few studies have focused on the streaming techniques themselves, particularly on the quality of streaming experiences they offer end users and on the resources of the media systems that they consume. In order to gain insights into current streaming services techniques and thus provide guidance on designing resource-efficient and high quality streaming media systems, we have collected a large streaming media workload from thousands of broadband home users and business users hosted by a major ISP, and analyzed the most commonly used streaming techniques such as automatic protocol switch, Fast Streaming, MBR encoding and rate adaptation. Our measurement and analysis results show that with these techniques, current streaming systems these techniques tend to over-utilize CPU and bandwidth resources to provide better services to end users, which may not be a desirable and effective is not necessary the best way to improve the quality of streaming media delivery. Motivated by these results, we propose and evaluate a coordination mechanism that effectively takes advantage of both Fast Streaming and rate adaptation to better utilize the server and Internet resources for streaming quality improvement.

Abstract — As a family of wireless local area network (WLAN) protocols between physical layer and higher-layer protocols, IEEE 802.11 has to accommodate the features and requirements of both ends. However, current practice has addressed the problems separately and is far from being satisfactory. On the one end, due to varying channel conditions, WLANs have to provide multiple data channel rates to support various bit error rates. A low channel rate station not only suffers low throughput itself, but also significantly degrades the throughput of other stations. On the other end, TCP is not energy efficient running on 802.11. This is because a wireless network interface (WNI) has to stay awake to generate timely acknowledgments during a TCP session, and hence, the energy consumed during idle awake time is wasted for channel listening. In this paper, considering the needs of both ends, we utilize the idle communication power of the WNI to improve the throughput and energy efficiency of stations in WLANs supporting multiple channel rates. We characterize the energy efficiency as energy per bit, instead of energy per second. Based on modeling and analysis, we propose a data forwarding mechanism and an energy-aware channel allocation mechanism. In such a system, a high channel rate station relays data frames between its neighboring stations with low channel rates and Access Point, improving their throughput and energy efficiency. Different from traditional relaying approaches, our scheme compensates for the energy consumption for data forwarding. The forwarding station gets additional channel access time from its beneficiaries, leading to the increase of its own throughput without compromising its energy efficiency. We implement a prototype of our proposed system and evaluate it through extensive experiments. Our results show significant performance improvements for both low and high channel rate stations. I.

To efficiently deliver streaming media, researchers have developed technical solutions that fall into three categories, each of which has its merits and limitations. Infrastructure-based CDNs with dedicated network bandwidths and hardware supports can provide high-quality streaming services, but at a high cost. Server-based proxies are cost-effective but not scalable due to the limited proxy capacity in storage and bandwidth, and its centralized control also brings a single point of failure. Client-based P2P networks are scalable, but do not guarantee high-quality, streaming service due to the transient nature of peers. To address these limitations, we present a novel and efficient design of a scalable and reliable media proxy system assisted by P2P networks, called PROP. In the PROP system, the clients' machines in an intranet are self-organized into a structured P2P system to provide a large media storage and to actively participate in the streaming media delivery, where the proxy is also embedded as an important member to ensure the quality of streaming service. The coordination and collaboration in the system are efficiently conducted by our P2P management structure and replacement policies. Our system has the following merits: 1) It addresses both the scalability problem in centralized proxy systems and the unreliable service concern by only relying on the P2P sharing of clients. 2) The proposed content locating scheme can timely serve the demanded media data and fairly dispatch media streaming tasks in appropriate granularity across the system. 3) Based on the modeling and analysis, we propose global replacement policies for proxy and clients, which well balance the demand and supply of streaming data in the system, achieving a high utilization of peers' cache. We have comparatively evaluated our system through trace-driven simulations with synthetic workloads and with a real-life workload extracted from the media server logs in an enterprise network, which shows our design significantly improves the quality of media streaming and the system scalability.

Streaming media objects have become widely used on the Internet, and the demand of interactive requests to these objects has increased dramatically. Typical interactive requests include fast forward and direct jumps. Unfortunately, most of existing streaming proxies are designed for sequential accesses, and only a few solutions have been proposed to maintain additional data structures in the proxy to support some interactive operations (such as fast forward) other than jumps, which are among the most common interactive requests from the clients. Focusing on interactive accesses, in this paper, we present an analysis of streaming media workload collected from thousands of broadband users hosted by a major ISP. Our analysis shows that jump accesses (48%) and pauses (51%) are the dominant client interactive requests and that jump accesses often suffer serious delays due to slow buffering through the network. To support jump accesses effectively, we further propose a novel caching algorithm - DISC (dynamic interleaved segment caching), which trades cache performance for response time to client interactive requests. In this algorithm, segments of a media object are cached dynamically according to client access patterns. DISC can support direct jumps efficiently while ensuring timely prefetching of uncached segments for sequential accesses. Trace-driven simulations demonstrate that DISC outperforms other caching schemes significantly for interactive requests with only a small degradation in cache performance

In this paper, we study the media workload collected from a large number of commercial Web sites hosted by a major ISP and that collected from a large group of home users connected to the Internet via a well-known cable company. Some of our key findings are: (1) Surprisingly, the majority of media contents are still delivered via downloading from Web servers. (2) A substantial percentage of media downloading connections are aborted before completion due to the long waiting time. (3) A hybrid approach, pseudo streaming, is used by clients to imitate real streaming. (4) The mismatch between the downloading rate and the client playback speed in pseudo streaming is common, which either causes frequent playback delays to the clients, or unnecessary traffic to the Internet. (5) Compared with streaming, downloading and pseudo streaming are neither bandwidth efficient nor performance effective. To address this problem, we propose the design of AutoStream, an innovative system that can provide additional previewing and streaming services automatically for media objects hosted on standard Web sites in server farms at the client's will.

The demand of delivering streaming media content in the Internet has become increasingly high for scientific, educational, and commercial applications. Three representative technologies have been developed for this purpose, each of which has its merits and serious limitations. Infrastructure-based CDNs with dedicated network bandwidths and powerful media replicas can provide high quality streaming services but at a high cost. Server-based proxies are cost-effective but not scalable due to the limited proxy capacity and its centralized control. Client-based P2P networks are scalable but do not guarantee high quality streaming service due to the transient nature of peers. To address these limitations, we present a novel and efficient design of a scalable and reliable media proxy system supported by P2P networks. This system is called PROP abbreviated from our technical theme of "collaborating and coordinating PROxy and its P2P clients". Our objective is to address both scalability and reliability issues of streaming media delivery in a cost-effective way. In the PROP system, the clients' machines in an intranet are self-organized into a structured P2P system to provide a large media storage and to actively participate in the streaming media delivery, where the proxy is also embedded as an important member to ensure quality of streaming service. The coordination and collaboration in the system are efficiently conducted by our P2P management structure and replacement policies. We have comparatively evaluated our system by trace-driven simulations with synthetic workloads and with a real-life workload trace extracted from the media server logs in an enterprise network. The results show that our design significantly improves the quality of media streaming and the system scalability.

Summary form only given. A peer-to-peer (P2P) system is built upon an overlay network whose topology is independent of the underlying physical network. A well-routed message path in an overlay network with a small number of logical hops can result in a long delay and excessive traffic due to undesirably long distances in some physical links. We propose an effective method, called SAT-Match, to adoptively construct structured P2P overlay networks, aiming at significantly reducing the lookup routing latency. In this method, each joining peer is initially guided to find a physically close neighbor to connect with. After then, its overlay location is adoptively adjusted whenever a location mismatch is detected. The topology matching optimization in our method solely relies on local neighborhood information. Compared with existing topology matching methods, our method addresses their three limitations: (1) heavily relying on global information about the Internet by using landmark-based measurements, (2) lacking adaptation to frequent peer movement in a dynamic environment, such as mobile networks, and (3) insufficiently accurate in topology matching due to the lack of adaptive topology adjustment. We have evaluated our method in the content-addressable network (CAN), a representative structured P2P system with a strong tolerance to frequent peer arrivals/departures. Through intensive simulation experiments on large scale CAN overlays, we have shown the effectiveness of SAT-Match. Our method can achieve average logical/physical link latency reduction rate by up to 40%. It also outperforms "landmark binning", a method utilizing global information by up to 20%. Finally, combining with the landmark binning method, SAT-Match can achieve up to 60% latency reduction.

"Flooding" is a fundamental operation in unstructured peer-to-peer (P2P) file sharing systems, such as Gnutella. Although it is effective in content search, flooding is very inefficient because it results in a great amount of redundant messages. Our study shows that more than 70% of the generated messages are redundant for a flooding with a TTL of 7 in a moderately connected network. Existing efforts to address this problem have been focused on limiting the use of flooding operations. We propose LightFlood, an efficient flooding scheme, with the objective of minimizing the number of redundant messages and retaining the same message propagating scope as that of standard flooding. By constructing a tree-like suboverlay within the existing P2P overlay called FloodNet, the flooding operation in LightFlood is divided into two stages. In the first stage, a message is propagated by using the standard flooding scheme with three or four TTL hops, through which the message can be spread to a sufficiently large scope with a small number of redundant messages. In the second stage, the message propagating is only conducted across the FloodNet, significantly reducing the number of redundant messages. Our analysis and simulation results show that the LightFlood scheme provides a low overhead broadcasting facility that can be effectively used in P2P searching. Compared with standard flooding used in Gnutella, we show that the LightFlood scheme with an additional 2 to 3 hops can reduce up to more than 69% of flooding messages, and retain the same flooding scope