چکیده

فرآيند جداسازي بسته‌هاي شبکه در قالب جريانهاي مشخص، با نام دسته‌بندي بسته‌ها¹ (Packet Classification) شناخته مي‌شود و هدف از آن ايجاد امکان انجام پردازشهاي ويژه هر جريان، بر روي جريان مربوطه مي‌باشد. هر جريان² توسط يک جداساز³، که شروطي را بر سرآيند بسته شبکه اعمال مي‌کند، مشخص مي‌شود.

در این مقاله انواع شیوه‌های Classification مورد بررسی قرار میگیرد.

 

 

1 Classification یا دسته‌بندي بسته های شبکه

فرآيند جداسازي بسته‌هاي شبکه در قالب جريانهاي مشخص، با نام دسته‌بندي بسته‌ها⁴ شناخته مي‌شود و هدف از آن ايجاد امکان انجام پردازشهاي ويژة هر جريان، بر روي جريان مربوطه مي‌باشد. هر جريان⁵ توسط يک جداساز⁶، که شروطي را بر سرآيند بستة شبکه اعمال مي‌کند، مشخص مي‌شود. رايج‌ترين گونة اين فرآيند، عمل مسيريابي در مسيريابهاي شبکه مي‌باشد. چنانکه مسيرياب با دريافت يک بستة شبکه، بر اساس مقدار آدرس مقصد آن گام بعدي بسته را مشخص و بسته را، بعد از مشخص شدن مسير، در آن هدايت مي‌کند. انجام اين عمل، که با نام IP-LookUP شناخته مي‌شود، مستلزم وجود جدولي از زوجهاي (آدرس مقصد ، گام بعدي) مي‌باشد تا بدين‌نحو امکان هدايت بسته‌ها، بر اساس آدرس مقصدشان، فراهم شود. در اين حالت فرآيند دسته‌بندي بسته‌ها، بر اساس آدرس مقصد بسته‌هاي شبکه صورت پذيرفته و پردازش مربوط به جريانهاي ايجاد شده از بسته‌ها نيز، هدايت بسته‌ها در مسير گام بعدي آنان مي‌باشد.

دو جزء اصلي يک فرآيند دسته‌بندي 1- انباره‌اي از جداسازها⁷ و 2- جستجودر ميان جداسازهاي موجود در انباره مي‌باشند. هدف از انجام عمل جستجو که با دريافت هر بسته انجام مي‌شود، يافتن مناسبترين جداسازِ مربوط به بستة دريافتي مي‌باشد. هر جداساز بر اساس پارامترهايي که هر يک متناظر با جزئي (فيلدي) از سرآيند بستة شبکه مي‌باشند، شروط خويش را براي پذيرش بستة شبکه اعلام مي‌کند و جستجو نيز بر اساس تطابق اين پارامترها با مقادير متناظر آنها در سرآيند بستة شبکه، انجام مي‌شود. در فرآيند IP-LookUP پارامتري که به عنوان شرط پذيرش بسته عنوان مي‌شود، پيشوند آدرس مقصد مي‌باشد. به عبارتي بسته‌اي توسط اين جداساز پذيرفته خواهد شد که آدرس مقصد آن داراي پيشوند ذکر شده باشد.

هر جداساز در کنار شروط پذيرش بسته‌هاي شبکه، پردازشي، که مي‌بايست بر روي بسته‌هاي تطابق يافته اعمال شود، را مشخص مي‌کند. اين پردازش در فرآيند IP-LookUP هدايت در مسير گام بعدي مي‌باشد.

چگونگي انجام عمل جستجو در فرآيند دسته‌بندي بسته‌ها، جزوِ بحث برانگيزترين مسائل مطرح در اين حيطه مي‌باشد. اهميت مسئله از اهميتِ نقش و جايگاه مسيريابها، به عنوان بارزترينِ استفاده‌کنندگانِ فرآيند دسته‌بندي بسته‌ها، ناشي مي‌شود. چرا که آنها مي‌بايست بسته‌ها را با سرعتي در حد سرعت ابزار شبکه، بدون تأخير، هدايت کنند.

از طرف ديگر تعداد پارامترهاي مربوط به شروط جداسازها، بر پيچيدگي مسئلة جستجو مي‌افزايد. چنانکه فرآيند IP-LookUP که تنها بر اساس آدرس مقصد انجام مي‌شود جزوِ ساده‌ترينِ دسته‌بندي‌ها به حساب مي‌آيد و امروزه به عنوان يک مسئلة حل شده بدان نگاه مي‌شود، چرا که نياز امروز، پارامترهاي بيشتري را براي انجام فرآيندهاي دسته‌بندي مي‌طلبد.

بيان جداسازها مي‌تواند با اشتراک محدوده‌اي همراه باشد، به عبارتي امکان پذيرش يک يا چند بسته توسط چند جداساز مختلف، در آنِِ واحد، وجود داشته باشد. در اين مورد الگوريتم جستجو، جداسازي را انتخاب خواهد کرد که نسبت به ديگران اولويت بيشتري داشته باشد. به عنوان مثال در IP-LookUP اين مسئله با طولانيترين طول پيشوند حل شده است و در بعضي موارد، با رسيدن به اولين تطابق، فرآيند جستجو متوقف مي‌شود. بدين صورت، چگونگي پراکندگي جداسازها در فضاي بسته‌هاي شبکه، تأثير زيادي بر چگونگي انجام فرآيند جستجو خواهد داشت.

انباره‌ها به عنوان مکان نگهداري جداسازها، تأثير بسزايي بر چگونگي انجام عمل جستجو خواهند داشت و از اين رو ساختمان دادة مربوط به انباره نيز، از مسائل قابل چالش و بحث برانگيز در اين حيطه مي‌باشد.

 

1.1 دليل استفاده از فرآيند دسته‌بندي بسته‌ها

مسيريابهاي هسته ، مسيريابهاي گوشه، و ديواره‌هاي آتش به عنوان سه بازيگر اصلي سناريوي دسته‌بندي‌بسته‌ها مطرح مي‌باشند.

مسيريابهاي هسته، به عنوان شاهراه‌هاي شبکة جهاني، وظيفة هدايت و مديريت بسته‌هاي شبکه را، با سرعت بسيار بالا، بر عهده دارند. مسيريابهاي گوشه به عنوان نقاط اتصال به شاهراه‌ها، وظيفة هدايت بسته‌هاي محلي به بيرون و بالعکس را بر عهده داشته و ديواره هاي آتش، فراهم کنندة امنيت مي‌باشند.

آنچه که تا کنون از مسيريابها انتظار مي‌رفته هدايت بسته‌ها بر اساس آدرس مقصد و انجام بهترين‌تلاش⁸ براي رساندن بسته‌ها به مقصد بوده است. ديواره‌هاي آتش نيز وظيفة جلوگيري از عبور بسته هاي شبکه، به مقصد يا از مبدأ خاصي، را بر عهده داشته‌اند.

اما افزايش دغدغه‌هاي امنيتي ،گسترش و تنوع برنامه‌هاي کاربردي شبکه، و به تبع آن گسترش و تنوع در نيازهاي کاربردي آنها در سطح شبکه، تنوع در تجهيزات شبکه، و تفکر براي ايجاد منابع درآمدزايي تازه در سطح جهان، بار پردازشي زيادي را بر دوش اين سه بازيگر گذاشته است، چنانکه اين بار پردازشي تنها به مسيريابي بر اساس آدرس مقصد منتهي نمي‌شود بلکه جداسازي بسته‌ها بر اساس پارامترهاي گوناگوني همانند: نوع برنامة کاربردي، سرويس کيفيت لازم، آدرس مبدأ گسيل شده ، آدرس مقصد، تعلق به زير شبکة خاص و ... را شامل مي‌شود .

در دنياي کنوني ديد واحد داشتن نسبت به بسته ها و رفتار بر اساس مکانيزم FIFO⁹، جوابگوي نيازهاي رو به رشد برنامه‌هاي کاربردي و کاربران پرتوقع نمي‌باشد.

هم اکنون انتظار مي‌رود که مسيريابها توانايي پشتيباني از سرويسهاي کيفيت مختلف، براي برنامه‌هاي کاربردي مختلف، را دارا باشند. براي اين منظور مسيريابها نياز به مکانيزمهاي جديدي از جمله رزرواسيون منابع ، صف‌بندي براي هر جريان و ... دارند. ديواره‌هاي آتش مي‌بايست کنترل بيشتري بر روي برنامه‌ها و کاربران داشته، و در کنار آن، مسيريابهاي گوشه نياز به انعطافپذيري بيشتري در مديريت کاربرانشان دارند .پيش نياز تمام اين موارد دسته‌بندي بسته‌ها در قالب جريانهاي مختلف، براي انجام پردازشِ مناسب مي‌باشد.

 

1.2 سرويسهاي قابل ارائه توسط فرآيند دسته‌بندي بسته‌ها

دسته‌بندي بسته‌ها يک قابليت و توان است که امکان عملي شدن انجام پردازشهايي را فراهم مي‌سازد. به عبارتي، دسته‌بندي بسته‌ها به خودي خود اهميت ندارد، بلکه پردازشهاي انجام شده بر روي جريانهاي حاصل از دسته‌بندي بسته‌ها مي‌باشند که اهميت دسته‌بندي بسته‌ها را، هر چه بيشتر نمايان مي‌سازند. اين پردازشها عبارتند از:

1. پالايش بسته‌ها¹⁰: اين وظيفه ( پردازش ) که بيشتر به ديواره‌هاي آتش نزديک است، امکان حذف بسته‌هاي ناخواسته را فراهم مي‌سازد. با اين پردازش قادر خواهيم بود تا از دسترسي به منابعي خاص، توسط کاربراني خاص، جلوگيري کنيم.

2. هدايت بر اساس سياست¹¹: با توجه به نيازهاي مختلف برنامه‌هاي کاربردي مطرح مي شود. به عنوان مثال مي‌توان بسته‌هاي مربوط به برنامه‌هاي VOIP¹² را از روي خطوط پرسرعت هدايت کرد تا تأ خيري در ارسال آنها حاصل نشود.

3. حسابداري و حسابرسي¹³: جزوِ منابع در آمدزايي جديد محسوب مي شود. به عنوان مثال مي‌توان بسته‌هاي مربوط به برنامه هاي بصري ( video )، گسيل شده از منبع خاصي، را با اولويت بالاتر در نظر گرفت و در کنارآن، هزينة خاص آن را نيز محاسبه کرد.

4. اعمال محدوديت بر نرخ جريان¹⁴: مربوط به دغدغه‌هاي مديريتي به يک مسيرياب گوشه مي‌باشد. بدين طريق مي توان نرخ جريان عبوري بسته‌هاي مربوط به يک برنامة خاص را، با توجه به مبدأ آن و يا بدون توجه به آن، در حد مشخصي محدود کرد تا شبکه بيش از آن اشغال نشود. اين موضوع براي مواردي که درخواست براي يک برنامه بسيار زياد، اما منابع ما محدود است، بسيار کارا مي‌باشد .

5. اطمينان از عدم تجاوزِ نرخ جريان ورودي به مقصدي مشخص از حدي معين¹⁵.

 

1.3 تشريح مسئلة دسته‌بندي بسته‌ها

براي رسيدن به جواب، اولين گام طرح مسئله مي‌باشد: به عبارتي بيانِ موضوعِ موردِ بحث با استفاده از زبان تئوريک و رياضي. پس بايد ببينيم منظور از دسته‌بندي بسته‌ها چيست تا بيان الگوريتمها و طرح انتظارات از آنها بي‌پايه و بدون استناد نباشد. تعريف بيان شده در اينجا تا پايان به عنوان محور بحث واقع خواهد شد.

تعريف: فرآيند دسته‌بندي بسته‌ها شامل يک انباره از جداسازها(قانونها) مي‌باشد. هرجداساز از d جزء که هر جزء متناظر با فيلدي در سرآيند بستة شبکه مي‌باشد، تشکيل شده که هر کدام از اين اجزاء، در تعريف يک جداساز، به صورت يک عبارت منظم بيان مي‌شوند: R[i] به عنوان جزء iام جداساز R، به صورت يک عبارت منظم بر روي iامين جزءِ سرآيند بسته، تعريف مي‌شود.

بيان مي‌شود که يک بستة P با جداساز R مطابقت دارد اگرکه هر جزء i از سرآيند بسته با عبارت منظم R[i] ازجداساز R تطابق حاصل کند، يا به عبارتي توسط آن عبارت منظم پذيرفته شود.

عمل جستجو شامل يافتن جداساز با بالاترين اولويت از ميان جداسازهاي مطابق با بستة دريافتي مي‌باشد .

در عمل اجزايِ يک جداساز به صورت تطابقهاي عيني ، محدوده‌اي و پيشوندي بيان مي‌شوند، با اين توضيح که تطابق عيني حالتي از تطابق محدوده‌اي مي‌باشد .

در تطابق عيني، مقدار متناظر آن جزء در سرآيند بسته بايد عيناً با مقدار ذکر شده در جداساز يکي باشد. به عنوان مثال از آن مي‌توان براي بيان پروتکل بسته استفاده‌کرد.

در تطابق محدوده‌اي، مقدار متناظر آن جزء در سرآيند بسته بايد مقداري در محدودة ذکر شده را اختيار کند. به عنوان مثال مي توان از آن براي بيان محدوده‌اي از شمارة پورتها استفاده‌کرد .

در تطابق پيشوندي‌، مقدار متناظر آن جز در سرآيند بسته بايد داراي پيشوندي برابر با مقدار ذکر شده در جداساز باشد. به عنوان مثال مي توان از آن براي مشخص کردن زير شبکه‌ها¹⁶ استفاده‌کرد .

 

1.3.1 تعبير هندسي

اگر خطي از اعداد باينري را در نظر بگيريم مي‌توانيم يک پيشوند را به صورت يک پاره‌خط بر روي آن نمايش دهيم. به عبارتي يک جداساز با يک جزء را مي‌توان به صورتِ يک پاره‌خط در فضاي يک بعدي نمايش داد. به عنوان مثال به نمايش  براي اعداد باينري با پهناي سه توجه کنيد(شکل 1.1).

 

شکل 1.1 : نمايش 1** بر روی خط اعداد

به همين صورت، جداساز داراي دو جزءِ پيشوندي، به صورت يک مستطيل در فضاي دو بعدي قابل نمايش است(شکل 2.1).

اگر به همين شکل از طرز بيان ادامه دهيم، يک جداساز داراي سه جزء را مي‌توان به صورت يک مکعب در فضاي سه‌بعدي و يک جداساز داراي k جزء را به صورت يک فوق مستطيل در فضاي k بعدي مطرح کرد . در اين نمايش هر جزء، يک بعد از فضاي k بعدي را تشکيل خواهد داد که اندازة آن بستگي به پهنايِ اعدادِ باينريِ تشکيل دهندة آن جزء دارد ( به عنوان مثال براي IP اندازة آن 2³² و محدودة آن [ 1-2³² ، 0 ] مي‌باشد) .

 

شکل 2.1 : نمايش در فضای دو بعدی

بنابر اين مي توانيم هر انباره را به صورت يک فضاي k بعدي در نظر بگيريم که جداسازها به صورت فوق مستطيليهاي ^k2 وجهي در آن قرار گرفته‌اند. در اين فضا هر بسته به صورت يک نقطه قابل نمايش است . بنابراين مي‌توان، با اين ديد، فرآيند دسته‌بندي بسته‌ها را اينگونه تعريف کرد: تشخيص تعلق نقطه مورد نظر (بسته) به فوق مستطيلي با بالاترين اولويت. به عبارتي ما به دنبال فوق ‌مستطيلي در فضاي k بعدي مي‌گرديم که محيط بر نقطة نمايش‌دهندة بسته مي‌باشد و اگر چندين فوق مستطيل داراي اين خاصيت شدند، فوق مستطيل داراي بالاترين اولويت را در نظر مي‌گيريم .

با اين تعريف عمل دسته‌بندي را مي توان جزوِ الگوريتمهاي مکان‌يابي، که در فضاي هندسي تعريف مي‌شوند، در نظر گرفت. مسائل هندسي استانداردي نظير Ray Shooting، موقعيت‌يابي نقطه ( Point Location ) و مستطيل محيط (Rectangle Enclosure) به نوعي دنباله‌رو مسائل دسته‌بندي هستند.

موقعيت‌يابي نقطه شامل يافتن محدودة حاوي نقطه مورد نظر در ميان مجموعه‌اي از نواحي غيرهمپوشان مي‌باشد. بهترين حدود براي اين الگوريتم از ديد پيچيدگي زماني و حافظه‌اي، براي N ناحية مستطيلي با d>3(تعداد ابعاد) به صورت  (زماني) و  (حافظه‌اي) و يا به صورت  (زماني) و  (حافظه‌اي) مي‌باشد .

در دسته‌بندي بسته‌ها، فوق‌مستطيلها مي‌توانند همپوشاني داشته ‌باشند. در نتيجه، با خوشبيني، پيچيدگي فرآيند دسته‌بندي بسته‌ها به اندازة الگوريتم موقعيت‌يابي نقطه خواهد‌بود ولي در عمل بسيار بيشتر از آن است. بنابراين اولين نتيجه‌اي که از اين مسائل مي‌توان گرفت اين است که: دسته‌بندي با اجزاي چندگانه در حد قابل توجهي پيچيده‌تر از تطابق طولاني‌ترين پيشوند در حالت يک بعدي خواهد بود و نيز مي‌توان پيش‌بيني کرد که راه حلهاي عملي، تمايل و کششي به سمت راه‌حلهاي مکاشفه‌اي پيدا کنند.

نياز به حمايت از تطابق‌هاي محدوده‌اي در کنار تطابق هاي پيشوندي، باعث پيچيده‌تر شدن فرآيند دسته‌بندي مي‌شود. مسئله جستجوي محدوده اي براي يک بعد با اندازة [1-^w2 ، 0] به اين گونه تعريف مي‌شود :

تعريف: با دارا بودن مجموعه‌اي از N محدودة غير مشترک که يک افراز از خط اعداد  را تشکيل مي‌دهند به صورت ، جستجوي محدوده‌اي به معناي يافتن محدوده‌اي خواهد بود که حاوي نقطة مورد نظر باشد ( نقطه همان اطلاعاتي است که بايد تعلق آن نسبت به يک محدوده مشخص شود ).

براي تخمين پيچيدگي اضافه شده به وسيلة محدوده‌ها، ما مي‌توانيم هر محدوده را به صورت مجموعه‌اي از پيشوندها نمايش دهيم و از تطابق با طولانيترين پيشوند براي يافتن محدودة محيط استفاده کنيم.

توجه: يک پيشوند به طول s نمايشِ محدودة [L, U] ميباشد اگر که w - s تا ( w پهناي محدوده مي‌باشد، تعداد بيتهاي لازم براي پوشاندن محدوده در مبناي دو ) از بيتهاي كم ارزش L تماما صفر و به همين مقدار از بيتهاي کم ارزش U تماما يك باشند.

 

به عنوان مثال به جدول روبرو براي بيان محدوده‌ها به صورت پيشوند توجه کنيد:

 

محدوده	پيشوندهاي عضو
[7 – 4]	01**
[8 – 3]	0011, 01**, 1000
[14 – 1]	0001, 001*, 01**, 110*, 1110

 

از آنجايي که هر محدودة w بيتي حداکثر با 2-w2 پيشوند قابل نمايش است، مي‌توان نتيجه گرفت که الگوريتم تطابق پيشوند مي‌تواند محدوده‌ها را به ازاي استفاده از w2 برابر حافظة بيشتر پوشش دهد ( چرا که هر قانونِ محدوده‌اي به w2 قانون تبديل مي‌شود ).

 

1.4 کارآيي الگوريتم هاي دسته‌بندي

به صورت معمول، دسته‌بندي بسته‌ها بر اساس اجزاي مختلف بستة شبکه عملي سخت و مشکل مي‌باشد. به همين دليل توسط محققان راه‌حلهاي مختلفي براي آن ارائه شده است. بعضا راه‌حلهاي مختلف بر جنبه‌هاي گوناگون انبارة جداسازها، به عنوان پيش‌فرضهاي حاکم بر محيط مسئله، تکيه کرده و بر اساس آن الگوريتم خود را بيان مي‌کنند. به عنوان مثال تعداد کم همپوشاني در بين جداسازها و محدوديت در تعداد جداسازهاي موجود در انباره، از جملة اين پيش‌فرضها مي‌باشند.

البته بيان اين موضوع خالي از لطف نيست که وجود تفاوت در تعريف و محيطِ کاري مسيريابهايِ گوشه، هسته و ديواره‌هاي‌آتش باعث بروز تفاوتهايي در ساختار انباره‌هاي موجود در آنها مي‌شود. بارزترين نمونة تفاوت، تعداد جداسازهاي موجود در انباره‌ها مي‌باشد به طوريکه اين تعداد در مسيريابهاي هسته در محدوده 2000 الي 4000 قرار دارد و همين مقدار در مسيريابهاي گوشه به 32 كيلو جداساز افزايش مي‌يابد. - اگر فيلدهاي آدرس مقصد و مبدا را جزو اجزاء دسته‌بندي در نظر بگيريم - در مسيريابهاي هسته مقادير مربوط به آدرس مقصد و مبدا به صورت مقادير پيشوندي مطرح مي‌شوند حال آنکه در مسيريابهاي گوشه بيشتر به صورت تطابق عيني براي آدرس مبدا و جواز¹⁷ براي آدرس مقصد(و يا برعکس) بيان مي‌گردند. بعضي الگوريتمها بر روي تعداد بخصوصي از اجزاء سرآيند تکيه مي‌کنند - به طور مثال جداسازهاي داراي دو جزء ( آدرس مبدا و مقصد) و يا يک جزء (آدرس مقصد: نمونه بارز آن مسئله IP-LookUP مي‌باشد) – .

محاوره‌اي بودن انباره ( به روزرسانيهاي پي‌در‌پي و مکرر ) نيز از ديگر پارامترهايي مي‌باشد که ديد نسبت به آن متفاوت است. به عنوان مثال انباره‌هايِ موجود در ديواره‌هاي آتش به عنوان انباره‌هاي ايستا مطرح شده و بالعکس در مسيريابهاي هسته و گوشه ما مواجه با انباره‌هاي محاوره‌اي هستيم. محاوره‌اي بودن انباره بار پردازشي بيشتري را بر الگوريتم دسته‌بندي اعمال مي‌کند و پيچيدگي الگوريتم‌هايي که موضوع به‌روزرساني را در پياده‌سازي خود در نظر گرفته‌اند به مراتب بيشتر از الگوريتمهايي مي‌باشد که انباره‌هاي ايستا را مبناي کار خود قرار داده‌اند. البته اين موضوع نيز به طبع انباره برمي‌گردد و مي‌توان تنها با تمرکز بر حالت ايستا الگوريتم سبکتري را ارئه داد(مثلاً الگوريتم فقط براي ديواره‌هاي آتش بيان شود).

در اين ميان الگوريتمهايي نيز بيان مي‌شوندکه از جنبة تئوريک فرض خاصي را بر انباره تحميل نمي‌کنند. البته اين امکان وجود دارد که اين الگوريتمها در محيطهاي خاصي کارآيي بيشتري داشته باشند ولي به هر حال نکتة مثبت براي آنها امکان تطابق با محيطهاي مختلف مي‌باشد، چرا که مي‌توان با اعمال پيش‌فرضهايي در ساختار الگوريتم، از آن براي محيط خاصي استفاده کرد.

در نتيجه مي توان اينگونه بيان کرد که مقايسة بين الگوريتمهاي مختلف مي‌بايست بر مبناي پيش‌فرضهايي باشد که آن الگوريتمها براي انبارة جداسازها، در نظر گرفته‌اند.

موضوع بسيار مهمي که در الگوريتمهاي دسته‌بندي وجود دارد تقابل مابين حافظه و زمان مي‌باشد. در اکثر موارد يکي از اين دو فداي ديگري مي‌شود: بدان معني که الگوريتم فضاي بسيار زيادي را اشغال کرده و در کنارآن زمان معقولي را در اختيار قرار مي دهد (منظور از زمان، زمان جستجو مي‌باشد) مانند الگوريتم RFC و بالعکس، الگوريتمهايي وجود دارند که فضاي حافظه‌اي معقولي را اشغال‌کرده ولي زمان مناسبي را در اختيار قرار نمي‌دهند مانند الگوريتم جستجوي ترتيبي. در اين ميان، الگوريتمي به عنوان الگوريتم مناسب شناخته مي‌شود که توازني را در هردو ايجاد کند. به عبارتي مقدار تناسب زمان به حافظه را به يک نزديک کند. کاهش در بدترين زمان جستجو، همزمان با کاهش در بيشترين ارجاعات حافظه‌اي.

 

1.4.1 پارامترهاي کارايي

1. سرعت جستجو¹⁸: اتصالات سريعتر نياز به دسته‌بندي سريعتري دارند. به عنوان مثال اگر فرض کنيم که طول هر بستة TCP/IP حد اقل 40 بايت باشد، بر روي يک اتصال با سرعت 10Gbps، در هر ثانيه مي‌تواند 31.25 ميليون بسته از سيستم عبور کند که اگر نياز به پردازش داشته باشند مي‌بايست در هر 9-10 * 3 ثانيه، کار پردازش يک بسته، که شامل انجام عمل جستجو و انجام پردازش مربوط به جداساز مربوطه مي‌باشد، به اتمام برسد. در فرآيند پردازشِ يک بسته، زمانگيرترين قسمت، انجام عمل جستجو مي‌باشد .

2. نياز حافظه‌اي کمتر¹⁹: استفاده از فضاي حافظه‌اي کمتر امکان استفاده از تکنولوژيهاي حافظه‌اي سريعتر، در هنگامي که محدوديت به‌کارگيري سخت‌افزار وجود داشته‌باشد، را فراهم مي‌سازد. علاوه بر اين هر جا که دغدغة حافظه اشغالي، مطرح باشد اين پارامتر بسيار مهم خواهد بود.

3. توانايي مديريت انباره‌هاي بزرگِ واقعي²⁰: پارامتر مهم هر الگوريتم آن است که بتواند در محيط واقعي و در رؤيارويي با انباره‌هاي واقعي، که به صورت عملي مورد استفاده قرار مي‌گيرند، کارايي خود را نشان دهد. پاسخگويي مناسب به داده‌هاي آزمايشگاهي تنها جنبة تائيدي دارد.

4. به‌هنگام‌سازي سريع²¹: تغيير در انباره مستلزم به‌هنگام‌سازي ساختمان ‌داده‌هاي انباره خواهد بود. ما مي‌توانيم ساختمان‌ داده‌هاي مورد استفاده را طوري پيکربندي کنيم که توانايي حذف و اضافه جداسازها را به طور مکرر ( incremental ) داشته ‌باشند و يا به گونه‌اي باشند که ما نياز به ساخت دوبارة تمام ساختمان داده‌ها، از پايه، از اطلاعات موجود داشته باشيم. نرخ به‌هنگام‌سازي در برنامه‌هاي مختلف متفاوت است. به عنوان مثال به‌هنگام‌سازي با نرخ پايين براي ديواره‌هاي‌آتش ممکن است مناسب باشد چرا که جداسازها به وسيلة مديران سيستم و در مواقعي خاص و نادر، به‌هنگام مي‌شوند. در حاليکه يک مسيرياب با صف‌بندي به ازاي هر جريان، نياز به به‌هنگام‌سازي‌هاي متعدد خواهد داشت.

5. قابليت گسترش در تعداد فيلدهاي سرآيند بسته که براي دسته‌بندي استفاده مي‌شوند: اين موضوع انعطاف سيستم را نشان مي‌دهد ولي در مقابل پيچيدگي الگوريتم را بيشتر مي‌کند، چرا که افزايش اجزاء، به تنهايي، بار جستجو را افزايش مي‌دهد.

6. انعطاف پذيري در ارائه جداسازها²²: چنان که گفته شد شروط به صورتهاي پيشوندي و محدوده‌ايي مطرح مي‌شوند. الگوريتمها مي‌بايست از اين گونه نمايش اجزاءِ جداسازها، که جزوِ نمايشهاي عمومي به حساب مي‌آيند، پشتيباني کنند. در کنار آن امکان وجود نيازهاي خاص براي برنامه‌هاي کاربرديِ ويژه نيز وجود دارد ( بعنوان مثال دو پيشوند مجزا براي يک فيلد ) که الگوريتم مربوطه مي‌بايست از آن پشتيباني کند. البته اکثر الگوريتمها از نمايشهاي ويژه و مشخصي(بر اساس کاربردشان) حمايت مي‌کنند.

 

1.5 الگوريتمهاي دسته‌بندي

الگوريتمهاي دسته‌بندي را مي توان در چهار دستة کلي تقسيم‌بندي کرد:

1. الگوريتمهاي جستجوي پايه

2. الگوريتمهاي هندسي

3. الگوريتمهاي مکاشفه‌اي

4. الگوريتمهاي مختص سخت‌افزار

 

1.5.1 الگوريتمهاي جستجوي پايه²³

اين الگوريتمها از ساختمانهاي داده‌ايِ پايه به منظور حل مسئله استفاده مي‌کنند. ساده‌ترين رويکرد در اين حيطه جستجوي ترتيبي در ميان يک ليست پيوندي از جداسازها مي‌باشد. با دريافت يک بسته، سرآيندِ آن با تمام جداسازها مقايسه شده و با رسيدن به اولين تطابق فرآيند جستجو متوقف مي‌شود. اين روش از نظر حافظه‌اي بسيار کارا ولي در مقابل از نظر زماني بسيار ناکارآمد و دامنه گسترش آن بسيار محدود مي‌باشد، چرا که زمان جستجو به صورت خطي با افزايش تعداد قانونها، افزايش مي‌يابد .

رويکردهاي ديگر در اين حيطه از ساختمان دادة trie استفاده مي‌کنند. trie در اصل درختي از رشته‌هاي کاراکتري مي‌باشد که هر پيشوندِ مشترک در بين رشته‌ها، متناظر با يک راس در درخت مي‌باشد. به عنوان مثال مي توان براي رشته‌هاي X₁=100 و X₂=0 درخت زير را تشکيل داد (شکل 3.1 - يک trieِ يک بعدي). چنان که ديده مي‌شود trie در عالم دودويي يک درخت دودويي مي‌باشد که هر حرکت در يک جهت مشخص، متناظر با صفر و در جهت مخالف آن متناظر با يک مي‌باشد.

 

 

شکل 3.1 : نمايش trie يک بعدی

1.5.1.1 trieهاي سلسله‌مراتبي²⁴

trie سلسله‌مراتبيِ d بعدي، گسترش ساده‌اي از حالت يک بعدي مي‌باشد. براي ساخت آن ابتدا براي جزءِ اول، يکtrie يک بعدي ساخته مي‌شود . سپس متناظر با هر نود آن يک trie از جزء دوم و از قانونهايي ساخته مي‌شود که پيشوند متناظر با نود مورد نظر را در جزء يکم خويش، عينا، داشته باشند و همين گونه براي هر ند از trieهاي ايجاد شده براي جزء دوم اين عمل براي جزء سوم تکرار مي‌شود و....

با دريافت يک بسته با اجزاءِ سرآيند v_1,…,v_d، عمل جستجو از trie اول شروع مي‌شود. يافتن هر تطابق به معني يافتن trie بعدي براي انجام عمل جستجو مي‌باشد. در هر trie بر اساس مقدار متناظر با آن در سرآيند بسته عمل جستجو انجام مي‌شود. در صورت برخورد به بن‌بست بازگشت به يک سطح بالاتر انجام مي‌شود .

توضيح 1: چنانچه در توصيف trie سلسله‌مراتبي ذکر شد، هرtrie در هر سطح، متناظر با جزئي از سرآيند بسته مي‌باشد .

توضيح 2: trie تنها براي تطابق هاي پيشوندي استفاده مي‌شود و در صورت وجود تطابقهاي محدوده‌اي آنها را بايد به صورت پيشوندي بيان کرد .

پيچيدگيهاي اين الگوريتم عبارتند از: حافظه‌اي-، زماني-، به‌هنگام‌سازي- .

 

1.5.1.2 trieها با حرسِ مجموعه‌اي²⁵

دليل عمدة اتلاف زمان در trie سلسله‌مراتبي بازگشت به سطح بالاتر، در صورت برخورد به بن‌بست، مي‌باشد و اگر بتوان آن را حذف کرد زمان جستجو تا حد زيادي بهبود مي‌يابد. trie با حرس‌مجموعه‌اي به دنبال اين هدف مي‌باشد .

ساخت trie با حرس‌ِمجموعه‌اي همانندtrie سلسله‌مراتبي مي‌باشد با اين تفاوت که در هر نود از trie سطح بالاتر براي ساخت trie سطح پايين‌تر از تمام جداسازهايي که توانايي پذيرش پيشوند متناظر با اين نود را داشته باشند استفاده مي‌‌شود. به عبارتي هر نود در trie سطح پايين‌تر خودش، تمام جداسازهايي را که در تشکيل trie سطح پايين‌تر اجدادش دخيل مي‌باشند را شامل خواهد بود. بدين صورت در هنگام انجام عمل جستجو کافي است هر trie تطابق طولانيترين پيشوند را انجام دهد و در اين صورت ديگر نيازي به بازگشت به سطح بالاتر نخواهد بود.

اضافه شدن جداسازهاي اجداد در trie، فضاي اشغالي را در حد زيادي افزايش مي‌دهد. اصولا اين روش براي دسته‌بنديهاي ايستا مورد استفاده قرار مي گيرد .

 

پيچيدگيهاي اين الگوريتم عبارتند از: حافظه‌اي-، زماني-، به‌هنگام‌سازي- .

 

1.5.2الگوريتمهاي هندسي²⁶

رويکرد هندسي بارزترين مشخصة اين الگوريتمها مي‌باشد: تعبير فضاي مسئلة دسته‌بندي به صورت يک فضاي هندسي d بعدي و نمايش جداسازها به صورت فوق مستطيلها.

 

1.5.2.1 مشبکي ازtrieها²⁷

اين روش از فوائد trie سلسله‌مراتبي (حافظة مناسب) و trie با حرس‌مجموعه‌اي (زمان مناسب) بهره مي‌گيرد. ساخت trieها همانند trie سلسله‌مراتبي انجام مي‌شود (اين الگوريتم براي فضاي دو بعدي بيان شده‌است).

در نودهاي trie سطح دوم از وجود switchهايي بهره‌گرفته مي‌شود: بدين صورت که اگر هنگام انجام عمل جستجو به نقطه‌اي رسيديم که ديگر ادامه راه امکان نداشته باشد، switch مي‌تواند ما را به نود ديگري در trieهاي سطح دو منتقل کند تا ادامه مسير امکان‌پذير باشد. به شکل 4.1 توجه کنيد .

 

شکل 4.1 : مشبکی از trieها

شرط وجودb ( b يک switch است ) اين گونه است :

1. T_x و T_y دو trie جداگانه بر روي جزء دوم جداسازها مي‌باشند و ارجاع به آنها مي‌بايست توسط دو نود جداگانه درT انجام شود (T ، trie سطح يک مي‌باشد).

2. رشتة‌بيتي حاصل از گذر از ريشة T به سمت w در Tx، به اضافة مقدار بيت b ( بايد گفت که هر switch داراي يک برچسب²⁸ مي‌باشد : 0يا 1 ) مي‌بايست برابر با رشتة‌بيتي حاصل از گذر از مسير ريشة T به سمت x درTy باشد .

3. نود w نبايد داراي فرزندي با برچسب b باشد .

4. نود s درT بايد نزديکترين اجداد نود r باشد .

هنگام جستجو از تطابقِ طولانيترين طول پيشوند استفاده مي‌شود .

توضيح1: وجود switch به منزلة حرکت از يک فوق‌مستطيل به فوق‌مستطيل ديگري در فضاي d بعدي مي‌ياشد. چرا که ترکيب T با هر کدام از trieهاي سطح دوم يک فوق مستطيل را تشکيل مي‌دهد که شامل چندين زير فوق‌مستطيل که نمايشگر قانونها مي‌باشند، است .

اگر يک الگوريتم جستجو، در trieهاي سلسله‌مراتبي، نياز به جستجو در مسيرهاي U₁(s,root(T_y),y,x) و U₂(s, root(T_x), w,x) داشته ‌باشد، در اين حالت تنها نياز به جستجو در مسير ( s, root(T_x), w , x) خواهد بود.

توضيح 2: اگر براي رشته‌اي از بيتها قانوني وجود داشته باشد، در هرجايي که در هنگام جستجو، به بن‌بست رسيديم، مي‌بايست نود ديگري متعلق به جداساز ديگري (يا trie ديگري) وجود داشته باشد که بتوان از آنجا به کار ادامه داد. به عبارتي روش مشبک مسئله را به خوبي حل مي کند .

هر بيت در سرآيند بسته تنها يک بار امتحان مي‌شود، در نتيجه پيچيدگي   زماني الگوريتم و حافظة اشغالي  مي‌باشد.

وجود switchها از انجام به‌روز‌رسانيهاي پي‌درپي جلوگيري مي‌کند و در هر به‌روز‌رساني مي‌بايست کل درخت دوباره ساخته شود.

 

اصولا روش مشبک براي فضاي دو بعدي خوب کار مي‌کند و براي فضاهاي چند بعدي نيز مي‌تواند براي نمايش دو بعد آخر استفاده شود. بدين صورت پيچيدگي زماني براي فضاهاي چندبعدي با ضريب w کاهش مي يابد (چرا که در دو بعد آخر از هر مسيري که وارد شود تنها زمان براي يافتن لازم خواهد بود). حالت مشبک نيز همانند حالتهاي سلسله مراتبي و حرس‌مجموعه‌اي از نمايش پيشوندي براي بيان محدوده‌ها استفاده مي‌کند.

 

1.5.2.2 ساخت نشانه²⁹

اين روش براي جستجو در ابعاد مختلف طراحي شده که بسيار سريع مي‌باشد چرا که با دريافت هر بسته تنها نياز به انجام d عمل جستجوي محدوده‌اي متناظر با هر جزءِ جداسازها، خواهد بود.

در اين الگوريتم ابتدا جدولي از دو ستون ساخته مي‌شود: يکي شامل چندتايي حاوي محدوده‌ها و ديگري شامل بهترين قانون متناظر با فوق مستطيل حاصل از چندتايي محدوده‌ها. ابتدا هر بعد به وسيلة برشهايي به محدوده‌هايي تقسيم مي‌شود، اجتماع اين محدوده‌ها در تمام ابعاد چندتاييهايي به صورت ( r₁,…,r_d ) ايجاد مي‌کند که در آن r₁ مربوط به يکي از برشهاي بعد اول و ... مي‌باشند . سپس براي تمام ترکيبهاي محتمل از برشها (چندتاييها) بهترين قانون انتخاب مي‌شود.

با دريافت يک بسته عمل جستجوي محدوده‌اي در هر بعد، در ميان برشهاي متناظر با آن بعد براي يافتن محدودة حاوي آن مقدار انجام مي‌شود. سپس بر اساس جدول نشانه، جداساز متناظر با آن بسته استخراج مي‌شود.

 

از آنجايي که N پيشوند حداکثر 2- N2 محدوده را ايجاد مي‌کنند، پيچيدگي حافظه‌اي آن  و زماني  خواهد بود که در آن  زمان مربوط به جستجوي محدوده‌اي مي‌باشد.

هر به‌روزرساني مستلزم ساخت مجدد تمام جدول مي‌باشد، در نتيجه اين الگوريتم براي حالت ايستا مناسب خواهد بود.

 

1.5.2.3 درخت چهارتايي متناظر با فضاي مسئله³⁰

اين الگوريتم براي فضاي دوبعدي طراحي شده است. در هر نود دو بيت از هر دو جزء بررسي مي‌شوند، در نتيجه در هر ند فضاي مسئله به چهار قسمت مساوي تقسيم مي‌شود. هر نود داراي قانونهايي مي‌باشد که بتوانند يکي از چهار قسمت آن را به طور کامل پوشش دهند. هنگام جستجو در هر نقطه که امکان ادامه مسير وجود نداشت، از بين قانونهاي موجود بهترين تطابق انتخاب مي‌شود.کار تقسيم تا آنجا ادامه پيدا مي‌کند که در هر نود انتهايي حداکثر يک جداساز وجود داشته باشد.

 

1.5.3 الگوريتم هاي مکاشفه‌اي³¹

چنانچه در توصيف مسئلة دسته‌بندي نيز بيان شد، مسئلة دسته‌بندي با اجزاءِ چندگانه بسيار پيچيده و پرهزينه مي‌باشد. اين پيچيدگي و پرهزينه بودن راهنماي محققان براي استفاده از روشهاي مکاشفه‌اي بوده است. چرا که امکان نمايش انباره‌هاي موجود در شبکه‌هاي حقيقي، به دليل وجود ساختارهای ويژه و همچنين اضافات غير ضروري، به صورت نمايش مکاشفه‌اي وجود دارد.

 

1.5.3.1دسته بندي بازگشتي جريانها (RFC) ³²

فرض کنيد s بيت در سرآيند بستة شبکه وجود داشته باشد. مي‌توانيم با تشکيل جدولي همراه با ^s2 ورودي ، پردازش مربوط به هر بستة ورودي را به راحتي مشخص کنيم. مشکل اصلي اين راهکار حافظه اشغالي بسيار زياد آن مي‌باشد.

الگوريتم RFC سعي داردکه اين عمل را در فضايي يا جدولي با ^t2 سطر که در آن  و N تعداد قانونهاي موجود مي‌باشد، انجام دهد. آنچه در اين الگوريتم انجام مي‌شود ، ايجاد يک تطابق بين فضاي ^s2 و ^t2 مي‌باشد. اين الگوريتم با انجام يک سري عمليات مياني بر روي مقادير فيلدهاي مختلف(در سرآيند بستة دريافتی) که براي دسته‌بندي استفاده مي‌شوند، چنان تداعي مي‌کند که در فضايي با وسعت ^t2 کار مي‌کند .

 

1.5.3.2 برشهاي سلسله‌مراتبي هوشمند (HiCuts)³³

در هر مرحله از اين الگوريتم ، فضاي مسئله، در يک بعد، به چند قسمت برش خورده و اين عمل در هر زير فضاي ايجادشده تکرار مي‌شود.

حاصل اين برشها يک درخت تصميم‌گيري مي‌باشدکه هر نود درآن يک زير فضاي مسئله را پوشش مي‌دهد و فرزندان هر نود زير فضاهايي از فضاي ند پدر، حاصل از انجام برشها در فضاي نود پدر، را پوشش مي‌دهند.

مسائلي که در اين الگوريتم به صورت مکاشفه‌اي حل مي‌شوند عبارتند از:

1. انتخاب بعدي که مي‌بايست برش بر روي آن انجام شود .

2. تعداد برشهايي که مي‌بايست بر روي بعد انتخاب شده انجام شود .

 

1.5.3.3 جستجو در فضاي چندتايي³⁴

در اين الگوريتم ، ابتدا هر جداساز d بعدي به يک d تاي تبديل مي‌شود ، عضو iام از اين d تايي نمايندة طول پيشوند جزء iام جداساز خواهد بود. از آنجائي که مجموعة جداسازهايي که به يک dتاي تبديل شده‌اند داراي طول پيشوند مساوي در اجزاءِ متناظر مي‌باشند، مي‌توان آنها را به صورت جداول درهم‌ساز³⁵ ذخيره کرد.

در نتيجه اگر فرض کنيم حاصل تبديل جداسازها به dتاييها، M تا dتايي مجزا باشد، الگوريتم داراي M جدول درهم‌ساز خواهد بود که در هر جدول جداسازهاي داراي طول پيشوند مساوي در اجزاءِ متناظر، ذخيره شده‌اند. جستجو به صورت تطابق عيني در تمام جداول انجام مي‌شود .

 

پيچيدگي زماني مربوط به اين الگوريتم برابر M جستجو در جداول درهم‌ساز مي‌باشد و همچنين پيچيدگي حافظه‌اي آن از رتبة  مي‌باشد، چرا که هر قانون دقيقا در يک جدول ذخيره مي‌شود.

هزينة به‌هنگام‌سازي آن تنها در حد اضافه کردن يک جداساز به جدول درهم‌ساز مربوطه مي‌باشد.

 

در صورت وجود تعداد کم چندتاييها (جداول درهم‌ساز) اين الگوريتم کارآيي خوبي براي دسته‌بندي بسته‌ها بر اساس اجزاءِ چندگانه خواهد داشت.

 

1.5.4 الگوريتمهاي مختص سخت‌افزار³⁶

به دو صورت مي‌باشند: يا سخت‌افزارهاي خاصي هستند که براي انجام عمل دسته‌بندي بسته‌ها مورد استفاده قرار مي‌گيرند و يا الگوريتمهايي مي‌باشند که بر اساس تواناييهاي خاص سخت‌افزاري مشخص گسترش يافته‌اند. در هر دو صورت به دليل استفادة مستقيم از سخت‌افزار، اين شيوه‌ها سرعت قابل قبولي را در اختيار قرار مي‌دهند. اما در کنار آن به دليل محدوديت حجم و همچنين تعداد فيلدهاي کمي که پشتيباني مي‌کنند، کارآيي خوبي براي انباره‌هاي بزرگِ واقعي نخواهند داشت. عمدة اين مشکلات است که روشهاي نرم‌افزاري را به عنوان انتخالي مطمئن مطرح مي‌سازد.

 

1.5.4.1 Ternary CAMها³⁷

يک TCAM مقادير w بيتي را به صورت ( مقدار، ماسک) ذخيره مي‌کند، مقدار و ماسک هر دو w بيت پهنا دارند. به عنوان مثال اگر مقدار پهنا 5 باشد (w = 5) ، پيشوند 10* به صورت (مقدار10000، ماسک . 11000 ) بيان مي‌شود.

TCAM در فضاي آرايه‌اي خودش، جداسازها را به ترتيب نزولي بر اساس اولويتشان ذخيره مي‌کند. عمل مقايسه براي يافتن تطابق به صورت موازي با تمام عناصر آرايه انجام مي‌شود. حاصل يک بيت‌نقش N بيتي از تطابقهاي صورت پذيرفته خواهد بود. توسط قسمت اولويت‌بندي، جداسازِ با بالاترين اولويت انتخاب مي‌شود. TCAM براي ذخيرة پردازشِ مربوط به يک قانون از آدرس پردازش که در RAM ذخيره شده است، استفاده مي‌کند و در صورت بروز تطابق با استفاده از اين آدرس، پردازشِ مربوطه فراخواني مي‌شود.

سادگي و سرعت TCAMها از جمله مزيتهايي مي‌باشد که استفاده از آنها را روزبه‌روز افزايش مي‌دهد. البته در کنار آن توان مصرفي بالا ( به دليل انجام مقايسه به صورت موازي با تمام عناصر آرايه) و پشتيباني نکردن از محدوده‌ها، از جمله کاستيهاي آن به شمار مي‌آيد.

 

1.5.4.2 اشتراک‌ بيت‌نقشها³⁸

فرض کنيد S، مجموعة جداسازهايي باشدکه مطابق با يک بستة دريافتي مي‌باشند. اگر مجموعه‌هاي S_i را شامل جداسازهايي در نظر بگيريم که در جزء iام از سرآيند بسته، مطابق بستة دريافتي باشند، آنگاه مي‌توان مجموعة S را اينگونه به دست آورد .

ايدة اصلي در اين روش نيز بر اين مبنا استوار است. جداولي براي هر بعد تشکيل مي‌شوندکه متناظر با هر محدوده در آن بعد، بهترين جداسازهاي متعلق بدان را به صورت يک بيت نقش N بيتي ذخيره مي‌کند. جستجو براي هر جزء، به صورت جداگانه، در جدول مربوط بدان انجام شده و در پايان از تمام بيت‌نقشهاي حاصل اشتراک گرفته مي‌شود. حاصل نمايانگر جداسازهايي خواهد بود که مطابق بسته هستند.

 

اين روش براي ابعاد کم جوابگو مي‌باشد اما نياز حافظه‌اي آن به صورت توان 2 و نياز زماني آن به صورت خطي با افزايش اندازة انباره افزايش مي‌يابد.

 

جستجو با انجام تطابقهاي محدوده‌اي در هر بعد صورت مي‌پذيرد، حاصل تمام آنها بيت‌نقشهاي N بيتي خواهد بود که به مدد سخت‌افزار، اشتراک‌گيري ( عمل AND ) از آنها مي‌تواند بسيار سريع انجام شود.

 

2 الگوريتم ABV ³⁹

در تقسيم‌بندي الگوريتمهاي دسته‌بندي، اين الگوريتم را مي‌توان در رستة الگوريتمهاي جستجوي پايه قرار داد. اين الگوريتم که نسخة گسترش يافته‌اي از الگوريتم BV مي‌باشد از طرف سازندگانش با نام الگوريتم قابل گسترش معرفي شده است که مي‌تواند انباره‌هايي تا 100،000 قانون را پوشش دهد.

اين الگوريتم سعي کرده است با استفاده از ايدة اجماع ، که ابتکار سازندگان اين الگوريتم به‌حساب مي‌آيد، زمان جستجوي الگوريتم BV را بهبود بخشد.

 

2.1 الگوريتم BV ⁴⁰

روش کار BV شبيه به روش اشتراک بيت‌نقشها مي‌باشد، بدان صورت که ابتدا سعي مي‌کند تا قانونهاي مطابق هز جزءِ سرآيند را به صورت جداگانه جستجو کند و سپس با اشتراک گرفتن از حاصل اين جستجوها، قانونهايي را که با کل بسته مطابق هستند استخراج کند.

نقطة اشتراک اين دو استفاده از بيت‌نقشها مي‌باشد که براي نمايش حاصل جستجوهاي جداگانه و استخراج نهايي، مورد استفاده قرار مي‌گيرند، و نقطة تفاوت آنها نيز استفاده از ساختمان دادة trie در الگوريتم BV به جاي ساختمان دادة جداول در الگوريتم اشتراک‌ بيت‌نقشها مي‌باشد. استفاده از trie امکان به‌روزرساني پي‌درپي را براي الگوريتم فراهم کرده و درکنار آن استفاده از بيت‌نقشها نيز منجر به استفاده از فوائد سخت‌افزاري شده است، چرا که با هر دسترسي به حافظه تعداد زيادي بيت واکشي مي‌شوند.

از آنجايي که الگوريتم BV فضاي مسئله را به d مسئلة کوچکتر تقسيم ميکند (d تعداد فيلدهاي سرآيند مي‌باشند که براي دسته‌بندي مورد استفاده قرار مي‌گيرند) مي‌توان آن را جزو الگوريتمهاي "تفرقه بيانداز-حکومت کن⁴¹" در نظرگرفت. طرز کار الگوريتم BV بدين گونه مي‌باشد که ابتدا براي هر جزء از اجزاءِ جداسازها، يک trie يک بعدي، که نمايشگر تمام پيشوندهاي ممکن مي‌باشد، ساخته مي‌شود، براي اجزايي که از تطابقهاي محدوده‌اي استفاده مي‌کنند فرض بر آن است که يا از درخت محدوده‌اي و يا، با تبديل به پيشوند، از trie براي نمايش آنها استفاده مي‌شود.

متناظر با هر نودِ هر trie ( تا اينجا ما d تا trie داريم ) يک بردار N بيتي (تعداد قانونها) در نظر گرفته مي‌شود. يک بودن موقعيت j در اين بردار، در يک نود مفروض، به منزلة تطابق پيشوند مربوط به اين نود با پيشوند جزء متناظر در قانون jام مي‌باشد و يا به عبارتي جزءِ متناظر در قانون jام، اين پيشوند را نيز پوشش مي‌دهد( به عنوان مثال پيشوند 00* توسط پيشنوندهاي 0* و 00* پوشش داده مي‌شود).

با دريافت يک بسته با اجزاءِ سرآيند H₁,….,H_d ، جستجو در trieهاي متناظر با هر جزء براي يافتن طولانيترين پيشوند مطابق با آن صورت مي‌پذيرد. حاصل جستجوها d بردار N بيتي خواهد بود. سپس از تمام اين بردارها اشتراک گرفته مي‌شود. حاصل بيان‌کنندة قانونهايي خواهد بود که تمام اجزاءِ سرآيند را پوشش مي‌دهند.

عمل بعدي يافتن مناسبترين قانون با پايين‌ترين هزينه يا بالاترين اولويت، مي‌باشد. پيچيدگي عمل جستجو که نياز به سير خطي در درون بيت نقش N بيتي دارد از مرتبة  مي‌باشد و اگر w را به عنوان طول واحد کلمة حافظه در نظر بگيريم، تعداد دسترسيها به حافظه در هنگام اشتراک گرفتن که جستجو نيز همزمان با آن انجام مي‌شود،  خواهد بود.

 

2.2 ايدة اجماع

هدفي که از ايدة اجماع دنبال مي‌شود ساخت بردار اشتراک و به عبارتي يافتن قانون مناسب بدون نياز به بررسي تمام مقادير مربوط به بيت‌نقشهاي حاصل از انجام عمل جستجو در trieهاي متناظر با هر جزء مي‌باشد.

براي اين منظور با هر نود، بردار ديگري با نام بردار اجماع همراه مي‌شود. بيت i در بردار اجماع يک خواهد بود اگر بيتي در محدودة  در بردار بيتي مربوط بدان نود يک باشد. A به عنوان عدد اجماع، به صورت يک عدد ثابت در الگوريتم مورد استفاده قرار مي‌گيرد، که معمولا مساوي w (اندازة کلمة حافظه) در نظر گرفته مي‌شود. اندازة بردار اجماع برابر مي‌باشد. با دريافت يک بسته، ابتدا از بردارهاي اجماع اشتراک گرفته مي‌شود. با استفاده از حاصل اشتراک، تنها قسمتهايي از بيت‌نقشها امتحان خواهند شد که بيت متناظر با آنها در بردار اجماع يک باشد.

در اين الگوريتم از اجماع چندسطحي نيز صحبت به ميان آمده است. بدان صورت که براي بردارهاي اجماع فعلي نيز بردار اجماع سطح بالاتري ساخته شود. با انجام اين عمل تا هنگامي که انجام آن مقدور باشد (حداقل A بردار اجماع موجود باشد) درختي با ارتفاع حاصل خواهدشد. بدين صورت در هنگام بررسي بردارهاي اجماع نيز، نياز به بررسي تمام آنها نخواهد بود چرا که بردارهاي اجماع سطح بالاتر قسمتي از بردارهاي سطح فعلي را از گردونة توجهات حذف مي‌کنند. هدف رسيدن به حالتي مي‌باشد که پيچيدگي دسترسي به حافظة آن از مرتبة باشد.

 

2.2.1 تطابق هاي نادرست

ايدة اجماع مي‌تواند حالاتي را سبب شود که تعداد دسترسي به حافظه چند برابر زماني باشد که از بردارهاي اجماع استفاده نمي‌شود. اين حالت هنگامي رخ مي‌دهد که دربين محدوده‌هاي متناظر با مکانهايي، در بردار اجماع، که عدد يک را اختيار کرده‌اند، اشتراکي وجود نداشته باشد. اين واقعيت از آنجا ناشي مي‌شود که يک مکان در بردار اجماع يک خواهد بود اگر در محدوده‌اي به طول A ، در بيت نقش متناظر، حداقل يک، يک وجود داشته باشد. اين يک مي‌تواند، در بردارهاي مختلف، مکانهاي مختلفي را اختيار کند. اين حالت با نام تطابق نادرست⁴² شناخته مي‌شود.

تطابقهاي نادرست هنگامي رخ مي‌دهند که قانونهايي که يک جزء را پوشش مي‌دهند در ترتيب ارائه شده از قانونها به صورت پراکنده قرار گرفته باشند. براي رفع آن مي‌توان ترتيب جداسازها را به گونه‌اي تغيير داد که قانونهاي مطابق با يک جزء در کنار يکديگر قرار بگيرند، تا بدين صورت از پراکندگي آنها جلوگيري شود.

 

2.3 توصيف الگوريتم ABV

در اين الگوريتم نيز همانند الگوريتم BV براي هر يک از اجزاءِ جداسازها، يک trie يک بعدي ساخته مي‌شود، البته با اين تفاوت که از بردارهاي اجماع نيز در هر نود استفاده مي‌شود. عمق بردارهاي اجماع قابل تصميم‌گيري مي‌باشد.

جستجوي اجماع: با دريافت يک بسته، جستجو در trieها به صورت جداگانه انجام مي‌شود و سپس از بردارهاي اجماع، اشتراک گرفته مي‌شود. اگر در حاصل اشتراک بيتي در موقيت i يک باشد، آنگاه عمل اشتراک‌گيري از بيتهاي واقع شده در محدودة در درون بيت‌نقشها، انجام مي‌شود. اگر در مجموع اين اعمال، بيتي يک باشد نشانگر وجود يک تطابق خواهد بود.

بعد از اتمام عمل اشتراک‌گيري، از بين قوانين مطابق با بسته، قانون با بالاترين اولويت انتخاب مي‌شود.

الگوريتم مرتب‌سازي: مرتب‌سازي در يک جزء بدين صورت انجام مي‌شود که در ابتدا تمام پيشوندها به ترتيب اندازه مرتب مي‌شوند. سپس در بين آنها بر اساس تساوي پيشوندها، مرتب‌سازي انجام مي‌شود. حاصل ترتيبي از قانونها خواهد بود که بر اساس مقادير يک جزء مرتب شده‌اند.

به همين صورت مي‌توان قانونهايي را که داراي پيشوند مساوي در يک جزء هستند را بر اساس مقادير جزء ديگري مرتب کرد. اين عمل مي‌تواند براي هر چند تا جزء به صورت بازگشتي ادامه يابد. بر طبق اين الگوريتم مي‌توان توالي اجزاء استفاده شده براي مرتب‌سازي را به صورت دلخواه انتخاب و به عبارتي اولويت‌بندي کرد.

 

3 الگوريتم HyperCuts

دسته بندي بسته‌ها با استفاده از برشهاي چندگانه ( HyperCuts ) جزو رستة الگوريتمهاي مکاشفه‌اي در تقسيم‌بندي الگوريتمهاي دسته‌بندي قرار مي‌گيرد.

الگوريتم HyperCuts که نسخة گسترش‌يافته‌اي از الگوريتم HiCuts مي‌باشد، با ايجاد امکان انجام برشهاي چندگانه سعي کرده، تا با رهايي از محدوديت برشهاي يک بعدي در HiCuts، سرعت الگوريتم را تا حد قابل توجهي بهبود بخشد. اين موضوع به HyperCuts امکان شبيه‌سازي چندين برش HiCuts(توالي برشها در چند سطح) در يک برش(انجام تمام برشها در يک سطح) را مي‌دهد.

HyperCuts همچنين از شيوة بالاراندن قوانين در درخت تصميم‌گيري، براي بهبود حافظة اشغالي، استفاده مي‌کند، چرا که جداسازهاي داراي جواز اغلب در چندين برگ درخت تصميم‌گيري تکرار مي‌شوند که اين موضوع حافظة اشغالي را افزايش مي‌دهد. براي رهايي از آن تمام قوانين مشترک در يک زير درخت ، به صورت يک ليست خطي، در ريشة آن درخت ذخيره مي‌شوند تا از تکرار آنها در برگها جلوگيري شود.

 

3.1 الگوريتمهاي مبتني بر درخت تصميم‌گيري⁴³

نقطة تشابه الگوريتمهاي مبتني بر درخت تصميم‌گيري، اتخاذ تصميمات بهينه‌شده يا بهينه در هر نود درخت تصميم‌گيري (در هنگام ساخت و استفاده از آنها در هنگام جستجو) براي ادامة مسير مي‌باشد. اين نوع الگوريتمها، اولين مرتبه، در دو مقاله براي الگوريتمهاي HiCuts و Woo مطرح شدند.

در الگوريتم Woo تصميم بهينه شدة محلي منجر به انتخاب بيت بعدي براي تست و در HiCuts منجر به انتخاب جزء يا بعدِ بعدي براي آزمايش و برش مي‌شود. در هر صورت در هر دو الگوريتم بعد از اِعمال تصميم در هر ند، فضاي مسئله به زير مجموعه‌هاي کوچکتري تقسيم مي‌شود و دوباره عمل تصميم‌گيري به صورت بازگشتي بر روي اين مجموعه‌ها اعمال مي‌شود، تا رسيدن به نقطه‌اي که هر برگ درخت شامل تعداد معقولي قانون باشد.

در هنگام جستجوي تطابق براي يک بسته، در هر نود، تعلق بسته به زير مجموعه‌ها بررسي مي‌شود تا يکي از فرزندان براي ادامة مسير انتخاب شود و اين عمل تا رسيدن به برگ ادامه پيدا مي‌کند. بعد از جلوس در يک برگ، قانونهاي موجود در آن به صورت ترتيبي، براي پيدا کردن قانون با بالاترين اولويت، جستجو مي‌شوند.

در اين الگوريتمها چند موضوع قابل توجه است:

1. تقسيم مجموعه يا فضاي جداسازها به زيرمجوعه‌ها مؤيد اين مطلب نيست که هر قانون تنها در يک زيرشاخه قرار مي‌گيرد، چرا که جداسازهايي که داراي جواز زياد در اجزايشان باشند، مي‌توانند به صورت مکرر در زير شاخه‌هايِ مختلف تکرار شوند. در الگوريتم Woo براي رهايي از اين مسئله اجازة استفاده از چند درخت تصميم‌گيري داده شده است. بدين صورت قادر خواهيم که به عنوان مثال براي تمام جداسازهايي که مقدار آدرس مبدا و مقصد آنها به صورت جواز مي‌باشد يک درخت جداگانه بسازيم. اين مسئله اگر چه باعث کندي الگوريتم مي‌شود اما به اندازة قابل توجهي فضاي اشغالي را کاهش مي‌دهد.

2. استفاده از تعداد معقولي قانون در برگها: فرض کنيد درخت تصميمگيري داراي 10.000 برگ باشد که هر کدام تا 4 قانون را در خود نگهداري مي‌کنند. اگر بخواهيم تقسيم‌بندي را تا آنجا ادامه دهيم که در هر برگ تنها يک قانون قرار داشته باشد ما نياز به 40.000 نود اضافي خواهيم داشت که اين موضوع به خوبي مؤيد افزايش تواني فضاي اشغالي مي‌باشد. بنابراين استفاده از تعداد معقولي جداساز در برگها باعث ايجاد توازن بين حافظه و زمان مي‌شود.

3. موضوع بعدي انجام تصميمات بهينه مي‌باشد. لازمة انجام اين مورد دسترسي به تعدادي قانون در هنگام ساختن درخت مي‌باشد. در اين هنگام خواهد بود که درخت با توجه به فضاي حافظه‌اي موجود، ساختار قانونها و عدد تعدادِ معقول ( حداکثر قانونهاي موجود در برگها ) قادر به تصميمگيري و ساختن درخت خواهد بود. در نتيجه اين الگوريتمها در حد زيادي وابسته به فضاي حالت قانونها مي‌باشند.

 

3.2 الگوريتم HiCuts

‌در درخت الگوريتم HiCuts ، هر نود را مي‌توان به صورت يک جعبة d بعدي که توسط برشهايي به يک مجموعة nc-جعبه‌اي تقسيم مي‌شود، در نظر گرفت. تطابقها در HiCuts از نوع محدوده‌اي هستند و تطابقهاي پيشوندي نيز تبديل به تطابقهاي محدوده‌اي مي‌شوند. جستجو بر اساس تعلق بسته به محدوده‌هاي متعلق به هر نود، از ريشه شروع و تا رسيدن به برگها ادامه مي‌‌يابد.

اندازة جعبه بستگي به محدوده‌هايي دارد که توسط جعبه در هر بعد پوشش داده ميشود. به عنوان مثال در پنج‌تاييِ ( آدرس مبدا، آدرس مقصد، پورت مبدا، پورت مقصد، پروتکل ) جعبه را مي‌توان به صورت در نظر گرفت.

هر جعبه در برگيرندة تعدادي قانون خواهد بود که با آن اشتراک محدوده‌اي دارند.در هر نود دو مسئله مطرح مي‌باشد:

1. تعداد برشها: که انتخاب آن منجر به بروز تقابل بين ارتفاع درخت و فضاي اشغالي مي‌شود.

2. بعدي که برش برروي آن بايد اعمال شود: تا تعداد حداکثر قانونهاي موجود در هر برش به حداقل برسد.

الگوريتم اين دو موضوع را بر اساس دو پارامتر binth و spfac مديريت مي‌کند. Binth که متناظر با عدد تعداد معقول مي‌باشد و مقدار جستجوي خطي را محدود مي‌کند و spfac که يک ضريب است که مقدار فضاي اضافه شده توسط برشها را محدود مي‌کند. اگر برش بر روي بعدي انجام شود که جداسازهاي داراي مجوز در آن زياد باشند، تکرار مکرر اين جداسازها در برگهاي درخت باعث اشغال بيش از نياز فضاي حافظه خواهد شد و همچنين افزايش در تعداد برشها شايد باعث کاهش تعداد جداسازهاي متعلق به هر زير مجموعه شود ولي اين موضوع حجم نود مرجع را چند برابر خواهد کرد.

براي ساخت درخت، بر اساس توضيحاتي که داده شد، در هر نود ( با شروع از ريشه ) بر اساس ساختار جداسازهاي موجود در آن نود ( که در نود ريشه تمام انباره خواهد بود ) بعدِ برش و تعداد برشها انتخاب مي‌شوند. سپس در هر يک از نودهاي فرزند، اگر تعداد قانونها بيش از عدد تعداد معقول باشد، عمل تقسيم به صورت بازگشتي در آن نيز اجرا مي‌شود. حاصل درختي خواهد شد که تعداد قانونهاي موجود در برگها، حداکثر به اندازة تعداد معقول مي‌باشد.

 

3.3 تقابل بين HiCuts و HyperCuts

HiCuts يک درخت تصميم‌گيري را، بر اساس تصميمات بهينه شدة محلي در هر نود، با انتخاب بعد برش و تعداد برشها مي‌سازد. برگها شامل ليستي از قوانيني مي‌باشند که امکان تطابق آنها در مسير جستجو تا برگ وجود دارد.

HyperCuts با برداشتن محدوديت حاکم بر Hicuts ( برش در يک بعد ) ، آزادي عمل، براي انتخاب چندين بعد براي آزمون را، به ما مي‌دهد. براي هر بعد انتخاب شده، تعداد برشها بر اساس حافظه‌اي که در اختيار ساختار جستجو قرار دارد انتخاب مي‌شود. با توجه به انجام برشهاي چندگانه ارتفاع درخت تصميم‌گيري به نسبت درخت حاصل از الگوريتم HiCuts کاهش مي‌يابد.

انجام برشهاي چندگانه بر روي سطوح چندگانه مي‌تواند باعث کندي عمل جستجو در هر نود براي يافتن مسير بعدي شود. HyperCuts براي مقابله با آن از index، به منظور دستيابي و تشخيص آسان محدوده‌ها به هنگام عمل جستجو استفاده مي‌کند. بدين صورت که: اگر يک محدوده را به چند محدودة مساوي تقسيم کنيم، قادر خواهيم بود با يک عمل تقسيم که در سخت افزار مي‌تواند بايک يا چند جابه‌جايي⁴⁴ انجام شود، index مناسب را پيدا کنيم. کافي است مقداري که بايد عضويت آن در محدوده‌ها بررسي شود، بر پهناي محدوده‌هاي برش‌خورده تقسيم و از مقدار کف خارج قسمت براي مقدار index استفاده کنيم ( به عنوان مثال براي برشهاي 14-10، 9-5، 4-0، index مربوط به عدد 6 بدين صورت بدست مي‌آيد 1= ).

با استفاده از آرايه‌ها عمل جستجو تنها به يک دستيابي به حافظه، مستقل از تعداد برشها محدود مي‌شود. در نتيجه با انجام برشهاي چندگانه، ضمن حصول به درختي با ارتفاع محدودتر نسبت به HiCuts که دستيابي سريعتر به جواب را نويد مي‌دهد، با اتخاذ سيساست مناسب، بار حاصل از انجام برشهاي چندگانه در ابعاد گوناگون، بر روي فرآيند جستجو،کاهش داده مي‌شود.

البته استفاده از آرايه بدين صورت مي‌تواند فضاي اشغالي را به دليل وجود اشاره‌گرهاي تکراري و يا خالي به هدر دهد. مي‌توان با جلوگيري از ساخت زيردرختهاي تکراري ( براي کاهش مکانهاي غير مفيد در آرايه ) و بالا راندن قوانين مشترک در درخت تصميم‌گيري ( کاهش فضاي اشغالي ) مسئله را تاحد زيادي تلطيف کرد.

نکتة ديگر اينکه وجود برشهاي چندگانه به خودي خود باعث افزايش فضاي اشغالي مي‌شود، چرا که اگر فرض کنيم در يک درخت HiCuts براي يک انبارة مفروض، از دو برش بر روي بعد اول در ريشه استفاده کنيم که حاصل آن دو فرزند Aو B باشد، آنگاه براي A از هشت برش بر روي بعد دوم و براي B از دو برش بر روي بعد سوم استفاده شود، فضاي اشغالي توسط HiCuts از رتبة 12=2+8+2 خواهد بود. ولي اگر تمام اين برشها را در نود ريشة درخت HyperCuts انجام دهيم حافظة اشغالي از رتبة 32=2*8*2 خواهد بود. اما HyperCuts مي‌تواند با شبيه‌سازي HiCuts در مواردي که حافظه کم است از انجام برشهاي چندگانه جلوگيري کند.

بر طبق پيشنهاد سازندگان اين الگوريتم، درجة آزادي بيشتر در HyperCuts به طور مؤثر براي مسيريابهاي هسته بيشتر مفيد مي‌باشد تا مسيريابهاي گوشه.

 

3.4 توصيف الگوريتم HyperCuts

HyperCuts يک الگوريتم بر پاية درختهاي تصميم‌گيري مي‌باشد. عمل برش در هر نود بر اساس اطلاعات موجود در يک يا چند جزء انجام مي‌شود. در هنگام دريافت يک بسته، عمل جستجو تا رسيدن به يک برگ ادامه پيدا مي‌کند و سپس جستجوي ترتيبي در بين قانونهاي موجود در برگ براي يافتن جداساز با بالاتري اولويت انجام مي‌شود.

هر نود در درخت HyperCuts مي‌تواند شامل موارد زير باشد:

1. يک محدودة که توسط آن نود پوشش داده مي‌شود.

2. تعدادي برش و اشاره‌گرهايي⁴⁵ به نودهاي مربوط به آنها.

3. ليستي از قانونهايي که امکان تطابق با آنها وجود دارد، تعداد حداکثر قانونهايي که مي‌تواند در يک نود ذخيره شوند از پيش تعيين شده است.

توصيف الگرويتم HyperCuts شامل توصيف دو الگوريتم مي‌باشد: الگوريتم مربوط به ساخت درخت بر اساس جداسازهاي موجود⁴⁶ در انباره و الگوريتم مربوط به جستجوي درخت براي يافتن تطابق مربوط به بستة دريافتي.

 

3.4.1 پيش فرضهاي حاکم بر درخت تصميم‌گيري

1. درخت تصميم گيري بايد سعي کند که در هر نود (مرحله) تا حد امکان قانونهاي بيشتري را از گردونة توجهات حذف کند (با انجام برشهاي مناسب).

2. حداکثر تعداد مراحل که براي يک جستجو مي‌بايست اتفاق بيافتد، بايد حداقل شود (کاهش در ارتفاع درخت).

3. بعضي قوانين وجود دارند که بررسي آنها يا دسته‌بندي آنها بدون افزايش پيچيدگي الگوريتم ( زماني و حافظه‌اي ) امکان‌پذير نيست. بنابراين يک روش جدا براي پردازش آنها بايد وجود داشته‌باشد (اين جداسازها آنهايي مي‌باشند که داراي جواز هستند، به عنوان راه حل مي‌توان از دو درخت استفاده کرد).

4. در بين تمام الگرويتمهاي دسته‌بندي تقابلي ما بين فضاي اشغالي و زمان جستجو وجود دارد، چنانکه در الگوريتمهاي مربوط به درخت تصميم‌گيري در تعداد قانونهاي کمتر برتري محسوسي در جستجوي ترتيبي نسبت به آنها احساس مي‌شود. بنابراين اين شرايط را مي‌پذيريم که يک نود تا هنگامي که تعداد قانونهاي موجود درآن، از يک حد کمتر باشد ( آن حد را اندازة سبد⁴⁷ مي‌نامند که متناظر با عدد تعداد معقول مي‌باشد ) عمل شکست (برش) در آن انجام نشود.

الگوريتم HyperCuts با انجام اعمال زير سعي مي‌کند مفروضات ذکر شده را برآورده کند:

1. ابتدا ابعادي را که داراي بيشترين تعداد مقادير جدا هستند انتخاب مي‌کند.

2. براي ابعاد انتخاب شده، بر اساس تقابل بين فضاي موجود و عمق درختي که بايد حاصل شود، تعداد برشها را تعيين مي‌کند.

3. برشها را انجام داده و تعداد nc فرزند را متناظر با nc برش را ايجاد مي‌کند، برشهاي بيشتري انجام نخواهد شد اگر که تعداد جداسازهاي موجود در هر ند از عدد اندازة سبد کوچکتر باشد.

 

3.4.2 ساخت درخت HyperCuts

انتخاب ابعاد: چالش اصلي انتخاب ابعادي مي‌باشد که بيشترين يکنواختي را در تعداد جداسازهاي موجود در برشها و همچنين بهترين پراکندگي قانونها در برشها را باعث شوند. نبود راه‌حلي کامل و مناسب، راهنمايي به سمت استفاده از روشهاي مکاشفه‌اي مي‌باشد. آنچه که به عنوان اولين رويکرد در نظر گرفته مي‌شود، انتخاب مجموعه‌اي از ابعاد مي‌باشد که داراي بيشترين تعداد مقادير يکتا باشند. توجه به اين رويکرد بدون لحاظ توجهات اضافي باعث خواهد شد که تمام ابعاد به عنوان يک مجموعه انتخاب شوند چرا که هر بعد مقاديري يکتا را، هر چند اندک، به مجموعة فعلي اضافه مي‌کند. اين موضوع پيچيدگي الگوريتم را با توجه به استفاده از آراية چند بعدي براي ذخيره‌سازي indexها، بالا مي‌برد و در ضمن اضافه کردن بعدي که تعداد ناچيزي مقدار يکتا را به مجموعه اضافه مي‌کند بهبود قابل توجهي را در الگوريتم موجب نمي‌شود چرا که پراکندگي قانونهاي تقسيم شده به وسيلة آن به صورت انباشته مي‌باشد که از فرض پراکندگي يکنواخت تبعيت نمي‌کند و بيشتر مؤيد جستجوي ترتيبي مي‌باشد.

به عنوان دومين رويکرد ابعادي انتخاب مي‌شوند که تعداد مقادير يکتاي آنها بيشتر از ميانگين مقادير يکتا در تمام ابعاد مي‌باشد. حال اگر دو بعد داراي مقادير يکساني، در تعداد عناصر يکتا، بودند هر دو انتخاب مي‌شوند اما بعدي به عنوان اولين برش استفاده مي‌شود که نسبت تعداد مقادير يکتاي آن به پهناي محدوده‌اش بيشتر باشد ( به عبارتي اندازة محدوده‌اش يا بعدش کوچکتر باشد )، چرا که تقسيمات آن محدوده‌هايي کوچکتر را تشکيل مي‌دهند. به طور مستندتر مي‌توان نسبت تعداد مقادير يکتا بر پهناي برشهاي حاصل ( تعداد عناصر موجود در برشها ) را به عنوان مشخصة اولويت بيان کرد.

انتخاب تعداد برش: قدم بعدي انتخاب تعداد برشها مي‌باشد، در اينجا مي‌بايست براي هر يک از ابعاد انتخاب شده j=1,….,N عدد nc_j که مشخص‌کنندة تعداد برش در بعد jام مي‌باشد را تعيين کنيم. براي کنترل حافظة اشغالي به طبع الگوريتم HiCuts، محدوديتي بر تعداد فرزندان نود فعلي اعمال مي‌شود، بدين صورت که تعداد فرزندان حاصل از انجام برشها مي‌بايست کمتر از باشد. N تعداد قانونهاي موجود در نود فعلي بوده و spfac مشخصة برطرف کنندة تقابل بين زمان و حافظه مي‌باشد. تعداد کل برشها خواهد بود که در آن D شامل تمامیِ ابعاد انتخاب شده مي‌باشد. اين تعداد کل مي‌بايست کمتر از مقدار باشد.

از بين تمام مجموعه هاي محتمل {nc_i}، آن مجموعه که داراي بهترين پراکندگي و کمترين حافظة اشغالي باشد انتخاب مي‌شود.

از آنجايي که بررسي تمام حالات ممکن اين مجموعه ناممکن است از يک روش حريسانه⁴⁸ براي دستيابي به بهترين مجموعه استفاده مي‌شود. بدين صورت که: ابتدا به صورت مجزا براي هر بعد i يک عدد بهينة تعيين و سپس بهترين ترکيب با محوريت قرار دادن اين اعداد انتخاب مي‌شود. براي مقايسة مقادير مختلف از پارامترهاي زير استفاده مي‌شود(اين پارامترها به فرض انجام اين تعداد برش در بعد مفروض و با نگاه به فرزندان حاصل تنظيم شده‌اند):

1. تعداد متوسط جداسازهاي موجود در فرزندان ( هر چه کمتر )

2. تعداد حداکثر جداسازهاي موجود در فرزندان ( هر چه کمتر )

3. تعداد فرزندان تهي ( هر چه کمتر )

در يک فرآيند تکراري، در هر مرحله مقدار را دو برابر مي‌کنيم تا جايي که در مشخصه‌هاي حداکثر و متوسط جداسازها، تغيير قابل ملاحظه‌اي صورت نگيرد و يا تعداد فرزندان تهي افزايش قابل ملاحظه‌اي داشته باشد. در اين صورت از آخرين مقدار (مقدار قبل از مقدار فعلي) به عنوان nc_j استفاده مي‌کنيم. اين عمل براي هر بعد به صورت جداگانه انجام مي‌شود.

توجه: براي اجزايي که از تطابق عيني استفاده مي‌کنند، برشها بر اساس توابع درهم‌ساز⁴⁹ تعريف مي‌شوند.

 

3.4.3 بهبود الگوريتم

به دليل تاثير مستقيم تعداد قانونهاي موجود در هر نود و تعداد فرزندان در حافظة اشغالي الگوريتم از روشهاي زير براي کاهش تعداد جداسازها و فرزندان و به تبع آن کاهش فضاي اشغالي استفاده مي‌شود:

نکته: انجام بهينه‌سازيها در ساختار درخت به نظر با فرض ايستايي بودن انباره انجام شده است، چرا که حذف بعضي اجزاءِ درخت، انجام به روزرسانيهاي مکرر را مشکل و به شکلي غير ممکن مي‌سازد. از جملة اين موارد ترکيب نودها و همپوشاني جداسازها مي‌باشد.

1. ترکيب نودها⁵⁰: هدف حذف سربارة ناشي از ذخيرة نودهاي مساوي به صورت مجزا مي‌باشد. به عبارتي اگر تعدادي از فرزندان يک نود داراي مجموعة جداسازهاي مساوي باشند به جاي ساخت و ذخيرة يک زير درخت مجزا براي هر يک از آنها، يک زير درخت براي تمام آنها ساخته مي‌شود.

2. همپوشاني جداسازها⁵¹: گاهي اتفاق ميافتد که دو جداساز Rk و Rz با همپوشاني محدوده‌اي، در يک نود قرار مي‌گيرند. به عبارتي اگر بسته‌اي توسط يکي از آنها پذيرفته شود، مطمئنا توسط ديگري هم پذيرفته خواهد شد. حال اگر اولويت Rk از Rz بيشتر باشد، در تمام مواردي که بسته‌اي توسط آنها پذيرفته مي‌شود، قانون Rk انتخاب خواهد شد. بنابراين نگهداري Rz تنها مسبب اتلاف حافظه و به طبع آن افزايش زمان جستجو خواهد بود، پس چه بهتر که از گردونة توجهات حذف شود.

3. انقباض محدوده‌اي⁵²: هر نود اسمی، بر اساس برشهاي انجام شده، محدوده‌اي را پوشش مي‌دهد. گاهي اتفاق مي‌افتد که جداسازهاي موجود در آن نود زير محدوده‌اي از آن محدوده را پوشش مي‌دهند که در تقابل با آن بسيار کوچکتر است. در نتيجه مي‌توان به جاي استفاده از محدودة اسمي از محدودة واقعي استفاده کرد چرا که اين موضوع، اندازة نود را کاهش مي‌دهد.

4. بالاراندن قوانين مشترک در درخت تصميم‌گيري⁵³: اگر تمام فرزندان يک نود، مجموعة مشترکي را پوشش دهند، اين مجموعه به جاي تکرار در فرزندان در نود پدر نگهداري مي‌شود. نتيجة مستقيم آن کاهش حجم فضاي حافظه‌اي درخت خواهد بود.

براي انجام اين بهينه‌سازيها، از يک الگوريتم پايين-به-بالا⁵⁴ که درخت را از برگها به سمت ريشه بررسي مي‌کند استفاده مي‌شود.