When considering issues of fairness of scheduling algorithms for packet data in networks, there is no well defined quantitative value for the 'fairness" of the system. Rather, fairness is usually expressed in...
详细信息
ISBN:
(纸本)0780375149
When considering issues of fairness of scheduling algorithms for packet data in networks, there is no well defined quantitative value for the 'fairness" of the system. Rather, fairness is usually expressed in broader terms. Generally, a system is deemed to be fair if it meets certain criteria on throughput or delay, and unfair if the criteria are not met. For example, a system in which some user receives a throughput less than X bits/sec or experiences a delay T with probability greater than p% may be deemed to be unfair. These definitions of fairness say if the system is or is not fair, but not how fair or unfair. This paper attempts to make a quantitative definition for a value of 'fairness" that makes sense from both a mathematical and semantic standpoint. Such a value could be used to quickly compare the fairness of differing systems or algorithms. Definitions for the self-fairness and self-unfairness of the users of the system, and the average fairness and average unfairness of the overall system are proposed. The case is first considered when all users are weighted equally. That is, every user is considered to have the same importance, and hence each user should receive an equal proportion of the allocated resources for the system to be fair. The definitions are then extended to the case when the users have different weightings (for example, to achieve different levels of Quality of Service). The definitions take the viewpoint that the users themselves control what resources they are allocated. However, the definitions can just as easily be applied to the case when a central scheduling algorithm determines the allocation of resources to the users.
Air travel has increased dramatically and the construction of new airports and runways has not kept pace with the increase in air traffic. The development and the implementation of effective optimization methods for a...
详细信息
ISBN:
(纸本)9780735412873
Air travel has increased dramatically and the construction of new airports and runways has not kept pace with the increase in air traffic. The development and the implementation of effective optimization methods for air traffic control requires great attention to scheduling problems. In fact, air traffic controllers can be seen as real-time systems. In this paper the problem of flights scheduling (landings and takeoffs) is addressed. Timeline scheduling, First Come First Served and Earliest Deadline First algorithms have been compared in order to assess which of the three obtain better performance in the context of optimizing the flights scheduling.
This paper studies the performance of a large class of scheduling algorithms, and investigates the interaction between the application and the network to improve performance under congestion. The following key ideas a...
详细信息
ISBN:
(纸本)0818685387
This paper studies the performance of a large class of scheduling algorithms, and investigates the interaction between the application and the network to improve performance under congestion. The following key ideas are presented in this paper: (a) we show the performance and scalability trade-offs between providing separation and multiplexing among flows;(b) we show that a bounded buffer FIFO scheduler performs approximately as well as a WRR scheduler with per-flow queues in most practical situations, but requires significantly less overhead ill terms of per-flow stare;and (c) we show how link layer schedulers can use application-level hints in order to increase the perceived goodness of connections at higher layers.
In this paper, we deal with the regularity of status updates in a monitoring system. Specifically, we consider a system consisting of independent energy harvesting nodes with adaptive modulation capabilities that tran...
详细信息
ISBN:
(纸本)9781665486156
In this paper, we deal with the regularity of status updates in a monitoring system. Specifically, we consider a system consisting of independent energy harvesting nodes with adaptive modulation capabilities that transmit status updates to a non energy harvesting sink over a fading channel. Due to the randomness of the energy arrival and the channel time variations, a node may have difficulties maintaining regular status updates. Hence, the objective of this work is to design scheduling algorithms that minimize the number of violations of inter-delivery time over a finite time horizon. An inter-delivery violation event occurs when the time duration between two consecutive status updates exceeds a given time limit. We focus on online modulation and power adaptation policies where the transmitting sensor node adjusts the M-ary modulation level and transmission power based on both the channel state and the battery level. Specifically, we propose both deterministic and randomized algorithms to efficiently solve the considered scheduling problem for the one-node system. Deterministic solutions were extended to the multi-node system. The numerical results show that the proposed algorithms realize significant gain in terms of violations events compared to the benchmark fixed modulation solutions.
In this paper we introduce the Starting-Energy Fair Queuing (SEFQ), a novel class of energy-aware scheduling algorithms aim to guarantee a target lifetime to mobile devices while providing proportional energy consumpt...
详细信息
ISBN:
(纸本)9781467313568
In this paper we introduce the Starting-Energy Fair Queuing (SEFQ), a novel class of energy-aware scheduling algorithms aim to guarantee a target lifetime to mobile devices while providing proportional energy consumption and time-constraint meeting to tasks. With the extension of fair queuing to the energy domain, energy consumption of CPU is managed in a way that each task is guaranteed a share of the average power of a fixed period. The simulation results show that the performance of time-sensitive tasks can be traded-off with their fairness.
In this paper, we describe the problem of developing scheduling algorithms for an environment of parallel cluster tools, which is a special case of the parallel unrelated machines problem. At first we will describe th...
详细信息
ISBN:
(纸本)9781424405008
In this paper, we describe the problem of developing scheduling algorithms for an environment of parallel cluster tools, which is a special case of the parallel unrelated machines problem. At first we will describe the problem under consideration in detail and then present our scheduling environment and the idea of using slow down factors to predict lot cycle times to evaluate schedules and parts of them. This article is more a conceptual kind of work containing mostly basic thoughts to illustrate facets of the problem and first solution ideas. Nonetheless the authors see a high potential in examining these questions. Little research has been done on that issue so far.
We consider the problem of selfish misbehavior in scheduling algorithms of wireless networks. All wireless scheduling algorithms are designed under the assumption that network users will follow the algorithm specifica...
详细信息
ISBN:
(纸本)9781424493289
We consider the problem of selfish misbehavior in scheduling algorithms of wireless networks. All wireless scheduling algorithms are designed under the assumption that network users will follow the algorithm specifications. In this paper, we study two scheduling algorithms in which a selfish user might misbehave in order to achieve better performance. In the first case, we consider a network that implements cross-layered rate control mechanism to determine arrival rate of users as well as link schedules. We explain a scenario in which a selfish user obtains extra throughput by misleading the scheduling component of the network. We find an equivalent optimization framework that captures misbehavior pattern of the selfish user. We present a solution to prevent such a greedy behavior by imposing a cost term on the utility function of the users. In the second part of the work, we consider the family of random access scheduling algorithms in which users of the wireless network wait for randomly chosen back-off intervals before accessing the medium. A selfish user might wait for smaller back-off in order to obtain an unfair advantage. We present a comparison method to detect such a greedy misbehavior.
The paper presents a tool for the assessrnent of the capacity of railway networks. This tool includes a first definition level that can be considered as microscopic, which permits train-runs to he simulated in a numer...
详细信息
The paper presents a tool for the assessrnent of the capacity of railway networks. This tool includes a first definition level that can be considered as microscopic, which permits train-runs to he simulated in a numerical way, through the identification of the occupation of block sections;a second mesoscopic level then uses aggregated data (e.g., the run times between stations or the minimum admitted headways), which can be calculated automatically by the micro-simulator or entered directly by the user, as input. A scheduling algorithm, using the aggregated data, produces feasible timetables, optimised according to given quality parameters. Since the procedure is automated and the computation phase is rather quick, it can be used to generate sets of feasible timetables and to perform timetable-based capacity assessments. Its implementation, within a perturbation analysis, is based on a discrete-event simulation core. This core applies any perturbation (delay, accident, anomaly) to a given timetable, which is re-arranged in order to solve any traffic conflict and to assess the robustness of the timetable design. The effectiveness of the rescheduling algorithms, which can be used to simulate different strategies that could be adopted by dispatchers, is also evaluated.
This paper focuses on researching and visualizing the differences of the quality of network connections between several network applications using popular scheduling algorithms. The aim of this work is to examine and ...
详细信息
ISBN:
(纸本)9781510630666
This paper focuses on researching and visualizing the differences of the quality of network connections between several network applications using popular scheduling algorithms. The aim of this work is to examine and compare the impact of application of scheduling algorithms for FIFO, DWRR, WFQ, PQ packets in IPv4 and IPv6 networks on the quality of data transmission. Using Riverbed Modeler Academic Edition version 17.5 software there was developed 10 research scenarios with different scheduling algorithms and IP protocols implemented on routers. Scenarios based on IP protocols in the fourth and sixth versions with implemented FIFO, PQ, DWRR and WFQ scheduling algorithms has been developed. Each scenario includes the operation of real-time VoIP and video conferencing applications as well as HTTP, FTP and e-mail applications. The research showed that there are significant differences in the quality of packet transmission of the tested applications using different configurations of the scheduling algorithms and network protocols.
In this paper, we study the problem of link scheduling for multi-hop wireless networks with per-flow delay constraints. Specifically, we are interested in algorithms that maximize the asymptotic decay-rate of the prob...
详细信息
ISBN:
(纸本)9781467307758
In this paper, we study the problem of link scheduling for multi-hop wireless networks with per-flow delay constraints. Specifically, we are interested in algorithms that maximize the asymptotic decay-rate of the probability with which the maximum end-to-end backlog among all flows exceeds a threshold, as the threshold becomes large. We provide both positive and negative results in this direction. By minimizing the drift of the maximum end-to-end backlog in the converge-cast on a tree, we design an algorithm, Largest-Weight-First(LWF), that achieves the optimal asymptotic decay-rate for the overflow probability of the maximum end-to-end backlog as the threshold becomes large. However, such a drift minimization algorithm may not exist for general networks. We provide an example in which no algorithm can minimize the drift of the maximum end-to-end backlog. Finally, we simulate the LWF algorithm together with a well known algorithm (the back-pressure algorithm) and a large-deviations optimal algorithm in terms of the sum-queue (the P-TREE algorithm) in converge-cast networks. Our simulation shows that our algorithm significantly performs better not only in terms of asymptotic decay-rate, but also in terms of the actual overflow probability.
暂无评论