قرار دادن پروكسي هاي وب داراي محدودكننده ظرفيت سرور

قرار دادن پروكسي هاي وب داراي محدودكننده ظرفيت سرور

قرار دادن پروكسي هاي وب داراي محدودكننده ظرفيت سرور

خلاصه

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

كلمات كليدي
سرور شبكه، تكرار، برنامه نويسي پويا، درخت

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 به كار مي رود.

1-3- الگوريتم مورد نظر

درخت Ts قرار گرفته در S با مجموعه V و رئوس را در نظر بگيريد. فرض كنيد كه بجه هر رأس بدون برگ از چپ به راست قرار گرفته است به طوري كه با داشتن هر كدام از دو خواهر V , U، مي توانيم مشخص كنيم كه U در سمت چپ V است يا برعكس. به طور كل، با داشتن y , x در Ts، گفته مي شود كه X در سمت چپ X قرار مي گيرد اگر U,V وجود داشته باشد به طوري كه  ،   و v , u با u خواهر هستند كه در سمت چپ v قرار دارند. به ازاءِ  ، Tv درخت فرعي Ts است كه در v قرار گرفته است. به ازاءِ هر  ، ما مي توانيم Tv را به 3 درخت فرعي تقسيم كنيم (شكل 2 را ببينيد):
•درخت فرعي Lv,u شامل تمام گره هاي سمت چپ u مي باشد.
•درخت فرعي شامل تمام گره ها در Tu است.
•درخت فرعي .Rv,u شامل بقيه گره هاست.
به شكل منظم داريم:
•x} سمت چپ u است:  
•درخت فرعي Tv قرار گرفته در Tu=u

  به شرط اينكه
(4)
در اينجا  ، هزينه دسترسي مينيمم به دست آمده با جاگذاري n پروكسي در Tv. بردار ظرفيت باري   گره ها در Tv به دست مي آيد. وقتي n=1 باشد، پروكسي هميشه در ريشه v قرار دارد. وقتي n>1 باشد، هميشه يك گره u پيدا مي كنيم،   كه بيان مي كند:
•يك پروكسي در u قرار گرفته است.
•در Lv,u هيچ پروكسي قرار نگرفته.
•هيچ پروكسي در   قرار نگرفته
كه كوتاه ترين مسير ميان گره هاي v,u است بدون در نظر گرفتن v,u.
با فرض اينكه Tv در گره u تقسيم شده و اينكه پروكسي هاي   در Tu جاگذاري شده اند،  ، آنگاه پروكسي هاي   در Rv.u قرار داده شده اند. بنابراين مي توانيم بنويسيم: فرمول ها در متن (5) و (6) براي تمام پروكسي هاي n، ما نياز داريم تا تمام محل هاي تقسيم بندي   و تمام مقادير ممكن   را پيدا كنيم. به طور تكراري ما پروكسي ها را در Tu و Rv,u مي گذاريم، به همان روشي كه در Tu قرار داديم. بنابراين روش برنامه ريزي ديناميك مي تواند از طريق معادلات زير فرمول بندي شود:
(7) فرمول در متن
(8) فرمول در متن
در معادله (7)،   ثابت است و مساوي با هزينه كل دسترسي به گره v از تمام گره ها در Lv,u مي باشد. اين هزينه غيرمشخص است اگر بار كلي گره ها در Lv,u بيشتر از ظرفيت Kv گره v باشد.
  به طور مكرر در Tv تعيين شده با ظرفيت محدود كننده   مربوط به گره هاي  . Rv,u به  ،   و   در اطراف گره  ، جايي كه يك پروكسي گذاشته شده است، تقسيم شده است. ظرفيت محدود كننده Rv,u نسبت به پروكسيv، ظرفيت  است كه با كسر از Kv، بار كلي تحميل شده بر v از طرف گره ها در Lv,u به دست آمده است.

4- تجزيه تحليل عملكرد

يك شبيه ساز مشتق شده از پيشامد براي ارزيابي عملكرد الگوريتم مورد نظر ما ايجاد شده است. درخواست ها در يك گره مشخص از يك مجموعه معين از مشتري ها مي رسد، هر مشتري x داراي يك ميزان درخواست مشخص است بر اساس درجه اش يعني  . (اين نظريه چنين است كه مشتريان را طبق تكرار درخواست آنها درجه بندي مي كند. در شبيه سازي ما به هر مشتري يك درجه تصادفي داده مي شود). ما فرض مي كنيم كه ميزان درخواست از مشتري x درجه iام، يك توزيع ZipF [3] را دنبال مي كند.
(B نزديك 1 است). ميزان درخواست، تكرار درخواست هاست كه از طرف مشتري x صورت مي گيرد. فاصله d(c,v)، دو گره را جدا مي سازد يعني v,u و ظرفيت هر گره در شبكه نيز به طور تصادفي ايجاد شده است. وقتي كه درخت ايجاد مي شود و پارامترهاي ورودي مختلف ايجاد مي شوند الگوريتم مورد نظر، براي تعيين جاگذاري بهينه كه كمترين اختفا را ايجاد مي كند و به طرفيت محدودكننده گره ها توجه مي كند، به كار مي رود.
ما عملكرد الگوريتم مورد نظرمان (بعد از اين به الگوريتم 1 برمي گردد) را با يك الگوريتم كه شبيه به مال ماست و بر اساس تكنيك DP ايجاد شده امّا توجهي به تحميل هيچگونه ظرفيت محدودكننده بر سرورهاي پروكسي نمي كند (بعد از اين با عنوان الگوريتم 2 ناميده مي شود) مقايسه مي كنيم. ما همچنين به يك الگوريتم كه پروكسي ها را در شبكه قرار مي دهد با روشي ساده و بي تجربه، يعني بدون محاسبه ظرفيت سرورها و هزينه كل جاگذاري، توجه كرده ايم. (از اين به بعد با عنوان الگوريتم 3 ناميده مي شود). الگوريتم 3 به عنوان يك بسترست براي تخمين ارتقاءِ خاصي كه روش تعيين جاي پيشنهاد شده ما نسبت به قرار دادن پروكسي ها به صورت تصادفي ارائه مي كند، گنجانده شده است.
شكل 5 نتايج اختفا براي خدمات دهي به يك درخواست به عنوان تابعي از تعداد پروكسي ها در شبكه ها براي سه الگوريتم را نشان مي دهد. اختفا براي هر مشتري با ضرب كردن فركانس و هزنه ارتباط تعيين مي شود. ميانگين اختفا سپس در تمام مشتريان محاسبه مي شود. نتايج شبيه سازي براي شبكه اي از هزار گره اندازه كه در آن تعداد پروكسي ها بين 30 تا 100 بوده است انجام شد. ديده شد كه نتايج در فرماني كه ديگر اندازه هاي شبكه مد نظر قرار گرفته. تغيير زيادي نكرده است. رقم نشان مي دهد كه وقتي تعداد پروكسي ها كم باشد (كمتر از 8 درصد) ميانگين اختفا در الگوريتم1، كمتر از الگوريتم هاي 2 و 3 است، با اين حال با افزايش تعداد پروكسي ها مزيت هاي عملكردي الگوريتم 1 كاهش مي يابد. اين را مي توان با اين حقيقت توضيح داد كه وقتي تعداد زيادي پروكسي وجود دارد، توزيع پروكسي ايجاد شده در هر دو الگوريتم شبيه بوده و كمتر احتمال دارد كه از ظرفيت پروكسي فراتر روند. در نتيجه هرگونه تعيين جاي بهينه ايجاد شده توسط الگوريتم 1 را مي توان به طور قابل مقايسه با آنچه كه توسط الگوريتم 2 ايجاد شده است منطبق كرد. در مقابل، آن طور كه انتظار مي رود، ميانگين اختفا براي رويكرد تصادفي (الگوريتم 3) هميشه بالاتر است. با افزايش تعداد پروكسي ها اختفا كاهش مي يابد امّا با سرعت كمتر، اين موضوع با كاهش جزيي در اختفا با افزايش پروكسي ها از 30 به 100، در شكل 6 نشان داده شده است.
شكل 6. نتايج عملكرد در زماني كه ميزان درخواست N در 3 الگوريتم متفاوت است را نشان مي دهد. ما با درخواست/ثانيه 30=N شروع كرده و آن را افزايش مي دهيم تا به 150 درخواست/ثانيه برسيم. اندازه شبكه و تعداد پروكسي ها به ترتيب 1000 و 60 تعيين شده است. وقتي ميزان درخواستها پايين است، الگوريتم 2 از الگوريتم 1 عملكرد بهتري دارد. با افزايش بيشتر ميزان درخواست، الگوريتم 1 نسبت به الگوريتم 2 عملكرد بهتري ارائه مي كند.
اين روند براي تمام مقادير N بيشتر از 70 درخواست/ثانيه ادامه پيدا مي كند. اين را مي توان با اين واقعيت كه در ابتدا تعداد درخواستها كم و بار روي سرور پايين است، توضيح داد. بنابراين زمان ارتباط از مدت زماني كه يك درخواست منتظر مي ماند تا در يك سرور پروكسي خدمات دهي شود، مهمتر است و در نتيجه الگوريتم 2، اختفاي پايين تري ارائه مي كند. با اين حال وقتي ميزان درخواست از 70 درخواست/ثانيه بيشتر مي شود، الگوريتم 1 مزيت عملكردي شفاهي نسبت به الگوريتم 2 به نمايش مي گذارد. اين به خاطر آن است كه بار سرورها با افزايش صفحه ها در سرور، حياتي مي شود و زمان انتظار يك عامل تعيين كننده در مجموع خدمات دهي به يك درخواست مي شود. در تمام موارد، الگوريتم 3 بدترين عملكرد را به نمايش مي گذارد. با افزايش درخواست ها، اختفا در اين الگوريتم به شيوه اي يكنواخت افزايش مي يابد.
شكل 7، نتايج را زماني كه اندازه شبكه متفاوت بوده و در عين حال تعداد مشابهي از پروكسي ها (6 درصد اندازه شبكه) را حفظ مي كند را نشان مي دهد. الگوريتم 1 به طور مرتب براي تمام اندازه هاي شبكه بررسي شده، عملكرد بهتري نسبت به الگوريتم 2 دارد، با اين حال هر دو الگوريتم نشان مي دهند كه ميانگين اختفا، چندان تحت تأثير اندازه شبكه قرار نمي گيرد (به خاطر داشته باشيد كه ما از درصد مشابهي از پروكسي ها نسبت به اندازه شبكه استفاده مي كنيم. با بزرگتر شدن اندازه سيستم، تنها يك افزايش جزيي در ميانگين اختفا اتفاق مي افتد. اين را مي توان به توپولوژي شبكه اختصاص داد. براي الگوريتم 3، ميانگين اختفا نسبت به الگوريتم 1 و 2 براي تمام اندازه ها بيشتر است و يك افزايش قابل توجه با اندازه سيستم وجود دارد

نتيجه گيري

اين مقاله، مسأله تعيين جاي سرور پروكسي با محدوديت هاي ظرفيت گره در يك محيط شبكه فقط خواندني را بررسي كرد. نشان داديم كه وب مي تواند فقط به عنوان مجموعه اي از درختهاي ريشه گرفته در سرورهاي هدف، الگوسازي شود تا تعيين جاي بهينه پروكسي هاي m در يك شبكه درختي متشكل از n گره را تكثير و تعبير كند. رويكرد برنامه نويسي پويا براي الگوسازي مصرف و پيشنهاد كردن الگوريتمي كه پروكسي ها را در يك شبكه درختي قرار مي دهد مورد استفاده قرار گرفته است. نتايج حاصل از آزمايش شبيه سازي نشان داده كه مد نظر قرار دادن ظرفيت سرورها، الگوريتم پيشنهاد شده را قادر مي سازد تا از نظر دستيابي به زمان پاسخ كمتر در سطح مراجعه كننده نسبت به الگوريتم مشابهي كه ظرفيت سرور را ناديده مي گيرد، ويژگي هاي بهتري را به نمايش مي گذارد. الگوريتم پيشنهاد شده همچنين مزيت هاي عملكردي بهتري را نسبت به رويكرد ساده اي كه پروكسي ها را به شيوه اي تصادفي تكثير مي كند، به نمايش مي گذارد. يك بسط آتي احتمالي در اين كار مي تواند مد نظر قرار دادن توپولوژي اينترنت واقعي با استفاده از رگه هاي داده هاي واقعي به جاي داده هاي به صورت تصادفي شبيه سازي شده باشد. مقايسه عملكرد اين الگوريتم با الگوريتم هاي ديگر انجام خواهد شد و ارزيابي واقعي تري از الگوريتم در يك مقياس اينترنت ارائه خواهد شد.

نظرات کاربران

نویسنده نظر : پيمانه آريادخت - 1398/6/1 (5:39)
تشکر مي کنم از استاد از اينکه اين فايل رو قرار داديد دانلود کردم خوب و کامل بود
 
پاسخ پشتیبانی یکتا فایل
با سلام لطف مي کنيد
 

برای ارسال نظر وارد سایت شوید