پروژه تحقیقی با موضوع بررسی روش‌های جایگذاری نسخه‌های تکراری در شبکه‌های توزیع محتوا

پروژه تحقیقی با موضوع بررسی روش‌های جایگذاری نسخه‌های تکراری در شبکه‌های توزیع محتوا

چکيده

در این گزارش به بررسی برخی از روش‌های جایگذاری سرورهای جایگزین در شبکه‌های توزیع محتوا (CDN) پرداخته‌ایم. این شبکه‌ها که روزبه‌روز محبوب‌تر می‌شوند، ‏‏از تکرار تمام محتوای وب‌سایت یا بخشی از آن برای نزدیک کردن محتوا به کاربران و بهبود تأخیر ارتباط استفاده می‌کنند. با توجه به اهمیت کیفیت خدمات ارائه‌شده به کاربران در این شبکه‌ها لازم است راهکارهایی اتخاذ شود تا بهترین خدمات با کمترین هزینه در اختیار کاربر قرار گیرد. به‌منظور ارائه بهینه محتوای وب، باید در مورد تعداد و محل قرارگیری سرورهای جایگزین در شبکه تصمیم‌گیری کنیم. شبکه‌های توزیع محتوای مبتنی بر ابر (‏CCDN ها) به‌عنوان نسل بعدی این شبکه‌ها توسعه داده‌شده‌اند. این شبکه‌های مدرن از مزایای معماری ابری برای کاهش هزینه دریافتی از کاربران نهایی و از مزایای مجازی‌سازی برای بهینه‌سازی تکرار محتوا استفاده می‌کنند. جایگذاری سرور جایگزین یک مسئله کلیدی در طراحی این شبکه‌ها است. این امر مستلزم قرار دادن سرورها در مکان‌های دقیق است، به‌طوری‌که هزینه به حداقل برسد و کیفیت سرویس (QoS) کاربران نهایی مطلوب باشد. بسیاری از مدل‌های جایگذاری سرور جایگزین در مقالات مربوط به CDN سنتی پیشنهادشده‌اند. ظهور پارادایم‌های مدرن، مانند محاسبات ابری و مجازی‌سازی توابع شبکه (NFV) تأثیر زیادی در تکامل معماری شبکه‌های توزیع محتوا داشته و الگوریتم‌های زیادی در این رابطه ارائه‌شده‌اند. در این مقاله، یک بررسی نسبتا جامع از الگوریتم‌های جایگذاری سرور جایگزین در شبکه‌های توزیع محتوای سنتی و مدرن ارائه می‌کنیم. سپس الگوریتم‌ها را دسته‌بندی نموده و خلاصه‌ای از ویژگی‌های آن‌ها را ارائه می‌دهیم. همچنین، شرایط لازم برای الگوریتم جایگذاری مؤثر سرور جایگزین را شناسایی کرده و مقایسه‌ای را برمبنای نیازمندی‌های شبکه انجام می‌دهیم. درنهایت، زمینه‌های ممکن برای تحقیقات بیشتر در جایگذاری سرور جایگزین در CDNs را موردبحث قرار می‌دهیم. ​

کلمات کلیدی: محاسبات ابری، شبکه‌های توزیع محتوا، مجازی‌سازی توابع شبکه، تخصیص منابع، مکان‌یابی تسهیلات، جایگذاری سرور جایگزین، طرح‌ریزی شبکه تصادفی

فهرست مطالب

عنوان                                                                                         صفحه

فصل اول: مقدمه و کلیات 1

1-1 مقدمه. 2

1-2- بیان مسئله. 2

1-3- هدف و انگیزه 4

1-4- اهمیت و ضرورت و کاربردها 5

1-5- جمع‌بندی.. 6

فصل دوم: دانش پس زمینه 7

2-1- مقدمه. 8

2-2- معرفی شبکه‌های توزیع محتوا 8

2-3- انواع شبکه‌های توزیع محتوا 12

2-3-1. CDN های سنتی.. 12

2-3-2. CDN های مدرن.. 13

2-4- مزایای استفاده از شبکه‌های توزیع محتوا 18

2-5- کاربردهای شبکه توزیع محتوا 18

2-6- پارامترهای جایگذاری سرور جایگزین در شبکه توزیع محتوا​​​​​​​​ 20

2-6-1. پارامترهای مرتبط با هزینه. 20

2-6-2. پارامترهای مرتبط با شبکه. 20

2-7 جمع‌بندی.. 22

فصل سوم: مروری بر تحقیقات پیشین 23

3-1- مقدمه. 24

3-2- مدل‌های نظری جایگذاری سرور جایگزین در CDN ​​​​ 24

3-3- مکان‌یابی تسهیلات: 25

3-3-1. مکان‌یابی تسهیلات مرتبط… 26

3-3-2.  K-میانه. 27

3-3-3.  Kمرکز کمینه. 28

3-3-4. مکان یابی K-حافظه نهان.. 28

3-4- الگوریتم‌های جایگذاری سرور رپلیکا برای cdn سنتی.. 29

3-4-1. آگاه به کیفیت سرویس…. 29

3-4-2. آگاه از سازگاری.. 34

3-4-3. آگاه از انرژی.. 38

3-4-4. سایر موارد. 40

3-5- الگوریتم‌های جایگذاری سرور رپلیکا برای نمونه‌های مدرن مبتنی بر CDN.. 43

3-5-1. CDN مبتنی بر ابر. 43

3-5-2. CDN مبتنی بر NFV.. 48

فصل چهارم: تحقیقات برگزیده 51

4-1- مقدمه. 52

4-2 برنامه‌ریزی بهینه شبکه‌های تحویل محتوای مجازی تحت تقاضای ترافیک نامشخص…. 52

4-2-1. مدل سیستم و فرضیات… 52

4-2-2. مدل بهینه‌سازی: 53

4-2-3. الگوریتم‌های برنامه‌ریزی CDN تصادفی.. 56

4-2-4. نتایج عددی.. 60

4-2-5. نتیجه‌گیری.. 67

4-3-استراتژی‌های جایگذاری رپلیکا با الگوریتم‌های خوشه‌بندی و شبکه عصبی SOM در CDN​​​​​​ 68

4-3-1. مقدمه ​​​​​ 69

4-3-2. فرمول‌های برنامه‌نویسی خطی ​​​​​​​​ 69

4-3-3. الگوریتم‌های K-means و c-means فازی و SOM برای جایگذاری سرور وب رپلیکا 71

4-3-4. زمان محاسباتی.. 75

4-3-5. شبیه‌سازی و نتایج.. 75

4-3-6. نتیجه‌گیری.. 80

4-4 یک الگوریتم جایگزین جدید برای شبکه‌های انتقال محتوای مبتنی بر ابر. 81

4-4-1. مقدمه. 81

4-4-2. مروری بر چارچوب سلسله مراتبی CCDN.. 82

4-4-3. فرمولاسیون جایگذاری سرور جایگزین مجازی.. 84

4-4-4. الگوریتم MKCF-VSP.. 90

4-4-5. ارزیابی.. 93

4-4-6. نتیجه‌گیری.. 100

4-5- جمع‌بندی.. 101

فصل پنجم: نتیجه گیری و پیشنهاد 102

5-1- مقدمه. 103

5-2- خلاصه‌ای از سمینار 103

5-3- مقایسه الگوریتم‌های جایگذاری سرور 104

5-3-1. الزامات… 104

5-4- یافته ها و نتایج سمینار 106

5-5- پیشنهاد جهت تحقیقات آینده 107

5-5-1. تعیین موازنه بار 107

5-5-2. جایگذاری VNF زنجیره ای در CDN.. 108

5-5-3. پیش‌بینی تقاضای کاربر نهایی و کاهش عدم قطعیت… 108

5-5-4. بهینه‌سازی هزینه لینک انتقال.. 109

5-5-5. روش‌های فرا ابتکاری.. 109

5-5-6. چارچوب چند منظوره 110

5-5-7. الگوریتم‌های مکان‌یابی سرور در CDN مبتنی بر Cloudlet 110

5-6- جمع‌بندی.. 111

مراجع.. 112

1-1- مقدمه

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

1-1- بیان مسئله

در ابتدا اینترنت به‌عنوان اینترنت میزبان‌ها در نظر گرفته می‌شد اما امروزه، داده‌ها و خدمات (‏یا محتوا) عوامل اصلی توسعه وب جهان‌گستر ‏هستند [1] . شبکه‌های توزیع ، ‏به‌عنوان شبکه‌های کلاینت/سرور پیشرفته، محتوا را از سرور مبدأ به روی سرورهای جایگزین تکثیر می‌کنند. برخی از سرورهای لبه[1] به‌عنوان نماینده سرور مبدأ عمل می‌کنند تا دسترسی، قابلیت اطمینان، شفافیت و کیفیت خدمات[2] دریافت شده توسط مشتریان نهایی را بهبود بخشند [2] [3]. این شبکه‌ها زیرساخت‌های توزیع‌شده بزرگی از سرورهای جایگزین حاوی نسخه‌های تکراری[3] (تکثیرشده) از داده هستند که در مکان‌های استراتژیک قرارگرفته‌اند [4] [5]‏. تکرار محتوای سرور مبدأ بر روی سرورهای جایگزین، موجب کاهش زمان تأخیر شده و محتوا با سرعت بیشتری به کاربران نهایی تحویل داده می‌شود. CDN ها از محتوای متنوعی شامل محتوای ایستا، محتوای پویا (‏امتیاز ورزشی آنلاین و قیمت سهام)‏، پخش صوتی/تصویری، اخبار و دانلود نرم‌افزاری پشتیبانی می‌کنند. در سال‌های اخیر، ظهور شرکت‌های بزرگ ‏(‏مانند یوتیوب، نت فلیکس و هولو) ‏نیز منجر به گسترش CDN ها شده است. امروزه شرکت‌ها در هر مقیاسی برای حفظ و ارتقای کسب‌وکار خود، به‌شدت به این شبکه‌ها وابسته‌اند. این شبکه‌ها  مزایایی چون: ۱)‏ کاهش بار سرورهای مبدأ از طریق واگذاری وظایف تحویل محتوا به سرورهای جایگزین، ۲)‏ کاهش تأخیر به علت نزدیک بودن میزبان‌های محتوا به کاربران نهایی، ۳) ‏بهبود قابلیت دسترسی به محتوا به دلیل وجود نقاط توزیع متعدد، و ۴)‏کاهش سربار ستون فقرات شبکه و کاهش ازدحام به دلیل اجتناب از انتقال طولانی ترافیک حجیم مانند ویدئو را در پی دارد.

یکی از مسائل مهم برای شرکت‌ها کارا بودن و در دسترس بودن سرویس‌های وبی است که ارائه می‌دهند. شرکت‌ها با داشتن تنها یک سرور برای میزبانی سرویس‌هایشان، قادر به تحقق این مهم نبوده و به همین دلیل از بستر شبکه‌های توزیع محتوا استفاده می‌نمایند. ارائه‌کننده[4] شبکه توزیع محتوا، كل وب‌سایت یک مشتری با محتوای حجیم را میزبانی می‌کنند و وظیفه‌ پردازش درخواست‌ها و تحویل محتوا به آن مشتری را بر عهده دارد. یک شبکه توزیع محتوا از تعداد زیادی سرور تشکیل‌شده است، که در سرتاسر دنیا پخش‌شده‌اند. این سرورها و ارتباطات فیزیکی یا مجازی‌شان، می‌توانند به‌صورت شبکه روی‌هم گذاری اینترنت دیده شوند. همان‌طور که می‌دانید درخواست‌های بسیاری از سرتاسر دنیا برای وب‌سایت‌های شرکت‌ها ارسال می‌شوند که باید توسط سرورهای مختلفی که در مکان‌های جغرافیایی متفاوتی قرارگرفته‌اند، پاسخ داده شوند. در این‌گونه موارد، باید درخواست‌ها به‌وسیله نزدیک‌ترین سرور به مشتری پاسخ داده شوند. پاسخ نزدیک‌ترین سرور به مشتری، باعث کاهش فاصله طی شده توسط درخواست و درنتیجه کاهش تأخیر می‌شود. هم‌چنین برای جلوگیری از اضافه‌بار روی سرورها و ازدحام روی لینک‌ها، باید درخواست‌ها در بین سرورهای مختلف تقسیم شوند.(بیان مسئله ادامه دارد)

1-1- مکان‌یابی تسهیلات:

 مدل مکان‌یابی تسهیلات شامل باز کردن امکانات با هزینه کم‌تر به‌منظور ارائه خدمات به یک یا چند شهر است. این هزینه شامل هزینه باز کردن امکانات و هزینه تحویل خدمات از تسهیلات به شهرها می‌شود. هنگامی‌که مسئله جایگذاری سرور رپلیکا از طریق مدل جانمایی ساختمان مدل‌سازی می‌شود، تسهیلات، سرورهای کپی را نشان می‌دهند و شهرها کاربران نهایی را نشان می‌دهند. هدف یافتن یک زیرمجموعه بهینه از موقعیت‌های سرور رپلیکا در F و اتصال هر کاربر نهایی در D به یکی از سرورهای رپلیکا است، به‌طوری‌که هزینه کل، یعنی هزینه باز شدن و هزینه تحویل به حداقل برسد. انواع مختلفی از مدل مکان‌یابی تسهیلات بر اساس ظرفیت سرور و توزیع بار کاربر نهایی وجود دارد. دو متغیر بر اساس ظرفیت سرور وجود دارد: ظرفیت محدود و ظرفیت نامحدود. متغیر اندازه‌گیری شده [34]‏ مدل مکان‌یابی تسهیلات شامل یک محدودیت بر روی ظرفیت سرور است که مستلزم آن است که هر سرور رپلیکا بتواند درخواست‌های کاربر نهایی را در ظرفیت موجود در آن مکان ارائه دهد. ظرفیت‌های سرور محدودیت‌های بسیار مهمی هستند که نقض آن‌ها می‌تواند تعداد زیادی از اتصالات را مختل کند و باید از آن‌ها اجتناب شود. مدل مکان‌یابی تسهیلات ازنظر ظرفیت نیز دو متغیر دارد: قابلیت نرم و قابلیت سخت. در نسخه با ظرفیت نرم، چندین سرور با ظرفیت‌های متفاوت را می‌توان در هر مکان بالقوه قرار داد. از سوی دیگر، در نسخه با قابلیت سخت،  می‌توان حداکثر یک سرور رپلیکا را  در هر مکان قرار داد. نوع بدون محدودیت ظرفیت [35]‏ ظرفیت سرور را محدود نمی‌کند، بنابراین به سرورها اجازه می‌دهد تا به هر تعداد از درخواست‌های کاربر نهایی خدمت کنند. ​

مدل مکان‌یابی تسهیلات را بر اساس اینکه آیا بار کاربر نهایی در میان سرورهای رپلیکا توزیع ‌شده است یا خیر، می‌توان به دو بخش مجزا و غیرمجزا تقسیم کرد. در نسخه تقسیم‌پذیر، بار کاربر نهایی در میان سرورهای رپلیکا تقسیم می‌شود؛ درحالی‌که در نسخه غیر تقسیم‌پذیر، کاربر نهایی توسط یک سرویس‌دهنده رپلیکا سرویس داده می‌شود. مسئله جایگذاری سرور رپلیکا موردمطالعه در [34]‏ پس از مدل مکان‌یابی تسهیلات با قابلیت سخت، مدل‌سازی شده است. مدل مکان‌یابی تسهیلات با قابلیت سخت در [36]‏ تحلیل شده است. ​یک فرمول‌بندی ILP از مدل عمومی مکان‌یابی تسهیلات (‏یعنی بدون محدودیت ظرفیت و تقسیم‌ناپذیر)‏ به‌صورت زیر داده‌شده است.

(معادلات داخل پروژه پس از خریداری موجود هستند)

در صورتی که روابط زیر برقرار باشد:

(معادلات داخل پروژه پس از خریداری موجود هستند)

در معادله (‏۱)‏، عبارت اول هزینه باز کردن را نشان می‌دهد (‏یعنی هزینه استقرار همان‌طور که در بخش ۳-الف تعریف‌شده است و عبارت دوم هزینه تحویل را نشان می‌دهد. قید(‏۲)‏نشان می‌دهد که کاربر نهایی j فقط در صورتی به مکان i اختصاص داده می‌شود که یک سرور رپلیکا روی i قرار داده شود؛ قید (‏۳) ‏تضمین می‌کند که یک کاربر نهایی باید دقیقا به یکی از مکان‌های سرور رپلیکا اختصاص داده شود. محدودیت (‏۴) ‏و محدودیت (‏۵)‏به ترتیب محدودیت برای متغیرهای تصمیم‌گیری    و  را نشان می‌دهند.

1-1-1. مکان‌یابی تسهیلات مرتبط

به‌روزرسانی سرورهای رپلیکا یک پدیده معمول در CDNها است که میزبان محتوای پویا (به‌روزرسانی‌های نقل‌قولی سهام)‏ یا برنامه‌های کاربردی تعاملی (‏شبکه‌های اجتماعی آنلاین) ‏است. به‌منظور ارائه محتوای دقیق و تازه به کاربران نهایی، سرورهای رپلیکا باید با یکدیگر سازگار و همگام شوند. این کار با توزیع به‌روزرسانی‌ها برای تمام سرورهای رپلیکا که یک نسخه از محتوا را نگه می‌دارند، انجام می‌شود. به‌روزرسانی توسط سرور مبدأ یا هر سرور جایگزین که محتوای آن تغییر کرده ارسال می‌شود. بااین‌حال، هزینه به‌روزرسانی با افزایش تعداد سرورهای رپلیکا، فاصله شبکه بین آن‌ها و نرخ نوسازی افزایش می‌یابد. در مورد برنامه‌های کاربردی تعاملی، نرخ به‌روزرسانی ، همان تعداد درخواست‌های نوشتن آغازشده توسط کاربران نهایی است؛ درحالی‌که در مورد محتوای پویا، نرخ به‌روزرسانی، فرکانسی است که با آن محتوا در سرور مبدأ تغییر می‌کند. ​

همان‌طور که مشهود است، اگر هزینه به هنگام سازی نادیده گرفته شود، قرار دادن سرورهای رپلیکا مقرون‌به‌صرفه نخواهد بود. مسئله جایگذاری سرور جایگزین آگاه از به‌روزرسانی، عموما بعد از مدل مکان‌یابی تسهیلات مرتبط مدل‌سازی می‌شود که شامل قرار دادن سرورهای رپلیکا در مکان‌های بهینه، تخصیص بهینه کاربران نهایی به سرورهای رپلیکا و اتصال سرورهای رپلیکا از طریق یک توپولوژی توزیع بهینه است. این امر با مدل عمومی مکان‌یابی تسهیلات با اعمال یک نیاز اتصال در میان سرورهای رپلیکا و سرور مبدأ متفاوت است، که با الزامات برنامه‌های کاربردی CDN تحریک می‌شود (‏به‌عنوان‌مثال برنامه‌های کاربردی تعاملی و محتوای پویا)‏. تابع هزینه در مدل مکان‌یابی تسهیلات مرتبط با معرفی هزینه به‌روزرسانی در معادله1 به دست می‌آید. نرخ به‌روزرسانی نیز یک پارامتر اضافی است که جایگذاری را کنترل می‌کند. فرض بر این است که سرورهای رپلیکا از طریق یک درخت پوشا با هزینه کمینه به هم متصل خواهند شد. بنابراین، هزینه به‌روزرسانی هزینه آن درخت است (‏به‌عنوان‌مثال درخت اشتاینر [37]‏که با پارامتر به‌روزرسانی مقیاس بندی شده است. تابع هدف در فرمول‌بندی ILP (‏شامل قیود (‏۲) تا (‏۵)‏)‏مدل تسهیلات متصل به‌صورت زیر داده‌شده است. ​

(معادلات داخل پروژه پس از خریداری موجود هستند)                       

که در آن جمله سوم در معادله (‏۶)‏هزینه به‌روزرسانی را نشان می‌دهد. آلفا پارامتر به‌روزرسانی است و  مقدار محتویات منتقل‌شده از سرور رپلیکا i به سرور رپلیکا k در طول روند به‌روزرسانی است. توجه داشته باشید که هزینه به‌روزرسانی در معادله (‏۶) ‏مربوط به هزینه درختی است که تمام سرورهای رپلیکا را به هم متصل می‌کند. با اندکی تغییر در هزینه به‌روزرسانی، درختی که سرور مبدأ را به تمام سرورهای رپلیکا متصل می‌کند، می‌تواند به دست آید. قید (‏۷)‏ محدودیت دامنه برای متغیر تصمیم  را نشان می‌دهد. ​

یکی از انواع مدل مکان‌یابی تسهیلات متصل یعنی مدل مکان تسهیلات متصل با قابلیت نرم در CDN موردمطالعه قرارگرفته است. ​