کادملیا

اولین شبکه های همتا به همتای به اشتراک گذاری فایل ها ، مانند نپستر Napster ، برای ایجاد هماهنگ سازی مراجعات در شبکه به یک پایگاه داده مرکزی متکی بودند. شبکه های همتا به همتای نسل دوم ، مانند ناتلا Gnutella ، برای یافتن پرونده ها از فلودینگ استفاده می کردند و هر گره را در شبکه جستجو می کردند. شبکه های همتا به همتا نسل سوم از جداول هش توزیع شده برای جستجوی فایل ها در شبکه استفاده می کنند. جداول هش توزیع شده ، مکان منابع در سراسر شبکه را ذخیره می کنند. معیار اصلی این پروتکل ها مکان یابی سریع گره های مورد نظر است.

کادملیا از یک روش محاسبه "فاصله" بین دو گره استفاده می کند. این فاصله به صورت یای انحصاری بین دو شناسه گره محاسبه می شود و نتیجه را به عنوان یک عدد صحیح بی علامت برمی گرداند. کلیدها و شناسه های Keys و Node از یک قالب و طول یکسان برخوردار هستند ، بنابراین می توان فاصله را بین آنها به طور یکسان محاسبه کرد. شناسه گره معمولاً یک عدد تصادفی بزرگ است که با هدف منحصر به فرد بودن برای یک گره خاص انتخاب می شود (به UUID مراجعه کنید).گاه اتفاق می افتد که گره هایی که از نظرجغرافیایی به طور گسترده ای - بطورمثال آلمان و استرالیا - از هم دور و جدا هستند ، اگر شناسه های گره تصادفی مشابهی را انتخاب نموده باشند ،می توانند "همسایه" قلمداد شوند.

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

• فاصله بین یک گره و خودش صفر است
• متقارن است: "مسافت" که از A تا B و B از A محاسبه می شود ، یکسان هستند
• از نابرابری مثلثی تبعیت می کند: با فرض این که A ، B و C راس (نقاط) یک مثلث هستند ، پس فاصله A تا B کوتاهتر از (یا مساوی با) جمع فاصله از A تا C به علاوه فاصله از C به B است.

این سه شرط کافی است تا اطمینان حاصل شود که یای انحصاری همه ویژگیهای مهم و اصلی یک تابع فاصله "واقعی" را دارد، در عین حال ارزان و ساده برای محاسبه است.

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

جداول مسیریابی با اندازه ثابت

این بخش برای استفاده از تنها یک بیت ساده سازی شده است. برای اطلاعات بیشتر در مورد جداول مسیریابی واقعی به بخش جداول مرجع تقویت شده مراجعه کنید.

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

جداول مسیریابی کادملیا شامل یک لیست برای هر بیت شناسه گره است. (به عنوان مثال اگر یک شناسه گره شامل 128 بیت باشد ، یک گره تعداد 128 عدد از این لیستها را نگه می دارد. ) یک لیست دارای ورودی های زیادی است. هر ورودی در یک لیست داده های لازم را برای یافتن گره دیگر در اختیار دارد. داده های موجود در هر ورودی لیست معمولاً آدرس IP ، پورت و شناسه گره دیگر است. هر لیست با فاصله مشخصی از گره مطابقت دارد. گره های که می تواند در n لیست جا بگیرند باید یک بیت n متفاوت از شناسه (ID) گره داشته باشند. اولین بیت n-1 شناسه نامزد باید با شناسه گره مطابقت داشته باشد. این بدان معنی است که جمع کردن لیست اول بسیار آسان است زیرا 1/2 گره های موجود در شبکه کاندیدای قرارگرفتن در دوردست هستند. در لیست بعدی فقط می توان از 1/4 از گره های موجود در شبکه استفاده کرد (یک بیت نزدیک تر از اول) و غیره.

با داشتن یک شناسه 128 بیتی ، هر گره در شبکه گره های دیگر را در یکی از 128 فاصله مختلف ، یک فاصله خاص در هر بیت طبقه بندی می کند.

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

در ادبیات کادملیا، از لیست ها به (k-سطل) یاد می شود . k یک عدد سیستمی مانند 20 است. هر (k-سطل) لیستی است که دارای ورودی های K در داخل خودش است. یعنی برای شبکه ای با k = 20 ، هر گره دارای لیست هایی است که حداکثر 20 گره را برای یک بیت خاص (فاصله خاص از خود) دارد.

از آنجا که گره های ممکن برای هر(k-سطل)به سرعت کاهش می یابد (زیرا گره های بسیار کمی در آن نزدیکی وجود خواهد داشت) ، بیت پایینتر (k-سطل) ، تمام گره ها را در آن بخش از شبکه به طور کامل نگاشت می کنند. از آنجا که مقدار شناسه های ممکن بسیار بزرگتر از هر تعداد گره ممکن است ، برخی از (k-سطل) ها که مربوط به مسافت های بسیار کوتاه هستند ، خالی باقی می مانند.

شبکه ساده سمت راست را در نظر بگیرید. اندازه شبکه 2 به توان 3 یا 8 کلید و گره حداکثر است. هفت گره برای شرکت کردن وجود دارند. حلقه های کوچک در پایین گره مورد نظر گره شش (دودویی 110) به رنگ سیاه است. در این شبکه سه سطل K برای هر گره وجود دارد. گره های صفر ، یک و دو (باینری 000 ، 001 و 010) نامزد دورترین سطل K هستند . گره سه (دودویی 011 ، نشان داده نشده است) در شبکه شرکت نمی کند. در سطل k میانی ، گره های چهار و پنج (باینری 100 و 101) قرار می گیرند. سرانجام ، سطل سوم k فقط می تواند شامل گره هفت باشد (باینری 111). هر یک از سه سطل K در یک دایره خاکستری محصور شده است. اگر اندازه k-bucket دو بود ، دورترین 2-سطل فقط می تواند حاوی دو تا از سه گره باشد. به عنوان مثال ، اگر گره شش گره یک و دو را در دورترین 2 سطل داشته باشد ، برای یافتن محل (آدرس ip) گره صفر ، باید یک جستجوی شناسه گره به این گره ها بخواهید. هر گره همسایگی خود را به خوبی می شناسد و با چند گره دورتر ارتباط دارد که می تواند به گره های دیگر دورتر کمک کند.

مشخص است که گره هایی که مدت طولانی در یک شبکه متصل شده اند ، احتمالاً در آینده برای مدت طولانی متصل خواهند بود. به دلیل این توزیع آماری ، کادملیاگره های متصل طولانی را برای ماندن در سطل های K انتخاب می کند. این تعداد گره های معتبر شناخته شده را در آینده افزایش می دهد و شبکه پایدار تری را فراهم می کند.

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

پیام های پروتکل

کادملیاچهار پیام دارد.

• PING - برای تأیید اینکه گره هنوز زنده است استفاده می شود.
• STORE - یک جفت (کلید ، ارزش) را در یک گره ذخیره می کند.
• FIND_NODE - گیرنده درخواست گره های k را در سطل خود که نزدیکترین آنها به کلید درخواست شده است ، بازمی گرداند.
• FIND_VALUE - مشابه FIND_NODE ، اما اگر گیرنده درخواست کلید درخواستی را در فروشگاه خود داشته باشد ، مقدار مربوطه را برمی گرداند.

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

گره ها را پیدا کنید

جستجوی گره ها می توانند به صورت غیر همزمان انجام شوند. مقدار جستجوی همزمان توسط α مشخص شده و به طور معمول سه است. یک گره با جستجوی گره های α در سطل های K که نزدیکترین آن به کلید مورد نظر است ، یک درخواست FIND_NODE را آغاز می کند. هنگامی که این گره های گیرنده درخواست را دریافت می کنند ، در سطل های K آنها نگاه می کنند و نزدیکترین گره های k را به کلید مورد نظر خود باز می گردانند. درخواست کننده با نتایج (شناسه گره) که دریافت می کند ، لیست نتایج را به روز می کند و بهترین k ((گره های k که به کلید جستجو نزدیکتر هستند) را نگه می دارد و به سؤالات پاسخ می دهد. سپس درخواست از این K بهترین نتایج را انتخاب کنید و صدور درخواست به آنها، و دوباره و دوباره تکرار این فرایند است. از آنجا که هر گره نسبت به سایر گره ها شناخت بهتری نسبت به محیط اطراف خود دارد ، نتایج دریافت شده گره های دیگری خواهد بود که هر بار به کلید جستجو نزدیکتر و نزدیک تر می شوند. این تکرارها تا زمان بازگشت هیچ گره ای که به بهترین نتایج قبلی نزدیک باشد ، ادامه می یابد. هنگامی که تکرارها متوقف می شوند ، بهترین گره k در لیست نتایج آنهایی هستند که در کل شبکه نزدیک به کلید مورد نظر هستند.

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

یافتن منابع

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

مقادیر در چندین گره (k از آنها) ذخیره می شوند تا گره ها بتوانند بیایند و بروند و همچنان مقداری از گره را در دسترس داشته باشند. بطور دوره ای ، گره ای که مقدار را ذخیره می کند ، شبکه را کاوش می کند تا گره های k را که به مقدار کلیدی نزدیک هستند پیدا کنند و مقدار آن را بر روی آنها تکرار کنند. این گره ها را ناپدید می کند.

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

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

پیوستن به شبکه

گره ای که مایل به پیوستن به شبکه است ابتدا باید از یک فرآیند راه انداز شروع شود. در این مرحله ، گره اتصال می بایست آدرس IP و پورت یک گره دیگر - یک گره راه انداز (از کاربر یا از یک لیست ذخیره شده) را بشناسد - این هم اکنون در شبکه کادملیاشرکت می کند. اگر گره پیوستن هنوز در شبکه شرکت نکرده باشد ، یک شماره شناسه تصادفی را محاسبه می کند که تصور می شود قبلاً به هیچ گره دیگری اختصاص نیافته است. تا زمان خروج از شبکه از این ID استفاده می کند.

گره اتصال دهنده گره راه انداز را در یکی از سطل های K آن قرار می دهد. گره اتصال سپس یک گره را از شناسه خود در برابر گره راه انداز انجام می دهد (تنها گره دیگری که می داند). "خود جستجو" سطل های دیگر K را با شناسه گره جدید جمع می کند ، و سطل های K- گره اتصال را با گره هایی در مسیر بین آن و گره راه انداز جمع می کند. پس از این ، گره پیوستگی تمام سطل های K را دورتر از k-bucket می کند که گره راه انداز در آن قرار می گیرد. این تازه سازی فقط جستجوی یک کلید تصادفی است که در آن محدوده k-bucket قرار دارد.

در ابتدا گره ها یک سطل K دارند . هنگامی که سطل k کامل می شود ، می توان آنرا تقسیم کرد. شکاف در صورتی رخ می دهد که دامنه گره ها در سطل k ، شناسه مخصوص خود گره را بپیماید (مقادیر در سمت چپ و راست در یک درخت باینری). کادملیاحتی این قاعده را برای یک "نزدیکترین گره" k-سطل آرام می کند ، زیرا به طور معمول یک سطل منفرد با فاصله ای مطابقت می کند که تمام گره هایی که به این گره نزدیکترین هستند وجود داشته باشد ، ممکن است آنها بیش از k باشند ، و ما آن را می خواهیم. همه آنها را بشناسیم ممکن است معلوم شود که یک درخت باینری بسیار نامتعادل در نزدیکی گره وجود دارد. اگر k 20 باشد ، و 21 گره با پیشوند "xxx0011 ....." وجود دارد و گره جدید "xxx0000 11001 " است ، گره جدید می تواند شامل چندین سطل k برای سایر گره های 21+ باشد. این تضمین می کند که شبکه از همه گره های نزدیکترین منطقه اطلاع دارد.

جستجوی شتاب

کادملیابرای تعیین فاصله از سنجش XOR استفاده می کند. دو شناسه گره با هم یا یک شناسه گره و یک کلید باهم XOR می شوند و نتیجه این عمل ، فاصله بین آنها را تعیین می کند. برای هر بیت،تابع XOR ، اگر دو بیت مساوی و یکی باشد صفر و اگر دو بیت با هم متفاوت باشند 1 را برمی گرداند. فواصل در سنجشهای XOR از قانون نابرابری مثلث پیروی می کنند: با توجه به اینکه A ، B و C راس (نقاط) یک مثلث هستند ، سپس فاصله A تا B کوتاهتر از (یا مساوی با) از مجموع فاصله A تا C تا B است.

سنجش XOR به کادملیا اجازه می دهد جداول مسیریابی را فراتر از بیت های واحد قرار دهد. گروه های بیت را می توان در سطل های K قرار داد. به گروه بیت ها پیشوند گفته می شود. برای پیشوند m-bit ، سطل 2 -1 وجود دارد. سطل K- گمشده ، بخش دیگری از درخت مسیریابی است که شامل شناسه گره است. پیشوند m-bit حداکثر تعداد جستجوها را از log ₂ n تا log ₂ n کاهش می دهد . اینها مقادیر حداکثر هستند و مقدار متوسط به مراتب کمتر خواهد بود ، شانس یافتن گره در یک k-bucket که بیت های بیشتری را نسبت به پیشوند با کلید هدف به اشتراک می گذارد ، افزایش می دهد.

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

در حالی که سنجش XOR برای درک کادملیا الزامی نیست ، اما در تجزیه و تحلیل پروتکل بسیار مهم است. حساب XOR یک گروه آبلی تشکیل می دهد که می تواند تجزیه و تحلیل بسته را انجام دهد. سایر پروتکل ها و الگوریتم های DHT به منظور پیش بینی رفتار و صحت شبکه ، نیاز به شبیه سازی یا تحلیل رسمی پیچیده دارند. استفاده از گروه های بیت به عنوان مسیریابی اطلاعات ، الگوریتم ها را نیز ساده می کند.

برای تجزیه و تحلیل الگوریتم ، یک شبکه کادملیارا در نظر بگیرید ${\displaystyle n}$

اجازه دهید ${\displaystyle T_{xy}}$

${\displaystyle \underset{x_1,\dots ,x_n}{sup}\underset{x\in \{x_1,\dots ,x_n\}}{sup}\underset{y\in \{0,1{\}}^d}{sup}\mathbb{E}[T_{xy}]\le (1+o(1))\frac{\log n}{H_k},}$

جایی که ${\displaystyle H_k}$

برای نزدیکتر کردن مدل به شبکه های واقعی کادملیا، ${\displaystyle x_1,\dots ,x_n}$

جایی که ${\displaystyle c_k}$

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

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

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

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

شبکه ها

شبکه های عمومی با استفاده از الگوریتم کادملیا(این شبکه ها با یکدیگر ناسازگار هستند):

• I2P - یک لایه شبکه با پوشش ناشناس.
• شبکه Kad - در اصل توسط جامعه eMule توسعه یافته است تا جایگزین معماری مبتنی بر سرور شبکه eDonkey2000 شود .
• اتریوم - پروتکل کشف گره در پشته شبکه بلاکچین.اتریوم مبتنی بر اجرای کمی اصلاح شده از کادملیااست.
• شبکه اورنت: با استفاده از KadC که یک کتابخانه C برای دستیابی به کادملیااست. (توسعه Overnet متوقف شده است)
• BitTorrent از DHT مبتنی بر اجرای الگوریتم کادملیابرای تورنتهای بدون ردیاب استفاده می کند.
• Osiris sps اوسیریس (تمام نسخه ها): برای مدیریت پورتال وب توزیع شده و ناشناس استفاده می شود.
• Retroshare - بستر ارتباطی غیر متمرکز F2F با VOIP امن ، پیام رسانی فوری ، انتقال پرونده و غیره.
• Tox - یک بستر پیام رسانی ، VoIP و چت تصویری کاملاً توزیع شده
• Gnutella DHT - در اصل توسط LimeWire برای تقویت پروتکل Gnutella برای یافتن مکان پرونده های جایگزین ، اکنون توسط سایر مشتری های gnutella استفاده می شود.
• IPFS - یک سیستم فایل متشکل از همسالان مبتنی بر libp2p.
• TeleHash یک پروتکل شبکه مش است که از کادملیابرای حل و فصل ارتباط مستقیم بین طرفین استفاده می کند.
• iMule - نرم افزار ابزار اشتراک فایل برای I2P .
• OpenDHT - کتابخانه ای که اجرای کادملیارا ارائه می دهد ، توسط جامی و دیگران استفاده می شود.
• GNUnet - پشته شبکه جایگزین برای ایجاد برنامه های توزیع شده ایمن ، غیرمتمرکز و حفظ حریم خصوصی. از نسخه تصادفی کادملیابه نام R5N استفاده می کند

• شبکه آدرس دهی محتوا
• کورد (DHT)
• تاپستری(DHT)
• پاستری(DHT)
• کوورد

• پروژه های Xlattice مشخصات و تعاریف Kademlia.