Your Search Results

Use this resource - and many more! - in your textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

Novel disjoint graph based algorithm for multi-field range-based packet classification

By: Krishnamurthy, A.; Tiyan Tang; Yun Zhang; Yuke Wang; Bou-Diab, B.; Damm, G.;

2004 / IEEE / 0-7803-8533-0

Description

This item was taken from the IEEE Conference ' Novel disjoint graph based algorithm for multi-field range-based packet classification ' Packet classification is necessary for flow-based network services in Internet routers, such as NAPT, IPsec, ACL, etc. The range-based packet classification function maps input packets to the highest-priority matching rule in a given rule set specified by ranges (P. Gupta and N. McKeown, August 1999, March-April 2001). For instance, multi-field range-based packet classification maps IP packets to security policy rules in an IPsec gateway. The FIS trees based packet classification algorithm has been proposed as a software implementation option of this function. In this paper, we present a novel disjoint graph based algorithm for multi-field range-based packet classification. The novel algorithm constructs a disjoint graph using elementary interval trees and disjoint interval trees for a given rule set, where only a single path traversal is required during a search to classify a packet. Experimental results show that the disjoint graph based packet classification algorithm significantly outperforms the FIS trees based solution. In a network processor implementation with an input rule set of 700 rules, the disjoint graph based packet classification algorithm requires only 45% of the search time, 69% of the data structure buildup time, and 47% of the memory storage of the FIS trees based solution.