אלגוריתם עדכון כפול מפוזר

לפני שתתחיל לקרוא את המאמר הזה, אנו מייעצים לך להכיר את החומר על חישוב השביל על פי אלגוריתם בלמן פורד.

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

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

מאז כפול תוכנן כמו אלגוריתם מבוזר, עדיף לתאר את עבודתו ברשת. למטרה זו, נעשה שימוש בדמויות 8 ו -9. כדי להסביר כפול, דוגמה זו תועבר בזרם של שלוש יעדים, ולאחר מכן שינויים מעובדים במצב הזמינות עבור אותם פריטי יעד. בדוגמה הראשונה, המקרה ייחשב כאשר יש נתיב חלופי, אבל אין שכן במורד הזרם, השני ישקול את המקרה כאשר יש נתיב חלופי ושכן במורד הזרם.

באיור 8, ללמוד D מנקודת המבט:

1. A לומד שתי דרכים D:

1. A לא יזהה את הנתיב באמצעות B, כי B משתמשת יורשו:
2. A משווה את השבילים הזמינים ובוחר את הנתיב הקצר ביותר ללא לולאות:
3. בודק את השבילים הנותרים כדי לקבוע אם יש את כל השכנים במורד הזרם:

A יודע את זה כי C מכריזה על המסלול D עם מטרי המקומי שלה שווה ל 3.

שומרת על מטרי מקומי בלוח הטופולוגיה שלה.

כתוצאה מכך, A יודע את הערך המקומי ב- C ואת הערך המקומי ב- A.

1. 3 (עלות ב C) = 3 (עלות ב א), כך נתיב זה עשוי להיות לולאה, ולכן, C אינו מספק את מצב היתכנות. ג 'לא מסומן כמו שכנים במורד הזרם.

שכנים במורד הזרם כפול נקראים יורשים אפשריים. נניח שהערוץ [A, H] אינו פועל. כפול אינו מסתמך על עדכונים תקופתיים, כך שלא יכול רק לחכות עדכון נוסף עם מידע אמין. במקום זאת, חייב לפעול באופן פעיל בדרך חלופית. לכן, זהו תהליך זיהוי מפוזר של נתיב חלופי. אם הערוץ [A, H] אינו פועל, שוקל רק D:

1. בודק את השולחן המקומי שלך עבור יורחים אפשריים (שכנים במורד הזרם).
2. אין שום יורשים אפשריים, ולכן חייב למצוא נתיב חלופי ללא לולאות ל D (אם זה קיים).
3. שלח בקשה לכל שכן כדי לקבוע אם יש נתיב חלופי ללא לולאות לד.
4. ב C:
5. בב:
6. A מקבל תשובות אלה:

באיור 9, הפריט (D) הועבר עם H ל- E. זה ישמש בדוגמה השנייה.

בדוגמה זו, יש יורש אפשרי (השכן במורד הזרם).

מחקר D מנקודת מבט A:

1. A לומד שתי דרכים D:
2. A לא יזהה בכל דרך ב B:
3. A משווה את השבילים הזמינים ובוחר את הנתיב הקצר ביותר ללא לולאות:
4. בודק את השבילים הנותרים כדי לקבוע אם יש את כל השכנים במורד הזרם:

אם הערוץ [A, C] לא עובד, פשוט שוקל:

1. מחאות את טופרתו המקומית ליורש אפשרי.
2. יורש אפשרי קיים דרך H.
3. בורר את השולחן המקומי שלה על H כמו הדרך הטובה ביותר.
4. שולח עדכון לשכנותיה, וציין כי עלות ההישג שלו השתנה מ 3 עד 4.

כפי שאתה יכול לראות, עיבוד כאשר יש יורש אפשרי, הרבה יותר מהר וקל יותר מאשר בלי זה. ברשתות שבהן פרוטוקול הניתוב נפרס באמצעות כפול (בפרט, EIGRP), אחד מטרות העיצוב הראשי יגביל את נפח הבקשות שנוצרו בהיעדר יורש אפשרי. אזור הבקשה הוא הגורם הקובע העיקרי כיצד האלגוריתם הכפול הושלם במהירות, ולכן, כמה מהר הרשת מתכנסת.

איור 10 מציג את המחשב הבסיסי סיים כפול.

דברים שנכללו במסלול מחמיר (השפלה של המסלול) עשוי להיות:

• כישלון הערוץ המחובר או השכן
• קבלת עדכון עבור מסלול עם מטרי גבוה יותר
• קבלת שאילתה מהיורש הנוכחי
• מקבל מסלול חדש משכן
• נמצא שכן חדש, כמו גם מסלולים שבו הוא יכול לקבל
• קבלת כל הבקשות שנשלחו לשכנים כאשר המסלול מחריף