Balaji Prabhakar

Algorithms On-chip

Customized hardware algorithms are an imperative in network routers and switches the one way to get high operatiing speeds. However, the algorithms cannot be ornate because a core Internet router is not computationally resource-rich. Designing for the imperative under the constraint is, therefore, quite challenging and exciting. This talk describes some of the challenges both for theory and for practice. We describe the design of algorithms for bandwidth partitioning, address lookup and packet classification. We aim to convey that randomization is a very useful trick, and that simplicity is crucial for commercial implementation.