ترجمه مسیریاب خود تطبیقی در محیط های پویا (ارزیابی و طراحی با استفاده از یک رویه ساده و احتمالاتی)

توضیحات

 عنوان فارسی: مسیریاب خود تطبیقی در محیط های پویا  (ارزیابی و طراحی با استفاده از یک رویه ساده و احتمالاتی)

عنوان انگلیسی مقاله ترجمه شده:

(On Self Adaptive Routing in Dynamic Environments (An Evaluation and Design Using a Simple, Probabilistic Scheme

مسیریاب خود تطبیقی در محیط های پویا

ارزیابی و طراحی با استفاده از یک رویه ساده و احتمالاتی

چکیده

اخیرا، ما شاهد یک روند نوظهور مسیریابی خود تطبیقی در هر دو شبکه اینترنت و شبکه های بی سیم بوده ایم. اگر چه روش های قبلی برای محاسبه تعادل ترافیک مسیریابی خود تطبیقی (به عنوان مثال، مسیریابی خودخواه) وجود دارد، این روش ها از الگوریتم های محاسباتی سخت هستند و نیاز به یک مدل تحلیلی دقیق از شبکه دارند . همچنین، یک سوال باز به نظر می رسد که چگونه یک طرح مسیریابی انطباقی طراحی کنیم که در عمل همگرایی با تعادل ترافیک را تضمین کند . در این مقاله، یک روش مسیریابی احتمالی ساده، کارآمد و گسترده برای مسیریابی خود تطبیقی در محیط های پویا و واقع بینانه پیشنهاد می کنیم. با استفاده از هر دوی تجزیه و تحلیل و شبیه سازی های گسترده، ما نشان می دهیم که طرح ما می تواند به سرعت به تعادل ترافیک مطلوب (یا کاربربهینه یا شبکه بهینه ) همگرا شود . ما متوجه می شویم که مسیریابی کاربر بهینه می تواند بسیار نزدیک به زمان واکنش بهینه متوسط در محیط های پویا باشد، اما چنین عملکردی اغلب به هزینه اضافه بار جدی برخی لینک ها می رسد. برای جلوگیری از اضافه بار لینک ، مسیریابی انطباقی را با بهینه سازی زمان واکنش کاربر و استفاده ضمنی از لینک  بهبود می بخشیم . ارزیابی ما نشان می دهد که یک مبادله بین اهداف بهینه سازی دوگانه وجود دارد، اما تنزل در زمان واکنش متوسط  تنها برای الزامات استفاده از لینک معمولی وابسته به حاشیه است .

معرفی

اخیرا ما شاهد یک روند ناپایدار مسیریابی انطباقی در هر دو شبکه اینترنت و شبکه بی سیم بوده ایم . در اینترنت، مطالعات اخیر [30، 34] نشان داده اند که ناکارآمدی ذاتی در مسیریابی IP از دیدگاه کاربر وجود دارد . در پاسخ به این مشاهدات، ما شاهد یک روند برای اجازه دادن به پایان دادن به میزبان ها برای انطباق مسیر خود با استفاده از مسیریابی منبع (به عنوان مثال، Nimrod [14] ) و یا با استفاده از مسیریابی جای گذاشت  (به عنوان مثال Detour [30] و یا RON [2]) هستیم . چنین سلکشن انتها به انتها خود تطبیق  ، به این دلیل که به کاربران اجازه می دهد مسیرهایی را برای بهینه سازی عملکرد خود بدون در نظر گرفتن معیارهای سیستم ، انتخاب کنند [27]. در شبکه های تک کاره بی سیم، مسیریابی منبع، مانند DSR [19]، به کاربران بی سیم اجازه می دهد تا خودمحورانه مسیرهای با زمان واکنش پایین را انتخاب کنند (به عنوان مثال، [18])، بنابراین به مسیریابی خودتطبیقی نتیجه داده میشود . این ظهور مسیریابی خود تطبیقی، سوالات تحقیقاتی چالش برانگیز در مورد طراحی پروتکل های مسیریابی و ارزیابی رفتار متعادل ترافیکی را مطرح می کند.

از لحاظ طراحی پروتکل های مسیریابی، یک سوال تحقیقاتی بدون پاسخ  باقی می ماند که چگونه یک طرح مسیریابی انطباقی طراحی شود که همگرایی با تعادل ترافیک را در شرایط واقع بینانه تضمین کند. اگرچه چندین طرح قبلی وجود دارد، اما برخی از مسائل اساسی هنوزباقی میماند که مورد توجه قرار بگیرد . به طور مشخص، معلوم نیست که چگونه شیوه های مسیریابی انطباقی باید شبکه را ردیابی کند تا بتواند مسیرهای کارآمد را به طور موثر کشف کند . اگر یک پروتکل از یک طرح ردیابی ناکارامد استفاده کند ، ممکن است مسیرهای با کیفیت بالا پیدا نشوند . علاوه بر این مشخص نیست که راههای مسیریابی باید در یک روش گسترده تنظیم شوند و همچنان بدون ایجاد نوسانات به راه های بهینه نزدیک شوند. از لحاظ ارزیابی رفتار متعادل ترافیکی، یک سوال مهم اما چالش برانگیز این است که چگونه عملکرد مسیریابی خود تطبیقی در شبکه های بزرگ را ارزیابی کرد .  در حالی که کارهای قبلی در این زمینه از هر دو دیدگاه نظری (به عنوان مثال، [23، 29]) و دیدگاه های عملی (به عنوان مثال، [27])، چندین مسئله همچنان باید مورد توجه قرار بگیرند . اول، چگونگی محاسبه کارامد تعادل ترافیک در شبکه های بزرگ یک مشکل بدون پاسخ است. الگوریتم های سنتی استفاده شده برای ایجاد تعادل ترافیکی (به عنوان مثال، الگوریتم فرانکل وولف [15]) به صورت محسوسی گران هستند و به سختی به مقیاس شبکه های بزرگ برده میشوند . دوم، چنین الگوریتم هایی نیازمند یک مدل تحلیلی از شبکه هستند، به عنوان مثال، توابع زمان بندی(زمان واکنش) لینک، که باید دانسته شوند ، هرچند که ممکن است مورد مسئله نباشند . برای مثال، عبارات ساده تحلیلی برای تاخیر بسته در شبکه های بی سیم وجود ندارد، زیرا تاخیر  از طریق صف بندی ، تضاد لایه های  MAC، و ارسال مجدد ایجاد میشود . علاوه بر این، چنین الگوریتم هایی  تعادل را فقط در یک محیط ثابت میتوانند ایجاد کنند. در حقیقت، شبکه ها می توانند بسیار پویا باشند  و مسیریابی را به صورت توزیع شده( گسترده)  کار کنند .  بنابراین مهم است که فرآیند پویا را دستگیری کنیم .

در این مقاله، ما یک طرح مسیریابی برای حل مسائل فوق پیشنهاد می دهیم. طرح ما دارای الزامات زیر است. ابتدا، به عنوان یک مکانیسم برای محاسبه تعادل، به نظر می رسد که طرح باید ساده و کارآمد باشد و بنابراین می تواند برای ارزیابی شبکه های بزرگ استفاده شود . این نباید به یک مدل شبکه دقیق نیاز داشته باشد و بنابراین می تواند در تنظیمات مختلف (به عنوان مثال، شبکه های سیمی و بی سیم) مورد استفاده قرار گیرد. همچنین باید بتواند روشی تطبیقی را در یک محیط پویا مدل سازی کند و بتواند سربار احتمالی مسیر یابی انطباقی را بگیرد . دوم، به عنوان یک پروتکل برای محاسبه مسیرهای شبکه مورد بررسی قرار می گیرد، این طرح باید گسترده باشد  و سربار پروتکل های آن کم باشد. در طراحی پروتکل های مسیریابی انطباقی با اهداف مختلف (به عنوان مثال بهینه سازی کاربر یا بهینه سازی شبکه) طراحی بصری باید ارائه دهد. پروتکل باید مسائل کلیدی چگونگی بررسی شبکه ها و نحوه تنظیم مسیرهای مسیریابی برای تضمین همگرایی را در نظر بگیرد . به طور خاص، طرح مسیریابی که در این مقاله پیشنهاد و مطالعه می شود یک طرح مسیریابی احتمالی است. در مسیر داده، هر بسته به یک همسایه که بر اساس توزیع احتمالی تعریف شده برای هر مقصد انتخاب شده  ارسال می شود . طرح ما مناطق را فقط برای مقاصد با ترافیک فعال نگه می دارد، و بنابراین سربار (مخارج کلی ) مناطق کم است. در مسیر کنترل، یک پروتکل مشابه مسیریابی بردار فاصله ، این احتمالات را حفظ می کند. پس از دریافت به روز رسانی مسیریابی از یک همسایه، یک مسیریاب احتمالات مسیریابی خود را به روز می کند. طرح به روز رسانی احتمالات ما توسط دو طرح تقریبی تصحیح شده در مقیاس زمانی پیشنهاد شده توسط Borkar و Kumar در [10] و طرح Q-routing پیشنهاد شده توسط Littman و Boyan در [25] برانگیخته شده است . با این حال، این دو طرح از بازخورد هر بسته (per-packet )بر اساس مسیر و بروز رسانی استفاده می کنند . در نتیجه، پروتکل های آنها نیاز به همکاری بین لایه مسیریابی و لایه حمل و نقل دارند. علاوه بر این، سربار(اضافه هزینه ) مسیریابی پروتکل های آنها می تواند بالا باشد. در مقایسه، طرح ما مسیرهای به روز رسانی را جمع میکند ؛ بنابراین هزینه سربار طرح ما قابل مقایسه با شیوه مسیریابی سازگار با بار مانند مسیریابی  QoS است. در یک محیط کم بار (به عنوان مثال، که زمان واکنش( تاخیر) یک لینک به مقدار ترافیک حساس نیست)، الگوریتم به روزرسانی ما معادل الگوریتم توزیع شده بلمن-فورد است [5].

 طرح بروز رسانی ما نیز توسط الگوریتم های طرح ریزی شیب توزیع شده است، به عنوان مثال، به [7، 4، 17، 35] مراجعه کنید. با این حال، این الگوریتم ها شرایط محیط شبه استاتیکی را می پذیرند، یعنی تأثیر به روز رسانی مسیریابی را می توان بلافاصله مشاهده کرد، در حالی که طرح ما اجازه می دهد تا اثرات مسیریابی به روزرسانی ها به تدریج حل شود. بنابراین طرح ما، پویایی شبکه را جذب می کند و می تواند یک طرح محاسباتی و یک طرح مسیریابی واقع بینانه باشد. همچنین، طرح مسیریابی ما احتمالی است و پیچیدگی کمتری نسبت به الگوریتم پیش بینی شیب قبلی دارد که قطعی است . ما از طرح مان برای پیاده سازی دو نوع مسیریابی انطباقی استفاده می کنیم: مسیریابی مطلوب برای کاربر و مسیریابی مطلوب شبکه .

مسیریابی مطلوب کاربر به تعادل Wardrop [36] در معنای( جهت) Cesaro ، جایی که در تعادل Wardrop، کاربران انگیزه ای برای تغییر یک جانبه مسیر خود ندارند، همگرا می شود. مسیریابی بهینه شبکه به حداقل زمان تأخیر(واکنش) می انجامد. اولی با داشتن اطلاعات تبادل همسایگان مربوط به زمان تاخیر پیوند به دست می آید، در حالی که دومی را با داشتن اطلاعات همسایگان مربوط به تاخیر پیوند نهایی(مرزی)  به دست می آورند.

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

با استفاده از رویکرد طرح مسیریابی کارامد، ما در حال مطالعه نحوه انتخاب مسیرها برای بهینه سازی عملکرد کاربر نهایی و استفاده از لینک به صورت همزمان هستیم . این یک مشکل مهم در مهندسی ترافیک برای شبکه های انطباق است [27]، زیرا بهینه سازی عملکرد کاربر نهایی به تنهایی گاهی باعث اضافه بار پیوند میشود (که از نظر اپراتورهای شبکه ناخوشایند است)، در حالی که بهینه سازی استفاده از شبکه تنها ممکن است عملکرد کاربر نهایی را کاهش دهد . برای دستیابی به عملکرد خوب کاربر بدون بارگذاری بیش از حد شبکه، یک آستانه استفاده از لینک را معرفی می کنیم. ما احتمالات مسیریابی را زمانی که استفاده از لینک زیر آستانه است، مانند قبل  به روز رسانی کنیم. از سوی دیگر، هنگامی که استفاده از یک لینک بالاتر از آستانه است، ما ترافیک را به لینک های کمتر بارگذاری می کنیم . ما مبادله بین زمان تأخیر کاربر و استفاده از پیوند برآورد میکنیم و نشان می دهد که تخریب عملکرد کاربر نهایی فقط برای الزامات استفاده از لینک معمولی مرزی است.

توجه:

• برای دانلود فایل word کامل ترجمه از گزینه افزودن به سبد خرید بالا استفاده فرمایید.
• لینک دانلود فایل بلافاصله پس از خرید بصورت اتوماتیک برای شما ایمیل می گردد.