ClassiFier Introduction

封包分類技術: 

封包分類技術 資策會 網路及通訊實驗室 楊儒林 rlyang@iii.org.tw 07/17/2001

The Function Of Classifier: 

The Function Of Classifier Classify internet packets Match a packet against a set of rules For router/switch/…network device

The Issues Of Classifier: 

The Issues Of Classifier Scalability Flexibility Speed Resource consuming Cost

Characteristics of III Classifier: 

Characteristics of III Classifier Multi-fields classifier Source MAC Destination MAC TOS/DSCP Protocol Source IP Destination IP Source port Destination port

Characteristics of III Classifier (continue): 

Characteristics of III Classifier (continue) Rule operation Exact, range, wildcard (don’t care) For example, source MAC: wildcard destination MAC: wildcard TOS/DSCP: wildcard protocol: wildcard source IP: 10.1.1.1 (exact) destination IP: 10.2.1.10-10.2.1.20 (range) source port: wildcard destination port: wildcard

Characteristics of III Classifier (continue): 

Characteristics of III Classifier (continue) Constant time algorithm Easy hardware implementation ASIC FPGA Using acceptable memory 256 rules Use less than 300k memory AP aware (negotiated dynamic port numbers) FTP, H323, …etc. Detecting rule collision

Characteristics of III Classifier (continue): 

Characteristics of III Classifier (continue) Scalability ? score Flexibility ? score Speed ? score Resource consuming ? score Cost ? score

How to classify internet packet ?: 

How to classify internet packet ?

How to classify internet packet ?: 

memory packet Parse Packet Header Classify Packet rule ID How to classify internet packet ?

How to add a new rule ?: 

parse the new rule transform to triple elements (a triple element point to a subset of a row of the rules table) rule collision ? get an unused rule ID according to the distribution method update rules table according to the rule ID and triple elements if we turn on the rule collision detection option False True begin end How to add a new rule ?

How to add a new rule ?: 

memory rule Partition Fields Classify Packets Detect Rule Collision Request Rule ID Update Rules Table How to add a new rule ?

How to detect rule collision ?: 

according to the triple elements does the range of the triple elements satisfy some rules ? rule collision no rule collision True False illegal rules ? True False begin end How to detect rule collision ?

How to remove an existent rule?: 

parse the existent rule transform to triple elements (a triple element point to a subset of a row of the rules table) leaf node of the policy tree ? get the rule ID of this rule update rules table according to the rule ID and triple elements True False return this rule ID begin end How to remove an existent rule?

How to remove an existent rule?: 

memory rule Partition Fields Update Rules Table Get Rule ID Return Rule ID How to remove an existent rule?