Online algorithms for the provision of quality of service in networks

by Fung, Ping-yuen

(Uncorrected OCR) Absact of thess enttled 'Online Algorithms for the Provision of Quality of Service in Networks' submitted by Fung Ping Yuen for the degee of Docor of Philophy at the Univesity of Hong Kng in March 2005 ew Intenet appliatins equie the undelying network o provide diffeent levels of or eliable sevie. The co of Quality of Svie (QoS) was designed t meet this demand. A number of algorithmi issues aise in the provisi of QoS, and in this study we conside thee elated nline scheduling problems for QoS. These thee problems besides having prtial appliatins e also of consideable theoretial inteest. The fst problem is an nline preemtive scheduling problem in whih a set of jobs with vaying elease times deadlines, processing times and weights must be sheduled s as t maximize the ttal value btained. Unli lassial heduling problems, ptially coleted jobs an btain tial values propor tinal t thei amunts processed. This problem has appliatins in multimedia QoS provisining in networks as well as ther prtial appliatins. The second problem is a cket sheduling problem for network switches supporting QoS. Packets with diffeent QoS values arrive at a network swit and ae t be sent alng an utging lin ue to oveading conditins me ckets have t be dropped. The tive is t maximize the ttal value of ckets that ae sent. We formulate this as an nline unit job sheduling problem whee ea job is sified by its elease time deadline and weight. In the thi problem a set of pages is t be broadasted to clients n demand. Requests asing for the same age an be satisfied in a single broadast. Ea equest is associated with a deadline and the tive is t maximize the profit equests satisfied before thei deadlines. We provide new and improved nline algorithms and lowe unds n the coetitive ati for these problems. In sme ases the bunds ae tight. Some major contibutins inlude: (1) a 1.58coetitive timeshaing algorithm for the heduling of jobs with tial values and a 1.618 lowe und n the coetitive atio of timeshaing algorithms; (2) andmized lowe und of 1.25 whi pplies simultaneusly t the sheduling of ptial value bs unit bs, and roadasts with deadlines as well as thei vaiatins; (3) optimal and improved algorithms for me sial ases of unit job sheduling; and (4) extensi of the heduling problems t the multiprocessor case inluding a new multiprocessor algorithm for unit job sheduling. We als show that the thee problems have inteesting connetins and that me of the tehniques we have developed an be applied t ore than ne of these problems.