تحقیق مقاله قرار دادن پروکسی های وب دارای محدودکننده ظرفیت سرور

خلاصه

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

کلمات کلیدی

سرور شبکه، تکرار، برنامه نویسی پویا، درخت

1- مقدمه

انتشار اطّلاعات در اینترنت، تبدیل به یکی از مهمترین فعالیتها در زندگی ما شده است. با این حال، بسیاری از سیستم های موجود اغلب از تأخیرهای طولانی مدّت تجربه شده توسط مراجعه کنندگان خصوصاً در ساعات پیک رنج می برند.

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

در [10] لی و همکاران، اعلام کردند که قرار دادن پروکسی های وب، برای عملکرد وب حیاتی بوده و سیاست بهینه جاگذاری پروکسی ها برای سرور وب هدف در اینترنت برای یک محیط فقط خواندنی را بررسی کردند. آنها نشان دادند که مسأله را می توان به عنوان یک مسأله برنامه نویسی پویا، الگوسازی کرد و از این تکنیک برای بهینه سازی مدّت زمان کلی دستیابی به سرورهای وب استفاده کردند. آنها یک الگوریتم با پیچیدگی زمانی (M3n2) پیشنهاد کردند که در آن M اندازه درخت و n تعداد پروکسی هاست.

کیسو و همکارانش مسأله قرار دادن پروکسی های متعدد تکراری در یک شبکه را به عنوان یک مسأله بهینه سازی فرمولیزه کردند. آنها نشان دادند که –NP کامل می باشد و تعدادی از استدلال ها را از نظر معاوضه های بین هزینه و پیچیدگی های الگوریتم مقایسه کردند. سپس آنها چند الگوریتم جاگذاری را ایجاد کردند که از اطّلاعات بار کاری مانند اختفای مراجعه کننده و میزان درخواست برای انجام تصمیمات آگاهانه در مورد جاگذاری استفاده کردند.

نوآوری رویکردی که در این فصل در پیش می گیریم این است که در زمان تصمیم گیری در مورد محل قرار دادن موارد تکثیر شده و میزان تکرارها، ما ظرفیت سرور را یکنواخت محسوب می کنیم. این محدودیت بسیار مهم است زیرا میانگین تعداد درخواستهای ارائه خدمات شده توسط یک المثنی u بر میانگین زمان پاسخی که گره ها توسط مشاهده گر u خدمات دهی می شوند، تأثیر می گذارد. به علاوه در انواع خاصی از برنامه های پرطرفدار مبتنی بر وب، من جمله تصویر و ویدئو در زمان تقاضا، قرار دادن یک کپی از سیستم نرم افزار مناسب، مثلاً یک DBMS یا یک سیستم GIS برای خدمات دهی درخواستهای خواندن و نوشتن به همراه هر کپی از شیء، اغلب ضروری است. با این حال در بسیاری از موارد چنین سیستم هایی محدودیتهایی را برای کاربران همزمان اعمال می کنند. عملکرد سیستم در چنین موقعیتهایی را می توان با مدنظر قرار دادن بارها و محدودیتهای ظرفیت گره ها به طور قابل ملاحظه ای ارتقاء داد. به علاوه شبکه منبع اطّلاعات مولتی مدیای زیادی می شود و ارسال فایل های بزرگ برای کاربران همانند فیلم، انتظار می رود که یکی از شروط شبکه نیازمند به ظرفیت پهنای باند بالا باشد. این کار ارائه کنندگان خدمات را تشویق می کند تا زمان مد نظر قرار دادن ظرفیت گره های سرور و همچنین ظرفیت لینک ها، خدمات ارسال را بهینه سازی کنند.

مدل سیستم

شبکه از تعدادی از سایت های به هم پیوسته توسط یک شبکه ارتباطی تشکیل شده است. اشیاء می توانند در تعدادی از سایت ها تکثیر شوند از طریق گروه فرآیندها به نام المثنی که در محل نسخه دوم اجرا می شوند، کنترل می شوند. توپولوهای شبکه به وسیله یک گراف G=(V,E) نمایش داده می شود که در آن u مجموعه رئوس (یا گره ها) بوده و نشان دهنده سرورهای وب یا پروکسی ها است (n=|v| مجموع تعداد گره ها E مجموع لبه ها بوده و نشان دهنده لینک های فیزیکی متصل کننده سرورها و پروکسی ها است.) یک شیءِ درخواست شده توسط مراجعه کننده C و قرار گرفته در سرور S، از طریق یک مسیر sàr1àr2 …àrn à c  به نام مسیر ترجیع داده شده توسط  حرکت می کند. این مسیر از توالی گره ها با مسیرهای متناظر آن تشکیل شده است. مسیرها از S به مراجعه کننده های مختلف، یک درخت مسیریابی تشکیل می دهند که در طول آن درخواستها منتشر می شوند. متعاقب آن برای هر سرور وب S، یک درخت پوشای T، ریشه دارنده در S را می توان ساخت تا درخت مسیریابی را نشان دهد و کل شبکه را می توان به عنوان مجموعه ای از چنین درختهای پوشا نشان داد که هر کدام در یک سرور وب معلوم مسیریابی شده اند.

از آنجا که یک شیء از S به C توسط گره های مسیر ترجیح  عبور می کند، در صورتی که درخواست توسط یکی از گره های داخلی در مسیر سرویس دهی شود، می تواند مفید باشد. در حقیقت هر چقدر داده ها در عدد  به C نزدیکتر باشند، مزیت های آن بیشتر است.

3- الگوریتمی برای قرار دادن بهینه پروکسی ها در شبکه های درختی

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

تعرف 1. یک مجموعه اسکان، گراف، مجموعه ای از رئوس می باشد که در آن کپی هایی از شیء قرار داده می شود. حداقل مجموعه محل اسکان یک مجموعه محل اسکان است که حداقل هزینه (مثلاً حداقل زمان میانگین زمان پاسخ) را در بین تمام مجموعه های محل اسکان در گراف ارائه می کند. یک مجموعه محل اسکان n مینیمم، یک مجموعه محل اسکان مینیمم حاوی n رأس است.

اکنون اگر d(u,v) فاصله بین هر دو گره v , u در شبکه درختی باشد که مساوی با طول کوتاهترین مسیر،  بین v , u می باشد. به عبارت دیگر، طول درخت که در آن درخواست ها منتشر می شوند. در نتیجه برای هر سرور وب S، یک درخت پوشای T، کار گذاشته شده در S می تواند ساخته شود تا درخت مسیریابی را توصیف کند (شکل 1 را ببینید). و وب کلی باید به شکل مجموعه ای از این درختهای پوشا نشان داده شود که هر کدام در یک سرور وب مشخص مسیریابی می شوند.

از آنجا که یک شیء از S تا C از گره های مسیر ترجیحی  عبور می کند، اگر درخواست توسط یکی از گره های داخلی سرویس دهی شود، سودمند و مقرون به صرفه خواهد بود. در حقیقت اطّلاعات و داده ها در  به C نزدیکتر است و مزایا و فواید بیشتری دارد.

(1)                                          

P(V,S) را اوّلین پروکسی می گیریم که در حالیکه از V به S در درخت Ts حرکت می کند با درخواست مواجه می شود. ما P(V,S) را پروکسی مطلوب می گیریم. این می تواند خود V باشد اگر V یک پروکسی باشد، یا S باشد اگر هیچ پروکسی در طول راه به طرف سرور ریشه درگیر نشود. fv را توالی دسترسی از مشتری V به سرور S در طول یک دوره زمانی  می گیریم. دوره میان دو درخواست الگوریتم جاگذاری پروکسی- و  بار تحمیل شده بر پروکسی P(V,S) است توسط گره V. اگر P برنامه تکرار باشد (مجموعه پروکسی ها برای درخت Ts که همراه با عملکرد P(V,S) است) آنگاه فاصله کل برای دسترسی به پروکسی ها چنین است  و هزینه کلی دسترسی به اطّلاعات از این طریق به دست می آید:

(2)                                          

هر گره V دارای پروکسی مطلوب چنین است U=P(V,S) که یک بار  را بر u تحمیل می کند.  را یک بردار می گیریم که ظرفیت های تمام گره ها را در درخت ذخیره می کند و Kv، ظرفیت گره  باشد.

با محدودیت در ظرفیت مجموع گره های دارای پروکسی مطلوب u، نباید بار بیشتر از ظرفیت Kvیِ u تحمیل شود.

اگر  آنگاه نابرابری  همیشه باید وجود داشته باشد.

اکنون برای یک تعداد ثابت از پروکسی ها، که به این شکل بیان می شود: ، اجازه دهید تا مجموعه محل اسکان مینیمم R را پیدا کنیم که هزینه  را بر حسب زمان در درخت TS، کاهش می دهد با توجه به ظرفیتی که  پروکسی ها را محدود می سازد. بنابراین مشکل کم می شود با هزینه دسترسی  به طوری که  مشروط به: (3)               

در کل، مسأله جاگذاری نسخه ها در درخت در زمان محدودیت بر ظرفیت گره ها، یک مسأله تکمیلی NP است[8]. امّا وقتی ما به پروکسی ها توجه می کنیم در جایی که جهت درخواستهای خواندنی همیشه به طرف سرور هدف است، مسأله دیگر تکمیل NP نیست.