خلاصه
این مقاله، مسألة یافتن یک مجموعة محل اسکان با حداقل هزینه که هزینة خدمات دهی به درخواستهای دستیابی در یک محیط فقط c مدنظر قرار می دهد. مجموع هر بار تحمیل شده بر هر پروکسی نباید از ظرفیت آن بیشتر شود. نتایج حاصل از شبیه سازی نشان می دهد که الگوریتم جای گذاری پیشنهادی ما سطوح عملکردی خوبی را نشان می دهد و به تعادل بار یکسان در پروکسی های متفاوت دست می یابد:
کلمات کلیدی
سرور شبکه، تکرار، برنامه نویسی پویا، درخت
1- مقدمه
انتشار اطّلاعات در اینترنت، تبدیل به یکی از مهمترین فعالیتها در زندگی ما شده است. با این حال، بسیاری از سیستم های موجود اغلب از تأخیرهای طولانی مدّت تجربه شده توسط مراجعه کنندگان خصوصاً در ساعات پیک رنج می برند.
یک ایدة کلیدی برای حل این مشکل، فراهم کردن سرورهای تکرار شده در محل های متفاوت برای کاهش تعداد عملیاتهای بازیابی شیء در فواصل زیاد و متعادل کردن بار سایت های پرطرفدار می باشد. این کار هزینه را کاهش داده و زمان کلی پاسخگویی در شبکه را ارتقاء می دهد. بسیاری از الگوریتم ها برای تکرار شیء ظرف سالهای گذشته پیشنهاد شده اند. با این حال بسیاری از آنها توجه کمّی به ظرفیت سرور در طی جاگذاری تکرار برای تضمین بار کافی محاسبه شدة مجموع تحمیل شده به یک سرور خاص از مجموع ظرفیت محاسبه ای آن بیشتر نشود، داشته اند.
در [10] لی و همکاران، اعلام کردند که قرار دادن پروکسی های وب، برای عملکرد وب حیاتی بوده و سیاست بهینة جاگذاری پروکسی ها برای سرور وب هدف در اینترنت برای یک محیط فقط خواندنی را بررسی کردند. آنها نشان دادند که مسأله را می توان به عنوان یک مسألة برنامه نویسی پویا، الگوسازی کرد و از این تکنیک برای بهینه سازی مدّت زمان کلی دستیابی به سرورهای وب استفاده کردند. آنها یک الگوریتم با پیچیدگی زمانی (M3n2) پیشنهاد کردند که در آن M اندازة درخت و n تعداد پروکسی هاست.
کیسو و همکارانش مسألة قرار دادن پروکسی های متعدد تکراری در یک شبکه را به عنوان یک مسألة بهینه سازی فرمولیزه کردند. آنها نشان دادند که –NP کامل می باشد و تعدادی از استدلال ها را از نظر معاوضه های بین هزینه و پیچیدگی های الگوریتم مقایسه کردند. سپس آنها چند الگوریتم جاگذاری را ایجاد کردند که از اطّلاعات بار کاری مانند اختفای مراجعه کننده و میزان درخواست برای انجام تصمیمات آگاهانه در مورد جاگذاری استفاده کردند.
نوآوری رویکردی که در این فصل در پیش می گیریم این است که در زمان تصمیم گیری در مورد محل قرار دادن موارد تکثیر شده و میزان تکرارها، ما ظرفیت سرور را یکنواخت محسوب می کنیم. این محدودیت بسیار مهم است زیرا میانگین تعداد درخواستهای ارائة خدمات شده توسط یک المثنی u بر میانگین زمان پاسخی که گره ها توسط مشاهده گر u خدمات دهی می شوند، تأثیر می گذارد. به علاوه در انواع خاصی از برنامه های پرطرفدار مبتنی بر وب، من جمله تصویر و ویدئو در زمان تقاضا، قرار دادن یک کپی از سیستم نرم افزار مناسب، مثلاً یک DBMS یا یک سیستم GIS برای خدمات دهی درخواستهای خواندن و نوشتن به همراه هر کپی از شیء، اغلب ضروری است. با این حال در بسیاری از موارد چنین سیستم هایی محدودیتهایی را برای کاربران همزمان اعمال می کنند. عملکرد سیستم در چنین موقعیتهایی را می توان با مدنظر قرار دادن بارها و محدودیتهای ظرفیت گره ها به طور قابل ملاحظه ای ارتقاء داد. به علاوه شبکه منبع اطّلاعات مولتی مدیای زیادی می شود و ارسال فایل های بزرگ برای کاربران همانند فیلم، انتظار می رود که یکی از شروط شبکة نیازمند به ظرفیت پهنای باند بالا باشد. این کار ارائه کنندگان خدمات را تشویق می کند تا زمان مد نظر قرار دادن ظرفیت گره های سرور و همچنین ظرفیت لینک ها، خدمات ارسال را بهینه سازی کنند.
مدل سیستم
شبکه از تعدادی از سایت های به هم پیوسته توسط یک شبکة ارتباطی تشکیل شده است. اشیاء می توانند در تعدادی از سایت ها تکثیر شوند از طریق گروه فرآیندها به نام المثنی که در محل نسخة دوم اجرا می شوند، کنترل می شوند. توپولوهای شبکه به وسیلة یک گراف G=(V,E) نمایش داده می شود که در آن u مجموعة رئوس (یا گره ها) بوده و نشان دهندة سرورهای وب یا پروکسی ها است (n=|v| مجموع تعداد گره ها E مجموع لبه ها بوده و نشان دهندة لینک های فیزیکی متصل کنندة سرورها و پروکسی ها است.) یک شیءِ درخواست شده توسط مراجعه کنندة C و قرار گرفته در سرور S، از طریق یک مسیر sr1r2 …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 نیست.
شکلهای 2b , 2-a، تقسیم Tv به سه درخت فرعی را نشان می دهند. مسألة اصلی، تقسیم مسأله به مسایل فرعی در مقیاس های کوچک است. به همین دلیل ما نیاز به تقسیم بندی بیشتر Rv,u، به درخت های فرعی کوچکتر داریم. برای هر ، چنین می گوییم:
y} در سمت چپ قرار دارد و
خاصیت تکرار شدن راه حل، ، معادلة 3، برای حاصل های Tv به کار می رود.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 12 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله قرار دادن پروکسی های وب دارای محدودکنندة ظرفیت سرور
