On-line admission control and packet scheduling with interleaving
Proceedings - IEEE INFOCOM - Tập 1 - Trang 94-103 vol.1
Tóm tắt
This paper presents a comprehensive study of the effect of job interleaving by preemption on the throughput of a single server where requests arrive with a given processing time and slack. The problem is to decide which requests to serve so as to maximize the server's utilization. This simple model captures many situations, both at the application (e.g., delivery of video) as well as at the network/transmission levels (e.g., scheduling of packets from input to output interface of a switch). The problem is on-line in nature, and thus we use competitive analysis for measuring the performance of our scheduling algorithms. We consider two modes of operation - with and without commitment - and derive upper and lower bounds for each case. Since competitive analysis is based on the worst-case scenario, the average-case performance of the algorithms is also examined by a simulation study.
Từ khóa
#Admission control #Scheduling algorithm #Interleaved codes #Network servers #Switches #Performance analysis #Algorithm design and analysis #Throughput #Packet switching #Analytical modelsTài liệu tham khảo
0
10.1109/90.556345
gens, 1979, Computational complexity of approximation algorithms for combinatorial problems, Mathematical Foundations of Computer Science, 74, 292
10.1006/jagm.1999.1060
garey, 1979, Computers and intractability: A guide to the theory of NP-completeness
1999, Data-over-cable service interface specification radio frequency interface specification SP-RFIv1.1-101-990311
goldwasser, 1999, Patience is a virtue: The effect of slack on competitiveness for admission control, Proc 9th Annu ACM-SIAM on Discrete Algorithms, 396
10.1109/18.623149
10.1137/S0895480196305124
armitage, 2000, Quality of service in IP networks
0, Atlanta ATM ICs
feldman, 1995, Competitive analysis of call admission algorithms that allow delay
10.1007/BF00365406
10.1109/12.620484
bar-yehuda, 1985, A local-ratio theorem for approximating the weighted vertex cover problem, Annals of Discrete Mathematics, 25, 27
borodin, 1998, Online Computation and Competitive Analysis
10.1002/jos.85
10.1007/978-1-4471-0459-9