فایل ورد قابل ویرایش

توضیحی مختصر از متن فایل  :

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

خلاصه

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

كلمات كليدي

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

1- مقدمه

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

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

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

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

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

مدل سيستم

شبكه از تعدادي از سايت هاي به هم پيوسته توسط يك شبكة ارتباطي تشكيل شده است. اشياء مي توانند در تعدادي از سايت ها تكثير شوند از طريق گروه فرآيندها به نام المثني كه در محل نسخة دوم اجرا مي شوند، كنترل مي شوند. توپولوهاي شبكه به وسيلة يك گراف G=(V,E) نمايش داده مي شود كه در آن u مجموعة رئوس (يا گره ها) بوده و نشان دهندة سرورهاي وب يا پروكسي ها است (n=|v| مجموع تعداد گره ها E مجموع لبه ها بوده و نشان دهندة لينك هاي فيزيكي متصل كنندة سرورها و پروكسي ها است.) يك شيءِ درخواست شده توسط مراجعه كنندة C و قرار گرفته در سرور S، از طريق يك مسير sàr₁àr₂ …àr_n à 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 نزديكتر است و مزايا و فوايد بيشتري دارد.