A two-segment model is introduced here to model the probing process in a network with the tree topology that subsequently leads to four types of explicit estimators to estimate the loss rates of the links within the network. All of the estimators are derived by the maximum likelihood principle, where one of them is developed from an estimator that was used but neglected previously. The estimators are proved to be either unbiased or asymptotic unbiased, and a set of formulae are derived to compute the efficiencies and variances of the estimates obtained by the estimators. One of the formulae shows that if a path is divided into two segments, the variance of the estimates obtained for the pass rate of a segment is equal to the variance of the pass rate of the path divided by the square of the pass rate of the other segment. A number of theorems and corollaries are derived from the formulae to evaluate the performance of an estimator. One of them shows that the estimators derived from the neglected ones are the best in terms of efficiency and computation complexity for the networks of the tree topology.

The use of multipath routing in overlay networks is a promising solution to improve performance and availability of Internet applications, without the replacement of the existing TCP/IP infrastructure. In this paper, we propose an approach to distribute data over multiple overlay paths that is able to improve Quality of Service (QoS) metrics, such as the data transfer time, loss, and throughput. By using the Imbedded Markov Chain technique, we demonstrate that the system under analysis, observed at specific instants, possesses the Markov property. We therefore cast the data distribution problem into the Markov Decision Process (MDP) framework, and design a computationally efficient algorithm named Online Policy Iteration (OPI), to solve the optimization problem on the fly. The proposed approach is applied to the problem of multipath data distribution in various wired/wireless network scenarios, with the objective of minimizing the data transfer time as well as the delay and losses. Through both intensive ns-2 simulations with data collected from real heterogeneous networks and experiments over real networks, we show the superior performance of the proposed traffic control mechanism in comparison with two classical schemes, that are Weighted Round Robin and Join the Shortest Queue.

Providing a high level of the path diversity is a substantial criterion in designing an overlay network. Given a underlying network infrastructure, the diversity of the overlay paths largely depends on how the overlay nodes, i.e. relays, are placed. In this paper, the problem of optimal relay placement is studied, and the goal is to maximize the diversity of the overlay paths while minimizing the number of relays. To tackle this multi-objective optimization problem, a novel genetic algorithm (GA) is applied hybridizing the standard GA and k-shortest path algorithms. By studying 6 real ISP topologies, we find that there exist non-unique solutions, which provide nearly the same level of the path diversity. In those solutions, only few locations are not replaceable allowing a great flexibility in the overlay network deployment. Perhaps surprisingly, these places do not include all those nodes with the highest number of links. The reason is that those nodes with the highest number of links are usually crossed by the default routing paths. Therefore, the overlay paths tend not to crossing them. We also notice that the number of relays required to maintain a high level of the path diversity is only 5% - 10% of the total number of network nodes depending on the topologies. We believe that our findings are useful for designing and deploying multi-path overlay networks.

In this paper, we study the problem of optimal data transfer over multiple overlay paths. Instead of solving the problem from the single controller point of view, we adopt the game theory perspective to consider the problem from a more realistic view where multiple traffic controllers competing for the shared bandwidth. We formulate the problem as a general- sum stochastic game, and a reinforcement learning technique namely Correlated-Q Learning is implemented to derive the best- possible strategy, i.e. the strategy to play correlated equilibrium (CE) for each controller. Through a proof-of-concept simulation scenario with 2 overlay paths and 2 controllers, we show that by playing cooperative strategies, e.g. CE, the controllers can achieve superior performance compared to acting selfishly. The result emphasizes that considering the problem of optimal multipath data transfer from the single controller perspective is inadequate.

Maintaining performance and reliability in wireless networks is a challenging task due to the nature of wireless channels. Multipath data transmission has been used in wired scenarios to reduce latency, improve throughput, and - when/where possible - balance the load. In this paper, we propose an approach for multipath data transmission over wireless networks. We demonstrate that the problem under study can be formulated as a Markov decision process (MDP) and we propose an algorithm called On-line Policy Iteration (OPI), to solve the formulated MDP in real time. We verified the proposed approach using simulations with ns-2 and data collected from real heterogeneous wired/wireless networks. The results indicate that we improve both delay and loss characteristics of end-to-end wireless communications outperforming the classical multi-path schemes including Round Robin and Join the Shortest Queue.

Recently some algorithms have been proposed to clean post-training rule populations evolved by XCS, a state of the art Learning Classifier System (LCS). We present an algorithm to extract optimal rules, which we refer to as signatures, during the operation of UCS, a recent variant of XCS. In a benchmark binary valued dataset our method seconds the generalization and optimality hypotheses for UCS and provide mechanisms for retrieving all maximally general rules in real time. In real valued problems, where precise realization of decision boundaries is often not possible, our algorithm is able to retrieve near optimal representations with the help of a modified subsumption operator. The algorithm is able to reduce the processing time asymptotically and provides a mechanism for early stopping of the learning process.

A long horizon end-to-end delay forecast, if possible, will be a breakthrough in traffic engineering. This paper introduces a hybrid approach to forecast end-to-end delays using wavelet transforms in combination with neural network and pattern recognition techniques. The discrete wavelet transform is implemented to decompose delay time series into a set of wavelet components, which is comprised of an approximate component and a number of detail components. Thus, it turns the problem of long horizon delay forecasting into a set of shorter horizon wavelet coefficient forecasting problems. A recurrent multi-layered perceptron neural network is applied to forecast coefficients of the wavelet approximate component, which represents the trend of the delay series. The k-nearest neighbors technique is used to forecast coefficients of the wavelet detail components, which reflect the burstiness of background traffic. The proposed approach has been verified in both simulation and over real heterogeneous networks showing promising results in terms of averaged normalized root mean square error. In addition, when compared to some existing and well known approaches it presents the superior performance.

Loss tomography as a key component of network tomography receives considerable attention in recent years and a number of methods based on maximum likelihood estimate (MLE) and Bayesian estimate have been proposed. However, most methods proposed so far only target a treelike network, their application in practice is limited because of this. To overcome this limitation, we in this paper propose three estimation methods for networks with a general topology. We start our description from the tree structure and provide the insight into the connection between observations and loss rates, and present a closed form MLE that is obtained by solving a set of log-likelihood equations. In addition, a top down algorithm based on the closed form MLE is developed to estimate link-level loss rates from observation. Then, the closed form MLE is extended to cover a general topology consisting of a number of intersected trees. Finally, the three approximating methods, called modified weighted average, combine probe top down (CPTD) and hybrid bottom up and top down (IIBT), are proposed to estimate the loss rates of a general network. All algorithms proposed in this paper are analyzed mathematically and evaluated through simulations which show the efficiency and accuracy of the methods.

Loss tomography has received considerable attention in recent years. A number of methods, either based on maximum likelihood (ML) or Bayesian reasoning, have been proposed to estimate the loss rates of a network, and almost all of them use an iterative approximating method to search for the maximum in a multi-dimensional space. Those approaches lead to the concerns of their scalability and accuracy. To overcome the problems, a bottom up method has been proposed recently, that is a near optimal solution. In this paper, we present a closed form maximum likelihood estimate (MLE) that can be implemented in a top down method. Then, the bottom up method is compared with the top down one that shows they are little difference. More, simulations conducted under various conditions show that these two methods have almost identical results. Apart from that, the bottom up approach is independent to the number of sources used to send probes to receivers, this makes it a good candidate to estimate the loss rates of a general topology.

Loss tomography as a key component of network tomography receives considerable attention in recent years and a number of methods based on maximum likelihood estimate (MLE) and Bayesian estimate have been proposed. However, most methods proposed so far only target a tree-like network. In this paper, we derive a direct expression to unveil the correlation between observations and loss rates in a network with a general topology. Based on the expression, we propose four algorithms to estimate the loss rates of such a network: called modified weighted average, combine probe top down (CPTD), hybrid bottom up and top down (HBT) and MCMC. The four algorithms proposed in this paper are compared against the MVWA, which show that the CPTD and HBT are pseudo maximum likelihood estimates and more accurate than weight average algorithms. This finding is confirmed through simulations.

Loss tomography aims to obtain the loss rate of each link in a network by end-to-end measurement. Based on loss rates we can understand the traffic flows and identify bottlenecks. All methods proposed so far rely on statistical inference to achieve this goal, and most of them are based on maximum likelihood to infer hidden information. However, there is a lack of studying the solution space of the inference, which may create uncertainty for the loss rates identified by the maximum likelihood approach since the solution identified could trap to a local maximum. In this paper, we reformulate the inference process into a nonlinear programming problem and concentrate on studying the solution space of the non-linear programming problem. We find when losses occurred on a link is modeled as Bernoulli process, the solution space is concave, which ensures an iterative approximating algorithm can identify the global maximum.

Shared object Distributed Shared Memory (DSM) minimizes the problem of false sharing by allowing programmer to control the sharing size. This shared object approach for distributed parallel programming works well in task parallelism but not in data parallelism. When the data of a shared object is being modified, a lock on that object must be enforced to exclude any concurrent access on that same object. If the shared data within an object is large, internal false sharing would become a problem. We present a multi-locking mechanism for shared object DSM which allows multiple locks be applied to the different data sets of a shared object and thus enhances its concurrency power.

We consider scheduling soft real-time tasks for a cluster which consists of multiple servers. Each server provides identical services where an incoming task can be assigned to one of the servers. The question we investigate is which assignment produces the best performance given two alternative approaches to queue the arriving tasks: a centralized approach or a distributed one. A missed deadline criterion is used to evaluate these approaches. The influence of dispatching policies on the performance of the distributed approach is also considered.

ATM protocols are connection oriented and migration of a mobile computer can therefore require rerouting of ATM connections while minimizing violation of Quality of Service specified for these connections. This implies that the handover process needs to be performed with small delay, minimal cell loss and no change in cell sequence. The problem is magnified by the fact that high-speed networks such as ATM will often deliver services to real time multimedia applications, such as video and audio, which have stringent Quality of Service requirements. In this paper, we describe a handover protocol that preprocesses partial connections for cells incurring long handover delays. In this protocol, cells are clustered and the clusters are divided into crust and core cells which are handled differently during handovers. The protocol minimizes the degradation of Quality of Service during handovers.

Three basic organizations have been proposed to construct the task queues for a shared memory multiprocessor system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantages of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out that the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload becomes heavier. We further identified the cause of this problem. We propose the use of a forest structure to provide load balancing and contention minimization.

Load balancing has been extensively studied by simulation and positive results were acheived in most of the research. With the increasing availability of distributed systems, a few experiments have been carried out on different systems. These experimental studies either depend on task initiation or task initiation plus task migration. We present the results of a 0 study of load balancing using a centralized policy to manage the load on a set of processors; it was carried out on an Amoeba system which consists of a set of 386s, linked by 10 Mbps Ethernet. The results on one hand indicate the necessity of a load balancing facility for a distributed system. On the other hand the results question the impact of using process migration to increase system performance under the configuration used in our experiments.

This paper presents a parallel approach to the development of a real-time system for recognition of textured objects. In order to find an efficient and effective approach to identify and localize objects in textured images invariant of translation, rotation and scale changes and occlusion, we propose a new method which involves dynamic texture feature extraction and hierarchical image matching. Based on our previous work, we extend the concept of interesting points and develop a dynamic detection procedure on texture energy image which is in conjunction with Laws' texture energy concept and our mask tuning scheme. The search for the best fit between two objects in terms of Hausdorff distance is guided through an interesting point pyramid from coarse level to fine level. In addition, unlike current approaches which mostly rely on specialized multiprocessor architectures for fast processing, we use a distributed workstation cluster to support parallelism, which provides a different approach to real-time computing and is applicable to many classes of tasks.

The design of a process migration mechanism for the Amoeba distributed operating system is described. The primary motivation for this implementation is to carry out experimental and realistic studies of load balancing algorithms for a distributed operating system. Our aim has been the implementation of a mechanism which is general, efficient and fully transparent and which is reliable in the presence of network and processor failures.>