Large-scale graph-structured computation is becoming increasingly important for various data analytics applications. However, most distributed graph processing frameworks do not directly support efficient implementation of sophisticated algorithms requiring massive graph traversals. In this paper, we propose concurrent hybrid breadth-first-search (BFS) algorithm on a popular distributed graph processing framework (Power-Graph and its optimized version PowerLyra). It leverages the small-world property of skewed graphs which apply to most realworld data sets. Hybrid BFS algorithm changes graph traversal direction to save computational workload and message transmissions. Concurrent BFS algorithm enables running multiple BFS simultaneously while sharing vertex explorations efficiently with bit operations. Extensive experiments are conducted to evaluate performance and scalability on a multi-core computer and a cluster of AWS instances. Concurrent hybrid BFS algorithm dramatically increases graph traversal efficiency with respect to the increasing number of concurrent BFS traversals. Compared with PowerGraph, PowerLyra uses fewer resources, while achieving significantly higher performance and better scalability.

Managing resources and cleverly pricing them on computing systems is a challenging task. Resource sharing demands careful load balancing and often strives to achieve a win-win situation between resource providers and users. Toward this goal, we consider a joint treatment of load balancing and pricing. We do not assume static pricing to determine load balancing, or vice versa. Instead, we study the relationship between the price that a computing node is charged and the load and revenue that it receives. We find that there exists an optimal price which maximizes the revenue. We then consider a multi-user environment and explore how the load from a user can be balanced on processors with existing loads. Finally, we derive an optimal price that maximizes the revenue in the multi-user environment. We evaluate the performance of the proposed algorithms through simulations.

Cloud computing is a suitable platform for execution of complex computational tasks and scientific simulations that are described in the form of workflows. Such applications are managed by Workflow Management System (WfMS). Because existing WfMSs are not able to autonomically provision resources to real-time applications and schedule them while supporting fault tolerance and data privacy, we present a highly-scalable workflow-enabled analytics system that manages inter-dependable analytics tasks adaptively with varying operational requirements on a common platform and enables visualization of multidimensional datasets of real world phenomena. In this paper, we present the architecture of such a WfMS and evaluate it in terms of performance for execution of workflows in Clouds. A real world application of climate-associated dengue fever prediction was evaluated on public, private, and hybrid Clouds and experienced effective speedup in all the environments.

Fault-tolerant scheduling is an imperative step for large-scale computational grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary copy and a backup copy on two different processors. In this paper, we identify two cases that may happen when scheduling dependent tasks with primary-backup approach. We derive two important constraints that must be satisfied. Further, we show that these two constraints play a crucial role in limiting the schedulability and overloading efficiency of backups of dependent tasks. We then propose two strategies to improve schedulability and overloading efficiency, respectively. We propose two algorithms (MRC-ECT and MCT-LRC), to schedule backups of independent jobs and dependent jobs, respectively. MRC-ECT is shown to guarantee an optimal backup schedule in terms of replication cost for an independent task, while MCT-LRC can schedule a backup of a dependent task with minimum completion time and less replication cost. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms.

We consider Label Switched Path (LSP) protection for connections with various protection grade requirements in multi-protocol label switching (MPLS) over wavelength division multiplexing (WDM) optical networks. In full protection, bandwidth needs to be reserved for the backup LSP to protect the failure of any fiber along the primary LSP. In this paper, we study the problem of partial spatial-protection (PSP) where bandwidth is reserved for the backup LSP to protect the failure of a subset of fibers traversed by the primary LSP to satisfy the specified protection grade. We formulate the optimal LSP PSP problem as an ILP and identify three suboptimal problems. For each suboptimal problem, an exhaustive search algorithm and a heuristic are developed. We analyze the probability that a connection can be restored upon a fiber failure and find that it is higher than or equal to the protection grade specified. We also develop a failure recovery protocol which specifies recovery operations upon failure and determines whether a connection can be recovered if the failed fiber is one of its unprotected fibers. Through extensive simulation experiments, we demonstrated that the proposed LSP PSP algorithms perform better than shared LSP protection in blocking probability and resource efficiency.

Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, the primary-backup approach is a common methodology used for fault tolerance where in each task has a primary copy and a backup copy on two different processors. Backup overloading has been proposed to reduce replication cost by allowing the backup copy to overload with other backup copies on the same processor. In this paper, we consider two classes of independent tasks where in both the classes have fault-tolerance requirements. Furthermore, Class 1 tasks require the response time to be as short as possible when a fault occurs, while Class 2 tasks prefer backups with minimum replication cost. We propose two algorithms, called the MRC-ECT algorithm and the MCT-LRC algorithm. Algorithm MRC-ECT is shown to guarantee an optimal backup schedule in terms of replication cost, while MCT-LRCcan schedule a backup with minimum completion time and low replication cost. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms.

This paper presents an efficient protection scheme to dynamically allocate restorable bandwidth-guaranteed paths in integrated IP-over-WDM networks. A restorable bandwidth-guaranteed path implies an active path and another link-disjoint backup path both with the required bandwidth. Dynamic traffic where connection requests arrive one by one with no knowledge about future requests is assumed. We consider integrated IP/WDM networks with generalized multi-protocol label switching (GMPLS) capabilities. To optimize the network resources, we provide the protection at the multi-protocol label switching (MPLS) layer and backup resources are judiciously shared among different requests at the label switched path (LSP) level. To allocate the restorable bandwidth-guaranteed paths, we propose two integrated routing algorithms: hop-based integrated routing algorithm (HIRA) and bandwidth-based integrated routing algorithm (BIRA). We use connection blocking probability and number of optical-electrical-optical (o-e-o) conversions as performance metrics to evaluate these two algorithms. Through extensive simulation experiments, we demonstrate that our algorithms perform better in terms of the above two metrics than other existing approaches.