سعید اسدروز - دانشکده فنی و مهندسی
دانشکده مهندسی
گروه آموزشی مهندسی کامپیوتر
پایاننامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات گرایش شبکههای کامپیوتری
عنوان:
یک روش ترافیک آگاه برای دستهبندی بستهها با هدف کاهش تعداد دفعات دسترسی به حافظه
استاد راهنما:
دکتر محمد نصیری
استاد مشاور:
دکتر مهدی عباسی
اساتید داور:
دکتر محرم منصوری زاده
دکتر مهدی سخایی نیا
نگارش:
سعید اسدروز
زمان: سه شنبه 27 بهمن ماه 94، ساعت 16:30
مکان: کلاس 27 سایت نظری
بهمن 1394
چكيده:
فرآیند دستهبندی بستههای ورودی به جریانهای مختلف در ابزارهای پردازشگر شبکهای، دستهبندی بستهها نامیده میشود. دستهبندی بستهها نقش بسزایی در بهبود عملکرد تجهیزات شبکهای ازجمله مسیریابها، دیوارههای آتش، سیستمهای تشخیص نفوذ ایفا میکند. دستهبندی بستهها بر اساس مجموعه قوانین خطمشی انجام میگیرد. از آنجا که ممکن است یک بسته با مجموعهای از قوانین منطبق شود، سیاست مرتبط با قانون با اولویت بالاتر بر آن بسته اعمال میشود. با توجه به افزایش تعداد قوانین دستهبندی و حجم بالای ترافیک عبوری و نیز پهنای باند بالای لینکهای شبکه، لزوم تسریع عمل دستهبندی آشکار میشود. با این حال، الگوریتمهای دستهبندی استفادهکننده از ساختار داده ایستا، الگوی رفتاری ترافیک ورودی را در بهینهسازی ساختار داده جستجو در نظر نمیگیرند.
در این پژوهش، ویژگیهای آماری ترافیک ورودی را در نظر گرفته و از داده ساختارهای کمکی ترافیک آگاه در کنار داده ساختارهای اصلی استفاده نمودهایم. ازآنجاکه حجم غالب ترافیک اینترنت، مربوط به جریانهای بلندمدت است، برای مدتزمانی نهچندان کوتاه، اکثر مطابقتهای قوانین در زیر درختهای مشخصی از درخت جستجو قرار دارند. برای بهرهگیری از این ویژگی، در این پژوهش از ساختار داده درخت AVL برای نگهداری قوانین دستهبند و از حدهای بالا و پایین مجموعه قوانین بهعنوان گرههای درخت جستجو استفاده شده است. در اینجا در هر گره از یک شمارنده برای نگهداری تعداد بستههای منطبقشده و به دست آوردن قوانین با فراوانی بالا استفاده شده است. در بازههای زمانی ثابت و بهصورت آنلاین با استفاده از قوانین با فراوانی بالا، بازسازی ساختار داده کمکی ترافیک آگاه صورت میگیرد. با استفاده از ارزیابیها نشان دادیم که با افزایش کجی بستههای آزمون، نرخ بهره الگوریتم دستهبندی ترافیک آگاه نسبت به الگوریتم دستهبندی پایه و نرخ برخورد درختهای قوانین پرتکرار افزایش مییابد. همچنین نشان دادهایم که دستهبندی بسته ترافیک آگاه با استفاده از قوانین پرتکرار میتواند بهطور قابلتوجهی میانگین تعداد دفعات دسترسی به حافظه را کاهش دهد و درنتیجه موجب افزایش سرعت جستجو شود.
کلمات کلیدی: : دستهبندی بستهها، ترافیک آگاه، درخت AVL، محلی بودن مراجعات، دسترسی به حافظه، نرخ برخورد، نرخ بهره
Abstract:
The process of categorizing incoming packets into flows in networks devices is called packet classification. Packet classification plays a critical role in improving the performance of many network devices including routers, firewalls and Intrusion Detection Systems. Packet classification is done based on policy rule set. Since it may be a packet match with a set of rules, policies with higher priority rule is applied on the packet. Due to the increasing number of classification rules and high volume of passing traffic and high bandwidth network links, the need to expedite classification appears. Packet classification algorithms that use static data structure, do not consider the pattern of the incoming traffic in optimizing their search data structure.
In this study, we consider the statistics characteristics of the incoming traffic and use traffic aware data structure along the main structures. Since most Internet traffic volume, related to long-term flows, for a period of time, most of the matchs are in the certain subtrees of search tree. To take advantage of this feature, use AVL tree data structure for storing classification rules and use the upper and lower limits of the rule set as nodes of search tree. We have a counter at each node for storing the number of matched packets and obtaining high frequency rules. Using high frequency rules at fixed time intervals and online, Restructuring of traffic aware data structure is done. Our evaluation results have shown that with increasing the skewness of test packets, gain rate of traffic aware algorithm to base algorithm and hit rate of high frequency rule trees will be increase. Finally, Results have shown that traffic aware packet classification with high frequency rules can significantly decrease average number of memory access and increases search speed.
Key Words: Packet Classification, Traffic Aware, AVL Tree, Locality of Reference, Memory Access, Hit Rate, Gain Rate
v مقام اول ششمین دوره مسابقات علمی و عملی هنرستانهای فنیوحرفهای و کشاورزی استان کهگیلویه و بویراحمد در رشته نرم افزار کامپیوتر
v مقام دوم ششمین دوره مسابقات علمی و عملی هنرستان های فنیوحرفهای و کشاورزی منطقه 4 کشور در رشته نرم افزار کامپیوتر – اسفندماه 1383 در مشهد مقدس
v دارای گواهینامه پایاندوره دوربینهای مداربسته آنالوگ (CCTV)، دوربین تحت شبکه، انتقال تصاویر، دزدگیر اماکن و سیستم اعلان حریق از مجتمع آموزشی سفیر قرن تهران
v دارای گواهینامه مهارت تکنسیین عمومی شبکه های کامپیوتری از سازمان آموزش فنی و حرفه ای کشور
v دارای مدارک تخصصی زیر از آموزشگاه فنی و حرفهای آزاد نوین دانشجو:
v Windows 8 Configuring
v Windows Server 2012 Enterprise Administrator
v Windows Server 2012 Network Infrastructure Configuring
v Windows Server 2012 Network Directory Configuring
v Windows Server 2012 Applications Infrastructure Configuring
v دارای گواهینامه های پایان دوره آموزشی:
v CCNA
v CCNP Switch
v CCNP Route
v CCNP TSHOOT
v CCNA Security