بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهينه سازی وزن های پروتکل مسيريابي OSPF با روشي مبتني بر جستجوی تصادفي بازگشتي
چکيده : در اين پژوهش مساله ی بهينه سازی وزن های پروتکل مسيريابي OSPF، يکي از مشهورترين و پرکاربردترين پروتکل های درون درگاهي در اينترنت ، معرفي شده است و پس از پرداختن به فرمول بندی مساله [١] يک روش جستجوی مکاشفه ای مبتني بر نمونه برداری تصادفي بازگشتي از فضای حالات [٣] برای حل اين مساله طراحي و پياده سازی شده و نتايج اجرای آن بر روی چند گراف تصادفي با نتيجه حاصل از حل مساله با برنامه ريزی خطي مقايسه شده است .
واژه های کليدی: مسيريابي ، وزن هاOSPF ی، مهندسي ترافيک ، نمونه برداری تصادفي ، بهينه سازی غيرقطعي .
١- مقدمه
با گسترش اينترنت و توسعه سيستم های خودمختار در اواخر دهه ی هشتاد، کاستي پروتکل های مسيريابي نظير RIP نمود بيشتری پيدا کرد.
با سريع تر شدن پردازنده ها و ارزان شدن سخت افزار نياز به طراحي يک پروتکل بهينه ، گروه ٢IETF را بر آن داشت تا در اين زمينه شروع به تحقيق نمايند. نتايج تحقيقات اين گروه در سال ١٩٩٠ در قالب پروتکل مسيريابي OSPF ارايه شد و بسياری از توليدکنندگان مسيرياب از آن استقبال کردند و هم اکنون اين پروتکل رايج ترين پروتکل مسيريابي درون درگاهي در اينترنت مي باشد. OSPF يک پروتکل حالت پيوند است که در آن بسته های حالت پيوند که حاوی اطلاعات پيوندهای هر مسيرياب با مسيرياب های مجاورش مي باشند از هر مسيرياب به همه ی مسيرياب های حاضر در آن شبکه به صورت سيل آسا ارسال مي شود. هر مسيرياب با استفاده از اطلاعات بسته های حالت پيوندی که از ساير مسيرياب ها دريافت نموده بانک اطلاعاتي توپولوژی شبکه را مي سازد. اين بانک در واقع گراف جهت دار و وزن داری را مشخص مي کند که راس های آن همان مسيرياب ها و يال های وزن دار آن پيوندهای فيزيکي بين مسيرياب ها مي باشند. هر مسيرياب کوتاهترين مسير تا ديگر مسيرياب ها را در اين گراف محاسبه مي کند و بسته های اطلاعاتي را همواره روی اين مسيرها هدايت مي نمايد[٤]. پروتکل OSPF يک مسيريابي سلسله مراتبي دارد به اين معني که در آن مسيرياب های شبکه به تعدادی ناحيه دسته بندی مي شوند که ارتباط آن ها از طريق ناحيه ای به نام ستون فقرات برقرار شده است .
در چنين شبکه ای برای ارسال يک بسته ابتدا بايد يک مسيريابي در سطح ناحيه مبدا و سپس يک مسيريابي در سطح ستون فقرات و سپس يک مسيريابي ديگر در سطح ناحيه ی مقصد صورت گيرد. هر مسيرياب OSPF برای محاسبه ی کوتاهترين مسيرها منتهي به ديگر مسيرياب ها از الگوريتم دايجسترا بهره مي گيرد که پيچيدگي زماني اين الگوريتم در (٢ ) مي باشد. در اين حالت مسيريابي سلسله مراتبي علاوه بر کاستن از طول جداول مسيريابي ، از n يعني تعداد مسيرياب های هر ناحيه نيز مي کاهد در نتيجه زمان محاسبه ی مسيرهای بهينه را کاهش مي دهد.
۱-۱- وزن هاOSPF
پارامتری عددی که به هر پيوند اختصاص داده مي شود وزن ناميده مي شود و بيانگر هزينه استفاده از آن پيوند م باشد. مسيرهای بهينه بر اساس اين وزن ها محاسبه مي شوند. وزندهي که مسيرياب های شرکت Cisco به طور پيش فرض روی پيوندهای شبکه اعمال مي کنند به نسبت عکس پهنای باند آنهاست ، يعني هر چه پهنای باند پيوند کمتر باشد هزينه ی بالاتری به آن تخصيص مي يابد. اين وزندهي به اين دليل انتخاب شده که پيوندهای با پهنای باند بيشتر شانس بيشتری برای قرارگرفتن روی کوتاهترين مسيرهاOSPF ی داشته باشند و بار ترافيکي بيشتری روی آنها اعمال شود. اين وزندهي اغلب بهينه نيست و مي تواند منجر به ازدحام ترافيک روی بعضي از پيوندها شود.
در يک شبکه OSPF با توپولوژی و ظرفيت مشخص ، يافتن يک وزندهي بهينه برای پيوندها که ترافيک شبکه را به گونه ای متوازن روی آن توزيع نمايد مي تواند به صورت يک مساله ی بهينه سازی مطرح شود.
تابع هدف در اين مساله ی بهينه سازی مي تواند به گونه های مختلفي در نظر گرفته شود، به عنوان مثال ميزان کل بسته های ناموفق مي تواند يک معيار خوب برای تابع هزينه ی مسيريابي باشد، يا يک معيار ساده تر مي تواند بر اساس ازدحام ترافيک روی پيوندهای شبکه تعريف شود.
همچنين برای داشتن تعريف دقيقي از مساله بايد تخميني از ميزان تقاضاهای ارسال نقطه به نقطه داشته باشيم . در يک شبکه مشخص الگوی اين تقاضاها به صورت دوره ای در حال تغيير است و با تغيير اين الگو برای متعادل ماندن توزيع ترافيک شبکه بايد وزندهي بهينه ی پيوندها بروزرساني شود.
۱-۲- فرمول بندی مساله
گراف جهت دار و وزن دار که تابع به هر پيوند آن يک ظرفيت اختصاص مي دهد به همراه ماتريس تقاضای داده شده اند. برای هر زوج ميزان تقاضای ارسال برای هدايت از مبدا s به مقصد t م باشد.
اگر پس از مسيريابي همه ی تقاضاها، بار ترافيکي اعمال شده روی يال باشد و هزينه ی انتقال اين ترافيک از طريق اين يال باشد، مي خواهيم وزندهي بهينه Wی را به گونه ای بيابيم که کل هزينه ی مسيريابي ناشي از اين وزندهي يعني تابع زيرکمينه باشد:
از آنجايي که ارسال اطلاعات روی خطوط پرترافيک شبکه کند مي باشد و نيز خطر شکست ارسال را افزايش مي دهد، تابع هزينه دراين مساله در بسياری از تحقيقات تابعي خطي پاره ای و افزايشي در نظرگرفته مي شود که در آن آهنگ رشد تابع بسته به ميزان پر بودن يک خط بيشتر است [٢][١]، در اين تحقيق برای سادگي و حفظ امکان مقايسه نتايج تابع هزينه مساله را به همين شکل در نظر گرفته ايم و هزينه ی استفاده از يال ها را به صورت (٣) قيد مي کنيم .
در اين حالت اگر ارسال اطلاعات بين رئوس آزادانه باشد و هيچ شرطي روی انتخاب مسيرهای يکسان نداشته باشيم مي توانيم مساله را به صورت زير فرمول بندی کنيم و با روش برنامه ريزی خطي در زمان چندجلمه ای حل نماييم [٦]:
بخشي از ترافيک است که از يال a عبور مي کند و شرط (٤) برای آن قيد شده است که شار ترافيک ورودی و خروجي هر راس شبکه برابر مي باشند.
۱-۳- پيچيدگي مساله با شرط اضافه شده به مسـاله در مسيريابي OSPF
الگـوريتم OSPF بسـته هـای اطلاعـاتي را روی کوتـاهترين مسـيرهای شبکه ارسال مي کند در اين حالت اگر بين دو راس شبکه بـيش از يـک مسير کوتاهترين موجود باشد ترافيـک ارسـالي بـين ايـن مسـيرها بـه صورت تقريبا مساوی تقسيم مي شود. به بيان رياضـي بـرای هـر زوج از رئوس و هر دو يال خـارج شـونده از راس u که روی کوتاهترين مسير موجود بين s و t مي باشدداريم :
و اگر یال (u,v) روی کوتاهترين مسير از s به t نباشد داريم :
بااين شرط اضافه شده حتي يافتن يـک وزنـدهي نزديـک بـه وزنـدهي بهينه ، مساله اNP-hard خواهد بود. اين نتيجه برای دسته ای از توابع هدف شامل تابع هدف تعريف شده در رابط ه ی (٣) در قالـب قضـا ايي بيان و اثبات شده است [١][٥].
۲- روش تحقيق
در اين تحقيق برای حل مساله ی مورد بحث از يک روش بهينه سازی غيرقطعي استفاده شده است . روش های بهينه سازی غيرقطعي به جای سعي در يافتن جواب بهينه ی عمومي که وقت گير است به يافتن جوابي نزديک به بهينه ی عمومي در محدوده ی زماني تعيين شده اکتفا مي کنند.
در الگوريتم مکاشفه ای اين تحقيق با انجام نمونه برداریهايي تصادفي کاوش در فضای پارامتری را آغاز مي کنيم و استخراج جواب بهينه را از نقطه ای واقع در يک ناحيه ی اميدبخش وسيع شروع مي کنيم ، سپس با اعمال تغييرات متوالي در مختصات و وسعت اين ناحيه سعي مي کنيم به يک جواب بهينه ی محلي همگرا مي شويم . دليل ما برای بکارگيری اين روش در حل مساله ی بهينه سازی وزن هاOSPF ی خصوصيات اين الگوريتم مي باشد که با نيازهای مساله ما مطابقت کامل دارد. در زير به اختصار به اين خصوصيات اشاره مي کنيم :
کارايي بالا: از آنجا که شرايط يک شبکه پي درپي در حال تغيير است به الگوريتم جستجويي نياز داريم که سريع باشد تا بتواند قبل از بروز تغييرات زيادی در وضعيت شبکه بهترين وزندهي را متناسب با وضعيت فعلي يافته و روی شبکه اعمال کند.
مقياس پذيری با ابعاد زياد: از آنجا که ممکن است گراف شبکه ی OSPF صدها يال داشته باشد، الگوريتم بهينه سازی به کار رفته با يد روی دامنه وسيعي از توابع هدف با تعداد پارامترهای زياد عملکرد خوبي داشته باشد.
مقاومت در برابر خطا: رفتار شبيه سازی شده ی مسيريابي شبکه همواره با کمي انحراف از رفتار واقعي همراه است يعني هميشه تقريبي از تابع هزينه ی مسيريابي در دست است ، درنتيجه پاسخ نهايي الگوريتم بهينه سازی بايد نسبت به خطای اين محاسبات حساسيت اندکي داشته باشد.
در تحقيقي که برای آزمودن ميزان کارايي ، مقياس پذيری و عدم حساست به خطا الگوريتم جستجوی تصادفي RRS انجام گرفته است از اين الگوريتم برای بهينه سازی تابع Rastrigin استفاده شده است و نتايج حاصل وجود همگي اين خصوصيات را در الگوريتم مذکور نشان داده است [٣]،اين تابع به شکل کلي زير باشد :
که در آن X بردارn بعدی از اعداد و A عددی ثابت مي باشد. اين تابع بهين ای محلي بسياری دارد اما تنها يک جواب بهينه ی عمومي در نقطه ی دارد و يافتن ين بهينه ی عمومي در بين تعداد زيادی بهينه ی محلي کار دشواری به نظر مي رسد.
در شکل ١ يک نمونه ی دو بعدی از اين تابع نشان داده شده است .
شکل ١. يک تابع Rastrigin دو بعدی
۲-۱- جستجوی تصادفي بازگشتي RRS
نمونه برداری تصادفي در يافتن نقاط خوب در گام های ابتدايي بسيار کارا م باشد. فرض کنيد تابع هدف روی فضای پارامترD تعريف شده و داريم :
نسبت نقاطي از فضای پارامتری که مقدار تابع هدف در آن ها کمتر از yr مي باشد را با تابع زير نشان مي دهيم :
اگر باشد، ناحيه ای با اندازه به صورت زير قابل تعريف است که آن را ناحيه r -اميدبخش مي ناميم :
فرض کنيد پس از n نمونه برداری تصادفي يک توالي از نمونه ها به صورت در اختيارداريم ، از بين آن ها بهترين نمونه ای که تابع هدف را کمينه مي کند ناميم . با فرض اين که نمونه ها روی فضای پارامتری توزيع يکنواختي دارند احتمال اين که در ناحيه r -اميدبخش باشد به صورت زيرخواهد بود:
زيرا احتمال اين که هيچ کدام از اين n نمونه ای در ناحيه r -اميدبخش نباشد است ، بنابراين داريم :
از اين رابطه پيداست که برای هر احتمال ١>p با افزايش n،r به سمت صفر ميل مي کند و به سمت مجموعه ای محدود از نقاط بهينه ی عمومي ميل خواهدکرد. از آنجا که با افزايش n کاهش r به صورت نمايي م باشد بنابراين نتيجه مي گيريم نمونه برداری تصادفي با افزودن بر تعداد نمونه ها به بهينه ی عمومي همگرا مي شود و سرعت همگرايي در گام های ابتدايي زياد است .
در شکل ٢ نمودار تغييرات r برحسب n برای احتمال ٠.٩٩ رسم شده است . مي بينيم که تنها با ٤٤ نمونه برداری به احتمال ٠.٩٩به نقطه ای در دست خواهيم يافت ، بدون آن که هيچ دانشي از تابع هدف داشته باشيم .
شکل ٢. نمودارکاهش نمايي r بر حسب تعداد نمونه برداریها
ازرابطه (١٣) تعداد نمونه برداری های لازم برای رسيدن به نقطه ای در ناحيه r -اميدبخش به دست مي آيد:
بنابراين الگوريتم ابتدا عدد نسبتا کوچک r و احتمال p را به دلخواه انتخاب مي کند سپس ازرابطه ی (١٤) مقدار n، تعداد نمونه برداریهای لازم را محاسبه مي نمايد، سپس n نمونه برداری انجام مي دهد و مقدار تابع هزينه در بهترين نمونه را به عنوان مقدار آستانه در نظر مي گيرد. در نمونه برداریهای بعدی اولين نقطه ای که در قرار گيرد با احتمال p در قراردارد، زيرا
پس از يافتن اين نقطه 0 X، کاوش نقطه ای بهتر در همسايگي آن آغازمي شود. اگر چنين نقطه ای پس از n نمونه برداری تصادفي يافت نشد با افزودن به مقدار آستانه وسعت ناحيه ی اميدبخش کمي افزايش مي يابد و مرحله ی کاوش برای رسيدن به نقطه ای بهتر واقع در ناحيه ی اميدبخش جديد تکرارمي شود.
اين نکته اهميت دارد که احتمال p درحدی باشدکه برای يافتن X0 نيازمند تعداد زيادی نمونه برداری نباشيم . همچنين مقدار r که مقدار و در نتيجه وسعت ناحيه را تعيين مي کند نبايد بزرگ باشد.
در اين حالت همسايگي نقطه ی مي تواند به اين صورت تعريف شود که در آن D فضای پارامتری و بردارهای نقاط اين فضا مي باشند و در آن ها مي باشد:
