Search

Jobs in modern computing clusters have highly diverse processing duration and heterogeneous resource requirements. In this paper, we consider the problem of job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the different resource demands of the jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the recently-proposed notion of fractional job flowtime as a surrogate objective for minimization. For the general online job arrival case with multi-dimensional resource requirements, we apply Online Convex Optimization (OCO) techniques to design the corresponding scheduling algorithm with performance guarantees. In the single-dimensional resource setting, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function with the corresponding switching costs. [ABSTRACT FROM AUTHOR]

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially. [ABSTRACT FROM AUTHOR]

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is $(1+\epsilon)$ (1 + ε) (1 + ε) -speed, $\ O(\frac{1}{\epsilon })$ O (1 ε) O (1 ε) -competitive. We also show that our proposed Fair+R and LAPS+R($\beta$ β β ) Algorithms for a multitasking cluster are $(4+\epsilon)$ (4 + ε) (4 + ε) -speed, $\ O(\frac{1}{\epsilon })$ O (1 ε) O (1 ε) -competitive and ($2 + 2\beta + 2\epsilon)$ 2 + 2 β + 2 ε) 2 + 2 β + 2 ε) -speed $O(\frac{1}{\beta \epsilon })$ O (1 β ε) O (1 β ε) -competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes. [ABSTRACT FROM AUTHOR]

Over the past few years, many major wireless providers restricted their unlimited data plans and replaced them with limited-size fixed-price data packages. While this could be perceived as a disadvantage for customers, it helps the cellular wireless providers to reduce the traffic intensity at their base stations and this leads to a better service quality and higher rates for concurrently connected users. Hence, there is a tradeoff between the data volume and the data rates attributed to the users. To avoid the adverse effect of service inaccessibility, the cellular providers should carefully set the size and pricing of their data packages. Toward this end, the providers need a model that, together with proper market information, would allow to set the best prices for volume-based data and estimate the acceptable quantity of subscribers and their average data rate. In this paper, we propose such a model that quantifies the relationship between pricing and various market/system parameters such as data volume size, user budget, data rate, and service blocking probability. In particular, we formulate a set of revenue optimization problems for different spectrum assignment criteria like shared-carrier and dynamic sub-carrier allocation. Finally, several realistic scenarios are investigated in which the optimal network parameters are computed. [ABSTRACT FROM PUBLISHER]

Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an $O(1)$ -competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based \beta$ -fraction Sharing plus Cloning algorithm (SREW+C(\beta$ )) for the online case. We also show that SREW+C(\beta$ ) is (1+ 2\beta + \epsilon) -competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C( $\beta$ ) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$ ) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass. [ABSTRACT FROM PUBLISHER]

A big parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable or congested machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow when extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for parallel processing clusters from an optimization perspective under different loading conditions. For the lightly loaded case, we analyze and propose one cloning scheme, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the overall system utility. We also derive the workload threshold under which SCA should be used for speculative execution. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme to mitigate stragglers. Our simulation results show SCA reduces the total job flowtime, i.e., the job delay/ response time by nearly $6$ percent comparing to the speculative execution strategy of Microsoft Mantri. In addition, we show that the ESE Algorithm outperforms the Mantri baseline scheme by $71$ percent in terms of the job flowtime while consuming the same amount of computation resource. [ABSTRACT FROM AUTHOR]

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/ reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels. [ABSTRACT FROM AUTHOR]

Feedback Retransmission Approximation for Slotted ALOHA (FRASA) is proposed to study the stability region of finite-user slotted ALOHA under the collision channel. With FRASA, the stability region is derived in closed form for any number of users in the system. The result derived from FRASA is shown to be identical to the analytical result of finite-user slotted ALOHA when there are two users. It is shown that the stability region obtained from FRASA is a good approximation to the stability region of finite-user slotted ALOHA. The convex hull bound, which is convex, piecewise linear and outer bounds the stability region of FRASA, is provided. p-convexity, an essential property that the stability region of FRASA should have to ensure the convex hull bound is close to the boundary, is characterized. From these, it is derived that the stability region of FRASA can never be convex when there are more than two users. A separate convex and piecewise linear inner bound on the stability region of FRASA, the supporting hyperplane bound, is also given. [ABSTRACT FROM AUTHOR]

Drive-thru Internet systems are multiple-access wireless networks in which users in moving vehicles can connect to a roadside access point (AP) to obtain Internet connectivity for some period of time as the vehicles pass through the AP's coverage range. In order to evaluate the type of communication services and the quality-of-service that these systems can provide, in this paper, we investigate the data communication performance of a vehicle in Drive-thru Internet systems. In particular, we derive analytical models with tractable solutions to characterize the average and the distribution of the number of bytes downloaded by a vehicle by the end of its sojourn through an AP's coverage range, in the presence of other vehicles contending for the same AP's resources. Our models are able to quantify the impact of road traffic density, vehicle speed, service penetration rate, AP's transmission range and the corresponding bit rate, on the amount of data downloaded by an individual vehicle. In terms of analysis technique, we map the study of our vehicular data downloading process into the transient analysis of a series of Markov reward processes. Our use of Markov reward model is novel in the sense that we only select from the corresponding Markov chain, a subset of relevant sample paths that matches the required behavior of our vehicular flow model. We also validate our proposed analytical models through extensive simulations, driven by empirical vehicular traffic traces. We believe our work offers a unique analytical framework based on which the interplay between vehicular traffic parameters and a vehicle's data communication performance in a Drive-thru Internet system can be studied and optimized in a systematic, quantitative manner. [ABSTRACT FROM AUTHOR]