We propose a class of binary queue length information based max-weight scheduling algorithms for wireless networks. In these algorithms, the scheduler, in addition to channel states, only needs to know when a link'...
详细信息
ISBN:
(纸本)9783903176003
We propose a class of binary queue length information based max-weight scheduling algorithms for wireless networks. In these algorithms, the scheduler, in addition to channel states, only needs to know when a link's queue length crosses a prescribed threshold. We show that these algorithms are throughput optimal. Further, we incorporate time-since-last service (TSLS) information to improve delay and service regularity of the scheduling algorithms while ensuring throughput optimality. We also perform simulations to illustrate throughput, delay and service regularity performance of the proposed algorithms.
Previously proposed wavelength scheduling algorithms in optical burst switching networks process each reservation request individually and in a greedy manner. In this paper we propose a new family of wavelength schedu...
详细信息
ISBN:
(纸本)3540258094
Previously proposed wavelength scheduling algorithms in optical burst switching networks process each reservation request individually and in a greedy manner. In this paper we propose a new family of wavelength scheduling algorithms that process a batch of reservation requests together instead of processing them one by one. When a control burst with a reservation request arrives to a free batch scheduler, the scheduler waits for a small amount of time, called the acceptance delay, before deciding to accept or reject the reservation request. After the acceptance delay has passed, the scheduler processes all the reservation requests that have arrived during the acceptance delay, then it accepts the requests that will maximize the utilization of the wavelength channels. We describe an optimal batch scheduler that serves as an upper bound on the performance of batch scheduling algorithms. Furthermore, we introduce two heuristic batch scheduling algorithms. The performance of the proposed algorithms is evaluated using a discrete-event simulation model. Simulation results suggest that batch schedulers could decrease the blocking probability by 25% compared to the best previously known wavelength scheduling algorithm.
Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakne...
详细信息
ISBN:
(数字)9783540362654
ISBN:
(纸本)3540003037
Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakness with existing methods is that a distinct automaton must be constructed for each combination of a reservation table and initiation interval. In this work, we present a different approach to model conflicts. We construct one automaton for each reservation table which acts as a compact encoding of all the conflict automata for this table, which can be recovered for use in modulo-scheduling. The basic premise of the construction is to move away from the Proebsting-Fraser model of conflict automaton to the Muller model of automaton modelling issue sequences. The latter turns out to be useful and efficient in this situation. Having constructed this automaton, we show how to improve the estimate of resource constrained initiation interval. Such a bound is always better than the average-use estimate. We show that our bound is safe: it is always lower than the true initiation interval. This use of the automaton is orthogonal to its use in modulo-scheduling. Once we generate the required information during pre-processing, we can compute the lower bound for a program without any further reference to the automaton.
In this paper, we address the problem of designing scalable scheduling and routing policies over a time-triggered multi-hop control network, when closing a considerable number of control loops on the same network. The...
详细信息
ISBN:
(纸本)9781424445783
In this paper, we address the problem of designing scalable scheduling and routing policies over a time-triggered multi-hop control network, when closing a considerable number of control loops on the same network. The key idea is to formally define by means of regular languages the set of schedules for each control loop that satisfy a given control specification, and to exploit operators on regular languages to compute the set of schedules for the whole system. In order to test our methodology, we address a mineral floatation control problem derived from the Boliden (a swedish mining company) mine in Garpenberg, and propose a scheduling solution that can be implemented on systems compliant with communication protocols for wireless networks (e.g. the WirelessHART specification).
In this paper, we propose a new scheduling algorithm for IEEE802.16 Broadband wireless Metropolitan Area Networks in TDD mode. Based on some known algorithms such as Modified Deficit Round Robin (MDRR), Proportional F...
详细信息
ISBN:
(纸本)9781479938247
In this paper, we propose a new scheduling algorithm for IEEE802.16 Broadband wireless Metropolitan Area Networks in TDD mode. Based on some known algorithms such as Modified Deficit Round Robin (MDRR), Proportional Fairness (PF) and Adaptive Proportional Fairness (APE), we have studied the scheduling problem and proposed scheduling algorithm, called (Enhanced-APF) for focuses on an efficient mechanism to serve high priority traffic in order to perform and achieve high resource utilization in the Wimax Base Station. We give a detailed simulation study for the proposed scheduling algorithm and its performance has been compared. Based on OPNET modeler Simulation, results show that the proposed algorithm can increase the network throughput, maintain relative fairness, and lower delay of dealing with different requirements from users under congestion conditions.
Static task scheduling in distributed computing systems is a very complex problem and known to be NP-hard. This problem is even harder when the module execution times become probabilistic. In this paper we study the e...
详细信息
ISBN:
(纸本)0818685387
Static task scheduling in distributed computing systems is a very complex problem and known to be NP-hard. This problem is even harder when the module execution times become probabilistic. In this paper we study the effect of probabilistic module execution times on the performance of task-scheduling algorithms. We show that in static task scheduling, for probabilistic module execution times, and in the existence of some factors there is no need to use an expensive task-scheduling algorithm. Given any two static task-scheduling algorithms that use deterministic module execution times in assigning task modules to the distributed system, the performance of these two algorithms will not remain the same when these module execution times become probabilistic rather than deterministic. We also study the effects of some factors on our results.
scheduling algorithms in Wavelength Division Multiplexing (WDM) single hope networks aim at producing an effective schedule in order to improve the networks' performance. Up to now, popular approaches schedule net...
详细信息
ISBN:
(纸本)9781424413690
scheduling algorithms in Wavelength Division Multiplexing (WDM) single hope networks aim at producing an effective schedule in order to improve the networks' performance. Up to now, popular approaches schedule network traffic based on nodes' requests which are considered in a sequential service order. This paper presents a novel packet scheduling scheme for WDM star networks based on clustering techniques. Our Clustering Based scheduling Algorithm (CBSA) organizes the nodes of a network into groups (i.e. clusters) according to the number of their requests per channel and then it defines their transmission priority beginning from the nodes belonging to the cluster with greater demands and ending to the nodes of cluster with fewer requests. The simulation results have shown that the proposed approach improves network performance since it results in higher network throughput keeping mean packet delay at low levels in comparison with conventional scheduling algorithms.
In this work, using ns-3 and different mobility models, we simulate realistic LTE network scenarios to study the effect of handover on two popular schedulers, namely the Proportional Fair (PF) and Max Weight (MW) sche...
详细信息
ISBN:
(纸本)9781479984060
In this work, using ns-3 and different mobility models, we simulate realistic LTE network scenarios to study the effect of handover on two popular schedulers, namely the Proportional Fair (PF) and Max Weight (MW) scheduler. The performances of these schedulers are widely studied in the literature via simulation and mathematical analysis in the absence of handovers. Specifically, it has been shown that MW is throughput optimal among all scheduling policies that stabilize the system in the sense of bounding the user queues. In our experiments, however, we observe that such general conclusions may not be accurate in the presence of mobile users that hand over across multiple cells. To this end, we show that: i) MW achieves higher throughput than PF when users are confined to a single cell, but ii) when there is handover in the network across multiple cells, PF achieves a throughput similar to that of MW, and in some cases even slightly outperforms MW. Furthermore, these observations are consistent across a wide range of network scenarios in terms of round-trip delay, buffer size and channel fading.
In recent years, Artificial Neural Networks have evolved rapidly and are applied to various fields. Meanwhile, to enhance computation efficiency of neural network applications, more and more neural network accelerator...
详细信息
ISBN:
(纸本)9783030296117;9783030296100
In recent years, Artificial Neural Networks have evolved rapidly and are applied to various fields. Meanwhile, to enhance computation efficiency of neural network applications, more and more neural network accelerators have been developed. Though traditional task scheduling algorithms on heterogeneous systems have been intensively researched, they can't be applied to neural network accelerators directly. Based on typical characteristics of neural network accelerators, we formalize the problem of tasks scheduling for neural networks, and transplant two listing heuristic scheduling algorithms, Heterogeneous-Earliest-Finish-Time (HEFT) and Critical-Pathon-a-Processor (CPOP). Inspired by the separable features of neural network operations, we propose two partition algorithms, the Iterative Partition scheduling Algorithm (IPS) and the Partition scheduling Combination Algorithm (PSC), which can be associated with scheduling algorithms. Further, we conduct experiments on some typical neural networks, and results show that compared to scheduling-only algorithms the partition associated algorithms achieve about 2x to 3x speedup.
This work provides some criteria that allow network administrators to measure the impact of different network configurations have on voice, data, and video applications quality of service offered to the different user...
详细信息
ISBN:
(纸本)9781728173498
This work provides some criteria that allow network administrators to measure the impact of different network configurations have on voice, data, and video applications quality of service offered to the different users. For that, this project implemented tests to measure parameters such as packet loss, delay and jitter using static routing, different packet scheduling algorithms (Custom Queuing, Priority Queuing, and Weighted First Queuing), different services (voice, data, and video), and connection speeds using Cisco 2800 Routers and D-ITG traffic generator in conjunction with the Network Time Protocol synchronizer. A comparative analysis of sensitive parameters for Quality of Service was conducted to describe network behavior for each service. The implemented services presented performances according to quality requirements, reported in the literature. Specifically, the data service presented delay and jitter within the levels considered acceptable for this application and zero packet loss. For its part, the video service presented levels of delay and jitter according to the quality requirements for streaming. Finally, the voice service presented the best configuration performance with the Priority Queuing algorithm, for all measured service quality parameters.
暂无评论