بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
روشي نو براي تضمين تأخير بسته هاي موجود در صف مسيرياب با استفاده از بهينه سازي اجتماع ذرات
چکيده
مديريت فعال صف بخش مهمي از فرآيند کنترل ازدحام اينترنت بوده و نقش مهمي در کارايي و کيفيت سرويس آنها ايفا ميکند. از جمله پارامترهايي که همواره در کارايي مکانيزمهاي مديريت فعال صف مورد توجه بوده است ، حداکثر تأخير صف ميباشد. الگوريتم RED معروفترين الگوريتم مديريت فعال صفي است ، که در شبکه اينترنت مورد استفاده قرار ميگيرد. در اين مقاله روشي ارائه ميشود، که با استفاده از الگوريتم بهينه سازي اجتماع ذرات، حداکثر تأخير صف الگوريتم RED را تضمين ميکند. در اين روش سطوح آستانه الگوريتم RED با استفاده از الگوريتم بهينه سازي اجتماع ذرات، به نحوي تنظيم ميگردد، که تأخير صف آن همواره کمتر از يک مقدار مرجع باقي بماند. نتايج شبيه سازي نشان ميدهد، که الگوريتم ارائه شده علاوه بر تضمين بيشينه تأخير باعث کاهش تعداد بسته هاي دور ريخته شده و کاهش طول متوسط صف مسيرياب نيز ميگردد.
کليد واژه- بهينه سازي اجتماع ذرات، کنترل ازدحام، مديريت فعال صف ، تاخير صف .
١- مقدمه
يکي از مشکلاتي که باعث کاهش کارايي مسيريابها ميشود وقوع ازدحام در آن است . ازدحام زماني رخ ميدهد، که مجموع درخواست ها از يک منبع شبکه (مثلا پهناي باند يک اتصال) فراتر از ظرفيت موجود باشد. نتيجه چنين وضعيتي، افزايش تاخير و احتمال حذف شدن بسته باشد. هنگامي که در يک مسيرياب ازدحام رخ دهد، طول صف ها افزايش مييابد و پردازش آنها طولانيتر ميشود در چنين حالتي ممکن است تاخير شبکه بيشتر گردد و مسيرياب به منظور کنترل ازدحام اقدام به دور انداختن بسته از درون صف کند.
در ميان روشهاي مديريت فعال صف ، الگوريتم DRE از همه مشهورتر است و در واقع يک الگوريتم کلاسيک و پرکاربرد در اين حوزه به شمار ميآيد[١]. الگوريتم RED توسط Floyd و Jacobson [٢] و جهت حل مسائل پرشدن صف و حبس شدن در روش Droptail پيشنهاد شد. برخلاف Droptail، که هنگام پرشدن صف ، به صورت قطعي بسته ها را حذف مينمايد، RED براساس ميانگين طول صف ، بسته هاي رسيده را به صورت احتمالي حذف مينمايد. دليل اينکه بسته ها به صورت تصادفي انداخته ميشوند، اين است که پديده همزمانسازي حذف گردد.
RED همچنين طول متوسط صف را کنترل و مديريت ميکند، تا از سرريز صف پرهيز گردد. تحقيقات وسيعي بر روي الگوريتم RED صورت گرفته است [٣،٤،٥،٦]. اما همواره کارايي الگوريتم RED بسيار حساس به انتخاب پارامترهاي آن است . انتخاب نادرست پارامترهاي minth و maxth ممکن است به بهرهوري حتي پايين تر Droptail، از نيز منجر شود. همچنين متوسط طول صف بسته به سطح ازدحامي که با آن مواجه ميشود، تغيير ميکند. مزيت استفاده از روش بهينه سازي اجتماع ذرات در مقايسه با ديگر روشهاي بهينه ساز اين است که با فرض ترافيک هاي انفجاري شبکه اينترنت حدود آستانه الگوريتم RED بصورت پويا تنظيم ميگردد.
در اين مقاله ، هدف الگوريتم RED تضمين تأخير صف همواره کمتر از يک مقدار مرجع باقي بماند و همچنين کاهش طول متوسط صف مسيرياب و کاهش تعداد بسته هاي دور انداخته شده ميباشد. ادامه اين مقاله به صورت زير سازماندهي شده است . در بخش دوم به بررسي الگوريتم RED ميپردازيم . در بخش سوم شرح مختصري درباره روش بهينه سازي اجتماع ذرات (PSO) ميدهيم . در بخش چهارم روش پيشنهادي ارائه ميگردد و همچنين سناريوهاي شبيه سازي شده در محيط 2-ns مرا اگرارئه ددمويهکمنيچم ن.ين راسننجاارميوهدار بخشبش يه سپنازجيم نشتديهجه دريمرحيط را 2ار-اsئه ميدهيم .
٢- الگوريتم RED
الگوريتم RED، بعنوان اصليترين مکانيزم مديريت فعال صف در مسيريابها استفاده ميشود. اين الگوريتم از دو جزء اساسي تشکيل شده است . جزء اول براي تخمين ميانگين طول صف با استفاده از ميانگين وزندار نمايي است که مي توان آن را مانند يک فيلتر پايين گذر تفسير کرد. جزء دوم نيز وظيفه تصميم گيري در مورد حذف بسته هاي رسيده را برعهده دارد. RED داراي سه پارامتر ميباشد، که عبارتند از maxth، minth و maxp. هنگامي که طول صف از minth کوچکتر است ، احتمال حذف بسته برابر صفر است و اگر طول صف بيشتر از maxth باشد، بسته رسيده قطعا حذف ميگردد. اگر طول صف بين minth و maxth باشد، بسته رسيده با احتمالي که از صفر تا maxp تغيير ميکند، حذف خواهد شد.(مطابق با شکل ١)
از ميانگين طول صف براي تصميم گيري حذف يا علامت زني بسته ها استفاده ميکنيم که طبق فرمول (١) متوسط طول صف محاسبه ميشود.
از w به عنوان فاکتور وزن، که تعيين کننده ميزان حساسيت دروازه RED به طول صف لحظه اي ميباشد. پارامتر وزن صف (w) بر حسب اندازه و تعداد دوره هاي انفجار که اجازه ورود به صف را دارند محاسبه ميشود. در جزء دوم براي محاسبه احتمال علامت زني بسته ها (P) به صورت زير بدست ميآيد:
در فرمول فوق پارامتر maxp کنترلي است که توسط آن حداکثر احتمال دور ريختن بسته ها مشخص ميشـود. با توجه به فرمول فوق ميتوان به اين نتيجه رسيد که مقدار احتمال P بين صفر و maxp تغيير ميکند. بنابراين پيکربندي الگوريتم RED براي دستيابي به يک کارايي قابل پيش بيني کاري پيچيده و دشوار ميباشد.
٣- الگوريتم بهينه سازي اجتماع ذرات
الگوريتم بهينه سازي اجتماع ذرات در سال ١٩٩٥ توسط آقايان James Kennedy و Russell Eberhart ارائه شد، که يک تکنيک بهينه سازي قدرتمند مبتني بر قوانين احتمال است که از حرکت و هوش دسته جمعي ذرات گرفته شده است . در اين روش ذرات در کنار هم در يک فضاي جستجو با حرکت هوشمندانه سعي در پيدا کردن راهحل بهينه ميکنند[٧،٨،٩].
در الگوريتم PSO، دسته ذرات شامل M ذره است . هر ذره در يک فضاي N بعدي فعاليت ميکند. هر ذره "پرواز" خود را بر اساس تجربه پرواز خود و تجربه پرواز اعضاي ديگر تنظيم مينمايد. هر ذره با استفاده از سرعت ، در مورد ميزان و جهت "پرواز" خود تصميم گيري ميکند، تا نقطه بهينه در فضاي Nبعدي را دنبال کند. موقعيت و سرعت ذره i را در تکرار Kميتوان به شکل فرمول ٣ و ٤ بيان کرد[٨]:
هر ذره براي يافتن راه حل بهينه در فضاي جستجو ادامه ميدهد، تا بهترين راهحل که تا آخرين مرحله به صورت گروهي بدست آمده دست يابد. اين مقدار بهترين شخصي (Pi,best) ناميده ميشود و طبق فرمول پنجم قابل بيان است .
يکي ديگر از بهترين راهحل ها در الگوريتم PSO وجود دارد بهترين سراسري (Pg,best) است ، که از همسايگي تمامي ذرات بدست ميآيد و طبق رابطه (٦) قابل بيان است .
هدف اصلي PSO سرعت بخشيدن به ذرات در رسيدن به نقطه بهينه سراسري و فردي است . سرعت و موقعيت ذره i در تکرار
1+K مطابق با فرمول (٧) و (٨) محاسبه ميشود.
بترتيب بردار موقعيت و سرعت ذرات را تشکيل ميدهند. w وزن لختي، c1 و c2 اعداد ثابت مثبت هستند، که ضرايب شتاب گفته ميشود و r1 و r2 دو عدد تصادفي با توزيع يکنواخت در محدوده [٠-١] ميباشند.
۴- روش پيشنهادي
در اين بخش روشي مبتني بر بهينه سازي اجتماع ذرات بمنظور تضمين تاخير براي بسته هاي موجود در صف مبتني بر الگوريتم RED مسيرياب طراحي ميشود. همانطور که در بخش دوم گفته شد، پايداري و کارايي الگوريتم RED بشدت به تنظيم پارامترهاي سطح آستانه وابسته است . بطوري که اگر سطح آستانه ها خيلي کوچک باشد، بهروري اتصال خيلي پايين است و اگر سطح آستانه ها خيلي بزرگ باشد، قبل از اينکه مبادي آگاه شوند ازدحام صورت ميگيرد، بنابراين مقدار بهينه براي سطح آستانه هاmin به طول متوسط صف وابسته است . در th , maxthنسخه اصلي الگوريتم RED مقادير maxth ,minth به صورت ايستاتيک تعريف شدهاند براي رسيدن به يک کارايي بهينه پارامترهاي سطح آستانه الگوريتم RED بايد بصورت پويا تنظيم شوند. در روش پيشنهادي مقادير maxth ,minth با توجه به شرايط شبکه ، بخصوص با استفاده از اندازهگيري متوسط طول صف بصورت پويا تنظيم ميشوند.. از طرفي براي تنظيم کردن تضمين تاخير صف از دو حد آستانه α و β استفاده ميکنيم .
همچنين يراي حدود آستانه صف مسيرياب داريم :
که در روش پيشنهادي Qmin و Qmax را بعنوان بهترين نقطه سراسري (Pg,best) در نظر ميگيريم . بنابراين مقدار β و α
طبق زمان ثابت تاخير صف دو ميلي ثانيه لحاظ ميکنيم . محاسبه سرعت ,minth maxth با استفاده از فرمول (١٢) و (١٣) بدست ميآيد.
براي تعيين موقعيت بعدي minth و maxth، سرعت بدست آمده از فرمولهاي (١٢) و (١٣) را با موقعيت يا همان مقادير قبلي minth و maxth مطابق با فرمول (١٤) و (١٥) جمع ميکنيم . minth و maxth محاسبه شده جديد براي تصميم گيري طول متوسط صف بکار ميرود.
