Information Retrieval (IR) plays a key role in serving large communities of users who are in need of relevant answers for their search queries. IR encompasses various search models to address different requirements and has introduced a variety of supporting tools to improve effectiveness and efficiency. "Search" is the key focus of IR. The classic search methodology takes an input query, processes it, and returns the result as a ranked list of documents. However, this approach is not the most effective method to support the task of finding document associations (relationships between concepts or queries) both for direct or indirect relationships. The Stepping Stones and Pathways (SSP) retrieval methodology supports retrieval of ranked chains of documents that support valid relationships between any two given concepts. SSP has many potential practical and research applications, which are in need of a tool to find connections between two concepts. The early SSP "proof-of-concept" implementation could handle only 6000 documents. However, commercial search applications will have to deal with millions of documents. Hence, addressing the scalability limitation becomes extremely important in the current SSP implementation in order to overcome the limitations on handling large datasets. Research on various commercial search applications and their scalability indicates that the Lucene search tool kit is widely used due to its support for scalability, performance, and extensibility features. Many web-based and desktop applications have used this search tool kit to great success, including Wikipedia search, job search sites, digital libraries, e-commerce sites, and the Eclipse Integrated Development Environment (IDE). The goal of this research is to re-implement SSP in a scalable way, so that it can work for larger datasets and also can be deployed commercially. This work explains the approach adopted for re-implementation focusing on scalable indexing, searching components, new ways to process citations (references), a new approach for query expansion, document clustering, and document similarity calculation. The experiments performed to test the factors such as runtime and storage proved that the system can be scaled up to handle up to millions of documents. / Master of Science

With the end of Moore's Law, computer architects have turned to multicore architecture to provide high performance. Unfortunately, to achieve higher performance, multicores require programs to be parallelized which is an untamed problem. Amdahl's law tells that the maximum theoretical speedup of a program is dictated by the size of the non-parallelizable section of a program. Hence to achieve higher performance, programmers need to reduce the size of sequential code in the program. This thesis explores asynchronous work as a means to reduce sequential portions of program. Using asynchronous work, a programmer can remove tasks which do not affect data consistency from the critical path and can be performed using background thread. Using this idea, the thesis introduces two systems. First, a synchronization mechanism, Multi-Version Read-Log-Update(MV-RLU), which extends Read-Log-Update (RLU) through multi-versioning. At the core of MV-RLU design is a concurrent garbage collection algorithm which reclaims obsolete versions asynchronously reducing blocking of threads. Second, a concurrent and highly scalable index-structure called Hydralist for multi-core. The key idea behind design of Hydralist is that an index-structure can be divided into two component (search layer and data layer) and updates to data layer can be done synchronously while updates to search layer can be propagated asynchronously using background threads. / Master of Science / Up until mid-2000s, Moore's law predicted that performance CPU doubled every two years. This is because improvement in transistor technology allowed smaller transistor which can switch at higher frequency leading to faster CPU clocks. But faster clock leads to higher heat dissipation and as chips reached their thermal limits, computer architects could no longer increase clock speeds. Hence they moved to multicore architecture, wherein a single die contains multiple CPUs, to allow higher performance. Now programmers are required to parallelize their code to take advangtage of all the CPUs in a chip which is a non trivial problem. The theoretical speedup achieved by a program on multicore architecture is dictated by Amdahl's law which describes the non parallelizable code in a program as the limiting factor for speedup. For example, a program with 99% parallelizable code can achieve speedup of 20 whereas a program with 50% parallelizable code can only achieve speedup of 2. Therefore to achieve high speedup, programmers need to reduce size of serial section in their program. One way to reduce sequential section in a program is to remove non-critical task from the sequential section and perform the tasks asynchronously using background thread. This thesis explores this technique in two systems. First, a synchronization mechanism which is used co-ordinate access to shared resource called Multi-Version Read-Log-Update (MV-RLU). MV-RLU achieves high performance by removing garbage collection from critical path and performing it asynchronously using background thread. Second, an index structure, Hydralist, which based on the insight that an index structure can be decomposed into two components, search layer and data layer, and decouples updates to both the layer which allows higher performance. Updates to search layer is done synchronously while updates to data layer is done asynchronously using background threads. Evaluation shows that both the systems perform better than state-of-the-art competitors in a variety of workloads.

Mobile Ad-hoc Networks (MANETs) have received considerable research interest in recent years. Because of dynamic topology and limited resources, it is challenging to design routing protocols for MANETs. In this dissertation, we focus on the scalability and efficiency problems in designing routing protocols for MANETs. We design the Way Point Routing (WPR) model for medium to large networks. WPR selects a number of nodes on a route as waypoints and divides the route into segments at the waypoints. Waypoint nodes run a high-level inter-segment routing protocol, and nodes on each segment run a low-level intra-segment routing protocol. We use DSR and AODV as the inter-segment and the intra-segment routing protocols, respectively. We term this instantiation the DSR Over AODV (DOA) routing protocol. We develop Salvaging Route Reply (SRR) to salvage undeliverable route reply (RREP) messages. We propose two SRR schemes: SRR1 and SRR2. In SRR1, a salvor actively broadcasts a one-hop salvage request to find an alternative path to the source. In SRR2, nodes passively learn an alternative path from duplicate route request (RREQ) packets. A salvor uses the alternative path to forward a RREP when the original path is broken. We propose Multiple-Target Route Discovery (MTRD) to aggregate multiple route requests into one RREQ message and to discover multiple targets simultaneously. When a source initiates a route discovery, it first tries to attach its request to existing RREQ packets that it relays. MTRD improves routing performance by reducing the number of regular route discoveries. We develop a new scheme called Bilateral Route Discovery (BRD), in which both source and destination actively participate in a route discovery process. BRD consists of two halves: a source route discovery and a destination route discovery, each searching for the other. BRD has the potential to reduce control overhead by one half. We propose an efficient and generalized approach called Accumulated Path Metric (APM) to support High-Throughput Metrics (HTMs). APM finds the shortest path without collecting topology information and without running a shortest-path algorithm. Moreover, we develop the Broadcast Ordering (BO) technique to suppress unnecessary RREQ transmissions.

The volumes of data which Big Data applications have to process are constantly increasing. This requires for the development of highly scalable systems. Microservices is considered as one of the solutions to deal with the scalability problem. However, the literature on practices for building scalable data-intensive systems is still lacking. This thesis aims to investigate and present the benefits and drawbacks of using microservices architecture in big data systems. Moreover, it presents other practices used to increase scalability. It includes containerization, shared-nothing architecture, data sharding, load balancing, clustering, and stateless design. Finally, an experiment comparing the performance of a monolithic application and a microservices-based application was performed. The results show that with increasing amount of load microservices perform better than the monolith. However, to cope with the constantly increasing amount of data, additional techniques should be used together with microservices.

Ho Wang Hei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 93-94). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Contributions --- p.1 / Chapter 1.1.1 --- Scalability of Network Capacity with Power Control --- p.1 / Chapter 1.1.2 --- Trade-off between network capacity and fairness with Power Control --- p.3 / Chapter 1.2 --- Related Work --- p.4 / Chapter 1.3 --- Organization of the Thesis --- p.6 / Chapter Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Hidden- and Exposed-node Problems --- p.8 / Chapter 2.1.1 --- HN-free Design (HFD) --- p.9 / Chapter 2.1.2 --- Non-Scalable Capacity in 802.11 caused by EN --- p.11 / Chapter 2.2 --- Shortcomings of Minimum-Transmit-Power Approach --- p.13 / Chapter Chapter 3 --- Simultaneous Transmissions Constraints with Power Control --- p.15 / Chapter 3.1 --- Physical-Collision Constraints --- p.16 / Chapter 3.1.1 --- Protocol-Independent Physical-Collision Constraints --- p.17 / Chapter 3.1.2 --- Protocol-Specific Physical-Collision Constraints --- p.17 / Chapter 3.2 --- Protocol-Collision-Prevention Constraints --- p.18 / Chapter 3.2.1 --- Transmitter-Side Carrier-Sensing Constraints --- p.18 / Chapter 3.2.2 --- Receiver-Side Carrier-Sensing Constraints --- p.19 / Chapter Chapter 4 --- Graph Models for Capturing Transmission Constraints and Hidden-node Problems --- p.20 / Chapter 4.1 --- Link-Interference Graph from Physical-Collision Constraints --- p.21 / Chapter 4.2 --- Protocol-Collision-Prevention Graphs --- p.22 / Chapter 4.3 --- Ideal Protocol-Collision-Prevention Graphs --- p.22 / Chapter 4.4 --- Definition of HN and EN and their Investigation using Graph Model --- p.23 / Chapter 4.5 --- Attacking Cases --- p.26 / Chapter Chapter 5 --- Scalability of Network Capacity with Adaptive Power Control --- p.27 / Chapter 5.1 --- Selective Disregard of NAVs (SDN) --- p.27 / Chapter 5.2 --- Scalability of Network Capacity: Analytical Discussion --- p.29 / Chapter 5.3 --- Adaptive Power Control for SDN --- p.31 / Chapter 5.3.1 --- Per-iteration Power Adjustment --- p.32 / Chapter 5.3.2 --- Power Control Scheduling Strategy --- p.35 / Chapter 5.3.3 --- Power Exchange Algorithm --- p.39 / Chapter 5.3.4 --- Comparison of Scheduling Strategies --- p.41 / Chapter 5.4 --- Scalability of Network Capacity: Numerical Results --- p.43 / Chapter Chapter 6 --- Decoupled Adaptive Power Control (DAPC) --- p.45 / Chapter 6.1 --- Per-iteration Power Adjustment --- p.45 / Chapter 6.2 --- Power Exchange Algorithm --- p.47 / Chapter 6.3 --- Implementation of DAPC --- p.48 / Chapter 6.4 --- Deadlock Problem in DAPC --- p.50 / Chapter Chapter 7 --- Progressive-Uniformly-Scaled Power Control (PUSPC): Deadlock-free Design --- p.53 / Chapter 7.1 --- Algorithm of PUSPC --- p.53 / Chapter 7.2 --- Deadlock-free property of PUSPC --- p.60 / Chapter 7.3 --- Deadlock Resolution of DAPC using PUSPC --- p.62 / Chapter Chapter 8 --- Incremental Power Adaptation --- p.65 / Chapter 8.1 --- Incremental Power Adaptation (IPA) --- p.65 / Chapter 8.2 --- Maximum Allowable Power in EPA --- p.68 / Chapter 8.3 --- Numerical Results of IPA --- p.71 / Chapter Chapter 9 --- Numerical Results and the Trade-off between EN and HN --- p.78 / Chapter Chapter 10 --- Conclusion --- p.83 / Appendix I: Proof of the Correct Operation of PE Algorithm for APC for SDN --- p.86 / Appendix II: Proof of the Correct Operation of PE Algorithm for DAPC --- p.89 / Appendix III: Scalability of the Communication Cost of PE Algorithm --- p.91 / Bibliography --- p.93

abstract: With the increasing complexity of computing systems and the rise in the number of risks and vulnerabilities, it is necessary to provide a scalable security situation awareness tool to assist the system administrator in protecting the critical assets, as well as managing the security state of the system. There are many methods to provide security states' analysis and management. For instance, by using a Firewall to manage the security state, and/or a graphical analysis tools such as attack graphs for analysis. Attack Graphs are powerful graphical security analysis tools as they provide a visual representation of all possible attack scenarios that an attacker may take to exploit system vulnerabilities. The attack graph's scalability, however, is a major concern for enumerating all possible attack scenarios as it is considered an NP-complete problem. There have been many research work trying to come up with a scalable solution for the attack graph. Nevertheless, non-practical attack graph based solutions have been used in practice for realtime security analysis. In this thesis, a new framework, namely 3S (Scalable Security Sates) analysis framework is proposed, which present a new approach of utilizing Software-Defined Networking (SDN)-based distributed firewall capabilities and the concept of stateful data plane to construct scalable attack graphs in near-realtime, which is a practical approach to use attack graph for realtime security decisions. The goal of the proposed work is to control reachability information between different datacenter segments to reduce the dependencies among vulnerabilities and restrict the attack graph analysis in a relative small scope. The proposed framework is based on SDN's programmable capabilities to adjust the distributed firewall policies dynamically according to security situations during the running time. It apply white-list-based security policies to limit the attacker's capability from moving or exploiting different segments by only allowing uni-directional vulnerability dependency links between segments. Specifically, several test cases will be presented with various attack scenarios and analyze how distributed firewall and stateful SDN data plan can significantly reduce the security states construction and analysis. The proposed approach proved to achieve a percentage of improvement over 61% in comparison with prior modules were SDN and distributed firewall are not in use. / Dissertation/Thesis / Masters Thesis Computer Engineering 2018

Este trabalho reside no campo de sistemas multiagente (MAS) compostos por agentes inteligentes que são capazes de usar protocolos de comunicação da Internet. Uma plataforma multiagente é um software ou framework capaz de gerenciar múltiplos aspectos da execução de agentes e suas interações. Muitas plataformas MAS foram desenvolvidas nos últimos anos, todas elas compatíveis com padrões de desenvolvimento de sistemas interoperáveis em diferentes níveis. Nos últimos anos,novas linguagens de programação foram definidas e novos protocolos foram adotados para comunicação em sistemas distribuídos. Esses fatos também influenciaram a comunidade multiagente,com a proposição de novas plataformas para apoiar o desenvolvimento de sistemas multiagente. Além disso, a adoção de agentes como paradigma para o desenvolvimento de sistemas distribuídos complexos em larga escala é vista como uma solução interessante na era do grande volume de dados. Portanto, uma comparação entre as plataformas existentes e seu suporte para desenvolver e implantar com eficiência sistemas multiagente de grande escala pode beneficiar a comunidade de desenvolvedores interessada em escolher qual plataforma melhor se adapta a seus projetos. O objetivo deste trabalho é avaliar plataformas multiagente em relação à escalabilidade, desempenho e compatibilidade com outras tecnologias com o objetivo de facilitar a escolha do desenvolvedor que queira projetar Sistemas Multiagente de grande porte. A fim de escolher as plataformas MAS para a comparação proposta, são consideradas plataformas de código aberto que são ativamente utilizadas pela comunidade multiagente. Além disso, tais plataformas MAS devem ser capazes de oferecer uma implantação de forma distribuída, característica essencial de sistemas escaláveis. Depois de restringir a lista de plataformas MAS de acordo com esses critérios, são analisados os sistemas de transporte de mensagens utilizando benchmarks para análise de escalabilidade e desempenho, considerando diferentes cenários de comunicação. Por fim, é apresentado um cenário realístico onde um MAS escalável pode ser adotado como solução. / This work resides in the field of multiagent systems (MAS) composed of intelligent agents that are able to use Internet communication protocols. A multiagent platform is a software or framework capable of managing multiple aspects of the agent execution and their interactions. In the recent years, many MAS platforms have been developed, all of them compliant with interoperable system development standards at different levels. Also, new programming languages have been defined and new protocols have been adopted for communication in distributed systems. These facts also influenced the multiagent community with the proposition of new platforms to support the development of multiagent systems. In addition, the adoption of agents as a paradigm for the development of large scale complex distributed systems is seen as an interesting solution in the era of big data. Therefore, a comparison between existing platforms and their support for efficiently developing and deploying large scale multiagent systems can benefit the developer community interested in choosing which platform best fits their projects. The purpose of this work is evaluate multiagent platforms for scalability, performance and compatibility with other technologies in order to facilitate the choice of the developer that wants design large scale multiagent systems. In order to choose MAS platforms for the proposed comparison, are considered open source platforms that are actively used by the multiagent community. Moreover, these MAS platforms should be able to provide a deployment in a distributed manner, essential characteristic of scalable systems. After narrowing the list of MAS platforms according to these criteria, message transport systems are analyzed using benchmarks for scalability and performance comparison, considering different communication scenarios. Finally, a realistic scenario is presented where a scalable MAS can be adopted as a solution.

Providing the ability to increase or decrease allocated resources on demand as the transactional load varies is essential for database management systems (DBMS) deployed on today's computing platforms, such as the cloud. The need to maintain consistency of the database, at very large scales, while providing high performance and reliability makes elasticity particularly challenging. In this thesis, we exploit data partitioning as a way to provide elastic DBMS scalability. We assert that the flexibility provided by a partitioned, shared-nothing parallel DBMS can be used to implement elasticity. Our idea is to start with a small number of servers that manage all the partitions, and to elastically scale out by dynamically adding new servers and redistributing database partitions among these servers as the load varies. Implementing this approach requires (a) efficient mechanisms for addition/removal of servers and migration of partitions, and (b) policies to efficiently determine the optimal placement of partitions on the given servers as well as plans for partition migration. This thesis presents Elasca, a system that implements both these features in an existing shared-nothing DBMS (namely VoltDB) to provide automatic elastic scalability. Elasca consists of a mechanism for enabling elastic scalability, and a workload-aware optimizer for determining optimal partition placement and migration plans. Our optimizer minimizes computing resources required and balances load effectively without compromising system performance, even in the presence of variations in intensity and skew of the load. The results of our experiments show that Elasca is able to achieve performance close to a fully provisioned system while saving 35% resources on average. Furthermore, Elasca's workload-aware optimizer performs up to 79% less data movement than a greedy approach to resource minimization, and also balance load much more effectively.

This thesis is predicated upon a vision of the future of computing with a separation of functionality between core and edges, very similar to that governing the Internet itself. In this vision, the core of our computing infrastructure is made up of vast server farms with an abundance of storage and processing cycles. Centralization of computation in these farms, coupled with high-speed wired or wireless connectivity, allows for pervasive access to a highly-available and well-maintained repository for data, configurations, and applications. Computation in the edges is concerned with provisioning application state and user data to rich clients, notably mobile devices equipped with powerful displays and graphics processors. We define flexible computing as systems support for applications that dynamically leverage the resources available in the core infrastructure, or cloud. The work in this thesis focuses on two instances of flexible computing that are crucial to the realization of the aforementioned vision. Location flexibility aims to, transparently and seamlessly, migrate applications between the edges and the core based on user demand. This enables performing the interactive tasks on rich edge clients and the computational tasks on powerful core servers. Scale flexibility is the ability of applications executing in cloud environments, such as parallel jobs or clustered servers, to swiftly grow and shrink their footprint according to execution demands. This thesis shows how we can use system virtualization to implement systems that provide scale and location flexibility. To that effect we build and evaluate two system prototypes: Snowbird and SnowFlock. We present techniques for manipulating virtual machine state that turn running software into a malleable entity which is easily manageable, is decoupled from the underlying hardware, and is capable of dynamic relocation and scaling. This thesis demonstrates that virtualization technology is a powerful and suitable tool to enable solutions for location and scale flexibility.

This thesis is predicated upon a vision of the future of computing with a separation of functionality between core and edges, very similar to that governing the Internet itself. In this vision, the core of our computing infrastructure is made up of vast server farms with an abundance of storage and processing cycles. Centralization of computation in these farms, coupled with high-speed wired or wireless connectivity, allows for pervasive access to a highly-available and well-maintained repository for data, configurations, and applications. Computation in the edges is concerned with provisioning application state and user data to rich clients, notably mobile devices equipped with powerful displays and graphics processors. We define flexible computing as systems support for applications that dynamically leverage the resources available in the core infrastructure, or cloud. The work in this thesis focuses on two instances of flexible computing that are crucial to the realization of the aforementioned vision. Location flexibility aims to, transparently and seamlessly, migrate applications between the edges and the core based on user demand. This enables performing the interactive tasks on rich edge clients and the computational tasks on powerful core servers. Scale flexibility is the ability of applications executing in cloud environments, such as parallel jobs or clustered servers, to swiftly grow and shrink their footprint according to execution demands. This thesis shows how we can use system virtualization to implement systems that provide scale and location flexibility. To that effect we build and evaluate two system prototypes: Snowbird and SnowFlock. We present techniques for manipulating virtual machine state that turn running software into a malleable entity which is easily manageable, is decoupled from the underlying hardware, and is capable of dynamic relocation and scaling. This thesis demonstrates that virtualization technology is a powerful and suitable tool to enable solutions for location and scale flexibility.