كاديميليا

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 28 صور
الموسوعة الحرة

كاديمليا عبارة عن جدول تجزئة موزع لشبكات الحاسوب اللامركزية من نظير إلى نظير، صممه بيتر مايمونكوف وديفيد مازيير عام ٢٠٠٢. [ ١ ] [ ٢ ] يحدد كاديمليا بنية الشبكة وتبادل المعلومات من خلال عمليات البحث عن العقد . تتواصل عقد كاديمليا فيما بينها باستخدام بروتوكول UDP . تتكون شبكة افتراضية أو شبكة تراكبية من العقد المشاركة. يتم تعريف كل عقدة برقم أو معرّف عقدة . لا يقتصر دور معرّف العقدة على التعريف فحسب، بل تستخدمه خوارزمية كاديمليا لتحديد مواقع القيم (عادةً تجزئات الملفات أو الكلمات المفتاحية).

للبحث عن القيمة المرتبطة بمفتاح معين، تستكشف الخوارزمية الشبكة على عدة مراحل. في كل مرحلة، يتم البحث عن العقد الأقرب إلى المفتاح حتى تُعيد العقدة المتصلة القيمة أو حتى لا يتم العثور على عقد أقرب. هذه الطريقة فعّالة للغاية: فمثل العديد من خوارزميات DHT الأخرى ، لا تتصل خوارزمية Kademlia إلا بـيا(سجل⁡ن){\displaystyle O(\log n)}العقد أثناء البحث من إجمالين{\displaystyle n}العقد في النظام.

تتجلى مزايا أخرى، لا سيما في البنية اللامركزية، التي تزيد من مقاومة هجمات حجب الخدمة . فحتى في حال تعرض مجموعة كاملة من العقد للهجوم، سيكون تأثير ذلك محدودًا على توافر الشبكة، إذ ستستعيد الشبكة عافيتها من خلال إعادة بناء بنيتها حول هذه "الثغرات".

تم تعديل تطبيق I2P لـ Kademlia للتخفيف من نقاط ضعف Kademlia، مثل هجمات Sybil . [ 3 ]

بحسب بيتر مايمونكوف، فإن اسم كاديمليا مشتق من قمة جبلية في بلغاريا وكلمة تركية تعني "الرجل المحظوظ". [ 4 ]

تفاصيل النظام

تتكون شبكات الند للند من عُقد، بحسب تصميمها. وقد أصبحت البروتوكولات التي تستخدمها هذه العُقد للتواصل وتحديد مواقع المعلومات أكثر كفاءة مع مرور الوقت. اعتمدت شبكات مشاركة الملفات من الجيل الأول، مثل نابستر ، على قاعدة بيانات مركزية لتنسيق عمليات البحث في الشبكة. أما شبكات الجيل الثاني، مثل غنوتيلا ، فقد استخدمت تقنية الفيضان لتحديد مواقع الملفات، حيث تبحث في كل عُقدة على الشبكة. بينما تستخدم شبكات الجيل الثالث، مثل بت تورنت ، جداول التجزئة الموزعة للبحث عن الملفات في الشبكة. وتخزن جداول التجزئة الموزعة مواقع الموارد في جميع أنحاء الشبكة.

تستخدم كادمليا حساب "المسافة" بين عقدتين. تُحسب هذه المسافة كعملية XOR (أو الحصرية) لمعرفي العقدتين، والنتيجة عدد صحيح غير مُوَقَّع . تتشابه المفاتيح ومعرفات العقد في الشكل والطول، لذا يمكن حساب المسافة بينها بنفس الطريقة تمامًا. عادةً ما يكون معرف العقدة عددًا عشوائيًا كبيرًا يُختار ليكون فريدًا لكل عقدة (انظر UUID ). قد يحدث، بل ويحدث بالفعل، أن تكون عقد متباعدة جغرافيًا - من ألمانيا وأستراليا، على سبيل المثال - "متجاورتين" إذا اختارتا معرفات عشوائية متشابهة.

تم اختيار عملية XOR لأنها تعمل كدالة مسافة بين جميع معرّفات العقد. تحديداً:

  • المسافة بين العقدة ونفسها تساوي صفرًا
  • إنها متناظرة: "المسافات" المحسوبة من A إلى B ومن B إلى A متساوية
  • ويتبع ذلك متباينة المثلث : إذا كانت A و B و C رؤوس (نقاط) مثلث، فإن المسافة من A إلى B أقصر من (أو تساوي) مجموع المسافة من A إلى C والمسافة من C إلى B.

تكفي هذه الشروط الثلاثة لضمان أن عملية XOR تستوعب جميع السمات الأساسية والمهمة لدالة المسافة "الحقيقية"، مع كونها رخيصة وبسيطة الحساب. [ 1 ]

تقترب كل دورة بحث في خوارزمية كاديميليا خطوة واحدة من الهدف. يبلغ تعقيد خوارزمية البحث الأساسية في كاديميليا O(log 2 (n)) ، وهذا يعني أنه بالنسبة للشبكة ذات2ن{\textstyle 2^{n}}العقد التي سيأخذها على الأكثرن{\displaystyle n}خطوات للعثور على تلك العقدة.

جداول التوجيه ذات الحجم الثابت

عُرضت جداول التوجيه ذات الحجم الثابت في النسخة التمهيدية من الورقة الأصلية [ 1 ] ، وتُستخدم في النسخة اللاحقة فقط لبعض البراهين الرياضية. أما تطبيق كادمليا الفعلي، فلا يحتوي على جدول توجيه ذي حجم ثابت ، بل على جدول توجيه ذي حجم ديناميكي.

تتكون جداول توجيه كاديميليا من قائمة لكل بت من مُعرّف العقدة (على سبيل المثال، إذا كان مُعرّف العقدة يتكون من 128 بت، فستحتفظ العقدة بـ 128 قائمة من هذا النوع ). يحتوي كل إدخال في القائمة على البيانات اللازمة لتحديد موقع عقدة أخرى. عادةً ما تكون البيانات في كل إدخال عبارة عن عنوان IP ، والمنفذ ، ومُعرّف العقدة الأخرى. تتوافق كل قائمة مع مسافة محددة من العقدة. يجب أن يكون للعقد التي يمكن إدراجها في القائمة رقم n بت مختلف عن مُعرّف العقدة؛ يجب أن تتطابق أول n-1 بت من مُعرّف المرشح مع تلك الموجودة في مُعرّف العقدة. هذا يعني أنه من السهل جدًا ملء القائمة الأولى لأن نصف العقد في الشبكة هي مرشحة بعيدة. يمكن للقائمة التالية استخدام ربع العقد فقط في الشبكة (أقرب ببت واحد من الأولى)، وهكذا.

باستخدام معرف مكون من 128 بت، سيقوم كل عقدة في الشبكة بتصنيف العقد الأخرى في واحدة من 128 مسافة مختلفة، مسافة محددة واحدة لكل بت.

بمجرد اكتشاف عُقد جديدة على الشبكة، تُضاف إلى القوائم . يشمل ذلك عمليات التخزين والاسترجاع، وحتى مساعدة العُقد الأخرى في العثور على مفتاح. تُؤخذ كل عُقدة مُكتشفة بعين الاعتبار لإضافتها إلى القوائم . لذا، فإن معرفة العُقدة بالشبكة ديناميكية للغاية، مما يُبقي الشبكة مُحدّثة باستمرار ويُعزز مقاومتها للأعطال والهجمات.

في أدبيات كاديميليا، يُشار إلى القوائم باسم k-buckets . k هو رقم على مستوى النظام، مثل 20. كل k -bucket عبارة عن قائمة تحتوي على ما يصل إلى k من المدخلات في الداخل؛ أي بالنسبة لشبكة مع k=20، سيكون لكل عقدة قوائم تحتوي على ما يصل إلى 20 عقدة لبت معين (مسافة معينة من نفسها).

بما أن عدد العقد المحتملة لكل مجموعة k يتناقص بسرعة (لأن عدد العقد القريبة جدًا سيكون قليلًا جدًا)، فإن مجموعات k ذات البتات الأدنى ستغطي جميع العقد في ذلك الجزء من الشبكة. ولأن عدد المعرفات المحتملة أكبر بكثير من أي عدد ممكن من العقد، فإن بعض مجموعات k المقابلة للمسافات القصيرة جدًا ستبقى فارغة.

تقسيم الشبكة للعقدة 110

انظر إلى الشبكة البسيطة على اليمين. حجم الشبكة هو 2^3، أي ثمانية مفاتيح وعقد كحد أقصى. هناك سبع عقد مشاركة، وهي الدوائر الصغيرة في الأسفل. العقدة قيد الدراسة هي العقدة السادسة (110 ثنائيًا) باللون الأسود. يوجد ثلاثة صناديق k لكل عقدة في هذه الشبكة. العقد صفر، وواحد، واثنان (000، 001، و010 ثنائيًا) مرشحة للصندوق k الأبعد . العقدة الثالثة (111 ثنائيًا، غير موضحة) غير مشاركة في الشبكة. في الصندوق k الأوسط ، توجد العقدتان الرابعة والخامسة (100 و101 ثنائيًا). أخيرًا، لا يمكن أن يحتوي الصندوق k الثالث إلا على العقدة السابعة (111 ثنائيًا). كل صندوق من الصناديق k الثلاثة محاط بدائرة رمادية. إذا كان حجم الصندوق k هو اثنان، فإن الصندوق 2 الأبعد لا يمكن أن يحتوي إلا على عقدتين من العقد الثلاث. على سبيل المثال، إذا كان العقدة السادسة تحتوي على العقدتين الأولى والثانية في أبعد خانة ثنائية، فسيتعين عليها طلب البحث عن مُعرّف العقدة من هاتين العقدتين للعثور على موقع (عنوان IP) العقدة الصفرية. كل عقدة على دراية جيدة بمحيطها وتتصل ببعض العقد البعيدة، مما يُساعد في تحديد مواقع العقد الأخرى البعيدة.

من المعروف أن العقد المتصلة لفترة طويلة في الشبكة ستبقى متصلة على الأرجح لفترة طويلة في المستقبل. [ 5 ] [ 6 ] وبسبب هذا التوزيع الإحصائي، يختار برنامج كاديميليا العقد المتصلة لفترة طويلة للاحتفاظ بها في مجموعات k. وهذا يزيد من عدد العقد الصالحة المعروفة في وقت ما في المستقبل، مما يوفر شبكة أكثر استقرارًا.

عندما تمتلئ حاوية k-bucket ويتم اكتشاف عقدة جديدة ضمنها ، يتم إرسال طلب PING إلى العقدة الأقل ظهورًا في الحاوية . إذا تبين أن العقدة الجديدة لا تزال تعمل، تُضاف إلى قائمة ثانوية، وهي ذاكرة التخزين المؤقت للاستبدال. تُستخدم ذاكرة التخزين المؤقت للاستبدال فقط في حال توقف إحدى العقد في حاوية k - bucket عن الاستجابة. بعبارة أخرى: لا تُستخدم العقد الجديدة إلا عند اختفاء العقد القديمة.

رسائل البروتوكول

لدى كاديميليا أربع رسائل.

  • PING — يستخدم للتحقق من أن العقدة لا تزال تعمل.
  • STORE — يخزن زوجًا (مفتاح، قيمة) في عقدة واحدة.
  • FIND_NODE — سيقوم متلقي الطلب بإرجاع العقد k في مجموعاته الخاصة التي هي الأقرب إلى المفتاح المطلوب.
  • FIND_VALUE — نفس FIND_NODE، ولكن إذا كان لدى متلقي الطلب المفتاح المطلوب في مخزنه، فسوف يعيد القيمة المقابلة.

تتضمن كل رسالة RPC قيمة عشوائية من المُرسِل. وهذا يضمن أن الاستجابة عند استلامها تتوافق مع الطلب المُرسَل سابقًا (انظر ملف تعريف الارتباط السحري ).

تحديد مواقع العقد

يمكن إجراء عمليات البحث عن العقد بشكل غير متزامن. يُرمز إلى عدد عمليات البحث المتزامنة بالرمز α، وعادةً ما يكون ثلاثة. تبدأ العقدة طلب FIND_NODE بالاستعلام من العقد α الموجودة في مجموعاتها k-buckets ، وهي أقرب العقد إلى المفتاح المطلوب. عند استلام هذه العقد للطلب، تبحث في مجموعاتها k-buckets وتُعيد أقرب k عقدًا إلى المفتاح المطلوب التي تعرفها. تُحدِّث العقدة المُستقبِلة قائمة النتائج بالنتائج (معرّفات العقد) التي تستلمها، مع الاحتفاظ بأفضل k عقدة (أقرب k عقدة إلى المفتاح المطلوب) التي تستجيب للاستعلامات. ثم تختار العقدة المُستقبِلة أفضل k نتيجة وتُرسل الطلب إليها، وتُكرِّر هذه العملية مرارًا وتكرارًا. نظرًا لأن كل عقدة لديها معرفة أفضل بمحيطها من أي عقدة أخرى، فإن النتائج المُستلمة ستكون عقدًا أخرى أقرب فأقرب إلى المفتاح المطلوب. تستمر التكرارات حتى لا يتم إرجاع أي عقد أقرب من أفضل النتائج السابقة. عندما تتوقف التكرارات، فإن أفضل k عقدة في قائمة النتائج هي تلك الموجودة في الشبكة بأكملها والتي هي الأقرب إلى المفتاح المطلوب.

يمكن إضافة معلومات عن العقدة تتضمن أوقات الاستجابة (RTT). تُستخدم هذه المعلومات لتحديد مهلة زمنية خاصة بكل عقدة يتم استشارتها. عند انتهاء مهلة استعلام، يمكن بدء استعلام آخر، دون تجاوز عدد الاستعلامات المتزامنة α استعلامًا.

تحديد الموارد

يتم تحديد موقع المعلومات بربطها بمفتاح. ويُستخدم عادةً جدول تجزئة لهذا الغرض. تحتوي عقد التخزين على معلومات نتيجةً لرسالة تخزين سابقة. ويتبع تحديد موقع قيمة ما نفس إجراء تحديد أقرب العقد إلى المفتاح، باستثناء أن البحث يتوقف عندما تحتوي إحدى العقد على القيمة المطلوبة في مخزنها وتُعيدها.

تُخزَّن القيم في عدة عُقد (عددها k) للسماح للعُقد بالانضمام والمغادرة مع بقاء القيمة متاحة في إحدى العُقد. بشكل دوري، تقوم عُقدة مُخزِّنة للقيمة باستكشاف الشبكة للعثور على العُقد k القريبة من القيمة الرئيسية، ثم تُكرِّر القيمة عليها. هذا يُعوِّض عن العُقد المفقودة.

كذلك، بالنسبة للقيم الشائعة التي قد تتطلب عددًا كبيرًا من الطلبات، يتم تقليل الحمل على عقد التخزين عن طريق قيام عقدة الاسترجاع بتخزين هذه القيمة في عقدة قريبة، ولكن خارج نطاق أقرب k عقدة. يُطلق على هذا التخزين الجديد اسم ذاكرة التخزين المؤقت. وبهذه الطريقة، تُخزَّن القيمة على مسافة أبعد فأبعد عن المفتاح، اعتمادًا على عدد الطلبات. وهذا يسمح لعمليات البحث الشائعة بالعثور على عقدة التخزين بسرعة أكبر. وبما أن القيمة تُعاد من عقد أبعد عن المفتاح، فإن هذا يُخفف من احتمالية وجود "نقاط ساخنة". ستقوم عقد التخزين المؤقت بإسقاط القيمة بعد فترة زمنية معينة تعتمد على بُعدها عن المفتاح.

بعض التطبيقات (مثل Kad ) لا تتضمن خاصية النسخ المتماثل أو التخزين المؤقت. والهدف من ذلك هو إزالة المعلومات القديمة بسرعة من النظام. تقوم العقدة التي توفر الملف بتحديث المعلومات على الشبكة بشكل دوري (عن طريق تنفيذ رسائل FIND_NODE وSTORE). عندما تتوقف جميع العقد التي تحتوي على الملف عن العمل، لن يقوم أي منها بتحديث قيمه (المصادر والكلمات المفتاحية)، وبالتالي ستختفي المعلومات نهائيًا من الشبكة.

الانضمام إلى الشبكة

يجب على أي عقدة ترغب بالانضمام إلى الشبكة أن تخضع أولاً لعملية تهيئة . في هذه المرحلة، تحتاج العقدة المنضمة إلى معرفة عنوان IP ومنفذ عقدة أخرى - عقدة تهيئة (يتم الحصول عليها من المستخدم أو من قائمة مخزنة) - مشاركة بالفعل في شبكة كاديميليا. إذا لم تكن العقدة المنضمة قد شاركت في الشبكة بعد، فإنها تحسب رقم تعريف عشوائي ، والذي نظرًا لكونه رقمًا عشوائيًا كبيرًا جدًا، فمن المرجح جدًا ألا يكون قد تم تخصيصه لأي عقدة أخرى. وتستخدم هذا الرقم التعريفي حتى تغادر الشبكة.

تقوم العقدة المُنضمة بإدراج عقدة التمهيد في إحدى مجموعات k الخاصة بها . ثم تُجري العقدة المُنضمة بحثًا عن مُعرّفها الخاص مقابل عقدة التمهيد (العقدة الأخرى الوحيدة التي تعرفها). سيؤدي هذا البحث الذاتي إلى ملء مجموعات k الخاصة بالعقد الأخرى بمُعرّف العقدة الجديد، كما سيؤدي إلى ملء مجموعات k الخاصة بالعقد الموجودة في المسار بينها وبين عقدة التمهيد. بعد ذلك، تُحدّث العقدة المُنضمة جميع مجموعات k الأبعد من مجموعة k التي تقع فيها عقدة التمهيد. هذا التحديث هو مجرد بحث عن مفتاح عشوائي يقع ضمن نطاق مجموعة k تلك .

في البداية، تحتوي كل عقدة على مجموعة واحدة من العقد (k-bucket ). عندما تمتلئ هذه المجموعة ، يمكن تقسيمها. يحدث التقسيم إذا امتد نطاق العقد في المجموعة (k-bucket) ليشمل معرّف العقدة نفسها (القيم على يسارها ويمينها في شجرة ثنائية ). يُخفف Kademlia من هذه القاعدة حتى بالنسبة لمجموعة "أقرب العقد" ( k-bucket )، لأنه عادةً ما تتوافق مجموعة واحدة مع المسافة التي تفصل أقرب جميع العقد عن هذه العقدة، وقد يكون عددها أكبر من k ، ونريد أن تكون جميعها معروفة. قد يتبين وجود شجرة فرعية ثنائية غير متوازنة بالقرب من العقدة. إذا كانت قيمة k تساوي 20، وكان هناك أكثر من 21 عقدة تبدأ بالبادئة "xxx0011..."، وكانت العقدة الجديدة هي "xxx0000 11001 "، فيمكن أن تحتوي العقدة الجديدة على مجموعات متعددة (k-bucket) للعقد الأخرى (21+). هذا لضمان معرفة الشبكة بجميع العقد في المنطقة الأقرب.

عمليات بحث سريعة

تستخدم كادمليا مقياس XOR لتحديد المسافة. يتم إجراء عملية XOR بين مُعرّفَي عقدة، أو بين مُعرّف عقدة ومفتاح، والنتيجة هي المسافة بينهما. لكل بت، تُرجع دالة XOR القيمة صفر إذا كان البتّان متساويين، والقيمة واحد إذا كانا مختلفين. تُحقق المسافات في مقياس XOR متباينة المثلث : إذا كانت A وB وC رؤوسًا (نقاطًا) لمثلث، فإن المسافة من A إلى B أقصر من (أو تساوي) مجموع المسافتين من A إلى C ومن C إلى B.

تُمكّن خاصية XOR في Kademlia من توسيع جداول التوجيه لتشمل أكثر من بت واحد. يمكن وضع مجموعات البتات في مجموعات k-buckets . تُسمى مجموعة البتات بادئة. بالنسبة لبادئة مكونة من m بت ، سيكون هناك 2 ^m - 1 مجموعة k-buckets . تمثل مجموعة k-buckets المتبقية امتدادًا إضافيًا لشجرة التوجيه التي تحتوي على مُعرّف العقدة. تُقلل البادئة المكونة من m بت الحد الأقصى لعدد عمليات البحث من log 2 n إلى log 2 m n . هذه قيم قصوى ، وسيكون المتوسط ​​أقل بكثير، مما يزيد من احتمالية العثور على عقدة في مجموعة k-bucket تشترك في عدد بتات أكبر من مجرد البادئة مع المفتاح المستهدف.

يمكن للعُقد استخدام مزيج من البادئات في جدول التوجيه الخاص بها، مثل شبكة Kad المستخدمة في eMule . بل قد تكون شبكة Kademlia غير متجانسة في تطبيقات جدول التوجيه، على حساب تعقيد تحليل عمليات البحث.

الأهمية الأكاديمية

على الرغم من أن مقياس XOR ليس ضروريًا لفهم بروتوكول كاديميليا، إلا أنه بالغ الأهمية في تحليله. تشكل عملية XOR الحسابية مجموعة تبديلية تسمح بتحليل مغلق. تتطلب بروتوكولات وخوارزميات DHT الأخرى محاكاة أو تحليلًا رسميًا معقدًا للتنبؤ بسلوك الشبكة وصحتها. كما أن استخدام مجموعات البتات كمعلومات توجيه يُبسط الخوارزميات.

التحليل الرياضي للخوارزمية

لتحليل الخوارزمية، ضع في اعتبارك شبكة كاديميليا منن{\displaystyle n}العقد ذات المعرفاتx1،...،xن{\displaystyle x_{1},\ldots ,x_{n}}، كل منها عبارة عن سلسلة من الطولد{\displaystyle d}يتكون من أصفار وواحدات فقط. يمكن نمذجته على شكل شجرة بحثية ، حيث تمثل كل ورقة عقدة، ويمثل المسار المسمى من الجذر إلى الورقة معرفها. بالنسبة للعقدةx∈{x1،...،xن}{\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}، يتركدأنا(x){\displaystyle {\mathcal {D}}_{i}(x)}لتكن مجموعة العقد (المعرفات) التي تشترك في بادئة معx{\displaystyle x}من الطولد-أنا{\displaystyle di}ثم ملءأنا{\displaystyle i}دلو رقم - منx{\displaystyle x}يمكن نمذجة ذلك على أنه إضافة مؤشرات من الورقةx{\displaystyle x}لك{\displaystyle k}أوراق (معرفات) مختارة عشوائيًا وبشكل متساوٍ مندأنا(x){\displaystyle {\mathcal {D}}_{i}(x)}وبالتالي يمكن اعتبار التوجيه بمثابة القفز بين الأوراق على طول هذه المؤشرات بحيث تتجه كل خطوة نحو معرف الهدف قدر الإمكان، أي بطريقة جشعة.

يتركتيxy{\displaystyle T_{xy}}عدد القفزات اللازمة للانتقال من الورقةx{\displaystyle x}إلى معرّف الهدفy{\displaystyle y}بافتراض أنx1،...،xن{\displaystyle x_{1},\ldots ,x_{n}}يتم اختيارها بشكل حتمي من{0،1}د{\displaystyle \{0,1\}^{d}}لقد ثبت أن

رشفةx1،...،xنرشفةx∈{x1،...،xن}رشفةy∈{0،1}دهـ[تيxy]≤(1+o(1))سجل⁡نحك،{\displaystyle \sup _{x_{1},\ldots ,x_{n}}\,\sup _{x\in \{x_{1},\ldots ,x_{n}\}}\,\sup _{y\in \{0,1\}^{d}}\mathbb {E} [T_{xy}]\leq (1+o(1)){\frac {\log n}{H_{k}}},}

أينحك{\displaystyle H_{k}}هوك{\displaystyle k}رقم التوافقي رقم . بما أنحك/سجل⁡ك→1{\displaystyle H_{k}/\log k\to 1}مثلك→∞{\displaystyle k\to \infty }، متىك{\displaystyle k}كبيرهـتيxy{\displaystyle \mathbb {E} T_{xy}}يحدها من الأعلى حواليسجلك⁡ن{\displaystyle \log _{k}n}ومع ذلك، يتم اختيار المعرفات والهدف. [ 7 ] وهذا يبرر الحدس القائل بأنه في كاديميليا فقطيا(سجل⁡ن){\displaystyle O(\log n)}يتم الاتصال بالعقد في عملية البحث عن العقدة المستهدفة.

لجعل النموذج أقرب إلى شبكات كاديميليا الحقيقية،x1،...،xن{\displaystyle x_{1},\ldots ,x_{n}}ويمكن أيضاً افتراض أنه يتم اختيارها بشكل عشوائي منتظم دون إرجاع من{0،1}د{\displaystyle \{0,1\}^{d}}ثم يمكن إثبات ذلك لجميعx∈{x1،...،xن}{\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}وy∈{0،1}د{\displaystyle y\in \{0,1\}^{d}}،

تيxy→صسجل⁡نجك،هـ[تيxy]→سجل⁡نجك،{\displaystyle {\begin{aligned}&T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}},\\&\mathbb {E} [T_{xy}]\to {\frac {\log n}{c_{k}}},\end{aligned}}}

أينجك{\displaystyle c_{k}}ثابت يعتمد فقط علىك{\displaystyle k}معجك/حك→1{\displaystyle c_{k}/H_{k}\to 1}مثلك→∞{\displaystyle k\to \infty }وهكذا بالنسبة لـك{\displaystyle k}كبير،هـتيxy/سجلك⁡ن{\displaystyle \mathbb {E} T_{xy}/\log _{k}n}يتقارب إلى إغلاق ثابت1{\displaystyle 1}وهذا يعني أن عدد العقد التي يجب الاتصال بها للبحث عن عقدة مستهدفة هو في الواقعΘ(سجل⁡ن){\displaystyle \Theta (\log n)}في المتوسط. [ 8 ]

يُستخدم في شبكات مشاركة الملفات

تُستخدم خوارزمية كادمليا في شبكات مشاركة الملفات . من خلال البحث باستخدام الكلمات المفتاحية في كادمليا، يمكن العثور على معلومات في شبكة مشاركة الملفات لتنزيلها. ولعدم وجود قاعدة بيانات مركزية لتخزين فهرس الملفات الموجودة، تُوزّع هذه المهمة بالتساوي بين جميع العملاء: إذا أرادت عقدة مشاركة ملف، فإنها تُعالج محتويات الملف، وتحسب منه رقمًا ( تجزئة ) يُعرّف هذا الملف داخل شبكة مشاركة الملفات. ولأن تجزئات الملفات ومعرّفات العقد لها نفس الطول، يمكن للعميل استخدام دالة مسافة XOR للبحث عن عدة عقد يكون معرّفها قريبًا من التجزئة، وتوجيه هذه العقد لتخزين عنوان IP الخاص بالناشر بطريقة مُحددة في التنفيذ. وبالتالي، ستمتلك العقد ذات المعرّفات الأقرب إلى تجزئة الملف قائمة بعناوين IP الخاصة بنظرائها/ناشري هذا الملف، والتي يمكن للعميل من خلالها تنزيل الملف بطريقة مُحددة في التنفيذ.

لا يحتاج العملاء الراغبون في تنزيل الملف من هذا الناشر إلى معرفة عنوان IP الخاص به (إذ قد يكون هناك العديد من الناشرين)، بل يكفيهم معرفة تجزئة الملف. سيستخدم العميل الباحث خوارزمية Kademlia للبحث في الشبكة عن العقدة التي يكون معرّفها الأقرب إلى تجزئة الملف، ثم يسترجع قائمة المصادر المخزنة في تلك العقدة.

بما أن المفتاح الواحد قد يرتبط بالعديد من القيم، مثل مصادر متعددة لنفس الملف، فقد تحتوي كل عقدة تخزين على معلومات مختلفة. بعد ذلك، يتم طلب المصادر من جميع العقد k القريبة من المفتاح، حيث k هو حجم الحاوية.

عادة ما يتم الحصول على تجزئة الملف من رابط مغناطيسي خاص بالإنترنت موجود في مكان آخر، أو يتم تضمينه داخل ملف فهرسة تم الحصول عليه من مصادر أخرى.

تُنفَّذ عمليات البحث عن أسماء الملفات باستخدام الكلمات المفتاحية . يُقسَّم اسم الملف إلى كلماته المكونة له. تُشفَّر كل كلمة مفتاحية وتُخزَّن في الشبكة، مع اسم الملف ورمز التجزئة الخاص به. تتضمن عملية البحث اختيار إحدى الكلمات المفتاحية، والاتصال بالعقدة التي تحمل المعرِّف الأقرب إلى رمز التجزئة الخاص بتلك الكلمة المفتاحية، واسترجاع قائمة أسماء الملفات التي تحتوي على الكلمة المفتاحية. وبما أن كل اسم ملف في القائمة مُرفق به رمز التجزئة الخاص به، يُمكن الحصول على الملف المُختار بالطريقة المعتادة.

التطبيقات

الشبكات

الشبكات العامة التي تستخدم خوارزمية كاديميليا (هذه الشبكات غير متوافقة مع بعضها البعض):

  • I2P : طبقة شبكة تراكبية مجهولة الهوية . [ 9 ]
  • شبكة Kad : تم تطويرها في الأصل من قبل مجتمع eMule لاستبدال البنية القائمة على الخادم لشبكة eDonkey .
  • إيثيريوم : يعتمد بروتوكول اكتشاف العقد في بنية شبكة سلسلة كتل إيثيريوم على تطبيق مُعدَّل لبروتوكول كاديميليا. لا يستخدم هذا البروتوكول جزء القيمة، ويعتمد على التحقق المتبادل من نقاط النهاية، ويتيح العثور على جميع العقد ضمن مسافة لوغاريتمية محددة، كما يتميز بتمييز البروتوكولات الفرعية. [ 10 ]
  • أوفيرنت : مع كادك، تتوفر مكتبة C للتعامل مع كادمليا الخاصة به. (تم إيقاف تطوير أوفيرنت)
  • Mainline DHT : عبارة عن DHT لـ BitTorrent يعتمد على تطبيق خوارزمية Kademlia، لملفات التورنت بدون متتبع.
  • أوزيريس (جميع الإصدارات): يستخدم لإدارة بوابة الويب الموزعة والمجهولة.
  • ريتروشير : منصة اتصالات لامركزية وجهاً لوجه مع بروتوكول نقل الصوت عبر الإنترنت الآمن، والمراسلة الفورية، ونقل الملفات، إلخ.
  • توكس : منصة مراسلة ومكالمات صوتية عبر الإنترنت ومحادثات فيديو موزعة بالكامل
  • Gnutella DHT: طُوِّرت في الأصل بواسطة LimeWire [ 11 ] [ 12 ] لتعزيز بروتوكول Gnutella للعثور على مواقع ملفات بديلة، وهي تُستخدم الآن بواسطة عملاء Gnutella آخرين. [ 13 ]
  • IPFS : نظام ملفات موزع من نظير إلى نظير يعتمد على libp2p . [ 14 ]
  • TeleHash : بروتوكول شبكة متداخلة يستخدم Kademlia لحل الاتصالات المباشرة بين الأطراف. [ 15 ]
  • iMule: برنامج مساعد لمشاركة الملفات عبر بروتوكول I2P .
  • OpenDHT : مكتبة توفر تطبيقًا لـ Kademlia، يستخدمها جامي وآخرون. [ 16 ]
  • GNUnet : حزمة شبكية بديلة لبناء تطبيقات موزعة آمنة ولا مركزية وتحافظ على الخصوصية. تستخدم نسخة عشوائية من Kademlia تسمى R5N. [ 17 ]
  • Dat : أداة لمشاركة الملفات من نظير إلى نظير تعتمد على بروتوكول Hypercore. [ 18 ]

انظر أيضاً

مراجع

  1. 1 2 3 ميمونكوف، بيتار؛ مازيريس، ديفيد. “Kademlia: نظام معلومات نظير إلى نظير يعتمد على مقياس XOR” (PDF) . pdos.csail.mit.edu . تم الاسترجاع بتاريخ 28-12-2023 .
  2. ^ "أوراق لديفيد مازيير" . www.scs.stanford.edu .
  3. ↑ "قاعدة بيانات الشبكة - I2P" . geti2p.net .
  4. ↑ مايمونكوف، بيتر (17 مارس 2013). "كادمليا - أكبر إسهاماتي على الإطلاق" . مؤرشف من الأصل في 22 مارس 2013.
  5. ↑ ستيفان سارويو، بي. كريشنا غومادي، وستيفن دي. غريبل. دراسة قياس لأنظمة مشاركة الملفات من نظير إلى نظير. تقرير فني UW-CSE-01-06-02، جامعة واشنطن، قسم علوم وهندسة الحاسوب، يوليو 2001.
  6. ↑ دانيال ستوتزباخ ورضا رجائي. فهم معدل التوقف في شبكات الند للند، القسم 5.5 إمكانية التنبؤ بوقت التشغيل، مؤتمر قياس الإنترنت، ريو دي جانيرو، أكتوبر 2006.
  7. ↑ كاي، إكس إس؛ ديفروي، إل. (2013). "تحليل احتمالي لشبكات كاديميليا". الخوارزميات والحوسبة . سلسلة محاضرات في علوم الحاسوب. المجلد 8283. الصفحات 711-721 . arXiv : 1309.5866 . doi : 10.1007/978-3-642-45030-3_66 . ISBN   978-3-642-45029-7. S2CID 6068991 . 
  8. ↑ كاي، شينغ شي؛ ديفروي، لوك (2015). "تحليل خوارزمية كاديميليا للمعرفات العشوائية". رياضيات الإنترنت . 11 (6): 1-16 . arXiv : 1402.1191 . doi : 10.1080/15427951.2015.1051674 . ISSN 1542-7951 . S2CID 16547375 .  
  9. ↑ "مقدمة - I2P" . geti2p.net .
  10. ↑ "من كاديميليا إلى ديسكوفر 5" . 20 يناير 2025 - عبر جيت هاب.
  11. ↑ "أخبار Slyck - برنامج LimeWire يستعيد صدارة Download.com" . www.slyck.com . مؤرشف من الأصل بتاريخ 19 يناير 2019. تم الاطلاع عليه بتاريخ 20 يونيو 2007 .
  12. ↑ "موجيتو - لايم واير" . wiki.limewire.org . مؤرشف من الأصل في 17 فبراير 2009.
  13. ↑ "سجل تغييرات Gtk-gnutella" . sourceforge.net . مؤرشف من الأصل بتاريخ 23 يوليو 2011. تم الاطلاع عليه بتاريخ 23 يناير 2010 .
  14. ↑ "ورقة بحثية حول نظام الملفات الدولي المتكامل" (ملف PDF) . GitHub .
  15. ↑ "#7: جيريمي ميلر - تيلي هاش" . تم الاطلاع عليه بتاريخ 12-03-2016 .
  16. ^ "الصفحة الرئيسية" . أوبن دي إتش تي ويكي. جيثب . براعة لينكس . تم الاسترجاع 2021-03-19 .
  17. ↑ "R5N: التوجيه المتكرر العشوائي لشبكات المسارات المقيدة" (PDF) .
  18. ↑ "بروتوكول هايبركور" . مؤرشف من الأصل بتاريخ 23-12-2020 . تم الاطلاع عليه بتاريخ 27-12-2020 .