<p>This licentiate thesis work investigates two medium access control (MAC) methods, when used in traffic safety applications over vehicular <em>ad hoc</em> networks (VANETs). The MAC methods are carrier sense multiple access (CSMA), as specified by the leading standard for VANETs IEEE 802.11p, and self-organizing time-division multiple access (STDMA) as used by the leading standard for transponders on ships. All vehicles in traffic safety applications periodically broadcast cooperative awareness messages (CAMs). The CAM based data traffic implies requirements on a predictable, fair and scalable medium access mechanism. The investigated performance measures are <em>channel access delay</em>, <em>number of consecutive packet drops</em> and the <em>distance between concurrently transmitting nodes</em>. Performance is evaluated by computer simulations of a highway scenario in which all vehicles broadcast CAMs with different update rates and packet lengths. The obtained results show that nodes in a CSMA system can experience <em>unbounded channel access delays</em> and further that there is a significant difference between the best case and worst case channel access delay that a node could experience. In addition, with CSMA there is a very high probability that several <em>concurrently transmitting nodes are located close to each other</em>. This occurs when nodes start their listening periods at the same time or when nodes choose the same backoff value, which results in nodes starting to transmit at the same time instant. The CSMA algorithm is therefore both <em>unpredictable</em> and <em>unfair</em> besides the fact that it <em>scales badly</em> for broadcasted CAMs. STDMA, on the other hand, will always grant channel access for all packets before a predetermined time, regardless of the number of competing nodes. Therefore, the STDMA algorithm is <em>predictable</em> and <em>fair</em>. STDMA, using parameter settings that have been adapted to the vehicular environment, is shown to outperform CSMA when considering the performance measure <em>distance between concurrently transmitting nodes</em>. In CSMA the distance between concurrent transmissions is random, whereas STDMA uses the side information from the CAMs to properly schedule concurrent transmissions in space. The price paid for the superior performance of STDMA is the required network synchronization through a global navigation satellite system, e.g., GPS. That aside since STDMA was shown to be scalable, predictable and fair; it is an excellent candidate for use in VANETs when complex communication requirements from traffic safety applications should be met.</p>

Field Programmable Gate Arrays (FPGAs) are programmable logic devices used for the implementation of a wide range of digital systems. In recent years, there has been an increasing interest in design methodologies that allow high-level design descriptions to be automatically implemented in FPGAs. This thesis describes the design and implementation of a novel compilation flow that implements circuits in FPGAs from a streaming programming language. The streaming language supported is called FPGA Brook, and is based on the existing Brook and GPU Brook languages, which target streaming multiprocessors and graphics processing units (GPUs), respectively. A streaming language is suitable for targeting FPGAs because it allows system designers to express applications in a way that exposes parallelism, which can then be exploited through parallel hardware implementation. FPGA Brook supports replication, which allows the system designer to trade-off area for performance, by specifying the parts of an application that should be implemented as multiple hardware units operating in parallel, to achieve desired application throughput. Hardware units are interconnected through FIFO buffers, which effectively utilize the small memory modules available in FPGAs. The FPGA Brook design flow uses a source-to-source compiler, and combines it with a commercial behavioural synthesis tool to generate hardware. The source-to-source compiler was developed as a part of this thesis and includes novel algorithms for implementation of complex reductions in FPGAs. The design flow is fully automated and presents a user-interface similar to traditional software compilers. A suite of benchmark applications was developed in FPGA Brook and implemented using our design flow. Experimental results show that applications implemented using our flow achieve much higher throughput than the Nios II soft processor implemented in the same FPGA device. Comparison to the commercial C2H compiler from Altera shows that while simple applications can be effectively implemented using the C2H compiler, complex applications achieve significantly better throughput when implemented by our system. Performance of many applications implemented using our design flow would scale further if a larger FPGA device were used. The thesis demonstrates that using an automated design flow to implement streaming applications in FPGAs is a promising methodology.

Field Programmable Gate Arrays (FPGAs) are programmable logic devices used for the implementation of a wide range of digital systems. In recent years, there has been an increasing interest in design methodologies that allow high-level design descriptions to be automatically implemented in FPGAs. This thesis describes the design and implementation of a novel compilation flow that implements circuits in FPGAs from a streaming programming language. The streaming language supported is called FPGA Brook, and is based on the existing Brook and GPU Brook languages, which target streaming multiprocessors and graphics processing units (GPUs), respectively. A streaming language is suitable for targeting FPGAs because it allows system designers to express applications in a way that exposes parallelism, which can then be exploited through parallel hardware implementation. FPGA Brook supports replication, which allows the system designer to trade-off area for performance, by specifying the parts of an application that should be implemented as multiple hardware units operating in parallel, to achieve desired application throughput. Hardware units are interconnected through FIFO buffers, which effectively utilize the small memory modules available in FPGAs. The FPGA Brook design flow uses a source-to-source compiler, and combines it with a commercial behavioural synthesis tool to generate hardware. The source-to-source compiler was developed as a part of this thesis and includes novel algorithms for implementation of complex reductions in FPGAs. The design flow is fully automated and presents a user-interface similar to traditional software compilers. A suite of benchmark applications was developed in FPGA Brook and implemented using our design flow. Experimental results show that applications implemented using our flow achieve much higher throughput than the Nios II soft processor implemented in the same FPGA device. Comparison to the commercial C2H compiler from Altera shows that while simple applications can be effectively implemented using the C2H compiler, complex applications achieve significantly better throughput when implemented by our system. Performance of many applications implemented using our design flow would scale further if a larger FPGA device were used. The thesis demonstrates that using an automated design flow to implement streaming applications in FPGAs is a promising methodology.

La nueva tendencia para aumentar el rendimiento de los futuroscomputadores son los multiprocesadores en un solo chip (CMPs). Seespera que en un futuro cercano salgan al mercado CMPs con decenas deprocesadores. Hoy en d�a, la mejor manera de mantener la coherencia decache en estos sistemas es mediante los protocolos basados endirectorio. Sin embargo, estos protocolos tienen dos grandesproblemas: una gran sobrecarga de memoria y una alta latencia de losfallos de cache.Esta tesis se ha centrado en estos problemas claves para la eficienciay escalabilidad del CMP. En primer lugar, se ha presentado unaorganizaci�n de directorios escalable. En segundo lugar, se hanpropuesto los protocolos de coherencia directa, que evitan laindirecci�n al nodo home y, por tanto, reducen el tiempo de ejecuci�nde las aplicaciones. Por �ltimo, se ha desarrollado una pol�tica demapeo para caches compartidas pero f�sicamente distribuidas, quereduce la latencia de acceso y garantiza una distribuci�n uniforme delos datos con el fin de reducir su tasa de fallos. Esto se traducefinalmente en un menor tiempo de ejecuci�n para las aplicaciones. / Chip multiprocessors (CMPs) constitute the new trend for increasingthe performance of future computers. In the near future, chips withtens of cores will become more popular. Nowadays, directory-basedprotocols constitute the best alternative to keep cache coherence inlarge-scale systems. Nevertheless, directory-based protocols have twoimportant issues that prevent them from achieving better scalability:the directory memory overhead and the long cache miss latencies.This thesis focuses on these key issues. The first proposal is ascalable distributed directory organization that copes with the memoryoverhead of directory-based protocols. The second proposal presentsthe direct coherence protocols, which are aimed at avoiding theindirection problem of traditional directory-based protocols and,therefore, they improve applications' performance. Finally, a novelmapping policy for distributed caches is presented. This policyreduces the long access latency while lessening the number of off-chipaccesses, leading to improvements in applications' execution time.

The performance of analog integrated circuits is dependent on the technology. Digital circuits are scalable in nature, and the same circuit can be scaled from one technology to another with improved performance. But, in analog integrated circuits, the circuit components must be re-designed to maintain the desired performance across different technologies. Moreover, in the case of digital circuits, minimum feature-size (short channel length) devices can be used for better performance, but analog circuits are still being designed using channel lengths larger than the minimum feature sizes. The research in this thesis is aimed at understanding the impact of technology scaling and short channel length devices on the performance of analog integrated circuits. The operational amplifier (op amp) is chosen as an example circuit for investigation. The performance of the conventional op amps are studied across different technologies for short channel lengths, and techniques to develop technology-independent op amp architectures have been proposed. In this research, three op amp architectures have been developed whose performance is relatively independent of the technology and the channel length. They are made scalable, and the same op amp circuits are scaled from a 0.25 um CMOS onto a 0.18 um CMOS technology with the same components. They are designed to achieve large small-signal gain, constant unity gain-bandwidth frequency and constant phase margin. They are also designed with short channel length transistors. Current feedback, gm-boosted, CMOS source followers are also developed, and they are used in the buffered versions of these op amps.

Im Rahmen der Dissertation wurde ein Middlewaredienst entwickelt und realisiert. Es gestattet die dynamische Verwaltung heterogener Kontextquellen. Das zugrunde liegende Komponentenmodell selbstbeschreibender Context Provieder ermöglicht die lose Kopplung von Kontextquellen und -senken. Es wird durch Filter- und Konverterkomponenten zur generischen Providersselektion anhand domänenspezifischer Merkmale ergänzt. Die Kopplung der verteilten Dienstinstanzen erfolgt durch ein hybrides Peer-to-Peer-System. Dies trägt der Heterogenität der Endgeräte Rechnung, und erlaubt die skalierbare , verteilte Verwaltung von Kontextquellen in globalen Szenarien.

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets. / Generally, network design problems consist of selecting links and vertices of a graph G so that a cost function is optimized and all constraints involving links and the vertices in G are met. A change in the criterion of optimization and/or the set of constraints leads to a new representation of a different problem. In this thesis, we consider the problem of designing infrastructure Wireless Mesh Networks (WMNs) where we show that the design of such networks becomes an optimization problem with multiple objectives instead of a standard optimization problem (a cost function is optimized) to take into account many aspects, often contradictory, but nevertheless essential in the reality. This thesis, composed of three parts, introduces new models and algorithms for designing WMNs from scratch. The first part is devoted to the simultaneous optimization of two equally important objectives: cost and network performance in terms of throughput. Three bi-objective models which differ mainly by the approach used to maximize network performance are proposed, solved and compared. The second part deals with the problem of gateways placement, given its impact on network performance and scalability. The concept of hop constraints is introduced into the network design to reduce the transmission delay. A novel algorithm based on a clustering approach is also proposed to find the strategic positions of gateways that support network scalability and increase its performance without significantly increasing the cost of installation. The final section addresses the problem of reliability in the presence of single failures. Allowing the installation of redundant components in the design phase can ensure reliable communications, but at the expense of cost and network performance. A new algorithm is developed based on the theoretical approach of "ear decomposition" to install the minimum number of additional routers to tolerate single failures. In order to solve the proposed models for real-size networks, an evolutionary algorithm (meta-heuristics), inspired from nature, is developed. Finally, the proposed models and methods have been evaluated through empirical and discrete events based simulations.

Large-scale virtualized data centers require cloud providers to implement scalable, autonomic, and energy-efficient cloud management systems. To address these challenges this thesis provides four main contributions. The first one proposes Snooze, a novel Infrastructure-as-a-Service (IaaS) cloud management system, which is designed to scale across many thousands of servers and virtual machines (VMs) while being easy to configure, highly available, and energy efficient. For scalability, Snooze performs distributed VM management based on a hierarchical architecture. To support ease of configuration and high availability Snooze implements self-configuring and self-healing features. Finally, for energy efficiency, Snooze integrates a holistic energy management approach via VM resource (i.e. CPU, memory, network) utilization monitoring, underload/overload detection and mitigation, VM consolidation (by implementing a modified version of the Sercon algorithm), and power management to transition idle servers into a power saving mode. A highly modular Snooze prototype was developed and extensively evaluated on the Grid'5000 testbed using realistic applications. Results show that: (i) distributed VM management does not impact submission time; (ii) fault tolerance mechanisms do not impact application performance and (iii) the system scales well with an increasing number of resources thus making it suitable for managing large-scale data centers. We also show that the system is able to dynamically scale the data center energy consumption with its utilization thus allowing it to conserve substantial power amounts with only limited impact on application performance. Snooze is an open-source software under the GPLv2 license. The second contribution is a novel VM placement algorithm based on the Ant Colony Optimization (ACO) meta-heuristic. ACO is interesting for VM placement due to its polynomial worst-case time complexity, close to optimal solutions and ease of parallelization. Simulation results show that while the scalability of the current algorithm implementation is limited to a smaller number of servers and VMs, the algorithm outperforms the evaluated First-Fit Decreasing greedy approach in terms of the number of required servers and computes close to optimal solutions. In order to enable scalable VM consolidation, this thesis makes two further contributions: (i) an ACO-based consolidation algorithm; (ii) a fully decentralized consolidation system based on an unstructured peer-to-peer network. The key idea is to apply consolidation only in small, randomly formed neighbourhoods of servers. We evaluated our approach by emulation on the Grid'5000 testbed using two state-of-the-art consolidation algorithms (i.e. Sercon and V-MAN) and our ACO-based consolidation algorithm. Results show our system to be scalable as well as to achieve a data center utilization close to the one obtained by executing a centralized consolidation algorithm.

L'objectif de ce travail de thèse dans un premier temps est l'évaluation de performances des modèles de routage multi-chemins pour l'ingénierie de trafic et l'équilibrage de charge sur un réseau de type IP/MPLS (MPLS-TE). Nous comparons la capacité de ces modèles à équilibrer la charge du réseau tout en faisant de la différentiation de trafic. Nous les appliquons sur des grandes topologies générées par le générateur automatique des topologies BRITE, qui s'approchent en forme et en complexité du réseau réel. Nous mesurons ainsi l'impact de leur complexité respective et donc la capacité à les déployer sur des réseaux de grande taille (scalabilité). Dans un second temps, l'objectif est de proposer un concept de modélisation générale d'un réseau à commutations par paquets. Ce modèle est établi sur la base de la théorie différentielle de trafic et la théorie des files d'attente, tout en utilisant des approches graphiques. Le but est d'estimer l'état de charge du réseau et de ses composants (routeurs, liens, chemins). Ensuite, en fonction de ça, nous développons des approches de contrôle de congestion et commande sur l'entrée améliorant les techniques de routage adaptatif et l'équilibrage de charge dans les réseaux IP/MPLS / In This work, firstly we present and evaluate the behavior of multipath routing models for the DS-TE (DiffSev aware MPLS traffic Engineering) called PEMS and LBWDP. To clarify network topologies and routing models that are suitable for MPLS Traffic Engineering, we evaluate them from the viewpoint of network scalability and end-to-end quality. Using a network topology generated by BRITE, that has many alternative paths, we applied these models on a huge topology that correspond to real network. This can provide a real simulation for the internet and gives a good evaluation for the end-to-end quality and the network use.Secondly, the aim of this work is to propose a general model for Packet switching networks. This model is established on the traffic differential theory and the Queuing theory, while using graphic approaches. The aim of this model is to calculate the network use state and its components (router, link, path...). Then, we develop control and command approaches in the entry of network to improve an adaptive routing plan and load balancing in IP/MPLS networks

Made available in DSpace on 2016-06-02T19:05:59Z (GMT). No. of bitstreams: 1 4685.pdf: 5011854 bytes, checksum: 20592729fa201c69f10672347d91c2a5 (MD5) Previous issue date: 2012-08-31 / Financiadora de Estudos e Projetos / Managing multiple systems such as machine tools, vehicles, aircraft, among others, demand a very intense flow of data between them and the system manager. Researches have been developed in the design and implementation of scalable architectures that meet these demands leading to interesting questions of performance. The objective of this work is to propose a low cost scalable architecture for embedded applications, using pools of personal computers for high performance storage, retrieval and processing of information. It is driven by strong demand for tracking and monitoring of machines and vehicles, covering concepts of mobile networks with satellites and GPRS technology together with the requirement of reliability and performance in the sending of information. Proposes the definition of a server structure, whose distribution is transparent to the application, which is responsible for the receipt of messages from embedded devices via radio frequency technology, decoding and integration of information in the database and subsequent recovery of these information s. Through simulation of different modeled strategies using queuing theory to determine the architecture and the use of predictive mathematical methods for estimating the future burden for the server application, it was possible to obtain a solution that satisfactorily met the assumptions of the research. Thus, it is concluded that it is possible to estimate trends peaks processing information for telemetry applications fleet. / O gerenciamento remoto de múltiplos sistemas tais como máquinas operatrizes, veículos, aviões, dentre outros, demanda um fluxo bastante intenso de dados entre eles e o sistema gerenciador. Pesquisas têm sido desenvolvidas na concepção e implementação de arquiteturas escaláveis que atendam essas demandas levando a questões interessantes de desempenho. O objetivo deste trabalho é propor uma arquitetura escalável de baixo custo para aplicações embarcadas, utilizando pools de computadores pessoais para obter alto desempenho no armazenamento, recuperação e tratamento da informação. É motivado pela grande demanda de rastreamento e monitoramento de máquinas e veículos, contemplando conceitos de redes móveis com tecnologia de satélites e GPRS, juntamente com o requisito de confiabilidade e desempenho no envio da informação. Propõe a definição de uma estrutura de servidor, cuja distribuição é transparente para a aplicação, à qual compete o recebimento das mensagens dos equipamentos embarcados através de tecnologia de radio frequência, decodificação e inserção das informações num banco de dados e posterior recuperação destas informações. Através da simulação de diferentes estratégias modeladas, utilizando a teoria das filas, para determinação da arquitetura e a utilização de métodos matemáticos preditivos para estimação da carga futura para a aplicação servidora, foi possível obter uma solução que atendeu satisfatoriamente às premissas da pesquisa. Dessa forma, conclui-se que é possível estimar tendências de picos de processamento de informação para aplicações de telemetria de frotas.