Reconfigurable finite-state machine based IP lookup engine for high-speed router

Author

Desai, Madhav ; Gupta, Ritu ; Karandikar, Abhay ; Saxena, Kshitiz ; Samant, Vinayak

Author_Institution

Dept. of Electr. Eng., Indian Inst. of Technol., Mumbai, India

Volume

21

Issue

4

fYear

2003

fDate

5/1/2003 12:00:00 AM

Firstpage

501

Lastpage

512

Abstract

Internet protocol (IP) address lookup is one of the major performance bottlenecks in high-end routers. This paper presents an architecture for an IP address lookup engine based on programmable finite-state machines (FSMs). The IP address lookup problem can be translated into the implementation of a large FSM. Our hardware engine is then used to implement this FSM using a structured approach, in which the large FSM is broken down into a set of smaller FSMs which are then mapped into reconfigurable hardware blocks. The design of our hardware engine is based on a regular and well structured architecture, which is easy to scale. Our simulation results demonstrate that the FSM based architecture can easily scale to wire speed performance at OC-192 rates. Unlike previous approaches, the performance of our architecture is not constrained by memory bandwidth and is, therefore, in principle scalable with very large scale integration technology.

Keywords

VLSI; cache storage; finite state machines; programmable circuits; reconfigurable architectures; table lookup; telecommunication network routing; transport protocols; FSM; FSM based architecture; IP lookup engine; Internet protocol address lookup; OC-192 rates; VLSI technology; architecture performance; cache storage; hardware engine; high-speed router; memory bandwidth; programmable finite-state machines; reconfigurable finite-state machine; reconfigurable hardware blocks; simulation results; software model; structured approach; very large scale integration technology; wire speed performance; Aggregates; Bandwidth; Hardware; Internet; Laboratories; Protocols; Routing; Search engines; Very large scale integration; Wire;

fLanguage

English

Journal_Title

Selected Areas in Communications, IEEE Journal on

Publisher

ieee

ISSN

0733-8716

Type

jour

DOI

10.1109/JSAC.2003.810498

Filename

1197696