<p>With fast-decreasing cost of electronic devices and the increasing use of mobile phones, vehicular ad hoc networks (VANETs) are emerging as a popular form of mobile ad hoc networks. VANETs are useful for supporting many applications that improve road safety and enhance driving convenience. Moreover, they also provide real-time data for traffic and travel management.</p><p>A VANET is composed of fast-moving mobile nodes (vehicles) that have intermittent and short contacts, fixed road-side units (RSUs) that overhear and broadcast to vehicles, and a central server. Vehicles move along roads, collect data and process them, and disseminate the data to other vehicles and RSUs. The central server aggregates data collected by vehicles, overviews traffic and road status, and generates keys and certificates when necessary. RSUs overhear the data sent from vehicles, broadcast road-side information to vehicles, and communicate to the central server via backhaul network.</p><p>With smartphones equipped on vehicles, many interesting research topics emerge, such as traffic-congestion detection and road-bump detection. After data are collected and processed, they are disseminated, such that other vehicles can collaboratively sense the road and traffic status. This motivates the need for data dissemination algorithms in a VANET. Due to the limited bandwidth and insufficient coverage of 3G/4G networks, direct peer-to-peer communication between nodes is important.</p><p>Other major concerns in a VANET are security and privacy, since a malicious user can track vehicles, report false alarms, create undesirable traffic congestion, and illegally track vehicles. It is important to ensure the authenticity of messages propagated within VANETs, while protecting the identity and location privacy of vehicles that send messages. This thesis addresses data collection, data processing, dissemination, and security.</p><p>First, we estimate the location of vehicles in the scenario of weak/faded GPS signals by using the built-in sensors on smartphones. This method combines landmark recognition and Markov-chain predictions to localize a vehicle. Compared to the coarse-grained localization embedded in an Android smartphone using cellular and wifi signals, this method significantly improves accuracy. </p><p>For data dissemination, we observe habitual mobility as well as deviations from habits, characterize their impact on latency, and exploit them through the Diverse Routing (DR) algorithm.</p><p>Comparing to existing protocols, we show that DR leads to the least packet delay, especially when users deviate from expected behavior.</p><p>An important challenge for secure information dissemination in a VANET lies in Sybil attacks, where a single vehicle fakes multiple identities. We propose the Privacy-perserving Detection of Sybil Attack Protocl (P<super>2</super>DAP) scheme to detect such Sybil attacks. The P<super>2</super>DAP method does not require any vehicle in the network to disclose its identity, hence privacy is preserved at all times. Our results also quantify the inherent trade-off between security, i.e., the detection of Sybil attacks and detection latency, and the privacy provided to the vehicles in the network.</p><p>Due to the dependency of P<super>2</super>DAP on RSUs, and the fact that RSUs are usually semi-trusted in VANETs, we need an additional protection mechanism for RSUs. This observation motivates the Predistribution and Local-Collaboration-Based Authentication (PLCA) scheme, which combines Shamir secret sharing with neighborhood collaboration. In PLCA, the cost of changing the infrastructure is relatively low, and any compromise of RSUs can be quickly detected.</p><p>In summary, this thesis addresses problems that are relevant to various stages of the life-cycle of information in a VANET. The proposed solution handle data collection, data processing and information extraction, data dissemination, and security/privacy issues. Together, these adverses contribute to a secure and efficient environment for VANET, such that better driving experience and safety can be achieved.</p> / Dissertation

<p> The use of video streaming has been growing rapidly in the recent years and has been utilized in various applications. Many of these applications are latency sensitive, but the latency requirements varies largely from one application to another. The high quality videos captured by cameras are quite large in size, so they are encoded to reduce the video size to achieve a reasonable bandwidth when sent over a network.</p><p> In this work, we characterize the latency components of edge video streaming with the goal of identifying latency bottlenecks. In edge applications, the processing is performed at the edge of the network close to data generation, rather than in the cloud, to meet the latency requirements. This work specifically investigates the latencies in the transmit and receive paths in the Linux networking stack, and the impact of encoding parameters on the latency.</p>

<p>The relative timing (RT) based asynchronous design methodology has been successfully used to create application specific integrated circuit (ASIC) designs that are a process generation ahead of their synchronous counterparts in terms of power, performance and energy. However, while the implementation of RT asynchronous circuits has been dealt with successfully in the ASIC domain, there has been limited exploration of utilizing the design methodology on field programmable gate arrays (FPGAs). This dissertation seeks to address the challenges in implementing RT asynchronous circuits on FPGAs. Relative Timing uses path-based timing constraints to guarantee that a circuit conforms to its behavioral specification. A methodology for the design of glitch free burstmode asynchronous controllers on FPGAs is presented. Path based timing constraints are implement to ensure circuit functionality. A flow for the modeling of the circuit, extraction of relative timing constraints, and implementation of the extracted constraints is presented. Optimizations that enable faster implementation and more robust designs are discussed. The dissertation also presents a framework to evaluate and rank relative timing constraint sets for a given circuit. Multiple constraint sets are possible for a single circuit. The constraint sets are evaluated on the basis of robustness of the constraints and conflicts between constraints in the same set. The methodology is used to optimize the extraction of relative timing constraints. An FPGA architecture capable of relative timing based digital implementations is designed. Modifications are made to a traditional synchronous FPGA architecture to make it asynchronous capable, while retaining its capability as a fully functional synchronous FPGA. A Microprocessor without Interlocked Pipeline Stages (MIPS) design is used to test the FPGA. A performance improvement of 1.7x and a power improvement of 2.3x is achieved. Furthermore, a novel reconfigurable circuit capable of implementing the entire family of 2-phase and 4-phase latch protocols is presented. The circuit is implemented on the International Business Machine Artisan 65nm node and its performance is compared with implementations on a Xilinx Virtex-5 chip that is manufactured on a similar node. A 4x improvement in speed and 2.7x improvement in energy per cycle is achieved.

<p> Soft errors caused by radiation are a common problem in spaceflight due to the intense radiation environment of space. Single Error Correction (SEC) Error Correcting Codes (ECCs) are a traditional approach to solve this problem, but with the increasing density of IC architectures, multiple-bit errors are becoming more common. Double Error Correction (DEC) ECCs are costly, but codes between DEC and SEC, which take advantage of the spatial locality of bit errors and correct only adjacent double-bit errors, have been found by others. In this thesis, one of those codes is implemented and evaluated on a Spartan-6 FPGA. The results of several error trials are presented herein, along with implementation details, including the source code. Tables of the trial results and the specific FPGA resources used are also presented. The implementation is found to have a non-negligible area cost, but low latency cost. Another implementation of this same ECC with potentially low area but high latency is also described. When errors well beyond the ECC&rsquo;s capability, such as multiple single-bit errors, or four-bit errors, are injected, around 30% of the time the code erroneously claims to have fixed an error. In these same circumstances, however, the ECC implementation hardly ever (0.2%) claims that no error has occurred. This suggests that a simple extension to a more conservative ECC which flushes data on any error could be used in situations with error rates that surpass the ECC&rsquo;s capability to maintain data integrity.</p>

<p> Humans are able to recognize objects in a scene almost effortlessly. Our visual system can easily handle ambiguous settings, like partial occlusions or large variations in viewpoint. One hypothesis that explains this ability is that we process the scene as a global instance. Using global contextual reasoning (e.g., a car sits on a road, but not on a building facade) can constrain interpretations of objects to plausible, coherent precepts. This type of reasoning has been explored in Computer Vision using weak 2D context, mostly extracted from monocular cues. In this thesis, we explore the benefits of strong 3D context extracted from multiple-view geometry. We demonstrate strong ties between geometric reasoning and object recognition, effectively bridging the gap between them to improve scene understanding. </p><p> In the first part of this thesis, we describe the basic principles of structure from motion, which provide strong and reliable geometric models that can be used for contextual scene understanding. We present a novel algorithm for camera localization that leverages search space partitioning to allow a more aggressive filtering of potential correspondences. We exploit image covisibility using a coarse-to-fine, prioritized search approach that can recognize scene landmarks rapidly. This system achieves state of the art results in large-scale camera localization, especially in difficult scenes with frequently repeated structures. </p><p> In the second part of this thesis, we study how to exploit these strong geometric models and localized cameras to improve recognition. We introduce an unsupervised training pipeline to generate scene-specific object detectors. These classifiers outperform state of the art and can be used when the rough camera location is known. When precise camera pose is available, we can inject additional geometric cues into novel re-scoring framework to further improve detection. We demonstrate the utility of background scene models for false positive pruning, akin to video-surveillance background subtraction strategies. Finally, we observe that the increasing availability of mapping data stored in Geographic Information Systems (GIS) provides strong geo-semantic information that can be used when cameras are located in world coordinates. We propose a novel contextual reasoning pipeline that uses lifted 2D GIS models to quickly retrieve precise geo-semantic priors. We use these cues to to improve object detection and image semantic segmentation, providing a successful trade-off of false positives that boosts average precision over baseline detection models. </p>

We consider the problem of reconciling similar strings in a distributed system. Specifically, we are interested in performing this reconciliation in an efficient manner, minimizing the communication cost. Our problem applies to several types of large-scale distributed networks, file synchronization utilities, and any system that manages the consistency of string encoded ordered data. We present the novel Recursive Content-Dependent Shingling (RCDS) protocol that can handle large strings and has the communication complexity that scales with the edit distance between the reconciling strings. Also, we provide analysis, experimental results, and comparisons to existing synchronization software such as the Rsync utility with an implementation of our protocol. / 2019-12-03T00:00:00Z

Analysis techniques are used to test mobile applications for bugs or malicious activity. Market operators such as Google and Amazon use analysis tools to scan applications before deployment. Creating a call graph is a crucial step in many of the static analysis tools for Android applications. Each edge in a call graph is a method call in the application. A sound call graph is one that contains all method calls of an application. The soundness of the call graph is critical for accurate analysis. Unsoundness in the call graph would render analysis of the application flawed. Therefore, any conclusions drawn from an unsound call graph could be invalid. In this project, we analyze the soundness of static call graphs. We propose and develop a novel approach to automatically identify unsoundness. We create a dynamic call graph to examine the soundness of the static call graph. We map the edges of the two graphs. Any edge observed dynamically but not present in the static call graph is a witness for unsoundness. We show that there are edges in the dynamic call graph that are not contained in the static call graph. We analyze 92 applications to find a total of 19,653 edges missed by a state-of-the-art static analysis tool. To further analyze these edges, our tool categorizes them into groups that can help identify the type of method call that was missed by the static analysis tool. These categories pinpoint where further research efforts are necessary to improve current state-of-the-art static analysis capabilities.

Applications running in large-scale computing systems such as high performance computing (HPC) or cloud data centers are essential to many aspects of modern society, from weather forecasting to financial services. As the number and size of data centers increase with the growing computing demand, scalable and efficient management becomes crucial. However, data center management is a challenging task due to the complex interactions between applications, middleware, and hardware layers such as processors, network, and cooling units. This thesis claims that to improve robustness and efficiency of large-scale computing systems, significantly higher levels of automated support than what is available in today's systems are needed, and this automation should leverage the data continuously collected from various system layers. Towards this claim, we propose novel methodologies to automatically diagnose the root causes of performance and configuration problems and to improve efficiency through data-driven system management. We first propose a framework to diagnose software and hardware anomalies that cause undesired performance variations in large-scale computing systems. We show that by training machine learning models on resource usage and performance data collected from servers, our approach successfully diagnoses 98% of the injected anomalies at runtime in real-world HPC clusters with negligible computational overhead. We then introduce an analytics framework to address another major source of performance anomalies in cloud data centers: software misconfigurations. Our framework discovers and extracts configuration information from cloud instances such as containers or virtual machines. This is the first framework to provide comprehensive visibility into software configurations in multi-tenant cloud platforms, enabling systematic analysis for validating the correctness of software configurations. This thesis also contributes to the design of robust and efficient system management methods that leverage continuously monitored resource usage data. To improve performance under power constraints, we propose a workload- and cooling-aware power budgeting algorithm that distributes the available power among servers and cooling units in a data center, achieving up to 21% improvement in throughput per Watt compared to the state-of-the-art. Additionally, we design a network- and communication-aware HPC workload placement policy that reduces communication overhead by up to 30% in terms of hop-bytes compared to existing policies. / 2019-07-02T00:00:00Z

Digitized by Kansas Correctional Industries

High Performance Computing (HPC) has matured to where it is an essential third pillar, along with theory and experiment, in most domains of science and engineering. Communication latency is a key factor that is limiting the performance of HPC, but can be addressed by integrating communication into accelerators. This integration allows accelerators to communicate with each other without CPU interactions, and even bypassing the network stack. Field Programmable Gate Arrays (FPGAs) are the accelerators that currently best integrate communication with computation. The large number of Multi-gigabit Transceivers (MGTs) on most high-end FPGAs can provide high-bandwidth and low-latency inter-FPGA connections. Additionally, the reconfigurable FPGA fabric enables tight coupling between computation kernel and network interface. Our thesis is that an application-aware communication infrastructure for a multi-FPGA system makes substantial progress in solving the HPC communication bottleneck. This dissertation aims to provide an application-aware solution for communication infrastructure for FPGA-centric clusters. Specifically, our solution demonstrates application-awareness across multiple levels in the network stack, including low-level link protocols, router microarchitectures, routing algorithms, and applications. We start by investigating the low-level link protocol and the impact of its latency variance on performance. Our results demonstrate that, although some link jitter is always present, we can still assume near-synchronous communication on an FPGA-cluster. This provides the necessary condition for statically-scheduled routing. We then propose two novel router microarchitectures for two different kinds of workloads: a wormhole Virtual Channel (VC)-based router for workloads with dynamic communication, and a statically-scheduled Virtual Output Queueing (VOQ)-based router for workloads with static communication. For the first (VC-based) router, we propose a framework that generates application-aware router configurations. Our results show that, by adding application-awareness into router configuration, the network performance of FPGA clusters can be substantially improved. For the second (VOQ-based) router, we propose a novel offline collective routing algorithm. This shows a significant advantage over a state-of-the-art collective routing algorithm. We apply our communication infrastructure to a critical strong-scaling HPC kernel, the 3D FFT. The experimental results demonstrate that the performance of our design is faster than that on CPUs and GPUs by at least one order of magnitude (achieving strong scaling for the target applications). Surprisingly, the FPGA cluster performance is similar to that of an ASIC-cluster. We also implement the 3D FFT on another multi-FPGA platform: the Microsoft Catapult II cloud. Its performance is also comparable or superior to CPU and GPU HPC clusters. The second application we investigate is Molecular Dynamics Simulation (MD). We model MD on both FPGA clouds and clusters. We find that combining processing and general communication in the same device leads to extremely promising performance and the prospect of MD simulations well into the us/day range with a commodity cloud.