Asymptotical Optimal Online Packet Scheduling in Multi-hop Networks

Asymptotical Optimal Online Packet Scheduling in Multi-hop Networks

时间：2019年6月4日（周二）10:00-11:30，14:30-16:00 地点：计算机楼370会议室

报告简介：

We first study the online packet scheduling problem raised by Mao, Koksal and Shroff for packets with arbitrary hard deadlines in multi-hop networks aiming at maximizing the total revenue. We present a greedy algorithm that is much more time efficient and yet achieves O(PM)-competitive, improving on MKS algorithm by a factor of O(logPM). We have also shown that it is asymptotically optimal by proving W(PM) is a lower bound on the competitiveness.

Second, we study the extended problem investigated by Deng and Hou that includes routing as part of the solution. We have also shown that with the fastest path routing, our greedy scheduling algorithm remains O(PM)-competitive. We have also shown (PM/2 – 1) is a lower bound on the competitiveness, proving that the greedy algorithm is also asymptotical optimal.

Third, we propose an improved online scheduling algorithm that not only achieves asymptotical optimal competitiveness, but also can offer better competitiveness when Cmin is increasing, where Cmin is the minimum capacity in the network.

Finally, we report our simulation results. Simulations show that not only the proposed algorithms achieve theoretical optimal bounds, but also practically outperform the previous MKS and DH online algorithms.

报告人简介：

Dr. Xiaojun Shen received his bachelor degree in computer science in 1968 from Tsinghua University, and master degree in computer science in 1982 from Nanjing University of Science and Technology, China. He came to USA and received his Ph.D degree in computer science in 1989 from University of Illinois, Urbana-Champaign. He became a faculty member in the School of Computing and Engineering at UMKC since 1989. He has done research work in the fields of Discrete Mathematics, Computational Geometry, Parallel Processing, and Computer Networking. In addition to 30 conference papers, he has published about 50 papers in prestigious journals including SIAM J. Computing, Discrete Mathematics, Discrete Applied Mathematics, IEEE/ACM Transactions on Networking, IEEE Transactions on Computers, IEEE Transactions on Communications, IEEE Transactions on Circuits and systems, Journal of Parallel and Distributed Computing, IEEE Journal on Selected Areas in Communications, Theoretical Computer Science, Computer Networks, etc. He has also published a book, Essentials of Computer Algorithms (in Chinese). His current research focuses on packet scheduling for wired and wireless networks.

计算机网络和信息集成教育部重点实验室（东南大学）