IP Route Lookups as String Matching - Donnelly, Austin; Deegan, Tim (IEEE LCN'2000, 2000)
An IP route lookup can be considered as a string matching problem on the destination address. Finite State Automata (FSA) are a ﬂexible and efﬁcient way to match strings. This paper describes how a routing table can be encoded as an FSA and how, through a process of state reduction, we can obtain an optimal representation. This gives insights into the basic properties of the longest-preﬁx match problem.