No description available.

BlobTree modelling has been used in several solid modelling packages to rapidly prototype models by making use of boolean and sketch-based modelling. Using these two techniques, a user can quickly create complex models as combinations of simple primitives and sketched objects. Because the BlobTree is based on continuous field-values, it offers a lot of possibilities to create and control smooth transitions between surfaces, something more complicated in other modelling approaches. In addition, the data required to describe a BlobTree is very compact. Despite these advantages, the BlobTree has not yet been integrated into state of the art industrial workflows to create models. This thesis identifies some shortcomings of the BlobTree, presents potential solutions to those problems and demonstrates an application that makes use of the BlobTree's compact representation. A main criticism is that the evaluation of a large BlobTree can be quite expensive, and, therefore, many applications are limited in the complexity of models that can be created interactively. This work presents an alternative way of traversing a BlobTree that lowers the time to calculate field-values by at least an order of magnitude. As a result, the limit of model complexity is raised for interactive modelling applications. In some domains, certain models need more than one designer or engineer to be created. Often, several iterations of a model are shared between multiple participants until it is finalized. Because the description of a BlobTree is very compact, it can be synchronized efficiently in a collaborative modelling environment. This work presents CollabBlob, an approach to collaborative modelling based on the BlobTree. CollabBlob is lock-free, and provides interactive feedback for all the participants, which helps with a fast iteration in the modelling process. In order to extend the range of models that can be created within CollabBlob, two areas of BlobTree modelling are improved in the context of this thesis. CAD modelling often makes use of a feature called filleting to add additional surface features, which could be caused by a manufacturing process. Filleting in general creates smooth transitions between surfaces, something that the BlobTree can do with less mathematical complexity than approaches needed in Constructive Solid Geometry (CSG), in the case of fillets between primitives. However, little research has been done on the construction of fillets between surfaces of a single BlobTree primitive. This work outlines Angle-Based Filleting and the Surface Fillet Curve, two solutions to improve the specification of fillets in the BlobTree. Sketch-based implicit modelling generates 3D shapes from 2D sketches by sampling the drawn shape and using the samples to create the implicit field via variational interpolation. Additional samples inside and outside the sketched shape are needed to generate a field compatible with BlobTree modelling and state of the art approaches use offset curves of the sketch to generate these samples. The approach presented in this work reduces the number of sample points, thus accelerating the interpolation time and improving the resulting implicit field. / Graduate / 0984 / herbert.grasberger@gmail.com

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>

[pt] Aplicações que usam CORBA como plataforma de comunicação geralmente possuem restrições ao serem executadas em ambientes compostos por mais de um domínio administrativo. Este fato é particularmente verdade quando as aplicações precisam atravessar firewalls/NAT. Além do mais, não existe atualmente uma solução padronizada e adotada por todos os ORBs, obrigando as aplicações que utilizam este enfatizar{middleware} a adotarem soluções proprietárias que muitas vezes não são adequadas ao ambiente em que as aplicações funcionam (e.g. impossibilidade de abertura de portas no firewall). Este trabalho apresenta e avalia três soluções para a travessia de firewall/NAT por aplicações distribuídas que utilizam CORBA como camada de comunicação, cada uma explorando as vantagens de uma situação específica. Exemplos de tais situações são a possibilidade de configuração do firewall ou a possibilidade de abertura de conexões TCP para fora da rede. / [en] Applications that use CORBA as the communication layer often face some restrictions for multi-domain deployment. This is particularly true when they have to face firewall/NAT traversal. Furthermore, nowadays there is no well-accepted unique or standardized solution adopted by all ORBs, compelling applications using this type of middleware to use proprietary solutions that sometimes do not address the environment restrictions in which they are deployed (e.g. impossibility to open firewall ports). This work presents and compares three solutions for firewall/NAT traversal by CORBA-based distributed applications, each one suitable for a specific situation and exploring its advantages. Examples of such situations are the possibility of open firewall ports or the possibility of start a TCP connection to the outside network.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第21543号 / 理博第4450号 / 新制||理||1639(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)准教授 福島 竜輝, 教授 熊谷 隆, 教授 牧野 和久 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

The industry of the civil Unmanned Aerial Vehicles (UAVs) has been growing rapidly in past few years. In many scenarios, accomplishing a task using a single UAV is either not cost-effective due to the size of the project or not even feasible due to the existence of unforeseen environment conditions and constraints (e.g., weather conditions and/or physical obstacles). This limitation motivates the need to move to solutions that incorporate a network of autonomous UAVs that carry out a joint and coordinated mission. This thesis introduces a multi-agent system and related algorithms that solve the graph traversal problem in a distributed and decentralized manner while optimizing a set of costs. The environment is modelled as a graph where every node is the point for the agents to accomplish some task or to distinguish the point as an obstacle where traveling is not possible. The online distributed algorithms are implemented on a network of UAVs and we report the results of rigorous simulations and real experiments with a network of UAVs. The results clearly validate our claim that a network UAVs can be effectively employed to accomplish a given task. / Thesis / Master of Science (MSc)

Breath-first search (BFS) is a fundamental building block in many graph-based applications, but it is difficult to optimize for a field-programmable gate array (FPGA) due to its irregular memory-access patterns. Prior work, based on hardware description languages (HDLs) and high-level synthesis (HLS), address the memory-access bottleneck of BFS by using techniques such as data alignment and compute-unit replication on FPGAs. The efficacy of such optimizations depends on factors such as the sparsity of target graph datasets. Optimizations intended for sparse graphs may not work as effectively for dense graphs on an FPGA and vice versa. This thesis presents two sets of FPGA optimization strategies for BFS, one for near-hypersparse graphs and the other designed for sparse to moderately dense graphs. For near-hypersparse graphs, a queue-based kernel with maximal use of local memory on FPGA is implemented. For denser graphs, an array-based kernel with compute-unit replication is implemented. Across a diverse collection of graphs, our OpenCL optimization strategies for near-hypersparse graphs delivers a 5.7x to 22.3x speedup over a state-of-the-art OpenCL implementation, when evaluated on an Intel Stratix~10 FPGA. The optimization strategies for sparse to moderately dense graphs deliver 1.1x to 2.3x speedup over a state-of-the-art OpenCL implementation on the same FPGA. Finally, this work uses graph metrics such as average degree and Gini coefficient to observe the impact of graph properties on the performance of the proposed optimization strategies. / M.S. / A graph is a data structure that typically consists of two sets -- a set of vertices and a set of edges representing connections between the vertices. Graphs are used in a broad set of application domains such as the testing and verification of digital circuits, data mining of social networks, and analysis of road networks. In such application areas, breadth-first search (BFS) is a fundamental building block. BFS is used to identify the minimum number of edges needed to be traversed from a source vertex to one or many destination vertices. In recent years, several attempts have been made to optimize the performance of BFS on reconfigurable architectures such as field-programmable gate arrays (FPGAs). However, the optimization strategies for BFS are not necessarily applicable to all types of graphs. Moreover, the efficacy of such optimizations oftentimes depends on the sparsity of input graphs. To that end, this work presents optimization strategies for graphs with varying levels of sparsity. Furthermore, this work shows that by tailoring the BFS design based on the sparsity of the input graph, significant performance improvements are obtained over the state-of-the-art BFS implementations on an FPGA.

A growing use for serverless computing is large parallel data processing applications that take advantage of its on-demand scalability. Because individual serverless compute nodes, which are called functions, run in isolated containers, a major challenge with this paradigm is transferring temporary computation data between functions. Previous works have performed inter-function communication using object storage, which is slow, or in-memory databases, which are expensive. We evaluate the use of direct network connections between functions to overcome these limitations. Although function containers block incoming connections, we are able to bypass this restriction using standard NAT traversal techniques. By using an external server, we implement TCP hole punching to establish direct TCP connections between functions. In addition, we develop a communications framework to manage NAT traversal and data flow for applications using direct network connections. We evaluate this framework with a reduce-by-key application compared to an equivalent version that uses object storage for communication. For a job with 100+ functions, our TCP implementation runs 4.7 times faster at almost half the cost. / Master of Science / Serverless computing is a branch of cloud computing where users can remotely run small programs, called "functions," and pay only based on how long they run. A growing use for serverless computing is running large data processing applications that use many of these serverless functions at once, taking advantage of the fact that serverless programs can be started quickly and on-demand. Because serverless functions run on isolated networks from each other and can only make outbound connections to the public internet, a major challenge with this paradigm is transferring temporary computation data between functions. Previous works have used separate types of cloud storage services in combination with serverless computing to allow functions to exchange data. However, hard-drive--based storage is slow and memory-based storage is expensive. We evaluate the use of direct network connections between functions to overcome these limitations. Although functions cannot receive incoming network connections, we are able to bypass this restriction by using a standard networking technique called Network Address Translation (NAT) traversal. We use an external server as an initial relay to setup a network connection between two functions such that once the connection is established, the functions can communicate directly with each other without using the server anymore. In addition, we develop a communications framework to manage NAT traversal and data flow for applications using direct network connections. We evaluate this framework with an application for combining matching data entries and compare it to an equivalent version that uses storage based on hard drives for communication. For a job with over 100 functions, our implementation using direct network connections runs 4.7 times faster at almost half the cost.

Um dos grandes avanços na área da computação nas últimas décadas refere-se aos sistemas distribuídos. O uso de tais sistemas tem crescido vertiginosamente nos últimos anos. Com o surgimento e uso de tecnologias de redes sem-fio, os sistemas ganharam mobilidade e dinamismo. Pessoas podem entrar ou sair de seus locais de trabalho, de entretenimento ou mesmo de suas casas com seus computadores móveis; redes podem ser formadas ou extintas conforme a dinâmica de um grupo de pessoas; e novos serviços podem ser disponibilizados ou interrompidos. Em sistemas como tais, um sistema de localização de serviços automático é fundamental para acompanhar as contínuas modificações na rede. A localização de serviços permite que, em uma rede de endereçamento estático ou dinâmico, dispositivos e serviços possam ser encontrados de modo completamente automático. A presente dissertação propõe um sistema de localização lógica (endereçamento) de serviços e dispositivos em uma rede local ou geograficamente distribuída, indo ao encontro às necessidades de controle de sistemas distribuídos dinâmicos, contribuindo ao mesmo tempo com questões de usabilidade e configuração automática de redes. O sistema, também, busca resolver questões relacionadas ao uso dos serviços entre redes protegidas por firewalls ou que utilizam configurações de NAT. / In the last decades, one of the most important progresses in computation is related to the distributed systems. The usage of these systems has increased a lot, in the last years. Due the emergence of wireless technologies, systems have acquired mobility and dynamism. People can enter or leave places, such as home, workplaces and entertainment spots, caring their mobile computers; networks can be formed or extinguished in accordance with the people dynamism; and new services can be available or interrupted. At these systems, a service location system is needed to keep track of the unceasing modifications in the network. The service location enables that services and devices can be found, at dynamic or static networks. This master thesis proposes a system for location of the logical addresses of services and devices at local or wide area networks. This work contributes to issues related to distributed systems control, usability and automatic network configuration. This system also solves questions related to service usage between networks using firewalls or NAT. Besides that, other points related to network interconnections in distributed systems, for example, using the Internet, are raised and solved.

Um dos grandes avanços na área da computação nas últimas décadas refere-se aos sistemas distribuídos. O uso de tais sistemas tem crescido vertiginosamente nos últimos anos. Com o surgimento e uso de tecnologias de redes sem-fio, os sistemas ganharam mobilidade e dinamismo. Pessoas podem entrar ou sair de seus locais de trabalho, de entretenimento ou mesmo de suas casas com seus computadores móveis; redes podem ser formadas ou extintas conforme a dinâmica de um grupo de pessoas; e novos serviços podem ser disponibilizados ou interrompidos. Em sistemas como tais, um sistema de localização de serviços automático é fundamental para acompanhar as contínuas modificações na rede. A localização de serviços permite que, em uma rede de endereçamento estático ou dinâmico, dispositivos e serviços possam ser encontrados de modo completamente automático. A presente dissertação propõe um sistema de localização lógica (endereçamento) de serviços e dispositivos em uma rede local ou geograficamente distribuída, indo ao encontro às necessidades de controle de sistemas distribuídos dinâmicos, contribuindo ao mesmo tempo com questões de usabilidade e configuração automática de redes. O sistema, também, busca resolver questões relacionadas ao uso dos serviços entre redes protegidas por firewalls ou que utilizam configurações de NAT. / In the last decades, one of the most important progresses in computation is related to the distributed systems. The usage of these systems has increased a lot, in the last years. Due the emergence of wireless technologies, systems have acquired mobility and dynamism. People can enter or leave places, such as home, workplaces and entertainment spots, caring their mobile computers; networks can be formed or extinguished in accordance with the people dynamism; and new services can be available or interrupted. At these systems, a service location system is needed to keep track of the unceasing modifications in the network. The service location enables that services and devices can be found, at dynamic or static networks. This master thesis proposes a system for location of the logical addresses of services and devices at local or wide area networks. This work contributes to issues related to distributed systems control, usability and automatic network configuration. This system also solves questions related to service usage between networks using firewalls or NAT. Besides that, other points related to network interconnections in distributed systems, for example, using the Internet, are raised and solved.