Broadcast Scheduling in Information Delivery Networks

Abstract

The continuous growth in the demand for access to information andthe increasing number of users of the information delivery systemshave sparked the need for highly scalable systems with moreefficient usage of the bandwidth. One of the effective methods forefficient use of the bandwidth is to provide the information to agroup of users simultaneously via broadcast delivery. Generally,all applications that deliver the popular data packages (trafficinformation, weather, stocks, web pages) are suitable candidatesfor broadcast delivery and satellite or wireless networks withtheir inherent broadcast capability are the natural choices forimplementing such applications.<p>In this dissertation, we investigate one of the most importantproblems in broadcast delivery i.e., the broadcast schedulingproblem. This problem arises in broadcast systems with a largenumber of data packages and limited broadcast channels and thegoal is to find the best sequence of broadcasts in order tominimize the average waiting time of the users.<p>We first formulate the problem as a dynamic optimization problemand investigate the properties of the optimal solution. Later, weuse the bandit problem formulation to address a version of theproblem where all packages have equal lengths. We find anasymptotically optimal index policy for that problem and comparethe results with some well-known heuristic methods.<p>Since the equal file length assumption is not appropriate forapplications such as cache broadcasting in the Internet deliverysystems, we also investigate an extension of the problem where thefiles have random lengths. After investigating some of theproperties of the optimal solution, we derive an asymptoticallyoptimal index policy for that case as well. Also, throughsimulation studies, the performance of the policy is compared withthat of some other heuristic polices designed by intuitivearguments. The index policy is also extended to systems withdeterministic, unequal file sizes and its performance is evaluatedand compared to other policies via simulation studies.<p>The formulation and analytical procedures used in deriving theindex policies in this dissertation allow for introduction ofother extensions of the problem like assigning weights to the datafiles (studied in Chapter 3) or taking into account the channelerrors and correlation between the arrivals. We will present ourformulation of the last two extensions and discuss some of thenumerical results to motivate future work on these problems.