Optimization in high-performance routers and switches

Strictly Nonblocking Network (SNB) and Wide Sense Nonblocking Network (WSNB) have long been recognized as interconnect networks to connect any idle input to any unconnected output of circuit switching network. While finding a low cost and realizable SNB or WSNB remains to be a theoretical challenge and scientific pursuit, we proposed an alternative network structure, Pyramid Benes(PB) network, which only has O( NlogN) cost and can be used as a low-cost SNB network in practice for circuit switching applications.;Internet Protocol (IP) lookup engine is used for finding the longest matching prefix of the destination IP address of a packet. Ternary Content-Address Memory (TCAM) has the capability of achieving single clock cycle lookup of prefix with arbitrary length by storing the "don't-care" state. TCAM has already been used to implement IP-lookup accelerator for IP forwarding. Optimizing the TCAM-Based IP Lookup Engine is a key factor to improve the performance of the high-end TCAM router. We prove that an optimized TCAM-Based IP Lookup Engine can improve the performance of the system without increasing the cost and complexity of the system.;Based on the optimized TCAM-Based IP Lookup Engine, a series of schemes have been studied on how to improve performance of the IP Lookup Engine without using more hardware resources, and how to design a engine, given a specific performance requirement. These schemes construct a wide-range solution space for TCAM-based IP lookup engines. TCAM based search engine is popularly used not only as IP lookup engine, but also as security Access Lists (ACLs) engine, Quality of Service (QoS) classification engine, and Layer-4 (L4) redirect service engine. TCAM based search engine is a pipelined architecture by itself, while it is used in several stages in the routing system. A hazard in TCAM based search engine can seriously reduce the performance from the ideal speedup gained by pipelining. A token based pipeline scheme is designed to eliminate the unnecessary hazard and achieve near-optimal speed with almost no additional hardware overhead.