بخشی از مقاله
چکيده : سيستم هاي نظيربه نظير١، شبکه هايي منطقي از گره هاي خودمختار هستند که بار سيستم به صورت عادلانه ميان اين گره ها توزيع شده است و هر گره هم به عنوان سرويس دهنده و هم به عنوان سرويس گيرنده عمل ميکند. براي پيادهسازي اين سيستم ها، پروتکل Chord با داشتن ويژگي هايي نظير سادگي ، تعداد پيمايش محدود و متناسب با لگاريتم تعداد گره ها در هنگام جستجوي کليد، مقياس - پذيري بالا و انعطافپذيري در ورود و خروج گره ها از شبکه ، از عموميت بالايي برخوردار است . علي رغم برخورداري از اين قابليت ها، اين الگوريتم به دليل در نظر نگرفتن توپولوژي شبکه فيزيکي در هنگام ورود گره هاي جديد به سيستم ، کارايي ضعيفي در مسيريابي ميان گره ها نشان مي - دهد. در اين مقاله ، بر اساس پروتکل Chord، پروتکل جديدي به نام TAC2 معرفي ميکنيم . اين پروتکل ميکوشد تا با معرفي مفهوم حلقه محلي و نيز در نظر گرفتن ناحيه جغرافيايي گره هاي جديد وارد شونده به سيستم ، هر گره را به حلقه محلي متناظر با ناحيه جغرافيايي آن پيوند دهد. به اين ترتيب ، توپولوژي شبکه فيزيکي در ساختار شبکه منطقي رويين ٣ انعکاس داده ميشود. نتايج شبيه سازي نشان ميدهد که در مقايسه با پروتکل Chord، پروتکل پيشنهادي ما کارايي بهتري در مسيريابي ارائه کرده و متوسط مسافت طي شده بسته هاي ترافيک جستجوي کليد را به ميزان قابل توجهي کاهش ميدهد.
کلمات کليدي : شبکه هاي نظيربه نظير، آگاهي از توپولوژي ، جدول هش توزيع شده ، کارايي مسيريابي
١- مقدمه
يک شبکه نظيربه نظير (PP٢)، سيستم توزيع شدهاي است که به طور عادي فاقد ساختار سلسله مراتبي و سيستم کنترل مرکزي ميباشد. اين شبکه ، يک شبکه منطقي روئين است که بر روي لايه فيزيکي قرار دارد. هر يک از گره هاي اين شبکه ميتواند از طريق اين لايه فيزيکي و تنها با استفاده از گره هاي مجاور خود، با گره هاي ديگر اتصال برقرار کند. هر يک از اين گره ها که تحت عنوان يک نظير٤ نيز شناخته مي شود، به صورت خودمختار عمل ميکند. اطلاعاتي که در اين سيستم وجود دارد، به صورت تقريبا يکنواخت ميان تمام گره هاي موجود در شبکه توزيع شده است و هيچ گره اي نسبت به گره هاي ديگر ارجحيت ندارد. بنابراين بر خلاف مدل سرويس دهنده–مشتري ، در شبکه هاي نظيربه نظير هر گره ميتواند هم به عنوان سرويس دهنده و هم به عنوان مشتري عمل کند.
شبکه هاي نظيربه نظير به طور کلي به دو دسته شبکه هاي ساختاريافته 5 و شبکه هاي غير ساختاريافته ٦ تقسيم مي شوند. در شبکه هاي ساختاريافته هر آيتم اطلاعات در گره ي معيني نگهداري ميشود اما در شبکه هاي غير ساختاريافته ، اين آيتم ها به صورت تصادفي و نامشخص بين گره ها پخش شده اند[٤]. مهمترين برتري شبکه هاي ساختاريافته نسبت به شبکه هاي غير ساختاريافته ، مقياس پذيري بالاي اين شبکه ها است . براي پيادهسازي اين شبکه ها، دو مکانيزم اصلي بايد وجود داشته باشند: (١) محول کردن هر يک از آيتم هاي محتوي به يکي از گره ها (٢)جستجوي ٧ گره ي دربرگيرنده آيتم خواسته شده و بازيابي محتوي آن با توجه به کليد آن آيتم . در شبکه هاي ساختار يافته مبتني بر جدول هش توزيع شده 8(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 1x1x 2x
خواهد بود. بنابراين همانگونه که ملاحظه ميشود، شبکه شکل (٣-ب ) همخواني بيشتري با شبکه فيزيکي دارد[١٢].
شکل (٢): لايه فيزيکي که چهار گره 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)تقسيم شده است . هر يک از دايره ها نماينده يک گره هستند و شناسه هر يک از آنها نيز مشخص گرديده است . فضاي شناسه ها ٨بيتي است و گره هايي که در يک ناحيه قرار گرفته اند مشابه هم هاشور خوردهاند.
