Improvement And Application Of Optimizing Rule Matching Algorithm In Network Traffic Control

Traffic Control plays an important role in the Quality of Services of key services.As the increase of network bandwidth and traffic and the appeared and development of new applications,Traffic Control faces more complex issues and higher challenges.This thesis analyses the basic idea and concept of traffic control,especially the rule structure and matching algorithm of traffic control with Netfilter/Ipatbles framework in Linux system.This thesis improves the processing rate of traffic control system by optimizing rule matching algorithm and rule collision detection to improve rule matching rate and limit the rule set scale.The main works are as follows:Firstly,we propose an adaptive tree based rule matching algorithm.Liner rule matching consume a lot of time,as the increase of rules.According to the protocol type(TCP/UDP/ICMP),building a tree can reduce the matching time.But the tree maybe not balances.The adaptive tree based rule matching algorithm branches according to the distribution of rule and the default rule rate in order to balance the tree depth and width.Building tree as the depth-first search strategy.A sub-algorithm is proposed to treat the rule add,delete and update.The simulation results show that our algorithm builds a more balance tree and decreases the match number 179%,14.9% than liner rule matching and tree with protocol.Secondly,we propose a rule collision detection criterion and algorithm.When building and managing the rule set,due to the limited knowledge of administrators,there are redundancy rules which lead that the rule set scale increase.When a packet may match several rules,only one rule with the highest priority is chosen as the final rule.This consumes the matching time.Therefore,we define the relationship of rules as redundancies,collision,inclusion,intersection and independence according to the relationship of packet set matched to rules.The rule collision detection criterion allows existing the inclusion,intersection and independence in rule set.It avoids the redundancy of rule set and avoids deleting valid rules.The rule collision detection algorithm implements the criterion by comparing the new adding rule with the rules in rule set to control the scale of rule set,reduce matching time and improve the rate of matching.Finally,the rule collision detection algorithm is directly implemented in Network Traffic Control System(NTCS).All new adding rules which pass the rule collision detection algorithm can be successfully added to rule set to improves the rate of matching and limit the rule set scale.