Training jobs of deep neural networks (DNNs) can be accelerated through distributed variants of stochastic gradient descent (SGD), where multiple nodes process training examples and exchange updates. The total throughput of the nodes depends not only on their computing power, but also on their networking speeds and coordination mechanism (synchronous or asynchronous, centralized or decentralized), since communication bottlenecks and stragglers can result in sublinear scaling when additional nodes are provisioned. In this paper, we propose two classes of performance models to predict throughput of distributed SGD:fine-grained models, representing many elementary computation/communication operations and their dependencies; andcoarse-grained models, where SGD steps at each node are represented as a sequence of high-level phases without parallelism between computation and communication. Using a PyTorch implementation, real-world DNN models and different cloud environments, our experimental evaluation illustrates that, while fine-grained models are more accurate and can be easily adapted to new variants of distributed SGD, coarse-grained models can provide similarly accurate predictions when augmented with ad hoc heuristics, and their parameters can be estimated with profiling information that is easier to collect.

The recent emergence of the small cloud (SC), both in concept and in practice, has been driven mainly by issues related to service cost and complexity of commercial cloud providers (e.g., Amazon) employing massive data centers. However, the resource inelasticity problem faced by the SCs due to their relatively scarce resources might lead to a potential degradation of customer QoS and loss of revenue. A proposed solution to this problem recommends the federated sharing of resources between competing SCs to alleviate the resource inelasticity issues that might arise. Based on this idea, a recent effort proposed SC-Share, a performance-driven static market model for competitive small cloud environments that results in an efficient market equilibrium jointly optimizing customer QoS satisfaction and SC revenue generation. However, an important question with a non-obvious answer still remains to be answered, without which SC sharing markets may not be guaranteed to sustain in the long-run - is it still possible to achieve a stable market efficient state when the supply of SC resources is dynamic in nature?. In this article, we take a first step to addressing the problem of efficient market design for single SC resource sharing in dynamic environments. We answer our previous question in the affirmative through the use of Arrow and Hurwicz's disequilibrium process in economics, and the gradient play technique in game theory that allows us to iteratively converge upon efficient and stable market equilibria.

The success of Deep Neural Networks (DNNs) has created significant interest in the development of software tools, hardware architectures, and cloud systems to meet the huge computational demand of their training jobs. A common approach to speeding up an individual job is to distribute training data and computation among multiple nodes, periodically exchanging intermediate results. In this paper, we address two important problems for the application of this strategy to large-scale clusters and multiple, heterogeneous jobs. First, we propose and validate a queueing model to estimate the throughput of a training job as a function of the number of nodes assigned to the job; this model targets asynchronous Stochastic Gradient Descent (SGD), a popular strategy for distributed training, and requires only data from quick, two-node profiling in addition to job characteristics (number of requested training epochs, mini-batch size, size of DNN parameters, assigned bandwidth). Throughput estimations are then used to explore several classes of scheduling heuristics to reduce response time in a scenario where heterogeneous jobs are continuously submitted to a large-scale cluster. These scheduling algorithms dynamically select which jobs to run and how many nodes to assign to each job, based on different trade-offs between service time reduction and efficiency (e.g., speedup per additional node). Heuristics are evaluated through extensive simulations of realistic DNN workloads, also investigating the effects of early termination, a common scenario for DNN training jobs.

Small-scale clouds (SCs) often suffer from resource under-provisioning during peak demand, leading to inability to satisfy service level agreements (SLAs) and consequent loss of customers. One approach to address this problem is for a set of autonomous SCs to share resources among themselves in a cost-induced cooperative fashion, thereby increasing their individual capacities (when needed) without having to significantly invest in more resources. In this context, a central problem is how to properly share resources for a price in order to achieve profitable service, while maintaining customer SLAs. To address this problem, we propose the SC-Share framework that utilizes two interacting models: (i) a stochastic performance model that estimates the achieved performance characteristics under given SLA requirements, and (ii) a market-based game-theoretic model that (as shown empirically) converges to efficient resource sharing decisions at market equilibrium. Our results include extensive evaluations that illustrate the utility of the proposed framework.

Consistent (pause-free) quality of service is required in peer-to-peer (P2P) video streaming systems. In this paper, we aim to eliminate the problem of playback pauses in such systems via the use of positive incentives for peers to contribute high upload rates. We model our problem as a market, where the market stakeholders consist of multiple content providers, advertisement providers, and network peers; the positive incentives for peers in the market are reduced advertisement (ad) viewing durations. From a system design perspective, one of our primary goals is to compute the market equilibria that include appropriate ad viewing durations, offering sufficient incentives for network peers to continue contributing. Our simulation-based studies demonstrate that we mitigate the “playback pause” problem for peers by up to 80% as compared to existing approaches, generate sufficient utility for advertisers to be part of the market, and enable content providers to achieve their desired utility by providing sufficient incentives for all peers to stay in the system without violating ad provider agreements.

Inconsistent quality of service is a significant problem in P2P-based video streaming systems. Pauses in playback are common for low capacity peers as they often upload relatively little compared to high capacity peers, and thus suffer from the `lack of reciprocity' problem. In this work, we propose an Ad-driven Streaming P2p ECosysTem (ASPECT) that aims to eliminate the problem of playback pauses by adopting `reduced advertisement viewing duration' as a positive incentive for peers to provide high upload rates. ASPECT rewards high capacity peers by reducing their advertisement viewing duration, when they provide more opportunities for lower capacity peers to download data. We build our research problem on a utility-theoretic market-based model, where the market stakeholders consist of a content provider, an advertisement provider, and network peers. Using concepts from game theory, we determine the system parameters to reach market efficiency, and study the practical implications of equilibria on the satisfaction of stakeholders' interests. From a system design perspective, one of our primary goals is to compute the equilibria advertisement viewing durations, that offer sufficient incentives for network peers to continue contributing. We evaluate ASPECT through an extensive simulation-based study. The results demonstrate that ASPECT mitigates the `playback pause' problem for peers by at least 80% compared to existing approaches, results in appropriate advertisement viewing durations for all peers based on their contributions, and at the same time generates sufficient profit for the advertiser to be part of the market.

Due to the vehicle's movement and inherent characteristics of wireless channel, how to discover and retrieve the required contents has become a challenging issue in a hybrid network including vehicular ad hoc networks (VANETs) and the Internet. In this paper, we propose a social cluster-based P2P framework that estimates similarity and connection condition among peers to provide mobile peers efficient resource discovery and retrieval. The idea of our framework is to consider a mobile peer's preference and its connectivity such as the lifetime or the bandwidth for a wireless link. Specifically, there are two major components in our framework. First, a social cluster-based overlay structure and lifetime-aware flooding scheme enable mobile peers to discover resource through the Internet and VANETs. Second, a connectivity-aware retrieval scheme considers connection lifetime and bandwidth schedules and determines how to retrieve resource from available peers. The simulation results show that, compared with other existing P2P schemes, our social cluster-based P2P framework is able to quickly locate more available peers holding the required contents and achieve a higher retrieval ratio.

In multi-channel wireless mesh networks (WMNs), the routing and channel assignment can interdependently determine network capacity. However, joint routing and channel assignment (JRC) is a challenging problem since it must satisfy theRadioConstraint,theChannelConstraint,andtheCo-channelInterferenceConstraint. Recently, many heuristic or suboptimization algorithms have been proposed to address the JRC problem. The aim of this paper is to preform a comprehensive performance study to fairly compare the different approaches. To achieve this goal, a proper benchmark, a mixed integer linear programming (MILP) model that can optimally configure the routing and channel assignment to get maximum achievable network capacity, is provided in this work as well. The proposed MILP model can help system designers quantitatively evaluate existing heuristic methods and make a better decision by considering the tradeoff between the characteristics of various schemes according to the system requirements.