PhD Defense and Thesis of Pankaj Gupta

Algorithms for Routing Lookups and Packet Classification

With margins adjusted for two-sided printing: Postscript (2.1 MB), PDF (0.97 MB).
With margins adjusted for one-sided printing: Postscript (2.1 MB), PDF (0.97 MB).

Initial pages (24 pages): Postscript (211 KB), PDF (69 KB).
Chapter 1 (30 pages): Introduction. Postscript (291 KB), PDF (98 KB).
Chapter 2 (48 pages): An Algorithm for Performing Routing Lookups in Hardware. Postscript (308 KB), PDF (160 KB).
Chapter 3 (26 pages): Minimum Average and Bounded Worst-case Routing Lookup Time on Binary Search Trees. Postscript (689 KB), PDF (722 KB).
Chapter 4 (56 pages): Recursive Flow Classification: An Algorithm for Packet Classification on Multiple Fields. Postscript (545 KB), PDF (238 KB).
Chapter 5 (16 pages): Hierarchical Intelligent Cuttings: A Dynamic Multi-dimensional Packet Classification Algorithm. Postscript (150 KB), PDF (56 KB).
Chapter 6 (4 pages): Future Directions. Postscript (60 KB), PDF (10 KB).
Appendix A (2 pages): Postscript (70 KB), PDF (9 KB).
Appendix B (2 pages): Postscript (66 KB), PDF (10 KB).
Bibliography (14 pages): Postscript (106 KB), PDF (34 KB).
Ending shloka (1 page): Postscript (120 KB), PDF (26 KB).

Last Updated December 07, 2000
Pankaj Gupta
pankaj@cs.stanford.edu