<p>Webbservrar på Internet använder idag dynamiska webbsidor genererade med hjälp av databassystem för sina användare. Detta har lett till en stor belastning på webbservrar och en metod för att minska belastningen är att använda cachning. Detta arbete implementerar och utför tester på en specifik cachningsalgoritm kallad Online View Selection i ett webbspelsscenario. Ett potentiellt problem identifieras hos algoritmen som kan leda till att inaktuell information levereras till klienten och algoritmen modifieras för att hantera problemet. Testresultaten visar att både den modifierade algoritmen och originalet ger likvärdig prestanda. Den modifierade algoritmen visar sig fungera men problemet med den ursprungliga algoritmen uppkommer sällan i webbspelsscenariot.</p>

Studies of secondary seed dispersal by small mammals have largely been focused on the interaction between nut-bearing tree species and sciurid rodents such as squirrels, and on heteromyid rodents in the southwestern United States. However, there is now evidence that wind-dispersed tree species such as pines also undergo a process of secondary seed dispersal, where animals redistribute (cache) seeds that have already fallen to the ground, often in microhabitats more suitable for successful seed germination. In Florida sandhill, where fire suppression has threatened wind-dispersed longleaf pine ( Pinus palustris) by encouraging the encroachment of hardwoods such as sand live oak ( Quercus geminata), secondary seed dispersal may be an important factor in determining community composition and persistence of longleaf pine systems. Using a combination of seed depots and seed predator exclosures, I looked at both longleaf pine and sand live oak in terms of whether small animals such as squirrels ( Sciurus carolinensis) and cotton mice ( Peromyscus gossypinus) cache the seeds, and where the seeds of these two tree species best germinate. Since sand live oak acorns are prone to infestation by weevils ( Curculio spp.), I also examined whether nut condition affects acorn germination potential. I found that longleaf pine seeds are cached by small mammals to a small degree. While these seeds are not moved great distances from where they originate, they are often redistributed into microhabitats that promote successful seed germination. Caging experiments indicated that seeds were most likely to germinate when buried in open areas between adult trees, and to some degree, under shrub cover. On the other hand, sand live oak acorns appear to face heavy predation by large seed predators such as raccoons ( Procyon lotor) and wild pigs (Sus scrofa). Those acorns that do escape predation, including weevil-infested acorns, may provide an opportunity for seedling establishment. However, it appears that sand live oak depends heavily on vegetative sprouting for regeneration. This suggests that even in the absence of fire, longleaf pines in Florida sandhill are able to persist through secondary seed dispersal by small animals coupled with heavy seed predation on competing sand live oak.

No description available.

Modern processor architectures suffer from an ever increasing gap between processor and memory performance. The current memory-register model attempts to hide this gap by a system of cache memory. Line Associative Registers(LARs) are proposed as a new system to avoid the memory gap by pre-fetching and associative updating of both instructions and data. This thesis presents a fully LAR-based architecture, targeting a previously developed instruction set architecture. This architecture features an execution pipeline supporting SWAR operations, and a memory system supporting the associative behavior of LARs and lazy writeback to memory.

Cloud Computing represents a recent paradigm shift that enables users to share and remotely access high-powered computing resources (both infrastructure and software/services) contained in off-site data centers thereby allowing a more efficient use of hardware and software infrastructures. This growing trend in cloud computing, combined with the demands for Big Data and Big Data analytics, is driving the rapid evolution of datacenter technologies towards more cost-effective, consumer-driven, more privacy conscious and technology agnostic solutions. This dissertation is dedicated to taking a systematic approach to develop system-level techniques and algorithms to tackle the challenges of large-scale data processing in the Cloud and scaling and delivering privacy-aware services with anytime-anywhere availability. We analyze the key challenges in effective provisioning of Cloud services in the context of MapReduce-based parallel data processing considering the concerns of cost-effectiveness, performance guarantees and user-privacy and we develop a suite of solution techniques, architectures and models to support cost-optimized and privacy-preserving service provisioning in the Cloud. At the cloud resource provisioning tier, we develop a utility-driven MapReduce Cloud resource planning and management system called Cura for cost-optimally allocating resources to jobs. While existing services require users to select a number of complex cluster and job parameters and use those potentially sub-optimal per-job configurations, the Cura resource management achieves global resource optimization in the cloud by minimizing cost and maximizing resource utilization. We also address the challenges of resource management and job scheduling for large-scale parallel data processing in the Cloud in the presence of networking and storage bottlenecks commonly experienced in Cloud data centers. We develop Purlieus, a self-configurable locality-based data and virtual machine management framework that enables MapReduce jobs to access their data either locally or from close-by nodes including all input, output and intermediate data achieving significant improvements in job response time. We then extend our cloud resource management framework to support privacy-preserving data access and efficient privacy-conscious query processing. Concretely, we propose and implement VNCache: an efficient solution for MapReduce analysis of cloud-archived log data for privacy-conscious enterprises. Through a seamless data streaming and prefetching model in VNCache, Hadoop jobs begin execution as soon as they are launched without requiring any apriori downloading. At the cloud consumer tier, we develop mix-zone based techniques for delivering anonymous cloud services to mobile users on the move through Mobimix, a novel road-network mix-zone based framework that enables real time, location based service delivery without disclosing content or location privacy of the consumers.

Distributed key-value systems have been widely used as elemental components of many Internet-scale services at sites such as Amazon, Facebook and Twitter. This thesis examines a system design approach to scale existing key-value systems, both horizontally and vertically, by carefully engineering and integrating techniques that are grounded in recent theory but also informed by underlying architectures and expected workloads in practice. As a case study, we re-design FAWN-KV—a distributed key-value cluster consisting of “wimpy” key-value nodes—to use less memory but achieve higher throughput even in the worst case. First, to improve the worst-case throughput of a FAWN-KV system, we propose a randomized load balancing scheme that can fully utilize all the nodes regardless of their query distribution. We analytically prove and empirically demonstrate that deploying a very small but extremely fast load balancer at FAWN-KV can effectively prevent uneven or dynamic workloads creating hotspots on individual nodes. Moreover, our analysis provides service designers a mathematically tractable approach to estimate the worst-case throughput and also avoid drastic overprovisioning in similar distributed key-value systems. Second, to implement the high-speed load balancer and also to improve the space efficiency of individual key-value nodes, we propose novel data structures and algorithms, including the cuckoo filter, a Bloom filter replacement that is high-speed, highly compact and delete-supporting, and optimistic cuckoo hashing, a fast and space-efficient hashing scheme that scales on multiple CPUs. Both algorithms are built upon conventional cuckoo hashing but are optimized for our target architectures and workloads. Using them as building blocks, we design and implement MemC3 to serve transient data from DRAM with high throughput and low-latency retrievals, and SILT to provide cost-effective access to persistent data on flash storage with extremely small memory footprint (e.g., 0.7 bytes per entry)

The past decade has witnessed the fast development of peer-assisted video ondemand (PA-VoD) systems, which have attracted millions of online users. The efforts on improving the quality of video programs have never ceased since the beginning, and nowadays offering high-definition (HD) channels has become a common practice. However, compared with standard-definition (SD) channels, HD channels have to sustain a higher streaming rate to peers, which is a challenging task. In real systems, HD channels often suffer from poor streaming quality, or impose a heavy burden on the servers. This thesis conducts an in-depth study on peer cache and upload bandwidth management at the same time for multi-channel PA-VoD systems, where HD and SD channels coexist with different bandwidth and cache requirements. The objective is to minimize the server bandwidth consumption, and thus the maintenance cost of VoD service providers. The solution is cross-channel allocation (or view-upload decoupling), i.e., making SD channels help HD viewers with the surplus peer-contributed resources. The management of these resources includes bandwidth allocation and caching strategies. We first propose a generic modeling framework to capture the essential characteristics of PA-VoD systems: the demand and supply of bandwidth from peers. Our modeling framework can be customized or extended to model a variety of caching strategies, including FIFO, passive caching, and active caching with different user behaviors. We then apply the modeling framework to two representative scenarios: stationary scenarios, where the channels have fixed popularity; and non-stationary scenarios, in which a new movie is released, and peers enter the channel in a flash-crowd manner. We prove using our models that passive caching is efficient for stationary user behaviors, and derive the optimal caching solutions when the channels in the system demonstrate different popularity evolutions, i.e., with non-stationary behaviors. With the insights gained from our modeling work, we design effective centralized heuristic algorithms and practical distributed strategies for peer cache replacement and upload bandwidth allocation, with a near-optimal utilization of these resources. We propose centralized and distributed cross-channel allocation, and also extend the substreaming technique from live streaming to VoD systems, where it demonstrates its extreme feasibility. Our extensive simulation results verify the efficacy of these heuristic and practical strategies. / Graduate / 0984 / changlecsu@gmail.com

This thesis covers three main issues in content delivery with a focus on placement algorithms of replica servers and replica contents. In a content delivery system, the location of replicas is very important as perceived by a quotation: Closer is better. However, considering the costs incurred by replication, it is a challenge to deploy replicas in a cost-effective manner. The objective of our work is to optimally select the location of replicas which includes sites for replica server deployment, servers for replica contents hosting, and en-route caches for object caching. Our solutions for corresponding applications are presented in three parts of the work, which makes significant contributions for designing scalable, reliable, and efficient systems for Internet content delivery. In the first part, we define the Fault-Tolerant Facility Allocation (FTFA) problem for the placement of replica servers, which relaxes the well known Fault-Tolerant Facility Location (FTFL) problem by allowing an integer (instead of binary) number of facilities per site. We show that the problem is NP-hard even for the metric version, where connection costs satisfy the triangle inequality. We propose two efficient algorithms for the metric FTFA problem with approximation factors 1.81 and 1.61 respectively, where the second algorithm is also shown to be (1.11,1.78)- and (1,2)-approximation through the proposed inverse dual fitting technique. The first bi-factor approximation result is further used to achieve a 1.52-approximation algorithm and the second one a 4-approximation algorithm for the metric Fault-Tolerant k-Facility Allocation problem, where an upper bound of facility number (i. e. k) applies. In the second part, we formulate the problem of QoS-aware content replication for parallel access in terms of combined download speed maximization, where each client has a given degree of parallel connections determined by its QoS requirement. The problem is further converted into the metric FTFL problem and we propose an approximation algorithm which is implemented in a distributed and asynchronous manner of communication. We show theoretically that the cost of our solution is no more than 2F* + RC*, where F* and C* are two components of any optimal solution while R is the maximum number of parallel connections. Numerical experiments show that the cost of our solutions is comparable (within 4% error) to the optimal solutions. In the third part, we establish mathematical formulation for the en-route web caching problem in a multi-server network that takes into account all requests (to any server) passing through the intermediate nodes on a request/response path. The problem is to cache the requested object optimally on the path so that the total system gain is maximized. We consider the unconstrained case and two QoS-constrained cases respectively, using efficient dynamic programming based methods. Simulation experiments show that our methods either yield a steady performance improvement (in the unconstrained case) or provide required QoS guarantees. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1461921 / Thesis (Ph.D.) - University of Adelaide, School of Computer Science, 2009

In recent years, adaptive HTTP streaming protocols have become the de facto standard in the industry for the distribution of live and video-on-demand content over the Internet. In this thesis, we solve the problem of distributing adaptive HTTP live video streams to a large number of viewers using peer-to-peer (P2P) overlays. We do so by assuming that our solution must deliver a level of quality of user experience which is the same as a CDN while trying to minimize the load on the content provider’s infrastructure. Besides that, in the design of our solution, we take into consideration the realities of the HTTP streaming protocols, such as the pull-based approach and adaptive bitrate switching. The result of this work is a system which we call SmoothCache that provides CDN-quality adaptive HTTP live streaming utilizing P2P algorithms. Our experiments on a real network of thousands of consumer machines show that, besides meeting the the CDN-quality constraints, SmoothCache is able to consistently deliver up to 96% savings towards the source of the stream in a single bitrate scenario and 94% in a multi-bitrate scenario. In addition, we have conducted a number of pilot deployments in the setting of large enterprises with the same system, albeit tailored to private networks. Results with thousands of real viewers show that our platform provides an average offloading of bottlenecks in the private network of 91.5%. These achievements were made possible by advancements in multiple research areas that are also presented in this thesis. Each one of the contributions is novel with respect to the state of the art and can be applied outside of the context of our application. However, in our system they serve the purposes described below. We built a component-based event-driven framework to facilitate the development of our live streaming application. The framework allows for running the same code both in simulation and in real deployment. In order to obtain scalability of simulations and accuracy, we designed a novel flow-based bandwidth emulation model. In order to deploy our application on real networks, we have developed a network library which has the novel feature of providing on-the-fly prioritization of transfers. The library is layered over the UDP protocol and supports NAT Traversal techniques. As part of this thesis, we have also improved on the state of the art of NAT Traversal techniques resulting in higher probability of direct connectivity between peers on the Internet. Because of the presence of NATs on the Internet, discovery of new peers and collection of statistics on the overlay through peer sampling is problematic. Therefore, we created a peer sampling service which is NAT-aware and provides one order of magnitude fresher samples than existing peer sampling protocols. Finally, we designed SmoothCache as a peer-assisted live streaming system based on a distributed caching abstraction. In SmoothCache, peers retrieve video fragments from the P2P overlay as quickly as possible or fall back to the source of the stream to keep the timeliness of the delivery. In order to produce savings, the caching system strives to fill up the local cache of the peers ahead of playback by prefetching content. Fragments are efficiently distributed by a self-organizing overlay network that takes into account many factors such as upload bandwidth capacity, connectivity constraints, performance history and the currently being watched bitrate. / <p>QC 20131122</p>

Um desafio fundamental em ICN (do inglês Information-Centric Networking) é desenvolver Content Stores (ou seja, unidades de cache) que satisfaçam três requisitos: espaço de armazenamento grande, velocidade de operação rápida e custo acessível. A chamada Hierarchical Content Store (HCS) é uma abordagem promissora para atender a esses requisitos. Ela explora a correlação temporal entre requisições para prever futuras solicitações. Por exemplo, assume-se que um usuário que solicita o primeiro minuto de um filme também solicitará o segundo minuto. Teoricamente, essa premissa permitiria transferir proativamente conteúdos de uma área de cache relativamente grande, mas lenta (Layer 2 - L2), para uma área de cache mais rápida, porém menor (Layer 1 - L1). A estrutura hierárquica tem potencial para incrementar o desempenho da CS em uma ordem de grandeza tanto em termos de vazão como de tamanho, mantendo o custo. Contudo, o desenvolvimento de HCS apresenta diversos desafios práticos. É necessário acoplar as hierarquias de memória L2 e L1 considerando as suas taxas de transferência e tamanhos, que dependem tanto de aspectos de hardware (por exemplo, taxa de leitura da L2, uso de múltiplos SSD físicos em paralelo, velocidade de barramento, etc.), como de software (por exemplo, controlador do SSD, gerenciamento de memória, etc.). Nesse contexto, esta tese apresenta duas contribuições principais. Primeiramente, é proposta uma arquitetura para superar os gargalos inerentes ao sistema através da paralelização de múltiplas HCS. Em resumo, o esquema proposto supera desafios inerentes à concorrência (especificamente, sincronismo) através do particionamento determinístico das requisições de conteúdos entre múltiplas threads. Em segundo lugar, é proposta uma metodologia para investigar o desenvolvimento de HCS explorando técnicas de emulação e modelagem analítica conjuntamente. A metodologia proposta apresenta vantagens em relação a metodologias baseadas em prototipação e simulação. A L2 é emulada para viabilizar a investigação de uma variedade de cenários de contorno (tanto em termos de hardware como de software) maior do que seria possível através de prototipação (considerando as tecnologias atuais). Além disso, a emulação emprega código real de um protótipo para os outros componentes do HCS (por exemplo L1, gerência das camadas e API) para fornecer resultados mais realistas do que seriam obtidos através de simulação. / A key challenge in Information Centric Networking (ICN) is to develop cache units (also called Content Store - CS) that meet three requirements: large storage space, fast operation, and affordable cost. The so-called HCS (Hierarchical Content Store) is a promising approach to satisfy these requirements jointly. It explores the correlation between content requests to predict future demands. Theoretically, this idea would enable proactively content transfers from a relatively large but slow cache area (Layer 2 - L2) to a faster but smaller cache area (Layer 1 - L1). Thereby, it would be possible to increase the throughput and size of CS in one order of magnitude, while keeping the cost. However, the development of HCS introduces several practical challenges. HCS requires a careful coupling of L2 and L1 memory levels considering their transfer rates and sizes. This requirement depends on both hardware specifications (e.g., read rate L2, use of multiple physical SSD in parallel, bus speed, etc.), and software aspects (e.g., the SSD controller, memory management, etc.). In this context, this thesis presents two main contributions. First, we propose an architecture for overcoming the HCS bottlenecks by parallelizing multiple HCS. In summary, the proposed scheme overcomes racing condition related challenges through deterministic partitioning of content requests among multiple threads. Second, we propose a methodology to investigate the development of HCS exploiting emulation techniques and analytical modeling jointly. The proposed methodology offers advantages over prototyping and simulation-based methods. We emulate the L2 to enable the investigation of a variety of boundary scenarios that are richer (regarding both hardware and software aspects) than would be possible through prototyping (considering current technologies). Moreover, the emulation employs real code from a prototype for the other components of the HCS (e.g., L1, layers management and API) to provide more realistic results than would be obtained through simulation.