Data Structures and Algorithms for Packet Forwarding and Classification
Dr Sartaj Sahni
University of
Talk:
Time:
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.