The Stable Marriage Problem (SMP) is a combinatorial optimization problem aimed at creating stable pairings between two groups, traditionally referred to as men and women. SMP has been widely applied across various domains, including healthcare, education, and cloud computing, to optimize resource allocation, matching, and utilization. The classical approach to solving SMP is based on the Gale-Shapley algorithm, which constructs stable pairings sequentially. However, this algorithm is both time-consuming and data-intensive, resulting in significant slowdowns even for a moderate number of participants. Despite various attempts to parallelize the Gale-Shapley algorithm over the years, progress has been consistently impeded by three major bottlenecks: (1) frequent and expensive data movement, (2) high synchronization overhead, and (3) workload-dependent and irregular data accessing and parallel processing patterns. To resolve the above-mentioned bottlenecks, in this paper, we introduce Bamboo-SMP, a highly efficient parallel SMP algorithm, and its implementation in a hybrid environment of GPUs and CPUs. We have made three key development efforts to achieve high performance for Bamboo-SMP. First, Bamboo-SMP effectively exploits the data accessing locality with a lightweight data structure to maximize the “shared residence space”. Second, Bamboo-SMP employs an advanced hardware atomic operation to decrease execution latency with “low contention”. Third, Bamboo-SMP is implemented in a hybrid environment of GPU and CPU, leveraging the high bandwidth of the GPU for massive parallel operations and the low latency of CPU for fast sequential tasks. By fostering “mutual complementarity” between CPU and GPU, Bamboo-SMP attains superior performance, consistently exceeding the best existing methods by 6.69 x to 21.44 x across a wide range of workloads. Moreover, Bamboo-SMP demonstrates excellent scalability, efficiently solving large-scale SMP instances while achieving sustained speedups of $5.6 \times$ to $13.8 \times$ on 4 GPUs. To the best of our knowledge, Bamboo-SMP is the fastest and most scalable solution for SMP data processing.

Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with blocking (FJQN/B). While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize their throughput performance at scale theoretically. What further complicates the study is the presence of heavy-tailed delays that have been widely documented therein. In this article, we utilize an infinite sequence of FJQN/Bs to study the throughput limit and focus on an important class of heavy-tailed service times that are regularly varying with index . The throughput is said to be scalable if the throughput limit infimum of the sequence is strictly positive as the network size grows to infinity. We introduce two novel geometric concepts—scaling dimension and extended metric dimension—and show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension and only if the scaling dimension . We also show that for the cases where buffer sizes are scaling in an order of , the scalability conditions are relaxed by a factor of . The results provide new insights on the scalability of a rich class of FJQN/Bs with various structures, including tandem, lattice, hexagon, pyramid, tree, and fractals.

We develop a data-driven adaptive control framework to password management in cyber security systems. A password policy is the frontline of protection against cyber attacks, which contains a set of rules on password length, duration, etc. We assume password has censored lifetime, and policy maker determines the duration of the password without complete knowledge of its true lifetime distribution. We develop a gradient based algorithm integrated with a Bayesian learning framework. We show that our algorithm converges to optimal solution and adapts to non-stationary lifetime data.

Due to emerging applications such as cloud computing and big data analytics, modern information processing systems are growing increasingly large and complex. A critical issue concerns the throughput performance as the system grows in size. This paper models distributed information processing systems as fork and join queueing networks with blocking. We identify necessary and sufficient conditions for throughput scalability of such fork and join networks as they grow in size. Previous studies have either focused on special structured networks such as tandem or tree networks, or provided only necessary conditions for throughput scalability. In this paper, we show that such necessary conditions are not sufficient. We present a key topological concept called ``minimum level" of the underlying graph, and develop lower and upper bounds for the throughput of arbitrary FJQN/Bs. The bounds depend on network degree, minimum level, deterministic cycle time, buffer sizes, and service time distributions, but not on network size. We show that level-boundedness and degree-boundedness are necessary and sufficient conditions to guarantee that the throughput of an FJQN/B is bounded away from zero as network size goes to infinity.

Distributed joint congestion control and routing optimization has received a significant amount of attention recently. To date, however, most of the existing schemes follow a key idea called the back-pressure algorithm. Despite having many salient features, the first-order subgradient nature of the back-pressure based schemes results in slow convergence and poor delay performance. To overcome these limitations, in this paper, we make a first attempt at developing a second-order joint congestion control and routing optimization framework that offers utility-optimality, queue-stability, fast convergence, and low delay. Our contributions in this paper are three-fold: i) we propose a new second-order joint congestion control and routing framework based on a primal-dual interior-point approach; ii) we establish utility-optimality and queue-stability of the proposed second-order method; and iii) we show how to implement the proposed second-order method in a distributed fashion.

In this paper, we consider the problem of distributed load shedding optimization for disaster recovery in smart grids. We develop distributed second-order interior-point based load shedding algorithms that enjoy a fast quadratic convergence rate. Our main contributions are two-fold: (i) We propose a rooted spanning tree based reformulation that enables our distributed algorithm design; (ii) Based on the spanning tree reformulation, we design distributed computation schemes for our proposed second-order interior-point based load shedding. Collectively, these results serve as an important first step in load shedding and disaster recovery that uses second-order distributed techniques.

Due to the rapidly growing scale and heterogeneity of wireless networks, the design of distributed cross-layer optimization algorithms has received significant interest from the networking research community. So far, the standard distributed cross-layer approach in the literature is based on the first-order Lagrangian dual decomposition and the subgradient method, which suffers from a slow convergence rate. In this paper, we make the first known attempt to develop a distributed Newton's method, which is second-order and enjoys a quadratic convergence rate. However, due to the inherent interference in wireless networks, the Hessian matrix of the cross-layer problem has a non-separable structure. As a result, developing a distributed second-order algorithm is far more difficult than its counterpart for wireline networks. Our main contributions in this paper are two-fold: i) For a special network setting where all links mutually interfere, we derive closed-form expressions for the Hessian inverse, which further yield a distributed Newton's method; ii) For general wireless networks where the interference relationships are arbitrary, we propose a double matrix-splitting scheme, which also leads to a distributed Newton's method. Collectively, these results create a new theoretical framework for distributed cross-layer optimization in wireless networks. More importantly, our work contributes to a potential second-order paradigm shift in wireless networks optimization theory.

Resource provisioning, the task of planning sufficient amounts of resources to meet service level agreements, has become an important management task in emerging cloud computing services. In this paper, we present a stochastic modeling approach to guide the resource provisioning task for future service clouds as the demand grows large. We focus on on-demand services and consider service availability as the key quality of service constraint. A specific scenario under consideration is when resources can be measured in base instances. We develop an asymptotic provisioning methodology that utilizes tight performance bounds for the Erlang loss system to determine the minimum capacity levels that meet the service availability requirements. We show that our provisioning solutions are not only asymptotically exact but also provide better QoS guarantees at all load conditions.

Traditional parallel processing models, such as BSP, are "scale up" based, aiming to achieve high performance by increasing computing power, interconnection network bandwidth, and memory/storage capacity within dedicated systems, while big data analytics tasks aiming for high throughput demand that large distributed systems "scale out" by continuously adding computing and storage resources through networks. Each one of the "scale up" model and "scale out" model has a different set of performance requirements and system bottlenecks. In this paper, we develop a general model that abstracts critical computation and communication behavior and computation-communication interactions for big data analytics in a scalable and fault-tolerant manner. Our model is called DOT, represented by three matrices for data sets (D), concurrent data processing operations (O), and data transformations (T), respectively. With the DOT model, any big data analytics job execution in various software frameworks can be represented by a specific or non-specific number of elementary/composite DOT blocks, each of which performs operations on the data sets, stores intermediate results, makes necessary data transfers, and performs data transformations in the end. The DOT model achieves the goals of scalability and fault-tolerance by enforcing a data-dependency-free relationship among concurrent tasks. Under the DOT model, we provide a set of optimization guidelines, which are framework and implementation independent, and applicable to a wide variety of big data analytics jobs. Finally, we demonstrate the effectiveness of the DOT model through several case studies.

Many emerging information processing applications require applying various fork and join type operations such as correlation, aggregation, and encoding/decoding to data streams in real-time. Each operation will require one or more simultaneous input data streams and produce one or more output streams, where the processing may shrink or expand the data rates upon completion. Multiple tasks can be co-located on the same server and compete for limited resources. Effective in-network processing and resource management in a distributed heterogeneous environment is critical to achieving better scalability and provision of quality of service. In this paper, we study the distributed resource allocation problem for a synchronous fork and join processing network, with the goal of achieving the maximum total utility of output streams. Using primal and dual based optimization techniques, we propose several decentralized iterative algorithms to solve the problem, and design protocols that implement these algorithms. These algorithms have different strengths in practical implementation and can be tailored to take full advantage of the computing capabilities of individual servers. We show that our algorithms guarantee optimality and demonstrate through simulation that they can adapt quickly to dynamically changing environments.

This paper addresses the problem of distributed resource allocation in general fork and join processing networks. The problem is motivated by the complicated processing requirements arising from distributed data intensive computing. In such applications, the underlying data processing software consists of a rich set of semantics that include synchronous and asynchronous data fork and data join. The different types of semantics and processing requirements introduce complex interdependence between various data flows within the network.

Multipath streaming protocols have recently attracted much attention because they provide an effective means to provide high-quality streaming over the Internet. However, many existing schemes require a long start-up delay and thus are not suitable for interactive applications such as video conferencing and tele-presence. In this paper, we focus on real-time live streaming applications with stringent end-to-end latency requirement, say several hundreds of milliseconds. To address these challenges, we take a joint multipath and FEC approach that intelligently splits the FEC-encoded stream among multiple available paths. We develop an analytical model and use asymptotic analysis to derive closed-form, optimal load splitting solutions, which are surprisingly simple yet insightful. To our best knowledge, this is the first work that provides such closed-form optimal solutions. Based on the analytical insights, we have designed and implemented a novel encoded multipath streaming (EMS) scheme for real-time live streaming. EMS strives to continuously satisfy the application's QoS requirements by dynamically adjusting the load splitting decisions and the FEC settings. Our simulation results have shown that EMS can not only outperform the existing multipath streaming schemes, but also adapt to the dynamic loss and delay characteristics of the network with minimal overhead.

Recent advances in computer technology and wireless communications have enabled the emergence of stream-based sensor networks. In such sensor networks, real-time data are generated by a large number of distributed sources. Queries are made that may require sophisticated processing and filtering of the data. A query is represented by a query graph. In order to reduce the data transmission and to better utilize resources, it is desirable to place operators of the query graph inside the network, and thus to perform in-network processing. Moreover, given that various queries occur with different frequencies and that only a subset of sensor data may actually be queried, caching intermediate data objects inside the network can help improve query efficiency. In this paper, we consider the problem of placing both operators and intermediate data objects inside the network for a set of queries so as to minimize the total cost of storage, computation, and data transmission. We propose distributed algorithms that achieve optimal solutions for tree-structured query graph topologies and general network topologies. The algorithms converge in Lmax(.HQ+ 1) iterations, where Lmaxis the order of the diameter of the sensor network, and Hq represents the depth of the query graph, defined as the maximum number of operations needed for a raw data to become a final data. For a regular grid network and complete binary tree query graph, the complexity is 0(radic(N)log2M), where N is the number of nodes in the sensor network and M is the number of data objects in a query graph. The most attractive features of these algorithms are that they require only information exchanges between neighbors, can be executed asynchronously, are adaptive to cost change and topology change, and are resilient to node or link failures.

We present a failure recovery framework for System S, a large-scale stream data analysis environment. It is intended to support multiple sites, which have their own local administration and goals. However, it is beneficial for these sites to cooperate with each other, especially in the presence of various failures. Our ultimate goal is to support automatic, timely failure recovery through cooperation among sites. We identify the unique challenges in the context of System S and present our initial design work. In particular, we consider a backup selection problem, specifying where to recover failed jobs, which we formulate as an optimization problem. We present an approximation algorithm together with empirical results obtained through simulations. Our numerical evaluations show that the proposed approximation algorithm is very efficient and effective compared to the optimal solutions. It exhibits a promising empirical performance ratio that is close to the theoretical limit of polynomial approximations of such a problem

A fundamental problem in a large scale decentralized stream processing system is how to best utilize the available resources and admission control the bursty and high volume input streams so as to optimize overall system performance. We consider a distributed stream processing system consisting of a network of servers with heterogeneous capabilities that collectively provide processing services to multiple data streams. Our goal is to design a joint source admission control, data routing, and resource allocation mechanism that maximizes the overall system utility. Here resources include both link bandwidths and processor resources. The problem is formulated as a utility optimization problem. We describe an extended graph representation that unifies both types of resources seamlessly and present a novel scheme that transforms the admission control problem to a routing problem by introducing dummy nodes at sources. We then present a distributed gradient-based algorithm that iteratively updates the local resource allocation based on link data rates. We show that our algorithm guarantees optimality and demonstrate its performance through simulation.

We study a joint scheduling and coding problem for collecting multi-snapshots spatial data in a resource constrained sensor network. Motivated by a distributed coding scheme for single snapshot data collection [7], we generalize the scenario to include multi-snapshots and general coding schemes. Associating a utility function with the recovered data, we aim to maximize the expected utility gain through joint coding and scheduling.

This paper investigates how the through put of a general fork-join queueing network with blocking behaves as the number of nodes increases to infinity while the processing speed and buffer space of each node stay unchanged. The problem is motivated by applications arising from distributed systems and computer networks. One example is large-scale distributed stream processing systems where TCP is used as the transport protocol for data transfer in between processing components. Other examples include reliable multicast in overlay networks, and reliable data transfer in ad hoc networks. Using an analytical approach, the paper establishes bounds on the asymptotic throughput of such a network. For a subclass of networks which are balanced, we obtain sufficient conditions under which the network stays scalable in the sense that the throughput is lower bounded by a positive constant as the network size increases. Necessary conditions of throughput scalability are derived for general networks. The special class of series-parallel networks is then studied in greater detail, where the asymptotic behavior of the throughput is characterized.

We study the problem of the reconstruction of a Gaussian field defined in [0,1] using N sensors deployed at regular intervals. The goal is to quantify the total data rate required for the reconstruction of the field with a given mean square distortion. We consider a class of two-stage mechanisms which (a) send information to allow the reconstruction of the sensor's samples within sufficient accuracy, and then (b) use these reconstructions to estimate the entire field. To implement the first stage, the heavy correlation between the sensor samples suggests the use of distributed coding schemes to reduce the total rate. Our main contribution is to demonstrate the existence of a distributed block coding scheme that achieves, for a given fidelity criterion for the sensor's measurements, a total information rate that is within a constant, independent of N, of the minimum information rate required by an encoder that has access to all the sensor measurements simultaneously. The constant in general depends on the autocorrelation function of the field and the desired distortion criterion for the sensor samples.

We consider the steady state distribution of the end-to-end delay of a tagged flow in queueing networks where the queues have self-similar cross traffic. We assume that such cross traffic at each queue, say queue I, is modeled by fractional Brownian motion (FBM) with Hurst parameter H/sub i/ /spl isin/ (1/2,1), and is independent of other queues. The arrival process of the tagged flow is renewal. Two types of queueing networks are considered. We show that the end-to-end delay of the tagged flow in a tandem queueing network, and more generally in a tree network, is completely dominated by one of the queues. The dominant queue is the one with the maximal Hurst parameter. If several queues have the same maximal Hurst parameter, then we have to compare the ratio (1-/spl rho/)/sup H///spl sigma/ to determine the dominant queue, where /spl rho/ is the load of the queue and /spl sigma/ is the coefficient of variation of the cross traffic at the queue. In the case that the tagged flow is controlled through a window based congestion control mechanism, the end-to-end delay is still asymptotically Weibullian with the same shape parameter. We provide upper and lower bounds on the constant that determines the scale parameter of the corresponding Weibull distribution.

No abstract available.

The overwhelming success of the Web as a mechanism for facilitating information retrieval and for conducting business transactions has ledto an increase in the deployment of complex enterprise applications. These applications typically run on Web Application Servers, which assume the burden of managing many tasks, such as concurrency, memory management, database access, etc., required by these applications. The performance of an Application Server depends heavily on appropriate configuration. Configuration is a difficult and error-prone task dueto the large number of configuration parameters and complex interactions between them. We formulate the problem of finding an optimal configuration for a given application as a black-box optimization problem. We propose a smart hill-climbing algorithm using ideas of importance sampling and Latin Hypercube Sampling (LHS). The algorithm is efficient in both searching and random sampling. It consists of estimating a local function, and then, hill-climbing in the steepest descent direction. The algorithm also learns from past searches and restarts in a smart and selective fashion using the idea of importance sampling. We have carried out extensive experiments with an on-line brokerage application running in a WebSphere environment. Empirical results demonstrate that our algorithm is more efficient than and superior to traditional heuristic methods.

Design of e-commerce services that are competitive in a quickly responding market requires the analyses of prices and price structures. We develop a general model of an e-commerce market that allows us to analyze optimal price structures, both flat and usage-based. Based on the price structure of a major web hosting provider, we consider single-tier and two-tier (burst-rate) pricing, and our result suggests that the more complex two-tier structure may not be worth the marketing effort, as the firm's equilibrium profits will not increase through the use of this structure. An essential feature of our approach is that we model explicitly the spread of price-QoS tradeoffs across the end-user population.

We analyze the asymptotic tail distribution of stationary waiting times and stationary virtual waiting times in a single-server queue with long-range dependent arrival process and subexponential service times. We investigate the joint impact of the long range dependency of the arrival process and of the tail distribution of the service times. We consider two traffic models that have been widely used to characterize the long-range dependence structure, namely, the M/G/8 input model and the Fractional Gaussian Noise (FGN) model. We focus on the response times of the customers in a First-Come First-Serve (FCFS) queueing system, although the results carry through to the backlog distribution of the system with any arbitrary queueing discipline. When the arrival process is driven by an M/G/8 input model we show that if the residual service time tail distribution Fe is lighter than the residual session duration Ge, then the stationary waiting time is dominated by the long-range dependence structure, which is determined by the residual session duration Ge. If the residual service time distribution Fe is heavier than the residual session duration Ge, then the tail distribution of the stationary waiting time is dominated by that of the residual service time. When the arrival process is modeled by an FGN, we show that the waiting time tail distribution is asymptotically equal to the tail distribution of the residual service time if the latter is asymptotically heavier than Weibull distribution with shape parameter 2-2H, where H is the Hurst parameter of the FGN. If, however, this residual service time is asymptotically lighter than Weibull distribution with shape parameter 2-2H, then the waiting time tail distribution is dominated by the dependence structure of the arrival process so that it is asymptotically equal to Weibull distribution with shape parameter 2-2H.

With the growing popularity of Web applications, there is a considerable increase in the importance of managing Web sites to deliver high levels of performance and scalability to accommodate future growth and evolution. One of the key issues in this regard concerns a better understanding of the traffic patterns at multiple levels, such as the levels of requests, pages and sessions. This paper presents a detailed analysis of measurement data from various sources pertaining to a specific multi-tiered, geographically distributed architecture that has been used to host the Web sites for a number of recent, popular sporting events. Our analysis of the request-level and page-level patterns demonstrate differences among the Web sites depending upon the type of event and the breadth of interests of the user community. Some of these patterns are consistent with commercial Web sites, while others are significantly different These results further illustrate geographical differences in the request-level and page-level patterns. Our analysis also investigates in detail session-level characteristics. This includes an analysis of the session durations, the think time distributions, the dependence structure of the session arrival process, and the page views comprising each session.

Packet delay traces are important measurements for analyzing end-to-end performance and for designing traffic control algorithms in computer networks. Due to the fact that the clocks at the end systems are usually not synchronized and running at different speeds, these measurements can be quite inaccurate. We propose several algorithms to estimate and remove the relative clock skews from delay measurements based on the computation of convex hulls. Compared with existing techniques, such as linear regression and linear programming, the convex-hull approach provides better insight and allows us to handle more error metrics. We obtain algorithms which are linear in the number of measurement points for the case with no clock resets. For the more challenging case with clock resets, i.e., the clocks are reset to some reference times during the measurement period, we develop linear algorithms to identity the clock resets, and derive the best clock skew lines. We extend this analysis to environments in which at least one of the clocks is controlled by NTP (network time protocol). These algorithms can greatly improve the accuracy of the measurements, and can be used both online and offline. They can also be extended for active clock synchronization, to replace or further improve NTP. Numerical experiments are presented to demonstrate the robustness of the algorithms.