کادملیا
کادملیا (Kademlia ) یک جدول هشی توزیع شده برای شبکه های کامپیوتری نامتمرکز همتا به همتا است که توسط پتار میمونونکوف و دیوید مازییرز در سال 2002 طراحی شده است. ساختار شبکه و تبادل اطلاعات را از طریق جستجوی گره مشخص می کند. گره های کادملیا با استفاده از UDP میان یکدیگر ارتباط برقرار می کنند. یک شبکه مجازی یا همپوشان توسط گره های شرکت کننده تشکیل می شود. هر گره توسط یک شماره یا "شناسه گره" مشخص می "شود" . شناسه گره نه تنها به عنوان شناسایی عمل می کند بلکه الگوریتم کادملیا از "شناسه گره" برای یافتن مقادیر (معمولاً هش فایل یا کلمات کلیدی) استفاده می کند. در واقع ، "شناسه گره" نقشه مستقیمی را برای تهیه هش ها فراهم می کند و این گره اطلاعات مربوط به محل دسترسی به فایل یا منبع را ذخیره می کند.
الگوریتم هنگام جستجو برای برخی از مقادیر ، باید کلید همراه را بشناسد و در چندین گام شبکه را کاوش کند. هر گام گره هایی را که به کلید نزدیک تر هستند پیدا می کند تا زمانی که گره تماس گرفته شده مقدار را برگرداند یا گره های نزدیک تری پیدا نکنند. این روش بسیار کارآمد است: مانند بسیاری دیگر از ، کادملیا فقط با formula_1 گره در طول جستجو از کل formula_2 گره های موجود در سیستم سر و کار خواهد داشت.
مزایای بیشتر این روش به ویژه در ساختار غیر متمرکز یافت می شود ، جایی که باعث افزایش مقاومت در برابر حملات امتناع از سرویس دهی می شود . حتی اگر مجموعه ای از گره ها سرریز شود ، این امر تأثیر محدودی بر در دسترس بودن شبکه خواهد داشت ، زیرا شبکه با گره زدن شبکه به اطراف این "سوراخ ها" ، خود را بازیابی می کند.
پیاده سازی اینترنت مخفی کادملیا برای کاهش آسیب پذیری های کادملیا در برابر حملات مانند حملات سیبیل اصلاح شده است.
اولین شبکه های همتا به همتای به اشتراک گذاری فایل ها ، مانند نپستر Napster ، برای ایجاد هماهنگ سازی مراجعات در شبکه به یک پایگاه داده مرکزی متکی بودند. شبکه های همتا به همتای نسل دوم ، مانند ناتلا Gnutella ، برای یافتن پرونده ها از فلودینگ استفاده می کردند و هر گره را در شبکه جستجو می کردند. شبکه های همتا به همتا نسل سوم از جداول هش توزیع شده برای جستجوی فایل ها در شبکه استفاده می کنند. "جداول هش توزیع" شده ، مکان منابع در سراسر شبکه را ذخیره می کنند. معیار اصلی این پروتکل ها مکان یابی سریع گره های مورد نظر است.
کادملیا از یک روش محاسبه "فاصله" بین دو گره استفاده می کند. این فاصله به صورت یای انحصاری بین دو شناسه گره محاسبه می شود و نتیجه را به عنوان یک عدد صحیح بی علامت برمی گرداند. کلیدها و شناسه های Keys و Node از یک قالب و طول یکسان برخوردار هستند ، بنابراین می توان فاصله را بین آنها به طور یکسان محاسبه کرد. شناسه گره معمولاً یک عدد تصادفی بزرگ است که با هدف منحصر به فرد بودن برای یک گره خاص انتخاب می شود (به UUID مراجعه کنید).گاه اتفاق می افتد که گره هایی که از نظرجغرافیایی به طور گسترده ای - بطورمثال آلمان و استرالیا - از هم دور و جدا هستند ، اگر شناسه های گره تصادفی مشابهی را انتخاب نموده باشند ،می توانند "همسایه" قلمداد شوند.
یای انحصاری به این دلیل انتخاب شده است زیرا به عنوان یک تابع فاصله بین تمام شناسه های گره عمل می کند. به طور مشخص: این سه شرط کافی است تا اطمینان حاصل شود که یای انحصاری همه ویژگیهای مهم و اصلی یک تابع فاصله "واقعی" را دارد، در عین حال ارزان و ساده برای محاسبه است.
هر تکرار جستجوی کادملیا کمی به هدف نزدیکتر می شود. یک شبکه اساسی کادملیا با 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" جواب ندهد. به عبارت دیگر: گره های جدید فقط در صورت ناپدید شدن گره های قدیمی استفاده می شوند.
کادملیاچهار پیام دارد. هر پیام 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 به منظور پیش بینی رفتار و صحت شبکه ، نیاز به شبیه سازی یا تحلیل رسمی پیچیده دارند. استفاده از گروه های بیت به عنوان مسیریابی اطلاعات ، الگوریتم ها را نیز ساده می کند.
برای تجزیه و تحلیل الگوریتم ، یک شبکه کادملیارا در نظر بگیرید formula_2 گره ها با شناسه formula_4 که هر کدام یک رشته طول دارند formula_5 که فقط از آنها و صفرها تشکیل شده است می توان آن را به عنوان یک trie مدل کرد که در آن هر برگ یک گره را نشان می دهد ، و مسیر برچسب زده شده از ریشه به یک برگ نشانگر ID آن است. برای یک گره formula_6 ، اجازه دهید formula_7 مجموعه گره ها (شناسه ها) باشد که پیشوند را با آنها به اشتراک می گذارد formula_8 طول formula_9 . سپس پر کردن formula_10 سطل چهارم formula_8 می توان به عنوان افزودن نشانگرها از برگ مدل شد formula_8 به formula_13 برگ (شناسه) به طور یکنواخت به طور تصادفی از formula_7 . بنابراین مسیریابی می تواند پرش در میان برگها در امتداد این نشانگرها باشد به گونه ای که هر مرحله تا حد ممکن به سمت شناسه هدف پیش می رود ، یعنی به طریقی حریص.
اجازه دهید formula_15 تعداد پرش های لازم برای رفتن از برگ باشد formula_8 به شناسه هدف formula_17 . فرض کنید که formula_4 به طور قطعی از بین انتخاب می شوند formula_19 ثابت شده است که
جایی که formula_21 هست formula_13 - شماره هارمونیک از آنجا که formula_23 مانند formula_24 ، چه زمانی formula_13 بزرگ است formula_26 از بالا به حدود محدود است formula_27 با این حال شناسه ها و هدف انتخاب می شوند. این شهودی را توجیه می کند که فقط در کادملیا وجود دارد formula_28 گره ها در جستجوی یک گره هدف تماس می گیرند.
برای نزدیکتر کردن مدل به شبکه های واقعی کادملیا، formula_4 همچنین می توان فرض کرد که به طور تصادفی و بدون جایگزینی از یکنواخت انتخاب می شود formula_19 . سپس می توان ثابت کرد که برای همه formula_6 و formula_32 ،
جایی که formula_34 یک ثابت است که فقط به آن بستگی دارد formula_13 با formula_36 مانند formula_24 . بنابراین برای formula_13 بزرگ ، formula_39 به یک نزدیک ثابت تبدیل می شود formula_40 . این بدان معنی است که تعداد گره ها برای جستجوی یک گره هدف نیاز به تماس دارند formula_41 به طور متوسط.
کادملیادر شبکه های اشتراک فایل استفاده می شود. با انجام جستجوی کلمات کلیدی کادملیامی توان اطلاعاتی را در شبکه اشتراک فایل پیدا کرد تا بارگیری شود. از آنجا که هیچ نمونه مرکزی برای ذخیره یک فهرست از پرونده های موجود وجود ندارد ، این کار به طور مساوی بین کلیه مشتری ها تقسیم می شود: اگر یک گره بخواهد یک فایل را به اشتراک بگذارد ، محتویات پرونده را پردازش می کند ، و از آن عددی ( هش ) محاسبه می کند. این پرونده را در شبکه اشتراک گذاری فایل شناسایی کنید. شناسه های هش و شناسه های گره باید به همان طول باشند. سپس چندین گره را که شناسه آنها نزدیک به هش است جستجو می کند و آدرس IP خاص خود را در آن گره ها ذخیره می کند. یعنی خود را به عنوان منبع این پرونده منتشر می کند. مشتری جستجوگر از کادملیابرای جستجوی شبکه برای گره ای استفاده می کند که شناسه آن کمترین فاصله را با هش پرونده داشته باشد ، سپس لیست منابعی را که در آن گره ذخیره شده است بازیابی می کند.
از آنجا که یک کلید می تواند با بسیاری از مقادیر مطابقت داشته باشد ، به عنوان مثال بسیاری از منابع با همان پرونده ، هر گره ذخیره سازی می تواند اطلاعات مختلفی داشته باشد. سپس از همه گره های k نزدیک به کلید از منابع درخواست می شود.
هش پرونده معمولاً از یک پیوند مخصوص آهنربای اینترنتی که در جای دیگر یافت می شود ، یا در یک پرونده فهرست بندی به دست آمده از منابع دیگر گنجانده می شود.
جستجوهای نام فایل با استفاده از کلمات کلیدی اجرا می شود. نام پرونده به کلمات تشکیل دهنده آن تقسیم می شود. هر یک از این کلمات کلیدی به همراه نام پرونده و هش پرونده در شبکه ذخیره شده و ذخیره می شوند. جستجو شامل انتخاب یکی از کلمات کلیدی ، تماس با گره با شناسه نزدیک به آن کلید واژه و بازیابی لیست نام فایلهای حاوی کلمه کلیدی است. از آنجا که هر نام پرونده در لیست هش خود پیوست شده است ، پس از آن پرونده انتخاب شده به روش عادی قابل دستیابی است.
شبکه های عمومی با استفاده از الگوریتم کادملیا(این شبکه ها با یکدیگر ناسازگار هستند):