Sticky-ERfair: a task-processor affinity aware proportional fair scheduler

A drawback of current proportional fair schedulers is that they ignore task-to-processor mutual affinities, thereby causing frequent inter-processor task migrations and cache misses. This paper presents the Sticky-ERfair Scheduler, an Early-Release Fair (ERfair) scheduler that attempts to minimize task migrations and preemptions. Given any processor V _i , Sticky-ERfair allocates to it the most recently executed ready task that previously executed on V _i (thus restricting migrations and preemptions) in such a way that this allocation does not cause any ERfairness violations in the system at any time during the schedule length. Experimental results reveal that Sticky-ERfair can achieve upto over 40 times reduction both in the number of migrations and preemptions suffered with respect to Basic-ERfair (for a set of 25 to 100 tasks running on 2 to 10 processors) while simultaneously guaranteeing ERfairness at each time slot.     

Energy-credit scheduler: An energy-aware virtual machine scheduler for cloud systems

Virtualization facilitates the provision of flexible resources and improves energy efficiency through the consolidation of virtualized servers into a smaller number of physical servers. As an increasingly essential component of the emerging cloud computing model, virtualized environments bill their users based on processor time or the number of virtual machine instances. However, accounting based only on the depreciation of server hardware is not sufficient because the cooling and energy costs for data centers will exceed the purchase costs for hardware. This paper suggests a model for estimating the energy consumption of each virtual machine without dedicated measurement hardware. Our model estimates the energy consumption of a virtual machine based on in-processor events generated by the virtual machine. Based on this estimation model, we also propose a virtual machine scheduling algorithm that can provide computing resources according to the energy budget of each virtual machine. The suggested schemes are implemented in the Xen virtualization system, and an evaluation shows that the suggested schemes estimate and provide energy consumption with errors of less than 5% of the total energy consumption.     

Rate-adaptive weighted fair queueing for energy-aware scheduling

In this paper we study energy-aware scheduling that trades energy consumption against a traditional performance measure of delay. We use the power-rate function f(x)=c+x^α$f(x)=c+x^{\alpha }$ for x>0$x>0$ and f(0)=0$f(0)=0$ to model the power consumption, where c>0$c>0$ represents the base power. We give a definition of a rate-adaptive version of the Weighted Fair Queueing scheduling algorithm, and prove its energy consumption is within a bounded factor of the best possible when the algorithm guarantees the classic end-to-end delay for every connection.     

WF2Q-M: Worst-case fair weighted fair queueing with maximum rate control

While existing weighted fair scheduling schemes guarantee minimum bandwidths/resources for the classes/processes of a shared channel, the maximum rate control, which is critical to service providers, carriers, and network managers for resource management and business strategies in many applications, is generally enforced by employing traffic policing mechanisms. These approaches use either a concatenation of the rate controller and scheduler, or a policer in front of the scheduler. The concatenation method uses two sets of queues and a management apparatus that incurs overhead. The latter method may allow bursty traffic to pass through the controller, which violates the maximum rate constraint, or results in packet loss. In this paper, we present a new weighted fair scheduling scheme, WF²Q-M, which can simultaneously support maximum rate control and minimum service rate guarantees. WF²Q-M uses the virtual clock adjustment method to enforce maximum rate control and distribute the excess bandwidths of saturated sessions to other sessions without recalculating the virtual starting and finishing times of sessions. In terms of performance, we prove that WF²Q-M is theoretically bounded by a corresponding fluid reference model. A procedural scheduling implementation of WF²Q-M is proposed, and a proof of correctness is given. Finally, we present the results of extensive experiments to show that the performance of WF²Q-M is just as claimed.     

A Corrigendum to: “Sticky-ERfair: a task-processor affinity aware proportional fair scheduler”

This paper provides a corrigendum to resolve a couple of minor issues in the algorithm presented in Sarkar et al. (Real-Time Syst., 2011). The first issue relates to the postponement of execution of a task when its own ‘deadline of postponement’ have not been crossed. The second issue concerns the updation of certain scheduler data structures.     

Multiprogramming with virtual memory—a queueing model

A multiprogramming computing system which utilizes a virtual memory operating system, with paging-on-demand, is defined in queueing-theoretic terms. The validity and possible uses of such a model are discussed. Several quantities and measures of effectiveness, such as paging time, total system response time, and memory requirements are computed. The discussion and analysis place emphasis on exact, computable results.     

Taking the Fourth Party further? Considering a shared virtual workspace for arbitration

Presently, there is a growing interest in creating global virtual teams for online arbitration, in which collaboration proceeds across time zones as well as across geographical borders. The aim in this article is to study virtual shared workspaces. While trying to operate a constant interplay with collaboration technologies, we will describe new practices totally unheard of in dispute resolution. Virtual shared workspaces are graphical interfaces that allow several actors to interact simultaneously with the same virtual object. They can be used in online arbitration not to mediate, but rather to augment discussions by facilitating pleadings in cases involving complex factual situations, by providing very sophisticated ways to make allegations, to present facts, and to explain evidence. In this article, we analyse the collaboration, implementation and legal issues that arise from the use of this technology during arbitral proceedings.     

Task mapper and application-aware virtual machine scheduler oriented for parallel computing

We design a task mapper TPCM for assigning tasks to virtual machines, and an application-aware virtual machine scheduler TPCS oriented for parallel computing to achieve a high performance in virtual computing systems. To solve the problem of mapping tasks to virtual machines, a virtual machine mapping algorithm (VMMA) in TPCM is presented to achieve load balance in a cluster. Based on such mapping results, TPCS is constructed including three components: a middleware supporting an application-driven scheduling, a device driver in the guest OS kernel, and a virtual machine scheduling algorithm. These components are implemented in the user space, guest OS, and the CPU virtualization subsystem of the Xen hypervisor, respectively. In TPCS, the progress statuses of tasks are transmitted to the underlying kernel from the user space, thus enabling virtual machine scheduling policy to schedule based on the progress of tasks. This policy aims to exchange completion time of tasks for resource utilization. Experimental results show that TPCM can mine the parallelism among tasks to implement the mapping from tasks to virtual machines based on the relations among subtasks. The TPCS scheduler can complete the tasks in a shorter time than can Credit and other schedulers, because it uses task progress to ensure that the tasks in virtual machines complete simultaneously, thereby reducing the time spent in pending, synchronization, communication, and switching. Therefore, parallel tasks can collaborate with each other to achieve higher resource utilization and lower overheads. We conclude that the TPCS scheduler can overcome the shortcomings of present algorithms in perceiving the progress of tasks, making it better than schedulers currently used in parallel computing.     

Virtual control - a virtual cluster tool for testing and verifying a cluster tool controller and a scheduler

In this paper, a systematic practice for verifying a scheduler and a CTC using a virtual cluster tool (VCT) model are presented, which emulates the operational behavior of a real cluster tool with high fidelity. The model architecture and modeling strategies of the VCT were also explained. This paper also presented the use of a formal model-based automatic error-detection technique and discussed experiences of verifying a real cluster tool controller using the VCT.     

Psu: a novel low-latency constant-degree overlay network

Many structured peer-to-peer (P2P) systems supported by distributed hash table (DHT) schemas have been proposed recently to improve the scalability of distributed virtual application systems. By organizing the peers based on interconnection topologies, existing proposed schemas are purely based on the logical relationship without knowledge of the physical networks. In this paper, we propose a new structured DHT schema, which receives routing information not just from virtual neighbors in P2P overlay network, but also from nearby physical neighbors. The average degree of our model is 5, the diameter is logarithmic. The simulation shows that our model achieves shorter query path length, higher clustering, and better robustness than other overlay networks which have the same level of degree and diameter.     

Partition equalizer: a scheduler for algorithm-agile-encryptor ATM networks

The ability of ATM Networks to support a wide range of applications has made it increasingly popular. As ATM Networks are more widely used, security services become a compelling requirement. Encryption in ATM Networks allows users to select an appropriate algorithm to implement security services for a given application. Algorithm-Agile-Encryptors (AAEs) implement multiple encryption algorithms in a single device. AAEs also reduce operational costs when they are shared among several users. However, algorithm agility may re-order cells belonging to different Virtual Circuits (VCs) and thereby affect the negotiated QoS. The two ways of scheduling the encrypted cells from the AAE are ‘FIFO queuing’ and ‘Delay equalization’. This paper addresses the effect of the existing scheduling schemes on the QoS of ATM Networks. Further, a scheduling scheme called Partition Equalizer (PE) has been proposed and analyzed. It has been shown that the PE reduces both the Cell Transfer Delay and the Cell Delay Variation compared to the other existing schemes such as ‘FIFO queuing’ and ‘Delay equalization’.     

Psu: a novel low-latency constant-degree overlay network

Many structured peer-to-peer (P2P) systems supported by distributed hash table (DHT) schemas have been proposed recently to improve the scalability of distributed virtual application systems. By organizing the peers based on interconnection topologies, existing proposed schemas are purely based on the logical relationship without knowledge of the physical networks. In this paper, we propose a new structured DHT schema, which receives routing information not just from virtual neighbors in P2P overlay network, but also from nearby physical neighbors. The average degree of our model is 5, the diameter is logarithmic. The simulation shows that our model achieves shorter query path length, higher clustering, and better robustness than other overlay networks which have the same level of degree and diameter.     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

A land-use and capital-investment allocation optimization model to develop a fair community opportunity framework for Columbus,Ohio

Land-use planning and capital investments have been increasingly recognized as important planning tools to mitigate social inequality. The idea is based on the concept of “neighborhood effects” that the built environment of a city has influence on the socioeconomic outcome of a residential community, which is defined as community opportunity in this study. The explicit local relationships between community opportunity and the physical setting of land uses, transportation infrastructure, and public facilities can be captured by a geographically weighted regression (GWR) model. The GWR results indicate the most effective locations for further developments and investments. This research is one of the few to incorporate such a GWR model into an optimization modeling framework in the contexts of Columbus, Ohio, to (1) maximize the total community opportunities over the region, and (2) minimize the total difference in community opportunities among the 284 census tracts, by an optimal allocation of future land uses and capital investments. Solving the optimization model for the two policy scenarios provides decision makers a new insight into the problem of social inequality. Comparison between the two allocation results has implications for the efforts to improve community opportunity without exacerbating social inequality, by allocating future activities to positive but less effective locations.     

A multithreaded scheduler for a high-speed spacecraft simulator

The Cassini spacecraft is on its journey to Saturn to perform a close-up study of the Saturnian system; its rings, moons, magneto-sphere, and the planet itself. Sequences of commands will be sent to the spacecraft by ground personnel to control every aspect of the mission. To validate and verify these command sequences, a bit-level, High-Speed Simulator (HSS) has been developed. To maximize performance, the HSS is implemented with multiple threads and runs on a multiprocessor system. A key component of the HSS is the scheduler, which controls the execution of the simulator. The general framework of the scheduler can be adapted to solve a wide variety of scheduling problems. The architecture of the scheduler is presented first, followed by a discussion of issues related to performance and multiple threads. Second, the avoidance of deadlocks and race conditions is discussed, and an informal proof for the absence of both in the scheduler is described. Finally, a study of various scheduling policies is provided. © 1998 John Wiley & Sons, Ltd.     

A scheduler ASIC for a programmable packet switch

While the Internet is successful in supporting traditional data-only traffic, an integrated services Internet is inevitable with the emergence of new applications such as voice, video, multimedia, and interactive video conferencing. Such an integrated services network should support a wide range of applications with diverse quality of service requirements and traffic characteristics. Provision for quality of service in packet networks in general, and in the Internet in particular, is the focus of most of the recent developments in switching and routing system design. We designed a generic, single-queue scheduler engine for use in a programmable packet switch/router to handle IP packets, ATM cells, or a combination of both. Comprising 275,000 gates, the 0.35-micron ASIC is incorporated into a prototype programmable packet switch     

KOALA: a co‐allocating grid scheduler

In multicluster systems, and more generally in grids, jobs may require co‐allocation, that is, the simultaneous or coordinated access of single applications to resources of possibly multiple types in multiple locations managed by different resource managers. Co‐allocation presents new challenges to resource management in grids, such as locating sufficient resources in geographically distributed sites, allocating and managing resources in multiple, possibly heterogeneous sites for single applications, and coordinating the execution of single jobs at multiple sites. Moreover, as single jobs now may have to rely on multiple resource managers, co‐allocation introduces reliability problems. In this paper, we present the design and implementation of a co‐allocating grid scheduler named KOALA that meets these co‐allocation challenges. In addition, we report on the results of an analysis of the performance in our multicluster testbed of the co‐allocation policies built into KOALA . We also include the results of a performance and reliability test of KOALA while our testbed was unstable. Copyright © 2007 John Wiley & Sons, Ltd.