Exploiting unlabeled data to improve peer-to-peer traffic classification using incremental tri-training method

Unlabeled training examples are readily available in many applications, but labeled examples are fairly expensive to obtain. For instance, in our previous works on classification of peer-to-peer (P2P) Internet traffics, we observed that only about 25% of examples can be labeled as “P2P”or “NonP2P” using a port-based heuristic rule. We also expect that even fewer examples can be labeled in the future as more and more P2P applications use dynamic ports. This fact motivates us to investigate the techniques which enhance the accuracy of P2P traffic classification by exploiting the unlabeled examples. In addition, the Internet data flows dynamically in large volumes (streaming data). In P2P applications, new communities of peers often join and old communities of peers often leave, requiring the classifiers to be capable of updating the model incrementally, and dealing with concept drift. Based on these requirements, this paper proposes an incremental Tri-Training (iTT) algorithm. We tested our approach on a real data stream with 7.2 Mega labeled examples and 20.4 Mega unlabeled examples. The results show that iTT algorithm can enhance accuracy of P2P traffic classification by exploiting unlabeled examples. In addition, it can effectively deal with dynamic nature of streaming data to detect the changes in communities of peers. We extracted attributes only from the IP layer, eliminating the privacy concern associated with the techniques that use deep packet inspection.

On peer-to-peer (P2P) content delivery

In both academia and industry, peer-to-peer (P2P) applications have attracted great attentions. P2P applications such as Napster, Gnutella, FastTrack, BitTorrent, Skype and PPLive, have witnessed tremendous success among the end users. Unlike a client-server based system, peers bring with them serving capacity. Therefore, as the demand of a P2P system grows, the capacity of the network grows, too. This enables a P2P application to be cheap to build and superb in scalability. In this paper, we survey the state of the art of the research and the development of P2P content delivery application. Using examples of the deployed P2P applications and research prototypes, we survey the best practices in P2P overlay building and P2P scheduling. We hope that the information may help the readers to build a reliable, robust P2P content delivery application.

An analysis of peer-to-peer networks with altruistic peers

We develop a new model of the interaction of rational peers in a Peer-to-Peer (P2P) network that has at its heart altruism, an intrinsic parameter reflecting peers’ inherent willingness to contribute. Two different approaches for modelling altruistic behavior and its attendant benefit are introduced. With either approach, we use Game Theoretic analysis to calculate Nash equilibria and predict peer behavior in terms of individual contribution. We consider the cases of P2P networks of peers that (i) have homogeneous altruism levels or (ii) have heterogeneous altruism levels, but with known probability distributions. We find that, under the effects of altruism, a substantial fraction of peers will contribute when altruism levels are within certain intervals, even though no incentive mechanism is used. Our results corroborate empirical evidence of large P2P networks surviving or even flourishing without or with barely functioning incentive mechanisms. We also enhance the model with a simple but powerful incentive scheme to limit free-riding and increase contribution to the network, and show that the particular incentive scheme on networks with altruistic peers achieves its goal.

Revisiting free riding and the Tit-for-Tat in BitTorrent: A measurement study

In this paper we report new results of our continuous effort on analyzing the impact of incentive mechanisms on user behavior in BitTorrent. In this second measurement and analysis study we find that free riders’ population has significantly increased comparing to our previous measurement study. We relate this increase to the advance in end-users’ connection speeds and to users’ increased knowledge in BitTorrent. We also categorize free riders based on the behavior they exhibit in multiple-torrent system into three types: cheaters, strategic and lucky peers. Furthermore, refuting the findings of other studies, we show that peers who exploit the system in BitTorrent are both high bandwidth capacity peers and low bandwidth capacity peers. Moreover, we argue that the Tit-for-Tat mechanism does not discriminate peers based on their bandwidth capacities and that it reacts successfully against inter-class bandwidth capacity strategic peers. Finally, we propose a memory-backoff approach to the optimistic unchoke policy that reduces the volume of free riding in BitTorrent.

Context-aware trust negotiation in peer-to-peer service collaborations

Service-oriented architecture (SOA) and Software as a Service (SaaS) are the latest hot topics to software manufacturing and delivering, and attempt to provide a dynamic cross-organisational business integration solution. In a dynamic cross-organisational collaboration environment, services involved in a business process are generally provided by different organisations, and lack supports of common security mechanisms and centralized management middleware. On such occasions, services may have to achieve middleware functionalities and achieve business objectives in a pure peer-to-peer fashion. As the participating services involved in a business process may be selected and combined at run time, a participating service may have to collaborate with multiple participating services which it has no pre-existing knowledge in prior. This introduces some new challenges to traditional trust management mechanisms. Automated Trust Negotiation (ATN) is a practical approach which helps to generate mutual trust relationship for collaborating principals which may have no pre-existing knowledge about each other without in a peer-to-peer way. Because credentials often contain sensitive attributes, ATN defines an iterative and bilateral negotiation process for credentials exchange and specifies security policies that regulate the disclosure of sensitive credentials. Credentials disclosure in the iterative process may follow different orders and combinations, each of which forms a credential chain. It is practically desirable to identify the optimal credential chain that satisfies certain objectives such as minimum release of sensitive information and minimum performance penalty. In this paper we present a heuristic and context-aware algorithm for identifying the optimal chain that uses context-related knowledge to minimize 1) the release of sensitive information including both credentials and policies and 2) the cost of credentials retrieving. Moreover, our solution offers a hierarchical method for protecting sensitive policies and provides a risk-based strategy for handling credential circular dependency. We have implemented the ATN mechanisms based on our algorithm and incorporated them into the CROWN Grid middleware. Experimental results demonstrate their performance-related advantages over other existing solutions.

An inexpensive unstructured platform for wireless mobile peer-to-peer networks

In this paper, we propose an unstructured platform, namely I nexpensive P eer-to- P eer S ubsystem (IPPS), for wireless mobile peer-to-peer networks. The platform addresses the constraints of expensive bandwidth of wireless medium, and limited memory and computing power of mobile devices. It uses a computationally-, memory requirement- and communication- wise inexpensive gossip protocol as the main maintenance operation, and exploits location information of the wireless nodes to minimize the number of link-level messages for communication between peers. As a result, the platform is not only lightweight by itself, but also provides a low cost framework for different peer-to-peer applications. In addition, further enhancements are introduced to enrich the platform with robustness and tolerance to failures without incurring any additional computational and memory complexity, and communication between peers. In specific, we propose schemes for a peer (1) to chose a partner for a gossip iteration, (2) to maintain the neighbors, and (3) to leave the peer-to-peer network. Simulation results are given to demonstrate the performance of the platform.

PatchPeer: A scalable video-on-demand streaming system in hybrid wireless mobile peer-to-peer networks

Video-on-demand service in wireless networks is one important step to achieving the goal of providing video services anywhere anytime. Typically, carrier mobile networks are used to deliver videos wirelessly. Since every video stream comes from the base station, regardless of what bandwidth sharing techniques are being utilized, the media stream system is still limited by the network capacity of the base station. The key to overcome the scalability issue is to exploit resources available at mobile clients in a peer-to-peer setting. We observe that it is common to have a carrier mobile network and a mobile peer-to-peer network co-exist in a wireless environment. A feature of such hybrid environment is that the former offers high availability assurance, while the latter presents an opportunistic use of resources available at mobile clients. Our proposed video-on-demand technique, PatchPeer, leverages this network characteristic to allow the video-on-demand system scale beyond the bandwidth capacity of the server. Mobile clients in PatchPeer are no longer passive receivers, but also active senders of video streams to other mobile clients. Our extensive performance study shows that PatchPeer can accept more clients than the current state-of-the-art technique, while maintaining the same Quality-of-Service to clients.

A contribution-based service differentiation scheme for peer-to-peer systems

Trust is required in a file sharing peer-to-peer system to achieve better cooperation among peers. In reputation-based peer-to-peer systems, reputation is used to build trust among peers. In these systems, highly reputable peers will usually be selected to upload requested files, decreasing significantly malicious uploads in the system. However, these peers need to be motivated by increasing the benefits that they receive from the system. In addition, it is necessary to motivate free riders to contribute to the system by sharing files. Malicious peers should be also motivated to contribute positively by uploading authentic files instead of malicious ones. Service differentiation is required to motivate peers to get involved by sharing and uploading the requested files. To provide the right incentives for peers to contribute to the system, the new concept of Contribution Behavior is introduced for partially decentralized peer-to-peer systems. In this paper, the Contribution Behavior of the peer is used as a guideline for service differentiation instead of peer’s reputation. Both Availability and Involvement of the peer are used to assess its Contribution Behavior. Performance evaluations confirm the ability of the proposed scheme to effectively identify both free riders and malicious peers and reduce the level of service provided to them. On the other hand, good peers receive better service. Simulation results also confirm that based on a Rational Behavior, peers are motivated to increase their contribution to receive services. Moreover, using our scheme, peers must continuously participate, reducing significantly the milking phenomenon.

Adaptive component composition and load balancing for distributed stream processing applications

Providing real-time and QoS support to stream processing applications running on top of large-scale overlays is challenging due to the inherent heterogeneity and resource limitations of the nodes and the multiple QoS demands of the applications that must concurrently be met. In this paper we propose an integrated adaptive component composition and load balancing mechanism that (1) allows the composition of distributed stream processing applications on the fly across a large-scale system, while satisfying their QoS demands and distributing the load fairly on the resources, and (2) adapts dynamically to changes in the resource utilization or the QoS requirements of the applications. Our extensive experimental results using both simulations as well as a prototype deployment illustrate the efficiency, performance and scalability of our approach.

Improving robustness of P2P applications in mobile environments

Mobile P2P networks possess particular characteristics which make accessibility of services deployed on peers a challenge. This has to be taken into account when considering robustness of applications that depend on successfully accessing a set of services. While ensuring robustness is traditionally handled through replication or redundancy, those solutions are not readily applicable to decentralized and dynamic networks. Instead, current solutions are based on efficient P2P structure maintenance or unstructured network search algorithms. A novel and alternative method proposed in this paper is based on the observation that some redundancy may exist between services offered on the network, a fact which could be used to recreate an unavailable service from services accessible to a peer. Instead of adding redundancy to the system, our solution exploits the already existing redundancy to improve robustness of mobile P2P applications. We model the interaction with services as finite-state transducers and propose a heuristic to obtain redundancy between any pair of services. Then, a set of algorithms that uses this inter-service redundancy to recreate the interaction with one service from the other is discussed. The computational cost is polynomial with respect to services’ size, and in practice, the non-redundant functionality and related control need to be implemented locally.

SUPNET: An end-to-end solution to scalable unstructured P2P networking

Despite many improvements on original unstructured P2P networks, these systems still suffer from several problems, the most important of which are, (a) lack of guarantees on the integrity of the network topology in the face of churns, (b) excessive traffic cost and (c) poor quality of search results. This paper introduces an end-to-end scalable unstructured P2P networking solution called SUPNET to address many of these issues. SUPNET is based on our pragmatic, design oriented approach to engineering complex networks. Rather than modeling dynamical behavior in already-existing networks, we actively design and implement local stochastic dynamics so that an engineered global system, with predictable structures emerges. The resulting protocol, SUPNET, consists of two sub-protocols for network management and content search. The network management sub-protocol is scalable and highly robust and is capable of utilizing the heterogeneous distribution of network resources. Its high stability is the result of implementation of a novel distributed feedback mechanism. The search sub-protocol is capable of locating every item, even if a single copy of that item exists in the network, while producing a traffic that scales provably sub-linear with the network size. It also contains mechanisms for very efficient location of popular items as well as distributed parameter tuning algorithms. These, along with inherently self-organized and de-centralized operation, relative ease of implementation and solid analytical foundation, make SUPNET a compelling solution for unstructured P2P networking.

A unifying framework of rating users and data items in peer-to-peer and social networks

We propose a unifying family of quadratic cost functions to be used in Peer-to-Peer ratings. We show that our approach is general since it captures many of the existing algorithms in the fields of visual layout, collaborative filtering and Peer-to-Peer rating, among them Koren spectral layout algorithm, Katz method, Spatial ranking, Personalized PageRank and Information Centrality. Besides of the theoretical interest in finding common basis of algorithms that where not linked before, we allow a single efficient implementation for computing those various rating methods. We introduce a distributed solver based on the Gaussian Belief Propagation algorithm which is able to efficiently and distributively compute a solution to any single cost function drawn from our family of quadratic cost functions. By implementing our algorithm once, and choosing the computed cost function dynamically on the run we allow a high flexibility in the selection of the rating method deployed in the Peer-to-Peer network. Using simulations over real social network topologies obtained from various sources, including the MSN Messenger social network, we demonstrate the applicability of our approach. We report simulation results using networks of millions of nodes.

Automated music video generation using multi-level feature-based segmentation

We show how to create a music video automatically, using computable characteristics of the video and music to promote coherent matching. We analyze the flow of both music and video, and then segment them into sequences of near-uniform flow. We extract features from the both video and music segments, and then find matching pairs. The granularity of the matching process can be adapted by extending the segmentation process to several levels. Our approach drastically reduces the skill required to make simple music videos.

Peer sampling with improved accuracy

Node sampling services provide peers in a peer-to-peer system with a source of randomly chosen addresses of other nodes. Ideally, samples should be independent and uniform. The restrictions of a distributed environment, however, introduce various dependancies between samples. We review gossip-based sampling protocols proposed in previous work, and identify sources of inaccuracy. These include replicating the items from which samples are drawn, and imprecise management of the process of refreshing items. Based on this analysis, we propose a new protocol, Eddy, which aims to minimize temporal and spatial dependancies between samples. We demonstrate, through extensive simulation experiments, that these changes lead to an improved sampling service. Eddy maintains a balanced distribution of items representing active system nodes, even in the face of realistic levels of message loss and node churn. As a result, it behaves more like a centralized random number generator than previous protocols. We demonstrate this by showing that using Eddy improves the accuracy of a simple algorithm that uses random samples to estimate the size of a peer-to-peer network.

Motion estimation based color transfer and its application to color video compression

In this paper a novel scheme for color video compression using color transfer technique is proposed. Towards this, a new color transfer mechanism for video using motion estimation is presented. Encoder and decoder architectures for the proposed compression scheme are also presented. In this scheme, compression is achieved by firstly discarding chrominance information for all but selected reference frames and then using motion prediction and discrete cosine transform (DCT) based quantization. At decompression stage, the luminance-only frames are colored using chrominance information from the reference frames applying the proposed color transfer technique. To integrate color transfer mechanism with hybrid compression scheme a new color transfer protocol is defined. Both compression scheme and color transfer work in YCbCr color space.

DHT routing analysis in a logarithmically transformed space

This paper presents an analytical model that helps understanding the common foundations of routing in DHTs and provides means for analytical comparison of different systems and different parameter combinations. In the proposed model, a logarithmic transformation is applied to the metric space embedding node identifiers. We show that in this transformed space - similarly to short-range connections in the real metric space - long-range connections have linear properties: connections are uniformly distributed and routing via long-range contacts progresses linearly toward the target. Using this transformation model, we introduce a λ long-range connection density parameter to characterize DHT routing and analyze common properties and differences between existing DHT routing mechanisms. For the the two extreme DHT families (“most random” and completely deterministic), we also present a detailed stochastic analysis of routing in the transformed space and express analytically the expected value of the number of routing hops.

Self-stabilization in preference-based systems

Participants of a decentralized system often use some local ranking informations, for selection of effective collaborations. We say that such systems are preference-based. For most practical types of preferences, such systems converge towards a unique stable configuration. In this paper, we investigate the speed and quality of the convergence process with respect to the model parameters. Our results provide an interesting insight into the design of system parameters, such as the number of connections or the algorithm for choosing new partners.

Semi-supervised discriminative classification with application to tumorous tissues segmentation of MR brain images

Due to the large data size of 3D MR brain images and the blurry boundary of the pathological tissues, tumor segmentation work is difficult. This paper introduces a discriminative classification algorithm for semi-automated segmentation of brain tumorous tissues. The classifier uses interactive hints to obtain models to classify normal and tumor tissues. A non-parametric Bayesian Gaussian random field in the semi-supervised mode is implemented. Our approach uses both labeled data and a subset of unlabeled data sampling from 2D/3D images for training the model. Fast algorithm is also developed. Experiments show that our approach produces satisfactory segmentation results comparing to the manually labeled results by experts.

Quadtree-based eigendecomposition for pose estimation in the presence of occlusion and background clutter

Eigendecomposition-based techniques are popular for a number of computer vision problems, e.g., object and pose estimation, because they are purely appearance based and they require few on-line computations. Unfortunately, they also typically require an unobstructed view of the object whose pose is being detected. The presence of occlusion and background clutter precludes the use of the normalizations that are typically applied and significantly alters the appearance of the object under detection. This work presents an algorithm that is based on applying eigendecomposition to a quadtree representation of the image dataset used to describe the appearance of an object. This allows decisions concerning the pose of an object to be based on only those portions of the image in which the algorithm has determined that the object is not occluded. The accuracy and computational efficiency of the proposed approach is evaluated on 16 different objects with up to 50% of the object being occluded and on images of ships in a dockyard.