נדמיין מוכרת ברשת מזון מהיר שבמקום לקרוא ללקוחות בשמם במערכת הכריזה כשההזמנה מוכנה, היא נוקבת בתאריך יום ההולדת שלהם: "זה שיום הולדתו ב-1 באפריל, הארוחה שלך מוכנה!" מה יקרה במסעדה הזו? הסיפור הזה קשור לבעיה מתמטית ידועה, וכעת נחבר אותו גם לרשת מחשבים באתרנט.

כתבו: מיקי גוטמן ידיד העמותה, ודורון אורנשטיין

בפוסט קודם [1] סיפרנו כיצד התפתחה רשת האתרנט לרשת מקומית המבוססת על מתגים (switches). תפקיד המתג הוא לנתב הודעות במהירות וביעילות, למשל מהמחשב שחיברנו לשקע במשרד ליעד המתאים ברשת. כיצד הוא עושה זאת?

מחשבים, כמו גם התקנים אחרים המחוברים לרשת, מדברים אלו עם אלו באמצעות שליחת הודעות המכילות את כתובת הנמען. לפי התקן, כל מכשיר המיועד להתחבר לרשת אתרנט או לאחיותיה, קווית או אלחוטית (למשל WiFi), מקבל מיצרן התקשורת מספר סידורי ייחודי השמור בתוכו כמו טביעת אצבע, ונקרא כתובת MAC (באנגלית: Media Access Control, [2]). אחת התכונות המוצלחות של האתרנט היא הגודל שהוא מקצה למספר זה, 48 סיביות, ובכך מאפשר לייצר בערך 281 טריליון כתובות שונות. זהו מספר עצום שיאפשר לספק כתובות ייחודיות עד שנת 2080.

ברגע שחיברנו את המחשב באמצעות כבל אתרנט לשער (port), המתג לומד ושומר בזיכרונו את הקישור בין מספר השער לכתובת MAC. למשל: "המחשב שכתובת ה-MAC שלו (לפי בסיס 16) היא DC-1B-A1-99-87-F8 התחבר לשער 23 של המתג". נניח שהתקבלה הודעה עבור כתובת זו. כיצד מצליח המתג לפשפש בזיכרונו ולמצוא במהירות לאיזה שער לנתב אותה?

השיטה המהירה היא שימוש בטבלה המכילה שורה עבור כל כתובת MAC אפשרית. אולם טבלה כזאת תתפוס שטח זיכרון עצום, ולכן אי אפשר לבנות אותה. שיטה אחרת היא לעבור על על רשימת כל השערים בזיכרון, ולהשוות את כל הכתובות שבה לכתובת שבהודעה (למשל: לבדוק אם הכתובת זהה לכתובת של שער 0, אם לא - לבדוק עבור שער 1, וכן הלאה), אולם השיטה איטית מדי.

השיטה הנפוצה לפתרון בעיות כאלו במערכות תקשורת ובעולם המחשבים היא באמצעות טבלת גיבוב (hash table) המאפשרת לטייב את זמן החיפוש ואת גודל הטבלה [3]. לשם כך משתמשים בפונקציה שנקראת פונקציית גיבוב – hash function המתרגמת את כתובת ה-MAC למספר קטן יותר, המשמש אינדקס לטבלה קטנה (hash table). 

דוגמה לפונקציה: נחלק את כתובת ה-MAC ב-365, ונקבל שארית. כיוון שהשארית היא מספר בין 0 ל-364, היא יכולה לשמש כאינדקס בטבלה עם 365 שורות. למשל, אם השארית עבור הכתובת בדוגמה היא 314, נרצה להכניס בשורה 314 שבטבלה את מספר השער (23). הבעיה היא שייתכנו כפילויות: כתובות של מחשבים שונים יכולות להגיע לאותה שורה, אם החלוקה מניבה אותה שארית. כשמגלים מקרה כזה, שומרים בצד את רשימת הכתובות שגרמו לכפילות וסורקים אותה לאט יותר (ראו תמונה).

עד כמה נפוצות הכפילויות? נניח שיש 35 עובדים במשרד המחוברים לאתרנט. מה הסיכוי שיהיו כפילויות בטבלת הגיבוב שבדוגמה? אם נניח שהכתובות אקראיות יחסית, השאלה שקולה לחידה ידועה: מה הסיכוי שיהיו בין 35 העובדים שניים שחוגגים יום הולדת באותו יום? חידה זו נקראת "פרדוקס יום ההולדת", כי היא די מפתיעה: עצרו ונסו לנחש את התשובה.

אף שמספר העובדים קטן מעשירית ממספר האפשרויות (365), החישוב מראה שסיכוי שיהיה זוג כזה גדול מ-80%! (ראו ניתוח ב-[4], וכתבה מעולה של גדי אלכסנדרוביץ בנושא [5]). מי שמבלה ברשתות חברתיות ודואג לברך את כל חבריו ברשת בברכת מזל טוב ליום הולדתם, ודאי נתקל בימים עמוסים במיוחד שבהם חל יותר מיום הולדת אחד…

נחזור למוכרת שהחליטה לקרוא לאנשים כשההזמנה מוכנה לפי תאריך יום ההולדת שלהם: "זה שיום הולדתו ב-1 באפריל, הארוחה שלך מוכנה". אם יש 35 לקוחות במסעדה, יש סיכוי גבוה מ-80% שבשלב מסוים יהיו שניים או יותר סועדים שיזנקו לדלפק בבת אחת ויתקוטטו. במקרה זה תצטרך המוכרת לבדוק את פירוט ההזמנות (כתובת ה-MAC) ולעבור עליהן אחת אחת כדי לברר מי מהם זכה, בדיקה שתימשך זמן רב יותר, כמו בדוגמה שלנו על רשת האתרנט.

אכן, כפילויות בטבלת הגיבוב הן שכיחות, והשאלה היא עד כמה, ומה השפעתן על הביצועים. כדי לנתח זאת צריך לבדוק את ההתפלגות של הכפילויות ביחס לגודל הטבלה. אפשר להשתמש בניתוח הסתברויות ובכלים פשוטים כמו אקסל כדי לבדוק זאת ([6], [7], [8], [9]). וזו דוגמה נוספת לבעיה מתמטית נחמדה מעולם ההנדסה!

עריכה: שיר רוזנבלום-מן

מקורות לקריאה נוספת:

[1] מדע גדול, בקטנה, פוסט על לידתה של רשת האתרנט

[2] ויקיפדיה, MAC Address

[3] ויקיפדיה, Hash Table

[4] חידת יום ההולדת

[5] פרדוקס יום ההולדת 

[6] מאמר על הסתברויות בגיבוב, Probability in Hashing

[7] אורך שורה בטבלת גיבוב

[8] ויקיפדיה, התפלגות בינומית

[9] הגיע זמן חינוך, כתבה על אקסל