عنوان پایان‌نامه
دسته بندی بسته ها در شبکه های سرعت بالا
- رشته تحصیلی
- مهندسی کامپیوتر -نرم افزار
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2287;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 59197
- تاریخ دفاع
- ۲۹ شهریور ۱۳۹۱
- دانشجو
- بعثت جعفریان
- استاد راهنما
- ناصر یزدانی
- چکیده
- مسیریاب‌ها و سوئیچ‌ها اساسی‌ترین بخش اینترنت را تشکیل می‌دهند. وظیفه اولیه مسیریاب‌ها رد و بدل کردن بسته‌های IP درون شبکه می‌باشد. با ظهور سرویس‌های جدید در شبکه و نیازمندیهای روزافزون کاربران، پردازش‌های بیشتری باید روی بسته‌های درون شبکه انجام شود. فیلتر کردن بسته‌ها، مسیریابی به روش‌هایی غیر از روش کوتاهترین مسیر و محدودسازی نرخ ترافیک از جمله این سرویس‌ها می‌باشد. برای ارائه این سرویس‌ها، مسیریاب‌ها باید جریان هر بسته را تعیین کنند تا عمل مربوطه روی بسته اعمال شود. بنابراین یک جدول از مجموعه قوانینی که از پیش تعریف شده‌اند در مسیریاب‌ها قرار داده می‌شود تا دسته‌بندی بسته‌ها طبق آن جدول انجام شود. این مجموعه قوانین روی دو یا چند حوزه از سرآیند بسته تعریف می‌شوند، بنابراین مسئله دسته‌بندی بسته‌ها یک مسئله چندبعدی به حساب می‌آید. با گسترش این مجموعه قوانین از یک سو و رشد روزافزون پهنای باند شبکه‌ها از سوی دیگر، زمان زیادی برای انجام دسته‌بندی بسته‌ها وجود ندارد. در واقع، چالش اصلی، انجام سریع دسته‌بندی بسته‌ها با مصرف بهینه‌ای از حافظه می‌باشد. در این پایان‌نامه، روش‌های ارائه شده مهم و شناخته‌شده را بررسی می‌کنیم. سپس به معرفی دو روش پیشنهادی در این زمینه می‌پردازیم. هر دو روش ارائه شده کاملا نرم‌افزاری هستند. روش اول مبتنی بر ساختار UB-tree است که این ساختار به طور کلی به منظور نمایه‌گذاری داده‌های چند بعدی استفاده می‌شود و ما از آن در روش خود، جهت نمایه‌گذاری مجموعه قوانین بهره می‌گیریم. روش دوم مبتنی بر ساختار داده B-tree می‌باشد که هدف کم کردن تعداد دسترسی به حافظه می‌باشد. هر دو روش از دو جنبه تعداد دسترسی به حافظه و پیچیدگی حافظه با روش‌های شناخته‌شده مقایسه شده‌اند. نتایج ارائه شده، نشان‌دهنده‌ی سرعت بالای هر دو روش و مصرف بسیار بهتر حافظه و در نتیجه قابلیت گسترش آن‌ها می‌باشد.
- Abstract
- Routers are one of the essential elements of Internet, which create connectivity by forwarding IP packets. Exponential growth of Internet and emergence of new network services such as packet filtering and quality of services requires routers to classify incoming packets and recognize their flows. In other words, packet classification is the ability to determine the packet flow using a classifier in the routers. A classifier (filter set) consists of a number of rules for classifying packets based on some header fields. Thus, packet classification is a multi-dimensional indexing problem. One of the main challenges is to classify packets with the line rate. This is deteriorated with the constantly increasing bandwidth rates and makes this the bottleneck of all existing classification schemes. In this thesis, we will briefly review some well known algorithms in this domain. We will present two software based methods. First, we will introduce a fast, efficient and scalable classification method called B-tree based packet classification (B2-PC) which utilizes B-tree as a base to propose a scheme with less memory access. Simulation results indicate our method outperforms existing software based methods. As the second method, we will propose a novel and scalable packet classification method that utilizes the Universal B-tree (UB-tree) data structure. UB-tree is an index structure for multi-dimensional data which is balanced and has guaranteed performance characteristics of B-tree. packet classification is also a multi-dimensional indexing problem, then, we can use UBtree. Based on simulation results, we believe our method has a better performance in terms of speed of classification and memory requirement compared to the previous proposed methods.
