موضوع مقاله: کادملیا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کادملیا | مقدمه: کادملیا (Kademlia ) یک جدول هشی توزیع شده برای شبکه های کامپیوتری نامتمرکز همتا به همتا است که توسط پتار میمونونکوف و دیوید مازییرز در سال 2002 طراحی شده است. | ## بخش 1: کادملیا | شناسه گره نه تنها به عنوان شناسایی عمل می کند بلکه الگوریتم کادملیا از شناسه گره برای یافتن مقادیر (معمولاً هش فایل یا کلمات کلیدی) استفاده می کند. در واقع ، شناسه گره نقشه مستقیمی را برای تهیه هش ها فراهم می کند و این گره اطلاعات مربوط به محل دسترسی به فایل یا منبع را ذخیره می کند. الگوریتم هنگام جستجو برای برخی از مقادیر ، باید کلید همراه را بشناسد و در چندین گام شبکه را کاوش کند. هر گام گره هایی را که به کلید نزدیک تر هستند پیدا می کند تا زمانی که گره تماس گرفته شده مقدار را برگرداند یا گره های نزدیک تری پیدا نکنند. این روش بسیار کارآمد است: مانند بسیاری دیگر از ، کادملیا فقط با گره در طول جستجو از کل گره های موجود در سیستم سر و کار خواهد داشت. مزایای بیشتر این روش به ویژه در ساختار غیر متمرکز یافت می شود ، جایی که باعث افزایش مقاومت در برابر حملات امتناع از سرویس دهی می شود . حتی اگر مجموعه ای از گره ها سرریز شود ، این امر تأثیر محدودی بر در دسترس بودن شبکه خواهد داشت ، زیرا شبکه با گره زدن شبکه به اطراف این "سوراخ ها" ، خود را بازیابی می کند. پیاده سازی اینترنت مخفی کادملیا برای کاهش آسیب پذیری های کادملیا در برابر حملات مانند حملات سیبیل اصلاح شده است. جزئیات سیستم اولین شبکه های همتا به همتای به اشتراک گذاری فایل ها ، مانند نپستر Napster ، برای ایجاد هماهنگ سازی مراجعات در شبکه به یک پایگاه داده مرکزی متکی بودند. شبکه های همتا به همتای نسل دوم ، مانند ناتلا Gnutella ، برای یافتن پرونده ها از فلودینگ استفاده می کردند و هر گره را در شبکه جستجو می کردند. شبکه های همتا به همتا نسل سوم از جداول هش توزیع شده برای جستجوی فایل ها در شبکه استفاده می کنند. این فاصله به صورت یای انحصاری بین دو شناسه گره محاسبه می شود و نتیجه را به عنوان یک عدد صحیح بی علامت برمی گرداند. کلیدها و شناسه های Keys و Node از یک قالب و طول یکسان برخوردار هستند ، بنابراین می توان فاصله را بین آنها به طور یکسان محاسبه کرد. شناسه گره معمولاً یک عدد تصادفی بزرگ است که با هدف منحصر به فرد بودن برای یک گره خاص انتخاب می شود (به UUID مراجعه کنید).گاه اتفاق می افتد که گره هایی که از نظرجغرافیایی به طور گسترده ای - بطورمثال آلمان و استرالیا - از هم دور و جدا هستند ، اگر شناسه های گره تصادفی مشابهی را انتخاب نموده باشند ،می توانند "همسایه" قلمداد شوند. یای انحصاری به این دلیل انتخاب شده است زیرا به عنوان یک تابع فاصله بین تمام شناسه های گره عمل می کند. به طور مشخص: فاصله بین یک گره و خودش صفر است متقارن است: "مسافت" که از A تا B و B از A محاسبه می شود ، یکسان هستند از نابرابری مثلثی تبعیت می کند: با فرض این که A ، B و C راس (نقاط) یک مثلث هستند ، پس فاصله A تا B کوتاهتر از (یا مساوی با) جمع فاصله از A تا C به علاوه فاصله از C به B است. این سه شرط کافی است تا اطمینان حاصل شود که یای انحصاری همه ویژگیهای مهم و اصلی یک تابع فاصله "واقعی" را دارد، در عین حال ارزان و ساده برای محاسبه است. یک شبکه اساسی کادملیا با 2n گره برای پیدا کردن گره مقصد تنها به n تکرار(در بدترین حالت) نباز خواهد داشت . جداول مسیریابی با اندازه ثابت این بخش برای استفاده از تنها یک بیت ساده سازی شده است. برای اطلاعات بیشتر در مورد جداول مسیریابی واقعی به بخش جداول مرجع تقویت شده مراجعه کنید. جداول مسیریابی اندازه ثابت در نسخه قبل از رسیدگی مقاله اصلی ارائه شده است و در نسخه بعدی فقط برای برخی از اثبات های ریاضی استفاده می شود. یک اجرای واقعی کادملیا دارای جدول مسیریابی با اندازه ثابت نیست بلکه دارای جدول مسیریابی با اندازه پویا است. (به عنوان مثال اگر یک شناسه گره شامل 128 بیت باشد ، یک گره تعداد 128 عدد از این لیستها را نگه می دارد. گره های که می تواند در n امین لیست جا بگیرند باید یک بیت n ام متفاوت از شناسه (ID) گره داشته باشند. این بدان معنی است که جمع کردن لیست اول بسیار آسان است زیرا 1/2 گره های موجود در شبکه کاندیدای قرارگرفتن در دوردست هستند. در لیست بعدی فقط می توان از 1/4 از گره های موجود در شبکه استفاده کرد (یک بیت نزدیک تر از اول) و غیره. با داشتن یک شناسه 128 بیتی ، هر گره در شبکه گره های دیگر را در یکی از 128 فاصله مختلف ، یک فاصله خاص در هر بیت طبقه بندی می کند. این کار شامل عملیات ذخیره سازی و بازیابی و حتی کمک به گره های دیگر برای یافتن کلید است. این ویژگی باعث می شود شبکه به طور مداوم به روز شود و مقاومت در برابر خرابی ها یا حملات را افزایش دهد. یعنی برای شبکه ای با k = 20 ، هر گره دارای لیست هایی است که حداکثر 20 گره را برای یک بیت خاص (فاصله خاص از خود) دارد. از آنجا که گره های ممکن برای هر(k-سطل)به سرعت کاهش می یابد (زیرا گره های بسیار کمی در آن نزدیکی وجود خواهد داشت) ، بیت پایینتر (k-سطل) ، تمام گره ها را در آن بخش از شبکه به طور کامل نگاشت می کنند. از آنجا که مقدار شناسه های ممکن بسیار بزرگتر از هر تعداد گره ممکن است ، برخی از (k-سطل) ها که مربوط به مسافت های بسیار کوتاه هستند ، خالی باقی می مانند. | ## بخش 2: کادملیا | به عنوان مثال ، اگر گره شش گره یک و دو را در دورترین 2 سطل داشته باشد ، برای یافتن محل (آدرس ip) گره صفر ، باید یک جستجوی شناسه گره به این گره ها بخواهید. هر گره همسایگی خود را به خوبی می شناسد و با چند گره دورتر ارتباط دارد که می تواند به گره های دیگر دورتر کمک کند. مشخص است که گره هایی که مدت طولانی در یک شبکه متصل شده اند ، احتمالاً در آینده برای مدت طولانی متصل خواهند بود. به دلیل این توزیع آماری ، کادملیاگره های متصل طولانی را برای ماندن در سطل های K انتخاب می کند. این تعداد گره های معتبر شناخته شده را در آینده افزایش می دهد و شبکه پایدار تری را فراهم می کند. هنگامی که یک سطل k کامل است و یک گره جدید برای آن سطل k کشف می شود ، کمترین گره اخیراً در سطل k دیده می شود PINGed. اگر مشخص شود که گره هنوز زنده است ، گره جدید در یک لیست ثانویه ، یک حافظه نهان جایگزین قرار می گیرد. به عبارت دیگر: گره های جدید فقط در صورت ناپدید شدن گره های قدیمی استفاده می شوند. (به کوکی جادویی مراجعه کنید) گره ها را پیدا کنید جستجوی گره ها می توانند به صورت غیر همزمان انجام شوند. یک گره با جستجوی گره های α در سطل های K که نزدیکترین آن به کلید مورد نظر است ، یک درخواست FIND_NODE را آغاز می کند. هنگامی که این گره های گیرنده درخواست را دریافت می کنند ، در سطل های K آنها نگاه می کنند و نزدیکترین گره های k را به کلید مورد نظر خود باز می گردانند. درخواست کننده با نتایج (شناسه گره) که دریافت می کند ، لیست نتایج را به روز می کند و بهترین k گره های k که به کلید جستجو نزدیکتر هستند) را نگه می دارد و به سؤالات پاسخ می دهد. سپس درخواست از این K بهترین نتایج را انتخاب کنید و صدور درخواست به آنها، و دوباره و دوباره تکرار این فرایند است. از آنجا که هر گره نسبت به سایر گره ها شناخت بهتری نسبت به محیط اطراف خود دارد ، نتایج دریافت شده گره های دیگری خواهد بود که هر بار به کلید جستجو نزدیکتر و نزدیک تر می شوند. این تکرارها تا زمان بازگشت هیچ گره ای که به بهترین نتایج قبلی نزدیک باشد ، ادامه می یابد. هنگامی که تکرارها متوقف می شوند ، بهترین گره k در لیست نتایج آنهایی هستند که در کل شبکه نزدیک به کلید مورد نظر هستند. هنگامی که یک پرس و جو پایان یافت ، می توان پرس و جو دیگری را آغاز کرد ، هرگز از درخواستهای α در همان زمان تجاوز نکنید. پیدا کردن یک مقدار از همان روشی که مکانهای نزدیک به یک کلید را پیدا می کنید پیروی می کند ، به جز جستجو وقتی که یک گره مقدار درخواستی را در فروشگاه خود داشته باشد خاتمه می یابد و این مقدار را برمی گرداند. مقادیر در چندین گره (k از آنها) ذخیره می شوند تا گره ها بتوانند بیایند و بروند و همچنان مقداری از گره را در دسترس داشته باشند. بطور دوره ای ، گره ای که مقدار را ذخیره می کند ، شبکه را کاوش می کند تا گره های k را که به مقدار کلیدی نزدیک هستند پیدا کنند و مقدار آن را بر روی آنها تکرار کنند. همچنین ، برای مقادیر محبوب که ممکن است درخواست های زیادی داشته باشند ، با داشتن یک گیرنده این مقدار را در بعضی از گره های نزدیک ، اما خارج از آن ، نزدیکترین k ، بار در گره های فروشگاه کم می شود. از آنجا که مقدار از گره ها دورتر از کلید بازگردانده می شود ، این "نقاط داغ" احتمالی را کاهش می دهد. برخی از پیاده سازی ها (به عنوان مثال کد ) نه همانند سازی و نه حافظه پنهانی دارد. پیوستن به شبکه گره ای که مایل به پیوستن به شبکه است ابتدا باید از یک فرآیند راه انداز شروع شود. در این مرحله ، گره اتصال می بایست آدرس IP و پورت یک گره دیگر - یک گره راه انداز (از کاربر یا از یک لیست ذخیره شده) را بشناسد - این هم اکنون در شبکه کادملیاشرکت می کند. اگر گره پیوستن هنوز در شبکه شرکت نکرده باشد ، یک شماره شناسه تصادفی را محاسبه می کند که تصور می شود قبلاً به هیچ گره دیگری اختصاص نیافته است. گره اتصال سپس یک گره را از شناسه خود در برابر گره راه انداز انجام می دهد (تنها گره دیگری که می داند). "خود جستجو" سطل های دیگر K را با شناسه گره جدید جمع می کند ، و سطل های K- گره اتصال را با گره هایی در مسیر بین آن و گره راه انداز جمع می کند. پس از این ، گره پیوستگی تمام سطل های K را دورتر از k-bucket می کند که گره راه انداز در آن قرار می گیرد. شکاف در صورتی رخ می دهد که دامنه گره ها در سطل k ، شناسه مخصوص خود گره را بپیماید (مقادیر در سمت چپ و راست در یک درخت باینری). کادملیاحتی این قاعده را برای یک "نزدیکترین گره" k-سطل آرام می کند ، زیرا به طور معمول یک سطل منفرد با فاصله ای مطابقت می کند که تمام گره هایی که به این گره نزدیکترین هستند وجود داشته باشد ، ممکن است آنها بیش از k باشند ، و ما آن را می خواهیم. همه آنها را بشناسیم ممکن است معلوم شود که یک درخت باینری بسیار نامتعادل در نزدیکی گره وجود دارد. | ## بخش 3: کادملیا | اگر k 20 باشد ، و 21 گره با پیشوند "xxx0011 ..." وجود دارد و گره جدید "xxx0000 11001 " است ، گره جدید می تواند شامل چندین سطل k برای سایر گره های 21+ باشد. دو شناسه گره با هم یا یک شناسه گره و یک کلید باهم XOR می شوند و نتیجه این عمل ، فاصله بین آنها را تعیین می کند. برای هر بیت،تابع XOR ، اگر دو بیت مساوی و یکی باشد صفر و اگر دو بیت با هم متفاوت باشند 1 را برمی گرداند. فواصل در سنجشهای XOR از قانون نابرابری مثلث پیروی می کنند: با توجه به اینکه A ، B و C راس (نقاط) یک مثلث هستند ، سپس فاصله A تا B کوتاهتر از (یا مساوی با) از مجموع فاصله A تا C تا B است. سنجش XOR به کادملیا اجازه می دهد جداول مسیریابی را فراتر از بیت های واحد قرار دهد. اینها مقادیر حداکثر هستند و مقدار متوسط به مراتب کمتر خواهد بود ، شانس یافتن گره در یک k-bucket که بیت های بیشتری را نسبت به پیشوند با کلید هدف به اشتراک می گذارد ، افزایش می دهد. گره ها می توانند از جدول پیشوندها در جدول مسیریابی خود استفاده کنند ، مانند شبکه Kad که توسط eMule استفاده شده است. شبکه کادملیا حتی می تواند در اجرای برنامه های مسیریابی ، بصورت ناهمگن عمل کند که به قیمت بالارفتن هزینه پیچیدگی در تجزیه و تحلیل جستجوها است. اهمیت علمی در حالی که سنجش XOR برای درک کادملیا الزامی نیست ، اما در تجزیه و تحلیل پروتکل بسیار مهم است. سایر پروتکل ها و الگوریتم های DHT به منظور پیش بینی رفتار و صحت شبکه ، نیاز به شبیه سازی یا تحلیل رسمی پیچیده دارند. استفاده از گروه های بیت به عنوان مسیریابی اطلاعات ، الگوریتم ها را نیز ساده می کند. تحلیل ریاضی الگوریتم برای تجزیه و تحلیل الگوریتم ، یک شبکه کادملیارا در نظر بگیرید گره ها با شناسه که هر کدام یک رشته طول دارند که فقط از آنها و صفرها تشکیل شده است می توان آن را به عنوان یک trie مدل کرد که در آن هر برگ یک گره را نشان می دهد ، و مسیر برچسب زده شده از ریشه به یک برگ نشانگر ID آن است. برای یک گره ، اجازه دهید مجموعه گره ها (شناسه ها) باشد که پیشوند را با آنها به اشتراک می گذارد طول . سپس پر کردن سطل چهارم می توان به عنوان افزودن نشانگرها از برگ مدل شد به برگ (شناسه) به طور یکنواخت به طور تصادفی از . بنابراین مسیریابی می تواند پرش در میان برگها در امتداد این نشانگرها باشد به گونه ای که هر مرحله تا حد ممکن به سمت شناسه هدف پیش می رود ، یعنی به طریقی حریص. فرض کنید که به طور قطعی از بین انتخاب می شوند ثابت شده است که جایی که هست - شماره هارمونیک از آنجا که مانند ، چه زمانی بزرگ است از بالا به حدود محدود است با این حال شناسه ها و هدف انتخاب می شوند. این شهودی را توجیه می کند که فقط در کادملیا وجود دارد گره ها در جستجوی یک گره هدف تماس می گیرند. برای نزدیکتر کردن مدل به شبکه های واقعی کادملیا، همچنین می توان فرض کرد که به طور تصادفی و بدون جایگزینی از یکنواخت انتخاب می شود . سپس می توان ثابت کرد که برای همه و ، جایی که یک ثابت است که فقط به آن بستگی دارد با مانند . این بدان معنی است که تعداد گره ها برای جستجوی یک گره هدف نیاز به تماس دارند به طور متوسط. در شبکه های اشتراک فایل استفاده کنید کادملیادر شبکه های اشتراک فایل استفاده می شود. با انجام جستجوی کلمات کلیدی کادملیامی توان اطلاعاتی را در شبکه اشتراک فایل پیدا کرد تا بارگیری شود. از آنجا که هیچ نمونه مرکزی برای ذخیره یک فهرست از پرونده های موجود وجود ندارد ، این کار به طور مساوی بین کلیه مشتری ها تقسیم می شود: اگر یک گره بخواهد یک فایل را به اشتراک بگذارد ، محتویات پرونده را پردازش می کند ، و از آن عددی ( هش ) محاسبه می کند. سپس چندین گره را که شناسه آنها نزدیک به هش است جستجو می کند و آدرس IP خاص خود را در آن گره ها ذخیره می کند. هر یک از این کلمات کلیدی به همراه نام پرونده و هش پرونده در شبکه ذخیره شده و ذخیره می شوند. جستجو شامل انتخاب یکی از کلمات کلیدی ، تماس با گره با شناسه نزدیک به آن کلید واژه و بازیابی لیست نام فایلهای حاوی کلمه کلیدی است. از آنجا که هر نام پرونده در لیست هش خود پیوست شده است ، پس از آن پرونده انتخاب شده به روش عادی قابل دستیابی است. پیاده سازی ها شبکه ها شبکه های عمومی با استفاده از الگوریتم کادملیا(این شبکه ها با یکدیگر ناسازگار هستند): I2P - یک لایه شبکه با پوشش ناشناس. اتریوم - پروتکل کشف گره در پشته شبکه بلاکچین.اتریوم مبتنی بر اجرای کمی اصلاح شده از کادملیااست. OpenDHT - کتابخانه ای که اجرای کادملیارا ارائه می دهد ، توسط جامی و دیگران استفاده می شود. | ## جمع‌بندی | GNUnet - پشته شبکه جایگزین برای ایجاد برنامه های توزیع شده ایمن ، غیرمتمرکز و حفظ حریم خصوصی.