The uplink data arriving at the Machine-to-Machine (M2M) Application Server (AS) via M2M Aggregators (MAs) is fairly heterogeneous along several dimensions such as maximum tolerable packet delay, payload size and arrival rate, thus necessitating the design of Quality-of-Service (QoS) aware packet scheduler. In this paper, we classify the M2M uplink data into multiple QoS classes and use sigmoidal function to map the delay requirements of each class onto utility functions. We propose a proportionally fair delay-optimal multiclass packet scheduler at AS that maximizes a system utility metric. We note that the average class delay under any work-conserving scheduling policy can be realized by appropriately time-sharing between all possible preemptive priority policies. Therefore the optimal scheduler is determined using an iterative process to determine the optimal time-sharing between all priority scheduling policies, such that it results in maximum system utility. The proposed scheduler can be implemented online with reduced complexity due to the iterative optimization process. We then extend this work to determine jointly optimal MA-AS channel allocation and packet scheduling scheme at the MAs and AS. We first formulate a joint optimization problem that is solved centrally at the AS and then propose a low complexity distributed optimization problem solved independently at MAs and AS. We show that the distributed optimization solution converges quickly to the centralized optimization result with minimal information exchange overhead between MAs and AS. Using Monte-Carlo simulations, we verify the optimality of the proposed scheduler and show that it outperforms other state-of-the-art packet schedulers such as weighted round robin, max-weight scheduler etc. Another desirable feature of proposed scheduler is low delay jitter for delay-sensitive traffic.
Another line of work considers the design of packet schedulers for real-time control applications (see @cite_23 and references therein) and assume hybrid task sets comprising of periodic tasks with hard deadlines and aperiodic tasks with hard, soft or non-real-time requirements. The goal of these schedulers is to guarantee schedulability for critical tasks (with hard deadlines) while providing a best-effort service for other tasks. The periodic tasks from different flows are processed by assuming a fixed-priority assignment and with service deadline equal to the arrival period of that flow, while the aperiodic tasks from various flows are aggregated and served using First-Come-First-Serve policy. Some of the popular algorithms include Rate Monotonic scheduling @cite_27 , Polling Server, Deferrable Server @cite_22 , Priority Exchange @cite_24 , Sporadic Server @cite_5 and Slack-Stealing @cite_1 . However for most of the practical M2M systems, the arrival rate and delay requirements are potentially different for each aperiodic flow and thus aggregating the aperiodic flows will degrade the overall delay performance. Furthermore, these schemes define a , a virtual periodic task with certain computation time and priority level to process outstanding aperiodic tasks. But the determination of delay-optimal period and capacity for given traffic characteristics is not clear.
@cite_22 @cite_1 @cite_24 @cite_27 @cite_23 @cite_5
2140936050 2160498682 2109488193 2137784941 2570030068
Most existing scheduling algorithms for hard real-time systems apply either to periodic tasks or aperiodic tasks but not to both. In practice, real-time systems require an integrated, consistent approach to scheduling that is able to simultaneously meet the timing requirements of hard deadline periodic tasks, hard deadline aperiodic (alert-class) tasks, and soft deadline aperiodic tasks. This paper introduces the Deferrable Server (DS) algorithm which will be shown to provide improved aperiodic response time performance over traditional background and polling approaches. Taking advantage of the fact that, typically, there is no benefit in early completion of the periodic tasks, the Deferrable Server (DS) algorithm assigns higher priority to the aperiodic tasks up until the point where the periodic tasks would start to miss their deadlines. Guaranteed alert-class aperiodic service and greatly reduced response times for soft deadline aperiodic tasks are important features of the DS algorithm, and both are obtained with the hard deadlines of the periodic tasks still being guaranteed. The results of a simulation study performed to evaluate the response time performance of the new algorithm against traditional background and polling approaches are presented. In all cases, the response times of aperiodic tasks are significantly reduced (often by an order of magnitude) while still maintaining guaranteed periodic task deadlines. > A novel algorithm for servicing soft deadline aperiodic tasks in a real-time system in which hard deadline periodic tasks are scheduled using a fixed priority algorithm is presented. This algorithm is proved to be optimal in the sense that it provides the shortest aperiodic response time among all possible aperiodic service methods. Simulation studies show that it offers substantial performance improvements over current approaches, including the sporadic server algorithm. Moreover, standard queuing formulas can be used to predict aperiodic response times over a wide range of conditions. The algorithm can be extended to schedule hard deadline aperiodics and to efficiently reclaim unused periodic service time when periodic tasks have stochastic execution times. > The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications is a basic treatise on real-time computing, with particular emphasis on predictable scheduling algorithms. It introduces the fundamental concepts of real-time computing, illustrates the most significant results in the field, and provides the essential methodologies for designing predictable computing systems which can be used to support critical control applications. This volume serves as a textbook for advanced level courses on the topic. Each chapter provides basic concepts, which are followed by algorithms that are illustrated with concrete examples, figures and tables. Exercises are included with each chapter and solutions are given at the end of the book. The book also provides an excellent reference for those interested in real-time computing for designing and or developing predictable control applications. This thesis develops the Sporadic Server (SS) algorithm for scheduling aperiodic tasks in real-time systems. The SS algorithm is an extension of the rate monotonic algorithm which was designed to schedule periodic tasks. This thesis demonstrates that the SS algorithm is able to guarantee deadlines for hard-deadline aperiodic tasks and provide good responsiveness for soft-deadline aperiodic tasks while avoiding the schedulability penalty and implementation complexity of previous aperiodic service algorithms. It is also proven that the aperiodic servers created by the SS algorithm can be treated as equivalently-sized periodic tasks when assessing schedulability. This allows all the scheduling theories developed for the rate monotonic algorithm to be used to schedule aperiodic tasks. For scheduling aperiodic and periodic tasks that share data, this thesis defines the interactions and schedulability impact of using the SS algorithm with the priority inheritance protocols. For scheduling hard-deadline tasks with short deadlines, an extension of the rate monotonic algorithm and analysis is developed. To predict performance of the SS algorithm, this thesis develops models and equations that allow the use of standard queueing theory models to predict the average response time of soft-deadline aperiodic tasks serviced with a high-priority sporadic server. Implementation methods are also developed to support the SS algorithm in Ada and on the Futurebus+.