Internet of Things offers the infrastructure for smooth functioning of autonomous context-aware devices being connected towards the Cloud. Edge Computing (EC) relies between the IoT and Cloud providing significant advantages. One advantage is to perform local data processing (limited latency, bandwidth preservation) with real time communication among IoT devices, while multiple nodes become hosts of the collected data (reported by IoT devices). In this work, we provide a mechanism for the exchange of data synopses (summaries of extracted knowledge) among EC nodes that are necessary to give the knowledge on the data present in EC environments. The overarching aim is to intelligently decide on when nodes should exchange data synopses in light of efficient execution of tasks. We enhance such a decision with a stochastic optimization model based on the Theory of Optimal Stopping. We provide the fundamentals of our model and the relevant formulations on the optimal time to disseminate data synopses to network edge nodes. We report a comprehensive experimental evaluation and comparative assessment related to the optimality achieved by our model and the positive effects on EC.

In the interval scheduling problem, jobs have known start and end times (referred to as job intervals) and must be assigned to processing nodes for their whole duration. Although the problem originally stems from the resource allocation demands of resident processes in operating systems, it found a renewed interest in the Cloud context, both in IaaS and SaaS, since reservations for virtual machines and services often have known activation intervals. A common objective of interval scheduling is to minimize busy time of machines which relates (among others) to minimizing the number of machines participating in the computation. As a consequence, bin packing techniques have been applied in the past. In this paper we tackle the online version of the problem, whereby future job arrivals are unknown. We propose novel algorithms that work as a pre-processing step to any bin packing scheme by offering recommendations that are enforced in all packing decisions. Job overlaps are used to characterize pairwise job affinity and subsequently provide threshold based job allocation recommendations. Thresholds are calculated using lower bound theoretical analysis upon two extreme workloads (sparse and dense). Experimental evaluation using real world workloads illustrates the merits of our approach against state-of-the-art algorithms.

Programming, most recently in the form of Computational Thinking (CT), is emerging as a new subject in primary schools worldwide. By data-based decision making, teachers, as learning designers, make decisions on instruction design based on a broad range of evidence, such as student assessment scores and classroom teaching observations. Given the current limitations on conclusive, field-proven teaching practices and an underlying “culture” to use as a basis, we turn to pertinent empirical studies that the growing scientific interest on introducing programming in primary school curricula has produced. The hypothesis is that we may overcome the lack of extensive experience in designing a programming course by reviewing the above evidence, in order to frame learning situations and methods.

Tasks management is a very interesting research topic for various application domains. Tasks may have the form of analytics or any other processing activities over the available data. One of the main concerns is to efficiently allocate and execute tasks to produce meaningful results that will facilitate any decision making. The advent of the Internet of Things (IoT) and Edge Computing (EC) defines new requirements for tasks management. Such requirements are related to the dynamic environment where IoT devices and EC nodes act and process the collected data. The statistics of data and the status of IoT/EC nodes are continuously updated. In this paper, we propose a demand- and uncertainty-driven tasks management scheme with the target to allocate the computational burden to the appropriate places. As the proper place, we consider the local execution of a task in an EC node or its offloading to a peer node. We provide the description of the problem and give details for its solution. The proposed mechanism models the demand for each task and efficiently selects the place where it will be executed. We adopt statistical learning and fuzzy logic to support the appropriate decision when tasks' execution is requested by EC nodes. Our experimental evaluation involves extensive simulations for a set of parameters defined in our model. We provide numerical results and reveal that the proposed scheme is capable of deciding on the fly while concluding the most efficient allocation.

One of the fundamental problems encountered by large-scale computing systems, such as clusters and cloud, is to schedule a set of jobs submitted by the users. Each job is characterized by resource demands, as well as start and completion time. Each job must be scheduled to execute on a machine having the required capacity between the start and completion time (referred as interval) of the job. Each machine is defined by a parallelism parameter g that indicates the maximum number of jobs that can be processed by the machine, in parallel. The above problem is referred to as the interval scheduling problem with bounded parallelism. The objective is to minimize the total busy time of all machines. Majority of the solutions proposed in the literature consider homogeneous set of jobs and machines that is a simplified assumption as in practice, heterogeneous jobs and machines are frequently encountered. In this article, we tackle the aforesaid problem with a set of heterogeneous jobs and machines. A major contribution of our work is that the problem is addressed in a novel way by combining a graph-based approach and a dynamic programming approach which is based on a variation of bin packing problem. A greedy algorithm is also proposed by employing only a graph-based approach at the aim to reduce the computational complexity. Experimental results show that the proposed algorithms can significantly reduce the cumulative busy interval over all machines compared with state-of-the-art algorithms proposed in the literature.

The Cloud infrastructure offers to end users a broad set of heterogenous computational resources using the pay-as-you -go model. These virtualized resources can be provisioned using different pricing models like the unreliable model where resources are provided at a fraction of the cost but with no guarantee for an uninterrupted processing. However, the enormous gamut of opportunities comes with a great caveat as resource management and scheduling decisions are increasingly complicated. Moreover, the presented uncertainty in optimally selecting resources has also a negatively impact on the quality of solutions delivered by scheduling algorithms. In this paper, we present a dynamic scheduling algorithm (i.e., the Uncertainty-Driven Scheduling - UDS algorithm) for the management of scientific workflows in Cloud. Our model minimizes both the makespan and the monetary cost by dynamically selecting reliable or unreliable virtualized resources. For covering the uncertainty in decision making, we adopt a Fuzzy Logic Controller (FLC) to derive the pricing model of the resources that will host every task. We evaluate the performance of the proposed algorithm using real workflow applications being tested under the assumption of different probabilities regarding the revocation of unreliable resources. Numerical results depict the performance of the proposed approach and a comparative assessment reveals the position of the paper in the relevant literature.

Service migration between datacenters can reduce the network overhead within a cloud infrastructure; thereby, also improving the quality of service for the clients. Most of the algorithms in the literature assume that the client access pattern remains stable for a sufficiently long period so as to amortize such migrations. However, if such an assumption does not hold, these algorithms can take arbitrarily poor migration decisions that can substantially degrade system performance. In this paper, we approach the issue of performing service migrations for an unknown and dynamically changing client access pattern. We propose an online algorithm that minimizes the inter-datacenter network, taking into account the network load of migrating a service between two datacenters, as well as the fact that the client request pattern may change “quickly”, before such a migration is amortized. We provide a rigorous mathematical proof showing that the algorithm is 3.8-competitive for a cloud network structured as a tree of multiple datacenters. We briefly discuss how the algorithm can be modified to work on general graph networks with an O(log|V|) probabilistic approximation of the optimal algorithm. Finally, we present an experimental evaluation of the algorithm based on extensive simulations.

Virtual machine (VM) migration is a widely used technique in cloud computing systems to increase reliability. There are also many other reasons that a VM is migrated during its lifetime, such as reducing energy consumption, improving performance, maintenance, etc. During a live VM migration, the underlying VM continues being up until all or part of its data has been transmitted from source to destination. The remaining data are transmitted in an off-line manner by suspending the corresponding VM. The longer the off-line transmission time, the worse the performance of the respective VM. The above is because during the off-line data transmission, the VM service is down. Because a running VM's memory is subject to changes, already transmitted data pages may get dirtied and thus needing re-transmission. The decision of when suspending the VM is not a trivial task at all. The above is justified by the fact that when suspending the VM early we may result in transmitting off-line a significant amount of data degrading thus the VM's performance. On the other hand, a long waiting time to suspend the VM may result in re-transmitting a huge amount of dirty data, leading in that way to waste of resources. In this paper, we tackle the joint problem of minimizing both the total VM migration time (reflecting the resources spent during a migration) and the VM downtime (reflecting the performance degradation). The aforementioned objective functions are weighted according to the needs of the underlying cloud provider/user. To tackle the problem, we propose an online deterministic algorithm resulting in an strong competitive ratio, as well as a randomized online algorithm achieving significantly better results against the deterministic algorithm.

Data stream processing has received considerable attention from both research community and industry over the last years. Since latency is a key issue in data stream processing environments, the majority of the works existing in the literature focus on minimizing the latency experienced by the users. The aforementioned minimization takes place by assigning the data stream processing components close to data sources. Server consolidation is also a key issue for drastically reducing energy consumption in computing systems. Unfortunately, energy consumption and latency are two objective functions that may be in conflict with each other. Therefore, when the target function is to minimize energy consumption, the delay experienced by users may be considerable high, and the opposite. For the above reason there is a dire need to design strategies such that by targeting the minimization of energy consumption, there is a graceful degradation in latency, as well as the opposite. To achieve the above, we propose a Pareto-efficient algorithm that tackles the problem of data processing tasks placement simultaneously in both dimensions regarding the energy consumption and latency. The proposed algorithm outputs a set of solutions that are not dominated by any solution within the set regarding energy consumption and latency. The experimental results show that the proposed approach is superior against single-solution approaches because by targeting one objective function the other one can be gracefully degraded by choosing the appropriate solution.

As the compression efficiency of HEVC comes at the cost of high complexity, especially in the encoder's side, improved parallelization techniques that will speedup the encoding process are essential. One of the parallelization granules offered by HEVC is the tile level, whereby a frame is split into a grid like fashion with each resulting rectangular area (tile) being independently encoded. While tile parallelism has attracted research interest, the primary focus was to characterize performance and develop load balancing schemes assuming a one on one tile processor assignment. In this paper we target the problem of adaptively defining tile sizes (upon each frame) based on CTU cost estimation, under the assumption that the number of processors might be less than the number of tiles. It turns out that aside from the tile load balancing aspect, the problem has a processor scheduling sub-component that plays equal role. A fast algorithm is proposed that decides both tile sizing and tile processor assignment in an adaptive per frame fashion. Through experiments with common test sequences, the algorithm is shown to outperform the static tile sizing (one thread per tile) approach, by more than 30% (de-pending on the evaluation scenario) in terms of running time, without affecting video quality.

Minimizing service-level agreement (SLA) violations and energy consumption through server consolidation is of paramount importance for the sustainability of cloud environments. In this paper, we propose an online method to reduce cloud SLA violations by taking into account: (a) the energy consumption of migrating virtual machines and (b) server consolidation techniques to minimize the energy consumption within the system. Rigorous mathematical competitive analysis shows that the proposed method achieves a 2.4 competitive ratio against a cognitive adversary. Our solution is superior compared to the current state of the art algorithms, such as UP-VMC, KMI, MBFD, both theoretically (competitive ratios of other alternatives are unbounded) and empirically through simulations using CloudSim. More specifically, the competitive ratios of state of the art algorithms are unbounded and our proposed methodology reduces the VM migrations and energy consumption by 85% and 45%, respectively. The aforementioned improvement comes at an expense of a small increase in terms of SLA violations. The above results are achieved without the a priori knowledge of VM utilization patterns.

Current networking applications involve the definition and utilization of multiple virtualized resources on top of the available infrastructure. Software defined networks increase the performance compared with legacy systems as any functionality is managed through software. Securing the quality of service in such environments is significant to support novel applications that deliver their results in real time. In this paper, we propose a monitoring mechanism that observes the performance of the virtualized resources and identifies possible quality of service violations. Our model can be applied to any application domain, however, it is adapted to virtualized resources. We rely on a simple model that collects performance data, focuses on multiple parts of a virtualized functions chain and immediately concludes potential violations in real time. The proposed mechanism is incorporated in an SDN controller that is responsible to manage the virtualized resources. We provide an analytical description of the model and through a large set of simulations, we reveal its performance. Our results exhibit the timely identification of quality of service violations even in very dynamic environments where the performance of the network changes continuously.

Recent advances in chip design and integration technologies have led to the development of Single-Chip Cloud computers which are a microcosm of cloud datacenters. Those computers are based on Network-on-Chip (NoC) architectures with deep memory hierarchies. Developing scheduling algorithms to reduce data access latency as well as energy consumption is a major challenge for such architectures. In this paper, we propose a set of algorithms to jointly address the problem of task scheduling and data allocation in a unified approach. Moreover, we present a feasible system model for NoC based multicores considering a three-level memory hierarchy that effectively captures the energy consumed by various elements of system including: processing cores, caches, and NoC subsystem. Simulation results show the superiority of proposed algorithms compared to two state-of-the-art algorithms found in the literature. The experimental results clearly indicate that algorithms performing data and task scheduling in a joint fashion are superior against techniques implementing task and data scheduling separately.

Several virtual machine (VM) placement algorithms have been proposed and studied in the literature with various scopes such as server consolidation or network cost minimization. In most cases, decisions on VM migrations are taken without factoring in directly the data access cost by VMs. In this paper, we investigate the use of data replication in conjunction with the VM assignment problem and target on developing algorithms that decide both on which data should be replicated where and which VM must be migrated so as to minimize the network overhead among traditional cloud and mobile cloud systems. We discuss both the un-capacitated case and the more realistic case whereby datacenters (for the traditional cloud case) and micro-datacenters (for the mobile cloud case) have limited storage and computing capacity. We propose an algorithm based on hyper-graph partitioning to solve the aforementioned problem in an optimal way regarding the unconstrained case and extend it to capture storage and computing capacity constraints. Experimental evaluation shows that the proposed algorithm yields up to 53 percent network overhead reduction when compared to state-of-the-art algorithms found in the literature.

The new video coding standard HEVC (High Efficiency Video Coding) offers the desired compression performance in the era of HDTV and UHDTV, as it achieves nearly 50% bit rate saving compared to H.264/AVC. To leverage the involved computational overhead, HEVC offers three parallelization potentials namely: wavefront parallelization, tile-based and slice-based. In this paper we study slice-based parallelization of HEVC using OpenMP on the encoding part. In particular we delve on the problem of proper slice sizing to reduce load imbalances among threads. Capitalizing on existing ideas for H.264/AVC we develop a fast dynamic approach to decide on load distribution and compare it against an alternative in the HEVC literature. Through experiments with commonly used video sequences, we highlight the merits and drawbacks of the tested heuristics. We then improve upon them for the case of Low-Delay by exploiting GOP structure. The resulting algorithm is shown to clearly outperform its counterparts achieving less than 10% load imbalance in many cases.

With an ever increasing amount of data generated by scientific experiments, social networks and mobile as well as wireless sensor networks, reducing resource consumption by big data applications becomes of paramount importance. Towards this end, filtering data close to the data sources is a common strategy in order to reduce network traffic. Assuming a network of nodes, each potentially generating data and a query in the form of a single operator to be applied in these data, the basic statement of the operator placement problem is: find the best node to place the operator so that the network traffic is minimized. In this paper we study the problem of placing a set of communicating operators exhibiting a tree structure over a tree network of nodes with capacity constraints. We take advantage of our previous work on unconstrained placement in order to develop a new approach enabling both single and group operator migrations using evictions of hosted operators if free space is required. To enhance their applicability, the algorithms work in a distributed asynchronous manner, requiring only minimal knowledge at each network node. Results from simulation experiments show that the proposed algorithms reduce considerably network overhead against their counterparts.

Agent-based middleware platforms for wireless sensor networks (WSNs) have received a lot of attention during the last years, due to their great flexibility in re-programming, monitoring, handling, and optimizing the application as well as the whole system. Even though many algorithms have been proposed for the dynamic placement of agents within the WSN, they do not take into account the coordination aspects of such migrations. This not only may result in slow convergence but also in perpetual oscillations of agent migrations, degrading application and system performance. In this paper, we propose full-coordination, semi-coordination, and non-coordination agent migration strategies, and evaluate their convergence and network overhead. We also provide proofs that convergence is guaranteed when dynamic agent placement algorithms adopt our proposed strategies. Our results show that the semi-coordination strategy is superior in terms of both network overhead and convergence rate.

Operator placement plays a key role in reducing the aggregate network overhead within a wireless sensor network (WSN) to extend battery life and the longevity of the network. Consequently, optimal algorithms for the operator placement problem (OPP) are of paramount importance to WSN performance. Unfortunately, the OPP becomes NP-complete when capacity constraints on the WSN nodes are taken into account. There are many algorithms in the literature that tackle the OPP; however, most of them consider tree-structured query graphs without limitations regarding the operators hosted by the WSN nodes. Therefore, there is a need to propose sophisticated approaches such that the problem is solved in an effective fashion. In this paper, we propose a fully distributed approach that takes into account the WSN node capacity constraints. The proposed approach is thoroughly evaluated through simulations and the results reveal that the proposed approach is superior to several state-of-the-art algorithms, such as DRA, DBA, MCFA, dFNS, and GRAL* found in the literature.

Recent embedded middleware platforms enable the structuring of an application as a set of collaborating agents deployed on various nodes of the underlying wireless sensor network (WSN). Of particular importance is the network cost incurred due to agent communication, which in turn depends on how the agents are placed within the WSN system. In this paper, we present two agent migration algorithms with the aim of minimizing the total network overhead. The first one takes independent single agent migration decisions, while the second one considers groups of agents for migration. Both algorithms work in a fully distributed fashion based on the knowledge available locally at each node, and can be used both for one-shot initial application deployment as well as for the continuous updating of agent placement. We also propose two methodologies to tackle the problem when WSN nodes have limited capacity. We show through theoretical analysis that one of our algorithms (called GRAL$\ast$) always results in an optimal placement, while for the rest of the algorithms, we derive approximation ratios pertaining to their performance. We evaluate the performance of our algorithms through a series of simulation experiments. Results show that group migration algorithms are superior compared to single agent migration algorithms with the performance difference reaching 34% for some settings.

In this paper we tackle the problem of virtual machine (VM) placement onto physical servers to jointly optimize two objective functions. The first objective is to minimize the total energy spent within a cloud due to the servers that are commissioned to satisfy the computational demands of VMs. The second objective is to minimize the total network overhead incurred due to: (a) communicational dependencies between VMs, and (b) the VM migrations performed for the transition from an old assignment scheme to a new one. We study different methodologies for solving the aforementioned problem. The first approach is based on VM packing algorithms that optimize the above objective functions separately, reaching a single solution. The other approach is to tackle simultaneously the two optimization targets and define a set of non-dominating solutions. Performance evaluation using simulation experiments reveals interesting trade-offs between energy consumption and network load.

With the development of mobile code frameworks for embedded systems, an application can be structured as a set of cooperating components (agents) that are placed on the nodes of the system in a flexible way. Reducing the network traffic caused by the application components is a crucial issue for the increase in the lifetime of wireless embedded systems, since it is widely known that the communication cost plays the most significant role in the energy consumption of embedded devices. To this end, most placement algorithms place or move an agent towards the center of gravity of the communication workload. However, if the target node does not have enough capacity, the attempt is usually aborted. In this paper, we introduce eviction-enabled algorithms that allow nodes to free capacity by forcing a locally hosted agent to move to another node, even at a loss, to accept a new and potentially more beneficial agent. To the best of our knowledge, this is the first time that agents are evicted by local hosts to enable beneficial agent migrations and eventually improve the total network cost. In this paper, we provide algorithms tackling the aforementioned problem in a fully distributed manner. We also present and discuss the results of extensive simulations, showing that eviction-enabled algorithms can outperform their counterparts by up to 300%.

We assume a wireless sensor and actuator network with nodes that can harvest energy from the environment, and an application deployed in this network, which is structured as a set of cooperating mobile components that can be placed on any node that provides the required sensor and actuator resources. We propose algorithms that take into account the energy consumption rate of agents as well as energy reserves and harvesting rate of nodes, and decide about the migration of agents in order to improve application availability. Initial evaluation results via simulation show that application availability can be greatly improved compared to having a static application placement.

Recent embedded middleware initiatives enable the structuring of an application as a set of collaborating agents deployed in the various sensing/actuating entities of the system. Of particular importance is the incurred cost due to agent communication which in terms depends on agent positions in the system. In this paper we present GRAL a grouping algorithm that migrates groups of agents with the aim of minimizing communication. The algorithm works in a distributed fashion based on knowledge available locally at each node and can be used both for one-shot initial application deployment and for the continuous updating of agent placement. Through simulation experiments under various scenarios we evaluate the algorithm, comparing the solution quality reached against the optimal obtained from exhaustive search.

Given two replication schemes Xoldand Xnew, the replica transfer scheduling problem (RTSP) aims at reaching Xnew, starting from Xold, with minimal implementation cost. In this paper we generalize the problem description to include special cases, where deadlocks can occur while in the process of implementing Xnew. We address this impediment by introducing artificial (dummy) transfers. We then prove that RTSP-decision is NP-complete and propose two kinds of heuristics. The first attempts to replace dummy transfers with valid ones, while the second minimizes the implementation cost. Experimental evaluation of the algorithms illustrates the merits of our approach.

Given a set of tasks with certain characteristics, e.g., data size, estimated execution time and a set of processing nodes with their own parameters, the goal of task scheduling is to allocate tasks at nodes so that the total makespan is minimized. The problem has been studied under various assumptions concerning task and node parameters with the resulting problem statements usually being NP-complete. List scheduling (LS) heuristics such as MaxMin and MinMin together with genetic algorithms (GAs) were applied in the past to find solutions. In this paper we investigate new heuristics for both the LS and the GA paradigm with the specific aim of improving the performance of the standard algorithms when task computations involve large data transfers. Experimental results under various environment assumptions illustrate the merits of the new algorithms.

With the advent of the grid, task scheduling in heterogeneous environments becomes more and more important. Of particular interest is the fact that especially in scientific experiments a non negligible amount of data must be transferred to the processing node before a task can commence execution. Given bandwidth constraints, scheduling both computations and data transfers is required. In this paper we first develop a suitable model that captures heterogeneity in the processing nodes while imposing communication constraints. We proceed by proposing scheduling heuristics with the aim of minimizing the total make span of a set of independent tasks. Through a series of experiments we illustrate the potential of a particular heuristic that is based on backfilling

The Internet now offers more than just simple information to the users. Decision makers can now issue analytical, as opposed to transactional, queries that involve massive data (such as, aggregations of millions of rows in a relational database) in order to identify useful trends and patterns. Such queries are often referred to as Online-analytical processing (OLAP). Typically, pages carrying query results do not exhibit temporal locality and, therefore, are not considered for caching at Internet proxies. In OLAP processing, this is a major problem as the cost of these queries is significantly larger than that of the transactional queries. This paper proposes a technique to reduce the response time for OLAP queries originating from geographically distributed private LANs and issued through the Web toward a central data warehouse (DW) of an enterprise. An active caching scheme is introduced that enables the LAN proxies to cache some parts of the data, together with the semantics of the DW, in order to process queries and construct the resulting pages. OLAP queries arriving at the proxy are either satisfied locally or from the DW, depending on the relative access costs. We formulate a cost model for characterizing the respective latencies, taking into consideration the combined effects of both common Web access and query processing. We propose a cache admittance and replacement algorithm that operates on a hybrid Web-OLAP input, outperforming both pure-Web and pure-OLAP caching schemes

The Replica Placement Problem (RPP) aims at creating a set of duplicated data objects across the nodes of a distributed system in order to optimize certain criteria. Typically, RPP formulations fall into two categories: static and dynamic. The first assumes that access statistics are estimated in advance and remain static, and, therefore, a one-time replica distribution is sufficient (IRPP). In contrast, dynamic methods change the replicas in the network potentially upon every request. This paper proposes an alternative technique, named Continuous Replica Placement Problem (CRPP), which falls between the two extreme approaches. CRPP can be defined as: Given an already implemented replication scheme and estimated access statistics for the next time period, define a new replication scheme, subject to optimization criteria and constraints. As we show in the problem formulation, CRPP is different in that the existing heuristics in the literature cannot be used either statically or dynamically to solve the problem. In fact, even with the most careful design, their performance will be inferior since CRPP embeds a scheduling problem to facilitate the proposed mechanism. We provide insight on the intricacies of CRPP and propose various heuristics.

Notoriously high delays in accessing Web pages loaded with massive multimedia objects are highly undesirable. Inspired by the requirements of news agencies and other information providers to include multimedia content in their pages, this paper proposes a new solution to the problem of minimizing the Web response time. We consider an environment that consists of a central multimedia repository and various sites physically dispersed. Our approach is based on simultaneous downloading of some of the embedded multimedia objects from the repository, and the rest from the regional servers. We propose a cost model to formalize the relative benefits of the proposed scheme, and design an algorithm that replicates multimedia objects so as to take advantage of concurrency in data transferring. An extensive simulation study evaluates the performance of the proposed replication policy under storage and processing capacity constraints, as well as with various network transfer rates. Comparisons are carried out with alternative schemes.

The Internet is offering more than just regular Web pages to the users. Decision makers can now issue analytical, as opposed to transactional, queries that involve massive data (such as, aggregations of millions of rows in a relational database) in order to identify useful trends and patterns. Such queries are referred to as On-Line-Analytical-Processing (OLAP) queries. Typically, pages carrying query results do not exhibit temporal locality and, therefore, are not considered for caching at WWW proxies. In OLAP processing, this becomes a major hurdle as the cost of such queries is much higher than traditional transactional queries. This paper proposes a systematic technique to reduce the response time for OLAP queries originating from geographically distributed private LANs and issued through the Web towards the central data warehouse (DW) of an enterprise. An active caching scheme is proposed that enables the LAN proxies to cache some parts of the data, together with the semantics of the DW in order to process queries and construct the resulting pages. OLAP queries arriving at the proxy are either satisfied locally or from the DW, depending on the relative access costs. We formulate a cost model for characterizing the latencies of these queries, taking into consideration normal Web access as well as analytical processing. We propose a cache admittance and replacement algorithm that outperforms a widely accepted caching algorithm.

Creating replicas of frequently accessed objects across a read-intensive network can result in large bandwidth savings which, in turn, can lead to reduction in user response time. On the contrary, data replication in the presence of writes incurs extra cost due to multiple updates. The set of sites at which an object is replicated constitutes its replication scheme. Finding an optimal replication scheme that minimizes the amount of network traffic given read and write frequencies for various objects, is NP-complete in general. We propose two heuristics to deal with this problem for static read and write patterns. The first is a simple and fast greedy heuristic that yields good solutions when the system is predominantly read-oriented. The second is a genetic algorithm that through an efficient exploration of the solution space provides better solutions for cases where the greedy heuristic does not perform well. We also propose an extended genetic algorithm that rapidly adapts to the dynamically changing characteristics such as the frequency of reads and writes for particular objects.

Dynamic replication algorithms aim at allocating, migrating and deleting copies of an object over various Internet hosts, according to the access patterns exhibited online, so as to improve object proximity for the end-users and/or load-balance the servers. Most of the existing algorithms try to disseminate the objects of an entire Internet Service Provider (ISP), without taking into account the needs and characteristics of specific web sites with large commercial value. In this paper we tackle the replication problem in an Internet environment, inspired by the need of news agencies and other information providers to include in their pages multimedia content without incurring high access delays. We consider an environment that consists of a central multimedia repository and various physically dispersed sires. We propose a cost model to formalize the replication of multimedia objects located at the repository which can result in decreasing the download time. Taking into account implementation issues, such as the storage and processing capacity constraints, the proposed replication policy is evaluated and compared with alternatives including an ideal LRU caching scheme. Qualitative comparisons with the other replication schemes are reported as well.