تاخیر تخصیص بهینه سرور صف متقارن

تاخیر تخصیص بهینه سرور صف متقارن – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

تاخیر تخصیص بهینه سرور برای صف های متقارن موازی با استفاده از اتصالات تصادفی

چکیده

در این مقاله، ما نسبت به بررسی مشکل تخصیص K سرور یکسان برای یک مجموعه از N صف موازی در یک سیستم صف بندی با بازه زمانی مشخص اقدام می نماییم. اتصال هر صف به هر سرور با توجه به زمان به صورت تصادفی تغییر می یابد. هر سرور در حالت حداکثری خود می تواند به یک صف سرویس دهد و هر صف نیز قابلیت سرویس دهی تنها به یک سرور در خلال هر بازه زمانی را خواهد داشت. این نوع از سیستم های صف بندی دارای کاربرد گسترده ای در مشکلات مدل سازی زمانی (یا تخصیص منبع) در شبکه های بی سیم می باشند. این موضوع قبلا اثبات شده است که خط مشی «انطباق وزنی حداکثری» (MWM) بعنوان یک الگوی تخصیص بهینه در مبحث توان عملیاتی هر سرور، مرتبط با سیستم های صف بندی، بشمار می آید [۱] ، [۲] . در این مقاله، ما این موضوع را اثبات می نماییم که برای یک سیستم متقارن، با توجه به پارامتر ورود و اتصال پاکت برنولی با توزیع مستقل و یکسان (iid) ، MWM با بهره گیری از روش مرتب سازی تصادفی، قابلیت به حداقل رسانی محدوده گسترده ای از توابع هزینه طول های صف شامل مجموع اشغال صف (یا به طور هم ارز میانگین تاخیر در صف قرار دادن) را خواهد داشت.

تاخیر تخصیص بهینه سرور صف متقارن

۱- مقدمه

کنترل بهینه تصادفی شبکه های نوظهور بی سیم یکی از اهداف اصلی در طراحی چنین شبکه هایی به شمار می آید. به طور کلی، هدف اصلی در کنترل تصادفی شبکه های بی سیم توزیع منابع به اشتراک گذاشته شده در لایه های فیزیکی (همانند نیرو) و لایه های MAC (نظیر رابط های رادیویی، ایستگاه های رله و کانال های متعامد) برای کاربران متعدد و به گونه ای می باشد که یک ویژگی عملکرد تصادفی خاص به صورت بهینه اعمال گردد. در عین آنکه ویژگی های مختلف عملکرد شامل بازده / توان عملیاتی ثابت، میزان مصرف نیرو و توابع سودمند پذیرفته شده در بسیاری از مقاله ها مورد بحث و بررسی قرار گرفته اند، میانگین تاخیر صف بندی جزء آن دسته از پارامترهایی بشمار می باشد که توجه چندانی بدان مبذول نشده و مباحث کمتری در خصوص آن ارائه شده است. البته علت این امر را می توان در مشکل ذاتی مرتبط با برنامه ریزی بهینه تاخیر در سیستم های صف بندی با توجه به شرایط متغیر زمانی کانال ها دانست. در این مقاله، ما یک سیستم صف بندی زمان گسسته که متناسب برای مدل سازی همترازی منابع متعامد می باشد (همانند رابط های رادیویی/ تخصیص کانال)، در باب شبکه های دسترسی چند کاربره بی سیم، را مورد بررسی قرار می دهیم. …

مشکل تخصیص بهینه سرور در سیستم های صف بندی با اتصالات تصادفی عمدتا در مراجع [۱]، [۲]، [۷]–[۱۳] مورد خطاب قرار گرفته است. در مرجع [۱]، نویسندگان ایده ناحیه با ثبات برای شبکه صف بندی، با توجه به اتصالات متنوع زمانی، را ارائه نموده و بر این مبنا یک الگوریتم فشار معکوس به عنوان خط مشی تخصیص بهینه منبع و افزایش توان عملیاتی را برای شبکه های صف بندی ارائه نمودند. در مرجع [۷]، آنها یک سیستم صف بندی تک سروری چند صفی، با قابلیت اتصال پذیری تصادفی، را مد نظر قرار دادند. آنها ناحیه باثبات را از طریق مجموعه ای از نامعادلات خطی توصیف نموده و همچنین این موضوع را اثبات نمودند که برای یک سیستم متقارن با پارامترهای ورود و اتصال یکسان برای کلیه صف ها، LCQ (درازترین صف متصل) فراهم آورنده عملکرد بهینه بر حسب میانگین اشغال صف می باشد.

در مرجع [۱۱]، خط مشی وزنی حداکثری (MW) به عنوان یک خط مشی تخصیص بهینه بازده کلی سرور برای سیستم های صف بندی چند صفه و چند سروره با توجه به فرآیندهای کانال ایستگاهی پیشنهاد شد. در مرجع [۱۳]، نویسندگان اقدام به توصیف ظرفیت شبکه سیستم های صف بندی (چند صفه / چند سروره) با توجه به اتصال پذیری مبتنی بر تنوع زمانی نمودند. آنها همچنین برای مشخص نمودن میانگین تاخیر صف بندی در خط مشی AS/LCQ یک کرانه فوقانی را عرضه داشتند که به عنوان خط مشی تخصیص بهینه سرور برای این سیستم ها به شمار می آید. نتایج متعاقبا در مرجع [۱۴] برای توزیع های کلی تر کانال ایستگاهی (و نه صرفا کانال های i.i.d برنولی) ارائه شده است.

…

ادامه این مقاله به شرح ذیل سازماندهی شده است. بخش ۲ اقدام به تشریح این مدل نموده و ایده های مورد نیاز در این مقاله را ارائه می نماید. در بخش ۳، ما نسبت به معرفی خط مشی تطبیق وزنی حداکثری (MWM) به عنوان یک خط مشی بهینه برای مدل تشریح شده اقدام می نماییم. علاوه بر این مفاهیم رتبه بندی تصادفی و روش اتصال دینامیکی که به عنوان ادوات اصلی ریاضی استفاده شده  در  خصوص فراهم آوردن بهینه شدگی خط مشی  MWM  می باشند  را  تشریح  می نماییم. در بخش ۴، نتیجه این مبحث را عرضه داشته که فراهم آورنده بهینه شدگی خط مشی تخصیص سرور MWM می باشد. بخش ۵ نیز در نهایت اقدام به خلاصه نمودن نتایج این مقاله خواهد نمود.

[۱] crossbar packet switches

تاخیر تخصیص بهینه سرور صف متقارن

۲- تشریح مدل

ما یک سیستم صف بندی موازی بازه بندی شده زمانی با توجه به یک سری از صف های متقارن موازی {N = {1, 2, …,N  و فضای بافر نامتناهی برای هر صف را مد نظر قرار دادیم. پاکت ها / بسته ها در این سیستم به نظر دارای طول ثابتی بوده و نیازمند یک بازه زمانی جهت تکمیل سرویس خود می باشند. سرویس مربوطه برای این مجموعه از صف ها از طریق مجموعه ای از سرورهای یکسان تامین شده که تحت عنوان {K = {1, 2, …,K خوانده می شوند. اتصال هر صف     n ∈ N به هر سرور k ∈ K در هر بازه زمانی t به صورت تصادفی اعمال شده و دنبال کننده یک توزیع برنولی می باشد. ما اقدام به تخصیص اتصال صف n به سرور k در بازه زمانی t به وسیله C_n,k(t)  نمودیم. توجه داشته باشید کهC_n,k(t) ∈ {۰, ۱}  وE[C_n,k(t)] = p  برای کلیه n ∈ N و k ∈ K و …. t = 1, 2 معتبر است.

تاخیر تخصیص بهینه سرور صف متقارن

۳- سوابق

الف. تطابق وزنی حداکثری

در مراجع [۱]، [۲]، [۱۷]–[۱۹]، این موضوع نشان داده شده است که الگوریتم فشار معکوس قابلیت به حداکثر رسانی ناحیه دارای توان عملیاتی ثابت یک شبکه داده کلی را خواهد داشت. برای مدل ارائه شده در بخش ۲، الگوریتم فشار معکوس به صورت هم ارز با حل مشکل بهینه سازی ذیل در هر بازه زمانی t مد نظر می باشد [۲]:

ب. مرتب سازی تصادفی و اتصال دینامیکی

در این بخش، ما به طور خلاصه مفاهیم مرتب سازی تصادفی (نفوذ تصادفی) و تکنیک های اتصال دینامیکی را مورد بحث قرار می دهیم. با توجه به دو فرآیند تصادفی زمان گسسته  و  در R این موضوع پیگیری می شود. بر این مبنا ما مشخص می سازیم که A از نقطه نظر تصادفی کمتر از B می باشد و بنابراین می توان این گونه نوشت که ، در صورتی که برای کلیه  و کل  صادق باشد [۲۱]، [۲۲]. برخی از خواص مرتب سازی تصادفی به شرح ذیل عرضه می شوند. در صورتی که  باشد بنابراین  برای کل توابع غیر نزولی f  نیز در نظر خواهد بود. در صورتی که  باشد بنابراین  نیز صحت خواهد داشت. A به صورت تصادفی کوچکتر از B خواهد بود ، در صورتی که فرآیند  وجود داشته باشد، تعریف شده در فضای احتمال یکسان همانند B با توزیع احتمال یکسان همانند A ، و قابلیت ارضای  نیز وجود داشته باشد می توان تقریبا برای هر … t = 1, 2  به صورت قریب به یقین این موارد را در نظر گرفت[۸] . جمله آخری تحت عنوان اتصال A و  مطرح است. در حقیقت، به هنگام بکارگیری تکنیک اتصال، ما فرآیند A را در نظر گرفته و سعی در ایجاد یک فرآیند اتصال  با توزیع یکسان همانند A و برای کل t می نماییم. چنین موردی ابزار لازم برای فرآیندهای مقایسه ای تصادفی  AوB  را در اختیار ما قرار می دهد.

تاخیر تخصیص بهینه سرور صف متقارن

۴- بهینگی تطابق وزنی حداکثری (MWM)

در این بخش، ما نتیجه اصلی این مقاله را عرضه می نماییم که همانا فراهم آوردن بهینگی MWM با توجه به حداقل رسانی یک کلاس توابع هزینه طول های صف شامل میانگین تاخیر صف بندی می باشد. در نظر  بگیرید که  به عنوان مجموعه اعداد صحیح غیر منفی به شمار آید و  نیز به عنوان فضای دکارتی N بعدی اعداد صحیح غیر منفی مدنظر باشد. بر این مبنا ما اقدام به تعریف ارتباط  با  به شرح ذیل می نماییم.

تاخیر تخصیص بهینه سرور صف متقارن

۵- نتیجه گیری

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