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.
Novel disjoint graph based algorithm for multi-field range-based packet classification
2004 / IEEE / 0-7803-8533-0
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.
Network Processor Implementation
Disjoint Graph Based Algorithm
Multifield Range-based Packet Classification
Flow-based Network Services
Security Policy Rules
Fis Trees Based Packet Classification Algorithm
Fat Inverted Segment
Software Implementation Option
Elementary Interval Trees
Disjoint Interval Trees
Classification Tree Analysis
Tree Data Structures
Web And Internet Services
Network Address Translation
Telecommunication Network Routing
Highest-priority Matching Rule