To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
A Novel Data Structure for String Matching Applicable in Network Processing |
|
Author |
Nasser Yazdani, Hossein Mohammadi |
| Citation |
Vol. 6 No. 7 pp. 194-203 |
|
Abstract |
We address prefix matching problems which constitute the building block of some applications in the computer realm and related area. It is assumed there are strings of an alphabet which are ordered. The data strings can have different lengths and some of them can be prefixes of others. A well known application of prefix matching is layer 3 IP switching in which routers forward an IP packet by checking its destination address and finding the longest matching prefix from a database. In layer 4 switching, the source and destination addresses are used to classify packets for differentiated service and Quality of Services (QoS). We believe the fundamental issue preventing applying the usual tree structures such as B-tree to the prefix matching problem is the lack of a systematic method to compare and sort strings of different lengths. We introduce a simple scheme for comparing and sorting strings of different lengths first. Then, since the usual data structures can not be applied directly to the sorted strings, we manipulate data and tune the tree structures. We propose twp tree structures and devise all related procedures to build trees and process queries. A binary prefix tree is introduced and which can be extended to static and dynamic m_way prefix trees. |
|
Keywords |
Prefix tree, IP Lookup, Packet Classification |
|
URL |
