Data structures and algorithms for packet forwarding and classification

  Speaker 

  :

Sartaj Sahni, University of Florida, USA

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.

  Abstract

 :

Packet forwarding and classification at Internet speed is a challenging task. 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 and hybrid shape shifting tries. Hardware assisted solutions such as Ternary Content Addressable Memories also are reviewed  http://www.cise.ufl.edu/~sahni