157 research outputs found
A dynamically adaptive, unstructured multicast overlay
No full textThe simplicity of multicast as a communication primitive belies its broad utility as a building block for distributed applications. Nevertheless, creating and maintaining multicast structures can be challenging, particularly when networks are transient and/or dynamic. We introduce a new unstructured multi-source multicast (UMM) overlay approach that we argue is less complex than, but as efficient as, current state-of-the-art solutions based either on structured overlays or on running full routing protocols at the overlay level. UMM builds a base overlay independently from the routing mechanisms employed to route messages. On top of this base overlay, it selects distribution trees for each multicast source by first flooding the base overlay and then using the implicit information contained in duplicated messages to select and filter out redundant tunnels. Simple heuristics are used to maintain and evolve both the base overlay and the multicast distribution trees in response to changes in the set of overlay participants or in underlying network conditions. We experiment on a 65-node PlanetLab deployment and on ModelNet emulated distributed platforms to quantify the overheads associated with UMM operation and to explore its performance and adaptability to changes in the underlying network conditions
A framework for the management of dynamic SLAs in composite service scenarios
No full textThe advent of information and communication technology has changed the nature of business-to-business interaction among organizations. The use of electronic contracts with automated support for their management allows an increase of effectiveness and efficiency in contract processing, opening new possibilities for interaction among parties. Service Providers and their customers negotiate utility based Service Level Agreements (SLA) to determine costs and penalties based on the achieved performance levels. The global QoS to be provided to the end customer can be strongly affected by any violation on each single SLA. In order to prevent such violations, SLAs need to be flexible and dynamically adaptable. In this work we focus on the WS-Agreement specification, a Web Service protocol to establish agreements on the QoS level to be guaranteed in the provision of a service. We propose to enhance the flexibility of its approach by integrating new functionality to the protocol that enable the parties of a WS-Agreement to re-negotiate and modify its terms during the service provisio
Asynchronous dynamic graph processing with real-time analysis
No full textThe rapid increase in connected data from various sources such as the World Wide Web, social networks, and financial transactions has led to the widespread use of graph-based representations for data analysis of these networks. However, traditional high-performance computing (HPC) solutions designed for static graphs are inefficient and impractical for dynamic graphs that evolve over time. This approach leads to high overheads, loss of information between snapshots, and potential correctness issues.
The demand for fast, real-time analytics on continuously evolving real-world systems at a massive scale has become critical for applications such as online recommendations, financial fraud detection, and counter-terrorism. For example, social media networks like Facebook handle potentially millions of interactions per second, and payment networks like Visa process thousands of transactions per second. To address these challenges, my dissertation focuses on the opportunities and challenges of analyzing dynamic graphs in real-time, offering an infrastructure-algorithm co-design for dynamic graph analytics at scale.
To this end, I develop and present a pattern for dynamic graph algorithms, and a supporting software infrastructure architecture, that together form a cohesive real-time graph analysis model. My algorithm pattern is designed to be amenable to distributed systems with concepts such as message passing, asynchronicity, and termination, while considering the timeliness requirements for real-time analysis. The infrastructure architecture considers real-world properties of dynamic data generation and hardware constraints, aiming for versatility, performance, and scalability. It supports dynamic graph topology evolution and provides interfaces for expressing algorithms for dynamic graph analysis and collecting results during runtime.
I demonstrate that many common static graph algorithms can be re-designed for dynamic processing and real-time analysis, and can be built and scaled efficiently. My dynamic graph model offers advantages over static designs, such as low-cost updates to the graph and the ability to observe algorithm results before or after topology modifications. The implementation of my model shows near-linear scalability in performance, and supports real-time analysis at potentially orders of magnitude higher evolution rates compared to alternative designs; providing a generic, scalable, and performant solution for dynamic graph analysis, addressing the challenges of analyzing large-scale, continuously evolving network data in real-time.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
On paradigm shifts : enabling proactive defenses by identifying the vulnerable population, and online bitemporal dynamic graph analytics
No full textFueled by the massive amount of data and meta-data harvested by large-scale online service providers, two trends stand out: the broad adoption of machine learning particularly for cybersecurity defenses, and the growing pains of temporal graph analytics particularly for dynamically evolving systems.
In this dissertation, my overarching goal is to explore novel ways: to effectively harness this harvested data to evidently improve the security of online platforms in general and their most vulnerable users in particular, and to explicitly model the temporal evolution of this data to efficiently enable business use cases that can not be served by existing graph analytics systems. To that end, I advocate for a paradigm shift across two high impact domains: cybersecurity and graph analytics.
On the one hand, existing cybersecurity defenses are reactive, and victim-agnostic: they are predicated on identifying the attacks/attackers, and do not take user characteristics into account. In contrast, I propose a proactive approach based on identifying the vulnerable population, and leveraging this information to improve the security of the platform in general and the most vulnerable users in particular.
To that end, I approach harnessing the vulnerable population under a victim-centric defense paradigm while contrasting against conventional defenses, and demonstrate its feasibility using four months of production data encompassing billions of events from hundreds of millions of users.
To my knowledge, I am the first to propose and discuss such a defense paradigm.
On the other hand, existing graph analytics systems are mostly static, and non-temporal: they are not fully able to support modeling systems that evolve dynamically over time while supporting the queries (including current state, historical, and audit queries) required by today's use cases. In contrast, I contend that future graph analytics systems should be: online, dynamic, and employ bitemporal modeling at their core.
To that end, I examine the use cases that are an ideal match for an online bitemporal dynamic graph analytics system, explore the design trade-off space, and develop and characterize several designs targeting different points within that space.
To my knowledge, I am the first to propose, develop, and characterize such a system end-to-end.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Towards variability-aware frequency scaling on heterogeneous edge platforms
No full textRecent Edge applications (e.g., machine learning inference) are becoming more sophisticated and computationally demanding. To meet their Quality of Service (QoS) objectives, today’s heterogeneous Edge platforms (e.g., NVIDIA Jetson platform) incorporate several architectural innovations. One that stands out is the wide frequency configuration space (more than a dozen frequency levels per processing unit spanning a 10x max-min ratio). We postulate that this can be harnessed to better navigate the trade-off space between performance and power consumption.
This dissertation makes progress towards harnessing frequency scaling on Edge platforms. We start by exploring the potential gains from frequency scaling on the NVIDIA Jetson platform. To this end, we develop an empirical methodology to characterize the performance and power consumption behavior of the Jetson platform under different frequency configurations. Our characterization indicates that indeed there is an opportunity to improve performance and/or energy-efficiency with careful frequency configuration selection. However, one challenge is to estimate the impact of the frequency configuration choice on performance and power consumption of the workload.
To overcome this challenge, we employ machine learning techniques to build performance and power consumption models for the target workload. While developing these models, we find that the quality of their predictions depends on where the models are deployed (even if they are deployed on identical devices with identical software stacks). This leads us to postulate that variability in performance and power consumption among nominally identical Edge platforms exists and is sizeable. To investigate this hypothesis, we develop statistical tools that allow developers to detect, quantify, categorize, and compare variability. Then we present a set of actions one can take to mitigate the impact of variability. We evaluate all the techniques and approaches on two clusters of popular Edge platforms - the Jetson AGX and Nano.
Finally, we focus on developing variability-aware performance and power
consumption models. We show that not accounting for variability can severely impact the quality of predictions. The evaluation of the models shows that accounting for inter-node variability improves the Root Mean Square Error (RMSE) by 9.5% and 31.9% for runtime and power models respectively.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
EdgeEngine : a thermal-aware optimization framework for edge inference
No full textHeterogeneous edge platforms enable the efficient execution of machine learning inference applications. These applications often have a critical constraint (such as meeting a deadline) and an optimization goal (such as minimizing energy consumption). To navigate this space, existing optimization frameworks adjust the platform's frequency configuration for the CPU, the GPU and/or the memory controller. These optimization frameworks, however, are thermal-oblivious disregarding the fact that edge platforms are frequently deployed in environments where they are exposed to ambient temperature variations.
In this thesis, we first characterize the impact of ambient temperature on the power consumption and execution time of machine learning inference applications running on a popular edge platform, the NVIDIA Jetson TX2. Our rigorous data collection and statistical methodology reveals a sizeable ambient temperature impact on power consumption (about 20\% on average, and up to 40\% on some workloads) and a moderate impact on runtime (up to 5\%). We also find that existing, thermal-oblivious optimization frameworks select frequency configurations that either violate the application's constraints and/or are sub-optimal in terms of the optimization goal assigned.
To address these shortcomings, we propose EdgeEngine, a lightweight thermal-aware optimization framework. EdgeEngine monitors the platform's temperature and uses reinforcement learning to adjust the frequency configuration of all underlying platform resources to meet the application's constraints. We find that EdgeEngine meets the application's constraint, and achieves up to 29\% lower energy consumption (up to 2x) and up to 41\% fewer violations compared to existing state-of-the-art thermal-oblivious optimization frameworks.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Towards context-aware Telecom end user services through SOA
No full textIn this paper a SOA inspired context-aware platform to enable context-aware Telecom services is presented. The SOA related components are highlighted and the platform’s integration into a Telecom provider’s service architecture is described — pointing out challenges in terms of protocols and semantic interoperability. An example application bridging the gap between data collected through a user’s mobile phone and a web based portal in order to provide a Virtual Location Application through the proposed platform is presented
PiMPACT : (re)assessing PiM impact
No full textProcessing-in-Memory (PiM) has gained attention as a potential solution to address the "memory wall" in high-performance computing applications. Recently the first general-purpose PiM technology - dubbed UPMEM - has been made commercially available.
While several studies report substantial advantage (often as application speedup) of UPMEM-equipped servers over high-end CPUs, these findings are often "fragile" due to overlooked factors, such as: (i) using unoptimized code on either one or both sides of the comparison, (ii) excluding overheads inherent to the accelerator-like processing model offered by UPMEM, (iii) ignoring power or energy consumption in the comparison, and (iv) high dependence on the the choice of CPU hardware baseline which can dramatically change the conclusions. This thesis aims to address these limitations by reexamining UPMEM PiM’s effectiveness within specific
application contexts.
To that end, we focus on applications that are well-suited for UPMEM, primarily in the area of genomic sequence alignment, and conduct a rigorous performance evaluation, ensuring both UPMEM and CPU codes are reasonably optimized, extending the comparison to include power consumption, and performing cost- and power-normalized comparisons to mitigate hardware dependency.
Our experiments reveal that, after applying optimizations to CPU baselines, the previously observed performance gap narrows significantly, and in many cases, the CPU-equipped servers offer an advantage even in terms of raw performance. More importantly, cost- and power-normalized comparisons suggest that while UPMEM may offer potential benefits in the future, the current technology is unlikely to offer a cost- or power-normalized advantage compared to CPU baselines for the set of applications we evaluate.
Finally, we provide practical heuristics to guide decisions on which types of computational tasks are best suited for offloading to UPMEM PiM system. These insights aim to assist researchers and practitioners in effectively leveraging UPMEM technology where may offer an advantage.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Two problems in dynamic graph analytics : maximum flow and online partitioning
No full textMany real-world systems, such as social networks and financial transactions, evolve quickly over time and can be modelled as dynamic graphs. Dynamic graph processing systems emerged to provide timely analysis on these graphs, ingesting graph updates through one or more streams, and providing (on-demand or regularly) answers to a standing query. This thesis explores both the algorithmic and the infrastructural aspects of dynamic graph processing.
On the algorithm side, this thesis proposes the vertex-local invariant restoration approach for designing dynamic graph algorithms. With this approach, we propose a novel algorithm for the maximum flow problem, targeting graphs that evolve quickly with millions of edge changes per second. The algorithm works well on a shared-nothing, asynchronous computational model in which the graph topology is updated concurrently as the algorithm executes. We prove that the algorithm is correct and provide a thorough experimental evaluation with difficult cases on large real-world dynamic graphs, showing that the algorithm obtains high throughputs, supports both additions and deletions efficiently, and provides results with low latency and high stability.
On the infrastructure side, this thesis explores a new problem that appears when processing dynamic graphs: online partitioning. A common model in dynamic graph processing is that the system ingests a stream of edge updates (edge add/remove/modify events), and creates and assigns a vertex—and its edge list—to a partition when first observing an edge that references the vertex. The common solution is to use random partitioning—vertices assigned to partitions based on hashes of their IDs, but it leads to suboptimal edge-cut minimization and/or load balance. This thesis proposes the Minimum Load with Affinity framework for systematic exploration of the trade-offs in a partitioning strategy: load balance, edge-cut minimization, and ingestion delay. The preliminary results show that MLA can (i) achieve a 7%-14% reduction in edge-cuts without sacrificing load balance (or a much higher reduction by sacrificing load balance), and (ii) achieve both better edge-cut minimization and load balance by ingesting edges in batches and reasoning about batch properties (at the cost of higher ingestion latency).Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
StPowla: SOA, Policies and Workflows
No full textWe introduce STPOWLA, a workflow based approach to business process modelling that integrates a simple graphical notation, to ease the presentation of the core business process, a user–friendly policy language, APPEL, to provide the necessary adaptation to the varied expectations of the various business stakeholders, and the Service Oriented Architecture, to assemble and orchestrate available services in the business process. We illustrate the approach with a loan approval process
- …
