On the performance of real-time multi-item request scheduling in data broadcast environments

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic data access patterns. Previous studies on time-critical on-demand data broadcast were conducted under the assumption that each client requests only one data item at a time. With the rapid growth of time-critical information dissemination services in emerging applications, there is an increasing need for systems to support efficient processing of real-time multi-item requests. Little work, however, has been done. In this paper, we study the behavior of six representative single-item request based scheduling algorithms in time-critical multi-item request environments. The results show that the performance of all algorithms deteriorates when dealing with multi-item requests. We observe that data popularity, which is an effective factor to save bandwidth and improve performance in scheduling single-item requests, becomes a hindrance to performance in multi-item request environments. Most multi-item requests scheduled by these algorithms suffer from a starvation problem, which is the root of performance deterioration. Based on our analysis, a novel algorithm that considers both request popularity and request timing requirement is proposed. The performance results of our simulation study show that the proposed algorithm is superior to other classical algorithms under a variety of circumstances.     

Scheduling time‐critical requests for multiple data objects in on‐demand broadcast

On‐demand broadcast is an effective data dissemination approach in mobile computing environments. Most of the recent studies on on‐demand data broadcast assume that clients request only a single‐data‐object at a time. This assumption may not be practical for the increasingly sophisticated mobile applications. In this paper, we investigate the scheduling problem of time‐critical requests for multiple data objects in on‐demand broadcast environments and observe that existing scheduling algorithms designed for single‐data‐object requests perform unsatisfactorily in this new setting. Based on our analysis, we propose new algorithms to improve the system performance. Copyright © 2010 John Wiley & Sons, Ltd.     

无线环境中的数据广播调度理论分析及算法研究

数据广播是无线环境中一种独特的数据发布方式。首先系统地归纳了周期广播、on-demand广播和混合广播3种广播方式的理论分析模型及其特点,然后针对单信道和多信道对各种广播方式的调度算法进行了分类、比较,并突出了理论模型对调度算法研究的指导价值。最后指出今后的研究方向。     

On-Demand数据广播环境下实时有序查询处理

在On-Demand数据广播环境下,广播服务器基于用户发送的数据请求等信息进行调度决策来满足用户的数据访问需求。在很多实际应用中,用户的数据请求需要在一定时间段内得到满足,即数据请求是有截止期的。现有研究只考虑了具有截止期约束的单个数据请求的调度问题,而实时查询处理即用户以查询为单位依次发送多个数据请求的研究尚未得到足够的关注。本文重点研究了On-Demand数据广播环境下如何有效地处理实时有序查询这一问题。基于对该问题的分析,定义了一类新的调度问题ROBS并证明了ROBS的Off-Line版本是NP-Hard的;提出了一种新的考虑查询语义的On-Line调度算法OL-ROBS,该算法通过综合考虑数据请求个数、查询截止期和查询剩余数据请求个数来确定待广播数据项的优先级;为提高OL-ROBS的执行效率,设计了一种裁减算法,用以减少调度决策的搜索空间。模拟实验将OL-ROBS与目前最为有效的实时数据请求调度算法Sinθ-进行了比较,结果显示OL-ROBS具有更低的错过截止期比率。     

Scheduling broadcasts with deadlines

We investigate the problem of scheduling broadcasts in data delivering systems via broadcast, where a number of requests from several clients can be simultaneously satisfied by one broadcast of a server. Most of prior work has focused on minimizing the total flow time of requests. It assumes that once a request arrives, it will be held until satisfied. In this paper, we are concerned with the situation that clients may leave the system if their requests are still unsatisfied after waiting for some time, that is, each request has a deadline. The problem of maximizing the throughput, for example, the total number of satisfied requests, is developed, and there are given online algorithms achieving constant competitive ratios.     

实时环境下一种混合广播调度策略

在实时的非对称通讯环境下,自适应混合广播策略能够根据数据的请求模式以及时间限制等特征来动态分配周期广播和按需广播的带宽比例.将这一策略推广到基于事务的多数据项广播调度中,同时引入"分布式广播"思想,以更精细的周期广播粒度来解决过长的周期广播与事务及数据的实时要求之间的矛盾,并且动态分配时间槽.实验结果表明:改进的调度策略更适合于实时环境下的数据广播,具有更低的事务失败率以及更小的上行信道负荷.     

非对称网络环境中数据广播的带索引多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,为了节约移动计算机接听数据广播的电源消耗,同时兼顾访问时间的限制,文中提出了两种带索引多盘调度算法,即复制索引算法（ＩＭＤ－ＲＩ）和多路复用算法（ＩＭＤ－ＭＵＸ）。理论分析和实验结果表明,这两种算法通过在广播信息中加入索引信息,能够有效减少数据广播的调谐时间,同时仍保持较低的访问时间,因此更具有竞争性     

数据广播环境下实时查询处理

现有的实时数据广播研究中,只考虑了具有截止期约束的单个数据请求的调度问题,而支持实时查询处理的数据广播技术尚未得到足够的关注。该文研究在on-demand数据广播环境下,如何有效地处理实时查询问题,提出一种新的数据调度算法(QSA)。通过仿真实验与目前最为有效的数据请求调度算法SIN进行了比较,结果显示QSA具有更低的错过截止期比率,在最好的情况下,QSA比SIN降低了17.45%。     

Utility driven optimization of real time data broadcast schedules

Data dissemination in wireless environments is often accomplished by on-demand broadcasting. The time critical nature of the data requests plays an important role in scheduling these broadcasts. Most research in on-demand broadcast scheduling has focused on the timely servicing of requests so as to minimize the number of missed deadlines. However, there exists many environments where the utility of the received data is an equally important criterion as its timeliness. Missing the deadline may reduce the utility of the data but does not necessarily make it zero. In this work, we address the problem of scheduling real time data broadcasts with such soft deadlines. We investigate search based optimization techniques to develop broadcast schedulers that make explicit attempts to maximize the utility of data requests as well as service as many requests as possible within an acceptable time limit. Our analysis shows that heuristic driven methods for such problems can be improved by hybridizing them with local search algorithms. We further investigate the option of employing a dynamic optimization technique to facilitate utility gain, thereby eliminating the requirement of a heuristic in the process. An evolution strategy based stochastic hill-climber is investigated in this context.     

On-demand broadcast for multiple-item requests in a multiple-channel environment

On-demand broadcast is an effective approach to disseminating data in mobile computing environments. Substantial efforts have been devoted to improving the scheduling efficiency of on-demand broadcast. Previous studies focused mainly on the case of scheduling single-item requests in single-channel environments. However, requesting multiple dependent data items is common in many advanced applications such as electronic stock trading and traffic information enquiry services. In addition, multi-channel architectures are widely deployed in data broadcast systems. In this work, we investigate the issues arising in scheduling multi-item requests in multi-channel on-demand broadcast environments. Two problems, namely, the request starvation problem and the bandwidth utilization problem are identified in existing algorithms. To tackle the observed problems, an innovative algorithm is proposed. Results from our simulation study demonstrate the superiority of the proposed algorithm.     

Scheduling on-demand data broadcast in mixed-type request environments

In many on-demand broadcast environments, there can be a mix of requests, in which some of the requests have real-time constraints, while other requests have no time constraints associated with them. We refer to such environments as mixed-type environments. Existing strategies for on-demand data in broadcast systems typically only consider how to minimize the wait time of the requests, while scheduling strategies for real-time requests typically only consider how to minimize the number of deadlines missed. How to satisfy both of these constraints is a challenging problem whose solution can benefit many applications. In this paper, we present an on-demand broadcast cost model that is more general than existing broadcast cost models because it considers both response time and number of deadlines missed. An analysis of the system is presented as a Markov decision process to ascertain the feasibility of an optimal policy. We propose two scheduling strategies for mixed-type broadcast systems that are based on our cost model: maximum paid cost first and maximum value gained first. The simulation results show that both of our strategies always achieve the best result, when compared to existing broadcast strategies, for varying request arrival rates, real-time to non-real-time request ratios, missed deadline weight values, wait-time bounds on the non-real-time requests, and varying broadcast rates.     

Courier: Multi-dimensional QoS guarantees for the consolidated storage system

The increasing cost and complexity of data management is driving data centers to consolidate resource and provide storage service for multiplex applications. Therefore, storage systems must be able to guarantee multi-dimensional Quality of Service (QoS) for various applications. However, satisfying performance targets for each workload is challenging, because that the I/O characteristics of workloads usually varies widely and capability of storage system changes significantly. In this paper, we design and implement a novel QoS scheduler, Courier, to maintain satisfactory performance for applications even in this highly-volatile scenario. Courier dynamically alternates between a feedback-based latency controller and reward budget-based scheduling to achieve per-application performance requirement. The feedback-based controller is employed to estimate request service times and adjust scheduling strategy dynamically. Based on the estimation, it can identify time-critical requests from throughput-sensitive requests and schedule applications with time-critical requests preferentially to avoid latency violations. In addition, Courier rewards well-behavior application with more budget to maintain high storage utilization while providing performance guarantees. We evaluate the effectiveness of our approach using synthetic and real workloads, and the results show that Courier has good ability to achieve per-application performance targets.     

Adaptive optimization of least-squares tracking algorithms: with applications to adaptive antenna arrays for randomly time-varying mobile communications systems

Adaptive antenna arrays are used for reducing the effects of interference and increasing capacity in mobile communications systems. Typical algorithms recursively compute the antenna weights that minimize the weighted error function (at discrete times kh, k=1,2,..., for a sampling interval h) /spl sigma//sub l=1//sup k//spl alpha//sup k-l/[e/sub l/(W)]/sup 2/, where e/sub l/(W) is a measure of the reception error at time lh with antenna weight vector W, and /spl alpha/<1. The forgetting factor /spl alpha/<1 allows tracking as conditions change and the minimization is used only to get the weights. The average detection error rate depends heavily on the chosen value of /spl alpha/, whose optimal value can change rapidly in time, perhaps significantly in seconds. We add another adaptive loop that tracks the optimal value of /spl alpha/ and greatly improves the operation when the environment is randomly time-varying. The additional adaptive loop is based on an approximation to a natural "gradient descent" method. The algorithm is practical and can improve the performance considerably. In terms of average detection error rates and for all of the scenarios tested, the new system tracks the optimal value of /spl alpha/ well, and always performs better (sometimes much better) than the original algorithm that uses any fixed value of /spl alpha/. Although the initial motivation arises in adaptive antennas, the method can be used to improve algorithms for tracking parameters of time-varying nonlinear systems, where similar issues are involved.     

Scheduling on-demand broadcast with timing constraints

In a distributed system, broadcasting is an efficient way to dispense data in certain highly dynamic environments. While there are several well-known on-line broadcast scheduling strategies that minimize wait time, there has been little research that considers on-demand broadcasting with timing constraints. One application which could benefit from a strategy for on-demand broadcast with timing constraints is a real-time database system. Scheduling strategies are needed in real-time databases that identify which data item to broadcast next in order to minimize missed deadlines. The scheduling decisions required in a real-time broadcast system allow the system to be modeled as a Markov Decision Process (MDP). In this paper, we analyze the MDP model and determine that finding an optimal solution is a hard problem in PSPACE. We propose a scheduling approach, called Aggregated Critical Requests (ACR), which is based on the MDP formulation and present two algorithms based on this approach. ACR is designed for timely delivery of data to clients in order to maximize the reward by minimizing the deadlines missed. Results from trace-driven experiments indicate the ACR approach provides a flexible strategy that can outperform existing strategies under a variety of factors.     

Dynamic priority scheduling of periodic queries in on-demand data dissemination systems

As an important wireless data broadcast technique, on-demand broadcast has been widely used for dynamic and large-scale data dissemination. An important class of emerging data broadcast applications requires monitoring multiple data items continuously in order to support data-driven decision making. Since wireless bandwidth is a precious shared medium, an important problem to solve is how to disseminate data to periodic queries, so that all the requests can be satisfied while the bandwidth consumption is minimized. In this paper, we first propose a new real-time scheduling algorithm called EDFS, which is a variant of the classic EDF [24] algorithm. Based on EDFS, we propose a novel on-line broadcast scheduling algorithm, called EDFS-BS. To our best knowledge, EDFS-BS is the first dynamic priority based broadcast scheduling algorithm that can be utilized to satisfy the timing constraints of periodic queries. We also propose a bandwidth utilization based schedulability test for EDFS-BS, which is used to ensure timing predictability of a periodic query set. Extensive experiments have been conducted to compare EDFS-BS versus existing solutions with comparable quality. The results show that EDFS-BS outperforms them considerably in terms of wireless bandwidth consumption and query service ratio.     

I/O issues in a multimedia system

In future computer system design, I/O systems will have to support continuous media such as video and audio, whose system demands are different from those of data such as text. Multimedia computing requires us to focus on designing I/O systems that can handle real-time demands. Video- and audio-stream playback and teleconferencing are real-time applications with different I/O demands. We primarily consider playback applications which require guaranteed real-time I/O throughput. In a multimedia server, different service phases of a real-time request are disk, small computer systems interface (SCSI) bus, and processor scheduling. Additional service might be needed if the request must be satisfied across a local area network. We restrict ourselves to the support provided at the server, with special emphasis on two service phases: disk scheduling and SCSI bus contention. When requests have to be satisfied within deadlines, traditional real-time systems use scheduling algorithms such as earliest deadline first (EDF) and least slack time first. However, EDF makes the assumption that disks are preemptable, and the seek-time overheads of its strict real-time scheduling result in poor disk utilization. We can provide the constant data rate necessary for real-time requests in various ways that require trade-offs. We analyze how trade-offs that involve buffer space affect the performance of scheduling policies. We also show that deferred deadlines, which increase buffer requirements, improve system performance significantly     

移动实时环境下一种改进的广播调度算法

在网络带宽不对称的移动实时环境中,数据广播是一种有效的数据访问方式。针对这种网络特性,分析了现今已经存在的某些广播调度算法。针对UFO算法,分别提出了SBS算法和CRS算法,它们从服务器、移动客户端两个方面进行了改进。两种算法可以根据给定的数据项访问概率分布,自动生成广播调度。通过理论分析和实验结果表明,该算法不会产生事务重启,并且可以有效减少数据的访问时间,使用户访问数据广播的平均等待时间最小。     

A speculative load adaptive streaming scheme for efficient video delivery

Video on demand services require video broadcast schemes to provide efficient and reliable performance under various client request loads. In this paper, we have developed an efficient request load adaptive broadcast scheme, speculative load adaptive streaming scheme (SLAS), that requires lower service bandwidth than previous approaches, regardless of request rate. We have provided both analysis and simulation to show the performance gain over previous schemes. In this paper, we provide the theoretic upper bound of the continuous segment allocations on channels. We found that the number of allocated segments of the SLAS is close to the theoretic upper bound when compared with other schemes over various numbers of stream channels. Our analysis of client waiting time is almost identical to simulation results about all client requests. By simulation, we compared the required service bandwidth and storage requirements of the SLAS scheme and other schemes and found the SLAS scheme is an efficient broadcast scheme as compared to well known seamless channel transition schemes.     

Scheduling algorithms for multicast traffic in TDM/WDM networks with arbitrary tuning latencies

We consider all-optical Time Division Multiplexing (TDM)/Wavelength Division Multiplexing (WDM) broadcast and select networks with slotted operation. Each network access node is equipped with one fixed transmitter and one tunable receiver; tuning times are not negligible with respect to the fixed size slot time. We discuss efficient scheduling algorithms to assign TDM/WDM slots to multicast traffic in such networks. The problem is shown to be NP-hard; thus, heuristic algorithms based on the Tabu Search meta-heuristic are proposed, and their performance are assessed using randomly created request matrices based on two types of multicast traffic patterns. We show that significant advantages can be obtained by using these novel algorithms with respect to simpler greedy algorithms, even when restricting CPU times to realistic values to make the algorithms of practical use.     

An energy-efficient and access latency optimized indexing scheme for wireless data broadcast

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.