فایل بررسی الگوریتم‌های تکثیر پویای داده در شبکه های گرید و ارائه یک الگوریتم جدید

جزئیات و دریافت

این پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد.

فهرست مطالب
عنوان                                                                                             صفحه

فصل1. مقدمه    2
1-1. مقدمه    3
2-1. بیان مسئله    3
3-1. اهمیت گرید داده    4
4-1. راه¬حل¬های ممکن    5
5-1. راه¬حل پیشنهادی    5
6-1. سؤالات پایان¬نامه    8
6-1. اهداف پایان¬نامه    8
7-1. ساختار پایان¬نامه    9
فصل2. مروری بر سوابق پیشین    10
2-1. مقدمه    11
2-2. تکنیکهای تكثير داده‌    11
2-3. چارچوبي براي تكثير داده‌ها    12
فصل3. الگوریتم تکثیر پویا در گرید داده با استفاده از واکشی اولیه داده‌ها    29
3-1. مقدمه    30
3-2. معماري PDDRA    30
3-3. مراحل انجام الگوریتم PDDRA    32
3-3-1. فاز 1: ذخیره‌سازی الگوي دسترسي فايل    33
3-4. فاز 2 الگوريتم واكشي اوليه    38
3-4-1. مسئوليت مدير به‌روزرسانی كپي    40
3-4-2. ساختار سرور محلي و سايت‌هاي گريد    41
3-5. فاز 3: جايگزيني    46
3-5-1. الگوريتم جايگزيني PDDRA    48
3-6. نتیجه گیری    49
فصل4. الگوریتم پیشنهادی    50
4-1. مقدمه    51
4-2 الگوریتم پیشنهادی تکثیر داده    51
4-3. توصيف الگوريتم    53
4-3-1. فاز اول: درخواست فايل و انجام عمل تكثير    53
4-3-2 فاز دوم: جايگزيني    54
فصل5. شبیه‌سازی الگوریتم    56
5-1 مقدمه    57
5-2. شبیه‌سازی الگوریتم    57
5-2-1 الگوهاي دسترسي    59
5-2-2. فايل‌هاي پيكربندي تنظيمات اپتورسیم    61
5-3. نتايج شبیه‌سازی    62
5-3-1. پیاده‌سازی سيستم فازي    63
5-4. ارزيابي عملكرد    63
6-4. بهره‌وري از شبكه    66
فصل6. نتیجه گیری و پیشنهادات    67
6-1. مقدمه    68
6-2. راه¬حل پیشنهادی    68
6-3. نتیجه‌گیری    68
5-2. کارهای آتی    69
مراجع    70

 
فهرست شکل¬ها/جدول¬ها
عنوان                                                                                 صفحه

شكل2- 1 گره سرور    13
شكل2- 2 گره مشتری    13
شكل2- 3 تعاملات بین گره¬ها     14
جدول 2- 1. تعاملات پارامترها     15
شكل2- 4 تصويري از تعامل بين گره‌ها    16
شكل3- 1. معماری PDDRA     30
شكل3-2. استفاده از ساختار درخت براي ذخيره ترتيب دسترسي    36
شكل3-3 . درج درخواست جدید در ساختار درخت    38
شكل3- 4. عبور پیام بین سایتهای گرید و  سرور محلی    42
شكل3- 5. ساختار سرور محلی و سایتهای گرید    43
شکل4-1. توپولوژی گرید داده مورد استفاده     52
شكل 5- 1. معماری OptorSim     58
شکل4-2. میانگین زمان اجرای کارها    64
شکل4-3. تعداد نسخه¬های تکثیر شده    65
شکل4-4. بهره¬وری از شبکه    66

    
 
چكيده
ضرورت استفاده روزافزون از داده¬های توزیع‌شده در شبکه‌های کامپیوتری بر همگان مشخص است. تعداد بسيار زيادي از منابع محاسباتي و ذخيره‌سازي در كنار يكديگر قرار مي‌گيرند و گريد را تشكيل مي‌دهند. در سال‌هاي اخير تكنولوژي گريد رشد چشمگيري داشته به‌طوری‌که در اكثر تحقيقات و آزمايش‌هاي علمي مورد استفاده قرار گرفته است. چالش‌هاي بزرگي كه در گريد داده وجود دارد، نياز به دسترس پذيري بالا، كارآيي و مصرف پهناي باند پايين مي‌باشد. تكثير داده‌ها روشي است كه با استفاده از آن مي‌توان مسائلي از قبيل دسترسي به داده‌ها به صورت كارا و يا قابليت دسترس پذيري بالا را حل كرد. در يك محيطي كه از تكثير استفاده مي‌شود با افزايش تعداد نسخه‌هاي تكرار شده از فايل‌ها با بهتر شدن محلي بودن داده‌ها، كارآيي سيستم بهبود خواهد يافت.
در این پایان نامه، روش‌های مختلف تکثیر داده پویا در شبکه‌های گرید داده بررسی شده و یك الگوريتم‌ تكثير داده پويا در گريد پيشنهاد مي‌شود كه با بهره‌گيري از عوامل مؤثر بر تكثير داده‌ها، موجب كاهش زمان اجراي كارها و كاهش مصرف پهناي باند و هزينه نگهداري نسخه‌ها، می¬شود. اين الگوريتم در شبیه‌ساز اپتورسیم پیاده‌سازی شده است و نتايج حاصل از شبیه‌سازی نشان مي‌دهد كه پارامترهايي مانند ميانگين زمان اجراي كارها، تعداد نسخه‌هاي تكثيري و بهره‌وري بهبود داشته‌اند.

كلمات كليدي: گريد داده، تكثير داده، جايگزيني، الگوي دسترسي، فاصله جغرافيايي، هزينه دسترسي

فصل اول
مقدمه

1-1. مقدمه
در طول زمان انواع مختلفی از سیستم¬های توزیع شده  طراحی و پیاده¬سازی شده است، یکی از انواع سیستم¬های توزیع¬شده سیستم¬های گرید  است. ویژگی این فناوری این است که تمرکز آن بر روی به اشتراک گذاری منابع با مقیاس بزرگ است. تکثیر داده سرویسی از گرید داده است که برای سهولت و تسریع در دسترسی به داده¬ها به وجود آمده است.  
 
2-1. بیان مسئله
امروزه در رشته‌هاي مختلف، مجموعه داده‌هاي بزرگ در حال تبديل به بخش مهمي از منابع مشترك هستند. در زمينه‌های گوناگون از جمله انرژي¬های فيزيكي، بيوانفورماتيك، مشاهدات زمين، تغييرات جهاني آب و هوايي، پردازش تصوير و داده‌کاوی حجم عظيمي از داده‌هاي مورد نظر، با مقياس ترابايت و در برخي موارد با بتابايت اندازه‌گيري مي‌شوند. چنين حجم عظيمي از اطلاعات توسط محققان و دانشمندان به‌وسیله دستگاه‌هاي محاسباتي پيچيده قابل‌ دسترسی است. این محققان و دستگاه‌هاي محاسباتي و ذخیره‌ساز در سراسر جهان توزیع ‌شده‌اند.
حجم عظيم اطلاعات و محاسبات مشكلات جديدي را در مورد دسترسي به داده‌ها، پردازش و توزيع آن‌ها به وجود مي‌آورد و با حجم زيادي داده، مكان‌هاي جغرافيايي مختلف و محاسبات پيچيده درگير مي‌شود که رويارويي با چالش زيرساخت‌هاي مديريتي را دشوار مي‌کند. گريد داده یک‌ راه حل مناسب براي تمام مشكلات ذکر شده است گرید يك معماري براي مديريت توزیع ‌شده و تجزیه‌وتحلیل مجموعه داده‌هاي علمي است.
تعداد زيادي از منابع محاسباتي و ذخيره‌سازي در كنار يكديگر قرار مي‌گيرند و گريد را تشكيل مي‌دهند. موضوع و مسئله اصلي كه سبب شكل گرفتن تكنولوژي گريد شد به اشتراك‌گذاري منابع به ‌صورت هماهنگ و حل مسائل و مشكلات در سازمان‌هاي مجازي پويا و چند نهادي بود. منظور و مقصود از به اشتراك‌گذاري، تنها مبادله فايل‌هاي ساده نبود بلكه هدف دسترسي مستقيم به كامپيوترها، نرم‌افزارها، داده‌ها و ديگر منابع موجود است. گريد دسترسي آسان به همه اين منابع را فراهم مي‌كند.

3-1. اهمیت گرید داده
 انگيزه اصلي براي طراحي گريد داده اين بود كه نياز كاربران با حجم زیاد داده را پاسخ دهد، كاربران و منابع توزیع‌ شده را تحت پوشش قرار دهد و تحليل‌هاي با حجم بالاي محاسبات را پاسخگو باشد[1].
دسترسي مؤثر به چنين حجم عظيم داده كه به‌طور وسيع توزیع‌ شده است، به دليل تأخیرات شبكه و مشكلات پهناي باند كند است. با رشد اندازه يك گريد، پيچيدگي اين سيستم افزايش مي‌يابد. چالش‌ بزرگي كه در گريد داده به وجود مي‌آيد، نياز به دسترسی‌پذیری بالا، کارایی و صرفه‌جویی در ترافيك شبكه مي‌باشد.
گريد داده براي برآوردن نيازهاي مجموعه دادههاي بزرگ، توزيع جغرافيايي كاربران و منابع و تجزیه‌وتحلیل محاسبات طراحي شده است. اين معماري همچنين براي مجموعه عمليات در نواحي وسيع و محيطهاي ناهمگن توسعه داده ‌شده است. در گريد داده، كاربردهاي فني و علمي اغلب به دسترسي حجم زيادي اطلاعات نياز دارد. مديريت چنين حجم وسيعي داده توزیع‌ شده در روش  متمركز به دلیل اینکه حجم بالايي از بار به سرور مركزي تحميل ميشود كارایی لازم را ندارد. علاوه بر اينكه ذخیره‌سازی در سرور مركزي صورت می‌گیرد، مشكلاتي از قبيل خرابي در يك نقطه و تنگنا را نيز دارد. بنابراين، اين حجم زياد اطلاعات بايد در مكانهاي مختلف از سيستم توزيعي تكرار و توزيع شوند تا از این ‌گونه  مسائل و مشكلات جلوگيري گردد. گريد، داده را از نزدیک‌ترین سايت بازيابي ميكند و آن‌ها را براي سايتهاي درخواست‌کننده تكثير مينماید.
 به کمک گرید داده می¬توان حجم زیاد داده را در نقاط مختلف در سرتاسر گرید ذخیره و سپس بازیابی نمود. در این حالت کارایی گرید به پهنای باند موجود و تأخیر زمانی شبکه بستگی دارد، به‌طوری‌که پهنای باند کم، بین محل ذخیره داده و محل پردازش باعث ناکارآمدی گرید می¬گردد.

4-1. راه¬حل¬های ممکن
همان‌طور که می¬دانیم زمان دسترسی به داده، به پهنای باند ارتباطی در گرید داده بستگی دارد. در یک محیط ارتباطی، اصلی¬ترین فاکتور برای تضمین دسترسی سریع به داده¬ها، عدم تأخیر بالا است. برای کاهش زمان دسترسی از راهکارهای مختلفی استفاده می‌شود، ازجمله این راهکارها می¬توان به استفاده از برنامه¬ریزی کار اشاره کرد. یک برنامه‌ریز خوب می‌تواند تا جایی که ممکن است هزینه¬های انتقال داده را برای دسترسی سریع¬تر با اجرای کار در محل مناسب کاهش دهد. راه‌حل دیگر استفاده از مکانیسم تکثیر  است که با ایجاد کپی¬هایی  از یک نسخه باعث افزایش سرعت دسترسی به آن می‌شود، در واقع برای افزایش کارایی می‌توان چندین نسخه از فایل‌ها را در سراسر گرید ذخیره کرد[2].

5-1. راه¬حل پیشنهادی
در واقع با رشد اندازه گريد پيچيدگي ساختار هم افزايش مي‌يابد. دسترسي بالا به داده‌ها يك چالش عمده در گريد است. برنامه‌هاي محاسباتي كاربران مقدار بسيار زيادي داده دارند. نگهداري محلي يك كپي از داده بسيار گران ‌قیمت و غيرعملي است. مقابله با تأخيرات شبكه و محدوديت ظرفيت ذخیره‌سازی  در سايت‌هاي مختلف براي تأمین دسترسي بالا يك چالش دشوار است. براي پاسخ به چالش دسترسي، تكثير داده از روش‌هاي عمده به شمار مي‌رود كه دسترسی‌پذیری بالا، مصرف پهناي باند، افزايش تحمل خطا و بهبود مقیاس‌پذیری و زمان پاسخ را ترويج مي‌دهد [9-3]. هنگامی‌که داده‌ها تكثير مي‌شوند، یک كپي از فايل‌هاي داده در مكان‌هاي مختلف از گريد داده قرار مي‌گيرد، تكثير مي‌تواند موجب صرفه‌جویی مقدار زيادي پهناي باند در مقايسه با اين شرط كه داده فقط در يك سايت موجود باشد، ‌شود. از این‌ رو براي تأمین دسترسي همیشگی و سريع به داده‌ها تكثير داده معاوضه بسيار خوبي بين حافظه در دسترس و پهناي باند موجود مي‌باشد [10].
تكثير داده روشي معمول براي اصلاح کارایی در دسترسي داده‌ها در سيستم‌هاي توزيعي است. ايجاد نسخه تكراري نه‌تنها مصرف پهناي باند را كاهش مي‌دهد، بلكه تأخير دسترسي را نيز كاهش مي‌‌دهد. به‌بیان‌دیگر، افزايش کارایی خواندن داده از گره‌هاي  متناسب، هدف اصلي الگوريتم‌هاي تكثير داده است.
علاوه بر اين ميتوان دسترسي به دادهها، قابليت اطمينان، مقیاس‌پذیری سيستم، تعادل بار با انجام تكثير و صف آن‌ها را در ميان سايتهاي مختلف را افزايش داد [11].
فوايد اصلي تكثير عبارت‌اند از: [12]
1. دسترس‌پذیری بهتر: هنگام خطاي يك گره، سيستم مي‌تواند از گره ديگري به داده دسترسي داشته باشد كه دسترس‌پذیری را نیز بهتر مي‌كند.
2. کارایی بهتر: به خاطر اينكه داده ميان چندين گره تكرار شده است، كاربر مي‌تواند داده را از نزدیک‌ترین گره يا گرهی كه بار كاري کمتری دارد، به دست آورد.
تكنيك‌هاي تكثير داده مي‌توانند به دو بخش اصلي، تكثير استاتيك  و تكثير ديناميك  طبقه‌بندی شوند. در تكثير استاتيك تعداد كپي‌ها و گره ميزبان به ‌صورت استاتيك در ابتدا انتخاب مي‌شوند و كپي بيشتري بعد از آن ايجاد نمي‌شود. از سوي ديگر استراتژي پويا، مي‌تواند با توجه به ظرفيت ذخیره‌سازی و پهناي باند، كپي را در گره جديدي ايجاد کند يا خودش را با تغييرات منطبق ‌سازد و با توجه به درخواست¬ها، كپي‌هايي كه ديگر مورد نیاز نيست را حذف نمايد. در تكثير داده ايستا يك نسخه تكراري تا زماني كه توسط كاربر پاك يا طول عمرش منقضي شود موجود هست. نقص تكثير ايستا زماني است كه الگوي دسترسي گره‌ها مرتب تغيير مي‌كند و الگوريتم‌هاي ايستا توانايي سازگاري با شرايط جديد را ندارند. پس از اينكه يك كپي در يك سايت ايجاد شد تا زماني كه توسط كاربر حذف شود در آن مكان قرار ميگيرد. در روشهاي استاتيك تعيين محل كپي در زمان طراحي صورت ميگيرد و اين مكان غيرقابل تغيير ميباشد [13].
 اشكال روشهاي تكثير استاتيك اين است كه آن‌ها نميتوانند خودشان را با رفتار كاربران وفق دهند، در واقع آن‌ها براي حجم زيادي داده و تعداد زيادي كاربر مناسب نيستند.
اما در تكثير پويا، ايجاد نسخه‌هاي تكرار، حذف و مديريت آن‌ها خودكار است و قابليت سازگاري با تغيير شرايط رفتار كاربر را دارد [14]. استراتژي‌هاي پويا بهتر از استاتيك هستند چون آن‌ها مي‌توانند به ‌صورت هوشمند در مورد مكان قرار گرفتن اطلاعات در گريد تصمیم‌گیری كنند. البته اشكالاتي هم وجود دارد؛ يك مركز تصمیم‌گیری متمركز مورد نیاز است كه اطلاعات را در زمان اجرا از تمام گره‌هاي موجود در گريد جمع‌آوری كند، اگر گره‌ها در گريد داده وارد شوند و استفاده نشوند بار واحد تصمیم‌گیری مركزي افزايش مي‌يابد.
البته استراتژيهاي تكثير استاتيك مزيتهايي نظیر سرعت بالاتر از روشهاي پويا و زمان‌بندی كار را دارند. شبكههاي گريد سيستمهاي ديناميك هستند و درخواستهاي كاربران در طول زمان متغير می‌باشد تكثير پويا براي اين سيستمها مناسبتر است.

6-1. سؤالات پایان¬نامه
برخی سؤالاتی که در رابطه با تکثیر پویای داده¬ها در فصول بعدی به آن¬ها پاسخ داده خواهد شددر این قسمت بیان می¬شود.
   سه سؤال اساسي که در استراتژي تکثیر پویا مطرح می-شود:
•    چه زماني بايد كپي انجام شود؟
•    چه فايلهايي بايد تكرار شوند؟
•    كپيها كجا بايد قرار بگيرند؟
در این تحقیق باید به این سؤال پاسخ داده شود که چگونه می‌توان با تکثیر داده پویای مناسب، کارایی شبکه گرید داده را افزایش داد؟

7-1. اهداف پایان¬نامه
در این پایان‌نامه یک الگوریتم¬ تکثیر داده پویا ارائه شده است که با در نظر گرفتن پارامترهایی که در تکثیر داده مهم هستند باعث کاهش مصرف پهنای باند، دسترسي بهينه به دادهها و در کل بالا رفتن کارایی در محيطهاي توزیع‌ شده می-گردد. در اين روش عواملي كه بر کارایی گريد داده، كاهش زمان پاسخ، كاهش اشغال پهناي باند و هزينه نگهداري نسخه‌ها وجود دارد شناسايي می‌شود. در الگوريتم ارائه شده عوامل مناسب با یکدیگر تركيب شده و ارزش و هزينه نسخه‌ها را براي ما تخمين مي‌زند.

8-1. ساختار پایان¬نامه
این پایان¬نامه در شش فصل تدوین شده است.
فصل اول: به بیان کلیات پایان¬نامه می¬پردازد. در این فصل اهداف و سؤالات تحقیق نیز بیان شد.
فصل دوم: به بررسی کارهای انجام شده در زمینه¬ی تکثیر پویای داده می¬پردازد. در این فصل برخی روش¬ها و الگوریتم-های ارائه شده در این زمینه مورد بحث و بررسی قرار می-گیرد.
فصل سوم: الگوریتم واکشی داده¬ها که روش پایه برای الگوریتم پیشنهادی است دراین فصل به¬طور کامل شرح داده می-شود.
فصل چهارم: به معرفی روش پیشنهادی این تحقیق می¬پردازد.
فصل پنجم: در این فصل شبیه¬سازی روش پیشنهادی انجام می-شود نتایج حاصل از آن با برخی از روش¬های تکثیر موجود مورد مقایسه قرار گرفته است.
فصل ششم: به جمع¬بندی و نتیجه¬گیری مطالب این پایان¬نامه اختصاص داده شده است و همچنین در این فصل اشاره¬ای به کارهای آتی نیز شده است.  

فصل دوم
مروری بر سوابق پیشین

2-1. مقدمه
برخی از مطالعات اخیر مشکل استراتژی‌های تکثیر پویا در گرید  داده‌ها را مورد بحث و بررسی قرار داده اند که در این بخش برخی از آن‌ها بررسی خواهد شد.
ابتدا برخی از روش‌هایی که با استفاده از تاریخچه دسترسی به سایت‌های گرید است و الگوریتم تکرار داده¬ها به ‌صورت خودکار شرح داده می¬شود و پس از آن برخی از الگوریتم‌های مبتنی بر واکشی اولیه موجود بررسی خواهد شد.

2-2. تکنیک¬های تكثير داده‌
تكثير داده‌ پويا، روشي بهينه است كه هدف آن كاهش متوسط زمان اجرا می¬باشد. اين موضوع دسترسی‌پذیری بالاي داده‌ها و بهبود مصرف پهناي باند موجود را تضمين مي‌كند. مسائل خاصي وجود دارد كه در تكنيك تكثير داده‌ها، بايد تكثير بر اساس محدوديت‌هاي خاص انجام شود [15].
ماهيت پويا: ماهيت گريد بسيار پوياست، كاربران مي‌توانند در هرزمانی عضو شوند و یا گريد را ترك كنند بنابراين تعداد شرکت‌کنندگان حاضر در گريد در هرزمانی فرق می¬كند. الگوريتم تكثير داده بايد خودش را با تغيير اندازه گريد تطبيق دهد تا نتيجه بهتري را فراهم نماید.
معماري گريد: روش تكثير بستگي به معماري شبكه دارد. گريد داده مي‌تواند معماري‌هاي مختلف ازجمله معماری چند لایه را پشتيباني كند؛ يك ساختاري شبيه درخت كه در آن گره‌ها به ‌صورت سلسله ‌مراتب مرتب ‌شده‌اند.
روش ديگر شبيه توپولوژي گراف است و در آن هر گره مي‌تواند به گره ديگري بدون در نظر گرفتن محدودیت‌های توپولوژي درختي متصل شود. توپولوژي مي‌تواند نظیربه¬نظیر  يا هر مدل تركيبي ديگري باشد. روش تكثير بر اساس معماري طراحي شده است.
تصمیم‌گیری: تكثير داده‌ها يك تصميم بسيار مهم است. براي تكثير داده‌ كدام فايل‌ها بايد كپي شوند و كجا بايد قرار بگيرند. بسته به پاسخ، استراتژي‌هاي تكثير مختلفي تكامل پيدا مي‌كنند.
فضاي ذخیره‌سازی در دسترس: اگرچه امروزه وسايل ذخیره‌سازی خيلي ارزان شده‌اند، ولی استراتژي‌‌هاي تكثير بايد اندازه فضاي ذخیره‌سازی موجود را قبل از ساخت كپي در نظر داشته باشند.
اگر فضاي كافي براي ذخيره يك كپي وجود نداشته باشد يك استراتژي جايگزين اتخاذ می¬شود.