مقاله طراحی یک سیستم نظیربه نظیر آگاه از توپولوژی بر اساس پروتکل Chord

word قابل ویرایش
17 صفحه
دسته : اطلاعیه ها
12700 تومان
127,000 ریال – خرید و دانلود

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

١- مقدمه
یک شبکه نظیربه نظیر (PP٢)، سیستم توزیع شدهای است که به طور عادی فاقد ساختار سلسله مراتبی و سیستم کنترل مرکزی میباشد. این شبکه ، یک شبکه منطقی روئین است که بر روی لایه فیزیکی قرار دارد. هر یک از گره های این شبکه میتواند از طریق این لایه فیزیکی و تنها با استفاده از گره های مجاور خود، با گره های دیگر اتصال برقرار کند. هر یک از این گره ها که تحت عنوان یک نظیر۴ نیز شناخته می شود، به صورت خودمختار عمل میکند. اطلاعاتی که در این سیستم وجود دارد، به صورت تقریبا یکنواخت میان تمام گره های موجود در شبکه توزیع شده است و هیچ گره ای نسبت به گره های دیگر ارجحیت ندارد. بنابراین بر خلاف مدل سرویس دهنده–مشتری ، در شبکه های نظیربه نظیر هر گره میتواند هم به عنوان سرویس دهنده و هم به عنوان مشتری عمل کند.
شبکه های نظیربه نظیر به طور کلی به دو دسته شبکه های ساختاریافته ۵ و شبکه های غیر ساختاریافته ۶ تقسیم می شوند. در شبکه های ساختاریافته هر آیتم اطلاعات در گره ی معینی نگهداری میشود اما در شبکه های غیر ساختاریافته ، این آیتم ها به صورت تصادفی و نامشخص بین گره ها پخش شده اند[۴]. مهمترین برتری شبکه های ساختاریافته نسبت به شبکه های غیر ساختاریافته ، مقیاس پذیری بالای این شبکه ها است . برای پیادهسازی این شبکه ها، دو مکانیزم اصلی باید وجود داشته باشند: (١) محول کردن هر یک از آیتم های محتوی به یکی از گره ها (٢)جستجوی ٧ گره ی دربرگیرنده آیتم خواسته شده و بازیابی محتوی آن با توجه به کلید آن آیتم . در شبکه های ساختار یافته مبتنی بر جدول هش توزیع شده ۸(DHT)، برای پیادهسازی این دو مکانیزم، ابتدا با استفاده از یک الگوریتم هش ٩ معین ، نام گره ها و هر یک از کلیدها هش شده و سپس به عنوان شناسه ١٠ اختصاصی آن کلید و یا گره در نظر گرفته میشود. با توجه به فضای هش مورد استفاده، هر گره به عنوان مسئول نگهداری تمام محتوی هایی که شناسه کلید آنها نزدیک شناسه آن گره است ، شناخته میشود. برای پیدا کردن محتوای کلید مورد نظر، هر گره با استفاده از یک جدول هش کوچک که اطلاعات محدودی در مقایسه با تعداد کل گره ها در خود نگهداری میکند، بسته درخواست محتوی کلید را به گره مناسب بعدی میفرستد و در نهایت با پیمایش تعداد محدودی از گره ها، این درخواست به گره نگهدارنده محتوی آن کلید رسیده و محتوی آن بازیابی می شود. پروتکل های Chord [٣]، CAN [٨]، Pastry [٩] و Tapestry [١٠] از معروف – ترین پروتکل های مبتنی بر جدول هش توزیع شده هستند.
یکی از مشکلاتی که در بیشتر پروتکل های مبتنی بر DHT وجود دارد، عدم در نظر گرفتن توپولوژی فیزیکی شبکه و محل قرار گرفتن گره های دیگر در هنگام اضافه کردن گره جدید به شبکه است (پروتکل های Pastry و CAN این مسئله را در نظر میگیرند).
پروتکل Chord یکی از معروف ترین و پرکاربردترین سیستم های نظیربه نظیر مبتنی بر DHT به شمار میآید. این پروتکل در عین بهره – مندی از قابلیت های مطلوبی از جمله مقیاس پذیری و انعطافپذیری بالا، ساختار سادهای دارد. با این وجود، در پروتکل Chord مسیر بین دو گره در شبکه روئین ممکن است با مسیر فیزیکی بین این دو گره کاملا متفاوت باشد زیرا این پروتکل در هنگام ساختن شبکه روئین ، توپولوژی شبکه فیزیکی را در نظر نمی گیرد[۵].
در این مقاله با استفاده از پروتکل Chord، الگوریتم جدیدی به نام TAC11 پیشنهاد میکنیم که محل جغرافیایی گره ها را در هنگام ورود آنها به شبکه در نظر میگیرد. برای این منظور، هر گره علاوه بر حلقه عمومی که در هنگام ورود به شبکه در آن قرار گرفته است ، با گره های دیگری که با آنها در ناحیه ١٢ فیزیکی یکسانی قرار دارد حلقه دیگری به نام حلقه محلی تشکیل میدهد. این حلقه محلی باعث میشود تا گره – هایی که در یک ناحیه جغرافیای قرار دارند از وجود یکدیگر آگاه شده و در نتیجه توپولوژی شبکه فیزیکی در تشکیل شبکه رویین لحاظ شود. در این پروتکل ، هر گره علاوه بر جدول Finger_table که به صورت عادی در پروتکل Chord مورد نیاز است ، با استفاده از اطلاعات گره های تشکیل دهنده حلقه محلی ، جدول دیگری به نام Zone_finger_table تشکیل میدهد. با استفاده از این جدول هر گره سعی می کند تا در هنگام مسیریابی ، گره بعدی را از میان گره های هم ناحیه خود انتخاب کند. تمامی مکانیزمهای مربوط به تشکیل و به روزرسانی این جدول ، مشابه با مکانیزم های به کار رفته در جدول Finger_table خواهند بود با این تفاوت که به جای در نظر گرفتن گره های حلقه عمومی در تشکیل جدول Finger_table، برای تشکیل جدول Zone_finger_table گره های حلقه محلی در نظر گرفته می شوند.
یکی از مزیت های اصلی پروتکل پیشنهادی ، ویراش اندک مکانیزم های پروتکل Chord و در نتیجه حفظ تمام ویژگی های مطلوب آن، اعم از سادگی و مقیاس پذیری است . در این پروتکل ، به غیر از گنجاندن حلقه محلی برای تشکیل جدول Zone_finger_table و ویرایش الگوریتم مسیریابی ، بقیه مکانیزم های Chord حفظ شدهاند.
ادامه این مقاله به صورت زیر ترتیب داده شده است : بخش ٢، خلاصه ای از کارهای قبلی انجام شده در ارتباط با بهبود مبحث آگاهی از توپولوژی پروتکل Chord را مورد بحث قرار داده است . در بخش ٣ پروتکل پیشنهادی خود را ارائه میدهیم و در بخش ۴ به ارزیابی این روش با استفاده از نتایج حاصل از شبیه سازی خواهیم پرداخت . بخش ۵ و آخرین بخش این مقاله ، به جمع بندی مطالب ارائه شده اختصاص دارد.
٢- پیش زمینه
٢-١- شبکه نظیربه نظیر Chord
یک سیستم نظیربه نظیر ساختاریافته از تعدادی گره به همراه مجموعه – ای از دادهها به صورت دوتایی «کلید، محتوی » تشکیل شده است . هر یک از این گره ها مسئول نگهداری تعدادی از این دادهها هستند به شرطی که ١) تعداد دادههای ذخیره شده در تمام گره ها تقریبا برابر باشد؛ ٢) با داشتن کلید یک محتوی ، گره نگهدارنده محتوی آن کلید با جستجوی تعداد محدودی از گره ها شناسایی شود.
بنابراین هر سیستم نظیربه نظیر باید بتواند مکانیزمی برای حل مسئله -های زیر ارائه کند:
• توزیع دادهها به صورت یکنواخت میان گره های شبکه
• جستجو١٣ی گره مسئول یک کلید دلخواه و بازیابی محتوی آن توسط هر یک از گره ها.
پروتکل Chord [٣]، یک پروتکل پیادهسازی شبکه های نظیربه نظیر ساختاریافته است . در این پروتکل با استفاده از تابع درهم ریزی همسان ١۴، هر کدام از کلیدها به یکی از گره ها انتساب داده می شود.
برای این منظور، ابتدا با استفاده از تابع درهم ریزی ، به هر کدام از گره ها و کلیدها یک شناسه m بیتی اختصاص داده میشود. شناسه هر گره با درهم ریختن آدرس IP آن، و شناسه هر کلید با درهم ریختن نام آن کلید تولید میشود. مجموعه تمام این شناسه ها یک فضای یک بعدی حلقوی به پیمانه m٢ تشکیل میدهند (شکل ١). با در نظر گرفتن این فضای حلقوی ، هر محتوی در اولین گره ای که شناسه آن بزرگتر از شناسه کلید این محتوی است ، ذخیره میشود. این تکنیک در توزیع دادهها باعث میشود که با به کارگیری خواص تابع درهم ریزی همسان ، هر کدام از گره های موجود در شبکه ، تعداد تقریبا یکسانی از داده ها را در خود جای دهند و بار دادهها به صورت یکسان میان گره ها تقسیم -شود. علاوه بر تقسیم متعادل بار، در صورت اضافه شدن یک گره جدید به شبکه ، تنها تعداد محدودی از دادهها میان گره ها جابجا خواهند شد.
شکل (١): نحوه قرار گیری داده ها در گره های شبکه با توجه به فضای
حلقوی ایجاد شده در پروتکل Chord [٣]
به منظور جستجو و بازیابی محتوی کلید خواسته شده، هر یک از گره ها دارای جدولی به نام Finger_table است که شناسه و آدر س گره دیگر را در خود نگهداری میکند. هنگامی که یک درخواست جستجوی کلید١۵ به یکی از گره ها میرسد، این گره ابتدا موجودیت محتوی مربوط به کلید خواسته شده را در لیست محتویات خود بررسی میکند. در صورتی که محتوی یافت نشود، با بررسی گره – های موجود در جدول Finger_table، گره مناسب بعدی را انتخاب کرده و این درخواست جستجو را مجددا برای آن گره ارسال می کند.
گره بعدی به نحوی انتخاب میشود که شناسه آن، نزدیک ترین مقدار کوچکتر از شناسه کلید، با توجه به فضای حلقوی باشد. به این ترتیب درخواست جستجو به تدریج به سمت گره ای که محتوی کلید خواسته شده در آن قرار دارد پیش رانده میشود و پس از رسیدن درخواست به این گره ، محتوی کلید بازیابی میشود.
٢-٢- آگاهی از توپولوژی در شبکه های نظیربه نظیر
هر سیستم نظیربه نظیر یک شبکه منطقی ١۶ است که بر روی شبکه فیزیکی (IP) قرار دارد. هر گره در این شبکه تنها میتواند با استفاده از گره های مجاور خود با دیگر گره ها ارتباط برقرار کند. بنابراین هنگامی که گره جدیدی به این شبکه میپیوندد، لازم است تا گره های همسایه آن مشخص شوند. در نظر گرفتن توپولوژی فیزیکی در هنگام ورود گره – های جدید، میتواند مسافت پیموده شده توسط بسته های ترافیک میان گره ها و نیز تاخیر در ارسال آنها را کاهش دهد. علاوه بر این ، با در نظر گرفتن مکان فیزیکی گره ها در هنگام اضافه شدن گره ی جدید، میتوان با حداقل نمودن ترافیک میان گره ها، پهنای باند اشغال شده را به میزان قابل توجهی کاهش داد و بازده شبکه را بهبود بخشید. برای تفهیم بهتر این موضوع ، چهار گره A،B ،C و D که از طریق شبکه فیزیکی نشان داده شده در شکل (٢) به یکدیگر متصل شدهاند، را در نظر بگیرید.
اعداد روی لبه های متصل کننده، طول فیزیکی لینک ها را نشان می – دهند. شکل (٣) دو شبکه نظیربه نظیر متشکل از این چهار گره را نشان میدهد که ترتیب قرار گرفتن گره ها در شبکه فیزیکی و منطقی با یکدیگر متفاوت است (فرض کنید ارتباط فقط در جهت عقربه های ساعت امکان پذیر است ). اگر گره A بخواهد پیام m را به گره B بفرستد، در شبکه شکل (٣-الف )، پیام m ناچار است از مسیرA→C→B عبور کند. با نگاشت این مسیر منطقی به شبکه فیزیکی ، مسیر فیزیکی این پیام به صورت
A→R1→R2→C→R2→R1→B
و مسافت طی شده توسط پیام m برابر با
خواهد بود. حال اگر شبکه شکل (٣-ب ) را در نظر بگیریم ، مسیر پیام m به صورت A→B و مسیر فیزیکی نیز به صورت
A→R1→B
بوده و مسافت طی شده برابر با
DistB ۱x۱x ۲x
خواهد بود. بنابراین همانگونه که ملاحظه میشود، شبکه شکل (٣-ب ) همخوانی بیشتری با شبکه فیزیکی دارد[١٢].
شکل (٢): لایه فیزیکی که چهار گره A،B ،C و D را متصل میکند
این آگاهی از ساختار شبکه زیرین باعث میشود تا علاوه بر کاهش مسافت طی شده توسط پیام ، با بالا رفتن کارایی مسیریابی بین گره ها پهنای باند کمتری از شبکه اشغال شود.
٢-٣- کارهای مرتبط
با توجه به اینکه هدف اصلی پروتکل Chord، نگاشت کلید داده شده به یکی از گرههای حاضر در شبکه بوده و توپولوژی شبکه فیزیکی در طراحی آن مورد توجه قرار نگرفته است ، این پروتکل در مسیریابی درخواست های محتوی ، کارایی غیرقابل قبولی از خود نشان میدهد. به همین دلیل در سال های اخیر تلاش های قابل توجهی برای رفع این مشکل و آشناسازی این پروتکل با توپولوژی شبکه فیزیکی صورت گرفته است .
پروتکل PChord [۶]، سعی دارد با استفاده از مفهومی به نام لیست – های مجاورت ١٧، مجاورت فیزیکی گره های حاضر را در نظر بگیرد. لیست مجاورت یک گره ، اسامی گره هایی است که در فاصله جغرافیایی نزدیکی با آن گره قرار دارند و در مدت زمان حیات گره کشف میشوند. برای تعیین گره بعدی در هنگام مسیریابی یک کلید، علاوه بر در نظر گرفتن مدخل های جدول Finger_table، از مدخل های لیست مجاورت نیز استفاده میشود. به این ترتیب با جایگزین کردن برخی از مدخل های جدول Finger_table با مدخل های مناسبی از لیست مجاورت ، سعی میشود تا گره بعدی از میان گره های نزدیک تر انتخاب شده و کارایی مسیریابی افزایش یابد. اگر چه این روش کارایی بهتری در مسیریابی از خود نشان میدهد، مشکلاتی نظیر همگرایی کند و ناکارایی در هنگامی که طول عمر یک گره کم است ، کاربرد آن را محدود میکنند[۵].
یکی دیگر از کارهای انجام شده در این زمینه ، پروتکل Chord6 [٧]، است . در این پروتکل با استفاده از ساختار سلسله مراتبی آدرس های IPv6، شناسه هر گره به گونه ای تولید میشود که تمامی گره های موجود در یک دامنه ، شناسه های نزدیک به هم داشته باشند. به این ترتیب ساختار شبکه فیزیکی در شبکه نظیربه نظیر نیز منعکس میشود.
به دلیل تعدد دامنه های موجود در شبکه اینترنت و کم بودن میانگین تعداد گره های یک شبکه نظیربه نظیر که در یک دامنه فیزیکی قرار گرفته اند، به نظر میرسد این پروتکل دارای کارایی موثری نیست . علاوه بر این در ساختار کنونی شبکه اینترنت که مبتنی بر IPv4 است ، نمی – توان این پروتکل پیادهسازی کرد. پروتکل AChord [۵] یکی دیگر از پروتکل های پیشنهاد شده برای لحاظ کردن توپولوژی فیزیکی در ساختار پروتکل Chord است . در این anycast برای بهبود آگاهی از شبکه فیزیکی پروتکل ، از مکانیزم استفاده میشود. مکانیزم anycast یکی از روش های برقراری ارتباط در پروتکل IPv6 است که در آن یک آدرس مشترک به گروهی از گره ها تخصیص داده میشود. هنگامی که یک گره خارجی پیامی را به این گروه بفرستد، این پیام به گره ای تحویل داده میشود که نزدیک ترین فاصله فیزیکی را با فرستنده پیام دارد. در این پروتکل تمام گره های شبکه نظیربه نظیر، به عنوان یک گروه anycast در نظر گرفته میشوند و هر گره جدیدی که بخواهد به این شبکه بپیوندد، بر اساس مکانیزم
anycast به گره ای که در نزدیک ترین فاصله فیزیکی با آن گره قرار دارد متصل میشود و به این ترتیب توپولوژی شبکه فیزیکی در هنگام تشکیل شبکه رویین در نظر گرفته میشود. اگر هر بسته ارسال شده به یک گروه anycast واقعا به نزدیک ترین گره موجود در آن گروه برسد، مکانیزم anycast ایده آل خواهد بود. یکی از اشکالات پروتکل AChord، ایدهال در نظر گرفتن مکانیزم anycast در محیط واقعی است حال آنکه این حالت همواره برقرار نیست . علاوه بر این مسئله ، پروتکل AChordنیز همانند پروتکل Chord۶ مبتنی بر ساختار IPv۶ است و در ساختار فعلی اینترنت نمی تواند در سطح وسیع پیاده سازی شود.
٣- پروتکل پیشنهاد شده
در این بخش به شرح پروتکل پیشنهادی خود میپردازیم .
٣-١- کلیات
برای بهبود مسئله آگاهی از توپولوژی در پروتکل Chord، پروتکل TAC بر اساس شناسه گره ها، علاوه بر فضای مدور کلی یا حلقه عمومی که تمام گره ها در آن شرکت دارند، برای گره هایی که در ناحیه جغرافیایی یکسانی قرار دارند، یک فضای حلقه ای دیگر، به نام حلقه محلی در نظر میگیرد. هر گره جدید در هنگام پیوستن به شبکه روئین ، علاوه بر قرار گرفتن در حلقه عمومی و تشکیل جدول Finger_table، در حلقه محلی مربوط به ناحیه جغرافیایی خود نیز گنجانده شده و جدول دیگری به نام Zone_finger_table را با توجه به گره های حلقه محلی تشکیل میدهد. نحوه تشکیل این جدول کاملا مشابه با تشکیل جدول Finger_table است با این تفاوت که به جای در نظر گرفتن گره های حلقه عمومی، گره های حلقه محلی در نظر گرفته میشوند. هدف از تشکیل دادن جدول Zone_finger_table این است که هر گره با آگاهی از تمام گره هایی که در نزدیکی آن قرار دارند، مسیریابی موثرتری در هدایت درخواست های جستجوی کلید انجام دهد.
٣-٢- ناحیه های جغرافیایی
در پروتکل Chord، تمامی گره های شبکه از لحاظ مکان جغرافیایی در یک سطح قرار دارند. به عبارت دیگر محل قرار گرفتن فیزیکی گره ها در تشکیل شبکه روئین در نظر گرفته نمی شود. برای حل این مشکل ، در پروتکل TAC کل فضای جغرافیایی به نواحی کوچک تری به نام Zone تقسیم بندی شده اند. انتظار میرود که گره هایی که در یک Zone قرار دارند، با تاخیر کمتری میتوانند با یکدیگر ارتباط برقرار کنند. ایده کلیدی پروتکل TAC این است که اگر گره هایی که فاصله نزدیکی با یکدیگر دارند از وجود یکدیگر مطلع باشند، مسیریابی موثرتری در هنگام جستجوی کلید انجام میگیرد. با توجه به بزرگی جغرافیایی شبکه نظیربه نظیر، هر Zone میتواند معرف یک کشور، یک شهر و یا یک سازمان باشد. با فرض یکنواخت بودن پراکندگی جغرافیایی گره ها، دو مصالحه در تقسیم فضای جغرافیایی باید لحاظ شود: ١) هر چه اندازه یک ناحیه کوچکتر انتخاب شود تعداد گره کمتری را درخود جای خواهد داد ٢) هر چه اندازه یک ناحیه بزرگتر باشد، تاخیر ترافیکی بدترین حالت ١٨ بین گره های آن ناحیه بیشتر خواهد بود. با این وجود چگونگی تقسیم و اندازه هر یک از این نواحی به صورت دلخواه انجام میگیرد و میتواند تابع شرایط سیاسی ، کاربردی و ملاحظات دیگر باشد. در شکل (۴) یک نمونه از تقسیم جغرافیایی نمایش داده شده است . در این شکل ، کل فضای جغرافیایی (Global)، به چهار ناحیه کوچک تر (۴-١ Zone)تقسیم شده است . هر یک از دایره ها نماینده یک گره هستند و شناسه هر یک از آنها نیز مشخص گردیده است . فضای شناسه ها ٨بیتی است و گره هایی که در یک ناحیه قرار گرفته اند مشابه هم هاشور خوردهاند.

این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
word قابل ویرایش - قیمت 12700 تومان در 17 صفحه
127,000 ریال – خرید و دانلود
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد