چگونگی ارتباط گره های شبکه های P2P در Unstructured Overlay ها چاپ نامه الکترونیک
امتیاز کاربر: / 45
بدخوب 
مقالات - شبکه
نوشته شده توسط محمد مهدی حاجی اسمعیلی   
جمعه ۰۷ مرداد ۱۳۹۰ ساعت ۱۴:۰۰

وقتی گره ها، به هم گره میخورند !

(بررسی چگونگی ارتباط گره های شبکه های P2P در Unstructured Overlay ها)


این مقاله مربوط به درس "ارائه مطلب" دانشگاهم بود و از اونجاییکه استادم به لودگی و مسخره بازی نمره نمیده (!) نتونستم این مقاله رو هم به سبک نوشته های همیشگیم بنویسم برای همینم یه کمی (فقط یه کم !) خشک و دانشگاهی و با کلاس هستش ! از اوناییه که دوست داری باهاشون پز بدی، فقط مشکل اینه که من گاگول نمیدونم اصلا میشه با مقاله به کسی پز داد یا نه ! حالا مهم نیست ! خونتونو کثیف نکنین ! اگه موضوعش به دردتون خورد (که احتمالا نمیخوره !) بخونینش و اگه به درد هم نخورد اصلا به درک ! چرا وقتتون رو هدر بدین ؟! برین YouTube چهار تا فیلم ببینین حال کنین !

فقط یه پیشنهاد بدم : اگه میخواین مقاله هه رو بخونین، بهتره برین آخرش و سعی کنین که فایل PDF شده ش رو دانلود کنین... اینطوری متون راست به چپ و چپ به راست هم خراب نمیشه و تازه مقاله ش هم خوشگلتر میشه !

چکيده

شبکه های P2P مقوله ایی قدیمی و شناخته شده در صنعت ارتباطات و شبکه های کامپیوتری هستند. شبکه های P2P، شبکه هایی با انعطاف بسیار بالا، گستردگی عظیم و جمعیت ارتباطی قابل توجهی هستند. در صورتیکه بتوان از پتانسیل نهفته ی این شبکه ها در جهت ارضای نیازهای کاربران و حتی شرکتهای مختلف بهره برد، قدرتی عظیم در اشتراک منابع و محاسبات خواهیم داشت که این قدرت قابل رقابت با ساختارهای شناخته شده ی Client/Server و حتی فراتر از آنهاست. در واقع علت محبوبیت و علاقه ی بسیاری از کاربران این شبکه ها، به رشد و فزایندگی قدرت ارتباطی آن با افزایش کاربرانش برمیگردد. گسستگی و در عین حال پیوستگی ارتباطات این شبکه ها مدیون راهکارهای شناخت گره های آن با هم است. اهمیت این ارتباط به قدری است که اشتباهی بسیار کوچک در تبیین چگونگی آن، میتواند موجب عدم کارکرد درست شبکه و در نهایت از هم پاشیدن آن گردد. هدف ما در این مقاله بررسی راههای چگونگی ایجاد ارتباط و مسیریابی بین گره ها در شبکه های P2P است که در ابتدا با معرفی دو خانواده ی اصلی این شبکه ها شروع شده و در ادامه با مطرح کردن راهکارهای ارتباطی خانواده ی اول یعنی Unstructured Overlay ها و بحث بر سر مزایا و مشکلات آن، موضوع را مورد بررسی بیشتر قرار میدهیم.

واژه­ هاي كليدي

شبکه های P2P، Network Overlay، Distributed Hash Table، Query Routing، Key-Based Routing،Random Graphs، Power-Law Graphs

 

1- مقدمه

منطق اصلی شبکه های P2P بر گسترده بودن و عدم تکیه ی گره های آن به سرورهای مرکزی است. در این مقاله معنای سرور کمی متفاوت از معنای همیشگی آن است چرا که در هر ارتباطی یک سیستم تبدیل به Client و سیستم دیگر تبدیل به یک Server میشود و با تکیه بر این توضیح نمیتوان هیچ سیستمی تعریف کرد که کاملا بدون Server باشد. ولی در مقوله ی شبکه های P2P معنای سرور، سیستمی مرکزی است که تمامی ارتباطات بین اعضا به آن تکیه دارد و در صورت حذف آن، ارتباطات بین گره ها با مشکلات جدی روبرو خواهد شد.

موضوع دیگری که باید به آن اشاره کرد، کلمه ی Overlay است. برای ایجاد تفاوت بین کارکرد لایه ی هفتمی پروتکل P2P و دیگر لایه های زیرین آن، از کلمه ی Overlay استفاده میشود که اشاره به سیستمهایی دارد که از دید لایه ی هفتم شبکه به یکدیگر متصل هستند. شکل-1 تفاوت بین ارتباطات فیزیکی و لایه هفتمی سیستمهای درون یک شبکه را نشان میدهد.

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


ساختار P2P Overlay در جزئیات بیشتر

شکل-1 : تصویر بالایی مربوط به Overlay ارتباطی لایه هفتمی یک شبکه P2P است در حالیکه تصویر پایینی مربوط به زیرساختهای ارتباطی همان شبکه بدون هیچگونه Abstraction است.

با توجه به این تعریف، شبکه های P2P به دو نوع اصلی تقسیم میشوند :

  1. UnStructured Overlays
  2. Structured Overlays

Unstructured Overlay ها شبکه هایی هستند که در آنها راهکار دقیقی برای دسترسی به نودهای دیگر، درخواست منبع و دریافت آن وجود ندارد. در این Overlay، سیستمها به کمک ساختارهای بر مبنای Broadcast و یا راهکارهای شانسی اقدام به پیدا کردن دیگر گره های درون شبکه میکنند و هیچ ضمانتی برای پیدا کردن منبع مورد نظر یک گره (در صورتیکه این منبع درون شبکه وجود داشته باشد) وجود ندارد. همچنین، آدرس دهی سیستمها و دسترسی کامل هر گره به گره ایی دیگر نیز تضمین شده نیست و ممکن است حتی با وجود حضور گره ی مورد نظر ما در شبکه، قادر به دسترسی و یا پیدا کردن آن نباشیم.

در پاسخ به محدودیتهای Unstructured Overlay ها، Structured Overlay ها به وجود آمدند که اقدام به برطرف کردن محدودیتهای آدرس دهی گره ها و منابع به کمک ادغام ساختارهای جغرافیایی با راهکارهای مسیریابی و نگهداری، نمودند. با توجه به گستردگی مطالب مربوط به هر دو Overlay، تلاش این مقاله در جهت شناخت و پیاده سازی راهکارهای بهینه برای UnStructured Overlay ها متمرکز شده است.

2- ارتباط در Unstructured Overlays

فرض گیریم که هر گره، لیستی از گره هایی دیگری که در یک شبکه به آن متصل است را نگه میدارد. به گره هایی که به صورت مستقیم به گره ی فوق متصل هستند، "همسایه" های این گره میگوییم و به تعداد این همسایه ها، "درجه" ی این گره میگوییم. در یک Overlay هر چقدر که درجه ی یک گره افزایش یابد، موجب کاهش اندازه ی ماکزیمم مسیری میشود که از یک گره به گره های دیگر به وجود می آید (شعاع Overlay) ولی در عین حال باعث افزایش فضای ذخیره سازی در هر گره میشود.

موضوع اصلی قابل توجه در Unstructured Overlay ها این حقیقت است که یک گره با اتصال به Overlay هیچ اطلاع خاصی از نحوه ی شکل گیری شبکه و مکان قرارگیری فایلها ندارد. این وضعیت درست مثل غریبه ایی است که به تازگی وارد یک مهمانی شده و به غیر از افرادی که در نزدیکش ایستاده اند، راهی برای شناختن دیگران و شروع ارتباط با آنها ندارد.

با توجه به این محدودیت مهم دو راهکار برای ارسال درخواستها از یک گره به دیگر گره ها وجود دارد : Flooding و Random Walk

2-1 راهکار Flooding یا غرق کردن

وقتیکه یک گره به Overlay متصل میشود، میتواند با همسایه هایش اقدام به رد و بدل پیام کند. نوع خاصی از این پیامها میتواند درخواست یک منبع مثل یک فایل باشد. از آنجاییکه ما نمیدانیم این منبع در کجا قرار دارد، میتوانیم درخواستمان را به تمامی همسایه هایمان ارسال کنیم و در صورتیکه این همسایه ها نیز ندانند که منبع کجاست، آنها نیز اقدام به فرستادن درخواست به همسایه هایشان میکنند و روند فوق همچنان ادامه پیدا میکند. به این راهکار Flooding و یا غرق کردن شبکه در پیامهای درخواست میگویند.

برای جلوگیری از مشکلاتی مثل ایجاد حلقه و همچنین کنترل ترافیک (تا شبکه خفه نشود) راهکارهایی اتخاذ میکنیم : برای پیامهایی که دوباره به خودمان برمیگردد و یا دو بار از مکانی رد میشود، هر گره میتواند لیستی از پیامهایی که قبلا گرفته و سپس ارسال کرده را نگه دارد و در صورتیکه این پیام را دوباره دریافت کرد، آنرا دور بیندازد. از طرفی برای جلوگیری از اینکه هر گره مجبور به نگهداری حجم عظیمی از پیامها شود، اقدام به در نظر گرفتن Time-To-Live برای هر پیام میکنیم بدین ترتیب که هر گاه پیام درخواستی از طرف یک گره ارسال شد، خود درخواست کننده برای آن عددی را برای TTL در نظر بگیرد و با هر بار گذشتن پیام از یک گره، یکی از مقدار TTL کم میشود.

در طراحی این ساختار برای پیامها باید این موضوع را در نظر بگیریم که مقدار TTL باید همنوا با شعاع شبکه باشد چرا که در صورتیکه این عدد متناسب با شعاع نباشد، ممکن است که پیام ما هیچگاه بیش از مقداری مشخص در شبکه پخش نشود و در صورتیکه منبع مورد نظرمان دور از ما باشد، آنگاه شاید هیچوقت نتوانیم آنرا دریافت کنیم.

شکل-2 Overlayیی را نشان میدهد که یک درخواست با TTL برابر 4 درون آن ارسال شده است.


الگوریتم Flooding با 4 پرش

شکل-2 : یک پیام با TTL برابر 4 از گره ی اول به سه گره ی همسایه اش فرستاده میشود و پس از اتمام TTL در گره های نهایی متوقف میشود. توجه شود که پیام کل Overlay را طی نکرد.

این راهکار ساده به نام Flooding شناخته میشود و در الگوریتم زیر چگونگی کارکرد آن نشان داده شده است :

FloodForward(Query q, Source p)

// have we seen this query before?

If (q.id ϵ oldIdsQ) return // yes, drop it

oldIdsQ = oldIdsQ υ q.id // remember this query

// expiration time reached?

q.TTL = q.TTL – 1

if q.TTL <= 0 then return // yes, drop it

// no, forward it to remaining neighbors

foreach(s Є Neighbors) if(s ≠p) send(s,q)

همانطور که اشاره شد، هر گره دارای لیستی از همسایه ها است. گره میتواند با وصل شدن به Overlay اقدام به بروزرسانی لیست همسایه هایش کند، مثلا میتواند با گرفتن کپی لیست اولین نود همسایه اش، سریعا نودهای دیگر متصل به همسایه را شناسایی کند و یا اینکه وقتی یک پیام درخواست به آن ارسال میشود، آدرس گره ی فرستنده را سریعا درون لیستش ثبت کند و بدین ترتیب لیست همسایه هایش را گسترش دهد. در مواقعی نیز که پاسخ پیامهای گره توسط همسایه ها جواب داده نمیشود میتواند همسایه اش را قطع از شبکه قلمداد کرده و آنرا از لیستش حذف کند.

وقتی که پیام درخواستی در گره ایی جواب میدهد، جواب آن پیام به فرستنده ی اصلی برمیگردد. حالا فرض کنید که پیام در یک گره جواب داده شده است ولی پیامهای دیگری که از گره های دیگر ارسال شده اند همچنان در حال پخش شدن در Overlay هستند. در این سناریو با اینکه جواب به دست ما رسیده است ولی هنوز درخواست ما که از گره های دیگر پخش شده اند، در شبکه هستند و تبدیل به پیامهای اضافه ایی شده اند که کارایی شبکه را تقلیل میدهند. برای درست کردن چنین مشکلی میتوانیم در ابتدا با فرستادن پیامی که TTL آن عدد کمی است شعاع کوچکی از گره های اطرافمان را مورد بررسی قرار دهیم و اگر جواب در همان دفعه ی اول برگشت، کار را تمام میکنیم ولی اگر جواب برنگشت، اقدام به فرستادن پیام درخواستی با TTL یی بالاتر از قبل میکنیم و اینکار را اینقدر ادامه میدهیم تا به شعاع کل Overlay نزدیک شویم.

این شاخه از Flooding با نام Iterative Deepening (عمیق شدن مرحله به مرحله) و یا Expanding Ring (حلقه ی در حال رشد) شناخته میشود. شبه کد مربوط به فرستادن درخواست به کمک راهکار Expanding Ring و همچنین دریافت درخواست و جواب دادن به آن در جدول-1 نمایش داده شده است.


فرستنده

گیرنده

ExpandingRingForward(Query q, Source p)

// is it an expansion of a previous query?

if(q.expansion = false)

{

// no, have we seen this query before?

if(q.id ϵ oldIdsQ) return // yes,

drop it

}

// remember this query

oldIdsQ = oldIsQ U q.id

// expiration time reached?

q.TTL = q.TTL – 1

if q.TTL <=0 then return // yes, drop it

// no, forward it to remaining neighbors

foreach(s ϵ Neighbors) if(s ≠ p) send(s,q)

ExpandingRingRequest(SearchTerm st)

q.st = st

q.TTL = minTTL // first try a small TTL

// send search request to neighbors

foreach(s ϵ Neighbors) send(s,q)

// wakeup and do a retry if request fails

lastTTL = minTTL

setTimer(ERRequestRetry,100)

ERRequestRetry()

// have we exceeded the permitted TTL?

// if so, then stop

if (lastTTL > maxTTL) return

// no, increase TTL and try again

lastTTL = lastTTL þ 1

// send it to neighbors

foreach(s ϵ Neighbors) send(s,q)

// wakeup and do a retry if request fails

setTimer(ERRequestRetry,100*(lastTTL-minTTL))

جدول-1 : شبه کد مربوط به الگوریتم Expanding Ring

راهکار فرعی دیگری که میتوان استفاده کرد، کنترل Replication و پخش شدگی اشیاء و منابع در Overlay است بطوریکه بتوانیم شانس پیدا کردن هر شیئ در Overlay را با درست قرار دادن و پخش کردن آن بیشتر کنیم که در ادامه به این راهکارها میپردازیم.

2-2 راهکار Random Walk

راهکار Flooding با وجود کاراییش دارای مشکل اساسی خفه کردن شبکه بود بطوریکه اگر میزان TTL به خوبی مشخص نشود و همچنین ساختارهای جلوگیری از ایجاد حلقه در آن به خوبی مشخص نشود باعث اعمال فشار بسیار زیادی بر روی گره های شبکه خواهد شد به طوریکه با افزایش تعداد گره ها، این الگوریتم بیش از پیش سنگینتر و پر هزینه تر خواهد شد.

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

برای بهتر کردن زمان پاسخ میتوانیم در یک آن چندین درخواست را به صورت Random Walk بر روی Overlay ارسال کنیم. در شکل-3 دو تصویر میبینیم که به تشریح چگونگی Random Walk میپردازند :


راهکار Random Walk برای شبکه های P2P

شکل-3 : (A) در اینحالت یک پیام درخواست به صورت Random Walk و با TTL برابر 7 بر روی Overlay ارسال شده است. (B) در اینحالت 3 پیام درخواست Random Walk بر روی Overlay به صورت همزمان ارسال شده اند.

شبه کد ساده شده ی Random Walk در زیر آمده است :


RandomWalk(source, query, TTL)

if (TTL > 0)

{

TTL = TTL – 1

// select next hop at random, don’t send back to source

while( (next_hop = neighbors[random()]) == source )

send(source, query,TTL)

}

2-3 اصلاح کردن Flooding و Random Walk

هر دو راهکار Flooding و Random Walk دارای محدودیاتی هستند : Flooding قابل استفاده برای شبکه های بزرگ نیست و موجب ناکارآمدی شبکه خواهد شد و از طرفی استفاده از Random Walk برای پیدا کردن یک منبع ممکن است زمان زیادی ببرد.

در ساختارهای Unstructured به غیر از الگوریتم و راهکارهای ارسال، دیگر از چه چیزهایی میتوان برای بهینه کردن ساختار Overlay کمک گرفت ؟!

توپولوژی Overlay، مکانهای قرارگیری اشیاء، Cache کردن اطلاعات و مبحث ارسال درخواستها ، مقوله هایی هستند که هنوز جای کار دارند و در این قسمت به آنها میپردازیم.

در یک Unstructured Overlay، هر گره کنترل قابل توجهی بر روی درخواستهای ارسالی از دیگران و درخواستهای خروجی از خود دارد. این گره میتواند از بین گره های همسایه، هر کدام را که ترجیح میدهد را انتخاب کرده و پیامش را ارسال کند و موضوع مهم در اینجا، این است که فاکتورهای بسیاری میتوانند این انتخاب را تحت تاثیر قرار داده و بهتر (یا بدتر) کنند. از بین این فاکتورها، میتوان به مواردی مثل گنجایش گره ی بعدی، نوع منبعی که در گره ی بعدی به اشتراک گذاشته شده است و همچنین چگونگی متصل ماندن گره ی بعدی به شبکه اشاره کرد.

مورد بعدی که میتوان به آن اشاره کرد مقوله ی Clustering گره ها است. Clustering یا "خوشه سازی" در یک شبکه وقتی به وجود می آید که احتمال اتصال دو گره به کمک یک همسایه در قسمتی از توپولوژی بالا رود بطوریکه بعد از گذشت مدت زمانی متوجه اتصال تعداد زیادی گره به هم در یک شعاع کوچک بشویم که تمام این گره ها غالبا با یک و یا دو پرش به یکدیگر متصل شده اند.

Topology Cluster ها را میتوان بر اساس فاصله ی جغرافیایی گره ها و یا مشخصه های یکسان آنها در منابع اشتراکیشان بوجود آورد. Object Cluster ها را نیز میتوان بر اساس نزدیک بودن شناسه ی اشیائی که چندین گره به اشتراک گذاشته اند و درون یک Identifier Space قرار میگرند، تشکیل داد. مثلا وجود یک خوشه سبب این میشود که وقتی درخواستی برای شیئی خاص به خوشه میرسد، میتوان درخواست را به قسمتی از خوشه فرستاد که میدانیم شانس پیدا کردن فایل در آن بیشتر است چرا که شناسه ی فایل مورد نظر نزدیکی قابل توجهی به شناسه ی یک سری از گره های آن خوشه دارد.

Object Placement نیز مقوله ایی قابل توجه است و بدین معناست که مکان قرارگیری یک شیئی را درون Overlay طوری انتخاب کنیم که شانس بیشتری برای پیدا کردن آن باشد. فاکتورهایی که Object Placement را تحت تاثیر قرار میدهند میتوانند محبوبیت و معروفیت فایل و همچنین چگونگی مسیریابی درخواستها باشند. بعنوان مثال پخش کردن یک فایل درون شبکه و Replicate کردن آن بین گره های مختلف موجب پایین آمدن فشار جستجو و همچنین زمان پیدا کردن آن فایل درون Overlay میشود. از این منظر میتوان گفت که Object Placement را میتوان با فرستادن زوری فایلها به دیگر گره ها (برای Replication) و همچنین Cache کردن جواب درخواستهای قبلی بر روی هر گره پیاده سازی نمود.

مسئله ی دیگری که میتوان به آن اشاره کرد، بهتر کردن الگوریتم Forwarding مربوط به Random Walk است. میدانیم که Random Walk به صورت شانسی اقدام به انتخاب همسایه هایش برای ارسال درخواستها میکند. یک گره میتواند با درخواست اطلاعات همسایه هایش از جمله منابع اشتراکی آن همسایه، از شرایط آن مطلع شود. این اطلاعات Cache شده و در بازه های معینی به روز میشوند و میتوانند برای انتخاب بهتری بین همسایه های یک گره به کار روند.

با تمام این اوصاف، یادمان نرود که دو الگوریتم Flooding و Random Walk به خاطر سادگی و صد البته سرعت بالایشان در پردازش درخواستها، تبدیل به راهکارهای اصلی Unstructured Overlay ها شده اند. با افزایش عناصر کمکی در شناخت هر چه بهتر Overlay توسط گره ها، ما در واقع داریم احتمال کند شدن ارسالها و دریافتها را افزایش میدهیم. برای سنجش بهینگی هر راهکاری که در بالا ارائه دادیم، نیاز به شاخصی داریم. این شاخص باید بتواند نشان دهد که هر راهکار استفاده شده توسط ما، چقدر زمان میانگین برای یافتن یک منبع را افزایش یا کاهش داده است. در قسمت بعد به این موضوع میپردازیم.

2-4 شاخص و یا Metric برای راهکارهای ارتباطی

هنگامیکه یک پیام درخواست بین دو گره در حال ارسال است، در واقع یک پیام در لایه ی شبکه در حال انتقال بین این دو گره است. به هر پرش پیام از یک گره به گره ی دیگر یک Overlay Hop و یا همان Hop میگوییم. ممکن است در یک Hop ساده بین دو گره، عملا پیام فوق چند بار در لایه ی شبکه از مسیریابهای متعددی گذر کند. هر چقدر که تعداد Hop ها برای پیدا کردن یک منبع افزایش یابد، عملا زمان پاسخ دهی به درخواست اولیه طولانیتر خواهد شد.

برای محاسبه ی شاخص عملکردی، دو راهکار با نامهای Hops Per Request (پرش برای هر درخواست) و Hops Per Successful Request (پرش برای هر درخواست موفق) در نظر میگیریم. HPR به تعداد درخواستهایی گفته میشود که برای یک پیام به طور کلی بر روی Overlay ارسال میشود. HPSR به تعداد جوابهای موفقی گفته میشود که در پاسخ به درخواستها داده شده است. این دو فاکتور به سوال مهمی پاسخ میدهند : "اگر میتوان یک شیئ را پیدا کرد، دقیقا چقدر طول کشیده تا آنرا پیدا کنیم ؟!"

از طرفی بالا بردن جوابهای موفق نیز یکی از اهداف ما در طراحی Overlay هاست. با در نظر گرفتن اینکه ساختار ارسال پیامهای درخواست همیشه یکسان هستند، میتوان مبحث دیگری را بنام Request Hit Rate تعریف کرد که در واقع تعداد درخواستهای موفق تقسیم بر تعداد کل درخواستهاست. در یک جامعه ی آماری با حد ارسال پیام مشخص و منابع مشخص هر گره، هر چقدر Request Hit Rate بالاتر باشد، میزان رضایت کاربران افزایش خواهد یافت.

فاکتورهای ارائه شده در بالا، به هنگام شبیه سازی آماری Overlay ها برای سنجش قدرت و بهینگی کارکرد الگوریتمهای مختلف به کار میروند.

3- انواع Unstructured Graph

همانطور که قبلا هم نشان دادیم، یک Overlay میتواند به عنوان یک گراف در نظر گرفته شود. بطور کل اعمالی که گره ها برای پیدا کردن و ارزش گذاری همسایه هایشان در یک Overlay انجام میدهند، تبدیل به شاخصه های مهمی از این گراف خواهند شد. این شاخصه ها میتوانند شامل چگونگی توزیع درجه ی هر گره در گراف (که بر روی توزیع بار تاثیر دارد) و شعاع یک گراف (که بر روی تعداد Hop ها در مسیریابی پیغام درخواستی تاثیر دارد) باشند.

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

در این قسمت اقدام به معرفی مختصری در مورد چگونگی کارکرد این مدلها میکنیم و در صورتیکه نیاز بیشتری به بررسی این موضوع توسط خوانندگان بود، شما را به [1] برای تسلط بیشتر در مطلب هدایت میکنیم.

3-1 گرافهای Random

یک گراف Random یا شانسی هنگامی ایجاد میشود که بین گره های آن به صورت شانسی اقدام به ایجاد یال نماییم. Gn,p گروهی از گرافهای شانسی است که در آنها p احتمال وجود یک یال بین یک گره و هر گره ی مستقل دیگر و 1-p احتمال نبودن یک یال بین گره و دیگر گره های مستقل است. از آنجاییکه تعداد یالها در این گراف برابر n(n-1)*p/2 است، میانگین درجه ی هر نود در این گراف تقریبا برابر np خواهد بود.

با اینکه گرافهای شانسی به خاطر مزیتهای آماریشان بسیار مهم شناخته میشوند ولی در دو مشخصه با اتفاقات دنیای واقعی متفاوت هستند :

اولین شاخصه وجود خوشه ها در شبکه های واقعی است. خوشه سازی یا Clustering مشخصه ایی از شبکه است که در آن احتمال اتصال دو گره به هم در صورتیکه یک همسایه ی مشترک داشته باشند، بیشتر است. این مقدار به کمک ضریب خوشه سازی یا Clustering Coefficient قابل محاسبه است. ضریب خوشه سازی احتمال خوشه شدن گره ها با توجه به تعداد تمامی گره های متصل به هم در شبکه است. بعنوان مثال در گرافهای شانسی، یالها بصورت کاملا مستقل بین گره ها به وجود می آیند پس مقدار ضریب خوشه سازی برابر p خواهد شد که احتمال انتخاب یک یال بین دو گره است. در بسیاری از شبکه های واقعی، مقدار خوشه سازی از چندین درصد تا نزدیک به 50 درصد متغیر است.[2]

دومین شاخصه این است که اکثر شبکه های واقعی از ساختار تابع "قانون توانی" یا Power-Law پیروی میکنند. این جمله بدین معنی است که جمع بسیار کوچکی از گره ها دارای درجه ی بسیار زیادی هستند. شکل 4 نشان دهنده ی توزیع درجه ی گره ها در یک گراف شانسی و در یک گراف Power-Law است.

توزیع مربوط به گراف شانسی دارای توزیع پواسون در میانه ی k = <k> است و با بزرگتر شدن مقادیر k به صورت نمایی نزول میکند. توزیع گراف Power-Law قله ایی ندارد و براساس قانون توانی کاهش میابد. به این شبکه ها، شبکه های Scale-Free نیز میگویند که این اسم توسط Barbasi & Albert اولین بار مورد استفاده قرار گرفت. Scale-Free به رفتار توابعی گفته میشود که حالت f (ax) = g (a) f(x) را ارضا میکنند و این حالت بدین معنی است که افزایش بزرگی x موجب افزایش تراکم f(x) نمیشود. [3]

مزیت گرافهای Scale-Free برای شبکه های P2P در این است که با افزایش تعداد کاربران و گره های این شبکه ها، شعاع کل Overlay به خاطر خوشه سازی همچنان کوچک باقی خواهد ماند که این امر به لطف وجود گره های کمی با درجه ی بسیار بالا در Overlay است.


توزیع درجه برای گره ها در Power Law و Random Graphs

شکل-4 : توزیع درجه برای گره ها در (A) Random Graph و (B) Power-Law Graph

این مشخصه میتواند مزیت بزرگی برای محدود کردن تعداد Hop ها در ارسال و در یافت پیامها در Unstructured Overlay ها باشد البته به شرط آنکه بتوان آنرا در ساختارهای مسیریابی شبکه پیاده سازی نمود. شکل-5 اقدام به مقایسه ی دسترسی در گرافهای شانسی و گرافهای Power-Law کرده است که در هر دوی آنها تعداد گره ها و تعداد یالها ثابت و مساوی است. گره های با درجه ی بالا در گراف Power-Law عملا تبدیل به درگاهی به قسمتهای دیگر و بزرگترOverlay شده است که گره های دیگر میتوانند به کمک آن به این قسمتها متصل شوند. پنج درگاه بزرگ گراف شانسی فقط به 27% گراف متصل هستند در حالیکه پنج درگاه بزرگ گراف Power-Law به 60% گراف متصل هستند.


Power Law گرافگراف شاانسی

شکل-5 : (A) گراف شانسی (B) گراف Power-Law

3-1 گرافهای Power-Law Random

با توجه به مزایای گرافهای Scale-Free این سوال پیش می آید که چطور میتوان Overlay را طوری طراحی کرد که توزیع درجه ی گره هایش پیرو Power-Law باشد. Barbasi, Albert و Jeong [4] دریافتند که دو شاخصه ی شبکه های واقعی موجب شکل گیری گرافهای Power-Law میشود : اولی این است که اکثر شبکه ها در طول زمان با وصل شدن به دیگر گره های شبکه، شروع به رشد میکنند و دومی اینکه گره های جدید تمایل دارند با گره های درجه بالای درون Overlay همسایه شوند. البته با وجود دو فاکتور فوق، باید اشاره کرد که هنوز هم توضیحات دیگری برای اینکه یک گراف Power-Law چطور بوجود می آید، وجود دارد.

Adamic et al [5] دو استراتژی را در مقوله ی جستجو درون گرافهای Power-Law پیاده سازی کرد که در آن الگوریتم Random Walk را با حالتی که در آن گره ها پیغامهای درخواست را به گره های با درجه ی بالا میفرستادند، مقایسه کرد. مشخص شد که فرستادن پیام به گره های درجه بالا هم از نظر زمان جستجو و هم از نظر پوشش Overlay برتری قابل توجهی نسبت به Random Walk دارد. به شکلهای 6 و 7 توجه کنید.


شکل-6 : تفاوت بین Random Walk (RW) و High-Degree Seeking (DS) در حالت "جستجوی گره به گره"

شکل-7 : تفاوت بین Random Walk (RW) و High-Degree Seeking (DS) در حالت "زمان پوشش نصف شبکه"

نتیجه گیری

در این مقاله به بررسی راهکارهای مختلف برای ارسال پیغامهای درخواستی در Unstructured Overlay ها و همچنین چگونگی بهینه کردن این راهکارها پرداختیم. در نهایت متوجه شدیم که رویکرد ایجاد گرافهای Scale-free بهمراه تمایل به بهینه سازی راهکارهای جستجوی بین گره ها، موجب نزدیک شدن طراحی Overlay های آینده به بهینگی بیشتر خواهد شد.

 

مراجع

[1] Y. Chawathe, S. Ratnasamy, L. Breslau, S. Shenker, and N. Lanham, GIA: Making Gnutella like P2P systems scalable, ACM SIGCOMM 2003.

[2] B. Bolloba´s and O. Riordan, Mathematical results on scale-free randomgraphs, in: S. Bornholdt,H. G. Schuster (eds.), Handbook of Graphs and Networks, Wiley-VCH, 2003, 1–34.

[3] L. Li, D. Alderson, R. Tanaka, J. C. Doyle, W. Willinger, Towards a theory of scale-free graphs: definition, properties, and implications (extended version), Internet Mathematica,2005.

[4] A.-L. Baraba´si, R. Albert, and H. Jeong, Scale-free characteristics of random networks: the topology of the World Wide Web, Physica A 281, 2000.

[5] L. A. Adamic, B. Humberman, R. Lukose, and A. Puniyani, Search in power-law networks, Phys. Rev. E, Vol. 64, 2001, 46135–46143.

[6] Y. Qiao and F. E. Bustamante, Structured and unstructured overlays under the microscope: a measurement-based view of two P2P systems that people use, in: Proceedings of the Annual Technical Conference on Usenix ’06 Annual Technical Conference (Boston, MA, May 30–June 3, 2006), USENIX Association, Berkeley, CA, 2006, 31–31.

[7] M. Castro, M. Costa, and A. Rowstron, Debunking some myths about structured and unstructured overlays, Proc. of the 2nd Symposium on Networked Sys. Design and Impl.(NSDI) 2005.

8] C. Xie, S. Guo, R. Rejaie, and Y. Pan, Examining Graph properties of unstructured peer-to peer overlay topology, Global Internet Symposium, 2007.

برای دانلود مقاله ی "Unstructured Overlay ها در شبکه های P2P" بصورت نسخه PDF بر روی این لینک کلیک کنید.

 

نظرات  

 
0 #4 الهام ۱۳۹۳-۰۹-۱۶ ۱۹:۳۲
خیلی خیلی ممنون ،خیلی خوشحالم که این مقالتونو خوندم واقعا به کارم اومد :-)
نقل قول
 
 
0 #3 مهدي ۱۳۹۱-۰۲-۲۰ ۱۱:۲۵
اي كاش لينك وب پيج مقاله تو pdf هم بود بازم ممنون
نقل قول
 
 
0 #2 مهدي ۱۳۹۱-۰۲-۲۰ ۱۱:۲۴
اين آرم p2p اول مقاله خيلي قشنگه كه مشابهش رو در pppoe و ddns گذاشته بودي ول ياي كاش تو pdf اش هم مي زاشتي اين آرم رو
نقل قول
 
 
+3 #1 پیمان ۱۳۹۰-۰۸-۰۱ ۰۹:۵۳
خیلی خوب بود، بواقعا نیاز داشتم ممنون
نقل قول
 

ارسال نظر


کد امنیتی
بروزرسانی

مقالات سر راهی !

همه چیز درباره ی EFS یا Encrypting File System

تا حالا شده از اون فایلا داشته باشین که نمیخواستین کسی بتونه بازش کنه ؟ مثلا از اون فایلایی که روی Flash RAM تون هست و همه جا با خودتون میبرینش ولی نمیخواین سیستمی غیر از سیستم خودتون بتونه باز و اجراش کنه ؟ یا اینکه یه شبکه دارین و شک دارین که یکی داره توش اطلاعاتی که نباید بخونه رو میخونه و شما میخواین فایله رو طوری رمز کنین تا خودش که هیچی، باباش هم نتونه فایله رو باز کنه !

دوران ویندوزهای 95 و 98 وقتی بود که اگه نمیخواستی فایلات رو Hidden کنی باید با بدبختی سراغ نرم افزارهای قفل گذاری کوفتی میرفتی ! هیچوقت یادم نمیره که یه بار یکی از عزیزترین فایلهام رو بدون اینکه ازش Backup بگیرم بهش سپردم و... و... و...

همه چیز درباره ی EFS یا Encrypting File System

تبلیغات تصویری

آگهی
آگهی