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.

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.

DAg-stream: Distributed video adaptation for overlay streaming to heterogeneous devices

Combining the advantages of Peer-to-Peer (P2P) content distribution concept and metadata driven adaptation of videos in compressed domain, in this paper, we propose a simple but scalable design of distributed adaptation and overlay streaming using MPEG-21 gBSD, called DAg-stream. The objective is not only to shift the bandwidth burden to end participating peers, but also to move the computation load for adapting video contents away from dedicated media-streaming/adaptation servers. It is an initiative to merge the adaptation operations and the P2P streaming basics to support the expansion of context-aware mobile P2P systems. DAg-stream organizes mobile and heterogeneous peers into overlays. For each video, a separate overlay is formed. No control message is exchanged among peers for overlay maintenance. We present a combination of infrastructure-centric and application end-point architecture. The infrastructure-centric architecture refers to a tree controller, named DAg-master, which is responsible for tree/overlay administering and maintenance. The application end-point architecture refers to video sharing, streaming and adaptation by the participating resourceful peers. The motivation for this work is based on the experiences and lessons learned so far about developing a video adaptation system for heterogeneous devices. In this article, we present our architecture and some experimental evaluations supporting the design concept for overlay video streaming and online adaptation.

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.

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.

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 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.

Quantitatively measuring object-oriented couplings

One key to several quality factors of software is the way components are connected. Software coupling can be used to estimate a number of quality factors, including maintainability, complexity, and reliability. Object-oriented languages are designed to reduce the number of dependencies among classes, which encourages separation of concerns and should reduce the amount of coupling. At the same time, the object-oriented language features change the way the connections are made, how they must be analyzed, and how they are measured. This paper discusses software couplings based on object-oriented relationships between classes, specifically focusing on types of couplings that are not available until after the implementation is completed, and presents a static analysis tool that measures couplings among classes in Java packages. Data from evaluating the tool on several open-source projects are provided. The coupling measurement is based on source code, which has the advantage of being quantitative and more precise than previous measures, but the disadvantage of not being available before implementation, and thus not useful for some predictive efforts.

Imputation techniques for multivariate missingness in software measurement data

The problem of missing values in software measurement data used in empirical analysis has led to the proposal of numerous potential solutions. Imputation procedures, for example, have been proposed to ‘fill-in’ the missing values with plausible alternatives. We present a comprehensive study of imputation techniques using real-world software measurement datasets. Two different datasets with dramatically different properties were utilized in this study, with the injection of missing values according to three different missingness mechanisms (MCAR, MAR, and NI). We consider the occurrence of missing values in multiple attributes, and compare three procedures, Bayesian multiple imputation, k Nearest Neighbor imputation, and Mean imputation. We also examine the relationship between noise in the dataset and the performance of the imputation techniques, which has not been addressed previously. Our comprehensive experiments demonstrate conclusively that Bayesian multiple imputation is an extremely effective imputation technique.

An experiment on the role of graphical elements in architecture visualization

The evolution and maintenance of large-scale software systems requires first an understanding of its architecture before delving into lower-level details. Tools facilitating the architecture comprehension tasks by visualization provide different sets of configurable, graphical elements to present information to their users. We conducted a controlled experiment that exemplifies the critical role of such graphical elements when aiming at understanding the architecture. In our setting, a different configuration of graphical elements had significant influence on program comprehension tasks. In particular, a 63% gain in effectiveness in architectural analysis tasks was achieved simply by changing the configuration of the graphical elements of the same tool. Based on the results, we claim that significant effort should be spent on the configuration of architecture visualization tools and that configurability should be a requirement for such tools.

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.

Software quality analysis by combining multiple projects and learners

When building software quality models, the approach often consists of training data mining learners on a single fit dataset. Typically, this fit dataset contains software metrics collected during a past release of the software project that we want to predict the quality of. In order to improve the predictive accuracy of such quality models, it is common practice to combine the predictive results of multiple learners to take advantage of their respective biases. Although multi-learner classifiers have been proven to be successful in some cases, the improvement is not always significant because the information in the fit dataset sometimes can be insufficient. We present an innovative method to build software quality models using majority voting to combine the predictions of multiple learners induced on multiple training datasets. To our knowledge, no previous study in software quality has attempted to take advantage of multiple software project data repositories which are generally spread across the organization. In a large scale empirical study involving seven real-world datasets and seventeen learners, we show that, on average, combining the predictions of one learner trained on multiple datasets significantly improves the predictive performance compared to one learner induced on a single fit dataset. We also demonstrate empirically that combining multiple learners trained on a single training dataset does not significantly improve the average predictive accuracy compared to the use of a single learner induced on a single fit dataset.

On detecting faults for Boolean expressions

Fault based testing aims at detecting hypothesized faults based on specifications or program source. There are some fault based techniques for testing Boolean expressions which are commonly used to model conditions in specifications as well as logical decisions in program source. The MUMCUT strategy has been proposed to generate test cases from Boolean expressions. Moreover, it detects eight common types of hypothesized faults provided that the original expression is in irredundant disjunctive normal form, IDNF. Software practitioners are more likely to write the conditions and logical decisions in general form rather than IDNF. Hence, it is interesting to investigate the fault detecting capability of the MUMCUT strategy with respect to general form Boolean expressions. In this article, we perform empirical studies to investigate the fault detection capability of the MUMCUT strategy with respect to general form Boolean expressions as well as mutated expressions. A mutated expression can be obtained from the original given Boolean expression by making a syntactic change based on a particular type of fault.

An experimental investigation of personality types impact on pair effectiveness in pair programming

In this paper, pair programming is empirically investigated from the perspective of developer personalities and temperaments and how they affect pair effectiveness. A controlled experiment was conducted to investigate the impact of developer personalities and temperaments on communication, pair performance and pair viability-collaboration. The experiment involved 70 undergraduate students and the objective was to compare pairs of heterogeneous developer personalities and temperaments with pairs of homogeneous personalities and temperaments, in terms of pair effectiveness. Pair effectiveness is expressed in terms of pair performance, measured by communication, velocity, design correctness and passed acceptance tests, and pair collaboration-viability measured by developers’ satisfaction, knowledge acquisition and participation. The results have shown that there is important difference between the two groups, indicating better communication, pair performance and pair collaboration-viability for the pairs with heterogeneous personalities and temperaments. In order to provide an objective assessment of the differences between the two groups of pairs, a number of statistical tests and stepwise Discriminant Analysis were used.

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.

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.

Theory of relative defect proneness

In this study, we investigated the functional form of the size-defect relationship for software modules through replicated studies conducted on ten open-source products. We consistently observed a power-law relationship where defect proneness increases at a slower rate compared to size. Therefore, smaller modules are proportionally more defect prone. We externally validated the application of our results for two commercial systems. Given limited and fixed resources for code inspections, there would be an impressive improvement in the cost-effectiveness, as much as 341% in one of the systems, if a smallest-first strategy were preferred over a largest-first one. The consistent results obtained in this study led us to state a theory of relative defect proneness (RDP): In large-scale software systems, smaller modules will be proportionally more defect-prone compared to larger ones. We suggest that practitioners consider our results and give higher priority to smaller modules in their focused quality assurance efforts.

Evaluation of preliminary data analysis framework in software cost estimation based on ISBSG R9 Data

Previous research has argued that preliminary data analysis is necessary for software cost estimation. In this paper, a framework for such analysis is applied to a substantial corpus of historical project data (ISBSG R9 data), selected without explicit bias. The consequent analysis yields sets of dominant variables, which are then used to construct project effort estimation models. Performance of the predictors on the raw variables and the extracted sets of variables is then measured in terms of Mean Magnitude of Relative Error (MMRE), Median of Magnitude of Relative Error (MdMRE) and prediction at levels 0.05, 0.1, and 0.25. The results from the comparative evaluation suggest that more accurate prediction models can be constructed for the selected prediction techniques. The framework processed predictor variables are statistically significant, at the 95% confidence level for both parametric techniques and one non-parametric technique. The results are also compared with the latest published results obtained by other research based on the same data set. The comparison indicates that, the models constructed using framework processed data are generally more accurate.