פרוטוקול ALOHA
פעולות נוספות
פרוטוקול ALOHA הוא פרוטוקול תקשורת מחשבים שפותח על ידי נורמן אברמסון בשנת 1970 באוניברסיטת הוואי. פרוטוקול זה מציע דרך ייחודית בפשטותה לאפשר למספר משתמשים במקביל להשתמש בערוץ תקשורת משותף. עקרונותיו של ALOHA מהווים בסיס לפרוטוקול ה-Ethernet הנמצא בשימוש רחב כיום. הפרוטוקול נמצא גם בשימוש ברשתות תקשורת סלולרית.
רקע היסטורי עריכה
בשנת 1970, ביחד עם עמיתיו באוניברסיטת הוואי, נורמן אברמסון הגה שיטה חדשה לפתור את בעיית הערוץ המשותף. פרוטוקול ALOHA שימש בבניית רשת מחשבים אלחוטית, מבוססת חבילות הראשונה בעולם. שיטת ALOHA סימנה התפתחות משמעותית בהנדסת תקשורת אלחוטית ובהנדסת רשתות תקשורת. בעקבות עבודה זו, אברמסון קיבל בשנת 2007 את מדליית אלכסנדר גראם בל מארגון IEEE (המכון למהנדסי חשמל ואלקטרוניקה) "על תרומתו בפיתוח רשתות מחשבים מודרניות"
הפרוטוקול עריכה
פרוטוקול ALOHA הוא פרוטוקול תקשורת עבור שכבה שנייה (שכבת הקו) במודל שבע השכבות לתקשורת (מודל OSI). הפרוטוקול מתאר דרך להעביר מידע בצורת מסגרות על ערוץ תקשורת משותף למספר לקוחות. פרוטוקול אשר מאפשר למספר לקוחות לגשת לערוץ תקשורת משותף מכונה פרוטוקול גישה מרובה (Multiple Access protocol). הרעיון הכללי מאחורי ALOHA הוא פשוט: כל משתמש יכול לשדר על הערוץ מתי שהוא חפץ. אם יש התנגשות, המסגרות ששודרו נהרסו ויש לשדרם שנית במועד מאוחר יותר. מועד השידור החוזר נקבע בצורה אקראית כדי למנוע התנגשויות חוזרות. התנגשויות ניתנות לגילוי לאחר השידור, מאחר שכל התחנות מאזינות אחת לשנייה. בנוסף, מניחים שהערוץ נטול רעשים, כלומר נפילת חבילה מתרחשת רק בעקבות התנגשות עם חבילה אחרת.
ניתוח ביצועים עריכה
בכל פעם שלשתי מסגרות יש חפיפה בזמן השידור על הערוץ, תהיה התנגשות. למעשה, בהינתן שתי הודעות שמשודרות, מספיק שרק הביט האחרון של ההודעה הראשונה יתנגש עם הביט הראשון של ההודעה השנייה כדי ליצור התנגשות. עובדה זו יכולה לגרום לכמות גדולה מאוד של התנגשויות החל מעומס מסוים בכמות השליחות מלקוחות. השאלה הנשאלת אם כך היא: מה היא הנצילות שהפרוטוקול יכול לספק?
נצילות הערוץ מוגדרת כיחס בין כמות המידע שהועברה (או גודל כל המסגרות שעברו בהצלחה, בביטים) לבין קצב השידור (או כמות הביטים הכוללת שעברה בערוץ).
בוצע ניתוח של נצילות הערוץ עבור מופע הודעות חדשות פואסוני בקצב λ הודעות לשנייה, הגורר קצב הופעת הודעות בערוץ (כולל שליחות חוזרות) g, עבור אורך הודעה ממוצע T שניות ועבור הסתברות הצלחת שליחת הודעה <math> P\ = e^{-2gT}\ </math>. ניתוח זה מעלה שהנצילות היא:
- <math> S\ = gTe^{-2gT}\ </math> – מה שגורר נצילות מקסימלית של 18%.
זוהי נצילות מקסימלית נמוכה למדי – עבור ערוץ עמוס יחסית הפרוטוקול נידון לחוסר יציבות, מספר רב של שידורים חוזרים ותעבורה נמוכה. אף על פי כן, נצילות עשויה להספיק, ואכן מספיקה, ליישומים רבים.
ALOHA מחורץ עריכה
בעקבות פרוטוקול ALOHA המקורי, תוכננו במשך השנים פרוטוקולים מבוססי ALOHA נוספים (Slotted ALOHA, CSMA ועוד). לכן כיום ALOHA מייצג משפחה של פרוטוקולים. בשנת 1972 הוצעה שיטה להכפיל את נצילות פרוטוקול ALOHA המקורי.
ALOHA מחורץ הוא פרוטוקול אשר מבוסס על הפרוטוקול המתואר לעיל, בהבדל אחד. במטרה להגדיל את נצילות הערוץ ולחסוך שידורים חוזרים, מוסיפים ל-ALOHA מנגנון סנכרון. סנכרון זה פירושו שצרכן יכול לשדר הודעה רק בזמנים מסוימים, במרחקים קבועים ושווים – "חריצי זמן". עקב סנכרון זה נמנעות התנגשויות רבות ותפוקת הערוץ עולה משמעותית מ-ALOHA הקלאסי, כי הודעה שמגיעה לשידור תחכה עד להגעה לחריץ הבא ולא תתנגש בהודעות המשודרות בחריץ הנוכחי.
ב־ALOHA מחורץ הנצילות היא:
- <math> S\ = gTe^{-gT}\ </math> – מה שגורר נצילות מקסימלית של כ-37%.
מנגנון הסנכרון איננו טריוויאלי והוא עשוי להיות מכשול אמיתי בהשגת התוצאות הללו במימוש הפרוטוקול על גבי מרחקים ארוכים.
ראו גם עריכה
קישורים חיצוניים עריכה
- Computer Networks, Andrew S.Tanenbaum
- IEEE Alexander Graham Bell Medal Recipients 2007 - Norman Abramson, באתר IEEE
- Norman Abramson , Aloha to the Web, באתר HICSS
- פרוטוקול ALOHA, באתר Laynetworks