Skip to main content

Data Structures and Algorithms for Packet Forwarding and Classification

Dr Sartaj Sahni
University of
Talk:   Friday, March 24, 2006
Time: 11:00am-12:00pm
Place: 1225 Engineering 

Host: A. Jain

Abstract: We review the data structures that have been proposed for the forwarding and classification of Internet packets. Data structures for both one-dimensional and multidimensional classification as well as for static and dynamic rule tables are reviewed. Sample structures include multibit one- and two-dimensional tries, binary trees on binary trees, and list of hash tables.

Biography: Sartaj Sahni is a Distinguished Professor and Chair of Computer and Information Sciences and Engineering at the University of Florida. He is also a member of the European Academy of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and a Distinguished Alumnus of the Indian Institute of Technology, Kanpur. In 1997, he was awarded the IEEE Computer Society Taylor L. Booth Education Award ``for contributions to Computer Science and Engineering education in the areas of data structures, algorithms, and parallel algorithms'', and in 2003, he was awarded the IEEE Computer Society W. Wallace McDowell Award ``for contributions to the theory of NP-hard and NP-complete problems''. Dr. Sahni was awarded the 2003 ACM Karl Karlstrom Outstanding Educator Award for ``outstanding contributions to computing education through inspired teaching, development of courses and curricula for distance education, contributions to professional societies, and authoring significant textbooks in several areas including discrete mathematics, data structures, algorithms, and parallel and distributed computing.'' Dr. Sahni received his B.Tech. (Electrical Engineering) degree from the Indian Institute of Technology, Kanpur, and the M.S. and Ph.D. degrees in Computer Science from Cornell University. Dr. Sahni has published over two hundred and eighty research papers and written 15 texts. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, design automation, and medical algorithms.


Dr. Sahni is a co-editor-in-chief of the Journal of Parallel and Distributed Computing, a managing editor of the International Journal of Foundations of Computer Science, and a member of the editorial boards of Computer Systems: Science and Engineering, International Journal of High Performance Computing and Networking, International Journal of Distributed Sensor Networks and Parallel Processing Letters. He has served as program committee chair, general chair, and been a keynote speaker at many conferences. Dr. Sahni has served on several NSF and NIH panels and he has been involved as an external evaluator of several Computer Science and Engineering departments.