A network processor unit (NPU) is a programmable device that consists of several hardware accelerators for wire-speed networking operations. One of the most important functional units in an NPU is packet classification unit (PCU) that classifies data packets based on single or multiple fields of packet header or contents in payload data. Large number of tasks in computer communication require packet classification. Network packet classification requires two types of matching techniques: (i) exact. and (ii) inexact match. There are two solutions for exact match: (i) sequential and (ii) parallel solutions. Inexact match can be of two types: (i) Longest prefix match and (ii) Best match. This dissertation talks about these four techniques required for the PCU.
For the sequential solution. we propose a string search algorithm that requires reduced time complexity. It also requires a small amount of memory. arid shows better performance than any other related algorithms as proved by numerical analysis and extensive computer simulations.
For parallel solution. we present a systematic technique for expressing the string search algorithm as a regular iterative expression to explore all possible processor arrays. The technique allows some of the algorithm variables to be pipelined while others are broadcast over system-wide buses. Nine possible processor array structures are obtained and analyzed in terms of speed, area. power. and I/O timing requirements. The proposed designs exhibit optimum speed and area complexities.
The parallel solution requires an embedding technique that embeds a source processor array onto a target processor array having smaller number of processing elements (PE) to meet the hardware resource constraint. We propose a. novel embed-ding technique. Through numerical analysis and extensive computer simulation. it is proved that the performance of the target array shows the same performance as the source array.
For Longest prefix match (LPM), we propose a novel variable-stride multi-bit trie data structure for IP-lookup table to assist. fast IP-lookup and fast lookup table update. In this dissertation. we first explicitly elaborate the solution of a problem in expanding IP (internet protocol) addresses. Through extensive computer simulation on several routing tables. it is proved that our proposed algorithm shows better performance (lookup and update time) than existing algorithms. However. our proposed technique requires larger memory than others. But the memory requirement is quite acceptable considering the current memory availability and price.
We propose a novel Best Match technique required to detect best-matched English words of obfuscated spam words. We have used a non-deterministic finite automaton (NFA) to build the English dictionary. We have used dynamic programming with state pruning to detect the best-matched word of an obfuscated spam word in the NFA. We have done extensive numerical simulations to prove the accuracy of our proposed system. Our system can detect best-matched words of the words obfuscated by spammers using five different techniques: insertion, deletion. substitution. trans-pose. and word boundary. Upto our knowledge. no other system can deal with all these obfuscating techniques so quickly as ours.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/2111 |
| Date | 26 January 2010 |
| Creators | Rafiq, A. N. M. Ehtesham |
| Contributors | Gebali, Fayez |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0016 seconds