IP route lookups as string matching

被引：10

作者：

Donnelly, A ^{[1
]}

Deegan, T ^{[1
]}

机构：

[1] Univ Cambridge, Comp Lab, Cambridge CB2 3QG, England

来源：

25TH ANNUAL IEEE CONFERENCE ON LOCAL COMPUTER NETWORKS - PROCEEDINGS | 2000年

关键词：

longest prefix matches; finite state automata;

D O I：

10.1109/LCN.2000.891104

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：589 / 595

页数：7

共 11 条

[1]

[Anonymous], 1998, P ACM SIGCOMM 98

[2]

BAYS J, 1974, THESIS U OKLAHOMA

[3]

Brzozowski J., 1962, MATH THEORY AUTOMATA, V12, P529

[4]

Degermark M., 1997, Computer Communication Review, V27, P3, DOI 10.1145/263109.263133

[5]

Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation

[6]

LAKHSMAN TV, 1998, COMPUT COMMUN, V28, P203

[7] A LOWER BOUND ON THE COMPLEXITY OF THE UNION-SPLIT-FIND PROBLEM [J].

MEHLHORN, K ;

NAHER, S ;

ALT, H .

SIAM JOURNAL ON COMPUTING, 1988, 17 (06) :1093-1102

[8]

NILSSON S, 1998, INT C BROADB COMM

[9] Fast address lookups using controlled prefix expansion [J].

Srinivasan, V ;

Varghese, G .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1999, 17 (01) :1-40

[10]

Waldvogel M., 1997, Computer Communication Review, V27, P25, DOI 10.1145/263109.263136

← 1 2 →