Loading...
Please wait, while we are loading the content...
Similar Documents
Towards Efficient Packet Classification Algorithms and Architectures
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ahmed, Omar |
| Copyright Year | 2013 |
| Abstract | Towards Efficient Packet Classification Algorithms and Arch itectures Omar Ahmed University of Guelph, 2013 Advisor: Professor Shawki Areibi Packet classification plays an important role in next genera tion networks. Packet classification is important to fulfill the requirements for many applic ations including firewalls, multimedia services, intrusion detection services, and differentiat ed services to name just a few. Hardware solutions such as CAM/TCAM do not scale well in space. Curren t software-based packet classification algorithms exhibit relatively poor performance, p rompting many researchers to concentrate on novel frameworks and architectures that employ bot h hardware and software components. In this thesis we propose two novel algorithms, PacketClassification withIncrementalUpdate (PCIU) andGroupBasedSearch packet classification Algorithm (GBSA), that are scalable and demonstrate excellent results in terms of preprocessing an d cl ssification. The PCIU algorithm is an innovative and efficient packet clas sification algorithm with a unique incremental update capability that demonstrates po werful results and is accessible for many different tasks and clients. The algorithm was further improved and made more available for a variety of applications through its implementation in hardware. Four such implementations are detailed and discussed in this thesis. A hardware accele rator based on an ESL approach, using Handel-C, resulted in a 22x faster classification than a pure software implementation running on a state of the art Xeon processor. An ASIP implementation ach ieved on average a 21x quicker classification. We also propose another novel algorithm, GBSA, for packet cl assification that is scalable, fast and efficient. On average the algorithm consumes 0.4 MB of mem ory for a 10k rule set. In the worst case scenario, the classification time per packet is 2 μs, and the pre-processing speed is 3M Rule/sec, based on a CPU operating at 3.4 GHz. The proposed al gorithm was evaluated and compared to state-of-the-art techniques, such as RFC, HiCut, T uple, and PCIU, using several standard benchmarks. The obtained results indicate that GBSA outper forms these algorithms in terms of speed, memory usage and pre-processing time. The algorithm , furthermore, was improved and made more accessible for a variety of applications through i mplementation in hardware. Three approaches using this algorithm are detailed and discussed in this thesis. The first approach was implemented using an Application Specific Instruction Proc essor (ASIP), while the others were pure RTL implementations using two different ESL flows (Impu lse-C and Handel-C). The GBSA ASIP implementation achieved, on average, a 18x faster runn ing speed than a pure software implementation operating on a Xeon processor. Conversely, th hardware accelerators (based on the ESL approaches) resulted in 9x faster processing. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://atrium.lib.uoguelph.ca/xmlui/bitstream/handle/10214/7406/Ahmed_Omar_201308_Phd.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
