Efficient and scalable hardware techniques for edge and core routers

The growth of the Internet continues as its usage continues to pervade everyday life, significantly impacting individuals, businesses, industries, and academia. Studies have shown that the both the traffic and the number of hosts on the Internet have been, and are expected to continue, growing exponentially. In addition, security concerns and innovative applications continue to add to the functionality demanded by the Internet. The operation of the Internet is fundamentally facilitated by routers, or packet switches. The growth trends in size, speed and functionality translate into opportunities and challenges in the design of future-generation routers. Edge-routers perform elaborate packet processing, but with less rigid performance guarantees because they are usually lower in cost. On the other hand, core-routers typically perform IP-lookup on the packets and are expected to do so with worst-case guarantees, albeit at higher system cost. Furthermore, advanced packet classification and a possible transition to IPv6 require longest prefix matching (LPM) on keys significantly longer than IPv4, and there is need for an efficient LPM scheme for arbitrarily long keys. In edge-routers, elaborate packet processing leads to high variation in processing times across packets. This variation and the cost and complexity considerations for edge-routers preclude a worst-case design paradigm. The packet-buffer design in edge-routers offers opportunities for average-case improvements, which are currently unexploited. As the first contribution of my dissertation, I propose and quantitatively evaluate a number of opportunistic techniques for improving performance of network-processor-based edge-routers by efficiently utilizing the memory bandwidth of the packet-buffer. In core-routers, worst-case guarantees and high line-rates necessitate IP-lookup to be performed on custom hardware. Yet, even with custom hardware, the growth trends of the Internet are beginning to outpace the technology scaling of hardware components such as memory, giving rise to scalability challenges. A truly scalable IP-lookup scheme must address five challenges of scalability, namely: routing-table size, lookup throughput, implementation cost, power dissipation, and routing-table update cost. However, when subjected to the scaling requirements of tomorrow\u27s routers, none of the previously-proposed IP-lookup schemes satisfy all the five scalability requirements. As the second contribution of my dissertation, I propose Scalable Dynamic Pipelining, a novel IP-lookup scheme which is the first to scale well in all five factors with worst-case guarantees. (Abstract shortened by UMI.