IP Route Lookups as String Matching
Austin Donnelly and Tim Deegan
Proc. IEEE LCN 2000, pp. 598-585, November 2000.
[PS]

Abstract

An IP route lookup can be considered as a string matching problem on the destination address. Finite State Automata (FSA) are a flexible and efficient 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-prefix match problem.

[PS]

$Id: lcn2000.html,v 1.2 2007/02/13 16:37:26 tjd Exp $
This page is valid HTML 4.01 and best viewed with any browser.
Tim Deegan