Le besoin des applications de streaming multimédia en temps réel sur Internet ne cesse d’accroître. Dans ce contexte, les réseaux Pair-à-Pair (P2P) jouent un rôle prépondérant afin d’assurer une transmission robuste et extensible (scalable) de contenu multimédia à grand-échelle. Cependant, le déploiement des applications de streaming multimédia à travers les réseaux P2P présente plusieurs verrous. En effet, les applications de streaming vidéo nécessitent une garantie de performances temps réel en termes de : délai minimal de bout-en-bout, faible taux de perte de paquets et garantie de la bande passante. Par ailleurs, un réseau P2P est composé d’un ensemble de terminaux interconnectés à travers des réseaux hétérogènes, n’ayant pas forcément les mêmes caractéristiques requises afin d’offrir la même qualité vidéo aux clients finaux.Dans cette thèse, nous analysons différents problèmes liés au streaming en-direct (Live) ou à la demande (VoD) de la vidéo sur les réseaux P2P, et nous proposons un ensemble de mécanismes pour y remédier. / There is an increasing demand for efficient deployment of real-time multimedia streaming applications over Internet. In this context, Peer-to-Peer (P2P) networks are playing an important role for supporting robust and scalable transmission of multimedia content to large-scale and massive receivers. P2P networks consist of different heterogeneous networks and devices, which may not have symmetric characteristics to offer the same video quality to end clients. The deployment of streaming applications such as live and on-demand over P2P networks is challenging. Indeed, video streaming applications require real-time performance guarantee in terms of low end-to-end delay, low packet loss and guaranteed available bandwidth. Moreover, P2P video streaming also experiences the problems of long start-time and churn-induced instability. The situation leads to affect the viewing experience of the users in P2P networks.The aim of this thesis is to analyze these issues and to propose quality-aware mechanisms for both live and on-demand streaming over P2P networks. Our contributions in this dissertation are threefold. First, we propose a small world overlay organization mechanism allowing efficient organization of peers to reduce the end-to-end delay for live streaming applications. Second, we propose a mechanism for cooperative prefetching with differentiated chunks scheduling suitable for P2P video-on-demand (VoD) to efficiently handle seek operations while reducing the response latency and increasing the hit ratio. Finally, we present a smoothing mechanism for layered streaming in P2P networks. The mechanism aims to reduce the number of layer changes under varying network conditions while at the same time achieving a high delivery ratio.

Det finns idag fortfarande ett behov av att minska den uppfattade responstiden för användare. Som ett sätt att förbättra prestandan föreslås förhämtning. Förhämtning kan ytterligare förbättra prestandan av AJAX. Med prestanda menas primärt responstiden men bandbredden är också en viktig faktor. Problemet handlar om hur prestandan påverkas av AJAX förhämtning baserad på historiska hints jämfört mot vanlig AJAX. Metoden är experiment och prestandan av 2 versioner av en webbplats för kursinformation jämförs. Under genomförandet byggdes siterna, förhämtningsversionen har en initial förhämtning baserad på historik samt pågående förhämtning baserad på sökningar och interaktion. Tester visar på att responstiden förbättras med förhämtningen, mellan 63 % och 29 % beroende på träffbilden av förhämtningen under en session. Bandbredden ökade dock som ett resultat mellan 61 % och 33 % på de olika sessionerna.

Esta tesis estudia la aplicación a la World Wide Web (WWW) de las técnicas de prebúsqueda desde un punto de vista realista y práctico. La prebúsqueda se aplica a la web para reducir la latencia percibida por los usuarios ya que, básicamente, consiste en predecir y preprocesar los siguientes accesos de los usuarios. Hasta ahora, la literatura disponible acerca de la prebúsqueda web se ha concentrado en cuestiones teóricas y no ha considerado algunos de los problemas que aparecen al implementar la técnica en condiciones reales. Por otra parte, los trabajos de investigación existentes usan para la evaluación modelos simplificados que no consideran cómo los aspectos prácticos afectan realmente a la implementación de una técnica de prebúsqueda. Además, apenas unos pocos trabajos han usado índices de prestaciones que sean relevantes para los usuarios en la evaluación de los beneficios que la prebúsqueda puede lograr. Con objeto de superar estas tres restricciones se ha desarrollado Delfos, un entorno de prebúsqueda web que implementa predicción y prebúsqueda en un sistema real, puede integrarse en la arquitectura web sin realizar modificaciones en los protocolos web estándar, y es compatible con los programas existentes. Delfos también puede usarse para evaluar y comparar técnicas de prebúsqueda y algoritmos de predicción así como ayudar en el diseño de otros nuevos ya que proporciona información estadística detallada de los experimentos llevados a cabo. A modo de ejemplo, Delfos se ha usado para proponer, probar y evaluar una nueva técnica (Predecir en la Prebúsqueda, PAP) que es capaz de reducir considerablemente la latencia percibida por el usuario sin costes adicionales respecto al mecanismo de prebúsqueda básico. Los algoritmos de predicción propuestos en la literatura de investigación que alcanzan la mayor precisión incurren en un alto coste computacional, y esto representa un problema para incluirlos en sistemas reales. Para aminorar este inconveniente, en esta tesis se propone un nuevo algoritmo de predicci on de bajo coste, (Referrer Graph, RG). / De La Ossa Pérez, BA. (2011). Web Prefetching Techniques in Real Environments [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/15574 / Palancia

No description available.

Low-latency, high throughput mechanisms to retrieve data become increasingly crucial as the cyber and cyber-physical systems pour out increasing amounts of data that often must be analyzed in an online manner. Generally, as the data volume increases, the marginal utility of an ``average'' data item tends to decline, which requires greater effort in identifying the most valuable data items and making them available with minimal overhead. We believe that data analytics driven mechanisms have a big role to play in solving this needle-in-the-haystack problem. We rely on the claim that efficient pattern discovery and description, coupled with the observed predictability of complex patterns within many applications offers significant potential to enable many I/O optimizations. Our research covers exploitation of storage hierarchy for data driven caching and tiering, reduction of distance between data and computations, removing redundancy in data, using sparse representations of data, the impact of data access mechanisms on resilience, energy consumption, storage usage, and the enablement of new classes of data driven applications. For caching and prefetching, we offer a powerful model that separates the process of access prediction from the data retrieval mechanism. Predictions are made on a data entity basis and used the notions of ``context'' and its aspects such as ``belief'' to uncover and leverage future data needs. This approach allows truly opportunistic utilization of predictive information. We elaborate on which aspects of the context we are using in areas other than caching and prefetching different situations and why it is appropriate in the specified situation. We present in more details the methods we have developed, BeliefCache for data driven caching and prefetching and AVSC for pattern mining based compression of data. In BeliefCache, using a belief, an aspect of context representing an estimate of the probability that the storage element will be needed, we developed modular framework BeliefCache, to make unified informed decisions about that element or a group. For the workloads we examined we were able to capture complex non-sequential access patterns better than a state-of-the-art framework for optimizing cloud storage gateways. Moreover, our framework is also able to adjust to variations in the workload faster. It also does not require a static workload to be effective since modular framework allows for discovering and adapting to the changes in the workload. In AVSC, using an aspect of context to gauge the similarity of the events, we perform our compression by keeping relevant events intact and approximating other events. We do that in two stages. We first generate a summarization of the data, then approximately match the remaining events with the existing patterns if possible, or add the patterns to the summary otherwise. We show gains over the plain lossless compression for a specified amount of accuracy for purposes of identifying the state of the system and a clear tradeoff in between the compressibility and fidelity. In other mentioned research areas we present challenges and opportunities with the hope that will spur researchers to further examine those issues in the space of rapidly emerging data intensive applications. We also discuss the ideas how our research in other domains could be applied in our attempts to provide high performance data access. / Computer and Information Science

The New Macroeconometrics may succinctly be described as the application of Bayesian analysis to the class of macroeconomic models called Dynamic Stochastic General Equilibrium (DSGE) models. A prominent local example from this research area is the development and estimation of the RAMSES model, the main macroeconomic model in use at Sveriges Riksbank.   Bayesian estimation of DSGE models is often computationally demanding. In this thesis fast algorithms for Bayesian inference are developed and tested in the context of the state space model framework implied by DSGE models. The algorithms discussed in the thesis deal with evaluation of the DSGE model likelihood function and sampling from the posterior distribution. Block Kalman filter algorithms are suggested for likelihood evaluation in large linearised DSGE models. Parallel particle filter algorithms are presented for likelihood evaluation in nonlinearly approximated DSGE models. Prefetching random walk Metropolis algorithms and adaptive hybrid sampling algorithms are suggested for posterior sampling. The generality of the algorithms, however, suggest that they should be of interest also outside the realm of macroeconometrics.

Nous assistons aujourd’hui à une croissance vertigineuse des volumes de données. Cela exerce une pression sur les infrastructures de stockage et les logiciels de traitement de données comme les Systèmes de Gestion de Base de Données (SGBD). De nouvelles technologies ont vu le jour et permettent de réduire la pression exercée par les grandes masses de données. Nous nous intéressons particulièrement aux nouvelles technologies de mémoires secondaires comme les supports de stockage SSD (Solid State Drive) à base de mémoire Flash. Les supports de stockage SSD offrent des performances jusqu’à 10 fois plus élevées que les supports de stockage magnétiques. Cependant, ces nouveaux supports de stockage offrent un nouveau modèle de performance. Cela implique l’optimisation des coûts d’E/S pour les algorithmes de traitement et de gestion des données. Dans cette thèse, nous proposons un modèle des coûts d’E/S sur SSD pour les algorithmes de traitement de données. Ce modèle considère principalement le volume des données, l’espace mémoire alloué et la distribution des données. Nous proposons également un nouvel algorithme de tri en mémoire secondaire : MONTRES. Ce dernier est optimisé pour réduire le coût des E/S lorsque le volume de données à trier fait plusieurs fois la taille de la mémoire principale. Nous proposons enfin un mécanisme de pré-chargement de données : Lynx. Ce dernier utilise un mécanisme d’apprentissage pour prédire et anticiper les prochaines lectures en mémoire secondaire. / The growing volume of data poses a real challenge to data processing software like DBMS (DataBase Management Systems) and data storage infrastructure. New technologies have emerged in order to face the data volume challenges. We considered in this thesis the emerging new external memories like flash memory-based storage devices named SSD (Solid State Drive).SSD storage devices offer a performance gain compared to the traditional magnetic devices.However, SSD devices offer a new performance model that involves 10 cost optimization for data processing and management algorithms.We proposed in this thesis an 10 cost model to evaluate the data processing algorithms. This model considers mainly the SSD 10 performance and the data distribution.We also proposed a new external sorting algorithm: MONTRES. This algorithm includes optimizations to reduce the 10 cost when the volume of data is greater than the allocated memory space by an order of magnitude. We proposed finally a data prefetching mechanism: Lynx. This one makes use of a machine learning technique to predict and to anticipate future access to the external memory.

Le contexte de la thèse porte sur le contrôle des réseaux de distribution de contenu à la demande. La performance des systèmes distribués interactifs dépend essentiellement sur la prévision du comportement de l'utilisateur et la bande passante en tant que ressource de réseau critique. Le préchargement est une approche prédictive bien connu dans le World Wide Web ce qui évite les délais de réponse en exploitant un temps d'arrêt que permet d'anticiper les futures demandes de l'utilisateur et prend avantage des ressources réseau disponibles. Le contrôle de préchargement est une opération vitale pour les systèmes à la demande interactifs où la réponse instantanée est le facteur crucial pour la réussite du système. Le contrôleur en ce type de système interactif fonctionne dans un environnement incertain et rend séquences de décisions à court et long terme effets stochastique. La difficulté est alors de déterminer à chaque état du système les contenus préchargés dans le cache. Le plan de préchargement pendant une session en flux continu interactif peut être modélisé comme un problème de décision séquentielle par les processus de décision de Markov (MDP). Nous nous concentrons sur le problème de contrôle de préchargement, dans lequel le contrôleur cherche à atteindre l'état du système à coût zéro aussi vite que possible. Nous modélisons ce problème de contrôle comme un problème de programmation dynamique stochastique négatif dans lequel nous minimisons le coût total prévu. Dans ce contexte, nous avons abordé les questions de recherche suivantes: 1) Comment fournir un politique de préchargement optimale/ approximative optimale qui maximise l'utilisation de la bande passante tout en minimisant les coûts de blocage et de la latence de l'utilisateur engagés sur le chemin? 2) Comment exploiter la structure du modèle de contrôle de préchargement pour aider efficacement calculer la politique de contrôle de préchargement avec la réduction des efforts de calcul et la mémoire de stockage? 3) Comment mener une étude d'évaluation pour évaluer le préchargement de différents algorithmes heuristiques basée sur le contexte de l'optimisation au lieu du cadre de l'empirique / simulation. Pour l'étude de notre problème de recherche, nous avons développé notre modèle MDP de préchargement, PREF-CT, nous avons établi ses propriétés théoriques et nous avons résolu par l'algorithme Value Iteration comme algorithme MDP pour calculer la politique de préchargement optimale. Pour calcul de la politique de préchargement optimale efficace, nous avons détecté une structure spéciale qui réalise un modèle de contrôle plus compact. Cette structure spéciale permet de développer deux algorithmes différents stratégiquement qui améliorent la complexité du calcul de la politique de préchargement optimale: - la première est « ONE-PASS » le second est « TREE-DEC ». Pour surmonter le problème de la dimensionnalité résultant du calcul de la politique de préchargement optimale, nous avons proposé l'algorithme de préchargement heuristique: « Relevant Blocks Prefetching » (RBP). Pour évaluer et comparer le préchargement politiques calculés par des algorithmes de préchargement heuristiques différents, nous avons présenté un cadre fondé sur des différentes mesures de performance. Nous avons appliqué le cadre proposé sous différentes configurations de coûts et différents comportements des utilisateurs pour évaluer les politiques de préchargement calculées par notre algorithme de préchargement proposé; RBP. Par rapport aux politiques de préchargement optimales, l'analyse expérimentale a prouvé des performances significatives des politiques de préchargement de l'heuristique du RBP algorithme. En outre, l'algorithme heuristique de préchargement; RBP se distingue par une propriété de clustériser qui est important pour réduire considérablement la mémoire nécessaire pour stocker la politique de préchargement. / The thesis context is concerned with the control of theOn-demand contents distribution networks. The performance of suchinteractive distributed systems basically depends on the prediction ofthe user behavior and the bandwidth as a critical network resource.Prefetching is a well-known predictive approach in the World Wide Webwhich avoids the response delays by exploiting some downtime thatpermits to anticipate the user future requests and takes advantage ofthe available network resources. Prefetching control is a vitaloperation for the On-demand interactive systems where the instantaneousresponse is the crucial factor for the system success. The controller insuch type of interactive system operates in an uncertain environment andmakes sequences of decisions with long and short term stochasticeffects. The difficulty, then, is to determine at every system statewhich contents to prefetch into the cache. The prefetching plan duringan interactive streaming session can be modeled as a sequential decisionmaking problem by a Markov Decision Process (MDP). We focus on theprefetching control problem in which the controller seeks to reach aZero-Cost system state as quickly as possible. We model this controlproblem as a Negative Stochastic Dynamic Programming problem in which weminimize the undiscounted total expected cost. Within this context, weaddressed the following research questions: 1) How to provide anoptimal/approximate-optimal prefetching policy that, maximizes thebandwidth utilization while minimizes the user's blocking and latencycosts incurred along the way? 2) How to exploit structure in theprefetching control model to help efficiently compute such prefetchingcontrol policy with both computational efforts and storage memoryreduction? 3) How to conduct a performance evaluation study to evaluatedifferent prefetching heuristic algorithms based on the context of thecontrol optimization rather than the context of theempirical/simulation. For studying our research problem, we developedour MDP prefetching control model, PREF-CT, we established itstheoretical properties and we solved it by the Value Iteration algorithmas MDP algorithm for computing the optimal prefetching policy. Forcomputing the optimal prefetching policy efficiently, we detected aspecial structure that achieves more compact control model. This specialstructure permits to develop two strategically different algorithmswhich improve the complexities of computing the optimal prefetchingpolicy: - the first one is the ONE-PASS which is based mainly on solvinga system of linear equations simultaneously in only one iteration,whereas the second is the TREE-DEC which is based on Markov decisiontree decomposition in which sequential sets of systems of equations aresolved. For overcoming the problem of the curse of dimensionalityresulting from the computation of the optimal prefetching policy, weproposed the prefetching heuristic algorithm: the Relevant BlocksPrefetching algorithm (RBP). For evaluating and comparing prefetchingpolicies computed by different prefetching heuristic algorithms, wepresented a framework based on different performance measures. Weapplied the suggested framework under different costs configurations anddifferent user behaviors to evaluate the prefetching policies computedby our proposed prefetching heuristic algorithm; the RBP. Compared tothe optimal prefetching policies, the experimental analysis provedsignificant performance of the prefetching policies of the RBP heuristicalgorithm. In addition, the RBP prefetching heuristic algorithm isdistinguished by a clustering property which is of importance to reducesignificantly the memory necessary to store the prefetching policy tothe controller.

More and more modern computer applications, from business decision support to scientific data analysis, utilize visualization techniques to support exploratory activities. Various tools have been proposed in the past decade to help users better interpret data using such display techniques. However, most do not scale well with regard to the size of the dataset upon which they operate. In particular, the level of cluttering on the screen is typically unacceptable and the performance is poor. To solve the problem of cluttering at the interface level, visualization tools have recently been extended to support hierarchical views of the data, with support for focusing and drilling-down using interactive brushes. To solve the scalability problem, we now investigate how best to couple such a visualization tool with a database management system without losing the real-time characteristics. This integration must be done carefully, since visual user interactions implemented as main memory operations do not map directly into efficient database operations. The main efficiency issue when doing this integration is to avoid the recursive processing required for hierarchical data retrieval. For this problem, we have develop a tree labeling method, called MinMax tree, that allows the movement of the on-line recursive processing into an off-line precomputation step. Thus, at run time, the recursive processing operations translate into linear cost range queries. Secondly, we employ a main memory access strategy to support incremental loading of data into the main memory. The techniques have been incorporated into XmdvTool, a multidimensional visual exploration tool, in order to achieve scalability. The tool now successfully scales up to datasets of the order 10^5-10^7 records. Lastly, we report experimental results that illustrate the impact of the proposed techniques on the system's overall performance.

The term Linked Data refers to connected information sources comprising structured data about a wide range of topics and for a multitude of applications. In recent years, the conceptional and technical foundations of Linked Data have been formalized and refined. To this end, well-known technologies have been established, such as the Resource Description Framework (RDF) as a Linked Data model or the SPARQL Protocol and RDF Query Language (SPARQL) for retrieving this information. Whereas most research has been conducted in the area of generating and publishing Linked Data, this thesis presents novel approaches for improved management. In particular, we illustrate new methods for analyzing and processing SPARQL queries. Here, we present two algorithms suitable for identifying structural relationships between these queries. Both algorithms are applied to a large number of real-world requests to evaluate the performance of the approaches and the quality of their results. Based on this, we introduce different strategies enabling optimized access of Linked Data sources. We demonstrate how the presented approach facilitates effective utilization of SPARQL endpoints by prefetching results relevant for multiple subsequent requests. Furthermore, we contribute a set of metrics for determining technical characteristics of such knowledge bases. To this end, we devise practical heuristics and validate them through thorough analysis of real-world data sources. We discuss the findings and evaluate their impact on utilizing the endpoints. Moreover, we detail the adoption of a scalable infrastructure for improving Linked Data discovery and consumption. As we outline in an exemplary use case, this platform is eligible both for processing and provisioning the corresponding information. / Unter dem Begriff Linked Data werden untereinander vernetzte Datenbestände verstanden, die große Mengen an strukturierten Informationen für verschiedene Anwendungsgebiete enthalten. In den letzten Jahren wurden die konzeptionellen und technischen Grundlagen für die Veröffentlichung von Linked Data gelegt und verfeinert. Zu diesem Zweck wurden eine Reihe von Technologien eingeführt, darunter das Resource Description Framework (RDF) als Datenmodell für Linked Data und das SPARQL Protocol and RDF Query Language (SPARQL) zum Abfragen dieser Informationen. Während bisher hauptsächlich die Erzeugung und Bereitstellung von Linked Data Forschungsgegenstand war, präsentiert die vorliegende Arbeit neuartige Verfahren zur besseren Nutzbarmachung. Insbesondere werden dafür Methoden zur Analyse und Verarbeitung von SPARQL-Anfragen entwickelt. Zunächst werden daher zwei Algorithmen vorgestellt, die die strukturelle Ähnlichkeit solcher Anfragen bestimmen. Beide Algorithmen werden auf eine große Anzahl von authentischen Anfragen angewandt, um sowohl die Güte der Ansätze als auch die ihrer Resultate zu untersuchen. Darauf aufbauend werden verschiedene Strategien erläutert, mittels derer optimiert auf Quellen von Linked Data zugegriffen werden kann. Es wird gezeigt, wie die dabei entwickelte Methode zur effektiven Verwendung von SPARQL-Endpunkten beiträgt, indem relevante Ergebnisse für mehrere nachfolgende Anfragen vorgeladen werden. Weiterhin werden in dieser Arbeit eine Reihe von Metriken eingeführt, die eine Einschätzung der technischen Eigenschaften solcher Endpunkte erlauben. Hierfür werden praxisrelevante Heuristiken entwickelt, die anschließend ausführlich mit Hilfe von konkreten Datenquellen analysiert werden. Die dabei gewonnenen Erkenntnisse werden erörtert und in Hinblick auf die Verwendung der Endpunkte interpretiert. Des Weiteren wird der Einsatz einer skalierbaren Plattform vorgestellt, die die Entdeckung und Nutzung von Beständen an Linked Data erleichtert. Diese Plattform dient dabei sowohl zur Verarbeitung als auch zur Verfügbarstellung der zugehörigen Information, wie in einem exemplarischen Anwendungsfall erläutert wird.