קדמליה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Incomplete-document-purple.svg יש להשלים ערך זה: בערך זה חסר תוכן מהותי. ייתכן שתמצאו פירוט בדף השיחה.
הנכם מוזמנים להשלים את החלקים החסרים ולהסיר הודעה זו. שקלו ליצור כותרות לפרקים הדורשים השלמה, ולהעביר את התבנית אליהם.

קדמליה (מלועזית: Kademlia, ובקיצור: Kad) היא טבלת גיבוב מבוזרת (Districuted Hash table, DHT) מדור שלישי, המשמשת ברשתות P2P שהומצאה על ידי Petar Maymounkov ו-David Mazières[1].

פונקציית הגיבוב ופונקציית המרחק[עריכת קוד מקור | עריכה]

בקדמליה ממופים כל הערכים המאוחסנים בעזרת פונקציית הגיבוב SHA-1, הנותנת לכל ערך מפתח בן 160 בתים. פונקציית המרחק היא בין שני מפתחות היא פונקציית XOR, כך נוצר מרחב חיפוש בו ניתן למקם את כל הערכים ולתאר את המרחקים ביניהם לפי מרחקי המפתחות.
בנוסף, ממופים כל הצמתים ברשת לפי אותן פונקציות גיבוב ומרחק ואותו מרחב בן 160 הבתים מכיל הן את הערכים והן את המשתתפים ברשת

משך החיפוש בקדמליה יחסי ל-log(n), כאשר n הוא מספר החברים ברשת.

שימוש טיפוסי[עריכת קוד מקור | עריכה]

השימוש הנפוץ ביותר ברשת הוא לצורך שיתוף קבצים, בדוגמה הבאה מודגם חיפוש אחר קובץ ברשת:

  1. מחשב המחובר לרשת מעוניין למצוא קובץ בשם XXX.
  2. המחשב המחפש מפעיל את פונקציית הגיבוב על השם XXX ומקבל YYY, ערך בן 128 ביט.
  3. המחפש מאתר בעזרת טבלת הניתוב (ראו בהמשך) את הדרך לעמית (Peer) האחראי על הערך YYY, בתהליך זה יש לכל היותר log(n) שלבים ברשת בת n עמיתים.
  4. המחשב האחראי על הערך YYY (זה שיש לו מזהה הקרוב ביותר ל-YYY) מדווח למחפש על רשימת המחשבים שדיווחו לו על כך שהם מכילים את הקובץ XXX.
  5. המחפש פונה אל כל איברי הרשימה ונרשם אצלם בתור להורדת הקובץ.

טבלת ניתוב[עריכת קוד מקור | עריכה]

הניתוב בקדמליה הוא הדרגתי, כל צומת (node) ברשת מעביר למחפש את הכתובת אל הצומת הבא. מפני שכל צומת מחזיק מידע מאוד מפורט על המתחם הקרוב אליו במרחב החיפוש ומידע דליל יותר על החלקים המרוחקים יותר, ה"קפיצות" אותן מבצע המחפש הן בצעדים שהולכים ומתקצרים (מבחינת המרחק בין ערכי פונקציית הגיבוב) וכך מובטח החיפוש בן log(n) שלבים לכל היותר.

מימושים עיקריים[עריכת קוד מקור | עריכה]

את הפרוטוקול מממשת התוכנה הפופולרית eMule, שהיא המחליפה של eDonkey ותוכנות P2P נוספות משתמשות בו.

הערות שוליים[עריכת קוד מקור | עריכה]