פרוטוקול ALOHA

פרוטוקול ALOHA הוא פרוטוקול תקשורת מחשבים שפותח על ידי נורמן אברמסון בשנת 1970 באוניברסיטת הוואי. פרוטוקול זה מציע דרך ייחודית בפשטותה לאפשר למספר משתמשים במקביל להשתמש בערוץ תקשורת משותף. עקרונותיו של ALOHA מהווים בסיס לפרוטוקול ה-Ethernet הנמצא בשימוש רחב כיום. הפרוטוקול נמצא גם בשימוש ברשתות תקשורת סלולרית.

רקע היסטורי

בשנת 1970, ביחד עם עמיתיו באוניברסיטת הוואי, נורמן אברמסון הגה שיטה חדשה לפתור את בעיית הערוץ המשותף. פרוטוקול ALOHA שימש בבניית רשת מחשבים אלחוטית, מבוססת חבילות הראשונה בעולם. שיטת ALOHA סימנה התפתחות משמעותית בהנדסת תקשורת אלחוטית ובהנדסת רשתות תקשורת. בעקבות עבודה זו, אברמסון קיבל בשנת 2007 את מדליית אלכסנדר גראם בל מארגון IEEE (המכון למהנדסי חשמל ואלקטרוניקה) "על תרומתו בפיתוח רשתות מחשבים מודרניות"

הפרוטוקול

פרוטוקול ALOHA הוא פרוטוקול תקשורת עבור שכבה שנייה (שכבת הקו) במודל שבע השכבות לתקשורת (מודל OSI). הפרוטוקול מתאר דרך להעביר מידע בצורת מסגרות על ערוץ תקשורת משותף למספר לקוחות. פרוטוקול אשר מאפשר למספר לקוחות לגשת לערוץ תקשורת משותף מכונה פרוטוקול גישה מרובה (Multiple Access protocol). הרעיון הכללי מאחורי ALOHA הוא פשוט: כל משתמש יכול לשדר על הערוץ מתי שהוא חפץ. במידה ויש התנגשות, המסגרות ששודרו נהרסו ויש לשדרם שנית במועד מאוחר יותר. מועד השידור החוזר נקבע בצורה אקראית כדי למנוע התנגשויות חוזרות. התנגשויות ניתנות לגילוי לאחר השידור, מאחר שכל התחנות מאזינות אחת לשנייה. בנוסף, מניחים שהערוץ נטול רעשים, כלומר נפילת חבילה מתרחשת רק בעקבות התנגשות עם חבילה אחרת.

ניתוח ביצועים

בכל פעם שלשתי מסגרות יש חפיפה בזמן השידור על הערוץ, תהיה התנגשות. למעשה, בהינתן שתי הודעות שמשודרות, מספיק שרק הביט האחרון של ההודעה הראשונה יתנגש עם הביט הראשון של ההודעה השנייה כדי ליצור התנגשות. עובדה זו יכולה לגרום לכמות גדולה מאוד של התנגשויות החל מעומס מסוים בכמות השליחות מלקוחות. השאלה הנשאלת אם כך היא: מה היא הנצילות שהפרוטוקול יכול לספק? נצילות הערוץ מוגדרת כיחס בין כמות המידע שהועברה (או גודל כל המסגרות שעברו בהצלחה, בביטים) לבין קצב השידור (או כמות הביטים הכוללת שעברה בערוץ). בוצע ניתוח של נצילות הערוץ עבור מופע הודעות חדשות פואסוני בקצב λ הודעות לשנייה, הגורר קצב הופעת הודעות בערוץ (כולל שליחות חוזרות) g, עבור אורך הודעה ממוצע T שניות ועבור הסתברות הצלחת שליחת הודעה $P\ =e^{-2gT}\$ . ניתוח זה מעלה נצילות: $S\ =gTe^{-2gT}\$ מה שגורר נצילות מקסימלית של 18%. זוהי נצילות מקסימלית נמוכה למדי, ברור שעבור ערוץ עמוס יחסית הפרוטוקול נידון לחוסר יציבות, מספר רב של שידורים חוזרים ותעבורה נמוכה. חרף כך, נצילות עשויה להספיק ואכן מספיקה, לאפליקציות רבות.

ALOHA מחורץ

בעקבות פרוטוקול ALOHA המקורי, עוצבו במשך השנים פרוטוקולים מבוססי ALOHA נוספים (Slotted ALOHA,‏ CSMA ועוד) לכן ניתן לומר שכיום ALOHA למעשה מייצג משפחה של פרוטוקולים. בשנת 1972, הוצעה שיטה להכפיל את נצילות פרוטוקול ALOHA המקורי [Roberts,1972].‏ ALOHA מחורץ הוא פרוטוקול אשר מבוסס על הפרוטוקול שראינו, בהבדל אחד. במטרה להגדיל את נצילות הערוץ ולחסוך שידורים חוזרים, מוסיפים ל-ALOHA מנגנון סנכרון. סנכרון זה פירושו שצרכן יכול לשדר הודעה רק בזמנים מסוימים, במרחקים קבועים ושווים (רק בחריצים). עקב סנכרון זה נמנעות התנגשויות רבות ותפוקת הערוץ עולה משמעותית ממה שראינו ב-ALOHA הקלאסי, כי עכשיו הודעה שמגיעה לשידור תחכה עד להגעה לחריץ הבא ולא תתנגש בהודעות המשודרות בחריץ הנוכחי. הפעם: $S\ =gTe^{-gT}\$ , מה שגורר נצילות מקסימלית של 37%. יש לציין שמנגנון הסנכרון איננו טריוויאלי ועשוי להוות מכשול אמיתי בהשגת התוצאות הללו במימוש הפרוטוקול על גבי מרחקים ארוכים.

ראו גם

קישורים חיצוניים

מדיה וקבצים בנושא פרוטוקול ALOHA בוויקישיתוף

Computer Networks, Andrew S.Tanenbaum
IEEE Alexander Graham Bell Medal Recipients 2007 - Norman Abramson, באתר IEEE
Norman Abramson ,‏ Aloha to the Web, באתר HICSS
פרוטוקול ALOHA, באתר Laynetworks