مقاله مقایسه الگوریتمهای توزیع بار Chord و Pastry در شبکه های نظیر به نظیر ساخت یافته

بخشی از مقاله

چکیده
رشد سریع حجم اطلاعات و توسعه وسیع ارتباطات اینترنتی سبب افزایش نرخ تقاضا برای توزیع و به اشتراکگذاری محتوای دیجیتال در سطح جهان شده است. یکی از گرایشات اساسی در محاسبات توزیع شده در سالهای اخیر، محبوبیت شبکه های نظیر به نظیر در ساخت برنامههای کاربردی اینترنت میباشد. از مشخصات این نوع سیستمهای شبکه ای عدم نیاز به مدیریت متمرکز و یا سازماندهی از قبل مشخص شده بوده که در آن ارتباطات به صورت همزمان انجام میگیرد.
با بزرگتر شدن اندازهی شبکه های نظیر به نظیر یکی از مسایل مهم، توزیع مناسب بار بین اعضای تشکیل دهنده آنها میباشد . در این تحقیق سعی شده است به منظور افزایش کارایی در ساخت و پیاده سازی شبکه های نظیر به نظیر ساخت یافته، به مقایسه دو نمونه از پرکاربردترین الگوریتمهای توزیع بار در این شبکه ها به نامهای Chord و Pastry پرداخته شود. در این بررسی با توجه به تعداد نودها، سه حالت مختلف جستجوی بازگشتی، انتقالی و تکراری در الگوریتمهای فوق توسط محیط شبیه ساز ارزیابی شدهاند. نتایج حاصل از شبیه سازی نشان میدهد که در هر سه حالت جستجو، الگوریتم Pastry بهترین کارایی را از خود نشان میدهد.
واژههای کلیدی: شبکه نظیر به نظیر، جدول هش توزیع شده، Chord، .Pastry

-1 مقدمه
امروزه گسترش جهانی استفاده از اینترنت در زمینه های مختلف از جمله تجارت، سبب توسعه انواع مختلفتکنولوژیهایی گردیده است که میتوانند از اینترنت به عنوان بستری مناسب برای ساخت خود استفاده کنند. از جمله این تکنولوژیها Web2.0، شبکه های نظیر به نظیر، شبکه های اجتماعی، سرویسهای چندرسانه ای و...میباشند که با استفاده از محاسبات توزیع شده به توسعه برنامههایی همچون سرویسهای بلادرنگ، چندرسانه ای و سیستمهای اشتراک فایل وسیع می پردازند .[1] یکی از مسایل جذاب در زمینه محاسبات توزیع شده، محبوبیت شبکه های نظیر به نظیر در ساخت برنامههای بزرگ توزیع شده امروزی در سطح اینترنت بوده که به حل مسایل مربوط به توزیع و پردازش اطلاعات انبوه پرداخته است. هدف اصلی از به کار بردن آنها جمع آوری و استفاده از منابع و اطلاعات موجود بر روی کامپیوترهایی است که به صورت گسترده در سطح اینترنت توزیع شدهاند تا بتوان به کمک آنها راهحلهای قابل توسعه برای پردازش و توزیع انبوهی از اطلاعات با حداقل هزینه را ارائه نمود.
از تفاوتهای اساسی بین شبکه های نظیر به نظیر با شبکه های سرویس گیرنده/سرویس دهنده ظرفیت بالای شبکه در فراهمی دادهها بین اعضای آن میباشد، به گونه ای که برخلاف شبکه های سرویس گیرنده/سرویس دهنده که کلیه اطلاعات و سرویسها از طریق یک سرور مرکزی انجام میگیرد. در شبکه های نظیر به نظیر هر کدام از اعضا با به اشتراک گذاری منابع خود مانند پروسسور، رسانه ذخیره سازی، پهنای باند شبکه و ... می توانند باعث افزایش کارایی و ظرفیت شبکه شوند. در سالهای اخیر، این شبکه ها برای طراحی سیستمهای توزیع شده در مقیاس بالا نقش بسیار مهمی پیدا کردهاند .[2]شبکه های نظیر به نظیر از جمله تکنولوژیهای بالقوهای هستند که میتوانند برای توسعه و گسترش برنامه های توزیع شده کاملاً غیر متمرکز و مقیاس پذیر عمل کرده و بسیاری از نیازهای مختلف برنامه هایکاربردی را پشتیبانی نماید. با بزرگ شدن اندازه این شبکه ها یکی از مسایل مهم قابل بررسی، توزیع مناسب اطلاعات بین اعضای همکار میباشد به نحوی که کارایی سیستم در حداکثر مقدار خود قرار گیرد . [3] بنابراین ضرورت بررسی الگوریتمهای مختلف توزیع بار برای رسیدن به این منظور بسیار اهمیت دارد .[1]
این تحقیق در نظر دارد به منظور افزایش کارایی در ساخت و پیادهسازی شبکه های نظیر به نظیر به بررسی یکی از عوامل مؤثر در این زمینه تحت عنوان توزیع بار بپردازد. بدین ترتیب معیارهای مهم در امر توزیع بار همچون نحوهی جستجوی اطلاعات مورد بررسی قرار می گیرند و دو نمونه از پرکاربردترین الگوریتمهای توزیع بار انتخاب گردیده و توسط یک محیط شبیه ساز به مقایسه این الگوریتمها پرداخته میشود.
در نهایت با مقایسه و بررسی نتایج حاصل از شبیهسازی مناسبترین الگوریتم پیشنهاد میشود. یافتن چنین الگوریتمی سبب کاهش مدت زمان جستجو و پاسخ میگردد که به عنوان دو عامل مهم در راندمان و کارایی شبکه های بزرگ مؤثر می باشند.

-2شبکه های نظیر به نظیر
شبکه های نظیر به نظیر به عنوان پلت فرمی کارا برای توسعه برنامههای توزیع شدهی مقیاس پذیر و قدرتمند میباشند. امکاناتی همچون دسترسی مستقیم بین کامپیوترهای توزیع شده، به اشتراکگذاری منابع کامپیوترها از طریق تبادل مستقیم، خود سازماندهی و مدیریت غیرمتمرکز منابع، محبوبیت این شبکه ها را برای ساخت شبکه های مجازی بیشتر کرده است .[4] امروزه بسیاری از موضوعات وابسته به شبکه های نظیر به نظیر مربوط به شاخص دهی، مسیر یابی، کنترل تصادم و امنیت در این شبکه ها میباشد .[5]
بر اساس نحوهی کنترل موقعیت دادهها و با توجه به توپولوژی شبکه عموماً شبکه های نظیر به نظیر به دو دسته تقسیم میشوند: شبکه های نظیر به نظیر غیر ساخت یافته و شبکه های نظیر به نظیر ساخت یافته. در شبکه های نظیر به نظیر غیر ساخت یافته هیچ محدودیتی در نحوهی قرارگیری دادهها بروی شبکه وجود ندارد و توپولوژی شبکه میتواند کاملاً دلخواه باشد. شبکه های غیر ساخت یافتهدارای مشکلاتی همچون عدم مقیاس پذیری، عدم تضمین کیفیت و کارایی جستجوها و وجود نقطه خرابی میباشند. در شبکه های نظیر به نظیر ساخت یافته معماری و ساختار شبکه و محل قرارگیری دادهها به طور دقیق مشخص میگردد. همسایگان هر نود به طور کامل مشخص شده و دادهها در یک موقعیت دقیق و مشخص شده ذخیره میشوند.
یکی از نمودهای ویژه جهت تخصیص اطلاعات بین نودها که به عنوان یک را هحل استاندارد برای شبکه های نظیر به نظیر مورد توجه قرار می گیرد، استفاده از جدول هش توزیع شده (DHT) میباشد 9]،8،7،.[6

جدول هش توزیع شده به عنوان یک الگوریتم مسیریابی و توزیع بار غیرمتمرکز برای ایجاد سرویس جستجو در شبکه های نظیر به نظیر ساخت یافته شناخته میشود. در این الگوریتم یک زوج مرتب (key,value) ذخیره شده و به جستجو ارزش((Value وابسته به کلید داده شده پرداخته میشود. کلیدها و ارزشها در کل سیستم توزیع میشوند و یک سیستم DHT باید این اطمینان را به وجود آورد که تمام نودهای موجود در سیستم اطلاعات کافی درباره کلیه کلیدها و ارزشها را دارند. بدین ترتیب میتوانند به ارسال اطلاعات و پردازش درخواست های مورد جستجو بپردازند. یک الگوریتم DHT مسئولیت توزیع کلیدها و ارزشها را به گونهای بر عهده دارد که جستجوی مؤثر یک ارزش وابسته به کلید خاص امکانپذیر باشد.

این جداول با داشتن الگوریتمهای خود سازمانده و مقیاسپذیر برای بازیابی و مدیریت دادهها در مقایسه با راهبردهای غیر ساخت یافته دارای مزایای فراوانی هستند. در توسعه کارا و مؤثر الگوریتمهای DHT توجه به عوامل تأثیرگذار در شکل گیری و اجرای این الگوریتمها حائز اهمیت میباشد. یکی از فاکتورهای قابل ملاحظه در کارایی این الگوریتمها نرخ تأخیر در مسیریابی اطلاعات توسط این الگوریتمها بوده که میتواند تحت تأثیر عوامل بسیاری از جمله تکنیکهای جستجوی اطلاعات قرار گیرد.

-1-2 تکنیکهای جستجو
تکنیکهای جستجوی اطلاعات که در جداول هش توزیع شده مورد استفاده قرار میگیرند به سه دسته کلی تقسیم میشوند: جستجوی بازگشتی، جستجوی تکراری و جستجوی انتقالی.
به طور کلی هنگام انجام یک فرایند جستجو توسط نود مبدأ عمل جستجو به سمت نود مقصد با شناسه مشخص آغاز میگردد و پس از یافتن آن نود عملیات مورد نظر که میتواند شامل قرار دادن داده، بازیابی اطلاعات و یا حذف کردن باشد انجام میگیرد.

در یک جستجوی بازگشتی هر نود در فرایند مسیریابی به صورت بازگشتی از نود بعدی در مورد شناسه مقصد سؤال کرده و در نهایت پاسخ هر نود به صورت بازگشتی به نود اول بر گردانده میشود. در جستجوی تکراری نود آغازین با اولین نود بعدی در مسیر جستجو ارتباط برقرار کرده و آدرس دومین نود را از آن دریافت میکند. سپس با دومین نود ارتباط برقرار کرده و آدرس نود سوم را جویا شده و این فرایند تا رسیدن به نود مقصد ادامه پیدا میکند.

جستجوی انتقالی ترکیبی از دو جستجوی بازگشتی و تکراری بوده به نحوی که در ابتدا به روش بازگشتی نود مقصد شناسایی شده و سپس پاسخ به طور مستقیم از نود مقصد به نود مبدأ فرستاده میشود.

-2-2 الگوریتمهای توزیع بار در DHT

از جمله عوامل مؤثر که در ساخت و توسعه شبکه های نظیر به نظیر مورد بررسی قرار میگیرند، میتوان به الگوریتمهای توزیع بار DHT اشاره نمود. این الگوریتمها نقش به سزایی در کارایی و مقیاس پذیری این نوع شبکه ها ایفا می کنند. در این تحقیق به بررسی دو نمونه از مهمترین این الگوریتمها پرداخته میشود.

Chord -1-2-2
الگوریتم Chord یک الگوریتم هش توزیع شده غیرمتمرکز برای اتصال نودها در یک شبکه نظیر به نظیر میباشد 10]،.[11 الگوریتم Chord به طور یکنواخت یک کلید را به یک نود نگاشت میکند. کلیدها و نودها هر کدام داری یک شناسه m بیتی میباشند.
در الگوریتم Chord، نودها به صورت یک حلقه منطقی سازمان دهی میگردند و هر نود دارای یک مجموعه از اشارهگرها به نودهای همسایه خود میباشد که در یک فضای لگاریتمی در اطراف حلقه قرار میگیرند . به علاوه هر نود یک لینک به نود بعدی و قبلی خود دارد. جدول مسیریابی Chordکه اصطلاحاً Finger table نام دارد، برای هر نود به طور جداگانه ساخته می شود و هر نود را قادر به دسترسی به سایر نودهای دورتر در حلقه با پیمایش در جهت حرکت عقربه های ساعت میگرداند. موقعیت هر نود در حلقه از صفر تا 2m-1 شماره گذاری می گردد و کلید k به Successor(k) انتصاب داده می شود و آن نودی است که شناسه آن برابر یا دنباله رو شناسه k میباشد. اگر در شبکه N نود و k کلید وجود داشته باشد، هر نود مسئول k/N کلید خواهد بود. شکل (1) نمونهای از حلقه Chord را نمایش میدهد .[12]
شکل -1 حلقه [12] Chord

در حالت پایدار، هر نود که در شبکه Chord شرکت میکند، اطلاعاتی در حدود O(log N) در مورد نودهای دیگر را نگهداری می کند و همچنین عمل جستجو را ازطریق O(log N) پیام انجام میدهد. با ورود نودها به شبکه و یا جدایی آنها از شبکه ، الگوریتم Chord تضمین میکندکهجستجویهردادهدرمرتبهایکمتراز انجام میشود.

Pastry -2-2-2
Pastry یک الگوریتم مقیاس پذیر و خود سازمانده در شبکه های نظیر به نظیر ساخت یافته میباشد. در شبکه های بر مبنای Pastry به هر نود و شی یک شناسه تصادفی از یک فضای شناسهای بزرگ انتصاب داده میشود. شناسه هر نود و هر کلید یک عددی 128 بیتی میباشد که به صورت یک توالی از رقمها در مبنای 2b نشان داده میشود. b یک پارامتر پیکربندیبوده که معمولاً 3 یا 4 می باشد.
Pastry بر پایه توابع هش ثابت ساخته شده است و یک سیستم مسیریابی پیشوندی می باشد. در این الگوریتم از هندسه حلقه و درخت به صورت ترکیبی استفاده میشود و همچنین قابلیت مسیریابی مجاورتی و انتخاب نودهای همسایه به صورت مجاورتی را دارد.
به منظور عمل مسیریابی، شناسه نودها و کلیدها به صورت یک توالی از رقمها در مبنای 2b نام گذاری میشوند. الگوریتم Pastry در مسیریابی پیامها آنها را به سمت نودهایی که شناسه آن نود از لحاظ عددی نزدیکتر به کلید داده شده باشد، ارسال می کند. به این ترتیب که در هر مرحله از مسیریابی یک نود به طور معمول به ارسال پیام به سمت نودی که شناسه آن با کلید داده شده دارای پیشوندی حداقل با یک رقم بیشتر از پیشوند نود کنونی باشد، میپردازد، اگر دو نود دارای پیشوند یکسان باشند پیام به سمت نودی که شناسه آن از لحاظ عددی نزدیکتر به کلید باشد، فرستاده میشود. شکل (2) یک مسیریابی پیشوندی در Pastry را نمایش میدهد .[12]