Packet Classification
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Wifi
Active In SP
**

Posts: 158
Joined: Oct 2010
#1
28-10-2010, 08:46 AM


Packet Classification Algorithms
Presented by
Dains Raj Antony
M1 CSE
College Of Engineering, Trivandrum


.ppt   Packet ClassificationAlgorithms.ppt (Size: 850.5 KB / Downloads: 83)

What this seminar and presentation is about:
Algorithms and techniques that a flow-aware router uses to classify packets into flows (packet classification)

What is a Flow?
All the packets sharing common header characterstics
Eg: All packets flowing between two specific IP addresses
flow = (src-IP-address, dst-IP-address), or a flow = (dst-IP-prefix, protocol) etc

Flow-aware vs Flow-unaware Routers
Flow-aware router: keeps track of flows and perform similar processing on packets in a flow
Flow-unaware router (packet-by-packet router): treats each incoming packet individually

Examples of special processing
Filtering packets for security reasons
Delivering packets according to a pre-agreed delay guarantee
Treating high priority packets preferentially
Maintaining statistics on the number of packets sent by various routers

Special Processing Requires Identification of Flows

All packets of a flow obey a pre-defined rule and are processed similarly by the router
E.g. a flow = (src-IP-address, dst-IP-address), or a flow = (dst-IP-prefix, protocol) etc.
Router needs to identify the flow of every incoming packet and then perform appropriate special processing

Why Flow-aware Router?
ISPs want to provide differentiated services
Routers require additional mechanisms: admission control, resource reservation, per-flow queueing, fair scheduling etc.
capability to distinguish and isolate traffic belonging to different flows based on negotiated service agreements

Need for Differentiated Services
Multi-field Packet Classification
Packet Header Fields for Classification

Flow-aware Router: Basic Architectural Components
Routing, resource reservation, admission control, SLAs
Routing lookup
Packet classification
Special processing
Switching
Scheduling
Datapath:
per-packet
processing

Packet Classification

Metrics for Classification Algorithms
Speed
Storage requirements
Low update time
Ability to handle large classifiers
Flexibility in implementation
Low preprocessing time
Scalability in the number of header fields
Flexibility in rule specification

Example Classifier
Linear Search
Keep prefixes in a linked list
O(N) storage, O(N) lookup time, O(1) update complexity
Improve average time by keeping linked list sorted in order of prefix lengths

Recursive Flow Classification
Observations:
Difficult to achieve both high classification rate and reasonable storage in the worst case
Real classifiers exhibit structure and redundancy
A practical scheme could exploit this structure and redundancy

Recursive Flow Classification
One-step
Multi-step

Source L3 Address
Destination L3 Address
L4 protocol and flags
Source L4 port
Destination L4 port
Type of Service

Ternary Content Adressable Memory
Need for higher processing capacity
Can be used for multi-diamensional classification
Fully associative memory:
compares input string with all the entries in parallel

Ternary CAMs
Advantages

Suitable for multiple fields
Fast: 16-20 ns (50-66 Mpps)
Simple to understand
Disadvantages

Inflexible:
Density: largest available in 2000 is 32K x 128 (but can be cascaded)
Management software, and on-chip logic:
Power: 5-8 W
Incremental updates: slow
DRAM-based CAMs: higher density but soft-error is a problem
Cost: $30-$160 for 1Mb

Conclusion

Linear search is simple but poor at scaling.
Heirarchical trie provides good worst case query time.
Set pruning tries has fast retrieval at the cost of storage.
RFC is suitable for small set of rules.
TCAM is simple but very costly.

References
[1] Pankaj Gupta & Nick Mckeown, "Algorithms for Packet Classification",Computer Systems Laboratory, Stanford University Stanford, CA.
[2]Pankaj Gupta and Nick McKeown , "Packet Classification using Hierarchical Intelligent Cuttings" Computer Systems Laboratory, Stanford.
Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
Reply
Wifi
Active In SP
**

Posts: 158
Joined: Oct 2010
#2
28-10-2010, 09:48 PM

Packet classification algorithms


.doc   Packet Classification algorithms.doc (Size: 893 KB / Downloads: 65)
Introduction
The process of categorizing packets into flows in an internet router is called packet classification.Packet classification is needed for non best-effort services, such as firewalls and quality of service, service s that require the capability to distinguish and isolate traffic in different flows for suitable processing. Packet classification can be done on a single field or multiple fields. There are a variety of algorithms proposed for packet classification. They can be broadly categorized as basic data structures / search algorithms, geometric algorithms, heuristic algorithms and hardware specific algorithms. Flows are specified by rules applied to incoming packets. We call a collection of rules a classifier. Each rule specifies a flow that a packet may belong to based on some criteria.
Algorithm
Algorithms and techniques that a flow-aware router uses to classify packets into flows (packet classification. The Flow-aware router keeps track of flows and perform similar processing on packets in a flow . While flow-unaware router (packet-by-packet router) treats each incoming packet individually.
Packet classification can be done on a single field or on multiple fields . Fields used for classification can be Data Link Layer (Layer 2) Source, Destination address, Network Layer (Layer 3) Source, Destination Address, Transport Layer (layer 4) Source, Destination Port number and Layer Protocol.

REQUIREMENTS OF PACKET CLASSIFICATION ALGORITHM
The requirements of packet classification can vary depending up on the application and the location where the classification is performed. The classification should be done at the line speeds with minimum time required for classification and minimum memory .


The requirements can be listed as under:
• Number of rules to be supported: Number of rules for PC can vary depending on applications such as firewalls, backbone router etc.
• Number of fields used: PC applications differ on basis of the fields in IP header used for classification.
• Nature of rules: The rules are about the prefix mask or general masks used on destination IP address.
• Updating the set of rules: The PC should be adaptable changes in the rules due to route or policy changes without sacrificing access performance
• Worst case Vs average case : For performance of PC, focusing should be done on worst case than average case.
All these algorithms can be categorized in four classes as under:
A. Basic Data Structures: The algorithms based on data structures are Linear Search, Caching, Hierarchical Tries, Set Pruning Tries, etc.
B. Geometry Based: The algorithms based on geometry are Grid of Tries, Area Based Quad Tree , Fat Inverted Segment Tree, etc.
C. Heuristic: The algorithms based on heuristic category are Recursive Flow Classification, Hierarchical Intelligent Cutting , Tuple Space Search, etc.
D. Hardware: The algorithms based on hardware category are Ternary CAM, Bitmap-Intersection, etc.
Basic Data Structure/ Search Algorithms:
A.Linear Search
Prefixes are kept in a linked list.Every arriving packet is compared with each rule sequentially until a rule is found that matches all required fields i.e. each rule is evaluated sequentially until a rule is found that matches all the relevant fields in the packet header.O(N) storage, O(N) lookup time, O(1) update complexity Improve average time by keeping linked list sorted in order of prefix lengths
Hierarchical Tries:
A radix trie is a binary tree with labeled branches and traversed during search operations using individual bits of the search key. The left branch is labeled zero and right branch is labeled one. A node represents a bit string formed by concatenating labels of all branches in the path from the root node. A radix trie is a binary tree with labeled branches and traversed during search operations using individual bits of the search key. The left branch is labeled zero and right branch is labeled one. A node represents a bit string formed by concatenating labels of all branches in the path fromthe root node


Set-pruning Tries
The data structure query time is reduced due to elimination of need to do recursive traversals. This is achieved by replicating rules at several nodes in the data structures. A set pruning trie has rules in (d-l) dimensional trie linked to a prefix p in FI trie are pushed down. This pushing down of prefixes is carried out recursively on the remaining (d-l ) dimensions in the set pruning trie data structure. The query algorithm for an incoming packet (v.. V2, ... ,Vd) only traverse the Fl-trie to find the longest matching prefix of VI, follow its next-trie pointer (if non null), traverse the F2-trie to find the longest matching prefix of v1 and so on for all dimensions . B. Geometry Based Algorithms:
Grid-of- Tries:
It is an optimization of hierarchical trie data strucure for 2 dimensions. Itavoids memory blowup of set pruning tries by allocating a rule to only one trie node as in hierarchical tries but still achieves O(W) query time by using precomputation and storing a switch pointer in some trie nodes.


Recursive Flow Classification

Classifying a packet can be viewed as mapping S bits in the packet header to T bits of class lD (an identifier denoting the rule or action) where, T =log N, T« S in a manner dictated by the classifier rules. A simple and fast, but unrealistic way of doing this mapping is to precompute the value of class lD for each of the 2s different packet header values. It is difficult to achieve both high classification rate and reasonable storage in the worst case. Real classifiers exhibit structure and redundancy. A practical scheme could exploit this structure and redundancy.
The algorithm operates as follows:
• In the first phase (phase 0), d fields of the packet header arc split up into multiple chunks that are used to index into multiple memories in parallel.
• In subsequent phases, the index into each memory is formed by combining the results of the lookups fromearlier phases.
• After successive combination and reduction, one result is received from the memory lookup, in the final phase.Because of the way the memory contents have been precomputed, this value corresponds to the class ID of the packet .




Hierarchical Intelligent Cuttings

HiCuts build a decision tree data structure such that the internal nodes contain suitable information to guide the classification algorithm, and the external nodes (i.e., the leaves of the tree) store a small number of rules. On receiving an incoming packet, the classification algorithm traverses the decision tree to arrive at a leaf node.The algorithm then searches the rules stored at this leaf node sequentially to determine the best matching rule. The shape characteristics of the decision tree such as its depth, the degree of each node and the local search decision to be made by the query algorithm at each node, are chosen while preprocessing the classifier and depend on the characteristics of the classifier.


HiCuts algorithm in d dimensions can be formulated as follows:
Each internal node, v, of the tree represents a portion of the geometric search space and the root node represents the Perhaps an algorithm can exploit this structure A heuristic hybrid scheme.
HiCuts: Pros and Cons
Advantages
 Exploits structure of real-life classifiers
 Adapts data structure
 Suitable for multiple fields
 Supports incremental updates
Disadvantages
 Depends on structure of classifiers
 Large pre-processing time
 Large worst-case storage requirements
TCAM
Hardware implementation comes from the need for higher packet processing capacity that is typically not obtainable by software implementations. TCAMs can be used for multi-dimensional classification with each row of the TCAM memory array to be wider than 32 bits, the required width depends on the number of fields used for classification , and usually varies between 128 and 256 bits depending on the application.




Advantages
 Suitable for multiple fields
 Fast: 16-20 ns (50-66 Mpps)
 Simple to understand
Disadvantages
 Inflexible: range-to-prefix blowup
 Density: largest available in 2000 is 32K x 128 (but can be cascaded)
 Management software, and on-chip logic: non-trivial complexity
 Power: 5-8 W
 Incremental updates: slow
 DRAM-based CAMs: higher density but soft-error is a problem



CONCLUSION

Linear search is a simple algorithm but poor at scaling. Hierarchical trie provides a good worst case query time at the expense of storage. Set pruning tries has reduced query time and has fast retrieval at the cost of storage. Grid of tries rebuilds each update and can be used for last 2 dimensions of a multidimensional hierarchical trie. RFC is suitable for small set of rules, uses preprocessing and large storage space. In HiCuts parameters can be tuned to trade-off query time against storage requirements. TCAM is simple but very costly and is good for small classifiers .


.doc   Packet Classification algorithms.doc (Size: 893 KB / Downloads: 65)
Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
Reply
summer project pal
Active In SP
**

Posts: 308
Joined: Jan 2011
#3
29-01-2011, 07:20 PM

Packet Classi cation Algorithms


Contents
1 Introduction 5
2 Requirement of packet classi cation 7
3 Speci cations of classi cation 8
4 Classi cation algorithms 9
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Basic Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2.1 Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2.2 Hierarchical Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.3 Set-pruning tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Geometric algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3.1 Grid-of-tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4.1 Recursive Flow Classi cation (RFC) . . . . . . . . . . . . . . . . . . . . 13
4.4.2 Hierarchical Intelligent Cuttings (HiCuts) . . . . . . . . . . . . . . . . . 14
4.5 Hardware-based algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5.1 Ternary CAMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.6 Performance metrics for classi cation algorithms . . . . . . . . . . . . . . . . . . 16
5 Conclusion 17
3
Abstract
The process of categorizing packets into
ows in an Internet router is called packet classi -
cation. All packets belonging to the same
ow obey a pre-de ned rule and are processed in a
similar manner by the router. For example, all packets with the same source and destination
IP addresses may be de ned to form a
ow. Packet classi cation is needed for non \best-
e ort"services, such as re walls and quality of service; services that require the capability to
distinguish and isolate trac in di erent
ows for suitable processing. In general, packet clas-
si cation on multiple elds is a dicult problem. Hence, researchers have proposed a variety of
algorithms which, broadly speaking, can be categorized as basic search algorithms, geometric
algorithms, heuristic algorithms, or hardware-speci c search algorithms. In this tutorial it was
described that algorithms that are representative of each category, and discuss which type of
algorithm might be suitable for di erent applications.
4
1 Introduction
Every router performs forwarding decision on an incoming packet to determine the packet's
next-hop router. This is achieved by looking up the destination address of the incoming packet
in a forwarding table . Packet arrival rate is increased due to high speed links so the complexity
of the forwarding lookup mechanism and the large size of forwarding tables make routing lookup
a dicult task for the internet. Fast and ecient routing lookup algorithms can be used to
overcome the problem up to a certain extent. Until recently, Internet routers provided only
\best-e ort"service, servicing packets in a rst-come- rst-served manner. Routers are now
called upon to provide di erent qualities of service to di erent applications which means routers
need new mechanisms such as admission control, resource reservation, per-
ow queueing, and
fair scheduling. All of these mechanisms require the router to distinguish packets belonging to
di erent
ows. Flows are speci ed by rules applied to incoming packets. We call a collection of
rules a classi er. Each rule speci es a
ow that a packet may belong to based on some criteria
applied to the packet header, as shown in Figure 1.
Figure 1: This gure shows some of the header elds (and their widths) that might be used
for classifying the packet.
To illustrate the variety of classi ers, consider some examples of how packet classi cation
can be used by an ISP to provide di erent services. Figure 2 shows ISP1 connected to three
di erent sites: enterprise networks E1 and E2 and a Network Access Point1 (NAP), which
is in turn connected to ISP2 and ISP3. ISP1 provides a number of di erent services to its
customers, as shown in Table 1. Table 2 shows the
ows that an incoming packet must be
classi ed into by the router at interface X.
Service Example
Packet Filtering Deny all trac from ISP3 (on interface X)
destined to E2.
Policy Routing Send all voice-over-IP trac arriving from
E1 (on interface Y) and destined to E2 via a separate
ATM network.
Accounting and Billing Treat all video trac to
E1 (via interface Y) as highest priority and perform
accounting for the trac sent this way.
Trac Shaping Ensure that no more than 50Mbps of web trac
is injected into ISP2 on interface X.
Table 1:
5
Note that the
ows speci ed may or may not be mutually exclusive. For example, the rst and
second
ow in Table 2 overlap. This is common in practice, and when no explicit priorities are
speci ed,We Follow the convention that rules closer to the top of the list take priority.
Figure 2:Example network of an ISP (ISP1) connected to two enterprise networks (E1 and
E2) and to two other ISP networks across a network access point (NAP).
Flow Relevant Packet Fields:
Email and from ISP2 Source Link-layer Address,
Source Transport port number.
From ISP2 Source Link-layer Address.
From ISP3 and going to E2 Source Link-layer Address,
Destination Network-Layer Address.
All other packets -
Table 2:
Routers must perform packet classi cation at high speed s to eciently implement functions
such as rewalls, Quality Of Service (QOS) routing, packet ltering, policy routing, accounting
and billing, trac rate limiting, trac shaping etc. Packet classi cation requires matching of
each packet against a database of lters or rules and forwarding packets as per the priority of
lters .
6
2 Requirement of packet classi cation
The requirements of packet classi cation can vary depending up on the application and the
location where the classi cation is performed. The classi cation should be done at the line
speeds like TI , T3, OC3, OCI2, OC48 with minimum time required for classi cation and
minimum memory. The requirements can be listed as under:
1. Resource limitations: Packet Classi cation (PC) can be decided on the basis of time
required to perform classi cation per packet or the memory used. Di erent access speeds
are available such as Tl, T3, OC3, OCI2,OC48 etc. so, the solution for PC should match
with speed and minimize memory required.
2. Number of rules to be supported: Number of rules for PC can vary depending on appli-
cations such as rewalls,backbone router etc.
3. Number of elds used: PC applications di er on basis of the elds in IP header used for
classi cation.
4. Nature of rules: The rules are about the pre x mask or general masks used on destination
IP address.
5. Updating the set of rules: The PC should be adaptable to changes in the rules due to
route or policy changes without sacri cing access performance
6. Worst case Vs average case : For performance of PC, focusing should be done on worst
case than average case.
7
3 Speci cations of classi cation
Each rule of a classi er has d components.R[i] is the ith component of rule R, and is a regular
expression on the ith eld of the packet header. A packet P is said to match rule R, if 8i , the
ith eld of the header of P satis es the regular expression R[i] . In practice, a rule component
is not a general regular expression but is often limited by syntax to a simple address/mask
or operator/number(s) speci cation. In an address/mask speci cation, a 0 (respectively 1) at
bit position x in the mask denotes that the corresponding bit in the address is a dont care
(respectively signi cant) bit. Examples of operator/number(s) speci cations are eq 1232 and
range 34-9339. Note that a pre x can be speci ed as an address/ mask pair where the mask is
contiguous i.e., all bits with value 1 appear to the left of bits with value 0 in the mask. It can
also be speci ed as a range of width equal to 2t where t=32


Attached Files
.pdf   Packet Classification Algorithms.pdf (Size: 474.32 KB / Downloads: 48)
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  PROGRAMS USING RAW SOCKETS (LIKE PACKET CAPTURING AND FILTERING project girl 2 2,158 30-10-2015, 10:03 AM
Last Post: Guest
  General Packet Radio Service (Download Full Seminar Report) Computer Science Clay 17 11,710 21-03-2014, 05:30 AM
Last Post: MichaelKa
  Optical Packet Buffers for Backbone Internet Routers pdf seminar projects maker 0 422 28-09-2013, 02:48 PM
Last Post: seminar projects maker
  Continuous online extraction of HTTP traces from packet traces pdf seminar projects maker 0 330 23-09-2013, 04:30 PM
Last Post: seminar projects maker
  ALGORITHMS FOR ROUTING LOOKUPS AND PACKET CLASSIFICATION pdf seminar projects maker 0 352 11-09-2013, 12:23 PM
Last Post: seminar projects maker
Photo Optical packet switch architectures (Download Full Report And Abstract) computer science crazy 8 4,248 24-08-2013, 07:49 PM
Last Post: Guest
  Web Services Metrics: A Survey and A Classification pdf study tips 0 240 31-07-2013, 02:20 PM
Last Post: study tips
  Client Packet: Project Managment PPT study tips 0 290 20-07-2013, 03:11 PM
Last Post: study tips
  Packet Capture With libpcap and other Low Level Network Tricks pdf study tips 0 338 17-06-2013, 03:18 PM
Last Post: study tips
  Cellular digital packet data report study tips 0 366 29-05-2013, 04:10 PM
Last Post: study tips