بخشی از مقاله
قرار دادن پروكسي هاي وب داراي محدودكنندة ظرفيت سرور
خلاصه
اين مقاله، مسألة يافتن يك مجموعة محل اسكان با حداقل هزينه كه هزينة خدمات دهي به درخواستهاي دستيابي در يك محيط فقط 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 به كار مي رود.
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 گره را تكثير و تعبير كند. رويكرد برنامه نويسي پويا براي الگوسازي مصرف و پيشنهاد كردن الگوريتمي كه پروكسي ها را در يك شبكة درختي قرار مي دهد مورد
استفاده قرار گرفته است. نتايج حاصل از آزمايش شبيه سازي نشان داده كه مد نظر قرار دادن ظرفيت سرورها، الگوريتم پيشنهاد شده را قادر مي سازد تا از نظر دستيابي به زمان پاسخ كمتر در سطح مراجعه كننده نسبت به الگوريتم مشابهي كه ظرفيت سرور را ناديده مي گيرد، ويژگي هاي بهتري را به نمايش مي گذارد. الگوريتم پيشنهاد شده همچنين مزيت هاي عملكردي بهتري را نسبت به رويكرد ساده اي كه پروكسي ها را به شيوه اي تصادفي تكثير مي كند، به
نمايش مي گذارد. يك بسط آتي احتمالي در اين كار مي تواند مد نظر قرار دادن توپولوژي اينترنت واقعي با استفاده از رگه هاي داده هاي واقعي به جاي داده هاي به صورت تصادفي شبيه سازي شده باشد. مقايسة عملكرد اين الگوريتم با الگوريتم هاي ديگر انجام خواهد شد و ارزيابي واقعي تري از الگوريتم در يك مقياس اينترنت ارائه خواهد شد.
