Scheduling Real-time Multi-item Requests In Multi-channel Data Broadcast Systems

Data broadcast is a widely accepted approach to dynamic and scalable wire-less information dissemination. With the rapidly increasing number of mobile users and real-time applications, real-time data demand from clients becomes more intractable in data broadcast systems. Moreover, the large data demand results in large database at the server side. Hence a static push-based broadcast program based on historical data access statistics or pre-determined request profiles can-not work well to achieve optimal performance. Therefore, on-demand broadcast is preferable. However, on-demand broadcast requires online data scheduling, which is hard to get optimal or near-optimal performance. Secondly, in some emerging applications, such as road traffic navigation systems, clients may request more than one dependent data items at a time. Such multi-item requests with dead-lines complicate the design of data scheduling algorithms for real-time on-demand data broadcast systems. Thirdly, although existing multi-channel architecture increases the available bandwidth for satisfying the large data demand, it com-plicates the bandwidth sharing among different channels and different clients as a client can only retrieve one data item from one channel at a time. Based on the above discussions, an online data scheduling algorithm is a vital component of real-time on-demand data broadcast systems.With the proliferation of real-time applications, minimizing request deadline miss ratio in scheduling multi-item requests has become an important task. In this study, we prove the NP-hardness of scheduling real-time multi-item requests in both single-and multi-channel data broadcast environments. Furthermore, we propose two profit-based scheduling algorithms, PVC and SSA, for single-and multi-channel architectures, respectively. Both algorithms utilize our two new concepts which are "profit" of pending items and "opportunity cost" of pending requests. To the best of our knowledge, it is the first time to introduce opportu-nity cost, which is derived from economics, into on-demand broadcast scheduling. Based on the scheduling decisions made by PVC, SSA allocates data items in the scheduled requests to available channels. Simulation results show great im-provement in comparison with traditional algorithms. In general, PVC for single channel scheduling is superior to the best of other algorithms in terms of request deadline miss ratio. For multi-channel scheduling, SSA has larger advantage with increasing number of channels in terms of request deadline miss ratio than the best of other algorithms. In addition, in the condition of the same total band-width, as simulation results show that scheduling in single-channel environment has better real-time performance than scheduling in multi-channel environment in terms of request deadline miss ratio, it motivates us to compare the former two kinds of scheduling through theoretical modelling. Our theoretical results show that single-channel scheduling is better than multi-channel scheduling in terms of average turnaround time.Although various works on admission control have been done for connection-oriented congestion control in wired and wireless networks, to the best of our knowledge. there is no admission control proposed for real-time data broadcast systems. In wireless/mobile network environments, data broadcasting is an in-creasingly popular method for information dissemination due to its potential to satisfy all outstanding requests for the same data item with a single response. In addition, data broadcasting can accommodate arbitrary populations of clients with common interests. In real-time applications, all requests have deadline con-straints, that is, missing deadlines means failure of requests. However, without admission control, all clients must wait for their desired data items until the re-quest deadlines. If the requests fail at the end, it is a waste of battery power and time. In addition, the clients have no idea about whether their requests can be satisfied at the time of submission. It will deteriorate client experience and service attraction. To reduce unnecessary waiting time of the failed requests and to provide some QoS guarantee to the clients, admission control is introduced to real-time data broadcast systems. After submission, the data items in a request are allocated to channels. If the allocation is infeasible, the request will be rejected in advance.However, by constructing the sub-problem of admission control, namely a clique problem, we prove that admission control of real-time multi-item requests that maximizes bandwidth sharing in data broadcast systems is an NP-hard prob-lem. After that, we propose a simplified algorithm of admission control, called Item Level Admission Control (ILAC). After admission control, to maximize band-width sharing, the channel allocation problem is modelled as a matching based allocation problem and is solved by utilizing the classical Primal-dual method. In addition, switching cost among channels is reduced through dynamic program-ming technique. Based on the above two points, we propose an algorithm called Matching Based Allocation (MBA). Simulation experiments are conducted to ver-ify the advantages of our proposed algorithms of admission control and channel allocation.