Search

The problem of placing replicas under the widely used time-to-live (TTL)-based consistency scheme is examined. The novel replica replacement scheme is compared, employing real Internet topologies and Web traces, against two existing approaches, which do not take into account consistency management or assume invalidation-based consistency scheme.

The difficulties faced in introducing replicas in network monitored by expiration-based consistency management for replica consistency in order to reduce the overall cost of client accesses and consistency management are examined by studying the communication cost of recursive validations for cascaded replicas. The analytical results show that the nodes not given replicas stimulate a connected subgraph, which is inclusive of the origin server, in the optimal placement scheme.

A real-time wireless system using hybrid automatic repeat request to correct errors is analyzed. Packet errors are modeled by a two-state Markov chain, and batch packet arrivals are allowed. Packets are dropped at the sender if their delays exceed a time limit, possibly after a number of retransmissions. Using the delay-model approach, a closed-form expression of packet-loss probability (PLP) and an approximate formula of wireless effective bandwidth (WEB) satisfying the quality of service requirements have been derived. If Bose-Chaudhuri-Hocquenghem codes are used, an expression estimating the number of correctable bits to minimize the PLP has also been obtained. Moreover, the WEB is found to be independent of the packet size, and the PLP decreases exponentially as the WEB increases. Index Terms--Batch arrivals, delay model, Markov chain, packet-loss probability (PLP), wireless effective bandwidth.

Energy efficiency is an important issue in wireless networks where the nodes are powered by batteries. In this work, we analyze the energy consumption in one-transmitter-multiple-receiver communication and develop scheduling schemes to improve energy efficiency at the transmitter. Our focus is on systems powered by a renewable energy source such as solar power. We consider an environment where both energy and time to access the wireless channel and transmit data are limited, and data destined for different receivers have different values and incur different energy costs. We present optimal scheduling algorithms that selectively transmit data at calculated rates so that the throughput or the total transmission value is maximized under given time limits and energy constraints. Index Terms--Dynamic programming, energy conservation, power control, scheduling, wireless communication.

A framework is proposed for testing the generic temporal properties of media objects in distributed multimedia software systems (DMSS). Experimental results have shown that the proposed framework is effective in detecting errors in temporal properties.

In this work, two Markov chains modeling packet delay have been developed to obtain closed-form solutions for packet loss probabilities and packet delay distributions in a real-time wireless communication environment. Packets with delay constraints are queued at the source and are transmitted one by one with possible retransmissions to correct errors. The first model models packet delay and correlated packet arrivals using a one-dimensional Markov chain. Usually, at least two dimensions are needed in queuing models. The second model is a two-dimensional Markov chain modeling packet delay, correlated channel errors, and correlated arrivals. Both correlated errors and arrivals are known to have significant impact on packet loss. Possible applications of the results are also discussed. Index Terms--Automatic repeat request (ARQ), correlated arrivals, correlated errors, delay model, packet loss probability.

A theoretical study on geographical replication of dynamic Web contents with the objective of minimizing the consistency management costs in terms of update transfers and object reconstruction is presented. A polynomial-time algorithm is proposed to compute the optimal replication strategy, which designates where each object should be replicated and how to keep the replicas up-to-date.

An attempt was made to manage the consistency of cached and replicated contents such as Web objects, using the expiration-based scheme, which was investigated in the context of a single replica. The performance of the heuristic algorithms against two classical graph-theoretic algorithms of tree construction: the shortest-paths tree and the minimum spanning tree, is evaluated.

A novel Markov model is constructed to calculate the packet loss probability and the delay distribution of real-time wireless packets. These packets are transmitted through an erroneous channel modeled by a two-state Markov chain. If a packet transmission is not successful, the packet is retransmitted until a delay limit is exceeded. At that time, the packet is discarded and the transmission of the next packet begins. This packet-dropping process has a significant impact on packet loss probability but is seldom considered in other Markov models. Closed-form solutions are obtained, and simplified expressions assuming highly correlated errors and small error probability are derived. Under these conditions, it is found that the packet loss probability is significantly affected by the delay limit and the transition probability of the channel's remaining in the failure state. On the other hand, the probability is almost independent of the arrival rate provided the rate is not close to one. Index Terms--Automatic repeat request (ARQ), correlated error, delay distribution, Markov model, packet loss probability.

A discussion of dynamic load balancing problems within a hydrodynamic framework is presented, focusing on heterogeneous distributed systems. Topics include communication networks, global potential energy and fairness, liquid flow in a load balancing process, and the effects of topology on convergence rates.

A polynomial solution is suggested to address the problem of minimizing job completion time by allocating task interaction graphs to heterogeneous computers. All processor pairs have the same interprocessor communication cost, to make them appropriate for fully interconnected multiprocessor systems and local area network systems. The availability of adequate communication capacity and homogeneous processors leads to an optimal polynomial solution which can be generalized to produce two faster heuristics.

The processor farm paradigm is commonly used on multicomputers, and is often supported by software components such as a runtime kernel. The design, implementation and modelling of a runtime kernel supporting a processor farm paradigm, is described. The method of obtaining performance models to predict phases of a processor farm through a general topology-independent framework is presented. It concludes that a design must overlap communication with computation, minimize task buffers and have continuous overhead to forward and execute tasks.