沈孝钧教授的报告定于六月二十六日周四下午两点，地点机电学科楼报告厅（E楼机械学院四楼），欢迎各位老师、同学参加。

A Nearly Optimal Packet Scheduling Algorithm for

Input Queued Switches with Deadline Guarantees

Abstract

In order to guarantee quality of service, we consider how to schedule a set of packets buffered at input side of a switch such that maximum number of packets can be transmitted to their destined output ports before their deadlines. This problem has been proven NP-complete if three or more classes (distinct deadlines) are present in the set. Traditionally, the only way to deal with this problem is to use EDF (Earliest Deadline First) or similar methods.  In 2007, we proposed the first non-EDF method that can produce a much higher throughput by repeatedly applying an optimal algorithm for two classes. Recently, a mush high throughput has been reached by a new algorithm which does not use the deadlines as the priorities. This new algorithm provides approximation ratio 2 and superb average performance as well. It would provide a practical solution to the historically difficult problem. A related paper will appear in IEEE Transactions on Computers.

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 more than 40 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, 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.

著名的美籍华裔计算机科学家Xiaojun Shen（沈孝钧）博士是美国密苏里大学堪薩斯城分校的终身教授。他1968年毕业于清华大学，1982年取得华东工程学院（现南京理工大学）的计算机科学的硕士学位，1989年获得Illinois大学Urbana-Champaign分校的计算机科学的博士学位。

他的研究方向包括离散数学、计算几何、并行处理、计算机网络，目前关注分布式计算和传感器网络。他的研究成果主要发表在 “IEEE Transactions on Computers”, “IEEE/ACM Transactions on Networking”, “IEEE Transactions on Communications”, “IEEE Transactions on Circuits and systems”, “SIAM Journal on Computing”, “Discrete Mathematics”, “Discrete Applied Mathematics”, “Journal of Parallel and Distributed Computing”等刊物。

鉴于其成果的广泛影响，他多次应邀担任计算机科学国际学术会议的chair或session chair，并多次应邀在加拿大、澳大利亚等国的高校及我国多所985、211高校、中国科学院研究生院和国家研究机构讲学。