A downlink wireless system is considered where a single base station serves two users simultaneously based on the information available at the PRY and NUC layers. Two new quality of service (QoS) oriented scheduling a...
详细信息
ISBN:
(纸本)9781424404681
A downlink wireless system is considered where a single base station serves two users simultaneously based on the information available at the PRY and NUC layers. Two new quality of service (QoS) oriented scheduling algorithms are proposed that consider both channel state and direction of arrival information. available at the PHY layer and queue length information available at the NUC layer to schedule users. The performance of the proposed algorithms is compared with existing scheduling algorithms, that consider either the channel state information, delay information or the combination of the two, in terms of SINR and exceedance probability of delay and queue length. The results obtained indicate that the proposed algorithms perform better than existing algorithms.
This paper evaluates how distinct real-time task scheduling algorithms impact power consumption and timing performance of embedded systems. A design space exploration methodology is proposed in order to adjust the sys...
详细信息
ISBN:
(纸本)1581139470
This paper evaluates how distinct real-time task scheduling algorithms impact power consumption and timing performance of embedded systems. A design space exploration methodology is proposed in order to adjust the system's power consumption by tuning the CPU frequency according to the scheduling algorithm and to the temporal requirements of the embedded application. The goal is to find an optimized configuration, selecting the right combination of a scheduling policy with a CPU frequency, so as to consume less power without missing any deadline in the application. Experiments based on a synthetic workload that simulates realistic applications demonstrate that considerable power savings can be obtained. Moreover, the paper defines guidelines to be used by system designers in order to find a configuration that best matches the design constraints and requirements.
The possibility of providing mobile devices with fast and affordable Cloud computing (CC) services is a major motivation for Cloudlet technology. However, for this happen, a suitable scheduling algorithm that minimize...
详细信息
ISBN:
(纸本)9781728132891
The possibility of providing mobile devices with fast and affordable Cloud computing (CC) services is a major motivation for Cloudlet technology. However, for this happen, a suitable scheduling algorithm that minimizes the consumer's (i.e. Mobile devices) waiting time under various Cloudlet scenarios needs to be determined. Hence, determining the suitability of a scheduling algorithm with respect to consumer's waiting time is the main objective of this study. To this end, we first present a brief review of existing scheduling algorithms as a road map towards evaluating the performance of each algorithm. Next, we present the performance evaluation of three popular scheduling algorithms under various Cloudlet scenarios. Specifically, an EdgeCloudSim simulator is used to evaluate the performance of MM1, Priority (PR) and Round Robin (RR) with respect to consumer's waiting time. Results gotten from the simulation show a noticeable difference in the performance of scheduling algorithms for different mobile applications as the number of mobile devices fluctuates.
The input-queued switch architecture is widely used in Internet routers due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is the scheduling algorithm that decide...
详细信息
ISBN:
(纸本)9781424410460
The input-queued switch architecture is widely used in Internet routers due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is the scheduling algorithm that decides which packets to transfer from ingress ports to egress ports in a given timeslot. It is desirable that such algorithms be iterative (so as to be pipelineable), distributed (allowing flexibility in hardware implementation) and are able to deliver high performance (in terms of throughput and delay). In practice, implementable algorithms have so far had limited success in combining all of the above properties. For example, the popular iSLIP [1] algorithm is known to perform suboptimally, but it is commercially deployed mainly because it is iterative and distributed. The main contribution of this paper is the design and systematic analysis of two algorithms which, to the best of our knowledge, are the first high-performance iterative and distributed scheduling algorithms with possibility of efficient implementation. We first present an iterative, distributed and low-delay maximal throughput algorithm based on the celebrated "Auction Algorithm" [2], [3]. This algorithm can be seen as a natural extension of iSLIP when queue-size information is allowed to be exchanged. The standard auction algorithm can take an unbounded number of iterations to converge in the worst case. However we show that under admissible Bernoulli i.i.d. traffic, our algorithm takes O(n(2)) iterations, where n is the number of ingress/egress ports in the switch. Moreover for a switch with finite buffer-size, the algorithm allows for a graceful trade-off between running time and performance, which we verify by representative simulation results. Next, we propose and analyze a throughput-optimal, iterative and distributed scheduling algorithm influenced by Max-Product Belief Propagation [4], [5]. Recently the problem of efficient transmission over multi-hop wireless networks has been formu
This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the proce...
详细信息
ISBN:
(纸本)9781538625422
This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the processing rate limit of jobs and charging station capacity constraint. The problem lies in the category of time-coupled online scheduling problems without availability of future information. This paper proposes two online algorithms, both of which are shown to be (2-1/U)-competitive, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. The first proposed algorithm is deterministic, whereas the second is randomized and enjoys a lower computational complexity. When U grows large, the performance of both algorithms approaches that of the stateof- the-art for the case where there is processing rate limits on the jobs. Nonetheless in realistic cases, where U is typically small, the proposed algorithms enjoy a much lower competitive ratio. To carry out the competitive analysis of our algorithms, we present a proof technique, which is novel to the best of our knowledge. This technique could also be used to simplify the competitive analysis of some existing algorithms, and thus could be of independent interest.
LTE is a promising generation of mobile communication, characterized by high data rate, lower latency in control and user plane. In the study simulation model was developed for LTE system throughput estimation for dif...
详细信息
ISBN:
(纸本)9781467391115
LTE is a promising generation of mobile communication, characterized by high data rate, lower latency in control and user plane. In the study simulation model was developed for LTE system throughput estimation for different scheduling algorithms. Conclusion of the algorithms advantages and weaknesses were made.
This paper presents the evaluation results of a simulation-based study on the fairness of packet scheduling algorithms to support QoS in IP networks. The simulation study aimed at validating the performance of our pro...
详细信息
ISBN:
(纸本)0889863911
This paper presents the evaluation results of a simulation-based study on the fairness of packet scheduling algorithms to support QoS in IP networks. The simulation study aimed at validating the performance of our proposed scheme for QoS provisioning for real-time traffic in the context of Differentiated Services. We assume that traffic classification based on the application QoS requirements is an indispensable feature for providing QoS guarantees to a wide variety of Internet multimedia applications such as voice over IP (VoIP) and video conferencing due to the scalability issues. We evaluate the performance of our proposed scheme using extensive network simulation in comparison to other approaches. The results from the simulation studies indicate that the packet scheduling mechanism we propose ensures both the required bandwidth fairness and end-to-end network delay bounds for QoS-sensitive applications according to the specified weight ratios under various traffic and network conditions.
This paper presents an algorithm for scheduling imprecise tasks to minimize maximum error and analyzes its performance through intensive simulation. The imprecise computation is used to manage transient overload of co...
详细信息
ISBN:
(纸本)081869209X
This paper presents an algorithm for scheduling imprecise tasks to minimize maximum error and analyzes its performance through intensive simulation. The imprecise computation is used to manage transient overload of computation. Each task for imprecise systems consists of a mandatory part and an optional part that can be skipped when systems are overloaded. The imprecise computation trades accuracy for meeting the deadline of tasks by skipping their optional parts. To increase accuracy for imprecise computation, we present a simple on-line scheduling algorithm that minimizes the maximum error: This algorithm executes mandatory parts of tasks first, then the optional parts in order to minimize maximum error The proposed algorithm also increases schedulability by executing mandatory parts first. The proposed algorithm is simple and does not require any additional data structures such as the reservation list for maintaining mandatory parts.
Cloud computing enables users to access computing resources over internet. Organizations that manage and provide these resources are called as cloud service providers. There are several such providers in the market of...
详细信息
ISBN:
(纸本)9781450347563
Cloud computing enables users to access computing resources over internet. Organizations that manage and provide these resources are called as cloud service providers. There are several such providers in the market offering large range of services to their users and charge them only for what they have consumed. Workflow is of a set of interdependent tasks that need to be performed in a coordinated way to complete a job. Any business or scientific application can be modelled as a workflow. An effective scheduling algorithm will optimize the resource utilization and in turn the amount spent for executing the workflow. Due to the numerous advantages in cloud, workflow scheduling in cloud seems to be an eminent way to minimize the execution time and cost. There are plenty of existing algorithms and many new algorithms are in the row for workflow scheduling in cloud. A complete understanding of these algorithms will help future researchers to propose novel ideas. Hence this paper provides an analysis of some dominant workflow scheduling algorithms and their performance in standard workflow data sets. The analysis is carried out in WorkflowSim environment with the identical set of Virtual Machines (VM) having similar configuration.
We consider networks with aggregated links, that is networks in which physical link segments between two interconnected devices are grouped into a single logical link. Network devices supporting such aggregated links ...
详细信息
ISBN:
(纸本)9783540939795
We consider networks with aggregated links, that is networks in which physical link segments between two interconnected devices are grouped into a single logical link. Network devices supporting such aggregated links must implement a distribution algorithm responsible for choosing the transmission link for any given packet. Traditionally, in order to maintain packet ordering within conversations, all distribution algorithms transmitted packets from a given conversation on a single link. This approach is attractive for its simplicity, but in some conditions it tends to under-utilize the capacity of the link. On the other hand, due to variations in packet lengths, sending packets from the same conversation simultaneously along different physical links requires careful scheduling to ensure that the packets arrive in the correct order. Recently, Jawor et al. [6) formulated this packet scheduling problem as an online optimization problem and proposed an algorithm called Block. The focus of the work in [6] was purely theoretical - to achieve an optimal competitive ratio. In this paper we study this problem in an experimental setting. To this end, we develop a refined version of Algorithm Block, and we show, through experimental analysis, that it indeed significantly reduces the maximum amount of time packets spent in buffers before transmission, compared to the standard methods based on hashing.
暂无评论