Routers are key building blocks in networks. They need to cope with high data rates in the range of multiple gigabit per second that are flowing through them. Therefore, specifically performance critical functions should be implemented in dedicated hardware units in order to speed up the forwarding task. These units can be embedded within regular workstations or into dedicated router architectures. This paper we address one of the most performance critical components of a router, the routing table and its access and search mechanisms. Earlier work has shown that this is more critical with respect to the resulting performance than IP processing itself. A simple but efficient organization of the routing table using binary trees and off-the-shelf SRAMs is presented together with a suited search algorithm.
展开▼
