دسته بندي بسته ها در شبكه هاي IP با استفاده از روش هاي هندسي

چكيده انگليسي :

Packet Classification in IP Networks Using Geometric Methods Mohammad Reza Hosseini mr hosseini@ec iut ac ir Date of Submission 2012 9 17 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisors Dr Hossein Saidi Dr Masoud Reza HashemiAbstractPacket classification is a key operation in computer networks Every packet that enters a node is classified basedon the rules which are defined in that node As a result the corresponding action of the rule that is matched withthe packet will be applied on it These rules are defined on the header fields of IP packet Packet classification isused in many applications such as routers firewalls and many applications that are related to network security orquality of service Due to the growth of computer networks and the increasing amount of transferred data it isnecessary that classification is done with appropriate speed and efficient memory usage Update time is anotherproperty which is also important in some applications Although many of the methods that are purposed forpacket classification until now have an efficient search time but most of them do not support fast updates of therules Packet classification algorithms are divided into four major classes Algorithms that use exhaustivesearch decision tree based algorithms decomposition based algorithms and algorithms that use tuple spacesearch Among these four classes decision tree based algorithms are used more than others because of usingefficient tree search algorithms Decomposition based algorithms are able to use parallel processing becausethey convert a multi field packet classification problem to many single field packet classification problems thusthe single field searches can be done in parallel In the final stage all the results of single field searches aremerged in order to find final results Different approaches have been introduced to solve packet classificationproblem One of the most famous approaches is to convert the packet classification problem to a computationalgeometry problem such that the problem can be solved using computational geometry algorithms Each packetclassification rule is equal to a hyper rectangle in a multi dimensional space where the number of dimensions isequal to the number of header fields which the rules are defined on them Based on this approach in this thesis the geometric representation of the packet classification problem is considered Many computational geometryproblems which are similar to the packet classification are reviewed and the stabbing query problem which isthe most similar one dimensional problem to packet classification is selected Finally some new algorithms areintroduced based on the solutions for stabbing query problem such as interval tree and interval skip list datastructures In these algorithms we have concentrated on efficient update speed and the ability to use parallelprocessing Using the characteristics of the packet classification rule sets we showed that applying the purposedalgorithms on two fields could be enough and classification on other fields can be done using linear search asthe number of remaining rules after a two field packet classification is very small The purposed methods areevaluated and compared against Parallel Bit Vector and HiCuts algorithms Experimental results showed thatthese methods have both acceptable search time and memory usage while support fast updates of the rules aswell Key WordsPacket classification Traffic control Interval tree Interval skip list

حسيني، محمدرضا

دسته بندي بسته ها در شبكه هاي IP با استفاده از روش هاي هندسي

كنترل ترافيك , درخت بازه ها , ليست پرشي بازه ها