16-02-2013, 12:26 PM
Packet classifiers in a large network with compression techniques
Packet classifiers.doc (Size: 35 KB / Downloads: 18)
ABSTRACT:
Packet classification is the core mechanism that enables many networking services on the firewall or the network such as packet filtering, traffic accounting, load balancing, traffic accounting and monitoring, etc. The essential problem is to compare each packet with a list of predefined rules, which we call a packet classifier, and find the first (i.e., highest priority) rule that the packet matches. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers. In a typical packet classification rule, the three fields of source and destination IP addresses and protocol type are specified as prefixes where all the *s are at the end of the ternary string, so the fields can be directly stored in a TCAM. Bit weaving is based on the observation that TCAM entries that have the same decision and whose predicates differ by only one bit can be merged into one entry by replacing the bit in question with . Bit weaving consists of two new techniques, bit swapping and bit merging, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast, it is effective, and it is compassable with other TCAM optimization methods as a pre/post-processing routine. In this paper, we present an all-match based complete redundancy removal algorithm. This is the first algorithm that attempts to solve first-match problems from an all-match perspective. We formally prove that the resulting packet classifiers have no redundant rules after running our redundancy removal algorithm.
Scope of the project:
The work is either focused on one-dimensional and two dimensional packet classifiers or it is focused on compressing packet classifiers with more than 2 dimensions. The first algorithm for eliminating all the redundant rules in a packet classifier, and we presented a more efficient redundancy removal algorithm. We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show that bit weaving is an effective stand-alone compression technique as it achieves an average compression ratio of 23.6% and that bit weaving finds compression opportunities that other methods miss.
When classifiers are updated automatically in an incremental fashion, fast updates may be very important. Bit weaving supports efficient incremental classifier updates by confining change impact to one cross-free partition. An incremental classifier change is typically inserting a new rule, deleting an existing rule, or modifying a rule. Since bit weaving is an efficient algorithm, we can apply it as a post processing step with little performance penalty. As bit weaving uses techniques that are significantly different than other compression techniques, it can often provide additional compression. We can also enhance other compression techniques by using bit weaving, in particular bit merging, within them.
The most computationally expensive stage of bit weaving is bit merging. Therefore, bit weaving is the first polynomial-time algorithm with a worst-case time complexity that is independent of the number of fields in that classifier. This complexity analysis excludes redundancy removal because redundancy removal is an optional pre/post processing step. The space complexity of bit weaving is dominated by finding the minimum prefix list.
Existing System:
TCAM compression method that can create non-prefix classifiers. All previous compression methods generate only prefix classifiers. This restriction to prefix format may miss important compression opportunities.
TCAM chips often cost more than network processors. The high price of TCAMs is mainly due to their large die area, not their market size.
Power consumption, heat generation, board space, and cost lead to system designers using smaller TCAM chips than the largest available.
It is the first efficient compression method with a polynomial worst-case running time with respect to the number of fields in each rule.
For example, TCAM components are often restricted to at most 10% of an entire board’s power budget, so a 36 Mb TCAM may not be deployable on many routers due to power consumption reasons.
All prior TCAM-based classifier compression schemes suffer from one fundamental limitation: they only produce prefix classifiers, which means they all miss some opportunities for compression.
Because all previous compression schemes can only produce prefix rules, they miss the compression opportunities created by non-prefix ternary rules.
Proposed System:
While TCAM-based packet classification is the current industry standard, the above limitations imply that existing TCAM-based solutions may not be able to scale up to meet the future packet classification needs of the rapidly growing Internet.
Specifically, packet classifiers are growing rapidly in size and width due to several causes. First, the deployment of new Internet services and the rise of new security threats lead to larger and more complex packet classification rule sets.
In this paper, we propose bit weaving, a new TCAM-based classifier compression scheme that is not limited to producing prefix classifiers.
First, we need to develop an algorithm that partitions a rule list into the least number of partitions.
Second, we must develop an algorithm that permutes the bit columns within each partition to produce one-dimensional prefix rule lists.
Third, we must adapt existing one-dimensional prefix rule list minimization algorithms to minimize incomplete one-dimensional rule lists.
A rule list is complete if and only if for any packet, the list has a rule that the packet matches. Finally, we must develop algorithms to detect and then merge rules within each partition.