This thesis examines the problem of scheduling with incomplete and/or local information in wireless systems. With large numbers of users and limited feedback resources, wireless systems require good scheduling algorithms to attain their performance limits. Classical studies on wireless scheduling investigate in much detail settings where the full state of the system is available when scheduling users. In contrast, this thesis focuses on the case where valuable network state information is lacking at the scheduler, and studies its resulting effect on system performance. The insights gained from the analysis are used to develop efficient wireless scheduling algorithms that operate with limited state information, and that guarantee high throughput and delay performance. The first part of the thesis considers scheduling for stability in a wireless downlink system, where a base station or server schedules transmissions to users, while acquiring channel state information from only subsets of users. It is shown that the system’s throughput region is completely characterized by the marginal channel statistics over observable channel subsets. Effective, queue-length based joint sampling and scheduling algorithms are developed that observe appropriate subsets of channels and schedule users, and the algorithms are shown to be optimal in the sense of throughput. Next, the thesis studies the queue-length performance of wireless scheduling algorithms that use only partial, subset-based channel state information. The chief objective here is to design partial information-based scheduling algorithms that keep the packet queues in the system short, and in this regard, the contributions of this thesis are twofold. First, from the algorithmic perspective, wireless scheduling algorithms using partial channel state information are designed that minimize the likelihood of queue overflow, in a suitable sense, across all partial information scheduling algorithms. The second key contribution is technical, by the development of novel analytical techniques to study the stochastic dynamics of partial state information-based algorithms. These techniques are not only instrumental in showing the optimality results above, but are also of independent interest in understanding the behavior of algorithms which rely on partially sampled system state. The second part of the thesis investigates coordinated inter-cell wireless scheduling across multiple base stations, each possessing only local and partial channel state information for its own users. Coordinated scheduling is necessary to mitigate interference between users in adjacent cells, but information sharing between the base stations is limited by high latencies in the backhauls that interconnect them. A class of distributed scheduling algorithms is developed in which the base stations share only delayed queue length information with each other, and locally acquire partial channel state information, to schedule users. These algorithms are shown to be throughput-optimal, and their average backlog performance in terms of the inter-base station latency is quantified. / text

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Not available / text

Paratransit operations in cities in developing countries play an important role in public transport provision. The operations are run within the realm of the infonnal sector and are highly flexible. There are numerous operators running one or two vehicles on a cash basis. This and other issues contribute to the problems with the services that are provided. Poor reliability and stability in supply are the main problems. Despite these serious problems, there has been little research on possible solutions to resolve them. The present study is aimed at improving understanding of the operation of such systems. It assesses the effects on users and operators of different routing, stopping and scheduling regimes. A new model of paratransit operations is developed. The problem of paratransit operations is conceptualised in terms of interactions between demand and supply. The interactions take place in time and geographical space and are shaped by the actions taken by individual users and individual vehicle operators. The model is designed to overcome some of the restrictions on the definitions of time - and in particular space - that are found in existing methodologies. A modelling approach designed to represent the two dimensions as realistically as possible was adopted. Two techniques are central to the construction of the model. Simulation techniques are used to model the temporal processes and a Geographical Information System (GIS) for the spatial processes. The two are complementary to overcome the inherent weaknesses in either approach. Modules are developed to represent demand and supply at a microscopic level. The Model of Paratransit Services (MOPS) involves interfacing a GIS and external modules for dynamic processes. The model was validated against field data collected in Harare, Zimbabwe. Experiments were run for a case study area and the results that were obtained on routing, stopping and scheduling regimes are reported in developing countries.

Context: Standard transport layer protocols like UDP, TCP, andSCTP use only one access technology at a time. Concurrent MultipathTransmission (CMT), has been developed for parallel use of the access technologies. The main theme of this thesis work is to implement CMT in real-time and evaluate the impact of various scheduling algorithms on its performance. Objectives: The main objectives of this thesis are to implement a de-multiplexer at the source, re-sequencer at the receiver and to investigate some of the heuristics and analyzing their impact based on some performance metrics. Methods: Thorough understanding on this topic is attained by literature review of related works. To implement and evaluate the different scheduling patterns an experimental test bed is set up. For thetransmission of data, socket programming in Python is used. Varying various parameters that are involved in the experiment, performance metrics were measured and based on them statistical analysis is carried out for proper evaluation. Results: CMT is implemented in real-time test bed and concurrency is validated. Weighted Round-Robin has better performance compared to that of Round-Robin when the size of the packet is large whereas both exhibit nearly same behavior for smaller packet sizes. Conclusions: It can be concluded that Weighted Round-Robin attains higher throughput. It can be possibly due to more load of fragmentation when large packets are transmitted on the high reliable path and hence better performance than Round-Robin. There is need for further evaluation of other metrics like delay, jitter and using other scheduling mechanisms and in other environments as well.

No description available.

Battery-powered portable embedded systems have been widely used in many applications. These embedded systems have to concurrently perform a multitude of complex tasks under stringent time constraints. As these systems become more complex and incorporate more functionality, they became more power-hungry. Thus, reducing power consumption and extending battery lifespan while guaranteeing the timing constraints has became a critical aspect in designing such systems. This gives rise to three aspects of research: (i) Guaranteeing the execution of the hard real-time tasks by their deadlines, (ii) Determining the minimum voltage under which each task can be executed, and (iii) Techniques to take advantage of run-time variations in the execution times of tasks. In this research, we present techniques that address the above aspects in single and multi processor embedded systems. We study the performance of the proposed techniques on various benchmarks in terms of energy savings.

Time-sensitive applications that are also CPU intensive like video games, video playback, eye-candy desktops etc. are increasingly common. These applications run on commodity operating systems that are targeted at diverse hardware, and hence they cannot assume that sufficient CPU is always available. Increasingly, these applications are designed to be adaptive. When executing multiple such applications, the operating system must not only provide good timeliness but also (optionally) allow co-ordinating their adaptations so that applications can deliver uniform fidelity. In this work, we present a starvation-free, fair, process scheduling algorithm that provides predictable and low latency execution without the use of reservations and assists adaptive time sensitive tasks with achieving consistent quality through cooperation. We combine an event-driven application model called cooperative polling with a fair-share scheduler. Cooperative polling allows sharing of timing or priority information across applications via the kernel thus providing good timeliness, and the fair-share scheduler provides fairness and full utilization. Our experiments show that cooperative polling leverages the inherent efficiency advantages of voluntary context switching versus involuntary pre-emption. In CPU saturated conditions, we show that the scheduling responsiveness of cooperative polling is five times better than a well-tuned fair-share scheduler, and orders of magnitude better than the best-effort scheduler used in the mainstream Linux kernel.

No description available.

No description available.