Advanced search and sort architectures for network processing

The research presented in this thesis focuses on high-speed search and sort hardware architectures developed to accelerate key fu~ctions in networks. Specific architectures have been developed and implemented for a tag sort/retrieve circuit, used in a fair queuing scheduler, in addition to a content addressable memory (CAM) used for IP address lookup. A detailed investigation highlights the reasons for using fair queuing in preference to other algorithms in order to deliver Quality of Service (QoS). It is shown that sorting finishing tags is a crucial process in fair queuing. A fundamental analysis oftag retrieval identifies two alternative 'search' and 'sort' models of operation. It is furthermore proven that the sort model is preferable. Further research investigating a range of lookup functions demonstrates that a multi-bit trie approach offers op~imum performance and conforms to the sort model. A scalable, modular architecture for the circuit is presented and results are shown for a 130nm standard cell silicon implementation. The issue ofIP address lookup has been clearly identified as a process of increasing significance, due to constraints such as increasing connection speeds and table size as well as changing traffic profiles. A critical analysis of recent specialised hardware designs for address lookup reveal a number ofimportant design factors that must be taken into account, such as routing updates, speed of search and update, and prefix distribution. The investigation highlights ternary CAMs as performing well against these criteria. Different CAM architectures have been developed and implemented based on the resources available on modern FPGAs. These are based on registers, LUTs and embedded RAM blocks. The results show these designs can be suitable for a range ofsmall to medium sized applications, and their use can extend beyond address lookup into other areas of networking such as packet classification and network security.EThOS - Electronic Theses Online ServiceGBUnited Kingdo